[TOC]

lib/kfifo.c 内核FIFO实现(Kernel FIFO Implementation) 高效的无锁字节流缓冲区

历史与背景

这项技术是为了解决什么特定问题而诞生的？

lib/kfifo.c 中的kfifo（Kernel First-In-First-Out）是为了在Linux内核中提供一个通用、高效、线程安全的先进先出字节流缓冲区（FIFO）而诞生的。在它出现之前，许多内核子系统和驱动程序都需要在生产者（写入数据方）和消费者（读取数据方）之间传递数据，并且它们都各自实现了自己的环形缓冲区（Ring Buffer）逻辑。

这导致了几个突出问题：

  • 代码重复：大量驱动中存在功能相似但实现各异的环形缓冲区代码，造成了代码冗余和维护困难。
  • 容易出错：环形缓冲区的边界条件处理，特别是索引的回绕（wrap-around）逻辑，是常见的bug来源。手写实现很容易在多线程并发场景下出现问题。
  • 缺乏标准化：没有一个标准的接口，使得代码的可读性和可重用性都很差。
  • 性能不佳：一些简单的实现可能使用了不必要的锁，或者没有充分利用CPU架构的特性来优化性能。

kfifo的诞生就是为了用一个经过充分测试、高度优化和标准化的实现来取代所有这些分散的、临时的解决方案。

它的发展经历了哪些重要的里程碑或版本迭代？

kfifo由Stefani Dogcu在2004年左右引入内核，其设计从一开始就非常精巧，后续的发展主要集中在API的完善和优化上：

  • 初始设计：kfifo的核心设计从一开始就奠定了其高效的基础：
    • 大小必须是2的幂：这是kfifo最重要的设计约束。它允许使用按位与操作（index & (size - 1)）来代替昂贵的模运算（index % size）来实现索引的回绕，极大地提高了性能。
    • 索引永不回绕：读写索引（in 和 out）被定义为无限增长的无符号整数。这巧妙地避免了在多线程场景下因读写指针同时回绕到0而产生的混淆（空还是满？），是实现无锁操作的关键。
  • API的演进：
    • 最初的API比较基础，主要有kfifo_put()和kfifo_get()。
    • 后来增加了kfifo_in()和kfifo_out()等函数，它们允许生产者/消费者直接在kfifo的内存空间上进行操作，避免了一次不必要的数据拷贝（即从用户提供的缓冲区拷贝到kfifo）。
    • 引入了动态分配kfifo的函数（kfifo_alloc）和静态定义的宏（DEFINE_KFIFO），使其使用更加灵活。
    • 为了支持需要传递离散记录（records）而非字节流的场景，内核还引入了kfifo_rec变体。

目前该技术的社区活跃度和主流应用情况如何？

kfifo是Linux内核中一个非常基础、稳定且被极其广泛使用的组件。它已经成为在内核中实现生产者-消费者数据传递的标准工具。其应用遍布内核的各个角落：

  • 字符设备驱动：TTY（终端）和串口驱动使用kfifo来缓冲用户输入和程序输出。
  • USB驱动：用于缓冲USB设备发来的数据。
  • 网络驱动：在某些场景下用于缓冲数据包。
  • 工业I/O（IIO）子系统：用于缓冲来自传感器的数据。

核心原理与设计

它的核心工作原理是什么？

kfifo是一个经过精心设计的环形缓冲区，其高效和线程安全的特性主要源于以下几个核心设计点：

  1. 2的幂大小：如上所述，强制kfifo的大小必须是2的幂。这使得索引的回绕操作可以通过位运算index & (size - 1)来完成，效率极高。
  2. 无限增长的索引：in（写入）和out（读出）索引被定义为无符号整数（unsigned int），它们只会单调递增，永远不会被显式地重置为0。当索引的值超过其最大表示范围时，它会自动利用无符号整数的溢出特性从0开始继续增长。
  3. 计算已用/可用空间：kfifo中已存储的数据量总是等于 in - out。可用的空闲空间总是 size - (in - out)。由于索引是无限增长的，这个简单的减法就避免了传统环形缓冲区中需要比较in和out指针大小来判断缓冲区是空是满的复杂逻辑。
  4. 内存屏障（Memory Barriers）：这是实现**单生产者/单消费者（SPSC）**场景下无锁操作的关键。
    • 在kfifo_put()（生产者）中，首先将数据拷贝到缓冲区，然后才更新in索引。这两步操作之间需要一个写内存屏障（smp_wmb()）。这确保了对数据的写入操作一定先于in索引的更新对其他CPU可见。
    • 在kfifo_get()（消费者）中，首先读取in索引的值，然后才从缓冲区拷贝数据，最后更新out索引。在读取in索引和拷贝数据之间需要一个读内存屏障（smp_rmb()）。这确保了消费者能看到生产者更新后的in索引，然后才去读取相应的数据。
    • 正是这种精巧的屏障使用和操作顺序，保证了在SPSC场景下，生产者和消费者可以安全地并发访问kfifo而无需任何锁。

