Linux kernel kfifo分析【转】

kfifo 是 Linux kernel 中的一个通用队列实现，对于 kernel 中常见的 FIFO 队列应用还是很有用的，本文主要简单介绍分析下 Linux kernel kfifo。实际上 ChinaUnix 上有个 kfifo 的分析文章，但已经比较老（基于 Linux 2.6.10），而且我现在用的 2.6.34 版本 kernel 中 kfifo 实现有很多改动，故自己简单写下，ChinaUnix 上的 kfifo 介绍帖子在这里：

<a href="http://bbs.chinaunix.net/thread-1994832-1-1.html" target="_blank">http://bbs.chinaunix.net/thread-1994832-1-1.html</a>

kfifo 定义在 include/linux/kfifo.h 头文件中，我们经常使用的就是 kfifo 结构，看看它的定义：

1

2

3

4

5

6

<code>struct</code> <code>kfifo {</code>

<code>    </code><code>unsigned</code><code>char</code> <code>*buffer; </code><code>/* the buffer holding the data */</code>

<code>    </code><code>unsigned</code><code>int</code> <code>size; </code><code>/* the size of the allocated buffer */</code>

<code>    </code><code>unsigned</code><code>int</code> <code>in;   </code><code>/* data is added at offset (in % size) */</code>

<code>    </code><code>unsigned</code><code>int</code> <code>out;  </code><code>/* data is extracted from off. (out % size) */</code>

<code>};</code>

kfifo 也像其它队列那样提供了两个主要操作：入队列（in） 和 出队列（out），对应于上面结构中的 in 和 out 两个偏移量，in 偏移量为下次入队列的位置，out 为下次出队列的位置，很容易也能想到 out 值必须小于等于 in 值，当 out 值等于 in 值时表示队列为空，kfifo 中 buffer 为队列的空间，size 为空间大小，必须为 2 的 k 次幂值（原因在下面说明）。当然如果 in 值等于队列长度了，就表示队列已经满了。

先看看 kfifo 最简单的一些操作实现，在 kernel/kfifo.c 文件中：

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

<code>static</code> <code>void</code> <code>_kfifo_init(</code><code>struct</code> <code>kfifo *fifo,</code><code>void</code> <code>*buffer,</code>

<code>        </code><code>unsigned</code><code>int</code> <code>size)</code>

<code>{</code>

<code>    </code><code>fifo-&gt;buffer = buffer;</code>

<code>    </code><code>fifo-&gt;size = size;</code>

<code>    </code><code>kfifo_reset(fifo);</code>

<code>}</code>

<code>/**</code>

<code> </code><code>* kfifo_init - initialize a FIFO using a preallocated buffer</code>

<code> </code><code>* @fifo: the fifo to assign the buffer</code>

<code> </code><code>* @buffer: the preallocated buffer to be used.</code>

<code> </code><code>* @size: the size of the internal buffer, this has to be a power of 2.</code>

<code> </code><code>*</code>

<code> </code><code>*/</code>

<code>void</code> <code>kfifo_init(</code><code>struct</code> <code>kfifo *fifo,</code><code>void</code> <code>*buffer, unsigned</code><code>int</code> <code>size)</code>

<code>    </code><code>/* size must be a power of 2 */</code>

<code>    </code><code>BUG_ON(!is_power_of_2(size));</code>

<code>    </code><code>_kfifo_init(fifo, buffer, size);</code>

<code>EXPORT_SYMBOL(kfifo_init);</code>

<code> </code><code>* kfifo_alloc - allocates a new FIFO internal buffer</code>

<code> </code><code>* @fifo: the fifo to assign then new buffer</code>

<code> </code><code>* @size: the size of the buffer to be allocated, this have to be a power of 2.</code>

<code> </code><code>* @gfp_mask: get_free_pages mask, passed to kmalloc()</code>

<code> </code><code>* This function dynamically allocates a new fifo internal buffer</code>

<code> </code><code>* The size will be rounded-up to a power of 2.</code>

<code> </code><code>* The buffer will be release with kfifo_free().</code>

<code> </code><code>* Return 0 if no error, otherwise the an error code</code>

<code>int</code> <code>kfifo_alloc(</code><code>struct</code> <code>kfifo *fifo, unsigned</code><code>int</code> <code>size, gfp_t gfp_mask)</code>

<code>    </code><code>unsigned</code><code>char</code> <code>*buffer;</code>

<code>    </code><code>/*</code>

<code>     </code><code>* round up to the next power of 2, since our 'let the indices</code>

<code>     </code><code>* wrap' technique works only in this case.</code>

<code>     </code><code>*/</code>

<code>    </code><code>if</code> <code>(!is_power_of_2(size)) {</code>

<code>        </code><code>BUG_ON(size &gt; 0x80000000);</code>

<code>        </code><code>size = roundup_pow_of_two(size);</code>

<code>    </code><code>}</code>

<code>    </code><code>buffer = kmalloc(size, gfp_mask);</code>

