2023q1 Homework1 (lab0)

contributed by < gaberplaysgame >

開發環境

$ gcc --version
gcc (Ubuntu 11.3.0-1ubuntu1~22.04) 11.3.0
$ 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):                  12
  On-line CPU(s) list:   0-11
Vendor ID:               GenuineIntel
  Model name:            11th Gen Intel(R) Core(TM) i5-11400 @ 2.60GHz
    CPU family:          6
    Model:               167
    Thread(s) per core:  2
    Core(s) per socket:  6
    Socket(s):           1
    Stepping:            1
    CPU max MHz:         4400.0000
    CPU min MHz:         800.0000
    BogoMIPS:            5184.00

在終端機執行 export LC_ALL=C，再執行上述命令。lscpu 套件目前的中文翻譯品質不佳。

jserv

開發過程

嘗試改進 lab0-c

注意書寫規範，中英文間用一個半形空白字元區隔

jserv

q_new()

依據作業規範，q_new() 應配置可容納 list_head 的記憶體空間，並對節點進行設定，這部份list.h有INIT_LIST_HEAD(head)可以做到，故這裡就直接用內建函式處理。考慮到 malloc 有可能無法配置空間，所以用一個if處理空間分配失敗的狀況，若失敗則 head 為 NULL 。

struct list_head *q_new()
{
    struct list_head *head = malloc(sizeof(struct list_head));
    if (head)
        INIT_LIST_HEAD(head);
    return head;
}

q_insert_head()

與下面的 insert_tail 是同樣道理，分了三次 if 來去排除掉可能 malloc 錯誤或者 head 為 NULL 的情況。

注意書寫規範，中英文間用一個半形空白字元區隔

jserv

bool q_insert_head(struct list_head *head, char *s)
{
    if (!head)
        return false;   //if head == NULL, return false
    element_t *new = malloc(sizeof(element_t));
    if (!new)
        return false;   //if malloc() failed
    size_t len_s = strlen(s) + 1;
    new->value = (char *) malloc(len_s * sizeof(char));
    if (!new->value){
        free(new);
        return false;   //if malloc() failed, free new and return false
    }

    //copy string value
    memcpy(new->value, s, len_s);

    //utilize function of list.h 
    list_add(&new->list, head);
    return true;
}

q_insert_tail()

bool q_insert_tail(struct list_head *head, char *s)
{
    if (!head)
        return false;   //if head == NULL, return false
    element_t *new = malloc(sizeof(element_t));
    if (!new)
        return false;   //if malloc() failed
    size_t len_s = strlen(s) + 1;
    new->value = (char *) malloc(len_s);
    if (!new->value){
        free(new);
        return false;   //if malloc() failed, free new and return false
    }

    //copy string value
    memcpy(new->value, s, len_s);

    //utilize function of list.h 
    list_add_tail(&new->list, head);
    return true;
}

q_size()

int q_size(struct list_head *head)
{
    //if head is NULL or head->next = head, the queue has no element
    if (!head || list_empty(head))
        return 0;

    int count = 0;
    struct list_head *iter;
    list_for_each(iter, head)
        count++;
    
    return count;
}

q_free()

這邊利用內建的函式來做 free ，用 for 迴圈遍歷 –- 整個鏈結串列，複雜度為 O(n)。

注意 資訊科技詞彙翻譯 並改進漢語表達。

jserv

void q_free(struct list_head *l)
{
    if (!l)
        return;  // if head is NULL
    element_t *iter, *next;
    list_for_each_entry_safe (iter, next, l, list) {
        list_del(&iter->list);    // delete node
        q_release_element(iter);  // free element
    }
    free(l);
}

q_remove_head()

與下方的remove_tail是一樣的，只是改head->next或head->prev。

element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
    if (!head || list_empty(head))   //there is no element in list
        return NULL;    
    element_t *remove = list_entry(head->next, element_t, list);
    list_del(&remove->list);        //an element in list is removed

    if (sp && bufsize) {            //sp != NULL and bufsize != 0
        memcpy(sp, remove->value, bufsize);
        sp[bufsize - 1] = '\0';
    }

    return remove;                  
}

q_remove_tail()

element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize)
{
    if (!head || list_empty(head))   //there is no element in list
        return NULL;    
    element_t *remove = list_entry(head->prev, element_t, list);
    list_del(&remove->list);        //an element in list is removed

    if (sp && bufsize) {            //sp != NULL and bufsize != 0
        memcpy(sp, remove->value, bufsize);
        sp[bufsize - 1] = '\0';
    }

    return remove;  
}

q_delete_mid()

利用 Floyd Tortoise and Hare Algorithm ，原理是給定兩個迭代節點分別跑一步與兩步，若兩個節點同時在除起點外同個位置時則代表鏈結串列有閉環。因為 linux 的鏈結串列是用循環雙向的方式做的，因此可以利用該演算法，在 Hare 第一次跑到鏈結串列的尾端時，Tortoise 會剛好在中間節點。

