ルート集合と到達可能性¶

トレースを行うガベージコレクタは、「もう使われない」オブジェクトを回収します。ではエンジンは、あるオブジェクトが「まだ使われる」かどうかをどう判断するのでしょうか。答えは到達可能性です。プログラムが確実に参照している値の集合(ルート集合)を出発点に、そこから参照をたどって到達できるオブジェクトを「生きている」とみなし、たどり着けないものを回収します。この仕組みが正しく働くかどうかは、ひとえにルート集合を過不足なく把握できているかにかかっています。ルートを一つ見落とせば、まだ使われる値が誤って回収され、解放後のメモリを参照する use-after-free を招きます。逆に不要なものまでルートに含めれば、回収されるべきメモリがいつまでも残りリークになります。この章では、何をルートに含めるべきか、到達可能性をどうたどるか、そして実装で陥りやすい罠とその検出手法を扱います。

到達可能性という考え方¶

トレース型 GC(前章「GC 方式の選択」で扱ったマーク&スイープや世代別など)は、参照カウント方式と違い、オブジェクト自身が「自分が何回参照されているか」を持ちません。代わりに、回収のたびにオブジェクトグラフをたどり直します。

• ルート集合 (root set): プログラムが今この瞬間に、他をたどらずとも直接触れられる値の集合。ここが到達可能性の出発点になる。
• マーキング (marking): 各ルートから参照をたどり、到達できたオブジェクトに「生きている」印を付ける。印の付いたオブジェクトが参照する先も再帰的にたどる。
• スイープ (sweep): マーキングが終わったあと、印の付かなかったオブジェクトを回収する。

flowchart LR
    subgraph roots["ルート集合"]
      g["グローバル"]
      s["値スタック"]
      f["コールフレーム"]
    end
    g --> o1["生存A"]
    s --> o2["生存B"]
    f --> o3["生存C"]
    o1 --> o4["生存D"]
    subgraph garbage["到達不能: 回収対象"]
      x1["ゴミX"] --> x2["ゴミY"]
      x2 --> x1
    end

したがって GC の正しさは、次の二つの命題に還元されます。

• ルート集合が完全であること: プログラムが参照しうる値は、すべてどこかのルートから到達できなければならない。
• マーキングが網羅的であること: 生きているオブジェクトが参照する先は、一つ残らずたどられなければならない。

どちらか一方でも破れると、生きている値が回収される可能性が生まれます。ルート集合の完全性はこの章の主題であり、マーキングの網羅性は後半の罠で扱います。

何をルートに含めるか¶

ルート集合は「プログラムの実行状態そのもの」から導かれます。実行中の VM が、間接参照を経ずに直接手にしている値がすべて対象です。代表的なものを挙げます。

• グローバルオブジェクト: グローバルスコープの変数・組み込みオブジェクト(Object・Array などのコンストラクタやそのプロトタイプ)は、常にグローバルオブジェクトから到達できる。realm(実行領域)が複数あるなら、その各々のグローバルがルートになる。
• 値スタック(オペランドスタック): 実行中のバイトコードが計算途中の値を積んでいくスタック。ここに積まれた一時値はすべて生きている。
• アクティブなコールフレームとローカルスロット: 現在呼び出し中の各関数フレームが持つローカル変数・引数のスロット。呼び出しの入れ子の分だけフレームが積まれ、そのすべてがルートになる。
• VM のレジスタ・一時領域にある値: 命令の実行途中で、スタックにもフレームにも属さず一時的に保持している値。たとえば「スタックから取り出したがまだ使い切っていないオペランド」「現在呼び出そうとしている関数(callee)」「new.target」「巻き戻し中に伝播させている保留中の例外」「保存中の完了値(completion value)」など。これらは寿命が短く見落とされやすいが、確かに生きている。
• realm ごとの内部構造: realm やコンテキストが保持する内部テーブル(組み込みの内部参照、シンボルレジストリ、その realm 固有の設定など)。
• ホストが登録した永続的なハンドル: エンジンを組み込むネイティブ側が「回収しないでほしい」と登録した値(後述のハンドルスコープ・永続ハンドル)。

逆に、ルートに含めてはならない/含める必要がないものもあります。両者を対比すると次のようになります。

原則は「間接的に到達できるものはルートにしない」ことです。あるオブジェクトが生きたオブジェクトのフィールドから参照されているなら、それはマーキングで自然にたどられます。ルートに登録すべきは、そうしたフィールドをたどっても届かない、実行状態が直接握っている値だけです。ここを取り違えて到達可能なものまで片端からルートに積むと、寿命の管理が破綻してリークの温床になります。

マーキングはすべての参照をたどる¶

ルートが出そろったら、各ルートを起点にオブジェクトグラフをたどります。マーキングの骨子は単純です。

mark(obj):
    obj がすでに印付きなら return   # 循環参照でも止まる
    obj に印を付ける
    obj が参照するすべての値 v について:
        mark(v)

