# 2019q1 Homework2 (fibdrv)
contributed by < `jeffcarl67` >
## 環境
* Linux 4.15.0-45-generic #48~16.04.1-Ubuntu SMP
* gcc (Ubuntu 5.4.0-6ubuntu1~16.04.11) 5.4.0 20160609
* 相關程式碼引用自 [linux v5.0](https://elixir.bootlin.com/linux/v5.0/source)
## 作業要求
* 回答「自我檢查清單」的所有問題，需要附上對應的參考資料和必要的程式碼，以第一手材料 (包含自己設計的實驗) 為佳
* 在 GitHub 上 fork [fibdrv](https://github.com/sysprog21/fibdrv)，目標是改善 `fibdrv` 計算 Fibinacci 數列的執行效率，過程中需要量化執行時間，可在 Linux 核心模組和使用層級去測量
* 在 Linux 核心模組中，可用 ktime 系列的 API
* 在 userspace 可用 [clock_gettime](https://linux.die.net/man/2/clock_gettime) 相關 API
* 分別用 gnuplot 製圖，分析 Fibonacci 數列在核心計算和傳遞到 userspace 的時間開銷，單位需要用 us 或 ns (自行斟酌)
* 嘗試解讀上述時間分佈，特別是隨著 Fibonacci 數列增長後，對於 Linux 核心的影響
* 原本的程式碼只能列出到 Fibonacci(100)，請修改程式碼，列出後方更多數值 (注意: 檢查正確性和數值系統的使用)
* 逐步最佳化 Fibonacci 的執行時間，引入 [費氏數列](https://hackmd.io/s/BJPZlyDSV) 提到的策略，並善用 [clz / ctz](https://en.wikipedia.org/wiki/Find_first_set) 一類的指令，過程中都要充分量化
## 自我檢查清單
* **檔案 `fibdrv.c` 裡頭的 `MODULE_LICENSE`, `MODULE_AUTHOR`, `MODULE_DESCRIPTION`, `MODULE_VERSION` 等巨集做了什麼事，可以讓核心知曉呢？ `insmod` 這命令背後，對應 Linux 核心內部有什麼操作呢？請舉出相關 Linux 核心原始碼並解讀**
在 `linux/include/linux/module.h` 中, 可以找到 `MODULE_LICENSE`, `MODULE_AUTHOR`, `MODULE_DESCRIPTION`, `MODULE_VERSION` 定義如下:
```c=
#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` 定義如下:
```c=
#define MODULE_INFO(tag, info) __MODULE_INFO(tag, tag, info)
```
而 `__MODULE_INFO` 定義在 `linux/include/linux/moduleparam.h` 中, 定義如下:
```c=
#define __MODULE_INFO(tag, name, info) \
static const char __UNIQUE_ID(name)[] \
__used __attribute__((section(".modinfo"), unused, aligned(1))) \
= __stringify(tag) "=" info
```
* `__UNIQUE_ID`
定義在 `linux/include/linux/compiler.h` 中
```c=
# define __UNIQUE_ID(prefix) __PASTE(__PASTE(__UNIQUE_ID_, prefix), __LINE__)
```
* `__PASTE`
定義在 `linux/include/linux/compiler_types.h` 中
```c=
#define ___PASTE(a,b) a##b
#define __PASTE(a,b) ___PASTE(a,b)
```
查閱 [`ISO/IEC 9899:201x`](http://port70.net/~nsz/c/c11/n1570.html) 後, 在 [6.10.3.3 The ## operator](http://port70.net/~nsz/c/c11/n1570.html#6.10.3.3) 描述如下:
> If, in the replacement list of a function-like macro, a parameter is immediately preceded or followed by a ## preprocessing token, the parameter is replaced by the corresponding argument's preprocessing token sequence;
再使用簡單的程式驗證
```c=
#include <assert.h>
#define ___PASTE(a, b) a##b
#define __PASTE(a, b) ___PASTE(a, b)
int main() {
char *ab = "hello";
char *p = __PASTE(a, b);
assert(p == ab);
return 0;
}
```
可知巨集 `__PASTE` 只是利用 `##` 在預處理階段將兩個符號拼接成一個
* `__LINE__`
查閱規格書後, 在 [6.10.8.1 Mandatory macros](http://port70.net/~nsz/c/c11/n1570.html#6.10.8.1) 描述如下
> The presumed line number (within the current source file) of the current source line (an integer constant).
即 `__LINE__` 為用於表示當前行號的預定義巨集
可知巨集 `__UNIQUE_ID(prefix)` 展開後會變成如下形式 :
```
__UNIQUE_ID_prefix__LINE__
```
由於使用巨集 ``__UNIQUE_ID`` 的位置不同, 因此可生成幾乎不會重複的變量符號
* `__used`
定義在 `inux/include/linux/compiler_attribute.h` 中
```c=
#define __used __attribute__((__used__))
```
查閱 gcc 文檔後可知, `__used` 用於告知編譯器將變量符號或函數符號放入符號表中
* [index-used-variable-attribute](https://gcc.gnu.org/onlinedocs/gcc/Common-Variable-Attributes.html#index-used-variable-attribute)
> This attribute, attached to a variable with static storage, means that the variable must be emitted even if it appears that the variable is not referenced.
* [index-used-function-attribute](https://gcc.gnu.org/onlinedocs/gcc/Common-Function-Attributes.html#index-used-function-attribute)
> This attribute, attached to a function, means that code must be emitted for the function even if it appears that the function is not referenced. This is useful, for example, when the function is referenced only in inline assembly.
* `__attribute__`
查閱 gcc 文檔可知 :
* `section`
> The section attribute specifies that a variable (or function) lives in a particular section.
* `unused`
> This attribute, attached to a variable, means that the variable is meant to be possibly unused. GCC does not produce a warning for this variable.
* `aligned`
> The aligned attribute specifies a minimum alignment for the variable or structure field, measured in bytes.
* `__stringify`
定義在 `linux/include/linux/stringify.h` 中
```c=
#define __stringify_1(x...) #x
#define __stringify(x...) __stringify_1(x)
```
查閱規格書後, 在 [`6.10.3.2 The # operator`](http://port70.net/~nsz/c/c11/n1570.html#6.10.3.2) 提到 :
> If, in the replacement list, a parameter is immediately preceded by a # preprocessing token, both are replaced by a single character string literal preprocessing token that contains the spelling of the preprocessing token sequence for the corresponding argument.
即 `__stringify` 利用 `#` 將一個符號變為字串
因此 `__MODULE_INFO` 展開後即變成
```
static const char __UNIQUE_ID_name__LINE__[] __used __attribute__((section(".modinfo"), unused, aligned(1))) = "tag" "=" info
```
當使用巨集 `MODULE_LICENSE`, `MODULE_AUTHOR`, `MODULE_DESCRIPTION`, `MODULE_VERSION` 會將指向所需信息的變量符號放入 `.modinfo` section 中
當執行 `sudo strace insmod fibdrv.ko` 跟蹤系統調用後
```
execve("/sbin/insmod", ["insmod", "fibdrv.ko"], [/* 17 vars */]) = 0
brk(NULL) = 0x55e9ffd7d000
access("/etc/ld.so.nohwcap", F_OK) = -1 ENOENT (No such file or directory)
access("/etc/ld.so.preload", R_OK) = -1 ENOENT (No such file or directory)
open("/etc/ld.so.cache", O_RDONLY|O_CLOEXEC) = 3
fstat(3, {st_mode=S_IFREG|0644, st_size=152639, ...}) = 0
mmap(NULL, 152639, PROT_READ, MAP_PRIVATE, 3, 0) = 0x7fa0df8ce000
close(3) = 0
access("/etc/ld.so.nohwcap", F_OK) = -1 ENOENT (No such file or directory)
open("/lib/x86_64-linux-gnu/libc.so.6", O_RDONLY|O_CLOEXEC) = 3
read(3, "\177ELF\2\1\1\3\0\0\0\0\0\0\0\0\3\0>\0\1\0\0\0P\t\2\0\0\0\0\0"..., 832) = 832
fstat(3, {st_mode=S_IFREG|0755, st_size=1868984, ...}) = 0
mmap(NULL, 4096, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0) = 0x7fa0df8cd000
mmap(NULL, 3971488, PROT_READ|PROT_EXEC, MAP_PRIVATE|MAP_DENYWRITE, 3, 0) = 0x7fa0df305000
mprotect(0x7fa0df4c5000, 2097152, PROT_NONE) = 0
mmap(0x7fa0df6c5000, 24576, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_FIXED|MAP_DENYWRITE, 3, 0x1c0000) = 0x7fa0df6c5000
mmap(0x7fa0df6cb000, 14752, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_FIXED|MAP_ANONYMOUS, -1, 0) = 0x7fa0df6cb000
close(3) = 0
mmap(NULL, 4096, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0) = 0x7fa0df8cc000
mmap(NULL, 4096, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0) = 0x7fa0df8cb000
arch_prctl(ARCH_SET_FS, 0x7fa0df8cc700) = 0
mprotect(0x7fa0df6c5000, 16384, PROT_READ) = 0
mprotect(0x55e9ff53d000, 4096, PROT_READ) = 0
mprotect(0x7fa0df8f4000, 4096, PROT_READ) = 0
munmap(0x7fa0df8ce000, 152639) = 0
brk(NULL) = 0x55e9ffd7d000
brk(0x55e9ffd9e000) = 0x55e9ffd9e000
uname({sysname="Linux", nodename="GE40", ...}) = 0
open("/lib/modules/4.15.0-46-generic/modules.softdep", O_RDONLY|O_CLOEXEC) = 3
fcntl(3, F_GETFL) = 0x8000 (flags O_RDONLY|O_LARGEFILE)
fstat(3, {st_mode=S_IFREG|0644, st_size=540, ...}) = 0
read(3, "# Soft dependencies extracted fr"..., 4096) = 540
read(3, "", 4096) = 0
close(3) = 0
open("/proc/cmdline", O_RDONLY|O_CLOEXEC) = 3
read(3, "BOOT_IMAGE=/boot/vmlinuz-4.15.0-"..., 4095) = 119
read(3, "", 3976) = 0
close(3) = 0
getcwd("/home/jeffcarl67/git/fibdrv", 4096) = 28
stat("/home/jeffcarl67/git/fibdrv/fibdrv.ko", {st_mode=S_IFREG|0664, st_size=8416, ...}) = 0
open("/home/jeffcarl67/git/fibdrv/fibdrv.ko", O_RDONLY|O_CLOEXEC) = 3
fstat(3, {st_mode=S_IFREG|0664, st_size=8416, ...}) = 0
mmap(NULL, 8416, PROT_READ, MAP_PRIVATE, 3, 0) = 0x7fa0df8f1000
finit_module(3, "", 0) = 0
munmap(0x7fa0df8f1000, 8416) = 0
close(3) = 0
exit_group(0) = ?
+++ exited with 0 +++
```
從中可以發現與載入模組相關的系統調用為 `finit_module`, 查閱 [finit_module(2) - Linux man page](https://linux.die.net/man/2/finit_module) 可找到相關描述如下:
> init_module() loads an ELF image into kernel space, performs any necessary symbol relocations, initializes module parameters to values provided by the caller, and then runs the module's init function.
> The finit_module() system call is like init_module(), but reads the module to be loaded from the file descriptor fd.
而 `finite_module` 定義於 `linux/kernel/module.c` 中, 函式定義如下
```c=
SYSCALL_DEFINE3(finit_module, int, fd, const char __user *, uargs, int, flags)
{
struct load_info info = { };
loff_t size;
void *hdr;
int err;
err = may_init_module();
if (err)
return err;
pr_debug("finit_module: fd=%d, uargs=%p, flags=%i\n", fd, uargs, flags);
if (flags & ~(MODULE_INIT_IGNORE_MODVERSIONS
|MODULE_INIT_IGNORE_VERMAGIC))
return -EINVAL;
err = kernel_read_file_from_fd(fd, &hdr, &size, INT_MAX,
READING_MODULE);
if (err)
return err;
info.hdr = hdr;
info.len = size;
return load_module(&info, uargs, flags);
}
```
在這段程式碼中實際用於載入模組的函式為 `load_module`, 在 `load_module` 函式中調用大量函式對模組進行檢查與載入的工作, 例如函式 `check_module_license_and_versions` 便會檢查模組的 license 與版本是否符合內核規範, 當 license 不符合規範時內核會給出 `module license taints kernel.` 警告,
* **當我們透過 `insmod` 去載入一個核心模組時，為何 `module_init` 所設定的函式得以執行呢？Linux 核心做了什麼事呢？**
巨集 `module_init` 定義於 `linux/include/linux/module.h` 中, 定義如下:
```c=
#define module_init(initfn) \
static inline initcall_t __maybe_unused __inittest(void) \
{ return initfn; } \
int init_module(void) __copy(initfn) __attribute__((alias(#initfn)));
```
* `__maybe_unused`
定義
```c=
#define __maybe_unused __attribute__((__unused__))
```
[index-unused-function-attribute](https://gcc.gnu.org/onlinedocs/gcc/Common-Function-Attributes.html#index-unused-function-attribute)
> This attribute, attached to a function, means that the function is meant to be possibly unused. GCC does not produce a warning for this function.
* __copy
[index-copy-function-attribute](https://gcc.gnu.org/onlinedocs/gcc/Common-Function-Attributes.html#index-copy-function-attribute)
> The copy attribute applies the set of attributes with which function has been declared to the declaration of the function to which the attribute is applied. The attribute is designed for libraries that define aliases or function resolvers that are expected to specify the same set of attributes as their targets.
* alias
[index-alias-function-attribute](https://gcc.gnu.org/onlinedocs/gcc/Common-Function-Attributes.html#index-alias-function-attribute)
> The alias attribute causes the declaration to be emitted as an alias for another symbol, which must be specified.
根據上述內容可知在巨集 `module_init(initfn)` 中將符號 `init_module` 設為 `initfn` 的別名, 亦即調用函式 `init_module` 相當於調用函式 `initfn`
除了 `fibdrv.c` 外, 編譯器還生成了 `fibdrv.mod.c`, 其中的 `__this_module` 結構使得內核能夠設定初始化函數以及結束時執行函數, 其定義如下:
```c=
__visible struct module __this_module
__attribute__((section(".gnu.linkonce.this_module"))) = {
.name = KBUILD_MODNAME,
.init = init_module,
#ifdef CONFIG_MODULE_UNLOAD
.exit = cleanup_module,
#endif
.arch = MODULE_ARCH_INIT,
};
```
* `__visible`
定義於 `linux/include/linux/compiler_attributes.h` 中
```
# define __visible __attribute__((__externally_visible__))
```
[externally_visible](https://gcc.gnu.org/onlinedocs/gcc/Common-Function-Attributes.html#index-externally_005fvisible-function-attribute)
> This attribute, attached to a global variable or function, nullifies the effect of the -fwhole-program command-line option, so the object remains visible outside the current compilation unit.
因此 `__this_module` 初始化 `struct module` 結構並設定 `init` , `exit` 等函數指針, 當內核在 `lond_module` 函式中調用 `setup_load_info` 函式時, 會讀取 section `.gnu.linkonce.this_module` 並設定 `info->mod` 結構, `setup_load_info` 在 `linux/kernel/module.c` 中, 相關程式碼如下
```c=
static int setup_load_info(struct load_info *info, int flags)
{
...
info->index.mod = find_sec(info, ".gnu.linkonce.this_module");
if (!info->index.mod) {
pr_warn("%s: No module found in object\n",
info->name ?: "(missing .modinfo name field)");
return -ENOEXEC;
}
/* This is temporary: point mod into copy of data. */
info->mod = (void *)info->hdr + info->sechdrs[info->index.mod].sh_offset;
...
return 0;
}
```
當 `load_module` 函式執行到最後會調用 `do_init_module` 函式, 在此函式中又調用 ` do_one_initcall` 執行巨集 `module_init` 設定的函式, `do_init_module` 在 `linux/kernel/module.c` 中, 相關程式碼如下
```c=
static noinline int do_init_module(struct module *mod)
{
...
/* Start the module */
if (mod->init != NULL)
ret = do_one_initcall(mod->init);
if (ret < 0) {
goto fail_free_freeinit;
}
...
return ret;
}
```
* 試著執行 `$ readelf -a fibdrv.ko`, 觀察裡頭的資訊和原始程式碼及 `modinfo` 的關聯，搭配上述提問，解釋像 `fibdrv.ko` 這樣的 ELF 執行檔案是如何「植入」到 Linux 核心
```
$ readelf -a fibdrv.ko
...
區段標頭：
[號] 名稱 類型 位址 偏移量
大小 全體大小 旗標 連結 資訊 對齊
...
[ 5] .init.text PROGBITS 0000000000000000 000001dd
0000000000000153 0000000000000000 AX 0 0 1
...
[13] .modinfo PROGBITS 0000000000000000 00000540
00000000000000ec 0000000000000000 A 0 0 8
...
符號表「.symtab」含有 60 個條目：
編號: 值 大小 類型 約束 版本 索引名稱
...
30: 0000000000000000 12 OBJECT LOCAL DEFAULT 13 __UNIQUE_ID_version26
31: 000000000000000c 36 OBJECT LOCAL DEFAULT 13 __UNIQUE_ID_description25
32: 0000000000000030 46 OBJECT LOCAL DEFAULT 13 __UNIQUE_ID_author24
33: 000000000000005e 21 OBJECT LOCAL DEFAULT 13 __UNIQUE_ID_license23
...
47: 0000000000000000 339 FUNC GLOBAL DEFAULT 5 init_module
```
觀察符號表中的 `索引名稱` 欄位, 可以看到使用巨集 `MODULE_LICENSE`, `MODULE_AUTHOR`, `MODULE_DESCRIPTION`, `MODULE_VERSION` 定義的符號 `__UNIQUE_ID_version26` , `__UNIQUE_ID_description25` , `__UNIQUE_ID_author24` , `__UNIQUE_ID_license23` 皆放置於 section `.modinfo` 中, 使用巨集 `module_init` 定義的符號 `init_module` 則放置於 section `.init.text` 中, 當 `load_module` 函式執行到最後會調用 `do_init_module` 函式, 在此函式中又調用 ` do_one_initcall` 執行巨集 `module_init` 設定的函式
* **這個 `fibdrv` 名稱取自 Fibonacci driver 的簡稱，儘管在這裡顯然是為了展示和教學用途而存在，但針對若干關鍵的應用場景，特別去撰寫 Linux 核心模組，仍有其意義，請找出 Linux 核心的案例並解讀。提示: 可參閱 [Random numbers from CPU execution time jitter](https://lwn.net/Articles/642166/)**
在 `linux/crypto/` 中, `jitterentropy.c` 與 `jitterentropy-kcapi.c` 可被編譯為內核模組, 其目的是用於產生隨機程度足夠高的亂數, 以改善在原本版本的 `deterministic random bit generator (DRBG) ` 在特定場景下無法產生有效隨機數的情況
* **查閱 [ktime 相關的 API](https://www.kernel.org/doc/html/latest/core-api/timekeeping.html)，並找出使用案例 (需要有核心模組和簡化的程式碼來解說)**
在 `linux/crypto/jitterentropy-kcapi.c` 中, 函式 `jent_get_nstime` 用於衡量程式執行過程消耗的時間, 當 high resolution timer 不可用時, 此函式轉而調用函式 `ktime_get_ns` 以取得足夠精度的時間, 以下為相關程式碼與註解
```c=
/*
* Obtain a high-resolution time stamp value. The time stamp is used to measure
* the execution time of a given code path and its variations. Hence, the time
* stamp must have a sufficiently high resolution.
*
* Note, if the function returns zero because a given architecture does not
* implement a high-resolution time stamp, the RNG code's runtime test
* will detect it and will not produce output.
*/
void jent_get_nstime(__u64 *out)
{
__u64 tmp = 0;
tmp = random_get_entropy();
/*
* If random_get_entropy does not return a value, i.e. it is not
* implemented for a given architecture, use a clock source.
* hoping that there are timers we can work with.
*/
if (tmp == 0)
tmp = ktime_get_ns();
*out = tmp;
}
```
* **[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` 中用了幾個函數將 `fibdrv` 設定為一個 `char device` , 使其在 `/dev` 文件夾下以文件的形式呈現, 從而使得 `client.c` 能夠以讀寫普通文件的方式與 `fibdrv` 通信, 這一系列操作中涉及幾個相關數據結構, 分別為 `struct class` , `struct device`
* `struct class`
定義在 `linux/include/device.h` 中 , 依據相關註解可知 `struct class` 結構用於提供對設備更高階層的抽象描述, 關注設備能做什麼而忽略其實線細節, 以下為程式碼中關於 `struct class` 的註釋
> A class is a higher-level view of a device that abstracts out low-level
implementation details. Drivers may see a SCSI disk or an ATA disk, but,
at the class level, they are all simply disks. Classes allow user space
to work with devices based on what they do, rather than how they are
connected or how they work.
* `struct cdev`
定義在 `linux/include/cdev.h` 中, 用於描述 `char device` 相關連的設備並定義能夠執行的文件系統操作
* `struct device`
定義在 `linux/include/device.h` 中 , 依據相關註解可知 `struct device` 結構用於描述設備的底層實現, 其中包含了更多設備相關的細節, 以下為程式碼中關於 `struct device` 的註釋
> At the lowest level, every device in a Linux system is represented by an
instance of struct device. The device structure contains the information
that the device model core needs to model the system. Most subsystems,
however, track additional information about the devices they host. As a
result, it is rare for devices to be represented by bare device structures;
instead, that structure, like kobject structures, is usually embedded within
a higher-level representation of the device.
而 `fibdrv` 能夠被 userspace 當作一個文件讀寫的關鍵在於函式 `device_create` 中, 在此函式中經過如下函式調用 `device_create` -> `device_create_vargs` -> `device_create_groups_vargs` -> `device_add` -> `device_create_file` -> `sysfs_create_file` -> `sysfs_create_file_ns` -> `sysfs_add_file_mode_ns` -> `__kernfs_create_file` -> `kernfs_new_node` -> `__kernfs_new_node` 後最終在文件系統中創建 `fibdrv` 節點, 至此 `fibdrv` 對於 userspace 而言與一個普通文件無異
相似的範例可參看 `/dev/null` 的實現, 定義在 `linux/drivers/mem.c` 中, 其定義的操作如下:
```
static const struct file_operations null_fops = {
.llseek = null_lseek,
.read = read_null,
.write = write_null,
.read_iter = read_iter_null,
.write_iter = write_iter_null,
.splice_write = splice_write_null,
};
```
* **注意到 `fibdrv.c` 存在著 `DEFINE_MUTEX`, `mutex_trylock`, `mutex_init`, `mutex_unlock`, `mutex_destroy` 等字樣，什麼場景中會需要呢？撰寫多執行緒的 userspace 程式來測試，觀察 Linux 核心模組若沒用到 mutex，到底會發生什麼問題**
使用簡單的程式碼測試, 程式碼如下 :
```c=
#include <pthread.h>
#include <stdio.h>
#include <unistd.h>
int count;
void *child(void *data) {
int i;
for (i = 0; i < 100000; i++) {
count++;
}
pthread_exit(NULL);
}
int main() {
pthread_t t;
pthread_create(&t, NULL, child, NULL);
for (int i = 0; i < 100000; ++i) {
count--;
}
pthread_join(t, NULL);
printf("count : %d\n", count);
return 0;
}
```
執行多次進行比較
```SHELL
$ gcc pthread1.c -o pthread1 -lpthread
$ ./pthread1
count : -99950
$ ./pthread1
count : -41318
$ ./pthread1
count : -100000
$ ./pthread1
count : 11264
$ ./pthread1
count : 91732
```
可以發現由於對變數 count 進行加減法操作並非原子操作, 因此結果無法預測, 此時加入 mutex 進行測試, 程式碼如下:
```c=
#include <pthread.h>
#include <stdio.h>
#include <unistd.h>
int count;
pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER;
void *child(void *data) {
int i;
for (i = 0; i < 100000; i++) {
pthread_mutex_lock(&mutex);
count++;
pthread_mutex_unlock(&mutex);
}
pthread_exit(NULL);
}
int main() {
pthread_t t;
pthread_create(&t, NULL, child, NULL);
for (int i = 0; i < 100000; ++i) {
pthread_mutex_lock(&mutex);
count--;
pthread_mutex_unlock(&mutex);
}
pthread_join(t, NULL);
printf("count : %d\n", count);
return 0;
}
```
執行多次進行比較
```SHELL
$ gcc pthread2.c -o pthread2 -lpthread
$ ./pthread2
count : 0
$ ./pthread2
count : 0
$ ./pthread2
count : 0
$ ./pthread2
count : 0
$ ./pthread2
count : 0
$ ./pthread2
count : 0
```
加上 mutex 後結果即符合預期, 因為在 mutex 保護的範圍內一次只能有一個執行序對變量 count 進行操作, 因此可知在 linux 中若沒有 mutex, 當有多個執行序對同一個變量進行操作時, 執行結果不確定
* **許多現代處理器提供了 [clz / ctz](https://en.wikipedia.org/wiki/Find_first_set) 一類的指令，你知道如何透過演算法的調整，去加速 [費氏數列](https://hackmd.io/s/BJPZlyDSV) 運算嗎？請列出關鍵程式碼並解說**
## fibdrv
* 原始版本消耗時間測量
在 `client` 使用 `clock_gettime` 函式測量 `read` 系統調用消耗的時間, 在 module 中使用 `ktime_get_real` 函式測量計算 fibonacci 消耗的時間, 由得到的結果可以大略推測從 kernel space 傳回 user space 大概需要 500 ns 的時間
* 使用 recursive fast doubling
本來預期能夠有教好的性能, 然而卻發現在性能上相比原來的版本並沒有比較好, 還需要利用其他方式測試以找出性能不佳的原因
* 嘗試增加大數運算
先嘗試定義了 128 bit 的大數, 定義如下:
```c=
typedef struct fib_num {
uint32_t word[4]; // 128 bit
} f_num_t;
```
接著實現相關的加法函數, 由於在此 128 bit 的數字拆開為四個 32 bit 的數字存放, 因此在執行加減法運算時需要特別注意進位問題, 相關實現如下:
```c=
static void fib_num_add(f_num_t *f1, f_num_t *f2, f_num_t *r)
{
int i;
uint32_t tmp;
uint32_t carry;
if (!f1 || !f2 || !r)
return;
carry = 0;
for (i = 0; i < 4; i++) {
tmp = f1->word[i] + f2->word[i] + carry;
if (tmp < f1->word[i] || tmp < f2->word[i])
carry = 1;
else
carry = 0;
r->word[i] = tmp;
}
}
```
由於原本版本的 fibonacci 算法只需要使用加法, 因此使用 128 bit 數實現原本的算法並測量時間消耗
由於進行了更多的運算, 可見時間消耗比原本版本高出許多, 而 128 bit 的無符號數可以計算至 fibonacci 數列第 186 項
Sign in with Wallet
Connect another wallet