2022q1 Homework1 (lab0)

contributed by < 2020leon >

作業要求

在 GitHub 上 fork lab0-c
- 參閱 Git 教學和 GitHub 設定指引 ^{附教學影片}
依據上述指示著手修改 queue.[ch] 和連帶的檔案，測試後用 Git 管理各項修改，要能滿足 $ make test 自動評分系統的所有項目。
- 在提交程式變更前，務必詳閱如何寫好 Git Commit Message
- 詳閱「你所不知道的 C 語言: linked list 和非連續記憶體」並應用裡頭提及的手法，例如 pointer to pointer (指向某個指標的指標，或說 indirect pointer)，讓程式碼更精簡且有效
- 研讀 Linux 核心原始程式碼的 lib/list_sort.c 並嘗試引入到 lab0-c 專案，比較你自己實作的 merge sort 和 Linux 核心程式碼之間效能落差
在 qtest 提供新的命令 shuffle，允許藉由 Fisher–Yates shuffle 演算法，對佇列中所有節點進行洗牌 (shuffle) 操作
在 qtest 提供新的命令 web，提供 web 伺服器功能，注意: web 伺服器運作過程中，qtest 仍可接受其他命令
- 可依據前述說明，嘗試整合 tiny-web-server
除了修改程式，也要編輯「作業區」，增添開發紀錄和 GitHub 連結，除了提及你如何逐步達到自動評分程式的要求外，共筆也要涵蓋以下:
- 開啟 Address Sanitizer，修正 qtest 執行過程中的錯誤
  - 先執行 qtest 再於命令提示列輸入 help 命令，會使開啟 Address Sanitizer 觸發錯誤，應予以排除
- 運用 Valgrind 排除 qtest 實作的記憶體錯誤，並透過 Massif 視覺化 "simulation" 過程中的記憶體使用量，需要設計對應的實驗
- 解釋 select 系統呼叫在本程式的使用方式，並分析 console.c 的實作，說明其中運用 CS:APP RIO 套件的原理和考量點。可對照參考 CS:APP 第 10 章重點提示
- 研讀論文〈Dude, is my code constant time?〉，解釋本程式的 "simulation" 模式是如何透過以實驗而非理論分析，達到驗證時間複雜度，需要解釋 Student's t-distribution 及程式實作的原理。注意：現有實作存在若干致命缺陷，請討論並提出解決方案;
指出現有程式的缺陷 (提示: 和 RIO 套件有關) 或者可改進之處 (例如更全面地使用 Linux 核心風格的鏈結串列 API)，嘗試實作並提交 pull request

環境

$ uname -a
Linux leon-ubuntu-20 5.13.0-28-generic #31~20.04.1-Ubuntu SMP Wed Jan 19 14:08:10 UTC 2022 x86_64 x86_64 x86_64 GNU/Linux

$ gcc --version
cc (Ubuntu 9.3.0-17ubuntu1~20.04) 9.3.0
Copyright (C) 2019 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
Byte Order:                      Little Endian
Address sizes:                   36 bits physical, 48 bits virtual
CPU(s):                          4
On-line CPU(s) list:             0-3
Thread(s) per core:              1
Core(s) per socket:              4
Socket(s):                       1
NUMA node(s):                    1
Vendor ID:                       GenuineIntel
CPU family:                      6
Model:                           58
Model name:                      Intel(R) Core(TM) i5-3570 CPU @ 3.40GHz
Stepping:                        9
CPU MHz:                         2100.000
CPU max MHz:                     3800.0000
CPU min MHz:                     1600.0000
BogoMIPS:                        6784.49
Virtualization:                  VT-x
L1d cache:                       128 KiB
L1i cache:                       128 KiB
L2 cache:                        1 MiB
L3 cache:                        6 MiB
NUMA node0 CPU(s):               0-3

開發紀錄

事先準備

將 sysprog21/lab0-c fork 至自己的 GitHub 帳號下並 pull 至本地端
開啟 GitHub Actions 功能

若未開啟 GitHub Actions 則在嘗試 make 時會出現以下輸出：

$ make
Fatal: GitHub Actions MUST be activated.
Check this article: https://docs.github.com/en/actions/managing-workflow-runs/disabling-and-enabling-a-workflow
Then, execute 'make' again.
make: *** [Makefile:34: .git/hooks/applied] Error 1

依據指示開啟後則會有以下輸出（Git hooks 亦會同時被安裝）：

$ make
GitHub Actions has been activated

Git hooks are installed successfully.

  CC    qtest.o
  CC    report.o
  CC    console.o
  CC    harness.o
  CC    queue.o
  CC    random.o
  CC    dudect/constant.o
  CC    dudect/fixture.o
  CC    dudect/ttest.o
  CC    linenoise.o
  LD    qtest

實做佇列（ `queue.c` ）

`q_new`

藉由 malloc 分配記憶體空間，並確認 malloc 的回傳值
藉 INIT_LIST_HEAD 初始化 struct list_head 物件的成員

/*
 * Create empty queue.
 * Return NULL if could not allocate space.
 */
struct list_head *q_new()
{
    /* Malloc queue. */
    struct list_head *const q = malloc(sizeof(struct list_head));
    /* Initialize queue if `q` is not NULL. */
    if (!q)
        return NULL;
    INIT_LIST_HEAD(q);
    return q;
}

後發現有更簡潔的寫法。

/*
 * Create empty queue.
 * Return NULL if could not allocate space.
 */
struct list_head *q_new()
{
    /* Malloc queue. */
    struct list_head *const q = malloc(sizeof(struct list_head));
    /* Initialize queue if `q` is not NULL. */
    if (q)
        INIT_LIST_HEAD(q);
    return q;
}

`q_free`

