Linux 核心專題: 重作第一次作業

執行人: jerry7961
專題解說影片

Reviewed by 'ken-LuWeiRu'

可以參考 https://hackmd.io/@sysprog/Syc7ROemA#效能分析
做效能分析

任務簡介

重作第一次作業，並強化若干子任務。

TODO: 重做 lab0，整合 Timsort，比較 Linux 核心的 `list_sort`

量化並分析程式表現 (設計實驗，考慮到資料排序演算法最差的狀況、cache / locality of reference, 資料亂度/分佈)

HackMD 不是讓你張貼完整程式碼的地方，而 GitHub 才是。
你若要張貼程式碼，就必定是因為你想討論或者提出後續的改進。
務必詳細閱讀第一次作業的規範！

`q_free`

先檢查佇列是否為空，若為空則 return 。
用 list_for_each_entry_safe 巨集走訪所有節點，並釋放節點。
最後釋放開頭節點。

void q_free(struct list_head *head)
{
    if (!head)
        return;
    element_t *cur, *next;
    list_for_each_entry_safe (cur, next, head, list) {
        q_release_element(cur);
    }
    free(head);
}

`q_insert_head`

一開始誤用 strcpy (如下) 。

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

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

    strcpy(new_element->value,s);
    if(!new_element->value){
        free(new_element);
        return false;
    }

    list_add(&new_element->list,head);
    return true;

}

strcpy(s1,s2) 的功能是複製字串 s2 到字串 s1 ，不會為 s1 分配内存， s1 的長度必須大於 s2 的長度。
因此在沒有為 new_element->value 分配內存的情況下直接用 strcpy(new_element->value,s) 會造成錯誤。
事先為 new_element->value 分配內存再用 strcpy 複製字串即可修正錯誤。

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

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

    new_element->value=malloc(strlen(s) + 1);
    if(!new_element->value){
        free(new_element);
        return false;
    }

    strcpy(new_element->value,s);
    list_add(&new_element->list,head);
    return true;

}

另一種做法是使用 strdup 來代替 strcpy ，strdup 會為字串分配內存空間，並返回新分配空間的指標。

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

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

    new_element->value=strdup(s);
    if(!new_element->value){
        free(new_element);
        return false;
    }

    list_add(&new_element->list,head);
    return true;

}

`q_insert_tail`

與 q_insert_head 的做法類似，差別是改用 list_add_tail。

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

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

    new_element->value = strdup(s);
    if (!new_element->value) {
        free(new_element);
        return false;
    }

    list_add_tail(&new_element->list, head);
    return true;
}

`q_remove_head`

q_remove_head 的作用是從鏈結串列的開頭移除一個元素。

首先檢查 head 是否為空指標，以及鏈結串列中是否至少有一個節點，確保鏈結串列存在且不為空。接著用 list_first_entry 取得鏈結串列第一個元素的指標，並透過 list_del 將這個元素從鏈結串列中移除。

如果 sp 不為 NULL ，使用 strncpy 函式將被移除元素的字串 (to_delete->value) 複製到 sp 指向的位址中。複製的字元數量最多為 bufsize - 1 ，這是為了在字串結尾預留一個位置，用來存放 \0 。

element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
    if (head && !list_empty(head)) {
        element_t *to_remove = list_first_entry(head, element_t, list);
        list_del(&to_remove->list);

        if (sp) {
            strncpy(sp, to_remove->value, bufsize - 1);
            sp[bufsize - 1] = '\0';

        }
        return to_remove;
    }

    return NULL;
}

`q_remove_tail`

與 q_remove_head 類似，差別在使用 list_last_entry 來取得要移除的元素。

`q_size`

使用 list_for_each 來走訪所有節點，每走訪一個節點 count 值就加一。

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

    int count = 0;
    struct list_head *temp;
    list_for_each (temp, head)
        count++;

    return count;
}

`q_delete_mid`

使用快慢指標，快指標每次前進兩步，慢指標每次前進一步。

