2024q1 Homework1 (lab0)

contributed by < ollieni >

詳閱作業說明，指定的格式中有空白字元，留意各式細節，唯有重視小處並步步為營，方可挑戰原始程式碼規模超越三千七百萬行的 Linux 核心

開發環境

$ gcc --version
gcc (Ubuntu 9.4.0-1ubuntu1~20.04.2) 9.4.0
Copyright (C) 2019 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

$ lscpu
Architecture:                       x86_64
CPU op-mode(s):                     32-bit, 64-bit
Byte Order:                         Little Endian
Address sizes:                      39 bits physical, 48 bits virtual
CPU(s):                             4
On-line CPU(s) list:                0-3
Thread(s) per core:                 1
Core(s) per socket:                 4
Socket(s):                          1
NUMA node(s):                       1
Vendor ID:                          GenuineIntel
CPU family:                         6
Model:                              154
Model name:                         12th Gen Intel(R) Core(TM) i7-12700H
Stepping:                           3
CPU MHz:                            2688.004
BogoMIPS:                           5376.00
Hypervisor vendor:                  KVM
Virtualization type:                full
L1d cache:                          192 KiB
L1i cache:                          128 KiB
L2 cache:                           5 MiB
L3 cache:                           96 MiB
NUMA node0 CPU(s):                  0-3

指定的佇列操作

修改 queue.c ，使其滿足 $ make test 自動評分系統的所有項目

q_new

commit 55648cf

建立一個空的佇列，並將其下一個和上一個的指標都指向自己。

避免非必要的項目縮排 (即 * )，用清晰、明確，且流暢的漢語書寫。

宣告一個 list_head 型別的指標並使用 malloc 分配 配置記憶體空間再2. 用 list.h 中的 INIT_LIST_HEAD 將其指向下一個和上一個的指標都指向自己。

allocate 的翻譯是「配置」，以區隔 dispatch (分配/分發) 的翻譯。

q_free

commit 08319cb

將佇列所使用的全部記憶體釋放，若是佇列是空的則不動作。

留意資訊科技詞彙翻譯

使用 list.h 中的 list_for_each_safe 去遍歷 走訪整個佇列
將走過的節點用 list_del 從佇列中移去
使用 list_entry 去取得該節點 container (也就是 element_t)位置，把 value 和該節點之記憶體釋放。

避免非必要的項目縮排 (即 * 和 - )，以清晰、明確，且流暢的漢語書寫。

q_insert_head, q_insert_tail

commit 303414a

插入一個節點到佇列的頭(尾)。

分配 記憶體空間給新結點
將要插入的字串存到 value
使用 list.h 中的 list_add / list_add_tail 將節點插入佇列中。

避免非必要的項目縮排 (即 * 和 - )，以清晰、明確，且流暢的漢語書寫。

一開始在寫完後執行 make check 產生以下錯誤訊息。

# Fill it with some values. First at the head
ERROR: Need to allocate and copy string for new queue element
l = [dolphin]

根據錯誤訊息可得知，需要先使用 malloc 配置空間給新的元素，並複製要插入的字串。

bool q_insert_head(struct list_head *head, char *s)
{
    element_t *new = malloc(sizeof(element_t *));
+   new->value = malloc(sizeof(s)+1);
+   strcpy(new->value, s);
-   new->value = s;
    list_add(&new->list, head);
    return true;
}

修改程式後可以順利執行，但是當 commit 的時候被偵測到有危險的函式。

Dangerous function detected in /home/ollieni/linux2024/lab0-c/queue.c
31:    strcpy(new->value, s);
41:    strcpy(new->value, s);

Read 'Common vulnerabilities guide for C programmers' carefully.
    https://security.web.cern.ch/security/recommendations/en/codetools/c.shtml

在查看錯誤訊息提供的 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. In fact, the whole family of functions is similarly vulnerable: strcpy, strcat and strcmp."

這些文字的大意是 :
strcpy 內建函式並未檢查緩衝區的長度，可能會覆寫意圖目的地相鄰的記憶體區域。事實上，整個函式家族都存在相似的風險：strcpy、strcat 和 strcmp。

我根據網頁中的推薦使用 strncpy 。

