Linux内核kfifo实现详解

Linux内核kfifo实现详解

Linux内核kfifo是一种高效的无锁环形缓冲区实现，其核心设计包括：1）使用2的幂次方大小缓冲区，通过位运算替代取模运算提高性能；2）分离的in/out索引设计，避免锁机制；3）内存屏障确保数据一致性。kfifo通过位运算优化索引计算（position & mask），并采用两段复制策略处理环形缓冲区的边界条件，在单生产者单消费者场景下实现高效无锁操作。

  1. kfifo设计原理

1.1 核心思想

Linux内核kfifo（kernel FIFO）是一个高效、无锁的环形缓冲区实现，专为内核环境设计。

1
2
3
4
5
6
7
8
9
10
11
12
/**
 * kfifo的核心数据结构
 * 为什么这样设计？
 */
struct __kfifo {
    unsigned int    in;     // 入队索引
    unsigned int    out;    // 出队索引  
    unsigned int    mask;   // 掩码，用于快速取模运算
    unsigned int    esize;  // 元素大小
    void        *data;      // 数据缓冲区指针
};

1.2 关键设计决策

1.2.1 2的幂次方大小

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 为什么要求缓冲区大小是2的幂次方？
// 因为可以使用位运算代替取模运算，提高性能

// 普通取模运算
index = position % size;  // 除法运算，较慢

// 2的幂次方优化
mask = size - 1;          // 例如：size=8, mask=7 (0111)
index = position & mask;  // 位运算，非常快

// 示例：
// position = 10, size = 8
// 普通方法：10 % 8 = 2
// 优化方法：10 & 7 = 0x0A & 0x07 = 0x02 = 2

1.2.2 索引分离设计

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// 为什么使用分离的in/out索引而不是head/tail？
// 这样可以避免复杂的边界检查和锁机制

struct __kfifo {
    unsigned int in;   // 累计入队元素数
    unsigned int out;  // 累计出队元素数
    // 实际索引通过 in & mask 和 out & mask 计算
};

// 当前缓冲区中元素数量
unsigned int len = fifo->in - fifo->out;

// 实际写入位置
unsigned int write_index = fifo->in & fifo->mask;

// 实际读取位置  
unsigned int read_index = fifo->out & fifo->mask;

  1. 内存布局优化

2.1 缓冲区大小计算

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
/**
 * 确保缓冲区大小是2的幂次方的算法
 */
static int __init kfifo_alloc_common(struct __kfifo *fifo, 
                                    unsigned int size,
                                    size_t esize,
                                    gfp_t gfp_mask)
{
    /*
     * Round up to the next power of 2, as vaddr_t is a power of 2,
     * and the FIFO size and cache line size are both powers of 2.
     */
    size = roundup_pow_of_two(size);
    
    fifo->in = 0;
    fifo->out = 0;
    fifo->esize = esize;
    
    if (size < 2) {
        fifo->data = NULL;
        fifo->mask = 0;
        return -EINVAL;
    }
    
    fifo->data = kmalloc(size * esize, gfp_mask);
    if (!fifo->data) {
        fifo->mask = 0;
        return -ENOMEM;
    }
    
    fifo->mask = size - 1;  // 关键：掩码用于快速取模
    
    return 0;
}

2.2 位运算优化详解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
 * 位运算优化示例
 */
// 传统方法：使用取模运算
int traditional_index(int position, int size) {
    return position % size;  // 涉及除法运算，较慢
}

// kfifo方法：使用位运算
int optimized_index(int position, int mask) {
    return position & mask;  // 位运算，非常快
}

// 示例对比：
// size = 8 (2^3), mask = 7 (0111)
// position = 0..15 的索引计算：
// 位置 0: 0 & 7 = 0    0 % 8 = 0
// 位置 1: 1 & 7 = 1    1 % 8 = 1  
// 位置 7: 7 & 7 = 7    7 % 8 = 7
// 位置 8: 8 & 7 = 0    8 % 8 = 0  (循环回到开始)
// 位置 9: 9 & 7 = 1    9 % 8 = 1  (循环)

  1. 无锁设计原理

3.1 单生产者单消费者无锁实现

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
/**
 * 无锁kfifo的核心：单生产者单消费者场景
 * 在这种场景下，in和out变量分别只被一个线程修改，无需锁保护
 */

