内核队列

一、kfifo原理

kfifo实现原理是采用循环（环形）队列。

1
2
3
4
5
6
7

struct kfifo
{
    unsigned char *buffer; / *保存数据的缓冲区* /
    unsigned int size;      / *分配的缓冲区的大小* /
    unsigned int in;        / *数据以偏移量(in%size)添加* /
    unsigned int out;       / *数据从off中提取。(out%size)* /
};

二、kfifo特点

1、采用环形缓冲区来实现，提供一个无边界的字节流服务。采用环形缓冲区的好处为，当一个数据元素被用掉后，其余数据元素不需要移动其存储位置，从而减少拷贝提高效率。

2、保证缓冲区大小为2的次幂，不是的向上取整为2的次幂（很重要）。

3、使用无符号整数保存输入(in)和输出(out)的位置，在输入输出时不对in和out的值进行模运算，而让其自然溢出，并能够保证in-out的结果为缓冲区中已存放的数据长度。

4、将需要取模的运算用 & 操作代替（ a % size = (a & (size − 1)) ), 这需要size保证为2的次幂。

5、使用内存屏障(Memory Barrier)技术，实现单消费者和单生产者对kfifo的无锁并发访问（包括多CPU的情况），多个消费者、生产者的并发访问还是需要加锁的。

关于kfifo中内存屏障的使用，请参考https://www.linuxidc.com/Linux/2016-12/137936.htm。

三、kfifo功能函数之创建队列

kfifo提供两种创建队列的方法，动态创建和静态创建。

1、动态创建

(1)、kfifo_alloc

1
2
3

struct kfifo g_fifoqueue;

int kfifo_alloc(struct kfifo *fifo, unsigned int size, gfp_t gfp_mask);

该函数创建并初始化一个size大小的kfifo。内核使用gfp_mask标识符分配队列的缓冲区内存。如果成功，函数返回0，错误则返回负数的错误码。注意kfifo_alloc申请的内存是在物理地址上是连续的

(2)、kfifo_init

如果要自己分配缓冲区，可以调用函数：

1

void kfifo_init(struct kfifo *fifo, void *buffer, unsigned int size);

2、静态创建

DECLARE_KFIFO(name, size) ;

INIT_KFIFO(name);

四、入队操作

对于推入队列数据，kfifo提供三大类函数：常规函数， 将用户空间数据推入队列的函数，带记录域功能的函数。

1）常规函数

unsigned int kfifo_in(struct kfifo *fifo, const void *from, unsigned int len);

unsigned int kfifo_in_locked(struct kfifo *fifo, const void *from, unsigned int n, spinlock_t *lock);

2）将用户空间数据推入队列的函数

int kfifo_from_user(struct kfifo *fifo, const void __user *from, unsigned int n, unsigned *lenout);

unsigned int kfifo_from_user_rec(struct kfifo *fifo, const void __user *from, unsigned int n, unsigned int recsize);

3）带记录域功能的函数

unsigned int kfifo_in_rec(struct kfifo *fifo, void *from, unsigned int n, unsigned int recsize)；

五、出队

对于摘取队列数据，kfifo提供三大类函数：常规函数， 摘取队列数据至用户空间的函数，带记录域功能的函数。

(1)、常规函数

1
2
3
4
5

unsigned int kfifo_out(struct kfifo *fifo, void *to, unsigned int len);

unsigned int kfifo_out_locked(struct kfifo *fifo, void *to, unsigned int n, spinlock_t *lock);

unsigned int kfifo_out_peek(struct kfifo *fifo, void *to, unsigned int len, unsigned offset);

(2)、摘取队列数据至用户空间的函数

1
2
3

unsigned  int kfifo_to_user(struct kfifo *fifo, void __user *to, unsigned int n, unsigned *lenout);

unsigned int kfifo_to_user_rec(struct kfifo *fifo, void __user *to, unsigned int n, unsigned int recsize, unsigned int *total);

(3)、带记录域功能的函数

1

unsigned int kfifo_out_rec(struct kfifo *fifo, void *to, unsigned int n, unsigned int recsize, unsigned int *total);

六、获取队列长度、判空等操作

(1)、获取队列缓冲区大小

1

unsigned int kfifo_size(struct kfifo *fifo);

(2)、获取队列已推入的数据大小

1

unsigned int kfifo_len(struct kfifo *fifo);

(3)、获取队列可用空间大小

1

unsigned int kfifo_avail(struct kfifo *fifo);

(4)、判断队列是否空

1

int kfifo_is_empty(struct kfifo *fifo);

(5)、判断队列是否满

1

int kfifo_is_full(struct kfifo *fifo);

七、重置和撤销队列

(1)、重置队列

1
2
3

void kfifo_reset(struct kfifo *fifo);

void kfifo_skip(struct kfifo *fifo, unsigned int len);

(2)、撤销队列

如果队列是由函数kfifo_alloc创建，则撤销队列使用：

1
2

void kfifo_free(struct kfifo *fifo);

如果队列是由函数kfifo_init创建，则你需要负责释放相关缓冲。