ガベージコレクション

Ruby には使われなくなったメモリを自動的に検出し解放してくれる ガベージコレクションの機能がある。 この節ではこのガベージコレクションの詳細を追ってゆく。

オブジェクトの管理

Ruby の GC は Ruby のオブジェクトのみが対象だ。かつ、Ruby が 生成し管理しているメモリにないといけない。逆に言うとユーザが勝手に 割りあてたメモリまでは面倒をみてくれないということだ。たとえば 以下の関数はメモリリークを起こす。

void koreha_dame()
{
    malloc(1024);  /* メモリをもらっては捨てる */
}

一方で以下の関数はメモリリークを起こさない。

void daijoubu()
{
    rb_ary_new();  /* Ruby の配列を作っては捨てる */
}

Ruby のオブジェクトはようするに struct RVALUE だったから、オブ ジェクトの管理はすなわちこの構造体の管理だ。もちろん Fixnum nil true false は例外だが、しつこくなるのでそれはいちいち書かない。

struct RVALUE

その構造体のサイズはクラスごとにまちまちだったが、おそらく管理 が大変になるのを避けるためだろう、組み込みクラスの構造体の共用 体を宣言して、メモリをさわるときはすべからくその共用体を介して 扱うようになっている。その共用体の宣言がこれだ。

typedef struct RVALUE {
    union {
        struct {
            unsigned long flag;	/* 使われていないときはゼロ */
            struct RVALUE *next;
        } free;
        struct RBasic  basic;
        struct RObject object;
        struct RClass  klass;
        struct RFloat  flonum;
        struct RString string;
        struct RArray  array;
        struct RRegexp regexp;
        struct RHash   hash;
        struct RData   data;
        struct RStruct rstruct;
        struct RBignum bignum;
        struct RFile   file;
        struct RNode   node;
        struct RMatch  match;
        struct RVarmap varmap; 
        struct SCOPE   scope;
    } as;
} RVALUE;

(gc.c translate)

struct RVALUE は要素が一つだけの構造体だ。わざわざこんなことを してあるのはたぶんソースコードを書くときに

obj->as.basic.klass

のように読みやすくするのが目的だと思われる。メモリ容量も変わら ないし、アクセスコードもコンパイラが消してくれるだろうから問題 にはならない。

まずは共用体の最初の要素 free に注目しよう。コメントには 「使われていないときはゼロ」と書いてあるが本当だろうか。まだ使っ ているオブジェクトの flags が偶然 0 になることはないのだろうか。 前に見たように全てのオブジェクト構造体は struct RBasic を最初 の要素に持つ。だから共用体のどの要素からアクセスしても obj->as.free.flagobj->as.basic.flags と書くのと同じことだ。 そしてオブジェクトは必ずフラグにクラス情報を持ち、しかもそのフ ラグはすべて 0 以外なので「生きている」オブジェクトのフラグが 偶然 0 になることはない(ruby.h)。つまりフラグを 0 にすること で「死に」オブジェクトを表すのは必要十分だと確かめられる。

オブジェクトの配置

すべてのオブジェクト構造体のためのメモリは struct RVALUE **heaps にまとめられている。heaps は概念的には struct RVALUE の配列の 配列だ。一次配列の長さは動的に決定し、二次配列の長さは固定長 HEAP_SLOTS(=10000)。また、ヒープスロット(struct RVALUE の配列) の数は、HEAP_INCREMENT(=10) づつ増やされ、使っているスロットの 数が heaps_used、上限が heaps_length に記憶される。

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

heaps[0]           = { 0=RVALUE, 1=RVALUE, ... 9999=RVALUE }
     [1]           = { 0=RVALUE, 1=RVALUE, ... 9999=RVALUE }
     [2]           = { 0=RVALUE, 1=RVALUE, ... 9999=RVALUE }
      :                            :
     [heap_used-1] = { 0=RVALUE, 1=RVALUE, ... 9999=RVALUE }
     [heap_used]
      :
     [heaps_length-1]

この構造には必然性がある。例えばすべての構造体を一つの配列に配 置するとメモリ空間は最もコンパクトになるが、realloc を発生させ るわけにはいかない(オブジェクトが移動してしまうから)ので、最初 から必要な容量だけ割りあてておく必要がでてきて非常に不便だ。一 方 RVALUE へのポインタの配列にすると、一見うまくいきそうだが、 これだと GC のときに困ってしまう。というのも、これから詳しく書 くとおり、Ruby の GC では「VALUERVALUE へのポインタ)らしい」 整数を知る必要があるからだ。すべての RVALUE がてんでバラバラの アドレスに配置されていると、全てのオブジェクトと「ポインタかも しれない」整数すべてをそれぞれ比較しなければいけない。これでは とても容認できるスピードにはならないだろう。ということで結局あ る程度アドレスにまとまりがあり、かつ、ある程度ばらけているよう に配置するのがよいことがわかる。それに一番適合するのが「配列へ のポインタの配列」ということだ。

