WeakMapと世代別GC

Omoikaneでhttps://tokyo6.tokyo/を開くと、スクリプトの実行中にSIGSEGVで終了する不具合がありました。Issue #1223ではGUIだけでなく、画面を画像へ出力するscreenshotでも再現しています。Linux aarch64のDocker開発環境とXvfbで再現したデバッグビルドのバックトレースは、BoaのGCがオブジェクトへの参照をたどる途中で止まっていました。

PR #1260で修正したのは、ephemeronという条件付き参照と、世代別GCの組み合わせです。古いオブジェクトから参照されている若いオブジェクトが、major GCの後のminor GCで回収されていました。その後のmajor GCが解放済みの参照をたどり、クラッシュしていました。

WeakMapの基本的な使い方は、前の記事WeakMapとは何かで説明しました。ここでは、参照されているオブジェクトがなぜ消えたのかを、GCの実装から見ていきます。実装の説明は、10月8日に確認したmainのコミットと、修正PRの差分・回帰テストに基づいています。

WeakMapの「弱い」はどこにかかるか

通常のMapは、登録したキーと値を保持します。Mapが生きていれば、そのMapだけが参照しているキーも値も、引き続き使えます。

WeakMapでは、登録したことだけを理由にキーを生かし続けません。たとえば、オブジェクトに補助的な情報を付けたい場合に使えます。

const metadata = new WeakMap();
let element = { name: "button" };

metadata.set(element, { clicks: 0 });
console.log(metadata.get(element).clicks); // 0

element = null;

最後の代入で、ここに示したコードからキーへ到達する通常の参照がなくなります。WeakMapへの登録だけでキーを保持することはありません。ただし、代入直後に必ず回収するという意味ではありません。回収の時期はGCに依存し、JavaScriptからこの瞬間の回収を要求するコードでもありません。ECMAScriptのWeakMap仕様にも、回収時期の制約と、キーを列挙する仕組みを持たない理由が記されています。

一方、キーをまだ使える間は、metadata.get(element)で値を取り出せなければ困ります。値まで普通の弱参照にすると、キーが生きているのに補助情報だけ消えてしまいます。

つまり、WeakMapのエントリには「キーが到達可能なら値を保持する」という条件が必要です。キーと値の両方を弱くするだけでは、この関係を表現できません。

値からキーへ戻る参照

キーだけを弱参照にして、値を無条件に強く保持する実装にも問題があります。

const metadata = new WeakMap();
let element = { name: "button" };

metadata.set(element, { owner: element });
element = null;

値のownerがキーを参照しています。WeakMapから値を常に強くたどると、値からキーへ戻れてしまいます。その結果、エントリの外からキーを使うコードがなくなっても、WeakMap自身が値を経由してキーを生かし続けます。

ここで使うのがephemeronです。キーの生存が確認できるまで、エントリから値への参照を有効にしません。値からキーへの参照があっても、その参照だけで自分自身の生存条件を満たすことはできません。

flowchart LR
    R[通常のroot] --> K[キー]
    W[生きているWeakMap] --> E[エントリ]
    E -. キーの到達を条件に保持 .-> V[値]
    V --> K

図のrootからキーへの線がなくなり、ほかにもキーを生かす参照がなければ、エントリから値への線を使ってキーを救うことはできません。反対に、値そのものが別のrootから強く参照されていれば、値のownerを通じてキーも到達可能になります。判定するのはエントリの外も含めた参照全体です。

Boaでは、この条件付き参照をEphemeronとEphemeronEdgeで表しています。これはOmoikaneに組み込まれたBoaの実装です。JavaScriptのWeakMapの振る舞いと、それを実現するGC内部の型は分けて読む必要があります。

一度の走査では決まらない

ephemeronのキーが生きているかどうかは、最初の強参照の走査だけでは決まらないことがあります。

二つのエントリを考えます。最初のキーkeyAはrootから到達できます。その値valueAは、二つ目のキーkeyBを強く参照しています。

root → keyA

