Linux 核心專題: 改進 lab0

執行人: yihsuan1011
專題講解影片

提問清單

• ?

任務簡述

重做 lab0 並彙整其他學員的成果。

TODO: 達成作業所有要求

開發環境

$ gcc --version
gcc (Ubuntu 9.4.0-1ubuntu1~20.04.1) 9.4.0
Copyright (C) 2019 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

$ 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):                          16
On-line CPU(s) list:             0-15
Thread(s) per core:              2
Core(s) per socket:              8
Socket(s):                       1
NUMA node(s):                    1
Vendor ID:                       GenuineIntel
CPU family:                      6
Model:                           141
Model name:                      11th Gen Intel(R) Core(TM) i7-11800H @ 2.30GHz
Stepping:                        1
CPU MHz:                         800.000
CPU max MHz:                     4600.0000
CPU min MHz:                     800.0000
BogoMIPS:                        4608.00

開發過程

q_new

用malloc來配置記憶體，若配置失敗則會回傳NULL，配置成功則接著使用INIT_LIST_HEAD來初始化。

struct list_head *q_new()
{
    struct list_head *q = malloc(sizeof(struct list_head));
    if (!q)  // If allocate failed
        return NULL;
    INIT_LIST_HEAD(q);
    return q;
}

q_free

用list_for_each_entry_safe來走訪佇列中的每個節點，並透過list_del與q_release_element將每個節點的空間釋放。list_for_each_entry_safe中除了用entry儲存當前節點外，還會使用另一個指標safe來儲存下一個節點，因此不必擔心當前節點空間被釋放後會導致循環無法繼續。

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

q_insert_head

使用malloc為新節點配置記憶體，並檢查該，element_t有無配置成功，接著使用strdup複製字串s到entry->value，若檢查到entry->value配置失敗，則要將整個entry都釋放，最後再透過list_add將新節點加入佇列中。

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

q_insert_tail

q_insert_tail與q_insert_head的目標類似，僅在插入節點的位置有所不同，因此直接用head->prev作為q_insert_head的第一個引數就可以完成目標，只需要額外考慮空佇列的特例即可。

bool q_insert_tail(struct list_head *head, char *s)
{
    if (!head)
        return false;

    if (list_empty(head))
        return q_insert_head(head, s);
    else
        return q_insert_head(head->prev, s);
}

q_remove_head

使用list_first_entry找到開頭節點，並使用strncpy將被刪除的節點字串複製到sp中，字串長度由bufsize限制，且需要加上結尾字元，最後再由list_del_init刪除開頭節點。

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(head->next);
    return target;
}

q_remove_tail

使用list_last_entry找到結尾節點，並使用strncpy將被刪除的節點字串複製到sp中，字串長度由bufsize限制，且需要加上結尾字元，最後再由list_del_init刪除結尾節點。

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(head->prev);
    return target;
}

q_size

使用list_for_each走訪佇列中的每個節點，宣告一個整數len來累計list_for_each的迴圈次數，達到計算佇列長度的效果。

int q_size(struct list_head *head)
{
    if (!head || list_empty(head))
        return 0;

    int len = 0;
    struct list_head *li;

    list_for_each (li, head)
        len++;
    return len;
}

q_delete_mid

首先需要找到佇列的中點，原本使用課程中提到的快慢指標完成，後來參考同學們的作法，善用雙向鏈結佇列的特性，用兩個指標以相反方向走訪，兩個指標指向同個節點時即為中點。此種做法比快慢指標法需要走訪的節點數少三分之一。

bool q_delete_mid(struct list_head *head)
{
    if (!head || list_empty(head))
        return false;
    struct list_head *front = head->next, *back = head->prev;
    while (front != back && front->next != back) {
        front = front->next;
        back = back->prev;
    }
    element_t *node = list_entry(back, element_t, list);
    list_del(&node->list);
    q_release_element(node);
    return true;
}

q_delete_dup

