新Linuxカーネル解読室 - プロセスディスパッチャ(前編)

「Linuxカーネル2.6解読室」（以降、旧版）出版後、Linuxには多くの機能が追加され、エンタープライズ領域をはじめとする様々な場所で使われるようになりました。 それに伴いコードが肥大かつ複雑化し、多くのエンジニアにとって解読不能なブラックボックスとなっています。 世界中のトップエンジニア達の傑作であるLinuxカーネルにメスを入れ、ブラックボックスをこじ開けて、時に好奇心の赴くままにカーネルの世界を解読する「新Linuxカーネル解読室」プロジェクト。

本稿では、旧版1章で解説されていた「プロセススケジューリング」の内、プロセスディスパッチャ(タスクの切り替え処理)について、カーネルv6.8/x86_64のコードをベースに解説します。

執筆者 : 西村　大助

※ 「新Linuxカーネル解読室」連載記事一覧はこちら

---

1. 前提知識

本章ではプロセスディスパッチャを解説するにあたり必要となる前提知識として、(スタックに関する)プロセッサの挙動やtask_struct構造体(含む、関連するデータ構造)、についてまとめます。

1.1 スタック

本節では、x86_64アーキテクチャにおける、スタックについて解説します。
詳細は後述しますが、イメージとしては下図のようになります*1。

1.1.1 概要

プロセッサはスタックと呼ばれる連続したメモリ領域を作業領域として処理を行います。スタックの具体的な用途はアーキテクチャはもちろん処理系にも依存しますが、実行中の関数のローカル変数や、関数呼び出し時の引数、関数 を呼び出した時のInstruction Pointer(RIPレジスタ)を保存しておく(呼び出し元に戻る時に参照する)など様々です。
スタックは上位アドレスから下位アドレスに向けて拡張していきます。また、スタックフレームと呼ばれる領域に分割されており、Base Pointer(RBPレジスタ)から、スタックの先頭を表すStack Pointer(RSPレジスタ)の間が、実行時点のスタックフレーム(実行中の関数が使用するスタックフレーム)となっています。

1.1.2 PUSH/POP命令

スタックへのデータの保存、及びデータの取り出しには、それぞれPUSH/POP命令を使用します*2。
PUSH命令を実行すると、オペランド(レジスタ等)のデータをスタックの先頭に積んで、Stack Pointer(RSPレジスタ)をその分だけ進めます(減算します)。
POP命令を実行すると、スタックの先頭のデータをオペランド(レジスタ等)に取り出して、Stack Pointer(RSPレジスタ)をその分だけ戻します(加算します)。

1.1.3 CALL/RET命令

関数の呼び出しにはCALL命令が使用されますが、CALL命令を実行するとその時のInstruction Pointer(RIPレジスタ)がスタックに保存(PUSH)されて、呼び出された関数に制御が移ります(Instruction Pointer(RIPレジスタ)が当該関数の先頭アドレスになります)。
呼び出された関数は、通常、最初にBase Pointer(RBPレジスタ)を保存(PUSH)した上で、Base Pointer(RBPレジスタ)をStack Pointer(RSPレジスタ)の値で更新するので、Base Pointer(RBPレジスタ)の指しているスタックフレームの最上位アドレスには呼び出し元関数のBase Pointer(RBPレジスタ)が、その1つ前には呼び出し元のInstruction Pointer(RIPレジスタ)が保存されている状態となっています。
そして関数の処理が終わる際にはRET命令が使用されますが、RET命令はその時のスタックからデータをPOPしてInstruction Pointer(RIPレジスタ)に設定します。なので、スタックフレームからBase Pointer(RBPレジスタ)を復元(POP)しててから(この時点でスタックの先頭はCALL実行時のInstruction Pointer(RIPレジスタ))RET命令を実行する事で、呼び出し元関数に制御が戻り、関数を呼び出した後の処理が継続される事になります。

1.2 task_struct構造体

Linuxでは、タスク*3毎にtask_struct構造体があり、タスク管理に必要な情報を保持しています。
task_struct構造体は非常に多くのメンバを持っていますが、本節では、プロセスディスパッチャの実装に関連した部分に絞って解説します。

1.2.1 カーネルスタック

タスクがシステムコールや割り込み等のためにカーネルモードで動作する時に使用するスタックをカーネルスタックと呼びます。
カーネルスタックは、task_struct構造体のstackが指すアドレスからTHREAD_SIZE(configにも依りますがx86_64では4ないし8ページ)分の領域が割り当てられています(参考:alloc_thread_stack_node())。カーネルスタックの最上位アドレスには、ユーザモードからカーネルモードに移行する際に、その時の各種レジスタの値を退避しています(pt_regs構造体として参照されます)。

1.2.2 thread_struct構造体

