【メモリ割付】
SBCLではメモリの割付はリージョンを通して行うというのは昨日書いた。それをすると何がうれしいかという話である。
たとえばBoehm GCではメモリは要求サイズをフリーリストから取ってくる。もちろん実際にはもっと最適化されていて、(記憶が正しかったら)8、16、24、といった感じでよく使われる小さいオブジェクトと大きいオブジェクトで別に管理している。っで、8バイトなら8バイト領域のフリーリストから取ってくるのでメモリがフィットするかどうかを調べる必要がないといった感じ(だったはず)。
では、SBCLではどうか？多くのコピーGCと同じくメモリの割付は先頭メモリのポインタを返すだけである。なので(おそらく)高速に動く。もちろん、ページ単位でメモリの割付を行うのでリージョンが管理しているアドレスの末尾を超えるようなサイズのチェック等はある。
実際に割付のコードを見てみよう。 (
src/runtime/gencgc.cより、一部整形及び削除)
static inline lispobj *
general_alloc_internal(sword_t nbytes, int page_type_flag, struct alloc_region *region,
struct thread *thread)
{
void *new_obj;
void *new_free_pointer;
os_vm_size_t trigger_bytes = 0;
if (nbytes > large_allocation)
large_allocation = nbytes;
/* maybe we can do this quickly ... */
new_free_pointer = region->free_pointer + nbytes;
if (new_free_pointer <= region->end_addr) {
new_obj = (void*)(region->free_pointer);
region->free_pointer = new_free_pointer;
return(new_obj); /* yup */
}
:
/* 削除 (GC起動用コード)*/
:
new_obj = gc_alloc_with_region(nbytes, page_type_flag, region, 0);
return (new_obj);
}
/* Allocate bytes. All the rest of the special-purpose allocation
* functions will eventually call this */
void *
gc_alloc_with_region(sword_t nbytes,int page_type_flag, struct alloc_region *my_region,
int quick_p)
{
void *new_free_pointer;
if (nbytes>=large_object_size)
return gc_alloc_large(nbytes, page_type_flag, my_region);
/* Check whether there is room in the current alloc region. */
new_free_pointer = my_region->free_pointer + nbytes;
if (new_free_pointer <= my_region->end_addr) {
/* If so then allocate from the current alloc region. */
void *new_obj = my_region->free_pointer;
my_region->free_pointer = new_free_pointer;
/* Unless a `quick' alloc was requested, check whether the
alloc region is almost empty. */
if (!quick_p &&
void_diff(my_region->end_addr,my_region->free_pointer) <= 32) {
/* If so, finished with the current region. */
gc_alloc_update_page_tables(page_type_flag, my_region);
/* Set up a new region. */
gc_alloc_new_region(32 /*bytes*/, page_type_flag, my_region);
}
return((void *)new_obj);
}
/* Else not enough free space in the current region: retry with a
* new region. */
gc_alloc_update_page_tables(page_type_flag, my_region);
gc_alloc_new_region(nbytes, page_type_flag, my_region);
return gc_alloc_with_region(nbytes, page_type_flag, my_region,0);
}
前提条件として要求サイズは8の倍数(src/runtime/alloc.cで切り上げられる)である必要がある。gc_alloc_internalを見ると分かるが、要求されたサイズが末尾アドレスを超えない場合は先頭アドレスを返し、末尾アドレスを増やす。超える場合は新たにリージョンの割付を行い、やはり先頭アドレスを返す(gc_alloc_with_region)。Boehm GCと違いSBCLではヒープから割り付けられるオブジェクトはLispオブジェクトのみと割り切っている(はずな)ので、メモリはヘッダ情報等を持つことはない。 逆に、
consを除く全てのオブジェクトはヘッダ情報を持っていて、そこからオブジェクトのサイズ等を割り出すことが可能である(はず、自信ない・・・)。まぁ、メモリの割付なんてそう面白いところはないので、適当に切り上げて次へ(逃走ともいう)。
【GC】
さて、ようやく本題のGCである。SBCLではGCの起動方法は2種類あって、ユーザーが直接Lisp手続きの
gcを叩くのと、リージョンの使用メモリがトリガーバイト以上になった際に勝手に起動されるのの2種類である。(前者しか用意されてなかったらGCじゃないわね・・・)では、GC起動の大まかな流れを見てみよう。流れとしては以下のようなフローになる。
- メモリ割付時に
*gc-pending*フラグにtをセットする - ついで擬似アトミックに割り込みフラグをセットする
- 割付終了後、擬似アトミックの割り込みをチェック
- 割り込みがあれば割り込みを処理させる
- 割り込みはCPU割り込みで実現される(int3もしくはud3命令)
- 使ってないスタックをきれいにする
- 世界を止める
- SBCLではincrementalマーキングとか、mostly concurrent GCとか軟弱なものはなく、漢らしくGCの間世界には止まってもらう
- ごみ集めする
- 基本的には第一世代のみを行うが、必要(次の世代もメモリが足りない)ならば以降の世代も行う
- 明示的にどの世代をGCするかの指定も可能
*gc-pending*にnilをセットする- 世界を動かす
- ファイナライザを起動させる
SBCLのファイナライザはLisp側で実装されていて、起動時にはGCが起きないようになっている(
src/code/final.lisp参照)。世界を止めるのはマルチスレッドでは重要だけど、今回はシングルスレッドの流れを追っているので深くは言及しないが、pthread_killでUSR2(内部でGC用シグナルとして定義)を送りスレッドを止めている。開始はその逆。わざわざシグナルを使っているのは、標準POSIXのpthreadではサスペンドがサポートされていないことと、Linuxのpthreadには拡張としてのpthread_suspend_npに対応するものがないことだと思われる。(Windows、*BSDとかだとスレッドのサスペンドが可能)。
【ルートマーキング】
SBCLにおいてGCルートと考えられているのは2つ、スタックとレジスタである。 マーキングは非常にシンプルで、スタックの底から現在のスタックポインタまでにあるヒープ領域に取られたLispオブジェクトもしくはコード(マシンコード)っぽいものを保存する。レジスタ上でも一緒。スタックの底は
pthread_attr_getstackで取得(Windows除く)。実際に何をするかと言えば、ルート上にあるそれっぽいオブジェクトが所属するページ丸ごとピン止めするのである。ページは最低でも4096バイトあるので、ある意味漢らしい。まぁ、いろいろ考えるよりは楽だわね。(詳細は
src/runtime/gencgc.cにあるpreserve_pointerを参照)タイムオーバーなので今日はこのくらいで。続きはまた明日。
No comments:
Post a Comment