2024q1 Homework1 (lab0)

# 2024q1 Homework1 (lab0) contributed by < `fatcatorange` > #### Reviewed by `HenryChaing` >git rebase 看似是成功的，抓取下來的分支經過別的分支 rebase 後 master 位置不變。其餘的 review 在底下有留言 ## 開發環境 ```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: 46 bits physical, 48 bits virtual Byte Order: Little Endian CPU(s): 32 On-line CPU(s) list: 0-31 Vendor ID: GenuineIntel Model name: 13th Gen Intel(R) Core(TM) i9-13900K CPU family: 6 Model: 183 Thread(s) per core: 2 Core(s) per socket: 24 Socket(s): 1 Virtualization: VT-x Caches (sum of all): L1d: 896 KiB (24 instances) L1i: 1.3 MiB (24 instances) L2: 32 MiB (12 instances) L3: 36 MiB (1 instance) NUMA: NUMA node(s): 1 NUMA node0 CPU(s): 0-31 ``` ### 節點結構 queue.h 檔案中紀錄了每一個節點的結構： ```c typedef struct { char *value; struct list_head list; } element_t; ``` 而在 list.h 中，則有紀錄 `list_head` 的結構： ```c struct list_head { struct list_head *prev; struct list_head *next; }; ``` 因此，基本的 list 結構中並不包含資料，只存在各節點的前後連接關係，而透過 element_t ，各節點內可儲存<s>一個字元陣列</s> 字串，並透過 list 的結構連接。 ### `q_new` :::danger allocate 的翻譯是「配置」，以區隔 dispatch (分發/分配) 的翻譯。 ::: 此處應只是要<s>分配</s> 配置一個 head 給 queue ，尚未開始放入資料，因此透過malloc分配一塊空間給新的list_head，並讓lh指標指向該位址，確認成功分配後透過~~巨集~~ 函式`INIT_LIST_HEAD` 來將此位址的 next 和 prev 欄位指向自身，形成一環狀鏈結串列 :::warning `INIT_LIST_HEAD` 不是巨集。 ::: ```c struct list_head *q_new() { struct list_head *lh = (struct list_head *) malloc(sizeof(struct list_head)); /*if lh didn't malloc sucessfully*/ if (!lh) return NULL; /*initialized the new list head*/ INIT_LIST_HEAD(lh); return lh; } ``` :::warning TODO: 1. 將 `if (lh == NULL)` 改寫為 `if (!lh)`，簡潔 2. 不需要將 `malloc` 返回的 `void *` 型態資料予以轉型，查閱 C 語言規格書 (並列出原文) 進行討論。 ::: 規格書中提到 malloc 的用法： > 7.20.3.3 The malloc function > The malloc function allocates space for an object whose size is specified by size and whose value is indeterminate. > Returns: The malloc function returns either a null pointer or a pointer to the allocated space. 也就是說，透過 `malloc` ，函式會回傳一個指向 void 型態的指標，而再參考到 void 在規格書中的解釋： > 6.3.2.3 Pointers > A pointer to void may be converted to or from a pointer to any incomplete or object type. A pointer to any incomplete or object type may be converted to a pointer to void and back again; the result shall compare equal to the original pointer 可以得知，指向 void 的指標可以轉換為任何物件或不完全型別（只宣告而未定義的結構），而 c 語言中物件應是指任何佔有記憶體的東西，因此透過`malloc`回傳的 void 指標，不需要在對其進行額外的轉型動作。透過 `make check` 檢查後，似乎有成功建立空的串列，但可能因為其他功能未完成，使用 `make test` 後分數反而降低，目前先暫時不修改。 ### `q_free` :::danger 避免過多的中英文混用，已有明確翻譯詞彙者，例如「鏈結串列」(linked list) 和「佇列」(queue)，就使用該中文詞彙，英文則留給變數名稱、人名，或者缺乏通用翻譯詞彙的場景。 ::: 透過 `list_for_each_entry_safe` 巨集可以安全的對每個節點進行刪除操作，而中止條件是 `&entry->member != (head)` ，但若只有一個 head 節點，也就是鏈結串列是空的，似乎無法有 `entry->member?` 因此這裡設定了一個特殊情況，如果 l 是空的（只有一個 head ），那直接 free(l) 後離開，否則透過 `list_for_each_entry_safe` 來個別刪除節點。 :::danger 改進你的漢語表達。 ::: ```c void q_free(struct list_head *l) { if (list_empty(l)) free(l); return; element_t *now, *safe; list_for_each_entry_safe (now, safe, l, list) { free(now); } free(l); } ``` 但後來將特殊情況刪除後，似乎也沒有出現其他錯誤，不確定是否誤會 `list_for_each_entry_safe` 的執行方式。後來想到 `list_entry` 可以回傳某 entry 的位址，因此嘗試只透過 `list_for_each_safe` 並搭配 `list_entry` 來達成相同目的，而因為 `list_for_each_safe` 的結束條件是 `node != (head)`，因此可以確定如果只傳入一個 head ，就不會進入迴圈。 ```c void q_free(struct list_head *l) { struct list_head *now, *safe; list_for_each_safe(now, safe, l) { free(list_entry(now,element_t,list)); } free(l); } ``` :::danger 使用 `git diff` 或 `diff -u` 命令來產生程式碼之間的變異列表。 ::: 後來又發現，這樣的方式只會釋放該鏈結和指向該字元陣列的指標，而不會釋放該陣列本身，因此透過 queue.h 中的 q_release_element 函式來將兩種指標都釋放，但仍存在 memory leak 問題而無法 commit 。 ```c void q_free(struct list_head *l) { if (list_empty(l)) free(l); return; element_t *now, *safe; list_for_each_entry_safe (now, safe, l, list) { q_release_element(now); } free(l); } ``` 在後面開始進行插入後，不知為何無論如何修改都沒辦法 commit 成功，check 時也都會卡在 freeing queue ，不確定該如何修改，因此等完成其他插入和移除後再嘗試修改。當完成 insert_tail 操作後，freeing queue 就神奇的成功了，推測是在測試時佇列內數量符合規範才會成功？但仍 commit 不過 > 注意看 Cppcheck 和相關的檢查訊息。 ### `q_insert_head` :::danger allocate 的翻譯是「配置」，以區隔 dispatch (分發/分配) 的翻譯。 ::: 首先，我嘗試先<s>分配</s> 配置出需要的 list 結構空間並用 li 指標指向其，接下來再分配 element_t 的空間並讓該空間的 list 欄位為 li後，使用 list_add 函式將其插入頂端。 ```c bool q_insert_head(struct list_head *head, char *s) { /*malloc space for new linked item*/ struct list_head *li = (struct list_head *) malloc(sizeof(struct list_head)); /*malloc space for new entry item*/ element_t *le = (element_t *) malloc(sizeof(element_t)); le->list = *li; le->value = s; list_add(li,head); return true; } ``` 然而，編譯後出現了以下問題： ``` Segmentation fault occurred. You dereferenced a NULL or invalid pointermake: ``` 似乎是因為存取 NULL 或不正常的位址？後來發現，當透過 malloc 分配 element_t 的空間時，其就應該已經分配了欄位 list 需要的空間，而如果透過硬是分配一塊區域並將其值複製給 le，則 list_add 加入 list 的仍是原本的 li ，而不是複製進去的，另外，也發覺沒有針對未成功非配進行處理。 ```c list_add(&(le->list),head); ``` :::danger HackMD 不是讓你張貼完整程式碼的地方，GitHub 才是！因此你在開發紀錄只該列出關鍵程式碼 (善用 diff 標示)，可附上對應 GitHub commit 的超連結，列出程式碼是為了「檢討」和「便於他人參與討論」，不是用來「假裝自身有付出」 > 收到 <s>已針對張貼的程式碼修改</s> > 沒做到的事，不要輕易宣告。 ::: 修改後，雖然成功插入元素，但插入的元素非常詭異，系統也提示必須分配空間給字串使用，才想起忘記幫 s 分配空間了，這裡直接透過strdup分配空間並放入，果然就成功插入元素。 ```c le->value = strdup(s); ``` ```c if (!le) return false; ``` 但完成後想 commit 時發現系統告知存在 memory leak 問題，搜尋相關錯誤後發現似乎是沒有成功釋放記憶體，這時發現，實際上 q_free 似乎並未成功釋放記憶體，在作業解說有提到用 valgrind 測試，目前還在嘗試。嘗試了非常久，查到`strdup`並非標準函式，因此我嘗試將 `strdup`的部份改為`malloc`搭配`strncpy`的方式實作，但仍出現相同問題。 ``` queue.c:66:5: error: Memory leak: le [memleak] return true; ^ queue.c:89:5: error: Memory leak: le [memleak] return true; ``` 終於成功修改問題，但引起了更大的疑問，當時使用 list_add 時，必須傳入要插入的節點的 list 部份的指標，而因為透過 `le->list` 取出的 list 並非指標，而是一個物件，因此我透過＆符號取得了該位址傳入，而在做這件事時，因為我想獲得的是 `le->list` 的位址，因此我寫成 `&(le->list)`，之後便不斷出現錯誤，但在我胡亂嘗試和參考其他程式碼後，我改為 `&le->list` 後就成功通過，但這讓我非常疑惑，因此調查了 address of 的規格書，但似乎未看到相關討論，而我測試後發現，如果我將括號放成：`(&le)->list` 的話，會連編譯都過不了，這也比較符合我的預期，因此我認為`&le->list` 和 `&(le->list)` 效果應該相同?但後者會導致 cppCheck 出現 memory leak 問題，可能要麻煩老師或其他同學解答。 :::warning 使用 GDB 一類的工具分析，有更多的資訊才可推測和討論。 ::: :::info 我首先檢查原本寫的 `&(le->list)` ```shell 70 list_add(&le->list, head); (gdb) print le $1 = (element_t *) 0x55555556b160 (gdb) print le->list $2 = {prev = 0x5555555555555555, next = 0x5555555555555555} (gdb) n //執行list_add(&(le->list), head); 73 return true; (gdb) print le->list $3 = {prev = 0x55555556b0e0, next = 0x55555556b0e0} ``` 因為這是插入的第一個元素，因此在`list_add(&(le->list), head);` 後，next 和 prev 都會指向 head。再插入一個元素： ```shell 70 list_add(&le->list, head); (gdb) print le->list $4 = {prev = 0x5555555555555555, next = 0x5555555555555555} (gdb) n //執行list_add(&(le->list), head); 73 return true; (gdb) print le->list $5 = {prev = 0x55555556b0e0, next = 0x55555556b168} (gdb) print le->list->next $6 = (struct list_head *) 0x55555556b168 (gdb) print le->list->next->next $7 = (struct list_head *) 0x55555556b0e0 ``` 可發現程式基本上就是照著預想的進行，因此我嘗試與 list_add(&le->list, head) 比對。 ```shell 70 list_add(&le->list, head); (gdb) print le->list $4 = {prev = 0x5555555555555555, next = 0x5555555555555555} (gdb) n 73 return true; (gdb) print le->list $5 = {prev = 0x55555556b0e0, next = 0x55555556b168} ``` 跟 list_add(&(le->list),head) 的結果一模一樣，因此我還是不知道為什麼會被擋下。 ::: ### `q_insert_tail` 因為這個鏈結串列的結構是環狀且雙向的，因此只需要透過 head 指標的前一項即可得到佇列尾端指標，將新的部份連接到該指標的 next ，並將新元素的 next 指向 head 即可(prev 操作相同) 在 list.h 中發現，直接透過 `list_add_tail` 操作即可，其他部份則與插入佇列頂端相同。 ```c bool q_insert_tail(struct list_head *head, char *s) { /*malloc space for new entry item*/ element_t *le = (element_t *) malloc(sizeof(element_t)); if (le == NULL) return false; le->value = strdup(s); list_add_tail(&(le->list), head); return true; } ``` ### `q_remove_head` 和 `q_remove_tail` 根據 queue.h 中的說明，被 remove 的資料並不會被釋放，並且如果原本的 sp 不為 NULL ，要把原本在該 entry 內的資料複製給 ap 指標。因為鏈結串列是雙向且環形，因此第一個元素就是 `head->next`，最後一個就是 `head->prev` ```c element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize) { if(!head || list_empty(head)) return NULL; element_t *temp = list_entry(head->next,element_t,list); if(sp && temp != NULL){ sp = malloc(bufsize); strncpy(sp,list_entry(head->next,element_t,list)->value,bufsize); } list_del(head->next); return temp; } ``` ```c element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize) { if(!head || list_empty(head)) return NULL; element_t *temp = list_entry(head->prev,element_t,list); if(sp && temp != NULL){ sp = malloc(bufsize); strncpy(sp,list_entry(head->prev,element_t,list)->value,bufsize); } list_del(head->prev); return temp; } ``` 但透過 make test 檢查，會發現並沒有成功取得釋出的值，另外記憶體也沒有釋放成功 ``` ERROR: Failed to store removed value ERROR: Failed to store removed value ERROR: Failed to store removed value ERROR: Freed queue, but 3 blocks are still allocated ``` 此處我發現，當我針對 sp 進行 malloc 操作，會導致 sp 指向一個新的位址，並在這個位址進行複製，然而原本傳入的 sp 位址並未進行任何操作。這裡我嘗試性的透過 `strncpy` 來直接寫入 sp 指標，就我的認知，如果將字串複製給空指標應該不能成功寫入。 ```c strncpy(sp,list_entry(head->prev,element_t,list)->value,bufsize); ``` 然而透過測試會發現，測資 1 反而成功的通過了，因此我搜尋了 strncpy 相關的規格書： > The strncpy function copies not more than n characters (characters that follow a null character are not copied) from the array pointed to by s2 to the array pointed to by s1. > > If copying takes place between objects that overlap, the behavior is undefined. > If the array pointed to by s2 is a string that is shorter than n characters, null characters are appended to the copy in the array pointed to by s1, until n characters in all have been written. 其似乎並未提及當輸入 s1 長度小於 n 時會發生的情況，因此我暫時只能推測當長度小於 n 時，`strncpy` 會幫其自動擴充。 :::danger 「較疑惑」是跟誰「比較」？ ::: 此外，此處我有一個<s>較疑惑</s> 疑惑的部份，就是 `list_del` 和 `list_del_init` 的區別，我最後選擇使用 `list_del_init` 來完成，因為我認為這樣處理被移出的節點應該較適合（ `list_del` 僅會移除，而 `list_del_init` 則會在移除後額外將其轉為環狀結構）理論上這樣應該較安全，因為如果訪問其 next 或 prev 才不會<s>訪問</s> 存取到已經釋放或其他狀況的節點，但在跑 test 時，有時加入 init 會導致更低的分數，可能必須等其他函式完成再確認。 :::danger access 的翻譯是「存取」，而非「訪問」(visit) ::: 執行到這裡，我的 memory leak 問題還在導致無法 commit ...明天可能再繼續想辦法解決。發現這兩個函式有個問題，如果節點內的值長度太長，這兩個函式回傳的字串不會以 '\0' 為結尾，因此必須手動加入這個條件 ```c sp[bufsize - 1] = '\0'; ``` ### `q_delete_mid` 此處因為已經有 `q_size()` 函式，因此我們可以直接刪除中間的節點就好，因為這次是說 delete ，應該是要連記憶體都釋放。 ```c bool q_delete_mid(struct list_head *head) { if(!head || !list_empty(head)) return false; int size = q_size(head); size/=2; struct list_head *now = head->next; for(int i=0;i<size;i++) now = now->next; list_del_init(now); q_release_element(list_entry(now,element_t,list)); return true; } ``` 結果不知道為什麼刪除結果一直不如預期？結果才發現 `list_empty(head) == true` 寫成 !list_empty(head)... 此處透過快慢指標技巧，將原本透過迴圈跑到中間的步驟改用快慢指標，其中 fast 每次跑兩格，slow 只跑一格，因此當 fast 跑完全程時 slow 剛好到一半。 ```c while(fast->next!= head && fast->next->next != head){ fast = fast->next->next; slow = slow->next; } ``` ### q_sort 實作此處參考 [Linked List Sort](https://npes87184.github.io/2015-09-12-linkedListSort/) 的方法，並嘗試將其改為雙向鏈結串列的作法，然而目前對我來說要在每個操作同時管理 prev 和 next 指標有點過於複雜，嘗試多次仍然有大量的 bug ，因此決定改用較為簡單的作法，我將鏈結串列的尾端透過`head->prev->next = NULL;` 斷開，並將其視為單向鏈結串列進行 merge sort ，並在排序完畢後將 prev 指標重新進行調整。 :::danger 本來 HackMD 就不是張貼程式碼的合適地方，張貼程式碼是為了討論。 ::: <s>因程式碼過長，此處緊列出斷開鏈結和重新調整 prev 指標的部份，詳細程式碼請看</s> ： https://github.com/sysprog21/lab0-c/commit/d579ab03bc0a9b1d350683e35d83cf50df0bdda0 ```c void q_sort(struct list_head *head, bool descend) { if (!head || list_empty(head) || list_is_singular(head)) return; head->prev->next = NULL; struct list_head *temp, *last; temp = mergeSort(head->next, descend); last = head; while (temp != NULL) { last->next = temp; temp->prev = last; last = last->next; temp = temp->next; } head->prev = last; last->next = head; } ``` ~~這樣做<s>感覺</s> 不太<s>正規</s> ，如果完成後面的程式會嘗試修改此處。~~ 這樣做儘管大幅簡化了程式，但浪費了原本雙向鏈結串列的優勢，因此日後完成作業會再嘗試修改。 :::danger 1. 工程人員說話要精準，避免說「感覺」。 2. 查詢辭典關於「正規」的描述，然後看你的用法是否合理。 >正規是代表正式規範，但此處並未有正式規範，因此應以「適當」或「合理」等詞彙代替 ::: ### q_swap 實作此題在 leetcode 上操作的是單向鏈結串列，而此處要改為雙向鏈結串列的操作，因此我首先想到兩種方法，第一種是像 sort 的方法一樣，將其當作單向鏈結串列操作後再修正 prev 指標，不同的是此時並沒有分割動作，因此只要檢查目前的節點是否為 head 即可，不需要額外斷開環狀結構。但此處我嘗試用第二種方法，直接同時修改 prev 和 next 指標，此處檢查後要發現每個動作必須作6個處理，其中 l1 代表要交換的第一個元素， l2 代表第二個。 1. 改變 l1 的前一項的 next 指標為 l2 2. 改變 l2 的後一項的 prev 指標為 l1 3. 改變 l2 的 prev 指標為 l1 的 prev 4. 改標 l1 的 prev 指標為 l2 5. 改變 l1 的 next 指標為 l2 的 next 6. 改變 l2 的 next 指標為 l1 注意以上動作的順序，例如不能先改了 l1 的 prev 為 l2 再改 l2 的 prev 為 l1 的 prev。完成上述調換後，將 l2 變為 `l1->next->next`，l1 變為 `l1->next` 即可（因為 l1 固定是前面的節點， l2 固定是後面的節點。） ```c void q_swap(struct list_head *head) { /*the list_head l1 is the first item need to be swap,l2 is the second*/ struct list_head *l1 = head->next; struct list_head *l2 = head->next->next; while(l1 != head && l2 != head){ l1->prev->next = l2; l2->next->prev = l1; l2->prev = l1->prev; l1->prev = l2; l1->next = l2->next; l2->next = l1; l2 = l1->next->next; l1 = l1->next; } } ``` 善用 List API 撰寫出更精簡的程式碼。 >參考 [SuNsHiNe-75](https://hackmd.io/@8gdFdQxMR8O0u3u7xLQmxA/r1V9YJI26)，才發現我一直把這些功能給限制的太死，當把一個節點搬到 head 的下一個時，實際上這個 head 不一定要是真正的頭節點，而可以只是將其搬到某個特定節點後面，這大幅精簡了我的程式碼。 ```diff -l1->prev->next = l2; -l2->next->prev = l1; -l2->prev = l1->prev; -l1->prev = l2; -l1->next = l2->next; -l2->next = l1; +list_move(l1, l2); ``` ### q_reverse 這題在 leetcode 上寫時是單向的鏈節串列，我透過遞迴操作逐一往回修改，詳細可看： https://leetcode.com/problems/reverse-linked-list/submissions/1052667547/ 此處是雙向的鏈節串列，因此我嘗試將其 prev 和 next 對調，並在最後將 head 指標進行調整即可，須注意此處應使用自身寫的 for 條件或 list_for_each_safe 巨集，否則修改了 next 指標可能導致錯誤。 :::info 或許先改 head 再使用 `list_for_each` 也可以？因為這樣 `list->next` 就是原本的 `list->prev`，只是改為反向的操作。 ::: 最後實測可以透過反向操作完成，因此決定透過反向操作完成，因為這樣可以省下一個 safe 指標的空間。 ```c void q_reverse(struct list_head *head) { struct list_head *now; struct list_head *temp = head->prev; head->prev = head->next; head->next = temp; list_for_each(now,head){ /*swap*/ struct list_head *tmp = now->prev; now->prev = now->next; now->next = tmp; } } ``` 如果我建立一個 list_for_each 裡面的指標 tmp ，則可以通過 constant time 的測試，但如果我沿用 temp 則不行（改為 `temp = now->prev;`），但我單獨測試應該是可以成功運作，而複雜度測試應該也沒有用到這個函式，我目前不確定原因。更新：好像只是有時候可以有時候不行，可能要再測試。 ### q_reverseK 這裡的想法應該跟 reverse 類似，只是改成每 k 個作一要，注意調整後頭節點的前一個和尾節點的後一個也要修改。 ```c void q_reverseK(struct list_head *head, int k) { struct list_head *now; struct list_head *start = head->next; struct list_head *safe; int count = 1; list_for_each_safe(now,safe,head){ if( count == k){ struct list_head *hd = start; struct list_head *tail = now; for(int i=0;i<k;i++){ struct list_head *tmp = start->next; start->next = start->prev; start->prev = tmp; start = start->prev; } tail->prev = hd->next; hd->next = start; tail->prev->next = tail; hd->next->prev = hd; count = 0; } count++; } } ``` ### q_ascend and q_descend 這兩個函式的作法基本一樣，首先要讓 list 是升序必須刪除所有**後面有比他還小的節點**的節點，因此我使用一個變數 min 來紀錄最小值，並且反著檢索所有節點，當該節點的值比 min 還大時，代表該節點後面存在比他還小的節點，這不符合升序，因此將其刪除，否則的話，代表該節點小於或等於目前的最小值，將最小值更新為其即可。 ```c int q_ascend(struct list_head *head) { if (!head || list_empty(head) || list_is_singular(head)) return q_size(head); struct list_head *tail = head->prev; struct list_head *now = tail; element_t *min = list_entry(tail, element_t, list); while (now != head) { if (strcmp(list_entry(now, element_t, list)->value, min->value) > 0) { struct list_head *tmp; tmp = now->prev; list_del(now); q_release_element(list_entry(now, element_t, list)); now = tmp; } else { min = list_entry(now, element_t, list); now = now->prev; } } return q_size(head); } ``` 降序部份，實際上就是相同邏輯，但改成維持 max 變數，刪除比 max 小的元素即可。 ```c strcmp(list_entry(now, element_t, list)->value, max->value) < 0 ``` ### q_delete_dup 此函式的想法較簡單，由於已經排序過，因此如果有相同元素，其相鄰的節點其元素必定相同，因此我們只要跑一個 for 迴圈並刪除和其前項有相同值的即可，這裡我是先刪除所有前面的節點，最後刪掉剩下的一個重複點（如果目前的點必須刪除會透過一個 checkDel 紀錄） ```c bool q_delete_dup(struct list_head *head) { if (!head) return false; element_t *now, *safe, *last; last = NULL; bool checkDel = false; list_for_each_entry_safe (now, safe, head, list) { if (!last) { last = now; continue; } if (strcmp(now->value, last->value) == 0) { list_del(&last->list); q_release_element(last); checkDel = true; } else { if (checkDel == true) { list_del(&last->list); q_release_element(last); } checkDel = false; } last = now; } if (checkDel == true) { list_del(&last->list); q_release_element(last); } return true; } ``` ### q_merge 這題在 leetcode 中我會先想到透過優先佇列來實作，每次接~~全部元素中最小的即可~~篩選出所有佇列中的頭節點最小者，將其頭節點加入新佇列的尾端即可，詳情可見：https://leetcode.com/problems/merge-k-sorted-lists/submissions/1188468957/ 然而，在 c 中並沒有優先權佇列標準函式庫，因此我只能嘗試開始自身手刻，或者使用比較差的方法（真的每一輪找最小的加入）。 :::danger 避免過多的中英文混用，已有明確翻譯詞彙者，例如「鏈結串列」(linked list) 和「佇列」(queue)，就使用該中文詞彙，英文則留給變數名稱、人名，或者缺乏通用翻譯詞彙的場景。 ::: 此題有一個較麻煩的問題，其不允許新配置空間，因此從頭到尾都必須使用第一個佇列的 head 做為其頭部節點，但這樣會導致在加入佇列的節點時出現困難（例如無法使用list_move_tail 函式，因為這樣會直接把元素拉到第一個佇列），因此這裡我嘗試用一個低效方法，我把所有第一個佇列的元素除了 head 節點外全部搬到第二個佇列，並重新排序第二個佇列，這樣就把第一個佇列清出來了。 >這裡我有點不確定他確保佇列已經排序是跟輸出要的排序一樣嗎（如結果要求降序，輸入進來的必定是降序？還是可能是升序？），因為 trace 中的 sort 並沒有變數，好像只會升序？但最後我先用了一個有點偷懶的方法，我把所有的 list 全部搬到第一個 queue ，然後排序一次即可，雖然這樣做很簡單，但這樣似乎浪費了原本進來的 list 都已經排序過的規則。 ```c nt q_merge(struct list_head *head, bool descend) { if (!head || list_empty(head)) return 0; if (list_is_singular(head)) return 1; struct list_head *h1 = list_entry(head->next, queue_contex_t, chain)->q; struct list_head *now, *safe; list_for_each_safe (now, safe, head) { if (list_entry(now, queue_contex_t, chain)->q != h1) { list_splice_init(list_entry(now, queue_contex_t, chain)->q, h1); } } q_sort(h1, descend); return 1; } ``` :::danger 改進你的漢語表達。 ::: 目前為 95 分，還需要看完論文改善 dudect 內的程式 ## 自動測試程式分析這一段是看完 lab0 關於 signal 說明後的一些理解，因為<s>不太確定</s>在 sigsetjmp 的行為有沒有問題（是否真的是跳回之前執行的地方），<s>如果有錯誤的觀念再麻煩老師指正</s>。 :::danger 說話要明確，到底是哪裡不確定，你該標出來，附上你的佐證。 ::: 首先當 process 執行時，如果有 signal 必定會先對其進行處理：首先，會先透過 q_init() 函式內的兩行註冊當 signal 發生時應該做的事： ```c signal(SIGSEGV, sigsegv_handler); signal(SIGALRM, sigalrm_handler); ``` signal 的兩個參數分別代表某種 signal 和其接收到時要執行的行為，已此處為例： * SIGSEGV:無效的記憶體參照，執行 sigsegv_handler 函式 * SIGALRM:由 alarm 傳來的 timer signal ，並執行 sigalrm_handler 函式在 do_something 系列函式中，首先都會有一行： ```c if (exception_setup(true)) ``` 在 exception_setup 函式中: ```c bool exception_setup(bool limit_time) { if (sigsetjmp(env, 1)) { /* Got here from longjmp */ ... return false; } else { /* Got here from initial call */ jmp_ready = true; if (limit_time) { alarm(time_limit); time_limited = true; } return true; } } ``` 首先， sigsetjmp(env, 1) 代表函式執行到此處時，會先將其堆疊（此處應為函式執行時一行行指令的堆疊）狀態保存，而如果該函式是直接執行到這裡的（不是用其他函式跳過來的），則回傳 0，因此進入 else 部份，接下來設定了 alarm(time_limit)，代表在 time_limit 後會收到一個 SIGALRM 類型的 signal，此時再來看當 sigalrm_handler　函式（觸發 SIGALRM 時會執行的函式）： ```c trigger_exception( "Time limit exceeded. Either you are in an infinite loop, or your " "code is too inefficient"); ``` 而 trigger_exception 內： ```c void trigger_exception(char *msg) { error_occurred = true; error_message = msg; if (jmp_ready) siglongjmp(env, 1); else exit(1); } ``` 此處的 siglongjmp 代表跳轉至 env 的狀態，而 env 正是剛才透過（sigsetjmp(env, 1）設定的狀態，也就是函式回到： ```c if (sigsetjmp(env, 1)){ ... } ``` 然而，這次是透過 siglongjmp 回來，而不是直接執行到這裡，因此回傳的值非 0，因此會進入 if 的部份，並回報錯誤的訊息。 ## 亂數+論文閱讀 ### q_shuffle 實作這裡直接透過作業要求中提供的方法<s>方法</s>，因為題目要求是交換裡面的值，因此只要運用類似 swap 的方法直接交換兩節點內容即可。 ```c void q_shuffle(struct list_head *head){ srand(time(NULL)); int len = q_size(head); while(len > 1){ int r = rand() % len; struct list_head* old = head->next; struct list_head* new = head->prev; for(int i=0;i<r;i++){ old = old->next; } while(new == old){ new = new->prev; } char *tmp = list_entry(old,element_t,list)->value; list_entry(old,element_t,list)->value = list_entry(new,element_t,list)->value; list_entry(new,element_t,list)->value = tmp; len--; } } ``` ### 加入 shuffle 的命令 <s>指令</s> :::danger command 是「命令」，而非「指令」(instruction) ::: 接下來，因為 shuffle 指令還未加入到 qtest 的命令中，此處參考 [kart81604](https://hackmd.io/@kart81604/HkGHY1cTs#2023q1-Homework1-lab0) 的作法，在 qtest.c 檔案中的 console_init() 中加入該<s>指令</s> 命令： ```c ADD_COMMAND(shuffle, "Shuffle all nodes value",""); ``` 並且要加入以下函式，因為參考 console.h 中的以下巨集： ```c #define ADD_COMMAND(cmd, msg, param) add_cmd(#cmd, do_##cmd, msg, param) ``` 實際上，前面那段加入的函式中就是加入了一個較 shuffle 的命令，而這個命令主要功能就是去執行 q_shuffle ，當然還包括一些檢查機制，此處我大多以 do_swap 的函式作修改，並且把函式執行 q_swap 的部份改為執行 q_shuffle。 ```diff! -q_swap(current->q); +q_shuffle(current->q); ``` 透過測試，目前已經可以透過 shuffle 指令來執行該函式，並且簡單的測試過該功能。 ``` ./qtest cmd> new l = [] cmd> ih RAND 10 l = [vjnkq iptfnmp djyqhpbfr gdvivx ekczzxaz pulopr srvfstljj zvxzygs kmlgmxho idsdav] cmd> shuffle l = [ekczzxaz srvfstljj gdvivx iptfnmp idsdav pulopr djyqhpbfr zvxzygs kmlgmxho vjnkq] ``` >此處發現無法 commit，因為不能修改 queue.h，但不將 q_shuffle 加入的話又沒辦法讓 console.c 使用，因此參考 [SuNsHiNe-75](https://hackmd.io/@8gdFdQxMR8O0u3u7xLQmxA/r1V9YJI26) 的方法，新建一個 shuffle.h 和 shuffle.c，並透過 include 讓 console.c 使用。然而要 commit 時再度出現問題，其指出： ```c char *tmp = list_entry(old, element_t, list)->value; list_entry(old, element_t, list)->value = list_entry(new, element_t, list)->value; list_entry(new, element_t, list)->value = tmp; ``` 這部份的操作，當 old 或 new 指標並不是 list_entry 的一部分時（可能僅是一個 list ，但不是一個 element 的一部分），會有 Null pointer dereference 問題： ``` shuffle.c:40:21: error: Null pointer dereference: (struct element_t*)0 [nullPointer] char *tmp = list_entry(old, element_t, list)->value; ^ shuffle.c:41:9: error: Null pointer dereference: (struct element_t*)0 [nullPointer] list_entry(old, element_t, list)->value = ^ shuffle.c:42:13: error: Null pointer dereference: (struct element_t*)0 [nullPointer] list_entry(new, element_t, list)->value; ^ shuffle.c:43:9: error: Null pointer dereference: (struct element_t*)0 [nullPointer] list_entry(new, element_t, list)->value = tmp; ``` 觀察了 list.h, queue.h 後似乎未發現能有效檢查此部份的函式或巨集，因此我可能必須修改為真正交換節點，而不能僅是交換內容。不知道為什麼重開機後突然讀不到 shuffle.h 檔案，因此我只好直接把 shuffle function 放到 qtest.c 完成後可透過[檢測程式](https://hackmd.io/@sysprog/linux2024-lab0/%2F%40sysprog%2Flinux2024-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)來進行亂度檢查。嘗試過後，結果非常詭異，似乎是洗牌方法有問題 ![image](https://hackmd.io/_uploads/By10l6Laa.png) 最後參考了 [slipet](https://hackmd.io/@Slipet/ryrLNN4Ah)，透過 move_to_tail 函式搬移節點，並透過模擬程式檢查： ![image](https://hackmd.io/_uploads/SkGjw08TT.png) 與前次相比，已獲得顯著改善。不慎把評分程式修改為亂數檢測程式後直接 push ，導致線上檢測直接變成 0 分，稍後的提交會再改回來。 ### 修改 commit messages 發現 commit messages 的格式非常不符合課程要求，因此開始重改，我透過 gitk 工具查看了目前版本的整體結構，並透過 `git rebase -i` 來從較早之前的提交開始一一修改，<s>目前已修改完畢</s> 。 :::danger 你確實做到再說，回去看！ ::: --- ## 整合網頁伺服器由於我還不了解 web 命令的功能，我首先查看了 console.c 中的 do_web，首先呼叫了 web_open 函式，這個函式首先使用了 socket 函式，根據 [socket(2)](https://man7.org/linux/man-pages/man2/socket.2.html)說明： > socket() creates an endpoint for communication and returns a file descriptor that refers to that endpoint. The file descriptor returned by a successful call will be the lowest-numbered file descriptor not currently open for the process. ```c if ((listenfd = socket(AF_INET, SOCK_STREAM, 0)) < 0) return -1; ``` :::danger function call 譯作「函式呼叫」，不是「調用」，它的權限沒大到可徵調什麼。 ::: 如果成功<s>調用</s> 呼叫，會回傳編號最低且未被使用的 file descriptor （在 linux 中， socket 被視為一個檔案），AF_INET 代表使用 ipv4， SOCK_STREAM 代表指定的類型， SOCK_STREAM 是雙向且可靠的，通常透過 TCP 完成。假如沒有成功，則回傳 -1。 >file descriptor 是這個 socket 的識別號碼，每個行程會有自己的 file descriptor table。接下來是針對 socket 進行設定，下面是針對這個地址的重用進行設定，若未設定則無法重用地址。 ```c if (setsockopt(listenfd, SOL_SOCKET, SO_REUSEADDR, (const void *) &optval, sizeof(int)) < 0) return -1; ``` >官方文件中似乎並未提及重用的處理方式？是都會接收到資料還是會覆之前使用該地址的行程？ > > 有，注意看 setsockopt 的描述 :notes: jserv > > 我找了一下官方文件，找到下面的資訊： > SO_REUSEADDR Indicates that the rules used in validating addresses supplied in a bind(2) call should allow reuse of local addresses. For AF_INET sockets this means that a socket may bind, except when there is an active listening socket bound to the address. When the listening socket is bound to INADDR_ANY with a specific port then it is not possible to bind to this port for any local address. Argument is an integer boolean flag. >裡面有提及如果沒有正在監聽的 socket 在使用這個地址，那麼就可以重複使用，因此就算有多個 socket 要綁定這個地址，但同時也只會有一個在監聽，所以應該是沒關係？ :::danger protocol 譯作「協定」，而非「協議」。 ::: 接下來是針對<s>協議</s> 的設定， TCP_CORK 是一種常用在伺服器傳輸的方法 ```c if (setsockopt(listenfd, IPPROTO_TCP, TCP_CORK, (const void *) &optval, sizeof(int)) < 0) return -1; ``` 一般來說，網頁伺服器在回應用戶端時，會先發送一個標頭和一個內容，標頭一般透過 write，內容透過 sendfile。為了小型封包的傳輸，有時會希望先收集更多資料，再進行傳輸，或者是讓多個資料收集起來，這樣只要一個標頭。因此有了 TCP_CORK ， CORK 是塞子的意思，當資料要傳輸時，如果有設定 TCP_CORK，只有在滿足條件（包含暫存的量夠大、取消 TCP_CORK 、超過一定延遲等）時才會送出訊息。 >注意：這可能會增加延遲，如果目標是低延遲，可以設定成 NODELAY。接下來要把這個 socket 綁定給地址，並安裝監聽器，表示可以開始接收訊息。在 do_web 中， ```c line_set_eventmux_callback(web_eventmux); ``` 在 linenoise 中有宣告，但看起來只是把 web_eventmux 這個函式傳入並設定為 callback function 而已。 >但這樣為什麼就可以開始接收資料？ >在註解中有說明，設定了此 callback function 之後，可以監聽不同 file descriptor 的輸入，而不只是原本的 stdio 目前的問題是，當使用了 web 命令， linenoise 的一些功能會不能用，例如： ```shell $ ./qtest cmd> web !listen on port 9999, fd is 3 cmd> new l = [] cmd> ih RAND 10 l = [zvgsk kuoyrme uhqxzvyx tswtggnsi vpvfqdzi dxracpjel qjodhekfm jykwgtjo rwrku nqwrhci] cmd> ``` 在這個<s>指令</s> 命令後，如果在輸入按下上鍵，應該出現上一個使用的命令，但卻會直接出現 web 而不是 ih RAND 10。 >use_linenoise = false 去掉就會恢復正常，應該不是這個問題.. 當資料被輸入時，會傳入一個 buffer 給 line_edit，這個 buffer 是用來存放命令的，程式會透過 read 閱讀目前輸入的按鍵，舉例來說： ```c nread = read(l.ifd, &c, 1); if (nread <= 0) return l.len; /* Only autocomplete when the callback is set. It returns < 0 when * there was an error reading from fd. Otherwise it will return the * character that should be handled next. */ if (c == 9 && completion_callback != NULL) { c = complete_line(&l); /* Return on errors */ if (c < 0) return l.len; /* Read next character when 0 */ if (c == 0) continue; } ``` 這段程式碼中， `c == 9` 代表的是輸入了 tab ，因此進行自動補全。在 web.c 中，web_eventmux 的功能是接收訊息，前面提到建立了 socket 並設定為監聽狀態，而在 web_eventmux 中就設定了 accept: ```c int web_connfd = accept(server_fd, (struct sockaddr *) &clientaddr, &clientlen); ``` > 參考 [accept(2)](https://man7.org/linux/man-pages/man2/accept.2.html) > accept 中會傳入目前正在監聽的 socket 和用來保存回傳資料的地址，而輸出會是另一個 file descriptor 編號，是另外一個 socket 的編號，這個 socket 是額外用來與要連接的用戶通訊用的，不影響原本正在 listen 的 socket。接下來，根據拿到的 clientaddr 和 file descriptor，就可以開始設定獲取的資料：在 web_recv 中，首先會透過 `parse_request(fd, &req);` 來獲取資料，此處的 fd 是這個 file descriptor 的 id ，函式會把資料存入 req，下面是接收到的資料。 ``` GET /new HTTP/1.1 Host: 127.0.0.1:9999 User-Agent: curl/7.81.0 Accept: */* ``` :::info 裡面到底怎麼抓出資料的還沒看懂 ::: 抓下的字串（命令）存放在指標 p 中，將其複製給 buf 後即可回傳 ok 訊息並關閉連接。 ```c char *p = web_recv(web_connfd, &clientaddr); char *buffer = "HTTP/1.1 200 OK\r\nContent-Type: text/plain\r\n\r\n"; web_send(web_connfd, buffer); strncpy(buf, p, strlen(p) + 1); free(p); close(web_connfd); return strlen(buf); ``` > 一定要回傳 ok 嗎？ > >不回傳 ok 會收到以下訊息： >```shell >$ curl 127.0.0.1:9999/new >curl: (52) Empty reply from server >``` >但程式還是會正常運作的樣子現在開始要進行作業的部份，首先作業提到當 read 阻塞時 web 的功能無法正常執行，應是指這部份： ```c while (1) { signed char c; int nread; char seq[5]; if (eventmux_callback != NULL) { int result = eventmux_callback(l.buf); if (result != 0) return result; } nread = read(l.ifd, &c, 1); if (nread <= 0) return l.len; ``` 當 read 被阻塞時，會被卡在迴圈的 read 那一行，導致程式無法往下執行，也不會再繼續跑迴圈檢查 eventmux_callback 的部份。這裡我想實驗，什麼情況下 read 會被卡住？我把 read 要讀取的 file descriptor id 設定成一個沒有的 file descriptor，例如： ```c nread = read(10 , &c, 1); ``` 結果跑出的結果跟預想的不同，我原本預想會被卡在這裡不能動，但直接跑出了無窮迴圈 ``` cmd> cmd> cmd> cmd> . . . ``` 檢查後發現問題： ```c nread = read(20, &c, 1); printf("%d", nread); ``` 因為直接出現錯誤了，所以 read 不會被 block ，而是直接回傳 -1 >那應該怎麼測試？ --- ## dudect #### 論文筆記 :::success 為何要有 constant time? 因為攻擊者可能根據輸入的值分析產生結果花費的時間複雜度，並以此來推測使用的演算法或內部結構（稱為 Timing Attacks），而如果是 constant time，無論是什麼樣的輸入其時間複雜度都相同，因此可以增加這種攻擊的難度。 ::: 首先，論文談到了目前的檢測時間複雜度的工具會有一些問題，舉例來說必須針對硬體設備的規格考慮，但各種 CPU 的內部運作是未公開的，且可能會因為一些內部程式碼改變而有誤差，因此本文才提出了透過統計分析避免針對個別硬體設備客製化。論文中提到會對兩種輸入類別進行測量，很常見的就是固定和隨機，第一類輸入資料是固定的，而第二次是隨機選取，第一類的資料可能會作為邊界條件。另外，現代處理器會有 clock counter，可以用來精準測量執行時間，而準備工作（如選擇類別）會在開始測量前完成已保證執行環境不受這些因素干擾。這個檢測工具最重要的就是要檢查這兩種輸入的執行時間分佈狀況是否相同，又分為以下兩種： 1. t-test: 這部份會透過 Welch's-test 來比較樣本，以下是 Welch's-test 的步驟：首先要先計算兩個輸入的變異數，不相等則可以透過: $t' = \frac{|\bar{x}_1 - \bar{x}_2|}{\sqrt{\frac{S_1^2}{n_1} + \frac{S_2^2}{n_2}}}$ 其中 $\bar{x}_1$代表第一筆輸入的平均值， $\bar{x}_2$代表第二筆輸入的平均值分母的 ${S_1^2}$、${S_2^2}$ 則是變異數 $n_1$、$n_2$ 則是樣本數。當計算出的 t' 小於臨界值，可以說這兩筆樣本均值相同。 <s> 以上資訊參考網路，但公式由來我不知道... </s> :::danger 為何不翻閱統計學教科書？ ::: 2. Non-parametric tests: 這個方法可以減少對底層分佈的假設（減少假設？），但其收斂慢且樣本需求大。這個檢測我查到有多種方法，例如 kruskal -Wallis 等，目前我不確定論文中指的是什麼方法。此處要參考原始程式碼修改程式，因為目前作業中沒有 percentile 的部份，因此先將原始碼中該部份引入，並針對引入的參數進行部份修改，主要參考 [kart81604](https://hackmd.io/@kart81604/HkGHY1cTs) 的方法，修改完後如下： ```c static int64_t percentile(int64_t *a, double which, size_t size) { qsort(a, size, sizeof(int64_t), (int (*)(const void *, const void *)) cmp); size_t array_position = (size_t) ((double) size * (double) which); assert(array_position < size); return a[array_position]; } static void prepare_percentiles(int64_t *percentiles, int64_t *exec_times) { for (size_t i = 0; i < DUDECT_NUMBER_PERCENTILES; i++) { percentiles[i] = percentile( exec_times, 1 - (pow(0.5, 10 * (double) (i + 1) / DUDECT_NUMBER_PERCENTILES)), N_MEASURES); } } ``` 完成後進行測試，目前分數已經可以達到 100/100。 :::danger 闡述論文和程式碼出入之處。 ::: --- ## 將 lib/list_sort 引入至 lab0-c 專案首先我先嘗試引入 list_sort，我暫時未加入 `descend` 變數，因為此處只是先確認是否成功引入，引入步驟主要參考 [kart81604](https://hackmd.io/@kart81604/HkGHY1cTs#2023q1-Homework1-lab0)。首先，將程式碼加入 queue.c 檔案中，並加入需要的巨集和檔案： ```diff +#include <linux/kernel.h> +#include <linux/string.h> +#define likely(x) __builtin_expect(!!(x),1) +#define unlikely(x) __builtin_expect(!!(x),0) ``` 另外，程式也必須進行一定程度的修改之後還必須新增 list_sort 這個命令，就和之前加入 shuffle 方法類似，在 q_test.c 中加入函式 do_list_sort。 :::danger 不用新增命令，善用 `qtest` 命令列的 "option" 來指定排序實作。 ::: 我首先在 sort 的命令中加入一個字串變數: ```c ADD_COMMAND(sort, "Sort queue in ascending/descening order", "str"); ``` >我不太確定這個 "str" 是否只是用來讓開發者識別傳入參數類型，因為沒有這個也能正常運行，找了一下前面的原始碼也沒有看到相關用途。接下來，修改 qtest 中的 do_sort，首先現在會多傳入一個參數用來判斷要用哪種排序，因此 argc 應為 1 或 2。 ```diff! +if (argc < 1 || argc > 2) { + report(1, "%s takes 0 or 1 arguments", argv[0]); -if (argc != 1) { - report(1, "%s takes no arguments", argv[0]); return false; } ``` 接下來，在內部判斷 argv[1] 的值（argv[0] 是指令），並根據這個值來執行對應的排序，如果 argc 為 2 而且 argv[1] 是 "list_sort"，就執行 list_sort，否則執行 q_sort。 ```c //true = list_sort false = q_sort bool sort_type = (argc == 2 && strcmp("list_sort",argv[1]) == 0); if (current && exception_setup(true)){ sort_type ? list_sort(current->q, descend) : q_sort(current->q, descend); } ``` 下方為實測： ``` ./qtest cmd> new l = [] cmd> ih RAND 10 l = [jovgax jurnec slmjqivtm prqcynz lseojm wfmtrqau juepovu ycyjijtin ksotm igbiztadx] cmd> sort list_sort l = [igbiztadx jovgax juepovu jurnec ksotm lseojm prqcynz slmjqivtm wfmtrqau ycyjijtin] cmd> ih RAND 10 l = [hdichazt yvrkfted dvoqs qlfnkl cpxpg kgtxhl oucqojf fheiw rgybteyr qdwuttsx igbiztadx jovgax juepovu jurnec ksotm lseojm prqcynz slmjqivtm wfmtrqau ycyjijtin] cmd> sort l = [cpxpg dvoqs fheiw hdichazt igbiztadx jovgax juepovu jurnec kgtxhl ksotm lseojm oucqojf prqcynz qdwuttsx qlfnkl rgybteyr slmjqivtm wfmtrqau ycyjijtin yvrkfted] cmd> quit Freeing queue ``` 實測後確認已經可以透過參數來執行對應排序，因此也可以把加入的 do_list_sort 命令刪除。再追加 timsort 選項： ```diff -bool sort_type = (argc == 2 && strcmp("list_sort",argv[1]) == 0); if (current && exception_setup(true)){ - sort_type ? list_sort(current->q, descend) : q_sort(current->q, descend); + if(argc == 2 && strcmp("list_sort",argv[1]) == 0){ + list_sort(current->q, descend); + } + else if(argc == 2 && strcmp("timsort", argv[1])){ + timsort(current->q, descend); + } + else{ + q_sort(current->q, descend); + } } ``` ```shell ./qtest cmd> new l = [] cmd> ih RAND 10 l = [abcbfevh nzblufc ycsvcssvb opayilnaw rpnro awauxk sores zzsidjhvh pvsmmg gyvdl] cmd> sort timsort l = [abcbfevh awauxk gyvdl nzblufc opayilnaw pvsmmg rpnro sores ycsvcssvb zzsidjhvh] ``` :::danger command 是「命令」，而非「指令」(instruction) ::: 在檢查網頁伺服器時，才發現我誤會老師的意思，不是在 sort 命令中增加選項，而是要在 option 中設定好要使用的排序函式，因此在輸入 ```shell cmd> option Options: descend 0 | Sort and merge queue in ascending/descending order echo 1 | Do/don't echo commands entropy 0 | Show/Hide Shannon entropy error 5 | Number of errors until exit fail 30 | Number of times allow queue operations to return false length 1024 | Maximum length of displayed string malloc 0 | Malloc failure probability percent simulation 0 | Start/Stop simulation mode verbose 4 ``` 後，應該要有一個 sort_type 之類的選項，我原本預計輸入想要的 sort type 來完成（例如 timsort, list_sort 等），但 add_param 只能輸入整數，因此我改為使用 0,1,2 表示 sorting type。 ```shell $ ./qtest cmd> option Options: descend 0 | Sort and merge queue in ascending/descending order echo 1 | Do/don't echo commands entropy 0 | Show/Hide Shannon entropy error 5 | Number of errors until exit fail 30 | Number of times allow queue operations to return false length 1024 | Maximum length of displayed string malloc 0 | Malloc failure probability percent simulation 0 | Start/Stop simulation mode sort_type 0 | Which sort does user want to use, 0 for q_sort, 1 for list_sort, 2 for tim_sort verbose 4 | Verbosity level cmd> new l = [] cmd> ih RAND 10 l = [zhegkwkx qbqwdq hebnlf qnjfzzmcx quaplti skogofpw chauk dhvfxg omggssxyu kpsnucmy] cmd> option sort_type 1 cmd> sort l = [chauk dhvfxg hebnlf kpsnucmy omggssxyu qbqwdq qnjfzzmcx quaplti skogofpw zhegkwkx] ``` 修改後即可透過 option 選擇 sort_type。 ```diff +bool do_list_sort(int argc, char *argv[]) ``` 在 timsort 的選項中，我嘗試使用函式指標技巧，讓程式碼更簡潔，不需要在 timsort 內再額外檢查排序方法，而直接根據傳入的函式指標操作：函式指標型態，傳入兩個 list_head 的指標： ```c typedef int (*list_cmp_func_t)(struct list_head *, struct list_head *); ``` 升序與降序的函式如下： ```c int ascmp(struct list_head *a, struct list_head *b) { return strcmp(list_entry(a,element_t,list)->value, list_entry(b,element_t,list)->value); } int descmp(struct list_head *a, struct list_head *b) { return strcmp(list_entry(b,element_t,list)->value, list_entry(a,element_t,list)->value); } ``` 在選擇 timsort 時，選擇要使用的比較方法： ```c int* temp = 0; list_cmp_func_t cmp = descend ? descmp : ascmp; timsort((void*)temp, current->q,cmp); ``` tim_sort 內可以直接拿該函式指標來使用 ```c cmp(a, b) <= 0 ``` 內部的程式碼直接拿 do_sort 來修改就可以了，另外還必須加入這個<s>指令</s> 命令 :::danger command 的翻譯是「命令」，而非「指令」(instruction) ::: ```diff ADD_COMMAND(list_sort, "Sort queue in ascending/descening order", ""); ``` 完成後，先透過簡單的檢查看是否能成功使用<s>指令</s> 命令： ``` ./qtest cmd> it 1 Warning: Calling insert tail on null queue l = NULL cmd> new l = [] cmd> it RAND 10 l = [bcxlyeas akfmowqa xmrizkz qjzihe epqyodqt flbvxv gbqqaf kyrjyhc admoncabh uvfnpgq] cmd> sort l = [admoncabh akfmowqa bcxlyeas epqyodqt flbvxv gbqqaf kyrjyhc qjzihe uvfnpgq xmrizkz] cmd> it RAND 10 l = [admoncabh akfmowqa bcxlyeas epqyodqt flbvxv gbqqaf kyrjyhc qjzihe uvfnpgq xmrizkz xdmsu eckrzzyz yvzsmom wifsszu uhrpsk dkvsspi xnrigdn ewdmuj eublhjs bbonzrrd] cmd> list_sort l = [admoncabh akfmowqa bbonzrrd bcxlyeas dkvsspi eckrzzyz epqyodqt eublhjs ewdmuj flbvxv gbqqaf kyrjyhc qjzihe uhrpsk uvfnpgq wifsszu xdmsu xmrizkz xnrigdn yvzsmom] cmd> ``` 根據結果，應以成功引入，接下來就要幫函式加入 `descend` 參數，實際上只要多一層條件式檢查 descend 的值即可，完成後結果如下： ``` // descend = 1 ./qtest cmd> new l = [] cmd> it RAND 10 l = [sbksbaux xfhtc nckimgwte zogmwu bljxebt obbcf isvxtkmv hfainetq ocbeduiy irtbb] cmd> list_sort l = [zogmwu xfhtc sbksbaux ocbeduiy obbcf nckimgwte isvxtkmv irtbb hfainetq bljxebt] cmd> ``` 接下來就要透過 perf 來檢查兩種排序演算法的效能，但此時會發現，如果兩種排序演算法拿到的資料不同，比對的結果也會不公平，為了讓兩種排序演算法公平的比較，這裡參考 [kart81604](https://hackmd.io/@kart81604/HkGHY1cTs#%E5%B0%87-liblist_sort-%E5%BC%95%E5%85%A5%E8%87%B3-lab0-c-%E5%B0%88%E6%A1%88) 的方法，新增兩個 <s>指令</s> 函式`do_write_in` 和 `do_write_out` ，使用 write_in 後，串列資料會被寫入檔案，而 write_out 則將資料取出放入串列，因此先透過 write_in 寫入資料後，再透過 write_out 將資料給 list_sort 和 q_sort 使用，才能公平的比較。 :::danger 翻閱你的統計學教科書，探究多大的量體才足以代表樣本特徵。要有對應的數學分析。 ::: :::danger 不是「指令」，請參照 C 語言規格書，用精準的詞彙。 ::: ```c bool write_out (struct list_head *head) { if (!head) return false; FILE *fptr; fptr = fopen("data.txt","w"); if(fptr == NULL){ return false; } element_t *entry; list_for_each_entry(entry, head, list){ fprintf(fptr,"%s ",entry->value); } fclose(fptr); return true; } static bool do_write_out() { return write_out(current->q); } ``` ~~而在 write_out 部份，因為要把資料從 data.txt 中取出，因此此處先透過 strtok 將資料一一分割，下方式 strtok 在 c 語言規格書中的解釋。~~ > 7.21.5.8 The strtok function Synopsis 1 #include <string.h> char *strtok(char * restrict s1, const char * restrict s2); Description 2 A sequence of calls to the strtok function breaks the string pointed to by s1 into a sequence of tokens, each of which is delimited by a character from the string pointed to by s2. The first call in the sequence has a non-null first argument; subsequent calls in the sequence have a null first argument. The separator string pointed to by s2 may be different from call to call. 3 The first call in the sequence searches the string pointed to by s1 for the first character that is not contained in the current separator string pointed to by s2. If no such character is found, then there are no tokens in the string pointed to by s1 and the strtok functionreturns a null pointer. If such a character is found, it is the start of the first token. 4 The strtok function then searches from there for a character that is contained in the current separator string. If no such character is found, the current token extends to the end of the string pointed to by s1, and subsequent searches for a token will return a null pointer. If such a character is found, it is overwritten by a null character, which terminates the current token. The strtok function savesapointer to the following character, from which the next search for a token will start. 5 Each subsequent call, with a null pointer as the value of the first argument, starts searching from the saved pointer and behaves as described above. 6 The implementation shall behave as if no library function calls the strtok function. Returns 7 The strtok function returns a pointer to the first character of a token, or a null pointer if there is no token. strtok 在第一次使用時，傳入的參數是： 1. 原始字串 2. 要用來分割的字串（在這個例子中就是 ' '）如果第一個參數傳入的是 NULL，則代表接續上次的結果後續繼續切割。後來改成單純使用 fgets 來達成，每次抓取檔案中的字串插入，直到沒有剩餘的字串： ```c bool write_in(struct list_head *head){ if(!head){ return false; } FILE *fptr; fptr = fopen("data.txt","r"); if(!fptr){ return false; } char str[100]; while(fptr){ q_insert_tail(head, fgets(str,sizeof(str),fptr)); } fclose(fptr); return true; } static bool do_write_in(){ return write_in(current->q); } ``` 但完成後執行卻發生 segmentation fault ，此處我透過 <s>valgring</s> valgrind 檢查： > 留意重要工具專有名詞。 > [name=HenryChaing] ``` ==9728== Invalid read of size 1 ==9728== at 0x484ED16: strlen (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so) ==9728== by 0x10FE32: q_insert_tail (queue.c:88) ==9728== by 0x10D171: write_in (qtest.c:1120) ==9728== by 0x10D1AD: do_write_in (qtest.c:1129) ==9728== by 0x10E4E1: interpret_cmda (console.c:181) ==9728== by 0x10EA96: interpret_cmd (console.c:201) ==9728== by 0x10F700: run_console (console.c:691) ==9728== by 0x10D8D3: main (qtest.c:1400) ==9728== Address 0x0 is not stack'd, malloc'd or (recently) free'd ==9728== Segmentation fault occurred. You dereferenced a NULL or invalid pointer==9728== 8 bytes in 1 blocks are still reachable in loss record 1 of 53 ==9728== at 0x484DA83: calloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so) ==9728== by 0x10E0F7: calloc_or_fail (report.c:234) ==9728== by 0x10EA2F: parse_args (console.c:149) ==9728== by 0x10EA2F: interpret_cmd (console.c:200) ==9728== by 0x10F700: run_console (console.c:691) ==9728== by 0x10D8D3: main (qtest.c:1400) ``` 在 insert_tail 時發生問題，後來發現是因為取出的 str 有可能是 NULL，因此要將 while 的條件改成 fgets(str,sizeof(str),fptr)，這樣就不會傳入空的 str，另外，我也在 insert 的函式<s>室</s>內加入判斷式來防止傳入 NULL 。 ```diff //write in -while(fptr){ +while(fgets(str,sizeof(str),fptr)){ q_insert_tail(head, str); current->size+=1; } ``` ```diff! //insert -if (!head) +if (!head || !s) ``` 接下來就可以開始透過 perf 來檢測效能：存入資料： ```shell cmd> new l = [] cmd> ih RAND 10000 l = [ltrev kqyicgeh ilqjv wpediz gtwokhktt anexxiwpw autnjupji xplyxq wougeih kqtzdv wrlhnqv lxwkl rgkihtjn hgvuo viymsrki gqbecwkio epqlmgw lkfcez drdkgqxd mmufecp hwnlnany lowthgh xeiirjo espepcg bkzpavpwk ubupdz ujmcgf ghmvsebqk njbhcfcig mygzyxymg ... ] cmd> write_out cmd> quit Freeing queue ``` 取出資料時，卻發現出現錯誤： ```shell cmd> new l = [] cmd> write_in l = [ixpxufhf vzllxqo synnzg cvwbws fkwkbcay yxfyde awcnzeqb qclalomq gmnvodyyb ljeyytwgk ] cmd> list_sort Warning: Calling sort on single node l = [ixpxufhf vzllxqo synnzg cvwbws fkwkbcay yxfyde awcnzeqb qclalomq gmnvodyyb ljeyytwgk ] cmd> sort Warning: Calling sort on single node l = [ixpxufhf vzllxqo synnzg cvwbws fkwkbcay yxfyde awcnzeqb qclalomq gmnvodyyb ljeyytwgk ] cmd> i Freeing queue ``` 系統表示只讀到了一筆資料，後來發現是因為當初在寫入資料時是透過空格來分隔字串，但實際上在使用 fgets 時只會透過換行符號來抓字串，因此我讀取時實際上是取到一個包含很多空格的大字串。要解決這個問題，只要將寫入時的字串結尾加入換行符號，並在讀取時去除即可： ```diff! \\write_out +fprintf(fptr,"%s\n",entry->value); -fprintf(fptr,"%s ",entry->value); ``` ```diff \\write_in +for(int i=0;i<100;i++){ + if(str[i] == '\n'){ + str[i] = '\0'; + break; + } +} ``` 下方則分別是 list_sort 和 sort 透過 perf 的結果 ```shell $ sudo perf stat ./qtest [sudo] jason 的密碼： cmd> new l = [] cmd> write_in l = [pdkzxqk urtqetzmb xphdvzsyh supzxgyow cxeaktev wyuql vtfajil lqcgbu lahvil edumjumj rsjef xepbvpcs apirkz gvfxckep zescch drxto ofwbjac dyzxd auhebig yqnuxvd ptqyiq dvdvz neevakwbb lnfjogluq ldwsd gdstvu edhhnedc sbebvdi shfvcu kuhvx ... ] cmd> list_sort l = [zzzuyicq zzzraf zzzmrjaw zzzjvovj zzzboc zzywjszbm zzyny zzyeztfke zzybp zzxmqxpfd zzxlrt zzwssa zzwiivn zzvohxnq zzvnyx zzvmbjpm zzvlbjhes zzurua zzump zzubkkxg zztzj zzsvc zzsjam zzshzd zzrymhqxl zzrtfwuyg zzrjxmyy zzqltyuuo zzpwv zzoszh ... ] cmd> quit Freeing queue Performance counter stats for './qtest': 122.81 msec task-clock # 0.005 CPUs utilized 44 context-switches # 358.278 /sec 17 cpu-migrations # 138.426 /sec 3,596 page-faults # 29.281 K/sec 347,535,201 cpu_core/cycles/ # 2.830 GHz (78.88%) 126,844,097 cpu_atom/cycles/ # 1.033 GHz (9.15%) 271,891,031 cpu_core/instructions/ # 0.78 insn per cycle (78.88%) 152,802,458 cpu_atom/instructions/ # 0.44 insn per cycle (11.30%) 58,124,246 cpu_core/branches/ # 473.287 M/sec (78.88%) 28,816,395 cpu_atom/branches/ # 234.643 M/sec (11.30%) 1,930,343 cpu_core/branch-misses/ # 3.32% of all branches (78.88%) 497,569 cpu_atom/branch-misses/ # 0.86% of all branches (8.48%) TopdownL1 (cpu_core) # 57.3 % tma_backend_bound # 16.3 % tma_bad_speculation # 13.5 % tma_frontend_bound # 12.9 % tma_retiring (78.88%) TopdownL1 (cpu_atom) # 8.2 % tma_bad_speculation (10.67%) # 11.4 % tma_frontend_bound (13.92%) # 49.3 % tma_backend_bound # 49.3 % tma_backend_bound_aux (17.18%) # 27.7 % tma_retiring (18.48%) 25.852618230 seconds time elapsed 0.115623000 seconds user 0.008258000 seconds sys ``` ```shell $ sudo perf stat ./qtest cmd> new l = [] cmd> write_in l = [pdkzxqk urtqetzmb xphdvzsyh supzxgyow cxeaktev wyuql vtfajil lqcgbu lahvil edumjumj rsjef xepbvpcs apirkz gvfxckep zescch drxto ofwbjac dyzxd auhebig yqnuxvd ptqyiq dvdvz neevakwbb lnfjogluq ldwsd gdstvu edhhnedc sbebvdi shfvcu kuhvx ... ] cmd> sort l = [zzzuyicq zzzraf zzzmrjaw zzzjvovj zzzboc zzywjszbm zzyny zzyeztfke zzybp zzxmqxpfd zzxlrt zzwssa zzwiivn zzvohxnq zzvnyx zzvmbjpm zzvlbjhes zzurua zzump zzubkkxg zztzj zzsvc zzsjam zzshzd zzrymhqxl zzrtfwuyg zzrjxmyy zzqltyuuo zzpwv zzoszh ... ] cmd> quit Freeing queue Performance counter stats for './qtest': 92.46 msec task-clock # 0.008 CPUs utilized 29 context-switches # 313.644 /sec 8 cpu-migrations # 86.522 /sec 3,593 page-faults # 38.859 K/sec 263,663,077 cpu_core/cycles/ # 2.852 GHz (87.51%) 65,826,499 cpu_atom/cycles/ # 0.712 GHz (4.68%) 279,375,707 cpu_core/instructions/ # 1.06 insn per cycle (87.51%) 35,432,302 cpu_atom/instructions/ # 0.13 insn per cycle (8.13%) 63,239,656 cpu_core/branches/ # 683.956 M/sec (87.51%) 12,054,525 cpu_atom/branches/ # 130.373 M/sec (12.44%) 1,773,521 cpu_core/branch-misses/ # 2.80% of all branches (87.51%) 126,310 cpu_atom/branch-misses/ # 0.20% of all branches (12.49%) TopdownL1 (cpu_core) # 46.7 % tma_backend_bound # 19.1 % tma_bad_speculation # 17.0 % tma_frontend_bound # 17.3 % tma_retiring (87.51%) TopdownL1 (cpu_atom) # 84.8 % tma_bad_speculation (12.49%) # 11.1 % tma_frontend_bound (12.49%) # 63.0 % tma_backend_bound # 63.0 % tma_backend_bound_aux (12.49%) # 9.6 % tma_retiring (7.81%) 11.939195393 seconds time elapsed 0.088879000 seconds user 0.004232000 seconds sys ``` > 提醒終端機命令開頭要加 `$` 字號。 > [name=HenryChaing] ## tim_sort 我嘗試參考作業二將 tim_sort 引入並一起比較，但還是很疑惑下面的地方： ```c static inline size_t run_size(struct list_head *head) { if (!head) return 0; if (!head->next) return 1; return (size_t) (head->next->prev); } ``` 此處是在回傳 run 的 size，如果 head 是 NULL 就回傳 0 ，如果 head->next 是 NULL 救回傳 1 ，但我<s>不太能理解</s> 為何 `（size_t）head->next->prev` 是什麼，因為 head->next->prev 應該就是 head? :::danger 有疑惑就去做實驗，善用 GDB 分析。不懂就說不懂，沒有「不太能」這回事。 :notes: jserv ::: 其他的引入部份，則根據我的[作業二](https://hackmd.io/e8PRXrlrSuyAht9jbCTg7w)內容引入後進行修改。 ## code review ### Amazing Code Reviews: Creating a Superhero Collective 影片中筆記： ~~1. 在開發初期，就要確立好開發方向並接受反饋，而不能等已經開發一段時間後才回頭審視，另外也要有開放的心態來接受批評 2. 不要一次修改太多再提交，否則 reviewer 不容易看，reviews 的品質也會下降，而且這樣也比較容易在大型專案除錯。 3. 具體的 feedback 和解決方法，而不是只說 "這樣不好"，如果方向有誤，也要說明理由，而如果方向正確，也要給予正面回饋。~~~~ > <s>我英文太爛，後面有點看不懂講者要表達的..</s> :::danger 你真正不好的地方不是英文，而是怕被笑。「大部分的人一輩子洞察力不彰，原因之一是怕講錯被笑。想了一點點就不敢繼續也沒記錄或分享，時間都花在讀書查資料看別人怎麼想。看完就真的沒有自己的洞察了」([出處](https://www.facebook.com/chtsai/posts/pfbid0Sw9Bv8GN8houyS6A6Mvg5gtWXShKFgguhTHuNFsDDGn9XZQE7C64pBy5atB9gXtJl)) ::: 重新看了一次影片，這次詳細紀錄了我學到的： 1. 開發初期就確立方向和接受反饋，因為這麼做可以避免已經開發一段時間後發現規格不合而要重做。 2. 開放的心態接受批評 3. 程式碼不要一次修改太多後提交，否則 reviewer 很難檢查，每次提交小部份可以提昇 review 的品質並減少盲點。 4. 分解一個大的 reques並檢查每個元件，這樣才不會在發生錯誤時無法知道錯誤源頭(?)。 5. review 時針對程式或產品，而不是人，專注在怎麼讓我們共同開發的產品進步，並提出 actionable feedback 而不是單純對成品做出批評。 6. 當程式碼是好的，也要發出正面回應，讓開發者知道他在正確的方向。 7. feedback 必須具體且提出解決方案，例如是針對程式碼的哪部份、可能可以怎麼解決等，並說明原本不好的原因。 8. 避免過多人同時討論 9. 根據協作對象來寫 pr description，如果是長時間合作的對象，可以不用寫的非常詳細，因為他們原本就知道這些程式的用途，但如果是新進人員，則必須寫的詳細讓他可以快速進入狀況。 ### fetch 取得最新的變更首先，必須先建立一個 branch 並增加一個遠端的連線，這裡我取名叫 local_original_branch ，而遠端連線叫做 original_branch。 ``` git remote add original_branch https://github.com/sysprog21/lab0-c.git git fetch original_branch git checkout -b local_original_branch original_branch/master ``` 接下來要把我自己寫的部份 rebase 到變更的地方，這裡我把 head 移動到 local_original_branch 後用 rebase 讓其基底轉移到 master。 ``` git checkout local_original_branch 已切換至分支 “local_original_branch” 您的分支與上游分支 'original_branch/master' 一致。 jason@jason-System-Product-Name:~/linux-2024/lab0-c$ gitk jason@jason-System-Product-Name:~/linux-2024/lab0-c$ git rebase master ``` >這部份操作應有誤，應該要移動到 master，然後 rebase 到 local_original_branch 的 > 我認為你 rebase 是成功的， rebase 是將現在分支的所有 commit 紀錄重新 commit 到新的分支上，若是在 original_branch 上對 local_original_branch 進行 rebase ，則所有剛才 fetch 的 commit 紀錄會重新 commit 到你的 local_original_branch 上，這應該不是老師想要的結果。 > [name=HenryChaing] ``` git config pull.rebase true jason@jason-System-Product-Name:~/linux-2024/lab0-c$ git pull original_branch master 來自 https://github.com/sysprog21/lab0-c * branch master -> FETCH_HEAD warning: 已略過先前套用的 546502f 提交 warning: 已略過先前套用的 e44a210 提交 warning: 已略過先前套用的 216d14c 提交 warning: 已略過先前套用的 8dff308 提交 warning: 已略過先前套用的 44d8ac7 提交 warning: 已略過先前套用的 8b4fbd1 提交 warning: 已略過先前套用的 3c470a0 提交 warning: 已略過先前套用的 fba7b67 提交 warning: 已略過先前套用的 0543a39 提交 warning: 已略過先前套用的 e3f6e86 提交 warning: 已略過先前套用的 270a16d 提交提示：使用 --reapply-cherry-picks 以包含略過提交提示：Disable this message with "git config advice.skippedCherryPicks false" 自動合併 queue.c22) 衝突（內容）：合併衝突於 queue.c error: 不能套用 4660ae7... Implement q_free function ``` rebase 過程中會出現和 merge 的過程中會出現一些衝突，不過大部分都容易解決，只需要檢查衝突部份並貼上真正需要修改的部份即可。但完成後會發現，master 還停留在原本的地方，而 local_original_branch 才是在最新的地方，這應該就是剛才 rebase 時操作錯誤的問題。因此，我透過 `git reset --hard <commit id>` 強致直接把 master 移動到最新的地方。 > original_branch/master 位置正常不會變，會變得是 local_original_branch/master 以及 HEAD。 > [name=HenryChaing] :::success 回覆 HenryChaing: 在 fetch 之前，我的 git 結構應該如下： ```graphviz digraph _graph_name_ { rankdir=LR; commit1[label = "commit"] commit2[label = "commit"] commit3[label = "commit"] fork[label = "fork from sysprog21/lab0-c"] master[penwidth=0]; head[penwidth=0]; fork->commit1 commit1->commit2->commit3 master->commit3 head->commit3 } ``` 而在 fetch 後，我預計是變成這樣： ```graphviz digraph _graph_name_ { rankdir=LR; commit1[label = "commit"] commit2[label = "commit"] commit3[label = "commit"] fork[label = "fork from sysprog21/lab0-c"] master[penwidth=0]; head[penwidth=0]; local_original_branch[penwidth=0]; local_original_branch->newchange newchange[label = "new change"] fork->commit1 fork->newchange commit1->commit2->commit3 master->commit3 head->commit3 } ``` 因此我的想法是，我應該讓 master rebase 到 newchange上，讓整體結構變成： ```graphviz digraph _graph_name_ { rankdir=LR; commit1[label = "commit"] commit2[label = "commit"] commit3[label = "commit"] fork[label = "fork from sysprog21/lab0-c"] master[penwidth=0]; head[penwidth=0]; local_original_branch[penwidth=0]; local_original_branch->newchange newchange[label = "new change"] fork->newchange commit1->commit2->commit3 master->commit3 head->commit3 newchange->commit1 } ``` 但之後操作錯誤，把 local_original_branch rebase 到 master，然後又一陣胡亂操作（下次應該把胡亂操作過程紀錄...)，才會變成上面提到的 master 在奇怪的地方，而 local_original_branch 在最新的 commit 處，因此我才透過指令把 master 給搬到最新的地方。（如果我前面對 rebase 的操作有誤解，再麻煩告訴我） ::: 完成後透過 gitk 檢查如下，lab-0 中修改的部份後面接續著我修改的部份。 ![image](https://hackmd.io/_uploads/r19mtz_A6.png) 最後，透過 git push --force 來把資料 push 上去即可。 >下次應該在動作前注意，可以省掉很多麻煩。

Syntax	Example	Reference
# Header	Header	基本排版
- Unordered List	Unordered List
1. Ordered List	Ordered List
- [ ] Todo List	Todo List
> Blockquote	Blockquote
Bold font	Bold font
Italics font	Italics font
~~Strikethrough~~	~~Strikethrough~~
19^th^	19^th
H~2~O	H₂O
++Inserted text++	Inserted text
==Marked text==	Marked text
[link text](https:// "title")	Link
![image alt](https:// "title")	Image
`Code`	`Code`	在筆記中貼入程式碼
```javascript var i = 0; ```	`var i = 0;`
:smile:		Emoji list
{%youtube youtube_id %}	Externals
$L^aT_eX$	L^aT_eX
:::info This is a alert area. :::	This is a alert area.