2024q1 Homework1 (lab0)

contributed by < Hualing-Chiu >

開發環境

$ 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:        39 bits physical, 48 bits virtual
  Byte Order:           Little Endian
CPU(s):                 8
  On-line CPU(s) list:  0-7
Vendor ID:              GenuineIntel
  Model name:           Intel(R) Core(TM) i7-7700 CPU @ 3.60GHz
    CPU family:         6
    Model:              158
    Thread(s) per core: 2
    Core(s) per socket: 4
    Socket(s):          1
    Stepping:           9
    CPU max MHz:        4200.0000
    CPU min MHz:        800.0000
    BogoMIPS:           7200.00

佇列實作與程式碼改進

`q_new`

透過 malloc 配置記憶體，並使用 list.h 內提供的INIT_LIST_HEAD 去初始化 struct list_head

需判斷是否有成功配置記憶體位址給指標

改進你的漢語表達。

struct list_head *q_new()
{
    struct list_head *new = malloc(sizeof(struct list_head));

+    if(!new)
+        new = NULL;

    INIT_LIST_HEAD(new);  // use the function in list.h

    return new;
}

無論標題和內文中，中文和英文字元之間要有空白字元

已修正 Sheena Chiu

`q_free`

使用 list.h 提供的 list_for_each_entry_safe 走訪包含 struct list_head 的另外一個結構之 entry ，並透過額外的 safe 紀錄每個 iteration 所操作的節點的下一個節點。

void q_free(struct list_head *head) 
{
    if(head){
        element_t *entry, *safe;
        list_for_each_entry_safe(entry, safe, head, list){
            q_release_element(entry);
        }
        free(head);
    }
}

`q_insert_head`

使用 strncpy 而非 strcpy 來達成字串複製

因為strcpy可能會造成 buffer overflow 的問題

當 node->value 沒有成功配置記憶體位址的話，需要 free 掉此節點，否則在執行 git commit -a 時會出現 memory leak 的錯誤。

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

    element_t *node = malloc(sizeof(element_t));
    if (!node)
        return false;

    int slen = strlen(s) + 1;
    node->value = malloc(slen * sizeof(char));

    if (node->value) {
-        strcpy(node->value, s);
+        strncpy(node->value, s, slen);
        list_add(&node->list, head);
        return true;
    } else {
+        free(node);
        return false;
    }
    return false;
}

使用 git diff 或 diff -u 命令來產生程式碼之間的變革列表，不要憑感覺填入，注意位移量。

`q_insert_tail`

做法跟 q_insert_head() 一樣，list_add() 改成 list_add_tail() 即可。

`q_remove_head`

使用 list.h 提供的list_first_entry 找出佇列中第一個 element，再使用 strncpy 複製此 element 的 value 到 sp 中。

要注意需手動把~~空字元~~結尾字元 '\0' 加上去

'\0' 不是「空」字元，你會把數字 0 叫做「空」數字嗎？

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

    element_t *node = list_first_entry(head, element_t, list);
    list_del(&node->list);

    if (sp && bufsize) {
        strncpy(sp, node->value, bufsize);
        sp[bufsize - 1] = '\0';
    }
    return node;
}

`q_remove_tail`

做法與 q_remove_head 一樣，list_first_entry 改成 list_last_entry 即可。

`q_size`

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

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

`q_delete_mid`

給定的佇列具備環狀且雙向的特性，不該說「反方向」，改進你的漢語表達，使用精準的詞彙。

從 list_head 結構可知此佇列為雙向鏈結串列，除了使用快慢指標去實作之外，也可以使用兩個指標指向串列的頭尾，分別朝~~反方向~~ 走訪節點，需要考慮兩個狀況:

節點個數為奇數，則兩個指標會相遇，因此判斷 left != right
節點個數為偶數，則兩個指標會相鄰，因此判斷 left->next != right

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

    struct list_head *left = head->prev;
    struct list_head *right = head->next;

    while (left != right && left->next != right) {
        left = left->prev;
        right = right->next;
    }

    list_del(right);
    element_t *element = list_entry(right, element_t, list);
    q_release_element(element);

    return true;
}

`q_delete_dup`

此函式目的為刪除佇列中出現重複字串的節點，使用 list_for_each_entry_safe 迭代去紀錄下個節點，當遇到下個節點與當前節點字串相同時，刪除並釋放記憶體。

而須注意的是當刪除完後續重複節點時，當前指向的節點也必須刪除，因此使用了 flag 去紀錄該節點是否刪除。

bool q_delete_dup(struct list_head *head)
{
    // https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/
    if (!head || list_empty(head)) {
        return false;
    }
    element_t *cur, *next;
    bool flag = false;
    list_for_each_entry_safe (cur, next, head, list) {
        if (&next->list != head && !strcmp(cur->value, next->value)) {
            list_del(&cur->list);
            q_release_element(cur);
            flag = true;
        } else if (flag) {
            list_del(&cur->list);
            q_release_element(cur);
            flag = false;
        }
    }
    return true;
}

