C言語でインクルードするだけで使えるNon-movingで正確なコピーGCを作った

インクルードするだけで使えるNon-movingで正確なGCをC言語用に作りました。
行数がコメントを除いて100行に満たない非常に小さなライブラリです。
GCのアルゴリズムとしてはCheneyのコピーGCを採用しています。
通常のCheneyのコピーGCではメモリ空間のうち半分が無駄になってしまいメモリ効率が悪かったり、
GC発生時にオブジェクトが移動してしまいC言語のようなポインタを直接触れる言語との相性が悪いという欠点がありました。
今回はヒープ全体を二重連結リストとして管理することでそのような問題を解決しています。
ちなみにこれはTreadmill GCのアイデアと同じです。(が、アルゴリズム自体はTreadmill GCではありません。)
APIはLinuxのlist.hに非常に近い見た目になっています。
ある構造体をgcで管理したい場合はstruct gc_head型のメンバを追加するだけで大丈夫です。
他にはヒープに対するアプリオリな知識を仮定していないという特徴があります。
結果として(実際にそれが必要になることはほとんどないと思いますが)このGCを動作させるだけであればlibcも必要ありません。

使い方

list.h

まず、APIのデザインのベースとしたLinuxのlist.hの使い方について簡単に説明します。Linuxのlist.hは非常に綺麗なAPIを持つC言語のための連結リストライブラリです。例えば構造体fooの連結リストを作成する場合、構造体fooにstruct list_head型のメンバを(どんな位置でもいいので)追加するだけです。

struct foo {
    ...
    struct list_head head;
    ...
};

fooを作成したらheadメンバをINIT_LIST_HEADで初期化してあげます。

struct foo *foo = malloc(sizeof *foo);
INIT_LIST_HEAD(&foo->head);

リスト自体もstruct list_head型で表されます。

struct list_head list_of_foo;
INIT_LIST_HEAD(&list_of_foo);

追加や削除はfooそのものではなくfooのheadメンバに対して行います。

list_add(&foo->head, &list_of_foo);
list_del(&foo->head);

list_headのポインタから、それが属する構造体のポインタを得るにはlist_entryマクロを用います。

struct list_head *h = list_of_foo.next;  // list_of_fooの1個目の要素
struct foo *f = list_entry(h, struct foo, head); // hが属する構造体へのポインタ

ちなみにAPIから明らかですが、struct foo自体はどんな方法でアロケートされていても構いません。例えばスタックに確保した構造体であっても正しくリストのメンバとして扱われます。

struct foo foo;
INIT_LIST_HEAD(&foo.head);
list_add(&foo.head, &list_of_foo);

gc.h

今回作ったgc.h(ファイル名がBoehmGCと被ってますね)はここ[4]に置いてあります。gc.hの使い方はlist.hと概ね同じです。GC対象にしたい構造体があればそれにstruct gc_head型のメンバを追加します。

struct foo {
    ...
    struct gc_head head;
    ...
};

次がポイントですが、struct foo型のオブジェクトをまず自分でアロケートしてから、GCに登録します。

struct foo *foo = malloc(sizeof *foo);
INIT_GC_HEAD(&foo->head, &foo_type);

ただし、このfoo_typeというのは事前に定義しておいた定数で、foo型がどのようにmarkされるか、freeされるかの情報を保持します。

void foo_mark(struct gc_head *head) {
    struct foo *foo = gc_entry(head, struct foo, head);
    ...
    /* mark members of foo using `gc_mark` (if any) */
    ...
}

void foo_free(struct gc_head *head) {
    struct foo *foo = gc_entry(head, struct foo, head);
    ...
    /* free members of foo (if any) */
    ...
    free(foo);
}

const struct gc_object_type foo_type = { foo_mark, foo_free };

