図1: マシンスタック
突然だが、本章を始めるに先立ち、プログラム実行時のメモリ空間の状態につ いて予習をしておこうと思う。この章ではコンピュータの低レベルな部分にか なり踏み込んでいくことになるので、あらかじめある程度の知識を仕入れてお かないと太刀打ちできないのだ。それにこの後の章になればいずれ必要になっ てくる。ここで一回やってしまえば後が楽だ。
一般的なCプログラムではメモリ空間の中に以下の部分を持つ。
テキスト領域はコードが置いてあるところ。二番目は見ての通り。マシンスタッ
クには関数の引数やローカル変数が積まれる。ヒープはmalloc()で割り当てて
もらうところだ。
三つめのマシンスタックについてもう少し話そう。マシン「スタック」と言う
くらいだから当然スタック構造をしている。つまりどんどん新しいものを上に
積み重ねていく。実際にマシンスタックに値を積むときはint一個などの細か
い単位で積むわけだが、論理的に見るともう少し大きい単位がある。それを
スタックフレーム（stack frame）と言う。
スタックフレームは一つが関数呼び出し一回に対応している。つまり関数を呼
ぶとスタックフレームを一つ積む。returnするとスタックフレームを一つ降
ろす。思い切り単純化すればマシンスタックの様子は図1のよう
に図示できる。
図1: マシンスタック
この図ではスタックの先端を「上」と書いたが、マシンスタッ クは必ずしも低位アドレスから高位アドレスに伸びるとは限らない。例えば x86マシンではスタックは低位アドレスに向かって伸びる。
alloca()
malloc()を使うとヒープ上に任意の大きさのメモリ領域をもらうことができた。
alloca()はそれのマシンスタック版である。ただしmalloc()と違って
alloca()で割り当てたメモリは解放しなくていい。あるいは、関数のreturnと
ともに解放「されてしまう」と言ったほうがいいだろうか。だから割り当てた
値を関数の返り値にしたりすることはできない。「ローカル変数を指すポイン
タを返してはいけない」というのと同じである。
ここまではいい。長さを実行時に変えられる配列をローカルに割り当てられる、 という程度のことだ。
だが世の中にはネイティブのalloca()がない環境というのがある。そういう場
合でもalloca()は使いたいと思う人は多いので、同じ働きをする関数がCで
書いてあったりする。ただこの場合は「解放する必要がない」という特徴だけ
が実装されていて、マシンスタック上にメモリを割り当ててくれるとは限らな
い。と言うか、普通は取らない。それができるならそもそもネイティブの
alloca()が実装できるということだからだ。
alloca()をCで実装するにはどうするか。一番簡単な実装だと、まず
普通にmalloc()でメモリを割り当てる。そしてalloca()を呼び出した関数と
割り当てたアドレスの組をグローバルなリストに覚えさせておく。
あとは次にalloca()が呼び出されたときについでにそのリストをチェックし、
既に終了した関数で割り当てたメモリがあったらfree()で解放すればいい
（図2）。
図2: Cで実装したalloca()の動き
rubyのmissing/alloca.cがこのエミュレート版alloca()の実装例だ。
ここからがようやく本章の主題、ガーベージコレクションの話題だ。
オブジェクトは普通、メモリのうえにある。当然の帰結として、オブジェクトを
たくさん作ればメモリをたくさん使う。メモリが無限に使えるなら何も問題
はないのだが、現実にはメモリの量には必ず限りがある。だから使わなくなっ
たメモリは回収して再利用しなければいけない。もう少し具体的に言うならば、
malloc()でもらったメモリはfree()で返さなければいけない。
しかしmalloc()とfree()の管理を全てプログラマにやらせるとプログラマはと
ても大変である。特にオブジェクト指向プログラムではオブジェクト同士が相
互に参照しあっていて、どのタイミングでメモリを解放すればいいのかわかり
にくい。
そこでガーベージコレクションだ。
ガーベージコレクション（garbage collection、以下GC）とは、
必要のなくなった
メモリを自動的に検出し解放してくれる機能である。GCさえ
あれば「いつfree()したらいいんだー」などと悩む必要がない。これがあるのと
ないのではプログラムの書きやすさが格段に違うのだ。
ところで、以前何かの本に「使えるメモリがこまぎれになっているのを整理す
るのがGC」と書いてあったのを見たことがある。これは「
コンパクション（compaction）」と言う作業だ。
コンパクトになるからコンパクションである。
コンパクションをやるとメモリキャッシュにヒットしやすくなるのでスピード
アップにそれなりの効果があるのだが、これはGCの主目的ではない。GCの目的
はあくまでメモリの回収である。実際、メモリの回収はしてもコンパクション
はしないGCも多い。rubyのGCもコンパクションはしない。
では具体的にどんなシステムでGCが使えるのだろうか。
CやC++ではアドオンとして使える
Boehm GC\footnote{Boehm GC http://www.hpl.hp.com/personal/Hans_Boehm/gc}と
いうものがある。
またJavaやPerl、Python、C#、Eiffelなど最近の言語にとってはGCは
標準装備だ。そしてもちろんRubyにもGCがある。
本章ではrubyのGCの詳細を追っていこう。対象となるファイルはgc.cである。
GCのアルゴリズムについて説明するにはまず、「GCとは何であるか」を 説明しないといけない。つまり「必要のないメモリ」とはどういう状態に あるメモリか、ということである。
話を具体的にするためにオブジェクトとリンクだけに構造を単純化しよう。 つまり図3のような状態になっている。
図3: オブジェクト
グローバル変数から指されていたり、言語のスタック上にあるオブジェクトは まず「確実に必要」である。さらにそのオブジェクトのインスタンス変数など から指されているオブジェクトも必要である。さらにそれらのオブジェトから リンクを辿って到達できるオブジェクトもやはり必要だ。
これをもう少し論理的に言うと、「確実に必要」なオブジェクトを起点として 再帰的にリンクを辿ったときに到達できるオブジェクト全てが必要である、と なる。図4にそのイメージを書いた。線の左側にあるのが「確実 に必要なオブジェクト」で、そこから辿れるものが黒く塗りつぶされている。 この黒く塗られたオブジェクトが必要なものだ。残りは解放してよい。
図4: 必要なオブジェクトと必要でないオブジェクト
専門用語だとこの「確実に必要なオブジェクト」のことを 「GCのルート」と呼ぶことになっている。 必要なオブジェクトを辿った結果として見えて くるツリー構造の根（root）になるからだ。
GCが最初に実装されたのはLispなのだが、そのLispで最初に実現されたGCつまり
世界で最初のGCを、マーク&スイープ（mark&sweep）型GCと言う。
rubyのGCもこの一種である。
マーク&スイープGCのイメージは「必要なオブジェクト」の定義にかなり近い。 まずルートオブジェクトに「マーク」を付ける。そしてこれを出発点として、 そこから辿れるオブジェクトに片端から「マーク」をつけていく。この全体が 「マーク」フェイズだ。
そしてこれ以上辿れるオブジェクトがない、とわかったところでオブジェクト溜まりを 全部チェックし、マークのついていないオブジェクトを全部解放する（スイー プ）。スイープはマインスイーパのsweep（掃除する）だ。
長所は二点である。
短所もやはり二点。
エディタのEmacsを使っているとときどき「Garbage collecting...」と出て
反応が全くなくなることがあるのだが、そのときにGCをやっているのである。
これは二点目の短所がモロに出る例だ。ただしこの点はアルゴリズムを変える
ことで改善できる（インクリメンタルGCと言う）。
ストップ&コピーGCはマーク&スイープGCの変形である。まずオブジェクト領域 を複数用意する。ここでは話を単純にするために領域AとBの二つとしよう。そ して片方に「active」マークを付けておき、オブジェクトを生成するときは activeなほうにだけ作る（図5）。
図5: ストップ&コピー（1）
いざGCが発動したら、マーク&スイープと同じようにルートから辿る。しかし マークの代わりにオブジェクト自体をもう一つの領域に移動してしまう （図6）。リンクを全て辿り終えたらAに残ったオブジェクトは捨て、 今度はBをactiveにすればいい。
図6: ストップ&コピー（2）
ストップ&コピーGCの長所もまた二点ある。
短所も二点だ。
世の中うまいことばかりではないようだ。
リファレンスカウントはこれまでのものとは少し違い、到達チェックを コードのあちこちに分散させるようになっている。
まずオブジェクト一つ一つに整数のカウンタを付ける。変数や配列経由で参照 するときは参照するオブジェクトのカウンタを増やす。参照するのをやめたら 同時にカウンタを減らす。それでカウンタが0になったら解放する。それが リファレンスカウントという方式である（図7）。
図7: リファレンスカウント
この方式も長所が二点。
そして短所も二点だ。
二点目について解説しておこう。サイクル（cycle）とは 図8のように参照関係が循環している状態のことだ。 こうなってしまうとカウンタが減らなくなり、絶対に解放されなくなる。
図8: サイクル
ちなみに最新のPython（2.2）はリファレンスカウントGCを使っているのだが サイクルも解放できる。しかしそれはリファレンスカウント自体の力ではなく、 ときどきマーク&スイープGCをやってチェックしているからだ。
rubyのGCはRubyオブジェクトのみが対象だ。しかもrubyが生成し
管理しているオブジェクトでないといけない。逆に言うとユーザが
勝手に割りあてたメモリまでは面倒を見てくれないということだ。
例えば以下の関数は例えrubyが稼働中だろうとメモリリークを起こす。
void not_ok()
{
malloc(1024); /* メモリをもらっては捨てる */
}
しかし以下の関数はメモリリークを起こさない。
void this_is_ok()
{
rb_ary_new(); /* Rubyの配列を作っては捨てる */
}
rb_ary_new()はその中でrubyの正式インターフェイスを使ってメ
モリを割り当てるのでrubyのGCの管理下にあり、rubyが面倒を
見てくれる。
struct RVALUE
オブジェクトの実体は構造体だったから、オブジェクトの管理とは即ちこの構
造体の管理だ。もちろん非ポインタのFixnum Symbol nil true falseなどは
例外だが、しつこくなるのでそれはいちいち書かない。
実体の構造体のサイズは型ごとにマチマチだが、恐らく管理が大変になるの を避けるためだろう、組み込みクラスの構造体の共用体を宣言して、メモリを さわるときは常にその共用体を介して扱うようになっている。その共用 体の宣言がこれだ。
▼RVALUE
211 typedef struct RVALUE {
212 union {
213 struct {
214 unsigned long flags; /* 使われていないときはゼロ */
215 struct RVALUE *next;
216 } free;
217 struct RBasic basic;
218 struct RObject object;
219 struct RClass klass;
220 struct RFloat flonum;
221 struct RString string;
222 struct RArray array;
223 struct RRegexp regexp;
224 struct RHash hash;
225 struct RData data;
226 struct RStruct rstruct;
227 struct RBignum bignum;
228 struct RFile file;
229 struct RNode node;
230 struct RMatch match;
231 struct RVarmap varmap;
232 struct SCOPE scope;
233 } as;
234 } RVALUE;
(gc.c)
struct RVALUEは要素が一つだけの構造体だ。unionを直接使わないのはデバッ
グや将来の拡張のときに簡単にメンバを増やせるようにするためだそうである。
まずは共用体の最初の要素free.flagsに注目しよう。コメントには「使われて
いないときはゼロ」と書いてあるが本当だろうか。まだ使っているオブジェク
トのfree.flagsが偶然0になることはないのだろうか。
第2章『オブジェクト』で見たように、全てのオブジェクト構造体は
struct RBasicを最初の要素に持つ。だから共用体のどの要素からアクセスしても
obj->as.free.flagsはobj->as.basic.flagsと書くのと同じことだ。そして
オブジェクトは必ずフラグに構造体型フラグ（T_STRINGなど）を持ち、しか
もそのフラグは全て0以外なので、「生きている」オブジェクトのフラグが偶
然0になることはない。つまりフラグを0にすることで「死に」オブジェクトを
表すのは必要十分だと確かめられる。
全てのオブジェクト構造体のためのメモリはグローバル変数
heapsにまとめられている。以下これをオブジェクトヒープと呼ぼう。
▼オブジェクトヒープ
239 #define HEAPS_INCREMENT 10 240 static RVALUE **heaps; 241 static int heaps_length = 0; 242 static int heaps_used = 0; 243 244 #define HEAP_MIN_SLOTS 10000 245 static int *heaps_limits; 246 static int heap_slots = HEAP_MIN_SLOTS; (gc.c)
heapsはstruct RVALUEの配列の配列だ。heapSだから、入っている配列
一本一本がheapだろう。heapの要素一つ一つはslotである
（図9）。
図9: heaps、heap、slot
heapsの長さはheaps_lengthで可変。そのうち実際に使っているスロット
の数がheaps_used。heap一本の長さは対応するheaps_limits[index]に
入っている。つまりオブジェクトヒープの構造は図10のようになる
だろう。
図10: メモリ上に展開されたheapsの概念図
この構造には必然性がある。例えば全ての構造体を一つの配列に配置すると
メモリ空間は最もコンパクトになるが、アドレスが変わってしまう恐れがある
のでrealloc()できない。VALUEは単なるポインタだからだ。
とあるJavaの実装だとVALUEに相当するものがアドレスではなくてオブジェク
トのインデックスで、ポインタテーブルを経由して取り扱われるようになって
いるため、オブジェクトを移動することができる。ただしその場合は
オブジェクトアクセスのたびに配列のインデクシングが入るので多少
パフォーマンスは落ちる。
一方RVALUEへのポインタ（つまりVALUE）の一次元配列にした場合はどうだろ
うか。これは一見うまくいきそうだが、GCのときに困ってしまう。というのも、
これから詳しく書くとおり、rubyのGCでは「VALUE（RVALUEへのポインタ）ら
しい」整数を知る必要があるからだ。全てのRVALUEがてんでバラバラのアドレ
スに配置されていると、全てのRVALUEのアドレスと「ポインタかもしれない」
整数全てをそれぞれ比較しなければいけない。これではGCの速度は O(n^2) 以
上のオーダーになり、容認できない。
以上の条件から、オブジェクトヒープはある程度アドレスにまとまりがあり、 しかも位置と総量は制限されないような構造にするのがよいというわけだ。
freelist
使われていないRVALUEはfreelistから始まるリンク
リストに一本につながれて管理される。RVALUEのas.free.nextはそのため
に使うリンクだ。
▼freelist
236 static RVALUE *freelist = 0; (gc.c)
add_heap()
データ構造がわかったところでヒープを追加する関数add_heap()を読んでみよ
う。この関数はやたらと本筋以外の記述がうるさいので、エラー処理やキャス
トを省いて簡単にしたものを見せる。
▼add_heap()（簡約版）
static void
add_heap()
{
RVALUE *p, *pend;
/* 必要ならheapsをのばす */
if (heaps_used == heaps_length) {
heaps_length += HEAPS_INCREMENT;
heaps = realloc(heaps, heaps_length * sizeof(RVALUE*));
heaps_limits = realloc(heaps_limits, heaps_length * sizeof(int));
}
/* heapを一つ増やす */
p = heaps[heaps_used] = malloc(sizeof(RVALUE) * heap_slots);
heaps_limits[heaps_used] = heap_slots;
pend = p + heap_slots;
if (lomem == 0 || lomem > p) lomem = p;
if (himem < pend) himem = pend;
heaps_used++;
heap_slots *= 1.8;
/* 割り当てたRVALUEをfreelistにつなぐ */
while (p < pend) {
p->as.free.flags = 0;
p->as.free.next = freelist;
freelist = p;
p++;
}
}
以下の点を確認しておいてほしい。
heapの長さはheap_slotsheap_slotsはheapが一つ増えるごとに1.8倍になっていくheaps[i]の長さ（ヒープ生成時のheap_slotsの値）はheaps_limits[i]に格納されている
またlomemとhimemを変更しているのもこの関数だけなので、この関数だけから
仕組みが理解できる。この変数にはオブジェクトヒープの最下位アドレスと
最上位アドレスが入っているのである。この値はあとで「VALUEっぽい」整数を
判断するときに使う。
rb_newobj()
以上の点を総合して考えればオブジェクトを生成する方法はすぐにわかる。
freelistにつながれているRVALUEがあればそれを使い、なければGCするか、
ヒープを増やせばよい。オブジェクト生成を行う関数rb_newobj()を読んで
確かめてみよう。
▼rb_newobj()
297 VALUE
298 rb_newobj()
299 {
300 VALUE obj;
301
302 if (!freelist) rb_gc();
303
304 obj = (VALUE)freelist;
305 freelist = freelist->as.free.next;
306 MEMZERO((void*)obj, RVALUE, 1);
307 return obj;
308 }
(gc.c)
freelistが0、つまり余りの構造体がないならGCを起動して領域を作る。
もし一つもオブジェクトを回収できなくても、rb_gc()の中で新しい
領域を割り当ててくれるので問題ない。そしてfreelistから構造体を
一つ取り出し、MEMZERO()で0を充填、それを返す、となる。
説明したとおり、rubyのGCはマーク&スイープである。マークとは具体的には
FL_MARKフラグをセットすることだ。使われているVALUEを探しては
FL_MARKをセットし、これで全部調べたと思ったらオブジェクトヒープを見て、
FL_MARKがセットされていないオブジェクトを解放すればいい。
rb_gc_mark()
rb_gc_mark()はオブジェクトを再帰的にマークする関数である。
▼rb_gc_mark()
573 void
574 rb_gc_mark(ptr)
575 VALUE ptr;
576 {
577 int ret;
578 register RVALUE *obj = RANY(ptr);
579
580 if (rb_special_const_p(ptr)) return; /* special const not marked */
581 if (obj->as.basic.flags == 0) return; /* free cell */
582 if (obj->as.basic.flags & FL_MARK) return; /* already marked */
583
584 obj->as.basic.flags |= FL_MARK;
585
586 CHECK_STACK(ret);
587 if (ret) {
588 if (!mark_stack_overflow) {
589 if (mark_stack_ptr - mark_stack < MARK_STACK_MAX) {
590 *mark_stack_ptr = ptr;
591 mark_stack_ptr++;
592 }
593 else {
594 mark_stack_overflow = 1;
595 }
596 }
597 }
598 else {
599 rb_gc_mark_children(ptr);
600 }
601 }
(gc.c)
まずRANY()の定義はこうだ。特にたいしたものではない。
▼RANY()
295 #define RANY(o) ((RVALUE*)(o)) (gc.c)
最初にポインタでないものや既に解放したオブジェクトのチェック、 マークされたオブジェクトの再帰チェックがあり、
obj->as.basic.flags |= FL_MARK;
でobj（つまり関数の引数ptr）がマークされる。
そうしたら次はobjから出ている参照を辿ってマークする番である。
rb_gc_mark_children()がそれだ。
その他の、CHECK_STACK()から始まっていろいろと書いてあるのはマシンスタッ
ク溢れを防ぐための仕掛けである。rb_gc_mark()は再帰呼び出しを使ってオブ
ジェクトをマークするため、大きなオブジェクトクラスタがあるとマシンスタッ
クの長さが足りなくなることがある。そこでスタックが溢れそうだったら再帰
を中止してオブジェクトをグローバルなリストに積んでおき、あとからもう一
度マークしなおすようにしているのだ。
このコードは本筋ではないので省略する。
rb_gc_mark_children()
さて、rb_gc_mark_children()だが、
内部の型をひたすら並べて地道にマークしているだけなので長いうえに
面白くない。ここでは単純な列挙部分は省略して載せる。
▼rb_gc_mark_children()
603 void
604 rb_gc_mark_children(ptr)
605 VALUE ptr;
606 {
607 register RVALUE *obj = RANY(ptr);
608
609 if (FL_TEST(obj, FL_EXIVAR)) {
610 rb_mark_generic_ivar((VALUE)obj);
611 }
612
613 switch (obj->as.basic.flags & T_MASK) {
614 case T_NIL:
615 case T_FIXNUM:
616 rb_bug("rb_gc_mark() called for broken object");
617 break;
618
619 case T_NODE:
620 mark_source_filename(obj->as.node.nd_file);
621 switch (nd_type(obj)) {
622 case NODE_IF: /* 1,2,3 */
623 case NODE_FOR:
624 case NODE_ITER:
/* …………省略………… */
749 }
750 return; /* basic.klassはマークしなくてよい */
751 }
752
753 rb_gc_mark(obj->as.basic.klass);
754 switch (obj->as.basic.flags & T_MASK) {
755 case T_ICLASS:
756 case T_CLASS:
757 case T_MODULE:
758 rb_gc_mark(obj->as.klass.super);
759 rb_mark_tbl(obj->as.klass.m_tbl);
760 rb_mark_tbl(obj->as.klass.iv_tbl);
761 break;
762
763 case T_ARRAY:
764 if (FL_TEST(obj, ELTS_SHARED)) {
765 rb_gc_mark(obj->as.array.aux.shared);
766 }
767 else {
768 long i, len = obj->as.array.len;
769 VALUE *ptr = obj->as.array.ptr;
770
771 for (i=0; i < len; i++) {
772 rb_gc_mark(*ptr++);
773 }
774 }
775 break;
/* …………省略………… */
837 default:
838 rb_bug("rb_gc_mark(): unknown data type 0x%x(0x%x) %s",
839 obj->as.basic.flags & T_MASK, obj,
840 is_pointer_to_heap(obj) ? "corrupted object"
: "non object");
841 }
842 }
(gc.c)
rb_gc_mark()を再帰呼び出ししているな、ということだけ確認してもらえば
それでよい。省略した部分にはNODEとT_xxxxがそれぞれ列挙されている。
NODEのことは第二部で紹介する。
それとT_DATA（拡張ライブラリに使う構造体）のマークの部分だけは確認した
いことがあるので見ておこう。このコードは二つめのswitch文から抜粋した。
▼rb_gc_mark_children()−T_DATA
789 case T_DATA: 790 if (obj->as.data.dmark) (*obj->as.data.dmark)(DATA_PTR(obj)); 791 break; (gc.c)
ここはrb_gc_mark()やその類似の関数ではなく、ユーザからもらった関数
dmarkを使っている。その中ではもちろんrb_gc_mark()なりなんなりを使
うだろうが、使わないこともありうる。例えば極端な場合で言うと、ユーザ
定義のオブジェクトにVALUEが入っていないならマークする必要はないだろう。
rb_gc()
ここまででオブジェクト単位の話は済んだので、ここからは全体を統轄する関数
rb_gc()を見ていくことにする。ここでマークしているのが「必要だということが
明らかに分かっているオブジェクト」つまり「GCのルート」だ。
▼rb_gc()
1110 void
1111 rb_gc()
1112 {
1113 struct gc_list *list;
1114 struct FRAME * volatile frame; /* gcc 2.7.2.3 -O2 bug?? */
1115 jmp_buf save_regs_gc_mark;
1116 SET_STACK_END;
1117
1118 if (dont_gc || during_gc) {
1119 if (!freelist) {
1120 add_heap();
1121 }
1122 return;
1123 }
/* ……全てのルートをマークする…… */
1183 gc_sweep();
1184 }
(gc.c)
マークすべきルートはこの後で順番に見せていくが、一点だけ触れておこう。
rubyではCPUのレジスタやマシンスタックもルートとする。
それはつまりCのローカル変数や引数も勝手にマークされるということだ。
例えば
static int
f(void)
{
VALUE arr = rb_ary_new();
/* ……いろいろする…… */
}
というように、ただ変数に入れておくだけでそのオブジェクトは保護されるの
だ。これはrubyのGCの非常に大きな特徴である。この機能があるからこそ
rubyの拡張ライブラリは異様に書き易くなっているのだ。
ただしもちろんスタックに置かれているのはVALUEばかりではない。何の関係も
ない値もたくさん存在する。そのあたりをどうやって解決しているのかがGCの
実装を見ていくときの鍵だ。
最初はインタプリタが使っている（rubyの）スタックフレームを
マークする。第三部まで行けばこれが何者かはわかるので今はあまり
深く考えなくてもいい。
▼Rubyスタックのマーク
1130 /* mark frame stack */
1131 for (frame = ruby_frame; frame; frame = frame->prev) {
1132 rb_gc_mark_frame(frame);
1133 if (frame->tmp) {
1134 struct FRAME *tmp = frame->tmp;
1135 while (tmp) {
1136 rb_gc_mark_frame(tmp);
1137 tmp = tmp->prev;
1138 }
1139 }
1140 }
1141 rb_gc_mark((VALUE)ruby_class);
1142 rb_gc_mark((VALUE)ruby_scope);
1143 rb_gc_mark((VALUE)ruby_dyna_vars);
(gc.c)
ruby_frame ruby_class ruby_scope ruby_dyna_varsがそれぞれ評価器の
スタックの先頭を指す変数で、それぞれその時点でのフレーム、クラススコープ、
ローカル変数スコープ、ブロックローカル変数を保持している。
次にCPUのレジスタをマークする。
▼レジスタのマーク
1148 FLUSH_REGISTER_WINDOWS;
1149 /* ここで全てのレジスタがjmp_bufに保存されなければならない */
1150 setjmp(save_regs_gc_mark);
1151 mark_locations_array((VALUE*)save_regs_gc_mark,
sizeof(save_regs_gc_mark) / sizeof(VALUE *));
(gc.c)
FLUSH_REGISTER_WINDOWSは特殊なので後にまわす。
setjmp()は本当は遠隔ジャンプのための関数なのだけど、
その副作用として引数（jmp_buf型の変数）にレジスタの内容を
保存するようになっている。
それを利用してレジスタの中身をマークしようというわけだ。
このあたりはかなり裏技っぽい。
ただしdjgppとHuman68kだけは特別扱いされている。
djgppというのはDOS用のgcc環境。
Human68kはシャープのX680x0シリーズのOSだ。
この二つの環境では通常のsetjmp()では全てのレジスタが書きこまれないよ
うで、setjmp()を以下のようにインラインアセンブラで再定義して明示的にレジスタを書き出し
ている。
▼オリジナル版setjmp
1072 #ifdef __GNUC__
1073 #if defined(__human68k__) || defined(DJGPP)
1074 #if defined(__human68k__)
1075 typedef unsigned long rb_jmp_buf[8];
1076 __asm__ (".even\n\ 2バイトアラインメント
1077 _rb_setjmp:\n\ 関数rb_setjmp()のラベル
1078 move.l 4(sp),a0\n\ 第一引数をレジスタa0にロード
1079 movem.l d3-d7/a3-a5,(a0)\n\ a0の指す先にレジスタをコピー
1080 moveq.l #0,d0\n\ d0に0をセット（返り値）
1081 rts"); return
1082 #ifdef setjmp
1083 #undef setjmp
1084 #endif
1085 #else
1086 #if defined(DJGPP)
1087 typedef unsigned long rb_jmp_buf[6];
1088 __asm__ (".align 4\n\ 4バイトアラインメントを指示
1089 _rb_setjmp:\n\ 関数rb_setjmp()のラベル
1090 pushl %ebp\n\ ebpをスタックにプッシュ
1091 movl %esp,%ebp\n\ スタックポインタをebpにセット
1092 movl 8(%ebp),%ebp\n\ 第一引数を拾いebpにセット
1093 movl %eax,(%ebp)\n\ 以下、各レジスタを
1094 movl %ebx,4(%ebp)\n\ ebpの指す先にストア
1095 movl %ecx,8(%ebp)\n\
1096 movl %edx,12(%ebp)\n\
1097 movl %esi,16(%ebp)\n\
1098 movl %edi,20(%ebp)\n\
1099 popl %ebp\n\ ebpをスタックから復帰
1100 xorl %eax,%eax\n\ eaxに0をセット（返り値）
1101 ret"); return
1102 #endif
1103 #endif
1104 int rb_setjmp (rb_jmp_buf);
1105 #define jmp_buf rb_jmp_buf
1106 #define setjmp rb_setjmp
1107 #endif /* __human68k__ or DJGPP */
1108 #endif /* __GNUC__ */
(gc.c)
アラインメント（alignment）というのはメモリに変数を置くときの
制約のことだ。
例えば32ビットマシンでは普通intは32ビットだが、メモリのど
こからでも32ビット取り出せるわけでは必ずしもない。特にRISCマシンだと制
約が強く、「4の倍数バイトから」とか「偶数バイトから」というふうに決め
られている。そういう制約があるほうがメモリアクセスユニットを単純化でき
る（その結果高速化できる）からだ。「4の倍数バイトから」という制約が
あるなら「4バイトアラインメント」と呼ぶ。
またdjgppやHuman68kのccではコンパイラが関数名の先頭にアンダーラインを
付ける規約があるようだ。だからアセンブラでCの関数を書くときは自分で先
頭にアンダーライン（_）を付けなければならない。このタイプの規約はライ
ブラリ関数と名前が重複しないようにするための工夫だ。UNIXでも少し前までは
アンダーラインを付けていたそうだが今はほぼなくなっている。
さてここまででレジスタの中身をjmp_bufに書きだせたので、
次のコードでマークする。
▼レジスタのマーク（再掲）
1151 mark_locations_array((VALUE*)save_regs_gc_mark,
sizeof(save_regs_gc_mark) / sizeof(VALUE *));
(gc.c)
mark_locations_array()というのが初めて出てきた。
これは別項目として見ておこう。
mark_locations_array()▼mark_locations_array()
500 static void
501 mark_locations_array(x, n)
502 register VALUE *x;
503 register long n;
504 {
505 while (n--) {
506 if (is_pointer_to_heap((void *)*x)) {
507 rb_gc_mark(*x);
508 }
509 x++;
510 }
511 }
(gc.c)
この関数は配列をまとめてマークするための関数なのだが、これまでのマーク
関数とは少し違う。これまでは確実にVALUEがある（オブジェクトを指すポイ
ンタだ）とわかっている場所をマークしてきた。しかし今度マークしようとし
ているのはレジスタ領域で、ここにはVALUE以外のものがあることも十分考え
られる。そこで、まずその数値がVALUEであるか（ポインタであるか）どうか
調べてみて、それらしく見えるならば全てポインタとして扱うことにする。
このような手法を「保守的GC（conservative GC）」と呼ぶ。
「とりあえず安全側に倒す」というところが保守的だということらしい。
では次はその「VALUEっぽいかどうか」を調べる関数
is_pointer_to_heap()を見よう。
is_pointer_to_heap()▼is_pointer_to_heap()
480 static inline int
481 is_pointer_to_heap(ptr)
482 void *ptr;
483 {
484 register RVALUE *p = RANY(ptr);
485 register RVALUE *heap_org;
486 register long i;
487
488 if (p < lomem || p > himem) return Qfalse;
489
490 /* pがポインタである可能性があるか調べる */
491 for (i=0; i < heaps_used; i++) {
492 heap_org = heaps[i];
493 if (heap_org <= p && p < heap_org + heaps_limits[i] &&
494 ((((char*)p)-((char*)heap_org))%sizeof(RVALUE)) == 0)
495 return Qtrue;
496 }
497 return Qfalse;
498 }
(gc.c)
簡単に説明すると次のようになる。
RVALUEがあるアドレスの最下端と最上端の間にあるか調べるRVALUEの先頭を指しているかどうか確かめる
このような仕組みなので、間違って本当はVALUEでない値をVALUEと
扱ってしまうことも当然ある。しかし少なくとも使っている
VALUEを見付けられないことはない。
それもこれだけのテストをしていれば意図的でない
限りそうそうVALUEでない値を拾うことはないと思われるので、GCで
得られる利点を考えれば十分に妥協できる。というわけだ。
最後に後回しにしておいたFLUSH_REGISTER_WINDOWS()について。
レジスタウィンドウ（register windows）とはマシンスタックの一部をCPUの
中に置いておくことができる機構である。ようするに用途を絞ったキャッシュ
だ。最近はSparcアーキテクチャにしか存在しない。レジスタウィンドウにも
VALUEが入っている可能性があるので、これも前もってメモリに落としておく
必要がある。
マクロの中身はこんな感じだ。
▼FLUSH_REGISTER_WINDOWS
125 #if defined(sparc) || defined(__sparc__)
126 # if defined(linux) || defined(__linux__)
127 #define FLUSH_REGISTER_WINDOWS asm("ta 0x83")
128 # else /* Solaris, not sparc linux */
129 #define FLUSH_REGISTER_WINDOWS asm("ta 0x03")
130 # endif
131 #else /* Not a sparc */
132 #define FLUSH_REGISTER_WINDOWS
133 #endif
(defines.h)
asm(...)は埋め込み
アセンブラだ。ただしアセンブラとは言ってもこのtaという命令は
特権命令の
コール、つまりCPUでなくOSの呼び出しである。だからこそOSごとに命令が
違うのだ。なお、コメントにはLinuxとSolarisしか書いていないが実際には
FreeBSDやNetBSDもSparcで動くのでこのコメントは間違いである。
それと、Sparcでない場合はそもそもフラッシュする必要がないので、
FLUSH_REGISTER_WINDOWSを無と定義している。このような、
マクロを無に還す手法はデバッグ出力などにも使える超有名手法だ。
ではまたrb_gc()の続きに戻ろう。今度はマシンスタックに置かれた
VALUEをマークする。
▼マシンスタックのマーク
1152 rb_gc_mark_locations(rb_gc_stack_start, (VALUE*)STACK_END); 1153 #if defined(__human68k__) 1154 rb_gc_mark_locations((VALUE*)((char*)rb_gc_stack_start + 2), 1155 (VALUE*)((char*)STACK_END + 2)); 1156 #endif (gc.c)
rb_gc_stack_startがスタックの開始アドレス（スタックの末尾）で
STACK_ENDが終了アドレス（先端）らしい。
そしてrb_gc_mark_locations()が実際にスタック領域をマークする。
rb_gc_mark_locations()が二回あるのはスタックが4バイトアラインメントで
ないアーキテクチャへの対策である。rb_gc_mark_locations()は
sizeof(VALUE)単位でマークを試すので、2バイトアラインメントの環境だとう
まくマークできないことがある。そこで2バイトズラしてもう一度マークする
わけだ。
ではrb_gc_stack_start、STACK_END、rb_gc_mark_locations()の
三つを順番に見ていこう。
Init_stack()
最初はrb_gc_stack_startだ。この変数はInit_stack()中でだけセットさ
れる。Init_という名前から想像がつくかもしれないが、この関数はrubyイン
タプリタの初期化の時点で呼ばれる。
▼Init_stack()
1193 void
1194 Init_stack(addr)
1195 VALUE *addr;
1196 {
1197 #if defined(__human68k__)
1198 extern void *_SEND;
1199 rb_gc_stack_start = _SEND;
1200 #else
1201 VALUE start;
1202
1203 if (!addr) addr = &start;
1204 rb_gc_stack_start = addr;
1205 #endif
1206 #ifdef HAVE_GETRLIMIT
1207 {
1208 struct rlimit rlim;
1209
1210 if (getrlimit(RLIMIT_STACK, &rlim) == 0) {
1211 double space = (double)rlim.rlim_cur*0.2;
1212
1213 if (space > 1024*1024) space = 1024*1024;
1214 STACK_LEVEL_MAX = (rlim.rlim_cur - space) / sizeof(VALUE);
1215 }
1216 }
1217 #endif
1218 }
(gc.c)
重要なのは真ん中の部分だけだ。つまり適当にローカル変数（スタックに確保される）を定義してそのア
ドレスをrb_gc_stack_startとする。__human68k__のコードにある
_SENDというのはコンパイラのライブラリかシステムが定義した変数だろう。
当然Stack ENDの略であろうと想像できる。
一方そのあとのHAVE_GETRLIMITでくくってあるコードではスタックの長さを
調べてゴニョゴニョとやっているようだ。これもrb_gc_mark_children()での
スタック溢れ防止の一貫である。無視していい。
STACK_END
次にスタックの先端を検出するマクロSTACK_ENDを見る。
▼STACK_END
345 #ifdef C_ALLOCA 346 # define SET_STACK_END VALUE stack_end; alloca(0); 347 # define STACK_END (&stack_end) 348 #else 349 # if defined(__GNUC__) && defined(USE_BUILTIN_FRAME_ADDRESS) 350 # define SET_STACK_END VALUE *stack_end = __builtin_frame_address(0) 351 # else 352 # define SET_STACK_END VALUE *stack_end = alloca(1) 353 # endif 354 # define STACK_END (stack_end) 355 #endif (gc.c)
SET_STACK_ENDが三通りあるので、まず一番下の場合から。alloca()はスタッ
クの先端に領域を割り当てて返すので、その返り値とスタックの先端アドレス
はかなり近いはずだ。そこでalloca()の返り値でスタック先端の近似とする。
次に戻って一番上を見よう。マクロC_ALLOCAが定義されている場合は
alloca()がネイティブで定義されてない……つまり、互換関数がCで定義され
ていることを示す。その場合はalloca()は内部でmalloc()でメモリを確保して
いるのであった。それではスタックの位置を取るのには全く役に立たない。そ
こでどうするかというと、いま実行中の関数のローカル変数（stack_end）が
スタックの先端に近いと判断してそのアドレスを使う（&stack_end）。
またこのコードには、何に使っているのかよくわからないalloca(0)も入って
いる。これはCで定義したalloca()の昔からの仕様で、いらない領域をチェッ
クして解放してね、という意味である。ちょうどGCをやっているから
alloca()の割り当てた分も一緒に解放してやろうというわけだ。しかしそれ
ならそれでこんなところに紛れこまさず別のマクロに入れておいたほうがいい
と思うのだが……。
そして最後に真ん中の場合、__builtin_frame_address()について。
__GNUC__はgcc（GNUのCコンパイラ）で定義されるシンボルである。
それを使って限定しているのだから、
これはgcc組み込みの拡張命令だ。__builtin_frame_address(n)で n 個前の
スタックフレームのアドレスが取れる。__builtin_frame_address(0)なら
現在のフレームのアドレスだ。
rb_gc_mark_locations()
最後は実際にスタックをマークする関数rb_gc_mark_locations()である。
▼rb_gc_mark_locations()
513 void
514 rb_gc_mark_locations(start, end)
515 VALUE *start, *end;
516 {
517 VALUE *tmp;
518 long n;
519
520 if (start > end) {
521 tmp = start;
522 start = end;
523 end = tmp;
524 }
525 n = end - start + 1;
526 mark_locations_array(start,n);
527 }
(gc.c)
基本的には領域をマークする関数mark_locations_array()に任せればよい。
この関数がやるのは引数をうまく調節することである。このような調整が
必要になるのは、マシンスタックが伸びる方向が決まっていないからだ。
低位アドレスに伸びる場合はendのほうが小さいし、高位アドレスに伸びる
場合はstartのほうが小さい。だからアドレスの小さいほうがstartになる
ようにここで揃えるのだ。
最後にインタプリタ組みこみのVALUEコンテナをマークする。
▼その他のルート
1159 /* 登録されているグローバル変数をマーク */
1160 for (list = global_List; list; list = list->next) {
1161 rb_gc_mark(*list->varptr);
1162 }
1163 rb_mark_end_proc();
1164 rb_gc_mark_global_tbl();
1165
1166 rb_mark_tbl(rb_class_tbl);
1167 rb_gc_mark_trap_list();
1168
1169 /* true、falseなどのインスタンス変数があればそれをマーク */
1170 rb_mark_generic_ivar_tbl();
1171
/* rubyのパーサで使う変数をマーク（パース中のみ） */
1172 rb_gc_mark_parser();
(gc.c)
Cのグローバル変数にVALUEを入れる場合はrb_gc_register_address()で
そのアドレスをユーザに登録してもらうことになっている。global_Listに
それが保存されているので、全部マークする。
rb_mark_end_proc()はRubyのEND文などで登録した、
プログラムの終了時に実行される
手続きオブジェクトのマーク（本書ではEND文は扱わない）。
rb_gc_mark_global_tbl()はグローバル変数のテーブルrb_global_tblの
マーク（次章『変数と定数』参照）。
rb_mark_tbl(rb_class_tbl)は前章でやったrb_class_tblのマーク。
rb_gc_mark_trap_list()はRubyの関数メソッドtrapで登録した
手続きオブジェクトのマーク（シグナル関係。これも本書では扱わない）。
rb_mark_generic_ivar_tbl()はtrueなどの非ポインタVALUEのために
用意されたインスタンス変数テーブルをマークする。
rb_gc_mark_parser()はパーサのセマンティックスタックをマークする
（セマンティックスタックについては第二部を参照）。
ここまででマークフェイズは終わりだ。
NODEの特別扱い
スイープフェイズはマークされていないオブジェクトを探して解放していく作
業だ。しかし、ちょっと理由があってT_NODE型のオブジェクトだけは特別扱い
されている。次のところを見てほしい。
▼gc_sweep()冒頭
846 static void
847 gc_sweep()
848 {
849 RVALUE *p, *pend, *final_list;
850 int freed = 0;
851 int i, used = heaps_used;
852
853 if (ruby_in_compile && ruby_parser_stack_on_heap()) {
854 /* yaccのスタックがマシンスタック上にない場合は
855 パース中はNODEを回収してはならない */
856 for (i = 0; i < used; i++) {
857 p = heaps[i]; pend = p + heaps_limits[i];
858 while (p < pend) {
859 if (!(p->as.basic.flags & FL_MARK) &&
BUILTIN_TYPE(p) == T_NODE)
860 rb_gc_mark((VALUE)p);
861 p++;
862 }
863 }
864 }
(gc.c)
NODEはパーサでプログラムを表現するために使うオブジェクトだ。NODEはコン
パイル中にはyaccというツールの用意するスタックに置かれるのだが、そのス
タックはマシンスタック上にあるとは限らない。具体的に言うと、
ruby_parser_stack_on_heap()が偽だとマシンスタック上にないことを示す。
するとその場合は生成途中のNODEがうっかり回収されてしまう危険があるので、
コンパイル中（ruby_in_compile）はT_NODE型のオブジェクトを無条件に
マークして、回収されないようにするのである。
ここまで来たらマークされていないオブジェクトは全て解放できるようになる。 が、解放前にもう一仕事しなければならない。Rubyではオブジェクトの解放を フックできるようになっているので、これを呼ぶ必要がある。このフックを ファイナライザ（finalizer）と言う。
▼gc_sweep()中盤
869 freelist = 0;
870 final_list = deferred_final_list;
871 deferred_final_list = 0;
872 for (i = 0; i < used; i++) {
873 int n = 0;
874
875 p = heaps[i]; pend = p + heaps_limits[i];
876 while (p < pend) {
877 if (!(p->as.basic.flags & FL_MARK)) {
878 (A) if (p->as.basic.flags) {
879 obj_free((VALUE)p);
880 }
881 (B) if (need_call_final && FL_TEST(p, FL_FINALIZE)) {
882 p->as.free.flags = FL_MARK; /* マークされたまま残る */
883 p->as.free.next = final_list;
884 final_list = p;
885 }
886 else {
887 p->as.free.flags = 0;
888 p->as.free.next = freelist;
889 freelist = p;
890 }
891 n++;
892 }
893 (C) else if (RBASIC(p)->flags == FL_MARK) {
894 /* ファイナライズが必要なオブジェクト。 */
895 /* 何もしないで放っておく */
896 }
897 else {
898 RBASIC(p)->flags &= ~FL_MARK;
899 }
900 p++;
901 }
902 freed += n;
903 }
904 if (freed < FREE_MIN) {
905 add_heap();
906 }
907 during_gc = 0;
(gc.c)
オブジェクトヒープを端から全て見てゆき、FL_MARKフラグが立っていなかっ
たらobj_free()で解放する（A）。obj_free()では例えば文字列オブジェクトが
使うchar[]や配列オブジェクトが使うVALUE[]を解放するだけで、
RVALUE構造体を解放したりはないし、basic.flagsも全くいじらない。だ
からobj_free()を呼んだあとにその構造体を操作しても落ちる心配はない。
オブジェクトを解放したあと、FL_FINALIZEフラグによって分岐する（B）。
FL_FINALIZEが立っていたらそのオブジェクトに対してファイナライザが定義
されているのでfinal_listに、立っていなかったらすぐにfreelistに追加す
る。またファイナライズするときはbasic.flagsをFL_MARKにする。これで構造
体型フラグ（T_STRINGなど）がクリアされるので、生きているオブジェクトと
区別が付く。
あとはまとめてファイナライザを実行すれば終わりだ。ここで、ファイナライ ザを呼ぶときはフック対象となったオブジェクトは既に死んでいることに注 意しよう。つまりファイナライザ実行中に、フックをかけたオブジェクトを使 うことはできない。
▼gc_sweep()残り
910 if (final_list) {
911 RVALUE *tmp;
912
913 if (rb_prohibit_interrupt || ruby_in_compile) {
914 deferred_final_list = final_list;
915 return;
916 }
917
918 for (p = final_list; p; p = tmp) {
919 tmp = p->as.free.next;
920 run_final((VALUE)p);
921 p->as.free.flags = 0;
922 p->as.free.next = freelist;
923 freelist = p;
924 }
925 }
926 }
(gc.c)
後半のforがメインのファイナライズ作業だ。前半のifは様々な理由により
Rubyプログラムに実行を移せない場合だ。ここでファイナライズを遅らせた
オブジェクトは先程のリストの経路（C）に出てくる。
rb_gc_force_recycle()
最後に少し違う話をしよう。ここまではrubyのガーベージコレクタがオブジェクトを回収する
かしないか決めていたが、ユーザから明示的に回収させることもできる。そ
れがrb_gc_force_recycle()である。
▼rb_gc_force_recycle()
928 void
929 rb_gc_force_recycle(p)
930 VALUE p;
931 {
932 RANY(p)->as.free.flags = 0;
933 RANY(p)->as.free.next = freelist;
934 freelist = RANY(p);
935 }
(gc.c)
仕組みはたいしたことはないが、第二部・第三部で何度か出会うことになるので 紹介しておいた。
個々のオブジェクトで割りあてた領域、例えばStringのchar[]など、はスイー
プフェイズの中で解放されていたが、RVALUE構造体自体を解放するコードは出
てこなかった。またオブジェクトヒープでも使っている構造体の数の管理など
はやっていない。ということは、rubyのオブジェクト領域は一度割り当てたら
絶対に解放されないのだ。
例えば筆者がいま作っているメーラは500通のメールのスレッドを構築する とき一時的に40Mバイトくらい領域を使うのだが、そのあとGCされて大半を使わなく なったとしてもずっと40Mバイト占有し続ける。筆者のマシンもイマドキのやつなの で40Mバイトくらい使われたところでなんともないが、ずっと起動しっぱなしの サーバなどでこれが起きると問題になることもあるだろう。
ただしfree()すればメモリ使用量が減るとも限らないことには留意すべきであ
る。メモリをOSに返さない限りプロセスのメモリ使用量は減らない。そして
malloc()の実装によってはfree()してもメモリがOSに返されないことはよく
ある。
……と書いていたのだが、なんと本書の締切間際にRVALUEが解放されるように
なってしまった。添付CD-ROMには最新版のrubyも入っているからdiffして
見てみてほしい。……なんて酷いオチだ。
マーク&スイープには「オブジェクト領域全体を最低でも一度なめる必要が ある」という弱点があった。世代別GCという考えかたを使うとその弱点を補え る可能性がある。
世代別GCの基礎になるのは「ほとんどのオブジェクトは寿命が非常に長いか 非常に短いかのどちらかである」という経験則だ。この点は自分の書くプロ グラムのことをちょっと考えてみれば納得がいくと思う。
さて、この規則を踏まえて考えてみると「長生きするオブジェクトは毎回毎回 マークしてスイープしなくてもいいじゃないか」という発想が出てくる。この オブジェクトは長生きだな、と思ったら、特別扱いにしてGC対象から外せばい いのだ。するとマークにしてもスイープにしてもオブジェクトの数を圧倒的に 減らすことができる。例えば特定のGCのタイミングで長生きしているオブジェ クトが半分を占めているとすれば対象オブジェクト数は半分になる。
ただ一つ問題がある。世代別GCはオブジェクトを移動できないと非常にやりに
くいのだ。なぜかというと、長生きするオブジェクトは先程書いたとおり「特
別扱い」しないといけないからである。世代別GCは扱うオブジェクトを減らし
てコストを下げるわけだから、この二つの世代にあるオブジェクトをきっちり
分類しておかないと結局のところ両方を対象にするのと変わらなくなってしま
う。またさらにrubyのGCはconservative GCであるから、
is_pointer_to_heap()が動くようにも作らなければならない。これが難しい。
そこでどうやってこの問題を解決するかだが……木山真人さんの手によって
rubyのための世代別GCの実装が公開されている。以下はこのパッチが各種の
問題にどう対処したのかを簡単に示していくことにしよう。また今回は
木山さんのご厚意により、この世代別GCパッチと論文を添付CD-ROMに収録して
いる\footnote{木山版世代別GCパッチについては添付CD-ROMのdoc/generational-gc.htmlをまず参照のこと}。
では説明に入る。説明がしやすいように、 長生きするオブジェクトを「旧世代オブジェクト」、 短い寿命のオブジェクトを「新世代オブジェクト」 と呼ぶことにしよう。
最初に、最大の問題である旧世代オブジェクトの特別扱いについて。この点は
新世代のオブジェクトだけをnewlistというリンクリストにつなぐことで解決
している。またこのリストはRVALUEの要素を増やすことで実現する。
第二に、旧世代のオブジェクトを見付ける方法について。これはとても簡単で、
newlistでGCされなかったものをnewlistから外すだけだ。つまり一回GCを生き
残ると旧世代のオブジェクトとして扱われる。
第三に、旧世代から新世代への参照を検出する方法について。世代別GCでは、 言ってみれば、旧世代のオブジェクトにはマークが付きっぱなしの状態になる わけだ。しかし旧世代から新世代へリンクが出ている場合、その新世代の オブジェクトにはマークが付かなくなる（図11）。
図11: 世代を越えた参照
これではまずいので、旧世代のオブジェクトから新世代のオブジェクトを参照 したらその瞬間にその新世代のオブジェクトは 旧世代にならなければいけない。そこでライブラリを修正し、こういう 参照が起こる可能性のあるところにひたすらチェックを入れるようにしている。
仕組みの概要は以上である。このパッチは当初ruby 1.7に取りこまれる予定だっ
たのだが結局まだ取りこまれていない。「速度が出なかった」というのが理由
だそうだ。第三点の「参照全チェック」のコストが効いているのではないか、
という推測もなされているが、詳しい原因はまだよくわかっていない。
rubyのGCでコンパクションはできるだろうか。rubyのVALUEは
構造体への直ポ
インタであるから、コンパクションして構造体のアドレスが変わったら、
移動した構造体を指しているVALUEを全て書き換えないといけない。
ところがrubyのGCはconservative GCなので「それが本当にVALUEかどうかわか
らない場合」がありうる。それなのにその値を書き換えてしまったら、もし
VALUEでなかったときにはとんでもないことになる。コンパクションと
conservative GCはとても相性が悪いのだ。
だがなんとかして対策を考えてみよう。まずVALUEをポインタでなく
オブジェクトIDに
する方法が考えられる（図12）。VALUEと構造体の間に一
枚間接層を挟む方法だ。これならVALUEを書き換えずに済むので安心して構
造体を移動できる。だがその代償としてアクセス速度は遅くなるし、拡張ライ
ブラリの互換性もなくなる。
図12: オブジェクトID経由での参照
そこで次の方法として、「確実にVALUEである」ポインタ「だけ」から
指されている構造体に限定して移動するという手法がある（図13）。
この手法をMostly-copying garbage collectionと言う。普通のプログ
ラムならis_pointer_to_heap()が真になるオブジェクトはそうたくさんはない
から、かなりの確率でオブジェクト構造体を移動できることになる。
図13: Mostly-copying garbage collection
さらにさらに、もし構造体が移動できるということになれば、 同時に世代別GCの実装も簡単になる。挑戦してみる価値はありそうだ。
volatile
スタック上のVALUEはGCが面倒を見てくれると書いた。それならば
ローカル変数としてVALUEを置いておけばそのVALUEは確実にマークされる
はずである。しかし現実には最適化の影響で変数が消えてしまうことがある。
例えば次のような場合は消える可能性がある。
VALUE str;
str = rb_str_new2("...");
printf("%s\n", RSTRING(str)->ptr);
このコードではstr自体にアクセスしていないので、コンパイラによっては
str->ptrだけメモリに残してstrは消してしまうことがある。そうすると
strが回収されて落ちる。こういう時は仕方がないので、
volatile VALUE str;
とする。volatileはCの予約語で、この変数に関する最適化を禁止する
効果がある。Ruby関係のコードでvolatileが付いていたらまず間違いなく
GC対策と思ってよい。K&Rを読んだときは「こんなもの何に使うんだろう」
と思っていたのだが、まさかrubyでこんなに大量に見ることになるとは
思わなかった。
しかしこういうところを見るとconservative GCの「ユーザがGCを気にしなく
ていい」という謳い文句もあまり当てにならないようである。一時は
「KSMというSchemeのGCはvolatileが必要ないらしい」
という話もあったのだが、
アルゴリズムに穴があって結局rubyには適用できないようだ。
gc.c内部
GCが起動するのはどんなときだろうか。
gc.cの内部ではrb_gc()を呼んでいるところは三個所ある。
ruby_xmalloc()ruby_xrealloc()rb_newobj()
ruby_xmalloc()とruby_xrealloc()の場合はメモリ割り当てに失敗したときだ。
そこでGCすればメモリが解放されてまた使えるスペースができるかもしれない。
rb_newobj()も状況は似ていて、freelistが空になったときに起動する。
gc.c以外でもインタプリタ内でrb_gc()を呼んでいるところが何か所かある。
まずio.cとdir.cで、ファイルディスクリプタが足りなくて開けなかったとき
にGCを起動する。IOオブジェクトがGCされればファイルがクローズされて
ファイルディスクリプタが空くかもしれない、という目論見からだ。
ruby.cではファイルをロードしたあとでrb_gc()することがある。スイープの
ところで書いたとおり、コンパイル中にNODEをGCできないのを補うためである。
GCの話が終わってRubyオブジェクトの生成から解放までを扱えるように なったので、ここでオブジェクトの生成についての話をしておこう。これは GCとはあまり関係なく、むしろ前章でやったクラスの話に少し関ってくる。
これまで何度もオブジェクトを生成してきた。例えばこんな方法がある。
class C end C.new()
このときC.newはどうやってオブジェクトを生成しているのだろうか。
まずC.newは実際にはClass#newである。その実体はこうだ。
▼rb_class_new_instance()
725 VALUE
726 rb_class_new_instance(argc, argv, klass)
727 int argc;
728 VALUE *argv;
729 VALUE klass;
730 {
731 VALUE obj;
732
733 obj = rb_obj_alloc(klass);
734 rb_obj_call_init(obj, argc, argv);
735
736 return obj;
737 }
(object.c)
rb_obj_alloc()はklassに対してallocateというメソッドを呼ぶ。つま
りいま説明している例ならばC.allocateを呼ぶ。
そのデフォルトはClass#allocateで、そのまた実体が
rb_class_allocate_instance()である。
▼rb_class_allocate_instance()
708 static VALUE
709 rb_class_allocate_instance(klass)
710 VALUE klass;
711 {
712 if (FL_TEST(klass, FL_SINGLETON)) {
713 rb_raise(rb_eTypeError,
"can't create instance of virtual class");
714 }
715 if (rb_frame_last_func() != alloc) {
716 return rb_obj_alloc(klass);
717 }
718 else {
719 NEWOBJ(obj, struct RObject);
720 OBJSETUP(obj, klass, T_OBJECT);
721 return (VALUE)obj;
722 }
723 }
(object.c)
最後の三行以外は気にしなくていい。このNEWOBJ()とOBJSETUP()はこれまで
も何回か出てきた、Rubyのオブジェクトを作るときのイディオムである。今度
は中身も見てみよう。
▼NEWOBJ() OBJSETUP()
274 #define NEWOBJ(obj,type) type *obj = (type*)rb_newobj()
275 #define OBJSETUP(obj,c,t) do {\
276 RBASIC(obj)->flags = (t);\
277 RBASIC(obj)->klass = (c);\
278 if (rb_safe_level() >= 3) FL_SET(obj, FL_TAINT);\
279 } while (0)
(ruby.h)
rb_newobj()はRVALUEを一つfreelistから外して返してくれる関数だった。
NEWOBJ()はそのrb_newobj()に型のごまかしを加えたものにすぎないとわ
かる。またOBJSETUP()はstruct RBasic部分を初期化するマクロである。
こちらはFL_TAINTフラグを立てるのを忘れないためだけにあると思って
いいだろう。
あとはrb_class_new_instance()に戻ってrb_obj_call_init()を呼ぶことにな
る。この関数が作ったばかりのオブジェクトに対してinitializeを呼び出して
初期化は完了である。
まとめると以下のようになっている。
SomeClass.new = Class#new (rb_class_new_instance)
SomeClass.allocate = Class#allocate (rb_class_allocate_instance)
SomeClass#initialize = Object#initialize (rb_obj_dummy)
クラスメソッドのallocateが物理的な初期化、initializeが論理的な初期
化と言ってもいい。このような仕組み……つまりオブジェクト生成を
allocate・initializeに分割し、newが統轄するという仕組みを、
「アロケーションフレームワーク」と呼んでいる。
次は拡張ライブラリで定義したクラスのインスタンス生成について見ていく。
ユーザ定義と言うからにはその構造体は決まっていないわけで、その割り当て
かたを教えてあげないとrubyにはどうやって作っていいのかわからない。それ
を教える方法を見よう。
Data_Wrap_Struct()
ユーザ定義だろうとなんだろうと生成の仕組み自体はアロケーションフレーム
ワークに従えばいい。つまり新しいクラスSomeClassをCで定義するときは
SomeClass.allocateとSomeClass#initializeの両方をオーバーライドする。
まずはallocateのほうから見ていこう。ここでは物理的な初期化をする。
何を割り当てればよいかと言うと、ユーザ定義クラスのインスタンスは
struct RDataと、こちらで用意する構造体の組であった。仮にその構造体を
struct my型としておこう。そのstruct myを元にVALUEを作るには
Data_Wrap_Struct()というマクロを使う。使いかたはこうだ。
struct my *ptr = malloc(sizeof(struct my)); /* 適当にヒープに取る */ VALUE val = Data_Wrap_Struct(data_class, mark_f, free_f, ptr);
data_classがvalの所属するクラスで、ptrがラップしようとしているポ
インタだ。mark_fがこの構造体をマークするための関数（へのポインタ）。
と言ってもptr自体をマークするわけではもちろんなくて、ptrの指す構造
体の中にVALUEがあるときに使うものだ。一方のfree_fはptr自体を解放
するために使う関数である。どちらの関数も引数はptrだ。このあたりは少
し戻ってマークのコードを読んでもらえると一発で納得できると思う。
Data_Wrap_Struct()の中身も見ておこう。
▼Data_Wrap_Struct()
369 #define Data_Wrap_Struct(klass, mark, free, sval) \
370 rb_data_object_alloc(klass, sval, \
(RUBY_DATA_FUNC)mark, \
(RUBY_DATA_FUNC)free)
365 typedef void (*RUBY_DATA_FUNC) _((void*));
(ruby.h)
rb_data_object_alloc()にほとんど委譲されている。
▼rb_data_object_alloc()
310 VALUE
311 rb_data_object_alloc(klass, datap, dmark, dfree)
312 VALUE klass;
313 void *datap;
314 RUBY_DATA_FUNC dmark;
315 RUBY_DATA_FUNC dfree;
316 {
317 NEWOBJ(data, struct RData);
318 OBJSETUP(data, klass, T_DATA);
319 data->data = datap;
320 data->dfree = dfree;
321 data->dmark = dmark;
322
323 return (VALUE)data;
324 }
(gc.c)
なんてことはない。通常のオブジェクトと同じくNEWOBJ() OBJSETUP()を使って
RVALUEを用意し、メンバを入れるだけだ。
ここでallocateの話に戻ろう。ここまででVALUEは作れたので、あとはこれを
適当な関数に入れてrb_define_singleton_method()でクラスに定義して
やればよい。
Data_Get_Struct()
次はinitializeだ。initializeに限らず、メソッドではさっき作ったVALUEか
らstruct my*を取り出す方法が必要になるはずだ。そのためには
Data_Get_Struct()というマクロを使う。
▼Data_Get_Struct()
378 #define Data_Get_Struct(obj,type,sval) do {\
379 Check_Type(obj, T_DATA); \
380 sval = (type*)DATA_PTR(obj);\
381 } while (0)
360 #define DATA_PTR(dta) (RDATA(dta)->data)
(ruby.h)
見ての通り、RDataのメンバから（struct myへの）ポインタを取り出すだけ
である。簡単だ。Check_Type()は構造体型のチェックをするだけ。
と、ここまで何食わぬ顔で説明してきたのだが、実は現在のアロケーションフ
レームワークには致命的な問題がある。いま、allocateで作ったオブジェクト
がinitializeやその他のメソッドに出てくる、ということを言ったが、ここで
同じクラスのallocateで作ったオブジェクトが渡ってきてくれないと非常に困
るはずだ。例えばデフォルトのObject.allocate（Class#allocate）で作った
オブジェクトがStringのメソッドに渡ってしまったらとても困る。なぜなら
Stringのメソッドはstruct RStringの構造体がもらえると仮定して書いてある
のに、実際にはstruct RObjectだからだ。こういうことを防ぐためには、
C.allocateで作ったオブジェクトなら、Cか、その下位クラスのメソッドだけ
に渡るようにしなければならない。
もちろん普通にやっていればそうなる。C.allocateならクラスCのインスタン
スを作るわけだから、クラスCのメソッド以外には渡らないはずだ。
例外としてObjectのメソッドには渡る可能性があるが、
Objectのメソッドは構造体型に依存しないよう書いてある。
だが普通にやらなかったらどうだろうか。C.allocateはRubyレベルに露出して
いるので、まだ説明していないがaliasだのsuperだのを活用しまくると
allocateの定義を別のクラスに移植できてしまう。そうすると、クラスは
Stringなのに本当の構造体型はstruct RObject、なんてオブジェクトも
作れてしまう。つまりRubyレベルから好き放題rubyを落とせるのだ。これは
困る。
問題の根源はallocateがメソッドとしてRubyレベルに露出していることだ。
逆に言うとallocateの中身をメソッド以外の手段でクラスに定義しておけば
いい。そこで
rb_define_allocator(rb_cMy, my_allocate);
という感じの代替案が現在議論されている。
御意見・御感想・誤殖の指摘などは 青木峰郎 <aamine@loveruby.net> までお願いします。
『Rubyソースコード完全解説』 はインプレスダイレクトで御予約・御購入いただけます (書籍紹介ページへ飛びます)。
Copyright (c) 2002-2004 Minero Aoki, All rights reserved.