被Linux内核用C写的kfifo无锁设计惊艳到了~

正文大家好我是bug菌~你一定遇到过这样的噩梦多线程共享一个队列为了线程安全不得不加锁结果锁竞争导致性能暴跌加锁确实是一门学问哈然后好不容易优化了锁又遇到了缓存伪共享想动态分配内存又怕在中断上下文里触发死锁。你可能像我一样手搓过无数个环形队列其实在Linux内核里有一个叫kfifo的无锁环形队列不到100行核心代码设计非常的巧妙几乎能够解决我上面提到的所有问题所以我被它的惊艳所折服所以必须写一篇文章来剥一下kfifo的神秘面纱了看看它是如何用几个简单的数学技巧和内存屏障在单生产者单消费者场景下实现真正的无锁并发。1为什么需要kfifo在嵌入式开发中生产者-消费者模型无处不在串口中断接收数据主线程处理传感器采集数据后台线程存储网络数据包接收应用层解析不管是在RTOS还是嵌入式linux中通常我们会定义一个环形缓冲区加一个互斥锁保护读写操作。但这种方式有三个比较麻烦的问题1、首先是锁竞争的开销每次读写都要加锁解锁在高频数据场景下锁的开销甚至超过了数据处理本身。2、然后是死锁的风险如果在中断上下文里尝试获取已经被持有的锁直接导致系统崩溃。3、最好是缓存伪共享这个主要是在带cache缓存时锁变量和队列变量放在同一个缓存行导致频繁的缓存失效。那么kfifo的出现几乎非常完美解决了这些问题。它在单生产者单消费者SPSC场景下不需要任何锁就能保证线程安全性能比加锁队列高出一个数量级。2核心设计技巧这里就要聊聊kfifo的设计哲学:通过限制使用场景来获得极致性能。这也是我为什么非常喜欢kfifo的原因它也是嵌入式软件设计中一个非常重要的思想。它只支持单生产者单消费者缓冲区大小必须是2的幂次方。正是这两个看似苛刻的限制换来了无与伦比的性能优势。技巧一unsigned int索引的自然回绕彻底告别取模运算传统环形队列最让人头疼的就是索引回绕问题。我们通常会这样写in (in 1) % size; out (out 1) % size;但取模运算%在CPU上是一个非常昂贵的操作需要几十个时钟周期kfifo是怎么做的呢它把in和out索引定义为unsigned int类型并且永远不让它们回绕让它们一直单调递增直到溢出。struct kfifo { unsigned char *buffer; unsigned int size; unsigned int in; // 写入索引一直递增 unsigned int out; // 读取索引一直递增 };那索引溢出了怎么办利用C语言中无符号整数的溢出特性当unsigned int超过最大值时会自动从0开始重新计数。这是C语言标准明确规定的行为不是未定义行为这正是kfifo最精妙的地方更神奇的是无论in和out怎么溢出in - out永远等于队列中已有的数据长度// 已用空间无论in和out怎么溢出结果永远正确 unsigned int used fifo-in - fifo-out; // 空闲空间 unsigned int free fifo-size - used; // 判断空满 bool is_empty (fifo-in fifo-out); bool is_full (used fifo-size);一个简单的减法就解决了传统环形队列中判断空满的复杂逻辑nice~那实际访问缓冲区时怎么办呢因为缓冲区大小是2的幂次方我们可以用位运算来代替取模前面bug菌也写过类似的文章当缓冲区大小必须是2的幂次方时候编译器都会帮我们优化不过需要注意前提条件:// 等价于 in % size但速度快10倍以上 unsigned int pos fifo-in (fifo-size - 1);位运算在CPU上是单周期指令比取模运算快得多。这就是为什么kfifo要求缓冲区大小必须是2的幂次方的原因。技巧二分离的in/out索引天然的安全区间分离你应该bug菌开始的时候一样会问:为什么两个线程同时修改in和out不会有竞态条件主要的原因是生产者只修改in消费者只修改out。生产者只读out只写in消费者只读in只写out这就像两个人用同一张环形便签纸留言写的人只负责在空白处写字然后把笔往前移读的人只负责在有字的地方读然后把笔往前移只要两个人不交叉操作同一个位置就不会有任何冲突。生产者看到的安全区间[in, out size)消费者看到的安全区间[out, in)这两个区间永远不会重叠因为in - out size。技巧三精准的内存屏障杜绝幽灵数据很多人以为kfifo不需要任何同步机制这是大错特错的。kfifo不需要锁但它需要内存屏障。现代CPU为了提高性能会对指令进行乱序执行编译器为了优化也会对代码进行重排。如果没有内存屏障可能会出现这样的情况// 生产者代码 memcpy(fifo-buffer pos, data, len); // 1. 写数据 fifo-in len; // 2. 更新索引CPU可能会把这两条指令的顺序颠倒过来先更新in索引再写数据。这会导致什么后果消费者看到in索引更新了以为有新数据可读结果读到的还是旧数据——这就是所谓的幽灵数据。那么kfifo是如何解决这个问题的呢在写数据和更新索引之间插入一个写内存屏障smp_wmb()。memcpy(fifo-buffer pos, data, len); smp_wmb(); // 写内存屏障保证前面的写操作全部完成 fifo-in len;同样在消费者这边也需要一个读内存屏障smp_rmb()memcpy(data, fifo-buffer pos, len); smp_rmb(); // 读内存屏障保证前面的读操作全部完成 fifo-out len;内存屏障就像一堵墙它不禁止所有乱序只禁止墙两边的内存操作互相穿越。这是一种非常轻量级的同步机制开销比锁小得多。3解读内核源码让我们来看看Linux内核中kfifo的核心实现说实在C真的优雅。我会去掉一些无关的宏定义保留最核心的逻辑。1、数据结构定义struct __kfifo { unsigned int in; // 写入索引 unsigned int out; // 读取索引 unsigned int mask; // size - 1用于位运算 unsigned int esize; // 每个元素的大小 void *data; // 缓冲区指针 };注意这里用了mask而不是size因为mask size - 1这样每次计算位置时就不用再减1了又是一个微小的性能优化。2、计算空闲空间static inline unsigned int kfifo_unused(struct __kfifo *fifo) { return (fifo-mask 1) - (fifo-in - fifo-out); }fifo-mask 1就是缓冲区大小fifo-in - fifo-out就是已用空间相减就是空闲空间够简洁吧。3、写入数据核心函数unsigned int __kfifo_in(struct __kfifo *fifo, constvoid *buf, unsignedint len) { unsignedint l; // 最多只能写入空闲空间大小的数据 len min(len, kfifo_unused(fifo)); // 第一步计算从当前in位置到缓冲区末尾的长度 l min(len, fifo-mask 1 - (fifo-in fifo-mask)); // 先拷贝尾部数据 memcpy(fifo-data (fifo-in fifo-mask), buf, l); // 如果还有剩余数据从缓冲区头部开始拷贝 memcpy(fifo-data, buf l, len - l); // 写内存屏障确保数据全部写入后再更新in索引 smp_wmb(); // 更新写入索引 fifo-in len; return len; }即使不需要回绕len - l等于0memcpy也什么都不做。这就是kfifo代码的优雅之处用统一的逻辑处理所有情况避免分支预测失败带来的性能损失所以你几乎看到if else。4、读取数据核心函数unsigned int __kfifo_out(struct __kfifo *fifo, void *buf, unsignedint len) { unsignedint l; // 最多只能读取已用空间大小的数据 len min(len, fifo-in - fifo-out); // 第一步计算从当前out位置到缓冲区末尾的长度 l min(len, fifo-mask 1 - (fifo-out fifo-mask)); // 先拷贝尾部数据 memcpy(buf, fifo-data (fifo-out fifo-mask), l); // 如果还有剩余数据从缓冲区头部开始拷贝 memcpy(buf l, fifo-data, len - l); // 读内存屏障确保数据全部读取后再更新out索引 smp_rmb(); // 更新读取索引 fifo-out len; return len; }和写入函数几乎对称同样几乎看不到if语句。下面是一个简化版的示例供参考:#include stdint.h #include string.h // 内存屏障定义根据你的平台修改 #if defined(__ARM_ARCH) // ARM Cortex-M系列使用__DMB()数据内存屏障 #define smp_wmb() __DMB() #define smp_rmb() __DMB() #elif defined(__GNUC__) // GCC编译器使用内置函数 #define smp_wmb() __sync_synchronize() #define smp_rmb() __sync_synchronize() #else // 其他平台至少需要一个编译器屏障 #define smp_wmb() asm volatile( ::: memory) #define smp_rmb() asm volatile( ::: memory) #endif // kfifo数据结构 typedefstruct { uint8_t *buffer; // 缓冲区指针 uint32_t size; // 缓冲区大小必须是2的幂次 uint32_t mask; // size - 1 uint32_t in; // 写入索引 uint32_t out; // 读取索引 } kfifo_t; // 初始化kfifo // 注意size必须是2的幂次 void kfifo_init(kfifo_t *fifo, uint8_t *buffer, uint32_t size) { fifo-buffer buffer; fifo-size size; fifo-mask size - 1; fifo-in 0; fifo-out 0; } // 写入数据 uint32_t kfifo_put(kfifo_t *fifo, const uint8_t *data, uint32_t len) { uint32_t l; // 计算可写入的最大长度 len len (fifo-size - (fifo-in - fifo-out)) ? len : (fifo-size - (fifo-in - fifo-out)); // 计算从当前位置到缓冲区末尾的长度 l len (fifo-size - (fifo-in fifo-mask)) ? len : (fifo-size - (fifo-in fifo-mask)); // 拷贝第一部分数据 memcpy(fifo-buffer (fifo-in fifo-mask), data, l); // 拷贝第二部分数据如果需要回绕 memcpy(fifo-buffer, data l, len - l); // 写内存屏障确保数据全部写入后再更新索引 smp_wmb(); // 更新写入索引 fifo-in len; return len; } // 读取数据 uint32_t kfifo_get(kfifo_t *fifo, uint8_t *data, uint32_t len) { uint32_t l; // 计算可读取的最大长度 len len (fifo-in - fifo-out) ? len : (fifo-in - fifo-out); // 计算从当前位置到缓冲区末尾的长度 l len (fifo-size - (fifo-out fifo-mask)) ? len : (fifo-size - (fifo-out fifo-mask)); // 拷贝第一部分数据 memcpy(data, fifo-buffer (fifo-out fifo-mask), l); // 拷贝第二部分数据如果需要回绕 memcpy(data l, fifo-buffer, len - l); // 读内存屏障确保数据全部读取后再更新索引 smp_rmb(); // 更新读取索引 fifo-out len; return len; } // 使用示例 int main(void) { // 定义一个大小为128字节的静态缓冲区 static uint8_t buffer[128]; static kfifo_t fifo; // 初始化 kfifo_init(fifo, buffer, sizeof(buffer)); // 生产者线程/中断中写入数据 uint8_t tx_data[] Hello, kfifo!; kfifo_put(fifo, tx_data, sizeof(tx_data)); // 消费者线程中读取数据 uint8_t rx_data[128]; uint32_t len kfifo_get(fifo, rx_data, sizeof(rx_data)); return0; }最后总结下使用注意事项1、缓冲区大小必须是2的幂次8, 16, 32, 64, 128...2、严格遵守单生产者单消费者模型3、内存屏障一定要正确实现否则会出现难以调试的幽灵数据问题4、在多核系统中需要使用硬件内存屏障而不仅仅是编译器屏障5、多生产者多消费者场景怎么办可以给kfifo加一把自旋锁变成轻量级加锁队列;或者使用多个kfifo每个生产者对应一个队列。最后分享一段话:最好的代码不是最复杂的代码而是用最简单的方法解决最复杂的问题。最后好了今天就跟大家分享这么多了如果你觉得有所收获一定记得点个赞~bug菌唯一、永久、免费分享嵌入式技术知识平台~推荐专辑 点击蓝色字体即可跳转☞MCU进阶专辑☞嵌入式C语言进阶专辑☞“bug说”专辑☞专辑|Linux应用程序编程大全☞专辑|学点网络知识☞专辑|手撕C语言☞专辑|手撕C语言☞专辑|经验分享☞专辑|电能控制技术☞专辑 | 从单片机到Linux