Try   HackMD

linux2025-homework1

contributed by <leonnig>

作業書寫規範:

  • 無論標題和內文中，中文和英文字元之間要有空白字元 (對排版和文字搜尋有利)
  • 文字訊息 (尤其是程式執行結果) 請避免用圖片來表示，否則不好搜尋和分類
  • 共筆書寫請考慮到日後協作，避免過多的個人色彩，用詞儘量中性
  • 不要在筆記內加入 [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 字元

開發環境





























$ gcc --version
gcc (Ubuntu 13.3.0-6ubuntu2~24.04) 13.3.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:               11th Gen Intel(R) Core(TM) i5-1135G7 @ 2.40GHz
CPU family:               6
Model:                    140
Thread(s) per core:       2
Core(s) per socket:       4
Socket(s):                1
Stepping:                 1
CPU(s) scaling MHz:       23%
CPU max MHz:              4200.0000
CPU min MHz:              400.0000
BogoMIPS:                 4838.40
Virtualization:           VT-x     
L1d:                      192 KiB (4 instances)
L1i:                      128 KiB (4 instances)
L2:                       5 MiB (4 instances)
L3:                       8 MiB (1 instance)
NUMA node0 CPU(s):        0-7

針對佇列操作的程式碼實作

q_new

目標為建立一個空佇列，其next和prev皆指向自己。

查閱C語言記憶體管理的相關用法
根據ISO/IEC 9899:202y章節7.24.4

The pointer returned points to the start (lowest byte address) of the allocated space. If the space cannot be allocated, a null pointer is returned.

也就是說若配置失敗，會回傳空指標，須納入考量。

首先使用malloc去配置一段記憶體空間(size為list_head結構體的大小)，並且後續必須檢查配置是否成功，若失敗則回傳NULL，反之則可以利用list.h中的INIT_LIST_HEAD來完成next和prev的初始化。實作如下:

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

    return head;
}

不過經過make test的評分後發現，在test of malloc failure on new這邊反而沒拿到分數，會發生error，提示說仍有部分block是allocated。

因此我想確認NULL在記憶體中是否會佔據空間。

q_size

目標為取得佇列內部的結點數量(相當於佇列的長度)。

一開始直覺的想法是逐一走訪佇列中每個節點，再透過變數的累加來紀錄長度，但發現因為本作業是以雙向鏈結串列來去實作，也就是說佇列尾部的next不會是指向NULL，也就不能靠此來判斷是否已走訪到佇列尾部。

後來發現list.h中其實已經有提供list_for_each可以達成逐一走訪每個節點並檢查next是否指向head。

首先檢查該佇列是否為空或者NULL，是的話則回傳0，否則使用list_for_each逐一走訪結點並宣告一個計數器來紀錄結點數量。

q_insert_head

目標為將 element 插入到佇列的最前端。

我理解的圖示表示:

first_insert
用malloc為準備插入的新 element 配置記憶體空間，若配置失敗或 queue為NULL，則此次插入失敗。而根據queue.h中的要求，需要複製字串到value，於是我使用strcpy，為了避免複製過來的字串會超過value可以存放的，所以將value的記憶體空間配置為strlen(s)+1(+1為存放'\0'用)，最後使用list.h提供的 API list_add來實作，初始程式碼如下:

bool q_insert_head(struct list_head *head, char *s)
{
    element_t *new_node = malloc(sizeof(element_t));
    if(!new_node || !head)
        return false;
    new_node->value = malloc(strlen(s) + 1);
    strcpy(new_node->value, s);
    list_add(&new_node->list, head);

    return true;
}

不過在git commit時，遇到以下訊息:

Dangerous function detected in /home/user/linux2025/lab0-c/queue.c
35:    strcpy(new_node->value, s);

於是我查閱了 Common vulnerabilities guide for C programmers

The strcpy built-in function does not check buffer lengths and may very well overwrite memory zone contiguous to the intended destination.

因為strcpy不會檢查buffer長度，可能會覆蓋掉相鄰的記憶體空間，因此這邊改為使用strncpy，並且需要在尾部加入'\0'已得知字串的結尾。

strncpy(new_node->value, s, strlen(s));
new_node->value[strlen(s)] = '\0';

後來發現少了一些必要檢查，像是對新插入的 element 的 value 做 malloc，卻沒有檢查其後續配置記憶體是否成功，以下為修改後的程式碼:

+ if (!head || !s)
+        return false;
     element_t *new_node = malloc(sizeof(element_t));
