转 Linux kernel 无锁队列
浏览数：39 /
时间：2015年06月20日
- 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 */
- };
- struct kfifo *kfifo_alloc(unsigned int size, gfp_t gfp_mask, spinlock_t *lock)
- {
- unsigned char *buffer;
- struct kfifo *ret;
- /*
- * 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);
- 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);
- /*
- * 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.
- */
- 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);
- /*
- * 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.
- */
- smp_mb();
- fifo->out += len;
- return len;
- }
郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。
