# 2022q1 Homework3 (fibdrv) ```bash $ git clone git@github.com:cy023/fibdrv.git ``` ```bash $ make check Git hooks are installed successfully. cc -o client client.c make -C /lib/modules/5.13.0-30-generic/build M=/home/cy023/linux2022/fibdrv modules make[1]: Entering directory '/usr/src/linux-headers-5.13.0-30-generic' CC [M] /home/cy023/linux2022/fibdrv/fibdrv.o /home/cy023/linux2022/fibdrv/fibdrv.c: In function ‘fib_sequence’: /home/cy023/linux2022/fibdrv/fibdrv.c:30:5: warning: ISO C90 forbids variable length array ‘f’ [-Wvla] 30 | long long f[k + 2]; | ^~~~ MODPOST /home/cy023/linux2022/fibdrv/Module.symvers CC [M] /home/cy023/linux2022/fibdrv/fibdrv.mod.o LD [M] /home/cy023/linux2022/fibdrv/fibdrv.ko BTF [M] /home/cy023/linux2022/fibdrv/fibdrv.ko Skipping BTF generation for /home/cy023/linux2022/fibdrv/fibdrv.ko due to unavailability of vmlinux make[1]: Leaving directory '/usr/src/linux-headers-5.13.0-30-generic' make unload make[1]: Entering directory '/home/cy023/linux2022/fibdrv' sudo rmmod fibdrv || true >/dev/null [sudo] password for cy023: rmmod: ERROR: Module fibdrv is not currently loaded make[1]: Leaving directory '/home/cy023/linux2022/fibdrv' make load make[1]: Entering directory '/home/cy023/linux2022/fibdrv' sudo insmod fibdrv.ko make[1]: Leaving directory '/home/cy023/linux2022/fibdrv' sudo ./client > out make unload make[1]: Entering directory '/home/cy023/linux2022/fibdrv' sudo rmmod fibdrv || true >/dev/null make[1]: Leaving directory '/home/cy023/linux2022/fibdrv' Passed [-] f(93) fail input: 7540113804746346429 expected: 12200160415121876738 ``` ```bash $ modinfo fibdrv.ko filename: /home/cy023/linux2022/fibdrv/fibdrv.ko version: 0.1 description: Fibonacci engine driver author: National Cheng Kung University, Taiwan license: Dual MIT/GPL srcversion: 9A01E3671A116ADA9F2BB0A depends: retpoline: Y name: fibdrv vermagic: 5.13.0-30-generic SMP mod_unload modversions ``` ```bash $ sudo insmod fibdrv.ko $ ls -l /dev/fibonacci crw------- 1 root root 508, 0 Mar 4 21:01 /dev/fibonacci ``` ```bash $ cat /sys/class/fibonacci/fibonacci/dev 508:0 ``` ```bash $ cat /sys/module/fibdrv/version 0.1 ``` ```bash $ lsmod | grep fibdrv fibdrv 16384 0 $ cat /sys/module/fibdrv/refcnt 0 ``` ### VLA issue 參考 [tabulation-vs-memoization](https://www.geeksforgeeks.org/tabulation-vs-memoization/)。 ```c static long long fib_sequence(long long k) { /* FIXME: C99 variable-length array (VLA) is not allowed in Linux kernel. */ long long f[k + 2]; f[0] = 0; f[1] = 1; for (int i = 2; i <= k; i++) { f[i] = f[i - 1] + f[i - 2]; } return f[k]; } ``` 上面程式紀錄 fibonacci 計算結果的陣列的大小為 variable length，但是當我們在計算時只有用到前兩筆數字，所以可以只利用兩個變數儲存，這樣就可以避免 `VLA` 並將程式的空間複雜度降到 $O(1)$。 ```c static long long fib_sequence(long long k) { if (k == 0) return 0; if (k == 1) return 1; long long fn = 0, fn1 = 1; long long i = 0; for (i = 2; i <= k; i++) { long long tmp = fn1; fn1 = fn1 + fn; fn = tmp; } return fn1; } ``` ## XS ### 資料結構 ```c typedef union { /* allow strings up to 15 bytes to stay on the stack * use the last byte as a null terminator and to store flags * much like fbstring: * https://github.com/facebook/folly/blob/master/folly/docs/FBString.md */ char data[16]; struct { uint8_t filler[15], /* how many free bytes in this stack allocated string * same idea as fbstring */ space_left : 4, /* if it is on heap, set to 1 */ is_ptr : 1, is_large_string : 1, flag2 : 1, flag3 : 1; }; /* heap allocated */ struct { char *ptr; /* supports strings up to 2^MAX_STR_LEN_BITS - 1 bytes */ size_t size : MAX_STR_LEN_BITS, /* capacity is always a power of 2 (unsigned)-1 */ capacity : 6; /* the last 4 bits are important flags */ }; } xs; ``` - 主要可以分兩部份看 - 長度 <= 15 資料存在此結構中。 ```c struct { uint8_t filler[15], /* how many free bytes in this stack allocated string * same idea as fbstring */ space_left : 4, /* if it is on heap, set to 1 */ is_ptr : 1, is_large_string : 1, flag2 : 1, flag3 : 1; }; ``` - 長度 > 15 使用額外動態配置的空間儲存，此結構變為存放，額外空間的位址、大小等資訊。 ```c /* heap allocated */ struct { char *ptr; /* supports strings up to 2^MAX_STR_LEN_BITS - 1 bytes */ size_t size : MAX_STR_LEN_BITS, /* capacity is always a power of 2 (unsigned)-1 */ capacity : 6; /* the last 4 bits are important flags */ }; ``` ### Static Function - bit field 檢查 ```c static inline bool xs_is_ptr(const xs *x) { return x->is_ptr; } static inline bool xs_is_large_string(const xs *x) { return x->is_large_string; } ``` - 查看資料大小 如果 bit field `is_ptr` 是 `1`，資料為動態配置，以**長度 > 15**版本視之，回傳 bit field `size`。 如果 bit field `is_ptr` 是 `0`，資料為靜態配置，以**長度 <= 15**版本視之，回傳 bit field `15 - x->space_left`。 ```c static inline size_t xs_size(const xs *x) { return xs_is_ptr(x) ? x->size : 15 - x->space_left; } ``` - 取得資料起點 ```c static inline char *xs_data(const xs *x) { if (!xs_is_ptr(x)) return (char *) x->data; if (xs_is_large_string(x)) return (char *) (x->ptr + 4); return (char *) x->ptr; } ``` - 查看 capacity ```c static inline size_t xs_capacity(const xs *x) { return xs_is_ptr(x) ? ((size_t) 1 << x->capacity) - 1 : 15; } ```