bool q_insert_head(struct list_head *head, char *s)
{

+   int len = strlen(s);
+   strncpy(new->value, s, len + 1);
-   strcpy(new->value, s);

}

q_remove_head, q_remove_tail

commit 4b5aafe

將佇列中第一個(最後一個)節點移去。

使用 list_entry 將第一個(最後一個)節點之 container 找出。
將節點之 value 複製存於 sp ，使用 list_del將節點移去。

避免非必要的項目縮排 (即 * 和 - )，以清晰、明確，且流暢的漢語書寫。

q_size

commit 51235c1

計算佇列的長度。

用教材中之程式。

q_delete_mid

commit e636266

刪除佇列中間的節點。

使用 q_size 得到佇列之長度後。
用 while 迴圈找到中間的節點，再將其刪除。

避免非必要的項目縮排 (即 * 和 - )，以清晰、明確，且流暢的漢語書寫。

q_delete_dup

commit 1f9b9be

將佇列中重複的元素全部刪除。

將節點和下一個節點之 value 進行比較，若是相同就刪除當下節點，並用 count++ 記錄此 value 有重複 (在 C 語言中除了 0 都是 True)。
在不相等時，去查看 count 來判斷是否刪除當下節點。
在最後一個節點時，也需查看 count 來判斷是否刪除當下節點。

避免非必要的項目縮排 (即 * 和 - )，以清晰、明確，且流暢的漢語書寫。

一開始的實作會如同這題 leetcode，無法將重複的全部刪除。
ERROR: Duplicate strings are in queue or distinct strings are not in queue

後來使用 count 記錄當下節點之前是否重複，在我自己的測試中能得到正確的結果。
但是在 make test 中出現問題，在自己排查後，發現是最後一個節點永遠不會被刪除。
再多加上一個判斷就解決了。

q_swap

commit cd02814

將佇列中每兩個相鄰元素的值進行交換。

1. 初始化兩個指標 cur 和 prev 分別指向連結串列中的第二個和第三個元素。
2. 使用 q_size 函數計算連結串列的大小，存儲在 size 中。
3. 進入一個迴圈，當 i 小於等於 size - 2 時，執行以下步驟：
   透過 list_entry 宏將 cur 和 prev 轉換為 element_t 結構的指標，分別為 cur_element 和 prev_element。
   交換 cur_element 和 prev_element 中的 value 成員。
   更新 cur 和 prev 指標，使其指向下一對元素。
   增加 i 的值，以繼續處理下一對元素。

善用 List API，撰寫出更精簡的程式碼。

q_reverse

commit fa5829a

反轉整個佇列。

1. 宣告三個指標變數 pos、temp 和 new，用於走訪連結串列。
2. 使用 list_for_each_safe 走訪連結串列，對每個元素執行以下操作：
   將 pos->next 指向 pos->prev，將 pos->prev 指向 new。
3. 最後將 head 自身的 next 和 prev 互換。

q_reverseK

commit da08d7c

按照指定的 k 大小，先將整個串列分成 k 組，再對其反轉。

將 current 指標向前移動 k 次，切斷 head 和 current->prev 之間的元素，存在 temp 中。
呼叫先前定義的 q_reverse 函數對 temp 進行反轉。
使用 list_splice_tail_init 將反轉後的 temp 串列添加到 result 串列的尾部。
使用 list_splice_init 將最終結果 result 串列合併到原始 head 串列。

改進你的漢語表達。

q_sort

commit ed69f07

使用 merge sort 實作，將佇列中元素依照輸入的 descend 參數決定要輸出升序或降序的結果。
我分成 4 個函式實作 :

merge 函式：
此函式用於合併兩個已經排序的佇列 l1 和 l2。
創建三個指標 cur1、cur2 和 swap 以遍歷 ??? l1 和 l2，以及存儲合併結果的 result 佇列。
在迴圈中，比較 cur1 和 cur2 指向的元素，將較小的元素添加到 result 佇列中。
最後，處理剩餘的元素，並將 result 佇列接合到原始 l1 或 l2 中。
返回合併後的佇列。

split_two 函式：
此函式用於將佇列分成兩半，返回分割點的位置。

sort 函式：
此函式實現合併排序，接受一個指向佇列 head 和一個布林值 descend（用於指定升序或降序排列）作為參數。
使用 split_two 函式將佇列分為兩半，然後分別對兩半進行遞迴排序。
使用 merge 函式將兩半合併為一個排序好的佇列。
返回排序後的佇列。

