--- 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 實驗環境 ```shell $ 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 後： ```shell Passed [-] f(93) fail input: 7540113804746346429 expected: 12200160415121876738 ``` 將 `fibdrv.ko` 載入 kernal： ```shell (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` ```shell 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` ```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 -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 的數, 但失敗. ```c 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` 來實現 ```c 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 相加程式碼： ```c 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 測試程式是否可用 ```c 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; } ``` ```shell= 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 時有下列訊息： ```shell +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 ）
Last changed by  
 
Paintakotako
226

Read more

Assignment3: single-cycle RISC-V CPU

contributed by <Paintakotako>

12/1/2023
交接問題紀錄

[ ] asdas

8/23/2023
2023q1 Homework7 (ktcp)

contributed by <Paintako>

8/5/2023
碩0

三個概念:

6/29/2023
Read more from Paintakotako
Published on HackMD