前言
环形缓冲区是很常用的数据结构,用途很广泛。我目前遇到的使用场景就是TCP分片转回TCP流,一个线程读取TCP分片拆包,写入缓存区,另一个线程从缓存区中读取,互相不影响。
为此Google了一番,发现了kfifo这个Linux内核的实现,十分精妙。
原理
基本原理
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 */
};
先看一下基本定义,buffer是数据缓存区,size是缓存区长度,in/out是输入输出指针位置(%size后就是真实指针了)。
size需要检测是否为2的次幂,不是的话需要升到2的次幂。方便后续计算。(可以看内核的roundup_pow_of_two实现)
in、out每次操作都+对应的读写长度,通过取模运算回落size区间。
data := kfifo.buffer[kfifo.out % kfifo.size:kfifo.in % kfifo.size]
data就是有效数据的缓存区区间。
快速取模
kfifo使用了二进制的位运算实现了2的幂取模运算,并且利用了无符号数的溢出做回绕。很精妙的设计。
首先,缓存区尺寸要取整为2的幂次,这样可以利用位运算进行取模。
M mod N = M & (N-1)
,当N为2的幂次时有效。
取模运算对于计算机来说运算速度也是很慢的(虽然你感觉不出来),而位运算就是分分钟的事了。
回绕
无符号数溢出后,就会变成0从头开始,借助这个特性可以绕开逻辑判断。