詳解SBCL - 世代別GC(3)

昨日はルートのマーキングまで書いたので、今日はいよいよ実際にオブジェクトを動かすところ、つまりSBCLの世代別GCの肝の部分に触れていこう。

【scavenge】
この処理がすべての処理の鍵であるといってもまぁ、過言ではないだろう。とりあえず中身を見ていこう。(src/runtime/gc-common.cより、一部整形及び削除)

void scavenge(lispobj *start, sword_t n_words)
{
    lispobj *end = start + n_words;
    lispobj *object_ptr;
    sword_t n_words_scavenged;

    for (object_ptr = start; object_ptr < end; object_ptr += n_words_scavenged) {

        lispobj object = *object_ptr;

        if (forwarding_pointer_p(object_ptr))
            lose("unexpect forwarding pointer in scavenge: %p, start=%p, n=%l\n",
                 object_ptr, start, n_words);

        if (is_lisp_pointer(object)) {
            if (from_space_p(object)) {
                /* It currently points to old space. Check for a
                 * forwarding pointer. */
                lispobj *ptr = native_pointer(object);
                if (forwarding_pointer_p(ptr)) {
                    /* Yes, there's a forwarding pointer. */
                    *object_ptr = LOW_WORD(forwarding_pointer_value(ptr));
                    n_words_scavenged = 1;
                } else {
                    /* Scavenge that pointer. */
                    n_words_scavenged =
                        (scavtab[widetag_of(object)])(object_ptr, object);
                }
            } else {
                /* It points somewhere other than oldspace. Leave it
                 * alone. */
                n_words_scavenged = 1;
            }
        } else if (fixnump(object)) {
            /* It's a fixnum: really easy.. */
            n_words_scavenged = 1;
        } else {
            /* It's some sort of header object or another. */
            n_words_scavenged =
                (scavtab[widetag_of(object)])(object_ptr, object);
        }
    }
    gc_assert_verbose(object_ptr == end, "Final object pointer %p, start %p, end %p\n",
                      object_ptr, start, end);
}

与えられたstartの中身を順番に見ていき、Lispオブジェクトでかつ既に移動されたものならば移動先に置き換える、まだならscavtabテーブルに格納された実際の処理に処理を委譲する。*object_ptrが何を指すのか今一理解できなくて、SBCLのGCはどう動いているのだろうなんて疑問に思ったのは秘密である(well if you have read my articles or twitter, you know...)。ここで、ポイント(と僕が思う部分)は与えられたstartは必ずヒープ領域を指すことだろう。また、特に何もしなくてもオブジェクトの割り付けられたメモリ境界を指すということだ。これは、scavengeが呼ばれる部分を見れば分かるのだが、事前にページもしくはリージョンの開始位置を計算しているのと、割り付けられたオブジェクトの位置を直接渡していることに起因する。詳しくはsrc/runtime/gencgc.cにあるgarbage_collect_generationを参照されたい(多分後で多少触れるけど)。

ではscavtabには何が入っているのだろうか？

この辺は実は非常に読みやすくて、scav_のプリフィックスがついた関数がsrc/runtime/gc-common.cにある。それらを眺めればどの処理がどのオブジェクトに対応しているのか大体わかるという寸法。実際の振り分けは、widetag_ofが適切にオブジェクトからタグを取り出すのでそれにしたがっている。また、テーブルの設定も同様に行われる。タグが255もあるのでテーブルの設定はすごく長い処理になっているのはまぁご愛嬌だろう(src/runtime/gc-common.cのgc_init_tables参照)。

とりあえず、一つ中身を見てみよう。Lispといえばでリストを見る。

static sword_t scav_list_pointer(lispobj *where, lispobj object)
{
    lispobj first, *first_pointer;

    gc_assert(is_lisp_pointer(object));

    /* Object is a pointer into from space - not FP. */
    first_pointer = (lispobj *) native_pointer(object);

    first = trans_list(object);
    gc_assert(first != object);

    /* Set forwarding pointer */
    set_forwarding_pointer(first_pointer, first);

    gc_assert(is_lisp_pointer(first));
    gc_assert(!from_space_p(first));

    *where = first;
    return 1;
}

処理としては非常に簡単で、与えられたリストobjectをtrans_listでコピー、その後whereが指すポインタと入れ替える。trans_listはリストの指すcarとcdrを単にコピーしているだけで、その中身までは見ない(コード貼り付けると無駄に長くなるので割愛)。これによってリニアタイムの処理になる。

では、リストの中身が指すポインタは一体誰が救うのか？

ここまで読んでいれば勘のいい人は既に分かっているだろうが、scavengeである。実際にscavengeは以下の3つの段階で呼ばれる。

1. 割り込みハンドラ、バインディングスタック及びSBCLの静的領域の回収
2. GC対象外の世代の回収
3. 新しい世代の回収

の3つである。ものすごく簡単に言えば、GC対象のヒープ領域以外のヒープをすべて回収し、GC対象の領域でピン止めされたページ以外はごみとするという感じである。

これで大まかなSBCLのGCの流れは終了。書き忘れたこととかあるかな？

今日はここで時間切れ。Genesisについては明日触れることにする。