曖昧なポインタの存在下での Copying Garbage Collection 2001/11/13 米澤研究室修士１年 小林　義徳

発表の内容 私の研究について。なにを目指しているか。 古典的な Copying Garbage Collection Cheney’s Breadth-First Copying Algorithm Bartlett’s Mostly-Copying Collection

Allocation が高速で、 言語処理系の一部として容易に利用可能なGC 私の研究について。何をめざしているか。 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 逆に、到達可能でないオブジェクトは、将来利用されることはない。

Garbage Collection 用語 Tracing Collector cf. Reference Counting Root set からポインタをたどっていき、到達不可能な　　　オブジェクトをゴミとして回収。 Root set から到達可能なオブジェクトの中にも　　　　　　　将来アプリケーションによって使われないものがあるが、　そのようなオブジェクトも生き残らせておく。 cf. Reference Counting

古典的 Copying Garbage Collector アプリケーションから オブジェクトの allocate 要求があった際、ヒープ内の空き領域が足りないとき、起動される。 アプリケーションは、GC が終わるまで一時停止、終わったら再開 Tracing Collector 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; if(free < limit){ return prev; }else{ ・・・ } } free Allocation 要求 limit

Copy GC の概略(1) Object は From_space より 端から順に allocate From_space To_space

Copy GC の概略(2) Object は From_space より 端から順に allocate From_space To_space Allocation 要求に応えられるだけの空き領域がなくなったら、GC を実行

Copy GC の概略(3) From_space To_space 生きているオブジェクトを To_space にコピー

Copy GC の概略(4) From_space To_space From_space と To_space を入れ替えておしまい。 これでめでたく、 allocation 要求に応えられるようになる

古典的 Copying Garbage Collector 詳細 Cheney’s Breadth-First Copying Algorithm

Copy GC の詳細 前提条件 GC の前後で、ヒープ内のオブジェクトの グラフ構造が保たれていなければならない Root set および ヒープ内の全てのデータについて、どの word がポインタで、どの word がポインタでないかは全て知っているものとする。 GC の前後で、ヒープ内のオブジェクトの 　　　　グラフ構造が保たれていなければならない Node – 各オブジェクト Edge – オブジェクト内のポインタ

Copy GC におけるコピー操作 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 アルゴリズム 初期化 – キューを空にする 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 To_space From_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 のメインループ) scan = free = (To_space の先頭); // 1. foreach r in rootset { r = copy(r); } // object* r; // 2. 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 データ構造 ヒープ : 同じ大きさに区切られたページより構成 Next_space – 曖昧なポインタに指されているページ – GC 中に新しく確保されたページ – To_space に相当 Current_space – それ以外。From_space に相当 キュー page 単位で管理 Next_space が連続した領域でないため、必要。 Forwarding Pointer – Copy GC と同じ

Bartlett’s Mostly-Copying Collector Root set キューの先頭のページから順に、舐める。 キュー

Bartlett’s Mostly-Copying Collector アルゴリズム 初期設定 – キューを空にする 本来のルートから「指されている」オブジェクトを含むページをnext_space に指定、キューに追加 キュー内の各ページについて ページ内の各オブジェクトについて、指されているオブジェクトをキューの最後のページにコピー。 以上を、キューが空になるまで続ける。

古典的 Copy GC におけるコピー操作 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 アルゴリズム 初期設定 – キューを空にする 本来のルートから「指されている」オブジェクトを含むページをnext_space に指定、キューに追加 キュー内の各ページについて ページ内の各オブジェクトについて、指されているオブジェクトをキューの最後のページにコピー。 以上を、キューの最後まで続ける。

Bartlett’s Mostly Copying Collector void gc(){ next_space = current_space + 1; queue = empty; // 1. foreach r in rootset{ promote_page(page pointed by r); } // 2. while(queue is not empty){ block = queue.dequeue(); foreach obj in block{ 3. 4. foreach q in obj.children{ q = copy (q); } } current_space = next_space:

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 キュー 本来のルートから「指されている」オブジェクトを含む ページをnext_space に指定、キューに追加

Bartlett’s Mostly-Copying Collector キュー 指されているオブジェクトを キュー内の各ページについて ページ内の各オブジェクトについて、指されているオブジェクトをページキューの最後のページにコピー。

Bartlett’s Mostly-Copying Collector キュー 指されているオブジェクトを コピー キュー内の各ページについて ページ内の各オブジェクトについて、指されているオブジェクトをページキューの最後のページにコピー。

Bartlett’s Mostly-Copying Collector キュー 以上を、キューの最後まで続ける。

結局、何がうれしいか。 スタックやレジスタなどの、曖昧なポインタの存在の元で、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 (青い本)