フリーリスト方式のヒープアロケータとstd.mem.Allocator対応

自前のページテーブルへの切り替えと、そこで踏んだ地雷の記事でページングが動くようになりました。今回はpmmが貸し出す4KiB単位のページを、もっと小さい任意サイズの確保に切り分けるヒープアロケータを実装します。

設計方針：フリーリスト、隣接ブロックの結合は見送り

方式はフリーリスト（空き領域を連結リストとして管理する）を選びました。確保時は先頭から順に、要求サイズを満たす最初のブロックを使うfirst-fitです。

// kernel/heap.zig
const BlockHeader = struct {
    size: usize, // このブロック全体のバイト数（ヘッダ込み）
    next: ?*BlockHeader,
};

var free_list: ?*BlockHeader = null;

解放時は、返ってきたブロックをそのままフリーリストの先頭に戻すだけの実装にしています。本来であれば、解放したブロックが物理的に隣接する別の空きブロックと連続していないかを調べ、連続していれば1つの大きな空きブロックに結合する処理が必要です。これを省略しているため、確保と解放を繰り返すうちに、本来使えるはずの連続した空き領域が細切れの小さなブロックに分かれたまま残ってしまう（断片化する）という制約が残っています。今回はこれを既知の制約として明記し、後から中身だけ差し替えられる形にとどめています。

複数ページにまたがる確保のために、pmmに機能を1つ追加した

ヒープの空きブロックが尽きた場合、pmmから新しくページを借りて空きブロックを追加します。ここで問題になったのが、pmm.alloc()が一度に1ページしか返さず、しかも複数回呼び出した結果が連続した物理アドレスになる保証がないことです。数バイトの確保であれば1ページ借りれば十分ですが、数KB以上のまとまった確保を1回で満たすには、連続した複数ページが必要になります。

そこでpmmに、指定した数だけ連続する空きページを探す関数を追加しました。

// kernel/pmm.zig
pub fn allocContiguous(count: usize) ?usize {
    if (count == 0) return null;
    var i: usize = 0;
    while (i + count <= page_count) {
        var run: usize = 0;
        while (run < count and isFree(i + run)) : (run += 1) {}
        if (run == count) {
            var k: usize = 0;
            while (k < count) : (k += 1) {
                setUsed(i + k);
                free_page_count -= 1;
            }
            return i * page_size;
        }
        i += run + 1;
    }
    return null;
}

ビットマップを先頭から走査し、count個分のビットが連続して空いている位置を探すだけの単純な実装です。ヒープの成長は、この関数で要求サイズぴったりのページ数を確保するだけにとどめており、将来の確保に備えてあらかじめ多めに確保しておくような先読みは行っていません。

std.mem.Allocatorに対応させる

Zigにはstd.mem.Allocatorという、標準ライブラリ全体で共通して使われるアロケータのインターフェースがあります。関数ポインタの集まり（VTable）を実装することで、標準ライブラリの様々な機能（動的配列など）にこのヒープをそのまま渡せるようになります。

// kernel/heap.zig
const vtable = std.mem.Allocator.VTable{
    .alloc = rawAlloc,
    .resize = rawResize,
    .remap = rawRemap,
    .free = rawFree,
};

pub fn allocator() std.mem.Allocator {
    return .{ .ptr = undefined, .vtable = &vtable };
}

allocは新規確保、freeは解放、resizeはアドレスを変えずにその場でサイズ変更できるか（できなければfalseを返し、呼び出し側が新規確保・コピー・旧領域の解放を自分で行う）、remapはアドレスが変わってもよいという条件でのサイズ変更を担当します。今回の実装では、resizeとremapはどちらも「今のブロックの容量に収まるかどうか」を判定するだけの単純なもので、ブロックの再分割や隣接ブロックへの拡張は行っていません。

// kernel/heap.zig
fn rawResize(ctx: *anyopaque, memory: []u8, alignment: std.mem.Alignment, new_len: usize, ret_addr: usize) bool {
    _ = ctx;
    _ = alignment;
    _ = ret_addr;
    const capacity = headerOf(memory).size - header_size;
    return new_len <= capacity;
}

headerOfは、確保時に返したポインタから、その直前に置かれているヘッダの位置を逆算する小さなヘルパーです。

// kernel/heap.zig
fn headerOf(memory: []u8) *BlockHeader {
    return @ptrFromInt(@intFromPtr(memory.ptr) - header_size);
}

アラインメントは16バイトまでに限定

std.mem.Allocatorのインターフェースは、確保時に任意のアラインメント要求を受け取れるようになっています。今回のヒープでは、すべてのブロックを16バイト境界に揃える設計にしており、それを超えるアラインメント要求（SIMD用の大きなアラインメントなど）には対応していません。

// kernel/heap.zig
fn rawAlloc(ctx: *anyopaque, len: usize, alignment: std.mem.Alignment, ret_addr: usize) ?[*]u8 {
    if (alignment.toByteUnits() > block_alignment) return null;
    ...

現時点のカーネルコードは、ポインタサイズ程度のアラインメントで足りる構造体しか扱っていないため、この制限で困る場面はありません。より大きなアラインメントが必要になった時点で見直す前提の、意図的な割り切りです。

QEMUでの確認

物理フレームアロケータの実装の記事や自前のページテーブルへの切り替えと、そこで踏んだ地雷の記事と同じく、フレームバッファの色に検証結果をエンコードして確認しました。

  • サイズの異なる3回の確保（64バイト、128バイト、複数ページにまたがる8192バイト）がいずれも成功し、それぞれ別々のアドレスを返すこと
  • 1つを解放したあと、同じサイズを再度確保すると、解放前と同じアドレスが返ってくること（フリーリストへ正しく戻され、再利用されていること）

の両方を1回の起動で確認し、いずれも問題ありませんでした。8192バイトの確保は複数ページにまたがるため、pmm.allocContiguousが連続ページを正しく見つけられていることの確認も兼ねています。

今後

今後はタイマー割り込みとキーボード入力を実装し、外部からの入力をカーネルが受け取れるようにします。

参考リンク