-    if (!new_node || !head)
+    if(!new_node)
         return false;
     new_node->value = malloc(strlen(s) + 1);
+    if(!new_node->value){
+        free(new_node);
+       return false;
+    }

q_insert_tail

實作方式和q_insert_head基本大同小異，差別在於這邊是使用list_add_tail來插入到佇列尾部。

q_free

一開始的想法是讓他遍歷佇列中的每個element，並且使用free去釋放。
而在 commit 時會出現靜態分析的錯誤，是由於我將拿來釋放用的element宣告在遍歷的迴圈外面，改到迴圈內部後則通過靜態分析。

-   element_t *ele;
while (cur != head) {
-   ele = container_of(cur, element_t, list);
+   element_t *ele = container_of(cur, element_t, list);
    cur = cur->next;
    q_release_element(ele);
}

q_remove_head

檢查傳入的sp參數是否為NULL，若不為空則使用strncpy將要被移除的 element 的 value 複製到sp中，並且使用list_del移除佇列的第一個節點。

q_remove_tail

實作上和q_remove_head雷同，只是差在要移除的目標是在佇列尾部。

q_delete_mid

使用快慢指標的技巧，在迴圈中ptr每次走一步，fast走兩步，迴圈結束時，ptr所指向的節點即為佇列的中間節點。

在提交 commit 時遇到靜態分析錯誤

