2022q1 Homework1 (lab0)

contributed by < freshLiver >

tags: `linux2022`

環境

$ gcc --version 
gcc (Ubuntu 10.3.0-1ubuntu1) 10.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):                          12
On-line CPU(s) list:             0-11
Thread(s) per core:              2
Core(s) per socket:              6
Socket(s):                       1
NUMA node(s):                    1
Vendor ID:                       GenuineIntel
CPU family:                      6
Model:                           167
Model name:                      11th Gen Intel(R) Core(TM) i5-11400 @ 2.60GHz
Stepping:                        1
CPU MHz:                         2600.000
CPU max MHz:                     4400.0000
CPU min MHz:                     800.0000
BogoMIPS:                        5184.00
Virtualization:                  VT-x
L1d cache:                       288 KiB
L1i cache:                       192 KiB
L2 cache:                        3 MiB
L3 cache:                        12 MiB
NUMA node0 CPU(s):               0-11

實作 queue 相關函式

結構體說明

struct list_head {
    struct list_head *prev;
    struct list_head *next;
};

struct list_head 為 list.h 中定義的結構體，這個結構體中包含了 prev 與 next 兩個定義於 list_head 的指標，分別藉由指向前、後一個節點，以便實作出 circular doubly-linked list。

typedef struct {
    char *value;
    struct list_head list;
} element_t;

struct element_t 為 queue.h 中定義的結構體，而在這個結構體中，除了定義 value 來儲存資料之外，也定義了結構體 list_head 的變數，並讓 list_head 中定義的 prev 以及 next 分別指向前、後一個佇列節點中的 list，以便在佇列中的各個節點間移動。

為什麼 `element_t` 中包含了 `list_head`

這次作業檔案 lsit.h 中除了定義結構體 list_head 之外還包含了數個相關的函式以及巨集，是 Linux 原始碼中的 list.h 的簡化版（少了一些 list_head 相關的操作函式以及 hlist 相關的部份）。

關於本次作業的 list.h 與 Linux 專案中的 list.h 的細節差異在你所不知道的 C 語言: linked list 和非連續記憶體中有更詳細的解說

而這個結構體也在 Linux 專案中被大量重複使用，除了包含了 circular doubly-linked list 相關的基本操作之外，若是想要在它之上定義其他變數的話，只需要另外定義新的結構體並在其中定義一個 list_head 的變數就可以進行擴充，而在擴充的結構體相關的操作中也可以直接使用 list.h 中的相關函式，而不用為每個新定義的結構體實作基本操作的函式，藉此來達到類似於其他語言中「繼承」的概念，也能夠藉由使用用這些函式以及巨集使得程式碼更簡潔、更具有可讀性。

為什麼在這次作業要實作的相關操作函式中，都是以 list_head 作為參數而不是直接使用 element_t 作為參數？

TODO: 思索這樣規劃帶來的效益

Image Not Showing Possible Reasons
The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported
Learn More →

jserv

在這次要完成的佇列相關操作函式幾乎都需要透過 head 這個節點來走訪佇列，但在 list_head 構成的雙向鏈結串列中， head 節點只負責指向串列的開頭以及結尾的節點，實際上不需要儲存資料，因此若是使用 element_t 作為參數的話，會出現閒置的空間造成浪費。且在走訪串列時實際還是透過 list_head 結構體來進行，因此也會造成存取首位、末位節點時需要使用像是 head->list->next 或 head->list->prev 這樣的額外操作。

巨集說明

#include <stddef.h>

size_t offsetof(type, member);

根據 Linus manual page 中對 offsetof 的說明，offsetof 是一個定義在 <stddef.h> 中的巨集，而 offsetof 可以用來獲取給定結構體 type 中某個 field member 相對於該結構體起始位置的位元組偏移量。

而在 GitHub 上 Linux 專案原始碼中的 stddef.h 檔案中有明確定義 offsetof 這個巨集的實作為：

#undef offsetof
#ifdef __compiler_offsetof
#define offsetof(TYPE, MEMBER)	__compiler_offsetof(TYPE, MEMBER)
#else
#define offsetof(TYPE, MEMBER)	((size_t)&((TYPE *)0)->MEMBER)
#endif

從這邊可以看到，當編譯器沒有定義 __compiler_offsetof 時，會將 offsetof 這個巨集定義為 ((size_t)&((TYPE *)0)->MEMBER)，而在這個定義中透過將 0 強制轉型成 TYPE 的指標使得該結構體的開頭地址為 0，接著再透過對該結構體中的 field MEMBER 取址來計算出 MEMBER 在這個結構體中的位元組偏移量。

TODO : 是否會造成 null pointer dereference

TODO : man page 有提到 padding 的問題，嘗試找到關於其的詳細說明

This macro is useful because the sizes of the fields that compose a structure can vary across implementations, and compilers may insert different numbers of padding bytes between fields. Consequently, an element's offset is not necessarily given by the sum of the sizes of the previous elements.

是否能找到 offsetof 的實作，~~參考：https://en.wikipedia.org/wiki/Offsetof~~

顯然「第一手材料」就在 Linux 核心原始程式碼，不要翻閱 Wikipedia (裡頭可能存在若干錯誤)。

Image Not Showing Possible Reasons
The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported
Learn More →

jserv

回覆老師：

我原先是透過 include 找到 offsetof 這個巨集在系統中 stddef.h 這個標頭檔中的定義是：

#define offsetof(t, d) __builtin_offsetof(t, d)

但是並沒有找到關於 __builtin_offsetof(t, d) 的實作，在老師提醒後我去翻閱 GitHub 上 Linux 中專案中於 stddef.h 的原始碼就有找到實際的定義了，感謝老師的提醒！

#if defined(__GNUC__)
#define __LIST_HAVE_TYPEOF 1
#endif

#ifndef container_of
#ifdef __LIST_HAVE_TYPEOF
#define container_of(ptr, type, member)                            \
    __extension__({                                                \
        const __typeof__(((type *) 0)->member) *__pmember = (ptr); \
        (type *) ((char *) __pmember - offsetof(type, member));    \
    })
#else
#define container_of(ptr, type, member) \
    ((type *) ((char *) (ptr) -offsetof(type, member)))
#endif
#endif

格式化問題：在上方的巨集中可發現 (ptr) -offsetof 的 - 與 offsetof 間缺少空格。

以 clang-format-11 及 clang-format-12 進行測試，若是將 Clang-format Style Option 中的 SpaceAfterCStyleCast 設為 false 會發現 (ptr) 與 -offset 間的空白消失：

嘗試用新版的 clang-format，例如 clang-format-12，後者已被 Ubuntu Linux 收錄。在 .ci/check-format.sh 中，指定用 clang-format-12

Image Not Showing Possible Reasons
The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported
Learn More →

jserv

#define container_of(ptr, type, member) \
    ((type *)((char *)(ptr)-offsetof(type, member)))

// .clang-format
...
SpaceAfterCStyleCast: false

因此推測是 clang-format 將前面的 (char *) (ptr) 當成是轉型，而後面的 -offsetof 則被判斷成負數，造成減號 - 後的空格被移除。

可透過將 (char *) (ptr) 加上額外的括號，使排版與預期相符：

#define container_of(ptr, type, member) \
    ((type *) (((char *) (ptr)) - offsetof(type, member)))

// .clang-format
...
SpaceAfterCStyleCast: true

container_of 是一個透過使用 offsetof 來獲取給定的結構體 type 中某個 field member 的指標 ptr 所屬的結構體物件的地址。

主要的計算方式為使用 offsetof 獲取 member 相對於結構體 type 開頭的位元組偏移量，再將 member 的指標 ptr 中儲存的地址扣除該偏移量以計算出結構體的開頭地址。

