2023q1 Homework1 (lab0)

contributed by < fewletter >

開發環境

$ gcc --version
gcc (Ubuntu 9.4.0-1ubuntu1~20.04.1) 9.4.0

$ lscpu
Architecture:                    x86_64
CPU op-mode(s):                  32-bit, 64-bit
Byte Order:                      Little Endian
Address sizes:                   39 bits physical, 48 bits virtual
CPU(s):                          6
On-line CPU(s) list:             0-5
Thread(s) per core:              1
Core(s) per socket:              6
Socket(s):                       1
NUMA node(s):                    1
Vendor ID:                       GenuineIntel
CPU family:                      6
Model:                           158
Model name:                      Intel(R) Core(TM) i5-9500 CPU @ 3.00GHz
Stepping:                        10
CPU MHz:                         3000.000
CPU max MHz:                     4400.0000
CPU min MHz:                     800.0000
BogoMIPS:                        6000.00
Virtualization:                  VT-x
L1d cache:                       192 KiB
L1i cache:                       192 KiB
L2 cache:                        1.5 MiB
L3 cache:                        9 MiB
NUMA node0 CPU(s):               0-5

開發過程

常用結構體

list_head

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

element_t

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

q_new

根據 list.h 中的 INIT_LIST_HEAD 來實作 q_new ，此巨集可產生一個 prev 和 next 都指向自己的 list_head 指標，並且沒有包含資料

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

實作流程:
使用 malloc 分配記憶體空間，當配置記憶體空間失敗時，回傳 NULL ，若成功則產生一個 prev 和 next 都指向自己的 list_head 指標，並且回傳此結構

struct list_head *q_new()
{
    struct list_head *head = malloc(sizeof(struct list_head));
    if (!head)
        return NULL;

    INIT_LIST_HEAD(head);
    return head;
}

q_free

利用 list.h 的巨集 list_for_each_safe ，其中 entry 代表著進行迭代的節點， safe 則是 entry 的下一個節點， head 則指向我們要釋放的串列

#define list_for_each_entry_safe(entry, safe, head, member)                \
    for (entry = list_entry((head)->next, __typeof__(*entry), member),     \
        safe = list_entry(entry->member.next, __typeof__(*entry), member); \
         &entry->member != (head); entry = safe,                           \
        safe = list_entry(safe->member.next, __typeof__(*entry), member))

實作流程:

先偵測 l 是否為 NULL ，若不為 NULL 則進行下面的步驟
利用巨集 list_for_each_safe 走過每個節點並且移除每個節點
將每個移除的節點釋放記憶體
最後再釋放 l 的記憶體空間

void q_free(struct list_head *l) 
{ 
    if (!l)
        return;
    element_t *node, *next;
    list_for_each_entry_safe (node, next, l, list) {
        list_del(&node->list);
        q_release_element(node);
    }
    free(l);
}

q_insert_head

實作步驟:

檢查 head 指向是否為 NULL ，是的話回傳 false
使用 malloc 配置出 element_t 大小的記憶體空間，若配置空間失敗，同樣回傳 false
利用 strlen 計算出 s 的長度
使用 malloc 配置出 s 長度再加上1的記憶體空間，若配置空間失敗，同樣回傳 false
將字串複製到 element 中，再利用 list_add 將它加入到 head 後面

bool q_insert_head(struct list_head *head, char *s)
{
    if (!head)
        return false;
    element_t *element = malloc(sizeof(element_t));
    if (!element)
        return false;
    INIT_LIST_HEAD(&element->list);
    int len = strlen(s);
    element->value = malloc((len + 1) * sizeof(char));
    if (!element->value) {
        free(element);
        return false;
    }
    strncpy(element->value, s, len);
    *(element->value + len) = '\0';
    list_add(&element->list, head);
    return true;
}

q_insert_tail

此函式和 q_insert_head 的程式幾乎相同，除了倒數第二行從 list_add 改成list_add_tail

bool q_insert_head(struct list_head *head, char *s)
{
    if (!head)
        return false;
    element_t *element = malloc(sizeof(element_t));
    if (!element)
        return false;
    INIT_LIST_HEAD(&element->list);
    int len = strlen(s);
    element->value = malloc((len + 1) * sizeof(char));
    if (!element->value) {
        free(element);
        return false;
    }
    strncpy(element->value, s, len);
    *(element->value + len) = '\0';
    list_add_tail(&element->list, head);
    return true;
}

q_remove_head

利用巨集 list_first_entry ，得到開頭節點的字串

#define list_first_entry(head, type, member) \
    list_entry((head)->next, type, member)

實作流程:

