2023q1 Homework1 (lab0)

--- tags: linux2023 --- # 2023q1 Homework1 (lab0) contributed by < `as200188` > ## 開發環境作業系統: ubuntu 22.04 硬體配置 ```shell $ 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): 8 On-line CPU(s) list: 0-7 Vendor ID: GenuineIntel Model name: Intel(R) Core(TM) i7-7700 CPU @ 3.60GHz CPU family: 6 Model: 158 Thread(s) per core: 2 Core(s) per socket: 4 Socket(s): 1 Stepping: 9 CPU max MHz: 4200.0000 CPU min MHz: 800.0000 BogoMIPS: 7200.00 Flags: fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mc a cmov pat pse36 clflush dts acpi mmx fxsr sse sse2 ss ht tm pbe syscall nx pdpe1gb rdtscp lm constant_tsc art arch_perfmon pebs bts rep_good nopl xtopology nonstop_ tsc cpuid aperfmperf pni pclmulqdq dtes64 monitor ds_cp l vmx smx est tm2 ssse3 sdbg fma cx16 xtpr pdcm pcid ss e4_1 sse4_2 x2apic movbe popcnt tsc_deadline_timer aes xsave avx f16c rdrand lahf_lm abm 3dnowprefetch cpuid_f ault epb invpcid_single pti ssbd ibrs ibpb stibp tpr_sh adow vnmi flexpriority ept vpid ept_ad fsgsbase tsc_adj ust bmi1 avx2 smep bmi2 erms invpcid mpx rdseed adx sma p clflushopt intel_pt xsaveopt xsavec xgetbv1 xsaves dt herm ida arat pln pts hwp hwp_notify hwp_act_window hwp _epp md_clear flush_l1d arch_capabilities Virtualization features: Virtualization: VT-x Caches (sum of all): L1d: 128 KiB (4 instances) L1i: 128 KiB (4 instances) L2: 1 MiB (4 instances) L3: 8 MiB (1 instance) NUMA: NUMA node(s): 1 NUMA node0 CPU(s): 0-7 Vulnerabilities: Itlb multihit: KVM: Mitigation: VMX disabled L1tf: Mitigation; PTE Inversion; VMX conditional cache flushe s, SMT vulnerable Mds: Mitigation; Clear CPU buffers; SMT vulnerable Meltdown: Mitigation; PTI Mmio stale data: Mitigation; Clear CPU buffers; SMT vulnerable Retbleed: Mitigation; IBRS Spec store bypass: Mitigation; Speculative Store Bypass disabled via prctl Spectre v1: Mitigation; usercopy/swapgs barriers and __user pointer sanitization Spectre v2: Mitigation; IBRS, IBPB conditional, RSB filling, PBRSB- eIBRS Not affected Srbds: Mitigation; Microcode Tsx async abort: Mitigation; TSX disabled ``` ## 開發過程 ### 設定開發環境 #### 安裝及設定 git 參考 [Git 教學和 GitHub 設定指引](https://hackmd.io/@sysprog/gnu-linux-dev/https%3A%2F%2Fhackmd.io%2F%40sysprog%2Fgit-with-github) #### 複製 lab0-c 專案 1. Fork [lab0-c](https://github.com/sysprog21/lab0-c) 參考[官方文檔 Fork 的方式](https://docs.github.com/en/get-started/quickstart/fork-a-repo) 2. 將專案複製到本地端 ```shell $ git clone https://github.com/as200188/lab0-c.git ``` 3. 設定成SSH連線參考 [git push without password](https://stackoverflow.com/questions/6565357/git-push-requires-username-and-password) ```shell $ git remote set-url origin git@github.com:as200188/lab0-c.git ``` 4. 確認輸出 ```shell $ git remote -v origin git@github.com:as200188/lab0-c.git (fetch) origin git@github.com:as200188/lab0-c.git (push) ``` #### 安裝 make 套件 1. 安裝 ```shell $ sudo apt-get install make ``` 2. 確認安裝版本 ```shell $ make -version GNU Make 4.3 Built for x86_64-pc-linux-gnu Copyright (C) 1988-2020 Free Software Foundation, Inc. License GPLv3+: GNU GPL version 3 or later <http://gnu.org/licenses/gpl.html> This is free software: you are free to change and redistribute it. There is NO WARRANTY, to the extent permitted by law. ``` #### 安裝 curl 套件 1. 安裝 ```shell $ sudo apt-get install curl ``` 2. 測試 ```shell $ curl -I https://www.gnu.org/ HTTP/1.1 200 OK Date: Tue, 21 Feb 2023 09:29:21 GMT Server: Apache/2.4.29 Content-Location: home.html Vary: negotiate,accept-language,Accept-Encoding TCN: choice Strict-Transport-Security: max-age=63072000 X-Frame-Options: sameorigin X-Content-Type-Options: nosniff Access-Control-Allow-Origin: (null) Accept-Ranges: bytes Cache-Control: max-age=0 Expires: Tue, 21 Feb 2023 09:29:21 GMT Content-Type: text/html Content-Language: en ``` #### 安裝 gcc 套件 1. 安裝 ```shell $ sudo apt-get install gcc ``` 2. 確認版本 ```shell $ gcc --version gcc (Ubuntu 11.3.0-1ubuntu1~22.04) 11.3.0 Copyright (C) 2021 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. ``` ### 測試 lab0-c 專案 #### 編譯 ```shell ~/linux2023/lab0-c$ make CC qtest.o CC report.o CC console.o CC harness.o CC queue.o CC random.o CC dudect/constant.o CC dudect/fixture.o CC dudect/ttest.o CC shannon_entropy.o CC linenoise.o CC web.o LD qtest ``` #### 清除編譯產生的檔案 ```shell ~/linux2023/lab0-c$ make clean rm -f qtest.o report.o console.o harness.o queue.o random.o dudect/constant.o dudect/fixture.o dudect/ttest.o shannon_entropy.o linenoise.o web.o .qtest.o.d .report.o.d .console.o.d .harness.o.d .queue.o.d .random.o.d .dudect/constant.o.d .dudect/fixture.o.d .dudect/ttest.o.d .shannon_entropy.o.d .linenoise.o.d .web.o.d *~ qtest /tmp/qtest.* rm -rf .dudect rm -rf *.dSYM (cd traces; rm -f *~) ``` ### 實做 queue 相關函式 #### 實做所使用的資料結構參考 [linked list](https://hackmd.io/@sysprog/c-linked-list) 利用 [list.h](https://github.com/sysprog21/lab0-c/blob/master/list.h) 建立雙向 linked list #### Linked list element 想法: 節點嵌入結構體 list_head，若要取得節點，則利用 container_of 來取得節點。 ```c typedef struct { char *value; struct list_head list; } element_t; ``` #### Queue 結構 ```c typedef struct { int size; struct list_head head; } queue_t; ``` #### 建立 element 並初始化想法: 用 malloc() 取得節點空間，並且初始化，回傳該節點位址。 ```c /* Initial element */ static inline void INIT_ELEMENT(element_t *e) { e->value = NULL; INIT_LIST_HEAD(&e->list); } /* Create element and initial it */ struct element_t *element_new() { element_t *e = malloc(sizeof(element_t)); INIT_ELEMENT(e); return e; } ``` 未考慮到 malloc() 可能會回傳 NULL，因此將程式碼修正成: ```c static inline void INIT_ELEMENT(element_t *e) { if (e == NULL) return; e->value = NULL; INIT_LIST_HEAD(&e->list); } ``` #### q_new 想法: 建 empty queue，並且做初始化。 ```c struct list_head *q_new() { /* Create queue and initial it */ queue_t *q = malloc(sizeof(queue_t)); q->size = 0; INIT_LIST_HEAD(&q->head); return &q->head; } ``` 未考慮到 malloc() 可能會回傳 NULL，因此將程式碼修正成: ```c /* Initial queue */ static inline void INIT_QUEUE(queue_t *q) { if (q == NULL) return; q->size = 0; INIT_LIST_HEAD(&q->head); } /* Create an empty queue and initial it */ struct list_head *q_new() { /* Create queue and initial it */ queue_t *q = malloc(sizeof(queue_t)); INIT_QUEUE(q); return (q != NULL) ? &q->head : NULL; } ``` #### q_insert_head 想法: 建立新節點，利用 list_add 加到第一個節點。考慮到傳入空指標和極長字串會導致程式出錯，利用計算字串長度再加一(放空字元)，作為放字串的空間，從靜態改成動態，避免極長字串導致程式出錯，將程式碼修改成: ```c bool q_insert_head(struct list_head *head, char *s) { if (head == NULL || s == NULL) return false; char *str = malloc(strlen(s)+1); element_t *e = element_new(); queue_t *q = container_of(head, queue_t, head); strcpy(str, s); e->s = str; list_add(&e->list, head); q->size += 1; return true; } ``` 發現字串動態配置空間和複製字串可由 strdup 一次做完(參考 [willwillhi](https://hackmd.io/@willwillhi/lab0-2023))，可將程式碼經簡化，將程式碼改成: ```c bool q_insert_head(struct list_head *head, char *s) { if (head == NULL || s == NULL) return false; char *str = strdup(s); element_t *e = element_new(); queue_t *q = container_of(head, queue_t, head); e->value = str; list_add(&e->list, head); q->size += 1; return true; } ``` 未考慮到 malloc 失敗後，未將已配置空間釋放，導致 memory leak。修正成: ```c bool q_insert_head(struct list_head *head, char *s) { if (head == NULL || s == NULL) return false; char *str = strdup(s); if (str == NULL) goto malloc_failed; element_t *e = element_new(); if (e == NULL) goto malloc_failed; queue_t *q = container_of(head, queue_t, head); e->value = str; list_add(&e->list, head); q->size += 1; return true; malloc_failed: if (str) free(str); if (e) free(e); return false; } ``` #### q_insert_tail ```c bool q_insert_tail(struct list_head *head, char *s) { if (head == NULL || s == NULL) return false; char *str = strdup(s); if (str == NULL) goto malloc_failed; element_t *e = element_new(); if (e == NULL) goto malloc_failed; queue_t *q = container_of(head, queue_t, head); e->value = str; list_add_tail(&e->list, head); q->size += 1; return true; malloc_failed: if (str) free(str); if (e) free(e); return false; } ``` #### q_size 想法: 有一種做法是計算節點數量，然後回傳答案，但該方式的時間複雜度為 $O(N)$，我希望讓時間複雜度為 $O(1)$，所以我會有一個 queue 結構，裡面會有 size 和 head 成員，並且利用 container_of 來取得該 queue 結構。 ```c int q_size(struct list_head *head) { if (head == NULL) return -1; queue_t *q = container_of(head, queue_t, head); return q->size; } ``` #### q_remove_head 想法: 若能移去節點，需要將字串複製到 sp, 並將 q->size 減一。 ```c element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize) { if (head == NULL || sp == NULL || q_size() == 0) return NULL; element_t *e = list_first_entry(head, element_t, list); queue_t *q = container_of(head, queue_t, head); strncpy(sp, e->value, bufsize-1); sp[bufsize-1] = '\0'; list_del(&e->list); q->size -= 1; return e; } ``` #### q_remove_head ```c element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize) { if (head == NULL || sp == NULL || q_size() == 0) return NULL; element_t *e = list_last_entry(head, element_t, list); queue_t *q = container_of(head, queue_t, head); strncpy(sp, e->value, bufsize-1); sp[bufsize-1] = '\0'; list_del(&e->list); q->size -= 1; return e; } ``` #### q_free 想法: 利用 list_for_each_safe 逐一走訪 list 上的節點，利用 container_of 取得 element 並釋放該 element 所使用的空間，走訪完後，將 queue 所使用的空間釋放。 ```c void q_free(struct list_head *head) { if (head == NULL) return; queue_t *q = container_of(head, queue_t, head); struct list_head *iter = NULL, *next = NULL; element_t *e = NULL; list_for_each_safe(iter, next, head){ e = container_of(iter, element_t, list); free(e->value); e->value = NULL; list_del_init(iter); free(e); } free(q); } ``` 由於刪除 element 這段程式經常重複，所以將該段程式寫成 function，修改成: ```c /* Delete element and update list and queue */ static void element_del(element_t *e, struct list_head *head) { if (e == NULL || head == NULL) return; queue_t *q = container_of(head, queue_t, head); free(e->value); e->value = NULL; list_del_init(&e->list); free(e); q->size -= 1; } /* Free all storage used by queue */ void q_free(struct list_head *head) { if (head == NULL) return; queue_t *q = container_of(head, queue_t, head); struct list_head *iter = NULL, *next = NULL; element_t *e = NULL; list_for_each_safe (iter, next, head) { e = container_of(iter, element_t, list); element_del(e, head); } free(q); } ``` #### q_delete_mid 想法: 有想到三種做法，第一種是逐一走訪，計算節點數，再去刪中間。第二種是用快慢指標來去找中間。第三種做法是從頭尾逐一走訪來找中間，採用第三種做法，當節點數是奇數的時候，front 等於 end時，front 和 end 都是中間節點，節點數為偶數的時候，front->next 等於 end時，end 為中間節點，找到中間節點後，將其刪除。 ```c /* Delete the middle node in queue */ bool q_delete_mid(struct list_head *head) { // https://leetcode.com/problems/delete-the-middle-node-of-a-linked-list/ if (head == NULL || q_size(head) == 0) return false; struct list_head *front = head->next, *end = head->prev; element_t *e = NULL; while(front != end && front->next != end){ front = front->next; end = end->prev; } e = container_of(end, element_t, list); element_del(e, head); return true; } ``` #### q_reverse 想法: 有想到兩種做法，一種是不改變節點 list 指向的位址，藉由改變 value 來做到 reverse，好處是 element 只有 value 要改變時，需要交換的值很少，效率佳，可從頭尾指標做 swap，得到結果。此處使用第二種做法，改變 list 指向的位址，逐一走訪節點，將節點放到尾巴，得到結果。 ```c void q_reverse(struct list_head *head) { if (head == NULL || list_empty(head) || list_is_singular(head)) return; struct list_head *old_front = head->next, *old_end = head->prev; struct list_head *iter = NULL, *next = NULL, *tmp = NULL; list_for_each_safe (iter, next, head) { tmp = iter->prev; iter->prev = iter->next; iter->next = tmp; } head->next = old_end; head->prev = old_front; } ``` #### q_swap 想法: 兩個節點以上才需要 swap，在做 swap 時，要將前一個和下一個和下兩個的節點，指標關係需要做更新，而當 swap 時，是和最後一個節點交換，需要更新 head 的前一個節點。 ```c void q_swap(struct list_head *head) { // https://leetcode.com/problems/swap-nodes-in-pairs/ if (head == NULL || list_empty(head) || list_is_singular(head)) return; struct list_head *iter = NULL, *next = NULL, *next_next = NULL, *prev = NULL; for (iter = head->next, next_next = iter->next->next; iter != head && iter != head->prev; iter = next_next, next_next = iter->next->next) { prev = iter->prev; next = iter->next; iter->next = next_next; next_next->prev = iter; prev->next = next; next->prev = prev; next->next = iter; iter->prev = next; if (head->prev == next) head->prev = iter; } } ``` #### compare ```c int compare(const void *a, const void *b) { const struct list_head *a_list = a; const struct list_head *b_list = b; element_t *a_e = container_of(a_list, element_t, list); element_t *b_e = container_of(b_list, element_t, list); return strcmp(a_e->value, b_e->value); } ``` #### q_sort 想法: 有想到兩種有效率的排序方式，quick sort 和 merge sort，怕會有 worst case 造成 quick sort 時間複雜度為 $O(N^2)$，所以最後採用 merge sort 讓時間複雜度為 $O(N*log(N))$。 ```c void merge(struct list_head *head, struct list_head *left_head, struct list_head *right_head) { struct list_head *left_iter = left_head->next, *right_iter = right_head->next; struct list_head *left_next = left_iter->next, *right_next = right_iter->next; while (left_iter != left_head || right_iter != right_head) { if (left_iter == left_head) { list_move_tail(right_iter, head); right_iter = right_next; right_next = right_iter->next; continue; } if (right_iter == right_head) { list_move_tail(left_iter, head); left_iter = left_next; left_next = left_iter->next; continue; } if (compare(left_iter, right_iter) < 0) { list_move_tail(left_iter, head); left_iter = left_next; left_next = left_iter->next; } else { list_move_tail(right_iter, head); right_iter = right_next; right_next = right_iter->next; } } } void merge_sort(struct list_head *head) { if (head == NULL || list_empty(head) || list_is_singular(head)) return; LIST_HEAD(left_head); LIST_HEAD(right_head); struct list_head *front = head->next, *end = head->prev, *mid = NULL; struct list_head *iter = NULL, *next = NULL; while (front != end && front->next != end) { front = front->next; end = end->prev; } mid = end; for (iter = head->next, next = iter->next; iter != mid; iter = next, next = iter->next) { list_move_tail(iter, &left_head); } for (iter = mid, next = iter->next; iter != head; iter = next, next = iter->next) { list_move_tail(iter, &right_head); } merge_sort(&left_head); merge_sort(&right_head); merge(head, &left_head, &right_head); } /* Sort elements of queue in ascending order */ void q_sort(struct list_head *head) { if (head == NULL || list_empty(head) || list_is_singular(head)) return; merge_sort(head); } ``` #### q_reverseK 想法: 將 list 切成多個 group，每個 group 大小為 k，切好後利用 q_reverse() 來得到結果，最後將多個 group 拼接起來。 ```c /* Reverse the nodes of the list k at a time */ void q_reverseK(struct list_head *head, int k) { // https://leetcode.com/problems/reverse-nodes-in-k-group/ if (head == NULL || list_empty(head) || list_is_singular(head)) return; int num_of_groups = q_size(head) / k; int i = 0, j = 0; struct list_head *iter = head->next, *next = iter->next; LIST_HEAD(res_head); for (; i < num_of_groups; i++) { LIST_HEAD(tmp_head); for (j = 0; j < k; j++) { list_move_tail(iter, &tmp_head); iter = next; next = iter->next; } q_reverse(&tmp_head); list_splice_tail(&tmp_head, &res_head); } list_splice(&res_head, head); } ``` #### q_delete_dup 想法: first 指標指向第一個節點，second 指標指向第二個節點，若兩個節點的字串相同，則 second 往下一個節點走，直到兩個節點的字串不相同，便能得到 first 和 second 的前一個為相同字串的節點。若兩個節點的字串不相同，first 和 second 皆往下一個節點走。 ```c bool q_delete_dup(struct list_head *head) { // https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/ if (head == NULL || list_empty(head) || list_is_singular(head)) return false; struct list_head *first = head->next, *second = first->next, *second_next = second->next, *first_prev = NULL; element_t *e = NULL; while (first != head && second != head) { if (compare(first, second) == 0) { first_prev = first->prev; while (second != head && compare(first, second) == 0) { e = container_of(second, element_t, list); element_del(e, head); second = second_next; second_next = second->next; } e = container_of(first, element_t, list); element_del(e, head); first_prev->next = second; second->prev = first_prev; } first = second; second = second_next; second_next = second->next; } return true; } ``` #### q_descend 想法: 由後往前逐一走訪，紀錄當前最大值，只要比最大值小，將該節點移除即可。 ```c int q_descend(struct list_head *head) { // https://leetcode.com/problems/remove-nodes-from-linked-list/ if (head == NULL || list_empty(head) || list_is_singular(head)) return 0; struct list_head *iter = head->prev, *prev = iter->prev, *max = iter; element_t *e = NULL; while (iter != head) { if (compare(iter, max) > 0) max = iter; else if (compare(iter, max) < 0) { e = container_of(iter, element_t, list); element_del(e, head); } iter = prev; prev = iter->prev; } return q_size(head); } ```

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.