然而在 C 語言標準文件中的 6.5.6 Additive operators 有關於加法以及減法運算子的說明，而在該節的第 7 項有說明當對一指向某物件的指標進行加減法時，會和對陣列的首個元素的地址進行加減運算有著相同表現。

For the purposes of these operators, a pointer to an object that is not an element of an array behaves the same as a pointer to the first element of an array of length one with the type of the object as its element type.

而在其後的第 8 項則有關於對指向陣列元素的指標進行加減運算時會有什麼表現：

When an expression that has integer type is added to or subtracted from a pointer, the result has the type of the pointer operand. If the pointer operand points to an element of an array object, and the array is large enough, the result points to an element offset from the original element such that the difference of the subscripts of the resulting and original array elements equals the integer expression.

綜合第 7 項與第 8 項我們可以知道若是直接對一指標進行加減運算（假設 ptr + k ）的話，其效果就猶如陣列索引的移動，而不是對記憶體位置直接加減 k 個位元組。

((type *) ((char *) (ptr) - offsetof(type, member)))

也因此在 container_of 這個巨集的定義中：可以看到它是先將指標的型別轉成 char * 使其在進行加減運算時能夠確實的將記憶體位置以一個位元組的單位進行計算，以搭配 offsetof 的計算結果來得到正確的結構體物件的開頭地址。

相似的概念有也在你所不知道的C語言：指標篇中的回頭看 C 語言規格書的部份被提及

延伸問題：是否能將 char * 夠改成 void *？

根據規格書中 6.5.6 Addit ive operators 對加法運算部份的描述：

For addition, either both operands shall have arithmetic type, or one operand shall be a pointer to a complete object type and the other shall have integer type. (Incrementing is equivalent to adding 1.)

可以看到加法運算有兩種情境：

兩運算元皆為算術型態
一運算元為指向 Complete Object Type 的指標，另一運算元整數型別

而在 container_of 這個巨集中，很明顯的屬於第二種情境，因此需要檢查的就是 void * 是否為一個「指向 Complete Object Type 的指標」。

然而在規格書中的 6.2.5 Types 的部份則說明了型別的類型以及 void 是什麼類型的型別：

The meaning of a value stored in an object or returned by a function is determined by the type of the expression used to access it. (An identifier declared to be an object is the simplest such expression; the type is specified in the declaration of the identifier.) Types are partitioned into object types (types that describe objects) and function types (types that describe functions). At various points within a translation unit an object type may be incomplete (lacking sufficient information to determine the size of objects of that type) or complete (having sufficient information).

在第 1 項就將 type 分成 object type 以及 function type 兩類，而 object type 又可以再分成 complete 與 incomplete 兩種。

The void type comprises an empty set of values; it is an incomplete object type that cannot be completed.

第 19 項則說明了 void 型別是一個 incomplete object type。

從綜合以上可以知道 void 不是 Complete Object Type，因此 void * 也不會是「指向 Complete Object Type 的指標」，所以若是將巨集中的 char * 改成 void * 的話，該巨集將不屬於加法運算的任一種情境。

const __typeof__(((type *) 0)->member) *__pmember = (ptr);

除了計算結構體開頭地址的部份之外，在定義中還使用到了 __typeof__ 這個 GNU C Extension 中定義的關鍵字 typeof 的 Alternate Keyword，透過使用這個關鍵字並配合另一個 GNU C Extension Statements and Declarations in Expressions 使用，這個巨集會先使用結構體 type 的 null pointer 來存取目標 field member 的類別，然後宣告一個該類別的變數 __pmember 並將 ptr 中的地址賦值給它，以達到檢查行別的效果。

可以透過簡單的實驗看到這個型別確認會帶來什麼效果：

$ cat test.c && gcc test.c && echo ">>done<<"
#include <stdio.h>
#include <stddef.h>

#define container_of(ptr, type, member) \
    ((type *) ((char *) (ptr) - offsetof(type, member)))

typedef struct TEST { 
    int foo;
    struct TEST *bar;
} test;

int main(int argc, char const *argv[])
{
    test t = {.foo = 1, .bar = &t};
    test *a = container_of(&t.foo, test, bar);
    return 0;
}
>>done<<

當沒有使用 typeof 進行型別檢查時，透過 gcc 可以順利的編譯過，且沒有任何錯誤或是警告。但若是加上 typeof 進行型別檢查的話，雖然一樣可以編譯過，但這次就出現了型別警告的訊息了。

$ cat test.c && gcc test.c && echo ">>done<<"
#include <stddef.h>
#include <stdio.h>

#define container_of(ptr, type, member)                            \
    ({                                                             \
        const __typeof__(((type *) 0)->member) *__pmember = (ptr); \
        (type *) ((char *) __pmember - offsetof(type, member));    \
    })

typedef struct TEST {
    int foo;
    struct TEST *bar;
} test;

int main(int argc, char const *argv[])
{
    test t = {.foo = 1, .bar = &t};
    test *a = container_of(&t.foo, test, bar);
    return 0;
}
test.c: In function ‘main’:
test.c:7:61: warning: initialization of ‘struct TEST * const*’ from incompatible pointer type ‘int *’ [-Wincompatible-pointer-types]
    7 |         const __typeof__(((type *) 0)->member) *__pmember = (ptr); \
      |                                                             ^
test.c:21:15: note: in expansion of macro ‘container_of’
   21 |     test *a = container_of(&t.foo, test, bar);
      |               ^~~~~~~~~~~~
test.c:7:61: note: (near initialization for ‘a’)
    7 |         const __typeof__(((type *) 0)->member) *__pmember = (ptr); \
      |                                                             ^
test.c:21:15: note: in expansion of macro ‘container_of’
   21 |     test *a = container_of(&t.foo, test, bar);
      |               ^~~~~~~~~~~~
>>done<<

TODO :
在上面的巨集定義中使用了 #ifdef __LIST_HAVE_TYPEOF 來決定是有要使用 GNU C 的兩個擴充語法，但 __LIST_HAVE_TYPEOF 會隨著 __GNUC__ 的定義被定義，是否有需要在其中使用 __extension__ 以及 typeof 的 Alternate Keywork 來避免編譯器錯誤

-std=c89

參考：
https://gcc.gnu.org/onlinedocs/gcc/Alternate-Keywords.html
https://gcc.gnu.org/onlinedocs/gcc/C-Dialect-Options.html

針對佇列的操作

`q_new`

struct list_head *q_new()
{
    struct list_head *head = malloc(sizeof(struct list_head));

    // check malloc not return null (implies error or size is 0)
    if (head != NULL)
        INIT_LIST_HEAD(head);
    return head;
}

根據 The GNU C Library 中 3.2.3.1 Basic Memory Allocation 的說明，malloc 會在 size 為 0 或是無法分配空間時回傳 null pointer，因此需要在 malloc 後檢查 head 是否為 NULL。

`q_size`

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

    int count = 0;
    for (struct list_head *ptr = head->next; ptr != head; ptr = ptr->next)
        ++count;

    return count;
}

將 head == NULL 改為 !head，保持程式碼的精簡

Image Not Showing Possible Reasons
The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported
Learn More →

jserv

`q_insert_head` 及 `q_insert_tail`

避免濫用 &，否則很難區分 operator 和英語的原本意思

Image Not Showing Possible Reasons
The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported
Learn More →

jserv

