backtrace 实现原理
显示函数调用关系(backtrace/callstack)是调试器必备的功能之一，比如在gdb里，用bt命令就可以查看backtrace。在程序崩溃的时候，函数调用关系有助于快速定位问题的根源，了解它的实现原理，可以扩充自己的知识面，在没有调试器的情况下，也能实现自己backtrace。更重要的是，分析backtrace的实现原理很有意思。现在我们一起来研究一下：
glibc提供了一个backtrace函数，这个函数可以帮助我们获取当前函数的backtrace，先看看它的使用方法，后面我们再仿照它写一个。
#include <stdio.h>
#include <stdlib.h>
#include <execinfo.h>
#define MAX_LEVEL 4
static void test2()
{
int i = 0;
void* buffer[MAX_LEVEL] = {0};
int size = backtrace(buffer, MAX_LEVEL);
for(i = 0; i < size; i++)
{
printf("called by %p/n", buffer[i]);
}
return;
}
static void test1()
{
int a=0x11111111;
int b=0x11111112;
test2();
a = b;
return;
}
static void test()
{
int a=0x10000000;
int b=0x10000002;
test1();
a = b;
return;
}
int main(int argc, char* argv[])
{
test();
return 0;
}
编译运行它：
gcc -g -Wall bt_std.c -o bt_std
./bt_std
屏幕打印：
called by 0×8048440
called by 0×804848a
called by 0×80484ab
called by 0×80484c9
上面打印的是调用者的地址，对程序员来说不太直观，glibc还提供了另外一个函数backtrace_symbols，它可以把这些地址转换成源代码的位置(通常是函数名)。不过这个函数并不怎么好用，特别是在没有调试信息的情况下，几乎得不什么有用的信息。这里我们使用另外一个工具addr2line来实现地址到源代码位置的转换：
运行：
./bt_std |awk ‘{print “addr2line “$3″ -e bt_std”}’>t.sh;. t.sh;rm -f t.sh
屏幕打印：
/home/work/mine/sysprog/think-in-compway/backtrace/bt_std.c:12
/home/work/mine/sysprog/think-in-compway/backtrace/bt_std.c:28
/home/work/mine/sysprog/think-in-compway/backtrace/bt_std.c:39
/home/work/mine/sysprog/think-in-compway/backtrace/bt_std.c:48
backtrace是如何实现的呢？ 在x86的机器上，函数调用时，栈中数据的结构如下：
参数N
参数… 函数参数入栈的顺序与具体的调用方式有关
参数 3
参数 2
参数 1
EIP 完成本次调用后，下一条指令的地址
EBP 保存调用者的EBP，然后EBP指向此时的栈顶。
----------------新的EBP指向这里---------------
临时变量1
临时变量2
临时变量3
临时变量…
临时变量5
(说明：下面低是地址，上面是高地址，栈向下增长的)
调用时，先把被调函数的参数压入栈中，C语言的压栈方式是：先压入最后一个参数，再压入倒数第二参数，按此顺序入栈，最后才压入第一个参数。
然后压入EIP和EBP，此时EIP指向完成本次调用后下一条指令的地址 ，这个地址可以近似的认为是函数调用者的地址。EBP是调用者和被调函数之间的分界线，分界线之上是调用者的临时变量、被调函数的参数、函数返回地址(EIP)，和上一层函数的EBP，分界线之下是被调函数的临时变量。
最后进入被调函数，并为它分配临时变量的空间。gcc不同版本的处理是不一样的，对于老版本的gcc(如gcc3.4)，第一个临时变量放在最高的地址，第二个其次，依次顺序分布。而对于新版本的gcc(如gcc4.3)，临时变量的位置是反的，即最后一个临时变量在最高的地址，倒数第二个其次，依次顺序分布。
为了实现backtrace，我们需要：
1.获取当前函数的EBP。
2.通过EBP获得调用者的EIP。
3.通过EBP获得上一级的EBP。
4.重复这个过程，直到结束。
通过嵌入汇编代码，我们可以获得当前函数的EBP，不过这里我们不用汇编，而且通过临时变量的地址来获得当前函数的EBP。我们知道，对于gcc3.4生成的代码，当前函数的第一个临时变量的下一个位置就是EBP。而对于gcc4.3生成的代码，当前函数的最后一个临时变量的下一个位置就是EBP。
有了这些背景知识，我们来实现自己的backtrace:
#ifdef NEW_GCC
#define OFFSET 4
#else
#define OFFSET 0
#endif/NEW_GCC/
int backtrace(void** buffer, int size)
{
int n = 0xfefefefe;
int* p = &n;
int i = 0;
int ebp = p[1 + OFFSET];
int eip = p[2 + OFFSET];
for(i = 0; i < size; i++)
{
buffer[i] = (void*)eip;
p = (int*)ebp;
ebp = p[0];
eip = p[1];
}
return size;
}
对于老版本的gcc，OFFSET定义为0，此时p+1就是EBP，而p[1]就是上一级的EBP，p[2]是调用者的EIP。本函数总共有5个int的临时变量，所以对于新版本gcc， OFFSET定义为5，此时p+5就是EBP。在一个循环中，重复取上一层的EBP和EIP，最终得到所有调用者的EIP，从而实现了backtrace。
现在我们用完整的程序来测试一下(bt.c)：
#include <stdio.h>
#define MAX_LEVEL 4
#ifdef NEW_GCC
#define OFFSET 4
#else
#define OFFSET 0
#endif/NEW_GCC/
int backtrace(void** buffer, int size)
{
int n = 0xfefefefe;
int* p = &n;
int i = 0;
int ebp = p[1 + OFFSET];
int eip = p[2 + OFFSET];
for(i = 0; i < size; i++)
{
buffer[i] = (void*)eip;
p = (int*)ebp;
ebp = p[0];
eip = p[1];
}
return size;
}
static void test2()
{
int i = 0;
void* buffer[MAX_LEVEL] = {0};
backtrace(buffer, MAX_LEVEL);
for(i = 0; i < MAX_LEVEL; i++)
{
printf("called by %p/n", buffer[i]);
}
return;
}
static void test1()
{
int a=0x11111111;
int b=0x11111112;
test2();
a = b;
return;
}
static void test()
{
int a=0x10000000;
int b=0x10000002;
test1();
a = b;
return;
}
int main(int argc, char* argv[])
{
test();
return 0;
}
写个简单的Makefile:
CFLAGS=-g -Wall
all:
gcc34 $(CFLAGS) bt.c -o bt34
gcc $(CFLAGS) -DNEW_GCC bt.c -o bt
gcc $(CFLAGS) bt_std.c -o bt_std
clean:
rm -f bt bt34 bt_std
编译然后运行：
make
./bt|awk ‘{print “addr2line “$3″ -e bt”}’>t.sh;. t.sh;
屏幕打印：
/home/work/mine/sysprog/think-in-compway/backtrace/bt.c:37
/home/work/mine/sysprog/think-in-compway/backtrace/bt.c:51
/home/work/mine/sysprog/think-in-compway/backtrace/bt.c:62
/home/work/mine/sysprog/think-in-compway/backtrace/bt.c:71
对于可执行文件，这种方法工作正常。对于共享库，addr2line无法根据这个地址找到对应的源代码位置了。原因是：addr2line只能通过地址偏移量来查找，而打印出的地址是绝对地址。由于共享库加载到内存的位置是不确定的，为了计算地址偏移量，我们还需要进程maps文件的帮助：
通过进程的maps文件(/proc/进程号/maps)，我们可以找到共享库的加载位置，如：
…
00c5d000-00c5e000 r-xp 00000000 08:05 2129013 /home/work/mine/sysprog/think-in-compway/backtrace/libbt_so.so
00c5e000-00c5f000 rw-p 00000000 08:05 2129013 /home/work/mine/sysprog/think-in-compway/backtrace/libbt_so.so
…
libbt_so.so的代码段加载到0×00c5d000-0×00c5e000，而backtrace打印出的地址是：
called by 0xc5d4eb
called by 0xc5d535
called by 0xc5d556
called by 0×80484ca
这里可以用打印出的地址减去加载的地址来计算偏移量。如，用 0xc5d4eb减去加载地址0×00c5d000，得到偏移量0×4eb，然后把0×4eb传给addr2line：
addr2line 0×4eb -f -s -e ./libbt_so.so
屏幕打印：
/home/work/mine/sysprog/think-in-compway/backtrace/bt_so.c:38
栈里的数据很有意思，在上一节中，通过分析栈里的数据，我们了解了变参函数的实现原理。在这一节中，通过分析栈里的数据，我们又学到了backtrace的实现原理。