オブジェクトのコピー

曖昧なポインタの存在下での
Copying Garbage Collection
2001/11/13
米澤研究室修士１年
小林義徳
発表の内容


私の研究について。なにを目指しているか。
古典的な Copying Garbage Collection
–

Cheney’s Breadth-First Copying Algorithm
Bartlett’s Mostly-Copying Collection
私の研究について。何をめざしているか。
Allocation が高速で、
言語処理系の一部として
容易に利用可能なGC
背景


言語処理系を作るにあたり、Garbage Collectorを
各処理系の作者が自前で実装しているのが現状
はっきりいって、似たようなものが世の中に存在する
のに、もう一度実装しなおすのは無駄な努力
ライブラリとして容易に利用可能な GC を
つくろう!
世の中に存在する、容易に利用可能な
GC

Boehm GC
–
–
–

全ての word がポインタか否か分からないような環境で、
Mark-Sweep GC を実現(Conservative GC)
ライブラリとして容易に利用可能。
C 言語のプログラムにすら使える(例 mozilla,w3m)
Allocation が遅いので、ML や Scheme のような、
Allocation を頻繁に行う言語処理系の GC として、
不向き。
実現したいこと(1)


言語処理系を作る際、容易にライブラリとして利用可能
メモリ上のデータの型が分からない環境でも利用可能。
–
–

各領域の word について、どれがポインタで、
どれがポインタでないか、部分的に情報がある処理系を仮定。
Conservative GC
Fast Allocation 可能
–
–
連続した大きな領域の確保が必要
Copy GC
実現したいこと(2)

Native なコードで生成したオブジェクトについて、
型をGC に教えるも教えないも自由な Interface
–

型がわかるオブジェクトについてのみ Copy を実行
メモリの断片化を解消
–
その際、コピー量をできるだけ減らす。
今日、Bartlett’s の Mostly-Copying
Collector を選んだ動機

もともと、言語処理系用に作られたものである
–

Bartlett’s Scheme-to-C Compiler
一部ポインタか否かが分からない状況で、
Copy GC を実現している。
古典的 Copying Garbage Collector
～概要およびアルゴリズムとデータ構造～
Root から到達可能な
オブジェクトのコピーで
GC を実現
古典的 Copying Garbage Collector



完全にどの word もポインタか否か
完全に分かる状況を想定
生きているオブジェクトをコピーすることで GCを実現
Fast Allocation
–

空き領域の先頭を指すポインタをずらすだけで allocation
完了
ヒープ内メモリの断片化が決して起こらない。
Garbage Collection 用語

Root set
–
–
–
アプリケーション内の任意の場所で常に利用可能な領域
(普通、レジスタ、スタック、静的変数を Root set とする)
Root set からオブジェクトのポインタをたどっていき、到達
可能なオブジェクトは、将来アプリケーションに利用される
可能性がある。
逆に、到達可能でないオブジェクトは、将来利用されること
はない。
Garbage Collection 用語

Tracing Collector
–
–
Root set からポインタをたどっていき、到達不可能な
オブジェクトをゴミとして回収。
Root set から到達可能なオブジェクトの中にも
将来アプリケーションによって使われないものがあるが、
そのようなオブジェクトも生き残らせておく。
cf. Reference Counting
古典的 Copying Garbage Collector

アプリケーションからオブジェクトの allocate 要求があった
際、ヒープ内の空き領域が足りないとき、起動される。
–

Tracing Collector
–

アプリケーションは、GC が終わるまで一時停止、終わったら再開
Root set からポインタをたどっていき、到達可能なオブジェクトを生
き残らせる。
Root set からポインタをたどりながら、たどられたオブジェ
クトをコピーしていく。
–
コピーされなかったオブジェクトがゴミ
Copy GC のヒープ構造


From_space と
To_space という、大きさ
が同じ二つのヒープ。
通常、オブジェクトを
From_space より
allocate
From_space
To_space
Copy GC での Fast Allocation

Copy GC はAllocation が速い！
From_space
void* allocate(size_t size){
prev = free;
free = free + size;
free
if(free < limit){
return prev;
}else{ ・・・ }
}
Allocation 要求
limit
Copy GC の概略(1)
1. Object は From_space より
端から順に allocate
From_space
To_space
Copy GC の概略(2)
1. Object は From_space より
端から順に allocate
2. Allocation 要求に応えら
れるだけの空き領域がな
くなったら、GC を実行
From_space
To_space
Copy GC の概略(3)
From_space
3. 生きているオブ
ジェクトを
To_space にコピー
To_space
Copy GC の概略(4)
From_space
4. From_space と
To_space を入れ替
えておしまい。
これでめでたく、
allocation 要求に応
えられるようになる
To_space
古典的 Copying Garbage Collector
詳細
Cheney’s Breadth-First
Copying Algorithm
Copy GC の詳細

前提条件
–

Root set およびヒープ内の全てのデータについて、ど
の word がポインタで、どの word がポインタでないか
は全て知っているものとする。
GC の前後で、ヒープ内のオブジェクトの
グラフ構造が保たれていなければならない
–
–
Node – 各オブジェクト
Edge – オブジェクト内のポインタ
Copy GC におけるコピー操作

