内核数据结构-----队列kfifo.h （4.0.8）较新的内核版本

冷不防 2022-08-08 16:00 175阅读 0赞

现在市面上能买到的书大多都是2.6.X内核的，可是现在内核都出到4.2了其中也是发生了翻天覆地的变化，我学习开始内核就想从内核数据结构看起，看以前旧代码真心没什么意思，不如开拓下荒地。

队列这个东西其实以前也接触过，也写过一版通用的代码，其实一般的代码都是OK 的，但是最近开始我的内核之旅了，我还是想看看内核是如何实现队列的，从上次分析list.h 看来，内核的数据结构还是非常复杂的，复杂的看不懂，看懂了不会用，。。。。

任何操作系统都是离不开编程模型的，其中，生产者与消费者模型是很常见的，也和我们今天分析的队列结构很有关系。其实使用队列来实现这个编程模型时最简单的一种实现方式了，所以我们就来分析分析它。

为了提高英语水平以及为后续参加开源活动我都会翻译源码注释

我用的是4.0.8 的内核，它与之前2.6.\* 版本的内核已经有了很大的区别。

/*
     * How to porting drivers to the new generic FIFO API:
     *
     * - Modify the declaration of the "struct kfifo *" object into a
     *   in-place "struct kfifo" object
     * - Init the in-place object with kfifo_alloc() or kfifo_init()
     *   Note: The address of the in-place "struct kfifo" object must be
     *   passed as the first argument to this functions
     * - Replace the use of __kfifo_put into kfifo_in and __kfifo_get
     *   into kfifo_out
     * - Replace the use of kfifo_put into kfifo_in_spinlocked and kfifo_get
     *   into kfifo_out_spinlocked
     *   Note: the spinlock pointer formerly passed to kfifo_init/kfifo_alloc
     *   must be passed now to the kfifo_in_spinlocked and kfifo_out_spinlocked
     *   as the last parameter
     * - The formerly __kfifo_* functions are renamed into kfifo_*
     */

如何将队列移植到一个新的驱动中：

修改结构体的定义，改成需要的结构体。

使用kfifo\_alloc( ) 或者 kfifo\_init( ) 函数初始化已经定义的对象，注意：结构体的私之必须经过函数的确定.

修改kfifo\_put 为kfifo\_in\_spinlocked    kfifo\_get为 kfifo\_out\_spinlocked    (spinlocked : 自旋锁）

\_\_kfifo\_ \* 被修改为  kfifo\_ \*

/*
     * Note about locking : There is no locking required until only * one reader
     * and one writer is using the fifo and no kfifo_reset() will be * called
     *  kfifo_reset_out() can be safely used, until it will be only called
     * in the reader thread.
     *  For multiple writer and one reader there is only a need to lock the writer.
     * And vice versa for only one writer and multiple reader there is only a need
     * to lock the reader.
     */

关于锁的注意：这里没有锁的要求，除非有一个读取的动作的同时还有一个写的动作在使用队列，并且没有调用kfifo\_reset( ) 函数，这时候使用kfifo\_reset\_out ( )函数就是安全的，这个函数一般在读动作的线程中调用。

对于多个写动作和一个读动作，只需要锁住写动作，反过来，只有一个写动作且有多个读动作，只需要锁住读动作。（真体现了内核数据结构链表的设计精巧）

内核的队列结构和我们平时用的队列不是很相同，首先看下结构体：

struct __kfifo {
    	unsigned int	in;
    	unsigned int	out;
    	unsigned int	mask;
    	unsigned int	esize;
    	void		*data;
    };

这就是队列的部分结构体，它的入队出队是根据偏移量来决定的。

@in：入队偏移量

@out :出队偏移量

@mask: 表示队列的总大小（静态分配时，队列的固定总长度）

@eszie: 数据域大小

@data:数据域指针

下面的是以前的结构体不得不说内核的改变还是很大的

struct kfifo {
    	unsigned char *buffer;	/* the buffer holding the data */
    	unsigned int size;	/* the size of the allocated buffer */
    	unsigned int in;	/* data is added at offset (in % size) */
    	unsigned int out;	/* data is extracted from off. (out % size) */
    	spinlock_t *lock;	/* protects concurrent modifications */
    };

真是区别很大。

上边基本上是关于新旧内核的区别，现在开始正式分析代码：

首先看kfifo 结构体。

这里有两个结构体声明，一个是动态分配结构体，一个是静态分配结构体。但是这两个结构体的定义都是用宏实现的也算是殊途同归吧。

先看动态的：

/*
     * define compatibility "struct kfifo" for dynamic allocated fifos
     */
    struct kfifo __STRUCT_KFIFO_PTR(unsigned char, 0, void);

这是动态分配结构体

#define __STRUCT_KFIFO_PTR(type, recsize, ptrtype) \
    { \
    	__STRUCT_KFIFO_COMMON(type, recsize, ptrtype); \
    	type		buf[0]; \
    }

@type : 元素类型；

@recsize: 队列长度

@ptrtype: 结构体指针类型

@buf\[0\] 中存储的就是一个队列的元素

下面分析其中的宏

#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; \
    	}

