kfifo是内核里面的一个First In First Out数据结构，它采用环形循环队列的数据结构来实现，提供一个无边界的字节流服务，并且使用并行无锁编程技术，即当它用于只有一个入队线程和一个出队线程的场情时，两个线程可以并发操作，而不需要任何加锁行为，就可以保证kfifo的线程安全。
kfifo代码既然肩负着这么多特性，那我们先一敝它的代码：
2.1 kfifo数据结构
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 */ };
/* * round up to the next power of 2, since our 'let the indices * wrap' tachnique works only in this case. */ if (size & (size - 1)) { BUG_ON(size > 0x80000000); size = roundup_pow_of_two(size); }
buffer = kmalloc(size, gfp_mask); if (!buffer) return ERR_PTR(-ENOMEM);
unsigned int__kfifo_put(struct kfifo *fifo, unsigned char *buffer, unsigned int len) { unsigned int l;
len = min(len, fifo->size - fifo->in + fifo->out);
/* * Ensure that we sample the fifo->out index -before- we * start putting bytes into the kfifo. */
smp_mb();
/* first put the data starting from fifo->in to buffer end */ l = min(len, fifo->size - (fifo->in & (fifo->size - 1))); memcpy(fifo->buffer + (fifo->in & (fifo->size - 1)), buffer, l);
/* then put the rest (if any) at the beginning of the buffer */ memcpy(fifo->buffer, buffer + l, len - l);
/* * Ensure that we add the bytes to the kfifo -before- * we update the fifo->in index. */
l = min(len, fifo->size - (fifo->in & (fifo->size - 1)));
这个表达式计算当前写入的空间，换成人可理解的语言就是：
l = kfifo可写空间和预期写入空间的最小值
使用min宏来代if-else分支
__kfifo_get也应用了同样技巧，代码如下：
unsigned int__kfifo_get(struct kfifo *fifo, unsigned char *buffer, unsigned int len) { unsigned int l;
len = min(len, fifo->in - fifo->out);
/* * Ensure that we sample the fifo->in index -before- we * start removing bytes from the kfifo. */
smp_rmb();
/* first get the data from fifo->out until the end of the buffer */ l = min(len, fifo->size - (fifo->out & (fifo->size - 1))); memcpy(buffer, fifo->buffer + (fifo->out & (fifo->size - 1)), l);
/* then get the rest (if any) from the beginning of the buffer */ memcpy(buffer + l, fifo->buffer, len - l);
/* * Ensure that we remove the bytes from the kfifo -before- * we update the fifo->out index. */
第二块当然是：[0, len - (kfifo->size - kfifo->in % kfifo->size)]
下面是代码，细细体味吧：
/* first put the data starting from fifo->in to buffer end */ l = min(len, fifo->size - (fifo->in & (fifo->size - 1))); memcpy(fifo->buffer + (fifo->in & (fifo->size - 1)), buffer, l);
/* then put the rest (if any) at the beginning of the buffer */ memcpy(fifo->buffer, buffer + l, len - l);
/* * __kfifo_put - puts some data into the FIFO, no locking version * @fifo: the fifo to be used. * @buffer: the data to be added. * @len: the length of the data to be added. * * This function copies at most 'len' bytes from the 'buffer' into * the FIFO depending on the free space, and returns the number of * bytes copied. * * Note that with only one concurrent reader and one concurrent * writer, you don't need extra locking to use these functions. */
unsigned intkfifo_put(kfifo *fifo, unsigned char *buffer, unsigned int len) { unsigned int l = 0;
len = MIN(len, fifo->size - fifo->in + fifo->out); /* first put the data starting from fifo->in to buffer end*/
/* then put the rest (if any) at the beginning of the buffer*/
memcpy(fifo->buffer, buffer + l, len - l);
fifo->in += len;
return len; }
/* * __kfifo_get - gets some data from the FIFO, no locking version * @fifo: the fifo to be used. * @buffer: where the data must be copied. * @len: the size of the destination buffer. * * This function copies at most 'len' bytes from the FIFO into the * 'buffer' and returns the number of copied bytes. * * Note that with only one concurrent reader and one concurrent * writer, you don't need extra locking to use these functions. */ unsigned intkfifo_get(kfifo *fifo, unsigned char *buffer, unsigned int len) { unsigned int l = 0;
len = MIN(len, fifo->in - fifo->out);
/* first get the data from fifo->out until the end of the buffer*/ l = MIN(len, fifo->size - (fifo->out & (fifo->size - 1))); memcpy(buffer, fifo->buffer + (fifo->out & (fifo->size - 1)), l);
/* then get the rest (if any) from the beginning of the buffer*/ memcpy(buffer + l, fifo->buffer, len - l);
/* * __kfifo_reset - removes the entire FIFO contents, no locking version * @fifo: the fifo to be emptied. */ voidkfifo_reset(kfifo *fifo) { fifo->in = fifo->out = 0; }
/* * __kfifo_len - returns the number of bytes available in the FIFO, no locking version * @fifo: the fifo to be used. */ unsigned intkfifo_len(kfifo *fifo) { return fifo->in - fifo->out; }
