2022q1 Homework1 (lab0)

contributed by < sternacht >

實驗環境

$ 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.[ch] 和連帶的檔案，測試後用 Git 管理各項修改，記得也該實作 q_sort 函式。

• q_new: 創一個空的 queue
• q_free: 釋放掉一個 queue
• q_insert_head: 在 head 插入一個 element (LIFO)
• q_insert_tail: 在 tail 插入一個 element (FIFO), O(1)
• q_remove_head: 把 head 的 element 移除
• q_remove_tail: 把 tail 的 elemeny 移除
• q_size: return queue 的大小
• q_delete_mid: 把位在中間的 element 刪除
• q_reverse: 將 queue 反轉，不配置或釋放任何的 element
• q_delete_dup: 將 queue 中有重複字串出現的所有節點刪除
• q_swap: 將 queue 的節點兩兩一組交換順序
• q_sort: 將 queue 由小排到大, sort by nature sort
• 在 qtest 提供新的命令 shuffle，允許藉由 Fisher–Yates shuffle 演算法，對佇列中所有節點進行洗牌 (shuffle) 操作
• 在 qtest 提供新的命令 web，提供 web 伺服器功能，注意: web 伺服器運作過程中，qtest 仍可接受其他命令
• 解釋 select 系統呼叫在本程式的使用方式，並分析 console.c 的實作，說明其中運用 CS:APP RIO 套件 的原理和考量點。

列出其他在作業要求中出現的操作，例如 LeetCode 題目。

jserv

開發過程

q_new

向記憶體索取大小為 element_t 的空間，並檢查是否成功，若非則回傳 NULL ，是則進行初始化並回傳

struct list_head *q_new()
{    
    element_t *new = malloc(sizeof(element_t));
    if (!new)
        return NULL;
    new->value = NULL;
    INIT_LIST_HEAD(&(new->list));
    return &(new->list);
}

git commit 時出現以下警告

queue.c:25:5: error: Memory leak: new [memleak]
return &(new->list);
^

修改為

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

q_free

逐個走訪包括 head 在內的 entry 並將其釋放

void q_free(struct list_head *l)
{
    element_t *del = NULL, *safe = NULL;
    list_for_each_entry_safe(del, safe, l, list){
        free(del);
    }
    free(l);
}

原先未考慮到 element 內還有 value 要釋放而出錯，並且在輸入值為 NULL 也沒有進行例外處理，因此修改為

void q_free(struct list_head *l)
{
    if (!l)
        return;
    element_t *del, *safe;
    list_for_each_entry_safe(del, safe, l, list){
        list_del(&(del->list));
        q_release_element(del);
    }
    free(l);
}

q_insert_head

判斷佇列是否存在，否則回傳 false ，是則向記憶體索取大小為 element_t 的空間，失敗則回傳 false ，成功則將 s 的內容複製到節點內，並將該節點放入 queue 的開頭並回傳 true 。

bool q_insert_head(struct list_head *head, char *s)
{
    if (!head)
        return false;
    element_t *new = malloc(sizeof(element_t));
    if (!new)
        return false;
    strcpy(new->value, s);
    list_add(&(new->list), head);
    return true;
}

new 配置時的 new->value 尚未配置記憶體空間，因此 strcpy 會報錯，因此需要先行計算欲放入的字串大小並向記憶體索取適當的空間，然後再用 strncpy 將字串放入。

註 : strcpy 與 strncpy 的差別在於 strcpy 會有 buffer overflow 的問題，因為其不考慮 *dest 是否有足夠空間放下 *src 的字串，而 strncpy 則會透過最後一個參數 count 來限制，但在必要時需自行補上 \0 來做結尾。 參考來源

bool q_insert_head(struct list_head *head, char *s)
{
    if (!head)
        return false;
    element_t *new = malloc(sizeof(element_t));
    if (!new)
        return false;
    size_t len = strlen(s) + 1;
    new->value = malloc(len);
    if (!new->value) {
        free(new);
        return false;
    }
    strncpy(new->value, s, len);
    list_add(&new->list, head);
    return true;
}

