explorer

万丈高楼平地起,勿在浮沙筑高台

0%

[What]linux -> kfifo

参考:

  1. 《Linux 内核设计与实现》
kernel version arch
v5.4.x lts arm32

罗列内核已经提供的 FIFO数据结构的使用方式。

Linux 内核中对 fifo 的操作已经支持得相当完善了,没必要重新造轮子,需要注意的是:

  • 当只有一个生产者和一个消费者时,不需要使用锁机制
  • 当有多个生产者和一个消费者时,仅需要给生产者加锁
  • 当有一个生产者和多个消费者时,仅需要给消费者加锁

kfifo 的实现由两部分组成:

  • /lib/kfifo.c 实现内部函数
  • /include/linux/kfifo.h 将内部函数封装为宏,供外部用户调用

API

Linux使用宏来封装成一系列可以操作的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
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
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
/**
* @brief: 定义一个动态长度的 fifo
* @fifo: fifo 的名称
* @type: 元素的类型
*/
#define DECLARE_KFIFO_PTR(fifo, type) STRUCT_KFIFO_PTR(type) fifo

/**
* @brief: 定义一个静态长度的 fifo
* @fifo: fifo 名称
* @type: 元素类型
* @size: 元素的个数(必须是2的整数次幂)
*/
#define DECLARE_KFIFO(fifo, type, size) STRUCT_KFIFO(type, size) fifo

/**
* @brief: 初始化上面定义的静态 fifo
* @fifo: fifo 名称
*/
#define INIT_KFIFO(fifo)

/**
* @brief: 定义 fifo 并将其值初始化
* @par : fifo -> fifo 的名称
* @par : type -> fifo 元素的类型
* @par : size -> fifo 元素的个数
* @note : fifo 元素的个数必须是 2 的整次幂
*/
#define DEFINE_KFIFO(fifo, type, size) \
/**
* @brief: 检查fifo是否已经被初始化
* @fifo: fifo的地址
* @return: true -> 已经被初始化
* false -> 未初始化
* @note: 当 Mask 不为 0 时,则代表该 fifo 有元素且已经被初始化过了
*/
#define kfifo_initialized(fifo) ((fifo)->kfifo.mask)
/**
* @brief: 获取 fifo 元素总共占有的字节数
* @fifo: fifo的地址
*/
#define kfifo_esize(fifo) ((fifo)->kfifo.esize)
/**
* @brief: returns the size of the record length field
* @fifo: fifo的地址
* @note: 这个还不太明白是什么意思
*/
#define kfifo_recsize(fifo) (sizeof(*(fifo)->rectype))
/**
* @brief: 获取fifo中元素的个数
*/
#define kfifo_size(fifo) ((fifo)->kfifo.mask + 1)
/**
* @brief: 清空 fifo 的计数
* @note: 清空了计数就意味着 fifo 的内容也被清空了,在使用此宏前,要确保没有其他线程在访问它
*/
#define kfifo_reset(fifo) ...
/**
* @brief: 跳过 fifo 读写之间的内容
* @note: 在仅有一个读线程访问时,可以使用此宏
* 将读写计数设置为一样,则跳过了 fifo 读写之间的内容
* 这样的话 fifo 也为空了,只不过不是从 0 计数开始
*/
#define kfifo_reset_out(fifo) ...
/**
* @brief: 获取已经使用的元素的个数
* @fifo: fifo的地址
* @note: 读写计数之间的差,则是已使用的元素
*/
#define kfifo_len(fifo) ...
/**
* @brief: 如果fifo为空返回true
* @fifo: fifo的地址
*/
#define kfifo_is_empty(fifo) ...
/**
* @brief: 如果fifo为满返回true
* @fifo: fifo的地址
*/
#define kfifo_is_full(fifo) ...
/**
* @brief: 获取空闲的元素个数
* @fifo: fifo的地址
*/
#define kfifo_avail(fifo) ...
/**
* @brief: 跳过一个元素
* @fifo: fifo的地址
*/
#define kfifo_skip(fifo) ...
/**
* @brief: 为 fifo 申请数据内存
* @fifo: fifo 地址
* @size: fifo 元素的数量,必须是 2 的整次幂
* @gfp_mask: 申请的掩码
* @note: 这个是用于宏 =DECLARE_KFIFO_PTR=
*/
#define kfifo_alloc(fifo, size, gfp_mask) ...
/**
* @brief: 释放申请的 fifo 内存
*/
#define kfifo_free(fifo) ...
/**
* @brief: 初始化申请的缓存
* @fifo: fifo 指针
* @buffer: 之前申请的 fifo 数据内存
* @size: 元素的个数,必须是 2 的整次幂
*/
#define kfifo_init(fifo, buffer, size) ...

