# 2024q1 Homework6 (integration)
contributed by <`ShawnXuanc`>
## 自我檢查
### [MODULE_LICENSE](https://elixir.bootlin.com/linux/v4.18/source/include/linux/module.h#L205)
條款包含 `GPL`, `GPL v2`, `GPL and additional rights`, `Dual BSD/GPL`, `Dual MIT/GPL`, `Dual MPL/GPL`, `Proprietary` 七種不同的類型
GPL 為自由軟體許可協議條款其特點包含，可以自由使用、自由修改、共享衍生產品
前面兩者為 GNU 授權許可第一版以及第二版，而第三個為 GPL 加上額外的條款，後面有加上 Dual 代表兩種授權方式，最後的 Proprietary 代表非自由即專有軟體，由原作者保留所有著作權利
### [insmod](https://man7.org/linux/man-pages/man8/insmod.8.html)
功能為將模組插入到 linux 核心之中，可搭配 [dmesg](https://man7.org/linux/man-pages/man1/dmesg.1.html) 使用查看 [kernel ring buffer](https://hackmd.io/@sysprog/concurrency-ringbuffer) 的內容
symbol 代表 linux 核心中的函式名稱以及變數名稱
insmod 將未處理符號的符號鏈結到模組的符號表，而當模組被載入時所有被導出的符號都會被載入到符號表，當模組在使用自己的函式時不需要進行任何的符號導出，而當模組要使用到外部的模組的函式時則需要使用 [EXPORT_SYMBOL](https://lwn.net/Articles/674303/)
而藉由上述 `EXPORT_SYMBOL` 可以知道 linux 核心中將符號的結構定義為 `kernel_symbol`，並可以在 [module/internal.h](https://elixir.bootlin.com/linux/latest/source/kernel/module/internal.h#L35) 中可以發現使用 `struct find_symbol_arg` 為 `find_symbol` 傳入值
在 [kernel/module/main.c](https://elixir.bootlin.com/linux/latest/source/kernel/module/main.c) 中 使用 `symsearch` 結構來表示符號表 start 代表表的開始位址而 stop 代表結束的位址，以及包含 licence，在 /module/main.c 內存在 `find_symbol` 的函式，其中藉由 `find_exported_symbol_in_section` 使用 `bsearch` 來進行符號的查找
在 `find_symbol` 中有使用到 `list_for_each_entry_rcu` ， [RCU](https://hackmd.io/@sysprog/linux-rcu) 為 linux 核心中的同步機制，適用於頻繁的讀取，不頻繁寫入的情況，藉著寬限期的概念來達成同步的處理
```graphviz
digraph G {
{
rank = "same"
rankdir = "LR"
head [label="head", shape="square"]
n1 [label="5", shape="square"]
n2 [label="1", shape="square"]
n3 [label="4", shape="square"]
NULL[label="NULL", shape="plain"]
head->n1->n3
n2->n3->NULL
}
{rank = "sink" p}
p[label="p",shape="plain"]
p->n2
}
```
而在例子中可以看到若多個執行緒在執行則當節點 `1` 被寫入端的執行緒移除時，而其他讀取中的執行緒可能可以看到節點 `1` 也可能不行會存在兩個不同的版本，此時若貿然將節點刪除就可能發生錯誤，因此需要寬限期的存在等所有執行緒都離開後不讓其他執行緒再次存取，最後才可以將節點釋放
可以到 /proc/kallsyms 查看 kernel 的符號
### strace 涉及的系統呼叫
```shell
$ strace insmod fibdrv.ko
```
使用命令 [strace](https://linux.die.net/man/1/strace) 可以查看所使用的系統呼叫
```
execve("/usr/sbin/insmod", ["insmod", "fibdrv.ko"], 0x7ffdd59ef898 /* 41 vars */) = 0
brk(NULL) = 0x601b7b5a7000
arch_prctl(0x3001 /* ARCH_??? */, 0x7ffdab58ca00) = -1 EINVAL (Invalid argument)
mmap(NULL, 8192, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0) = 0x77ead1c9c000
...
finit_module(3, "", 0) = -1 EPERM (Operation not permitted)
write(2, "insmod: ERROR: could not insert "..., 74insmod: ERROR: could not insert module fibdrv.ko: Operation not permitted
) = 74
munmap(0x77ead1b49000, 274784) = 0
close(3) = 0
exit_group(1)
```
在 `init_module` 系統呼叫將 ELF image 載入到 kernel space 並利用 `alias` 為模組命名
在新版本中的 `idempotent_init_module` 可以看到 `init_module_from_file` 呼叫 `load_module` 使用 `do_init_module` ，最後由 `do_init_module` 呼叫`do_one_init_call` 內部的 `fn()` 為核心模組中真正做初始化的的部分
## 閱讀[《The Linux Kernel Module Programming Guide》](https://sysprog21.github.io/lkmpg/) 並解釋 simrupt 程式碼裡頭的 mutex lock 的使用方式
### Device
`simrup` 為 `character device` ，而另外一種類型為 `block device` 其差異在於 `block device` 有一個接受請求的緩求區，並且只能以 `block` 作為單位接收以及回傳資料而 `charater device` 並不受限於大小，可以使用下方命令查看輸出第一個字符為 c 還是 b 來查看設備文件的類型
```shell
$ ls -l /dev
```
`character device` 使用 [sturct file_operations](https://git.kernel.org/pub/scm/linux/kernel/git/stable/linux.git/tree/include/linux/fs.h) 定義設備的操作使用指標指向其功能函式，在 `simrupt` 中為 `simrupt_fops`
```c
static const struct file_operations simrupt_fops = {
.read = simrupt_read,
.llseek = no_llseek,
.open = simrupt_open,
.release = simrupt_release,
.owner = THIS_MODULE,
};
```
而註冊方式為使用 `alloc_chrdev_region(&dev_id, 0, NR_SIMRUPT, DEV_NAME)` 動態分配設備的主要編號，並使用 `cdev_init(&simrupt_cdev, &simrupt_fops)` 進行設備初始化並將裝置加入到系統中使用 `cdev_add(&simrupt_cdev, dev_id, NR_SIMRUPT)`
### Tasklet
中斷分成兩個部分分別為 `top half` 以及 `bottom half`， `top half` 主要是硬體做快速回應處理重要的部分，而為了要避免中斷時期再次發生中斷因此會進行 disable interrupt，當前面 `top half` 處理完重要的中斷任務後將中斷重新打開， `bottom half` 時會將尚未完成被延遲的中斷部分交由 kernel thread 進行處理
kernel thread 由 kernel 創建只在 kernel space 活動，為可排程且 preemptive ，每一個 cpu 的核心會有一個運行 `bottom half` 部分 `softirqd` 的 kernel thread 為 worker thread，即用來處理中斷請求，而對於這樣的安排每個 cpu 由一個 worker thread 來負責即是為了要避免 migration 的問題
使用命令查看 cpu 核心上的 ksoftirqd，前述的 k 為命名傳統
```shell
$ ps -r | grep softirqd
```
`bottom half` 即為被延遲的部分，linux 中三種延遲中斷的處理機制
1. softirqs
2. tasklets
3. workqueues
相同類型的 tasklet 不能同時執行，即執行相同處理函式，而 tasklet 被 cpu 排程過後就只會待在同一個 cpu 上執行
而對於上述處理機制中的前面兩者 `softirq` 以及 `tasklet` 的呼叫時機有兩個第一個為在 `interrupt context` 結束之前會由 linux 核心進行呼叫此時若要處理的 `softirq` 以及 `tasklet` 工作量在可負荷範圍會直接進行處理，當系統負載較高時才將剩餘的 `softirq` 以及 `tasklet` 加入到排程器中在 `bottom half` 執行
基本使用如下進行初始化
```c
static DECLARE_TASKLET_OLD(mytask, tasklet_fn);
```
將 tasklet 加入
```c
tasklet_schedule(&mytask);
```
移除 tasklet
```c
tasklet_kill(&mytask);
```
在 `simrupt` 使用 `DECLARE_TASKLET_OLD(simrupt_tasklet, simrupt_tasklet_func)` 宣告 tasklet 並指定中斷處理函式，並用 `tasklet_schedule(&simrupt_tasklet)` 將其加入 `kernel thread context` 中，使用 `tasklet_kill(&simrupt_tasklet)` 將其從系統刪除
但是在使用上限制較多，像是不能存取 user space 的資料以及進行 sleep，在有些情況下就無法僅靠 tasklet 就完成所需的工作，所以逐漸使用 `workqueue` 來取代
### CMWQ
workqueue 的作用在於把任務推遲到 kernel thread 去執行而這個 kernel thraed 就稱為 worker thread (一個 processor 有一個 worker thread)
原先的 workqueue 版本，因 single workqueue 的並行等級較低，而 MT workqueue 有嚴重的資源消耗所以 CMWQ 誕生
其特點包含維持了與原先 `workqueue API` 的相容性，並捨棄每個 workqueue 對應一組 `worker-pools`，使所有 workqueue 共享 `per-CPU worker-pools` 並按需求提供並行等級，節省資源的浪費，將 `work-pool` 以及並行等級交由內部調節，api 使用者不用知道細節
worker-pool 分成兩種類型包含 `Bound` 以及 `Unbound` 差異在於前者會綁定特定 CPU 使 worker 執行在指定的 CPU 上，而後者不綁定 CPU 使 thread pool 可以動態的調整
在 CMWQ 中每個函式都會被抽象化為一個 `work item` ，在每一個 work item 中有一個函式指標指向所要執行的任務
linux 核心中的 workqueue 使用 completely fair scheduler (CFS) 來執行，基本宣告如下
```c
static struct workqueue_struct *queue = NULL;
static struct work_struct work;
```
將任務進行初始化，並添加到 workqueue 中
```c
queue = alloc_workqueue("HELLOWORLD", WQ_UNBOUND, 1);
INIT_WORK(&work, work_handler);
queue_work(queue, &work);
```
釋放 workqueue
```c
destroy_workqueue(queue);
```
在 simrupt 中使用 `static struct workqueue_struct *simrupt_workqueue` 建立 workqueue， `alloc_workqueue("simruptd", WQ_UNBOUND, WQ_MAX_ACTIVE)` 在建立時使用 unbound 的 workqueue 即不綁定 cpu 的方式，
以 `DECLARE_WORK(work, simrupt_work_func)` 建立 work item 執行 `simrupt_work_func`，使用 `queue_work(simrupt_workqueue, &work)` 將任務加入到 workqueue 之中
### timer_handler
在 simrupt 中使用此函式來模擬 interrupt 的發生，對於 `top half` 硬體的中斷的部分在函式中使用 `local_irq_disable` 將中斷關閉避免前面所提到當發生中斷時又發生中斷的情況發生
對於延遲中斷的部分使用 process_data 先將資料放入 circular buffer 中，並將處理 softirq 的 simrupt_tasklet 加入到 kernel thread context 中以此任務進行模擬等待 `bottom half` 時進行處理
最後使用 `local_irq_enable` 將中斷再次打開，藉此模擬 top half 的中斷流程
### mutex
`mutex` 確保了多個 process 在同一時間點只能有一個取得資源，且在使用 `mutex` 之下需考慮 `priority inversion` 的情況，像是藉由 `priority inheritance` 來解決，對於 `mutex` 取得以及釋放都必須是同一個 process，而在 linux 核心之中 `mutex` 屬於休眠鎖，若未取得 mutex 及會進入休眠的狀態
在 simrupt 中使用 `read_lock` 以及 `produce_lock`, `consumer_lock` 進行互斥的處理
```c
static DEFINE_MUTEX(read_lock);
static DEFINE_MUTEX(producer_lock);
static DEFINE_MUTEX(consumer_lock)
```
藉由 kernel thread 取得 `circular buffer` 的資料，使用互斥的方式來避免執行緒之間在取得資料時發生問題，即當某個執行緒取得資料時而因為沒有記憶體及時更新導致取得了相同資料
```c
mutex_lock(&consumer_lock);
val = fast_buf_get();
mutex_unlock(&consumer_lock);
```
在前面正確的取得資料之後將資料放入到 kfifo 之中，為了可以在將資料放入 kfifo 時避免其他執行緒也同時將資料放入導致放入相同位置等等的問題，因此這邊也使用了互斥的方式進行處理，避免多個執行緒的交錯順序不一發生問題
```c
mutex_lock(&producer_lock);
produce_data(val);
mutex_unlock(&producer_lock);
```
在進行資料放置以及取出時皆使用了 smp_rmb 以及 smp_wmb 的 `memory barrier` 操作來防止指令被重排而導致執行順序錯誤的問題
使用命令即可查看 kfifo buffer 中被放置的資料，在 `simrupt_read` 使用 kfifo_to_user 將資料複製到 userspace 的緩衝區中
```shell
$ sudo cat /dev/simrupt
```
在 simrupt 中使用 [wiat queue](https://elixir.bootlin.com/linux/latest/source/include/linux/wait.h) 藉由 `wait_event_interruptible(rx_wait, kfifo_len(&rx_fifo))` 讓 `simrupt_read` 中若 xfifo buffer 內如果沒有資料時進入休眠直到 simprupt 中的 `wake_up_interruptible(&rx_wait)` 將 wait queue 中的任務喚醒
```c
static DECLARE_WAIT_QUEUE_HEAD(rx_wait);
```
在 simrupt_read 中使用 [mutex_lock_interruptible(&read_lock)](https://lwn.net/Articles/167034/) 來取得互斥鎖與 `mutex_lock` 的差別在 `mutex_lock_interruptible` 可以被 `signal` 中斷
在此處對 kfifo 將資料複製給 userspace 的動作進行互斥的動作避免資料的錯誤，並使用 `mutex_unlock(&read_lock)` 進行釋放
### lock-free
`lock-free` 為對於系統而言只要時間進行的夠長，至少會有一個執行緒可以進行下去，即程式不會因為某個運行中的執行緒被 lock 住而沒有辦法再執行下去，而對於沒有使用 lock 的程式而言其不一定為 `lock-free` 的程式，因為在某些情況下還是可能造成程式無法運行
對於 simrupt_work_func 中使用互斥鎖保護從 `circular buffer` 取出資料的一致性，使用互斥鎖會使得未取得鎖的執行緒進入休眠，所以可能會導致系統的效率下降，所以可以在對於當要使用到 `circular buffer` 的 `index` 的部分時使用 `atomic` 的 `CAS` 操作來確保 index 的正確性，進而避免使用互斥鎖來達到 `lock-free` 的方式
可以參考 [EFTpool](https://github.com/xhjcehust/LFTPool/blob/master/tpool.c) 在 get_work_concurrently 中的方式
在 linux 核心中進行 [atomic](https://elixir.bootlin.com/linux/latest/source/tools/arch/x86/include/asm/atomic.h#L69) 操作
```c
#define ATOMIC_INIT(i) { (i) }
```
使用 [atomic_cmpxchg](https://www.kernel.org/doc/html/v4.10/core-api/atomic_ops.html) 來進行最小操作，old 跟 v 進行比較若相等即將 v 的值更改為 new
```c
int atomic_cmpxchg(atomic_t *v, int old, int new)
```
Sign in with Wallet
Connect another wallet