---
tags: linux2023
---

# fibdrv Note

- follow [2023 年 Linux 核心設計/實作課程作業 —— fibdrv](https://hackmd.io/@sysprog/linux2023-fibdrv/%2F%40sysprog%2Flinux2023-fibdrv-a)

:::info
參考資料繁多，僅用以紀錄自己瀏覽狀況
- 預期目標+費氏數列
- [ ] 費氏數列相關研讀
- [x] 介紹短片、fast doubling、Fibonacci Q-martix
- [ ] [PRNG](https://en.wikipedia.org/wiki/Pseudorandom_number_generator)
- [ ] [你所不知道的C語言：遞迴呼叫篇](https://hackmd.io/@sysprog/c-recursion)
- [ ] [LFG](https://en.wikipedia.org/wiki/Lagged_Fibonacci_generator)
- [ ] [Linux 核心的 hash table 實作](https://hackmd.io/@sysprog/linux-hashtable)
- Linux 核心模組
- [x] [Part 1: Introduction](http://derekmolloy.ie/writing-a-linux-kernel-module-part-1-introduction/)
- [x] [Part 2: A Character Device](http://derekmolloy.ie/writing-a-linux-kernel-module-part-2-a-character-device/)
:::

## 作業要求

- 在 GitHub 上 fork [fibdrv](https://github.com/sysprog21/fibdrv)，目標是修正 Fibonacci 數計算並改善 fibdrv 核心模組的計算效率，過程中需要量化執行時間，可在 Linux 核心模組和使用者空間 (userspace) 中測量
- 原本的程式碼只能列出到 $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 的執行時間，過程中要充分量化
- 嘗試研讀 [sysprog21/bignum](https://github.com/sysprog21/bignum) 的實作，理解其中的技巧並與你的實作進行效能比較，探討個中值得取鏡之處。
- 當 $Fib(n)$ 隨著 $n$ 越來越大時，由 Linux 核心傳遞字串形式的十進位就成為效能瓶頸
- 儘量降低由核心傳遞到應用程式的資料量
- 確保應用程式不需要過多的計算量才可重現 Fibonacci 數列
- BONUS: 研讀〈[Integer Encoding Algorithm 筆記](https://kkc.github.io/2021/01/30/integer-compression-note/)〉所提及的策略，在 Linux 核心模組先對數值進行編碼和壓縮，再由應用程式予以顯示 $Fib(n)$ 數值

## 前期準備
>步驟皆 follow [文件](https://hackmd.io/@sysprog/linux2023-fibdrv/%2F%40sysprog%2Flinux2023-fibdrv-a)

首先檢查 kernel 版本

uname -r

5.19.0-35-generic

uname -a     // full information

Linux aaron-System-Product-Name 5.19.0-35-generic #36~22.04.1-Ubuntu SMP PREEMPT_DYNAMIC Fri Feb 17 15:17:25 UTC 2 x86_64 x86_64 x86_64 GNU/Linux

確認 `linux-headers` 套件已經正確安裝於開發環境

dpkg -L linux-headers-5.19.0-35-generic | grep "/lib/modules"

預期輸出

/lib/modules
/lib/modules/5.19.0-35-generic
/lib/modules/5.19.0-35-generic/build

檢查目前使用者身份，避免使用 `root`

whoami

安裝工具

sudo apt install util-linux strace gnuplot-nox

- [strace(1)](https://man7.org/linux/man-pages/man1/strace.1.html): 可以追蹤系統呼叫
- `util-linux` (utility linux)

dpkg -l | grep util-linux

- `dpkg -l` 列出以安裝的包

ii  util-linux                                 2.37.2-4ubuntu3                         amd64        miscellaneous system utilities

- linux 的系統工具

clone [fibdrv](https://github.com/sysprog21/fibdrv) 並嘗試編譯測試

make check

 Passed [-]
f(93) fail
input: 7540113804746346429
expected: 12200160415121876738

在 `f(93)` 的時候 `fail` 了

編譯時會產生 `.ko` 檔案，此為 kernel object 檔案，可以使用 [modinfo(8)](https://man7.org/linux/man-pages/man8/modinfo.8.html) 查看 kernel module 的資訊

modinfo fibdrv.ko

預期輸出

filename:       /home/aaron/linux2023/fibdrv/fibdrv.ko
version:        0.1
description:    Fibonacci engine driver
author:         National Cheng Kung University, Taiwan
license:        Dual MIT/GPL
srcversion:     9A01E3671A116ADA9F2BB0A
depends:        
retpoline:      Y
name:           fibdrv
vermagic:       5.19.0-35-generic SMP preempt mod_unload modversions 

- 延伸閱讀 [EXPORT_SYMBOL用法](http://bluequiet.blogspot.com/2011/10/exportsymbolkernelkernel.html)

掛載進去

sudo insmod fibdrv.ko

用 [dmesg(1)](https://man7.org/linux/man-pages/man1/dmesg.1.html) 可以看到相關資訊

$ sudo dmesg
[ 3585.255612] fibdrv: loading out-of-tree module taints kernel.
[ 3585.255647] fibdrv: module verification failed: signature and/or required key missing - tainting kernel

$ lsmod | grep fib
/* Module              Size   Used by*/
fibdrv                 16384  0

- size: 16384
- use: 0

$ ls -l /dev/fibonacci
crw------- 1 root root 509, 0  三  11 17:57 /dev/fibonacci

- `1` 是硬連結數
- `root` 為擁有者 (user) 和所屬群組 (group)
- `509` 是文件大小
- 延伸閱讀 [Character device drivers](https://linux-kernel-labs.github.io/refs/heads/master/labs/device_drivers.html)

**chatGPT 給的解釋**
:::info
在 `ls -l` 命令的輸出中，如果一個文件的大小為 0，那麼第五欄的數字就會是 0。如果文件的大小不為 0，那麼第五欄的數字就代表該文件的大小，表示該文件佔用了多少字節的磁盤空間。

而在 `ls -l` 命令的輸出中，第一欄的第一個數字是用來表示該文件的類型的，例如普通文件、目錄、符號鏈接、設備文件等。在 Linux 系統中，設備文件是一種特殊的文件，用來表示硬體設備。設備文件的第一個數字通常是 0，表示這是一個設備文件。

因此，如果一個文件的第一個數字是 4，這表示這是一個目錄文件。如果一個文件的第一個數字是 0，這表示這是一個設備文件，其大小可能為 0，也可能不為 0，具體取決於該設備的容量。因此，同時出現 4 和 0 的情況，代表這是一個目錄文件，並且其中一些條目是設備文件。
:::

$ cat /sys/module/fibdrv/refcnt
0

- 代表 [reference counting](https://en.wikipedia.org/wiki/Reference_counting)

在重新 `make check` 之前要 `sudo rmmod fibdrv`

## 什麼是費氏數列

- [ ] [費氏數列分析](https://hackmd.io/@sysprog/fibonacci-number)


舉例來說
$$
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233……
$$
- 下一個數字為前兩個數字相加

Recursive 實作 (Python)

def normal_recursion(n):
    if n < 2:
        return n
    return normal_recursion(n - 1) + normal_recursion(n - 2)

- 就是執行的效率很差

- 做了非常多重複的運算

### Fast doubling 計算方法

根據 [Fast doubling](https://chunminchang.github.io/blog/post/matrix-difference-equation-for-fibonacci-sequence)

可得:
$$
\begin{split}
&F&(2k) = F(k)[2F(k+1) - F(k)] \\
&F&(2k+1) = F(k+1)^2+F(k)^2
\end{split}
$$

且遞迴過程縮減，如下

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(3)$ 和遞迴 $F(3)$ 時所得到的 $F(2)$ 來計算 $F(4)$ ，可以再次降低運算的次數

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]
}

### 硬體加速 $F(n)$ 的手法

透過 [clz/ctz](https://en.wikipedia.org/wiki/Find_first_set) 搭配 fast doubling
1. 省略 $F(0)$，直接從 $F(1)$ 開始
2. clz/[ffs](https://man7.org/linux/man-pages/man3/ffs.3.html)
- `a = 0b1000`, `ffs(a)=4`
- `a = 0b1010`, `ffs(a)=2`
- `a = 0b1011`, `ffs(a)=1`

- 遇到 `0` -> fast doubling，求 $F(2n)$ 和 $F(2n+1)$
- 遇到 `1` -> fast doubling，求 $F(2n)$ 和 $F(2n+1)$，相加後求 $F(2n+2)$

**求解 $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

- 左邊第一欄，遇到 `1`，計算 $F(2n)=F(2*0)=0$ 以及 $F(2n+1)=F(1)=1 = a$、相加後求得 $b = F(2*0+2)=F(2)=1$
- 左邊第二欄，遇到 `0`，計算 $F(2n)=F(2*1)=1=a$ 以及 $F(2n+1)=F(3)=2=b$
- 左邊第三欄，遇到 `1`，計算 $F(2n)=F(4)=3$ 以及 $F(2n+1) = 5 = a$、相加後求得 $F(2n+2)=8=b$
- 左邊第四欄，遇到 `1`，計算 $F(2n)=F(10)=F(5)[2F(5+1)-F(5)]=5[2*8-5]=55$，計算 $F(2n+1)=F(11)=F(6)^2+F(5)^2=64+25=89=a$，相加得 $F(2n+2)=F(12)=55+89=144$

### Fibonacci 數的應用

[Pseudorandom number generator](https://en.wikipedia.org/wiki/Pseudorandom_number_generator)

### 加速 Fibonacci 運算

範例: 計算 $F(6)$

strict digraph G
{
	1[label="F(6)"]
    2[label="F(3)", color=red]
    3[label="F(4)"]
    4[label="F(2)", style=filled]
    5[label="F(1)", style=filled]
    6[label="F(3)", color=red]
    7[label="F(2)", style=filled]
    8[label="F(2)", style=filled]
    9[label="F(1)", style=filled]
    {rank = same; 2;3;}
    {rank = same; 4;5;6;7}
    {rank = same; 8;9}
    1 -> {2, 3}
    2 -> {4, 5}
    3 -> {6, 7}
    6 -> {8, 9};
}

- 根據 fast doubling 計算，但是還是有重複計算的部份，當 `target` 數值越大，重複的計算效能衝擊越顯著。

### Bottom-up Fast Doubling
>[Top-down vs Bottom-up approach in Dynamic Programming](https://www.enjoyalgorithms.com/blog/top-down-memoization-vs-bottom-up-tabulation)

以 87~10~ 為例:

                87 =  1010111            (87 >> i+1)
        i = 0 : 43 = (1010111 - 1) >> 1 = 101011
        i = 1 : 21 = ( 101011 - 1) >> 1 = 10101
        i = 2 : 10 = (  10101 - 1) >> 1 = 1010 
        i = 3 :  5 = (   1010 - 0) >> 1 = 101 
        i = 4 :  2 = (    101 - 1) >> 1 = 10 
        i = 5 :  1 = (     10 - 0) >> 1 = 1
        i = 6 :  0 = (      1 - 1) >> 1 = 0
                      	     ^
                         87 的第 i 個位元

移項並反過來看

                   (87 >> i+1)
        i = 6 :  1 =        0 << 1 + 1 = 1
        i = 5 :  2 =        1 << 1 + 0 = 10
        i = 4 :  5 =       10 << 1 + 1 = 101
        i = 3 : 10 =      101 << 1 + 0 = 1010
        i = 2 : 21 =     1010 << 1 + 1 = 10101
        i = 1 : 43 =    10101 << 1 + 1 = 101011
        i = 0 : 87 =   101011 << 1 + 1 = 1010111
                                     ^
                              87 的第 i 個位元

這邊感謝 [Eroiko 的筆記](https://hackmd.io/@Eroiko/fibdrv-impl) 幫助很大。

### $F(92)$ 以後的數值錯誤原因

測試結果如同作業說明及二補數計算，在返回值為 `long long` 的情況下 $F(93)$ 會造成 overflow

F(93) = -6246583658587674878

二補數計算
$$
\begin{split}
if(A+B) &>& T_{Max} (overflow)\\
result &=& A+B-2^{64}\\
&=& F(91)+F(92)-2^{64}\\
&=& -6246583658587674878
\end{split}
$$

## 初步支援大數運算

引入 `bn` 結構體，計算 92 項以後的費氏數列

/* number[size - 1] = msb, number[0] = lsb */
typedef struct _bn {
    unsigned int *number;
    unsigned int size;
    int sign;
} bn;

- `number` - 指向儲存的數值，之後以 **array** 的形式來取用
- `size` - 配置的記憶體大小，單位為 `sizeof(usigned int)`
- `sign` - 0 為 正數，1 為負數

由於大數沒辦法直接以數值的形式列出，故改用**字串**來做呈現，轉換部份利用 **ASCII** 特性並搭配 **fast doubling** 的邏輯來**組合**出 10 進位

Trace 其運作流程

static ssize_t fib_read(struct file *file,
                        char *buf,
                        size_t size,
                        loff_t *offset)
{
    bn *fib = bn_alloc(1);
    bn_fib_fdoubling(fib, *offset);
    // bn_fib(fib, *offset);
    char *p = bn_to_string(fib);
    size_t len = strlen(p) + 1;
    size_t left = copy_to_user(buf, p, len);
    // printk(KERN_DEBUG "fib(%d): %s\n", (int) *offset, p);
    bn_free(fib);
    kfree(p);
    return left;  // return number of bytes that could not be copied
}

首先宣告一指標 `fib` 指向 `bn` 結構體，並分配空間

`bn_alloc`

/*
 * alloc a bn structure with the given size
 * the value is initialized to +0
 */
bn *bn_alloc(size_t size)
{
    bn *new = (bn *) kmalloc(sizeof(bn), GFP_KERNEL);
    new->number = kmalloc(sizeof(int) * size, GFP_KERNEL);
    memset(new->number, 0, sizeof(int) * size);
    new->size = size;
    new->sign = 0;
    return new;
}

- `bn_alloc` 會使用 `kmalloc` 分配 `bn` 大小的空間，`kmalloc` 和 `vmalloc` 都用以分配核心的記憶體空間，但 `kmalloc` 會分配**連續的虛擬以及實體地址**，但 `vmalloc` 只保證**連續的虛擬地址**，**不保證連續的實體地址**， kernel 中常用 `kmalloc` 因為使用 `vamlloc` 需要進行映射 (mapping) 會讓效能變差
- 參考 [Memory Management APIs](https://www.kernel.org/doc/html/latest/core-api/mm-api.html) (useful GFP flag combinations):
- `GFP_KERNEL` is typical for kernel-internal allocations. The caller requires `ZONE_NORMAL` or a lower zone for direct access but can direct reclaim.
- 其中 Linux 會將 kernel 地址分成三部份 (`ZONE_DMA`、`ZONE_NORMAL` 和 `ZONE_HIGHMEM`)
- 之後便將其結構體中的元素做初始化

接下來將分配好空間的 `bn` 結構體 `fib` 以及要計算的 $n^{th}$ 費式數透過 `bn_fib_fdoubling` 計算

`bn_fib_fdoubling`

/*
 * calc n-th Fibonacci number and save into dest
 * using fast doubling algorithm
 */
void bn_fib_fdoubling(bn *dest, unsigned int n)
{
    bn_resize(dest, 1);
    if (n < 2) {  // Fib(0) = 0, Fib(1) = 1
        dest->number[0] = n;
        return;
    }

    bn *f1 = dest;        /* F(k) */
    bn *f2 = bn_alloc(1); /* F(k+1) */
    f1->number[0] = 0;
    f2->number[0] = 1;
    bn *k1 = bn_alloc(1);
    bn *k2 = bn_alloc(1);

    /* walk through the digit of n */
    for (unsigned int i = 1U << 31; i; i >>= 1) {
        /* F(2k) = F(k) * [ 2 * F(k+1) – F(k) ] */
        bn_cpy(k1, f2);
        bn_lshift(k1, 1);
        bn_sub(k1, f1, k1);
        bn_mult(k1, f1, k1);
        /* F(2k+1) = F(k)^2 + F(k+1)^2 */
        bn_mult(f1, f1, f1);
        bn_mult(f2, f2, f2);
        bn_cpy(k2, f1);
        bn_add(k2, f2, k2);
        if (n & i) {
            bn_cpy(f1, k2);
            bn_cpy(f2, k1);
            bn_add(f2, k2, f2);
        } else {
            bn_cpy(f1, k1);
            bn_cpy(f2, k2);
        }
    }
    // return f[0]
    bn_free(f2);
    bn_free(k1);
    bn_free(k2);
}

- 這裡的實作方法和 iterattion 版本的 fast doubling 一樣，只是在四則運算都分別利用其他函式處理，以 `bn_add` 為例

`bn_add` (`c = a + b`)

/*
 * c = a + b
 * Note: work for c == a or c == b
 */
void bn_add(const bn *a, const bn *b, bn *c)
{
    if (a->sign == b->sign) {  // both positive or negative
        bn_do_add(a, b, c);
        c->sign = a->sign;
    } else {          // different sign
        if (a->sign)  // let a > 0, b < 0
            SWAP(a, b);
        int cmp = bn_cmp(a, b);
        if (cmp > 0) {
            /* |a| > |b| and b < 0, hence c = a - |b| */
            bn_do_sub(a, b, c);
            c->sign = 0;
        } else if (cmp < 0) {
            /* |a| < |b| and b < 0, hence c = -(|b| - |a|) */
            bn_do_sub(b, a, c);
            c->sign = 1;
        } else {
            /* |a| == |b| */
            bn_resize(c, 1);
            c->number[0] = 0;
            c->sign = 0;
        }
    }
}

- 首先透過結構體中定義的 `sign` 判斷 `a, b` 正負號是否相等，如果相等相加過後輸出的正負號會相同，交由 `bn_do_add` 負責運算，且設定 `c` 符號相同
- 如果 `a, b` 符號不同，則透過比較正負號使 `a` 大於 `b`，再來判斷絕對值數值的大小，這會影響相加後結果的正負，例如
- 如果 `a = -100, b = 10`，做 `swap` 使得 `a = 10, b = -100`，透過比較絕對值後進行運算得到結果為**負的** `|b| - |a|`
- 如果 `a = 100, b = -10`，不會做 `swap` 且運算的結果為**正的** `|a| - |b|`
- 如果 `a, b` 不同號， 且 `|a| = |b|` ，則輸出為 `0`

實作判斷可以如下表格所示 (`a, b` 不同號，且 `a` > `b`)

| Condition | $\|a\|>\|b\|$ | $\|a\| < \|b\|$ |
| ---------- | ------------- | --------------- |
| Output `c` | $c = +(\|a\|-\|b\|)$ | $c = -(\|b\|-\|a\|)$ |

`bn_do_add`

/* |c| = |a| + |b| */
static void bn_do_add(const bn *a, const bn *b, bn *c)
{
    // max digits = max(sizeof(a) + sizeof(b)) + 1
    int d = MAX(bn_msb(a), bn_msb(b)) + 1;
    d = DIV_ROUNDUP(d, 32) + !d;
    bn_resize(c, d);  // round up, min size = 1

    unsigned long long int carry = 0;
    for (int i = 0; i < c->size; i++) {
        unsigned int tmp1 = (i < a->size) ? a->number[i] : 0;
        unsigned int tmp2 = (i < b->size) ? b->number[i] : 0;
        carry += (unsigned long long int) tmp1 + tmp2;
        c->number[i] = carry;
        carry >>= 32;
    }

    if (!c->number[c->size - 1] && c->size > 1)
        bn_resize(c, c->size - 1);
}

- 其中 `bn_msb` 會回傳傳入的 `bn` 結構體中所有 array 儲存的資料的 leading zero 有幾個，取較多的那個 + 1 就會是相加後最多有幾個 digits (進位)
- `bn_resize` 會將最終結果 `c` resize 成 `d` 的大小，代表著需要幾個 `unsigned int *number` 去儲存相加後的結果

假設結構體為 `uint8_t` 為例，若 `a = 0b11111111 = 255`，`b = 0b10000001 = 129` 我們想要獲得的答案為 `0b 1 10000000 = 384`，但只有 8 bit 的話無法表達，所以會輸出會用兩個 `uint8_t` 數值的陣列表示

digraph g{
    rankdir=LR
    node[shape=record, height=.1];
    labela[label="a"][shape=plaintext]
    labelb[label="b"][shape=plaintext]
    a[label="{1|1|1|1|1|1|1|1}"]
    b[label="{1|0|0|0|0|0|0|1}"]
    labela->a
    labelb->b
    labelc[label="c"][shape=plaintext]
    c2[label="{0|0|0|0|0|0|0|1}"]
    c1[label="{1|0|0|0|0|0|0|0}"]
    labelc->c1
    labelc->c2
}

`bn_do_sub`

/*
 * |c| = |a| - |b|
 * Note: |a| > |b| must be true
 */
static void bn_do_sub(const bn *a, const bn *b, bn *c)
{
    // max digits = max(sizeof(a) + sizeof(b))
    int d = MAX(a->size, b->size);
    bn_resize(c, d);

    long long int carry = 0;
    for (int i = 0; i < c->size; i++) {
        unsigned int tmp1 = (i < a->size) ? a->number[i] : 0;
        unsigned int tmp2 = (i < b->size) ? b->number[i] : 0;

        carry = (long long int) tmp1 - tmp2 - carry;
        if (carry < 0) {
            c->number[i] = carry + (1LL << 32);
            carry = 1;
        } else {
            c->number[i] = carry;
            carry = 0;
        }
    }

    d = bn_clz(c) / 32;
    if (d == c->size)
        --d;
    bn_resize(c, c->size - d);
}

同樣的，在 `bn_do_sub` 中，輸出 `c` 最大的 digit 數為 兩個 digit 數高的那個 (不發生借位)，計算 `carry` 值，若兩數值相減後 msb 還是 `1` 的話，代表發生借位，會將 `c->number[i]` 的值設定為 `carry + (1LL << 32)` ，這邊的 `(1LL << 32)` 看起來是要把第 32 bit (含) 以上的都設定為 0 (但實測後不做這件事情可以正確計算)

這裡的判斷是否借位可改寫成

- carry = (long long int) tmp1 - tmp2 - carry;

+ tmp1 - tmp2 - carry < 0 ? carry = 1 : 0;
+ c->number[i] = carry;
- if (carry < 0) {
-     c->number[i] = carry + (1LL << 32);
-     carry = 1;
- } else {
-     c->number[i] = carry;
-     carry = 0;
- }

一樣可以正確計算 Fibonacci number

`bn_sub`

/*
 * c = a - b
 * Note: work for c == a or c == b
 */
void bn_sub(const bn *a, const bn *b, bn *c)
{
    /* xor the sign bit of b and let bn_add handle it */
    bn tmp = *b;
    tmp.sign ^= 1;  // a - b = a + (-b)
    bn_add(a, &tmp, c);
}

這裡的 `bn_sub` 可以偷過 `bn_add` 來實作，因 `bn` 結構為 `unsigned int` 的 number 陣列，由另外的 `sign` 元素決定其正負，若要執行 `bn_sub`，可以透過反轉 b 的 `sign` 元素再進行 `bn_add` 即可

`bn_mult`

/*
 * c = a x b
 * Note: work for c == a or c == b
 * using the simple quadratic-time algorithm (long multiplication)
 */
void bn_mult(const bn *a, const bn *b, bn *c)
{
    // max digits = sizeof(a) + sizeof(b))
    int d = bn_msb(a) + bn_msb(b);
    d = DIV_ROUNDUP(d, 32) + !d;  // round up, min size = 1
    bn *tmp;
    /* make it work properly when c == a or c == b */
    if (c == a || c == b) {
        tmp = c;  // save c
        c = bn_alloc(d);
    } else {
        tmp = NULL;
        bn_resize(c, d);
    }

    for (int i = 0; i < a->size; i++) {
        for (int j = 0; j < b->size; j++) {
            unsigned long long int carry = 0;
            carry = (unsigned long long int) a->number[i] * b->number[j];
            bn_mult_add(c, i + j, carry);
        }
    }
    c->sign = a->sign ^ b->sign;

    if (tmp) {
        bn_cpy(tmp, c);  // restore c
        bn_free(c);
    }
}

實作一般直式長乘法，用輔助函式 `bn_mult_add` 負責將每一行的計算結果疊加上去，假設 `number` 為 4 bit，`a=0b0111 0111 (size=2), b=0b0101 0101 (size=2)` 計算過程如下


`bn_lshift`

/* left bit shift on bn (maximun shift 31) */
void bn_lshift(bn *src, size_t shift)
{
    size_t z = bn_clz(src);
    shift %= 32;  // only handle shift within 32 bits atm
    if (!shift)
        return;

    if (shift > z)
        bn_resize(src, src->size + 1);
    /* bit shift */
    for (int i = src->size - 1; i > 0; i--)
        src->number[i] =
            src->number[i] << shift | src->number[i - 1] >> (32 - shift);
    src->number[0] <<= shift;
}

此處實作先僅限於移動 32 bit 以內，函式內用一個 bitwise or `|` 來處理跨越 `number` 之間的 bit shift

`bn_to_string`

char *bn_to_string(const bn *src)
{
    // log10(x) = log2(x) / log2(10) ~= log2(x) / 3.322
    size_t len = (8 * sizeof(int) * src->size) / 3 + 2 + src->sign;
    char *s = kmalloc(len, GFP_KERNEL);
    char *p = s;

    memset(s, '0', len - 1);
    s[len - 1] = '\0';

    /* src.number[0] contains least significant bits */
    for (int i = src->size - 1; i >= 0; i--) {
        /* walk through every bit of bn */
        for (unsigned int d = 1U << 31; d; d >>= 1) {
            /* binary -> decimal string */
            int carry = !!(d & src->number[i]);
            for (int j = len - 2; j >= 0; j--) {
                s[j] += s[j] - '0' + carry;
                carry = (s[j] > '9');
                if (carry)
                    s[j] -= 10;
            }
        }
    }
    // skip leading zero
    while (p[0] == '0' && p[1] != '\0') {
        p++;
    }
    if (src->sign)
        *(--p) = '-';
    memmove(s, p, strlen(p) + 1);
    return s;
}

上述實作中關鍵的程式碼為

/* binary -> decimal string */
int carry = !!(d & src->number[i]);
for (int j = len - 2; j >= 0; j--) {
    s[j] += s[j] - '0' + carry;
    carry = (s[j] > '9');
    if (carry)
        s[j] -= 10;
}

- 由高位 (MSB) 開始檢測 binary 中每個 bit
- 若為 `1`，則輸出**乘二加一**
- 若為 `0`，則輸出**乘二**

### 計算 F~93~ (包含) 之後的 Fibonacci 數

參考 [AdrianHuang/fibdrv](https://github.com/AdrianHuang/fibdrv/tree/big_number) 實作程式碼

### bignum

以數字陣列來儲存(同時也可以指定陣列大小)，以 `uint8_t` 為例，其數值範圍在 0\~255，若要表示 300 則以數字陣列 `digit` 來表示，假設陣列大小為 3，則 300 表示為

$$
\begin{split}
300&:&&00000000 \space &00000001 \space &00101100 \\
digit&:&&digit[2] &digit[1]&digit[0]\\
value&:& &0&1&44&
\end{split}
$$
然後在透過 [format.c](https://github.com/sysprog21/bignum/blob/master/format.c) 格式轉換為十進位

可以透過以下兩種演算法實現大數的乘法
- **Karatsuba 演算法**
- **Schönhage–Strassen Algorithm**

## 改善大數運算
### 改善方案 1: 改寫 `bn_fib_fdoubling`

直接引入 [Reference](https://hackmd.io/@sysprog/linux2023-fibdrv/%2F%40sysprog%2Flinux2023-fibdrv-d#%E6%94%B9%E5%96%84%E6%96%B9%E6%A1%88-1-%E6%94%B9%E5%AF%AB-bn_fib_fdoubling) 竟然報錯

sudo ./client > out
*** stack smashing detected ***: terminated
Aborted

查看 `out` 檔案發現計算的值有很大的問題

Reading from /dev/fibonacci at offset 0, returned the sequence 0.
Reading from /dev/fibonacci at offset 1, returned the sequence 1.
Reading from /dev/fibonacci at offset 2, returned the sequence 10.
Reading from /dev/fibonacci at offset 3, returned the sequence 24.
Reading from /dev/fibonacci at offset 4, returned the sequence 392.
Reading from /dev/fibonacci at offset 5, returned the sequence 724.

在**尚未優化的版本中**， bignum 版本和正常版本的運算可以直接對應

**不支援大數的 fast doubling iteration**

static long long fib_sequence_fd_iter(long long k)
{
    // Fibonacci sequence: 0, 1, 1, 2, 3, 5, 8, 13, ...
    if (k <= 2)
        return !!k;
...
    for (uint64_t i = count, f2k0, f2k1; i-- > 0;) {
        /*  F(2k) = F(k)[2F(k+1) - F(k)]
         *  F(2k+1) = F(k+1)^2 + F(k)^2
         */
        f2k0 = fk0 * ((fk1 << 1) - fk0);
        f2k1 = fk1 * fk1 + fk0 * fk0;

        if (k & (1UL << i)) {
            fk0 = f2k1;
            fk1 = f2k0 + f2k1;
        } else {
            fk0 = f2k0;
            fk1 = f2k1;
        }
    }
    return fk0;
}

**支援大數的 fast doubling iteration**

void bn_fib_fdoubling(bn *dest, unsigned int n)
{
    bn_resize(dest, 1);
    if (n < 2) {  // Fib(0) = 0, Fib(1) = 1
        dest->number[0] = n;
        return;
    }
...
    /* walk through the digit of n */
    for (unsigned int i = 1U << 31; i; i >>= 1) {
        /* F(2k) = F(k) * [ 2 * F(k+1) – F(k) ] */
        bn_cpy(k1, f2);
        bn_lshift(k1, 1);      // k1 = 2 * F(k+1)
        bn_sub(k1, f1, k1);    // k1 = 2 * F(k+1) - F(k)
        bn_mult(k1, f1, k1);   // k1 = F(k) * (2F(k+1) - F(k))
        /* F(2k+1) = F(k)^2 + F(k+1)^2 */
        bn_mult(f1, f1, f1);   // f1 = F(k)^2
        bn_mult(f2, f2, f2);   // f2 = F(k+1)^2
        bn_cpy(k2, f1);        // k2 = f1 = F(k)^2
        bn_add(k2, f2, k2);    // k2 = F(k+1)^2 + F(k)^2
        if (n & i) {
            bn_cpy(f1, k2);    // f1 = F(k+1)^2 + F(k)^2
            bn_cpy(f2, k1);    // f2 = F(k) * (2F(k+1) - F(k))
            bn_add(f2, k2, f2);
        } else {
            bn_cpy(f1, k1);    // f1 = F(k) * (2F(k+1) - F(k))
            bn_cpy(f2, k2);    // f2 = F(k+1)^2 + F(k)^2
        }
    }
...
}

- 注意根據函式引數， 我們需要的計算結果為 `f1` 也就是傳入的 `dest`

void bn_fib_fdoubling_v1(bn *dest, unsigned int n)
{
    ...
    for (unsigned int i = 1U << (31 - __builtin_clz(n)); i; i >>= 1) {
        /* F(2k) = F(k) * [ 2 * F(k+1) – F(k) ] */
        /* F(2k+1) = F(k)^2 + F(k+1)^2 */
        bn_lshift_2(f2, 1, k1);// k1 = 2 * F(k+1)
        bn_sub(k1, f1, k1);  // k1 = 2 * F(k+1) – F(k)
        bn_mult(k1, f1, k2); // k2 = k1 * f1 = F(2k)
        bn_mult(f1, f1, k1); // k1 = F(k)^2
        bn_swap(f1, k2);     // f1 <-> k2, f1 = F(2k) now
        bn_mult(f2, f2, k2); // k2 = F(k+1)^2
        bn_add(k1, k2, f2);  // f2 = f1^2 + f2^2 = F(2k+1) now
        if (n & i) {
            bn_swap(f1, f2);    // f1 = F(2k+1)
            bn_add(f1, f2, f2); // f2 = F(2k+2)
        }
    }
    ...
}

而此改善方案旨在降低使用 `malloc` 及 `memcpy` 的次數，首先新的 `bn_lshift_2` 可以將第一個引數 `src` 左移第二個引數 `shift` 後儲存至第三個引數 `dest`

`bn_lshift_2` 函式修改
>[wanghanchi](https://hackmd.io/@wanghanchi/linux2023-fibdrv#%E5%BC%95%E5%85%A5%E6%9B%B4%E4%B8%80%E6%AD%A5%E7%9A%84%E5%84%AA%E5%8C%96)

void bn_lshift_2(const bn *src, size_t shift, bn *dest)
{
    size_t z = bn_clz(src);
    shift %= 32;  // only handle shift within 32 bits atm
    if (!shift)
        return;

    if (shift > z) {
        bn_resize(dest, src->size + 1);
+       dest->number[src->size] = src->number[src->size - 1] >> (32 - shift);
    } else {
        bn_resize(dest, src->size);
    }
    /* bit shift */
    for (int i = src->size - 1; i > 0; i--)
        dest->number[i] =
            src->number[i] << shift | src->number[i - 1] >> (32 - shift);
    dest->number[0] = src->number[0] << shift;
}

結果在測試時還是錯誤

make check FIBMODE=3

檢查過後發現在 `bn_mult` 中當資料來源與目的**沒有**重疊時，並沒有將其 `number` 初始化，以至於產生非預期的取值，之前沒有發現是因為在 bignum 的 fast-doubing 版本中使用 `bn_mult` 的案例都屬於 `(c == a || c == b)`

void bn_mult(const bn *a, const bn *b, bn *c)
{
    // max digits = sizeof(a) + sizeof(b))
    int d = bn_msb(a) + bn_msb(b);
    d = DIV_ROUNDUP(d, 32) + !d;  // round up, min size = 1
    bn *tmp;
    /* make it work properly when c == a or c == b */
    if (c == a || c == b) {
        tmp = c;  // save c
        c = bn_alloc(d);
    } else {
        tmp = NULL;
+        for (int i = 0; i < c->size; i++)
+            c->number[i] = 0;
        bn_resize(c, d);
    }

    for (int i = 0; i < a->size; i++) {
        for (int j = 0; j < b->size; j++) {
            unsigned long long int carry = 0;
            carry = (unsigned long long int) a->number[i] * b->number[j];
            bn_mult_add(c, i + j, carry);
        }
    }
    c->sign = a->sign ^ b->sign;

    if (tmp) {
        bn_swap(tmp, c);  // restore c
        bn_free(c);
    }
}

修正完成後此節改善方案可通過測試。

### 改善方案 2: 運用 Q-Matrix

[參考網站](https://chunminchang.github.io/blog/post/matrix-difference-equation-for-fibonacci-sequence) 所提供的 fast doubling 方法如下

$$
\begin{split}
\begin{bmatrix}
F(2n+1) & F(2n)\\
F(2n) & F(2n-1)
\end{bmatrix} &=
\begin{bmatrix}
1 & 1 \\
1 & 0
\end{bmatrix}^{2n}
\end{split}
$$

左右欄對調
$$
\begin{split}
\begin{bmatrix}
F(2n) & F(2n+1)\\
F(2n-1) & F(2n)
\end{bmatrix} &=
\begin{bmatrix}
1 & 1 \\
0 & 1
\end{bmatrix}^{2n}
\end{split}
$$

可以將第一欄取出為

$$
\begin{split}
\begin{bmatrix}
F(2n)\\
F(2n-1)
\end{bmatrix} &=
\begin{bmatrix}
1 & 1 \\
0 & 1
\end{bmatrix}^{2n}
\begin{bmatrix}
1 \\
0
\end{bmatrix}\\
&=
\begin{bmatrix}
1 & 1 \\
0 & 1
\end{bmatrix}^{2n}
\begin{bmatrix}
F(1) \\
F(0)
\end{bmatrix}
\end{split}
$$

列對調
$$
\begin{split}
\begin{bmatrix}
F(2n-1)\\
F(2n)
\end{bmatrix} &=
\begin{bmatrix}
0 & 1 \\
1 & 1
\end{bmatrix}^{2n}
\begin{bmatrix}
0 \\
1
\end{bmatrix}\\
&=
\begin{bmatrix}
0 & 1 \\
1 & 1
\end{bmatrix}^{2n}
\begin{bmatrix}
F(0) \\
F(1)
\end{bmatrix}
\end{split}
$$

觀察 [sysprog21/bignum](https://github.com/sysprog21/bignum) 中費氏數列的實作函式 [fibonacci](https://github.com/sysprog21/bignum/blob/master/fibonacci.c)，會發現雖看似採用 fast doubling，但實際是 Q-matrix 這樣的變形，推導如下:
$$
\begin{split}
\begin{bmatrix}
F(2n-1) \\
F(2n)
\end{bmatrix} &=
\begin{bmatrix}
0 & 1 \\
1 & 1
\end{bmatrix}^{2n}
\begin{bmatrix}
F(0) \\
F(1)
\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)^2 + F(n-1)^2\\
F(n)F(n) + 2F(n)F(n-1)
\end{bmatrix}
\end{split}
$$

整理後可得
$$
\begin{split}
F(2k-1) &= F(k)^2+F(k-1)^2 \\
F(2k) &= F(k)[2F(k-1) + F(k)]
\end{split}
$$

使用上述公式改寫 `bn_fib_fdoubling`，搭配使用 `clz` ，後者可讓 n 值越小的時候，減少越多次迴圈運算，從而達成加速。

### 改善方案 3: 引入 memory pool
原本在實作中在計算前會使用 `bn_resize` 來確保有足夠的空間儲存計算結果 (number 的數量)，而現在引入 `capacity` 的方式來管理 `bn` 的可用大小，減少 `bn_resize` 呼叫 `realloc` 的次數。

static int bn_resize(bn *src, size_t size)
{
    if (!src)
        return -1;
    if (size == src->size)
        return 0;
    if (size == 0)  // prevent krealloc(0) = kfree, which will cause problem
        return bn_free(src);
    if (size > src->capacity) { /* need to allocate larger capacity */
        src->capacity = (size + (ALLOC_CHUNK_SIZE - 1)) & ~(ALLOC_CHUNK_SIZE - 1); // ceil to 4*n
        src->number = krealloc(src->number, sizeof(int) * src->capacity, GFP_KERNEL);
    }
    if (!src->number) {  // realloc fails
        return -1;
    }
    if (size > src->size) { /* memset(src, 0, size) */
        for (int i = src->size; i < size; i++)
            src->number[i] = 0;
    }
    src->size = size;
    return 0;
}

- 只有當 `size` 超過 `capacity` 時才會 `realloc`，並以 4 為單位
- 計算仍以 `size` 作為範圍，不必計算多餘的空間
- trim 時只要縮小 size 就好，不需要實際 `realloc` 來縮小空間

## [Part 1: Introduction](http://derekmolloy.ie/writing-a-linux-kernel-module-part-1-introduction/) 閱讀筆記
>This article is focused on the system configuration, tools and code required to build and deploy a “Hello World!” kernel module.

### 什麼是 Kernel Module?

Loadable kernel module (LKM) 是一個在 Linux kernel run time 下新增、移除程式的機制。這樣使得 kernel 無須知道硬體是如何運作的便可以使 kernel 和 硬體進行通訊 (ideal for device drivers!)
- LKM 的替代方案就是將每個驅動都直接灌到 Linux Kernel 中

如果沒有這個東西的話， Linux kernel 將會非常的龐大，且要更新 hardware driver 的話每次都要重新建構 kernel。 LKM 的缺點就是每個 device 的 driver 都需要被 maintain

LKMs 是在 runtime 被加載的，但並不是在 user space 運行。

Kernel modules 在 kernel space 運行，Application 在 user space 運行

- kernel space 和 user space 都有自己**唯一且不重疊的記憶體位置**，確保應用程式不管在任何硬體平台上在 user space 都有 consistent view。

### 為什麼要寫 kernel module?

在嵌入式 Linux 中利用 `sysfs` 以及低階 (low-level) 檔案操作來與電子電路進行互動，這樣的方法非常沒有效率。但是，這樣的方法在各種應用程式上已經足夠 (原文提供證明)。

而替代方案就是使用支援中斷 (interrupt) 的 kernel module，但 kernel code 是非常編寫和除錯的。

:::warning
在寫測試 LKMs 時是非常容易 crash system 的，是有可能損壞檔案系統的，若有需要就要備份
:::

### The Module Code

一般典型的電腦程式在 runtime life cycle 非常直觀。 loader 分配記憶體給程式，然後載入任何需要的 libraries。 指令執行的起始點通常東在 `main()`，然後接著執行、回報錯誤、例外狀況，分配動態記憶體，然後最終運行完成。在程式離開時，作業系統會將 memroy leaks 以及沒有 free 乾淨的 memory 丟到 pool 中。

**但 kernel module 沒有這些東西**，且沒有 `main()` function!

以下是一些主要區別:
- **不會按照順序執行**: kernel module 是用自己的 initialization function 來註冊自己 handle request，該函數可以運行然後中止。它可以 handle 的類型會在 module code 中定義。這和 GUI 中的 [event-driven programming model](https://en.wikipedia.org/wiki/Event-driven_programming) 非常類似。
- **沒有自動清理 (automatic cleanup)**: 分配給 module 的任何資源 (resources) 都必須在卸載 (unloaded) module 的時候釋放掉 (released) ，否則在重開機之前這些資源**不可用**
- **沒有 `printf()` 函式**: kernel code 無法訪問 (access) user space 的 libraries。kernel module 在 kernel space 生成及執行，**有自己的 memory address space**， kernel space 和 user space 的界面 (interface) 被明確定義，但確實有一個 `printk()` 函數可以輸出 information，且可以在 user space 查看
- **可以被中斷 (interrupt)**: kernel module 可以同時被多個不同的程式 (programs) 或 行程 (process) 使用，須仔細的建構以確保在被中斷時具有一致且有效的行為。就算是單核心的 processor ，也還是要考慮到多行程的問題。
- **具有更高級別的權限**: 一般來說，分配給 kernel module 的 cpu cycle 會比 user space 的 program 來的多，但是就必須要注意 kernel module 不要對整體效能產生不利的影響。
- **不支援浮點數**: kernel code 使用 traps 將系統從整數模式轉換為浮點數模式，但是在 kernel space 下難以執行這些 traps，替代方案是手動保存和恢復浮點數運算，但是最好還是留給 user space code 來處理。
- Reference [Linux 核心的浮點數運算](https://hackmd.io/@sysprog/linux2023-fibdrv/%2F%40sysprog%2Flinux2023-fibdrv-b#-Linux-%E6%A0%B8%E5%BF%83%E7%9A%84%E6%B5%AE%E9%BB%9E%E6%95%B8%E9%81%8B%E7%AE%97)

## [Part 2: A Character Device](http://derekmolloy.ie/writing-a-linux-kernel-module-part-2-a-character-device/) 閱讀筆記

### Character Device Drivers

ChatGPT 給的解釋
:::info
Character Device 是指一種在 Unix/Linux 系統中的設備類型，該設備對外提供了一個字符（Character）流的接口，用於與其他軟件或硬件進行通信。一些例子包括終端設備（如 tty）、滑鼠、鍵盤、語音輸入、音訊裝置等。

Character Device 與另一種設備類型 Block Device 不同。Block Device 是指提供塊（Block）訪問方式的設備，例如硬碟驅動器，其將數據劃分為固定大小的塊（通常為512位元組或4KB），用於高效地存儲和讀取數據。

在 Linux 系統中，Character Device 和 Block Device 均被視為一種特殊的檔案，可以使用文件描述符（File Descriptor）對其進行讀寫操作。Character Device 提供了一種簡單的、無緩衝的 I/O 模型，允許使用者以字節為單位進行讀寫操作。相較之下，Block Device 的 I/O 模型則更複雜，需要進行塊緩存、讀寫計劃等操作，以達到更高的性能。
:::

Character decive 一般在 user application 收送資料，就像是 pipes 或 serial ports，立即讀寫 character-by-character stream 中的位元組資料。為典型的驅動軟體提供框架，連接 serial communcations、video capture、audio devices，其主要的替代品是 [block device](https://www.codingame.com/playgrounds/2135/linux-filesystems-101---block-devices/about-block-devices)， block device 的行為和常規的文件相似，允許透過讀取、寫入、查找等等操作來查看或操作 buffered array of cached data

這兩種 device types 都可以被 attached 到 file system tree 的 device file 來 access

本文提供了一個運行在 linux kernel space 下，且可以讓 Linux user-space program 和 loadable kernel module (LKM) 之間 pass information 的 character driver，本例中， C user-space application 發送一段 string 給 LKM，然後 LKM 會回傳其收到的字節數。接著解釋為何要解決同步的問題 (本文透過 mutex lock 解決)

### Major and Minor Numbers

Device drivers 有一個 major 和 minor 號碼， major number 是 kernel 在當這個 device 被 accessed 時用來識別正確的 device driver，而 minor number 取決於 device，並在驅動程式內部處理

:/dev$ ls -l |grep i2c
crw-------   1 root  root     89,     0  三  17 19:19 i2c-0

如果是 character deviceds ，首欄字母為 `c`，如果是 block device，首欄字母為 `b`，接下來就是常見的 access permission, owner, grops.

可以手動建立 block 或 character device，例如 `sudo mknod /dev/test c 92 1`，但是這個方法必須確認 `92` 這個數字沒有被使用

### The File Operation Data Structure
>`file_operations` 的 data structure 定義於 [`/linux/fs.h`](https://github.com/torvalds/linux/blob/master/include/linux/fs.h)，內部結構包含 function pointer 並允許設計人員定義以下操作。

struct file_operations {
   struct module *owner;                             // Pointer to the LKM that owns the structure
   loff_t (*llseek) (struct file *, loff_t, int);    // Change current read/write position in a file
   ssize_t (*read) (struct file *, char __user *, size_t, loff_t *);    // Used to retrieve data from the device
   ssize_t (*write) (struct file *, const char __user *, size_t, loff_t *);   // Used to send data to the device
   ssize_t (*aio_read) (struct kiocb *, const struct iovec *, unsigned long, loff_t);  // Asynchronous read
   ssize_t (*aio_write) (struct kiocb *, const struct iovec *, unsigned long, loff_t); // Asynchronous write
   ssize_t (*read_iter) (struct kiocb *, struct iov_iter *);            // possibly asynchronous read
   ssize_t (*write_iter) (struct kiocb *, struct iov_iter *);           // possibly asynchronous write
   int (*iterate) (struct file *, struct dir_context *);                // called when VFS needs to read the directory contents
   unsigned int (*poll) (struct file *, struct poll_table_struct *);    // Does a read or write block?
   long (*unlocked_ioctl) (struct file *, unsigned int, unsigned long); // Called by the ioctl system call
   long (*compat_ioctl) (struct file *, unsigned int, unsigned long);   // Called by the ioctl system call
   int (*mmap) (struct file *, struct vm_area_struct *);                // Called by mmap system call
   int (*mremap)(struct file *, struct vm_area_struct *);               // Called by memory remap system call 
   int (*open) (struct inode *, struct file *);             // first operation performed on a device file
   int (*flush) (struct file *, fl_owner_t id);             // called when a process closes its copy of the descriptor
   int (*release) (struct inode *, struct file *);          // called when a file structure is being released
   int (*fsync) (struct file *, loff_t, loff_t, int datasync);  // notify device of change in its FASYNC flag
   int (*aio_fsync) (struct kiocb *, int datasync);         // synchronous notify device of change in its FASYNC flag
   int (*fasync) (int, struct file *, int);                 // asynchronous notify device of change in its FASYNC flag
   int (*lock) (struct file *, int, struct file_lock *);    // used to implement file locking
   …
} __randomize_layout;

- 結尾的 `__randomize_layout` 標示可參考 [Linux Kernel之randomized layout](http://xuxinting.cn/2020/12/20/2020-12-20-kernel-randomize-layout/)，其目的在於增強 kernel 的安全性

這個 driver 提供了 `read`, `write`, `open`, `release` 等 system call file operation，如果沒有實作的話，那麼這些 function pointer 會指向 `NULL`

### The Device Driver Source Code

本節[原文](http://derekmolloy.ie/writing-a-linux-kernel-module-part-2-a-character-device/)以 BeagleBone 做為舉例，但其架構可從 [fibdrv](https://github.com/sysprog21/fibdrv) 找到相對應的 `init()`、 `exit()`，以及 `file_operations` 等等實作，其中
- `dev_open()`: Called each time the device is opened from user space.
- `dev_read()`: Called when data is sent from the device to user space.
- `dev_write()`: Called when data is sent from user space to the device.
- `dev_release()`: Called when the device is closed in user space.
- `llseak()`: Change current read/write position in a file
- 在 userr-level 的 entry point 為`lseek(int __fd, off_t __offset, int __whence)` ，控制檔案的讀寫位置，引數 `__offset` 根據引數 `__whence` 來移動讀寫位置的位移數， `__whence` 可以是以下其中一種:
- `SEEK_SET`: 引數 `__offset` 即為新的讀寫位置
- `SEEK_CUR`: 以目前的讀寫位置往後增加 `__offset` 個位移量
- `SEEK_END`: 將讀寫位置指向檔案未端後在增加 `__offset` 個位移量
- 在 `fibdrv.c` 中的 `fib_device_lseek` 有對應的實作

在 user space 呼叫 `read()` 函式時，是**無法直接指定文件 offset** 的，文件的偏移量是和 file descriptor 的屬性，只能透過呼叫 `lseek()` 函式或其他類似的 system call 來修改，故若要指定文件偏移量，需在**讀取文件之前使用 `lseek()` 設定偏移量，然後在呼叫 `read()` 函式進行讀取**，例如 `client.c` 中的作法

for (int i = 0; i <= offset; i++) {
    lseek(fd, i, SEEK_SET);
    // cppcheck-suppress unreadVariable
    sz = read(fd, buf, 1);
    printf("Reading from " FIB_DEV
           " at offset %d, returned the sequence "
           "%s.\n",
           i, buf);
}

在原文的留言處有提到
>**devnull**: You should add “.owner = THIS_MODULE,” in struct file_operations fops or you will get nasty kernel oopses when unloading or rebooting. Took me 2 weeks to find out.

- 在 fibdrv 中有做

## fibdrv 核心模組內部
可以發現有些東西是在 user-level 運作的

查看 `client.c`

#include <fcntl.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/types.h>
#include <unistd.h>

#define FIB_DEV "/dev/fibonacci"

int main()
{
    long long sz;

    char buf[1];
    char write_buf[] = "testing writing";
    int offset = 100; /* TODO: try test something bigger than the limit */

    int fd = open(FIB_DEV, O_RDWR);
    if (fd < 0) {
        perror("Failed to open character device");
        exit(1);
    }

    for (int 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 (int 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);
    }

    for (int i = offset; i >= 0; 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);
    }

    close(fd);
    return 0;
}

上述這段 code 會用系統呼叫 `open` 打開 device file `/dev/fibonacci`，其中也使用了 `open`、`write`、`lseek`、`read` 等系統呼叫來對 `fibonacci` 進行操作，操作之後就可以**從 kernel 讀取出之前運算出來的 fibonacci 數值**，然後就可以在 user space 中進行輸出

`client.c`

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);
}

- 此處透過 `read` 系統呼叫來得到輸出

查看 `fibdrv.c` (參考 [物件導向程式設計篇](https://hackmd.io/@sysprog/c-oop#%E4%BD%A0%E6%89%80%E4%B8%8D%E7%9F%A5%E9%81%93%E7%9A%84-C-%E8%AA%9E%E8%A8%80%EF%BC%9A%E7%89%A9%E4%BB%B6%E5%B0%8E%E5%90%91%E7%A8%8B%E5%BC%8F%E8%A8%AD%E8%A8%88%E7%AF%87) (designated initializers)、[file_operations Struct Reference](https://docs.huihoo.com/doxygen/linux/kernel/3.7/structfile__operations.html))

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_read` 宣告為 `static` (表示其能見度只有在該檔案)，但在 `fib_fops` 被初始化成 `read` function pointer，所以之後只要操作該 function pointer，就會像是在操作 `fib_read`，且可以避免**命名衝突**

這裡實作了 `fib_read` 函數內將 `fib_sequence` 的值回傳，透過使用者給定不同的 `offset` 作為 Fibonacci 數列的 $x$ 回傳 $fib(x)$

### [Linux Virtual File System (VFS)](https://www.win.tue.nl/~aeb/linux/lk/lk-8.html)


在傳統 UNIX 系統中，檔案系統是固定的，但是在 Linux 中，為了結合各個檔案系統，因而加上了一層虛擬檔案系統 (VFS)， VFS 是一組**檔案操作的抽象界面**，可以將任何真實的檔案系統透過 VFS **掛載**到 Linux 中。

VFS 並不直接處理檔案格式，而是規定這些處理請求的介面及操作語意，然後交由真實的檔案系統 (像是 EXT2) 去處理。

而透過 VFS， `fibdrv` 核心模組可以將計算出來 Fibonacci 數讓 `client.c` 程式得以存取
Linux 的裝置驅動程式大致分為:
- Character Device Driver
- Block Device Driver
- Network Device Driver

參照 [Linux 核心設計: 檔案系統概念及實作手法](https://hackmd.io/@sysprog/linux-file-system)

### Makefile

- [How to autofill "obj-y" or "xxx-objs" in linux kernel module Makefile?](https://stackoverflow.com/questions/67673126/how-to-autofill-obj-y-or-xxx-objs-in-linux-kernel-module-makefile)
- [objs in Makefile breaks kernel module](https://stackoverflow.com/questions/19934142/objs-in-makefile-breaks-kernel-module)

在 `Makefile` 中，`make check` 會去加載編譯好的 `fibdrv` kernel module，並將 `client` 輸出儲存至 `out`，透過以下指令

diff -u out scripts/expected.txt && $(call pass)

來檢驗輸出和預期是否一樣，在第一版本的 `fibdrv` 中僅能輸出正確的 $Fib(92)$

Reading from /dev/fibonacci at offset 92, returned the sequence 7540113804746346429.
Reading from /dev/fibonacci at offset 93, returned the sequence 7540113804746346429.
Reading from /dev/fibonacci at offset 94, returned the sequence 7540113804746346429.

在和目標檔案 `expected.txt` 比對時會給 `pass` ，因為 `expected.txt` 本來就給定這樣的預期輸出，若要檢測後續的 Fibonacci number 是否正確則連同 `expected.txt` 也要一起改

### `copy_[to/from]_user`

- user-space 無法直接存取 kernel-space 的記憶體
- Linux device driver 與 user-space 間的 I/O 會與 `fops->read`、`fops->write`、`fops->ioctl` 這三個 system call 有關

不論是從 user-space 讀取資料至 kernel-space，或是將 kernel-space 的資料寫至 user-space, 必須透過 kernel 提供的兩個 API 來進行
- `long copy_tp_user(void *to, const void * from, long n)`
- `long copy_from_user(void *to, const void* from, long n)`

**`copy_to_user`**
- `to`: 資料的目的位置 (指向 user-space 記憶體的指標)
- `from`: 資料的來源位址 (指向 kernel-space 記憶體的指標)

**`copy_from_user`**
- `to`: 資料的目的位置 (指向 kernel-spcae 記憶體的指標)
- `from`: 資料的來源位置 (指向 user-space 記憶體的指標)

Kernel 裡面有 [copy_to_user](https://elixir.bootlin.com/linux/latest/ident/copy_to_user)，可以把資料從 kernel space copy 到 user space
- 注意到 `copy_to_user` 其實是有成本的

## 核心模式的時間測量
>參照 [核心模式的時間測量](https://hackmd.io/@sysprog/linux2023-fibdrv/%2F%40sysprog%2Flinux2023-fibdrv-c)、[Linux 核心設計: Timer 及其管理機制](https://hackmd.io/@sysprog/linux-timer)

如果只在 user space 做測量，那就只能測量進出 kernel 內部的時間，測量不到 kernel 內部，進出 kernel 其實有其他的成本開銷 (例如 [mode switch](https://www.ibm.com/docs/en/aix/7.1?topic=performance-mode-switching))

這時候就需要用到 `hrtimer` (high-resolution timer)，在 linux 上的通常可以達到 1 micro second 的精準度

`jiffies` 是一種計時機制，計算自開機以來計時器中斷發生的次數，**較舊的** Linux 核心有提到 timer wheel，而一個新的機制是將計時機制建立在新資料結構 `ktime_t` 上
>參照 [The high-resolution timer API](https://lwn.net/Articles/167897/)、[ktime 相關 API](https://www.kernel.org/doc/html/latest/core-api/timekeeping.html)

### 關於 `client.c`

根據[作業說明](https://hackmd.io/@sysprog/linux2023-fibdrv/%2F%40sysprog%2Flinux2023-fibdrv-c#%E9%97%9C%E6%96%BC-clientc)描述，在 user-mode 的位置配置一個 buffer 空間時， kernel driver 不能直接寫入該地址，而是要透過 [copy-to-user](https://elixir.bootlin.com/linux/latest/ident/copy_to_user)，將想傳給 user-mode (運作中的 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) 研究指出，從 kernel-level 複製資料到 user-level 的時間成本是每位元組 22ns，故在進行效能分析時，**必須要考慮到 copy_to_user 函式的時間開銷**，特別留意**資料大小成長後造成的量測誤差**

## Linux 效能分析的提示
- 傳統多核心的系統使用 [SMP](https://zh.wikipedia.org/zh-tw/%E5%AF%B9%E7%A7%B0%E5%A4%9A%E5%A4%84%E7%90%86) 進行設計，各個 CPU 共享相同的記憶體，每個 CPU 都可以訪問記憶體中的任何地址，**所需要的時間都是相同的**
- 由於 SMP 在擴展上的限制，非統一記憶體存取架構 (NUMA)因而誕生，可以把更多數量的 CPU 組合起來， CPU 可以同時訪問不同的記憶體，**大幅提高並行性**， NUMA 模式下，處理器被劃分為多個節點，每個節點有自己的 local memory，同樣的每個 CPU 都可以訪問所有的記憶體位址，但離自己越遠則需要花費比較多的時間。


參考[Linux 效能分析的提示](https://hackmd.io/@sysprog/linux2023-fibdrv/%2F%40sysprog%2Flinux2023-fibdrv-c#-Linux-%E6%95%88%E8%83%BD%E5%88%86%E6%9E%90%E7%9A%84%E6%8F%90%E7%A4%BA)、[KYG-yaya573142](https://hackmd.io/@KYWeng/rkGdultSU)，使用 [processor affinity / CPU pinning](https://en.wikipedia.org/wiki/Processor_affinity) 讓行程在特定的 CPU 中執行不受排程的干擾

$ cat /proc/cpuinfo | grep "^processor" | wc -l
8

也可以使用 `perf record` 來取樣並紀錄目標的執行狀態

sudo perf record -g --call-graph dwarf ./measure

- `-g` 回同時紀錄取樣點的 stack trace
- `--call-graph` 指定走訪 stack trace 的方法 follow [The DWARF Debugging Standard](https://dwarfstd.org/)
- 記得要先 `make load` 載入 module

### 限定 CPU 給特定的程式使用

修改 `/etc/default/grub` 內的 `GRUP_CMDLINE_LINUX_DEFAULT` ，加入 `isolcpus=7` 來指定編號 `7` 的核心 **不被排程器賦予任務**，修改完成後 `sudo update-grub` 來更新設定
- `quiet`: 啟動系統的過程中，如果沒有 `quiet`， kernel 就會輸出很多訊息，包括啟動過程中運行了哪些程式，如果系統可以正常啟動，通常就不會需要這些訊息，故會設定成 `quiet`
- `splash`: 與可視化界面有關
- `GRUB_CMDLINE_LINUX`: 一直生效
- `GRUB_CMDLINE_LINUX_DEFAULT`: 恢復模式 (recovery mode) 下不會運作

### 排除干擾效能的因素

- 抑制 [address space layout randomization](https://en.wikipedia.org/wiki/Address_space_layout_randomization) (ASLR)

$ sudo sh -c "echo 0 > /proc/sys/kernel/randomize_va_space"

- 設定 scaling_governor 為 performance。

for i in /sys/devices/system/cpu/cpu*/cpufreq/scaling_governor
do
    echo performance > ${i}
done

以我的電腦來說，會將 `performance` 分別寫入

/sys/devices/system/cpu/cpu0/cpufreq/scaling_governor
/sys/devices/system/cpu/cpu1/cpufreq/scaling_governor
/sys/devices/system/cpu/cpu2/cpufreq/scaling_governor
/sys/devices/system/cpu/cpu3/cpufreq/scaling_governor
/sys/devices/system/cpu/cpu4/cpufreq/scaling_governor
/sys/devices/system/cpu/cpu5/cpufreq/scaling_governor
/sys/devices/system/cpu/cpu6/cpufreq/scaling_governor
/sys/devices/system/cpu/cpu7/cpufreq/scaling_governor

參考 [CPU frequency scaling](https://wiki.archlinux.org/title/CPU_frequency_scaling)，會讓 CPU 在最高頻率下運轉


- 針對 Intel 處理器，關閉 turbo mode

$ sudo sh -c "echo 1 > /sys/devices/system/cpu/intel_pstate/no_turbo"

- 關閉 SMT (Hyper-threading)

$ sudo sh -c "echo off > /sys/devices/system/cpu/smt/control"

## gnuplot

set title "Performance with setting affinity"
set xlabel "n^{th} fibonacci number"
set ylabel "Time(ns)"
set terminal png font "Times_New_Roman, 12"
set output "tt.png"
set key left

FILES = system("ls -1 *.txt")

plot for [data in FILES]\
data using 3 with linespoints linewidth 2 title data\

## 觀察 Linux 核心模組若沒用到 mutex，到底會發生什麼問題
>[並行和多執行緒設計](https://hackmd.io/@sysprog/concurrency/https%3A%2F%2Fhackmd.io%2F%40sysprog%2FS1AMIFt0D)

### POSIX Threads
>POSIX Threads 是一套符合 [POSIX](https://en.wikipedia.org/wiki/POSIX) 標準的 API，方便開發者設計出 User-level 的多執行緒程式。

在 [linux/unistd.h](https://github.com/torvalds/linux/blob/master/include/uapi/asm-generic/unistd.h) 中提供了 POSIX 作業系統 API 的存取功能標頭檔名稱。通常為大量的 system call。

在可移植性方面，符合 POSIX 標準的 API 其函數名稱、返回值、參數類型等等都按照標準定義，而 POSIX 相容也就指定這些接口 (interface) 函式相容，但是**並不管 API 具體如何實現**

利用 `strace` 簡單測試一個 `printf` 到底呼叫了哪些 system call

int main()
{
    printf("Hello!\n");
    return 0;
}

execve("./strace", ["./strace"], 0x7ffe4f88a900 /* 54 vars */) = 0
brk(NULL)                               = 0x55b334ae3000
arch_prctl(0x3001 /* ARCH_??? */, 0x7fff9841a5c0) = -1 EINVAL (Invalid argument)
mmap(NULL, 8192, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0) = 0x7fc18d976000
access("/etc/ld.so.preload", R_OK)      = -1 ENOENT (No such file or directory)
openat(AT_FDCWD, "/etc/ld.so.cache", O_RDONLY|O_CLOEXEC) = 3
newfstatat(3, "", {st_mode=S_IFREG|0644, st_size=70567, ...}, AT_EMPTY_PATH) = 0
mmap(NULL, 70567, PROT_READ, MAP_PRIVATE, 3, 0) = 0x7fc18d964000
close(3)                                = 0
openat(AT_FDCWD, "/lib/x86_64-linux-gnu/libc.so.6", O_RDONLY|O_CLOEXEC) = 3
read(3, "\177ELF\2\1\1\3\0\0\0\0\0\0\0\0\3\0>\0\1\0\0\0P\237\2\0\0\0\0\0"..., 832) = 832
pread64(3, "\6\0\0\0\4\0\0\0@\0\0\0\0\0\0\0@\0\0\0\0\0\0\0@\0\0\0\0\0\0\0"..., 784, 64) = 784
pread64(3, "\4\0\0\0 \0\0\0\5\0\0\0GNU\0\2\0\0\300\4\0\0\0\3\0\0\0\0\0\0\0"..., 48, 848) = 48
pread64(3, "\4\0\0\0\24\0\0\0\3\0\0\0GNU\0i8\235HZ\227\223\333\350s\360\352,\223\340."..., 68, 896) = 68
newfstatat(3, "", {st_mode=S_IFREG|0644, st_size=2216304, ...}, AT_EMPTY_PATH) = 0
pread64(3, "\6\0\0\0\4\0\0\0@\0\0\0\0\0\0\0@\0\0\0\0\0\0\0@\0\0\0\0\0\0\0"..., 784, 64) = 784
mmap(NULL, 2260560, PROT_READ, MAP_PRIVATE|MAP_DENYWRITE, 3, 0) = 0x7fc18d600000
mmap(0x7fc18d628000, 1658880, PROT_READ|PROT_EXEC, MAP_PRIVATE|MAP_FIXED|MAP_DENYWRITE, 3, 0x28000) = 0x7fc18d628000
mmap(0x7fc18d7bd000, 360448, PROT_READ, MAP_PRIVATE|MAP_FIXED|MAP_DENYWRITE, 3, 0x1bd000) = 0x7fc18d7bd000
mmap(0x7fc18d815000, 24576, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_FIXED|MAP_DENYWRITE, 3, 0x214000) = 0x7fc18d815000
mmap(0x7fc18d81b000, 52816, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_FIXED|MAP_ANONYMOUS, -1, 0) = 0x7fc18d81b000
close(3)                                = 0
mmap(NULL, 12288, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0) = 0x7fc18d961000
arch_prctl(ARCH_SET_FS, 0x7fc18d961740) = 0
set_tid_address(0x7fc18d961a10)         = 21183
set_robust_list(0x7fc18d961a20, 24)     = 0
rseq(0x7fc18d9620e0, 0x20, 0, 0x53053053) = 0
mprotect(0x7fc18d815000, 16384, PROT_READ) = 0
mprotect(0x55b333cc8000, 4096, PROT_READ) = 0
mprotect(0x7fc18d9b0000, 8192, PROT_READ) = 0
prlimit64(0, RLIMIT_STACK, NULL, {rlim_cur=8192*1024, rlim_max=RLIM64_INFINITY}) = 0
munmap(0x7fc18d964000, 70567)           = 0
newfstatat(1, "", {st_mode=S_IFCHR|0620, st_rdev=makedev(0x88, 0x1), ...}, AT_EMPTY_PATH) = 0
getrandom("\xaf\xb4\x13\x5c\x53\x7c\x1c\x55", 8, GRND_NONBLOCK) = 8
brk(NULL)                               = 0x55b334ae3000
brk(0x55b334b04000)                     = 0x55b334b04000
write(1, "Hello!\n", 7Hello!
)                 = 7
exit_group(0)                           = ?
+++ exited with 0 +++

- 在 `line 37` 中 `write` system call 把字符串 `Hello!` 傳給 file descriptor 1 的設備

$ ls /dev/std* -l
lrwxrwxrwx 1 root root 15  四  10 19:55 /dev/stderr -> /proc/self/fd/2
lrwxrwxrwx 1 root root 15  四  10 19:55 /dev/stdin -> /proc/self/fd/0
lrwxrwxrwx 1 root root 15  四  10 19:55 /dev/stdout -> /proc/self/fd/1

- 對應到的為 `stdout`

### 建立執行緒
>[pthread API](https://www.ibm.com/docs/en/i/7.3?topic=ssw_ibm_i_73/apis/rzah4mst.html)

首先程式運行時第一個 tread 負責運行 `main()`，建立一個以上的執行緒則使用 [pthread_create](https://man7.org/linux/man-pages/man3/pthread_create.3.html) ，而執行緒完成工作後很多種結束的方法

>The new thread terminates in one of the following ways:
> * It calls pthread_exit(3), specifying an exit status value that is available to another thread in the same process that calls pthread_join(3).
> * It returns from start_routine(). This is equivalent to calling pthread_exit(3) with the value supplied in the return statement.
> * It is canceled (see pthread_cancel(3)).
> * Any of the threads in the process calls exit(3), or the main thread performs a return from main(). This causes the termination of all threads in the process.

如果不使用 `pthread_join` ，該執行緒會繼續佔用資源直到 process 結束。

`pthread_create`

int pthread_create(pthread_t *thread, const pthread_attr_t *attr,
                          void *(*start_routine) (void *), void *arg);

- `thread`: 指向 `pthread_t` 結構體的指標
- `attr`: 設定 thread 的 attribute，如果設定 `attr` 為 NULL ，則這個 thread 使用 default attributes
- `start_routine`: 這個 thread 會 invoke `start_routine()`
- `arg` 會作為 `start_routine` 的引數

## 嘗試建立 hash table

hlist_add_head(&dnode->list, &htable[key]); // add to hash table

[ 7850.213620] BUG: kernel NULL pointer dereference, address: 0000000000000008
[ 7850.213621] #PF: supervisor write access in kernel mode
[ 7850.213622] #PF: error_code(0x0002) - not-present page

- `#PF` 代表 page fault，當 page fault 發生時，CPU 會將相關的錯誤訊息除存在 `error code` 的特殊暫存器中 (32bit value)
- ` supervisor write access in kernel mode`: 可能發生的原因包含
1. 程式碼對 kernel 空間的指標操作，但是這些指標操作沒有經過適當得初始化。
2. 對該資源進行寫操作，但是該資源已經被鎖定 or 被其他程式使用。
3. 使用了已經被取消或是被棄用的函式或 API，這些函式可能會對 kernel 的 memory 進行寫操作而沒有足夠的權限

### Memroy management

在多執行緒的預期流程，`insmode` -> 多執行緒進行 hash table 的查表、填表 -> 結束運算，走訪 hash table 並釋放空間 -> `rmmod`

>[lkmpg 4.3 The __init and __exit Macros](https://sysprog21.github.io/lkmpg/#the-init-and-exit-macros)
>The __exit macro causes the omission of the function when the module is built into the kernel, and like __init , has no effect for loadable modules. Again, if you consider when the cleanup function runs, this makes complete sense; built-in drivers do not need a cleanup function, while loadable modules do.

## quick note

- [function declaration isn't a prototype](https://stackoverflow.com/questions/42125/warning-error-function-declaration-isnt-a-prototype)
- 引數加上 `void`

## Reference

- [Linux 當中的 VFS 虛擬檔案系統](http://sp1.wikidot.com/linuxvfs)
- [KYG-2020q1 Homework2 (fibdrv)](https://hackmd.io/@KYWeng/rkGdultSU)
- [smp irq affinity介绍](https://blog.csdn.net/yue530tomtom/article/details/76095739)
- [POSIX Thread 介紹](https://ithelp.ithome.com.tw/m/articles/10280830)
- [posix 是什麼都不知道，就別說你懂 Linux 了！](https://www.readfog.com/a/1645003345925083136)
- [Driver (驅動)](https://hackmd.io/@combo-tw/ryRp--nQS#Character-devices)
- [調試工具ltrace strace ftrace的使用](https://jasonblog.github.io/note/linux_kernel/diao_shi_gong_ju_ltrace_strace_ftrace_de_shi_yong.html)
- [ltrace-strace](https://littlebees.github.io/2021/10/ltrace-strace/)