# 2019q1 Homework2 (fibdrv)
contributed by < `ChihAnLin0607` >
## Module 背景知識
### Linux 設備模型概念
硬件拓撲描述Linux設備模型中四個重要概念中三個：Bus，Class和Device（第四個為Device Driver，後面會說）。
* Bus（匯流排）：Linux 將匯流排視作 CPU 和一個或多個設備之間資訊交換的通道。而為了抽象化裝置模型，所有的裝置都應連接到匯流排上。
* Class (類別): 在 Linux 裝置模型中，Class 主要是集合具有相似功能或屬性的設備，這樣就可以抽像出一套可以在多個設備之間共用的數據結構和介面函式。因而從屬於相同 Class 的設備的驅動程序，就不再需要重複定義這些公共資源，直接從 Class 中繼承即可。
* Device (裝置): 抽象系統中所有的硬件設備，描述它的名字、屬性、從屬的 Bus 、從屬的 Class 等信息。
* Device Driver (裝置驅動程式): Linux 設備模型用 Driver 抽象硬件設備的驅動程序，它包含設備初始化、電源管理相關的接口實現。而 Linux 內核中的驅動開發，基本都圍繞該抽象進行（實現所規定的接口函數）。
:::danger
改用繁體中文和台灣慣用術語!
儘量引用第一手材料，如 Linux 核心的 `Documentation/` 目錄下的文件，有許多對岸的材料已過時或充斥謬誤。
:notes: jserv
:::
來源：[Linux設備模型(1)_基本概念](http://www.wowotech.net/linux_kenrel/13.html)
### Block Device Driver vs. Character Device Driver
Device Driver 大致分為 Block Device Driver 、 Character Device Driver 和 Network Device Driver 三類。
* **Block Device Driver** 是以固定大小長度來傳送轉移資料，其所連接的 Block Device 大致是可以隨機存取 ( Random Access )資料的設備，如硬碟機或光碟機
* **Character Device Driver** 是以不定長度的字元傳送資料，其所連接的 Character Device 則是依循先後順序存取資料的設備，如印表機、終端機等。
* **Network Device Driver** 是與其他主機交換資料裝置的驅動，可以是硬體設備(網路卡)也可以是軟體模擬的虛構裝置(loopback)。
來源：[[轉]Linux driver 開發 - Function Routines 和 Data Structure](http://huenlil.pixnet.net/blog/post/23315109-%5B%E8%BD%89%5Dlinux-driver-%E9%96%8B%E7%99%BC---function-routines-%E5%92%8C-data-struct)
### 概念圖
module 被 insmod 命令加載到 kernel 中後， linux 會用 cdev 紀錄此 module 的資訊，其中包括對他的操作接口( file_operations )。使用者空間的程序，只需要對此 module 進行這些特定的接口操作，就可以和此 module 互動。
來源：[Linux 字符设备驱动结构（一）—— cdev 结构体、设备号相关知识解析](https://blog.csdn.net/zqixiao_09/article/details/50839042)
### struct cdev
定義於 [<linux/cdev.h>](https://github.com/torvalds/linux/blob/master/include/linux/cdev.h) 中：
```clike
struct cdev {
struct kobject kobj; // 簡單來說就是 cdev 的父類別
struct module *owner; // 通常為 macro: THIS_MODULE
const struct file_operations *ops; // linux 將 module 視同檔案，所以要定義對此「檔案」操作的實際行為
struct list_head list;
dev_t dev; // 設備號( major 、 minor number )
unsigned int count; // minor number 數量
} __randomize_layout;
```
以下是 **struct kobject** 更仔細的描述：
linux 所支援的硬件設備數量、種類非常繁多，這使 kernel 無可避免地有大量的有關設備模型的數據結構。這些數據結構一定有一些共同的功能，需要抽像出來統一實現，否則就會不可避免的產生冗餘代碼。這就是 Kobject 誕生的背景。
Kobject 功能與特點：
* 通過 parent 指針，可以將所有 kobject 以層次結構的形式組合起來。
* 使用一個引用計數（ reference count ），來記錄kobject 被引用的次數，並在引用次數變為 0 時把它釋放（這是kobject誕生時的唯一功能）。
* 和 sysfs 虛擬文件系統配合，將每一個 kobject 及其特性，以文件的形式，開放到用戶空間（有關 sysfs ，會在其它文章中專門描述，本文不會涉及太多內容）。
* 在 Linux 中， Kobject 幾乎不會單獨存在。它的主要功能，就是內嵌在一個大型的數據結構中，為這個數據結構提供一些底層的功能實現。
* Linux driver 開發者，很少會直接使用 kobject 以及它提供的接口，而是使用構建在 kobject 之上的設備模型接口。
來源：[Linux設備模型(2)_Kobject](http://www.wowotech.net/device_model/kobject.html)
### struct kobj_map
```clike=
struct kobj_map {
struct probe {
struct probe *next; /* 這樣形成了鏈表結構 */
dev_t dev; /* 設備號 */
unsigned long range; /* 設備號的範圍 */
struct module *owner;
kobj_probe_t *get;
int (*lock) (dev_t, void *);
void *data; /* 指向struct cdev對象 */
} *probes[255];
struct mutex *lock;
}
```
`struct kobj_map`是一個是用來管理設備號和其對應設備的一個結構， linux/kobj_map.h 會宣告一個全域的實體。每個 driver 都有一個獨一無二的設備號( major number )，利用這個設備號就能透過查 kobj_map 來找出該設備號設備的 driver 程式位置。
`dev_t`的前 12 bit 是主設備號( major number )，後 20 bit 則是副設備號( minor number )。 major number 剛剛提過就像是 driver 的 ID，用來查找出其 driver 主體程式的位置； minor number 是由 driver 自己管理的號碼，當一個 driver 同時控制許多裝置時，就可以用 minor number 做區分。
回到 kobj_map 結構，結構有個指標陣列成員 probes ，陣列內的第 n 個指標都指向一個 linked list 結構的頭，其所有 node 都是由 major number 等於 n 的 driver 資訊所組成，第一個 node 的 minor number 為一、第二個 node 的 minor number 為二，以此類推。 也就是說，要找到 major number 為 10 ，minor number 為 2 的 driver 的話，去查詢 kobj_map 底下的 probes[10] ， 其指向的 linked list 的第 2 個 node 就是 minor number 為 2 的 driver 資訊。
來源：
1. [linux設備：cdev和kobj_map](https://www.twblogs.net/a/5b82214b2b71772165afccb6)
2. [LDDP:五、開發驅動程式需要的基礎知識](http://silverfoxkkk.pixnet.net/blog/post/41156465-lddp%3A%E4%BA%94%E3%80%81%E9%96%8B%E7%99%BC%E9%A9%85%E5%8B%95%E7%A8%8B%E5%BC%8F%E9%9C%80%E8%A6%81%E7%9A%84%E5%9F%BA%E7%A4%8E%E7%9F%A5%E8%AD%98)
### alloc_chrdev_region
`int alloc_chrdev_region(dev_t *dev, unsigned baseminor, unsigned count, const char *name); ; `
`alloc_chrdev_region` 可以用來取得可用的 major number ， 並保留 baseminor 開始 count 個數的 minor number 空間。
### struct file_operations
linux 設計成將所有東西都視為檔案，不論是真的檔案、裝置或是 module 在 linux 中都被視為檔案。所以若要對 module 類型檔案做操作，則需要自行定義其操作( read 、 write 等等)的實際行為。
struct file_operations定義在 [<linux/fs.h>](https://github.com/torvalds/linux/blob/master/include/linux/fs.h) 是一組函數指標的集合。
* `loff_t`參數: 是一個 long offset , 其長度最少有 64 bits ?
* `__user`參數: 該指標是指向user-space位址，因為 kernel 和 user process 的記憶體不共用，所以不可直接取值。
```clike=
struct file_operations {
/*
此欄位的作用,是避免模組仍在活動中時,被卸載出核心.
通常初始化為 THIS_MODULE (所定義的?#64;個巨集)
幾乎沒有例外
*/
struct module *owner;
/*
改變檔案的存取位置,使得下次讀寫在新位置開始
改變的是file結構裡的loff_t f_pos參數,file結構看後面
*/
loff_t (*llseek) (struct file *, loff_t, int);
ssize_t (*read) (struct file *, char __user *, size_t, loff_t *);
// 類似 read 但不同步
ssize_t (*aio_read) (struct kiocb *, char __user *, size_t, loff_t);
ssize_t (*write) (struct file *, const char __user *, size_t, loff_t *);
// 類似write,但不同步
ssize_t (*aio_write) (struct kiocb *, const char __user *, size_t, loff_t);
// 讀取檔案系統上的目錄
int (*readdir) (struct file *, void *, filldir_t);
/*
檢查檔案I/O狀態,下次的讀寫如有停頓,延遲,來不及的情況,應該提供kernel用來休眠等待
直到可以順利I/O為止,指向NULL則kernel會假設你的裝置永遠都可流暢讀寫,而不會停頓
*/
unsigned int (*poll) (struct file *, struct poll_table_struct *);
int (*ioctl) (struct inode *, struct file *, unsigned int, unsigned long);
int (*mmap) (struct file *, struct vm_area_struct *);
int (*open) (struct inode *, struct file *);
/*
為了避免資料尚未完全寫出之前,裝置檔被關閉
process關閉裝置檔時會呼叫flush
*/
int (*flush) (struct file *);
int (*release) (struct inode *, struct file *);
//讓應用程式用來將滯留在記憶體中的資料全數確實寫入裝置
int (*fsync) (struct file *, struct dentry *, int datasync);
// 類似fsynce,但不同步
int (*aio_fsync) (struct kiocb *, int datasync);
int (*fasync) (int, struct file *, int);
// 檔案鎖定
int (*lock) (struct file *, int, struct file_lock *);
ssize_t (*readv) (struct file *, const struct iovec *, unsigned long, loff_t *);
ssize_t (*writev) (struct file *, const struct iovec *, unsigned long, loff_t *);
ssize_t (*sendfile) (struct file *, loff_t *, size_t, read_actor_t, void *);
ssize_t (*sendpage) (struct file *, struct page *, int, size_t, loff_t *, int);
unsigned long (*get_unmapped_area)(struct file *, unsigned long, unsigned long, unsigned long, unsigned long);
int (*check_flags)(int);
int (*dir_notify)(struct file *filp, unsigned long arg);
int (*flock) (struct file *, int, struct file_lock *);
};
```
來源：[重要的資料結構 file_operations,file,inode](http://welkinchen.pixnet.net/blog/post/41068895-%E9%87%8D%E8%A6%81%E7%9A%84%E8%B3%87%E6%96%99%E7%B5%90%E6%A7%8B-file_operations%2Cfile%2Cinode-)
### cdev_alloc
```clike
struct cdev *cdev_alloc(void)
{
struct cdev *p = kzalloc(sizeof(struct cdev), GFP_KERNEL);
if (p) {
INIT_LIST_HEAD(&p->list);
kobject_init(&p->kobj, &ktype_cdev_dynamic);
}
return p;
```
取得 struct cdev 實體。
來源：[Linux 字符设备驱动结构（一）—— cdev 结构体、设备号相关知识解析](https://blog.csdn.net/zqixiao_09/article/details/50839042)
### cdev_init
```clike
void cdev_init(struct cdev *cdev, const struct file_operations *fops)
{
memset(cdev, 0, sizeof *cdev);
INIT_LIST_HEAD(&cdev->list);
kobject_init(&cdev->kobj, &ktype_cdev_default);
cdev->ops = fops;
}
```
初始化 cdev 外，也根據傳入參數指定 cdev 的 file_operattions。
來源：[Linux 字符设备驱动结构（一）—— cdev 结构体、设备号相关知识解析](https://blog.csdn.net/zqixiao_09/article/details/50839042)
### cdev_add
```clike
int cdev_add(struct cdev *p, dev_t dev, unsigned count)
{
p->dev = dev;
p->count = count;
return kobj_map(cdev_map, dev, count, NULL, exact_match, exact_lock, p);
}
```
將 cdev 加入到 kobj_map 中。
來源：[Linux 字符设备驱动结构（一）—— cdev 结构体、设备号相关知识解析](https://blog.csdn.net/zqixiao_09/article/details/50839042)
### device_create
`struct device * device_create ( struct class * class,
struct device * parent,
dev_t devt,
const char * fmt,
...);
`
將 devt 代表的 device 加入到檔案系統 (sysfs) 中，成功後，將能在 /dev 底下看到名為 fmt 的裝置檔。
來源：[device_create](https://www.fsl.cs.sunysb.edu/kernel-api/re812.html)
---
## 列出 Fibonacci(100) 以上的數值
Fibonacci(92) 為 0x1 11F3 8AD0 840B F6BF ，超過 8 bytes (64 bits) 能夠顯示的最大數字，所以若要能夠顯示 Fibonacci(100) 以上的數字，就必須使用到一個以上的變數來存取回傳值：
```clike
// bigN.h
struct BigN {
unsigned long long lower;
unsigned long long upper;
};
```
使用 struct BigN 來將一個數字分成兩部份：高位的 64 bits 存在 upper 中、低位的 64 bit 則是存在 lower 中。
大數在做加法時，則需要注意 lower 是否需要進位到 upper：
```clike=
// bigN.h
static inline void addBigN(struct BigN *output, struct BigN x, struct BigN y)
{
output->upper = x.upper + y.upper;
if (y.lower > ~x.lower)
output->upper++;
output->lower = x.lower + y.lower;
}
```
#4 因為 x.lower + ~x.lower = ~0 ，移項之後 ~x.lower = ~0 - x.lower ，也就是說 ~x.lower 表示 x.lower 跟 最大值( ~0 )的距離。所以若 y.lower 比 x.lower 距離最大值的距離還大，就表示相加後會 overflow 、需要進位，就把 output->upper++ 。
最後來修改 fibdrv.c ：
```clike=
// fibdrv.c
static ssize_t fib_read(struct file *file,
char *buf,
size_t size,
loff_t *offset)
{
return (ssize_t) fib_sequence(*offset, buf, size);
}
static long long fib_sequence(long long k, char *buf, size_t size)
{
ktime_t ktime = ktime_get();
/* FIXME: use clz/ctz and fast algorithms to speed up */
struct BigN f[k + 2];
memset(f, 0, sizeof(struct BigN) * (k + 2));
f[0].lower = 0;
f[1].lower = 1;
for (int i = 2; i <= k; i++)
addBigN(&f[i], f[i - 1], f[i - 2]);
unsigned int ns = ktime_to_ns(ktime_sub(ktime_get(), ktime));
printk(KERN_INFO "%lld:\t%u ns\n", k, ns);
copy_to_user(buf, &f[k], size);
return 1;
}
```
現在費氏數列的值是透過 buf 回傳給 user-process，但不能直接對 buf 做操作，因為 kernel 和 user-space 的記憶體空間是互相獨立的，所以需要利用 copy_to_user 來將值傳到使用者空間的 buf 中，見 #26。以下為費氏數列 90 到 103 的數出結果。
```
.
.
.
i = 90, 1969 ns, f[90] = 0x0000000000000000 27F80DDAA1BA7878
i = 91, 1995 ns, f[91] = 0x0000000000000000 40ABCFB3C0325745
i = 92, 1958 ns, f[92] = 0x0000000000000000 68A3DD8E61ECCFBD
i = 93, 1960 ns, f[93] = 0x0000000000000000 A94FAD42221F2702
i = 94, 2075 ns, f[94] = 0x0000000000000001 11F38AD0840BF6BF
i = 95, 2028 ns, f[95] = 0x0000000000000001 BB433812A62B1DC1
i = 96, 2038 ns, f[96] = 0x0000000000000002 CD36C2E32A371480
i = 97, 1987 ns, f[97] = 0x0000000000000004 8879FAF5D0623241
i = 98, 2007 ns, f[98] = 0x0000000000000007 55B0BDD8FA9946C1
i = 99, 2051 ns, f[99] = 0x000000000000000B DE2AB8CECAFB7902
i = 100, 2054 ns, f[100] = 0x0000000000000013 33DB76A7C594BFC3
i = 101, 2057 ns, f[101] = 0x000000000000001F 12062F76909038C5
i = 102, 2095 ns, f[102] = 0x0000000000000032 45E1A61E5624F888
i = 103, 2074 ns, f[103] = 0x0000000000000051 57E7D594E6B5314D
.
.
.
```
改用 128 bits 紀錄費氏數列的值後，就可以紀錄到第 Fibonacci(186)，其值為 0xFA63C8D9FA216A8F C8A7213B333270F8 。
---
## 時間開銷
### 圖表
(未用 clz / ctz 改寫費氏數列演算法前)
圖片顯示 kernel 將資料傳送至 user space 的時間(淺藍色線)大致都維持在 1000 ~ 1500 ns 這附近；<u>kernel 計算時間(綠色線)則根據 n 大致成線性成長，符合時間複雜度 $O(n)$ </u>； user space 的到的時間差(紫色線)為前兩者的合，所以其也是呈線性成長。
### 資料取得方法
在 kernel 中，因為數列的值是改由 buf 回傳給 user space，所以`read`的 return 值被空了出來，因此將他拿來傳遞 kernel 中的計算時間。
```clike
// fibdrv.c
static ssize_t fib_read(struct file *file,
char *buf,
size_t size,
loff_t *offset)
{
ktime_t ktime = ktime_get();
fib_sequence(*offset, buf, size);
unsigned int ns = ktime_to_ns(ktime_sub(ktime_get(), ktime));
return ns;
}
```
client 端取的 kernel 計算時間後， 就可以利用 user space 呼叫`read`所花的總時間減去此 kernel 計算時間，來取得 kernel 傳遞資料到 user space 所花時間。
```clike=
//client.c
struct timespec start, end;
printf(
"|n|\t|user-space 時間差|\t|kernel 計算所花時間|\t|kernel傳遞到user "
"space時間開銷|\n");
for (i = 0; i <= MAX_LENGTH; i+=5) {
lseek(fd, i, SEEK_SET);
buf.lower = 0;
buf.upper = 0;
clock_gettime(CLOCK_MONOTONIC, &start);
kernel_time = read(fd, &buf, sizeof(struct BigN));
clock_gettime(CLOCK_MONOTONIC, &end);
printf("%3d\t\t%ld\t\t\t%ld\t\t\t\t%ld ", i,
end.tv_nsec - start.tv_nsec, kernel_time,
end.tv_nsec - start.tv_nsec - kernel_time);
printf("\n");
}
```
其輸出結果片斷如下：
```
|n| |user-space 時間差| |kernel 計算所花時間| |kernel傳遞到user space時間開銷|
0 7277 688 6589
5 859 187 672
10 791 180 611
15 727 174 553
20 866 260 606
.
.
.
```
最後再利用 gnuplot 就能將輸出製成上圖。
---
## 快速費氏數算法
### 概況
快速費氏數列算法其實就是將第 n 個數，用其第 n/2 左右的數字來表達，這樣計算第 n 個數字時，就只需要計算 $log_2n$ 次就好。實際公式如下：
$f(2n) = 2 \times f(n+1) \times f(n) - f^2(n)$
$f(2n+1)=f^2(n+1) + f^2(n)2$
得到時間開銷結果如下：
其結果直觀看起來時間複雜度為 $O(n)$ ，並不是 $O(logn)$。仔細想一下，我猜會有這樣出入原因是因為，雖然只需要遞迴呼叫 $log_2n$ 次，但每一次呼叫的時間複雜度並不是 $O(1)$。
另外除了時間複雜度保持 $O(n)$ 外，總共所花的時間也上升了許多，$f(186)$ 竟然需要 77332 ns，相較於原本方法所花的 2996 ns，快速費式數算法似乎一點也不快速。
### 效能提升
#### 瓶頸
由於這個演算法需要用到乘法與減法，所以特別先實作了 struct BigN 的乘法與減法：
```clike=
// bigN.c
static inline void minusBigN(struct BigN *output, struct BigN x, struct BigN y)
{
if (x.lower < y.lower) {
output->lower = (-1 - y.lower) + 1 + x.lower;
x.upper--;
} else
output->lower = x.lower - y.lower;
output->upper = x.upper - y.upper;
}
static inline void multiBigN(struct BigN *output, struct BigN x, struct BigN y)
{
int i = 0, j = 0;
short digit;
output->lower = 0;
output->upper = 0;
for (i = 0; i < 32; i++) {
digit = getDigit(y, i);
if (digit) {
j = 0;
while (j++ < digit)
addBigN(output, *output, x);
}
shift_l_BigN(&x, x);
}
}
```
在實作`multiBigN`時，為了避免溢位其實是用加法來代替乘法，但這就變成大數字相乘的時候，會需要重複非常多次加法，若編譯器又沒接受`addBigN`的 inline 建議，就會需要非常多次的函式呼叫成本，所以我猜這應該是造成效能低落的一大原因。為了證明，我將花費在`multiBigN`的時間獨立計算，並把 read offset 最大值 (186) + 1 當作取得此數字的指令，藉此將直傳回給 userspace：
```clike=
// fibdrv.c
#ifdef PERFORMACE_TRACE
static ktime_t multi_ktime = 0;
static ktime_t ktime;
#endif
static void fib_sequence(long long k, struct BigN *buf)
{
/* 省略 */
if (!(k % 2)) {
/* 省略 */
#ifdef PERFORMACE_TRACE
ktime = ktime_get();
#endif
multiBigN(&tmp1, fn, fn); // tmp := f(n)^2
multiBigN(buf, fn_plus_1, fn); // buf := f(n+1)*f(n)
#ifdef PERFORMACE_TRACE
multi_ktime = ktime_add(ktime_sub(ktime_get(), ktime), multi_ktime);
#endif
/* 省略 */
} else {
/* 省略 */
#ifdef PERFORMACE_TRACE
ktime = ktime_get();
#endif
multiBigN(&tmp1, fn_plus_1, fn_plus_1); // tmp1 := f(n+1)^2
multiBigN(&tmp2, fn, fn); // tmp2 := f(n)^2
#ifdef PERFORMACE_TRACE
multi_ktime = ktime_add(ktime_sub(ktime_get(), ktime), multi_ktime);
#endif
/* 省略 */
}
}
static ssize_t fib_read(struct file *file,
char *buf,
size_t size,
loff_t *offset)
{
ktime_t ktime = ktime_get();
#ifdef FAST_FIBONACCI
#ifdef PERFORMACE_TRACE
if (*offset == MAX_LENGTH + 1)
return ktime_to_ns(multi_ktime);
#endif
/* 省略 */
}
```
並且在 client 的最後將此值讀出來：
```clike=
//client.c
int main()
{
/* 省略 */
#ifdef PERFORMACE_TRACE
lseek(fd, MAX_LENGTH + 1, SEEK_SET);
long multi_time = read(fd, NULL, 0);
printf("multi_time = %ld\n", multi_time);
printf("kernel_all_time = %ld\n", kernel_time_all);
printf("multi_time / kernel_all_time = %f\n",
(double) multi_time / kernel_time_all);
#endif
/* 省略 */
}
```
得到結果：
```shell
$sudo ./client
(省略)
130 63341 62242 1099
135 65145 64026 1119
140 69401 68315 1086
145 71051 69959 1092
150 75362 74235 1127
155 78114 77008 1106
160 81889 80784 1105
165 84034 82945 1089
170 88961 87839 1122
175 90117 89019 1098
180 104542 103066 1476
185 119974 117752 2222
multi_time = 1564345
kernel_all_time = 1854659
multi_time / kernel_all_time = 0.843468
```
果然，花在`multiBigN`的時間佔了 kernel 計算總時間的 84.3% 。
#### 優化
為了避免上述乘法會進行無數次加法的狀況，我將`struct BigN`改寫，利用一個長度為 6 的`unsigned long long`陣列，每個值都用來存放一整個大數字的 24 bits 部份，所以最高能夠使用到 144 bits。
```clike=
#define BIGN_PART_COUNT 6
#define BIGN_BIT_EACH_PART 24
struct BigN {
unsigned long long num_part[BIGN_PART_COUNT];
};
```
這樣好處是，在做乘法時，能就將各位數相乘相加並存放在指定的位置中，不用擔心 overflow 的問題，最後在一次進位，避開先前的不斷作加法的狀況。
```clike=
static inline void multiBigN(struct BigN *output, struct BigN x, struct BigN y)
{
int xi, yi;
// 初始化 output
for (xi = 0; xi < BIGN_PART_COUNT; xi++)
output->num_part[xi] = 0;
// 做直式乘法
for (yi = 0; yi < BIGN_PART_COUNT; yi++) {
if (!y.num_part[yi])
continue;
for (xi = 0; xi < BIGN_PART_COUNT - yi; xi++) {
if (!x.num_part[xi])
continue;
output->num_part[xi + yi] += x.num_part[xi] * y.num_part[yi];
}
}
// 進位
for (xi = 0; xi < BIGN_PART_COUNT - 1; xi++) {
if (output->num_part[xi] & 0xFFFFFFFFFF000000) {
output->num_part[xi + 1] +=
(output->num_part[xi] & 0xFFFFFFFFFF000000) >>
BIGN_BIT_EACH_PART;
output->num_part[xi] &= 0xFFFFFF;
}
}
}
```
再次測試 `multiBigN` 耗時比例：
```shell
$ sudo ./client
.
.
.
155 20014 19260 754
160 20209 19443 766
165 20263 19549 714
170 51306 50418 888
175 51561 49938 1623
180 53593 51982 1611
185 54618 53008 1610
multi_time = 546676
kernel_all_time = 988936
multi_time / kernel_all_time = 0.552792
```
成功降低成 55.27 % 左右。
最後再來測試總體耗時，結果顯示確實變快許多，但是仍然比一開始的慢：
但這結果顯然怪怪的，快速費氏數算法居然慢這麼多，這應該是數值系統造成的影響，上述的方式都是使用我自己定義的 `struct BigN` 數字系統來做操作，而這個操作的乘法顯然成本是高加法非常多的，這就是導致快速費氏算法反而較慢的原因，雖然他遞迴較少次，但每一次因為使用成本較高的乘法，所以總時間反而消耗較多。
最後我改回一般單一變數的數字系統來觀察效能的變化：
果然，若讓乘法與加法的操作成本趨近，那快速費氏演算法的耗時是較低的，不過時間複雜度看起來仍然不是 $O(logn)$，而是 $O(n)$。
---
## 自我檢查清單
* **檔案 `fibdrv.c` 裡頭的 `MODULE_LICENSE`, `MODULE_AUTHOR`, `MODULE_DESCRIPTION`, `MODULE_VERSION` 等巨集做了什麼事，可以讓核心知曉呢？ `insmod` 這命令背後，對應 Linux 核心內部有什麼操作呢？請舉出相關 Linux 核心原始碼並解讀**
MODULE_LICENSE 定義如下：
```clike
#define MODULE_LICENSE(__MODULE_LICENSE_value) \
static __attribute__((unused)) const char *__MODULE_LICENSE_name = \
__MODULE_LICENSE_value
```
* 當我們透過 `insmod` 去載入一個核心模組時，為何 `module_init` 所設定的函式得以執行呢？Linux 核心做了什麼事呢？
* 試著執行 `$ readelf -a fibdrv.ko`, 觀察裡頭的資訊和原始程式碼及 `modinfo` 的關聯，搭配上述提問，解釋像 `fibdrv.ko` 這樣的 ELF 執行檔案是如何「植入」到 Linux 核心
* 這個 `fibdrv` 名稱取自 Fibonacci driver 的簡稱，儘管在這裡顯然是為了展示和教學用途而存在，但針對若干關鍵的應用場景，特別去撰寫 Linux 核心模組，仍有其意義，請找出 Linux 核心的案例並解讀。提示: 可參閱 [Random numbers from CPU execution time jitter](https://lwn.net/Articles/642166/)
* 查閱 [ktime 相關的 API](https://www.kernel.org/doc/html/latest/core-api/timekeeping.html)，並找出使用案例 (需要有核心模組和簡化的程式碼來解說)
* [clock_gettime](https://linux.die.net/man/2/clock_gettime) 和 [High Resolution TImers (HRT)](https://elinux.org/High_Resolution_Timers) 的關聯為何？請參閱 POSIX 文件並搭配程式碼解說
* `fibdrv` 如何透過 [Linux Virtual File System](https://www.win.tue.nl/~aeb/linux/lk/lk-8.html) 介面，讓計算出來的 Fibonacci 數列得以讓 userspace (使用者層級) 程式 (本例就是 `client.c` 程式) 得以存取呢？解釋原理，並撰寫或找出相似的 Linux 核心模組範例
* 注意到 `fibdrv.c` 存在著 `DEFINE_MUTEX`, `mutex_trylock`, `mutex_init`, `mutex_unlock`, `mutex_destroy` 等字樣，什麼場景中會需要呢？撰寫多執行緒的 userspace 程式來測試，觀察 Linux 核心模組若沒用到 mutex，到底會發生什麼問題
* 許多現代處理器提供了 [clz / ctz](https://en.wikipedia.org/wiki/Find_first_set) 一類的指令，你知道如何透過演算法的調整，去加速 [費氏數列](https://hackmd.io/s/BJPZlyDSV) 運算嗎？請列出關鍵程式碼並解說
Sign in with Wallet
Connect another wallet