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

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

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

セグメント

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

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

テキスト領域はコードが置いてあるところ。二番目は見ての通り。マシンスタッ クには関数の引数やローカル変数が積まれる。ヒープは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()の動き

rubymissing/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(掃除する)だ。

長所は二点である。

短所もやはり二点。

エディタの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: リファレンスカウント

この方式も長所が二点。

そして短所も二点だ。

二点目について解説しておこう。サイクル(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.flagsobj->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)

heapsstruct RVALUEの配列の配列だ。heapSだから、入っている配列 一本一本がheapだろう。heapの要素一つ一つはslotである (図9)。

(heapitems)
図9: heapsheapslot

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

(heaps)
図10: メモリ上に展開されたheapsの概念図

この構造には必然性がある。例えば全ての構造体を一つの配列に配置すると メモリ空間は最もコンパクトになるが、アドレスが変わってしまう恐れがある のでrealloc()できない。VALUEは単なるポインタだからだ。

とあるJavaの実装だとVALUEに相当するものがアドレスではなくてオブジェク トのインデックスで、ポインタテーブルを経由して取り扱われるようになって いるため、オブジェクトを移動することができる。ただしその場合は オブジェクトアクセスのたびに配列のインデクシングが入るので多少 パフォーマンスは落ちる。

一方RVALUEへのポインタ(つまりVALUE)の一次元配列にした場合はどうだろ うか。これは一見うまくいきそうだが、GCのときに困ってしまう。というのも、 これから詳しく書くとおり、rubyのGCでは「VALUERVALUEへのポインタ)ら しい」整数を知る必要があるからだ。全てのRVALUEがてんでバラバラのアドレ スに配置されていると、全てのRVALUEのアドレスと「ポインタかもしれない」 整数全てをそれぞれ比較しなければいけない。これではGCの速度は O(n^2) 以 上のオーダーになり、容認できない。

以上の条件から、オブジェクトヒープはある程度アドレスにまとまりがあり、 しかも位置と総量は制限されないような構造にするのがよいというわけだ。

freelist

使われていないRVALUEfreelistから始まるリンク リストに一本につながれて管理される。RVALUEas.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++;
    }
}

以下の点を確認しておいてほしい。

またlomemhimemを変更しているのもこの関数だけなので、この関数だけから 仕組みが理解できる。この変数にはオブジェクトヒープの最下位アドレスと 最上位アドレスが入っているのである。この値はあとで「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()を再帰呼び出ししているな、ということだけ確認してもらえば それでよい。省略した部分にはNODET_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)

簡単に説明すると次のようになる。

  1. RVALUEがあるアドレスの最下端と最上端の間にあるか調べる
  2. 各ヒープの範囲内にあるかどうか調べる
  3. その数値が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_startSTACK_ENDrb_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.flagsFL_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)

仕組みはたいしたことはないが、第二部・第三部で何度か出会うことになるので 紹介しておいた。

考察

領域の解放

個々のオブジェクトで割りあてた領域、例えばStringchar[]など、はスイー プフェイズの中で解放されていたが、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でコンパクションはできるだろうか。rubyVALUEは 構造体への直ポ インタであるから、コンパクションして構造体のアドレスが変わったら、 移動した構造体を指している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()の場合はメモリ割り当てに失敗したときだ。 そこでGCすればメモリが解放されてまた使えるスペースができるかもしれない。 rb_newobj()も状況は似ていて、freelistが空になったときに起動する。

インタプリタ内

gc.c以外でもインタプリタ内でrb_gc()を呼んでいるところが何か所かある。

まずio.cdir.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が論理的な初期 化と言ってもいい。このような仕組み……つまりオブジェクト生成を allocateinitializeに分割し、newが統轄するという仕組みを、 「アロケーションフレームワーク」と呼んでいる。

ユーザ定義オブジェクトの生成

次は拡張ライブラリで定義したクラスのインスタンス生成について見ていく。 ユーザ定義と言うからにはその構造体は決まっていないわけで、その割り当て かたを教えてあげないとrubyにはどうやって作っていいのかわからない。それ を教える方法を見よう。

Data_Wrap_Struct()

ユーザ定義だろうとなんだろうと生成の仕組み自体はアロケーションフレーム ワークに従えばいい。つまり新しいクラスSomeClassをCで定義するときは SomeClass.allocateSomeClass#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_classvalの所属するクラスで、ptrがラップしようとしているポ インタだ。mark_fがこの構造体をマークするための関数(へのポインタ)。 と言ってもptr自体をマークするわけではもちろんなくて、ptrの指す構造 体の中にVALUEがあるときに使うものだ。一方のfree_fptr自体を解放 するために使う関数である。どちらの関数も引数は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.allocateClass#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.