--- tags: linux2022 --- # 2022q1 Homework1 (lab0) contributed by < [kaiweike](https://github.com/kaiweike/lab0-c) > ## 實驗環境 :::spoiler 剛開始的實驗環境 ```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): 4 On-line CPU(s) list: 0-3 Thread(s) per core: 2 Core(s) per socket: 2 Socket(s): 1 NUMA node(s): 1 Vendor ID: GenuineIntel CPU family: 6 Model: 61 Model name: Intel(R) Core(TM) i5-5257U CPU @ 2.70GHz Stepping: 4 CPU MHz: 1405.132 CPU max MHz: 3100.0000 CPU min MHz: 500.0000 BogoMIPS: 5399.87 Virtualization: VT-x L1d cache: 64 KiB L1i cache: 64 KiB L2 cache: 512 KiB L3 cache: 3 MiB NUMA node0 CPU(s): 0-3 ``` ::: 上面的環境一直故障，後來換成這個實驗環境 ```shell $ gcc --version gcc (Ubuntu 9.4.0-1ubuntu1~20.04.1) 9.4.0 $ lscpu Architecture: x86_64 CPU op-mode(s): 32-bit, 64-bit Byte Order: Little Endian Address sizes: 48 bits physical, 48 bits virtual CPU(s): 4 On-line CPU(s) list: 0-3 Thread(s) per core: 2 Core(s) per socket: 2 Socket(s): 1 NUMA node(s): 1 Vendor ID: AuthenticAMD CPU family: 21 Model: 16 Model name: AMD A8-4500M APU with Radeon(tm) HD Graphics Stepping: 1 Frequency boost: enabled CPU MHz: 1511.772 CPU max MHz: 1900.0000 CPU min MHz: 1400.0000 BogoMIPS: 3793.17 Virtualization: AMD-V L1d cache: 32 KiB L1i cache: 128 KiB L2 cache: 4 MiB NUMA node0 CPU(s): 0-3 ``` ## 開發紀錄 ```shell $ make test CC queue.o LD qtest scripts/driver.py -c --- Trace Points +++ TESTING trace trace-01-ops: # Test of insert_head and remove_head --- trace-01-ops 5/5 +++ TESTING trace trace-02-ops: # Test of insert_head, insert_tail, remove_head, remove_tail, and delete_mid --- trace-02-ops 6/6 +++ TESTING trace trace-03-ops: # Test of insert_head, insert_tail, reverse, and remove_head --- trace-03-ops 6/6 +++ TESTING trace trace-04-ops: # Test of insert_head, insert_tail, size, swap, and sort --- trace-04-ops 6/6 +++ TESTING trace trace-05-ops: # Test of insert_head, insert_tail, remove_head, reverse, size, swap, and sort --- trace-05-ops 6/6 +++ TESTING trace trace-06-ops: # Test of insert_head, insert_tail, delete duplicate, and sort --- trace-06-ops 6/6 +++ TESTING trace trace-07-string: # Test of truncated strings --- trace-07-string 6/6 +++ TESTING trace trace-08-robust: # Test operations on empty queue --- trace-08-robust 6/6 +++ TESTING trace trace-09-robust: # Test remove_head with NULL argument --- trace-09-robust 6/6 +++ TESTING trace trace-10-robust: # Test operations on NULL queue --- trace-10-robust 6/6 +++ TESTING trace trace-11-malloc: # Test of malloc failure on insert_head --- trace-11-malloc 6/6 +++ TESTING trace trace-12-malloc: # Test of malloc failure on insert_tail --- trace-12-malloc 6/6 +++ TESTING trace trace-13-malloc: # Test of malloc failure on new --- trace-13-malloc 6/6 +++ TESTING trace trace-14-perf: # Test performance of insert_tail, reverse, and sort Segmentation fault occurred. You dereferenced a NULL or invalid pointer --- trace-14-perf 0/6 +++ TESTING trace trace-15-perf: # Test performance of sort with random and descending orders # 10000: all correct sorting algorithms are expected pass # 50000: sorting algorithms with O(n^2) time complexity are expected failed # 100000: sorting algorithms with O(nlogn) time complexity are expected pass --- trace-15-perf 6/6 +++ TESTING trace trace-16-perf: # Test performance of insert_tail --- trace-16-perf 6/6 +++ TESTING trace trace-17-complexity: # Test if time complexity of q_insert_tail, q_insert_head, q_remove_tail, and q_remove_head is constant Probably constant time Probably constant time Probably constant time Probably constant time --- trace-17-complexity 5/5 --- TOTAL 94/100 make: *** [Makefile:56: test] Error 1 ``` ## 基礎概念 * [typeof](https://gcc.gnu.org/onlinedocs/gcc/Typeof.html) * [offsetof](https://man7.org/linux/man-pages/man3/offsetof.3.html) ([參考 你所不知道的 C 語言: linked list 和非連續記憶體-Linked list 在 Linux 核心原始程式碼-簡化的實作](https://hackmd.io/@sysprog/c-linked-list#簡化的實作)) `offsetof(type, member)` =>可得到成員的位址減去 struct 的起始位址 * [container_of](https://github.com/torvalds/linux/blob/master/include/linux/container_of.h) ([參考 Linux 核心原始程式碼巨集: container_of](https://hackmd.io/@sysprog/linux-macro-containerof)) `#define container_of(ptr, type, member)` => 可得到 type 結構的 address * [Common vulnerabilities guide for C programmers](https://security.web.cern.ch/recommendations/en/codetools/c.shtml) **“ Most vulnerabilities in C are related to buffer overflows external link and string manipulation. ”** * ~~gets()~~ -> `fgets()` * ~~strcpy()~~ -> `strlcpy()` or `strncpy()` * ~~strcat()~~ -> `strncat()` * ~~strcmp()~~ -> `strncmp()` * ~~sprintf()~~ -> `snprintf()` * string formatting -> always hardcode the format string. At least, never let it come directly from any user's input. * file opening ## 實做佇列(queue.c) :::danger 不要只列出原始程式碼，要提出你的想法/推測，並予以驗證。請把開發紀錄當作「資訊科技公司面試的逐字稿」來面對，你現在若能用越專業的說法，明日就能表現更好。 :notes: jserv ::: ### q_new :::spoiler 最初的寫法 ```c // Create empty queue. // Return NULL if could not allocate space. struct list_head *q_new() { struct list_head *q = malloc(sizeof(struct list_head)); if (q != NULL) q->next = q->prev = q; return q; } ``` ::: 參考 [2020leon](https://hackmd.io/@6649/linux2022-lab0) ，並改寫為更簡潔的寫法： 1. 利用 `malloc` 分配記憶體空間。 2. 利用 `INIT_LIST_HEAD` 初始化 `struct list_head` 物件成員。 ```c struct list_head *q_new() { struct list_head *q = malloc(sizeof(struct list_head)); if (q) INIT_LIST_HEAD(q); return q; } ``` ### q_free :::spoiler 這個寫法一直出錯 ```c void q_free(struct list_head *l) { element_t *entry, *safe; if(!l || list_empty(l)) return; list_for_each_entry_safe( entry, safe, l, list) q_release_element(entry); free(l); } ``` ::: 後來刪掉 if 判斷中的 `list_empty(l)` 就好了， 因為當 `list_empty() = !0` 時表示 list is empty， 但 empty 還是指向有效結構，開頭(head)的值為NULL([參考 K01: lab0](https://hackmd.io/@sysprog/linux2022-lab0#-改寫自-CMU-電腦系統概論的作業))。 ```c void q_free(struct list_head *l) { element_t *entry, *safe; if(!l) return; list_for_each_entry_safe( entry, safe, l, list) q_release_element(entry); free(l); } ``` ### q_insert_head ::: spoiler 這個寫法一直出現錯誤 ```c // Attempt to insert element at head of queue. // Return true if successful. // Return false if q is NULL or could not allocate space. // Argument s points to the string to be stored. // The function must explicitly allocate space and copy the string into it. bool q_insert_head(struct list_head *head, char *s) { element_t n; n.value = s; if(list_empty(head)) return false; list_add(&n.list, head); return true; } ``` ::: 參考 [freshLiver](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) 的寫法後， 發現原來是少了 `malloc` 和 `memcpy` 這兩個步驟，沒有配置指定大小的記憶體空間。 另外，發現 `list_empty` != `null`， “ 若你有空的紅包袋，裡面的東西是 empty; 若你連紅包袋都沒有，就可以說 NULL; ” ([參考 K01: lab0](https://hackmd.io/@sysprog/linux2022-lab0#-改寫自-CMU-電腦系統概論的作業))。 ```c bool q_insert_head(struct list_head *head, char *s) { if(!head) return false; element_t *n = malloc(sizeof(element_t)); if(!n) return false; n->value = malloc(strlen(s)+1); if(!n->value) return false; memcpy(n->value, s, strlen(s)); n->value[strlen(s)] = '\0'; list_add(&n->list, head); return true; } ``` 參考 [freshLiver](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) 的寫法， 進一步使用 `strdup` 簡化 `malloc`、 `memcpy` 和 `value[strlen(s)] = '\0'` 的操作: ```c bool q_insert_head(struct list_head *head, char *s) { if(!head) return false; element_t *n = malloc(sizeof(element_t)); if(!n) return false; n->value = strdup(s); if (!n->value) { free(n); return false; } list_add(&n->list, head); return true; } ``` ### q_insert_tail 操作邏輯和 `q_insert_head` 一樣，只是將 `list_add` 更換成 `list_add_tail` ```c bool q_insert_tail(struct list_head *head, char *s) { if(!head) return false; element_t *n = malloc(sizeof(element_t)); if(!n) return false; n->value = strdup(s); if (!n->value) { free(n); return false; } list_add_tail(&n->list, head); return true; } ``` ### q_remove_head ```c // Attempt to remove element from head of queue. // Return target element. // Return NULL if queue is NULL or empty. // If sp is non-NULL and an element is removed, copy the removed string to *sp // (up to a maximum of bufsize-1 characters, plus a null terminator.) element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize) { if(!head || list_empty(head)) return NULL; element_t *n = list_first_entry(head, element_t, list); list_del(head->next); if(sp){ strncpy(sp, n->value, bufsize-1); sp[bufsize-1] = '\0'; } return n; } ``` ### q_remove_tail ```c // Attempt to remove element from tail of queue. element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize) { if(!head || list_empty(head)) return NULL; element_t *n = list_last_entry(head, element_t, list); list_del(head->prev); if(sp){ strncpy(sp, n->value, bufsize-1); sp[bufsize-1] = '\0'; } return n; } ``` ### q_delete_mid ::: spoiler 這樣的寫法有誤： ```c // Delete the middle node in list. // The middle node of a linked list of size n is the // ⌊n / 2⌋th node from the start using 0-based indexing. // If there're six element, the third member should be return. // Return true if successful. // Return false if list is NULL or empty. bool q_delete_mid(struct list_head *head) { if (!head || list_empty(head)) return false; struct list_head *front = head->next; struct list_head *back = head->prev; while (front != back && front->next != back) { front = head->next; back = back->prev; } list_del(front); return true; } ``` ::: 參考 [LJP-TW](https://hackmd.io/@LJP/SyRFuull9) 的寫法後修改為： ```c 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; if (list_is_singular(head)){ element_t *element = q_remove_head(head, NULL, 0); q_release_element(element); return true; } struct list_head *twoStep = head->next; struct list_head *oneStep = head->next; while (twoStep != head && twoStep->next != head){ twoStep = twoStep->next->next; oneStep = oneStep->next; } element_t *element = list_entry(oneStep, element_t, list); list_del(oneStep); q_release_element(element); return true; } ``` ### q_delete_dup 參考 [eric88525](https://hackmd.io/@eric88525/linux2022-lab0) 的寫法 ```c // Delete all nodes that have duplicate string, // leaving only distinct strings from the original list. // Return true if successful. // Return false if list is NULL. // // Note: this function always be called after sorting, in other words, // list is guaranteed to be sorted in ascending order. bool q_delete_dup(struct list_head *head) { if(!head || list_empty(head)) return false; struct list_head **p = &(head->next); struct list_head *curr = head->next; struct list_head *temp = NULL; while(curr != head && curr->next != head){ if(strcmp(container_of(curr, element_t, list)->value, container_of(curr->next, element_t, list)->value) == 0){ do{ temp = curr; curr = curr->next; list_del(tmp); q_release_element(container_of(temp, element_t, list)); }while(curr->next != head && strcmp(container_of(curr, element_t, list)->value, container_of(curr->next, element_t, list)->value) == 0); } p = &((*p)->next); curr = curr->next; } return true; } ``` ### q_swap ```c // Attempt to swap every two adjacent nodes. void q_swap(struct list_head *head) { if(!head || list_empty(head)) return; struct list_head *curr = head->next; struct list_head *next = NULL; while(curr && curr->next && curr != head && curr->next != head){ next = curr->next; list_del(next); list_add_tail(next, curr); curr = curr->next; } } ``` ### q_reverse ```c // Reverse elements in queue // No effect if q is NULL or empty // This function should not allocate or free any list elements // (e.g., by calling q_insert_head, q_insert_tail, or q_remove_head). // It should rearrange the existing ones. void q_reverse(struct list_head *head) { if(!head|| list_empty(head)) return; struct list_head *prev = head->prev; struct list_head *curr head; struct list_head *next NULL; while(next != head){ next = curr->next; curr->next = prev; curr->prev = next; prev = curr; curr = next; } } ``` 參考 [kdvnt](https://hackmd.io/WuqBNTdFQnuNxkFtR6FIWg?view#q_reverse) 更精簡的方法： ```c void q_reverse(struct list_head *head) { if (!head || list_empty(head) || list_is_singular(head)) return; struct list_head *node, *safe; list_for_each_safe (node, safe, head) list_move(node, head); } ``` ### q_sort [參考 你所不知道的 C 語言: linked list 和非連續記憶體- MergeSort的實作](https://hackmd.io/@sysprog/c-linked-list#Merge-Sort-的實作) * 實做遞迴版本的 MergeSort: ```c // Sort elements of queue in ascending order // No effect if q is NULL or empty. In addition, if q has only one // element, do nothing. struct list_head *merge(struct list_head *L1, struct list_head *L2) { struct list_head *head = NULL, **ptr = &head; while (L1 && L2) { if (strcmp(list_entry(L1, element_t, list)->value, list_entry(L2, element_t, list)->value) < 0) { *ptr = L1; L1 = L1->next; } else { *ptr = L2; L2 = L2->next; } ptr = &(*ptr)->next; } *ptr = (struct list_head *) ((unsigned long int) L1 | (unsigned long int) L2); return head; } struct list_head *mergesort(struct list_head *head) { if (!head || !head->next) return head; struct list_head *slow = head, *fast = head->next; while (fast && fast->next) { fast = fast->next->next; slow = slow->next; } fast = slow->next; slow->next = NULL; slow = head; struct list_head *L1 = mergesort(slow); struct list_head *L2 = mergesort(fast); return merge(L1, L2); } void q_sort(struct list_head *head) { if (!head || list_empty(head) || list_is_singular(head)) return; head->prev->next = NULL; head->next = mergesort(head->next); struct list_head *prev = head, *cur = head->next; for (; cur != NULL; prev = cur, cur = cur->next) { cur->prev = prev; } prev->next = head; head->prev = prev; } ``` 測項 14 和 15 指出效能不夠好 ```bash +++ TESTING trace trace-14-perf: # Test performance of insert_tail, reverse, and sort ERROR: Time limit exceeded. Either you are in an infinite loop, or your code is too inefficient --- trace-14-perf 0/6 +++ TESTING trace trace-15-perf: # Test performance of sort with random and descending orders # 10000: all correct sorting algorithms are expected pass # 50000: sorting algorithms with O(n^2) time complexity are expected failed # 100000: sorting algorithms with O(nlogn) time complexity are expected pass --- trace-15-perf 6/6 ``` 推測可能是因為執行遞迴需要多次函式呼叫，如果呼叫層數比較深，增加的堆疊處理會影響效能。 * 實做迭代版本的 MergeSort: ```c struct list_head *merge(struct list_head *L1, struct list_head *L2) { struct list_head *head = NULL, **ptr = &head; while (L1 && L2) { if (strcmp(list_entry(L1, element_t, list)->value, list_entry(L2, element_t, list)->value) < 0) { *ptr = L1; L1 = L1->next; } else { *ptr = L2; L2 = L2->next; } ptr = &(*ptr)->next; } *ptr = (struct list_head *) ((unsigned long int) L1 | (unsigned long int) L2); return head; } struct list_head *mergesort_iter(struct list_head *head){ if (!head || !head->next) return head; int top = 0; int listsSize = 0; struct list_head *stack[1000] = {NULL}; struct list_head *lists[100000] = {NULL}; stack[top] = head; while(top >= 0){ struct list_head *left = stack[top--]; if(left){ struct list_head *slow = left; struct list_head *fast; for(fast = left->next; fast && fast->next; fast = fast->next->next) slow = slow->next; struct list_head *right = slow->next; slow->next = NULL; stack[++top] = left; stack[++top] = right; }else{ lists[listsSize++] = stack[top--]; } } while(listsSize>1){ for(int i = 0, j = listsSize - 1; i < j; i++, j--) lists[i] = merge(lists[i], lists[j]); listsSize = (listsSize + 1) / 2; } head = lists[0]; return head; } void q_sort(struct list_head *head) { if (!head || list_empty(head) || list_is_singular(head)) return; head->prev->next = NULL; head->next = mergesort_iter(head->next); struct list_head *curr = head, *next = head->next; while(next){ next->prev = curr; curr = next; next = next->next; } curr->next = head; head->prev = curr; } ``` Segmentation fault..改寫中 ```bash +++ TESTING trace trace-14-perf: # Test performance of insert_tail, reverse, and sort Segmentation fault occurred. You dereferenced a NULL or invalid pointer --- trace-14-perf 0/6 +++ TESTING trace trace-15-perf: # Test performance of sort with random and descending orders # 10000: all correct sorting algorithms are expected pass # 50000: sorting algorithms with O(n^2) time complexity are expected failed # 100000: sorting algorithms with O(nlogn) time complexity are expected pass ``` ## 實做洗牌(shuffle) ## 實做伺服器(web) ## ## 參考資訊 * [jim12312321](https://hackmd.io/@MMz_Y0CPR-2VCQTxd4pFIA/linux2022-lab0) * [laneser](https://hackmd.io/@laneser/linux2022_lab0) * [2020leon](https://hackmd.io/@6649/linux2022-lab0) * [freshLiver](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) * [eric88525](https://hackmd.io/@eric88525/linux2022-lab0) * [LJP-TW](https://hackmd.io/@LJP/SyRFuull9) * [kdvnt](https://hackmd.io/WuqBNTdFQnuNxkFtR6FIWg?view#q_reverse) <s> linked_list https://haogroot.com/2019/12/12/漫談-linked-list-在-linux-kernel-中的不一樣/ https://www.cntofu.com/book/46/linux_kernel/20.md https://myao0730.blogspot.com/2016/12/linux.html http://adrianhuang.blogspot.com/2007/10/linux-kernel-listhead.html container_of https://hackmd.io/@sysprog/linux-macro-containerof http://adrianhuang.blogspot.com/2010/01/linux-kernel-containerof.html https://myao0730.blogspot.com/2016/09/linuxcontainerof-offsetof.html https://zhuanlan.zhihu.com/p/54932270 https://www.gushiciku.cn/pl/ggOa/zh-tw https://blog.csdn.net/wukongmingjing/article/details/81746071 </s> :::danger 不用花太多時間 Google 搜尋，大部分需要細讀的材料，我已經列在教材和作業說明中，請確保你閱讀「每一段落」及其指向的「每個」超連結。 :notes: jserv :::