---
# System prepended metadata

title: 2023q1 Homework3 (fibdrv)
tags: [Linux Kernel]

---

---
tags: Linux Kernel
---

# 2023q1 Homework3 (fibdrv)
contributed by < [`chun61205`](https://github.com/chun61205) >

> [K04: fibdrv](https://hackmd.io/@sysprog/linux2022-fibdrv)
## 實驗環境
```bash
$ 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):                  8
  On-line CPU(s) list:   0-7
Vendor ID:               GenuineIntel
  Model name:            Intel(R) Core(TM) i5-1035G1 CPU @ 1.00GHz
    CPU family:          6
    Model:               126
    Thread(s) per core:  2
    Core(s) per socket:  4
    Socket(s):           1
    Stepping:            5
    CPU max MHz:         3600.0000
    CPU min MHz:         400.0000
    BogoMIPS:            2380.80
```
## 開發紀錄
### Fast Doubling
$F(2k) = F(k)[2F(k+1) - F(k)] \\ F(2k+1) = F(k+1)^2+F(k)^2$

$F(10)$:
10~10~ = 1010~2~
| i | start | 4        | 3        | 2        | 1       | result |
|---|-------|----------|----------|----------|---------|--------|
| n | -     | ==1==010 | 1==0==10 | 10==1==0 | 101==0== |  - |
|F(m) | F(0) | F(0*2+1) | F(1*2) | F(2*2+1) | F(5*2) | F(10) |
| a | 0 | 1 | 1 | 5 | 55 | 55 |
| b | 1 | 1 | 2 | 8 | 89 | - |
### 引入 Fast Doubling
原本 fibdrv 採用 Dynamic Programming 實作 `fib_sequence` ，為了減少計算量，我引入 Fast Doubling 並加入 GCC`__uint128_t` 以增加能夠計算的大小。
```c
static __uint128_t fib_sequence(int k)
{
    if (k < 2)
        return k;
    __uint128_t a = 0, b = 1, t1, t2;
    int len = 32 - __builtin_clz(k);
    for(; len > 0; len--){
        t1 = a * (2 * b - a);
        t2 = b * b + a * a;
        a = t1;
        b = t2;
        if((k >> (len - 1)) & 0x1){
            t1 = a + b;
            a = b;
            b = t1;
        }
    }
    return a;
}
```
然而，經過測試，上面這段程式碼無法解決 $F(93)$ 會得出錯誤結果的問題。推測原因如下：
```c
static ssize_t fib_read(struct file *file,
                        char *buf,
                        size_t size,
                        loff_t *offset)
{
    return (ssize_t) fib_sequence(*offset);
}
```
這段程式碼會將 `fib_sequence` 的回傳值改成 `ssize_t` ，因此單是更改 `fib_sequence` 的回傳值型態無法解決問題，計畫在研究 [Small/Short String Optimization](http://wdv4758h.github.io/notes/cpp/string-optimization.html) 和 [sysprog21/bignum](https://github.com/sysprog21/bignum) 後改善。
### F(93) 會計算錯誤的原因
參考 [yanjiew1](https://hackmd.io/v4itYIvpToq0rICnuRAvLQ?both)
透過公式解可直接計算第 $n$ 個費氏數：

$$
F(n)= \frac{(\phi^n)-(1-\phi)^n}{\sqrt5} \\
\phi \text{  (golden ratio)} = \frac{1+\sqrt5}{2} \approx 1.61803398875
$$

當 n 足夠大時，可得到約略值:

$$
F(n) \approx \frac{\phi^n}{\sqrt5} \approx 0.4472135955 \times 1.61803398875^n
$$

取得以 2 為底的對數

$$
\log F(n) \approx -1.160964 + n\times0.694242
$$

這裡的 $logF(n)$ 正好表示需要多少 bits 才能完全表達 $F(n)$ 。
$$
logF(93) \approx 63.4
$$
因此會造成 overflow 。

若是代入 $logF(n)=128$ ，則 $n\approx186$
大概可以表示到 $F(186)$
### 研究大數運算
#### `bn` 資料結構
:::spoiler 完整程式碼
```c
/* number[size - 1] = msb, number[0] = lsb */
typedef struct _bn {
    unsigned int *number;
    unsigned int size;
    int sign;
} bn;
```
* `number` - 指向儲存的數值，之後會以 array 的形式來取用
* `size` - 配置的記憶體大小，單位為 sizeof(unsigned int)
* `sign` - `0` 為正數、`1` 為負數
#### `bn_to_string`
由於大數沒辦法直接以數值的形式列出，因此需要透過此函數來轉換成字串。
:::spoiler 完整程式碼
```c
/* 
 * output bn to decimal string
 * Note: the returned string should be freed with kfree()
 */
char *bn_to_string(bn src)
{
    // log10(x) = log2(x) / log2(10) ~= log2(x) / 3.322
    size_t len = (8 * sizeof(int) * src.size) / 3 + 2 + src.sign;
    char *s = kmalloc(len, GFP_KERNEL);
    char *p = s;

    memset(s, '0', len - 1);
    s[len - 1] = '\0';

    for (int i = src.size - 1; i >= 0; i--) {
        for (unsigned int d = 1U << 31; d; d >>= 1) {
            /* binary -> decimal string */
            int carry = !!(d & src.number[i]);
            for (int j = len - 2; j >= 0; j--) {
                s[j] += s[j] - '0' + carry; // double it
                carry = (s[j] > '9');
                if (carry)
                    s[j] -= 10;
            }
        }
    }
    // skip leading zero
    while (p[0] == '0' && p[1] != '\0') { 
        p++;
    }
    if (src.sign)
        *(--p) = '-';
    memmove(s, p, strlen(p) + 1);
    return s;
}
```
:::
* `kmalloc` 會分配連續的虛擬記憶體，同時也會分配連續的實體記憶體。而 `vmalloc` 則會分配非連續的實體記憶體空間，因此需要映射時，效率較低。
* `for` 迴圈會將 `bn` 轉換成 `string`
    * 每 $32$ 個 bytes 處理一次
    * `carry` 表示是否進位初始值為 ``!!(d & src.number[i])``
    * `s[j] += s[j] - '0' + carry` 累加的方式為原本的數值乘以二再加上 `carry`
    * 最後如果有進位則減去 $10$
* 最後將 leading zero 去掉後返回

::: info
待確認： 為什麼 `len` 的計算是除以 `3` 而不是 `3.322`
猜測如下：
1. 整數的除法相較浮點數的除法來的快速，因此使用整數 `3`
2. 最後會將 leading zero 去除，因此除數少一點點使得 `len` 多出來的部份會被去除掉

順帶一提， chatgpt 回答如下：
![](https://i.imgur.com/OVy39Bp.png)
:::
#### `bn_add` 和 `bn_sub`
:::spoiler 完整程式碼
```c
/* c = a + b 
 * Note: work for c == a or c == b
 */
void bn_add(const bn *a, const bn *b, bn *c)
{
    if (a->sign == b->sign) { // both positive or negative
        bn_do_add(a, b, c);
        c->sign = a->sign;
    } else { // different sign
        if (a->sign)  // let a > 0, b < 0
            SWAP(a, b);
        int cmp = bn_cmp(a, b);
        if (cmp > 0) {
            /* |a| > |b| and b < 0, hence c = a - |b| */
            bn_do_sub(a, b, c);
            c->sign = 0;
        } else if (cmp < 0) {
            /* |a| < |b| and b < 0, hence c = -(|b| - |a|) */
            bn_do_sub(b, a, c);
            c->sign = 1;
        } else {
            /* |a| == |b| */
            bn_resize(c, 1);
            c->number[0] = 0;
            c->sign = 0;
        }
    }
}

/* c = a - b 
 * Note: work for c == a or c == b
 */
void bn_sub(const bn *a, const bn *b, bn *c)
{
    /* xor the sign bit of b and let bn_add handle it */
    bn tmp = *b;
    tmp.sign ^= 1; // a - b = a + (-b)
    bn_add(a, &tmp, c);
}
```
:::
* `bn_add` 會先判斷 `a` 和 `b` 的 `sign` 如果是一樣的就做加法，不一樣的就做減法。而 `bn_sub` 則是直接將 `a` 和 `b` 交給 `bn_add` 處理。
#### `bn_do_add`
:::spoiler 完整程式碼
```c
/* |c| = |a| + |b| */
static void bn_do_add(const bn *a, const bn *b, bn *c)
{
    // max digits = max(sizeof(a) + sizeof(b)) + 1
    int d = MAX(bn_msb(a), bn_msb(b)) + 1;
    d = DIV_ROUNDUP(d, 32) + !d;
    bn_resize(c, d); // round up, min size = 1

    unsigned long long int carry = 0;
    for (int i = 0; i < c->size; i++) {
        unsigned int tmp1 = (i < a->size) ? a->number[i] : 0;
        unsigned int tmp2 = (i < b->size) ? b->number[i] : 0;
        carry += (unsigned long long int) tmp1 + tmp2;
        c->number[i] = carry;
        carry >>= 32;
    }

    if (!c->number[c->size - 1] && c->size > 1)
        bn_resize(c, c->size - 1);
}
```
:::
* `d` 代表總位數
    * `MAX(bn_msb(a), bn_msb(b)) + 1` 的 `+1` 是為了避免 `MAX(bn_msb(a), bn_msb(b))` 溢位。
    * `DIV_ROUNDUP` 表示向上取整數，會回傳 `d` 是 `32` 的幾倍
    * 因為 `d` 的最小值應該為 `1` ，如果 `d = 0` ，則應該加上 `!d` ，也就是 `1`
* 利用 `for (int i = 0; i < c->size; i++)` 將各個位數相加。
#### `bn_do_sub`
:::spoiler 完整程式碼
```c
/* 
 * |c| = |a| - |b| 
 * Note: |a| > |b| must be true
 */
static void bn_do_sub(const bn *a, const bn *b, bn *c)
{
    // max digits = max(sizeof(a) + sizeof(b))
    int d = MAX(a->size, b->size);
    bn_resize(c, d);

    long long int carry = 0;
    for (int i = 0; i < c->size; i++) {
        unsigned int tmp1 = (i < a->size) ? a->number[i] : 0;
        unsigned int tmp2 = (i < b->size) ? b->number[i] : 0;
        carry = (long long int) tmp1 - tmp2 - carry;
        if (carry < 0) {
            c->number[i] = carry + (1LL << 32);
            carry = 1;
        } else {
            c->number[i] = carry;
            carry = 0;
        }
    }
    
    d = bn_clz(c) / 32;
    if (d == c->size)
        --d;
    bn_resize(c, c->size - d);
}
```
:::
計算邏輯大部分和 `bn_do_add` 相同，不過如果相減小於 $0$ 則需要先對調 `a` 和 `b` 。
* 這裡的 `carry` 表示借位。
#### `bn_mult`
:::spoiler 完整程式碼
```c
/* 
 * c = a x b
 * Note: work for c == a or c == b
 * using the simple quadratic-time algorithm (long multiplication)
 */
void bn_mult(const bn *a, const bn *b, bn *c)
{
    // max digits = sizeof(a) + sizeof(b))
    int d = bn_msb(a) + bn_msb(b);
    d = DIV_ROUNDUP(d, 32) + !d; // round up, min size = 1
    bn *tmp;
    /* make it work properly when c == a or c == b */
    if (c == a || c == b) {
        tmp = c; // save c
        c = bn_alloc(d);
    } else {
        tmp = NULL;
        for (int i = 0; i < c->size; i++)
            c->number[i] = 0;
        bn_resize(c, d);
    }
    
    for (int i = 0; i < a->size; i++) {
        for (int j = 0; j < b->size; j++) {
            unsigned long long int carry = 0;
            carry = (unsigned long long int) a->number[i] * b->number[j];
            bn_mult_add(c, i + j, carry);
        }
    }
    c->sign = a->sign ^ b->sign;

    if (tmp) {
        bn_swap(tmp, c); // restore c
        bn_free(c);
    }
}
/* c += x, starting from offset */
static void bn_mult_add(bn*c, int offset, unsigned long long int x)
{
    unsigned long long int carry = 0;
    for (int i = offset; i < c->size; i++) {
        carry += c->number[i] + (x & 0xFFFFFFFF);
        c->number[i] = carry;
        carry >>= 32;
        x >>= 32;
        if (!x && ! carry) //done
            return;
    }
}
```
:::
此程式碼分別計算每一個位數的乘法，以得到答案。
```c
for (int i = 0; i < a->size; i++) {
    for (int j = 0; j < b->size; j++) {
        unsigned long long int carry = 0;
        carry = (unsigned long long int) a->number[i] * b->number[j];
        bn_mult_add(c, i + j, carry);
    }
}
```
#### `bn_lshift`
:::spoiler 完整程式碼
```c
/* left bit shift on bn (maximun shift 31) */
void bn_lshift(const bn *src, size_t shift, bn *dest)
{
    size_t z = bn_clz(src);
    shift %= 32;  // only handle shift within 32 bits atm
    if (!shift)
        return;

    if (shift > z) {
        bn_resize(dest, src->size + 1);
    } else {
        bn_resize(dest, src->size);
    }
    /* bit shift */
    for (int i = src->size - 1; i > 0; i--)
        dest->number[i] =
            src->number[i] << shift | src->number[i - 1] >> (32 - shift);
    dest->number[0] = src->number[0] << shift;
}
```
:::
此程式碼可以將 `src` 向左 shift。
1. 此程式碼最大可 shift 的位元數為 $32$
    ```c
    shift %= 32;
    ```
2. 為了處理 left shift 超出的位元，必須將 `src->number[i]` 的最右邊 `32 - shift` 個位元，串接上 `src->number[i-1]` 最左邊的 `shift` 個位元。
    ```c
    dest->number[i] = src->number[i] << shift | src->number[i - 1] >> (32 - shift);   ```
#### `bn_clz`
:::spoiler 完整程式碼
```c
/* count leading zeros of src*/
static int bn_clz(const bn *src)
{
    int cnt = 0;
    for (int i = src->size - 1; i >= 0; i--) {
        if (src->number[i]) {
            // prevent undefined behavior when src = 0
            cnt += __builtin_clz(src->number[i]);
            return cnt;
        } else {
            cnt += 32;
        }
    }
    return cnt;
}
```
:::
此程式碼透過 `__builtin_clz` 計算 leading zero ，如果迴圈遇到非零的數，則代表最高位數在該格中，因此計算完後回傳結果。
### 使用大數運算來實做 `fib_sequence`

:::spoiler 完整程式碼
```c
static void bn_fib_sequence(bn *dest, int k)
{
    bn_resize(dest, 1);
    if (k < 2) {
        dest->number[0] = k;
        return;
    }
    /* a: F(k), b: F(k+1) */
    bn *a = dest, *b = bn_alloc(1);
    a->number[0] = 0;
    b->number[0] = 1;
    bn *t1 = bn_alloc(1), *t2 = bn_alloc(1);
    for (unsigned int i = 1U << 31; i; i >>= 1) {
        /* F(2k) = F(k) * [ 2 * F(k+1) – F(k) ] */
        bn_cpy(t1, b);
        bn_lshift(t1, 1);
        bn_sub(t1, a, t1);
        bn_mult(t1, a, t1);
        /* F(2k+1) = F(k)^2 + F(k+1)^2 */
        bn_mult(a, a, a);
        bn_mult(b, b, b);
        bn_add(t2, a, b);
        if (k & i) {
            bn_cpy(a, t2);
            bn_cpy(b, t1);
            bn_add(b, t2, b);
        } else {
            bn_cpy(a, t1);
            bn_cpy(b, t2);
        }
    }
    bn_free(b);
    bn_free(t1);
    bn_free(t2);
}
```
:::
並透過 `copy_to_user` 把資料傳送到 user mode 輸出。
```c
bn *fib_time_proxy(long long k)
{
    kt = ktime_get();
    bn *dest = bn_alloc(1);
    fib_fdoubling_bn(dest, k);
    kt = ktime_sub(ktime_get(), kt);
    return dest;
}

static ssize_t fib_read(struct file * file, char *buf, size_t size, loff_t *offset)
{
    bn *dest = fib_time_proxy(*offset);
    char *result = bn_to_string(dest);
    int len = strlen(result);
    copy_to_user(buf, result, len);
    return (ssize_t) len;
}
```
結果如下：
```shell
Reading from /dev/fibonacci at offset 92, returned the sequence 7540113804746346429. utime 33064, ktime 28621
Reading from /dev/fibonacci at offset 93, returned the sequence 12200160415121876738. utime 33287, ktime 28915
Reading from /dev/fibonacci at offset 94, returned the sequence 19740274219868223167. utime 38217, ktime 27735
Reading from /dev/fibonacci at offset 95, returned the sequence 31940434634990099905. utime 37996, ktime 27815
Reading from /dev/fibonacci at offset 96, returned the sequence 51680708854858323072. utime 37179, ktime 27087
Reading from /dev/fibonacci at offset 97, returned the sequence 83621143489848422977. utime 36502, ktime 27363
Reading from /dev/fibonacci at offset 98, returned the sequence 135301852344706746049. utime 35970, ktime 27510
Reading from /dev/fibonacci at offset 99, returned the sequence 218922995834555169026. utime 37317, ktime 28233
Reading from /dev/fibonacci at offset 100, returned the sequence 354224848179261915075. utime 38529, ktime 29498
```
結果正確。
### 量測時間
參考 [shawn5141](https://hackmd.io/@Shawn5141/linux2022q1-hw3#%E9%87%8F%E6%B8%AC%E6%99%82%E9%96%93%E7%9A%84%E6%96%B9%E5%BC%8F) 和 [bakudr18](https://hackmd.io/@bakudr18/HJ363p_Qd#%E6%B8%AC%E9%87%8F-user-space-%E8%88%87-kernel-space-%E6%99%82%E9%96%93)
#### 在 user space 下
使用 [clock_gettime](https://linux.die.net/man/2/clock_gettime) 下的 `CLOCK_MONOTONIC` 來計時，`CLOCK_MONOTONIC` 是從特定起始時間單調遞增的計時方式。
```c
// client.c
static inline long long elapsed(struct timespec *t1, struct timespec *t2)
{
    return (long long) (t2->tv_sec - t1->tv_sec) * 1e9 +
           (long long) (t2->tv_nsec - t1->tv_nsec);
}
for (int i = 0; i <= offset; i++) {
    clock_gettime(CLOCK_MONOTONIC, &t1);
    sz = read(fd, buf, 1);
    clock_gettime(CLOCK_MONOTONIC, &t2);
    long long utime = elapsed(&t1, &t2);
}
```
#### 在 kernel space 下
使用 [hrtimer](https://lwn.net/Articles/167897/) 進行量測。
```c
// fibdrv.c
static ktime_t kt;
static long long fib_time_proxy(long long k)
{
    kt = ktime_get();
    long long result = fib_sequence_dp(k);
    kt = ktime_sub(ktime_get(), kt);

    return result;
}

static ssize_t fib_read(struct file * file, char *buf, size_t size, loff_t *offset)
{
    return (ssize_t) fib_time_proxy(*offset);
}

static ssize_t fib_write(struct file * file, const char *buf, size_t size, loff_t *offset)
{
    return ktime_to_ns(kt);
}
```
```c
// client.c
for (int i = 0; i <= offset; i++) {
    ssize_t kt = write(fd, NULL, 0);
}
```
![](https://i.imgur.com/8RyG7ii.png)
### 研究程式碼的運作方式
程式碼分為 user space 和 kernel space ， `client.c` 可以視為 user space ，剩下的則為 kernel space。
#### 使用 kernel space 的 system call
如果 user space 要使用 kernel space 的 system call ，則必須先掛載核心模組。
```c
$ sudo insmod fibdrv.ko
```
#### File Operations
在 `fibdrv.c` 中，定義了 file operations
```c
// fibdrv.c
const struct file_operations fib_fops = {
    .owner = THIS_MODULE,
    .read = fib_read,
    .write = fib_write,
    .open = fib_open,
    .release = fib_release,
    .llseek = fib_device_lseek,
};
```
舉例來說，如果在 user space 呼叫 `read` ，就相當於在 kernel space 呼叫 `fib_read` 。
#### `offset`
在一開始看到這段程式碼的時候我非常納悶，明明在 `client.c` 並沒有把 `offset` 作為參數傳入，為什麼能夠在 `fib_read` 中使用。
經過調查後得知，`offset` 是在 linux 核心中已經定義好的變數，指向目前檔案系統讀寫的位置。
#### `lseek`
先解釋 `lseek` 。
`lseek` 這個函式的目的在於指定目前讀寫的位置，透過以下程式碼
```c
// client.c
lseek(fd, i, SEEK_SET);
```
`lseek` 能夠將讀寫的位置設定在「從檔案的起頭開始數的第 `i` byte」。
```c
// fibdrv.c
static loff_t fib_device_lseek(struct file * file, loff_t offset, int orig)
{
    loff_t new_pos = 0;
    switch (orig) {
    case 0: /* SEEK_SET: */
        new_pos = offset;
        break;
    case 1: /* SEEK_CUR: */
        new_pos = file->f_pos + offset;
        break;
    case 2: /* SEEK_END: */
        new_pos = MAX_LENGTH - offset;
        break;
    }

    if (new_pos > MAX_LENGTH)
        new_pos = MAX_LENGTH;  // max case
    if (new_pos < 0)
        new_pos = 0;        // min case
    file->f_pos = new_pos;  // This is what we'll use now
    return new_pos;
}
```
從上面的程式碼可以看出， `lseek` 的回傳值為目前檔案的讀寫位置。
值得注意的是，輸入不同的 `orig` 會有不一樣的結果， linux 核心定義的 Macro 如下：
1. `SEEK_SET`: 將檔案讀寫的位置設成 `offset` 。
2. `SEEK_CUR`: 將檔案讀寫的位置設成「當前的位置+ `offset` 」。
3. `SEEK_END`: 將檔案讀寫的位置設成從檔案的尾端向前數 `offset` 處。
#### `read`
了解了 `lseek` 可以來看看 `read` 。
`fibdrv` 的特別之處在於，這裡的程式碼並不是真的為了從檔案系統讀取檔案，而是透過 `lseek` 移動 `offset` ，並將 `offset` 的值傳入 `fib_sequence` 來達到計算 fibonacci number 的效果。
具體作法如下：
1. 透過 `lseek` 移動 `offset`
    ```c
    // client.c
    for (int i = 0; i <= offset; i++) {
        lseek(fd, i, SEEK_SET);
    }
    ```
2. `offset` 被設定為 `i` 的值
    ```c
    // fibdrv.c
    new_pos = offset;
    return new_pos;
    ```
3. 呼叫 `read`
    ```c
    for (int i = 0; i <= offset; i++) {
        sz = read(fd, buf, 1);
    }
    ```
4. `read` 透過 `offset` 來呼叫 `fib_sequence`
    ```c
    static ssize_t fib_read(struct file * file, char *buf, size_t size, loff_t *offset)
    {
        return (ssize_t) fib_time_proxy(*offset);
    }
    ```
### 將 `bn_to_string` 移動到 user space
分析 `fib_fdoubling_bn` 後可以得到下面的圖。
![](https://i.imgur.com/gDrRKOr.png)
可以發現，隨著 `n` 增加， `copy_to_user` 的成本越高，這是因為 copy 的資料越大 `copy_to_user` 的執行時間越多。因此可以嘗試將 `bn_to_string` 移動到 user space ，以此來減少 `copy_to_user` 傳輸的時間成本。
```c
// client.c
unsigned int *tmp = (unsigned int*)buf;
char *s = bn_to_string_user(tmp, len);
````
```c
// fibdrv.c
int len = dest->size;
copy_to_user(buf, (char*)dest->number, 4 * len);
```
結果如下，可以發現 `copy_to_user` 的時間不會明顯隨著 `n` 變大而提升。
![](https://i.imgur.com/pjtuuGr.png)
### 研究 fibdrv 的 mutex
#### 觀察 `fibdrv.c` 的 `__init` 和 `__exit`
> [Linux 核心模組運作原理](https://hackmd.io/@sysprog/linux-kernel-module#Linux-%E6%A0%B8%E5%BF%83%E6%A8%A1%E7%B5%84%E9%81%8B%E4%BD%9C%E5%8E%9F%E7%90%86)

可以看到 kernel
```c
// fibdrv.c
module_init(init_fib_dev);
module_exit(exit_fib_dev);
```
這兩段程式碼分別定義兩個函式， `init_fib_dev` 和 `exit_fib_dev` 。
#### 觀察 `fibdrv.c` 中的 mutex
在 `fibdrv.c` 中有使用到 mutex 的函式除了初始化和刪除 mutex 外總共有兩個， `fib_open` 和 `fib_release`
可以看到在 `fib_open` 時 `/dev/fibonacci` 的存取便會被保護住：
```c
if (!mutex_trylock(&fib_mutex)) {
    printk(KERN_ALERT "fibdrv is in use");
    return -EBUSY;
}
```
在 `fib_release` 時則會釋放：
```c
mutex_unlock(&fib_mutex);
```
#### 撰寫 POSIX Thread 測試程式碼
```c
// client.c
#define THREAD_COUNT 2
void run(){
    char buf[1000];
    int offset = 100;
    struct timespec t1, t2;
    FILE *data = fopen("perf/time.txt", "w");

    int fd = open(FIB_DEV, O_RDWR);

    if (fd < 0) {
        perror("Failed to open character device");
        exit(1);
    }

    for (int i = 0; i <= offset; i++) {
        lseek(fd, i, SEEK_SET);
        int len = read(fd, buf, 1);
        unsigned int *tmp = (unsigned int *) buf;
        char *s = bn_to_string_user(tmp, len);
        printf("Reading from " FIB_DEV
               " at offset %d, returned the sequence "
               "%s\n",
               i, s);
        fprintf(data, "%d %lld %ld %lld\n", i);
    }

    return;
}
int main(){
    pthread_t pt[THREAD_COUNT];
    for (int i = 0; i < THREAD_COUNT; i++) {
        pthread_create(&pt[i], NULL, run, NULL);
    }

    for (int i = 0; i < THREAD_COUNT; i++) {
        pthread_join(pt[i], NULL);
    }
    return 0;
}
```
```shell
...
Reading from /dev/fibonacci at offset 100, returned the sequence 354224848179261915075
Reading from /dev/fibonacci at offset 97, returned the sequence 83621143489848422977
Reading from /dev/fibonacci at offset 98, returned the sequence 135301852344706746049
Reading from /dev/fibonacci at offset 99, returned the sequence 218922995834555169026
Reading from /dev/fibonacci at offset 100, returned the sequence 354224848179261915075
```
可以看到雖然順序不一定，結果則是對的。