レガシーガジェット研究所

気になったことのあれこれ。

Linux Kernel ~ コンテキストスイッチ x86編 ~

概要

「詳解Linux Kernel」を参考にVersion 2.6.11のコードリーディングをしていく。CPUのアーキテクチャは書籍に沿ってIntelx86とする。

ここではコンテキストスイッチを見ていく。

プロセスの切り替え(コンテキストスイッチ)

ハードウェアコンテキスト

各プロセスは自身のアドレス空間を持つがCPUのレジスタは共有する。よってカーネルはプロセスを再開する前にレジスタの値をプロセスが休止した瞬間の値に戻す必要がある。

プロセスの実行再開の前にレジスタに戻す必要のある一連のデータのことをハードウェアコンテキストと呼ぶ。プロセス実行コンテキストのサブセットになる。Linuxでは一部をプロセスディスクリプタ内に、残りをカーネルモードスタックに保持している。

プロセスの切り替えは、prev(休止するプロセス)のハードウェアコンテキストをnext(次に実行するプロセス)のハードウェアコンテキストに置き換える動作と定義することができる。

初期のLinuxではプロセスの切り替え時、x86のハードウェア機構(セグメント状態セグメントディスクリプタ(TSSD)に対してfar jmp命令を実行するとプロセスの切り替え(csipレジスタを変更)を行ってくれる)を使用していたが現在は以下の理由からソフトウェアでプロセスの切り替えを行っている。

プロセスの切り替えはカーネルモードにおいてのみ発生し、レジスタの値はプロセス切り替えが起こる前に全てカーネルモードスタックに保存される。退避の対象にはもちろんssespレジスタも含まれている。

タスク状態セグメント(Task State Segment: TSS)

x86アーキテクチャではTSSという特別なセグメントが存在し、ハードウェアコンテキストを保持する。Linuxではハードウェアコンテキスト時にTSSを用いていないが、システム内の各CPUにおいて以下の理由からTSSの初期化を行なっている。

  • x86 CPUがユーザモードからカーネルモードに切り替わる時に、カーネルスタックのアドレスをTSSから読みこむ。
  • ユーザモードのプロセスがin/out命令によるI/Oポートアクセスを行う時、TSSに格納されているI/Oパーミッションビットマップを参照し対象のプロセスに当該ポートの利用許可があるのかを確認する。実際には以下のような流れになる。

    1. eflagsレジスタIOPLフィールドを確認し、3だった場合にI/O命令を実行する。3以外の場合は以下の処理が続く。
    2. TR(Task Register: 16bitのレジスタでTSSのセレクタ値を保持する)レジスタにアクセスし現在のTSSを取得、適切なI/Oパーミッションビットマップを取得する。
    3. 命令で指定されたI/Oポートへのアクセスがあるか先ほど取得したビットマップを用いて確認し、対象ポートに対応するビットが0だった場合には命令を実行し、1だった場合には「一般保護例外」を発生させる。
// include/asm-i386/processor.h

#define IO_BITMAP_BITS  65536
#define IO_BITMAP_BYTES (IO_BITMAP_BITS/8)
#define IO_BITMAP_LONGS (IO_BITMAP_BYTES/sizeof(long))

struct tss_struct {
    unsigned short    back_link,__blh;
    unsigned long esp0;
    unsigned short    ss0,__ss0h;
    unsigned long esp1;
    unsigned short    ss1,__ss1h; /* ss1 is used to cache MSR_IA32_SYSENTER_CS */
    unsigned long esp2;
    unsigned short    ss2,__ss2h;
    unsigned long __cr3;
    unsigned long eip;
    unsigned long eflags;
    unsigned long eax,ecx,edx,ebx;
    unsigned long esp;
    unsigned long ebp;
    unsigned long esi;
    unsigned long edi;
    unsigned short    es, __esh;
    unsigned short    cs, __csh;
    unsigned short    ss, __ssh;
    unsigned short    ds, __dsh;
    unsigned short    fs, __fsh;
    unsigned short    gs, __gsh;
    unsigned short    ldt, __ldth;
    unsigned short    trace, io_bitmap_base;
    /*
    * The extra 1 is there because the CPU will access an
    * additional byte beyond the end of the IO permission
    * bitmap. The extra byte must be all 1 bits, and must
    * be within the limit.
    */
    unsigned long io_bitmap[IO_BITMAP_LONGS + 1];
    /*
    * Cache the current maximum and the last task that used the bitmap:
    */
    unsigned long io_bitmap_max;
    struct thread_struct *io_bitmap_owner;
    /*
    * pads the TSS to be cacheline-aligned (size is 0x100)
    */
    unsigned long __cacheline_filler[35];
    /*
    * .. and then another 0x100 bytes for emergency kernel stack
    */
    unsigned long stack[64];
} __attribute__((packed));

