xv6: OSはどうメモリを参照、管理するのか（前編）

メモリ管理の仕組みはOSを理解するのに重要なポイントの一つですが、勿論x86エミュレーターを自作する際にもメモリ構造をエミュレートする為にMMU（メモリーマネジメントユニット）がどういう構造なのか、そしてそれをxv6のコードがどう使うのか理解するのは必須でした。この記事ではxv6がどのように命令列をリンクし、ブート後プロテクトモードやページングに入り、カーネルのメイン関数に入るまでメモリを参照するのかを追います。

少し具体的な話をすると、xv6のカーネルが0x80100000の仮想アドレスをベースに配置され読まれる仕組みについては、公式の教科書であるthe xv6 text bookやその他ネット上にあるxv6のメモリ管理の解説に書かれているのですが、それをカーネルソースコードのコンパイルやOSイメージ作成の段階から全て繋げた説明は中々見つからず、始めから終わりまで完全に理解するのは中々大変でした。この記事を含め当ブログではend-to-endな理解を重視しています。

Makefile

前回のxv6のブートブロックに関する記事でもそうしたように、Makefileから見ていきます。MakefileにOSイメージの作成レシピがある為です。以下がカーネルのバイナリを作成するコマンドになります。

kernel: $(OBJS) entry.o entryother initcode kernel.ld
	$(LD) $(LDFLAGS) -T kernel.ld -o kernel entry.o $(OBJS) -b binary initcode entryother
	$(OBJDUMP) -S kernel > kernel.asm
	$(OBJDUMP) -t kernel | sed '1,/SYMBOL TABLE/d; s/ .* / /; /^$$/d' > kernel.sym

ここではカーネルが必要とする全てのオブジェクトファイル、$(OBJS)をその他いくつかののファイルと一緒に依存リストに持つのが見られます。entry.oはCPUがブート後にカーネルのメイン関数に入る為のオブジェクトで、initcodeはユーザーモードで新規のプロセスを初期化する命令列です。そしてこの記事でキーとなるのがkernel.ldというファイルです。

kernel.ld

このkernel.ldというファイルはxv6のソースコード内に存在し、Makefileでldコマンドに-Tオプションの引数として使われるリンカースクリプトです。下記に見られるSECTIONS内の.は命令出力のアドレスを保持する特別なリンカーの変数で、ここでは値に0x80100000がセットされているのが見られます。これは出力されるバイナリの命令アドレスが0x80100000から始まるように指定している訳です。

OUTPUT_FORMAT("elf32-i386", "elf32-i386", "elf32-i386")
OUTPUT_ARCH(i386)
ENTRY(_start)