它的主要优势体现在哪些方面？

  • 极高的性能：基于2的幂大小和位运算，以及在SPSC场景下的无锁设计，使其数据传输的开销极小。
  • 线程安全：为最常见的SPSC场景提供了开箱即用的无锁安全保证。对于多生产者或多消费者（MPMC）的场景，kfifo也明确要求用户必须在外部使用锁（如自旋锁）来保护访问，提供了清晰的安全模型。
  • 代码简洁：将复杂的环形缓冲区逻辑封装成简单易用的API，极大地简化了驱动程序的开发。
  • 健壮性：作为一个通用的内核组件，它经过了社区的广泛使用和严格测试，非常可靠。

它存在哪些已知的劣势、局限性或在特定场景下的不适用性？

  • 大小限制：大小必须是2的幂，这可能会导致一些内存的浪费。例如，如果你需要一个33KB的缓冲区，你必须分配一个64KB的kfifo。
  • 字节流导向：标准的kfifo是为字节流设计的。它不保留消息边界。如果生产者写入了两次数据，消费者一次性读取可能会将两次写入的数据合并在一起。对于需要保持消息边界的场景，需要使用kfifo_rec或在应用层自己处理分包。
  • 无锁限制：其无锁特性仅适用于单生产者、单消费者的场景。只要存在多个生产者或多个消费者，就必须由调用者负责加锁。

使用场景

在哪些具体的业务或技术场景下，它是首选解决方案？请举例说明。

在内核中，任何需要在两个执行单元（如中断上下文和进程上下文，或者两个内核线程）之间传递字节流数据的生产者-消费者模型中，kfifo都是首选。

  • 例一：串口驱动
    当串口硬件收到数据时，会触发一个中断。串口驱动的中断处理函数（生产者）需要快速地将收到的字节存放到一个缓冲区中，然后退出中断。内核中的一个内核线程（消费者）会从这个缓冲区中读取数据，并将其传递给上层的TTY子系统。这个“中断上下文生产，线程上下文消费”的场景是典型的SPSC模型，使用kfifo可以实现无锁、高效的数据缓冲。
  • 例二：用户空间I/O缓冲
    一个字符设备驱动在处理用户空间的write()系统调用时，可以将用户传入的数据放入一个kfifo（生产者是进程上下文）。设备的硬件发送逻辑（可能是由一个工作队列或内核线程驱动）则从kfifo中取出数据并发送（消费者是另一个内核上下文）。

是否有不推荐使用该技术的场景？为什么？

  • 需要保持消息边界：如果生产者写入的是一个个独立的数据包，且消费者需要以同样的数据包单位来读取，那么标准的kfifo不适用，因为它会合并字节。此时应考虑使用kfifo_rec或专门的消息队列。
  • 数据量巨大且非2的幂：如果需要一个非常大的缓冲区（如几MB），且大小需求恰好不是2的幂（如3MB），那么使用kfifo导致的内存浪费可能会比较显著。在这种情况下，可能需要评估是否值得为了性能而接受这种空间开销。
  • 需要复杂队列操作：如果需要的不仅仅是FIFO，还需要如优先级、乱序处理等复杂队列功能，那么kfifo不适用。应选择更高级的队列数据结构。

对比分析

请将其 与 其他相似技术 进行详细对比。

特性 kfifo 手动实现的环形缓冲区 链表 (Linked List)
核心功能 高效、线程安全的字节流FIFO 字节流FIFO 离散对象（节点）的序列
实现方式 连续的内存块，2的幂大小，无限增长的无符号索引 连续的内存块，手动处理索引回绕 离散的内存节点，通过指针连接
性能 非常高。无锁(SPSC)，位运算代替模运算。 可变。性能取决于实现质量，通常不如kfifo优化。 较低。每个节点都需要单独的内存分配/释放，缓存局部性差。
内存占用 固定。一次性分配连续内存。大小为2的幂可能导致浪费。 固定。一次性分配连续内存。 动态。根据元素数量变化，但每个节点有额外的指针开销。
线程安全 内置SPSC无锁。MPMC需外部加锁。 需手动实现。非常容易出错。 需手动加锁。
数据模型 字节流。不保留消息边界。 字节流。 离散记录。每个节点是一个独立的消息。
典型用途 内核驱动中的生产者-消费者数据缓冲（串口，USB）。 （应被kfifo取代） 管理离散的对象列表，如任务队列、设备列表。

include/linux/kfifo.h

KFIFO: 内核高性能无锁循环缓冲区

此代码片段来自Linux内核的<linux/kfifo.h>头文件, 它定义了**KFIFO (内核FIFO)**的数据结构和初始化宏。KFIFO是一个高度优化的、通用的、固定大小的循环缓冲区(circular buffer)实现。

它的核心原理有两个:

  1. 强制容量为2的幂: KFIFO要求其容量必须是2的幂(2, 4, 8, 16, …)。这个看似严格的限制是为了一个巨大的性能优势: 它可以使用**位掩码(bitmask)来代替昂贵的模运算(modulo)**来实现索引的回绕(wrap-around)。例如, 对于一个大小为16的缓冲区, 其掩码为15(二进制1111)。当索引增加到16时, 16 & 15的结果是0, 实现了从末尾到开头的回绕, 这比16 % 16的计算速度快得多。
  2. 生产者/消费者模型解耦: KFIFO的设计旨在安全高效地在两个不同的执行上下文之间传递数据, 最经典的场景就是中断处理程序(生产者)和进程上下文(消费者)。通过精心设计的内存屏障和原子操作(在kfifo_in/kfifo_out函数中实现), KFIFO可以在单生产者/单消费者的场景下实现**无锁(lock-free)**操作, 极大地降低了系统开销和中断延迟。

