本文共 6154 字,大约阅读时间需要 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 */};它的结构如图: 这看起来与普通的环形缓冲区没有什么差别,但是让人叹为观止的地方就是它巧妙的用 in 和 out 的关系和特性,处理各种操作,下面我们来详细分析。
首先,看一个很有趣的函数,判断一个数是否为2的次幂,按照一般的思路,求一个数n是否为2的次幂的方法为看 n % 2 是否等于0, 我们知道“取模运算”的效率并没有 “位运算” 的效率高,有兴趣的同学可以自己做下实验。下面再验证一下这样取2的模的正确性,若n为2的次幂,则n和n-1的二进制各个位肯定不同 (如8(1000)和7(0111)),&出来的结果肯定是0;如果n不为2的次幂,则各个位肯定有相同的 (如7(0111) 和6(0110)),&出来结果肯定为0。是不是很巧妙?
bool is_power_of_2(unsigned long n){ return (n != 0 && ((n & (n - 1)) == 0));}
再看下kfifo内存分配和初始化的代码,前面提到kfifo总是对size进行2次幂的圆整,这样的好处不言而喻,可以将kfifo->size取模运算可以转化为与运算,如下:
kfifo->in % kfifo->size 可以转化为 kfifo->in & (kfifo->size – 1)
“取模运算”的效率并没有 “位运算” 的效率高还记得不,不放过任何一点可以提高效率的地方。
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' technique works only in this case. */ if (!is_power_of_2(size)) { 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实现的单生产/单消费模式的共享队列是不需要加锁同步的呢?==天底下没有免费的午餐的道理人人都懂,下面我们就来看看kfifo实现并发无锁的奥秘。
我们知道 编译器编译源代码时,会将源代码进行优化,将源代码的指令进行重排序,以适合于CPU的并行执行。然而,内核同步必须避免指令重新排序,优化屏障(Optimization barrier)避免编译器的重排序优化操作,保证编译程序时在优化屏障之前的指令不会在优化屏障之后执行。
举个例子,如果多核CPU执行以下程序:
a = 1;b = a + 1;assert(b == 2);
假设初始时a和b的值都是0,a处于CPU1-cache中,b处于CPU0-cache中。如果按照下面流程执行这段代码:
1 CPU0执行a=1; 2 因为a在CPU1-cache中,所以CPU0发送一个read invalidate消息来占有数据 3 CPU0将a存入store buffer 4 CPU1接收到read invalidate消息,于是它传递cache-line,并从自己的cache中移出该cache-line 5 CPU0开始执行b=a+1; 6 CPU0接收到了CPU1传递来的cache-line,即“a=0” 7 CPU0从cache中读取a的值,即“0” 8 CPU0更新cache-line,将store buffer中的数据写入,即“a=1” 9 CPU0使用读取到的a的值“0”,执行加1操作,并将结果“1”写入b(b在CPU0-cache中,所以直接进行) 10 CPU0执行assert(b == 2); 失败
软件可通过读写屏障强制内存访问次序。读写屏障像一堵墙,所有在设置读写屏障之前发起的内存访问,必须先于在设置屏障之后发起的内存访问之前完成,确保内存访问按程序的顺序完成。Linux内核提供的内存屏障API函数说明如下表。内存屏障可用于多处理器和单处理器系统,如果仅用于多处理器系统,就使用smp_xxx函数,在单处理器系统上,它们什么都不要。
如果对上述代码加上内存屏障,就能保证在CPU0取a时,一定已经设置好了a = 1:void foo(void){ a = 1; smp_wmb(); b = a + 1;}
__kfifo_put是入队操作,它先将数据放入buffer中,然后移动in的位置,其源代码如下:
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;}
__kfifo_get是出队操作,它从buffer中取出数据,然后移动out的位置,其源代码如下:
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;}
这里图解一下 in 先溢出的情况,size = 64, 写入前 in = 4294967291, out = 4294967279 ,数据 in – out = 12;
写入 数据16个字节,则 in + 16 = 4294967307,溢出为 11,此时 in – out = –4294967268,溢出为28,数据长度仍然正确, 由此可见,在这种特殊情况下,这种计算仍然正确,是不是让人叹为观止,妙不可言? 原文链接:转载地址:http://yvxcn.baihongyu.com/