當鏈結串列包含奇數個節點時，快指標會停在最後一個節點上，此時慢指標正好指向鏈結串列的中間節點。
當鏈結串列包含偶數個節點時，快指標會回到鏈結串列的 head ，此時慢指標將指向中間兩個節點中的第二個。為了使 q_delete_mid 能夠刪除中間兩個節點中的第一個，需要增加一個 if 語句來調整慢指標的位置。

 if (fast == head) {
     slow = slow->prev;
 }

`q_delete_dup`

q_delete_dup 是要在鏈結串列已經排序好的狀況下，移走其中具有重複內容的節點。

使用 list_for_each_safe 來走訪鏈結串列中的每個節點。
mark_del 用來標記是否遇到重複節點。
在走訪過程中，根據當前節點與前後節點的關係，需要處理以下幾種情況：

當前節點已經是最後一個節點，此時用 mark_del 來判斷當前節點是否與前一個節點重複，如果重複則刪除它。
當前節點與下一個節點內容相同，此時刪除當前節點，並將 mark_del 設為 true ，表示已遇到重複節點。
當前節點與下一個節點內容不同，但 mark_del 為 true，這表示當前節點與上一個節點內容相同，因此刪除當前節點，並將 mark_del 設為 false。
非前三種情況，代表當前節點與下一個節點內容不同，與上一個節點也不同，無需執行任何操作。

`q_swap`

q_swap 的作用是交換鏈結串列中鄰近的節點。

如果鏈結串列中的節點數量小於等於 1 ，無需執行任何操作。
如果鏈結串列中的節點數量大於 1 ，則 q_swap 從頭部節點的下一個節點開始走訪鏈結串列。對於每對相鄰節點，q_swap 會先將它們從鏈結串列中移除，然後以交換後的順序將它們重新插入到鏈結串列中。這個過程會一直重複，直到走訪完鏈結串列的所有節點。

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

    struct list_head *node = head->next;
    while (node != head && node->next != head) {
        struct list_head *nextNode = node->next;

        list_del(node);
        list_del(nextNode);

        list_add(nextNode, node->prev);
        list_add(node, nextNode);

        node = node->next;
    }
}

`q_reverse`

從頭部節點開始走訪鏈結串列，交換每個節點的 next 和 prev 指標以反轉鏈結串列方向，直到走訪完整個鏈結串列。

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

    struct list_head *current = head;
    struct list_head *temp = NULL;

    do {
        temp = current->next;
        current->next = current->prev;
        current->prev = temp;

        current = current->prev;
    } while (current != head);
}

`q_sort`

一開始使用 Insertion Sort ，無法通過測資，後來參考同學寫法，改用 Merge Sort 。

void merge(struct list_head *l_head,
           struct list_head *r_head,
           struct list_head *head)
{
    struct list_head temp_list;
    INIT_LIST_HEAD(&temp_list);

    while (!list_empty(l_head) || !list_empty(r_head)) {
        struct list_head *chosen;

        if (list_empty(l_head)) {
            chosen = r_head;
        } else if (list_empty(r_head)) {
            chosen = l_head;
        } else {
            element_t *l_entry = list_entry(l_head->next, element_t, list);
            element_t *r_entry = list_entry(r_head->next, element_t, list);
            chosen =
                (strcmp(l_entry->value, r_entry->value) <= 0) ? l_head : r_head;
        }

        list_move_tail(chosen->next, &temp_list);
    }

    list_splice_tail_init(&temp_list, head);
}
void merge_sort_recursive(struct list_head *head, int length)
{
    if (length <= 1)
        return;

    int mid = length / 2;
    struct list_head left, right;
    INIT_LIST_HEAD(&left);
    INIT_LIST_HEAD(&right);

    struct list_head *current = head->next;
    for (int i = 0; i < mid; i++) {
        struct list_head *next = current->next;
        list_move_tail(current, &left);
        current = next;
    }
    list_splice_tail_init(head, &right);

    merge_sort_recursive(&left, mid);
    merge_sort_recursive(&right, length - mid);

    INIT_LIST_HEAD(head);
    merge(&left, &right, head);
}

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

    int length = 0;
    struct list_head *pos;
    list_for_each (pos, head) {
        length++;
    }

    merge_sort_recursive(head, length);
}