此代码片段本身专注于KFIFO的数据结构定义和静态初始化。它通过一系列复杂的C预处理器宏, 提供了两种主要的FIFO声明方式:

  • DECLARE_KFIFO: 用于在编译时声明一个缓冲区内嵌的FIFO。FIFO的管理结构和其实际的数据存储区是一块连续的内存。这适用于大小在编译时就已确定的场景。
  • DECLARE_KFIFO_PTR: 用于声明一个缓冲区外置的FIFO。FIFO的管理结构本身不包含数据存储区, 数据区需要稍后通过kfifo_alloc或kfifo_init动态分配并关联。这适用于大小在运行时才能确定的场景。

在STM32H750这样的单核系统中, KFIFO的价值依然巨大:

  • 性能: 位掩码操作带来的效率提升对于资源受限的MCU至关重要。
  • 中断处理: 它是处理异步数据流的理想工具。例如, UART或SPI的接收中断可以将收到的数据快速推入一个KFIFO, 而主循环或一个低优先级任务可以安全地从这个KFIFO中取出数据进行处理。这避免了在中断上下文中进行耗时操作, 保证了系统的实时响应能力。
  • 并发安全: 即使在单核系统上, 如果内核是抢占式的, 一个任务也可能在操作KFIFO的中间被抢占。KFIFO内部的实现(虽然在此代码片段中未完全展示)确保了这种并发访问的安全性。

宏和结构体详解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
/* 前向声明一个分散-聚集列表结构体, 此处未使用但kfifo可能与其他内核API交互. */
struct scatterlist;

/*
 * __kfifo: KFIFO最核心的、与类型无关的管理结构体.
 * 它包含了操作一个循环缓冲区所需的所有元数据.
 */
struct __kfifo {
	unsigned int	in;      /* "放入"索引: 下一个数据要写入的位置. */
	unsigned int	out;     /* "取出"索引: 下一个数据要读取的位置. */
	unsigned int	mask;    /* 容量掩码: 值等于 (容量 - 1). 用于通过位与(&)操作实现索引回绕. */
	unsigned int	esize;   /* 元素大小: FIFO中单个元素占用的字节数. */
	void		*data;   /* 数据指针: 指向实际存储数据的缓冲区的起始地址. */
};

/*
 * __STRUCT_KFIFO_COMMON: 一个通用的宏, 定义了所有KFIFO结构体都包含的联合(union).
 * union允许多个成员共享同一块内存. 这是一种C语言的技巧, 用于实现类型安全和方便的访问.
 */
#define __STRUCT_KFIFO_COMMON(datatype, recsize, ptrtype) \
	union { \
		struct __kfifo	kfifo;      /* 可以将这块内存解释为核心管理结构. */ \
		datatype	*type;      /* 可以将其解释为指向"元素类型"的指针, 用于编译时类型检查. */ \
		const datatype	*const_type;/* ...const版本. */ \
		char		(*rectype)[recsize]; /* 可以将其解释为指向"记录类型"的数组的指针, 用于面向记录的FIFO. */ \
		ptrtype		*ptr;       /* 可以将其解释为指向"通用指针类型"的指针. */ \
		ptrtype const	*ptr_const; \
	}

/*
 * __STRUCT_KFIFO: 定义一个"缓冲区内嵌"的KFIFO结构体.
 * @type: FIFO中存储的数据的类型.
 * @size: FIFO的容量, 必须是2的幂.
 * @recsize: (用于面向记录的FIFO)记录的大小.
 * @ptrtype: (用于面向记录的FIFO)通用指针类型.
 */
#define __STRUCT_KFIFO(type, size, recsize, ptrtype) \
{ \
	__STRUCT_KFIFO_COMMON(type, recsize, ptrtype); \
	/*
	 * buf[...]: 这就是内嵌的数据缓冲区.
	 * ((size < 2) || (size & (size - 1))) ? -1 : size : 这是一个编译时断言.
	 * (size & (size - 1)) 是一个判断size是否为2的幂的技巧. 如果不是, 结果不为0.
	 * 如果size小于2或不是2的幂, 整个表达式会变成 buf[-1], 这是一个无效的数组大小, 会导致编译错误.
	 * 这就强制了使用者必须提供一个有效的、2的幂的容量.
	 */ \
	type		buf[((size < 2) || (size & (size - 1))) ? -1 : size]; \
}

/* STRUCT_KFIFO: __STRUCT_KFIFO的一个简化版宏, 用于声明一个标准的、面向元素类型的内嵌式FIFO. */
#define STRUCT_KFIFO(type, size) \
	struct __STRUCT_KFIFO(type, size, 0, type)