/**
* @brief: 存入一个数据到 fifo
* @fifo: fifo 的地址
* @val: 数据的值
* @return: 0 -> fifo 满 ,否则返回处理的个数
* @note: 单生产者和单消费者使用此宏时不用外加锁
*/
#define kfifo_put(fifo, val) ...
/**
* @brief: 从 fifo 读取一个值到 val
* @fifo: fifo的地址
* @val: 数据存储的地址
* @return: 0 -> fifo 空 ,否则返回处理的个数
* @note: 单生产者和单消费者使用此宏时不用外加锁
*/
#define kfifo_get(fifo, val) ...
//从 fifo 获取值,但是该值不会从 fifo 移出
#define kfifo_peek(fifo, val) ...
/**
* @brief: 将 buf 中的 n 个元素存入 fifo
* @return: 实际存入的个数
* @note: 单生产者和单消费者使用此宏时不用外加锁
*/
#define kfifo_in(fifo, buf, n) ...
//! 带自旋锁的存储
#define kfifo_in_spinlocked(fifo, buf, n, lock)
/**
* @brief: 读取 fifo 中的 n 个元素到 buf
* @return: 实际读取的个数
* @note: 单生产者和单消费者使用此宏时不用外加锁
*/
#define kfifo_out(fifo, buf, n) ...
//! 带自旋锁的读取
#define kfifo_out_spinlocked(fifo, buf, n, lock)
//! 读取数据但是不移出队列内的数据
#define kfifo_out_peek(fifo, buf, n)
/**
* @brief: 从用户态拷贝数据到内核fifo中
* @fifo: fifo 地址
* @from: buf 地址
* @len: 数据字节数
* @copied: 实际拷贝的字节数
* @note: 单生产者和单消费者使用此宏时不用外加锁
*
*/
#define kfifo_from_user(fifo, from, len, copied) ...
/**
* @brief: 从内核态拷贝数据到用户态中
* @fifo: fifo 地址
* @to: buf 地址
* @len: 数据字节数
* @copied: 实际拷贝的字节数变量的地址
*/
#define kfifo_to_user(fifo, to, len, copied) ...

分析

定义与初始化

kfifo 的核心结构定义如下:

1
2
3
4
5
6
7
8
9
10
struct __kfifo {
unsigned int in;
unsigned int out;
//fifo 元素的个数的掩码,比如 16 的低位掩码就是 0b1111(0x0F)
unsigned int mask;
//fifo 元素所总共占用的字节数
unsigned int esize;
//指向 fifo 的首元素
void *data;
};

静态定义和初始化

而宏 DEFINT_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
//! fifo 的名称是 fifo
//! fifo 的类型是 datatype
//! 这个 fifo 一共有 size 个元素
//DEFINE_KFIFO(fifo, datatype, size)
struct
{
//以联合体的方式来表示该 fifo 的信息,这个有点像是元数据
union
{
struct __kfifo kfifo;
datatype *type;//元素的指针
const datatype *const_type;//const 元素的指针,不能改变元素但可以在多个元素中移动
char (*rectype)[0];
datatype *ptr;
datatype const *ptr_const;//元素的 const 指针,可以改变元素内容,但不能修改其指向
};
//用数字存放 size 个元素,这里会检查元素的个数是否是 2 的整次幂
datatype buf[((size < 2) || (size & (size - 1))) ? -1 : size];
} fifo =

typeof(fifo)
{
//初始化其 union,以 kfifo 的形式来写入
{
{
.in = 0,
.out = 0,
//这里的 __is_kfifo_ptr 用于检查该 fifo 是否是动态 fifo
//如果是动态 fifo,则元素大小为 0,元素指针为空
.mask = __is_kfifo_ptr(&(fifo)) ? 0 : ARRAY_SIZE((fifo).buf) - 1,
.esize = sizeof(*(fifo).buf),
.data = __is_kfifo_ptr(&(fifo)) ? NULL : (fifo).buf,
}
}
}

这是静态定义和初始化的方式,FIFO 的大小在此刻就已经定死了。

当然也可以先使用 DECLARE_KFIFO 定义,然后再使用 INIT_KFIFO 来初始化。

动态定义

动态定义的方式便是先不指定其元素的个数,而是在后面动态申请。

DECLARE_KFIFO_PTR 来完成此定义:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//DECLARE_KFIFO_PTR(fifo, datatype)
struct
{
//以联合体的方式来表示该 fifo 的信息,这个有点像是元数据
union
{
struct __kfifo kfifo;
datatype *type;//元素的指针
const datatype *const_type;//const 元素的指针,不能改变元素但可以在多个元素中移动
char (*rectype)[0];
datatype *ptr;
datatype const *ptr_const;//元素的 const 指针,可以改变元素内容,但不能修改其指向
};
//这个零长数值就是便于后面扩展元素用的
datatype buf[0];
} fifo

单独的申请内存便使用 kfifo_alloc 宏来完成,然后使用 kfifo_init 完成初始化。

实例验证

内核示例

内核在 /samples/kfifo/inttype-example.c 中展示了如何使用:

