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

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

Linux Kernel ~ セグメンテーション x86編 ~

概要

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

今回はアドレス変換機構であるセグメンテーションについて見ていく。

前提知識

メモリのアドレス変換を見ていくあたって必要となるハードウェア機構を以下にまとめた。

メモリアドレス

x86の環境では以下の3種類のアドレスを扱う。

  • 論理アドレス: 16bitのセグメントセレクタと32bitのオフセットから成るアドレス。メモリをセグメントという単位に分割し使用する際に用いられる。当該アドレスはMMUを返してリニアアドレスに変換される。
  • リニアアドレス: 一般的に仮想アドレスと言われるのはリニアアドレスのこと。最大で4GBまで使用でき、32bit符号無しで表現される。範囲としては0x00000000 ~ 0xFFFFFFFFとなる。
  • 物理アドレス: アドレスバスを通じて実際のメモリセルを指定するのに使用される。32bitまたは36bitの符号無しで表現される。

MMU

MMUをセグメンテーション回路とページング回路を用いることで以下のようなアドレス変換が可能となる。

-- 論理アドレス --> [セグメンテーション回路] -- リニアアドレス --> [ページング回路] -- 物理アドレス -->

メモリ調停回路(Memory Arbita)

マルチコアプロセッサ(SMP)環境では複数のCPUがメモリにアクセスするので逐次に処理を行う必要があり、そのためバスとメモリの間には調整回路が配置されている。メモリ調停回路の役割はCPUに順次メモリの使用権を与えることである。シングルプロセッサ環境でもDMAコントローラが存在するためメモリ調停回路は必要にある。

CPUのモード

Intel 80286以降のCPUには以下の2種類のモードが存在する。ここでは簡単に説明する。

  • リアルモード: リニアアドレスが物理アドレスとして処理される。単一のセグメントが64KBという制限が存在する。現在でも互換性のために当該モードは存在し、起動時などに使用される。
  • プロテクトモード: 基本的な動作モード。セグメント情報保持するセグメントディスクリプタで管理する。セグメントディスクリプタはセグメントのアドレスやサイズ、保護情報などを保持する。セグメントディスクリプタはグローバルディスクリプタテーブル(GDT)やローカルディスクリプタテーブル(LDT)で管理される。当該モードではセグメントのサイズは最大4GBを使用できる。

セグメント機構

ここから実際のメモリ変換で使用されるセグメント機構を見ていく。

セグメントセレクタ

論理アドレスはセグメント識別子(16bit)とオフセット(32bit)から成る。オフセットはセグメント内での相対位置を表している。セグメント識別子はセグメントセレクタという以下の構造で管理される。

bit 名前 用途
0 ~ 1 RPL(Request Privilege Level) CPUの特権レベルを表す
2 TI(Table Indicator) セグメントがGDT(0)にあるのかLDT(1)にあるのかを示す
3 ~ 15 Index GDTもしくはLDTのインデックス

セグメントレジスタ

CPUにはセグメントセレクタを保持するための以下の6種類のセグメントレジスタが用意されている。

  • cs: コードセグメントレジスタ。プログラムの命令が配置されているセグメントを指す。当該レジスタ内の2bitはCPUの現行特権レベルで0ならカーネル、3ならユーザレベルと成る。
  • ss: 現在実行しているプログラムのスタックセグメントを指す。
  • ds: グローバルな静的データが置かれたセグメントを指す。
  • es: 汎用セグメントを指す。
  • fs: 汎用セグメントを指す。
  • gs: 汎用セグメントを指す。

セグメントディスクリプタ

8バイト長のデータ構造となっており、セグメントの特性を保持する。セグメントディスクリプタには主に以下のような種類がある。

  • コードセグメントディスクリプタ: GDTもしくはLDTに内に存在し、Sフラグを1に設定する。コードセグメントを示す。
  • データセグメントディスクリプタ: GDTもしくはLDTに内に存在し、Sフラグを1に設定する。データセグメントを示す。
  • タスク状態セグメントディスクリプタ: GDT内にのみ存在し、sフラグを0に設定する。プロセッサのレジスタ群のの内容を退避するために使用する。
  • GDT内にのみ存在し、Sフラグを0に設定する。LDTが存在するセグメントを参照するディスクリプタ

セグメントディスクリプタarch/x86/include/asm/desc_defs.hで以下のように定義されている。

// 8 byte segment descriptor
struct desc_struct { 
    u16 limit0;
    u16 base0;
    unsigned base1 : 8, type : 4, s : 1, dpl : 2, p : 1;
    unsigned limit : 4, avl : 1, l : 1, d : 1, g : 1, base2 : 8;
} __attribute__((packed)); 

