HackMD2023q1 Homework3 (fibdrv)
contributed by < Paintako >
實驗環境
$ 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.
Prove 已經 overflow:
已知, 在原本 fibdrv.c 中, 用來存放 fib 結果的大小是 long long, 根據 C 語言規格書, long long 的有效儲存位元數至少 為 64 bit
64 位元的最大值為：
64 位元的最小值為：
要求出某數最靠近 2 的幾次方, 可以將數字轉換為以 2 為底的對數, 然後再將其向下取整數，以獲得最接近的 2 的次方數。
再往上加就會 overflow 了
Note: loff_t
用於管理檔案位移量，用來表示文件的讀寫指標在文件中的位置。
- From ChatGpt
以下是 long long 位元大小相關的說明
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 的有效範圍也只是
參考老師筆記中的作法, 可以用一個 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]);
}
}
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.
原本的程式碼中, 使用了 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 * 進行數字相加：
相加程式碼：
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);
}
測試程式是否可用
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 ）
