第5章ガ－ベージコレクション

プログラムの実行時イメージ

突然だが、本章を始めるに先立ち、プログラム実行時のメモリ空間の状態について予習をしておこうと思う。この章ではコンピュータの低レベルな部分にかなり踏み込んでいくことになるので、あらかじめある程度の知識を仕入れておかないと太刀打ちできないのだ。それにこの後の章になればいずれ必要になってくる。ここで一回やってしまえば後が楽だ。

セグメント

一般的なCプログラムではメモリ空間の中に以下の部分を持つ。

テキスト領域
スタティック変数やグローバル変数の置場
マシンスタック
ヒープ

テキスト領域はコードが置いてあるところ。二番目は見ての通り。マシンスタックには関数の引数やローカル変数が積まれる。ヒープはmalloc()で割り当ててもらうところだ。

三つめのマシンスタックについてもう少し話そう。マシン「スタック」と言うくらいだから当然スタック構造をしている。つまりどんどん新しいものを上に積み重ねていく。実際にマシンスタックに値を積むときはint一個などの細かい単位で積むわけだが、論理的に見るともう少し大きい単位がある。それをスタックフレーム（stack frame）と言う。

スタックフレームは一つが関数呼び出し一回に対応している。つまり関数を呼ぶとスタックフレームを一つ積む。returnするとスタックフレームを一つ降ろす。思い切り単純化すればマシンスタックの様子は図1のように図示できる。

(macstack)
図1: マシンスタック

この図ではスタックの先端を「上」と書いたが、マシンスタックは必ずしも低位アドレスから高位アドレスに伸びるとは限らない。例えば x86マシンではスタックは低位アドレスに向かって伸びる。

`alloca()`

malloc()を使うとヒープ上に任意の大きさのメモリ領域をもらうことができた。 alloca()はそれのマシンスタック版である。ただしmalloc()と違って alloca()で割り当てたメモリは解放しなくていい。あるいは、関数のreturnとともに解放「されてしまう」と言ったほうがいいだろうか。だから割り当てた値を関数の返り値にしたりすることはできない。「ローカル変数を指すポインタを返してはいけない」というのと同じである。

ここまではいい。長さを実行時に変えられる配列をローカルに割り当てられる、という程度のことだ。

だが世の中にはネイティブのalloca()がない環境というのがある。そういう場合でもalloca()は使いたいと思う人は多いので、同じ働きをする関数がCで書いてあったりする。ただこの場合は「解放する必要がない」という特徴だけが実装されていて、マシンスタック上にメモリを割り当ててくれるとは限らない。と言うか、普通は取らない。それができるならそもそもネイティブの alloca()が実装できるということだからだ。

alloca()をCで実装するにはどうするか。一番簡単な実装だと、まず普通にmalloc()でメモリを割り当てる。そしてalloca()を呼び出した関数と割り当てたアドレスの組をグローバルなリストに覚えさせておく。あとは次にalloca()が呼び出されたときについでにそのリストをチェックし、既に終了した関数で割り当てたメモリがあったらfree()で解放すればいい（図2）。

(calloca)
図2: Cで実装したalloca()の動き

rubyのmissing/alloca.cがこのエミュレート版alloca()の実装例だ。

概要

ここからがようやく本章の主題、ガーベージコレクションの話題だ。

GCとは

オブジェクトは普通、メモリのうえにある。当然の帰結として、オブジェクトをたくさん作ればメモリをたくさん使う。メモリが無限に使えるなら何も問題はないのだが、現実にはメモリの量には必ず限りがある。だから使わなくなったメモリは回収して再利用しなければいけない。もう少し具体的に言うならば、 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のアルゴリズムについて説明するにはまず、「GCとは何であるか」を説明しないといけない。つまり「必要のないメモリ」とはどういう状態にあるメモリか、ということである。

話を具体的にするためにオブジェクトとリンクだけに構造を単純化しよう。つまり図3のような状態になっている。

(objects)
図3: オブジェクト

グローバル変数から指されていたり、言語のスタック上にあるオブジェクトはまず「確実に必要」である。さらにそのオブジェクトのインスタンス変数などから指されているオブジェクトも必要である。さらにそれらのオブジェトからリンクを辿って到達できるオブジェクトもやはり必要だ。

これをもう少し論理的に言うと、「確実に必要」なオブジェクトを起点として再帰的にリンクを辿ったときに到達できるオブジェクト全てが必要である、となる。図4にそのイメージを書いた。線の左側にあるのが「確実に必要なオブジェクト」で、そこから辿れるものが黒く塗りつぶされている。この黒く塗られたオブジェクトが必要なものだ。残りは解放してよい。

(gcimage)
図4: 必要なオブジェクトと必要でないオブジェクト

専門用語だとこの「確実に必要なオブジェクト」のことを「GCのルート」と呼ぶことになっている。必要なオブジェクトを辿った結果として見えてくるツリー構造の根（root）になるからだ。

マーク&スイープ

GCが最初に実装されたのはLispなのだが、そのLispで最初に実現されたGCつまり世界で最初のGCを、マーク&スイープ（mark&sweep）型GCと言う。 rubyのGCもこの一種である。

マーク&スイープGCのイメージは「必要なオブジェクト」の定義にかなり近い。まずルートオブジェクトに「マーク」を付ける。そしてこれを出発点として、そこから辿れるオブジェクトに片端から「マーク」をつけていく。この全体が「マーク」フェイズだ。

そしてこれ以上辿れるオブジェクトがない、とわかったところでオブジェクト溜まりを全部チェックし、マークのついていないオブジェクトを全部解放する（スイープ）。スイープはマインスイーパのsweep（掃除する）だ。