q_insert_tail

大致與 q_insert_head 相同，僅節點放置之位置不同。

bool q_insert_head(struct list_head *head, char *s)
{
    if (!head)
        return false;
    element_t *new = malloc(sizeof(element_t));
    if (!new)
        return false;
    strcpy(new->value, s);
    list_add_tail(&new->list, head);
    return true;
}

同 q_insert_head 做修改

bool q_insert_head(struct list_head *head, char *s)
{
    if (!head)
        return false;
    element_t *new = malloc(sizeof(element_t));
    if (!new)
        return false;
    size_t len = strlen(s) + 1;
    new->value = malloc(len);
    if (!(new->value)) {
        free(new);
        return false;
    }
    strncpy(new->value, s, len);
    list_add_tail(&new->list, head);
    return true;
}

q_remove_head

將 queue 中的第一個節點移出 queue 並回傳該節點，同時將節點中的內容複製到 sp 中，若queue 不存在或為空時回傳 NULL 。

element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
    if(!head || list_empty(head))
        return NULL;
    element_t *remove = NULL;
    remove = list_entry (head->next, element_t, list);
    strncpy(sp, remove->value, bufsize);
    head->next = head->next->next;
    return remove;
}

題目上表示 if sp is non-NULL… ，因此加上對 sp 的判斷式。此外，之前對strncpy有誤會，字串末的 \0是要自己加的，連同最後第二行錯誤也一齊修正，修改後如下:

element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
    if (!head || list_empty(head))
        return NULL;
    element_t *remove = list_entry(head->next, element_t, list);
    if (sp != NULL){
        strncpy(sp, remove->value, bufsize);
        sp[bufsize - 1] = '\0';
    }
    list_del_init(&(remove->list));
    return remove;
}

q_remove_tail

大致同 q_remove_head 。

element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize)
{
    if(!head || list_empty(head))
        return NULL;
    element_t *remove = list_entry(head->prev, element_t, list);
    strncpy(sp, remove->value, bufsize);
    head->prev = head->prev->prev;
    return remove;
}

同 q_remove_head 做修改

element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
    if (!head || list_empty(head))
        return NULL;
    element_t *remove = list_entry(head->prev, element_t, list);
    if (sp != NULL){
        strncpy(sp, remove->value, bufsize);
        sp[bufsize - 1] = '\0';
    }
    list_del_init(&(remove->list));
    return remove;
}

q_size

利用一個 counter 逐個計算 queue 中的節點個數(不包含 head )，當 queue 不存在時回傳0

{
    if (!head)
        return 0;
    int len = 0;
    struct list_head *node;
    list_for_each (node, head)
        len++;
    return len;
}

q_delete_mid

利用快慢指標來找出位在中間的節點，因作業要求是在 queue size 為偶數時刪除第

$\lfloor \frac{n}{2}\rfloor$ 個，因此要從 head 開始，而非從 head->next 開始，刪除時先利用 list_del_init 將位處中間的節點 slow 從 queue 中移除，再用 q_free 將該節點的記憶體釋放。

註 : list_del 不會將該節點的 prev, next 指回自身，因此直接用使用 q_free 會有問題，需要先取得整個節點( element_t )後，再進行 free 。

bool q_delete_mid(struct list_head *head)
{
    if (!head || list_empty(head))
        return false;
    struct list_head *slow = head;
    for (struct list_head *fast = head; fast && fast->next; fast->next->next){
        slow = slow->next;
    }
    list_del_init(slow);
    q_free(slow);
    return true;
}

先前撰寫時錯以 singly linked list 的方式來寫，但這樣在 doubly linked list 中會有 infinite loop 的問題發生，因此改成以個數計算的方式來做為迴圈的條件，找出第

$\lfloor \frac{n}{2}\rfloor$ 個節點

bool q_delete_mid(struct list_head *head)
{
    if (!head || list_empty(head))
        return false;
    struct list_head *node = head;
    for (int len = q_size(head); len > 0; len -= 2) {
        node = node->next;
    }
    element_t *del = list_entry(node, element_t, list);
    list_del(node);
    q_release_element(del);
    return true;
}

