2024q1 Homework1 (lab0)

contributed by < ICARUSHERALD96500 >

詳閱作業說明，指定的格式中有空白字元，留意各式細節，唯有重視小處並步步為營，方可挑戰原始程式碼規模超越三千七百萬行的 Linux 核心

開發環境

$ gcc --version
gcc (Ubuntu 11.4.0-1ubuntu1~22.04) 11.4.0

$ lscpu
Architecture:                x86_64
CPU op-mode(s):              32-bit, 64-bit
Address sizes:               48 bits physical, 48 bits virtual
Byte Order:                  Little Endian
CPU(s):                      16
On-line CPU(s) list:         0-15
Vendor ID:                   AuthenticAMD
Model name:                  AMD Ryzen 7 6800H with Radeon Graphics
CPU family:                  25
Model:                       68
Thread(s) per core:          2
Core(s) per socket:          8
Socket(s):                   1
Stepping:                    1
CPU max MHz:                 4785.0000
CPU min MHz:                 400.0000
BogoMIPS:                    6388.18

指定的佇列操作

結構體

struct list_head {
    struct list_head *prev;
    struct list_head *next;
};

typedef struct {
    char *value;
    struct list_head list;
} element_t;

`q_new`

原先對 Linux Kernel API 不熟悉，寫出 q_new

流程
1.malloc 分配sizeof(struct list_head) 大小的記憶體空間。
2.若所分配的位址 q 失敗，為 NULL ，則直接 return q ，q_new函式就會回傳 NULL 。

struct list_head *q = malloc(sizeof(struct list_head));
   if (q) {
        q->prev = q;
        q->next = q;
    }
    return q;

後來發現 list.h 當中就有 INIT_LIST_HEAD 故更改為下列

static inline void INIT_LIST_HEAD(struct list_head *head)
{
    head->next = head->prev = head;
}

`q_free`

void q_free(struct list_head *head) 
{
    if (head == NULL){
        return;
    }
    while (list_empty(head)){
        struct list_head *n = head ->next;
        list_del(n);
        free(n);
    }
    free(head);
}

`q_insert_head`

bool q_insert_head(struct list_head *head, char *s)
{   
    if (head && s){
        element_t * new_element = malloc(sizeof(element_t));
        if (new_element){
            new_element->value = strdup(s);
            if (new_element->value){
                head->next = new_element;
                return true;
            }
            else {
                free(new_element);
            }
        }
    }
    else{
    return false;
    }
}

使用 git diff 或 diff 命令來產生程式碼之間的差異列表，不要憑感覺填寫，注意位移量。

對於指標是否被成功分配記憶體的條件判斷的寫法，關於 if (head != NULL) 以及 if (head) 二者間的差別，雖然效果相同，後者更為簡潔，但為求可讀與維護性。

明確指出你參考的 GitHub 帳號
什麼叫做「多數會選擇」？我們本該做出更精簡更有效的程式碼，不是去迎合「多數」

`q_remove_head`

起初對於 *head 意思與題目誤解，導致誤以為是移除對於 head 前一節點的元素，寫出下列的程式碼。
導致於使用 ./qtest 測試時反而產生把 link list tail 移除的效果。

element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
    if (!head || !list_empty(head))
        return NULL;
    struct list_head *rm_list_head = head->prev;
    struct list_head *dummy_prev = rm_list_head->prev;
    struct list_head *dummy_next = rm_list_head->next;
    dummy_prev->next = dummy_next;
    dummy_next->prev = dummy_prev;

    element_t *rm_element = list_entry(rm_list_head, element_t, list);
    if (!sp || !(rm_element->value))
        return NULL;
    strncpy(sp, rm_element->value, bufsize);
    sp[bufsize -1] = '\0';
    return rm_element;
}

並修正下列錯誤

-    struct list_head *rm_list_head = head->prev;
+    struct list_head *rm_list_head = head->next;

commit bb0dbb1
熟悉linux kernel API並修正函式中不必要的 list 宣告

在當中發現 list_del

