---
# System prepended metadata

title: 2024q1 Homework1 (lab0)
tags: [linuxkernel2024]

---

# 2024q1 Homework1 (lab0)
contributed by < `Jimmy01240397` >

### Reviewed by `jujuegg`
- 不用張貼完整程式碼
- dudect 的部分可以把詳細實作列出，或者貼出 commit 的連結來參考
- 我認為可以適當的在程式碼中間加入一點空行，增加可讀性。
> 工程人員說話要明確，避免說「感覺」
> 與其談「心法」，不如設想「如果我是你」，我會怎麼做，示範一次給同學看，而且檢討自己哪裡沒做好，從而呼應原本學員的不足處。
> [軟體工程師要學會說故事](https://ruddyblog.wordpress.com/2016/06/18/)，本作業要求學員從良性詳盡的批評開始。繼續檢討！

## 開發環境
```shell
$ gcc --version
gcc (Debian 12.2.0-14) 12.2.0
Copyright (C) 2022 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

$ lscpu
Architecture:            x86_64
  CPU op-mode(s):        32-bit, 64-bit
  Address sizes:         40 bits physical, 48 bits virtual
  Byte Order:            Little Endian
CPU(s):                  1
  On-line CPU(s) list:   0
Vendor ID:               GenuineIntel
  Model name:            Common KVM processor
    CPU family:          15
    Model:               6
    Thread(s) per core:  1
    Core(s) per socket:  1
    Socket(s):           1
    Stepping:            1
    BogoMIPS:            5999.99
```

## 實驗圖表生成程式
`python labtest.py config.yml labtest.png`

```python
import sys
import matplotlib.pyplot as plt
import subprocess
import yaml
import importlib

with open(sys.argv[1], 'r') as f:
    config = yaml.load(f, Loader=yaml.FullLoader)

data = [[] for a in config['lab']]
size = list(range(int(config['size']['min']), int(config['size']['max']), int(config['size']['step'])))

for a in size:
    for idx, b in enumerate(config['lab']):
        testcase = importlib.import_module(f'testcase.{b["testcasegen"]}').init(a)
        time = subprocess.run(b['command'], input=testcase, stdout=subprocess.PIPE).stdout.decode()
        time = float(time.split('\n')[0])
        data[idx].append(time)

plt.xlabel('size', fontsize=20)
plt.ylabel('time', fontsize=20)

for idx, a in enumerate(data):
    plt.scatter(size, a, c=config['lab'][idx]['color'], alpha=0.5)

plt.savefig(sys.argv[2])
```

## 針對佇列操作的程式碼實作
### q_new
實作建立一個空的佇列，建立一個 `list_head` 用來連結佇列的第一個節點以及最後一個節點。

:::danger
避免過多的中英文混用，已有明確翻譯詞彙者，例如「鏈結串列」(linked list) 和「佇列」(queue)，就使用該中文詞彙，英文則留給變數名稱、人名，或者缺乏通用翻譯詞彙的場景。
> 已修
:::

```c
struct list_head *q_new()
{
    struct list_head *node = malloc(sizeof(struct list_head));
    if (!node)
        return NULL;
    INIT_LIST_HEAD(node);
    return node;
}
```

### q_free
實作佇列的釋放，當佇列被釋放，裡面的所有節點理應被釋放，如果佇列為空的 for 便不會執行，直接釋放佇列本身。
```c
void q_free(struct list_head *l)
{
    if (!l)
        return;
    struct list_head *node, *safe;
    list_for_each_safe (node, safe, l) {
        list_del(node);
        element_t *element = container_of(node, element_t, list);
        e_free(element);
    }
    free(l);
}
```

### q_insert_head 與 q_insert_tail
建立一個新節點並且加入到鏈結串列的頭部或尾部。
考慮到堆疊釋放的情況，因此要對字串做複製。

```diff
    if (!head || !s)
        return false;
    element_t *element = e_new(s);
    if (!element)
        return false;
-   list_add(&(element->list), head);
+   list_add_tail(&(element->list), head);
    return true;
```

考慮到兩者有高度相似，可運用巨集來代替減少重複程式。

```c
/* Base function for insert an element into queue */
#define q_insert_base(head, s, list_add_method) \
    if (!head || !s)                            \
        return false;                           \
    element_t *element = e_new(s);              \
    if (!element)                               \
        return false;                           \
    list_add_method(&(element->list), head);    \
    return true;

/* Insert an element at head of queue */
bool q_insert_head(struct list_head *head, char *s)
{
    q_insert_base(head, s, list_add);
}

/* Insert an element at tail of queue */
bool q_insert_tail(struct list_head *head, char *s)
{
    q_insert_base(head, s, list_add_tail);
}
```

### q_remove_head 與 q_remove_tail
從鏈結串列的頭部或尾部移除一個節點。

```diff
-   if (!head || head->next == head) return NULL;
-   element_t *element = container_of(head->next, element_t, list);
+   if (!head || head->prev == head) return NULL;
+   element_t *element = container_of(head->prev, element_t, list);
    list_del(&(element->list));
    strncpy(sp, element->value, bufsize - 1);
    sp[bufsize - 1] = '\0';
    return element;
```

同理，可以運用巨集來代替減少重複程式。

```c
#define q_remove_base(head, sp, bufsize, nextprev)                           \
    if (!head || head->nextprev == head)                                     \
        return NULL; /* When head->next or head->prev == head queue is empty \
                      */                                                     \
    element_t *element = container_of(head->nextprev, element_t, list);      \
    list_del(&(element->list));                                              \
    strncpy(sp, element->value, bufsize - 1);                                \
    sp[bufsize - 1] = '\0';                                                  \
    return element;

element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
    q_remove_base(head, sp, bufsize, next);
}

element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize)
{
    q_remove_base(head, sp, bufsize, prev);
}
```

實作時也產生一個疑問是為甚麼 `list_del` 的無效記憶體位址一定要是 0x00100100 與 0x00200200 而不是其他數字如：0x00100101、0x00200202、0x0 之類的。

:::warning
這問題很好，你可參見 Linux 核心原始程式的 git log 來解讀。
:::

### q_size
實作計算佇列的長度。
由於計算需要迭代計算，如果一次走兩步或許可以加快運行的速度。
> <s>所以真的有比較快嗎? 真心發問</s>
> 雖然迴圈次數減少一半，但是實際上指標還是前進了整個佇列，條件也相對變多，請問真的會比較快嗎?
> [name=jujuegg]

:::danger
不要書寫「真心發問」，詳盡提出你的疑慮和佐證，這樣才能有效溝通。

真誠地分享你的專業知識，讓溝通能夠達到共鳴，才是真正展現禮貌的方式。
:::

```c
int q_size(struct list_head *head)
{
    if (!head)
        return -1;
    int size = 0;
    struct list_head *node;
    for (node = head->next; node != head && node->next != head;
         node = node->next->next, size+=2) {
    }
    size += (node != head) & 1;
    return size;
}
```

#### 實驗
<s>測資產生器</s>

:::danger
「產生器」不是精準的詞彙，因為你應當有明確的測試計畫，並從數學分析 (或已有的論述) 證實該計畫可行，接著才用程式碼去產生對應的資料輸入。否則，你只是「憑感覺」做事，根本不能算是「工程」。
:::

```python
def init(size):
    return f"""new
ih RAND {size}
size
quit
""".encode()
```

設定檔
```yaml
size:
  min: 1000
  max: 100000
  step: 100

lab:
# 一步一步算
- command:
  - "./qtest-normal"
  - "-v"
  - "0"
  color: 'blue'
  testcasegen: 'size'
# 二步二步算
- command:
  - "./qtest"
  - "-v"
  - "0"
  color: 'red'
  testcasegen: 'size'
```

結果：
- min: 100 max: 1000 step: 1
![labtest1](https://hackmd.io/_uploads/S1UpO_kA6.png)
- min: 1000 max: 10000 step: 10
![labtest2](https://hackmd.io/_uploads/r15pOukAT.png)
- min: 1000 max: 100000 step: 100
![labtest3](https://hackmd.io/_uploads/rJCad_10T.png)

結論：在 size 高的情況兩步兩步算真的比較快一點點
:::danger
需要更多的解讀，從電腦科學的基礎學科的角度去陳述，避免說「真的比較快一點點」。
:::

### q_delete_mid
參考「[你所不知道的 C 語言: linked list 和非連續記憶體](https://hackmd.io/@sysprog/c-linked-list)」，使用快慢指標並且由於使用環狀鏈結串列因此終止判斷會以 `= head` 為標準。

```c 
for (fast = head->next, slow = head->next;
     fast != head && fast->next != head;
     fast = fast->next->next, slow = slow->next) {
}
list_del(slow);
element_t *element = container_of(slow, element_t, list);
e_free(element);
```

### `q_delete_dup`
由於 github action 上的 ubuntu 以及我自己的 debian 版本所使用的 glibc 版本皆低於 2.38，而 2.38 後的 strcmp 有做<s>優化</s>，在這之前的 strcmp 都是一個字元做比較，效能不佳。

:::danger
某些濫用「優化」的語境，根本與「改良」和「改善」無異，那為何不直接講「改良」和「改善」呢？

$\to$ [資訊科技詞彙翻譯](https://hackmd.io/@sysprog/it-vocabulary)
:::

- Debian 12.4
```
$ ldd --version
ldd (Debian GLIBC 2.36-9+deb12u4) 2.36
Copyright (C) 2022 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
Written by Roland McGrath and Ulrich Drepper.
```
- Ubuntu 22.04.3 LTS
```
$ ldd --version
ldd (Ubuntu GLIBC 2.35-0ubuntu3.6) 2.35
Copyright (C) 2022 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
Written by Roland McGrath and Ulrich Drepper.
```
- glibc 2.38 前的 strcmp 實作
```c
int
STRCMP (const char *p1, const char *p2)
{
  const unsigned char *s1 = (const unsigned char *) p1;
  const unsigned char *s2 = (const unsigned char *) p2;
  unsigned char c1, c2;

  do
    {
      c1 = (unsigned char) *s1++;
      c2 = (unsigned char) *s2++;
      if (c1 == '\0')
        return c1 - c2;
    }
  while (c1 == c2);

  return c1 - c2;
}
```

因此這邊將優化後的 strcmp 做移植，作為 newstrcmp。
```c
list_for_each_safe (node, safe, head) {
    element_t *element = container_of(node, element_t, list);
    if (!check || newstrcmp(check, element->value)) {
        check = element->value;
        continue;
    }
    list_del(node);
    e_free(element);
} 
```

### q_swap
for 迴圈同時使用兩個節點，一次移動兩步，當其中有一個為 head 時停止。
```c
void q_swap(struct list_head *head)
{
    struct list_head *nodea, *nodeb, *safea, *safeb, *tmp = NULL;
    for (nodea = head->next, nodeb = nodea->next,
         safea = nodea->next->next, safeb = nodeb->next->next;
         nodea != head && nodeb != head;
         nodea = safea, nodeb = safeb,
         safea = nodea->next->next, safeb = nodeb->next->next) {
        list_move(nodea, nodeb);
    }
}
```

### q_reverse
一個一個的把 head->prev 移到 head->next 後面。
```c
void q_reverse(struct list_head *head)
{
    if (!head)
        return;
    for (struct list_head *node = head, *move = head->prev; node != move;
         node = move, move = head->prev) {
        list_move(move, node);
    }
}
```

### q_reverseK
從頭迭代 k 次並把這個範圍的節點取出來另外存成一個鏈結串列以後做一次 `q_reverse` 再放回來原來的位置。
```c
for (first = head->next, last = first; first != head;
     first = lastnext, last = first) {
    for (int i = 0; i < k - 1 && last != head; i++, last = last->next) {
    }
    if (last == head)
        return;
    firstprev = first->prev;
    lastnext = last->next;
    lastnext->prev = firstprev;
    firstprev->next = lastnext;
    tmphead.next = first;
    first->prev = &tmphead;
    tmphead.prev = last;
    last->next = &tmphead;
    q_reverse(&tmphead);
    list_splice(&tmphead, firstprev);
}
```

### q_ascend 與 q_descend
從後面往前迭代，當出現大於/小於前一個節點時，便刪除該節點。
```c
for (node = head->prev, safe = node->prev; node != head;
     node = safe, safe = node->prev) {
    element = container_of(node, element_t, list);
    if (check && newstrcmp(check, element->value) op 0) {
        list_del(node);
        e_free(element);
        continue;
    }
    check = element->value;
    len++;
}
```

### q_sort
參考 [Linux 核心的鏈結串列排序](https://hackmd.io/@sysprog/linux2024-lab0/%2F%40sysprog%2Flinux2024-lab0-e) 並且閱讀 [lib/list_sort.c](https://github.com/torvalds/linux/blob/master/lib/list_sort.c)，這邊採用 Queue-Mergesort。

先寫一個巨集來處理合併兩個列表
```c
#define mergelist(nodea, nodeb, mergeadd, mergesplice, mergehead)              \
    {                                                                          \
        struct list_head *lastnode = nodeb, *safe, **pnode;                    \
        while (nodea && nodeb) {                                               \
            element_t *elementa = container_of(nodea, element_t, list),        \
                      *elementb = container_of(nodeb, element_t, list);        \
            bool cmpresult = ((!descend) * 2 - 1) *                            \
                                 newstrcmp(elementa->value, elementb->value) < \
                             0;                                                \
            pnode = cmpresult ? &nodea : &nodeb;                               \
            safe = (*pnode)->next;                                             \
            lastnode = cmpresult ? nodeb : nodea;                              \
            mergeadd(*pnode, mergehead);                                       \
            *pnode = safe;                                                     \
        }                                                                      \
        mergesplice(lastnode, mergehead);                                      \
    }
```

sort 總共有兩個階段，第一個階段是將 `list` 移到 `pending` 並且對部分節點做合併，第二階段是將所有 pending 做合併。

第一階段的每個迴圈先做 `count++` 接著判斷是否做合併最後將原本的 `pending` 放到 `list` 上並且 `list` 成為新 `pending` 然後切到下一個 `list`。當需要合併時，對 `count` 做 `ffs` 得到需要對哪兩個列表做合併，使用 `mergelist` 處理合併，最後更新 `*ppending`。

第二階段時先對 `head` 做初始化，並且使用 `mergelist` 對 `head` 與目前的 `pending` 做合併。

### q_merge
每兩個鏈結串列一組做合併，遇到長度為 0 就跳過，持續到只有一條鏈結串列有東西為止。
```c
do {
    count = 0;
    mergehead = NULL;
    list_for_each_safe (node, safe, head) {
        queue_contex_t *queue = container_of(node, queue_contex_t, chain);
        if (!queue->q || (!queue->size && queue->q != head->next)) {
            continue;
        }
        count++;
        if (mergehead) {
            mergehead->q->prev->next = NULL;
            queue->q->prev->next = NULL;
            struct list_head *nodea = mergehead->q->next,
                             *nodeb = queue->q->next;
            INIT_LIST_HEAD(mergehead->q);
            INIT_LIST_HEAD(queue->q);
            mergehead->size = 0;
            queue->size = 0;
            mergelist(nodea, nodeb, descend, queuemergeadd,
                      queuemergesplice, mergehead);
            queue = NULL;
            count--;
        }
        mergehead = queue;
    }
} while (count > 1);
```

:::danger
當你選定合併排序，現有的測試案例要如何涵蓋合併排序的最差狀況呢？
:::

## 研讀論文〈[Dude, is my code constant time?](https://eprint.iacr.org/2016/1123.pdf)〉並改進 lab0-c 的 dudect

與 [dudect](https://github.com/oreparaz/dudect) 原始程式搭配對照。
- dudect_main <-> doit
- prepare_inputs <-> prepare_inputs
- measure <-> measure
- update_statistics <-> update_statistics
- report <-> report

其中缺少 `percentile` 相關用來去除極端值的程式碼。將該功能寫入即可。

:::danger
指出論文和實作的出入之處，尚有其他！
:::

```diff
prepare_inputs(input_data, classes);
bool ret = measure(before_ticks, after_ticks, input_data, mode);
differentiate(exec_times, before_ticks, after_ticks);
+prepare_percentiles(exec_times);
update_statistics(exec_times, classes);
ret &= report();
```