C++とJSを跨ぐ
クロスコンポーネント
ガベージコレクタ
1
自己紹介
服部慶士
大学・大学院は電子工学科
Google Japan (2011 - 現在)
ソフトウェアエンジニア
ずっとChromeブラウザチーム
最初は <input type=date>や<select>のポップアップUIを実装
今はメモリ管理関連（GC・メモリ削減・malloc）の開発を担当
2
本日のお話
3
ブラウザ開発とガベージコレクタ
4
JavaScriptはGCを使うマネージド言語
JavaScript(JS)のメモリ管理には仕様上ガベージコレクタ(GC)が必須
GCを使うプログラミング言語はマネージド言語と呼ばれる
マネージド言語のユーザーはオブジェクト寿命の管理の手間が大幅軽減
JSを実装するV8にはGCが実装されている
5
V8に実装されたMark-sweep-compact GC
V8のGCはコードネームOrinocoと呼ばれ�Mark-sweep-compact GCを実装している
オブジェクトはお互いを参照しあいobject graphを形成する
mark phaseでは、グローバル変数などのrootから、このobject graphをトラバース(trace)し、rootから到達可能なオブジェクトに印（mark）をつける
sweep phaseでは印のついていないオブジェクトを開放する
compaction phaseでは残ったオブジェクトを隙間を詰めるようにコピーする、デフラグ処理をする
6
V8に実装されたMark-sweep-compact GC
V8のGCはコードネームOrinocoと呼ばれ�Mark-sweep-compact GCを実装している
オブジェクトはお互いを参照しあいobject graphを形成する
mark phaseでは、グローバル変数などのrootから、このobject graphをトラバース(trace)し、rootから到達可能なオブジェクトに印（mark）をつける
sweep phaseでは印のついていないオブジェクトを開放する
compaction phaseでは残ったオブジェクトを隙間を詰めるようにコピーする、デフラグ処理をする
7
V8に実装されたMark-sweep-compact GC
V8のGCはコードネームOrinocoと呼ばれ�Mark-sweep-compact GCを実装している
オブジェクトはお互いを参照しあいobject graphを形成する
mark phaseでは、グローバル変数などのrootから、このobject graphをトラバース(trace)し、rootから到達可能なオブジェクトに印（mark）をつける
sweep phaseでは印のついていないオブジェクトを解放する
compaction phaseでは残ったオブジェクトを隙間を詰めるようにコピーする、デフラグ処理をする
8
V8に実装されたMark-sweep-compact GC
V8のGCはコードネームOrinocoと呼ばれ�Mark-sweep-compact GCを実装している
オブジェクトはお互いを参照しあいobject graphを形成する
mark phaseでは、グローバル変数などのrootから、このobject graphをトラバース(trace)し、rootから到達可能なオブジェクトに印（mark）をつける
sweep phaseでは印のついていないオブジェクトを開放する
compaction phaseでは残ったオブジェクトを隙間を詰めるようにコピーする、デフラグ処理をする
9
V8に実装されたMark-sweep-compact GC
V8のGCはコードネームOrinocoと呼ばれ�Mark-sweep-compact GCを実装している
オブジェクトはお互いを参照しあいobject graphを形成する
mark phaseでは、グローバル変数などのrootから、このobject graphをトラバース(trace)し、rootから到達可能なオブジェクトに印（mark）をつける
sweep phaseでは印のついていないオブジェクトを開放する
compaction phaseでは残ったオブジェクトを隙間を詰めるようにコピーする、デフラグ処理をする
10
ブラウザ開発の天敵：GCのpause time
シンプルな実装なGCだと、GCを走らせている間はプログラムの実行を止める必要がある
GCを実行していて他の処理ができない時間をpause timeと呼ぶ
11
ブラウザ開発の天敵：GCのpause time
最近のウェブサイトはインタラクティブなアニメーションが多用される
ブラウザは60fpsで表示することが目標�16ms以内に１フレームの処理が終わらないと表示がカクカクに
16ms以内には、他にJS,recalc style,layoutも実行する必要がある
GCの性能として、スループットももちろん大事だが、�ブラウザ開発ではpause timeがとても大事
12
GC pause timeを短縮する工夫
V8 GCはpause timeを短縮する様々な工夫がされているのですが�ここでは基本の３つを紹介します
13
世代別GC
「ほとんどのオブジェクトは若いうちに死ぬ」という世代別仮説に基づき�ヒープをyoungジェネレーションとoldジェネレーションにわける
youngジェネレーションのゴミのみ高速に回収するMinor GC(Scavenger)と�全オブジェクト回収できる代わりに遅いMajor GCを使い分けられる
14
incremental GC
GCを休止可能にしてpause timeを細切れにする
GCを再開したときにはobject graphが変更されているかもしれないので�変更を監視するためのwriteバリアが必要
15
concurrent GC
別スレッドで、プログラムと並行してGCを行う
同時に同じオブジェクトにアクセスしてread/writeレースが起きるのを避け必要が
16
ブラウザ開発にとってGCを使う利点
GCを使うと、この二種類のバグのリスクが低減される
この二種類のバグは、どちらもブラウザ開発にとって超重要！
17
free()が忘れられてメモリリーク
うっかり出来た循環参照でfree()がされずメモリリークになるパターンがよくある
ブラウザのメモリ使用量はとても大事
ブラウザが原因のメモリリークは許されません！
18
free()が早すぎてdangling pointer
dangling pointerはuse-after-freeバグに繋がります
use-after-freeバグはクラッシュを引き起こすだけでなく�ハッカーの攻撃に利用される脆弱性になることが多い（例,例,例,例）
ブラウザにとってセキュリティは重要、脆弱性は一つでも減らしたい！
19
だからBlinkもGCにした
C++で書かれたBlinkはもともとreference counting
GCはブラウザ開発における重大バグのリスクを軽減できるので�OilpanプロジェクトでBlinkをGCに移行した
詳細は後ほど
20
ブラウザ開発とガベージコレクタ：まとめ
ブラウザはJSを使う以上、GCの実装は避けて通れない
ブラウザ開発で重要なのはGCのpause time
GCは工夫次第でpause timeの短縮が可能
メモリ管理のバグはブラウザにとって最重要課題
GCはそれらを解決する鍵になる
21
GCの欠点
GCの利点
Cross-component tracingとは
22
Chromeチームが目指した�DOM/JSメモリ管理について�この論文から
マネージド言語のVMを組み込む
マネージド言語のVMはcomponentとして�別の言語（非マネージド言語の場合も）で書かれたソフトウェアシステムの中に組み込まれることがある
Chromeもこのような異種混在ソフトウェアである
V8というJS VMが、C++で書かれたBlinkレンダリングエンジンに組み込まれている
23
cross-component referenceとは
このような異種混在ソフトウェアで�効率的な連携をするためには、�別のcomponentのオブジェクトへの直接ポインタを保持する必要がある
これをcross-component referenceと呼ぶこととする
cross-component referenceはオブジェクト活性(liveness)を決定しうる
よって何らかの方法でobject graphにも含める必要がある
24
Cross-component循環参照
一番簡単なのはcross-component referenceはroot referenceとして扱うという方法
しかしcross-component循環参照があるときにメモリリークを起こす
25
Cross-component循環参照の解決方法
普通は
しかしDOM APIは仕様上、循環参照が回避不能な場合も
システム全体の状況を把握してlivenessを推測するメモリ管理が必要
26
Cross-component tracingとは
cross-component循環参照の問題を解決するためには�異種componentの壁を超えてobject graphをtraceする必要がある
我々はこのテクニックをcross-component tracing (CCT)と呼んでいる
ブラウザ以外でCCTを使っている例は知る限りない
しかしブラウザには必須のテクニックとなっている
ChromeのCCT導入前の話からCCTの利点について説明する
27
Blinkとは
Chromeのレンダリングエンジン
C++でHTML/CSSが実装されている
HTMLDivElementやCanvasRenderingContext2DのようなDOM APIのオブジェクトがJSからはただのJSオブジェクトのように見えますが、本体はBlinkにある
28
V8とBlinkをつなげるbindings
JSオブジェクトはV8内でカスタムなオブジェクトモデルで実装されていて�BlinkのC++オブジェクトとは互換性がない
DOM APIを通してJSからアクセスできるBlinkのC++オブジェクトはwrappableと呼ばれる
JSがwrappableにアクセスすると、対応するJSオブジェクト、wrapperがV8側に作られる
JSコードがwrapperのプロパティをアクセスする際は、V8はBlink側のcallbackを呼び出して本体のC++オブジェクトwrappableに変更が加えられる
29
CCT以前のwrapperのメモリ管理
右の図はwindow.documentを実行したときのobject graphを表している
HTMLDocumentの本体であるwrappableとJS側のwrapperと２つのオブジェクトがあり、�相互に参照を持ち合っている
先に説明したとおり、これらの参照をrootとして扱ってしまうとメモリリークが起きるので…
wrapperからwrappableへはstrong reference�wrappableからwrapperはweak referenceを使っていた
30
CCT以前のwrapperのメモリ管理
右の図はwindow.documentを実行したときのobject graphを表している
HTMLDocumentの本体であるwrappableとJS側のwrapperと２つのオブジェクトがあり、�相互に参照を持ち合っている
先に説明したとおり、これらの参照をrootとして扱ってしまうとメモリリークが起きるので…
wrapperからwrappableへはstrong reference�wrappableからwrapperはweak referenceを使っていた
31
Wrapperの寿命
weak referenceを使うとwrapperだけ�先に解放されてしまうことがある
しかしwrapperとwrappableは原則として、寿命が一致しているべきである
右のような場合、aとbのwrapperは残しつつ、cは解放するにはどうすればよいか？
CCT以前なのでV8 GCからBlinkのobject graphは見えていない
32
Wrapperの寿命
weak referenceを使うとwrapperだけ先に解放されてしまうことがある
しかしwrapperとwrappableは原則として、寿命が一致しているべきである
右のような場合、aとbのwrapperは残しつつ、cは解放するにはどうすればよいか？
CCT以前なのでV8 GCからBlinkのobject graphは見えない
33
昔の手法：object grouping
Chromeバージョン57以前は�object groupingという手法を使っていた
DOMツリー内の参照関係はすべて双方向なstrong referenceという特性を利用
wrapperを所属するDOMツリーごとにグループに束ね、JS側からグループの中の一つのオブジェクトにでも到達可能ならグループ全体を残す
34
Object groupingの利点・欠点
Object groupingは実装が単純なのが利点
しかし弱点がありました
実装当時のウェブページでは、JSからDOMを変更する頻度が低かったので十分な性能だった
35
新しい手法：cross-component tracing
CCTはcross-component循環参照の問題を解決するために�システム全体を一個のマネージドヒープのように扱うという手法
まず、関係するcomponentのGCすべてを、別のcomponentにtraceできるように拡張する
CCTはそのうちの一つのcomponentのGCをmain tracerとして使う�main tracerの役割は全体の推移的参照閉包を算出し、循環参照を解除すること
他のcomponentのGCはremote tracerと呼び�main tracerの要請に応じて自分のobject graphをtraceをする役割を担う
36
CCTの動作
オブジェクトaをマークしたmain tracerはa′へのエッジを発見
しかしcross-component referenceなのでremote tracerにtraceを依頼
remote tracerはa′からb′をtraceし、bのtraceはmain tracerに依頼
trace終了後、main tracerがcを解放し�b′が解放可能になる
37
ChromeでのCCT
main tracer: V8 GC�remote tracer: Blink GC
最初はwrapperのみのCCTを実装（Wrapper Tracingプロジェクト）�全Blinkオブジェクトを対象にするとpause timeが長すぎるから
pause timeを短縮できるincremental markingをBlink GCに実装してから
全Blinkオブジェクトを対象にした完全なCCTを実装（Unified Heapプロジェクト）
詳細は後ほど
38
FirefoxのCCT
GeckoレンダリングエンジンはC++で書かれ、メモリ管理にはreference countingを使用
それに加えサイクルコレクタがC++、cross-component両方の循環参照を回収する
実装はBacon and Rajan [2001]をもとにしているがconcurrentではない
サイクルコレクタはゴミ候補オブジェクトのセットを保持する�reference countが下がったときにセットに追加され、上がったときに除かれる�サイクルコレクタはこのセットの中から循環参照を見つけて回収する
pause timeを短縮するためインクリメンタルに動作し、ゴミ候補オブジェクトのセットを最小限にするための工夫がされている
39
SafariのCCT
WebKitはC++で書かれ、メモリ管理はreference counting
wrapperのメモリ管理には二種類の仕組みを使っている
WebKitのJS VM(JavaScriptCore)のGC（Riptide）はincrementalでconcurrentなGCであるが、C++オブジェクトとの循環参照回収をする部分はアトミックに行われている
40
主要ブラウザでのCCT
wrapperのメモリ管理は三者三様
安全性、メモリリークを防ぐ有効性、pause timeの短さ、すべてを実現するためにみんな工夫をしている
しかしCCTのテクニックを取り入れている点では共通
41
おまけ：CCTでメモリリークのデバッグが容易に
ChromeにはメモリリークをデバッグするためのHeap Snapshotというツールがある
CCTでretaining pathがDOM/JS境界を跨ぐ場合でも正確に表示できるように
42
Cross-component tracingとは：まとめ
CCTはcross-component循環参照によるメモリリークを解決する手法
ブラウザ開発では必須のテクニックとなっている
Chromeは完全なCCTを実装
43
Chromeのcross-component tracing実装
44
実装およびその過程を紹介
Oilpanプロジェクト
Chromeバージョン50でリリース
Blink GCを実装しreference countingからの移行を行う壮大なプロジェクト
45
Oilpanプロジェクトの難しさ
46
サンプルコード
GarbageCollectedを継承するとallocatorが切り替わります
MemberでBlinkオブジェクトを参照します�TraceWrapperV8ReferenceでV8オブジェクトを参照します
それらはTrace()メソッドの中に手動で追加する必要がある
47
class MessageEvent : public GarbageCollected<MessageEvent> {
Member<Blob> data_as_blob_;� TraceWrapperV8Reference<v8::Value> data_as_v8_value_;
void Trace(Visitor* visitor) const {
visitor->Trace(data_as_blob_);
visitor->Trace(data_as_v8_value_);
}
};
blink_gc_plugin
Trace()メソッドに追加するのを忘れてしまうとdangling pointerになって危険
他にもベースクラスのtraceを忘れたり、�std::unique_ptrでBlink GCのオブジェクトを参照してしまったり
こういったBlink開発者のミスはオリジナルclang pluginでチェックしてcompile errorになるようにして、開発者の負担を減らしている
48
Wrapper Tracingプロジェクト
Chromeバージョン57でリリース
Blinkのwrappableと一部オブジェクトだけCCTするプロジェクト
writeバリアを挿入しincrementalマーキングを実装
wrappableはV8 GCのあとにBlink GCがあって初めて解放される
Wrapper Tracingの対象とするオブジェクトをコード中に記述することが必要
49
Blink GC incrementalマーキング
Chromeバージョン70でリリース
Wrapper Tracingで実装したconservative Dijkstra-style writeバリアを最適化したうえで全体に適用
Blink GCのpause timeを大幅に短縮（75パーセンタイルで-62%）
50
Unified Heapプロジェクト
Chromeバージョン74でリリース
Blink GCのobject graph全体がCCTの対象に
JSとBlink、どちらのオブジェクトでも一回のV8 GCで解放可能に
メインスレッドでのGC実行時間が10-15%削減
Chromeバージョン77でGCスケジュリングもV8に完全に一本化
51
Blink GC concurrentマーキング
Chromeバージョン82でリリース
markingの負担がメインスレッドから別スレッドに
markingが速くなり、write barrierが有効になっている時間も短縮
Blink GCの1 GC cycleあたりの合計pause timeが-45%
52
🚧 次のステップ：cppgcライブラリ
V8の中にBlink GCをライブラリとして再実装
目的はC++ GCやCCTを全てのV8 embedderや一般のC++開発に使っていただくため
Blink GCはcppgcに今月切り替わりました
53
まとめ
マネージド言語のVMを組み込むとcross-component循環参照が問題になることがある
この問題はCCTを実装することで解決できる
ただしCCTの実装コストは大きい
Chromeは長年かけて完全なCCTを実装しました
将来はcppgcライブラリで誰でもChromeのCCTが使えるかも
54
Appendix
55
Object groupingの具体例
HTMLDocumentに繋がったHTMLElement #fooと�切り離されているHTMLElement #barがあるとき
V8内の情報だけでGCすると#foo wrapper、#bar wrapper両方解放されてしまう
BlinkからどのDOMツリーに所属しているか教えてあげると
documentが到達可能なら同じグループの#foo wrapperも到達可能とみなす
56
Object groupingの具体例
HTMLDocumentに繋がったHTMLElement #fooと�切り離されているHTMLElement #barがあるとき
V8内の情報だけでGCすると#foo wrapper、#bar wrapper両方解放されてしまう
BlinkからどのDOMツリーに所属しているか教えてあげると
documentが到達可能なら同じグループの#foo wrapperも到達可能とみなす
57
Object groupingの具体例
HTMLDocumentに繋がったHTMLElement #fooと�切り離されているHTMLElement #barがあるとき
V8内の情報だけでGCすると#foo wrapper、#bar wrapper両方解放されてしまう
BlinkからどのDOMツリーに所属しているか教えてあげると
documentが到達可能なら同じグループの#foo wrapperも到達可能とみなす
58
Object groupingの具体例
HTMLDocumentに繋がったHTMLElement #fooと�切り離されているHTMLElement #barがあるとき
V8内の情報だけでGCすると#foo wrapper、#bar wrapper両方解放されてしまう
BlinkからどのDOMツリーに所属しているか教えてあげると
documentが到達可能なら同じグループにある#foo wrapperも到達可能とみなす
59
CCTのアルゴリズム
詳細は論文をご参照ください
60
MainTracer {
MarkingWorkList work_list;
mark_roots():
// Root marking logic.
mark(object):
// Marks the object and returns true on
// success and false otherwise.
mark_and_put (object):
if mark(object) : work_list.put(object)
mark_live_objects():
mark_roots()
RemoteTracer.mark_cct_roots()
while !work_list.empty():
advance_marking(inf)
RemoteTracer.advance_marking(inf)
advance_marking(deadline):
while !work_list.empty() && !deadline_reached(deadline):
obj = work_list.get()
for child in obj:
if is_remote(child):
RemoteTracer.mark_and_put(child)
else:
mark_and_put(child)
}
RemoteTracer {
MarkingWorkList work_list;
mark_cct_roots():
// Mark roots for CCT.
mark(object):
// Marks the object and returns true on
// success and false otherwise.
mark_and_put(object):
if mark(object): work_list.put(object)
advance_marking(deadline):
while !work_list.empty() && !deadline_reached(deadline):
obj = work_list.get()
for child in obj:
if is_remote(child):
MainTracer.mark_and_put(child)
else:
mark_and_put(child)
}
CCT導入以前の循環参照メモリリークの例
昔はたったこれだけでウェブページの全オブジェクトがリークしました
e = new CustomEvent({detail: new Error()});
なぜでしょう？
61
wrapperメモリリーク
e = new CustomEvent({detail: new Error()});
62
Backup slides
63
64