BitVisorのヒープ領域とその確保・解放の仕組みおよびAPIについて簡単に紹介します。🎅🎄

ヒープ領域のアドレス

BitVisorは初期化時に4MiBアラインメントで128MiB以上のサイズの連続する物理アドレスを予約して使用します。対応する仮想アドレスは0x40000000からの128MiBになります。ここに、プログラムとしての.text, .data, .bssセクションと、ヒープが含まれます。

BIOS環境の場合は、最初は物理アドレス1MiBからの領域で起動し、途中でメモリーマップを取得して上位アドレスに自分自身を移動させます。1MiBにロードされる理由は、GNU GRUB Multiboot Specificationに沿って固定アドレスにロードさせているためで、上位アドレスに移す理由は、Linuxなどのオペレーティングシステムが同じ領域を使うためです。また、古いBIOSのインターフェイスでは、細かいメモリーマップが提供されず、メモリー容量のみが提供されていましたので、そのような古いインターフェイスを用いるシステムで、容量を減らして見せるには上位アドレスに常駐する必要があります。アラインメントとメモリーマップを偽装する処理の単純化のため、予約する領域が128MiBを超えることがあります。

UEFI環境の場合は、BitVisorの先頭64KiBに含まれるプログラムで上位アドレスを確保し、そこに先頭64KiBはコピーされ、残りは直接読み込まれます。UEFI環境では、上位アドレスを探して確保しているのはファームウェアのほうで、BitVisorとしては、下位4GiB未満から約132MiB (アラインメント調整分を含む) を割り当ててくれ、と、そういう呼び出しをしているだけです。また、アラインメント調整で余った分もちゃんと解放していますので、BIOS環境よりも無駄がありません。

なぜ下位4GiB未満を使用するのかというと、32ビットアドレス指定にしか対応していないデバイスに対応するためです。

確保・解放のAPI

プロトタイプ宣言についてはinclude/core/mm.hを見てください。

ページ単位

alloc_pages()関数は、第三引数の数のページ (4KiB/ページ) を割り当て、その仮想アドレスおよび物理アドレスをそれぞれ第一引数と第二引数が指す変数に格納します。0を返します。アラインメントは確保するサイズ以上の最小の2のべき乗のページ数と同じになります。

alloc_page()関数は、第三引数を1にしたalloc_pages()関数と同じです。

free_page()関数は、alloc_pages()関数等で確保したページを解放します。引数は仮想アドレスです。複数ページ確保されていた場合、確保された時と同じ単位でまとめて解放します。

free_page_phys()関数は、free_page()関数の引数を物理アドレスにしたものです。

バイト単位

alloc()関数は、引数のバイト数を割り当て、その仮想アドレスを返します。アラインメントは確保するサイズ以上となる最小の2のべき乗のバイト数と同じになります。ただし最小16バイトアラインメントとなります。

alloc2()関数は、alloc()関数と同様に割り当て、第二引数が指す変数に物理アドレスを格納します。BitVisor 1.0.1で登場しました。

realloc()関数は、alloc()関数等で確保された領域のサイズ変更を行います。第一引数が割り当てられている仮想アドレスで、第二引数が新しいバイト数になります。大きめに割り当てられている場合があるため、サイズを増やしてもアドレスが変わらないことがあります。BitVisor 0.8で登場しました。

free()関数は、alloc()関数等で確保された領域を解放します。引数は仮想アドレスです。

alloc()関数、free()関数、および、realloc()関数は、保護ドメイン (プロセス機能) でも提供されています。保護ドメインではアラインメントが異なります。おそらく4バイトアラインメントです。

メモリープール

メモリープールは、特定の用途に使う領域をページ単位で区別できるようにするためのものです。これには、保護ドメインとのやり取りに使う領域がページより小さい単位で確保されていても、他の用途のデータがもれないようにする目的があります。また、解放時にいくつかをキープしておくことで、積極的に同じ領域が再利用されるようにし、キャッシュ効率を高める狙いもあります。小さな単位での割り当ても可能です。BitVisor 1.1で登場しました。

