2022q1 Homework1 (lab0)

contributed by < linjohnss >

作業要求

針對 Queue 的操作

滿足 $ make test 自動評分系統的所有項目
也可以用 $ ./qtest -f traces/trace-XX-CAT.cmd 來針對單一項目測試

• q_new: 建立新的「空」佇列
• q_free: 釋放佇列所佔用的記憶體
• q_insert_head: 在佇列開頭 (head) 插入 (insert) 給定的新節點 (以 LIFO 準則)
• q_insert_tail: 在佇列尾端 (tail) 插入 (insert) 給定的新節點 (以 FIFO 準則)
• q_remove_head: 在佇列開頭 (head) 移去 (remove) 給定的節點
• q_release_element: 釋放特定節點的記憶體空間
• q_size: 計算目前佇列的節點總量
• q_delete_mid: 移走佇列中間的節點
• q_delete_dup: 在已經排序的狀況，移走佇列中具備重複內容的節點
• q_swap: 交換佇列中鄰近的節點
• q_reverse: 以反向順序重新排列鏈結串列，該函式不該配置或釋放任何鏈結串列節點，換言之，它只能重排已經存在的節點
• q_sort: 以遞增順序來排序鏈結串列的節點

在 qtest 提供新的命令 shuffle

允許藉由 Fisher–Yates shuffle 演算法，對佇列中所有節點進行洗牌 (shuffle) 操作

在 qtest 提供新的命令 web

提供 web 伺服器功能，注意: web 伺服器運作過程中，qtest 仍可接受其他命令

• 可依據前述說明，嘗試整合 tiny-web-server

引入 lib/list_sort.c 至 lab0-c 專案

研讀 Linux 核心原始程式碼的 lib/list_sort.c 並嘗試引入到 lab0-c 專案，比較你自己實作的 merge sort 和 Linux 核心程式碼之間效能落差

運用 Valgrind 排除 qtest 實作的記憶體錯誤

運用 Valgrind 排除 qtest 實作的記憶體錯誤，並透過 Massif 視覺化 “simulation” 過程中的記憶體使用量，需要設計對應的實驗

開發環境

$ gcc --version
gcc (Ubuntu 9.3.0-17ubuntu1~20.04) 9.3.0

$ lscpu
Architecture:                    x86_64
CPU op-mode(s):                  32-bit, 64-bit
Byte Order:                      Little Endian
Address sizes:                   39 bits physical, 48 bits virtual
CPU(s):                          8
On-line CPU(s) list:             0-7
Thread(s) per core:              2
Core(s) per socket:              4
Socket(s):                       1
NUMA node(s):                    1
Vendor ID:                       GenuineIntel
CPU family:                      6
Model:                           142
Model name:                      Intel(R) Core(TM) i5-8250U CPU @ 1.60GHz
Stepping:                        10
CPU MHz:                         1800.000
CPU max MHz:                     3400.0000
CPU min MHz:                     400.0000
BogoMIPS:                        3600.00
Virtualization:                  VT-x
L1d cache:                       128 KiB
L1i cache:                       128 KiB
L2 cache:                        1 MiB
L3 cache:                        6 MiB
NUMA node0 CPU(s):               0-7

針對 Queue 的操作

q_size

db70a3

int q_size(struct list_head *head)
{
    if (!head)
        return 0;

    int len = 0;
    struct list_head *li;

    list_for_each (li, head)
        len++;
    return len;
}

根據作業說明進行 queue 長度計算的實作。

• 回傳 queue 內 element 的數量。
• 如果 queue 為 NULL 或 empty，則回傳 0。

q_new

0a8131

struct list_head *q_new()
{
    struct list_head *head = malloc(sizeof(struct list_head));
    // malloc return NULL if allocate failed.
    if (head)
        INIT_LIST_HEAD(head);
    
    return head;
}

