自力で末尾再帰をループにしてみた ver C

コールスタックについて理解するためにスタックをいじって遊んでみました。

C言語で末尾再帰関数を呼び出す際にスタックを使い果たさないようにしてみます。もっとも、gccだと-O2を付けてコンパイルすると最適化がかかって勝手にループになるみたいではありますが。

関数呼び出し後のスタックに積まれている値とesp,ebpの値は以下のようになるらしいです。

...
ebp + 8 : 第1引数
ebp + 4 : リターンアドレス
ebp + 0 : 呼び出し元でのebpの値
ebp - 4 : ローカル変数
...
ebp - x : ローカル変数
このへん <- ESP

バッファオーバーフローやoff-by-oneエラーではreturn時に復帰するリターンアドレス(returnする際に移るアドレスを変える)や呼び出し元のebp(呼び出し元関数がreturnする際に移るアドレスを変える)を書き換えることでexploitしたりするようです。

#include <stdio.h>

void recur(void (*fn)(unsigned int n), unsigned int n){
	unsigned int ebp = 0;
	unsigned int old_ebp = 0;

	__asm__("movl %%ebp, %0" : "=r" (ebp) :);

        // 現在のebpが指す値が、呼び出し元関数のebpである
	old_ebp = *((unsigned int *)ebp);

	// fn の引き数
	*((unsigned int *)(old_ebp + 8)) = n;
	// fnからESPの退避などの分をずらしたアドレス
	*((unsigned int *)(ebp + 4)) = (unsigned int)fn + 9;
}

void dec(unsigned int n){
	char buf[256];
	if(n == 0){
		printf("done\n");
	}else{
		printf("n = %d\n", n);
		recur(dec, n - 1);
	}
	return;
}

void dec2(unsigned int n){
	char buf[256];
	if(n == 0){
		printf("done\n");
	}else{
		printf("n = %d\n", n);
		dec2(n - 1);
	}
	return;
}

int main(void){
        // decは正常終了する
	dec(100000);
        p// dec2はスタックを使い果たしてSEGVる
	// dec2(100000);
	return 0;
}

recur関数はリターンアドレスを書き換えることでreturnするときに第一引数に渡した関数へ制御を移します。

fn + 9としているのはebpのpushとespの減算分の処理を飛ばすためです。

// objdump の結果(一部)
08048480 <dec>:
 8048480:	55                   	push   %ebp
 8048481:	89 e5                	mov    %esp,%ebp
 8048483:	81 ec 28 01 00 00    	sub    $0x128,%esp

この定数はローカル変数の領域のサイズによって変わると思われるので、汎用性は無いです。