エントリA: keyAが生きていればvalueAを保持
valueA → keyB

エントリB: keyBが生きていればvalueBを保持

最初に通常の強参照をたどると、keyAが生きていると分かります。次にエントリAの条件を満たすので、valueAをたどれます。そこで初めてkeyBも生きていると分かり、エントリBからvalueBをたどれるようになります。

エントリBを先に調べていた場合、初回は条件を満たしていません。そこで「キーは死んでいる」と確定すると誤回収になります。未解決のエントリを残し、値の走査で新たな到達関係が分かったら再び評価する必要があります。

新しい到達関係が増えなくなった状態を、固定点と呼びます。Boaのmark_heapも、未解決のephemeronをpending_ephemeronsへ残し、条件を満たした値を走査する処理を繰り返します。未解決の件数が変わらなくなると、このループを終えます。

この段階より前に見た「未到達」は、最終結果とは限りません。今回の不具合では、この判定の時期が世代別GCの管理情報に影響していました。

古い親から若い子への参照

世代別GCは、オブジェクトを世代に分けて管理します。Boaのこの実装では、新しい割り当てを若い世代で扱い、collectionを生き残ったものを古い世代へ昇格させます。

minor GCは若い世代を回収対象にし、major GCは古い世代を含めて到達関係を調べます。minor GCのたびに古いオブジェクトをすべて走査すると、若い世代だけを対象にする利点が薄れます。そこで、古い世代から若い世代への参照を別に記録します。

root → 古い親 → 新しく作った若い子

古い親に新しい子を格納した場合、若い子は親を通じて使えます。minor GCが若い世代だけを見て、親からの参照を見落とすと、子を回収してしまいます。

この書き込みを検知してGCへ知らせる仕組みを、write barrierと呼びます。今回関係するBoaの方式では、書き換えられた古い親をdirty parentとして記録し、minor GCでその親を走査します。dirtyは「内容が変更され、子への参照を確認し直す必要がある」という意味です。

mark_minorは、こうした記録やrootを起点に、若い世代の到達関係を解決します。古い親はminor GCの回収対象でなくても、若い子を見つけるための走査対象になるわけです。

major GCの後で子が消えた

問題の参照関係は、親自身がephemeronの値になっている形でした。

root → キー
生きているephemeron --キーの到達を条件に保持--> 古い親
古い親 → 若い子

キーは生きています。したがって親も生きていて、親から参照される子も保持しなければなりません。ただし、親に到達できると分かるのは、ephemeronを処理する段階です。

修正前のmajor GCでは、dirty parentの記録を処理する時点で親が未到達だと、その記録が失われていました。この時点ではephemeronの固定点をまだ解決していません。後からキーの到達が確認されると親と子はmarkされ、major GCでは回収されずに残ります。しかし、次のminor GCへ渡すべきdirty parentの記録は消えています。

古い親へ若い子を書き込む
  → dirty parentとして記録
  → major GCの初期走査では親がまだ未到達
  → 親の記録を失う
  → ephemeronを解決し、親と子を生かす
  → 次のminor GCで親から子への参照を見落とす
  → 子を回収

major GCで親と子を生かす判定が正しくても、それだけでは足りません。次のminor GCは古い世代全体を再走査しないため、その走査に必要な記録も保持する必要があります。

子を回収した時点で、親には解放済みの子への参照が残ります。そこで必ず即座にクラッシュするとは限りません。PRの原因説明では、後のmajor GCがその参照をたどった時にSIGSEGVになっています。バックトレースに現れたmark処理は、不正な参照を作った場所から時間を置いて、それを使用した場所でした。

記録を捨てる時期を変える

修正では、dirty parentの記録をephemeronの解決まで残します。

mark_heapの変更箇所は、取り出した親をdirty_parents_pending_sweepへ保存します。すでに到達可能な親は必要な再走査を行いますが、まだmarkされていない親の記録も残します。

その後、ephemeronを含む到達関係を解決してから、retain_major_rememberedで最終的に到達可能な親だけを残します。これにより、ephemeronを通じて後から生存が分かった親も、次のminor GCで参照元として使えます。

