型記述子ごとの Cheney Copying ゴミ集め

Chibi Scheme のセルは型識別子をタグとするバリアントになっています。 ゴミ集めのマーク・フェーズでセルの子供セルのありかと個数を型識別子に対する型記述子から求めて、 マークを進めていきます。 この型記述子もセルであって、 context バリアントから vector バリアントを 2 段経由して型記述子の type バリアントを求める流儀になっています。 Chibi Scheme はマーク & スイープなので、 セルの再配置がなく、 マーク・フェーズで、 ヒープ中の context バリアントと type バリアントをそのまま参照しても正しく設定された値を読むことが可能です。

これを、 セルの再配置があるコピー・ゴミ集めにアレンジするには、 どうすれば良いのか考えてみます。 ゴミ集めが利用するセルの構成を記述している型記述子を含めて再配置していくわけです。 なお、 ここでは Chibi Scheme よりも踏み込んで、 セルの先頭には型識別子ではなく、 型記述子である type バリアントへの参照を直接配置することにします。 さらに、 セルのメンバはシンボルを除いてすべてタグ付きポインタ型とし、 fixnum とポインタを最下位ビットで区別することにします。 簡単化のため、 バリアントは pair、 symbol、 vector、 type、 context の 5 通りとします。 さらに、 それらにゴミ集め中の再配置後アドレスを表す forwarding バリアントを加えます。 context バリアントは、 それが含まれているヒープのアドレスと型記述子を保持します。 型記述子 type バリアントは vector バリアントに並べます。 type バリアントの type メンバは SEXP_TYPE の型記述子への参照とします。 なお、 SEXP_TYPE の型記述子の type メンバは自分自身への参照とします。

#include <stdlib.h>
#include <stddef.h>
#include <stdint.h>
#include <stdbool.h>
#include <stdio.h>

enum {
    SEXP_TYPE,
    SEXP_BOOLEAN,
    SEXP_NIL,
    SEXP_FIXNUM,
    SEXP_PAIR,
    SEXP_SYMBOL,
    SEXP_VECTOR,
    SEXP_CONTEXT,
    SEXP_CORE_SIZE,
};

/*  end bits    00 : pointer
 *               1 : fixnum
 *              10 : immediate + BROKEN_HEART
 */
#define sexp_is_pointer(x) ((((uintptr_t)(x))&3U)==0)
#define sexp_is_fixnum(x) ((((uintptr_t)(x))&1U)==1U)

typedef struct sexp_s *sexp_t;
typedef sexp_t sexp_fixnum_t;
typedef sexp_t sexp_vector_t;

struct sexp_s {
    sexp_t type;
    union {
        struct {
            sexp_t head;
            sexp_t tail;
        } pair;
        struct {
            sexp_fixnum_t size;
            char data[];
        } symbol;
        struct {
            sexp_fixnum_t size;
            sexp_t data[];
        } vector;
        struct {
            sexp_t name;
            sexp_fixnum_t child_field;
            sexp_fixnum_t size_field;
            sexp_fixnum_t size_scale;
            sexp_fixnum_t size_fix;
            sexp_fixnum_t skip_fix;
        } type;
        struct {
            sexp_t space;
            sexp_t cell;
            sexp_t cell_top;
            sexp_t from;
            sexp_t from_top;
            sexp_t hall;
            sexp_vector_t type_table;
        } context;
        struct {
            sexp_t address;
        } forwarding;
    } v;
};

C 言語の整数と fixnum の間の変換はマクロでおこないます。

#define sexp_make_fixnum(x) ((sexp_fixnum_t)(((uintptr_t)((intptr_t)(x)<<1))|1U))
#define sexp_fixnum_data(x) ((intptr_t)(x)>>1)

#define SEXP_ZERO sexp_make_fixnum(0)

次のセルの位置、 セルのバイトサイズ、 セルのメンバのオフセット等を扱うマクロを定義します。 これらのマクロは Chibi Scheme のものを流用しています。

