Garbage collection

デザインの概要

SpiderMonkeyは、オプションでインクリメンタルマーキングモード（incremental marking mode）を有効にされたマーク & スイープ方式のガベージコレクション（GC）を持っています。マークフェイズでは、インクリメンタルマーキングに必要なマークスタックを用います。ファイナライザを伴わないオブジェクトのスイープは、バックグラウンドスレッドにて実行されます。

世代別GCおよびコンパクションGC（compacting GC）の実装に向けた作業が進行中です。

主要なデータ構造

Cell

Cell は、外部からも使用される、GCによって割当と回収が行われるメモリーの単位です。つまり、GC以外から見れば、GCの仕事はCellの割当と自動的な回収ということになります。

例えばJSObjectのように、CellはGCによって割り当てられる全てのクラスの基底クラスとなります。

Allocation Kind

Cellは、Allocation Kindにより分類されます。Allocation Kindはオブジェクトのサイズおよびファイナライズの振る舞いを定義します。Allocation KindはAllocKind列挙型によって定義されます。

Arenas always hold objects of the same allocation kind. Thus, an arena holds objects all of the same size and finalization behavior.

Compartment

JSヒープはCompartmentに分割されます。Compartmentの要点は以下になります：

• あらゆるCell（JSヒープオブジェクト）は、Compartmentのどれか一つに属します（ヒープはCompartmentに分類されることを意味します）。
• オブジェクトは、別のCompartment内のオブジェクトに対する直接のポインタを保持することはできません。代わりに、他のオブジェクト用のラッパーを保持することになります。ラッパーは、Compartment間のセキュリティチェックに用いられます。同じCompartment内のオブジェクトは同じアクセス権限を持っているため、セキュリティチェックの必要はありませんが、cross-compartment wrapper（Compartment間ラッパー）のトラバース時にチェックが行われるかもしれません。
• エンジンは同時にひとつのCompartmentのGCが可能です。同様に、エンジンは他をGCしている場合を除いて、Compartmentの集合に対してGCが可能です。cross-compartment wrapperは、ひとつないし複数のCompartmentのGCのrootとして用いられます。

Compartmentは、SpiderMonkeyにおける、GCを含む特にメモリに関連した事項の構造的かつ分野横断的なコンセプトになっています。詳細はCompartmentsを参照してください。

JSCompartmentはGCに関連した重要なフィールドを保持しています：

ArenaLists型 arenas

この構造体は、それぞれのAllocation KindのArenaの2つのリストを記録しています。未使用のArenaのリストと、割当済みのArenaのリストです。

bool型 needsBarrier

このCompartmentにおけるGCが、インクリメンタルバリアの実行を必要とする場合にtrueとなります。すなわり、このCompartmentが現在インクリメンタルGCを実行しているかどうかを表します。

CompartmentGCState型 gcState

このCompartmentが現在GCを実行しているかどうかを表します。もし実行していなければ、GCの実行がスケジュールされているかを表します。

size_t型 gcBytes, gcTriggerBytes, gcMallocBytes, gcMaxMallocBytes

GCのスケジュールに使用される情報を表します

WrapperMap型 crossCompartmentWrappers

このCompartment内のオブジェクトのラッパーの集合です。Mapのキーはオブジェクト、値はラッパーです。同じオブジェクトに対するラッパーが複数回要求される場合、エンジンが同一のラッパーを毎回返せるようにするためにマッピングが必要とされます。ラッパーオブジェクトの集合は同様に、単一および複数のcompartmentの（non-globalな）GCにおいても必要となります

Zone

TODO（原文ママ）

Chunk

Chunkはメモリの割当における最大の内部単位となります。

Chunkは1MBのサイズを持ち、内部にArena、パディング、Mark Bitmap（ChunkBitmap）、解放されたArenaのビットマップ、およびChunkヘッダ（ChunkInfo）を保持しています。