遍歷佇列，將屬於佇列的 element 提出
藉 q_release_element 釋放空間
釋放變數 l 所指向的空間

/* Free all storage used by queue */
void q_free(struct list_head *l)
{
    element_t *element;
    if (!l)
        return;
    for (struct list_head *i = l->next, *next; i != l; i = next) {
        element = list_entry(i, element_t, list);
        /* `next` as a temporary variable to save the next `list_head` */
        next = element->list.next;
        q_release_element(element);
    }
    free(l);
}

注：需注意的是，要在記憶體空間被釋放前取得所指向的下一個 list_head

善用 list_for_each 一類的巨集來改寫程式碼
jserv

隨後利用 list_for_each_entry_safe 巨集改寫程式碼，結果精簡許多。

/* Free all storage used by queue */
void q_free(struct list_head *l)
{
    element_t *i, *tmp;
    if (!l)
        return;
    list_for_each_entry_safe (i, tmp, l, list)
        q_release_element(i);
    free(l);
}

`q_size`

q_size 的實做可見於 K01: lab0 中。

遍歷佇列並累計其 element 的數量

/*
 * Return number of elements in queue.
 * Return 0 if q is NULL or empty
 */
int q_size(struct list_head *head)
{
    int len = 0;
    struct list_head *li;
    if (!head || list_empty(head))
        return 0;
    list_for_each (li, head)
        len++;
    return len;
}

`q_insert_head`

在實做 q_insert_head 時，注意到下方亦有功能類似的函式（即 q_insert_tail），因此在實做時，將其共同部份提取出來，待未來供 q_insert_tail 使用。

提取出來的函式名為 alloc_helper ，實做如下：

注： ele_alloc_helper 原先的名稱為 _new_element ，為求函式名稱簡潔明瞭而改成 ele_alloc_helper 。

或直接寫 alloc_helper，因為是採 static 宣告的函式，簡潔清晰
jserv

後又改為 alloc_helper 以求簡潔清晰。

/*
 * Create an element with string initialized.
 * Return NULL if could not allocate space or `s` is NULL.
 */
static element_t *alloc_helper(const char *s)
{
    element_t *element;
    size_t slen;
    if (!s)
        return NULL;
    element = malloc(sizeof(element_t));
    if (!element)
        return NULL;

    INIT_LIST_HEAD(&element->list);

    slen = strlen(s) + 1;
    element->value = malloc(slen);
    if (!element->value) {
        free(element);
        return NULL;
    }
    memcpy(element->value, s, slen);
    return element;
}

藉由上方的函式，可大幅簡化 q_insert_head 的實做程式碼。

由 alloc_helper 分配並初始化 element_t 結構
插入佇列的頭端

/*
 * Attempt to insert element at head of queue.
 * Return true if successful.
 * Return false if q is NULL or could not allocate space.
 * Argument s points to the string to be stored.
 * The function must explicitly allocate space and copy the string into it.
 */
bool q_insert_head(struct list_head *head, char *s)
{
    element_t *element;
    if (!head)
        return false;
    element = alloc_helper(s);
    if (!element)
        return false;
    list_add(&element->list, head);
    return true;
}

`q_insert_tail`

由 alloc_helper 分配並初始化 element_t 結構
插入佇列的尾端

/*
 * Attempt to insert element at tail of queue.
 * Return true if successful.
 * Return false if q is NULL or could not allocate space.
 * Argument s points to the string to be stored.
 * The function must explicitly allocate space and copy the string into it.
 */
bool q_insert_tail(struct list_head *head, char *s)
{
    element_t *element;
    if (!head)
        return false;
    element = alloc_helper(s);
    if (!element)
        return false;
    list_add_tail(&element->list, head);
    return true;
}

`q_swap`

依據 struct list_head 的特性，可以寫出簡短的程式碼。其原理便是將索引為偶數的節點之 next 移至其前方，直到僅剩一個節點或全部的節點都交換完為止。

注：索引值從零開始

/*
 * Attempt to swap every two adjacent nodes.
 */
void q_swap(struct list_head *head)
{
    // https://leetcode.com/problems/swap-nodes-in-pairs/
    if (!head || list_empty(head))
        return;
    for (struct list_head *i = head->next; i != head && i->next != head;
         i = i->next)
        list_move_tail(i->next, i);
}

`q_reverse`

依據 struct list_head 的特性，亦可寫出簡短的程式碼。原理便是每次將節點從佇列的最尾端移至 i 的前方，而 i 總是指向前一步被移動的節點。

/*
 * Reverse elements in queue
 * No effect if q is NULL or empty
 * This function should not allocate or free any list elements
 * (e.g., by calling q_insert_head, q_insert_tail, or q_remove_head).
 * It should rearrange the existing ones.
 */
void q_reverse(struct list_head *head)
{
    if (!head || list_empty(head))
        return;
    for (struct list_head *i = head; i->next != head->prev; i = i->next)
        list_move(head->prev, i);
}

`q_remove_head`

剩下尚未實做的函式（即 q_remove_head 、 q_remove_tail 、 q_delete_dup 、 q_delete_mid ）大多需要從佇列中移除節點，因此將其共同部份提取出來，待未來供以上函式使用。

提取出來的函式名為 my_q_remove ，實做如下：

/*
 * Attempt to remove node from a queue.
 * Return target element.
 * Return NULL if queue is NULL or empty.
 * If sp is non-NULL and an element is removed, copy the removed string to *sp
 * (up to a maximum of bufsize-1 characters, plus a null terminator.)
 */
static element_t *my_q_remove(struct list_head *node, char *sp, size_t bufsize)
{
    element_t *const element = list_entry(node, element_t, list);
    list_del_init(node);
    if (sp && bufsize) {
        size_t min = strlen(element->value) + 1;
        min = min > bufsize ? bufsize : min;
        memcpy(sp, element->value, min);
        sp[min - 1] = '\0';
    }
    return element;
}

