---
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
```
Sign in with Wallet
Connect another wallet