2025q1 Homework1 (lab0)

contributed by < wurrrrrrrrrr >

作業書寫規範:

無論標題和內文中，中文和英文字元之間要有空白字元 (對排版和文字搜尋有利)
文字訊息 (尤其是程式執行結果) 請避免用圖片來表示，否則不好搜尋和分類
共筆書寫請考慮到日後協作，避免過多的個人色彩，用詞儘量中性
不要在筆記內加入 [TOC] : 筆記左上方已有 Table of Contents (TOC) 功能，不需要畫蛇添足
不要變更預設的 CSS 也不要加入任何佈景主題: 這是「開發紀錄」，用於評分和接受同儕的檢閱
當在筆記中貼入程式碼時，避免非必要的行號，也就是該手動將 c= 或 cpp= 變更為 c 或 cpp。行號只在後續討論明確需要行號時，才要出現，否則維持精簡的展現。可留意「你所不知道的 C 語言: linked list 和非連續記憶體」裡頭程式碼展現的方式
HackMD 不是讓你張貼完整程式碼的地方，GitHub 才是！因此你在開發紀錄只該列出關鍵程式碼 (善用 diff 標示)，可附上對應 GitHub commit 的超連結，列出程式碼是為了「檢討」和「便於他人參與討論」
留意科技詞彙的使用，請參見「資訊科技詞彙翻譯」及「詞彙對照表」
不要濫用 :::info, :::success, :::warning 等標示，儘量用清晰的文字書寫。:::danger 則僅限授課教師作為批注使用
避免過多的中英文混用，已有明確翻譯詞彙者，例如「鏈結串列」(linked list) 和「佇列」(queue)，就使用該中文詞彙，英文則留給變數名稱、人名，或者缺乏通用翻譯詞彙的場景
在中文敘述中，使用全形標點符號，例如該用「，」，而非 ","。注意書名號的使用，即 〈 和 〉，非「小於」和「大於」符號
避免使用不必要的 emoji 字元

開發環境

$  gcc --version
gcc (Ubuntu 11.4.0-1ubuntu1~22.04) 11.4.0
Copyright (C) 2021 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:          39 bits physical, 48 bits virtual
  Byte Order:             Little Endian
CPU(s):                   16
  On-line CPU(s) list:    0-15
Vendor ID:                GenuineIntel
  Model name:             Intel(R) Core(TM) i7-10700 CPU @ 2.90GHz
    CPU family：          6
    model：               165
    Thread(s) per core:   2
    Core(s) per socket:   8
    Socket(s):            1
    Socket(s):            5
    CPU max MHz:          4800.0000
    CPU min MHz:          800.0000
    BogoMIPS:             5799.77

在開始前我先詳閱了這個好的 Git Commit Message 一個好的 commit message 是非常重要的。
其中關鍵的就是以下這7點:

用一行空白行分隔標題與內容
限制標題最多只有 50 字元
標題開頭要大寫
標題不以句點結尾
以祈使句撰寫標題
內文每行最多 72 字
用內文解釋 what 以及 why vs. how

實作指定佇列操作

q_new()

由於之前沒有先看過大概的程式碼就開始實做，因此原本不是用INIT_LIST_HEAD 初始化，後來才在list.h檔中發現到這個函式就改為使用 INIT_LIST_HEAD 初始化 head。

struct list_head *q_new()
{
    struct list_head *new_qhead =
        (struct list_head *) malloc(sizeof(struct list_head));
    if (!new_qhead) {
        return NULL;
    }
    INIT_LIST_HEAD(new_qhead);
    return new_qhead;
}

經過同學對我的提問我才發現到我並不知道 malloc 這個函式分配失敗是否是回傳 NULL ，因此我查閱了c99並看到相關的論述。
c99(7.20.3)

The pointer returned points to the start (lowest byte address) of the allocated space. If the space cannot be allocated, a null pointer is returned. If the size of the space requested is zero, the behavior is implementationdefined: either a null pointer is returned, or the behavior is as if the size were some nonzero value, except that the returned pointer shall not be used to access an object

c99(7.20.3.3)

The malloc function allocates space for an object whose size is specified by size and whose value is indeterminate.
Returns
The malloc function returns either a null pointer or a pointer to the allocated space.

q_insert_head() && q_insert_tail()

分別利用了list.h檔中的list_add和list_add_tail來去完成實做，但在經由友人的提醒之後發現到其實並不需要實做兩個類似的函式，只須完成其中之一的函式，而另一個函式只要呼叫已經實做完成的那個函式即可，改進完的程式碼更為優雅更簡潔。

/* Insert an element at tail of queue */
bool q_insert_tail(struct list_head *head, char *s)
{
    if (!head) {
        return false;
    }
    return q_insert_head(head->prev, s);
}

q_free()

在實做之前我先閱讀了 Linux 核心原始程式碼巨集: container_of 來去了解到container_of的實作手法，並把它引入我的實做當中。

/* Free all storage used by queue */
void q_free(struct list_head *head)
{
    if(!head) {
        return ;
    }
    struct list_head * temp_ptr = head->next;
    while(temp_ptr != head) {
        temp_ptr = temp_ptr->next;
        free(list_entry(temp_ptr->prev, element_t, list)->value);
        free(list_entry(temp_ptr->prev, element_t, list));
    }
    free(head);
}

q_remove_head() && q_remove_tail()

在開始實做前我發現到有兩個函式都能用來複製字串，一個為strncpy另一個為strcpy，於是我好奇兩個有什麼樣的差異，因此我看了 c99 才知道兩個的不同，strcpy來源和目標 (destination) 的記憶體區域不應該有重疊，而另一個strncpy則是不會複製\0。
c99(7.21.2.3)

The strcpy function copies the string pointed to by s2 (including the terminating null character) into the array pointed to by s1. If copying takes place between objects that overlap, the behavior is undefined.

c99(7.21.2.4)

