chapter05.textile

layout	title
default	Garbage Collection

Translated by Sebastian Krause

Chapter 5: Garbage Collection

A conception of an executing program

It’s all of a sudden but at the beginning of this chapter, we’ll
learn about the memory space of an executing program. In this chapter
we deal with the lower level parts of a computer quite a bit, so without
preliminary knowledge it’ll be hard to follow. And it’ll be also necessary
for the following chapters. If we finish this, the rest will be a piece of cake.

Memory Segments

The memory space of a general C program has the following parts:

1. the text area
2. a place for static and global variables
3. the machine stack
4. the heap

The text area is where the code lies. Obviously the second area holds static and global variables.
Function calls, along with their arguments and local variables are piled up in the machine stack.
The heap is allocated by `malloc()`.

Let’s talk a bit about number three, the machine stack.
Obviously, because it’s the machine-“stack” it has the structure of a stack.
In other words new stuff is piled on top of it.
The new in a word fast one is piled up. There is a large a little more unit when logically seeing when the value is actually piled up in the machine stack because it piles up by a detailed unit of `int` 1 piece etc. It is called stack frame (stack frame).

One stack frame corresponds to one function call. Or in other words when there is a function call, one stack frame is added.
With the return the stack frame descends by one. Really simplified the stack frame looks as shown below.

上（先端）above (top)
下（末端）below (bottom)
スタックフレーム stack frame
現在実行中の関数フレーム presently executing function frame

In this picture the top of the stack is depicted above,
but this it is not necessarily always the case that it goes
from low addresses to high addresses. For instance on the x86
machine the stack goes from high to low addresses.

`alloca()`

By using `malloc()` it’s possible to get an abitrarily large memory
area of the heap. `alloca()` is the machine stack version of it.
But unlike `malloc()` it’s not necessary to free the memory allocated
with `alloca()`. Or one should say:
it is freed automatically with the return of the function.
That’s why it’s not possible to have an allocated value as the return
value (?). It’s the same as “You must not return the pointer to
a local variable.”

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

However there exist environments where there is no native `alloca()`.
In this case there are still many who would like to use alloca(),
they write versions of this function in C.

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

How can one implement alloca() in C? The simplest implementation is:
first allocate memory normally with malloc(). Then remember the function
which called alloca() and the assigned addresses in a global list.
After that whenever alloca() is called check this list if the calling
function has already finished. If so set the allocated memory free with
free().

D→alloca(8)の対応を記録 record the relation D→ alloca(8)
B→alloca(32)の対応を記録 record the relation B→ alloca(32)
Dで割り当てたメモりを解放 release the memory allocated in D

The missing/alloca.c in ruby is an example of an emulated alloca().

Overview

From here on we can talk at last about the main subject of this chapter:
garbage collection.

What is GC?

Objects are normally on top of the memory. Naturally, if a lot of objects are created, a lot of memory is used. If memory
were infinite there would be no problem but at present there is always a limit to memory. That’s why the memory which is not
used anymore must be collected and recycled. More concretely the memory received through malloc() must be returned with
free().

However, it is difficult to leave the management of malloc() and free() to the
program. Especially in object oriented programming if objects reference each other,
it is difficult to tell when to release memory.

そこでガーベージコレクションだ。
There garbage collection comes in.
With garbage collection the memory which has become unnecessary,
is gathered and automatically freed. With garbage collection
the worry, when to release some memory with @free(), has become
unnecessary. Depending on this the writing of a program becomes
considerably easier.

