2015年7月9日

システムコールを経由する生のLinuxスレッド

Unix/Linux

(2015-05-15)by Chris Wellons

本記事は、原著者の許諾のもとに翻訳・掲載しております。

Linuxのスレッドは、洗練された美しい設計です。スレッドは仮想アドレス空間とファイルディスクリプタテーブルを共有するプロセスに過ぎません。プロセスによって生成されたスレッドは、メイン”スレッドの”親プロセスに追加された子プロセスです。これらは同じプロセス管理のシステムコールを通して処理されるので、スレッドに関するシステムコールのセットを分ける必要性を取り除きます。これはファイルディスクリプタと同様に洗練された方法です。一般的に、UNIX系のシステムではfork()を使ってプロセスを生成します。新しいプロセスは、オリジナルのコピーとして独自のアドレス空間とファイルディスクリプタテーブルを取得します。︵Linuxではコピーオンライトを使用して、この部分を効率的に処理します。︶しかし、これは非常に高度なスレッドの生成方法なので、Linuxでは別の clone() システムコールを使用します。folk()と同じような働きをしますが、主に親の実行コンテキストの一部を子と共有するために、いくつかのフラグを受け入れて振る舞いを調整するという点が異なります。これは 非常に 簡単なことなので、 15以下の命令で独自のスタックでのスレッドの生成が可能です 。ライブラリも、Pthreadの呼び出しも必要ないのです。この記事では、これをx86_64で行う方法について説明していきます。私個人の意見ですが、全てのコードが NASM の構文で書かれていれば最適です︵ nasm-mode を見てください︶。一度に説明を見たいという方には、こちらを用意しました。 ●純粋なアセンブリ、ライブラリなしのLinuxスレッドのデモ

x86_64入門

x8664のアセンブリになじみがない方でも理解できるように、関係のある事項を下記に簡単に説明します。すでにx8664のアセンブリを使用されている方は、次のセクションに進んでいただいて構いません。 x86_64には64ビットの 汎用レジスタ が16本あり、主にメモリアドレスを含む整数値の操作に使用されます。これ以外にも、より具体的な目的のための 多くの レジスタが存在しますが、スレッドの作成には必要ありません。 ●rsp ‥ スタックポインタ ●rbp ‥ “ベース”ポインタ︵デバッギングとプロファイリングに使用される︶ ●rax 、 rbx 、 rcx 、 rdx ‥ 汎用︵a、b、c、dに注意︶ ●rdi 、 rsi ‥ “デスティネーション”と”ソース”のことで、名前に意味はない ●r8 、 r9 、 r10 、 r11 、 r12 、 r13 、 r14 、 r15 ‥x86_64に追加された

頭に付いている”r”は、64ビットのレジスタであることを示しています。この記事の内容には関係のないことですが、”e”で始まる同じ名前のものはこれよりも低い32ビットのレジスタを、頭に何も付かないものは最も低い16ビットのレジスタであることを表わしています。これは、x86が元々は16ビットのアーキテクチャだったからです。そこから32ビット、64ビットと拡張されました。歴史的に、これらのレジスタはそれぞれ具体的でユニークな目的を持っていましたが、x86_64はほぼ完全な互換性を持っています。

スタック