q_delete_dup

將佇列裡有重複出現的所有字串刪除，當佇列不存在或為空時回傳 false ，若只有一個節點則因不會有重複出現直接回傳 true 。

bool q_delete_dup(struct list_head *head)
{
    if (!head)
        return false;
    if (list_empty(head) || list_is_singular(head))
        return true;
    struct list_head *node = head->next;
    struct list_head *del_q = q_new();
    element_t *entry1 = NULL, *entry2 = NULL;
    int len = q_size(head) - 1;
    while (len > 0) {
        entry1 = container_of(node, element_t, list);
        entry2 = list_entry(node->next, element_t, list);
        if (strcmp(entry1->value, entry2->value) == 0) {
            while (len && strcmp(entry1->value, entry2->value) == 0) {
                list_move(node->next, del_q);
                entry2 = list_entry(node->next, element_t, list);
                len--;
            }
            node = node->next;
            list_move(node->prev, del_q);
        } else {
            node = node->next;
        }
        len--;
    }
    q_free(del_q);
    return true;
}

q_swap

將佇列中的節點兩兩交換位置

void q_swap(struct list_head *head)
{
    if (!head || list_empty(head))
        return;
    struct list_head *lnode = head->next;
    struct list_head *rnode = lnode->next;
    int len = q_size(head);
    while (len > 1) {
        lnode->prev->next = rnode;
        rnode->next->prev = lnode;
        lnode->next = rnode->next;
        rnode->prev = lnode->prev;
        lnode->prev = rnode;
        rnode->next = lnode;
        lnode = lnode->next;
        rnode = lnode->next;
        len -= 2;
    }
    return;
}

使用 List API 改寫為更精簡好讀的程式碼。

jserv

先前對 list_add 有些誤會，仔細想一想才發覺改成這樣做是沒問題的，雖然以指標操作的數量來說並沒有減少，但相比於上方的程式碼來說，更為直觀且好讀。

void q_swap(struct list_head *head)
{
    if (!head || list_empty(head))
        return;
    bool lock = false;
    struct list_head *node = NULL, *safe = NULL;
    list_for_each_safe(node, safe, head) {
        if (lock){
            list_del(node);
            list_add(node, safe->prev->prev);
        }
        lock = !lock;
    }
    return;
}

q_reverse

將佇列中的節點順序反過來

void q_reverse(struct list_head *head)
{
    if (!head || list_empty(head))
        return;
    struct list_head *node, *safe;
    list_for_each_safe (node, safe, head) {
        list_del(node);
        list_add(node, head);
    }
    return;
}

q_sort

將佇列中節點依照字串值由小至大排序

void q_sort(struct list_head *head)
{
    if (!head || list_empty(head) || list_is_singular(head))
        return;
    // list_head is doubly linked list, so make it singly first
    head->prev->next = NULL;
    
    // go mergesort
    head->next = q_mergesort(head->next);
    
    // make queue doubly again
    head->next->prev = head;
    struct list_head *node = head->next;
    while (node->next){
        node = node->next;
    }
    node->next = head;
    head->prev = node;
}

struct list_head *q_mergesort(struct list_head *head)
{
    if (!head || !head->next)
        return head;
    struct list_head *tail = q_split(head);
    head = q_mergesort(head);
    tail = q_mergesort(tail);
    return q_merge(head, tail);
}

struct list_head *q_merge(struct list_head *head, struct list_head *tail)
{
    if (!head)
        return (tail);
    if (!tail)
        return (head);
    if (cmp(head, tail) > 0){
        tail->next = q_merge(head, tail->next);
        tail->next->prev = tail;
        tail->prev = NULL;
        return tail;
    } else {
        head->next = q_merge(head->next, tail);
        head->next->prev = head;
        head->prev = NULL;
        return head;
    }
}

struct list_head *q_split(struct list_head *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 *tmp = slow->next;
    slow->next = NULL;
    return tmp;
}