ChunkInfoは、ChunkInfo::freeArenasHeadから開始しており、ArenaHeader::nextを介してリンクしている未割当のArenaのリストを保持します。また、ChunkInfoは未割当のArenaの数の基本的な情報を保持しています。

TODO ChunkInfo next/prev（原文ママ）

Arena

Arenaはメモリ割当の内部単位です。

Arenaは1ページ（ほぼ全てのプラットフォームで4096バイト）の大きさであり、ArenaHeaderと、僅かなパディングとなるバイト領域と、整列された要素の配列を含みます。Arena内のすべての要素は、同じAllocation Kindとサイズを持ちます。

すべてのArenaは、ArenaHeader::firstFreeSpanOffetsから始まる自由なメモリ区間のリストを保持します。自由なメモリ区間の最後のCell（最後であるのが望ましい）は、次の自由なメモリ区間を表すFreeSpanを保持します。

Free Span

構造体FreeSpanは、Arena内の自由なCell [first, last]の連続を表します。FreeSpanは、自由なメモリ区間から割当を行うための関数を保持しています。

Mark Bitmap

マークビットマップはChunkBitmapによって表されます。

マークビットマップはGC Cellごとのビットを持ちます。故に、複数のCellによって構成されているオブジェクトは、ビットマップ中の複数のビットを使います。

Exact Stack Rooting API

GC rootの実装とおよびSpiderMonkey内での使用についての情報となります。 Exact Stack Rooting.

マーキング

TODO（原文ママ）

インクリメンタルマーキング

インクリメンタルマーキングは、マーキングの最中に（JavaScriptプログラムによる）状態の変更が発生しても、他のマーキング作業の実行が可能であることを意味します。つまり、マーキングによる長時間のプログラムの実行の停止の代わりに、小さな停止の集まりがGCの実行となるのです。停止時間は10msもしくはそれ以下に抑えられます。

長時間の停止が必要となる可能性も常に存在します。インクリメンタルGCの間のメモリ割当の頻度が高い場合、エンジンはインクリメンタルGCの完了の前にout of memoryを実行するかもしれません。そのような場合、エンジンは幾つかのメモリーの返還とプログラムの実行の継続のために、非インクリメンタルな完全なGCを直ちに再実行しなくてはなりません。

Incremental write barrier（インクリメンタル書き込みバリア）

write barrierを必要とする問題

インクリメンタルGCは正確性の担保のためにwrite barrierを必要とします。

TODO（原文ママ）、基本的な問題を表す図を用意する

基本的な問題は以下の通りです（色の説明については、辞書を参照）。オブジェクトAはblackかつポインタ領域を所持しています。オブジェクトBはwhiteとします。ここで、インクリメンタルなスライスが止まり、プログラムの実行による状態の変更が再開しました。プログラムがBをAに保存したことにより、AはBへのポインタを持つことになります。そして、Bへのすべての既存のポインタが削除されました。そのとき、

• Bは生存している。なぜならAはblackであり、Bへのポインタを含んでいるから。
• Bはマーク作業が実行されない。なぜならBはAを介してのみ到達可能であり、Aがblackである故にAはすでにマーク作業が完了しているから。
• 以上により、Bは生存しているが、GCの回収対象となってしまう。

write barrierは、ポインタの保存の発生前に実行され、生存しているオブジェクトが回収されないようにするために情報を記録する機構の一つです。

SpiderMonkeyのincremental write barrier

SpiderMonkeyは、（相対的に）シンプルな、ssnapshot-at-the-beginning allocate-black barrierと呼ばれる一般的なincremental write barrierを用いています。

このバリアの動作を理解するために、事象を単純にするために、新規にオブジェクトが割り当てられることの無いインクリメンタルGCを仮定します。生存しているオブジェクトを回収しないようにするためにはどうすればよいでしょうか？　一つの方法としては、インクリメンタルGCの最初の時点で生存していたすべてのオブジェクトをマークするという手法があります（これは、オブジェクトへの全ての参照が現在のインクリメンタルGC中に消えた場合は、次のインクリメンタルGC時にそのオブジェクトが回収されるということです）。この手法は、インクリメンタルGCの開始時に生存しているオブジェクトのスナップショットを保存し、それら全てをマークするのとコンセプト上は同義であるために、snapshot-at-the-beginningと呼ばれています。実際にはスナップショットを撮る訳ではありません。そのような場合は完全な非インクリメンタルなマーク作業が必要となります。