在 my_q_remove 中，亦提供 sp 、 bufsize 等參數可供 q_remove_head 、 q_remove_tail 等需將字串複製至 sp 所指向位置的函式使用。值得注意的地方為 min 變數，其確保能以最少的複製來達成複製字串的目的。

藉由上方的函式，可大幅簡化 q_remove_head 的實做程式碼，只需判斷佇列是否為空即可。

/*
 * Attempt to remove element from head of queue.
 * Return target element.
 * Return NULL if queue is NULL or empty.
 * If sp is non-NULL and an element is removed, copy the removed string to *sp
 * (up to a maximum of bufsize-1 characters, plus a null terminator.)
 *
 * NOTE: "remove" is different from "delete"
 * The space used by the list element and the string should not be freed.
 * The only thing "remove" need to do is unlink it.
 *
 * REF:
 * https://english.stackexchange.com/questions/52508/difference-between-delete-and-remove
 */
element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
    return !head || list_empty(head) ? NULL
                                     : my_q_remove(head->next, sp, bufsize);
}

`q_remove_tail`

q_remove_tail 的實做與 q_remove_head 大同小異，只差所移除的節點不同。

/*
 * Attempt to remove element from tail of queue.
 * Other attribute is as same as q_remove_head.
 */
element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize)
{
    return !head || list_empty(head) ? NULL
                                     : my_q_remove(head->prev, sp, bufsize);
}

`q_delete_dup`

比較相鄰的節點字串
若相鄰的節點字串相同，將節點自佇列中移除並釋放之

/*
 * Delete all nodes that have duplicate string,
 * leaving only distinct strings from the original list.
 * Return true if successful.
 * Return false if list is NULL.
 *
 * Note: this function always be called after sorting, in other words,
 * list is guaranteed to be sorted in ascending order.
 */
bool q_delete_dup(struct list_head *head)
{
    // https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/
    struct list_head *i, *j;
    if (!head)
        return false;
    i = head->next;
    for (j = i->next; j != head; j = j->next) {
        if (strcmp(((element_t *) list_entry(i, element_t, list))->value,
                   ((element_t *) list_entry(j, element_t, list))->value) ==
            0) {
            // Remove j from the queue and release it
            q_release_element(my_q_remove(j, NULL, 0));
            // Assign i to j after j is deleted
            // For the next loop, j == i->next
            j = i;
        } else {
            i = i->next;
        }
    }
    return true;
}

注：由於 aspell 工具會阻擋含有「 dup 」單字的 commit message ，因此若 commit message 中有提及該函式，需在 aspell-pws 檔案中加入「 dup 」單字。

後又仔細研讀 LeetCode 82 所提供的例子及 #73 可知以上實做不符要求。

根據以上二者， list [a, a, b] 在經過本函式後應為 [b] 而非 [a, b] 。修改起來很簡單，僅需再加數行即可。

bool q_delete_dup(struct list_head *head)
{
    // https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/
    struct list_head *i, *j;
+   bool is_i_dup = false;
    if (!head)
        return false;
    i = head->next;
    for (j = i->next; j != head; j = j->next) {
        if (strcmp(((element_t *) list_entry(i, element_t, list))->value,
                   ((element_t *) list_entry(j, element_t, list))->value) ==
            0) {
+           is_i_dup = true;
            // Remove j from the queue and release it
            q_release_element(my_q_remove(j, NULL, 0));
            // Assign i to j after j is deleted
            // For the next loop, j == i->next
            j = i;
        } else {
            i = i->next;
+           // Delete the last node whose string was duplicated
+           if (is_i_dup) {
+               q_release_element(my_q_remove(i->prev, NULL, 0));
+               is_i_dup = false;
+           }
        }
    }
    return true;
}

上述改動可通過測資，但並非正確實做。其未考慮到如 [a, b, b] 之例，上述函式會錯誤地將 list 改為 [a, b] ，而實應為 [a] 。因此做出最後改動。

bool q_delete_dup(struct list_head *head)
{
...
+   if (is_i_dup)
+       q_release_element(my_q_remove(i, NULL, 0));
    return true;
}

隨後又發現 container_of 巨集會返回其相關型別的指標型別，因此將類似 ((element_t *) list_entry(i, element_t, list))->value 的語句改為 list_entry(i, element_t, list)->value ，下方 q_sort 亦同不再贅述。

`q_delete_mid`

q_delete_mid 及 q_sort 均需將中間值提出，將提取中間值作為一個函式，待未來供 q_sort 使用。

提取出來的函式名為 get_mid_node ，實做如下：

/*
 * Get the middle node in list.
 * The middle node of a linked list of size n is the
 * ⌊n / 2⌋th node from the start using 0-based indexing.
 * If there're six element, the third member should be return.
 * Return the middle node.
 *
 * Note: `head` must not be empty
 */
static struct list_head *get_mid_node(const struct list_head *head)
{
    struct list_head *i = head->next, *j = head->prev;
    while (i != j && i->next != j)
        i = i->next, j = j->prev;
    return j;
}

藉由上方的函式，可大幅簡化 q_delete_mid 的實做程式碼。

/*
 * Delete the middle node in list.
 * The middle node of a linked list of size n is the
 * ⌊n / 2⌋th node from the start using 0-based indexing.
 * If there're six element, the third member should be return.
 * Return true if successful.
 * Return false if list is NULL or empty.
 */
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;
    q_release_element(my_q_remove(get_mid_node(head), NULL, 0));
    return true;
}

`q_sort`

利用「合併排序」實作排序。

將佇列分二半
分二半的佇列各自排序
將被分出去的另一半逐項插回原佇列