// 生产者线程（只能修改in变量）
unsigned int kfifo_in(struct __kfifo *fifo,
                      const void *buf, unsigned int len)
{
    unsigned int l;
    
    // 计算可用空间
    len = min(len, fifo->mask + 1 - fifo->in + fifo->out);
    
    /* first put the data starting from fifo->in to buffer end */
    l = min(len, fifo->mask + 1 - (fifo->in & fifo->mask));
    memcpy(fifo->data + (fifo->in & fifo->mask) * fifo->esize, buf, l * fifo->esize);
    
    /* then put the rest (if any) at the beginning of the buffer */
    memcpy(fifo->data, (char *)buf + l * fifo->esize,
           (len - l) * fifo->esize);
    
    /*
     * Ensure that we add the bytes to the kfifo -before-
     * we update the fifo->in index.
     */
    smp_wmb();  // 内存屏障，确保数据写入完成
    
    fifo->in += len;  // 原子更新in索引
    
    return len;
}

// 消费者线程（只能修改out变量）  
unsigned int kfifo_out(struct __kfifo *fifo,
                       void *buf, unsigned int len)
{
    unsigned int l;
    
    // 计算可用数据
    len = min(len, fifo->in - fifo->out);
    
    /* first get the data from fifo->out until the end of the buffer */
    l = min(len, fifo->mask + 1 - (fifo->out & fifo->mask));
    memcpy(buf, fifo->data + (fifo->out & fifo->mask) * fifo->esize, l * fifo->esize);
    
    /* then get the rest (if any) from the beginning of the buffer */
    memcpy((char *)buf + l * fifo->esize, fifo->data,
           (len - l) * fifo->esize);
    
    /*
     * Ensure that we remove the bytes from the kfifo -before-
     * we update the fifo->out index.
     */
    smp_mb();  // 内存屏障
    
    fifo->out += len;  // 原子更新out索引
    
    return len;
}

3.2 内存屏障的作用

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/**
 * 内存屏障的重要性
 * 防止编译器和CPU重排序导致的数据不一致
 */

// 生产者端
smp_wmb();  // write memory barrier
// 确保数据写入缓冲区的操作在更新in索引之前完成
fifo->in += len;

// 消费者端  
smp_mb();   // memory barrier
// 确保读取数据的操作在更新out索引之前完成
fifo->out += len;

  1. 边界条件处理

4.1 环形缓冲区的两段复制

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
/**
 * 环形缓冲区的挑战：数据可能跨越缓冲区边界
 * 需要分两段复制
 */

// 示例：缓冲区大小为8，当前状态
// &#91;0]&#91;1]&#91;2]&#91;3]&#91;4]&#91;5]&#91;6]&#91;7]
//        ^out      ^in
// 数据在位置&#91;3]&#91;4]&#91;5]&#91;6]&#91;7]

// 当要写入大量数据时，可能需要分两段：
// 第一段：从in位置到缓冲区末尾
// 第二段：从缓冲区开始到剩余数据

unsigned int kfifo_in(struct __kfifo *fifo,
                      const void *buf, unsigned int len)
{
    unsigned int l;
    
    // 计算第一段可以写入的数据量
    l = min(len, fifo->mask + 1 - (fifo->in & fifo->mask));
    
    // 第一段复制：从当前in位置到缓冲区末尾
    memcpy(fifo->data + (fifo->in & fifo->mask) * fifo->esize, 
           buf, 
           l * fifo->esize);
    
    // 第二段复制：如果还有剩余数据，从缓冲区开始处继续
    memcpy(fifo->data,
           (char *)buf + l * fifo->esize,
           (len - l) * fifo->esize);
    
    fifo->in += len;
    return len;
}

4.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
25
26
27
28
29
30
31
32
33
34
/**
 * 空/满状态判断的巧妙设计
 */

// 判断是否为空
#define kfifo_is_empty(fifo) \
({ \
    typeof((fifo) + 1) __tmp = (fifo); \
    struct __kfifo *__kfifo = &__tmp->kfifo; \
    __kfifo->in == __kfifo->out; \
})

// 判断是否为满
#define kfifo_is_full(fifo) \
({ \
    typeof((fifo) + 1) __tmp = (fifo); \
    struct __kfifo *__kfifo = &__tmp->kfifo; \
    kfifo_len(__tmp) == __kfifo->mask + 1; \
})

// 计算当前元素数量
#define kfifo_len(fifo) \
({ \
    typeof((fifo) + 1) __tmp = (fifo); \
    struct __kfifo *__kfifo = &__tmp->kfifo; \
    __kfifo->in - __kfifo->out; \
})

// 为什么满状态是 len == mask + 1？
// 因为需要保留一个空位来区分空和满状态
// 如果in == out，表示空
// 如果in == out + size，表示满（但这样in和out会相等）
// 所以实际容量是 size - 1

  1. 类型安全的宏设计

5.1 泛型支持

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
/**
 * kfifo的类型安全设计
 */

// 类型安全的宏定义
#define DECLARE_KFIFO(name, size) \
    struct { \
        struct __kfifo kfifo; \
        typeof(name) *rectype; \
    } name