bool q_insert_head(struct list_head *head, char *s)
{
    if (!head)
        return false;  // head should not be null
    
    element_t *node = malloc(sizeof(element_t));
    if (!node)
        return false;  // malloc for new node failed

    node->value = malloc(strlen(s) + 1);
    if (!node->value) {
        free(node);
        return false;  // malloc for string failed
    }

    // copy string content
    memcpy(node->value, s, strlen(s));
    node->value[strlen(s)] = '\0';

    // insert new node after head
    node->list.prev = head;
    node->list.next = head->next;
    head->next = &node->list;
    node->list.next->prev = &node->list;

    return true;
}

若要加入一個節點 node 到佇列首位的話，需要修改到 4 個連結：

head 指向首位節點的連結
node 指向前一節點的連結
node 指向後一節點的連結
原本首位節點指向前一個節點的連結

而其中要注意的部份是第 4 項的連結，若是一開始就將首位節點 head->next 更新的話，後面會沒辦法直接取得原本的首位節點（假設沒另外存起來的話）。

而其實新增節點的操作在 list.h 中就有被以函式的形式被實作了，叫做 list_add，所以其實 q_insert_head 可以再簡化成：

bool q_insert_head(struct list_head *head, char *s)
{
    ...

    // insert new node after head
    list_add(&node->list, head);
    return true;
}

q_insert_tail 要做的是跟 q_insert_head 相似，只有更新節點間連結的部份不同：

head 指向末位節點的連結
node 指向前一節點的連結
node 指向後一節點的連結
原本末位節點指向後一個節點的連結

而這個操作也有在 list.h 中被實作出來，所以可以用 list_add_tail 簡單的完成。

bool q_insert_tail(struct list_head *head, char *s)
{
    ...

    // insert new node after head
    list_add_tail(&node->list, head);
    return true;
}

除了使用 list.h 中提供的巨集簡化程式碼之外，也使用 strdup 來簡化 malloc、memcpy、string[size] = '\0' 的操作：

    ...
    node->value = strdup(s);
    if (!node->value) {
        free(node);
        return false;  // malloc for string failed
    }

    // insert new node after head
    list_add(&node->list, head);     // or list_add_tail
    return true;

`q_remove_head` 和 `q_remove_tail`

element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
    if (!head || list_empty(head))
        return NULL;  // cannot remove a node from NULL or empty list


    // get node and unlink (remove) this node from list
    element_t *first_entry = list_first_entry(head, element_t, list);
    list_del(head->next);

    // copy target node's value if need
    if (sp) {
        strncpy(sp, first_entry->value, bufsize - 1);
        sp[bufsize - 1] = '\0';
    }
    return first_entry;
}

element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize)
{
    if (!head || list_empty(head))
        return NULL;  // cannot remove a node from NULL or empty list

    // get node and unlink (remove) this node from list
    element_t *last_entry = list_last_entry(head, element_t, list);
    list_del(head->prev);

    // copy target node's value if need
    if (sp) {
        strncpy(sp, last_entry->value, bufsize - 1);
        sp[bufsize - 1] = '\0';
    }
    return last_entry;
}

q_remove_head 跟 q_remove_tail 也有類似 list_add 的函式可以用，叫做 list_del，而這個函式可以用在任一節點上，所以只需要透過 list_first_entry 和 list_last_entry 兩個巨集拿到頭尾節點後就可以使用 list_del 移除連結並釋放資源。

`q_delete_mid`

bool q_delete_mid(struct list_head *head)
{
    if (!head || list_empty(head))
        return false;  // NULL or empty list

    // move to mid node
    struct list_head *ptr = head->next;
    for (struct list_head *rev = head->prev; rev != ptr && rev != ptr->next;) {
        ptr = ptr->next;
        rev = rev->prev;
    }

    // remove this node
    list_del(ptr);

    // delete entry
    element_t *entry = list_entry(ptr, element_t, list);
    free(entry->value);
    free(entry);
    return true;
}

用兩個指標 ptr 與 rev 分別從佇列頭尾而行，直到兩指標交會或是 rev 指到 ptr 的下一個節點，此時 ptr 即為中間點。

`q_sort` 和 `mergesort`

在 singly-linked list 中，若要實作一個遞迴版的 mergesort 的話，可以簡單的透過以下程式碼：






































struct list_head *mergesort(struct list_head *start, struct list_head *end)
{
    // if only one node, just return
    if (start == end)
        return start;

    // find mid point and split into 2 parts
    struct list_head *mid = start, *flag = start;
    for (; flag->next && flag->next->next; flag = flag->next->next)
        mid = mid->next;

    flag = mid->next;
    mid->next = NULL;

    // do mergesort on both parts
    struct list_head *left = mergesort(start, mid);
    struct list_head *right = mergesort(flag, end);

    // merge 2 sorted list
    struct list_head tmp_head, *ptmp = &tmp_head;

    for (element_t *l, *r; left && right; ptmp = ptmp->next) {
        l = list_entry(left, element_t, list);
        r = list_entry(right, element_t, list);

        if (strcmp(l->value, r->value) < 0) {
            ptmp->next = left;
            left = left->next;
        } else {
            ptmp->next = right;
            right = right->next;
        }
    }

    ptmp->next = left ? left : right;

    return tmp_head.next;
}

雖然這個方式也可以應用在 circular doubly-linked list 中，但很明顯的有以下幾點問題需要解決：

頭尾相連
擁有 node->prev

因此需要對上面的 mergesort 進行一些修補以避免破壞 circular doubly-linked list 的特性：

struct list_head *mergesort(struct list_head *start, struct list_head *end)
{
    ...

    ptmp->next = left ? left : right;

    // repair prev links
    for (ptmp = tmp_head.next; ptmp->next != NULL; ptmp = ptmp->next)
        ptmp->next->prev = ptmp;

    return tmp_head.next;
}

在原本 singly-linked list 的版本中，在 merge 兩個 sorted linked list 時只需要比對 left 以及 right 的值，並將較小的節點 append 到 tmp_head 即可。但若是對 doubly linked list 進行一樣的操作的話，會造成排序後的節點的 node->prev 所指向的節點與預期中的前一個節點不同，因此在 doubly 的版本中，在 merge 完之後需要再依序走訪 new_head 並將各節點的 node->prev 指向正確的節點。

除了 node->prev 需要指向正確的節點之外，還需要注意到 head 是一個頭尾相連的 circular linked list，而 mergesort 中第 9 列用來尋找中間點的 for 迴圈的結束條件是 fast->next == NULL 或 fast->next->next == NULL，因此在傳入佇列的首尾節點之前，需要將佇列的尾端節點的 next 指向 NULL，以免造成無限迴圈。

void q_sort(struct list_head *head)
{
    if (head == NULL || head->prev == head->next)
        return;

    // do merge sort on list
    struct list_head *start = head->next, *end = head->prev;
    end->next = NULL;

    // connect head and sorted list
    head->next = mergesort(start, end);
    head->next->prev = head;

    // repair head.prev
    for (; end->next != NULL; end = end->next)
        ;
    end->next = head;
    head->prev = end;
}

而在 mergesort 結束後，由於 head->next 有可能並非實際擁有最小值的節點，因此需要將 head 與 mergesort 回傳的 list 重新建立雙向鏈結；相似地，head->prev 在 mergesort 前已改指向 NULL，因此需要移動到最後一個節點，並將其與 head 重新建立雙向鏈結。

簡化 `mergesort`

以指標的指標改寫 merge 部份

    ...
    // merge 2 sorted list
    struct list_head *new_head = start, **phead = &new_head;

    for (element_t *l, *r; left && right; phead = &(*phead)->next) {
        l = list_entry(left, element_t, list);
        r = list_entry(right, element_t, list);

        struct list_head **next;
        next = strcmp(l->value, r->value) < 0 ? &left : &right;
        *phead = *next;
        *next = (*next)->next;
    }
    *phead = left ? left : right;
    ...

