kfifo算法原理

[gin]

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

[gin]

相关源码链接：bootlin kfifo.h source