or
or
By clicking below, you agree to our terms of service.
New to HackMD? Sign up
Syntax | Example | Reference | |
---|---|---|---|
# Header | Header | 基本排版 | |
- Unordered List |
|
||
1. Ordered List |
|
||
- [ ] Todo List |
|
||
> Blockquote | Blockquote |
||
**Bold font** | Bold font | ||
*Italics font* | Italics font | ||
~~Strikethrough~~ | |||
19^th^ | 19th | ||
H~2~O | H2O | ||
++Inserted text++ | Inserted text | ||
==Marked text== | Marked text | ||
[link text](https:// "title") | Link | ||
 | Image | ||
`Code` | Code |
在筆記中貼入程式碼 | |
```javascript var i = 0; ``` |
|
||
:smile: | ![]() |
Emoji list | |
{%youtube youtube_id %} | Externals | ||
$L^aT_eX$ | LaTeX | ||
:::info This is a alert area. ::: |
This is a alert area. |
On a scale of 0-10, how likely is it that you would recommend HackMD to your friends, family or business associates?
Please give us some advice and help us improve HackMD.
Do you want to remove this version name and description?
Syncing
xxxxxxxxxx
2020q1 Homework2 (fibdrv)
contributed by <
KYG-yaya573142
>預期目標
排除干擾效能分析的因素
限定 CPU 給特定的程式使用
修改
/etc/default/grub
內的GRUB_CMDLINE_LINUX_DEFAULT
,加入isolcpus=7
來指定編號 7 的核心不被排程器賦予任務,修改完成後需sudo update-grub
來更新設定,重開機後即生效 (可從/sys/devices/system/cpu/isolated
確認是否生效)修改後可觀察到 PID 1 - init 的 affinity list 不包含該編號的 CPU
將程式固定在特定的 CPU 中執行
透過指定處理器親和性 (processor affinity,亦稱 CPU pinning),可以將程式固定在特定的 CPU 中執行
抑制 address space layout randomization (ASLR)
設定 scaling_governor 為 performance
準備以下 shell script 來設定 CPU 以最高頻率執行所有 process
關閉 turbo mode
關閉 Intel 處理器的 turbo mode
整合為單一 script
整合成單一 script 以便於重複操作,詳見 do_measurement.sh
SMP IRQ affinity
執行上述步驟後進行量測,發現結果仍有飄動的情況

針對 SMP IRQ affinity 進行設置,盡量避免 CPU 7 去處理 IRQ。使用以下 script 進行設置,僅將 CPU 7 從可用清單去除,但不大幅度改變本來系統的設置 (例如 smp_affinity 原本是 0~7,只會被更改為 0~6)
註: smp_affinity 和 smp_affinity_list 擇一設定即可
設置完畢後可以透過

cat /proc/interrupts
觀察 CPU 7 的 IRQ 數量,同時也可以量測到更穩定的實驗結果量測時間的方式
user space
使用
clock_gettime
來取得時間kernel space
使用 ktime 來量測執行時間,這裡參照作業說明的手法,挪用
fib_write
來回傳 kernel space 的執行時間,同時借用size
參數當作切換的參數,以便於量測不同演算法的執行時間write(fd, buf, 0)
- 回傳 iterative 算法的執行時間write(fd, buf, 1)
- 回傳 fast doubling 的執行時間write(fd, buf, 2)
- 單純回傳在 kernel space 使用ktime_get
獲得的時間點 (後續分析會用到)統計量測結果
為了增加量測資料的代表性,對每一項費氏數列的計算時間採樣 1000 次,再根據 95% 的信賴區間來去除離群值,使用程式碼可參閱 client_statistic.c
user space 與 kernel space 的傳遞時間
system call overhead
使用上述量測時間的方式中提到的方式分別量測 user space 及 kernel space 花費的時間,再將兩者相減即可獲得 user space 呼叫 system call 所花費的時間
copy_from_user
來複製資料,仍花費約 500 ns 的時間在執行 system call 本身將
fib_write
改為僅回傳ktime_get
獲得的時間點,配合在 user space 記錄呼叫write
的前後時間點,可以再進一步取得 system call overhead 中 user to kernel 和 kernel to user 所花費的時間TODO:
- The image file may be corrupted
- The server hosting the image is unavailable
- The image path is incorrect
- The image format is not supported
Learn More →接下來使用 mlock 系列的系統呼叫,並參照 Threaded RT-application with memory locking and stack handling example 的範例,確保 user space 的 page 不會被 swap out
copy_{from/to}_user
的傳遞時間修改
fib_read
和fib_write
來量測傳遞時間read
和write
需負責更新offset
的位置,為了簡化流程所以沒有實作這點fib_write
一樣改法,只是將copy_to_user
改為copy_from_user
接著在 user space 使用對
/def/fibdrv
執行read
和write
來取得 kernel space 的執行時間copy_to_user
根據 CPU 架構有不同的實作,以 x86 為例,在 /arch/x86/lib/copy_user_64.S 可以觀察到會使用不同的方式來加速複製 (視硬體支援),但原則上還是呈線性成長,只是斜率會不同費氏數列
iterative 算法
fibdrv 一開始就是使用此法進行計算,時間複雜度為 \(O(n)\)
fast doubling
參閱你所不知道的 C 語言:遞迴呼叫篇對 fast doubling 的說明,使用以下兩式來計算費氏數列
\[ \begin{split} F(2k) &= F(k)[2F(k+1) - F(k)] \\ F(2k+1) &= F(k+1)^2+F(k)^2 \end{split} \]
fast doubling 每次疊代會根據 F(k) 與 F(k+1) 來計算 F(2k) 與 F(2k+1),由於 k 只能是整數,因此當所求項為奇數時,代表所求的目標會變成 F(2k+1),也就是乘 2 之後需要再加 1 項才是目標
以計算 F(10) 為例,首先考量 2 進位下的表達
\(10_{10}=1010_2\)
乘 2 即左移一項
k << 1
,因此可以理解為從 F(0) 開始,經過以下 4 個步驟可以得到 F(10),這也是為何 fast doubling 實作上會根據 bit 來決定計算的步驟(0000 << 1) + 1 = 0001
(0001 << 1) + 0 = 0010
(0010 << 1) + 1 = 0101
(0101 << 1) + 0 = 1010
參考作業說明的虛擬碼以及Calculating Fibonacci Numbers by Fast Doubling後,實作程式碼如下
clz 的影響
fast doubling 需要根據 bit 來決定計算的步驟,因此使用 clz/ctz 可以縮短尋找 MSB (Most Significant Bit) 的時間
Other Built-in Functions Provided by GCC
__builtin_clz
的參數不能是 0使用以下幾種方式實作 fast doubling 並測試,目的是凸顯尋找 MSB 所耗費的時間差異
__builtin_clz
來尋找 MSB1U << 31
1U << 16
與1U << 6
(\(92_{10} = 1011100_2\),因此至少需要移動 6 bits,否則會計算錯誤)__builtin_clz
所耗時間最少心得 - 注意實驗設置
一開始我使用以下方式來測試執行時間
得到的結果如下,顯示使用 clz 沒有比較快,甚至可能更慢一些

怎麼想都覺得事有蹊俏,決定看一下組合語言 (如果有 offset 可以加上
--adjust-vma=0xoffset
來調整,從 /proc/modules 可以查詢 offset)結果發現
fib_sequence_fdouble
直接被 opt out 啦,所以我一開始測出來的數據根本就沒有執行費氏數列相關的計算為了避免
fib_sequence_fdouble
因沒有用到回傳值而被優化掉,參照 CppCon 2015: Tuning C++: Benchmarks, and CPUs, and Compilers! Oh My! 提到的方法,使用escape
來確保回傳值不會被 opt out (inline asm 相關的語法請參閱 GCC Extended Asm)另外,也可以觀察
__builtin_clz
是如何實作的1U << (31 - __builtin_clz)
,也就是 MSB 後有幾個 bits,其實會直接等於 instruction - bsr 的結果xor $0xffffffe0,%eax
和lea 0x20(%rax),%ecx
這兩個 instruction 看起來就算不做,結果也一樣,不知道是否有我沒想到的作用F(92) 以後的數值錯誤的原因
初次執行
client
會發現從 F(92) 之後輸出的數值都一樣,這是因為 fibdrv 中預設限制最大項目為 92fib_read
返回的資料型態為long long
,即 64 bits 的有號整數,可涵蓋的整數值介於 \(2^{64 - 1}-1\) 至 \(-2^{64}\) 之間,比對費氏數列的正確值,可確認 F(93) 會超出此範圍,這也是預設限制最大可用項目為 92 的原因移除限制並重新觀察輸出,會從 F(93) 開始 overflow
雖然結果 overflow,但可根據 two's complement 算出 overflow 後為何是這個數值
\[ \begin{equation} \begin{aligned} if (A + B) &> T_{Max} \quad(overflow) \\ result &= A + B - 2^{64} \\ &= F(91) + F(92) - 2^{64} \\ &= -6246583658587674878 \end{aligned} \end{equation} \]
將使用的 data type 由
long long
更改為uint64_t
,可以多計算出一項正確的數值 F(93),不過從 F(94) 開始仍會 overflow一樣可以檢驗 overflow 後為何是這個數值
\[ \begin{equation} \begin{aligned} if (A + B) &> U_{Max} \quad(overflow) \\ result &= A + B \quad(mod\quad2^w - 1) \\ &= A + B - 2^{64} \\ &= F(92) + F(93) - 2^{64} \\ &= 1293530146158671551 \end{aligned} \end{equation} \]
大數運算
bn
資料結構為了計算 92 項以後的費氏數列,須採用長度可變動的數值表示法,動態配置不同大小的記憶體來呈現更大範圍的整數,定義的資料結構如下
number
- 指向儲存的數值,之後會以 array 的形式來取用size
- 配置的記憶體大小,單位為sizeof(unsigned int)
sign
- 0 為正數、1 為負數由於大數沒辦法直接以數值的形式列出,這裡改用字串來呈現,轉換的部分利用 ASCII 的特性並根據 fast doubling 的邏輯來 "組合" 出 10 進位字串
加法與減法
加法與減法由於需要考慮數值的正負號,因此分為兩個步驟,先由
bn_add
與bn_sub
判斷結果的正負號,再使用輔助函數bn_do_add
與bn_do_add
進行無號整數的計算bn_add
負責所有正負號的判斷,所以bn_sub
只是改變 b 的正負號後,再直接交給bn_add
判斷tmp
來暫時的賦予不同的正負號bn_cmp
負責比對兩個bn
物件開絕對值後的大小,邏輯類似strcmp
c
的大小足以儲存計算結果DIV_ROUNDUP
的用法參考自 /arch/um/drivers/cow_user.ccarry
來實行兩個 4 bytes 項目的加法來避免 overflowbn_msb
和bn_clz
是 bn 版本的 clz,詳見 bn_kernel.ca
與b
,並於計算完成後再再補上負號bn_do_add
一樣,不過此時 carry 是作為借位使用乘法
c == a || c == b
,就必須配置記憶體來儲存計算結果,避免a
與b
在計算途中就被改變bn_mult_add
負責將每一行的計算結果疊加上去,如下bit shift
swap
number
紀錄的是指標,因此這麼做可以確實的互換兩個 bn 的數值,但不用更動儲存在 heap 中的數值正確計算 F(92) 以後的數值
使用實作的大數運算來計算第 92 項以後的費氏數列,首先是 iterative 算法
接著是 fast doubling 的實作
使用以下 python 程式碼進行驗證,至少能正確計算至第 100000 項
如何減少大數運算的成本
接下來會以 perf 分析函式的熱點,再逐步改善大數運算的效能
原本的運算成本
測試環境
-O2
、-g
、-fno-omit-frame-pointer
運算成本
初版實作的效能如下,參考組為老師實作的 bignum
perf
本文中主要使用
perf stat
、perf record
、perf report
這三種工具,以下分別介紹接下來會用的設置參數perf stat
perf stat
用來快速的檢視量測的統計資料,詳細的訊息需使用perf record
-r 10
: 量測 10 次,目的是確認每次量測間沒有明顯的波動-e
: 指定要量測的項目perf record
perf record
會紀錄樣本,預設輸出檔名為 perf.data-g
: 紀錄 call graph,可搭配--call graph
指定 stack trace 的方式,預設為 fp--fomit-frame-pointer
使用,但如果受測函數呼叫 libc 函式,會因為函式庫編譯時沒有使用該 flag 編譯而導致 perf record 無法正確紀錄 stack trace,改用 dwarf 或是 lbr 可以避免這個問題--fomit-frame-pointer
,建議使用 dwarf 來量測,因此接下來都使用 dwarfperf report
perf report
會顯示perf record
採樣的結果,預設讀取的檔案名稱為 perf.data--stdio
: 使用 stdio 作為輸出介面,主要是方便我將結果貼上來,預設是--tui
--children
: 將 callee 的樣本加入 caller,這個選項與-g
有關,預設為--children
-g
: 顯示 call graph,使用 perf record 時如果有-g
,perf report 時也要一併使用--children
時,-g
的預設值是graph,0.5,caller
,會產生 caller-based 的 call graph--no-children
時,-g
的預設值是graph,0.5,callee
,會產生 callee-based 的 call graphcaller 與 callee 的差別
perf report
可以對同一筆資料分別產生 caller-based 與 callee-based 兩種 call graph,分別提供不同的數據解讀方向。接下來以一個簡單的程式舉例,考量以下程式碼 foobar.ccaller-based call graph
callee-based
測試程式碼
perf record
及perf stat
皆使用以下程式碼進行測試ITER_TIMES
會根據不同的量測範圍ITH
與使用的演算法而改變,但後續的討論只會直接比對同條件下的量測結果escape
用來確保每次迴圈都會確實的執行受測函式優化
bn_fib_fdoubling
先以
perf stat
分析目前實作的效能,作為後續比對的基準接下來使用
perf record
量測 call graph (有省略部分內容來提升可讀性)bn_fib_fdoubling
內,其中有 83.03% 的時間會再呼叫其他函式bn_mult
佔整體 48.43% 的時間,因此優化乘法會帶來明顯的效能增益bn_fib_fdoubling
內有接近一半的時間在管理動態記憶體與複製資料,顯然需要相關的策略來降低這部分的成本bn_add
與bn_sub
共佔 9% 的時間,需要再單獨使用 iterative 版本的bn_fib
來進行分析與優化,否則很難在bn_fib_fdoubling
內觀察到效能增益bn_free
占有高比例的原因不明,目前先猜測可能是因為bn_mult
過度頻繁的呼叫bn_alloc
與bn_free
改善方案 1 - 改寫
bn_fib_fdoubling
實作的方式bn_cpy
來更新暫存變數k1
與k2
的數值,其實可以藉由bn_swap
以及改變各函式儲存結果的位置來達成一樣的目的,將所有的bn_cpy
去除來降低複製資料造成的成本c == a || c == b
),bn_mult
必須先配置暫存的記憶體空間來儲存計算結果,因此可以進一步確保呼叫bn_mult
時不要發生此狀況,降低使用malloc
及memcpy
的次數結果如下 (v1 綠線)

