记得以前曾经两次谈到过内存对齐话题，一次在'也谈内存对齐'一文中，另一次则是'也谈内存对齐(续)'，今天下午和同事又谈到内存对齐的问题了，遂想继续挖掘下去，看看其背后的故事。

关于内存对齐的中文文章多在介绍对齐的'法则'，比如为什么sizeof(T)和我们估计的T的大小有出入呢等等，而对于内存对齐的本质少有介绍，我在Google上搜索了一阵后，在IBM开发社区上发现一篇叫'Data alignment: Straighten up and fly right'的文章，其中就有我想知道的关于'内存对齐背后的故事'，下面的很多内容都是来自那篇文章的。

很多书籍中都讲到：内存可以看成一个byte数组，我们通过编程语言提供的工具对这个'大数组'中的每个元素进行读写，比如在C中我们可以用指针一次读写一个或者更多个字节，这是我们一般程序员眼中的内存样子。但是从机器角度更具体的说从CPU角度看呢，CPU发出的指令是一个字节一个字节读写内存吗？答案是'否'。CPU是按照'块(chunk)'来读写内存的，块的大小可以是2bytes, 4bytes, 8bytes, 16bytes甚至是32bytes. 这个CPU访问内存采用的块的大小，我们可以称为'内存访问粒度'。

程序员眼中的内存样子：

———————————
| | | | | | | | | | | | | | | | |
———————————
 0 1 2 3 4 5 6 7 8 9 A B C D E F  (地址)

CPU眼中的内存样子：(以粒度＝4为例)
———————————————
| | | | |   | | | | |   | | | | |   | | | | |
———————————————
 0 1 2 3     4 5 6 7     8 9 A B     C D E F  (地址)

有了上面的概念，我们来看看粒度对CPU访问内存的影响。

假设这里我们需要的数据分别存储于地址0和地址1起始的连续4个字节的存储器中，我们目的是分别读取这些数据到一个4字节的寄存器中，

如果'内存访问粒度'为1，CPU从地址0开始读取，需要4次访问才能将4个字节读到寄存器中；
同样如果'内存访问粒度'为1，CPU从地址1开始读取，也需要4次访问才能将4个字节读到寄存器中；而且对于这种理想中的''内存访问粒度'为1的CPU，所有地址都是'aligned address'。

如果'内存访问粒度'为2，CPU从地址0开始读取，需要2次访问才能将4个字节读到寄存器中；每次访存都能从'aligned address'起始。
如果'内存访问粒度'为2，CPU从地址1开始读取，相当于内存中数据分布在1,2,3,4三个地址上，由于1不是'aligned address'，所以这时CPU要做些其他工作，由于这四个字节分步在三个chunk上，所以CPU需要进行三次访存操作，第一次读取chunk1(即地址0,1上两个字节，而且仅仅地址1上的数据有用)，第二次读取chunk2(即地址2,3上两个字节，这两个地址上的数据都有用)，最后一次读取chunk3(即地址5,6上两个字节，而且仅仅地址5上的数据有用)，最后CPU会将读取的有用的数据做merge操作，然后放到寄存器中。

同理可以推断如果'内存访问粒度'为4，那么从地址1开始读取，需要2次访问，访问后得到的结果merge后放到寄存器中。

是不是所有的CPU都会帮你这么做呢，当然不是。有些厂商的CPU发现你访问unaligned address，就会报错，或者打开调试器或者dump core，比如sun sparc solaris绝对不会容忍你访问unaligned address，都会以一个core结束你的程序的执行。所以一般编译器都会在编译时做相应的优化以保证程序运行时所有数据都是存储在'aligned address'上的，这就是内存对齐的由来。

我们可以指定按照何种粒度访问特定内存块儿：其中void *T为指向特定内存块的地址指针
char *p = (char*)T；每次操作一个字节
short *p = (short*)T；每次操作两个字节
int *p = (int*)T；每次操作4个字节
以此类推。

在'Data alignment: Straighten up and fly right'这篇文章中作者还得出一个结论那就是："如果访问的地址是unaligned的，那么采用大粒度访问内存有可能比小粒度访问内存还要慢"。

