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

この記事ではブートからカーネルのメイン関数に入るまでxv6がいかにメモリを参照するのかを追った前回の記事に続き、メイン関数以降のカーネル空間とユーザー空間でのメモリ管理の構造を追います。具体的には、xv6はMMU（メモリ管理機構）の2段のページング構造を使っていて、これは段数は違えどLinuxのメモリー管理構造と本質的には同じです。

main.c

xv6がブートし、entry.Sからカーネルのメイン関数に入ると、まずメモリのセットアップが行われます。先頭にあるkinit1関数と kvmalloc関数の二つがカーネルモードのメモリ空間を2段のページング構造を使ってセットアップし、デバイスの初期化や割り込みの設定等の後にkinit2関数とuserinit関数がユーザーモード用のメモリをセットアップします。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


int
main(void)
{
  kinit1(end, P2V(4*1024*1024)); // phys page allocator
  kvmalloc();      // kernel page table
  ... device initialization ...
  kinit2(P2V(4*1024*1024), P2V(PHYSTOP)); // must come after startothers()
  userinit();      // first user process
  mpmain();        // finish this processor's setup
}

カーネルモード

まずはカーネルモードのメモリ管理を追っていきます。ここでは先述したページングを使ったメモリ管理の仕組みがポイントとなります。そしてカーネルモードでのメモリページのマッピングは実はユーザーモードでも使われています。

メモリアロケーション

メイン関数の一番最初にあるkinit1関数は*vstartと*vendを引数にとり、指定された範囲分のメモリをカーネルが使えるようページ単位にアロケートし（割り当て）ます。上記のメイン関数ではend (ELFファイルからメモリへロードされたカーネル直後のアドレス)からP2V(4*1024*1024)（マクロを展開するとKERNBASEである0x80000000に4MBを足した0x80400000）までの範囲が指定されています。それではkinit1関数を追っていきます。

前回からのノート

カーネルの命令列は0x80100000の仮想アドレスをベースにリンクされています。

カーネルのメイン関数に入った時点ではカーネルはentrypgdirのマッピングを使った1段のページングモードで走っています。

まずkinit1関数はカーネルメモリの構造体のロックを初期化し、freerange関数を呼びます:

kalloc.c

1
2
3
4
5
6
7


void
kinit1(void *vstart, void *vend)
{
  initlock(&kmem.lock, "kmem");
  kmem.use_lock = 0;
  freerange(vstart, vend);
}

freerange関数はvstartからvendまでPGSIZEごとにkfreeを呼んでいます:

1
2
3
4
5
6
7
8


void
freerange(void *vstart, void *vend)
{
  char *p;
  p = (char*)PGROUNDUP((uint)vstart);
  for(; p + PGSIZE <= (char*)vend; p += PGSIZE)
    kfree(p);
}

そしてkfreeは指定されたアドレスから1ページ分1の値を書き込み、run構造体を指すポインターにキャストし、singly-linkedリストであるkmem.freelistの先頭に挿入します。メモリページを使用する場合はkalloc関数がこのkmem.freelistからポインターを返します:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


struct run {
  struct run *next;
};
...
void
kfree(char *v)
{
  ...
  // Fill with junk to catch dangling refs.
  memset(v, 1, PGSIZE);

  if(kmem.use_lock)
    acquire(&kmem.lock);
  r = (struct run*)v;
  r->next = kmem.freelist;
  kmem.freelist = r;
  if(kmem.use_lock)
    release(&kmem.lock);
}

2段ページング

ここまででカーネルが指定されたメモリ範囲をページごとに割り当てる仕組みを追ったので、引き続きkvmalloc関数がいかに2段のページング構造をセットアップしていくのかを見ていきます。

オンラインでx86 ページング等を検索するとこのようなダイアグラムが見つかり、3つに分割された仮想アドレスが物理アドレスに変換される様子は理解出来るのですが、この構造をOS側からいかに使うのかを明確に理解するのは（少なくとも自分には）容易ではありません。ここでのキーポイントはこの2段のマッピングをセットアップするのはOS側の仕事であり、またどう使うかはOS側の自由ということです。具体的にはOSはまず1ページ分のメモリをページディレクトリ用に、もう1ページ分のメモリをページテーブル用に割り当てます。そしてそのページディレクトリとページテーブルに好きな仮想アドレスと狙った物理アドレスをエントリーとして書き込むことで望んだマッピングが作られます。ここでもう一つ重要なのがこのマッピングがページディレクトリのアドレスで指定され、それをCR3レジスターが保持しているということです。これによりCR3レジスタの値を書き換えることでプロセスごとの仮想アドレスから物理アドレスのマッピングを切り替えることが可能になります。そしてこれから追うkvmalloc関数はこのセットアップからマッピングの切り替えまで全体の流れを実行します。