檢測此串列是否存在和是否為空，如果不存在或者串列為空的話回傳NULL
利用 list_first_entry，創造出一個 element_t 包含第一個節點和第一個節點的字串
將字串複製給 sp 後，刪除此節點並且將開頭交給原本串列的第二項

element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
    if (!head || list_empty(head))
        return NULL;

    element_t *target = list_first_entry(head, element_t, list);
    if (sp) {
        strncpy(sp, target->value, bufsize - 1);
        *(sp + bufsize - 1) = '\0';
    }

    list_del_init(&target->list);
    return target;
}

q_remove_tail

此函式和 q_remove_head 幾乎相同，只有 list_first_entry 需改成list_last_entry

element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize)
{
    if (!head || list_empty(head))
        return NULL;

    element_t *target = list_last_entry(head, element_t, list);
    if (sp) {
        strncpy(sp, target->value, bufsize - 1);
        *(sp + bufsize - 1) = '\0';
    }

    list_del_init(&target->list);
    return target;
}

q_size

本函式讓指標 *node 走訪過每個節點，每走過一個讓 size+1 ，邏輯並不複雜，所以主要考慮的點為讓程式碼盡量精簡

int q_size(struct list_head *head)
{
    int size = 0;
    struct list_head *node = NULL;
    list_for_each (node, head)
        size++;
    return size;
}

q_delete_mid

本函式利用〈你所不知道的 C 語言: linked list 和非連續記憶體〉提及的快慢指標來找尋一個串列中間的節點，通過兩個指標不同的速度，讓其中一個指標走完全程時，另一個在此串列的中間。

實作流程:

建立兩個指標 fast 和 slow，fast 為 slow 的兩倍速度
走完整個串列，當 fast 迭代到底或是迭代到 head 時，slow 即為我們要找的中點
移除 slow 並釋放記憶體

bool q_delete_mid(struct list_head *head)
{
// https://leetcode.com/problems/delete-the-middle-node-of-a-linked-list/
    if (!head || list_empty(head))
        return false;

    struct list_head *fast = head->next;
    struct list_head *slow = head->next;

    while (fast != head && fast->next != head) {
        fast = fast->next->next;
        slow = slow->next;
    }
    list_del(slow);
    q_release_element(list_entry(slow, element_t, list));
    return true;
}

上面是 Leetcode 的標準常見解法，但是此題並不只是單向的鏈結串列，而是具備環狀雙向特性，於是除了可指向後一個節點的 *next 以外，尚有參照前一節點的 *prev，運用前述特性，實作下面程式碼。

實作流程:

建立兩個指標 left 和 right，left 為從頭開始走的指標，right 為從尾巴開始走的指標，兩者速度相同
迴圈檢查兩者相遇的地點，移除並且刪掉 right 指標

