记得刚来公司时曾参与过一个项目，项目中用到了部门基础库中的一个B+树接口。不过在程序调试过程中我们发现可执行程序总是dump core（在sparc solaris上），经初步分析，断定问题就出在B+树接口处，但一时又找不到问题原因。还好这个B+树的实现者就坐在我的旁边。他分析后告诉我：这个B+树接口要求用户自定义的索引结构体的size应该为4的整数倍。按照他的说法，我为结构体打了padding，以满足结构体size为4的整数倍的要求。修改后果然不再dump core了。当时项目进度紧，我也没有求甚解，这件事也就过去了。

一晃N年过去了。今天在做程序的64位移植过程中我再次遇到了这个问题。问题的表象就是程序运行时dump core，通过gdb或pstack查看core的内容，发现程序是在B+ Tree初始化时出的core。显然这又是一个内存违规访问的问题，且在Sparc上出现（x86 Linux上运行正常）十有八九与内存对齐有关。

B+ Tree出问题首先让我想到了N年前的那个解决方法。我先查看了自定义的索引结构体(usr_idx)：

struct usr_idx {
    unsigned int usr;
};

不过sizeof(usr_idx)无论是32bit编译还是64bit编译，其值都是4。那按照B+树原作者的说法，这显然不足以让B+树出现问题。事实也的确如此，32bit编译的程序在Sparc Solaris下运行良好，只是目前改为了64bit编译，才dump core，那问题到底出现在哪呢？

到这里，我也只能从代码着手了，把N年前没弄清楚的原因找出来，顺便也把这个存在了N年的Bug彻底解决掉，把这笔技术债还了。pstack的输出告诉我问题出在一个名为bptree_create_node的函数中，嫌疑最大的一处代码大致是这样的：

for (i = 0; i rank; i++) {
    (elem_base(tree, tmp_bn, i))->key = key_base(tree, tmp_bn, i);
    (elem_base(tree, tmp_bn, i))->pointer = NULL;
}

直觉告诉我问题出在elem_base这个宏里，elem_base的定义如下：

#define elem_base(tree, eb, index) ((xx_bptree_elem*)((char *)&(eb)->e_base.mw_cp + ((SIZEOF_bptree_elem + (tree)->keysize))*(index)))

很显然这个定义最终是想得到一个xx_bptree_elem*类型的指针。从内存地址角度来说，我们会得到了一个内存地址，且这个地址被认为是一个xx_bptree_element元素的起始地址。那么是否所有地址作为xx_bptree_element元素的起始地址都合法呢？答案是不一定，至少在Sparc平台上不是所有地址都可以作为xx_bptree_elem的起始地址的。

那么什么样地址可以作为xx_bptree_element的起始地址呢？在Sparc上这取决于结构体的对齐系数。xx_bptree_elem结构的定义如下：

union mem_word {
    void  *mw_vp;
    void (*mw_fp)(void);
    char  *mw_cp;
    long   mw_l;
    double mw_d;
};
typedef union mem_word mem_word;
#define SIZEOF_mem_word (sizeof(mem_word))

struct xx_bptree_elem {
    void       *key;
    void       *pointer;
    mem_word   base;
};
typedef struct xx_bptree_item xx_bptree_item;
#define SIZEOF_bptree_elem        (sizeof(xx_bptree_elem)-sizeof(mem_word))

在32bit编译的情况下，系统默认对齐系数为4(参见/usr/include/sys/isa_defs.h中的宏_MAX_ALIGNMENT)，则该结构体的对齐系数 = min(max(sizeof(key), sizeof(pointer), sizeof(base)), 4) = 4。这样xx_bptree_elem在32bit下的有效起始地址为可被4整除的内存地址。

而在用64bit编译时，系统默认的对齐系数为16（同参见isa_defs.h），但由于xx_bptree_elem中size最大的字段(base)的size为8，则结构体的对齐系数就等于8。即xx_bptree_elem元素的有效起始地址为可被8整除的地址。

好了，我们再回过头来看看elem_base宏在不同编译情况下能否总是返回合法的地址。

#define elem_base(tree, eb, index) ((xx_bptree_elem*)((char *)&(eb)->e_base.mw_cp + ((SIZEOF_bptree_elem + (tree)->keysize))*(index)))