長所は二点である。

GCの実装以外の場所ではGCのことを（あまり）考えなくていい
サイクルも解放できる（サイクルについてはリファレンスカウントの項を参照）

短所もやはり二点。

スイープのため最低一度はオブジェクトを全部なめる必要がある
GCの負荷が一点に集中する

エディタのEmacsを使っているとときどき「Garbage collecting...」と出て反応が全くなくなることがあるのだが、そのときにGCをやっているのである。これは二点目の短所がモロに出る例だ。ただしこの点はアルゴリズムを変えることで改善できる（インクリメンタルGCと言う）。

ストップ&コピー

ストップ&コピーGCはマーク&スイープGCの変形である。まずオブジェクト領域を複数用意する。ここでは話を単純にするために領域AとBの二つとしよう。そして片方に「active」マークを付けておき、オブジェクトを生成するときは activeなほうにだけ作る（図5）。

(stop2)
図5: ストップ&コピー（1）

いざGCが発動したら、マーク&スイープと同じようにルートから辿る。しかしマークの代わりにオブジェクト自体をもう一つの領域に移動してしまう（図6）。リンクを全て辿り終えたらAに残ったオブジェクトは捨て、今度はBをactiveにすればいい。

(stop3)
図6: ストップ&コピー（2）

ストップ&コピーGCの長所もまた二点ある。

メモリ回収と同時にコンパクションができる
しかも参照しているオブジェクト同士が近くに来るので

短所も二点だ。

オブジェクト領域が倍以上必要になる
オブジェクトの位置が変わってしまう

世の中うまいことばかりではないようだ。

リファレンスカウント

リファレンスカウントはこれまでのものとは少し違い、到達チェックをコードのあちこちに分散させるようになっている。

まずオブジェクト一つ一つに整数のカウンタを付ける。変数や配列経由で参照するときは参照するオブジェクトのカウンタを増やす。参照するのをやめたら同時にカウンタを減らす。それでカウンタが0になったら解放する。それがリファレンスカウントという方式である（図7）。

(refcnt)
図7: リファレンスカウント

この方式も長所が二点。

GCの負荷がプログラム全体に分散される
必要なくなったオブジェクトが即座に解放される

そして短所も二点だ。

カウンタ操作を忘れがち
単純にやるとサイクルを解放できない

二点目について解説しておこう。サイクル（cycle）とは図8のように参照関係が循環している状態のことだ。こうなってしまうとカウンタが減らなくなり、絶対に解放されなくなる。

(cycle)
図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）。

(heapitems)
図9: heaps、heap、slot

heapsの長さはheaps_lengthで可変。そのうち実際に使っているスロットの数がheaps_used。heap一本の長さは対応するheaps_limits[index]に入っている。つまりオブジェクトヒープの構造は図10のようになるだろう。

(heaps)
図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_slots
そのheap_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の）スタックフレームをマークする。第三部まで行けばこれが何者かはわかるので今はあまり深く考えなくてもいい。

▼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はオブジェクトを移動できないと非常にやりにくいのだ。なぜかというと、長生きするオブジェクトは先程書いたとおり「特別扱い」しないといけないからである。世代別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）。

(gengc)
図11: 世代を越えた参照

これではまずいので、旧世代のオブジェクトから新世代のオブジェクトを参照したらその瞬間にその新世代のオブジェクトは旧世代にならなければいけない。そこでライブラリを修正し、こういう参照が起こる可能性のあるところにひたすらチェックを入れるようにしている。

仕組みの概要は以上である。このパッチは当初ruby 1.7に取りこまれる予定だったのだが結局まだ取りこまれていない。「速度が出なかった」というのが理由だそうだ。第三点の「参照全チェック」のコストが効いているのではないか、という推測もなされているが、詳しい原因はまだよくわかっていない。

コンパクション

rubyのGCでコンパクションはできるだろうか。rubyのVALUEは構造体への直ポインタであるから、コンパクションして構造体のアドレスが変わったら、移動した構造体を指しているVALUEを全て書き換えないといけない。

ところがrubyのGCはconservative GCなので「それが本当にVALUEかどうかわからない場合」がありうる。それなのにその値を書き換えてしまったら、もし VALUEでなかったときにはとんでもないことになる。コンパクションと conservative GCはとても相性が悪いのだ。

だがなんとかして対策を考えてみよう。まずVALUEをポインタでなくオブジェクトIDにする方法が考えられる（図12）。VALUEと構造体の間に一枚間接層を挟む方法だ。これならVALUEを書き換えずに済むので安心して構造体を移動できる。だがその代償としてアクセス速度は遅くなるし、拡張ライブラリの互換性もなくなる。

(objid)
図12: オブジェクトID経由での参照

そこで次の方法として、「確実にVALUEである」ポインタ「だけ」から指されている構造体に限定して移動するという手法がある（図13）。この手法をMostly-copying garbage collectionと言う。普通のプログラムならis_pointer_to_heap()が真になるオブジェクトはそうたくさんはないから、かなりの確率でオブジェクト構造体を移動できることになる。

(mostcopy)
図13: Mostly-copying garbage collection

さらにさらに、もし構造体が移動できるということになれば、同時に世代別GCの実装も簡単になる。挑戦してみる価値はありそうだ。

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);

という感じの代替案が現在議論されている。

御意見・御感想・誤殖の指摘などは青木峰郎 <[email protected]> までお願いします。

『Rubyソースコード完全解説』はインプレスダイレクトで御予約・御購入いただけます (書籍紹介ページへ飛びます)。

第5章 ガ－ベージコレクション