---
title: 2022 年 Linux 核心設計/實作課程作業 —— fibdrv
image: https://i.imgur.com/KXUuZLV.png
description: 引導學員開發 Linux 核心模組，預期知悉核心模組如何掛載進入 Linux 核心、Virtual File System (VFS) 概況、character device driver 撰寫，和準備對應的測試及效能分析工具
tags: linux2022
---
# K04: fibdrv
> 主講人: [jserv](http://wiki.csie.ncku.edu.tw/User/jserv) / 課程討論區: [2022 年系統軟體課程](https://www.facebook.com/groups/system.software2022/)
:mega: 返回「[Linux 核心設計](http://wiki.csie.ncku.edu.tw/linux/schedule)」課程進度表
==[作業說明錄影](https://youtu.be/IfsldrCuX28)== / ==[Code Review 錄影](https://youtu.be/Fo-3MtrXr3E)==
> :warning: 2022 年已變更作業要求
## :memo: 預期目標
* 撰寫適用於 Linux 核心層級的程式
* 學習 ktimer, copy_to_user 一類的核心 API
* 複習 C 語言 [數值系統](https://hackmd.io/@sysprog/c-numerics) 和 [bitwise 操作](https://hackmd.io/@sysprog/c-bitwise)
* 數值分析和運算改進策略
* 初探 Linux VFS
* 自動測試機制
* 透過工具進行效能分析
## :rocket: 費氏數列
參照以下材料理解 Fibonacci 數列和對應的計算手法:
* [費氏數列分析](https://hackmd.io/@sysprog/fibonacci-number)
* 「什麼是費氏數列」短片: [Part I](https://youtu.be/JWGCrICTars), [Part II](https://youtu.be/TA0Dpx0LOeY), [Part III](https://youtu.be/WyDn6wiwW74), [Part IV](https://youtu.be/iCSNHH45EeI)
* TED: [The magic of Fibonacci numbers](https://youtu.be/SjSHVDfXHQ4) (有繁體中文字幕)
依據 [Fibonacci and Golden Ratio Formulae](http://www.maths.surrey.ac.uk/hosted-sites/R.Knott/Fibonacci/fibFormulae.html)，考慮 Fibonacci 最初提到不會死亡的兔子繁衍總量問題，假設成年兔子為 `a` ，幼年兔子為 `b` ，我們可得到以下關係:
$$
a_{n+1} = a_n + b_n \\ b_{n+1} = a_n
$$
將上述推導寫成矩陣的形式就會變成
$$
\begin{pmatrix}
a_{n+1} \\ b_{n+1}
\end{pmatrix}
=
\begin{pmatrix}
1 & 1 \\
1 & 0
\end{pmatrix}
\begin{pmatrix}
a_n \\ b_n
\end{pmatrix}
$$
則 $\begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}$ 就是所謂的 ==Q-matrix==，可進一步改寫為:
$$
Q =
\begin{pmatrix}
1 & 1 \\
1 & 0
\end{pmatrix}
=
\begin{pmatrix}
F_2 & F_1 \\
F_1 & F_0
\end{pmatrix}
\\
Q^n =
\begin{pmatrix}
F_{n+1} & F_n \\
F_n & F_{n-1}
\end{pmatrix}
$$
解說短片: [The Fibonacci Q-matrix](https://youtu.be/lTHVwsHJrG0)
接著談及 [Fast Doubling](https://chunminchang.github.io/blog/post/calculating-fibonacci-numbers-by-fast-doubling) 手法，繼續整理:
$$
\begin{split}
\begin{bmatrix}
F(2n+1) \\
F(2n)
\end{bmatrix} &=
\begin{bmatrix}
1 & 1 \\
1 & 0
\end{bmatrix}^{2n}
\begin{bmatrix}
F(1) \\
F(0)
\end{bmatrix}\\ \\ &=
\begin{bmatrix}
1 & 1 \\
1 & 0
\end{bmatrix}^n
\begin{bmatrix}
1 & 1 \\
1 & 0
\end{bmatrix}^n
\begin{bmatrix}
F(1) \\
F(0)
\end{bmatrix}\\ \\ &=
\begin{bmatrix}
F(n+1) & F(n) \\
F(n) & F(n-1)
\end{bmatrix}
\begin{bmatrix}
F(n+1) & F(n) \\
F(n) & F(n-1)
\end{bmatrix}
\begin{bmatrix}
1 \\
0
\end{bmatrix}\\ \\ &=
\begin{bmatrix}
F(n+1)^2 + F(n)^2\\
F(n)F(n+1) + F(n-1)F(n)
\end{bmatrix}
\end{split}
$$
因此可得:
$$
\begin{split}
F(2k) &= F(k)[2F(k+1) - F(k)] \\
F(2k+1) &= F(k+1)^2+F(k)^2
\end{split}
$$
根據 Fibonacci 數列原始定義 `F(0) = 0, F(1) = 1, F(2) = 1`我們就可用這三個值，依據上述公式推導出隨後的數值。
對應的虛擬碼如下:
```python
Fast_Fib(n)
a = 0; b = 1; // m = 0
for i = (number of binary digit in n) to 1
t1 = a*(2*b - a);
t2 = b^2 + a^2;
a = t1; b = t2; // m *= 2
if (current binary digit == 1)
t1 = a + b; // m++
a = b; b = t1;
return a;
```
以 $F(6)$ 為例:
* 第 1 次遞迴
```graphviz
strict digraph G
{
1[label="F(6)"]
2[label="F(4)"]
3[label="F(5)"]
4[label="F(2)"]
5[label="F(3)"]
6[label="F(3)"]
7[label="F(4)"]
8[label="F(0)", style=filled]
9[label="F(1)", style=filled]
10[label="F(1)", style=filled]
11[label="F(2)"]
12[label="F(1)", style=filled]
13[label="F(2)"]
14[label="F(2)"]
15[label="F(3)"]
16[label="F(0)", style=filled]
17[label="F(1)", style=filled]
18[label="F(0)", style=filled]
19[label="F(1)", style=filled]
20[label="F(0)", style=filled]
21[label="F(1)", style=filled]
22[label="F(1)", style=filled]
23[label="F(2)", style=filled]
24[label="F(0)", style=filled]
25[label="F(1)", style=filled]
1 -> {2, 3}
2 -> {4, 5}
3 -> {6, 7}
4 -> {8, 9}
5 -> {10, 11}
6 -> {12, 13}
7 -> {14, 15}
11 -> {16, 17}
13 -> {18, 19}
14 -> {20, 21}
15 -> {22, 23}
23 -> {24, 25}
}
```
* 第 2 次遞迴
```graphviz
strict digraph G
{
1[label="F(6)"]
2[label="F(3)"]
3[label="F(4)"]
4[label="F(1)", style=filled]
5[label="F(2)", style=filled]
6[label="F(2)", style=filled]
7[label="F(3)"]
8[label="F(1)", style=filled]
9[label="F(2)", style=filled]
1 -> {2, 3}
2 -> {4, 5}
3 -> {6, 7}
7 -> {8, 9}
}
```
可見遞迴次數縮減，還能再更快嗎？再觀察到 $F(6)$ 被分成 $F(3)$ 和 $F(4)$ 兩個部分，其中 $F(4) = F(2)+F(3)$ ，可以利用 $F(3)$ 和遞迴 $F(3)$ 時所得到的 $F(2)$ 去計算 $F(4)$，這樣可以再次降低運算的次數，如下：
* 第 2 次遞迴
```graphviz
strict digraph G
{
1[label="F(6)"]
2[label="F(3)"]
3[label="F(4)"]
4[label="F(1)", style=filled]
5[label="F(2)", style=filled]
6[label=" " ,color=white]
7[label=" " ,color=white]
{rank = same; 2;3;}
{rank = same; 4;5;}
1 -> {2, 3}
2 -> {4, 5}
2 -> 3 [style=dashed; arrowhead=vee]
5 -> 3 [style=dashed; arrowhead=vee]
3 -> {6, 7} [color=white]
}
```
和最初的 Fibonacci 數列定義相比，可見相當大的差距。
示範案例:
求解 $F(10)$:
10~10~ = 1010~2~
| i | start | 4 | 3 | 2 | 1 | result |
|---|-------|----------|----------|----------|---------|--------|
| n | - | ==1==010 | 1==0==10 | 10==1==0 | 101==0== | - |
|F(m) | F(0) | F(0*2+1) | F(1*2) | F(2*2+1) | F(5*2) | F(10) |
| a | 0 | 1 | 1 | 5 | 55 | 55 |
| b | 1 | 1 | 2 | 8 | 89 | - |
對照 $F(11)$
11~10~ = 1011~2~
| | 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
### 考慮到硬體加速 $F(n)$ 的手法
許多現代處理器提供 [clz / ctz](https://en.wikipedia.org/wiki/Find_first_set) 一類的指令，可搭配上述 [Fast Doubling](https://chunminchang.github.io/blog/post/calculating-fibonacci-numbers-by-fast-doubling) 手法運用:
1. 省略 $F(0)$，直接從 $F(1)$ 開始;
2. clz/[ffs](https://www.kernel.org/doc/htmldocs/kernel-api/API-ffs.html): 先去除數字 MSB 起算的開頭 0 位元，因為真正的數字不包含 leading 0s，所以計算它也沒用，因此需要 [clz](https://en.wikipedia.org/wiki/Find_first_set#CLZ) 計算有多少 leading 0s
* 遇到 `0` $\rightarrow$ 進行 fast doubling，也就是求 $F(2n)$ 和 $F(2n+1)$
* 遇到 `1` $\rightarrow$ 進行 fast doubling，也就是先求 $F(2n)$ 和 $F(2n+1)$，再求 $F(2n+2)$
可對照 [你所不知道的 C 語言: 遞迴呼叫篇](https://hackmd.io/@sysprog/c-recursion)。
### Fibonacci 數的應用
電腦在計算亂數時，常以新產生出來的數值作為下一次計算的依據，這就是為什麼計算機隨機數大部分都會表示成遞迴定義的數列。
:::info
這裡只探討 [Pseudo-Random Number Generators](https://en.wikipedia.org/wiki/Pseudorandom_number_generator) (PRNG)
:::
> 這是一般的 Fibonacci 數列
```cpp
f[0] = 0;
f[1] = 1;
f[i] = f[i - 1] + f[i - 2];
```
>數列呈現單調遞增
```
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 generator](https://en.wikipedia.org/wiki/Lagged_Fibonacci_generator) (LFG)，是電腦產生隨機數的一種方法。
延伸閱讀:
* [For The Love of Computing: The Lagged Fibonacci Generator — Where Nature Meet Random Numbers](https://medium.com/asecuritysite-when-bob-met-alice/for-the-love-of-computing-the-lagged-fibonacci-generator-where-nature-meet-random-numbers-f9fb5bd6c237)
## :package: 撰寫 Linux 核心模組
請自行參閱以下教材:
* 《[The Linux Kernel Module Programming Guide](https://sysprog21.github.io/lkmpg/)》
* [Introduction to Linux kernel driver programming](https://events.linuxfoundation.org/wp-content/uploads/2017/12/Introduction-to-Linux-Kernel-Driver-Programming-Michael-Opdenacker-Bootlin-.pdf)
* [Part 1: Introduction](http://derekmolloy.ie/writing-a-linux-kernel-module-part-1-introduction/)
* [Part 2: A Character Device](http://derekmolloy.ie/writing-a-linux-kernel-module-part-2-a-character-device/)
## :dart: `fibdrv`: 可輸出 Fibonacci 數列的 Linux 核心模組
### 前期準備
:::info
1. 開發環境預期和 ==[lab0](https://hackmd.io/@sysprog/linux2021-lab0)== 相似，如果你剛好重新安裝 Ubuntu Linux，請依據指示將必要的開發套件裝好;
2. 從 [Homework3](https://hackmd.io/@sysprog/linux2021-homework3) 起，我們就有分析應用程式和 Linux 核心效能的需求，==不該在虛擬機器環境== 裡頭測試 (但 [container](https://linuxcontainers.org/) 或 [Linux KVM](https://www.linux-kvm.org/page/Main_Page) 可接受)，否則會有效能偏差的問題 $\to$ 及早在實體機器上安裝好 GNU/Linux;
:::
* 自從 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?](https://askubuntu.com/questions/762254/why-do-i-get-required-key-not-available-when-install-3rd-party-kernel-modules)
* 檢查 Linux 核心版本
```shell
$ uname -r
```
預期是大於等於 `5.4.0` 的版本，例如 `5.4.0-66-generic`。若在你的開發環境中，核心版本低於 `5.4` 的話，需要更新 Linux 核心，請自行參照相關文件
* 安裝 `linux-headers` 套件 (注意寫法裡頭有 `s`)，以 [Ubuntu Linux 20.04 LTS](https://packages.ubuntu.com/focal/linux-headers-generic) 為例:
```shell
$ sudo apt install linux-headers-`uname -r`
```
* 確認 `linux-headers` 套件已正確安裝於開發環境
```shell
$ dpkg -L linux-headers-5.4.0-66-generic | grep "/lib/modules"
```
預期得到以下輸出:
```
/lib/modules/5.4.0-66-generic/build
```
* 檢驗目前的使用者身份
```shell
$ whoami
```
預期為「不是 root 的使用者名稱」，例如 `jserv` (或者你安裝 Ubuntu Linux 指定的登入帳號名稱)。由於測試過程需要用到 sudo，請一併查驗:
```shell
$ sudo whoami
```
預期輸出是 `root`
:notes: 在下列操作中，請==避免用 root 帳號輸入命令==，而該善用 `sudo`
:::danger
之後的實驗中，我們會重建 root file system，若濫用 root 權限，很可能就把 GNU/Linux 開發環境不小心破壞 (當然，你還是可重新安裝)，現在開始養成好習慣
:::
* 安裝後續會用得到的工具
```shell
$ sudo apt install util-linux strace gnuplot-nox
```
* 取得原始程式碼
```shell
$ git clone https://github.com/sysprog21/fibdrv
$ cd fibdrv
```
* 編譯並測試
```shell
$ make check
```
預期會看到綠色的 ` Passed [-]` 字樣，隨後是
```
f(93) fail
input: 7540113804746346429
expected: 12200160415121876738
```
這符合預期，因為給定的 `fibdrv` 存在==缺陷==。
:::info
就因世界不完美，才有我們工程師存在的空間。
:::
* 觀察產生的 `fibdrv.ko` 核心模組
```shell
$ modinfo fibdrv.ko
```
預期可得以下輸出:
```
description: Fibonacci engine driver
author: National Cheng Kung University, Taiwan
license: Dual MIT/GPL
name: fibdrv
vermagic: 5.4.0-45-generic SMP mod_unload
```
* 觀察 `fibdrv.ko` 核心模組在 Linux 核心掛載後的行為（要先透過 `insmod` 將模組載入核心後才會有下面的裝置檔案 `/dev/fibonacci`）
```shell
$ ls -l /dev/fibonacci
$ cat /sys/class/fibonacci/fibonacci/dev
```
新建立的裝置檔案 `/dev/fibonacci`，注意到 `236` 這個數字，在你的電腦也許會有出入。試著對照 [fibdrv.c](https://github.com/sysprog21/fibdrv/blob/master/fibdrv.c)，找尋彼此的關聯。
```shell
$ cat /sys/module/fibdrv/version
```
預期輸出是 `0.1`，這和 [fibdrv.c](https://github.com/sysprog21/fibdrv/blob/master/fibdrv.c) 透過 `MODULE_VERSION` 所指定的版本號碼相同。
```shell
$ lsmod | grep fibdrv
$ cat /sys/module/fibdrv/refcnt
```
這兩道命令的輸出都是 `0`，意味著目前的 [reference counting](https://en.wikipedia.org/wiki/Reference_counting)。
## 計算 F~93~ (包含) 之後的 Fibonacci 數 - 使用數字字串並套用 quiz2 SSO (Small String Optimization)
因 F~93~ 之後的運算會發生 overflow，導致無法正確地計算結果。可以使用底下方法計算 big number:
* 使用 [GCC `__int128`](https://gcc.gnu.org/onlinedocs/gcc/_005f_005fint128.html) 型態，或者自行定義的結構:
```cpp
struct BigN {
unsigned long long lower, upper;
};
```
* 使用數字字串做運算，並運用 [Small/Short String Optimization](http://wdv4758h.github.io/notes/cpp/string-optimization.html)。[實作程式碼](https://github.com/AdrianHuang/fibdrv/tree/big_number)。
底下為數字字串加法實作，細節如下:
* 確保 `a` 字串長度大於 `b` 字串
* 將 `a` 與 `b` 字串反轉
* 逐字對數字字元做加法運算
* 將得出字串反轉，即得出最終結果
```cpp
static void string_number_add(xs *a, xs *b, xs *out)
{
char *data_a, *data_b;
size_t size_a, size_b;
int i, carry = 0;
int sum;
/*
* Make sure the string length of 'a' is always greater than
* the one of 'b'.
*/
if (xs_size(a) < xs_size(b))
__swap((void *) &a, (void *) &b, sizeof(void *));
data_a = xs_data(a);
data_b = xs_data(b);
size_a = xs_size(a);
size_b = xs_size(b);
reverse_str(data_a, size_a);
reverse_str(data_b, size_b);
char buf[size_a + 2];
for (i = 0; i < size_b; i++) {
sum = (data_a[i] - '0') + (data_b[i] - '0') + carry;
buf[i] = '0' + sum % 10;
carry = sum / 10;
}
for (i = size_b; i < size_a; i++) {
sum = (data_a[i] - '0') + carry;
buf[i] = '0' + sum % 10;
carry = sum / 10;
}
if (carry)
buf[i++] = '0' + carry;
buf[i] = 0;
reverse_str(buf, i);
/* Restore the original string */
reverse_str(data_a, size_a);
reverse_str(data_b, size_b);
if (out)
*out = *xs_tmp(buf);
}
```
如此一來，計算到 F~500~ [(The first 500 Fibonacci numbers )](https://blog.abelotech.com/posts/first-500-fibonacci-numbers/) 也是正確的，結果如下:
```shell
$ sudo ./client
...
Reading from /dev/fibonacci at offset 499, returned the sequence 86168291600238450732788312165664788095941068326060883324529903470149056115823592713458328176574447204501.
Reading from /dev/fibonacci at offset 500, returned the sequence 139423224561697880139724382870407283950070256587697307264108962948325571622863290691557658876222521294125.
...
```
### `fibdrv` 核心模組內部
觀察使用者層級 (user-level) 的程式如何與 fibdrv 互動:
```cpp
fd = open(FIB_DEV, O_RDWR);
if (fd < 0) {
perror("Failed to open character device");
exit(1);
}
for (i = 0; i <= offset; i++) {
sz = write(fd, write_buf, strlen(write_buf));
printf("Writing to " FIB_DEV ", returned the sequence %lld\n", sz);
}
for (i = 0; i <= offset; i++) {
lseek(fd, i, SEEK_SET);
sz = read(fd, buf, 1);
printf("Reading from " FIB_DEV
" at offset %d, returned the sequence "
"%lld.\n",
i, sz);
}
```
`fibdrv` 設計為一個 [character device](https://linux-kernel-labs.github.io/refs/heads/master/labs/device_drivers.html)，可理解是個能夠循序存取檔案，透過定義相關的函數，可利用存取檔案的系統呼叫以存取 (即 open, read, write, mmap 等等)。因此，使用者層級 (user-level 或 userspace) 的程式可透過 `read` 系統呼叫來得到輸出。
接著來看如何實作:
```cpp
/* calculate the fibonacci number at given offset */
static ssize_t fib_read(struct file *file,
char *buf,
size_t size,
loff_t *offset)
{
return (ssize_t) fib_sequence(*offset);
}
const struct file_operations fib_fops = {
.owner = THIS_MODULE,
.read = fib_read,
.write = fib_write,
.open = fib_open,
.release = fib_release,
.llseek = fib_device_lseek,
};
```
不難發現是透過 `fib_fops` 中的自行定義的 read 來實作讀取操作，而 `fib_read` 最終會回傳 `fib_sequence(*offset)`，因此就是透過讓使用者指定不同的 offest 作為 Fibonacci 數列的 $x$ 然後透過 read 的回傳值輸出 $fib(x)$ 給使用者。
在 [LP64](https://en.wikipedia.org/wiki/64-bit_computing#64-bit_data_models) 資料模式中，`long long` 僅寬 64 位元，因此若要表示更大的數，需要用兩個以上的變數表示一個數，在這種情況下作加法運算時，若使用 "+" operator ，會發生 overflow，可考慮實作一個更多位元的全加器。
$fib(92)$ 的計算結果用 16 進位表示是 `0x1 11F3 8AD0 840B F6BF`，超過 64 位元整數所夠表示的最大數值，因此考量到要正確輸出 $fib(100)$ 或數列更後面的數值，就必須使用到特製的結構來處理回傳值。以下是參考實作
```cpp
struct BigN {
unsigned long long lower, upper;
};
```
使用 struct BigN 來將一個數字分成兩部份:
* 高位的 64 bits 保存 upper 中;
* 低位的 64 bit 則是保存在 lower 中;
進行大數加法時，則需要注意 lower 是否需要進位到 upper:
```cpp
static inline void addBigN(struct BigN *output, struct BigN x, struct BigN y)
{
output->upper = x.upper + y.upper;
if (y.lower > ~x.lower)
output->upper++;
output->lower = x.lower + y.lower;
}
```
因為 `x.lower + ~x.lower = ~0`，移項後 `~x.lower = ~0 - x.lower`，亦即 `~x.lower` 表示 `x.lower` 跟最大值(`~0`) 的距離。所以若 `y.lower` 比 `x.lower` 距離最大值的距離還大，就表示相加後會 overflow，需要進位，這時執行 `output->upper++`。
### [Linux Virtual File System](https://www.win.tue.nl/~aeb/linux/lk/lk-8.html) 介面
透過 [Linux Virtual File System](https://www.win.tue.nl/~aeb/linux/lk/lk-8.html) 介面，本核心模組可將計算出來的 Fibonacci 數讓 `client.c` 程式得以存取。
VFS 提供一統各式檔案系統的共用介面，方便使用者操作不同的裝置或檔案時，可用一致的方式存取。Linux 的裝置驅動程式大致分為:
* Character Device Driver;
* Block Device Driver;
* Network Device Driver;
在使用裝置前需要對其定義一些 file operation，並將其註冊到 kernel 中。
依據 [/include/linux/fs.h](https://elixir.bootlin.com/linux/v4.15/source/include/linux/fs.h#L1692) 中的定義
```cpp
struct file_operations {
struct module *owner;
loff_t (*llseek) (struct file *, loff_t, int);
ssize_t (*read) (struct file *, char __user *, size_t, loff_t *);
ssize_t (*write) (struct file *, const char __user *, size_t, loff_t *);
...
int (*open) (struct inode *, struct file *);
...
int (*release) (struct inode *, struct file *);
int (*fsync) (struct file *, loff_t, loff_t, int datasync);
int (*fasync) (int, struct file *, int);
int (*lock) (struct file *, int, struct file_lock *);
...
} __randomize_layout;
```
此手法可參見 [你所不知道的 C 語言：物件導向程式設計篇](https://hackmd.io/@sysprog/c-oop)。
以本例來說，宣告一個 file_operations 的資料型態並設定一些對應到 VFS 操作的函式 (fib_read, fib_write 等等)。當在使用者模式程式中呼叫到 read 系統呼叫時，藉由 VFS 將其對應到 fib_read。
```cpp
const struct file_operations fib_fops = {
.owner = THIS_MODULE,
.read = fib_read,
.write = fib_write,
.open = fib_open,
.release = fib_release,
.llseek = fib_device_lseek,
};
```
對照 [Linux 核心設計: 檔案系統概念及實作手法](https://hackmd.io/@sysprog/linux-file-system)。
### 核心模式的時間測量
LWN 的 [Reinventing the timer wheel](https://lwn.net/Articles/646950/) 一文中描述道：
> The kernel maintains two types of timers with two distinct use cases. The high-resolution timer ("hrtimer") mechanism provides accurate timers for work that needs to be done in the near future; hrtimer use is relatively rare, but, when hrtimers are used, they almost always run to completion. "Timeouts," instead, are normally used to alert the kernel to an expected event that has failed to arrive — a missing network packet or I/O completion interrupt, for example. The accuracy requirements for these timers are less stringent (it doesn't matter if an I/O timeout comes a few milliseconds late), and, importantly, these timers are usually canceled before they expire.
跟計時有關的功能主要用在 2 種情境：
1. timer: 安排「在某個時間點做某件事情」。可想像成火車班次表，這個重要的地方是：若某班火車誤點，會連鎖地影響後面所有班次。因此需要較精準的計時機制;
2. timeout: 用來作為逾時的通知，提醒「有東西遲到了」。最簡單的例子是 `qtest` 裡面的 `SIGALRM` 的使用。這對於時間的精準度要求不高;
其中一種計時方式是用作業系統從開機以來的計時器中斷發生的次數作為計時的依據，這個計時機制叫作 `jiffies`，很早就存在於 Linux 核心。較舊的 Linux 核心提供一個建議在 `jiffies` 上的計時機制，叫作 timer wheel。可以參考 [A new approach to kernel timers](https://lwn.net/Articles/152436/) 一文 (註：標題雖然說是 new approach，但這篇寫作時間是 2005 年)。
以 `tv1` 為例，他是個大小是 256 個陣列，看 `jiffies` 的最低 8 位元代表的數字是多少，就去 `tv1` 陣列對應的元素找對應需要處理的事件。而 tv2 是 tv1 的陣列，每經過 $2^8$ 次 jiffy ，index 就加一。 `tv3` 後面以此類推。
不過，這個計時器受限於計時器中斷觸發和實質能處理的的頻率，而這個頻率有其極限。關於中斷，可參見 [Linux 核心設計: 中斷處理和現代架構考量](https://hackmd.io/@sysprog/linux-interrupt)。
一個新的機制是跳脫 `jiffies`，而將計時機制建立在一個新的資料結構 `ktime_t` 上面，可參考 LWN [The high-resolution timer API](https://lwn.net/Articles/167897/) 一文。
`hrtimer` 是在 2.6.16 開始有的新的計時機制，裡面使用了 `ktime_t` 這個新的資料結構來進行計時。這個結構體的定義會隨架構有所不同。所以跟大多數 Linux 中的資料結構使用機制類似，都要使用專門的函數來對這個資料型態進行操作。而在 x86-64 中是個 64 位元整數。相關的使用方式如下：
宣告並初始化一個 `ktime_t`:
```cpp
DEFINE_KTIME(name);
```
這跟 `LIST_HEAD` 的功能之於 `struct list_head` 相仿，宣告一個 `ktime_t` 並初始化成 `0`。
對 ktime 數值進行運算:
```cpp
ktime_t ktime_add(ktime_t kt1, ktime_t kt2);
ktime_t ktime_sub(ktime_t kt1, ktime_t kt2); /* kt1 - kt2 */
ktime_t ktime_add_ns(ktime_t kt, u64 nanoseconds);
```
與其他時間相關的轉換：
```cpp
ktime_t timespec_to_ktime(struct timespec tspec);
ktime_t timeval_to_ktime(struct timeval tval);
struct timespec ktime_to_timespec(ktime_t kt);
struct timeval ktime_to_timeval(ktime_t kt);
clock_t ktime_to_clock_t(ktime_t kt);
u64 ktime_to_ns(ktime_t kt);
```
詳見 [IBM](https://www.ibm.com/developerworks/library/l-timers-list/index.html) 關於 hrtimer 的文章，並對照 [Linux 核心設計: Timer 及其管理機制](https://hackmd.io/@sysprog/linux-timer)。
[ktime 相關的 API](https://www.kernel.org/doc/html/latest/core-api/timekeeping.html) 可用來測量時間，我們可發現到 write 在此核心模組暫時沒作用，於是可挪用來輸出上一次 fib 的執行時間。以下是示範的修改:
```cpp
static ktime_t kt;
static long long fib_time_proxy(long long k)
{
kt = ktime_get();
long long result = fib_sequence(k);
kt = ktime_sub(ktime_get(), kt);
return result;
}
static ssize_t fib_read(struct file *file,
char *buf,
size_t size,
loff_t *offset)
{
return (ssize_t) fib_time_proxy(*offset);
}
static ssize_t fib_write(struct file *file,
const char *buf,
size_t size,
loff_t *offset)
{
return ktime_to_ns(kt);
}
```
### 關於 [client.c](https://github.com/sysprog21/fibdrv/blob/master/client.c)
由 [read](https://linux.die.net/man/2/read) 的手冊描述可知， 若 read 成功，會回傳讀進的 byte 數，而 read 的其中一個輸入參數為 count，即所要讀取的 byte 數，但在 client.c 中，計算出的 Fibonacci 數是 read() 的回傳值。
參考 [Linux Driver Tutorial: How to Write a Simple Linux Device Driver](https://www.apriorit.com/dev-blog/195-simple-driver-for-linux-os) 的第 7 部分 "Using Memory Allocated in User Mode":
> The user allocates a special buffer in the user-mode address space. And the other action that the read function must perform is to copy the information to this buffer. The address to which a pointer from that space points and the address in the kernel address space may have different values. That's why we cannot simply dereference the pointer.
也就是說，在使用者模式 (user-mode) 的位址空間配置一個 buffer 空間時，核心裝置驅動不能直接寫入該地址，相反的，需要透過 [copy_to_user](https://elixir.bootlin.com/linux/latest/ident/copy_to_user)，將想傳給使用者模式 (即運作中的 `client`) 的字串複製到到 `fib_read` 的 buf 參數後，client 端方可接收到此字串。
依據 [Hierarchical performance measurement and modeling of the Linux file system](https://www.researchgate.net/publication/221556402_Hierarchical_performance_measurement_and_modeling_of_the_Linux_file_system) 研究指出，從核心模式複製資料到使用者層級的時間成本是，每個位元組 達 22ns，因此進行效能分析時，要考慮到 [copy_to_user](https://elixir.bootlin.com/linux/latest/ident/copy_to_user) 函式的時間開銷，特別留意到資料大小成長後造成的量測誤差。
## :microscope: Linux 效能分析的提示
無論是伺服器或個人電腦裡頭的 CPU 幾乎都是多核架構，通常在多核心的作業系統中常使用處理器的親和性 ([processor affinity](https://en.wikipedia.org/wiki/Processor_affinity)，亦稱 CPU pinning) 讓行程 (process) 在特定的 CPU 核心中持續執行，不受作業系統排程的干擾。
將行程綁定在特定的 CPU 核心上有許多優點，例如一個 cache bound 的程式跟其他比較耗費 CPU 計算的程式一起執行時，將程式綁定在特定的 CPU 核心可減少 cache miss 的狀況。另外在兩個行程頻繁的藉由共享記憶體進行資料交換時，將兩個行程都綁定在同一個 [NUMA](https://en.wikipedia.org/wiki/Non-uniform_memory_access) 節點中也可增進執行效率。
在 Linux 系統中若要將特定的處理器核心指定給一個程式或行程使用，可以使用 [taskset](http://man7.org/linux/man-pages/man1/taskset.1.html) 命令來設定或取得行程的處理器親和性。
延伸閱讀:
* [Linux 核心設計: 不只挑選任務的排程器](https://hackmd.io/@sysprog/linux-scheduler)
### 查看行程的 CPU affinity
若要查看指定行程的處理器親和性，可使用 `taskset` 加上 `-p` 參數再加上該行程的 PID（process ID）：
```shell
$ taskset -p PID
```
其中 PID 就是行程的 ID，例如：
```shell
$ taskset -p 1
```
參考輸出為: (顯然每台主機搭配 Linux 會有多樣結果)
```
pid 1's current affinity mask: ffffffffffffffff
```
輸出的 affinity mask 是一個十六進位的 bitmask，將其轉換為二進位格式之後，若位元值為 `1` 則代表該行程可在這個位元對應的 CPU 核心中執行，若位元值為 `0` 則代表該行程不允許在這個位元對應的 CPU 核心中執行。
在上面這個例子中十六進位的 ff 轉成二進位的格式會是 `11111111`，這 8 個 1 分別代表該行程可以在第 0 到第 7 個 CPU 核心中執行，最低（LSB; 最右邊）的位元代表第 0 個 CPU 核心，次低的代表第 1 個，以次類推。
如果 affinity mask 是一個 `0x11`，則代表可在第 0 個與第 4 個 CPU 核心執行。若對 bitmask 表示法不易掌握，可加上 `-c` 參數，讓 taskset 直接輸出 CPU 的核心列表：
```shell
$ taskset -cp 1
```
參考輸出為:
```
pid 1's current affinity list: 0-63
```
### 將行程固定在特定的 CPU 中執行
[taskset](http://man7.org/linux/man-pages/man1/taskset.1.html) 亦可設定行程的 core mask，將指定的行程固定在特定的 CPU 核心中執行：
```shell
$ taskset -p COREMASK PID
```
其中 COREMASK 就是指定的十六進位 core mask，PID 則為行程的 ID。除此之外，亦可使用 `-c` 參數以 CPU 的核心列表來指定：
```shell
$ taskset -cp CORELIST PID
```
其中 CORELIST 為 CPU 核心列表，以逗點分隔各個核心的編號或是使用連字號指定連續的區間，例如: `0,2,5,7-10`。
例如若要將一個行程固定在第 0 個與第 4 個 CPU 核心，則使用：
```shell
$ taskset -p 0x11 9030
```
輸出為：
```
pid 9030's current affinity mask: ff
pid 9030's new affinity mask: 11
```
亦可使用 CPU 核心列表的方式：
```shell
taskset -cp 0,4 9030
```
兩種方式效果一致。
在 Linux 中的使用者必須有開啟 [CAP_SYS_NICE](http://man7.org/linux/man-pages/man7/capabilities.7.html) 這個權限，才能更動行程的處理器親和性，而若只是要查看處理器親和性的設定，則沒有限制（任何使用者皆可查詢。
### 以特定的 CPU 執行程式
除了更改現有行程的處理器親和性，使用者也可使用 [taskset](http://man7.org/linux/man-pages/man1/taskset.1.html) 指定 CPU 核心來執行一個新的程式：
```shell
$ taskset COREMASK EXECUTABLE
```
其中 EXECUTABLE 是要執行的程式。
例如若要以第 0 個 CPU 核心執行 vlc 則使用：
```shell
$ taskset 0x1 vlc
```
### 限定 CPU 給特定的程式使用
[taskset](http://man7.org/linux/man-pages/man1/taskset.1.html) 可指定行程所使用的 CPU 核心，但不代表其他的行程不會使用這些被指定的 CPU 核心，如果你不想讓其他的行程干擾你要執行的程式，讓指定的核心只能被自己設定的行程使用，可以使用 `isolcpus` 這個 Linux 核心起始參數，這個參數可以讓特定的 CPU 核心在開機時就被保留下來。
設定的方式有兩種，一個是在開機時使用 boot loader 所提供的自訂開機參數功能，手動加入 `isolcpus=cpu_id` 參數，或是直接加在 GRUB 的設定檔中，這樣 Linux 的排程器在預設的狀況下就不會將任何一般行程放在這個被保留的 CPU 核心中執行，只有那些被 [taskset](http://man7.org/linux/man-pages/man1/taskset.1.html) 特別指定的行程可使用這些 CPU 核心。
舉例來說，如果想讓第 0 個與第 1 個 CPU 核心都被保留下來，則在開機時加入:
```
isolcpus=0,1
```
這個 Linux 起始核心參數，然後再使用 [taskset](http://man7.org/linux/man-pages/man1/taskset.1.html) 命令將這兩個 CPU 核心指定給要執行的程式使用即可。
### 排除干擾效能分析的因素
* 抑制 [address space layout randomization](https://en.wikipedia.org/wiki/Address_space_layout_randomization) (ASLR)
```shell
$ sudo sh -c "echo 0 > /proc/sys/kernel/randomize_va_space"
```
* 設定 scaling_governor 為 performance。準備以下 shell script，檔名為 `performance.sh`:
```shell
for i in /sys/devices/system/cpu/cpu*/cpufreq/scaling_governor
do
echo performance > ${i}
done
```
之後再用 `$ sudo sh performance.sh` 執行
* 針對 Intel 處理器，關閉 turbo mode
```shell
$ sudo sh -c "echo 1 > /sys/devices/system/cpu/intel_pstate/no_turbo"
```
## 用統計手法去除極端值
假設數據分佈接近常態分佈的情況下，一個標準差到三個標準差之內的資料量約佔 68%, 95%, 99.7%
> 圖片來源: [wikipedia](https://en.wikipedia.org/wiki/Standard_deviation)
### Python script 實作以及結果
> [4ce43c4](https://github.com/colinyoyo26/fibdrv/commit/4ce43c4e7ee0b80c4ce9e6dcd995bbfdf239206c)
`datas` 的資料為計算某個 fibonacci number 的時間，並用此手法去除 95% 區間之外的值
- 其中 `z` 代表某個 sample 距離 mean 幾個標準差
```python
def outlier_filter(datas, threshold = 2):
datas = np.array(datas)
z = np.abs((datas - datas.mean()) / datas.std())
return datas[z < threshold]
```
處理計算每個 Fibonacci number 的時間，最後返回處理好資料 (去除 outlier 再取平均)
```python
def data_processing(data_set, n):
catgories = data_set[0].shape[0]
samples = data_set[0].shape[1]
final = np.zeros((catgories, samples))
for c in range(catgories):
for s in range(samples):
final[c][s] = \
outlier_filter([data_set[i][c][s] for i in range(n)]).mean()
return final
```
以下是分別是計算 $100th$ 和 $1000th$ Fibonacci number 的結果，單獨一張圖看起來可能還是波動很大，但對照組放下去就能看出差異
- 每個數據取樣 50 次，對照組為直接平均
從處理過數據的圖中可以更明顯的看出執行時間有週期性波動的趨勢。
## 整數編碼
閱讀〈[Integer Encoding Algorithm 筆記](https://kkc.github.io/2021/01/30/integer-compression-note/)〉及 [invertedtomato/integer-compression](https://github.com/invertedtomato/integer-compression)
---
## 自我檢查清單
- [ ] 研讀上述 ==Linux 效能分析的提示== 描述，在自己的實體電腦運作 GNU/Linux，做好必要的設定和準備工作 $\to$ 從中也該理解為何不希望在虛擬機器中進行實驗;
- [ ] 研讀上述費氏數列相關材料 (包含論文)，摘錄關鍵手法，並思考 [clz / ctz](https://en.wikipedia.org/wiki/Find_first_set) 一類的指令對 Fibonacci 數運算的幫助。請列出關鍵程式碼並解說
- [ ] 複習 C 語言 [數值系統](https://hackmd.io/@sysprog/c-numerics) 和 [bitwise operation](https://hackmd.io/@sysprog/c-bitwise)，思考 Fibonacci 數快速計算演算法的實作中如何減少乘法運算的成本;
- [ ] 研讀 [KYG-yaya573142 的報告](https://hackmd.io/@KYWeng/rkGdultSU)，指出針對大數運算，有哪些加速運算和縮減記憶體操作成本的舉措？
- [ ] `lsmod` 的輸出結果有一欄名為 `Used by`，這是 "each module's use count and a list of referring modules"，但如何實作出來呢？模組間的相依性和實際使用次數 ([reference counting](https://en.wikipedia.org/wiki/Reference_counting)) 在 Linux 核心如何追蹤呢？
> 搭配閱讀 [The Linux driver implementer’s API guide » Driver Basics](https://www.kernel.org/doc/html/latest/driver-api/basics.html)
- [ ] 注意到 `fibdrv.c` 存在著 `DEFINE_MUTEX`, `mutex_trylock`, `mutex_init`, `mutex_unlock`, `mutex_destroy` 等字樣，什麼場景中會需要呢？撰寫多執行緒的 userspace 程式來測試，觀察 Linux 核心模組若沒用到 mutex，到底會發生什麼問題。嘗試撰寫使用 [POSIX Thread](https://en.wikipedia.org/wiki/POSIX_Threads) 的程式碼來確認。
## :penguin: 作業要求
* 回答上述==自我檢查清單==的所有問題，需要附上對應的參考資料和必要的程式碼，以第一手材料 (包含自己設計的實驗) 為佳
:::warning
:warning: 如果你在 2022 年 3 月 1 日前，已從 GitHub [sysprog21/fibdrv](https://github.com/sysprog21/fibdrv) 進行 fork，請依據 ==[Alternatives to forking into the same account](https://github.community/t5/Support-Protips/Alternatives-to-forking-into-the-same-account/ba-p/7428)== 一文，對舊的 repository 做對應處置，然後重新 fork
:::
* 在 GitHub 上 fork [fibdrv](https://github.com/sysprog21/fibdrv)，目標是修正 Fibonacci 數計算的正確性 (現有實作存在缺陷，請指出)，隨後改善 `fibdrv` 計算 Fibinacci 數列的執行效率，過程中需要量化執行時間，可在 Linux 核心模組和使用層級去測量
* 原本的程式碼只能列出到 $Fibonacci(100)$ 而且==部分輸出是錯誤的數值==，請修改程式碼，列出後方更多數值 (注意: 檢查正確性和數值系統的使用)
* 務必研讀上述 ==Linux 效能分析的提示== 的描述，降低效能分析過程中的干擾;
* 在 Linux 核心模組中，可用 ktime 系列的 API;
* 在 userspace 可用 [clock_gettime](https://linux.die.net/man/2/clock_gettime) 相關 API;
* 善用統計模型，除去極端數值，過程中應詳述你的手法
* 分別[用 gnuplot 製圖](https://hackmd.io/@sysprog/Skwp-alOg)，分析 Fibonacci 數列在核心計算和傳遞到 userspace 的時間開銷，單位需要用 us 或 ns (自行斟酌)
* 嘗試解讀上述實驗的時間分佈，特別是隨著 Fibonacci 數列增長後，對於 Linux 核心的影響。可修改 VFS 函式，允許透過寫入 `/dev/fibonacci` 裝置檔案來變更不同的 Fibonacci 求值的實作程式碼。
* 用 printk 固然方便，但其執行時間易受各種因素而不穩定，除了透過統計來觀察，也可改用核心的 sysfs 介面，後者可讓我們自行宣告 show 和 store 介面來提供讀寫操作，可參見 [Sample kobject implementation](https://elixir.bootlin.com/linux/latest/source/samples/kobject/kobject-example.c) (注意: 切換到對應的 Linux 核心版本)。
* 逐步最佳化 Fibonacci 的執行時間，引入[費氏數列分析](https://hackmd.io/@sysprog/fibonacci-number) 提到的策略，並善用 [clz / ffs](https://en.wikipedia.org/wiki/Find_first_set) 一類的指令 (Linux 核心有對應的包裝函式)，過程中都要充分量化
* 嘗試研讀 [bignum](https://github.com/0xff07/bignum/tree/fibdrv) (`fibdrv` 分支) 的實作，理解其中的技巧並與你的實作進行效能比較，探討個中值得取鏡之處。
* 當 $Fib(n)$ 隨著 $n$ 越來越大時，由 Linux 核心傳遞字串形式的十進位就成為效能瓶頸，研讀〈[Integer Encoding Algorithm 筆記](https://kkc.github.io/2021/01/30/integer-compression-note/)〉所提及的策略，在 Linux 核心模組先對數值進行編碼和壓縮，以二進位方式傳遞到使用者層級後，再由應用程式予以顯示 $Fib(n)$ 數值
* 儘量降低由核心傳遞到應用程式的資料量
* 確保應用程式不需要過多的計算量才可重現 Fibonacci 數列
## 繳交方式
編輯 [Homework3 作業區共筆](https://hackmd.io/@sysprog/linux2022-homework3)，將你的觀察、上述要求的解說、應用場合探討，以及各式效能改善過程，善用 gnuplot 製圖，紀錄於新建立的共筆
## 截止日期
Mar 21, 2022 (含) 之前
越早在 GitHub 上有動態、越早接受 code review，評分越高
## 作業觀摩
* [2021 年春季班](https://hackmd.io/@sysprog/linux2021-homework3)
* [2020 年春季班](https://hackmd.io/@sysprog/linux2020-homework2)
Sign in with Wallet
Connect another wallet