利用 list.h 裡的函式 INIT_LIST_HEAD 來初始化 head。
當無法分配空間時 molloc 會回傳 NULL，因此需要在 molloc 後檢查 head 是否為 NULL。

q_free

void q_free(struct list_head *l)
{
    if (!l)
        return;

    // traverse all entries and free the entry and its value
    element_t *entry, *safe;
    list_for_each_entry_safe (entry, safe, l, list) {
        free(entry->value);
        free(entry);
    }
    free(l);
}

利用 list.h 裡的函式 list_for_each_entry_safe 來走訪 list 中的 element，並釋放其佔用的記憶體。

9cd1fa

原先為用 free 實做得的部份，可以改用 q_release_element 來代替，進而提昇程式碼精簡度。

void q_free(struct list_head *l)
{
    if (!l)
        return;

    // traverse all entries and free the entry and its value
    element_t *entry, *safe;
    list_for_each_entry_safe (entry, safe, l, list)
        q_release_element(entry);
    free(l);
}

q_insert_head

0a8131

bool q_insert_head(struct list_head *head, char *s)
{
    if (!head)
        return false;

    element_t *node = malloc(sizeof(element_t));
    if (!node)
        return false;

    // allocate string space
    size_t length = strlen(s);
    node->value = malloc(length + 1);
    if (!node->value) {
        free(node);
        return false;
    }


    // copy the string into space
    strncpy(node->value, s, length);
    node->value[length] = '\0';

    // add new node in begining of head
    list_add(&node->list, head);

    return true;
}

由於 strlen 不會算到結束字元\0，因此要+1用來放結束字元。

當無法分配 node->value 的空間時，除了回傳 false 外，還要釋放 node 的空間。

q_insert_tail

0a8131

bool q_insert_tail(struct list_head *head, char *s)
{
    if (!head)
        return false;

    element_t *node = malloc(sizeof(element_t));
    if (!node)
        return false;

    // allocate string space
    size_t length = strlen(s);
    node->value = malloc(length + 1);
    if (!node->value) {
        free(node);
        return false;
    }

    // copy the string into space
    strncpy(node->value, s, length);
    node->value[length] = '\0';

    // add new node in begining of head
    list_add_tail(&node->list, head);

    return true;
}

同 q_insert_head 改用 list_add_tail 加入 list

q_reverse

0cf3af

void q_reverse(struct list_head *head)
{
    if (!head)
        return;
    else if (list_empty(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;
}

利用 list_for_each_safe 走訪 list 中的 node，並將該 node 的 prev 以及 next 交換。
走訪完畢後，需要將 head->next 與 head->prev 交換。

2aa8d7

void q_reverse(struct list_head *head)
{
    if (!head)
        return;
    else if (list_empty(head))
        return;

    struct list_head *node, *safe;
    list_for_each_safe (node, safe, head) {
        node->next = node->prev;
        node->prev = safe;
    }
    head->next = head->prev;
    head->prev = safe;
}

參考 Kevin-Shih 的開發紀錄 提到使用 list_for_each_safe 時，可以利用 safe 紀錄的下一個節點替代 tmp，因此根據此特性作修改。

q_remove_head

e60602

element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
    if (!head || list_empty(head))
        return NULL;

    element_t *ptr = list_first_entry(head, element_t, list);
    list_del_init(&ptr->list);
    size_t length = strlen(ptr->value);
    if (sp) {
        length = length > bufsize ? bufsize : length;
        strncpy(sp, ptr->value, length);
        sp[length] = '\0';
    }
    return ptr;
}

先透過 list_first_entry 找到第一個 element，接著利用 list_del_init 移除。
若 sp 不為 NULL 則將 element 的 value 複製到 sp（須判斷 vlaue 與 bufsize 的大小）。

3edcaf

element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
    if (!head || list_empty(head))
        return NULL;

    element_t *ptr = list_first_entry(head, element_t, list);
    list_del_init(&ptr->list);
    size_t length = strlen(ptr->value);
    if (sp) {
        length = length > bufsize - 1 ? bufsize - 1 : length;
        strncpy(sp, ptr->value, length);
        sp[length] = '\0';
    }
    return ptr;
}