int cmp(struct list_head *a, struct list_head *b)
{
    element_t *entry1 = list_entry(a, element_t, list);
    element_t *entry2 = list_entry(b, element_t, list);
    return strcmp(entry1->value, entry2->value);
}

以上是用 merge sort 實作，理論上時間複雜度為

$O(n\log n)$ ，而以測試的結果來說，該 sort 實作可以通過第 15 項測試，表示其時間複雜度確實在

$O(n\log n)$ ，然而此 sort 實作在第 14 項測試中會失敗。

接著引入 lib/list_sort.c

void q_sort(struct list_head *head)
{
    // this function is rewrite from list_sort.c
    if (!head || list_empty(head) || list_is_singular(head))
        return;
    struct list_head *list = head->next, *pending = NULL;
    size_t count = 0;
    head->prev->next = NULL;
    do {
        size_t bits;
        struct list_head **tail = &pending;
        for (bits = count; bits & 1; bits >>= 1)
            tail = &(*tail)->prev;
        if (likely(bits)) {
            struct list_head *a = *tail, *b = a->prev;
            a = merge(b, a);
            a->prev = b->prev;
            *tail = a;
        }
        list->prev = pending;
        pending = list;
        list = list->next;
        pending->next = NULL;
        count++;
    } while (list);
    list = pending;
    pending = pending->prev;
    for (;;) {
        struct list_head *next = pending->prev;
        if (!next)
            break;
        list = merge(pending, list);
        pending = next;
    }
    merge_final(head, pending, list);
}

int cmp(struct list_head *a, struct list_head *b)
{
    element_t *entry1 = list_entry(a, element_t, list);
    element_t *entry2 = list_entry(b, element_t, list);
    return strcmp(entry1->value, entry2->value);
}

static struct list_head *merge(struct list_head *a, struct list_head *b)
{
    struct list_head *head, **tail = &head;
    for (;;) {
        if (cmp(a, b) <= 0) {
            *tail = a;
            tail = &a->next;
            a = a->next;
            if (!a) {
                *tail = b;
                break;
            }
        } else {
            *tail = b;
            tail = &b->next;
            b = b->next;
            if (!b) {
                *tail = a;
                break;
            }
        }
    }
    return head;
}

static void merge_final(struct list_head *head,
                        struct list_head *a,
                        struct list_head *b)
{
    struct list_head *tail = head;
    int count = 0;
    for (;;) {
        if (cmp(a, b) <= 0) {
            tail->next = a;
            a->prev = tail;
            tail = a;
            a = a->next;
            if (!a)
                break;
        } else {
            tail->next = b;
            b->prev = tail;
            tail = b;
            b = b->next;
            if (!b) {
                b = a;
                break;
            }
        }
    }
    tail->next = b;
    do {
        if (unlikely(!++count))
            cmp(b, b);
        b->prev = tail;
        tail = b;
        b = b->next;
    } while (b);
    tail->next = head;
    head->prev = tail;
}

從 list_sort.c 改寫的 sort 實作可通過第 14 項測試，觀察兩種 sort function 在 perf top 中的使用情況，主要由兩項函式消耗大部分的資源，第一個是 sort 本身，第二個是 strcmp ，前後兩個相比 strcmp 消耗程度大致相同，因此合理推斷導致第 14 項測試結果出現分歧的原因，就是第一個 sort 實作使用的是 recuresive 的結構，而使得資料量大的時候會出現崩潰。

需要更多分析和實驗，來支持你的論點。

jserv

