contributed by < Tonr01 >
自從 Linux 核心 4.4 版以來,Ubuntu Linux 預設開啟 EFI_SECURE_BOOT_SIG_ENFORCE,這使得核心模組需要適度的簽章才可掛載進入 Linux 核心,為了後續測試的便利,我們需要將 UEFI Secure Boot 的功能關閉,請見 Why do I get “Required key not available” when install 3rd party kernel modules or after a kernel upgrade?
首先先關閉 UEFI Secure Boot
檢查 Linux 核心版本
安裝 linux-headers
套件
確認 linux-headers
套件已正確安裝於開發環境,預期得到以下輸出:
檢驗目前的使用者身份
檢驗測試過程所需 sudo
編譯並測試
預期會看到綠色的 Passed [-]
字樣,隨後是
fibdrv.c
的標頭檔錯誤直接將檔案從 clone 後,用 vscode 開啟,會有標頭檔錯誤,這裡參考 Shiritai 的方法。
首先先確認 Linux 核心版本。
再確認 Linux kernel header,確認其安裝的路徑,可移動至 /usr/src 下查看。
再確認 gcc version
最後 IntelliSense 需要調整 C/C++ Extension 設定檔,在 vscode 界面按下 f1,輸入 Edit configuration (UI),就能編輯 IntelliSense 組態,詳細改動放在 commit。
改動完, 就無 error message 了
How to develop Linux Kernel Module with vscode without incorrect error detection
An IntelliSense Bug When Coding Linux Kernel Module
費氏數列分析
你所不知道的C語言:遞迴呼叫篇 - Fibonacci sequence
這個「公式解」一般認為由 Jacques P. M. Binet 在 1843 年發現,仍可追溯得更早。習慣上我們仍稱之為 Binet 等式 (Binet’s Formula)
大多數的迷思認為這是最快的解法,為 的公式解,但對於電腦的離散本質會有幾個問題
sqrt(5)
之後,只能用一個近似的值來表達結果,其誤差會在 n 值變大時慢慢放大。可運用 GMP 或 MPFR 這這兩個 GNU 函式庫是所謂的「無限」位數的整數跟「無限」精確度的浮點數,可參考 Fibonacci 快速解程式碼與公式解程式碼 實作
主要透過矩陣轉換之方法,我們把原本之遞迴式轉換到矩陣表示,並透過矩陣次方之Divide and Conquer Method 來做加速,解說短片: The Fibonacci Q-matrix。
Fast Doubling 為 Q-matrix 的改良版,主要再細分成兩種情況, n 為奇數或偶數的情況,可以降低遞迴次數,
這裡參考 Fast Doubling 的手法,先用 63 - __builtin_clzl(k)
去找出不包含 leading 0s 的真正數字,再用 bit-mask 的方式取檢驗目前 bit 為0或1。
以 k = 50
為例,其二進位表示為
round | k | mask | k & mask | odd/even |
---|---|---|---|---|
1 | 110010 | 100000 | 100000 | odd |
2 | 110010 | 010000 | 010000 | odd |
3 | 110010 | 001000 | 000000 | even |
4 | 110010 | 000100 | 000000 | even |
5 | 110010 | 000010 | 000010 | odd |
6 | 110010 | 000001 | 000000 | even |
可以輸出正確到 Fib(92)
這裡引入 ktime_t 來測量輸出上一次 fib 的執行時間,先使用老師的參考範例來測試,因為 fib_write
未使用,所以使用這個函式計算時間。
再不影響原本的 client.c
,這裡多加入了一個新的使用者模式,叫做 runtime.c
,主要用來輸出時間的資料,並修改 Makefile
來執行程式,詳細改動在 commit,將輸出的時間資料用 gnuplot 去繪製圖片。
將 fib_sequence
改善成可以切換不同的實作。
並將 fib_write
改善成可以同時計算及輸出其 runtime。
在 runtime.c
中將兩種實作的 runtime 輸出到 txt 檔,方便圖的繪製,詳細改動在 commit。
參考初步支援大數運算,這邊引入 KYG-yaya573142 的實作來研究。
bn
首先是結構體的部份,number
指向數值的部份,在後續使用會以陣列的方式存放數值,size
則是大數的記憶體大小,也就是陣列的大小,陣列的大小為 number[size]
,sign
存放的是數值的正負。
bn_clz
大數版本的 clz
,主要用來計算 leading zero 的個數。
bn_to_string
因大數無法以數值的形式表示,故需要將其轉成字串,len
存放大數的 bit 個數,迴圈將二進位字串轉換成十進位字串。
bn_add
, bn_sub
加法的部份,首先要先判斷兩個大數的正負是否相同,相同的話直接加起來即可,若正負不同時,因為大數的結構體是將數值跟正負號的部份分開存放,所以要先判斷兩個數值的大小,做相減的動作,其結果在加上正負號。
這裡用 DIV_ROUNDUP
來計算 c
的所需大小,其大小會滿足所需大小而不過於太多,使用 8 bytes 大小的 carry
來實行兩個 4 bytes 項目的加法來避免 overflow,因為每個 array 大小為 4 bytes,所以當相加完,carry
扣除右邊 4 bytes ,其餘都是進位的值,所以每回合 carry>>32
。
因為減法不會有 overflow 的問題,所以不須用 DIV_ROUNDUP
,這裡是做無號數減法,carry
與加法的不同,這裡是作為向前一位的借位,當相減的值小於 0 ,才須向前一位借位,最後在調整 c
的所需大小,將不需要的 0 去掉。
再來是減法的部份,因為 ,所以先將負號給 b
,但是不能改變 b
的值,所以宣告 tmp
給予改變後的 b
值,最後將 a
與 tmp
做加法即可。
bn_mult
乘法採用簡單的 long multiplication ,若 c == a || c == b
,就必須配置記憶體來儲存計算結果,避免 a
與 b
在計算途中就被改變。
bn_mult_add
主要處理乘法運算時,每回合的計算結果累加。
bn_lshift
, bn_rshift
主要做大數左移,這裡只考慮最多位移 31 bits 的情形,當 shift
大於 leading zero 個數時,會超出原本的大小限制,所以須將 size + 1
,在重新配置記憶體大小。
dest->number[0] = src->number[0] << shift;
這行就是因為當超出原本大小時,可能會有 overflow 的問題,所以須將多出來的部份在放到最一開始新增的位置。
與左移類似,只考慮最多位移 31 bits 的情形,當 shift
大於 leading zero 個數時,則表示原本的 number[0]
的數值以全部右移到下一個陣列,故須重新調整大小,扣除不需要的空間。
Todo