x86 Linux のメモリモデル、プロセス空間切り替え、カーネルスタック

ひとつ前のエントリ id:naoya:20070924:1190653790 では Linux のコンテキストスイッチにおける、主にハードウェアコンテキストの退避/復帰の処理を追ってみました。その中で

カーネルスタック (switch_to() 内で pushl %ebp とかして値が積まれるスタック)とはそのときの実行コンテキストに紐づくカーネルプロセススタックという理解でよいか。

という疑問がもやもや湧いて出てきました。ここ数日 はじめて読む486―32ビットコンピュータをやさしく語る を読んでいたのですが、その中にこの疑問への答えへの入り口が載っていまして、そこを糸口に調べてみました。で、結果としては

• 答え: 良い

でした。

x86 は特権レベルの移行と連動してスタックポインタを切り替える仕組みを持っています。Linux の場合モードはカーネルモード(特権レベル0) とユーザーモード(特権レベル3) の二つのモードを行き来します。このモードが切り替わるときに、スタックポインタが切り替わる = 利用するスタック領域が切り替わります。それをハードウェアが自動的に行ってくれているのでした。

この x86 のスタック切り替えの機能に伴い、具体的にそれぞれのモードで使うスタック領域のアドレスをハードに知らせる必要があります。そのためには TSS (タスク状態セグメント) を使うことになります。

ところで TSS はタスク状態セグメントの名前からも分かるとおり、タスクの状態を退避しておくためのセグメントです。しかし前回見たとおり Linux はハードウェアコンテキストの退避には TSS を使用せず、自前で task_struct の thread メンバにそれを格納していました。とまあこの辺から更に追っていった結果、結局 Linux のメモリモデルの概要を把握することができたので、それを以下にまとめます。

なお、486 本に加えて

• 詳解 Linuxカーネル 第3版
• Linuxカーネル2.6解読室
• Linuxのブートプロセスをみる (UNIXMAGAZINE COLLECTION)

の 3 冊を読んで調べた内容になっています。ところどころ上記書籍からの引用となります。また、主に i386 (not x86_64) を前提に書きます。周辺情報から自分の推測で書いたところには先頭に (*) を付けておきます。

Linux のメモリモデル

x86 Linux はセグメント機構はほとんど使わず、論理アドレスとリニアアドレスが一致する「基本フラットモデル」を採用しています。

• Linux では x86 のセグメント機構はごく一部しか使っていない。
  • すべてのセグメントディスクリプタはベースアドレスが 0、リミット値が 0xfffffh (G ビット有効)
  • 論理アドレスとリニアアドレスが一致している → 常に論理アドレスのオフセットフィールドがリニアアドレスと一致する
  • これを「基本フラットモデル」と呼ぶ
  • モードとセグメントが異なる組として __USER_CS、__USER_DS、__KERNEL_CS、__KERNEL_DS の 4 つのセグメントのみが用意されている
  • (*) C 言語での関数呼び出しは基本的に同一セグメント間でのジャンプに変換される。セグメント間ジャンプはしない、ということ
• プロセス空間の分離やメモリの保護はページング機構を利用して実現される
  • 具体的には? → 後述

なぜフラットモデルか。

• メモリ管理を簡略化することができる (すべてのプロセスで同じ値のセグメントレジスタを使用して、同じリニアアドレス空間を共有することができる)
• 広範囲アーキテクチャへの移植性を考慮して (アーキテクチャによってはセグメント機構が限定されている)

Linux の GDT と LDT

• 各CPUごとにひとつの GDT を持つ
  • 基本的に各CPUの GDT の中のディスクリプタの構成は全部一緒。
  • 異なるのは以下のもの
    • TSS → Linux は TSS も限定的にしか使用しない。1CPU につき一つの TSS セグメントのディスクリプタのみを GDT に登録する
    • CPU が実行しているプロセスに依存している GDT → LDT、TLS のディスクリプタ
• Linux のユーザーモードアプリケーションのほとんどは LDT を利用しない
  • iBCS 実行コード用のコールゲート、Solaris/x86 実行コードのコールゲートに利用する

Pentium 以降のページング機構に関して重要な話のメモ

• Page Size Extension (PSE)
  • Pentium モデル以降の拡張ページング機構にはページフレームの大きさを 4KB の代わりに 4MB にする機能がある
    • cr4 の PSE フラグをセットすると有効になる
    • PDE の第 7 ビットによって、PDE の指す先がページテーブルなのか 4MB ページフレームなのかを識別できる。これによって 4KB or 4MB のページフレームを混在させることができる。
  • 4MB ページフレームの Pros: TLB のヒット率が上がりキャッシュミスが減る。/ Cons: メモリ領域の利用率が下がる
  • Linux カーネルは 4MB ページフレームに置かれる

