前面两节较为详细的讨论了 linux 内核中链表的设计，以及相关的C语言代码实现。本节再来看看 linux 内核中另外一种常用的数据类型：队列。

“队列”数据结构适合处理“生产者”和“消费者”编程模型

事实上，不仅仅是 linux 内核，基本上稍微有些规模的编程项目都会用到“队列”的概念。队列这种数据结构特别适合处理“生产者”和“消费者”编程模型。

生产者产生数据。比如麦克风设备产生的音频数据，从网络传来的tcp数据等。这些数据大都不能在产生的时候“瞬间”被处理完成，一般都会被暂时放在内存里。消费者则负责处理这些数据，比如从麦克风设备读取音频数据保存到磁盘，从网络读取 tcp 数据分析等。

实现“生产者”和“消费者”编程模型的最佳数据结构无疑是“队列”。所谓队列，其实就是“拍好队的数据”而已。生产者将数据推入队列，消费者则从队列头挨个摘取数据处理，如此一来，第一个进入队列的数据肯定会被消费者第一个处理。

C语言中的“队列”和现实世界中人类排队是相似的，都是谁先在队伍里排队，谁的事就最先被处理，所以“队列”也被称为 FIFO(first in first out, 先进先出)。linux 内核中“队列”数据结构的设计，以及相关C语言代码实现

linux 内核使用的“队列”设计相当简洁，实际上，内核中关于队列（kfifo）的代码量只有数百行。下面介绍一下 linux 内核中的队列，请看下面的 C语言代码：

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 结构体了，buffer 用于存储数据，in 和 out 则是入队和出队时的偏移。 因为 buffer 只是一个指针，若想使用需要调用 kfifo_alloc() 函数为其分配内存，它的C语言代码如下：

struct kfifo *kfifo_alloc(unsigned int size, gfp_t gfp_mask, spinlock_t *lock) { unsigned char *buffer; struct kfifo *ret; /* * round up to the next power of 2, since our 'let the indices * wrap' tachnique works only in this case. */ if (size & (size - 1)) { BUG_ON(size > 0x80000000); size = roundup_pow_of_two(size); } buffer = kmalloc(size, gfp_mask); if (!buffer) return ERR_PTR(-ENOMEM); ret = kfifo_init(buffer, size, gfp_mask, lock); if (IS_ERR(ret)) kfree(buffer); return ret; }

可以看出，kfifo_alloc() 函数要求 size 是 2 的幂，原因接下来会说。接着 kfifo_alloc() 函数调用了 kfifo_init() 函数初始化一个 kfifo 结构体对象， kfifo_init() 函数的C语言代码如下，请看：

struct kfifo *kfifo_init(unsigned char *buffer, unsigned int size, gfp_t gfp_mask, spinlock_t *lock) {  struct kfifo *fifo; /* size must be a power of 2 */ BUG_ON(!is_power_of_2(size)); fifo = kmalloc(sizeof(struct kfifo), gfp_mask); if (!fifo) return ERR_PTR(-ENOMEM); fifo->buffer = buffer;  fifo->size = size; fifo->in = fifo->out = 0; fifo->lock = lock; return fifo; }

linux 内核维护队列，其实就是维护 buffer、以及 in 和 out 偏移。在调用 kfifo_init() 函数后，队列的形状如下图：

in 表示入口偏移，下一次有数据需要排入队列时就从此处进入。out 表示出口偏移，是指下一次从队列摘取数据的位置。

不难看出，out 总是小于或者等于 in。推入队列数据

linux 内核往队列推入数据的动作由 kfifo_put() 函数完成，它的C语言代码如下，请看：

 79 static inline unsigned int kfifo_put(struct kfifo *fifo, 80 unsigned char *buffer, unsigned int len)- 81 {| 82 unsigned long flags;| 83 unsigned int ret;| 84 | 85 spin_lock_irqsave(fifo->lock, flags);| 86 | 87 ret = __kfifo_put(fifo, buffer, len);| 88 | 89 spin_unlock_irqrestore(fifo->lock, flags);| 90 | 91 return ret;| 92 }

核心代码是 __kfifo_put() 函数，如下图，容易看出，内核维护队列，主要工作其实就是维护 in 和 out 偏移。

从__kfifo_put() 函数的 len 变量计算方法可以看出，如果要推入的数据长度超出了队列的可用长度，则数据会被截短。

有了上面这张图，就不难看出已推入队列的数据长度等于 finfo->in – finfo->out，因此 fifo->size – fifo->in + fifo->out 就表示队列中的可用长度。事实上，linux 内核计算队列数据长度的 kinfo_len() 函数就是这么实现的：

继续分析 kfifo_put() 函数，发现要推入的数据可能会被截成两段放入队列 buffer。那什么时候数据会被截成两段呢？请看下图：

当要被推入的数据长度超过 finfo->size – finfo->in 时，数据就要被截成两段，并且一段要放在队列头了。变量 l 的计算解释了为什么分配 buffer 内存时，要求 size 必须是 2 的幂。

摘取队列数据

往队列推入数据可以调用 kfifo_put() 函数，那么从队列摘取数据则可以用 kfifo_get() 函数，它的C语言代码如下：

 103 static inline unsigned int kfifo_get(struct kfifo *fifo, 104 unsigned char *buffer, unsigned int len)- 105 {| 106 unsigned long flags;| 107 unsigned int ret;| 108 | 109 spin_lock_irqsave(fifo->lock, flags);| 110 | 111 ret = __kfifo_get(fifo, buffer, len);| 112 | 113 /*| 114 * optimization: if the FIFO is empty, set the indices to 0| 115 * so we don't wrap the next time| 116 */| 117 if (fifo->in == fifo->out)| 118 fifo->in = fifo->out = 0;| 119 | 120 spin_unlock_irqrestore(fifo->lock, flags);| 121 | 122 return ret;| 123 }

同样的，核心代码是__kfifo_get() 函数，它的C语言代码如下：

可以看出，它的逻辑与 kfifo_put() 函数是类似的，这里就不再赘述了。

重置队列

如果不再需要队列中的数据，并且希望重复使用队列，则简单重置 fifo->in 与 fifo->out 即可：

static inline void __kfifo_reset(struct kfifo *fifo){fifo->in = fifo->out = 0;}

可以看出，这种设计相当简洁。

欢迎在评论区一起讨论，质疑。文章都是手打原创（本文部分参考linux内核原理和设计），每天最浅显的介绍C语言、linux等嵌入式开发，喜欢我的文章就关注一波吧，可以看到最新更新和之前的文章哦。