@@ -76,16 +74,18 @@ element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
 {
     if (!head || list_empty(head))
         return NULL;
+    element_t *f = list_first_entry(head, element_t, list);
+    list_del(&f->list);
-    struct list_head *rm_list_head = head->next;
-    struct list_head *dummy_prev = rm_list_head->prev;
-    struct list_head *dummy_next = rm_list_head->next;
-    dummy_prev->next = dummy_next;
-    dummy_next->prev = dummy_prev;
 
+    if (sp) {
+        size_t copy_size =
+            strlen(f->value) < (bufsize - 1) ? strlen(f->value) : (bufsize - 1);
+        strncpy(sp, f->value, copy_size);
+        sp[copy_size] = '\0';
+    }
+    return f;
-    element_t *rm_element = list_entry(rm_list_head, element_t, list);
-    if (!sp || !(rm_element->value))
-        return NULL;
-    strncpy(sp, rm_element->value, bufsize);
-    sp[bufsize - 1] = '\0';
-    return rm_element;
}

`q_remove_tail`

使用與 q_remove_head 相同邏輯

    if (!head || !list_empty(head))
        return NULL;
    struct list_head *rm_list_head = head->prev;
    struct list_head *dummy_prev = rm_list_head->prev;
    struct list_head *dummy_next = rm_list_head->next;
    dummy_prev->next = dummy_next;
    dummy_next->prev = dummy_prev;

    element_t *rm_element = list_entry(rm_list_head, element_t, list);
    if (!sp || !(rm_element->value))
        return NULL;
    strncpy(sp, rm_element->value, bufsize);
    sp[bufsize -1] = '\0';
    return rm_element;

commit bb0dbb1
同樣修正與函式q_remove_head中同樣不必要的 list 宣告

@@ -93,16 +93,18 @@ element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize)
 {
     if (!head || list_empty(head))
         return NULL;
+    element_t *f = list_first_entry(head, element_t, list);
+    list_del(&f->list);
-    struct list_head *rm_list_head = head->next;
-    struct list_head *dummy_prev = rm_list_head->prev;
-    struct list_head *dummy_next = rm_list_head->next;
-    dummy_prev->next = dummy_next;
-    dummy_next->prev = dummy_prev;
 
+    if (sp) {
+        size_t copy_size =
+            strlen(f->value) < (bufsize - 1) ? strlen(f->value) : (bufsize - 1);
+        strncpy(sp, f->value, copy_size);
+        sp[copy_size] = '\0';
+    }
+    return f;
-    element_t *rm_element = list_entry(rm_list_head, element_t, list);
-    if (!sp || !(rm_element->value))
-        return NULL;
-    strncpy(sp, rm_element->value, bufsize);
-    sp[bufsize - 1] = '\0';
-    return rm_element;
 }

`q_delete_mid`

在 make test 中出現 ERROR: Removed value gerbil != expected value bear。發現是在走訪到中間節點過程中使用 for() 迴圈使用錯誤導致函數輸出不為所求。修正確定其為走訪到 mid point，並改為使用 while 使之更為簡短。