rspレジスタは”トップの”コールスタックを指します。このスタックは、ローカル変数やその他の関数ステート︵ スタックフレーム ︶に加えて、current関数の呼び出しを追跡します。”トップの”という言葉を使いましたが、x86のスタックは低位のアドレスへ向かって 下方に 伸びていくので、スタックポインタはスタックで最も低位のアドレスを指します。私たちは独自のスタックを割り当てようとしているので、スレッドに関しては、この情報は重要です。また、このスタックは別の関数に引数を渡すために使用されることもあります。x8664では、それほど頻繁に行われません。最初の6個の引数がレジスタを経由して渡されるLinuxの [System V ABI](http://wiki.osdev.org/SystemV_ABI) では特にそうです。戻り値はraxを経由して返されます。他のfunction関数を呼び出す際には、整数値やポインタの引数は次のレジスタの順に渡されます。 ●rdi、rsi、rdx、rcx、r8、r9 例えば、 foo(1,2,3) のような関数呼び出しを実行すると、1、2、3が順にrdi、rsi、rdxに格納されてから関数を call します。 mov 命令はデスティネーション︵第1︶オペランドにソース︵第2︶オペランドを格納します。 call 命令はスタック上のripのcurrent値をプッシュし、ターゲット関数のアドレスにripをセット︵ ジャンプ ︶します。呼び出し先が戻る準備ができたら、 ret 命令でオリジナルのrip値をスタックから 取り出して ripに返し、呼び出し先のコントロールに戻ります。

    mov rdi, 1
    mov rsi, 2
    mov rdx, 3
    call foo

呼び出された関数は、以下のレジスタのコンテンツを保存する 必要があります ︵同じ値は関数が戻ったときに格納されます︶。 ●rbx、rsp、rbp、r12、r13、r14、r15

システムコール

システムコールを作成する際、引数を渡すレジスタが若干異なります。rcxがr10に置き換えられているのが分かると思います。 ●rdi rsi, rdx, r10, r8, r9 各システムコールには識別のための整数が割り振られています。プラットフォームによってこの番号は異なってきますが、Linuxにおいては、絶対に変わりません。raxは call の代わりに、呼び出したいシステムコールの番号に設定され、 syscall でOSカーネルにリクエストの命令を出します。x8664以前は、昔ながらの割り込みでシステムコールを呼び出していました。割り込みは遅いため、静的に位置づけられた”vsyscall”ページ︵今では [セキュリティ上危険](https://en.wikipedia.org/wiki/Return-orientedprogramming) であるため使用すべきではないとされています︶、後の vDSO が特定のシステムコールを呼び出す関数として用意されています。この記事で使うのは syscall のみです。例えば、write()システムコールをCのプロトタイプ宣言で表すとこうなります。

ssize_t write(int fd, const void *buf, size_t count);

x86_64では、システムコールテーブルの上部にcall 1としてwrite()システムコールが置かれています（read()は0）。標準出力はファイルディスクリプタ1がデフォルトとして設定されています（標準入力は0）。下のコードは10ﾊﾞｲﾄのデータをメモリアドレスの buffer （アセンブリ言語プログラム内の別の場所に定義済みのシンボル）から標準出力に書き出します。raxに返される値は、書き込みに成功した場合はそのバイト数、エラーの場合は-1となります。

    mov rdi, 1        ; fd
    mov rsi, buffer
    mov rdx, 10       ; 10 bytes
    mov rax, 1        ; SYS_write
    syscall

実効アドレス

もう1つ覚えておくべきことがあります。それは、レジスタは︵ポインタのように︶メモリアドレスを持つため、アドレスの指す場所のデータを読み込む方法が必要であるということです。NASM︵Netwideアセンブラ︶記法では、レジスタにはにブラケットを付けます。︵例‥ [rax] ︶C言語に慣れている場合は、ポインタの 参照先の値を取得する のと同じです。これらのブラケット表現は、 実効アドレス と呼ばれ、限られた数式で ベース アドレスを単一命令の範囲内でオフセットします。この表現では、別の インデックス レジスタ、 スカラ の2のべき乗︵ビットシフト︶、オフセットのそして、符号付きイミディエートオフセットを含むことができます。例えば、 [rax + rdx*8 + 12] の場合、もしraxが構造体へのポインタでrdxが構造体の中の要素の配列インデックスであれば、単一命令で要素を読み取ることができます。NASMには、アセンブリプログラマが複雑な表現で多少その型を崩したとしても [base + index*2^exp + offset] にまで短縮できるだけの賢さがあります。この記事では、アドレッシングの詳細は重要ではありません。理解できなくても気にしないでください。

スタックの割り当て

スレッドはリソースを共有しますが、レジスタやスタック、スレッドローカルストレージ︵TLS︶は共有しません。OSや基盤となるハードウェアは自動的にスレッドごとにレジスタを確保します。しかし、スレッドローカルストレージは必須ではないので、この記事では触れません。実際には、スタックはスレッドローカルデータとして使われています。スタックについては、新しいスレッドを立てる前に、スタックを割り当てる必要があります。これはメモリバッファにすぎません。通常は、実行可能なファイル内にスレッド用に固定の.bss︵ゼロで初期化︶ストレージを確保してスタックを割り当てます。しかし、私はPthreadsや他のスレッドライブラリのように、正しく動的にスタックを割り当てたいと思います。そうしないと、アプリケーションのスレッド数は、コンパイル時間に限定された固定の数になってしまいます。仮想メモリ内で、ただ任意のアドレスから読み込んだり書き込んだりすることはできません。まず、カーネルがページの割り当てをするように設定しなければなりません。Linuxにはこれを実現させる2つのシステムコールがあります。 ●brk()‥ 実行プロセスの領域を拡大︵または縮小︶し、通常は、.bssセグメントの直後に置かれます。多くのアロケータは小規模や初期の割り当てで行います。他の重要なデータや他のスタックに近く、︵デフォルトでは︶ガードページがないため、これは、スレッドスタックに最適とは言えません。バッファオーバーフローを悪用して、攻撃を仕掛けやすくしてしまいます。ガードページはロックダウンページで、スタックオーバーフローのセグメンテーション違反のトリガとなるスタックの最後にあります。検出されずにスタックオーバーフローで他のメモリを壊わすことを防ぎます。mprotect()を使って手動でガードページを作成することはできます。また、これらのスタックが拡張する余裕はありません。 ●mmap()‥ 無作為のメモリ領域に近接したページのセットを割り当てるために、無名マッピングを使います。後で分かりますが、このメモリをスタックとして使用することを具体的にカーネルに指示できます。そして何と言っても、brk()を使うより簡単です。 x86_64では、mmap()はシステムコール9です。スタックを割り当てる関数は、Cのプロトタイプ宣言ではこのように定義できます。

void *stack_create(void);

mmap()というシステムコールでは6個の引数を使いますが、無名メモリをマッピングする際、最後の2個の引数は無視されます。私たちの目的に合わせて使用すると、C言語の以下のプロトタイプ宣言に類似します。

void *mmap(void *addr, size_t length, int prot, int flags);

flags には、スタックとなって下方へ伸びるプライベートな無名マッピングを選びます。最後のフラグであっても、システムコールはマッピングの低位アドレスを戻しますが、これが後で重要になってきます。レジスタ内に引数を設定し、システムコールを作るのは実に簡単です。

%define SYS_mmap    9
%define STACK_SIZE  (4096 * 1024)   ; 4 MB

stack_create:
    mov rdi, 0
    mov rsi, STACK_SIZE
    mov rdx, PROT_WRITE | PROT_READ
    mov r10, MAP_ANONYMOUS | MAP_PRIVATE | MAP_GROWSDOWN
    mov rax, SYS_mmap
    syscall
    ret

これで必要に応じて新しいスタック（またはスタックサイズのバッファ）を割り当てることができます。

新しいスレッドを生成する

スレッドの生成は非常に簡単で、分岐命令すら必要ありません。2個の引数を使ってclone()を呼び出し、フラグと新しいスレッドのスタックポインタをコピーします。ここで大切なのは、多くの場合、glibcのラッパー関数とシステムコールでは引数の順番が異なることです。私たちが使用しているフラグのセットでは、2個の引数を使用します。

long sys_clone(unsigned long flags, void *child_stack);

私たちのスレッドのspawn関数は、以下のようなC言語プロトタイプ宣言を持つこととなります。これは引数として関数を使い、関数を実行してスレッドを開始します。

long thread_create(void (*)(void));

関数ポインタの引数は、ABIごとにrdi経由で渡されます。stack_create()を呼び出す準備として、この引数を保管するためにスタック上に保存（ push ）します。これが戻ると、スタックの最低位アドレスはraxの中に格納されます。

thread_create:
    push rdi
    call stack_create
    lea rsi, [rax + STACK_SIZE - 8]
    pop qword [rsi]
    mov rdi, CLONE_VM | CLONE_FS | CLONE_FILES | CLONE_SIGHAND | \
             CLONE_PARENT | CLONE_THREAD | CLONE_IO
    mov rax, SYS_clone
    syscall
    ret

clone()に渡す2個目の引数はスタックの 高位アドレス ︵具体的に言うとスタックのすぐ上︶を指すポインタです。最高位アドレスを得るためには、 STACK_SIZE をraxに加える必要があります。これは lea ︵load effective address︶命令を使って行います。ブラケットでくくられていますが、このアドレスではメモリを読み込みません。代わりにデスティネーションレジスタ︵rsi︶内にアドレスを保存します。私はこれを8バイト戻し、スレッド関数ポインタを次の命令内の新しいスレッドの”トップ”に置くことにしました。なぜこうするかは、すぐに分かるでしょう。

訳注: Thread Function Pointer = スレッド関数ポインタ Higher Addresses = より高位なアドレス Thread Stack = スレッドスタック Stack Growth = スタックが伸びる方向 関数ポインタは、保管のためにスタックの上部に押し上げられたことを思い出してください。これは現在のスタックから取り出され、新しいスタック内のあらかじめ決まった場所に書き込まれます。見ると分かりますが、clone()を使ってスレッドを生成するには、沢山のフラグを使用します。デフォルトでは、ほとんどが呼び出し先と共有されないため、実現するには数多くのオプションが必要です。clone(2)のmanページでこれらのフラグの全詳細を確認できます。 ●CLONE_THREAD ‥同じスレッドグループ内に新しいプロセスを加える ●CLONE_VM ‥同じ仮想メモリ空間内で実行する ●CLONE_PARENT ‥親プロセスを呼び出し先と共有する ●CLONE_SIGHAND ‥シグナルハンドラを共有する ●CLONE_FS 、 CLONE_FILES 、 CLONE_IO ‥ファイルシステムの情報を共有する新しいスレッドが生成され、システムコールが同じ命令で2つのスレッド内にそれぞれ戻ります。これはfork()に そっくり です。スレッド間の全てのレジスタが一致しますが、新しいスレッド内で0の値をとるraxと、新しいスレッド内でrsiと同じ値をとるrspは例外です(新しいスタックのポインタとなります)。 ここが非常に大切な部分であり 、分岐が不要な理由です。元のスレッド︵呼び出し元に返した場合︶か、新しいスレッド︵スレッド関数へ飛んだ場合︶かを見極めるために、raxをチェックする必要はありません。スレッド関数を使って新しいスタックを、どのように生成したかを思い出してください。新しいスレッドが戻る時︵ ret ︶、新しいスレッドは完全に空のスタックと一緒にスレッド関数まで飛びます。元のスレッドは、元のスタックを使って呼び出し元まで戻ります。 threadcreate()で戻される値は新しいスレッドのプロセスIDで、スレッドオブジェクトには必要不可欠です︵例えばPthreadの ` pthreadt ` です︶。

クリーンアップ

スレッド関数は戻る︵ ret ︶ことがないよう注意が必要です。なぜなら戻る場所がないからです。スレッド関数はスタックから離れ、セグメンテーション違反を引き起こしてプログラムを終了させてしまいます。スレッドがただのプロセスだったかどうかを思い出してください。必ずexit()というシステムコールを使って終了しなければいけません。他のスレッドでは終了しません。

%define SYS_exit    60

exit:
    mov rax, SYS_exit
    syscall

プログラムを終了する前にmunmap()というシステムコールを使ってスタックを解放し、スレッドを終了することによってリソースが漏れないようにします。メインの親プロセスによるpthread_join()は、wait4()というシステムコールをスレッドプロセスで使用することに相当します。

更なる探究

もしこの記事を面白いと感じたら、記事の最初にご紹介したフルバージョンのデモのリンクを確認してください。今やスレッドを大量生成できるようになったので、 lock 命令プリフィックスや xadd 、 compare-and-exchange ︵ cmpxchg ︶などのx86の同期プリミティブをさらに探究し、実験してみるには絶好のチャンスです。これについては今後の記事でお伝えしていきましょう。

古川陽介
株式会社リクルート　プロダクト統括本部　プロダクト開発統括室　グループマネジャー株式会社ニジボックス　デベロップメント室室長 Node.js 日本ユーザーグループ代表

複合機メーカー、ゲーム会社を経て、2016年に株式会社リクルートテクノロジーズ(現リクルート)入社。現在はAPソリューショングループのマネジャーとしてアプリ基盤の改善や運用、各種開発支援ツールの開発、またテックリードとしてエンジニアチームの支援や育成までを担う。 2019年より株式会社ニジボックスを兼務し、室長としてエンジニア育成基盤の設計、技術指南も遂行。 Node.js 日本ユーザーグループの代表を務め、Node学園祭などを主宰。

Twitter: @yosuke_furukawa
Github: yosuke-furukawa