这个宏中有三个元素决定返回地址，分别是"基址"：&(eb)->e_base.mw_cp、偏移量SIZEOF_bptree_elem和(tree)->keysize。其中基址是另外一个结构体xx_bptree_node中一个mem_word类型字段的地址，你知道的，mem_word这种手法可以保证其起始地址严格按照其内部最大字段的对齐系数对齐的，也就是说mem_word的对齐系数与double的对齐系数一致，即无论是32bit编译还是64bit编译，其对齐系数都是8，也就是说我们可以确保这个”基址“是可以被8整除的；至于偏移量SIZEOF_bptree_elem，我们可以直接可以得出其大小：

32bit下，SIZEOF_bptree_elem = 8
64bit下，SIZEOF_bptree_elem = 16

可以看出无论是32bit还是64bit编译，SIZEOF_bptree_elem的值都是8的倍数；显然这两个值都不会影响elem_base最终返回地址的合法性。

现在剩下的就是(tree)->keysize了。keysize是由xx_bptree_init接口传进来的，它在上层实际上就是用户自定义的索引结构体的大小，显然这个大小不一定就是8的倍数。在我们的系统中，keysize = sizeof(usr_idx) =
4。这个keysize在32bit编译下是没有问题的，因为32bit编译只需要elem_base返回的地址可以被4整除即可，这也是为什么我们的程序在32bit编译下运行正常的原因。回想一下N年前的那个问题，其真正原因也就在这里：当时我定义的索引结构体的大小无法被4整除。在64bit编译下，keysize显然不能满足被8整除的要求，导致elem_base返回的地址只能被4整除。而xx_bptree_elem这个结构体的地址是严格要求必须可被8整除的。将一个只能被4整除而不能被8整除的地址强制转换为xx_bptree_elem元素地址并通过该强制类型转换后的地址访问xx_bptree_elem内部的元素显然就会导致core的出现了。

现在看来当初我的同事并未真正理解该B+ tree为何要求用户自定义结构体的大小必须为4的整数倍了，他只是通过现象得到了那条经验罢了，这笔技术债务也就从那时留了下来。

解决该问题并不难，作为基础库，我们无论如何都不应该依赖用户的自觉，我们在接口实现中增加一个转换就可以解决这一隐藏了若干年的Bug，将外面传入的keysize经align_word转换后再赋给tree->keysize，这样就可以保证elem_base始终返回合法的地址了。

突然想起了那句话：”出来混，总是要还的“，我们欠的技术债务也不例外。

日常开发中，我们为了辅助程序调试常常在每个函数的出入口(entry/exit)增加Trace，一般我们多用宏来实现这些Trace语句，例如：

#ifdef XX_DEBUG_
#define TRACE_ENTER() printf("Enter %s\n", __FUNCTION__)
#define TRACE_EXIT() printf("Exit %s\n", __FUNCTION__)
#else
#define TRACE_ENTER()
#define TRACE_EXIT()
#endif

有了TRACE_ENTER和TRACE_EXIT后，你就可以在你的函数中使用它们了。例如：
void foo(…) {
    TRACE_ENTER();
    … …
    TRACE_EXIT();
}

这样你就可以很容易看到函数的调用关系。不过这种手法用起来却不轻松。首先你需要在每个函数中手工加入TRACE_ENTER和TRACE_EXIT，然后再利用XX_DEBUG_宏控制其是否生效。特别是对于初期未添加函数级Enter/Exit Trace的项目，后期加入工作量很大。

不过Gcc给我们提供了另外一种方便的手法：使用GCC的-finstrument-functions选项。-finstrument-functions使得GCC在生成代码时自动为每个函数在入口和出口生成__cyg_profile_func_enter和__cyg_profile_func_exit两个函数调用。我们要做的就是给出一份两个函数的实现即可。最简单的实现莫过于打印出被调用函数的地址了：

/* func_trace.c */
__attribute__((no_instrument_function))
void __cyg_profile_func_enter(void *this_fn, void *call_site) {
    printf("enter func => %p\n", this_fn);
}

__attribute__((no_instrument_function))
void __cyg_profile_func_exit(void *this_fn, void *call_site) {
    printf("exit func <= %p\n", this_fn);
}

我们将这两个函数放入libfunc_trace.so：gcc -fPIC -shared -o libfunc_trace.so func_trace.c

我们为下面例子添加enter/exit级Trace：

/* example.c */
static void foo2() {

}

void foo1() {
    foo2();
}

void foo() {
    chdir("/home/tonybai");
    foo1();
}

int main(int argc, const char *argv[]) {
    foo();
    return 0;
}

$ gcc -g example.c -o example -finstrument-functions
$ LD_PRELOAD=libfunc_trace.so example
enter func => 0×8048524
enter func => 0x80484e5
enter func => 0x80484b2
enter func => 0×8048484
exit func <= 0×8048484
exit func <= 0x80484b2
exit func <= 0x80484e5
exit func <= 0×8048524