上記の図にもありますが、task_struct構造体は、メンバとしてthread_struct構造体を保持しています*4。
thread_struct構造体の定義はアーキテクチャ毎に分かれていますがが、タス クを切り替える際に、タスクの実行状態(各レジスタ値等)を保存・復旧するのに使用されます。例えば、x86_64 の場合、spにはその名の通りスタックポインタ(RSPレジスタ)の値の保存・復旧に使用されます(詳細は後述します)。

2. 全体の流れ

タスクの切り替えの中心は、__schedule()の中のcontext_switch()により行われます。context_switch()を抜粋すると以下のようになっており、
(kernel/sched/core.c)

   5340 /*
   5341  * context_switch - switch to the new MM and the new thread's register state.
   5342  */
   5343 static __always_inline struct rq *
   5344 context_switch(struct rq *rq, struct task_struct *prev,
   5345                struct task_struct *next, struct rq_flags *rf)
   5346 {
   5347         prepare_task_switch(rq, prev, next);
   5348
   ...
   5366         if (!next->mm) {                                // to kernel
   5367                 enter_lazy_tlb(prev->active_mm, next);
   5368
   5369                 next->active_mm = prev->active_mm;
   5370                 if (prev->mm)                           // from user
   5371                         mmgrab_lazy_tlb(prev->active_mm);
   5372                 else
   5373                         prev->active_mm = NULL;
   5374         } else {                                        // to user
   5375                 membarrier_switch_mm(rq, prev->active_mm, next->mm);
   ...
   5384                 switch_mm_irqs_off(prev->active_mm, next->mm, next);
   5385                 lru_gen_use_mm(next->mm);
   5386
   5387                 if (!prev->mm) {                        // from kernel
   5388                         /* will mmdrop_lazy_tlb() in finish_task_switch(). */
   5389                         rq->prev_mm = prev->active_mm;
   5390                         prev->active_mm = NULL;
   5391                 }
   5392         }
   ...
   5399         /* Here we just switch the register state and the stack. */
   5400         switch_to(prev, next, prev);
   5401         barrier();
   5402
   5403         return finish_task_switch(prev);
   5404 }

大まかな流れとしては、

• 前処理(L5347)
• メモリ空間の切り替え(L5366-L5392)
• レジスタの切り替え(L5400)
• 後処理(L5403)

のようになっています。
以降の章で、レジスタの切り替えと前後処理についてまとめたいと思います。尚、説明すべき事が多くなるので、本稿ではタスクのメモリ空間については触れません。

3. レジスタの切り替え

3.1 通常のタスク切り替え

前述の通り、レジスタの切り替えはswitch_to()により行われますが、以下のように定義されており、
(arch/x86/include/asm/switch_to.h)

     49 #define switch_to(prev, next, last)                                     \
     50 do {                                                                    \
     51         ((last) = __switch_to_asm((prev), (next)));                     \
     52 } while (0)

その実体は、__switch_to_asm()というアセンブラで記述されています。

(arch/x86/entry/entry_64.S)

    171 /*
    172  * %rdi: prev task
    173  * %rsi: next task
    174  */
    175 .pushsection .text, "ax"
    176 SYM_FUNC_START(__switch_to_asm)
    177         /*
    178          * Save callee-saved registers
    179          * This must match the order in inactive_task_frame
    180          */
    181         pushq   %rbp
    182         pushq   %rbx
    183         pushq   %r12
    184         pushq   %r13
    185         pushq   %r14
    186         pushq   %r15
    187
    188         /* switch stack */
    189         movq    %rsp, TASK_threadsp(%rdi)
    190         movq    TASK_threadsp(%rsi), %rsp
    ...
    206         /* restore callee-saved registers */
    207         popq    %r15
    208         popq    %r14
    209         popq    %r13
    210         popq    %r12
    211         popq    %rbx
    212         popq    %rbp
    213
    214         jmp     __switch_to
    215 SYM_FUNC_END(__switch_to_asm)

__switch_to_asm()は上記の通り、

• 切り替え前タスク(prev)のレジスタをカーネルスタックにPUSH(L181-L186)。
• その時点のスタックポインタ(RSPレジスタ)を、切り替え前タスク(prev)のthread_struct.spに保存し(L189)、
  
• 切り替え後タスク(next)のthread_struct.spをスタックポインタ(RSPレジスタ)に復旧(L190。この時点で、スタックは切り替え後タスク(next)のカーネルスタックになる)。
  
• カーネルスタックに保存していた各種レジスタをPOPして(L207-L212)、
  
• __switch_to()にジャンプする(L214)。

という流れになっています。
一言で言うと、「最低限のレジスタの退避・復旧とカーネルスタックの切り替えを行い、__switch_to()にジャンプする」という事になりますが、3点補足しておきます。

