堆栈再谈

whypro

《初探缓冲区溢出》那篇文章讲了一些堆栈，另发一篇再讲讲，各位看官注意这是一个系列的。
C原程序：
主函数main()和子函数func1都定义了不同类型的局部变量, 并且子函数定义了两个以上(包括两个)的参数.
这样实例源代码可以较充分地说明各种情况。在本实例没有体现的情况, 建议另外添加代码来运行分析。

1. 
   
2. #include <stdio.h>
   
3. #include <string.h>
   
4. 
   
5. void func1(int input1, int input2)
   
6. {
   
7.         int j;
   
8.         char c;
   
9.         short k;
   
10. 
    
11.         j = 0;
    
12.         c = 'a';
    
13.         k = 1;
    
14. 
    
15.         printf("sum=%d\n", input1+input2);
    
16. 
    
17.         return;
    
18. }
    
19. 
    
20. int main()
    
21. {
    
22.         char output[8] = "abcdef";
    
23.         int i, j;
    
24. 
    
25.         i=2;
    
26.         j=3;
    
27.         func1(i,j);
    
28. 
    
29.         printf("%s\r\n", output);
    
30. 
    
31.         return 0;
    
32. }
    

复制代码

whypro

汇编代码
在VC中，按F10进入DEBUG模式。右键弹出菜单，选择“Go To Disassembly”，则显示C源程序的相应汇编代码。注意：这里的汇编代码是DEBUG模式的，与RELEASE模式的汇编代码会有所不同，但我们将要研究的问题。下面的代码完全摘自VC中，未作任何修改。由此可见，子函数存储区（低址）和主函数存储区（高址）之间还有一些空白区。函数中调用的其他库函数存储在更高的地址，具体情况在实践在查看。
……(前面省略)
1:    #include <stdio.h>
2:    #include <string.h>
3:
4:    void func1(int input1, int input2)
5:    {
00401020   push        ebp
00401021   mov         ebp,esp
00401023   sub         esp,4Ch
00401026   push        ebx
00401027   push        esi
00401028   push        edi
00401029   lea         edi,[ebp-4Ch]
0040102C   mov         ecx,13h
00401031   mov         eax,0CCCCCCCCh
00401036   rep stos    dword ptr [edi]
6:        int j;
7:        char c;
8:        short k;
9:
10:       j = 0;
00401038   mov         dword ptr [ebp-4],0
11:       c = 'a';
0040103F   mov         byte ptr [ebp-8],61h
12:       k = 1;
00401043   mov         word ptr [ebp-0Ch],offset func1+27h (00401047)
13:
14:       printf("sum=%d\n", input1+input2);
00401049   mov         eax,dword ptr [ebp+8]
0040104C   add         eax,dword ptr [ebp+0Ch]
0040104F   push        eax
00401050   push        offset string "sum=%d\n" (0042001c)
00401055   call        printf (00401130)
0040105A   add         esp,8
15:
16:       return;
17:   }
0040105D   pop         edi
0040105E   pop         esi
0040105F   pop         ebx
00401060   add         esp,4Ch
00401063   cmp         ebp,esp
00401065   call        __chkesp (004011b0)
0040106A   mov         esp,ebp
0040106C   pop         ebp
0040106D   ret
18:
19:   int main()
20:   {
00401080   push        ebp
00401081   mov         ebp,esp
00401083   sub         esp,50h
00401086   push        ebx
00401087   push        esi
00401088   push        edi
00401089   lea         edi,[ebp-50h]
0040108C   mov         ecx,14h
00401091   mov         eax,0CCCCCCCCh
00401096   rep stos    dword ptr [edi]
21:       char output[8] = "abcdef";
00401098   mov         eax,[string "abcdef" (00420f84)]
0040109D   mov         dword ptr [ebp-8],eax
004010A0   mov         cx,word ptr [string "abcdef"+4 (00420f88)]
004010A7   mov         word ptr [ebp-4],cx
004010AB   mov         dl,byte ptr [string "abcdef"+6 (00420f8a)]
004010B1   mov         byte ptr [ebp-2],dl
004010B4   xor         eax,eax
004010B6   mov         byte ptr [ebp-1],al
22:       int i, j;
23:
24:       i=2;
004010B9   mov         dword ptr [ebp-0Ch],2
25:       j=3;
004010C0   mov         dword ptr [ebp-10h],3
26:       func1(i,j);
004010C7   mov         ecx,dword ptr [ebp-10h]
004010CA   push        ecx
004010CB   mov         edx,dword ptr [ebp-0Ch]
004010CE   push        edx
004010CF   call        @ILT+0(_func1) (00401005)
004010D4   add         esp,8
27:
28:       printf("%s\r\n", output);
004010D7   lea         eax,[ebp-8]
004010DA   push        eax
004010DB   push        offset string "%s\r\n" (00420024)
004010E0   call        printf (00401130)
004010E5   add         esp,8
29:
30:       return 0;
004010E8   xor         eax,eax
31:   }
004010EA   pop         edi
004010EB   pop         esi
004010EC   pop         ebx
004010ED   add         esp,50h
004010F0   cmp         ebp,esp
004010F2   call        __chkesp (004011b0)
004010F7   mov         esp,ebp
004010F9   pop         ebp
004010FA   ret
……(后面省略)