由於鏈結串列的長度會有分單雙數的情況，單數時 Hare 可以剛好跑到尾端，雙數則會多跑一格 ?? 到 head 指標。由於 Hare 一次跑兩格，所以跑到尾端和跑到 Head 的事件不會同時發生，可以當作 while 判斷式的中止條件。

注意量詞，翻閱辭典以理解「格」的使用時機。

jserv

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;

    struct list_head
        *tortoise = head->next,
        *hare = head->next;  // given two node points to 0th node, using floyd's
                             // tortoise and hare algorithm.
    while (hare != head &&
           hare != head->prev) {  // when hare reaches end of list or head,
                                  // tortoise will be in the middle of the list
        tortoise = tortoise->next;
        hare = hare->next->next;
    }

    element_t *element = list_entry(tortoise, element_t, list);
    list_del(&element->list);
    q_release_element(element);

    return true;
}

q_delete_dup()

原本寫的程式碼：利用一個flag和strcmp進行兩個元素的比較，若strcmp出來0則flag為 true 並刪除cur的元素，下次若是strcmp非0，flag為 true 時亦會刪除元素。如此便有三點要處理：

1. 當next == head時，由於head沒有數值，不能進行strcmp，因此只能進到flag判斷。
2. 當strcmp == 0時，進行元素刪除。
3. 當flag == true時，進行元素刪除。

下面是第一版的程式碼（節錄）：

element_t *cur, *next;
bool flag = false;
list_for_each_entry_safe (cur, next, head, list) {
    if (&next->head != head) {
        int cmp = strcmp(cur->value, next->value);
        if (!cmp) {
            flag = true;
            list_del(&cur->list);
            q_release_element(cur);
        } 
    } else if (flag) {
        flag = false;
        list_del(&cur->list);
        q_release_element(cur);
    }
}

可以看到上面程式碼用了很多 if，尤其list_del的部份有重複，自己都認為沒有品味，因此花了一些時間在改進程式碼方面。

首先嘗試了把上面提到的重複部份整理一頓，先忽略了next->list可能為head的情形，利用cmp與flag兩個數值相反的特性將區塊合併。

1. 當 cmp 為0時，flag會被設為 true ，這代表如果下一圈 cmp 不是0時仍可以刪除 cur 的元素
2. 沿述，當 cmp 不是0時，若 flag 為 true ，則刪除元素；若 flag 為 false ，則代表沒有需要刪除元素，可以進到下一圈。

排除掉未刪除元素的可能性後，可以看到flag = !cmp的性質，且可以放在程式最後面執行，因此只要把 cmp 非0，flag 為 false 的情況先擋掉，就可以把兩個區塊合併。

    if (cmp && !flag)
        continue;

    list_del(&cur->list);
    q_release_element(cur);
    flag = !cmp;

再來就是解決next->list可能為 head 的情形了。若此狀況發生，cmp 沒辦法決定值，因此給這段加上了一個三元判斷式判定若該狀況發生，指定 cmp 為 true 。如此可以保證if (cmp && !flag)能被觸發，再來若 flag 為 true 可以保證元素能被刪除。

改進過後的程式碼：

不用張貼完整程式碼，只要列出差異的部分，善用 diff

jserv

bool q_delete_dup(struct list_head *head) { // https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/ if (!head) return false; // list is NULL

​​​​element_t *cur, *next;
​​​​bool flag = false;
​​​​list_for_each_entry_safe (cur, next, head, list) {
​​​​    int cmp = &next->list != head ?
​​​​        strcmp(cur->value, next->value) :
​​​​        true;  // no comparison if next is head,
​​​​               // comparison gives 0 or nonzero value
​​​​    if (cmp && !flag)
​​​​        continue;

​​​​    list_del(&cur->list);
​​​​    q_release_element(cur);
​​​​    flag = !cmp;
​​​​}

​​​​return true;

}

目前只有這個函式還沒有去做正確性的測試，等sort與reverse等做完後才能進一步確認是否運行順利。 經過測試後確定可以順利通過autojudge測資。

注意看程式碼，lab0-c 使用 autograde 一詞，「測試案例」不該簡稱「測資」。

jserv

q_swap()

因為下方的 reverse 函式會用到 swap 的技術，所以將實際將兩個節點進行交換的步驟給獨立出來。

改進你的漢語表達。

jserv

void swap(struct list_head *n1, struct list_head *n2)
{
    struct list_head *tmp = n1->next;
    n1->next = n2->next;
    n2->next->prev = n1;
    n2->next = tmp;
    n2->next->prev = n2;

    tmp = n2->prev;
    n2->prev = n1->prev;
    n1->prev->next = n2;
    n1->prev = tmp;
    n1->prev->next = n1;
}

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 *n1 = head->next, *n2 = n1->next;
    while (n1 != head && n2 != head) {
        swap(n1, n2);
        n1 = n1->next;
        n2 = n1->next;
    }
}

q_reverse()

本意上用到的是頭尾交換的想法，由於是循環陣列容易找到鏈結串列尾，故用這個方法實作。

void reverse(struct list_head *start, struct list_head *end)
{
    while (start != end && start != end->next) {
        swap(start, end);
        struct list_head *tmp = end->next;
        end = start->prev;
        start = tmp;
    }
}

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

    reverse(head->next, head->prev);
}