这是一个联合结构体

@datatype  :数据元素类型

@recsize:  队列长度

@ptrtypr :  指针类型

这个联合结构体包含了这个队列元素的一切信息，它的类型，偏移量，指针类型等信息；

现在在来看看静态分配的队列：

/**
     * DECLARE_KFIFO - macro to declare a fifo object
     * @fifo: name of the declared fifo
     * @type: type of the fifo elements
     * @size: the number of elements in the fifo, this must be a power of 2
     */
    #define DECLARE_KFIFO(fifo, type, size)	STRUCT_KFIFO(type, size) fifo

静态分配也是有宏来实现的。

@fifo : 声明队列的对象；

@type：队列元素类型；

@size：队列的元素个数，其中个数必须是2的幂；

/**
     * DECLARE_KFIFO_PTR - macro to declare a fifo pointer object
     * @fifo: name of the declared fifo
     * @type: type of the fifo elements
     */
    #define DECLARE_KFIFO_PTR(fifo, type)	STRUCT_KFIFO_PTR(type) fifo

同上，也是静态的但是只是定义一个指针。

#define STRUCT_KFIFO(type, size) \
    	struct __STRUCT_KFIFO(type, size, 0, type)

#define __STRUCT_KFIFO(type, size, recsize, ptrtype) \
    { \
    	__STRUCT_KFIFO_COMMON(type, recsize, ptrtype); \
    	type		buf[((size < 2) || (size & (size - 1))) ? -1 : size]; \
    }

与是调用两个宏，同时定义了buf 队列的空间。并且调用了\_\_STRUCT\_KFIFO\_COMMON(type, recsize, ptrtype); 初始化了详细的队列信息；

下面来看看初始化：

首先看一下初始化的函数，这是一个宏定义函数：

/**
     * INIT_KFIFO - Initialize a fifo declared by DECLARE_KFIFO
     * @fifo: name of the declared fifo datatype
     */

#define INIT_KFIFO(fifo) \
    (void)({ \
    	typeof(&(fifo)) __tmp = &(fifo); \
    	struct __kfifo *__kfifo = &__tmp->kfifo; \
    	__kfifo->in = 0; \
    	__kfifo->out = 0; \
    	__kfifo->mask = __is_kfifo_ptr(__tmp) ? 0 : ARRAY_SIZE(__tmp->buf) - 1;\
    	__kfifo->esize = sizeof(*__tmp->buf); \
    	__kfifo->data = __is_kfifo_ptr(__tmp) ?  NULL : __tmp->buf; \
    })

这个宏将队列的信息初始化，这个初始化是针对静态定义的队列使用的；

