2024q1 Homework1 (lab0)

contributed by < komark06 >

實驗環境

$ lscpu
Architecture:            x86_64
  CPU op-mode(s):        32-bit, 64-bit
  Address sizes:         36 bits physical, 48 bits virtual
  Byte Order:            Little Endian
CPU(s):                  4
  On-line CPU(s) list:   0-3
Vendor ID:               GenuineIntel
  Model name:            Intel(R) Core(TM) i3 CPU       M 370  @ 2.40GHz
    CPU family:          6
    Model:               37
    Thread(s) per core:  2
    Core(s) per socket:  2
    Socket(s):           1
    Stepping:            5
    CPU max MHz:         2399.0000
    CPU min MHz:         933.0000
    BogoMIPS:            4931.51

大約十年前的舊電腦，實體記憶體只有 2GB 再加上 SWAP 2GB，總共為 4GB。作業系統為 Lubuntu。

指定的佇列操作

`q_new`

透過 malloc 配置記憶體，並用 INIT_LIST_HEAD 讓佇列指向自己。

`q_free`

透過 list_for_each_entry_safe 走訪佇列，避免釋放節點後，無法走訪下一個節點。單一節點可以透過 q_release_element 來釋放，但是由於實作了 e_new 來配置新節點，將 q_release_element 包裝在 e_release 。

static inline void e_release(element_t *e)
{
    if (e)
        q_release_element(e);
}

`q_insert_head`

透過 e_new 來配置新節點，並用 list_add 插入在佇列開頭。

static element_t *e_new(const char *s)
{
    if (!s)
        return NULL;
    element_t *e = malloc(sizeof(*e));
    if (!e)
        return NULL;
    size_t len = strlen(s) + 1;
    e->value = malloc(len);
    if (!e->value) {
        free(e);
        return NULL;
    }
    memcpy(e->value, s, len);
    return e;
}

研讀 Linux man-pages，撰寫出更精簡的程式碼。

commit 7b453b9 已修正

透過 strdup 來複製字串，可讓程式碼更精簡。

static element_t *e_new(const char *s)
{
    if (!s)
        return NULL;
    element_t *e = malloc(sizeof(*e));
    if (!e)
        return NULL;
    e->value = strdup(s);
    if (!e->value) {
        free(e);
        return NULL;
    }
    return e;
}

`q_insert_tail`

q_insert_head 和 q_insert_tail 只有插入位置的不同，透過將尾端節點當作是佇列本身即能重用 q_insert_head 。

bool q_insert_tail(struct list_head *head, char *s)
{
    return q_insert_head(head->prev, s);
}

`q_remove_head`

透過 q_empty 檢查佇列是否為空或是 NULL，再移除佇列開頭的節點。需要注意的是，由於 bufsize 小於欲刪除的字串長度的情況下，字串結尾的 '\0' 並不會複製到，必須加上去。

static inline bool q_empty(struct list_head *head)
{
    if (!head || list_empty(head))
        return true;
    return false;
}

`q_remove_tail`

類似於 q_remove_head，把佇列的倒數第二個節點作為佇列本身，便會移除佇列結尾的節點。

element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize)
{
    return q_remove_head(head->prev->prev, sp, bufsize);
}

`q_size`

走訪佇列來計算佇列大小。

`q_delete_mid`

透過快慢指標來找尋佇列的中間節點並釋放。

`q_delete_dup`

透過 list_for_each_entry_safe 走訪佇列，若發現當前節點和下一個節點的字串相同，則移除當前節點並紀錄下一個節點到 ready，等到兩字串不相同或是佇列走到最後一個節點時，再釋放 ready 。

`q_reverseK`

dummy: 用來反轉節點用的另一格佇列。
start: 紀錄切分佇列和連結佇列的位置

void q_reverseK(struct list_head *head, int k)
{
    // https://leetcode.com/problems/reverse-nodes-in-k-group/
    if (!head || k <= 1)
        return;
    LIST_HEAD(dummy);
    int count = 0;
    struct list_head *cur, *safe, *start = head;
    list_for_each_safe (cur, safe, head) {
        count++;
        if (count == k) {
            list_cut_position(&dummy, start, cur);
            struct list_head *c, *s;
            list_for_each_safe (c, s, &dummy) {
                list_move(c, &dummy);
            }
            list_splice_init(&dummy, start);
            count = 0;
            start = safe->prev;
        }
    }
}

