2024q1 Homework6 (integration)

contributed by <ShawnXuanc>

自我檢查

MODULE_LICENSE

條款包含 GPL, GPL v2, GPL and additional rights, Dual BSD/GPL, Dual MIT/GPL, Dual MPL/GPL, Proprietary 七種不同的類型

GPL 為自由軟體許可協議條款其特點包含，可以自由使用、自由修改、共享衍生產品

前面兩者為 GNU 授權許可第一版以及第二版，而第三個為 GPL 加上額外的條款，後面有加上 Dual 代表兩種授權方式，最後的 Proprietary 代表非自由即專有軟體，由原作者保留所有著作權利

insmod

功能為將模組插入到 linux 核心之中，可搭配 dmesg 使用查看 kernel ring buffer 的內容

symbol 代表 linux 核心中的函式名稱以及變數名稱

insmod 將未處理符號的符號鏈結到模組的符號表，而當模組被載入時所有被導出的符號都會被載入到符號表，當模組在使用自己的函式時不需要進行任何的符號導出，而當模組要使用到外部的模組的函式時則需要使用 EXPORT_SYMBOL

而藉由上述 EXPORT_SYMBOL 可以知道 linux 核心中將符號的結構定義為 kernel_symbol，並可以在 module/internal.h 中可以發現使用 struct find_symbol_arg 為 find_symbol 傳入值

在 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 為 linux 核心中的同步機制，適用於頻繁的讀取，不頻繁寫入的情況，藉著寬限期的概念來達成同步的處理

而在例子中可以看到若多個執行緒在執行則當節點 1 被寫入端的執行緒移除時，而其他讀取中的執行緒可能可以看到節點 1 也可能不行會存在兩個不同的版本，此時若貿然將節點刪除就可能發生錯誤，因此需要寬限期的存在等所有執行緒都離開後不讓其他執行緒再次存取，最後才可以將節點釋放

可以到 /proc/kallsyms 查看 kernel 的符號

strace 涉及的系統呼叫

$ strace insmod fibdrv.ko

使用命令 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》並解釋 simrupt 程式碼裡頭的 mutex lock 的使用方式

Device

simrup 為 character device ，而另外一種類型為 block device 其差異在於 block device 有一個接受請求的緩求區，並且只能以 block 作為單位接收以及回傳資料而 charater device 並不受限於大小，可以使用下方命令查看輸出第一個字符為 c 還是 b 來查看設備文件的類型

$ ls -l /dev

character device 使用 sturct file_operations 定義設備的操作使用指標指向其功能函式，在 simrupt 中為 simrupt_fops

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 為命名傳統

$ ps -r | grep softirqd

bottom half 即為被延遲的部分，linux 中三種延遲中斷的處理機制

softirqs
tasklets
workqueues

相同類型的 tasklet 不能同時執行，即執行相同處理函式，而 tasklet 被 cpu 排程過後就只會待在同一個 cpu 上執行

而對於上述處理機制中的前面兩者 softirq 以及 tasklet 的呼叫時機有兩個第一個為在 interrupt context 結束之前會由 linux 核心進行呼叫此時若要處理的 softirq 以及 tasklet 工作量在可負荷範圍會直接進行處理，當系統負載較高時才將剩餘的 softirq 以及 tasklet 加入到排程器中在 bottom half 執行

基本使用如下進行初始化

static DECLARE_TASKLET_OLD(mytask, tasklet_fn);

將 tasklet 加入

tasklet_schedule(&mytask);

移除 tasklet

 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) 來執行，基本宣告如下

static struct workqueue_struct *queue = NULL; 
static struct work_struct work;

將任務進行初始化，並添加到 workqueue 中

queue = alloc_workqueue("HELLOWORLD", WQ_UNBOUND, 1); 
INIT_WORK(&work, work_handler); 
queue_work(queue, &work);

釋放 workqueue

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 進行互斥的處理

static DEFINE_MUTEX(read_lock);
static DEFINE_MUTEX(producer_lock);
static DEFINE_MUTEX(consumer_lock)

藉由 kernel thread 取得 circular buffer 的資料，使用互斥的方式來避免執行緒之間在取得資料時發生問題，即當某個執行緒取得資料時而因為沒有記憶體及時更新導致取得了相同資料

mutex_lock(&consumer_lock);
val = fast_buf_get();
mutex_unlock(&consumer_lock);

在前面正確的取得資料之後將資料放入到 kfifo 之中，為了可以在將資料放入 kfifo 時避免其他執行緒也同時將資料放入導致放入相同位置等等的問題，因此這邊也使用了互斥的方式進行處理，避免多個執行緒的交錯順序不一發生問題

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 的緩衝區中

$ sudo cat /dev/simrupt

在 simrupt 中使用 wiat queue 藉由 wait_event_interruptible(rx_wait, kfifo_len(&rx_fifo)) 讓 simrupt_read 中若 xfifo buffer 內如果沒有資料時進入休眠直到 simprupt 中的 wake_up_interruptible(&rx_wait) 將 wait queue 中的任務喚醒

static DECLARE_WAIT_QUEUE_HEAD(rx_wait);

在 simrupt_read 中使用 mutex_lock_interruptible(&read_lock) 來取得互斥鎖與 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 在 get_work_concurrently 中的方式

在 linux 核心中進行 atomic 操作

#define ATOMIC_INIT(i)	{ (i) }

使用 atomic_cmpxchg 來進行最小操作，old 跟 v 進行比較若相等即將 v 的值更改為 new

int atomic_cmpxchg(atomic_t *v, int old, int new)

2024q1 Homework6 (integration)

自我檢查

MODULE_LICENSE

insmod

strace 涉及的系統呼叫

閱讀《The Linux Kernel Module Programming Guide》 並解釋 simrupt 程式碼裡頭的 mutex lock 的使用方式

Device

Tasklet

CMWQ

timer_handler

mutex

lock-free

Read more

Demystifying The Linux Cpu Scheduler

2024q1 Homework5 (assessment)

2024q1 Homework1 (lab0)

2024q1 Homework4 (quiz3+4)

閱讀《The Linux Kernel Module Programming Guide》並解釋 simrupt 程式碼裡頭的 mutex lock 的使用方式