---
# System prepended metadata

title: 2024q1 Homework1 (lab0)

---

# 2024q1 Homework1 (lab0)
contributed by < [youjiaw](https://github.com/youjiaw/lab0-c) >

:::danger
留意各式細節，唯有重視小處並步步為營，方可挑戰原始程式碼規模超越三千七百萬行的 Linux 核心。
> 好的
:::

### Reviewed by `yu-hsiennn`
```diff
    // Add remaining elements
-   if (!list_empty(head1))
-       list_splice_tail_init(head1, &merged);
-   if (!list_empty(head2))
-       list_splice_tail_init(head2, &merged);
+   (!list_empty(head1)) ? list_splice_tail_init(head1, &merged) : list_splice_tail_init(head2, &merged);
```
改寫程式碼 ( q_sort )，使其更為精簡。

:::warning
感謝提醒，已修改。
:::

## 開發環境
```shell
$ gcc --version
gcc (Ubuntu 11.4.0-1ubuntu1~22.04) 11.4.0

$ lscpu
Architecture:            x86_64
  CPU op-mode(s):        32-bit, 64-bit
  Address sizes:         46 bits physical, 48 bits virtual
  Byte Order:            Little Endian
CPU(s):                  20
  On-line CPU(s) list:   0-19
Vendor ID:               GenuineIntel
  Model name:            Intel(R) Core(TM) i9-10900X CPU @ 3.70GHz
    CPU family:          6
    Model:               85
    Thread(s) per core:  2
    Core(s) per socket:  10
    Socket(s):           1
    Stepping:            7
    CPU max MHz:         4700.0000
    CPU min MHz:         1200.0000
    BogoMIPS:            7399.70
Virtualization features: 
  Virtualization:        VT-x
Caches (sum of all):     
  L1d:                   320 KiB (10 instances)
  L1i:                   320 KiB (10 instances)
  L2:                    10 MiB (10 instances)
  L3:                    19.3 MiB (1 instance)
NUMA:                    
  NUMA node(s):          1
  NUMA node0 CPU(s):     0-19
```

## 指定的佇列操作
<s>實做 queue</s>

:::danger
對照 Dictionary.com 對 [implement](https://www.dictionary.com/browse/implement) 一詞的解釋:
* to fulfill; perform; carry out:
* to put into effect according to or by means of a definite plan or procedure.
* Computers. to realize or instantiate (an element in a program), often under certain conditions as specified by the software involved.
* to fill out or supplement

「實作」會是符合上述 "implement" 語意的譯詞，取「起」以「創作」的意思，而「製造」本質上是固定輸入並通常產生固定輸出的行為。
$\to$ [資訊科技詞彙翻譯](https://hackmd.io/@sysprog/it-vocabulary)
:::

### `q_new`
配置記憶體，並用 `INIT_LIST_HEAD` 初始化。

### `q_free`
一開始實作時，沒有確認 `head` 是否有成功配置到記憶體，在 `make test` 的 "Test of malloc failure on new" 會出現錯誤。
```diff
void q_free(struct list_head *head)
{
+   if (!head)
+       return;
    element_t *entry, *safe;
    list_for_each_entry_safe (entry, safe, head, list)
        q_release_element(entry);
    free(head);
}
```

### `q_insert_head`, `q_insert_tail`
原本未檢查記憶體配置情況，在 `make test` 的 "Test of malloc failure on insert_head, insert_tail" 出現錯誤。

```diff
    element_t *new = malloc(sizeof(element_t));
    if (!new)
        return false;
    new->value = strdup(s);
+   if (!new->value) {
+       free(new);
+       return false;
+   }
```

### `q_remove_head`, `q_remove_tail`
使用 API 的 `list_entry` 取得開頭的 `element` ，將值複製到 `sp` 並從佇列移除。
```c
element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
    if (!head || list_empty(head))
        return NULL;
    struct list_head *node = head->next;
    element_t *element = list_entry(node, element_t, list);
    if (sp) {
        strncpy(sp, element->value, bufsize - 1);
        sp[bufsize - 1] = '\0';
    }
    list_del(node);
    return element;
}
```
`q_remove_tail` 的做法相同，但改取尾端的 `element`。
```diff
-   struct list_head *node = head->next;
+   struct list_head *node = head->prev;
```

### `q_size`
使用[教材](https://hackmd.io/@sysprog/linux2024-lab0-a#%E7%89%9B%E5%88%80%E5%B0%8F%E8%A9%A6)提供的做法。


:::danger
列出程式碼的目的是討論和檢討，倘若你沒有如此的舉措，就不用列出。
> 好的，已修正。
:::

### `q_delete_mid`
:::danger
避免非必要的項目縮排 (即 `* ` 和 `- `)，以清晰、明確，且流暢的漢語書寫。
> 好的，謝謝老師提醒。
:::

我原本的做法如下，除了沒有考慮到 `q_size` 逐一走訪每個節點的成本，使用 indirect pointer 來實作此函式的優缺點也需討論。
```c
int mid_node = q_size(head) / 2;
struct list_head **indir = &head;
for (int i = 0; i <= mid_node; i++)
    indir = &((*indir)->next);
    
element_t *element = list_entry(*indir, element_t, list);
list_del(*indir);
q_release_element(element);
```

在參考 [chun61205](https://hackmd.io/H2fpkPChSkuRw88H4bt_XQ?view#q_delete_mid) 以及 [yanjiew1](https://hackmd.io/@komark06/SyCUIEYpj#q_delete_mid-%E5%AF%A6%E4%BD%9C) 的建議後，決定使用兩個指標，從頭尾往中間找，以此減少記憶體的存取次數。
> commit [85a19ba](https://github.com/youjiaw/lab0-c/commit/85a19babc45540b0532aa275ceadf1b746fe0f2c)

```c
struct list_head *left = head->next, *right = head->prev;
while (!(left == right) && !(right->next == left)) {
    left = left->next;
    right = right->prev;
}
list_del(left);
q_release_element(list_entry(left, element_t, list));
```

### `q_delete_dup`
:::danger
避免非必要的項目縮排 (即 `* ` 和 `- `)，以清晰、明確，且流暢的漢語書寫。
:::

由於是傳入已排序的佇列，因此，只需檢查相鄰節點的值是否相同。
使用 `list_for_each_entry_safe` 逐一走訪每個節點，若 `current` 與 `next` 的值相同，就刪除 `current`，而 `flag` 的作用為刪除最後一個重複的節點。
```c
bool q_delete_dup(struct list_head *head)
{
    if (!head || list_empty(head))
        return false;

    element_t *current, *next;
    bool flag = false;
    list_for_each_entry_safe (current, next, head, list) {
        if (current->list.next == head)
            break;

        if (strcmp(current->value, next->value) == 0) {
            list_del(&current->list);
            q_release_element(current);
            flag = true;
        } else if (flag) {
            list_del(&current->list);
            q_release_element(current);
            flag = false;
        }
    }
    return true;
}
```

目前發現 `make test` 有時後會出現以下錯誤：
ERROR: Duplicate strings are in queue or distinct strings are not in queue
在經過 `./qtest` 測試不同測資後，發現如果最後一個節點有重複的話，會直接被跳過，因此加入檢查程式碼。
> commit [bb834f2](https://github.com/youjiaw/lab0-c/commit/bb834f2fb39f86fd469119c091e7ec9c925ae037)

```diff
-   if (current->list.next == head)
+   if (current->list.next == head) {
+       if (flag) {
+           list_del(&current->list);
+           q_release_element(current);
+       }
        break;
+   }
```

### `q_swap`
:::danger
避免非必要的項目縮排 (即 `* ` 和 `- `)，以清晰、明確，且流暢的漢語書寫。
:::

使用 `list_for_each` 逐一走訪每個節點。
使用 `list_move` 將 `next` 移到 `prev` 後方，等同於將 `current` 與  `next` 交換位置。
```c
struct list_head *current;
list_for_each (current, head) {
    if (current->next == head)
        break;

    list_move(current->next, current->prev);
}
```

### `q_reverse`
用指標 `first` 指向開頭節點，並不斷將 `next` 移動至 `head` 後方。
```c
struct list_head *first = head->next;
while (first->next != head)
    list_move(first->next, head);
```

### `q_reverseK`
參考 [koty6069](https://hackmd.io/UJQfmB61SkuVMoKR7dcYVA?view#q_reverseK) 的做法，以每 k 個節點為一組執行 `q_reverse`。
```c
struct list_head *current, *safe, *ptr = head;
int cnt = 0;
list_for_each_safe (current, safe, head) {
    if (++cnt == k) {
        LIST_HEAD(tmp);
        list_cut_position(&tmp, ptr->next, current);
        q_reverse(&tmp);
        list_splice(&tmp, ptr);
        ptr = safe->prev;
        cnt = 0;
    }
}
```

### `q_sort`
分為 `q_sort` 及 `list_merge`。
1. `q_sort`
* 使用快慢指標及 `list_cut_position` 將佇列對半切。
* 不斷遞迴，直到所有節點被分割成單一節點，再進行 `list_merge`。
```c
    struct list_head *fast = head->next, *slow = head;
    while (fast != head && fast->next != head) {
        slow = slow->next;
        fast = fast->next->next;
    }

    struct list_head second_half;
    list_cut_position(&second_half, head, slow);
    q_sort(head, descend);
    q_sort(&second_half, descend);
    list_merge(head, &second_half, descend);
```
2.  `list_merge`
* 比較兩個佇列的開頭節點值，依照結果和排序方式將指定節點移動到 `merged` （用來存放排序過的節點）。
* 當其中一個佇列空了，就將另一個移動到 `merged` 尾端。
```c
static void list_merge(struct list_head *head1,
                       struct list_head *head2,
                       bool descend)
{
    struct list_head merged;
    INIT_LIST_HEAD(&merged);

    while (!list_empty(head1) && !list_empty(head2)) {
        int compare_result =
            strcmp(list_entry(head1->next, element_t, list)->value,
                   list_entry(head2->next, element_t, list)->value);

        if ((descend && compare_result > 0) ||
            (!descend && compare_result < 0)) {
            struct list_head *tmp = head1->next;
            list_move_tail(tmp, &merged);
        } else {
            struct list_head *tmp = head2->next;
            list_move_tail(tmp, &merged);
        }
    }

    // Add remaining elements
    if (!list_empty(head1))
        list_splice_tail_init(head1, &merged);
    if (!list_empty(head2))
        list_splice_tail_init(head2, &merged);

    INIT_LIST_HEAD(head1);
    list_splice(&merged, head1);
}
```

:::danger
你如何確認目前的測試程式已涵蓋排序演算法的最差狀況？
:::

### `q_ascend`
由尾端向 `head` 走訪，並比較當前與前一個節點的 `value`：
1. 若 `prev` 大於 `current`，就刪除 `prev`。
```graphviz
digraph q_ascend {
    rankdir=LR
    node [shape=circle, fontsize=12];
    3 [fillcolor="#f9a7a7", style=filled]
    Head [shape=box, fontsize=12]
    Head -> 5 -> 2 -> 13 -> 3 -> 8 [arrowhead=normal, arrowtail=normal ,dir=both];

    current [fontsize=15, shape=plain, fontcolor=red]
    current -> 8 [style=dashed, color=red];

    { rank=same; current;8 };
}
```
2. 其餘情況，則 `current` 指向 `prev`。
```graphviz
digraph q_ascend {
    rankdir=LR;
    node [shape=circle, fontsize=12];
    Head [shape=box, fontsize=12]
    Head -> 5 -> 2 -> 13 -> 8[arrowhead=normal, arrowtail=normal ,dir=both];
    
    current [fontsize=15, shape=plain, fontcolor=red]
    current -> 13 [color=red];
    {rank=same; current;13};
}
```

```c
struct list_head *current = head->prev;
while (current->prev != head) {
    struct list_head *prev = current->prev;
    if (strcmp(list_entry(current, element_t, list)->value,
                  list_entry(prev, element_t, list)->value) <= 0) {
        list_del_init(prev);
        q_release_element(list_entry(prev, element_t, list));
    } else
        current = current->prev;
}
```

<!-- ![1](https://hackmd.io/_uploads/HkNcWGfap.png) -->

### `q_descend`
想法與 `q_ascend` 相同，但將條件改為：若 `prev` 小於 `current`，就刪除 `prev`。
```diff
-   if (strcmp(list_entry(current, element_t, list)->value,
-                 list_entry(prev, element_t, list)->value) <= 0) {
+   if (strcmp(list_entry(current, element_t, list)->value,
+                 list_entry(prev, element_t, list)->value) >= 0) {
        list_del_init(prev);
        q_release_element(list_entry(prev, element_t, list));
    } 
```

由下圖可發現，若由尾端向左邊走訪，只需紀錄最大值，並將小於當前最大值的節點移除即可。

### `q_merge`
目前作法是將所有佇列接起來，再執行 `q_sort`。
```c
    if (list_is_singular(head))
            return q_size(head);

    queue_contex_t *cur = NULL,
                   *qhead = list_first_entry(head, queue_contex_t, chain);
    list_del_init(&qhead->chain);

    list_for_each_entry (cur, head, chain) {
        list_splice_init(cur->q, qhead->q);
        qhead->size += cur->size;
    }

    list_add(&qhead->chain, head);
    q_sort(qhead->q, descend);

    // https://leetcode.com/problems/merge-k-sorted-lists/
    return qhead->size;
```

:::danger
改進你的漢語表達。
:::

## 分析記憶體問題
執行 `make valgrind` 以及開啟 `Address Sanitizer` 後，都沒有偵測到記憶體錯誤。

## 在 qtest 提供新的命令 shuffle

### `make` 時產生 eror

:::danger
directory 的翻譯是「目錄」，而非「資料夾」(folder)
> 好的，已修正。
:::

我在寫完 shuffle 函式後，做了以下幾個步驟：
1. 在 `scripts` <s>資料夾</s> 目錄中新增一個 python 檔，內容為教材提供的[測試程式](https://hackmd.io/@sysprog/linux2024-lab0-d#%E6%B8%AC%E8%A9%A6%E7%A8%8B%E5%BC%8F)。
2. 在終端機確認是否有安裝 python。
3. 執行 `make`。

接著就出現數行錯誤訊息，以下節錄其中兩行做紀錄
```shell
/usr/bin/ld: /home/webber/linux2024/lab0-c/qtest.c:884: undefined reference to `__asan_report_load8'
/usr/bin/ld: /home/webber/linux2024/lab0-c/qtest.c:887: undefined reference to `__asan_report_load8'
```

:::danger
這與 Address Sanitizer 有關，查閱 GCC 手冊。
> 好，謝謝老師提醒。
:::

就我的觀察，所有的 `.c` 檔均有產生此錯誤，內容格式為
```shell
/usr/bin/ld: [路徑名稱]: undefined reference to `xxx`
```

嘗試解決：
首先，刪除測試的 Python 檔案和 shuffle 函式，確保在 Visual Studio Code 的版本控制中，沒有任何更改過的項目（版本與成功執行 make valgrind 時一致）。但仍有相同的錯誤訊息。

在老師提醒這與 Address Sanitizer 有關後，我嘗試執行 `make clean` 及 `make SANITIZER=0` 來關閉它，隨後便可順利執行 `make test`。

### 統計方法驗證 shuffle
函式按照 Fisher–Yates shuffle 演算法來實作，以下為測試 [1, 2, 3, 4] 做 shuffle 1,000,000 次的直方圖。
![Figure_1](https://hackmd.io/_uploads/HJ_Lp2U06.png)

## 論文〈Dude, is my code constant time?〉
### 閱讀論文
Dudect 使用 leakage detection tests 在目標平台上進行統計分析，以決定該程式是否能在常數時間內完成，此方法解決了相關研究中，需要對硬體進行建模的困難。

我的疑惑是，為什麼兩種輸入資料的執行時間分佈相同時，就代表此演算法可以在常數時間內完成？

在查閱了 leakage detection 的論文後得知，在兩種輸入資料下，如果演算法的執行時間分佈在統計上沒有顯著差異，則代表演算法的性能不受輸入資料分佈的影響，即時間複雜度為常數時間。

### 解釋本程式的 "simulation" 模式
由 [trace-17-complexity.cmd](https://github.com/sysprog21/lab0-c/blob/d43e0723a034586e2200cfae0263657304ffcd02/traces/trace-17-complexity.cmd#L2) 可得知，在測試 it, ih, rh 及 rt 是否為常數時間時，會開啟 simulation 模式，讓 `qtest.c` 的 [queue_insert()](https://github.com/sysprog21/lab0-c/blob/d43e0723a034586e2200cfae0263657304ffcd02/qtest.c#L184) 與 [queue_remove()](https://github.com/sysprog21/lab0-c/blob/d43e0723a034586e2200cfae0263657304ffcd02/qtest.c#L291C13-L291C25) 函式可以使用 `dudect` 目錄中的 [test_const()](https://github.com/sysprog21/lab0-c/blob/d43e0723a034586e2200cfae0263657304ffcd02/dudect/fixture.c#L154C13-L154C23) 進行測試。

`test_const()` 會依照預先設定的測試次數，持續呼叫 `doit()` 來獲得測試結果，此函式可分為三個部分，分別對應到 `dudect` 中的 `dudect_init()`, `dudect_main()` 及`dudect_free()`。

### 處理 percentile
```c
if (first_time) {
    // throw away the first batch of measurements.
    // this helps warming things up.
    prepare_percentiles(ctx);
} else {
    update_statistics(ctx);
    ret = report(ctx);
}
```
在 `dudect_main()` 裡，會捨棄部份的第一批測量結果，根據論文所述，大於閾值 p 的測量值會被捨棄，目的是要讓結果與測量值的分佈盡可能的相符，我目前還不是很理解此意思。

若不是第一次測試，會呼叫 `update_statistics()`，可以發現在 `dudect` 中的函式會捨棄前 10 次的結果，而 `lab0-c` 則是沒有捨棄。
```c
// dudect
for (size_t i = 10 /* discard the first few measurements */; i < (ctx->config->number_measurements-1); i++) {

// lab0-c
for (size_t i = 0; i < N_MEASURES; i++) {
```

因此，我們要改進的部份如下：
* 將處理 percentile 的函式加入 lab0-c。
* 更改 update_statistics() 的迴圈走訪範圍。

做完上述的改進後（commit [cb0eb09](https://github.com/youjiaw/lab0-c/commit/cb0eb09fb67c93b7465a81a499c8da252f086a48)），`make test` 的 `trace-17-complexity` 就可以順利通過了。

## 嘗試引入 lib/list_sort.c 引入到 lab0-c 專案