Tag: FIFO

Linux kernel kfifo分析

本文同步自(如浏览不正常请点击跳转):https://zohead.com/archives/linux-kernel-kfifo/ kfifo 是 Linux kernel 中的一个通用队列实现,对于 kernel 中常见的 FIFO 队列应用还是很有用的,本文主要简单介绍分析下 Linux kernel kfifo。实际上 ChinaUnix 上有个 kfifo 的分析文章,但已经比较老(基于 Linux 2.6.10),而且我现在用的 2.6.34 版本 kernel 中 kfifo 实现有很多改动,故自己简单写下,ChinaUnix 上的 kfifo 介绍帖子在这里: http://bbs.chinaunix.net/thread-1994832-1-1.html kfifo 定义在 include/linux/kfifo.h 头文件中,我们经常使用的就是 kfifo 结构,看看它的定义: kfifo 也像其它队列那样提供了两个主要操作:入队列(in) 和 出队列(out),对应于上面结构中的 in 和 out 两个偏移量,in 偏移量为下次入队列的位置,out 为下次出队列的位置,很容易也能想到 out 值必须小于等于 in 值,当 out 值等于 in 值时表示队列为空,kfifo 中 buffer 为队列的空间,size 为空间大小,必须为 2 的 k 次幂值(原因在下面说明)。当然如果 in 值等于队列长度了,就表示队列已经满了。 先看看 kfifo 最简单的一些操作实现,在 kernel/kfifo.c 文件中: 调用 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 的实现: 可以看到 __kfifo_from_user_data 中是直接调用 copy_from_user 将用户空间的数据拷贝到 kfifo 队列的空间中。相应的也有 kfifo_to_user 函数将队列中的数据取出到用户空间的地址,他就调用 copy_to_user 将队列中数据拷贝到用户空间。 需要注意的是 __kfifo_from_user_data 中用到的 __kfifo_off 函数: __kfifo_off 是根据指定的偏移量得到索引值,由这里也可以看出为什么队列的大小为什么必须是 2 的 k 次幂值,否则无法得到正确的值。而且从代码中可以看到 __kfifo_from_user_data、__kfifo_in_n、__kfifo_in_rec 等函数中都用到了 __kfifo_off 函数指定加入队列时的偏移量。 另外从 include/linux/kfifo.h 中你也可以看到新的 kfifo 实现中默认 EXPORT 了非常多的 API 函数给 kernel 开发者使用。 以上为个人分析结果,有任何问题欢迎指正哦 ^_^