2022q1 Homework1 (lab0)

contributed by < LJP-TW >

實驗環境

$ 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 的初始化。

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 中移除鏈結。

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 預留空間。

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 類似。

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 的空間。

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 類似。

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

沒有做改動。

void q_release_element(element_t *e)
{
    free(e->value);
    free(e);
}

q_size

需要走過 queue 計算長度，時間複雜度為 O(n)。

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 後刪除該節點。

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，但這個寫法不夠簡潔，還有改善空間。

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。

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 即可。

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;
}

TODO: 針對上方的若干操作，提取出可共用的 inline function

Image Not Showing Possible Reasons

The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported

Learn More →

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。

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() 函數:

static bool do_ih(int argc, char *argv[])
{
    ...
}

以及在 console_init() 中大量使用 ADD_COMMAND:

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:

/* 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)

command 是「命令」、instruction 是「指令」，請查詢英語辭典

Image Not Showing Possible Reasons

The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported

Learn More →

jserv

add_cmd 會在命令列表 cmd_list 中添加新命令，明白要新增一條新命令 shuffle 則要實作 do_shuffle，並在 console_init() 替新命令加上 ADD_COMMAND。

在查看 swap、reverse 命令的實作時，發現在呼叫到主要邏輯 q_swap、q_reverse 前後都有特定的函數呼叫:

set_noallocate_mode(true);
if (exception_setup(true))
    q_reverse(l_meta.l);
exception_cancel();

set_noallocate_mode(false);

在閱讀了 K01: lab0 - Signal 處理和應用後明白這部分是設定發生 exception 時的處理方式，這邊實作 shuffle 時也可將主要邏輯以 set_noallocate_mode 和 exception_xxxx 包住。

shuffle 主要邏輯:

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();
}

新增命令:

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:

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 的主要程式碼放置於此。新增檔案後需要修改 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() 尾端要另外配置記憶體，並複製字串的部分如下:

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():

static void parse_request(int fd, http_request *req)
{
    ...
    url_decode(filename, req->filename, MAXLINE);
}

這邊最長能往 req->filename 寫入 MAXLINE 個字，也就是 1024，而 req 為 http_request 結構，其原始定義如下:

typedef struct {
    char filename[512];
    off_t offset; /* for support Range */
    size_t end;
} http_request;

req 為 process() 的區域變數，這就導致了有 stack-based buffer overflow 的漏洞，目前修正方式是將 http_request 定義方式改成如下:

typedef struct {
    char filename[MAXLINE];
    off_t offset; /* for support Range */
    size_t end;
} http_request;

在 qtest.c 新增 do_web():

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 的說明進行 run_console() 和 cmd_select() 的修改。

首先是 run_console()，當 web server 開啟時，則改成通過 cmd_select() 進行輸入的選擇:

     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 有輸入時則要接收連線並處理:

         /* 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，與 Linux source code 中的 include/linux/list.h 很像。先閱讀了一下此檔案，一方面看是否有能派上用場的工具，一方面先詳讀每個工具以避免實作時錯誤使用。

container_of

#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 提到:

If you are writing a header file that must work when included in ISO C programs, write __typeof__ instead of typeof.

但這邊我真正的疑問是為何要分成兩種做法，實際使用兩者，編譯成執行檔，查看組語：

#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));
}

組合語言:

   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 中提到，在使用 -ansi 或 -std 的情況下，asm、inline、typeof 這些關鍵字不支援，解法是需要在這些關鍵字前後加上雙底線 __。

typeof 為編譯器提供的功能，而非原本就在 C specs 中的關鍵字，因此使用 typeof 要看你用的編譯器有沒有支援，而 __typeof__ 為 GNU gcc 提供的功能，在其他編譯器可能沒有，這種情況下可以用 macro __GNUC__ 來判別編譯器是否為 GNU gcc，如下例子:

#ifndef __GNUC__
#define __typeof__ typeof
#endif

但以上例子成立的前提是你使用的別款編譯器要支援 typeof。
回過頭來解釋 container_of，裡面用到的 offsetof 就有在 C specs 中，所以其一邊的定義是用了 GNU gcc 功能，一邊則是完全遵守 C specs，但似乎還是沒解釋到為何不單純用遵守 C specs 的定義就好。

list_entry

#define list_entry(node, type, member) container_of(node, type, member)

在 qtest.c 中的使用範例，可以直接從 element_t 的 list 反推取得 element_t 的位址:

element_t *next_item;
next_item = list_entry(item->list.next, element_t, list);

char *cur_inserts =
    list_entry(l_meta.l->prev, element_t, list)->value;

從以上範例也可觀察到，element_t 中的 list，不管是 prev 或 next 都應該指向到 element_t 中的 list。

list_del

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

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

/**
 * 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 部分程式碼:

__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 滿足幾個假設:

每個 pending list size 都為 \(2^k\)
每種 size 的 pending list 個數為 0 ~ 2
較小 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 的結果不如預期。在本地端測試時，主要是 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 就通過了，需要再研究為何會有這樣的結果發生。

TODO: 對照閱讀論文

Image Not Showing Possible Reasons

The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported

Learn More →

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.