# 2024q1 Homework6 (integration)
contributed by < [marvin0102](https://github.com/marvin0102) >
:::danger
留意空白字元，注意細節。
:::
## 開發環境
```shell
$ gcc --version
gcc (Ubuntu 11.4.0-1ubuntu1~22.04) 11.4.0
$lscpu
Architecture: x86_64
CPU op-mode(s): 32-bit, 64-bit
Address sizes: 43 bits physical, 48 bits virtual
Byte Order: Little Endian
CPU(s): 12
On-line CPU(s) list: 0-11
Vendor ID: AuthenticAMD
Model name: AMD Ryzen 5 1600 Six-Core Processor
CPU family: 23
Model: 1
Thread(s) per core: 2
Core(s) per socket: 6
Socket(s): 1
Stepping: 1
Frequency boost: enabled
CPU max MHz: 3200.0000
CPU min MHz: 1550.0000
BogoMIPS: 6387.26
```
## 自我檢查清單
- [x] 研讀前述 Linux 效能分析 描述，在自己的實體電腦運作 GNU/Linux，做好必要的設定和準備工作 → 從中也該理解為何不希望在虛擬機器中進行實驗;
- 檢查目前的 linux 版本：
```c
$ uname -r
6.5.0-27-generic
```
- 安裝 linux-headers 套件
```c
$ sudo apt install linux-headers-`uname -r`
```
- 確認 linux-headers 套件已正確安裝於開發環境
```c
$ dpkg -L linux-headers-`uname -r` | grep "/lib/modules/.*/build"
/lib/modules/6.5.0-27-generic/build
```
掛載核心模組測試流程
```c
$ make -C /lib/modules/`uname -r`/build M=`pwd` modules
$ sudo insmod hello.ko
$ sudo rmmod hello
$ sudo dmesg
...
[28745.089937] Hello. world
[28787.389700] Goodbye, cruel world
```
- [x] 閱讀〈Linux 核心模組運作原理〉並對照 Linux 核心原始程式碼 (v6.1+)，解釋 insmod 後，Linux 核心模組的符號 (symbol) 如何被 Linux 核心找到 (使用 List API)、MODULE_LICENSE 巨集指定的授權條款又對核心有什麼影響 (GPL 與否對於可用的符號列表有關)，以及藉由 strace 追蹤 Linux 核心的掛載，涉及哪些些系統呼叫和子系統？
以 `fibdrv.c` 為例：
```c
MODULE_LICENSE("Dual MIT/GPL");
```
從 [include/linux/module.h](https://elixir.bootlin.com/linux/v4.18/source/include/linux/module.h#L199) 可以得到聚集 `MODULE_LICENSE` 的定義，展開可得：
```c
/*
* The following license idents are currently accepted as indicating free
* software modules
*
* "GPL" [GNU Public License v2 or later]
* "GPL v2" [GNU Public License v2]
* "GPL and additional rights" [GNU Public License v2 rights and more]
* "Dual BSD/GPL" [GNU Public License v2
* or BSD license choice]
* "Dual MIT/GPL" [GNU Public License v2
* or MIT license choice]
* "Dual MPL/GPL" [GNU Public License v2
* or Mozilla license choice]
*
* The following other idents are available
*
* "Proprietary" [Non free products]
*
* There are dual licensed components, but when running with Linux it is the
* GPL that is relevant so this is a non issue. Similarly LGPL linked with GPL
* is a GPL combined work.
*
* This exists for several reasons
* 1. So modinfo can show license info for users wanting to vet their setup
* is free
* 2. So the community can ignore bug reports including proprietary modules
* 3. So vendors can do likewise based on their own policies
*/
#define MODULE_LICENSE("Dual MIT/GPL") MODULE_INFO(license, "Dual MIT/GPL")
```
從註解可以得知， 目前提供的自由軟體模組的 license 有 `GPL`、`BSD`、`MIT`、`MPL`，而 `Proprietary` 代表非自由軟體，其中 [GPL](https://en.wikipedia.org/wiki/GNU_General_Public_License) 根據法規與技術的更新，分為 `GPL` 、 `GPL v2` 、 `GPL and additional rights` ， `MODULE_LICENSE` 的作用主要為： 1. 在 `modinfo` 中顯示，讓使用者知道此模組為自由軟體模組 2. 讓開發者社群可以忽略 `Proprietary` 相關的錯誤訊息 3. 廠商可以根據自己的政策做同樣的事情
:::danger
為何 Linux 核心模組的掛載跟授權條款有關？
:::
通過 strace 查看執行 `insmod fibdrv.ko` 時，的過程有哪些系統呼叫被執行:
```
$ sudo strace insmod fibdrv.ko
execve("/usr/sbin/insmod", ["insmod", "fibdrv.ko"], 0x7ffe3ce19e58 /* 18 vars */) = 0
brk(NULL) = 0x5e048d034000
arch_prctl(0x3001 /* ARCH_??? */, 0x7ffeca28ff70) = -1 EINVAL (不適用的引數)
mmap(NULL, 8192, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0) = 0x7382fb5fe000
access("/etc/ld.so.preload", R_OK) = -1 ENOENT (沒有此一檔案或目錄)
openat(AT_FDCWD, "/etc/ld.so.cache", O_RDONLY|O_CLOEXEC) = 3
newfstatat(3, "", {st_mode=S_IFREG|0644, st_size=63067, ...}, AT_EMPTY_PATH) = 0
mmap(NULL, 63067, PROT_READ, MAP_PRIVATE, 3, 0) = 0x7382fb5ee000
close(3) = 0
...
close(3) = 0
getcwd("/home/marvin/linux2024/fibdrv", 4096) = 30
newfstatat(AT_FDCWD, "/home/marvin/linux2024/fibdrv/fibdrv.ko", {st_mode=S_IFREG|0664, st_size=274792, ...}, 0) = 0
openat(AT_FDCWD, "/home/marvin/linux2024/fibdrv/fibdrv.ko", O_RDONLY|O_CLOEXEC) = 3
read(3, "\177ELF\2\1", 6) = 6
lseek(3, 0, SEEK_SET) = 0
newfstatat(3, "", {st_mode=S_IFREG|0664, st_size=274792, ...}, AT_EMPTY_PATH) = 0
mmap(NULL, 274792, PROT_READ, MAP_PRIVATE, 3, 0) = 0x7382fb4ae000
finit_module(3, "", 0) = 0
munmap(0x7382fb4ae000, 274792) = 0
close(3) = 0
exit_group(0) = ?
+++ exited with 0 +++
```
從訊息中可以得知， `insmod` 大量的使用了 `openat` 、 `read` 、 `newfstatat` 、 `mmap` 、 `close` 等系統呼叫。
其中，系統呼叫 `finit_module` 被定義於 [kernel/module.c](https://elixir.bootlin.com/linux/v4.18/source/kernel/module.c#L3855) 中，通過呼叫 `kernel_read_file_from_fd` 將 ELF 檔 `fibdrv.ko` 打開並且呼叫 `load_module` 。
`load_module` 同樣被定義於 [kernel/module.c](https://elixir.bootlin.com/linux/v4.18/source/kernel/module.c#L3855) 中，從程式碼可以發現，核心先做 `layout_and_allocate` 為載入的 module 進行記憶體配置。而後在呼叫 `do_init_module` 對 module 做初始化。最後在函式 `do_one_initcall` 中，呼叫 init_function 為核心模組進行真正的初始化的工作。
在核心初始化的過程中， `load_module` 呼叫了函式 `simplify_symbols`:
```c
static int load_module(struct load_info *info, const char __user *uargs,
int flags)
{
struct module *mod;
long err;
char *after_dashes;
...
/* Fix up syms, so that st_value is a pointer to location. */
err = simplify_symbols(mod, info);
if (err < 0)
goto free_modinfo;
...
return do_init_module(mod);
}
```
`simplify_symbols` 被定義於 [kernel/module.c](https://elixir.bootlin.com/linux/v4.18/source/kernel/module.c#L2237) 中:
```c
/* Change all symbols so that st_value encodes the pointer directly. */
static int simplify_symbols(struct module *mod, const struct load_info *info)
{
Elf_Shdr *symsec = &info->sechdrs[info->index.sym];
Elf_Sym *sym = (void *)symsec->sh_addr;
unsigned long secbase;
unsigned int i;
int ret = 0;
const struct kernel_symbol *ksym;
...
case SHN_UNDEF:
ksym = resolve_symbol_wait(mod, info, name);
/* Ok if resolved. */
if (ksym && !IS_ERR(ksym)) {
sym[i].st_value = ksym->value;
break;
}
...
return ret;
}
```
從註解可以得知， `simplify_symbols` 從模組的 ELF 中取出需要尋找的 external symbols ， 隨後在函式 `resolve_symbol_wait` 中呼叫 `resolve_symbol` 。 `resolve_symbol` 通過呼叫 `find_symbol` 尋找哪些符號屬於該模組，而後使用 `add_module_usage` 將符號加入模組。
其中， `find_symbol` 搜尋使用到 `list_for_each_entry_rcu` 走訪 `mod` 雙向鏈結串列。
:::danger
使用精準的術語
:::
- [x] 閱讀《The Linux Kernel Module Programming Guide》(LKMPG) 並解釋 simrupt 程式碼裡頭的 mutex lock 的使用方式，並探討能否改寫為 lock-free;
在 `simrupt` 中，函式 `simrupt_read` 的作用為將 buffer 中的資料輸送到 userspace ， 若 `rx_fifo` 為空，則呼叫 `wait_event_interruptible` 將程式加入 wait queue 中。
其中使用到了 `mutex_lock_interruptible` ， `mutex_lock_interruptible` 被定義在 [kernel/locking/mutex.c](https://elixir.bootlin.com/linux/latest/source/kernel/locking/mutex.c#L982) 中：
```c
/**
* mutex_lock_interruptible() - Acquire the mutex, interruptible by signals.
* @lock: The mutex to be acquired.
*
* Lock the mutex like mutex_lock(). If a signal is delivered while the
* process is sleeping, this function will return without acquiring the
* mutex.
*
* Context: Process context.
* Return: 0 if the lock was successfully acquired or %-EINTR if a
* signal arrived.
*/
int __sched mutex_lock_interruptible(struct mutex *lock)
{
might_sleep();
if (__mutex_trylock_fast(lock))
return 0;
return __mutex_lock_interruptible_slowpath(lock);
}
```
從註解中可以得知， `mutex_lock_interruptible` 可以在接收到中斷信號後，直接返回 `-EINTR` ，<s>避免浪費 CPU 資源</s> ，若成功獲得 lock 則返回 0。
:::danger
並非如此，詳閱 LKMPG 和 Linux 文件。
:::
:::info
在 LKMPG 中提到：
>We could have used `wait_event` instead, but that would have resulted in extremely angry users whose Ctrl+c’s are ignored.
`wait_event_interruptible` 與 `wait_event` 的差別在於， `wait_event` 會忽略 ctl+c signal ，因此需要返回 `-EINTR` 讓使用者可以中止行程。
因此我們可以知道，返回 `-EINTR` 的作用是行程在進入 critical section 前，允許使用者中止行程或是接收 interrupt signal。
:::
`mutex_lock` 與 `mutex_lock_interruptible` 主要的差別在未能獲得 lock 時所呼叫的函式 `__mutex_lock_common` 中的參數 `state` 被設定為 `uninterrputible` 或是 `interruptible` ，即是否能被中斷。
另外 `wait_event_interruptible` 會將 process 加入 wait queue `rx_wait` 中，並且使 process 進入 sleep 狀態，只有滿足條件 `kfifo_len(&rx_fifo)` 不為 0 時才會被喚起。
- [ ] 探討 Timsort, Pattern Defeating Quicksort (pdqsort) 及 Linux 核心 lib/sort.c 在排序過程中的平均比較次數，並提供對應的數學證明;
- [ ] 研讀 CMWQ (Concurrency Managed Workqueue) 文件，對照 simrupt 專案的執行表現，留意到 worker-pools 類型可指定 "Bound" 來分配及限制特定 worker 執行於指定的 CPU，Linux 核心如何做到？CMWQ 關聯的 worker thread 又如何與 CPU 排程器互動？
- [ ] 解釋 xoroshiro128+ 的原理 (對照〈Scrambled Linear Pseudorandom Number Generators〉論文)，並利用 ksort 提供的 xoro 核心模組，比較 Linux 核心內建的 /dev/random 及 /dev/urandom 的速度，說明 xoroshiro128+ 是否有速度的優勢？其弱點又是什麼？
## 從 LKMPG 理解 simrupt 原理
### [simrupt](https://github.com/sysprog21/simrupt/blob/main/simrupt.c)
從 `simrupt_init` 的初始化可以知道， simrupt 為 character device ，作用為不斷循環生成大小為 0x20 ~ 0x7f 的可視字元，並且輸出至 user space 。
字元生成的流程如下:
在函式 `timer_handler` 中，呼叫函式 `process_data` -> `update_simrupt_data` ，函式 `update_simrupt_data` 循環輸出範圍 0x20 ~ 0x7f 中的數值，每次呼叫遞增 1 ，隨後在函式 `fast_buf_put` 將數值存入 Circular buffer `fast_buf` 中，`fast_buf` 做為資料輸入 kfifo `rx_fifo` 的中間緩衝區，最後通過函式 `fast_buf_get` 將數值提出後，在函式 `produce_data` 將資料存入 `rx_fifo` 。
字元輸出的流程如下:
在讀取 character device 時，會呼叫 `simrupt_fops.read` ，也就是函式 `simrupt_read` ，在函式 `simrupt_read` 中，先是會使用 mutex lock 確認沒有其他 process 進入 critical section ，隨後通過 `kfifo_to_user` 將 `rx_fifo` 中的字元輸出至 userspace ，當 `rx_fifo` 為空時，則呼叫 `wait_event_interruptible` 使 precoss 進入 sleep 狀態。
### class
在註冊 character device 時，使用到 `device_create` 函式，在 LKMPG 中提到:
>6.3 Registering A Device:
> we can have our driver make the device file using the device_create function after a successful registration and device_destroy during the call to cleanup_module .
`device_create` 被定義在 [drivers/base/core.c](https://elixir.bootlin.com/linux/latest/source/drivers/base/core.c#L4378)，作用是建立一個 device 並且註冊於 sysfs 中。其中 class 的作用為何呢?
從註解中可以知道，引數 class 為 device 所需註冊之類的指標，此 class 經由 `class_create` 函式建立。`struct class *class_create` 在 [include/linux/device/class.h](https://elixir.bootlin.com/linux/latest/source/include/linux/device/class.h#L228) 中被定義，同樣被定義在此檔案的還有資料結構 `class` 。
```c
/**
* ...
* 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.
*/
```
從資料結構 `class` 的註解中可以知道，`class` 為低層級實作細節之高層級抽象，做用為讓使用者可以根據 device 的功能進行使用，而非根據 device 的連接或運作方式。
### vmalloc
simrupt 中記憶體配置使用的是 `vmalloc` 而非 LKMPG 中提到的 `kmalloc` 。
`kmalloc` 被定義在 [include/linux/slab.h](https://elixir.bootlin.com/linux/latest/source/include/linux/slab.h#L581) ，而 `vmalloc` 則是定義於 [mm/vmalloc.c](https://elixir.bootlin.com/linux/latest/source/mm/vmalloc.c#L3416) 中:
```c
/**
* kmalloc - allocate kernel memory
* @size: how many bytes of memory are required.
* @flags: describe the allocation context
*
* kmalloc is the normal method of allocating memory
* for objects smaller than page size in the kernel.
* ...
* /
```
```c
/**
* vmalloc - allocate virtually contiguous memory
* @size: allocation size
*
* Allocate enough pages to cover @size from the page level
* allocator and map them into contiguous kernel virtual space.
* ...
* /
```
比較之後可以發現， `kmalloc` 負責在 kernal 中配置大小小於 page size 的記憶體，而 `vmalloc` 則可以透過虛擬記憶體的方式，配置數量滿足 size 大小的 pages，並且映射到連續的核心虛擬空間。
### interrupt
在 simrupt 中，使用到 workqueue 、 tesklet 等 interrupt handler。
在[ linux-insides](https://0xax.gitbooks.io/linux-insides/content/Interrupts/linux-interrupts-9.html) 中有介紹到:
>Interrupts may have different important characteristics and there are two among them:
>- Handler of an interrupt must execute quickly;
>- Sometime an interrupt handler must do a large amount of work.
中斷有可能會有兩中不同的特性，有時些中斷需要盡快處理，如:硬體中斷，然而有些中斷需要做的事非常多，因此可能會占用較長的 CPU 時間，需要同時滿足這兩個特性非常困難。
在 LKMPG 中有提到:
>15.1 Interrupt Handlers:
>Linux kernel solves the problem by splitting interrupt handling into two parts. The first part executes right away and masks the interrupt line. Hardware interrupts must be handled quickly, and that is why we need the second part to handle the heavy work deferred from an interrupt handler.
解決辦法為將中斷分為兩種，需要即時處理的中斷具有較高的權重，被歸類為 top half ，而工作比較繁重，需要佔有較多 CPU 時間的中斷，被歸類為 button half ，此類中斷會被推遲處理，可以稱為 deferred interrupts。
>There are three types of deferred interrupts in the Linux kernel:
>- softirqs;
>- tasklets;
>- workqueues;
#### softirq
目前 linux bottom half handlers 的實作都是基於 ksoftirqd ，每一個行程都一個 `ksoftirqd/n` 其中 `n` 為行程編號，可以經由命令 `systemd-cgls -k | grep ksoft` 查看。
[ linux-insides](https://0xax.gitbooks.io/linux-insides/content/Interrupts/linux-interrupts-9.html) 中有提到:
>Interrupts and Interrupt Handling. Part 9.:
>Softirqs are determined statically at compile-time of the Linux kernel and the open_softirq function takes care of softirq initialization.
`open_softirq` 在 [kernel/softirq.c](https://elixir.bootlin.com/linux/latest/source/kernel/softirq.c#L698) 可以找到其定義:
```C
void open_softirq(int nr, void (*action)(struct softirq_action *))
{
softirq_vec[nr].action = action;
}
```
目前 linux 定義了 10 種類型的 softirq，`softirq_vec` 則包含其中一種 :
```c
static struct softirq_action softirq_vec[NR_SOFTIRQS] __cacheline_aligned_in_smp;
DEFINE_PER_CPU(struct task_struct *, ksoftirqd);
const char * const softirq_to_name[NR_SOFTIRQS] = {
"HI", "TIMER", "NET_TX", "NET_RX", "BLOCK", "IRQ_POLL",
"TASKLET", "SCHED", "HRTIMER", "RCU"
};
```
我們可以透過命令 `cat /proc/softirqs ` 查看:
#### tasklets
[linux-insides](https://0xax.gitbooks.io/linux-insides/content/Interrupts/linux-interrupts-9.html) 中寫到:
>tasklets are softirqs that can be allocated and initialized at runtime and unlike softirqs, tasklets that have the same type cannot be run on multiple processors at a time.
我們知道， softirq 只能在 compile-time 時被決定，而 tasklet 則可以在 runtime 時配置及初始化。
從 [kernel/softirq.c](https://elixir.bootlin.com/linux/latest/source/kernel/softirq.c#L893) 中的函式 `softirq_init` 可以知道， tasklet 可以藉由兩種 softirqs 建立:
- TASKLET_SOFTIRQ
- HI_SOFTIRQ
```c
void __init softirq_init(void)
{
int cpu;
for_each_possible_cpu(cpu) {
per_cpu(tasklet_vec, cpu).tail =
&per_cpu(tasklet_vec, cpu).head;
per_cpu(tasklet_hi_vec, cpu).tail =
&per_cpu(tasklet_hi_vec, cpu).head;
}
open_softirq(TASKLET_SOFTIRQ, tasklet_action);
open_softirq(HI_SOFTIRQ, tasklet_hi_action);
}
```
[kernel/softirq.c](https://elixir.bootlin.com/linux/latest/source/kernel/softirq.c#L706) 中，資料結構 `tasklet_head` 負責描述 tasklet 串列:
```c
struct tasklet_head {
struct tasklet_struct *head;
struct tasklet_struct **tail;
};
```
串列中的tasklet，經由資料結構 `task_struct` 表達:
```c
struct tasklet_struct
{
struct tasklet_struct *next;
unsigned long state;
atomic_t count;
bool use_callback;
union {
void (*func)(unsigned long data);
void (*callback)(struct tasklet_struct *t);
};
unsigned long data;
};
```
可以看到，此資料結構內容包含:
- 指向下個 tasklet 的指標
- tasklet 的狀態
- tasklet 是否為 active
- tasklet 的 callback function
- callback function 所需之參數
可以同過聚集 `DECLARE_TASKLET(name, func, data)
` 、 `DECLARE_TASKLET_DISABLED(name, func, data)` 或是函式 `tasklet_init` 進行初始化。
而我們可以通過下列這三個函式標示該 tasklet 準備執行:
```c
void tasklet_schedule(struct tasklet_struct *t);
void tasklet_hi_schedule(struct tasklet_struct *t);
void tasklet_hi_schedule_first(struct tasklet_struct *t);
```
三者的實作方法相似，差別在於優先權的高低而已。
#### Workqueues
同樣以 [linux-insides](https://0xax.gitbooks.io/linux-insides/content/Interrupts/linux-interrupts-9.html) 理解 workqueue :
>Workqueue functions run in the context of a kernel process, but tasklet functions run in the software interrupt context. This means that workqueue functions must not be atomic as tasklet functions.
workqueue 與 tasklet 主要的差別在於，workqueue 函式不能為 atomic 。
workqueue 中的 work 使用 `work_struct` 表現，定義於 [include/linux/workqueue_types.h](https://elixir.bootlin.com/linux/latest/source/include/linux/workqueue_types.h#L16) :
```c
struct work_struct {
atomic_long_t data;
struct list_head entry;
work_func_t func;
#ifdef CONFIG_LOCKDEP
struct lockdep_map lockdep_map;
#endif
};
```
其中 `func` 為被排程於 workqueue 中的函式， `data` 為 `func` 所需要的參數。
linux 核心使用 `kworker` 執行續用於排程 workqueue，作用相當於 `ksoftirqd` 之於 softirqs， 我們可以透過命令 `systemd-cgls -k | grep kworker` 查看:
linux 核心使用巨集 `DECLARE_WORK` 建立 work :
```c
#define DECLARE_WORK(n, f) \
struct work_struct n = __WORK_INITIALIZER(n, f)
```
接著使用函式 `queue_work` 將 work 加入 workqueue 中:
```c
static inline bool queue_work(struct workqueue_struct *wq,
struct work_struct *work)
{
return queue_work_on(WORK_CPU_UNBOUND, wq, work);
}
```
### timer
simrupt 使用 timer_list 模擬 IRQ，根據 [Linux Device Drivers, 3rd Edition](https://www.makelinux.net/ldd3/chp-7-sect-4.shtml) 的敘述:
>A kernel timer is a data structure that instructs the kernel to execute a user-defined function with a user-defined argument at a user-defined time.
在 [include/linux/timer_types.h](https://elixir.bootlin.com/linux/latest/source/include/linux/timer_types.h#L8) 中可以找到資料結構 `timer_list` 的定義:
```c
struct timer_list {
/*
* All fields that change during normal runtime grouped to the
* same cacheline
*/
struct hlist_node entry;
unsigned long expires;
void (*function)(struct timer_list *);
u32 flags;
#ifdef CONFIG_LOCKDEP
struct lockdep_map lockdep_map;
#endif
};
```
其中，expire 為設定的時間，function 為超過時間時所執行的 call back function 。
巨集 `timer_setup` 用於初始化 `timer_list` ， `timer_list` 在使用前必須先使用巨集 `DEFINE_TIMER()` 或是 `timer_setup()` 初始化。
函式 `mod_timer` 用於更新 `timer_list` 的觸發時間，作用相當於
del_timer(timer); timer->expires = expires; add_timer(timer)
函式 `del_timer_sync` 用於刪除 `timer_list` ，與 `del_timer` 的差別在於，當 `del_timer_sync` 返回時，保證 `timer_list` 不會在任何 CPU 上執行。
#### jiffies
在 wikipedia 可以看見敘述:
>Jiffy is an informal term for any unspecified short period of time
同樣 linux 核心也有相似的定義，在 [linux-insides](https://0xax.gitbooks.io/linux-insides/content/Timers/linux-timers-1.html) 中提到:
>There is global variable with the jiffies which holds the number of ticks that have occurred since the system booted.
在形成初始化的時候，全域變數 jiffies 會被設為 0 ，並且在 timer interrupt 觸發時遞增。
## 作業主題二
### 繪製棋盤
在一開始繪製棋盤的時候，是使用 `cir_buff` 將棋盤一個字元一個字元送至 `rx_fifo` 中。但考慮到棋盤所需的資料很少，因此改為直接將棋盤輸入至 `rx_fifo` 中，再交由 `rx_fifo` 將棋盤送至 userspace。
使用函式 `update_simrupt_data()` 模擬下棋，將棋盤 `table[N_GRIDS]` 中的格子陸續下滿。
```
| O | |
----------------
| | |
----------------
| | |
----------------
| | |
----------------
| O | O |
----------------
| | |
----------------
| | |
----------------
| | |
----------------
| O | O | O
----------------
| | |
----------------
| | |
----------------
| | |
----------------
```
[commit d7362cf](https://github.com/sysprog21/simrupt/commit/d7362cf28dee35c7823f282e33452a224742a9d9)
### AI 對弈
做為測試，先只將 MCTS 移入，並且作為兩個 ai 的下棋演算法。在測試時，嘗試使用函式 `get_random_bytes()` 作亂數生成，但此函式不能再 wait 狀態，因此會導致程式出現錯誤。
```c
int i = 0;
get_random_bytes(&i, sizeof(i));
int move = moves[i % n_moves];
```
因此維持 PRNG 作為亂數產生器。
首先，先測試 MCTS 在 linux module 中是否能正常對弈，因此將兩個 ai 寫在同一個 while 迴圈中，透過 `turn = turn == 'O'? 'X' : 'O';` 交換對弈。
```
...
| | |
----------------
| | |
----------------
| | |
----------------
| | |
----------------
| | |
----------------
| | |
----------------
| | | X
----------------
| | |
----------------
| | |
----------------
| | |
----------------
| | | X
----------------
| | |
----------------
| | |
----------------
| | |
----------------
| | | X
----------------
| | |
----------------
| | |
----------------
| | |
----------------
| | | X
----------------
| | |
----------------
| | |
----------------
| | |
----------------
| | | X
----------------
| | |
----------------
| | |
----------------
| | O |
----------------
| | | X
----------------
| | |
----------------
| | |
----------------
| | O |
----------------
| | | X
----------------
| | |
----------------
| | |
----------------
| | O |
----------------
| | | X
----------------
| | |
----------------
| | |
----------------
| | O |
----------------
| | | X
----------------
| | |
----------------
| | |
----------------
| | O |
----------------
| | | X
----------------
| | | X
----------------
| | |
----------------
| | O |
----------------
| | | X
----------------
| | | X
----------------
| | |
----------------
| O | O |
----------------
| | | X
----------------
| | | X
----------------
| | |
----------------
| O | O |
----------------
| | | X
----------------
| | | X
----------------
| | |
----------------
| O | O | X
----------------
| | | X
----------------
| | | X
----------------
```
從結果可以看出，ai 可以正常對弈，但由於對弈演算法的執行速度較慢，無法在一個 interrupt 之內跑完，因此會出現棋盤的顯示比下棋速度快的情況。
接這是將 ai 的對弈從 while 迴圈轉換成函式加入 workqueue 中進行對弈，一開始單純將 while 迴圈中的任務摘分出來，寫成函式。
```diff
static void Player_I_task(struct work_struct *w){
// if(turn != 'O') return;
/* This code runs from a kernel thread, so softirqs and hard-irqs must
* be enabled.
*/
WARN_ON_ONCE(in_softirq());
WARN_ON_ONCE(in_interrupt());
int move = 0;
- mutex_lock(&consumer_lock);
move = mcts(table, turn);
if (move != -1) {
table[move] = turn;
+ WRITE_ONCE(table[move], turn);
}
turn = turn == 'O'? 'X':'O';
+ WRITE_ONCE(turn, turn == 'O'? 'X':'O');
- mutex_unlock(&consumer_lock);
pr_info("------- first ------");
pr_info("simrupt: [CPU#%d] play game\n", smp_processor_id());
}
```
為了避免出現 race condition ，因此加入 mutex lock ，但因為 workqueue 中的 work 為並行，容易出現 dead lock ，因此先改為 `WRITE_ONCE` 做測試。
[commit ee4ce37](https://github.com/sysprog21/simrupt/commit/ee4ce37a3601ddd3a66b3e5ca54ed96ad6494670)
在成功使兩個 ai 對弈後，發現 cpu 的使用比起將兩個 ai 寫在同一個 while 迴圈的版本還要多上不少，從 `dmesg` 發現，因為使用 `timer_handler` 將 ai 對弈的程式不斷加入 workqueue 中，但演算法的運算過於緩慢，無法一個interrupt 內完成，導致 workqueue 中的 `work` 不斷堆積。
解決方法為，將 `Player_I_task` 、 `Player_II_task` 中加入 while 迴圈，使兩程式不斷相互執行對弈，而 `timer_handler` 的功能從將程式加入 workqueue 中改為檢查對弈是否結束。
```diff
static void Player_I_task(struct work_struct *w)
{
...
int move;
+ while (check_win(table) == ' ') {
if (turn == 'O') {
move = mcts(table, turn);
if (move != -1) {
WRITE_ONCE(table[move], turn);
}
WRITE_ONCE(turn, 'X');
pr_info("simrupt: [CPU#%d] -------- player I game\n",
smp_processor_id());
smp_wmb();
+ process_data();
}
+ }
}
...
static void timer_handler(struct timer_list *__timer)
{
ktime_t tv_start, tv_end;
...
- if (win == ' ') {
- play_game();
- }
- process_data();
+ if (win != ' ') {
+ pr_info("simrupt: %c win!!!", win);
+ }
...
}
```
[commit f00b3ab](https://github.com/sysprog21/simrupt/commit/f00b3ab5772d414e37feea7a9163073f2fcfeb08)
### 使用者介面
使用 ioctl 作為 kernel module 的交互工具，在 LKMPG 中的範例程式要求在使用 ioctl 時，需要固定 character device 的 major number ，原因是當我們在使用 ioctl 時，會需要定義 ioctl numbers 來區分讀取、寫入等不同的命令，但 `__IOW` 、 `__IOR` 等等定義 ioctl numbers 的巨集需要三個引數，其中引數 `type` 的作用是用於區分不同 device 的 ioctl 命令，因此不能與其他 device 重疊，這也是為甚麼使用 major number 作為引數 `type` 的原因。
`__IOW` 、 `__IOR` 等等定義 ioctl numbers 的巨集 [include/uapi/asm-generic/ioctl.h](https://elixir.bootlin.com/linux/latest/source/include/uapi/asm-generic/ioctl.h#L87):
```c
/*
* Used to create numbers.
*
* NOTE: _IOW means userland is writing and kernel is reading. _IOR
* means userland is reading and kernel is writing.
*/
#define _IO(type,nr) _IOC(_IOC_NONE,(type),(nr),0)
#define _IOR(type,nr,size) _IOC(_IOC_READ,(type),(nr),(_IOC_TYPECHECK(size)))
#define _IOW(type,nr,size) _IOC(_IOC_WRITE,(type),(nr),(_IOC_TYPECHECK(size)))
#define _IOWR(type,nr,size) _IOC(_IOC_READ|_IOC_WRITE,(type),(nr),(_IOC_TYPECHECK(size)))
#define _IOR_BAD(type,nr,size) _IOC(_IOC_READ,(type),(nr),sizeof(size))
#define _IOW_BAD(type,nr,size) _IOC(_IOC_WRITE,(type),(nr),sizeof(size))
#define _IOWR_BAD(type,nr,size) _IOC(_IOC_READ|_IOC_WRITE,(type),(nr),sizeof(size))
```
從引數 `type` 的作用可以只到，我們只需要設定一個不與其他 device 重疊的數值就可以了，這樣不但可以使 device 可以動態配置 major number ，也不會造成不同 device 的 ioctl 命令重疊的問題。
使用者層級的程式主要做的事情為，接收兩種命令 `'^Q'` 、 `'^P'` ，其中命令 `'^Q'` 的作用是終止遊戲，而命令 `'^p'` 的作用是暫停棋局的輸出，但對弈仍會繼續。
使用 RawMode 來改變程式在接收 stdin 的輸入時的設定:
```c
void enableRawMode()
{
tcgetattr(STDIN_FILENO, &E.orig_termios);
struct termios raw = E.orig_termios;
atexit(disableRawMode);
raw.c_iflag &= ~(IXON);
raw.c_lflag &= ~(ECHO | ICANON);
raw.c_cc[VMIN] = 0;
raw.c_cc[VTIME] = 1;
tcsetattr(STDIN_FILENO, TCSAFLUSH, &raw);
}
```
其中 `raw.c_iflag &= ~(IXON)` 、 `raw.c_lflag &= ~(ECHO | ICANON)` 的作用為禁用特殊字元 `'^Q'` `'^P'` 的功能以及不再印出輸入的字元，` raw.c_cc[VMIN] = 0` `raw.c_cc[VTIME] = 1` 的作用是使程式不再等待來自 stdin 的輸入進而使程式無法繼續運行。
使用者層級的程式透過 while 迴圈中的 iotcl 命令接收來自 device 訊息，也就是對弈的過程，並將其印出，在接收到命令 `'^Q'` 後，跳出迴圈並且關閉 device 。
命令 `'^p'` 的作用是暫停棋局的輸出，但如果使 device 停止輸出， iotcl 會因為需要等待來自 device 對弈過程而使程式無法順利執行。因此，在使用者層級的程式接收到命令 `'^p'` 時，將其傳入 device 中，而 device 在接收到此命令後，將停止把新的棋局寫入紀錄棋盤的 `board_buff` 中，使得 device 輸出的仍會是舊的棋盤。
成果影片
{%youtube YkvxmbDwzo4 %}
[commit 2bc85f2](https://github.com/sysprog21/simrupt/commit/2bc85f2391ff91c67c86e7c0c3adb653cac7a79d)
Sign in with Wallet
Connect another wallet