OSの役割は（と10日目にしてはじめて説明するのは良いのだろうか……），計算資源・デバイスの抽象化と管理です。コンピュータの二大資源はCPUとメモリです。CPUは時分割で資源管理します。これをスケジューラと呼びます。メモリは空間分割により資源管理します。メモリ割り当てを行う機能をメモリアロケータと呼びます。

今日は物理メモリ管理を実装していきます。バディシステムの実装まで終わらせようと思っていたのですが，メモリを管理するためのメモリをどう確保しようか，設計に悩んで時間を溶かしましたので，今日はページテーブルの設定までです。すみません。

物理メモリはページ単位で管理します。CPUのページテーブルはページ単位での保護機能を提供するので，これにあわせます。x86/x86-64のページテーブルは4 KiB, 2 MiB, 1 GiBのページをサポートします。このうち4 KiBのページがよく使われています。しかし4 KiBのページングは大容量のメモリ（または仮想メモリ空間）に対して，ページテーブルだけで大量のメモリを消費します。そこで，近年では，スーパーページと呼ばれる2 MiBと4 KiBのページサイズを組み合わせたページングが実装されています。

仮想メモリ（ページテーブル）により連続していない物理ページを連続した仮想メモリとして見せることができるため，基本的には物理メモリもこの2 MiBと4 KiBのページサイズに合わせて管理すれば良いのですが，DMAのように物理メモリ空間を直接参照するものは，連続した物理メモリ空間を割り当てる必要があります。

連続したメモリ領域を管理する方法として，最も簡単なものが4 KiBまたは2 MiBの連続するページをビットマップとして表現し，そこから空き領域を探し出すものです。アロケーションアルゴリズムとしては，ビットマップを先頭から走査して最初に見つかった空き領域を割り当てる「First Fit」や走査を前回の割り当て領域から行う「Next Fit」，最も空き領域のサイズが近い領域を割り当てる「Best Fit」，最も大きい空き領域から割り当てる「Worst Fit」などがあるが，これらは走査を行うため計算量が大きく，また大容量のメモリで4 KiBページを管理しようとするとビットマップが大量のメモリを消費してしまう問題があります。

この連続した物理メモリ空間を効率良く割り当てるアルゴリズムが後述するバディシステムと呼ばれるものです。

Linuxではメモリを複数のゾーンに分けて管理しています。代表的なゾーンは以下の3つです。

• ZONE_DMA: 0–16 MiB; ISA DMAは16 MiB以下の領域のみをサポートしているため，この領域を特別なゾーンとして扱います。
• ZONE_NORMAL: 16–896 MiB; Linuxでは896 MiBまでをNormalな領域として扱い，カーネルのメモリはこの領域から割り当てられます。
• ZONE_HIGHMEM: 896– MiB; ユーザランドアプリケーション用の領域です

さらに，以前は複数のCPUで共通のメモリコントローラを使用するSymmetric MultiProcessing (SMP)が主流でしたが，現在はCPUごとにメモリコントローラを持つNon-Uniform Memory Access (NUMA)が主流となっています。メモリコントローラ（CPUソケット）をNUMAドメインと呼びます。NUMAは現段階では扱いませんが，後日取り扱うかもしれませんので，ゾーン以外にNUMAドメインというものがあるということを念頭においておきます。なお，NUMAの情報はAdvanced Configuration and Power Interface (ACPI)を使って取得できます。

NUMAでは異なるドメインへのメモリアクセスは遅延が大きくなる上に，CPUソケット（メモリコントローラ）間のインターコネクト（Intelの場合はQPIやUPI）の帯域を消費するので，実行するCPUソケットと同じNUMAドメインのメモリを使うことが望ましいです。そのため，NUMAドメインごとに物理メモリを管理します。

一方，メモリを管理するためのメモリ領域など，すべてのコアで共有される領域などNUMA-awareに実装できない領域があります。NUMA_AWAREのゾーンから割り当てることにします。しかし，ACPIのNUMAドメイン情報を読むのにもメモリは必要なので，advosでは，以下のように太古のデバイスとの互換性用DMA領域，カーネルが使用する領域，NUMA-awareで使用する領域に分けます。

• ZONE_DMA: 0–16 MiB
• ZONE_KERNEL: 16–64 MiB
• ZONE_NUMA_AWARE: 64– MiB

物理ページはバディシステムで管理します。

バディシステムでは，2^nページのブロックを連結リストで管理します。バディシステムでは2^nページの割り当て，返却を行います。2^nではなく，フィボナッチ数列を使うものもありますが，今回は2^nのバディシステムを実装します。

例えば，下図のように連続した8ページがあるとします。この場合，バディシステムでは，8ページを1つのブロックとしてまとめます。このとき，2^3からこのブロックにリンクを作ります。2^2，2^1，2^0ページのブロックは現在は存在しないので，ポインタの先は空（NULL）となっています。

ここから1ページを割り当てることを考えます。1(=2^0)ページのブロックリストは空なので，1段上の2^1ページのブロックの分割を試みます。これを空でない2^nページのブロックリストまで再帰的に実行します。この例の場合，2^3ページのブロックリストが空ではないので，下図のようにこのブロックを2分割して，2^2ページのリストに接続します。

