2023q1 Homework1 (lab0)

# 2023q1 Homework1 (lab0) contributed by < [LiChiiiii](https://github.com/LiChiiiii/lab0-c) > ## 開發環境 ```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: 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-6700 CPU @ 3.40GHz CPU family: 6 Model: 94 Thread(s) per core: 2 Core(s) per socket: 4 Socket(s): 1 Stepping: 3 CPU max MHz: 4000.0000 CPU min MHz: 800.0000 BogoMIPS: 6799.81 ``` ## 完成 queue.c :::success TOTAL SCORE : 100/100 ::: :::danger 注意書寫規範：中英文間用一個半形空白字元區隔。 :notes: jserv > 已修正 > [name=LiChiiiii] ::: #### `q_new` 利用 `malloc()` 配置記憶體空間，若記憶體配置失敗回傳 `NULL`，成功則使用 `list.h` 中的 `INIT_LIST_HEAD()` 來初始化 `head`。 ```c struct list_head *q_new() { struct list_head *head = malloc(sizeof(*head)); if (!head) return NULL; INIT_LIST_HEAD(head); return head; } ``` #### `q_free` 使用` list.h` 中的 `list_for_each_entry_safe()` 走訪佇列中每個節點，並使用 `q_release_element()` 釋放每一個元素，迴圈做完只會剩下指向佇列的 `l`，最後`free(l)`完成此功能。 :::info `list_for_each_entry_safe()` 會額外使用一個指標 `safe` 來暫存下一次循環的 entry，使得每次在執行 `q_release_element()` 時不會影響迴圈的執行。 ::: ```c void q_free(struct list_head *l) { if(!l) return; element_t *itm=NULL, *is=NULL; list_for_each_entry_safe (itm, is, l, list) { q_release_element(itm); } free(l); } ``` #### `q_insert_head` 先替 `new_itm` （欲新增至佇列的元素）配置一個資料結構為 `element_t` 的記憶體空間。 ```c typedef struct { char *value; struct list_head list; } element_t; ``` 計算 `s` （欲新增至 `new_itm->value` 的字元）大小，並依據計算出的大小配置記憶體空間至 `new_itm->value` ，透過條件式確認配置成功後，利用 `memcpy()` 將 `s` 複製到 `new_itm->value` 中，最後呼叫 `list_add()` 將 `new_itm` 元素加入佇列的第一個。剛開始忘記在判斷配置失敗後要執行 `free(new_itm)` （第11行），導致報錯 `error: Memory leak: new_itm [memleak]` 。 ```c= bool q_insert_head(struct list_head *head, char *s) { if (!head) return false; element_t *new_itm = malloc(sizeof(*new_itm)); if (!new_itm) return false; size_t size = strlen(s) + 1; new_itm->value = malloc(size * sizeof(char)); if (!new_itm->value) { free(new_itm); return false; } memcpy(new_itm->value, s, size); list_add(&new_itm->list, head); return true; } ``` #### `q_insert_tail` 與 **`q_insert_head`** 的思路一樣，將第15行改成 `list_add_tail()` 。 ```c= bool q_insert_tail(struct list_head *head, char *s) { if (!head) return false; element_t *new_itm = malloc(sizeof(*new_itm)); if (!new_itm) return false; size_t size = strlen(s) + 1; new_itm->value = malloc(size * sizeof(char)); if (!new_itm->value) { free(new_itm); return false; } memcpy(new_itm->value, s, size); list_add_tail(&new_itm->list, head); return true; } ``` #### `q_remove_head` 使用 `list_first_entry()` 找到佇列中第一個元素，並透過 `list_del()` 刪除此元素。使用 `strncpy()` 來複製字串至 `sp` 以避免 buffer overflow 的問題，但會產生以下狀況，若來源字元數小於限制複製字元的個數，剩下未填滿的部分會全部補上 '\0'，反之則要手動補 '\0'（第9行）。 ```c= element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize) { if (!head) return NULL; element_t *itm = list_first_entry(head, element_t, list); list_del(&itm->list); if (sp != NULL) { strncpy(sp, itm->value, bufsize - 1); sp[bufsize - 1] = '\0'; } return itm; } ``` #### `q_remove_tail` 與 **`q_remove_head`** 的思路一樣，將第5行改成 `list_last_entry()` 。 ```c= element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize) { if (!head) return NULL; element_t *itm = list_last_entry(head, element_t, list); list_del(&itm->list); if (sp != NULL) { strncpy(sp, itm->value, bufsize - 1); sp[bufsize - 1] = '\0'; } return itm; } ``` #### `q_size` 使用 `list.h` 中的 `list_for_each()` 走訪佇列，紀錄佇列長度。 ```c int q_size(struct list_head *head) { int size = 0; if (!head) return size; struct list_head *itm; list_for_each (itm, head) { size++; } return size; } ``` #### `q_delete_mid` 利用 doubly-linked list 的特性，宣告兩個指標 `front` 和 `rear` 分別**從前向後**和**從後到前**同時移動，直到重疊即可找到 `mid` 並刪除。利用 `front!=rear->prev` 條件式來尋找含偶數個元素的佇列之 `mid` ，利用 `front!=rear` 條件式來尋找含奇數個元素的佇列之 `mid` （第6行）。原本的寫法是先寫 `q_release_element(mid)` ，才接著寫 `list_del(front)` ，這樣會先把 `front` 指向的元素之記憶體空間釋放掉，導致報錯： `Segmentation fault occurred. You dereferenced a NULL or invalid pointerAborted (core dumped)` ```c= bool q_delete_mid(struct list_head *head) { if (!head) return false; struct list_head *front = head->next, *rear = head->prev; while (front != rear->prev && front != rear) { front = front->next; rear = rear->prev; } element_t *mid = list_entry(front, element_t, list); list_del(front); q_release_element(mid); return true; } // https://leetcode.com/problems/delete-the-middle-node-of-a-linked-list/ ``` #### `q_delete_dup` `flag` ：決定當前元素是否為應被刪除的元素利用迴圈比較當前元素 `cur_el` 以及前一個元素 `cur_prev_el` 之值是否相同，若相同則刪除 `cur_prev_el` 並設定 `flag=1` ，若不相同但 `flag=1` 則代表當前元素 `cur_el` 為重複元素中最後一個元素，也就是應被刪除的元素。 ```c bool q_delete_dup(struct list_head *head) { if (!head || list_is_singular(head) || list_empty(head)) return false; int flag = 0; struct list_head *cur, *safe = NULL; list_for_each_safe (cur, safe, head) { if (cur->prev == head) continue; element_t *cur_el = list_entry(cur, element_t, list); element_t *cur_prev_el = list_entry(cur->prev, element_t, list); if (!strcmp(cur_el->value, cur_prev_el->value)) { list_del(cur->prev); q_release_element(cur_prev_el); flag = 1; if (cur == head->prev){ list_del(cur); q_release_element(cur_el); return true; } } else if (flag == 1) { list_del(cur->prev); q_release_element(cur_prev_el); flag = 0; } } return true; } // https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/ ``` #### `q_swap` `flag` ：決定當前元素是否與前一個元素交換若 `flag=0` 則設定 `flag=1`並跳過此元素，若 `flag=1` 則當前元素與前一個元素交換（前一個元素移到當前元素後面）並設定 `flag=0` 。 ```c void q_swap(struct list_head *head) { if (!head || list_is_singular(head) || list_empty(head)) return; int flag = 0; struct list_head *cur, *safe = NULL; list_for_each_safe (cur, safe, head) { if (cur->prev == head || flag == 0) { flag = 1; continue; } else if (flag == 1) { list_move(cur->prev, cur); flag = 0; } } return; } // https://leetcode.com/problems/swap-nodes-in-pairs/ ``` #### `q_reverse` `list_move()` 會先執行 `list_del()` 將當前指向的元素刪除，在執行 `list_add()` 將元素新增至佇列最前端。第 7 行使用 `list_for_each_safe()` 可以允許當前節點從佇列中移除，用 `list_for_each()` 會導致 infinite loop 。 ```c= void q_reverse(struct list_head *head) { if(!head || list_is_singular(head) || list_empty(head)) return; struct list_head *cur , *safe=NULL; list_for_each_safe(cur, safe, head){ list_move(cur, head); } } ``` #### `q_reverseK` 讓指標邊走邊數 k 個元素，到第 k 個元素進行 reverse 。 `cur_prev_k` 存放 `top` 為 1 的元素之記憶體位址，也就是記錄當前元素要進行 reverse時的前 k 個元素之記憶體位址。 :::info 宣告改成 `*cur_prev_k = head->next` 會出現無限迴圈，因為 `cur_prev_k` 會跟著指向的元素做移動，導致 `cur_prev_k` 永遠不會等於 `tmp` ，也就是離不開 while 迴圈。 ::: ```c void q_reverseK(struct list_head *head, int k) { if(!head || list_is_singular(head) || list_empty(head)) return; int top = 0; struct list_head *cur, **cur_prev_k = &(head->next), struct list_head *safe=NULL, *tmp=NULL; list_for_each_safe(cur, safe, head){ top++; if(top%k==0){ tmp = cur; while(*cur_prev_k != tmp){ list_move(tmp->prev, cur); cur = cur->next; } cur_prev_k = &(cur->next); } } // https://leetcode.com/problems/reverse-nodes-in-k-group/ } ``` #### `q_sort` 參考[你所不知道的 c 語言: linked list 和非連續記憶體](https://hackmd.io/@sysprog/c-linked-list#Merge-Sort-%E7%9A%84%E5%AF%A6%E4%BD%9C)、 [Linked List Sort](https://npes87184.github.io/2015-09-12-linkedListSort/) 中提到的 Merge Sort 以及 [seasonwang0905](https://hackmd.io/@seasonwang/B1B0lVqpo) 的程式碼實作。 :::danger 避免張貼完整程式碼，列出關鍵程式碼並闡述你的觀察、推論，和考慮議題。 :notes: jserv > 已修正 > [name=LiChiiiii] ::: 排序實作總共用到三個函式： 1. `merge_two_list()` ：將兩個佇列合併成一個已完成排序的佇列 2. `mergesort()`：將未排序的佇列進行不斷的分割，直到剩一個節點即開始執行`merge_two_list()`，直到遞迴結束。 3. `q_sort()`：先將尚未排序的佇列變成 singly-linked list ，這樣排序過程中就不用維持 doubly-linked list 。等到執行完 `mergesort()` 排序完畢後，再重新連結 prev 即可。 ```c /* Merge two list into one queue */ struct list_head *merge_two_list(struct list_head *l1, struct list_head *l2) { struct list_head *temp = NULL; struct list_head **indirect = &temp; for (struct list_head **node = NULL; l1 && l2; *node = (*node)->next) { element_t *e1 = list_entry(l1, element_t, list); element_t *e2 = list_entry(l2, element_t, list); if (strcmp(e1->value, e2->value) < 0) node = &l1; else node = &l2; *indirect = *node; indirect = &(*indirect)->next; } *indirect = (struct list_head *) ((u_int64_t) l1 | (u_int64_t) l2); return temp; } /* Divide the queue and sort every element */ struct list_head *mergesort(struct list_head *head) { if (!head || !head->next) return head; struct list_head *fast = head, *slow = head; while (fast && fast->next) { fast = fast->next->next; slow = slow->next; } fast = slow; slow->prev->next = NULL; struct list_head *l1 = mergesort(head); struct list_head *l2 = mergesort(fast); return merge_two_list(l1, l2); } /* Sort elements of queue in ascending order */ void q_sort(struct list_head *head) { if (!head || list_empty(head)) return; head->prev->next = NULL; head->next = mergesort(head->next); struct list_head *current = head, *next = head->next; while (next) { next->prev = current; current = next; next = next->next; } current->next = head; head->prev = current; } ``` #### `q_descend` 從 list 尾端向前比較大小，比從 list 前端向後比較大小來的簡單。前者只要反向比較下一個元素小於當前元素即可刪除，後者則是順向比較當前元素之前的所有元素是否小於當前元素。 ```c int q_descend(struct list_head *head) { if (!head || list_is_singular(head) || list_empty(head)) return 0; struct list_head *cur = head->prev; while (cur->prev != head) { element_t *cur_el = list_entry(cur, element_t, list); element_t *cur_prev_el = list_entry(cur->prev, element_t, list); int cmp = strcmp(cur_el->value, cur_prev_el->value); if (cmp > 0) { list_del(cur->prev); q_release_element(cur_prev_el); } else { cur = cur->prev; } } return q_size(head); } // https://leetcode.com/problems/remove-nodes-from-linked-list/ ``` #### `q_merge` 使用 `queue.h` 中定義的資料結構 `queue_contex_t` 來表示每一個queue。 ```c typedef struct { struct list_head *q; struct list_head chain; int size; int id; } queue_contex_t; ``` 透過 `list_for_each_entry()` 查看所有的佇列，並將佇列合併，最後將合併起來的queue做排序。 ```c /* Merge all the queues into one sorted queue, which is in ascending order */ int q_merge(struct list_head *head) { if (!head || list_empty(head)) return 0; else if(list_is_singular(head)) return list_entry(head, queue_contex_t,chain)->size; queue_contex_t *que = list_entry(head->next, queue_contex_t,chain); queue_contex_t *cur_que = NULL; list_for_each_entry(cur_que, head, chain) { if(cur_que == que) continue; list_splice_init(cur_que->q, que->q); que->size = que->size + cur_que->size; cur_que->size = 0; } q_sort(que->q); return que->size; // https://leetcode.com/problems/merge-k-sorted-lists/ } ``` ## 改進 `web` 命令原始程式碼執行 `web` 命令可開啟網頁伺服器，一旦 web_fd > 0 表示成功開啟 web server 。 ```c /* console.c */ static int web_fd; static bool do_web(int argc, char *argv[]) { int port = 9999; if (argc == 2) { if (argv[1][0] >= '0' && argv[1][0] <= '9') port = atoi(argv[1]); } web_fd = web_open(port); if (web_fd > 0) { printf("listen on port %d, fd is %d\n", port, web_fd); use_linenoise = false; } else { perror("ERROR"); exit(web_fd); } return true; } ``` 在 `web.c` 可以看到已經寫好在 web 接收訊息和傳送訊息的處理方式。 ```c /* web.c */ char *web_recv(int fd, struct sockaddr_in *clientaddr) { http_request_t req; parse_request(fd, &req); char *p = req.filename; /* Change '/' to ' ' */ while (*p) { ++p; if (*p == '/') *p = ' '; } char *ret = malloc(strlen(req.filename) + 1); strncpy(ret, req.filename, strlen(req.filename) + 1); return ret; } void web_send(int out_fd, char *buf) { writen(out_fd, buf, strlen(buf)); } ``` 問題在於網頁伺服器開啟後，處理命令列的 `linenoise` 套件無法使用，因此嘗試改寫 `linenoise.c` 用 [select()](https://man7.org/linux/man-pages/man2/select.2.html) 同時處理 stdin 及 socket。在`line_edit` 新增參數 `web_fd` ，當 web_fd != 0 就使用 `select()` 監聽。若從 web 輸入訊息（第33行），則將訊息複製到 buf 中並透過 linenoise 處理命令，同時也傳送 HTTP 回應的 header 訊息給客戶端，表示回應成功，並關閉 socket 。若從命令列輸入訊息（第43行），則保持原本做法處理。 ```c= /* linenoise.c */ static int line_edit(int stdin_fd, int stdout_fd, char *buf, size_t buflen, const char *prompt, int web_fd) { ... while (1) { signed char c; int nread; char seq[5]; if (web_fd) { fd_set set; FD_ZERO(&set); FD_SET(web_fd, &set); FD_SET(stdin_fd, &set); int rv = select(web_fd + 1, &set, NULL, NULL, NULL); struct sockaddr_in clientaddr; socklen_t clientlen = sizeof(clientaddr); int connfd; switch (rv) { case -1: perror("select"); /* an error occurred */ continue; case 0: printf("timeout occurred\n"); /* a timeout occurred */ continue; default: if (FD_ISSET(web_fd, &set)) { FD_CLR(web_fd, &set); connfd = accept(web_fd, (struct sockaddr *) &clientaddr, &clientlen); strncpy(buf, web_recv(connfd, &clientaddr), buflen); char *header = "HTTP/1.1 200 OK\r\nContent-Type: text/plain\r\n\r\n"; web_send(web_connfd, header); close(web_connfd); return strlen(buf); } else if (FD_ISSET(stdin_fd, &set)) { nread = read(l.ifd, &c, 1); if (nread <= 0) return l.len; } break; } } else { nread = read(l.ifd, &c, 1); if (nread <= 0) return l.len; } } ... } ``` > 參考老師的[整合網頁伺服器](https://hackmd.io/@sysprog/linux2023-lab0/%2F%40sysprog%2Flinux2023-lab0-c) ## 實作 `shuffle` 命令利用 Fisher–Yates shuffle 演算法來實作洗牌。 ```c /* queue.c */ void value_swap(struct list_head *node1, struct list_head *node2) { element_t *node1_ele = list_entry(node1, element_t, list); element_t *node2_ele = list_entry(node2, element_t, list); char *temp; temp = node1_ele->value; node1_ele->value = node2_ele->value; node2_ele->value = temp; } void q_shuffle(struct list_head *head) { if (!head || list_is_singular(head) || list_empty(head)) return; struct list_head *last = head->prev; struct list_head *cur = head->next; int len = q_size(head); srand(time(NULL)); while(len) { int i = rand() % len; while(i) { cur = cur->next; i--; } value_swap(cur,last); last = last->prev; cur = head->next; len--; } } ``` 原本 swap 的寫法是透過 `list_move()` 來移動兩個節點位置，但執行 shuffle 時偶爾會失敗，後來才改成交換 value 的方法。 ```c void node_swap(struct list_head *node1, struct list_head *node2) { struct list_head *node1_prev = node1->prev; struct list_head *node2_prev = node2->prev; list_move(node2, node1_prev); list_move(node1, node2_prev); } ``` 除了實作程式碼，還需要在 `qtest.c` 新增命令和執行函式。 ```c ADD_COMMAND(shuffle, "Implement Fisher–Yates shuffle",""); ``` ```c static inline bool do_shuffle(int argc, char *argv[]) { if (argc != 1) { report(1, "%s takes no arguments", argv[0]); return false; } if (!current) { report(3, "Warning: Try to operate null queue"); return false; } error_check(); set_noallocate_mode(true); if (current && exception_setup(true)) q_shuffle(current->q); exception_cancel(); set_noallocate_mode(false); return q_show(3); } ``` ## Address Sanitizer 在 `Makefile` 中發現已定義一個變數稱 `SANITIZER` ，當 `SANITIZER` 變數設置為 1，即可啟用 address sanitizer。 ``` # Enable sanitizer(s) or not ifeq ("$(SANITIZER)","1") # https://github.com/google/sanitizers/wiki/AddressSanitizerFlags CFLAGS += -fsanitize=address -fno-omit-frame-pointer -fno-common LDFLAGS += -fsanitize=address endif ``` 執行下列命令開啟 address sanitizer ，並重新編譯，沒有出現任何關於記憶體之錯誤。 ```shell make clean make SANITIZER=1 make test ``` :::spoiler 執行結果 ```shell $ make test 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, 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 ``` ::: ## Valgrind 執行 `make valgrind` 沒有出現相關問題 :::spoiler 執行結果 ``` $ make valgrind # Explicitly disable sanitizer(s) make clean SANITIZER=0 qtest make[1]: Entering directory '/home/lichi/Documents/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/lichi/Documents/lab0-c' cp qtest /tmp/qtest.J1q9iz chmod u+x /tmp/qtest.J1q9iz sed -i "s/alarm/isnan/g" /tmp/qtest.J1q9iz scripts/driver.py -p /tmp/qtest.J1q9iz --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 ``` ::: ### 使用 Massif 查看記憶體的狀況 ``` valgrind --tool=massif ./qtest -f traces/trace-17-complexity.cmd ``` 以下是 `traces/trace-17-complexity.cmd` 的記憶體使用狀況 ![](https://i.imgur.com/yr2Y1wi.jpg) 在 trace-17 執行了 `q_insert_head()` 、 `q_insert_tail()` 、 `q_remove_head()` 以及 `q_remove_tail()` 四個函式，在圖中的最右邊可以看到，執行結束後記憶體並沒有釋放完全，此部分待確認。 ## Linux 核心原始程式碼的 `lib/list_sort.c ` #### 比較 `lib/list_sort.c` 與自行實作的合併排序演算法差異由於無法新增 `queue.h` 的定義，所以就把 `lib_sort.c` 的程式放進 `qtest.c` ，新增一個 option 來切換 sort 的實作，這樣很快就可以看看自己實作的效能跟 Linux 核心程式碼的差距。在 `qtest.c` 當中把 `do_sort()` 函式的部分改為這樣： ```c if (exception_setup(true)) { if (is_enable_linux_sort()) { q_sort_linux(l_meta.l); } else { q_sort(l_meta.l); } } ``` 參考 [komark06](https://hackmd.io/@komark06/SyCUIEYpj#引入-liblist_sortc) 對 `list_sort.c` 的修改方法，將程式放入 `qtest.c` 執行。接著利用以下的 command 來比較排序時間： ``` option fail 0 option malloc 0 new ih dolphin 1000000 it gerbil 1000000 reverseK 100 time sort option linux_qsort 1 new ih dolphin 1000000 it gerbil 1000000 reverseK 100 time sort ``` :::warning 執行 `list_sort.c` 會出現 `Segmentation fault occurred.` ，應是引入程式碼時有錯誤，待處理。 ::: ## 研讀論文〈Dude, is my code constant time?〉論文中提出了工具 **dudect** ，可以用來檢測一段程式是否 constant time 執行。測試方式主要分成三個步驟： 1. Measure execution time : 輸入**固定資料**和**隨機資料**來量測目標函式耗費的時間。每次隨機選擇一種類型資料並重複執行得到量測結果。 2. Apply post-processing：大於某個 threshold 的執行時間不列入統計檢定。 3. Apply statistical test：論文中提及兩個檢驗方式 `t-test` （採用 [Welch's t-test](https://en.wikipedia.org/wiki/Welch%27s_t-test) ）和 `Non-parametric tests` :::info :stars: **t-test** t-test 是一個常用來協助判斷**比較兩組資料是否具有顯著差異**的統計方法之一。在這裡我們試圖**反證兩組資料時間分佈相等**，也就是說當 t-test 拒絕假說（無法證明平均值的差異），表示執行時間為 constant time。 ::: ### 程式實作原理在 lab0-c 中，當 `simulation` 開啟後會將 `is_xx_xx_const()` 作為目標函式進行時間複雜度測試 `test_const()` $\rightarrow$ `doit()` ，並根據論文中的三個步驟實作： 1. `measure()` 和 `differentiate()`：計算目標函式執行時間 2. `update_statistics()`：處理取得的資料 3. `report()`：利用 [Welch's t-test](https://en.wikipedia.org/wiki/Welch%27s_t-test) 驗證目標函式是否為 constant time ```c /* dudect/fixture.c */ static bool doit(int mode) { ... bool ret = measure(before_ticks, after_ticks, input_data, mode); differentiate(exec_times, before_ticks, after_ticks); update_statistics(exec_times, classes); ret &= report(); ... return ret; } ``` 在 `measure()` 函式發現計算過程中**直接減掉要做刪除的次數**（第10行），但測試流程應該要是**紀錄所有資料再去做第二步驟的資料處理**。 ```c /* dudect/constant.h */ #define N_MEASURES 150 #define DROP_SIZE 20 ``` ```c= /* dudect/constant.c */ bool measure(int64_t *before_ticks, int64_t *after_ticks, uint8_t *input_data, int mode) { ... switch (mode) { case DUT(insert_head): for (size_t i = DROP_SIZE; i < N_MEASURES - DROP_SIZE; i++) { char *s = get_random_string(); dut_new(); dut_insert_head( get_random_string(), *(uint16_t *) (input_data + i * CHUNK_SIZE) % 10000); int before_size = q_size(l); before_ticks[i] = cpucycles(); dut_insert_head(s, 1); after_ticks[i] = cpucycles(); int after_size = q_size(l); dut_free(); if (before_size != after_size - 1) return false; } break; ... ``` 因此將該部分改成做完 `N_MEASURES` 次的紀錄後進行排序再刪除前後各 `DROP_SIZE` 個資料點，即可每次皆通過 `trace-17-complexity` 的測試。 > 參考 [KHLee529](https://hackmd.io/@KHLee529/linux2023-lab0 ) 解決方法 ## Debug 紀錄 * 編譯時出現以下錯誤訊息 ```! gcc: internal compiler error: Segmentation fault signal terminated program as Please submit a full bug report, with preprocessed source if appropriate. See <file:///usr/share/doc/gcc-11/README.Bugs> for instructions. make: *** [Makefile:54: qtest.o] Error 4 ``` > 1. 檢查gcc版本 > 2. 檢查可用的記憶體空間 > 3. 重新啟動主機

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.