物理フレームアロケータの実装

IDTを構築してCPU例外を捕捉するの記事でCPU例外のハンドリングを実装しました。ここからは、UEFIから受け取ったメモリマップをもとに、使用可能な物理メモリをページ単位で管理する物理フレームアロケータを実装します。

メモリマップから使用可能な領域を判別する

UEFIからのメモリマップとGOPフレームバッファ情報の取得の記事で触れたとおり、BootInfo.memory_mapには生のメモリディスクリプタ列がそのまま保持されています。カーネル側はstd.os.uefiをインポートしない設計にしているため、ディスクリプタのレイアウトはkernel/pmm.zig側で独自に定義しています。

// kernel/pmm.zig
const MemoryDescriptor = extern struct {
    type: u32,
    _reserved: u32 = 0,
    physical_start: u64,
    virtual_start: u64,
    number_of_pages: u64,
    attribute: u64,
};

エントリを読み進める際は、この構造体のサイズではなく、UEFIから渡されたdescriptor_sizeを1エントリ分の刻み幅として使います。仕様上、実際のディスクリプタはこの構造体より大きくなる可能性があるためです。

fn descriptorAt(mmap: boot_info.MemoryMapInfo, index: usize) *const MemoryDescriptor {
    const offset = index * mmap.descriptor_size;
    return @ptrCast(@alignCast(mmap.buffer + offset));
}

すべてのメモリ種別が「空いている」わけではありません。今回、フレームアロケータが割り当てて良いと判断するのは次の3種別だけです。

const MemoryType = enum(u32) {
    loader_code = 1,
    loader_data = 2,
    boot_services_code = 3,
    boot_services_data = 4,
    conventional_memory = 7,
    _,
};

fn isUsable(memory_type: u32) bool {
    return switch (@as(MemoryType, @enumFromInt(memory_type))) {
        .boot_services_code, .boot_services_data, .conventional_memory => true,
        else => false,
    };
}

boot_services_code/boot_services_dataを含めているのは、ExitBootServicesを呼び終えた時点でこれらの領域はもう不要になっているためです。一方loader_code/loader_dataは含めていません。これは今まさに実行中のブートローダー・カーネルのイメージ自体が置かれている領域で、ここを「空き」とみなして誰かに渡してしまうと、実行中の自分自身のコードやデータを上書きされかねません。

ビットマップ方式と、その「鶏と卵」問題

物理フレームアロケータの実装方式には、ページ1つにつき1ビットを対応させるビットマップ方式と、空き領域を連続区間の連結リストとして持つフリーリスト方式があります。今回はビットの読み書きだけで完結し、実装と検証が単純なビットマップ方式を選びました。

ビットマップ方式には、この種のアロケータに共通する構造的な問題があります。「どのメモリが空いているか」を記録するビットマップ自体も、当然メモリ上のどこかに置く必要がありますが、それを置く場所を決めるためのアロケータは、このビットマップができるまでまだ存在しません。

対処として、init()の中でメモリマップを2回走査します。1回目でビットマップに必要なバイト数を算出し、2回目でそのサイズを収められる使用可能領域を探して、その先頭にビットマップ自身を直接配置します。

// kernel/pmm.zig（抜粋）
const bitmap_base: u64 = blk: {
    i = 0;
    while (i < mmap.entry_count) : (i += 1) {
        const desc = descriptorAt(mmap, i);
        if (isUsable(desc.type) and desc.number_of_pages * page_size >= bitmap_bytes) {
            break :blk desc.physical_start;
        }
    }
    arch.interrupts.halt();
};
bitmap = @ptrFromInt(bitmap_base);

十分な大きさの領域が1つも見つからなければ、その時点で起動を続ける意味が無いためhalt()しています。

初期化の流れ

ビットマップの置き場所が決まったあとの初期化は、次の3段階で行っています。

  1. 全ページをまず「使用中」にする：ビットマップの全バイトを0xFFで埋めます。MMIOやACPIテーブル領域、ファームウェア予約領域などを個別に列挙して除外するのではなく、「明示的に空きと分かった範囲だけを後から解放する」という設計にすることで、未知の種別を安全側（使用中）に倒しています
  2. 使用可能な範囲だけを解放する：メモリマップをもう一度走査し、isUsableを満たす範囲のビットだけを0に落とします
  3. ビットマップ自身の領域を、使用中へ戻す：ビットマップは使用可能な範囲の先頭を間借りして配置したため、2の処理で一度「空き」としてマークされてしまっています。これを最後に上書きして、使用中に戻します
// kernel/pmm.zig（抜粋）
var b: usize = 0;
while (b < bitmap_bytes) : (b += 1) bitmap[b] = 0xFF;

// (usable な範囲を setFree でループするコードは省略)

const bitmap_pages = (bitmap_bytes + page_size - 1) / page_size;
const bitmap_start_page: usize = @intCast(bitmap_base / page_size);
var p: usize = 0;
while (p < bitmap_pages) : (p += 1) {
    setUsed(bitmap_start_page + p);
    free_page_count -= 1;
}

alloc/free：ビットを走査するだけの単純な実装

alloc()はビットマップを先頭から走査し、最初に見つかった空きビットを使用中にして、そのページの物理アドレスを返します。

pub fn alloc() ?usize {
    var i: usize = 0;
    while (i < page_count) : (i += 1) {
        if (isFree(i)) {
            setUsed(i);
            free_page_count -= 1;
            return i * page_size;
        }
    }
    return null;
}

割り当てのたびに毎回先頭から線形探索するため、割り当て済みページが増えるほど遅くなります。この非効率さは、フリーリストのような別方式に切り替えれば改善できますが、現時点ではまず正しく動くものを用意することを優先し、最適化は扱っていません。

物理アドレスをそのまま読み書きできる前提について

pmm.zigは、alloc()が返した値を物理アドレスとして扱い、@ptrFromIntで直接読み書きできることを前提にしています。これは今のところ正しく動作しますが、この時点ではまだページングを自前で実装しておらず、UEFIが用意した恒等マッピング（仮想アドレスと物理アドレスが一致する状態）に乗っているだけです。仮想アドレス空間を自分で設計する段階になると、この前提はもう成り立たなくなります。

QEMUでの確認

テキスト出力がまだ無いため、IDTを構築してCPU例外を捕捉するの記事と同じく、値をフレームバッファの色にエンコードして検証しました。今回はfreePageCount()の値をそのままRGB各チャンネルに分割して埋め込み、スクリーンダンプから10進数に復元しています。

QEMUのデフォルト設定（128MiB RAM）で得られた値は次の通りです。

free_page_count = 31184 (121.8 MiB)

boot_services_code/boot_services_dataまで使用可能に含めているため、UEFIからのメモリマップとGOPフレームバッファ情報の取得の記事で確認したconventional_memoryのみの数値（83 MiB）より大きく、かつ総RAM量（128 MiB）からファームウェア予約領域やビットマップ自身の分を差し引いた範囲に収まっており、妥当な値と言えます。

続けて、2回連続のalloc()が別々のアドレスを返すこと、free()で解放したページがその後のalloc()で再び返ってくることも同様の手法で確認しています。

今後

今後はページングを自前で実装し、恒等マッピングへの依存を解消します。物理フレームアロケータは、そのページテーブル自体を格納する物理ページの調達先としても使うことになります。

参考リンク