棧
棧作為一種基本數據結構，我並不感到驚訝，用來實現函數調用，這也司空見慣的作法。直到我試圖找到另外一種方式實現遞歸操作時，我才感歎於它的巧妙。要實現遞歸操作，不用棧不是不可能，而是找不出比它更優雅的方式。
盡管大多數編譯器在優化時，會把常用的參數或者局部變量放入寄存器中。但用棧來管理函數調用時的臨時變量（局部變量和參數）是通用做法，前者只是輔助手段，且只在當前函數中使用，一旦調用下一層函數，這些值仍然要存入棧中才行。
通常情況下，棧向下（低地址）增長，每向棧中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的值，我們取出來就行了。用下面的代碼可以輕易實現：
#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，即自動釋放的意思。
