Linux内核中链表的使用

上一篇 / 下一篇 2012-08-09 10:23:40 / 个人分类：Linux

　　链表是存放和操作可变数量元素的数据结构，它可在需要时动态创建结点并插入链表中，在编译时不需知道包含多少个元素，而且它在内存中也无须占用连续内存区。

"r.HKRFtfI0　　内核有许多链表的实现，而且还有其官方内核实现，所以在内核中使用链表时只要使用官方实现即可，可以说是方便、快捷、高效、安全。链表的基础知识可见K&R经典C程序设计语言。LKD3e对于内核数据结构的讲解无疑是经典的，但没有更实际的例子以至看后印象不是很深，现通过LKD3e为指明方向，增加实际例子讲解内核链表是如何操作的。51Testing软件测试网5@tP]g'zW

tH\x&V0　　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结构取包含其的节点数据。51Testing软件测试网,zgZ&J)?!p

Ku(mQ`\'N[0 51Testing软件测试网PC.HMpC

#define list_entry(ptr, type, member) \
%}(Bg|U8}s\0 container_of(ptr, type, member)

    #define container_of(ptr, type, member) ({          \
?7fIg8L0    const typeof( ((type *)0)->member ) *__mptr = (ptr);    \51Testing软件测试网T6z)sR%N n#]+n
    (type *)( (char *)__mptr - offsetof(type,member) );})

　　LKD3e上描述说：在C语言中，一个给定结构中的变量偏移在编译时地址就被ABI固定下来。也就是说定义的一个结构体变量地址再加上偏移地址就能知道各成员的地址了。

'Cu7Ok*]c+e4Pne0　　2、定义一个链表

　　链表使用之前需要初始化。一般使用链表的情况是定义一个全局链表头，并将其初始化。ip地址和时间挂钩的情况很多时候都可用到，所以现以一个包含ip地址和一个时间的结构体为例演示内核链表是如何操作使用的。题外话，把存放ip地址的成员定义成4个__u32大小的数组是为了支持ipv6地址，因为ipv6地址是128bit，4*32刚好是128bit，如果是ipv4地址只用数组的第0个成员足够了，本文只讲解v4地址的比较。51Testing软件测试网z{]p%|L!c

$K!V-Nkm0

typedef unsigned int __u32

    struct ipstore{51Testing软件测试网ElIeI*Jg2e
    unsigned long time;51Testing软件测试网x%_z_(M
    __u32 addr[4];
't'`H y Veeo5R0    struct list_head list;
    };

y%jJ3q8o0 static LIST_HEAD(addr_list);51Testing软件测试网AA;mzVj1l

　　这样就定义了一个名为addr_list链表头，LIST_HEAD本身是宏，它已对addr_list进行了初始化：

p@F4n5WL&^Pg0#define LIST_HEAD_INIT(name) { &(name), &(name) }51Testing软件测试网5c%[H6fa2Wg

P8q)?8|-` l;SHc0 #define LIST_HEAD(name) \51Testing软件测试网i"lLqy~%[
struct list_head name = LIST_HEAD_INIT(name)51Testing软件测试网~[5@c9L

3k(_8|%z0~d"{4a0　　如果是动态创建链表结点，使用运行时初始化：51Testing软件测试网3f%F B#VeN+{

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);
    }

　　要调用此函数，只要在上一步后面接上：51Testing软件测试网 P$d E6C:gN

+Zbox$~bg\#c}0

list_add(&ist->list, &addr_list);

gJ(w9]1?-p]5o RO0　　完整的增加操作：

ZOp_5Qz;}/YF0 51Testing软件测试网1|m(nv-u

　　这样在链表addr_list中就增加了新的链表节点。

"_4K-M0u#o0b!]0　　4、遍历链表

TD/]]+h{3|-q0　　为什么不先讲删除节点，因为很多情况下都是先遍历链表，找到匹配的节点后再去删除的，所以先讲遍历链表，遍历链表分普通遍历和安全删除遍历，可见如果要删除链表结点我们就需要使用安全删除遍历。

'F Kak!o`5@0　　普通遍历,主要使用在当加入节点时判断是否有相同的结点存在，如果已存在就不需要再往下操作了，如下判断是否有相同的IP地址存在。51Testing软件测试网$z$iS$`q {1[

_wt{|4sN` ^0 51Testing软件测试网5E7c-\5Fj

#define list_for_each(pos, head) \
5BPh'Yc%C:PUX%wj0 for (pos = (head)->next; prefetch(pos->next), pos != (head); \
&lx1j:}@ `B+g0 pos = pos->next)

