栈是计算机科学里最重要且最基础的数据结构之一。[1]
从技术上说,栈就是CPU寄存器里的某个指针所指向的一片内存区域。这里所说的“某个指针”通常位于x86/x64平台的ESP寄存器/RSP寄存器,以及ARM平台的SP寄存器。
操作栈的最常见的指令是PUSH和POP,在x86和ARM Thumb模式的指令集里都有这两条指令。PUSH指令会对ESP/RSP/SP寄存器的值进行减法运算,使之减去4(32位)或8(64位),然后将操作数写到上述寄存器里的指针所指向的内存中。
POP指令是PUSH指令的逆操作:它先从栈指针(Stack Pointer,上面三个寄存器之一)指向的内存中读取数据,用以备用(通常是写到其他寄存器里),然后再将栈指针的数值加上4或8。
在分配栈的空间之后,栈指针,即Stack Pointer所指向的地址是栈的底部。PUSH将减少栈指针的数值,而POP会增加它的数值。栈的“底”实际上使用的是整个栈的最低地址,即是整个栈的启始内存地址。虽然听起来很奇怪,但是实际上确实如此。
虽然x86/x64的栈已经很难理解了,但是ARM的栈却更为复杂。ARM的栈分为递增栈和递减栈。递减栈(descending stack)的首地址是栈的最高地址,栈向低地址增长,栈指针的值随栈的增长而减少,如STMFD/LDMFD、STMED/LDMED等指令都是递减栈的操作指令。而ARM的递增栈(ascending stack)的首地址则占用栈的最低地址,栈向高地址增长,栈指针的值随栈的增长而增加,如STMFA/LMDFA、STMEA/LDMEA等指令都是递增栈的操作指令。[2]
多数人想象中的“增长”,是栈从低地址位向高地址位增长,似乎这样才符合自然规律。然而研究过栈的人知道,多数的栈是逆增长的,它会从高地址向低地址增长。
这多数还得归功于历史原因。当计算机尚未小型化的时候,它还有数个房间那么大。在那个时候,内存就分为两个部分,即“堆/heap”和“栈/stack”。当然,在程序执行过程中,堆和栈到底会增长到什么地步并不好说,所以人们干脆把它们分开:
有兴趣的读者可以查阅参考文献RT74,其中有这样一段话:
程序镜像(进程)在逻辑上分为 3 个段。从虚拟地址空间的 0 地址位开始,第一个段是文本段(也称为代码段)。文本段在执行过程中不可写,即使一个程序被执行多次,它也必须共享 1 份文本段。在程序虚拟空间中,文本段 8k bytes 边界之上,是不共享的、可写的数据段。程序可以通过调用系统函数调整其数据段的大小。栈启始于虚拟地址空间的最高地址,它应随着硬件栈指针的变化而自动地向下增长。
这就好比用同一个笔记本给两门课程做笔记:第一门的笔记可以按照第一页往最后一页的顺序写;然而在做第二门的笔记时,笔记本要反过来用,也就是要按照从最后一页往第一页的顺序写笔记。至于笔记本什么时候会用完,那就要看笔记本有多厚了。
x86
当程序使用call指令调用其他函数时,call指令结束后的返回地址将被保存在栈里;在call所调用的函数结束之后,程序将执行无条件跳转指令,跳转到这个返回地址。
CALL指令等价于“PUSH 返回地址”和“JMP 函数地址”的指令对。
被调用函数里的RET指令,会从栈中读取返回地址,然后跳转到这个地址,就相当于“POP 返回地址”+“JMP 返回地址”指令。
栈是有限的,溢出它很容易。直接使用无限递归,栈就会满:
void f()
{
f();
}
如果使用MSVC 2008编译上面的问题程序,将会得到报告:
c:\tmp6>cl ss.cpp /Fass.asm
Microsoft (R) 32-bit C/C++ Optimizing Compiler Version 15.00.21022.08 for 80x86
Copyright (C) Microsoft Corporation. All rights reserved.
ss.cpp
c:\tmp6\ss.cpp(4) : warning C4717:’f’ : recursive on all control paths. Function will cause runtime stack overflow
但是它还是会老老实实地生成汇编文件:
?f@@YAXXZ PROC ; f
; File c:\tmp6\ss.cpp
; Line 2
Push ebp
mov ebp, esp
; Line 3
call ?f@@YAXXZ ; f
; Line 4
pop ebp
ret 0
?f@@YAXXZ ENDP ; f
有趣的是,如果打开优化选项“/Ox”,生成的程序反而不会出现栈溢出的问题,而且还会运行得很“好”:
?f@@YAXXZ PROC ; f
; File c:\tmp6\ss.cpp
; Line 2
$LL3@f:
; Line 3
jmp SHORT $LL3@f
?f@@YAXXZ ENDP ; f
无论是否开启优化选项,GCC 4.4.1生成的代码都和MSVC生成的代码相似,只是GCC不会发布任何警告。
ARM
ARM程序也使用栈保存返回地址,只是略有不同。在3.4节中,我们看到“Hello, World!”程序的返回地址保存在LR (link register)寄存器里。但是,如果程序还会继续调用其他函数,就需要在调用函数之前保存LR寄存器的值。通常,函数会在启动过程中(序言处)保存LR寄存器的值。我们通常在函数序言处看到“PUSH R4-R7,LR”,并在尾声处看到“POP R4-R7,PC”。这些指令会对函数自身将要用到的寄存器进行保护,把它们的值存放在栈中——当然,这其中也包括LR寄存器。
如果一个函数不调用其他函数,它就像树上的枝杈末端的叶子那样。这种函数就叫作“叶函数(leaf function)”[3]。叶函数的特点是,它不必保存LR寄存器的值。如果叶函数的代码短到用不到几个寄存器,那么它也可能根本不会使用数据栈。所以,调用叶函数的时候确实可能不会涉及栈操作。这种情况下,因为这种代码不在外部内存RAM进行与栈有关的操作,所以它的运行速度有可能超过x86系统[4]。在没有分配栈或者不可能用栈的时候,这类函数就会显现出“寸有所长”的优势。
本书介绍了很多的叶函数。请参见8.3.2节、8.3.3节、15.2节、15.4节、17.3节、19.5.4节、19.17节、19.33节中演示的程序。
在x86平台的程序中,最常用的参数传递约定是cdecl[5]。以cdecl方式处理参数,其上下文大体是这个样子:
push arg3
push arg2
push arg1
call f
add esp, 12; 4*3=12
被调用方函数(Callee functions)通过栈指针获取其所需的参数。
在运行f()函数之前,传递给它的参数将以以下格式存储在内存里。
ESP
|
返回地址
|
ESP+4 | arg1, 它在IDA里记为arg_0 |
ESP+8 | arg2, 它在IDA里记为arg_4 |
ESP+0xC | arg3, 它在IDA里记为arg_8 |
…… | …… |
本书第64章将会详细介绍有关的调用约定(Calling conventions)。需要注意的是,程序员可以使用栈来传递参数,也可以不使用栈传递参数。参数处理方面并没有相关的硬性规定。
例如,程序员可以在堆(heap)中分配内存并用之传递参数。在堆中放入参数之后,可以利用EAX寄存器为函数传递参数。这种做法确实行得通。[6]只是在x86系统和ARM系统上,使用栈处理参数已经成为了约定俗成的习惯,而且它的确十分方便。
另外,被调用方函数并不知晓外部向它传递了多少个参数。如果函数可处理的参数数量可变,它就需要说明符(多数以%号开头)进行格式化说明、明确参数信息。拿我们常见的printf()函数来说:
printf("%d %d %d", 1234);
这个命令不仅会让printf()显示1234,而且还会让它显示数据栈内1234之后的两个地址的随机数。
由此可知,声明main()函数的方法并不是那么重要。我们可以将之声明为main(),main(int argc, char *argv[])或main(int argc, char *argv[], char *envp[])。
实际上CRT中调用main()的指令大体上是下面这个样子的。
push envp
push argv
push argc
call main
…
即使我们没有在程序里声明main()函数使用哪些参数,程序还可以照常运行;参数依旧保存在栈里,只是不会被主函数调用罢了。如果将main()函数声明为main(int argc, char*argv[]),程序就能够访问到前两个参数,但仍然无法使用第三个参数。除此以外,也可以声明为main( int argc),主函数同样可以运行。
通过向栈底调整栈指针(stack pointer)的方法,函数即可在数据栈里分配出一片可用于存储局部变量的内存空间。可见,无论函数声明了多少个局部变量,都不影响它分配栈空间的速度。
虽然您的确可以在栈以外的任何地方存储局部变量,但是用数据栈来存储局部变量已经是一种约定俗成的习惯了。
alloca()函数很有特点。[7]
大体来说,alloca()函数直接使用栈来分配内存,除此之外,它与malloc()函数没有显著的区别。
函数尾声的代码会还原ESP的值,把数据栈还原为函数启动之前的状态,直接抛弃由alloca()函数分配的内存。所以,程序不需要特地使用free()函数来释放由这个函数申请的内存。
alloca() 函数的实现方法至关重要。
简要地说,这个函数将以所需数据空间的大小为幅度、向栈底调整ESP的值,此时ESP就成为了新的数据空间的指针。我们一起做个试验:
#ifdef __GNUC__
#include <alloca.h> // GCC
#else
#include <malloc.h> // MSVC
#endif
#include <stdio.h>
void f()
{
char *buf=(char*)alloca (600);
#ifdef __GNUC__
snprintf (buf, 600, "hi! %d, %d, %d\n", 1, 2, 3); // GCC
#else
_snprintf (buf, 600, "hi! %d, %d, %d\n", 1, 2, 3); // MSVC
#endif
puts (buf);
}
snprintf()函数的功能和 printf()函数的功能差不多。printf()将输出结果输出到 stdout(也就是终端terminal或console一类的输出设备上),而snprintf()则将结果输出到buf数组(人工设定的缓冲区)、我们需要通过puts()函数才能将buf的内容输出到stdout。当然,printf()函数就足以完成_snprint()和puts()两个函数的功能。本文意在演示缓冲区的用法,所以刻意把它拆分为2个函数。
MSVC
现在使用MSVC 2010编译上面的代码,得到的代码段如下所示。
指令清单5.1 MSVC 2010
...
mov eax, 600 ; 00000258H
call __alloca_probe_16
mov esi, esp
push 3
push 2
push 1
push OFFSET $SG2672
push 600 ; 00000258H
push esi
call __snprintf
push esi
call _puts
add esp, 28 ; 0000001cH
...
由于alloca()函数是编译器固有函数(参见本书第90章),并非常规函数的缘故,这个程序没有使用栈,而是使用EAX寄存器来传递alloca()函数唯一的参数。在调用alloca()函数之后,ESP将指向600字节大小的内存区域,用以存储数组buf。
GCC Intel语体
在编译上述代码时,GCC 4.4.1 同样不会调用外部函数。
指令清单5.2 GCC 4.7.3
.LC0:
.string "hi! %d, %d, %d\n"
f:
push ebp
mov ebp, esp
push ebx
sub esp, 660
lea ebx, [esp+39]
and ebx, -16 ; align pointer by 16-bit border
mov DWORD PTR [esp], ebx ; s
mov DWORD PTR [esp+20], 3
mov DWORD PTR [esp+16], 2
mov DWORD PTR [esp+12], 1
mov DWORD PTR [esp+8], OFFSET FLAT:.LC0 ; "hi! %d, %d, %d\n"
mov DWORD PTR [esp+4], 600 ; maxlen
call _snprintf
mov DWORD PTR [esp], ebx ; s
call puts
mov ebx, DWORD PTR [ebp-4]
leave
ret
GCC+ AT&T语体
接下来让我们看看AT&T语体的指令。
指令清单5.3 GCC 4.7.3
.LC0:
.string "hi! %d, %d, %d\n"
f:
pushl %ebp
movl %esp, %ebp
pushl %ebx
subl $660, %esp
leal 39(%esp), %ebx
andl $-16, %ebx
movl %ebx, (%esp)
movl $3, 20(%esp)
movl $2, 16(%esp)
movl $1, 12(%esp)
movl $.LC0, 8(%esp)
movl $600, 4(%esp)
call _snprintf
movl %ebx, (%esp)
call puts
movl -4(%ebp), %ebx
leave
ret
它与Intel 语体的代码没有实质区别。
其中,“movl $3, 20(%esp)”对应Intel语体的“mov DWORD PTR [esp+20], 3”指令。在以“寄存器+偏移量”的方式寻址时,AT&T语体将这个寻址表达式显示为“偏移量(%寄存器)”。
如果程序里存在SEH记录,那么相应记录会保存在栈里。
本书将在68.3节里进行更详细的介绍。
本书将在18.2节里进行更详细的介绍。
在32位系统中,在程序调用函数之后、执行它的第一条指令之前,栈在内存中的存储格式一般如下表所示。
… | …… |
ESP-0xC | 第2个局部变量,在IDA里记为var_8 |
ESP-8 | 第1个局部变量,在IDA里记为var_4 |
ESP-4 | 保存的EBP值 |
ESP | 返回地址 |
ESP+4 | arg1, 在IDA里记为arg_0 |
ESP+8 | arg2, 在IDA里记为arg_4 |
ESP+0xC | arg3, 在IDA里记为arg_8 |
… | …… |
本书会经常使用“噪音”、“脏数据”这些词汇。它们怎么产生的呢?待函数退出以后,原有栈空间里的局部变量不会被自动清除。它们就成为了栈的“噪音”、“脏数据”。我们来看下面这段代码。
#include <stdio.h>
void f1()
{
int a=1, b=2, c=3;
};
void f2()
{
int a, b, c;
printf ("%d, %d, %d\n", a, b, c);
};
int main()
{
f1();
f2();
};
使用MSVC 2010编译后可得到如下所示的代码。
指令清单5.4 Non-optimizing MSVC 2010
$SG2752 DB '%d, %d, %d', 0aH, 00H
_c$ = -12 ; size = 4
_b$ = -8 ; size = 4
_a$ = -4 ; size = 4
_f1 PROC
push ebp
mov ebp, esp
sub esp, 12
mov DWORD PTR _a$[ebp], 1
mov DWORD PTR _b$[ebp], 2
mov DWORD PTR _c$[ebp], 3
mov esp, ebp
pop ebp
ret 0
_f1 ENDP
_c$ = -12 ; size = 4
_b$ = -8 ; size = 4
_a$ = -4 ; size = 4
_f2 PROC
push ebp
mov ebp, esp
sub esp, 12
mov eax, DWORD PTR _c$[ebp]
push eax
mov ecx, DWORD PTR _b$[ebp]
push ecx
mov edx, DWORD PTR _a$[ebp]
push edx
push OFFSET $SG2752 ; ’%d, %d, %d’
call DWORD PTR __imp__printf
add esp, 16
mov esp, ebp
pop ebp
ret 0
_f2 ENDP
main PROC
push ebp
mov ebp, esp
call _f1
call _f2
xor eax, eax
pop ebp
ret 0
_main ENDP
编译器会给出提示:
c:\Polygon\c>cl st.c /Fast.asm /MD
Microsoft (R) 32-bit C/C++ Optimizing Compiler Version 16.00.40219.01 for 80x86
Copyright (C) Microsoft Corporation. All rights reserved.
st.c
c:\polygon\c\st.c(11) : warning C4700: uninitialized local variable 'c' used
c:\polygon\c\st.c(11) : warning C4700: uninitialized local variable 'b' used
c:\polygon\c\st.c(11) : warning C4700: uninitialized local variable 'a' used
Microsoft (R) Incremental Linker Version 10.00.40219.01
Copyright (C) Microsoft Corporation. All rights reserved.
/out:st.exe
st.obj
可是运行它的结果却是:
c:\Polygon\c>st
1, 2, 3
天,真奇怪!虽然我们没有给f2()的任何变量赋值,但是变量自己有自己的值。f2()函数的值就是栈里残存的脏数据。
我们使用OllyDbg打开这个程序,如图5.1所示。
图5.1 使用OllyDbg查看f1()函数的数据栈
在f1()函数给变量a、b、c赋值后,数值存储于0x1FF860开始的连续地址里。
然后,在执行f2()时,情况如图5.2所示。
图5.2 使用OllyDbg查看f2()函数的数据栈
f2()函数的三个变量的地址,和f1()函数的三个变量的地址相同。因为没有对这个空间进行重新赋值,所以那三个变量会因为地址相同的原因获得前三个变量的值。
在这个特例里,第二个函数在第一个函数之后执行,而第二个函数变量的地址和SP的值又与第一个函数的情况相同。所以,相同地址的变量获得的值相同。
总而言之,在运行第二个函数时,栈中的所有值(即内存中的单元)受前一个函数的影响,而获得了前一个函数的变量的值。严格地说,这些地址的值不是随机值,而是可预测的伪随机值。
有没有办法清除脏数据呢?我们可以在每个函数执行之前清除其开辟的栈空间的数据。不过,即使这是一种技术上可行的方法,但是因为这种方法开销太大、而且必要性很低,所以没有人这样做。
如果使用MSVC编译、运行下列程序,将会打印出3个整数。这些数值来自哪里?如果使用MSVC的优化选项“/Ox”,程序又会在屏幕上输出什么?为什么GCC的情况完全不同?
#include <stdio.h>
int main()
{
printf ("%d, %d, %d\n");
return 0;
};
答案请参见G1.1。
请问描述下述程序的功能。
经MSVC 2010(启用/Ox选项)编译而得的代码如下。
指令清单5.5 Optimizing MSVC 2010
$SG3103 DB '%d', 0aH, 00H
_main PROC
push 0
call DWORD PTR __imp___time64
push edx
push eax
push OFFSET $SG3103 ; ’%d’
call DWORD PTR __imp__printf
add esp, 16
xor eax, eax
ret 0
_main ENDP
指令清单5.6 经Keil 6/2013(启用优化选项)编译而得的ARM模式代码
main PROC
PUSH {r4,lr}
MOV r0,#0
BL time
MOV r1,r0
ADR r0,|L0.32|
BL __2printf
MOV r0,#0
POP {r4,pc}
ENDP
|L0.32|
DCB "%d\n",0
指令清单5.7 经Keil 6/2013(启用优化选项)编译而得的Thumb模式代码
main PROC
PUSH {r4,lr}
MOVS r0,#0
BL time
MOVS r1,r0
ADR r0,|L0.20|
BL __2printf
MOVS r0,#0
POP {r4,pc}
ENDP
|L0.20|
DCB "%d\n",0
指令清单5.8 经GCC 4.9(启用优化选项)编译而得的ARM64模式代码
main:
stp x29, x30, [sp, -16]!
mov x0, 0
add x29, sp, 0
bl time
mov x1, x0
ldp x29, x30, [sp], 16
adrp x0, .LC0
add x0, x0, :lo12:.LC0
b printf
.LC0:
.string "%d\n"
指令清单5.9 经GCC 4.4.5(启用优化选项)编译而得的MIPS指令(IDA)
main:
var_10 = -0x10
var_4 = -4
lui $gp, (__gnu_local_gp >> 16)
addiu $sp, -0x20
la $gp, (__gnu_local_gp & 0xFFFF)
sw $ra, 0x20+var_4($sp)
sw $gp, 0x20+var_10($sp)
lw $t9, (time & 0xFFFF)($gp)
or $at, $zero
jalr $t9
move $a0, $zero
lw $gp, 0x20+var_10($sp)
lui $a0, ($LC0 >> 16) # "%d\n"
lw $t9, (printf & 0xFFFF)($gp)
lw $ra, 0x20+var_4($sp)
la $a0, ($LC0 & 0xFFFF) # "%d\n"
move $a1, $v0
jr $t9
addiu $sp, 0x20
$LC0: .ascii "%d\n"<0> # DATA XREF: main+28
[1] 请参见http://en.wikipedia.org/wiki/Call_stack。
[2] 这些指令所对应的英文全称,分别是Store Multiple Full Descending、Load Multiple Full Descending、Store Multiple Empty Descending、Load Multiple Empty Descending 、Store Multiple Full Ascending 、Load Multiple Full Ascending 、Store Multiple Empty Ascending、 Load Multiple Empty Ascending。其中的Full/Empty的区别在于:如果指针指向的地址是最新操作的值,那么它就是Full stack;而指针指向的地址没有值、是下一个值将写到的地址,那么这个栈就是Empty stack。
[3] 参照http://infocenter.arm.com/help/index.jsp?topic=/com.arm.doc.faqs/ka13785.html。部分文献又称叶函数为“末端函数”
[4] 多年以前,在PDP-11和VAX平台上,调用函数的指令效率很低;在运行程序的时候,差不多近半的耗时都花在互相调用的指令上。以至于当时普遍认为、“大规模调用功能较少的函数”的程序就是垃圾程序。
[5] 此外还有stdcall、fastcall、thiscall等。Windows上很多程序使用stdcall。
[6] Donald Knuth在《The Art of Computer Programming》 一书的14.1节专门介绍了子程序。读者能够发现他提到了一种方法,通过JMP跳转到子程序并在子程序的入口处即刻提取所需参数。Knuth的这种方法在System/360上非常实用。
[7] 在MSVC编译环境里,它的实现方式可在目录C:\Program Files (x86)\Microsoft Visual Studio 10.0\VC\crt\src\intel下的alloca16.asm和chkstk.asm中找到。