织梦CMS - 轻松建站从此开始！
高级搜索|网站地图|TAG标签RSS订阅[设为首页] [加入收藏]

罗索

搜索

热门标签:

当前位置: 主页>基础技术>C/CPP专题>

大内高手—栈/堆

落鹤生 发布于 2012-04-28 09:17 点击:次 
从汇编代码中，我们可以看出，参数是逆序入栈的。在取参数时，先让ap指向第一个参数，又因为栈是向下增长的，不断把指针向上移动就可以取出所有参数了。
TAG:

转载时请注明出处和作者联系方式：http://blog.csdn.net/absurd

作者联系方式：李先静 <xianjimli at hotmail dot com>

更新时间：2007-7-9

l         栈

栈作为一种基本数据结构，我并不感到惊讶，用来实现函数调用，这也司空见惯的作法。直到我试图找到另外一种方式实现递归操作时，我才感叹于它的巧妙。要实现递归操作，不用栈不是不可能，而是找不出比它更优雅的方式。

尽管大多数编译器在优化时，会把常用的参数或者局部变量放入寄存器中。但用栈来管理函数调用时的临时变量（局部变量和参数）是通用做法，前者只是辅助手段，且只在当前函数中使用，一旦调用下一层函数，这些值仍然要存入栈中才行。

通常情况下，栈向下（低地址）增长，每向栈中PUSH一个元素，栈顶就向低地址扩展，每从栈中POP一个元素，栈顶就向高地址回退。一个有兴趣的问题：在x86平台上，栈顶寄存器为ESP，那么ESP的值在是PUSH操作之前修改呢，还是在PUSH操作之后修改呢？PUSH ESP这条指令会向栈中存入什么数据呢？据说x86系列CPU中，除了286外，都是先修改ESP，再压栈的。由于286没有CPUID指令，有的OS用这种方法检查286的型号。

一个函数内的局部变量以及其调用下一级函数的参数，所占用的内存空间作为一个基本的单元，称为一个帧(frame)。在gdb里，f 命令就是用来查看指定帧的信息的。在两个frame之间通过还存有其它信息，比如上一层frame的分界地址(EBP)等。

关于栈的基本知识，就先介绍这么多，我们下面来看看一些关于栈的技巧及应用：

1.         backtrace的实现

callstack调试器的基本功能之一，利用此功能，你可以看到各级函数的调用关系。在gdb中，这一功能被称为backtrace，输入bt命令就可以看到当前函数的callstack。它的实现多少有些有趣，我们在这里研究一下。

 

我们先看看栈的基本模型

参数N

↓高地址

参数…

函数参数入栈的顺序与具体的调用方式有关

参数 3

参数 2

参数 1

EIP

返回本次调用后，下一条指令的地址

EBP

保存调用者的EBP，然后EBP指向此时的栈顶。

临时变量1

 

临时变量2

 

临时变量3

 

临时变量…

 

临时变量5

↓低地址

要实现callstack我们需要知道以下信息：

l         调用函数时的指令地址（即当时的EIP）。

l         指令地址对应的源代码代码位置。

关于第一点，从上表中，我们可以看出，栈中存有各级EIP的值，我们取出来就行了。用下面的代码可以轻易实现：

  1. #include <stdio.h> 
  2.  
  3. int backtrace(void** BUFFER, int SIZE) 
  4. { 
  5.     int  n = 0; 
  6.     int* p = &n; 
  7.     int  i = 0; 
  8.  
  9.     int ebp = p[1]; 
  10.     int eip = p[2]; 
  11.  
  12.     for(i = 0; i < SIZE; i++) 
  13.     { 
  14.         BUFFER[i] = (void*)eip; 
  15.         p = (int*)ebp; 
  16.         ebp = p[0]; 
  17.         eip = p[1]; 
  18.     } 
  19.  
  20.     return SIZE; 
  21. } 
  22.  
  23. #define N 4 
  24. static void test2() 
  25. { 
  26.     int i = 0; 
  27.     void* BUFFER[N] = {0}; 
  28.    backtrace(BUFFER, N); 
  29.     for(i = 0; i < N; i++) 
  30.     { 
  31.         printf("%p/n",  BUFFER[i]); 
  32.     } 
  33.     return; 
  34. } 
  35.  
  36. static void test1() 
  37. { 
  38.     test2(); 
  39. } 
  40.  
  41. static void test() 
  42. { 
  43.     test1(); 
  44. } 
  45.  
  46. int main(int argc, char* argv[]) 
  47. { 
  48.     test(); 
  49.     return 0; 
  50. } 

