# 2019q1 Homework2 (fibdrv) contributed by < `fakepaper56` > ## 自我檢查清單 #### 檔案 fibdrv.c 裡頭的 `MODULE_LICENSE`, `MODULE_AUTHOR`, `MODULE_DESCRIPTION`, `MODULE_VERSION` 等巨集做了什麼事，可以讓核心知曉呢？ insmod 這命令背後，對應 Linux 核心內部有什麼操作呢？請舉出相關 Linux 核心原始碼並解讀 1. 我們可以發現 `MODULE_LICENSE` , `MODULE_AUTHOR` 等巨集都是定義 `module.h` 中，同時他們都是被丟入 `__MODULE_INFO` 這個巨集中。而 `__MODULE_INFO` 定義 `moduleparam.h` 裡。 ``` clike= /* module.h */ #define MODULE_LICENSE(_license) MODULE_INFO(license, _license) #define MODULE_AUTHOR(_author) MODULE_INFO(author, _author) #define MODULE_DESCRIPTION(_description) MODULE_INFO(description, _description) #define MODULE_VERSION(_version) MODULE_INFO(version, _version) /* moduleparam.h */ #define MODULE_INFO(tag, info) __MODULE_INFO(tag, tag, info) ``` 所以 `MODULE_LICENSE("GPL")` 我們可以轉換成 `__MODULE_INFO(license, license, "GPL")` 。 而 `__MODULE_INFO` 的巨集是定義如下: ``` clike= #define __MODULE_INFO(tag, name, info) \ static const char __UNIQUE_ID(name)[] \ __used __attribute__((section(".modinfo"), unused, aligned(1))) \ = __stringify(tag) "=" info ``` 我們先解析 `__UNIQUE_ID` 與 `__stringify` 這兩個巨集 可以看出來 `__UNIQUE_ID` 是做出 `__UNIQUE_ID_<perfix><line>` 的字串。 而 `__stringify` 跟它名子一樣，就是做字串化。 ``` clike= #define __UNIQUE_ID(prefix) __PASTE(__PASTE(__UNIQUE_ID_, prefix), __LINE__) /* compiler_types.h */ #define ___PASTE(a,b) a##b #define __PASTE(a,b) ___PASTE(a,b) /* stringfy.h */ #define __stringify_1(x...) #x #define __stringify(x...) __stringify_1(x) ``` 而最後，我們的`MODULE_LICENSE("GPL")`會被展開成如下: ``` clike= static const char __UNIQUE_ID_licienseXX[] __used __attribute__ ((section(".modinfo"),unused,aligned(1))) = "license" "=" "GPL" ``` `"license" "=" "GPL"` 這部份是利用C語言字串的特性，可視為一般的 `"license=GPL"` 。 那為什麼核心可以知道這些內容呢？他利用__attribute__，把這些描述內容放入`.text` 區的 `.modinfo` 區段而不是 `.data` 區。 2. #### 注意到 `fibdrv.c` 存在著 `DEFINE_MUTEX`, `mutex_trylock`, `mutex_init`, `mutex_unlock`, `mutex_destroy` 等字樣，什麼場景中會需要呢？撰寫多執行緒的 userspace 程式來測試，觀察 Linux 核心模組若沒用到 mutex，到底會發生什麼問題 下面這支程式，我在 userspace 使用pthread做的程式，這兩個執行緒同時加了@n一萬次1，也同時減少了一萬次1。照理來說，我們預期結果@n為0。 ```clike= #include <stdio.h> #include <pthread.h> void *add(void *p) { int *ip = (int *)p; for(int i = 0; i < 10000; ++i) { int tmp = *ip + 1; *ip = tmp; } } void *sub(void *p) { int *ip = (int *)p; for (int i = 0; i < 10000; ++i){ int tmp = *ip - 1; *ip = tmp; } } int main() { int n = 0; pthread_t t1; // thread to execute add(). pthread_t t2; // thread to execute sub(). pthread_create(&t1, NULL, add, &n); pthread_create(&t2, NULL, sub, &n); /* wait for t1 t2 */ pthread_join(t1, NULL); pthread_join(t2, NULL); printf("%d\n",n); return 0; } ``` 執行結果如下，看起有不小的誤差。想樣一個場景，add() 剛執行完 tmp = *(ip) + 1 的時候我們跑完了一個完整的 sub()，這時候才執行 *ip = tmp 。這樣的話，中間插入的那個sub() 就跟白做了一樣。 ``` paper56@paper56-X510UNR:~$ ./a.out 127 paper56@paper56-X510UNR:~$ ./a.out -2234 paper56@paper56-X510UNR:~$ ./a.out 5194 paper56@paper56-X510UNR:~$ ./a.out -2734 ``` 核心如果沒有使用lock這種機制的話，如果執行多個行程卻同時讀寫一個資源的時候，也容易發生上面出現的狀況。 #### 許多現代處理器提供了 clz / ctz 一類的指令，你知道如何透過演算法的調整，去加速 費氏數列 運算嗎？請列出關鍵程式碼並解說 以我利用[fast doubling](https://www.nayuki.io/page/fast-fibonacci-algorithms)實做出的程式而言，首要做的事情:就是找到參數的 [MSB](https://zh.wikipedia.org/wiki/%E6%9C%80%E9%AB%98%E6%9C%89%E6%95%88%E4%BD%8D) :::warning 用語要精準，注意是 MSB 到 LSB，還是反向，避免「左右」這種含糊詞彙 :notes: jserv ::: 如果我們是用一個一個找的話，程式碼如下(以下程式碼，都沒考慮 `x==0` 的時候): ``` clike t = 1 << 31； while(x & t == 0) t >>= 1; ``` 但是如果善用 __builtin_clz() 這個 gcc 提供的 extension，可以使用硬體來減少上面程式用的 branch 的數量: ``` clike t = 1 << (31 - __buitin_clz(x)); ```