/*
 * __STRUCT_KFIFO_PTR: 定义一个"缓冲区外置"的KFIFO结构体.
 * 注意buf的大小为0. 这是一个C语言的"柔性数组成员"或"零长度数组"技巧.
 * 它表示数据缓冲区不在这里, 需要在别处动态分配.
 */
#define __STRUCT_KFIFO_PTR(type, recsize, ptrtype) \
{ \
	__STRUCT_KFIFO_COMMON(type, recsize, ptrtype); \
	type		buf[0]; \
}

/* STRUCT_KFIFO_PTR: __STRUCT_KFIFO_PTR的一个简化版宏. */
#define STRUCT_KFIFO_PTR(type) \
	struct __STRUCT_KFIFO_PTR(type, 0, type)

/* 为了兼容旧代码, 定义了一个名为 struct kfifo 的标准动态FIFO类型. */
struct kfifo __STRUCT_KFIFO_PTR(unsigned char, 0, void);

/* -- 面向记录的FIFO的特殊类型定义, 此处不深入 -- */
#define STRUCT_KFIFO_REC_1(size) \
	struct __STRUCT_KFIFO(unsigned char, size, 1, void)
#define STRUCT_KFIFO_REC_2(size) \
	struct __STRUCT_KFIFO(unsigned char, size, 2, void)
struct kfifo_rec_ptr_1 __STRUCT_KFIFO_PTR(unsigned char, 1, void);
struct kfifo_rec_ptr_2 __STRUCT_KFIFO_PTR(unsigned char, 2, void);

/*
 * __is_kfifo_ptr: 一个辅助宏, 用于在编译时判断一个KFIFO是内嵌式还是指针式.
 * 它比较fifo结构体的大小和标准的指针式KFIFO结构体的大小. 如果相等, 说明它是指针式的.
 */
#define	__is_kfifo_ptr(fifo) \
	(sizeof(*fifo) == sizeof(STRUCT_KFIFO_PTR(typeof(*(fifo)->type))))

/**
 * DECLARE_KFIFO_PTR: 用户接口宏, 用于声明一个指针式的KFIFO变量.
 * @fifo: 变量名.
 * @type: 元素类型.
 */
#define DECLARE_KFIFO_PTR(fifo, type)	STRUCT_KFIFO_PTR(type) fifo

/**
 * DECLARE_KFIFO: 用户接口宏, 用于声明一个内嵌式的KFIFO变量.
 * @fifo: 变量名.
 * @type: 元素类型.
 * @size: 容量, 必须是2的幂.
 */
#define DECLARE_KFIFO(fifo, type, size)	STRUCT_KFIFO(type, size) fifo

/**
 * INIT_KFIFO: 用户接口宏, 用于初始化一个由DECLARE_KFIFO声明的FIFO.
 * @fifo: 目标FIFO变量名.
 */
#define INIT_KFIFO(fifo) \
(void)({ \
	/* ({...}) 是一个GCC扩展, 称为"语句表达式", 允许多行代码的宏表现得像一个单一表达式. */ \
	/* typeof(&(fifo)) __tmp = &(fifo); 获取一个指向用户fifo结构体的、类型正确的临时指针. */ \
	typeof(&(fifo)) __tmp = &(fifo); \
	/* struct __kfifo *__kfifo = &__tmp->kfifo; 从联合体中获取核心管理结构的指针. */ \
	struct __kfifo *__kfifo = &__tmp->kfifo; \
	/* 初始化输入和输出索引为0. */ \
	__kfifo->in = 0; \
	__kfifo->out = 0; \
	/*
	 * 初始化掩码:
	 * 如果是外置式FIFO, 此处mask为0, 因为容量未知.
	 * 如果是内嵌式FIFO, mask = 容量 - 1. ARRAY_SIZE(__tmp->buf)获取内嵌数组的大小.
	 */ \
	__kfifo->mask = __is_kfifo_ptr(__tmp) ? 0 : ARRAY_SIZE(__tmp->buf) - 1;\
	/* 初始化元素大小. */ \
	__kfifo->esize = sizeof(*__tmp->buf); \
	/*
	 * 初始化数据指针:
	 * 如果是外置式FIFO, data指针为NULL, 等待后续kfifo_init/alloc.
	 * 如果是内嵌式FIFO, data指针指向自己的buf成员.
	 */ \
	__kfifo->data = __is_kfifo_ptr(__tmp) ?  NULL : __tmp->buf; \
})

KFIFO 状态检查宏

此代码片段继续展示了Linux内核 KFIFO (内核FIFO) 的接口, 这次是一组用于检查KFIFO状态 (是否为空或已满) 的宏。这些宏是KFIFO生产者/消费者模型中进行流量控制和状态判断的基础。它们被设计得既高效又安全, 提供了不同级别的并发保护。

其核心原理非常直观:

  • 空 (Empty): 当”放入”索引(in)与”取出”索引(out)相等时, 缓冲区为空。
  • 满 (Full): 当缓冲区中已存储的元素数量等于其总容量时, 缓冲区为满。

然而, 这些宏的实现细节体现了内核编程的高度技巧性, 特别是在类型安全和并发控制方面。

  • + 1 的目的不是为了计算地址, 而是一个编译时(compile-time)的 “诡计”, 用来强制进行类型检查, 确保传入宏的 fifo 是一个指向完整结构体(complete type)的指针, 而不是一个 void * 或者指向一个不完整类型(incomplete type)的指针。