[ 本帖最后由 whypro 于 2010-5-17 21:15 编辑 ]

whypro

跟踪与分析过程
在此过程，我们主要根据与堆栈相关的若干寄存器的变化，来跟踪栈内存区的变化。
1 栈是如何建造的?
栈是一种经典的数据结构，它遵循“先进后出”的操作特性。那么在实现栈时如何保证这种操作特性呢？我们来看一下栈的定义及相关概念。
栈的逻辑结构与线性表相同，但栈有其特殊的操作规则，所以说栈是运算受限的线性表。我们可以定义栈是限制在表的一端进行插入和删除的线性表，
允许插入/删除的一端称为栈顶，另一端称为栈底。对于插入操作称为PUSH(入栈)；删除操作称为POP(出栈)。
很明显，我们要对栈进行操作，需要且仅需要记录栈顶的位置。在Intel 80x86系统中，完成这一功能的就是寄存器ESP(Extended Stack Pointer)。
所有的PUSH/POP操作都通过它来完成，因而寄存器ESP是经常变化。
聪明的读者这时会问：如何访问非栈顶的数据呢？Intel 80x86系统中解决的办法是设置另外一个寄存器EBP(Extended Base Pointer)，我们用它来保存一个稳定不变的基准地址(基址)，
然后通过“基址+正负偏移量”的方式实现非栈顶的数据访问。也可以把EBP看作是保存栈底的位置，那么寄存EBP和ESP一起就组成一个栈。
寄存器是CPU的记忆细胞，非常重要。我们的分析也是依靠寄存器来进行的。更多的寄存器知识可以参考计算机组成原理和汇编语言的相关教程。
下面说明几个后文我们需要特别关注的Intel 80x86系统的32位寄存器。
指令地址寄存器EIP：永远保存下一步将要执行的指令的地址。在VC的调试模式下，就是
彩色箭头所在行的地址。
基址寄存器EBP：保存当前函数层的栈内存基地址，要依靠它来完成栈内存的变量寻址。
栈顶指针寄存器ESP：保存栈顶地址(指针)，系统依靠它来完成PUSH、POP操作。栈顶指
针所指向的位置是存储有效数据的。故PUSH操作是先往低址移动栈顶指针，再存储数据；
而POP操作是先读取数据，再往高址移动栈顶指针。


2 函数调用之CALL
编译好工程，按F11进入单步调试模式，并切换到Disassembly视图。接着打开Register，Memory，Call Stack窗口。最原始的寄存器状态如图1所示。下面开始跟踪和分析之旅。再次强调，在其中，要利用相关寄存器的数据来获取想得到的一切东东。

                                              图1 main()函数入口处的寄存器状态


3 CALL指令前做了什么？
如图2所示，在main()函数调用func1()函数前，还有一大堆代码，暂且不管，后文再叙。我们直接跳到调用func1()语句的地方往下看。

从上述汇编代码可以知道，执行call指令前，有两个push指令。从mov指令的操作数地址可得知，两个PUSH操作的作用是从右向左把子函数func1()的参数j,i先后入栈。这里的参数入栈顺序涉及到一个知识点：调用约定(Calling Convention)，它决定了函数调用时如何传递函数参数以及由此而产生的其他操作的规则。高级语言中常用的调用约定有__stdcall、__cdecl、__pascal、__fastcall、thiscall、naked call等。C语言默认的调用约定是__cdecl，本文讨论的也遵循这种调用约定。更具体的内容参阅相关资料。
在函数参数入栈过程中，需要关注寄存器esp的变化和对应栈内存的修改。完成参数入栈后寄存器状态如图3所示。

                                                        图2 func1()调用前的寄存器状态


4 CALL指令中做了什么？
在完成参数入栈后，执行call指令，寄存器状态如图3所示。大家注意到了吗？与图2对比，可看出寄存ESP往低址偏移了4字节，说明其中执行了一个PUSH操作。查看寄存器ESP对应的内存地址的值：0x004010C4，此地址刚好是call指令后续第一条指令的地址。