The strncpy function copies not more than n characters (characters that follow a null character are not copied) from the array pointed to by s2 to the array pointed to by If copying takes place between objects that overlap, the behavior is undefined. If the array pointed to by s2 is a string that is shorter than n characters, null characters are appended to the copy in the array pointed to by s1, until n characters in all have been written.

在原本的實做中我使用了 bufsize 而不是 bufsize-1 結果會導致以下的錯誤。

    if (sp) {
        memset(sp, '\0', bufsize);
-        strncpy(sp, container_of(head->next, element_t, list)->value,
-                bufsize);
+        strncpy(sp, container_of(head->next, element_t, list)->value,
+               bufsize-1);
    }

這是其中一個的錯誤訊息:

+++ TESTING trace trace-07-string:
# Test of truncated strings
ERROR: Removed value meerkat_panda_squirrel_vulture_XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX != expected value meerkat_panda_squirrel_vulture

於是我開始找尋該測試的 cmd 檔案發現到這裡的option剛好設置為字串的長度，因此我的 bufsize 會剛好等於字串的長度導致讀出來的字串會沒有\0造成上述的錯誤。

option length 30
rh meerkat_panda_squirrel_vulture

q_delete_mid()

在實做這題前我先解決了 2095. Delete the Middle Node of a Linked List 這題我的解法是先製作了一個fake節點來去指向head，再用first去指向middle的前一個節點
圖參考來源

但在 lab0-c 是雙向鏈結因此不用跑過串列一次去知道串列的大小，只需要一個指向head->next而另一個指向head->prev，然後當兩個指標相遇或是第一個指標的next= 第二個指標時就為middle。

/* Delete the middle node in queue */
bool q_delete_mid(struct list_head *head)
{
    if (!head || list_empty(head)) {
        return false;
    }
    struct list_head *first = head->next;
    struct list_head *last = head->prev;
    while (first != last && first->next != last) {
        first = first->next;
        last = last->prev;
    }
    list_del(last);
    free(list_entry(last, element_t, list)->value);
    free(list_entry(last, element_t, list));
    return true;
}

q_swap()

這題對應到 Leetcode 24. Swap Nodes in Pairs 我使用兩個指標來去指向一個節點和該節點的下一個節點，並使用list.h中所提供的list_move()去做交換。
圖參考來源

/* Swap every two adjacent nodes */
void q_swap(struct list_head *head)
{
    if (!head || list_empty(head) || list_is_singular(head)) {
        return;
    }
    struct list_head *l1 = head->next;
    struct list_head *l2 = head->next->next;
    while (l1 != head && l2 != head) {
        list_move(l1, l2);
        l1 = l1->next;
        l2 = l1->next;
    }
}

q_reversek()

實做之前我先完成 Leetcode 25. Reverse Nodes in k-Group 這題中我先實作一個函式，該函式的功用為傳入一個串列就能將該串列反轉，再用兩個指標去紀錄上一個的 end node 跟當前組的 end node。(以下例子 k = 3)
圖參考來源

後來我參考了 vax-r 來完成相關的實作。

q_ascend() && q_descend()

在實做這個函式之前我先完成相關的 LeetCode 2487. Remove Nodes From Linked List 發現到這個函式基本是循著嚴格遞增或嚴格遞減的方式，像是下面是單向鏈結q_descend()的例子。可以看到最後結果為嚴格遞減，由於這題是雙向鏈結串列因此只需從 head->prev 開始往 prev 找尋嚴格遞增，而q_ascend()是從head->next開始往next找尋嚴格遞增。圖參考來源

/* Remove every node which has a node with a strictly greater value anywhere to
 * the right side of it */
int q_descend(struct list_head *head)
{

    if (!head || list_empty(head) || list_is_singular(head)) {
        return 0;
    }


    char *tmp_max = list_entry(head->prev, element_t, list)->value;
    struct list_head *cur = head->prev->prev;


    while (cur != head) {
        element_t *cur_node = list_entry(cur, element_t, list);
        char *tmp1 = cur_node->value;

        if (strcmp(tmp1, tmp_max) > 0) {
            tmp_max = tmp1; 
            cur = cur->prev;
        } 
        else {
            cur = cur->prev;
            element_t *free_node = list_entry(cur->next, element_t, list);
            list_del(&free_node->list);
            free(free_node->value);
            free(free_node);
        }

    }

    return q_size(head);
}

q_sort()

在實做前我先詳閱 Linked List Sort 來了解相關的實做，在詳閱後發現要通過指定測資的排序方法只有merge sort，而其他的排序方式都會達不成測資所要求的時間複雜度和 stable ，而merge sort相關的實作方法有兩種，這兩種的方式都是遞迴下去切割元素只有在merge所採用的策略有所不同，而一開始我所採用的是遞迴版本的merge。

// Merges two sorted lists into one sorted list
struct list_head *merge(struct list_head* l1, struct list_head* l2, bool descend) {
    // merge with recursive
    if (!l2) {
        return l1;
    }
    if (!l1) {
        return l2;
    }
    
    element_t *node1 = list_entry(l1, element_t, list);
    element_t *node2 = list_entry(l2, element_t, list);

    if (descend) {
        if(strcmp(node1->value, node2->value) < 0) {
            l2->next = merge(l1, l2->next, descend);
            return l2;
        } 
        else {
            l1->next = merge(l1->next, l2, descend);
            return l1;

        }
    }
    else {
        if(strcmp(node1->value, node2->value) <= 0) {
            l1->next = merge(l1->next, l2, descend);
            return l1;
        } 
        else {
            l2->next = merge(l1, l2->next, descend);
            return l2;
        }
    }

}

但發現到不管如何修改我的程式都無法通過測試，原本以為是我的程式出了問題，但反覆觀察程式碼後都找不出原因，後來查看了該測資發現到它是塞入了大量的字串去做排序，由於前面幾筆有關於排序的測試都能通過，而本項測試與前面測試最大的不同只在於資料數量的不同，因此我猜測是否為merge這個函式遞迴的次數太多導致 stack overflow的問題，所以我調整了測資來驗證我的猜測是否屬實，發現到確實是遞迴版本的merge導致我的 stack overflow 。