`q_swap`

當實作到 q_reverseK 時，可以發現 q_swap 其實就是 q_reverseK 的其中一種例子，因此直接套用 q_reverseK 的內容即可。

/* Swap every two adjacent nodes */
void q_swap(struct list_head *head)
{
    q_reverseK(head, 2);
}

`q_reverse`

給定的佇列具備環狀且雙向的特性，不該說「反向」，改進你的漢語表達，使用精準的詞彙。

利用 list.h 內提供的 list_for_each_safe 去走訪每個節點，使用 list_move 將節點從原本的 linked list 移動到另一個 linked list head 的開頭，就能達成~~反向順序~~ 重新排列。

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

無論標題和內文中，中文和英文字元之間要有空白字元

`q_reverseK`

使用 count 變數紀錄已走訪的節點個數，當 count == 0 時，使用 list_cut_position 切斷目前節點位址並放到 tmp 上，再使用前面實作好的 q_reverse 對 tmp 進行反轉，最後用 list_splice 把 tmp 接回 tmp_head 上。

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

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

`q_sort`

使用的排序演算法為 Merge Sort，首先使用 NULL 將最後一個節點的 next 與 head 斷開，接著使用 mergeSort 函式找出中間節點，分成左右兩段 list

head->prev->next = NULL;
head->next = mergeSort(head->next);

實作完 mergeSort 後會回傳排序好的指標串列，但由於先前使用 NULL 將最後一個節點與 head 斷開，因此需要手動將 head 跟最後一個 node 的 prev 及 next 都接回去。

struct list_head *last = head;
while (last->next)
    last = last->next;

head->prev = last;
last->next = head;
head->next->prev = head;

你如何確保目前的測試已涵蓋排序演算法的最差狀況？

`mergeSort`

採用遞迴呼叫搭配快慢指標的概念將指標串列左右對半分，直到分割成單一節點再使用 mergeTwoLists 函式合併成排序好的串列。

struct list_head *mergeSort(struct list_head *head)
{
    if (!head->next)
        return head;

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

    slow->prev->next = NULL;
    struct list_head *left, *right;
    left = mergeSort(head);
    right = mergeSort(slow);
    return mergeTwoLists(left, right);
}

`mergeTwoLists`

此函式的目的是依照字串大小順序合併兩個指標串列。

參照你所不知道的C語言：linked list 和非連續記憶體提供的較直觀的做法進行修改，但程式碼會顯的冗長，因尚未完整研讀 list_sort.c，之後改進並嘗試引入 list_sort.c。

struct list_head *mergeTwoLists(struct list_head *L1, struct list_head *L2)
{
    struct list_head *head, *ptr;
    if (strcmp(list_entry(L1, element_t, list)->value,
               list_entry(L2, element_t, list)->value) <= 0) {
        head = L1;
        ptr = head;
        L1 = L1->next;
    } else {
        head = L2;
        ptr = head;
        L2 = L2->next;
    }

    while (L1 && L2) {
        if (strcmp(list_entry(L1, element_t, list)->value,
                   list_entry(L2, element_t, list)->value) <= 0) {
            ptr->next = L1;
            L1->prev = ptr;
            L1 = L1->next;
        } else {
            ptr->next = L2;
            L2->prev = ptr;
            L2 = L2->next;
        }
        ptr = ptr->next;
    }

    if (L1) {
        ptr->next = L1;
        L1->prev = ptr;
    } else {
        ptr->next = L2;
        L2->prev = ptr;
    }
    head->prev = NULL;
    return head;
}

`q_descend`

commit f766e18

從指標串列尾端走訪至 head，若下一個節點小於當前節點的 value，則刪除下一個節點。

`q_merge`

int q_merge(struct list_head *head, bool descend)
{
    if (!head || list_empty(head))
        return 0;

    if (list_is_singular(head))
        return q_size(list_first_entry(head, queue_contex_t, chain)->q);

    queue_contex_t *q1 = container_of(head->next, queue_contex_t, chain);
    for (struct list_head *cur = head->next->next; cur != head;
         cur = cur->next) {
        queue_contex_t *q = container_of(cur, queue_contex_t, chain);
        list_splice_init(q->q, q1->q);
        q->size = 0;
    }
    q_sort(q1->q, false);
    q1->size = q_size(q1->q);
    return q1->size;
}

Valgrind + 自動測試程式

參照 Massif: a heap profiler，Massif 可以量測程式用了多少的 heap memory，除了可以幫忙加速程式，讓程式可以跟機器快取有更好的互動且避免 paging 發生，還可以減少耗盡 swap space 的機會。