不过只输出函数地址很难让人满意，根据这些地址我们无法得知到底对应的是哪个函数。那我们就尝试一下将地址转换为函数名后再输出，这方面GNU依旧给我们提供了工具，它就是addr2line。addr2line是binutils包中的一个工具，它可以根据提供的地址在可执行文件中找出对应的函数名、对应的源码文件名以及行数。我们改造一下func_trace.c中的两个函数的实现：

/* func_trace.c */
static char path[PATH_MAX];

__attribute__((constructor))
static void executable_path_init() {
    char    buf[PATH_MAX];

    memset(buf, 0, sizeof(buf));
    memset(path, 0, sizeof(path));

#ifdef _SOLARIS_TRACE
    getcwd(buf, PATH_MAX);
    sprintf(path, "%s/%s", buf, getexecname());
#elif _LINUX_TRACE
    readlink("/proc/self/exe", path, PATH_MAX);
#else
    #error "The OS has not been supported!"
#endif
}

__attribute__((no_instrument_function))
void __cyg_profile_func_enter(void *this_fn, void *call_site) {
    char buf[PATH_MAX];
    char cmd[PATH_MAX];

    memset(buf, 0, sizeof(buf));
    memset(cmd, 0, sizeof(cmd));

    sprintf(cmd, "addr2line %p -e %s -f|head -1", this_fn, path);

    FILE *ptr = NULL;
    memset(buf, 0, sizeof(buf));

    if ((ptr = popen(cmd, "r")) != NULL) {
        fgets(buf, PATH_MAX, ptr);
        printf("enter func => %p:%s", this_fn, buf);
    }

    (void) pclose(ptr);
}

__attribute__((no_instrument_function))
void __cyg_profile_func_exit(void *this_fn, void *call_site) {
    char buf[PATH_MAX];
    char cmd[PATH_MAX];

    memset(buf, 0, sizeof(buf));
    memset(cmd, 0, sizeof(cmd));

    sprintf(cmd, "addr2line %p -e %s -f|head -1", this_fn, path);

    FILE *ptr = NULL;
    memset(buf, 0, sizeof(buf));

    if ((ptr = popen(cmd, "r")) != NULL) {
        fgets(buf, PATH_MAX, ptr);
        printf("exit func <= %p:%s", this_fn, buf);
    }

    (void) pclose(ptr);
}

在我的Ubuntu 10.04下，我们编译和执行

$ gcc -D_LINUX_TRACE -fPIC -shared -o libfunc_trace.so func_trace.c
$ gcc -g example.c -o example -finstrument-functions
$ LD_PRELOAD=libfunc_trace.so example
$ example
enter func => 0×8048524:main
enter func => 0x80484e5:foo
enter func => 0x80484b2:foo1
enter func => 0×8048484:foo2
exit func <= 0×8048484:foo2
exit func <= 0x80484b2:foo1
exit func <= 0x80484e5:foo
exit func <= 0×8048524:main

关于这个实现，还有几点要说道说道：
首先libfunc_trace.so是动态链接到你的可执行程序中的，那么如何获取addr2line所需要的文件名是一个问题；另外考虑到可执行程序中可能会调用chdir这样的接口更换当前工作路径，所以我们需要在初始化时就得到可执行文件的绝对路径供addr2line使用，否则会出现无法找到可执行文件的错误。在这里我们利用了GCC的__attribute__扩展：
__attribute__((constructor))

这样我们就可以在main之前就将可执行文件的绝对路径获取到，并在__cyg_profile_func_enter和__cyg_profile_func_exit中直接引用这个路径。

在不同平台下获取可执行文件的绝对路径的方法有不同，像Linux下可以利用"readlink /proc/self/exe"获得可执行文件的绝对路径，而Solaris下则用getcwd和getexecname拼接。

再总结一下，如果你想使用上面的libfunc_trace.so，你需要做的事情有：
1、将编译好的libfunc_trace.so放在某路径下，并export LD_PRELOAD=PATH_TO_libfunc_trace.so/libfunc_trace.so
2、你的环境下需要安装binutils的addr2line
3、你的应用在编译时增加-finstrument_functions选项。

我已经将这个小工具包放到了Google Code上，有兴趣的朋友可以在这里下载完整源码包（20110715更新：支持输出函数所在源文件路径以及所在行号，前提编译你的程序时务必加上-g选项）。