SECTIONS
{
	/* Link the kernel at this address: "." means the current address */
        /* Must be equal to KERNLINK */
	. = 0x80100000;

	.text : AT(0x100000) {
		*(.text .stub .text.* .gnu.linkonce.t.*)
	}

このリンカースクリプトの結果として、カーネルバイナリの命令列が指定されたアドレスから出力されます。これをobjdumpコマンドで以下のように確認することが出来ます。

$ objdump -M intel -S kernelmemfs

kernelmemfs:     file format elf32-i386


Disassembly of section .text:

80100000 <multiboot_header>:
80100000:	02 b0 ad 1b 00 00    	add    dh,BYTE PTR [eax+0x1bad]
80100006:	00 00                	add    BYTE PTR [eax],al
80100008:	fe 4f 52             	dec    BYTE PTR [edi+0x52]
8010000b:	e4 0f                	in     al,0xf

8010000c <entry>:

ブート時のメモリ構造

ブートプロセスに入った時点では、CPUはリアルモード下にあり、メモリは物理アドレスに一つの計算のみを通して参照されます。その計算というのは、命令ならCS、スタックならSSというように目的に対応したセグメントレジスタの値を左に4シフトし、それを指定されたアドレスに足すというものです。そしてブートブロック中のbootasm.Sの数命令の後、プロテクトモードに入ります。ここでのプロテクトモードへの遷移の仕方は割とシンプルなもので、上記リンク先やその他多数の解説がウェブで見つかります。プロテクトモードへ入るとメモリーはGDT（グローバルディスクリプタテーブル）を通して参照されます。このテーブルは複数のエントリーを持ち、個々のエントリーにはメモリのアドレス範囲を指定するベース値やリミット値に加えアクセス権限の情報が記されます。この時点で先述したセグメントレジスタの役割は変わっており、このテーブルのエントリーのインデックスを保持するポインターになります。

ページング

上記のMakefileやkernal.ldで触れたように、カーネルの命令アドレスは0x80100000をベースにしてリンクされます。これにはユーサーモードとカーネルモードの仮想メモリ範囲を切り分ける目的があり、それはx86のページング機構を使って行われます。ページングには様々なモデルがあり、xv6のカーネルのメイン関数へ入る為のentry.Sではpage size extensionを使った1段階のページングが使われ、カーネルのメイン関数に入ってからはすぐに2段階のページング構造がセットアップされ使われます。

`entry.S`のメモリ構造

先述したようにCPUがカーネルの大きな仮想アドレスを読むためにはページング機構を使う必要がある訳ですが、その為の設定はentry.Sで行われます。下記が該当部分のコードです。

# By convention, the _start symbol specifies the ELF entry point.
# Since we haven't set up virtual memory yet, our entry point is
# the physical address of 'entry'.
.globl _start
_start = V2P_WO(entry)

# Entering xv6 on boot processor, with paging off.
.globl entry
entry:
  # Turn on page size extension for 4Mbyte pages
  movl    %cr4, %eax
  orl     $(CR4_PSE), %eax
  movl    %eax, %cr4
  # Set page directory
  movl    $(V2P_WO(entrypgdir)), %eax
  movl    %eax, %cr3
  # Turn on paging.
  movl    %cr0, %eax
  orl     $(CR0_PG|CR0_WP), %eax
  movl    %eax, %cr0

ここではページディレクトリのアドレスを保持するCR3レジスターに$(V2P_WO(entrypgdir))という値をロードしているのが見られます。まずV2P_WOというのはmemlayout.hで定義されている引数からKERN_BASE(0x80000000)の値を引くマクロです。その引数であるentrypgdirはmain.c内で宣言されている配列で、ページディレクトリエントリの型（中身はuint）1024個分の領域を持っています。先述したようにentry.oはカーネルバイナリの一部分で、大きな仮想アドレスをベースにリンクされている為、当然この配列へのアドレスも仮想アドレスになっています。そしてCR3に値をロードする時点ではページングはまだオンになっていません。その為CR3の値にそのまま仮想アドレスをセットしてもMMUはそれを物理アドレスとして参照しようとしてしまい、エラーとなります。これがV2P_WOを使って物理アドレスに変換した値をCR3にセットする理由です。（ちなみにこのアセンブリコード自体もELFファイルのエントリーポイントとなる_startにV2P_WOでentryのアドレスを物理アドレスに変換してセットしているのが分かります。）ではページディレクトリの配列であるentrypgdirを見ていきます。

__attribute__((__aligned__(PGSIZE)))
pde_t entrypgdir[NPDENTRIES] = {
  // Map VA's [0, 4MB) to PA's [0, 4MB)
  [0] = (0) | PTE_P | PTE_W | PTE_PS,
  // Map VA's [KERNBASE, KERNBASE+4MB) to PA's [0, 4MB)
  [KERNBASE>>PDXSHIFT] = (0) | PTE_P | PTE_W | PTE_PS,
};

ページディレクトリのエントリーが2つあり、両方ともPTE_PSのフラッグがORオペレーターで立てられているのが見られます。このフラッグはCR4レジスターのpage size extensionビットが立っている場合に於いてエントリーのページング構造を1段階に指定します。具体的には1段階のページング構造では（上記リンク先の図にも見られるように）アドレスの先頭10ビットで指定されたページディレクトリのエントリーが持つアドレスがすでに物理アドレスで、残りの22ビットがそこからのオフセットとして使われます。そしてその2つのエントリーのマッピングを見ていくと、一つ目は0番地を0番地に、二つ目はKERNBASE(0x80000000)を0番地にマップしているのが分かります。二つとも結局物理アドレスの0を指す訳ですが、それらはページング機構をオンにしてメイン関数へ遷移する際に使われます。ここまでブートからentry.oのコードまで追ってきている訳ですが、ページング機構をオンにする時点ではEIP（命令ポインター）は物理アドレス空間の値で実行しています。EIPのアドレス参照も勿論ページングをオンにした際に適用されるので、ページングをオンにした瞬間に仮想アドレスのマッピングしかなかったら、命令列を参照出来なくなってしまいます。これが一つ目の0-to-0のマッピングが必要な理由で、この種のマッピングはIdentical Mappingと呼ばれます。長くなってしまいましたがこの後entry.Sはmain.c内のmain()関数にジャンプします。ここでようやくEIPの値がジャンプ先の仮想アドレスとなり、2つ目のマッピングが使われ、仮想アドレス空間でカーネルのコードへの遷移が成功する訳です。

カーネルのメイン関数に入るとすぐによく知られた2段階のページングモデルに移行しますが、ここまでで既に結構な説明の量になってしまっている上に2段階のメモリ管理は更なるボリュームになりかねないので、後編として別記事で書きたいと思います。読んで頂きありがとうございました。自分の学習を秩序立てて記すことはとても良いエクササイズで、更にそれが誰かの為になっていたらwinwinだと思います。