U5A6Am*|!A$MT0    struct list_head *p;
B6Or!T0A h0    struct ipstore *store;
(Q&|P7}/i)T0    list_for_each(p, &addr_list)51Testing软件测试网2j X`|b~%h
    {
K)h#F3g*[g#\%[j)J{P/a J[0      store = list_entry(p, struct ipstore, list);51Testing软件测试网A+zTO'XEB
      if(store->addr[0] == ist->addr[0])
/tyVn_~#O0      {51Testing软件测试网bqy9RV*@C7i
          if(ist)
#qh;m2GVa1b*{0              kfree(ist);
0~n-f'Q5p7_f/f0          break;
      }51Testing软件测试网[mE@TS
    }
f jr1r)Y6MZO0    INIT_LIST_HEAD(&ist->list);
    list_add(&ist->list, &addr_list);

`/R{ K$} O4]'|Egn0　　ist就是上一步的链表结点指针，如果链表中有IP和新增节点IP地址相同的节点则释放刚分配的新节点空间，不进行任何操作，否则加入addr_list链表中。

　　内核提供了一个比较简单的接口，可以在遍历的同时取出节点，此函数内部封装了list_entry()：51Testing软件测试网?8rG3jX*UM

#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))

　　所以以上例子可改成如下，这样就比较简洁了。51Testing软件测试网_+TN1qN)?i

p^,J"T&G0 51Testing软件测试网UD}5D8VbG

struct ipstore *store;
    list_for_each_entry(store, &addr_list, list)
    {
      if(store->addr[0] == ist->addr[0])
      {
          if(ist)
              kfree(ist);

          return 0;
      }
    }

　　再来看安全删除遍历接口：

!EH,j,HE0F0

#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))

　　同样把上面的例子进行修改，这样删除时就不会破坏原有链表的结构出现“使用在释放后”的程序崩溃问题：51Testing软件测试网R}amf

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、判空操作

7GQZR9z M5N0　　判空操作也比较重要，如果为空咱就什么都不操作，直接返回

nI&EfT+\3c5tm0

if(list_empty(&addr_list))
    {
        return 0;
    }

}G!G _2H/BB0　　总结：到此为止对于内核链表的操作基本上可以满足日常需求了，当然内核还提供移动和合并链表操作、反向遍历链表操作的接口，具体可参考LKD3e.51Testing软件测试网pp8?Uj t

　　对链表的操作中一不小心就会出现“使用在释放后”的程序崩溃问题,请看如下使用普通遍历并删除的代码：51Testing软件测试网u|1V+J3c\

Oj:^'kn d;[#`-{0

DEFINE_RWLOCK(v4_rwlock);
    struct list_head *p;51Testing软件测试网;|,F0f#WHrU
    struct ipstore *store;51Testing软件测试网!OfR#os
    list_for_each(p, &addr_list)
    {
-TT1A4c [`0        store = list_entry(p, struct ipstore, list);51Testing软件测试网)xQW.Cu\-K
        if(iph->saddr == store->addr[0])51Testing软件测试网|^-ZB L ~ O
        {51Testing软件测试网K*ku!{i:c#SG
            read_lock(&v4_rwlock);51Testing软件测试网:} V8I1h Y&W@
            list_del(&store->list);
OcH$bj+zf/gg0            read_unlock(&v4_rwlock);

kfree(store);

5MWp0jG.L3@0            return 0;
        }
    }51Testing软件测试网a5l$V2PE

NJpFlm J*y0N0　　这段代码虽然用了普通非安全遍历删除操作，但不会引起程序崩溃，但它已经埋下了安全隐患，不会崩溃是因为在删除链表并释放内存后直接 return 0了，没再对目前的链表进行遍历移动操作，所以不会出现问题，万一哪天没return呢？。所以很多时间程序出现莫名崩溃问题都发现不了，我想这也许是个例子。

　　在操作写数据时的好习惯是加一把锁，前面例子为了突出链表操作没把加解锁的代码贴出，这个例子中就有体现，首先定义了一把读写锁，在删除链表结点时加锁，删除完毕解锁。51Testing软件测试网&kK-Iw;y_5`

收藏举报

TAG:

查看全部评论

bob123654

不要让那些真正对你好的人，慢慢的从你的生活中消失，无论爱情还是友情，都需要用心经营。

Linux内核中链表的使用

用户菜单

我的栏目

标题搜索

日历

我的存档

数据统计

RSS订阅