把比較值 bufsize 改為 bufsize -1，因為要留一個字元存取 Null-terminated。

q_remove_tail

e60602

element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize)
{
    if (!head || list_empty(head))
        return NULL;

    element_t *ptr = list_last_entry(head, element_t, list);
    list_del_init(&ptr->list);
    size_t length = strlen(ptr->value);
    if (sp) {
        length = length > bufsize ? bufsize : length;
        strncpy(sp, ptr->value, length);
        sp[length] = '\0';
    }
    return ptr;
}

同 q_remove_head，改用 list_last_entry 找到最後一個 element。

3edcaf

element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize)
{
    if (!head || list_empty(head))
        return NULL;

    element_t *ptr = list_last_entry(head, element_t, list);
    list_del_init(&ptr->list);
    size_t length = strlen(ptr->value);
    if (sp) {
        length = length > bufsize - 1 ? bufsize - 1 : length;
        strncpy(sp, ptr->value, length);
        sp[length] = '\0';
    }
    return ptr;
}

把比較值 bufsize 改為 bufsize -1，因為要留一個字元存取 Null-terminated。

q_delete_mid

3edcaf

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 NULL;
    element_t *ptr;
    struct list_head *rear, *front;
    rear = head->prev;
    front = head->next;
    while (front != rear && front->next != rear) {
        front = front->next;
        rear = rear->prev;
    }
    list_del_init(front);
    ptr = list_entry(front, element_t, list);
    q_release_element(ptr);
    return true;
}

利用兩個指標 rear、front 指向 list 的頭尾，兩個指標反向移動，當指標發生交會時，及找到 list 的中間值。

q_swap

eeca3c

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 *right, *left;
    left = head->next;
    right = left->next;
    while (left != head && right != head) {
        list_move(left, right);
        left = left->next;
        right = left->next;
    }
}

根據 leetcode 解釋，是將 queue 分兩兩一組，並進行交換。

1. 首先，判斷當 head 不存在、空的或是只有一個 node，則什麼都不用作。
2. 利用兩個指標 left、right 分別指向開頭相鄰的左右兩個 node。
3. 將這兩個 node 用 list_move 交換。此時，原本在左邊的 node 就會移到右邊。
4. 因此，下一組的指標即為 left = left->next、right = right->next。
5. 重複 3.、4. 步驟，直到無法在兩兩一組為止 left == head || right == head。

原本的 double circular link list 結構，順序為 1、2、3、4。

left、right 指向前兩個相鄰的 node。

將這兩個 node 用 list_move 交換。因此，left 會成為右側的 node。

接著，left = left->next, right = right->next，並重複這兩個動作，直到沒辦法相鄰兩兩一組為止。

即為相鄰兩兩一組交換的成果。

mergeTwoList ,mergesort_list and q_sort

eeca3c

struct list_head *mergeTwoList(struct list_head *L1, struct list_head *L2)
{
    struct list_head *head = NULL, **ptr = &head, **node = NULL;

    for (element_t *ele1, *ele2; L1 && L2; *node = (*node)->next) {
        ele1 = list_entry(L1, element_t, list);
        ele2 = list_entry(L2, element_t, list);
        node = (strcmp(ele1->value, ele2->value) <= 0) ? &L1 : &L2;
        *ptr = *node;
        ptr = &(*ptr)->next;
    }
    *ptr = (struct list_head *) ((__UINTPTR_TYPE__) L1 | (__UINTPTR_TYPE__) L2);
    //*ptr = L1 ? L1 : L2;
    return head;
}