程序输出：

0x8048460

0x804849c

0x80484a9

0x80484cc

关于第二点，如何把指令地址与行号对应起来，这也很简单。可以从MAP文件或者ELF中查询。Binutil带有一个addr2line的小工具，可以帮助实现这一点。

[root@linux bt]# addr2line  0x804849c -e bt.exe

/root/test/bt/bt.c:42

2.         alloca的实现

大家都知道动态分配的内存，一定要释放掉，否则就会有内存泄露。可能鲜有人知，动态分配的内存，可以不用释放。Alloca就是这样一个函数，最后一个a代表auto，即自动释放的意思。

Alloca是在栈中分配内存的。即然是在栈中分配，就像其它在栈中分配的临时变量一样，在当前函数调用完成时，这块内存自动释放。

正如我们前面讲过，栈的大小是有限制的，普通线程的栈只有10M大小，所以在分配时，要量力而行，且不要分配过大内存。

Alloca可能会渐渐的退出历史舞台，原因是新的C/C++标准都支持变长数组。比如int array[n]，老版本的编译器要求n是常量，而新编译器允许n是变量。编译器支持的这一功能完全可以取代alloca。

这不是一个标准函数，但像linux和win32等大多数平台都支持。即使少数平台不支持，要自己实现也不难。这里我们简单介绍一下alloca的实现方法。

我们先看看一个小程序，再看看它对应的汇编代码，一切都清楚了。

  1. #include <stdio.h> 
  2.  
  3. int main(int argc, char* argv[]) 
  4. { 
  5.     int  n = 0; 
  6.     int* p = alloca(1024); 
  7.  
  8.     printf("&n=%p p=%p/n", &n, p); 
  9.     return 0; 
  10. } 

汇编代码为：

  1. int main(int argc, char* argv[]) 
  2. { 
  3.  8048394:       55                      push   %ebp 
  4.  8048395:       89 e5                   mov    %esp,%ebp 
  5.  8048397:       83 ec 18                sub    $0x18,%esp 
  6.  804839a:       83 e4 f0                and    $0xfffffff0,%esp 
  7.  804839d:       b8 00 00 00 00          mov    $0x0,%eax 
  8.  80483a2:       83 c0 0f                add    $0xf,%eax 
  9.  80483a5:       83 c0 0f                add    $0xf,%eax 
  10.  80483a8:       c1 e8 04                shr    $0x4,%eax 
  11.  80483ab:       c1 e0 04                shl    $0x4,%eax 
  12.  80483ae:       29 c4                   sub    %eax,%esp 
  13.         int  n = 0; 
  14.  80483b0:       c7 45 fc 00 00 00 00    movl   $0x0,0xfffffffc(%ebp) 
  15.         int* p = alloca(1024); 
  16.  80483b7:       81 ec 10 04 00 00       sub    $0x410,%esp 
  17.  80483bd:       8d 44 24 0c             lea    0xc(%esp),%eax 
  18.  80483c1:       83 c0 0f                add    $0xf,%eax 
  19.  80483c4:       c1 e8 04                shr    $0x4,%eax 
  20.  80483c7:       c1 e0 04                shl    $0x4,%eax 
  21.  80483ca:       89 45 f8                mov    %eax,0xfffffff8(%ebp) 
  22.         printf("&n=%p p=%p/n", &n, p); 
  23.  80483cd:       8b 45 f8                mov    0xfffffff8(%ebp),%eax 
  24.  80483d0:       89 44 24 08             mov    %eax,0x8(%esp) 
  25.  80483d4:       8d 45 fc                lea    0xfffffffc(%ebp),%eax 
  26.  80483d7:       89 44 24 04             mov    %eax,0x4(%esp) 
  27.  80483db:       c7 04 24 98 84 04 08    movl   $0x8048498,(%esp) 
  28.  80483e2:       e8 d1 fe ff ff          call   80482b8 <printf@plt> 
  29.         return 0; 
  30.  80483e7:       b8 00 00 00 00          mov    $0x0,%eax 
  31. } 