kvmallocは2段のページング構造をセットアップするsetupkvm関数を呼びます。setupkvmはまずkallocを呼び新たなページディレクトリの為のメモリページをpgdir変数にポインターとして格納します。その後キーとなる関数はmapppages関数で、渡されたページディレクト内に指定された仮想アドレスからページテーブルを作成し、その中のエントリーに物理アドレスを指定された範囲分書き込みます:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


pde_t*
setupkvm(void)
{
  pde_t *pgdir;
  struct kmap *k;

  if((pgdir = (pde_t*)kalloc()) == 0) // ページディレクトリの1ページ分のメモリへのポインターを格納
    return 0;
  memset(pgdir, 0, PGSIZE);
  if (P2V(PHYSTOP) > (void*)DEVSPACE)
    panic("PHYSTOP too high");
  for(k = kmap; k < &kmap[NELEM(kmap)]; k++)
    if(mappages(pgdir, k->virt, k->phys_end - k->phys_start,
                (uint)k->phys_start, k->perm) < 0) {
      freevm(pgdir);
      return 0;
    }
  return pgdir;
}

具体的にはmappages関数はページテーブルのエントリーに物理アドレスをページサイズごとに書き込み、指定された物理アドレスの範囲分を書き込むまでループします。ページテーブルのエントリーはwalkpgdir関数で作成され、ポインターが返されます:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21


static int
mappages(pde_t *pgdir, void *va, uint size, uint pa, int perm)
{
  char *a, *last;
  pte_t *pte;

  a = (char*)PGROUNDDOWN((uint)va);
  last = (char*)PGROUNDDOWN(((uint)va) + size - 1);
  for(;;){
    if((pte = walkpgdir(pgdir, a, 1)) == 0)
      return -1;
    if(*pte & PTE_P)
      panic("remap");
    *pte = pa | perm | PTE_P; // 物理アドレスを割り当てられたページテーブルのエントリーに書き込む
    if(a == last)
      break;
    a += PGSIZE;
    pa += PGSIZE;
  }
  return 0;
}

walkpgdir関数はまず指定された仮想アドレスであるvaをページディレクトリ内のインデックスに変換（先頭10ビットを抽出）し、渡されたページディレクトリへのポインターであるpgdirからインデックス指定することでページディレクトリのエントリーを指すポインターを作り、pde変数に格納します。そしてそのページディレクトリのエントリーがすでに存在しているかどうかをPTE_Pフラッグでチェックし、存在している場合はそのページディレクトリーのエントリーの値からページテーブルへのポインターをpgtab変数に格納します。存在しない場合は先にページテーブル用のメモリーを割り当て、そのアドレスをページディレクトリのエントリーの値として書き込みます。そしてこの分岐処理の後、ページテーブルのアドレスからvaの真ん中10ビットをインデックス値として指定したページテーブルのエントリーへのポインターが返り値となります:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21


static pte_t *
walkpgdir(pde_t *pgdir, const void *va, int alloc)
{
  pde_t *pde;
  pte_t *pgtab;

  pde = &pgdir[PDX(va)]; // ページディレクトリエントリーへのポインターを格納
  if(*pde & PTE_P){
    pgtab = (pte_t*)P2V(PTE_ADDR(*pde)); // ページディレクトリエントリーの値からページテーブルへのポインターを格納
  } else {
    if(!alloc || (pgtab = (pte_t*)kalloc()) == 0) // 新規ページテーブルのメモリをアロケート
      return 0;
    // Make sure all those PTE_P bits are zero.
    memset(pgtab, 0, PGSIZE);
    // The permissions here are overly generous, but they can
    // be further restricted by the permissions in the page table
    // entries, if necessary.
    *pde = V2P(pgtab) | PTE_P | PTE_W | PTE_U; // ページディレクトリエントリーに作成されたページテーブルのアドレスを書き込む
  }
  return &pgtab[PTX(va)];
}

