xv6を読む：メモリアロケータ

実行時に、プロセスやカーネルにページを割り当てるため、xv6はメモリアロケータを使用する。メモリアロケータは、未使用のページのフリーリストを管理している。カーネルからの要求に従って、フリーリストからページを割り当てる。

カーネルの起動処理で、フリーリストを未使用のページで満たさなければならない。ここで、鶏と卵の問題が生じる。すなわち、フリーリストの初期化処理を行うためにはカーネルに物理メモリが割り当てられていなければならず、カーネルに物理メモリを割り当てるためにはメモリアロケータが動作しなければならない。

xv6では、フリーリストの初期化を二段階で行うことで、これを解決している。main関数から呼び出されるkinit1関数と、kinit2関数がそれである。関数呼び出しの関係を以下に示す：

main
:
+->kinit1
|  +->initlock
|  +->freerange
|     +->kfree
+->kvmalloc（前回説明。kinit1で初期化したページを使用する）
:
+->kinit2
|  +->freerange
|     +->kfree
:


ここで、xv6のアドレス空間について少し説明する。仮想アドレス空間を左に、物理アドレス空間を右に示す：


        4G->+----+
           /|    |\
     Device |    |
           \|    |
0xFE000000->|----|
           /|    |
            |    |
Free Memory |    | Kernel Space
            |    |
           \|    |
       end->|    |        +----+<-4G
            |    |        |    |\
 +0x100000->|    |        |    | Device
  KERNBASE->|    |        |    |/
           /|----|/       |----|<-PHYSTOP
            |    |        |    |\
            |    |        |    |
            |    |        |    |
            |    |        |    | Extended Memory
            |    |        |    |
 User Space |    |        |    |
            |    |        |    |
            |    |        |----|/
            |    |        |    |<-0x100000
            |    |        |    |<-I/O Space
            |    |        |    |<-640k
           \|    |        |    |<-Base Memory
         0->+----+        +----+
            Vertual      Physical


仮想アドレス空間では、カーネルは上位2GBにマップされる（KERNBASE=2GBに定義されている）。したがって、ユーザプロセスは2GBまでのアドレス空間を利用できる。カーネルのテキストとデータは、仮想アドレスでKERNBASE + 0x100000〜endの間にロードされる。これは、物理アドレス0x100000〜end - KERNBASEにマップされている。

物理アドレス空間で、カーネルの後ろ、すなわちend - KERNBASEからPHYSTOPまでの空間をページとして利用する。メモリアロケータは、この部分をフリーリストとして管理する。PHYSTOPは240MBに定義されている。

xv6はブート時のページテーブルとして、entrypgdirを持っている。entrypgdirは、仮想アドレスの0〜4MBを実アドレスの0〜4MBへ、仮想アドレスのKERNBASE〜KERNBASE + 4MBを実アドレスの0〜4MBへマップするよう設定されている。前回説明したkvmallocでカーネルページテーブルが作成されるまでは、カーネルはこのページテーブルを用いてアドレス変換を行う。すなわち、xv6は、カーネルのサイズは少なくとも4MBより小さいものと仮定している。

さて、kinit1では、end〜4MBまでの物理アドレス空間を4KBのページに分割し、フリーリストに登録する。この処理を行うのが、freerange関数とkfree関数である。kinit1は、main関数内で以下のように呼び出されている：

kinit1(end, P2V(4*1024*1024));


ここで、P2Vマクロは物理アドレスを仮想アドレスに変換するマクロである。このマクロは、単に引数 + KERNBASEに展開されるだけである。

freerange関数は、以下の処理を行う：

1. 引数vstartとvendで渡された仮想アドレス空間（範囲）についてPGSIZE(4KB)ごとにkfree関数を呼び出す

kfree関数は、以下の処理を行う：

1. 引数vで渡された仮想アドレスが以下の条件にない場合、パニックする：
• ページ境界に合っていない
• endより小さい
• v2p(v)がPHYSTOP以上である
2. vから1ページ分、メモリ領域を1で埋める
3. vをフリーリストにつなぐ

ここで、v2p関数は、上記のP2Vマクロの親戚で、仮想アドレスvからKERNBASEを引き、仮想アドレスを物理アドレスに変換するものである。同種の関数・マクロには、他にp2vとV2Pがある。

以上で、フリーリストの初期化の第1段階が完了した。これで、4MBまでの範囲で、メモリアロケータはページを割り当てることができる。

フリーリストの初期化の第2段階であるkinit2関数は、main関数のかなり後のほうで、以下のように呼び出されている：

kinit2(P2V(4*1024*1024), P2V(PHYSTOP));


4MBからPHYSTOPまでの物理アドレス空間を、フリーリストに登録する。以上でフリーリストの初期化はすべて完了し、メモリアロケータを使用することができる。