kfifo_is_empty

这是最基础的、非线程安全的空状态检查宏。

原理与工作流程:
它直接比较in和out索引。如果相等, 则FIFO为空。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
 * kfifo_is_empty - 如果fifo为空则返回true
 * @fifo: 要使用的fifo的地址
 */
#define	kfifo_is_empty(fifo) \
({ \
	/*
	 * ({...}) 是一个GCC的"语句表达式"扩展. 它允许多行代码的宏表现得像一个单一表达式,
	 * 并且可以安全地返回值, 避免了传统宏的许多副作用.
	 */ \
	/*
	 * typeof((fifo) + 1) __tmpq = (fifo);
	 * 这是一个类型安全的宏技巧. `typeof`获取fifo指针的正确类型,
	 * 并创建一个临时指针变量`__tmpq`. 这可以防止在宏内部多次对`fifo`求值,
	 * 避免了当传入`fifo++`这类表达式时产生的意外行为.
	 */ \
	typeof((fifo) + 1) __tmpq = (fifo); \
	/*
	 * 核心逻辑: 直接比较in和out索引.
	 * 比较的结果(true或false)是这个语句表达式的最终值, 也就是宏的返回值.
	 */ \
	__tmpq->kfifo.in == __tmpq->kfifo.out; \
})

适用场景: 只能在可以确定没有其他执行绪(无论是任务还是中断)会同时修改FIFO的上下文中使用, 或者由调用者自己提供外部锁定。

kfifo_is_empty_spinlocked 和 kfifo_is_empty_spinlocked_noirqsave

这两个宏提供了线程安全的空状态检查。它们是实际并发编程中必须使用的版本。

原理与工作流程:
它们都通过在执行kfifo_is_empty检查前后获取和释放一个自旋锁(spinlock)来保证操作的原子性。

kfifo_is_empty_spinlocked:
这是最常用、最安全的版本, 特别是用于中断上下文与进程上下文之间的同步。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
 * kfifo_is_empty_spinlocked - 使用自旋锁, 返回fifo是否为空
 * @fifo: 要使用的fifo的地址
 * @lock: 用于锁定的自旋锁
 */
#define kfifo_is_empty_spinlocked(fifo, lock) \
({ \
	unsigned long __flags; \
	bool __ret; \
	/*
	 * spin_lock_irqsave: 1. 保存当前的中断状态到__flags. 2. 禁用本地中断. 3. 获取自旋锁.
	 * 这可以防止来自其他任务的抢占, 以及来自本地中断处理程序的并发访问.
	 */ \
	spin_lock_irqsave(lock, __flags); \
	/* 在持有锁的情况下, 调用非安全的版本进行检查. */ \
	__ret = kfifo_is_empty(fifo); \
	/*
	 * spin_unlock_irqrestore: 1. 释放自旋锁. 2. 恢复之前保存的中断状态.
	 */ \
	spin_unlock_irqrestore(lock, __flags); \
	/* 返回检查结果. */ \
	__ret; \
})

适用场景: 在STM32H750这类系统中, 当一个中断处理程序作为生产者向FIFO写入数据, 而一个内核任务(进程上下文)作为消费者读取数据时, 消费者在检查FIFO是否为空时必须使用这个宏。

kfifo_is_empty_spinlocked_noirqsave:
这是一个轻量级的版本, 它不处理中断状态。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
 * kfifo_is_empty_spinlocked_noirqsave  - 使用自旋锁返回fifo是否为空,
 * 不禁用中断.
 * @fifo: 要使用的fifo的地址
 * @lock: 用于锁定的自旋锁
 */
#define kfifo_is_empty_spinlocked_noirqsave(fifo, lock) \
({ \
	bool __ret; \
	/*
	 * spin_lock: 只获取自旋锁, 在单核系统上, 这主要起到禁用内核抢占的作用.
	 * 它不会禁用硬件中断.
	 */ \
	spin_lock(lock); \
	__ret = kfifo_is_empty(fifo); \
	/* spin_unlock: 只释放自旋锁, 重新启用内核抢占. */ \
	spin_unlock(lock); \
	__ret; \
})

适用场景: 用于两个内核任务之间的同步, 或者可以确定与FIFO交互的代码路径都不会在中断上下文中执行的场景。在单核系统上, 这足以防止任务间的并发冲突。我们之前分析的lineinfo_watch_poll函数就使用了这个版本, 因为它是在进程上下文中被调用, 而其生产者(中断处理程序)在推入数据后会使用spin_lock_irqsave版本的锁, 这种”非对称”的锁使用是正确且高效的。

kfifo_is_full

这是最基础的、非线程安全的满状态检查宏。

原理与工作流程:
它通过kfifo_len()宏(此处未显示, 但其作用是计算in - out)来获取当前FIFO中的元素数量, 然后将该数量与FIFO的容量(mask + 1)进行比较。为了效率, 它直接与mask比较。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/**
 * kfifo_is_full - 如果fifo已满则返回true
 * @fifo: 要使用的fifo的地址
 */
