Linux kernal 鬼斧神工，博大精深，让人叹为观止，拍手叫绝。然匠心独运的设计并非扑朔迷离、盘根错节，真正的匠心独运乃辞简理博、化繁为简，在简洁中昭显优雅和智慧，kfifo就是这样一种数据结构，它就是这样简约高效，匠心独运，妙不可言，下面就跟大家一起探讨学习。
一、kfifo概述 本文分析的原代码版本 2.6.32.63kfifo的头文件 include/linux/kfifo.h
kfifo的源文件 kernel/kfifo.c
kfifo是一种"First In First Out “数据结构，它采用了前面提到的环形缓冲区来实现，提供一个无边界的字节流服务。采用环形缓冲区的好处为，当一个数据元素被用掉后，其余数据元素不需要移动其存储位置，从而减少拷贝提高效率。更重要的是，kfifo采用了并行无锁技术，kfifo实现的单生产/单消费模式的共享队列是不需要加锁同步的。
1: struct kfifo { 2: unsigned char *buffer; /* the buffer holding the data */ 3: unsigned int size; /* the size of the allocated buffer */ 4: unsigned int in; /* data is added at offset (in % size) */ 5: unsigned int out; /* data is extracted from off. (out % size) */ 6: spinlock_t *lock; /* protects concurrent modifications */ 7: };
buffer
用于存放数据的缓存
size
缓冲区空间的大小，在初化时，将它向上圆整成2的幂
in
指向buffer中队头
out
指向buffer中的队尾
lock
如果使用不能保证任何时间最多只有一个读线程和写线程，必须使用该lock实施同步。
它的结构如图：
这看起来与普通的环形缓冲区没有什么差别，但是让人叹为观止的地方就是它巧妙的用 in 和 out 的关系和特性，处理各种操作，下面我们来详细分析。
二、kfifo内存分配和初始化首先，看一个很有趣的函数，判断一个数是否为2的次幂，按照一般的思路，求一个数n是否为2的次幂的方法为看 n % 2 是否等于0， 我们知道“取模运算”的效率并没有 “位运算” 的效率高，有兴趣的同学可以自己做下实验。下面再验证一下这样取2的模的正确性，若n为2的次幂，则n和n-1的二进制各个位肯定不同 (如8(1000)和7(0111))，&出来的结果肯定是0；如果n不为2的次幂，则各个位肯定有相同的 (如7(0111) 和6(0110))，&出来结果肯定为0。是不是很巧妙？
1: bool is_power_of_2(unsigned long n) 2: { 3: return (n != 0 && ((n & (n - 1)) == 0)); 4: }
再看下kfifo内存分配和初始化的代码，前面提到kfifo总是对size进行2次幂的圆整，这样的好处不言而喻，可以将kfifo->size取模运算可以转化为与运算，如下：
kfifo->in % kfifo->size 可以转化为 kfifo->in & (kfifo->size – 1)
“取模运算”的效率并没有 “位运算” 的效率高还记得不，不放过任何一点可以提高效率的地方。
1: struct kfifo *kfifo_alloc(unsigned int size, gfp_t gfp_mask, spinlock_t *lock) 2: { 3: unsigned char *buffer; 4: struct kfifo *ret; 5: 6: /* 7: * round up to the next power of 2, since our 'let the indices 8: * wrap' technique works only in this case. 9: */ 10: if (!is_power_of_2(size)) { 11: BUG_ON(size > 0x80000000); 12: size = roundup_pow_of_two(size); 13: } 14: 15: buffer = kmalloc(size, gfp_mask); 16: if (!buffer) 17: return ERR_PTR(-ENOMEM); 18: 19: ret = kfifo_init(buffer, size, gfp_mask, lock); 20: 21: if (IS_ERR(ret)) 22: kfree(buffer); 23: 24: return ret; 25: }
三、kfifo并发无锁奥秘---内存屏障