# 2019q1 Homework2 (fibdrv)
contributed by < `JulianATA` >

### Reviewed by `jeffcarl67`
* 在 `mutex` 的實驗中, 可以加入一份使用 mutex 相關操作的程式碼, 實際比較在有無 mutex 的情況下程式的行為有何不同

## Environmet

$ uname -a
Linux 4.15.0-20-generic
$ gcc -v
gcc (Ubuntu 7.3.0-27ubuntu1~18.04) 7.3.0

## 自我檢查清單
### 檔案 fibdrv.c 裡頭的 MODULE_LICENSE, MODULE_AUTHOR, MODULE_DESCRIPTION, MODULE_VERSION 等巨集做了什麼事，可以讓核心知曉呢？ insmod 這命令背後，對應 Linux 核心內部有什麼操作呢？請舉出相關 Linux 核心原始碼並解讀
#### `MODULE_LICENSE`
In `fibdrv.c`:

MODULE_LICENSE("Dual MIT/GPL");
MODULE_AUTHOR("National Cheng Kung University, Taiwan");
MODULE_DESCRIPTION("Fibonacci engine driver");
MODULE_VERSION("0.1");

We used these macros to define our modules.
Take a look at `linux/module.h`.(use License as example):

#define MODULE_LICENSE(_license) MODULE_INFO(license, _license)
.
.
.
#define MODULE_INFO(tag, info) __MODULE_INFO(tag, tag, info)

