kfifo是一个环形缓存，是一个队列，实现FIFO功能。kfifo头文件linux/kfifo.h，实现代码：lib/kfifo.c

1 结构体

kfifo有一个结构体，定义在linux/kfifo.h中：

struct __kfifo {

unsigned int in;

unsigned int out;

unsigned int mask;

unsigned int esize;

void *data;

};

esize：块（element）大小，FIFO按整块入队列和出队列，esize可以为1。

data：数据指针，可动态分配，或用户传递数据地址。

mask：FIFO块个数减1，FIFO块个数需要为2的整数次方。

in：下一个入块的offset。

out：下一个出块的offset。

in和out的范围并没有限制在[0, mask]，而是不断累加，因此通过(in-out)可以得出队列的块个数。这里并没有回绕的问题：

$ cat test.c

#include <stdio.h>

#include <limits.h>

void main()

{

unsigned int out = UINT_MAX - 10 ;

unsigned int in = UINT_MAX + 2;

printf("%u\n", in - out);

}

$ cc test.c

$ ./a.out

12

2 关于锁

对于是单生产者和单消费者的情形，不需要锁。底层通过memory barrier实现为一个lock-free ring buffer。

多生产者单消费者，入队要加锁。单生产者多消费者，出队要加锁。

3 底层接口

这些接口实现在lib/kfifo.c中，操作struct __kfifo对象，并且使用EXPORT_SYMBOL导出符号。

int __kfifo_alloc(struct __kfifo *fifo, unsigned int size,

size_t esize, gfp_t gfp_mask)

初始化fifo，并且调用kmalloc分配内存，size在内部会调用roundup_pow_of_two()向上调整为2的整数次方。

void __kfifo_free(struct __kfifo *fifo)

调用free释放内存，并且初始化其它fifo成员，和__kfifo_alloc成对使用。

int __kfifo_init(struct __kfifo *fifo, void *buffer,

unsigned int size, size_t esize)

通过传入data指针，初始化fifo。size在内部同样会向上调整为2的整数次方。

unsigned int __kfifo_in(struct __kfifo *fifo,

const void *buf, unsigned int len)

入队，注意len是按块算的，如果可用的块个数少于len，则只拷贝部分块到队列满。返回入队的块数。

unsigned int __kfifo_out_peek(struct __kfifo *fifo,

void *buf, unsigned int len)

从队列拷贝len个块，如果队列中的可用块少于len，则只拷贝哪些可用块。返回拷贝的块数。

此接口不改变out。

unsigned int __kfifo_out(struct __kfifo *fifo,

void *buf, unsigned int len)

出队len个块，如果队列中的可以用块少于len，则全部出队，返回出队的块数。

int __kfifo_from_user(struct __kfifo *fifo, const void __user *from,

unsigned long len, unsigned int *copied)

从用户空间最多拷贝len个bytes，copied是实际拷贝的字节数。

拷贝会按elements整块拷贝，如果可用空间不足或者len不是块大小的整数倍，则实际拷贝的字节数小于len。

返回0，如果copy_from_user没有错误的话。返回-EFAULT，如果copy_from_user返回非0值。

返回-EFAULT也可能拷贝了部分块，实际拷贝的块为copied/esize

int __kfifo_to_user(struct __kfifo *fifo, void __user *to,

unsigned long len, unsigned int *copied)

最多拷贝len个bytes到用户空间。和 __kfifo_from_user类似。

DMA接口

略

4 底层record FIFO接口

这些接口实现在lib/kfifo.c中。record FIFO每块数据前面带一个长度域，表示该块数据的长度。所有的接口函数都带一个recsize参数，指定长度域的长度。支持1个字节或者2个字节的record。record形式的FIFO，其esize为1。

unsigned int __kfifo_max_r(unsigned int len, size_t recsize)

recsize是record域的长度，如果为1，则最大长度为255。如果len大于recsize所能表示的长度，则返回最大长度，否则返回len。

unsigned int __kfifo_len_r(struct __kfifo *fifo, size_t recsize)

返回下一个块的长度

unsigned int __kfifo_in_r(struct __kfifo *fifo, const void *buf,

unsigned int len, size_t recsize)