• TLB キャッシュの貼り付け
  • Pentium Pro 以降の PTE には Global フラグというフィールドがあり、このフラグを利用するとそのページテーブルが TLB から追い出されるのを防ぐことができる。
  • 利用のためには cr4 の PGE フラグに 1 を立てること
  • (*) invlpg 命令のことかな?

• PAE (Physical Address Extension)
  • Pentium Pro 以降はアドレスバスが 36本 に増えている。 → 2^36 = 64GB のメモリをアドレス付けできる
  • 32 ビット CPU で 36 ビットアドレスバスを利用するには、32 ビットリニアアドレスを 36 ビット物理アドレスに変換する新しいページング機構が必要だった。これが PAE。
  • 従来のページング機構のページディレクトリ、ページテーブルに加えてページディレクトリポインタテーブル (PDPT) という階層を追加。
  • PAE では 64 ビットの物理メモリへのマッピングが可能になるが、リニアアドレスは相変わらず 32 ビットのまま。よって物理アドレスのみが拡張され、プロセスのリニアアドレス空間は拡張されない、つまり OS は 64GB のメモリを扱うが、プロセスあたりの最大メモリ空間は 4GB。
  • (*) いまどきは x86_64 を使うのでもう古い話題です。あくまで 32 ビット時代での。

Linux のページングモデル

• 32ビット PAE 無効/有効、64 ビットなどに関わらずすべて共通のページング機構を利用。汎用的なページングモデル。
• 4階層5分割でリニアアドレスを扱う
  • ページグローバルディレクトリ、ページアッパーディレクトリ、ページミドルディレクトリ、ページテーブル
  • PAE なし 32 ビットの場合アッパー、ミドルを実質アドレス変換から取り除き、ハードウェアのページング機構のそれとほぼ同一の対応を行う

Linux のプロセス空間切り替え (＝ ページグローバルディスクリプタの切り替え)

ここがセグメント機構を使わずにフラットメモリモデルでプロセス空間の切り替えを行っているらしいけどどうやっているのか、その回答になります。

• Linux はフラットメモリモデルで、プロセス空間の切り替えはプロセス毎にページディレクトリを切り替えることにより実現される。
  • このページディレクトリのことをページグローバルディレクトリと呼ぶ。(*) PAE とかがあるとページングモデルのトップ階層が必ずしもページディレクトリではなかったりするので、そのためにグローバルと敢えて呼んでいるのかな。
• 利用中のページディレクトリは cr3 の制御レジスタによってその先頭アドレスが指定されている
• cr3 を別のページディレクトリに切り替える = プロセス空間の切り替えに相当
• cr3 の制御レジスタを更新した場合、ハードウェアが TLB を自動的にフラッシュする (この処理が高コスト)
  • ただし、TLB 無効化を省略する場合がある
    • 同じページテーブルの組を使用している2つの通常プロセス間で、プロセス切り替えを行う場合 → スレッドの切り替え
      • つまり、マルチスレッドの実行コンテキスト切り替えの際は TLB がフラッシュされないのでプロセスによる複数実行コンテキストよりもコストが低く済む。
    • 通常プロセスとカーネルスレッド間でのプロセス切り替え
      • カーネルプロセスは固有のページテーブルを持たず、直前にその CPU 上で動作していた通常プロセスのページテーブルをそのまま使用する
• プロセス空間を管理するカーネル内部での制御表が mm_struct 構造体。task_struct 構造体からリンクされる。
  • mm_struct 構造体には pgd メンバがあり、これがそのプロセスのページグローバルディレクトリの場所を保持している
  • この pgd メンバの値を cr3 に読み込むことでプロセス空間の切り替えが行われる。

context_switch() から呼ばれる switch_mm が上記の処理をやっている箇所になります。

static inline void switch_mm(struct mm_struct *prev,
                 struct mm_struct *next,
                 struct task_struct *tsk)
{
    int cpu = smp_processor_id();

    if (likely(prev != next)) {
        /* stop flush ipis for the previous mm */
        cpu_clear(cpu, prev->cpu_vm_mask);
#ifdef CONFIG_SMP
        per_cpu(cpu_tlbstate, cpu).state = TLBSTATE_OK;
        per_cpu(cpu_tlbstate, cpu).active_mm = next;
#endif
        cpu_set(cpu, next->cpu_vm_mask);

        /* Re-load page tables */
        load_cr3(next->pgd);

        /*
         * load the LDT, if the LDT is different:
         */
        if (unlikely(prev->context.ldt != next->context.ldt))
            load_LDT_nolock(&next->context);
    }
#ifdef CONFIG_SMP
    else {
        per_cpu(cpu_tlbstate, cpu).state = TLBSTATE_OK;
        BUG_ON(per_cpu(cpu_tlbstate, cpu).active_mm != next);

        if (!cpu_test_and_set(cpu, next->cpu_vm_mask)) {
            /* We were in lazy tlb mode and leave_mm disabled
             * tlb flush IPI delivery. We must reload %cr3.
             */
            load_cr3(next->pgd);
            load_LDT_nolock(&next->context);
        }
    }
#endif
}