#define sexp_skip(p,x) ((sexp_t)((sexp_t*)(p)+(((x)+sizeof(sexp_t)-1U)/sizeof(sexp_t))))
#define sexp_sizeof(f) (offsetof(struct sexp_s,v)+sizeof(((sexp_t)0)->v.f))
#define sexp_offsetof(f) offsetof(struct sexp_s,v.f)
#define sexp_field_at(s,t,i) ((t)(((char*)(s))+i))

context から型記述子を求めるマクロと、 ヒープの空き領域ポインタを求めるマクロ、 ポインタが from か cell に含まれるかどうかを調べるマクロ、 コピー中の再配置情報を扱うマクロを定義します。 sexp_gcprune マクロは、 from 中に残っているセルのときはそのままそのアドレスを、 cell へコピー済みのときはコピー先のアドレスを求めます。 なお、 context から型記述子へのベクタは 1 段に減らしています。

#define sexp_context_type_size(x) ((x)->v.context.type_table->v.vector.size)
#define sexp_context_type_data(x) ((x)->v.context.type_table->v.vector.data)

#define sexp_context_in(ctx,x,f,t) (sexp_is_pointer(x)&&(ctx)->v.context.f<=(x)&&(x)<(ctx)->v.context.t)

#define SEXP_BROKEN_HEART ((sexp_t)0xfeedcafeU)
#define sexp_gcprune(x) (SEXP_BROKEN_HEART == (x)->type ? (x)->v.forwarding.address : (x))

コピー・ゴミ集めなので、 最初に 2 つのセル空間 cell と from を交換します。 交換後、 from から cell へと生きているオブジェクトを移動していきます。 context の hall メンバは空き領域の開始ポインタであり、 交換直後は cell の先頭にセットします。

#define sexp_swap(a,b,t) do{t=a;a=b;b=t;}while(0)

void
sexp_gcflip(sexp_t ctx)
{
    sexp_t tmp;

    sexp_swap(ctx->v.context.cell, ctx->v.context.from, tmp);
    sexp_swap(ctx->v.context.cell_top, ctx->v.context.from_top, tmp);
    ctx->v.context.hall = ctx->v.context.cell;
}

今回、 根は context だけとして、 まず from 中の context を cell へコピーします。 その後は、 セルの先頭の type に続いて、 子供があるときは、 それらを再帰コピーしていきます。 セルの大きさと、 子供への参照のメンバ位置とメンバの個数は type 記述子から求めます。 ちなみに、 型記述子から求まるセルの大きさはバイト単位です。 sexp_skip マクロがバイト単位の大きさからワード単位へアラインメントをおこないます。

sexp_t
sexp_gc(sexp_t ctx)
{
    sexp_t scan, *child;
    int field, scale, size, cellsize, nchild, i;

    sexp_gcflip(ctx);
    ctx = sexp_gccopy(ctx, ctx);
    scan = ctx->v.context.cell;
    while (scan < ctx->v.context.hall) {
        scan->type = sexp_gccopy(ctx, scan->type);
        cellsize = sexp_fixnum_data(scan->type->v.type.skip_fix);
        nchild = sexp_fixnum_data(scan->type->v.type.size_fix);
        if (SEXP_ZERO != scan->type->v.type.size_field) {
            field = sexp_fixnum_data(scan->type->v.type.size_field);
            scale = sexp_fixnum_data(scan->type->v.type.size_scale);
            size = sexp_fixnum_data(sexp_field_at(scan, sexp_fixnum_t*, field)[0]);
            cellsize += size * scale;
            nchild += size;
        }
        if (SEXP_ZERO != scan->type->v.type.child_field) {
            field = sexp_fixnum_data(scan->type->v.type.child_field);
            child = sexp_field_at(scan, sexp_t*, field);
            for (i = 0; i < nchild; i++)
                child[i] = sexp_gccopy(ctx, child[i]);
        }
        scan = sexp_skip(scan, cellsize);
    }
    return ctx;
}