struct list_head *mergesort_list(struct list_head *head)
{
    if (!head || !head->next)
        return head;
    struct list_head *slow = head;
    for (struct list_head *fast = head->next; fast && fast->next;
         fast = fast->next->next)
        slow = slow->next;
    struct list_head *mid = slow->next;
    slow->next = NULL;
    struct list_head *left = mergesort_list(head), *right = mergesort_list(mid);
    return mergeTwoList(left, right);
}

void q_sort(struct list_head *head)
{
    if (!head || list_empty(head) || list_is_singular(head))
        return;

    head->prev->next = NULL;

    head->next = mergesort_list(head->next);
    struct list_head *ptr;
    for (ptr = head; ptr->next; ptr = ptr->next)
        ptr->next->prev = ptr;
    ptr->next = head;
    head->prev = ptr;
}

利用 Merge Sort 對 Queue 進行排序，因為 Merge Sort 為 O(nlogn)，可以通過 trace-14 與 trace-15。

q_delete_dup

d38186

bool q_delete_dup(struct list_head *head)
{
    // https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/
    if (!head || list_empty(head))
        return false;
    element_t *entry, *safe;
    list_for_each_entry_safe (entry, safe, head, list) {
        if (&safe->list != head && !strcmp(entry->value, safe->value)) {
            list_del(&entry->list);
            q_release_element(entry);
        }
    }
    return true;
}

利用 list_for_each_entry_safe 走訪整個 Queue，當 entry->value 與 safe->value（下一個 node 的值） 相同時，刪除 entry->value。

此作法是刪除所有重複的 node 直到剩下單獨一個 node，並不符合題意，須要刪除所有重複的 node。

bool q_delete_dup(struct list_head *head)
{
    // https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/
    if (!head || list_empty(head))
        return false;
    element_t *entry, *safe;
    bool left = false;  // use left to delete the last duplicate element
    list_for_each_entry_safe (entry, safe, head, list) {
        if (&safe->list != head && !strcmp(entry->value, safe->value)) {
            list_del(&entry->list);
            q_release_element(entry);
            left = true;
        } else if (left) {
            list_del(&entry->list);
            q_release_element(entry);
            left = false;
        }
    }
    return true;
}

為了刪除留下的一個 element，先宣告一個變數 left，用來判斷是否為留下來的重複 element（當重複發生時，令 left 為 true。如此一來，若與下一個 safe->value 不相同，但是left 為 true則代表為留下來的element），並將其刪除。

在 qtest 提供新的命令 shuffle

shuffle 實作

4532cd
閱讀 Fisher–Yates shuffle 演算法，在 queue.c 加入函式 q_shuffle：

void q_shuffle(struct list_head *head)
{
    if (!head || list_empty(head) || list_is_singular(head))
        return;

    struct list_head *i = head, *j;
    int r;
    for (size_t length = q_size(head); length > 0; length--) {
        j = head->next;
        for (r = rand() % length; r > 0; r--)
            j = j->next;

        list_move_tail(i->prev, j);
        list_move_tail(j, i);
        i = i->prev;
    }
    
}

如何加入新的指令（command）

4532cd
在 qtest.c 先宣告 q_shuffle 函式其定義在 queue.c 中。

void q_shuffle(struct list_head *head);

接著在 console_init() 加入一行

ADD_COMMAND(shuffle, "                | Shuffle all nodes in queue");

並加入 do_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();

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

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

在 qtest 提供新的命令 web

加入 tiny.c 至 lab0-c

將 tiny.c 加入 lab0-c，並修改 Makefile 來編譯它。在 Makefile 的 OBJS 加入 tiny.o 即可。

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

加入 tiny.h 至 lab0-c

宣告兩個全域變數 listenfd 與 noise，提供 console.c 讀取。

#ifndef TINY_H
#define TINY_H

#include <netinet/in.h>
#include <stdbool.h>

extern int listenfd;
extern bool noise;
/* Simplifies calls to bind(), connect(), and accept() */
typedef struct sockaddr SA;

void socket_init();

char *process(int fd, struct sockaddr_in *clientaddr);

#endif

