[week 2] fibdrv 紀錄
===

fibdrv 是一個 kernel space 負責處理費氏數列運算的核心模組

開始之前
---
### 更新核心

因為筆電上的 OS 是 Linux Mint 18.1，是從 Ubuntu 16.04 改過來的，所以預設 kernel 也是 linux-4.4，根據作業說明（linux kernel version > linux-4.15）我是需要更新核心的

1. 直接從 [Ubuntu](http://kernel.ubuntu.com/~kernel-ppa/mainline/) 抓 deb 下來裝
根據 The linux kernel Archieves，最近的穩定版本（kernel v5 以外的）就是 linux-4.20 了
但是載下來裝了一半發現這中間 Linux Base 有調整，導致沒有裝成功 `$ dpkg -L linux-headers-4.15.0-45-generic | grep "/lib/modules"` 後不會顯示任何東西

2. 透過 mint 內建 IDE
Mint 桌面工具可以自動下載不同版本的核心，但是實際上看終端機行為也就是把第一點做的事用 script 完成而已
不過這次我是裝 linux-4.15 版本，也就是作業原始要求的環境，雖然根據終端機輸出 error 出現很多次找不到相關韌體以及函式庫，但是最後還是編譯成功了
但是重開後雖然有成功載入，但是網路驅動沒抓到，`ifconfig` 只有看到一個 loopback，linux-4.4 上可以看到的網卡 wlp3s0 不見了

3. 偷偷用 linux-4.4-generic 試試看
恩結果成功了
其實重裝 ubuntu 18.04 的話就可以確定升到 kernel v5 了，但是無論是雙系統筆電端跟有一堆應用設定的遠端機器要升級都是一件非常花時間的事情，更別提核心上的修改很有可能導致系統損毀，所以個人認為要玩核心最好是另外有一台測試用的機器，才不至於核心修壞了，也把自己的工具也一併弄壞了

### 什麼是驅動程式？

一個週邊硬體裝置上需要有相互配對的韌體與驅動軟體，作業系統才能存取到該硬體資源，而在 Linux 這樣一個 monolithic 的核心設計中，驅動程式被放在 kernel space

但是萬一今天我們每拿到一個未知的硬體裝置，就必須重新編譯一個支援該硬體驅動程式的系統核心嗎？ Linux 為了避免這種繁瑣的事情，設計了 kernel module，在需要的時候才把 user space 的程式透過 syscall 連結到 kernel space

事實上，現在 linux kernel 的程式大小每日都在增長的一部分原因，也是把一些常見的驅動程式加入核心（避免每次都需要手動 `insmod`）

開始中
---

在直接看 fibdrv.c 實做以前，先對驅動程式架構有基本了解會比較有幫助 - [Linux 驅動程式是怎麼鍊成的？](/s/BysEaiGwN#)

### 註冊 Device Number
透過 `ls -l /dev/` 可以看到所有裝置的 major / minor 號


如果想要對 major 與 minor 差異有更直觀的理解


可以看到 tty 終端機對應到的都是同一個 major number (這邊是 4)，使用的是同一個驅動程式，而後面的 minor number 則具體區分出不同的裝置 ([Major and Minor Numbers](https://www.oreilly.com/library/view/linux-device-drivers/0596000081/ch03s02.html))

那要怎麼取得 major 與 minor number ?

主要有三種方法： `register_chrdev_region()` `alloc_chrdev_region()` `register_chrdev()`，而這三個函式都會調用同一個實做 `__register_chrdev_region()`

`register_chrdev()` 是最古老的調用函式，如果給定主副號碼則嘗試靜態分配，若主號碼設為 0 則定義為動態分配

`alloc_chrdev_region()` 則單純是靜態分配，我們需要先指定需要的主設備號以及設備數量

`alloc_chrdev_region()` 則是改進上述只能靜態分配的缺點，系統會自動動態分配可以用的設備號

:::info
事實上，所有的設備編號都被紀錄在一個 `chrdevs` 的 linked-list 中，具體請參考 [字符设备 register_chrdev_region()、alloc_chrdev_region() 和 register_chrdev()](https://blog.csdn.net/Tommy_wxie/article/details/7195471)
:::

自我檢查清單
---

1. 檔案 fibdrv.c 裡頭的 `MODULE_LICENSE`, `MODULE_AUTHOR`, `MODULE_DESCRIPTION`, `MODULE_VERSION` 等巨集做了什麼事，可以讓核心知曉呢？ insmod 這命令背後，對應 Linux 核心內部有什麼操作呢？請舉出相關 Linux 核心原始碼並解讀

根據 [linux/module.h](https://github.com/torvalds/linux/blob/master/include/linux/module.h) 程式碼我們可以看到，事實上無論是 `MODULE_LICENSE()` 或是 `MODULE_AUTHOR()` 以上的抽象化函式事實上都指向同一個實做 `MODULE_INFO()`(或者說是 `_MODULE_INFO()`)
並且在 [moduleparam.h](https://github.com/torvalds/linux/blob/master/include/linux/moduleparam.h) 我們可以發現 `__MODULE_INFO()` 會呼叫 `__used __attribute__()` 的實做

:::info
網路上直接搜索 'linux/module.h' 會找到一篇 [2013 年寫的 MODULE_LICENCE 机制](https://blog.csdn.net/computertechnology/article/details/16801079)，關於這篇文章提到「`__MODULE__INFO()` 後續會接到 `__module_cat()` 實做部份可能是舊的核心實做」
:::

但是關於這個 macro 呼叫真的寫得很奇葩，於是特別拉出來研究一下

#define __MODULE_INFO(tag, name, info)					  \
static const char __UNIQUE_ID(name)[]					  \
  __used __attribute__((section(".modinfo"), unused, aligned(1)))	  \
= __stringify(tag) "=" info

分開斷句就會變成

static const char __UNIQUE_ID(name)[] 
/* 以上代表輸出為一個 char array */      
__used __attribute__( (section(".modinfo"), unused, aligned(1) ) )
/* 以上代表另外一個巨集的呼叫 */
= __stringify(tag) "=" info
/* 這邊又做了什麼？ */

簡單的跑一個範例的小程式（感謝助教王紹華提供）

int main() {
  static const char a[] = "a" "=" "b";
  printf("%s\n", a);
  return 0;
}

結果是會印出與一般 assign 一樣的結果 `a=b`
實驗把 `static` 或 `const` 拿掉執行結果是一樣的

:::info
雖然說去掉 `static` 或 `const` 執行結果還是一樣
但是看組合語言表現差別還是蠻大的
具體實做差別請看 [link text](https:// "title")

~~等我把作業寫完再補~~
:::

因為無論是 C99 規格書或者是 [ANSI C grammar](https://www.lysator.liu.se/c/ANSI-C-grammar-y.html?fbclid=IwAR34emhDlHVdNK1dDxi9F2O6s32IQw1SONwQA0mCMrjnWBdNkzsuM3MSvOk) 都沒有提到這樣的文法，因此猜測在編譯前的預處理階段就已經轉換了

根據 [gcc internals](https://gcc.gnu.org/onlinedocs/cpp/Stringizing.html) 中關於 Stringizing 的章節中提到，C 預處理器不僅遇到 `#` 會做 `strcat` ，`a series of adjacent string constants and stringized arguments` 也會被編譯成一個 string const

2. 當我們透過 `insmod` 去載入一個核心模組時，為何 `module_init` 所設定的函式得以執行呢？Linux 核心做了什麼事呢？

這個問題在 [Linux模块化机制和module_init](https://blog.csdn.net/yueqian_scut/article/details/46694229) 中被完整的討論到整體執行流程，簡單來說 `module_init()` 的 call stack 依序為 `__initcall()` → `device_initcall()` → `__define_initcall(,6)`

:::info
上述文章可能也因為引用資料過舊，導致 `__define_initcall()` 在新版本事實上只有兩個 parameter，而最後多了一步 `___define_initcall()` 才是三個
:::

你可能會想問，後面那個 6 是什麼意思？

#define device_initcall(fn) __define_initcall(fn, 6)

根據 [linux/init.h](https://github.com/torvalds/linux/blob/f346b0becb1bc62e45495f9cdbae3eef35d0b635/include/linux/init.h) 中相關註解我們可以看到

/*
 * initcalls are now grouped by functionality into separate
 * subsections. Ordering inside the subsections is determined
 * by link order. 
 * For backwards compatibility, initcall() puts the call in 
 * the device init subsection.
 *
 * The `id' arg to __define_initcall() is needed so that multiple initcalls
 * can point at the same handler without causing duplicate-symbol build errors.
 *
 * Initcalls are run by placing pointers in initcall sections that the
 * kernel iterates at runtime. The linker can do dead code / data elimination
 * and remove that completely, so the initcall sections have to be marked
 * as KEEP() in the linker script.
 */

我們知道後面的數字代表不同的 handler

同時根據 [linux/init.h](https://github.com/torvalds/linux/blob/f346b0becb1bc62e45495f9cdbae3eef35d0b635/include/linux/init.h) 中各種不同的 `__define_initcall()` 使用情形

#define core_initcall(fn)		__define_initcall(fn, 1)
#define core_initcall_sync(fn)		__define_initcall(fn, 1s)
#define postcore_initcall(fn)		__define_initcall(fn, 2)
#define postcore_initcall_sync(fn)	__define_initcall(fn, 2s)
#define arch_initcall(fn)		__define_initcall(fn, 3)
#define arch_initcall_sync(fn)		__define_initcall(fn, 3s)
#define subsys_initcall(fn)		__define_initcall(fn, 4)
#define subsys_initcall_sync(fn)	__define_initcall(fn, 4s)
#define fs_initcall(fn)			__define_initcall(fn, 5)
#define fs_initcall_sync(fn)		__define_initcall(fn, 5s)
#define rootfs_initcall(fn)		__define_initcall(fn, rootfs)
#define device_initcall(fn)		__define_initcall(fn, 6)
#define device_initcall_sync(fn)	__define_initcall(fn, 6s)
#define late_initcall(fn)		__define_initcall(fn, 7)
#define late_initcall_sync(fn) __define_initcall(fn, 7s)

我們可以看到根據呼叫的對象不同，會有不同 id 的 handler
最後導到以 asm 實做的系統呼叫

3. 試著執行 $ readelf -a fibdrv.ko, 觀察裡頭的資訊和原始程式碼及 modinfo 的關聯，搭配上述提問，解釋像 fibdrv.ko 這樣的 ELF 執行檔案是如何「植入」到 Linux 核心

關於 `readelf` 這個工具在 [readelf elf文件格式分析](https://linuxtools-rst.readthedocs.io/zh_CN/latest/tool/readelf.html) 上有一連串詳細的說明，但是要更加詳細的了解程式怎麼被執行的則需要看到 [可执行文件（ELF）格式的理解](http://www.cnblogs.com/xmphoenix/archive/2011/10/23/2221879.html)

首先我們先透過 `readelf -h fibdrv.ko` 看到以下 ELF 檔的標頭

ELF Header:
  Magic:   7f 45 4c 46 02 01 01 00 00 00 00 00 00 00 00 00 
  Class:                             ELF64
  Data:                              2's complement, little endian
  Version:                           1 (current)
  OS/ABI:                            UNIX - System V
  ABI Version:                       0
  Type:                              REL (Relocatable file)
  Machine:                           Advanced Micro Devices X86-64
  Version:                           0x1
  Entry point address:               0x0
  Start of program headers:          0 (bytes into file)
  Start of section headers:          7832 (bytes into file)
  Flags:                             0x0
  Size of this header:               64 (bytes)
  Size of program headers:           0 (bytes)
  Number of program headers:         0
  Size of section headers:           64 (bytes)
  Number of section headers:         27
  Section header string table index: 24

從這邊我們可以發現幾點 .ko 或說是 relocatable file（可重定位文件，類似 gcc 編譯過程中會出現的 .o 檔）有幾點特性

- 進入點 (Entry point) 必為 0x0
因為可重定位文件尚未透過 linker (像是 ar) 連結成可執行文件，因此 relocatable file 的進入點都只為了暫時提供之後連接之後新位址的區域，因此都會設置成零
如果改成已經編入核心的執行檔，像是 `readelf -h /bin/ls`
則可以看到 entry point 是非零的值

  Entry point address:               0x4049a0

之後我們可以用 `readelf -S fibdrv.ko` 看到 section header table，並且發現到因為尚未映射到實際記憶體位置，因此 `addr` 欄位在可重定位文件中都為零（相反的在 `/bin/ls` 這類執行檔則可看到遞增的記憶體位址）

如果想看到 ELF 檔案中各 section 資料具體狀況，我們可以使用 binutils 的 `objdump` 工具將原始機器碼轉成可以閱讀的組合語言 `objdump -d -j .text fibdrv.ko`

我們可以看到除了 `init_fib_dev()` 與 `exit_fib_dev()` 之外大部分的函式都出現在這個區段，除了 `fib_sequence()` 之外

`init_fib_dev()` 跟 `exit_fib_dev()` 有各自的 `.init.text` `.exit.text` 區段，另外像是第一題提到的 `MODULE_LICENSE`, `MODULE_AUTHOR`, `MODULE_DESCRIPTION`, `MODULE_VERSION` 這些東西都會被放在 `.modinfo` 區段中

:::warning
那 `fib_sequence` 跑到哪裡去了？
:::

4. 這個 `fibdrv` 名稱取自 Fibonacci driver 的簡稱，儘管在這裡顯然是為了展示和教學用途而存在，但針對若干關鍵的應用場景，特別去撰寫 Linux 核心模組，仍有其意義，請找出 Linux 核心的案例並解讀。提示: 可參閱 [Random numbers from CPU execution time jitter](https://lwn.net/Articles/642166/)

5. 查閱 [ktime 相關的 API]()，並找出使用案例 (需要有核心模組和簡化的程式碼來解說)

6. [clock_gettime](https://linux.die.net/man/2/clock_gettime) 和 [High Resolution TImers (HRT)](https://elinux.org/High_Resolution_Timers) 的關聯為何？請參閱 POSIX 文件並搭配程式碼解說

7. `fibdrv` 如何透過 [Linux Virtual File System](https://www.win.tue.nl/~aeb/linux/lk/lk-8.html) 介面，讓計算出來的 Fibonacci 數列得以讓 userspace (使用者層級) 程式 (本例就是 `client.c` 程式) 得以存取呢？解釋原理，並撰寫或找出相似的 Linux 核心模組範例

8. 注意到 fibdrv.c 存在著 `DEFINE_MUTEX`, `mutex_trylock`, `mutex_init`, `mutex_unlock`, `mutex_destroy` 等字樣，什麼場景中會需要呢？撰寫多執行緒的 userspace 程式來測試，觀察 Linux 核心模組若沒用到 mutex，到底會發生什麼問題

9. 許多現代處理器提供了 [clz / ctz](https://en.wikipedia.org/wiki/Find_first_set) 一類的指令，你知道如何透過演算法的調整，去加速 [費氏數列](https://hackmd.io/s/BJPZlyDSV) 運算嗎？請列出關鍵程式碼並解說