Hatena::ブログ(Diary)

naoyaのはてなダイアリー

September 24, 2007

Linux カーネルのコンテキストスイッチ処理を読み解く

Linux カーネルのプロセススケジューラの核である kernel/sched.c の schedule() を読み進めていくと、タスク切り替え(実行コンテキスト切り替え)はその名も context_switch() という関数に集約されていることが分かります。2.6.20 の kernel/sched.c だと以下のコードです。

1839 static inline struct task_struct *
1840 context_switch(struct rq *rq, struct task_struct *prev,
1841                struct task_struct *next)
1842 {
1843         struct mm_struct *mm = next->mm;
1844         struct mm_struct *oldmm = prev->active_mm;
1845
1846         if (!mm) {
1847                 next->active_mm = oldmm;
1848                 atomic_inc(&oldmm->mm_count);
1849                 enter_lazy_tlb(oldmm, next);
1850         } else
1851                 switch_mm(oldmm, mm, next);
1852
1853         if (!prev->mm) {
1854                 prev->active_mm = NULL;
1855                 WARN_ON(rq->prev_mm);
1856                 rq->prev_mm = oldmm;
1857         }
1858         /*
1859          * Since the runqueue lock will be released by the next
1860          * task (which is an invalid locking op but in the case
1861          * of the scheduler it's an obvious special-case), so we
1862          * do an early lockdep release here:
1863          */
1864 #ifndef __ARCH_WANT_UNLOCKED_CTXSW
1865         spin_release(&rq->lock.dep_map, 1, _THIS_IP_);
1866 #endif
1867
1868         /* Here we just switch the register state and the stack. */
1869         switch_to(prev, next, prev);
1870
1871         return prev;
1872 }

context_switch() は Linuxカーネル2.6解読室 によると

  • プロセス空間の切り替えの処理 switch_mm() : 1851行目
  • 各種レジスタの切り替え switch_to() : 1869 行目

の二つから成っている、とのこと。(1) 仮想メモリの変換テーブル等を次のプロセス空間のものに切り替えて (2) CPU レジスタに設定されたハードウェアコンテキスト情報等を退避、切り替える... という二つの処理を行うのがコンテキストスイッチ。

この後者のレジスタ切り替えの処理がどうなっているのかな、と興味本位で switch_to() を覗いみるとたどり着いたのは include/asm-i386/system.h のマクロでした。

 14 /*
 15  * Saving eflags is important. It switches not only IOPL between tasks,
 16  * it also protects other tasks from NT leaking through sysenter etc.
 17  */
 18 #define switch_to(prev,next,last) do {                                  \
 19         unsigned long esi,edi;                                          \
 20         asm volatile("pushfl\n\t"               /* Save flags */        \
 21                      "pushl %%ebp\n\t"                                  \
 22                      "movl %%esp,%0\n\t"        /* save ESP */          \
 23                      "movl %5,%%esp\n\t"        /* restore ESP */       \
 24                      "movl $1f,%1\n\t"          /* save EIP */          \
 25                      "pushl %6\n\t"             /* restore EIP */       \
 26                      "jmp __switch_to\n"                                \
 27                      "1:\t"                                             \
 28                      "popl %%ebp\n\t"                                   \
 29                      "popfl"                                            \
 30                      :"=m" (prev->thread.esp),"=m" (prev->thread.eip),  \
 31                       "=a" (last),"=S" (esi),"=D" (edi)                 \
 32                      :"m" (next->thread.esp),"m" (next->thread.eip),    \
 33                       "2" (prev), "d" (next));                          \
 34 } while (0)

アセンブリ言語と C のコードが入り乱れたマクロ。一見何がなにやらですね。これは gcc の拡張機能で、C のコード内にインラインでアセンブリ処理を書ける asm() というキーワードを使ったコードです。インラインアセンブリと呼ばれます。

このインラインアセンブリなコードを読み解くために色々と調べごとをしたので、記憶を強めるためにもここで解説をしてみようと思います。なお、以下に記す内容はマシン語の基礎的な話が主ですが、僕はマシン語の知識はほぼ皆無なので相当適当な解説になってる可能性があります。間違いなどありましたら指摘いただけると嬉しいです。(あと、慣れてないものでアセンブル、アセンブリ、アセンブラ...の言葉の使い方がおかしいかもしれません。ツッコミ希望です。)

x86 且つ i386 (not x86_64) を前提に話を進めていきます。

GNU as でアセンブル

まずはインラインアセンブリを使わずに、素でアセンブリ言語を書くところから。Linux カーネルは gcc でコンパイルされており、gcc はアセンブラに GNU as を利用します。故にアセンブラには gas を使うことになります。

手始めに「何もしない」バイナリを gas で作ってみます。.s ファイルに GNU as (gas) の構文でアセンブリ命令を記述していきます。

.file "do_nothing.s"
.global main

main:
        ret

C言語で main() が最初に呼ばれるのは libc が main というシンボルをバイナリの中から見つけて、それをエントリポイントとして処理を開始する仕組みになっているからです。従って、何もしない (ret するだけの) main というシンボルを用意して、これを gcc で libc とリンクしてやるとバイナリを実行したときにこの main の箇所から処理が始まることになります。ただし、リンカからシンボルを参照できるようにするためには、.global ディレクティブで明示的に公開したいシンボルを指定する必要があります。

これを gcc でコンパイル。gcc は拡張子 .s のファイルはアセンブリファイルであると自動判定してコンパイル、リンクを行ってくれます。

% gcc do_nothing.s -o do_nothing

実行してみます。

% ./do_nothing
%

当然何も起きません。意図したとおりに動いています。ldd で共有ライブラリの依存関係を確認してみます。

% ldd do_nothing
        linux-gate.so.1 =>  (0xffffe000)
        libc.so.6 => /lib/tls/libc.so.6 (0xb7eb0000)
        /lib/ld-linux.so.2 (0xb7feb000)

libc とリンクしているのがわかります。

アセンブリ言語でシステムコール呼び出し

何もしないバイナリでは面白くないのでお決まりの Hello World! を、といきたいところです。が、一筋縄にはいきません。そうです、Hello World! を画面に出力するにはアセンブリ言語で x86 Linux カーネルのシステムコール (write(2)) を呼ぶ必要があるのです。この辺の解説は 404 Not Found が詳しいのでご参照ください。