ここで決定的に重要なのは、「obj が参照するすべての値」を一つも漏らさないことです。オブジェクトの種類ごとに、参照を持つフィールドは異なります。

• 通常のオブジェクト: プロパティ値、プロトタイプ、形状(hidden class)経由の格納先。
• 配列: 要素、および dense/sparse どちらの表現に入っているか。
• 関数(クロージャ): 捕捉したアップバリュー、束縛された this、所属する realm。
• そのほか: Map/Set の要素、Proxy のターゲットとハンドラ、Promise が握る値、束縛関数(bound function)のターゲットと引数など。

いずれの種類でも、参照を持つフィールドを一つでもマーク処理から漏らすと、そのフィールドの参照先が「まだ到達可能なのに印が付かない」状態になり、スイープで回収されてしまいます。回収後もそのフィールドは古いアドレスを指し続けるため、次にそこをたどった瞬間に解放済みメモリへアクセスします。これは典型的な use-after-free です。

この漏れは、オブジェクトのレイアウトを変更したときに紛れ込みやすいものです。新しい参照フィールドを追加したのに、対応するマーク処理を更新し忘れると、平時は動いてしまうため気づきにくく、GC のタイミング次第で忽然と壊れます。対策は、マーク処理をオブジェクトのレイアウト定義と一体で管理し、フィールドを増減させたら必ずマーク処理も見直すことです。

実装上の罠¶

ルート集合とマーキングの誤りは、いずれも「その瞬間だけ到達不能に見える生きた値」を生み、GC のタイミングに依存して発現します。ここでは実際に踏みやすい三つのパターンを扱います。

罠1: 一時値のルート漏れ¶

もっとも多いのが、一時的な置き場所にしかない値が、その隙に GC で回収される罠です。

値スタックやコールフレームはルートに含まれますが、そこから値を取り出してネイティブのローカル変数や VM の一時レジスタに移した瞬間、その値はルート集合の外に出ます。取り出してすぐ使い切るなら問題ありませんが、その間に GC が走りうる処理を挟むと危険です。

古典的なのは型強制(coercion)を伴うケースです。ある演算がオペランドを二つ必要とするとき、まず両方を(ルートである)スタックからポップしてローカル変数に受けたとします。次に一方を仕様どおりプリミティブへ変換しようとして valueOf や toString、あるいは Symbol.toPrimitive を呼ぶと、そこでユーザ定義の JavaScript が動きます。ユーザコードはオブジェクトを大量に確保でき、その途中で GC を誘発しえます。このとき、先にポップしておいたもう一方のオペランドは、もうスタックにもフレームにもなく、どのルートからも到達できません。GC はそれを回収し、変換から戻ってきたコードは解放済みの値を使い続けます。

対策は、再入(ユーザコードの実行)を挟むステップの前に、生かしておきたい値をルート集合から外さないことです。具体的には次のいずれかです。

• ポップを再入ステップのあとまで遅らせ、値をスタック(ルート)に置いたまま変換を行う。
• 取り出さざるをえないなら、その値を後述のピン留めリストに登録し、コレクタが常にマークするようにする。

要は「ユーザコードが動きうる区間をまたいで生かす値は、必ず何らかのルートに繋いでおく」という一点に尽きます。

罠2: マーキング漏れ¶

前節で述べたマーキングの網羅性の裏返しです。オブジェクトに新しい参照フィールドを足したのに、コレクタのマーク処理がそれをたどらない、という漏れが起きます。

このバグの厄介さは、そのフィールドの参照先が他の経路からも到達可能なうちは何も起きない点にあります。別の生きたオブジェクトが同じ先を参照していれば、そちら経由でマークされるため表面化しません。ところがその別経路が消えた瞬間、参照先はマークされなくなり回収されます。発現がデータの形と GC のタイミングに依存するため、再現が難しく原因の特定に手間取ります。

予防はマーク処理を常に網羅的に保つことです。オブジェクトのレイアウトを変えるたびにマーク処理を突き合わせてレビューする、参照フィールドの追加とマーク処理の更新を同じ変更として扱う、といった規律が有効です。フィールド定義からマーク処理を機械的に導ける構造にできれば、人手の漏れそのものを減らせます。

罠3: 構築途中のオブジェクト¶

オブジェクトや realm を組み立てている最中に、まだどのルートにも繋がっていない段階でコードが走り、その隙に GC がその半完成の対象を回収してしまう罠です。

初期化の途中で JavaScript やネイティブ処理を呼ぶ場面は珍しくありません。たとえば、新しいオブジェクトを確保したあとにその内部を初期化する処理がさらにオブジェクトを確保する、あるいは二つ目の realm を立ち上げる際に、その realm 上で組み込みを準備するコードを実行する、といった具合です。このとき、まだ構築中の対象がどのルートからも到達できないままだと、初期化の途中で誘発された GC がそれを「到達不能」と判断して回収します。初期化から戻ったコードは、すでに解放された対象へ書き込みを続け、以降その対象を指す参照はすべてダングリング(宙ぶらりん)になります。