/**
     * DEFINE_KFIFO - macro to define and initialize a fifo
     * @fifo: name of the declared fifo datatype
     * @type: type of the fifo elements
     * @size: the number of elements in the fifo, this must be a power of 2
     *
     * Note: the macro can be used for global and local fifo data type variables.
     */
    #define DEFINE_KFIFO(fifo, type, size) \
    	DECLARE_KFIFO(fifo, type, size) = \
    	(typeof(fifo)) { \
    		{ \
    			{ \
    			.in	= 0, \
    			.out	= 0, \
    			.mask	= __is_kfifo_ptr(&(fifo)) ? \
    				  0 : \
    				  ARRAY_SIZE((fifo).buf) - 1, \
    			.esize	= sizeof(*(fifo).buf), \
    			.data	= __is_kfifo_ptr(&(fifo)) ? \
    				NULL : \
    				(fifo).buf, \
    			} \
    		} \
    	}

这个定义是比较通用的一种定义和初始化方式。参数：

@fifo:已经定义的队列结构名称；

@type:元素类型名称；

@size:队列中元素个数，必须是2 的幂；

Note:这个宏可以适用与全局的以及本地的队列数据类型；

/**
     * kfifo_initialized - Check if the fifo is initialized
     * @fifo: address of the fifo to check
     *
     * Return %true if fifo is initialized, otherwise %false.
     * Assumes the fifo was 0 before.
     */
    #define kfifo_initialized(fifo) ((fifo)->kfifo.mask)

检查队列是否被初始化过，假设0是未被初始化；

/**
     * kfifo_esize - returns the size of the element managed by the fifo
     * @fifo: address of the fifo to be used
     */
    #define kfifo_esize(fifo)	((fifo)->kfifo.esize)

返回队列可以管理的队列的长度；

/**
     * kfifo_recsize - returns the size of the record length field
     * @fifo: address of the fifo to be used
     */
    #define kfifo_recsize(fifo)	(sizeof(*(fifo)->rectype))

返回记录长度字段大小；

/*
     * helper macro to distinguish between real in place fifo where the fifo
     * array is a part of the structure and the fifo type where the array is
     * outside of the fifo structure.
     */
    #define	__is_kfifo_ptr(fifo)	(sizeof(*fifo) == sizeof(struct __kfifo))

这个宏用来确定\_kfifo 是这个结构体的一部分并且确定传进来的类型是外部的宿主类型。

/**
     * kfifo_size - returns the size of the fifo in elements
     * @fifo: address of the fifo to be used
     */
    #define kfifo_size(fifo)	((fifo)->kfifo.mask + 1)

返回队列中可以存放元素的长度；

/**
     * kfifo_reset - removes the entire fifo content
     * @fifo: address of the fifo to be used
     *
     * Note: usage of kfifo_reset() is dangerous. It should be only called when the
     * fifo is exclusived locked or when it is secured that no other thread is
     * accessing the fifo.
     */
    #define kfifo_reset(fifo) \
    (void)({ \
    	typeof((fifo) + 1) __tmp = (fifo); \
    	__tmp->kfifo.in = __tmp->kfifo.out = 0; \
    })

/**
     * kfifo_reset_out - skip fifo content
     * @fifo: address of the fifo to be used
     *
     * Note: The usage of kfifo_reset_out() is safe until it will be only called
     * from the reader thread and there is only one concurrent reader. Otherwise
     * it is dangerous and must be handled in the same way as kfifo_reset().
     */
    #define kfifo_reset_out(fifo)	\
    (void)({ \
    	typeof((fifo) + 1) __tmp = (fifo); \
    	__tmp->kfifo.out = __tmp->kfifo.in; \
    })

/**
     * kfifo_len - returns the number of used elements in the fifo
     * @fifo: address of the fifo to be used
     */
    #define kfifo_len(fifo) \
    ({ \
    	typeof((fifo) + 1) __tmpl = (fifo); \
    	__tmpl->kfifo.in - __tmpl->kfifo.out; \
    })

返回队列中已经存在的（已经在队列中的元素）个数；