q_sort 函式：

call 的翻譯是「呼叫」，這個函式的權限沒大到可以「調用」你。

此函式用於調用呼叫 sort 函式進行合併排序。
先檢查連結串列的大小，如果為空或只有一個元素，則直接返回。
將連結串列的頭節點刪除，將剩餘部分進行排序，最後將排序後的結果重新連結到原始的 head。

q_ascend

commit cf8cdde

刪除具有較小值在右側的節點。

1. 使用 list_entry 取得 head 節點的前一個節點的 value 值，將其初始化為 right_max。
2. 使用迴圈從 head 節點的前一個節點(尾端)往前，走訪整個連結串列，對每個節點進行以下操作：
   透過 list_entry 取得節點的 element_t 結構指標 entry。
   如果 right_max 與 entry->value 相等或更大，更新 right_max。
   否則，刪除當前節點，釋放相應的資源（value 和 entry）。

q_descend

commit cf8cdde

刪除具有較大值在右側的節點。
實作和ascend一樣，只要將判斷式中的 >= 改成 <= 即可。

q_merge

commit 19d7e81

合併多個排好序的佇列，並將結果放到第一個佇列裡。
以下方兩個函式實作:

對應到數學公式，function 應翻譯為「函數」，後者就像是台「機器」，它能夠將集合 A 裡面的每個元素「唯一地」對應到集合 B 裡的一個元素。但在 C 語言一類的通用程式語言中，function 未必具備數學函數的意涵，也就是缺乏「唯一對應」的特性，例如對於 time 來說，給定同樣的輸入，卻會在不同時間點得到不同的結果，在 C 語言一類的通用程式語言中，甚至可省略傳回值，後者就不符合「函數」的行為。因此，當在通用的程式設計中，function 應翻譯為「函式」，表示「衍生自數學函數的常式 (routine)」。另外，對於更一般的描述，function 會指「功能」一類的意涵，應合適挑選譯詞。

$\to$ 資訊科技詞彙翻譯

merge_two_list 函式：
此函式用於合併兩個已經排序的連結串列 l1 和 l2。
創建三個指標 cur1、cur2 和 swap 以遍歷 l1 和 l2，以及儲存合併結果的 result 串列。
在迴圈中，比較 cur1 和 cur2 指向的元素，將較小（或相等）的元素添加到 result 串列中。
將剩餘的元素依次添加到 result 串列中。
最後，將 result 串列接合到原始 l1 中。

q_merge 函式：
此函式的目的是合併多個已排序佇列，形成一個新的排序佇列。
使用 merge_two_list 函數將每個佇列逐一合併到第一個串列 context1->q 中。
如果指定的排序方式為降序，則呼叫 q_reverse 函數對最終合併的佇列進行反轉。
返回最終合併的佇列的大小，即呼叫 q_size 函數。

make test 結果

做完所有項目後，我 make test 有時候會得到100分，有時候不會。


文字訊息避免用圖片來表示，否則不好搜尋和分類

---	trace-14-perf	6/6
+++ TESTING trace trace-15-perf:
# Test performance of sort with random and descending orders
# 10000: all correct sorting algorithms are expected pass
# 50000: sorting algorithms with O(n^2) time complexity are expected failed
# 100000: sorting algorithms with O(nlogn) time complexity are expected pass
---	trace-15-perf	6/6
+++ TESTING trace trace-16-perf:
# Test performance of insert_tail
---	trace-16-perf	6/6
+++ TESTING trace trace-17-complexity:
# Test if time complexity of q_insert_tail, q_insert_head, q_remove_tail, and q_remove_head is constant
Probably constant time
Probably constant time
Probably constant time
Probably constant time
---     trace-17-complexity     5/5
---	TOTAL		100/100
ollieni@ollie-CA:~/linux2024/lab0-c$ 

但 push 上 github ，無法通過 CI/CD的測試。
經過推測，發現有可能是老師在作業文件中提到的問題。
注意：現有實作存在若干致命缺陷，請討論並提出解決方案

確保 qtest 提供的 web 命令得以搭配上述佇列實作使用