<code>    </code><code>if</code> <code>(!buffer) {</code>

<code>        </code><code>_kfifo_init(fifo, NULL, 0);</code>

<code>        </code><code>return</code> <code>-ENOMEM;</code>

<code>    </code><code>return</code> <code>0;</code>

<code>EXPORT_SYMBOL(kfifo_alloc);</code>

<code> </code><code>* kfifo_free - frees the FIFO internal buffer</code>

<code> </code><code>* @fifo: the fifo to be freed.</code>

<code>void</code> <code>kfifo_free(</code><code>struct</code> <code>kfifo *fifo)</code>

<code>    </code><code>kfree(fifo-&gt;buffer);</code>

<code>    </code><code>_kfifo_init(fifo, NULL, 0);</code>

<code>EXPORT_SYMBOL(kfifo_free);</code>

调用 kfifo_alloc 可以自动分配空间并初始化，你也可以调用 kfifo_init 函数使用自己的空间来初始化队列，可以看到这两个函数中都用 is_power_of_2 做了检查队列空间的操作。kfifo_free 释放队列，它会调用 _kfifo_init 函数（参数为 NULL 和 0 清空队列），调用 kfifo_reset 可以重置队列（将 in 和 out 都设为 0）。你也可以用 DECLARE_KFIFO 和 INIT_KFIFO 静态定义一个 kfifo 队列，尽管这不太会被用到。

调用 kfifo_in 函数将数据加入队列，kfifo_out 将数据从队列中取出并从队列中删除（增加 out 值），Linux 还提供了 kfifo_out_peek 函数从队列中取数据但并不删除（不增加 out 值）。kfifo_in 中会先调用 __kfifo_in_data 将输入加入队列，然后调用 __kfifo_add_in 增加 in 的值，kfifo_out 相反则调用 __kfifo_out_data 和 __kfifo_add_out 函数取出数据并删除。

kfifo 中同时提供了 kfifo_from_user 函数用户将用户空间的数据加入到队列中，它会先调用 __kfifo_from_user_data 将用户空间的数据加入队列，再调用 __kfifo_add_in 增加 in 的值。看看 __kfifo_from_user_data 的实现：

<code>static</code> <code>inline</code> <code>int</code> <code>__kfifo_from_user_data(</code><code>struct</code> <code>kfifo *fifo,</code>

<code>     </code><code>const</code> <code>void</code> <code>__user *from, unsigned</code><code>int</code> <code>len, unsigned</code><code>int</code> <code>off,</code>

<code>     </code><code>unsigned *lenout)</code>

<code>    </code><code>unsigned</code><code>int</code> <code>l;</code>

<code>    </code><code>int</code> <code>ret;</code>

<code>     </code><code>* Ensure that we sample the fifo-&gt;out index -before- we</code>

<code>     </code><code>* start putting bytes into the kfifo.</code>

<code>    </code><code>smp_mb();</code>

<code>    </code><code>off = __kfifo_off(fifo, fifo-&gt;in + off);</code>

<code>    </code><code>/* first put the data starting from fifo-&gt;in to buffer end */</code>

<code>    </code><code>l = min(len, fifo-&gt;size - off);</code>

<code>    </code><code>ret = copy_from_user(fifo-&gt;buffer + off, from, l);</code>

<code>    </code><code>if</code> <code>(unlikely(ret)) {</code>

<code>        </code><code>*lenout = ret;</code>

<code>        </code><code>return</code> <code>-EFAULT;</code>

<code>    </code><code>*lenout = l;</code>

<code>    </code><code>/* then put the rest (if any) at the beginning of the buffer */</code>

<code>    </code><code>ret = copy_from_user(fifo-&gt;buffer, from + l, len - l);</code>

<code>    </code><code>*lenout += ret ? ret : len - l;</code>

<code>    </code><code>return</code> <code>ret ? -EFAULT : 0;</code>

可以看到 __kfifo_from_user_data 中是直接调用 copy_from_user 将用户空间的数据拷贝到 kfifo 队列的空间中。相应的也有 kfifo_to_user 函数将队列中的数据取出到用户空间的地址，他就调用 copy_to_user 将队列中数据拷贝到用户空间。

需要注意的是 __kfifo_from_user_data 中用到的 __kfifo_off 函数：

<code>static</code> <code>inline</code> <code>unsigned</code><code>int</code> <code>__kfifo_off(</code><code>struct</code> <code>kfifo *fifo, unsigned</code><code>int</code> <code>off)</code>

<code>    </code><code>return</code> <code>off &amp; (fifo-&gt;size - 1);</code>

__kfifo_off 是根据指定的偏移量得到索引值，由这里也可以看出为什么队列的大小为什么必须是 2 的 k 次幂值，否则无法得到正确的值。而且从代码中可以看到 __kfifo_from_user_data、__kfifo_in_n、__kfifo_in_rec 等函数中都用到了 __kfifo_off 函数指定加入队列时的偏移量。

另外从 include/linux/kfifo.h 中你也可以看到新的 kfifo 实现中默认 EXPORT 了非常多的 API 函数给 kernel 开发者使用。

以上为个人分析结果，有任何问题欢迎指正哦 ^_^

相关文章:

<a href="https://zohead.com/archives/linux-kernel-learning-memory-management/">Linux kernel学习-内存管理</a>

<a href="https://zohead.com/archives/linux-kernel-percpu-variable/">Linux kernel percpu变量解析</a>

<a href="https://zohead.com/archives/linux-kernel-learning-process-address-space/">Linux kernel学习-进程地址空间</a>

<a href="https://zohead.com/archives/linux-kernel-learning-memory-addressing/">Linux kernel学习-内存寻址</a>

<a href="https://zohead.com/archives/linux-kernel-learning-block-layer/">Linux kernel学习-block层</a>