#define	kfifo_is_full(fifo) \
({ \
	/* 同样使用类型安全的临时变量技巧. */ \
	typeof((fifo) + 1) __tmpq = (fifo); \
	/*
	 * kfifo_len(__tmpq) 计算出当前FIFO中的元素数量 (in - out).
	 * __tmpq->kfifo.mask 是 (容量 - 1).
	 * 当FIFO满时, len == mask + 1, 所以 len > mask.
	 * 这个比较避免了计算 "mask + 1".
	 */ \
	kfifo_len(__tmpq) > __tmpq->kfifo.mask; \
})

适用场景: 由生产者在尝试向FIFO写入数据之前调用, 以防止数据溢出和丢失。同样, 这个基础版本需要调用者自己处理锁定。

kfifo_out: 从KFIFO中获取数据

此宏是Linux内核 KFIFO (内核FIFO) 接口中负责从缓冲区取出数据的核心消费者API。它的根本原理是以一种高效且在特定条件下无需外部加锁的方式, 从循环缓冲区中复制出指定数量的元素。

这个宏的设计集成了多项内核编程的最佳实践, 以实现高性能、类型安全和并发安全。

核心工作原理 (内部函数 __kfifo_out 所做的事情):

  1. 计算可用长度: 它首先读取in和out索引, 计算出当前FIFO中可用元素的数量 (len = in - out)。
  2. 确定复制数量: 它取用户请求的数量n和FIFO中实际可用的数量len之间的最小值, 作为本次要复制的元素数量。
  3. 分段复制: 由于数据在循环缓冲区中可能被分割在两段 (一部分在数组末尾, 一部分在数组开头), __kfifo_out会智能地处理这种情况。它可能会执行一次或两次memcpy操作, 将数据从FIFO的内部data缓冲区复制到用户提供的buf中。
  4. 更新out索引: 在所有数据被安全地复制出去之后, 它会原子地更新out索引, 将其增加实际复制出去的元素数量。这个操作顺序是至关重要的。
  5. 无锁(Lock-Free)操作: 在单生产者/单消费者的场景下, kfifo_out是无锁的。这是因为:
    • 只有消费者(调用kfifo_out的代码)会修改out索引。
    • 只有生产者(调用kfifo_in的代码)会修改in索引。
    • __kfifo_out内部使用了内存屏障(memory barrier, 如smp_rmb()), 确保对in索引的读取发生在我们开始复制数据之前, 并且对out索引的更新发生在我们完成复制之后。这可以防止编译器或CPU对操作进行不安全的乱序优化, 保证了生产者和消费者之间看到的数据状态是一致的。

宏定义详解

kfifo_out本身是一个复杂的宏, 它封装了所有必要的类型检查和逻辑分派。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
/**
 * kfifo_out - 从fifo中获取数据
 * @fifo: 要使用的fifo的地址
 * @buf: 指向存储数据的缓冲区的指针
 * @n: 最多要获取的元素的数量
 *
 * 此宏从fifo中获取一些数据, 并返回被复制的元素的数量.
 *
 * 注意: 在只有一个并发读取者和一个并发写入者的情况下,
 * 使用此宏不需要额外的加锁.
 */
#define	kfifo_out(fifo, buf, n) \
/*
 * 步骤4: 将整个宏的返回值包裹在一个带有 __must_check 属性的辅助函数中.
 * 这会强制调用kfifo_out的代码必须检查其返回值(即实际取出的元素数量), 否则编译器会发出警告.
 * 这是一个增强代码健壮性的重要措施.
 */ \
__kfifo_uint_must_check_helper( \
({ \
	/* 步骤1: 使用标准的类型安全技巧创建临时变量. */ \
	typeof((fifo) + 1) __tmp = (fifo); \
	/* 为目标缓冲区buf也创建一个类型正确的临时指针, 确保其类型与FIFO元素类型兼容. */ \
	typeof(__tmp->ptr) __buf = (buf); \
	unsigned long __n = (n); \
	/*
	 * 步骤2: 检查是否为"面向记录"的FIFO.
	 * sizeof(*__tmp->rectype) 会得到记录的大小(如果不是记录式FIFO, 则为0).
	 */ \
	const size_t __recsize = sizeof(*__tmp->rectype); \
	/* 获取指向核心管理结构的指针. */ \
	struct __kfifo *__kfifo = &__tmp->kfifo; \
	/*
	 * 步骤3: 逻辑分派.
	 * 使用三元运算符, 根据 __recsize 是否为0, 来决定调用哪个底层工作函数.
	 */ \
	(__recsize) ?\
	__kfifo_out_r(__kfifo, __buf, __n, __recsize) : /* 如果是记录式, 调用__kfifo_out_r */ \
	__kfifo_out(__kfifo, __buf, __n);               /* 否则, 调用标准的__kfifo_out */ \
}) \
)

/*
 * 这是一个非常简单的内联函数, 它的唯一目的就是带上 __must_check 属性.
 * 它直接返回传入的值.
 */
static inline unsigned int __must_check
__kfifo_uint_must_check_helper(unsigned int val)
{
	return val;
}

lib/kfifo.c