入队列，如果剩余空间不能容纳len+recsize，直接返回0，否则返回len。

unsigned int __kfifo_out_peek_r(struct __kfifo *fifo, void *buf,

unsigned int len, size_t recsize)

从队列中提取一个record，长度域不被提取，如果len小于record的长度，则只返回len长度的数据。

如果队列为空，直接返回0。否则返回拷贝的长度。

unsigned int __kfifo_out_r(struct __kfifo *fifo, void *buf,

unsigned int len, size_t recsize)

如果队列为空，则直接返回0。

否则返回一个record的数据，如果len小于record的长度，只拷贝len长度的数据。

out指向下一个record，未拷贝的数据将丢失，返回len。

void __kfifo_skip_r(struct __kfifo *fifo, size_t recsize)

跳过一个record

int __kfifo_from_user_r(struct __kfifo *fifo, const void __user *from,

unsigned long len, unsigned int *copied, size_t recsize)

如果len大于recsize能容纳的大小，len在内部将等于最大值。

如果len+recsize大于能容纳的大小，直接返回0。

如果拷贝失败，则返回-EFAULT，copied被置为0，也不会移动in，这点和__kfifo_from_user不同，后者可能拷贝部分数据。

而这个接口要么拷贝全部，要么完全不拷贝。

否则返回0。

int __kfifo_to_user_r(struct __kfifo *fifo, void __user *to,

unsigned long len, unsigned int *copied, size_t recsize)

类似__kfifo_out_r，当用户IO出错时，返回-EFAULT。

DMA接口

略

5 上层接口

实现在linux/kfifo.h

5.1 结构定义

封装了一个新的结构体：

#define __STRUCT_KFIFO_COMMON(datatype, recsize, ptrtype) \

union { \

struct __kfifo kfifo; \

datatype *type; \

const datatype *const_type; \

char (*rectype)[recsize]; \

ptrtype *ptr; \

ptrtype const *ptr_const; \

}

#define __STRUCT_KFIFO(type, size, recsize, ptrtype) \

{ \

__STRUCT_KFIFO_COMMON(type, recsize, ptrtype); \

type buf[((size < 2) || (size & (size - 1))) ? -1 : size]; \

}

#define STRUCT_KFIFO(type, size) \

struct __STRUCT_KFIFO(type, size, 0, type)

#define __STRUCT_KFIFO_PTR(type, recsize, ptrtype) \

{ \

__STRUCT_KFIFO_COMMON(type, recsize, ptrtype); \

type buf[0]; \

}

#define STRUCT_KFIFO_PTR(type) \

struct __STRUCT_KFIFO_PTR(type, 0, type)

/*

* define compatibility "struct kfifo" for dynamic allocated fifos

*/

struct kfifo __STRUCT_KFIFO_PTR(unsigned char, 0, void);

#define STRUCT_KFIFO_REC_1(size) \

struct __STRUCT_KFIFO(unsigned char, size, 1, void)

#define STRUCT_KFIFO_REC_2(size) \

struct __STRUCT_KFIFO(unsigned char, size, 2, void)

/*

* define kfifo_rec types

*/

struct kfifo_rec_ptr_1 __STRUCT_KFIFO_PTR(unsigned char, 1, void);

struct kfifo_rec_ptr_2 __STRUCT_KFIFO_PTR(unsigned char, 2, void);

通用结构体：

struct

{

union

{

struct __kfifo kfifo;

datatype *type;

const datatype *const_type;

char (*rectype)[recsize];

ptrtype *ptr;

ptrtype const *ptr_const;

};

datatype buf[size];

}

这里一看可能很纳闷，kfifo怎么和其它字段是联合呢？其它字段读写岂不是会覆盖kfifo的内容。其实这又是内核的一个技巧，其它字段不会读写数据，只是编译器用来获取相关信息。比如获取recsize：

#define kfifo_recsize(fifo) (sizeof(*(fifo)->rectype))

这里使用指向数组的指针，而不是直接使用数组，是因为recsize为0，0大小的数组只能

非record类型的，分为静态和指针两种：

STRUCT_KFIFO(type, size)

STRUCT_KFIFO_PTR(type)

指针类型的buf为buf[0]，数据动态分配。静态类型的，buf大小是宏传递的size，size必须为常亮。recsize为0