**next 會被 cppcheck 的 style 檢查抱怨 scope 可以縮小，所以需要放在迴圈內，而長度限制則會讓它分成兩行，所以就乾脆讓 **next 的宣告與賦值分成兩行了。

排序完再修復 `prev` 連結

void q_sort(struct list_head *head)
{
    if (!head || head->prev == head->next)
        return;

    // do merge sort on list
    struct list_head *start = head->next, *end = head->prev;
    end->next = NULL;

    // connect head and sorted list
    head->next = mergesort(start, end);
    head->next->prev = head;

    // repair all prev links
    for (end = head; end->next; end = end->next)
        end->next->prev = end;
    end->next = head;
    head->prev = end;
}

在以指標的指標重新實作時發現，其實 mergesort 中可以不使用 prev，所以可以把最後修復 prev 的 for 迴圈移除，改在 q_sort 最後一次完成，不僅可以讓程式碼更精簡，也能避免在遞迴呼叫時重複修正已修正過的 prev 連結。

迭代 mergesort

TODO

使用 bitwise OR 替代 `ptmp->next = left ? left : right;` 以減少分支

`q_delete_dup`

bool q_delete_dup(struct list_head *head)
{
    if (head == NULL)
        return false;

    LIST_HEAD(duplist);
    element_t *ptr = NULL, *next;

    bool found = false;
    char *prev = "";

    list_for_each_entry_safe (ptr, next, head, list) {
        if (strcmp(prev, ptr->value) == 0) {
            found = true;
            list_move(&ptr->list, &duplist);
        }
        else {
            if (found)
                list_move(ptr->list.prev, &duplist);

            found = false;
            prev = ptr->value;
        }
    }

    list_for_each_entry_safe (ptr, next, &duplist, list) {
        free(ptr->value);
        free(ptr);
    }

    return true;
}

q_delete_dup 的實作概念是額外建立一個佇列 duplist 來存放 head 中重複的節點。

這個實作想法利用了 head 為遞增排序的特性，因此走訪每個節點時只須與前一個節點比較即可，若當前節點與前一個節點擁有相同值的話，就將其移動到 duplist 中。

待 head 中的所有節點都走訪過之後，再搭配 container_of 相關的 macro 來釋放 duplist 中的所有節點以及它們的資料。

上方的 q_delete_dup 實作在 6edd0f0 的修正後就會被檢查出錯誤，因此需要進行修正。

修正並簡化 `q_delete_dup`

原版是從首位節點開始依序與前一個節點進行比較，直到走到最後一個節點為止，然而當最後 2 個（或更多）節點相同時，最後一個節點需要在 list_for_each_entry_safe 後進行額外的確認，但又因為 list_for_each_entry_safe 的結束條件是 ptr->list != head，所以在結束後需要用 ptr->list.prev 才能取得最後一個節點，所以我決定直接重寫這部份。

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


    LIST_HEAD(duplist);

    bool prev = false;
    element_t *ptr = list_entry(head->next, element_t, list), *next = ptr;

    for (bool same; next->list.next != head; ptr = next) {
        next = list_entry(ptr->list.next, element_t, list);
        same = !strcmp(ptr->value, next->value);
        if (same || prev)
            list_move(&ptr->list, &duplist);
        prev = same;
    }
    // don't forget last node
    if (prev)
        list_move(&ptr->list, &duplist);

    // delete each element in dup list
    list_for_each_entry_safe (ptr, next, &duplist, list) {
        free(ptr->value);
        free(ptr);
    }

    return true;
}

修正後的版本則是從首位節點開始依序與後一個節點進行比較，並將 list_for_each_entry_safe 替換成以 next->list.next != head 為結束條件的 for 迴圈，讓 ptr 在結束迴圈時的狀態是指向最後一個節點，以便檢查是否需要將最後一個節點也移入 duplist 中。此外，也透過新增一個布林變數來簡化迴圈內所需的操作。

理解 Linux 核心中的排序實作

圖解 list_sort 的 `do while` 部份

在第一次看這段程式碼的時候，想了很久都不知道在幹麻，因此只好直接畫出來一步步觀察它的規律以及奧妙，並參考了你所不知道的 C 語言: linked list 和非連續記憶體和 blueskyson 以及 kdnvt 的開發紀錄來輔助理解這部份到底在做什麼。

`do while` 部份程式碼
























do {
    size_t bits;
    struct list_head **tail = &pending;

    // part 1, shift all trailing 1s 
    for (bits = count; bits & 1; bits >>= 1)
        tail = &(*tail)->prev;
    
    // part 2, merge sorted pending
    if (likely(bits)) {
        struct list_head *a = *tail, *b = a->prev;

        a = merge(priv, cmp, b, a);
        a->prev = b->prev;
        *tail = a;
    }

    // part3, add node to pending
    list->prev = pending;
    pending = list;
    list = list->next;
    pending->next = NULL;
    count++;
} while (list);

首先，為了方便後面說明，將 do while 中的程式碼分成三個 part。

每個 count 的操作

由於還不太熟悉 graphviz 的語法導致畫不出看起來整齊的圖，因此這邊使用 drawio 自己畫、自己移動指標觀察規律。而為了簡化圖示，沒有箭頭的格子就代表指向 NULL。

0b0000
- 初始化後 pending 會是空的，而 list 則指向當前未排序串列的首位節點 (後面統一稱作 first )。
- 而進入 do while 的部份後，則因為 count 以及 bits 都為 0，因此只會進行新增節點到 pending 串列的步驟 (part3)。
- 而在 part3 結束後 pending 將會指向 first，而 list 將會移動到 first 的下一個節點 (後面統一稱作 second)。
0b0001
- 接著進入到 count == 0b0001，由於尾端有 1，所以會先進行右移檢查的部份 (part1)。而由於只有最後一位元是 1，因此 tail 會往前走一次，最後指向節點 5 prev，但因為右移結束後不會進入到 if 區塊，因此這段其實不會被用到。
- 再來會進行 part3 的操作，將 first 加入到 pending 中，並在停在 pending 指向 first (4)、list 指向 second (3) 的狀態。

到這邊為止有幾個需要注意的地方：

將 first 新增到 pending 後，first 的 next 會被指向 NULL，也就是說節點被加到 pending 串列後就不能以 next 依序拜訪。
雖然加入 pending 後 next 連結都會被指向 NULL，但是在加入前一輪時其實已經有將 list->next 指向 pending，而 list 其實就是下一輪的 first，也就是說其實可以用 prev 依序拜訪 pending 中的串列。

0b0010
- 再來是 count == 0b0010 的情況，由於最低位元不是 1，因此不用做 part1，但因為 bits != 1 因此要先進行合併 pending 中節點 (part2) 的操作。
- 合併前 a 會先移動到當前 tail 指向的指標所指向的節點（圖中的節點 4 ），而 b 則會指向 a 的前一個節點 (圖中的節點 5)。
- 合併後 4 的 next 會指向 5 ，而 a 則會指向排序後串列的首位節點（在此次合併中為 4），並需要將 a->prev 指向 b->prev（在此次合併中為 NULL）以及將 tail 指向的指標指向 a。
- 而合併後則需要再進行 part3 的操作，最後 pending 會指向 first (2)，而 list 則會指向 second (3)。
0b0011
- 而當 count == 0b0011 時，首先會先進行 part1 移除尾端的連續 1、將 tail 指向 4 的 prev，但因為 bits 為 0，所以其實沒有作用。
- 然後是 part3 的新增節點以及移動指標的操作。最終 pending 會指向 first (3)，而 list 則會指向 7。