1点目ですが、なぜ退避・復旧を行うのがRBP、RBX、R12-R15であるかという点です。
まずこれら以外のレジスタ(FPUç­‰)の退避・復旧は、__switch_to()により行われるため、__switch_to_asm()では行う必要がありません。逆に、これらのレジスタはここで退避・復旧するようにしないと、__switch_to()により更新されてしまう可能性があり、正しく状態を復元できなくなります。
次に2点目ですが、CALL命令ではなくJMP(ジャンプ)命令で__switch_to()が実行される事です。先程、CALL命令では、実行した時のInstruction Pointer(RIPレジスタ)ã‚’CALL命令自身がスタックの先頭に積んで、呼び出した関数に制御が移り、呼び出された関数が実行するRET命令によりそのスタックの先頭に積まれているアドレスがInstruction Pointer(RIPレジスタ)に復旧され制御が呼び出し元に戻る、という話をしましたが、ここでは既にCALL時のInstruction Pointer(RIPレジスタ)がスタックに積まれた状態でジャンプするので、__switch_to()がreturn(RET命令)すると、context_switch()に制御が戻る事になります。
最後に3点目ですが、(当然と言えば当然なのですが)切り替え後タスク(next)自身、先にCPUを別タスクに明け渡す際に、同じコードを実行している(なので、カーネルスタックにRBP、RBX、R12-R15の値や、thread_struct.spにスタックポインタが保存されていて復旧できる)という事です。ただし、その時(前述の「先にCPUを別タスクに明け渡す際」)のprevは(今の)next自身なので(スタックにはこちらの情報が残っている)、このままでは今CPUを明け渡そうとしているprevが何なのかわからなくなってしまいます(それだと後述する「後処理」がうまくいかない)。 そうならないようにするため、__switch_to()では最後にprevを返し、それが、(少し話が遡りますが)switch_to()のlastとして呼び出し元のcontext_switch()に渡される事で、正しく後処理が行われる事になります(これが、switch_to()にlast引数が3つある理由です)。

3.2 生成されたばかりのタスクへの切り替え

先程、「先にCPUを別タスクに明け渡す際に、同じコードを実行している(なので、カーネルスタックにRBP、RBX、R12-R15の値や、thread_struct.spにスタックポインタが保存されていて復旧できる)」と書きましたが、1つだけ例外があります。それは、fork(2)等によって生成されたばかりのタスクです(生成されたばかりなので、当然自分で保存などはしていない)。
このケースについては後編で詳細に解説する予定です。

3.3 FPUの切り替え

FPUの退避・復旧を行う、__switch_to()の処理についても、詳細は後編にて解説する予定です。

4. 前後処理

本章では、context_switch()から呼ばれる、prepare_task_switch()、及びfinish_task_switch() で行われる、前後処理について簡単に説明します。
前後処理で行われるのは、一言で言えば「タスクに結びつく情報を管理している、カーネル内の様々なサブシステムについて、その切り替えを行う」事にあります。ここでは、いくつかのサブシステムについて例を挙げながら解説し ます。

4.1 schedstat

Linuxでは/proc/<PID>/schedstatから当該タスクの実行時間等の統計情報を確認する事ができます。
実行時間を集計するため、タスクの切り替えが行われる際には、切り替え前のタスクの集計を止めて切り替え後のタスクの集計を開始する必要がありますが、それを行っているのがprepare_task_switch()から呼ばれるsched_info_switch()です。

4.2 perf

パフォーマンス分析に使われるperfもタスク毎の性能情報を管理するため、前後処理で切り替え処理が行われます*5。
具体的には、prepare_task_switch()から呼ばれるperf_event_task_sched_out()とfinish_task_switch()から呼ばれるperf_event_task_sched_in()により切り替え処理が行われます。

4.3 notifier

前2節では、既にソースレベルで組み込まれている、特定のサブシステムにおける切り替え処理について見てみましたが、タスク切り替え時に実行される処理を動的に追加する機能も準備されています。
具体的には、preempt_notifier_register()という関数でnotifierを登録すれば、prepare_task_switch()から呼ばれるfire_sched_out_preempt_notifiers()、及びfinish_task_switch()から呼ばれるfire_sched_in_preempt_notifiers()を経由して、登録したnotifierのコールバック関数が実行されます。

5. 最後に

本稿では、駆け足ではありますが、プロセスディスパッチャ(タスクの切り替え処理)の基本的な部分についてまとめてみました。
後編では、本稿では書ききれなかった、生成されたばかりのタスクへの切り替えやFPUの切り替えの話について説明する予定です。

参考資料

• Intel SDM(SoftwareDevelopperManual)

*1:本項ではメモリを図示する際、下位アドレスを上に(上位アドレスを下に)図示します。

*2:MOV命令でもデータ保存・取り出しはできますが、その場合Stack Pointer(RSPレジスタ)は増減されません。

*3:本稿ではプロセスやスレッドといった、OSにおける実行単位の事を「タスク」と呼称します。

*4:実装の都合上、必ず最後のメンバとなっています。

*5:perfの仕組みや実装については、未定ですが、別途、記事化できればと思います