Linux2.6.36内核源码中链表、红黑树实现风格的讨论

1、结构中包含数据 vs 数据中包结构

个人以为，一般程序员，要么写专用的数据与结构一体的程序，要么写通用的结构，留一个空指针以适应不同的数据。前者违反了DRY原则，大项目中不太可取。后者的遗憾是要强转类型，还要多操心一层内存管理。后者在mysql源码中可以看到，mysql里的list正是用了一个空类型指针。

而Linux一反常态，提供基本数据结构，让数据去包含结构。这种方案有好处也有坏处，让我们对比一下：

• Linux方案节约了一个空类型指针所占存储空间；
• 进而减少一层内存管理（销毁节点即同时销毁了数据和结构信息）；
• 并且避免了空类型指针的强制转换；
• 但Linux方案要用一些宏来实现根据节点获取数据，这些宏不利于调试维护，并且有陷阱（见下文）；
• 因为数据的不确定性，一些数据结构与算法的实现并不完整，使用这些lib要对其有足够的了解，用软件工程的视角来看就是解耦很差，封装性不好；

Linux的编程风格有很多并不符合近来越来越被重视的软件工程学。看Linux源码只有一个感觉，为了让系统飙起来，不择手段，管你好不好维护呢。在看Linux内核的list实现时我就发现，其宏存在一个陷阱。让我们看下这个宏：

#define list_for_each_entry(pos, head, member)              \
	    for (pos = list_entry((head)->next, typeof(*pos), member);   \
	         prefetch(pos->member.next), &pos->member != (head);  \
	         pos = list_entry(pos->member.next, typeof(*pos), member))

这个宏的用法类似于其它语言中的forEach之类的循环，比如下面的代码：

struct my_data {
    int value;
    list_head node;
};
//...
struct my_data *pos;
struct list_head *head;
//...
list_for_each_entry(pos, head, node) {
    //...
}
if (pos != NULL) printf("%d\n", pos->value);

在我们的编程习惯中，循环遍历结束后，数据指针（pos）要么是最后一个值，要么是NULL。可是这里，如果我们有一个专门的链表头，即专门用一个list_head做头，而没有用无数据的my_data做头的话，上面的代码就会Segment fault了。因为这段宏编写的循环语句执行完成后，pos将指向一个非法地址，也就是说pos所指的地址并不对应一个struct my_data类型的数据。具体原因在于，Linux的这个链表实现是双向循环链表，遍历结束实际上是遍历回到了表头。这时list_for_each_entry宏并没有将pos置为NULL。pos的计算需要参考list_entry宏，这个宏根据node成员在my_data结构体中的偏移来根据node的地址推算my_data的地址（这正是Linux可以反过来让数据结构只需包含一个list_head成员即可享用链表的magic所在）。问题是如果链表头仅仅是一个list_head，并非包含于my_data中，推出来的地址就指向了不可知的内存数据，引用它是很危险的。

从而可见，Linux内核编码的风格是假定写代码的都是高手、熟手，对各个相关部分代码都很了解。这也许是OS开发与常规项目的不同之处，这里无法用软件工程的思想去看，否则Linux源码就是个地狱般的工程。

2、解耦与封装

Linux红黑树的实现直接是个残肢，以至于作者在注释中写了应用示范代码（应该是从真实代码中拷过来的）供参考。这用软件工程的视角来看这简直说不通。可是Linux就是这样。不知道其它系统的源码风格是怎样的，抽空再去对照着看看FreeBSD的源码。至于Windows，听说是反对使用goto之类的语句的，相信应该更注重软件工程（Linux单红黑树的实现就多处用到了goto）。

struct my_data {
    int value;
    list_head node;
};
//...
struct my_data *pos;
struct list_head *head;
//...
list_for_each_entry(pos, head, node) {
    //...
}
if (pos != NULL) printf("%d\n", pos->value);

在我们的编程习惯中，循环遍历结束后，数据指针（pos）要么是最后一个值，要么是NULL。可是这里，如果我们有一个专门的链表头，即专门用一个list_head做头，而没有用无数据的my_data做头的话，上面的代码就会Segment fault了。

struct my_data {
    int value;
    list_head node;
};
//...
struct my_data *pos;
struct list_head *head;
//...
list_for_each_entry(pos, head, node) {
    //...
}
if (pos != NULL) printf("%d\n", pos->value);

你要用Linux的list_head的话，就一定要留一个专门作表头，你违反了它的用法，怎么能说是“陷阱”？ 在我看来，Linux的链表实现比其他大多数系统都优雅很多，可以说整个Linux内核的各种复杂关系如果没有这么一个高超的链表实现将会是一团糟。

单单是免去node的内存管理，可以减少无数的野指针风险。各种for_each宏使C代码看起来就像具备了高级语言才有的“闭包”功能，大大提高了可读性以及降低出错几率。

struct my_data {
    int value;
    list_head node;
};
//...
struct my_data *pos;
struct list_head *head;
//...
list_for_each_entry(pos, head, node) {
    //...
}
if (pos != NULL) printf("%d\n", pos->value);

当然用了专门的表头，即然是专门的表头，配合Linux节约内存的出发点，应该仅用一个list_head就行了吧，那么list_for_each_entry遍历完之后，pos指向表头所在的container里，就成了非法指针。

如果你告诉我表头也要用含数据的结构体，那就算了，我情愿自己留意循环外不要再用pos。