/*
 * 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)
{
    // Merge sort
    struct list_head *i, *j, *tmp;
    LIST_HEAD(new_head);
    if (!head || list_empty(head) || list_is_singular(head))
        return;
    // Split the list
    list_cut_position(&new_head, head, get_mid_node(head)->prev);
    // Call recursively
    q_sort(&new_head);
    q_sort(head);
    // Insert nodes in new_head to head
    i = head->next;
    for (j = new_head.next; !list_empty(&new_head); j = tmp) {
        while (i != head &&
               strcmp(((element_t *) list_entry(i, element_t, list))->value,
                      ((element_t *) list_entry(j, element_t, list))->value) <
                   0) {
            i = i->next;
        }
        if (i == head) {
            // All of the remaining elements in new_head is greater than i
            list_splice_tail_init(&new_head, i);
        } else {
            tmp = j->next;
            list_del_init(j);
            list_add_tail(j, i);
            // i->prev == j
        }
    }
}

引入 `lib/list_sort.c`

引入該檔的作法參考 SmallHanley 。

首先在 qtest.c 新增一個 option 名為「 sort 」。新增選項的目的為待未來測試時能夠在不調整程式碼重新編譯的情況下快速切換自行實做的排序法及 lib/list_sort.c 中的排序函式。

 ...
+static int kernelsort = 0;
 ...
 static void console_init()
 {
 ...
+    add_param("sort", &kernelsort, "Enable/disable kernel version sort", NULL);
 ...
 }

接著直接至 linux 核心複製 lib/list_sort.c 及 include/linux/list_sort.h 至 lab0-c 專案下並加以修改。需修改的地方如下。

所引入的標頭檔
- 因 lib/list_sort.c 所引入的標頭檔均為 linux 核心相關的的標頭檔，若欲在 user mode 運作需修改相關標頭
likely(x) 及 unlikely(x) 巨集
- 上述二巨集定義於 include/linux/compiler.h 中，其功能為藉由搬動程式碼使更為常用的區塊能夠相鄰，使 cache hit rate 上升
使 cppcheck 忽略 merge 函式中的 struct list_head *head, **tail = &head; 「 unassignedVariable 」錯誤
- 事實上 head 會在往後的迴圈中藉 tail 賦值，但 cppcheck 未能偵測，藉 // cppcheck-suppress unassignedVariable 抑制錯誤
型別 u8 更為 uint8_t
- u8 為定義於 include/linux/types.h 的資料型態，藉引入 stdint.h 改為 uint8_t

複製後，記得修改 Makefile 。

list_sort.c 中的 list_sort 函式原型可簡化如下。

typedef int (*list_cmp_func_t)(void *,
                               const struct list_head *,
                               const struct list_head *);
void list_sort(void *priv, struct list_head *head, list_cmp_func_t cmp);

分析其函式原型，可知其須傳入三個參數。

priv ：為未來會傳入 cmp 的第一個參數，可協助 cmp 排序
head ：欲排序的 list
cmp ：比較函式，回傳 int 型別

在此先實做比較函式。

static int list_cmp(void *_,
                    const struct list_head *a,
                    const struct list_head *b)
{
    return strcmp(list_entry(a, element_t, list)->value,
                  list_entry(b, element_t, list)->value);
}

再修改 do_sort 函式即完成。

bool do_sort(int argc, char *argv[])
{
...
    set_noallocate_mode(true);
-   if (exception_setup(true))
+   if (exception_setup(true)) {
+       if (kernelsort)
+           list_sort(NULL, l_meta.l, list_cmp);
+       else
            q_sort(l_meta.l);
+   }
    exception_cancel();
    set_noallocate_mode(false);
...
}

比較效能落差

嘗試新增批次命令檔 traces/trace-sort.cmd 以達自動化測試。

option echo 0
option verbose 1

# user-version sort
option sort 0
new
it RAND 262144
time sort

# kernel-version sort
option sort 1
new
it RAND 262144
time sort

其中一次結果如下：

$ ./qtest -f traces/trace-sort.cmd
cmd> option echo 0
# user-version sort
Delta time = 0.148
# kernel-version sort
Delta time = 0.204

原因自己的合併排序較核心的排序法快而竊喜，然在修改 traces/trace-sort.cmd 後再執行一次。

$ ./qtest -f traces/trace-sort.cmd
cmd> option echo 0
# user-version sort
Delta time = 0.146
Delta time = 0.244
# kernel-version sort
Delta time = 0.213
Delta time = 0.215

由上可發現，第一次排序會莫名快，目前仍未找出原因。

因此在前方加入一假排序。

./qtest -f traces/trace-sort.cmd
cmd> option echo 0
# dummy sort
Delta time = 0.156
# user-version sort
Delta time = 0.250
Delta time = 0.262
# kernel-version sort
Delta time = 0.214
Delta time = 0.217

最後使各排序法排序已排序的 list ，並使各排序法排序五次。

$ ./qtest -f traces/trace-sort.cmd
cmd> option echo 0
# dummy sort
Delta time = 0.156
# user-version sort
Delta time = 0.250
Delta time = 0.262
Delta time = 0.261
Delta time = 0.260
Delta time = 0.261
# sort sorted list
Delta time = 0.201
# kernel-version sort
Delta time = 0.214
Delta time = 0.217
Delta time = 0.218
Delta time = 0.216
Delta time = 0.216
# sort sorted list
Delta time = 0.164

結果發現自己實做的排序較核心版本的排序慢約 19.7% 。對已排序的 list 做排序則慢約 22.6% 。

實做洗牌（ `shuffle` ）

依據作業要求，需根據 Fisher-Yates shuffle 演算法，對佇列中所有節點進行洗牌，因此在 qtest.c 中以名為 q_shuffle 的函式實做洗牌。

static void q_shuffle(struct list_head *head)
{
    // Fisher-Yates shuffle
    int size;
    if (!head || list_empty(head))
        return;
    size = q_size(head);
    for (struct list_head *i = head, *j; size > 0; i = j, size--) {
        j = head->next;
        for (int k = rand() % size; k > 0; k--)
            j = j->next;
        // Swap i->prev and j
        list_move_tail(i->prev, j);
        list_move_tail(j, i);
    }
}

上方的函式利用英語維基所提及的 morden algorithm 實作其~~偽代碼~~虛擬碼如下：

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

接下來實做 do_shuffle 對 q_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: Try to access null queue");
    error_check();

    if (exception_setup(true))
        q_shuffle(l_meta.l);
    exception_cancel();

    show_queue(3);
    return !error_check();
}

do_shuffle 參考 q_test.c 中眾多 do_* 函式實做，使 shuffle 成為一個不接受任何參數、呼叫 q_shuffle 的命令。

最後在 console_init 函式中註冊 shuffle 命令即大功告成。

static void console_init()
{
...
    ADD_COMMAND(swap,
                "                | Swap every two adjacent nodes in queue");
+   ADD_COMMAND(shuffle, "                | Shuffle nodes in queue");
    add_param("length", &string_length, "Maximum length of displayed string",
              NULL);
...
}

實做伺服器（ `web` ）

伺服器並非一蹴可及，因此先新增一個命令 web ，待未來實做伺服器後再賦予其實際功能。

static bool do_web(int argc, char *argv[])
{
    if (argc != 1) {
        report(1, "%s takes no arguments", argv[0]);
        return false;
    }
    return true;
}

static void console_init()
{
...
    ADD_COMMAND(shuffle, "                | Shuffle nodes in queue");
+   ADD_COMMAND(web, "                | Response to web client");
    add_param("length", &string_length, "Maximum length of displayed string",
              NULL);
...
}

由於網頁伺服器並不是由簡單的三言兩語能夠描述的，因此獨立出二個檔案（分別為標頭檔 tinyserver.h 和實做 tinyserver.c ）來實現網頁伺服器。

首先，在標頭檔中，須對於全域變數進行宣告，以供其他檔案存取。

extern int listenfd;
extern bool noise;

參考 K01: lab0 及 7890/tiny-web-server 來實做自己的 process 函式，其功能為在收到請求後，將 URL 的斜線替為空格，並在終端機及網頁上印出相對應的字串。

char *process(int fd, struct sockaddr_in *clientaddr)
{
#ifdef LOG_ACCESS
    printf("accept request, fd is %d, pid is %d\n", fd, getpid());
#endif
    http_request req;
    parse_request(fd, &req);

    char *p = req.function_name;
    /* Change '/' to ' ' */
    while ((*p) != '\0') {
        ++p;
        if (*p == '/')
            *p = ' ';
    }