socket_init

改寫自 tiny.c 的 main，只需保留啟動 server 與忽略 SIGPIPE 訊號的部份。並且將 socket 改為 non-blocking，防止程式停止接收使用者輸入。

void socket_init()
{
    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);
    }
    // Ignore SIGPIPE signal, so if browser cancels the request, it
    // won't kill the whole process.
    signal(SIGPIPE, SIG_IGN);
    int flags = fcntl(listenfd, F_GETFL);
    fcntl(listenfd, F_SETFL, flags | O_NONBLOCK);
    return;
}

process

參照 lab0-c 作業提示改寫。原先給的程式碼無法通過 pre-commit。

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);
    int status = 200;
    // handle_request(fd, req.filename);

    char *p = req.filename;
    /* Change '/' to ' ' */
    if (*p) {
        while ((*p) != '\0') {
            ++p;
            if (*p == '/') {
                *p = ' ';
            }
        }
    }
#ifdef LOG_ACCESS
    log_access(status, clientaddr, &req);
#endif
    char *ret = malloc(strlen(req.filename) + 1);
    strncpy(ret, req.filename, strlen(req.filename) + 1);

    return ret;
}

TODO：handle_request(fd, req.filename)，負責處理 reply message。

cmd_select

根據 lab0-c 作業提示，cmd_select 可以滿足同時處理命令列輸入與網頁伺服器。因此我們根據提示下去改。

int cmd_select(int nfds,
           fd_set *readfds,
           fd_set *writefds,
           fd_set *exceptfds,
           struct timeval *timeout)
{
    int infd;
    fd_set local_readset;

    if (cmd_done())
        return 0;
        
    if (!block_flag) {
        /* 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 (listenfd != -1)
+           FD_SET(listenfd, readfds);

        if (infd == STDIN_FILENO && prompt_flag) {
            printf("%s", prompt);
            fflush(stdout);
            prompt_flag = true;
        }

        if (infd >= nfds)
            nfds = infd + 1;
+       if (listenfd >= nfds)
+           nfds = listenfd + 1;
    }
    if (nfds == 0)
        return 0;
        
    int result = select(nfds, readfds, writefds, exceptfds, timeout)
    if (result <= 0)
        return result;

    infd = buf_stack->fd;
    if (readfds && FD_ISSET(infd, readfds)) {
        /* Commandline input available */
        FD_CLR(infd, readfds);
        result--;
-       if (has_infile) {
        char *cmdline;
        cmdline = readline();
        if (cmdline)
            interpret_cmd(cmdline);
-       }
+    } else if (readfds && FD_ISSET(listenfd, readfds)) {
+       FD_CLR(listenfd, readfds);
+       result--;
+       int connfd;
+       struct sockaddr_in clientaddr;
+       socklen_t clientlen = sizeof(clientaddr);
+       connfd = accept(listenfd,(SA *) &clientaddr, &clientlen);

+       char *p = process(connfd, &clientaddr);
+       if (p)
+           interpret_cmd(p);
+       free(p);
+       close(connfd);
+   }
    return result;
}

加入 web 命令

這次嘗試在 console.c 中加入 command。先實做 do_web 函式。

static bool do_web(int argc, char *argv[])
{
    socket_init();
    noise = false;
    return true;
}

接著在 init_cmd() 中加入一行。

ADD_COMMAND(web, "                | Response to web client");

執行成果

