1. メモリ管理とGCの必要性

プログラムは実行中に、必要になったぶんだけメモリを確保し、不要になったら 手放しながら動きます。この「確保」と「解放」をどう扱うかが、本書のすべて の出発点です。この章では、まず手動でメモリを管理するとは何をすることなの か、そこにどんな落とし穴があるのか、そして ガベージコレクション （GC）がなぜ生まれたのかを整理します。

1.1 スタックとヒープ：メモリはどこから来るのか

プログラムが使うメモリは、大きく スタック (stack) と ヒープ (heap) に分けて考えられます。

スタックは、関数呼び出しに対応して自動的に伸び縮みする領域です。関数に 入るとローカル変数のための場所が積まれ、関数から戻ると自動的に取り除か れます。確保も解放もコンパイラが面倒を見てくれるので、プログラマは普段 意識しません。

問題はヒープです。ヒープは、関数の寿命とは無関係に、好きなタイミングで 確保し、好きなタイミングで解放できる領域です。たとえば「ユーザーが入力 した行数ぶんの配列」のように、コンパイル時には大きさも寿命もわからない データはヒープに置きます。この自由さの代償として、いつ解放するかを 誰かが決めなければなりません。

C言語では、これをプログラマが手で行います。

#include <stdlib.h>

char *buf = malloc(1024);   /* ヒープから 1024 バイト確保 */
/* ... buf を使う ... */
free(buf);                  /* もう使わないので解放 */

malloc で確保し、free で解放する。一見単純ですが、この「もう使わない」 という判断をプログラム全体で正しく行い続けるのは、驚くほど難しいのです。

1.2 手動メモリ管理の3つの落とし穴

手動でメモリを管理するとき、典型的に3種類のバグが発生します。これらは GC が解こうとしている問題そのものなので、しっかり押さえておきましょう。

1.2.1 メモリリーク：解放し忘れる

確保したメモリを free し忘れると、そのメモリは二度と再利用されません。 プログラムが動き続けるうちに使用メモリが膨らみ、やがて枯渇します。これを メモリリーク (memory leak) と呼びます。

void leak(void) {
    char *p = malloc(100);
    /* p を free しないまま関数が終わる → 100 バイトが永久に迷子になる */
}

リークは「クラッシュしない」ぶん厄介です。テストでは気づかれず、長時間 稼働するサーバーで初めて顕在化する、といったことがよく起こります。

1.2.2 ダングリングポインタ：早く解放しすぎる

逆に、まだ使っているメモリを free してしまうと、そのメモリを指していた ポインタは無効な場所を指す ダングリングポインタ (dangling pointer) になります。解放済みメモリを読み書きすると、運が よければクラッシュ、運が悪ければ別のデータを静かに破壊します。

char *p = malloc(100);
free(p);
p[0] = 'x';   /* 解放済みメモリへの書き込み（use-after-free） */

この「use-after-free」は、セキュリティ脆弱性の温床としても悪名高い バグです。

1.2.3 二重解放：二度解放する

同じメモリを2回 free すると、メモリ管理機構の内部構造が壊れ、後続の malloc/free が予測不能な動作をします。これを 二重解放 (double free) と呼びます。

これら3つに共通するのは、あるメモリが「まだ使われているか」を人間が 正確に追跡し続けなければならない点です。データ構造が複雑に絡み合い、 複数の場所から同じオブジェクトが参照されるようになると、この追跡はほぼ 不可能になります。

1.3 GC というアイデア

ガベージコレクションは、この「いつ解放するか」の判断を 処理系（ランタイム） に肩代わりさせる 技術です。プログラマは確保するだけでよく、解放は GC が 自動的に行います。

GC の根底にある洞察は驚くほどシンプルです。

プログラムがこれ以上アクセスできないオブジェクトは、解放してよい。

裏返せば、プログラムがまだ到達できるオブジェクトは生かしておく必要が あります。この「到達できるかどうか」を 到達可能性 (reachability) と呼び、GC の中心概念になります。詳しくは次章 2. GCの基本アルゴリズム で扱います。

GC というアイデア自体は新しいものではありません。1960年、John McCarthy が プログラミング言語 LISP を設計した際に、世界初の GC が導入されました McCarthy^{[John, 1960]}。リストを多用する LISP では、不要になった セルを自動回収する仕組みが事実上必須だったのです。それ以来、GC は60年 以上にわたって研究・改良され続けてきました Wilson^{[Paul, 1992]}。

Ruby を例に取れば、私たちは普段こう書くだけで済みます。

def build
  ary = []
  1000.times { |i| ary << "item #{i}" }
  ary            # 大量の文字列オブジェクトを作って返す
end

result = build
# build の中で作られ、二度と参照されなくなった一時オブジェクトは、
# いずれ Ruby の GC が自動的に回収する。free は一切書かない。

free がどこにもないことに注目してください。不要になった文字列の回収は、 すべて Ruby 処理系の GC に任されています。

1.4 正確なGCと保守的GC：本書の主役

ここで一つ大きな分岐点が現れます。GC が「あるメモリ上の値がポインタなの かどうか」をどうやって知るか、という問題です。

多くの GC は、処理系の協力を得て どこにポインタがあるかを正確に把握 しています。これを 正確なGC (precise GC / exact GC) と呼びます。Ruby や Java の GC はこちらです。

これに対して 保守的GC (conservative GC) は、 「ポインタかどうか正確にはわからないが、ポインタに見える値はポインタだと みなす」という方針を取ります。この一見乱暴なアプローチは、Hans Boehm と Mark Weiser が1988年の論文で実用レベルに磨き上げました Boehm and Weiser^{[Hans-Juergen, 1988]}。彼らの実装は今日 libgc（Boehm- Demers-Weiser GC）として広く使われており、本書の後半で実際に動かします。

1.5 本書の歩き方

ここまでで、本書全体の見取り図が描けました。残りの章は次のように進みます。

1. 2. GCの基本アルゴリズム — 到達可能性、mark-sweep、参照カウント、 コピーGC といった GC の基本アルゴリズムを学びます。保守的GCを理解する ための土台です。
2. 3. 保守的GCとは何か — 「正確」と「保守的」の違いを正面 から定義し、保守的GCが何を諦めて何を得るのかを明らかにします。
3. 4. libgc を使ってみる — libgc を実際にインストールし、C プログラム から使ってみます。
4. 5. libgc の裏側 — libgc の内部実装を読み解きます。
5. 6. 保守的GCの理論的背景 — 偽ポインタ、正当性、空間使用量の 限界といった理論的な裏側に踏み込みます。
6. 7. 言語処理系への組み込み — Ruby を題材に、言語処理系へ GC を組み込む 際の実践的な勘どころを扱います。
7. 8. まとめと、これから — 全体のまとめと、保守的GCを「いつ使うべきか」 の指針を示します。

それでは、GC の基本アルゴリズムから始めましょう。

2. GCの基本アルゴリズム

保守的GCを理解するには、まず「ふつうのGC」がどう動くのかを知る必要が あります。実は、保守的GCの大半のメカニズムは通常のGCと同じで、違うのは 「どこにポインタがあるかをどう知るか」という一点だけだからです。この章 では、すべてのGCの基礎となる 到達可能性 の考え方と、代表的な3つの アルゴリズム（参照カウント、mark-sweep、コピーGC）を学びます。

2.1 到達可能性：何を生かし、何を回収するか

前章で述べたとおり、GC の判断基準は「プログラムがまだアクセスできるか」 です。これを形式的に考えてみましょう。

ヒープ上のオブジェクトは、互いにポインタで参照し合い、巨大な 有向グラフ (directed graph) を成しています。ノードがオブジェクト、 辺がポインタです。このグラフには出発点があります。プログラムが「いま まさに手に持っている」参照、すなわち

