Slab / Buddy アロケーション (ベアメタルのヒープ管理)

OS やベアメタル環境([[concepts/bare-metal-rust-freestanding]])で、固定サイズブロックを高速に確保・解放するためのヒープ管理アルゴリズム。[[entities/redox-slab-allocator]] の Rust 実装を一般化した概念ページ。汎用の [[concepts/malloc-allocator-internals]](可変サイズ glibc malloc)とは設計思想が異なる。

Slab allocation

大きなメモリ領域を特定サイズの固定ブロックに切り分けて管理する方式(slab = 厚切り)。手順:

1. 大きなメモリ領域を確保する。
2. 領域を一定サイズのブロックに分割する(例: 4KB を 64byte×64個 = slab_64_bytes)。
3. allocate で適切なサイズのブロックを割り当てる。
4. dealloc で再利用可能リストへ戻す。

固定サイズなので alloc/dealloc が O(1)、かつ同一サイズだけ扱うので外部断片化が起きない。core::alloc::Layout(size, power-of-two な align)から適切な slab サイズを選ぶ。

FreeBlockList のトリック

未使用ブロック自体を管理情報の置き場に流用する。64byte の slab なら、空きブロック先頭 8byte に next: Option<&'static mut FreeBlock> を埋め込んで連結リスト(intrusive list)を作り、残り 56byte は空けておく。誰にも割り当てていない領域なのでアロケータが内部利用してよい。Rust の null pointer optimization により Option<&mut T> はポインタ1個分のサイズで表現される。

Buddy allocation

可変サイズ要求に対応するため、領域を2の冪で再帰分割する古典手法(1960年代〜)。要求サイズ以上の最小の2冪ブロックに分割し、解放時に相棒(buddy)ブロックと再併合する。slab より細やかにサイズへ追従できる。実装では空きブロック探索に de Bruijn 列で BSR(最上位ビット)を O(1) 算出する技法が使える。

ベアメタル実装の注意

• #[global_allocator] に core::alloc::GlobalAlloc 実装を登録すると Box/Vec が使える。core::alloc と alloc::alloc の使い分けに注意。
• 並行アクセスは spin-lock(busy-wait, spin crate)で守る。内部可変は UnsafeCell::get(): *mut T。
• ヒープ初期化 init_heap() では確保すべき物理領域の場所を自分で知る必要がある(std が無いので)。デバッグは print も使えず syscall 頼み。
• Rust デフォルトのグローバルアロケータは jemalloc(現在は system allocator)だが、ベアメタルでは誰も面倒を見ないので自力管理する。

関連

• スレッドセーフ化のための per-thread arena は [[concepts/malloc-allocator-internals]]。
• [[concepts/operating-system-kernel]] / [[concepts/virtual-memory-mapping-strategies]]。