進行到這邊，除了單純位移以及新增節點到 pending 串列中之外，還進行了合併 (part2) 的操作，有幾個細節可以注意：

如同合併函式的註解說明，將兩個排序好的串列 a、b 進行合併時只會將 next 連結指向正確的節點，prev 則不會被改變。而合併結束後就用了這個特性，讓新的已排序串列的首位節點的 prev 指向串列 b 的 prev 所指向的節點。
在前面的注意事項有說到 pending 中的節點是以 prev 作為連結互相連結，而 next 雖然在剛被加入 pending 時會被指向 NULL，但是在合併時 next 會被正確的連接、形成正確排序的串列。
雖然在合併前 a、b 節點可以被正確的透過 prev 依序走訪，但是在合併後，不論合併後的已排序串列的首位節點是 a 還是 b，最後能夠透過 pending 以及 prev 連結指標走訪的節點只有排序後串列的首位節點而已（第 14、15 行在做的事）。

0b0100
- 在 count == 0b0100 時，由於尾端沒有連續的 1，因此不須進行位移以及移動 tail 的 part1。但由於 bits != 0，因此需要進行 part2 的合併。
- 首先要先決定要合併的兩個串列，由於 part1 沒有做，因此一已排序串列 a 會指向 3，而另一已排序串列 b 則會指向 2。
- 而這兩個已排序串列合併後新的首位節點 2 將會變成變成新的 a，其 prev 連結則會指向原本 b->prev 指向的 4（由於首位節點沒變，因此指向的節點也沒變），且 tail 指向的 pending 指標則會改指向合併後的首位節點 a。
- 最後則是 part3 的新增節點以及移動指標。操作完成後 pending 將會指向 first (7)，而 list 則會指向 second (6)。

到這邊為止則是又重複了一次 count == 0b0010 的操作，只是這次是兩個不一樣的節點。

0b0101
- 當 count == 0b0101 時，會先進行 part1 將 tail 指向 7 的 prev，接著再進行 part2 的合併。
- 由於 part1 有進行，因此 a 為 7 的 prev 所指向的節點，也就是 2，而 b 則為它的前一個節點 4。而合併後會產生一個新的已排序串列，此時將 a 更新成該串列的首位節點 2，並且將 a->prev 更新、 tail 指向的指標指向 2。
- 最後再將 first (6) 新增到 pending 中，並將 list 指向 NULL，而由於 list 指向 NULL 因此 do while 的部份就結束了。

到這邊為止，大概可以抓到一個規律是：當合併( part2 )發生時，*tail 會指向最接近 pending 開頭的兩個大小皆為

2^{k}

的子串列，並進行合併。

但：

為什麼合併時總會剛好有一對相同大小的子串列能夠進行合併？
為什麼 part1 還能夠剛好將 *tail 移動到到最近一對相同大小的子串列？

還在思考是否能以二進制的規律理解
// TODO :
The cost distribution of queue-mergesort, optimal mergesorts, and
power-of-two rules
Wei-Mei Chen, Hsien-Kuei Hwang, Gen-Huey Chen
Journal of Algorithms 30(2); Pages 423–448, February 1999
https://doi.org/10.1006/jagm.1998.0986
https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.4.5380

合併的規律

count	合併前 (上輪結果)	本輪動作 (位置)
0b0000	[]	add
0b0001	[1]	add
0b0010	[1,1]	merge(0), add
0b0011	[1,2]	add
0b0100	[1,1,2]	merge(0), add
0b0101	[1,2,2]	merge(1), add
0b0110	[1,1,4]	merge(0), add
0b0111	[1,2,4]	add
0b1000	[1,1,2,4]	merge(0), add
0b1001	[1,2,2,4]	merge(1), add
0b1010	[1,1,4,4]	merge(0), add
0b1011	[1,2,4,4]	merge(2), add
0b1100	[1,1,2,8]	merge(0), add
0b1101	[1,2,2,8]	merge(1), add
0b1110	[1,1,4,8]	merge(0), add
0b1111	[1,2,4,8]	add

表格中間 column 的陣列代表該該輪合併前 pending 串列的狀態，每個元素都代表一個「已排序」的串列（如前面圖中著有相同顏色的節點），該元素的數值則代表該串列的長度，而陣列最左側的元素就是當下 pending 指標指向的串列。

`merge_final` 部份

而當 list 指向 NULL 時，代表所有節點都走訪過了，且全部的節點都在 pending 串列中因此最後還需要依序兩兩合併所有 pending 中的已排序串列：














    ...
    list = pending;
    pending = pending->prev;
    for (;;) {
        struct list_head *next = pending->prev;

        if (!next)
            break;
        list = merge(priv, cmp, pending, list);
        pending = next;
    }
    /* The final merge, rebuilding prev links */
    merge_final(priv, cmp, head, pending, list);
}

而要合併 pending 中的子串列可以用類似 iterative merge k sorted list 的方式，依序從 pending 開頭合併到剩下最後兩個子串列。

為什麼剩最後兩個子串列時就停了？

到目前為止的合併過程都只有保證 next 連結會指向正確的節點，而 prev 連結則是用來指向下一個 pending 中的子串列（僅各個子串列的首位節點的 prev 能用來走訪 pending 串列，其他合併後非首位的節點的 prev 則不應該被使用），因此需要趁最後合併時將 prev 復原、指向正確的節點。

static void merge_final(void *priv,
                        list_cmp_func_t cmp,
                        struct list_head *head,
                        struct list_head *a,
                        struct list_head *b)
{
    struct list_head *tail = head;
    uint8_t count = 0;
    
    // part1, merge 2 sorted non-null list
    for (;;) {
        if (cmp(priv, 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;
            }
        }
    }

    // part2, link remain nodes
    tail->next = b;
    do {
        if (unlikely(!++count))
            cmp(priv, b, b);
        b->prev = tail;
        tail = b;
        b = b->next;
    } while (b);

    // make circular
    tail->next = head;
    head->prev = tail;
}

最後的合併大致上與 merge 要做的事相同，首先是 part1 的部份，依序比較兩串列的首位節點，並將較小的節點加到雙向串列的尾端 (tail)，直到其中一個串列為空。

當 part1 完成後，不像是單向鏈結串列可以直接將剩餘的接在後面，由於有 prev 連結需要處理，所以要依序將剩餘的節點加入到尾端並恢復 prev 連結。

問題一：
為什麼要在 part2 中加上 if (unlikely(!++count)) cmp(priv, b, b);？

首先可以先來看原本的註解寫了什麼：

/*
 * If the merge is highly unbalanced (e.g. the input is
 * already sorted), this loop may run many iterations.
 * Continue callbacks to the client even though no
 * element comparison is needed, so the client's cmp()
 * routine can invoke cond_resched() periodically.
 */

從這說明可以知道這是為了兩個子串列非常不平衡時設計的一個分支，每當新增一個節點時就會 ++count，看起來沒什麼意義，但回去看 count 宣告時的型別會發現它是 uint8_t（原始程式碼中是另外使用 typedef 將 u8 定義成 u_int8_t，這邊為了方便解釋直接替換成 uint8_t），所以若是剩餘的節點非常多的時候會因為 overflow 而從頭開始計算，而在 overflow 時就會呼叫 cmp 函數，因此可以達成定期呼叫 cmp 函式的效果。

問題二：
為什麼需要定期呼叫 cmp？
裡面提到的 cond_resched 是什麼？
// TODO

`likely` 與 `unlikely` 巨集

這兩個巨集被定義在 include/linux/compile.h 中。

相關 extension

TODO

其他相關論文