またさらに、空いている RVALUEfreelist から始まるリンクリス トにつながれて管理される。rvalue->as.free.next はそのために使 うリンクだ。

あとは簡単だ。オブジェクトを生成するには freelist に登録されて いるメモリがあればそれを使い、なければ GC するか、ヒープを増や せばよい。実際にオブジェクト生成を行う関数 rb_newobj() を載せ ておくので、確かめてみよう。

VALUE
rb_newobj()
{
    VALUE obj;

    if (freelist) {
      retry:
        obj = (VALUE)freelist;
        freelist = freelist->as.free.next;
        alloc_objects++;
        return obj;
    }
    if (dont_gc || during_gc || rb_prohibit_interrupt) add_heap();
    else rb_gc();

    goto retry;
}

マーク

Ruby の GC はマークアンドスイープと呼ばれる方式を使っている。 この方式では、確実にデータがあることがわかっているアドレスから ポインタをたどっていき(マーク)、到達できなかったポインタをも う使われていないものとみなして解放する(スイープ)。

もう少し具体的に言うと、「マークする」とは RBasicflagsFL_MARK フラグをセットすることだ。使われている VALUE を探して は FL_MARK をセットし、これで全部調べたと思ったらオブジェクト ヒープを見て、FL_MARK がセットされていないオブジェクトを解放す ればいい。

では、実際にそのコードを見ていこう。まずはマーク、rb_gc() から。 やや長いので少しづつ出すことにする。

最初は Ruby インタプリタが使っているスタックフレームのマーク。 フレームはローカル変数のテーブルなどを含んでいて、 構造体 struct FRAME で表される。

/* mark frame stack */
for (frame = ruby_frame; frame; frame = frame->prev) {
    rb_gc_mark_frame(frame); 
    if (frame->tmp) {
        struct FRAME *tmp = frame->tmp;
        while (tmp) {
            rb_gc_mark_frame(tmp);
            tmp = tmp->prev;
        }
    }
}
rb_gc_mark(ruby_class);
rb_gc_mark(ruby_scope);
rb_gc_mark(ruby_dyna_vars);

最後のほうにある ruby_class ruby_scope ruby_dyna_varseval.c で宣言されているグローバル変数で、それぞれその時点でのクラスス コープ、ローカルスコープ、ダイナミックローカル変数、を示してい る。これらの情報の最新のものは他のものとは別にされてグローバル 変数に格納されていることがあるので、ここで特別にマークしてやる必 要があるのだ。

次に CPU のレジスタと(C の)スタックのマーク。

FLUSH_REGISTER_WINDOWS;

FLUSH_REGISTER_WINDOWS というのは defines.h で定義されているマ クロで、CPU の中にあるレジスタウィンドウ という領域をメモリに掃き出させる。今のところは sparc アーキテ クチャのみで必要なようだ。

/* ここで全てのレジスタが jmp_buf に保存されなければいけない */
setjmp(save_regs_gc_mark);

この setjmpsave_regs_gc_mark (jmp_buf) にレジスタを書きだ す。だが djgpp・68k ではレジスタが書きこまれないようで、 setjmp を以下のような関数に再定義して明示的にレジスタを書きだ ている。アセンブラだ。(コメントは筆者。筆者はアセンブラ知らな いので注意)