io_bitmap[IO_BITMAP_LONGS + 1];が先ほどのI/Oポートビットマップとなる。tss_structはTSSの構造となっている。システム内部の各CPUに対応するTSSはinit_tss配列に格納されており、プロセス切り替え時にはTSSのフィールドを更新し、CPUの制御回路が必要な情報を利用できるようにする。よってTSSにはカレントプロセスの特権状態が反映されている。

TSSには対応する8バイトのTSSD(Task State Segment Descriptor)が存在する。セグメントディスクリプタの一種でTSSのベースアドレスやリミットなどを保持する。gdtrレジスタからGDTを求め、TRレジスタに保持しているセレクタ値からTSSDを求める。TSSDが保持しているTSSのベースアドレスやリミットを用いてTSSにアクセスする。

Intelでは元々プロセス毎にTSSが存在し、カレントプロセスのTSSのみビジービット(タイプフィールド内に存在する)が立っていた。Linuxでは各CPUにTSSは1つしか存在しないため常に立っている。

thread メンバ

プロセス切り替え時にはハードウェアコンテキストを全て退避させる必要があるが、Intelの設計のようにプロセス毎にTSSを持っていないため、Linuxではプロセスディスクリプタ内にあるthread_struct型のthreadメンバにハードウェアコンテキストを退避させる。thread_structカーネルスタックに退避されるeaxebx以外のほとんど全てのCPUレジスタ用のメンバを保持する。

x86では以下のように定義されている。

// 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;
/* max allowed port in the bitmap, in bytes: */
    unsigned long io_bitmap_max;
};

プロセス切り替えの実行

プロセスの切り替えはschedule()関数においてのみ発生し、以下の処理からなる。

switch_toマクロ

switch_toマクロはカーネルモードスタックとハードウェアコンテキストの切り替え時に呼び出すマクロで、以下のように定義されている。

// include/asm-i386/system.h
#define switch_to(prev,next,last) do {                   \
   unsigned long esi,edi;                        \
   asm volatile("pushfl\n\t"                    \
            "pushl %%ebp\n\t"                 \
            "movl %%esp,%0\n\t"   /* save ESP */      \
            "movl %5,%%esp\n\t"   /* restore ESP */   \
            "movl $1f,%1\n\t"      /* save EIP */      \
            "pushl %6\n\t"     /* restore EIP */   \
            "jmp __switch_to\n"                \
            "1:\t"                     \
            "popl %%ebp\n\t"                  \
            "popfl"                     \
            :"=m" (prev->thread.esp),"=m" (prev->thread.eip),  \
             "=a" (last),"=S" (esi),"=D" (edi)            \
            :"m" (next->thread.esp),"m" (next->thread.eip),    \
             "2" (prev), "d" (next));                \
} while (0)

prevswitch_to実行前に実行中であるプロセスのディスクリプタで、コンテキストスイッチ後、停止状態となる。nextは切り替え前は停止しており、切り替え後、実行中となるプロセスのディスクリプタである。そしてlastは再度prevが実行される際に切り替え前に実行していたプロセスディスクリプタとなる。

