# 2024q1 Homework1 (lab0) contributed by < [Dainel-0224](https://github.com/Daniel-0224/lab0-c) > ### Reviewed by `david965154` 1. > 這裡採取遞迴 `merge_sort` 來實作 `q_sort` 應該修改為 : 「這裡採取 `merge sort` 的遞迴版本來實作 `q_sort` 」較適當，加了底線會讓人誤以為你實作了這個函式，也應提到使用了下方函式 `q_merge_two` 完成 merge 的功能。 2. > 一開始想不到一個從頭走到尾的簡潔寫法，但在經過 [HotMercury](https://github.com/HotMercury/lab0-c) 及 [devarajabc](https://github.com/devarajabc/lab0-c) 的提醒，採取從尾走到頭的方式 可以解釋一下為什麼從頭走到尾不行，但可以從尾走到頭，例如 : 因為 `q_descend` 題目要求為 : 只要在此節點後方的節點有存在比此節點更大之成員 `value` 則刪去，因此等同於尋找佇列後方的嚴格遞減佇列，直接從後方找最大成員 `value` 並向前比對，只需逐一走訪一次就可以完成實作。 > 「從尾走到頭」不精準，因為在環狀雙向鏈結串列中，已是首尾相接，於是尾端必定會緊接著開頭。真正的關鍵是運用 prev 和 next 來存取節點的方向。 :notes: jserv ## 開發環境 ```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): 16 On-line CPU(s) list: 0-15 Vendor ID: GenuineIntel Model name: Intel(R) Core(TM) i7-10700K CPU @ 3.80GHz CPU family: 6 Model: 165 Thread(s) per core: 2 Core(s) per socket: 8 Socket(s): 1 Stepping: 5 CPU max MHz: 5100.0000 CPU min MHz: 800.0000 BogoMIPS: 7599.80 ``` ## 指定的佇列操作 ### `q_new` 用 `malloc `來配置 `head` 所需記憶體，並使用`INIT_LIST_HEAD`初始化`head`。要注意的是`malloc`不一定會成功，在配置記憶體失敗時，得到指標值會是 `NULL`，因此需要在配置後檢查`head`。 :::danger 無論標題和內文中，中文和英文字元之間要有空白字元 (對排版和文字搜尋有利) ::: ### `q_free` 藉由 `container_of` 巨集找到 `element_t` 結構的起始地址，`offsetof(type, member)` 可得知 `member` 在 `type` 這個結構體位移量。將絕對位址 `(char ) pmember` 減去 `offset` ，可得到結構體的起始位址。`head` 是個特例，無法藉由 `containerof` 巨集來找到對應的節點，因為後者並未嵌入到任何結構體之中，其存在是為了找到 `list` 整體。 ### `q_insert_head & q_insert_tail` `strdup` 有使用 `malloc` 來配置字串存放的記憶體空間，空間配置失敗時要釋放記憶體，這裡要釋放整個 `element_t`。 而 `q_insert_head` 、`q_insert_tail` 分別使用 `list_add` 和 `list_add_tail` 來串接節點。 ### `q_remove_head` 利用 `list_first_entry` 找到第一個 `element` ,並用 `list_del` 將其與佇列斷開連接，再利用 `strncpy` 複製字串。 ```c element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize) { if(!head || list_empty(head)) return NULL; element_t *first = list_first_entry(head, element_t, list); list_del(&first->list); if(sp && first->value){ strncpy(sp, first->value, bufsize - 1); sp[bufsize - 1] = '\0'; } return first; } ``` ### `q_remove_tail` 一開始我只將 `list_first_entry` 改為 `list_last_entry` ，但在參考< [alanjian](https://hackmd.io/@alanjian85/lab0-2023) >的想法後發現，這兩題程式碼相似度高，其實可以重複使用。 ```c element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize) { if(!head || list_empty(head)) return NULL; return q_remove_head(head->prev->prev, sp, bufsize); } ``` ### `q_size` 用 `list_for_each` 走訪每個節點，並隨之遞增 `count` 。 ### `q_delete_mid` 這裡使用了 `fast` 和 `slow` 兩個指標，當 `fast` 走到序列結尾時，`slow` 走到序列一半，再將這個 `element` 刪除即可。 ### `q_reverse` 使用 `list_for_each_safe` 來走訪序列是因為需要 `safe` 來紀錄當前處理節點的下個節點，在使用 `list_move` 將 `node` 移至首位。 ### `q_reverseK` 我的想法是在走訪了 k 個節點後，將這 k 個節點利用 `list_cut_position` 從原序列截斷後再利用 `q_reverse` 反轉，最後再用 `q_splice` 接回原序列。我一開始想利用 `q_new` 創建一個節點來連接截斷的序列，然後發現在這個函式中不能使用 `malloc` ，並經過同學的題點改為使用 `LIST_HEAD` 。 ``` $ ./qtest <test.cmd FATAL ERROR: Calls to malloc disallowed FATAL Error. Exiting ``` ```diff list_for_each_safe (node, safe, head) { if (count != 1) { count--; } else { - tmp = q_new(); + LIST_HEAD(tmp); count = k; list_cut_position(tmp, cut, node); q_reverse(tmp); list_splice(tmp, cut); cut = safe->prev; } } ``` ### `q_swap` `q_swap` 可以想成 `q_reverseK` 而 `k = 2` 。 ### `q_descend ＆ q_ascend` :::danger 明確標注同學的 GitHub 名稱。 ::: 一開始想不到一個從頭走到尾的簡潔寫法，但在經過 [HotMercury](https://github.com/HotMercury/lab0-c) 及 [devarajabc](https://github.com/devarajabc/lab0-c) 的提醒，採取從尾走到頭的方式，在過程中會判斷目前節點與前一個節點的大小，如 `descend` 前一個節點小於目前節點，則需要將前一個節點刪除，相反則移動目前節點到前一個節點。 ### `q_sort` 這裡採取遞迴 `merge sort` 來實作 `q_sort` ，並且使用 `q_merge_sort` 來達成兩串列合併，一開始一樣以快慢兩個指標來找出中間點，再利用 `list_cut_position` 將串列分成兩串再進行一次 `q_sort`。 :::danger 你如何確保目前的測試程式已涵蓋排序演算法的最差狀況？ ::: ### `q_merge_two` 這裡逐一比對兩個串列的節點的大小，合併的方式是從輸入的二個串列中，根據 `descend` 參數取較小或較大的，放到一個暫存串列 `tmp` 中。 一開始我是以 `list_add_tail` 這個函式來將節點串接上新的串列，但在執行時遇到無窮迴圈。發現是這個函式沒有將節點從原本串列移除，最後改用 `list_move_tail` 將問題解決。 ```diff while (!list_empty(left) && !list_empty(right)) { element_t *l = list_entry(left->next, element_t, list); element_t *r = list_entry(right->next, element_t, list); if (strcmp(l->value, r->value) >= 0) { - list_add_tail(&l->list, &tmp); + list_move_tail(&l->list, &tmp); } else { - list_add_tail(&l->list, &tmp); + list_move_tail(&r->list, &tmp); } } ``` ### `q_delete_dup` 我的想法是用兩個指標指比對兩個節點是否相同，相同則刪除。原本我使用 `list_for_each_entry_safe` 來做比對，但是在 `strcmp(cur->value, post->value)` `post` 指向 `head` 時會造成 `Segmentation fault occurred. You dereferenced a NULL or invalid pointerAborted` 。 ```diff bool q_delete_dup(struct list_head *head) { if(!head) return false; bool flag = false; element_t *post, *cur; list_for_each_entry_safe(cur, post, head, list) { - if(!strcmp(cur->value, post->value)) { + if(&post->list != head && !strcmp(cur->value, post->value)) { flag = true; list_del(&cur->list); q_release_element(cur); } else { if(flag) { list_del(&cur->list); q_release_element(cur); flag = false; } } } return true; } ``` ### `q_merge` 利用兩個指標來走訪 `chain` ，每次迭代合併兩個 `q_contex_t` ，因為這裡使用 `q_merge_two` 來做合併，因此 `first` 串列會越來越長，使得走訪成本越來越高。 :::danger 需要有更多討論。 ::: --- ## 論文研讀〈[Dude, is my code constant time?](https://eprint.iacr.org/2016/1123.pdf)〉 ### Step1. Measure execution time **a ) class definition** 建立兩種類型的資料，並重複測量其作為輸入資料時的執行時間。 固定資料：這包括了特殊的極端情況。(such as low-weight input for arithmetic operations) 隨機資料：隨機生成的資料，以模擬實際情況下的不確定性和變化性。 **b ) cycle counters** 使用 CPU 的 cycle clock， 可準確取得執行時間。 **c ) environment conditions** 最大限度地減少環境變化對結果的影響，每次測量都對應一個隨機選擇的類別 ### Step2. Post-processing 在統計分析之前，我們對每個測量值進行了一些處理。 **Cropping** ：由於測量過程中可能會受到作業系統或其他活動的干擾，我們需要對測量值進行裁剪，去除受外部干擾的部分，以獲得準確的執行時間。 **Higher-order preprocessing** : 根據所應用的統計測試，去應用像是 centered product mimicking higher-order DPA attacks 預處理得到更好的數據。 ### Step3. Apply statistical test 採用統計檢定方法來試圖反駁「兩個時序分佈相等」的原假設。成功反駁這個假設將證明該假設錯誤，從而表明程式執行時間不是常數。 * t-test：為 dudect 所使用的 Welch's t-test。 ## Valgrind 與 Address Sanitizer 這部份是因為我在 `q_free` 少寫了一行 `free(head)` 所導致的。 ``` $ valgrind -q --leak-check=full ./qtest <tttt.cmd ``` ``` l = [] l = [b] Freeing queue ERROR: Freed queue, but 1 blocks are still allocated ==20977== 56 bytes in 1 blocks are still reachable in loss record 1 of 1 ==20977== at 0x4848899: malloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so) ==20977== by 0x10F327: test_malloc (harness.c:133) ==20977== by 0x10F72C: q_new (queue.c:17) ==20977== by 0x10CDE3: do_new (qtest.c:155) ==20977== by 0x10E011: interpret_cmda (console.c:181) ==20977== by 0x10E5C6: interpret_cmd (console.c:201) ==20977== by 0x10F230: run_console (console.c:691) ==20977== by 0x10D403: main (qtest.c:1258) ==20977== ``` 更改完程式碼後執行 `＄valgrind --tool=massif ./qtest <tttt.cmd` 得到 `massif.out.19175` 檔案。再利用以下指令可視化程式執行時期的記憶體行為。 ``` $ ms_print massif.out.19175 ``` ``` -------------------------------------------------------------------------------- Command: ./qtest Massif arguments: (none) ms_print arguments: massif.out.19175 -------------------------------------------------------------------------------- KB 20.45^ ::: | :::#: | : #: | : #: | : #: : | @ #: @ | :@ #: @ | :@ #: @ | :@ #: @ | :@ #: @ | :@ #: @ | :@ #: @ | :@ #: @ | :@ #: @ | :@@@ #: @ | :@@@ #: @@ | :@@@ #: @@ | :@@@ #: @@ | :@@@ #: @@ | @@:@@@ #: @@ 0 +----------------------------------------------------------------------->ki 0 313.0 ``` ``` $massif-visualizer massif.out.19175 ``` ![Screenshot from 2024-03-04 23-34-46](https://hackmd.io/_uploads/HJjC9Dmaa.png) ## 實作 shuffle 根據〈[你所不知道的 C 語言: linked list 和非連續記憶體](https://hackmd.io/@sysprog/c-linked-list#Fisher%E2%80%93Yates-shuffle)〉中提到的 `Fisher–Yates shuffle` 演算法來實作 `shuffle` 。 * 假設初始的序列如下: | 隨機數範圍 | 選擇隨機數 | 原始序列 | | ---------- | ---------- |:--------- | | | | 1 2 3 4 5 | * 從 1~5 間隨機選一數字，例如這裡的 `3`，將原始序列從左開始數的第 3 個數字和最後 1 個數字對調 | 隨機數範圍 | 選擇隨機數 | 更新後序列 | | ---------- | ---------- |:--------- | | 1-5 | 3 | 1 2 5 4 3 | * 從 1~4 間隨機選一數字，以這裡為例是 2，所以把原始序列從左開始數的第 2 個數字和倒數第 2 個數字交換 | 隨機數範圍 | 選擇隨機數 | 更新後序列 | | ---------- | ---------- | ------------- | | 1-4 | 2 | 1 4 5 2 3 | * 重複這個流程，直到隨機數範圍為 0 ### 實作 1. 模仿 do_reverse 在 qtest.c 中產生 do_shuffle。 2. 在 queue.c 中實作 q_shuffle ``` Expectation: 41666 Observation: {'1234': 41886, '1243': 41890, '1324': 41603, '1342': 41557, '1423': 41721, '1432': 41872, '2134': 41610, '2143': 41395, '2314': 41707, '2341': 41679, '2413': 41962, '2431': 41945, '3124': 41790, '3142': 41464, '3214': 41562, '3241': 41347, '3412': 41504, '3421': 41982, '4123': 41643, '4132': 41867, '4213': 41370, '4231': 41482, '4312': 41600, '4321': 41562} chi square sum: 21.029184466951474 ``` ![Figure_1](https://hackmd.io/_uploads/H15rcPNpT.png)