嘗試使用 web 去確認我實作的程式是否能搭配，
測試指令 :

$ curl http://localhost:9999/new
$ curl http://localhost:9999/ih/1
$ curl http://localhost:9999/ih/2
$ curl http://localhost:9999/ih/3
$ curl http://localhost:9999/sort
$ curl http://localhost:9999/quit

以下是測試結果 :

$ ./qtest
cmd> web
listen on port 9999, fd is 3
cmd> l = []
cmd> l = [1]
cmd> l = [2 1]
cmd> l = [3 2 1]
cmd> l = [1 2 3]
cmd> Freeing queue

在 qtest 新增 shuffle 命令

指令

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

根據教學文件 qtest 命令直譯器的實作，在 console_init() 中加上 ADD_COMMAND(shuffle, "Shuffle the nodes of the queue", "");，並寫一個 do_shuffle 去呼叫我們實作的q_shuffle。

q_shuffle

雖然教材中有，但我還是嘗試寫了一個版本。

1. 獲取連結串列的大小，存儲在變數 length 中，使用 q_size 函數。

algorithm 是「演算法」，而「算法」是 the way to calculate，一如你以前國小考試作答的計算過程。

2. 使用 Fisher-Yates shuffle 演算法 算法：
   進行一個迴圈，從最後一個元素開始，依次對每個位置進行處理。
   在每次迭代中，生成一個隨機數 j，範圍為 [0, i]，其中 i 為當前迭代的位置。
   透過兩個迴圈分別找到第 i 和 j 位置對應的節點。
   交換這兩個節點的 value 值。

以下為執行測試程式後的結果 :

$ python3 scripts/shuffle.py
Expectation:  41666
Observation:  {'1234': 41656, '1243': 41850, '1324': 41965, '1342': 41372, '1423': 41682, '1432': 41783, '2134': 41375, '2143': 41391, '2314': 41578, '2341': 41945, '2413': 41157, '2431': 41731, '3124': 41651, '3142': 41445, '3214': 41810, '3241': 41649, '3412': 41421, '3421': 41752, '4123': 42126, '4132': 41662, '4213': 41641, '4231': 42100, '4312': 41487, '4321': 41771}
chi square sum:  31.539144626314016

啟發和疑惑

ClangFormat

整個專案的程式風格統一，才能有利於協做並更好的維護程式。

Clang Format 這個工具，可以很有效率的幫助我們輕鬆統一程式風格。
我們只要在專案的根目錄下，寫一個 .clang-format 檔案，裡面可以詳細定義要遵循的程式風格，比如說 : 不能使用 tab 、使用 4 個空白代替，我們在下指令的時候，沒有指定 -style，clang format 預設會去抓我們定義的 .clang-format 檔案。

Git Hooks

你查詢哪些材料？該列出來，並以第一手材料為主。

根據我查詢的資料 根據 Git 官方手冊 Git Hooks ， Git Hook 這個功能的是將一些簡單的 CI 從 server 端，移到開發人員端做，我們在 commit 前就能確保我們程式符合規範。
這些規範的腳本會在 .git/hooks/ 這個目錄下，有些腳本有 .sample 這個副檔名，代表沒啟用，如果要啟用只需將 .sample 刪掉即可。
在 Git 官方手冊中，有提到我們使用的 pre-commit 是 client-side hook，這種 hook 不會隨著 git clone 被複製，我就有疑問我們沒有特別設定，怎麼有這個功能。
在仔細重看了一次 lab0 文件後，找到在 Git Hooks 進行自動程式碼排版檢查，有寫到 "首次執行 make 後，Git pre-commit / pre-push hook 將自動安裝到現行的工作區 (workspace)"，於是我去看 Makefile，注意到有執行一個腳本 $(GIT_HOOKS): @scripts/install-git-hooks ，再去查看 scripts/install-git-hooks 腳本中的內容，以下我覺得是重點

mkdir -p .git/hooks

ln -sf ../../scripts/pre-commit.hook .git/hooks/pre-commit || exit 1
chmod +x .git/hooks/pre-commit

ln -sf ../../scripts/commit-msg.hook .git/hooks/commit-msg || exit 1
chmod +x .git/hooks/commit-msg

ln -sf ../../scripts/pre-push.hook .git/hooks/pre-push || exit 1
chmod +x .git/hooks/pre-push