mempool_new()関数は、メモリープールを作成します。第一引数はブロックサイズ、第二引数は何個キープするか、第三引数は確保時に領域をクリアするかどうかを指定します。

mempool_free()関数は、メモリープールを解放します。

mempool_allocmem()関数は、メモリープールから領域を割り当てます。

mempool_freemem()関数は、メモリープールに領域を返します。

確保・解放の仕組み

ページ単位

上に書いたように128MiBの領域をBitVisor全体として確保しています。これはページ数にすると128MiB/4KiB=128*1024KiB/4KiB=32*1024=32768ページになります。これを、struct pageの配列で管理しています。

各ページには、free, not_head, allocated, reservedの4つのタイプがあります。freeは、解放されたページです。not_headは、複数ページをまとめて確保・解放する場合の先頭以外のページを表します。allocatedは確保されたページです。reservedは、プログラムで使用しているページです。

初期化時はまず全体をreservedとして1ページずつ確保した状態にします。次に、BitVisorのプログラム以外の部分を解放していきます。解放時に、隣り合った同サイズの領域も解放されていたら、連結してまとめます。この時、複数ページは必ずそのサイズのアラインメントになるようにします。

1ページ: 2^12バイト: アドレスの下位12ビットが0
2ページ: 2^13バイト: アドレスの下位13ビットが0
4ページ: 2^14バイト: アドレスの下位14ビットが0
...

このように2のべき乗単位のページ数で扱います。最大2^(12+12)バイト、すなわち、16MiBまで連結されます。たぶん。

解放されたページのstruct pageのポインターは、サイズごとに線形リストlist1_freepage[]で管理されます。確保の時は目的のサイズの線形リストから取り出して割り当て状態とします。目的のサイズのリストが空の場合は、その倍のサイズのリストから取り出して2分割します。そこにもない場合はさらにその倍の... と繰り返していくことで割り当てを行います。

解放の時はアドレスから32768ページ分の番号に変換することで、struct pageのポインターを得て、リストに突っ込みます。

このように、ページ単位の確保・解放には線形探索の要素はなく、比較的高速に動作するはずです。

バイト単位

バイト単位の確保・解放処理ですが、結構シンプルな実装になっています。まず、1025バイト以上の割り当てはページ単位の割り当てになります。つまり1025バイト確保すると4096バイトが割り当てられます。このような確保ではアドレスの下位12ビットは必ず0となります。

1024バイト以下の割り当ての場合、以下の単位で割り当てを行います。

16バイト
32バイト
64バイト
128バイト
256バイト
512バイト
1024バイト

例えば257バイトの割り当てを行うと、512バイトが割り当てられます。

この割り当ては、1ページを確保しその中を各バイト数で分割することで行われます。ページの先頭に割り当て情報をビットマップで保持し、残りが割り当てられる領域となります。そのため、このような確保ではアドレスの下位12ビットが0になりません。

もっとも大きな1024バイト単位の場合、4096バイトの1ページ中に3つの領域が確保できます。ビットマップは4つ分になり、先頭のひとつは常時確保された状態となります。

もっとも小さな16バイト単位の場合、4096バイトの1ページ中に... 4096/16=256個となり、ビットマップも256ビット、すなわち32バイトが必要ですし、それに加えてリスト構造用のポインターと、確保サイズを示す1バイトが必要ですので、おそらく、先頭の4つ分くらいが常時確保された状態となり、残りの252個が確保できることになりそうです。

割り当て情報のアドレスは、サイズごとにalloclist[]というリストで管理されますが、各ビットマップはリスト管理にはなっておらず、線形探索です。決して性能の良いものではありません。

解放の場合はアドレスの下位12ビットを見て、0の場合はページ単位の解放を行います。0以外の場合はビットマップを変更して、必要に応じてリストに追加し、解放とします。連続領域が解放されても、各サイズ用に割り当てたページ単位の領域が解放されることはありません。

バイト単位 (保護ドメイン)

保護ドメインのメモリー確保・解放処理はとてつもなく単純です。保護ドメインのヒープは単なる配列から取られます。int heap[100], heaplen=100のようにグローバル変数として宣言しておくと、それがヒープとなります。Unixのbrkシステムコールのように、保護ドメインのメモリーを動的に増やすシステムコールはありません。

