2025q1 Homework1 (lab0)

contributed by < BigMickey69 >

作業書寫規範:

• 無論標題和內文中，中文和英文字元之間要有空白字元 (對排版和文字搜尋有利)
• 文字訊息 (尤其是程式執行結果) 請避免用圖片來表示，否則不好搜尋和分類
• 共筆書寫請考慮到日後協作，避免過多的個人色彩，用詞儘量中性
• 不要在筆記內加入 [TOC] : 筆記左上方已有 Table of Contents (TOC) 功能，不需要畫蛇添足
• 不要變更預設的 CSS 也不要加入任何佈景主題: 這是「開發紀錄」，用於評分和接受同儕的檢閱
• 當在筆記中貼入程式碼時，避免非必要的行號，也就是該手動將 c= 或 cpp= 變更為 c 或 cpp。行號只在後續討論明確需要行號時，才要出現，否則維持精簡的展現。可留意「你所不知道的 C 語言: linked list 和非連續記憶體」裡頭程式碼展現的方式
• HackMD 不是讓你張貼完整程式碼的地方，GitHub 才是！因此你在開發紀錄只該列出關鍵程式碼 (善用 diff 標示)，可附上對應 GitHub commit 的超連結，列出程式碼是為了「檢討」和「便於他人參與討論」
• 留意科技詞彙的使用，請參見「資訊科技詞彙翻譯」及「詞彙對照表」
• 不要濫用 :::info, :::success, :::warning 等標示，儘量用清晰的文字書寫。:::danger 則僅限授課教師作為批注使用
• 避免過多的中英文混用，已有明確翻譯詞彙者，例如「鏈結串列」(linked list) 和「佇列」(queue)，就使用該中文詞彙，英文則留給變數名稱、人名，或者缺乏通用翻譯詞彙的場景
• 在中文敘述中，使用全形標點符號，例如該用「，」，而非 ","。注意書名號的使用，即 〈 和 〉，非「小於」和「大於」符號
• 避免使用不必要的 emoji 字元

我是成大資訊116乙的石維廉，以下是紀錄著我在2025年「Linux 核心設計」Lab0遇到的問題與開發的過程紀錄。

q_size

遇到問題之 — hook 警告一些進去卻看不到的字元
嗯，看到心情就很差

輸入e進去後，預設是使用 vi 而不是 vim ，只是小事但我們都知道沒有人會自願用 vi 編輯。

嗯。
看到這個時我笑出來了
在這種情況下我也沒辦法，只好使用神器: $ git commit –no-verify

q_delete_dup():

完成了 Leetcode 上對應的題目，努力的把程式寫的"有品味"。但一旦到了 lab0 這卻發現乍看 list_head 的定義中沒有 val 或其他儲存資料方式，又頓時敢到了無比困惑…

• 向 GPT 求助 -> 雙手一攤，它不會 ❌
• 向同學求助 -> 甚至還沒開始做… ❌
• 向助教協助 -> 助教人非常好🥹 ✅

助教說要用 list_entry 來看，因為它是侵入式結構。
再次仔細看過 list.h, queue.c & queue.h
此時才發現包覆 list_head 結構的結構叫 "element_t"，而list_entry利用記憶體相鄰的特性去找到包著的結構。

list_entry 與 container_of 毫無差別，

依 GPT 的解釋，if 的兩種版本差在編譯器的版本，有些編譯器沒有 typeof 有些有。邏輯上一樣，不過有 typeof 的版本多個安全網，如果 type 上不一樣會丟出 error，另一版不會停止運行，造成錯誤。
（示意圖）（往回推到 dog 結構）

q_swap

開始抓到 lab0 的規律，寫起來更快、問題也沒有向前面幾個那麼多。Leetcode 寫完搬過來，再改成支援 doubly-linked-list 即可

q_reverse

非常的直觀，從head開始把所有的 next 與 prev 交換。

q_reverseK

第一版程式碼：

邏輯

pp 在原地、pp2 先走到 k 節點位置 next_group，紀錄下一組的初始節點，交換兩者後再修正 *next 與 *prev 指標，最後設 pp 與 pp2 到 next_group。
示意圖：

問題：說實話我找不到，但程式就是困再迴圈中出不去。詢問 GPT 也沒啥用。

走頭無路時就該回頭!