これはどういう事かというと、switch_toマクロは切り替え前の段階ではprev上で動作しているが、切り替え後はnext上で実行される、そのためコンテキストスイッチswitch_toマクロ上で行われるということになり、単一のプロセスから見るとswitch_toマクロ上で処理が中断し、再度実行される時はその続きから処理が実行されるように見える。再度prevが実行される時switch_toマクロはprevで実行されるが、prevは現在実行中のプロセス、nextは先ほど切り替え実行したプロセスとなり、どのプロセスから処理が切り替えられたのかわからない状況になる。そのため、プロセス切り替え前にprevの値を %eaxに保存し、プロセス切り替え後、別のswitch_toマクロ上で%eaxの値をlastにリストアすることでどのプロセスから切り替わったのか把握できるという仕組みになっている。

以下の図を用意した。

context-switch

次に実際のコードを見ていく。

  1. %eaxprev及びlastを、%edxnextを設定。少々わかりづらいが"=a" (last),"2" (prev),prevlastに対して%eaxを割り当て、"d" (next)nextに対して%edxを割り当てている。プロセスを切り替えた後も%eaxは値が変わらないためlastを次に実行されるプロセスでも参照できることになる。
:"=m" (prev->thread.esp),"=m" (prev->thread.eip),    \
"=a" (last),"=S" (esi),"=D" (edi)          \
:"m" (next->thread.esp),"m" (next->thread.eip), \
"2" (prev), "d" (next));                \
  1. eflagsレジスタ及びベースポインタの保存。スタックに退避しているのがわかる。
