**ベビーの第二のガーベジコレクタ**

ガーベジコレクションとは？
メモリはどのように言語で確保されるのか？

プログラミング初心者が抱える、非常に混乱した疑問。

2013 年、13 年前に Baby’s First Garbage Collector（ファースト・ガーベジコレクタ） が誕生しました。
今では大人になり、浅い子ども用プールとパドルを離れ、思春期へ進み、すぐに大学へ行くというような、成長の速さを実感します。

Bob Nystrom は Baby’s First Garbage Collector が本当にゴミを拾うと言っていました。
そのバージョンは私の動的言語 lone lisp でも実際に搭載されており、今も同じく存在しています。
さらに、彼は「高位神々との交信」についても冗談ではなかったと述べています。私は魔法レベルが上昇しているのを感じます――ウィザードの世界に近づいています。

Baby’s First Garbage Collector は出発点です。
そこで止まることはなく、実際にサポートする言語に合わせて進化し、最終形態―究極の偉大なガーベジコレクタへと成長していく予定です。
その道程を記録するのもまた素晴らしいことです。

---

原始的領域でのトラブル

Baby’s First Garbage Collector は「正確（precise）」ガーベジコレクタです。
オブジェクトがどこにあるか常に把握し、監視し、世界停止して即座に回収します。
その精度と自動化は、オブジェクトが逃げる余地を与えません。

しかし、やがて抵抗勢力が形成されました。
オブジェクトたちはガーベジコレクタの支配から解放されたいと願い、スタックを抜け出す方法を探し始めます。

LONE_LISP_PRIMITIVE(run_objects_run)
{
    struct lone_lisp_value object;
    object = lone_lisp_machine_pop_value(lone, machine);
    /* freedom */
}

これでオブジェクトは一時的に自由になりますが、ガーベジコレクタは生まれた瞬間から追跡データを埋め込んでいます。
「カウント」リストを保ち、いつでも再び捕捉できるようになっています。

ガーベジコレクタはすべてのオブジェクトに対して行動しますが、実際には ゴミ とみなされたものだけです。
逃げたオブジェクトは「ゴミ」と見做され、再び追跡されます。

しかし、ガーベジコレクタは全てを網羅できるわけではありません。
プライベート領域や魔法の隙間など、チェックできない場所が存在します。
その結果、重要なオブジェクトが失われ、プログラム自体が崩壊する恐れがあります。

---

地下界への旅

ガーベジコレクタを創造した高位神々はこの事態を受け入れられませんでした。
彼らは進化を強制し、失われた子どもたちを探し回復させるために、**地下界（ネザー）**へと足を踏み入れました。

ダークマジシャンたちは自ら地下界へ挑み、機械にその任務を教えることが可能だと判断しました。
ガーベジコレクタは「根」（roots）を検索し、見つからなければオブジェクトを回収します。

Lisp スタック

プログラムの実行中、値は一時停止状態で保存され、後で必要になったときに復元されます。
スタックから抜け出すことで動的社会に混乱が生じます。

ネイティブスタック

地下界にも独自のスタックがあります。
これは Lisp スタックに似ていますが、極めて異なります。
このスタックを理解する必要はなく、オブジェクトだけを探すことです。

フレームアドレスの取得

long lone(int argc, char **argv, char **envp,
          struct lone_auxiliary_vector *auxv)
{
    void *stack = __builtin_frame_address(0);
    /* interpreter runs... */
    return 0;
}

この「禁断の呪文」により、スタックポインタが決定されます。

根のマーク

static void lone_lisp_mark_native_stack_roots(struct lone_lisp *lone)
{
    lone_lisp_mark_native_stack_roots_in_range(
        lone,
        lone->native_stack,
        __builtin_frame_address(0));
}

ポインタが 2 のべき乗で揃っていることを確認し、ネイティブスタックの内容を再解釈します。