• グローバル変数
• 実行中の関数のローカル変数（スタック上にある）
• CPU のレジスタに入っている値

などです。これらをまとめて ルート (root / root set) と呼びます。

オブジェクトが 到達可能 (reachable) であるとは、いずれかのルートから ポインタをたどって（何ステップでもよい）そのオブジェクトに行き着ける、 ということです。到達可能なオブジェクトは将来使われるかもしれないので生か し、到達できないオブジェクト（=ごみ、garbage）は回収します。

graph LR
    R1[ルート: 変数 a] --> A((オブジェクト A))
    R2[ルート: 変数 b] --> B((オブジェクト B))
    A --> C((オブジェクト C))
    B --> C
    D((オブジェクト D)) --> E((オブジェクト E))
    style D fill:#fbb,stroke:#900
    style E fill:#fbb,stroke:#900

上の図では、A・B・C はルートから到達できるので生きています。D と E は 互いに参照し合っていますが、どのルートからもたどり着けないので「ごみ」 です。互いに参照し合っていても、外から到達できなければ回収できる—— この点が後で述べる参照カウントとの大きな違いになります。

2.2 アルゴリズム1：参照カウント

最も素朴なアプローチが 参照カウント (reference counting) です。各オブジェクトに「自分を指しているポインタ の数」を数えるカウンタを持たせます。

• ポインタが新しくオブジェクトを指したら、カウンタを +1
• ポインタがオブジェクトを指すのをやめたら、カウンタを −1
• カウンタが 0 になった瞬間、そのオブジェクトは誰からも参照されていない ので即座に解放する

# 参照カウントの考え方（擬似コード）
def assign(slot, new_obj)
  new_obj.refcount += 1 if new_obj      # 新しい参照が増える
  old = slot.value
  slot.value = new_obj
  if old
    old.refcount -= 1                   # 古い参照が減る
    free(old) if old.refcount == 0      # 0 になったら回収
  end
end

参照カウントの長所は、回収が即時で、処理が局所的なことです。一方で、 2つの弱点があります。第一に、ポインタを書き換えるたびにカウンタ更新の コストがかかります。第二に、循環参照を回収できません。先ほどの図の D と E のように互いを指し合うと、カウンタは 1 のまま 0 になりません。 このため純粋な参照カウントだけでは循環するデータ構造を扱えず、別の仕組み （後述のトレース型GC）と組み合わせるのが普通です Jones et al.^{[Richard, 2023]}。

2.3 アルゴリズム2：mark-sweep

参照カウントが「各オブジェクトが局所的に判断する」方式だったのに対し、 mark-sweep（マークアンドスイープ） は、 グラフ全体を一気にたどって到達可能性を判定する トレース型GC (tracing GC) の代表格です。本書の主役である保守的GCも、基本はこの mark-sweep です。

mark-sweep は2つの段階（フェーズ）から成ります。

マークフェーズ (mark phase): ルートから出発してポインタをたどり、 到達できたオブジェクトすべてに「印（マークビット）」を付けます。これは グラフの探索（深さ優先探索や幅優先探索）そのものです。

スイープフェーズ (sweep phase): ヒープ全体を端から端まで走査し、 マークが付いていないオブジェクトを解放します。同時に、次回のために すべてのマークを消します。

# mark-sweep の骨格（擬似コード）
def mark(obj)
  return if obj.nil? || obj.marked?    # 印済みなら再訪しない（循環対策）
  obj.mark!
  obj.each_pointer { |child| mark(child) }   # 参照先を再帰的にたどる
end

def collect(roots, heap)
  roots.each { |r| mark(r) }           # マークフェーズ
  heap.each do |obj|                   # スイープフェーズ
    if obj.marked?
      obj.unmark!                      # 次回に備えて消す
    else
      free(obj)                        # ごみを回収
    end
  end
end

mark-sweep は循環参照を問題なく回収できます（到達できなければ、たとえ 循環していてもマークされないからです）。一方、欠点は GC のたびにヒープ 全体を走査する必要があり、その間プログラムを止める ストップ・ザ・ワールド (stop-the-world) な停止が発生しやすいことです。この停止を短くする工夫 として、Dijkstra らはプログラムと並行して動く on-the-fly GC を提案しま した Dijkstra et al.^{[Edsger, 1978]}。

mark-sweep のもう一つの特徴は、オブジェクトを動かさない（non-moving） ことです。回収しても生きているオブジェクトはその場に残ります。この性質は、 後で見るように保守的GCにとって決定的に重要になります。

2.4 アルゴリズム3：コピーGC

3つめは コピーGC (copying GC) です。ヒープを 2つの等しい領域（fromスペースとtoスペース）に分け、片方だけを使います。

GC が走ると、fromスペースの中の到達可能なオブジェクトを、すべて toスペースへコピーします。コピーが終わったら from と to の役割を 入れ替えます。ごみは「コピーしない」だけで自動的に置き去りにされるので、 スイープのようにヒープ全体を走査する必要がありません。生きているオブ ジェクトだけを訪問すればよいのです。C. J. Cheney は、これを補助スタック なしに（toスペース自体を作業領域として使い）実現する巧妙な手法を示しま した Cheney^{[C., 1970]}。

graph LR
    subgraph from [from スペース GC前]
        A1((A 生存)) --> B1((B 生存))
        G1((ごみ))
    end
    subgraph to [to スペース GC後]
        A2((A)) --> B2((B))
    end
    A1 -.コピー.-> A2
    B1 -.コピー.-> B2

コピーGCの長所は2つあります。第一に、コピー後の toスペースには生きた オブジェクトが隙間なく詰めて配置されるので、断片化 (fragmentation) が起きません。第二に、空いた領域が連続するので、確保がポインタを進める だけの非常に高速な操作になります。

しかし、ここに保守的GCとの根本的な緊張関係があります。コピーGCは オブジェクトを動かす（moving） ため、そのオブジェクトを指していた すべてのポインタを、新しいアドレスに書き換えなければなりません。 そのためには「どの値がそのオブジェクトを指すポインタなのか」を正確に 知る必要があります。次章で見るように、保守的GCはまさにこの「正確に知る」 ことを諦めた仕組みなので、素朴なコピーGCとは相性が悪いのです。

2.5 3つのアルゴリズムの比較

ここまでの3つを整理しておきましょう。

保守的GCは、この中の mark-sweep を土台にします。なぜなら mark-sweep は オブジェクトを動かさない ため、「これはポインタかもしれない」と いう曖昧な判断だけで安全に動かせるからです。この理由を次章でしっかり 解き明かしていきます。

3. 保守的GCとは何か

前章で、GC は「ルートからポインタをたどって到達可能性を判定する」もので あることを見ました。ここで素朴な疑問が湧きます——GC はそもそも、メモリ上 のどの値が「ポインタ」なのかを、どうやって知るのでしょうか。この問いへの 答え方の違いが、正確なGC と 保守的GC を分けます。この章では両者の 違いを正面から定義し、保守的GCが何を諦め、その代わりに何を手に入れるのか を明らかにします。

3.1 ビット列はそれ自体ではポインタではない

コンピュータのメモリの中身は、結局のところただのビット列です。たとえば 4バイトに 0x00 0x60 0x3a 0x10 という並びが入っていたとして、これが

• ヒープ上のアドレス 0x103a6000 を指すポインタなのか
• それとも整数 272105472 なのか
• あるいは浮動小数点数や文字列の一部なのか

——メモリの中身を見ただけでは区別がつきません。「これはポインタである」 という情報は、値そのものには書かれていない のです。

GC がポインタをたどるには、この区別を何らかの方法で手に入れなければなり ません。手に入れ方が2通りあり、それが正確なGCと保守的GCの分かれ道です。

3.2 正確なGC：型情報でポインタを知る