@@ -4,14 +4,14 @@ bool q_delete_mid(struct list_head *head
     if (!head || list_empty(head))
         return false;
 
-    struct list_head *fast = head->next;
-    struct list_head *slow = head->next;
+    struct list_head *left = head->next;
+    struct list_head *right = head->prev;
 
-    while (fast != head && fast->next != head) {
-        fast = fast->next->next;
-        slow = slow->next;
+    while (left != right && left->next != right) {
+        left = left->next;
+        right = right->prev;
     }
-    list_del(slow);
-    q_release_element(list_entry(slow, element_t, list));
+    list_del(right);
+    q_release_element(list_entry(right, element_t, list));
     return true;
 }

善用 diff 展現程式碼變異處，查閱 diff(1) 以熟悉相關用法。

Image Not Showing Possible Reasons

The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported

Learn More →

jserv

q_delete_dup

bool q_delete_dup(struct list_head *head)
{
    // https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/
    if (!head || list_empty(head) || list_is_singular(head))
        return false;
    bool diff = false;
    struct list_head *curr, *safe;
    list_for_each_safe (curr, safe, head) {
        struct list_head *next = curr->next;
        element_t *curr_entry = list_entry(curr, element_t, list);
        element_t *next_entry = list_entry(next, element_t, list);
        if ((next != head) && (!strcmp(curr_entry->value, next_entry->value))) {
            list_del(curr);
            q_release_element(curr_entry);
            diff = true;
        } else if (diff) {
            list_del(curr);
            q_release_element(curr_entry);
            diff = false;
        }
    }
    return true;
}

q_swap

本函式使用 list_move 來達成兩兩互換的串列

static inline void list_move(struct list_head *node, struct list_head *head)
{
    list_del(node);
    list_add(node, head);
}

原本想利用 list_for_each_safe 來實作此題的迴圈，但是其中迭代時的其中一行迭代的程式 node = safe 會造成迴圈停止，因為此時 node 已經移到 safe 後面，所以迭代時要使用 node = node->next 來進行迭代。

void q_swap(struct list_head *head)
{
    // https://leetcode.com/problems/swap-nodes-in-pairs/
    if (!head || list_empty(head) || list_is_singular(head))
        return;

    struct list_head *node, *safe;
    for (node = (head)->next, safe = node->next; node != (head) && safe != head;
         node = node->next, safe = node->next) {
        list_move(node, safe);
    }
}

實作流程
下面是一個一般的串列

list_del 將 node 從原本的地方移除

list_add 將 node 接在 safe 後面

讓 node = node->next 和 safe = node->next，然後依照上面步驟再做一次

q_reverse

本函式的目的為將 next 和 prev 相互交換，方法是將指標由指向 next 改成指向 prev ，指向 prev 改成指向 next 。

/* Reverse elements in queue */
void q_reverse(struct list_head *head)
{
    if (!head || list_empty(head))
        return;

    struct list_head *front = head->prev, *now = head, *next = NULL;
    while (next != head) {
        next = now->next;
        now->next = front;
        now->prev = next;
        front = now;
        now = next;
    }
}

實作流程

將需要迭代的節點 front 指向 head->prev， now 指向 head, next 指向head->next

將節點 now 的 *next 指到節點 front，節點 now 的 *prev 指到節點 next ，交換 front 和 next 的位置

進行下一次的迭代位置

q_reverseK

本函式利用 list_move，將每個需要被反轉的節點，依序接到另行建立的 empty 節點，再用 list_splic_init 連接已觸及的節點。

void q_reverseK(struct list_head *head, int k)
{
    // https://leetcode.com/problems/reverse-nodes-in-k-group/
    if (!head || k <= 1)
        return;

    struct list_head *node, *start, *anchor = head;
    LIST_HEAD(empty);
    int count = 0;
    int time_mark = 0;
    int size = q_size(head);
    list_for_each_safe (node, start, head) {
        count++;
        if (count <= k && (size - time_mark) >= k) {
            list_move(node, &empty);
            if (count == k) {
                list_splice_init(&empty, anchor);
                count = 0;
                time_mark += k;
                anchor = start->prev;
            }
        }
    }
}

撰寫更精簡的程式碼。

Image Not Showing Possible Reasons

The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported

Learn More →

jserv

實作流程

下面以 k=2 作為舉例

list_move 第一個節點到 empty 後

list_move 第二個節點到 empty 後，得到反轉後的串列

list_splic_init 接回去

q_descend

仿照 list_for_each_safe 的迴圈方法，寫一個 prev 的迴圈版本，想法是將所有節點與迭代中的最大值做比較。

實作流程

建立 char *s 來記錄結尾的字串
建立迴圈，走訪每個節點，但是結尾字串不比較
若 s 小於節點的內含值，s 則變為節點的值，反之則將節點刪除並且釋放記憶體空間

int q_descend(struct list_head *head)
{
    // https://leetcode.com/problems/remove-nodes-from-linked-list/
    struct list_head *node, *safe;
    char *s = list_entry(head->prev, element_t, list)->value;
    for (node = (head)->prev, safe = node->prev; node != (head);
         node = safe, safe = node->prev) {
        element_t *tmp = list_entry(node, element_t, list);
        if (node != head->prev) {
            if (strcmp(s, tmp->value) < 0) {
                s = tmp->value;
            } else {
                list_del(&tmp->list);
                q_release_element(tmp);
            }
        }
    }
    return q_size(head);
}

上方程式碼迴圈內的 if-if-else 可簡化。

Image Not Showing Possible Reasons

The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported

Learn More →

jserv

q_merge

此函式會使用到下面的結構體

typedef struct {
    struct list_head *q;
    struct list_head chain;
    int size;
    int id;
} queue_contex_t;

避免只用圖示來解釋 queue_context_t，你應該先用清晰的文字敘述，再搭配圖解。

Image Not Showing Possible Reasons

The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported

Learn More →

jserv

queue_contex_t 結構體， head 與 chain 的關係

此函式必須要靠著 head 迭代出所有結構體 queue_contex 當中的串列 q，然後把每一個串列 q 以由小到大排序的順序串接起來，其中必須先將串列 q 利用指標 q->prev->next 指向 NULL 變成 singly-linked list，最後頭尾再接起來形成完整的 doubly-linked list。

實作流程

先切斷每個節點部分的連接， iter->q->prev->next = NULL
再將兩個串列利用 mergeTwolists 合併

queue_contex_t *iter;
list_for_each_entry (iter, head, chain) {
    iter->q->prev->next = NULL;
    merge_node = mergeTwolists(merge_node, iter->q->next);
    INIT_LIST_HEAD(iter->q);
}

走過整個串列後，形成完整的 doubly-linked list，最後回傳q_size(q_head)

struct list_head *curr = q_head->q, *next = curr->next;
    while (next) {
        next->prev = curr;
        curr = next;
        next = next->next;
    }
    curr->next = q_head->q;
    q_head->q->prev = curr;

q_sort

參考〈你所不知道的 C 語言: linked list 和非連續記憶體: Merge Sort 的實作〉和〈Merge Sort 與它的變化〉中的 merge sort 的遞迴程式碼。

mergeTwolists

本函式的目的為將兩個串列以由小到大排序的順序連接在一起，並利用間接指標 **ptr 來指向兩個串列中迭代到的節點，避免使用 malloc 配置多的記憶體，無法釋放記憶體空間，此函式也是實作 merge 時會利用到的函式。

實作流程

利用 list_entry 將兩個串列個別節點的 value 相互比較
將 *node 指向 value 比較過後較小的節點
將 *ptr 指向 *node ，最後再迭代到下一個節點

struct list_head *mergeTwolists(struct list_head *L1, struct list_head *L2)
{
    struct list_head *head = NULL, **ptr = &head, **node = NULL;
    while (L1 && L2) {
        element_t *L1_entry = list_entry(L1, element_t, list);
        element_t *L2_entry = list_entry(L2, element_t, list);
        node = strcmp(L1_entry->value, L2_entry->value) < 0 ? &L1 : &L2;
        *ptr = *node;
        ptr = &(*ptr)->next;
        *node = (*node)->next;
    }
    *ptr = (struct list_head *) ((uintptr_t) L1 | (uintptr_t) L2);
    return head;
}

merge_sort

本函式的想法即為將一個串列從中間一直切成兩份並在最後結合在一起

實作流程

利用快慢指標找到中間的節點

    for (struct list_head *fast = head->next; fast && fast->next;
         fast = fast->next->next) {
        slow = slow->next;
    }

利用遞迴將每個節點一個個分開，再利用 mergeTwolists 將兩個節點以由小到大排序的順序一直合併

    struct list_head *left = merge_sort(head), *right = merge_sort(mid);
    return mergeTwolists(left, right);

sort

實作流程

將頭尾切開
利用 merge_sort 一直分開和合併節點
走過每個節點形成一個完整的 circular doubly linked list

/* Sort elements of queue in ascending order */
void q_sort(struct list_head *head)
{
    if (!head || list_empty(head) || list_is_singular(head))
        return;
    head->prev->next = NULL;
    head->next = merge_sort(head->next);
    struct list_head *curr = head, *next = curr->next;
    while (next) {
        next->prev = curr;
        curr = next;
        next = next->next;
    }
    curr->next = head;
    head->prev = curr;
}

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

與其逐行列出程式碼，你應該先闡述 Linux 核心開發者到底要解決什麼問題，以及這些考量如何反映在設計中。

Image Not Showing Possible Reasons

The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported

Learn More →

jserv

了解，謝謝老師

研讀 list_sort.c前，第一個問題是自己所寫 merge sort 有什麼問題需要解決？
從Linux 核心的鏈結串列排序中可以知道，自己所寫 merge sort 為 Top-down mergesort 是透過不停的 partition (分割)，最後在兩兩串列合併成最後的串列，並且過程中完全沒有考慮到 cache 。

 * This mergesort is as eager as possible while always performing at least
 * 2:1 balanced merges.  Given two pending sublists of size 2^k, they are
 * merged to a size-2^(k+1) list as soon as we have 2^k following elements.
 *
 * Thus, it will avoid cache thrashing as long as 3*2^k elements can
 * fit into the cache.  Not quite as good as a fully-eager bottom-up
 * mergesort, but it does use 0.2*n fewer comparisons, so is faster in
 * the common case that everything fits into L1.

從以上註解可知道 Linux 核心開發者採用了只有合併串列，並且避免 cache thrashing 的合併方法，此種方法少了partition (分割)這樣一直更新串列的動作，同時也對 cache 更友善。

閱讀 list_sort.c 程式碼時可以發現，此程式碼由三個函式 merge ， merge_final ， list_sort 所組成。
merge 此函式可以看到 cmp(priv, a, b) ，從 list_sort.h 中可以看到其定義。

typedef int __attribute__((nonnull(2,3))) (*list_cmp_func_t)(void *, const struct list_head *, const struct list_head *);
__attribute__((nonnull(2,3)))

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

雖然還不知道 __attribute__((nonnull(2,3))) 是什麼，但是從下面的程式可以看出這是一個比較大小的函式，放到 merge 裡面的程式碼中，就可以看出如果當一個串列是以升冪 –- 由小到大排序的方式傳入， merge 就會以由小到大排序的方式結合兩個串列，反之由大到小排序也是相同情況。

查閱教育部辭典「升冪」:

數學代數式中，某一字母的指數，由低順次至高，稱為此一字母的「升冪」。

這裡不是多項式。

Image Not Showing Possible Reasons

The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported

Learn More →

jserv

for (;;) {
    /* if equal, take 'a' -- important for sort stability */
    if (cmp(priv, a, b) <= 0) {
        *tail = a;
        tail = &a->next;
        a = a->next;
        if (!a) {
            *tail = b;
            break;
        }
    } else {
        *tail = b;
        tail = &b->next;
        b = b->next;
        if (!b) {
            *tail = a;
            break;
        }
    }
}

對解說的程式碼以一致的程式碼風格排版，善用 clang-format

Image Not Showing Possible Reasons

The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported

Learn More →

jserv

嘗試引入 list_sort.c 到 `lab0-c` 專案中

參考 qtest 命令直譯器的實作

複製 list_sort.c 程式碼到 list_sort.c 和所需要的標頭檔到 list_sort.h

標頭檔程式碼

#ifndef _LIST_SORT_H
#define _LIST_SORT_H

#include <stdint.h>
#include "list.h"

#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

從 list_sort.c 中可以知道需要巨集 likely，unlikely 和函式指標 list_cmp_func_t
增加 linux_sort 到 qtest.c 中，可以讓自己手動測試

為了能夠分別測試 list_sort 和實作的 sort ，所以按照 qtest 命令直譯器的實作的步驟在 qtest裡面新增命令 linux_sort 。

研讀 option 相關程式碼，以此切換排序的實作，這樣就不用引入彆扭的 linux_sort 新命令，日後可繼續在 option 擴充新的排序演算法，但不用新增命令。

Image Not Showing Possible Reasons

The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported

Learn More →

jserv

ADD_COMMAND(linux_sort,
                "Sort queue in ascending order by using Linux kernel", "");

仿照 do_sort 實作 do_linux_sort ，作法是將下面程式碼

if (current && exception_setup(true))
        q_sort(current->q);

改成

if (current && exception_setup(true))
        list_sort(NULL, current->q, cmp);

增加 trace-linux_sort.cmd 和 trace-sort.cmd 來自動測試 list_sort 和 sort

trace-linux_sort.cmd

option fail 0
option malloc 0
new
ih RAND 100000
linux_sort
time

trace-sort.cmd

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

比較 `merge sort` 與 Linux 核心程式碼效能

執行 trace-sort_compare.cmd ，執行以下命令:

./qtest -f traces/trace-linux_sort.cmd
./qtest -f traces/trace-sort.cmd

執行結果如下

l = []
l = [itisgpj stgknec uwget ermhm lqfrjs rgbdzwkia niyuvs pmpwnspem igpiww ngtfqwzri pytuioyh vlmcweivt aricspdeo lgsbl dvbhfohee ervqwsuj owpubrys cswmotz pppoocle dfrsbh wcsuq txlgnm xymdctq clviiyx ksvodq qiavlv funhx ztivnniyz rqplaqwh rmndrks ... ]
l = [aaakfol aaalei aaapry aaayu aabihget aablmstks aabnmex aabnqexg aabogae aabuq aabwzdvd aabxpat aacchunqy aacmwy aacwzasyh aacxvldzv aaczhmu aadajyh aadgxr aadmyblgk aadnufbz aadwf aadzx aaeby aaeffxrkn aaejrpx aaejvwhle aaemen aaenfh aaevvyptr ... ]
Elapsed time = 0.159, Delta time = 0.159

l = []
l = [xfxddnmsv quamfmmc ogadbq hncje puoqkxjz rysllv lutjl mmsbruz ctqhmyl jkxwbywy myedjyr ohjmzyy zvolja xolyhka fppekszq ymummjic ootvvl hyxhm sfbtu ysgujjdl fspczebyo grmukar ewasih ylcay jgeqj cbzohwigb wkfyq dvxoi eecsqda rfwefxcj ... ]
l = [aaafp aaaojws aaatw aaayfm aaayzjud aabbxbdde aabfbux aabfjeji aabgbbco aabnxncu aabpj aabpyou aabso aabtoavy aabvaqgx aacbp aacdkjlz aacdrzhbv aacfzhhx aacuco aadvgu aadvx aaeea aaeetqcvi aaega aaehhuak aaejhhb aaelvp aaenapv aaeouak ... ]
Elapsed time = 0.179, Delta time = 0.179

ih RAND 100000

	q_sort	list_sort
Elapsed time	0.179	0.159
Delta time	0.179	0.159

ih RAND 500000

	q_sort	list_sort
Elapsed time	1.1014	0.808
Delta time	1.1014	0.808

ih RAND 1000000

	q_sort	list_sort
Elapsed time	Time limit exceed	1.725
Delta time	Time limit exceed	1.725

接著利用 perf 原理和實務檢測 cache-misses，cache-references，instructions，cycles 四個項目

ih RAND 500000

	q_sort	list_sort
cache-misses	5032,7722	3538,6984
cache-references	8940,8835	6581,8426
instructions	21,2075,2982	21,1753,5235
cycles	45,0536,4432	33,9000,1693

從上面數據可以看到除了 instructions 大約相同外，其他項目 linux_sort 都比 q_sort 還少

TODO: 針對排序演算法的限制，設計足以產生 worst-case 的測試案例。

Image Not Showing Possible Reasons

The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported

Learn More →

jserv

參考Linux 核心的鏈結串列排序

想法：

list_sort 是一種只有合併的 mergesort ，代表其 worst-case 是比較次數較多的串列
將比較次數最大化，即為將一個完全是由大到小排序的串列傳入

實作流程：

先給一個隨機的串列
利用 list_sort 將串列排列
將已經排序的的串列排成由大到小排序順序(reverse)
分別紀錄 list_sort 和 q_sort 的時間

測試結果如下：

串列大小 30000

q_sort

Elapsed time = 0.057, Delta time = 0.057
Elapsed time = 0.074, Delta time = 0.017

 Performance counter stats for './qtest -f traces/trace-worst-sort.cmd':

          179,5892      cache-misses              #   35.594 % of all cache refs    
          504,5521      cache-references                                            
       1,3893,6266      instructions              #    0.55  insn per cycle         
       2,5346,8567      cycles                                                      

       0.075241075 seconds time elapsed

開始排序時間為 0.57，排序完成時間為 0.74，排序時間為 0.17

list_sort

Elapsed time = 0.045, Delta time = 0.045
Elapsed time = 0.063, Delta time = 0.018

 Performance counter stats for './qtest -f traces/trace-worst-linux_sort.cmd':

          205,1925      cache-misses              #   43.335 % of all cache refs    
          473,5060      cache-references                                            
       1,3853,7035      instructions              #    0.54  insn per cycle         
       2,5478,4476      cycles                                                      

       0.064160188 seconds time elapsed

開始排序時間為 0.45，排序完成時間為 0.63，排序時間為 0.18

串列大小 / merge 種類	q_sort	list_sort
10000	0.02	0.03
30000	0.17	0.18
100000	0.97	0.59

串列大小 10000

	q_sort	list_sort
cache-misses	10,7731	21,2893
cache-references	136,5123	132,8497
instructions	4637,2298	4617,1204
cycles	5828,7503	6080,4767

串列大小 30000

	q_sort	list_sort
cache-misses	179,5892	205,1925
cache-references	504,5521	473,5060
instructions	1,3893,6266	1,3853,7035
cycles	2,5346,8567	2,5478,4476

串列大小 100000

	q_sort	list_sort
cache-misses	1189,0006	1050,7305
cache-references	2089,1345	1916,7928
instructions	4,7343,4558	4,6870,1310
cycles	11,5324,7931	9,4894,3256

從上面四個表格可以看出，即使是在 list_sort 排序的最壞情況，時間都可以幾乎跟 q_sort 一樣，但是在 cache-misses 這項指標中，在 list_sort 排序的最壞情況，串列大小越小， list_sort 比 q_sort 多了很多，代表此項指標影響速度的程度很大，要降低排序時間首先的目標是要降低此項指標。

在 qtest 提供新的命令 shuffle

參考 qtest 命令直譯器的實作

在 qtest.c 中加入下面程式碼

ADD_COMMAND(shuffle, "Shuffle the queue", "");

實作 q_shuffle 於 qtest.c 中
- 利用 Fisher–Yates shuffle 演算法來實作洗牌（shuffle）
  - q_size 取得整體串列大小
  - 隨機選取節點並將其移至尾巴

void q_shuffle(struct list_head *head)
{
    if (!head || list_empty(head) || list_is_singular(head))
        return;
    int len = q_size(head);

    while (len != 0) {
        struct list_head *node = head->next;
        int pos = rand() % len;
        for (int i = 0; i < pos; i++)
            node = node->next;
        list_move_tail(node, head);
        len--;
    }
};

實作 do_shuffle 程式碼，主要是讓自己所寫的 q_shuffle 可以在 qtest.c 中測試

程式碼

if (exception_setup(true))
    q_shuffle(current->q);

測試結果

cmd> new
l = []
cmd> ih RAND 5
l = [cnytb rbjjuwnh afwpqjmpz cayfh kkzddhit]
cmd> sort
l = [afwpqjmpz cayfh cnytb kkzddhit rbjjuwnh]
cmd> shuffle
l = [cnytb afwpqjmpz kkzddhit cayfh rbjjuwnh]

統計方法驗證 shuffle

為了讓測試程式可以在本地端直接使用 make shuffle 命令執行，所以執行下面的流程

開啟新檔案將測試程式程式碼貼到新檔案中
將新檔案檔名加入到 Makefile 中

shuffle: 
	python3 scripts/shuffle.py

執行 make shuffle 命令即可得到一個串列 shuffle 過後的出現次數的直方圖

測試結果

0.3513854055416222
0.28514514058056234
0.0021660086640346563
0.24725498901995607
6.000024000096e-06
0.3313513254053016
Expectation:  166666
Observation:  {'123': 166908, '132': 166884, '213':    166647, '231': 166463, '312': 166667, '321': 166431}
chi square sum:  1.2173088692354768

由上圖來看，此圖符合 uniform distribution。

計算chi-squared test statistic

$X^{2} = \sum_{i = 1}^{n} \frac{(O_{i} - E_{i})^{2}}{E_{i}}$

	公式計算	chi-squared
$123$	$\frac{(166908 - 166666)^{2}}{166666}$	$0.3514$
$132$	$\frac{(166884 - 166666)^{2}}{166666}$	$0.2851$
$213$	$\frac{(166647 - 166666)^{2}}{166666}$	$0.0026$
$231$	$\frac{(166463 - 166666)^{2}}{166666}$	$0.2473$
$312$	$\frac{(166667 - 166666)^{2}}{166666}$	$6 \times 10^{- 6}$
$321$	$\frac{(166431 - 166666)^{2}}{166666}$	$0.3314$
總和		$1.2173$

統計檢定的結果不拒絕虛無假說

$α = P$ (拒絕
$H_{0}$ |
$H_{0}$ 為真)

改用 LaTeX 重寫數學式

Image Not Showing Possible Reasons

The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported

Learn More →

jserv

在此將

α

設為 0.05。
由於 [1,2,3] 有六種排列情形，所以它有 5 個自由度，根據卡式分佈表，

P

value 介於 0.95 到 0.9 之間，因為

P

value（0.95~0.9）> alpha（0.05），統計檢定的結果不拒絕虛無假說（

H_{0}

）。

研讀論文〈Dude, is my code constant time?〉

本篇論文在討論 dudect ，一項工具來評估一段程式是否可以在給定時間(constant time)運行。

而為什麼 constant time 對一段程式碼如此重要，可以參考解讀計算機編碼：在資訊安全的應用，又或是論文上的這段話

Kocher writes in 1996 his seminal paper on recovering cryptographic
keys by measuring the execution time of cryptographic
implementations [Koc96 ]. More concretely, he exploits data-
dependent variance in the execution time of RSA, DSS or Diffie-
Hellman to recover secret key bits in a divide-and-conquer
fashion. Since then, timing attacks have been broken numerous
variable-time implementations, including high-impact systems
such as TLS [ AP13 ]. In comparison to other side-channel
attacks, timing attacks require minimal interaction with the
target and can be mounted remotely [BB03].

簡單來說就是通過程式實作時的一些指標，比如說程式執行時間，來推斷程式碼隱藏的東西。

dudect 是一種不需要知道 CPU 硬體結構也可以實作的檢測方法，此論文提及一些其他的研究作法，不過其他研究的共同缺點是都需要知道 CPU 硬體結構。

以下是此論文所提及的檢測步驟：

在有可能造成洩漏 (potential leakages) 測試範圍分成兩種測試方法，一種是固定測試(constant)，一種是隨機測試 (random)。
資料後處理 (post-processing)， Cropping 主要是修剪掉較長的執行時間， Higher-order preprocessing 則是根據統計檢測來應用。
應用統計測試，主要有兩種測試方法，第一種為 Welch’s t-test ，第二種則為 Non-parametric tests 。

解釋 Student’s t-distribution 及程式實作的原理

Student's t-distribution 主要是作為兩組數據的抽樣檢查，只要兩組數據越多，越接近常態分布，之後檢查兩者分布如果越相近，便會主張兩者皆為 constant time 。
Student's t-distribution 通常假設兩者的變異數相同，所以 Welch’s t-test 此種可以應用在不同變異數的統計測試方法被提出。
Welch’s t-test 中的 t 定義如下

$t = \frac{{\overset{―}{X}}_{0} - {\overset{―}{X}}_{1}}{\sqrt{\frac{v a r_{0}}{N_{0}} + \frac{v a r_{1}}{N_{1}}}}$
由於兩組數據變異數不相同，因此需要對 t 分布的自由度做加權後才可以檢定，加權過後的自由度定義如下

$d f^{^{'}} = \frac{(\frac{v a r_{1}^{2}}{n_{1}} + \frac{v a r_{2}^{2}}{n_{2}})^{2}}{\frac{v a r_{1}^{2} / n_{1}}{n_{1} - 1} + \frac{v a r_{2}^{2} / n_{2}}{n_{2} - 1}}$

simulation 程式實作原理

首先先查看 qtest.c 中有關 simulation 的命令

if (simulation) {
    if (argc != 1) {
        report(1, "%s does not need arguments in simulation mode", argv[0]);
        return false;
    }
    bool ok = is_insert_head_const();
    if (!ok) {
        report(1,
               "ERROR: Probably not constant time or wrong implementation");
        return false;
    }
    report(1, "Probably constant time");
    return ok;
}

由上面可以看到，如果進入 simulation 模式，重點是 is_insert_head_const() 此函式會傳出 do_ih 執行時間是否為 constant time。
尋找 is_insert_head_const() ，在 fixure.h 中找到下面這項巨集

#define _(x) bool is_##x##_const(void);

在 fixure.c 中找到下面巨集

#define DUT_FUNC_IMPL(op) \
    bool is_##op##_const(void) { return test_const(#op, DUT(op)); }

然後再沿著 test_const() 此項函式繼續尋找，路徑大概如下 test_const()
$\to$ doit()
$\to$ report() ，得知決定 is_insert_head_const() 是 true 或是 false 的關鍵在 report() 中

double max_t = fabs(t_compute(t));
double number_traces_max_t = t->n[0] + t->n[1];
double max_tau = max_t / sqrt(number_traces_max_t);

t_compute() 就是在計算 Welch’s t-test 中的 t

double t_compute(t_context_t *ctx)
{
    double var[2] = {0.0, 0.0};
    var[0] = ctx->m2[0] / (ctx->n[0] - 1);
    var[1] = ctx->m2[1] / (ctx->n[1] - 1);
    double num = (ctx->mean[0] - ctx->mean[1]);
    double den = sqrt(var[0] / ctx->n[0] + var[1] / ctx->n[1]);
    double t_value = num / den;
    return t_value;
}

從 report() 中可以看到有三種情況會讓 qtest.c 中的 ih 測試結果不是 constant time
第一種是測量的 cpu cycle 太少

if (number_traces_max_t < ENOUGH_MEASURE) {
        printf("not enough measurements (%.0f still to go).\n",
               ENOUGH_MEASURE - number_traces_max_t);
        return false;
    }

第二、三種是從 Welch’s t-test 計算出來的 t 太大無法通過測試標準

/* Definitely not constant time */
if (max_t > t_threshold_bananas)
    return false;
    
/* Probably not constant time. */
if (max_t > t_threshold_moderate)
    return false;

要讓 trace-17-complexity.cmd 通過最簡單的方法就是調整測試標準，不過此方法就代表上述統計檢驗方法完全沒用到，所以還在研究其他方法中。

enum {
    t_threshold_bananas = 50000, /* Test failed with overwhelming probability*/ 
    t_threshold_moderate = 100, /* Test failed*/
};

測試結果

+++ TESTING trace trace-17-complexity:
# Test if time complexity of q_insert_tail, q_insert_head, q_remove_tail, and q_remove_head is constant
Probably constant time
Probably constant time
Probably constant time
Probably constant time
---     trace-17-complexity     5/5
---     TOTAL           100/100

oreparaz/dudect 還在研究中

運用 Valgrind 排除 qtest 實作的記憶體錯誤

TODO

2023q1 Homework1 (lab0)

開發環境

開發過程

常用結構體

q_new

q_free

q_insert_head

q_insert_tail

q_remove_head

q_remove_tail

q_size

q_delete_mid

q_delete_dup

q_swap

q_reverse

q_reverseK

q_descend

q_merge

q_sort

mergeTwolists

merge_sort

sort

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

嘗試引入 list_sort.c 到 lab0-c 專案中

比較 merge sort 與 Linux 核心程式碼效能

在 qtest 提供新的命令 shuffle

統計方法驗證 shuffle

研讀論文〈Dude, is my code constant time?〉

解釋 Student’s t-distribution 及程式實作的原理

運用 Valgrind 排除 qtest 實作的記憶體錯誤

Read more

STM32

Linux核心實作筆記

Implement Linux userspace RV32 emulation for RVVM

Assignment3: single-cycle RISC-V CPU

嘗試引入 list_sort.c 到 `lab0-c` 專案中

比較 `merge sort` 與 Linux 核心程式碼效能