2022q1 Homework1 (lab0)

--- tags: Linux --- # 2022q1 Homework1 (lab0) contributed by < `LJP-TW` > # 實驗環境 ```shell $ gcc --version gcc (Debian 10.2.1-6) 10.2.1 20210110 Copyright (C) 2020 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: 45 bits physical, 48 bits virtual Byte Order: Little Endian CPU(s): 2 On-line CPU(s) list: 0,1 Vendor ID: AuthenticAMD Model name: AMD Ryzen 7 PRO 4750U with Radeon Graphics CPU family: 23 Model: 96 Thread(s) per core: 1 Core(s) per socket: 1 Socket(s): 2 Stepping: 1 BogoMIPS: 3393.62 ``` # 作業要求 ## 實作 queue 嘗試盡量使用 Linux 核心風格的鏈結串列 API 進行各函數的實作。 ### q_new 檢查是否能分配空間，並且做 `list_head` 的初始化。 ```c struct list_head *q_new() { struct list_head *head; head = malloc(sizeof(struct list_head)); if (!head) { return NULL; } INIT_LIST_HEAD(head); return head; } ``` ### q_free 釋放整條 queue 所占用的記憶體，由於都要歸還記憶體了，已經無需再將 element 從 queue 中移除鏈結。 ```c void q_free(struct list_head *l) { if (!l) { return; } element_t *entry, *safe; list_for_each_entry_safe (entry, safe, l, list) { q_release_element(entry); } free(l); } ``` ### q_insert_head 從 queue 的頭部新增節點，檢查是否能正常分配記憶體，字串長度需要為了 NULL byte 預留空間。 ```c bool q_insert_head(struct list_head *head, char *s) { element_t *element; int len; if (!head) { return false; } element = malloc(sizeof(element_t)); if (!element) { return false; } len = strlen(s) + 1; element->value = malloc(sizeof(char) * len); if (!element->value) { free(element); return false; } strncpy(element->value, s, len); list_add(&element->list, head); return true; } ``` ### q_insert_tail 與 `q_insert_head` 類似。 ```c bool q_insert_tail(struct list_head *head, char *s) { element_t *element; int len; if (!head) { return false; } element = malloc(sizeof(element_t)); if (!element) { return false; } len = strlen(s) + 1; element->value = malloc(sizeof(char) * len); if (!element->value) { free(element); return false; } strncpy(element->value, s, len); list_add_tail(&element->list, head); return true; } ``` ### q_remove_head 從 queue 的頭部移除一個節點，複製字串到 `sp` 時要預留 NULL byte 的空間。 ```c element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize) { if (!head || list_empty(head)) { return NULL; } element_t *first = list_first_entry(head, element_t, list); list_del_init(&first->list); if (sp) { char *val = first->value; char c; while (bufsize > 1 && (c = *val)) { *sp = c; sp++; val++; bufsize--; } *sp = 0; } return first; } ``` ### q_remove_tail 與 `q_remove_head` 類似。 ```c element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize) { if (!head || list_empty(head)) { return NULL; } element_t *last = list_last_entry(head, element_t, list); list_del_init(&last->list); if (sp) { char *val = last->value; char c; while (bufsize > 1 && (c = *val)) { *sp = c; sp++; val++; bufsize--; } *sp = 0; } return last; } ``` ### q_release_element 沒有做改動。 ```c void q_release_element(element_t *e) { free(e->value); free(e); } ``` ### q_size 需要走過 queue 計算長度，時間複雜度為 `O(n)`。 ```c int q_size(struct list_head *head) { if (!head || list_empty(head)) { return 0; } struct list_head *node; int len = 0; list_for_each (node, head) { len++; } return len; } ``` ### q_delete_mid 用兩個 pointer 走過 queue，`curr` 走訪速度為 `mid` 兩倍，因此當 `curr` 到達 queue 的結尾時，`mid` 自然是在 queue 的中間，找到 `mid` 後刪除該節點。 ```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 *curr, *mid; element_t *element; mid = curr = head->next; while (curr != head && curr->next != head) { curr = curr->next->next; mid = mid->next; } list_del(mid); element = list_entry(mid, element_t, list); q_release_element(element); return true; } ``` ### q_delete_dup 呼叫此函式前，queue 已經排序完畢，因此走訪過程中，只需要判斷下個節點的值是否與當前節點相同，作為是否要刪除節點的依據。在 `do` `while` 後，還要再刪除 `currelm`，但這個寫法不夠簡潔，還有改善空間。 ```c bool q_delete_dup(struct list_head *head) { // https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/ if (!head) { return false; } if (list_empty(head) || list_is_singular(head)) { return true; } struct list_head *curr = head->next; element_t *currelm, *nextelm; while (curr != head && curr->next != head) { currelm = list_entry(curr, element_t, list); nextelm = list_entry(curr->next, element_t, list); if (!strcmp(currelm->value, nextelm->value)) { do { curr = curr->next; list_del(&currelm->list); q_release_element(currelm); currelm = nextelm; if (curr->next == head) { break; } nextelm = list_entry(curr->next, element_t, list); } while (!strcmp(currelm->value, nextelm->value)); curr = curr->next; list_del(&currelm->list); q_release_element(currelm); } else { curr = curr->next; } } return true; } ``` ### q_swap 每經過兩個節點就交換兩者在 queue 中的順序。`list.h` 沒有與交換節點相關的工具能夠使用，或許能夠增加相關工具 macro / function。 ```c void q_swap(struct list_head *head) { // https://leetcode.com/problems/swap-nodes-in-pairs/ if (!head || list_empty(head) || list_is_singular(head)) { return; } struct list_head *peer, *curr; curr = head->next; while (curr != head && curr->next != head) { peer = curr->next; curr->next = peer->next; curr->next->prev = curr; peer->prev = curr->prev; peer->prev->next = peer; peer->next = curr; curr->prev = peer; curr = curr->next; } } ``` ### q_reverse 將整個 queue 的順序倒轉，只要交換每個節點 (包含 `head`) 的 `prev` 和 `next` 即可。 ```c void q_reverse(struct list_head *head) { if (!head || list_empty(head) || list_is_singular(head)) { return; } struct list_head *node, *safe, *tmp; list_for_each_safe (node, safe, head) { tmp = node->next; node->next = node->prev; node->prev = tmp; } tmp = head->next; head->next = head->prev; head->prev = tmp; } ``` :::warning TODO: 針對上方的若干操作，提取出可共用的 inline function :notes: jserv ::: ### q_sort 使用 merge sort 進行排序，先將 doubly-linked list 的 `prev` 和 `next` 指標拆開來變成兩個 singly-linked list，以 `next` 組成的 singly-linked list 用來串接排序好的節點，形成一個個獨立排序好的 sublists，再以 `prev` 組成的 singly-linked list 串接每一個 sublists，即可在不額外配置記憶體的情況下完成 merge sort。 ```c static void merge(struct list_head **chain, struct list_head *a, struct list_head *b) { struct list_head **tail = chain; while (a && b) { element_t *alist = list_entry(a, element_t, list); element_t *blist = list_entry(b, element_t, list); if (strcmp(alist->value, blist->value) < 0) { *tail = a; a = a->next; } else { *tail = b; b = b->next; } tail = &(*tail)->next; } if (a) { *tail = a; } else if (b) { *tail = b; } } /* * 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. */ void q_sort(struct list_head *head) { if (!head || list_empty(head) || list_is_singular(head)) { return; } struct list_head *list = head->next; struct list_head *sublist = NULL, *tmp, *currsub; // Let next chain become to singly linked list head->prev->next = NULL; // Divide singly linked list. Use prev chain to link each sublists while (list) { tmp = list->next; list->next = NULL; list->prev = sublist; sublist = list; list = tmp; } // Merge sublists while (sublist->prev) { struct list_head **chain; currsub = sublist; chain = &sublist; while (currsub && currsub->prev) { tmp = currsub->prev->prev; merge(chain, currsub, currsub->prev); chain = &(*chain)->prev; currsub = tmp; } *chain = currsub; } // Fix doubly linked list head->next = sublist; tmp = head; while (sublist) { sublist->prev = tmp; tmp = sublist; sublist = sublist->next; } head->prev = tmp; tmp->next = head; } ``` ## 在 qtest 實作命令 shuffle 首先先看一下要如何增加一個命令，在 `qtest.c` 搜尋 `ih`，試圖從 `ih` 命令怎麼實作的下手，可以看到有 `do_ih()` 函數: ```c static bool do_ih(int argc, char *argv[]) { ... } ``` 以及在 `console_init()` 中大量使用 `ADD_COMMAND`: ```c ADD_COMMAND( ih, " str [n] | Insert string str at head of queue n times. " "Generate random string(s) if str equals RAND. (default: n == 1)"); ``` 檢查 `ADD_COMMAND` macro，位於 `console.h`: ```c /* Add a new command */ void add_cmd(char *name, cmd_function operation, char *documentation); #define ADD_COMMAND(cmd, msg) add_cmd(#cmd, do_##cmd, msg) ``` :::warning command 是「命令」、instruction 是「指令」，請查詢英語辭典 :notes: jserv ::: `add_cmd` 會在命令列表 `cmd_list` 中添加新命令，明白要新增一條新命令 `shuffle` 則要實作 `do_shuffle`，並在 `console_init()` 替新命令加上 `ADD_COMMAND`。在查看 `swap`、`reverse` 命令的實作時，發現在呼叫到主要邏輯 `q_swap`、`q_reverse` 前後都有特定的函數呼叫: ```c set_noallocate_mode(true); if (exception_setup(true)) q_reverse(l_meta.l); exception_cancel(); set_noallocate_mode(false); ``` 在閱讀了 [K01: lab0 - Signal 處理和應用](https://hackmd.io/dPYu4WH8TuqXnAJvfxm-JA?view#Signal-%E8%99%95%E7%90%86%E5%92%8C%E6%87%89%E7%94%A8)後明白這部分是設定發生 exception 時的處理方式，這邊實作 `shuffle` 時也可將主要邏輯以 `set_noallocate_mode` 和 `exception_xxxx` 包住。 `shuffle` 主要邏輯: ```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: Calling shuffle on null queue"); return false; } set_noallocate_mode(true); if (exception_setup(true)) { // Fisher–Yates shuffle algorithm if (l_meta.size > 1) { int max = l_meta.size; int curr_idx = 1; // 1-based indexing struct list_head *curr = l_meta.l->next, *tail = l_meta.l->prev, *tmpcurr; while (max != 1) { int r = rand() % max + 1; // Find r-th node while (curr_idx < r) { curr = curr->next; curr_idx++; } while (curr_idx > r) { curr = curr->prev; curr_idx--; } // Put r-th node to the tail if (curr == tail) { tail = tail->prev; // curr will get updated at next round, we don't need // to update it here. } else { tmpcurr = curr->next; curr->next->prev = curr->prev; curr->prev->next = curr->next; tail->next->prev = curr; curr->next = tail->next; tail->next = curr; curr->prev = tail; curr = tmpcurr; } max--; } } } exception_cancel(); set_noallocate_mode(false); show_queue(3); return !error_check(); } ``` 新增命令: ```c static void console_init() { ... ADD_COMMAND(shuffle, " | Use Fisher–Yates shuffle algorithm to " "shuffle all nodes in queue"); ... } ``` ## 在 qtest 實作命令 web 提供命令 `web`，並可以用參數指定 listen port，預設 port 為 9999: ```c ADD_COMMAND(web, " [port] | Host a web server (default: port == 9999)"); ``` 使用範例可以用 `curl` 進行測試: ``` # curl -v <SERVER>:<PORT>/<COMMAND>[/<ARGUMENT>][/<ARGUMENT>]... curl -v localhost:9999/it/1 ``` 新增了 `web.h` 和 `web.c`，將從 [tiny-web-server](https://github.com/7890/tiny-web-server) 的主要程式碼放置於此。新增檔案後需要修改 `Makefile`: ``` OBJS := qtest.o report.o console.o harness.o queue.o \ random.o dudect/constant.o dudect/fixture.o dudect/ttest.o \ - linenoise.o + linenoise.o web.o ``` 值得一提的是，在 `process()` 尾端要另外配置記憶體，並複製字串的部分如下: ```c char *process(int fd, struct sockaddr_in *clientaddr) { ... char *ret = malloc(strlen(req.filename) + 1); strncpy(ret, req.filename, strlen(req.filename) + 1); printf("[Web] p: %s\n", p); return ret; } ``` 而 `req.filename` 的設定來自於 `parse_request()`: ```c static void parse_request(int fd, http_request *req) { ... url_decode(filename, req->filename, MAXLINE); } ``` 這邊最長能往 `req->filename` 寫入 `MAXLINE` 個字，也就是 1024，而 `req` 為 `http_request` 結構，其原始定義如下: ```c typedef struct { char filename[512]; off_t offset; /* for support Range */ size_t end; } http_request; ``` `req` 為 `process()` 的區域變數，這就導致了有 stack-based buffer overflow 的漏洞，目前修正方式是將 `http_request` 定義方式改成如下: ```c typedef struct { char filename[MAXLINE]; off_t offset; /* for support Range */ size_t end; } http_request; ``` 在 `qtest.c` 新增 `do_web()`: ```c static bool do_web(int argc, char *argv[]) { int port; if (argc > 2) { report(1, "%s needs 0-1 argument", argv[0]); return false; } else if (argc == 2) { port = atoi(argv[1]); } else { // Default port number is 9999 port = 9999; } // Initialize server socket web_sock = open_listenfd(port); if (web_sock > 0) { report(3, "listen on port %d, fd is %d\n", port, web_sock); } else { perror("ERROR"); return false; } return true; } ``` 參照 [K01: lab0 - 整合 tiny-web-server](https://hackmd.io/dPYu4WH8TuqXnAJvfxm-JA#%E6%95%B4%E5%90%88-tiny-web-server) 的說明進行 `run_console()` 和 `cmd_select()` 的修改。首先是 `run_console()`，當 web server 開啟時，則改成通過 `cmd_select()` 進行輸入的選擇: ```c if (!has_infile) { char *cmdline; - while ((cmdline = linenoise(prompt)) != NULL) { + + while (web_sock <= 0 && (cmdline = linenoise(prompt)) != NULL) { interpret_cmd(cmdline); linenoiseHistoryAdd(cmdline); /* Add to the history. */ linenoiseHistorySave(HISTORY_FILE); /* Save the history on disk. */ linenoiseFree(cmdline); } + + if (web_sock) { + while (!cmd_done()) { + cmd_select(0, NULL, NULL, NULL, NULL); + } + } } else { - while (!cmd_done()) + while (!cmd_done()) { cmd_select(0, NULL, NULL, NULL, NULL); + } } ``` `cmd_select()` 當 server socket 有輸入時則要接收連線並處理: ```c /* Commandline input available */ FD_CLR(infd, readfds); result--; - if (has_infile) { - char *cmdline; - cmdline = readline(); + if (has_infile || web_sock) { + char *cmdline = readline(); if (cmdline) interpret_cmd(cmdline); } + } else if (readfds && FD_ISSET(web_sock, readfds)) { + FD_CLR(web_sock, readfds); + result--; + + int connfd; + struct sockaddr_in clientaddr; + socklen_t clientlen = sizeof(clientaddr); + connfd = accept(web_sock, (SA *) &clientaddr, &clientlen); + + char *p = process(connfd, &clientaddr); + if (p) + interpret_cmd(p); + free(p); + close(connfd); } + return result; } ``` 使用結果 (`qtest`): ``` ➜ lab0-c git:(master) ✗ ./qtest cmd> option echo 0 cmd> new l = [] cmd> web listen on port 9999, fd is 3 cmd> accept request, fd is 4, pid is 18350 127.0.0.1:34124 200 - 'it 1' (text/plain) l = [1] cmd> accept request, fd is 4, pid is 18350 127.0.0.1:34128 200 - 'it 2' (text/plain) l = [1 2] cmd> accept request, fd is 4, pid is 18350 127.0.0.1:34132 200 - 'it 3' (text/plain) l = [1 2 3] cmd> accept request, fd is 4, pid is 18350 127.0.0.1:34136 200 - 'it 4' (text/plain) l = [1 2 3 4] cmd> accept request, fd is 4, pid is 18350 127.0.0.1:34140 200 - 'it 5' (text/plain) l = [1 2 3 4 5] cmd> accept request, fd is 4, pid is 18350 127.0.0.1:34144 200 - 'shuffle' (text/plain) l = [4 1 3 5 2] cmd> sort l = [1 2 3 4 5] cmd> accept request, fd is 4, pid is 18350 127.0.0.1:34148 200 - 'free' (text/plain) l = NULL cmd> ``` Client 端: ``` ➜ lab0-c git:(master) ✗ curl localhost:9999/it/1 curl: (52) Empty reply from server ➜ lab0-c git:(master) ✗ curl localhost:9999/it/2 curl: (52) Empty reply from server ➜ lab0-c git:(master) ✗ curl localhost:9999/it/3 curl: (52) Empty reply from server ➜ lab0-c git:(master) ✗ curl localhost:9999/it/4 curl: (52) Empty reply from server ➜ lab0-c git:(master) ✗ curl localhost:9999/it/5 curl: (52) Empty reply from server ➜ lab0-c git:(master) ✗ curl localhost:9999/shuffle curl: (52) Empty reply from server ➜ lab0-c git:(master) ✗ curl localhost:9999/free curl: (52) Empty reply from server ➜ lab0-c git:(master) ✗ ``` # 開發過程 ## list.h 觀察 `lab0-c` 中的 [list.h](https://github.com/sysprog21/lab0-c/blob/master/list.h)，與 Linux source code 中的 [include/linux/list.h](https://elixir.bootlin.com/linux/v4.1/source/include/linux/list.h) 很像。先閱讀了一下此檔案，一方面看是否有能派上用場的工具，一方面先詳讀每個工具以避免實作時錯誤使用。 ### container_of ```c #ifndef container_of #ifdef __LIST_HAVE_TYPEOF #define container_of(ptr, type, member) \ __extension__({ \ const __typeof__(((type *) 0)->member) *__pmember = (ptr); \ (type *) ((char *) __pmember - offsetof(type, member)); \ }) #else #define container_of(ptr, type, member) \ ((type *) ((char *) (ptr) -offsetof(type, member))) #endif #endif ``` 為何要寫 `__typeof__` 在 [6.7 Referring to a Type with typeof](https://gcc.gnu.org/onlinedocs/gcc/Typeof.html) 提到: > If you are writing a header file that must work when included in ISO C programs, write **\_\_typeof__** instead of typeof. 但這邊我真正的疑問是為何要分成兩種做法，實際使用兩者，編譯成執行檔，查看組語： ```c #include <stdio.h> #include <stddef.h> typedef struct { int a; int b; } test; #define container_of(ptr, type, member) \ ((type *) ((char *) (ptr) - offsetof(type, member))) #define gnu_container_of(ptr, type, member) \ __extension__({ \ const __typeof__(((type *) 0)->member) *__pmember = (ptr); \ (type *) ((char *) __pmember - offsetof(type, member)); \ }) int main() { test instance; test* ptr = &instance; printf("instance : %p\n", &instance); printf("container_of : %p\n", container_of(&(ptr->b), test, b)); printf("gnu_container_of: %p\n", gnu_container_of(&(ptr->b), test, b)); } ``` 組合語言: ```c 0x000055555555513d <+8>: lea rax,[rbp-0x18] 0x0000555555555141 <+12>: mov QWORD PTR [rbp-0x8],rax 0x0000555555555145 <+16>: lea rax,[rbp-0x18] 0x0000555555555149 <+20>: mov rsi,rax 0x000055555555514c <+23>: lea rdi,[rip+0xeb1] # 0x555555556004 0x0000555555555153 <+30>: mov eax,0x0 0x0000555555555158 <+35>: call 0x555555555030 <printf@plt> // 取出 ptr 0x000055555555515d <+40>: mov rax,QWORD PTR [rbp-0x8] // &(ptr->b) 0x0000555555555161 <+44>: add rax,0x4 // 減去 offsetof(test, b) 0x0000555555555165 <+48>: sub rax,0x4 0x0000555555555169 <+52>: mov rsi,rax 0x000055555555516c <+55>: lea rdi,[rip+0xea7] # 0x55555555601a 0x0000555555555173 <+62>: mov eax,0x0 0x0000555555555178 <+67>: call 0x555555555030 <printf@plt> // 取出 ptr 0x000055555555517d <+72>: mov rax,QWORD PTR [rbp-0x8] // &(ptr->b) 0x0000555555555181 <+76>: add rax,0x4 // 儲存 __pmember 0x0000555555555185 <+80>: mov QWORD PTR [rbp-0x10],rax // 取出 __pmember 0x0000555555555189 <+84>: mov rax,QWORD PTR [rbp-0x10] // 將 __pmember 減去 offsetof(test, b) 0x000055555555518d <+88>: sub rax,0x4 0x0000555555555191 <+92>: mov rsi,rax 0x0000555555555194 <+95>: lea rdi,[rip+0xe95] # 0x555555556030 0x000055555555519b <+102>: mov eax,0x0 0x00005555555551a0 <+107>: call 0x555555555030 <printf@plt> ``` 在 [6.48 Alternate Keywords](https://gcc.gnu.org/onlinedocs/gcc/Alternate-Keywords.html) 中提到，在使用 `-ansi` 或 `-std` 的情況下，`asm`、`inline`、`typeof` 這些關鍵字不支援，解法是需要在這些關鍵字前後加上雙底線 `__`。 `typeof` 為編譯器提供的功能，而非原本就在 C specs 中的關鍵字，因此使用 `typeof` 要看你用的編譯器有沒有支援，而 `__typeof__` 為 GNU gcc 提供的功能，在其他編譯器可能沒有，這種情況下可以用 macro `__GNUC__` 來判別編譯器是否為 GNU gcc，如下例子: ```c #ifndef __GNUC__ #define __typeof__ typeof #endif ``` 但以上例子成立的前提是你使用的別款編譯器要支援 `typeof`。回過頭來解釋 `container_of`，裡面用到的 `offsetof` 就有在 C specs 中，所以其一邊的定義是用了 GNU gcc 功能，一邊則是完全遵守 C specs，但似乎還是沒解釋到為何不單純用遵守 C specs 的定義就好。 ### list_entry ```c #define list_entry(node, type, member) container_of(node, type, member) ``` 在 `qtest.c` 中的使用範例，可以直接從 `element_t` 的 `list` 反推取得 `element_t` 的位址: ```c element_t *next_item; next_item = list_entry(item->list.next, element_t, list); ``` ```c char *cur_inserts = list_entry(l_meta.l->prev, element_t, list)->value; ``` 從以上範例也可觀察到，`element_t` 中的 `list`，不管是 `prev` 或 `next` 都應該指向到 `element_t` 中的 `list`。 ### list_del ```c static inline void list_del(struct list_head *node) { struct list_head *next = node->next; struct list_head *prev = node->prev; next->prev = prev; prev->next = next; #ifdef LIST_POISONING node->prev = (struct list_head *) (0x00100100); node->next = (struct list_head *) (0x00200200); #endif } ``` 若有啟用 `LIST_POISONING`，則可以防止被移出 list 的 node 的 `prev` 和 `next` 仍然指向有效的 node，進而防止類似 Use-After-Free 的攻擊。 ### list_splice ```c static inline void list_splice(struct list_head *list, struct list_head *head) { struct list_head *head_first = head->next; struct list_head *list_first = list->next; struct list_head *list_last = list->prev; if (list_empty(list)) return; head->next = list_first; list_first->prev = head; list_last->next = head_first; head_first->prev = list_last; } ``` 將 list 中的 node 加到 head 的起頭，隨後若要再使用 list 需要重新初始化。 ### list_for_each_entry_safe ```c /** * list_for_each_entry_safe - iterate over list entries and allow deletes * @entry: pointer used as iterator * @safe: @type pointer used to store info for next entry in list * @head: pointer to the head of the list * @member: name of the list_head member variable in struct type of @entry * * The current node (iterator) is allowed to be removed from the list. Any * other modifications to the the list will cause undefined behavior. * * FIXME: remove dependency of __typeof__ extension */ #define list_for_each_entry_safe(entry, safe, head, member) \ for (entry = list_entry((head)->next, __typeof__(*entry), member), \ safe = list_entry(entry->member.next, __typeof__(*entry), member); \ &entry->member != (head); entry = safe, \ safe = list_entry(safe->member.next, __typeof__(*entry), member)) ``` 迴圈經過所有在 list 中的結構 entry 本身，而非用來連結的 pointer。但是定義中還是使用到了 GNU gcc 的額外功能 `__typeof__`，所以才註解了 `FIXME: remove dependency of __typeof__ extension`。 ## list_sort.c [linux/lib/list_sort.c 部分程式碼](https://github.com/torvalds/linux/blob/master/lib/list_sort.c): ```c __attribute__((nonnull(2,3))) 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); ... } ``` 這邊非常巧妙，可以使得 pending lists 滿足幾個假設: 1. 每個 pending list size 都為 $2^k$ 2. 每種 size 的 pending list 個數為 0 ~ 2 3. 較小 size 的 pending list 位置會比較靠前 `pending` 以 `prev` 連結成一個 singly linked list，每個 `prev` 指向的是一個 size $2^k$ sublists，等待著被合併。以下表格逐步說明 count 增長時，pending lists 內部中各個 sublists 的變化，每一個數字表示一個 sublist size，寫在越後面的表示是在 `pending` 這張 singly linked list 越前面的位置: | count | pending lists | | -------- | -------- | | 0b0 | NULL | | 0b1 | 1 | | 0b10 | $2^1$ | | 0b11 | $2^1$, 1 | | 0b100 | $2^1$, $2^1$ | | 0b101 | $2^2$, 1 | | 0b110 | $2^2$, $2^1$ | | 0b111 | $2^2$, $2^1$, 1 | | 0b1000 | $2^2$, $2^1$, $2^1$ | | 0b1001 | $2^2$, $2^2$, 1 | | 0b1010 | $2^2$, $2^2$, $2^1$ | | 0b1011 | $2^3$, $2^1$, 1 | | 0b1100 | $2^3$, $2^1$, $2^1$ | | 0b1101 | $2^3$, $2^2$, 1 | | 0b1110 | $2^3$, $2^2$, $2^1$ | | 0b1111 | $2^3$, $2^2$, $2^1$, 1 | 再對比自己的實作，發現自己的實作問題是在 worst case 的情況下，在 merge 時兩邊 list 的 size 沒有限制，導致單次 merge 最差的時間複雜度會是 $O(n)$；反過來看 Linux 的實作方式，最差的狀況兩邊 list size 為 $2^{(k+1)}$ 和 $2^k$，單次 merge 過慢的發生機率就會顯著下降。 ## trace-17-complexity 在完成 queue 的實作後首次推上 github，[CI 的結果](https://github.com/LJP-TW/lab0-c/actions/runs/1880381686/attempts/1)不如預期。在本地端測試時，主要是 trace-14-perf 一直過不了；但 CI 的結果反而是卡在 trace-17-complexity，而這部分是測試 `q_insert_tail`、`q_insert_head`、`q_remove_tail`、`q_remove_head` 是否為 constant time，這我反而很有信心應該要通過。錯誤訊息中有大量的 `not enough measurements` 訊息，可能與之相關。[第二次重新跑一次 CI](https://github.com/LJP-TW/lab0-c/actions/runs/1880381686/attempts/2) 就通過了，需要再研究為何會有這樣的結果發生。 :::warning TODO: 對照閱讀論文 :notes: jserv ::: ``` meas: 0.01 M, not enough measurements (430 still to go). meas: 0.01 M, not enough measurements (320 still to go). meas: 0.01 M, not enough measurements (210 still to go). meas: 0.01 M, not enough measurements (100 still to go). meas: 0.01 M, max t: +62.42, max tau: 6.24e-01, (5/tau)^2: 6.42e+01. ERROR: Probably not constant time --- Trace Points +++ TESTING trace trace-01-ops: --- trace-01-ops 5/5 +++ TESTING trace trace-02-ops: --- trace-02-ops 6/6 +++ TESTING trace trace-03-ops: --- trace-03-ops 6/6 +++ TESTING trace trace-04-ops: --- trace-04-ops 6/6 +++ TESTING trace trace-05-ops: --- trace-05-ops 6/6 +++ TESTING trace trace-06-ops: --- trace-06-ops 6/6 +++ TESTING trace trace-07-string: --- trace-07-string 6/6 +++ TESTING trace trace-08-robust: --- trace-08-robust 6/6 +++ TESTING trace trace-09-robust: --- trace-09-robust 6/6 +++ TESTING trace trace-10-robust: --- trace-10-robust 6/6 +++ TESTING trace trace-11-malloc: --- trace-11-malloc 6/6 +++ TESTING trace trace-12-malloc: --- trace-12-malloc 6/6 +++ TESTING trace trace-13-malloc: --- trace-13-malloc 6/6 +++ TESTING trace trace-14-perf: --- trace-14-perf 6/6 +++ TESTING trace trace-15-perf: --- trace-15-perf 6/6 +++ TESTING trace trace-16-perf: --- trace-16-perf 6/6 +++ TESTING trace trace-17-complexity: --- trace-17-complexity 0/5 --- TOTAL 95/100 make: *** [Makefile:56: test] Error 1 ```

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.