/**
     * kfifo_is_empty - returns true if the fifo is empty
     * @fifo: address of the fifo to be used
     */
    #define	kfifo_is_empty(fifo) \
    ({ \
    	typeof((fifo) + 1) __tmpq = (fifo); \
    	__tmpq->kfifo.in == __tmpq->kfifo.out; \
    })
    
    /**

队列是否为空；

/**
     * kfifo_is_full - returns true if the fifo is full
     * @fifo: address of the fifo to be used
     */
    #define	kfifo_is_full(fifo) \
    ({ \
    	typeof((fifo) + 1) __tmpq = (fifo); \
    	kfifo_len(__tmpq) > __tmpq->kfifo.mask; \
    })

队列是否已经满了；

/**
     * kfifo_avail - returns the number of unused elements in the fifo
     * @fifo: address of the fifo to be used
     */
    #define	kfifo_avail(fifo) \
    __kfifo_uint_must_check_helper( \
    ({ \
    	typeof((fifo) + 1) __tmpq = (fifo); \
    	const size_t __recsize = sizeof(*__tmpq->rectype); \
    	unsigned int __avail = kfifo_size(__tmpq) - kfifo_len(__tmpq); \
    	(__recsize) ? ((__avail <= __recsize) ? 0 : \
    	__kfifo_max_r(__avail - __recsize, __recsize)) : \
    	__avail; \
    }) \
    )

返回队列中没有被使用的元素个数。

/**
     * kfifo_alloc - dynamically allocates a new fifo buffer
     * @fifo: pointer to the fifo
     * @size: the number of elements in the fifo, this must be a power of 2
     * @gfp_mask: get_free_pages mask, passed to kmalloc()
     *
     * This macro dynamically allocates a new fifo buffer.
     *
     * The numer of elements will be rounded-up to a power of 2.
     * The fifo will be release with kfifo_free().
     * Return 0 if no error, otherwise an error code.
     */
    #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; \
    }) \
    )

队列动态分配一片新的空间，旧的空间会被释放。

@fifo:指向队列的指针

@size:队列中元素的个数

@标记，使用系统调用动态分配空间；

/**
     * kfifo_free - frees the fifo
     * @fifo: the fifo to be freed
     */
    #define kfifo_free(fifo) \
    ({ \
    	typeof((fifo) + 1) __tmp = (fifo); \
    	struct __kfifo *__kfifo = &__tmp->kfifo; \
    	if (__is_kfifo_ptr(__tmp)) \
    		__kfifo_free(__kfifo); \
    })

释放这个队列；

/**
     * kfifo_init - initialize a fifo using a preallocated buffer
     * @fifo: the fifo to assign the buffer
     * @buffer: the preallocated buffer to be used
     * @size: the size of the internal buffer, this have to be a power of 2
     *
     * This macro initialize a fifo using a preallocated buffer.
     *
     * The numer of elements will be rounded-up to a power of 2.
     * Return 0 if no error, otherwise an error code.
     */
    #define kfifo_init(fifo, buffer, size) \
    ({ \
    	typeof((fifo) + 1) __tmp = (fifo); \
    	struct __kfifo *__kfifo = &__tmp->kfifo; \
    	__is_kfifo_ptr(__tmp) ? \
    	__kfifo_init(__kfifo, buffer, size, sizeof(*__tmp->type)) : \
    	-EINVAL; \
    })

初始化一个队列，使用预先分配的一片空间；

/**
     * kfifo_put - put data into the fifo
     * @fifo: address of the fifo to be used
     * @val: the data to be added
     *
     * This macro copies the given value into the fifo.
     * It returns 0 if the fifo was full. Otherwise it returns the number
     * processed elements.
     *
     * Note that with only one concurrent reader and one concurrent
     * writer, you don't need extra locking to use these macro.
     */
    #define	kfifo_put(fifo, val) \
    ({ \
    	typeof((fifo) + 1) __tmp = (fifo); \
    	typeof(*__tmp->const_type) __val = (val); \
    	unsigned int __ret; \
    	size_t __recsize = sizeof(*__tmp->rectype); \
    	struct __kfifo *__kfifo = &__tmp->kfifo; \
    	if (__recsize) \
    		__ret = __kfifo_in_r(__kfifo, &__val, sizeof(__val), \
    			__recsize); \
    	else { \
    		__ret = !kfifo_is_full(__tmp); \
    		if (__ret) { \
    			(__is_kfifo_ptr(__tmp) ? \
    			((typeof(__tmp->type))__kfifo->data) : \
    			(__tmp->buf) \
    			)[__kfifo->in & __tmp->kfifo.mask] = \     此处的这个与操作可以确定入队的位置。
    				(typeof(*__tmp->type))__val; \
    			smp_wmb(); \
    			__kfifo->in++; \
    		} \
    	} \
    	__ret; \
    })