下圖忽略最後節點和 head 的連結
假設有六個節點，要以三個節點為單位反轉 (k=3)，當 count == 3 時， cur 會指向 3 。

執行完 list_cut_position(&dummy, start, cur) ，會形成兩個佇列。

透過 list_move 反轉。

最後，透過 list_splice_init(&dummy, start) 將兩個佇列連結成一個佇列，並更新 start 。

`q_swap`

q_swap 是兩個節點互換，等同於 q_reverseK(head,2) 。

`q_reverse`

q_reverse 反轉整個佇列，等同於 q_reverseK(head, q_size(head)) ，但這意味著要走訪兩次佇列，應不依賴 q_reverseK 來實作 q_reverse 。
透過 list_for_each_safe 走訪佇列，並用 list_move ，將後方的節點逐個移動到佇列開頭。

commit ef3cfa7 修正。

q_sort

專業術語避免引用 Wikipedia 中文條目，除非沒有對應的英語條目，前者通常落後於英語條目。

已更新成英語條目

使用 merge sort 來實作 q_sort 。拆分佇列時，除了從中間分割以外，也將雙向鏈結改為單向鏈結，直到合併後才回復雙向鏈結。
升序或降序則透過傳入函式指標來控制， e_cmp_func 做為 helper function 判斷是升序或降序，並回傳相對應的函式指標。

typedef int (*list_cmp_func_t)(const struct list_head *,
                               const struct list_head *);

/* Compare two elements in descending order. */
static inline int e_compare_des(const struct list_head *a,
                                const struct list_head *b)
{
    return strcmp(list_entry(b, element_t, list)->value,
                  list_entry(a, element_t, list)->value);
}

/* Return compare function according to 'descend' */
static inline list_cmp_func_t e_cmp_func(bool descend)
{
    if (descend)
        return e_compare_des;
    return e_compare;
}

`q_ascend` 和 `q_descend`

由於q_ascend 和 q_descend 只差別在升序和降序，透過實作 q_remove_by_order ，讓程式碼得以重用。
q_remove_by_order 從尾部走訪佇列並用 descend 來決定升降序，決定節點是否要刪除。

q_remove_order 可能會讓人誤會是「移除某種順序設定」，但其實你要表達 "by order"

commit c04aced 已修正

q_merge

將所有佇列合併成一個佇列後，再用 q_sort 排序。

研讀論文〈Dude, is my code constant time?〉

這篇論文介紹了 dudect，dudect 透過對目標平台上執行時間測量的統計分析，從而檢測程式碼的時間複雜度是否為常數時間。

減少項目縮排，控制在三層，以便於協作。

已修正縮排

步驟 1 ：測量執行時間

首先，我們通過 fix-vs-random 測試來反覆測量函式的執行時間，以捕捉潛在的洩漏。在這種測試中，我們會使用兩種不同的輸入類別：一種是固定值，另一種是每次測量前隨機生成的值。為了避免可能的並行執行導致的干擾，交替使用兩個類別並隨機排列它們的順序。
測量方式：現代 CPU 提供的 cycle counter

步驟 2 ：測量數據前置處理

一般來說，時間分布會呈現正偏態（分布的主體集中在左側），是因為主程序可能被作業系統中斷或是外部活動影響。在此情況下，截斷大於固定的、與類別無關的閾值的測量數據可能會更方便。

步驟 3 ：應用統計檢定

應用統計檢驗來嘗試反駁虛無假說「兩個時間分佈相等」。
使用 Welch’s t-test 來檢定兩個母體的平均是否相等，如果測試失敗就能驗證函式的時間複雜度不是常數時間。

實作

commit 16516c3 已加入 percentile

測試函式為 test_const ，透過 X macro 擴展 test_const ，來測試 q_insert_head 、 q_insert_tail 、 q_remove_head 、 q_remove_tail。

步驟1 ：產生輸入資料

使用 prepare_inputs 來產生隨機字串、每次插入或移除節點的次數、隨機排序兩個資料輸入的順序。