簡単にまとめると「システムコール番号と引数を汎用レジスタに設定してソフトウェア割り込み 0x80 を発行」、すなわち

  • システムコールには例えば exit(2) は 1、write(2) は 4 などと整数で番号が振られている
  • 呼び出したいシステムコールに対応した番号を eax に設定する
  • システムコールへの引数を ebx, ecx, edx, eci, edi, ebp に設定する (引数が1つなら1つめを ebx、2 つなら 1つ目を ebx 2つ目を ecx ...)
  • ソフトウェア割り込み int 0x80 を発行する

という手順で命令を出すことでカーネルにシステムコールを発行することができます。

ソフトウェア割り込みが CPU に発行されると CPU はあらかじめ設定された割り込みハンドラを実行します。x86 Linux では 0x80 に設定された割り込みベクタがシステムコール起動処理に対応しています。割り込みを契機に CPU は特権モードに移ってスタックがカーネルスタックに切り替わり、eax レジスタからシステムコール番号を取得して対応するシステムコールを起動します。

システムコール番号とシステムコールの対応は i386 Linux の場合 i386/kernel/syscall_table.S に記述されています。

ENTRY(sys_call_table)
        .long sys_restart_syscall       /* 0 - old "setup()" system call, used for restarting */
        .long sys_exit
        .long sys_fork
        .long sys_read
        .long sys_write
        .long sys_open          /* 5 */
...

この sys_call_table をシステムコール番号で検索すると対応するシステムコールのシンボル名が取得できるという流れです。上記を見ても確かに exit は 1、 write は 4 です。

なお、最近の x86 では int 0x80 命令でのシステムコール呼び出しはすでに古く、sysenter 命令を使った方がより高速に処理が可能とのことです。

では、int 0x80 命令を使用して write(2) を発行してみます。write(2) をアセンブリ言語で起動するには

  • eax に 4 を設定
  • ebx にファイルディスクリプタの番号を指定 (標準出力は 0番)
  • ecx に出力する文字列の先頭アドレスを指定
  • edx に出力するデータの長さを指定
  • int 0x80

となります。この命令をそのまま記述すれば OK。

.file "hello_world.s"
.data
msg:    .ascii "Hello, World!\n"

.global main

main:
        movl    $0x04, %eax    # 0x04 = write(2)
        movl    $0x00, %ebx    # 0x00 = stdout
        movl    $msg, %ecx
        movl    $14, %edx
        int     $0x80
        ret

となります。

  • gas では (1) .data ディレクティブでデータセクションの開始を指定して (2) クォートされた文字列をにラベル指定 (msg:)しつつその先頭アドレスを後から $msg で参照するといったことができます。
  • 即値は $0x04 など $ を付けて記述します。
  • レジスタには % を付けます。

文字列の長さを 14 とハードコードしてしまってるのがちとダサいですがわかりやすさのためにとりあえずはこれで。これを先ほどと同じように gcc でコンパイル。

% ./hello_world
Hello, World!

できました。万歳。

(脱線その1) シンボルの種類

少し脱線。readelf -s でバイナリのシンボルに関する情報を覗いてみると

% readelf -s hello_world | grep main
     1: 00000000   231 FUNC    GLOBAL DEFAULT  UND __libc_start_main@GLIBC_2.0 (2)
    71: 0804954a     0 NOTYPE  GLOBAL DEFAULT   22 main
    72: 00000000   231 FUNC    GLOBAL DEFAULT  UND __libc_start_main@@GLIBC_

と main が NOTYPE になっています。http://sourceware.org/binutils/docs-2.18/as/Type.html#Type によれば、シンボルの種類は明示的に .type ディレクティブで指定することが可能だそうです。

.file "hello_world.s"
.data
msg:    .ascii "Hello, World!\n"

.global main
        .type   main, @function
main:
        movl    $0x04, %eax
        movl    $0x00, %ebx
        movl    $msg, %ecx
        movl    $14, %edx
        int     $0x80
        ret

と、.type ディレクティブを追加して main は関数である旨を明記しました。これでコンパイルしたバイナリは

% readelf -s hello_world | grep main
     1: 00000000   231 FUNC    GLOBAL DEFAULT  UND __libc_start_main@GLIBC_2.0 (2)
    71: 0804954a     0 FUNC    GLOBAL DEFAULT   22 main
    72: 00000000   231 FUNC    GLOBAL DEFAULT  UND __libc_start_main@@GLIBC_

と、NOTYPE だったところが FUNC になりました...とそこまではいいのですが、実際問題ここが NOTYPE だったり FUNC だったりするのが何に関わってくるかがよくわかっていません。誰か教えてください。

(脱線その2) libc にリンクしないバイナリにする

脱線その2。

% ls -la hello_world
-rwxr-xr-x 1 naoya naoya 6849 2007-09-24 21:56 hello_world

とここまでで作ったバイナリのサイズを見ると 6,849 バイトもあります。Hello, World ! を出力するだけなのに随分と大きい。システムコールは libc を経由せずに直接呼び出しているわけですし、プログラムでやっている処理で libc の機能が必要なのは main() からプログラムを起動するという規約の実装、それだけです。ここは一丁 libc を使わないバイナリに仕立て上げてみましょう。

ld の -e (--entry) オプションを指定すると、どのシンボルから処理を開始するかを明示的に指定することができます。

% as -o hello_world.o hello_world.s
% ld -o hello_world -e main hello_world.o

とアセンブルとリンクを明示的に行います。この場合 libc とリンクしなくなるので、バイナリのどこから処理を始めればいいか OS がわからなくなります。そこで -e オプションで main を指定して、そのアドレスを教えておきます。

% ldd hello_world
        not a dynamic executable

ldd すると、どの共有ライブラリも必要としないバイナリになっているのがわかります。気になるサイズの方は、

% ls -la hello_world
-rwxr-xr-x 1 naoya naoya 612 2007-09-24 21:54 hello_world

612バイト。だいぶ小さくなりました。ちゃんと実行できるか試してみます。

% ./hello_world
Hello, World!
[1]    25473 segmentation fault (core dumped)  ./hello_world

おっと Hello, World! を出すまではよかったですがそこでセグフォ。コードを見てみます。