Besides, in some book there was written: Garbage collection cleans up
usable memory which has become fragmented. This is an action called
compaction. It makes the memory more compact.
ところで、以前何かの本に「使えるメモリがこまぎれになっているのを整理す
るのが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`である。

What does GC do?

Before we explain the GC algorithm, we should explain what garbage collection
is. In other words how can we tell that memory has become unnecessary?

To keep it more concrete let’s simplify the structure and assume that there
are only objects and links. This would look as shown in figure 3.

Object referred in global variables or objects on top of the language stack
are surely necessary. And objects referred to in instance variables of these
objects are also necessary. Again following links we reach more necessary
objects.

To put it more systematically, the necessary objects are all objects which
can be reached recursively via links starting at the surely necessary objects.
This is depicted in figure 4. Left of the line are all obviously necessary objects.
The objects which can be reached from them are colored black. These are the
necessary objects. The rest of the objects can be released.

ルートオブジェクト　root object
不要なオブジェクト unused object
ルートオブジェクトから参照されているオブジェクト an object referenced by the root object

To put it into jargon , the surely necessary objects
are the garbage collection root. It becomes the root
of the tree of object links.

Mark and Sweep

GC was first implemented in Lisp. The GC in Lisp, the world’s first
GC was of the type mark&sweep. Ruby’s GC is of the same type.

Garbage collection with Mark&sweep is pretty close to our definition of
“necessary object”. First a mark is put on the root objects. From this starting
point all elements which are reached will also be marked. This is the mark phase.

At some point no new elements can be reached. The yielded elements are all checked
and the objects which do not have a marked are all released. This is the sweep.

There are two advantages.

• There does not need to be any (or almost any) concern for garbage collection
  outside the implementation of GC.
• Cycles can also be released. (Look up cycles in the section “Reference Count” below)

There are also two disadvantages.

• In order to make the sweep every object must be touched at least once.
• The load of the GC is concentrated at one point.

If you use the emacs editor there appears sometimes a Garbage collecting...
and it completely stops reacting. That is an example of the second disadvantage.
But this point can be alleviated by modifying the algorithm (incremental GC).

Stop and Copy

Stop and Copy is a variation of Mark and Sweep. First we prepare the object area in several
ways. We simplify by assuming there are two areas A and B. We mark both as active.
Always when creating an object we mark it as active.

The garbage collection starts as with mark&sweep at the root elemnts.
But instead of marking elements it moves them to another region (Fig.6).
When all the links have been followed the elements which remain in A
are all discarded. Next we make B active.

Stop and Copy has two advantages:

• Compaction happens at the same time as collecting the memory
• Objects that reference each other move closer together, improving memory cache hits

The second point is both good and bad:

• The area needed for storing objects needs to be twice as big
• The position of the object changes

There does not seem to be an allaround positive thing.

Reference counting

Reference count differs a bit from the aforementioned, the check(??)
code is distributed in several places.

First each elements get an integer counter. When it is referenced via
variables or arrays the counter of the referenced object is increased.
When the reference ends the counter is decreased. When the counter
becomes zero the object is released. This is the reference counter method.
(Fig.7)

There are two advantages:

• The load of GC is distributed to the entire program.
• The object that became unnecessary is immediately freed.

And there are two disadvantages.

• Handling the counters tends to be forgotten.
• When doing it naively cycles are not released.

Let’s explain about the second point. A cycle is
a cycle of references as shown in figure 8.
If this is the case the counters will never vanish
and the objects will not be released.

By the way, latest Python(2.2) uses reference count GC and cycles can be freed.
However, it is not because of the reference count, but because it occasionally uses mark and sweep to check for them.

Object Management

Ruby’s garbage collection is only concerned with ruby objects.
Objects must be created and managed by ruby. In other words
if the user allocates memory by himself ruby want take care of it.
For instance the following function will create a memory leak in ruby.

void not_ok()
{
    malloc(1024);  /* receive memory and discard it */
}

However, the following function does not cause the memory leak.

void this_is_ok()
{
    rb_ary_new();  /* create a ruby array and discard it */
}

rb_ary_new() uses Ruby’s proper interface to allocate memory.
Ruby’s garbage collection will take care of it.

`struct RVALUE`

As objects are really structures, object management is really
management of these structures. Of course there are also the non-pointer
objects like Fixnum Symbol nil true false which are not of this form.
We will not deal with this distinction here.

The size of the structure varies for the different types, how can we
keep management simple? We declare a union type of all the structures of
embedded classes. When we deal with memory we will deal with this union type.
The declaration of this union type is as follows.

▼ `RVALUE`

 211  typedef struct RVALUE {

 212      union {

 213          struct {

 214              unsigned long flags;   /* 0 if not used */

 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)

The element of struct RVALUE is only one struct.
`struct RVALUE`は要素が一つだけの構造体だ。`union`を直接使わないのはデバッ
グや将来の拡張のときに簡単にメンバを増やせるようにするためだそうである。

まずは共用体の最初の要素`free.flags`に注目しよう。コメントには「使われて
いないときはゼロ」と書いてあるが本当だろうか。まだ使っているオブジェク
トの`free.flags`が偶然0になることはないのだろうか。

第2章『オブジェクト』で見たように、全てのオブジェクト構造体は
`struct RBasic`を最初の要素に持つ。だから共用体のどの要素からアクセスしても
`obj→as.free.flags`は`obj→as.basic.flags`と書くのと同じことだ。そして
オブジェクトは必ずフラグに構造体型フラグ(`T_STRING`など)を持ち、しか
もそのフラグは全て0以外なので、「生きている」オブジェクトのフラグが偶
然0になることはない。つまりフラグを0にすることで「死に」オブジェクトを
表すのは必要十分だと確かめられる。

Object heap

The memory for all the object structures has been brought together in global variable `heaps`. Hereafter, let’s call this an object heap.。

▼ Object heap

 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 is an array of arrays of struct RVALUE. The contained arrays
are each a heap. The elements of heap are each a slot.
(Fig.9)。

The length of heaps can be changed in heap_length. The number of
the slots actually in use is heaps_used. The length of each heap
is in the corresponding heaps_limits[index]. In other words the
structure of the object heap is as depicted in figure 10.

This structure must necessarily be this way.
この構造には必然性がある。例えば全ての構造体を一つの配列に配置すると
メモリ空間は最もコンパクトになるが、アドレスが変わってしまう恐れがある
ので`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      MEMZEROobj, RVALUE, 1);

 307      return obj;

 308  }