snapshot-at-the-beginningバリアの実装は単純です。GCポインタを保持する場所がプログラムによって上書きされたタイミングで、バリアは開始します。バリアは単純にポインタによって指し示されているオブジェクトをblackにします。鍵となるのは、オブジェクトへの全てのポインタが上書きされた場合にのみ、オブジェクトはマークされず”死んだもの”となりうるという点です。そのため、オブジェクトへのポインタが上書きされたタイミングでオブジェクトをblackにすれば、オブジェクトが”死ぬ”ということは発生し得ないのです。

FIXME（原文ママ）:指し示されたオブジェクトをblackにするだけは十分ではないと思います。マークされていない別のオブジェクトがあったら何がおこりますか？　マークスタックについても言及すべきです。「指し示されているオブジェクトをblackにする」というのは、「再帰的に指し示されたオブジェクトをblackにする」という意味で書かれていますか？

これで、メモリの割当の正確性についても話します。新規に割り当てられたオブジェクトはGCの開始時には存在していませんでした。snapshot-at-the-beginningバリアはこれについては巧くカバーしません。ですが、もし新規に割り当てられたオブジェクトが生存している場合は、それが回収されないようにする必要があります。これは簡単で、インクリメンタルGC中に新規にオブジェクトが割り当てられたら、それをマークすれば良いのです。これを名付けてallocate-blackと言います。

SpiderMonkeyの incremental read barrier（インクリメンタル読み取りバリア）

インクリメンタルGCの教科書的な実装では、write barrierしかありません。SpiderMonkeyでは、weak pointer（用語集参照）のためにread barrierも用意しています。

TODO（原文ママ）：解説の完成

実装の詳細

write barrierは実行時のコストを伴うので、SpiderMonkeyはインクリメンタルGCの実行中以外ではスキップするようにしています。各compartmentのneedsBarrier()フラグによって、バリアが必要かどうかを示しています。

T*型のフィールドのように、全てのT型はwrite barrierを必要としており、T::writeBarrierPre(old)という関数が存在しています。たとえば、JSObject*がwrite barrierを必要とする場合、関数ObjectImpl::writeBarrierPre(ObjectImpl *old)が存在します（JSObjectはObjectImplを継承しています。）。 zone->needsBarrier()がtrueである場合、writeBarrierPre()はoldをマークする、ということです。

HeapPtr<t>クラスはwrite barrierの起動を簡単にするために提供されています。HeapPtr<t>はT*をカプセル化し、割当時にwrite barrierを起動します。これにより、GCポインタ型のオブジェクトの領域は、通常、HeapPtr<T><t>として定義されています。HeapValueクラスはValueに対して同じことを行います。HeapSlot（および関連するHeapSlotArray）も同様に、オブジェクトスロットに対するものです。HeapIdは、同じくjsidに対する物です。TODO（原文ママ）：なぜHeapValueとHeapSlotの2つが存在するのか</t></t></t>

オブジェクトのプライベート領域は、特別に取り扱う必要があります。プライベート領域自体は、エンジンに対しては隠されていますが、マークされる必要があるものを指し示すかもしれません（例：JSObjectのポインタの配列）。この例では、プライベート領域が上書きされた場合、JSObjectのポインタは”死ぬ”ことになります。そのため、write barrierはそれらをマークしなければなりません。ObjectImpl::privateWriteBarrierPreはプライベート領域が上書きされる前にJSObjectクラスのトレースフックによって起動され、これに対処します。