main:
        movl    $0x04, %eax
        movl    $0x00, %ebx
        movl    $msg, %ecx
        movl    $14, %edx
        int     $0x80
        ret

write(2) を実行した後にやっているのは単に ret で呼び出し元へ返るのみ...がここが問題。libc 下では libc が main の返値を受け取って exit(2) を呼び出すなんていう後処理をしてくれているので main からは ret するだけでよかったわけですが、このバイナリは libc とリンクしてないわけで、誰もそんな面倒を見てくれないのです。

そこで、exit(2) 呼び出しも自分で書きます。write(2) のときと手順はほとんど一緒。

.file "hello_world.s"
.data
msg:    .ascii "Hello, World!\n"

.global main
        .type   main, @function
main:
        movl    $0x04, %eax     # write (2)
        movl    $0x00, %ebx     # stdout
        movl    $msg, %ecx
        movl    $14, %edx
        int     $0x80

        movl    $0x01, %eax     # exit
        movl    $0x00, %ebx     # exit(0)
        int     $0x80

これでセグフォしなくなります。

なお、Hello World! な ELF バイナリを極限まで小さくするという話題はこの辺が変態的で楽しいです。

C とアセンブリコードを混ぜる

脱線しすぎたので本論へ。gas でのコードの書き方はだいたい分かってきたところで、次は C 言語とアセンブリ言語を(インライアセンブリを使わずに) 混ぜたプログラムにしてみます。といっても一つのファイルに二種類書くわけじゃなく、それぞれ個別のファイル .c ファイルと .s ファイルへ。

  • 引数を二つ受け取ってその二つの数を足して返す add という関数をアセンブリ言語で
  • add を呼び出して実行する main() を C で

それぞれ書いてリンクさせて関数呼び出しの裏側を見てみます。

まずは C の側から。

#include <stdio.h>

int main()
{
    printf("%d\n", add(3, 5));
    return 0;
}

何の変哲もない。まだ add が用意されてないので実行ファイルは作れませんがオブジェクトファイルにはできます。

% gcc -c add_main.c -o add_main.o

で、このオブジェクトファイルを readelf してみます。

% readelf -s add_main.o

シンボルテーブル '.symtab' は 11 個のエントリから構成されています:
  番号:      値 サイズ タイプ  Bind   Vis      索引名
     0: 00000000     0 NOTYPE  LOCAL  DEFAULT  UND
     1: 00000000     0 FILE    LOCAL  DEFAULT  ABS add_main.c
     2: 00000000     0 SECTION LOCAL  DEFAULT    1
     3: 00000000     0 SECTION LOCAL  DEFAULT    3
     4: 00000000     0 SECTION LOCAL  DEFAULT    4
     5: 00000000     0 SECTION LOCAL  DEFAULT    5
     6: 00000000     0 SECTION LOCAL  DEFAULT    6
     7: 00000000     0 SECTION LOCAL  DEFAULT    7
     8: 00000000    71 FUNC    GLOBAL DEFAULT    1 main
     9: 00000000     0 NOTYPE  GLOBAL DEFAULT  UND add
    10: 00000000     0 NOTYPE  GLOBAL DEFAULT  UND printf

add や printf が UND (Undefined) です。printf は libc から借りてくる、add は自分で実装する、というわけです。この add を自分で実装するというのはどういうことか。libc が main を期待しているので main というシンボルの元にサブルーチンを作ったのと同じく、add を期待されているので add というシンボルの元にサブルーチンを定義し、.global 指定すれば OK。

もう一つ別の見方をしてみます。gcc -S で C をコンパイルした段階でとめてアセンブリ言語で処理を見てみます。

% gcc -S add_main.c -o add_main.s

add_main.s は以下のようになります。

  1         .file   "add_main.c"
  2         .section        .rodata
  3 .LC0:
  4         .string "%d\n"
  5         .text
  6 .globl main
  7         .type   main, @function
  8 main:
  9         pushl   %ebp
 10         movl    %esp, %ebp
 11         subl    $8, %esp
 12         andl    $-16, %esp
 13         movl    $0, %eax
 14         addl    $15, %eax
 15         addl    $15, %eax
 16         shrl    $4, %eax
 17         sall    $4, %eax
 18         subl    %eax, %esp
 19         movl    $5, 4(%esp)
 20         movl    $3, (%esp)
 21         call    add
 22         movl    %eax, 4(%esp)
 23         movl    $.LC0, (%esp)
 24         call    printf
 25         movl    $0, %eax
 26         leave
 27         ret
 28         .size   main, .-main
 29         .section        .note.GNU-stack,"",@progbits
 30         .ident  "GCC: (GNU) 3.4.6 (Debian 3.4.6-5)"

いろいろごちゃごちゃとあるのですが、注目するのは 21 行目。"call add" で add というルーチンが呼ばれています。その add がまだ定義されてない。従ってこの add というサブルーチンを他のファイルで定義してやってリンクすれば OK、というのがわかります。

add.s は以下のようになります。

  1 .file   "add.s"
  2 .global add
  3         .type add, @function
  4
  5 add:
  6         pushl   %ebp
  7         movl    %esp, %ebp
  8         movl    12(%ebp), %eax  # y => 12(%ebp)
  9         addl    8(%ebp), %eax   # x => 8(%ebp)
 10         popl    %ebp
 11         ret

この add は C言語の関数呼び出しの規約 (cdecl 呼出規約 - Wikipedia) をアセンブリ言語で実装したものになります。この辺の解説は (インラインアセンブリの解説も含めて ) gccのx86インラインアセンブリに関して が具体的で分かりやすいと思います。

