linux内核之无锁缓冲队列kfifo原理（结合项目实践）

6行，可去读的长度为fifo->in – fifo->out，让读的长度取len和剩余容量中较小的，避免读越界；
13行，加读内存屏障，保证在开始取数据之前，fifo->in取到正确的值（另一个cpu可能正在改写in值）
16行，前面讲到fifo->size已经2的次幂圆整，而且kfifo->out % kfifo->size 可以转化为 kfifo->out & (kfifo->size – 1)，所以fifo->size - (fifo->out & (fifo->size - 1)) 即位 fifo->out 到 buffer末尾所剩余的长度，l取len和剩余长度的最小值，即为从fifo->buffer + fifo->in到末尾所要去读的长度。
17行，从fifo->buffer + fifo->out的位置开始读取l长度，如果l = len，则已读取完成，第20行len – l 为0，将不执行，如果l =fifo->size - (fifo->out & (fifo->size - 1)) ，则第20行还需从buffer头部读取 len – l 长。
27行，加内存屏障，保证在修改out前，已经从buffer中取走了数据，如果不加屏障，可能先执行了增加out的 *** 作，数据还没取完，令一个cpu可能已经往buffer写数据，将数据破坏，因为写数据是通过fifo->size - (fifo->in & (fifo->size - 1))来判断的 。
29行，注意这里 只是用了 fifo->out += len 也未取模，同样unsigned int的溢出性质，当out 持续增加到溢出时又会被置为0，如果in先溢出，出现 in < out 的情况，那么 in – out 为负数（又将溢出），in – out 的值还是为buffer中数据的长度。

图解一下 in 先溢出的情况，size = 64， 写入前 in = 4294967291， out = 4294967279 ，数据 in – out = 12;

计算机科学家已经证明，当只有一个读经程和一个写线程并发 *** 作时，不需要任何额外的锁，就可以确保是线程安全的，也即kfifo使用了无锁编程技术，以提高kernel的并发。

kfifo使用in和out两个指针来描述写入和读取游标，对于写入 *** 作，只更新in指针，而读取 *** 作，只更新out指针，可谓井水不犯河水，示意图如下：

                                               |<--写入-->|+--------------------------------------------------------------+|                        |<----------data----->|               |+--------------------------------------------------------------+                         |<--读取-->|                         ^                     ^               ^                         |                     |               |                        out                   in              size

为了避免读者看到写者预计写入，但实际没有写入数据的空间，写者必须保证以下的写入顺序：

1.往[kfifo->in, kfifo->in + len]空间写入数据
2.更新kfifo->in指针为 kfifo->in + len

在 *** 作1完成时，读者是还没有看到写入的信息的，因为kfifo->in没有变化，认为读者还没有开始写 *** 作，只有更新kfifo->in之后，读者才能看到。

那么如何保证1必须在2之前完成，秘密就是使用内存屏障：smp_mb()，smp_rmb(), smp_wmb()，来保证对方观察到的内存 *** 作顺序。

kfifo优点：

读完kfifo代码，令我想起那首诗“众里寻他千百度，默然回首，那人正在灯火阑珊处”。不知你是否和我一样，总想追求简洁，高质量和可读性的代码，当用尽各种方法，江郞才尽之时，才发现linux kernel里面的代码就是我们寻找和学习的对象。

思想和上面差不多，只不过把队列内容改为了指针，是为了我们项目存储数据（使用时malloc）用到。废话不多说，直接上源码：

struct kfifo {	voID  **data;    /* the buffer holding the data */	unsigned int size;    /* the count of the data */	unsigned int pod;    /* productor */	unsigned int cons;    /* consumer */};static inline uint32_t roundup_power_of_two(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);}struct kfifo* kfifo_alloc(uint32_t size){	struct kfifo* fifo;	if (size & (size - 1))	{		size = roundup_pow_of_two(size);	}	FORCE_DEBUG(w_log_fp, "kfifo_alloc file stream queue len:%d n", size);	fifo = (struct kfifo* )malloc(sizeof(struct kfifo));	fifo->data = (voID**)malloc(size * sizeof(voID*));	fifo->size = size;	fifo->pod = 0;	fifo->cons = 0;	return fifo;}voID kfifo_free(struct kfifo* fifo){	uint32_t i = 0;	for ( i = 0; i < fifo->size; i++ )	{		free(fifo->data[i]);	}	free(fifo);}int kfifo_put(struct kfifo* fifo, voID * data){	if ( data == NulL )		return 0;   if (fifo->pod - fifo->cons < fifo->size)   {      fifo->data[fifo->pod & (fifo->size - 1) ] = data;      fifo->pod++;      return 1;   }   else      return 0;}voID* kfifo_get(struct kfifo* fifo){   voID * result = NulL;   if (fifo->pod != fifo->cons)   {      result = fifo->data[fifo->cons & (fifo->size - 1) ];      fifo->cons++;   }   return result;}