ここでfoo_freeの中でfoo自体をfreeしています。このように、ネイティブヒープからのアロケーションはプログラマが自分で行います。gc.hが管理するのは参照の生死だけです。オブジェクトが死んだ場合は事前にINIT_GC_HEADで登録しておいたfree関数が呼ばれるので、その中で適切にネイティブヒープへメモリを返却するのもプログラマの責任です。そのようなデザインのおかげで、gc.hはlibcの関数を使用していません。

通常のGCではヒープの管理までGCが行うので、GCはもともと設定されたタイミングで自動で走ります。しかし、gc.hはネイティブヒープについて一切感知しないというデザインのため、GCが走るタイミングはプログラマが自分で制御する必要があります。mallocでアロケートしたメモリの総量を数えておき、域値を越えればGCを走らせるというのが通常の戦略になると思います。GCはgc_run関数を呼べば走ります。

gc_run();

さて、参照の生死の管理について説明します。gc.hは簡単なスコープ管理の機能を持っています。スコープはgc_scope_openで作成、gc_scope_closeで破棄できます。

{
    gc_scope_t s = gc_scope_open();

    ...

    gc_scope_close(s);
}

まず、INIT_GC_HEADで初期化されたオブジェクトはその時点でのスコープに属する生存オブジェクトになります。スコープが閉じられると、その中で確保されたオブジェクトの参照が切れます。ここで、他からの参照が一切なくなってしまったオブジェクトは次回のgc_runで回収されます。スコープを閉じた後にオブジェクトを使用する場合はgc_protectを呼びます。下のようなコードを実行した場合(make_fooの定義は普通だとして)aは生き残りますがbは次回のGCで回収されます。

{
    gc_scope_t s = gc_scope_open();

    struct foo *a = make_foo();
    struct foo *b = make_foo();

    gc_scope_close(s);
    gc_protect(&a->head);
}

解説

CheneyのコピーGC(以下単にコピーGC)の詳細についてはWikipediaとか[1]を参照してください。原理の解説をしようと思いましたが、実際には基本的にはコピーGCと全く同じです。ただし、non-movingにするためにTreadmill GCの考え方を用いています。Treadmill GCについてはこのWikiとか[2]をみてください。

struct gc_headの中身は以下のようになっています。大きさが4ワードとかなり大きめです。

struct gc_head {
    struct list_head head;
    const struct gc_object_type *type;
    struct gc_head *stack_next;
};

headは全オブジェクト(生きているか、もしくは死んでいるが回収されていない)への二重連結リストにつながっています。typeはこのオブジェクトに対してどのようなmarkとfreeを施すかの情報が入っています。stack_nextはスコープの管理(=root setの管理)に用います。一重連結リストです。

GC全体の状態は一つの変数にまとまっています。

struct gc_state {
    struct list_head spaces[2];
    struct gc_head *stack;
    char from;
};

spacesはfromスペースとtoスペースを表す二重連結リストです。stackは現在のスコープのトップにあるgc_headを指しています。fromはspacesのどちらがfromかを表す1bitの状態です。

spacesのfrom側はgc中でなければ全オブジェクトへの二重連結リストで、gc中はmarkされていないオブジェクトからなる二重連結リストです。spacesのto側はgc中でなければ常に空、gc中はmark済みのオブジェクトからなる二重連結リストです。Treadmill GCと違い、このGCではgc実行中に二つの異なる二重連結リストを使用します。これは通常のコピーGCの挙動に近いです。

スコープの管理は非常に簡単です。まず、gc_protectはオブジェクトをstackにつなぎます。

static inline void gc_protect(struct gc_head *head) {
    head->stack_next = gc.stack;
    gc.stack = head;
}

stackはINIT_GC_HEADをすることでも伸びます。

static inline void INIT_GC_HEAD(struct gc_head *head, const struct gc_object_type *type) {
    head->type = type;
    list_add(&head->head, &gc.spaces[gc.from]);
    gc_protect(head);
}

そして、スコープのopenとcloseは現在のstackを記録、変更するだけです。

typedef struct gc_head *gc_scope_t;

