# 2019q1 Homework2 (fibdrv)
contributed by < `JulianATA` >
### Reviewed by `jeffcarl67`
* 在 `mutex` 的實驗中, 可以加入一份使用 mutex 相關操作的程式碼, 實際比較在有無 mutex 的情況下程式的行為有何不同
## Environmet
```bash
$ 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`:
```clike
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):
```clike
#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):
``` clike
#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:
```clike
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`
```clike
#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;
}
```
``` bash
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!
```clike
#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`
Sign in with Wallet
Connect another wallet