void q_sort(struct list_head *head, bool descend)
{
    merge_sort(head);
    if (descend) {
        q_reverse(head);
    }
}

`q_merge`

~~![image](https://hackmd.io/_uploads/ByoIcC-wC.png)~~

+++ TESTING trace trace-03-ops:
# Test of insert_head, insert_tail, remove_head, reverse and merge
ERROR: Freed queue, but 2 blocks are still allocated
==665==    112 bytes in 2 blocks are still reachable in loss record 1 of 1
==665==    at 0x4848899: malloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==665==    by 0x10F2E7: test_malloc (harness.c:133)
==665==    by 0x10F6EC: q_new (queue.c:17)
==665==    by 0x10CDA3: do_new (qtest.c:155)
==665==    by 0x10DFD1: interpret_cmda (console.c:181)
==665==    by 0x10E586: interpret_cmd (console.c:201)
==665==    by 0x10E987: cmd_select (console.c:610)
==665==    by 0x10F273: run_console (console.c:705)
==665==    by 0x10D3C3: main (qtest.c:1258)
==665== 
trace-03-ops 0/6

文字訊息「不要」用圖片展現。

收到，已更正

在 trace-03-ops 出現以上錯誤，經過排查，問題出在 q_merge 函式。原始版本的 q_merge 創建了一個新的 first_queue 指標，它用來指向第一個遇到的非空鏈結串列，這個鏈結串列將作為所有鏈結串列合併的目標，所有其他鏈結串列的元素都會被合併到這個 first_queue 中，其他鏈結串列在合併到 first_queue 後 q 指標會被設為 NULL，但相關記憶體沒有被釋放，導致錯誤。修改 q_merge 函式後， trace-03-ops 可順利通過。

注意用語：

memory 是「記憶體」

務必使用本課程教材規範的術語。

收到，已更正

原始版本：

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

    int total_elements = 0;
    queue_contex_t *context, *tmp;
    struct list_head *first_queue = NULL;

    list_for_each_entry_safe (context, tmp, head, chain) {
        if (!first_queue) {
            first_queue = context->q;
            total_elements += context->size;
        } else {
            list_splice_init(context->q, first_queue);
            context->q = NULL;
            total_elements += context->size;
        }
    }
    q_sort(first_queue, false);

    return total_elements;
}

修改版本：

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

    queue_contex_t *base_queue = list_first_entry(head, queue_contex_t, chain);
    if (list_is_singular(head)) {
        return base_queue->size;
    }

    queue_contex_t *queue_to_merge;
    struct list_head *current, *next;

    list_for_each_safe (current, next, head) {
        if (current == &base_queue->chain) {
            continue;
        }
        queue_to_merge = list_entry(current, queue_contex_t, chain);
        list_splice_tail_init(queue_to_merge->q, base_queue->q);
        base_queue->size += queue_to_merge->size;
    }

    q_sort(base_queue->q, descend);
    return base_queue->size;
}

TODO: 留意 lab0-c 記憶體佔用分析

善用 valgrind, massif, perf 等工具

透過 Massif 分析記憶體使用量

參考 alanjiang85 的說明，用 trace-eg.cmd 進行分析

透過 Valgrind 產生 massif 檔案

$ valgrind --tool=massif ./qtest -f traces/trace-eg.cmd

產生記憶體使用情形的時間分佈圖

$ massif-visualizer ./massif.out.59554

TODO: 修正 lab0-c 網頁伺服器的整合問題並整合 coroutine 來改進性能

留意 I/O Multiplexing Model，務必詳閱 Linux 核心設計: 針對事件驅動的 I/O 模型演化和並行程式設計: 排程器原理

Linux 核心專題: 重作第一次作業

Reviewed by 'ken-LuWeiRu'

任務簡介

TODO: 重做 lab0，整合 Timsort，比較 Linux 核心的 list_sort

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_sort

q_merge