owned this note
owned this note
Published
Linked with GitHub
# 2024q1 Homework6 (integration)
contributed by < `fatcatorange` >
## 自我檢查清單：
### Linux 核心模組運作原理
檢查 linux 核心版本：
```shell
$ uname -r
6.5.0-27-generic
```
掛載 fibdrv 模組:
```shell
Passed [-]
f(93) fail
input: 7540113804746346429
expected: 12200160415121876738
```
linux 核心是如何讀取到那些作者等訊息？
以 author 為例，透過巨集會把
```c
MODULE_AUTHOR("National Cheng Kung University, Taiwan");
```
展開成：
```c
static const char __UNIQUE_ID(author)[] \
__used __attribute__((section(".modinfo"), unused, aligned(1))) \
= __stringify(author) "=" "National Cheng Kung University, Taiwan"
```
其中 `__UNIQUE_ID` 會產生不重複的名字（每次遇到 `__COUNTER__ `都會 ＋1)
stringify 換成字串，因此巨集被轉變成：
`static const char 生成的 uniqueid[] "author = National Cheng Kung University, Taiwan"`
因此其被載入 .modinfo 區段：
```shell
.modinfo 區段的內容：
0000 76657273 696f6e3d 302e3100 64657363 version=0.1.desc
0010 72697074 696f6e3d 4669626f 6e616363 ription=Fibonacc
0020 6920656e 67696e65 20647269 76657200 i engine driver.
0030 61757468 6f723d4e 6174696f 6e616c20 author=National
0040 4368656e 67204b75 6e672055 6e697665 Cheng Kung Unive
0050 72736974 792c2054 61697761 6e006c69 rsity, Taiwan.li
0060 63656e73 653d4475 616c204d 49542f47 cense=Dual MIT/G
```
在 init_module 中，自己寫的 init_module 會被取一個自己做的 function 的別名，在系統呼叫 init_module 時也相當於執行自己寫的 init function。
## How to write a simple device driver:
### 基本 module
建立基礎的 module:
```c
#include <linux/init.h>
#include <linux/module.h>
static int my_init(void)
{
return 0;
}
static void my_exit(void)
{
return;
}
module_init(my_init);
module_exit(my_exit);
```
### 註冊
首先要針對這個裝置進行註冊，使用 `register_chrdev` 來註冊：
```c
int register_chrdev (unsigned int major,
const char * name,
const struct file_operations * fops);
```
第一個參數是指定的號碼，如果是 0 則會動態分配，後面就是裝置的名稱和他的 file_operations 結構。
在 file_operations 結構中，可以分配要給使用者的一些函式，如 read、write。
```c
#include <linux/fs.h>
static struct file_operations simple_driver_fops =
{
.owner = THIS_MODULE,
.read = device_file_read,
};
```
例如上面這樣， device_file_read 是自定義的函式。
而要取消註冊時，則使用：
```c
unregister_chrdev(device_file_major_number, device_name);
```
### printk
和 printf 非常類似，但可以指定這個輸出的等級，例如較嚴重可使用 emerg ，不嚴重可用 info等
### 嘗試製作
我嘗試透過 [教學網站](https://meetonfriday.com/posts/62f55520/) 建立簡單的 driver 來練習，完成後卻發現在 client 端無法開啟 driver:
```c
fd = open(SIMPLE_DRIVER_DEV, O_RDWR);
printf(SIMPLE_DRIVER_DEV);
if (fd == -1) {
printf("Can not open file\n");
return -1;
}//進入這裡
```
我嘗試檢查後發現，模組應該有成功加入，但 /dev/ 下卻沒有資料夾：
透過 lsmod 有看到我的模組
```shell
lsmod
Module Size Used by
driver_mod 12288 0
```
但使用 ls -l /dev/driver_mod 卻找不到
參考[網上解法](https://www.apriorit.com/dev-blog/195-simple-driver-for-linux-os) ，我直接建立一個資料夾給這個 driver:
`mknod /dev/driver_mod c 510 0`
最後調整一下讀寫權限，就可以成功開啟：
```
sudo chmod o+w /dev/simple-driver
```
### read
在用 driver 時是在 kernel mode， 不能直接把讀到的東西給 user mode，因此要透過 copy_to_user 把在 kernel mode 中分配到的空間內的資料丟給 user mode 分配的空間。
假如想要逐字讀寫的話，可以用這種方法：
```c
for(int i = 0;i < 10; i++) {
ret = read(fd, readbuf + i, 1);
if (ret < 0)
printf("Read file fail\n");
else
printf("App read data: %s\n", readbuf);
}
```
在模組內的讀可以使用
```c
static ssize_t chrdevbase_read(struct file *filp, char *buf, size_t length, loff_t* offset)
{
int ret = 0;
printk(KERN_INFO "chrdevbase_read\n");
//printk(KERN_INFO "length: %zu, offset: %lld\n", length, *offset);
memcpy(readbuf, kerneldata, sizeof(kerneldata));
ret = copy_to_user(buf, readbuf + *offset, length);
if (ret == 0) {
printk("kernel send data: %s\n", readbuf);
} else {
/* error handle */
}
*offset += length;
return length;
}
```
offset 是偏移量，例如要讀取第五個字，就把偏移量 +5 ，所以這裡可以看到每次讀取完後，程式就會把 offset 加上 size_t(要讀取的字數)。
buf 則是傳入的使用者分配的記憶體，注意不可以直接對這塊空間操作，要使用 copy_to_user。
`copy_to_user` 中，`readbuf + *offset` 就設定了要從哪裡開始讀取，並透過 copy_to_user 來把資料複製給 user_space 的使用者。
### write
可以透過類似的方法完成 write 的操作
```c
static ssize_t chrdevbase_write(struct file *filp, const char *buf, size_t len, loff_t* offset)
{
int ret = 0;
printk(KERN_INFO "chrdevbase_write\n");
ret = copy_from_user(writebuf + *offset, buf, len);
if (ret == 0) {
printk("kernel receive data: %s\n", writebuf);
} else {
/* error handle */
}
printk(KERN_INFO "%s\n", writebuf);
*offset += len;
return len;
}
```
## ksort
編譯：
```
Sorting succeeded!
sudo ./test_xoro
n_bytes=0 n_bytes_read=0 value=0000000000000000
n_bytes=1 n_bytes_read=1 value=000000000000005f
n_bytes=2 n_bytes_read=2 value=000000000000ed8e
n_bytes=3 n_bytes_read=3 value=0000000000747c6a
n_bytes=4 n_bytes_read=4 value=00000000c61be1dd
n_bytes=5 n_bytes_read=5 value=000000f069befa4a
n_bytes=6 n_bytes_read=6 value=0000ebab275f98f0
n_bytes=7 n_bytes_read=7 value=0042569408ac9f4b
n_bytes=8 n_bytes_read=8 value=16b355d705d7d6d7
n_bytes=9 n_bytes_read=8 value=0b7f14b4fc108855
make rmmod
make[1]: 進入目錄「/home/jason/linux-2024/lab0-c/ksort」
make[1]: 離開目錄「/home/jason/linux-2024/lab0-c/ksort」
```
好像沒看到兩次綠色的 pass?
```
cat /sys/class/sort/sort/dev
```
中， 510:0 是裝置的識別號碼，前面是 major, 後面是 minor，這可以固定，但如果這個號碼已經被佔用會返回 error，或者也可以透過在 `register_chrdev` [傳入 0 來動態分配一個號碼](https://tldp.org/LDP/lkmpg/2.6/html/x569.html)。
`kmalloc:`參考[文章](https://hackmd.io/@sysprog/linux-memory)，在 kernel 分配較小的區塊時，應使用 kmalloc，較大則使用 vmalloc，因為 vmalloc 可以分配不連續的實體記憶體空間，分配大空間時較容易成功。
### 運作原理：
首先，在 user space 的程式會先產生 1000 個亂數並透過 read 來讓目前的 driver 操作：
```c
for (size_t i = 0; i < n_elements; i++)
inbuf[i] = rand() % n_elements;
ssize_t r_sz = read(fd, inbuf, size);
```
在 sort_mod 中，定義了：
```c
static const struct file_operations fops = {
.read = sort_read,
.write = sort_write,
.open = sort_open,
.release = sort_release,
.owner = THIS_MODULE,
};
```
因此，我們檢查 sort_read 來觀察 user space 使用 read 會發生什麼：
首先程式先分配了一塊給 kernel space 的空間 sort_buffer ，並使用 copy_from_user 來複製資料給 sort_buffer
```c
void *sort_buffer = kmalloc(size, GFP_KERNEL);
len = copy_from_user(sort_buffer, buf, size);
```
:::info
在大多數情況下，kmalloc 的第二個參數都使用 GFP_KERNEL，當分配空間失敗時可能進入睡眠直到有空間可使用，但少數情況例外，例如在不可中斷的工作中。 參考[此處](https://www.kernel.org/doc/html/next/translations/zh_CN/core-api/memory-allocation.html)
:::
接下來就進入 sort 的操作：
```c
sort_main(sort_buffer, size / es, es, num_compare);
```
es 代表一個元素大小，這裡是 int。
#### sort_main
真正的 sort 在 sort_impl.c 中的 sort_main，首先分配了一塊空間給
```c
struct qsort {
struct work_struct w;
struct common *common;
void *a;
size_t n;
};
```
並且宣告了一個 common，裡面的 es 和 cmp 就是傳入的參數，而 swaptype 則較特別，要檢查一個 element 的 size 是否和陣列開頭位址是否為 sizeof(long) 的倍數，這應是在檢查對齊，有下面三種狀況：
1. 位址 或 element size 不對齊： swaptype = 2
2. 都對齊且 es 大小為 4 : swaptype = 0
3. 其他情況（都對齊但 es 大小不為 4 ，可能 8、12...）： swaptype = 1
> 為何要針對這些狀況設定不同的 swaptype?
觀察 swaptype 的功能，狀況 0 時做的就是進行最普通的 swap，如果是另外兩種情況，進行 swapfunc:
```c
static inline void swapfunc(char *a, char *b, int n, int swaptype)
```
其中 n 是一個元素的大小。
假設有不對其的，執行 `swapcode(char, a, b, n)`
在 swapcode 中，有以下：
```c
long i = (n) / sizeof(TYPE);
```
如果是 TYPE 是 char，則 i 為 4，將 parmi 和 parmj 逐 byte 進行交換，而如果 TYPE 是 8、12...bytes，則以 4bytes 為單位搬移。
在後續的 init_qsort 中，會透過
```c
INIT_WORK(&q->w, qsort_algo);
```
加入工作。
> 如果 qsort_algo 需要一些參數，就是放在 qsort 這個結構體中(內容可以隨便放，但裡面一定要有 struct work_struct 這個欄位），qsort_algo 在執行時會傳入執行到的 work_struct，這時使用 container_of 就可以取出 qsort 內的資料。
#### qsort_algo
首先，如果長度 < 7 ，改為使用 insertion sort:
```c
if (n < 7) {
for (pm = (char *) a + es; pm < (char *) a + n * es; pm += es) // 從二個元素開始
for (pl = pm; pl > (char *) a && CMP(thunk, pl - es, pl) > 0;
pl -= es) // 根據比較參數往前 swap
q_swap(pl, pl - es);
return;
}
```
否則的話:
pm 為 `pm = (char *) a + (n / 2) * es;`，這應是指向陣列中間的位址。
pl 為 `pl = (char *) a;` ，陣列開頭位址。
pn 為 `pn = (char *) a + (n - 1) * es;` ，陣列尾端位址。
假如 n > 40:
設 n 為 50，則設定一變數 d 為 50/8 * es， 即 6 * es
也就是說：
pl 改為 (陣列開頭、陣列第 6 格、陣列第 12 格) 的中間值的位址
pm 改為 (陣列第 25 格、陣列第 19 格 、 陣列第 31 格) 的中間值的位址
pn 改為 (陣列第 37 格、陣列第 43 格 、 陣列第 49 格) 的中間值的位址
然後，pm 再改為這三者的中間值。
這麼做應是在避免一直取到過大或過小值，導致 quicksort 效果不佳。
接下來，陣列第一格和 pm 交換， pa、pb 被設定為第二格，pc、pd 被設定為最後一格。
接下來就是執行 quicksort ，需要注意的是，只要有交換行為， swap_cnt 會被設定成 1 ，而如果執行一輪後 swap_cnt 仍為 0 ，則轉為 insertion sort。
另外，過程中會有一個 pa 和 pc 指標，當出現比較結果為 0 時會和 pb 及 pd 交換，初步實驗後發現這樣會讓與 pivot 相同的值集中在陣列開頭與結尾，舉例來說：
陣列內容執行前為：
5 2 4 5 7 9 3 5 2
執行後會變成：
5 5 4 2 2 3 9 7 5
然後程式會再把 5 搬到中間：
3 2 4 2 5 5 5 7 9
最後的結果為：
pa: 指向第三個元素
pb: 指向第七個元素
pc: 指向倒數第二個元素
pd: 指向第六個元素
程式接下來會檢查 pa 和 pb 的距離(7-3) 和 pc 和 pd 的差距 (9-7)
假如兩邊差距都很大 （> 100 ) ，代表還要排很大部份，使用 queue_work 透過並行處理左邊部份，否則的話，使用普通的遞迴方式再呼叫來處李左邊部份。
至於右半部份，則透過修改 a 的位址並使用 goto 直接回到程式處理的地方繼續執行。
目前看完這應就是 quicksort ，但在某些例外狀況改為使用 insertion sort，而在 quicksort 將 pivot 插入到位置後，左半部份如果還有很多要排，就使用 queue_work 進行並行處理，否則使用遞迴呼叫，右半部份則透過 goto 達到類似迭代的效果。
### 引入其他排序演算法
在引入前，需要讓 user space 的用戶可以選擇要使用的排序方法，因為原始程式碼中 user space 的 write 對應到 driver 內的 sort_write，我嘗試透過改寫此函式完成寫入要執行的演算法：
原先想法是透過 user space 輸入數字（如 0 代表預設、1 代表 timsort 等），但在使用時發現一個問題，就是在 kernel space 無法使用一般常用的字串函式 atoi ，儘管在 kernel space 有其他替代方式，但後來還是決定直接根據輸入進來的字串比對就好。
user.c 中透過 argv 輸入值決定要用的方法:
```c
ssize_t r_sz = write(fd, argv[1], strlen(argv[1]));
```
sort_mod 中透過 sort_write 讀取使用者傳入的資料並將 sort_type 修改為對應的值:
```c
static ssize_t sort_write(struct file *file,
const char *buf,
size_t size,
loff_t *offset)
{
void *type_buffer = kmalloc(size, GFP_KERNEL);
int ret = copy_from_user(type_buffer, buf, size);
if(ret == 0) {
if(strcmp("default",type_buffer) == 0) {
sort_type = 0;
}
else if(strcmp("timsort",type_buffer) == 0) {
sort_type = 1;
}
else if(strcmp("??",type_buffer) == 0) {
sort_type = 0;
}
printk(KERN_INFO "sort type: %d", sort_type);
}
return 0;
}
```
使用 `sudo dmesg` 可以看到 sort type 已經被修改：
```shell
[274720.917870] sort type: 1
```
接下來就可以開始引入。
### lib/sort
這是 linux 核心使用的排序演算法，以 heap_sort 為基礎，此處參考去年 [kart81604](https://hackmd.io/@sysprog/B146OVeHn#Linux-%E6%A0%B8%E5%BF%83%E5%B0%88%E9%A1%8C-libsortc) 的期末專題，首先先確認此算法要傳入的參數，在 lib/sort 中有說明：
```c
void sort(void *base, size_t num, size_t size,
cmp_func_t cmp_func,
swap_func_t swap_func)
```
* base 就是要排序的陣列，因此這裡直接傳入 copy_from_user 取得的資料即可。
* num 是資料量，先前已經計算過為 size/es。
* size 是每個資料的大小，就是 es。
* cmp_func 則一樣直接使用 cmp 即可
* swap_func 是使用的 swap 函式，這裡值得注意的是，演算法中原本就會檢查記憶體對齊狀況，如果沒有要特別指定 swap 函式的功能，可以直接傳入 NULL。
檢查對齊狀況：
```c
if (!swap_func) {
if (is_aligned(base, size, 8))
swap_func = SWAP_WORDS_64;
else if (is_aligned(base, size, 4))
swap_func = SWAP_WORDS_32;
else
swap_func = SWAP_BYTES;
}
```
透過 user_space 傳入的參數進行設定，即可使用 sort。
### 加入時間檢測：
首先此處我要加入運行時間的檢測，考量到不管使用何種演算法都會進入
```c
sort_main(sort_buffer, size / es, es, num_compare);
```
我加入 ktime_get 來獲取時間資訊並回傳給 user space ，再透過 user space 程式進行寫入：
```c
kt = ktime_get();
sort_main(sort_buffer, size / es, es, num_compare);
kt = ktime_sub(ktime_get(), kt);
```
user space:
```c
r_sz = read(fd, inbuf, size);
FILE *fp;
fp = fopen("test.txt", "a+");
if (fp == NULL) {
printf("Error opening file!\n");
return 1;
}
if (strcmp(argv[1], "default") == 0) {
fprintf(fp, "%s %ld ", argv[2], r_sz);
} else if (strcmp(argv[1], "bubblesort") == 0) {
fprintf(fp, "%ld\n", r_sz);
} else {
fprintf(fp, "%ld ", r_sz);
}
fclose(fp);
return 0;
```
透過 shell script ，執行 900 次，樣本數逐步增加：
```bash
i=1000
while [ $i -le 10000 ]; do
sudo ./user default $i
sudo ./user heapsort $i
((i+=10))
done
```
不知為何輸入到 2030 時就會當掉，因此只先獲取到 2000 的資料：
不管如何執行，只要到 2030 必定會當掉，而且即使透過 `pidof sort` 指令也找不到正在使用的 pid，但要重新載入或卸載模組卻會顯示：
```c
rmmod: ERROR: Module sort is in use
```
只要當機就只能重新開機，而且必須強致關機，一般關機會卡在關機畫面..。
因為問題似乎出在原始的 ksort 中，我首先先拿掉 ksort，嘗試只執行 heapsort，但還是只要執行到 2030 必定當機，而反過來只執行 ksort 也一樣，而跳過 2030 直接從 2040 開始執行又可以正常運作。
我嘗試跳過 2030 ，結果執行到 7580 時，又會發生一樣的情形。
檢查 printk 的內容，發現以下：
```shell
general protection fault, probably for non-canonical address 0x5e240cad9431b1f9: 0000 [#1] PREEMPT SMP NOPTI
[ 323.468121] CPU: 4 PID: 555 Comm: kworker/4:3 Tainted: G OE 6.5.0-28-generic #29~22.04.1-Ubuntu
[ 323.468126] Hardware name: ASUS System Product Name/TUF GAMING Z790-PLUS WIFI, BIOS 1010 05/04/2023
[ 323.468128] Workqueue: sortq qsort_algo [sort]
[ 323.468139] RIP: 0010:qsort_algo+0x2c/0xbf0 [sort]
[ 323.468148] Code: 44 00 00 55 48 89 f8 48 89 e5 41 57 41 56 41 55 41 54 53 48 83 ec 78 48 8b 5f 20 48 89 bd 60 ff ff ff 4c 8b 68 28 48 8b 40 30 <48> 8b 7b 10 4c 8b 43 08 48 89 9d 68 ff ff ff 8b 1b 48 89 45 88 48
```
執行到 7580 時的結果：
ksort 偶爾會出現非常差的效能
Sign in with Wallet
