# 2019q1 Homework2 (fibdrv)
contributed by < `zodf0055980` >
###### tags: `Linux 核心設計`
## Reviewed by `bauuuu1021`
* 建議一次 commit 著重一個主要修改，例如 [06f574f](https://github.com/zodf0055980/fibdrv/commit/06f574f2da2069845d6bdc838d0d9a3ec7fc6342) 可以拆成兩次，分別修改 client.c 及 showtime.gp；或在 commit message 中更清楚提及 ==以 gnuplot 展示時間變化==
* 共筆中有許多實驗都有製圖，但在 GitHub 中只有看到其中一個圖的 script。建議將其他的 script 也放到 GitHub 中，並在 Makefile 中加入對應操作，方便他人重現實驗或提出改進
# 自我檢查清單
- [ ] 檔案 `fibdrv.c` 裡頭的 `MODULE_LICENSE`, `MODULE_AUTHOR`, `MODULE_DESCRIPTION`, `MODULE_VERSION` 等巨集做了什麼事，可以讓核心知曉呢？ `insmod` 這命令背後，對應 Linux 核心內部有什麼操作呢？請舉出相關 Linux 核心原始碼並解讀
在 [linux/module.h](https://github.com/torvalds/linux/blob/master/include/linux/module.h)中可以看到:
```clike
#define MODULE_LICENSE(_license) MODULE_INFO(license, _license)
#define MODULE_AUTHOR(_author) MODULE_INFO(author, _author)
#define MODULE_DESCRIPTION(_description) MODULE_INFO(description, _description)
#define MODULE_VERSION(_version) MODULE_INFO(version, _version)
```
都可以發現這些都對應到 MODULE_INFO()，如果在同一個檔案下搜尋能發現 MODULE_INFO() 對應到 `__MODULE_INFO()`
```clike
#define MODULE_INFO(tag, info) __MODULE_INFO(tag, tag, info)
```
再到 [linux/moduleparam.h](https://github.com/torvalds/linux/blob/master/include/linux/moduleparam.h)可以找到
```clike
#define __MODULE_INFO(tag, name, info) \
static const char __UNIQUE_ID(name)[] \
__used __attribute__((section(".modinfo"), unused, aligned(1))) \
= __stringify(tag) "=" info
```
再依序把上面給拆解，發現在 [linux/moduleparam.h](https://github.com/torvalds/linux/blob/master/include/linux/moduleparam.h) 有這段
```clike
#include <linux/kernel.h>
```
再到 linux/kernel.h 中發現有
```clike
#include <linux/compiler.h>
```
因此至 [compiler.h](https://github.com/torvalds/linux/blob/bb617b9b4519b0cef939c9c8e9c41470749f0d51/include/linux/compiler.h) 中可以發現
```clike
# define __UNIQUE_ID(prefix) __PASTE(__PASTE(__UNIQUE_ID_, prefix), __LINE__)
```
而在 [linux/compiler_types.h](https://github.com/torvalds/linux/blob/9105b8aa50c182371533fc97db64fc8f26f051b3/include/linux/compiler_types.h) 中可以發現
```clike
#define ___PASTE(a,b) a##b
#define __PASTE(a,b) ___PASTE(a,b)
```
而在 macro 中 [##](https://www.cprogramming.com/tutorial/cpreprocessor.html)為 Pasting Tokens，可把兩參數或文字做串連。
因此 `__UNIQUE_ID(prefix)` 可視為 `__UNIQUE_ID_ + prefix + __LINE__` ，去產生一個獨立名稱的變數。
而 [__attribute__](https://gcc.gnu.org/onlinedocs/gcc-3.2/gcc/Variable-Attributes.html)可以發現 `__attribute__((section(".modinfo"), unused, aligned(1)))`的意涵為把變數放到 .modinfo 中，且變數可能不會備使用，使 GCC 不會發出警告，並對變數最小的對齊為1 byte。
而 `__stringify` 定義在 [linux/stringify.h](https://github.com/torvalds/linux/blob/6f0d349d922ba44e4348a17a78ea51b7135965b1/tools/include/linux/stringify.h)中
```clike
#define __stringify_1(x...) #x
#define __stringify(x...) __stringify_1(x)
```
因此會以 static const char 的特殊名稱的變數儲存 "license = Dual MIT/GPL" 、 "author = National Cheng Kung University, Taiwan" 、"description = Fibonacci engine driver" 、 "version = 0.1"，儲存在 .modinfo 中。
- [ ] 當我們透過 insmod 去載入一個核心模組時，為何 module_init 所設定的函式得以執行呢？Linux 核心做了什麼事呢？
在 inux/module.h 中可以找到
```clike
#define module_init(x) __initcall(x);
```
再到 [linux/init.h](https://github.com/torvalds/linux/blob/f346b0becb1bc62e45495f9cdbae3eef35d0b635/include/linux/init.h) 可以找到
```clike
#define __initcall(fn) device_initcall(fn)
#define device_initcall(fn) __define_initcall(fn, 6)
#define __define_initcall(fn, id) ___define_initcall(fn, id, .initcall##id)
```
```clike
#ifdef CONFIG_HAVE_ARCH_PREL32_RELOCATIONS
#define ___define_initcall(fn, id, __sec) \
__ADDRESSABLE(fn) \
asm(".section \"" #__sec ".init\", \"a\" \n" \
"__initcall_" #fn #id ": \n" \
".long " #fn " - . \n" \
".previous \n");
#else
#define ___define_initcall(fn, id, __sec) \
static initcall_t __initcall_##fn##id __used \
__attribute__((__section__(#__sec ".init"))) = fn;
#endif
```
因此如果傳入的變數為 X ，會在 會建立 type 為 initcall_t 的變數`__initcall_X6 __used`，並儲存設定檔在 .initcall6.init 中。
而為什麼是 6 這個數字，可以在 init.h 中找到
```clike
#define pure_initcall(fn) __define_initcall(fn, 0)
#define core_initcall(fn) __define_initcall(fn, 1)
#define core_initcall_sync(fn) __define_initcall(fn, 1s)
#define postcore_initcall(fn) __define_initcall(fn, 2)
#define postcore_initcall_sync(fn) __define_initcall(fn, 2s)
#define arch_initcall(fn) __define_initcall(fn, 3)
#define arch_initcall_sync(fn) __define_initcall(fn, 3s)
#define subsys_initcall(fn) __define_initcall(fn, 4)
#define subsys_initcall_sync(fn) __define_initcall(fn, 4s)
#define fs_initcall(fn) __define_initcall(fn, 5)
#define fs_initcall_sync(fn) __define_initcall(fn, 5s)
#define rootfs_initcall(fn) __define_initcall(fn, rootfs)
#define device_initcall(fn) __define_initcall(fn, 6)
#define device_initcall_sync(fn) __define_initcall(fn, 6s)
#define late_initcall(fn) __define_initcall(fn, 7)
#define late_initcall_sync(fn) __define_initcall(fn, 7s)
```
而其中後方的數字為其優先權。 在 init/main.c中可以看到
```clike
static void __init do_initcalls(void)
{
int level;
for (level = 0; level < ARRAY_SIZE(initcall_levels) - 1; level++)
do_initcall_level(level);
}
```
在 kernel 啟動過程中，會呼叫 do_initcalls 呼叫我們透過 xxx_initcall() 所註冊的函式。所以我們用 module_init() 註冊函式的會依其優先權依序備執行。而由 for 迴圈可知0的優先權最高，7 的優先權最小。
- [ ] 試著執行 $ readelf -a fibdrv.ko, 觀察裡頭的資訊和原始程式碼及 modinfo 的關聯，搭配上述提問，解釋像 fibdrv.ko 這樣的 ELF 執行檔案是如何「植入」到 Linux 核心
ELF 和其他檔案資料是由一個一個 bit 組成的，然而因為它內部依循著一定的結構，[如下圖](https://en.wikipedia.org/wiki/Executable_and_Linkable_Format)：
所以我們能用 readelf 這個工具去解讀 ELF 檔案，而由於原本電腦預設的語系，所以顯示出來有些資訊是中文，因此可以改成下方的指令使中文資訊換成英文。
```
$ LC_ALL=C readelf -a fibdrv.ko
```
readelf 去解讀 elf 檔的最前 16 位元，也就是 magic numbe，去確定此檔案是 elf 檔和知道有關這檔案的資訊。而有關 magic numbe 和 elf 檔案的資訊可以在 [linux/elf.h](https://github.com/torvalds/linux/blob/master/include/uapi/linux/elf.h) 查詢的到。
```clike
typedef struct elf64_hdr {
unsigned char e_ident[EI_NIDENT]; /* ELF "magic number" */
Elf64_Half e_type;
Elf64_Half e_machine;
Elf64_Word e_version;
Elf64_Addr e_entry; /* Entry point virtual address */
Elf64_Off e_phoff; /* Program header table file offset */
Elf64_Off e_shoff; /* Section header table file offset */
Elf64_Word e_flags;
Elf64_Half e_ehsize;
Elf64_Half e_phentsize;
Elf64_Half e_phnum;
Elf64_Half e_shentsize;
Elf64_Half e_shnum;
Elf64_Half e_shstrndx;
} Elf64_Ehdr;
```
可以看到 magic number 分別代表不同的資訊，像是檔案的儲存方式是 2's complement, little endian 等等，而 readelf 可以去解讀並顯示資訊內容。
而由 magic numbe 可知 Elf64_Off e_shoff 的值，因此能利用 e_shoff 找到 Section Headers 的位置， readelf 去讀取顯示 elf Section 的資訊。
而由於 MODULE_VERSION 等巨集是對 .modinfo 做寫入，因此能發現有出現 [12] .modinfo 的資訊。而我們可以利用另一個工具 objdump 去顯示 Section 的資訊。
```
$ sudo objdump --section=.modinfo -s fibdrv.ko
```
```
Contents of section .modinfo:
0000 76657273 696f6e3d 302e3100 64657363 version=0.1.desc
0010 72697074 696f6e3d 4669626f 6e616363 ription=Fibonacc
0020 6920656e 67696e65 20647269 76657200 i engine driver.
0030 61757468 6f723d4e 6174696f 6e616c20 author=National
0040 4368656e 67204b75 6e672055 6e697665 Cheng Kung Unive
0050 72736974 792c2054 61697761 6e006c69 rsity, Taiwan.li
0060 63656e73 653d4475 616c204d 49542f47 cense=Dual MIT/G
0070 504c0000 00000000 73726376 65727369 PL......srcversi
0080 6f6e3d32 34444335 46423745 37363038 on=24DC5FB7E7608
0090 41463136 42304343 31460000 00000000 AF16B0CC1F......
00a0 64657065 6e64733d 00726574 706f6c69 depends=.retpoli
00b0 6e653d59 006e616d 653d6669 62647276 ne=Y.name=fibdrv
00c0 00766572 6d616769 633d342e 31352e30 .vermagic=4.15.0
00d0 2d34352d 67656e65 72696320 534d5020 -45-generic SMP
00e0 6d6f645f 756e6c6f 61642000 mod_unload .
```
- [ ] 這個 fibdrv 名稱取自 Fibonacci driver 的簡稱，儘管在這裡顯然是為了展示和教學用途而存在，但針對若干關鍵的應用場景，特別去撰寫 Linux 核心模組，仍有其意義，請找出 Linux 核心的案例並解讀。
文章一開始有提到 entropy，原本以為指的是以前修熱力學所提到的測量能量增減所用的熵，沒想到其實有[資訊熵](https://zh.wikipedia.org/wiki/%E7%86%B5_(%E4%BF%A1%E6%81%AF%E8%AE%BA))。指的是是接收的每條消息中包含的資訊的平均量。
在文章中有提到，CPU 執行時間可能因為要填滿 pipeline、處理 branch 等等而會產生[時基誤差](https://zh.wikipedia.org/wiki/%E6%8A%96%E5%8A%A8)使的執行時間難以預估。而為了測量時基誤差，透過 [crypto/jitterentropy.c](https://github.com/torvalds/linux/blob/master/crypto/jitterentropy.c) 中的 jent_measure_jitter() 去產生隨機的 bit來解決。
- [ ] 查閱 ktime 相關的 API，並找出使用案例
- [ ] clock_gettime 和 High Resolution TImers (HRT) 的關聯為何？
參考這篇[文章](https://elinux.org/High_Resolution_Timers)提到，clock_gettime 為 HRT Posix Timers API，並透過下面的 timespec 的結構去儲存時間單位。
```clike
struct timespec {
time_t tv_sec; /* seconds */
long tv_nsec; /* nanoseconds */
};
```
而 time.c 提供多種時鐘，最主要的是 CLOCK_REALTIME and CLOCK_MONOTONIC。CLOCK_REALTIME 使用的是系統本身的時間，因此在執行時可透過改變系統時鐘測量時間受到影響。而 CLOCK_MONOTONIC 是指從過去到現在經過的絕對時間，時間會穩定遞增，不是系統時間影響。
仿效此篇[文章](http://www.guyrutenberg.com/2007/09/22/profiling-code-using-clock_gettime/)做測試:
```clike
#include <time.h>
#include <stdio.h>
static int diff_in_ns(struct timespec t1, struct timespec t2)
{
struct timespec diff;
if (t2.tv_nsec - t1.tv_nsec < 0) {
diff.tv_sec = t2.tv_sec - t1.tv_sec - 1;
diff.tv_nsec = t2.tv_nsec - t1.tv_nsec + 1000000000;
} else {
diff.tv_sec = t2.tv_sec - t1.tv_sec;
diff.tv_nsec = t2.tv_nsec - t1.tv_nsec;
}
return (diff.tv_sec * 1000000000 + diff.tv_nsec);
}
int main()
{
struct timespec start, end;
clock_gettime(CLOCK_MONOTONIC, &start);
sleep(2);
clock_gettime(CLOCK_MONOTONIC, &end);
printf("%d\n",diff_in_ns(start, end));
return 0;
}
```
測量程序暫停兩秒前後相差多少 ns，執行後得到的結果為 2000182543。這種測量前後時間相差多少 ns 的方法也可以用在這次作業去測量 userspace 執行的時間。
- [ ] fibdrv 如何透過 Linux Virtual File System 介面，讓計算出來的 Fibonacci 數列得以讓 userspace (使用者層級) 程式 (本例就是 client.c 程式) 得以存取呢？
VFS是一個檔案系統虛擬層，再往下是實體的檔案系統。VFS主要是使上層的程式用單一的方式去和底層檔案系統溝通。
在 [linux/fs.h](https://github.com/torvalds/linux/blob/master/include/linux/fs.h) 中有看到 file_operations 的 結構。(結構眾多，只列出此次用到1的)
```clike
struct file_operations {
struct module *owner;
loff_t (*llseek) (struct file *, loff_t, int);
ssize_t (*read) (struct file *, char __user *, size_t, loff_t *);
ssize_t (*write) (struct file *, const char __user *, size_t, loff_t *);
int (*release) (struct inode *, struct file *);
} __randomize_layout;
```
在 fibdrv.c 中利用下面宣告去定義相關操作。
```clike
const struct file_operations fib_fops = {
.owner = THIS_MODULE,
.read = fib_read,
.write = fib_write,
.open = fib_open,
.release = fib_release,
.llseek = fib_device_lseek,
};
```
並利用下面兩個呼叫去註冊。
```clike
cdev_init(fib_cdev, &fib_fops);
rc = cdev_add(fib_cdev, fib_dev, 1);
```
並利用下面兩個去創建 class 以及設備文件作為接口。
```clike
fib_class = class_create(THIS_MODULE, DEV_FIBONACCI_NAME);
device_create(fib_class, NULL, fib_dev, NULL, DEV_FIBONACCI_NAME)
```
- [ ] 注意到 fibdrv.c 存在著 DEFINE_MUTEX, mutex_trylock, mutex_init, mutex_unlock, mutex_destroy 等字樣，什麼場景中會需要呢？
在多執行序的程式如果共用相同的記憶體並同時對它做操作，可能因為在不同 CPU 同時執行或是因為 CPU 排班先後執行而導致執行錯誤，這裡簡單寫個 pthread 程式去測試。
```clike
#include <stdio.h>
#include <unistd.h>
#include <pthread.h>
int counter = 0;
void* child() {
for(int i = 0;i < 5;++i) {
counter = counter + 1;
printf("Counter = %d\n", counter);
sleep(1);
}
pthread_exit(NULL);
}
int main() {
pthread_t t1, t2;
pthread_create(&t1, NULL, child, NULL);
pthread_create(&t2, NULL, child, NULL);
pthread_join(t1, NULL);
pthread_join(t2, NULL);
printf("End = %d", counter);
return 0;
}
```
執行結果：
```
yuan@yuan-X555LF:~$ gcc test.c -lpthread
yuan@yuan-X555LF:~$ ./a.out
Counter = 1
Counter = 2
Counter = 3
Counter = 4
Counter = 5
Counter = 5
Counter = 6
Counter = 7
Counter = 8
Counter = 9
End = 9
```
可以見到因為 counter 是全域變數，因此透過 pthread 建立得執行序都能對 counter 做操作，應此可能會造成不可預期的結果。
如果加上 mutex ，如果執行序再做切換時程序停留在臨界區段，而有其他程式要執行臨界區段時，便會產生 busywaiting。因此把上述程式加上 mutex，便能正確執行。
```clike
pthread_mutex_t mutex0 = PTHREAD_MUTEX_INITIALIZER;
int counter = 0;
void* child() {
for(int i = 0;i < 5;++i) {
pthread_mutex_lock(&mutex0);
counter = counter + 1;
printf("Counter = %d\n", counter);
pthread_mutex_unlock(&mutex0);
sleep(1);
}
pthread_exit(NULL);
}
```
- [ ] 許多現代處理器提供了 clz / ctz 一類的指令，你知道如何透過演算法的調整，去加速 費氏數列 運算嗎？
參考這篇[文章](https://www.slideshare.net/erickitten/fibonacci-fast-doubling)，對於 Fast doubling 的判斷由bit是0還是1去做判斷。
首先，先利用 clz 去求位數，並由位數由高到低去做判斷。
如果是 1 則先求 f(2n) 和 f(2n+1)，並再依此求 f(2n+2)
如果是 0 則求 f(2n) 和 f(2n+1)即可。
假如要求Fib(10)，10的二進位表示式為1010。
| bit | start | 1 | 0 | 1 | 0 | return |
| ------ | ------ | ------ | ------ | ------ | ------| ------|
| f(n) | f(0) | f(2*0+1) | f(1*2) | f(2*2+1) | f(5*2) | f(10)|
| a | 0 | 1 | 1 | 5 | 55 | 55 |
| b | 1 | 1 | 2 | 8 | 89 | |
因此能透過clz去得知判斷次數，減少不必要的判斷。
# 改善效率
用 ktime 去取的時間，並把時間回傳給 userspace。回想到大三上 OS 課程寫的 [mailbox](https://github.com/zodf0055980/OSclass_hw2_mailbox/blob/master/module/mailbox.c) 作業，利用 char *buf 去把要回傳的東西寫入 buf。
```clike
sprintf(buf,"%s",stmkbuf[stmheadpdf->number].path);
```
因此想套用此方法去取得回傳的時間
```clike
char tmp[128];
memset(tmp, 0, 128);
sprintf(tmp, "%lld\n", runtime);
strncpy(buf,tmp,128);
```
但發現程式執行到一半會結束執行，並且觀察程式的輸出檔 out ，發現程式會執行到 write 中途就結束了。
```
Writing to /dev/fibonacci, returned the sequence 1
Writing to
```
因此參考其他同學的[共筆](https://hackmd.io/s/SJ34e1-PV)發現有相同的問題，改用 copy to user，便能解決。
由上圖可以發現除了一開始因為要設定初值要花時間較多外，時間大致以 O(n) 上升。
## Fast doubling
透過下面兩個式子，便可以求出 O(logn)的演算法
$\begin{split}
F(2k) &= F(k)[2F(k+1) - F(k)] \\
F(2k+1) &= F(k+1)^2+F(k)^2
\end{split}$
```clike
if (k == 0)
return 0;
long long fn = 1;
long long fn1 = 1;
long long f2n = 1;
long long f2n1 = 0;
long long i = 1;
while (i < k) {
if ((i << 1) <= k) {
f2n1 = fn1 * fn1 + fn * fn;
f2n = fn * (2 * fn1 - fn);
fn = f2n;
fn1 = f2n1;
i = i << 1;
} else {
fn = f2n;
f2n = f2n1;
f2n1 = fn + f2n1;
i++;
}
}
return f2n;
```
求出的時間如下:
並去比較 Iterative 和 Fast Doubling 的執行時間
發現當數字越大， Fast Doubling 的執行時間越短，但由於我們只有測量到 FIB(100)，因此看不太出來 logn 的趨勢，但明顯 Fast Doubling 是比較快的。
## CLZ加速
參考[重新理解數值](https://hackmd.io/s/SkKZBXZT#)中 byte-shift version 的 clz 並嘗試改寫成 64 bit 的版本。
```clike
int n = 0;
unsigned long long clz = k;
if (clz <= 0x00000000FFFFFFFF) {
n += 32;
clz <<= 32;
}
if (clz <= 0x0000FFFFFFFFFFFF) {
n += 16;
clz <<= 16;
}
if (clz <= 0x00FFFFFFFFFFFFFF) {
n += 8;
clz <<= 8;
}
if (clz <= 0x0FFFFFFFFFFFFFFF) {
n += 4;
clz <<= 4;
}
if (clz <= 0x3FFFFFFFFFFFFFFF) {
n += 2;
clz <<= 2;
}
if (clz <= 0x7FFFFFFFFFFFFFFF) {
n += 1;
clz <<= 1;
}
k <<= n;
n = 64 - n;
```
最後求出除了 clz 外的 bit 數作為判斷次數。並把 k 作往左位移使 MSB 為 1 使方便作判斷。
```clike
unsigned long long fn = 0;
unsigned long long fn1 = 1;
unsigned long long f2n = 0;
unsigned long long f2n1 = 0;
int i;
for (i = 0; i < n; i++) {
f2n1 = fn1 * fn1 + fn * fn;
f2n = fn * (2 * fn1 - fn);
if (k & 0x8000000000000000) {
fn = f2n1;
fn1 = f2n + f2n1;
} else {
fn = f2n;
fn1 = f2n1;
}
k <<= 1;
}
return fn;
```
利用 k & 0x8000000000000000 去判斷 MSB 的位元，如果是 1 則先求 f(2n+1) 和 f(2n+2)，如果是 0 則求 f(2n) 和 f(2n+1)。
由上圖可見透過 clz 可以有效加速 Fast doubling。而為何 Fast doubling 執行時間有較大的變化，使之執行時間產生鋸齒狀，我認為和 bit 有關。例如: 19 的二進為表示式為 10011，除了五次利用公式求出 f(2n) 外，還需要3次加法。而 24 的二進位表示是為 11000 卻只需要2次加法而已。這種因為 1 bit 個數差距所導致額外的加法我想是造成執行時間起伏的原因。
# Reference
[你所不知道的C語言：遞迴呼叫篇](https://hackmd.io/nWwDmm64SyqmlhGpgNbbag?view)
Sign in with Wallet
Connect another wallet