在计算机编程方面的教科书里,我们通常都能找到Fibonacci数列(斐波拉契数列)(以下简称为“Fibonacci”)的生成函数。其实这种数列编排的规则非常简单:从第三项开始,后续数字为前两项数字之和。头两项一般为0和1;也有头两项都是1的情况。因此,常见的Fibonacci数列大致如下:
0; 1; 1; 2; 3; 5; 8; 13; 21; 34; 55; 89; 144; 233; 377; 610; 987; 1597; 2584; 4181…
Fibonacci的实现方法比较简单。举例来说,下面这个程序可以生成数值不超过21的数列各项:
#include <stdio.h>
void fib (int a, int b, int limit)
{
printf ("%d\n", a+b);
if (a+b > limit)
return;
fib (b, a+b, limit);
};
int main()
{
printf ("0\n1\n1\n");
fib (1, 1, 20);
};
指令清单36.1 MSVC 2010 x86
_TEXT SEGMENT
_a$ = 8 ; size = 4
_b$ = 12 ; size = 4
_limit$ = 16 ; size = 4
_fib PROC
push ebp
mov ebp, esp
mov eax, DWORD PTR _a$[ebp]
add eax, DWORD PTR _b$[ebp]
push eax
push OFFSET $SG2750 ; "%d"
call DWORD PTR __imp__printf
add esp, 8
mov ecx, DWORD PTR _limit$[ebp]
push ecx
mov edx, DWORD PTR _a$[ebp]
add edx, DWORD PTR _b$[ebp]
push edx
mov eax, DWORD PTR _b$[ebp]
push eax
call _fib
add esp, 12
pop ebp
ret 0
_fib ENDP
_main PROC
push ebp
mov ebp, esp
push OFFSET $SG2753 ; "0\n1\n1\n"
call DWORD PTR __imp__printf
add esp, 4
push 20
push 1
push 1
call _fib
add esp, 12
xor eax, eax
pop ebp
ret 0
_main ENDP
我们重点分析这个程序的栈结构。
我们在OllyDbg中加载本例生成的可执行程序,并跟踪到调用f()函数的那条指令,如图36.1所示。
图36.1 OllyDbg最后一个函数f()
让我们来仔细分析栈里的内容。在下面的程序行中,笔者用打括弧的方法加了两个注释。一个是main()为f1()做准备,另外一个是CRT为main()做准备[1]。
0035F940 00FD1039 RETURN to fib.00FD1039 from fib.00FD1000
0035F944 00000008 1st argument: a
0035F948 0000000D 2nd argument: b
0035F94C 00000014 3rd argument: limit
0035F950 /0035F964 saved EBP register
0035F954 |00FD1039 RETURN to fib.00FD1039 from fib.00FD1000
0035F958 |00000005 1st argument: a
0035F95C |00000008 2nd argument: b
0035F960 |00000014 3rd argument: limit
0035F964 ]0035F978 saved EBP register
0035F968 |00FD1039 RETURN to fib.00FD1039 from fib.00FD1000
0035F96C |00000003 1st argument: a
0035F970 |00000005 2nd argument: b
0035F974 |00000014 3rd argument: limit
0035F978 ]0035F98C saved EBP register
0035F97C |00FD1039 RETURN to fib.00FD1039 from fib.00FD1000
0035F980 |00000002 1st argument: a
0035F984 |00000003 2nd argument: b
0035F988 |00000014 3rd argument: limit
0035F98C ]0035F9A0 saved EBP register
0035F990 |00FD1039 RETURN to fib.00FD1039 from fib.00FD1000
0035F994 |00000001 1st argument: a
0035F998 |00000002 2nd argument: b
0035F99C |00000014 3rd argument: limit
0035F9A0 ]0035F9B4 saved EBP register
0035F9A4 |00FD105C RETURN to fib.00FD105C from fib.00FD1000
0035F9A8 |00000001 1st argument: a \
0035F9AC |00000001 2nd argument: b | prepared in main() for f1()
0035F9B0 |00000014 3rd argument: limit /
0035F9B4 ]0035F9F8 saved EBP register
0035F9B8 |00FD11D0 RETURN to fib.00FD11D0 from fib.00FD1040
0035F9BC |00000001 main() 1st argument: argc \
0035F9C0 |006812C8 main() 2nd argument: argv | prepared in CRT for main()
0035F9C4 |00682940 main() 3rd argument: envp /
本例属于递归函数[2]。递归函数的栈一般都是这样的“三明治”结构。在上述程序中,limit(阈值)参数总是保持不变(十六进制的14,也就是十进制的20),而两个参数a和b在每次调用函数的时候都是不同的值。此外栈也存储了RA和保存EBP(扩展堆栈指针)的值。OllyDbg能基于EBP的值判断栈的存储结构,因此它能够用括弧标注栈帧。换而言之,在每个括弧里的一组数值都形成了一个相对独立的栈结构,即栈帧(stack frame)。栈帧就是每次函数调用期间的数据实体。另一方面,即使从纯萃技术方面看每个被调用方函数确实可以访问栈帧之外的栈存储空间,但是正常情况下不应当访问栈帧之外的数据(当然除了获取函数参数的操作以外)。对于没有bug(缺陷)的函数来说,上述命题的确成立。每一个 EBP值都是前一个栈帧的地址。因此调试程序能够把数据栈识别为栈帧,并能识别出每次调用函数时传递的参数值。
结合上述指令可知,递归函数应当为下一轮的自身调用制备各项参数。
在程序的最后部分,main()有3个参数。其中argc(参数总数)为1。确实如此,笔者的确未带参数直接运行并调试本程序。
另外,调整本程序、引发栈溢出的过程并不复杂:我们只需要删除或者注释掉阈值limit判断语句,即可导致栈溢出(即错误编号为0xC00000FD的异常错误)。
上一节的函数有些冗余。接下来,我们增加一个新的局部变量next,并用它来代替所有程序中的a+b:
#include <stdio.h>
void fib (int a, int b, int limit)
{
int next=a+b;
printf ("%d\n", next);
if (next > limit)
return;
fib (b, next, limit);
};
int main()
{
printf ("0\n1\n1\n");
fib (1, 1, 20);
};
这是非优化MSVC的输出,因此next变量确实是在本地栈中分配存储空间。
指令清单36.2 MSVC 2010 x86
_next$ = -4 ; size = 4
_a$ = 8 ; size = 4
_b$ = 12 ; size = 4
_limit$ = 16 ; size = 4
_fib PROC
push ebp
mov ebp, esp
push ecx
mov eax, DWORD PTR _a$[ebp]
add eax, DWORD PTR _b$[ebp]
mov DWORD PTR _next$[ebp], eax
mov ecx, DWORD PTR _next$[ebp]
push ecx
push OFFSET $SG2751 ; '%d'
call DWORD PTR __imp__printf
add esp, 8
mov edx, DWORD PTR _next$[ebp]
cmp edx, DWORD PTR _limit$[ebp]
jle SHORT $LN1@fib
jmp SHORT $LN2@fib
$LN1@fib:
mov eax, DWORD PTR _limit$[ebp]
push eax
mov ecx, DWORD PTR _next$[ebp]
push ecx
mov edx, DWORD PTR _b$[ebp]
push edx
call _fib
add esp, 12
$LN2@fib:
mov esp, ebp
pop ebp
ret 0
_fib ENDP
_main PROC
push ebp
mov ebp, esp
push OFFSET $SG2753 ; "0\n1\n1\n"
call DWORD PTR __imp__printf
add esp, 4
push 20
push 1
push 1
call _fib
add esp, 12
xor eax, eax
pop ebp
ret 0
_main ENDP
我们再来调用OllyDbg,如图36.2所示。
图36.2 OllyDbg: 最后调用f()
现在,每个栈帧里都有一个变量next。
我们来仔细看看堆栈。笔者依然给其中增加了注释。
0029FC14 00E0103A RETURN to fib2.00E0103A from fib2.00E01000
0029FC18 00000008 1st argument: a
0029FC1C 0000000D 2nd argument: b
0029FC20 00000014 3rd argument: limit
0029FC24 0000000D "next" variable
0029FC28 /0029FC40 saved EBP register
0029FC2C |00E0103A RETURN to fib2.00E0103A from fib2.00E01000
0029FC30 |00000005 1st argument: a
0029FC34 |00000008 2nd argument: b
0029FC38 |00000014 3rd argument: limit
0029FC3C |00000008 "next" variable
0029FC40 ]0029FC58 saved EBP register
0029FC44 |00E0103A RETURN to fib2.00E0103A from fib2.00E01000
0029FC48 |00000003 1st argument: a
0029FC4C |00000005 2nd argument: b
0029FC50 |00000014 3rd argument: limit
0029FC54 |00000005 "next" variable
0029FC58 ]0029FC70 saved EBP register
0029FC5C |00E0103A RETURN to fib2.00E0103A from fib2.00E01000
0029FC60 |00000002 1st argument: a
0029FC64 |00000003 2nd argument: b
0029FC68 |00000014 3rd argument: limit
0029FC6C |00000003 "next" variable
0029FC70 ]0029FC88 saved EBP register
0029FC74 |00E0103A RETURN to fib2.00E0103A from fib2.00E01000
0029FC78 |00000001 1st argument: a \
0029FC7C |00000002 2nd argument: b | prepared in f1() for next f1()
0029FC80 |00000014 3rd argument: limit /
0029FC84 |00000002 "next" variable
0029FC88 ]0029FC9C saved EBP register
0029FC8C |00E0106C RETURN to fib2.00E0106C from fib2.00E01000
0029FC90 |00000001 1st argument: a \
0029FC94 |00000001 2nd argument: b | prepared in main() for f1()
0029FC98 |00000014 3rd argument: limit /
0029FC9C ]0029FCE0 saved EBP register
0029FCA0 |00E011E0 RETURN to fib2.00E011E0 from fib2.00E01050
0029FCA4 |00000001 main() 1st argument: argc \
0029FCA8 |000812C8 main() 2nd argument: argv | prepared in CRT for main()
0029FCAC |00082940 main() 3rd argument: envp /
这里我们看到:递归函数在每次调用期间都会计算并传递下一轮调用所需的函数参数。
递归函数只是看起来很帅而已。从技术上讲,递归函数在栈方面的开销过大,因而性能不怎么理想。注重性能指标的应用程序,应当避免使用递归函数。
笔者曾经编写过一个遍历二叉树、搜索既定节点的应用程序。把它写成递归函数的时候,整个程序确实又清爽又有条理性。但是每次函数调用都得进行赋值、回调,这使得递归函数比其他类型的函数慢了数倍。
另外,部分PL[3]编译器会对递归调用采取“尾部调用”的优化方法,以减轻栈的各种开销。
[1] 在OllyDbg中,可以选择多项指令,再使用Ctrl+C组合键把它们复制到剪切板中。本例就是这样做的。
[2] 也就是自己调用自己。
[3] PL:Program Language(编程语言)。LISP、Python、Lua等编程语言的编译器能够进行尾部调用优化。详情请参阅https://en. wikipedia.org/wiki/Tail_call。