Cでクロージャ

GCC拡張を使えばCもクロージャが使える。

int
retfunc( int x )
{
	int a = 20;
	int hogehoge( ) { return a; }
	return hogehoge();
}

GCC拡張で、ネストした関数は、外側のスコープの変数を参照できる、というのは有名な話かと思う。
これの実装は結構面白くて、スタックの上に、フレームをロードしたあと、関数を呼び出すプログラムを実行時に生成して、それを関数ポインタとする、というようになっている。
（どっか解説有るかなーっと思ったけど見つからないな…google:gcc trampolineとかを漁ってみるとよいかもしれない）

gcc4.1、x86だと、

	mov	$フレームのアドレス, %ecx
	jmp	関数のアドレス

こういうプログラムをスタックの上に生成して、それを関数ポインタとするのである。(exec-shieldがあるともうちょっと色々あるらしいけど)
ちなみに、これは、

typedef int (*func_t)( int );
func_t dump_closure( func_t f)
{
	int i;
	unsigned char *p = (unsigned char*)f;
	for ( i=0; i<10; i++ ) {
		putchar( p[i] );
	}
	return f;
}
func_t
retfunc( int x )
{
	int a = 4;
	int hogehoge( int b ) { return b + a + x; }
	dump_closure( hogehoge );
}

こういう感じのプログラムを書いて、

$ ./a.out > out
$ objdump -m i386 -b binary -D out

out:     ファイル形式 binary

セクション .data の逆アセンブル:

00000000 <.data>:
   0:	b9 08 f6 93 bf       	mov    $0xbf93f608,%ecx   ; これがフレームのアドレスね
   5:	e9 f0 8d 70 48       	jmp    0x48708dfa         ; これが関数へのジャンプ

こうやれば見られる。

で、ここまでが前提知識。続いて、クロージャを実装する。

GCC3.4とかでは無理だったのだけど、GCC4.xだと、このトランポリンを作るときのスタック構造が、

|        | 
+--------+
| local  | <- mov xxx, %ecx で %ecxに入れられる値
+--------+
| local  |
+--------+
| ....   |
.        .
+--------+
|mov     | <- mov $0xbf93f608, %ecx
+        +
|  0x08  |
+        +
|  0xf6  |
+        +
|  0x93  |
+        +
|  0xbf  |
+--------+
|jmp     | <- jmp 0x48708dfa
+        +
|  0xf0  |
+        +
|  0x8d  |
+        +
|  0x70  |
+        +
|  0x48  |
+--------+
. .....  .
| .....  | <- %ebp
+--------+

こんな感じになってるのである。（必ずこうなるのかどうかは調べてない）

これがあれば、ネストされた関数が使うフレームの大きさがわかる。
ここまでくれば、答えは見えたも同じだ。

struct trampoline_code /* トランポリンのコード */
{
	char mov_ecx;
	unsigned char *frame_start; /* フレームのアドレスはここに */
	char jmp_func;
	unsigned char *func_offset; /* ジャンプ先のアドレスはここに */
} __attribute__((packed)) ;

func_t
make_closure( func_t f )  /* f がトランポリンの先頭アドレス */
{
	struct trampoline_code *src = (struct trampoline_code*)f;
	unsigned char *tramp_start = (unsigned char*)src;
	unsigned char *frame_start = src->frame_start;

	/* フレームは、フレームの先頭とトランポリンの先頭の間 */
	unsigned int frame_size = tramp_start-frame_start;

	unsigned char *off;

	unsigned char *frame = malloc( frame_size );

	struct trampoline_code *dst = malloc( sizeof(struct trampoline_code) );

	/* フレームの値をコピー */
	memcpy( frame, frame_start, frame_size );

	/* トランポリンのコピー */
	dst->mov_ecx = -71;
	dst->jmp_func = -23;
	dst->frame_start = frame;
	off = (unsigned int)src->func_offset + (unsigned char*)src;
	dst->func_offset = off - (unsigned int)dst;

	return (func_t)dst;
}

これで、クロージャができる！！

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef int (*func_t)(  );

struct trampoline_code
{
	char mov_ecx;
	unsigned char *frame_start;
	char jmp_func;
	unsigned char *func_offset;
} __attribute__((packed)) ;

func_t
make_closure( func_t f )
{
	struct trampoline_code *src = (struct trampoline_code*)f;
	unsigned char *tramp_start = (unsigned char*)src;
	unsigned char *frame_start = src->frame_start;
	unsigned int frame_size = tramp_start-frame_start;
	unsigned char *off;

	unsigned char *frame = malloc( frame_size );

	struct trampoline_code *dst = malloc( sizeof(struct trampoline_code) );
	memcpy( frame, frame_start, frame_size );
	dst->mov_ecx = -71;
	dst->jmp_func = -23;
	dst->frame_start = frame;
	off = (unsigned int)src->func_offset + (unsigned char*)src;
	dst->func_offset = off - (unsigned int)dst;

	return (func_t)dst;
}


void
dump_result(void)
{
	func_t func[10];
	int i;


	for ( i=0; i<10; i++ ) {
		int n = i*i;
		int hogehoge(  ) { return n + 30; }
		func[i] = make_closure( hogehoge );
	}

	for ( i=0; i<10; i++ ) {
		printf("%d\n",func[i]());
	}
}

int main()
{
	dump_result();
	return 0;
}

だからどうした！！
TODO: 引数に対応する。（しません）