q_reverseK()

方法目前只有想到類似硬破法，將佇列拆為 k 個（或更少）一組，然後分別進行 reverse 操作。

void q_reverseK(struct list_head *head, int k)
{
    // https://leetcode.com/problems/reverse-nodes-in-k-group/
    if (!head || list_empty(head) || list_is_singular(head))
        return;

    struct list_head *start = head->next, *end = start;
    while (end != head) {
        int count = 1;
        while (count != k && end->next != head) {
            end = end->next;
            count++;
        }
        struct list_head *tmp = end->next;
        reverse(start, end);
        start = tmp, end = start;
    }
}

q_sort()

這裡的 sort 是使用 mergesort 來實作，方法有參考你所不知道的C語言：Merge Sort的實作與間接指標的應用，但有用到將循環鏈結串列斷開成一般鏈結串列的操作，還沒有想到有沒有可以保持循環鏈結串列的實作方式。

struct list_head *merge(struct list_head *l1, struct list_head *l2)
{
    struct list_head *new_head = NULL, **indirect = &new_head;
    while (l1 && l2) {
        if (strcmp(list_entry(l1, element_t, list)->value,
                   list_entry(l2, element_t, list)->value) < 0) {
            *indirect = l1;
            l1 = l1->next;
        } else {
            *indirect = l2;
            l2 = l2->next;
        }
        indirect = &(*indirect)->next;
    }
    *indirect = (struct list_head *) ((uintptr_t) l1 | (uintptr_t) l2);
    return new_head;
}

struct list_head *mergeSort(struct list_head *head, struct list_head *tail)
{
    if (head == tail)
        return head;
    struct list_head *start = head, *end = tail;
    while (start != end && start != end->prev) {
        start = start->next;
        end = end->prev;
    }
    if (start == end)
        end = end->next;
    start->next = NULL;
    end->prev = NULL;

    struct list_head *l1 = mergeSort(head, start), *l2 = mergeSort(end, tail);
    return merge(l1, l2);
}

void q_sort(struct list_head *head)
{
    if (!head || list_empty(head) ||
        list_is_singular(head))  // if head == NULL or empty or one element
        return;

    struct list_head *start = head->next, *end = head->prev;

    // Break the circular linked list
    start->prev = NULL;
    end->next = NULL;

    // Mergesort
    struct list_head *new_head = mergeSort(start, end);
    start = new_head;
    end = start->next;

    // Rebuild circular linked list
    for (; end != NULL; start = start->next, end = end->next) {
        end->prev = start;
    }
    start->next = head;
    new_head->prev = head;
    head->next = new_head;
    head->prev = start;
}

q_merge()

有用到前面 merge 的想法，並且用 Devide & Conquer 的方式處理合併，使時間複雜到可以降到 O(NlogK)。

注意書寫規範，中英文間用一個半形空白字元區隔

jserv

int q_merge(struct list_head *head)
{
    // https://leetcode.com/problems/merge-k-sorted-lists/
    int interval = 1, list_amount = 0;
    queue_contex_t *contex = NULL;
    list_for_each_entry (contex, head, chain) {
        list_amount++;
        contex->q->prev->next = NULL;
    }

    struct list_head *l1 = NULL, *l2 = NULL;
    while (interval < list_amount) {
        for (int i = 0; i < list_amount - interval; i += interval * 2) {
            list_for_each_entry (contex, head, chain) {
                if (contex->id == i)
                    l1 = contex->q;
                else if (contex->id == i + interval)
                    l2 = contex->q;
            }
            l1->next = merge(l1->next, l2->next);
            l2->prev = l2;
            l2->next = l2;
        }
        interval *= 2;
    }

    struct list_head *start, *end;
    head = l1;
    start = head->next;
    end = start->next;

    // Rebuild circular linked list
    for (; end != NULL; start = start->next, end = end->next) {
        end->prev = start;
    }
    start->next = head;
    head->next->prev = head;
    head->prev = start;
    return q_size(head);
}

q_descend()

這函式用了兩個指標 left 與 right 來處理數值比較，當 right 指到 head 時結束操作並回傳佇列大小。其餘實作方式基本可以參考 remove 系列。

注意書寫規範，中英文間用一個半形空白字元區隔

jserv

int q_descend(struct list_head *head)
{
    // https://leetcode.com/problems/remove-nodes-from-linked-list/
    if (!head || list_empty(head))  // if head == NULL or empty or one element
        return 0;
    if (list_is_singular(head))
        return 1;

    int count = 1;
    struct list_head *left = head->next, *right = left->next;
    while (right != head) {
        element_t *left_entry = list_entry(left, element_t, list);
        if (strcmp(left_entry->value,
                   list_entry(right, element_t, list)->value) < 0) {
            left = left->next;
            list_del(&left_entry->list);
            q_release_element(left_entry);
            count--;
        } else {
            right = right->next;
            count++;
        }
    }
    return count;
}

注意書寫規範，中英文間用一個半形空白字元區隔

jserv

