---
# System prepended metadata

title: 2023q1 Homework1 (quiz1)
tags: [Linux Kernel]

---

---
tags: Linux Kernel
---

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

## 測驗 1
### 解釋程式碼運作原理
該程式碼使用 quick sort 來實作。
結構體如下：

```c
struct item {                         
    uint16_t i;
    struct list_head list;
};
```

因此可以判斷出 `AAA` 為 `item` ， `BBB` 為 `list` 。
首先，該程式碼使用串列的第一筆資料當作 `pivot` ：
```c
struct item *pivot = list_first_entry(head, AAA, BBB);
list_del(&pivot->list);
```
接著將值小於 `pivot` 值的資料放到 `list_less` ，並把大於 `pivot` 值的資料放到 `list_greater` 。

```c
struct item *itm = NULL, *is = NULL;
CCC (itm, is, head, list) {
    if (cmpint(&itm->i, &pivot->i) < 0)
        DDD (&itm->list, &list_less);
    else
        EEE (&itm->list, &list_greater);
}
```

因此從這裡我們便可以判斷出 `CCC` 為 `list_for_each_entry_safe` (因為資料會被移動，所以要使用有 safe 的版本)， `DDD` 和 `EEE` 都是 `list_move_tail` 。至於使用 `list_move_tail` 而不是使用 `list_move` 的原因參考[課堂問答簡記](https://hackmd.io/VIvUZemESvGUev4aCwOnWA?view)：
stable sort alg 指若有多個 elements 有相同的 key value，則 sort 前後其相對關係不變。
e.g
有一 list 5, 3, 3*, 4  
其中有兩個 elements 有相同的 key value 3 ，這裡用 3 以及 3* 作為區別。他們兩個的相對關係為 3 在 3* 前面  
則經過穩定排序後的結果必為：
3, 3*, 4, 5
若使用不穩定的 sort alg 排序，則結果可能為：
3*, 3, 4, 5
可以看到兩個 3 的相對關係發生改變了。
由於程式是取從開頭 pivot 後往後比較，所以用 list_move_tail 可以確保後面的 ele 被放在後面。
以剛剛提到的 list 5, 3, 3*, 4 為例，則若使用 list_move 的話程式執行會變為：
```
remained list: 3, 3*, 4
               ^
              item
pivot (5)
less_list: 3

---
remained list: 3*, 4
               ^
              item
pivot (5)
less_list: 3*, 3
---
remained list: 4
               ^
              item
pivot (5)
less_list: 4, 3*, 3
---
```
可以看到 3* 和 3 的相對位置改變了。

最後使用 divide-and-conquer 。
配合遞迴排序 `list_less` 和 `list_greater` ：

```c
list_sort(&list_less);
list_sort(&list_greater);
```

並將排序好的兩個串列連接。

```c
list_add(&pivot->list, head);
list_splice(&list_less, head);
FFF(&list_greater, head);
```

因此可以判斷這裡的 `FFF` 為 `list_splice_tail` 。
## 測驗 2
### 解釋程式碼運作原理
該程式碼使用迭代的方式實作 `quick_sort` 。
該程式碼使用 `stack` 來存取待排序的串列。

```c
struct list_head stack[MAX_DEPTH];
```

這裡的 `if` 代表，如果 `partition` 如果不是空或者只有一點，就把 `partition` 依照 `pivot` 分成 `list_less` 和 `list_greater` 。其中 `list_del(&itm->list)` 是多餘的，後面的 `list_move` 已經包含相同的效果。

同樣是使用第一筆資料當作 `pivot`

```c
struct item *pivot = list_first_entry(&partition, struct item, list);
```

同樣是再比較後將值小於 `pivot` 值的資料放到 `list_less` ，並把大於 `pivot` 值的資料放到 `list_greater` 。

```c
GGGG (itm, is, &partition, list) {
    list_del(&itm->list);
    if (cmpint(&itm->i, &pivot->i) < 0)
        list_move(&itm->list, &list_less);
    else
        list_move(&itm->list, &list_greater);
}
```

因此可以判斷這裡的 `GGGG` 為 `list_for_each_entry_safe` 。
最後再將 `pivot` 放到 `list_less` 的最後，並將兩個串列放到 `stack` 中：

```c
HHHH (&pivot->list, &list_less);
if (!list_empty(&list_greater))
    list_splice_tail(&list_greater, IIII);
if (!list_empty(&list_less))
    list_splice_tail(&list_less, JJJJ);
```

因此可以判斷 `HHHH` 為 `list_move_tail` ， `IIII` 和 `JJJJ` 都代表 `stack` 的頂端，因此為 `&stack[++top]` 。

另一方面

```c
else {
    while (top >= 0 && list_is_singular(&stack[top])) {
        struct item *tmp = list_first_entry(&stack[top], struct item, list);
        list_del(&tmp->list);
        INIT_LIST_HEAD(KKKK);
        list_add_tail(&tmp->list, head);
    }
}
```

代表如果 `stack` 的頂端只剩一筆資料，則向下合併，因此 `KKKK` 為 `&stack[top--]` 。
而這段程式碼，可以使用下面這段來代替：

```c
else {
    while (top >= 0 && list_is_singular(&stack[top])) {
        list_splice_tail_init(&stack[top--], head);
    }
}
```

## 測驗 3
### 解釋程式碼運作原理
該程式碼利用 XOR 運算來找出下 linked list 的下一個節點。
其中，核心的巨集如下：

```c
#define XOR_COMP(a, b) ((xor_node_t *) (LLLL))
```

其目的是以 `a` 和 `b` 進行 XOR 運算，因此 `LLLL` 為
`(uintptr_t)(a) ^ (uintptr_t)(b)`

另一個常用的函式如下：

```c
static inline xor_node_t *address_of(xor_node_t *n1, xor_node_t *n2)
{
    assert(n1 && n2);
    return XOR_COMP(n1, n2);
}
```

此函式的目的在於，再透過 `assert` 判斷 `n1` 和 `n2` 是否為 `NULL` 後再裡用 `XOR_COMP` 來獲得下一格地址。
XOR 運算可以透過前一個的地址以及這一格的 link 來獲得下一格的位址，因此當前位置的 link 可以透過前後兩個點的地址進行 xor 運算得到。

`xorlist_for_each`, `xorlist_for_each_prev`, `xorlist_for_each_from`, `xorlist_for_each_from_prev` 的功能大同小異，都是尋訪整個串列，因此這裡挑出 `xorlist_for_each` 說明。

```c
#define xorlist_for_each(node, rp, rn, list)                        \
    for (rp = &(list)->head, node = rp->cmp; node != &(list)->tail; \
         rn = address_of(rp, node->cmp), rp = node, node = rn)
```

這個巨集透過 `address_of(rp, node->cmp)` ， `rp` 和 `node->cmp` ，也就是前一格的位置和目前格子的 `link` 進行 XOR 運算得到下一格的位置。

接者是 `xorlist_add`
此函式的目標是將 `n` 加入到 `list` 中。
```c
int xorlist_add(xor_list_t *list, xor_node_t *n)
{
    xor_node_t *real_next;

    if (!n)
        return ENOMEM;

    xor_node_t *real_prev = &list->head;
    xor_node_t *node = real_prev->cmp;
    if (node == &list->tail)
        real_next = MMMM;
    else
        real_next = node;
    real_prev->cmp = n;
    n->cmp = XOR_COMP(real_prev, real_next);
    real_next->cmp = XOR_COMP(n, XOR_COMP(real_prev, PPPP));
    list->count++;

    return 0;
}
```

首先 `node` 儲存了 `real_prev->cmp` 也就是前一個節點的 `link` ，因此可以判斷出 `node` 會用在找出下一格位置的 XOR 運算中。
接著，判斷 `list` 是否為空的，如果是的話就將 `%list->tail` 指定給 `real_next`。
最後再計算和更新 `real_prev`, `real_next` ，先將 `real_prev->cmp` 設定為 `n` 代表插入新節點，並藉由 `n->cmp = XOR_COMP(real_prev, real_next)` 更新新節點的 `link` ，接著在更新 `real_next->cmp = XOR_COMP(n, XOR_COMP(real_prev, PPPP))` 就可以完成插入。因此這裡的 `PPPP` 為 `real_next->cmp` 。
值得注意的是，當 `list` 為空時 `head` 節點內的 `cmp` 就會是 `tail` 因此可以將程式碼改成：
```c
int xorlist_add(xor_list_t *list, xor_node_t *n)
{
    if (!n)
        return ENOMEM;

    xor_node_t *real_prev = &list->head;
    xor_node_t *real_next = real_prev->cmp;

    real_prev->cmp = n;
    n->cmp = XOR_COMP(real_prev, real_next);
    real_next->cmp = XOR_COMP(n, XOR_COMP(real_prev, real_next->cmp));
    list->count++;

    return 0;
}
```
這裡參考了 [yanjiew1](https://hackmd.io/@yanjiew/linux2023q1-quiz1#2023q1-Homework1-quiz1) 的筆記。

## References
[2023q1 第 1 週測驗題 - HackMD](https://hackmd.io/@sysprog/linux2023-quiz1)
[第 1, 2 週課堂問答簡記 - HackMD](https://hackmd.io/VIvUZemESvGUev4aCwOnWA?view)
[2023q1 Homework1 (quiz1) contributed by < yanjiew1 >](https://hackmd.io/@yanjiew/linux2023q1-quiz1#2023q1-Homework1-quiz1)