1.
2.
GC の前後で、ヒープ内のオブジェクトの
グラフとしての構造が保たれていなければならない
あるオブジェクトを別の場所にコピー
コピーされたオブジェクトを指していたポインタ全て
を、GC の終了時までに、オブジェクトの新しい位置
を指すように更新
Cheney’s Breadth-first Copying
アルゴリズムとデータ構造


キューを用いた幅優先探索アルゴリズム
To_space をキューとして用いる。
–

To_space へのオブジェクトのコピーは、同時に、
オブジェクトをキューに追加することを意味する。
探索しながら、オブジェクトをコピーしていく。
Cheney’s Breadth-first Copying
データ構造


ヒープ : From_space と To_space
To_space 内を指すポインタ
–
–

scan – 次に探索されるオブジェクトを指すポインタ
キューの先頭を指すポインタ
free – To_space の空き領域の先頭を指すポインタ
キューの末尾を指すポインタ
Forwarding pointer
–
コピーされるオブジェクトの古い位置に置かれ、
新しい位置を指すポインタ。
Cheney’s Breadth-first Copying
アルゴリズム
1.
初期化 – キューを空にする

2.
3.
4.
5.
scan = free = (To_space の先頭)
ルートから指されているオブジェクトを To_space
にコピー(キューに追加)
キュー内のオブジェクトに指されているオブジェク
トをコピー(キューに追加)
以上を、キューが空になるまで続ける。
最後に、From_space と To_space を交換
Cheney’s Breadth-first Copying
アルゴリズム(オブジェクトのコピー)
object* copy(object* p)
{
if ( p is already copied) { return p->forwarding_addr; }
object* newaddr = free;
memcpy(newaddr,p,p->size);
free = free + p->size;
p->forwarding_addr = newaddr;
return newaddr;
}
Cheney’s Breadth-first Copying
アルゴリズム(オブジェクトのコピー)
From_space
ポインタの更新
From_space
To_space
To_space
scan
free
Forwarding pointer
オブジェクトのコピー
- コピー前 -
- コピー後 -
Cheney’s Breadth-first Copying
アルゴリズム(オブジェクトのコピー)
From_space
To_space
From_space
To_space
Forwarding pointer
すでにコピーされたオブジェクトを指している場合、
ポインタを forwarding pointer で置き換える
Cheney’s Breadth-first Copying
アルゴリズム(GC のメインループ)
gc(){
// 1.
foreach r in rootset { r = copy(r); } // object* r; // 2.
scan = free = (To_space の先頭);
while(scan < free){
foreach p in scan.children{ // object* p;
p = copy(p);
3.
4.
}
scan = scan + p->size;
}
swap(To_space,From_space);
}
// 5.
Bartlett’s Mostly Copying Collector
～ Compacting Garbage Collection with Ambiguous Roots～
Root set の型が分からない
状況下での Copying GC
Bartlett’s Mostly-Copying Collector


もともとScheme => C コンパイラ用に開発された。
想定している条件



Root set(レジスタ、スタック)は、曖昧なポインタとして扱う。
ヒープ内のオブジェクトの構造については、GC は
完全に知っている。
上のような条件のもとでCopy GC を実現
Conservative GC 用語

曖昧なポインタ
–
–
–

ある word について、それがポインタであるか否かがわ
からないような word
ポインタかもしれないので、「指されている」オブジェクト
は生きている可能性がある。
ポインタでないかもしれないので、書き換えるとプログラ
ムが正しく動かなくなる場合がある。
Bartlett’s Mostly-Copying GC 等では、
曖昧なポインタに「指されている」オブジェクトは、
とりあえず生かされる(Conservative GC)。
Mostly Copying Collector の概要(1)




同じサイズのページ達で構成されるヒープ
{曖昧なポインタすべて} = {Rootset のword}
GC の始めの Rootset の探索時に、
曖昧なポインタに「指されている」オブジェクトを含む
ページを next_space に指定。
next_space 内のオブジェクトは、GC 中コピーせず、
そのままその場に残す。
Mostly Copying Collector の概要(2)

曖昧なポインタに指されているオブジェクトを含む
ページ内のオブジェクト全体を Rootset だと思って、
古典的な Copy GC を実行するのと等価
–
–

ただ、上記のようなページを、explicit に Rootset として
扱っているわけではない。
アルゴリズムが非常に簡単
キューを用いた幅優先探索アルゴリズム
Bartlett’s Mostly Copying Collector
本来の Root set
新しいRootset
内には、曖昧
なポインタが
存在しない。
普通のCopy GC が可能。
Bartlett’s Mostly-Copying Collector
データ構造

ヒープ : 同じ大きさに区切られたページより構成
–
–

キュー
–
–