引進 lib/list_sort.c

引入linux/list_sort.[c, h] 並做了些特別的修改，主要是為了繞開不能修改 queue.h 的限制，所以將 list_sort.[c, h] 作為新的引入檔，以 q_list_sort 作為在 qtest.c 的呼叫函式。

ADD_COMMAND(lsort, "Sort queue in ascending order in linux kernel way", "");

cmp 函式以此方式實作，由於不太確定 priv 傳入值的用處，加上可以為 NULL 值，cmp 函式就將此刪除：

__attribute__((nonnull(1,2)))
int q_list_cmp(const struct list_head *a, const struct list_head *b)
{
    element_t *element_a = list_entry(a, element_t, list);
    element_t *element_b = list_entry(b, element_t, list);

    int res = strcmp(element_a->value, element_b->value);

    return res;
}

這邊以原本進行 make 是沒有問題的，但在更新 GitHub 時有遇到 cppcheck 的 "Null pointer dereference" ，指向 list_entry 的用法。

list_sort.c:24:28: error: Null pointer dereference: (struct element_t*)0 [nullPointer]
    element_t *element_a = list_entry(a, element_t, list);

起初不太知道這個錯誤應該如何解決，以為是程式碼本身的錯誤，在這個程式碼上面花了一點時間。觀摩 jasperlin1996 後發現說可能是 cppcheck 的問題。由於學長已經做過了 cppcheck 1.9~2.7 的測試，自己把最新版的 2.10 安裝之後這個錯誤仍存在，最後只好使用 cppcheck suppression 的方式解決，即使用 cppcheck-suppress nullPointer繞過。這邊引用學長對於這個錯誤的敘述以及當屆討論：

這邊是因為 list.h 中 container_of 的實作中，有一行是 typeof(((type *) 0)->member) 而 (type *) 0 的確是 null pointer。不過這邊的用法是為了取得 member 的 type，且這個用法是符合 ANSI C 的標準的，詳細的說明可以看這篇：https://stackoverflow.com/questions/13723422/why-this-0-in-type0-member-in-c
以及規格書的第 6.3.2 章關於 pointer 的說明：http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1256.pdf

另外直接引入 list_sort.[c, h] 會遇到 likely & unlikely 巨集的問題，雖然這段編碼只是為了優化 gcc ，但為了不過度影響程式效能自己還是從compiler.h 抓入相關部份並放入list_sort.c。

注意書寫規範，中英文間用一個半形空白字元區隔。
改進你的漢語表達。

jserv

對自撰 sort 與 list_sort 進行效能分析

利用 Perf 進行效能分析，執行 10 次並取平均，測試程式如下：

new
ih RAND <number>
time
sort/lsort
time
free

Perf 似乎無法支援筆電 CPU ，導致部份如 instruction, cycles 的測試無法進行，這邊先貼上部份的測試結果，之後預計會換回桌機進行測試。筆電使用 i7-7700 CPU 無法進行有關 instruction 與 cycles 等的測試，換回桌機使用 i5-11400 已解決問題，故以下會使用桌機數據重新進行紀錄。

清楚列舉硬體型號和相關系統資訊，這樣他人才能協助排除問題。

jserv

• 註：q 為 q_sort ，l 為 q_list_sort

number	instruction	time	cycles	page fault	branch
1024_q	5,934,943	0.91 ms	3,884,975	112	911,195
2048_q	10,164,886	1.48 ms	6,164,264	150	1,509,771
4096_q	18,852,459	4.76 ms	19,931,933	220	2,755,409
10240_q	45,017,257	6.47 ms	27,146,322	438	6,533,543
102400_q	448,797,359	100.75 ms	425,198,490	3677	65,891,213
409600_q	1,824,311,621	649.45 ms	2,562,835,035	14477	270,998,617
1024_l	5,504,024	1.76 ms	3,135,236	112	797,843
2048_l	9,005,109	2.62 ms	10,824,548	148	1,229,047
4096_l	16,449,283	6.55 ms	12,042,236	221	2,164,575
10240_l	38,676,693	18.08 ms	18,684,006	437	4,955,814
102400_l	372,969,154	46.82 ms	197,921,647	3677	46,956,545
409600_l	1,488,046,316	177.62 ms	725,989,221	14477	187,069,862

這邊取的是平均值的數值，實際的時間差在正負 10ms 左右。可以看到在 instruction, cycle, branch 上 list sort 都比自己寫的 sort 還有好。由於時間差落在正負 10ms ，因此在數量級小的情況下兩個演算法難分軒輊，但若是數量級大則可以明顯看到 list sort 的表現比自己寫的還要消耗更少時間。綜合以上數據可以發現 list sort 在各方面都優於自己實作的 merge sort 。

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

執行make valgrind可以得到以下結果（節錄）：

--- trace-01-ops    0/5
--- trace-02-ops    0/6
--- trace-03-ops    0/6
--- trace-04-ops    0/6
--- trace-05-ops    0/6
--- trace-06-ops    0/6
--- trace-07-string    0/6
--- trace-08-robust    6/6
--- trace-09-robust    0/6
--- trace-10-robust    6/6
--- trace-11-malloc    6/6
--- trace-12-malloc    6/6
--- trace-13-malloc    0/6
--- trace-14-perf    6/6
--- trace-15-perf    6/6
--- trace-16-perf    6/6