最近自己曾经辛苦耕耘过的两个项目同时上线，相关问题也就逐渐暴露出来。工作这两年多时间以后，使我有这样感觉：’测试永远都是不完备的’，有些问题只能在商用过程中发现，呵呵，明确一点啊我不是搞测试的:)

在解决问题过程中的感悟往往是最深刻的，解决问题的过程往往真的像是警察在侦破案件，往往一点点罪犯留下的蛛丝马迹就会让神探们找到线索，并迅速破案。

最近两天一直在一个bug上煎熬着，终于于昨天发现蛛丝马迹并醒悟过来，很有意思的一个bug，和大家一起来分享一下。

这周三我们组的一个同事在现网商用运行的系统上发现我们的程序出现了一个core，对于unix后台服务程序来说，出core是一件很严重的事情，而这个core也直接导致了进程的死锁，消息的积压。

通过gdb调试core发现，问题出在遍历一棵放在共享内存中的B+树，从B+树中取出的地址是一个无效地址，所以当使用memcpy拷贝这个地址上的数据时core出现了。

说到这不能不提及一些背景资料了，在开发这个项目的时候，我们在实现业务需求的时候发现需要部门B+树操作库提供一个完备的遍历接口，可是却发现已有的B+树接口并不提供遍历功能，这显然是库接口的不完备造成的，大家都知道树的遍历是一个特别常见的功能。我们决定对该库进行扩充，添加一个遍历接口；不过，我们在添加接口的时候发现，库内部提供一个叫get_next_key的内部接口，但是该接口的问题在于它返回的下一个key并不是总存储有效数据的。按我们的正常逻辑，如果我们提供一个get_next_key，如果遍历到最后一个有效节点后再继续遍历，则应该返回NOT_FOUND之类的返回值，而这个库中的get_next_key仍然给你返回一个空闲节点，而这个节点中的数据是随机值。了解到这种情况，考虑到时间原因，我定义了一个xx_get_next_key的外部接口，在这个接口实现中我仍然选择使用get_next_key来辅助工作，并且在xx_get_next_key的接口说明中解释到需要业务层控制调用xx_get_next_key的次数。

比如说如果目前B+树中有100个有效节点，那么我调用100次xx_get_next_key均会返回有效节点，如果再100次后继续调用该接口，返回的可能就是非有效数据了。

这样在业务层，我写下了如下代码：
int get_default_xx_info(…) {
 int total = 0;
 int i     = 0;
 xx_get_bptree_msgc(&total);

 for (i =0 ; i < total; i++) {
  调用xx_get_next_key遍历B+树；
 }
}

就是这样的代码在系统运行很长时间后出问题了，通过gdb跟踪到xx_get_next_key的内部实现中，最开始我怀疑是不是对以前的B+树操作库不熟悉，代码调用的不对，后经确认，xx_get_bptree_msgc的实现代码无误。而咋一眼看上去业务层的逻辑也没有问题亚。在查了一个下午之后，仍然没有结果。第二天继续，结合日志和GDB跟踪输出，发现这样的一个很奇怪的现象，而且在我们的分布式系统的两台机器上现象是一致的。

通过日志看出，在调用get_default_xx_info之前，日志打印出来当前B+树中有12610个有效数据节点；而通过GDB跟踪栈上信息，发现B+树中的有效节点是12609个。也就是说我们通过xx_get_bptree_msgc调用得到total值是12610个，而在多次调用xx_get_next_key的间隙时间里，B+树中的节点被其他进程删除了，前面我们提到过我们的B+树是进程间共享的。这样的话，xx_get_next_key使用的约束条件被破坏了，发生了多一次的调用，问题应该就在这。的确，在xx_get_next_key内部执行时是有写锁保证其他进程不会对B+树进行修改的，但是当xx_get_next_key结束一次执行，释放锁资源后，阻塞在该锁上的其他进程对B+树的操作很有可能就发生了，也就是说我们没有保证整个完整遍历过程的事务性。真相大白了。修改也容易了，但是由于库接口的不完备性，使得修改后的逻辑看起来也很别扭，业务层和底层库有交叉了。