正確なGC (precise GC) は、処理系の協力によって 「どこにポインタがあるか」を正確に把握します。具体的には、処理系が次の ような情報を用意します。

• オブジェクトの型情報：各オブジェクトについて「先頭から8バイト目と 16バイト目がポインタ」のように、どのフィールドがポインタかを記述した 地図（ポインタマップ (pointer map) や レイアウト情報と呼ばれる）。
• スタックマップ (stack map)：実行中の各関数について、スタックフレーム のどの位置にポインタがあるかをコンパイラが記録したもの。

これらがあれば、GC はメモリ上の値がポインタかどうかを迷わず判定できます。 Java（JVM）の GC はこの方式の典型例です。CRuby（MRI）では、ヒープ上の 各オブジェクトが RBasic という共通ヘッダを持ち、型ごとに内部構造が 決まっているため、ヒープオブジェクト内の参照は正確にたどれます。 ただし CRuby の C スタックのスキャンには保守的な要素が残るため、GC 全体 としては「おおむね正確 (mostly-precise)」に近い立場であり、また GC.compact による断片化解消も全オブジェクトを対象にできるわけでは ありません（ピン留めが必要なオブジェクトが存在します）。

正確なGCには大きな利点があります。ポインタの在り処を確実に知っているの で、前章のコピーGCのように オブジェクトを動かして、すべてのポインタを 書き換える ことができます。つまり、断片化の解消やコンパクションが可能 です。

ただし、正確なGCには代償もあります。コンパイラと密に連携してスタック マップや型情報を生成しなければならず、処理系全体がGCを前提に設計されて いる必要があります。GC を想定していない C や C++ のコードに後から正確な GC を載せるのは、極めて困難 です。なぜなら、C コンパイラはスタックや レジスタのどこにポインタがあるかを記録してくれないからです。

3.3 保守的GC：見た目でポインタを推測する

ここで 保守的GC (conservative GC) の出番です。 保守的GCは型情報やスタックマップを 使いません。代わりに、メモリ上の すべての語（word）について、こう問いかけます。

この値を「アドレス」だと解釈したら、ヒープ上の確保済みオブジェクトの 内部を指しているか？

もし指しているなら、その値は ポインタかもしれない とみなし、指す先の オブジェクトを生かしておきます。指していなければ、ただの整数か何かだろう と判断して無視します。

この方針が「保守的」と呼ばれる理由は、判断に迷ったとき必ず 安全側に 倒す からです。本当はただの整数なのにポインタに見えてしまった場合、 余計なオブジェクトを生かしてしまいますが、それは「メモリを少し無駄に する」だけで、プログラムは正しく動き続けます。逆に、本物のポインタを 見落としてオブジェクトを誤って回収してしまうと、プログラムが壊れます。 だから保守的GCは「疑わしきは生かす」のです。

# 保守的なルート走査の考え方（擬似コード）
# スタックやレジスタの「全部の値」を、ポインタ候補として総当たりで調べる
def scan_conservatively(region, heap)
  region.each_word do |value|
    obj = heap.object_containing(value)   # value が指す先のオブジェクトは?
    mark(obj) if obj                       # 見つかったら（疑わしきは）生かす
  end
end

ポイントは、保守的GCがメモリ領域の 意味を一切問わない ことです。 スタック上に並ぶ値が、ローカル変数なのか、保存されたレジスタなのか、 関数の戻りアドレスなのかを区別せず、ただ「ヒープを指しているように 見えるか」だけで判定します。だからこそ、コンパイラの協力なしで、つまり GC を想定していない環境（uncooperative environment）でも動く のです。 この発想を実用化したのが、Hans Boehm と Mark Weiser の1988年の論文 Boehm and Weiser^{[Hans-Juergen, 1988]} でした。論文タイトルの “uncooperative environment（非協力的な環境）” とは、まさに「GC に協力してくれない C の ような環境」を指しています。

3.4 偽ポインタ：保守的GCが払う代償

保守的GCの代償は、偽ポインタ (false pointer) の 問題です。たまたまヒープ内のアドレスと同じビット列を持った整数が、ポインタ と誤認されることがあります。

たとえば、ある画像処理プログラムが画素値として 0x00103a60 という整数を 持っていて、それがちょうどあるオブジェクトの先頭アドレスと一致したと しましょう。保守的GCはこの整数を「ポインタかもしれない」とみなし、その オブジェクトを生かし続けてしまいます。本当はもう誰も使っていないのに、です。

その結果、回収されるべきごみが回収されず、メモリ使用量がじわじわ増える ことがあります。これは前章で見たメモリリークに似ていますが、原因が違い ます。プログラマのミスではなく、「ポインタかもしれない」という曖昧さ そのものが生んだリーク です。

幸い、実用上は偽ポインタの確率は驚くほど低く抑えられます。64ビット環境 ではアドレス空間が広大なので、ランダムな整数がたまたま有効なヒープ アドレスと一致する確率は極めて小さくなります。Boehm らの測定や Zorn の 評価でも、多くの実プログラムで保守的GCは実用的に機能することが示されて います Zorn^{[Benjamin, 1993]}。

3.5 あいまいなルートと「動かせない」という制約

保守的GCのもう一つの本質的な帰結が、オブジェクトを動かせない ことです。

前章で見たコピーGCは、オブジェクトを移動したらそのポインタをすべて書き 換える必要がありました。しかし保守的GCは、ある値が「ポインタかもしれない」 としか言えません。もしそれが本物のポインタなら書き換えるべきですが、 たまたま一致しただけの整数だったら、書き換えてはいけません（プログラムの データを破壊してしまいます）。確信が持てないものは書き換えられない—— これが保守的GCの鉄則です。

このように、ポインタかどうか確定できない参照を あいまいな参照 (ambiguous reference) あるいは「あいまいなルート (ambiguous root)」と 呼びます。あいまいな参照が指すオブジェクトは、安全のため動かせません。

ここから2つの設計が生まれます。

1. 完全に動かさない設計：すべてを mark-sweep で扱い、一切オブジェクト を移動しない。libgc が基本的に取る方式です。
2. 一部だけ動かす設計（mostly-copying GC）：あいまいな参照に指された オブジェクトだけはその場に固定（ピン留め, pinning）し、それ以外は コピーGCで動かす。Joel Bartlett が提案した手法です Bartlett^{[Joel, 1988]}。彼はこれを Scheme から C へのコンパイラ で実際に用いました Bartlett^{[Joel, 1989]}。

「mostly-copying（おおむねコピー）」という名前は、「あいまいな参照に 指された一部を除いて、おおむねコピーする」という折衷を表しています。 詳しくは 6. 保守的GCの理論的背景 で再訪します。

3.6 正確なGCと保守的GCの比較

両者の違いをまとめておきましょう。

要するに、保守的GCは 「正確さ」と「コンパクションの能力」を諦める代わ りに、「コンパイラの協力なしにどんな環境でも動く」という強力な汎用性を 手に入れた GC だ、と言えます。このトレードオフを理解したところで、 次章ではいよいよ代表的な実装である libgc を実際に動かしてみましょう。

4. libgc を使ってみる

理論の話が続きましたが、この章では手を動かします。保守的GCの代表的な実装 である libgc（正式には Boehm-Demers-Weiser GC、略して BDWGC）を実際に インストールし、C プログラムから使ってみましょう。前章までで「保守的GCは コンパイラの協力なしに動く」と述べましたが、それがどれほど手軽かを体感 できるはずです。

4.1 libgc とは

libgc は、C と C++ のための保守的なごみ収集ライブラリです。Hans Boehm、 Alan Demers、Mark Weiser らの研究 Boehm and Weiser^{[Hans-Juergen, 1988]} を 出発点に、長年にわたって開発が続けられてきました。今日では多くの実用 ソフトウェアで使われています。たとえば、

