linux驱动编程 - kfifo先进先出队列

简介：

        kfifo是Linux Kernel里面的一个 FIFO（先进先出）数据结构，它采用环形循环队列的数据结构来实现，提供一个无边界的字节流服务，并且使用并行无锁编程技术，即当它用于只有一个入队线程和一个出队线程的场情时，两个线程可以并发操作，而不需要任何加锁行为，就可以保证kfifo的线程安全。
        FIFO主要用于缓冲速度不匹配的通信。

下面图解kfifo工作过程：

蓝色表示kfifo剩余空间，红色表示kfifo已占用空间

1）空的kfifo

2）put数据到buffer后

3）从buffer中get数据后

4）当此时put到buffer中的数据长度超出in到末尾长度时，则将剩下的移到头部去

注意，kfifo如果只有一个写入者，一个读取者，是不需要锁的。但是多对一的情况，多的那方需要上锁。如：多个写入者，一个读取者，需对写入者上锁。 反之，如果有多个读取者，一个写入者，需对读取者上锁。

一、kfifo常用函数介绍

Linux内核中的路径：lib/kfifo.c、include/linux/kfifo.h

头文件：#include <linux/kfifo.h>

常用函数 / 宏	功能
DECLARE_KFIFO_PTR(fifo, type)	定义一个名字为fifo，element类型为type，其数据需要kfifo_alloc动态分配
DECLARE_KFIFO(fifo, type, size)	定义一个名字为fifo，element类型为type，element个数为size，其数据静态存储在结构体中，size需为常数且为2的整数次方
INIT_KFIFO(fifo)	初始化DECLARE_KFIFO接口定义的fifo
DEFINE_KFIFO(fifo, type, size)	定义并初始化fifo
kfifo_initialized(fifo)	fifo是否初始化
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的总size
kfifo_is_empty(fifo)	fifo是否为空 (in == out)
kfifo_is_full(fifo)	fifo是否满
kfifo_avail(fifo)	获取队列的空闲空间长度
kfifo_skip(fifo)	跳过一个element
kfifo_peek_len(fifo)	获取下一个element的字节长度。
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的地址。拷贝一个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)	复制用户空间的数据到kfifo 最多拷贝len个字节，参考record FIFO和非record FIFO的对应底层接口。
kfifo_to_user(fifo, to, len, copied)	复制kfifo中的数据到用户空间 最多拷贝len个字节到用户空间，参考record FIFO和非record FIFO的对应底层接口。
kfifo_out_peek(fifo, buf, n)	peek n个elements的数据，但是内部out不动，返回拷贝的elements个数

1、结构体定义

1.1 struct __kfifo 结构体

struct __kfifo {unsigned int	in;           //入队指针，指向下一个元素可被插入的位置unsigned int	out;          //出队指针，指向即将出队的第一个元素unsigned int	mask;         //向上扩展成2的幂queue_size-1unsigned int	esize;        //每个元素的大小，单位为字节void		*data;            //存储数据的缓冲区
};

下图可以直观的表示各结构体成员之间的关系：

1.2 struct kfifo 结构体

#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_PTR(type, recsize, ptrtype) \
{ \__STRUCT_KFIFO_COMMON(type, recsize, ptrtype); \type		buf[0]; \
}struct kfifo __STRUCT_KFIFO_PTR(unsigned char, 0, void);

kfifo结构体展开后格式如下：