這邊取trace-01-ops的問題進行細部觀察，可以看到大致由三種問題組成：

gaberil0903@host:~/linux2023/lab0-c$ valgrind ./qtest -f traces/trace-01-ops.cmd
# Test of insert_head and remove_head
l = []
l = [gerbil]
l = [bear gerbil]
l = [dolphin bear gerbil]
==12508== Invalid read of size 8
==12508==    at 0x4852AF8: memmove (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==12508==    by 0x10F89C: memcpy (string_fortified.h:29)
==12508==    by 0x10F89C: q_remove_head (queue.c:96)
==12508==    by 0x10C333: do_remove (qtest.c:404)
==12508==    by 0x10C4DB: do_rh (qtest.c:461)
==12508==    by 0x10DF86: interpret_cmda (console.c:181)
==12508==    by 0x10E53B: interpret_cmd (console.c:201)
==12508==    by 0x10E93C: cmd_select (console.c:610)
==12508==    by 0x10F228: run_console (console.c:705)
==12508==    by 0x10D378: main (qtest.c:1270)
==12508==  Address 0x4b7f3d8 is 8 bytes before a block of size 2,049 alloc'd
==12508==    at 0x4848899: malloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==12508==    by 0x10C0ED: do_remove (qtest.c:371)
==12508==    by 0x10C4DB: do_rh (qtest.c:461)
==12508==    by 0x10DF86: interpret_cmda (console.c:181)
==12508==    by 0x10E53B: interpret_cmd (console.c:201)
==12508==    by 0x10E93C: cmd_select (console.c:610)
==12508==    by 0x10F228: run_console (console.c:705)
==12508==    by 0x10D378: main (qtest.c:1270)
==12508== 
==12508== Invalid read of size 8
==12508==    at 0x4852B00: memmove (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==12508==    by 0x10F89C: memcpy (string_fortified.h:29)
==12508==    by 0x10F89C: q_remove_head (queue.c:96)
==12508==    by 0x10C333: do_remove (qtest.c:404)
==12508==    by 0x10C4DB: do_rh (qtest.c:461)
==12508==    by 0x10DF86: interpret_cmda (console.c:181)
==12508==    by 0x10E53B: interpret_cmd (console.c:201)
==12508==    by 0x10E93C: cmd_select (console.c:610)
==12508==    by 0x10F228: run_console (console.c:705)
==12508==    by 0x10D378: main (qtest.c:1270)
==12508==  Address 0x4b7f3d0 is 16 bytes before a block of size 2,049 alloc'd
==12508==    at 0x4848899: malloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==12508==    by 0x10C0ED: do_remove (qtest.c:371)
==12508==    by 0x10C4DB: do_rh (qtest.c:461)
==12508==    by 0x10DF86: interpret_cmda (console.c:181)
==12508==    by 0x10E53B: interpret_cmd (console.c:201)
==12508==    by 0x10E93C: cmd_select (console.c:610)
==12508==    by 0x10F228: run_console (console.c:705)
==12508==    by 0x10D378: main (qtest.c:1270)
==12508== 
==12508== Invalid read of size 8
==12508==    at 0x4852AE4: memmove (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==12508==    by 0x10F89C: memcpy (string_fortified.h:29)
==12508==    by 0x10F89C: q_remove_head (queue.c:96)
==12508==    by 0x10C333: do_remove (qtest.c:404)
==12508==    by 0x10C4DB: do_rh (qtest.c:461)
==12508==    by 0x10DF86: interpret_cmda (console.c:181)
==12508==    by 0x10E53B: interpret_cmd (console.c:201)
==12508==    by 0x10E93C: cmd_select (console.c:610)
==12508==    by 0x10F228: run_console (console.c:705)
==12508==    by 0x10D378: main (qtest.c:1270)
==12508==  Address 0x4b7f3c8 is 24 bytes before a block of size 2,049 alloc'd
==12508==    at 0x4848899: malloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==12508==    by 0x10C0ED: do_remove (qtest.c:371)
==12508==    by 0x10C4DB: do_rh (qtest.c:461)
==12508==    by 0x10DF86: interpret_cmda (console.c:181)
==12508==    by 0x10E53B: interpret_cmd (console.c:201)
==12508==    by 0x10E93C: cmd_select (console.c:610)
==12508==    by 0x10F228: run_console (console.c:705)
==12508==    by 0x10D378: main (qtest.c:1270)
==12508== 
==12508== Invalid read of size 8
==12508==    at 0x4852AF0: memmove (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==12508==    by 0x10F89C: memcpy (string_fortified.h:29)
==12508==    by 0x10F89C: q_remove_head (queue.c:96)
==12508==    by 0x10C333: do_remove (qtest.c:404)
==12508==    by 0x10C4DB: do_rh (qtest.c:461)
==12508==    by 0x10DF86: interpret_cmda (console.c:181)
==12508==    by 0x10E53B: interpret_cmd (console.c:201)
==12508==    by 0x10E93C: cmd_select (console.c:610)
==12508==    by 0x10F228: run_console (console.c:705)
==12508==    by 0x10D378: main (qtest.c:1270)
==12508==  Address 0x4b7f3c0 is 32 bytes before a block of size 2,064 in arena "client"
==12508== 
Removed dolphin from queue
l = [bear gerbil]
==12508== Invalid read of size 8
==12508==    at 0x4852947: memmove (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==12508==    by 0x10F89C: memcpy (string_fortified.h:29)
==12508==    by 0x10F89C: q_remove_head (queue.c:96)
==12508==    by 0x10C333: do_remove (qtest.c:404)
==12508==    by 0x10C4DB: do_rh (qtest.c:461)
==12508==    by 0x10DF86: interpret_cmda (console.c:181)
==12508==    by 0x10E53B: interpret_cmd (console.c:201)
==12508==    by 0x10E93C: cmd_select (console.c:610)
==12508==    by 0x10F228: run_console (console.c:705)
==12508==    by 0x10D378: main (qtest.c:1270)
==12508==  Address 0x4b7f030 is 3 bytes after a block of size 45 alloc'd
==12508==    at 0x4848899: malloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==12508==    by 0x10F29C: test_malloc (harness.c:133)
==12508==    by 0x10F765: q_insert_head (queue.c:48)
==12508==    by 0x10CAA5: do_ih (qtest.c:224)
==12508==    by 0x10DF86: interpret_cmda (console.c:181)
==12508==    by 0x10E53B: interpret_cmd (console.c:201)
==12508==    by 0x10E93C: cmd_select (console.c:610)
==12508==    by 0x10F228: run_console (console.c:705)
==12508==    by 0x10D378: main (qtest.c:1270)
==12508== 
==12508== Invalid read of size 8
==12508==    at 0x485294F: memmove (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==12508==    by 0x10F89C: memcpy (string_fortified.h:29)
==12508==    by 0x10F89C: q_remove_head (queue.c:96)
==12508==    by 0x10C333: do_remove (qtest.c:404)
==12508==    by 0x10C4DB: do_rh (qtest.c:461)
==12508==    by 0x10DF86: interpret_cmda (console.c:181)
==12508==    by 0x10E53B: interpret_cmd (console.c:201)
==12508==    by 0x10E93C: cmd_select (console.c:610)
==12508==    by 0x10F228: run_console (console.c:705)
==12508==    by 0x10D378: main (qtest.c:1270)
==12508==  Address 0x4b7f038 is 11 bytes after a block of size 45 alloc'd
==12508==    at 0x4848899: malloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==12508==    by 0x10F29C: test_malloc (harness.c:133)
==12508==    by 0x10F765: q_insert_head (queue.c:48)
==12508==    by 0x10CAA5: do_ih (qtest.c:224)
==12508==    by 0x10DF86: interpret_cmda (console.c:181)
==12508==    by 0x10E53B: interpret_cmd (console.c:201)
==12508==    by 0x10E93C: cmd_select (console.c:610)
==12508==    by 0x10F228: run_console (console.c:705)
==12508==    by 0x10D378: main (qtest.c:1270)
==12508== 
==12508== Invalid read of size 8
==12508==    at 0x4852934: memmove (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==12508==    by 0x10F89C: memcpy (string_fortified.h:29)
==12508==    by 0x10F89C: q_remove_head (queue.c:96)
==12508==    by 0x10C333: do_remove (qtest.c:404)
==12508==    by 0x10C4DB: do_rh (qtest.c:461)
==12508==    by 0x10DF86: interpret_cmda (console.c:181)
==12508==    by 0x10E53B: interpret_cmd (console.c:201)
==12508==    by 0x10E93C: cmd_select (console.c:610)
==12508==    by 0x10F228: run_console (console.c:705)
==12508==    by 0x10D378: main (qtest.c:1270)
==12508==  Address 0x4b7f040 is 19 bytes after a block of size 45 alloc'd
==12508==    at 0x4848899: malloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==12508==    by 0x10F29C: test_malloc (harness.c:133)
==12508==    by 0x10F765: q_insert_head (queue.c:48)
==12508==    by 0x10CAA5: do_ih (qtest.c:224)
==12508==    by 0x10DF86: interpret_cmda (console.c:181)
==12508==    by 0x10E53B: interpret_cmd (console.c:201)
==12508==    by 0x10E93C: cmd_select (console.c:610)
==12508==    by 0x10F228: run_console (console.c:705)
==12508==    by 0x10D378: main (qtest.c:1270)
==12508== 
==12508== Invalid read of size 8
==12508==    at 0x485293F: memmove (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==12508==    by 0x10F89C: memcpy (string_fortified.h:29)
==12508==    by 0x10F89C: q_remove_head (queue.c:96)
==12508==    by 0x10C333: do_remove (qtest.c:404)
==12508==    by 0x10C4DB: do_rh (qtest.c:461)
==12508==    by 0x10DF86: interpret_cmda (console.c:181)
==12508==    by 0x10E53B: interpret_cmd (console.c:201)
==12508==    by 0x10E93C: cmd_select (console.c:610)
==12508==    by 0x10F228: run_console (console.c:705)
==12508==    by 0x10D378: main (qtest.c:1270)
==12508==  Address 0x4b7f048 is 24 bytes after a block of size 48 in arena "client"
==12508== 
==12508== Invalid read of size 1
==12508==    at 0x4852A10: memmove (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==12508==    by 0x10F89C: memcpy (string_fortified.h:29)
==12508==    by 0x10F89C: q_remove_head (queue.c:96)
==12508==    by 0x10C333: do_remove (qtest.c:404)
==12508==    by 0x10C4DB: do_rh (qtest.c:461)
==12508==    by 0x10DF86: interpret_cmda (console.c:181)
==12508==    by 0x10E53B: interpret_cmd (console.c:201)
==12508==    by 0x10E93C: cmd_select (console.c:610)
==12508==    by 0x10F228: run_console (console.c:705)
==12508==    by 0x10D378: main (qtest.c:1270)
==12508==  Address 0x4b7f420 is 64 bytes inside a block of size 2,049 free'd
==12508==    at 0x484B27F: free (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==12508==    by 0x10C3B3: do_remove (qtest.c:454)
==12508==    by 0x10C4DB: do_rh (qtest.c:461)
==12508==    by 0x10DF86: interpret_cmda (console.c:181)
==12508==    by 0x10E53B: interpret_cmd (console.c:201)
==12508==    by 0x10E93C: cmd_select (console.c:610)
==12508==    by 0x10F228: run_console (console.c:705)
==12508==    by 0x10D378: main (qtest.c:1270)
==12508==  Block was alloc'd at
==12508==    at 0x4848899: malloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==12508==    by 0x10C0ED: do_remove (qtest.c:371)
==12508==    by 0x10C4DB: do_rh (qtest.c:461)
==12508==    by 0x10DF86: interpret_cmda (console.c:181)
==12508==    by 0x10E53B: interpret_cmd (console.c:201)
==12508==    by 0x10E93C: cmd_select (console.c:610)
==12508==    by 0x10F228: run_console (console.c:705)
==12508==    by 0x10D378: main (qtest.c:1270)
==12508== 
Removed bear from queue
l = [gerbil]
Removed gerbil from queue
l = []
==12508== 32 bytes in 1 blocks are still reachable in loss record 1 of 2
==12508==    at 0x4848899: malloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==12508==    by 0x10CD3D: do_new (qtest.c:146)
==12508==    by 0x10DF86: interpret_cmda (console.c:181)
==12508==    by 0x10E53B: interpret_cmd (console.c:201)
==12508==    by 0x10E93C: cmd_select (console.c:610)
==12508==    by 0x10F228: run_console (console.c:705)
==12508==    by 0x10D378: main (qtest.c:1270)
==12508== 
==12508== 56 bytes in 1 blocks are still reachable in loss record 2 of 2
==12508==    at 0x4848899: malloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==12508==    by 0x10F29C: test_malloc (harness.c:133)
==12508==    by 0x10F6A1: q_new (queue.c:20)
==12508==    by 0x10CD76: do_new (qtest.c:150)
==12508==    by 0x10DF86: interpret_cmda (console.c:181)
==12508==    by 0x10E53B: interpret_cmd (console.c:201)
==12508==    by 0x10E93C: cmd_select (console.c:610)
==12508==    by 0x10F228: run_console (console.c:705)
==12508==    by 0x10D378: main (qtest.c:1270)
==12508== 

==12311== Invalid read of size 8
==12311==    at 0x4852AF8: memmove (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==12311==    by 0x10F89C: memcpy (string_fortified.h:29)
==12311==    by 0x10F89C: q_remove_head (queue.c:96)
==12311==    by 0x10C333: do_remove (qtest.c:404)
==12311==    by 0x10C4DB: do_rh (qtest.c:461)
==12311==    by 0x10DF86: interpret_cmda (console.c:181)
==12311==    by 0x10E53B: interpret_cmd (console.c:201)
==12311==    by 0x10E93C: cmd_select (console.c:610)
==12311==    by 0x10F228: run_console (console.c:705)
==12311==    by 0x10D378: main (qtest.c:1270)

==12311==  Address 0x4b7f3d8 is 8 bytes before a block of size 2,049 alloc'd
==12311==    at 0x4848899: malloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==12311==    by 0x10C0ED: do_remove (qtest.c:371)
==12311==    by 0x10C4DB: do_rh (qtest.c:461)
==12311==    by 0x10DF86: interpret_cmda (console.c:181)
==12311==    by 0x10E53B: interpret_cmd (console.c:201)
==12311==    by 0x10E93C: cmd_select (console.c:610)
==12311==    by 0x10F228: run_console (console.c:705)
==12311==    by 0x10D378: main (qtest.c:1270)

==12311== 32 bytes in 1 blocks are still reachable in loss record 1 of 2
==12311==    at 0x4848899: malloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==12311==    by 0x10CD3D: do_new (qtest.c:146)
==12311==    by 0x10DF86: interpret_cmda (console.c:181)
==12311==    by 0x10E53B: interpret_cmd (console.c:201)
==12311==    by 0x10E93C: cmd_select (console.c:610)
==12311==    by 0x10F228: run_console (console.c:705)
==12311==    by 0x10D378: main (qtest.c:1270)

第一、二個問題源自 bufsize 大小為 1025，然而測試字串 dolphin 的大小長度只有 8 ，所以在 memcpy(sp, remove->value, bufsize); 中會造成記憶體空間錯誤。所以只要將 bufsize 更改為bufsize > strlen(remove->value) + 1 ? strlen(remove->value) : bufsize 就好。

if (sp && bufsize) {  // sp != NULL and bufsize != 0
    memcpy(sp, remove->value, bufsize > strlen(remove->value) + 1 ? strlen(remove->value) + 1 : bufsize);
    sp[bufsize - 1] = '\0';
}

根據執行順序，判斷第三個訊息來自於把佇列清空後沒有正常釋放記憶體所導致，根據q_quit函式可以看到有個不正常的return true在程式第3行被執行，導致後續沒有進行 free 佇列。將不正常的程式碼移除後即可解決這個錯誤。

static bool q_quit(int argc, char *argv[])
{
    return true;
    report(3, "Freeing queue");
    if (current && current->size > BIG_LIST_SIZE)
        set_cautious_mode(false);

    if (exception_setup(true)) {
        struct list_head *cur = chain.head.next;
        while (chain.size > 0) {
            queue_contex_t *qctx, *tmp;
            tmp = qctx = list_entry(cur, queue_contex_t, chain);
            cur = cur->next;
            q_free(qctx->q);
            free(tmp);
            chain.size--;
        }
    }

    exception_cancel();
    set_cautious_mode(true);

    size_t bcnt = allocation_check();
    if (bcnt > 0) {
        report(1, "ERROR: Freed queue, but %lu blocks are still allocated",
               bcnt);
        return false;
    }

    return true;
}

再次執行make valgrind可以看到問題皆以修復。

利用 massif 視覺化 simulation

這邊設計一個實驗組與一個對照組，採用的是前章節出問題的 removehead 指令 –-，可以得出兩種結果，前者為優化前，後者為優化後：

去查詢 optimize 的意思，留意 optimal 的定義。不要濫用詞彙。

jserv

利用valgrind --tool=massif ./qtest -f traces/sim-rh.cmd與 Valgrind User Manual 9.3 的 massif-visualizer 來顯示結果：

massif-visualizer massif.out.14944

massif-visualizer massif.out.14972

可以看到在針對 q_quit 函式進行修復後，有改善記憶體的釋出，但程式執行最後仍未完全釋放記憶體。

TODO: 利用 Address Sanitizer 修正 qtest 執行過程中的錯誤

使用 Address Sanitizer 後進行 make test 後發現編號第 14 的測試案例因超時無法順利通過，而編號第 17 的測試案例中，常數時間測試在 remove_head/tail 時為常數時間時非常數時間。比對過其他人程式碼後還沒有找到問題在哪裡，預計會再進行深入研究。

不要說「其他人」，明確列出你參照的帳號名稱，還有你如何實驗。

jserv

在 q_test 添加指令 命令 shuffle

command 的翻譯是「命令」，instruction 的翻譯是「指令」，二者語境落差大。

jserv

參考 Fisher-Yates Shuffle 演算法的偽代碼 虛擬碼進行實作。

台灣的慣用翻譯風格中，少用「偽」，反過來說，中共的刊物就常見。

jserv

void q_shuffle(struct list_head *head, size_t len)
{
    if (!head || list_empty(head) || list_is_singular(head))
        return;
    struct list_head *tail = head->prev;

    for (int i = len - 1; i > 0; i--) {
        struct list_head *cur = head;
        int j = rand() % (i + 1);
        for (int tmp = 0; tmp <= j; tmp++)
            cur = cur->next;
        shuffle_swap(cur, tail);
        tail = cur->prev;
    }
}

實作完成後利用範例的測試程式進行卡方（

$X^2$）的計算，得出約等於 22.9521 。

$[1,2,3,4]$ 的排序中共有 24 種排列組合，故自由度（P）為 23 。根據卡方分布圖查詢可知 P-value 介於 0.25~0.5 之間，大於常見的顯著水準 alpha (0.05) 。統計結果鑑定不拒絕虛無假說。

Expectation:  41666
Observation:  {'1234': 41341, '1243': 41787, '1324': 41601, '1342': 41794, '1423': 41864, '1432': 41914, '2134': 41506, '2143': 41670, '2314': 41623, '2341': 41579, '2413': 41635, '2431': 41982, '3124': 41732, '3142': 41633, '3214': 41552, '3241': 41843, '3412': 41806, '3421': 41728, '4123': 41406, '4132': 41222, '4213': 41999, '4231': 41325, '4312': 41783, '4321': 41675}
chi square sum:  22.952143234291746