==59110== Stack overflow in thread #1: can't grow stack to 0x1ffe801000
==59110== Stack overflow in thread #1: can't grow stack to 0x1ffe801000
==59110== Can't extend stack to 0x1ffe8010a8 during signal delivery for thread 1:
==59110==   no stack segment
==59110== 
==59110== Process terminating with default action of signal 11 (SIGSEGV)
==59110==  Access not within mapped region at address 0x1FFE8010A8
==59110== Stack overflow in thread #1: can't grow stack to 0x1ffe801000
==59110==    at 0x10EED6: q_merge (queue.c:313)
==59110==  If you believe this happened as a result of a stack
==59110==  overflow in your program's main thread (unlikely but
==59110==  possible), you can try to increase the size of the
==59110==  main thread stack using the --main-stacksize= flag.
==59110==  The main thread stack size used in this run was 8388608.
==59110== Stack overflow in thread #1: can't grow stack to 0x1ffe801000
==59110== 
==59110== Process terminating with default action of signal 11 (SIGSEGV)
==59110==  Access not within mapped region at address 0x1FFE801F70
==59110== Stack overflow in thread #1: can't grow stack to 0x1ffe801000
==59110==    at 0x4831130: _vgnU_freeres (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_core-amd64-linux.so)
==59110==  If you believe this happened as a result of a stack
==59110==  overflow in your program's main thread (unlikely but
==59110==  possible), you can try to increase the size of the
==59110==  main thread stack using the --main-stacksize= flag.
==59110==  The main thread stack size used in this run was 8388608.
Segmentation fault (core dumped)

利用 valgraind ./qtest ，並執行如 14 項測試中的命令順序 :
new -> ih dolphin 1000000 -> it gerbil 1000000 -> reverse -> sort
其中用 recursive 形式的 sort 實作會跑出以上的訊息，並以 Segmentation fault (core sumped) 的錯誤結束程式。
仔細看看錯誤訊息，可以發現出錯的原因是主程式 main 的 stack 沒有空間了，也就是大名鼎鼎的 stack overflow，這是因為函式在執行的時候，若是遇到要執行其他函式，則會把目前的參數值、變數以及其他函數結束後的返回位址 push 到該函式的 stack 中，直到要繼續執行才會 pop 出來，而也就是因為這個特性，使得 recursive 形式的函式雖然直觀但執行速度慢 (push, pop 都要花時間)，而且還有發生 stack overflow 的風險。

shuffle

將佇列中的節點打亂，演算法參考
以下是直接利用演算法的原理實作的，能夠運作但依然需要改進，尤其是面對巨量資料的時候。

void q_shuffle(struct list_head *head)
{
    if (!head || list_empty(head) || list_is_singular(head))
        return;
    srand(time(0));
    int len = q_size(head);
    struct list_head *tail = head->prev, *node = NULL;
    for (;len > 1; len--) {
        node = head->next;
        for (int i = rand() % len; i > 0; i--){
            node = node->next;
        }
        swap_two_node(node, tail);
        tail = node->prev;
    }
}

void swap_two_node(struct list_head *a, struct list_head *b)
{
    if (a->next == b){
        a->prev->next = b;
        b->next->prev = a;
        a->next = b->next;
        b->prev = a->prev;
        a->prev = b;
        b->next = a;
    } else {
        struct list_head *tmp;
        a->prev->next = b;
        b->prev->next = a;
        tmp = a->prev;
        a->prev = b->prev;
        b->prev = tmp;
        a->next->prev = b;
        b->next->prev = a;
        tmp = a->next;
        a->next = b->next;
        b->next = tmp;
    }
}

因為 queue.h 不能更動的關係，需要額外寫一個 .h 檔來放置函式的宣告，如下，並在 qtest.c 中將其 include 進去

#include "list.h"
#include "queue.h"

void q_shuffle(struct list_head *head);

void swap_two_node(struct list_head *a, struct list_head *b);

原本的演算法中，面對結構簡單的陣列可以達到

$O(n)$ 的時間複雜度，但在結構較複雜且記憶體不連續的 linked list 中，要還原演算法的話就必須花費

$O(n^2)$ 的時間複雜度在逐個尋找節點的過程上。

總是書寫為 linked list，中間不要有連字號。

jserv

而若不考慮完全按照演算法，不用交換 node 的方式來做，則可以不使用 swap 函式，改成如下，在指標的操作上次數會固定，而不需要進行條件判斷

// swap_two_node(node, tail);
// tail = node->prev;
//     |
//     v
list_del(node);
list_add(node, tail->prev);
tail = node;

完全移除 swap_two_node，改為用 list api 來實作