cmd> new
l = []
cmd> ih dolphin 1000000
l = [dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin ... ]
cmd> it gerbil 1000000
l = [dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin ... ]
cmd> reverse
l = [gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil ... ]
cmd> sort
Warning: Skip checking the stability of the sort because the number of elements 2000000 is too large, exceeds the limit 100000.
程式記憶體區段錯誤 (核心已傾印)

cmd> new
l = []
cmd> ih dolphin 10000
l = [dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin ... ]
cmd> it gerbil 10000
l = [dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin ... ]
cmd> reverse
l = [gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil ... ]
cmd> sort
l = [dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin ... ]
cmd>

以下為修改後不是遞迴的版本:

struct list_head *merge(struct list_head *l1,
                        struct list_head *l2,
                        bool descend)
{
    if (!l2)
        return l1;
    if (!l1)
        return l2;


    struct list_head dummy;
    struct list_head *temp = &dummy;
    dummy.next = NULL;
    dummy.prev = NULL;

    while (l1 && l2) {
        element_t *node1 = list_entry(l1, element_t, list);
        element_t *node2 = list_entry(l2, element_t, list);

        if (!descend) {
            if (strcmp(node1->value, node2->value) <= 0) {
                temp->next = l1;
                temp = temp->next;
                l1 = l1->next;
            } else {
                temp->next = l2;
                temp = temp->next;
                l2 = l2->next;
            }
        } else {
            if (strcmp(node1->value, node2->value) < 0) {
                temp->next = l2;
                temp = temp->next;
                l2 = l2->next;
            } else {
                temp->next = l1;
                temp = temp->next;
                l1 = l1->next;
            }
        }
    }

    if (l1)
        temp->next = l1;
    if (l2)
        temp->next = l2;

    return dummy.next;
}

q_merge()

lab0-c 中 queue_contex_t 與 element_t 的結構是下列這張圖:（trace-03）用到了merge

經過我的測試發現有兩個 id 為 0 的queue_contex_t，但我並不清楚有何作用。圖參考來源

此題是要將每個queue_contex_t結構上head節點所指的鏈結串列去做合併，而每個合併的串列都是事先排序好的因此我們可以運用到上方的merge函式來做合併，確定好方向後開始以下的實做，當最後都合併完之後必須要將鏈結串列去做重新的串接，因為我是將其視為單向鏈結串列來去實做因此只有保證鏈結串列往next的方向是正確的。

/* Merge all the queues into one sowu@wu-Pro-E500-G6-WS720T:~/linux2025/lab0-c$ ./qtest
cmd> new
l = []
'cmd> ih RAND 10
l = [ppdaxq zrsqbseq jqrwe rmyxq tolkbcz fksdh mcbdmci arotglxvf wlwtuxdm zlkfbs]
cmd> option entropy 1
cmd> show
Current queue ID: 0
l = [ppdaxq(26.56%) zrsqbseq(29.69%) jqrwe(26.56%) rmyxq(26.56%) tolkbcz(32.81%) fksdh(26.56%) mcbdmci(26.56%) arotglxvf(37.50%) wlwtuxdm(32.81%) zlkfbs(29.69%)]
cmd> 
cmd> 
Freeing queuerted queue, which is in ascending/descending
 * order */
int q_merge(struct list_head *head, bool descend)
{
    if (!head || list_empty(head))
        return 0;
    else if (list_is_singular(head))
        return q_size(list_first_entry(head, queue_contex_t, chain)->q);

    queue_contex_t *node = list_entry(head->next, queue_contex_t, chain);
    node->q->prev->next = NULL;
    struct list_head *temp = node->chain.next;
    for (int i = 0; i < ((node->size) - 1); i++) {
        queue_contex_t *next_node = list_entry(temp, queue_contex_t, chain);
        next_node->q->prev->next = NULL;
        node->q->next = merge(node->q->next, next_node->q->next, descend);
        INIT_LIST_HEAD(next_node->q);
        temp = temp->next;
    }

    struct list_head *curr = node->q->next;
    struct list_head *pre = node->q;
    while (curr->next != NULL) {
        curr->prev = pre;
        pre = curr;
        curr = curr->next;
    }
    curr->prev = pre;
    curr->next = node->q;
    node->q->prev = curr;

    return q_size(node->q);
}

目前測試結果為95/100。

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

這篇論文的目標是檢測加密演算法是否有時間變異，以確保其在真實硬體上不會因為執行時間不同而洩漏秘密資訊。
這篇論文測量加密函式在兩組不同輸入資料類別下的執行時間，然後檢查這兩組計時分佈是否在統計上存在顯著差異。在測試中第一組輸入數據被固定為一個恆定值，而第二組輸入數據則在每次測量時隨機選取，這種測試叫做fix-vs-random test。

null hypothesis
這篇論文主要是用應用統計檢定來試圖推翻 null hypothesis，也就是「兩組執行時間的分佈是相等的」這個假設，而這個作者使用 Welch’s t-test 的方式去驗證兩組數據的均值是否相等，更嚴格的說兩組結果的變異數 (variance) 也應該相等，如果這個檢定失敗（即結果顯示兩組均值不同），那麼就明顯表示存在一階時間資訊洩漏。

static void measure(dudect_ctx_t *ctx) {
  for (size_t i = 0; i < ctx->config->number_measurements; i++) {
    ctx->ticks[i] = cpucycles();
    do_one_computation(ctx->input_data + i * ctx->config->chunk_size);
  }

  for (size_t i = 0; i < ctx->config->number_measurements-1; i++) {
    ctx->exec_times[i] = ctx->ticks[i+1] - ctx->ticks[i];
  }
}

simulation