Found `__MODULE_INFO` in [`linux/moduleparam.h`](https://elixir.bootlin.com/linux/v4.18/source/include/linux/moduleparam.h):

#ifdef MODULE
#define __MODULE_INFO(tag, name, info)					  \
static const char __UNIQUE_ID(name)[]					  \
  __used __attribute__((section(".modinfo"), unused, aligned(1)))	  \
  = __stringify(tag) "=" info
#else  /* !MODULE */
/* This struct is here for syntactic coherency, it is not used */
#define __MODULE_INFO(tag, name, info)					  \
  struct __UNIQUE_ID(name) {}
#endif

It'll like config the Module information if module has been defined.
#### `insmod`
It's a program with following steps
1. Call `init_module()` to tell kernel that a module is try to be load in the kernel and transfer the control to the kernel.
2. Run `sys_init_module()`, which verifies if the user who trying to load the module is allowed or not. If allowed do step3.
3. Call `load_module` function, which assigns temporary memory and duplicate the`elf` module from user space to kernel using `copy_from_user()`. Then check if the ELF file is proper or not. Copy users arguments to the kernel. Update the state of module to `MODULE_STATE_COMING`. Then returns a reference to the kernel module!
4. The reference returned will be added to a `doubly linked list` for modules loaded.
5. Module stat update to `MODULE_STATE_LIVE`.
### 當我們透過 insmod 去載入一個核心模組時，為何 module_init 所設定的函式得以執行呢？Linux 核心做了什麼事呢？
Covered in last question.
need to paste source code(todo).
### 試著執行 $ readelf -a fibdrv.ko, 觀察裡頭的資訊和原始程式碼及 modinfo 的關聯，搭配上述提問，解釋像 fibdrv.ko 這樣的 ELF 執行檔案是如何「植入」到 Linux 核心

### 這個 fibdrv 名稱取自 Fibonacci driver 的簡稱，儘管在這裡顯然是為了展示和教學用途而存在，但針對若干關鍵的應用場景，特別去撰寫 Linux 核心模組，仍有其意義，請找出 Linux 核心的案例並解讀。提示: 可參閱 Random numbers from CPU execution time jitter

### 查閱 ktime 相關的 API，並找出使用案例 (需要有核心模組和簡化的程式碼來解說)
In my fibdrv.c:

static unsigned long long fib_sequence(long long k)
{
    ktime_t t = ktime_get();
    /* FIXME: use clz/ctz and fast algorithms to speed up */
    unsigned long long f[k + 2];

    f[0] = 0;
    f[1] = 1;

    for (int i = 2; i <= k; i++) {
        f[i] = f[i - 1] + f[i - 2];
    }
    runtime = ktime_sub(ktime_get(), t);
    printk("iteration %llu runtime = %lldns\n", k, runtime);
    return f[k];
}

Use my own code as reference!
The first variable `t` store the starting time of the calculation.
Then after the calculation, use `ktime_sub` to get the differnce of the ending time and the starting time, whic can be represent as `runtime`!
### clock_gettime 和 High Resolution Timers (HRT) 的關聯為何？請參閱 POSIX 文件並搭配程式碼解說
In the manpage of `clock_gettime`, we find `clock_getres()`:

The function clock_getres() finds the resolution (precision) of the
       specified clock clk_id, and, if res is non-NULL, stores it in the
       struct timespec pointed to by res.  The resolution of clocks depends
       on the implementation and cannot be configured by a particular
       process.  If the time value pointed to by the argument tp of
       clock_settime() is not a multiple of res, then it is truncated to a
       multiple of res.

The word `Resolution` is to describe the `precision` of clock.
I wrote a simple program to get resolution of `CLOCK_MONOTONIC`

#include <time.h>
#include <stdio.h>

int main()
{
  struct timespec t;
  clock_getres(CLOCK_MONOTONIC, &t);
  printf("resolution: %ld\n", t.tv_nsec);
  return 0;
}

resolution: 1000#The unit of the time is nano sec.

I found the rationale in [linux.org](https://elinux.org/High_Resolution_Timers)
>Currently, timers in Linux are only supported at a resolution of 1 jiffy. The length of a jiffy is dependent on the value of HZ in the Linux kernel, and is 1 millisecond on i386 and some other platforms, and 10 milliseconds on most embedded platforms.

>Higher resolution timers are needed to allow the system to wake up and process data at more accurate intervals.
### fibdrv 如何透過 Linux Virtual File System 介面，讓計算出來的 Fibonacci 數列得以讓 userspace (使用者層級) 程式 (本例就是 client.c 程式) 得以存取呢？解釋原理，並撰寫或找出相似的 Linux 核心模組範例

### 注意到 fibdrv.c 存在著 DEFINE_MUTEX, mutex_trylock, mutex_init, mutex_unlock, mutex_destroy 等字樣，什麼場景中會需要呢？撰寫多執行緒的 userspace 程式來測試，觀察 Linux 核心模組若沒用到 mutex，到底會發生什麼問題

Mutex lock here is for protection of critical section!

#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>
void thread1(void)
{
    for(int i=0;i<5;i++)
        printf("This is a pthread1.\n");
}
void thread2(void)
{
    for(int i=0;i<5;i++)
        printf("This is a pthread2.\n");
}
int main(void)
{
    pthread_t t1, t2;
    pthread_create(&t1,NULL, (void *) thread1,NULL);
    pthread_create(&t2,NULL, (void *) thread2,NULL);
    for(int i=0;i<5;i++)
        printf("This is the main process.\n");
    pthread_join(t1,NULL);
    pthread_join(t2,NULL);
    return (0);
}

Expected outcome:

This is a pthread1.
This is a pthread1.
This is a pthread1.
This is a pthread1.
This is a pthread1.
This is a pthread2.
This is a pthread2.
This is a pthread2.
This is a pthread2.
This is a pthread2.
This is the main process.
This is the main process.
This is the main process.
This is the main process.
This is the main process.

What I got:

This is the main process.
This is the main process.
This is a pthread1.
This is a pthread1.
This is a pthread1.
This is a pthread1.
This is the main process.
This is the main process.
This is a pthread1.
This is a pthread2.
This is a pthread2.
This is a pthread2.
This is a pthread2.
This is a pthread2.
This is the main process.

### 許多現代處理器提供了 clz / ctz 一類的指令，你知道如何透過演算法的調整，去加速 費氏數列 運算嗎？請列出關鍵程式碼並解說

## Original Fibdrv time testing(100 Repeat)
ktime_t vs get_time

ktime_t

## dynamic programing(100 repeat)


## with clz cts(todo)

###### tags: `Cprogramming` `LinuxKernel`