---
tags: Linux
---

# 2022q1 Homework3 (fibdrv)
contributed by < `LJP-TW` >

# 實驗環境
虛擬機器的組態:

$ uname -r
5.11.0-34-generic

$ lscpu
Architecture:                    x86_64
CPU op-mode(s):                  32-bit, 64-bit
Byte Order:                      Little Endian
Address sizes:                   45 bits physical, 48 bits virtual
CPU(s):                          2
On-line CPU(s) list:             0,1
Thread(s) per core:              1
Core(s) per socket:              1
Socket(s):                       2
NUMA node(s):                    1
Vendor ID:                       AuthenticAMD
CPU family:                      23
Model:                           96
Model name:                      AMD Ryzen 7 PRO 4750U with Radeon Graphics
Stepping:                        1
CPU MHz:                         1696.813
BogoMIPS:                        3393.62

TODO: 於主機進行效能測試。

# 自我檢查清單
TODO

# 修正 fibdrv
為了計算 F~93~ 後的 Fibonacci 數列，需要一套大數運算，在閱讀了作業敘述中的連結 ([Small/Short String Optimization](http://wdv4758h.github.io/notes/cpp/string-optimization.html)。[實作程式碼](https://github.com/AdrianHuang/fibdrv/tree/big_number)。) 後，嘗試自己的實作。

連結的程式碼中，`xs` 實作了大數的結構、運算方式。我將其拆成兩個部分來實作，一個部分是 `sso`，另一部份為 `bignum`，將優化字串的部分，和用優化字串來實作大數的部分兩者區別開來。

目前 `bignum` 還不支持負數運算。

## sso
其結構定義如下 ([程式碼](https://github.com/LJP-TW/fibdrv/blob/master/sso.h#L8)):

#define SSO_CAPACITY 0x17

typedef union {
    char data[0x18];

    struct {
        uint8_t filler[SSO_CAPACITY];

        union {
            uint8_t flags;

            struct {
                uint8_t is_ptr : 1, reserved : 2,
                    left : 5;  // SSO_CAPACITY - size
            };
        };
    };

    struct {
        char *ptr;
        size_t size;
        size_t capacity;
    };
} sso_s;

* 當 `is_ptr` 為 0 時，表示為 sso mode，使用 `filler` 來存放字串，在此字串佔滿空間後，`left` 也會為 0，使得最後 1 byte 為 NULL byte，作為 `filler` 的 terminated byte。
* 當 `is_ptr` 為 1 時，則表示字串實際存放位址是從記憶體管理機制分配來的空間，由 `ptr` 指著，大小以及容量分別由 `size` 和 `capacity` 所存放。
* `capacity` 的最高 byte 為 flags，因此在存取 `capacity` 時須通過以下函式 ([程式碼](https://github.com/LJP-TW/fibdrv/blob/master/sso.c#L16)):

void sso_set_capacity(sso_s *sso, size_t capacity)
{
    if (sso->is_ptr) {
        // Preserve flags setting
        sso->capacity = (sso->capacity & (0xff00000000000000)) | capacity;
    }
}

size_t sso_get_capacity(sso_s *sso)
{
    if (sso->is_ptr) {
        return sso->capacity & (0x00ffffffffffffff);  // Exclude flag field
    } else {
        return SSO_CAPACITY;
    }
}

## bignum
其結構定義如下 ([程式碼](https://github.com/LJP-TW/fibdrv/blob/master/bignum.h#L10)):

typedef struct {
    sso_s sso;  // Must be first member of this struct
    /*
     * mode:
     *  0: Calculatable
     *  1: Outputable
     */
    int mode;
} bignum;

`sso_s` 結構為 `bignum` 結構的第一個 member，就能在呼叫以 `sso_s *` 作為參數的函式時，能方便地直接傳遞 `bignum *`，例如以下程式碼片段 ([程式碼](https://github.com/LJP-TW/fibdrv/blob/master/bignum.c#L132)):

size_t bn_size(bignum *bn)
{
    return sso_get_size((sso_s *) bn);
}

為了實作 fast Fibonacci algorithm，需要的函式有以下:
* `bn_init`: 初始化 `bignum` 為指定數字。
* `bn_release`: 釋放 `bignum` 所使用的資源。
* `bn_add`: 實作 `c = a + b`。
* `bn_sub`: 實作 `c = a - b`。
* `bn_mul`: 實作 `c = a * b`。
* `bn_assign`: 實作 `a = b`。
* `bn_str`: 取得 `bignum` 的大數字串。
* `bn_size`: 取得 `bignum` 大數字串的長度。

### bn_init
[程式碼](https://github.com/LJP-TW/fibdrv/blob/master/bignum.c#L110):

void bn_init(bignum *bn, int num)
{
    int size = 0;

    do {
        bn->sso.filler[size++] = num % 10 + '0';
        num /= 10;
    } while (num);

    bn->sso.filler[size] = 0;

    bn->mode = BN_MOD_CALCULATABLE;

    sso_clear_flag((sso_s *) bn);
    sso_set_size((sso_s *) bn, size);
}

將 `num` 轉為字串形式存至 `bignum`。

由於 `int` 的範圍最大僅為 2147483647，為 10 個字元，因此一定能夠使用 sso mode 來存放。

`sso_clear_flag` 同時也將 `is_ptr` 清除為 0，不用額外設置 `is_ptr`。

### bn_release
[程式碼](https://github.com/LJP-TW/fibdrv/blob/master/bignum.c#L127):

void bn_release(bignum *bn)
{
    sso_release((sso_s *) bn);
}

現階段的實作只需要呼叫 `sso_release` 即可，其會根據 `bn` 是否為 sso mode，來決定是否釋放 `ptr`。

### bn_add
[程式碼](https://github.com/LJP-TW/fibdrv/blob/master/bignum.c#L221):

void bn_add(bignum *op1, bignum *op2, bignum *result)
{
    char *str_op1, *str_op2, *str_result;
    size_t sz_op1, sz_op2, cap_left, i;
    int carry;

    bn_mode_to_cal(op1);
    bn_mode_to_cal(op2);
    bn_mode_to_cal(result);

    if (bn_size(op1) < bn_size(op2)) {
        // Swap pointers
        bignum *tmp = op1;
        op1 = op2;
        op2 = tmp;
    }

    str_op1 = sso_get_data((sso_s *) op1);
    str_op2 = sso_get_data((sso_s *) op2);
    str_result = sso_get_data((sso_s *) result);
    sz_op1 = bn_size(op1);
    sz_op2 = bn_size(op2);
    cap_left = sso_get_capacity((sso_s *) result);

    carry = 0;

    for (i = 0; i < sz_op2; ++i) {
        int num;

        if (!cap_left) {
            if (!bn_extend_capacity(result, i, &cap_left, &str_result)) {
                return;
            }
        }

        num = str_op1[i] - '0' + str_op2[i] - '0' + carry;
        str_result[i] = num % 10 + '0';
        carry = num / 10;
        cap_left -= 1;
    }

    for (; i < sz_op1; ++i) {
        int num;

        if (!cap_left) {
            if (!bn_extend_capacity(result, i, &cap_left, &str_result)) {
                return;
            }
        }

        num = str_op1[i] - '0' + carry;
        str_result[i] = num % 10 + '0';
        carry = num / 10;
        cap_left -= 1;
    }

    if (carry) {
        if (cap_left == (size_t) 0) {
            if (!bn_extend_capacity(result, i, &cap_left, &str_result)) {
                return;
            }
        }

        str_result[i++] = '1';
        cap_left -= 1;
    }

    str_result[i] = 0;

    sso_set_size((sso_s *) result, i);
}

先用 `bn_mode_to_cal` 將要被運算的 `bignum` 都轉為 calculatable mode，參考以下函式 ([程式碼](https://github.com/LJP-TW/fibdrv/blob/master/bignum.c#L23))，其根據目前是要計算或是輸出，來進行 `bn_reverse` 將大數字串倒置:

static void bn_mode_to_cal(bignum *bn)
{
    if (bn->mode == BN_MOD_OUTPUTABLE) {
        bn_reverse(bn);
        bn->mode = BN_MOD_CALCULATABLE;
    }
}

static void bn_mode_to_out(bignum *bn)
{
    if (bn->mode == BN_MOD_CALCULATABLE) {
        bn_reverse(bn);
        bn->mode = BN_MOD_OUTPUTABLE;
    }
}

接著的演算法步驟如下:
1. 確保 `op1` 為數字較多的那方。
2. 變數 i 迴圈從 0 到 `op2` size - 1，將 `op1`、`op2` 第 i 個數字和 carry 相加，存到 `result` 第 i 個數字。設置 carry，必要時擴展 `result` 容量。
3. 變數 i 迴圈繼續到 `op1` size - 1，將 `op1` 第 i 個數字和 carry 相加，存到 `result` 第 i 個數字。設置 carry，必要時擴展 `result` 容量。
4. 若 carry 為 1，則將 `result` 的第 i 個數字設為 1，必要時擴展 `result` 容量。
5. 為 `result` 加上 NULL byte。
6. 為 `result` 設置 size。

由於設置 `result` 的第 i 個字時，已經不會再用到 `op1`、`op2` 的第 i 個數字，因此此函式可以直接支援類似 `bn_add(ptr_same_bn, ptr_same_bn, ptr_same_bn)` 這種 `bignum` 同時為 dst 和 src 的操作。

### bn_sub
[程式碼](https://github.com/LJP-TW/fibdrv/blob/master/bignum.c#L293):

void bn_sub(bignum *op1, bignum *op2, bignum *result)
{
    char *str_op1, *str_op2, *str_result;
    size_t sz_op1, sz_op2, cap_left, i;
    int borrow;

    if (bn_cmp(op1, op2) < 0) {
        // TODO: Support negative big number
        return;
    }

    if (!bn_cmp(op1, op2)) {
        bn_release(result);
        bn_init(result, 0);
        return;
    }

    bn_mode_to_cal(op1);
    bn_mode_to_cal(op2);
    bn_mode_to_cal(result);

    str_op1 = sso_get_data((sso_s *) op1);
    str_op2 = sso_get_data((sso_s *) op2);
    str_result = sso_get_data((sso_s *) result);
    sz_op1 = bn_size(op1);
    sz_op2 = bn_size(op2);
    cap_left = sso_get_capacity((sso_s *) result);

    borrow = 0;

    for (i = 0; i < sz_op2; ++i) {
        int num;

        if (!cap_left) {
            if (!bn_extend_capacity(result, i, &cap_left, &str_result)) {
                return;
            }
        }

        num = str_op1[i] - str_op2[i] - borrow;

        if (num < 0) {
            num += 10;
            borrow = 1;
        } else {
            borrow = 0;
        }

        str_result[i] = num + '0';
        cap_left -= 1;
    }

    for (; i < sz_op1; ++i) {
        int num;

        if (!cap_left) {
            if (!bn_extend_capacity(result, i, &cap_left, &str_result)) {
                return;
            }
        }

        num = str_op1[i] - '0' - borrow;

        if (num < 0) {
            num += 10;
            borrow = 1;
        } else {
            borrow = 0;
        }

        str_result[i] = num + '0';
        cap_left -= 1;
    }


    if (str_result[i - 1] == '0') {
        i -= 1;
    }

    str_result[i] = 0;

    sso_set_size((sso_s *) result, i);
}

演算法步驟如下:
1. 確保 `op1` 為數字較大的那方。
2. 變數 i 迴圈從 0 到 `op2` size - 1，將 `op1`、`op2` 第 i 個數字相減，並減去 borrow，存到 `result` 第 i 個數字。設置 borrow，必要時擴展 `result` 容量。
3. 變數 i 迴圈繼續到 `op1` size - 1，將 `op1` 第 i 個數字和 borrow 相減，存到 `result` 第 i 個數字。設置 borrow，必要時擴展 `result` 容量。
4. 若 result 的第 i - 1 個字為 0，表示其剛剛被借位減去，將 i -= 1，使其為 NULL byte index。
5. 為 `result` 加上 NULL byte。
6. 為 `result` 設置 size。

### bn_mul
[程式碼](https://github.com/LJP-TW/fibdrv/blob/master/bignum.c#L144):

void bn_mul(bignum *op1, bignum *op2, bignum *result)
{
    bignum tmp;
    char *str_op1, *str_op2, *str_result;
    size_t sz_op1, sz_op2, cap, i, j, inited;

    bn_mode_to_cal(op1);
    bn_mode_to_cal(op2);
    bn_mode_to_cal(result);

    bn_init(&tmp, 0);

    str_op1 = sso_get_data((sso_s *) op1);
    str_op2 = sso_get_data((sso_s *) op2);
    str_result = sso_get_data((sso_s *) &tmp);
    sz_op1 = bn_size(op1);
    sz_op2 = bn_size(op2);
    cap = sso_get_capacity((sso_s *) &tmp);

    inited = 0;

    for (i = 0; i < sz_op2; ++i) {
        int num2;

        num2 = str_op2[i] - '0';

        for (j = 0; j < sz_op1; ++j) {
            int num;

            num = (str_op1[j] - '0') * num2;

            if (i + j >= cap) {
                if (!bn_extend_capacity2(&tmp, &cap, &str_result)) {
                    return;
                }
            }

            if (i + j == 0 || i + j > inited) {
                inited = i + j;
            } else {
                num += str_result[i + j];
            }

            str_result[i + j] = num % 10;

            if (i + j + 1 >= cap) {
                if (!bn_extend_capacity2(&tmp, &cap, &str_result)) {
                    return;
                }
            }

            if (i + j + 1 > inited) {
                str_result[i + j + 1] = num / 10;
                inited = i + j + 1;
            } else {
                str_result[i + j + 1] += num / 10;
            }
        }
    }

    for (i = 0; i <= inited; ++i) {
        str_result[i] += '0';
    }

    if (str_result[inited] != '0') {
        inited += 1;
    }

    str_result[inited] = 0;

    sso_set_size((sso_s *) &tmp, inited);

    bn_assign(result, &tmp);

    bn_release(&tmp);
}

演算法步驟如下:
1. `inited = 0`，其代表目前 `tmp` 的數字字串中，已經初始化過的最大 index。
2. `i` 迴圈從 0 走到 `op2` size - 1:
1. 取得 `str_op2[i]` 放到 num2
2. `j` 迴圈從 0 走到 `op1` size - 1:
1. 將 `str_op1[j]` 與 num2 相乘，存到 num
2. 若 `i + j` 為 0 或是 `i + j > inited`，表示目前將要把計算結果存放到未被初始化過的 `str_tmp[i + j]`，更新 `inited = i + j`；否則表示 `str_tmp[i + j]` 已經存放著稍早的計算結果，將 `num += str_tmp[i + j]`。必要時擴展 `tmp` 容量。
3. `str_tmp[i + j] = num % 10`。
4. 若 `i + j + 1 > inited`，表示目前將要把進位結果存放到未被初始化過的 `str_tmp[i + j + 1]`，更新 `inited = i + j + 1`，並設置 `str_tmp[i + j + 1] = num / 10`；否則表示 `str_tmp[i + j + 1]` 已經存放著稍早的計算結果，直接將進位結果加進去 `str_tmp[i + j + 1] += num / 10`。必要時擴展 `tmp` 容量。
3. 將 `tmp` 的內容全部加 `'0'` 使其從數字變成數字字串。
4. 判斷最後一個字是否為 `'0'`，調整 NULL byte index。
5. 為 `tmp` 加上 NULL byte。
6. 為 `tmp` 設置 size。
7. 將 `tmp` 內容指派給 `result`。

由於設置 `tmp` 的第 i 個字時，還是有可能再用到 `op1`、`op2` 的第 i 個數字，因此此函式無法直接支援類似 `bn_add(ptr_same_bn, ptr_same_bn, ptr_same_bn)` 這種 `bignum` 同時為 dst 和 src 的操作。需要在函式內部新建立一個 `tmp` 作為暫時的 dst，操作結束後再將 `tmp` 指派給真正的 dst，才能支援類似操作。

### bn_assign
[程式碼](https://github.com/LJP-TW/fibdrv/blob/master/bignum.c#L377):

void bn_assign(bignum *to, bignum *from)
{
    bn_mode_to_cal(to);
    bn_mode_to_cal(from);

    sso_assign((sso_s *) to, (sso_s *) from);
}

將兩者調整為同一種運算模式後，再呼叫 `sso_assign`。

### bn_str
[程式碼](https://github.com/LJP-TW/fibdrv/blob/master/bignum.c#L137):

char *bn_str(bignum *bn)
{
    bn_mode_to_out(bn);

    return sso_get_data((sso_s *) bn);
}

將模式調整為輸出模式後，再呼叫 `sso_get_data`。

### bn_size
[程式碼](https://github.com/LJP-TW/fibdrv/blob/master/bignum.c#L132):

size_t bn_size(bignum *bn)
{
    return sso_get_size((sso_s *) bn);
}

呼叫 `sso_get_size` 取得 `sso_s` 結構 size。

## fibdrv

### fib_sequence
實作 fast Fibonacci algorithm ([程式碼](https://github.com/LJP-TW/fibdrv/blob/master/fibdrv.c#L29)):

static void fib_sequence(long long k, bignum *result)
{
    bignum fk0;   // F(k)
    bignum fk1;   // F(k+1)
    bignum fk20;  // F(2k)
    bignum fk21;  // F(2k+1)
    bignum tmp1, tmp2;

    if (k < 2) {
        bn_release(result);
        bn_init(result, k);
        return;
    }

    bn_init(&fk0, 1);
    bn_init(&fk1, 1);
    bn_init(&fk20, 0);
    bn_init(&fk21, 0);
    bn_init(&tmp1, 0);
    bn_init(&tmp2, 0);

    long long mask = 1 << (fls(k) - 2);

    while (mask) {
        bn_add(&fk1, &fk1, &tmp1);
        bn_sub(&tmp1, &fk0, &tmp1);
        bn_mul(&fk0, &tmp1, &fk20);  // fk20 = fk0 * (2 * fk1 - fk0)

        bn_mul(&fk0, &fk0, &tmp1);
        bn_mul(&fk1, &fk1, &tmp2);
        bn_add(&tmp1, &tmp2, &fk21);  // fk21 = fk0 * fk0 + fk1 * fk1

        bn_assign(&fk0, &fk20);  // fk0 = fk20
        bn_assign(&fk1, &fk21);  // fk1 = fk21

        if (k & mask) {
            bn_add(&fk0, &fk1, &fk20);  // fk20 = fk0 + fk1
            bn_assign(&fk0, &fk1);      // fk0 = fk1
            bn_assign(&fk1, &fk20);     // fk1 = fk20
        }

        mask >>= 1;
    }

    bn_assign(result, &fk0);  // return fk0

    bn_release(&fk0);
    bn_release(&fk1);
    bn_release(&fk20);
    bn_release(&fk21);
    bn_release(&tmp1);
    bn_release(&tmp2);
}

跳過 F~0~，從 F~1~ 開始運算。

### fib_read
調整 `fib_read` ([程式碼](https://github.com/LJP-TW/fibdrv/blob/master/fibdrv.c#L99)):

/* calculate the fibonacci number at given offset */
static ssize_t fib_read(struct file *file,
                        char *buf,
                        size_t size,
                        loff_t *offset)
{
    bignum result;
    int n;

    bn_init(&result, 0);

    fib_sequence(*offset, &result);

    n = bn_size(&result);

    if (n + 1 <= size) {
        if (copy_to_user(buf, bn_str(&result), n + 1))
            return -EFAULT;
    }

    bn_release(&result);

    return n;
}

`n + 1` 連同 NULL byte 複製到 user space。

若使用者 buffer size 不夠，則不進行複製，只回傳 Fibonacci number 字串長度告知使用者。

## client
buffer 改成用足夠的空間來接收字串:

#define BUF_SIZE 0x200

int main()
{
    char buf[BUF_SIZE];
    ...
}

改變輸出方式，從原本的以 `read` 回傳值得到結果，改成從 `buf` 得到結果:

int main()
{
    ...
        sz = read(fd, buf, BUF_SIZE);
        printf("Reading from " FIB_DEV
               " at offset %d, returned the sequence "
               "%s.\n",
               i, buf);
    ...
}

## Makefile

TARGET_MODULE := fibdrv_bn

obj-m += $(TARGET_MODULE).o
$(TARGET_MODULE)-objs := fibdrv.o bignum.o sso.o

`TARGET_MODULE` 需和 `fibdrv` 不同名稱；`$(TARGET_MODULE)-objs` 指定所需的 object files。

原先的 `make check` 使用到 `scripts/expected.txt`，其只是舊實作的結果輸出，將其刪去:

check: all
	$(MAKE) unload
	$(MAKE) load
	sudo ./client > out
	$(MAKE) unload
	@scripts/verify.py