该示例代码在 insmod 后便调用 testfunc 完成测试,用户还可以在 "/proc/int-fifo" 中体验。

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
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
// SPDX-License-Identifier: GPL-2.0-only
/*
* Sample kfifo int type implementation
*
* Copyright (C) 2010 Stefani Seibold
*/

#include
#include
#include
#include
#include

/*
* This module shows how to create a int type fifo.
*/

/* fifo size in elements (ints) */
#define FIFO_SIZE 32

/* name of the proc entry */
#define PROC_FIFO "int-fifo"

/* lock for procfs read access */
static DEFINE_MUTEX(read_lock);

/* lock for procfs write access */
static DEFINE_MUTEX(write_lock);

/*
* define DYNAMIC in this example for a dynamically allocated fifo.
*
* Otherwise the fifo storage will be a part of the fifo structure.
*/
#if 0
#define DYNAMIC
#endif

#ifdef DYNAMIC
static DECLARE_KFIFO_PTR(test, int);
#else
static DEFINE_KFIFO(test, int, FIFO_SIZE);
#endif

static const int expected_result[FIFO_SIZE] = {
3, 4, 5, 6, 7, 8, 9, 0,
1, 20, 21, 22, 23, 24, 25, 26,
27, 28, 29, 30, 31, 32, 33, 34,
35, 36, 37, 38, 39, 40, 41, 42,
};

static int __init testfunc(void)
{
int buf[6];
int i, j;
unsigned int ret;

printk(KERN_INFO "int fifo test start\n");

/* put values into the fifo */
for (i = 0; i != 10; i++)
kfifo_put(&test, i);

/* show the number of used elements */
printk(KERN_INFO "fifo len: %u\n", kfifo_len(&test));

/* get max of 2 elements from the fifo */
ret = kfifo_out(&test, buf, 2);
printk(KERN_INFO "ret: %d\n", ret);
/* and put it back to the end of the fifo */
ret = kfifo_in(&test, buf, ret);
printk(KERN_INFO "ret: %d\n", ret);

/* skip first element of the fifo */
printk(KERN_INFO "skip 1st element\n");
kfifo_skip(&test);

/* put values into the fifo until is full */
for (i = 20; kfifo_put(&test, i); i++)
;

printk(KERN_INFO "queue len: %u\n", kfifo_len(&test));

/* show the first value without removing from the fifo */
if (kfifo_peek(&test, &i))
printk(KERN_INFO "%d\n", i);

/* check the correctness of all values in the fifo */
j = 0;
while (kfifo_get(&test, &i)) {
printk(KERN_INFO "item = %d\n", i);
if (i != expected_result[j++]) {
printk(KERN_WARNING "value mismatch: test failed\n");
return -EIO;
}
}
if (j != ARRAY_SIZE(expected_result)) {
printk(KERN_WARNING "size mismatch: test failed\n");
return -EIO;
}
printk(KERN_INFO "test passed\n");

return 0;
}

static ssize_t fifo_write(struct file *file, const char __user *buf,
size_t count, loff_t *ppos)
{
int ret;
unsigned int copied;

if (mutex_lock_interruptible(&write_lock))
return -ERESTARTSYS;

ret = kfifo_from_user(&test, buf, count, &copied);

mutex_unlock(&write_lock);

return ret ? ret : copied;
}

static ssize_t fifo_read(struct file *file, char __user *buf,
size_t count, loff_t *ppos)
{
int ret;
unsigned int copied;

if (mutex_lock_interruptible(&read_lock))
return -ERESTARTSYS;

ret = kfifo_to_user(&test, buf, count, &copied);

mutex_unlock(&read_lock);

return ret ? ret : copied;
}

static const struct file_operations fifo_fops = {
.owner = THIS_MODULE,
.read = fifo_read,
.write = fifo_write,
.llseek = noop_llseek,
};

static int __init example_init(void)
{
#ifdef DYNAMIC
int ret;

ret = kfifo_alloc(&test, FIFO_SIZE, GFP_KERNEL);
if (ret) {
printk(KERN_ERR "error kfifo_alloc\n");
return ret;
}
#endif
if (testfunc() < 0) {
#ifdef DYNAMIC
kfifo_free(&test);
#endif
return -EIO;
}

if (proc_create(PROC_FIFO, 0, NULL, &fifo_fops) == NULL) {
#ifdef DYNAMIC
kfifo_free(&test);
#endif
return -ENOMEM;
}
return 0;
}

static void __exit example_exit(void)
{
remove_proc_entry(PROC_FIFO, NULL);
#ifdef DYNAMIC
kfifo_free(&test);
#endif
}

module_init(example_init);
module_exit(example_exit);
MODULE_LICENSE("GPL");
MODULE_AUTHOR("Stefani Seibold ");
Last Updated 2020-08-20 四 17:38.
Render by hexo-renderer-org with Emacs 26.3 (Org mode 9.3.7)