void q_shuffle(struct list_head *head)
{
    if (!head || list_empty(head) || list_is_singular(head))
        return;
    srand(time(0));
    int len = q_size(head);
    struct list_head *tail = head->prev, *node = NULL;
    for (;len > 1; len--) {
        node = head->next;
        for (int i = rand() % len; i > 0; i--){
            node = node->next;
        }
        if (node->next != tail){
            list_del(node);
            list_add(node, tail->prev);
        }
        tail = node;
    }
}

web

使用 tiny-web-server 提供伺服器功能，目前如下的程式能符合伺服器運作的同時， qtest 仍可輸入指令 命令的要求，但是當 tiny 有輸出訊息時，畫面會被覆蓋掉，不影響運作。

instruction 是「指令」，command 是「命令」，二者語意不同。

jserv

錯誤嘗試

// this code is writen in qtest.c, not queue.c
static bool do_web(int argc, char *argv[])
{
    if (argc != 1) {
        report(1, "%s takes no arguments", argv[0]);
        return false;
    }
    // tiny is installed in different path, so path was given here
    int id = system("../tiny-web-server/tiny 9999 &");
    if (id == -1)
        return false;
    return true;
}

更新錯誤 : 當 qtest 結束執行時， tiny 程式不會結束執行，也無法用 jobs 命令查到。

不要呼叫 system 函式，你應該引入 tiny-web-server 的原始程式碼並整合。

jserv

select 系統呼叫在本程式的使用方式

首先先看看 select 的用途，參考了這篇以及這篇，了解 select 中各項傳入參數所代表的意義。

select(nfds, readfds, writefds, exceptfds, timeout) 中， ndfs 用以表示可以檢查的 file descriptors 的範圍，中間三個參數個別表示指向存放 read, write, except 的三個 file descriptors set (fd_set) ，最後 timeout 參數則限制了 select 要等待多久，特別的是當 timeout 值為 NULL 時， select 會無限制的等下去。

當 select 回傳 -1 表示有錯誤發生，回傳 0 表示等待超時，而成功時則會回傳一個值，根據描述，這個值是大於0的，端看傳入的 fd_set 大小。

the total number of bits that are set in readfds, writefds, exceptfds

回頭看 select 在程式中在何處使用，是在 console.c 的 cmd_select 中，並且依據 cmd_select 的使用， nfds, writefds, exceptfds, timeout 四個參數的傳入值都是固定的，分別是 0 以及三個 NULL ，這意味著 select 永遠只會看 read 的 fd_set 中的第一個，而且會無限制地等到該 fd 準備好，而該 fd 就是指向我們所輸入的命令ㄉ，或是 source 從檔案中讀到的第一個命令。

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

如果輸入 make valgrind 來檢查程式運作，在將 queue.c 撰寫完成之後，仍可看到來自 linenoise.c 的錯誤發生，而主要是從 linenoiseHistoryAdd 的函式中所取的記憶體沒有完全釋放掉，而使部分資料仍 'reachable'

先看這部分的程式碼是如何運作

int linenoiseHistoryAdd(const char *line)
{
    char *linecopy;
    if (history_max_len == 0)
        return 0;

    /* Initialization on first call. */
    if (history == NULL) {
        history = malloc(sizeof(char *) * history_max_len);
        if (history == NULL)
            return 0;
        memset(history, 0, (sizeof(char *) * history_max_len));
    }

    /* Don't add duplicated lines. */
    if (history_len && !strcmp(history[history_len - 1], line))
        return 0;

    /* Add an heap allocated copy of the line in the history.
     * If we reached the max length, remove the older line. */
    linecopy = strdup(line);
    if (!linecopy)
        return 0;
    if (history_len == history_max_len) {
        free(history[0]);
        memmove(history, history + 1, sizeof(char *) * (history_max_len - 1));
        history_len--;
    }
    history[history_len] = linecopy;
    history_len++;
    return 1;
}

這個函式看起來沒有問題，因此錯誤應該不是發生在函式內部，接著看發生 memory leak 的地方是在 qtest.c 呼叫 history load 時所產生的，推測是結束時 histroy 的記憶體沒有被釋放掉，所以再來看 main 結束之前的動作，
TODO