步驟2 ：開始測量

使用 prepare_inputs 產生的資料，傳入到 measure 後，開始測量。

步驟3 ：前置處理測量數據與應用統計檢定

此步驟為 lab0-c 缺乏的部分。

透過 prepare_percentiles 來裁剪數據，並用 update_statistics 算出多個 t 值並找出最大的 t 值，若 t 值大於 t_threshold_moderate，則拒絕虛無假說，說明被測式的函式的時間複雜度並非常數時間。

dudect 的文件中並未詳細說明 prepare_percentiles 函式的理論基礎，僅簡要提及其目標是使數據大致符合測量分布。

整合 linenoise 與網頁伺服器

最初的想法是將 linenoise 的 Asyncrhronous API 加入 lab0-c 後，搭配 select ，便能在處理網頁請求的同時，還能使用 linenoise 的功能。

清楚標示 GitHub 帳號名稱。

已標示清楚

不過 vax-r 先行在 commit b13335b 提交相關功能。故目前以改善此實作為目標。

現有實作問題

由於 lab0-c 的 linenoise 設計，是阻塞直到使用者輸入 Enter 、 Ctrl+C 或 CTRL+D (無任何輸入的情況下)， vax-r 的作法是透過在 line_edit 納入 callback ，也就是 web_eventmux ，阻塞直到有網路請求或是命令列有輸入。
現有實作的問題：

透過網路請求發送命令後，僅能得到狀態碼，並沒有回傳佇列的狀態。最為明顯的便是執行 show ，客戶端只得到 200 OK 的狀態碼，而不知道佇列的狀態。
網頁伺服器啟動後，在沒有任何輸入的情況下，按下 Ctrl+D 並不會結束程式。與未啟用網頁伺服器的情況不同。

改善

static int web_fd;

int web_connfd;
int web_eventmux(char *buf)
{
    fd_set listenset;

    FD_ZERO(&listenset);
    FD_SET(STDIN_FILENO, &listenset);
    FD_SET(web_fd, &listenset);
    int max_fd = STDIN_FILENO > web_fd ? STDIN_FILENO : web_fd;
    int result = select(max_fd + 1, &listenset, NULL, NULL, NULL);
    if (result < 0)
        return -1;

    if (FD_ISSET(web_fd, &listenset)) {
        FD_CLR(web_fd, &listenset);
        struct sockaddr_in clientaddr;
        socklen_t clientlen = sizeof(clientaddr);
        web_connfd =
            accept(web_fd, (struct sockaddr *) &clientaddr, &clientlen);

        char *p = web_recv(web_connfd, &clientaddr);
        char *buffer = "HTTP/1.1 200 OK\r\nContent-Type: text/plain\r\n\r\n";
        web_send(web_connfd, buffer);
        if (p)
            interpret_cmd(p);
        free(p);
        close(web_connfd);
    }
    return 0;
}

一開始的想法，將 web_eventmux 移至 console.c 並呼叫 interpret_cmd 執行命令後，再關閉連結，網路客戶端就可以看到命令執行後的結果。但本地命令列出現格式錯誤，如下面所示：










cmd> web
listen on port 9999, fd is 3
cmd> l = []                 # curl localhost:9999/new

cmd> l = [llukjo bufybp]    # curl localhost:9999/ih/2

cmd> Current queue ID: 0    # curl localhost:9999/show
                        l = [llukjo bufybp]

cmd>

這是因為呼叫 interpret_cmd 時，終端仍處在 raw mode ，導致 linenoise 仍以為使用者還未輸入命令，此外， raw mode 會關閉 OPOST，使 \n 並未轉換成 \r\n ，可見第八行。

思考如何提供對應的測試程式。

一些對測試程式的想法

使用 Popen 來執行 qtest 並啟用網頁伺服器，再用 urlopen 來驗證網頁伺服器是否有正常運作，最後，試圖將程式碼融入到 driver.py

目前碰到的問題：