record类型的，分为静态和指针，recsize有1和2两种，type固定为unsigned char。

STRUCT_KFIFO_REC_1(size)

STRUCT_KFIFO_REC_2(size)

由于recsize和type均固定，结构体不随这些类型变化，因此其结构体是预定义的，上述4种则是随变量匿名定义的。

struct kfifo_rec_ptr_1

struct kfifo_rec_ptr_2

5.2 接口

如下表

DECLARE_KFIFO_PTR(fifo, type)	定义一个非record FIFO，名字为fifo，element类型为type，其数据需要动态分配。
DECLARE_KFIFO(fifo, type, size)	定义一个非record FIFO，名字为fifo，element类型为type，element个数为size，其数据静态存储在结构体中，size需为常数且为2的整数次方
INIT_KFIFO(fifo)	初始化DECLARE_KFIFO接口定义的fifo
DEFINE_KFIFO(fifo, type, size)	定义并初始化fifo
kfifo_initialized(fifo)	fifo是否初始化
kfifo_esize(fifo)	返回fifo的esize
kfifo_recsize(fifo)	返回fifo的recsize
kfifo_size(fifo)	返回fifo的size
kfifo_reset(fifo)	将in和out置0，注意：需要上锁。
kfifo_reset_out(fifo)	将out设置为in，由于只修改out，因此在读者上下文，且只有一个读者时，是安全的。否则需要上锁。
kfifo_len(fifo)	返回fifo中element的个数
kfifo_is_empty(fifo)	fifo是否为空 (in == out)
kfifo_is_full(fifo)	fifo是否满
kfifo_avail(fifo)	非record FIFO，返回可容纳的element个数 record FIFO，返回除去record头能容纳的字节数，最多不超过record头能表示的字节数，如recsize为1，最多返回255。
kfifo_skip(fifo)	跳过一个element或record
kfifo_peek_len(fifo)	获取下一个element或者record的字节长度。
kfifo_alloc(fifo, size, gfp_mask)	为指针式FIFO分配空间并初始化，成功返回0，错误则返回负数错误码
kfifo_free(fifo)	释放kfifo_alloc分配的内存
kfifo_init(fifo, buffer, size)	使用预分配的缓存初始化fifo，成功返回0，错误则返回负数错误码
kfifo_put(fifo, val)	这是一个宏，将val赋值给一个FIFO type类型的临时变量，然后将临时变量入队。存放一个element，如果成功返回入队的elements个数。如果FIFO满，则返回0。
kfifo_get(fifo, val)	val是一个指针，内部将val赋值给一个ptr指针类型的临时变量，并拷贝sizeof(*ptr)长度到val的地址。对于record FIFO，其是void类型，sizeof(void)为1，所以拷贝1个字节。非record类型，拷贝一个element。如果FIFO为空，返回0，否则返回拷贝的element数。
kfifo_peek(fifo, val)	和kfifo_get相同，除了不更新out外。
kfifo_in(fifo, but, n)	入队n个elemnts。返回工程入队的elements数。
kfifo_in(fifo, buf, n, lock)	加锁入队。加锁方式为spin_lock_irqsave
kfifo_out(fifo, buf, n)	出队n个elements，返回成功拷贝的elements数
kfifo_out_spinlocked(fifo, buf, n, lock)	加锁出队。加锁方式位spin_lock_irqsave
kfifo_from_user(fifo, from, len, copied)	最多拷贝len个字节，参考record FIFO和非record FIFO的对应底层接口。
kfifo_to_user(fifo, to, len, copied)	最多拷贝len个字节到用户空间，参考record FIFO和非record FIFO的对应底层接口。
kfifo_dma_in_prepare kfifo_dma_in_finish kfifo_dma_out_prepare kfifo_dma_out_finish	DMA接口，略
kfifo_out_peek(fifo, buf, n)	peek n个elements的数据，但是内部out不动，返回拷贝的elements个数

参考：

linux-4.16.8 源码

https://www.kernel.org/doc/htmldocs/kernel-api/kfifo.html

ILD

1 结构体

2 关于锁

3 底层接口

4 底层record FIFO接口

5 上层接口

5.1 结构定义

5.2 接口