Linux内核中的循环缓冲区

Linux内核中的循环缓冲区（circular buffer）为解决某些特殊情况下的竞争问题提供了一种免锁的方法。这种特殊的情况就是当生产者和消费者都只有一个，而在其它情况下使用它也是必须要加锁的。循环缓冲区定义在include/linux/kfifo.h中，如下：struct kfifo {unsigned char *buffer;unsigned int size;unsigned int in;unsigned int out;spinlock_t *lock;};buffer指向存放数据的缓冲区，size是缓冲区的大小，in是写指针下标，out是读指针下标，lock是加到struct kfifo上的自旋锁（上面说的免锁不是免这里的锁，这个锁是必须的），防止多个进程并发访问此数据结构。当in==out时，说明缓冲区为空；当（in-out）==size时，说明缓冲区已满。为kfifo提供的接口可以分为两类，一类是满足上述情况下使用的，以双下划线开头，没有加锁的；另一类是在不满足的条件下，即需要额外加锁的情况下使用的。其实后一类只是在前一类的基础上进行加锁后的包装（也有一处进行了小的改进），实现中所加的锁是spin_lock_irqsave。清空缓冲区的函数：static inline void __kfifo_reset（struct kfifo *fifo）;static inline void kfifo_reset（struct kfifo *fifo）;这很简单，直接把读写指针都置为0即可。向缓冲区里放入数据的接口是：static inline unsigned int kfifo_put（struct kfifo *fifo, unsigned char *buffer, unsigned int len）;unsigned int __kfifo_put（struct kfifo *fifo, unsigned char *buffer, unsigned int len）;后者是在kernel/kfifo.c中定义的。这个接口是经过精心构造的，可以小心地避免一些边界情况。我们有必要一起来看一下它的具体实现。1 unsigned int __kfifo_put（struct kfifo *fifo,2 unsigned char *buffer, unsigned int len）3 {4 unsigned int l;56 len = min（len, fifo->size - fifo->in + fifo->out）;...13 smp_mb（）;1415 /* first put the data starting from fifo->in to buffer end */16 l = min（len, fifo->size - （fifo->in & （fifo->size - 1）））;17 memcpy（fifo->buffer + （fifo->in & （fifo->size - 1））, buffer, l）;1819 /* then put the rest （if any） at the beginning of the buffer */20 memcpy（fifo->buffer, buffer + l, len - l）;...27 smp_wmb（）;2829 fifo->in += len;3031 return len;32 }第6行，在len和（fifo->size - fifo->in + fifo->out）之间取一个较小的值赋给len。注意，当（fifo->in == fifo->out+fifo->size）时，表示缓冲区已满，此时得到的较小值一定是0，后面实际写入的字节数也全为0。另一种边界情况是当len很大时（因为len是无符号的，负数对它来说也是一个很大的正数），这一句也能保证len取到一个较小的值，因为fifo->in总是大于等于fifo->out，所以后面的那个表达式的值不会超过fifo->size的大小。第13行和第27行是加内存屏障，这里不是我们讨论的范围，你可以忽略它。