で、構造は、領域の最後から手前にたどっていく線形探索を確保と解放で行います。確保済みの領域の最後には正の数、解放済みの領域の最後には負の数で領域のバイト数が入れられています。これを線形探索で探して、空き領域を見つけたり、確保済みの領域を見つけたりしています。性能はお察しください。

メモリープール

メモリープール作成の際に指定するブロックサイズは、2のべき乗のページ単位に切り上げられます。で、確保の際は空きがなければこのページ単位での割り当てが行われます。そして、そこから確保される領域と空き領域は連続する部分のオフセットとバイト数で線形リストに保持されます。

確保・解放は線形探索にはなりますが、連続する部分はひとつにまとめられているので数は少なくなります。また、ブロックごとにリストが分かれているので、どのブロックに属しているかは線形探索となりますが、関係のないブロックのリストまでたどることはありません。

現状、保護ドメインとのやり取りの際に無関係のデータがアクセスされないようにする目的以外では使用されていません。

メモリー不足

保護ドメイン (プロセス) でのメモリー不足は、あらかじめ用意しておいたheap[]配列を使い果たしたということで、この時には単にpanic in process: out of memoryが出力されてプロセス終了となります。用途次第でこの出力が見えるかどうかもわかりませんが、とにかく、保護ドメインではこれ以上の処理はありません。

それ以外のVMM内メモリー不足の際は、以下の記事にあるように、Assertion failed!(n < NUM_OF_ALLOCSIZE) が出ます。

Hyper-Threading有効時にBitVisorが起動しない原因を特定してみる - Qiita
http://qiita.com/lti0/items/4025e297014517108af0

バイト単位での割り当てもページ単位で割り当てたところから細かく割り当てていくので、足りない場合は必ずページ単位の割り当てに落ちてきます。さらに、1ページ単位が余っていない場合は2ページ単位、それもなければ4ページ単位と、倍々ゲームになっていき、最後は上のassertion failedでpanicとなります。

さて、panicの際はデフォルトではshellを起動するか再起動するかというメッセージが出る仕掛けになっています。shellを起動すればログの確認やメモリーダンプなどが行えるというわけなのですが、メモリー不足が原因のpanicでは何かやろうとしてもまたメモリー不足ということになり、大変厳しい事態となることが考えられます。そのための緊急用関数が、core/mm.cに用意されています。以下の2つです。

mm_force_unlock()
mm_free_panicmem()

これらはpanicの際にメッセージを出すプロセスに実行を移す前に呼び出されます。mm_force_unlock()関数は、メモリー関係のスピンロックを全部アンロックしてしまうもので、これによってデッドロックを回避します。mm_free_panicmem()関数は、起動時に予約してあったNUM_OF_PANICMEM_PAGES (256) ページ=1MiBのメモリーを解放します。これによって手に入った最後の1MiBが、デバッグ用のログ確認等に使われることになります。

ただし、この処理が実行される段階ですべてのコアがpanicしたとは限らないため、最後の1MiBが手に入った後に他のコアでメモリーを確保するような処理が走ってしまって、本当にメモリーがなくなってしまうこともあるかも知れませんので、できるだけメモリー不足にはしないようにするのがおすすめです。

空きメモリーの確認

空きメモリーを確認するためのAPIとしてnum_of_available_pages()関数がcore/mm.cに用意されています。これは、ページ単位の割り当てが残り何ページあるかをカウントして返すものです。空きメモリーの状況に応じて動作を変えるようなプログラムに使えるほか、各種開発やメモリーリークのデバッグ用にdbgshやpanic時のshellからも確認することができるようになっています。以下のコマンドを実行すると、ログに空きメモリー容量が出力されます。

> sendint
sendint> free
send 0 to free

名前の謎

malloc/freeが一般的なCのAPIですが、なぜalloc/freeなのでしょうか。理由はわかりませんが、そういえばWindows APIではGlobalAlloc/GlobalFreeといった名前が使われていましたので、それに近い雰囲気のつもりなのかも知れません。