改善方案 2 - 使用不同的 Q-Matrix 實作
bn_fib_fdoubling
觀察老師的 bignum 中費氏數列的實作函式 fibonacci,會發現雖然一樣基於 fast doubling,但是使用了稍微不一樣的 Q-matrix,推導如下
\[ \begin{split} \begin{bmatrix} F(2n-1) \\ F(2n) \end{bmatrix} &= \begin{bmatrix} 0 & 1 \\ 1 & 1 \end{bmatrix}^{2n} \begin{bmatrix} F(0) \\ F(1) \end{bmatrix}\\ \\ &= \begin{bmatrix} F(n-1) & F(n) \\ F(n) & F(n+1) \end{bmatrix} \begin{bmatrix} F(n-1) & F(n) \\ F(n) & F(n+1) \end{bmatrix} \begin{bmatrix} 1 \\ 0 \end{bmatrix}\\ \\ &= \begin{bmatrix} F(n)^2 + F(n-1)^2\\ F(n)F(n) + F(n)F(n-1) \end{bmatrix} \end{split} \]
整理後可得
\[ \begin{split} F(2k-1) &= F(k)^2+F(k-1)^2 \\ F(2k) &= F(k)[2F(k-1) + F(k)] \end{split} \]
使用上述公式改寫
bn_fib_fdoubling
,優點是可以少掉一次迴圈的計算及避免使用減法結果如下 (v2 紅線)
改善 bn 使用動態記憶體的方式
原本實作的大數運算會在計算前先使用
bn_resize
(realloc
),確保有足夠大的空間來儲存計算結果,再於計算結束後檢查是否有多餘的空間 (msb 所在的 array 數值為 0) 並進行修剪 (trim),避免造成 memory leak 與增加後續計算的成本 (因為要走訪的空間會越來越長),然而頻繁使用realloc
可能會造成降低效能改善方案 3 - 引入 memory pool 的概念
參考 quiz 4,以 capacity 的方式管理 bn 實際可用的記憶體大小,降低
bn_resize
實際呼叫realloc
的次數realloc
,並以 4 為單位配置更大的空間realloc
來縮小空間結果如下 (v3 紅線)
realloc
造成的成本非常可觀改善方案 4 - 善用 64-bit CPU 的優勢
bn 資料結構中原本每個 array 的資料型態使用
unsigned int
,在 64-bit CPU 下改為使用uint64_t
應該能增加計算效能 (因為 word size 就是 64-bit)__int128
實作結果如下 (v4)