參考 var-x 的測試步驟，首先先在 Makefile 中新增以下指令：

+    check-massif: qtest
+	    valgrind --tool=massif ./$< -v 3 -f traces/trace-massif.cmd

trace-massif.cmd 是我們自己定義的 trace 檔，裡面的內容可以複製 trace-17-complexity.cmd，如果只要測試 q_insert_head 的話，稍微修改一下 trace-17-complexity.cmd 的內容即可。




# Test if time complexity of q_insert_tail, q_insert_head, q_remove_tail, and q_remove_head is constant
option simulation 1
it
option simulation 0

接著執行 make check-massif 後可以獲得一個輸出檔案為 massif.out.xxxxx，執行 ms_print massif.out.xxxxx 可以顯示程式執行期間的記憶體消耗圖表，可以讓 user 更容易閱讀。

    MB
1.231^ #                                                                      
     | #                                                                      
     | #                                                                      
     | #                           ::                        :               :
     | #                           :                         :               :
     | #                           :                         :               :
     | #                           :                         :               :
     | #          @@               :                         :               :
     | #          @       :        :                         :               :
     | #   ::  :: @       :        :         :               :               :
     | #   :   :  @       :        :    ::   :               :        :      :
     | #   :   :  @       :        :    :    :               :        :      :
     | #   :   : :@       :        :  :::    :  :: :@@    @@ :        :      :
     | #   :   : :@      ::  ::    :  : :    :  :  :@ ::  @  :   :    :::    :
     | #   :   : :@    ::::  :     :  : :    :  :  :@ :   @ :::  :    ::     :
     | #   :   : :@    : ::  :     :  : :    :  :  :@ :  :@ ::::::    :: :   :
     | # :::   : :@    : ::  : ::  :  : : :  :  :  :@ : ::@ :::: :    :: ::  :
     | # : :   : :@    : ::  : :   :  : : :  ::::  :@ : ::@ :::: : :: :: ::@@:
     | # : :   : :@ :: : ::  : :   :  : : :  :: :  :@ : ::@ :::: : :  :: ::@ :
     | # : : ::: :@ :::: ::::: :  ::  : : :  :: :  :@ : ::@ :::: ::: ::: ::@ :
   0 +----------------------------------------------------------------------->Gi
     0                                                                   14.71

Number of snapshots: 51
 Detailed snapshots: [1 (peak), 8, 31, 35, 48]

以上圖表顯示 Massif 對這個程式做了56次的 snapshot，而 Massif 在 heap allocation/deallocation 時才會做 snapshot，但隨著程式運行時間增加，Massif 會減少 snapshot 的次數。

: 是 normal snapshot
@ 是 detailed snapshots
# 是 peak snapshot，紀錄 memory 消耗最大的時候

如果想要更直觀去看記憶體用量的話，可以執行 massif-visualizer massif.out.xxxxx，會顯示出以下圖形：

只要摘錄你認為值得討論的訊息片段即可。

研讀 Linux 核心原始程式碼 lib/list_sort.c 並嘗試引入

將 list_sort.c 跟 list_sort.h 引入專案中。

一開始會遇到 include 相關的錯誤，檢查是否引入多餘的標頭檔，將不需要用到的全部刪除。

-    #include <linux/bug.h>
-    #include <linux/compiler.h>
-    #include <linux/export.h>
+    #include "list_sort.h"

再來則會遇到 unknown type name ‘u8’ 的錯誤，在 /include/linux/types.h 可以發現 u8 被定義為 uint8_t，因此將型別宣告改成 uint8_t。

+    uint8_t count = 0;

再來處理 cmp 參數，list_sort.c 的設計是傳入 cmp 比較函式，這邊我參考 gaberplaysgame 實作的 q_list_cmp 函式放入 list_sort.c 中，並刪掉 priv 與 cmp 參數。

__attribute__((nonnull(1, 2))) int q_list_cmp(const struct list_head *a,
                                              const struct list_head *b)
{
    element_t *element_a = list_entry(a, element_t, list); // cppcheck-suppress nullPointer
    element_t *element_b = list_entry(b, element_t, list); // cppcheck-suppress nullPointer

    int res = strcmp(element_a->value, element_b->value);

    return res;
}

接著在 qtest.c 中加入一個新的函式 do_lsort ，寫法與 do_sort 大同小異，差異在呼叫的函式需改成 Linux 核心風格的 list_sort 函式。

在 qtest.c 中新增 lsort 指令命令

command 的翻譯是「命令」，而非「指令」(instruction)

+    ADD_COMMAND(lsort, "Sort queue in ascending order by using Linux kernel sorting algorithm", "");

TODO: 使用 perf 分析效能

2024q1 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_sort

mergeSort

mergeTwoLists

q_descend

q_merge