- struct kfifo {
- unsigned char *buffer;
- unsigned int size;
- unsigned int in;
- unsigned int out;
- spinlock_t *lock;
- };
- struct kfifo *kfifo_alloc(unsigned int size, gfp_t gfp_mask, spinlock_t *lock)
- {
- unsigned char *buffer;
- struct kfifo *ret;
-
-
- 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);
-
- ret = kfifo_init(buffer, size, gfp_mask, lock);
-
- if (IS_ERR(ret))
- kfree(buffer);
-
- return ret;
- }
这里值得一提的是，kfifo->size的值总是在调用者传进来的size参数的基础上向2的幂扩展，这是内核一贯的做法。这样的好处不言而喻--对kfifo->size取模运算可以转化为与运算，如下：
kfifo->in % kfifo->size 可以转化为 kfifo->in & (kfifo->size – 1)
在kfifo_alloc函数中，使用size & (size – 1)来判断size 是否为2幂，如果条件为真，则表示size不是2的幂，然后调用roundup_pow_of_two将之向上扩展为2的幂。 这些都是很常用的技巧，只不过大家没有将它们结合起来使用而已，下面要分析的__kfifo_put和__kfifo_get则是将kfifo->size的特点发挥到了极致。
3. __kfifo_put和__kfifo_get，巧妙的入队和出队操作，无锁并发
__kfifo_put是入队操作，它先将数据放入buffer里面，最后才修改in参数；__kfifo_get是出队操作，它先将数据从buffer中移走，最后才修改out。你会发现in和out两者各司其职。计算机科学家已经证明，当只有一个读经程和一个写线程并发操作时，不需要任何额外的锁，就可以确保是线程安全的，也即kfifo使用了无锁编程技术，以提高kernel的并发。
下面是__kfifo_put和__kfifo_get的代码
- 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);
-
-
-
- smp_mb();
-
-
- l = min(len, fifo->size - (fifo->in & (fifo->size - 1)));
- memcpy(fifo->buffer + (fifo->in & (fifo->size - 1)), buffer, l);
-
-
- memcpy(fifo->buffer, buffer + l, len - l);
-
-
-
- smp_wmb();
-
- fifo->in += len;
-
- return len;
- }
-
- unsigned int __kfifo_get(struct kfifo *fifo,
- unsigned char *buffer, unsigned int len)
- {
- unsigned int l;
-
- len = min(len, fifo->in - fifo->out);
-
-
-
- smp_rmb();
-
-
- l = min(len, fifo->size - (fifo->out & (fifo->size - 1)));
- memcpy(buffer, fifo->buffer + (fifo->out & (fifo->size - 1)), l);
-
-
- memcpy(buffer + l, fifo->buffer, len - l);
-
-
-
- smp_mb();
-
- fifo->out += len;
-
- return len;
- }
转 Linux kernel 无锁队列,布布扣,bubuko.com
转 Linux kernel 无锁队列
原文：http://www.cnblogs.com/happy-pm/p/3831530.html