#ifdef LOG_ACCESS
    log_access(status, clientaddr, &req);
#endif
    char *ret = malloc(strlen(req.function_name) + 1);
    strncpy(ret, req.function_name, strlen(req.function_name) + 1);
    writen(fd, req.function_name, strlen(req.function_name));
    printf("web> %s\n", req.function_name);

    return ret;
}

其中許多的自定義函式實做均在 7890/tiny-web-server 可見，惟部份函式須稍做更動以符合本作業的規範。

Makefile 也要做出相對應的更動。

OBJS := qtest.o report.o console.o harness.o queue.o \
        random.o dudect/constant.o dudect/fixture.o dudect/ttest.o \
-       linenoise.o
+       linenoise.o tinyserver.o

deps := $(OBJS:%.o=.%.o.d)

接著參考 K01: lab0 編輯 console.c 中的 cmd_select 函式及 run_console 函式，以使其能處理多個檔案描述符及根據 noise 旗標來決定要執行 linenoise() 或 cmd_select() 。詳細的改動可以參考 K01: lab0 ，在此不多贅述。

再來是新增取得檔案描述符的函式，此函式僅為對 open_listenfd 函式的封裝，而 open_listenfd 函式實做可見於 7890/tiny-web-server。

int get_listenfd()
{
    int default_port = DEFAULT_PORT;

    listenfd = open_listenfd(default_port);
    if (listenfd > 0) {
        printf("listen on port %d, fd is %d\n", default_port, listenfd);
    } else {
        perror("ERROR");
        exit(listenfd);
    }

    return listenfd;
}

緊接著是 tinyserver.c 中的最後一個函式： tiny_server_init ，其功能為忽略 SIGPIPE 訊號，並會在主函式中被呼叫。當瀏覽器因故取消請求時，便會發出 SIGPIPE 訊號。該訊號的預設行為為中止（ terminate ）程序。未避免程序中止，在訊號發出時直接忽略它。

void tiny_server_init()
{
    // Ignore SIGPIPE signal, so if browser cancels the request, it
    // won't kill the whole process.
    signal(SIGPIPE, SIG_IGN);
}

實踐伺服器的最後一里路就是回到 do_web 函式，新增以下二行！

static bool do_web(int argc, char *argv[])
{
    if (argc != 1) {
        report(1, "%s takes no arguments", argv[0]);
        return false;
    }
+   listenfd = get_listenfd();
+   noise = false;
    return true;
}

然在編譯實測後，發現仍有不足，遇到的問題如下：

輸入第二次 web 命令後會使程序直接中斷
在發出請求後，會再印出一次指令

以下是依據以上問題所提出的解決方案，即：

檢查 listenfd ，若已開啟則不再呼叫 get_listenfd 。
set_echo(false)

static bool do_web(int argc, char *argv[])
{
    if (argc != 1) {
        report(1, "%s takes no arguments", argv[0]);
        return false;
    }
+   if (listenfd == -1) {
        listenfd = get_listenfd();
        noise = false;
+       set_echo(false);
        return true;
+   } else {
+       report(1, "web server is already turned on");
+       return false;
+   }
}

