2021q1 Homework2 (quiz2)

contributed by < D4nnyLee >

題目連結

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

測驗 1

解釋程式碼運作原理

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

list_add_tail()

• Before

• After

list_del()

• Before

• After

list_splice_tail()

• Before

• After

list_cut_position()

• Before

• After

---

接著來看 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 。

這邊的排序只有對 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 中的 list_for_each_safe 。
原理為事先紀錄下一個要走到的節點 n，迴圈執行完之後就用 pos = n 而不是 pos = pos->next 來走到下一個節點，如此一來就不會用到已經被釋放的空間。

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 lo{g}_{2}n\rfloor }$ ，而當 n 為 0 的時候取

$log$ 則會得到無限大，而

$2^{\mathrm{\infty }}=\mathrm{\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() 同理，是未定義。

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

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

---

測驗 3

測驗 4