将一个数据入队列；

@fifo:将要被使用的队列的地址

@val：需要被加入的数据

这个宏将这个数据的一份拷贝加入队列，如果返回0，那么这个队列已经满了，否则它返回处理的元素所在位置；

注意：如果只有一个并行的读者（进程）和一个并行的（写者）进程，你不需要确定这个队列已经被锁，直接可以使用。

这一有一个smp\_wmb ( ) 者是CPU的写内存屏障。这里写应当，必须是一个原子操作；

/**
     * kfifo_get - get data from the fifo
     * @fifo: address of the fifo to be used
     * @val: address where to store the data
     *
     * This macro reads the data from the fifo.
     * It returns 0 if the fifo was empty. Otherwise it returns the number
     * processed elements.
     *
     * Note that with only one concurrent reader and one concurrent
     * writer, you don't need extra locking to use these macro.
     */
    #define	kfifo_get(fifo, val) \
    __kfifo_uint_must_check_helper( \
    ({ \
    	typeof((fifo) + 1) __tmp = (fifo); \
    	typeof(__tmp->ptr) __val = (val); \
    	unsigned int __ret; \
    	const size_t __recsize = sizeof(*__tmp->rectype); \
    	struct __kfifo *__kfifo = &__tmp->kfifo; \
    	if (__recsize) \
    		__ret = __kfifo_out_r(__kfifo, __val, sizeof(*__val), \
    			__recsize); \
    	else { \
    		__ret = !kfifo_is_empty(__tmp); \
    		if (__ret) { \
    			*(typeof(__tmp->type))__val = \
    				(__is_kfifo_ptr(__tmp) ? \
    				((typeof(__tmp->type))__kfifo->data) : \
    				(__tmp->buf) \
    				)[__kfifo->out & __tmp->kfifo.mask]; \
    			smp_wmb(); \
    			__kfifo->out++; \
    		} \
    	} \
    	__ret; \
    }) \
    )

从队列中获取一个元素；

/**
     * kfifo_in - put data into the fifo
     * @fifo: address of the fifo to be used
     * @buf: the data to be added
     * @n: number of elements to be added
     *
     * This macro copies the given buffer into the fifo and returns the
     * number of copied elements.
     *
     * Note that with only one concurrent reader and one concurrent
     * writer, you don't need extra locking to use these macro.
     */
    #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); \
    })

入队操作；

/**
     * kfifo_out - get data from the fifo
     * @fifo: address of the fifo to be used
     * @buf: pointer to the storage buffer
     * @n: max. number of elements to get
     *
     * This macro get some data from the fifo and return the numbers of elements
     * copied.
     *
     * Note that with only one concurrent reader and one concurrent
     * writer, you don't need extra locking to use these macro.
     */
    #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); \
    }) \
    )

出队操作；

/**
     * kfifo_in_spinlocked - put data into the fifo using a spinlock for locking
     * @fifo: address of the fifo to be used
     * @buf: the data to be added
     * @n: number of elements to be added
     * @lock: pointer to the spinlock to use for locking
     *
     * This macro copies the given values buffer into the fifo and returns the
     * number of copied elements.
     */
    #define	kfifo_in_spinlocked(fifo, buf, n, lock) \
    ({ \
    	unsigned long __flags; \
    	unsigned int __ret; \
    	spin_lock_irqsave(lock, __flags); \
    	__ret = kfifo_in(fifo, buf, n); \
    	spin_unlock_irqrestore(lock, __flags); \
    	__ret; \
    })

入队一个操作，使用自旋锁上锁，加入队列后解开自旋锁；