2023q1 Homework3 (fibdrv)

contributed by < 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)

自我檢查清單

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

開發紀錄

剛開始 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 中所提到的 Fast Doubling 方法進行改寫，可以更快的方式計算。

$$\begin{array}{rl}F(2k)& =F(k)[2F(k+1)-F(k)]\\ F(2k+1)& =F(k+1{)}^2+F(k{)}^2\end{array}$$

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

此為字串加法的函式，根據作業說明的演算法實作，由 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 語言：數值系統中用 XOR 操作做變數交換(在你所不知道的C語言：遞迴呼叫篇，也有提及到字串反轉的演算法，但使用限定使用遞迴操作)，可以節省額外暫存變數的記憶體空間，原理是用 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 的問題。

作業說明中是每次都將字串反轉後做加法運算，但可以做完計算後在最後呼叫一次反轉就好，省略函式呼叫，且在作業說明中提到 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? 以及一些學過的 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 中有提到此資料結構會根據不同的架構上有所變化，像是 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);
    }

為了要使用作業說明中提到的 python script 來生成圖表比較執行時間，透過寫檔的方式將資料寫入檔案再透過 script 讀出資料進行統計，此 script 使用標準化的方式先降低資料的離散程度。

這裡可以複習 process 透過 system call 請求 kernel 服務的流程(圖都來自恐龍本)，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 給特定程式使用

根據參考網址以及作業說明在 /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 會帶來一些效能上的影響。
參考 Differences Between ASLR on Windows and Linux 以及 ASLR Wiki

• 針對 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，其實跟 processor affinity 很像，只是對象換成了 IRQ (Interrupt Request) ，而 SMP 則是在描述多處理器的架構，可以理解為系統存在多個相同的 CPU ，共同使用相同的主記憶體以及資源，彼此在系統中擁有相同的地位。

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

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

大數運算

大數運算中如何加速運算

在 bignum/mul.c 中使用到 Karatsuba 演算法去減少乘法的運算成本。

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

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

#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 文件，此 API 的功能是一個 thread 會嘗試取得 mutex，且此動作是 atomically 代表要不一氣呵成地完成，要不就是失敗，不會有中間狀態，且 mutex 只能被持有 (acquire) 的 thread 釋放，保證共享資源不會發生有兩個以上的 thread 同時使用造成 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}$，沒有使用大數運算或是字串運算)。

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

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

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 討論後，發現 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 處理字串以及處理檔案的方式。