9.Garbage Collection for C 早稲田大学理工学部情報学科上田研究室 山根信之

自動メモリ管理 宣言型、文字列処理言語の早期から関連付けられてきた オブジェクト指向型言語でも多くは自動メモリ管理を提供している

CでのGC プログラマがGCを使う時だけ使うようにしたい 効率的な自動管理システムがあってもあまり使われないし、メモリ操作に費やす時間は小さい　　　　　　　　　　　　　　　　　　　 GCが利益を得るまでは、コンパイラやランタイムシステムから独立して動作できなければならない

GCの持たない情報 どこでrootが見つかるのか スタックフレームレイアウトやレジスタの協定 どのwordがポインタで、どれがそうでないのか

9.1 曖昧なroot集めの分類法(1) Garbage collectorはコンパイラの密接な知識や協調でオブジェクトのレイアウトを明確に決定する 保守的collectorはコンパイラからヒープを受け取らない。どのwordも潜在的なポインタの可能性があるのでポインタかどうか調べる

9.1 曖昧なroot集めの分類法(2) この２つの中間に、部分的に正確だったり曖昧だったりするcollectorがある これはコンパイラの助けを全く受けないので、スタックレイアウトやレジスタに関する知識を持たない。プログラマ自身がデータ配置を決める

Conservative collector ごみの量を保守的に見積もる 使われない参照もいくらか余分に保持する コンパイラの助けのない、非強調的な環境の中で動くcollectorのことを表すことにする この章ではBoehm,Demers,Weiserの開発したcollectorとBartlettが開発したcollectorを見ていく

Boehm-Demers-Weiser collector mark and deferred sweepに基づいた　　　non-moving collector CやC++と共に使うのに適している　　　　　 現在はincrementalやgenerationalもサポートしている 幅広いOSで実行

Bartlett’s collector The Mostly Copying Garbage collector CやC++と共に使うこともできる いくつかの他のcollectorの基本

9.2 保守的GC 明確なメモリ管理に比べてわずかなペナルティを普段から課す collectorはmark-and-sweepに基づく bitmapや異なるサイズのオブジェクトを隔離したフリーリストを使う マーカーは回収スタックを使い、オーバーフローしそうならより大きいスタックを用意

Allocation Collectorはtwo-level allocatorを使う →Section4.5 ヒープは4kbyteのブロックからなる ブロックはmalloc等のOSのスタンダードアロケータで取得 ブロックはsingle sizeのオブジェクトを含む 隣の空のブロックと結合もできる

Allocation ブロックの半分よりも大きいオブジェクトは自分の一塊のブロックにallocateされる 十分なサイズのフリーな塊が利用できなければGCに頼るかヒープを拡張する アロケータはfirst-fit戦略を使う

Allocation 小さいオブジェクトは、free-listの最初のメンバをそのオブジェクトサイズ分だけどけてallocateする free listが空になれば、sweep phaseで回収して満たそうとする 回収も成功しなければ、lower-levelのallocatorから新たなブロックを得てヒープを拡張

Root and pointer finding 保守的collectorは、遭遇した全てのwordを(特にわかっていない限り)潜在的ポインタとして扱わなければならない 正確に安価にこれを決定できるとよい 非常に保守的なcollectorは大量のごみを保持してしまう

Objectをマークするためのテスト 潜在的ポインタpはヒープを参照しているか？ このオブジェクトを含んでいそうなヒープブロックは配置されたか？ ブロックの初めから疑わしいオブジェクトのオフセットは、オブジェクトサイズのブロック倍か？

Interior pointer 小さいオブジェクトは内部ポインタの最初のsignificant bitを覆うことでブロックヘッダのアドレスを得る 大きいオブジェクトはその開始点を見つけるかポインタが無効になるまでブロックにスキップしてbottom_indexを調べる。

保守的GCの問題点 データをヒープポインタとして誤認識するリスクを持つか、一部のごみを不要に保持する collectorが内部ポインタを有効とみなすようにすると、ポインタでないwordがポインタとして認識されることが増える

Misidentification ポインタに間違えられたwordは大体整数 小さい整数は多くのシステム上では有効なヒープアドレスではない 非初期化データもポインタに間違えられやすい atomic objectは定義上他のヒープのオブジェクトへの参照を持てない

Misidentification 大きなprocedure frameを奨励するアーキテクチャで、フレームの大きな部分が正しく初期化されていないと間違った参照を生成する black listingはヒープにあるメモリの一部を解放して利用できなくする

Efficiency 設計はallocationとフラグメンテーションへの耐久度の間で妥協が必要 古いオブジェクトを解放するのはコストがかかるので単純にmallocやfreeの実行命令数を数えるのは効率的でない

Incremental/generational GC Boehm-Demers-Weiser collectorもこの方法をサポートしている

9.3 Mostly Copying collection 保守的なCopying collectorである。 スタックやレジスタやstatic areaから参照されているかもしれないオブジェクトはcopyされない。 そのためallocationが速く、ヒープオブジェクトにあるポインタを発見するのが単純で、GCが正確。

Heap layout Fromspace,Tospaceではなく、spaceIDのついたブロックから成る。 ブロック内のオブジェクトをコピーする方法には次の二つがある。 Tospaceとなっているブロックへコピーする そのブロックをTospaceにセットする spaceIDがcurrent_spaceと同じブロックはFromspaceである。

Allocation ブロックに十分な空きがあればそこへ配置。 ブロックに十分な空きがなければ、フリーブロックを探す。フリーブロックはIDがcurrent_spaceでもnext_spaceでもない。 大きなオブジェクトは複数のブロックにまたがる。

Garbage Collection(1) まずrootからscanしていき、辿ったブロックのIDをnext_spaceの値に変更し、そのブロックをTospace scan-listに加える。 次にTospace scan-listにあるブロックの中を調べ、到達可能なオブジェクトは新たなメモリ空間(Tospace)へとコピーされる。

Garbage Collection(2) ヒープを探索する方法は２つある。 同じIDのブロックに入っているオブジェクトの型を同じにする これはオブジェクトがコンパクトになるが、allocationが複雑になる オブジェクトごとにオブジェクト型を示すヘッダをつける

Generational GC(1) Bartlettのcollectorでも世代GCができる。 メモリの50%が使われるとminor collectionが起きる。 世代は２世代で、新しい世代はIDが偶数番号、古い世代はIDが奇数番号とする。 ルートセットから直接参照されるオブジェクトのあるブロックはID書き換えでTospaceになり、それ以外のブロックのオブジェクトは普通にコピーされる。

Generational GC(2) Minor collectionを繰り返すと古い世代が大半を占めるようになる。これが85%を超えるとmajor collection(mark and compact)が起きる。 この完了後にヒープが75%以上埋まっていれば、megabyte incrementをする。 最初のフェイズでブロックの1/3以下しか使われていないブロックをscavengeして空にし、次のフェイズでポインタを修正する。

Ambiguous data structures Unionでintとポインタを宣言すると、intなのかポインタなのかを判断できない。 Bartlettはこれを後で回収できるようにするためにcontinuationsを使う計画を設計した。 この方法だと、２倍高価になる。

The efficiency of Mostly Copying CopyingはspaceIDやオブジェクトの型情報、promotion bit、ブロックへのリンクなどの空間的オーバーヘッドがある。 Generationalはremembered setの維持コストがかかるが、GCに使う時間が減少する。