static void lone_lisp_mark_native_stack_roots_in_range(
    struct lone_lisp *lone, void *bottom, void *top)
{
    void *tmp, **pointer;
    if (top < bottom) {
        tmp = bottom; bottom = top; top = tmp;
    }
    for (pointer = bottom; pointer < top; ++pointer) {
        if (lone_lisp_points_to_heap(lone, *pointer)) {
            lone_lisp_mark_heap_value(lone, *pointer);
        }
    }
}

完全ではありませんが、十分に機能します。
ネイティブスタックはしばしば「幻影」を与えますが、実際のオブジェクトを誤って残すことはありません。

---

ヒープポインタ

ガーベジコレクタはヒープ内の値を検査します。
全ての Lisp 値ポインタを再帰的に追跡する必要はなく、ヒープセグメント全体を調べれば十分です。

struct lone_lisp_heap {
    struct lone_lisp_heap *next;
    struct lone_lisp_heap_value values[LONE_LISP_HEAP_VALUE_COUNT];
};

ポインタがヒープ内にあるかどうかをチェックする関数は以下の通りです。

static bool lone_points_within_range(void *pointer, void *start, void *end)
{
    return pointer >= start && pointer < end;
}

static bool lone_lisp_points_to_heap(struct lone_lisp *lone, void *pointer)
{
    struct lone_lisp_heap *heap;
    for (heap = lone->heaps; heap; heap = heap->next) {
        if (lone_points_within_range(pointer,
                                     heap->values,
                                     heap->values + LONE_LISP_HEAP_VALUE_COUNT)) {
            return true;
        }
    }
    return false;
}

これにより conservative（保守的）ガーベジコレクションが実現されます。

---

サメの攻撃

テストスイートを走らせると、Lisp の世界は大混乱。
オブジェクトはランダムに別のものへ変わり、デバッガで追跡できなくなります。

何かが足りないことを示す唯一の手掛かりは レジスタ です。

レジスタのスパイリング

Garbage Collector は

GC_with_callee_saves_pushed

を使用して、レジスタをスタックに退避させます。
その実装例は以下の通りです（x86_64 と AArch64 のアセンブリ）：

x86_64

typedef long lone_registers[16];
extern void lone_save_registers(lone_registers);

__asm__
(
    ".global lone_save_registers"            "\n"
    ".type lone_save_registers,@function"    "\n"
    "lone_save_registers:"                   "\n"
    "mov %rax,   0(%rdi)"                    "\n"
    /* ... */
    "mov %r15, 120(%rdi)"                    "\n"
    "ret"                                    "\n"
);

AArch64

typedef long lone_registers[31];
extern void lone_save_registers(lone_registers);

__asm__
(
    ".global lone_save_registers"            "\n"
    ".type lone_save_registers,@function"    "\n"
    "lone_save_registers:"                   "\n"
    "stp x0,  x1,  [x0, #0 ]"               "\n"
    /* ... */
    "str x30,      [x0, #240]"              "\n"
    "ret"                                    "\n"
);

レジスタのマーク

static void lone_lisp_mark_all_reachable_values(struct lone_lisp *lone,
                                                struct lone_lisp_machine *machine)
{
    lone_registers registers;
    lone_save_registers(registers);   /* スタックへ退避 */

    lone_lisp_mark_known_roots(lone);
    lone_lisp_mark_lisp_stack_roots(lone, machine);
    lone_lisp_mark_native_stack_roots(lone);
}

テストが終了すると、失われた子どもたち（オブジェクト）がすべて見つかり、Lisp の世界は平和を取り戻します。

---

まとめ

• Baby’s First Garbage Collector は正確なガーベジコレクタとして始まりましたが、現実のプログラムに合わせて進化し続けています。
• ネイティブスタックとヒープ内ポインタを効率的に検査することで conservative ガベージコレクションを実装しています。
• レジスタの退避（スパイリング）も重要で、これにより「サメ攻撃」などの予期せぬオブジェクト変化を防止します。

次回は、ガーベジコレクタが自らの部屋（内部状態）をきれいに保つ方法について掘り下げます。