在qtest.c中可以看到下列幾行，當simulation被設為 1 時會執行測試指令是否為constant time。這個模式下總共會有10000次的測試總共十輪，只要其中一次小於 lab0-c 所設定的 t 值時就視為常數時間。

    if (simulation) {
        if (argc != 1) {
            report(1, "%s does not need arguments in simulation mode", argv[0]);
            return false;
        }
        bool ok =
            pos == POS_TAIL ? is_insert_tail_const() : is_insert_head_const();
        if (!ok) {
            report(1,
                   "ERROR: Probably not constant time or wrong implementation");
            return false;
        }
        report(1, "Probably constant time");
        return ok;

論文中在統計處理前，他們對測量數據進行預處理，包括丟棄超過某個百分位數 p 的數據。
在論文中有提到典型的計時分佈通常大多數執行時間較短，但仍然會有一些較長的執行時間，導致分佈偏向positively skewed為以下這張圖:

Typical timing distributions are positively skewed towards larger execution times. This may be caused by measurement artifacts, the main process being interrupted by the OS or other extraneous activities
positively skewed

圖參考來源

因此論文有提到截尾（Cropping）：限制測量範圍，例如只保留較短的執行時間數據，去掉異常長的數據點。

In this case, it may be convenient to crop the measurements (or discard measurements that are larger than a fixed, class-independent threshold).

根據我對 dudect 原始程式碼的觀察我發現prepare_percentiles這個函式會呼叫一個percentile的函式，而這個函式的輸入為一個排序完的exec_times陣列和你測試資料的數量，最後還有一個double的浮點數，這個浮點數的作用為你要裁切你資料％數的位置把超過這個％數後的資料去捨棄掉。

  qsort(ctx->exec_times, ctx->config->number_measurements, sizeof(int64_t), (int (*)(const void *, const void *))cmp);
  for (size_t i = 0; i < DUDECT_NUMBER_PERCENTILES; i++) {
    ctx->percentiles[i] = percentile(
        ctx->exec_times, 1 - (pow(0.5, 10 * (double)(i + 1) / DUDECT_NUMBER_PERCENTILES)),
        ctx->config->number_measurements);
  }

可以看到上述程式有一個 1 - (pow(0.5, 10 * (double)(i + 1) / DUDECT_NUMBER_PERCENTILES) ，這個式子就是剛剛所提到的浮點數，而當我們實際畫圖則會發現到這個式子收斂的速度非常的快，因為就像上面提到的典型的計時分佈通常大多數分佈偏向positively skewed所以要專注在裁切掉後半部的部份。
output (1)
可改善的地方在於原始程式碼中只使用了一個陣列去儲存程式執行時間，
而在 lab0-c 中我發現到是使用了兩個陣列去保存執行前執行後的數值分別為 before_ticks[i] 跟 after_ticks[i] 。

  for (size_t i = 0; i < ctx->config->number_measurements; i++) {
    ctx->ticks[i] = cpucycles();
    do_one_computation(ctx->input_data + i * ctx->config->chunk_size);
  }

  for (size_t i = 0; i < ctx->config->number_measurements-1; i++) {
    ctx->exec_times[i] = ctx->ticks[i+1] - ctx->ticks[i];
  }

這段是用percentile這個函式先算出要的百分點位置在陣列中哪個index，並且把超過這個index的資料去做捨棄。

    // t-test on cropped execution times, for several cropping thresholds.
    for (size_t crop_index = 0; crop_index < DUDECT_NUMBER_PERCENTILES; crop_index++) {
      if (difference < ctx->percentiles[crop_index]) {
        t_push(ctx->ttest_ctxs[crop_index + 1], difference, ctx->classes[i]);
      }
    }

在原本的程式中參考了 var-x 的程式，將percentile和prepare_percentiles引入到fixture.c中並把上述的ctx->percentiles[i]替換成exec_times[i]，這樣可以讓大部分執行時間數據反映較長的執行時間，進而更能凸顯整體效能瓶頸。。
但我發現到在我原本的實做中我的排序並沒有把標籤和執行時間去做配對，這樣會導致排序完後的執行時間跟標籤會和原本有所差異，沒有配對的話就像是將標籤去隨機分配到你已經排序完後的資料上，這在原始程式碼會是正確的，因為在原始程式碼中它做排序只是為了抓到上述所說的百分點位置不會改變標籤，而在我的程式碼實做中則是對執行時間做排序後直接使用，因此我先做了個結構叫做Pair來將執行時間和class做配對，因此當qsort完執行時間後可以根據這個配對對class做排序，這樣確保了執行時間不會因為做排序而改變它對應的class。
而當我在實做之前我先去量測了fix跟random的執行時間，結果發現到fix跟random的執行時間有極大的落差，下列為測試執行時間的結果( 當fix為 0 的字串)
constant_time
由圖中可以發現前面幾筆的測試資料都是與後面的數據相比都是有極大的差異，因此在 Dude 中會去捨棄掉前十筆的測試資料在去做相關的測試，但可以發現到fix的每筆資料的執行時間都是顯著低於我random的執行時間，因此我在想是不是0會在電腦中做特殊的處理導致執行時間較短，所以我嘗試將測試資料更改為不同的fix字串，以下為得出的執行結果。
constant_time_changetest1
此測試為將fix字串改動為 0xAA ，可以看到資料的分佈大致相同且通過了trace 17的測試。
constant_time_changetest3
此測試為將fix字串改動為 0xCC ，可以看到資料的分佈也大致相同且通過了trace 17的測試。
constant_changetest2
此測試為將fix字串改動為 0xFF 來去測試邊界，可以看到這個例子會讓 fix 的執行時間平均起來大於random但是也還是能通過trace 17的測試。

至於為什麼 0 會有這種特別的現象是我不懂的地方。

Student's t-distribution

當母群體為常態分佈且無法得知變異數和抽樣的樣本數不夠大的這種情況下我們不能去計算 z 分數這時就要採用樣本的標準差來估計母群體的標準差，像這樣子的分佈我們稱為 Student's t-distribution。
Student's t-distribution 分佈的平均數為 0 且是對稱的分佈為下列這張圖它跟常態分佈不同的地方在於 t 分佈是依據自由度(樣本數 - 1)來改變他的分佈形狀，隨著樣本數越大會越接近常態分佈，當樣本數超過 30 以上的時候就能使用常態分佈的 z 值去取代 t 值( 自由度是統計學中可自由變動的數據數量，代表在計算某個統計量時，有多少個數據點是可以自由變化的。)簡單來說自由度 = 可自由變動的數據數量，受限制的數據點越多，自由度就越少。
紅色的線為他的分佈

(自由度為 1 )

(自由度為 30 )
可以看到當自由度逐漸增加 t 分佈就逐漸和常態分佈越來越相似，還有在探討兩個樣本平均值之差異是否顯著的時候，我們必須先做變異數檢定，假設母群體變異數相同時我們可以套用下列式子
$S_{p}^{2} = \frac{(n_{1} - 1) S_{1}^{2} + (n_{2} - 1) S_{2}^{2}}{n_{1} + n_{2} - 2}$
也就是合併兩個樣本的變異數 $S 1^{2}$ 和 $S 2^{2}$ 來去估計共同的變異數也就是 $S_{p}^{2}$ 這時的 t 值就為下列的公式
$t = \frac{({\bar{x}}_{1} - {\bar{x}}_{2}) - (μ_{1} - μ_{2})}{\sqrt{\frac{S_{p}^{2}}{n_{1}} + \frac{S_{p}^{2}}{n_{2}}}}$
另一種情況為母群體變異數不相同時
$t = \frac{({\bar{x}}_{1} - {\bar{x}}_{2}) - (μ_{1} - μ_{2})}{\sqrt{\frac{S_{1}^{2}}{n_{1}} + \frac{S_{2}^{2}}{n_{2}}}}$
知道了 t 值那我們還需要自由度才能夠去查表那我們在母群體變異數不相同時的自由度計算方式就為這個公式
$v = \frac{{(\frac{S_{1}^{2}}{n_{1}} + \frac{S_{2}^{2}}{n_{2}})}^{2}}{\frac{{(\frac{S_{1}^{2}}{n_{1}})}^{2}}{n_{1} - 1} + \frac{{(\frac{S_{2}^{2}}{n_{2}})}^{2}}{n_{2} - 1}}$

實作 shuffle 命令

實作 Fisher-Yates shuffle Algorithm

在實做這項之前我先去閱讀了 Fisher–Yates shuffle我採用的是他現今的版本是專為電腦使用而設計，由 Richard Durstenfeld 於 1964 年提出。

-- To shuffle an array a of n elements (indices 0..n-1):
for i from n−1 down to 1 do
     j ← random integer such that 0 ≤ j ≤ i
     exchange a[j] and a[i]

利用 lab0-d 提供之測試腳本進行實驗，結果如下。
這是跑了 1000 次的結果，經過幾次測試下來，我發現到說每一次的數據結果的變異性大，尚無法得出具統計意義的結論，因此我進一步擴大測試範圍以獲取更穩定的結果。
shuffle

Expectation:  41666
Observation:  {'1234': 41481, '1243': 41517, '1324': 41850, '1342': 41807, '1423': 41956, '1432': 41674, '2134': 41686, '2143': 41600, '2314': 41309, '2341': 41941, '2413': 41747, '2431': 41760, '3124': 41436, '3142': 41838, '3214': 41974, '3241': 41599, '3412': 41524, '3421': 41595, '4123': 41215, '4132': 41794, '4213': 41593, '4231': 41627, '4312': 41824, '4321': 41653}
chi square sum:  21.033072529160467

以下是跑了1000000次的結果
shuffle

比較亂數產生器 (Xorshift vs. 內建) 的品質

首先要必須先了解到當執行 ih RAND 100 會發生什麼事情，因此我閱讀了原代碼qtest.c和console.c發現到console.c實現了一個簡單的指令列介面，當我輸入 ih RAND 100 時interpret_cmd這個函式會去解析我的這段指令並呼叫parse_args，這個函式把它分割為ih和RAND還有100再用argv這個陣列去保存，隨後交由interpret_cmda這個函式去執行我的命令，其中interpret_cmda這個函式裡使用了叫做cmd_element_t的結構體儲存CLI的指令資訊，並且使用鏈結串列來管理所有可用的指令。
在閱讀完後我發現到了q_show中主要確認開啟entropy分析的在這行：

if (show_entropy) {
    report_noreturn(
        vlevel, "(%3.2f%%)",
        shannon_entropy((const uint8_t *) e->value));
                }

當你在cmd中輸入option entropy 1時它就會將show_entropy這個值設為1也就是 true 。
你原本輸入 ih RAND 10 是不會去做分析的也就是下面這段。

l = [ppdaxq zrsqbseq jqrwe rmyxq tolkbcz fksdh mcbdmci arotglxvf wlwtuxdm zlkfbs]

隨後我們執行option entropy 1可以分別看到個別的字串的 p 值。

Current queue ID: 0
l = [ppdaxq(26.56%) zrsqbseq(29.69%) jqrwe(26.56%) rmyxq(26.56%) tolkbcz(32.81%) fksdh(26.56%) mcbdmci(26.56%) arotglxvf(37.50%) wlwtuxdm(32.81%) zlkfbs(29.69%)]

程式要如何的得知要插入的是亂數字串呢？就必須依靠 ih 後面的 RAND，這個參數會在queue_insert()中的這段去做檢查，當檢查到有輸入 RAND 時會將need_rand設為 true 在把輸入的字串替換成randstr_buf。

    if (!strcmp(inserts, "RAND")) {
        need_rand = true;
        inserts = randstr_buf;
    }

當need_rand為 true 時會執行叫做fill_rand_string的函式，這個函式會將randstr_buf填入亂數字串當作我要插入的資料。

    if (need_rand)
        fill_rand_string(randstr_buf,sizeof(randstr_buf));

了解完大概的流程之後我們開始將Xorshift這一組新的命令去引入 lab0-c ，首先先設計指令檢查到Xorshift就執行Xorshift這個命令。

    if (!strcmp(inserts, "Xorshift")) {
        need_Xorshift = true;
        inserts = Xorshiftstr_buf;
    }

在來就是就設計生出 n 個隨機位元組的函式，我把它命名叫做randombytes_xor也就是以下這個式子

uint64_t xorshift64(void)
{
    xorshift64_state ^= xorshift64_state << 13;
    xorshift64_state ^= xorshift64_state >> 7;
    xorshift64_state ^= xorshift64_state << 17;
    return xorshift64_state;
}


void randombytes_xor(uint8_t *buf, size_t n)
{
    for (size_t i = 0; i < n; i++)
        buf[i] = (uint8_t)(xorshift64() & 0xFF);  
}

後來我依據fill_rand_string這個函式去實做了一個fill_Xorshift_string的函式主要就是去呼叫randombytes_xor這個函式來去填充Xorshiftstr_buf這個buffer。

以下為兩種的方式測試 1000 次的測試結果

研讀 lib/list_sort.c 並嘗試改進

引入 list_sort.c 到 lab0-c

用bottom up實作merge sort對cache較友善，因為過程中就是一直合併，cache被參照到的機會更大。
而top down是會先做partition再來merge，但partition本身對cache不友善，在cache移進移出（內容不斷更新，導致cache thrashing）。

何時合併

每當count + 1，可能會有兩種情況：

1. 當 count + 1 後為 $2^{k}$ 就不合併（只有 leading 1 是 1，其餘都為 0）

2. 當 count + 1 後不為 $2^{k}$ ，就合併

在lib/list_sort.c的基礎上，我進行了一部分的修改後引入到 lab0-c 之程式碼當中。在開發過程中使用make test報出了以下的錯誤，第一步我開始思考什麼叫做這裡所提到的implicit declaration of function。

queue.c: In function ‘list_sort’:
queue.c:478:17: error: implicit declaration of function ‘list_merge’; did you mean ‘list_move’? [-Werror=implicit-function-declaration]

於是我上網看了你所不知道的 C 語言：函式呼叫篇才發現到甚麼是隱式函式也就是在早期的 C 編譯器（ANSI C 之前），當你呼叫一個未事先宣告的函式，編譯器不會報錯，而是自動假設它回傳 int，並允許程式繼續編譯，這種行為稱為Implicit Function Declaration。
但在現在 Implicit Function Declaration 已經被移除掉。

c99(page10)

— remove implicit function declaration

測試 Top down 和 Buttom up merge sort 的效能落差

首先我實做了一個測試程式能夠去相比Top down Merge sort和Buttom up Merge sort的執行速率，其中關於隨機字串我做了一個函式來去生成隨機字串，來去當作我q_insert_head()中的char *s的參數此字串的長度我將它設定為10個char。

const char charset[] = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789";
    for (int i = 0; i < len; i++) {
        int key = rand() % (sizeof(charset) - 1);
        str[i] = charset[key];
    }
    str[len] = '\0';
    return str;

以下測試的clock cycle都還有額外加上generate_random_string()和q_insert_head()還有q_new()執行所需的clock cycles，因此跟單獨執行Merge sort有實際的落差。
這個是Top down的Merge sort所執行出來的結果( test 10000)

 Performance counter stats for './linklisttest' (100 runs):

              3.85 msec task-clock                       #    0.944 CPUs utilized               ( +-  0.17% )
                 0      context-switches                 #    0.000 /sec                      
                 0      cpu-migrations                   #    0.000 /sec                      
               212      page-faults                      #   55.064 K/sec                       ( +-  0.03% )
        17,629,607      cycles                           #    4.579 GHz                         ( +-  0.10% )
        26,215,945      instructions                     #    1.49  insn per cycle              ( +-  0.01% )
         4,934,918      branches                         #    1.282 G/sec                       ( +-  0.00% )
           109,388      branch-misses                    #    2.22% of all branches             ( +-  0.21% )

        0.00408039 +- 0.00000817 seconds time elapsed  ( +-  0.20% )

可以看到第二個clock cycle(16,955,761) 相比第一個 (17,629,607)，減少了 673,846 個 cycle，相當於提升了約 3.82% 的效率。
這個是Buttom up的Merge sort所執行出來的結果( test 10000)

 Performance counter stats for './linklisttest' (100 runs):

              3.70 msec task-clock                       #    0.940 CPUs utilized               ( +-  0.13% )
                 0      context-switches                 #    0.000 /sec                      
                 0      cpu-migrations                   #    0.000 /sec                      
               212      page-faults                      #   57.283 K/sec                       ( +-  0.03% )
        16,955,761      cycles                           #    4.582 GHz                         ( +-  0.11% )
        26,228,216      instructions                     #    1.55  insn per cycle              ( +-  0.01% )
         4,565,037      branches                         #    1.233 G/sec                       ( +-  0.00% )
           109,184      branch-misses                    #    2.39% of all branches             ( +-  0.10% )

        0.00393548 +- 0.00000593 seconds time elapsed  ( +-  0.15% )

這個是Top down的Merge sort所執行出來的結果( test 50000)

 Performance counter stats for './linklisttest' (100 runs):

             20.97 msec task-clock                       #    0.986 CPUs utilized               ( +-  0.23% )
                 0      context-switches                 #    0.000 /sec                      
                 0      cpu-migrations                   #    0.000 /sec                      
               837      page-faults                      #   39.915 K/sec                       ( +-  0.01% )
        96,190,817      cycles                           #    4.587 GHz                         ( +-  0.23% )
       134,174,518      instructions                     #    1.39  insn per cycle              ( +-  0.01% )
        25,198,595      branches                         #    1.202 G/sec                       ( +-  0.01% )
           598,313      branch-misses                    #    2.37% of all branches             ( +-  0.10% )

         0.0212657 +- 0.0000525 seconds time elapsed  ( +-  0.25% )

這個是Buttom up的Merge sort所執行出來的結果( test 50000)

 Performance counter stats for './linklisttest' (100 runs):

             19.77 msec task-clock                       #    0.986 CPUs utilized               ( +-  0.19% )
                 0      context-switches                 #    0.000 /sec                      
                 0      cpu-migrations                   #    0.000 /sec                      
               837      page-faults                      #   42.332 K/sec                       ( +-  0.01% )
        90,649,422      cycles                           #    4.585 GHz                         ( +-  0.18% )
       134,543,086      instructions                     #    1.48  insn per cycle              ( +-  0.00% )
        23,118,201      branches                         #    1.169 G/sec                       ( +-  0.00% )
           596,671      branch-misses                    #    2.58% of all branches             ( +-  0.04% )

         0.0200463 +- 0.0000388 seconds time elapsed  ( +-  0.19% )

第二個clock cycle(90,649,422) 相比第一個 (96,190,817)，減少了 5,541,395 個cycle，相當於提升了約 5.76% 的效率。

以下是測試list node從 5000 到 50000 的實驗結果("Each step size is 5000")
class 0 為 Top down 的 Merge sort
class 1 為 Buttom up 的 Merge sort

引入 timsort 並測試效能

在這次測試中，我選擇使用一個由一半已排序與一半亂序元素組成的串列進行排序操作。結果顯示，在處理 50,000 筆資料時，速度提升達到了 16% :
comparison
然而，必須注意的是，在 worst case（也就是所有資料完全亂序的情況下），timsort 的效能會比 bottom-up merge sort 和 top-down merge sort 略顯不足。這主要是因為 timsort 在處理局部已排序的情形時能夠大幅提升效率，但當所有資料都處於亂序狀態時，這一優勢就無法發揮，反而會因額外的遞迴調用和臨時空間開銷，使得其效能不如傳統的合併排序變種。

Valgrind + 自動測試程式

使用 valgrind 排除 qtest 記憶體問題

根據以 Valgrind + 自動測試程式執行命令 make valgrind ，檢查是否存在記憶體錯誤。
檢查出來的結果如下，可以看到說目前的實做並沒有 Valgrind + 自動測試程式以下所提到的這幾個 memory lost。

definitely lost: 真的 memory leak
indirectly lost: 間接的 memory leak，structure 本身發生 memory leak，而內部的 member 如果是 allocate 的出來的，一樣會 memory leak，但是只要修好前面的問題，後面的問題也會跟著修復。
possibly lost: allocate 一塊記憶體，並且放到指標 ptr，但事後又改變 ptr 指到這塊記憶體的中間
still reachable: 程式結束時有未釋放的記憶體，不過卻還有指標指著，通常會發生在 global 變數
即便是在所用的函式庫裡頭配置的記憶體，也可偵測到，這也是動態分析手法的優勢。

+++ TESTING trace trace-17-complexity:
 # Test if time complexity of q_insert_tail, q_insert_head, q_remove_tail, and q_remove_head is constant
Probably constant time
Probably constant time
Probably constant time
Probably constant time
---     trace-17-complexity     5/5
---     TOTAL           100/100
Test with specific case by running command:
scripts/driver.py -p /tmp/qtest.4wVZMs --valgrind -t < tid >

Massif 視覺化 "simulation" 過程中的記憶體使用量

test
實驗：嘗試減少 heap memory 用量
首先，我將 measure 函式中原本需要輸入兩個陣列的設計，改為只需使用一個陣列，因為在測量操作的執行時間時，並不需要分別存儲執行前後的時間點。只需在陣列中記錄操作開始的 CPU cycles，然後在操作結束後，再以當前的 CPU cycles 減去先前儲存的值，即可計算出執行時間。

bool measure(
+            int64_t *exec_time,
-            int64_t *before_ticks,
-            int64_t *after_ticks,
             uint8_t *input_data,
             int mode);

並去改動 contant.c 中的程式碼：

            int before_size = q_size(l);
-           before_ticks[i] = cpucycles();
+           exec_time[i] = cpucycles();
            dut_insert_head(s, 1);
-           after_ticks[i] = cpucycles();
+           exec_time[i] = cpucycles() - exec_time[i];
            int after_size = q_size(l);

透過這兩項改動，我們成功將兩個陣列的記憶體使用量減少為一個，從而提升了程式的記憶體效率。同時，這種方式不影響執行時間的準確性，因為我們仍然能夠精確地計算出操作的執行時間，僅使用一個陣列來存儲起始時間，並在操作完成後直接計算時間差。這樣不僅減少了不必要的記憶體分配，也讓程式的結構變的加簡潔。

-     int64_t *before_ticks = calloc(N_MEASURES + 1, sizeof(int64_t));
-     int64_t *after_ticks = calloc(N_MEASURES + 1, sizeof(int64_t));
-     free(before_ticks);
-     free(after_ticks);

以下為實驗結果在最高峰的記憶體使用量減少約 1 %：
testmemory

解釋 select 系統

要解釋 select 系統就必須先了解 select 是什麼，於是我先閱讀了 select，了解到 select 是一個同步 I/O Multiplexing 的方法，允許程式同時監視多個檔案描述符，以判斷哪些描述符已準備好進行 I/O 操作。
select() 的主要參數是三個 fd_set（檔案描述符集合）：

readfds（讀取集合）：監視哪些 fd 可讀。

The file descriptors in this set are watched to see if they are ready for reading.

writefds（寫入集合）：監視哪些 fd 可寫。

The file descriptors in this set are watched to see if they are ready for writing.

exceptfds（異常集合）：監視哪些 fd 發生異常。

The file descriptors in this set are watched for "exceptional conditions".

       int select(int nfds, fd_set *_Nullable restrict readfds,
                  fd_set *_Nullable restrict writefds,
                  fd_set *_Nullable restrict exceptfds,
                  struct timeval *_Nullable restrict timeout);

fd_set
這是一種結構體類型，可用於表示一組檔案描述符。在 POSIX 標準中，一個 fd_set 結構內最多能容納 FD_SETSIZE 個描述符（1024 個）。

WARNING: select() can monitor only file descriptors numbers that are less than FD_SETSIZE (1024)

File descriptors sets 可以利用以下巨集操作

FD_ZERO(set) 清空 fd_set（移除所有描述符）。

This macro clears (removes all file descriptors from) set. It should be employed as the first step in initializing a file descriptor set.

FD_SET(fd, set) 將 fd 加入 set。

This macro adds the file descriptor fd to set. Adding a file descriptor that is already present in the set is a no-op, and does not produce an error.

FD_CLR(fd, set) 從 set 移除 fd。

This macro removes the file descriptor fd from set. Removing a file descriptor that is not present in the set is a no-op, and does not produce an error.

FD_ISSET(fd, set) 檢查 fd 是否在 set 中存在於集合中，0 表示不在集合內。

After calling select(), the FD_ISSET() macro can be used to test if a file descriptor is still present in a set. FD_ISSET() returns nonzero if the file descriptor fd is present in set, and zero if it is not.

最後要提到 select 的限制

select() 只能監控數值小於 FD_SETSIZE（1024）的檔案描述符。
因此如果是 web 伺服器、大規模網路應用來說的話是無法勝任的
所以有提到這段話。

All modern applications should instead use poll(2) or epoll(7), which do not suffer this limitation.

而 select 在 lab0-c 中的使用方式為去監聽 0 和 3。其中 0 代表標準輸入也就是終端機，而 3 是伺服器所監聽的 socket 描述符這個用來監聽來自 HTTP 用戶端的請求。而當 server_fd 可讀時代表有新的用戶端嘗試連線，這時會執行 accept() 接受這個連線，並返回一個新的並返回一個新的文字描述符為 4 給予 web_connfd 這個變數，在將網頁資訊寫入該文字描述符最後回傳網頁值給使用者並去釋放該文字描述符。

pselect6(4, [0 3], NULL, NULL, NULL, NULL) = 1 (in [3])
accept(3, {sa_family=AF_INET, sin_port=htons(41216), sin_addr=inet_addr("127.0.0.1")}, [16]) = 4
read(4, "GET /new HTTP/1.1\r\nHost: localho"..., 1024) = 81
write(4, "HTTP/1.1 200 OK\r\n%s%s%s%s%s%sCon"..., 209) = 209
close(4)

當我閱讀完上述的文件後發現到題目的敘述中還有提到了 console.c 的實作運用到了 CS:APP RIO 套件，因此我閱讀了 RIO 套件並把發現記錄下來 System-Level I/O 。
在仔細觀察完程式碼後發現在 console.c 中有模仿了 select() 行為函式的實做。
它實際上是根據內部緩衝區（buf_stack）和網頁伺服器的狀態來決定讀取哪個輸入來源，並將讀取到的命令交給命令解析器來執行。

static int cmd_select(int nfds,
                      fd_set *readfds,
                      fd_set *writefds,
                      fd_set *exceptfds,
                      struct timeval *timeout)

於是我開始找尋 cmd_select 這個函式會在 console.c 中哪一段被呼叫，最後發現到 run_console 這個函式，於是我觀察這個函式的程式碼後發現到 run_console 這個函式在於這個 console.c 這個檔案中是作 console.c 的主要執行函式，他的輸入為 char *infile_name ，而 run_console 中的 push_file 會去看 infile_name 的值否為 NULL ，如果為 NULL 則將會把輸入設為 STDIN_FILENO (也就是標準輸入)，如果不為 NULL 則會去查找是否有這個檔案假如沒有則會執行以下的程式：

report(1, "ERROR: Could not open source file '%s'", infile_name);

假如執行 push_file 成功的話則會去執行該檔案的命令，當檔案中的命令全部執行完後就退出程式，如果為沒有輸入檔案時將會執行一個迴圈不斷的去接收看看有哪個文件表示符就緒。

console.c 會將檔案塞入以下結構業就是類似 RIO 套件中所提到的：

typedef struct __rio {
    int fd;                /* File descriptor */
    int count;             /* Unread bytes in internal buffer */
    char *bufptr;          /* Next unread byte in internal buffer */
    char buf[RIO_BUFSIZE]; /* Internal buffer */
    struct __rio *prev;    /* Next element in stack */
} rio_t;

此處相比 RIO 套件還多增加了 prev 這個參數使得此結構能做成單向鏈結串列。

上述的結構這就是 CS:APP RIO 中所提到的第二種函式有緩衝（Buffered）輸入函式，可以看到在 console.c 中 readline() 這個函式就實現了類似 readlineb() 的結構，就是從當前的緩衝區（buf_stack）中讀取一行文字，直到讀到換行符或達到緩衝區限制，其中該函式最關鍵的是在下列這行。

buf_stack->count = read(buf_stack->fd, buf_stack->buf, RIO_BUFSIZE);

簡單來說就是從該檔案中讀取 RIO_BUFSIZE 位元的資料並存入 buf_stack 的暫存區( buf_stack 是一個指向 rio_t 結構的指標，而且 buf_stack 總是指向最新產生的 rio_t 結構)，這樣的好處就是不用反覆執行 read() 與核心做溝通，在原本可能讀一個檔案要不斷的使用 read 去讀取每一行指令，而在此結構下在buf_stack尚未用完時只須從應用層級的緩衝區來去讀取就好。

舉個例子:就像你今天想喝水每次都要到飲水機去喝，這樣不是很麻煩，所以我們就有了水壺能去裝滿水，只要還沒喝完之前都不用去飲水機裝水要喝水在原地就好。

web.c 中則是直接引入 RIO 套件中的 rio_read 、 rio_readlineb 、rio_readinitb 以及 writen 這些函式來使得 web.c 能將 web_connfd 中 HTTP Request 內容是透過讀取並寫入 rio 。