Linux内核中链表的使用
《Linux内核中链表的使用》
本文档的Copyleft归rosetta所有，使用GPL发布，可以自由拷贝、转载，转载时请保持文档的完整性。
参考资料：LKD3e,linux-2.6.27源码
来源：http://blog.csdn.net/rosetta

    链表是存放和操作可变数量元素的数据结构，它可在需要时动态创建结点并插入链表中，在编译时不需知道包含多少个元素，而且它在内存中也无须占用连续内存区。
    内核有许多链表的实现，而且还有其官方内核实现，所以在内核中使用链表时只要使用官方实现即可，可以说是方便、快捷、高效、安全。链表的基础知识可见K&R经典C程序设计语言。LKD3e对于内核数据结构的讲解无疑是经典的，但没有更实际的例子以至看后印象不是很深，现通过LKD3e为指明方向，增加实际例子讲解内核链表是如何操作的。
1，链表数据结构
    头文件<linux/list.h>
    数据结构：  
    struct list_head {
      struct list_head *next；
      struct list_head  *prev;
    };

    需要理解的是内核不是将数据结构插进链表，而是将链表节点插入数据结构，也就是说我们自己定义的每个结构体里面都含有一个struct list_head结构体成员，用其指向链表的下一个节点和上一个节点,它并没有把数据本身插入到链表中。而我们其实只对数据感兴趣，对于struct list_head来说只是一个链接前后节点的工具，那么如何取其数据呢？内核实现是把每个struct list_head和一个数据节点挂勾（也就每个节点中包含struct list_head的原因），通过list_entry()宏即可通过struct list_head结构取包含其的节点数据。
    #define list_entry(ptr, type, member) \
    container_of(ptr, type, member)

    #define container_of(ptr, type, member) ({          \
    const typeof( ((type *)0)->member ) *__mptr = (ptr);    \
    (type *)( (char *)__mptr - offsetof(type,member) );})
    LKD3e上描述说：在C语言中，一个给定结构中的变量偏移在编译时地址就被ABI固定下来。也就是说定义的一个结构体变量地址再加上偏移地址就能知道各成员的地址了。
2，定义一个链表
    链表使用之前需要初始化。一般使用链表的情况是定义一个全局链表头，并将其初始化。ip地址和时间挂钩的情况很多时候都可用到，所以现以一个包含ip地址和一个时间的结构体为例演示内核链表是如何操作使用的。题外话，把存放ip地址的成员定义成4个__u32大小的数组是为了支持ipv6地址，因为ipv6地址是128bit,4*32刚好是128bit，如果是ipv4地址只用数组的第0个成员足够了，本文只讲解v4地址的比较。
    typedef unsigned int __u32

    struct ipstore{
    unsigned long time;
    __u32 addr[4];
    struct list_head list;
    };

    static LIST_HEAD(addr_list);

    这样就定义了一个名为addr_list链表头，LIST_HEAD本身是宏，它已对addr_list进行了初始化：
    #define LIST_HEAD_INIT(name) { &(name), &(name) }

    #define LIST_HEAD(name) \
        struct list_head name = LIST_HEAD_INIT(name)

    如果是动态创建链表结点，使用运行时初始化：
    struct ipstore *ist;
    ist = kmalloc(sizeof (*ist), GFP_ATOMIC);
    if(!ist)
    {
        printk("kmalloc failed.\n");
        return -1;
    }
    
    ist->time = jiffies+time*HZ;
    ist->addr[0] = 0xc0a80101;//IP:192.168.1.1
    INIT_LIST_HEAD(&ist->list);
    此时ist就是一个指向已初始化完成并有数据的ipstore结构体结点，其struct list_head成员list已初始化。
3，在链表中增加一个节点
    static inline void list_add(struct list_head *new, struct list_head *head)
    {   
        __list_add(new, head, head->next);
    }
    要调用此函数，只要在上一步后面接上：
    list_add(&ist->list, &addr_list);

    完整的增加操作：
    struct ipstore *ist;
    ist = kmalloc(sizeof (*ist), GFP_ATOMIC);
    if(!ist)
    {
        printk("kmalloc failed.\n");
        return -1;
    }
    
    ist->time = jiffies+time*HZ;
    ist->addr[0] = 0xc0a80101;//IP:192