これを繰り返すと下図のように，1ページを割り当てることができます。

バディシステムでのページ解放は，（分割した）隣り合うページが揃ったときに連結し，1段上のブロックに挿入します。この隣り合うページを管理する都合で，連結リストはソート済みのリストとして扱うことにします。

今回は，オーダーは最大で18（2^18より上位のブロックは作らない）にします。通常は仮想メモリを使うので連続したメモリ領域は必要無いですが，2 MiBのスーパーページや1 GiBページング使う可能性も考えて，1 GiBまでは作ってあります。

バディシステムは連結リストでページを管理します。管理されるメモリ領域に連結リストのポインタを入れることで，バディシステムの管理に2^nのポインタ群以外に追加のメモリ領域が必要無い点が利点ですが，ブートローダから引き継いだページテーブルは，物理メモリのうち一部のみが仮想メモリにマッピングされており，全領域がアクセスできる状態ではありません。

64ビットモードであれば，十分大きな仮想メモリ領域があるので，全メモリ領域を割り当てることができます。しかし，ページテーブルを割り当てるには物理メモリを割り当てなければいけないので，にわたま問題が発生します。

なので，まずは

• ZONE_DMA: 0–16 MiB
• ZONE_KERNEL: 16–64 MiB の2領域のみを実装していきます。

x86/x86-64のページテーブルは，仮想メモリアドレスから物理メモリアドレスのマッピングはできますが，物理メモリアドレスから仮想メモリアドレスの逆変換はできません。逆変換のテーブルを作っても良いのですが，二重管理によりコードが複雑になってしまうため，各ゾーンのリニアマッピングをページテーブルのどこかに作成することにします。今回は，ZONE_DMAとZONE_KERNELの物理アドレス0x00000000-0x03ffffffを仮想アドレス0x100000000-0x103ffffffにマッピングするようにページテーブルを構築します。

これまではブートローダで構築したページテーブルをそのまま使ってきましたが，メモリ管理を実装する前にカーネルでページテーブルを作成します。まず，このページテーブルを構築するために4 KiBのブロックを5つ用意します。PML4とPDPTに1ブロックずつ，0-1 GiB，3-4 GiB，そして上記の領域のPDに1ブロックずつの合計5ブロックです。1-3 GiBの領域は今回は使わないので省略します。

メモリ管理が先か，ページテーブルが先かのにわたま問題を解決するために，20 KiB分の領域なので，ZONE-DMAとZONE_KERNELを管理するベースとなるページテーブルは，以下のメモリマップで予約していた0x00069000-0x0006ffffの28 KiBの領域を使います。

インラインアセンブラ混じりで汚いです（明日以降，整理したいと思います）が，上記のページテーブルは以下のC言語のコードで構築できます。最後にCR3にセットしています。

#define set_cr3(cr3)    __asm__ __volatile__ ("movq %%rax,%%cr3" :: "a"((cr3)))
static void
setup_kernel_pgt(void)
{
    int i;
    uint64_t base;
    uint64_t *pml4;
    uint64_t *e;

    /* Setup the kernel base page table */
    base = 0x00069000ULL;
    pml4 = (uint64_t *)base;

    /* Zero (memset() may work) */
    for ( i = 0; i < 512 * 5; i++ ) {
        *(pml4 + i) = 0;
    }
    /* First 512 GiB */
    *pml4 = (base + 0x1000) | 0x007;

    /* PDPT */
    e = (uint64_t *)(base + 0x1000);
    /* 0-1 GiB */
    *(e + 0) = (base + 0x2000) | 0x007;
    /* 3-4 GiB */
    *(e + 3) = (base + 0x3000) | 0x007;
    /* 4-5 GiB */
    *(e + 4) = (base + 0x4000) | 0x007;

    /* 0-1 GiB */
    e = (uint64_t *)(base + 0x2000);
    for ( i = 0; i < 512; i++ ) {
        *(e + i) = (0x00200000 * i) | 0x83;
    }
    /* 3-4 GiB (first 2 MiB) */
    e = (uint64_t *)(base + 0x3000);
    *(e + 0) = (0x00000000ULL) | 0x83;
    /* 4-5 GiB (first 64 MiB) */
    e = (uint64_t *)(base + 0x4000);
    for ( i = 0; i < 32; i++ ) {
        *(e + i) = (0x0ULL + 0x00200000 * i) | 0x83;
    }

    set_cr3(base);
}

これで0x100000000-0x103ffffffの64 MiBの仮想メモリ空間が，物理メモリ空間の0x00000000-0x003ffffff（ZONE_DMAおよびZONE_KERNEL）にリニアマッピングできました。これでバディシステムを実装する際に物理メモリ空間と仮想メモリ空間がリニアに対応付けできるので，物理→仮想のマッピングテーブルを持たずに実装することができます。

今日はバディシステムの説明と物理メモリ空間と仮想メモリ空間を扱いやすするためのページテーブルを構築しました。明日はバディシステムの実装をして物理メモリ管理をしていこうと思います。