其中关键的一条指令为：sub    $0x410,%esp

由此可以看出实现alloca，仅仅是把ESP减去指定大小，扩大栈空间（记记住栈是向下增长），这块空间就是分配的内存。

 

3.         可变参数的实现。

对新手来说，可变参数的函数也是比较神奇。还是以一个小程序来说明它的实现。

  1. #include <stdio.h> 
  2. #include <stdarg.h> 
  3.  
  4. int print(const char* fmt, ...) 
  5. { 
  6.     int n1 = 0; 
  7.     int n2 = 0; 
  8.     int n3 = 0; 
  9.     va_list ap; 
  10.     va_start(ap, fmt); 
  11.   
  12.     n1 = va_arg(ap, int); 
  13.     n2 = va_arg(ap, int); 
  14.     n3 = va_arg(ap, int); 
  15.  
  16.     va_end(ap); 
  17.  
  18.     printf("n1=%d n2=%d n3=%d/n", n1, n2, n3); 
  19.  
  20.     return 0; 
  21. } 
  22.  
  23. int main(int arg, char argv[]) 
  24. { 
  25.     print("%d/n", 1, 2, 3); 
  26.     return 0; 
  27. } 

我们看看对应的汇编代码：

  1. int print(const char* fmt, ...) 
  2. { 
  3.  8048394:       55                      push   %ebp 
  4.  8048395:       89 e5                   mov    %esp,%ebp 
  5.  8048397:       83 ec 28                sub    $0x28,%esp 
  6.         int n1 = 0; 
  7.  804839a:       c7 45 fc 00 00 00 00    movl   $0x0,0xfffffffc(%ebp) 
  8.         int n2 = 0; 
  9.  80483a1:       c7 45 f8 00 00 00 00    movl   $0x0,0xfffffff8(%ebp) 
  10.         int n3 = 0; 
  11.  80483a8:       c7 45 f4 00 00 00 00    movl   $0x0,0xfffffff4(%ebp) 
  12.         va_list ap; 
  13.         va_start(ap, fmt); 
  14.  80483af:       8d 45 0c                lea    0xc(%ebp),%eax 
  15.  80483b2:       89 45 f0                mov    %eax,0xfffffff0(%ebp) 
  16.         n1 = va_arg(ap, int); 
  17.  80483b5:       8b 55 f0                mov    0xfffffff0(%ebp),%edx 
  18.  80483b8:       8d 45 f0                lea    0xfffffff0(%ebp),%eax 
  19.  80483bb:       83 00 04                addl   $0x4,(%eax) 
  20.  80483be:       8b 02                   mov    (%edx),%eax 
  21.  80483c0:       89 45 fc                mov    %eax,0xfffffffc(%ebp) 
  22.         n2 = va_arg(ap, int); 
  23.  80483c3:       8b 55 f0                mov    0xfffffff0(%ebp),%edx 
  24.  
  25.  80483c6:       8d 45 f0                lea    0xfffffff0(%ebp),%eax 
  26.  
  27.  80483c9:       83 00 04                addl   $0x4,(%eax) 
  28.  
  29.  80483cc:       8b 02                   mov    (%edx),%eax 
  30.  
  31.  80483ce:       89 45 f8                mov    %eax,0xfffffff8(%ebp) 
  32.  
  33.         n3 = va_arg(ap, int); 
  34.  
  35.  80483d1:       8b 55 f0                mov    0xfffffff0(%ebp),%edx 
  36.  
  37.  80483d4:       8d 45 f0                lea    0xfffffff0(%ebp),%eax 
  38.  
  39.  80483d7:       83 00 04                addl   $0x4,(%eax) 
  40.  
  41.  80483da:       8b 02                   mov    (%edx),%eax 
  42.  
  43.  80483dc:       89 45 f4                mov    %eax,0xfffffff4(%ebp) 
  44.  
  45.   
  46.  
  47.         va_end(ap); 
  48.  
  49.        printf("n1=%d n2=%d n3=%d/n", n1, n2, n3); 
  50.  
  51.  80483df:       8b 45 f4                mov    0xfffffff4(%ebp),%eax 
  52.  
  53.  80483e2:       89 44 24 0c             mov    %eax,0xc(%esp) 
  54.  
  55.  80483e6:       8b 45 f8                mov    0xfffffff8(%ebp),%eax 
  56.  
  57.  80483e9:       89 44 24 08             mov    %eax,0x8(%esp) 
  58.  
  59.  80483ed:       8b 45 fc                mov    0xfffffffc(%ebp),%eax 
  60.  
  61.  80483f0:       89 44 24 04             mov    %eax,0x4(%esp) 
  62.  
  63.  80483f4:       c7 04 24 f8 84 04 08    movl   $0x80484f8,(%esp) 
  64.  
  65.  80483fb:       e8 b8 fe ff ff          call   80482b8 <printf@plt> 
  66.  
  67.   
  68.  
  69.         return 0; 
  70.  
  71.  8048400:       b8 00 00 00 00          mov    $0x0,%eax 
  72.  
  73. } 
  74.  
  75. int main(int arg, char argv[]) 
  76.  
  77. { 
  78.  
  79.  8048407:       55                      push   %ebp 
  80.  
  81.  8048408:       89 e5                   mov    %esp,%ebp 
  82.  
  83.  804840a:       83 ec 18                sub    $0x18,%esp 
  84.  
  85.  804840d:       83 e4 f0                and    $0xfffffff0,%esp 
  86.  
  87.  8048410:       b8 00 00 00 00          mov    $0x0,%eax 
  88.  
  89.  8048415:       83 c0 0f                add    $0xf,%eax 
  90.  
  91.  8048418:       83 c0 0f                add    $0xf,%eax 
  92.  
  93.  804841b:       c1 e8 04                shr    $0x4,%eax 
  94.  
  95.  804841e:       c1 e0 04                shl    $0x4,%eax 
  96.  
  97.  8048421:       29 c4                   sub    %eax,%esp 
  98.  
  99.         int n = print("%d/n", 1, 2, 3); 
  100.  
  101.  8048423:       c7 44 24 0c 03 00 00    movl   $0x3,0xc(%esp) 
  102.  
  103.  804842a:       00 
  104.  
  105.  804842b:       c7 44 24 08 02 00 00    movl   $0x2,0x8(%esp) 
  106.  
  107.  8048432:       00 
  108.  
  109.  8048433:       c7 44 24 04 01 00 00    movl   $0x1,0x4(%esp) 
  110.  
  111.  804843a:       00 
  112.  
  113.  804843b:       c7 04 24 0b 85 04 08    movl   $0x804850b,(%esp) 
  114.  
  115.  8048442:       e8 4d ff ff ff          call   8048394 <print> 
  116.  
  117.  8048447:       89 45 fc                mov    %eax,0xfffffffc(%ebp) 
  118.  
  119.   
  120.  
  121.         return 0; 
  122.  
  123.  804844a:       b8 00 00 00 00          mov    $0x0,%eax 
  124.  
  125. } 

从汇编代码中，我们可以看出，参数是逆序入栈的。在取参数时，先让ap指向第一个参数，又因为栈是向下增长的，不断把指针向上移动就可以取出所有参数了。

 

l         堆

在内存分配算法一节中再详细讲解。

 

(李先静)
本站文章除注明转载外，均为本站原创或编译欢迎任何形式的转载，但请务必注明出处，尊重他人劳动，同学习共成长。转载请注明：文章转载自：罗索实验室 [http://www.rosoo.net/a/201204/15970.html]
本文出处：CSDN博客　作者：李先静 原文
顶一下
(0)
0%
踩一下
(0)
0%
------分隔线----------------------------
相关文章
发表评论
请自觉遵守互联网相关的政策法规，严禁发布色情、暴力、反动的言论。
评价:
表情:
用户名: 验证码:点击我更换图片
最新评论 进入详细评论页>>
栏目列表
将本文分享到微信
织梦二维码生成器
推荐内容
热点内容