touch .git/hooks/applied || exit 1

我可以看出，在這個專案中，將我們所需的腳本先放在 scripts 目錄下，這樣我們 clone 時，就能複製到這些腳本。然後在執行 make 的時候，會去執行 install-git-hooks ， 將 pre-commit、commit-msg、pre-push 用 ln 建立連結檔到 .git/hooks/ 目錄下並改變權限讓其可以執行，如此我們就可以使用這些 client-side hook。

參考資料 : 探索藏在Git當中的Git Hook

為何不閱讀 Git 官方的手冊呢？

工程人員說話要精準，避免說「感覺」

教材啟發

Indirect pointer 使用時機

1. 藉由 indirect pointer 來改動傳入的鏈結串列開頭節點，函式就不需回傳值
2. 避免配置暫時節點的空間
3. 實作快慢指標
4. 指向兩條要合併的串列，避免動態記憶體配置

Rust key concept

1. Ownership and Borrowing
2. Every variable in rust is immutable
3. Package manager : Cargo

你閱讀教材都沒遇到問題嗎？

分析及引入 lib/list_sort.c

這是 Linux 核心使用的 sort ，是 merge sort ，主要由三個函式 list_sort() 、 merge() 及 merge_final() 組成，這個實作有幾個特別的地方:
在 sort 的時候會先將鏈結串列轉換成 null-terminated 的。
有兩個 merge 的函式，merge_final ，會在合併完最後兩個鏈結串列後將結果恢復為標準的 circular doubly linked-list。

merge () 函式 :
merge() 的實作方法是用一個無線迴圈，使用 cmp 來決定要將 a 還是 b 放到 tail.
這裡有個重點，註解有提到如果有等於的情況，為了排序的 stability 要取 a。
值得一提的是 cmp 以 function pointer 的型別傳入，定義在 include/linux/list_sort.h 裡面:

typedef int __attribute__((nonnull(2,3))) (*list_cmp_func_t)(void *, const struct list_head *, const struct list_head *);

在 linux/lib /test_list_sort.c 中可以找到cmp 函式，以下是 cmp() 的行為 :
當 cmp 回傳大於 0 時，表示 a > b 。
當 cmp 回傳小於等於 0 時，表示 b < a 。

補充 :
__attribute__ 能讓你向編譯器提供關於函式的額外訊息，比如說 list_sort.c 中的 __attribute__((nonnull(2,3,4))) ，代表告訴編譯器，這個函式的第 2、3、4個參數不能是 null。
likely 被定義在 /include/linux/compiler.h 裡，這個宏定義可以告訴編譯器，你覺得哪個分支更有可能被執行，可以讓編譯器在編譯時，做最佳化，舉例來說，如果在判斷式中使用 unlikely，編譯器會調整其編譯出的組語或機器碼，讓 false 分支接在後面，使其只有在 true 的時候 jump。
參考資料 :
Declaring Attributes of Functions
The Linux Kernel Module Programming Guide

在我測試完功能要 commit 時，遇到以下問題:

Following files need to be cleaned up:
qtest.c
queue.c
list_sort.c:21:20: style: Variable 'head' is not assigned a value. [unassignedVariable]
 struct list_head *head, **tail = &head;
                   ^
list_sort.c:11:7: error: Null pointer dereference: (struct element_t*)0 [nullPointer]
 la = list_entry(a, element_t, list);
      ^
list_sort.c:12:7: error: Null pointer dereference: (struct element_t*)0 [nullPointer]
 lb = list_entry(b, element_t, list);
      ^

Fail to pass static analysis.

第一個 style 的錯誤訊息是因為沒有賦值給 head ，所以我改成 struct list_head *head = NULL，就符合 style 了。
接下來兩個錯誤訊息是 cppcheck 檢查的東西，根據 david965154 的筆記，我了解到可以去 script/pre-commit.hook 中設定，--suppress=nullPointer:list_sort.c" ，我加了這行讓 pre-commit 對我的 list_sort.c 不檢查 nullPointer 的問題，即可 commit 成功。

引入 Tim_sort

使用第一周測驗2的 tim_sort(待辦事項:了解程式碼有沒有問題)，引入過程和 list_sort 引入過程一樣。