第二版程式碼：

這個版本是把 Leetcode 對應題目寫完、修改、再搬過來的。第一版的邏輯依靠 *prev，這一版則是使用stack。

一指標跑過 k 個節點，把路過的節點放入一 stack 之中。
依序 pop 出 stack 裡的節點們，並適當更新他們的 *next 與 *prev 指標。

優點：

• 能動、邏輯上比較好理解

缺點：

• 邏輯上第一版若能動的話比較快
• 用 malloc 而使用到更多的記憶體

自己還不夠熟練，這個函式也是一直遇到問題並不停修正

q_sort

第一時間想到的排序法是 quicksort ，多數情況下是最快的排序法，第二是使用 Bubblesort 來進行排序，一來程式較為簡單，二來記憶體使用率比較低。但後來覺得不能逃避問題，想得到就該做，因此毅然決然使用 qsort。

先用一 pointer 掃過每個節點並加入一陣列之中，陣列大小從5開始，若空間不夠則將 realloc 擴大到兩倍。紀錄完成陣列後再使用 <stdlib.h> 中的 qsort 進行排列，最後再 free 掉創的矩陣。

short int cmp_ascend(const void *a, const void *b)
{
    struct list_head *A = *(struct list_head **) a;
    struct list_head *B = *(struct list_head **) b;

    const element_t *nodeA = list_entry(A, element_t, list);
    const element_t *nodeB = list_entry(B, element_t, list);

    return nodeA->value - nodeB->value;
}
short int cmp_descend(const void *a, const void *b)
{
    struct list_head *A = *(struct list_head **) a;
    struct list_head *B = *(struct list_head **) b;

    const element_t *nodeA = list_entry(A, element_t, list);
    const element_t *nodeB = list_entry(B, element_t, list);

    return nodeB->value - nodeA->value;
}

void q_sort(struct list_head *head, bool descend)
{
    if (list_empty(head))
        return;

    struct list_head *p = head->next;

    short int a_max = 5;
    short int a_size = 0;
    struct list_head **arr = malloc(sizeof(struct list_head *) * a_max);

    while (p != head) {
        arr[a_size++] = p;
        if (a_size == a_max) {
            a_max *= 2;
            arr = realloc(arr, sizeof(struct list_head *) * a_max);
        }
        p = p->next;
    }
    if (descend)
        qsort(arr, a_size, sizeof(struct list_head *), cmp_descend);
    else
        qsort(arr, a_size, sizeof(struct list_head *), cmp_ascend);

    arr[0]->prev = head;
    head->next = arr[0];
    for (int i = 0; i < a_size - 1; i++) {
        arr[i]->next = arr[i + 1];
        arr[i]->next->prev = arr[i];
    }
    arr[a_size - 1]->next = head;
    head->prev = arr[a_size - 1];

    free(arr);
}

優點：

• 在 list 夠大的情況下仍比 bubblesort 快

缺點：

• 須耗費大量記憶體儲存每個節點
• 應該有更好的作法，只是此時還沒想到

嘗試commit 時會遇到此問題，意思是當realloc失敗時目前的作法會導致 memory leak，得架個安全往才行

arr = realloc(arr, sizeof(struct list_head *) * a_max);

改為

struct list_head **new =
                realloc(arr, sizeof(struct list_head *) * a_max);
if (!new) {
    free(arr);
    arr = NULL;
    return;
}

後續問題-git hook

若仔細看上面的程式碼會發現 cmp_descend 與 cmp_ascend 兩個函式的 return type 為 short int ，但 qsort 希望傳進去的函式回傳 int ，因此在 git push 時會被擋下來。

修正後進行 commit 後問題來了，git hook 會認為 cmp 為 typo 而無法進行此修正。

理論上 q_reverseK 等也不是正確的英文單字，或許在設定檔中有允許這些函式的單字？後續嘗試了在函式前面加 "functions" 或將函式名用「`」符號包住，但依然無法 commit。

前面教授提過函式命名規則，不應該亂縮寫，不過感覺 compare 縮成 cmp 還算常見?

- 最後決定把 compare 改成 cmp 暫時略過此問題。
`

更：

後來發現函式中的比較邏輯有大問題，當時寫的時候誤把字串當作整數而使用減法進行比較，已更正改用 strcmp 進行比較。