各フィールドの説明を以下の表にまとめた。

構造体メンバー名 フィールド名 説明
base0(0 ~ 15), base1(16 ~ 23), base2(24 ~ 31) ベース セグメントの先頭アドレスを示す
limit0(0 ~ 15), limit1(16 ~ 19) リミット セグメント長を表す。Gフラグが0なら1Byte ~ 1KBの範囲、1なら4KB ~ 4GBの範囲となる
type タイプ セグメントのタイプとアクセス権を表す
s システムフラグ 0ならLDTなどの重要なデータ構造を保持するシステムセグメント。1ならコードセグメント若しくはデータセグメント
dpl DPL ディスクリプタ特権レベルを示す。DPLはCPLとなる。0ならカーネル、3ならユーザレベルとなる
g Gフラグ ラニュラリティを表すフラグ。0ならセグメント長の単位はバイトで表し、1ならページ(4KB)で表す
p Pフラグ セグメントがメモリに存在しているかを表すフラグ。0ならスワップアウトされており、1ならメモリ上に存在する。Linuxではセグメント全体をスワップアウトすることはないので常に1となる
d Dフラグ セグメントのオフセットが32bitの場合に1を設定し、16bitの時に0を設定する
avl AVLフラグ Linuxでは使用しない

グローバルディスクリプタテーブル/ローカルディスクリプタテーブル

セグメントディスクリプタは以下の2種類のどちらかのテーブルで管理される。実際にディスクリプタにアクセスする際にはテーブルのインデックスを指定する。

GDTR/LDTR

GDT及びLDTの先頭アドレスとサイズを保持する専用レジスタ。GDTRの構造は以下のようになっている。

bit サイズ 用途
0 ~ 15 16bit Limit
16 ~ 47 32bit Base Address

arch/x86/boot/pm.cではGDTポインタとして同じ構造で定義されている。

/*
 * Set up the GDT
 */

struct gdt_ptr {
    u16 len;
    u32 ptr;
} __attribute__((packed));

*To do: LDTRの構造を調べる

セグメンテーション回路

セグメンテーション回路では以下のような流れでアドレス変換が行われる。

  1. セグメントレジスタに読み込まれているセグメントセレクタ(論理アドレスの16bit)のTIを参照しセグメントディスクリプタがGDTに存在するのかLDTに存在するのかを決定する。
  2. GDTR若しくはLDTRからディスクリプタテーブルのベースアドレスを取得する。セグメントセレクタのインデックスフィールドに8を乗算したものをテーブルのインデックスとし、先ほど取得したベースアドレスに加算することでセグメントディスクリプタの先頭アドレスが取得できる。
  3. セグメントディスクリプタのベースフィールドに論理アドレスのオフセットを加算しリニアアドレスを得る。

セグメントレジスタに対応したノンプログラマブルレジスタがセグメントディスクリプタの情報を保持するため、上記のアドレス変換はセグメントレジスタを変更した際にのみ発生する。

Linuxのセグメント機構

Linuxではセグメント機構の使用を最小限に留めている。理由はセグメンテーション及びページング共に論理的なアドレスを異なる物理アドレスに変換する機能なので冗長なためLinuxではページングを優先して使用している。

ページングを優先して採用する理由には以下のようなものが挙げられる。

  • 全てのプロセスでセグメントレジスタを同値にする事でアドレス変換を簡略化できる。
  • Linuxの設計思想には様々なアーキテクチャへの対応があるが、RISCの中には限定したセグメント機構しか備わっていないものもある。

セグメントの種類

ユーザモードで動作するLinuxプロセスは1組みのユーザコードセグメントとユーザデータセグメントが割り当てられる。同様にカーネルモードで動作するLinuxプロセスには1組みのカーネルコードセグメントとカーネルデータセグメントが割り当てられる。以下に対応するセグメントディスクリプタの値を示す。

セグメント Base G Limit S Type DPL D/B P セレクタ変数名
ユーザコード 0x00000000 1 0xFFFFF 1 10 3 1 1 __USER_CS
ユーザデータ 0x00000000 1 0xFFFFF 1 2 3 1 1 __USER_DS
カーネルコード 0x00000000 1 0xFFFFF 1 10 0 1 1 __KERNEL_CS
カーネルデータ 0x00000000 1 0xFFFFF 1 2 0 1 1 __KERNEL_DS

セグメントセレクタarch/x86/include/asm/segment.hで以下のように定義されている。