#ifdef __GNUC__
#if defined(__human68k__) || defined(DJGPP)
#if defined(__human68k__)
typedef unsigned long rb_jmp_buf[8];
__asm__ (".even                  ; 偶数アドレス アライメント ?
_rb_setjmp:                      ; 関数 rb_setjmp
        move.l  4(sp),a0         ; 引数を a0 に
        movem.l d3-d7/a3-a5,(a0) ; ポインタ a0 の先に d3〜d7 a3〜a5 をストリング転送
        moveq.l #0,d0            ; d0 に 0 を代入?(返り値)
        rts");
#else
#if defined(DJGPP)
typedef unsigned long rb_jmp_buf[6];
__asm__ (".align 4             ; 4 バイトアライメント
_rb_setjmp:                    ; 関数 rb_setjmp
        pushl   %ebp           ; ベースポインタをスタックにプッシュ
        movl    %esp,%ebp      ; スタックポインタを ebp に移動
        movl    8(%ebp),%ebp   ; スタックから第一引数を拾い ebp に代入
        movl    %eax,(%ebp)    ; ポインタ ebp の指す配列にレジスタの中身を入れていく
        movl    %ebx,4(%ebp)
        movl    %ecx,8(%ebp)
        movl    %edx,12(%ebp)
        movl    %esi,16(%ebp)
        movl    %edi,20(%ebp)  
        popl    %ebp           ; スタックからベースポインタを復帰
        xorl    %eax,%eax      ; eaxを0にする(返り値)
        ret");
#endif
#endif
int rb_setjmp (rb_jmp_buf);
#define jmp_buf rb_jmp_buf
#define setjmp rb_setjmp
#endif /* __human68k__ or DJGPP */
#endif /* __GNUC__ */

アライメント(alignment)というのはメモリに変数を置くときの置 き方のことだ。たとえば 32 ビットマシンでは int は当然 32 ビッ トを使うが、普通はどこからでも 32 ビットとれるわけではなく、 「4 の倍数バイトから」とか「偶数バイトから」というふうに決めら れている。なぜかというとそのほうがメモリアクセスを高速化できる からだ。

それから、C で書かれた関数はコンパイラが自動的に先頭に _ を付 ける規約があるので、アセンブラで C の関数を書くときは自分で先 頭に _ を付ける。

これでレジスタを書きだせたので、次のコードでマークする。

mark_locations_array((VALUE*)save_regs_gc_mark,
                     sizeof(save_regs_gc_mark) / sizeof(VALUE *));

mark_locations_array() というのは始めて出てきた関数だ。この関 数は配列をまとめてマークするための関数なのだが、これまでのマー ク関数とは少し違う。これまでは、ここには確実に VALUE がある (オブジェクトを指すポインタだ)とわかっている場所をマークして きた。しかし今度マークしようとしているのはレジスタで、ここには VALUE があることも当然あるだろうが、そうでないものがあることも 十分考えられる。そこで、まずその数値がポインタである可能性があ るか調べてみて、それらしく見えるならばすべてポインタとして扱う。 どういうものがポインタらしく見えるかという判定は looks_pointerp() で行う。

static int
looks_pointerp(ptr)
    void *ptr;
{
    register RVALUE *p = RANY(ptr);
    register RVALUE *heap_org;
    register long i;

    if (p < lomem || p > himem) return Qfalse;

    /* p がポインタかどうか調べる */
    for (i = 0; i < heaps_used; i++) {
        heap_org = heaps[i];
        if (heap_org <= p && p < heap_org + HEAP_SLOTS
            && ((((char*)p)-((char*)heap_org))%sizeof(RVALUE)) == 0)
            return Qtrue;
    }
    return Qfalse;
}

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

  1. VALUE があるアドレスの最下端と最上端の間にあるか調べる(最初のif
  2. 各ヒープの範囲内にあるかどうか調べる(for 文内の if の一行目)
  3. その数値が RVALUE の先頭を指しているかどうか確かめる(内部の if の二行目)

このようなしくみであるから、間違って VALUE でない値を VALUE と 扱ってしまうことも当然ある。しかし少なくとも使っている VALUE をみつけられないことはないので、影響があるのは GC の速度と多少 のメモリの無駄だけだ。それもこれだけのテストをしていれば意図的 でない限りそうそうポインタ以外の値を拾うことはないと思われるの で、この GC で得られる利点を考えれば十分に妥協できる。というわけだ。

ではまた rb_gc_mark() の続きに戻ろう。

#ifdef C_ALLOCA
    rb_gc_mark_locations(rb_gc_stack_start, (VALUE*)&stack_end);
#else
    rb_gc_mark_locations(rb_gc_stack_start, (VALUE*)alloca(1));
#endif

このコードでスタックをマークする。スタックもどこに VALUE があ るかはわからないので、レジスタと同じく gc_mark_locations() で マークする。ネイティブな alloca のあるところでは(C_ALLOCA が 偽)、alloca がスタックの先頭に値を割りあてることを利用してス タックの先頭を得る。alloca がない環境では、最も近い関数で定義 したローカル変数(stack_end)がスタックの先頭にあると判断して そのアドレスを使う。さらに、スタックが 32 ビットアライメントさ れていないアーキテクチャでは、以下のように開始アドレスをずらし て再度マークする。

#if defined(THINK_C) || defined(__human68k__)
#ifndef __human68k__  /* 実際には think C でコンパイルはできない */
    mark_locations_array((VALUE*)((char*)save_regs_gc_mark+2),
                         sizeof(save_regs_gc_mark) / sizeof(VALUE *));
#endif
    rb_gc_mark_locations((VALUE*)((char*)rb_gc_stack_start + 2),
                         (VALUE*)((char*)&stack_end + 2));
#endif

まだ終わらない。Ruby ではスタックを自前で保存・書き戻しするこ とでスレッドを実現しているので、スタックがスレッドの数だけ保存 されている。rb_gc_mark_threads() でこの領域もマークする (スレッドの詳細はスレッドの項を参照)。

最後にインタプリタ組みこみの VALUE コンテナをマークする。 C のグローバル変数は rb_global_variable() でユーザが登録することになっていて、 そのアドレスは Global_List にリンクリストとして保存されている。

/* グローバル変数をマークする */
for (list = Global_List; list; list = list->next) {
    rb_gc_mark(*list->varptr);
}
rb_gc_mark_global_tbl();    /* Ruby のグローバル変数テーブルをマーク */

rb_mark_tbl(rb_class_tbl);  /* クラステーブルをマーク */
rb_gc_mark_trap_list();     /* signal() で登録した Proc をマーク */

/* 汎用 インスタンス変数テーブル をマーク */
rb_mark_generic_ivar_tbl();

これでマークのフェーズが終わった。

スイープ

スイープフェーズはマークされていないオブジェクトを探して解放し ていく作業です。しかし、この局面に入ってもマークされていないオ ブジェクトは全て解放していいとは限らない。現在特別扱いされてい るのは T_NODE 型のオブジェクトと、ファイナライザが登録されてい るオブジェクトだ。以下は gc_sweep() の冒頭である。

static void
gc_sweep()
{
    RVALUE *p, *pend, *final_list;
    int freed = 0;
    int i, used = heaps_used;

    if (ruby_in_compile) {
        /* コンパイル中は NODE を回収すべきでない */
        for (i = 0; i < used; i++) {
            p = heaps[i]; pend = p + HEAP_SLOTS;
            while (p < pend) {
                if (!(p->as.basic.flags&FL_MARK) && BUILTIN_TYPE(p) == T_NODE)
                    rb_gc_mark(p);
                p++;
            }
        }
    }

T_NODE 型のオブジェクトは Ruby の構文木をつくるために使われる。 この NODE はコンパイル中には yacc のセマンティックスタック に置かれるのだがそのスタックは C のスタックにあるとは限らない。 この生成途中の枝が回収されてしまうとまずいので、コンパイル中は T_NODE 型のオブジェクトは無条件にマークして避けなければならない。 ちなみに BUILTIN_TYPE() というのは前書いた TYPE() と同じく構造体 の型を返すマクロだが、VALUE がポインタとわかっている時にだけ 使えるところが違う。

では続きの部分。

    freelist = 0;
    final_list = 0;
    for (i = 0; i > used; i++) {
        int n = 0;

        p = heaps[i]; pend = p + HEAP_SLOTS;
        while (p > pend) {
            if (!(p->as.basic.flags & FL_MARK)) {
                if (p->as.basic.flags) {
                    obj_free((VALUE)p);
                }
                if (need_call_final && FL_TEST(p, FL_FINALIZE)) {
                    p->as.free.flag = FL_MARK; /* マークされたまま残る */
                    p->as.free.next = final_list;
                    final_list = p;
                }
                else {
                    p->as.free.flag = 0;
                    p->as.free.next = freelist;
                    freelist = p;
                }
                n++;
            }
            else if (RBASIC(p)->flags == FL_MARK) {
                /* ファイナライズが必要なオブジェクト */
                /* なにもしないでマークされたままにしておく */
            }
            else {
                RBASIC(p)->flags &= ~FL_MARK;
            }
            p++;
        }
        freed += n;
    }

    if (freed < FREE_MIN) {
        add_heap();
    }
    during_gc = 0;

heap を順々に見ていき、FL_MARK フラグが立っていなかったら obj_free() を呼んで解放する。ただし FL_FINALIZE フラグが立って いたらそれをfinal_list に、立っていなかったらすぐに free_list に追加する。そのすぐ下の flags == FL_MARK というのは、前回の GC でファイナライズが必要になったオブジェクトを検出していると 思われる。これでスイープも終わった。

このあとでファイナライザを実行すれば GC 全体が終わる。

    /* ファイナライザ リストを一掃する */
    if (need_call_final) {
        RVALUE *tmp;

        for (p = final_list; p; p = tmp) {
            tmp = p->as.free.next;
            run_final((VALUE)p);
            p->as.free.flag = 0;
            p->as.free.next = freelist;
            freelist = p;
        }
    }
}

ところで…

個々のオブジェクトで割りあてた領域(たとえばArrayの配列とか) はスイープフェイズの中で解放されているが、RVALUE 構造体自体を 解放するコードは出てこなかった。また、VALUE スロット自体でも使っ ている数の管理などは特にやっていない。ということは Ruby のオブ ジェクト領域は一度わりあてたら絶対に解放されないということだ。