Try   HackMD

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

  1. 每個 pending list size 都為
    2k
  2. 每種 size 的 pending list 個數為 0 ~ 2
  3. 較小 size 的 pending list 位置會比較靠前

pending 以 prev 連結成一個 singly linked list，每個 prev 指向的是一個 size

2k sublists，等待著被合併。

以下表格逐步說明 count 增長時，pending lists 內部中各個 sublists 的變化，每一個數字表示一個 sublist size，寫在越後面的表示是在 pending 這張 singly linked list 越前面的位置:

count pending lists
0b0 NULL
0b1 1
0b10
21
0b11
21, 1
0b100
21,
21
0b101
22, 1
0b110
22,
21
0b111
22,
21, 1
0b1000
22,
21,
21
0b1001
22,
22, 1
0b1010
22,
22,
21
0b1011
23,
21, 1
0b1100
23,
21,
21
0b1101
23,
22, 1
0b1110
23,
22,
21
0b1111
23,
22,
21, 1

再對比自己的實作，發現自己的實作問題是在 worst case 的情況下，在 merge 時兩邊 list 的 size 沒有限制，導致單次 merge 最差的時間複雜度會是

O(n)；反過來看 Linux 的實作方式，最差的狀況兩邊 list size 為
2(k+1) 和
2k，單次 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
Last changed by 
 
LJP-TW
早安你好再見。
0
1130

Read more

Windbg 筆記

Windbg 筆記 http://windbg.info/doc/1-common-cmds.html Setting Load symbols 先創好資料夾 C:\MyLocalSymbols File -&gt; Settings -&gt; Debugging settings -&gt; Symbol Path srv*C:\MyLocalSymbols*http://msdl.microsoft.com/download/symbols

Apr 1, 2025
Linux Kernel pwn

Linux Kernel pwn Inspection 取得 symbol address 方便下斷點觀察 # 觀察 printk 輸出 echo /proc/sys/kernel/dmesg_restrict # 觀察是否有權限讀 printk 輸出 dmesg # 拿 kernel module address

May 22, 2023
Signal Handling in Linux

&#x597D;&#x6587;: http://courses.cms.caltech.edu/cs124/lectures-wi2016/CS124Lec15.pdf &#x5176;&#x4ED6;&#x7BC7;&#x7B46;&#x8A18;: https://hackmd.io/@LJP/BJAb95O1c &#x5728; task_struct &#x6709;&#x5169;&#x500B; member:

Apr 29, 2022
AArch64 EL1 IRQ handling in Linux

&#x4E3B;&#x8981;&#x60F3;&#x8FFD;&#x8E64;&#x4E00;&#x4E0B; Linux &#x662F;&#x600E;&#x9EBC;&#x505A; irq handling &#x7684;&#x3002; &#x672C;&#x7BC7;&#x8FFD;&#x8E64;&#x7684; Linux &#x7248;&#x672C;&#x70BA; 5.17.1 head.S arch/arm64/kernel/head.S &#x5148;&#x627E; vector table &#x7684;&#x914D;&#x7F6E; primary_entry

Apr 29, 2022
Read more from LJP-TW
Published on HackMD