• GNU の言語処理系の一部（過去の GCJ など）
• いくつかの Scheme / Lisp 処理系（前章で触れた Bartlett の Scheme→C を 含む Bartlett^{[Joel, 1989]}）
• 各種スクリプト言語や組み込み言語のランタイム

などです。「既存の C コードに、malloc/free を書き換えるだけで GC を 導入できる」という手軽さが、その普及を支えてきました。

4.2 インストール

多くの Linux ディストリビューションでは、パッケージマネージャから簡単に 入れられます。Debian/Ubuntu 系なら次のとおりです。

# 開発用ヘッダ（gc.h）とライブラリ本体をまとめて入れる
sudo apt install libgc-dev

Fedora/RHEL 系なら sudo dnf install gc-devel、macOS の Homebrew なら brew install bdw-gc です。

最新版を使いたい、あるいは細かくビルドオプションを調整したい場合は、 ソースからビルドします。

git clone https://github.com/bdwgc/bdwgc
cd bdwgc
./autogen.sh         # 自動ツールで configure を生成
./configure
make
sudo make install

4.3 最初のプログラム：malloc を GC_MALLOC に置き換える

libgc の使い方は驚くほど単純です。malloc を GC_MALLOC に置き換え、 free を 書かない（消す）だけです。次のプログラムは、大量のメモリを 確保し続けますが、free を一切呼びません。それでもメモリは枯渇しません。 libgc が不要になったメモリを自動的に回収するからです。

#include <stdio.h>
#include <gc.h>          /* libgc のヘッダ */

int main(void) {
    GC_INIT();           /* GC を初期化する（最初に一度だけ） */

    for (int i = 0; i < 10000000; i++) {
        /* 毎回 256 バイト確保するが、ポインタはすぐ上書きされる。
           つまり前回確保したメモリは到達不能になり「ごみ」になる。 */
        char *p = (char *)GC_MALLOC(256);
        p[0] = (char)i;                 /* 確保したメモリを使う */

        if (i % 1000000 == 0) {
            /* libgc が把握しているヒープサイズを表示してみる */
            printf("iter %8d, heap size = %zu bytes\n",
                   i, (size_t)GC_get_heap_size());
        }
    }
    return 0;
}

ループは1000万回まわり、毎回 256 バイトを確保します。単純計算では 約2.5GB ものメモリを要求していますが、free を書いていないのに メモリは破綻しません。GC_get_heap_size() の表示を見ると、ヒープサイズ がある程度で頭打ちになることが確認できます。確保したメモリがすぐ到達 不能になるため、libgc がそれを繰り返し回収して再利用しているのです。

4.4 コンパイルとリンク

このプログラムをビルドするには、libgc をリンクします。ライブラリ名は gc なので、-lgc を指定します。

cc -o gctest gctest.c -lgc
./gctest

ヘッダ gc.h が標準の場所になければ -I で、ライブラリが見つからなけ れば -L でパスを補います（ソースから /usr/local に入れた場合など）。

cc -I/usr/local/include -o gctest gctest.c -L/usr/local/lib -lgc

リンク以外にソースコードへ加える変更は、#include <gc.h> と malloc→GC_MALLOC の置き換えだけです。これが「非協力的な環境でも動く」 保守的GCの威力です。

4.5 確保関数の使い分け：ポインタを含むか含まないか

libgc には用途別の確保関数があります。中でも重要なのが GC_MALLOC と GC_MALLOC_ATOMIC の使い分けです。

• GC_MALLOC(size)：確保した領域の中に ポインタが入っているかも しれない とみなされます。GC はマーク時にこの領域の中身を走査し、 ポインタらしき値があればたどります。構造体やポインタ配列はこちらを 使います。
• GC_MALLOC_ATOMIC(size)：確保した領域の中に ポインタは絶対に 入っていない とプログラマが保証する確保です。「atomic」は「これ以上 たどる必要がない＝走査の対象としては不可分」という意味です。文字列、 画像の画素データ、浮動小数点数の配列など、純粋なデータにはこちらを 使います。

/* ポインタを含むかもしれない構造体 → GC_MALLOC */
struct node {
    int value;
    struct node *next;     /* ポインタを含む！ */
};
struct node *n = (struct node *)GC_MALLOC(sizeof(struct node));

/* 純粋なバイト列（ポインタを含まない）→ GC_MALLOC_ATOMIC */
double *samples = (double *)GC_MALLOC_ATOMIC(1000 * sizeof(double));

なぜこの区別が重要なのでしょうか。前章で見た 偽ポインタ を思い出して ください。GC_MALLOC_ATOMIC で確保した領域を「ポインタを含まない」と GC に教えておけば、GC はその中身を一切走査しません。すると、その領域に たまたまヒープアドレスと一致する数値（画素値など）があっても、偽ポインタ として誤認されることがなくなります。GC_MALLOC_ATOMIC を正しく使うこと は、偽ポインタによる無駄な保持を減らす最も効果的な手段の一つ です。

4.6 明示的な GC 制御と統計

libgc はふだん自動でGCを走らせますが、手動で制御することもできます。 デバッグや性能測定で便利です。

GC_gcollect();                 /* 今すぐフルGCを実行する */

size_t heap = GC_get_heap_size();      /* ヒープ全体のサイズ */
size_t free = GC_get_free_bytes();     /* そのうち空きバイト数 */
printf("heap=%zu free=%zu\n", (size_t)heap, (size_t)free);

GC_FREE(p) で明示的に解放することもできますが、保守的GCの利点を捨てる ことになるので、通常は使いません。むしろ、確保はすべて GC に任せ、解放を 書かないのが libgc 流のスタイルです。

ここまでで、libgc を「使う」側の基本は身につきました。malloc を置き 換えるだけで GC が手に入る——この手軽さの裏で、libgc はいったいどんな 仕組みでポインタを探し、メモリを管理しているのでしょうか。次章 5. libgc の裏側 で、その内部に踏み込みます。

5. libgc の裏側

前章では libgc を「使う」側に立ちました。この章では、その内部に分け入り ます。GC_MALLOC を呼ぶと何が起きるのか。GC はどうやってスタックや レジスタからルートを集めるのか。「この値はヒープを指しているか」をどう 判定しているのか。そして、保守的GCならではの偽ポインタ問題に、libgc は どんな工夫で立ち向かっているのか。これらを順に見ていきます。

5.1 ヒープの構造：サイズごとのブロック

libgc はヒープを、OS から大きな塊（チャンク）でまとめて受け取り、それを ブロック (block) と呼ばれる固定サイズ（典型的には4KB、メモリページ 1枚ぶん）の単位に切り分けて管理します。

ここが要点ですが、1つのブロックは1種類のサイズのオブジェクトだけを 入れる よう使われます。たとえばあるブロックは16バイトのオブジェクト 専用、別のブロックは32バイト専用、という具合です。同じ大きさのオブジェクト をまとめる方式を サイズクラス (size class) による管理と呼びます。

graph TD
    OS[OS から確保した大きな領域] --> B1[ブロック A: 16B 用]
    OS --> B2[ブロック B: 32B 用]
    OS --> B3[ブロック C: 64B 用]
    B1 --> O1[obj]
    B1 --> O2[obj]
    B1 --> O3[obj ...]
    B2 --> O4[obj]
    B2 --> O5[obj ...]

この設計には、保守的GCにとって嬉しい効果があります。あるアドレスが 与えられたとき、「それがどのブロックに属するか」はアドレスを ブロックサイズで割るだけで求まり、ブロックがわかれば「そこに入っている オブジェクトのサイズ」も即座にわかります。つまり 任意のアドレスから、 それがどのオブジェクトの内部を指しているかを高速に逆引きできる のです。 保守的GCはメモリ上の無数の値について「これはヒープを指すか？」を問い続け るので、この逆引きが速いことは死活的に重要です。

