ごみ集めを邪魔するもの

と、いうわけで帰ってきた。昨日の記録を見てみると、今日帰ってきたように見えるが、帰ってきたのは昨日。そこらへんは察して。


で、帰ってきたわけだが、僕は、家に入った瞬間、がくぜんとする。部屋がちらかっているわけだ。ううん。
確か、僕は、去年の最後あたりに、「大掃除する」と決めたはずだ。が、しかし、部屋は散らかっている。何故だ。何かがおかしい。
答えは、もちろん、決意しただけで実際に実行には移さなかったからなんだけど、いや、しかし、やっぱりおかしいのではないか？何故掃除を決意したのに、実行はされなかったんだ？


僕は、そこで、「何者かが、僕の掃除しようとする決意を邪魔する電波を送ってるに違いない」と、いう結論を得る。部屋が散らかっているのは僕の責任ではない。どこかで掃除を阻止しようとする力が働いてるのだ。


と、いうようなどうでもいい話はいいとして、C with GCを読んだり、C言語でコピーGCを読んだりして、Cで無理矢理Copying GCを実装するのも面白そうだと思った次第。


C言語は、他の言語と違って、GCの実装を邪魔しようとする大きな問題が、いくつも転がっている。それらを全て解決しないと、正しいGCは書けない。tanakhさんとこにも書いてある、ポインタと整数の区別が付かない、と、いうのも、そのひとつだ
が、しかし、そこらへんは環境依存にこだわらなければ、結構なんとかなったりするのだ。で、そこらへん、傾向と対策について考えてる。

  • ポインタと整数の区別が付かない

まず、わかりやすく、かつ、致命的な問題。
変数に型情報が付いてない。全てのオブジェクトが、ただの数値の羅列にしか見えない。
どうすればいいんだろうか。
このへん、GCCのGCが、C構造体から、マーク用のルーチンを生成するツールを使って解決してたりするのが参考になるかもしれない。が、いちいちツールを通すのは面倒。
と、思ってたら、h_sakuraiさんのところで、dumperと同じような要領で…って書いてあって、なるほど、と、思った。
DWARF2の情報をGCにも使う、というのは面白いかもしれない。DWARF2の情報を使えば、スタックを巡るのもできるようになるし。


デバッグ情報は実は、色々と有効に活用できるんじゃないかという説が。

  • どこらへんにルート変数があるのかわからない

ポインタは、bss領域にあるかもしれないし、data領域かもしれないし、スタック上かもしれない。それ以外かもしれない。
大体のOS、リンカでは、bssとdata領域の最初と最後では、なんか、特殊なシンボルを埋めてたりするので、それが利用できるかもしれない。
(data領域の先頭は無いかも…bssは多分ある。)

extern int __bss_start;
extern int _end;

int a;
int b;
int c;
int d;

int main()
{
	int *p;

	a=500;
	b=999;
	c=0xff;
	d=88;

	for ( p=&__bss_start; p!=&_end; p++ ) {
		printf("%d\n",*p);
	}

	return 0;
}
/*
0   <- ???
999
255
500
*/

マークしたいオブジェクトはbss領域に置く…とか？


スタック領域は、ローカル変数のアドレスでわかる。

  • 参照はメモリを読んでくるしかない

Javaのように、参照する動作が隠蔽されてればいいんだけど、C言語の参照する、とは、すなわち、「メモリからデータを読んでくること」。ただそれだけだ。


参照が抽象化されてれば、「実は、テーブルのインデックスで、ポインタはテーブルに埋まってるんです」とかやって、Copying GCを実装しちゃったり、write barrier張ったりできるんだけど、C言語ではそれは不可能だ。


write barrierは、OSのメモリ保護機能で実現できるかもしれない。そこらへんはよくわからんが。


  • 配列、構造体の途中を参照してるかも…

地味に致命的な問題。

	int *a = alloc( 32 );
	int *p = &(a[3]);
	a = NULL;

この場合、先頭は参照されていないが、3番目が参照されているので配列は解放してはいけない。
Boehm GCはどうやってんのかな…

  • union
union
{
	int i;
	int*p;
};

Oh!
きみ、それはポインタかい？整数値かい？どうやっても判定不可能だよ。


ちなみに、GCCのGCでは、unionに、判定ルーチンを付けることができる。（というか、付けないとエラーになる）

  union tree_decl_u2 {
    struct function * GTY ((tag ("FUNCTION_DECL"))) f;
    rtx GTY ((tag ("PARM_DECL"))) r;
    tree GTY ((tag ("FIELD_DECL"))) t;
    int GTY ((tag ("VAR_DECL"))) i;
  } GTY ((desc ("TREE_CODE((tree) &(%0))"))) u2;

descの式でswitchして、tagがcaseのラベルになる、というもの。


面倒だけど、これ以外に方法無いよな…

Cのプログラマは平気でポインタをintにキャストする。

int func( union u v, int tag )
{
	if ( tag == POINTER )
		return (int)v.pointer
}

Cプログラマは、レジスタに入れられる値はなんでも同じだと考えるのだ！！（多分）


まあ、これはさすがにプログラマが悪いだろ…


と、いうわけで、GCのアルゴリズムはどうするべきか。っていう話なんだけど、眠くなってきたのでこのへんで。
気が向いたら、続く。