大内高手—栈/堆
1,473 views| 2008-11-30| 李先静| Programming| | 1 条评论转载时请注明出处和作者联系方式
文章出处：http://www.limodev.cn/blog
作者联系方式：李先静 <xianjimli@gmail.com>
o 栈
栈作为一种基本数据结构，我并不感到惊讶，用来实现函数调用，这也司空见惯的作法。直到我试图找到另外一种方式实现递归操作时，我才感叹于它的巧妙。要实现递归操作，不用栈不是不可能，而是找不出比它更优雅的方式。
尽管大多数编译器在优化时，会把常用的参数或者局部变量放入寄存器中。但用栈来管理函数调用时的临时变量（局部变量和参数）是通用做法，前者只是辅助手段，且只在当前函数中使用，一旦调用下一层函数，这些值仍然要存入栈中才行。
通常情况下，栈向下（低地址）增长，每向栈中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 临时变量… 临时变量N-----------↓低地址
要实现callstack我们需要知道以下信息：
o 调用函数时的指令地址（即当时的EIP）。
o 指令地址对应的源代码代码位置。
关于第一点，从上表中，我们可以看出，栈中存有各级EIP的值，我们取出来就行了。用下面的代码可以轻易实现：
#include <stdio.h>
int backtrace(void** BUFFER, int SIZE)
{
int n = 0;
int* p = &n;
int i = 0;
int ebp = p[1];
int eip = p[2];
for(i = 0; i < SIZE; i++)
{
BUFFER[i] = (void*)eip;
p = (int*)ebp;
ebp = p[0];
eip = p[1];
}
return SIZE;
}
#define N 4
static void test2()
{
int i = 0;
void* BUFFER[N] = {0};
backtrace(BUFFER, N);
for(i = 0; i < N; i++)
{
printf("%p\n", BUFFER[i]);
}
return;
}
static void test1()
{
test2();
}
static void test()
{
test1();
}
int main(int argc, char* argv[])
{
test();
return 0;
}
程序输出：
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的实现方法。
我们先看看一个小程序，再看看它对应的汇编代码，一切都清楚了。
#include <stdio.h>
int main(int argc, char* argv[])
{
int n = 0;
int* p = alloca(1024);
printf("&n=%p p=%p\n", &n, p);
return 0;
}
汇编代码为：
int main(int argc, char* argv[])
{
8048394: 55 push %ebp
8048395: 89 e5 mov %esp,%ebp
8048397: 83 ec 18 sub $0x18,%esp
804839a: 83 e4 f0 and $0xfffffff0,%esp
804839d: b8 00 00 00 00 mov $0x0,%eax
80483a2: 83 c0 0f add $0xf,%eax
80483a5: 83 c0 0f add $0xf,%eax
80483a8: c1 e8 04 shr $0x4,%eax
80483ab: c1 e0 04 shl $0x4,%eax
80483ae: 29 c4 sub %eax,%esp
int n = 0;
80483b0: c7 45 fc 00 00 00 00 movl $0x0,0xfffffffc(%ebp)
int* p = alloca(1024);
80483b7: 81 ec 10 04 00 00 sub $0x410,%esp
80483bd: 8d 44 24 0c lea 0xc(%esp),%eax
80483c1: 83 c0 0f add $0xf,%eax
80483c4: c1 e8 04 shr $0x4,%eax
80483c7: c1 e0 04 shl $0x4,%eax
80483ca: 89 45 f8 mov %eax,0xfffffff8(%ebp)
printf("&n=%p p=%p\n", &n, p);
80483cd: 8b 45 f8 mov 0xfffffff8(%ebp),%eax
80483d0: 89 44 24 08 mov %eax,0x8(%esp)
80483d4: 8d 45 fc lea 0xfffffffc(%ebp),%eax
80483d7: 89 44 24 04 mov %eax,0x4(%esp)
80483db: c7 04 24 98 84 04 08 movl $0x8048498,(%esp)
80483e2: e8 d1 fe ff ff call 80482b8 <printf@plt>
return 0;
80483e7: b8 00 00 00 00 mov $0x0,%eax
}
其中关键的一条指令为：sub $0×410,%esp
由此可以看出实现alloca，仅仅是把ESP减去指定大小，扩大栈空间（记记住栈是向下增长），这块空间就是分配的内存。
3. 可变参数的实现。
对新手来说，可变参数的函数也是比较神奇。还是以一个小程序来说明它的实现。
#include <stdio.h>
#include <stdarg.h>
int print(const char* fmt, ...)
{
int n1 = 0;
int n2 = 0;
int n3 = 0;
va_list ap;
va_start(ap, fmt);
n1 = va_arg(ap, int);
n2 = va_arg(ap, int);
n3 = va_arg(ap, int);
va_end(ap);
printf("n1=%d n2=%d n3=%d\n", n1, n2, n3);
return 0;
}
int main(int arg, char argv[])
{
print("%d\n", 1, 2, 3);
return 0;
}
我们看看对应的汇编代码：
int print(const char* fmt, ...)
{
8048394: 55 push %ebp
8048395: 89 e5 mov %esp,%ebp
8048397: 83 ec 28 sub $0x28,%esp
int n1 = 0;
804839a: c7 45 fc 00 00 00 00 movl $0x0,0xfffffffc(%ebp)
int n2 = 0;
80483a1: c7 45 f8 00 00 00 00 movl $0x0,0xfffffff8(%ebp)
int n3 = 0;
80483a8: c7 45 f4 00 00 00 00 movl $0x0,0xfffffff4(%ebp)
va_list ap;
va_start(ap, fmt);
80483af: 8d 45 0c lea 0xc(%ebp),%eax
80483b2: 89 45 f0 mov %eax,0xfffffff0(%ebp)
n1 = va_arg(ap, int);
80483b5: 8b 55 f0 mov 0xfffffff0(%ebp),%edx
80483b8: 8d 45 f0 lea 0xfffffff0(%ebp),%eax
80483bb: 83 00 04 addl $0x4,(%eax)
80483be: 8b 02 mov (%edx),%eax
80483c0: 89 45 fc mov %eax,0xfffffffc(%ebp)
n2 = va_arg(ap, int);
80483c3: 8b 55 f0 mov 0xfffffff0(%ebp),%edx
80483c6: 8d 45 f0 lea 0xfffffff0(%ebp),%eax
80483c9: 83 00 04 addl $0x4,(%eax)
80483cc: 8b 02 mov (%edx),%eax
80483ce: 89 45 f8 mov %eax,0xfffffff8(%ebp)
n3 = va_arg(ap, int);
80483d1: 8b 55 f0 mov 0xfffffff0(%ebp),%edx
80483d4: 8d 45 f0 lea 0xfffffff0(%ebp),%eax
80483d7: 83 00 04 addl $0x4,(%eax)
80483da: 8b 02 mov (%edx),%eax
80483dc: 89 45 f4 mov %eax,0xfffffff4(%ebp)
va_end(ap);
printf("n1=%d n2=%d n3=%d\n", n1, n2, n3);
80483df: 8b 45 f4 mov 0xfffffff4(%ebp),%eax
80483e2: 89 44 24 0c mov %eax,0xc(%esp)
80483e6: 8b 45 f8 mov 0xfffffff8(%ebp),%eax
80483e9: 89 44 24 08 mov %eax,0x8(%esp)
80483ed: 8b 45 fc mov 0xfffffffc(%ebp),%eax
80483f0: 89 44 24 04 mov %eax,0x4(%esp)
80483f4: c7 04 24 f8 84 04 08 movl $0x80484f8,(%esp)
80483fb: e8 b8 fe ff ff call 80482b8 <printf@plt>
return 0;
8048400: b8 00 00 00 00 mov $0x0,%eax
}
int main(int arg, char argv[])
{
8048407: 55 push %ebp
8048408: 89 e5 mov %esp,%ebp
804840a: 83 ec 18 sub $0x18,%esp
804840d: 83 e4 f0 and $0xfffffff0,%esp
8048410: b8 00 00 00 00 mov $0x0,%eax
8048415: 83 c0 0f add $0xf,%eax
8048418: 83 c0 0f add $0xf,%eax
804841b: c1 e8 04 shr $0x4,%eax
804841e: c1 e0 04 shl $0x4,%eax
8048421: 29 c4 sub %eax,%esp
int n = print("%d\n", 1, 2, 3);
8048423: c7 44 24 0c 03 00 00 movl $0x3,0xc(%esp)
804842a: 00
804842b: c7 44 24 08 02 00 00 movl $0x2,0x8(%esp)
8048432: 00
8048433: c7 44 24 04 01 00 00 movl $0x1,0x4(%esp)
804843a: 00
804843b: c7 04 24 0b 85 04 08 movl $0x804850b,(%esp)
8048442: e8 4d ff ff ff call 8048394 <print>
8048447: 89 45 fc mov %eax,0xfffffffc(%ebp)
return 0;
804844a: b8 00 00 00 00 mov $0x0,%eax
}
从汇编代码中，我们可以看出，参数是逆序入栈的。在取参数时，先让ap指向第一个参数，又因为栈是向下增长的，不断把指针向上移动就可以取出所有参数了。
o 堆
在内存分配算法一节中再详细讲解。
November 30th, 2008
This author published 367 posts in this site.Share
Dig
December 1st, 2008
学习，再学习，感觉自己理解还是不够彻底