対策は、確保した対象を、コードを走らせる前にルートへ登録することです。オブジェクトなら、これから初期化で再入が起こりうるなら先にピン留めしておき、初期化が終わって適切なルート(親オブジェクトのフィールドや realm のテーブル)に繋いだらピン留めを外します。realm のセットアップも同様で、realm を管理構造に登録してから、その上で組み込みを準備するコードを動かします。「割り付けてから、まだ何も繋がっていないうちにコードを走らせない」を徹底することが要点です。

値を生かし続ける仕組み¶

以上の罠はすべて「生かしたい値をルートに繋ぎ続けられていない」ことに起因します。そこでエンジンは、値を明示的にルート集合へ組み込むための道具立てを用意します。ここでは種類だけ導入し、ネイティブ境界での具体的な使い方は次章「ネイティブコードとの相互作用と GC 安全性」で扱います。

• ハンドルスコープ (handle scope): ネイティブ関数の内部で、エンジンの値を安全に保持するための一時的な入れ物。スコープの間だけ、そこに登録された値をコレクタがルートとして扱い、スコープを抜けると一括で解除する。ネイティブ関数がローカルに握る一時値をまとめて保護するのに向く。
• 永続ハンドル (persistent handle): スコープの寿命を越えて、ホストが明示的に解放するまで値を生かし続けるハンドル。ネイティブ側が長期に保持するオブジェクト(コールバックや設定値など)に使う。解放を忘れるとリークになるため、寿命の管理はホストの責任になる。
• ピン留めリスト (pin list): エンジン内部が持つ「コレクタが常にマークする値」の集合。一時値のルート漏れ(罠1)や構築途中のオブジェクト(罠3)を防ぐため、再入をまたいで生かしたい値を短期間ここに登録し、用が済んだら外す。

三者は寿命と用途で使い分けます。

いずれも「コレクタに、このアドレスは生きているとみなさせる」ための手段である点は共通です。違いは、誰が(ホストか、エンジン内部か)どれだけの期間、生存を保証するかにあります。

見落としたルートを検出する¶

ルート漏れやマーキング漏れの本質的な難しさは、平時にはまず発現しない点にあります。GC がたまたまその危険区間で走らなければ何も起きず、テストも通ってしまいます。そこで、潜在的な漏れを意図的に炙り出す手法が要ります(詳細は第VI部「メモリ安全性の検出」で扱いますが、原理をここで述べておきます)。

• GC ストレスモード: 割り付けのたび(あるいはほぼ毎回)に GC を強制的に走らせるビルド構成。ルート漏れは「危険区間で GC が走ること」で初めて発現するため、常に走らせれば潜在バグが確実に踏まれるようになり、再現困難だった不具合が決定的に再現するようになる。
• 回収オブジェクトのポイズニング/隔離: スイープで回収したメモリを、すぐ再利用せずに埋めておく(既知の毒パターンで塗りつぶす)か、しばらく再利用禁止の隔離状態に置く。こうすると、ダングリング参照をたどった瞬間に毒パターンや無効アクセスとして即座に破綻する。ポイズニングをしないと、回収済みメモリがすぐ別の値で再利用され、ダングリング参照が「たまたま妥当に見える別の値」を読んでしまい、バグが黙って結果を汚すだけで気づけない。

この二つを組み合わせると、ルート漏れは「GC ストレスで必ず回収され、ポイズニングで必ず即死する」ようになり、静かに壊れる不具合が、原因の近くで確定的にクラッシュする不具合へと変わります。デバッグの難易度は劇的に下がります。開発・テスト時にはこの構成を常用し、本番ビルドでは外す、という運用が現実的です。

まとめ¶

• トレース型 GC は、ルート集合から到達できるかどうかで生死を判定する。ルートの過不足は、それぞれ use-after-free とリークに直結する。
• ルート集合には、グローバルオブジェクト・値スタック・アクティブなコールフレームとローカルスロット・VM の一時値(callee・保留中例外・完了値など)・realm 内部構造・ホスト登録のハンドルを含める。間接的に到達できる値はルートにしない。
• マーキングは各ルートから再帰的に到達可能オブジェクトを印付けする。オブジェクトの種類ごとに、参照を持つフィールドを一つも漏らさずたどることが必須。
• 実装上の罠は「生かしたい値をルートに繋げていない」ことに集約される。一時値のルート漏れ・マーキング漏れ・構築途中のオブジェクトの三つが代表的。
• 値を生かす道具として、ハンドルスコープ・永続ハンドル・ピン留めリストがある。寿命と保証の主体で使い分ける。
• 見落としたルートは、GC ストレスモードとポイズニング/隔離を組み合わせることで、静かなバグを決定的なクラッシュに変えて検出できる。

参考文献¶

• ECMA-262 (ECMAScript 言語仕様) — 実行コンテキスト・レキシカル環境・完了値など、実行中に生存すべき状態の意味論の一次資料。