2019q1 Homework2 (fibdrv)

# 2019q1 Homework2 (fibdrv) contributed by < `rebvivi` > ###### tags: `linux2019` * [F03: fibdrv](https://hackmd.io/s/SJ2DKLZ8E#F03-fibdrv) ### Reviewed by `flawless0714` - 請將本共筆最後提到的問題(放到 kernel 後無法正常輸出)所使用的程式碼(client.c, fibdrv.c...etc)放到共筆或更新到 GitHub 上嗎？想研究一下，感謝！ - 編輯器使用的設定檔資料夾(.vscode/)可以加入 `.gitignore` 以保持專案的一致性 - `fibdrv.c` 中的 MAX_LENGTH 記得調大，不然 `lseek()` 會被限制將 fd 的 offset 卡在 92，造成 fibonacci 的計算限制 - [`client.c`](https://github.com/rebvivi/fibdrv/blob/61357b57878ebcccf02ce1027cf95f26bdd0d650/client.c#L56)中 `%lld` 應改為 `%llu`，不然 MSB 為 1 時會讓輸出變負數 > 已經補上傳程式碼了~ [name=rebvivi] > > 找到問題點了，有點驚訝...，kernel space 的 array of struct 在配置記憶體時不會讓裡面的成員有連續的記憶體位置，所以當你使用 `copy_to_user()` 時，一次給定 16 bytes 就會違法存取 kernel 中的記憶體。目前想到的解決方法為另外宣告一個 `struct U64` 以得到有連續記憶體位置的 struct。原本以為同學你說計算結果沒辦法傳到 `client.c` 只是傳不出來或結果有問題之類，結果是 kernel panic...，第一次測試我用實體機測試，東西都還沒關，直接母湯:cry:。以下為測試時用的程式碼及 dmesg 的輸出： > > ```clike > > static long long fib_sequence(long long g, char *buf, size_t size) > > { > > unsigned long long a; > > a = 10000000000000000000; > > struct U64 fib[g + 1], tmp = {0}; > > memset(fib, 0, sizeof(struct U64) * (g + 1)); > > > > int k; > > fib[0].lsl = 1; > > fib[1].lsl = 1; > > for (k = 2; k <= g; k++) { > > fib[k].lsl = fib[k - 1].lsl + fib[k - 2].lsl; > > fib[k].msl = fib[k - 1].msl + fib[k - 2].msl; > > if (fib[k].lsl > a) { > > fib[k].lsl = fib[k].lsl - a; > > fib[k].msl = fib[k].msl + 1; > > } > > } > > tmp = fib[g - 1]; > > printk("Valid memory address range is at least from %p to %p\n" > > "Address of `fib[g - 1].msl` is %p, whereas address of `fib[g - 1].lsl` is %p\n" > > "Address of tmp.msl is %p, whereas tmp.lsl is %p", > > &fib[g - 2], &fib[g].lsl, &fib[g - 1].msl, &fib[g - 1].lsl, &tmp.msl, &tmp.lsl); > > copy_to_user(buf, &tmp, size); > > return 1; > > } > > ``` > > ``` > > [ 2555.395975] Valid memory address range is at least from 00000000ee12084d to 00000000d0e2865f > > Address of `fib[g - 1].msl` is 00000000c59a48c4, whereas address of `fib[g - 1].lsl` is 00000000c4c3f823 > > Address of tmp.msl is 0000000096237fec, whereas tmp.lsl is 000000002435e6b7 > > ``` >謝謝你~已經可以成功印到fib(92)以上了 [name=rebvivi] > > 不會不會，我也上了一課! > > [name=flawless0714] > > > 想請問 `flawless0714` 為何 Valid memory address range 是設定在 `&fib[g - 2]` 和 `&fib[g - 1].msl` 之間？為何定義一個 `tmp` 就能確保在有效範圍？ > > > [name=Laurora] > > > > 大家抱歉，剛剛發現我的測試不完整且有問題(已更新程式碼與輸出)，我昨天在 user space 測試完 array of struct 的記憶體是連續後就篤定 kernel space 中只對 array of struct 配置不連續的記憶體，而沒有繼續檢查下去，但剛剛發現就連另外宣告的 non-array of struct 的 `tmp` 也有成員記憶體位置不連續的情況。所以現在用 `tmp` 去餵給 `copy_to_user()` 時，其實也使用了不連續的記憶體，這樣目前就無解了...，因為現在 `copy_to_user()` 複製的記憶體是 `0x0000000096237fec ~ (0x0000000096237fec + 16D - 1)`，但是 `tmp` 的第二個成員的記憶體位置卻是從 `0x000000002435e6b7` 開始，這樣沒有 kernel panic 就怪了。目前推測是跟 logical address 有關，查資料中！ > > > > [name=flawless0714] > > > > > trace 了 kernel panic 前的 log 資料(如下)，推測了可以觸發 `BUG()` 的點，但有段==看不太懂==，不知道其他同學有沒有什麼看法。log 中提及 `BUG()` 位於 [`usercopy.c:72`](https://elixir.bootlin.com/linux/v4.15.18/source/mm/usercopy.c#L72)，所以我去研究 [`copy_to_user()`](https://elixir.bootlin.com/linux/v4.15.18/source/include/linux/uaccess.h#L152) 的實做，其中有段 [code](https://elixir.bootlin.com/linux/v4.15.18/source/mm/usercopy.c#L35) 是在驗證欲複製的記憶體，然後有兩個部份會讓回傳值為 `BAD_STACK` (造成 `BUG()` 的原因)，第一個是位於 `check_stack_object()` `#L50` 在確保 `obj` (這邊是我們的 `&fib[g - 1] ~ (&fib[g - 1] + 16bytes - 1)`) 是否位於 stack 中，==第二個是同個函數的 `#L54`，不太懂他的功能(`Check if object is safely within a valid frame`)跟 `#L50` 的差別在哪==，目前推測後者比較可能是觸發點，因為 `&fib[g - 1]` 是 function call 的 local var，這點可以保證他的記憶體位於 stack 中，而且餵給 `copy_to_user()` 的 size 也沒有超過單個 struct size。 > > > > > ``` > > > > > [ 4167.013170] usercopy: kernel memory exposure attempt detected from 00000000e7ee16e5 (<process stack>) (16 bytes) > > > > > [ 4167.013177] ------------[ cut here ]------------ > > > > > [ 4167.013178] kernel BUG at /build/linux-7kdHqT/linux-4.15.0/mm/usercopy.c:72! > > > > > [ 4167.013183] invalid opcode: 0000 [#1] SMP PTI > > > > > ``` > > > > > [name=flawless0714] > > > > > > 找到真正原因了..，問題是出在 `g=0` 的時候，`g=0` 會讓 `copy_to_user` 拿到 `fib[-1]` 的位置，然後在檢查複製內容時發現這是非法存取而觸發 `BUG()`。而當使用 `tmp` 去裝 `fib[-1]` 時則沒有被檢查，所以沒有 panic，另外測試後發現 `tmp` 可以偷到 stack frame (16KB on x86_64) 內的資料，但假如沒有把偷到的資料使用 `copy_to_user` 傳送則可以拿到任何 offset 的資料(測試過最少可以拿到 -312 byte 個 offset 的資料)，這感覺不算 bug，因為這 driver 本身就沒有 signature 了(tainted kernel)。更詳細的討論可以參考[這裡](https://www.ptt.cc/bbs/LinuxDev/M.1553628544.A.D7C.html)。 > > > > > > [name=flawless0714] --- ## 作業要求 - 回答「自我檢查清單」的所有問題，需要附上對應的參考資料和必要的程式碼，以第一手材料 (包含自己設計的實驗) 為佳 - 在 GitHub 上 fork fibdrv，目標是改善 fibdrv 計算 Fibinacci 數列的執行效率，過程中需要量化執行時間，可在 Linux 核心模組和使用層級去測量 * 在 Linux 核心模組中，可用 ktime 系列的 API * 在 userspace 可用 clock_gettime 相關 API * 分別用 gnuplot 製圖，分析 Fibonacci 數列在核心計算和傳遞到 userspace 的時間開銷，單位需要用 us 或 ns (自行斟酌) * 嘗試解讀上述時間分佈，特別是隨著 Fibonacci 數列增長後，對於 Linux 核心的影響 * 原本的程式碼只能列出到 Fibonacci(100)，請修改程式碼，列出更後多數值 (注意: 檢查正確性和數值系統的使用) - 逐步最佳化 Fibonacci 的執行時間，引入費氏數列提到的策略，並善用 clz / ctz 一類的指令，過程中都要充分量化 ## 自我檢查清單 1. 檔案 `fibdrv.c` 裡頭的 `MODULE_LICENSE`, `MODULE_AUTHOR`, `MODULE_DESCRIPTION`, `MODULE_VERSION` 等巨集做了什麼事，可以讓核心知曉呢？ `insmod` 這命令背後，對應 Linux 核心內部有什麼操作呢？請舉出相關 Linux 核心原始碼並解讀 2. 當我們透過 `insmod` 去載入一個核心模組時，為何 `module_init` 所設定的函式得以執行呢？Linux 核心做了什麼事呢？ 3. 試著執行 `$ readelf -a fibdrv.ko`, 觀察裡頭的資訊和原始程式碼及 `modinfo` 的關聯，搭配上述提問，解釋像 `fibdrv.ko` 這樣的 ELF 執行檔案是如何「植入」到 Linux 核心 4. 這個 `fibdrv` 名稱取自 Fibonacci driver 的簡稱，儘管在這裡顯然是為了展示和教學用途而存在，但針對若干關鍵的應用場景，特別去撰寫 Linux 核心模組，仍有其意義，請找出 Linux 核心的案例並解讀。提示: 可參閱 Random numbers from CPU execution time jitter 5. 查閱 ktime 相關的 API，並找出使用案例 (需要有核心模組和簡化的程式碼來解說) 6. clock_gettime 和 High Resolution TImers (HRT) 的關聯為何？請參閱 POSIX 文件並搭配程式碼解說 7. `fibdrv` 如何透過 Linux Virtual File System 介面，讓計算出來的 Fibonacci 數列得以讓 userspace (使用者層級) 程式 (本例就是 `client.c` 程式) 得以存取呢？解釋原理，並撰寫或找出相似的 Linux 核心模組範例 8. 注意到 `fibdrv.c` 存在著 `DEFINE_MUTEX`, `mutex_trylock`, `mutex_init`, `mutex_unlock`, `mutex_destroy` 等字樣，什麼場景中會需要呢？撰寫多執行緒的 userspace 程式來測試，觀察 Linux 核心模組若沒用到 mutex，到底會發生什麼問題 9. 許多現代處理器提供了 clz / ctz 一類的指令，你知道如何透過演算法的調整，去加速費氏數列運算嗎？請列出關鍵程式碼並解說 --- - [ ] 檔案 `fibdrv.c` 裡頭的 `MODULE_LICENSE`, `MODULE_AUTHOR`, `MODULE_DESCRIPTION`, `MODULE_VERSION` 等巨集做了什麼事，可以讓核心知曉呢？ `insmod` 這命令背後，對應 Linux 核心內部有什麼操作呢？請舉出相關 Linux 核心原始碼並解讀 - `MODULE_LICENSE`：讓 kernel 知道 device driver 的授權方式 >如果一個 module 没有授權，那麼很多需要授權的函式會因此不能使用 >如果 module 授權錯誤，會導致 module 在 run 或是 load 的錯誤 ```cpp MODULE_LICENSE("Dual MIT/GPL"); ``` - `MODULE_LICENSE`：用來宣告 module 的作者 ```cpp MODULE_AUTHOR("National Cheng Kung University, Taiwan"); ``` - `MODULE_DESCRIPTION`：描述這個 module 的功用跟簡介 ```cpp MODULE_DESCRIPTION("Fibonacci engine driver"); ``` - `MODULE_VERSION`：描述 module 的版本 ```cpp MODULE_VERSION("0.1"); ``` - `insmod`：用於將給定的 module 載入到 kernel 中 >Linux 有許多功能是通過 module 的方式，在需要時才載入 kernel，可以讓 kernel較為精簡，進而提高效率 >module 載入的時候會呼叫 init_fib_dev 當使用 `insmod fibdrv.ko` 時，會自動的呼叫到 init_fib_dev 這個 function ```cpp module_init(init_fib_dev); ``` --- - [ ] 當我們透過 `insmod` 去載入一個核心模組時，為何 `module_init` 所設定的函式得以執行呢？Linux 核心做了什麼事呢？ >我們在`fibdrv.c` 引入標頭檔 `<linux/init.h>` ```clike #include <linux/init.h> ``` >在 <linux/init.h> 中定義如下: >>`__attribute__`: 讓我們定義函數的行為，以便告訴 gcc 在編譯時期對此函式做一些特殊的處理或檢查動作 >`alias` : 定義 init_module 爲函數 initfn 的別名 ```cpp #ifndef MODULE #define module_init(x) __initcall(x); #else #define module_init(initfn) \ int init_module(void) __attribute__((alias(#initfn))); #endif ``` >module_init(init_fib_dev) 的作用就是定義一個變量名 init_module，其地址和 init_fib_dev 是一樣的 ```cpp module_init(init_fib_dev); ``` 在寫 module 的時候有兩個特殊的函數，分別是init_module和cleanup_module，這兩個函數分別在insmod的時候和rmmod的時候調用，並且insmod和rmmod只識別這兩個特殊的函數當我們給的 initfn (init_fib_dev) 定義一個別名 init_module，這樣insmod 就能夠執行我們的 initfn (init_fib_dev) --- - [ ] 試著執行 `$ readelf -a fibdrv.ko`, 觀察裡頭的資訊和原始程式碼及 `modinfo` 的關聯，搭配上述提問，解釋像 `fibdrv.ko` 這樣的 ELF 執行檔案是如何「植入」到 Linux 核心 * 作業一開始在 terminal 輸入 `$ modinfo fibdrv.ko`，得到輸出： ``` filename: /home/peiwen/fibdrv/fibdrv.ko version: 0.1 description: Fibonacci engine driver author: National Cheng Kung University, Taiwan license: Dual MIT/GPL srcversion: 24DC5FB7E7608AF16B0CC1F depends: retpoline: Y name: fibdrv vermagic: 4.18.0-15-generic SMP mod_unload ``` * 執行`$ readelf -a fibdrv.ko`的時候，總共有 25 個區段標頭，在編號 14 的區段標頭可以找到 modinfo：`[14] .modinfo` >objdump：可以根據目的檔案來生成可讀性比較好的彙編檔 >objdump --section：可以顯示指定section的完整內容 * 我們利用 `$ sudo objdump --section=.modinfo -s fibdrv.ko`看 fibdrv.ko 中 modinfo 的內容，發現跟我們輸入`$ modinfo fibdrv.ko`的結果相同 >`.modinfo` : 被 modinfo 命令用來顯示關於核心模組的資訊，該區段中儲存的資料不會載入kernel address space ``` fibdrv.ko：檔案格式 elf64-x86-64 Contents of section .modinfo: 0000 76657273 696f6e3d 302e3100 64657363 version=0.1.desc 0010 72697074 696f6e3d 4669626f 6e616363 ription=Fibonacc 0020 6920656e 67696e65 20647269 76657200 i engine driver. 0030 61757468 6f723d4e 6174696f 6e616c20 author=National 0040 4368656e 67204b75 6e672055 6e697665 Cheng Kung Unive 0050 72736974 792c2054 61697761 6e006c69 rsity, Taiwan.li 0060 63656e73 653d4475 616c204d 49542f47 cense=Dual MIT/G 0070 504c0000 00000000 73726376 65727369 PL......srcversi 0080 6f6e3d32 34444335 46423745 37363038 on=24DC5FB7E7608 0090 41463136 42304343 31460000 00000000 AF16B0CC1F...... 00a0 64657065 6e64733d 00726574 706f6c69 depends=.retpoli 00b0 6e653d59 006e616d 653d6669 62647276 ne=Y.name=fibdrv 00c0 00766572 6d616769 633d342e 31382e30 .vermagic=4.18.0 00d0 2d31352d 67656e65 72696320 534d5020 -15-generic SMP 00e0 6d6f645f 756e6c6f 61642000 mod_unload . ``` * 輸入`$ sudo objdump --section=.gnu.linkonce.this_module -s fibdrv.ko`，我們看到 module 名稱 `fibdrv` >` .gnu.linkonce.this_module`：含有一個 module 結構，其中包含了模組的名字，還有些別的欄位，輸入 insmod 的時候，system call init_module() 會從這個特殊區段，將該結構 module 讀入動態記憶體的區塊 ``` fibdrv.ko：檔案格式 elf64-x86-64 Contents of section .gnu.linkonce.this_module: 0000 00000000 00000000 00000000 00000000 ................ 0010 00000000 00000000 66696264 72760000 ........fibdrv.. 0020 00000000 00000000 00000000 00000000 ................ 0030 00000000 00000000 00000000 00000000 ................ 0040 00000000 00000000 00000000 00000000 ................ 0050 00000000 00000000 00000000 00000000 ................ 0060 00000000 00000000 00000000 00000000 ................ 0070 00000000 00000000 00000000 00000000 ................ 0080 00000000 00000000 00000000 00000000 ................ 0090 00000000 00000000 00000000 00000000 ................ 00a0 00000000 00000000 00000000 00000000 ................ 00b0 00000000 00000000 00000000 00000000 ................ 00c0 00000000 00000000 00000000 00000000 ................ 00d0 00000000 00000000 00000000 00000000 ................ 00e0 00000000 00000000 00000000 00000000 ................ 00f0 00000000 00000000 00000000 00000000 ................ 0100 00000000 00000000 00000000 00000000 ................ 0110 00000000 00000000 00000000 00000000 ................ 0120 00000000 00000000 00000000 00000000 ................ 0130 00000000 00000000 00000000 00000000 ................ 0140 00000000 00000000 00000000 00000000 ................ 0150 00000000 00000000 00000000 00000000 ................ 0160 00000000 00000000 00000000 00000000 ................ 0170 00000000 00000000 00000000 00000000 ................ 0180 00000000 00000000 00000000 00000000 ................ 0190 00000000 00000000 00000000 00000000 ................ 01a0 00000000 00000000 00000000 00000000 ................ 01b0 00000000 00000000 00000000 00000000 ................ 01c0 00000000 00000000 00000000 00000000 ................ 01d0 00000000 00000000 00000000 00000000 ................ 01e0 00000000 00000000 00000000 00000000 ................ 01f0 00000000 00000000 00000000 00000000 ................ 0200 00000000 00000000 00000000 00000000 ................ 0210 00000000 00000000 00000000 00000000 ................ 0220 00000000 00000000 00000000 00000000 ................ 0230 00000000 00000000 00000000 00000000 ................ 0240 00000000 00000000 00000000 00000000 ................ 0250 00000000 00000000 00000000 00000000 ................ 0260 00000000 00000000 00000000 00000000 ................ 0270 00000000 00000000 00000000 00000000 ................ 0280 00000000 00000000 00000000 00000000 ................ 0290 00000000 00000000 00000000 00000000 ................ 02a0 00000000 00000000 00000000 00000000 ................ 02b0 00000000 00000000 00000000 00000000 ................ 02c0 00000000 00000000 00000000 00000000 ................ 02d0 00000000 00000000 00000000 00000000 ................ 02e0 00000000 00000000 00000000 00000000 ................ 02f0 00000000 00000000 00000000 00000000 ................ 0300 00000000 00000000 00000000 00000000 ................ 0310 00000000 00000000 00000000 00000000 ................ 0320 00000000 00000000 00000000 00000000 ................ 0330 00000000 00000000 00000000 00000000 ................ ``` * 我們利用 `insmod` 來將 `fibdrv.ko` 值入 linux kernel ，輸入 `$ dpkg -L linux-headers-4.18.0-15-generic | grep "/lib/modules"`，以確認 linux-headers 套件已正確安裝於開發環境，並且注意 linux kernel 的版本要與 `fibdrv.ko` 一致 >得到的結果如下： ``` /lib/modules/4.18.0-15-generic/build ``` --- - [ ] 這個 `fibdrv` 名稱取自 Fibonacci driver 的簡稱，儘管在這裡顯然是為了展示和教學用途而存在，但針對若干關鍵的應用場景，特別去撰寫 Linux 核心模組，仍有其意義，請找出 Linux 核心的案例並解讀。提示: 可參閱 Random numbers from CPU execution time jitter 電腦在計算亂數的時候，希望每次計算都得到不同的結果，所以我們常常拿每次新產生出來的數值作為下一次計算的依據，這就是為什麼計算機隨機數大部分都會表示成遞迴定義的數列 >這是一般的 Fibonacci 數列 ```cpp f[0] = 0; f[1] = 1; f[i] = f[i - 1] + f[i - 2]; ``` >數列呈現單調遞增 ```cpp 1, 1, 2, 3, 5, 8, 13, 21, ... ``` >如果我們強迫 Fibonacci 數列的數值超出 100 之後折回來 ```cpp f[0] = 0; f[1] = 1; f[i] = (f[i - 1] + f[i - 2]) % 100; ``` >一開始雖然還是看得到規則，不過整體趨勢已經不再是單調遞增，當數值折回之後規律變得不太明顯 ```cpp 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 44, 33, 77, 10, 87, 97, 84, 81, 65, 46, 11, 57, 68, 25, 93, 18, 11, 29, 40, ... ``` >甚至我們可以將 Fibonacci 的遞迴數列改成: ```cpp f[0] = 18; f[1] = 83; f[2] = 4; f[3] = 42; f[4] = 71; f[i] = (f[i - 2] + f[i - 5]) % 100; ``` >這個數列的規則已經非常不容易看穿 ```cpp 18, 83, 4, 42, 71, 60, 54, 64, 96, 35, 56, 89, 20, 85, 55, 41, 44, 61, 29, 16, 70, 60, 31, 89, 47, 59, 7, 90, 96, 37, ... ``` 這種產生隨機數的方法，稱為 Lagged Fibonacci ，是電腦產生隨機數的一種方法 --- - [ ] 查閱 ktime 相關的 API，並找出使用案例 (需要有核心模組和簡化的程式碼來解說 --- - [ ] clock_gettime 和 High Resolution Timers (HRT) 的關聯為何？請參閱 POSIX 文件並搭配程式碼解說 - `clock_gettime`：用來取得程式的 CPU time，是POSIX 的 High Resolution Timer 之一，精確度可以達到 nanosecond，其所回傳的時間是用 timespec 這個 struct 所儲存 >第一個 parameter `clock_id`分別可以設定成 `clockid_t` 型態 >>`CLOCK_REALTIME`：`clockid_t` 型態的一種，是系統實際的時間 ```clike int clock_gettime (clockid_t clock_id, struct timespec *tp); ``` >函式會將計時器的值儲存成 timespec 的型態，會將時間值分為 second 及 nanosecond 兩部分 ```clike struct timespec { time_t tv_sec; /* seconds */ long tv_nsec; /* nanoseconds */ }; ``` --- - [ ] `fibdrv` 如何透過 Linux Virtual File System 介面，讓計算出來的 Fibonacci 數列得以讓 userspace (使用者層級) 程式 (本例就是 `client.c` 程式) 得以存取呢？解釋原理，並撰寫或找出相似的 Linux 核心模組範例 - `Virtual File System (VFS)` ：負責提供一套統一的檔案系統介面，供 user space 使用 - 基本的 driver，都會實作 open 與 close 等等的 handler，也就是 user 在操作裝置檔做的 open 以及 close 等等的動作，定義 system call 界面給 user space 使用 - `System call`： user space 與 Linux device driver 的溝通界面 - 透過 `Virtual File System (VFS)`可讓同一套`System call`在不同的檔案系統上使用，讓不同檔案系統可以用一致的方式存取 > 在`client.c` 中，我們利用 open 和 close 的 system call 來存取 kernel 裡頭 `fibdrv.c` 中計算出來的 Fibonacci 數列 ```cpp #include <unistd.h> #define FIB_DEV "/dev/fibonacci" int main() { ... fd = open(FIB_DEV, O_RDWR); ... close(fd); } ``` >以下是 linux driver 基本的架構： :::warning 依據指定風格進行程式碼縮排。 :notes: jserv ::: ```clike #include <linux/fs.h> #include <linux/init.h> #include <linux/kernel.h> #include <linux/module.h> static ssize_t drv_read(struct file *filp, char *buf, size_t count, loff_t *ppos) { printk("device read\n"); return count; } static ssize_t drv_write(struct file *filp, const char *buf, size_t count, loff_t *ppos) { printk("device write\n"); return count; } static int drv_open(struct inode *inode, struct file *filp) { printk("device open\n"); return 0; } int drv_ioctl(struct inode *inode, struct file *filp, unsigned int cmd, unsigned long arg) { printk("device ioctl\n"); return 0; } static int drv_release(struct inode *inode, struct file *filp) { printk("device close\n"); return 0; } struct file_operations drv_fops = { read : drv_read, write : drv_write, ioctl : drv_ioctl, open : drv_open, release : drv_release, }; #define MAJOR_NUM 60 #define MODULE_NAME "DEMO" static int demo_init(void) { if (register_chrdev(MAJOR_NUM, "demo", &drv_fops) < 0) { printk("<1>%s: can't get major %d\n", MODULE_NAME, MAJOR_NUM); return (-EBUSY); } printk("<1>%s: started\n", MODULE_NAME); return 0; } static void demo_exit(void) { unregister_chrdev(MAJOR_NUM, "demo"); printk("<1>%s: removed\n", MODULE_NAME); } module_init(demo_init); module_exit(demo_exit); ``` >之後我們只要在 user space 使用read、write、ioctl、open、release 這些 system call 便能使用這個 driver --- - [ ] 注意到 `fibdrv.c` 存在著 `DEFINE_MUTEX`, `mutex_trylock`, `mutex_init`, `mutex_unlock`, `mutex_destroy` 等字樣，什麼場景中會需要呢？撰寫多執行緒的 userspace 程式來測試，觀察 Linux 核心模組若沒用到 mutex，到底會發生什麼問題 - `mutex`:用於 multithreading，讓同一時間有且僅有一個 thread 可以獲取某段 code - `DEFINE_MUTEX`:靜態定義和初始化一個 mutex - `mutex_trylock`:嘗試鎖定 mutex ，成功返回 0，否則返回飛零值 - `mutex_init`:動態初始化一個 mutex - `mutex_unlock`:解鎖 mutex - `mutex_destroy`:可以銷毀與 mutex pointer 所指向的 mutex 相關聯的任何狀態。用來存儲該 mutex 的空間不會釋放 --- - [ ] 許多現代處理器提供了 clz / ctz 一類的指令，你知道如何透過演算法的調整，去加速費氏數列運算嗎？請列出關鍵程式碼並解說 - Fast Doubling 有以下關係式： F(2n)=F(n)[2F(n+1)-F(n)] F(2n+1)=F(n+1)^2^+F(n)^2^ - 假設我們要求 F(11)，11~10~=1011~2~ * 因為我們是用 `unsigned long long`總共 64-bits 來表示輸入的 n ，所以如果我們求第 11 個數字，所輸入的 n 會是 0x000000000000000B，n 的前面會有許多 0 ，如果考慮進去會增加無謂的計算 * 我們利用 clz 去求 n 用 2 進位表示的位數，去除 msb 之前不必要的 0，指針由 msb 開始一路指到 lsb 去做判斷： * 指針指到的是 1：則先求 F(2n) 和 F(2n+1)，再求 F(2n+2) * 指針指到的是 0：則求 F(2n) 和 F(2n+1) | | 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 ```cpp static unsigned long long fib_sequence(unsigned long long g) { unsigned long long n = 0, x; x = g; if ((x & 0x00000000FFFFFFFF) == 0) { n += 32; x <<= 32; } if ((x & 0x0000FFFFFFFFFFFF) == 0) { n += 16; x <<= 16; } if ((x & 0x00FFFFFFFFFFFFFF) == 0) { n += 8; x <<= 8; } if ((x & 0x0FFFFFFFFFFFFFFF) == 0) { n += 4; x <<= 4; } if ((x & 0x3FFFFFFFFFFFFFFF) == 0) { n += 2; x <<= 2; } if ((x & 0x7FFFFFFFFFFFFFFF) == 0) { n += 1; } g <<= n; unsigned long long a = 0; unsigned long long b = 1; unsigned long long t1 = 0; unsigned long long t2 = 0; int i; for (i = 0; i < 64 - n; i++) { t1 = a * (2 * b - a); t2 = a * a + b * b; if ((g & 0x8000000000000000) == 0) { a = t1; b = t2; } else { a = t2; b = t1 + t2; } g <<= 1; } return a; } ``` >以下是利用 clz 在加上 Fast Doubling ，以 O(logn) 計算 fib_sequence 所測得的執行時間 > ![](https://i.imgur.com/Z5PLwsZ.png) ## Fibonacci 數列的執行效率 >以下是用老師一開始給的 `fibdrv.c` 所測得的執行時間 >我們可以很明顯看到在 user 以及 kernel 的執行時間都呈現 O(n)，而 kernel to user 則呈現 O(1) ![](https://i.imgur.com/7xyCUVO.png) 沿用老師一開始給的 `fibdrv.c`，在`client.c`中，將 Fib(n) 的輸入數值 n 改成： 1~100 的範圍中，隨機取 100 個數字，但彼此都不重複 ```cpp int rand_num[100]; int i, j, k; srand(time(NULL)); for (i = 0; i < 100; i++) { rand_num[i] = rand() % 100; for (j = i - 1; j >= 0; j--) if (rand_num[i] == rand_num[j]) i--; } for (i = 0; i < offset; i++) { struct timespec start, end; lseek(fd, rand_num[i], SEEK_SET); clock_gettime(CLOCK_REALTIME, &start); sz = read(fd, buf, 128); clock_gettime(CLOCK_REALTIME, &end); fprintf(fp, "%d %d %lld %lld\n", rand_num[i], diff_in_ns(start, end), atoll(buf), diff_in_ns(start, end) - atoll(buf)); printf("Reading from " FIB_DEV " at offset %d, returned the sequence " "%lld.\n", rand_num[i], sz); } ``` >雖然大致 user 以及 kernel 的上升趨勢都呈現 O(n)，kernel to user 呈現 O(1)，但是會比最佳輸入的情況，也就是 n 是 1~100 依序遞增輸入的情況下，多出許多 peak > ![](https://i.imgur.com/bIN53CQ.png) >以下是用 O(logn) 的 fib_sequence 所畫出來的圖，但 logn 的趨勢沒有很明顯，我推論是因為 size 的數量還不夠大，所以還看不出 logn 的趨勢 >但是和一樣是 O(logn)，用 clz 及 Fast Doubling 的 fib_sequence 呈現相似的圖形趨勢 > :::warning 注意 Fib(n) 的輸入數值，如果是遞增的話，那麼就會遇到演算法的最佳狀況，進而得到很短的時間。應當改變 for 迴圈的行為，將輸入數值變成一定範圍內的亂數，並且取出特定的信賴區間 :notes: jserv ::: ```cpp static long long fib_sequence(long long n) { long long i,h,j,k,t; i = h = 1; j = k = 0; while (n > 0) { if(n&1){ t=j*h; j=i*h + j*k +t; i=i*k + t; } t=h*h; h=2*k*h + t; k=k*k + t; n=(long long) n/2; } return j; } ``` :::info `(n % 2 == 1)` 可改為 `(n & 1)` :notes: jserv ::: ![](https://i.imgur.com/WueU0V9.png) ==遇到的問題== >以下的 fib_sequence 在 user space 都能夠成功印出 fib(92)以上的值 ```cpp #include <limits.h> #include <stdio.h> #include <stdlib.h> struct U64 { unsigned long long msl; unsigned long long lsl; }; struct U64 fib_sequence(unsigned long long g) { unsigned long long a; a = 10000000000000000000; struct U64 fib[g + 1]; int i, j, k; for (i = 0; i < g + 2; i++) { fib[i].lsl = 0; fib[i].msl = 0; } fib[0].lsl = 1; fib[1].lsl = 1; for (k = 2; k <= g; k++) { fib[k].lsl = fib[k - 1].lsl + fib[k - 2].lsl; fib[k].msl = fib[k - 1].msl + fib[k - 2].msl; if (fib[k].lsl > a) { fib[k].lsl = fib[k].lsl - a; fib[k].msl = fib[k].msl + 1; } } return fib[g - 1]; } int main() { unsigned long long n; n = 100; fib_sequence(n); for (n = 91; n <= 100; n++) printf("%lld\t%llu%llu \n", n, fib_sequence(n).msl, fib_sequence(n).lsl); } ``` >以下是輸出 ``` 91 04660046610375530309 92 07540113804746346429 93 12200160415121876738 94 19740274219868223167 95 31940434634990099905 96 51680708854858323072 97 83621143489848422977 98 135301852344706746049 99 218922995834555169026 100 354224848179261915075 ``` >但如果將 fib_sequence 放在 kernel ，用 `copy_to_user` 將數值傳到 user，就無法順利印出 fib(92) 以上的值，沒有辦法成功將數值傳到 `client.c` ```cpp struct U64 { unsigned long long msl; unsigned long long lsl; }; static long long fib_sequence(long long g, char *buf, size_t size) { unsigned long long a; a = 10000000000000000000; struct U64 fib[g + 1]; memset(fib, 0, sizeof(struct U64) * (g + 1)); int k; fib[0].lsl = 1; fib[1].lsl = 1; for (k = 2; k <= g; k++) { fib[k].lsl = fib[k - 1].lsl + fib[k - 2].lsl; fib[k].msl = fib[k - 1].msl + fib[k - 2].msl; if (fib[k].lsl > a) { fib[k].lsl = fib[k].lsl - a; fib[k].msl = fib[k].msl + 1; } } copy_to_user(buf, &fib[g - 1], size); return 1; } ```