static inline gc_scope_t gc_scope_open(void) {
    return gc.stack;
}

static inline void gc_scope_close(gc_scope_t s) {
    gc.stack = s;
}

stackから繋がる全てのオブジェクトは生存していると見なされます。というか、root setはstackから繋がるオブジェクト全体と同じです。

パフォーマンス

力尽きたので測ってません。

今後の拡張について

少なくともこのリポジトリではこれ以上の拡張を行うことを予定してはいませんが、実際に使用する上では以下のような拡張が必要になるはずです。

グローバルな参照への対応
マルチスレッド対応
インクリメンタルGC化
Mark&Sweep化

まず、現在の実装ではグローバルに保持される参照には対応していません。stackのチェインの下の方にうまくオブジェクトを繋いでおくことで擬似的にグローバル参照のようなものを作ることはできます。が、その場合一番下のスコープに番兵オブジェクトを置く必要があるため面倒です。おそらくgc_stateにもう一つの二重連結リストを付け足してグローバルな参照をそこに全部つなぎ、マークフェイズでそれらをroot setとして扱うのが良いと思います。stack_nextメンバを使った一重連結リストでも良いですがその場合グローバルな参照を削除するのに線形の時間が必要になってしまいます。

マルチスレッド対応は地道にlockを各所に入れれば良さそうです。gc_stateのstackメンバはスレッドの数だけ用意すればcontentionが減りそうです。ただ、いずれにせよlockは必要ですが。一方で、各スレッドで独立したGCを動かす場合には、グローバル変数gcをスレッドローカルにするだけで良いはずです。

インクリメンタル化はTreadmill GCと同じやり方で簡単に実現できます。つまり、from空間からto空間へのmoveをインクリメンタルに行う(n個単位で行うとか)だけです。と、今書いてて思ったんですがこれいい感じにTask stealingな感じでマルチスレッドに出来ないんですかね。いかにもすでにありそうだけど。

現在のコピーGCに基づく実装は簡単でかつGC中に追加のメモリを必要としないという利点がありますが、一方でそれは必要な情報をオブジェクトのヘッダに入れているだけだと捉えることもできます。4ワードのヘッダは通常の感覚で言えばかなり大きいと思います。アルゴリズムをMark & Sweepにすれば二重連結リストで管理している部分が一重で済むので3ワードにはなります。ただしその分GCを行うために追加の領域が必要になります。ちなみに、スコープの管理のために別にスタックを用意することにすればstack_nextを無くして2ワードまで減らせますが、メモリ使用量の観点からは効果がないです。(ただしキャッシュのヒット率が上がってGCが高速化される可能性は高いです。)

追記

その後よく考えたところいくつかの改良を行うことができました。まず、ヘッダーサイズを3ワードに減らすことができました。これ以上の削減にはアルゴリズムをマーク&スイープにするなどの本質的な変更が必要で、またそのような変更を行なった場合、GC中に追加のメモリ領域を必要としないというコピーGCの恩恵は受けられないと思われます。今回のヘッダサイズ削減はヒープ全体の管理に使用している二重連結構造をルート集合の管理にも用いるようにしたことで実現されました。また、副次的な効果としてスコープの管理が柔軟になったため、グローバルな参照のサポートが簡単に実装できました。さらに、コメント欄で指摘を頂いたマルチスレッド化に向けたインターフェイスの変更についても利便性を損なわずに効率的に実装を行うことができるようになったため実装しました。具体的なコードはおまけ(その2)に追加しました。

見かけ上はスコープ管理に関連するAPIが変更されました。改良版ではスコープは以下のようにして作成します。

struct gc_scope s;

gc_scope_open(&s);
...
gc_scope_close();

またgc_preserveとgc_releaseという二つの関数が追加されました。gc_preserveはオブジェクトとスコープを受け取り、オブジェクトの生存期間を指定されたスコープに変更します。gc_releaseはオブジェクトを受け取り、所属するスコープからの参照を削除します。

