9.Garbage Collection for C
早稲田大学理工学部情報学科上田研究室
山根信之
自動メモリ管理
• 宣言型、文字列処理言語の早期から関連
付けられてきた
• オブジェクト指向型言語でも多くは自動メモ
リ管理を提供している
CでのGC
• プログラマがGCを使う時だけ使うようにし
たい
• 効率的な自動管理システムがあってもあ
まり使われないし、メモリ操作に費やす時
間は小さい
• GCが利益を得るまでは、コンパイラやラン
タイムシステムから独立して動作できなけ
ればならない
GCの持たない情報
• どこでrootが見つかるのか
• スタックフレームレイアウトやレジスタの協定
• どのwordがポインタで、どれがそうでないの
か
9.1 曖昧なroot集めの分類法(1)
• Garbage collectorはコンパイラの密接な知
識や協調でオブジェクトのレイアウトを明
確に決定する
• 保守的collectorはコンパイラからヒープを
受け取らない。どのwordも潜在的なポイン
タの可能性があるのでポインタかどうか調
べる
9.1 曖昧なroot集めの分類法(2)
• この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)
• ヒープを探索する方法は2つある。
– 同じIDのブロックに入っているオブジェクトの
型を同じにする
• これはオブジェクトがコンパクトになるが、allocation
が複雑になる
– オブジェクトごとにオブジェクト型を示すヘッダ
をつける
Generational GC(1)
• Bartlettのcollectorでも世代GCができる。
• メモリの50%が使われるとminor collection
が起きる。
• 世代は2世代で、新しい世代は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を使う計画を設計した。
• この方法だと、2倍高価になる。
The efficiency of Mostly Copying
• CopyingはspaceIDやオブジェクトの型情報、
promotion bit、ブロックへのリンクなどの空
間的オーバーヘッドがある。
• Generationalはremembered setの維持コス
トがかかるが、GCに使う時間が減少する。
ダウンロード

Power Point(発表用スライド)