时间戳

首页 > 解决方案 > 为什么在一些博客中kfifo是循环队列

c - 为什么在一些博客中kfifo是循环队列

问题描述

kfifo 是循环队列吗？

在循环队列 WIKI（https://en.wikipedia.org/wiki/Circular_buffer）中说“它是端到端连接的。 ”。但在 linux-4.16.12\lib\kfifo.c

int __kfifo_init(struct __kfifo *fifo, void *buffer,
        unsigned int size, size_t esize)
{
    size /= esize;

    size = roundup_pow_of_two(size);

    fifo->in = 0;
    fifo->out = 0;
    fifo->esize = esize;
    fifo->data = buffer;

    if (size < 2) {
        fifo->mask = 0;
        return -EINVAL;
    }
    fifo->mask = size - 1;

    return 0;
}

我没有找到指向结束指针的开始指针，所以：

1) kfifo 是循环队列吗？

2）如果是，如何证明？

标签： clinuxlinux-kernel

解决方案

您提到的维基百科页面指出，循环缓冲区的行为就像缓冲区是端到端连接的。在实践中，循环缓冲区只是一个固定长度的数组，有两个索引指针（通常称为headand tail，或inand out）表示写入数据的“边界”。为了避免写入缓冲区边界之外，对这些索引的所有算术运算都以缓冲区的长度为模完成。

通常，指针的含义是：

  • head或in索引，指示下一个可用于写入的插槽，以及
  • tail或out索引，表示最后读取（“删除”）插槽。

还有两种边界状态：

  • 如果tail等于head，则缓冲区为空。
  • 如果增加tail模缓冲区长度等于等于tail，head则缓冲区已满。

大多数实现将使用以下方法之一将索引保持在缓冲区范围内：

// check if index overflowed and reset
int fifo_increment_index(struct fifo *fifo, int index)
{
     index = index + 1; 
     if (index > fifo->capacity)
         index = 0;
     return index;
}

// use the modulo operator (slower due to division,
// although it avoids branching)
int fifo_increment_index(struct fifo *fifo, int index)
{
     index = (index + 1) % fifo->capacity; // modulo
     return index;
}

// use a bitwise mask (in most cases the fastest approach),
// but works ONLY if capacity is a power of 2
int fifo_increment_index(struct fifo *fifo, int index)
{
     // if capacity is 1024 (0x400), then
     // mask will be 1023 (0x3FF)

     index = (index + 1) & fifo->mask; // bitwise and
     return index;
}

Linux kfifo 使用最后一种方法（按位屏蔽），这就是为什么它始终确保容量是init 函数 ( size = roundup_pow_of_two(size)) 中的 2 的幂。

但是，它不会在索引更改后立即重置索引，而是在每次访问缓冲区时屏蔽它们：

#define __KFIFO_PEEK(data, out, mask) ( (data)[(out) & (mask)] )
#define __KFIFO_POKE(data, in, mask, val) ( (data)[(in) & (mask)] = (unsigned char)(val) )

对于uint8_t缓冲区，__KFIFO_PEEK宏基本上是：

static inline uint8_t kfifo_peek(struct __kfifo *fifo)
{
     int index = fifo->out & fifo->mask;
     return fifo->data[index];
}

推荐阅读