struct gc_scope s0;
gc_scope_open(&s0);
{
    struct gc_scope s1;
    gc_scope_open(&s1);

    obj = make_obj();
    gc_preserve(&obj->head, &s0);
    gc_scope_close();

    // obj is alive
}
gc_scope_close();

// obj is dead

gc_preserveの特殊な場合として、受け取ったオブジェクトの生存期間を現在のスコープからみて一つ下のスコープに延長するgc_protectと最上位のスコープに延長するgc_pinを追加しました。たいていの場合gc_pinは大域変数に代入されたオブジェクトに対して使用するはずです。

参照

おまけ

gc.hの全容。

extern struct gc_state {
    struct list_head spaces[2];
    struct gc_head *stack;
    char from;
} gc;

struct gc_head {
    struct list_head head;
    const struct gc_object_type *type;
    struct gc_head *stack_next;
};

struct gc_object_type {
    void (*mark)(struct gc_head *);
    void (*free)(struct gc_head *);
};

#define gc_entry(ptr, type, field) container_of(ptr, type, field)

static inline void gc_init(void) {
    INIT_LIST_HEAD(&gc.spaces[0]);
    INIT_LIST_HEAD(&gc.spaces[1]);
    gc.stack = NULL;
    gc.from = 0;
}

typedef struct gc_head *gc_scope_t;

static inline gc_scope_t gc_scope_open(void) {
    return gc.stack;
}

static inline void gc_scope_close(gc_scope_t s) {
    gc.stack = s;
}

static inline void gc_protect(struct gc_head *head) {
    head->stack_next = gc.stack;
    gc.stack = head;
}

static inline void INIT_GC_HEAD(struct gc_head *head, const struct gc_object_type *type) {
    head->type = type;
    list_add(&head->head, &gc.spaces[gc.from]);
    gc_protect(head);
}

static inline void gc_mark(struct gc_head *head) {
    if ((unsigned long) head->stack_next & 1)
        return;
    head->stack_next = (struct gc_head *) ((unsigned long) head->stack_next | 1);
    list_move_tail(&head->head, &gc.spaces[1 - gc.from]);
}

static inline void gc_run(void) {
    struct gc_head *head, *n;
    /* copy live objects */
    for (head = gc.stack; head != NULL; head = (struct gc_head *) ((unsigned long) head->stack_next & ~1ul)) {
        gc_mark(head);
    }
    list_for_each_entry (head, &gc.spaces[1 - gc.from], head) {
        if (head->type->mark)
            head->type->mark(head);
    }
    /* clean up */
    list_for_each_entry (head, &gc.spaces[1 - gc.from], head) {
        head->stack_next = (struct gc_head *) ((unsigned long) head->stack_next & ~1ul);
    }
    list_for_each_entry_safe (head, n, &gc.spaces[gc.from], head) {
        list_del(&head->head);
        if (head->type->free)
            head->type->free(head);
    }
    gc.from = 1 - gc.from;
}

static inline void gc_destroy(void) {
    gc.stack = NULL;
    gc_run();
}

以下はpicogcのテスト[3]を移植したもの。

#include <stdio.h>
#include <stdlib.h>
#include "gc.h"

struct gc_state gc;

struct list {
    int value;
    struct list *next;
    struct gc_head head;
};

void list_mark(struct gc_head *head) {
    struct list *list = gc_entry(head, struct list, head);
    if (list->next) {
        gc_mark(&list->next->head);
    }
}

void list_free(struct gc_head *head) {
    struct list *list = gc_entry(head, struct list, head);
    printf("free %d!\n", list->value);
    free(list);
}

const struct gc_object_type list_type = { list_mark, list_free };

struct list *cons(int value, struct list *next) {
    struct list *list = malloc(sizeof(struct list));
    INIT_GC_HEAD(&list->head, &list_type);
    list->value = value;
    list->next = next;
    return list;
}

struct list *doit(void) {
    gc_scope_t s = gc_scope_open();