HTTP header

上述之伺服器並未回傳任何 HTTP header ，也就是本伺服器在回覆時並未明確定義狀態碼、 HTTP 版本、資料格式等，在此簡單實做回傳 HTTP header 的函式。

static void writen_header(int out_fd)
{
    char buf[256];
    snprintf(buf, sizeof(buf), "HTTP/1.1 200 OK\r\nAccept-Ranges: bytes\r\n");
    snprintf(buf + strlen(buf), sizeof(buf) - strlen(buf),
             "Cache-Control: no-cache\r\n");
    snprintf(buf + strlen(buf), sizeof(buf) - strlen(buf),
             "Content-type: text/plain\r\n\r\n");

    writen(out_fd, buf, strlen(buf));
}

並在 process 函式中呼叫。

char *process(int fd, struct sockaddr_in *clientaddr)
{
...
+   writen_header(fd);
    writen(fd, req.function_name, strlen(req.function_name));
...
}

`favicon.ico` 問題

實際上部份瀏覽器在發出請求的時候，若未在 HTML 的 head 段落中明確定義 favicon ，瀏覽器會順帶發出 http://xxx/favicon.ico 的請求。若要避免瀏覽器發出該請求，可在 head 段落中加入 <link rel="shortcut icon" href="#"> 即可。

嘗試在承接之前的程式碼下解決問題，因此簡單實做回覆 HTML 格式的函式。

static void writen_content(int out_fd, const char *content)
{
    char buf[1024];
    // Prevent browser sending favicon.ico request
    snprintf(buf, sizeof(buf),
             "<!DOCTYPE html>"
             "<html>"
             "<head>"
             "<link rel=\"shortcut icon\" href=\"#\">"
             "</head>"
             "<body>%s</body>"
             "</html>",
             content);
    writen(out_fd, buf, strlen(buf));
}

並修改 MIME 類別。

static void writen_header(int out_fd)
{
...
    snprintf(buf + strlen(buf), sizeof(buf) - strlen(buf),
-            "Content-type: text/plain\r\n\r\n");
+            "Content-type: text/html\r\n\r\n");
...
}

最後在 process 函式中呼叫即可。

char *process(int fd, struct sockaddr_in *clientaddr)
{
...
    writen_header(fd);
-   writen(fd, req.function_name, strlen(req.function_name));
+   writen_content(fd, req.function_name);
...
}

修正錯誤（ Address Sanitizer ）

期望藉 Address Sanitizer 修正錯誤，事實上該錯誤已於 #60 解決。

在此嘗試重現錯誤。

git revert 並修復衝突
```
git revert 8fbc1
```

make

make clean # optional
make SANITIZER=1

執行 qtest 並鍵入 help ，錯誤訊息如下

$ ./qtest         
cmd> help
Commands:
        #        ...            | Display comment
        dedup                   | Delete all nodes that have duplicate string
        dm                      | Delete middle node in queue
        free                    | Delete queue
        help                    | Show documentation
        ih       str [n]        | Insert string str at head of queue n times. Generate random string(s) if str equals RAND. (default: n == 1)
        it       str [n]        | Insert string str at tail of queue n times. Generate random string(s) if str equals RAND. (default: n == 1)
        log      file           | Copy output to file
        new                     | Create new queue
        option   [name val]     | Display or set options
        quit                    | Exit program
        reverse                 | Reverse queue
        rh       [str]          | Remove from head of queue.  Optionally compare to expected value str
        rhq                     | Remove from head of queue without reporting value.
        rt       [str]          | Remove from tail of queue.  Optionally compare to expected value str
        show                    | Show queue contents
        shuffle                 | Shuffle nodes in queue
        size     [n]            | Compute queue size n times (default: n == 1)
        sort                    | Sort queue in ascending order
        source   file           | Read commands from source file
        swap                    | Swap every two adjacent nodes in queue
        time     cmd arg ...    | Time command execution
        web                     | Response to web client
Options:
=================================================================
==449409==ERROR: AddressSanitizer: global-buffer-overflow on address 0x559904fd1d40 at pc 0x559904fb7b84 bp 0x7ffcaa133e50 sp 0x7ffcaa133e40
READ of size 4 at 0x559904fd1d40 thread T0
    #0 0x559904fb7b83 in do_help /home/leon/Documents/NCKU/Linux_Kernel/hw0/lab0-c/console.c:271
    #1 0x559904fb79bf in interpret_cmda /home/leon/Documents/NCKU/Linux_Kernel/hw0/lab0-c/console.c:185
    #2 0x559904fb835e in interpret_cmd /home/leon/Documents/NCKU/Linux_Kernel/hw0/lab0-c/console.c:208
    #3 0x559904fb9daf in run_console /home/leon/Documents/NCKU/Linux_Kernel/hw0/lab0-c/console.c:669
    #4 0x559904fb666e in main /home/leon/Documents/NCKU/Linux_Kernel/hw0/lab0-c/qtest.c:1135
    #5 0x7fad9f4480b2 in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x270b2)
    #6 0x559904fb2ccd in _start (/home/leon/Documents/NCKU/Linux_Kernel/hw0/lab0-c/qtest+0x9ccd)