可为什么没有看到push指令呢？原来在CALL操作中，隐式地把call指令后续第一条指令的地址0x004010C4入栈，然后再无条件地跳转到func1()函数继续执行。
大家是否奇怪call指令的操作数。从图3可以看到，func1()函数的入口地址是0x00401020，那么call指令的操作数就应该是0x00401020，可现在却是一个乱七八糟的东西，还带了莫明其妙的标识符@ILT。
ILT是什么，@ILT又是什么？
在DEBUG版本中，VC汇编程序会产生一个函数跳转指令表，该表的每个表项存放一个函数的跳转指令。程序中的函数调用就是利用这个表来实现跳转到相应函数的入口地址。

ILT就是函数跳转指令表的名称，是Import Lookup Table的缩写；@ILT就是函数跳转指令表的首地址。在DEBUG版本中增加函数跳转指令表，其目的是加快编译速度，当某函数的地址发生变化时，只需要修改ILT相应表项即可，而不需要修改该函数的每一处引用。
注意：在RELEASE版本中，不会生成ILT，也就是说call指令的操作数直接是函数的入口地址，例如在本例中是这样的：call 00401020

                                                     图3 func1调用后的寄存器状态
5 函数入口做了什么？
到此，程序已经运行到子函数func1()了。此时的寄存器状态如图4所示，我们来看看func1()在入口处作了些什么处理。
首先是把main()函数层的栈内存基地址(由寄存器ebp指示)入栈保存起来。同时把当前的栈顶地址(由寄存器esp指示)作为func1()函数层的栈内存基地址，即更新寄存器ebp为寄存器esp。此时两者相等，留神吧，后文会对此大做文章呢!


然后，栈顶指针esp向低地址偏移76(0x4C)字节。这里相当于为func1()函数层分配了栈内存。

1. 00401023 sub esp 4ch

复制代码

接着把寄存器ebx,esi,sdi依次入栈保存，即保存main()函数层的上下文。

1. 00401026 push ebx
   
2. 00401027 push esi
   
3. 00401028 push edi

复制代码

最后用0xCC初始化上述为func1()函数层所分配的栈内存的每个字节。这里每一步用F11单步跟踪，栈内存的变化你会看得更清楚。

1. 00401029 lea  edi,[ebp-4ch]
   
2. 0040102c mov  ecx,13h
   
3. 00401031 mov  eax,0cccccccch
   
4. 00401036 rep stos dword ptr [edi]

复制代码

完成入口处理后的寄存器状态如图5所示。
大家是否注意到func1()只定义了三个变量j、c、k，在32位系统中只需要7(=4+1+2)字节，可实际却分配了76个字节。即使考虑到四字节对齐的原因(从后文来看，系统确实也考虑了这一点)，三个变量也只需要12(=4+4+4)个字节，也就是说系统额外预留了64(=76-12)个字节，为什么要预留额外空间，为什么额外空间是64，而不是32，或其他数目？
嗯，预留栈空间是为了防止栈溢出。而对于为什么是64?#@#@$@%&*%$#@我也不知道。

图4 func1()函数入口处理前的寄存器状态

图5 func1()入口处理后的寄存器状态


6 栈变量如何寻址？
接下来，我们看一下是如何读写函数内的局部变量以及函数的入口参数的。在前文2小节我们知道func1()函数参数是PUSH入栈了，为什么在func1()函数内部没有看到POP出栈呢？
如图6所示，从汇编代码我们可以看出,对栈变量的寻址是通过“ebp+偏移量”来完成的，即以寄存器ebp为基点，若访问局部变量则向低址方向偏移(减)；若访问入口参数则向高址方向偏移(加)。

                                          图6 func1()内读写栈数据