q_ascend

邏輯上不會太難，先從最後一個節點開始往前走，並開始紀錄當下出現過的最大節點，若比較小則跳過並釋放記憶體、比較大則接上 linked list。

我認為最大的難點是如何紀錄目前最大的數值，因每個節點中儲存的資料均為字串，無法向整數那麼容易紀錄。

Idea💡:
創一字串 max ，並分配足夠多的記憶體（這邊假設每一節點中的字串都 < 256 個字元）
將最後一節點的字串複製進去當作初始化，接下來比較節點大小時都使用 strcmp 函式去做。

第一版程式碼：

#define LONGEST_STRING_LENGTH 256
int q_ascend(struct list_head *head)
{
    if (list_empty(head))
        return -1;

    struct list_head **pp = &head->prev;
    struct list_head *prev = head;

    char *max = malloc(LONGEST_STRING_LENGTH);
    const element_t *last_e = list_entry(*pp, element_t, list);
    strcpy(max, last_e->value);

    while (*pp != head) {
        const element_t *e = list_entry(*pp, element_t, list);

        if (strcmp(max, e->value) < 0) {
            strcpy(max, e->value);
            (*pp)->next = prev;
            prev->prev = *pp;
            prev = *pp;
            *pp = (*pp)->prev;
        } else {
            struct list_head *temp = (*pp)->prev;
            list_del(*pp);
            *pp = temp;
        }
        
    }
    *pp = prev;
    free(max);
    return 0;
}

commit 時會被 hook 擋下，因為 strcpy 似乎是個不安全的函式

strcpy:
The strcpy built-in function does not check buffer lengths
and may very well overwrite memory zone contiguous to the 
intended destination. In fact, the whole family of functions 
is similarly vulnerable: strcpy, strcat and strcmp.

解決辦法✅：

• 改用 strdup() 函式

q_descend

邏輯上與q_ascend相同，差別在：

