Jserv's blog

探訪 stack frame：談不定數量參數

前文 [以 C 語言實做 Functional Language 的 Currying] 已探討在 IA32 stack 的操作，讓 Currying 的行為得以在此基礎，予以實現，而我們還可看另一種應用：C 語言的不定數量參數，也就是 stdarg.h 裡規範的行為。當我們使用 printf() 函式搭配強大的資料格式化處理 (printf 本身就是個小型的 interpreter) 時，不免會其運作行為感到好奇，以下是 GNU/Linux 上 /usr/include/stdio.h 的 prototype：(取自 glibc)

__BEGIN_NAMESPACE_STD
...
/* Write formatted output to stdout.
   This function is a possible cancellation point and therefore not
   marked with __THROW.  */
extern int printf (__const char *__restrict __format, ...);

注意到函式參數列裡頭的 "..."，語法上表示不定個數的參數輸入，在實做面則不離 stack 的行為，筆者以一個簡單的小程式，說明其運作原理： (multiply.c)

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

static int multiply() 
{
	int *bp;
	int result = 1;
	/* Start stack traverse */

#if defined(__i386)
	__asm__( "movl %%ebp, %0" : "=g"(bp));
#elif defined(__x86_64__)
	__asm__( "movq %%rbp, %0" : "=g"(bp));
#else
	/*
	 * Caution: this would fail if it points to the end of the saved
	 * registers instead of the start. (gcc bug in 4.1 branch)
	 */
	bp = (void **) __builtin_frame_address(0);
#endif
	bp += 2;
	while (abs(*bp) < 0x1000000) {
		result *= *bp++;
	}
	return result;
}

int main()
{
	printf("1! = %7d\n", multiply(1));
	printf("2! = %7d\n", multiply(1,2));
	printf("3! = %7d\n", multiply(1,2,3));
	printf("4! = %7d\n", multiply(1,2,3,4));
	printf("5! = %7d\n", multiply(1,2,3,4,5));
	printf("6! = %7d\n", multiply(1,2,3,4,5,6));
	printf("7! = %7d\n", multiply(1,2,3,4,5,6,7));
	printf("8! = %7d\n", multiply(1,2,3,4,5,6,7,8));
	printf("9! = %7d\n", multiply(1,2,3,4,5,6,7,8,9));
	return 0;
}

先看看 main() 裡頭的函式呼叫方式，數學的 1!, 2!, 3!, .., 9! (階層運算) 定義就是 1, 1*2, 1*2*3, ..., 1*2*3*...*8*9, 這裡用 multiply() 函式實現，又，筆者在前文已大致提及 C 語言的 function call 與 IA32 stack 的執行時期行為對應：%ebp 指向 frame pointer 頂端，function 本體必須在 prologue 處理好 caller/callee 的 frame pointer，而參數的傳遞也是這時該考量的。所以，若我們可取得 stack 中 frame pointer 的內含值，往後推算，不就可取得參數內容嗎？進而，我們可拿這些資料作自行規範的舉動，比方說本範例的乘法運算。

取得 %ebp 的方式可透過 inline assembly，如程式碼列表中 x86 與 x86_64 的動作，或者考慮到不同平台，可援引 GCC 的 GNU Extension : __builtin_frame_address，以下是文件的描述：

void *__builtin_frame_address (int level);

This function is similar to __builtin_return_address, but it returns the address of the function frame rather than the return address of the function. Calling __builtin_frame_address with a value of 0 yields the frame address of the current function, a value of 1 yields the frame address of the caller of the current function, and so forth.

The frame is the area on the stack which holds local variables and saved registers. The frame address is normally the address of the first word pushed on to the stack by the function. However, the exact definition depends upon the processor and the calling convention. On the Motorola 68000, if the function has a frame, then __builtin_frame_address will return the value of the frame pointer register a6 if level is 0.

簡單來說，此內建的函式用以提供 backtrace 或動態偵錯所需的基礎建設，回傳函式的結構體 (為 frame address，而非 return address)，當參數代入 "0" 時，回傳目前的函式 frame address，而代入 "1" 時，回傳呼叫目前函式的函式的 frame address，參數的數值越大，則表示越上層。

stack frame 就是保存變數與暫存器的區域，通常是此函式被推入 (push) 到 stack 中頂端的位址，不過，確切的行為需要視硬體處理器 (如 x86 vs. RISC) 與呼叫方式 (如 ARM 的 OABI vs. EABI) 而定，不過我們這裡只想取得傳遞給 multiply() 的參數序列，就先不思考這麼多。需要留意的是，在 GNU gcc 4.1 branch 中，__builtin_frame_address(0) 的回傳值「有時」會是錯誤的，所以筆者先使用 inline assembly 處理。筆者先進行位移的動作，以自 %ebp 後方取得參數列表，在不參照參數個數的情況下，筆者用投機的途徑來判斷，因為代入者都是小整數序列，基本上只要確定是否落在合理範圍即可。以下是編譯執行的輸出：

$ gcc -xc multiply.c -O0 && ./a.out
1! =       1
2! =       2
3! =       6
4! =      24
5! =     120
6! =     720
7! =    5040
8! =   40320
9! =  362880

由可見依序將 multiply() 後方傳遞的參數取出，將其累乘得階層運算值。注意，我們必須將 gcc optimization 關掉，以避免 gcc 將參數捨棄的狀況，另外，也不能傳遞 gcc 編譯的參數 "-fomit-frame-pointer"，這會導致 %ebp 取得與前述方式不一致而無法正確執行的問題。

另外，在 NetBSD/PowerPC 上， stdarg.h 其實就是使用 __builtin_frame_address 來實做對不定個數參數的處理，參見 /usr/src/sys/arch/powerpc/include/stdarg.h 的相關宣告如下：

#define va_start(ap, last)                                              \
        (__builtin_next_arg(last),                                      \
         (ap).__stack = __va_stack_args,                                \
         (ap).__base = __va_reg_args,                                   \
         (ap).__gpr = __va_first_gpr,                                   \
         (ap).__fpr = __va_first_fpr)
 
#define __va_first_gpr  (__builtin_args_info(0))
#define __va_first_fpr  (__builtin_args_info(1) - 32 - 1)

#define __va_stack_args                                                 \
        ((char *)__builtin_saveregs() +                                 \
         (__va_first_gpr >= 8 ? __va_first_gpr - 8 : 0) * sizeof(int))
#define __va_reg_args                                                   \
        ((char *)__builtin_frame_address(0) + __builtin_args_info(4))

不過，NetBSD 與 GNU/Linux 對 gcc 處理的更迭，現已用不同的方式封裝，但原理還是一致的。
由 jserv 發表於 June 25, 2008 01:33 PM