2022q1 Homework1 (lab0)

# 2022q1 Homework1 (lab0) contributed by < [`Pepitaw`](https://github.com/Pepitaw/lab0-c) > ###### tags: `linux2022` ## 實驗環境 ```shell $ gcc --version gcc (Ubuntu 9.3.0-17ubuntu1~20.04) 9.3.0 $ 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): 12 On-line CPU(s) list: 0-11 Thread(s) per core: 2 Core(s) per socket: 6 Socket(s): 1 NUMA node(s): 1 Vendor ID: GenuineIntel CPU family: 6 Model: 158 Model name: Intel(R) Core(TM) i7-9750H CPU @ 2.60GHz Stepping: 10 CPU MHz: 2600.000 CPU max MHz: 4500.0000 CPU min MHz: 800.0000 BogoMIPS: 5199.98 L1d cache: 192 KiB L1i cache: 192 KiB L2 cache: 1.5 MiB L3 cache: 12 MiB NUMA node0 CPU(s): 0-11 ``` ## 開發紀錄 :::info 作業要求 - [x] q_new: 建立新的「空」佇列 - [x] q_free: 釋放佇列所佔用的記憶體 - [x] q_insert_head: 在佇列開頭 (head) 插入 (insert) 給定的新節點 (以 LIFO 準則) - [x] q_insert_tail: 在佇列尾端 (tail) 插入 (insert) 給定的新節點 (以 FIFO 準則) - [x] q_remove_head: 在佇列開頭 (head) 移去 (remove) 給定的節點 - [x] q_release_element: 釋放特定節點的記憶體空間 - [x] q_size: 計算目前佇列的節點總量 - [x] q_delete_mid: 移走佇列中間的節點 - [x] q_delete_dup: 在已經排序的狀況，移走佇列中具備重複內容的節點 - [x] q_swap: 交換佇列中鄰近的節點 - [x] q_reverse: 以反向順序重新排列鏈結串列，該函式不該配置或釋放任何鏈結串列節點，換言之，它只能重排已經存在的節點 - [x] q_sort: 以遞增順序來排序鏈結串列的節點 ::: ### q_new 根據 `list.h` 參考函式 `INIT_LIST_HEAD` 初始化 q ，將 q 的 `next` 與 `prev` 指向自己。 :::spoiler 實際程式碼 ```clike struct list_head *q_new() { struct list_head *q = malloc(sizeof(struct list_head)); if (!q) return NULL; INIT_LIST_HEAD(q); return q; } ``` ::: - 實作流程 1. 使用 `malloc` 分配記憶體空間給指標 q 2. 如果 `malloc` 分配空間失敗，會回傳 `NULL` 3. 使用 `INIT_LIST_HEAD` 初始化指標 q ### q_free 根據 `list.h` 參考函式 `list_for_each_entry_safe` ，藉由副本遍歷各個 `entry` ，不會受到移除 `entry` 的影響 :::spoiler 實際程式碼 ```clike void q_free(struct list_head *l) { if (!l) return; element_t *pos, *n; list_for_each_entry_safe (pos, n, l, list) q_release_element(pos); free(l); } ``` ::: - 實作流程 1. 若 `head` 指向 NULL 就 `return` 2. 走訪整個 `linked list` ，對每個 `entry` 呼叫 `q_release_element` 釋放其空間 3. 釋放 `head` 的記憶體空間 ### q_insert_head 根據 `list.h` 參考函式 `list_add` ，將新增的 `element_t` 加到 `head` 的 `next` :::spoiler 實際程式碼 ```clike bool q_insert_head(struct list_head *head, char *s) { if (!head) return false; element_t *e = malloc(sizeof(element_t)); if (!e) return false; e->value = strdup(s); if (!e->value) { free(e); return false; } list_add(&e->list, head); return true; } ``` ::: - 實作流程 1. 若 `head` 指向 NULL 就回傳 `false` 2. 使用 `malloc()` 分配 `element_t` 大小的記憶體空間給 e ，若分配失敗則回傳 `false` 3. 利用 `strdup` 會用 `malloc` 分配記憶體儲存字串的特性，直接指派給 e->value 4. 若 `strdup` 分配記憶體失敗就清除 e 與回傳 `false` 5. 加入新 `entry` 到list :::spoiler 過去嘗試與心路歷程 1. 不知道在 queue.h 有定義 element_t ，自行定義 node ```clike bool q_insert_head(struct list_head *head, char *s) { struct node{ char *str; struct list_head list; }; struct node *n = malloc(sizeof(struct node)); strcpy(n->str, s); list_add(&n->list, head); return true; } ``` 2. 遇到以下問題 Segmentation fault occurred. You dereferenced a NULL or invalid pointer 發現是 e->value 未配置記憶體，利用 strdup 配置記憶體與複製 *s (規格書中提到 Memory for the new string is obtained with malloc ，有malloc仍有配置失敗的時候) ```clike element_t *e = malloc(sizeof(element_t)); if(!e) return false; strcpy(e->value, s); list_add(&e->list, head); return true; ``` 3. 去看 list_add 加入 node 的位置 ```clike struct list_head *tmp = head->next; list_del(tmp); list_add(tmp, head->next->next); ``` 由以下結果得知，可以直接插入指定位置的下一個 `entry` ```shell cmd> ih ant l = [ant dolphin dolphin dolphin gerbil bear dolphin meerkat bear bear bear cat] cmd> reverse l = [dolphin dolphin ant dolphin gerbil bear dolphin meerkat bear bear bear cat] ``` ::: ### q_insert_tail 根據 `list.h` 參考函式 `list_add_tail` ，將新增的 `element_t` 加到 `head` 的 `prev` ，其餘同 `q_insert_head` :::spoiler 實際程式碼 ```clike bool q_insert_tail(struct list_head *head, char *s) { if (!head) return false; element_t *e = malloc(sizeof(element_t)); if (!e) return false; e->value = strdup(s); if (!e->value) { free(e); return false; } list_add_tail(&e->list, head); return true; } ``` ::: ### q_remove_head 根據 `list.h` 參考函式 `list_first_entry` ，找到第一個 `entry` ，也參考函式 `list_del` 將目標 `entry` remove ，成為單一節點 :::spoiler 實際程式碼 ```clike element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize) { if (!head || head->next == head) return NULL; element_t *e = list_first_entry(head, element_t, list); list_del(&e->list); if (sp) { strncpy(sp, e->value, bufsize - 1); sp[bufsize - 1] = '\0'; } return e; } ``` ::: - 實作流程 1. 如果 `head` 指向 NULL 或只有 `head` 就回傳 `NULL` 2. 利用 `list_first_entry` 找到第一個 `entry` 3. 再用`list_del` 將目標 `entry` remove ，成為單一節點 4. 若 sp 存在，複製 e->value 到 sp 並補結尾 `\0` :::spoiler 過去嘗試與心路歷程（有問題待解） 1. 想說用 strdup 修改 sp 不但有配置記憶體，還會自動補 `\0` ，但卻報錯還不知道原因。 ```clike if(sp){ sp = strndup(e->value, bufsize - 1); } ``` ERROR: Failed to store removed value ::: ### q_remove_tail 根據 `list.h` 參考函式 `list_last_entry` ，找到最後一個 `entry` ，其餘與 `q_remove_head` 相同 :::spoiler 實際程式碼 ```clike element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize) { if (!head || head->next == head) return NULL; element_t *e = list_last_entry(head, element_t, list); list_del(&e->list); if (sp) { strncpy(sp, e->value, bufsize - 1); sp[bufsize - 1] = '\0'; } return e; } ``` ::: ### q_size 根據 `list.h` 參考函式 `list_for_each()` 遍歷各個 `entry` :::spoiler 實際程式碼 ```clike int q_size(struct list_head *head) { if (!head) return false; int i = 0; struct list_head *lh; list_for_each (lh, head) i++; return i; } ``` ::: - 實作流程 1. 若傳入的 `head` 指向 NULL 就回傳 `false` 2. 每經過一個 `entry` i 就加一，最後即為size ### q_delete_mid 依據「龜兔賽跑」[Floyd’s Cycle detection](https://en.wikipedia.org/wiki/Cycle_detection)，當 `rabbit` 跑完 list 時， `turtle` 跑到一半的特性，來尋找中間的節點 :::spoiler 實際程式碼 ```clike bool q_delete_mid(struct list_head *head) { struct list_head *fast = head->next, *slow = head->next; for (; fast != head->prev && fast->next != head->prev; fast = fast->next->next, slow = slow->next) ; /*while(fast != NULL && fast->next != NULL){ fast = fast->next->next; slow = slow->next; }*/ slow->prev->next = slow->next; slow->next->prev = slow->prev; q_release_element(list_entry(slow, element_t, list)); return true; } ``` ::: - 實作流程 1. 設置兩個 pointer ， fast 一次跑一個 `entry` ， slow 跑兩個 `entry` 2. 兩 pointer 開始遍歷 list ，當其中一個 pointer 跑完 list 時結束 3. 利用 q_release_element 對 slow 做 delete :::spoiler 過去嘗試與心路歷程 1. 實做龜兔賽跑找中間節點，遇到以下問題 ERROR: Time limit exceeded. Either you are in an infinite loop, or your code is too inefficient 因為迴圈結束方式是判斷是否為 NULL ，但 circular linked list 是頭尾相接不會 NULL ```clike for(struct list_head *fast = head, *slow = head; fast && fast->next; \ fast = fast->next->next, slow = slow->next); ``` ::: ### q_delete_dup :::spoiler 實際程式碼 ```clike bool q_delete_dup(struct list_head *head) { if (!head) return false; element_t *pos, *n; bool used = false; list_for_each_entry_safe (pos, n, head, list) { if (pos->list.next != head && !strcmp(pos->value, list_entry(pos->list.next, element_t, list)->value)) { list_del(&pos->list); q_release_element(pos); used = true; } else if (used) { list_del(&pos->list); q_release_element(pos); used = false; } } return true; } ``` ::: - 實作流程 1. 如果 `head` 指向 NULL 就回傳 `false` 2. 利用 `list_for_each_entry_safe` 遍歷各個 `entry` 3. 利用 `strcmp` 比較 pos 跟下一個 `entry` 的 value 是否相同 4. 若 value 相同且 pos 不是結尾，就將 pos delete 5. 用 use 去紀錄該 `entry` 是否跟以刪除 `entry` 有相同的 value ### q_swap 根據 `list.h` 參考函式 `list_move_tail` 將 `entry` 放到 `head->prev` :::spoiler 實際程式碼 ```clike void q_swap(struct list_head *head) { bool odd = q_size(head) & 0x01; for (int i = q_size(head) >> 1; i > 0; i--) { list_move_tail(head->next->next, head); list_move_tail(head->next, head); } if (odd) list_move_tail(head->next, head); } ``` ::: - 實作流程 1. 先將第二個的 `entry` 放到尾巴 2. 再將第一個的 `entry` 放到尾巴 3. 總共做"總數的一半"次 4. 若總數為奇數，就要再做一次流程二 :::spoiler 過去嘗試與心路歷程（有問題待解） 1. 想使用 `list.h` 函式 `list_swap` ，但發現未定義我是在 linux kernel 版本 5.13.0 查到的函式，與我的 linux kernel 5.13.0-30-generic 相符，但還是找不到原因 ```clike void q_shuffle(struct list_head *head) { srand( time(NULL) ); for (int i = q_size(head); i > 0; i--) { struct list_head *tmp = head->next; for (int x = rand()%i; x > 0; x--){ tmp = tmp->next; } list_swap(tmp, head->prev); //list_move_tail(tmp, head); } } ``` ```shell queue.c: In function ‘q_shuffle’: queue.c:347:2: error: implicit declaration of function ‘list_swap’ [-Werror=implicit-function-declaration] 347 | list_swap(tmp, head->prev); | ^~~~~~~~~ cc1: all warnings being treated as errors make: *** [Makefile:50：queue.o] 錯誤 1 ``` ::: ### q_reverse :::spoiler 實際程式碼 ```clike void q_reverse(struct list_head *head) { if (!head || head->next->next == head) return; struct list_head *pos = head->prev; for (int i = q_size(head); i > 1; i--) list_move_tail(pos->prev, head); } ``` ::: - 實作流程 1. 若 `head` 指向 NULL 或 list 只有一個 `entry` 就回傳 NULL 2. 從尾巴開始反向遍歷，將 `entry` 依序放到尾巴 ### q_sort :::spoiler 實際程式碼 ```clike struct list_head *mergesort(struct list_head *node) { if (!node || !node->next) return node; struct list_head *fast = node, *slow = node; for (; fast->next && fast->next->next; fast = fast->next->next, slow = slow->next) ; fast = slow->next; slow->next = NULL; struct list_head *l1 = mergesort(node); struct list_head *l2 = mergesort(fast); struct list_head t_head, *tmp = &t_head; while (l1 && l2) { if (strcmp(list_entry(l1, element_t, list)->value, list_entry(l2, element_t, list)->value) > 0) { tmp->next = l2; l2 = l2->next; } else { tmp->next = l1; l1 = l1->next; } tmp = tmp->next; } if (l1) tmp->next = l1; else tmp->next = l2; return t_head.next; } void q_sort(struct list_head *head) { if (!head || !head->next) return; head->prev->next = NULL; struct list_head *list = head->next; list = mergesort(list); head->next = list; struct list_head *i = head; while (i->next != NULL) { i->next->prev = i; i = i->next; } head->prev = i; i->next = head; } ``` ::: - 實作流程 1. 若 `head` 指向 NULL 或 list 沒有 `entry` 就 return 2. 將尾巴的 next 指向 NULL，切斷 next 方向的 circular 3. 將去除 `head` 的 list 進行 mergesort - 以下為 mergesort 4. 利用「龜兔賽跑」將 list 從中間一分為二 5. 再用 `strcmp` 比較大小，依小到大排列 6. 將 `head` 指向排序好的 list 7. 最後利用 `list` 的 `next->prev` 將所有 `prev` 重新排列 ## 理解 [Linux 核心中的排序實作](https://github.com/torvalds/linux/blob/master/lib/list_sort.c) :::spoiler merge (pointer to pointer version) ```clike static struct list_head *merge(void *priv, list_cmp_func_t cmp, struct list_head *a, struct list_head *b) { struct list_head *head, **tail = &head; for (;;) { /* if equal, take 'a' -- important for sort stability */ if (cmp(priv, a, b) <= 0) { *tail = a; tail = &a->next; a = a->next; if (!a) { *tail = b; break; } } else { *tail = b; tail = &b->next; b = b->next; if (!b) { *tail = a; break; } } } return head; } ``` ::: - 程式碼理解 1. 用 pointer to pointer 指向 a 與 b 之間較小的 2. 但沒有處理 prev 的部份 :::spoiler merge_final (pointer version) ```clike static void merge_final(void *priv, list_cmp_func_t cmp, struct list_head *head, struct list_head *a, struct list_head *b) { struct list_head *tail = head; u8 count = 0; for (;;) { /* if equal, take 'a' -- important for sort stability */ if (cmp(priv, a, b) <= 0) { tail->next = a; a->prev = tail; tail = a; a = a->next; if (!a) break; } else { tail->next = b; b->prev = tail; tail = b; b = b->next; if (!b) { b = a; break; } } } /* Finish linking remainder of list b on to tail */ tail->next = b; do { /* * If the merge is highly unbalanced (e.g. the input is * already sorted), this loop may run many iterations. * Continue callbacks to the client even though no * element comparison is needed, so the client's cmp() * routine can invoke cond_resched() periodically. */ if (unlikely(!++count)) cmp(priv, b, b); b->prev = tail; tail = b; b = b->next; } while (b); /* And the final links to make a circular doubly-linked list */ tail->next = head; head->prev = tail; } ``` ::: - 程式碼理解 1. 比較 a 跟 b 的大小，用 tail 的 next 指向比較小的 entry 2. 一路遍歷兩個 linked list 直到其中一個 linked list 結束(a 或 b 指向 NULL) 3. 用 b 指向還未走到尾巴的 linked list (未經過的 entry) 4. 用 tail 的 next 指向剩下的 entry 5. 遍歷完剩下的 entry ，並用 count 紀錄剩下的 entry 數量 6. 利用 unlikely 將 count 轉成 bool 7. 頭尾相接成為 circular - 程式碼差異 1. 在每次 merge 時就處理好 prev 與 next 的 link 我則是只看 next ，將 linked list 用 next 排列完後，再一次將所有的 prev 處理好 2. 計算兩個 linked list 的 merge 是否 entry 數量相近，我則沒有考慮 :::spoiler list_sort ```clike void list_sort(void *priv, struct list_head *head, list_cmp_func_t cmp) { struct list_head *list = head->next, *pending = NULL; size_t count = 0; /* Count of pending */ if (list == head->prev) /* Zero or one elements */ return; /* Convert to a null-terminated singly-linked list. */ head->prev->next = NULL; do { 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; } /* Move one element from input list to pending */ list->prev = pending; pending = list; list = list->next; pending->next = NULL; count++; } while (list); /* End of input; merge together all the pending lists. */ list = pending; pending = pending->prev; for (;;) { struct list_head *next = pending->prev; if (!next) break; list = merge(priv, cmp, pending, list); pending = next; } /* The final merge, rebuilding prev links */ merge_final(priv, cmp, head, pending, list); } ``` ::: - 程式碼理解 1. 用 head->next == head->prev 去判斷是否只有一個 entry 或沒有 entry 2. 將 circular 的 next 部份斷開 - 程式碼差異 ## 運用 Valgrind 排除 qtest 實作的記憶體錯誤 :::info 作業目標 - [ ] 運用 Valgrind 排除 qtest 實作的記憶體錯誤，並透過 Massif 視覺化 “simulation” 過程中的記憶體使用量，需要設計對應的實驗 ::: ==更新中== :::spoiler ```shell $ valgrind -q --leak-check=full ./qtest -f traces/trace-01-ops.cmd ==2951== 5 bytes in 1 blocks are still reachable in loss record 1 of 2 ==2951== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so) ==2951== by 0x4A5250E: strdup (strdup.c:42) ==2951== by 0x1108BE: linenoiseHistoryAdd (linenoise.c:1236) ==2951== by 0x111451: linenoiseHistoryLoad (linenoise.c:1325) ==2951== by 0x10C6B0: main (qtest.c:951) ==2951== ==2951== 160 bytes in 1 blocks are still reachable in loss record 2 of 2 ==2951== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so) ==2951== by 0x11087E: linenoiseHistoryAdd (linenoise.c:1224) ==2951== by 0x111451: linenoiseHistoryLoad (linenoise.c:1325) ==2951== by 0x10C6B0: main (qtest.c:951) ``` ```clike linecopy = strdup(line); ``` ::: ## 在 qtest 提供新的命令 shuffle :::info 作業目標 - [x] 在 `qtest` 提供新的命令 `shuffle` ，允許藉由 [Fisher–Yates shuffle](https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle) 演算法，對佇列中所有節點進行洗牌 (shuffle) 操作 - [ ] 解釋 [select](https://man7.org/linux/man-pages/man2/select.2.html) 系統呼叫在本程式的使用方式，並分析 console.c 的實作，說明其中運用 CS:APP [RIO](http://csapp.cs.cmu.edu/2e/ch10-preview.pdf) 套件的原理和考量點。可對照參考 CS:APP [第 10 章重點提示](https://hackmd.io/@sysprog/H1TtmVTTz) ::: :::spoiler 程式碼 ```clike void q_shuffle(struct list_head *head) { srand(time(NULL)); for (int i = q_size(head); i > 0; i--) { struct list_head *tmp = head->next, *tail = head->prev; for (int x = rand() % i; x > 0; x--) tmp = tmp->next; list_del(tail); list_add(tail, tmp->prev); list_move_tail(tmp, head); } } ``` ::: - 實作流程 1. 將 `linked list` 的 size 不斷減一，作為隨機變數的範圍 2. 遍歷去找隨機變數所指定的 `entry` 3. 用 `list_del` 將尾巴成為獨立的 `entry` ，將尾巴用 `list_add` 加到目標 `entry` 的下一個 `entry` ，再將目標 `entry` 移動到尾巴，作為交換 ## 在 qtest 提供新的命令 web ## 參考資料 - HackMD 模板參考 [`Risheng1128`](https://hackmd.io/kZtEa_LdSGKVQGg8jczrLQ?view) - Mergesort 分割部分參考 [`Risheng1128`](https://hackmd.io/kZtEa_LdSGKVQGg8jczrLQ?view) - [K01: lab0](https://hackmd.io/@sysprog/linux2022-lab0) - [你所不知道的 C 語言: linked list 和非連續記憶體](https://hackmd.io/@sysprog/c-linked-list) - [Floyd’s Cycle detection](https://en.wikipedia.org/wiki/Cycle_detection) - [quick-sort.c](https://github.com/sysprog21/linux-list/blob/master/examples/quick-sort.c)

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.