---
tags: Linux Kernel
---

# 2023q1 Homework1 (lab0)
contributed by < [`chun61205`](https://github.com/chun61205) >

## 開發環境

$ 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):                  8
  On-line CPU(s) list:   0-7
Vendor ID:               GenuineIntel
  Model name:            Intel(R) Core(TM) i5-1035G1 CPU @ 1.00GHz
    CPU family:          6
    Model:               126
    Thread(s) per core:  2
    Core(s) per socket:  4
    Socket(s):           1
    Stepping:            5
    CPU max MHz:         3600.0000
    CPU min MHz:         400.0000
    BogoMIPS:            2380.80

## 資料結構
### `element_t`
:::info
圖待補
:::
### `queue_contex_t`
:::info
圖待補
:::
## 開發過程
:::success
詳閱作業書寫規範。
:notes: jserv

已解決
:::
### `q_size`

/* Create an empty queue */
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;
}

走訪所有節點，已找到佇列的 `size` 。

### `q_new`

/* Create an empty queue */
struct list_head *q_new()
{
    struct list_head *head = malloc(sizeof(struct list_head));
    if (head == NULL)
        return NULL;
    INIT_LIST_HEAD(head);
    return head;
}

利用 `INIT_LIST_HEAD` 來建立一個空的佇列。

### `q_free`

/* Free all storage used by queue */
void q_free(struct list_head *l)
{
    if (!l || list_empty(l)) {
        free(l);
        return;
    }
    element_t *entry, *safe;
    list_for_each_entry_safe (entry, safe, l, list) {
        q_release_element(entry);
    }
    free(l);
    return;
}

利用 `list_for_each_entry_safe` 走訪所有 `entry` ，再藉由 `q_release_element` 釋放記憶體。

### `q_insert_head` 和 `q_insert_tail`

:::danger
避免只列出程式碼，你的想法和遇到的各式開發問題，更為關鍵，HackMD 適合討論，而非張貼大量程式碼。
:notes: jserv
:::

/* Insert an element at head of queue */
bool q_insert_head(struct list_head *head, char *s)
{
    if (!head)
        return false;
    element_t *tmp = malloc(sizeof(element_t));
    if (!tmp)
        return false;
    size_t s_len = strlen(s);
    tmp->value = malloc(s_len + 1);
    if (!(tmp->value)) {
        free(tmp);
        return false;
    }
    strncpy(tmp->value, s, s_len);
    tmp->value[s_len] = '\0';
    list_add(&(tmp->list), head);
    return true;
}

/* Insert an element at tail of queue */
bool q_insert_tail(struct list_head *head, char *s)
{
    if (!head)
        return false;
    element_t *tmp = malloc(sizeof(element_t));
    if (!tmp)
        return false;
    size_t s_len = strlen(s);
    tmp->value = malloc(s_len + 1);
    if (!(tmp->value)) {
        free(tmp);
        return false;
    }
    strncpy(tmp->value, s, s_len);
    tmp->value[s_len] = '\0';
    list_add_tail(&(tmp->list), head);
    return true;
}

生成要插入的 `entry` 後，分別藉由 `list_add` 和 `list_add_tail` 來插入 `entry` 。
:::info
實測後發現無法滿足時間複雜度 $O(1)$ 的要求，推測原因為 strncpy，預計在研究 [dudect](https://github.com/oreparaz/dudect) 工具和論文 [Dude, is my code constant time?](https://eprint.iacr.org/2016/1123.pdf) 後改善。
:::
### `q_remove_head` 和 `q_remove_tail`

/* Remove an element from head of queue */
element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
    if (!head || list_empty(head))
        return NULL;
    element_t *target = list_first_entry(head, element_t, list);
    list_del(head->next);
    if (sp) {
        strncpy(sp, target->value, bufsize - 1);
        sp[bufsize - 1] = '\0';
    }
    return target;
}

/* Remove an element from tail of queue */
element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize)
{
    if (!head || list_empty(head))
        return NULL;
    element_t *target = list_last_entry(head, element_t, list);
    list_del(head->prev);
    if (sp) {
        strncpy(sp, target->value, bufsize - 1);
        sp[bufsize - 1] = '\0';
    }
    return target;
}

兩個函式分別藉由 `list_first_entry` 和 `list_last_entry` 取得要移除的 `entry` 再藉由 `list_del` 將目標移除掉。
因為 `list_del` 會將目標前後的 `entry` 連接，因此不需要額外進行調整。