ここまでで2段のページング構造がセットアップされる仕組みを追いました。では実際にxv6がどんな仮想メモリーのマップを作っているのかを見ていきます:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


static struct kmap {
  void *virt;
  uint phys_start;
  uint phys_end;
  int perm;
} kmap[] = {
 { (void*)KERNBASE, 0,             EXTMEM,    PTE_W}, // I/O space
 { (void*)KERNLINK, V2P(KERNLINK), V2P(data), 0},     // kern text+rodata
 { (void*)data,     V2P(data),     PHYSTOP,   PTE_W}, // kern data+memory
 { (void*)DEVSPACE, DEVSPACE,      0,         PTE_W}, // more devices
};

上記がソースコード上でのマッピングですが、実際の値は以下のようになります:

仮想アドレス: KERNBASE（0x80000000）を物理アドレス: 0からEXTMEM（0x100000）まで
仮想アドレス: KERNLINK（0x80100000）を物理アドレス: KERNLINK（0x100000）からV2P(data) (カーネルイメージのread-onlyデータ）まで
仮想アドレス: dataを物理アドレス: V2P(data)からPHYSTOP（0xE000000: 235MB）まで
仮想アドレス: DEVSPACE（0xFE000000）を物理アドレス: DEVSPACE（0xFE000000）から 0まで

カーネルのメイン関数にあるkvmalloc関数は上記のマッピングを作成し、最終的にswitchkvm関数がCR3レジスターにそのページディレクトリのアドレスを書き込むことでこのマッピングが有効になります。カーネルの命令列へのマッピングはentrypgdirから変わっていないので命令実行に影響は無くそのまま実行が進む訳です。

ユーザーモード

上記にあるようにカーネルのメイン関数では割り込みやデバイスの初期化の関数の後にkinit2(P2V(4*1024*1024), P2V(PHYSTOP))とuserinit()という二つの関数呼び出しが見られます。一つ目のkinit2は仮想アドレス0x80400000から0x8E000000を利用可能なページに割り当て、二つ目のuserinitはユーザープロセスの為にコンテクストやメモリー、割り込み等の設定を行います。

このuserinit関数を見ていくと、setupkvm関数が呼ばれているのが見られます。これはユーザーモード下で割り込みやシステムコールがあった場合にページディレクトリを切り替えなくてもカーネルのメモリーを参照できるようにする為であり、それが先述したようにユーザーモードでもカーネルのマッピングを使う理由になります。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12


void userinit(void)
{
  struct proc *p;
  extern char _binary_initcode_start[], _binary_initcode_size[];

  p = allocproc();

  initproc = p;
  if ((p->pgdir = setupkvm()) == 0)
    panic("userinit: out of memory?");
  inituvm(p->pgdir, _binary_initcode_start, (int)_binary_initcode_size);
  ...

setupkvm関数がカーネルのマッピングをセットアップするとuserinit関数はそのページディレクトリと共にinitcodeへのポインターとサイズをinituvm関数に渡して呼び出します。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12


void
inituvm(pde_t *pgdir, char *init, uint sz)
{
  char *mem;

  if(sz >= PGSIZE)
    panic("inituvm: more than a page");
  mem = kalloc();
  memset(mem, 0, PGSIZE);
  mappages(pgdir, 0, PGSIZE, V2P(mem), PTE_W|PTE_U);
  memmove(mem, init, sz);
}

上記のinituvim関数はまずkalloc関数を呼び出して新たなページをアロケートし、0の値でその中身をリセットします。そして仮想アドレスの0とそのページへの物理アドレスV2P(mem)をmappagesに渡して呼び出しています。これによって仮想アドレスの0がアロケートされた新規のメモリページを指す構造が出来あがります。最後にmemmoveがプロセスの初期化命令列であるinitをそのページに書き込むことでユーザープロセスがEIPの値として0のアドレスから実行できる環境が整う訳です。

まとめ

長い記事となってしまいましたが、前編と後編を通してxv6がどのようにメモリーを管理、参照するかを順序立てて追いました。記事に書き出すのは自分の理解を整理、確認するいい機会です。これが誰かの為に役に立てばと思います。

コンテンツ

main.c

カーネルモード

メモリアロケーション

2段ページング

ユーザーモード

まとめ