cmd> web
listen on port 9999, fd is 3
cmd> accept request, fd is 4, pid is 219443
127.0.0.1:56212 200 - 'new' (text/plain)
l = []
cmd> accept request, fd is 4, pid is 219443
127.0.0.1:56214 200 - 'ih bear' (text/plain)
l = [bear]
cmd> accept request, fd is 4, pid is 219443
127.0.0.1:56216 200 - 'ih tiger' (text/plain)
l = [tiger bear]
cmd> accept request, fd is 4, pid is 219443
127.0.0.1:56218 200 - 'ih dolphin' (text/plain)
l = [dolphin tiger bear]
cmd> accept request, fd is 4, pid is 219443
127.0.0.1:56222 200 - 'reverse' (text/plain)
l = [bear tiger dolphin]
cmd> accept request, fd is 4, pid is 219443
127.0.0.1:56224 200 - 'rh bear' (text/plain)
Removed bear from queue
l = [tiger dolphin]
cmd> accept request, fd is 4, pid is 219443
127.0.0.1:56226 200 - 'rh tiger' (text/plain)
Removed tiger from queue
l = [dolphin]
cmd> accept request, fd is 4, pid is 219443
127.0.0.1:56228 200 - 'rh dolphin' (text/plain)
Removed dolphin from queue
l = []
cmd> 

引入 lib/list_sort.c 至 lab0-c 專案

研讀 lib/list_sort.c

引入 queu.c

0399d2

1. 將 lib/list_sort.c 改寫成 linux_sort.h，並在 queue.c include
2. 宣告函式 string_cmp 與 q_linux_sort

int string_cmp(void *t,const struct list_head *L1,const struct list_head *L2)
{
    return strcmp(list_entry(L1, element_t, list)->value, list_entry(L2, element_t, list)->value);
}

void q_linux_sort(struct list_head *head)
{
    if (!head || list_empty(head) || list_is_singular(head))
        return;
    list_sort(NULL, head, string_cmp);
}

加入命令 LinuxSort

0399d2

在 qtest.c 裡加入 do_LinuxSort

bool do_LinuxSort(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 sort on null queue");
    error_check();

    int cnt = q_size(l_meta.l);
    if (cnt < 2)
        report(3, "Warning: Calling sort on single node");
    error_check();

    set_noallocate_mode(true);
    if (exception_setup(true))
        q_linux_sort(l_meta.l);
    exception_cancel();
    set_noallocate_mode(false);

    bool ok = true;
    if (l_meta.size) {
        for (struct list_head *cur_l = l_meta.l->next;
             cur_l != l_meta.l && --cnt; cur_l = cur_l->next) {
            /* Ensure each element in ascending order */
            /* FIXME: add an option to specify sorting order */
            element_t *item, *next_item;
            item = list_entry(cur_l, element_t, list);
            next_item = list_entry(cur_l->next, element_t, list);
            if (strcasecmp(item->value, next_item->value) > 0) {
                report(1, "ERROR: Not sorted in ascending order");
                ok = false;
                break;
            }
        }
    }

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

接著在 console_init() 加入一行

ADD_COMMAND(LinuxSort, "                | Use linux list_sort to sort queue in ascending order");

比較自己寫的 merge sort 與 linux 的 list_sort 效能落差

撰寫一個用於比較 merge sort 與 linux 的 list_sort 效能落差的 .cmd 檔案

cmd> # Test of sort and LinuxSort
cmd> option fail 0
cmd> option malloc 0
cmd> new
l = []
cmd> ih gerbil 100000
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> it bear 100000
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> ih dolphin 100000
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 = [bear bear bear bear bear bear bear bear bear bear bear bear bear bear bear bear bear bear bear bear bear bear bear bear bear bear bear bear bear bear ... ]
cmd> time sort
l = [bear bear bear bear bear bear bear bear bear bear bear bear bear bear bear bear bear bear bear bear bear bear bear bear bear bear bear bear bear bear ... ]
Delta time = 0.130
cmd> time LinuxSort
l = [bear bear bear bear bear bear bear bear bear bear bear bear bear bear bear bear bear bear bear bear bear bear bear bear bear bear bear bear bear bear ... ]
Delta time = 0.065
Freeing queue

從上述成果，可以看出 Linux 的 list_sort 相較我的 merge sort 快了一倍。

運用 Valgrind 排除 qtest 實作的記憶體錯誤

command history 錯誤

首先，執行 qtest 並開啟 Valgrind

$ make valgrind

可以看到報告不斷顯示 blocks are still reachable，代表在 linenoise.c 的 linenoiseHistoryAdd 有記憶體未被釋放。

==79220== 4 bytes in 1 blocks are still reachable in loss record 1 of 3
==79220==    at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==79220==    by 0x4A7A50E: strdup (strdup.c:42)
==79220==    by 0x111237: linenoiseHistoryAdd (linenoise.c:1236)
==79220==    by 0x111DCA: linenoiseHistoryLoad (linenoise.c:1325)
==79220==    by 0x10CBEE: main (qtest.c:1122)

根據 Valgrind 報告，找到 linenoise.c 的這行出現問題。在 qtest.c 執行 linenoiseHistoryLoad 會使用到。

    linecopy = strdup(line);

根據作業說明，still reachable 代表程式結束時有未釋放的記憶體，不過卻還有指標指著，通常會發生在 global 變數。

strdup 會進行 malloc，而在 linenoise.c 中複製後的字串會被放入陣列 history。而這個 history 會在
從 linenoise.c 中可以發現有一個函式 freeHistory 會釋放 history 的記憶體。

static void freeHistory(void)
{
    if (history) {
        int j;

        for (j = 0; j < history_len; j++)
            free(history[j]);
        free(history);
    }
}

接著，我們從 console.c 中的 run_console 找到當 has_infile ＝ true 時，並不會對 history 有任何改動（包含釋放記憶體空間）。

has_infile ＝ true 代表為 command 為從檔案輸入的。

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 ((cmdline = linenoise(prompt)) != NULL) {
            interpret_cmd(cmdline);
            linenoiseHistoryAdd(cmdline);       /* Add to the history. */
            linenoiseHistorySave(HISTORY_FILE); /* Save the history on disk. */
            linenoiseFree(cmdline);
        }
    } else {
        while (!cmd_done())
            cmd_select(0, NULL, NULL, NULL, NULL);
    }

    return err_cnt == 0;
}

