2024q1 Homework1 (lab0)

# 2024q1 Homework1 (lab0) contributed by < [ChengChaoChun](https://https://github.com/ChengChaoChun) > ### Reviewed by `Chloexyw` 1. 根據 GitHub 的 `q_ascend` 我有試跑看看程式，但是結果都是呈現，可以檢查看看程式碼是否有 Segmentation fault 的問題 ``` l = [8 9 3] cmd> ascend ERROR: Attempted to free unallocated block. Address = 0x5bf5835591c8 ERROR: Attempted to free unallocated or corrupted block. Address = 0x5bf5835591c8 Segmentation fault occurred. You dereferenced a NULL or invalid pointerAborted (core dumped) ``` 2. 2^k 可以參考 [常用 LaTeX 數學符號指令](https://hackmd.io/@CynthiaChuang/Basic-LaTeX-Commands) 將數學式改寫成 $2^k$ ### Reviewed by `chishuo9810` 1.已有明確翻譯詞彙者，就使用該中文詞彙，避免過多中英夾雜。 `traverse` 應直接使用`走訪`，`doubly circular linked list` 應改作 `雙向鏈節串列`。 q_size() > 使用 list_for_each 巨集來 traverse 佇列，計算節點個數 q_swap() > Traverse 佇列的節點並改變指標的指向，最後佇列的頭節點指標也要記得修改。 q_ascend() > 因為佇列是 doubly circular linked list 2. 查看了你 github 中註解掉的 q_sort，看起來是要使用快滿指標且遞迴的方法來實現合併排序法但是失敗了。 ```c struct list_head l; l.next = slow; q_sort(&l, descend); ``` * 命名問題：這裡的 `l` 明顯示要賦予右半佇列一個 `head` 節點，但是卻命名為 `l`，這樣的取名方式不直觀容易讓人引起誤會。 * 未初始化：宣告了 `l` 而沒有初始化，這樣並沒有配置空間給它，僅僅是一個具有兩個指標的結構，導致接著要遞迴進入 `q_sort` 時一開始就會因為 `l` 為空而直接跳出函式。 ## 開發環境 ```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: 45 bits physical, 48 bits virtual Byte Order: Little Endian CPU(s): 2 On-line CPU(s) list: 0,1 Vendor ID: GenuineIntel Model name: Intel(R) Core(TM) i5-8265U CPU @ 1.60GHz CPU family: 6 Model: 142 Thread(s) per core: 1 Core(s) per socket: 1 Socket(s): 2 Stepping: 11 BogoMIPS: 3600.00 ``` ## 指定的佇列操作 ### `q_new` :::danger 1. 留意[資訊科技詞彙翻譯](https://hackmd.io/@sysprog/it-vocabulary) 2. allocate 的翻譯是「配置」，以區格 dispatch (分發/分配) 的翻譯。 3. 避免非必要的項目縮排 (即 `* `)，以清晰、明確，且流暢的漢語書寫。 4. 改進你的漢語表達。 ::: 建立佇列的開頭節點，使用 malloc <s>函數</s> 來<s>分配</s> 記憶體空間 (struct list_head)。若記憶體空間配置失敗將函式返回 NULL，函式返回配置到的記憶體空間地址。 ### `q_free` 判斷佇列的開頭節點是否為 NULL ，若是 NULL 則返回，不需要執行其他操作由於 q_free 功能需要逐一走訪所有的佇列節點，我們可以使用 `list.h` 的巨集 `list_for_each_entry_safe` 對於每個 element_t 節點需要釋放 value 的記憶體空間，並且將該節點從佇列中移除(可以使用 `list.h` 的 `list_del` 函式)，移除後再釋放該節點空間再處理完佇列的每個節點後，最後需要再釋放掉佇列的開頭節點空間 ```c /* Free all storage used by queue */ void q_free(struct list_head *head) { if(!head)return; element_t *entry; element_t *safe; list_for_each_entry_safe(entry, safe, head, list){ free(entry->value); list_del(&entry->list); free(entry); } free(head); } ``` :::danger 使用作業指定的程式碼縮排風格。 ::: ### `q_insert_head` 判斷佇列的開頭節點是否為 NULL ，若是 NULL 則返回 false 建立 element_t 節點，若 malloc 記憶體配置失敗則返回 false 使用 strdup() 函式將字符串複製到新建立的空間，由element_t 的 value 指向這個空間如果 strdup() 函式新建空間失敗，將 element_t 節點空間釋放並返回false 再成功完成第2和3點後，使用 `list.h` 的 `list_add` 函式加入到佇列中 ```c /* Insert an element at head of queue */ bool q_insert_head(struct list_head *head, char *s) { if(!head)return false; element_t *ele = malloc(sizeof(element_t)); if(!ele)return false; ele->value = strdup(s); if (!ele->value) { free(ele); return false; } list_add(&ele->list, head); return true; } ``` ### `q_insert_tail` 方法同 `q_insert_head` ，將 `list_add` 函式替換成 `list_add_tail` 即可 ### `q_remove_head` 若佇列的開頭節點為 NULL 或佇列沒有節點時，返回 NULL。使用 `list_first_entry` 巨集來找到佇列的第一個節點，並使用 `list_del` 函式把該節點從佇列中刪除，需要判斷參數的字符串指標不為空，若不為空才將第一個節點的 value 指標指向的字符串複製給函式參數的指標。 ```c /* Remove an element from head of queue */ element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize) { if(!head || list_empty(head)){ return NULL; } element_t *ele = list_first_entry(head, element_t, list); list_del(&ele->list); if(sp && ele->value){ memcpy(sp, ele->value, bufsize); sp[bufsize - 1] = '\0'; } return ele; } ``` ### `q_remove_tail` 實作方法同 `q_remove_head` ，將尋找第一個節點替換成尋找最後一個節點即可 :::danger HackMD 不是讓你張貼完整程式碼的地方，GitHub 才是！因此你在開發紀錄只該列出關鍵程式碼 (善用 diff 標示)，可附上對應 GitHub commit 的超連結，列出程式碼是為了「檢討」和「便於他人參與討論」，不是用來「假裝自己有付出」 ::: ### `q_size` 使用 `list_for_each` 巨集來走訪佇列，計算節點個數 ### `q_delete_mid` 若開頭節點為空或者佇列為空就返回 false。使用快指標和慢指標的技巧找到佇列的中間節點，將該節點從佇列中移除，並釋放節點的記憶體空間 ```c /* Delete the middle node in queue */ bool q_delete_mid(struct list_head *head) { if(!head||list_empty(head)){ return false; } struct list_head *fast = head->next; struct list_head *slow = head->next; while (fast != head && fast->next != head) { slow = slow->next; fast = fast->next->next; } list_del(slow); free(slow); // https://leetcode.com/problems/delete-the-middle-node-of-a-linked-list/ return true; } ``` ### `q_reverse` 若開頭節點為空或者佇列為空就返回。使用 `list_for_each_safe` 巨集定義中 safe 參數紀錄當前節點的下一個節點，這裡不適合使用 `list_for_each` 巨集，因為 `q_reverse` 函式需要改變當前節點的 list_head 的指標的指向，因此需要額外紀錄原佇列的當前節點的下一個節點，否則指標指向改變後就無法找到原先佇列的下一個節點了(在 `list_for_each_safe` 巨集定義中 safe 參數紀錄當前節點的下一個節點)。把每個節點的 `list_head` 的 next 指標指向改成原先的 prev 指標紀錄值，prev 指標指向改成 next 紀錄值(safe 節點)，最後以同樣方法修改佇列的開頭節點。 :::danger 使用作業指定的程式碼縮排風格。 ::: ```c void q_reverse(struct list_head *head) { if(!head || !head->next){ return; } struct list_head *node; struct list_head *safe; list_for_each_safe(node, safe, head){ node->next = node->prev; node->prev = safe; } node = head->next; head->next = head->prev; head->prev = node; } ``` :::danger HackMD 不是讓你張貼完整程式碼的地方，GitHub 才是！因此你在開發紀錄只該列出關鍵程式碼 (善用 diff 標示)，可附上對應 GitHub commit 的超連結，列出程式碼是為了「檢討」和「便於他人參與討論」，不是用來「假裝自己有付出」 ::: ### `q_delete_dup` 使用 `list_for_each_entry_safe` 巨集走訪佇列元素。檢查當前走訪的節點是否與下一個的節點的 value 重複 (strcmp)。若倆 value 不相同，接著繼續走訪佇列；否則尋找佇列中所有相鄰且相同value 的節點，將這些 value 重複的節點的前一個節點與 value 重複的節點的下一個節點相連接。 ### `q_swap` 走訪佇列的節點並改變指標的指向，最後佇列的頭節點指標也要記得修改。 ### `q_ascend` `q_ascend` 函式要將原本的佇列改成 `element_t` 的 `value` 嚴格遞增的佇列。因為佇列是雙向鏈節串列，因此這裡可以很方便從最後一個節點往回 traverse。對於每個節點比較它們的 value 是否比之前訪問過的節點的 value 還要大，若成立則將節點移除，否則繼續訪問前一個節點。 ### `q_descend` 實現邏輯與 `q_ascend` 相同 ### `自動評分結果` Failed: 3,4,5,6,14,15 ## 研讀 Linux 核心原始程式碼的 [lib/list_sort.c ](https://github.com/torvalds/linux/blob/master/lib/list_sort.c) 目前還沒有完全理解 lib/list_sort.c 是如何排序的，我嘗試寫下分析的過程 ### `list_sort` 每次的合併的過程是將兩個長度同為 $2^k$ 的 linked list 合併成長度為 $2^{k+1}$ 的 linked list ``` * This mergesort is as eager as possible while always performing at least * 2:1 balanced merges. Given two pending sublists of size 2^k, they are * merged to a size-2^(k+1) list as soon as we have 2^k following elements. ``` count 表示 pending list 的長度。 pending list 每新增一個節點 count 就會+1，在每次 +1 的過程一定會產生進位，這個進位用 bit k 表示，也就是說 bit k 被置為 1 而 bit k 之前的 bit 都是 0 ( k 不表示特定的 bit ，而是表示進位的 bit )。 count 的值會決定要不要合併 list ex: 0b0 -> 0b1 ,可以理解為 k=1 且 bit 0 被置為 0 0b10111 -> 0b11000 , k=4 且小於 k 的 bit 全為 0 ``` * The merging is controlled by "count", the number of elements in the * pending lists. This is beautifully simple code, but rather subtle. * * Each time we increment "count", we set one bit (bit k) and clear * bits k-1 .. 0. Each time this happens (except the very first time * for each bit, when count increments to 2^k), we merge two lists of * size 2^k into one list of size 2^(k+1). ``` 在 do while 的每次循環中， pending list 會新增 list 指向的第一個節點，然後 list 指向 list 的下一個節點。 pending list 中的節點是使用 prev 指標鏈接起來的，同時 next 指標都是 null ，也就是 pending list 是單向鏈結串列。 ```c /* Move one element from input list to pending */ list->prev = pending; pending = list; list = list->next; pending->next = NULL; count++; ``` 在 for 迴圈中會計算起始位為 1 且連續為 1 的位元數量，每次循環 tail 移動到下一個節點。因為 pending list 是由 prev 指標鏈接起來的，所以 tail = &(*tail)->prev; 。 ex: 若 bits = 0b111， tail 最終會指向pending list 的第三個節點。在 for 迴圈結束後第一個 bit 一定是 0 ，除了第一個 bit 以外，如果還有 bit 為 1 ， if 判斷式就會成立，即進行合併動作 ```c size_t bits; struct list_head **tail = &pending; /* Find the least-significant clear bit in count */ for (bits = count; bits & 1; bits >>= 1) tail = &(*tail)->prev; /* Do the indicated merge */ if (likely(bits)) { struct list_head *a = *tail, *b = a->prev; a = merge(priv, cmp, b, a); /* Install the merged result in place of the inputs */ a->prev = b->prev; *tail = a; } ``` ## 在 qtest 提供新的命令 shuffle 這個部分我不知道怎麼做，於是我從 [willwillhi](https://hackmd.io/@willwillhi/lab0-2023#%E5%9C%A8-qtest-%E6%96%B0%E5%A2%9E-shuffle-%E5%91%BD%E4%BB%A4) 的文章學習如何完成 shuffle 命令。 ### `shuffle` 在 queue.[ch] 中實現 shuffle 功能，參考 [willwillhi](https://hackmd.io/@willwillhi/lab0-2023#%E5%9C%A8-qtest-%E6%96%B0%E5%A2%9E-shuffle-%E5%91%BD%E4%BB%A4)。 `console.h` 介面中提供 `ADD_COMMAND` ```c /* Add a new command */ void add_cmd(char *name, cmd_func_t operation, char *summary, char *parameter); #define ADD_COMMAND(cmd, msg, param) add_cmd(#cmd, do_##cmd, msg, param) ``` 在 `qtest.c` 中完成 do_shuffle 函式，用於獲取使用者的輸入，並反饋，接著在 console_init 函式中添加 shuffle 命令。 ``` ADD_COMMAND(shuffle, "Do Fisher-Yates shuffle", ""); ``` 輸入 `help` 命令後，`qtest` 新增了 shuffle 命令 ``` shuffle | Do Fisher-Yates shuffle ``` 功能展示: ``` cmd> show Current queue ID: 0 l = [butterfly penguin giraffe panda meerkat gerbil bear dolphin] cmd> shuffle l = [meerkat giraffe panda penguin bear gerbil butterfly dolphin] cmd> shuffle l = [bear penguin panda meerkat dolphin gerbil giraffe butterfly] cmd> shuffle l = [bear dolphin meerkat giraffe penguin gerbil butterfly panda] cmd> shuffle l = [gerbil panda meerkat butterfly giraffe bear penguin dolphin] ``` ## 研讀論文〈[Dude, is my code constant time?](https://eprint.iacr.org/2016/1123.pdf)〉以前沒有學習過資安相關的課題，論文中還有很多地方不太了解。 ### side-channel attacks (旁路攻擊) [駭客辭典：什麼是旁路攻擊？](https://www.inside.com.tw/article/23299-what-is-a-side-channel-attack) 旁路攻擊是用電腦不斷散發出來的訊息痕跡，解讀其中各種模式的攻擊手法。 ### Timing attacks (時序攻擊) Timing attacks example : [Cracking passwords using ONLY response times | Secure Python](https://www.youtube.com/watch?v=XThL0LP3RjY) 時序攻擊是一種旁道攻擊，攻擊者通過分析執行加密算法所花費的時間來嘗試破壞密碼系統。一個簡單的例子是，服務器將用戶的密碼以字符逐個比對，當比對到錯誤的<s>字符</s> ?? 時立刻反饋，這樣當輸入的密碼正確的比例越來越高時，系統反饋的時間會更長。計算系統的反饋時間，在多次嘗試下最終便能破解密碼。 ### dudect 早期手工檢查組合語言來確認程式是否有時序漏洞，這相當的耗時。後來出現幾款工具可以用來檢查代碼的時序漏洞，而它們共同的缺點是要在相同的硬體平台上執行。 dudect 工具解決了這個問題。

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.