# 2023q1 Homework3 (fibdrv)
contributed by < [zeddyuu](https://github.com/zeddyuu) >

## 實驗環境

$ neofetch --stdout
zhenyu@zhenyu-HP-Laptop-15s-du2xxx
OS: Kubuntu 22.04.1 LTS x86_64 
Host: HP Laptop 15s-du2xxx 
Kernel: 5.15.0-43-generic 
Uptime: 53 mins 
Packages: 1993 (dpkg), 7 (snap) 
Shell: bash 5.1.16 
Resolution: 1920x1080 
DE: Plasma 5.24.4 
WM: KWin 
Theme: [Plasma], Breeze [GTK2/3] 
Icons: [Plasma], breeze-dark [GTK2/3] 
Terminal: konsole 
CPU: Intel i5-1035G1 (8) @ 3.600GHz 
GPU: NVIDIA GeForce MX330 
GPU: Intel Iris Plus Graphics G1 
Memory: 2089MiB / 11754MiB

$ gcc -v
Thread model: posix
Supported LTO compression algorithms: zlib zstd
gcc version 11.3.0 (Ubuntu 11.3.0-1ubuntu1~22.04)

## 自我檢查清單

- [x] 研讀上述 ==Linux 效能分析的提示== 描述，在自己的實體電腦運作 GNU/Linux，做好必要的設定和準備工作 $\to$ 從中也該理解為何不希望在虛擬機器中進行實驗;
- [x] 研讀上述費氏數列相關材料 (包含論文)，摘錄關鍵手法，並思考 [clz / ctz](https://en.wikipedia.org/wiki/Find_first_set) 一類的指令對 Fibonacci 數運算的幫助。請列出關鍵程式碼並解說
- [x] 複習 C 語言 [數值系統](https://hackmd.io/@sysprog/c-numerics) 和 [bitwise operation](https://hackmd.io/@sysprog/c-bitwise)，思考 Fibonacci 數快速計算演算法的實作中如何減少乘法運算的成本;
- [ ] 學習指出針對大數運算的加速運算和縮減記憶體操作成本的舉措，紀錄你的認知和疑惑
- [x] 注意到 `fibdrv.c` 存在著 `DEFINE_MUTEX`, `mutex_trylock`, `mutex_init`, `mutex_unlock`, `mutex_destroy` 等字樣，什麼場景中會需要呢？撰寫多執行緒的 userspace 程式來測試，觀察 Linux 核心模組若沒用到 mutex，到底會發生什麼問題。嘗試撰寫使用 [POSIX Thread](https://en.wikipedia.org/wiki/POSIX_Threads) 的程式碼來確認。 $\to$ 搭配閱讀〈[並行和多執行緒程式設計](https://hackmd.io/@sysprog/concurrency)〉

## 開發紀錄
剛開始 `make check` 後得到錯誤訊息
`insmod: ERROR: could not insert module fibdrv.ko: Operation not permitted`

將 secure boot 關閉並確認

$ sudo dmesg|grep -i secure
[    0.000000] secureboot: Secure boot disabled
[    0.019923] secureboot: Secure boot disabled
[    1.143830] Loaded X.509 cert 'Canonical Ltd. Secure Boot Signing: 61482aa2830d0ab2ad5af10b7250da9033ddcef0'
[    1.143842] Loaded X.509 cert 'Canonical Ltd. Secure Boot Signing (2017): 242ade75ac4a15e50d50c84b0d45ff3eae707a03'
[    1.143854] Loaded X.509 cert 'Canonical Ltd. Secure Boot Signing (ESM 2018): 365188c1d374d6b07c3c8f240f8ef722433d6a8b'
[    1.143867] Loaded X.509 cert 'Canonical Ltd. Secure Boot Signing (2019): c0746fd6c5da3ae827864651ad66ae47fe24b3e8'
[    1.143878] Loaded X.509 cert 'Canonical Ltd. Secure Boot Signing (2021 v1): a8d54bbb3825cfb94fa13c9f8a594a195c107b8d'
[    1.143889] Loaded X.509 cert 'Canonical Ltd. Secure Boot Signing (2021 v2): 4cf046892d6fd3c9a5b03f98d845f90851dc6a8c'
[    1.143900] Loaded X.509 cert 'Canonical Ltd. Secure Boot Signing (2021 v3): 100437bb6de6e469b581e61cd66bce3ef4ed53af'
[    1.143912] Loaded X.509 cert 'Canonical Ltd. Secure Boot Signing (Ubuntu Core 2019): c1d57b8f6b743f23ee41f4f7ee292f06eecadfb9'
[    1.330599] sdhci: Secure Digital Host Controller Interface driver
[   24.730196] Bluetooth: hci0: Secure boot is enabled

再次編譯執行如預期結果

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

### 使用 Fast Doubling 改寫

根據 [fibdrv](https://hackmd.io/@sysprog/linux2023-fibdrv/%2F%40sysprog%2Flinux2023-fibdrv-a) 中所提到的 Fast Doubling 方法進行改寫，可以更快的方式計算。
$$
\begin{split}
F(2k) &= F(k)[2F(k+1) - F(k)] \\
F(2k+1) &= F(k+1)^2+F(k)^2
\end{split}
$$

static long long fib_sequence(long long k)
{
    /* FIXME: C99 variable-length array (VLA) is not allowed in Linux kernel. */
    if (k < 2)
        return k;

    long long a = 0, b = 1;
    int len_zero = __builtin_clzll(k), counter = 64 - len_zero;
    k <<= len_zero;

    for (; counter; k <<= 1, counter--) {
        long long t1 = a * (2 * b - a);
        long long t2 = b * b + a * a;
        a = t1, b = t2;
        if (k & 1ULL << 63) {
            t1 = a + b;
            a = b;
            b = t1;
        }
    }
    return a;
}

用 `builtin_clzll` 先算出 leading zero 的個數，再位移到第一個出現的 1 開始計算，迴圈執行次數也能由此推論出來，原理就是透過位元左移達到乘 2 的效果，並且用 1 在最高位其餘為 0 的 mask 確認 MSB 是否為 1 來判斷是否要將 Fibnacci number 往後計算一位。

若不使用硬體指令 `clz` 的話則必須使用一個從 64 開始的迴圈，使用硬體指令後可以省略不必要的計算，直接從最高位的 1 開始計算


上圖為有使用 clz 以及 沒有使用 clz 的執行時間差距，其中執行時間以 kernel time 為準。

+Reading from /dev/fibonacci at offset 90, returned the sequence 2880067194370816120.
+Reading from /dev/fibonacci at offset 91, returned the sequence 4660046610375530309.
+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.
+Reading from /dev/fibonacci at offset 95, returned the sequence 7540113804746346429.

另外將乘以 2 部份改為用 bitwise 完成，觀察是否能減少乘法運算的成本

     long long t1 = a * ((b << 1) - a);


可以看到 bitwise 對於減少乘法運算的成本是有效的

目前可以正確計算到 $F_{92}$ 的值， $F_{93}$ 以後運算會 overflow。

### 字串運算

利用字串做運算，實作字串加法可以突破 $F_{93}$

static void add_string(char *x, char *y, char *next) {
    int x_size = strlen(x), y_size = strlen(y);
    int i, carry = 0;
    int sum;
    if (x_size >= y_size) {
        for(i = 0; i < y_size; i++) {
        sum = (x[i] - '0') + (y[i] - '0') + carry;
        next[i] = '0' + sum % 10;
        carry = sum / 10;
        }
        for(i = y_size; i < x_size; i++) {
        sum = (x[i] - '0') + carry;
        next[i] = '0' + sum % 10;
        carry = sum / 10;
        }
    } else {
        for(i = 0; i < x_size; i++) {
        sum = (x[i] - '0') + (y[i] - '0') + carry;
        next[i] = '0' + sum % 10;
        carry = sum / 10;
        }
        for(i = x_size; i < y_size; i++) {
        sum = (y[i] - '0') + carry;
        next[i] = '0' + sum % 10;
        carry = sum / 10;
        }
    }
    if (carry) {
        next[i] = '1';
    }
    next[++i] = '\0';
}

此為字串加法的函式，根據[作業說明](https://hackmd.io/@sysprog/linux2023-fibdrv/%2F%40sysprog%2Flinux2023-fibdrv-a)的演算法實作，由 low index 累加到 high index 每個步驟都會計算進位看是否在下一位累加 1。

void reverse_string(char *str, size_t size){
    for (int i = 0; i < size - i; i++){
        str[i] = str[i] ^ str[size - i];
        str[size -i] = str[i] ^ str[size - i];
        str[i] = str[i] ^ str[size - i];
    }
}

此為反轉字串的函式，頭尾做交換直到迴圈結束即可完成，交換一般都需要一個暫存的變數，但根據[你所不知道的 C 語言：數值系統](https://hackmd.io/@sysprog/c-numerics#%E9%81%8B%E7%94%A8-bit-wise-operator)中用 XOR 操作做變數交換(在[你所不知道的C語言：遞迴呼叫篇](https://hackmd.io/@sysprog/c-recursion#%E6%A1%88%E4%BE%8B%E5%88%86%E6%9E%90%EF%BC%9A%E5%AD%97%E4%B8%B2%E5%8F%8D%E8%BD%89)，也有提及到字串反轉的演算法，但使用限定使用遞迴操作)，可以節省額外暫存變數的記憶體空間，原理是用 a XOR a = 0 ， b XOR 0 = b 來完成。

struct strbuf
{
    char fib[128];
};

static long long fib_sequence_string(long long k, char *buf) {
    struct strbuf *res = kmalloc(sizeof(struct strbuf) * (k + 1), GFP_KERNEL);
    strncpy(res[0].fib, "0", 2);
    strncpy(res[1].fib, "1", 2);
    for (int i = 2; i <= k; i++) {    
        add_string(res[i - 1].fib, res[i - 2].fib, res[i].fib);
    }
    size_t size = strlen(res[k].fib);
    reverse_string(res[k].fib, size - 1);
    __copy_to_user(buf, res[k].fib, size + 1);
    return size;
}

先為每一個 Fibonacci number 定義一個結構，最多可以用 128 長度的字串代表數字，可以解決 64 位元運算 overflow 的問題。

[作業說明](https://hackmd.io/@sysprog/linux2023-fibdrv/%2F%40sysprog%2Flinux2023-fibdrv-b)中是每次都將字串反轉後做加法運算，但可以做完計算後在最後呼叫一次反轉就好，省略函式呼叫，且在[作業說明](https://hackmd.io/@sysprog/linux2022-fibdrv#%E9%97%9C%E6%96%BC-clientc)中提到 kernel space 以及 user space 進行溝通的方法必須透過 `copy_to_user()` 將kernel space 記憶體內容複製到 user space 記憶體之中，因為 user space 無法直接存取 kernel space，參考 [Why do you have to use copy_to_user()/copy_from_user() to access user space from the kernel?](https://stackoverflow.com/questions/12666493/why-do-you-have-to-use-copy-to-user-copy-from-user-to-access-user-space-from) 以及一些學過的 OS。

	$(MAKE) unload
	$(MAKE) load
	sudo ./client > out
	$(MAKE) unload
	@diff -u out scripts/expected.txt && $(call pass)
	@scripts/verify.py

最後 Makefile 中第 5 行有將 out 跟 expected.txt 比較，要將內容改成正確的值比較過後才會 pass。

### 時間測量和效能分析
引入 `ktime_t` 來計算 kernel space 執行時間，在 [The high-resolution timer API ](https://lwn.net/Articles/167897/) 中有提到此資料結構會根據不同的架構上有所變化，像是 64 位元系統上是以 ns 為單位的整數值，在 32 位元系統上則是一個 two-field 結構，一段 32 位元資料存秒數，一段以 ns 為單位儲存。

static long long fib_time_proxy(long long k, char *buf)
{
    kt = ktime_get();
    long long res = fib_sequence_string(k, buf);
    kt = ktime_sub(ktime_get(), kt);
    return res;
}

static ssize_t fib_read(struct file *file,
                        char *buf,
                        size_t size,
                        loff_t *offset)
{
    return (ssize_t) fib_time_proxy(*offset, buf);
}

根據作業說明透過 `fib_time_proxy` 來計算 kernel space 中執行運算的時間。

static ssize_t fib_write(struct file *file,
                         const char *buf,
                         size_t size,
                         loff_t *offset)
{
    return ktime_to_ns(kt);
}

因為 write 操作暫時沒有作用，可以用來輸出上一次的執行時間給 user space 的 `client.c`。

static inline long nanotime()
{
    struct timespec t;
    clock_gettime(0, &t);
    return t.tv_nsec;
}

struct timespec {
  time_t tv_sec;  /* seconds */
  long   tv_nsec; /* nanoseconds */
};

在 `client.c` 中定義 `nanotime()` 可以透過 `clock_gettime()` 取得當前時間，其中時間是用 `timespec` 這個結構體來儲存，其結構是定義在 `time.h` 標頭檔中，可以存秒為單位也可以存 ns 為單位， `clock_gettime()` 可以得到當前時間，第一個參數需給定時間的類型，這裡選用 `CLOCK_REALTIME` 代表系統的實際時間(但我這邊系統找不到定義，所以根據他的巨集給定 0)。

    for (int i = 0; i <= offset; i++) {
        lseek(fd, i, SEEK_SET);
        long long start = nanotime();
        sz = read(fd, buf, sizeof(buf));
        long long user_time = nanotime() - start; 
        long long kernel_time = write(fd, write_buf, sizeof(write_buf)); 
        printf("Writing to " FIB_DEV ", returned the kernel time %ld\n", kernel_time);
        printf("Reading from " FIB_DEV
               " at offset %d, returned the sequence "
               "%s.\n",
               i, buf);
        fprintf(data, "%d %lld %lld %lld\n", i, kernel_time, user_time, user_time - kernel_time);
    }

為了要使用[作業說明](https://hackmd.io/@sysprog/linux2023-fibdrv/%2F%40sysprog%2Flinux2023-fibdrv-c)中提到的 [python script](https://github.com/colinyoyo26/fibdrv/commit/4ce43c4e7ee0b80c4ce9e6dcd995bbfdf239206c) 來生成圖表比較執行時間，透過寫檔的方式將資料寫入檔案再透過 script 讀出資料進行統計，此 script 使用標準化的方式先降低資料的離散程度。


這裡可以複習 process 透過 system call 請求 kernel 服務的[流程](https://hackmd.io/@combo-tw/Linux-%E8%AE%80%E6%9B%B8%E6%9C%83/%2F%40combo-tw%2FBJPoAcqQS#%E5%91%BC%E5%8F%AB%E6%B5%81%E7%A8%8B)(圖都來自恐龍本)，process 提出 system call 請求後會經由軟體中斷進入 kernel mode ，並查詢 system call table 找到對應的中斷服務常式，完成後發出中斷通知 OS 完成，這個系統呼叫的過程在 process 的壽命中是由 `running` 到 `ready` ，之後還要由 CPU scheduler 排程給 CPU 執行，所以有一些額外的時間要考慮進去，因此在計算時間上必須要細分出幾個細項。

可以將時間分為 `user time`、`real time`、`kernel time`，其中 `real time` 是完整程式執行的時間，且包含了其他 process 以及此 process blocked(e.g. wait for I/O) 的時間，所以我們關注的只有`kernel time` 以及 `user time` ，前者是在 kernel space 執行的 CPU time 總和，後者是在 user space 執行的 CPU time 總和，在程式中只計算 `read` 這個系統呼叫的此兩項標準來做評估。

以實作的字串運算來計算到 $F_{100}$ 作為時間測量標準，其中將 `user time` 減去 `kernel time` 得到的就是在 user space 以及 kernel space 之間額外傳遞的時間。

由圖表可以看到在計算量較小時，執行時間上呈現劇烈的波動，在後面計算量變大時波動幅度會較為區緩。

### 限定 CPU 給特定程式使用
根據[參考網址](https://askubuntu.com/questions/165075/how-to-get-isolcpus-kernel-parameter-working-with-precise-12-04-amd64)以及[作業說明](https://hackmd.io/@sysprog/linux2023-fibdrv/%2F%40sysprog%2Flinux2023-fibdrv-c#%E9%99%90%E5%AE%9A-CPU-%E7%B5%A6%E7%89%B9%E5%AE%9A%E7%9A%84%E7%A8%8B%E5%BC%8F%E4%BD%BF%E7%94%A8)在 `/etc/default/grub` 中的 `GRUB_CMDLINE_LINUX_DEFAULT="quiet splash"` 後方加入 `isolcpus=1` 之後 update-grub，重開機後就可以孤立出 CPU Core 1。

在 `/sys/devices/system/cpu/isolated` 中也可以確認是否正確啟用。

用 `top` 指令確認

top - 09:51:27 up 34 min,  5 users,  load average: 0.72, 1.29, 1.08
Tasks: 353 total,   2 running, 351 sleeping,   0 stopped,   0 zombie
%Cpu0  :  0.4 us,  1.1 sy,  0.0 ni, 98.6 id,  0.0 wa,  0.0 hi,  0.0 si,  0.0 st
%Cpu1  :  0.0 us,  0.0 sy,  0.0 ni,100.0 id,  0.0 wa,  0.0 hi,  0.0 si,  0.0 st
%Cpu2  :  1.0 us,  0.7 sy,  0.0 ni, 98.3 id,  0.0 wa,  0.0 hi,  0.0 si,  0.0 st
%Cpu3  :  0.7 us,  0.3 sy,  0.0 ni, 99.0 id,  0.0 wa,  0.0 hi,  0.0 si,  0.0 st
%Cpu4  :  1.3 us,  0.7 sy,  0.0 ni, 98.0 id,  0.0 wa,  0.0 hi,  0.0 si,  0.0 st
%Cpu5  :  1.0 us,  0.0 sy,  0.0 ni, 99.0 id,  0.0 wa,  0.0 hi,  0.0 si,  0.0 st
%Cpu6  :  0.3 us,  1.0 sy,  0.0 ni, 98.7 id,  0.0 wa,  0.0 hi,  0.0 si,  0.0 st
%Cpu7  :  1.7 us,  0.3 sy,  0.0 ni, 98.0 id,  0.0 wa,  0.0 hi,  0.0 si,  0.0 st
MiB Mem :  11752.6 total,   6750.9 free,   2302.8 used,   2698.9 buff/cache
MiB Swap:   2048.0 total,   2048.0 free,      0.0 used.   8556.2 avail Mem 

可以看到 Core 1 的確被孤立出來，沒有行程使用，但 cpu 有時候會突然有反應，並不是完全閒置，推測是為了處理一些中斷請求所造成的

透過觀察 `/proc/interrupts` 可以觀察 IRQ 的統計情況，會顯示每個 CPU 處理中斷的次數，發現確實是因為如此。

            CPU0       CPU1       CPU2       CPU3       CPU4       CPU5       CPU6       CPU7       
   1:       2981          0          0          0          0        448          0          0  IR-IO-APIC    1-edge      i8042
   8:          0          0          0          0          0          0          0          0  IR-IO-APIC    8-edge      rtc0
   9:         10         11         14          0          0          0          0          0  IR-IO-APIC    9-fasteoi   acpi
  14:          2          0          0          0          0          0          0          0  IR-IO-APIC   14-fasteoi   INT3455:00
  16:    1319778          0          0     327770          0          0          0          0  IR-IO-APIC   16-fasteoi   i801_smbus, idma64.0, i2c_designware.0, mmc1
  19:          0          0          0          0          0          0          0          0  IR-IO-APIC   19-fasteoi   mmc0
  ....

### 以特定 CPU 執行程式

sudo taskset -c 1 ./client

使用 `taskset` 將行程固定在 CPU Core 1 執行，再跑一次 driver.py 查看結果

變動沒有很明顯，繼續試其他項目。

### 排除干擾效能分析的因素
* 抑制 address space layout randomization (ASLR)

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

ASLR 能讓每次程式以及動態函式庫的載入位置都不相同，以防止能填入固定的位置到堆疊中的返回位置中，若每次都是固定的返回位置，攻擊者能透過其堆疊中的返回位址來替換為另一條指令的位址，並跳轉到記憶體的特定位置。

在 Linux 系統中，ASLR 可能會影響到系統效能，尤其是在 x86 架構上，因為要讓程式在運行時兼容 ASLR ，在編譯的時候要指定一個叫做 PIE (PositionIndependent Executable) 的選項，根據論文 [Too much PIE is bad for performance](https://hexhive.epfl.ch/publications/files/12TRpie.pdf) 會帶來一些效能上的影響。
參考 [Differences Between ASLR on Windows and Linux](https://insights.sei.cmu.edu/blog/differences-between-aslr-on-windows-and-linux/) 以及 [ASLR Wiki](https://zh.wikipedia.org/zh-tw/%E4%BD%8D%E5%9D%80%E7%A9%BA%E9%96%93%E9%85%8D%E7%BD%AE%E9%9A%A8%E6%A9%9F%E8%BC%89%E5%85%A5)

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

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

* 設定 scaling_governor 為 performance。準備以下 shell script，檔名為 `performance.sh`:

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

之後再用 `$ sudo sh performance.sh` 執行


可以看到執行時間降低了很多，經過交叉測試，是因為前面我的 CPUFREQ 設定皆為 powersave 限制了 CPU 時脈速度達到省電的功能，所以時間才會差很多，但波動幅度仍舊很大。

### SMP IRQ affinity
閱讀了 [SMP IRQ affinity](https://www.kernel.org/doc/html/next/core-api/irq/irq-affinity.html)，其實跟 processor affinity 很像，只是對象換成了 IRQ (Interrupt Request) ，而 SMP 則是在描述多處理器的架構，可以理解為系統存在多個相同的 CPU ，共同使用相同的主記憶體以及資源，彼此在系統中擁有相同的地位。

故可以藉由調整 IRQ affinity 來避免我們想要指定的 cpu 去處理中斷請求，再將行程放到此 cpu 核心上看是否能解決這個波動的問題。


波動幅度仍然存在，但可以看到突然升起的波峰部分似乎變少了，推測是有一些 IRQ Affinity 是沒辦法更動的，所以依舊存在 CPU 去處理 IRQ 的情況。

## 大數運算
### 大數運算中如何加速運算
在 [bignum/mul.c](https://github.com/sysprog21/bignum/blob/master/mul.c) 中使用到 `Karatsuba` 演算法去減少乘法的運算成本。

### 大數運算中如何減少記憶體操作

## 注意到 `fibdrv.c` 存在著 `DEFINE_MUTEX`, `mutex_trylock`, `mutex_init`, `mutex_unlock`, `mutex_destroy` 等字樣，什麼場景中會需要呢？撰寫多執行緒的 userspace 程式來測試，觀察 Linux 核心模組若沒用到 mutex，到底會發生什麼問題。嘗試撰寫使用 [POSIX Thread](https://en.wikipedia.org/wiki/POSIX_Threads) 的程式碼來確認。

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

#define FIB_DEV "/dev/fibonacci"

void run() 
{
    long long sz;

    char buf[128];
    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++) {
        lseek(fd, i, SEEK_SET);
        sz = read(fd, buf, sizeof(buf));
        printf("Reading from " FIB_DEV
               " at offset %d, returned the sequence "
               "%s.\n",
               i, buf);
    }

    close(fd);
}



int main()
{
    pthread_t pt[2];
    for (int i = 0; i < 2; i++) {
        pthread_create(&pt[i], NULL, run, NULL);
    }

    for (int i = 0; i < 2; i++) {
        pthread_join(&pt[i], NULL);
    }    
    return 0;
}

新增一個 thread.c 來測試 mutex 的功能，而 thread 執行的函式為 run ，因為只是要測試功能，故為原來 client.c 的簡化版本。

sudo ./thread 
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 1.
Reading from /dev/fibonacci at offset 3, returned the sequence 2.
Failed to open character device: Device or resource busy
Reading from /dev/fibonacci at offset 4, returned the sequence 3.
Reading from /dev/fibonacci at offset 5, returned the sequence 5.
Reading from /dev/fibonacci at offset 6, returned the sequence 8.
Reading from /dev/fibonacci at offset 6, returned the sequence 8.
Reading from /dev/fibonacci at offset 7, returned the sequence 13.
Reading from /dev/fibonacci at offset 8, returned the sequence 21.

可以看到因為 mutex 先被其中一個 thread 取得，則另外一個 thread 無法開啟 /dev/fibonacci

static int fib_open(struct inode *inode, struct file *file)
{
    if (!mutex_trylock(&fib_mutex)) {
        printk(KERN_ALERT "fibdrv is in use");
        return -EBUSY;
    }
    return 0;
}

參考 [mutex_trylock](https://archive.kernel.org/oldlinux/htmldocs/kernel-locking/API-mutex-trylock.html) 文件，此 API 的功能是一個 thread 會嘗試取得 mutex，且此動作是 atomically 代表要不一氣呵成地完成，要不就是失敗，不會有中間狀態，且 mutex 只能被持有 (acquire) 的 thread 釋放，保證共享資源不會發生有兩個以上的 thread 同時使用造成 [race condition](https://en.wikipedia.org/wiki/Race_condition)。

Reading from /dev/fibonacci at offset 99, returned the sequence 218922995834555169026.
Reading from /dev/fibonacci at offset 92, returned the sequence 7540113804746346429.
Reading from /dev/fibonacci at offset 100, returned the sequence 354224848179261915075.
Reading from /dev/fibonacci at offset 93, returned the sequence 12200160415121876738.
Reading from /dev/fibonacci at offset 94, returned the sequence 19740274219868223167.
Reading from /dev/fibonacci at offset 95, returned the sequence 31940434634990099905.
Reading from /dev/fibonacci at offset 96, returned the sequence 51680708854858323072.
Reading from /dev/fibonacci at offset 97, returned the sequence 83621143489848422977.
Reading from /dev/fibonacci at offset 98, returned the sequence 135301852344706746049.
Reading from /dev/fibonacci at offset 99, returned the sequence 218922995834555169026.
Reading from /dev/fibonacci at offset 100, returned the sequence 354224848179261915075.

將 fibdrv 中 mutex 相關的程式碼註解掉，可以發現兩個 thread 都可以正常執行，但這是發生在兩個 thread 都是做讀取的情況，若是有寫入檔案相關可能會發生 race condition，導致讀取發生資料錯誤(這裡的 fib 數值錯誤是因為使用 fast doubling 版本，正確數值只能顯示到 $F_{92}$，沒有使用大數運算或是字串運算)。

:::warning
做實驗確認，並觀察實際行為，避免籠統地說「可能會發發生 race condition」，我們要知曉「行為」並根治問題。

另外，使用 (mutex) lock 會影響 Fibonacci 數運算效率，你該提出兼顧並行處理的正確和運算效率的方案。
:notes: jserv
>收到
:::

設計一個實驗去驗證當有寫入檔案時會不會發生 race condition，將文字檔案當成是共享資源，實驗在有無 mutex 下是否會正確執行

將 `fib_write` 的功能改為寫檔

/* write operation is skipped */
static ssize_t fib_write(struct file *file,
                         const char *buf,
                         size_t size,
                         loff_t *offset)
{
    struct file *fptr;
    loff_t pos;
    fptr = filp_open("/home/usr/fibdrv/fib_sequence.txt", O_RDWR | O_APPEND, 0644);
    if (IS_ERR(fptr)) {
        return -1;
    }
    long long res = fib_sequence(*offset);
    char formatted_str[80];
    int str_size = snprintf(NULL, 0, "offset %lld = %lld\n", *offset, res);
    sprintf(formatted_str, "offset %lld = %lld\n", *offset, res);
    pos = fptr->f_pos;
    kernel_write(fptr, formatted_str, str_size, &pos);
    filp_close(fptr, NULL);
    return 1;
}

為了在 kernel space 開檔案，使用了 `filp_open`，其回傳值和參數跟 user space 的 `fopen` 一樣，都是回傳 `FILE *`，參數則是檔名和開檔的模式以及創建檔案時的權限，開檔的權限對應了 User, Group, Others 並且用三個位元表示 Read, Write, Execute，像我這邊設定成 User 可以進行讀寫就是 110，轉十進位後就是 6，之後處理開檔失敗則回傳 -1。

接著就是字串處理的部份，先預先宣告一個長度一定不會超過計算結果長度的字元陣列，防止 buffer overflow，取得 `fib_sequence` 的計算結果後使用 `snprintf` 計算出格式化字串的長度，再使用 `sprintf` 寫入字元陣列，正在尋找有沒有更省空間的方法。

    struct file *fptr;
    loff_t pos;
    fptr = filp_open("/home/usr/fibdrv/fib_sequence.txt", O_RDWR | O_APPEND,
                     0644);
    if (IS_ERR(fptr)) {
        return -1;
    }
    long long res = fib_sequence(*offset);
    char *formatted_str;
    formatted_str = kasprintf(GFP_KERNEL, "offset %lld = %lld\n", *offset, res);
    if (formatted_str == NULL) {
        return -1;
    }
    printk("%s", formatted_str);

    pos = fptr->f_pos;
    kernel_write(fptr, formatted_str, strlen(formatted_str), &pos);
    filp_close(fptr, NULL);
    kfree(formatted_ptr);
    return 1;

更省空間的方法，使用 `kasprintf` 去動態輸出格式化字串，如此一來就不需要事先宣告比較大的字元陣列，節省空間，在過程中也使用 `printk` 搭配 `dmesg` 去觀察輸出的字串是否正確

sudo dmesg | tail
[15389.339349] offset 83 = 99194853094755497
[15389.339426] offset 84 = 160500643816367088
[15389.339460] offset 85 = 259695496911122585
[15389.339491] offset 86 = 420196140727489673
[15389.339516] offset 87 = 679891637638612258
[15389.339551] offset 88 = 1100087778366101931
[15389.339577] offset 89 = 1779979416004714189
[15389.339628] offset 90 = 2880067194370816120
[15389.339655] offset 91 = 4660046610375530309
[15389.339678] offset 92 = 7540113804746346429

最後是使用 `kernel_write` 寫入檔案，一開始是想要使用 `vfs_write` 來進行，但看 [Unknown symbol vfs_write (err -2) in kernel module in kernel 4.20](https://stackoverflow.com/questions/53917041/unknown-symbol-vfs-write-err-2-in-kernel-module-in-kernel-4-20) 討論後，發現 Linux v4.14 以後已經不會 export `vfs_write` 給 module 使用，改用 `kernel_write` 來完成寫檔，寫入的長度為預先計算出的字串本身長度，最後再用 `filp_close` 關檔。

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

#define FIB_DEV "/dev/fibonacci"

void run() 
{
    long long sz;
    
    char buf[128];
    char write_buf[] = "testing writing";
    int offset = 92; /* TODO: try test something bigger than the limit */

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

    for (int i = 0; i <= offset; i++) {
        lseek(fd, i, SEEK_SET);
        sz = write(fd, buf, sizeof(buf));
        
        printf("Reading from " FIB_DEV
               " at offset %d, returned the sequence "
               "%lld.\n",
               i, sz);
    }
    close(fd);
}

int main()
{
    pthread_t pt[2];
    for (int i = 0; i < 2; i++) {
        pthread_create(&pt[i], NULL, run, NULL);
    }

    for (int i = 0; i < 2; i++) {
        printf("thread %d is running\n", i);
        pthread_join(&pt[i], NULL);
        printf("thread %d is end\n", i);
    }    
    return 0;
}

client 端使用兩個 thread 執行 fib_write 寫入檔案，跟讀取差不多，只是換成 write 操作，且將 fib_open 的動作改為 while，使得不會因為另外一個 thread 嘗試取得 mutex 而導致所有的 thread 因為 `exit(1)` 而停止，如此一來所有的 thread 都會全部執行，雖然會因為 while 迴圈不斷檢查以及嘗試取得 mutex 而在時間效能上有所影響，但可以保證寫入的順序是正確的。

* **在有 mutex 的控制下**

終端訊息

sudo ./thread 
thread 0 is running
Reading from /dev/fibonacci at offset 0, returned the sequence 1.
Reading from /dev/fibonacci at offset 1, returned the sequence 1.
Failed to open character device: Device or resource busy
Reading from /dev/fibonacci at offset 2, returned the sequence 1.
Reading from /dev/fibonacci at offset 3, returned the sequence 1.
Failed to open character device: Device or resource busy
Failed to open character device: Device or resource busy
Reading from /dev/fibonacci at offset 4, returned the sequence 1.
Failed to open character device: Device or resource busy
.
.
.
Reading from /dev/fibonacci at offset 89, returned the sequence 1.
Reading from /dev/fibonacci at offset 90, returned the sequence 1.
Reading from /dev/fibonacci at offset 91, returned the sequence 1.
Reading from /dev/fibonacci at offset 92, returned the sequence 1.

檔案內容

offset 0 = 0
offset 1 = 1
offset 2 = 1
offset 3 = 2
offset 4 = 3
offset 5 = 5
offset 6 = 8
offset 7 = 13
offset 8 = 21
offset 9 = 34
offset 10 = 55
offset 11 = 89
.
.
.
offset 85 = 259695496911122585
offset 86 = 420196140727489673
offset 87 = 679891637638612258
offset 88 = 1100087778366101931
offset 89 = 1779979416004714189
offset 90 = 2880067194370816120
offset 91 = 4660046610375530309
offset 92 = 7540113804746346429
offset 0 = 0
offset 1 = 1
offset 2 = 1
offset 3 = 2
offset 4 = 3
offset 5 = 5
offset 6 = 8
offset 7 = 13
offset 8 = 21
.
.
.
offset 84 = 160500643816367088
offset 85 = 259695496911122585
offset 86 = 420196140727489673
offset 87 = 679891637638612258
offset 88 = 1100087778366101931
offset 89 = 1779979416004714189
offset 90 = 2880067194370816120
offset 91 = 4660046610375530309
offset 92 = 7540113804746346429

* **在沒有 mutex 的控制下**

終端訊息

sudo ./thread 
thread 0 is running
Reading from /dev/fibonacci at offset 0, returned the sequence 1.
Reading from /dev/fibonacci at offset 0, returned the sequence 1.
Reading from /dev/fibonacci at offset 1, returned the sequence 1.
Reading from /dev/fibonacci at offset 1, returned the sequence 1.
Reading from /dev/fibonacci at offset 2, returned the sequence 1.
.
.
.

Reading from /dev/fibonacci at offset 85, returned the sequence 1.
Reading from /dev/fibonacci at offset 92, returned the sequence 1.
Reading from /dev/fibonacci at offset 86, returned the sequence 1.
Reading from /dev/fibonacci at offset 87, returned the sequence 1.
Reading from /dev/fibonacci at offset 88, returned the sequence 1.
Reading from /dev/fibonacci at offset 89, returned the sequence 1.
Reading from /dev/fibonacci at offset 90, returned the sequence 1.
Reading from /dev/fibonacci at offset 91, returned the sequence 1.
Reading from /dev/fibonacci at offset 92, returned the sequence 1.

檔案內容

offset 0 = 0
offset 0 = 0
offset 1 = 1
offset 2 = 1
offset 1 = 1
offset 2 = 1
offset 3 = 2
.
.
.
offset 87 = 679891637638612258
offset 88 = 1100087778366101931
offset 89 = 1779979416004714189
offset 90 = 2880067194370816120
offset 91 = 4660046610375530309
offset 92 = 7540113804746346429

可以看到在有 mutex 的控制下，寫檔可以按照取得 mutex 的順序寫入，在沒有 mutex 的控制下，寫檔過程發生 race condition，對共享資源的寫入順序成為亂序，在這個實驗中學到一些在 kernel module 處理字串以及處理檔案的方式。