(gc.c)

`freelist`が0、つまり余りの構造体がないならGCを起動して領域を作る。
もし一つもオブジェクトを回収できなくても、`rb_gc()`の中で新しい
領域を割り当ててくれるので問題ない。そして`freelist`から構造体を
一つ取り出し、`MEMZERO()`で0を充填、それを返す、となる。

Mark

説明したとおり、`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;

 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)

The definition of RANY() is as follows. It is not particularly important.

▼ `RANY ((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;

 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 Stack

最初はインタプリタが使っている(`ruby`の)スタックフレームを
マークする。第三部まで行けばこれが何者かはわかるので今はあまり
深く考えなくてもいい。

▼ Marking the Ruby Stack

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)

The frame, the class scope, the local variable scope, and the block local variable at that time are maintained respectively by the variable to which `ruby_frame ruby_class ruby_scope ruby_dyna_vars` points at the head of the stack of the evaluation machine respectively.

Register

次にCPUのレジスタをマークする。

▼ marking the registers

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` is special. We will come to it later.

`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_buf8;

1076  asm (“.even\n\                   2バイトアラインメント

1077  rb_setjmp:\n\                       関数rbsetjmp()のラベル

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

1088  asm (“.align 4\n\                4バイトアラインメントを指示

1089  rb_setjmp:\n\                       関数rbsetjmp()のラベル

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;

 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で
得られる利点を考えれば十分に妥協できる。というわけだ。

The Register Window

最後に後回しにしておいた`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  0×83”)

 128  # else /* Solaris, not sparc linux /

 129  #define FLUSH_REGISTER_WINDOWS  asm(“ta  0×03”)

 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.rlimcur0.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()`はパーサのセマンティックスタックをマークする
(セマンティックスタックについては第二部を参照)。

ここまででマークフェイズは終わりだ。

Sweep

`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  ©         else if (RBASIC→flags == FL_MARK) {

 894                  / ファイナライズが必要なオブジェクト。 /

 895                  / 何もしないで放っておく */

 896              }

 897              else {

 898                  RBASIC→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プログラムに実行を移せない場合だ。ここでファイナライズを遅らせた
オブジェクトは先程のリストの経路©に出てくる。

`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→as.free.flags = 0;

 933      RANY→as.free.next = freelist;

 934      freelist = RANY;

 935  }

(gc.c)

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

Closing Thoughts

領域の解放

個々のオブジェクトで割りあてた領域、例えば`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)。

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

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

コンパクション

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

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

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

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

さらにさらに、もし構造体が移動できるということになれば、
同時に世代別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`内部

When will GC start?
There are three places where `rb_gc() ` is called internally of `gc.c`.

• `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できないのを補うためである。

Object Creation

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;

 720          OBJSETUP;

 721          return (VALUE)obj;

 722      }

 723  }

(object.c)

最後の三行以外は気にしなくていい。この`NEWOBJ`はこれまで
も何回か出てきた、Rubyのオブジェクトを作るときのイディオムである。今度
は中身も見てみよう。

▼ `NEWOBJ`

 274  #define NEWOBJ type obj = (type)rb_newobj()

 275  #define OBJSETUP do {\

 276      RBASIC→flags = (t);\

 277      RBASIC→klass = ©;\

 278      if (rb_safe_level() >= 3) FL_SET(obj, FL_TAINT);\

 279  } while (0)

(ruby.h)

`rb_newobj()`は`RVALUE`を一つ`freelist`から外して返してくれる関数だった。
`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;

 318      OBJSETUP;

 319      data→data = datap;

 320      data→dfree = dfree;

 321      data→dmark = dmark;

 322

 323      return (VALUE)data;

 324  }

(gc.c)

なんてことはない。通常のオブジェクトと同じく`NEWOBJ`を使って
`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→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 © 2002-2004 Minero Aoki, All rights reserved.