kernel list实现技巧



  • kernel list实现技巧

    偶然间,翻到了一篇帖子下的评论说内核中的链表官方实现很巧妙,具有强大的通用性。于是我动手打开源码开始研究,内核链表实现通用性的方法与kfifo不仅异曲同工,甚至更加简洁优雅,实在是令我叹为观止。

    内核中维护的链表节点定义如下,非常简洁:

    struct list_head {
        struct list_head *next, *prev;
    };
    

    那么这个链表节点如何使用呢?巧妙之处又在哪里呢?

    这里总结一下最朴素的链表实现方法,假设现在我们需要维护一个元素类型为apple的链表,我们一般会将链表元素定义为如下结构体:

    struct apple {
        unsigned int weight;
        char name[30];
        ...
        struct apple *next, *prev;
    };
    

    这样实现有什么问题呢?

    • 通用性和代码可复用性。这样一来我们每定义一个类型的链表元素类型,都需要重新写一套新的API提供链表操作(插入,删除等)。

    • 链表元素不能多样化。这样的实现方法就不可能满足链表元素多样化的需求。

    Think outside the box! 这是我对内核链表官方实现的概括。这个implementation并不像kfifo一样exploit编译器的功能,相反,它是源自于算法层面的思考。我们一般的链表实现都是将元素插入链表里,但是内核链表官方实现的原理却是将共同的部分提取出来作为list_head,而每个list_head就相当于一个个衣架,而我们想要存储的元素就是一件件衣服,整个链表就是一个晾衣绳上用衣架挂着很多衣服。

    如何从kernel list中获得元素?

    内核中提供了list_entry这个API用来访问某个list_head对应的链表元素。其定义如下:

    #define list_entry(ptr, type, member)     container_of(ptr, type, member)
    

    其中ptr是从内核链表中获得的一个list_head指针;type是链表元素的结构体类型;memberlist_head在链表元素的结构体类型中定义的字段名称。

    对于内核中的通用性处理,我也会继续更新不同的内容。拜读大师们的作品,岂不乐乎?



  • 源码见链接:bootlin kernel list source



  • 此回复已被删除!

 

Copyright © 2018 bbs.dian.org.cn All rights reserved.

与 Dian 的连接断开,我们正在尝试重连,请耐心等待