uint64_t
更能發揮 64 位元 CPU 的優勢改善
bn_add
的效能為了凸顯
bn_add
對效能的影響,這個章節改為量測bn_fib
(iterative) 作為判斷依據,並將量測的範圍提高到 F(10000)。由於上述幾個改善策略也會提升bn_add
的效能,因此先重新量測現有的效能,結果如下 (v1 紅線)改善方案 I - 改寫
bn_add
的實作法原本的實作會在每次迴圈判斷需要相加的數值,這麼做的優點是只需寫一個迴圈就能完成計算,但缺點是每次迴圈都有兩個 branch 要判斷。為了改善這點,改為使用兩個迴圈進行計算,第一個迴圈先計算兩者皆有資料的範圍,再於第二個迴圈處理 carry 與剩餘的資料範圍。另外,藉由無號整數不會 overflow 的特性 (modulo),可以進一步避免使用
__int128
(bn_data_tmp
) 進行計算改善
bn_mult
的效能改回量測

bn_fib_fdoubling
作為判斷依據,並接續上述 fast doubling v4 版本,將測試範圍提高至 F(10000),會發現bn_mult
的效能明顯低於對照組改善方案 5 - 改寫
bn_mult
的實作法原本實作
bn_mult
的方式為依序將兩格 array 相乘,再將結果直接疊加至輸出的變數,然而這會導致每行乘法被拆分成 2 個步驟 (相乘後先將 carry 疊加至下個 array,下次迴圈又再從該 array 取出數值來進行乘法),降低計算的速度。接下來參考 bignum/mul.c 來改寫bn_mult
,改為一次將乘積與 carry 疊加至輸出的變數來提升效能改善方案 6 - inline asm
bignum 中使用 inline asm 來直接取得乘法運算的高位與低位,直接使用一樣的方式實作乘法,取代原本使用的
__int128
(bn_data_tmp
)__int128
好,主因是沒辦法藉由使用__int128
直接把乘積的高位與低位儲存至指定的空間引入
bn_sqr
考慮上述 \(abc^2\) 的計算過程,會發現數值 \(ab\) 、 \(ac\) 與 \(bc\) 各會重複一次,因此可先計算對角線其中一邊的數值,將數值的總和直接乘二,最終再加上對角線上的 \(aa\) 、 \(bb\) 與 \(cc\)。藉由這種方式,平方運算的成本可由本來的 \(n^2\) 次乘法降為 \((n^2 - n)/2\) 次乘法
結果如下 (v7 藍線)