各ブロックはヘッダを持ち、その中に マークビットの配列 を保持します。 オブジェクトごとに1ビットを割り当て、マークフェーズで立てます。マーク ビットをオブジェクト本体とは別の場所（ブロックヘッダ）にまとめておくのは、 オブジェクトの中身に手を触れずに済ませる工夫でもあります。

5.2 ルートの収集：スタック・レジスタ・静的領域

GC が始まると、まずルートを集めます。正確なGCならスタックマップを見る ところですが、保守的GCにはそれがありません。代わりに libgc は、ルートに なりうる領域を 丸ごとスキャン対象 にします。

• スタック：現在のスタックポインタから、スタックの底までの全範囲。 この中の語をすべてポインタ候補として調べます。スタックの底（開始位置） は、GC_INIT() の時点やOSの情報から推定します。
• レジスタ：CPU のレジスタにポインタが入ったままGCが起きるかもしれ ません。libgc はレジスタの内容をいったんスタックに退避させてから（ setjmp などを使って）、まとめてスキャンします。
• 静的データ領域：グローバル変数や静的変数が置かれる領域（BSS や data セグメント）。ここに入っているポインタもルートです。

graph LR
    S[スタック全体] -->|候補値| M{ヒープを指すか?}
    R[レジスタ退避値] -->|候補値| M
    G[静的データ領域] -->|候補値| M
    M -->|Yes| K[そのオブジェクトをマーク]
    M -->|No| I[無視する]

ここで重要なのは、libgc が これらの領域の意味を一切解釈しない こと です。スタック上の値がローカル変数なのか、保存されたレジスタなのか、 関数の戻りアドレスなのかを区別しません。ただ全部の語について「ヒープを 指すように見えるか」だけを総当たりで調べます。これこそが、前章「GCの基本アルゴリズム」で述べた「あいまいなルート」の正体です。意味を問わないからこそ、コンパイラ の協力なしに動けるのです。

5.3 ポインタ妥当性の判定と内部ポインタ

「この値はヒープを指すか？」という問いを、libgc は2段階で答えます。

1. まず、値が libgc の管理するヒープのアドレス範囲に収まっているかを ざっと確認する。
2. 次に、先ほどのブロック構造を使って、その値が実際に確保済みオブジェクト の内部を指しているかを確かめる。割り当て済みでない（空き）位置を指して いれば、ポインタではないと判断する。

ここで保守的GCならではの配慮が必要になります。それが 内部ポインタ (interior pointer) です。C のプログラムでは、オブジェクトの先頭では なく途中を指すポインタがごく普通に現れます。

char *buf = (char *)GC_MALLOC(100);
char *p = buf + 50;     /* オブジェクトの途中を指すポインタ */
/* このあと buf を捨てて p だけ残しても、buf 全体が生きていてほしい */

もし GC が「オブジェクトの先頭アドレスと一致する値だけをポインタとみなす」 設計だと、p のような内部ポインタを見落とし、buf を誤って回収して しまいます。そこで libgc は、オブジェクトの内部のどこを指していても、 そのオブジェクト全体を生かす よう設計されています。先ほどの「アドレス からブロックを逆引きし、オブジェクトのサイズがわかる」構造が、ここでも 効いています。途中のアドレスから所属オブジェクトの先頭を割り出せるから です。

5.4 マークと遅延スイープ

ルートが集まったら、mark-sweep を実行します。基本 アルゴリズムは「GCの基本アルゴリズム」の章で見たとおりです。ルート から到達できたオブジェクトのマークビットを立て（マークフェーズ）、立って いないものを回収します（スイープフェーズ）。

ただし libgc のスイープには工夫があります。遅延スイープ (lazy sweep) です。マークが終わった直後にヒープ全体を一気に走査するのではなく、その後 GC_MALLOC が呼ばれて「空きが必要になったとき」に、必要なぶんだけブロック を走査して空きを回収します。回収の手間を実際の確保要求に合わせて分散させ ることで、一度に長く止まることを避けています。

GC_MALLOC の中で空きが見つからなければ、libgc はまず遅延スイープで 回収を試み、それでも足りなければGC（マーク）を起動し、それでも足りなけ れば OS からヒープを拡張します。確保関数の裏では、このような段階的な処理 が走っているのです。

5.5 blacklisting：偽ポインタへの備え

ここからが保守的GCの核心的な工夫です。前章で述べたとおり、偽ポインタ （たまたまヒープアドレスと一致した整数）は、本来回収すべきオブジェクトを 生かし続けてしまいます。libgc はこれに ブラックリスティング (blacklisting) という手法で対抗します Boehm^{[Hans-Juergen, 1993]}。

アイデアはこうです。GC は走査の途中で、「ヒープを指しているように見える が、実際には確保済みオブジェクトを指していない値」に出会うことがあります。 これは「あと少しずれていたら偽ポインタになっていた、危険なビットパターン」 です。libgc はそうした値が指す 付近のアドレス（ブロック）を記録 して おきます。これがブラックリストです。

そして、その後に新しくメモリを確保するとき、libgc は ブラックリストに 載っているアドレスを避けて オブジェクトを配置します。こうすると、その 危険なビットパターンが将来また現れても、そこには確保済みオブジェクトが 存在しないため、偽ポインタとして悪さをしません。「偽ポインタになりそうな 場所には、そもそも大事なものを置かない」という予防策です。

5.6 並行・インクリメンタルGC：止まる時間を短くする

mark-sweep の弱点は、GC 中にプログラムを止める stop-the-world でした。 libgc はこれを和らげる インクリメンタル／おおむね並行（mostly-parallel） なモードも備えています。これは Boehm、Demers、Shenker による手法に基づい ています Boehm et al.^{[Hans-J., 1991]}。

鍵となるのは、仮想メモリのページ保護機能 の活用です。OS は「あるメモリ ページが書き換えられたか（dirty かどうか）」を検出する仕組みを持っています。 libgc はこれを使い、マーク作業をプログラム実行と少しずつ交互に進めます。 マークの途中でプログラムがオブジェクトを書き換えても、そのページが dirty として記録されるので、GC はそのページだけを後でマークし直せばよいのです。 これにより、ヒープ全体を一度に走査するための長い停止を避けられます。 このモードは GC_enable_incremental() で有効化できます。

仮想メモリのハードウェア機能を使ってGCの停止を短くする——これは「OS や ハードウェアの協力は得るが、コンパイラの協力は要らない」という、保守的GC ならではのバランス感覚をよく表しています。

ここまでで、libgc が内部でどうポインタを探し、メモリを管理し、偽ポインタ に備えているかが見えてきました。次章では、これらの工夫が「なぜ正しく動く のか」「偽ポインタによるメモリ増加は理論上どこまで保証できるのか」という、 一段深い理論に踏み込みます。

6. 保守的GCの理論的背景

ここまで「保守的GCは曖昧さを安全側に倒すことで動く」と繰り返してきました。 この章では、その「安全側」が本当に安全だと言える根拠（正当性）を整理し、 偽ポインタがどれくらいの確率で起きるのかを見積もり、そして「偽ポインタ のせいでメモリは際限なく増えてしまわないのか」という理論的な限界に踏み 込みます。少し抽象的になりますが、保守的GCを安心して使うための土台です。

6.1 正当性：なぜ壊れずに動くのか

GC の正しさは、2つの性質に分けて考えると見通しがよくなります。

• 健全性 (soundness / safety)：生きている（到達可能な）オブジェクト を絶対に回収しない。これが破れるとプログラムが壊れます。
• 完全性 (completeness)：ごみ（到達不能なオブジェクト）はすべて回収 する。これが破れてもプログラムは壊れませんが、メモリが無駄になります。