KFIFO 面向记录的数据出队核心实现

此代码片段展示了Linux内核 KFIFO (内核FIFO) 中用于面向记录(record-based)的数据出队(dequeue)操作的底层核心实现。与简单的、逐元素(element)的FIFO不同, 面向记录的FIFO用于处理可变长度的数据包或消息。它的核心原理是: 在存入每条可变长度的数据记录之前, 先存入一个固定大小的头部, 这个头部记录了紧随其后的数据记录的长度。

这组函数协同工作, 实现了一个安全、分层的记录出队过程:

  1. __kfifo_out_r (API层): 这是外部调用的顶层函数。它负责完成一次完整的”记录出队”事务: 检查非空, 调用下一层来复制数据, 最后更新out指针以宣告记录已被消耗。
  2. kfifo_out_copy_r (逻辑层/ framing层): 它负责处理”记录”的逻辑。它首先”窥探”(peek)记录的头部以获取其长度, 然后调用物理层来复制记录的数据体, 但它不会更新out指针。
  3. kfifo_copy_out (物理层/ copy层): 这是最底层的内存复制引擎。它不关心”记录”的概念, 只负责高效、安全地将指定长度的字节从循环缓冲区中复制出来, 并正确处理地址回绕(wrap-around)的情况。

kfifo_copy_out: 从循环缓冲区中复制数据

这是最底层的物理复制函数。

原理与工作流程:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
/*
 * kfifo_copy_out: 从fifo内部缓冲区复制数据到外部.
 * @fifo: 指向核心 __kfifo 管理结构的指针.
 * @dst: 目标缓冲区的地址.
 * @len: 要复制的元素的数量.
 * @off: 起始复制点, 以元素为单位的逻辑偏移量.
 */
static void kfifo_copy_out(struct __kfifo *fifo, void *dst,
		unsigned int len, unsigned int off)
{
	unsigned int size = fifo->mask + 1; // FIFO的总容量 (元素数)
	unsigned int esize = fifo->esize;   // 每个元素的大小 (字节)
	unsigned int l;

	/* 使用位掩码将逻辑偏移量转换为缓冲区内的实际偏移量, 处理回绕. */
	off &= fifo->mask;
	/* 如果元素大小不是1字节, 将所有单位从"元素"转换为"字节". */
	if (esize != 1) {
		off *= esize;
		size *= esize;
		len *= esize;
	}
	/*
	 * 计算第一段要复制的长度.
	 * l = min(要复制的总长度, 从当前偏移量到物理缓冲区末尾的长度)
	 */
	l = min(len, size - off);

	/* 复制第一段 (从off到缓冲区末尾). */
	memcpy(dst, fifo->data + off, l);
	/*
	 * 复制第二段 (从缓冲区开头到剩余部分).
	 * 如果数据没有回绕 (len <= l), 那么 len - l 等于 0, 第二个memcpy不会执行任何操作.
	 */
	memcpy(dst + l, fifo->data, len - l);
	/*
	 * 关键: 内存屏障.
	 * smp_wmb() (Write Memory Barrier) 确保在它之前的所有内存写入操作(即上面的memcpy),
	 * 必须在它之后的任何内存操作(特别是调用者对fifo->out索引的更新)对其他CPU可见之前完成.
	 * 这可以防止一种竞态条件: 消费者还没完成数据复制, 生产者就看到了更新后的out索引,
	 * 误认为空间已空闲并覆盖了正在被复制的数据.
	 * 在单核系统上, 它主要用来阻止编译器的乱序优化, 保证操作的逻辑顺序.
	 */
	smp_wmb();
}

kfifo_out_copy_r: “窥探”并复制一条记录的数据

这个函数负责读取记录的头部, 并据此复制记录的数据体。

原理与工作流程:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/*
 * kfifo_out_copy_r: 窥探下一条记录的长度, 并复制其数据.
 * @fifo: 指向核心 __kfifo 管理结构的指针.
 * @buf: 目标缓冲区.
 * @len: 目标缓冲区的最大容量.
 * @recsize: 记录头部的长度 (1或2字节).
 * @n: [输出参数] 用于返回实际记录数据的长度.
 * @return: 实际复制到buf中的字节数.
 */
static unsigned int kfifo_out_copy_r(struct __kfifo *fifo,
	void *buf, unsigned int len, size_t recsize, unsigned int *n)
{
	/* 调用一个内部函数(此处未显示)来窥探FIFO, 读取记录头, 获取记录数据的长度. */
	*n = __kfifo_peek_n(fifo, recsize);

	/* 如果用户的缓冲区大小len小于记录的实际长度*n, 则只复制len个字节. */
	if (len > *n)
		len = *n;

	/*
	 * 调用物理复制函数.
	 * 复制的起始点是 fifo->out + recsize, 即跳过记录头, 从实际数据开始复制.
	 */
	kfifo_copy_out(fifo, buf, len, fifo->out + recsize);
	/* 返回实际复制的字节数. */
	return len;
}

__kfifo_out_r: 完成一次面向记录的出队操作

这是导出的API函数, 它将上述两个函数的功能组合起来, 完成一次完整的记录出队。

