• 好好学习,天天向上~
  • 欢迎欢迎~

linux学习19,内核中的“队列”数据类型

linux笔记 lcc 234℃ 0评论

前面两节较为详细的讨论了 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学习19,内核中的“队列”数据类型 - 刘冲的博客(https://blog.popkx.com) 原创版权所有,转载请注明出处。
点赞 (0)分享 (0)
发表我的评论
取消评论
表情     2 + 2 = ? (必填)