0x559904fd1d41 is located 0 bytes to the right of global variable 'echo' defined in 'console.c:59:13' (0x559904fd1d40) of size 1
SUMMARY: AddressSanitizer: global-buffer-overflow /home/leon/Documents/NCKU/Linux_Kernel/hw0/lab0-c/console.c:271 in do_help
Shadow bytes around the buggy address:
  0x0ab3a09f2350: f9 f9 f9 f9 04 f9 f9 f9 f9 f9 f9 f9 04 f9 f9 f9
  0x0ab3a09f2360: f9 f9 f9 f9 00 f9 f9 f9 f9 f9 f9 f9 00 f9 f9 f9
  0x0ab3a09f2370: f9 f9 f9 f9 00 f9 f9 f9 f9 f9 f9 f9 00 00 00 00
  0x0ab3a09f2380: 04 f9 f9 f9 f9 f9 f9 f9 00 00 00 00 00 00 00 00
  0x0ab3a09f2390: 00 00 f9 f9 f9 f9 f9 f9 01 f9 f9 f9 f9 f9 f9 f9
=>0x0ab3a09f23a0: 01 f9 f9 f9 f9 f9 f9 f9[01]f9 f9 f9 f9 f9 f9 f9
  0x0ab3a09f23b0: 04 f9 f9 f9 f9 f9 f9 f9 04 f9 f9 f9 f9 f9 f9 f9
  0x0ab3a09f23c0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x0ab3a09f23d0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x0ab3a09f23e0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x0ab3a09f23f0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
Shadow byte legend (one shadow byte represents 8 application bytes):
  Addressable:           00
  Partially addressable: 01 02 03 04 05 06 07 
  Heap left redzone:       fa
  Freed heap region:       fd
  Stack left redzone:      f1
  Stack mid redzone:       f2
  Stack right redzone:     f3
  Stack after return:      f5
  Stack use after scope:   f8
  Global redzone:          f9
  Global init order:       f6
  Poisoned by user:        f7
  Container overflow:      fc
  Array cookie:            ac
  Intra object redzone:    bb
  ASan internal:           fe
  Left alloca redzone:     ca
  Right alloca redzone:    cb
  Shadow gap:              cc
==449409==ABORTING

修正錯誤（ Valgrind ）

直接執行主程式並未發現任何可觸發錯誤的地方。範例如下。

$ valgrind ./qtest
cmd> new
l = []
cmd> it a
l = [a]
cmd> it z
l = [a z]
cmd> swap
l = [z a]
cmd> sort
l = [a z]
cmd> free
l = NULL
cmd> 
Freeing queue

然若餵檔則會出錯。

$ valgrind ./qtest -f ./traces/trace-eg.cmd
cmd> # Demonstration of queue testing framework
cmd> # Use help command to see list of commands and options
cmd> # Initial queue is NULL.
cmd> show
l = NULL
cmd> # Create empty queue
cmd> new
l = []
cmd> # See how long it is
cmd> size
Queue size = 0
l = []
cmd> # Fill it with some values.  First at the head
cmd> ih dolphin
l = [dolphin]
cmd> ih bear
l = [bear dolphin]
cmd> ih gerbil
l = [gerbil bear dolphin]
cmd> # Now at the tail
cmd> it meerkat
l = [gerbil bear dolphin meerkat]
cmd> it bear
l = [gerbil bear dolphin meerkat bear]
cmd> # Reverse it
cmd> reverse
l = [bear meerkat dolphin bear gerbil]
cmd> # See how long it is
cmd> size
Queue size = 5
l = [bear meerkat dolphin bear gerbil]
cmd> # Delete queue.  Goes back to a NULL queue.
cmd> free
l = NULL
cmd> # Exit program
cmd> quit
Freeing queue
==450650== 5 bytes in 1 blocks are still reachable in loss record 1 of 3
==450650==    at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==450650==    by 0x4A5250E: strdup (strdup.c:42)
==450650==    by 0x111024: linenoiseHistoryAdd (linenoise.c:1236)
==450650==    by 0x111BB7: linenoiseHistoryLoad (linenoise.c:1325)
==450650==    by 0x10CC9B: main (qtest.c:1124)
==450650== 
==450650== 97 bytes in 19 blocks are still reachable in loss record 2 of 3
==450650==    at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==450650==    by 0x4A5250E: strdup (strdup.c:42)
==450650==    by 0x110F98: linenoiseHistoryAdd (linenoise.c:1236)
==450650==    by 0x111BB7: linenoiseHistoryLoad (linenoise.c:1325)
==450650==    by 0x10CC9B: main (qtest.c:1124)
==450650== 
==450650== 160 bytes in 1 blocks are still reachable in loss record 3 of 3
==450650==    at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==450650==    by 0x110FE4: linenoiseHistoryAdd (linenoise.c:1224)
==450650==    by 0x111BB7: linenoiseHistoryLoad (linenoise.c:1325)
==450650==    by 0x10CC9B: main (qtest.c:1124)
==450650==

發現均為 linenoiseHistoryLoad 所呼叫的 linenoiseHistoryAdd 中直接或間接呼叫的 malloc 未釋放。

追查後發現，有一 freeHistory 函式會負責釋放 history 相關物件，其會間接被註冊為當程序結束時的函式（ atexit ）。 atexit 其在有輸入檔的情況下並不會被呼叫到。見下方函式實做。

bool run_console(char *infile_name)
{
    if (!push_file(infile_name)) {
        report(1, "ERROR: Could not open source file '%s'", infile_name);
        return false;
    }

    if (!has_infile) {
        char *cmdline;
        while (noise && (cmdline = linenoise(prompt)) != NULL) {
            interpret_cmd(cmdline);
            linenoiseHistoryAdd(cmdline);       /* Add to the history. */
            linenoiseHistorySave(HISTORY_FILE); /* Save the history on disk. */
            linenoiseFree(cmdline);
        }
        if (!noise)
            while (!cmd_done())
                cmd_select(0, NULL, NULL, NULL, NULL);
    } else {
        while (!cmd_done())
            cmd_select(0, NULL, NULL, NULL, NULL);
    }

    return err_cnt == 0;
}

