模仿Linux内核kfifo实现的循环缓存

想实现个循环缓冲区（Circular Buffer），搜了些资料多数是基于循环队列的实现方式。使用一个变量存放缓冲区中的数据长度或者空出来一个空间来判断缓冲区是否满了。偶然间看到分析Linux内核的循环缓冲队列kfifo的实现，确实极其巧妙。kfifo主要有以下特点：

保证缓冲空间的大小为2的次幂，不是的向上取整为2的次幂。

使用无符号整数保存输入(in)和输出(out)的位置，在输入输出时不对in和out的值进行模运算，而让其自然溢出，并能够保证in-out的结果为缓冲区中已存放的数据长度，这也是最能体现kfifo实现技巧的地方；

使用内存屏障(Memory Barrier)技术，实现单消费者和单生产者对kfifo的无锁并发访问，多个消费者、生产者的并发访问还是需要加锁的。

本文主要以下三个部分：

关于2的次幂问题，判断是不是2的次幂以及向上取整为2的次幂

Linux内核中kfifo的实现及简要分析

根据kfifo实现的循环缓冲区，并进行一些测试

关于内存屏障的本文不作过多分析，可以参考WikiMemory Barrier。另外，本文所涉及的整数都默认为无符号整数，不再做一一说明。

1. 2的次幂

判断一个数是不是2的次幂
kfifo要保证其缓存空间的大小为2的次幂，如果不是则向上取整为2的次幂。其对于2的次幂的判断方式也是很巧妙的。如果一个整数n是2的次幂，则二进制模式必然是1000...，而n-1的二进制模式则是0111...，也就是说n和n-1的每个二进制位都不相同，例如：8(1000)和7(0111)；n不是2的次幂，则n和n-1的二进制必然有相同的位都为1的情况，例如：7(0111)和6(0110)。这样就可以根据 n & (n-1)的结果来判断整数n是不是2的次幂，实现如下：

/* 判断n是否是2的幂 若n为2的次幂, 则 n & (n-1) == 0，也就是n和n-1的各个位都不相同。例如 8(1000)和7(0111） 若n不是2的次幂, 则 n & (n-1) != 0,也就是n和n-1的各个位肯定有相同的，例如7(0111)和6(0110) */ static inline bool is_power_of_2(uint32_t n) { return (n != 0 && ((n & (n - 1)) == 0)); }

将数字向上取整为2的次幂
如果设定的缓冲区大小不是2的次幂，则向上取整为2的次幂，例如：设定为5，则向上取为8。上面提到整数n是2的次幂，则其二进制模式为100...，故如果正数k不是n的次幂，只需找到其最高的有效位1所在的位置（从1开始计数）pos，然后1 << pos即可将k向上取整为2的次幂。实现如下：

static inline uint32_t roundup_power_of_2(uint32_t a) { if (a == 0) return 0; uint32_t position = 0; for (int i = a; i != 0; i >>= 1) position++; return static_cast<uint32_t>(1 << position); }

2. Linux实现kfifo及分析

Linux内核中kfifo实现技巧，主要集中在放入数据的put方法和取数据的get方法。代码如下：

unsigned int __kfifo_put(struct kfifo *fifo, unsigned char *buffer, unsigned int len) { unsigned int l; len = min(len, fifo->size - fifo->in + fifo->out); /* * Ensure that we sample the fifo->out index -before- we * start putting bytes into the kfifo. */ smp_mb(); /* first put the data starting from fifo->in to buffer end */ l = min(len, fifo->size - (fifo->in & (fifo->size - 1))); memcpy(fifo->buffer + (fifo->in & (fifo->size - 1)), buffer, l); /* then put the rest (if any) at the beginning of the buffer */ memcpy(fifo->buffer, buffer + l, len - l); /* * Ensure that we add the bytes to the kfifo -before- * we update the fifo->in index. */ smp_wmb(); fifo->in += len; return len; } unsigned int __kfifo_get(struct kfifo *fifo,unsigned char *buffer, unsigned int len) { unsigned int l; len = min(len, fifo->in - fifo->out); /* * Ensure that we sample the fifo->in index -before- we * start removing bytes from the kfifo. */ smp_rmb(); /* first get the data from fifo->out until the end of the buffer */ l = min(len, fifo->size - (fifo->out & (fifo->size - 1))); memcpy(buffer, fifo->buffer + (fifo->out & (fifo->size - 1)), l); /* then get the rest (if any) from the beginning of the buffer */ memcpy(buffer + l, fifo->buffer, len - l); /* * Ensure that we remove the bytes from the kfifo -before- * we update the fifo->out index. */ smp_mb(); fifo->out += len; return len; }