--- tags: linux2023 --- # 2023q1 Homework1 (lab0) contributed by < `JoshuaLee0321` > ## 開發環境 ```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. $ lscpu Architecture: x86_64 CPU op-mode(s): 32-bit, 64-bit Address sizes: 43 bits physical, 48 bits virtual Byte Order: Little Endian CPU(s): 12 On-line CPU(s) list: 0-11 Vendor ID: AuthenticAMD Model name: AMD Ryzen 5 2600X Six-Core Processor CPU family: 23 Model: 8 Thread(s) per core: 2 Core(s) per socket: 6 Socket(s): 1 Stepping: 2 Frequency boost: enabled CPU max MHz: 3600.0000 CPU min MHz: 2200.0000 BogoMIPS: 7199.10 Flags: fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov pat pse36 clflush mmx fxsr sse sse2 ht ``` ## 目前分數 <s> 目前分數 100/100 都卡在一些memory的分配問題 2023/2/23 由於課程時發現 C 語言的前置處理器可用來定義 function-like macro，從而使程式碼更容易維護，所以本日會專注在定義macro 2023/2/27 完成 delete_dup 2023/2/27 make valgrind 中出現非常多錯誤，目前正在debug 2023/2/27 由於 `memcpy` 會報錯，所以把所有有關於 `memcpy` 的都改成 `strncpy` </s> :::warning HackMD 提供時間戳記，不需要自行列舉。 注意作業書寫規範：中英文間用一個半形空白字元區隔。 :notes: jserv > 好的 ::: ## 開發 `queue.c` 的過程 ### `q_new` * 首先利用 `malloc` 分配空間給queue，考量到`malloc`有機會出錯，那先判斷是不是沒有分配成功，之後再利用 Linux 核心中的 `INIT_LIST_HEAD` 來把指針指向自己 :::spoiler ```c struct list_head *q_new() { struct list_head *head = malloc(1 * sizeof(struct list_head)); if(!head) return NULL; INIT_LIST_HEAD(head); return head; } ``` ::: ### `q_free` * 最剛開始的寫法，利用 `list_for_each_safe` run 過所有的 item，一個一個節點 release 但這樣會出先 segmentation fault :::danger 改進你的漢語描述。 :notes: jserv ::: :::spoiler ```c void q_free(struct list_head *l) { if (!l || list_empty(l)) { free(l); return; } struct list_head *it,*safe; list_for_each_safe(it, safe, l){ element_t *tmp = list_entry(it, element_t, list); list_del(it); free(tmp); } free(list_entry(l, element_t, list)); return; } ``` ::: :::info 後續改成 `q_release_element` 的內建API ::: ```c void q_free(struct list_head *l) { if(!l || list_empty(l)) return; // ~~ struct list_head *it, *safe; // list_for_each_safe(it, safe, l){ // q_release_element(it); // }~~ /*以上為錯誤版本，已修正成以下版本*/ list_for_each_entry_safe(it, safe, l, list) { q_release_element(it); } free(l) } ``` 更正版本： `element_t *it = NULL, *safe = NULL;` `list_for_each_entry_safe(it, safe, l, list) { q_release_element(it); }` :::info (更新)發現 safe 並沒有初始化成NULL 導致出錯，已修正 (更新)發現 list_for_each_entry_safe 以及 q_release_element 才可以把東西刪除完全 ::: ### `q_insert_head` `q_insert_tail` `q_delete_head` `q_delete_tail` :::info (更)剛開始的實做如下，但這樣會發生我的實做並不是constant time，錯誤還有代釐清 (更)以上課後學習到的新知 (macro) function 為基準 重新製作了 q_insert_##type 在macro 中 (更)已把 q_insert 以及 q_remove 類型的都把它做成macro 方便維護，除此之外還找到了 `q_remove_macro` 中少加入 if(list_empty(head)) 而導致 `segmentation fault` ::: #### macro 如下 :::spoiler ```c #define q_insert_macro(type, func) \ bool q_insert_##type(struct list_head *head, char *s) \ { \ if (!head) \ return false; \ element_t *new_node = malloc(1 * sizeof(*new_node)); \ if (!new_node) \ return false; \ new_node->value = malloc((strlen(s) + 1) * sizeof(char)); \ if (!new_node->value) { \ q_release_element(new_node); \ return false; \ } \ memcpy(new_node->value, s, strlen(s) + 1); \ func(&new_node->list, head); \ return true; \ } \ #define q_remove_macro(type, func) \ element_t *q_remove_##type(struct list_head *head, char *sp, \ size_t bufsize) \ { \ if (!head || list_empty(head)) \ return NULL; \ element_t *del = func(head, element_t, list); \ list_del(&del->list); \ if (sp != NULL) { \ memcpy(sp, del->value, bufsize - 1); \ sp[bufsize - 1] = '\0'; \ } \ return del; \ } ``` ::: 而實際上我就可以只利用四行程式碼來實作 :::success ```c /* Insert an element at head of queue */ q_insert_macro(head, list_add); /* Insert an element at tail of queue */ q_insert_macro(tail, list_add_tail); /* Remove an element from head of queue */ q_remove_macro(head, list_first_entry); /* Remove an element from tail of queue */ q_remove_macro(tail, list_last_entry); ``` ::: * 如此一來 insert_head 跟 insert_tail 都可以在組譯階段被完成，如此一來可以節省空間之外還可以更好的維護兩個function * 不過目前還在找出為甚麼此function 無法在constant time 完成，之後會研讀論文 ### `q_delete_dup` * 利用 `linux/list.h` 中的 API 跑過迴圈；要注意的事情是，這個function 必須把重複的東西通通刪除掉。由於`list_for_each_safe` 中的 `safe` 可以當作 `next` 來使用，如此一來我們只要 1. 跑過 `head` 中的所有元素 2. 使用 iterator `it` 來觀察是否當前元素與下個元素相同 3. 利用 `bool not_finished` 變數來記錄是否要把當前 `it` 刪除 以下為實作code :::spoiler ```c bool q_delete_dup(struct list_head *head) { // https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/ if (!head || list_is_singular(head)) return false; struct list_head *it, *safe = NULL; bool not_finished = false; list_for_each_safe (it, safe, head) { element_t *prev = list_entry(it, element_t, list); element_t *cur = list_entry(safe, element_t, list); if (!strcmp(prev->value, cur->value)) { not_finished = true; list_del(it); q_release_element(prev); if (safe->next == (head)) { list_del(safe); q_release_element(cur); break; } } else if (not_finished) { not_finished = false; list_del(it); q_release_element(prev); } } return true; } ``` ::: ### `q_size` * 已經由 `jserv` 老師撰寫好了 ```c int q_size(struct list_head *head) { if (!head) return 0; int len = 0; struct list_head *li; list_for_each(li,head) len++; return len; } ``` ### `q_delete_mid` * 基本上這個題目有兩種作法，一種先找出 `queue` 的長度除以2之後給定一個`int cnt` 去計算這個list目前到哪裡，但這個實做方法有一個問題，它會花到O(2N)的時間 * N = 得到 `size` 的時間 * N = traverse 到中間的時間 * 第二個作法就是利用兩種不同方向或速度的指標，而我的實做方法就是利用一個每一次只會往後走一歩的 `single_p` 以及每一次會往後走兩步的 `double_p`，在double走到底的時候single會直接在中間 * 如此一來只需要直接把 `single_p` 給移除掉即可 :::spoiler ```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; struct list_head *single_p, *double_p; single_p = double_p = head->next; while(double_p != (head) && double_p->next != (head)) { single_p = single_p->next; double_p = double_p->next->next; } list_del_init(single_p); q_release_element(list_entry(single_p,element_t,list)); return true; } ``` ::: ### `q_swap` * 在 `swap-nodes-in-pairs` 中，可以使用 `iterative` 跟 `recursive` 的方法實做，而因為有linux kernel 的 API，我選擇使用 `iterative` 的作法 * 使用 `it` 當作 每一次走過的node * 每次 `it` 往前走一步 * 每次 `it` 跟 `it->next` 互換 如此一來就可以達到每兩個 node 互相交換了 :::spoiler ```c void q_swap(struct list_head *head) { if(!head || list_empty(head) || head->next->next == head) return; struct list_head *it = head->next; while(it != (head) && it->next != (head)) { list_move(it,it->next); it = it->next; } // https://leetcode.com/problems/swap-nodes-in-pairs/ } ``` ::: ### `q_reverse` * `q_reverse` 如果使用 Linux 核心的 api 就會非常簡單 * 儘需要走過這整個串列，並且每一次都把當前的node放到最前方即可 ```c void q_reverse(struct list_head *head) { if(!head || list_empty(head) || list_is_singular(head)) return; struct list_head *it, *safe = NULL; list_for_each_safe(it, safe, head) { list_move(it, head); } return; } ``` ### `q_sort` * 參考[你所不知道的 c 語言: linked list 和非連續記憶體及 Linked List Sort](https://hackmd.io/@sysprog/c-linked-list#Merge-Sort-%E7%9A%84%E5%AF%A6%E4%BD%9C) 中提到的Merge Sort ，並以 [LiChiii](https://hackmd.io/@NYC6Z-WqQ3W-61xcE-2SvA/SJDBv7Cps#q_sort) 的程式碼為實作。 ## `Valgrind` ```shell # Explicitly disable sanitizer(s) $ make clean SANITIZER=0 qtest make[1]: Entering directory '/home/joshua/linux2023/lab0-c' 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 *~) 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 make[1]: Leaving directory '/home/joshua/linux2023/lab0-c' cp qtest /tmp/qtest.83iQ10 chmod u+x /tmp/qtest.83iQ10 sed -i "s/alarm/isnan/g" /tmp/qtest.83iQ10 scripts/driver.py -p /tmp/qtest.83iQ10 --valgrind --- 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, remove_head, reverse and merge --- 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, sort, descend and reverseK --- 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 --- trace-14-perf 6/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 100/100 Test with specific case by running command: scripts/driver.py -p /tmp/qtest.83iQ10 --valgrind -t <tid> ``` ## debug 紀錄 #### 2 / 23 :::info 目前一直卡在 q_insert 的function 並沒有在constant time 處理完畢 除此之外，每一次free佇列都會發生一些問題 (更新) 發先是 q_free 中的safe 沒有初始化 ::: #### 2 / 27 :::info 測試時一直發現 trace - 17 一直報告不是常數時間。同時我也很確定我的實作方法為constant time，而經由閱讀 [KHLEE](https://hackmd.io/@KHLee529/linux2023-lab0) 的實作方法，更改了 dudect/constant.c 以及 dudect/fixture 的計算方法後才得到目前的滿分 :::