2024q1 Homework1 (lab0)

# 2024q1 Homework1 (lab0) contributed by < `eleanorLYJ` > #### Reviewed by `gawei1206` 測試分數的部分有提到偶爾會有95分的情況，想請問你知道這個問題發生在哪個部分，有對這個問題做出相對應的改善嗎 > 謝謝建議，目前嘗試讀懂〈Dude, is my code constant time?〉與檢測常數時間的程式碼但還未參透 [name= eleanorLYJ] #### Reviewed by `fatcatorange` 部份 commit message 可以更加詳述 > 謝謝建議，已新增敘述了 [name= eleanorLYJ] ## 開發環境 ```shell $ 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): 12 On-line CPU(s) list: 0-11 Vendor ID: GenuineIntel Model name: 12th Gen Intel(R) Core(TM) i5-12450H CPU family: 6 Model: 154 Thread(s) per core: 2 Core(s) per socket: 8 Socket(s): 1 Stepping: 3 CPU max MHz: 4400.0000 CPU min MHz: 400.0000 BogoMIPS: 4992.00 Virtualization features: Virtualization: VT-x Caches (sum of all): L1d: 320 KiB (8 instances) L1i: 384 KiB (8 instances) L2: 7 MiB (5 instances) L3: 12 MiB (1 instance) NUMA: NUMA node(s): 1 NUMA node0 CPU(s): 0-11 Vulnerabilities: ``` ## 針對佇列操作的程式碼實作 > 得分: 100/100 (偶爾 95/100) ### `q_new` > [commit 21e3c61](https://github.com/eleanorLYJ/lab0-c/commit/21e3c612a4526f0d931c9c8d3db5dd3e943d1120) :::danger 對應到數學公式，function 應翻譯為「函數」，後者就像是台「機器」，它能夠將集合 A 裡面的每個元素「唯一地」對應到集合 B 裡的一個元素。但在 C 語言一類的通用程式語言中，function 未必具備數學函數的意涵，也就是缺乏「唯一對應」的特性，例如對於 time 來說，給定同樣的輸入，卻會在不同時間點得到不同的結果，在 C 語言一類的通用程式語言中，甚至可省略傳回值，後者就不符合「函數」的行為。因此，當在通用的程式設計中，function 應翻譯為「函式」，表示「衍生自數學函數的常式 (routine)」。 $\to$ [資訊科技詞彙翻譯](https://hackmd.io/@sysprog/it-vocabulary) ::: <s>函數</s> 函式目的: 建立空的佇列，回傳指標實作: 為了回傳指向有效結構的指標，考慮到使用 malloc 函式配置記憶體時，當配置失敗，函式會回傳 `NULL` 指標，為了避免出現初始化佇列發生未定義行為 (Undefined Behavior)，因此在此有多做判斷。發現 `list.h` 中有 `INIT_LIST_HEAD(struct list_head *head)`，該函式會將`head` 的`prev` 與 `next` 指向 `head` 完成初始化。 :::danger 避免非必要的項目縮排 (即 `* ` 和 `- `)，以清晰、明確，且流暢的漢語書寫。 ::: > commit message 中應可更詳細描述作法和想法 > [name=fatcatorange] 新增敘述的 [Commit 8e11a](https://github.com/eleanorLYJ/lab0-c/commit/8e11a9a1ca3937e72089612133926995e64516fa) ### `q_free` 將佇列所佔據的記憶體都釋放 `list_for_each_safe` 允許在迭代中刪除節點。閱讀 [Linux 核心原始程式碼巨集: container_of](https://hackmd.io/@sysprog/linux-macro-containerof) 理解container_of 的用法，在此函式中，用於尋找佇列中的各個 `element_t`。在我完成 `q_insert_head()` 與 ` q_insert_tail()` 兩個函式後，使用`make check` 發現佔據的記憶體反而比在完成上述兩個函式時變多了，因此才發現我未在`q_free()` 中將 `struct element_t` 中的 `char *value`釋放。參考 [2024 年 Linux 核心設計/實作課程作業 —— lab0 (A)](https://hackmd.io/@sysprog/linux2024-lab0/%2F%40sysprog%2Flinux2024-lab0-a) 的圖片: ![image](https://hackmd.io/_uploads/BknGq1t2T.png) 因此我將程式碼改成以下 ```diff list_for_each_safe (node, next, l) { element_t *ele = container_of(node, element_t, list); + free(ele->value); free(ele); } free(l); ``` 然後，我發現 `queue.h` 中有 `q_release_element()` ，可以避免如以上撰寫時的粗心並且增加整體的可讀性。 ### q_insert_head() > 未修改結尾空终止字元: [commit c4b77a2](https://github.com/eleanorLYJ/lab0-c/commit/c4b77a2785924afbefb72713cd82b516cc017d7e) :::danger 避免非必要的項目縮排 (即 `* ` 和 `- `)，以清晰、明確，且流暢的漢語書寫。 ::: 在佇列開頭插入給定的新節點閱讀 strncpy 的使用方式在完成 `insert_head()` 與 `q_remove_head()` 後，發現`make test`的結果，並未通過主要測試 `insert_head` 與 `remove_head` 兩函式的 `trace-01-ops`。因此我找 `/scripts` 中 `trace-01-ops.cmd`，根據 `trace-01-ops.cmd` 裡的命令，逐一找出未通過測試的答案。 ```bash $./qtest cmd> option fail 0 cmd> option malloc 0 cmd> new l = [] cmd> ih gerbil l = [gerbilU��] cmd> ih bear l = [bearU�� gerbilU��] cmd> rh dolphin Removed bearU�� from queue ERROR: Removed value bearU�� != expected value dolphin l = [gerbilU��] ``` 結果出現非預期的 "��"亂碼，這時我才發現複製字串的結尾缺少了結尾空终止<s>字符串</s> 字串 (null-terminated string)。在複製的字串最後加上'/0'後，便通過 `trace-01-ops` 的測試。 :::danger string 的翻譯是「字串」 ::: ```diff + copyStr[len] = '\0'; strncpy(copyStr, s, len); newNode->value = copyStr; list_add(&newNode->list, head); ``` :::danger 列出對應的 GitHub commit 超連結即可，不用張貼完整程式碼。僅在需要討論時，才列出關鍵程式碼。 ::: ### q_insert_tail 在佇列尾端插入給定的新節點與 `q_insert_head()`邏輯相似 ### q_remove_head() 在佇列開頭移去給定的節點實作過程發現忘記檢查 bufsize，之後又在補上。 ```diff element_t *rmElement = list_first_entry(head, element_t, list); list_del(&rmElement->list); + if (sp && bufsize > 0) { - if (sp) { strncpy(sp, rmElement->value, bufsize - 1); sp[bufsize - 1] = '\0'; } ``` #### 關於靜態分析 :::danger 避免非必要的英語和漢語交雜書寫，若你想用英語書寫開發紀錄，則整份都該以英語書寫，反之亦然。 ::: ##### 問題1 ```bash queue.c:53:24: error: syntax error [syntaxError] copyStr[len] = '\0'; ^ Fail to pass static analysis. ``` ```diff + strncpy(copyStr, s, len); + copyStr[len] = '\0'; - copyStr[len] = '\0'; - strncpy(copyStr, s, len); ``` > 我多次rebase 此commit 的基礎，但它無法正常工作。 Cppcheck不斷告訴我靜態分析失敗。 #### 問題 2 ``` queue.c:85:1: error: Unmatched '{'. Configuration: ''. [syntaxError] { ^ queue.c:85:1: error: Unmatched '{'. Configuration: 'INTERNAL'. [syntaxError] { ^ queue.c:85:1: error: Unmatched '{'. Configuration: 'LIST_POISONING'. [syntaxError] { ^ queue.c:85:1: error: Unmatched '{'. Configuration: '__GNUC__;__clang__'. [syntaxError] { ^ Fail to pass static analysis. ``` 我只是加了{}，然後它就通過了靜態分析。太奇怪了。 ```diff - if (!head || list_empty(head)) + if (!head || list_empty(head)) { return NULL; + } ``` :::warning 你可能找到 Cppcheck 的錯誤，確認最新的 Cppcheck 是否存在同樣的問題。 ::: :::danger 查閱第一手材料，例如 C 語言規格，不要把自己專業的成長交給大語言模型。 ::: ### `q_size` > [commit 86e6406](https://github.com/eleanorLYJ/lab0-c/commit/86e640652990dbc1c9909f203ceb94de87dc6a9d) 計算目前佇列的節點總量 ### q_delete_mid 移走佇列中間的節點，詳見 [LeetCode 2095. Delete the Middle Node of a Linked List](https://leetcode.com/problems/delete-the-middle-node-of-a-linked-list/description/) 使用快慢指標（Fast-slow Pointers）找到中間節點為了省略指向中間節點的前一個節點的指標，因此我慢指針的型態為指標的指標。為了讓快指標走完單向鏈結串列時，讓慢指標停在中間節點的前一個節點，因此慢指標從下一個指向head的dummy開始移動。 :::danger 沒必要先用 C++ 程式語言撰寫，直接以 C 語言開發。 ::: 後來想到只要讓快指標提前移動，就不需要 dummy 節點了。程式碼 version 2 ```diff if(!head || !head->next) return NULL; - ListNode *dummy = new ListNode(0, head); - ListNode *fast = head, **slow = &dummy; + ListNode *fast = head->next->next, **slow = &head; // find the middle node while (fast && fast->next) { fast = fast->next->next; slow = &((*slow)->next); } - if (fast != head) + ListNode* tmp = (*slow)->next; ``` :::danger 善用 `diff`，列出存在差異的程式碼。 ::: 回到倉儲（Repository），想起意識到自己 leetcode 僅是移除 (remove) 非刪除 (delete)。又回到 leetcode 上，將程式碼改成釋放記憶體的版本: 程式碼 version 3 ```diff + delete(tmp); return head; } ``` 然而作業中不同於 leetcode 題目中是處理單向鏈結串列，而是實作環狀雙向鏈結串列，想想只需要快慢指標的想法就可以完成這個函式。 [commit 1e0fc45](https://github.com/eleanorLYJ/lab0-c/commit/1e0fc456ecc16595aef1bf5562f26edf8044b0d4) :::warning 針對環狀雙向鏈結串列，能否提出更快的程式碼？ ::: todo: 嘗試將一指標從頭向後，另一指標從尾向前移動找中間節點，這樣是否會更快 ### `q_delete_dup` 用指標的指標`cur`指向確定不重複的節點。迭代過程中的 `ptr` 與 `ptr2` - 前者的值為是否重複的基準 - 後者是要找到不同於基準的值的節點同樣地，我在 leetcode [Remove Duplicates from Sorted List II](https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/description/)上使用 C 驗證以上想法</s> :::danger 沒必要用 C++，強化 C 語言程式設計。 ::: ```c struct ListNode* deleteDuplicates(struct ListNode* head) { if (!head) return head; struct ListNode *newhead; struct ListNode **curr = &newhead; struct ListNode *ptr = head; while (ptr) { bool isDup = false; struct ListNode *ptr2 = ptr->next; // Check for duplicates while there are next nodes while (ptr2 && ptr->val == ptr2->val) { isDup = true; ptr2 = ptr2->next; } if (!isDup) { *curr = ptr; curr = &(*curr)->next; } else if (!ptr2) { *curr = NULL; } ptr = ptr2; } return newhead; } ``` ### q_swap: :::danger 避免非必要的項目縮排 (即 `* ` 和 `- `)，以清晰、明確，且流暢的漢語書寫。 ::: 交換佇列中鄰近的節點 1. 記錄當前節點對的尾節點。 2. 反轉當前節點對的順序。 3. 如果有前一組交換節點對，則將其與當前組連接。 4. 更新兩個變數，指向代表前一對尾的指標 (`prevPairEnd`) 和指向該對開始的指標 (`currPairStart`) ，為迭代到下一對節點做準備。 :::danger 注意用語。 ::: 我先在 leetcdoe [24. Swap Nodes in Pairs](https://leetcode.com/problems/swap-nodes-in-pairs/description/) 上使用 C 驗證想法。 ```c struct ListNode* swapPairs(struct ListNode* head) { if (!head) return NULL; struct ListNode *currPairStart = head; struct ListNode *prevPairEnd = NULL; struct ListNode *newHead = head; if (head->next) { newHead = head->next; } while (currPairStart && currPairStart->next) { struct ListNode *pairEnd = currPairStart->next; currPairStart->next = pairEnd->next; pairEnd->next = currPairStart; if (prevPairEnd) { prevPairEnd->next = pairEnd; } prevPairEnd = currPairStart; currPairStart = currPairStart->next; } return newHead; } ``` > <s>寫得很醜，有改進空間</s> >1. 因為以上用了兩個if判斷head，希望能夠減少if的使用 >2. 因為寫以上程式的時候，靠著leetcode測試，不斷修改，因此整個迭代邏輯是用拼湊的接著想看其他人是用什麼邏輯寫完這題 :::danger 具體說明哪邊要改進，而非籠統的「寫得很醜」。 ::: :::warning 沒必要看上面這些實作不佳的討論，你可以做更好！ ::: 新的嘗試，雖然不符合 leetcode 題意，但若作業只追求兩兩翻轉的效果就可以用以下程式碼 :::danger 說好的空白字元呢？ ::: 指標 `cur`指向每一對 pair 的第一個節點將 pair 值用 XOR swap 作交換，每次迭代移動兩步，直到 cur 指向的pair內不足兩個節點，便停止迭代 ```c struct ListNode* swapPairs(struct ListNode* head) { if (!head) return NULL; for (struct ListNode* cur = head; cur&&cur->next; cur=cur->next->next) { struct ListNode *first = cur; struct ListNode *second = cur->next; // swap the value first->val ^= second->val; second->val ^= first->val; first->val ^= second->val; } return head; } ``` :::danger 使用作業規範的程式碼縮排風格。 ::: 作業內的實作也是 XOR Swap [Commit d72248](https://github.com/eleanorLYJ/lab0-c/commit/d72248dcc2fb3b6bbe62ede61a8e43d6372d4e15) - 用 `uintptr_t` 將 `char *` 轉成整數型別 > the following type designates an unsigned integer type with the property that any valid pointer to void can be converted to this type, then converted back to pointer to void, and the result will compare equal to the original pointer: uintptr_t (C99 7.18.1.4) :::danger 查閱辭典關於 assign 的解釋，考慮到漢語的書寫慣例，不該偷懶用「賦值」，本處應為「指派」之義。 ::: - 然後發現，<s>賦值</s> 指派表達式中的左運算元不可以是 lvalue > An assignment operator stores a value in the object designated by the left operand. An assignment expression has the value of the left operand after the assignment, but is not an lvalue. (C99 6.5.16) ```c first->value = (char *) ((uintptr_t) first->value ^ (uintptr_t) second->value); second->value = (char *) ((uintptr_t) first->value ^ (uintptr_t) second->value); first->value = (char *) ((uintptr_t) first->value ^ (uintptr_t) second->value); ``` ### q_reverse 以反向順序重新排列鏈結串列，該函式不該配置或釋放任何鏈結串列節點，換言之，它只能重排已經存在的節點; :::danger 避免非必要的項目縮排 (即 `* ` 和 `- `)，以清晰、明確，且流暢的漢語書寫。 ::: 參考影片 [Reverse a Doubly Circular Linked List](https://youtu.be/NFgEy5fv23E?si=DdpmuQ151qMK3sLi)中的作法: 將每個節點的 `prev` 與 `next`交換，最終將 `head` 指向原鏈結串列的`tail` ```c void q_reverse(struct list_head *head) { if (!head || list_empty(head)) return; struct list_head *currNode = head; struct list_head *nextNode = currNode->next; while (nextNode != head) { nextNode = currNode->next; // Swap the current node's next and prev pointers currNode->next = currNode->prev; currNode->prev = nextNode; currNode = nextNode; } head = currNode->next; } ``` :::danger 使用作業規範的程式碼縮排風格 ::: 上述程式碼中，要讓 head 指向原鏈結串列 tail 的地方，靜態檢查失敗。 ```bash queue.c:178:10: style: Variable 'head' is assigned a value that is never used. [unreadVariable] head = currNode->next; ^ Fail to pass static analysis. ``` 回想起在[你所不知道的C語言：指標篇](https://hackmd.io/@sysprog/c-pointer)看到的概念: > C 語言中，萬物皆是數值 (everything is a value)，函式呼叫當然只有 call-by-value。「指標的指標」(英文就是 a pointer of a pointer) 是個常見用來改變「傳入變數原始數值」的技巧。使用指標的指標更改傳入函式的數值。 ```c struct list_head **indirect = &head; *indirect = currNode->next; ``` ### q_reverseK > [commit db57db2](https://github.com/eleanorLYJ/lab0-c/commit/db57db2b6ed76f59bde24768139946ad5b99ff46) 指定每 k 個節點為一組，進行反向順序排列詳見 LeetCode 25. Reverse Nodes in k-Group 想法: 迭代過程,將每k個節點截斷成獨立的list，再呼叫q_reverse()，再將這k個節點接回原始lisr 實作參考`yanjiew1` ### q_sort > [commit fa03314](https://github.com/eleanorLYJ/lab0-c/commit/fa033149f5756b4a0891ba50739d45aa9605cd28)   `q_sort` 呼叫 `mergesort_list()` :::danger 1. 你如何確保目前的測試已涵蓋排序演算法最差的狀況？ 2. 如果不用遞迴呼叫，你該如何實作排序？ ::: #### mergesort_list 遞迴呼叫 `mergesort_list()` , 使用快慢指標找到中間節點, 接著拆成兩個環狀串列, 直到把串列拆至只剩一個節點,接著呼叫 mergeTwoLists() #### mergeTwoLists 此函式參數接受將兩個已排序的環狀雙向串列合併為一個環狀串列。迭代將使用strcmp比較後確定的節點加到額外的空串列後, 直到把某一串列為空。當一個串列用盡，使用 list_splice_tail_init 和 list_splice 追加另一個串列的剩餘節點。 #### 測試 mergesort 結合作業2的 timsort 測試，小幅修改[commit fa03314](https://github.com/eleanorLYJ/lab0-c/commit/fa033149f5756b4a0891ba50739d45aa9605cd28)寫的遞迴版本 mergesort ，一併做測試結果在[commit 3fe74](https://github.com/eleanorLYJ/lab2/commit/3fe747f347d74c0076cf84f85efbffdd3fd1b315) 我測試資料設計成6種類別，分別為(0)全部隨機資料、(1)遞增資料、(2)遞減資料、(3)遞增資料並隨機交換3次、(4)遞增資料隨機交換7次、(5)每64個數字作為一個 run 組成的資料、(6)每64個數字作為一個 run 組成的資料並在同一個 run 以20％機率隨機交換 (7)全部資料以同一個隨機值組成而此 [commit fa03314](https://github.com/eleanorLYJ/lab0-c/commit/fa033149f5756b4a0891ba50739d45aa9605cd28)能通過所有隨機資料的測試, 但在遞增資料時，mergeTwoLists 函式會進入無窮迴圈中。 > TODO: 暫時我看不出來哪裡有問題，稍後用GDB看變數的變化小幅修改 [andy155224](https://hackmd.io/@sysprog/HJmB5x5Hn) 的 mergeTwoLists 函式，仍然沒有通過全部測試另外發現了幾個原本實作的缺陷 1. 所有隨機的資料沒有排序成功。 2. 資料個數調成2的冪, 然而發現我分割後的兩個串列大小不等大 3. `mergeTwoList` 跟 `visitorckw` 實作 `timsort` 的 `merge` 函式有相同目的, 我決定重複使用後者函式, 但要注意的 `merge` 函式考慮的是兩鏈結串列非環狀的並且沒有 dummy node 每一種資料測試的大小為 32788 = $2^{15} +20$ ``` ==== Testing recursive merge_sort ==== type == 0 Elapsed time: 775 Comparisons: 38661 List is not sorted type == 1 Elapsed time: 692 Comparisons: 28169 List is sorted type == 2 Elapsed time: 1085 Comparisons: 171629 List is sorted type == 3 Elapsed time: 553 Comparisons: 28169 List is sorted type == 4 Elapsed time: 512 Comparisons: 28169 List is sorted type == 5 Elapsed time: 569 Comparisons: 34963 List is sorted type == 6 Elapsed time: 556 Comparisons: 35834 List is sorted type == 7 Elapsed time: 1066 Comparisons: 199771 List is sorted ``` 以下每一種資料測試的大小仍為 32788 = $2^{15} +20$ ``` ==== Testing recursive merge_sort ==== type == 0 Elapsed time: 4068 Comparisons: 450115 List is sorted type == 1 Elapsed time: 2191 Comparisons: 246040 List is sorted type == 2 Elapsed time: 1664 Comparisons: 245820 List is sorted type == 3 Elapsed time: 1871 Comparisons: 273882 List is sorted type == 4 Elapsed time: 2128 Comparisons: 307399 List is sorted type == 5 Elapsed time: 3277 Comparisons: 404392 List is sorted type == 6 Elapsed time: 3840 Comparisons: 440152 List is sorted type == 7 Elapsed time: 1808 Comparisons: 246040 List is sorted ``` ### q_descend 在 [LeetCode 2487. Remove Nodes From Linked List](https://leetcode.com/problems/remove-nodes-from-linked-list/) 寫 1. 天真的版本(導致超時) - `ptr` 為指向符合題意的節點, `biggest` 為每次迭代範圍中能找到的最大節點 - 從 `head` 開始迭代, 判斷最大節點 `biggest`, `ptr` 指向`biggest`, 下一次迭代的起點就是從`biggest`的下一節點開始, 直到把此鏈結串列的最後一節點加到 `ptr` 上若鏈結串列上的值是遞減,最壞時間複雜度就會達 $O(n^2)$ ```c struct ListNode* removeNodes(struct ListNode* head) { struct ListNode *cur = head->next; struct ListNode *newHead = head; struct ListNode **ptr = &newHead; while (cur && cur->next) { struct ListNode *biggest = *ptr; while (cur) { if (cur->val > biggest->val) { biggest = cur; } cur = cur->next; } *ptr = biggest; // next iteration cur = biggest->next; ptr = &((*ptr)->next); } return newHead; } ``` :::danger 移除 C++ 程式碼，除非你要彰顯 C++ 特有之語言特徵。 ::: :::danger 程式語言的標注是 `cpp`，而非 `c++`，後者不為 HackMD 所識別。減少對 C++ 的參照，本作業要強化學員對 C 語言的掌握，過程中應適度查閱 C 語言規格書。 ::: 2. 改用c語言與遞迴方式解這題優點: 時間複雜度 $O(n)$ 缺點: 空間變成複雜度 $O(n)$ ```c ** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ struct ListNode* removeNodes(struct ListNode* head) { if(!head || !head->next) { return head; } struct ListNode *ans = removeNodes(head->next); if(head->val >= ans->val) { head->next = ans; return head; } return ans; } ``` 3. 作業實作因為作業實作環狀鏈結串列，換個方向迭代就可以改善天真版的效率問題反向迭代紀錄最小節點，串列尾端因為不需再跟下一節點故是當前最小，接著向前迭代，若當前最小節點比該比較節點大就刪除，反之更新當前最小節點 [Commit 0a53875](https://github.com/eleanorLYJ/lab0-c/commit/0a53875a9f6b7575a2738b9293f79f0ccd8d289c) ### q_ascend > [Commit 915e1c3](https://github.com/eleanorLYJ/lab0-c/commit/915e1c3f5ffda9d451eefbc5fc834f0b72dc0584) 想法相似於 q_descend ### q_merge 合併所有已排序的佇列，並合而為一個新的已排序佇列 #### 失敗版本 - 想要使用 `sortTwolists()` 去實現頭尾相接的合併作法，但未得到預期結果 ```c int q_merge(struct list_head *head, bool descend) { if (!head || list_empty(head)) return 0; if (list_is_singular(head)) return list_entry(head->next, queue_contex_t, chain)->size; int queueSize = q_size(head); queue_contex_t *context; while (queueSize > 1) { list_for_each_entry (context, head, chain) { queue_contex_t *tailContext = list_entry(head->prev, queue_contex_t, chain); if (context == tailContext) break; context->q = mergeTwoLists(context->q, tailContext->q, descend); // tailContext->size = 0; INIT_LIST_HEAD(tailContext->q); list_del_init(head->prev); } queueSize = (queueSize +1)/2; } return list_first_entry(head, queue_contex_t, chain)->size; } ``` - 學習 GDB 工具，我中斷點設在 `queue.c` 裡的 `q_merge()` 處，希望執行下一行(`step` 或 `next`)，卻會跳去 `harness.c` 中`exception_setup()` 中的 `sigsetjmp`。回頭看 `qtest.c` 呼叫 `q_merge` 的地方 ```c set_noallocate_mode(true); if (current && exception_setup(true)) len = q_merge(&chain.head, descend); exception_cancel(); set_noallocate_mode(false); ``` - 目前不清楚呼叫 q_merge 的下一步，為什麼會執行 if 條件句中的函式 - TODO: 1. 釐清GDB 使用方式 -> 閱讀 [GDB 文件](https://sourceware.org/gdb/current/onlinedocs/gdb.html/Sample-Session.html#Sample-Session) 2. 理解 qtest 的執行過程 -> 以下紀錄理解過程 > 題目的要求: 不能把 queue_contex_t 的節點移除掉 0.0 ### 另一版參考 `SPFishcool` 寫法想法簡單，將所有的串列相接再排序 [Commit fa03314](https://github.com/eleanorLYJ/lab0-c/commit/fa033149f5756b4a0891ba50739d45aa9605cd28) :::danger 考慮因素是什麼？量化表現如何？拾人牙慧不難，但精準評判很難。 ::: >此 commit 的修改較多， commit message 描述應更詳細。 >[name=fatcatorange] 新增敘述的 [Commit 8f750](https://github.com/eleanorLYJ/lab0-c/commit/8f7505b89b57088f7ae1b112db2f16810af66830) ## valgrind `$ make valgrind` 沒有看到記憶體相關問題。 ### valgrind massif 閱讀 [Massif: a heap profiler](https://valgrind.org/docs/manual/ms-manual.html) 與參考[cymizer/](https://hackmd.io/@cymizer/2021q1_lab0#%E4%BB%A5-Valgrind-%E5%88%86%E6%9E%90%E8%A8%98%E6%86%B6%E9%AB%94%E5%95%8F%E9%A1%8C) ```shell $ valgrind --tool=massif ./qtest -f traces/trace-01-ops.cmd $ massif-visualizer massif.out.* ``` 原始程式運行時配置的記憶體，約在執行 340000 ms 時 memory heap size 急速地降低，最終記憶體會歸 0。  TODO: 用其他方式表達 :::danger 文字訊息不要用圖片展現！ ::: 然而我將 `harness.c` 中的 `test_free()` 的 free() 註解掉。最終記憶體並未歸0。  ## 釐清 GDB 的 next 與 step 如果要 GDB 要執行的該行是函式呼叫 (function call) 執行 next，下一行會停在函式完成之後。執行 step，下一行會停在被呼叫的函式的第一行因此 - step: 命令適合時機在於逐行檢查代碼，並且深入函式内部。 - next: 命令適合時機用於快速跳過函式，關注主調用函式的執行流程。 ## 理解 qtest 的流程閱讀 lab0 的 [qtest 命令直譯器的實作](https://hackmd.io/@sysprog/linux2024-lab0/%2F%40sysprog%2Flinux2024-lab0-b#qtest-%E5%91%BD%E4%BB%A4%E7%9B%B4%E8%AD%AF%E5%99%A8%E7%9A%84%E5%AF%A6%E4%BD%9C)，期望解我在使用 GDB 執行我失敗版本的`q_merge` 時的疑惑。從上述文章能得知，qtest執行順序 > main → run_console → cmd_select → interpret_cmd → parse_args 因此我去找倉儲（Repository）中對應的程式碼，期望能找到與 `harness.c` 的`exception_setup()`相關的線索。在 `console.c` 中的 `interpret_cmd` 函式負責解析參數，之後將參數傳給 `interpret_cmda()`中 ```c char **argv = parse_args(cmdline, &argc); bool ok = interpret_cmda(argc, argv); ``` `interpret_cmda` 函式目的是要在 cmd_list 找對應指令，接著執行指令。 `next_cmd` 的結構體為 `cmd_element_t`，而在 `cmd_element_t` 結構體裡有 operation 成員，這成員為指向函式的指標。 ```c // in static bool interpret_cmda(int argc, char *argv[]) while (next_cmd && strcmp(argv[0], next_cmd->name) != 0) next_cmd = next_cmd->next; if (next_cmd) { ok = next_cmd->operation(argc, argv); ``` 執行的指令就會對應 qtest.c 中的 `do_*` 接下來我看 `qtest.c` 的 `do_merge` 函式，因為我對 `q_merge` 函式有興趣。找到對 `do_merge` 中其中一段程式碼: ```c set_noallocate_mode(true); if (current && exception_setup(true)) len = q_merge(&chain.head, descend); exception_cancel(); set_noallocate_mode(false); ``` 在執行 q_merge 前會呼叫 `exception_setup()` 函式。而我中斷點設`q_merge` 函式內，執行`run` 與 `next` 命令後，卻也會停在`exception_sepup()`上。 ```c bool exception_setup(bool limit_time) { if (sigsetjmp(env, 1)) { /* Got here from longjmp */ jmp_ready = false; // 省略 return false; } /* Got here from initial call */ jmp_ready = true; // 省略 return true; } ``` 接著查 [sigsetjmp](https://linux.die.net/man/3/sigsetjmp) 是甚麼? `int sigsetjmp(sigjmp_buf env, int savesigs);` sigsetjmp的功能: 負責處理錯誤與中斷。保存`env` 中堆疊(stack)的內容/環境(context/environment)。而若 savesigs 非零, 會把行程(process)的 signal mask 也存進 `env`中疑問[signal mask](https://www.gnu.org/software/libc/manual/html_node/Process-Signal-Mask.html)是甚麼? > The collection of signals that are currently blocked is called the signal mask. Each process has its own signal mask. sigsetjmp 的回傳值，只分 0 與非 0。回傳 0代表是直接使用，而回傳非 0 代表是 siglongjmp 跳躍到此處。因此，我使用 GDB 觀察到執行 `exception_setup` 的部分，假設是因為執行到 `q_merge.c` if 判斷式內中使用的 `exception_sepup` 函式，那我預期在 GDB 中執行 next 後就會停在`jmp_ready = true;` 行。並非如此，反而是停在`jmp_ready = false;` ```shell cmd> merge Breakpoint 1, q_merge (head=head@entry=0x5555555664c0 <chain>, descend=false) at queue.c:395 395 { (gdb) next 0x000055555555b5ce in exception_setup (limit_time=<optimized out>) at harness.c:255 255 if (sigsetjmp(env, 1)) { (gdb) next 257 jmp_ready = false; ``` 因此這說明是因為 siglongjmp 而執行到了 `if (sigsetjmp(env, 1))` 搜尋整個 `harness.c` 找 siglongjmp，只有 `trigger_exception` 函式有用到 siglongjmp。從函式註解得知，該函式是要返回最近的異常設置 (exception setup)。因此是異常(exception) 造成我 GDB 觀察的結果。然而這部分是什麼異常造成，我目前不知道。這部分我應該再學其他GDB使用方式。 --- ## shuffle ### shuffle 命令在 `qtest.c` 新增 shuffle 命令與 do_shuffle 函式後，在 queue.h 新增 q_shuffle prototype ```diff +void q_shuffle(struct list_head *); ``` 開始在 queue.c 撰寫 q_shuffle 函式 q_shuffle實作[Fisher–Yates shuffle 演算法](https://hackmd.io/@sysprog/linux2024-lab0-d#%E5%9C%A8-qtest-%E6%8F%90%E4%BE%9B%E6%96%B0%E7%9A%84%E5%91%BD%E4%BB%A4-shuffle) > 1. 先用 q_size 取得 queue 的大小 len。 > 2. 隨機從 0 ~ (len - 1) 中抽出一個數字 random，然後 old 將指向從前面數來第 random 個節點，new 會指向最後一個未被抽到的節點，將 old 和 new 指向的節點的值交換，再將 len - 1。 > 3. 隨著 len 大小變小，已經被抽到過，並交換值到 queue 後面的會愈來愈多，直到所有的節點都已經被抽到過，shuffle 就結束。然後當我想要寫 commit message 時，被 pre-commit.hook 擋下來了 ``` [!] You are not allowed to change the header file queue.h or list.h ``` 所以最後我拿掉在 queue.h 的改動。 >拿掉後是否需要額外的動作來完成此函式？若沒有為何一開始要改動 queue.h? >[name=fatcatorange] 最終完成的[commit 2a66a61](https://github.com/eleanorLYJ/lab0-c/commit/2a66a614964b113b469ed58a6da183ffa5aab646) :::danger 列出程式碼的主要目的是討論和檢討，若你沒有這舉措，就不該列出程式碼。 ::: 在 `./qtest` 測試命令效果 ```bash cmd> new l = [] cmd> ih RAND 10 l = [cnnsqxu ogdecp oirgbrjka hrcegl uckygdnfh okmdyiq bgsalbdq idzzlyu yefynyg crelx] cmd> shuffle l = [hrcegl oirgbrjka cnnsqxu ogdecp idzzlyu bgsalbdq uckygdnfh okmdyiq yefynyg crelx] ``` ### 統計方法驗證 shuffle 虛無假說為 > $H_0$（虛無假說）: shuffle 的結果發生的機率相同，遵守 Uniform distribution 使用 [lab0(D)](https://hackmd.io/@sysprog/linux2024-lab0-d#%E6%B8%AC%E8%A9%A6%E7%A8%8B%E5%BC%8F) 提供的測試程式，計算 chi-squared test statistic $X^2$ 以下 shuffle 的結果明顯只4種組合，在 q_shuffle 函式印出亂數值，在./qtest 手動測試 q_shuffle 函式值，就明顯感覺亂數重複。 ```bash dict_values([11251, 0, 0, 0, 0, 38749, 0, 0, 0, 0, 0, 0, 0, 0, 18179, 0, 31821, 0, 0, 0, 0, 0, 0, 0]) len: 24 Expectation: 4166 Observation: {'1234': 11251, '1243': 0, '1324': 0, '1342': 0, '1423': 0, '1432': 38749, '2134': 0, '2143': 0, '2314': 0, '2341': 0, '2413': 0, '2431': 0, '3124': 0, '3142': 0, '3214': 18179, '3241': 0, '3412': 31821, '3421': 0, '4123': 0, '4132': 0, '4213': 0, '4231': 0, '4312': 0, '4321': 0} chi square sum: 613167.409505521 ``` 更改程式碼 ```diff for (last = head->prev; last != head && len; len--, ptr = head->next, last = last->prev) { - time_t t; - srand((unsigned) time(&t)); int r = rand() % len; ``` 計算 chi-squared test statistic $X^2$就降低至18.8 ```bash dict_values([4120, 4181, 4203, 4174, 4164, 4089, 4239, 4237, 4116, 4157, 4157, 4181, 4235, 4297, 4132, 4130, 4218, 4125, 4114, 4189, 4036, 4108, 4177, 4221]) len: 24 Expectation: 4166 Observation: {'1234': 4120, '1243': 4181, '1324': 4203, '1342': 4174, '1423': 4164, '1432': 4089, '2134': 4239, '2143': 4237, '2314': 4116, '2341': 4157, '2413': 4157, '2431': 4181, '3124': 4235, '3142': 4297, '3214': 4132, '3241': 4130, '3412': 4218, '3421': 4125, '4123': 4114, '4132': 4189, '4213': 4036, '4231': 4108, '4312': 4177, '4321': 4221} chi square sum: 18.810849735957753 ``` 自由變換的變數只有 24 個，我自由度選擇 23。因為 $X^2$ 為 18.8，P value介於 0.10 至 0.9 因為 P value（0.1~0.9）> alpha（0.05），統計檢定的結果不拒絕虛無假說（$H0$ ) ![image](https://hackmd.io/_uploads/SkFAbwlCp.png) 圖片來源: [卡方分布表](https://www.obhrm.net/index.php/%E5%8D%A1%E6%96%B9%E5%88%86%E5%B8%83%E8%A1%A8_Chi-Square_Probabilities) ### 查閱文件得知 rand, srand, time 用法 rand 函式用途於計算出 0 到 RAND_MAX 的偽隨機整數。 > The rand function computes a sequence of pseudo-random integers in the range 0 to RAND_MAX. (C99 7.20.2.1) 而 RAND_MAX 在規格書上寫至少有32767。 > The value of the RAND_MAX macro shall be at least 32767. srand 函式的參數會作為 rand 函式計算時的亂數種子。 > The srand function uses the argument as a seed for a new sequence of pseudo-random numbers to be returned by subsequent calls to rand. (C99 7.20.2.2) time 函式用途於得知當前時間。 > The time function returns the implementation’s best approximation to the current calendar time 然而在 linux 上才有定義 [time 函式](https://man7.org/linux/man-pages/man2/time.2.html?fbclid=IwAR12sa9bffmgCD_qxcSreONpEgQXqYrApqwAmfTvDWGddgxML_dfwOkV1L8) 的單位是秒數。 > time() returns the time as the number of seconds since the Epoch, 1970-01-01 00:00:00 +0000 (UTC). 因此原本以為在迴圈中重新指派當前時間當亂數種子就能每次獲得亂數，然而這樣看來，迴圈跑得速度太快，所以在同一秒中內的所有亂數都會相同啊。  --- ## ttt ### 新增hlist 與 ttt 命令將 Linux 核心的 linux/list.h 標頭檔與 hlist 相關的程式碼抽出，成為 hlist.h 並修改 qtest 程式，使其新增 ttt 命令 [Commit 0667a9f](https://github.com/eleanorLYJ/lab0-c/commit/0667a9fd4d6e03ac430757e10731ff0874a1bf2d)    ### 擴充引用 ttt 命令新增 option 中 mode 的這個變數。若 mode 為 0，代表允許使用者切換「人 vs.電腦」， mode 為 1 指「電腦 vs. 電腦」的對弈，最後 mode 2 為引入 coroutine ，並且處理鍵盤事件，當按下 'p' 能夠暫停或回復棋盤畫面，按下'q' 能夠中止當局電腦與電腦的對弈。 TODO: 1. 處理 mode 非 0, 1, 2 的情況 2. 鍵盤事件改處理 Ctrl + p 與 Ctrl + q ### 引入 coroutine 與處理鍵盤事件之前，我先理解了三個專案 1. 協同式多工的 [coro](https://github.com/sysprog21/concurrent-programs/tree/master/coro) 2. 搶佔式多工的 [preempt_sched](https://github.com/sysprog21/concurrent-programs/tree/master/preempt_sched) 3. [mazu editor](https://github.com/jserv/mazu-editor) ### [coro](https://github.com/sysprog21/concurrent-programs/tree/master/coro) 看懂此專案，最核心的大概就是每次 setjmp 或 longjmp，該會到程式碼的哪裡。首先會在 `main()` 先初始化好變數與確定任務( task )的執行順序，之後就進入 `schedule()`。一進入 `schedule()`，就會用 setjmp 設跳轉點。 tasks 是存函式指標的陣列，在此函數的第 9 行，就會運行指定函式。假設這裡的 tasks 為 {task0, task1}，ntasks 為 2 ，那麼首先執行 `task0` 函式。 ```c= void schedule(void) { static int i; setjmp(sched); while (ntasks-- > 0) { struct arg arg = args[i]; tasks[i++](&arg); printf("Never reached\n"); } task_switch(); } ``` `INIT_LIST_HEAD(&task->list);` 是要創建 `task0` 的節點。執行到函式的第 11 行的 `setjmp()`，設置一個跳轉點，並且由於是直接呼叫 `setjmp`，所以進入 if 判斷式中，將此任務的插入到存有全部任務的串列(`tasklist`)，之後做 `longjmp`，跳回 `schedule()` 第 5 行，並接續執行 `task1` 函式。而 `task0` 與 `task1` 的結構相似，同樣會在會進入 if 判斷式之後，又再次回到 `schedule()`的第 5 行的 `setjmp`。 ```c= void task0(void *arg) { struct task *task = malloc(sizeof(struct task)); strcpy(task->task_name, ((struct arg *) arg)->task_name); task->n = ((struct arg *) arg)->n; task->i = ((struct arg *) arg)->i; INIT_LIST_HEAD(&task->list); printf("%s: n = %d\n", task->task_name, task->n); if (setjmp(task->env) == 0) { task_add(task); longjmp(sched, 1); } task = cur_task; for (; task->i < task->n; task->i += 2) { if (setjmp(task->env) == 0) { long long res = fib_sequence(task->i); task_add(task); task_switch(); } task = cur_task; printf("%s: resume\n", task->task_name); } printf("%s: complete\n", task->task_name); longjmp(sched, 1); } ``` 將 tasks 裡的任務都執行完了，就不會再進入 while 迴圈，此時做 `task_switch()`，從 `tasklist` 取得目前第一個任務，並且執行。目前這任務就是 task0，`longjmp` 會跳至 task0 的第 11 行，但不會進入 if 判斷式中，之後，執行到 `task0` 的 18 行又存下當下的 env，並將該任務的節點又加入 tasklist 中，之後又換 `task1` 的 if 判斷式處，之後處理 task1 的任務內容 .....。結果就會是 task0 ，從數字從 i 開始，每次加 2 直到達於n為止，每次將數字算斐波那契數列後，控制權就會轉給task1。因此 task0 就會與 task1 交錯執行。 ```c static void task_switch() { if (!list_empty(&tasklist)) { struct task *t = list_first_entry(&tasklist, struct task, list); list_del(&t->list); cur_task = t; longjmp(t->env, 1); } } ``` ### [preempt_sched](https://github.com/sysprog21/concurrent-programs/tree/master/preempt_sched) > todo: 解釋 ```c static int preempt_count = 0; static void preempt_disable(void) { preempt_count++; } static void preempt_enable(void) { preempt_count--; } static void timer_handler(int signo, siginfo_t *info, ucontext_t *ctx) { if (preempt_count) /* once preemption is disabled */ return; /* We can schedule directly from sighandler because Linux kernel cares only * about proper sigreturn frame in the stack. */ schedule(); } static void local_irq_save(sigset_t *sig_set) { sigset_t block_set; sigfillset(&block_set); sigdelset(&block_set, SIGINT); sigprocmask(SIG_BLOCK, &block_set, sig_set); } static void local_irq_restore(sigset_t *sig_set) { sigprocmask(SIG_SETMASK, sig_set, NULL); } ``` > ualarm - schedule signal after given number of microseconds ``` useconds_t ualarm(useconds_t usecs, useconds_t interval); ``` The ualarm() function causes the signal SIGALRM to be sent to the invoking process after (not less than) usecs microseconds. The delay may be lengthened slightly by any system activity or by the time spent processing the call or by the granularity of system timers. Unless caught or ignored, the SIGALRM signal will terminate the process. -> usecs：第一次触发SIGALRM信号的时间 interval：第一次触发SIGALRM信号之后每隔 interval 微秒再觸發一次SIGALRM信号以微秒为单位 ### mazu edit > todo: 加解釋 ```c void disable_raw_mode() { if (tcsetattr(STDIN_FILENO, TCSAFLUSH, &ec.orig_termios) == -1) panic("Failed to disable raw mode"); } void enable_raw_mode() { if (tcgetattr(STDIN_FILENO, &ec.orig_termios) == -1) panic("Failed to get current terminal state"); atexit(disable_raw_mode); struct termios raw = ec.orig_termios; raw.c_iflag &= ~(BRKINT | ICRNL | INPCK | ISTRIP | IXON); raw.c_oflag &= ~(OPOST); raw.c_cflag |= (CS8); raw.c_lflag &= ~(ECHO | ICANON | IEXTEN | ISIG); raw.c_cc[VMIN] = 0; raw.c_cc[VTIME] = 1; open_buffer(); if (tcsetattr(STDIN_FILENO, TCSAFLUSH, &raw) == -1) panic("Failed to set raw mode"); } ``` ### 定點數 ## TODO - 閱讀 [The perfect patch](https://www.ozlabs.org/~akpm/stuff/tpp.txt) 修改 commit message