---
tags: linux2022
---

# 2022q1 Homework3 (fibdrv)
contributed by < `linchi1997yeh` >

## 自我檢查清單

- [x] 研讀上述 ==Linux 效能分析的提示== 描述，在自己的實體電腦運作 GNU/Linux，做好必要的設定和準備工作 $\to$ 從中也該理解為何不希望在虛擬機器中進行實驗;
- [x] 研讀上述費氏數列相關材料 (包含論文)，摘錄關鍵手法，並思考 [clz / ctz](https://en.wikipedia.org/wiki/Find_first_set) 一類的指令對 Fibonacci 數運算的幫助。請列出關鍵程式碼並解說
- [x] 複習 C 語言 [數值系統](https://hackmd.io/@sysprog/c-numerics) 和 [bitwise operation](https://hackmd.io/@sysprog/c-bitwise)，思考 Fibonacci 數快速計算演算法的實作中如何減少乘法運算的成本;
- [x] 研讀 [KYG-yaya573142 的報告](https://hackmd.io/@KYWeng/rkGdultSU)，指出針對大數運算，有哪些加速運算和縮減記憶體操作成本的舉措？
- [ ] `lsmod` 的輸出結果有一欄名為 `Used by`，這是 "each module's use count and a list of referring modules"，但如何實作出來呢？模組間的相依性和實際使用次數 ([reference counting](https://en.wikipedia.org/wiki/Reference_counting)) 在 Linux 核心如何追蹤呢？
> 搭配閱讀 [The Linux driver implementer’s API guide » Driver Basics](https://www.kernel.org/doc/html/latest/driver-api/basics.html)
- [ ] 注意到 `fibdrv.c` 存在著 `DEFINE_MUTEX`, `mutex_trylock`, `mutex_init`, `mutex_unlock`, `mutex_destroy` 等字樣，什麼場景中會需要呢？撰寫多執行緒的 userspace 程式來測試，觀察 Linux 核心模組若沒用到 mutex，到底會發生什麼問題。嘗試撰寫使用 [POSIX Thread](https://en.wikipedia.org/wiki/POSIX_Threads) 的程式碼來確認。
- Dynamically allocate mememory (calculate digits needed for the n number of fibonacci digits output needed)
## Reference Documents
* [Introduction to Linux kernel driver programming](https://events.linuxfoundation.org/wp-content/uploads/2017/12/Introduction-to-Linux-Kernel-Driver-Programming-Michael-Opdenacker-Bootlin-.pdf)
* [Part 1: Introduction](http://derekmolloy.ie/writing-a-linux-kernel-module-part-1-introduction/)
* [Part 2: A Character Device](http://derekmolloy.ie/writing-a-linux-kernel-module-part-2-a-character-device/)
* [Linux 核心設計: 檔案系統概念及實作手法](https://hackmd.io/@sysprog/linux-file-system?type=view#Linux-%E6%A0%B8%E5%BF%83%E8%A8%AD%E8%A8%88-%E6%AA%94%E6%A1%88%E7%B3%BB%E7%B5%B1%E6%A6%82%E5%BF%B5%E5%8F%8A%E5%AF%A6%E4%BD%9C%E6%89%8B%E6%B3%95)
## Background
- [File descriptor (FD)](https://www.computerhope.com/jargon/f/file-descriptor.htm)
- [Open](https://man7.org/linux/man-pages/man2/open.2.html)
- [mmap](https://man7.org/linux/man-pages/man2/mmap.2.html) (CSAPP ch9)
- mmap function asks the kernel to create a new virtual memory area, to map a contigous(consecutive) object chunk specified by the fd to the newly created virtual memory area.
- After the mmap() call has returned, the file descriptor, fd, can be closed immediately without invalidating the mapping.
- prot argument containes the memory protection specificatoins
- Why do we need device drivers?
- Device drivers acts as a crucial component to facilitate communication between any hardware device and the operating system
- What is a character device?
- Just as a driver a character device has the property of reading and writing the data in a character-by-character stream.
- In this assignment although we have not inserted any additional device, we simulate to stablish communication between components of current device with the user.
- Lseek functionality in `client.c`

lseek(fd, i, SEEK_SET);
/*
 * reposition the read/write file offset
 * the offset is set to new_pos = 0 + i 
 * 0 is to represent the start of the file
 */

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;
}

- files that doesn't support seek?
> - terminals does not support seeking, it always [read](https://linux.die.net/man/3/pread) from the current posistion. The value of a file offset associated with such file is undefined

---

:::info
note: all experiment below is average over 5000 iteration and values outside 2 sigma(95%) are discarded.
:::
## Fibonacci run time

### Kernel vs user time

Here we can say that actual time consumed is:
$TimeConsumed =KernelTime+SystemCalls$

Use [clock_gettime](https://linux.die.net/man/2/clock_gettime) to measure the time consumed on the user side.

#include <time.h>

struct timespec t_start, t_end;
clock_gettime(CLOCK_REALTIME, &t_start);
sz = write(fd, write_buf, 0);
clock_gettime(CLOCK_REALTIME, &t_end);
long long dif = t_end.tv_nsec - t_start.tv_nsec;

Use [ktime](https://github.com/spotify/linux/blob/master/include/linux/ktime.h) to calculate execution time on kernel mode.

static ssize_t fib_write(struct file *file,
                         const char *buf,
                         size_t mode,
                         loff_t *offset){
    ktime_t kt;
    kt = ktime_get();
    fib_sequence(*offset);
    kt = ktime_sub(ktime_get(), kt);
}


System call time is unstable.Kernel space computational time is much stable

:::info
Encounter an error when using sqrt from math.h
Error message: undefined reference to `sqrt' => must add a -lm flag when compiling the c file
ref: [Why am I getting "undefined reference to sqrt" error even though I include math.h header?](https://stackoverflow.com/questions/10409032/why-am-i-getting-undefined-reference-to-sqrt-error-even-though-i-include-math)
:::

### Fibonacci Sequence vs Fibonacci Fast Doubling


We can use the formula for fibonacci 2n and fibonacci 2n+1 to speed up the iterative method.

static long long fib_fast_dob(long long n)
{
    if (n < 2) { /* F(0) = 0, F(1) = 1 */
        return n;
    }
    long long f[2];
    unsigned int ndigit = 32 - __builtin_clz(n); /* number of digit in n */
    f[0] = 0;                                    /* F(k) */
    f[1] = 1;                                    /* F(k+1) */

    for (unsigned int i = 1U << (ndigit - 1); i;
         i >>= 1) { /* walk through the digit of n */
        long long k1 =
            f[0] * (f[1] * 2 - f[0]); /* F(2k) = F(k) * [ 2 * F(k+1) – F(k) ] */
        long long k2 =
            f[0] * f[0] + f[1] * f[1]; /* F(2k+1) = F(k)^2 + F(k+1)^2 */
        if (n & i) {                   /* current binary digit == 1 */
            f[0] = k2;                 /* F(n) = F(2k+1) */
            f[1] = k1 + k2; /* F(n+1) = F(2k+2) =  F(2k) +  F(2k+1) */
        } else {
            f[0] = k1; /* F(n) = F(2k) */
            f[1] = k2; /* F(n+1) = F(2k+1) */
        }
    }
    // printk("%lld", f[0]);
    return f[0];
}

Here we observe that the iterative approach cost increases linearly and the fast doubling approach seems to remain constant when the Fibonacci number is under 100.
## Big Number implementation
### Runtime comparison Iterative vs fast-doubling
Big num implementation reference from [arthurchang09](https://hackmd.io/@arthur-chang/linux2022-fibdrv#%E8%A8%88%E7%AE%97-F93-%E5%8C%85%E5%90%AB-%E4%B9%8B%E5%BE%8C%E7%9A%84-Fibonacci-%E6%95%B8)

Experiments found that the big num iterative is much faster than fast doubling, here we can assume that the multiplication cost on big num is much higher than addition.


Further obseving values larger than 1000, time cost from the iterative method goes up linearly almost surpassing the fast-doubling at Fib(5000). To be able to compute up to Fib(5000), we have to allocate a larger buffer size and increase the bignum.

### Dynamic Array Length
The original implementation:

#define LENGTH 100
typedef struct bn {
    unsigned int num[LENGTH];
} bn;

In order to compute large fibonacci number the Length of the array must be set to a large number.
We want the integer array to be dynamic.
Referring to [KYG-yaya573142](https://hackmd.io/@KYWeng/rkGdultSU#%E5%A4%A7%E6%95%B8%E9%81%8B%E7%AE%97) implementation we can change the bignum struct to be:

typedef struct bn {
    unsigned int *number;
    unsigned int size;
    int sign;
} bn;

// init
    bn *fib;
    fib = bn_alloc(0);

This implementation initializes a bignum with size 0 and when operation exceeds its representation limit it reallocates larger size for the number to be represented.

Here we can see improvement on speed on smaller fibonacci number where the array size is small. Also the computation time between iterative method and Fast doubling is almost the same, we can accelerate fast doubling by improving big num multiplication function.

### Fixed buffer size problem
The original implementation we initialized a fixed size buffer. It leads to various problem:
- Buffer size is too small store the fibonacci number or too big to be allocated
- If allocated a big chunk of memory and wasted since the fibonacci number doesn't requires it.

#define LENGTH 100
#define BUFFSIZE 8 * sizeof(int) * LENGTH / 3 + 2

int main()
{
    char buf[BUFFSIZE];
    int offset = 100;
    ...

We can then dynamically allocate the size we need to store the fibonacci number, but that requires knowing how many digits we need before.

#### How many digits does nth fibonacci number have?
Here first we need to know that we can calculate any fibonacci number using Binet's Formula for the nth Fibonacci number
$$Fn= \frac{(\phi^n)-(1-\phi)^n}{\sqrt5}$$ $$\phi = \frac{1+\sqrt5}{2} (golden \ ratio)$$

An aproximation to the formula above would be:
$$Fn= \frac{\phi^n}{\sqrt5} \ (since\ (1-\phi)^n\ is\ very\ small\ for\ large\ n)$$

Knowing the aproximation we can calculate the number of digits with the Log base 10 of the aproximation. That would be:
$$ Digits = \log_{10}(\frac{\phi^n}{\sqrt5})$$
$$ Digits = n\log_{10}\phi - (\frac{\log_{10}5}{2})$$

For implementation in C:
Log(phi) and Log5 can be defined as constanst for easier implementation.

#define BUFFSIZE 8 * sizeof(int) * LENGTH / 3 + 2
#define LOGPHI 0.20898764025
#define LOGSQRT5 0.34948500216
int main()
{
    int offset = 100; /* TODO: try test something bigger than the limit */
    int fd = open(FIB_DEV, O_RDWR);
    if (fd < 0) {
        perror("Failed to open character device");
        exit(1);
    }
    float digits;
    int size;
    for (int i = 0; i <= offset; i++) {
        // calculate how many digits are needed for fib(i)
        // digits needed for fib(n) = n*LOG(Phi) - (LOG √5)
        digits = i * LOGPHI - LOGSQRT5;
        float buf_size = floor(digits / 9);
        size = (int) buf_size;
        char *buf = malloc(sizeof(char) * (BUFFSIZE * size));
        lseek(fd, i, SEEK_SET);
        long long time1 = read(fd, buf, 0);
        long long time2 = read(fd, buf, 1);
        printf("%d %lld %s\n", i, time1, buf); 
        free(buf);
    }

Now we can pass in the required size used by the fibonacci number so when computing the big num we don't need to be reallocating memory in kernel space.
Simply by initializing the required space on the first call:

static ssize_t fib_read(struct file *file,
                        char *buf,
                        size_t size,
                        loff_t *offset)
{
    bn *fib;    
    // fib = bn_alloc(0); Not preallocating
    if (size < 1) {
        fib = bn_alloc(0);
    } else {
        fib = bn_alloc(size);
    }
    ktime_t kt;

Here size is the array size calculated at client.c
Before precalculating the size.



Seems like the time required is almost the same, maybe we should test for larger numbers where reallocation is needed multiple times.


The results shows almost no improvement trying to decrease the memory reallocation process since memory reallocation only happens only 116 times (without knowing size) on fib(5000), memoryy reallocation ins't the bottle neck on this computational heavy fibonacci task so improvement is barely noticeble.
<!--  -->