勉強会でMiniLispのソースコードを読んだので、ガベージコレクションのところを解説します。
evalの解説はこちら。
まずMiniLispのガベージコレクション(以下gc)で使用されているCheney's algorithmの概要を説明した後、MiniLispの実装についてソースコードを引用しながら説明します。なお解説しない箇所については適宜ソースコードを省略しています。
MiniLispのソースコードには、ガベージコレクションについてコメントが丁寧に書かれているため参考になりました。
間違いなどありましたら、ご指摘いただけるとありがたいです。
Cheney's algorithmの概要
wikipediaとこちらのサイトを参考にしました。後者のサイトではgcが行われるようすのアニメーションがあり、わかりやすいです(Java appletを動かす必要があります)。
以下、説明です。
gcに使用するヒープを半分に分け、片方のヒープにオブジェクトを割り当てていきます。オブジェクトが割り当てられていく方のヒープをfrom-space、割り当てられていない方のヒープをto-spaceと呼びます。
gcを実行する際、まずアクティブなオブジェクトへの参照をすべてチェックしていき以下の2つの処理のどちらかを行います(今後はこの処理「forward処理」と呼びます)。
参照先にあるオブジェクトがto-spaceに移動されていない場合
オブジェクトをfrom-spaceからto-spaceへ移動する(to-spaceにメモリを割り当て、オブジェクトそのもののデータをto-spaceにコピーする)。また、参照をコピー先のアドレスに更新する。その後、オブジェクトがあった場所(from-space)にオブジェクトのコピー先(to-space)を示すポインタ(following pointerという)を残す。参照先にあるオブジェクトがすでにto-spaceに移動されていた場合
参照をfollowing pointerの示しているアドレスに更新する。
その後、to-spaceにあるオブジェクトの参照をすべてチェックしていき、上記forward処理を行います。
to-spaceの参照チェックがすべて終わったら移動完了です。
from-spaceにあるオブジェクトはすべて破棄することができます。
MiniLispがlispオブジェクトを作成するときにやっていること
ここではMiniLispがlispオブジェクトを作成する方法について解説していきます。
lispオブジェクトとは以下のような構造体です。
typedef struct Obj {
// The first word of the object represents the type of the object. Any code that handles object
// needs to check its type first, then access the following union members.
int type;
// The total size of the object, including "type" field, this field, the contents, and the
// padding at the end of the object.
int size;
// Object values.
union {
// Int
int value;
// Cell
struct {
struct Obj *car;
struct Obj *cdr;
};
// Symbol
char name[1];
// Primitive
Primitive *fn;
// Function or Macro
struct {
struct Obj *params;
struct Obj *body;
struct Obj *env;
};
// Environment frame. This is a linked list of association lists
// containing the mapping from symbols to their value.
struct {
struct Obj *vars;
struct Obj *up;
};
// Forwarding pointer
void *moved;
};
} Obj;
数値、シンボル、consセル、プリミティブ関数、ユーザー定義関数、マクロ、環境、following pointerのいずれかを表現できます。
ヒープ領域の確保
まずalloc_semispaceでオブジェクトを割り当てていくヒープを確保します。システムコールで実際に動的メモリを確保しているのはここだけです。
static void *alloc_semispace() {
return mmap(NULL, MEMORY_SIZE, PROT_READ | PROT_WRITE, MAP_PRIVATE | MAP_ANON, -1, 0);
}
lispオブジェクトの割り当て
確保したヒープに、allocを使用してオブジェクトを割り当てていきます。
allocは、これまでヒープに割り当てたオブジェクトの合計サイズを記録する役割も果たしており、もし十分な領域がなくなればgcを実施します。
// Allocates memory block. This may start GC if we don't have enough memory.
static Obj *alloc(void *root, int type, size_t size) {
(省略)
// Otherwise, run GC only when the available memory is not large enough.
if (!always_gc && MEMORY_SIZE < mem_nused + size)
gc(root);
(省略)
// Allocate the object.
Obj *obj = memory + mem_nused;
obj->type = type;
obj->size = size;
mem_nused += size;
return obj;
}
allocはlispオブジェクトのコンストラクタ内で使用されます。
例えばintオブジェクトのコンストラクタは以下のようになっています。
static Obj *make_int(void *root, int value) {
Obj *r = alloc(root, TINT, sizeof(int));
r->value = value;
return r;
}
Cからlispオブジェクトへのアクセス方法
さて、上記のmake_intでは作成したオブジェクトへのポインタを返しています。
作成したオブジェクトにアクセスするためには、コンストラクタの戻り値を変数に入れて保存しておけば良さそうですが、この方法には問題があります。
オブジェクトへの参照は、gc実行後にはfrom-spaceからto-spaceに移動されるため、アドレスが変わってしまいます。
そのため、コンストラクタの戻り値を変数に保存して、再度アクセスするまでの間にgcが実行された場合、無効なアドレスへのアクセスとなりSEGVが起きてしまう可能性があります。
MiniLispではgc実行後もオブジェクトのアドレスに正しくアクセスできるようにするため、オブジェクトへのアクセスは以下のような2階層を通るようになっています。
- オブジェクトを指すポインタ
- 1へのポインタ(ポインタのポインタ)
SEGVを避けるためには、Cからオブジェクトへアクセスする時は必ず ポインタのポインタ -> ポインタ -> オブジェクトの順にアクセスするようにします。また、gc実行時にto-spaceへオブジェクトを移動した際には、上記のオブジェクトのポインタとオブジェクトのアドレスが変わりますが、その際にオブジェクトのポインタの新しいアドレスでポインタのポインタを書き換えるようにする必要があります。
上記のようなポインタの階層を構築するためのマクロは以下のように定義されています。
MiniLispでは上記allocでオブジェクトを割り当てる前に必ずこれらのマクロを使います。
#define ROOT_END ((void *)-1)
#define ADD_ROOT(size) \
void *root_ADD_ROOT_[size + 2]; \
root_ADD_ROOT_[0] = root; \
for (int i = 1; i <= size; i++) \
root_ADD_ROOT_[i] = NULL; \
root_ADD_ROOT_[size + 1] = ROOT_END; \
root = root_ADD_ROOT_
#define DEFINE1(var1) \
ADD_ROOT(1); \
Obj **var1 = (Obj **)(root_ADD_ROOT_ + 1)
#define DEFINE2(var1, var2) \
ADD_ROOT(2); \
Obj **var1 = (Obj **)(root_ADD_ROOT_ + 1); \
Obj **var2 = (Obj **)(root_ADD_ROOT_ + 2)
#define DEFINE3(var1, var2, var3) \
ADD_ROOT(3); \
Obj **var1 = (Obj **)(root_ADD_ROOT_ + 1); \
Obj **var2 = (Obj **)(root_ADD_ROOT_ + 2); \
Obj **var3 = (Obj **)(root_ADD_ROOT_ + 3)
#define DEFINE4(var1, var2, var3, var4) \
ADD_ROOT(4); \
Obj **var1 = (Obj **)(root_ADD_ROOT_ + 1); \
Obj **var2 = (Obj **)(root_ADD_ROOT_ + 2); \
Obj **var3 = (Obj **)(root_ADD_ROOT_ + 3); \
Obj **var4 = (Obj **)(root_ADD_ROOT_ + 4)
DEFINE(1-4) で、オブジェクトのポインタのポインタを入れるための変数が宣言されます。これらの変数は呼び出し元の式で DEFINE(1-4) が使われるたびにスタックに積まれていきます。ADD_ROOTにあるrootはスタックの最後尾を指すための(void *)型の変数です。
例えば、rootの初期値をNULLとして以下コードのように宣言すると
DEFINE2(n1, n2);
*n1 = make_int(root, 1);
*n2 = make_int(root, 2);
以下の図のようになります。
その後さらに以下のように宣言すると
DEFINE3(n3, n4, n5);
*n3 = make_int(root, 3);
*n4 = make_int(root, 4);
*n5 = make_int(root, 5);
以下の図のようになります。
MiniLispのエントリポイントは以下のようになっています。
int main(int argc, char **argv) {
(省略)
// Memory allocation
memory = alloc_semispace();
// Constants and primitives
Symbols = Nil;
void *root = NULL;
DEFINE2(env, expr);
*env = make_env(root, &Nil, &Nil);
define_constants(root, env);
define_primitives(root, env);
// The main loop
for (;;) {
*expr = read_expr(root);
(省略)
print(eval(root, env, expr));
printf("\n");
}
}
rootを宣言した後、環境と読み込んでいる式をいれるための変数envとexprをDEFINE2で作成し、define_constrantsとdefine_primitivesでlisp内でグローバル変数とその値を作成します(define_constrantsとdefine_primitivesは内部でDEFINE(1-4)が使っています)。
その後メインループで次々に式をread(read_expr)、evalしていきます。上記のグローバル変数の定義が終わった時のrootの状態が、メインループである式をreadしてevalする際の初期状態となります。一つの式を評価し終えたらrootは初期状態に戻ります。rootはコールスタックとなっており、それを辿ることですべての有効な変数が得られます。
MiniLispのgcで行っていること
gcのソースコードは以下のようになっています。
static void gc(void *root) {
assert(!gc_running);
gc_running = true;
// Allocate a new semi-space.
from_space = memory;
memory = alloc_semispace();
// Initialize the two pointers for GC. Initially they point to the beginning of the to-space.
scan1 = scan2 = memory;
// Copy the GC root objects first. This moves the pointer scan2.
forward_root_objects(root);
// Copy the objects referenced by the GC root objects located between scan1 and scan2. Once it's
// finished, all live objects (i.e. objects reachable from the root) will have been copied to
// the to-space.
while (scan1 < scan2) {
switch (scan1->type) {
case TINT:
case TSYMBOL:
case TPRIMITIVE:
// Any of the above types does not contain a pointer to a GC-managed object.
break;
case TCELL:
scan1->car = forward(scan1->car);
scan1->cdr = forward(scan1->cdr);
break;
case TFUNCTION:
case TMACRO:
scan1->params = forward(scan1->params);
scan1->body = forward(scan1->body);
scan1->env = forward(scan1->env);
break;
case TENV:
scan1->vars = forward(scan1->vars);
scan1->up = forward(scan1->up);
break;
default:
error("Bug: copy: unknown type %d", scan1->type);
}
scan1 = (Obj *)((uint8_t *)scan1 + scan1->size);
}
// Finish up GC.
munmap(from_space, MEMORY_SIZE);
size_t old_nused = mem_nused;
mem_nused = (size_t)((uint8_t *)scan1 - (uint8_t *)memory);
if (debug_gc)
fprintf(stderr, "GC: %zu bytes out of %zu bytes copied.\n", mem_nused, old_nused);
gc_running = false;
}
順を追って要点を解説していきます。
gcの進行状況の管理
scan1とscan2というポインタを使って以下のようにgcの進行状況を管理しています。scan1、scan2ともにgc開始時はto-spaceの最初の位置を指しており、scan2はto-spaceの空きメモリの先頭を指しています。
状況は以下のようにわかります。
- scan1の後にあるオブジェクトは、そのオブジェクトもっている参照先にあるオブジェクトも含めてto-spaceにコピーが完了しています。
- scan1とscan2の間にあるオブジェクトは、オブジェクト自体はto-spaceにコピーされているが、オブジェクトがもっている参照先にあるオブジェクトがfrom-spaceに存在している可能性がある状態。
アクティブなオブジェクトにforward処理を実施
アクティブなオブジェクトとは、コールスタックにある変数とグローバル変数が参照しているオブジェクトです。
forward_root_objectsでは、すべてのアクティブなオブジェクトにforward処理を行います。
static void forward_root_objects(void *root) {
Symbols = forward(Symbols);
for (void **frame = root; frame; frame = *(void ***)frame)
for (int i = 1; frame[i] != ROOT_END; i++)
if (frame[i])
frame[i] = forward(frame[i]);
}
まずSymbols = forward(Symbols);で、すべてのグローバル変数を表すSymbolsにforward処理を行っています。
次にコールスタック(root)を辿って変数が参照しているオブジェクトをチェックしていき、それぞれのオブジェクトに対してforward処理を行います。for (void **frame = root; ...)というループでは、スタックの最後尾にあるroot_ADD_ROOT_から1つ前のroot_ADD_ROOT_へ進んで行きます。ネストしているfor (int i = 1; ...)というループでは、root_ADD_ROOT_の2つ目の要素から最後-1の要素まで進んでいきます。
先ほどの図のrootが辿られる様子を表すと以下のようになります。赤丸の数字の順にforwardが行われます。青い矢印はfor (int i = 1; ...)のループ。緑の矢印はfor (void **frame = root; ...)のループの進行です。
オブジェクトがNULLでなければ、frame[i] = forward(frame[i]);でforward処理を行っています。
forwardの戻り値は移動後のオブジェクトのポインタのアドレスですが、この値でオブジェクトのポインタのポインタを書き換える処理も行っています。このようにすることでSEGVを避けることができます。
to-spaceにあるオブジェクトにforward処理を実施
while (scan1 < scan2) {...}のブロックでto-spaceのオブジェクトをチェックしていき、それぞれに対してforward処理を行いますが、実質ここでは参照先オブジェクトがすでにto-spaceへ移動されていた場合の処理しか行われることはありません。
すべてのチェックが終わればアクティブなオブジェクトはすべてto-spaceにコピー完了したことになります。
from-spaceの削除
munmap(from_space, MEMORY_SIZE);でfrom-spaceの削除を実施しています。
次回gcを実施するときは、今回のto-spaceがfrom-spaceとして扱われ、to-spaceは新たに確保されます。