2022q1 Homework1 (lab0)

# 2022q1 Homework1 (lab0) contributed by < `ibat10clw` > > [lab0-c](https://github.com/ibat10clw/lab0-c) ###### tags: `linux2022` ## 實驗環境 ```shell $ gcc (Ubuntu 9.3.0-17ubuntu1~20.04) 9.3.0 Copyright (C) 2019 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. $ lscpu Architecture: x86_64 CPU op-mode(s): 32-bit, 64-bit Byte Order: Little Endian Address sizes: 39 bits physical, 48 bits virtual CPU(s): 8 On-line CPU(s) list: 0-7 Thread(s) per core: 2 Core(s) per socket: 4 Socket(s): 1 NUMA node(s): 1 Vendor ID: GenuineIntel CPU family: 6 Model: 60 Model name: Intel(R) Core(TM) i7-4790 CPU @ 3.60GHz Stepping: 3 CPU MHz: 1200.000 CPU max MHz: 4000.0000 CPU min MHz: 800.0000 BogoMIPS: 7183.16 Virtualization: VT-x L1d cache: 128 KiB L1i cache: 128 KiB L2 cache: 1 MiB L3 cache: 8 MiB NUMA node0 CPU(s): 0-7 Vulnerability Itlb multihit: KVM: Mitigation: VMX disabled Vulnerability L1tf: Mitigation; PTE Inversion; VMX conditional cach e flushes, SMT vulnerable Vulnerability Mds: Mitigation; Clear CPU buffers; SMT vulnerable Vulnerability Meltdown: Mitigation; PTI Vulnerability Spec store bypass: Mitigation; Speculative Store Bypass disabled v ia prctl and seccomp Vulnerability Spectre v1: Mitigation; usercopy/swapgs barriers and __user pointer sanitization Vulnerability Spectre v2: Mitigation; Full generic retpoline, IBPB condit ional, IBRS_FW, STIBP conditional, RSB filling Vulnerability Srbds: Mitigation; Microcode Vulnerability Tsx async abort: Not affected Flags: fpu vme de pse tsc msr pae mce cx8 apic sep mtr r pge mca cmov pat pse36 clflush dts acpi mmx f xsr sse sse2 ss ht tm pbe syscall nx pdpe1gb rd tscp lm constant_tsc arch_perfmon pebs bts rep_ good nopl xtopology nonstop_tsc cpuid aperfmper f pni pclmulqdq dtes64 monitor ds_cpl vmx smx e st tm2 ssse3 sdbg fma cx16 xtpr pdcm pcid sse4_ 1 sse4_2 x2apic movbe popcnt tsc_deadline_timer aes xsave avx f16c rdrand lahf_lm abm cpuid_fa ult epb invpcid_single pti ssbd ibrs ibpb stibp tpr_shadow vnmi flexpriority ept vpid ept_ad f sgsbase tsc_adjust bmi1 avx2 smep bmi2 erms inv pcid xsaveopt dtherm ida arat pln pts md_clear flush_l1d ``` ## 作業要求 > [lab0](https://hackmd.io/@sysprog/linux2022-lab0) * 在 GitHub 上 fork [lab0-c](https://github.com/sysprog21/lab0-c) * 依據上述指示著手修改 `queue.[ch]` 和連帶的檔案，測試後用 Git 管理各項修改，要能滿足 `$ make test` 自動評分系統的所有項目。 * q_new: 建立一個新的 queue 並將 head 的指標初始化 * q_free: 釋放目前 queue 中的所有元素 * q_insert_head: 在 head 插入一個新元素 * q_insert_tail: 在 tail 插入一個新元素 * q_remove_head: 移除 head 端的元素 * q_remove_tail: 移除 tail 端的元素 * q_size: 計算 queue 的長度 * q_delete_mid: 刪除 queue 中間的元素(⌊q_size / 2⌋) * q_delete_dup: 刪除 queue 所有重複的元素 * q_swap: 將 queue 中相鄰的元素交換位置 * q_reverse: 將 queue 的順序反轉 * q_sort: 將 queue 中的元素以字典序做排序 ## 開發紀錄 ### q_new 最一開始沒有去判斷當 malloc 失敗的時候要有例外處理, 到了執行評分程式時才注意到, 後面如果有需要做 malloc 的部份也都需要檢查回傳的結果是否成功 INIT_LIST_HEAD 的作用是將 head->prev 和 head->next 指向自己 ```c= struct list_head *q_new() { // allocate a space of list_head struct list_head *q = (struct list_head *) malloc(sizeof(struct list_head)); if (!q) return NULL; INIT_LIST_HEAD(q); return q; } ``` ### q_free 根據[你所不知道的 C 語言: 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)中提到在 linux 中的 list 會把 list_head 嵌入到所需的結構體中, 但傳入的參數是 list_head, 因此需要透過 list_head 去找到 element_t 才能夠真正的去釋放記憶體此外 element_t 中的 value 是一個指標, 也需要將其指向的記憶體空間收回 ```c void q_free(struct list_head *l) { if (!l) return; element_t *previous, *current; list_for_each_entry_safe (current, previous, l, list) { free(current->value); free(current); } free(l); } ``` ### q_insert_head 在插入的部份有兩個地方需要用到 malloc, 分別是 node 本身和 node 要存的value 由於 value 的部份是字串, 需要計算它的長度後再進行分配, 要是失敗的話則要先把前面 malloc 的node 釋放掉才能 return, 當 data 都準備好後只要將其接在 head 的next就好 ```c bool q_insert_head(struct list_head *head, char *s) { if (!head) return false; element_t *node = (element_t *) malloc(sizeof(element_t)); if (!node) return false; unsigned int len = strlen(s) + 1; node->value = malloc(sizeof(char) * len); if (!node->value) { free(node); return false; } memcpy(node->value, s, len); list_add(&node->list, head); return true; } ``` ### q_insert_tail 由於是 circular doubly linked list, 因此能夠參考 insert head 的部份, 只有最後要改為將 data 接在 head 的 prev 就可以了 ```c bool q_insert_tail(struct list_head *head, char *s) { if (!head) return false; element_t *node = (element_t *) malloc(sizeof(element_t)); if (!node) return false; unsigned int len = strlen(s) + 1; node->value = malloc(sizeof(char) * len); if (!node->value) { free(node); return false; } memcpy(node->value, s, len); list_add_tail(&node->list, head); return true; } ``` ### q_remove_head 根據作業要求除了要將 node 移出 list 以外, 當傳入的 sp 不是空指標時要將 data 複製進去 ```c element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize) { if (!head || head->next == head) return NULL; element_t *node = list_first_entry(head, element_t, list); if (sp) { strncpy(sp, node->value, bufsize - 1); sp[bufsize - 1] = '\0'; } list_del(head->next); return node; } ``` ### q_remove_tail 跟 remove_head 做比較, 差別只有移除的 node 從 head->next 改為 head->prev ```c element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize) { if (!head || head->next == head) return NULL; element_t *node = list_last_entry(head, element_t, list); if (sp) { strncpy(sp, node->value, bufsize - 1); sp[bufsize - 1] = '\0'; } list_del(head->prev); return node; } ``` ### q_size 透過走訪整個 list 後來計算 list 的長度 ```c int q_size(struct list_head *head) { if (!head || head == head->next) return 0; int len = 0; struct list_head *li; list_for_each (li, head) len++; return len; } ``` ### q_delete_mid 這邊的關鍵在於如何找出位於中間的 node 我使用了 slow 和 fast 的指標來走訪 list, 兩個指標的移動速度剛好差一倍, 所以當 fast 繞了一圈後 slow恰好會在 list 中間, 找到之後將其刪除(除了移出 list 外, 記憶體也要收回) ```c bool q_delete_mid(struct list_head *head) { if (!head || head->next == head) return false; struct list_head *fast = head; struct list_head *slow = head; do { fast = fast->next->next; slow = slow->next; } while (fast->next != head && fast != head); element_t *target = list_entry(slow, element_t, list); list_del(slow); free(target->value); free(target); return true; } ``` ### q_delete_dup 由於只會作用在 sorted list , 我用了一個 current 的指標, 並且會在每個 node 都向後看, 只要發現重複就將開始刪除, 直到 current->next 和 current 不相等後再把 current 刪除, 並且往更新過後的 list 的下一個 node 前進 ```c bool q_delete_dup(struct list_head *head) { if (!head || head->next == head) return false; struct list_head *current = head->next; char tag; while (current != head) { element_t *node = list_entry(current, element_t, list); while (current->next != head && !strcmp(node->value, list_entry(current->next, element_t, list)->value)) { tag = 1; element_t *del_node = list_entry(current->next, element_t, list); list_del(current->next); free(del_node->value); free(del_node); } if (tag) { tag = 0; element_t *del_node = list_entry(current, element_t, list); struct list_head *tmp = current->next; list_del(current); free(del_node->value); free(del_node); current = tmp; } else current = current->next; } return true; } ``` ### q_swap 這裡採用比較直覺的作法, 交換兩個 node 共會影響 6 個 link 把他們全部轉向即可由於 while 的判斷, 當 current 走回 head 的時候就會停止, 不過若 q_size 為偶數, 則最後一個 node 也會被調整, 最後的 if 是為了在此情形中調整 head 的 link ```c void q_swap(struct list_head *head) { struct list_head *current = head->next, *previous = head, *tmp = NULL; while (current != head && current->next != head) { tmp = previous; previous = current; current = current->next; previous->next = current->next; current->next = previous; current->prev = previous->prev; previous->prev = current; tmp->next = current; previous->next->prev = previous; current = previous->next; } if (current->next != head) { previous->next = head; head->prev = previous; } } ``` ### q_reverse 由於 head 是不帶 data 的, 因此要反轉 list 只需要將所有 node 的 next 和 prev 做交換即可指標 tmp 用於輔助交換, 當交換完成後原先的 next 的方向會變成存在 prev 內, 因此透過 prev 來移動 current ```c void q_reverse(struct list_head *head) { if (!head || head == head->next || list_is_singular(head)) return; struct list_head *tmp; struct list_head *current = head->next; while (current != head) { tmp = current->prev; current->prev = current->next; current->next = tmp; current = current->prev; } tmp = head->prev; head->prev = head->next; head->next = tmp; } ``` ### q_sort 這邊採用了遞迴的 merge sort來實作, 並且在排序的過程中先忽視 prev 的存在, 同時將 circular 的結構破壞, 等待排序完畢後再透過 next 的順序去恢復成 doubly circular linked list merge sort 共有兩大重點, 分別是: 1. 分割在分割的部份我採用了 slow 和 fast 的指標來找尋 list 的中間節點, 找到後將中間節點的 next 指向 NULL, 直到所有 sub list 的 size 都小於等於 1 為止 1. 合併合併的部份採用的方式是老師[你所不知道的 C 語言: linked list 和非連續記憶體](https://hackmd.io/@sysprog/c-linked-list#%E6%A1%88%E4%BE%8B%E6%8E%A2%E8%A8%8E-LeetCode-21-Merge-Two-Sorted-Lists)中介紹的 merge two sorted list 的方法當 sorting 完成後, 把 prev 的 link 連回去, 然後把 last node 與 head 的連結也恢復後就完成了 ```c struct list_head *merge(struct list_head *l1, struct list_head *l2) { struct list_head *head = NULL, **ptr = &head, **node; for (node = NULL; l1 && l2; *node = (*node)->next) { node = strcmp(list_entry(l1, element_t, list)->value, list_entry(l2, element_t, list)->value) < 0 ? &l1 : &l2; *ptr = *node; ptr = &(*ptr)->next; } *ptr = l1 ? l1 : l2; return head; } struct list_head *mergesort(struct list_head *head) { if (!head->next) { return head; } struct list_head *fast = head; struct list_head *slow = head; while (fast->next && fast->next->next) { fast = fast->next->next; slow = slow->next; } struct list_head *mid = slow->next; slow->next = NULL; struct list_head *left = mergesort(head); struct list_head *right = mergesort(mid); return merge(left, right); } void q_sort(struct list_head *head) { if (!head || head->next == head || list_is_singular(head)) return; struct list_head *tmp = head->next; head->prev->next = NULL; head->next = NULL; struct list_head *sorted = mergesort(tmp); struct list_head *current = sorted; struct list_head *previous = 0; while (current) { previous = current; current = current->next; if (current) current->prev = previous; } sorted->prev = head; head->next = sorted; head->prev = previous; previous->next = head; } ``` ### 在 qtest 提供新的命令 shuffle 目前已經在 queue.c 中完成了 shuffle 的程式碼先建立一個 newh 來輔助洗牌每個回合會從原 list 中隨機選一個 node 移除, 並且 insert 在 newh 的 head 當所有元素都以新的順序被串在 newh 後, 之後再將 newh, first node, last node 的 link 串回原先的 head 便完成了洗牌的操作 ```c static bool q_shuffle(struct list_head *head) { if(!head || list_empty(head)) return false; else if(list_is_singular(head)) return true; int len = 0; struct list_head *li; struct list_head newh; newh.next = &newh; newh.prev = &newh; list_for_each (li, head) len++; srand(time(NULL)); while (len) { int node_num = (rand() % len) + 1; li = head; do { li = li->next; } while (--node_num); struct list_head *tmp = li; list_del(li); list_add(tmp, &newh); len--; } newh.next->prev = head; newh.prev->next = head; head->next = newh.next; head->prev = newh.prev; return true; } ``` 接下來要將功能與 qtest 做結合在閱讀了作業要求中, 如何新增 do_hello 的方法後, 已經有成功新增 hello 命令同時在 qtest.c 中找到了 do_show 的實作, 打算模仿此方法將 shuffle 的命令加入 qtest 中最後我仿照了 do_dm 將 shuffle 的功能加入了 qtest ```c static bool do_shuffle(int argc, char *argv[]) { if (argc != 1) { report(1, "%s takes no arguments", argv[0]); return false; } if (!l_meta.l) report(3, "Warning: Try to access null queue"); error_check(); bool ok = true; if (exception_setup(true)) ok = q_shuffle(l_meta.l); exception_cancel(); show_queue(3); return ok && !error_check(); } ``` ## TODO ### trace-17-complexity 我的程式碼在 github 的 CI 有時後會失敗, 但在自己的電腦上測試從 insert, remove, free 這三個部份做完後就一直是通過的狀態, 需要進一步釐清原因 ### 部份程式碼改進與觀摩區的作業比較後認為我的程式碼應該需要多使用 list.h 提供的 API 去改寫, 但有些 macro 還不是很理解, 等待理解後在將他們改進 ## 參考資料 * [Reverse a doubly circular linked list](https://www.geeksforgeeks.org/reverse-a-doubly-circular-linked-list/) *

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.