# 2021q1 Homework3 (fibdrv)
contributed by < `RZHuangJeff` >

###### tags: `linux2021`

## Environment Setup
The environment is set up to reliable for running our experiment. The `linux-headers` package is installed by running following command:

$ sudo apt install linux-headers-`uname -r`

This package provides header files that defines linux kernal APIs.
And to minimize the influence from scheduler and other processes while running experiments, two of eight CPU cores on my computer is isolated by setting up boot argument `isolcpus`, following are boot arguments of my system:

$ cat /proc/cmdline 
BOOT_IMAGE=/boot/vmlinuz-5.8.0-45-generic root=UUID=4f90c489-bb9c-4dd1-aafe-e6038bb0d51a ro isolcpus=6-7 quiet splash vt.handoff=7

And the experiment programs will run on these isolated CPU cores.

Since my CPU is manufactured by Intel, to reduce statistical error, turbo mode of my CPU is baned by following command:

$ sudo sh -c "echo 1 > /sys/devices/cpu/intel_pstate/no_turbo"

To measure the improvement of performace between various calculating methods, a simple timer proxy is introduced that the time token for last request to calculate the Fibonacci sequence is reserved and a userspace program could ask for it via making a write request.

static long long fib_time_proxy(long long k)
{
    kt = ktime_get();
    long long res = fib_sequence(k);
    kt = ktime_sub(ktime_get(), kt);

    return res;
}

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

## Fibonacci Sequence
Fibonacci sequence is a sequence of numbers that following recursive definition holds:
$$
F_0 = 0 \\
F_1 = F_2 = 1 \\
F_{n + 2} = F_{n + 1} + F_{n}
$$
At the first sight, since it is a clear recursive definition, it can be converted to corresponding C program easily:

static long long fib_sequence_rec(long long k)
{
    if (k == 0)
        return 0LL;

    if (k == 1 || k == 2)
        return 1LL;

    return fib_sequence_rec(k - 1) + fib_sequence_rec(k - 2);
}