1 循环缓冲区在一些竞争问题上提供了一种免锁的机制，免锁的前提是，生产者和消费2 都只有一个的情况下，否则也要加锁。下面就内核中提取出来，而经过修改后的fifo进3 行简要的分析。4 5 先看其只要数据结构：6 struct my_fifo {7 unsignedchar *buffer;/* the buffer holding the data*/8 unsignedint size;/* the size of the allocated buffer*/9 unsignedint in;/* data is added at offset (in % size)*/10 unsignedint out;/* data is extracted from off. (out % size)*/11 };12 也不用多说，一看就明白。size, in, out 都设成无符号型的，因为都不存在负值的情13 型。14 15 /*16 form kernel/kfifo.c17 */18 19 #include <stdio.h>20 #include <stdlib.h>21 #include <fifo.h>22 23 #define min(a,b) ((a) < (b) ? (a):(b))24 /*25 my_fifo_init26 */27 struct my_fifo *my_fifo_init(unsignedchar *buffer,unsignedint size)28 {29 struct my_fifo *fifo;30 31 32 fifo = malloc(sizeof(struct my_fifo));33 if (!fifo)34 returnNULL;35 36 fifo->buffer = buffer;37 fifo->size = size;38 fifo->in = fifo->out = 0;39 40 return fifo;41 }42 这个初始化fifo结构的函数一般也不会在应用层里进行调用，而是被下面的fifo_alloc43 调用。依我的观点来看，这两个函数合成一个函数会更加的清晰,但是这一情况只针对
buffer是系统开辟的空间，如果buffer的空间是由其它的函数来提供，就只能用上面的这个函数。
44 /*45 my_fifo_alloc46 */47 struct my_fifo *my_fifo_alloc(unsignedint size)48 {49 unsignedchar *buffer;50 struct my_fifo *ret;51 52 /*53 * round up to the next power of 2, since our ‘let the indices54 * wrap’ tachnique works only in this case.55 */56 57 buffer = malloc(size);58 if (!buffer)59 returnNULL;60 61 ret = my_fifo_init(buffer, size);62 63 if (ret ==NULL)64 free(buffer);65 66 return ret;67 }68 /*69 * my_fifo_free70 */71 void my_fifo_free(struct my_fifo *fifo)72 {73 free(fifo->buffer);74 free(fifo);75 }76 77 这两个函数也不作过多的分析，都很清晰。
78 /*79 my_fifo_put()80 */81 unsignedint my_fifo_put(struct my_fifo *fifo,82 unsignedchar *buffer,unsigned int len)83 {84 unsignedint l;85 86 len = min(len, fifo->size – fifo->in + fifo->out);/*可能是缓冲区的空闲长度或者要写长度*/87 88 /* first put the data starting from fifo->in to buffer end*/89 l = min(len, fifo->size – (fifo->in & (fifo->size -1)));90 memcpy(fifo->buffer + (fifo->in & (fifo->size -1)), buffer, l);91 92 /* then put the rest (if any) at the beginning of the buffer*/93 memcpy(fifo->buffer, buffer + l, len – l);94 95 fifo->in += len;96 97 return len;98 }
99 100 /*101 my_fifo_get102 */103 unsignedint my_fifo_get(struct my_fifo *fifo,104 unsignedchar *buffer,unsigned int len)105 {106 unsignedint l;107 108 len = min(len, fifo->in – fifo->out); /*可读数据*/109 110 /* first get the data from fifo->out until the end of the buffer*/111 l = min(len, fifo->size – (fifo->out & (fifo->size -1)));112 memcpy(buffer, fifo->buffer + (fifo->out & (fifo->size -1)), l);113 114 /* then get the rest (if any) from the beginning of the buffer*/115 memcpy(buffer + l, fifo->buffer, len – l);116 117 fifo->out += len;118 119 return len;120 }121 这两个读写结构才是循环缓冲区的重点。在fifo结构中，size是缓冲区的大小，是由用122 户自己定义的，但是在这个设计当中要求它的大小必须是2的幂次。123 当in==out时，表明缓冲区为空的，当(in-out)==size 时，说明缓冲区已满。124 125 我们看下具体实现，在86行处如果size-in+out ==0,也即获得的len值会0，而没有数126 据写入到缓冲区中。所以在设计缓冲区的大小的时候要恰当，读出的速度要比定入的速127 度要快，否则缓冲区满了会使数据丢失，可以通过成功写入的反回值来做判断尝试再次128 写入.129 另一种情况则是缓冲区有足够的空间给要写入的数据，但是试想一下，如果空闲的空间130 在缓冲的首尾两次，这又是如何实现呢？这部分代码实现得非常巧妙。131 我们看fifo->in &(fifo->size-1) 这个表达式是什么意思呢？我们知道size是2的幂次132 项，那么它减1即表示其值的二进制所有位都为1，与in相与的最终结果是in%size,比133 size要小，所以看in及out的值都是不断地增加，但再相与操作后，它们即是以size为134 周期的一个循环。89行就是比较要写入的数据应该是多少，如果缓冲区后面的还有足够135 的空间可写，那么把全部的值写到后面，否则写满后面，再写到前面去93行。136 读数据也可以作类似的分析，108行表示请求的数据要比缓冲区的数据要大时，只137 读取缓冲区中可用的数据。138 139 staticinlinevoid my_fifo_reset(struct my_fifo *fifo)140 {141 fifo->in = fifo->out = 0;142 }143 144 staticinlineunsigned int my_fifo_len(struct my_fifo *fifo)145 {146 return fifo->in – fifo->out;147 }148 149 在头文件里还有缓冲区置位及返回缓冲区中数据大小两个函数，很简单，不必解释。
你可能付出一定的代价，但日后你得到的，远比付出的多得多。