asm volatile("pushfl\n\t"                 \
"pushl %%ebp\n\t"                  \
  1. スタックポインタの切り替え処理。現在実行しているプロセスのディスクリプタであるprev%espthread_struct型のメンバであるthreadメンバのespに保存し、そしてnextの同一メンバを%espにリストアしている。ここでスタックポインタは切り替わる。
"movl %%esp,%0\n\t" /* save ESP */      \
"movl %5,%%esp\n\t"    /* restore ESP */   \
:
:"=m" (prev->thread.esp), // %0
:
:"m" (next->thread.esp), // %5
  1. 実行のプロセス(prev)が再実行される際に読み込まれる%eipをスレッドのメンバに設定し、次に実行されるプロセスが保持する%eipをスタックへの保存する。$1f1:のアドレスで再度実行される時は当該箇所からの実行となる。そして__switch_toにジャンプする。(ここで一度prevの実行は停止し、nextが実行される)
"movl $1f,%1\n\t"        /* save EIP */      \
"pushl %6\n\t"      /* restore EIP */   \
"jmp __switch_to\n"             \
"1:\t"                      \
:
... ,"=m" (prev->thread.eip), \
:
... ,"m" (next->thread.eip),  \
  1. (ここからは再度実行が移ってきた時の処理となる)ベースポインタとフラグレジスタ(eflag)をリストアする。
"popl %%ebp\n\t"                    \
"popfl"                      \

__switch_to()関数

次に先ほど見たswitch_toマクロ内でコールされていた__switch_to()を見ていく。以下のように定義されている。

当該関数はswitch_to()マクロから始まるコンテキストスイッチのメインの処理となる。

// arch\i386\kernel\process.c
struct task_struct fastcall * __switch_to(struct task_struct *prev_p, struct task_struct *next_p)
{
    struct thread_struct *prev = &prev_p->thread,
                 *next = &next_p->thread;
    int cpu = smp_processor_id();
    struct tss_struct *tss = &per_cpu(init_tss, cpu);

    /* never put a printk in __switch_to... printk() calls wake_up*() indirectly */

    __unlazy_fpu(prev_p);

    /*
    * Reload esp0, LDT and the page table pointer:
    */
    load_esp0(tss, next);

    /*
    * Load the per-thread Thread-Local Storage descriptor.
    */
    load_TLS(next, cpu);

    /*
    * Save away %fs and %gs. No need to save %es and %ds, as
    * those are always kernel segments while inside the kernel.
    */
    asm volatile("movl %%fs,%0":"=m" (*(int *)&prev->fs));
    asm volatile("movl %%gs,%0":"=m" (*(int *)&prev->gs));

    /*
    * Restore %fs and %gs if needed.
    */
    if (unlikely(prev->fs | prev->gs | next->fs | next->gs)) {
        loadsegment(fs, next->fs);
        loadsegment(gs, next->gs);
    }

    /*
    * Now maybe reload the debug registers
    */
    if (unlikely(next->debugreg[7])) {
        loaddebug(next, 0);
        loaddebug(next, 1);
        loaddebug(next, 2);
        loaddebug(next, 3);
        /* no 4 and 5 */
        loaddebug(next, 6);
        loaddebug(next, 7);
    }

    if (unlikely(prev->io_bitmap_ptr || next->io_bitmap_ptr))
        handle_io_bitmap(next, tss);

    return prev_p;
}

上記の関数定義では関数名の前にfastcallという文字列が付加されていることがわかるが、fastcallは以下のようにマクロとして以下のように定義されている。

// include\asm-i386\linkage.h
#define fastcall   __attribute__((regparm(3)))

__attribute__GCC拡張機能を付加するもので今回使用されているregparm(n)は関数の引数をスタックからではなくレジスタ経由で受けとるという指定で、nはいくつの引数をとるかを指定する。今回は3を指定しているので%eax%edx及び%ecxとなる。

先程のswitch_toマクロ内ではprev%eaxnext%edxに割り当てられていたため、__switch_to()の引数はprev_p%eaxnext_p%edxになることがわかる。

ここから__switch_to()の処理を見ていく。まずは以下の処理。

// arch\i386\kernel\process.c
struct task_struct fastcall * __switch_to(struct task_struct *prev_p, struct task_struct *next_p)
{
    struct thread_struct *prev = &prev_p->thread,
                 *next = &next_p->thread;
    int cpu = smp_processor_id();
    struct tss_struct *tss = &per_cpu(init_tss, cpu);

上記ではまず変数にスレッドの情報を書き出し、現在実行しているプロセスのCPU及びそのCPUが保持しているTSSを取得している。

smp_processor_id()は以下のように定義されており、%espをスレッドのサイズでマスクしthread_info構造体のポインタを取得、そこから現在使用しているCPUを取得している。

// include/linux/smp.h
#define smp_processor_id() __smp_processor_id()

// include/asm-i386/smp.h
#define __smp_processor_id() (current_thread_info()->cpu)

// include/asm-i386/thread_info.h
static inline struct thread_info *current_thread_info(void)
{
    struct thread_info *ti;
    __asm__("andl %%esp,%0; ":"=r" (ti) : "0" (~(THREAD_SIZE - 1)));
    return ti;
}

// include/asm-i386/thread_info.h
#define THREAD_SIZE        (8192)

以下の__unlazy_fpu()prev_pの数値演算コアプロセッサレジスタの値を退避する関数で、レジスタの退避は選択的に行なっている。

// arch\i386\kernel\process.c
struct task_struct fastcall * __switch_to(struct task_struct *prev_p, struct task_struct *next_p)
{
:
    __unlazy_fpu(prev_p);

次にload_esp0()ではtssesp0メンバにnext->threadesp0メンバを登録する、これによってカーネルモードへ移行した際に当該espがスタックポインタ(レジスタ)に読み込まれるようになる。

// arch/i386/kernel/process.c
struct task_struct fastcall * __switch_to(struct task_struct *prev_p, struct task_struct *next_p)
{
:
    /*
     * Reload esp0, LDT and the page table pointer:
     */
    load_esp0(tss, next);

上記の関数は以下のように定義されており、スタックポインタをTSSに渡しているのが確認できる。

// include/asm-i386/processor.h
static inline void load_esp0(struct tss_struct *tss, struct thread_struct *thread)
{
    tss->esp0 = thread->esp0;
    /* This can only happen when SEP is enabled, no need to test "SEP"arately */
    if (unlikely(tss->ss1 != thread->sysenter_cs)) {
        tss->ss1 = thread->sysenter_cs;
        wrmsr(MSR_IA32_SYSENTER_CS, thread->sysenter_cs, 0);
    }
}

以下のload_TLS()はCPU毎に存在するローカルストレージを読み込んでいる。

// arch\i386\kernel\process.c
struct task_struct fastcall * __switch_to(struct task_struct *prev_p, struct task_struct *next_p)
{
:
    /*
     * Load the per-thread Thread-Local Storage descriptor.
     */
    load_TLS(next, cpu);

load_TLS()は以下のように定義されており一時的なマクロを使用しているので分かりづらいが、現在使用しているCPUのGDT内にあるTLSを切り替えている。

// include/asm-i386/desc.h
static inline void load_TLS(struct thread_struct *t, unsigned int cpu)
{
#define C(i) per_cpu(cpu_gdt_table, cpu)[GDT_ENTRY_TLS_MIN + i] = t->tls_array[i]
    C(0); C(1); C(2);
#undef C
}

// include/asm-i386/segment.h
#define GDT_ENTRY_TLS_MIN  6

以下ではfsgsセグメントレジスタを保存する処理となる。コメントにもある通りesdsセグメントレジスタカーネルモードの間、カーネルが使用するレジスタであるため切り替えは必要ない。

// arch\i386\kernel\process.c
struct task_struct fastcall * __switch_to(struct task_struct *prev_p, struct task_struct *next_p)
{
:
    /*
     * Save away %fs and %gs. No need to save %es and %ds, as
     * those are always kernel segments while inside the kernel.
     */
    asm volatile("movl %%fs,%0":"=m" (*(int *)&prev->fs));
    asm volatile("movl %%gs,%0":"=m" (*(int *)&prev->gs));

そして続く以下の処理では先ほど保存したセグメントレジスタ及びnextのセグメントレジスタいずれかが使用されている場合に、その切り替えを行う。

// arch\i386\kernel\process.c
struct task_struct fastcall * __switch_to(struct task_struct *prev_p, struct task_struct *next_p)
{
:
    /*
     * Restore %fs and %gs if needed.
     */
    if (unlikely(prev->fs | prev->gs | next->fs | next->gs)) {
        loadsegment(fs, next->fs);
        loadsegment(gs, next->gs);
    }

ここで使用されているunlikelyという関数はGCCのビルトイン関数が用いられているのマクロで、以下のように定義されている。

// include/linux/compiler.h
#define likely(x)  __builtin_expect(!!(x), 1)
#define unlikely(x)    __builtin_expect(!!(x), 0)

これはコンパイル結果に最適化を行うものでlikely()であれば結果が"真"の場合に対して、unlikely()であれば結果が"偽"の場合に対して最適化が行われる。!!(x)のような記述がなされているのは引数がポインタでNULLだった場合を考慮したものらしい。

loadsegment()は以下のように定義されており、

// arch/i386/kernel/process.c
#define loadsegment(seg,value)         \
   asm volatile("\n"            \
       "1:\t"              \
       "movl %0,%%" #seg "\n"      \
       "2:\n"              \
       ".section .fixup,\"ax\"\n"   \
       "3:\t"              \
       "pushl $0\n\t"          \
       "popl %%" #seg "\n\t"       \
       "jmp 2b\n"          \
       ".previous\n"           \
       ".section __ex_table,\"a\"\n\t"  \
       ".align 4\n\t"          \
       ".long 1b,3b\n"         \
       ".previous"          \
       : :"m" (*(unsigned int *)&(value)))

マクロの文字列化演算を使用しているので読みづらいが、valuesegで指定したレジスタに設定しているのがわかる。

次にデバッグレジスタの設定の処理を行なっている以下の個所。デバッグレジスタを使用している時のみ値を更新している。

// arch\i386\kernel\process.c
struct task_struct fastcall * __switch_to(struct task_struct *prev_p, struct task_struct *next_p)
{
:
    /*
    * Now maybe reload the debug registers
    */
    if (unlikely(next->debugreg[7])) {
        loaddebug(next, 0);
        loaddebug(next, 1);
        loaddebug(next, 2);
        loaddebug(next, 3);
        /* no 4 and 5 */
        loaddebug(next, 6);
        loaddebug(next, 7);
    }

loaddebug()は以下のように定義されており、第一引数をマクロの文字列化演算でレジスタ名を指定し、第二引数のregisterをオフセットにデバッグレジスタを指定している。

// i386/kernel/process.c
/*
 * This special macro can be used to load a debugging register
 */
#define loaddebug(thread,register) \
       __asm__("movl %0,%%db" #register  \
           : /* no output */ \
           :"r" (thread->debugreg[register]))

次にI/Oパーミッションビットマップの処理を見ていく。

// arch\i386\kernel\process.c
struct task_struct fastcall * __switch_to(struct task_struct *prev_p, struct task_struct *next_p)
{
:
if (unlikely(prev->io_bitmap_ptr || next->io_bitmap_ptr))
        handle_io_bitmap(next, tss);

これはprevまたはnextが独自のI/Oパーミッションビットマップを保持していた場合にhandle_io_bitmap(next, tss)を呼び出すという処理になっている。プロセスは基本的に独自のI/Oパーミッションビットマップは保持しないためunlikelyとなっている。prev若しくはnextがI/Oポートにアクセスした時のみローカルCPUのTSSに実際のビットマップが、io_bitmap_ptrポインタが指す場所にコピーされる。

handle_io_bitmap()の定義を以下に示す。

// arch/i386/kernel/process.c
static inline void
handle_io_bitmap(struct thread_struct *next, struct tss_struct *tss)
{
    if (!next->io_bitmap_ptr) {
        /*
        * Disable the bitmap via an invalid offset. We still cache
        * the previous bitmap owner and the IO bitmap contents:
        */
        tss->io_bitmap_base = INVALID_IO_BITMAP_OFFSET;
        return;
    }
    if (likely(next == tss->io_bitmap_owner)) {
        /*
        * Previous owner of the bitmap (hence the bitmap content)
        * matches the next task, we dont have to do anything but
        * to set a valid offset in the TSS:
        */
        tss->io_bitmap_base = IO_BITMAP_OFFSET;
        return;
    }
    /*
    * Lazy TSS's I/O bitmap copy. We set an invalid offset here
    * and we let the task to get a GPF in case an I/O instruction
    * is performed.  The handler of the GPF will verify that the
    * faulting task has a valid I/O bitmap and, it true, does the
    * real copy and restart the instruction.  This will save us
    * redundant copies when the currently switched task does not
    * perform any I/O during its timeslice.
    */
    tss->io_bitmap_base = INVALID_IO_BITMAP_OFFSET_LAZY;
}

// include/asm-i386/processor.h
#define IO_BITMAP_OFFSET offsetof(struct tss_struct,io_bitmap)
#define INVALID_IO_BITMAP_OFFSET 0x8000
#define INVALID_IO_BITMAP_OFFSET_LAZY 0x9000

次に実行対象となっているタスクであるnextがI/Oパーミッションビットマップを保持していない場合はio_bitmap_baseINVALID_IO_BITMAP_OFFSET(構造体のオフセットとして無効な値)を設定する。nextがすでにセットされているI/Oパーミッションマップのオーナーだった場合は有効なオフセットを設定する。条件分岐に引っかからない場合はレイジーコピーを行うような設定となる。これはhandle_io_bitmap()内ではビットマップのコピーは行わず、実際にI/Oパーミッションマップへのアクセスが発生した時にio_bitmap_baseINVALID_IO_BITMAP_OFFSET_LAZYだった場合、実際のコピーを行う。

最後に以下の処理。

// arch\i386\kernel\process.c
struct task_struct fastcall * __switch_to(struct task_struct *prev_p, struct task_struct *next_p)
{
:
return prev_p;

上記の処理でprevへのポインタを%eaxに設定する。これにより__switch_to()前後での%eaxの値が担保できる。

switch_toマクロ内では__switch_to()jmpしているため、上記のreturnでスタックから%eipとして取り出される値は__switch_to()jmpする直前にスタックにプッシュされたswitch_toマクロ内の:1のアドレスとなり、しっかりと再実行時に意図した場所に戻ってくることがわかる。

参考