然後我們可以在 qtest.c 中發現，無論 command 是否為從檔案輸入它都會將 command history 載入（linenoiseHistoryLoad），進而導致記憶體空間沒有被釋放。

    linenoiseSetCompletionCallback(completion);

    linenoiseHistorySetMaxLen(HISTORY_LEN);
    linenoiseHistoryLoad(HISTORY_FILE); /* Load the history at startup */
    set_verblevel(level);
    if (level > 1) {
        set_echo(true);
    }
    if (logfile_name)
        set_logfile(logfile_name);

    add_quit_helper(queue_quit);

    bool ok = true;
    ok = ok && run_console(infile_name);
    ok = ok && finish_cmd();

    return ok ? 0 : 1;
}

針對上述觀察，我們可以改由讀取鍵盤指令的方式判斷是否有記憶體錯誤發生。發現確實沒有發生錯誤，驗證了我們的觀察。

$ valgrind -q --leak-check=full ./qtest

因此，我們可以藉由判斷 command 是否為從檔案（infile_name）輸入來判斷要不要使用 command history。重新執行 make valgrind 後就沒有回報記憶體錯誤了。

    linenoiseSetCompletionCallback(completion);

    linenoiseHistorySetMaxLen(HISTORY_LEN);
    /* Do not load history when command input is from file*/
    if (!infile_name)
        linenoiseHistoryLoad(HISTORY_FILE); /* Load the history at startup */
    set_verblevel(level);
    if (level > 1) {
        set_echo(true);
    }
    if (logfile_name)
        set_logfile(logfile_name);

    add_quit_helper(queue_quit);

    bool ok = true;
    ok = ok && run_console(infile_name);
    ok = ok && finish_cmd();

    return ok ? 0 : 1;
}

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

解釋 Student’s t-distribution

Student’s t-distribution，簡稱 t 分佈，改善 z 檢定在小樣本誤差大的問題。