Linux内核中链表的使用

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

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

    这样在链表addr_list中就增加了新的链表节点。
4，遍历链表
   为什么不先讲删除节点，因为很多情况下都是先遍历链表，找到匹配的节点后再去删除的，所以先讲遍历链表，遍历链表分普通遍历和安全删除遍历，可见如果要删除链表结点我们就需要使用安全删除遍历。
    普通遍历,主要使用在当加入节点时判断是否有相同的结点存在，如果已存在就不需要再往下操作了，如下判断是否有相同的IP地址存在。
    #define list_for_each(pos, head) \
        for (pos = (head)->next; prefetch(pos->next), pos != (head); \
                pos = pos->next)

    struct list_head *p;
    struct ipstore *store;
    list_for_each(p, &addr_list)
    {
      store = list_entry(p, struct ipstore, list);
      if(store->addr[0] == ist->addr[0])
      {
          if(ist)
              kfree(ist);
          break;
      }
    }
    INIT_LIST_HEAD(&ist->list);
    list_add(&ist->list, &addr_list);
    ist就是上一步的链表结点指针，如果链表中有IP和新增节点IP地址相同的节点则释放刚分配的新节点空间，不进行任何操作，否则加入addr_list链表中。

    内核提供了一个比较简单的接口，可以在遍历的同时取出节点，此函数内部封装了list_entry():
    #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))
    所以以上例子可改成如下，这样就比较简洁了。
    struct ipstore *store;
    list_for_each_entry(store, &addr_list, list)
    {
      if(store->addr[0] == ist->addr[0])
      {
          if(ist)
              kfree(ist);
      
          return 0;
      }
    }

    再来看安全删除遍历接口：
    #define list_for_each_entry_safe(pos, n, head, member)          \
    for (pos = list_entry((head)->next, typeof(*pos), member),  \
        n = list_entry(pos->member.next, typeof(*pos), member); \
         &pos->member != (head);                    \
         pos = n, n = list_entry(n->member.next, typeof(*n), member))
    同样把上面的例子进行修改，这样删除时就不会破坏原有链表的结构出现“使用在释放后”的程序崩溃问题：
    struct ipstore *v, *n;
    list_for_each_entry_safe(v, n, &addr_list, list)
    {
        if(iph->saddr == v->addr[0])
        {
              list_del(&v->list);//删除节点
              kfree(v);//还需要注意的是list_del()只是把节点从链表中摘除，它并不释放其占用的内存，所以需要手动释放内存。
        }
    }
5，判空操作
    判空操作也比较重要，如果为空咱就什么都不操作，直接返回
    if(list_empty(&addr_list))
    {
        return 0;
    }

总结：到此为止对于内核链表的操作基本上可以满足日常需求了，当然内核还提供移动和合并链表操作、反向遍历链表操作的接口，具体可参考LKD3e.
      对链表的操作中一不小心就会出现“使用在释放后”的程序崩溃问题,请看如下使用普通遍历并删除的代码：
    DEFINE_RWLOCK(v4_rwlock);
    struct list_head *p;
    struct ipstore *store;
    list_for_each(p, &addr_list)
    {
        store = list_entry(p, struct ipstore, list);
        if(iph->saddr == store->addr[0])
        {
            read_lock(&v4_rwlock);
            list_del(&store->list);
            read_unlock(&v4_rwlock);

            kfree(store);

            return 0;
        }
    }

    这段代码虽然用了普通非安全遍历删除操作，但不会引起程序崩溃，但它已经埋下了安全隐患，不会崩溃是因为在删除链表并释放内存后直接return 0了，没再对目前的链表进行遍历移动操作，所以不会出现问题，万一哪天没return呢？。所以很多时间程序出现莫名崩溃问题都发现不了，我想这也许是个例子。
    在操作写数据时的好习惯是加一把锁，前面例子为了突出链表操作没把加解锁的代码贴出，这个例子中就有体现，首先定义了一把读写锁，在删除链表结点时加锁，删除完毕解锁。