第5章 栈

栈是计算机科学里最重要且最基础的数据结构之一。[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]

5.1 为什么栈会逆增长

多数人想象中的“增长”,是栈从低地址位向高地址位增长,似乎这样才符合自然规律。然而研究过栈的人知道,多数的栈是逆增长的,它会从高地址向低地址增长。

这多数还得归功于历史原因。当计算机尚未小型化的时候,它还有数个房间那么大。在那个时候,内存就分为两个部分,即“堆/heap”和“栈/stack”。当然,在程序执行过程中,堆和栈到底会增长到什么地步并不好说,所以人们干脆把它们分开:

有兴趣的读者可以查阅参考文献RT74,其中有这样一段话:

程序镜像(进程)在逻辑上分为 3 个段。从虚拟地址空间的 0 地址位开始,第一个段是文本段(也称为代码段)。文本段在执行过程中不可写,即使一个程序被执行多次,它也必须共享 1 份文本段。在程序虚拟空间中,文本段 8k bytes 边界之上,是不共享的、可写的数据段。程序可以通过调用系统函数调整其数据段的大小。栈启始于虚拟地址空间的最高地址,它应随着硬件栈指针的变化而自动地向下增长。

这就好比用同一个笔记本给两门课程做笔记:第一门的笔记可以按照第一页往最后一页的顺序写;然而在做第二门的笔记时,笔记本要反过来用,也就是要按照从最后一页往第一页的顺序写笔记。至于笔记本什么时候会用完,那就要看笔记本有多厚了。

5.2 栈的用途

5.2.1 保存函数结束时的返回地址

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节中演示的程序。

5.2.2 参数传递

在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),主函数同样可以运行。

5.2.3 存储局部变量

通过向栈底调整栈指针(stack pointer)的方法,函数即可在数据栈里分配出一片可用于存储局部变量的内存空间。可见,无论函数声明了多少个局部变量,都不影响它分配栈空间的速度。

虽然您的确可以在栈以外的任何地方存储局部变量,但是用数据栈来存储局部变量已经是一种约定俗成的习惯了。

5.2.4 x86:alloca()函数

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语体将这个寻址表达式显示为“偏移量(%寄存器)”。

5.2.5 (Windows)SEH结构化异常处理

如果程序里存在SEH记录,那么相应记录会保存在栈里。

本书将在68.3节里进行更详细的介绍。

5.2.6 缓冲区溢出保护

本书将在18.2节里进行更详细的介绍。

5.3 典型的栈的内存存储格式

在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
……

5.4 栈的噪音

本书会经常使用“噪音”、“脏数据”这些词汇。它们怎么产生的呢?待函数退出以后,原有栈空间里的局部变量不会被自动清除。它们就成为了栈的“噪音”、“脏数据”。我们来看下面这段代码。

#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所示。

..\TU\0501.tif{}

图5.1 使用OllyDbg查看f1()函数的数据栈

在f1()函数给变量abc赋值后,数值存储于0x1FF860开始的连续地址里。

然后,在执行f2()时,情况如图5.2所示。

..\TU\0502.tif{}

图5.2 使用OllyDbg查看f2()函数的数据栈

f2()函数的三个变量的地址,和f1()函数的三个变量的地址相同。因为没有对这个空间进行重新赋值,所以那三个变量会因为地址相同的原因获得前三个变量的值。

在这个特例里,第二个函数在第一个函数之后执行,而第二个函数变量的地址和SP的值又与第一个函数的情况相同。所以,相同地址的变量获得的值相同。

总而言之,在运行第二个函数时,栈中的所有值(即内存中的单元)受前一个函数的影响,而获得了前一个函数的变量的值。严格地说,这些地址的值不是随机值,而是可预测的伪随机值。

有没有办法清除脏数据呢?我们可以在每个函数执行之前清除其开辟的栈空间的数据。不过,即使这是一种技术上可行的方法,但是因为这种方法开销太大、而且必要性很低,所以没有人这样做。

5.5 练习题

5.5.1 题目1

如果使用MSVC编译、运行下列程序,将会打印出3个整数。这些数值来自哪里?如果使用MSVC的优化选项“/Ox”,程序又会在屏幕上输出什么?为什么GCC的情况完全不同?

#include <stdio.h>

int main() 
{
         printf ("%d, %d, %d\n");

         return 0;
};

答案请参见G1.1。

5.5.2 题目2

请问描述下述程序的功能。

经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中找到。