2024q1 Homework6 (integration)

contributed by < fatcatorange >

自我檢查清單：

Linux 核心模組運作原理

檢查 linux 核心版本：

$ uname -r
6.5.0-27-generic

掛載 fibdrv 模組:

Passed [-]
f(93) fail
input: 7540113804746346429
expected: 12200160415121876738

linux 核心是如何讀取到那些作者等訊息？

以 author 為例，透過巨集會把

MODULE_AUTHOR("National Cheng Kung University, Taiwan");

展開成：

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 區段：

.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:

#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 來註冊：

int register_chrdev (unsigned int   major,
                     const char *   name,
                     const struct file_operations * fops);

第一個參數是指定的號碼，如果是 0 則會動態分配，後面就是裝置的名稱和他的 file_operations 結構。

在 file_operations 結構中，可以分配要給使用者的一些函式，如 read、write。

#include <linux/fs.h>
static struct file_operations simple_driver_fops = 
{
    .owner   = THIS_MODULE,
    .read    = device_file_read,
};

例如上面這樣， device_file_read 是自定義的函式。

而要取消註冊時，則使用：

unregister_chrdev(device_file_major_number, device_name);

printk

和 printf 非常類似，但可以指定這個輸出的等級，例如較嚴重可使用 emerg ，不嚴重可用 info等

嘗試製作

我嘗試透過 教學網站 建立簡單的 driver 來練習，完成後卻發現在 client 端無法開啟 driver:

fd = open(SIMPLE_DRIVER_DEV, O_RDWR);
printf(SIMPLE_DRIVER_DEV);
if (fd == -1) {
    printf("Can not open file\n");
    return -1;
}//進入這裡

我嘗試檢查後發現，模組應該有成功加入，但 /dev/ 下卻沒有資料夾：

透過 lsmod 有看到我的模組

lsmod
Module                  Size  Used by
driver_mod             12288  0

但使用 ls -l /dev/driver_mod 卻找不到

參考網上解法 ，我直接建立一個資料夾給這個 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 分配的空間。

假如想要逐字讀寫的話，可以用這種方法：

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);
}

在模組內的讀可以使用

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 的操作

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 來動態分配一個號碼。

kmalloc:參考文章，在 kernel 分配較小的區塊時，應使用 kmalloc，較大則使用 vmalloc，因為 vmalloc 可以分配不連續的實體記憶體空間，分配大空間時較容易成功。

運作原理：

首先，在 user space 的程式會先產生 1000 個亂數並透過 read 來讓目前的 driver 操作：

for (size_t i = 0; i < n_elements; i++) 
        inbuf[i] = rand() % n_elements;

ssize_t r_sz = read(fd, inbuf, size);

在 sort_mod 中，定義了：

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

void *sort_buffer = kmalloc(size, GFP_KERNEL);
len = copy_from_user(sort_buffer, buf, size);

在大多數情況下，kmalloc 的第二個參數都使用 GFP_KERNEL，當分配空間失敗時可能進入睡眠直到有空間可使用，但少數情況例外，例如在不可中斷的工作中。 參考此處

接下來就進入 sort 的操作：

sort_main(sort_buffer, size / es, es, num_compare);

es 代表一個元素大小，這裡是 int。

sort_main

真正的 sort 在 sort_impl.c 中的 sort_main，首先分配了一塊空間給

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:

static inline void swapfunc(char *a, char *b, int n, int swaptype)

其中 n 是一個元素的大小。

假設有不對其的，執行 swapcode(char, a, b, n)

在 swapcode 中，有以下：

long i = (n) / sizeof(TYPE); 

如果是 TYPE 是 char，則 i 為 4，將 parmi 和 parmj 逐 byte 進行交換，而如果 TYPE 是 8、12…bytes，則以 4bytes 為單位搬移。

在後續的 init_qsort 中，會透過

INIT_WORK(&q->w, qsort_algo);

加入工作。

如果 qsort_algo 需要一些參數，就是放在 qsort 這個結構體中(內容可以隨便放，但裡面一定要有 struct work_struct 這個欄位），qsort_algo 在執行時會傳入執行到的 work_struct，這時使用 container_of 就可以取出 qsort 內的資料。

qsort_algo

首先，如果長度 < 7 ，改為使用 insertion sort:

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 輸入值決定要用的方法:

ssize_t r_sz = write(fd, argv[1], strlen(argv[1]));

sort_mod 中透過 sort_write 讀取使用者傳入的資料並將 sort_type 修改為對應的值:

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 已經被修改：

[274720.917870] sort type: 1

接下來就可以開始引入。

lib/sort

這是 linux 核心使用的排序演算法，以 heap_sort 為基礎，此處參考去年 kart81604 的期末專題，首先先確認此算法要傳入的參數，在 lib/sort 中有說明：

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。

檢查對齊狀況：

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。

加入時間檢測：

首先此處我要加入運行時間的檢測，考量到不管使用何種演算法都會進入

sort_main(sort_buffer, size / es, es, num_compare);

我加入 ktime_get 來獲取時間資訊並回傳給 user space ，再透過 user space 程式進行寫入：

    kt = ktime_get();

    sort_main(sort_buffer, size / es, es, num_compare);

    kt = ktime_sub(ktime_get(), kt);

user space:

    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 次，樣本數逐步增加：

i=1000

while [ $i -le 10000 ]; do
    sudo ./user default $i
    sudo ./user heapsort $i

    ((i+=10))
done

不知為何輸入到 2030 時就會當掉，因此只先獲取到 2000 的資料：

不管如何執行，只要到 2030 必定會當掉，而且即使透過 pidof sort 指令也找不到正在使用的 pid，但要重新載入或卸載模組卻會顯示：

rmmod: ERROR: Module sort is in use

只要當機就只能重新開機，而且必須強致關機，一般關機會卡在關機畫面..。

因為問題似乎出在原始的 ksort 中，我首先先拿掉 ksort，嘗試只執行 heapsort，但還是只要執行到 2030 必定當機，而反過來只執行 ksort 也一樣，而跳過 2030 直接從 2040 開始執行又可以正常運作。

我嘗試跳過 2030 ，結果執行到 7580 時，又會發生一樣的情形。

檢查 printk 的內容，發現以下：

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 偶爾會出現非常差的效能