Bottom-up Mergesort: A Detailed Analysis
Wolfgang Panny, Helmut Prodinger
Algorithmica 14(4):340–354, October 1995
https://doi.org/10.1007/BF01294131
https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.6.5260

Queue-Mergesort
Mordecai J. Golin, Robert Sedgewick
Information Processing Letters, 48(5):253–259, 10 December 1993
https://doi.org/10.1016/0020-0190(93)90088-q
https://sci-hub.tw/10.1016/0020-0190(93)90088-Q

使用 Valgrind 對 qtest 進行分析

問題 - 1 `atexit`

尋找問題

原本想直接對 make test 的過程使用 Valgrind 檢查，但是發現自動測試程式是用 python 進行的，所以只好使用 Valgrind 分別檢查各個測資。

若以 Valgrind 執行 qtest 並以 trace-01-ops.cmd 作為輸入測資的話：

$ make && valgrind ./qtest < traces/trace-01-ops.cmd
  CC    qtest.o
  LD    qtest
Freeing queue
==3555496== 4 bytes in 1 blocks are still reachable in loss record 1 of 3
==3555496==    at 0x4842839: malloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==3555496==    by 0x4A5A14E: strdup (strdup.c:42)
==3555496==    by 0x110BF8: linenoiseHistoryAdd (linenoise.c:1236)
==3555496==    by 0x11172B: linenoiseHistoryLoad (linenoise.c:1325)
==3555496==    by 0x10CAAB: main (qtest.c:1101)
==3555496== 
==3555496== 160 bytes in 1 blocks are still reachable in loss record 2 of 3
==3555496==    at 0x4842839: malloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==3555496==    by 0x110BB8: linenoiseHistoryAdd (linenoise.c:1224)
==3555496==    by 0x11172B: linenoiseHistoryLoad (linenoise.c:1325)
==3555496==    by 0x10CAAB: main (qtest.c:1101)
==3555496== 
==3555496== 199 bytes in 19 blocks are still reachable in loss record 3 of 3
==3555496==    at 0x4842839: malloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==3555496==    by 0x4A5A14E: strdup (strdup.c:42)
==3555496==    by 0x110B6C: linenoiseHistoryAdd (linenoise.c:1236)
==3555496==    by 0x11172B: linenoiseHistoryLoad (linenoise.c:1325)
==3555496==    by 0x10CAAB: main (qtest.c:1101)
==3555496==

