---
tags: linux2023
---

# 2023q1 Homework3 (fibdrv)
contributed by < [`Paintako`](https://hackmd.io/@Paintako) >

> [作業需求](https://hackmd.io/@sysprog/linux2023-fibdrv/%2F%40sysprog%2Flinux2023-fibdrv-a)
> [GitHub](https://github.com/qwe661234/fibdrv)

::: spoiler 實驗環境

$ gcc --version
gcc (Ubuntu 11.3.0-1ubuntu1~22.04) 11.3.0

$ lscpu
Architecture:            x86_64
  CPU op-mode(s):        32-bit, 64-bit
  Address sizes:         39 bits physical, 48 bits virtual
  Byte Order:            Little Endian
CPU(s):                  12
  On-line CPU(s) list:   0-11
Vendor ID:               GenuineIntel
  Model name:            Intel(R) Core(TM) i5-10400 CPU @ 2.90GHz
    CPU family:          6
    Model:               165
    Thread(s) per core:  2
    Core(s) per socket:  6
    Socket(s):           1
    Stepping:            5
    CPU max MHz:         4300.0000
    CPU min MHz:         800.0000
    BogoMIPS:            5799.77

:::

## 觀察 fibdrv.c

make check 後：

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

將 `fibdrv.ko` 載入 kernal：

(base) eric@eric-System-Product-Name:~/linux2023/fibdrv$ sudo insmod fibdrv.ko
(base) eric@eric-System-Product-Name:~/linux2023/fibdrv$ sudo lsmod
Module                  Size  Used by
fibdrv                 16384  0
rfcomm                 86016  16
cmac                   16384  3
algif_hash             16384  1
algif_skcipher         16384  1

確定 kernal module 中已有 fibdrv 後, 可執行 `client`

sudo ./client

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.
Reading from /dev/fibonacci at offset 96, returned the sequence 7540113804746346429.
Reading from /dev/fibonacci at offset 97, returned the sequence 7540113804746346429.

可以發現, 92 以後數值全都固定在了 `7540113804746346429`, 因為 `client.c` 中把 `offset` 寫死成 100, 但是 `fibdrv.c 中的 MAX_LENGTH` 被寫死成 92, 故 92 以後都被寫死成 92 了, 修改 `MAX_LENGTH` 即可順利跑出大於 92 的結果, 但也因為這個原因無法順利通過 `make check`

 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 -6246583658587674878.
-Reading from /dev/fibonacci at offset 94, returned the sequence 1293530146158671551.
-Reading from /dev/fibonacci at offset 95, returned the sequence -4953053512429003327.
-Reading from /dev/fibonacci at offset 96, returned the sequence -3659523366270331776.

:::warning
Prove 已經 overflow:
已知, 在原本 `fibdrv.c` 中, 用來存放 `fib` 結果的大小是 long long, 根據 C 語言規格書, long long 的有效儲存位元數**至少** 為 64 bit

64 位元的最大值為： $2^{63} - 1$
64 位元的最小值為： $-(2^{63})$

要求出某數最靠近 2 的幾次方, 可以將數字轉換為以 2 為底的對數, 然後再將其向下取整數，以獲得最接近的 2 的次方數。

$log_2(7540113804746346429) ＝ 62$
再往上加就會 **overflow** 了

Note: loff_t
用於管理檔案位移量，用來表示文件的讀寫指標在文件中的位置。
- From ChatGpt

:::

以下是 long long 位元大小相關的說明
:::spoiler

6.2.5 Types

Types are partitioned into object types (types that describe objects) and function types (types that describe functions). Numeric types consist of the two classes signed and unsigned integer types, and the floating types.

The following types are used in this International Standard:

signed integer types:
char: type that has the same range, representation, and behavior as signed char
short int: signed integer type with a width of at least 16 bits
int: signed integer type with a width of at least 16 bits
long int: signed integer type with a width of at least 32 bits
long long int: signed integer type with a width of at least 64 bits
...

:::

## 計算 F93 (包含) 之後的 Fibonacci 數

一開始的想法是： 改成 `__uint128_t` 來表示 128 bit 的數, 但失敗.

static  __uint128_t fib_sequence(long long k)
{
    /* FIXME: C99 variable-length array (VLA) is not allowed in Linux kernel. */
    __uint128_t f0 = 0;
    __uint128_t f1 = 1;
    __uint128_t f_result = 0;
    
    for (int i = 2; i <= k; i++) {
        f_result = f0 + f1;
        f0 = f1;
        f1 = f_result;
    }

    return f_result;
}

或是改成 `unsigned long long` , 但不能解決問題, 因為 `unsigned long long` 的有效範圍也只是 $2^{64}-1$ 而已, 仍然無法表達更大的數值範圍

參考老師筆記中的作法, 可以用一個 char* 來存數值, 避免 overflow

首先, 要把兩個數組給 `reverse`, 原因是因為要**對齊**.
對齊的方法可以使用 `swap` 來實現

void swap_two_char(char *a, char *b){
    char temp = *a;
    *a = *b;
    *b = temp;
}

void reverse(char *a){
    // int seqence_length = sizeof(a); 這是錯的！！
    int sequence_length = strlen(a);
    for(int i =0;i<sequence_length;i++){
        swap_two_char(&a[i],&a[seqence_lenght-i-1]);
    }
}

:::warning
**variable-length array (VLA)**:
also called **variable-sized** or **runtime-sized**
一種 **array data structure**, VLA 的長度在 **run time** 決定
Declaring variable-length arrays can lead to a **stack overflow and potential vulnerabilities(弱點)** in the program.

Linux Kernal 中不允許 VLA 的存在, Linus Torvalds 做出了解釋：
`AND USING VLA'S IS ACTIVELY STUPID! It generates much more code, and
much _slower_ code (and more fragile code), than just using a fixed
key size would have done.
`
- [ref](https://lkml.org/lkml/2018/3/7/621)
:::

原本的程式碼中, 使用了 VLA 來紀錄整個 fib array 來計算 fib(i) , 而 VLA 出現在 `static long long fib_sequence(long long k)` 這裡, k 是在 run time 時才傳入的, 故無法提前在 compile time 就分配好空間, 這在 kernal 中是危險的.

Todo: 看看組語的程式碼, 驗證是否真的如 Linux Torvalds 所說 `generates much more code`

故需要改寫此段程式碼, 與其宣告一個 k 大小的 array, 可以只用兩個變數存 fib(i-1) 以及 fib(i-2), 因為從頭到尾只需要這兩個變數就可以計算 fib(i).

實現 `char *` 進行數字相加：
:::spoiler 相加程式碼：

static void Big_Add(char *a,char *b, char*out){
    reverse(a);
    reverse(b);
    int sum = 0, carry = 0;
    int a_len = strlen(a), b_len = strlen(b);
    int i = 0;
    // Char to int: char - '0'
    if (a_len >= b_len) {
        for (;i<b_len;i++) {
            sum = (a[i]-'0') + (b[i]-'0') + carry;
            out[i] = sum % 10 + '0';  
            carry = sum / 10;
        }

        for (i=b_len;i<a_len;i++) {
            sum = a[i] - '0' + carry;
            out[i] = sum % 10+ '0';  
            carry = sum / 10;
        }
    }
    
    else {
        for (;i<a_len;i++) {
            sum = (a[i]-'0') + (b[i]-'0') + carry;
            out[i] = sum % 10+ '0';  
            carry = sum / 10;
        }

        for (i=a_len;i<b_len;i++) {
            sum = b[i] - '0' + carry;
            out[i] = sum % 10 + '0';  
            carry = sum / 10;
        }
    }
    if (carry) {
        out[i++] = '0' + carry;
    }
    out[i] = '\0';
    reverse(a);
    reverse(b);
    reverse(out);
}

:::

:::spoiler 測試程式是否可用

int main(){
   
    char *a = (char*) malloc(128);
    char *b = (char*) malloc(128);
    strcpy(a,"0");
    strcpy(b,"1");
    char *out = (char*) malloc(128);
    for(int i=2;i<=500;i++){
        Big_Add(a,b,out);
        strcpy(a,b);
        strcpy(b,out);
        printf("%d: %s\n",i,out);
    }

    return 0;
}

490: 1133597084613134447271848482284309025629966048359864130560049384871348807054284272752352079971127752695
491: 1834198612451841980590573354049832310520934744426580487728496070230903857873047734872321602858257776409
492: 2967795697064976427862421836334141336150900792786444618288545455102252664927332007624673682829385529104
493: 4801994309516818408452995190383973646671835537213025106017041525333156522800379742496995285687643305513
494: 7769790006581794836315417026718114982822736329999469724305586980435409187727711750121668968517028834617
495: 12571784316098613244768412217102088629494571867212494830322628505768565710528091492618664254204672140130
496: 20341574322680408081083829243820203612317308197211964554628215486203974898255803242740333222721700974747
497: 32913358638779021325852241460922292241811880064424459384950843991972540608783894735358997476926373114877
498: 53254932961459429406936070704742495854129188261636423939579059478176515507039697978099330699648074089624
499: 86168291600238450732788312165664788095941068326060883324529903470149056115823592713458328176574447204501
500: 139423224561697880139724382870407283950070256587697307264108962948325571622863290691557658876222521294125

:::

至此, 改寫後的程式碼可以順利通過 overflow 測試, 並且藉由宣告兩個 char* 來紀錄 f(i-1) 以及 f(i-2), 成功解決 VLA 問題.

## 核心模式的時間測量
首先以原本程式作為 baseline, 將 `linux/ktime.h` 給引入, 嘗試計算時間, 但是 make check 時有下列訊息：

+Writing to /dev/fibonacci, returned the sequence 1
+Writing to /dev/fibonacci, returned the sequence 1
+Writing to /dev/fibonacci, returned the sequence 1
+Writing to /dev/fibonacci, returned the sequence 1
+Writing to /dev/fibonacci, returned the sequence 1
+Writing to /dev/fibonacci, returned the sequence 1
+Writing to /dev/fibonacci, returned the sequence 1
+Writing to /dev/fibonacci, returned the sequence 1
+Writing to /dev/fibonacci, returned the sequence 1
+Writing to /dev/fibonacci, returned the sequence 1
...

觀察 `clinet.c` ：
`read:` 從 buf 中讀取 count 個 bytes

`sz = write(fd, write_buf, strlen(write_buf));`
查看 write 的定義, 被定義在 `unistd.h` 中, write 是用於把 BUF 中的 N 個 bytes 寫入 FD （ file descript ）