if (strcmp(max, e->value) > 0) {

一行，descend 中改為

if (strcmp(max, e->value) < 0) {

q_merge

第一眼看到 q_merge 是有點不知所錯的，只有傳入一個 list_head *head，不確定具體是要什麼跟什麼合起來。
研讀queue.h 努力理解後，發現一結構 queue_context

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

我認為每個 list_head 的頭都被這個結構包住，而 queue_context就好比一串項鍊，連接著一個個 queue。

若要合併，邏輯上就是反覆操作著「合併兩 list 」這件事，但及便是這樣仍有有兩種作法可實行：

一、依序合併

先將A、B合併，再合併B、C，C、D…以此類推
每一次的合併一次得走 n 個節點，假設總共有 k 個 queue ，則總共得走 n * k次，時間複雜度:
- O(n) = n * k

缺點：

• 執速度較慢

二、兩兩合併

兩兩一組的將每個節點合併，若 list 為奇數則跳過落單的。
每一次的合併一次得走 n 個節點，假設總共有 k 個 queue ，則總共得走 n log2(k)次，時間複雜度:
- O(n) = n * log k

優點：

• 執行速度較快

注意！

以上所有函式都是先寫完並 commit 後，再隨後去改，因為一直不清楚怎麼去測各個函式才好，所以決定先把能做的地方做一做，後面再來修正。

Bug 地獄

將 queue.c 給 chatGPT o3-mini-high 看過一遍，修正一些它看到的潛在問題。例如：

• list_head 為 NULL 指標
• list 中只有 head
• 某些函式刪除節點時沒釋放記憶體

當我執行 & ./qtest會出現以下錯誤訊息↓

Commit history 中有兩個 commit 沒有 change-ID，原因是當初 commit 時加了指令 –no-verify，而使用該指令的原因均是檢查文法時遇到了問題而無法 commit

1. ".gitignore" 會被 git hook 擋下，它認為 gitignore 不是個合法單字
2. "kfree" 也會被 git hook 擋下，它認為 kfree 也不是合法單字

解法：

• 執行git rebase -i HEAD~20
• 編輯兩個有問題的 commit
• 文字間加個底線來繞過偵測↓
  （gitignore -> git_ignore 、 kfree -> k_free）
• 最後再 git push origin HEAD --force
  （雖然這麼做有點危險，但想不到什麼更好的方法QQ）

接下來開始執行 traces 中的各個檔案：
traces-01-ops.cmd ✅
traces-02-ops.cmd ERROR

• 修正 insert_tail 更改指標時邏輯錯誤
• 確保 q_delete_mid 的 value 記憶體也會被釋放

traces-03-ops.cmd ERROR

• q_sort 的邏輯使用了一 array ，初衷是犧牲記憶體來提升速度，但很明顯這是不被允許的，因此重新寫了一次。新版使用最笨最不會出錯的 bubble sort 來進行排序。

q_merge

(此時已經過5小時)
撞到了牆壁，看不出 bug 可能的點，gpt 更是沒用，房間充滿了無助感。
我想說獨立開個新檔案，把要用的函式通通帶進來，再使用printf去細找問題。

但，最後仍無望。

有尋求教授協助，但教授是請我研讀C語言規格書，並使用 GDB 來分析問題。

後來出去玩了幾個小時，回家後洗個澡靜下心來思考，我其實沒理解過 qtest 的原理。當我們寫 new 時，程式會關注並印出此 list，it 與 ih 指令也是擴充並印出此 list。那麼問題來了，執行 merge 後只會剩下一 list ，那此時 l 顯示的 list 究竟是被刪掉的 list 還是最後留下來的 list 呢？會顯示哪個？

錯誤一：

原來 q_merge 不會刪掉其他list…

錯誤二：

q_merge 回傳值應為最後一 list 的 size

用 for 迴圈走過整個 chain，將每個節點與第一個節點 merge，即修正完 q_merge。

traces-04-ops.cmd ✅
traces-05-ops.cmd ✅
traces-06-ops.cmd ERROR

• q_delete_dup 函式有問題，遲遲找不太到問題，決定直接打掉重寫最快。很多問題來自當初寫函式時對list.h, queue.h 與各個結構還不夠熟悉，所以會操作錯誤或是漏掉一些細節e.g. 更新 q->size 或是善用提供的函式與 macro。
• q_descend 邏輯不變，但幾乎整個重寫，原本的作法是將節點刪掉並繼續往回走，但沒有刪清楚也沒有更新好各節點的 prev 與 next 指標，也並未回傳新串列的 size。
• q_ascend 與 q_descend 大同小異，簡單改 strcmp 判斷式中的大小寫即可。
• q_reverseK 也是動大刀，原先作法紙上行得通但礙於使用 malloc 違法就得換一個作法。新作法相似於 q_sort ，創一新 list_head，走過 k 個節點後開始往回走並一一加到新的 list_head 中，反覆操作，最後再把 list_head 與 原先的 head 結合。

traces-07-string.cmd ✅
traces-08-robust.cmd ✅
traces-09-robust.cmd ✅
traces-10-robust.cmd ✅
traces-11-robust.cmd ✅
traces-12-robust.cmd ✅
traces-13-robust.cmd ERROR

• 修正 q_free 嘗試釋放 NULL 指標

traces-14-perf.cmd ERROR

就如上面所述，前面 q_sort 撞牆後改使用了 bubblesort ，但 bubblesort O(n^2)似乎太慢，無法通過測驗。

後來一樣整個重寫，這次決定使用 mergesort O(n * log n) 來提升速度。

嗯。

測驗後發現插入100000 時還沒問題，但一但插入1000000個元素就會Segmentation fault，或許樣本太大就會發生stack overflow？

！！這個問題尚未解決！！

traces-15-pref.cmd ERROR

• 很奇妙，q_reverse 函式只有交換 next 與 prev 指標，卻會導致 memory leak ，而程式碼的邏輯也非常簡單明瞭。

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

    struct list_head *p = head;
    do {
        struct list_head *temp = p->next;
        p->next = p->prev;
        p->prev = temp;
        p = temp;
    } while (p != head);
}

雖然敘述這麼寫，但我的 q_sort 卻在 50000 就會 Segmentation fault，即便理論上使用的是個 O(n * log n)的 mergesort。

• 此時，開始出現蠻大的挫折感。

！！這個問題尚未解決！！

traces-16-pref.cmd ✅
（即便 traces-16 裡插入了1000000個元素，也進行了 reverse，卻不會導致 memory leak）

traces-17-complexity.cmd:

就也不知道為什麼會這樣

！！這個問題尚未解決！！