# 2021q1 Homework5 (sort)
contributed by < `RainbowEye0486` >

## 理解程式碼以及程式碼表現

==**`main.c`**==
- `struct file_operations` 是在 `linux/fs.h` 中定義的結構，在寫 linux driver 的時候，對檔案的讀寫可以透過在裡面的內部成員變數進行定義，這邊只定義了其中三個函式 `dev_open` 、 `dev_read` 、 `rev_release` 分別在檔案開啟、讀取跟關閉的時候會被呼叫

static struct file_operations fops = {
    .open = dev_open,
    .read = dev_read,
    .release = dev_release,
};

- `static int __init xoro_init(void)` :
- `register_chrdev` : 註冊一個 character driver ，傳入的參數 `major` 指定 driver 所要實作的週邊設備，主要是 kernel 辨識用，而另一個相對應的 `minor` 則是對同一個 driver 來說區別它可以控制的這些設備。
- `class_create` : Class 的概念是高階層抽象化的表示低階層的設備實做細節，提供 user 相似的接口，當調用 `device_create` 、 `class_create` 等函數向系統註冊設備及其類的時候， kernel 會自動的在 sysfs 文件系統中創建對應的文件。
- `device_create` : 在 sysfs 中創建一個 `struct device` ，並將其註冊到指定的 class 中。
>當執行指令
>```shell
>$ make load
>sudo insmod ksort.ko
>```
>後，可以發現 kernel 已經成功註冊 device 於 `/dev/xoroshiro128p` 以及 devicr class 於 `/sys/class/xoro`

- `mutex_init` : 註冊屬於 `xoroshiro128p` 的互斥鎖，實做上會初始化一個原子變量 count 、自旋鎖以及 wait queue
- `seed` : 用 extern 在 `xoroshiro128plus.c` 繼承
- `kmalloc_array` : 配置一個大小不超過 SIZE_MAX 的陣列，傳入參數 `GFP_KERNEL` 表示配置記憶體的 flags ，代表可以休眠(較常用於一般函式)，另外， `GFP_ATOMIC` 絕不休眠，應用於中斷函式中。核心函式 `kmalloc` 一次最多能分配的記憶體空間是 129 Kbytes ，如果想要更大的記憶體配置需要使用到 page 配置的技巧如使用 `get_zeroed_page` 等
:::info
當一個 driver 載入的時候，udevd daemon會偵測到這個事件，而後去檢查/sys目錄，如果驅動程式建立了dev檔案的話，檔案裡會含有major及minor number，如此 udevd就能以它建立裝置檔。而怎麼檢查 udevd 是否有在運行狀態呢？執行

 $ ps aux|grep udevd

得到輸出

root       327  0.0  0.0  49476  7540 ?        Ss   12:29   0:05 /lib/systemd/systemd-udevd

:::
- static void __exit xoro_exit(void) : 將掛載的核心模組移除
- static int dev_open(struct inode *inodep, struct file *filep) :
- `mutex_trylock` : 嘗試以原子方式獲取 mutex 。如果成功獲取了 mutex lock ，則返回1，爭用時返回0。
- `jump` : 在 `xoroshiro128plus.c` 中定義的函式，
- static ssize_t dev_read(struct file *filep, char *buffer, size_t len, loff_t *offset) :
- 每次讀取至多 8 bytes
- `next` : 在 `xoroshiro128plus.c` 中定義的函式，
- ` copy_to_user` : 將 value 從 kernel space 複製到 buffer 中以利在 user space 中讀取。

- static int dev_release(struct inode *inodep, struct file *filep) : 釋放 mutex lock

以上為在 kernel space 掛載的模組建立，執行時由 user space 的 main 去呼叫 kernel module 執行相關動作，實做細節如下 :

==**`text_xoro.c`**==

int fd = open("/dev/xoroshiro128p", O_RDONLY);
    if (0 > fd) {
        perror("Failed to open the device.");
        return errno;
    }
/* Test reading different numbers of bytes */
for (int n_bytes = 0; n_bytes < 10; n_bytes++) {
    /* Clear/zero the buffer before copying in read data */
    zero_rx();

    /* Read the response from the LKM */
    ssize_t n_bytes_read = read(fd, rx, n_bytes);

    if (0 > n_bytes_read) {
        perror("Failed to read all bytes.");
        return errno;
    }

    uint64_t value_ = 0;
    for (int b_idx = 0; b_idx < n_bytes_read; b_idx++) {
        unsigned char b = rx[b_idx];
        value_ |= ((uint64_t) b << (8 * b_idx));
    }
    printf("n_bytes=%d n_bytes_read=%ld value=%016lx\n", n_bytes,n_bytes_read, value_);
}

- 調用 open 函數打開裝置 `/dev/xoroshiro128p`
- 在我們從 kernel 獲取排序資料之前，先把預計從 kernel 裡抓出來的資料 buffer 清空，也就是設成0。
- `n_bytes_read = read(fd, rx, n_bytes)` : 傳入 buffer `rx` ，從 kernel 中讀取數值後放入 `rx` 內，並回傳總共讀取的 byte 數。
-

## 透過 ktime 取得時間並紀錄排序實作佔用的時間
透過以下程式碼實做：

ktime_t ktime = ktime_get();

sort_impl(a, TEST_LEN, sizeof(*a), cmpint, NULL);

ktime = ktime_sub(ktime_get(), ktime);
printk("Time: time spend =%lld ms on heap sort",  (long long)ktime_to_us(ktime));

得到原先 heap sort 的實做時間約為 ==160 ms==

## 實作上述的 introsort 或 pdqsort，並整合進 ksort，須確保和標頭檔

選擇 introsort 實做，首先修改提供的 introsort 範例

typedef int (*comparator_t)(const void *, const void *);

定義一個輸入兩個 `const void *` 變數，並回傳 int 的 function pointer 。

將 introsort 的函式整合進去後發現之後發現 introsort 的執行時間反而比原本 heap sort 還要長

## 改寫 swenson/sort 的程式碼並整合進 ksort，擴充測試情境，並分析現有 Linux 核心採用的 heapsort 效能表現。

### Reference

[將 driver 掛載到 kernel 上](https://pcnews.pixnet.net/blog/post/30747058)
[基礎 Linux Device Driver 驅動程式#8](http://csw-dawn.blogspot.com/2012/01/linux-device-driver-8-character-device.html)

###### tags: `linux2021`