# 2022q1 Homework1 (lab0-c)
contributed by < `robertnthu` >
###### tags: `linux2022`

## 環境設置

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

$ uname -r
5.16.10-051610-generic

$ 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):                          4
On-line CPU(s) list:             0-3
Thread(s) per core:              2
Core(s) per socket:              2
Socket(s):                       1
NUMA node(s):                    1
Vendor ID:                       GenuineIntel
CPU family:                      6
Model:                           142
Model name:                      Intel(R) Core(TM) i5-7360U CPU @ 2.30GHz
Stepping:                        9
CPU MHz:                         2300.000
CPU max MHz:                     3600.0000
CPU min MHz:                     400.0000
BogoMIPS:                        4599.93
Virtualization:                  VT-x
L1d cache:                       64 KiB
L1i cache:                       64 KiB
L2 cache:                        512 KiB
L3 cache:                        4 MiB
NUMA node0 CPU(s):               0-3

## queue.c
### q_new()
Use `INIT_LIST_HEAD()` to init `struct list_head`

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

### q_free()
**Version1**

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

    element_t *tmp;
    while (!list_empty(l)) {
        tmp = list_first_entry(l, element_t, list);
        list_del(l->next);    
        q_release_element(tmp);
    }
    free(l);
}

Use `list_for_each_safe()` to do `q_free()`iteration.
**Version2**

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

   struct list_head *tmp1, *tmp2;
   list_for_each_safe (tmp1, tmp2, l) {
       list_del(tmp1);
       element_t *tmp = list_entry(tmp1, element_t, list);
       q_release_element(tmp);
   }
   free(l);
}

### q_insert_head()
* Why is `strcpy()` not safe?
* strcpy has no way of knowing how large the destination buffer is (i.e. there is no length parameter) so sloppy programming using it can lead to overrunning the buffer and corrupting other memory.
* What can we use as a replacement of `strcpy()`?
* `strdup()` :
* This function returns a pointer to a null-terminated byte string, which is a duplicate of the string pointed to by s. **The memory obtained is done dynamically using malloc and hence it can be freed using free().**
It returns a pointer to the duplicated string s.
-pasted from [GeeksforGeeks]
(https://www.geeksforgeeks.org/strdup-strdndup-functions-c/)
* `strncpy()` : It can guarentee the length of string is under control.

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

    // create a new element_t
    element_t *new_ele = malloc(sizeof(element_t));
    if (!new_ele)
        return false;

    // init element_t new_ele
    INIT_LIST_HEAD(&new_ele->list);

    size_t len = strlen(s);
    new_ele->value = malloc(sizeof(char) * (len + 1));

    // if allocation failed, free and return
    if (!new_ele->value) {  
        free(new_ele);
        return false;
    }
    strncpy(new_ele->value, s, len);
    new_ele->value[len] = '\0';

    list_add(&new_ele->list, head);
    return true;
}

### q_insert_tail()
Just amend `list_add()` to `list_add_tail()`

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

    // create a new element_t
    element_t *new_ele = malloc(sizeof(element_t));
    if (!new_ele)
        return false;

    // init element_t new_ele
    INIT_LIST_HEAD(&new_ele->list);

    size_t len = strlen(s);
    new_ele->value = malloc(sizeof(char) * (len + 1));
    // if allocation failed, free and return
    if (!new_ele->value) {
        free(new_ele);
        return false;
    }
    strncpy(new_ele->value, s, len);
    new_ele->value[len] = '\0';

    list_add_tail(&new_ele->list, head);
    return true;
}

### q_remove_head()
* Use `list_entry()` to get value and then `strncpy()`

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

    if (!sp && bufsize) {
        strncpy(sp, list_entry(head->next, element_t, list)->value, bufsize - 1);
        sp[bufsize - 1] = '\0';
    }
    list_del(head->next);

    return NULL;
}

trace-01-ops will not pass with check of `sp`. After amending `if (!sp && bufsize)` to `if (bufsize)`, trace-01-ops passed.
:::danger
Why?
>Either the condition '!sp' is redundant or there is possible null pointer dereference: sp. [nullPointerRedundantCheck]

