はじめに
こんにちは．だいみょーじんです．
この記事は，第38回自作OSもくもく会で発表した内容をまとめ，自作OSアドベントカレンダー2024の8日目の記事として公開したものです．
私が開発しているRust製の自作OS，HeliOSにおけるメモリ管理アルゴリズムについて解説します．
HeliOSはx64アーキテクチャ上で動作するOSで，以降の説明においてもx64アーキテクチャを想定します．
また，以降登場する全てのコードはRustです．
OSにおけるメモリ管理
OSの役割のひとつにメモリ管理があります．
OSは，OS自身が使用するメモリを確保したり，
不要になったメモリを解放したり，
アプリケーションにメモリを供給したり，
アプリケーションからメモリを回収したりします．
様々なメモリ管理アルゴリズムがありますが，今回私が採用したのはメモリの確保と解放が高速なことで知られるBuddy memory allocatorです．
Buddy memory allocator
とりあえず挙動を見よう
Buddy memory allocatorがメモリを管理している様子を見てみましょう．
横軸がメモリ空間，縦軸が時間で，上から下に時間が流れています．
- 上図の1段目，32KiBのメモリがある状態で，4KiBのメモリを要求されます．
- 2段目，32KiBは要求に対して大きすぎるので，2つの16KiBに分割します．
- 3段目，16KiBも大きすぎるので，2つの8KiBに分割します．
- 4段目，8KiBも大きすぎるので，2つの4KiBに分割します．
- 5段目，要求と同サイズの4KiBのメモリができたので，左端の4KiBを要求者に与えます．ここでさらに7KiBのメモリが要求されます．
- 6段目，7KiBの要求に対して，中央の8KiBのメモリを要求者に与えます．
- 7段目，5段目で与えた4KiBが返されます．
- 8段目，左端に4KiBの空きメモリが2つ並んでいるので，統合して8KiBの空きメモリとします．ここで9KiBのメモリが要求されます．
- 9段目，9KiBの要求に対して，右端の16KiBのメモリを要求者に与えます．ここで7KiBの要求し対して6段目で与えた8KiBのメモリが返されます．
- 10段目，左に8KiBの空きメモリが2つ並んでいるので，統合して16KiBの空きメモリとします．
- 11段目，9KiBの要求に対して10段目で与えた16KiBのメモリが返されます．
- 12段目，16KiBの空きメモリが2つ並んでいるので，統合して32KiBの空きメモリとします．
このようにBuddy system allocatorでは，2の冪乗の大きさのメモリに対して，それを半分サイズの2つ組（バディ）に分割したり逆に分割されたバディを統合することにより，要求に対して適した大きさのメモリを出し入れします．
全二分木による表現
このようなBuddy memory allocatorの挙動を実現する方法はいくつかありますが，ここでは全二分木を使う方法を採用します．
前述の挙動を全二分木で表現してみましょう．
32KiBのメモリがある状態で，4KiBのメモリを要求されます．
32KiBは要求に対して大きすぎるので，2つの16KiBに分割します．
16KiBも大きすぎるので，2つの8KiBに分割します．
8KiBも大きすぎるので，2つの4KiBに分割します．
要求と同サイズの4KiBのメモリができたので，左端の4KiBを要求者に与えます．
7KiBのメモリが要求されます．
7KiBの要求に対して，中央の8KiBのメモリを要求者に与えます．
左端の4KiBが返されます．
左端に4KiBの空きメモリが2つ並んでいます．
左端の2つの4KiBを統合して8KiBの空きメモリとします．
9KiBのメモリが要求されます．
9KiBの要求に対して，右端の16KiBのメモリを要求者に与えます．
中央の7KiBが返されます．
左端に8KiBの空きメモリが2つ並んでいます．
左端の2つの8KiBを統合して16KiBの空きメモリとします．
右端の9KiBが返されます．
16KiBの空きメモリが2つ並んでいます．
2つの16KiBを統合して32KiBの空きメモリとします．
このように，メモリの分割は親ノードからの子ノードの派生として表現され，メモリの統合は子ノードの親ノードへの吸収として表現されます．
初期化
このようなBuddy memory allocatorを構築する上で好ましいメモリ領域の性質が3つ挙げられます．
- きりの良いメモリアドレスから始まる．
- 2の冪乗のサイズを持つ．
- 連続している（間に使えない領域が散在していない）
しかし，実際のメモリマップは，割とごちゃごちゃしています．
ここで，まず切りの良いメモリアドレスから始まる連続領域を用意する手段として，ページングが考えられます．
ページングによって仮想アドレスから物理アドレスへの写像をうまいこといじくることによって，物理メモリ空間上に散在する利用可能な物理メモリ領域を，きりの良い仮想アドレス（0xffff_c000_0000_0000）から始まる連続した仮想メモリ領域にまとめることができます．
これにより，Buddy memory allocatorを構築する上で好ましいメモリ領域の3つの性質のうち，
- きりの良いメモリアドレスから始まる．
- 連続している（間に使えない領域が散在していない）
を満たすことができます．
残る性質は，「2の冪乗のサイズを持つ」ですが，利用可能な領域の大きさの合計がぴったり2の冪乗になることはほぼないでしょう．
この問題への対処として，2の冪乗のサイズを持つ「ヒープ領域」と，そのうち実際に利用可能な範囲である「利用可能領域」という2つの領域の情報を両方持っておくという方法があります．
上の図では，30MiBの利用可能領域に対して，実際には存在しない利用不可領域2MiBを付け加えることにより，ヒープ領域を32MiBにしています．
HeliOSにおけるBuddy memory allocator初期化の具体的な流れ
上述したBuddy memory allocator初期化は，HeliOSでは以下のような手順で実装されています．
- UEFIの機能を使ってメモリマップを取得し，ヒープ領域の大きさを決める．
- UEFIのメモリアロケータを使用し，ヒープ領域の仮想アドレスから物理アドレスへの写像を表すページング階層構造を確保しておく．
- UEFIブートサービスを終了すると同時に再度メモリマップを取得する．
- ブートサービス終了時のメモリマップを参照し，ヒープ領域の全ページの仮想アドレスから物理アドレスへの写像を，確保したページング階層構造に書き込む．
全二分木の表現
Buddy memory allocatorの全二分木は複数のノードで構成されますが，それらのノードの情報をどこに置くかに関して，大きく2つの選択肢があります．
- グローバルなデータ領域に固定長のノードリストを用意し，そこに置く．
- ヒープ領域内に置く．
前者の場合ノードリストの長さを静的に決める必要があります．
ノードリストが短すぎればメモリが十分に余っているにも関わらずメモリが確保できなくなる事態が発生しえます．
ノードリストが長すぎればノードリストの大部分が未使用となり，メモリの無駄が発生します．
後者の場合アルゴリズムが複雑になってしまいますが，需要に応じてある程度自由にノードの数を増減できるので，前者が抱える課題を解決できます．
今回は後者を採用することにしました．
利用可能領域の最後の4KiBページをノードリストとし，その分利用可能領域を減らします．
ノードリストの構造
ノードリストは複数のノードを持ちます．
全二分木を構成する各ノードは，幅優先順でノードリストに格納されます．
幅優先順にすることで，ノードリスト内の$n$番目のノードの子ノードが$2n+1$番目と$2n+2$番目に決まるため，新しいノードを作るときにノードリスト内の空きを探す必要がなくなり，処理の高速化につながります．
ノードリストの長さは4KiBと決めたため，葉ノード$n$から2つの子ノード$2n+1$および$2n+2$を生やそうとした際に，それらがノードリストの範囲外に飛び出してしまう場合があります．
その場合，分割した2つのメモリ領域それぞれの最後尾の4KiBページを新たなノードリストとし，それらの先頭に，ノード$2n+1$およびノード$2n+2$をそれぞれ配置します．
LinuxのBuddy memory allocatorは4KiBのページ単位でのメモリ管理を行っており，より細かいメモリ管理はSlab allocatorを使用しています．
今回のBuddy memory allocatorは，場合にもよりますが4KiBより細かくメモリを分割できます．
上の図の左のように，4KiBのメモリ領域を表すノード$n$が，ノードリスト内の十分に先頭寄りに存在する場合，そのメモリ領域をさらに細かく分割することができます．
上の図の右のように，4KiBのメモリ領域を表すノード$n$が，ノードリスト内の最後尾寄りに存在する場合，そのメモリ領域を分割するには新たなノードリストを作成する必要がありますが，ノードリストの長さは4KiBであり，新たなノードリストをそこに配置すると利用可能領域がなくなってしまうので，結局はこれ以上メモリを分割することができません．
ノードの構造
ノードは，以下の構造体として，ノードリスト内に存在します．
- stateはノードが指し示すメモリの状態です．
- rangeはノードが指し示すメモリ領域のアドレスの範囲です．
- available_rangeはノードが指し示すメモリ領域のうちの利用可能領域のアドレスの範囲です．
- max_sizeはノードが供給できる最大のメモリの大きさです．
struct Node {
state: State,
range: Range<usize>,
available_range: Range<usize>,
max_size: usize,
}
ノードの状態は，以下の列挙体で表現されます．
- Allocatedはノードが指し示すメモリが確保されている状態です．
- Dividedはノードが指し示すメモリが分割されている状態です．
- Freeはノードが指し示すメモリが解放されている状態です．
- Invalidはノードが指し示すメモリ全体が利用不可である状態です．
enum State {
Allocated,
Divided,
Free,
Invalid,
}
メモリの確保および解放の高速化
今回のBuddy memory allocatorは，メモリの確保および解放にかかる時間計算量が，ヒープ領域全体の大きさ$s$に対して$O(\log s)$となっています．
Node構造体のmax_sizeが，Buddy memory allocatorのメモリの確保および解放の高速化の役割を持っています．
例えば以下の図のように7KiB要求されて，全二分木を探索しまくって，最後の最後にようやく与えられる領域を見つけられたという状況を想像してみて下さい．
絶対に遅いです．
そこでどうすれば早くなるかと考えてみると，各ノードが自分が供給できるメモリの最大量を教えてくれれば，根ノードから葉ノードまで迷うことなく一直線に進めるわけです．
そして，確保するメモリ領域が確定したら，今度は来た道を戻るついでに各ノードのmax_sizeを更新してあげます．
考察
今回紹介したBuddy memory allocatorは，以下のようなメリットが挙げられます．
- メモリの確保と解放を時間計算量$O(\log s)$でできるようになった（はず）
- 4KiBより細かく分割できる場所もある．
また，以下のデメリットが挙げられます．
- ヒープ領域のページングの初期化に時間がかかる（GPD MicroPCで約1分）
- 4KiBより細かく分割できない場所もある．
まとめ
自作OSのメモリ管理として，Buddy memory allocator（っぽいもの）を作ってみました．
メモリを2分割したり，あるいは統合するという大まかな原理はLinuxのBuddy memory allocatorと同じですが，細かい部分は完全に我流です．
工夫した点
- 物理メモリ空間上に散在する利用可能領域を，ページングにより仮想メモリ空間上で連続した領域にまとめて扱いやすくした．
- しかし，初期化に時間がかかるようになった．
- ノードリストをヒープ内に置くことで全二分木の柔軟性を上げた．
- ノードが供給できるメモリの大きさの最大値を持つことで，メモリの確保および解放にかかる時間計算量を$O(\log s)$に抑えることができた．
今回紹介したBuddy memory allocatorのソースコードはこちらを参照してください．