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->buffer = buffer;</code>
<code> </code><code>fifo->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 > 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->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->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->in + off);</code>
<code> </code><code>/* first put the data starting from fifo->in to buffer end */</code>
<code> </code><code>l = min(len, fifo->size - off);</code>
<code> </code><code>ret = copy_from_user(fifo->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->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 & (fifo->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>