# 2023q1 Homework3 (fibdrv)
contributed by < [zeddyuu](https://github.com/zeddyuu) >
## 實驗環境
```shell
$ 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
```
```shell
$ 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 關閉並確認
```shell
$ 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
```
再次編譯執行如預期結果
```shell
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}
$$
```c
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 為準。
```shell
+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 完成，觀察是否能減少乘法運算的成本
```c
long long t1 = a * ((b << 1) - a);
```
可以看到 bitwise 對於減少乘法運算的成本是有效的
目前可以正確計算到 $F_{92}$ 的值， $F_{93}$ 以後運算會 overflow。
### 字串運算
利用字串做運算，實作字串加法可以突破 $F_{93}$
```c
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。
```c
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 來完成。
```c
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。
```shell=
$(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 為單位儲存。
```c
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;
}
```
```c
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 中執行運算的時間。
```c
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`。
```c
static inline long nanotime()
{
struct timespec t;
clock_gettime(0, &t);
return t.tv_nsec;
}
```
```c
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)。
```c
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` 指令確認
```shell
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 處理中斷的次數，發現確實是因為如此。
```shell
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 執行程式
```shell
sudo taskset -c 1 ./client
```
使用 `taskset` 將行程固定在 CPU Core 1 執行，再跑一次 driver.py 查看結果
變動沒有很明顯，繼續試其他項目。
### 排除干擾效能分析的因素
* 抑制 address space layout randomization (ASLR)
```shell
$ 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
```shell
$ sudo sh -c "echo 1 > /sys/devices/system/cpu/intel_pstate/no_turbo"
```
* 設定 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` 執行
可以看到執行時間降低了很多，經過交叉測試，是因為前面我的 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) 的程式碼來確認。
```c
#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 的簡化版本。
```shell
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
```c
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)。
```shell
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` 的功能改為寫檔
```c
/* 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` 寫入字元陣列，正在尋找有沒有更省空間的方法。
```c
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` 去觀察輸出的字串是否正確
```shell
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` 關檔。
```c
#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 的控制下**
終端訊息
```shell
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 的控制下**
終端訊息
```shell
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.
```
檔案內容
```shell
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 處理字串以及處理檔案的方式。
Sign in with Wallet
Connect another wallet