2021q1 Homework5 (sort)

contributed by < Julian-Chu >

tags: linux2021

GitHub

LKM: Linux Loadable Kernel Module

---

copy_to_user with uint64_t and variable length

dev_read

    uint64_t value = next(); /* in xoroshiro128plus.c */
    /* copy_to_user has the format ( * to, *from, size) and ret 0 on success */
    int n_notcopied = copy_to_user(buffer, (char *) (&value), len_);

test_xoro.cc

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

        uint64_t value_ = 0;
        // uint64_t 8 bytes <-> char *
        // char 1 byte
        // little endian
        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));
        }

重點: uint64_t 與 char * 的互換, bit operation, little endian

q1: Test reading different numbers of bytes 設計的使用場景？

你可嘗試用 uintptr_t (C99 規範)

jserv

---

透過 ktime 取得時間並紀錄排序實作佔用的時間

Github branch

make check: run check and plot

main.c

next()回傳 uint64, 使用 cmpint 比較 uint64 會導致排序錯誤, 新增 cmpuint64

static int __init cmpuint64(const void *a, const void *b)
{
    uint64_t a_val = *(uint64_t *) a;
    uint64_t b_val = *(uint64_t *) b;
    if (a_val > b_val)
        return 1;
    if (a_val == b_val)
        return 0;
    return -1;

在 dev_read 內部利用 next() 產生待排序資料, 利用 cmpuint64 跟 sort_impl 進行排序, 量測排序時間並檢驗排序結果

static ktime_t kt;

static ssize_t dev_read(struct file *filep,
                        char *buffer,
                        size_t len,
                        loff_t *offset)
{
    size_t len_ = (len > 8) ? 8 : len;
    uint64_t value;

    // generate data to sort
    uint64_t sizes[TEST_LEN];
    for (int i = 0; i < TEST_LEN; i++) {
        sizes[i] = next();
        value = sizes[i];
    }

    // measure sorting time
    kt = ktime_get();
    sort_impl(sizes, TEST_LEN, sizeof(*sizes), cmpuint64, NULL);
    kt = ktime_sub(ktime_get(), kt);
    printk(" %llu\n", kt);

    /* copy_to_user has the format ( * to, *from, size) and ret 0 on success */
    int n_notcopied = copy_to_user(buffer, (char *) (&value), len_);

    if (0 != n_notcopied) {
        printk(KERN_ALERT "XORO: Failed to read %d/%ld bytes\n", n_notcopied,
               len_);
        return -EFAULT;
    }

    // check sorted data
    #define ESORT 999
    for (int i = 0; i < TEST_LEN - 1; i++)
        if (sizes[i] > sizes[i + 1]) {
            pr_err("test has failed\n");
            return -ESORT;
        }
    printk(KERN_INFO "XORO: read %ld bytes\n", len_);
    return len_;
}

對 LKM 新增 write 方法回傳量測時間

// declaration of write
static ssize_t dev_write(struct file *, const char *, size_t size, loff_t *);
static struct file_operations fops = {
    .open = dev_open,
    .read = dev_read,
    .release = dev_release,
    // assign function to write
    .write = dev_write,
};

static ssize_t dev_write(struct file *file,
                         const char *buf,
                         size_t size,
                         loff_t *offset)
{
    printk(" %llu\n", kt);
    return ktime_to_ns(kt);
}

test_xoro.c

更動 test_xoro.c, 由於用到 write, 需要設定 fd 可寫入, 將原本的 O_RDONLY 改為 O_RDWR, 使用 write 回傳資料

記得 read/write 回傳都要 error check, 善用 errno 提高 debug 效率

int main(int argc, char *argv[])
{
    int fd = open("/dev/xoroshiro128p", O_RDWR);
    if (0 > fd) {
        perror("Failed to open the device.");
        return errno;
    }

    char write_buf[] = "testing writing";
    /* 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;
        // uint64_t 8 bytes <-> char *
        // char 1 byte
        // little endian
        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));
        }

        // get sorting time
        long long kt = write(fd, write_buf, strlen(write_buf));
        if (kt < 0) {
            perror("Failed to write the message to the device.");
            return errno;
        }
        printf("%d %lld\n", n_bytes, kt);
    }

    return 0;
}

跑 10 次的結果

---

改寫 swenson/sort 的程式碼並整合進 ksort

修改 sort.h 使之可以被使用在 Linux 核心，移除 C 標準函式庫和執行環境的依賴，改用 Linux 核心內建的 API。

malloc(size) -> kmalloc(size, GFP_KERNEL) // what's different between flags
free -> kfree
printf(stderr...)-> printk(KERN_ERR ...)
exit(1) -> 移除

// 以下錯誤爲使用空間超過 stack 最大值的設定, 改用 heap 即可
BUG: stack guard page was hit at 000000005b18ddff (stack is 00000000e8fcc7a9..00000000f3c40e99)

整合後發現排序錯誤, 原因是使用 demo 裡面的定義給 int 的 SORT_CMP 會導致 uint 的情況錯誤, (x-y) 不會小於零, 使用預設 SORT_CMP 即可修正

#define SORT_CMP(x, y) (x - y)
/* You can redefine the comparison operator.
   The default is
#define SORT_CMP(x, y)  ((x) < (y) ? -1 : ((x) == (y) ? 0 : 1))
   but the one below is often faster for integer types.
*/
#define SORT_CMP(x, y) (x - y)

改寫 dev_read 讓回傳時間可以透過 copy_to_user 回傳

    uint64_t *times = kmalloc(sizeof(uint64_t)*8, GFP_KERNEL);
    .......    
    // shell sort
    memcpy(dst, src, sizeof(uint64_t) * TEST_LEN);
    kt = ktime_get();
    ksort_shell_sort(dst, TEST_LEN);
    times[(int)shell_sort] = ktime_sub(ktime_get(), kt);
    printk(KERN_INFO " %llu\n", kt);

    for (int i = 0; i < TEST_LEN - 1; i++)
        if (dst[i] > dst[i + 1]) {
            pr_err("test has failed with shell_sort\n");
            kfree(src);
            kfree(dst);
            return -ESORT;
        }
    ......
    int n_notcopied = copy_to_user(buffer, (void *) (times), sizeof(uint64_t)*8);

todo: 利用 preprocessor 與 goto 簡化程式碼

排序 100 筆資料

排序 1000 筆資料

排序 1500 筆資料

嘗試排序 2000 筆資料以上會發生 page fault 錯誤, 找問題中

[31087.396151] BUG: unable to handle page fault for address: ffffffffc064b00f
[31087.396152] #PF: supervisor instruction fetch in kernel mode
[31087.396153] #PF: error_code(0x0010) - not-present page

q: 除了 dmesg, 在 kernel debug 的技巧？

透過 UML 搭配 GDB 來除錯！

jserv

sort.h 遇到的 static analysis issue, 新增下列的 cppcheck arguments 暫時忽略。

--suppress=variableScope -i sort.h --suppress=redundantAssignment -i sort.h

---

實作 introsort 或 pdqsort，整合進 ksort