參考資料繁多,僅用以紀錄自己瀏覽狀況
/dev/fibonacci
裝置檔案來變更不同的 Fibonacci 求值的實作程式碼。步驟皆 follow 文件
首先檢查 kernel 版本
確認 linux-headers
套件已經正確安裝於開發環境
預期輸出
檢查目前使用者身份,避免使用 root
安裝工具
util-linux
(utility linux)dpkg -l
列出以安裝的包clone fibdrv 並嘗試編譯測試
在 f(93)
的時候 fail
了
編譯時會產生 .ko
檔案,此為 kernel object 檔案,可以使用 modinfo(8) 查看 kernel module 的資訊
預期輸出
掛載進去
用 dmesg(1) 可以看到相關資訊
1
是硬連結數root
為擁有者 (user) 和所屬群組 (group)509
是文件大小chatGPT 給的解釋
在 ls -l
命令的輸出中,如果一個文件的大小為 0,那麼第五欄的數字就會是 0。如果文件的大小不為 0,那麼第五欄的數字就代表該文件的大小,表示該文件佔用了多少字節的磁盤空間。
而在 ls -l
命令的輸出中,第一欄的第一個數字是用來表示該文件的類型的,例如普通文件、目錄、符號鏈接、設備文件等。在 Linux 系統中,設備文件是一種特殊的文件,用來表示硬體設備。設備文件的第一個數字通常是 0,表示這是一個設備文件。
因此,如果一個文件的第一個數字是 4,這表示這是一個目錄文件。如果一個文件的第一個數字是 0,這表示這是一個設備文件,其大小可能為 0,也可能不為 0,具體取決於該設備的容量。因此,同時出現 4 和 0 的情況,代表這是一個目錄文件,並且其中一些條目是設備文件。
在重新 make check
之前要 sudo rmmod fibdrv
舉例來說
Recursive 實作 (Python)
可得:
且遞迴過程縮減,如下
此時再次利用 和遞迴 時所得到的 來計算 ,可以再次降低運算的次數
透過 clz/ctz 搭配 fast doubling
a = 0b1000
, ffs(a)=4
a = 0b1010
, ffs(a)=2
a = 0b1011
, ffs(a)=1
0
-> fast doubling,求 和 1
-> fast doubling,求 和 ,相加後求 求解 (1110 = 10112)
1 | 0 | 1 | 1 | result | |
---|---|---|---|---|---|
F(n) | F(0*2+1) | F(1*2) | F(2*2+1) | F(5*2+1) | F(11) |
a | 1 | 1 | 5 | 89 | 89 |
b | 1 | 2 | 8 | 144 |
1
,計算 以及 、相加後求得 0
,計算 以及 1
,計算 以及 、相加後求得 1
,計算 ,計算 ,相加得 範例: 計算
target
數值越大,重複的計算效能衝擊越顯著。以 8710 為例:
移項並反過來看
這邊感謝 Eroiko 的筆記 幫助很大。
測試結果如同作業說明及二補數計算,在返回值為 long long
的情況下 會造成 overflow
二補數計算
引入 bn
結構體,計算 92 項以後的費氏數列
number
- 指向儲存的數值,之後以 array 的形式來取用size
- 配置的記憶體大小,單位為 sizeof(usigned int)
sign
- 0 為 正數,1 為負數由於大數沒辦法直接以數值的形式列出,故改用字串來做呈現,轉換部份利用 ASCII 特性並搭配 fast doubling 的邏輯來組合出 10 進位
Trace 其運作流程
首先宣告一指標 fib
指向 bn
結構體,並分配空間
bn_alloc
bn_alloc
會使用 kmalloc
分配 bn
大小的空間,kmalloc
和 vmalloc
都用以分配核心的記憶體空間,但 kmalloc
會分配連續的虛擬以及實體地址,但 vmalloc
只保證連續的虛擬地址,不保證連續的實體地址, kernel 中常用 kmalloc
因為使用 vamlloc
需要進行映射 (mapping) 會讓效能變差GFP_KERNEL
is typical for kernel-internal allocations. The caller requires ZONE_NORMAL
or a lower zone for direct access but can direct reclaim.ZONE_DMA
、ZONE_NORMAL
和 ZONE_HIGHMEM
)接下來將分配好空間的 bn
結構體 fib
以及要計算的 費式數透過 bn_fib_fdoubling
計算
bn_fib_fdoubling
bn_add
為例bn_add
(c = a + b
)
sign
判斷 a, b
正負號是否相等,如果相等相加過後輸出的正負號會相同,交由 bn_do_add
負責運算,且設定 c
符號相同a, b
符號不同,則透過比較正負號使 a
大於 b
,再來判斷絕對值數值的大小,這會影響相加後結果的正負,例如
a = -100, b = 10
,做 swap
使得 a = 10, b = -100
,透過比較絕對值後進行運算得到結果為負的 |b| - |a|
a = 100, b = -10
,不會做 swap
且運算的結果為正的 |a| - |b|
a, b
不同號, 且 |a| = |b|
,則輸出為 0
實作判斷可以如下表格所示 (a, b
不同號,且 a
> b
)
Condition | ||
---|---|---|
Output c |
bn_do_add
bn_msb
會回傳傳入的 bn
結構體中所有 array 儲存的資料的 leading zero 有幾個,取較多的那個 + 1 就會是相加後最多有幾個 digits (進位)bn_resize
會將最終結果 c
resize 成 d
的大小,代表著需要幾個 unsigned int *number
去儲存相加後的結果假設結構體為 uint8_t
為例,若 a = 0b11111111 = 255
,b = 0b10000001 = 129
我們想要獲得的答案為 0b 1 10000000 = 384
,但只有 8 bit 的話無法表達,所以會輸出會用兩個 uint8_t
數值的陣列表示
bn_do_sub
同樣的,在 bn_do_sub
中,輸出 c
最大的 digit 數為 兩個 digit 數高的那個 (不發生借位),計算 carry
值,若兩數值相減後 msb 還是 1
的話,代表發生借位,會將 c->number[i]
的值設定為 carry + (1LL << 32)
,這邊的 (1LL << 32)
看起來是要把第 32 bit (含) 以上的都設定為 0 (但實測後不做這件事情可以正確計算)
這裡的判斷是否借位可改寫成
一樣可以正確計算 Fibonacci number
bn_sub
這裡的 bn_sub
可以偷過 bn_add
來實作,因 bn
結構為 unsigned int
的 number 陣列,由另外的 sign
元素決定其正負,若要執行 bn_sub
,可以透過反轉 b 的 sign
元素再進行 bn_add
即可
bn_mult
實作一般直式長乘法,用輔助函式 bn_mult_add
負責將每一行的計算結果疊加上去,假設 number
為 4 bit,a=0b0111 0111 (size=2), b=0b0101 0101 (size=2)
計算過程如下
bn_lshift
此處實作先僅限於移動 32 bit 以內,函式內用一個 bitwise or |
來處理跨越 number
之間的 bit shift
bn_to_string
上述實作中關鍵的程式碼為
1
,則輸出乘二加一0
,則輸出乘二參考 AdrianHuang/fibdrv 實作程式碼
以數字陣列來儲存(同時也可以指定陣列大小),以 uint8_t
為例,其數值範圍在 0~255,若要表示 300 則以數字陣列 digit
來表示,假設陣列大小為 3,則 300 表示為
然後在透過 format.c 格式轉換為十進位
可以透過以下兩種演算法實現大數的乘法
bn_fib_fdoubling
直接引入 Reference 竟然報錯
查看 out
檔案發現計算的值有很大的問題
在尚未優化的版本中, bignum 版本和正常版本的運算可以直接對應
不支援大數的 fast doubling iteration
支援大數的 fast doubling iteration
f1
也就是傳入的 dest
而此改善方案旨在降低使用 malloc
及 memcpy
的次數,首先新的 bn_lshift_2
可以將第一個引數 src
左移第二個引數 shift
後儲存至第三個引數 dest
bn_lshift_2
函式修改
結果在測試時還是錯誤
檢查過後發現在 bn_mult
中當資料來源與目的沒有重疊時,並沒有將其 number
初始化,以至於產生非預期的取值,之前沒有發現是因為在 bignum 的 fast-doubing 版本中使用 bn_mult
的案例都屬於 (c == a || c == b)
修正完成後此節改善方案可通過測試。
參考網站 所提供的 fast doubling 方法如下
左右欄對調
可以將第一欄取出為
列對調
觀察 sysprog21/bignum 中費氏數列的實作函式 fibonacci,會發現雖看似採用 fast doubling,但實際是 Q-matrix 這樣的變形,推導如下:
整理後可得
使用上述公式改寫 bn_fib_fdoubling
,搭配使用 clz
,後者可讓 n 值越小的時候,減少越多次迴圈運算,從而達成加速。
原本在實作中在計算前會使用 bn_resize
來確保有足夠的空間儲存計算結果 (number 的數量),而現在引入 capacity
的方式來管理 bn
的可用大小,減少 bn_resize
呼叫 realloc
的次數。
size
超過 capacity
時才會 realloc
,並以 4 為單位size
作為範圍,不必計算多餘的空間realloc
來縮小空間This article is focused on the system configuration, tools and code required to build and deploy a “Hello World!” kernel module.
Loadable kernel module (LKM) 是一個在 Linux kernel run time 下新增、移除程式的機制。這樣使得 kernel 無須知道硬體是如何運作的便可以使 kernel 和 硬體進行通訊 (ideal for device drivers!)
如果沒有這個東西的話, Linux kernel 將會非常的龐大,且要更新 hardware driver 的話每次都要重新建構 kernel。 LKM 的缺點就是每個 device 的 driver 都需要被 maintain
LKMs 是在 runtime 被加載的,但並不是在 user space 運行。
Kernel modules 在 kernel space 運行,Application 在 user space 運行
在嵌入式 Linux 中利用 sysfs
以及低階 (low-level) 檔案操作來與電子電路進行互動,這樣的方法非常沒有效率。但是,這樣的方法在各種應用程式上已經足夠 (原文提供證明)。
而替代方案就是使用支援中斷 (interrupt) 的 kernel module,但 kernel code 是非常編寫和除錯的。
在寫測試 LKMs 時是非常容易 crash system 的,是有可能損壞檔案系統的,若有需要就要備份
一般典型的電腦程式在 runtime life cycle 非常直觀。 loader 分配記憶體給程式,然後載入任何需要的 libraries。 指令執行的起始點通常東在 main()
,然後接著執行、回報錯誤、例外狀況,分配動態記憶體,然後最終運行完成。在程式離開時,作業系統會將 memroy leaks 以及沒有 free 乾淨的 memory 丟到 pool 中。
但 kernel module 沒有這些東西,且沒有 main()
function!
以下是一些主要區別:
printf()
函式: kernel code 無法訪問 (access) user space 的 libraries。kernel module 在 kernel space 生成及執行,有自己的 memory address space, kernel space 和 user space 的界面 (interface) 被明確定義,但確實有一個 printk()
函數可以輸出 information,且可以在 user space 查看ChatGPT 給的解釋
Character Device 是指一種在 Unix/Linux 系統中的設備類型,該設備對外提供了一個字符(Character)流的接口,用於與其他軟件或硬件進行通信。一些例子包括終端設備(如 tty)、滑鼠、鍵盤、語音輸入、音訊裝置等。
Character Device 與另一種設備類型 Block Device 不同。Block Device 是指提供塊(Block)訪問方式的設備,例如硬碟驅動器,其將數據劃分為固定大小的塊(通常為512位元組或4KB),用於高效地存儲和讀取數據。
在 Linux 系統中,Character Device 和 Block Device 均被視為一種特殊的檔案,可以使用文件描述符(File Descriptor)對其進行讀寫操作。Character Device 提供了一種簡單的、無緩衝的 I/O 模型,允許使用者以字節為單位進行讀寫操作。相較之下,Block Device 的 I/O 模型則更複雜,需要進行塊緩存、讀寫計劃等操作,以達到更高的性能。
Character decive 一般在 user application 收送資料,就像是 pipes 或 serial ports,立即讀寫 character-by-character stream 中的位元組資料。為典型的驅動軟體提供框架,連接 serial communcations、video capture、audio devices,其主要的替代品是 block device, block device 的行為和常規的文件相似,允許透過讀取、寫入、查找等等操作來查看或操作 buffered array of cached data
這兩種 device types 都可以被 attached 到 file system tree 的 device file 來 access
本文提供了一個運行在 linux kernel space 下,且可以讓 Linux user-space program 和 loadable kernel module (LKM) 之間 pass information 的 character driver,本例中, C user-space application 發送一段 string 給 LKM,然後 LKM 會回傳其收到的字節數。接著解釋為何要解決同步的問題 (本文透過 mutex lock 解決)
Device drivers 有一個 major 和 minor 號碼, major number 是 kernel 在當這個 device 被 accessed 時用來識別正確的 device driver,而 minor number 取決於 device,並在驅動程式內部處理
如果是 character deviceds ,首欄字母為 c
,如果是 block device,首欄字母為 b
,接下來就是常見的 access permission, owner, grops.
可以手動建立 block 或 character device,例如 sudo mknod /dev/test c 92 1
,但是這個方法必須確認 92
這個數字沒有被使用
file_operations
的 data structure 定義於/linux/fs.h
,內部結構包含 function pointer 並允許設計人員定義以下操作。
__randomize_layout
標示可參考 Linux Kernel之randomized layout,其目的在於增強 kernel 的安全性這個 driver 提供了 read
, write
, open
, release
等 system call file operation,如果沒有實作的話,那麼這些 function pointer 會指向 NULL
本節原文以 BeagleBone 做為舉例,但其架構可從 fibdrv 找到相對應的 init()
、 exit()
,以及 file_operations
等等實作,其中
dev_open()
: Called each time the device is opened from user space.dev_read()
: Called when data is sent from the device to user space.dev_write()
: Called when data is sent from user space to the device.dev_release()
: Called when the device is closed in user space.llseak()
: Change current read/write position in a file
lseek(int __fd, off_t __offset, int __whence)
,控制檔案的讀寫位置,引數 __offset
根據引數 __whence
來移動讀寫位置的位移數, __whence
可以是以下其中一種:
SEEK_SET
: 引數 __offset
即為新的讀寫位置SEEK_CUR
: 以目前的讀寫位置往後增加 __offset
個位移量SEEK_END
: 將讀寫位置指向檔案未端後在增加 __offset
個位移量fibdrv.c
中的 fib_device_lseek
有對應的實作在 user space 呼叫 read()
函式時,是無法直接指定文件 offset 的,文件的偏移量是和 file descriptor 的屬性,只能透過呼叫 lseek()
函式或其他類似的 system call 來修改,故若要指定文件偏移量,需在讀取文件之前使用 lseek()
設定偏移量,然後在呼叫 read()
函式進行讀取,例如 client.c
中的作法
在原文的留言處有提到
devnull: You should add “.owner = THIS_MODULE,” in struct file_operations fops or you will get nasty kernel oopses when unloading or rebooting. Took me 2 weeks to find out.
可以發現有些東西是在 user-level 運作的
查看 client.c
上述這段 code 會用系統呼叫 open
打開 device file /dev/fibonacci
,其中也使用了 open
、write
、lseek
、read
等系統呼叫來對 fibonacci
進行操作,操作之後就可以從 kernel 讀取出之前運算出來的 fibonacci 數值,然後就可以在 user space 中進行輸出
client.c
read
系統呼叫來得到輸出查看 fibdrv.c
(參考 物件導向程式設計篇 (designated initializers)、file_operations Struct Reference)
fib_read
宣告為 static
(表示其能見度只有在該檔案),但在 fib_fops
被初始化成 read
function pointer,所以之後只要操作該 function pointer,就會像是在操作 fib_read
,且可以避免命名衝突這裡實作了 fib_read
函數內將 fib_sequence
的值回傳,透過使用者給定不同的 offset
作為 Fibonacci 數列的 回傳
在傳統 UNIX 系統中,檔案系統是固定的,但是在 Linux 中,為了結合各個檔案系統,因而加上了一層虛擬檔案系統 (VFS), VFS 是一組檔案操作的抽象界面,可以將任何真實的檔案系統透過 VFS 掛載到 Linux 中。
VFS 並不直接處理檔案格式,而是規定這些處理請求的介面及操作語意,然後交由真實的檔案系統 (像是 EXT2) 去處理。
而透過 VFS, fibdrv
核心模組可以將計算出來 Fibonacci 數讓 client.c
程式得以存取
Linux 的裝置驅動程式大致分為:
在 Makefile
中,make check
會去加載編譯好的 fibdrv
kernel module,並將 client
輸出儲存至 out
,透過以下指令
來檢驗輸出和預期是否一樣,在第一版本的 fibdrv
中僅能輸出正確的
在和目標檔案 expected.txt
比對時會給 pass
,因為 expected.txt
本來就給定這樣的預期輸出,若要檢測後續的 Fibonacci number 是否正確則連同 expected.txt
也要一起改
copy_[to/from]_user
fops->read
、fops->write
、fops->ioctl
這三個 system call 有關不論是從 user-space 讀取資料至 kernel-space,或是將 kernel-space 的資料寫至 user-space, 必須透過 kernel 提供的兩個 API 來進行
long copy_tp_user(void *to, const void * from, long n)
long copy_from_user(void *to, const void* from, long n)
copy_to_user
to
: 資料的目的位置 (指向 user-space 記憶體的指標)from
: 資料的來源位址 (指向 kernel-space 記憶體的指標)copy_from_user
to
: 資料的目的位置 (指向 kernel-spcae 記憶體的指標)from
: 資料的來源位置 (指向 user-space 記憶體的指標)Kernel 裡面有 copy_to_user,可以把資料從 kernel space copy 到 user space
copy_to_user
其實是有成本的如果只在 user space 做測量,那就只能測量進出 kernel 內部的時間,測量不到 kernel 內部,進出 kernel 其實有其他的成本開銷 (例如 mode switch)
這時候就需要用到 hrtimer
(high-resolution timer),在 linux 上的通常可以達到 1 micro second 的精準度
jiffies
是一種計時機制,計算自開機以來計時器中斷發生的次數,較舊的 Linux 核心有提到 timer wheel,而一個新的機制是將計時機制建立在新資料結構 ktime_t
上
client.c
根據作業說明描述,在 user-mode 的位置配置一個 buffer 空間時, kernel driver 不能直接寫入該地址,而是要透過 copy-to-user,將想傳給 user-mode (運作中的 client) 的字串複製到 fib_read
的 buf
參數後, client
方可接收此字串
而 Hierarchical performance measurement and modeling of the Linux file system 研究指出,從 kernel-level 複製資料到 user-level 的時間成本是每位元組 22ns,故在進行效能分析時,必須要考慮到 copy_to_user 函式的時間開銷,特別留意資料大小成長後造成的量測誤差
參考Linux 效能分析的提示、KYG-yaya573142,使用 processor affinity / CPU pinning 讓行程在特定的 CPU 中執行不受排程的干擾
也可以使用 perf record
來取樣並紀錄目標的執行狀態
-g
回同時紀錄取樣點的 stack trace--call-graph
指定走訪 stack trace 的方法 follow The DWARF Debugging Standardmake load
載入 module修改 /etc/default/grub
內的 GRUP_CMDLINE_LINUX_DEFAULT
,加入 isolcpus=7
來指定編號 7
的核心 不被排程器賦予任務,修改完成後 sudo update-grub
來更新設定
quiet
: 啟動系統的過程中,如果沒有 quiet
, kernel 就會輸出很多訊息,包括啟動過程中運行了哪些程式,如果系統可以正常啟動,通常就不會需要這些訊息,故會設定成 quiet
splash
: 與可視化界面有關GRUB_CMDLINE_LINUX
: 一直生效GRUB_CMDLINE_LINUX_DEFAULT
: 恢復模式 (recovery mode) 下不會運作以我的電腦來說,會將 performance
分別寫入
參考 CPU frequency scaling,會讓 CPU 在最高頻率下運轉
POSIX Threads 是一套符合 POSIX 標準的 API,方便開發者設計出 User-level 的多執行緒程式。
在 linux/unistd.h 中提供了 POSIX 作業系統 API 的存取功能標頭檔名稱。通常為大量的 system call。
在可移植性方面,符合 POSIX 標準的 API 其函數名稱、返回值、參數類型等等都按照標準定義,而 POSIX 相容也就指定這些接口 (interface) 函式相容,但是並不管 API 具體如何實現
利用 strace
簡單測試一個 printf
到底呼叫了哪些 system call
line 37
中 write
system call 把字符串 Hello!
傳給 file descriptor 1 的設備stdout
首先程式運行時第一個 tread 負責運行 main()
,建立一個以上的執行緒則使用 pthread_create ,而執行緒完成工作後很多種結束的方法
The new thread terminates in one of the following ways:
- It calls pthread_exit(3), specifying an exit status value that is available to another thread in the same process that calls pthread_join(3).
- It returns from start_routine(). This is equivalent to calling pthread_exit(3) with the value supplied in the return statement.
- It is canceled (see pthread_cancel(3)).
- Any of the threads in the process calls exit(3), or the main thread performs a return from main(). This causes the termination of all threads in the process.
如果不使用 pthread_join
,該執行緒會繼續佔用資源直到 process 結束。
pthread_create
thread
: 指向 pthread_t
結構體的指標attr
: 設定 thread 的 attribute,如果設定 attr
為 NULL ,則這個 thread 使用 default attributesstart_routine
: 這個 thread 會 invoke start_routine()
arg
會作為 start_routine
的引數#PF
代表 page fault,當 page fault 發生時,CPU 會將相關的錯誤訊息除存在 error code
的特殊暫存器中 (32bit value) supervisor write access in kernel mode
: 可能發生的原因包含
在多執行緒的預期流程,insmode
-> 多執行緒進行 hash table 的查表、填表 -> 結束運算,走訪 hash table 並釋放空間 -> rmmod
lkmpg 4.3 The __init and __exit Macros
The __exit macro causes the omission of the function when the module is built into the kernel, and like __init , has no effect for loadable modules. Again, if you consider when the cleanup function runs, this makes complete sense; built-in drivers do not need a cleanup function, while loadable modules do.
void