即，當沒有輸入檔時， has_infile 為非，函式會直接執行 else 部份，而不會執行到會間接呼叫到 atexit() 的 linenoise() 。

欲避免此情形解法至少有二。

無論如何強制呼叫 atexit
在沒有輸入檔的情況下不在主函式呼叫類 linenoiseHistoryLoad 的函式

其中第二種作法較為合理。因此嘗試改寫主函式。

int main(int argc, char *argv[])
{
...
+   if (!infile_name) {
        /* Trigger call back function(auto completion) */
        linenoiseSetCompletionCallback(completion);

        linenoiseHistorySetMaxLen(HISTORY_LEN);
        linenoiseHistoryLoad(HISTORY_FILE); /* Load the history at startup */
+   }
...
}

再次編譯後發現錯誤被解決了。

隨後根據 AmyLin0210 的開發紀錄及 #74 ，發現我尚未考慮到在錯誤檔名下亦會有記憶體洩漏。根據上述連結，再次更改主函式的部份實做。

int main(int argc, char *argv[])
{
...
-   ok = ok && finish_cmd();
+   ok = finish_cmd() && ok;
...
}

如此一來便解決目前已發現的記憶體洩漏問題了。

視覺化記憶體用量（ Massif ）

在此針對修正前及修正後的記憶體用量做出觀察，在此以 ./qtest -f ./traces/trace-eg.cmd 指令作為範例。

以下為修正前的數據。

運用 ms_print 工具所印出的圖表

--------------------------------------------------------------------------------
Command:            ./qtest -f ./traces/trace-eg.cmd
Massif arguments:   (none)
ms_print arguments: massif.out.564249
--------------------------------------------------------------------------------


    KB
12.08^                                                                    @#  
     |                                                           :@:::@:::@#  
     |                                                  ::@::::::@@:::@:: @#: 
     |                                                  ::@::::::@@:::@:: @#: 
     |                                                  ::@::::::@@:::@:: @#: 
     |                                                  ::@::::::@@:::@:: @#: 
     |                                                  ::@::::::@@:::@:: @#: 
     |                                                  ::@::::::@@:::@:: @#: 
     |                                                  ::@::::::@@:::@:: @#: 
     |                                                  ::@::::::@@:::@:: @#: 
     |                                                ::::@::::::@@:::@:: @#: 
     |                                                ::::@::::::@@:::@:: @#: 
     |                                                ::::@::::::@@:::@:: @#: 
     |                                                ::::@::::::@@:::@:: @#: 
     |                                                ::::@::::::@@:::@:: @#: 
     |                                                ::::@::::::@@:::@:: @#: 
     |                                                ::::@::::::@@:::@:: @#: 
     |                                                ::::@::::::@@:::@:: @#: 
     |                                                ::::@::::::@@:::@:: @#:@
     |                                              :@::::@::::::@@:::@:: @#:@
   0 +----------------------------------------------------------------------->ki
     0                                                                   362.6

Number of snapshots: 80
 Detailed snapshots: [4, 22, 43, 48, 57, 67, 68 (peak), 78]

運用 Massif.js 所視覺化的圖表。

./qtest -f ./traces/trace-eg.cmd

由此二圖可見末端未完全歸零。

以下為修正後的數據。

運用 ms_print 工具所印出的圖表

--------------------------------------------------------------------------------
Command:            ./qtest -f ./traces/trace-eg.cmd
Massif arguments:   (none)
ms_print arguments: massif.out.564872
--------------------------------------------------------------------------------


    KB
11.45^                                                                    #   
     |                                                           : :::@:::#:  
     |                                                 ::@:@::::::::::@:: #:: 
     |                                                 ::@:@::::::::::@:: #:: 
     |                                                 ::@:@::::::::::@:: #:: 
     |                                                 ::@:@::::::::::@:: #:: 
     |                                                 ::@:@::::::::::@:: #:: 
     |                                                 ::@:@::::::::::@:: #:: 
     |                                                 ::@:@::::::::::@:: #:: 
     |                                                 ::@:@::::::::::@:: #:: 
     |                                                 ::@:@::::::::::@:: #:: 
     |                                                 ::@:@::::::::::@:: #:: 
     |                                                 ::@:@::::::::::@:: #:: 
     |                                                 ::@:@::::::::::@:: #:: 
     |                                                 ::@:@::::::::::@:: #:: 
     |                                                 ::@:@::::::::::@:: #:: 
     |                                                 ::@:@::::::::::@:: #:: 
     |                                                 ::@:@::::::::::@:: #:: 
     |                                                 ::@:@::::::::::@:: #:: 
     |                                                @::@:@::::::::::@:: #:::
   0 +----------------------------------------------------------------------->ki
     0                                                                   353.3

Number of snapshots: 66
 Detailed snapshots: [3, 11, 19, 45, 52, 55 (peak), 65]

運用 Massif.js 所視覺化的圖表

./qtest -f ./traces/trace-eg.cmd

由此二圖可見末端完全歸零。

tinyynoob

2022/02/21 15:41:49

Nice! This helps. (Edited)

Jim Huang

2022/02/23 15:32:16

碼~~

依據國家教育研究院，"pseudo code" 翻譯為「虛擬碼」: https://terms.naer.edu.tw/detail/1218292/ # 其實中華人民共和國境內早期也翻譯為「虛擬碼」，畢竟台灣的資訊科技起得早，後來很多詞彙重新「被翻譯」(跟所謂的「海歸」有關)，就變得詞不達意 (Edited)

2022q1 Homework1 (lab0)

作業要求

環境

開發紀錄

事先準備

實做佇列（ queue.c ）

q_new

q_free

q_size

q_insert_head

q_insert_tail

q_swap

q_reverse

q_remove_head

q_remove_tail

q_delete_dup

q_delete_mid

q_sort

引入 lib/list_sort.c