bool q_delete_mid(struct list_head *head)
{
    if (head == NULL || list_empty(head))
        return false;
    int count = q_size(head) / 2;
    struct list_head *temp = head->next;
-   for (int i = 0; i <= count; i++) {
+   while (count--) {
        temp = temp->next;
    }
    list_del(temp);
    q_release_element(list_entry(temp, element_t, list));
    return true;
}

`q_swap`

首先我嘗試的方法使用,在每兩個節點中進行 next 與 prev 之間的關係互換

    if (!head || list_empty(head))
        return;
    int count = 0;
    struct list_head *node, *prev_node, *dummy_prev, *dummy_next;
    for (node = (head)->next; node != (head); node = node->next) {
        count++;
        if (count % 2 == 0) {
            prev_node = node->prev;
            //
            dummy_prev = prev_node->prev;
            dummy_next = node->next;
            dummy_prev->next = node;
            dummy_next->prev = prev_node;
            //
            node->prev = dummy_prev;
            node->next = prev_node;
            //
            prev_node->prev = node;
            prev_node->next = dummy_next;
        }
    }

但在該方法下會產生的問題是 head 所指向的節點會因為 prev 與 next 關係重組而被排列到最後。效果如下：

new l = [1 2 3 4 5 6 7]
swap l = [2 3 4 3 7 6 1]

熟悉kernel api後改進：

commit b18ff64

@@ -226,22 +226,13 @@ void q_swap(struct list_head *head)
     if (!head || list_empty(head))
         return;
     int count = 0;
-    struct list_head *node, *prev_node, *dummy_prev, *dummy_next;
-    for (node = (head)->next; node != (head); node = node->next) {
+    struct list_head *node, *prev = head;
+    list_for_each (node, head) {
         count++;
         if (count % 2 == 0) {
-            prev_node = node->prev;
-            //
-            dummy_prev = prev_node->prev;
-            dummy_next = node->next;
-            dummy_prev->next = node;
-            dummy_next->prev = prev_node;
-            //
-            node->prev = dummy_prev;
-            node->next = prev_node;

`q_reverse`

Valgrind + 自動測試程式

閱讀 'qtest命令直譯器的實作'，發現其中展示qtest原理，展示在 qtest.c 當中的 init_cmd() 添加：

bool do_hello(int argc, char *argv[])
{
    return (bool) printf("Hello, World\n");
}

結果 make 後產生下列錯誤代碼:

/usr/bin/ld: queue.o: in function `do_hello':
/home/b37265417/linux2024/lab0-c/queue.c:390: multiple definition of `do_hello'; console.o:/home/b37265417/linux2024/lab0-c/console.c:417: first defined here
collect2: error: ld returned 1 exit status
make: *** [Makefile:49: qtest] Error 1

將 bool do_hello(int argc, char *argv[]) 改為 static bool do_hello(int argc, char *argv[]) 後解決。

Fisher–Yates shuffle

將 shuffle 引入 `qtest` 命令中

參照自動測試程式在qtest新增shuffle功能，在 console.h 的巨集中：

/* Add a new command */
void add_cmd(char *name, cmd_func_t operation, char *summary, char *parameter);
#define ADD_COMMAND(cmd, msg, param) add_cmd(#cmd, do_##cmd, msg, param)

要添加新命令需要透過在 console.c 底下的 console_init 當中使用 add_cmd 函式。該函式需要輸入三個引數 "<instruction>"、<do_*>、"<document>"。以呼叫同樣宣告在console.c 底下命名為 do_<instruction> 的函式（因為在巨集中 do_##cmd 將所要呼叫的函式名稱 concatinate 為 cmd 前加上 do_）。

以 q_new 函式被呼叫的流程為例。首先 qtest.c 的主函式中， init_cmd() 使用 ADD_COMMAND 將 q_new() 加入。add_cmd 接收的第二項引數是型別為 cmd_func_t 的函式指標。該指標指向 console.c 的 Build-in funciton 或 qtest.c 的 do_* 函式，如 do_new()，再由該函式中呼叫在 queue.c 中所撰寫的各項 q_* 函式。

將 shuffle 分別新增在 init_cmd 與 console_init 底下的的差別似乎不大，同樣都可以執行。但最後決定添加在 console 底下，因為其他鏈結串列的操作同樣新增在這個類別。

qtest.c

static void consloe_init()
{...
    ADD_COMMAND(shuffle, "Fisher-Yates shrffle", "")
    ...
}

static bool do_shuffle(int argc, char *argv[])
{
    if (!current || !current->q)
        return;
    if (q_size(current->q) < 2)
        return;
    if (exception_setup(true))
        q_shuffle(current->q);
    q_show(3);
    return !error_check();
}

queue.h

    void q_shuffle(struct list_head *head) ;

queue.c

static inline void swap(struct list_head *node_1, struct list_head *node_2)
{
    if (node_1 == node_2)
        return;
    struct list_head *node_1_prev = node_1->prev;
    struct list_head *node_2_prev = node_2->prev;
    if (node_1->prev != node_2) list_move(node_2, node_1_prev);
    list_move(node_1, node_2_prev);
}

void q_shuffle(struct list_head *head) 
{
    if (!head || list_is_singular(head)) 
        return;
    struct list_head *last = head;
    int size = q_size(head);
    while (size > 0) {
        int index = rand() % size;
        struct list_head *new = last->prev;
        struct list_head *old = new;
        while (index--) 
            old = old->prev;
        swap(new, old);
        last = last->prev;
        size--;
    }
    return;
}

`shuffle`

研讀 Linux 核心原始程式碼 list_sort.c

研讀 Linux 核心原始程式碼 list_sort.c
嘗試引入 Linux 核心原始程式碼到 lab0-c 專案
比較自己實做的merge sort 和 Linux 核心程式碼之間的效能落差

引入 Linux list_sort.c 到 lab0-c

修改檔案： qtest.c、Makefile
新增檔案： list_sort.c、list_sort.h

list_sort.c
為了要讓 ./qtest command line 當中的 time 指令可以執行 linux list_sort 的方法，利用首先在 lab0-c中新增 list_sort.c ，並移除不會用到的部份：

// SPDX-License-Identifier: GPL-2.0
// #include <linux/bug.h>
// #include <linux/compiler.h>
// #include <linux/export.h>
// #include <linux/string.h>
// #include <linux/list_sort.h>
// #include <linux/list.h>
...
// EXPORT_SYMBOL(list_sort);

list_sort.h
其中包含 list_sort.c 所需要的定義

#ifndef _LIST_SORT_H
#define _LIST_SORT_H
#include <stdint.h>
#include "list.h"
#define USE_LINUX_SORT  0
#define likely(x)	__builtin_expect(!!(x), 1)
#define unlikely(x)	__builtin_expect(!!(x), 0)
typedef int __attribute__((nonnull(2,3))) (*list_cmp_func_t)(void *, const struct list_head *, const struct list_head *);
void list_sort(void *priv, struct list_head *head, list_cmp_func_t cmp);
#endif /* End of _LIST_SORT_H_ */

Makefile
為了使 make 時連同 list_sort 加入源代碼文件的目標編譯文件，所需更改：

OBJS := qtest.o report.o console.o harness.o queue.o list_sort.o \
        random.o dudect/constant.o dudect/fixture.o dudect/ttest.o \
        shannon_entropy.o \
        linenoise.o web.o \

qtest.c
在 qtest.c 中建立函式：

__attribute__((nonnull(2,3)))
int cmp(void *priv, const struct list_head *list1, const struct list_head *list2)
{
    element_t *list1_entry = list_entry(list1, element_t, list);
    element_t *list2_entry = list_entry(list2, element_t, list);
    return strcmp(list1_entry->value, list2_entry->value) < 0 ? 0 : 1;
}

比較自己的merge sort 和 Linux 核心程式碼之間的效能落差

新增一筆測資 trace-sort.cmd 於 trace/ 中：

option fail 0
option malloc 0
new
ih RAND 10000
time
sort
time

並將 Makefile 中 check 的部份改為下列。執行 make check 時，便會使用自己定義的 trace-sort.cmd 測資。

check: qtest
	./$< -v 3 -f traces/trace-sort.cmd

結果如下：

資料總數	q_sort() 測試1(s)	q_sort() 測試2(s)	q_sort() 測試3(s)	q_sort() 測試4(s)	q_sort() 測試5(s)
100000	0.08	0.076	0.078	0.075	0.076
300000	0.302	0.309	0.316	0.309	0.313
500000	0.614	0.585	0.578	0.576	0.585

資料總數	list_sort() 測試1(s)	list_sort() 測試2(s)	list_sort() 測試3(s)	list_sort() 測試4(s)	list_sort() 測試5(s)
100000	0.108	0.055	0.054	0.056	0.055
300000	0.180	0.178	0.179	0.178	0.180
500000	0.303	0.311	0.305	0.304	0.308

比較 q_sort 、 list_sort 性能差異：

閱讀論文 Dude, is my code constant time?

論文提出一種測試程式執行時間是否為 constant time 的工具 dudect，這個方法不需要硬體模型，以消弭不同硬體架構下對測量的影響。目的是驗證理論上時間複雜度為 constant time ，但實則存在 time leakage 的問題，如此可以藉由程式處理不同輸入時的響應時間差，藉此推敲程式內部細節，引發資安疑慮。

文中取 '字串比較' 典型場景。普遍作法為逐字元比較，若一但遇到不相符者即刻中斷比較並回傳false ，如此便可以透過從輸入字元到回傳的時間推敲是第幾個字元錯誤。較佳的作法為，就算遭遇不相符，也同樣比對完剩餘字元，以此避免time leakage。

作者採取 Students' T test 其中 Two-sample T test 進行實驗。使用兩種測資，第一種為全數固定為某值的固定測資、第二種為亂數的隨機測資。在虛無假設下進行 Fix-vs-Random test。

2024q1 Homework1 (lab0)

開發環境

指定的佇列操作

結構體

q_new

q_free

q_insert_head

q_remove_head

q_remove_tail

q_delete_mid

q_swap

q_reverse

Valgrind + 自動測試程式

Fisher–Yates shuffle

將 shuffle 引入 qtest 命令中

shuffle