内核数据结构贯穿于整个内核代码中，这里介绍4个基本的内核数据结构。
利用这4个基本的数据结构，可以在编写内核代码时节约大量时间。
主要内容：
1. 链表
链表是linux内核中最简单，同时也是应用最广泛的数据结构。
内核中定义的是双向链表。
1.1 头文件简介
内核中关于链表定义的代码位于： include/linux/list.h
list.h文件中对每个函数都有注释，这里就不详细说了。
其实刚开始只要先了解一个常用的链表操作（追加，删除，遍历）的实现方法，
其他方法基本都是基于这些常用操作的。
1.2 链表代码的注意点
在阅读list.h文件之前，有一点必须注意：linux内核中的链表使用方法和一般数据结构中定义的链表是有所不同的。
一般的双向链表一般是如下的结构，
具体见下图：
传统的链表有个最大的缺点就是不好共通化，因为每个node中的data1，data2等等都是不确定的(无论是个数还是类型)。
linux中的链表巧妙的解决了这个问题，linux的链表不是将用户数据保存在链表节点中，而是将链表节点保存在用户数据中。
linux的链表节点只有2个指针(pre和next)，这样的话，链表的节点将独立于用户数据之外，便于实现链表的共同操作。
具体见下图：
linux链表中的最大问题是怎样通过链表的节点来取得用户数据？
和传统的链表不同，linux的链表节点(node)中没有包含用户的用户data1，data2等。
整个list.h文件中，我觉得最复杂的代码就是获取用户数据的宏定义
#define list_entry(ptr, type, member) \container_of(ptr, type, member)
这个宏没什么特别的，主要是container_of这个宏
#define container_of(ptr, type, member) ({\const typeof(((type *)0)->member)*__mptr = (ptr); \(type *)((char *)__mptr – offsetof(type, member)); })
这里面的type一般是个结构体，也就是包含用户数据和链表节点的结构体。
ptr是指向type中链表节点的指针
member则是type中定义链表节点是用的名字
比如：
struct student{int id;char* name;struct list_head list;};
下面分析一下container_of宏:
// 步骤1：将数字0强制转型为type*，然后取得其中的member元素((type *)0)->member // 相当于((struct student *)0)->list(((type *)0)->member)*__mptr = (ptr);// 步骤3：计算member字段距离type中第一个字段的距离，也就是type地址和member地址之间的差offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)// 步骤4：将__mptr的地址 – type地址和member地址之间的差// 其实也就是获取type的地址
步骤1，2，4比较容易理解，下面的图以sturct student为例进行说明步骤3：
首先需要知道 ((TYPE *)0) 表示将地址0转换为 TYPE 类型的地址
由于TYPE的地址是0，所以((TYPE *)0)->MEMBER 也就是 MEMBER的地址和TYPE地址的差，如下图所示：
1.3 使用示例
构造了一个内核模块来实际使用一下内核中的链表，网站空间，代码在CentOS6.3 x64上运行通过。
C代码：
#include<linux/init.h>#include<linux/slab.h>#include<linux/module.h>#include<linux/kernel.h>#include<linux/list.h>MODULE_LICENSE();struct student{int id;char* name;struct list_head list;};void print_student(struct student*);static int testlist_init(void){struct student *stu1, *stu2, *stu3, *stu4;struct student *stu;// init a list head LIST_HEAD(stu_head);// init four list nodesstu1 = kmalloc(sizeof(*stu1), GFP_KERNEL);stu1->id = 1;stu1->name = ;INIT_LIST_HEAD(&stu1->list);stu2 = kmalloc(sizeof(*stu2), GFP_KERNEL);stu2->id = 2;stu2->name = ;INIT_LIST_HEAD(&stu2->list);stu3 = kmalloc(sizeof(*stu3), GFP_KERNEL);stu3->id = 3;stu3->name = ;INIT_LIST_HEAD(&stu3->list);stu4 = kmalloc(sizeof(*stu4), GFP_KERNEL);stu4->id = 4;stu4->name = ;INIT_LIST_HEAD(&stu4->list);// add the four nodes to headlist_add (&stu1->list, &stu_head);list_add (&stu2->list, &stu_head);list_add (&stu3->list, &stu_head);list_add (&stu4->list, &stu_head);// print each student from 4 to 1list_for_each_entry(stu, &stu_head, list){print_student(stu);}// print each student from 1 to 4list_for_each_entry_reverse(stu, &stu_head, list){print_student(stu);}// delete a entry stu2list_del(&stu2->list);list_for_each_entry(stu, &stu_head, list){print_student(stu);}// replace stu3 with stu2list_replace(&stu3->list, &stu2->list);list_for_each_entry(stu, &stu_head, list){print_student(stu);}return 0;}static void testlist_exit(void){printk(KERN_ALERT );printk(KERN_ALERT );printk(KERN_ALERT );}void print_student(struct student *stu){printk (KERN_ALERT );printk (KERN_ALERT , stu->id);printk (KERN_ALERT , stu->name);printk (KERN_ALERT );}module_init(testlist_init);module_exit(testlist_exit);
Makefile：
做对的事情比把事情做对重要。