セルのコピーでは、 コピー済みならコピー先アドレスを返し、 そうでないときは、 from から cell へセルの内容をコピーしてからコピー済みの設定をおこないます。 type オブジェクトも再配置対象なので、 コピー済みかどうか調べて、 from に残存するセルか、 cell へ移動済みのセルを使うのかを sexp_gcprune マクロで解決します。

sexp_t
sexp_gccopy(sexp_t ctx, sexp_t src)
{
    sexp_t dst, type;
    int cellsize, field, size, scale;

    if (! sexp_context_in(ctx, src, from, from_top))
        return src;
    if (SEXP_BROKEN_HEART == src->type)
        return src->v.forwarding.address;
    type = sexp_gcprune(src->type);
    cellsize = sexp_fixnum_data(type->v.type.skip_fix);
    if (SEXP_ZERO != type->v.type.size_field) {
        field = sexp_fixnum_data(type->v.type.size_field);
        size = sexp_fixnum_data(sexp_field_at(src, sexp_fixnum_t*, field)[0]);
        scale = sexp_fixnum_data(type->v.type.size_scale);
        cellsize += size * scale;
    }
    dst = ctx->v.context.hall;
    ctx->v.context.hall = sexp_skip(ctx->v.context.hall, cellsize);
    memcpy(dst, src, cellsize);
    src->type = SEXP_BROKEN_HEART;
    src->v.forwarding.address = dst;
    return dst;
}

ゴミ集めの動作確認のために、 context をセル領域に初期化します。 最初に、 セル領域 2 つ分を malloc で割り当てます。 これの前半と後半をそれぞれ cell 領域と from 領域にします。 割り当てた先頭、 つまり cell 領域の先頭を context オブジェクトの置き場所として、 メンバに領域情報をセットします。 さらに、 型記述子を並べるための vector オブジェクトを配置し、 コア型記述子を作ってセットしていきます。 最後に、 オブジェクトの type のつじつま合わせをして初期化が終わります。

enum { SEXP_TOPCELL = 131072 };

sexp_t
sexp_context_bootstrap(void)
{
    sexp_t ctx;
    size_t const SPACE_SIZE = SEXP_TOPCELL * sizeof(sexp_t);

    ctx = malloc(SPACE_SIZE * 2);
    if (NULL == ctx)
        return NULL;
    ctx->v.context.space = ctx;
    ctx->v.context.cell = ctx->v.context.space;
    ctx->v.context.cell_top = sexp_skip(ctx->v.context.cell, SPACE_SIZE);
    ctx->v.context.from = ctx->v.context.cell_top;
    ctx->v.context.from_top = sexp_skip(ctx->v.context.from, SPACE_SIZE);
    ctx->v.context.hall = sexp_skip(ctx->v.context.cell, sexp_sizeof(context));
    ctx->v.context.type_table = ctx->v.context.hall;
    ctx->v.context.hall = sexp_skip(ctx->v.context.hall, sexp_sizeof(vector) + SEXP_CORE_SIZE * sizeof(sexp_t));
    ctx->v.context.type_table->v.vector.size = sexp_make_fixnum(SEXP_CORE_SIZE);

    sexp_bootstrap_core_type(ctx, SEXP_TYPE, "<type>",
        sexp_offsetof(type.name), 0, 0, 1, sexp_sizeof(type));
    sexp_bootstrap_core_type(ctx, SEXP_SYMBOL, "<symbol>",
        0, sexp_offsetof(symbol.size), 1, 0, sexp_sizeof(symbol) + 1);
    sexp_bootstrap_core_type(ctx, SEXP_BOOLEAN, "<boolean>", 0, 0, 0, 0, 0);
    sexp_bootstrap_core_type(ctx, SEXP_NIL, "<nil>", 0, 0, 0, 0, 0);
    sexp_bootstrap_core_type(ctx, SEXP_FIXNUM, "<fixnum>", 0, 0, 0, 0, 0);
    sexp_bootstrap_core_type(ctx, SEXP_PAIR, "<pair>",
        sexp_offsetof(pair.head), 0, 0, 2, sexp_sizeof(pair));
    sexp_bootstrap_core_type(ctx, SEXP_VECTOR, "<vector>",
        sexp_offsetof(vector.data), sexp_offsetof(vector.size), sizeof(sexp_t), 0, sexp_sizeof(vector));
    sexp_bootstrap_core_type(ctx, SEXP_CONTEXT, "<context>",
        sexp_offsetof(context.type_table), 0, 0, 1, sexp_sizeof(context));

    ctx->type = sexp_context_type_data(ctx)[SEXP_CONTEXT];
    ctx->v.context.type_table->type = sexp_context_type_data(ctx)[SEXP_VECTOR];
    sexp_context_type_data(ctx)[SEXP_TYPE]->v.type.name->type = sexp_context_type_data(ctx)[SEXP_SYMBOL];
    return ctx;
}