**Update**
By reference of [jasperlin1996's note](https://hackmd.io/@jasperlin1996/linux2022-lab0?fbclid=IwAR2YZsHC-i9MQeCaQTqFeS6IZB489MAqc6rgW76HF0_gUtPsVjCwPwtupEI#q_remove_head), i found this bug can be fixed by `if (sp != NULL && bufsize)`, which fulfill the requirement better than skip checking `sp`.

:::

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

    element_t *node = list_first_entry(head, element_t, list);
    list_del(&node->list);

    if (sp != NULL && bufsize) {
        strncpy(sp, node->value, bufsize - 1);
        sp[bufsize - 1] = '\0';
    }
    
    return node;
}

### q_remove_tail()
Similar to `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 *node = list_entry(head->prev, element_t, list);
    list_del(&node->list);

    if (sp != NULL && bufsize) {
        strncpy(sp, node->value, bufsize - 1);
        sp[bufsize - 1] = '\0';
    }

    return node;
}

### q_size()
Same as [professor's code](https://hackmd.io/@sysprog/linux2022-lab0#-%E5%8F%96%E5%BE%97%E7%A8%8B%E5%BC%8F%E7%A2%BC%E4%B8%A6%E9%80%B2%E8%A1%8C%E9%96%8B%E7%99%BC)

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

    int len = 0;
    struct list_head *li;

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

### q_delete_mid()
* Reference : [你所不知道的 C 語言: linked list 和非連續記憶體](https://hackmd.io/@sysprog/c-linked-list#%E6%A1%88%E4%BE%8B%E6%8E%A2%E8%A8%8E-Leetcode-2095-Delete-the-Middle-Node-of-a-Linked-List)
* Use "fast and slow pointer technique".

:::info
With doubly linked list, we don't need indirect pointer to iterate. Pointer with `list_del()` is enough.
:::

bool q_delete_mid(struct list_head *head)
{
    // https://leetcode.com/problems/delete-the-middle-node-of-a-linked-list/
    // check if head == NULL or queue is empty
    if (!head || list_empty(head))
        return false;

    // Use fast and slow pointer technique
    // pointer of pointer is to prevent using another pointer to record the
    // previous node
    struct list_head *mid = head->next;
    for (struct list_head *fast = head->next;
         fast != head && fast->next != head; fast = fast->next->next) {
        mid = mid->next;
    }
    //"indir" is the middle list_node, we want to delete this element_t
    list_del(mid);
    q_release_element(list_entry(mid, element_t, list));

    return true;
}

### q_delete_dup()
* If we encounter duplicates, store the value and iterate the list to delete the nodes with same value.
* For convenience, i declared the function `val()`, which returns the value of a given node.

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

    struct list_head *node = head->next;
    // iterate node and check whether there are duplicates
    // if val(node) == val(node->next), there are duplicates
    // and we have to check whether node->next exists
    while (node != head) {
        if (node->next != head && strcmp(val(node), val(node->next)) == 0) {
            // there are duplicates, iterate to delete the node
            char *tar_val = strdup(val(node));  // copy the target value
            while (node != head && strcmp(val(node), tar_val) == 0) {
                struct list_head *del = node;
                node = node->next;
                // delete del
                list_del(del);
                q_release_element(list_entry(del, element_t, list));
            }
            free(tar_val);
        } else {
            node = node->next;
        }
    }

    return true;
}

char *val(struct list_head *l)
{
    return (list_entry(l, element_t, list))->value;
}

### q_swap()
* Iterate the list and swap the value.

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;

    // Dealing with element_t or list_head is complicated
    // So i decide to swap the value in element_t
    // Use tar to iterate the list
    struct list_head *tar = head->next;
    while (tar != head && tar->next != head) {
        char *val1 = val(tar);
        // Swap
        list_entry(tar, element_t, list)->value =
            list_entry(tar->next, element_t, list)->value;
        list_entry(tar->next, element_t, list)->value = val1;
        // then move tar to next pair
        tar = tar->next->next;
    }
    return;
}

**Version 2**
* 利用 `list_del` 跟 `list_add` 來交換兩個 list_head 的位置

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;

    // Dealing with element_t or list_head is complicated
    // So i decide to swap the value in element_t
    // Use tar to iterate the list
    for (struct list_head *tar = head->next; tar != head && tar->next != head;
         tar = tar->next) {
        list_del(tar);
        list_add(tar, tar->next);
    }
    return;
}

### q_reverse()
* Use `list_move()` to reorder the queue.
* I reorder the linked list by move the last element to the front of previous `tail` and iterate the list.

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

    // use list_move
    struct list_head *tail = head;
    while (tail->next != head) {
        list_move(head->prev, tail);
        tail = tail->next;
    }
    return;
}

:::info
I've tried to use

list_for_each (tail, head)
    list_move(head->prev, tail);

But it would be in a infinite loop when `tail == head->prev`, i think solving this is more complicated than the above version.
:::

### q_sort()
**Merge sort**
* Reference : [你所不知道的 C 語言: linked list 和非連續記憶體](https://hackmd.io/@sysprog/c-linked-list#Merge-Sort-%E7%9A%84%E5%AF%A6%E4%BD%9C)
1. Use `list_del()` to remove the `head`, since `head` is not `element_t`. Then use `merge_sort()` to sort the list.
2. `merge_sort()`
1. Split the list from the middle.
* I defined two function to split the list, `find_mid()` and `cut_list()`.
* `find_mid()` use "fast and slow pointer" to get the mid of a linked list
* `cut_list()` is to cut the linked list, returning the pointer that points the next half list.
2. Call `merge_sort()` recurrently.
3. Call `mergeTwoLists()` to merge two lists.
* referenced from [你所不知道的 C 語言: linked list 和非連續記憶體](https://hackmd.io/@sysprog/c-linked-list#Merge-Sort-%E7%9A%84%E5%AF%A6%E4%BD%9C)
3. At the end, `q_sort()` add `head` node back and recover the `prev` pointer.

void q_sort(struct list_head *head)
{
    if (!head || list_empty(head) || list_is_singular(head))
        return;
    // For convenience, i delete head at first
    struct list_head *tmp_head = head->next;
    list_del_init(head);
    // cut_list to cancel the linked list cycle
    tmp_head = cut_list(tmp_head->prev);
    // then sort 'tmp_head'.
    tmp_head = merge_sort(tmp_head);

    // we need to recover the prev link
    // Add prev link back
    struct list_head *tmp;
    for (tmp = tmp_head; tmp->next != NULL; tmp = tmp->next) {
        tmp->next->prev = tmp;
    }
    // recover the cycle list structure and add 'head' back
    head->next = tmp_head;
    tmp_head->prev = head;
    // tmp is the last node, so just set the link with head
    tmp->next = head;
    head->prev = tmp;
}

struct list_head *merge_sort(struct list_head *head)
{
    if (!head || head->next == NULL)  // when head has only one node
        return head;
    // split
    struct list_head *left, *right, *mid;
    mid = find_mid(head);
    left = head;
    // cut_list cut the given list_head and its next list_head
    // and return the next list_head
    right = cut_list(mid);

    // Then merge_sort both left and right
    left = merge_sort(left);
    right = merge_sort(right);

    // Merge two sorted list
    return mergeTwoLists(left, right);
}

struct list_head *find_mid(struct list_head *head)
{
    // Use fast and slow pointer technique
    struct list_head *fast, *slow;
    for (fast = head, slow = head;
         fast->next != NULL && fast->next->next != NULL;
         fast = fast->next->next) {
        slow = slow->next;
    }
    return slow;
}

struct list_head *cut_list(struct list_head *head)
{
    struct list_head *next = head->next;
    head->next = NULL;
    next->prev = NULL;
    return next;
}

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

    for (node = NULL; L1 && L2; *node = (*node)->next) {
        // node is the pointer of the pointer 'next'
        // if node = &L1, it means that *node = L1
        // then *node = (*node)->next is equal to L1 = L1->next
        // so node always keep the pointer of pointer 'next'
        // node = (val(L1) < val(L2)) ? &L1 : &L2;
        node = (strcmp(val(L1), val(L2)) < 0) ? &L1 : &L2;
        *ptr = *node;
        // ptr is to concate the list at the end
        // *ptr = (*ptr)->next
        ptr = &(*ptr)->next;  // move prt to its next node
    }
    // *ptr = L1 or L2, concate the list
    *ptr = (struct list_head *) ((uintptr_t) L1 | (uintptr_t) L2);
    // Why return head. At the beginning, we set **ptr = *head,
    // so *ptr = head. In the first iteration, we make *ptr = *node,
    // where *node = L1 or L2, this equal to head = L1 or L2. Then we move
    // ptr = &(*ptr)->next, in other words, head was set in the first iteration.
    return head;
}

* `uintptr_t`
* [Branchless Programming in C++ - Fedor Pikus - CppCon 2021](https://www.youtube.com/watch?v=g-WPhYREFjk)
* [2020q1 第 3 週測驗題](https://hackmd.io/@sysprog/linux2020-quiz3?fbclid=IwAR1f6VLpTCdzgszZHuHR9TYVgdw4Ip2099yqg4iUzJiaWcfC1oGW4hMwm9A)
[XOR linked list](https://en.wikipedia.org/wiki/XOR_linked_list) 用單一指標的空間，實作出雙向的鏈結串列，其中的關鍵操作是 XOR(a, b) ==> ((list *) ((uintptr_t) (a) ^ (uintptr_t) (b)))
* The following type designates an unsigned integer type with the property that any valid pointer to void can be converted to this type, then converted back to a pointer to void, and the result will compare equal to the original pointer: uintptr_t

### Compare with lib/list_sort.c
[lib/list_sort.c](https://github.com/torvalds/linux/blob/master/lib/list_sort.c)
**筆記**
1. `merge()`
* By using infinite loop `for (;;)`, we needs conditional statement to judge when to get out of the loop.
* `__attribute__`
- In GNU C and C++, you can use function attributes to specify certain function properties that may help the compiler optimize calls or check code more carefully for correctness.
—from [Declaring Attributes of Functions](https://gcc.gnu.org/onlinedocs/gcc/Function-Attributes.html#Function-Attributes)
* This function attribute specifies function parameters that are not supposed to be null pointers. This enables the compiler to generate a warning on encountering such a parameter.
* `__attribute__((nonnull[(arg-index, ...)]))`
* Where `[(arg-index,...)]` denotes an optional argument index list.
* If no argument index list is specified, all pointer arguments are marked as nonnull.
--[www.keil.com](https://www.keil.com/support/man/docs/armcc/armcc_chr1359124976631.htm)
2. `merge_final()`
- Merge with restoration of standard doubly-linked list structure.
- `unlikely()` :
- 在Linux kernel 2.6之後提供了likely, unlikely 這兩個macro，他們被定義在/include/linux/compiler.h中

        # define likely(x)	__builtin_expect(!!(x), 1)            
        # define unlikely(x)	__builtin_expect(!!(x), 0)

* `__built_expect()`
是 gcc 的內建 function，用來將 branch 的相關資訊提供給 compiler，告訴 compiler 設計者期望的比較結果，以便對程式碼改變分支順序來進行優化。
* `!!(x)`
* 透過兩次 NOT op 來確保值一定是0 或 1
* 因為 if 內邏輯敘述的值可以是0或是非0的整數的，所以如果不做`!!(x)`就無法確保值一定是0或1
* [[Linux Kernel慢慢學]ARRAY_SIZE macro in linux kernel](https://meetonfriday.com/posts/58e72281/) 這篇文章中有討論到這個用法，`BUILD_BUG_ON_ZERO`在拿到`__same_type()` 的回傳值時，利用兩個`Not`確保回傳值一定是1或0，再乘上-1並回傳。
* 使用`likely` macro 表示這段敘述(x)為 true 的機率比較大(比較常發生)，告訴 compiler 將 x==ture 的對應執行程式碼接在判斷後面
* 使用`unlikely` macro 表示這段敘述 (x) 為 true 的機率比較小(不常發生)，告訴 compiler 將 x==false 的對應執行程式碼接在判斷後面
—from [[Linux Kernel慢慢學]likely and unlikely macro](https://meetonfriday.com/posts/cecba4ef/)
3. `list_sort()`
* [作者 George Spelvin 的 commit message](https://github.com/torvalds/linux/commit/b5c56e0cdd62979dd538e5363b06be5bdf735a09?branch=b5c56e0cdd62979dd538e5363b06be5bdf735a09&diff=split) 裡面有非常多的訊息
* merge sort 過程中的比較數值次數是以下算式$$n*log2(n) - K*n + O(1)$$
其中我們能改善的是 K 係數
* Top-down merge sort 理論上 K 係數最大，也就是比較總次數最小，因為都是在正中間把 list 分開，但是因為 L1 cache 有限，過程中沒辦法把整個 list 都 load 到記憶體，每一次遞迴都需要頻繁的把資料載入 cache ，實際上的效能並不理想。
* 所以在 bottom up 使用 depth-first order，越長的 list 優先 merge ，這樣就能較有效的利用 cache
* 但這樣又會產生另一個影響效能的現象，George Spelvin 舉例，如果 entries 數量比二的次方再多一點，那 depth-first order 的 merge 過程中，如果兩個串列太不平衡，比較次數也會比較多，例如要合併長度分別為1024及4的 list，平均而言要跑遍4/5個長度為1024的 list。
>原文：
>The simple eager merge pattern causes bad performance when n is just
over a power of 2. If n=1028, the final merge is between 1024- and
4-element lists, which is wasteful of comparisons. (This is actually
worse on average than n=1025, because a 1204:1 merge will, on average,
end after 512 compares, while 1024:4 will walk 4/5 of the list.)
* 最後 George Spelvin 透過 bottom up 但過程中控制 list 的長度最長跟最短在2:1，獲得了跟 top down merge sort 相近的比較次數，且對 cache 的使用也比較友善。
* [kdnvt 的開發紀錄](https://hackmd.io/@5ux520T8Sd-OoYfdxZR55Q/SyzDKJ9y9#%E7%A0%94%E8%AE%80-liblist_sortc) 有詳細的表格展示了實作的概念，仔細的列出了每一個步驟發生前與發生後的變化，比起本來的 commit massage 更加好懂
* 只有碰到一樣長度的 list 時，才會做 merge，而在這樣的 bottom up merge 過程，每個 list 的長度都會是 2 的次方（因為一開始是1，1跟1合併之後變成長度2的 list，而我們只合併一樣長度的 list，所以下次長度2的 list 合併之後會變成長度4的 list。）
* 確切來說，並不是看到一樣長度的 list 都做 merge，例如第八個元素加進去前，此時 count = 111，pending list 是 1-2-4（代表有長度為1, 2, 4的 list），但因為`if (likely(bits))`這個條件判斷的關係，在這個 while 並不會 merge 任何 list。
* 在第九個元素加進去前，count = 1000，pending list 是1-1-2-4。因為在找 least-significant clear bit 時，會檢查到 count(1000) 第一個 bit 的0而跳出 loop，接下來`if (likely(bits))`檢查出後面還有東西，就會 merge 最近的兩個 pending list，也就是1-1-2-4變成2-2-4，然後才加入第九個元素，pending list 變成 1-2-2-4
* 而這樣做最差的情況，就是最後把所有 pending list 都 merge 起來時，各個 list 的長度分別為 1, 2, 4, 8,..., 2^k^，就是上述的長度最長跟最短被控制在2:1，也就不會出現本來 bottom up merge sort 可能會出現的不平衡現象

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

		/* Find the least-significant clear bit in count */
		for (bits = count; bits & 1; bits >>= 1)
			tail = &(*tail)->prev;
		/* Do the indicated merge */
		if (likely(bits)) {
			struct list_head *a = *tail, *b = a->prev;

			a = merge(priv, cmp, b, a);
			/* Install the merged result in place of the inputs */
			a->prev = b->prev;
			*tail = a;
		}

		/* Move one element from input list to pending */
		list->prev = pending;
		pending = list;
		list = list->next;
		pending->next = NULL;
		count++;
	} while (list);

* `bits >>= 1`是把 bits 做 right shift，用來檢查 count 這個數在二進位表示是否有出現連續的 1，如果碰到0就會跳出迴圈，例如 count = 10111，用來表示此時的 pending list 長度分別是 1, 2, 4, 16，那到第四個 iteration，就會跳出來
* 而 `tail = &(*tail)->prev` 是把 `tail` 指標移到下一個 pending list，因為所有的 list 在這裡都被改成了單向串列，只有 `next`才是指向下一個元素，而`prev`就被用來指到下一個順位的 list

        // 程式片段
        list = pending; // Take one list from pending
        pending = pending->prev;
        for (;;) { // Merge other lists
            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 list 後，再對整個 pending list 做 merge
* 作者保留了 pending list 的最後一條 list ，先把前面的 pending list 都 merge 起來，最後再使用 `merge_final` 來 merge，並且恢復雙向鏈結

**加入實做**
參考[eric88525的開發紀錄](https://hackmd.io/@eric88525/linux2022-lab0#%E5%BC%95%E5%85%A5-liblist_sortc)
* 除了 [eric88525](https://hackmd.io/@eric88525/linux2022-lab0#%E5%BC%95%E5%85%A5-liblist_sortc)提到的操作外 :
* 刪除`EXPORT_SYMBOL(list_sort);`
* 這行是為了讓`list_sort()`能夠被所有 linux kernel 的模塊使用，所以此處可以去掉
* 在`list_sort.c`定義`u8`：`typedef uint8_t u8;`
* 本來是用 include header file 來解決 `error: unknown type name ‘u8’
`，但都沒能解決，最後直接在 `list_sort.c`裡面宣告了

**測試**

cmd> new
l = []
cmd> ih RAND 7
l = [dkxny lxluzcl pfogyfzzz rubmfeyjm prbuhvvfn ivjbjefs gcotbyqd]
cmd> sort
l = [dkxny gcotbyqd ivjbjefs lxluzcl pfogyfzzz prbuhvvfn rubmfeyjm]
cmd> shuffle
l = [lxluzcl pfogyfzzz ivjbjefs dkxny rubmfeyjm gcotbyqd prbuhvvfn]
cmd> sort linux
l = [dkxny gcotbyqd ivjbjefs lxluzcl pfogyfzzz prbuhvvfn rubmfeyjm]

**比較**
(未完成，我想使用 perf ，但 kernel 5.16.11好像並沒有 perf 的 package)

### shuffle()

參考：[你所不知道的 C 語言: linked list 和非連續記憶體](https://hackmd.io/@sysprog/c-prog/%2Fs%2FSkE33UTHf#Modern-method)
* 因為老師文章的實作與此專案的資料結構有些許不同（第一個 list_head `head` 是沒有資料的），所以針對這點做了修改
* 使用 `list.h` 之後，除了可以不使用 pointer of pointer 外，也能縮短程式

void q_shuffle(struct list_head *head) {
    srand(time(NULL));

    // First, we have to know how long is the linked list
    int len = q_size(head);

    // Append shuffling result to another linked list
    struct list_head  *new = NULL, *indirect;

    while (len) {
        int random = rand() % len;
        indirect = head->next;

        while (random--)
            indirect = indirect->next;
        list_del_init(indirect);

        if (new) {
            list_add_tail(indirect, new);
        } else
            new = indirect;

        len--;
    }

    list_add_tail(head, new);
}

**加入專案**
參考：[qtest 命令直譯器的實作](https://hackmd.io/@sysprog/linux2022-lab0#qtest-%E5%91%BD%E4%BB%A4%E7%9B%B4%E8%AD%AF%E5%99%A8%E7%9A%84%E5%AF%A6%E4%BD%9C)
1. 程式呼叫流程：
>main → run_console → cmd_select → interpret_cmd → parse_args

* `console.h`裡面的定義

    /* Organized as linked list in alphabetical order */
    typedef struct CELE cmd_ele, *cmd_ptr;
    struct CELE {
        char *name;
        cmd_function operation;
        char *documentation;
        cmd_ptr next;
    };

* 本來要使用 `CELE`這個結構都要打`struct CELE`，但加上`typedef struct CELE cmd_ele, *cmd_ptr` 之後，只要用`cmd_ele`就能呼叫了
* `qtest.c` 有 `console_init()`，`console.c`有`init_cmd()`

* `console.h` 裡面多定義了

    /* Add a new command */
    void add_cmd(char *name, cmd_function operation, char *documentation);
    #define ADD_COMMAND(cmd, msg) add_cmd(#cmd, do_##cmd, msg)

所以我們只需要在`qtest.c`寫一個`do_shuffle()`，並在裡面呼叫`q_shuffle()`，並在`console_init()`加入

    ADD_COMMAND(shuffle, " shffle the whole list");

**do_shuffle()**
參考 [qtest-命令直譯器的實作](https://hackmd.io/@sysprog/linux2022-lab0#qtest-%E5%91%BD%E4%BB%A4%E7%9B%B4%E8%AD%AF%E5%99%A8%E7%9A%84%E5%AF%A6%E4%BD%9C)

>* 首次呼叫`do_XXX` 函式時，`exception_setup` 的功能是建立 `sigjmp_buf`，並回傳 `true`。
>* 回到稍早提及的 `if (exception_setup(true))`敘述中，若是第一次回傳，那麼會開始測試函式。若測試函式的過程中，發生任何錯誤 (亦即觸發 `SIGSEGV`或 `SIGALRM` 一類的 signal)，就會立刻跳回 signal handler。signal handler 會印出錯誤訊息，並進行 `siglongjmp`。
>* 由 `exception_setup`的程式可以知道又是跳到 `exception_setup(true)`裡面，但這時會回傳 `false`，因而跳過測試函式，直接結束測試並回傳 `ok`內含值。
>* 換言之，`exception_cancel()`後就算再發生 `SIGALRM`或 `SIGSEGV`，也不會再有機會回到 `exception_setup()`裡面。

* 首次呼叫是怎麼發生的？
* `report()` 的參數有什麼功能？
* `error_check()`跟`exception_cancel()`有什麼功能？`
* `return ok && !error_check();`又是做什麼的？
確認程式執行過程沒有出錯

// do_shuffle
static bool do_shuffle(int argc, char *argv[]) 
{
	if (argc != 1) {
        report(1, "%s takes no arguments", argv[0]);
        return false;
    }
	if (!l_meta.l)
        report(3, "Warning: Calling  on null queue");
    error_check();

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

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

最後測試程式，確認 `shuffle()`功能正常。

cmd> new
l = []
cmd> ih RAND 4
l = [mjpay xrcehkw qoiuyyn sprmhzmnh]
cmd> sort
l = [mjpay qoiuyyn sprmhzmnh xrcehkw]
cmd> shuffle
l = [qoiuyyn xrcehkw sprmhzmnh mjpay]
cmd> sort
l = [mjpay qoiuyyn sprmhzmnh xrcehkw]

## 未完成
### web

### Address Sanitizer

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

### 解釋 select 系統呼叫在本程式的使用方式，並分析 console.c 的實作

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

### 指出現有程式的缺陷 (提示: 和 RIO 套件 有關) 或者可改進之處 (例如更全面地使用 Linux 核心風格的鏈結串列 API)，嘗試實作並提交 pull request