#define __USER_CS (GDT_ENTRY_DEFAULT_USER_CS * 8 + 3)
#define __USER_DS (GDT_ENTRY_DEFAULT_USER_DS * 8 + 3)
#define __KERNEL_CS (GDT_ENTRY_KERNEL_CS * 8)
#define __KERNEL_DS (GDT_ENTRY_KERNEL_DS * 8)

#define GDT_ENTRY_DEFAULT_USER_CS  14
#define GDT_ENTRY_DEFAULT_USER_DS  15
#define GDT_ENTRY_KERNEL_CS        (GDT_ENTRY_KERNEL_BASE + 0)
#define GDT_ENTRY_KERNEL_DS        (GDT_ENTRY_KERNEL_BASE + 1)

#define GDT_ENTRY_KERNEL_BASE  12

__**_CS__**_DSに対応するわけだが、これは基本的にDPLの値が同値となっている。SSレジスタについてもデータセグメント内にスタックが確保されるのでDSレジスタと同じ値が入る。

GDT

GDTはCPUの数に対応した個数用意される。よってシングルプロセッサでは1個、マルチプロセッサでは複数個のGDTをシステムは保持する。

GDT内部の配置は以下のようになることがarch/x86/include/asm/segment.hにコメントで記載されている。

/*
 * The layout of the per-CPU GDT under Linux:
 *
 *   0 - null
 *   1 - reserved
 *   2 - reserved
 *   3 - reserved
 *
 *   4 - unused            <==== new cacheline
 *   5 - unused
 *
 *  ------- start of TLS (Thread-Local Storage) segments:
 *
 *   6 - TLS segment #1            [ glibc's TLS segment ]
 *   7 - TLS segment #2            [ Wine's %fs Win32 segment ]
 *   8 - TLS segment #3
 *   9 - reserved
 *  10 - reserved
 *  11 - reserved
 *
 *  ------- start of kernel segments:
 *
 *  12 - kernel code segment       <==== new cacheline
 *  13 - kernel data segment
 *  14 - default user CS
 *  15 - default user DS
 *  16 - TSS
 *  17 - LDT
 *  18 - PNPBIOS support (16->32 gate)
 *  19 - PNPBIOS support
 *  20 - PNPBIOS support
 *  21 - PNPBIOS support
 *  22 - PNPBIOS support
 *  23 - APM BIOS support
 *  24 - APM BIOS support
 *  25 - APM BIOS support 
 *
 *  26 - unused
 *  27 - unused
 *  28 - unused
 *  29 - unused
 *  30 - unused
 *  31 - TSS for double fault handler
 */

GDTのエントリ数やサイズはarch/x86/include/asm/segment.hで以下のように定義されている。

/*
 * Number of entries in the GDT table:
 */
#define GDT_ENTRIES 32


#define  GDT_SIZE (GDT_ENTRIES*8)

アドレスとサイズはarch/x86/include/asm/desc_defs.hで以下のような構造体により管理される。

struct desc_ptr {
    unsigned short size;
    unsigned long address;
} __attribute__((packed)) ;

GDT内部のレイアウトでは以下の種類のセグメントが扱われる。

  • ユーザとカーネルのコードセグメント及びデータセグメント
  • プロセッサ毎にタスクの状態を保持するTSS(Task State Segement)
  • 初期設定のLDTを管理するセグメント
  • 3のThread Local Storage(TLS)。マルチスレッドアプリケーションにおいてスレッド固有のデータを保持するセグメント。
  • APM(Advanced Power Management)用の3つのセグメント。
  • PnP(Plug-and-Play)用の5つのセグメント。
  • カーネルが「ダブルフォルト例外」を処理するために使用する特別なセグメント。

プロセッサ毎にGDTの複製を持っているが、一部を除いて同一のエントリを保持している。 各プロセッサには固有のTSSが存在し、LDTやTLSは現在実行しているプロセスに依存する。 プロセッサは一時的にGDTのエントリを変更することもあり、APMBIOS手続きを呼び出す際などに変更を加える。

LDT

LinuxのユーザモードアプリケーションのほとんどはLDTを使用しない。ユーザモードで動作するプロセスはカーネルが定義した初期設定のLDTを共有する。

arch/x86/include/uapi/asm/ldt.hではエントリのサイズや最大エントリ数などが定義されている。

/* Maximum number of LDT entries supported. */
#define LDT_ENTRIES    8192
/* The size of each LDT entry. */
#define LDT_ENTRY_SIZE 8

LDTにはdesc_struct構造体ポインタが用いられており、GDTと同じデータ構造になっていることがわかる。

参考文献