此外，這兩個函式的回傳值為 `target->value` 的值。
:::info
實測後發現無法滿足時間複雜度 $O(1)$ 的要求，推測原因為 strncpy，預計在研究 [dudect](https://github.com/oreparaz/dudect) 工具和論文 [Dude, is my code constant time?](https://eprint.iacr.org/2016/1123.pdf) 後改善。
:::

### `q_delete_mid`

/* Delete the middle node in queue */
bool q_delete_mid(struct list_head *head)
{
    if (!head || list_empty(head))
        return false;
    struct list_head *left = head->prev, *right = head->next;
    while (!(left == right) && !(right->prev == left)) {
        right = right->next;
        left = left->prev;
    }
    list_del(right);
    q_release_element(list_entry(right, element_t, list));
    return true;
}

我的想法是使用左右指標，分別從左邊和右邊開始尋訪整個佇列。
如此一來，我們便需要分作兩種情況討論：
1. 節點數為單數，則代表左右指標相同時，它們所指向的便是中間的節點。
2. 節點數為複數，則代表右指標會超過一格，因此中間的節點會出現在 `right->prev == left`

### `q_delete_dup`
我的想法為
只要使用兩個連續的指標， `curr_node` 和 `next_node` ，並尋訪整個佇列，便能夠直接透過比較的方式來查看相鄰兩個節點是否有相同的值。

if(strcmp((list_entry(curr_node, element_t, list))->value, (list_entry(next_node, element_t, list))->value)

然而，這樣做會衍生出一個問題，就是當出現相同值得節點，並刪除其中一個的時候，下一步會無法確定是否要移除 `curr_node` 。因此我的作法為，先透過一個變數紀錄上一個節點是否需要移除。

if(strcmp((list_entry(curr_node, element_t, list))->value, (list_entry(next_node, element_t, list))->value)){ //curr and next elements don't have the same value.
    if(last_cmp){
        list_del(curr_node);
        q_release_element(list_entry(curr_node, element_t, list));
    }
    last_cmp = 0; 
} else{ //curr and next elements have the same value;
    last_cmp = 1;
    list_del(curr_node);
    q_release_element(list_entry(curr_node, element_t, list));
}

### `q_swap`
:::warning
> :warning: 不要急著說「完成」，工程是持續反省和改進的過程，目前只是 `qtest` 搭配自動評分沒有遇到 regression，不代表「完成」。再改進！
> :notes: jserv
:::

/* Swap every two adjacent nodes */
void q_swap(struct list_head *head)
{
    if (!head || list_empty(head))
        return;
    struct list_head *curr_node;
    list_for_each (curr_node, head) {
        if (curr_node->next == head)
            break;
        list_move(curr_node, curr_node->next);
    }
    return;
}

我的思路為，透過 `curr_node` 和 `curr_node->next` 表示要交換的兩個節點
，接著尋訪所有節點，再利用 `list_move` 將 `curr_node` 搬移到 `curr_node->next` 前面，以實現兩個節點交換。
其實最一開始的想法是透過 `curr_node` 和 `next_node` 的操作來實現 `q_swap` ，不過在看到 [komark06](https://hackmd.io/@komark06/SyCUIEYpj#q_reverse-%E5%AF%A6%E4%BD%9C) 的 `q_reverse` 後，我又回去重看了 `list_move` ，發現 `list_move` 不只有在移動到 `head` 時可以使用，中途的節點也可以使用，因此才有了現在的版本。

### `q_reverse`

/* Reverse elements in queue */
void q_reverse(struct list_head *head) 
{
    if (!head || list_empty(head))
        return;
    struct list_head *node = NULL, *safe = NULL;
    list_for_each_safe (node, safe, head)
        list_move(node, head);
    return;
}

這裡受到 [komark06](https://hackmd.io/@komark06/SyCUIEYpj#q_reverse-%E5%AF%A6%E4%BD%9C) 的啟發，只要走訪所有節點，再將節點移動到佇列開頭，整個佇列就會被反轉。

### `q_reverseK`

void q_reverseK(struct list_head *head, int k)
{
    if (!head || list_empty(head) || k <= 1)
        return;
    struct list_head *node = head->next;
    while (1) {
        struct list_head *tmp = node, *curr_head = node->prev;
        for (int i = 0; i < k; i++, node = node->next) 
            if (node == head)
                return;
        node = tmp;
        tmp = node->next;
        for (int i = 0; i < k; i++, node = tmp, tmp = tmp->next)
            list_move(node, curr_head);
    }
}

我的想法為，將每 $k$ 個節點分為一組，在確認接下來的節點不會有 `head` 後，再一個一個用 `list_move` 來將排列順序倒轉。

### `q_sort` 和 `lib/list_sort.c` 研讀
#### `q_sort` 初步開發

我使用 merge sort 實作，實作分兩個部份，負責合併兩個佇列的 `q_merge_two` ，和負責分割佇列的 `q_sort` ：

list_for_each_safe(node, safe, head){
    INIT_LIST_HEAD(node);
    stack[i] = node;
    i++;
}
INIT_LIST_HEAD(head);
for(i = 1; i < queue_size; i *= 2){
    for(int j = 0; i + j < queue_size; j += (i * 2)){
        stack[j] = merge_two_list(stack[j], stack[i + 1]);
    }
}
list_add_tail(head, stack[0]);

:::danger
不用列舉完整程式碼，HackMD 是讓你描述想法和過程中遇到的問題的地方，你應該只列出關鍵程式碼片段，並在之前就探討你的構思和對應的考量。
:notes: jserv
:::

這裡的 `q_merge_two` 的輸入參數不需要輸入 `head` 也就是沒有內存資料的部份。
另外，對於 `q_sort` 我的想法是，先透過尋訪整的佇列，並將所有節點堆疊在 `stack` 裡面，如此一來，只要在最後將所有節點兩兩合併，便可以得到結果。
#### `lib/list_sort.c` 研讀
此外，我研讀了 [lib/list_sort.c](https://github.com/torvalds/linux/blob/master/lib/list_sort.c) 以及 [kdnvt](https://hackmd.io/@sysprog/linux2022-sample-lab0) 的整理。
1. `list_sort.c` 在 `merge` 和 `merge_final` 將串列當成單向鏈結串列，並無視 prev 指標的操作，最後再在 `merge_final` 時再串起來。
2. 在合併的過程中 `list_sort.c` 確保合併的兩個子串列的大小不會大於
$2:1$，如此一來便可以降低比較的次數，以增加 performance ：

/*
 * The number of pending lists of size 2^k is determined by the
 * state of bit k of "count" plus two extra pieces of information:
 *
 * - The state of bit k-1 (when k == 0, consider bit -1 always set), and
 * - Whether the higher-order bits are zero or non-zero (i.e.
 *   is count >= 2^(k+1)).
 *
 * There are six states we distinguish.  "x" represents some arbitrary
 * bits, and "y" represents some arbitrary non-zero bits:
 * 0:  00x: 0 pending of size 2^k;           x pending of sizes < 2^k
 * 1:  01x: 0 pending of size 2^k; 2^(k-1) + x pending of sizes < 2^k
 * 2: x10x: 0 pending of size 2^k; 2^k     + x pending of sizes < 2^k
 * 3: x11x: 1 pending of size 2^k; 2^(k-1) + x pending of sizes < 2^k
 * 4: y00x: 1 pending of size 2^k; 2^k     + x pending of sizes < 2^k
 * 5: y01x: 2 pending of size 2^k; 2^(k-1) + x pending of sizes < 2^k
 * (merge and loop back to state 2)
 */

|count decimal|count binary|merge|before merge|after merge
| -------- | -------- | -------- |---|---|
0|0000 |No| NULL| X
1|0001 |No| 1 |X
2|0010 |Yes| 1-1 |2
3|0011 |No| 1-2 |X
4|0100 |Yes| 1-1-2 |2-2
5|0101 |Yes| 1-2-2 |1-4
6|0110 |Yes| 1-1-4 |2-4
7|0111 |No| 1-2-4 |X
8|1000 |Yes| 1-1-2-4 |2-2-4
9|1001 |Yes| 1-2-2-4 |1-4-4
10|1010 |Yes | 1-1-4-4| 2-4-4
11|1011 |Yes | 1-2-4-4| 1-2-8
12|1100 |Yes| 1-1-2-8| 2-2-8
13|1101 |Yes | 1-2-2-8 |1-4-8
14|1110|Yes | 1-1-4-8 |2-4-8
15|1111 |No | 1-2-4-8 |X
16|10000 |Yes| 1-1-2-4-8| 2-2-4-8

#### 回頭檢查 `q_sort`
研讀完 `lib/list_sort.c` 後，我發現原本的程式碼有以下幾點做的不夠好
1. `int queue_size = q_size(head);`
我原本的程式碼使用 `q_size` 來獲得佇列的長度，以此來走訪所有節點，然而，這個做法式建立在「需要利用尋訪整個佇列，並把所有節點兩兩合併」的情況下才需要用到。若是參考 `lib/list_sort.c` 的做法，便不須要這樣做。
2. `stack`
在原本的程式碼中，我使用 `stack[STACKCAPACITY]` 來儲存佇列中所有節點，然而，這樣做會有 `stack` 的記憶體空間浪費或是不足的問題，因此這裡也改成 `lib/list_sort.c` 的 `pending` 的方法。

在考慮到這些因素後，我發現難以已 `lib/list_sort.c` 的作法來修改我的程式碼，並且我發現能夠使用 `lib/list_sort.c` 的想法來實做 `q_merge` 因此我打算先使用 `lib/list_sort.c` 的程式碼，並轉頭修改 `q_merge` 。
### `q_descend`
我的想法為，利用 `curr_node` 和 `prev_node` 來尋訪整個佇列，如此一來便能夠直接透過比較來判斷是否移除。另外，這個函式必須使用相反的順序來尋訪，以確保迭代的過程中會不會遇到嚴格大於的節點。

/* Remove every node which has a node with a strictly greater value anywhere to
 * the right side of it */

while (prev_node != head) {
    if (strcmp(list_entry(curr_node, element_t, list)->value, list_entry(prev_node, element_t, list)->value) < 0) {
        list_del(prev_node);
        q_release_element(list_entry(prev_node, element_t, list));
    } 
    curr_node = prev_node;
    prev_node = prev_node->prev;
}

不過，在實際測試後發現這個函式會有兩個問題：
1. 在刪除節點後 `curr_node` 應該保持不動。
2. 在 `prev_node` 被刪除後，便無法存取到 `prev_node->prev` 因此應該事先記錄下來

while (prev_node != head) {
    if (strcmp(container_of(prev_node, element_t, list)->value, container_of(curr_node, element_t, list)->value) < 0) {
        tmp = prev_node->prev;
        list_del(prev_node);
        q_release_element(container_of(prev_node, element_t, list));
        prev_node = tmp;
    } else {
        curr_node = prev_node;
        prev_node = prev_node->prev;
    }
}

### q_merge
:::info
待補圖
待測試
待優化
:::

/* Merge all the queues into one sorted queue, which is in ascending order */
int q_merge(struct list_head *head)
{
    if (!head || list_empty(head))
        return 0;
    queue_contex_t *first_queue  = container_of(head->next, queue_contex_t, chain);
    if (list_is_singular(head))
        return first_queue->size;
    for (struct list_head *node = head->next->next; node != head; node = node->next) {
        queue_contex_t *target = container_of(node, queue_contex_t, chain);
        merge_two_queue(first_queue->q, target->q);
        if(first_queue->size + target->size < first_queue->size)
            return -1;
        first_queue->size += target->size;
        target->size = 0;
    }
    return first_queue->size;
}

這題參考了 [komark06](https://hackmd.io/@komark06/SyCUIEYpj#q_merge-%E5%AF%A6%E4%BD%9C) 的做法，並做出優化。
我在每次尋訪到新的佇列時就進行 `merge_two_list` 並更新 `first_queue->size` 而不是在最後才 `q_sort` 。
但是， `q_merge` 可以使用 divide-and-conquer 方法進行優化。
首先，透過走訪整個佇列，並將目前的節點和下一個節點合併

if(queue != head && queue->next != head){
    struct list_head *a_queue = queue, *b_queue = a_queue->next;
    queue_contex_t *a_queue_container= container_of(a_queue, queue_contex_t, chain), *b_queue_container = container_of(b_queue, queue_contex_t, chain);
    if(!a_queue_container->size){
        list_del(a_queue);
    }
    if(!b_queue_container->size){
        list_del(b_queue);
    }
    if(a_queue_container->size && b_queue_container->size){
        if(a_queue_container->q->prev){
            a_queue_container->q->prev->next = NULL;
            a_queue_container->q->prev = NULL;
        }
        if(b_queue_container->q->prev){
            b_queue_container->q->prev->next = NULL;
            b_queue_container->q->prev = NULL;
        }
        a_queue_container->q->next = merge_two_queue(a_queue_container->q->next, b_queue_container->q->next);
        a_queue_container->size += b_queue_container->size;
        b_queue_container->size = 0;
        list_del(b_queue);
    }
}

結束迴圈的時間點就在只剩下一個佇列時。
不過，在我寫完這個函式後才發現，題目的要求是不能把 `queue_contex_t` 的節點移除掉的。因此須要再調整。

## References
[sysprog21/lab0-c: C Programming Lab - GitHub](https://github.com/sysprog21/lab0-c)
[2023q1 Homework1 (lab0) contributed by < komark06 >](https://hackmd.io/@komark06/SyCUIEYpj#2023q1-Homework1-lab0)
[linux/list_sort.c at master · torvalds/linux - GitHub](https://github.com/torvalds/linux/blob/master/lib/list_sort.c)
[2023q1 Homework1 (lab0) contributed by < kdnvt >](https://hackmd.io/@sysprog/linux2022-sample-lab0)