Running static analysis…
queue.c:124:27: style: Variable 'fast' can be declared as pointer to const [constVariablePointer] for (struct list_head *fast = head->next;

而這邊可以參照 你所不知道的 C 語言：指標篇 中 針對指標的修飾 (qualifier) 段落。

指標本身不可變更 (Constant pointer to variable): const 在 * 之後
char * const pContent;
指標所指向的內容不可變更 (Pointer to constant): const 在 * 之前
const char * pContent;
char const * pContent;

所以雖然fast會指向不同的list_head，但並不會修改list_head的內容，使用const修飾可以更清楚fast的作用。

-    for(，struct list_head *fast = head->next; 
+    for (const struct list_head *fast = head->next;
         fast->next != head && fast->next->next != head;
         fast = fast->next->next)

q_delete_dup

使用list_for_each_entry_safe來實作，此macro適合用在要對節點作移除或刪除的動作時，在迴圈中會依序去比較當下目標節點的value是否有相同，而在比較前我先宣告了3個 element_t:

struct list_head *ele, *safe, *dup;

ele 作為主要負責遍歷的指標，dup指向ele的下一個 element，用於檢查ele的下個 element 的 value 是否有重複，若有重複，則開始進行第二次遍歷，將dup指標依序往後移動直到遇到不跟ele->value重複的 element，而中間若有重複的 element 使用q_release_element直接移除，但這麼做可能會讓safe指向NULL，所以每一個 step 也要讓 safe跟著dup移動，才能確保ele下次指向safe的位址時是正確的。

而比較用的 function 我是使用 strcmp去作去作value的比較。

SO/IEC 9899:202y 章節7.27.4.3

The strcmp function returns an integer greater than, equal to, or less than zero, accordingly as the string pointed to by s1 is greater than, equal to, or less than the string pointed to by s2.

判斷當回傳的值為0時，代表此兩邊的字串內容相同。

初始實作如下:

list_for_each_entry_safe(ele, safe, head, list) {
    ptr = (&(ele->list))->next;
    bool check = false;
    if (ptr == head)
        return true;
    dup = list_entry(ptr, element_t, list);
    while (ptr != head && strcmp(dup->value, ele->value) == 0) {
        check = true;
        tmp = ptr->next;
        list_del(ptr);
        q_release_element(dup);
        ptr = tmp;
        dup = list_entry(ptr, element_t, list);
        safe = dup;
    }
    if (check) {             //ele also need be deleted
        list_del(&ele->list);
        q_release_element(ele);
    }
}

q_swap

宣告兩個主要的指標來固定指向準備交換的第一個和第二個節點，搭配 list_del 和 list_add來實現交換兩個相鄰節點的功能。

q_reverse

從佇列中第一個節點開始，依序移除，然後再加入到佇列頭部，這邊用到list_move，可以一次做到list_del和list_add，最後整條佇列掃完一遍即可完成反轉。

圖示:

reverse1.drawio (1)

reverse2.drawio

q_reverseK

先用LIST_HEAD初始化兩個 list_head，一個負責做反轉的，一個則是拿來存放反轉過後的節點。

LIST_HEAD(trans);   //reverse
LIST_HEAD(tmp);     //store

我的想法是先將 k 個節點從佇列中移除，這邊用到list_cut_position擷取前面 k 個節點，並且加入到trans中，然後使用q_ereverse將這 k 個節點反轉，在使用list_splice_tail_init加入到tmp的尾部，這樣才能保持原來每一組節點在佇列中的順序。

while(q_size(head) >= k){
    start = head->next;
    end = start;
    for(int i=1; i<k; i++){
        end = end->next;
    }
    list_cut_position(&trans, head, end);
    q_reverse(&trans);
    list_splice_tail_init(&trans,&tmp);
}

reversek1.drawio

reversek2.drawio

reversek3.drawio

而最後head為 empty 時，再把反轉好的佇列從tmp加回到head。

q_sort

原本 sort 是寫insertionsort，但在make test的時候會遇到時間複雜度無法降到

O(nlogn)，以及執行qtest時會報錯沒有stable sorting，於是選擇使用mergesort來實作，於是另外寫了兩個 function 來完成。

mergeTwoLists

功能: 將給予的兩條以排序好的 lists 進行 merge，由於還要可以做到任意選擇ascending和descending的排序。

判斷的條件是，當L1當前的值小於L2當前的值時，將 L1_ele 往後移，否則將 L2_ele 加入到 L1_ele 前方，而這是在ascending的情況下，但當是descending時，要讓條件判斷可以反過來。

所以判斷式可以加入XOR來幫忙判斷。

if ((strcmp(L1_ele->val, L2_ele->value) <= 0)^descend)
strcmp <= 0 descend result
1 0 L1_ele後移
1 1 L2_ele加入到L1_ele前面
0 0 L2_ele加入到L1_ele前面
0 1 L1_ele後移

而最後剩下不為空的那條list，再加入至另一端的尾部。
而這邊使用的是list_splice_tail_init，因為原本使用list_splice_tail時，在q_merge呼叫mergeTwoLists會出錯。

實作如下:

struct list_head *mergeTwoLists(struct list_head *L1,
                                struct list_head *L2,
                                bool descend)
{
    element_t *L1_ele = list_entry(L1->next, element_t, list),
              *L2_ele = list_entry(L2->next, element_t, list), *next;
    while (&L1_ele->list != L1 && &L2_ele->list != L2) {
        if ((strcmp(L1_ele->value, L2_ele->value) <= 0) ^ descend) {
            L1_ele = list_entry(L1_ele->list.next, element_t, list);
        } else {
            next = list_entry(L2_ele->list.next, element_t, list);
            list_move(&L2_ele->list, L1_ele->list.prev);
            L2_ele = next;
        }
    }

    list_splice_tail_init(L2, L1);

    return L1;
}

mergesort_list

功能: 將 list 以中點分割，並且遞迴下去，直到 list 內剩下一個節點時回傳。
在呼叫mergeTwoLists來將分割完的 lists 倆倆合併。

先用快慢指標找出 list 的中間節點，再以中間節點的下一個節點作為分割的位置，並且宣告一個新的list_head來連接被分割的 list，然後兩 list 再各自遞迴下去。

實作如下:

struct list_head *mergesort_list(struct list_head *head, bool descend)
{
    if (!head || list_empty(head) || list_is_singular(head))
        return head;


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


    LIST_HEAD(cut);
    cut.prev = head->prev;
    head->prev->next = &cut;
    slow->next->prev = &cut;
    cut.next = slow->next;
    slow->next = head;
    head->prev = slow;



    struct list_head *left = mergesort_list(head, descend),
                     *right = mergesort_list(&cut, descend);
    return mergeTwoLists(left, right, descend);
}

q_sort

此 function 呼叫執行mergesort_list。

q_ascend

一開始先宣告兩個struct list_head *，一個在前，一個在後

struct list_head *cmp = head->next;
struct list_head *ptr = cmp->next;

用while迴圈讓指標遍歷這條 list ，每次都會讓cmp指向的 element去和相鄰後方ptr指向的 element 去比較 value 大小，如果前者沒有比後者大，則兩個指標繼續往前走，但若前方的 value 大於後方，則將前方的 element，也就是cmp指向的 element 刪除，但因為刪除後，也不能保證此時ptr指向的點和更前面的點可以形成ascending，所以一旦完成了一次刪除後，就會讓cmp和ptr重新會到佇列最前方的位置重新遍歷，直到某次遍歷出現完全沒有刪除 element 的情況才會終止，而中止時也代表 list 已經為ascending。

while (ptr != head) {
    left = list_entry(cmp, element_t, list);
    right = list_entry(ptr, element_t, list);
    if (strcmp(left->value, right->value) > 0) {
        list_del(cmp);
        q_release_element(left);
        cmp = head->next;
        ptr = cmp->next;
    } else {
       cmp = ptr;
       ptr = ptr->next;
    }
}

q_descend

這邊的實作方式和q_ascending大同小異，差別在於判斷 element 的 value 大小時，因為是要降序，所以當前方的value小於後方時，刪除前方的 element。

q_merge

在寫此 function 之前需要先了解q_contex_t這個結透體以及整個queue的結構

q_merge2.drawio

每個佇列之間都是由chain這個 member 所連接在一起的，而我想要將其他佇列給合併起來，就必須取得q，而我使用container_of去取得q_contex_t結構體，有了結構體就能存取其中的成員了。

我的作法是使用list_for_each_safe，走訪 chain 上每個 node，並且取得q_ccontex_t，將裡面的 list 和第一個 queue去做合併，這邊使用前面寫過的mergeTwoLists，實作如下:

struct list_head *q_c = NULL, *safe = NULL;
queue_contex_t *tmp = container_of(head->next, queue_contex_t, chain);

list_for_each_safe(q_c, safe, head) {
    if (q_c != head->next) {
        queue_contex_t *merge = list_entry(q_c, queue_contex_t, chain);
        mergeTwoLists(tmp->q, merge->q, descend);
    }
}

不過在過程中有遇到問題，在我使用qtest測試的時候，我發現當我要 merge 到 first queue 的時候，只要我的 list 中的節點超過1個，就會引發錯誤:

Attempted to free unallocated block.

git rebase

先將上游的 branch 加入進來，將其命名為upstream

$ git remote add upstream git@github.com:sysprog21/lab0-c.git

使用git remote -v 檢查看看。

origin	git@github.com:leonnig/lab0-c (fetch)
origin  git@github.com:leonnig/lab0-c (push)
upstream  git@github.com:sysprog21/lab0-c.git (fetch)
upstream  git@github.com:sysprog21/lab0-c.git (push)

使用git fetch更新遠程的 repo。

$ git fetch upstream master

若有更改過但尚未 commit 的檔案，在rebase前可以用 stash 作暫存。

$ git stash

使用 rebase 將提交的 commit 移至最新的基底。

$ git rebase upstream/master

將更新公開推送到Github。

$ git push --force

等 rebase 成功後再用 git pop 將檔案還原回來。

以 Valgrind 分析記憶體問題

由於在 make test 時，第17個測試 it、ih、rt、rh 是否是 constant time，測試過程非常慢，想當然這項測試也沒有通過。
於是我使用 valgrind 搭配 massif 來檢查看看問題。

image

待完成

在 qtest 提供新的命令 shuffle

為了在qtest中新增命令，需要先了解qtest的運作機制。
閱讀 qtest 命令直譯器的實作 ，從中可以得知，我們撰寫的關於 queue 的操作命令，都是用cmd_element_t這個結構體包裝起來，而操作的函式則放在operation成員中，而這些命令則會被存放在 cmd_list 這個鏈結串列中。

一開始在consloe.c裡面並沒有找到跟佇列操作相關的函式，後來才在qtest.c裡面發現

Implementation of testting code for queue code.

而這些 queue code 又是如何被新增的。

在console.h中可以發現ADD_COMMAND巨集的定義，而他又會展開為add_cmd，所以根據作業說明，我需要在console_init中呼叫 shuffle，才可以增加這個新命令。

所以我需要在queue.c 中撰寫 q_shuffle，然後在qtest.c 中提供 do_shuffle 函式去呼叫queue.c。

但作業規定有提到不能修改 queue.h，所以我不能直接在裡面宣告 q_shuffle，我使用extern的方式去做外部宣告。

q_shuffle

使用 Fisher–Yates shuffle 去實作 shuffle。

剛開始的想法很單純，直接去判斷 len 是否大於0，每回合只要還大於0，就使用rand() 來獲得一個數值，也就是本回合old要指向的位置，而new則從最後一個節點開始逐回合往前，去跟old指向的節點做交換，而交換時我另外宣告了一個指標tmp來儲存new應該交換的位置，而交換的操作則是使用 list_move API 來完成，先將old移動到new的後方，再將new移動到tmp後方完成交換:

tmp = old->prev;
list_move(old, new);
list_move(new, tmp);
new = old->prev;
old = head->next;
len -= 1;

測試

使用測試程式進行1000000測試

樣本 觀察到的頻率 預期的頻率
(Oi−Ei)2Ei
[1, 2, 3, 4] 41899 41666 1.302956847309557
[1, 2, 4, 3] 41845 41666 0.768996303940863
[1, 3, 2, 4] 41798 41666 0.41818269092305477
[1, 3, 4, 2] 41914 41666 1.4761196179138867
[1, 4, 2, 3] 41432 41666 1.3141650266404263
[1, 4, 3, 2] 41811 41666 0.5046080737291797
[2, 1, 3, 4] 41579 41666 0.1816589065425047
[2, 1, 4, 3] 41616 41666 0.06000096001536025
[2, 3, 1, 4] 41099 41666 7.71585945375126
[2, 3, 4, 1] 41676 41666 0.00240003840061441
[2, 4, 1, 3] 41843 41666 0.7519080305284884
[2, 4, 3, 1] 41385 41666 1.8950943215091443
[3, 1, 2, 4] 41606 41666 0.08640138242211876
[3, 1, 4, 2] 41872 41666 1.018480295684731
[3, 2, 1, 4] 41747 41666 0.15746651946431142
[3, 2, 4, 1] 41525 41666 0.47715163442615083
[3, 4, 1, 2] 41604 41666 0.09225747611961792
[3, 4, 2, 1] 41833 41666 0.6693467095473528
[4, 1, 2, 3] 41656 41666 0.00240003840061441
[4, 1, 3, 2] 41555 41666 0.29570873133970144
[4, 2, 1, 3] 41501 41666 0.6534104545672731
[4, 2, 3, 1] 41745 41666 0.14978639658234533
[4, 3, 1, 2] 41782 41666 0.322949167186675
[4, 3, 2, 1] 41677 41666 0.002904046464743436
Total 20.32021312340997

X2 = 20.32021312340997

在此測試中是24個隨機樣本，自由度為23。

顯著水準（Significance level）α 測定為 0.05。

從卡方分布表

image

對照自由度23，因為 14.8480 < 20.3202 < 32.0069，所以我們的p value 介於 0.9 和 0.1之間。

因為 p value (0.1~0.9) > alpha (0.05)，統計檢定的結果不拒絕虛無假說，再搭配實驗的圖表可以看出結果大致是符合 Uniform distribution。

rand_out_2

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

lab0-c 中的 simulation

我去查看qtest.c的程式碼，發現在 queue_insert和queue_remove兩個函式中都有額外去判斷是否開啟 simulation 模式，以 insert 為例，其中有一個判斷式

pos == POS_TAIL ? is_insert_tail_const() : is_insert_head_const();

即判斷插入或刪除的位置，並且去呼叫is_insert_XXX_const()，而我在fixture.h中找到它的宣告，他是來自 is_##x##_const(void) 這個巨集會展開為DUT_FUNCS，而在 constant.h 裡面有對DUT_FUNCS的更仔細的定義

#define DUT_FUNCS  _(insert_head) _(insert_tail) _(remove_head) _(insert_tail)

可以發現它其實是展開為另外4個前置處理器，而在同個檔案內，繼續往下看可以發現他們展開後的樣子

#define DUT(x) DUT_##x

enum {
#define _(x) DUT(x),
    DUT_FUNCS
#undef _
};

可以看到_(x)會被替換成DUT(x)， 而DUT(x)又會被替換為DUT_##x ，搭配enum，最後會展開為

enum {
DUT(insert_head),  
DUT(insert_tail),  
DUT(remove_head),  
DUT(remove_tail),
}

再將DUT(x)替換掉

enum {
DUT_insert_head,  
DUT_insert_tail,  
DUT_remove_head,  
DUT_remove_tail,
}

而在fixture.h中有完整的定義了is_XXX_const

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

#define _(x) DUT_FUNC_IMPL(x)
DUT_FUNCS
#undef
Last changed by 
 
Cool-55
0
105

Read more

linux2025-homework2

contributed by &lt;leonnig&gt;

Mar 21, 2025
linux2025-idea

contributed by &lt;leonnig&gt;

Mar 9, 2025
Read more from Cool-55
Published on HackMD