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");

測試結果：?