大家是否注意到，虽然局部变量c是char类型，只占一个字节，但实际上分配了4个字节，这是要求四字节对齐导致的，由编译器自动完成。变量k同理。这里也证实了4.2.4小节有关栈内存分配的考虑。
7 栈也分层？
我们再回头看看main()函数。其入口处的汇编代码是否似曾相识？不，简直，根本就是与func1()函数入口处的汇编代码一样。也就是说main()函数入口也完成了保存当前寄存器ebp，更新寄存器ebp，分配/初始化栈内存，保存上下文等一系列操作。
这并不奇怪，main()函数虽然是C程序的执行入口点，但对于OS来说，它也是作为一个子函数被OS调用的，所以也存在我们讨论的子函数调用所涉及的一切堆栈操作。因此，也就不难想像，对于多层函数调用的情况下，以每层的ebp为分界线，那么栈也有清晰的层次结构了。动手编写一个多层调用的源程序，把其中的栈结构画出来，栈将不再神秘！
这里我们顺便讨论另一个知识点：字符串数组及其赋值。C语言定义字符串数组并初始化只用了一条语句
char output[8] = "abcdef";
但对应了8条汇编语句。如图7所示, 字符串“abcdef”并不直接存放在栈内存区，而在高址的全局数据内存区有相应的内存空间0x00420F84。从相应的8条汇编指令可以看出，对局部字符数组变量（栈变量）赋值，是利用寄存器从上述数据内存区把字符串“abcdef”拷贝到栈内存中，如图8所示。即使从函数中返回，数据内存区的字符串“abcdef”也不会被销毁，但程序也访问不了。

图7 字符串常量存放在全局数据区

图8 局部字符串数组赋值
8 函数调用之RET
与call指令相对的是ret指令。下面我们看看是如何完成返回到main()函数的。
9 函数出口做了什么？
如图9所示，一条return语句对应着9条汇编指令，最后一条是ret指令。那么ret指令前那些指令是做什么的呢？

图9 func1()函数出口处理前的寄存器状态
细心的读者可能已经注意到此时寄存器ebp、esp状态与func1()函数入口处理完后的状态一致(如图5所示)。是的，是时候退出func1()函数返回到main()函数了，一切准备就绪，只欠行动。
首先依次出栈恢复寄存器edi、esi、ebx，即恢复main()函数层的上下文；

1. 0040105d pop edi
   
2. 0040105e pop esi
   
3. 0040105f pop ebx

复制代码

然后栈顶指针往高址偏移76(0x4C)字节，即释放入口处分配的func1()函数的栈内存；

1. 00401060 add esp,4ch

复制代码

      最后出栈恢复寄存器ebp、esp。

1. 
   
2. 0040106a mov esp,ebp
   
3. 0040106c pop ebp
   

复制代码

从上述过程来看，完全是func1()函数入口处理的逆过程嘛。挺公道的，谁破坏别人的现场就要给别人恢复回来，最终寄存器ebp、esp恢复到func1()函数入口时的状态，如图10所示(对比图4)。

图10 fun1()函数恢复入口时寄存器状态
结束了吗？等等，漏了两条指令。

1. 
   
2. 00401063 cmp ebp,esp
   
3. 00401065 call __chkesp(004011b0)

复制代码

还记得前文让你留神的忠告吗？回头看看func1()函数入口的指令，正常情况下，在释放func1()函数的栈内存之后，寄存器esp和ebp应该指向栈的同一位置，如果两者不相同，则说明程序出现异常了。所以在这里放置了cmp指令，并调用__chkesp来检查保存在寄存器EFL中的比较结果，如图11所示。

图11 func1()函数的栈内存释放后的寄存器状态
下面是__chkesp例程的指令代码。

10 RET指令中做了什么？
接下来就要执行ret指令了，按下F11，看看哪些寄存器发生了变化？嗯，寄存器esp、eip变了。寄存器esp变大了？咋没看到pop指令呀？呵呵，又是在暗处做了些“见不得人的勾当”。ret指令完成了两个动作：
(1) 把寄存器esp指向的栈数据取出来，存放到寄存器eip中；
(2) 按完成一个出栈动作更新寄存器esp。
看到了吗？寄存器eip存放的指令地址又是call指令后续的第一条指令地址0x004010E4，也就是说又回main()函数中了，如图12所示。

图12 ret指令使得控制返回main()函数中
11 RET指令后做了什么？
大家可能已经注意到寄存器esp现在是指向func1()函数的入口参数的栈区。在前文我们知道func1()函数的入口参数是在main()函数中通过两次push指令入栈的，那么是否意味着有配对的两次pop指令出栈呢？可没有找到pop指令，只有这么一条add指令。

1. 004010e4 add esp,8

复制代码

很明显，对于寄存器esp来说，上述add指令完成两次pop指令同样的功能，即把func1()函数的入口参数j、i出栈。为什么不用pop指令呢？大家考虑一下如果一个函数有10个入口参数，那么岂不是要执行10次pop指令才能把所有入口参数出栈，考虑到指令执行的时钟周期数，采用pop指令的执行时间将是采用add指令的10倍。既然入口参数出栈后不再使用，所以出栈的时间当然是越短越好。
完成入口参数出栈后，寄存器esp又恢复调用func1()函数之前那一刻的状态了，如图13所示(对比图2)。至此，一个完整的函数调用过程到此就圆满结束了。