正確なGCは、原理的にこの両方を満たせます。一方、保守的GCのキモは次の 非対称性にあります。

保守的GCは 健全性は完全に保証する が、完全性は犠牲にする。

なぜ健全性が保証されるのか。保守的GCは「ポインタかもしれない値」をすべて ポインタとみなして、その先を生かします。本物のポインタは必ず「ポインタの ように見える」ので、見落とされることがありません。つまり、到達可能な オブジェクトに至る本物のポインタは 必ず たどられ、対象は生かされます。 ゆえに生きているオブジェクトを誤って回収することはない——これが健全性の 直観的な証明です。

代償として、ポインタでない値もポインタとみなしてしまうため、到達不能な オブジェクトの一部を「ごみだと判定できず」生かしてしまいます。これが完全性 の犠牲、すなわち 偽ポインタ によるメモリ保持です。

6.2 健全性の但し書き：見えないポインタ

保守的GCの健全性は、「本物のポインタは必ずポインタのように見える」という 前提に立っています。逆に言えば、本物のポインタがどこにも『見えなく』 なってしまうと、健全性が崩れます。これは保守的GC特有の落とし穴です。

たとえば、プログラマがポインタを暗号化したり、ビット演算で隠したり、 ファイルやネットワーク越しに退避してメモリ上から消したりすると、GC は それを「ポインタかもしれない値」として発見できません。

char *p = (char *)GC_MALLOC(100);
uintptr_t hidden = (uintptr_t)p ^ 0xdeadbeef;  /* ポインタを隠す */
p = NULL;     /* 元のポインタを消す。今や hidden を XOR しないと復元できない */
/* この時点で GC からは p の指す先が到達不能に見え、回収されうる！ */
char *q = (char *)(hidden ^ 0xdeadbeef);        /* 復元しても手遅れ */

このように、ポインタを GC から「見えなく」する操作は、保守的GCの前提を 壊します。実用上めったに起きませんが、最適化でポインタの下位ビットにタグ を埋め込む（pointer tagging）処理系などでは現実的な注意点になります Jones et al.^{[Richard, 2023]}。

6.3 偽ポインタはどれくらい起きるのか

完全性を犠牲にするとはいえ、実用上は問題にならない程度に偽ポインタを 抑えられる、というのが保守的GCが広く使われている理由です。簡単な確率の 見積もりでそれを確かめましょう。

いま、ヒープが バイト確保されているとします。ランダムな1つの語の値 が、たまたまこのヒープのどこかを指してしまう確率は、ざっくりとアドレス 空間全体 に対する の割合です。

32ビット環境ではアドレス空間は バイト（約4GB）しかありません。 ヒープが数百MBにもなると が無視できなくなり、偽ポインタが現実的な 頻度で発生します。これが「32ビット環境では保守的GCの偽ポインタが痛い」 と言われた歴史的な理由です。

ところが64ビット環境では と桁違いに広大です。仮にヒープが 1GB () でも、

と、1語あたりの偽ポインタ確率は天文学的に小さくなります。さらに、実際の ヒープアドレスは空間内のごく狭い範囲に固まっているため、ランダムな整数が そこに当たる確率はもっと低くなります。64ビット環境の普及が、保守的GC の実用性を大きく押し上げた のです。

6.4 空間使用量に限界はあるのか

確率は小さいとしても、「最悪のケースでは偽ポインタが連鎖して、メモリが 際限なく膨れ上がるのではないか」という不安が残ります。これは理論的にも 重要な問いで、Hans Boehm が正面から論じています Boehm^{[Hans-J., 2002]}。

直観的な心配はこうです。1個の偽ポインタが大きなデータ構造 X を生かす。 X の中の値がまた偽ポインタとなって別の構造 Y を生かす。Y がさらに……と、 偽の連鎖が雪だるま式に広がるのではないか、という懸念です。

Boehm の分析が示したのは、適切に設計された保守的GCでは、この空間 オーバーヘッドにきちんと上界（バウンド）を与えられる ということです。 鍵になるのは、やはり前章の工夫です。

• ポインタを含まない領域の扱い（GC_MALLOC_ATOMIC）：純粋なデータ （画素・文字列・数値配列）はポインタとして走査されないので、偽ポインタ の発生源になりません。偽の連鎖は、ポインタを含みうる領域を経由しなければ 続かないので、この区別が連鎖を断ち切ります。
• ブラックリスティング：偽ポインタになりそうなアドレスを確保前に避ける ことで、危険なビットパターンが現実のオブジェクトに「命中」する確率を 下げます Boehm^{[Hans-Juergen, 1993]}。

これらが効くことで、保守的GCの空間使用量は「正確なGCの定数倍」といった 形で抑えられることが、理論と実測の両面から示されています。実プログラム での実測コストを丁寧に評価した古典的な研究としては、Zorn の測定 Zorn^{[Benjamin, 1993]} や Detlefs らの比較 Detlefs et al.^{[David, 1994]} があり、保守的GCの実用性を裏づけています。

6.5 「どこまで保守的か」のスペクトル

「保守的GC」とひとくくりにしてきましたが、実は「どの部分を保守的に扱う か」には幅があります。これを理解すると、設計の選択肢が見えてきます。

• ルートのみ保守的（partly conservative）：スタックやレジスタといった ルートは保守的に（あいまいに）扱うが、ヒープ上のオブジェクトの中身は 型情報で正確にたどる方式。コンパイラの協力が一部得られるが、スタック マップまでは用意できない、という処理系で使われます。
• 完全に保守的（fully conservative）：ルートもヒープの中身も、すべて あいまいに扱う。libgc の既定の動作がこれです。GC_MALLOC で確保した 領域の中身を、型を知らずに総当たりで走査します。

ルートだけを保守的にすると、ヒープ内は正確なので偽ポインタの連鎖が 起こりにくく、しかもスタックマップが要らない、という良いとこ取りができ ます。次章で扱う Ruby のGCは、まさにこの「ルート（C のスタック）だけ 保守的」という設計の好例です。

6.6 mostly-copying：保守と移動の折り合い

前々章で「保守的GCはオブジェクトを動かせない」と述べました。あいまいな 参照に指されたオブジェクトを動かして書き換えると、それが本物のポインタ でなかった場合にデータを壊すからです。しかし、この制約を 部分的に 緩める巧妙な方法があります。Joel Bartlett の mostly-copying GC （おおむねコピーGC） です Bartlett^{[Joel, 1988]}。

アイデアはこうです。あいまいな参照（スタックなどから来る、ポインタか どうか確信できない参照）に指されたオブジェクトだけは、その場に固定して 動かしません。これを ピン留め (pinning) と呼びます。一方、ピン留め されていないオブジェクト（ヒープ内の正確にたどれる参照からのみ到達される もの）は、コピーGCで自由に動かします。

ヒープは コピーGC のようにページ単位で from/to を 管理し、あいまいな参照が指すページを「to スペースに昇格」させてその場に 残し、それ以外は通常どおりコピーする、という形で実現されます。こうすると、

• あいまいな参照が指す一部のオブジェクトは動かせない（保守の制約は残る）
• しかし、大多数のオブジェクトはコピー・コンパクションでき、断片化を抑え られる

という折衷が成立します。「mostly（おおむね）」という名前は、この「一部を 除いておおむねコピーする」性質を表しています。Bartlett はこれを Scheme から C へのコンパイラの実装で実証しました Bartlett^{[Joel, 1989]}。 保守的GCでも、工夫しだいでコンパクションの恩恵を部分的に取り戻せる—— これは理論的にも実用的にも美しい結果です。

理論的な土台が見えたところで、次章ではいよいよ、これらの考え方が実際の 言語処理系——とりわけ Ruby——でどう活かされているかを見ていきます。

7. 言語処理系への組み込み