實作 Karatsuba algorithm
雖然上述 v7 版本所花的時間已略低於參考組,但若將量測範圍逐漸提高,會發現效能仍不及參考組,至 F(100000) 時差距約有 1 倍,觀察 bignum 的原始碼會發現有使用 Karatsuba algorithm 來加速乘法與平方運算,因此接下來一樣實作該演算法來提升效能
Karatsuba algorithm 的核心概念是將 a 與 b 拆分為高位與低位再進行計算,考量計算 \(a\times b\),且 a 與 b 的位數皆為 \(N=2n\) 位 (2 進位下的位數,不過 10 進位時邏輯相同),可將 a 與 b 表示如下
\(a= a_0 + a_1\times 2^n\)
\(b= b_0 + b_1\times 2^n\)
因此 \(a\times b\) 可進一步整理為
\((2^{n}+2^{2n})(a_1b_1) + 2^{n}(a_1-a_0)(b_0-b_1)+(2^{n}+1)(a_0b_0)\)
由於 \(2^n\) 可藉由 bit shift 達成,因此實際使用乘法的部分只剩 3 項,遠少於直接使用乘法的 \(N^2\) 項,可大幅度降低乘法運算的成本
將 Karatsuba multiplication 應用至

bn_mult
與bn_sqr
後,效能如下 (v8 藍線)mutex 對 Linux 核心模組的影響
mutex 可用來確保 critical section (也就是 mutex 圍住的範圍) 內的程式碼同時間只會有一個 thread 可以執行,避免 thread 取用共用的資源時 (shared resource) 的同時,另一個 thread 對該資源進行修改,造成 race conditon
fibdrv 分別在
fib_open
與fib_release
中使用mutex_trylock
及mutex_unlock
將 /dev/fibonacci 上鎖及解鎖,因此同時間只能有一個 user thread 使用此 char device。這點可以藉由簡單的實驗驗證,測試的程式碼如下另外,
fib_read
更改為根據 offset 回傳費氏數列結果可以觀察到第二個 thread 無法成功
open
,因為第一個 thread 已經取得 mutex 了如果將 fibdrv.c 中關於 mutex 的部分移除會造成甚麼後果呢? 以上述的例子而言,反而會使所有 thread 都能正常輸出結果,這是因為本例中的 thread 間沒有共用的資源
那麼 fibdrv 中是否完全不需使用 mutex 呢? 其實還是得根據使用的情境而定,例如下面這個例子,更改為讓所有 thread 共用同個 file descriptor,由於 offset 實際上儲存於該 fd 對應的
struct file
中的f_pos
欄位,因此 offset 會成為共用資源這時就可以觀察到結果會出現錯誤,thread 2 以
lseek
設定好目標 offset 後會休眠 2 秒,但在休眠的期間 thread 1 又更改了 offset,導致 thread 進行read
時使用的 offset 不是當初設定的數值,產生 race condition如何量測模組間的相依性和實際使用次數 (reference counting)
模組間的相依性
在 Linux Device Drivers 中的 The Kernel Symbol Table 小節提到核心模組可以輸出 symbols 來讓其他核心模組使用 (module stacking),不過這樣會產生模組的相依性 (dependency) 關係,也就是說輸出 symbols 的核心模組需要先被掛載,才能供其他模組使用。
/lib/modules/$(uname -r)/modules.dep
的內容來掛載與卸除核心模組接著寫兩個小型核心模組來觀察相依性,首先是輸出 symbol 的
hello_dep1.ko
EXPORT_SYMBOL
將 symbol 輸出至 symbol table__ksymtab
sectioncat /proc/kallsyms | grep 'hello_dep.*'
來觀察EXPORT_SYMBOL
造成的差異,會發現print_hello
的 symbol type 從小寫的't'
變為大寫的'T'
If lowercase, the symbol is usually local; if uppercase, the symbol is global (external).
再來是負責使用 symbol 的
hello_dep2.ko
hello_dep2.ko
直接使用hello_dep1.ko
輸出的print_hello
WARNING: "print_hello" [path/hello_dep2.ko] undefined!
KBUILD_EXTRA_SYMBOLS := .../Module.symvers
將兩者編譯並掛載後,可從
dmesg
觀察到hello_dep2.ko
成功呼叫print_hello
後產生的訊息核心模組的 reference counting (refcnt)
成功掛載
hello_dep2.ko
後,觀察 /sys/module/MODULENAME/refcnt 會發現 refcnt 從 0 變成 1根據核心的說明文件 Unreliable Guide To Hacking The Linux Kernel,可以知道
try_module_get
和module_put()
分別會增加及減少 usage count (refcnt),不過掛載模組時是如何用到這兩個函式呢?掛載模組時 (
insmod
)用
strace
觀察單獨掛載hello_dep2.ko
時的情況,會發現錯誤來自於finit_module
這個步驟,錯誤代碼為ENOENT
,進一步追蹤核心程式碼,可以歸納出以下流程:finit_module
>load_module
>simplify_symbols
(從模組的 ELF 中取出需要尋找的 external symbols) >resolve_symbol_wait
>resolve_symbol
(會調用find_symbol
來尋找該 symbol 屬於哪個核心模組) >ref_module
>strong_try_module_get
>try_module_get
(增加 symbol 所屬的核心模組的refcnt
)註:
try_module_get
實際改變的是struct module
中的 refcnt,在load_module
的過程中會建立與 sysfs 的關係,然後再將模組的相關資訊列出到 sys/module/modulename,在 Module parameters in sysfs 有相關的討論open
device 的時候同樣以 strace 觀察 user space 對 /dev/fibdrv 執行
open
,可以發現實際會執行的 system call 為openat
,一路追蹤核心程式碼,可以歸納出以下流程:openat
>do_sys_openat2
>do_filp_open
(共會嘗試呼叫 3 次path_openat
,第一次會使用LOOKUP_RCU
這個 flag 來開啟) >path_openat
>do_open
(以前稱為 do_last,請參閱 LWN linux-kernel archive) >vfs_open
>do_dentry_open
>fops_get
(增加目標核心模組的 refcnt)fops_get
除了增加 refcnt 之外,主要的目的是從核心模組的 inode 取得 file 的作業方式inode->i_fop
,然後再執行 open 這個動作f->f_op->open
我們知道對 char devices 執行
open
(user space),最終會一同呼叫模組內對應的函式 (定義於模組內struct file_operations
的.open
欄位,例如 fibdrv 中的fib_open
),不過模組的inode->i_fop
是在何時連結至我們定義的struct file_operations
呢? 考量 /dev/fibdrv 這個裝置會在呼叫device_create
後產生,一路觀察相關的核心程式碼:device_create
>device_create_vargs
>device_create_groups_vargs
>device_add
>devtmpfs_create_node
>devtmpfsd
(這是一個 kthread,很像 daemon 的概念) >handle_create
>vfs_mknod
>mknod
(dir->i_op->mknod
會根據檔案系統而有不同的實作) >init_special_inode
init_special_inode
會將inode->i_fop
設為def_chr_fops
,其中.open
的函式為chrdev_open
,也就是說上述dentry_open
中的f->f_op->open
不會直接呼叫模組中定義的函式,而是會先呼叫chrdev_open
,然後chrdev_open
再將核心模組中定義的struct file_operations
取代原本 inode 中的def_chr_fops
lsmod
是如何實作出來的?直接以
strace
觀察lsmod
,可以發現其實是直接列出 /sys/module/module_name 內的資訊,其中 “each module’s use count and a list of referring modules” 的資訊是來自於 holders 這個子目錄使用 sysfs 介面來提供讀寫操作
簡介
sysfs 是 Linux 的一個虛擬檔案系統,提供使用者存取部分核心資料結構的介面 (準確來說是定義於核心內的
struct kobject
物件),可以讓使用者讀取核心資訊或是寫入設定值 (例如 driver 相關設定)。sysfs 通常被掛載於 /sys 目錄下。sysfs 的目錄結構基本上由 kobjects 、 ktypes 、 attributes 和 ksets 構成,要確實了解這個部分還是建議閱讀 Linux Device Drivers 的第 14 章或是核心說明文件 sysfs - The filesystem for exporting kernel objects 與 Everything you never wanted to know about kobjects, ksets, and ktypes。以下將列出部分重點,以便於更快速理解 sysfs 的目錄結構
kobjects
struct kobject
或是內嵌有struct kobject
的資料結構,但很少單獨使用,一般都是內嵌在別的資料結構中使用attributes
struct attribute
的資料結構,例如struct kobj_attribute
.show
和.store
兩個欄位的 callback functions 決定了核心內部的對應行為sysfs_create_file
增加至 kobjects 上的屬性ktypes
struct kobj_type
的物件ktypes
kobject_init_and_add
來創建該 ktype 的 kobjectdynamic_kobj_ktype
.release
指向負責釋放所屬 kobjects 的函式.sysfs_ops
指向一個struct sysfs_ops
,其中的.store
及.shows
欄位分別定義了當使用者讀取或設置 attributions 時 sysfs 會呼叫的 callback funstions.default_attrs
指向一個struct attribute_group
,其中定義了此 ktype 具有的預設 attribute(s).store
及.shows
欄位,當使用者讀取或是設置 attributes 時,呼叫的順序如下dynamic_kobj_ktype
提供給 sysfs 的 callback 是kobj_attr_show
和kobj_attr_store
,其實就是直接呼叫 attributes 中定義的 callback functionsksets
struct kset
的物件新增 fibdrv 在 sysfs 中的存取路徑
接下來會在 fibdrv 中實作專屬的 kobject -
fib_obj
,在 sysfs 中的存取路徑為 /sys/kernel/linux2020/fibdrv,目前只需要一個 attribute -nth
,此 attribute 的用途如下定義 kobject -
fib_obj
第一步當然是定義 fibdrv 專用的 kobject
因為使用自定義的 kobject,需要自定義函數來配置 kobject 所需的記憶體及進行初始化
kobject_init_and_add
,如此一來 kobject 會自動列於該 kset 的目錄下fib_ktype
是自定義的 ktype,後文會說明準備 ktype 所需欄位
.default_attrs
定義 fibdrv 專用的 attribute
定義
fib_attribute
的 callback functionsPAGE_SIZE
,而且使用的格式為字串scnprintf
而不是snprintf
,可參閱 snprintf() confusion接著創建所需的 attribute,待之後定義 ktype 時使用
nth
fib_default_attrs
是之後定義 ktype 時連結於.default_attrs
欄位的資料結構fib_attribute
,這麼做的目的只是為了練習使用自定義 attribute準備 ktype 所需欄位
.sysfs_ops
定義 sysfs 存取 ktype 的 callback functions
container_of
來取出我們自定義的 kobject 與 attribute,再呼叫 attribute 中定義的 callback functions最後準備 ktype 中
.sysfs_ops
欄位所需的部分準備 ktype 所需欄位
.release
kobject 必須動態記憶體,因此需定義釋放的方式。由於使用自定義的 kobject,一樣須搭配使用
container_of
來取得實際的 kobject 指標定義 ktype -
fib_ktype
將上述三個部分組成我們要的 ktype -
fib_ktype
將 kobject 整合至 fibdrv 模組
新增 kobject 相關的部分至 fibdrv 掛載與卸載的函數
init_fib_dev
與exit_fib_dev
kset_create_and_add
使用的參數為kernel_kobj
,代表會將名稱為 "linux2020" 的 kset 置於 /sys/kernel/ 下kobject_put
,否則那些 kobject(s) 就會一直佔據記憶體kobject_put
來減少 kobject 的 refcount,當 refcount 為 0 時,sysfs 就會呼叫 ktype 中.release
欄位的 callback 來清理配置的記憶體實際測試後,
fib_obj
會正確掛載於 /sys/kernel/linux2020/fibdrv,且讀寫操作皆符合預期參考資料
Writing a Linux Kernel Module — Part 1: Introduction
The first 300 Fibonacci numbers, factored
簡介 perf_events 與 Call Graph
tags:
linux 2020