原理与工作流程:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/*
 * __kfifo_out_r: 从面向记录的fifo中获取一条记录.
 * @return: 复制到buf中的数据字节数.
 */
unsigned int __kfifo_out_r(struct __kfifo *fifo, void *buf,
		unsigned int len, size_t recsize)
{
	unsigned int n;

	/* 如果FIFO为空, 直接返回0. */
	if (fifo->in == fifo->out)
		return 0;

	/*
	 * 步骤1: 调用逻辑层函数, 它会窥探记录长度, 并将数据复制到buf中.
	 * 执行后, len 变量包含了实际复制的字节数, n 变量包含了记录的完整数据长度.
	 */
	len = kfifo_out_copy_r(fifo, buf, len, recsize, &n);
	/*
	 * 步骤2: 更新 'out' 索引.
	 * 将 'out' 索引向前移动整个记录的长度, 包括记录数据(n)和记录头(recsize).
	 * 这个更新操作是在数据复制完成之后才执行的, 这是保证安全的关键.
	 */
	fifo->out += n + recsize;
	/* 返回实际复制到用户缓冲区的字节数. */
	return len;
}
EXPORT_SYMBOL(__kfifo_out_r);

__kfifo_out: 核心数据出队函数

这是标准的、用于**面向元素(element-based)**的FIFO的数据出队函数。它的作用是从FIFO中复制出指定数量的元素, 并更新FIFO的状态以表示这些元素已被消耗。

原理与工作流程:
它将”出队”这个动作优雅地分解为两个独立的步骤:

  1. 窥探与复制 (__kfifo_out_peek): 它首先调用__kfifo_out_peek。这个函数负责计算实际可复制的元素数量, 并执行从KFIFO内部缓冲区到用户目标缓冲区的内存复制(memcpy), 但它不会修改FIFO的任何状态指针。
  2. 消耗与更新 (fifo->out += len): 在数据被安全地复制出去之后, __kfifo_out才执行最关键的一步: 将out索引向前移动实际复制出去的元素数量(len)。这个更新操作宣告了缓冲区中的这部分空间现在可以被生产者重新使用。

这种两步分离的设计是KFIFO在单生产者/单消费者场景下实现无锁(lock-free)的关键。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/*
 * __kfifo_out: 从fifo中获取数据并更新索引.
 * @return: 实际获取的元素数量.
 */
unsigned int __kfifo_out(struct __kfifo *fifo,
		void *buf, unsigned int len)
{
	/* 步骤1: 调用peek函数, 它会计算可复制的数量, 并执行内存复制. */
	len = __kfifo_out_peek(fifo, buf, len);
	/*
	 * 步骤2: 更新out索引, 将其增加已复制的元素数量.
	 * 这个操作是在数据复制完成之后才执行的, 保证了操作的安全性.
	 */
	fifo->out += len;
	return len;
}
EXPORT_SYMBOL(__kfifo_out);

__kfifo_out_peek: 窥探并复制数据

此函数的作用是”窥探”FIFO中的数据——即复制数据, 但不更新out索引。这允许消费者在不消耗数据的情况下检查队列头部的内容。

原理与工作流程:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/*
 * __kfifo_out_peek: 从fifo中窥探数据 (复制但不消耗).
 * @return: 实际窥探并复制的元素数量.
 */
unsigned int __kfifo_out_peek(struct __kfifo *fifo,
		void *buf, unsigned int len)
{
	unsigned int l;

	/* 计算当前FIFO中的元素数量. */
	l = fifo->in - fifo->out;
	/* 取用户请求数量'len'和实际可用数量'l'中的较小者. */
	if (len > l)
		len = l;

	/* 调用底层复制引擎kfifo_copy_out(在之前的分析中), 执行内存复制. */
	kfifo_copy_out(fifo, buf, len, fifo->out);
	return len;
}
EXPORT_SYMBOL(__kfifo_out_peek);

__kfifo_peek_n: 窥探记录头以获取记录长度

这是一个内部辅助函数, 专门用于面向记录(record-based)的FIFO。它的唯一作用是窥探下一条记录的头部, 并解析出该记录的数据体长度。

原理与工作流程:
它从fifo->out的当前位置读取1个或2个字节, 并将它们组合成一个代表长度的整数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/* __KFIFO_PEEK: 一个安全的宏, 用于读取内部数据缓冲区中的一个元素. */
#define	__KFIFO_PEEK(data, out, mask) \
	((data)[(out) & (mask)])

/*
 * __kfifo_peek_n: 窥探下一条记录的长度.
 * @recsize: 记录头的大小 (1或2字节).
 * @return: 下一条记录的数据体长度.
 */
static unsigned int __kfifo_peek_n(struct __kfifo *fifo, size_t recsize)
{
	unsigned int l;
	unsigned int mask = fifo->mask;
	unsigned char *data = fifo->data;

	/* 读取长度的第一个字节. */
	l = __KFIFO_PEEK(data, fifo->out, mask);

	/* 如果记录头是2字节(recsize=2), 则读取第二个字节并组合成一个16位数. */
	if (--recsize)
		l |= __KFIFO_PEEK(data, fifo->out + 1, mask) << 8;

	return l;
}