gin
@gin
gin 发布的帖子
-
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
是链表元素的结构体类型;member
是list_head
在链表元素的结构体类型中定义的字段名称。对于内核中的通用性处理,我也会继续更新不同的内容。拜读大师们的作品,岂不乐乎?
-
-
kfifo算法原理
kfifo
的算法原理kfifo
本质上就是一个无锁队列,它的结构体如下:struct __kfifo { unsigned int in; unsigned int out; unsigned int mask; unsigned int esize; void *data; };
in
和out
分别指向入队和出队的位置。mask
等于队列长度减一。esize
是元素长度,也就是这个队列的颗粒度。队列默认的颗粒度是字节。讨论
mask
的作用,就不得不提及kfifo
的一个潜规则——队列长度一定为2的整数次幂。这样一来,对队列长度取模就可以直接利用mask & offset
的方法快速求得(取模运算耗时远高于位操作)。环形队列的一个关键问题就是——如何判断队列为空或者队列已经满了。一般的处理办法或许会在
in
和out
超过队列长度之后进行取模,让in
和out
两个指针始终保持在合法范围内。但是这就会产生一个难题——无法很简洁地区分队列为空和队列已满,因为这两个情况下都满足in==out
。此时就不得不在结构体里添加一个occupied_size
字段用来表示当前已入队的元素数量,这样显然并非最优解。而
kfifo
里是这样解决这个问题的:in
和out
不需要保证在合法范围内。此时就可以使用in-out
表示当前入队的元素数量。kfifo_put
和kfifo_get
的时候,需要对数组进行读写操作,此时数组的索引用in & mask
或out & mask
保证索引within range
。in
和out
的类型都是unsigned int
,它们溢出后不会有任何影响。因为对于unsigned int
这个类型而言,相减得到的结果是绝对值,所以比如说in
溢出后小于out
,但是in - out
得到的还是入队的元素数量。in == out
代表队列为空;in - out == mask + 1
表示队列已经满了。