– 曖昧なポインタに指されているページ
– GC 中に新しく確保されたページ
– To_space に相当
Current_space – それ以外。From_space に相当
Next_space
page 単位で管理
Next_space が連続した領域でないため、必要。
Forwarding Pointer – Copy GC と同じ
Bartlett’s Mostly-Copying Collector
Root set
キュー
Bartlett’s Mostly-Copying Collector
アルゴリズム
1.
2.
3.
初期設定 – キューを空にする
本来のルートから「指されている」オブジェクトを
含むページをnext_space に指定、キューに追加
キュー内の各ページについて
1.
4.
ページ内の各オブジェクトについて、指されているオブ
ジェクトをキューの最後のページにコピー。
以上を、キューが空になるまで続ける。
古典的 Copy GC におけるコピー操作

1.
2.
GC の前後で、ヒープ内のオブジェクトの
グラフとしての構造が保たれていなければならない
あるオブジェクトを別の場所にコピー
コピーされたオブジェクトを指していたポインタ全て
を、GC の終了時までに、オブジェクトの新しい位置
を指すように更新
Bartlett’s Mostly-Copying Collector
のコピー操作(1)

オブジェクトのコピー
–
–
–
オブジェクトが既に next_space にある場合は、コピーし
ない。
オブジェクトがまだコピーされていない場合は、
オブジェクトをキューの最後のページの最後にコピーし、
もとの位置に forwarding_pointer を残す
もし、キューの最後のページの空き領域が足りない場合、
新しいページをキューの最後に追加し、そこにコピー。
Bartlett’s Mostly-Copying Collector
のコピー操作(2)
object* copy(object* p){
if(p belongs to next_space || p == NULL){ return p; }
if(p is already copied){ return p->forwarding_addr; }
object* newobj = move(p);
p->forwarding_addr = newobj;
return newobj;
}
Bartlett’s Mostly-Copying Collector
アルゴリズム
1.
2.
3.
初期設定 – キューを空にする
本来のルートから「指されている」オブジェクトを
含むページをnext_space に指定、キューに追加
キュー内の各ページについて
1.
4.
ページ内の各オブジェクトについて、指されているオブ
ジェクトをキューの最後のページにコピー。
以上を、キューの最後まで続ける。
Bartlett’s Mostly Copying Collector
void gc(){
next_space = current_space + 1;
queue = empty;
// 1.
// 2.
foreach r in rootset{ promote_page(page pointed by r); }
while(queue is not empty){
block = queue.dequeue();
foreach obj in block{
3.
foreach q in obj.children{ q = copy (q); }
}
}
current_space = next_space:
}
4.
Bartlett’s Mostly Copying Collector
void promote_page(page* p){
if(p->spaceID == current_space){
p->spaceID = next_space;
2.
queue.enqueue(p);
}
}
Bartlett’s Mostly-Copying Collector
アルゴリズム
Root set
キュー
2. 本来のルートから「指されている」オブジェクトを含む
ページをnext_space に指定、キューに追加
Bartlett’s Mostly-Copying Collector
キュー
指されているオブジェクトを
3.
キュー内の各ページについて
1.
ページ内の各オブジェクトについて、指されているオ
ブジェクトをページキューの最後のページにコピー。
Bartlett’s Mostly-Copying Collector
キュー
指されているオブジェクトを
コピー
3.
キュー内の各ページについて
1.
ページ内の各オブジェクトについて、指されているオ
ブジェクトをページキューの最後のページにコピー。
Bartlett’s Mostly-Copying Collector
キュー
4.
以上を、キューの最後まで
続ける。
結局、何がうれしいか。

スタックやレジスタなどの、曖昧なポインタの存在の
元で、Copy GC が実現できた。
–
–

曖昧なポインタに指されていないページについて、
断片化を解消できる。
アルゴリズムが非常に単純 - 実装がラク
Root set の中にオブジェクトの中間を指すポインタ
が存在しても OK
Bartlett’s Mostly-Copying Collector
の欠点

曖昧なポインタに指されているページにあるオブ
ジェクトが生き残ってしまう。
–

さらに、その子孫まで生き残ってしまう。
曖昧なポインタに指されているページについて、
断片化が起こってないように見えるが、
実は死んでいるオブジェクトが間を埋めているだけ。
関連研究



[Appel 1988] Copying Garbage Collection in the
Presence of Ambiguous References
(http://research.microsoft.com/~drh/pubs/tr-162-88.pdf)
[Yip 1991] Incremental,Generational Mostly-Copying
Garbage Collection in Uncooperative Environments
(http://www.research.compaq.com/wrl/techreports/abstracts/91.8.html)
[田中 1998] 卒業論文,Copying Garbage Collection in the
Presence of Uncertain Pointers
(/home/yl2/y-tanaka/ise-env/work/98winter/senior-thesis/thesis)
References
[Bartlett 1988] Joel.F.Bartlett,
Compacting Garbage Collection with Ambiguous
Roots
(http://www.research.compaq.com/wrl/techreports/abstracts/88.2.html)
 Garbage Collection,Algorithm for Automatic
Dynamic Memory Management,
Richard Jones,Rafael Lins
(青い本)


Download Report