prev != next、つまり異なるメモリ空間だった場合は load_cr3(next->pgd) で cr3 の値を次のプロセスのページディレクトリ next->pgd に変更してプロセス空間切り替えを行っているのが分かります。おお。

カーネルスタックとは

ここがそもそもの疑問のカーネルスタックって何よ、とかいうあたり。また TSS を限定的に使ってるのは何で、の回答もここにあります。

• Linux カーネルは割り込みスタックを用意していないという実装上の特徴がある。
• Linux カーネルでは、割り込みが発生したときその時点で実行中のカレントプロセスのカーネルスタックを利用して動作する。
• 各プロセスには1つのメモリ領域が割り当てられ、このメモリ領域 8,192 バイトに thread_info 構造体とカーネルモードプロセススタックを割り付ける。

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

• x86 には特権レベル移行と連動してスタックポインタを自動的に切り替える仕組みがある。
  • 特権レベルの移行 ← 割り込み、例外発生、コールゲート呼びだし時などに。
• GDT に登録した TSS に、各特権レベル (0〜3) に対応する ss と esp の値を指定する箇所がある。x86 は特権モード切替時に、その時点で有効な TSS (Linux の場合は各 CPU に TSS は 1 つのみ、なのでそれ) の該当特権モードに対応した ss:esp を読み込んでスタックを切り替える。
  • Linux は特権モード 0 または 3 (Xen 使用時は 1 も使うらしい) 。ユーザーモードプロセス → カーネルモードへのモード移行時には ss0:esp0 がレジスタに読み込まれる。
  • この ss0、esp0 に先のカーネルプロセススタックのアドレスを指定することで、割り込み発生時にスタックがユーザープロセススタックからカーネルスタックへ切り替わる

Linux では TSS は tss_struct 構造体によって表現されます。include/asm-i386/processor.h に tss_struct の定義があります。

struct tss_struct {
    unsigned short  back_link,__blh;
    unsigned long   esp0;
    unsigned short  ss0,__ss0h;
    ...
} __attribute__((packed));

たしかに esp0 や ss0 メンバがありますね。ここに先のカーネルスタックのアドレスを入れておけば、特権モード切替時に自動でこのスタックに切り替わるという仕組みがあったのでした。

ところで、そもそも TSS はタスク切り替え時にハードウェアコンテキストを退避するためのセグメントですが、前のエントリで見たように Linux はコンテキストスイッチは自前で行っていて、TSS によるタスクゲートなどは利用しません。が、

• x86 のスタック切り替えの機能
• I/O パーミッションビットマップの参照

の 2 つの目的にのみ TSS が利用されます。前者がここで解説したスタック切り替えの話。要はほぼ自前でやってて TSS のコアは要らないんだけど、一部必要なハードウェアの機能を利用するためのインタフェースとして TSS を介するので、そのために用意している、ということなんでしょう。

Linux のシステムコール

確かに特権モード移行時にスタックが切り替わりますが、ここで一つ留意点。システムコール呼び出し(ソフトウェア割り込み発生 → 特権モード切り替えが伴う)の引数がどう渡されるか、というところ。

• 特権モードが切り替わる際にスタックがカーネルスタックに切り替わると、システムコール呼びだし時にもスタックが切り替わることになる
• 従ってユーザーモードのスタックにシステムコールの引数を積んでも、カーネルからは直接それを取り出すことができない。
• そのため、システムコールへの引数はレジスタ経由で渡される
  • eflags, cs, eip, ss, esp はハードウェアによって例外(割り込み) 発生時にカーネルスタック上に退避される
  • system_call() および sysenter_entry() 関数は SAVE_ALL マクロにより汎用レジスタおよび gs, es, ds, ebp 等をカーネルスタックに積む
  • システムコールへの引数は ebx、ecx、edx、esi、edi、ebp の 6 つのレジスタによって渡される、のでここからそれらの引数を取り出して処理する