ここまで、保守的GCの理論と libgc の使い方を見てきました。最後に、これらを 「自分の言語処理系に GC を入れる」という観点でつなぎ直します。題材として、 広く使われている実用処理系である Ruby が保守的GCの考え方をどう取り 入れているかを読み解き、続いて自作のミニ言語に libgc を組み込む際の実践的 な注意点（ファイナライザ、弱参照、スレッド）を整理します。

7.1 Ruby は「スタックだけ保守的」なGC

Ruby（CRuby、いわゆる MRI）の GC は、よく「保守的GC」と紹介されますが、 正確には、前章 6. 保守的GCの理論的背景 で述べた 「ルートのみ 保守的」 な設計です。中身を分解するとこうなります。

• C のマシンスタックは保守的に走査する：Ruby のインタプリタは C で 書かれており、評価の途中で生成された Ruby オブジェクトへのポインタが、 C 関数のローカル変数として C スタックに載ります。Ruby はこの C スタック を、どこにポインタがあるか正確には知りません。そこで libgc と同じく、 スタックを丸ごと走査して「Ruby のヒープを指しているように見える値」を ルートとして拾います。これが保守的な部分です。
• ヒープ上のオブジェクトは正確にたどる：いったんオブジェクトに到達 すれば、その先は曖昧さなしにたどれます。なぜなら Ruby のオブジェクトは すべて共通ヘッダ（RBasic）を持ち、型ごとに内部構造が決まっているから です。配列なら要素を、ハッシュならキーと値を、というように、型に応じた マーク関数が参照を正確にたどります。

つまり Ruby は「ルート（C スタック）は保守的・ヒープは正確」という ハイブリッドなのです。この設計には明確な理由があります。

このような「スタックは保守的・ヒープは正確」というハイブリッド設計は Ruby に限りません。C で実装された言語処理系では、C 拡張との共存や 生ポインタのスタック上への露出という課題が共通して現れるため、 類似のアプローチが広く使われています。たとえば GNU Guile（Scheme 処理系） は BDW-GC（libgc と同系統の Boehm-Demers-Weiser GC）を採用して 同様のハイブリッド戦略を取っています。

また、「スタックだけ保守的」は Ruby の設計における代表的な保守的走査箇所を 示した表現です。実際には C レジスタの内容も GC 開始直前にスタックへ退避 してから走査するため、厳密には「スタック＋レジスタ」が保守的走査の対象 です。さらに実装上の都合——型情報が確定していない箇所、正確なマーク関数を 書くコストが高い箇所、外部から持ち込まれた不透明なデータ構造など——から、 スタック以外の箇所を意図的に保守的に走査する実装も珍しくありません。 「どこを正確にし、どこを保守的にするか」は設計上のトレードオフであり、 スタックはその代表例にすぎません。

7.2 オブジェクトを正確にマークする

ヒープ側がどう「正確」なのかを、Ruby 風の擬似コードで見てみましょう。 各オブジェクトは型を持ち、型ごとに「自分が参照している他のオブジェクト」 を GC に教えるマーク処理を持ちます。

# 型ごとに、参照している子オブジェクトを正確にたどる（擬似コード）
def gc_mark(obj)
  return if obj.nil? || obj.marked?
  obj.mark!                       # このオブジェクトに印を付ける
  case obj.type
  when :array
    obj.elements.each { |e| gc_mark(e) }     # 全要素をたどる
  when :hash
    obj.each_pair { |k, v| gc_mark(k); gc_mark(v) }
  when :object
    obj.instance_variables.each { |iv| gc_mark(iv) }
  when :string, :float
    # 参照を持たないので、これ以上たどる必要はない（atomic に相当）
  end
end

注目してほしいのは、:string や :float のように 参照を持たない型は それ以上たどらない 点です。これは libgc の GC_MALLOC_ATOMIC と まったく同じ発想です。「ポインタを含まないと分かっているものは走査しない」 ことが、効率にも、（保守的な部分での）偽ポインタ抑制にも効きます。

実際の CRuby では、この gc_mark に相当する処理を、型ごとのマーク関数や rb_gc_mark といった API が担っています。C 拡張を書く人が「自分の構造体 が握っている Ruby オブジェクトを生かしたい」ときには、マーク用のコールバック の中でこの rb_gc_mark を呼びます。これは「ヒープ側は正確」という設計の 裏返しで、参照を GC に明示的に申告しているわけです。

7.3 自作言語に libgc を組み込む

では逆に、自分でミニ言語のインタプリタを C で書いているとして、そこに libgc を入れる場合を考えましょう。Ruby のように型ごとのマーク関数を全部 用意するのは大変です。ここで保守的GCの真価が発揮されます——完全に保守的 に倒せば、マーク関数を一切書かずに済むのです。

手順はこれだけです。

1. インタプリタのオブジェクト（値を表す構造体）を、malloc ではなく GC_MALLOC で確保する。
2. 参照を含まない値（文字列バッファや数値配列）は GC_MALLOC_ATOMIC で 確保する。
3. free を書かない。

#include <gc.h>

typedef enum { T_INT, T_PAIR, T_STR } type_t;

typedef struct value {
    type_t type;
    union {
        long      i;            /* 整数 */
        struct { struct value *car, *cdr; } pair;   /* ポインタを含む */
        char     *str;          /* 文字列へのポインタ */
    } as;
} value_t;

/* cons セル（ポインタを2つ含む）→ GC_MALLOC */
value_t *new_pair(value_t *a, value_t *d) {
    value_t *v = (value_t *)GC_MALLOC(sizeof(value_t));
    v->type = T_PAIR;
    v->as.pair.car = a;
    v->as.pair.cdr = d;
    return v;                   /* free は不要。GC が面倒を見る */
}

new_pair の中身を GC_MALLOC で確保しているので、libgc はこの構造体の 中身（car と cdr のポインタ）を勝手に走査してくれます。型ごとのマーク 関数を書く必要はありません。インタプリタの評価ループが回る間、生きている 値への参照は C のローカル変数（=スタック）に自然に残るので、libgc が保守的 に拾ってくれます。「GC を後から、最小の労力で載せる」用途で保守的GCが 重宝される のは、まさにこの手軽さゆえです Jones et al.^{[Richard, 2023]}。

7.4 ファイナライザ：解放時に後始末する

オブジェクトが回収されるとき、ファイルを閉じる・OSリソースを返すといった 後始末をしたいことがあります。libgc は ファイナライザ (finalizer) で これに対応します。GC_register_finalizer でコールバックを登録すると、 そのオブジェクトが到達不能になって回収される際に呼ばれます。

void close_file(void *obj, void *client_data) {
    fclose(((my_handle *)obj)->fp);     /* 回収前にファイルを閉じる */
}

my_handle *h = (my_handle *)GC_MALLOC(sizeof(my_handle));
h->fp = fopen("data.txt", "r");
GC_register_finalizer(h, close_file, NULL, NULL, NULL);

7.5 弱参照：キャッシュを GC に邪魔させない

「このオブジェクトを参照したいが、そのせいで回収を妨げたくはない」という 場面があります。典型例はキャッシュです。キャッシュが普通の（強い）参照で オブジェクトを握ると、それだけで永遠に生き続けてしまいます。

そこで 弱参照 (weak reference) を使います。弱参照は到達可能性の計算に 数えられないので、対象が他から参照されなくなれば回収され、弱参照側は自動的 に「空」になります。libgc では disappearing link（GC_GENERAL_REGISTER_- DISAPPEARING_LINK）という仕組みで弱参照を実現できます。対象が回収される と、登録したポインタ変数が自動的に NULL に書き換わります。

弱参照は、保守的GCの「素直なポインタを残しておかないと回収されうる」と いう性質を、逆に利用した道具だとも言えます。

7.6 スレッドとの付き合い方