一開始的想法是透過 pipeline 來模擬使用者輸入，但是 linenoise 會判斷 STDIN_FILENO 是否為終端，如果不是終端，就執行 line_no_tty，導致 line_edit (負責 tab 補完) 和 eventmux_callback (負責處理網路請求)不會被執行。此外，透過 pipeline 來模擬使用者輸入 web 後，會進入無限迴圈，也是因為上述原因。

對於如何測試，目前沒有太多想法

lab0-c 能改善的地方

改善 `test_calloc`

test_calloc 目前尚未將block_element_t 嵌入到配置的記憶體中，故無法追蹤記憶體的使用情況，例如：妥當地釋放記憶體、記憶體是否有越界存取等情況。

須注意test_malloc 和 test_free 會用 FILLCHAR 填滿 payload 做初始化，而 calloc 則是用 0 。

等你的 pull request!

pull request #172 已合併

改善 `console.c`

在 commit b13335b 後， cmd_select 不再需要多工處理網路請求和使用者輸入。故移除相關程式碼並縮減參數。
block_flag 及 prompt_flag 是靜態變數，一旦初始化後，它們的值就不會改變，因此可以刪除相關的條件判斷和變數本身。此外， block_timing 只受到 block_flag 的影響，所以也可以移除相關的條件判斷和變數本身。

-static bool block_flag = false;
-static bool prompt_flag = true;
-
-/* Am I timing a command that has the console blocked? */
-static bool block_timing = false;

static bool do_time(int argc, char *argv[])
         report(1, "Elapsed time = %.3f, Delta time = %.3f", elapsed, delta);
     } else {
         ok = interpret_cmda(argc - 1, argv + 1);
-        if (block_flag) {
-            block_timing = true;
-        } else {
-            delta = delta_time(&last_time);
-            report(1, "Delta time = %.3f", delta);
-        }
+        delta = delta_time(&last_time);
+        report(1, "Delta time = %.3f", delta);
     }

-static int cmd_select(int nfds,
-                      fd_set *readfds,
-                      fd_set *writefds,
-                      fd_set *exceptfds,
-                      struct timeval *timeout)
+static int cmd_select(void)
 {
-    fd_set local_readset;
-
     if (cmd_done())
         return 0;
-
-    if (!block_flag) {
-        int infd;
-        /* Process any commands in input buffer */
-        if (!readfds)
-            readfds = &local_readset;
-
-        /* Add input fd to readset for select */
-        infd = buf_stack->fd;
-        FD_ZERO(readfds);
-        FD_SET(infd, readfds);
-
-        /* If web not ready listen */
-        if (web_fd != -1)
-            FD_SET(web_fd, readfds);
-
-        if (infd == STDIN_FILENO && prompt_flag) {
-            char *cmdline = linenoise(prompt);
-            if (cmdline)
-                interpret_cmd(cmdline);
-            fflush(stdout);
-            prompt_flag = true;
-        } else if (infd != STDIN_FILENO) {
-            char *cmdline = readline();
-            if (cmdline)
-                interpret_cmd(cmdline);
-        }
+    int infd = buf_stack->fd;
+    if (infd == STDIN_FILENO) {
+        char *cmdline = linenoise(prompt);
+        if (cmdline)
+            interpret_cmd(cmdline);
+        fflush(stdout);
+    } else if (infd != STDIN_FILENO) {
+        char *cmdline = readline();
+        if (cmdline)
+            interpret_cmd(cmdline);
     }
     return 0;
 }

bool run_console(char *infile_name)
             line_history_save(HISTORY_FILE); /* Save the history on disk. */
             line_free(cmdline);
             while (buf_stack && buf_stack->fd != STDIN_FILENO)
-                cmd_select(0, NULL, NULL, NULL, NULL);
+                cmd_select();
             has_infile = false;
         }
         if (!use_linenoise) {
             while (!cmd_done())
-                cmd_select(0, NULL, NULL, NULL, NULL);
+                cmd_select();
         }
     } else {
         while (!cmd_done())
-            cmd_select(0, NULL, NULL, NULL, NULL);
+            cmd_select();
     }

2024q1 Homework1 (lab0)

實驗環境

指定的佇列操作

q_new

q_free

q_insert_head

q_insert_tail

q_remove_head

q_remove_tail

q_size

q_delete_mid

q_delete_dup

q_reverseK

q_swap

q_reverse