• なお、Linux のシステムコールは int 0x80 のソフトウェア割り込みまたは sysenter 命令によって実現されており、コールゲートは使われていない
• またレジスタ経由で引数を渡すので、ゲートディスクリプタのコピーカウントも利用しない
• この方法でユーザーモードからの引数渡しを実現することで、システムコールハンドラをほかの例外ハンドラと同じような構造にできるという利点が得られる。

SAVE_ALL マクロは以下です。arch/i386/kernel/entry.S より。

#define SAVE_ALL \
        cld; \
        pushl %gs; \
        CFI_ADJUST_CFA_OFFSET 4;\
        /*CFI_REL_OFFSET gs, 0;*/\
        pushl %es; \
        CFI_ADJUST_CFA_OFFSET 4;\
        /*CFI_REL_OFFSET es, 0;*/\
        pushl %ds; \
        CFI_ADJUST_CFA_OFFSET 4;\
        /*CFI_REL_OFFSET ds, 0;*/\
        pushl %eax; \
        CFI_ADJUST_CFA_OFFSET 4;\
        CFI_REL_OFFSET eax, 0;\
        pushl %ebp; \
        CFI_ADJUST_CFA_OFFSET 4;\
        CFI_REL_OFFSET ebp, 0;\
        pushl %edi; \
        CFI_ADJUST_CFA_OFFSET 4;\
        CFI_REL_OFFSET edi, 0;\
        pushl %esi; \
        CFI_ADJUST_CFA_OFFSET 4;\
        CFI_REL_OFFSET esi, 0;\
        pushl %edx; \
        CFI_ADJUST_CFA_OFFSET 4;\
        CFI_REL_OFFSET edx, 0;\
        pushl %ecx; \
        CFI_ADJUST_CFA_OFFSET 4;\
        CFI_REL_OFFSET ecx, 0;\
        pushl %ebx; \
        CFI_ADJUST_CFA_OFFSET 4;\
        CFI_REL_OFFSET ebx, 0;\
        movl $(__USER_DS), %edx; \
        movl %edx, %ds; \
        movl %edx, %es; \
        movl $(__KERNEL_PDA), %edx; \
        movl %edx, %gs

まとめると、スタックが切り替わるのはいいけど場合によってはユーザモードからカーネルモードに値を渡さなきゃいけない、でもそれは通常の関数呼び出しのように単にスタックに積んで渡す、というのはできないからレジスタを経由させますよ、という話でした。

まとめ

• カーネルプロセススタックとは何ぞや、というところから追っていって Linux のメモリモデルや、ページング機構を利用したプロセス空間の切り替えなどを見てみました。
• Linux はフラットモデルで、プロセス空間の切り替えはページグローバルディレクトリの切り替え (cr3 制御レジスタの更新) によって実現されています。
• 特権モード移行時にスタックがカーネルスタックに切り替わります。x86 は TSS をインタフェースにこの切り替えを自動で行います。ハードウェアコンテキストでレジスタの値を退避していた先の正体はこの切り替わった後のスタックで、それは task_struct 構造体からリンクされた箇所、つまり実行コンテキストの中にありました。
• 前回のハードウェアコンテキストの退避/復帰と併せるとコンテキストスイッチ中の主要処理 (1) プロセス空間の切り替え (2) ハードウェアコンテキストの切り替えの両方を見たことになります。
• セグメント機構を使っていない、TSS ã‚„ LDT を限定的にしか使っていないなど、ハードウェアの機能を使わずに自前で実装している箇所が色々ありました。UNIX OS の設計の基本方針、移植性、ハードウェアの機構が作られた時代背景などが絡み合った結果かと思われます。
• 途中、なぜマルチスレッドがマルチプロセスよりもコンテキストスイッチの負荷が低いか、の理由が垣間見えたりもしました。

参考文献

• はじめて読む486―32ビットコンピュータをやさしく語る
• 詳解 Linuxカーネル 第3版
• Linuxカーネル2.6解読室
• Linuxのブートプロセスをみる (UNIXMAGAZINE COLLECTION)

はじめて読む486―32ビットコンピュータをやさしく語る は方々で聞いていたとおりとても良い書籍です。が、実は最初に読んだときはちょっと難しくて挫折しました。

• はじめて読む8086―16ビット・コンピュータをやさしく語る (アスキーブックス)
• はじめて読むMASM―ソフトウェア環境のからくりを学ぶ

と二冊を読んでから改めて 486 本を読んでみたら、最後まで挫折せずに読むことができました。また 486 本は小さな OS のコアを再現するようなコードも伴った具体的な本ではあるものの、ではそれが実用的な OS ではどうなっているのかまでをつかむのに、Linux カーネルの本を併せて読むというのはとてもよい方法ではないかと思いました。OS の教科書がここまで豊富、良い時代ですね。