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
表示队列已经满了。