• 好好学习,天天向上~
  • 欢迎欢迎~

linux学习18,内核是如何操作链表的

linux笔记 lcc 149℃ 0评论

上一节较为详细的介绍了 linux 内核中链表的设计与实现,能够看出,内核实际上是将链表“塞入”数据结构的。事实上,为了方便的操作这些链表,linux内核实现了一系列方法,本节将了解此。

链表的初始化

正如上一节介绍的,list_head 本身没有记录额外的信息,它仅仅起到连接各个数据节点的作用,所以在 linux 内核中,链表常常都是嵌入数据结构使用的,由这些数据结构存储需要记录的数据。例如将 list_head 嵌入 struct fox:

struct fox{
    int tail_len;
    int weight;
};
// 嵌入 list_head,构成链表节点。
struct fox{
    int tail_len;
    int weight;
    struct list_head list;
};

链表特别适合记录动态创建的数据,请看下面的C语言代码:

struct fox* rf;
rf = kmalloc(sizeof(struct fox), GFP_KERNEL);
rf->tail_length = 40;
rf->weight = 6;
INIT_LIST_HEAD(&rf->list);

实际上,程序中的多数元素都是在程序运行时动态创建的,若希望使用链表,则最好将其初始化,linux 内核提供了 INIT_LIST_HEAD() 函数用于初始化链表,它的C语言代码如下:

static inline void INIT_LIST_HEAD(struct list_head *list)
 {
     list->next = list;
     list->prev = list;
 }

可以看出,linux 内核初始化链表相当简单,就是让 list 的 prev 和 next 指针都指向自己而已。INIT_LIST_HEAD() 虽然很简单,但是却很有用,它可以避免 list 的 prev 和 next 指向未知的区域。

指针指向未知区域,是非常危险的。(为什么危险,可以参考我之前的文章。)

我们也可以直接使用 LIST_HEAD() 宏定义并初始化一个链表,它的 C语言代码如下,请看:

#define LIST_HEAD_INIT(name) { &(name), &(name) }
#define LIST_HEAD(name) \
    struct list_head name = LIST_HEAD_INIT(name)


该宏定义了一个名为 name 的链表,并按照 INIT_LIST_HEAD() 函数方式初始化了该链表。

向链表加入一个节点

以上介绍的是 linux 内核创建并初始化一个新链表的方法,如何将其加入已有的链表呢?linux 内核定义了 list_add() 函数,它的C语言代码如下,请看:

static inline void __list_add(struct list_head *new,
                   struct list_head *prev,
                   struct list_head *next)
{
     next->prev = new;
     new->next = next;
     new->prev = prev;
     prev->next = new;
 }
static inline void list_add(struct list_head *new, struct list_head *head)
{
     __list_add(new, head, head->next);
}


该函数往链表 head 节点后插入了 new 节点。从 __list_add() 函数可以看出,这一操作无非就是调整了各个链表节点的指向关系而已。

上一节我们说过,linux 内核使用的链表都是双向环形链表,所有没有“首尾”的概念,每个节点都可以当作 head 节点。

例如,假设有如 strcut fox* 型的节点 f,若想将其加入 fox_list 链表,可以这么做:

list_add(&f->list, &fox_list)

list_add_tail() 函数和 list_add() 函数是相似的,它的 C语言代码如下:

static inline void list_add_tail(struct list_head *new, struct list_head *head)
{
    __list_add(new, head->prev, head);
}

容易看出,与 list_add() 函数不同的是,list_add_tail() 函数是将 new 节点插入到 head 节点的前面。

从链表删除节点

既然有往链表加入节点的需求,也一定有从链表删除节点的需求,linux 内核是通过 list_del() 函数实现的,它的C语言代码如下:

static inline void __list_del(struct list_head * prev, struct list_head * next)
{
     next->prev = prev;
     prev->next = next;
}
#define LIST_POISON1  ((void *) 0x00100100)
#define LIST_POISON2  ((void *) 0x00200200)
static inline void list_del(struct list_head *entry)
{
     __list_del(entry->prev, entry->next);
     entry->next = LIST_POISON1;
     entry->prev = LIST_POISON2;
 }

__list_del() 函数是删除节点的核心部分,不过从C语言代码可以看出,它仅仅是将节点从链表移出而已,并没有释放该节点,也就是说,之后 linux 内核还能继续使用该节点中的数据。

list_del() 函数的后两行让被删除节点的 prev 和 next 指针指向指定值了,这两个值是非 NULL 值,但是也能引起页异常,避免调用者因为使用没有初始化的节点引发的错误。

遍历链表

上一节说过,链表适合记录需要遍历的数据,那么,linux 内核是怎样遍历链表的呢?答案是使用 list_for_each() 宏,它的C语言代码如下:

 #define list_for_each(pos, head) \
     for (pos = (head)->next; prefetch(pos->next), pos != (head); \
            pos = pos->next)


容易看出,list_for_each() 宏其实就是一个 for(;;) 循环的头而已,它从 head->next 开始遍历,每次让 post 指向下一个节点,遍历到 pos == head 结束(一圈,即全部链表节点)。

不过,list_for_each() 宏操作的都是 list_head,我们更常需要遍历的其实是存储数据的结构体,当然可以如下使用:

list_for_each(p, &fox_list){
    f = list_entry(p, struct fox, list);
    //...
}

但是,更方便的方法是使用 list_for_each_entry() 宏,它帮助我们找到结构体指针了,请看C语言代码:

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


如上一节介绍的一致,双向链表既可以往前遍历,也可以往后遍历。linux 内核提供了反向遍历的宏——其实就是在正向宏后加上 reverse 而已:

list_for_each_entry_reverse(pos, head, member)

遍历同时删除

以上遍历宏都是建立在链表结构不会改变的基础上的,也就是说标准的遍历过程中是不能删除节点的,否则接下来的遍历就找不到 next 或者 prev 指针了。一个解决方法就是在删除节点时,使用临时变量先将该节点的信息存储下来,事实上,linux 内核也的确是这么设计的,请看:

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


借助 list_for_each_entry_safe() 宏,我们就可以在遍历链表节点的同时删除它。

linux 内核操作链表非常关键的函数或者宏就介绍到这里。这里再延伸一点,使用上面介绍的方法遍历链表节点时,是不能有其他地方并发删除的,如果有,就应该做好同步。


linux学习18,内核是如何操作链表的 - 刘冲的博客(https://blog.popkx.com) 原创版权所有,转载请注明出处。
点赞 (0)分享 (0)
发表我的评论
取消评论
表情     4 + 7 = ? (必填)