Scala Native の Immix GC 実装の使い方

※この記事は 言語実装 Advent Calendar 2018の15日目の記事です。

はじめに

ブログがあったことすら完全に忘れていました。

Immix¹は Blackburn らが提案した高速なガベージコレクション（GC）の手法です。 Scala Nativeではv0.3.0においてこのImmix GCを実装し、従来のBohem GCに代えて使用できるようになりました。 また、Scala NativeではImmix GCの実装を言語処理系自身から分離したものを公開しています。

このImmix GC 実装は他の言語処理系からの利用が容易になるよう配慮されている（と個人的に思っている）のですが、どこを探してもまともな資料がありません。そこで本記事では私が調べた、この実装（以降はlibImmixと呼ぶことにします）を自作処理系に組み込むための基本的な知見等について書き残し、供養しておきたいと思います²。

ユーザとして使用する分には、Immix GCはマークアンドスウィープGCとほぼ同じように扱える³ため、マークアンドスウィープの概要を頭の片隅に置きながら、以後の文章を読んでいただければと思います。

GitHubの該当リポジトリからcloneし、readmeにあるとおりにビルドしてください⁴。build/にlibImmix.aができるので、これを使います。

libImmixの使い方

libImmixと共有するグローバル変数

libImmixを使用するにあたり、以下の3つのグローバル変数をlibImmix側から見られるようにしておく必要があります。

uintptr_t *__modules;
int __modules_size;
uintptr_t **__stack_bottom;

これらはガベージコレクタが marking を行う際のルートとして使用されます。

__modulesおよび__modules_sizeはstaticな寿命を持つオブジェクト⁵の配列であり、後述するscalanative_alloc系の関数の返値の配列を設定します。 また、__stack_bottomはスタックの底へのポインタであり、ガベージコレクタはスタックの先頭からこの変数に設定したアドレスまでをGCの対象とします。

ガベージコレクタはこの2つの領域（__modulesを先頭とする要素数__modules_sizeの配列および、スタックの頭から__stack_bottomまで）を走査し、 その中に自身が確保したメモリ領域へのポインタを探し出し、オブジェクトをたどる起点とします。

libImmixが提供する関数

libImmixは以下の関数を提供します。

extern "C" void scalanative_init();
extern "C" void *scalanative_alloc(void *info, size_t size, int isObjectArray);
extern "C" void *scalanative_alloc_small(void *info, size_t size);
extern "C" void *scalanative_alloc_large(void *info, size_t size);
extern "C" void scalanative_collect();

scalanative_initとscalanative_collectはその名の通り、ガベージコレクタの初期化と明示的なオブジェクト回収を行います。 scalanative_alloc系の関数は、size分のメモリをガベージコレクタが管理する領域から確保します。また、infoには後述のRtti構造体へのポインタをvoid*にして渡します。

alloc系の関数の返値は、以下のような構造体へのポインタにキャストして使うことができます。

struct Obj {
    Rtti* info;
    uintptr_t body[0];
};

このうち、infoにはalloc系関数の引数に渡した値がそのままセットされます。また、bodyが、ユーザが使用できる領域の先頭になります。 bodyにはalloc系関数の引数sizeの大きさの領域が確保されます。

scalanative_alloc関数では、isObjectArrayをtrueにすると、その領域をオブジェクトの配列と見なし、marking時にその領域すべてを走査するようになります。

scalanative_alloc_smallとscalanative_alloc_largeの使い分けですが、Scala Nativeでは、8192 bytes 以上のオブジェクトに対してlargeを、それ未満のオブジェクトに対してsmall を使用しているようです⁶⁷。

Rtti構造体

Rtti構造体はその名の通り、Scalaの実行時型情報（RTTI）を扱う構造体のようです。

Rtti構造体は以下のように定義されています（ObjectHeader.hより）。

typedef struct {
    struct {
        int32_t id;
        word_t *name;
        int8_t kind;
    } rt;
    int64_t size;
    struct {
        int32_t from;
        int32_t to;
    } range;
    struct {
        int32_t dyn_method_count;
        word_t *dyn_method_salt;
        word_t *dyn_method_keys;
        word_t *dyn_methods;
    } dynDispatchTable;
    int64_t *refMapStruct;
} Rtti;

この内、GCに必要となるのはrefMapStructのみです。実際にlibImmixを自作言語処理系に組み込む場合は、ObjectHeader.hの各種構造体を 自身の処理系で使っているものと同じになるように書き換えた方が良いかもしれません。

refMapStructは、その型のどこに他のオブジェクトへの参照を持っているかを表す配列です。 上記Obj構造体のbodyフィールドのうち、他のオブジェクトのアドレスとなっている要素のインデックスを並べ、最後に番兵として-1を置きます。

その他

Log.h内の#define DEBUG_PRINTを有効にすると、GCが走ったタイミングでどれくらいの領域が開放されたかなどの情報が表示されるようになります。

以上が私が調べた範囲でのlibImmixの基本的な使い方です。 libImmixはScala Licenseで提供されているため、ライセンス的に自作言語処理系に組み込みやすく、何よりBoehmGCに比べてかなり高速なのが嬉しいところですね。

慌てて書いたので誤り等多々あるかと思います。お気づきの際は優しくお知らせいただければと思います。