# 2021q1 Homework2 (quiz2)
contributed by < `D4nnyLee` >

> [題目連結](https://hackmd.io/@sysprog/linux2021-quiz2)

:::warning
不需要多事加上 `[toc]`，HackMD 的瀏覽模式就內建 TOC，謹記 KISS 原則。
:notes: jserv
:::

## 測驗 `1`

### 解釋程式碼運作原理

先視覺化和 doubly linked list 有關的 API 的效果。

#### `list_add_tail()`

* Before

    graph {
        node [shape = box, label = ""]
        head [shape = none, label = "head"]
        pnode [shape = none, label = "node"]
        prev [shape = none, label = "prev"]
        
        many [shape = none, label = "..."]
        nnode [label = ""]

        pnode -- nnode [dir = forward]
        head -- n0 [dir = forward]
        prev -- n2 [dir = forward]
        {
            rank = same
            n0 -- n1 -- many -- n2 -- n0
        }
    }

* After

    graph {
        node [shape = box, label = ""]
        head [shape = none, label = "head"]
        pnode [shape = none, label = "node"]
        prev [shape = none, label = "prev"]
        
        many [shape = none, label = "..."]
        nnode [label = ""]

        pnode -- nnode [dir = forward]
        head -- n0 [dir = forward]
        prev -- n2 [dir = forward]
        {
            rank = same
            n0 -- n1 -- many -- n2 -- nnode -- n0
        }
    }

#### `list_del()`

* Before

    graph {
        subgraph ptr {
            node [shape = none]
            p_prev [label = "prev"]
            p_next [label = "next"]
            p_node [label = "node"]
        }
        subgraph obj {
            node [shape = box, label = ""]
            o_1 o_2 o_prev o_next o_node
            o_many1, o_many2 [shape = none, label = "..."]
        }
        
        p_prev -- o_prev [dir = forward]
        p_next -- o_next [dir = forward]
        p_node -- o_node [dir = forward]
        
        {
            rank = same
            o_1 -- o_many1 -- o_prev -- o_node -- o_next -- o_many2 -- o_2
            o_2 -- o_1 [constraint = false]
        }
    }

* After

    graph {
        subgraph ptr {
            node [shape = none]
            p_prev [label = "prev"]
            p_next [label = "next"]
            p_node [label = "node"]
        }
        subgraph obj {
            node [shape = box, label = ""]
            o_1 o_2 o_prev o_next o_node
            o_many1, o_many2 [shape = none, label = "..."]
        }
        
        p_prev -- o_prev [dir = forward]
        p_next -- o_next [dir = forward]
        p_node -- o_node [dir = forward]
        
        o_node -- o_prev [dir = forward]
        o_node -- o_next [dir = forward]
        {
            rank = same
            o_1 -- o_many1 -- o_prev -- o_next -- o_many2 -- o_2
            o_2 -- o_1 [constraint = false]
        }
    }

#### `list_splice_tail()`

* Before

    graph {
        subgraph ptr {
            node [shape = none]
            list list_first list_last
            head head_last
        }
        subgraph obj {
            node [shape = box, label = ""]
            o_list
            o_list_first, o_list_last [style = filled, color = blue]
            o_head o_head_last
            o_many_list, o_many_head [shape = none, label = "..."]
        }
        
        list -- o_list [dir = forward]
        list_first -- o_list_first [dir = forward]
        list_last -- o_list_last [dir = forward]
        head -- o_head [dir = forward]
        head_last -- o_head_last [dir = forward]
        {
            rank = same
            o_list -- o_list_first -- o_many_list -- o_list_last -- o_list
            o_head -- o_many_head -- o_head_last -- o_head
        }
    }

* After

    graph {
        subgraph ptr {
            node [shape = none]
            list list_first list_last
            head head_last
        }
        subgraph obj {
            node [shape = box, label = ""]
            o_list
            o_list_first, o_list_last [style = filled, color = blue]
            o_head o_head_last
            o_many_list, o_many_head [shape = none, label = "..."]
        }
        
        list -- o_list [dir = forward]
        list_first -- o_list_first [dir = forward]
        list_last -- o_list_last:ne [dir = forward]
        head -- o_head [dir = forward]
        head_last -- o_head_last [dir = forward]
        {
            rank = same
            o_head -- o_many_head -- o_head_last -- o_list_first -- o_many_list -- o_list_last
            o_list_last -- o_head [constraint = false]
        }
        
        o_list -- o_list_first [dir = forward]
        o_list -- o_list_last:n [dir = forward]
    }

#### `list_cut_position()`

* Before

    graph {
        subgraph ptr {
            node [shape = none]
            p_head_from [label = "head_from"]
            p_head_to [label = "head_to"]
            p_node [label = "node"]
            p_head_from_first [label = "head_from_first"]
        }
        subgraph obj {
            node [shape = box, label = ""]
            o_many_cut, o_many_remain [shape = none, label = "..."]
            o_first, o_node [style = filled, color = blue]
            o_last o_dummy_from o_dummy_to
        }
        
        p_head_from -- o_dummy_from [dir = forward]
        p_head_from_first -- o_first [dir = forward]
        p_head_to -- o_dummy_to [dir = forward]
        p_node -- o_node [dir = forward]
        {
            rank = same
            o_dummy_from -- o_first -- o_many_cut -- o_node -- o_many_remain -- o_last -- o_dummy_from
        }
    }

* After

    graph {
        subgraph ptr {
            node [shape = none]
            p_head_from [label = "head_from"]
            p_head_to [label = "head_to"]
            p_node [label = "node"]
            p_head_from_first [label = "head_from_first"]
        }
        subgraph obj {
            node [shape = box, label = ""]
            o_many_cut, o_many_remain [shape = none, label = "..."]
            o_first, o_node [style = filled, color = blue]
            o_last o_dummy_from o_dummy_to
        }
        
        p_head_from -- o_dummy_from [dir = forward]
        p_head_from_first -- o_first [dir = forward]
        p_head_to -- o_dummy_to [dir = forward]
        p_node -- o_node [dir = forward]
        {
            rank = same
            o_dummy_from -- o_many_remain -- o_last -- o_dummy_from
            o_dummy_to -- o_first -- o_many_cut -- o_node -- o_dummy_to
        }
    }

---

接著來看 Merge Sort 的實作。

#### `list_ele_t`, `queue_t`

typedef struct __element {
    char *value;
    struct __element *next;
    struct list_head list;
} list_ele_t;

typedef struct {
    list_ele_t *head; /* Linked list of elements */
    list_ele_t *tail;
    size_t size;
    struct list_head list;
} queue_t;

從上面定義可以看到 `queue_t` 裡面已經有引入 `struct list_head` 了，但是還又自行維護另一個 singly linked list 。

引入 `struct list_head` 的目的在於可以利用 API 來快速實作完 Merge Sort 。
自行維護 singly linked list 的目的在於實作 `q_free()` 的時候比較方便。

#### `list_merge_sort()`

典型的分治法實作，先將待排序的 linked list 從中間切分成兩個小的 linked list 之後利用遞迴呼叫分別排序完後再將兩個已排序的 linked list 合併成一個已排序的 linked list 。

:::warning
這邊的排序只有對 circular doubly linked list 做排序。
:::

### 指出改進空間並實作

#### 改進空間

在 `queue_t` 中總共有兩種 linked list ，雖然這兩個 linked list 都有各自的存在目的，但是這樣就會出現兩個問題：
1. 會有兩個順序一模一樣的 linked list 存在，差別只在於一個為 circular doubly linked list 而另一個為 singly linked list ，且在這個實作中這兩個 linked list 並不是必須同時存在的，可以只保留其中一個就完成需要的功能。
2. 呼叫完 `list_merge_sort()` 後兩個 linked list 的順序並不一致。
singly linked list 的順序為排序前的順序。

上述兩個問題只要把其中一種 linked list 去掉後就可以同時解決。

這邊我決定保留 `struct list_head` ，因為有前面許多 API 的幫助確實讓 Merge Sort 的實作簡單不少，而且去掉 singly linked list 之後並不會讓 `q_free()` 變得太複雜。

#### 實作

##### `queue_t`, `list_ele_t`

 typedef struct __element {
     char *value;
-    struct __element *next;
     struct list_head list;
 } list_ele_t;

 typedef struct {
-    list_ele_t *head; /* Linked list of elements */
-    list_ele_t *tail;
     size_t size;
-    struct list_head list;
+    struct list_head list; /* Linked list of elements */
 } queue_t;

首先最基本的就是把 singly linked list 的 link 刪掉。

##### `get_middle()`, `list_merge_sort()`

-static list_ele_t *get_middle(struct list_head *list)
+static struct list_head *get_middle(struct list_head *list)
 {
     ...
-    return list_entry(slow, list_ele_t, list);
+    return slow;
 }

 void list_merge_sort(queue_t *q)
 {
     ...
     INIT_LIST_HEAD(&left.list);
-    list_cut_position(&left.list, &q->list, &get_middle(&q->list)->list);
+    list_cut_position(&left.list, &q->list, get_middle(&q->list));
     list_merge_sort(&left);
     list_merge_sort(q);
     ...
 }

和之前提到的兩個問題沒什麼關係，但是也是可以簡化的部分。

`get_middle()` 只有在 `list_merge_sort()` 中被呼叫到，且原本的作法為回傳中間點的 `list_ele_t` ，然後 `list_merge_sort()` 中使用的時候還是取 `list_ele_t` 中的 `struct list_head` 成員。
因此改成直接回傳 `struct list_head *` 就可以省下一些不必要的操作且可以讓程式碼更好閱讀。

##### `q_new()`

static queue_t *q_new()
 {
     queue_t *q = malloc(sizeof(queue_t));
     if (!q)
         return NULL;
 
-    q->head = q->tail = NULL;
     q->size = 0;
     INIT_LIST_HEAD(&q->list);
     return q;
 }

##### `q_free()`

以下為使用 `list_for_each` 的作法：

static void q_free(queue_t *q)
{
    if (!q)
        return;

    struct list_head *current;
    list_for_each(current, &q->list) {
        list_ele_t *tmp = list_entry(current, list_ele_t, list);
        free(tmp->value);
        free(tmp);
    }
    free(q);
 

但是因為 `current` 為指向 `list_ele_t` 的成員的指標，然後在迴圈執行完 `free(ele)` 之後 `current` 指向的物件的生命週期已經結束，但是又會因為 `list_for_each` 而執行 `current = current->next` ，因此就造成了 heap-use-after-free 漏洞。

解決的方法為使用 Linux 核心 [include/linux/list.h](https://github.com/torvalds/linux/blob/master/include/linux/list.h) 中的 `list_for_each_safe` 。
原理為事先紀錄下一個要走到的節點 `n`，迴圈執行完之後就用 `pos = n` 而不是 `pos = pos->next` 來走到下一個節點，如此一來就不會用到已經被釋放的空間。

:::warning
TODO: 解釋 Linux 核心中以 `_safe` 結尾的 API 背後的設計考量，並舉出 Linux 核心原始程式碼的案例
:notes: jserv
:::

最終修改：

+/**
+ * list_for_each_safe - iterate over a list safe against removal of list entry
+ * @pos:    the &struct list_head to use as a loop cursor.
+ * @n:        another &struct list_head to use as temporary storage
+ * @head:    the head for your list.
+ */
+#define list_for_each_safe(pos, n, head) \
+    for (pos = (head)->next, n = pos->next; pos != (head); \
+        pos = n, n = pos->next)

 static void q_free(queue_t *q)
 {
     if (!q)
         return;
         
-    list_ele_t *current = q->head;
-    while (current) {
-        list_ele_t *tmp = current;
-        current = current->next;
+    struct list_head *current, *next;
+    list_for_each_safe (current, next, &q->list) {
+        list_ele_t *tmp = list_entry(current, list_ele_t, list);
         free(tmp->value);
         free(tmp);
     }
     free(q);
 }

##### `q_insert_head()`

 bool q_insert_head(queue_t *q, char *s)
 {
     ...
     newh->value = new_value;
-    newh->next = q->head;
-    q->head = newh;
-    if (q->size == 0)
-        q->tail = newh;
     q->size++;
     list_add_tail(&newh->list, &q->list);
 }

---

## 測驗 `2`

### 運作原理

函式最後的回傳為 `return (n + 1) >> 1;` ，如果有辦法把 `n` 中最高位的 1 以下的位元也都設為 1 ，則這個 `return` 的寫法就會回傳預期的值。

1. `n |= n >> 1` 會將從最高位的 1 算起的 2 個位元設為 1 。

2. `n |= n >> 2` 又會將從最高位的 1 算起的 4 個位元設為 1 。
> 因為有了 1. 的操作，這行程式碼才有辦法確保將 4 個位元設為 1 的效果

而之後就以此類推。

因為參數為 16 位元的整數，所以最多可能需要將 16 個位元設為 1 ，也因為最多只需要設 16 個位元，最後只有停在 `n |= n >> 8` 而沒有繼續 `n |= n >> 16` 。

且根據 C11 6.7.5.2
> The integer promotions are performed on each of the operands. The type of the result is
> that of the promoted left operand. If the value of the right operand is negative or is
> greater than or equal to the width of the promoted left operand, the behavior is undefined.

當 `>>` 運算子的位移量大於或等於數字的長度，這個操作是 Undefined Behavior ，所以不應該出現 `n |= n >> 16` 。

### `is_power_of_2()`

/**
 * is_power_of_2() - check if a value is a power of two
 * @n: the value to check
 *
 * Determine whether some value is a power of two, where zero is
 * *not* considered a power of two.
 * Return: true if @n is a power of 2, otherwise false.
 */
static inline __attribute__((const))
bool is_power_of_2(unsigned long n)
{
    return (n != 0 && ((n & (n - 1)) == 0));
}

從註解可以看到 0 不算是一個二的冪，因此在 `return` 的時候就先把這個情況特判回傳 `false` ，所以接下來只考慮 `n != 0` 的情況。

因為 `n` 大於 0 ，所以 `n` 可以視為一個以上不同的二的冪的和，也就是說 $n = 2^{x_0} + 2^{x_1} + \dots$ 。

對於一個二的冪，一定會符合 `(n & (n - 1)) == 0` 的情況，以 `32` 來舉例， `32` 是二的冪，以八位元的二進位表示就是 `00100000` ，`32 - 1 = 31` 以二進位表示就是 `00011111` ，可以看到 `00100000 & 00011111` 的結果就是 `0` ，因為沒有任何一個位置的位元同時是 1 。

如果 `n` 不是二的冪，所以就可以將 `n` 看成**兩個**以上不同的二的冪的和，而 `n - 1` 只會對最小的二的冪造成影響，其餘的二的冪還是保持原樣，所以可以確定如果 `n` 不是二的冪的話 `(n & (n - 1)) == 0` 一定不成立。

以下用 `40` 來舉例，`40` 的二進位表示為 `00101000` ，可以看成 `00100000 + 00001000` ，然後將 `40 - 1 = 39` 以二進位表示就是 `00100111` ，這邊可以視為 `00100000 + 00000111` ，可以看到減一的效果只有作用在 `00001000` 上面，並不會影響到 `00100000` ，所以不管有沒有減一 `00100000` 都會存在，並且這會造成做 bitwise and 運算的時候結果不為 0 ，也就讓判斷式回傳 `false` 。

### `__rounddown_pow_of_two()`

/**
 * __rounddown_pow_of_two() - round down to nearest power of two
 * @n: value to round down
 */
static inline __attribute__((const))
unsigned long __rounddown_pow_of_two(unsigned long n)
{
    return 1UL << (fls_long(n) - 1);
}

首先先看有用到此函式的地方，也就是 `rounddown_pow_of_two()` 這個 macro 的註解，可以看到當 `n` 為 0 的時候結果為未定義。

/**
 * rounddown_pow_of_two - round the given value down to nearest power of two
 * @n: parameter
 *
 * round the given value down to the nearest power of two
 * - the result is undefined when n == 0
 * - this can be used to initialise global variables from constant data
 */
#define rounddown_pow_of_two(n)            \
(                                          \
    __builtin_constant_p(n) ? (            \
        (1UL << ilog2(n))) :               \
    __rounddown_pow_of_two(n)              \
 )

因為實作的想法在數學意義上可以表示成回傳 $2^{\lfloor log_2{n} \rfloor}$ ，而當 `n` 為 0 的時候取 $log$ 則會得到無限大，而 $2^\infty = \infty$ ，因此結果為未定義，使用時也該注意不可傳入 0 。

接著再看 `fls_long()` ，此函式會根據 `unsigned long` 為 32 還是 64 位元來選擇使用 `fls()` 還是 `fls64()` ，這兩個函式的共通點有兩個：
1. 都是回傳最高位的 1 的位置，如果傳入 0 則回傳 0 。
2. 位置的編號從 LSB 到 MSB 都是 `1 ~ 8 * sizeof(unsigned long)`

因為此函式為 round down ，所以不管 `n` 是不是二的冪，回傳的值都會是 `n` 的最高位的 1 ，而最高位的 1 的位置為 `fls_long(n)` ，而 LSB 的位置為 1 ，因此 `fls_long(n) - 1` 的值就是從 1 這個位置 shift 到 `fls_long(n)` 所需要的偏移量，

`1UL << (fls_long(n) - 1)` 則就會是 `n` 的最高位的 1 。

### `__roundup_pow_of_two()`

/**
 * __roundup_pow_of_two() - round up to nearest power of two
 * @n: value to round up
 */
static inline __attribute__((const))
unsigned long __roundup_pow_of_two(unsigned long n)
{
    return 1UL << fls_long(n - 1);
}

首先當 `n` 為 0 的時候和 [`__rounddown_pow_of_two()`](#__rounddown_pow_of_two) 同理，是未定義。

此函式的原理將分成以下兩種情境來探討：

* `n` 是二的冪
預期回傳 `n` 。

因為 `n` 是二的冪，所以 `fls_long(n - 1)` 就會是 `fls_long(n) - 1` ，所以 `1UL << fls_long(n - 1)` 就會變成 `1UL << (fls_long(n) - 1)` ，也就是 `n` 的最高位的 1 ，然後又因為 `n` 是二的冪，所以 `1UL << (fls_long(n) - 1)` 也就會等於 `n` 。

* `n` 不是二的冪
預期回傳 `1UL << fls_long(n)` 。

和 [`is_power_of_2`](#is_power_of_2) 的解釋中提到的相同，此時 `n` 可以視為兩個以上不同的二的冪的和，且減一的效果只會作用在最小的二的冪，換句話說 `n` 的最高位的 1 不會受到影響，所以 `fls_long(n - 1)` 就等同於 `fls_long(n)` ，也就得到預期的結果了。

---

## 測驗 `3`

## 測驗 `4`