# 2021q1 Homework3 (fibdrv)
Contributed by < `fdfdd12345628` >

> [作業需求](https://hackmd.io/@sysprog/linux2021-fibdrv)
> [GitHub](https://github.com/fdfdd12345628/fibdrv)

## Fibonacci 數列
這裡使用 [HUGE-Fibonacci](https://github.com/wolfofalgstreet/HUGE-Fibonacci) ，因為是 MIT licence 所以就直接用了。

它的原理是建構一個 struct 來儲存大數字

// Fibonacci.h
struct HugeInteger
{
	// a dynamically allocated array to hold the digits of a huge integer
	int *digits;

	// the number of digits in the huge integer (approx. equal to array length)
	int length;
}

並且在每次加法時配置更多記憶體

// fibonacci.c
if(isPlenLarger(p,q) == 1)
    hugeAddition->digits = calloc(p->length + 7, sizeof(int));
else hugeAddition->digits = calloc(q->length + 7, sizeof(int));

並且加法時計算加了幾位數，最後才儲存 length

// fibonacci.c
hugeAddition->length = size;

由於這個程式是使用 int array 當儲存數字的地方，但因為單個數字範圍只有$0 - 9$，所以可以只用 byte array 就好了。

最後把 `malloc` 改成 `kmalloc` ， `calloc` 改成 `kcalloc` ， `free` 改成 `kfree` 。並且將 header 全部整合進一個檔案，就可以編譯並且執行了。

## 效能檢定
測試電腦環境如下
CPU: kvm Genuine Intel(R) CPU x1
RAM: 981MB
測試電腦在伺服器上，可以將筆電相關的影響去除

首先在 `fibdrv.c` 加入以下程式碼來計算時間

// fibdrv.c
static ktime_t kt;

static HugeInteger *fib_time_proxy(long long k)
{
    kt = ktime_get();
    HugeInteger *result = fib_sequence(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)
{
    HugeInteger *result = fib_time_proxy(*offset);
    copy_to_user(buf, result->digits, sizeof(int) * result->length);
    return result->length;
}


static ssize_t fib_write(struct file *file,
                         const char *buf,
                         size_t size,
                         loff_t *offset)
{
    return ktime_to_ns(kt);
}

這樣可以在 `fib_write` 時讀取到上次 `fib_read` 的時間。

並且製作一個新的 client 來讀取 kernel 耗時與計算 user 耗時，取樣 100 次

for (int k = 0; k < 100; k++) {
    long long sz;
    sz = write(fd, write_buf, strlen(write_buf));
    long long kernel_time = sz;
    for (int i = 0; i <= offset; i++) {
        // printf("Writing to " FIB_DEV ", returned the sequence %lld\n",sz);
        lseek(fd, i, SEEK_SET);
        struct timespec start, end;
        double time_used;

            // 計算開始時間
        clock_gettime(CLOCK_MONOTONIC, &start);

        sz = read(fd, buf, 100 * sizeof(int));
        clock_gettime(CLOCK_MONOTONIC, &end);
        // printf("Reading from " FIB_DEV " at offset %d, returned the sequence ", i);
        for (int j = sz - 1; j >= 0; j--) {
            printf("%d", buf[j]);
        }
        printf(".\n");
        struct timespec temp = diff(start, end);
        time_used = (double) temp.tv_nsec;
        sz = write(fd, write_buf, strlen(write_buf));
        kernel_time = sz;

        printf("Num: %d, kernel: %lld, user: %lf, diff: %lf\n", i, kernel_time, time_used, time_used - kernel_time);
        memset(buf, 0, sizeof(int) * 100);
    }
}

輸出如下

...
218922995834555169026.
Num: 99, kernel: 21413, user: 24785.000000, diff: 3372.000000
354224848179261915075.
Num: 100, kernel: 21839, user: 25191.000000, diff: 3352.000000

最後將輸出資料用 python 處理

# script/statistic.py
#!/usr/bin/env python3
import pprint
import numpy as np

expect = [0, 1]
result = []
result_split = []
dics = []

for i in range(2, 101):
    expect.append(expect[i - 1] + expect[i - 2])
with open('out', 'r') as f:
    tmp = f.readline()
    while (tmp):
        result.append(tmp)
        tmp = f.readline()
    f.close()
for r in result:
    if (r.find('Num') != -1):
        
        result_split.append(r.split(' '))
        num=int(result_split[-1][1][:-1])
        kernel=int((result_split[-1][3][:-1]))
        user=int(float(result_split[-1][5][:-1]))
        diff=int(float(result_split[-1][7][:-1]))
        if num==0:
            dics.append([])

        dics[-1].append((num, kernel, user, diff))

# pprint.pprint(dics)

mean=[]

data=np.array(dics)

print(data[:, 1:2,:])

def outlier_filter(datas, threshold = 2):
    datas = np.array(datas)
    z = np.abs((datas - datas.mean()) / datas.std())
    return datas[z < threshold]

def data_processing(data_set, n):
    catgories = data_set[0].shape[0]
    samples = data_set[0].shape[1]
    final = np.zeros((catgories, samples))

    for c in range(catgories):        
        for s in range(samples):
            final[c][s] =                                                    \
                outlier_filter([data_set[i][c][s] for i in range(n)]).mean()
    return final

for i in range(101):
    kernel_mean = outlier_filter(data[:, i:i+1, 1]).mean()
    user_mean = outlier_filter(data[:, i:i+1, 2]).mean()
    diff_mean = outlier_filter(data[:, i:i+1, 3]).mean()
    mean.append((i, kernel_mean, user_mean, diff_mean))

print("result:")
pprint.pprint(mean)

import csv

with open('output.csv', 'w+') as fp:
    writer=csv.writer(fp)
    writer.writerows(mean)

最後用 gnuplot 來繪製 `output.csv` 如下

可以看出 kernel 到 user 有一定的 overhead

## TODO
1. 增進大數計算