好久没有看技术类的书籍了，今晚恰看到以前不知什么时候下到的一本oreilly的叫’mastering algorithms with c’的书，从书名可以看出这是一本讲算法的书，不过由于是选用了C语言作为讲解语言，所以难免不说说C语言。其中看到一节讲指针和数组，恰好碰到书中说: a[i][j] <=> *(*(a+i) + j)，这个等价式看起来显而易见，但是还是有些东西值得挖掘一下的。

我们都知道C语言定义的多维数组是’行主序’的，这意味着越靠右边的下标变换越快。a[i][j]形象的可以看成一个i行j列的矩阵，但是实际在内存中存储时，a[i][j]肯定不是矩阵存储，因为存储器可是线性下来的，至于a[i][j]各元素的存储位置我们可以通过测试获得，结果也验证了’行主序’的规则。

以a[2][3]为例，

#include <stdio.h>

int main() {
 int a[2][3] = {{1,2,3}, {4,5,6}};
 int i;
 int j;
 int k;
 int *p;

 for (i = 0; i < 2; i++) {
  for (j = 0; j < 3; j++) {
   printf("a[%d][%d] = %d; addr = [0x%X]\n", i, j, a[i][j], &a[i][j]);
  }

 }

 return 0;
}

输出结果：

a[0][0] = 1; addr = [0x23FE94]
a[0][1] = 2; addr = [0x23FE98]
a[0][2] = 3; addr = [0x23FE9C]
a[1][0] = 4; addr = [0x23FEA0]
a[1][1] = 5; addr = [0x23FEA4]
a[1][2] = 6; addr = [0x23FEA8]

从结果addr的规律看得出: 先排行元素，再排列元素。也就是说第一行排完，再来排第二行。

我们再来分析一下上面提到的那个等价式：a[i][j] <=> *(*(a+i) + j)，其实这里不一定要用常理分析，我们通过实验能得出一些结论：

#include <stdio.h>

int main() {
 int a[2][3] = {{1,2,3}, {4,5,6}};
 int i;
 int j;
 int k;
 int *p;

 for (i = 0; i < 2; i++) {
  for (j = 0; j < 3; j++) {
   printf("a[%d][%d] = %d; addr = [0x%X]\n", i, j, a[i][j], &a[i][j]);
  }

 }

 p = a;
 
 for (k =0 ; k < 6; k++) {
  printf("p[%d] = %d\n", k, p[k]);
 }

 printf("a+1 = 0x%X\n", a+1);
 printf("*(a+1) = 0x%X\n", *(a+1));
 printf("*(*(a+1)+2) = %d\n", *(*(a+1)+2));
 printf("*(a+1)+2 = 0x%X\n", *(a+1)+2);
 return 0;

}

输出结果：

a[0][0] = 1; addr = [0x23FE94]
a[0][1] = 2; addr = [0x23FE98]
a[0][2] = 3; addr = [0x23FE9C]
a[1][0] = 4; addr = [0x23FEA0]
a[1][1] = 5; addr = [0x23FEA4]
a[1][2] = 6; addr = [0x23FEA8]
p[0] = 1
p[1] = 2
p[2] = 3
p[3] = 4
p[4] = 5
p[5] = 6
a+1 = 0x23FEA0
*(a+1) = 0x23FEA0
*(*(a+1)+2) = 6
*(a+1)+2 = 0x23FEA8

这里关键的就是a+1 = 0x23FEA0以及*(a+1) = 0x23FEA0，奇怪了吧，加不加’*'号结果一致；实际上 *(*(a+i) + j)中的a + i是为了取第i行的首地址，按照常理用a+i即可了。但是由于是多维数组，取数组中某一元素的值，不仅要行还要列，那这么写: *((a +i) +j )能行吗？这就是当时C的设计者要考虑到问题了。显然*((a +i) +j )这么做欠妥，依然以上面的例子为例，我们再输出些信息瞧瞧：

printf("*((a+1)+2) = 0x%X\n", *((a+1) +2));

输出结果：
*((a+1)+2) = 0x23FEB8

这显然不是a[1][2]的值，0x23FEB8是什么呢，实际上是第四行的行首地址，当然在我们的程序中只有两行在合法的范围之内。好了，问题既然出现了，当时的C设计者就考虑要区别于这种情况，遂就如是做了: *(*(a+1)+2)；这样结果正确了，*(*(a+1)+2) = 6。至于当时C设计者的真实考虑我无从而知，权当逗乐打趣吧。

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

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

最近两天一直在一个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+树的操作很有可能就发生了，也就是说我们没有保证整个完整遍历过程的事务性。真相大白了。修改也容易了，但是由于库接口的不完备性，使得修改后的逻辑看起来也很别扭，业务层和底层库有交叉了。