# 2019q1 Homework2 (fibdrv) contributed by < `Zames-Chang` > :::danger 注意依循指定的格式，細節很重要 :notes: jserv ::: ## 對於費氏數列的加速運算 ### 使用矩陣運算加速費氏數列 先講結論 假設 $Q =\begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}$ $Q^n = \begin{pmatrix} F_{n + 1} & F_n \\ F_ n & F_{n - 1} \end{pmatrix}$ 為啥會是這樣呢？ 首先 $F(N) = F(N-1) + F(N-2)$ ### 然後數學歸納法 #### 檢查初始狀態是否為真 $Q =\begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix} =\begin{pmatrix} F_{2} & F_1 \\ F_ 1 & F_0 \end{pmatrix}$ #### 假設在n時對的n+1也要對 $Q^n = \begin{pmatrix} F_{n + 1} & F_n \\ F_ n & F_{n - 1} \end{pmatrix}$ 是對的 那 $Q^{n+1} = \begin{pmatrix} F_{n + 2} & F_{n+1} \\ F_ {n+1} & F_{n} \end{pmatrix}$ 也是對的 $Q =\begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}$ $Q^{n+1} = Q^nQ$ $Q^{n+1} = \begin{pmatrix} F_{n + 2} & F_{n+1} \\ F_ {n+1} & F_{n} \end{pmatrix} = \begin{pmatrix} F_{n + 1} & F_n \\ F_ n & F_{n - 1} \end{pmatrix}\begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix} \\= \begin{pmatrix} F_{n + 1} + F_{n} & F_{n} + F_{n-1} \\ F_{n} + F_{n-1} & F_{n} \end{pmatrix}$ #### 得證 [參考自](http://fedelebron.com/fast-modular-fibonacci) ### 透過矩陣的特性 if $m = \left\lfloor \frac{n}{2} \right\rfloor$ $Q^n = \begin{cases} \left(Q^m\right)^2 & \textrm{ if } n \equiv 0 \pmod {2},\\ \left(Q^m\right)^2 Q & \textrm { if } n \equiv 1 \pmod{2} \end{cases}$ 透過這個特性，原本只要的 `fib(K)` 為$O(K)$就會變成$O(log_2K)$ #### 以下為實現 ```c= /* *把兩個矩陣相乘並把結果存回第一個矩陣身上 */ static void matrix_mut(long long m[2][2],long long n[2][2]) static long long fib_sequence_boost(long long k) { /* FIXME: use clz/ctz and fast algorithms to speed up */ if(k == 0) return 0; long long f[2][2] = { {1,1}, {1,0} }; long long base_f[2][2] = { {1,1}, {1,0} }; int stack[100]; int stack_ptr = -1; /* 我可以將一個數字轉換成全是+1或是*2的計算 * 假設我要計算 Q^50 = Q^(25*2) * = Q^(24+1)*2 = Q^((12*2)+1)*2 * = Q^((6*2*2)+1)*2 = Q^((3*2*2*2)+1)*2 * = Q^((1+2)*2*2*2)+1)*2 * = Q^(((1+(1+1))*2*2*2)+1)*2 * 把要做的operation的順序以 0 跟 1 做紀錄 */ while(k > 1){ if(k % 2 == 1){ k = k-1; stack_ptr++; stack[stack_ptr] = 0; } else{ k = k / 2 ; stack_ptr++; stack[stack_ptr] = 1; } } /* * 計算 Q^50 = Q^(25*2) * = Q^((1+2)*2*2*2)+1)*2 * 現在就是將這段計算實際算出來 */ for(int i=stack_ptr ;i>=0;i--){ if(stack[i] == 0){ matrix_mut(f,base_f); } else{ matrix_mut(f,f); } } return f[0][1]; // f(k) } ``` 使用boost版本的fib_sequence ```c= #define USE_BOOST true static ssize_t fib_read(struct file *file, char *buf, size_t size, loff_t *offset) { return (USE_BOOST) ? fib_sequence_boost(*offset) : fib_sequence(*offset); } ``` ### 單元測試 #### client.c 將結果輸出至 fib.txt ```c= fp = fopen("fib.txt", "w+"); for (i = 0; i <= offset; i++) { lseek(fd, i, SEEK_SET); sz = read(fd, buf, 1); fprintf(fp, "%lld\n", sz); printf("Reading from " FIB_DEV " at offset %d, returned the sequence " "%lldd.\n", i, sz); } ``` #### fib_unit_test.py 使用 python 去確認是否$F(N) = F(N-1) + F(N-2)$ ```python with open("fib.txt", "r") as f : content = f.readlines() content = [int(x.strip()) for x in content] if(content[0] != 0 and content[1] != 1): print("error at f(0) or f(1)") exit(0) for i in range(2,93): ans = content[i-1] + content[i-2] if(ans != content[i]): print("wrong at",i) exit(0) print("every thing rigth when k <= 92") ``` ### 結果 `every thing rigth when k <= 92` ### 速度的比較 #### 使用 boost 版本的 `fib_sequence` ```c= static long long fib_sequence_boost(long long k) { long long t = k; ktime_t ktime = ktime_get(); ... ktime = ktime_sub(ktime_get(), ktime); long long s = (long long) ktime_to_ns(ktime); printk("k = %lld using %lld ns\n",t,s); return f[0][1]; } ``` 以下為在我電腦的實驗結果(近似一個 $O(log_{2}N)$ 的曲線） ![](https://i.imgur.com/Luw2E20.png) #### 普通版本的 `fib_sequence` ```c= static long long fib_sequence(long long k) { ktime_t ktime = ktime_get(); /* FIXME: use clz/ctz and fast algorithms to speed up */ long long f[k + 2]; f[0] = 0; f[1] = 1; for (int i = 2; i <= k; i++) { f[i] = f[i - 1] + f[i - 2]; } ktime = ktime_sub(ktime_get(), ktime); long long s = (long long) ktime_to_ns(ktime); printk("k = %lld using %lld ns\n",t,s); return f[k]; } ``` 在我的電腦實驗(近似一個 $O(N)$ 的曲線） ![](https://i.imgur.com/oRvHGuH.png) #### 衍生議題 * 為啥在boost版本中有時候有時候在n比較低的時候會比較慢呢？ ## 自我檢查清單 ### 檔案 `fibdrv.c` 裡頭的 `MODULE_LICENSE`, `MODULE_AUTHOR`, `MODULE_DESCRIPTION`, `MODULE_VERSION` 等巨集做了什麼事，可以讓核心知曉呢？ #### linux/module.h 在原始碼中，這4個 macro 其實都是在 call 同一個 macro ，只是將不同的 flag 與其資訊帶入`MODULE_INFO` ```c= #define MODULE_LICENSE(_license) MODULE_INFO(license, _license) #define MODULE_AUTHOR(_author) MODULE_INFO(author, _author) /* What your module does. */ #define MODULE_DESCRIPTION(_description) MODULE_INFO(description, _description) #define MODULE_VERSION(_version) MODULE_INFO(version, _version) ``` #### linux/module.h `MODULE_INFO`其實又是去 call `__MODULE_INFO` ```c= #define MODULE_INFO(tag, info) __MODULE_INFO(tag, tag, info) ``` #### linux/moduleparam.h 在 moduleparam.h 中終於找到`__MODULE_INFO` ```c= #define __MODULE_INFO(tag, name, info) \ static const char __UNIQUE_ID(name)[] \ __used __attribute__((section(".modinfo"), unused, aligned(1))) \ = __stringify(tag) "=" info ``` 然後我們來看看 __UNIQUE_ID 在幹嘛 ```c= __UNIQUE_ID(prefix) __PASTE(__PASTE(__UNIQUE_ID_, prefix), __LINE__) ``` 繼續 DFS ，然後我們來看看 __PASTE 在幹嘛，基本上就是把 a,b 在 proprocess 時 concat 起來 ```c= #define ___PASTE(a,b) a##b #define __PASTE(a,b) ___PASTE(a,b) ``` **註解: a##b = concat(a,b) in C macro** [參考來源](https://stackoverflow.com/questions/26576201/what-does-a-b-mean-in-c) 理解完之後，就會發現 `__UNIQUE_ID(prefix)` 這段`code = __UNIQUE_ID_ + prefix　+ __LINE__ ` ```c= __UNIQUE_ID(prefix) __PASTE(__PASTE(__UNIQUE_ID_, prefix), __LINE__) ``` 所以其實這段看似複雜的code可以理解成，`static const char xxxx[] = "xxxxxxx"` ```c= #define __MODULE_INFO(tag, name, info) \ static const char __UNIQUE_ID(name)[] \ __used __attribute__((section(".modinfo"), unused, aligned(1))) \ = __stringify(tag) "=" info ``` 也就說這些macro做的事情其實就是把module的相關資訊以特定格式的字串放在heap區 ```c= #define MODULE_LICENSE(_license) MODULE_INFO(license, _license) #define MODULE_AUTHOR(_author) MODULE_INFO(author, _author) /* What your module does. */ #define MODULE_DESCRIPTION(_description) MODULE_INFO(description, _description) #define MODULE_VERSION(_version) MODULE_INFO(version, _version) * `insmod` 這命令背後，對應 Linux 核心內部有什麼操作呢？請舉出相關 Linux 核心原始碼並解讀 ``` ### 當我們透過 `insmod` 去載入一個核心模組時，為何 `module_init` 所設定的函式得以執行呢？Linux 核心做了什麼事呢？ module_init經過一連串macro轉換後 `module_init(fn)—> __initcall(fn) —> device_initcall(fn) —> __define_initcall(fn, 6)` ```c= #define __define_initcall(fn, id) \ static initcall_t __initcall_##fn##id __used \ __attribute__((__section__(“.initcall” #id “.init”))) = fn ``` 可以轉換為`static initcall_t __initcall_fn6 __used __attribute__((__section__(“.initcall””6” “.init”))) = fn` 到這邊就可以大致猜到，linux把你的function pointer放到heap區，並註冊成linux module [參考自](https://codertw.com/%E7%A8%8B%E5%BC%8F%E8%AA%9E%E8%A8%80/474266/) ### 試著執行 `$ readelf -a fibdrv.ko`, 觀察裡頭的資訊和原始程式碼及 `modinfo` 的關聯，搭配上述提問，解釋像 `fibdrv.ko` 這樣的 ELF 執行檔案是如何「植入」到 Linux 核心 `$ insmod` 會去 call `init_module` 這個system call，以下為`init_module` manpage ``` int init_module(void *module_image, unsigned long len, const char *param_values); ``` *The paramvalues argument is a string containing space-delimited specifications of the values for module parameters (defined inside the module using moduleparam() and moduleparamarray()). The kernel parses this string and initializes the specified parameters. Each of the parameter specifications has the form:* `name[=value[,value...]]` 對應到 modinfo ``` filename: /home/zames/workspaces/jserv/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 看看索引名稱，這不就是`MODULE_LICENSE`, `MODULE_AUTHOR`, `MODULE_DESCRIPTION`, `MODULE_VERSION`註冊的 `static char __UNIQUE_ID_xxx[]` ``` 編號: 值 大小 類型 約束 版本 索引名稱 29: 0000000000000000 12 OBJECT LOCAL DEFAULT 14 __UNIQUE_ID_version26 30: 000000000000000c 36 OBJECT LOCAL DEFAULT 14 __UNIQUE_ID_description25 31: 0000000000000030 46 OBJECT LOCAL DEFAULT 14 __UNIQUE_ID_author24 32: 000000000000005e 21 OBJECT LOCAL DEFAULT 14 __UNIQUE_ID_license23 ``` * 這個 `fibdrv` 名稱取自 Fibonacci driver 的簡稱，儘管在這裡顯然是為了展示和教學用途而存在，但針對若干關鍵的應用場景，特別去撰寫 Linux 核心模組，仍有其意義，請找出 Linux 核心的案例並解讀。提示: 可參閱 [Random numbers from CPU execution time jitter](https://lwn.net/Articles/642166/) [linux source](https://github.com/torvalds/linux/blob/master/crypto/jitterentropy.c) ```c= /* * Fibonacci LSFR with polynom of * x^64 + x^61 + x^56 + x^31 + x^28 + x^23 + 1 which is * primitive according to * http://poincare.matf.bg.ac.rs/~ezivkovm/publications/primpol1.pdf * (the shift values are the polynom values minus one * due to counting bits from 0 to 63). As the current * position is always the LSB, the polynom only needs * to shift data in from the left without wrap. */ ec->data ^= data; ec->data ^= ((ec->data >> 63) & 1); ec->data ^= ((ec->data >> 60) & 1); ec->data ^= ((ec->data >> 55) & 1); ec->data ^= ((ec->data >> 30) & 1); ec->data ^= ((ec->data >> 27) & 1); ec->data ^= ((ec->data >> 22) & 1); ec->data = jent_rol64(ec->data, 1); ``` * 查閱 [ktime 相關的 API](https://www.kernel.org/doc/html/latest/core-api/timekeeping.html)，並找出使用案例 (需要有核心模組和簡化的程式碼來解說) * [clock_gettime](https://linux.die.net/man/2/clock_gettime) 和 [High Resolution TImers (HRT)](https://elinux.org/High_Resolution_Timers) 的關聯為何？請參閱 POSIX 文件並搭配程式碼解說 * `fibdrv` 如何透過 [Linux Virtual File System](https://www.win.tue.nl/~aeb/linux/lk/lk-8.html) 介面，讓計算出來的 Fibonacci 數列得以讓 userspace (使用者層級) 程式 (本例就是 `client.c` 程式) 得以存取呢？解釋原理，並撰寫或找出相似的 Linux 核心模組範例 * 注意到 `fibdrv.c` 存在著 `DEFINE_MUTEX`, `mutex_trylock`, `mutex_init`, `mutex_unlock`, `mutex_destroy` 等字樣，什麼場景中會需要呢？撰寫多執行緒的 userspace 程式來測試，觀察 Linux 核心模組若沒用到 mutex，到底會發生什麼問題 * 許多現代處理器提供了 [clz / ctz](https://en.wikipedia.org/wiki/Find_first_set) 一類的指令，你知道如何透過演算法的調整，去加速 [費氏數列](https://hackmd.io/s/BJPZlyDSV) 運算嗎？請列出關鍵程式碼並解說