2023q1 Homework3 (fibdrv)

contributed by < peter91015 >

實驗環境

$ gcc --version
gcc (Ubuntu 11.3.0-1ubuntu1~22.04) 11.3.0
Copyright (C) 2021 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
$ lscpu
  架構：                   x86_64
  CPU 作業模式：         32-bit, 64-bit
  Address sizes:         39 bits physical, 48 bits virtual
  Byte Order:            Little Endian
CPU(s):                  4
  On-line CPU(s) list:   0-3
供應商識別號：           GenuineIntel
  Model name:            Intel(R) Core(TM) i5-7400 CPU @ 3.00GHz
    CPU 家族：           6
    型號：               158
    每核心執行緒數：     1
    每通訊端核心數：     4
    Socket(s):           1
    製程：               9
    CPU max MHz:         3500.0000
    CPU min MHz:         800.0000
    BogoMIPS:            6000.00

實作大數運算

原本實作的 fibdrv 輸出的型別是 long long，隨著輸入的 n 越大會導致輸出溢位，為了解決此問題所以使用字串的形式來儲存 fibdrv 的輸出並且資料結構上採用了 Small/Short String Optimization 並且引入了 xs.h xs.c 來時作此功能。在輸出時因為是將 fibdrv 導入至 linux 核心裡面，可以將系統呼叫 read 所寫入的字串為 fibonacci 數列的數值(對應 lseek 所輸入的 offset )以及將 read 回傳的數值設為該數值十進位所需要的位數。

xs f[3];
int i, n;
f[0] = *xs_tmp("0");
f[1] = *xs_tmp("1");
f[2] = *xs_tmp("1");
int tmp;
for (i = 2; i <= k; i++) {
    tmp = i % 3;
    string_number_add(&f[(tmp + 1) % 3], &f[(tmp + 2) % 3], &f[tmp]);
}

原先的實作在計算

$fib(n)$ 時，會宣告一個大小為 n+2 的陣列並且運用 dynamic programming 的方式加上遞迴定義依序從

$fib(2),fib(3)\cdots$ 一直到

$fib(n)$ 停止並且回傳，

$fib(0)$ 和

$fib(1)$ 則是直接對應到 0 和 1。這樣的作法很直觀但是會額外占用

$O(n)$ 的記憶空間，觀察 fibonacci 數列的遞迴定義：

$$fib(n)=fib(n-1)+fib(n-2)$$每次在計算下一項的數值時只會需要給

$fib(n)$、

$fib(n-1)$ 和

$fib(n-2)$ 這三個數值空間，所以只需要宣告大小為 3 的陣列去進行迭代：

(後續有參照 yanjiew1 的筆記，其實可以只使用 2 個空間，兩個空間輪流去算出下一個 fibonacci 數值)

Memory leak 的問題

大數運算的實作參考了 fibdrv_core.c並且直接使用了裡面所提供的函式 string_number_add ，一開始並沒有發生任何異狀，直到實作了 fast doubling 的時候發現每次 client.c 執行中的時候記憶體占用的空間會快速上升，在程式結束之後也沒有釋放，甚至打開系統監測也找不到占用記憶體的程式。後來才想到自己在實作時並沒有在程式的結尾呼叫 xs_free 對於 xs 型別的資料所指向的字串進行釋放空間，造成 memory leak 的現象發生。不過修正過後還是會有記憶體空間釋放不出的情況，這時才發現 string_number_add 在某個段落會有一些問題：

if (out)
    *out = *xs_tmp(buf);

out 是一個 xs 型態的指標， xs_tmp() 則是會產生新的 xs 的資料並且回傳一個指標的形式，而上面的程式碼在 out 本身已經有儲存數值的時候可能會將舊有的字串捨棄掉而指向新的字串，這個行為導致了 memory leak，所以後續先將 out 本身指向的空間進行釋放再去指派。

-if (out)
+if (out){
+   xs_free(out) 
    *out = *xs_tmp(buf);
+}

原先的程式碼在執行會宣告多個空間，並且每個空間只會被指派新的空間一次，程式結束時也會把每個空間都進行釋放，所以並不會造成 memory leak，但是在對已經有指向某個字串的 xs 型別變數還是要進行修改。

效能分析

目前已經研讀完作業說明的 Linux 效能分析的提示的部份，可以使用 taskset 以及 isolcpus 讓某些行程(process)獨占某些 CPU ，但是目前還不太清楚怎麼在 kernel space 上得到 pid 讓 fibdrv 得以使用上面的操作，所以效能分析先不以獨立 CPU 做考慮，修改 client.c 和 fibdrv.c 的程式碼讓 client.c 能對同一個 fibonacci 數列的數值執行運算並且能得到執行運算所花費的時間。

獲得運算執行時間

參照 yanjiew1 的筆記，將原本的 fibdrv.c 之中沒有作用的 write 作為回傳執行時間的系統呼叫(原先的函式只會回傳 1 )。宣告一個 ktime_t 的全域變數 kt，分別在 fib_sequence 執行前後加上 ktime_get 以及 ktime_sub 來得到 fib_sequence 總共花費多少 CPU 時間，並且在呼叫 fib_write 時將 kt 回傳。

static ssize_t fib_read(struct file *file,
                        char *buf,
                        size_t size,
                        loff_t *offset)
{
+    ktime_t start = ktime_get();
    ssize_t fib_res = (ssize_t) fib_sequence(*offset, buf);
+    kt = ktime_sub(ktime_get(), start);
    return fib_res;
}

修改 client.c

讓 client.c 可以對同一個 fibonacci 數列的數值進行多次運算得到數個執行所花費的時間，目前先採用較簡易的方法，取相同數值下的每個執行時間之中位數來做代表，後續可以針對不同的 fibonacci 數列的算法去進行比較，目前只有實作用 dynamic programming，後續會和 fast doubling 的方法去做比較。

實作 fast doubling

Top-down

fast doubling 的遞迴式如下：

$$Fib(2k+1)=Fib(k+1{)}^2+Fib(k{)}^2$$

$$Fib(2k)=Fib(k)\cdot [2\cdot Fib(k+1)-Fib(k)]$$
和前面所述的 dynamic programming 的方法時間複雜度為

$O(n)$比較，fast doubling 只需要

$O(\log n)$，但是 dynamic programming 的方法只需要對數字進行加法，而 fast doubling 的計算卻還需要使用到減法和乘法：

static void string_number_sub(xs *a, xs *b, xs *out);
static void string_scalar_multi(xs *a, char b, xs *out);
static void string_pow10(char *input, size_t pow, xs *out);
static void string_number_multi(xs *a, xs *b, xs *out);   

這邊實作了幾個對於xs.h 所使用的運算，分別是兩個數字相減的絕對值、讓資料型別為 xs 的指標 a 所指的空間對於一個單一字元 b 相乘(b 須為 '0'~'9' 其一)、將某個 xs 變數乘上 10 的冪以及將兩個資料型態為 xs 的兩個變數進行相乘
所提供的資料結構去做運算。
資料結構本身使用字串去存數值，相同的數值所需要的空間會比其他的型別來的多(1 個 byte 只能存一個十進位的位數)，在計算時上也需要將數值做轉換，好處大概只有能動態調整空間以及在輸出數值的時候會比較方便，或許不是最理想的資料結構，作業說明中的 bn 結構體或許能改善計算時要轉換數值的部份，不過還是可以用來比較 dynamic prgramming 和 fast doubling 之間的效率比較。

Bottom-up

TODO