他の詳細事項として、write barrierは新規に確保されたオブジェクトのフィールドの初期化時には、上書きされるポインタが存在しないことから、スキップすることができます。

Sweeping（スイーピング）

TODO（原文ママ）

世代別GC

TODO（原文ママ）

GC統計API

実行時にGC統計API.を通じて、GCが保持する明確な統計情報にアクセスする事ができます。

ソースファイル

jsgc{.h,inlines.h,.cpp} GCを起動するためのエントリーポイントを含む内部API関数群を定義します。

jsgcstats.{h,cpp} 保守的なスタックスキャンに基づく情報収集のための構造体ConservativeGCStatsを定義します。TODO（原文ママ）：削除されたときに消す

gc/Barrier[-inl].h インクリメンタルおよび世代別用のwrite barrierを実装しています。

gc/Heap.h GCのヒープ構造の根幹を成す、Chunk, ChunkInfo, ChunkBitmap, Arena, ArenaHeader, Cell, FreeSpanといった一連の構造体を定義します。

gc/Marking.{h,cpp} 多様なGC対象用のマーク作業関数の全てを定義します。

gc/Memory.{h,cpp} ページの配置と解放（mapping and unmapping）のための僅かな関数に加えて、プラットフォーム固有の実装を保持しています。配置・解放（map/unmap）用の関数はチャンクの確保と解放（allocate and release ）用のために、 jsgc.cppによって使用されています。使用されておらずディスクに格納する代わりメモリ破棄が可能なページをOS伝えるなどに用いる、確保または解放（commit or decommit）のための関数もあります。

gc/Root.h GCルートとして用いられる変数クラスを定義します。

gc/Statistics.{h,cpp} SpiderMonkey GCのパフォーマンスカウンタとして保存される Statics構造体を定義しています。

用語の解説

TODO（原文ママ）: SpiderMonkeyの実装と色の名前が一致しているかを確認

black（黒）一般的な計算機科学の文脈において、マークフェイズ中、マーク済かつ子供がgray（マークキューに積まれている）なオブジェクトをblackとします。SpiderMonkeyでは、マークビットが設定されたオブジェクトをblackと見なします。

gray（灰色）：一般的な計算機科学の文脈において、マークフェイズ中、マークキューに積まれているオブジェクトをgrayとします。SpiderMonkeyでは、マークスタック内のオブジェクトの子孫かつblackで無いものはgrayとなります。つまり、状態が明白でないオブジェクトがgrayであるということです。

Handle（ハンドル） 私たちのGCでは、Handleはルートによって登録されたどこかを指し示すポインタです。

root TODO（原文ママ）: 上からコピーする

weak pointer（弱参照ポインタ） 一般的な計算機科学の文脈において、weak pointerはGC目的で指し示された値が生存し続ける必要がなくなるポインタです。具体的には、既にポインタの指し示す対象が既にGCされている場合は、weak pointerのget()メソッドが返す値はnullポインタとなります。Gecko/SpiderMonkeyでは、weak pointerはマークされていないがGC対象となりうるオブジェクトへのポインタとなります。そのため、get()メソッドは存在せず、指し示す値がGCされたかどうかの保証も存在しません。プログラマは、指し示されたオブジェクトの生存時間が、weak pointerの生存時間よりも長いことを保証する必要があります。TODO（原文ママ） これが正しいか確認。

white（白） 一般的な計算機科学の文脈において、マークフェイズ中、まだ辿れていないオブジェクトはwhiteとなります。マークされなかった場合、マークフェイズの後にオブジェクトはwhiteとなります。SpiderMonkeyでは、grayでもblackでもない（blackでもマークスタック内のオブジェクトの子でもない）オブジェクトがwhiteとなります。

クリーンアップの可能性

MarkPagesInUse はすべてのプラットフォームで何の操作も実施しません。

統計ファイルのマージ。

ArenaLists::refillFreeListsは悪いネーミングです。それは、たとえArenaの解放リストが完全ではなくても、Cellの確保を試みるように見えます。