struct kfifo
{union{struct __kfifo    kfifo;            //__kfifo是kfifo的成员unsigned char        *type;const unsigned char  *const_type;char                 (*rectype)[0];void                 *ptr;void const           *ptr_const;  };unsigned char buf[0];
}

kfifo怎么和其它字段是联合的？其它字段读写岂不是会覆盖kfifo的内容。其实这又是内核的一个技巧，其它字段不会读写数据，只是编译器用来获取相关信息 。

比如：

获取recsize：

#define kfifo_recsize(fifo)     (sizeof(*(fifo)->rectype))
通过kfifo_alloc分配buf存储空间时，获取块的大小

__kfifo_alloc(__kfifo, size, sizeof(*__tmp->type), gfp_mask) : 

2、初始化kfifo

声明kfifo有2种方式：

• DECLARE_KFIFO_PTR 配合 kfifo_alloc 用于动态申请kfifo；
• DECLARE_KFIFO 用于静态定义kfifo；

宏	功能	相似方法
DECLARE_KFIFO_PTR(fifo, type) 参数： fifo：要定义的kfifo的名字 type：元素的类型	宏定义一个kfifo指针对象，会设置type buf[]数组的大小为0，因此需配合 kfifo_alloc  动态分配buf的存储空间	struct kfifo fifo;
DECLARE_KFIFO(fifo, type, size) 参数： fifo：要定义的kfifo的名字 type：元素的类型 size：kfifo可容纳的元素个数，必须是2的幂	静态声明一个kfifo对象，设置type buf[] 大小为size、类型为 type 的数组	DEFINE_KFIFO

笔者常用到动态申请方式，因此主要介绍动态申请方式。

动态申请除了用 DECLARE_KFIFO_PTR，还能用 struct kfifo 创建结构体，如：

struct kfifo fifo；        #可替代 DECLARE_KFIFO_PTR(fifo, unsigned char)

这种方式可替代 DECLARE_KFIFO_PTR(fifo, unsigned char)，它们都用到 __STRUCT_KFIFO_PTR，仅传入的第3个参数不同。

/* struct kfifo结构体定义 */
struct kfifo __STRUCT_KFIFO_PTR(unsigned char, 0, void);/* DECLARE_KFIFO_PTR宏定义 */
#define STRUCT_KFIFO_PTR(type) \struct __STRUCT_KFIFO_PTR(type, 0, type)#define DECLARE_KFIFO_PTR(fifo, type)   STRUCT_KFIFO_PTR(type) fifo

2.1 动态申请

方法一：

struct kfifo fifo = {0};                                //定义一个 struct kfifo 变量

kfifo_alloc(&fifo, 4096, GFP_KERNEL);  //使用 kfifo_alloc 动态申请内存空间，大小为4096

方法二：

DECLARE_KFIFO_PTR(fifo, unsigned char);        //申请

INIT_KFIFO(fifo);                                                    //初始化 

kfifo_alloc(&fifo, 4096, GFP_KERNEL);   //使用 kfifo_alloc 动态申请内存空间，大小为4096

注意：动态分配最后需要调用 kfifo_free 释放

2.2 静态定义

方法一：

DECLARE_KFIFO(fifo, char, 512);        //静态申明，type buf[] 大小为512，类型为char

INIT_KFIFO(fifo);                                   //初始化fifo结构

方法二：

DEFINE_KFIFO(fifo, char, 512)             //同上

3、入队、出队

3.1 kfifo_in

功能：buf中len长度数据写入到fifo中

返回值：实际写入长度

unsigned int __kfifo_in(struct __kfifo *fifo,const void *buf, unsigned int len)
{unsigned int l;l = kfifo_unused(fifo);        //判断kfifo还有多少剩余空间if (len > l)len = l;kfifo_copy_in(fifo, buf, len, fifo->in);    //将数据拷贝到kfifo中fifo->in += len;               //设置写入数量+lenreturn len;
}#define	kfifo_in(fifo, buf, n) \
({ \typeof((fifo) + 1) __tmp = (fifo); \typeof(__tmp->ptr_const) __buf = (buf); \unsigned long __n = (n); \const size_t __recsize = sizeof(*__tmp->rectype); \struct __kfifo *__kfifo = &__tmp->kfifo; \(__recsize) ?\__kfifo_in_r(__kfifo, __buf, __n, __recsize) : \__kfifo_in(__kfifo, __buf, __n); \
})

3.2 kfifo_out

功能：从fifo中获取len长度数据到buf中

unsigned int __kfifo_out(struct __kfifo *fifo,void *buf, unsigned int len)
{len = __kfifo_out_peek(fifo, buf, len);    //fifo输出数据到buffifo->out += len;                          //输出数量+lenreturn len;
}#define	kfifo_out(fifo, buf, n) \
__kfifo_uint_must_check_helper( \
({ \typeof((fifo) + 1) __tmp = (fifo); \typeof(__tmp->ptr) __buf = (buf); \unsigned long __n = (n); \const size_t __recsize = sizeof(*__tmp->rectype); \struct __kfifo *__kfifo = &__tmp->kfifo; \(__recsize) ?\__kfifo_out_r(__kfifo, __buf, __n, __recsize) : \__kfifo_out(__kfifo, __buf, __n); \
}) \
)

4、动态申请、释放内存

4.1 kfifo_alloc

功能：动态申请kfifo内存

返回值：0-成功，其他-失败

int __kfifo_alloc(struct __kfifo *fifo, unsigned int size,size_t esize, gfp_t gfp_mask)
{/** round up to the next power of 2, since our 'let the indices* wrap' technique works only in this case.*/size = roundup_pow_of_two(size);    //向上扩展为2的幂fifo->in = 0;fifo->out = 0;fifo->esize = esize;if (size < 2) {fifo->data = NULL;fifo->mask = 0;return -EINVAL;}fifo->data = kmalloc_array(esize, size, gfp_mask);    //动态申请内存if (!fifo->data) {fifo->mask = 0;return -ENOMEM;}fifo->mask = size - 1;return 0;
}#define kfifo_alloc(fifo, size, gfp_mask) \
__kfifo_int_must_check_helper( \
({ \typeof((fifo) + 1) __tmp = (fifo); \struct __kfifo *__kfifo = &__tmp->kfifo; \__is_kfifo_ptr(__tmp) ? \__kfifo_alloc(__kfifo, size, sizeof(*__tmp->type), gfp_mask) : \-EINVAL; \
}) \
)

注意：保证缓冲区大小为2的次幂，若不是，会向上取整为2的次幂（很重要）

4.2 kfifo_free

功能：释放kfifo动态申请的内存

void __kfifo_free(struct __kfifo *fifo)
{kfree(fifo->data);        //释放内存fifo->in = 0;fifo->out = 0;fifo->esize = 0;fifo->data = NULL;fifo->mask = 0;
}#define kfifo_free(fifo) \
({ \typeof((fifo) + 1) __tmp = (fifo); \struct __kfifo *__kfifo = &__tmp->kfifo; \if (__is_kfifo_ptr(__tmp)) \__kfifo_free(__kfifo); \
})

二、使用方法

使用kfifo的方式有两种，动态申请和静态定义。

3.1 动态申请

动态申请步骤如下：

① 包含头文件 #include <linux/kfifo.h>

② 定义一个 struct kfifo 变量；

③ 使用 kfifo_alloc 申请内存空间；

④ 分别使用 kfifo_in、kfifo_out 执行入队、出队的操作；

⑤ 不再使用kfifo时，使用 kfifo_free 释放申请的内存。

示例：

#include <linux/types.h>
#include <linux/kernel.h>
#include <linux/delay.h>
#include <linux/ide.h>
#include <linux/init.h>
#include <linux/module.h>
#include <linux/errno.h>
#include <linux/kfifo.h>//定义fifo存储结构体
struct member {char name[32];char val;
};//定义fifo最大保存的元素个数
#define FIFO_MEMBER_NUM     64//定义kfifo
static struct kfifo stFifo;static int __init kfifo_demo_init(void)
{int ret = 0;int i;/* 1.申请fifo内存空间，空间大小最好为2的幂 */ret = kfifo_alloc(&stFifo, sizeof(struct member) * FIFO_MEMBER_NUM, GFP_KERNEL);if (ret) {printk(KERN_ERR "kfifo_alloc fail ret = %d\n", ret);return;}/* 2.入队 */struct member stMember = {0}; for (i = 0; i < FIFO_MEMBER_NUM; i++) {snprintf(stMember.name, 32, "name%d", i);stMember.val = i;ret = kfifo_in(&stFifo, &stMember, sizeof(struct member));if (!ret) {printk(KERN_ERR "kfifo_in fail, fifo is full\n");}}/* 3.出队 */for  (i = 0; i < FIFO_MEMBER_NUM; i++) {ret = kfifo_out_peek(&stFifo, &stMember, sizeof(struct member));        //读，返回实际读到长度（不修改out）ret = kfifo_out(&stFifo, &stMember, sizeof(struct member));             //读，返回实际读到长度（修改out）if (ret) {printk(KERN_INFO "kfifo_out stMember: name = %s, val=%d\n", stMember.name, stMember.val);} else {printk(KERN_ERR "kfifo_out fail, fifo is empty\n");}if (kfifo_is_empty(&stFifo)) {        //判断fifo空printk(KERN_INFO "kfifo is empty!!!\n");break;}}/* 4.释放 */kfifo_free(&stFifo);
}static void __exit kfifo_demo_exit(void)
{kfifo_free(&stFifo);
}module_init(kfifo_demo_init);
module_exit(kfifo_demo_exit);
MODULE_LICENSE("GPL");
MODULE_AUTHOR("dong");

测试结果：

这种动态申请方式in、out都是以字节为单位。

3.2 静态定义

静态定义步骤如下：

① 包含头文件 #include <linux/kfifo.h>

② 使用宏 DECLARE_KFIFO 静态定义 fifo 变量；

③ 分别使用 kfifo_put、kfifo_get执行入队、出队的操作；

静态定义不需要申请和释放内存的步骤，出入队函数也更精简。

示例：

#include <linux/types.h>
#include <linux/kernel.h>
#include <linux/delay.h>
#include <linux/ide.h>
#include <linux/init.h>
#include <linux/module.h>
#include <linux/errno.h>
#include <linux/kfifo.h>//定义fifo存储结构体
struct member {char name[32];char val;
};//定义fifo最大保存的元素个数，最好为2的幂
#define FIFO_MEMBER_NUM     64//静态定义已经包含了缓存定义
DECLARE_KFIFO(stFifo, struct member, FIFO_MEMBER_NUM);static int __init kfifo_demo_init(void)
{int ret = 0;int i;/* 1.初始化  */INIT_KFIFO(stFifo);/* 2.入队 */struct member stMember = {0}; for (i = 0; i < FIFO_MEMBER_NUM; i++) {snprintf(stMember.name, 32, "name%d", i);stMember.val = i;ret = kfifo_put(&stFifo, stMember);  //注意这里的元素变量名而不是指针if (!ret) {printk(KERN_ERR "kfifo_put fail, fifo is full\n");}}/* 3.出队 */for  (i = 0; i < FIFO_MEMBER_NUM; i++) {ret = kfifo_get(&stFifo, &stMember); //注意这里传入地址if (ret) {printk(KERN_INFO "kfifo_get stMember: name = %s, val=%d\n", stMember.name, stMember.val);} else {printk(KERN_ERR "kfifo_get fail, fifo is empty\n");}printk(KERN_INFO "kfifo: in = %d, out = %d\n", stFifo.kfifo.in, stFifo.kfifo.out);if (kfifo_is_empty(&stFifo)) {printk(KERN_INFO "kfifo is empty!!!\n");break;}}
}static void __exit kfifo_demo_exit(void)
{return;
}module_init(kfifo_demo_init);
module_exit(kfifo_demo_exit);
MODULE_LICENSE("GPL");
MODULE_AUTHOR("dong");

测试结果： 

示例中静态定义的in、out是以结构体为单位，64次入队fifo中就会有64个结构体元素。