    struct list *a = cons(1, NULL);
    struct list *b = cons(2, NULL);
    struct list *c = cons(3, NULL);
    struct list *d = cons(4, a);

    gc_run();
    puts("0 objects must be released");

    gc_scope_close(s);
    gc_protect(&d->head);
    return d;
}

int main() {
    gc_init();

    {
        gc_scope_t s = gc_scope_open();

        struct list *list = doit();

        gc_run();
        puts("2 objects must be released");

        list->next = NULL;

        gc_run();
        puts("1 object must be released");

        gc_scope_close(s);
    }

    gc_run();
    puts("1 object must be released");

    gc_destroy();
}

おまけ(その2)

改良版


struct gc_scope {
    struct list_head local;
    struct gc_scope *next;
};

extern struct gc_state {
    struct list_head from, to;
    struct gc_scope *scope, global;
} gc;

struct gc_head {
    struct list_head head;
    const struct gc_object_type *type;
};

struct gc_object_type {
    void (*mark)(struct gc_head *);
    void (*free)(struct gc_head *);
};

#define gc_entry(ptr, type, field) container_of(ptr, type, field)

static inline void gc_scope_open(struct gc_scope *s) {
    INIT_LIST_HEAD(&s->local);
    s->next = gc.scope;
    gc.scope = s;
}

static inline void gc_scope_close(void) {
    list_splice(&gc.scope->local, &gc.from);
    gc.scope = gc.scope->next;
}

static inline void gc_preserve(struct gc_head *head, struct gc_scope *s) {
    list_move(&head->head, &s->local);
}

static inline void gc_release(struct gc_head *head) {
    list_move(&head->head, &gc.from);
}

#define gc_protect(head) gc_preserve((head), gc.scope->next)
#define gc_pin(head) gc_preserve((head), &gc.global)

static inline void INIT_GC_HEAD(struct gc_head *head, const struct gc_object_type *type) {
    INIT_LIST_HEAD(&head->head);
    head->type = type;
    gc_preserve(head, gc.scope);
}

static inline void gc_mark(struct gc_head *head) {
    if ((unsigned long) head->type & 1)
        return;
    head->type = (struct gc_object_type *) ((unsigned long) head->type | 1);
    list_move_tail(&head->head, &gc.to);
}

#define gc_type(head) ((struct gc_object_type *) ((unsigned long) (head)->type & ~1ul))

static inline void gc_run(void) {
    struct gc_head *head, *n;
    struct gc_scope *s;
    for (s = gc.scope; s != NULL; s = s->next) {
        list_for_each_entry (head, &s->local, head)
            head->type = (struct gc_object_type *) ((unsigned long) head->type | 1);
    }
    /* copy live objects */
    INIT_LIST_HEAD(&gc.to);
    for (s = gc.scope; s != NULL; s = s->next) {
        list_for_each_entry (head, &s->local, head)
            if (gc_type(head)->mark) gc_type(head)->mark(head);
    }
    list_for_each_entry (head, &gc.to, head) {
        if (gc_type(head)->mark) gc_type(head)->mark(head);
    }
    /* clean up */
    for (s = gc.scope; s != NULL; s = s->next) {
        list_for_each_entry (head, &s->local, head)
            head->type = (struct gc_object_type *) ((unsigned long) head->type & ~1ul);
    }
    list_for_each_entry (head, &gc.to, head) {
        head->type = (struct gc_object_type *) ((unsigned long) head->type & ~1ul);
    }
    list_for_each_entry_safe (head, n, &gc.from, head) {
        if (head->type->free) head->type->free(head);
    }
    INIT_LIST_HEAD(&gc.from);
    list_splice(&gc.to, &gc.from);
}

static inline void gc_init(void) {
    INIT_LIST_HEAD(&gc.from);
    gc.scope = NULL;
    gc_scope_open(&gc.global);
}

static inline void gc_destroy(void) {
    gc.scope = NULL;
    gc_run();
}