Cの関数呼び出し規約では関数の引数はそのプログラムのスタック領域に積まれます。呼び出された側の関数であるところの add では引数をスタックから取り出して足し算を行い、結果を呼び出し元に返却します。

  • 現在のスタックトップのアドレスは esp に設定されている
  • x86 の場合スタックは上位から下位に伸張する
  • 後ろの引数から順にスタックに積まれる。関数の戻りアドレスも詰まれる。 (ここでは int y → int x → 戻りアドレスの順)
  • 続く7行目で ebp レジスタの値を破壊するので、元の値は事前にスタックに積んで(push して)退避しておく (6行目)
  • 引数を取り出すのに esp をそのまま使うと色々面倒なのでそれを ebp に設定する (7行目)
  • ebp から見ると「ebp + 8バイト」に第一引数「ebp + 12バイトに第二引数」が積まれている
    • ebp は 32 ビットレジスタなので 4 バイト
    • 「ebp + 4バイト」には戻りアドレス
    • 引数はいずれも int なので 4 バイト → 引数は 「ebp + 8 バイト」「ebp + 12 バイト」に積まれている
    • 「ebp + 8バイト」は gas では 8(%ebp) という間接参照と呼ばれる文法で指定する。(C で言うところの a[i] みたいなもん)
  • 12(%ebp) で第二引数を取り出して eax に設定 (8行目)
  • 8(%ebp) で第一引数を取り出して eax に足しこむ (9行目)
  • 関数の戻り値は eax に突っ込んでおくという決まり。すでに eax には x + y の結果が入っている
  • 最初に退避しておいた ebp の値をスタックから取り出す (pop する) (10行目)

という流れになります。図を描くと分かりやすいです。(後で図を追加します。)

これで main、add が揃ったので実行ファイルが作れます。

% gcc *.s -o add
% ./add
8

add() に 3 と 5 を渡したら 8 になりました。ちゃんと動いてます。

インラインアセンブリ

さて、前振りが長くなりましたがここからが本番。gcc 拡張機能のインラインアセンブラを使って、別々になっていた C による main() とアセンブリ言語による add を一つの .c ファイルの中に定義します。

インラインでアセンブリ言語のコードを C のソースに埋め込むには asm() というキーワードを使います。(ANSI C では asm は使えません。gcc -std=c99 をしてる場合は __asm__ を使います。asm も __asm__ も同じです。) asm() の中に文字列で gas の構文を書けば OK です。

#include <stdio.h>

int add(int x, int y)
{
    asm(
        "movl 8(%ebp), %eax;"
        "addl 12(%ebp), %eax"
        );
}

int main ()
{
    printf("%d\n", add(3, 5));
    return 0;
}

となります。

先ほどの add.s に比べるとアセンブリコードが 4 行減りました。これは asm() で処理を記述する場所がすでに C の関数内なので、関数呼び出し規約の実装に相当する ebp の退避や esp のコピー等が必要ない (コンパイラがその部分コードを生成してくれる) ためです。

関数の戻り値は eax に積むのでした。上記ではインラインアセンブリの処理が終わった時点で計算結果は eax に入っているので、return などせずに関数を終えています。

