2022q1 Homework3 (fibdrv)

$ git clone [e-mail]:cy023/fibdrv.git

$ 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

$ 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

$ sudo insmod fibdrv.ko
$ ls -l /dev/fibonacci
crw------- 1 root root 508, 0 Mar  4 21:01 /dev/fibonacci

$ cat /sys/class/fibonacci/fibonacci/dev
508:0

$ cat /sys/module/fibdrv/version 
0.1

$ lsmod | grep fibdrv
fibdrv                 16384  0
$ cat /sys/module/fibdrv/refcnt 
0

VLA issue

參考 tabulation-vs-memoization。

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)$。

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

資料結構

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
    資料存在此結構中。
    ​​​​​​​​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
    使用額外動態配置的空間儲存，此結構變為存放，額外空間的位址、大小等資訊。
    ​​​​​​​​/* 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 檢查

  ​​​​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。

  ​​​​static inline size_t xs_size(const xs *x)
  ​​​​{
  ​​​​    return xs_is_ptr(x) ? x->size : 15 - x->space_left;
  ​​​​}
  

• 取得資料起點

  ​​​​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

  ​​​​static inline size_t xs_capacity(const xs *x)
  ​​​​{
  ​​​​    return xs_is_ptr(x) ? ((size_t) 1 << x->capacity) - 1 : 15;
  ​​​​}