2023q1 homework1 (lab0)開發日誌

# 2023q1 homework1 (lab0)開發日誌 contributed by < `Urbaner3` > :::warning 注意 GitHub 帳號名稱。我已經幫你修改了。 > [name=yanjiew1] ::: :::info 感謝，其實我也很猶豫，那是我一開始設定的情形。 > [name=Urbaner] ::: ###### tags: `linux2022`,`linux kernel` ### Reviewed by `yanjiew1` - commit message 語意表達不太清楚，開頭沒有大寫。例如： [c7fe7ff](https://github.com/Urbaner3/lab0-c/commit/c7fe7ff5132087ae7d32f1ff08f01d1c5f757e25) ，`implem_t del_mid ` 可改為 `Implement q_delete_mid` 。 - Coding style 沒有符合規範，建議善用 `clang-format -i` 來協助調整 Coding style 。例如下方 `q_delete_dup` 的程式： ```c= if(strcmp(val1->value, val2->value) == 0){ list_del(val1); q_release_element(cur); break; } else printf("mulp is %c\n",mulp); ``` 5, 6 行： `else` 和 `}` 應為同一行；第 1 行： `)` 和 `{` 中間要有空格。可改為： ```c= if(strcmp(val1->value, val2->value) == 0) { list_del(val1); q_release_element(cur); break; } else printf("mulp is %c\n", mulp); ``` - 完成度不高，沒達到作業要求，但可以從共筆中看到你的努力。未來繼續努力，加油！ ## 實驗環境 ```shell! (base) urbaner@urbaner:~$ gcc --version gcc (Ubuntu 12.2.0-3ubuntu1) 12.2.0 (base) urbaner@urbaner:~$ 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): 4 On-line CPU(s) list: 0-3 Vendor ID: GenuineIntel Model name: Intel(R) Core(TM) i3-7100 CPU @ 3.90GHz CPU family: 6 Model: 158 Thread(s) per core: 2 Core(s) per socket: 2 Socket(s): 1 Stepping: 9 CPU(s) scaling MHz: 21% CPU max MHz: 3900.0000 CPU min MHz: 800.0000 BogoMIPS: 7799.87 Virtualization features: Virtualization: VT-x Caches (sum of all): L1d: 64 KiB (2 instances) L1i: 64 KiB (2 instances) L2: 512 KiB (2 instances) L3: 3 MiB (1 instance) NUMA: NUMA node(s): 1 NUMA node0 CPU(s): 0-3 ``` ## 作業要求 > [lab0](https://hackmd.io/@sysprog/linux2023-lab0) [queue.c 介面](https://hackmd.io/@sysprog/linux2023-lab0/%2F%40sysprog%2Flinux2023-lab0-a#-%E6%94%B9%E5%AF%AB%E8%87%AA-CMU-%E9%9B%BB%E8%85%A6%E7%B3%BB%E7%B5%B1%E6%A6%82%E8%AB%96%E7%9A%84%E4%BD%9C%E6%A5%AD) - `q_new`: 建立新的「空」佇列; - `q_free`: 釋放佇列所佔用的記憶體; - `q_insert_head`: 在佇列開頭 (head) 插入 (insert) 給定的新節點 (以 LIFO 準則); ︙ (後續…參閱[queue.c 介面]) ## 開發過程 ### 簡介：完成作業要求，得到一個完整可控制排序的介面，包含自動偵錯、結果輸出、測試。熟悉專案開發環境，多人一起合作，認識程式從編碼，執行過程中控制，錯誤停止相關的觀念及技術等。這份作業可以輸入多個文字節點，利用 linux 內核鏈結序列結構，依照開頭順序，做需要的處理，包含排序、刪除重複、交換、翻轉順序等等。如[例題：刪除重複](https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/)。 [你所不知道的 C 語言：編譯器和最佳化原理篇](https://hackmd.io/@sysprog/c-compiler-optimization)，背景知識回顧: The C++ Build Process Explained 此章節有 AST 產生之程序，以利於確認所有標頭檔，如下： ```shell! gcc -H -O0 -std=c99 -g -c -o queue.o queue.c ``` 參考作業： [laneser_2022q1](https://hackmd.io/@laneser/linux2022_lab0) ，[共筆示範](https://hackmd.io/@cccccs100203/linux2020-lab0) ### q_new 三步驟，配置空間、檢查開頭非空、控制指標。 :::warning 建議寫清楚一點，這樣子太文言看不懂 > [name=yanjiew1] ::: :::info 我放程式碼加上註解 > [name=Urbaner3] ::: ```cpp! struct list_head *q = malloc(sizeof(struct list_head)) // 配置空間 if (!list_empty(q)) // 檢查開頭非空 INIT_LIST_HEAD(q); //控制指標 return q; ``` ```diff @@ -16,7 +16,8 @@ { struct list_head *q = malloc(sizeof(struct list_head)); if (!list_empty(q)) - INIT_LIST_HEAD(q); + return NULL; + INIT_LIST_HEAD(q); return q; } ``` 改為 [`!q`寫法](https://github.com/yanjiew1/lab0-c/commit/0f09bf6ab87795c13f8aae2e6f773e48ce41eb0a) 通過 `make test` 測試13，原理待釐清。 ### q_free (1)element_t (2)q_release_element (3)list_for_each_entry_safe 經過兩次修改三處，閱讀並理解後，確認函數為如下： ```cpp void q_free(struct list_head *l) { if (l == NULL) return; element_t *n, *s; list_for_each_entry_safe (n, s, l, list) q_release_element(n); free(l); } ``` 老師舉 yanjiew 同學的例子，讓我另一個疑惑，free 到底作用在哪個結構更有興趣去探討了。 :::warning `free` 要作用在當初用 `malloc` 配置記憶體的結構上。故串列的頭是 `struct list_head` ，而串上去有存值的節點是 `element_t` 。 > [name=yanjiew1] ::: ### q_insert_head & tail ~~因為對list結構，只知道細節，目前當作規格一樣遵守，日後維護時一併觀察。~~ 越用越習慣了。注意到需要用 strdup 函數，並將 insert 共用部份縮減為 part_ins 函式。 ```cpp element_t *part_ins(char *s) { element_t *new_ele = malloc(sizeof(element_t)); if (new_ele == NULL) return NULL; new_ele->value = strdup(s); if (new_ele->value == NULL) { free(new_ele); return NULL; } return new_ele; } bool q_insert_head(struct list_head *head, char *s) { if (head == NULL) return false; element_t *new_ele = part_ins(s); if (new_ele == NULL) return false; list_add(&new_ele->list, head); return true; } bool q_insert_tail(struct list_head *head, char *s) { if (head == NULL) return false; element_t *new_ele = part_ins(s); if (new_ele == NULL) return false; list_add_tail(&new_ele->list, head); return true; } ``` :::warning 可以想想 `q_insert_tail` 可以怎麼利用 `q_insert_head` 來達成。可以參考[我寫的](https://github.com/yanjiew1/lab0-c/blob/92d98c6902dcc681297d2485141a51508100f6a3/queue.c#L70)。 > [name=yanjiew1] ::: ### q_remove_head 很疑惑 q_remove_head 函數，其中的兩個參數，{ char *sp, size_t bufsize }，還有 q_remove_head 程式碼的 macro 巨集 container_of，發現 jserv 之前有做說明 [container_of](https://hackmd.io/@sysprog/linux-macro-containerof) 附註於[你所不知道的 C 語言: linked list 和非連續記憶體(含目錄)](https://hackmd.io/@owlfox/BJkrdnExL/https%3A%2F%2Fhackmd.io%2Fs%2FSkE33UTHf#%E4%BD%A0%E6%89%80%E4%B8%8D%E7%9F%A5%E9%81%93%E7%9A%84-C-%E8%AA%9E%E8%A8%80-linked-list-%E5%92%8C%E9%9D%9E%E9%80%A3%E7%BA%8C%E8%A8%98%E6%86%B6%E9%AB%94) 另外 [linked list 案例實作](https://hackmd.io/@sysprog/c-linked-list#Linked-list-%E5%9C%A8-Linux-%E6%A0%B8%E5%BF%83%E5%8E%9F%E5%A7%8B%E7%A8%8B%E5%BC%8F%E7%A2%BC)，這兩個連結是一樣的，但一個有包含你所不知道的 C 語言系列目錄。此處與 [link](https://hackmd.io/@sysprog/linux2023-lab0/%2F%40sysprog%2Flinux2023-lab0-b#%E8%BF%BD%E8%B9%A4%E8%A8%98%E6%86%B6%E9%AB%94%E9%85%8D%E7%BD%AE%E5%92%8C%E9%87%8B%E6%94%BE%E7%9A%84%E7%8B%80%E6%B3%81) 情形類似，可以注意它的插圖，幫助理解。注意有用到 strncpy 貼上 bufsize ，有些同學提到使用 memcpy 列於考慮中。[好的說明](https://hackmd.io/@Risheng/linux2023-lab0#q_remove_head)，類似複製變數值的道理，將第三個變數稱作 buffer ，最後在結尾補上0，完成刪除的動作。 ```cpp! element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize) { element_t *n = container_of(head->next, element_t, list); list_del(head->next); if (sp != NULL) { strncpy(sp, n->value, bufsize - 1); sp[bufsize - 1] = '\0'; } return n; } ``` :::warning 共筆中英文和中文之間要有空格。漢語表達不太清楚。例如：「有用到 strncpy 貼上 bufsize 」這句話，應該可以改成「使用 `strncpy` 函式，將 `n->value` 中的字串複製到 `sp` 中，最多複製 `bufsize - 1` 個字元。」。可以善用 ChatGPT 來改進。 > [name=yanjiew1] ::: ### q_remove_tail 修改一次兩處： (1)head 要做檢查。 (2)可以盡量使用 q_remove_head 因為對head的檢查，以及類似的指標是否為空，此一類檢查另我覺得很冗贅，所以思索原因並設計實驗確認，如以下，實驗方法與結果。 ```shell! (base) urbaner@urbaner:~/linux2022/lab0-c$ make SANITIZER=1 CC queue.o queue.c: In function ‘q_new’: queue.c:20:8: error: ‘rr’ is used uninitialized [-Werror=uninitialized] 20 | if (!rr) | ^ queue.c:19:23: note: ‘rr’ was declared here 19 | struct list_head *rr; | ^~ cc1: all warnings being treated as errors make: *** [Makefile:50: queue.o] Error 1 (base) urbaner@urbaner:~/linux2022/lab0-c$ vim queue.c ``` :::warning 只看文字無法了解你想表達的意思，建議在共筆貼出此段程式碼，文字描述寫完整一點。 > [name=yanjiew1] ::: :::info 已修正並標示下方段落。 >[name=Urbaner3] ::: ### 實驗方法與結果 ```cpp! struct list_head *q_new() { struct list_head *q = malloc(sizeof(struct list_head)); puts("check if sturct initial and malloc are null"); if (q != NULL) printf("malloc is not null\n"); else puts("sorry, malloc is null @@"); if (list_empty(q)) puts("list is empty"); else if (list_empty(q)==0) puts("not empty!!"); if (q != NULL) INIT_LIST_HEAD(q); if (q != NULL) printf("malloc is not null\n"); else puts("sorry, malloc is null @@"); if (list_empty(q)) puts("list is empty"); else if (list_empty(q)==0) puts("not empty!!"); return q; } void q_free(struct list_head *l) { if (l == NULL) return; element_t *n, *s; int lp_l, lp_nl; list_for_each_entry_safe (n, s, l, list) q_release_element(n); raise(SIGINT); free(l); lp_l=list_empty(l); if (lp_l == 0){ puts("l not empty in q_free"); } lp_nl=list_empty(&n->list); raise(SIGINT); if (lp_nl == 0) puts("n not empty in q_free"); } ``` ```shell! (base) urbaner@urbaner:~/linux2022/lab0-c$ make SANITIZER=1 CC queue.o CC random.o CC dudect/constant.o CC dudect/fixture.o CC dudect/ttest.o CC linenoise.o LD qtest (base) urbaner@urbaner:~/linux2022/lab0-c$ ./qtest cmd> new check if sturct initial and malloc are null malloc is not null not empty!! malloc is not null list is empty l = [] cmd> (base) urbaner@urbaner:~/linux2022/lab0-c$ scripts/debug.py -d Reading symbols from /home/urbaner/linux2022/lab0-c/qtest... cmd> free Program received signal SIGINT, Interrupt. __pthread_kill_implementation (no_tid=0, signo=2, threadid=<optimized out>) at ./nptl/pthread_kill.c:44 ``` malloc 函式初始化指標，其值為非 NULL ，這樣我們知道不需要測試，足以繼續開發。 list_empty 在 new 指令 q_new 函數前後能分別指令效果。所以應該把有關測試的檔案，其中 if(q!=NULL) 片段修改為 if(list_empty(q)) 才有意義。~~這告訴我們要習慣用 else if 來作測試，尤其是必須確認 if 條件式當中的變數值時。於是將 q_new, q_free, q_insert_head, q_insert_tail, q_remove_head, q_remove_tail 都進行 if 條件式的修正。~~ CONTRIBUTING.md 檔案有說明，有~~比較好~~標準的 if 敘述參考。至此完成初步操作，通過 `make check` 的要求。~~接下來的部份，會在發布前先暫時貼在這裡，通過測試後，再整理筆記。~~ :::warning 無法理解你的意思。當 malloc 回傳值不為 NULL 時，表示空間配置成功。然而，配置的記憶體空間是未初始化的，可能包含先前該記憶體位置上的舊資料。因此，在使用前應先進行初始化。 > [name=yanjiew1] ::: ### q_delete_mid ```cpp! bool q_delete_mid(struct list_head *head) { // https://leetcode.com/problems/delete-the-middle-node-of-a-linked-list/ if (!head || list_empty(head)) { return false; } struct list_head *h = head->next; struct list_head *t = head->prev; while (true) { if (h == t || h->next == t) { list_del(h); q_release_element(list_entry(h, element_t, list)); break; } else { puts("del tail case."); break; } h = h->next; t = t->prev; } return true; } ``` 按照 [leetcode](https://leetcode.com/problems/delete-the-middle-node-of-a-linked-list/) 的提示，刪去前方的節點。 **失敗案例**，沒定好結束條件，有最優化的程式提示錯誤： ```shell! cmd> it tig l = [meer dolp bea ger bea ger tig] cmd> rt tig Removed tig from queue l = [meer dolp bea ger bea ger] cmd> dm del tail case. l = [meer dolp bea ger bea ... ] ERROR: Queue has more than 5 elements cmd> show Current queue ID: 0 l = [meer dolp bea ger bea ... ] ERROR: Queue has more than 5 elements ``` :::warning `h` 和 `t` 二個指標相遇時，應該要刪除 `t` 才對。 > [name=yanjiew1] ::: :::info 已標注失敗案例，考慮今後省略，對開發無幫助，也無法交流，僅為我個人的疑慮。下方補上程式碼。 ::: 補完程式碼： ```cpp! if (h->next == t) { list_del(t); q_release_element(list_entry(t, element_t, list)); break; } h = h->next; t = t->prev; ``` ### q_delete_dup 需要比對字串，因為 element_t 型別預設 value 為 char 型別，先指定strcmp做函數，找到三種作法，參考 [for](https://hackmd.io/@freshLiver/2022q1-hw1#%E9%87%9D%E5%B0%8D%E4%BD%87%E5%88%97%E7%9A%84%E6%93%8D%E4%BD%9C), [while](https://hackmd.io/@jim12312321/linux2022-lab0#q_delete_dup), [cut_position](https://hackmd.io/@yanjiew/linux2023q1-lab0#q_delete_dup), 可以學到不同的函式用法，能較快熟練 linked list 的細節。 :::info 縮減筆記篇幅，將疑惑與困難記錄收錄到另一份筆記。 [link: dedup](https://hackmd.io/@Urbaner/page1#delete_dup) ::: ```graphviz digraph structs { rankdir=LR; node[shape=circle]; struct0 [label= "head"]; struct1 [label= "1"]; struct2 [label= "1"]; struct3 [label= "1"]; struct4 [label= "2"]; struct5 [label= "3"]; struct6 [shape=plaintext label="cut"]; struct7 [shape=plaintext label="it"]; struct8 [shape=plaintext label="safe"] struct0 -> struct1 -> struct2 -> struct3 -> struct4 -> struct5; struct7 struct6 struct8 {rank = same; struct0; struct6}; {rank = same; struct1; struct7}; {rank = same; struct2; struct8}; } ``` ```graphviz digraph structs { rankdir=LR; node[shape=circle]; struct0 [label= "head"]; struct1 [label= "1"]; struct2 [label= "1"]; struct3 [label= "1"]; struct4 [label= "2"]; struct5 [label= "3"]; struct6 [shape=plaintext label="cut"]; struct7 [shape=plaintext label="it"]; struct8 [shape=plaintext label="safe"] struct0 -> struct1 -> struct2 -> struct3 -> struct4 -> struct5; struct7 struct6 struct8 {rank = same; struct0; struct6}; {rank = same; struct2; struct7}; {rank = same; struct3; struct8}; } ``` ```graphviz digraph structs { rankdir=LR; node[shape=circle]; struct0 [label= "head"]; struct1 [label= "1"]; struct2 [label= "1"]; struct3 [label= "1"]; struct4 [label= "2"]; struct5 [label= "3"]; struct6 [shape=plaintext label="cut"]; struct7 [shape=plaintext label="it"]; struct8 [shape=plaintext label="safe"] struct0 -> struct1 -> struct2 -> struct3 -> struct4 -> struct5; struct7 struct6 struct8 {rank = same; struct0; struct6}; {rank = same; struct3; struct7}; {rank = same; struct4; struct8}; } ``` 如圖示，保持 cut 位置，移到比對相異時，safe 的節點，分開兩個 list。按照 list_cut_position 的定義，傳入參數。 [code_page](https://github.com/Urbaner3/lab0-c/blob/b65f692d80f5dabeb08e796044e87e370231dcbf/queue.c#L139) ### swap and sort merge_sort [node ed.](https://hackmd.io/@sysprog/c-linked-list#Merge-Sort-%E7%9A%84%E5%AF%A6%E4%BD%9C), [list ed.](https://npes87184.github.io/2015-09-12-linkedListSort/), [recursive](https://hackmd.io/@sysprog/linux2023-quiz1#%E6%B8%AC%E9%A9%97-1) [my work of merge sort](https://github.com/Urbaner3/lab0-c/blob/182237afbb53f941ede406a2ff93671f81284b30/queue.c#L227) 其中含有 [merge_two](https://github.com/Urbaner3/lab0-c/blob/182237afbb53f941ede406a2ff93671f81284b30/queue.c#L273) 自訂函式 [work of swap](https://github.com/Urbaner3/lab0-c/blob/182237afbb53f941ede406a2ff93671f81284b30/queue.c#L180) ```cpp! void q_sort(struct list_head *head) { /* Remove every node which has a node with a strictly greater value anywhere * to the right side of it */ /*https://npes87184.github.io/2015-09-12-linkedListSort/ */ if (!head || !head->next) return head; struct list_head *fast = head->next; struct list_head *slow = head; while (fast && fast->next) { slow = slow->next; fast = fast->next->next; } /*reset fast node, cut the list*/ fast = slow->next; slow->next = NULL; q_sort(head); q_sort(fast); two_merge(head, fast); ``` trace 04, 05 ### reverse (and merge) 依序將節點從頭走訪，再將開頭視為另一表單入口，很像瓶口向瓶底送，先進後出，FILO。 ### merge 實作時使用 list 儲存排序後結果。把 [iterative merge](https://npes87184.github.io/2015-09-12-linkedListSort/) 排序後接上，結合 [yanjiew](https://hackmd.io/@yanjiew/linux2023q1-lab0#q_merge_two), [alan](https://github.com/alanjian85/lab0-c/blob/master/queue.c#L183) 的作法，寫出表單版本的合併。最後考慮若迴圈結束時， l1 或 l2 為空，將剩餘表單依序接在新做表單，再去做切割。 trace 03, 05 ```cpp! static void merge_two(struct list_head *l1, struct list_head *l2){ if (!l1 || !l2) return 0; element_t *nod1, *nod2; LIST_HEAD(newhd); nod1 = list_first_entry(l1,element_t,list); nod2 = list_first_entry(l2,element_t,list); while (l1 && l2){ if (strcmp(nod1->value, nod2->value) < 0) /*add l1 node to tail of newhd list */ list_move_tail(l1, &newhd); else list_move_tail(l2, &newhd); } list_splice(&newhd, l1); list_splice( } ``` ```cpp! struct list_head *temp = LIST_HEAD(nh); struct list_head *q = temp; element_t *ll1, *ll2; while (l1 && l2) { ll1 = list_entry(l1, element_t, list); ll2 = list_entry(l2, element_t, list); if (*ll1->value < *ll2->value) { temp->next = l1; temp = temp->next; l1 = l1->next; } else { temp->next = l2; temp = temp->next; l2 = l2->next; } } if (l1) temp->next = l1; if (l2) temp->next = l2; struct list_head *head = q->next; list_del(q); free(q); return head; ``` 釐清 queue_context 這個結構之後，可以理解 [alan](https://github.com/alanjian85/lab0-c/blob/f34b3b61b64347cc98abdbfe8b3df8dc62a97bed/queue.c#L267) 的程式碼，把 qc 命名之後，改正 size 的名字為 cnt_len，避免與 q_size 搞混。先記錄第一列的資料，再引入迴圈，讀取第二列數列資料，合併和刪除空數列，即完成。 [work of code](https://github.com/Urbaner3/lab0-c/blob/f1a0c592b5f5cae50c71e45c39e75835a863fd9a/queue.c#L299) ### dedup reverseK, descend trace 06 根據 [yanjiew](https://hackmd.io/@yanjiew/linux2023q1-lab0#q_descend) descend 為所有點右邊不可有更大的值或字串，從右邊開始，刪去小於尾端的值或字串，整理到開頭。 ascend 則相反。 [work of code](https://github.com/Urbaner3/lab0-c/blob/6b118495d9bbe9df2426e4c973c5d1f34cd4f6ef/queue.c#L256) ## Valgrind 與自動程式設計 ## Web server ```shell! ./qtest cmd> web listen on port 9999, fd is 3 cmd> Unknown command '.' cmd> Unknown command 'favicon.ico' cmd> l = [] cmd> Unknown command 'favicon.ico' cmd> l = [1] cmd> Unknown command 'favicon.ico' cmd> l = [2 1] cmd> Unknown command 'favicon.ico' Error limit exceeded. Stopping command execution ``` [epoll_program](https://hackmd.io/@qwe661234/S1tuJOC6s#Explain-how-select-system-call-work-in-this-program-and-examine-the-consolec-implementation) ## 亂數＆ Dudect 論文 [chi_square_test](https://soc.utah.edu/sociology3112/chi-square.php) [t-test](https://highscope.ch.ntu.edu.tw/wordpress/?p=73780) [excel](https://highscope.ch.ntu.edu.tw/wordpress/?p=73782) 檢查，[yanjiew](https://hackmd.io/@yanjiew/linux2023q1-lab0#%E7%A0%94%E8%AE%80%E8%AB%96%E6%96%87%E3%80%88Dude-is-my-code-constant-time%E3%80%89) /lab-0/dudect/ttest.c , only `push`, `compute` and `init` 3 functions. /ob.../dudect/src/dudect.h, 4 `struct`s ; public,`init`,`main`,`free`, `randombits`, `randombytes` `cmp`, `percentile`, `cpucycles()`, `measure`, `report_test`, `test` `percentile` in `dedect_ctx_t`

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.