% gcc -Wall inline_add.c -o inline_add
inline_add.c: In function `add':
inline_add.c:9: 警告: 制御が非 void 関数の終りに到達しました

と、return を書いていないのでコンパイル時に警告は出ますがアセンブリレベルでは return するのと同じコードが吐かれるので大丈夫です。実行してみましょう。

% ./inline_add
8

正しく 8 が出力されました。

インラインアセンブリで書いたコードはどのように出力されるでしょうか。gcc -S でコンパイルして確認してみます。

% cat inline_add.s
        .file   "inline_add.c"
        .text
.globl add
        .type   add, @function
add:
        pushl   %ebp
        movl    %esp, %ebp
#APP
        movl 8(%ebp), %eax;addl 12(%ebp), %eax
#NO_APP
        popl    %ebp
        ret
        .size   add, .-add
        .section        .rodata
.LC0:
        .string "%d\n"
        .text
.globl main
        .type   main, @function
main:
        pushl   %ebp
        movl    %esp, %ebp
        subl    $8, %esp
        andl    $-16, %esp
        movl    $0, %eax
        addl    $15, %eax
        addl    $15, %eax
        shrl    $4, %eax
        sall    $4, %eax
        subl    %eax, %esp
        movl    $5, 4(%esp)
        movl    $3, (%esp)
        call    add
        movl    %eax, 4(%esp)
        movl    $.LC0, (%esp)
        call    printf
        movl    $0, %eax
        leave
        ret
        .size   main, .-main
        .section        .note.GNU-stack,"",@progbits
        .ident  "GCC: (GNU) 3.4.6 (Debian 3.4.6-5)"

となります。一見分かりにくいので、add() に相当するところだけに絞ると

add:
        pushl   %ebp
        movl    %esp, %ebp
#APP
        movl 8(%ebp), %eax;addl 12(%ebp), %eax
#NO_APP
        popl    %ebp
        ret

ですね。 一行で繋がってしまってますが #APP 〜 #NO_APP で囲まれた箇所がインラインアセンブリで埋め込んだコードに相当するのが分かります。前後のコードも含め、先に素で書いたアセンブリコードとまったく同じ命令が並んでいます。

x86拡張インラインアセンブリ

インラインアセンブリでアセンブリコードを埋め込めるようになったところで、次は x86 拡張アセンブリを使って C言語側で確保したメモリ領域とのやりとりをスマートにしてみます。

先のコードではスタックに積まれた関数の引数を取得するのに 8(%ebp) や 12(%ebp) など ebp レジスタを意識した記述をしました。また戻り値も eax に積まれるという規約を前提にごまかした感があります。

ここで

  • そもそも引数である x や y は関数内部では変数として参照できるわけで、これをインラインアセンブリの中で使えれば ebp を意識せずに書ける
  • インラインアセンブリの中で設定された値を C の変数に書き出すことができれば C 側の変数に値をセットして return 文でそれを返すことができる

ということが言えます。このような C 側で確保したメモリ領域とインラインアセンブリのコードの連携を実現するのが x86 拡張インラインアセンブリ構文です。

  • asm(アセンブリテンプレート : 出力オペランド : 入力オペランド : 破壊されるレジスタのリスト)

という構文を使うと、任意のレジスタを C の変数に書き出したり、C の任意の変数の内容を任意のレジスタに設定した上でアセンブリの処理を進めたりすることができます。

x86 拡張インラインアセンブリ構文については

が詳しく参考になります。

例えば

asm(
    "movl $0x01, %eax;"
    "addl $0x05, %eax"
);

というインラインアセンブリは (1) 即値 0x01 を eax に設定 (2) 即値 0x05 を eax に足しこむ、ということをやっていてこの処理が終わった直後に eax は 0x06 になっています。この eax に設定された足し算の結果を C の変数に格納したい場合は拡張構文で

int result;
asm(
    "movl $0x01, %%eax;"
    "addl $0x05, %%eax"
    : "=a" (result)
);

と書くことができます。

  • 前半の文字列部分がアセンブリテンプレート
    • アセンブリテンプレート内ではレジスタは "%%eax" と % を2つ指定して記述する必要があります
  • : 以降が出力オペランドの指定
  • 入力オペランド、破壊されるレジスタのリストは使わないので省略

となっています。

出力オペランドの指定箇所がポイントです。"=a" (result) は「アセンブリの処理の最後に eax に設定された値を result という変数に書き出しなさい」という指定になります。この指定に従って、result に 0x06 が代入されることになります。

入力オペランドも指定してみましょう。例文の中で即値で 0x01 や 0x05 としている箇所を C の変数にセットされた値を使うように変更してみます。

int x = 1, y = 5;
int result;
asm(
    "movl %2, %%eax;"
    "addl %1, %%eax"
    : "=a" (result)
    : "m" (x), "m" (y)
);

「"m" (x), "m" (y)」が入力オペランドの指定です。

  • メモリ中に x、y を設定し、その値をインラインアセンブリの中から指定できるようにしています
  • アセンブリテンプレートの中の %1 が %2 が、入出力オペランドに指定した値を参照するための指示詞
    • %0 が result
    • %1 が x
    • %2 が y

です。これで x や y に代入されている値を使って計算が行われます。

さらにもう少し短くしてみます。上記のコードでは

  • x = x + y として結果を x を破壊して受け取るようにする。この場合 result は要らない。
  • 明示的に eax を経由して計算を行っているが、命令的には x + y してるだけなのでそのように記述。

これを加味すると

int x = 1, y = 5;
asm(
    "addl %2, %0;"
    : "=r" (x)
    : "0" (x), "m" (y)
);

となります。

  • この場合 x は入出力兼用。
  • 入力オペランドで "0" というのはアセンブリテンプレート内で %0 と同等の意味を持ち、このように書くことで x が入出力兼用であることを指定することができます
  • 出力オペランドに指定した "=r" は任意のレジスタを意味するもので、x 用に任意のレジスタを割り当ててその内容を最後に x に書き出してね、という指定になります
  • これで %0 が x、%2 が y、結果は x に出力する ... という準備は整いました。addl %2, %0 で x = x + y 相当の命令が記述できます

ここまでくれば先の add() 関数をインラインアセンブリのコードを拡張構文を使って書き直すことができますね。以下のようになりました。

#include <stdio.h>

int add(int x, int y)
{
    asm(
        "addl %2, %0;"
        : "=r" (x)
        : "0" (x), "r" (y)
        );
    return x;
}

int main ()
{
    printf("%d\n", add(3, 5));
    return 0;
}

引数の x、y を受け取って x = x + y してその結果を return しています。

マクロ + インラインアセンブリでインライン展開

インラインアセンブリなコードはもちろんマクロに使うこともできます。先の add() を関数でなくマクロとして定義すると以下のようになります。

#include <stdio.h>

#define add(x, y)                                \
    ({                                           \
        int _x = (x), _y = (y);                  \
        asm(                                     \
            "addl %2, %0;"                       \
            : "=r" (_x)                          \
            : "0" (_x), "r" (_y)                 \
            );                                   \
        _x;                                      \
    })

int main ()
{
    printf("%d\n", add(3, 5));
    return 0;
}

当然ですが、マクロにした場合引数の x, y にはメモリは割り当てられていないのでそれを直接拡張構文の入出力オペランドに指定することはできません。そこで int _x = (x) と新たに変数を用意してそこに値を格納、その変数を入出力オペランドとして指定します。

このマクロで定義した add() は、コンパイラがインライン展開してくれます。さらにインラインアセンブリのコードも展開されます。試しに上記コードのコンパイル済みのアセンブリコードを見てみます。

% cat macro_add.s
        .file   "macro_add.c"
        .section        .rodata
.LC0:
        .string "%d\n"
        .text
.globl main
        .type   main, @function
main:
        pushl   %ebp
        movl    %esp, %ebp
        subl    $24, %esp
        andl    $-16, %esp
        movl    $0, %eax
        addl    $15, %eax
        addl    $15, %eax
        shrl    $4, %eax
        sall    $4, %eax
        subl    %eax, %esp
        movl    $3, -4(%ebp)     // int _x = 3
        movl    $5, -8(%ebp)     // int _y = 5
        movl    -4(%ebp), %edx   // _x の値を edx に設定
        movl    -8(%ebp), %eax   // _y の値を eax に設定
#APP
        addl %eax, %edx;         // 加算
#NO_APP
        movl    %edx, %eax       // 加算結果を eax に設定
        movl    %eax, -4(%ebp)   // eax の値を _x に設定
        movl    -4(%ebp), %eax
        movl    %eax, 4(%esp)
        movl    $.LC0, (%esp)
        call    printf
        movl    $0, %eax
        leave
        ret
        .size   main, .-main
        .section        .note.GNU-stack,"",@progbits
        .ident  "GCC: (GNU) 3.4.6 (Debian 3.4.6-5)"

add の定義はなく、main の定義内に各種処理が直接インライン展開されているのが分かります。(このコード自体は少々最適化の余地が残っていそうですが) このようにインラインアセンブリをマクロ定義しておくことで add(3, 5) のようにあたかも関数のように見せかけて、インラインに任意のアセンブリ命令を埋め込むことができます。

冒頭でみたレジスタ退避処理を行う switch_to() はこの手法でマクロとして定義されています。カーネルのコンテキストスイッチは非常に頻繁に実行される処理なので、マクロでインライン展開させることにより性能を稼いでいるものと思われます。

システムコールをインラインアセンブリで

少し脱線気味になりますが、アセンブリ言語からのシステムコール呼び出し (write(2) / exit(2)) をインラインアセンブリで書いてみます。まずはわかりやすさのため拡張構文なしで。先に見たアセンブリでの write(2) や exit(2) の記述、つまり汎用レジスタにシステムコール番号と引数を積んで int 0x80 なコードをそのまま asm() 内に書くだけ。

int my_write(const char *str, int len)
{
    asm(
        "movl $0x04, %eax;"
        "movl $0x00, %ebx;"
        "movl 8(%ebp), %ecx;"
        "movl 12(%ebp), %edx;"
        "int $0x80"
        );
}

int my_exit(int st)
{
    int ret = 0;
    asm(
        "movl $0x01, %eax;"
        "movl 8(%ebp), %ebx"
        );
    return ret;
}

int main()
{
    my_write("Hello, World!\n", 14);
    my_exit(0);
    return -1;
}

となります。

次にこのコードを拡張構文を使ってもう少し綺麗にします。例えば my_write() のインラインアセンブリで write(2) を呼んでるわけですが、改めて wirte(2) の呼び方を振り返ると

  • eax にシステムコール番号 0x04 を設定
  • ebx に標準出力のファイルディスクリプタ 0x00 を設定
  • ecx に文字列の先頭アドレス (str) を設定
  • edx にデータの長さ(len) を設定
  • int 0x80

となります。ここで ecx に str の値を入力するには拡張構文として入力オペランドの "c" (str) が使えますし、同様に edx に len は "d" (len) と記述できます。この容量で C の変数と連携を取って余分なコードを省きます。

int my_write(const char *str, int len)
{
    int ret = 0;
    asm(
        "movl $0x04, %%eax;"
        "movl $0x00, %%ebx;"
        "int $0x80"
        : "=a" (ret)
        : "c" (str), "d" (len)
        );
    return ret;
}

int my_exit(int st)
{
    int ret = 0;
    asm(
        "movl $0x01, %%eax;"
        "int $0x80"
        : "=a" (ret)
        : "b" (st)
        );
    return ret;
}

int main()
{
    my_write("Hello, World!\n", 14);
    my_exit(0);
    return -1;
}

となりました。これで問題なく動きます。このように C の変数に格納された値をシステムコールの引数に相当する各種汎用レジスタに積む手続きを入力オペランドの指定で済ませているのがミソですね。

Linux 2.6 の switch_to() を読み解く

駆け足でしたがここまでで x86 インラインアセンブリの説明は終わり。いよいよ本丸、switch_to() の中を改めて見てみます。

 14 /*
 15  * Saving eflags is important. It switches not only IOPL between tasks,
 16  * it also protects other tasks from NT leaking through sysenter etc.
 17  */
 18 #define switch_to(prev,next,last) do {                                  \
 19         unsigned long esi,edi;                                          \
 20         asm volatile("pushfl\n\t"               /* Save flags */        \
 21                      "pushl %%ebp\n\t"                                  \
 22                      "movl %%esp,%0\n\t"        /* save ESP */          \
 23                      "movl %5,%%esp\n\t"        /* restore ESP */       \
 24                      "movl $1f,%1\n\t"          /* save EIP */          \
 25                      "pushl %6\n\t"             /* restore EIP */       \
 26                      "jmp __switch_to\n"                                \
 27                      "1:\t"                                             \
 28                      "popl %%ebp\n\t"                                   \
 29                      "popfl"                                            \
 30                      :"=m" (prev->thread.esp),"=m" (prev->thread.eip),  \
 31                       "=a" (last),"=S" (esi),"=D" (edi)                 \
 32                      :"m" (next->thread.esp),"m" (next->thread.eip),    \
 33                       "2" (prev), "d" (next));                          \
 34 } while (0)

呪文のようだったコードですが、ここまでで説明した内容に照らし合せると

  • マクロで switch_to() が定義されている
  • asm () を使ったインラインアセンブリで各種命令が記述されている
  • 拡張構文で prev や next らのオブジェクトが保持する値をレジスタに設定して演算している

ということが分かると思います。(asm volatile (...) の volatile はコンパイラの最適化抑制を意味します。このインラインアセンブリのコードがコンパイラによる最適化で意図しないコードになってしまうのを防ぐための処置です。)

拡張構文のままですと入力/出力がどうなっているかも含めた命令の流れがわかりにくいので、このインラインアセンブリコードを展開してみます。

        /* 入力オペランドの処理 */
        movl    prev, %eax
        movl    next, %edx

        /* 本体 */
        pushfl                           /* Save flags */
        pushl   %ebp
        movl    %esp, prev->thread.esp   /* save ESP */
        movl    next->thread.esp, %esp   /* restore ESP */
        movl    $1f, prev->thread.eip    /* save EIP */
        pushl   next->thread.eip         /* restore EIP */
        jmp     __switch_to
1:
        popl    %ebp
        popfl

        /* 出力オペランドの処理 */
        movl    %eax, last
        movl    %esi, esi
        movl    %edi, edi

実際にはアセンブリ言語内で prev->thread.esp といった参照の仕方はできないのでこのコードは駄目なんですが、擬似コードということでひとつ。

ここで prev や next (あと last) はプロセスやスレッドのカーネル内部でのデータ表現である task_struct 構造体のインスタンスです。task_struct 構造体のインスタンスはプロセスディスクリプタと呼ばれます。プロセスディスクリプタはカーネル内構造体の中でも非常に重要なオブジェクトで、ここにプロセスの状態やアドレス空間の情報等、プログラムが実行時に実体化された後に必要な情報が詰まっています。実行コンテキストを切り替えるというのは結局、

  • prev のメモリ空間を next のメモリ空間へ切り替える
  • prev のハードウェアコンテキスト (CPU のレジスタに設定された値) を prev 内の領域に退避
  • next 内の領域にあるハードウェアコンテキストを復帰

という処理のことになります。ハードウェアコンテキストの退避は

  • 一部をプロセスディスクリプタ内に
  • 一部をカーネルモードプロセススタックに

格納することで行われます。前者を格納する場所を見てみます。include/linux/sched.h に task_struct の定義があります。

struct task_struct {
    ....
/* CPU-specific state of this task */
    struct thread_struct thread;
    ....
}

と、thread メンバに CPU 状態を保存する thread_struct という別のオブジェクトが格納されています。thread_struct は CPU 依存の低レベルな実行コンテキスト情報を格納するオブジェクトです。

i386 の thread_struct は include/asm-i386/processor.h に定義があります。

struct thread_struct {
/* cached TLS descriptors. */
    struct desc_struct tls_array[GDT_ENTRY_TLS_ENTRIES];
    unsigned long   esp0;
    unsigned long   sysenter_cs;
    unsigned long   eip;
    unsigned long   esp;
    unsigned long   fs;
    unsigned long   gs;
/* Hardware debugging registers */
    unsigned long   debugreg[8];  /* %%db0-7 debug registers */
/* fault info */
    unsigned long   cr2, trap_no, error_code;
/* floating point info */
    union i387_union    i387;
/* virtual 86 mode info */
    struct vm86_struct __user * vm86_info;
    unsigned long       screen_bitmap;
    unsigned long       v86flags, v86mask, saved_esp0;
    unsigned int        saved_fs, saved_gs;
/* IO permissions */
    unsigned long   *io_bitmap_ptr;
    unsigned long   iopl;
/* max allowed port in the bitmap, in bytes: */
    unsigned long   io_bitmap_max;
};

プログラムカウンタ (eip) やスタックポインタ (esp) など 32 ビットレジスタを収めるメンバが見つかります。これが先の拡張構文の入出力オペランドに指定されている prev->thread.esp や prev->thread.eip です。繰り返しになりますが、これらのメモリ領域はプロセスディスクリプタ内のレジスタの保存場所、ということですね。

では改めて、switch_to() のアセンブリコードを。少しずつ見ていくとします。

        /* 入力オペランドの処理 */
        movl    prev, %eax
        movl    next, %edx

拡張構文の入力オペランド指定を展開した箇所です。prev、next のアドレスをそれぞれ eax と edx に設定しています。一見なんでそんなことを、と思うのですがこれは後で jmp する __switch_to() 関数へのレジスタ経由での引数渡しのためです。詳しくは後述します。

        /* 本体 */
        pushfl                           /* Save flags */
        pushl   %ebp

インラインアセンブリで定義された処理本体に入っていきます。

  • pushfl でフラグレジスタ EFLAGS をスタックに退避
  • ebp をスタックに退避

この時点での実行コンテキストはまだ次に切り替わる前の prev です。従ってこれらの値は prev のカーネルスタックに積まれることになります。(この辺の理解がやや曖昧。カーネルモードスタックはプロセス毎にあって、カーネルの内部で push などしてスタックにデータ積む = 現在の実行コンテキストにリンクしているカーネルモードスタック積む...ということで良い? 具体的には

union thread_union {
    struct thread_info thread_info;
    unsigned long stack[THREAD_SIZE/sizeof(long)];
};

の stack がそれに相当する。この理解で合ってるという前提で話を進めます。超勘違いしてたらごめんなさい。)

        movl    %esp, prev->thread.esp   /* save ESP */
        movl    next->thread.esp, %esp   /* restore ESP */
  • 現在のスタックポインタ esp を prev 内に保存
  • next に保存されていたスタックポインタ esp を現在のスタックポインタとして設定

これにより使用するスタックが prev のものから next のものに切り替わります。(Linux 2.6 の構造では esp のアドレスから計算して task_struct インスタンスのアドレスを知ることができます。実際カレントプロセスを求める current マクロはその方法で esp からカレントプロセスへの参照を取得します。故に esp を切り替えたということはすなわちカレントプロセスを切り替えたことに相当します。)

        movl    $1f, prev->thread.eip    /* save EIP */
        pushl   next->thread.eip         /* restore EIP */
        jmp     __switch_to

スタックポインタに続けてプログラムカウンタ eip の退避、復帰が行われるのですがここがちょっとトリッキーです。

まず、prev->thread.eip に movl している $1f とは何か。これは続けて定義されている

1:
        popl    %ebp
        popfl

の "1:" というラベルで指定した箇所のアドレスです。prev つまり切り替えられる側のプログラムカウンタをここ (ラベル1 のアドレス) に設定したということは、次回 prev の処理が再開されたときはラベル1 のアドレスから処理を再開せよ、という指定に等しい。

次にあらかじめ保存されていた next->thread.eip を新しく切り替えた next のカーネルスタック上に push。先に見たように switch_to() を通ったプロセスディスクリプタの thread.eip メンバにはラベル1のアドレスが設定されるのですから、next->thread.eip も(多くの場合) ラベル1 のアドレスを指しています。つまり、ここで新たに %eip にセットされた値もラベル1 のアドレスということになります。*1 そして C の __switch_to() にジャンプ。

なぜこのように next->thread.eip のアドレスをスタックに積んでから __switch_to() にジャンプするのか。__switch_to() は process.c に定義された C の関数で、最後は C の return 文で終わっています。C の return 文はアセンブリ命令では ret となります。ret はその仕様で、スタック上から戻りアドレスを eip に読み込むという仕様になっています。

つまり、

  • 先に next->thread.eip をスタックに push してから jmp __switch_to すると
  • __switch_to() が処理終えて ret で返ろうとしたときに
  • CPU が次のプログラムのアドレスとしてスタックから取り出す値が next->thread.eip になる
  • それがプログラムカウンタ (eip レジスタ) に設定される

わけです。C の呼出規約をうまく利用して、関数を呼出して返って来たあとの処理の再開箇所を任意の場所に指定するテクニックです。

__switch_to() 関数への引数わたし (fastcall 呼出規約)

switch_to マクロからジャンプする __switch_to() 関数はプログラムカウンタとスタックポインタ以外のレジスタ切り替えを行う関数。浮動小数点演算レジスタやデバッグ関連レジスタ、I/O ポートへのアクセス権の設定ほかを行います。__switch_to() は prev と next の二つの引数を受け取ります。

ここまで見てきたように switch_to マクロから __switch_to() を呼び出すにあたっては

        jmp     __switch_to

と jmp 命令を使っています。ここで気づくのが、__switch_to() の引数として prev、next を渡す必要があるのに、それら引数をスタックの上に積んでいる様子が見られないということです。cdecl 呼出規約では関数の引数は呼出元でスタックに push しておき、それから関数を call する決まりです。

むむ、と思って __switch_to() の宣言を見てみます。

struct task_struct fastcall * __switch_to(struct task_struct *prev_p, struct task_struct *next_p)

fastcall という指定があります。これは何でしょうか。fastcall は cdecl に同じく関数の呼出規約。引数をスタック経由ではなくレジスタ経由で渡す規約です。なるほど __switch_to() への引数はスタックではなくレジスタを使って渡すのでした。

この fastcall が最終的にコンパイラにどのような形で渡るかは 404 Not Found に解説があります。fastcall は gcc の __attribute__((regparam(3)) 属性に展開されて、結果として引数が eax レジスタと edx レジスタ経由で渡ることになります。

__switch_to を展開した擬似アセンブリコードの中で

        /* 入力オペランドの処理 */
        movl    prev, %eax
        movl    next, %edx

という箇所が先頭にありました。これは __switch_to() へ引数として渡すための命令だったわけです。

ラベル 1 以降の処理

__switch_to() から処理が戻ってくると、ラベル 1 の箇所から処理が再開されます。すでにこの時点で実行コンテキストは切り替わっています。

1:
        popl    %ebp
        popfl

        /* 出力オペランドの処理 */
        movl    %eax, last
        movl    %esi, esi
        movl    %edi, edi

スタックに退避されていた ebp と eflags を復帰して、レジスタを変数に書き出してマクロは終わります。(last はわかるけど esi と edi は何のためにこうしてるのかがわからない) で、context_switch() は prev を return して呼出元の schedule() に戻ります。

このようにして context_switch() から戻ったときには実行コンテキストが prev から next へ切り替っているという仕組みになっています。

まとめ

だいぶ長くなってしまいましたが、Linux のコンテキストスイッチ処理の核となる switch_to () マクロのコードを読み、その解説をしました。

  • switch_to() マクロでは gcc のインラインアセンブリでアセンブリ命令が使われています。
  • x86 拡張インラインアセンブリ構文を使うとアセンブリ命令と C 言語との間でスマートにメモリの内容をやり取りすることができます。
  • switch_to() マクロを展開して一つずつ追っていくと、プログラムカウンタやスタックポインタが退避/復帰される様子や処理の再開のためのテクニックなどを見ることができます。
  • switch_to() マクロから __switch_to() 関数を呼び出すにあたって fastcall 呼出規約が使われており、gcc の regparam 属性を使うことでその実現が可能だということも分かりました。

独り言

fastcall のところとか色々解説しようとすると、実はよく分かってないことがあってそれを調べるうちに知識を補強することができました。自分がちゃんと物事を理解したかどうかは人に説明ができるかどうか、というのがよくわかります。

今回調べてまだはっきりと理解できてない箇所、要調査。

  • gas の .type ディレクティブによる @function 指定が何に影響するか
  • カーネルスタック (switch_to() 内で pushl %ebp とかして値が積まれるスタック)とはそのときの実行コンテキストに紐づくカーネルプロセススタックという理解でよいか。
  • switch_to() の終わりで自動変数 esi, edi にレジスタの内容を書き出しているのは何のため?
  • switch_to() が prev, next, last と3つ引数を取る。書籍を見ると last が指定されている理由の解説はあるのだけどちゃんと理解できてない。

参考文献 (文中で紹介した URL 以外)

*1:fork(2) で生まれた子プロセスが処理を開始する場合やカーネルスレッド生成時は例外

herumiherumi 2007/09/26 22:11 >esi, edi にレジスタの内容を書き出しているのは何のため?
外してるかもしれませんが,これらのレジスタの退避/復元を必ずさせたいために,明示しているとか(書かないと退避されないことがある).
kernel 2.4系のswitch_toのasm内ではpush/pop edi/esiしてます.何故書き方を変えたのかは分かりません.

naoyanaoya 2007/09/27 14:13 なるほどありがとうございます。

でも復元した値を自動変数に積んでその後何もせずに return してしまってるのは何でだろう...

独り言: そもそも esi, edi をなぜ保存するのかというところまで疑問に思って調べてたんですがその辺は gcc の規約で保存しとけ! ということみたいですね。

ref: http://yashiromann.sakura.ne.jp/memo/x86_proccall.html

herumiherumi 2007/09/27 15:12 >でも復元した値を自動変数に積んでその後何もせずに return してしまってるのは何でだろう...

復元された値を積むのではなく復元そのものが目的なのでいいのではないでしょうか.たとえば,switch_toを含む簡単な関数を書いて,
,”=S” (esi),”=D” (edi)
のありなしを比べると,asm()の部分は変わりませんが,それを含む関数にesi, ediの退避/復元コードが削除されてしまいませんか?

esi/ediの退避はgccだけでなくx86のほぼすべてのCコンパイラでの規約ですね.

kosakikosaki 2007/09/28 00:03 >switch_to() が prev, next, last と3つ引数を取る。書籍を見ると last が指定されている理由の解説はあるのだけどちゃんと理解できてない

prev変数はコンテキストスイッチ前のスタックにある変数、よってスイッチ後は違う値になっている。
よって、字面上はばかばかしくてもスイッチ後の新しいコンテキストにprev変数を受け渡す処理が必要。
・・・と勝手に理解してるよ。おいらは

とみながたけひろとみながたけひろ 2007/09/30 19:15 >当然ですが、マクロにした場合引数の x, y にはメモリは割り当てられていないのでそれを直接拡張構文の入出力オペランドに指定することはできません。

このへんはレジスタ制約(”r”みたいなやつ)でちゃんと「レジスタにしろー」と書けば大丈夫です。

ただ、この例の場合だと、gccの拡張である「{}ブロックの最後に式を書くと式の値がその式になる」部分がうまく働かないため、_xの方は変数に一旦代入する必要があります。

後、全然本質ではないですが、変数が入力と出力の両方に出てくるときは”=r”と”0”を使うよりは”+r”のような+による修飾を使う、引数には名前をつけて%0とかではなく名前でアクセスする、というのが好みです。こうしないと、長いアセンブラコードを書いてると正直読めなくなってきます…(え、そんなの書くなって?)

naoyanaoya 2007/10/08 01:37 おお、みなさんどもども。しばらく留守にしておりました。

herumi さん:

うむむ、復元しているのはわかるのですがその復元した値を使ってない、(context_switch() の自動変数に復元するのですぐに解放されてしまう。) 使ってないのにわざわざ復元するのは何でだろう、という点がやっぱりまだよくわからんです。書かないと退避/復元されないことがある、とのことですがそういうことなのかな

kosaki さん:

あ、そういうことか! 理解した! thanks!

とみながたけひろさん:

{} ブロックの最後に式を書きたいがために _x だったんですね。理解しました。どうもです。