图13 入口参数出栈后恢复函数调用前的寄存器状态
我们继续讨论函数入口参数出栈的问题，它有一个专业术语“堆栈的平衡”。从上述跟踪过程来看，函数入口参数是由调用者main()函数完成入/出栈操作，即由调用者实现堆栈的平衡，这很合符逻辑。嗯，再来思考这样一个问题：能否由被调用者func1()函数完成上述出栈操作，即由被调用者负责堆栈的平衡呢？
答案是肯定的，因为在被调用者清楚的知道自己的入口参数的长度的情况下，技术实现上完全没有问题，只要在ret指令前清除入口参数的栈区就OK了。
在3小节也提到上述的问题是由函数采用调用约定规则决定。函数声明定义时采用的调用约定告诉了编译器：如何传递参数，是通过堆栈还是寄存器？如果是通过堆栈，函数参数以何种方式入栈，是从右向左，还是从左向右？如果是通过堆栈，由谁负责堆栈的平衡，是调用者，还是被调用者？……下面是几种常见的调用约定。
(1) __cdecl：C/C++函数默认的调用约定，使用栈传递函数参数，从右向左压栈，由调用者负责栈的平衡，VC将函数编译后会在函数名前面加上下划线“_”前缀；

1. 004010df call @ILT+0(_func1)(00401005)

复制代码

(2) __sdtcall：Win32 API函数默认的调用约定，使用栈传递函数参数，从右向左压栈，由被调用者负责栈的平衡，VC将函数编译后会在函数名前面加上下划线“_”前缀，在函数名后加上"@"和参数的字节数；

1. 004010df call @ILT+5(_func1@8)(0040100a)

复制代码

(3) __fastcall：与__stdcall调用约定类似，区别在于函数的第一、二个DWORD类型参数(或者类型长度更小的参数)通过寄存器ecx和edx传道，其余参数通过栈来传递，从右向左压栈，由被调用者负责栈的平衡，VC将函数编译后会在函数名前面加上下划线“@”前缀，在函数名后加上"@"和参数的字节数；

1. 004010ed call @ILT+0(@func1@8)(00401005)

复制代码

由上述规则可知，__cdecl调用约定产生的执行文件会比__stdcall调用约定的要大，因为采用前者，每一个调用者都会产生堆栈平衡的代码，而采用后者，只在被调用者内部产生一次堆栈平衡的代码。噢，由此看来，__cdecl调用约定岂不是要被淘汰了？非也，想想像printf()这种参数个数不确定的函数，__stdcall调用约定应付不了，只能采用__cdecl调用约定，它允许函数的参数的个数是不固定的，这也是C语言的一大特色。
动手试试吧，在定义func1()时增加调用约定说明，然后Save，Rebuild All，再看看其汇编代码，一切尽在不言中。










[ 本帖最后由 whypro 于 2010-5-19 18:41 编辑 ]

whypro

堆栈再谈结论:
1.        函数调用是由call和ret指令完美配对完成的，call指令作用是把控制传送给被调用函数，ret指令作用是把控制返回给调用函数；
2.        函数调用根据函数定义时采用的调用约定来完成函数参数的传递和堆栈平衡；
3.        函数调用导致的入栈操作分三类：
           执行call前入栈操作：显式地把被调用函数入口参数入栈；
           执行call时入栈操作：隐式地把call指令后的那条指令的地址入栈；
           执行call后入栈操作：显式地把调用函数的上下文寄存器入栈；
4.        根据上述入栈内容对栈内存划分结构，则形成如下的典型栈结构
           
5.        栈变量是通过“EBP+偏移量”方式寻址的；
6.        栈内存中自动完成四字节对齐；
7.        字符串常量不存储在栈区中，而存储在全局数据区中。

有些地方可能有一些错误，这是以前写的东西了，所以各位大侠就放我一马，谢谢指出错误！

[ 本帖最后由 whypro 于 2010-5-19 18:37 编辑 ]

Nisy

支持楼主更新 写的不错

建议以后 Debug的编译一份  Release的编译一份 对比着来学习

Release 的优化还是蛮厉害的 很多优化后 代码都是无法还原的

月之精灵

不错，楼主的帖子都很有质量，感谢您对论坛的支持。

wayson

好啊 顶一个啊

源少

现在时间不允许，有时间必来好好拜读楼主的贴。

psjdh

这么好的帖子，多看看

wswm

看到有点晚  看完之后对堆栈确实有进一步的了解  支持LZ 继续更新