可以從上方執行紀錄看到有在 linenoiseHistory 時使用到的 malloc 與 strdup 分配到的空間沒被釋放。

























    /* 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;

而實際到該函式檢查則會發現這個函式是在在新增紀錄到 history 這個 char ** 的全域變數中（字串的陣列），而出問題的 1224 行是在分配空間給 history、1236 則是在分配空間給要新增的命令歷史紀錄，而它後來又存到 history 的某個欄位中。到這邊為止可以發現這兩個問題都是跟 history 相關，所以依次檢查 history 是否有哪邊處理的不完善。

依序檢查了 linenoise.c 中使用到 history 的部份似乎都沒什麼問題，所以參考了 laneser 以及 Risheng 兩位的開發紀錄，並在其中看到似乎是在以檔案形式輸入測資時，沒有正確呼叫 freeHistory 造成的錯誤，因此改從 freeHistory 開始回推發生錯誤的原因。

而從 freeHistory 往回推會發現該函式只會被 linenoiseAtExit 呼叫，而 linenoiseAtExit 則是由 atexit 這個函式呼叫，而根據 atexit 的 man page 中的說明可以知道這個函式會在程式正常結束時呼叫設定的函式 function，也就是說 linenoiseAtExit 這個函式只有在 qtest 結束時才會被呼叫。

#include <stdlib.h>

int atexit(void (*function)(void));

知道了可能的問題後，接著對 linenoiseAtExit 函式設定中斷點看看會發生什麼事：

不使用測資、直接執行 qtest 時，程式會在結束後（輸入 quit）進入到 linenoiseAtExit 函式，無 memory leak 相關錯誤。
使用 < 將測資重新導向至 qtest 執行時，程式結束後不會進入 linenoiseAtExit 函式，會出現 memory leak 相關錯誤。
使用 -f 指定測資執行 qtest 時，程式結束後不會進入 linenoiseAtExit 函式，會出現 memory leak 相關錯誤。

可以發現與參考的兩位同學開發紀錄中提到的情況相同，而接下來為了找出是什麼原因造成這個差異，所以使用 GDB 逐步執行並比較不同的輸入方式會發現：

直接執行並手動輸入測資時，會經由 linenoise 進入到 linenoiseRaw 函式
若是用重新導向來輸入測資時，會經由 linenoise 進入到 linenoiseNoTTY 函式
若是用 -f 參數指定測資檔案，則會直接進入到 cmd_select 函式，而不會進入到 linenoise 函式

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;
}

綜合執行結果以及進入的函式差異，可以推測問題可能出在 linenoiseRaw 這個函式中，而 linenoiseRaw 中又呼叫了 enableRawMode 函式，下方為該函式的其中一部份，可以看到在第 8 行出現了前面提到的 atexit 以及 linenoiseAtExit，且 atexit 並沒有在其他地方被呼叫，因此合理推測這就是問題所在。













static int enableRawMode(int fd)
{
    struct termios raw;

    if (!isatty(STDIN_FILENO))
        goto fatal;
    if (!atexit_registered) {
        atexit(linenoiseAtExit);
        atexit_registered = 1;
    }
    if (tcgetattr(fd, &orig_termios) == -1)
        goto fatal;
    ...

嘗試解決問題

推測出問題所在後開始嘗試修改程式碼來解決這個問題：

為了讓三種輸入方式都能夠呼叫到 atexit(linenoiseAtExit)，我在 linenoise.h 以及 linenoise.c 中新增了一函式 setAtExit，並將 atexit 相關的部份移到該函式內：

void setAtExit(void)
{
    if (!atexit_registered) {
        atexit(linenoiseAtExit);
        atexit_registered = 1;
    }
}

並在三種輸入方法都有呼叫到的 run_console 中呼叫此函數來設定在 qtest 結束後需要呼叫 linenoiseAtExit 來釋放資源。

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

    setAtExit();
    ...
}

而重新編譯並用 valgrind 測試 trace-01-ops.cmd 後，可以看到不論是用 -f 指定測資、還是透過重新導向輸入測資，錯誤訊息就如預期的消失了：

$ make && valgrind ./qtest -f traces/trace-01-ops.cmd
make: 對「all」無需做任何事。
cmd> # Test of insert_head and remove_head
cmd> option fail 0
cmd> option malloc 0
cmd> new
l = []
cmd> ih gerbil
l = [gerbil]
cmd> ih bear
l = [bear gerbil]
cmd> ih dolphin
l = [dolphin bear gerbil]
cmd> rh dolphin
Removed dolphin from queue
l = [bear gerbil]
cmd> rh bear
Removed bear from queue
l = [gerbil]
cmd> rh gerbil
Removed gerbil from queue
l = []
cmd> 
Freeing queue

$ make && valgrind ./qtest < traces/trace-01-ops.cmd
make: 對「all」無需做任何事。
l = []
l = [gerbil]
l = [bear gerbil]
l = [dolphin bear gerbil]
Removed dolphin from queue
l = [bear gerbil]
Removed bear from queue
l = [gerbil]
Removed gerbil from queue
l = []
Freeing queue

問題 - 2 `test_malloc`

尋找問題

在解決 atexit 的問題後，繼續以 Valgrind 對其他測資進行測試，發現在執行 trace-14-perf.cmd 這個測資時會跳出大約 300 行的錯誤訊息，查看了測資後發現是在測 reverse 以及 sort 兩函式的效率，而這兩個操作的測試函式 do_reverse 及 do_sort 中有使用 alarm 來中斷執行過久的函式。

若將 harness.c 中的 time_limit 調高到 99999 的話，會發現操作都能順利完成， Valgrind 也不會跳錯誤訊息，所以初步推測問題是出在 singal 相關操作的部份。

而為了簡化問題，先將 trace-14-perf.cmd 中的 sort 操作移除：

# Test performance of insert_tail, reverse, and sort
option fail 0
option malloc 0
new
ih dolphin 1000000
it gerbil 1000000
reverse

接著再重新以 Valgrind 檢查問題：

$ make && valgrind ./qtest < traces/trace-14-perf.cmd
make: 對「all」無需做任何事。
l = []
ERROR: Time limit exceeded.  Either you are in an infinite loop, or your code is too inefficient
ERROR: Insertion of dolphin failed (1 failures total)
l = [dolphin ... ]
ERROR: Time limit exceeded.  Either you are in an infinite loop, or your code is too inefficient
ERROR: Insertion of gerbil failed (2 failures total)
l = [dolphin ... ]
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 ... ]
Freeing queue
ERROR: Time limit exceeded.  Either you are in an infinite loop, or your code is too inefficient
ERROR: Freed queue, but 20741 blocks are still allocated
==1199500== 48 bytes in 1 blocks are possibly lost in loss record 1 of 6
==1199500==    at 0x4842839: malloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==1199500==    by 0x10E65B: test_malloc (harness.c:138)
==1199500==    by 0x10E8D3: test_strdup (harness.c:217)
==1199500==    by 0x10EB23: q_insert_head (queue.c:67)
==1199500==    by 0x10C322: do_ih (qtest.c:201)
==1199500==    by 0x10D5AE: interpret_cmda (console.c:185)
==1199500==    by 0x10DAE6: interpret_cmd (console.c:208)
==1199500==    by 0x10E593: run_console (console.c:651)
==1199500==    by 0x10CAD0: main (qtest.c:1117)
==1199500== 
==1199500== 56 bytes in 1 blocks are still reachable in loss record 2 of 6
==1199500==    at 0x4842839: malloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==1199500==    by 0x10E65B: test_malloc (harness.c:138)
==1199500==    by 0x10EA83: q_new (queue.c:22)
==1199500==    by 0x10C46A: do_new (qtest.c:128)
==1199500==    by 0x10D5AE: interpret_cmda (console.c:185)
==1199500==    by 0x10DAE6: interpret_cmd (console.c:208)
==1199500==    by 0x10E593: run_console (console.c:651)
==1199500==    by 0x10CAD0: main (qtest.c:1117)
==1199500== 
==1199500== 64 bytes in 1 blocks are definitely lost in loss record 3 of 6
==1199500==    at 0x4842839: malloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==1199500==    by 0x10E65B: test_malloc (harness.c:138)
==1199500==    by 0x10EB0E: q_insert_head (queue.c:62)
==1199500==    by 0x10C322: do_ih (qtest.c:201)
==1199500==    by 0x10D5AE: interpret_cmda (console.c:185)
==1199500==    by 0x10DAE6: interpret_cmd (console.c:208)
==1199500==    by 0x10E593: run_console (console.c:651)
==1199500==    by 0x10CAD0: main (qtest.c:1117)
==1199500== 
==1199500== 64 bytes in 1 blocks are definitely lost in loss record 4 of 6
==1199500==    at 0x4842839: malloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==1199500==    by 0x10E65B: test_malloc (harness.c:138)
==1199500==    by 0x10EB7F: q_insert_tail (queue.c:92)
==1199500==    by 0x10C01D: do_it (qtest.c:290)
==1199500==    by 0x10D5AE: interpret_cmda (console.c:185)
==1199500==    by 0x10DAE6: interpret_cmd (console.c:208)
==1199500==    by 0x10E593: run_console (console.c:651)
==1199500==    by 0x10CAD0: main (qtest.c:1117)
==1199500== 
==1199500== 497,712 bytes in 10,369 blocks are still reachable in loss record 5 of 6
==1199500==    at 0x4842839: malloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==1199500==    by 0x10E65B: test_malloc (harness.c:138)
==1199500==    by 0x10E8D3: test_strdup (harness.c:217)
==1199500==    by 0x10EB23: q_insert_head (queue.c:67)
==1199500==    by 0x10C322: do_ih (qtest.c:201)
==1199500==    by 0x10D5AE: interpret_cmda (console.c:185)
==1199500==    by 0x10DAE6: interpret_cmd (console.c:208)
==1199500==    by 0x10E593: run_console (console.c:651)
==1199500==    by 0x10CAD0: main (qtest.c:1117)
==1199500== 
==1199500== 663,680 bytes in 10,370 blocks are still reachable in loss record 6 of 6
==1199500==    at 0x4842839: malloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==1199500==    by 0x10E65B: test_malloc (harness.c:138)
==1199500==    by 0x10EB0E: q_insert_head (queue.c:62)
==1199500==    by 0x10C322: do_ih (qtest.c:201)
==1199500==    by 0x10D5AE: interpret_cmda (console.c:185)
==1199500==    by 0x10DAE6: interpret_cmd (console.c:208)
==1199500==    by 0x10E593: run_console (console.c:651)
==1199500==    by 0x10CAD0: main (qtest.c:1117)
==1199500==

可以從這些錯誤訊息發現，這些沒被釋放的記憶體空間都是從 harness.c 中的 test_malloc 這個函式中產生的，而根據作業說明以及查看 harness.c 中的程式碼，會知道這個函式是用來包裝 malloc 並紀錄已分配的記憶體，來檢查 q_free 等功能是否有正確被實作。

而在 qtest 的錯誤訊息中可以看到在 Freeing queue 時，由於超出 alarm 設定的時間，因此有部份應該被釋放的記憶體空間尚未被釋放：

Freeing queue
ERROR: Time limit exceeded.  Either you are in an infinite loop, or your code is too inefficient
ERROR: Freed queue, but 20741 blocks are still allocated

若在程式碼中尋找 Freeing queue 這個訊息的話，會發現這個訊息是當 qtest 收到 quit 命令後的提示訊息，而在印出訊息後就會進行 q_free：

static bool queue_quit(int argc, char *argv[])
{
    report(3, "Freeing queue");
    if (lcnt > big_list_size)
        set_cautious_mode(false);

    if (exception_setup(true))
        q_free(l_meta.l);
    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;
}

因此這邊猜測是 q_free 進行到一半時就因 alarm 的設定而產生 SIGALRM ，而在 queue_init 中又有透過 signal(SIGALRM, sigalrmhandler); 設定當 SIGALRM 發生時要進行的處理（使用 siglongjmp 跳到 exception_setup 進行後續處理），造成 q_free 沒辦法釋放所有 allocated 串列中紀錄的記憶體空間。

嘗試解決

從上面的過程可以推測出問題出在 q_free 沒辦法釋放 allocated 這個鏈結串列中紀錄的記憶體空間，因此這邊嘗試為檢查是否有空間尚未被釋放的函式 allocation_check 新增一個參數來決定是否要在檢查後釋放所有空間：

size_t allocation_check(bool do_release)
{
    size_t remain = allocated_count;

    if (do_release) {
        for (block_ele_t *ptr = allocated, *next; ptr; ptr = next) {
            next = ptr->next;
            free(ptr);
        }
        allocated_count = 0;
    }
    return remain;
}

並且為 qtest 中使用到此函式的部份進行修改（傳送參數 true ），接著再重新以 valgrind 測試在超時後是否仍有記憶體沒被釋放：

$ make && valgrind ./qtest < traces/trace-14-perf.cmd
  CC    qtest.o
  CC    harness.o
  CC    queue.o
  LD    qtest
l = []
ERROR: Time limit exceeded.  Either you are in an infinite loop, or your code is too inefficient
ERROR: Insertion of dolphin failed (1 failures total)
l = [dolphin ... ]
ERROR: Time limit exceeded.  Either you are in an infinite loop, or your code is too inefficient
ERROR: Insertion of gerbil failed (2 failures total)
l = [dolphin ... ]
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 ... ]
Freeing queue
ERROR: Time limit exceeded.  Either you are in an infinite loop, or your code is too inefficient
ERROR: Freed queue, but 68081 blocks are still allocated

可以看到這次雖然仍然因為超時而中斷 q_free 的操作，並且有 68081 個 blocks 偵測出沒被正確釋放，但是後面卻沒出現 Valgrind 的錯誤訊息了，這與上述修改的預期結果相符。

若是多執行幾次會發現，其實這個問題沒有完全解決，Valgrind 仍有機會跳出錯誤訊息：

$ make && valgrind ./qtest < traces/trace-14-perf.cmd
make: 對「all」無需做任何事。
l = []
ERROR: Time limit exceeded.  Either you are in an infinite loop, or your code is too inefficient
ERROR: Insertion of dolphin failed (1 failures total)
l = [dolphin ... ]
ERROR: Time limit exceeded.  Either you are in an infinite loop, or your code is too inefficient
ERROR: Insertion of gerbil failed (2 failures total)
l = [dolphin ... ]
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 ... ]
Freeing queue
ERROR: Time limit exceeded.  Either you are in an infinite loop, or your code is too inefficient
ERROR: Freed queue, but 106095 blocks are still allocated
==1670281== 48 bytes in 1 blocks are definitely lost in loss record 1 of 1
==1670281==    at 0x4842839: malloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==1670281==    by 0x10E65B: test_malloc (harness.c:138)
==1670281==    by 0x10E8D3: test_strdup (harness.c:217)
==1670281==    by 0x10EB3B: q_insert_head (queue.c:67)
==1670281==    by 0x10C322: do_ih (qtest.c:201)
==1670281==    by 0x10D5AE: interpret_cmda (console.c:185)
==1670281==    by 0x10DAE6: interpret_cmd (console.c:208)
==1670281==    by 0x10E593: run_console (console.c:651)
==1670281==    by 0x10CAD0: main (qtest.c:1117)
==1670281==

可以看到這個錯誤仍發生在 test_malloc 中，但這次卻只有一個 block 沒被釋放，且這個記憶體位址是 definitely lost in loss record。

若是回到 test_malloc 中會發現函式中其實只是呼叫 malloc 後再紀錄到 allocated 這個串列中而已，因此初步推測是在 malloc 後，但是在新增到 allocated 之前發生了 SIGALRM，所以即使在 allocation_check 時手動釋放了 allocated 中的紀錄，也會因為這個 block 根本沒被紀錄而造成 memory leak 的發生。

初步解法：
若是有辦法暫時暫停 alarm 的計時器的話，或許能夠讓所有 test_malloc 中 malloc 的空間能夠被正確加入到 allocated 串列中，以確保後它能夠在後去操作被正確釋放。

問題 - 3

尋找問題

嘗試解決

為 qtest 新增 shuffle 功能

新增命令

可以在 console_init 中透過 ADD_COMMAND 或是 add_cmd 新增測試時的命令，兩者的差異在於前者是透過巨集的 Stringizing 以及 Concatenation 來簡化呼叫 add_cmd 要傳遞的參數，而 ADD_COMMAND 則會根據參數來設定命令的名稱以及執行命令時要呼叫的對應函式。

Signal

實作 shuffle 命令

static bool do_shuffle(int argc, char *argv[])
{
    // check queue length
    if (!l_meta.l)
        report(3, "Warning: Calling shuffle on null queue");
    else if (q_size(l_meta.l) == 0)
        report(3, "Warning: Calling shuffle on empty queue");
    error_check();


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

    show_queue(3);

    return !error_check();
}

當 shuffle 命令被執行時，會先呼叫此函式，而這個函式參考了 do_sort 加入了佇列的檢查以及設定例外，接著才會呼叫 q_shuffle 函式。

TODO : check argc

void q_shuffle(struct list_head *head)
{
    // check queue length
    int len = q_size(head);
    if (len <= 1)
        return;  // NULL, empty, only 1 node


    // do shuffle
    for (struct list_head *ptr = head->prev; --len; ptr = ptr->prev) {
        // pick random node and put at node[len]
        int target = rand() % (len + 1);

        // swap if target != len
        if (target != len) {
            // move to target node
            struct list_head *node = head->next;
            for (int i = 0; i < target; ++i)
                node = node->next;

            // swap node data
            element_t *ptr_entry = container_of(ptr, element_t, list);
            element_t *node_entry = container_of(node, element_t, list);

            char *tmp = ptr_entry->value;
            ptr_entry->value = node_entry->value;
            node_entry->value = tmp;
        }
    }
}

而在 shuffle 函式則是參考了 Fisher–Yates shuffle 的 modern method 進行實作。

為 qtest 新增 web 功能

實作 web 命令

Jim Huang

2022/02/21 04:03:51

(ptr) -offsetof 的 - 與 offsetof 間

去研究 clang-format，看如何改進程式碼排版 (Edited)

freshLiver

2022/02/22 18:17:36

若將 SpaceAfterCStyleCast 設為 false 的話，會發現 (ptr) -offsetof 間的空格移除，因此推測 -offset(...)是被當作負數了，可以將 (char *)(ptr) 以額外括弧包住來解決這問題。

2022q1 Homework1 (lab0)

tags: linux2022

環境

實作 queue 相關函式

結構體說明

為什麼 element_t 中包含了 list_head

巨集說明

針對佇列的操作

q_new

q_size

q_insert_head 及 q_insert_tail

q_remove_head 和 q_remove_tail

q_delete_mid

q_sort 和 mergesort

簡化 mergesort

以指標的指標改寫 merge 部份

排序完再修復 prev 連結

迭代 mergesort

使用 bitwise OR 替代 ptmp->next = left ? left : right; 以減少分支

q_delete_dup

修正並簡化 q_delete_dup

理解 Linux 核心中的排序實作

圖解 list_sort 的 do while 部份

do while 部份程式碼

每個 count 的操作

合併的規律

merge_final 部份

likely 與 unlikely 巨集

其他相關論文

使用 Valgrind 對 qtest 進行分析

問題 - 1 atexit

尋找問題

嘗試解決問題

問題 - 2 test_malloc

尋找問題

嘗試解決

問題 - 3

尋找問題

嘗試解決

為 qtest 新增 shuffle 功能

新增命令

Signal

實作 shuffle 命令

為 qtest 新增 web 功能

實作 web 命令

tags: `linux2022`

為什麼 `element_t` 中包含了 `list_head`

`q_new`

`q_size`

`q_insert_head` 及 `q_insert_tail`

`q_remove_head` 和 `q_remove_tail`

`q_delete_mid`

`q_sort` 和 `mergesort`

簡化 `mergesort`

排序完再修復 `prev` 連結

使用 bitwise OR 替代 `ptmp->next = left ? left : right;` 以減少分支

`q_delete_dup`

修正並簡化 `q_delete_dup`

圖解 list_sort 的 `do while` 部份

`do while` 部份程式碼

`merge_final` 部份

`likely` 與 `unlikely` 巨集

問題 - 1 `atexit`

問題 - 2 `test_malloc`