根據LeetCode 82的題意，該函式的目標是刪除所有重複的節點。使用list_for_each_entry_safe走訪所有節點，並且使用bool dup來標示當前節點是否為多個連續重複節點組成的重複節點群。用strcmp比較當前節點和下一個節點的字串是否相同，如果相同，則刪除當前節點，同時dup設置為1表示已進入重複節點群。直到當前節點與下一個點的字串不同時，會進到else if (dup)的區塊，刪除最後一個重複節點並將dup重新設置為0。

bool q_delete_dup(struct list_head *head)
{
    if (!head || list_empty(head))
        return false;

    element_t *curr, *next;
    bool dup = 0;
    list_for_each_entry_safe (curr, next, head, list) {
        if (&next->list != head && strcmp(curr->value, next->value) == 0) {
            list_del(&curr->list);
            q_release_element(curr);
            dup = 1;
        } else if (dup) {
            list_del(&curr->list);
            q_release_element(curr);
            dup = 0;
        }
    }

    return true;
}

q_swap

使用一個for迴圈走訪所有節點，且當前節點node和node->next皆不能為head，再使用list_move將當前節點與下一個節點交換位置，完成一個成對節點的交換，而此時的node->next就會指向下一組成對節點的第一個節點，重複直到佇列結束。

void q_swap(struct list_head *head)
{
    if (!head || list_empty(head))
        return;

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

q_reverse

使用list_for_each_entry_safe走訪所有節點，並將當前節點依序移動至佇列最前端，即完成佇列排列順序反轉。

void q_reverse(struct list_head *head)
{
    if (!head || list_empty(head))
        return;

    struct list_head *node, *safe;
    list_for_each_safe (node, safe, head)
        list_move(node, head);
}

q_reverseK

使用list_for_each_entry_safe走訪所有節點，使用count計次，每k個節點擷取成一個子佇列sub_q，並將sub_q透過q_reverse進行順序反轉，再將子佇列移動回原佇列的位置。

void q_reverseK(struct list_head *head, int k)
{
    if (!head || list_empty(head))
        return;

    int count = 0;
    struct list_head sub_q, *node, *safe, *tmp = head;
    INIT_LIST_HEAD(&sub_q);
    list_for_each_safe (node, safe, head) {
        count++;
        if (count == k) {
            list_cut_position(&sub_q, tmp, node);
            q_reverse(&sub_q);
            list_splice_init(&sub_q, tmp);
            count = 0;
            tmp = safe->prev;
        }
    }
}

q_merge_two

參考上課中的merge方法，另外定義了q_merge_two。引數為兩個佇列，宣告了一個儲存結果的list_head result，依序比較兩個佇列的最前端節點，將字串較大者移動到result的末端，完成排序後，原本的兩個佇列會有一個變為空佇列，再將另一個有剩餘節點的佇列移動到result的末端，最終結果result會儲存再原先第一個佇列的位址。
後面新增了引數 bool descend，目前先簡單依descend不同分成兩種while迴圈，但兩種迴圈有很多相同處，應可再簡化。

void q_merge_two(struct list_head *q1, struct list_head *q2, bool descend)
{
    if (!q1 || !q2)
        return;

    struct list_head result;
    INIT_LIST_HEAD(&result);
    element_t *node;
    if (descend) {
        while (!list_empty(q1) && !list_empty(q2)) {
            element_t *e1 = list_first_entry(q1, element_t, list);
            element_t *e2 = list_first_entry(q2, element_t, list);
            node = (strcmp(e1->value, e2->value) > 0) ? e1 : e2;
            list_move_tail(&node->list, &result);
        }
    } else {
        while (!list_empty(q1) && !list_empty(q2)) {
            element_t *e1 = list_first_entry(q1, element_t, list);
            element_t *e2 = list_first_entry(q2, element_t, list);
            node = (strcmp(e1->value, e2->value) < 0) ? e1 : e2;
            list_move_tail(&node->list, &result);
        }
    }

    struct list_head *residual = (list_empty(q2)) ? q1 : q2;
    list_splice_tail_init(residual, &result);
    list_splice(&result, q1);
}

q_sort

此處實作了課程中的Merge Sort方法。首先用快慢指標方法找到中間節點，從中間節點切成左右兩個子佇列，用遞迴的方式重複分割佇列，直到每個子佇列都只有一個節點，最後再用前面定義的q_merge_two兩兩合併，最終得到排序完成的佇列。

void q_sort(struct list_head *head, bool descend)
{
    if (!head || list_empty(head) || head->next == head->prev)
        return;

    struct list_head *mid = head;
    for (struct list_head *fast = head->next;
         fast != head && fast->next != head; fast = fast->next->next)
        mid = mid->next;

    struct list_head left;
    INIT_LIST_HEAD(&left);
    list_cut_position(&left, head, mid);
    // head will become right half
    q_sort(&left, descend);
    q_sort(head, descend);
    q_merge_two(head, &left, descend);
}

q_ascend

使用雙向鏈結佇列的特性，反向走訪所有節點，比較當前節點curr和前一個節點curr->list.prev位置的字串大小，若前一個節點大於當前節點則將前一個節點刪除。

int q_ascend(struct list_head *head)
{
    if (!head || list_empty(head))
        return 0;

    element_t *curr = list_entry(head->prev, element_t, list);
    while (curr->list.prev != head) {
        element_t *next = list_entry(curr->list.prev, element_t, list);
        if (strcmp(next->value, curr->value) > 0) {
            list_del(&next->list);
            q_release_element(next);
        } else {
            curr = next;
        }
    }
    return q_size(head);
}

q_descend

與q_ascend相同作法，反向走訪所有節點，比較當前節點curr和前一個節點curr->list.prev位置的字串大小，若前一個節點小於當前節點則將前一個節點刪除。

int q_descend(struct list_head *head)
{
    if (!head || list_empty(head))
        return 0;

    element_t *curr = list_entry(head->prev, element_t, list);
    while (curr->list.prev != head) {
        element_t *next = list_entry(curr->list.prev, element_t, list);
        if (strcmp(next->value, curr->value) < 0) {
            list_del(&next->list);
            q_release_element(next);
        } else {
            curr = next;
        }
    }
    return q_size(head);
}

q_merge

首先先檢查是否只有一個佇列，如果有大於一個佇列，會先將第一個佇列儲存到first，接著再從第二個佇列開始依序透過q_merge_two合併至first中，最後返回first的大小。

int q_merge(struct list_head *head, bool descend)
{
    if (!head || list_empty(head))
        return 0;
    if (head->next == head->prev)
        return list_first_entry(head, queue_contex_t, chain)->size;

    queue_contex_t *first = list_first_entry(head, queue_contex_t, chain);
    queue_contex_t *curr, *safe;

    list_for_each_entry_safe (curr, safe, head, chain) {
        if (curr != first) {
            q_merge_two(first->q, curr->q, descend);
            curr->q = NULL;
        }
    }

    return q_size(first->q);
}

引入 lib/list_sort.c

此處參考同學 chiangkd 筆記中的步驟。

加入 list_sort.c 和 list_sort.h

將 list_sort.c 和 list_sort.h 兩者加入lab0-c資料夾中，直接加入會出現很多錯誤，大多數都是因為include許多沒有使用到的header，確認那些header不會使用到則直接刪除即可。

修改 Makefile

修改Makefile，加入list_sort.o

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

修改 qtest

參考qtest當中do_sort的內容，在qtset中新增do_lsort，以執行list_sort，作法同chiangkd同學之實作。

int cmp(void *priv, const struct list_head *a, const struct list_head *b)
{
    element_t *a_ele = list_entry(a, element_t, list);  // get mother element
    element_t *b_ele = list_entry(b, element_t, list);
    return strcmp(a_ele->value, b_ele->value) < 0 ? 0 : 1;
}
bool do_lsort(int argc, char *argv[])
{
    if (argc != 1) {
        report(1, "%s takes no arguments", argv[0]);
        return false;
    }

    int cnt = 0;
    if (!current || !current->q)
        report(3, "Warning: Calling sort on null queue");
    else
        cnt = q_size(current->q);
    error_check();

    if (cnt < 2)
        report(3, "Warning: Calling sort on single node");
    error_check();

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

    bool ok = true;
    if (current && current->size) {
        for (struct list_head *cur_l = current->q->next;
             cur_l != current->q && --cnt; cur_l = cur_l->next) {
            /* Ensure each element in ascending order */
            /* FIXME: add an option to specify sorting order */
            element_t *item, *next_item;
            item = list_entry(cur_l, element_t, list);
            next_item = list_entry(cur_l->next, element_t, list);
            if (strcmp(item->value, next_item->value) > 0) {
                report(1, "ERROR: Not sorted in ascending order");
                ok = false;
                break;
            }
        }
    }

    q_show(3);
    return ok && !error_check();
}

最後再加入新命令 lsort。

ADD_COMMAND(lsort, "Sort queue in ascending order provided by linux kernel", "");

TODO: 研讀 Linux 的 lib/list_sort.c 並量化分析

解讀 Linux 核心原始程式碼的 lib/list_sort.c，設計實驗來量化分析，探討其實作手法，需要善用 perf 一類的工具。解析程式碼要有完整的圖文、數學證明，和如何達到 cache 友善。

研讀 list_sort 內容

list_sort 的排序步驟如下：

• 宣告了兩個指標 list 和 pending 分別指向佇列的當前節點和暫存節點
• 檢查是否為空佇列或只有一個節點，是則直接返回
• 透過 head->prev->next = NULL 將佇列以 NULL 為結尾
• 用for迴圈走訪每個節點，找到最小的子佇列，就進行 merge ，並更新指標和計數。
• 最後用 merge_final 完成最後合併。

上述為最簡略的步驟解釋，中間的一些條件判斷方式我還不完全理解，查閱的資料顯示這樣的佇列排序方法能達到高效率及高穩定性。

此方法為 Tim Sort 的排序演算法的變體，結合了上課提到的 merge sort 和 insertion sort。主要概念是將輸入資料分割成許多小佇列，對每一小佇列使用 insertion sort 進行排序，接著再使用 merge 將這些已經排序好的小佇列合併成排序好的大佇列，最終完成排序。

確認上述陳述是否正確！
jserv

TODO: 改進 qtest 以切換不同的排序實作

在 qtest 新增 option，允許使用者切換不同的排序實作 (例如 Linux 核心的 list_sort.c 和自行實作的 merge sort)。

上述步驟透過新增了do_lsort功能，以及新增了lsort指令，即可讓使用者透過cmd>選擇排序方法。

cmd> new
l = []
cmd> ih RAND 1000
l = [bairbyrip jltlqum vwndfsce nucefk cwxzxkt blbzozhyd abjxfpgk egsvt dobyffwh vcjdyx trgwmnw feshg fiecplk jcjrl nhrvknat qjlsix wgvttx ernhzmidp fhzxluuto soyrojs jbdlziapd benrs vfgzvod yfpngg fbysew paqqh dlfot hvqvyctlq zwxpqz pxexhawae ... ]
cmd> lsort
l = [aacsgl aamaga abjxfpgk acfhmcjt acswijwsz acwcpzmye adqpkt adxmkcww afbfx aglwnbops ahhtr ahincpmw ajtxuja akcngotau akodcaj aliwy alnnzaad ambhdg amhcs aoekbho aoictluys apkser apogs aqjzhzst aqmgbxj ashap askzhuqxr asufdf asxgvswkd asxlc ... ]

TODO: 改進原有常數時間複雜度判斷程式

搭配研讀必要的統計原理，探討如何改進原有常數時間複雜度判斷程式