// 类型安全的入队操作
#define kfifo_put(fifo, val) \
({ \
    typeof((fifo) + 1) __tmp = (fifo); \
    typeof(*val) __val = (val); \
    unsigned int __ret; \
    size_t __recsize = sizeof(*__tmp->rectype); \
    struct __kfifo *__kfifo = &__tmp->kfifo; \
    __ret = __kfifo_uint32s_put(__kfifo, __val, __recsize); \
    __ret; \
})

// 类型安全的出队操作
#define kfifo_get(fifo, val) \
({ \
    typeof((fifo) + 1) __tmp = (fifo); \
    typeof(val) __val = (val); \
    unsigned int __ret; \
    const size_t __recsize = sizeof(*__tmp->rectype); \
    struct __kfifo *__kfifo = &__tmp->kfifo; \
    __ret = __kfifo_uint32s_out(__kfifo, __val, __recsize); \
    __ret; \
})

// 使用示例：
DECLARE_KFIFO(my_fifo, 32);  // 声明一个可以存储32个int的kfifo
int value = 42;
kfifo_put(&my_fifo, &value); // 类型安全的入队
kfifo_get(&my_fifo, &value); // 类型安全的出队

5.2 编译时检查

1
2
3
4
5
6
7
8
9
10
11
/**
 * 编译时类型检查
 */
#define __KFIFO_PEEK(data, out, mask) \
    ((data)&#91;(out) & (mask)])

#define __KFIFO_POKE(data, in, mask, val) \
    ( (data)&#91;(in) & (mask)] = (val) )

// 这些宏确保在编译时就能发现类型错误

  1. 性能优化技术

6.1 缓存友好性

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/**
 * 缓存友好的数据布局
 */

struct __kfifo {
    unsigned int    in;     // 控制信息集中存储
    unsigned int    out;    // 提高缓存命中率
    unsigned int    mask;
    unsigned int    esize;
    void        *data;      // 数据指针单独存储
};

// 为什么这样布局？
// 1. 控制信息连续存储，提高缓存局部性
// 2. 频繁访问的in/out字段相邻，减少缓存行加载
// 3. data指针单独存储，避免数据移动时的拷贝

6.2 编译器优化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
 * 利用编译器优化
 */

// 内联函数减少函数调用开销
static inline unsigned int kfifo_len(struct __kfifo *fifo)
{
    return fifo->in - fifo->out;
}

// 编译时常量传播
#define KFIFO_SIZE 1024
// 编译器可以将 mask = KFIFO_SIZE - 1 优化为常量

// 分支预测提示
#define likely(x)   __builtin_expect(!!(x), 1)
#define unlikely(x) __builtin_expect(!!(x), 0)

  1. 实际应用场景

7.1 内核中的典型应用

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
/**
 * Linux内核中的kfifo应用示例
 */

// 1. 网络数据包缓冲
struct sk_buff_head {
    struct __kfifo  skb_queue;
    // ...
};

// 2. 工作队列
struct workqueue_struct {
    struct __kfifo  work_list;
    // ...
};

// 3. 字符设备缓冲
struct tty_port {
    struct __kfifo  buf;
    // ...
};

// 4. 中断处理
struct irq_desc {
    struct __kfifo  pending_mask;
    // ...
};

7.2 用户空间移植

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
 * 用户空间kfifo实现要点
 */

// 1. 替换内核内存分配函数
// kmalloc -> malloc
// kfree -> free

// 2. 替换内核同步原语
// spin_lock -> pthread_mutex_lock
// smp_mb -> __sync_synchronize 或者使用互斥锁

// 3. 替换内核特定宏
// likely/unlikely -> 保持或移除
// container_of -> 自定义实现

// 4. 错误处理
// 内核返回负数错误码 -> 用户空间返回-1并设置errno

  1. 设计优势总结

8.1 性能优势

O(1)时间复杂度：所有操作都是常数时间

位运算优化：避免除法运算

缓存友好：数据局部性好

无锁设计：单生产者单消费者场景下无需锁

8.2 内存优势

紧凑布局：控制信息集中存储

零拷贝支持：直接内存访问

动态分配：按需分配内存

8.3 使用优势

类型安全：编译时类型检查

接口简洁：易于使用

广泛测试：内核级稳定性保证

8.4 可扩展性

泛型支持：支持任意数据类型

可配置大小：动态调整缓冲区大小

多线程支持：提供同步版本

这个设计体现了Linux内核对性能、可靠性和简洁性的极致追求，是系统编程的经典范例。

Linux内核kfifo实现详解-CSDN博客

https://www.calcguide.tech/2025/08/24/linux内核kfifo实现详解/

https://www.calcguide.tech/2025/08/23/getitimer系统调用及示例/

相关阅读

Linux内核kfifo实现详解
https://blog.calcguide.tech/2025-08-24-linux内核kfifo实现详解/
作者
CalcGuide
发布于
2025年8月24日
许可协议