ここで、dirty parentの記録そのものをmajor GCのrootにしてはいけません。単に書き換えられたという理由で親を生かすと、本来は回収できる親と子を保持してしまいます。記録は走査のための手掛かりであり、major GCでの生存を保証する所有者ではありません。修正は最終的なmark結果に従って記録を選別します。

同じPRには、minor GCのmarkをクリアする時期の修正もあります。オブジェクトとephemeronの昇格処理が終わるまで、今回のminor GCで付けたmarkを保持します。

以前の順番では、若い値のmarkを先にクリアした後、ephemeronの昇格処理がその値を走査して、再びmarkする可能性がありました。そのmarkが次のcollectionまで残ると、新しく書き込まれた参照の走査を省いてしまいます。到達済みという印は、どのcollectionのものかを揃える必要があります。

現在は昇格処理の後にclear_survivor_minor_marksを呼び、若い世代に残ったものと、今回昇格したもののmarkをまとめてクリアします。次のminor GCは、この前のcollectionの印に邪魔されずに参照を調べられます。

解放済みの子を読む前に確認する

回帰テストのmajor_collection_preserves_dirty_parent_reached_through_ephemeronは、問題の参照関係をGCの型で直接作ります。

まずキーと親をrootし、minor GCを二度実行して親が古い世代に入ったことを確認します。その親へ若い子を書き込み、親の直接のrootを外して、ephemeronの値として保持させます。キーのrootは残します。

*parent.child.borrow_mut() = Some(GcEdge::new(42_u32));
let ephemeron = Ephemeron::new(&key, parent.into_edge());
force_collect();
force_minor_collect();

この部分はテストからの抜粋です。parent.into_edge()によって、親を直接保持するrootから、GCがたどる参照へ変えています。major GCの後にminor GCを実行し、その後も親と子が残っているかを確認します。

検証は、いきなり子の値42を読むところから始めません。子がすでに回収されていれば、その読み出し自体が解放済みメモリへのアクセスになります。

先に子のポインタがGCの若い割り当て一覧、または古い割り当て一覧に存在することをassertします。その確認が通ってから、子の値を読みます。PRには、修正前はこのallocation membershipのassertで失敗し、修正後に通ると記録されています。クラッシュするまで待つ代わりに、誤回収が起きた段階でテストを失敗させる構成です。

対になるdirty_ephemeron_parent_is_reclaimed_when_its_key_diesでは、キーのrootも外してからmajor GCを実行します。ephemeronが値を持たなくなり、親と子の強参照オブジェクトの割り当て数がゼロになることを確認します。

生きたキーなら親と子を保持し、キーが死んだら回収する。この両方を試すことで、誤回収を止めるために到達不能なオブジェクトまで残してしまう修正を検出できます。

実ページでの確認

PR #1260の検証記録では、boa_gcのテスト53件、ルート全体のテストとdoc-test、GUI付きbuildが成功しています。保存した最小再現ページはscreenshotで2回、保存した全ページは1回実行し、いずれも終了コード0でした。実際のhttps://tokyo6.tokyo/もscreenshotで終了コード0になっています。

保存ページと実サイトをXvfb上のGUIで開いた試験では、タイトル表示後15秒間、プロセスの生存と描画を確認しています。これはPRに記録された条件での結果です。この記事のために、別環境で再実行した結果ではありません。

以前のgetter返値がinline cache更新中のGCで回収された件では、値がVMレジスタへ入る前の一時rootが不足していました。今回は、キーとephemeronを通じて到達可能な親があり、その親から子への参照もありました。失われていたのは、世代をまたぐ参照を次のcollectionで見つけるための記録です。

修正後は、ephemeronの固定点を解決した最終的なmark結果を使ってdirty parentを残し、minor GCのmarkは昇格処理が終わってからクリアします。条件付き参照の生存判定と、次の世代別collectionへ渡す管理情報を、この順番で揃えています。