最後に、マルチスレッド環境での注意です。保守的GCは「全スレッドのスタック とレジスタ」をルートとして走査しなければなりません。あるスレッドのスタック にしか参照がないオブジェクトを、別スレッドのGCが見落とすと回収されて しまうからです。

そのため、libgc を使うスレッドは GC に自分の存在を知らせる必要があります。 pthread_create を libgc 版でラップするか、GC_register_my_thread で スレッドを登録します。GC が走る際には、libgc が全スレッドをいったん停止 させてスタックを走査します。

ここまでで、保守的GCを「使う」「作る」「組み込む」の全体像が揃いました。 最終章では、これらを振り返り、保守的GCを「いつ選ぶべきか」を整理します。

8. まとめと、これから

長い旅をしてきました。最後にこの章で、保守的GCの全体像を一枚に描き直し、 「結局どんなときに保守的GCを選べばよいのか」という実践的な指針を示し、 さらに学びを深めたい人のための道しるべを置いておきます。

8.1 本書のまとめ

本書をひと言にまとめれば、保守的GCとは

「これはポインタかもしれない」という曖昧さを、安全側に倒すことで、 コンパイラの協力なしに成立させた mark-sweep GC

でした。各章で見てきたことを振り返りましょう。

• メモリ管理には、リーク・ダングリングポインタ・二重解放という落とし穴が あり、GC はその判断を処理系に肩代わりさせる技術でした（1. メモリ管理とGCの必要性）。
• GC の中心は到達可能性で、参照カウント・mark-sweep・コピーGC という基本 アルゴリズムがありました。保守的GCはオブジェクトを動かさない mark-sweep を土台にします（2. GCの基本アルゴリズム）。
• 「保守的」とは、型情報やスタックマップを使わず、値の見た目だけでポインタ を推測し、迷ったら生かす方針でした。その代償が偽ポインタでした （3. 保守的GCとは何か）。
• libgc は malloc を GC_MALLOC に置き換えるだけで使え、ポインタを含む かどうかで GC_MALLOC と GC_MALLOC_ATOMIC を使い分けます （4. libgc を使ってみる）。
• libgc はサイズ別ブロック構造で高速にアドレスを逆引きし、スタック・レジ スタ・静的領域を保守的に走査し、内部ポインタを扱い、ブラックリスティング で偽ポインタに備えていました（5. libgc の裏側）。
• 保守的GCは健全性を完全に保証する一方で完全性を犠牲にし、64ビット環境では 偽ポインタの確率が極めて小さく、空間使用量にも理論的な上界が与えられる のでした。mostly-copying なら部分的にコンパクションもできました （6. 保守的GCの理論的背景）。
• Ruby は「スタックだけ保守的、ヒープは正確」というハイブリッドで、自作 言語には完全に保守的な libgc を最小の労力で組み込めました （7. 言語処理系への組み込み）。

8.2 保守的GCを選ぶべきとき・避けるべきとき

これらを踏まえ、保守的GCの長所と短所を一覧にします。

「移動できない」という制約は、コンパクション（断片化の解消）だけでなく、 世代別GCにおける新世代から旧世代へのオブジェクト昇格や、 連続した空き領域へポインタをずらすだけで割り当てが完了するバンプポインタ割り当てなど、 現代の高性能GCが多用する手法全般に影響します。

この表から、選ぶべき場面の指針が導けます。

8.3 GC か、手動管理か

そもそも「GC は手動のメモリ管理より遅いのではないか」という素朴な疑問が あるかもしれません。この問いには、Hertz と Berger による有名な定量評価が 一つの答えを与えています Hertz and Berger^{[Matthew, 2005]}。彼らの測定 では、十分なメモリ（おおむね実使用量の5倍程度）が与えられれば、優れた GC は手動メモリ管理に匹敵する性能を出す 一方、メモリが切り詰められると GC の性能は急速に悪化します。つまり GC の損得は「メモリの余裕」と引き換え だ、という構図です。

保守的GCはここにもうひとつのトレードオフ——偽ポインタによる余分な保持—— を加えますが、本書で見たとおり、それは64ビット環境と実装上の工夫によって 実用的な水準に抑えられています。Zorn や Detlefs らの古典的な測定も、 保守的GCが多くの実プログラムで現実的に機能することを裏づけています Zorn^{[Benjamin, 1993]}, Detlefs et al.^{[David, 1994]}。

8.4 さらに学ぶために

本書は入門書なので、踏み込まなかった話題がたくさんあります。世代別GC、 インクリメンタル/並行GC、リージョン推論、Rust のような所有権ベースの 静的メモリ管理——どれも豊かな世界です。次の一歩として、以下を強くお勧め します。

• GC全般の地図を得たい人へ：Wilson の survey Wilson^{[Paul, 1992]} は、本書で触れた各アルゴリズムを一望できる定番の入門サーベイです。
• 本格的に深めたい人へ：Jones・Hosking・Moss の『The Garbage Collection Handbook』Jones et al.^{[Richard, 2023]} は、現代GCの 事実上の標準教科書です。保守的GCも一章を割いて扱われています。
• 保守的GCの原典に当たりたい人へ：Boehm と Weiser の1988年の論文 Boehm and Weiser^{[Hans-Juergen, 1988]} と、空間効率を論じた Boehm の論文 Boehm^{[Hans-Juergen, 1993]} は、本書の内容を一次資料で確かめる出発点です。

保守的GCという、一見大胆で、しかし理論的にきちんと裏打ちされた技術を巡る 旅は、ここでひとまず終わりです。あなたの次のプロジェクトで、この「疑わしき は生かす」精神が役に立つことを願っています。

A. 付録：libgc クイックリファレンス

本書で登場した libgc（Boehm-Demers-Weiser GC）の主な API と設定を、用途別 にまとめます。それぞれ「何をするものか」「いつ使うか」を添えてあるので、 本文を読み終えたあとの実装の手引きとして使ってください。詳細は公式の ヘッダ gc.h と配布物のドキュメントが一次資料です。

A.1 初期化

GC を使い始める前の準備に関わる関数です。

初期化は「とりあえず最初に GC_INIT() を呼ぶ」と覚えておけば、大半の 場面で困りません。組み込み先のプログラムがいつ libgc に最初に触れるか 読みにくいときほど、明示的な初期化が効いてきます。

A.2 メモリの確保

本書の中心となる確保系の関数です。free を書かないのが基本スタイルで、 確保関数の選択（特に atomic かどうか）が偽ポインタの抑制に直結します。

A.3 GC の制御と統計

GC を手動で起こしたり、状態を覗いたりする関数です。デバッグや性能測定で 役立ちます。

GC_get_heap_size() を定期的に表示すると、本文の最初のサンプルのように、 ヒープが頭打ちになって安定する様子が観察できます。GC が効いている確認に うってつけです。

A.4 ファイナライザと弱参照

オブジェクトの回収に合わせた後始末（ファイナライザ）と、回収を妨げない 参照（弱参照）のための仕組みです。本書 7. 言語処理系への組み込み の内容に対応 します。

A.5 マルチスレッド

スレッドを使うプログラムで、各スレッドのスタックを GC に走査させるための 登録に関わる関数です。

スレッド対応でビルドした libgc が前提です（./configure --enable-threads=posix など）。「オブジェクトに触れるスレッドはすべて登録する」が鉄則でした。

A.6 ビルドと環境変数

libgc は再コンパイルなしに、環境変数で挙動を調整できます。実験や運用時の チューニングに便利です。

リンク時のオプションは本文のとおり -lgc が基本です。ヘッダやライブラリ が標準の場所になければ -I／-L でパスを補います。

cc -o prog prog.c -lgc                      # 基本
GC_PRINT_STATS=1 ./prog                      # GC の様子を観察しながら実行