コア型記述子は、 type オブジェクトと symbol オブジェクトで作ります。 symbol オブジェクトは型名のシンボルで、 ここでは簡単化のためシンボル表を作らずインターンしていません。 型記述子の child_field は sexp_s 構造体の先頭からの子供スロットのオフセットです。 セルを消費しない fixnum 等ではゼロにします。 size_field は可変長セルの大きさを格納するスロットのオフセットです。 可変長でないセルではゼロにします。 size_scale は size_field のスロットから取り出した fixnum の値に乗じる因子で、 乗じた結果がバイト単位になるようにします。 size_fix は固定長セルの子供スロットの個数です。 skip_fix はセルの可変でない部分が占めるのバイト数です。

例えば、 ペアは、 head と tail の 2 個の子供スロットを持つ固定長セルなので、 size_field と size_scale をゼロにし、 size_fix を 2 にします。 ベクタは vector.size に子供スロットの個数を格納するので、 size_field に vector.size のオフセットを、 size_scale にセルのワードの大きさをバイト単位で指定し、 size_fix をゼロにします。 シンボルは子供スロットがないので、 child_field をゼロにし、 size_field に symbol.size のオフセットを、 size_scale に 1 (イチ)を指定します。

static void
sexp_bootstrap_core_type(sexp_t const ctx, int const typeid, char const *name,
                        int const child_field,
                        int const size_field, int const size_scale,
                        int const size_fix, int const skip_fix)
{
    sexp_t spec, sym;
    int len;

    spec = ctx->v.context.hall;
    ctx->v.context.hall = sexp_skip(ctx->v.context.hall, sexp_sizeof(type));
    sexp_context_type_data(ctx)[typeid] = spec;
    spec->type = sexp_context_type_data(ctx)[SEXP_TYPE];

    len = strlen(name);
    sym = ctx->v.context.hall;
    ctx->v.context.hall = sexp_skip(ctx->v.context.hall, sexp_sizeof(symbol) + len + 1);
    sym->type = sexp_context_type_data(ctx)[SEXP_SYMBOL];

    spec->v.type.name = sym;
    spec->v.type.child_field = sexp_make_fixnum(child_field);
    spec->v.type.size_field = sexp_make_fixnum(size_field);
    spec->v.type.size_scale = sexp_make_fixnum(size_scale);
    spec->v.type.size_fix = sexp_make_fixnum(size_fix);
    spec->v.type.skip_fix = sexp_make_fixnum(skip_fix);

    sym->v.symbol.size = sexp_make_fixnum(len);
    memmove(sym->v.symbol.data, name, len + 1);
}

main 関数を埋めて、 コンパイルし、 デバッガで cell 空間の内容を追跡すると、 context オブジェクトと type オブジェクト等もすべてを丸ごとコピー・ゴミ集めしていくのを確かめることができます。

int
main(int argc, char *argv[])
{
    sexp_t ctx;

    ctx = sexp_context_bootstrap ();
    if (NULL == ctx) {
        perror("malloc");
        exit(EXIT_FAILURE);
    }
    ctx = sexp_gc(ctx);
    free(ctx->v.context.space);
    return EXIT_SUCCESS;    
}