← OSと低レイヤのしくみ コース
13. カーネル側のメモリ確保 — バディとスラブ
カーネルが物理ページとカーネルオブジェクトをどう確保するかを、2段構えの仕組みとして図で追っていきましょう。
① 2段構えの全体像
カーネル内のコードstruct を1個ほしい / ページがほしい
要求サイズで行き先が変わる
slab / SLUB 層ページ未満の小さなオブジェクト
kmalloc() / kmem_cache_alloc()ページ単位の要求4KiB 以上のまとまり
alloc_pages()slab 層も足りなくなるとページを買いに行く
バディアロケータ物理ページを2の冪の塊で管理
zone ごとの free_area最終的な実体
物理メモリのページPAGE_SIZE = 4KiB(x86-64の既定)
- ・カーネル公式の Memory Allocation Guide は、同一のオブジェクトを多数確保するなら slab キャッシュを使うのがよいとしています
- ・同じガイドは、kmalloc で確保できる上限はハードウェアと構成に依存するとしたうえで、ページサイズ未満のオブジェクトに kmalloc を使うのが良い習慣だと述べています
- ・slab 層は自前でメモリを作るわけではなく、下のバディアロケータからページを買って切り分けます
カーネルのメモリ確保は1段ではありません。下段のバディアロケータがページを配り、その上に載った slab 層が小さなオブジェクトを配ります。
② バディアロケータは2の冪でしか配らない
free_area[] 配列各要素が1つの order に対応する
order ごとに空き塊のリストを持つ
order 01ページ = 4KiB
order 12ページ = 8KiB
order 24ページ = 16KiB
order 38ページ = 32KiB
以降も倍々で続く
order 9512ページ = 2MiB
order 101024ページ = 4MiB
- ・kernel.org の Physical Memory は free_area を「各要素が2の冪である特定の order に対応する空き領域の配列」と説明しています
- ・proc_buddyinfo(5) は塊の大きさを (2^order) * PAGE_SIZE と定義しています
- ・追跡する order の上限はカーネルの構成で決まります。x86-64 の一般的な既定では buddyinfo に order 0〜10 の11列が並びます
バディアロケータは任意のバイト数を配りません。ページ数が2の冪の塊だけを扱い、order という指数で管理します。
③ 大きい塊しかないときは半分に割る
要求: order 1(8KiB)だが order 1 のリストは空
足りる中で最小の塊を探す
order 3 の塊が1つある32KiB の連続ページ
半分に割る(分割)
order 2 の片割れ16KiB → order 2 のリストへ返す
order 2 のもう片方さらに割る
足りるところまで割り続ける
order 1 の片割れ8KiB → order 1 のリストへ返す
order 1 のもう片方これを要求元に渡す
- ・kernel.org の Physical Memory は、十分な大きさの最小の塊を探し、それが要求より大きければ必要なサイズになるまで再帰的により小さな塊へ分割すると説明しています
- ・分割で余った片割れは捨てずに、対応する order の空きリストに登録されます
- ・32KiB を2つに割ると16KiB が2つ、その片方をさらに割ると8KiB が2つになります
ちょうどの大きさがなければ、足りる中で最小の塊を見つけて半分ずつに割っていきます。余りは捨てずに下の order の空きリストへ戻ります。
④ 解放時は相方(buddy)と結合して戻る
order 1 の塊を解放使い終わった8KiB
同じ order の相方の状態を見る
相方(buddy)も空いている元は1つの order 2 だった対
相方が使用中結合できない
空いていれば結合、使用中ならそこで止まる
order 2 の塊として合体order 2 のリストへ移動
order 1 のまま空きリストへ
合体した側はさらに上を試す
order 3 の相方も空いていれば再び合体上へ上へと繰り返す
- ・kernel.org の Physical Memory は、ページが解放されるとその buddy と結合してより大きな塊を形成することがあると説明しています
- ・buddy とは、同じ親の塊を2分割したときの「もう片方」を指します。任意の隣接ページではありません
- ・結合は1段で終わらず、上の order でも相方が空いていれば連鎖的に続きます
解放は分割の逆です。相方が空いていれば合体して上の order へ戻り、連鎖できるところまで登ります。
⑤ なぜこの設計なのか — 外部断片化を抑える
問い: なぜ2の冪と結合にこだわるのか
結合しない場合
空きはあるのに連続していない小さな空きが散らばる
外部断片化大きな連続領域の要求が失敗合計空き容量は足りているのに
buddy 方式で結合する場合
相方の位置が計算で分かる探索せずに結合相手を特定できる
空きが自動的に大きな塊へ育つ高い order が復活する
ただし代償もある
要求が2の冪でないと切り上げ5ページ要求 → order 3(8ページ)
内部断片化- ・proc_buddyinfo(5) は、メモリが激しく断片化していると高い order のカウンタがゼロになり、大きな連続領域の確保が失敗すると述べています
- ・塊は常に2の冪のページ数で境界も揃うため、相方の位置をページ番号から導けます。総当たりで探す必要がありません
- ・切り上げによる無駄は内部断片化として残ります。これが次の slab 層が必要になる理由です
2の冪に限定するのは制約ではなく、結合相手を計算で特定するための設計です。その代わり切り上げの無駄が残ります。
⑥ slab / SLUB がページを敷き詰める
問題: 32バイトの struct に4KiBは無駄すぎるバディの最小単位は1ページ
slab 層がページをまとめ買いする
kmem_cache同一サイズ・同一種類の専用キャッシュ
kmem_cache_create() で用意買ったページを等分に区切る
obj32B
obj32B
obj32B
…以降も同サイズで並ぶ
確保・解放はこの中で完結する
空きオブジェクトを1個渡すだけバディまで降りずに済む
- ・カーネル公式の Memory Allocation Guide は、同一のオブジェクトを多数確保する場合に slab キャッシュを使い、使用前に kmem_cache_create() でキャッシュを用意するとしています
- ・同じサイズだけを詰めるので、どの空き位置も次の要求にそのまま使えます
- ・確保のたびにページを割る必要がないため、頻繁な確保・解放が安価になります
slab 層はページをまとめ買いし、同一サイズのオブジェクトで敷き詰めます。以後の確保はページ分割を伴わず、キャッシュ内で完結します。
⑦ 2つの層をそのまま観測する
下段を見る: /proc/buddyinfoorder ごとの空き塊の個数
上段を見る: /proc/slabinfoキャッシュごとのオブジェクト状況
buddyinfo の読み方
Node と Zone を示す行行ごとに1つのメモリ領域
左から order 0, 1, 2 … の列列番号が order そのもの
塊の大きさは (2^order) * PAGE_SIZE右側の列がゼロに寄ったら
連続領域が枯れている合図高い order から順に確保できなくなる
断片化- ・proc_buddyinfo(5) は「order は列番号に一致する(ゼロから数え始めた場合)」と明記しています
- ・proc_buddyinfo(5) は、断片化が激しいと高 order のカウンタがゼロになり大きな連続領域の確保が失敗するとしています
- ・slabinfo(5) によれば /proc/slabinfo を読めるのは root だけです
2つのファイルが2つの層にそのまま対応します。buddyinfo は下段の連続領域の余力を、slabinfo は上段のオブジェクト側の消費を映します。