# 2021q1 Homework2 (quiz2)
contributed by < `iLeafy11` >
###### tags: `linux2021`

## 作業描述

## 測驗 1
### 解釋 `include/linux/list.h` 的精簡實作的運作原理
#### Function-like macro: `offsetof`
`offsetof` 定義在 `<linux/stddef.h>` 中，用來計算某一個 struct 結構的成員相對於該結構起始地址的偏移量 (offset)。

#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)

1.                         0
2.                ((TYPE *)0)
3.              ( ((TYPE *)0)->MEMBER )
4.             &( ((TYPE *)0)->MEMBER )
5.  ( (size_t) &( ((TYPE *)0)->MEMBER )

上述程式碼的 operation 可以拆解成以下：
1. 首先從數值 `0` 開始。
2. 將數值 `0` (`NULL`) 強制轉型成某個 `struct` 結構的指標 `(TYPE *)` 型別，`0` 會被認定是該 `struct` 結構 `TYPE` 的起始地址。
3. 然後再指向該 `struct` 結構型別內的某個成員 `MEMBER`。
4. 取得其地址 (address of `( ((TYPE *)0)->MEMBER )`)。
5. 再將該地址轉型回 `size_t`。

因為起始地址為 `0`，所以 `MEMBER` 的地址也就等於 `MEMBER` 與起始地址 `0` 的偏移 (offset)。
如果將起始地址 `0` 換成不同的數字，那麼就要記得將結果扣掉該數字，這樣才可以算出偏移量 (offset)。

#define offsetof(TYPE, MEMBER) ((size_t) &(((TYPE *)87)->MEMBER) - 87)

上述程式碼實現依賴於早期編譯器，所以不會有 Undefined behavior: dereference a `NULL` pointer 的問題，如今以 C11 的標準來看，`offsetof` 被定義於 gcc 內部實作：

#define offsetof(st, m) __builtin_offsetof(st, m)

詳細資料參照： [GCC syntastic extension: Offsetof macro](https://gcc.gnu.org/onlinedocs/gcc/Offsetof.html#Offsetof)
至於 `__builtin_offsetof(st, m)` gcc 的實作，在此不討論，參照： [gcc/cp/parser.c](https://raw.githubusercontent.com/gcc-mirror/gcc/master/gcc/cp/parser.c)
#### Function-like macro: `container_of`
`container_of() - Calculate address of object that contains address ptr`

#define container_of(ptr, type, member)                            \
    __extension__({                                                \
        const __typeof__(((type *) 0)->member) *__pmember = (ptr); \
        (type *) ((char *) __pmember - offsetof(type, member));    \
    })

`container_of()` macro 使用到 gcc extention `__extension__` ，包含 `__typeof__()` 以及 `offsetof()` 的使用。
`container_of()` 實作的原理：
1. 與上面 `offsetof()` 原理相似，只是從原本第 `4.` 步取地址，變成用 `__typeof__()` 去取得其型別，並宣告該型別的指標 `__pmember` 去接住被複製的 `(ptr)` 的值。
2. `__pmember` 的值減去 `offsetof()` 該結構 `struct` 型別 `type` 的偏移量，就可以得到該結構 `struct` 型別 `type` 其內部成員 `member` 的 container 的地址。

對於為何 `const __typeof__(((type *) 0)->member) *__pmember = (ptr)` 不會產生 Undefined behavior: dereference a `NULL` pointer，~~我們將問題推給 gcc 對於 `typeof` extension 的實作~~，參照： ["Why this 0 in ((type*)0)->member in C?" from Stack Overflow](https://stackoverflow.com/questions/13723422/why-this-0-in-type0-member-in-c)
:::info
**以 GNU extension `typeof` operator 優化 function-like macro 實作**

若在定義 Macro 時，善用 GNU extension 的 `typeof` operator 可以避免 double evaluation。

**Double evaluation 的範例**

假設我們實作了 function-like macro `max()`，並定義函式 `x()`、`y()` 如下

#define max(a,b) (a < b ? b : a)
int x(){ turnLeft();   return 0; }
int y(){ turnRight();  return 1; }

呼叫上述實作的 function-like macro `max()`

int findmax = max(x(), y());

將上面呼叫的 function-like macro `max()` 展開來看

int findmax = max(x() < y() ? y() : x());

我們可以觀察到，`max()` 在被呼叫後，在比較大小 `x() < y()` 的過程中，`x()` 和 `y()` 都會個別被呼叫 1 次，此時 `turnLeft()` 和 `turnRight()` 也各會被執行一次。
因為 `y()` 函式 `return` 的值 `1` 比 `x()` 函式 `return` 的值 `0` 還要大，所以 `y()` 函式會被呼叫第 2 次，於是 `turnRight()` 會再被執行 1 次。
這樣造成的結果就會導致 `max()` 在被呼叫後，`turnLeft()` 被執行 1 次，而 `turnRight` 被執行 2 次的情形。
所以說，如果單純以 [運算表達式 (`expressions`)](https://en.cppreference.com/w/c/language/expressions)，只用 `operators` 和 `operands` 去實作 function-like macro，一不小心就有可能產生會造成 double evaluation 的 function-like macro。

**以 GNU extension 的 `typeof` operator 改寫 `max()`**

實作如下：

#define max(a,b) \
  ({ typeof (a) _a = (a); \
      typeof (b) _b = (b); \
    _a > _b ? _a : _b; })

若 `max()` 改用 GNU extension 的 `typeof` operator 實作，即可避免 double evaluation，同時亦可確保型別 (type) 的安全。

在 GNU C 裡面，GNU extension 可以利用 `__auto_type` operator 提供更好的方式實作 `max()`，如下：

#define max(a,b) \
  ({ __auto_type _a = (a); \
      __auto_type _b = (b); \
    _a > _b ? _a : _b; })

Reference：
* ["What is double evaluation and why should it be avoided?" from Stack Overflow](https://stackoverflow.com/questions/39439181/what-is-double-evaluation-and-why-should-it-be-avoided)
* [6.7 Referring to a Type with typeof from C Extensions (Using the GNU Compiler Collection (GCC))](https://gcc.gnu.org/onlinedocs/gcc/Typeof.html#Typeof)
:::
#### Data Structure: `struct list_head - Head and node of a doubly-linked list`

struct list_head {
    struct list_head *prev, *next;
};

digraph list_head {
    rankdir=LR;
    node[shape=record, style=bold];
    head [label="{<prev>prev|<next>next}"];
}

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

digraph list {
    rankdir=LR;
    node[shape=record, style=bold];
    subgraph cluster_0 {
        node [shape=record];
        value [label="{value}"];
        head [label="{<prev>prev|<next>next}"];
        style=bold;
        label=list_ele_t
    }
    
}

簡化成下圖：

digraph list_ele {
    rankdir=LR;
    node[shape=record];
    node [shape=record];
    head [label="value|{<left>prev|<right>next}", style=bold];
}

#### Function-like macro:
`LIST_HEAD - Declare list head and initialize it`

#define LIST_HEAD(head) struct list_head head = {&(head), &(head)}

digraph list_init {
    rankdir=LR;
    node[shape=record];
    style=bold
    node [shape=record];
    head [label="value|{<left>prev|<right>next}", style="bold"];
    head:right:e -> head:left:w[arrowhead=normal, arrowtail=normal, dir=both];
}

`list_entry() - Calculate address of entry that contains list node`

#define list_entry(node, type, member) container_of(node, type, member)

digraph container {
    rankdir=LR;
    node[shape=record];
    compound=true;
    style=bold;
    subgraph cluster_0 {
        container [label = "container" style=filled,color=white];
        subgraph cluster_1 {
            node [shape=record];
            element [label="|{|}", style="bold"];
            label = "member" 
        }
    }
    
    element -> container[ltail=cluster_1, lhead=cluster_0];
}

`list_for_each - iterate over list nodes`

#define list_for_each(node, head) \
    for (node = (head)->next; node != (head); node = node->next)

digraph ele_list {
    rankdir=LR;
    node[shape=record];
    h [label="head", style=dashed, color=grey];
    h -> e1:right:w [style=dashed, color=grey];
    e1 [label="head node|{<left>prev|<right>next}", style="bold", color=grey];
    e2 [label="cat|{<left>prev|<right>next}", style="bold"];
    e3 [label="...", style="bold"];
    e4 [label="eat|{<left>prev|<right>next}", style="bold"];
    e5 [label="fat|{<left>prev|<right>next}", style="bold"];
    e1:right:e -> e2:left:w[arrowhead=normal, arrowtail=normal, dir=both];
    e2:right:e -> e3:left:w[arrowhead=normal, arrowtail=normal, dir=both];
    e3:right:e -> e4:left:w[arrowhead=normal, arrowtail=normal, dir=both];
    e4:right:e -> e5:left:w[arrowhead=normal, arrowtail=normal, dir=both];
    e5:right:e -> e1:left:w[arrowhead=normal, arrowtail=normal, dir=both];
}

:::info
TODO: 採用 circular linked list 是基於哪些考量？
:::

#### Functions for implementing Merge Sort

### 改進上述程式碼並實作

#### 去除不必要的資料結構
不需要用到佇列 (Queue) 資料結構，此結構無益於 linked list merge sort 的排序，且同時浪費記憶體以及效能。

    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;

#### 修改函式
**函式： `list_del()`**

`list_del()` 以命名上來說是 **刪除（delete)** list 的某個節點結構，將該節點移出 list 並將釋放其記憶體。然而觀察 `list_del()` 程式碼，其行為卻是只有將目標節點移出 list，而沒有實質上的去 __刪除 (delete)__ 該目標節點。因此這裡我認為比較好的命名方式是 __拆除 (remove)__ 目標節點，函式更名為 `list_remove()`。

    /**
-    * list_del() - Remove a list node from the list
+    * list_remove() - Remove a list node from the list
     * @node: pointer to the node
     */
-   static inline void list_del(struct list_head *node)
+   static inline void list_remove(struct list_head *node)
    {
        struct list_head *next = node->next, *prev = node->prev;
        next->prev = prev; prev->next = next;
    }

**函式： `list_merge_sort()`**

因為刪除不必要的佇列 (Queue) 結構，所以傳遞佇列 (Queue) 結構參數的函式必須要做修正，改成傳遞 `struct list_head` 的指標參數。

-   void list_merge_sort(queue_t *q)
+   void list_merge_sort(struct list_head *list)
    {
-       if (list_is_singular(&q->list))
-           return;
-       queue_t left;
-       INIT_LIST_HEAD(&left.list);
-       list_cut_position(&left.list, &q->list, &get_middle(&q->list)->list);
+       if (list_is_singular(list))
+           return;
+       struct list_head left;
+       INIT_LIST_HEAD(&left);
+       list_cut_position(&left, list, &get_middle(list)->list);
        struct list_head sorted;
        list_merge_sort(&left);
-       list_merge_sort(q);
-       list_merge(&left.list, &q->list, &sorted);
-       INIT_LIST_HEAD(&q->list);
-       list_splice_tail(&sorted, &q->list);
+       list_merge_sort(list);
+       list_merge(&left, list, &sorted);
+       INIT_LIST_HEAD(list);
+       list_splice_tail(&sorted, list);
    }

**函式： `validate()`**

修改原因及結果同上。

-   static bool validate(queue_t *q)
+   static bool validate(struct list_head *list)
    {
        struct list_head *node;
-       list_for_each (node, &q->list) {
-           if (node->next == &q->list)
-               break;
+       list_for_each (node, list) {
+           if (node->next == list)
+               break;
            if (strcmp(list_entry(node, list_ele_t, list)->value,
                       list_entry(node->next, list_ele_t, list)->value) > 0)
                return false;
        }
        return true;
    }

**函式： `list_merge()`**

觀察函式 `list_merge()` 裡面，`if` `while` 以及最底下的三元運算子 (ternary operator) 的條件判斷皆與 `list_empty()` 相關。其中，不難發現，前面兩個 `if` 條件式所做的行為，與底下 `while` 以及最底下三元運算子 (ternary operator) 所做的行為自相矛盾。
而這兩個 `if` 條件式內有 `return` 且寫在 `while` 迴圈之前，因此先判斷 `list_empty(lhs)` 而後判斷 `list_empty(rhs)` 的寫法也會在順序上出現問題，因為 `list_empty(lhs)` 與 `list_empty(rhs)` 兩個條件應當是要被同時考量的存在。
舉例來說，在執行 `merge_sort()` 的過程中，會呼叫到 `get_middle()` 來切割 linked list。假設被切割的 linked list 的節點個數為奇數，最終在遞迴的過程中勢必會切割到其中一邊的 linked list 只有 1 個節點，而另一邊 linked list 有 2 個節點的情形。
假設傳進來的參數 `rhs` 接收到的數值是，含有 2 個節點的 linked list 指標，而 `lhs` 接收到的數值是，只含有 1 個節點的 linked list 指標，那麼在不修改題目原始程式碼的情形下，`if` 條件的行為便會造成 `merge_sort()` 的錯誤。
結論是，這兩個 `if` 條件除了是多餘的程式碼 (redundant code) 之外，也會造成 `merge_sort()` 演算法出錯，因此必須予以刪除。

    static void list_merge(struct list_head *lhs,
                       struct list_head *rhs,
                       struct list_head *head)
    {
        INIT_LIST_HEAD(head);
-       if (list_empty(lhs)) {
-           list_splice_tail(lhs, head);
-           return;
-       }
-       if (list_empty(rhs)) {
-           list_splice_tail(rhs, head);
-           return;
-       }
        while (!list_empty(lhs) && !list_empty(rhs)) {
            char *lv = list_entry(lhs->next, list_ele_t, list)->value;
            char *rv = list_entry(rhs->next, list_ele_t, list)->value;
            struct list_head *tmp = strcmp(lv, rv) <= 0 ? lhs->next : rhs->next;
            list_remove(tmp);
            list_add_tail(tmp, head);
        }
        list_splice_tail(list_empty(lhs) ? rhs : lhs, head);
    }

**函式：`merge_sort()`**

`merge_sort()` 需要考慮當 list 為空的情形，否則會有 segmentation fault。

void list_merge_sort(struct list_head *list)
{
-   if (list_is_singular(list)) 
-       return;
+   if (list_empty(list) || list_is_singular(list))
+       return;
    struct list_head left;
    struct list_head sorted;
    INIT_LIST_HEAD(&left);
    list_cut_position(&left, list, &get_middle(list)->list);
    list_merge_sort(&left);
    list_merge_sort(list);
    list_merge(&left, list, &sorted);
    INIT_LIST_HEAD(list);
    list_splice_tail(&sorted, list);
}

:::info
TODO:
:::
#### 新增函式
**函式： `list_alloc_add_tail()`**

動態配置記憶體，新增 `list_ele_t` 的節點 `new`，同時再次動態配置記憶體，複製一份 `char *s` 傳遞進來的字串到 `new->value`。最後再藉由 `list_add_tail()` 函式以及傳遞進來的 `struct list_head` 的指標參數，將新的節點 `new` 新增至 circular doubly linked list。
函式執行期間，若動態配置記憶體失敗，則 `return false`。需要注意，如果是在 `strdup()` 動態配置記憶體失敗，則必須歸還在 `list_alloc_add_tail()` 函式內先前已成功動態配置的記憶體 `new`。若兩次的動態配置記憶體皆已成功配置，則在函式執行到最後時 `return true`。
此實作手法類似於 [`quiz1`](https://hackmd.io/g1_AyhXXRRmwtRh965SKLw?view) 的 `q_insert_head()` 以及 `q_insert_tail` 的實作。

bool list_alloc_add_tail(struct list_head *head, char *s)
{
    list_ele_t *new = malloc(sizeof(list_ele_t));
    if (!new) 
        return false;
    new->value = strdup(s);
    if (!new->value) {
        free(new);
        return false;
    }
    list_add_tail(&new->list, head);
    return true;
}

**Function-like macro: `list_for_each_safe()`**

為了能夠實作 `list_free()`，刪除整個 list 的函式，所以參考了 [linux/list.h](https://github.com/torvalds/linux/blob/master/include/linux/list.h) 的實作 `list_for_each_safe()`。
之所以使用 `list_for_each_safe()` 而非 `list_for_each()` 的原因是，使用 `list_for_each()` 會在刪除節點的過程中將存取下個節點的指標一併抹除，所以為了避免在 iterate over a list 的過程中存取不到下個節點，於是選擇採用此實作。

/**
 * Shamelessly copy from linux/list.h
 * 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)

**函式： `list_free()`**

利用 `list_for_each_safe()`，走訪整個 linked list 的所有節點，然後再利用 `list_entry()` ，找到在 container (`list_ele_t` structure) 內部以及 container 本身被動態配置的記憶體，然後再將其釋放 (`free`) 掉。

void list_free(struct list_head *head)
{
    struct list_head *curr, *next;
    list_for_each_safe(curr, next, head) {
        list_remove(curr);
        list_ele_t *target = list_entry(curr, list_ele_t, list);
        free(target->value);
        free(target);
    }
}

#### 修改主程式以及編譯執行
**主程式：`main()`**

int main(void)
{
    FILE *fp = fopen("cities.txt", "r");
    if (!fp) {
        perror("failed to open cities.txt");
        exit(EXIT_FAILURE);
    }
-   queue_t *q = q_new();
+   LIST_HEAD(list);
    char buf[256];
    while (fgets(buf, 256, fp)) {
-       q_insert_head(q, buf);
+       list_alloc_add_tail(&list, buf);
    }
    fclose(fp);
-   list_merge_sort(q);
-   assert(validate(q));
-   q_free(q);
+   list_merge_sort(&list);
+   assert(validate(&list));
+   list_free(&list);
    return 0;
}

$ gcc -Wall -o merge_sort merge_sort.c
$ ./merge_sort

#### 檢查是否有 memory leak

$ valgrind --leak-check=full ./merge_sort
==19101== Memcheck, a memory error detector
==19101== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==19101== Using Valgrind-3.15.0 and LibVEX; rerun with -h for copyright info
==19101== Command: ./merge_sort
==19101== 
==19101== 
==19101== HEAP SUMMARY:
==19101==     in use at exit: 0 bytes in 0 blocks
==19101==   total heap usage: 187,656 allocs, 187,656 frees, 4,529,436 bytes allocated
==19101== 
==19101== All heap blocks were freed -- no leaks are possible
==19101== 
==19101== For lists of detected and suppressed errors, rerun with: -s
==19101== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)

### 將 lib/list_sort.c 的實作抽離為可單獨執行
:::info

:::
#### compile & execution
:::info
TODO：附上解釋
:::

#### 設計實驗 & 效能分析
### 與 quiz1 作效能比較
(linked list merge_sort vs linked list quick_sort)\
？？用相同的資料結構？？
:::info
TODO：用相同資料結構刻出 QuickSort 並比較效能
:::

---

## 測驗 2
考慮函式 `func()` 接受一個 16 位元無號整數 N，並回傳小於或等於 N 的 power-of-2。

uint16_t func(uint16_t N) {
    /* change all right side bits to 1 */
    N |= N >> 1;
    N |= N >> 2;
    N |= N >> 4;
    N |= N >> 8;

    return (N + 1) >> 1;
}

其實上述程式碼在做的事情是，就是 Find most significant (left-most) bit。

### 解釋 `func()` 的運作原理

N |= N >> 1;
N |= N >> 2;
N |= N >> 4;
N |= N >> 8;

上述程式碼的作用是，將所有比 N 的 most significant (left-most) bit 位置還要低的 bit 通通變成 1。原理是 `N |= N >> 1` 會將 most significant (left-most) bit 的下一個 bit 利用 `bitwise or` 也變成是 1，而 `N |= N >> 2` 會利用 `N |= N >> 1` 的結果將 most significant (left-most) bit 的下一個 bit 的後面兩個 bit 也變成是 1，以此類推。
因為函式 func 是接受一個 16 位元無號整數 N，所以 right shift 的最大值就會是 8。
* Example： N = (1000 0000 0000 0000)₂ = (32768)₁₀

    1000 0000 0000 0000
or  0100 0000 0000 0000 (right-shifted by 1)
is  1100 0000 0000 0000

    1100 0000 0000 0000
or  0011 0000 0000 0000 (right-shifted by 2)
is  1111 0000 0000 0000

    1111 0000 0000 0000
or  0000 1111 0000 0000 (right-shifted by 4)
is  1111 1111 0000 0000

    1111 1111 0000 0000
or  0000 0000 1111 1111 (right-shifted by 8)
is  1111 1111 1111 1111

:::info
TODO: 描述並解釋
:::
考慮到 `func()` 最後 `return` 的值為 `(N + 1) >> 1`，若 `N` 的值 = (1000 0000 0000 0000)₂ = (32768)₁₀，推測在 `(N + 1)` 時有可能會產生 overflow。

稍微實作實驗一下 `func.c`：

#include <stdio.h>
#include <stdint.h>

uint16_t func(uint16_t N)
{
    N = N | N >> 1;
    N = N | N >> 2;
    N = N | N >> 4;
    N = N | N >> 8;
    return (N + 1) >> 1;
}

int main(int argc, char *argv[])
{
    printf("%u\n", func(32768));
    return 0;
}

執行時沒有發現什麼問題。

$ gcc -Wall -g -o func func.c
$ ./func
32768

使用 Address Sanitizer 也沒有報錯。

$ clang -fsanitize=address -O1 -fno-omit-frame-pointer -g test.c
$ ./a.out

用 gcc 加入參數 `-Wconversion` 編譯時，就會報錯。

$ gcc -o func -Wconversion func.c
test.c: In function ‘func’:
test.c:10:20: warning: conversion from ‘int’ to ‘uint16_t’ {aka ‘short unsigned int’} may change value [-Wconversion]
   10 |     return (N + 1) >> 1;
      |            ~~~~~~~~^~~~

查看 C99 規格書。
:::info
**C99 Standard - §6.3.1.1**

If an `int` can represent all values of the original type, the value is converted to an `int`; otherwise, it is converted to an `unsigned int`. These are called the integer promotions. All other types are unchanged by the integer promotions.
:::
因此是不會發生 overflow 的。在 **C99 Standard** 中，有定義所謂 "integer promotions" 的行為，所以 `return (N + 1) >> 1;` 這段程式碼實際上會等同於：

return (uint8_t)((int)(N + 1) >> 1);

用 gcc 編譯查看其 Assembly 可發現其端倪。

$ gcc -S func.c -o func.s
$ cat func.s

	.file	"func.c"
	.text
	.globl	func
	.type	func, @function
func:
.LFB6:
	.cfi_startproc
	endbr64
	pushq	%rbp
	.cfi_def_cfa_offset 16
	.cfi_offset 6, -16
	movq	%rsp, %rbp
	.cfi_def_cfa_register 6
	movl	%edi, %eax
	movw	%ax, -4(%rbp)
	movzwl	-4(%rbp), %eax
	shrw	%ax
	orw	%ax, -4(%rbp)
	movzwl	-4(%rbp), %eax
	shrw	$2, %ax
	orw	%ax, -4(%rbp)
	movzwl	-4(%rbp), %eax
	shrw	$4, %ax
	orw	%ax, -4(%rbp)
	movzwl	-4(%rbp), %eax
	shrw	$8, %ax
	orw	%ax, -4(%rbp)
	movzwl	-4(%rbp), %eax
	addl	$1, %eax
+	sarl	%eax
	popq	%rbp
	.cfi_def_cfa 7, 8
	ret
	.cfi_endproc
.LFE6:
	.size	func, .-func
	.section	.rodata
.LC0:
        ...

:::info
* `eax` is a 32 bit register.
* `sar` right shifts (signed divides) a byte, word, or long value for a count specified by an immediate value and stores the quotient in that byte, word, or long respectively. The second variation right shifts by a count value specified in the CL register. sar rounds toward negative infinity; the high-order bit remains unchanged.

notes: CSAPP: 3/E chapter 3
:::
不過如果是在不同的機器上運作，便不能確定上述程式碼是安全的，因為 32-bit 的 `int` type 只會在有 64-bit 暫存器的機器上實現。所以我們最好還是把數值操作限縮在 `uint16_t` 大小的資料。

從 C99 規格書中可以得知 right-shift 為 well-defined behavior。
:::info
**C99 Standard - §6.5.7**

The result of **E1 >> E2** is **E1** right-shifted **E2** bit positions. If **E1** has an unsigned type or if **E1** has a signed type and a nonnegative value, the value of the result is the integral part of the quotient of **E1** / 2^**E2**. If **E1** has a signed type and a negative value, the resulting value is implementation-defined.
:::
所以程式碼可以改寫如下：

-   return (N + 1) >> 1;
+   return (N >> 1) + 1;

### Linux 核心的 round up/down power of 2 的運作機制
:::info
TODO
:::

---

## 測驗 3
### 解釋 `bitcpy()` 程式碼運作原理

#### 傳遞參數

void bitcpy(void *_dest,      /* Address of the buffer to write to */
            size_t _write,    /* Bit offset to start writing to */
            const void *_src, /* Address of the buffer to read from */
            size_t _read,     /* Bit offset to start reading from */
            size_t count)

[題目敘述](https://hackmd.io/@sysprog/linux2021-quiz2#%E6%B8%AC%E9%A9%97-3)
* `input/_src`: 長度為 8 個 uint8 陣列 (總共 64 位元)。同時也是 `input` 的起始地址。
* `output/_dest`: 長度為 8 個 uint8 陣列 (總共 64 位元)。同時也是 `output` 的起始地址。
* `_write`: 從 `_dest` 的第 `_write` 個位元開始寫入 `_count` 位元數。
* `_read`: 從 `_src` 的第 `_read` 個位元開始讀取 `_count` 位元數。
* `count`: 讀取/寫入的位元數。
#### 變數 `read_lhs` `read_rhs` `source` `write_lhs` `write_rhs` `dest` 的意義

size_t read_lhs = _read & 7;
size_t read_rhs = 8 - read_lhs;
const uint8_t *source = (const uint8_t *) _src + (_read / 8);

* `read_lhs`: `_read & 7` 可以視為是 `_read % 8`。決定在一個 byte 的大小內，從左邊數來的第 `read_lhs` 個 bit 開始讀取。
* `read_rhs`: 決定在一個 byte 的大小內，從右邊數來的第 `read_rhs` 個 bit 開始讀取。
* `source`: 指向 `uint8_t` 的指標，指標數值加 1 等同於指標指向下一個 8 個 bit 的起始位置。其值以 `_src` 為起始地址，加上 `(_read / 8)` 來決定從哪一個 byte 開始讀取。如下圖：

digraph{
    node [shape=plaintext, fontsize=60];
    {
        node [shape=record, fontsize=50, width=30, fixsize=true];
        bit [label="<p0>1111 1111 | <p1>1111 1111 | <p2>1111 1111 | <p3>1111 1111 | <p4>1111 1111 | <p5>1111 1111 | <p6>1111 1111 | <p7>1111 1111", style=bold];
        _src [label="<p0>_src + 0 | <p1>_src + 1 | <p2> _src + 2 | <p3>_src + 3 | <p4>_src + 4 | <p5>_src + 5 | <p6>_src + 6 | <p7> _src + 7"];  
    }
    source [label="source", style=dashed];
    edge [color=grey, style=bold];
    source -> _src:p0;
    source -> _src:p1;
    source -> _src:p2;
    source -> _src:p3;
    source -> _src:p4;
    source -> _src:p5;
    source -> _src:p6;
    source -> _src:p7;
    edge [color=black, style=bold];
    _src:p0 -> bit:p0;
    _src:p1 -> bit:p1;
    _src:p2 -> bit:p2;
    _src:p3 -> bit:p3;
    _src:p4 -> bit:p4;
    _src:p5 -> bit:p5;
    _src:p6 -> bit:p6;
    _src:p7 -> bit:p7;
}

size_t write_lhs = _write & 7;
size_t write_rhs = 8 - write_lhs;
uint8_t *dest = (uint8_t *) _dest + (_write / 8);

* `write_lhs`: 原理同 `read_lhs`。決定在一個 byte 的大小內，從左邊數來的第 `write_lhs` 個 bit 開始寫入。
* `write_rhs`: 原理同 `read_rhs`。決定在一個 byte 的大小內，從右邊數來的第 `write_rhs` 個 bit 開始寫入。
* `dest`: 原理同 `source`。以 `_dest` 為起始地址，加上`(_write / 8)` 來決定從哪一個 byte 開始寫入。如下圖：

digraph{
    node [shape=plaintext, fontsize=60];
    {
        node [shape=record, fontsize=50, width=30, fixsize=true];
        bit [label="<p0>1111 1111 | <p1>1111 1111 | <p2>1111 1111 | <p3>1111 1111 | <p4>1111 1111 | <p5>1111 1111 | <p6>1111 1111 | <p7>1111 1111", style=bold]
        _dest [label="<p0>_dest + 0 | <p1>_dest + 1 | <p2> _dest + 2 | <p3>_dest + 3 | <p4>_dest + 4 | <p5>_dest + 5 | <p6>_dest + 6 | <p7> _dest + 7"];
    }
    edge [color=grey, style=bold];
    dest -> _dest:p0;
    dest -> _dest:p1;
    dest -> _dest:p2;
    dest -> _dest:p3;
    dest -> _dest:p4;
    dest -> _dest:p5;
    dest -> _dest:p6;
    dest -> _dest:p7;
    edge [color=black, style=bold];
    _dest:p0 -> bit:p0;
    _dest:p1 -> bit:p1;
    _dest:p2 -> bit:p2;
    _dest:p3 -> bit:p3;
    _dest:p4 -> bit:p4;
    _dest:p5 -> bit:p5;
    _dest:p6 -> bit:p6;
    _dest:p7 -> bit:p7;
}

#### `bit_mask` 的使用

static const uint8_t read_mask[] = {
    0x00, /*    == 0    00000000b   */
    0x80, /*    == 1    10000000b   */
    0xC0, /*    == 2    11000000b   */
    0xE0, /*    == 3    11100000b   */
    0xF0, /*    == 4    11110000b   */
    0xF8, /*    == 5    11111000b   */
    0xFC, /*    == 6    11111100b   */
    0xFE, /*    == 7    11111110b   */
    0xFF  /*    == 8    11111111b   */
};

static const uint8_t write_mask[] = {
    0xFF, /*    == 0    11111111b   */
    0x7F, /*    == 1    01111111b   */
    0x3F, /*    == 2    00111111b   */
    0x1F, /*    == 3    00011111b   */
    0x0F, /*    == 4    00001111b   */
    0x07, /*    == 5    00000111b   */
    0x03, /*    == 6    00000011b   */
    0x01, /*    == 7    00000001b   */
    0x00  /*    == 8    00000000b   */
};

可以觀察到其實 `read_mask[]` 和 `write_mask[]` 的內容其實是一樣的，只是順序是倒過來的而已。所以其中一個 `bit_mask` 其實是多餘的。
#### 迴圈終止條件 & 讀取/寫入 bit 實作 bit_copy

while (count > 0) {
    ...
    size_t bitsize = (count > 8) ? 8 : count;
    ...
    count -= bitsize;
}

`while` 迴圈會在 `count` 為 `0` 的時候，也就是所有的 bit 被複製完的時候離開 `while` 迴圈。
考量到 `count` 不一定為 `8` 的倍數，因此宣告一個 `bitsize` 變數，其值為迴圈的一次循環中，讀取/寫入的 bit 的個數，一次最多為 `8` 個 bit。而當迴圈執行最後一次時，`bitsize` 的值便是 `count` 除以 `8` 的餘數。
考慮到以下 bitwise operation 來讀取/寫入 bit，以實作 bit_copy。
* `X |= 0 -> X`
* `X &= 1 -> X`
#### 讀取

uint8_t data = *source++;
size_t bitsize = (count > 8) ? 8 : count;
if (read_lhs > 0) {
    data <<= read_lhs;
    if (bitsize > read_rhs)
        data |= (*source >> read_rhs);
}

1. 首先 `data` 複製讀取的 `*source` 的起始 byte 的資料，大小為 1 byte，也就是 8 個 bit。`*source` 被讀完 1 個 byte 之後前往下一個 byte，也就是下一個 8-bit 的起始位置。
2. 在該 byte 內，如果要讀取的起始 bit 的位置沒有對齊讀進來的 byte 的起始位置，也就是當 `read_lhs` 不為 `0` 的時候，則讀取要從左邊數來的第 `read_lhs` 個 bit 開始讀取。所以 `data` 必須要左移 `read_lhs` 個 bit，`data` 右邊的 `read_lhs` 個 bit 會補上 `0`。
3. `bitsize > read_rhs` 的意義是，是否所有要讀取的 bit 都已經完全讀取結束，如果沒有完全讀取結束，則需要跨兩個 byte，再從已前進至下一個 byte 位置的 `*source`，將其值右移 `read_lhs` 個 bit，如此才能複製前 `read_lhs` 個 bit 至 `data` 剛剛被清 `0` 的空間。

if (bitsize < 8)
    data &= read_mask[bitsize];

4. `bitsize < 8` 會意味著 `while` 迴圈的執行是否已經到達最後一次，若是最後一次，則利用 `read_mask` 做為遮罩，將多餘讀取的 bit 抹除掉。

digraph {
    node [shape=plaintext, fontsize=60];
    text [label="Assume read_lhs = 3"];

    {
        node [shape=record, fontsize=50, width=30, fixsize=true];
        next [label="<p0>X | <p1>X | <p2>X | <p3>X | <p4>X | <p5>X | <p6>X | <p7>X", style=bold]
        curr [label="<p0>X | <p1>X | <p2>X | <p3>X | <p4>X | <p5>X | <p6>X | <p7>X", style=bold];
        prev [label="<p0>X | <p1>X | <p2>X | <p3>X | <p4>X | <p5>0 | <p6>0 | <p7>0", style=bold];
    }

    {
        rank=same; prev;
        ""
        "left-shift by 3"
    }

    edge [color=white, style=bold];
    text -> prev;
    prev:p0 -> curr:p0;
    prev:p7 -> curr:p7;
    curr:p0 -> next:p0;

}

read
---
    XXXXXXXX    data copy from *source
--- 
if read_lhs = 3, read_rhs = 5, bitsize <= read_rhs

    XXXXX000    data left-shift by read_lhs
---
if read_lhs = 3, read_rhs = 5, bitsize > read_rhs

    XXXXX000    data left-shift by read_lhs
or  00000XXX    *source right-shift by read_rhs
is  XXXXXXXX
---
if bitsize = 6

    XXXXXXXX    data
and 11111100    read_mask[bitsize]
is  XXXXXX00
---
read end
---

#### 寫入

uint8_t original = *dest;
uint8_t mask = read_mask[write_lhs];
if (bitsize > write_rhs) {
/* Cross multiple bytes */
    *dest++ = (original & mask) | (data >> write_lhs);
    original = *dest & write_mask[bitsize - write_rhs];
    *dest = original | (data << write_rhs);
} else {
// Since write_lhs + bitsize is never >= 8, no out-of-bound access.
    mask |= write_mask[write_lhs + bitsize];
    *dest++ = (original & mask) | (data >> write_lhs);
}

write
---
    XXXXXXXX    original copy from *dest
---    
if write_lhs = 6

    11111100    mask = read_mask[write_lhs]
---
if write_rhs = 2, bitsize = 3

    XXXXXXXX    original
and 11111100    mask
is  XXXXXX00    original & mask

    000000XX    data right-shift by write_lhs
    
    XXXXXX00    original & mask
or  000000XX    data right-shift by write_lhs
    XXXXXXXX

### 重寫為同樣功能但效率更高的實作
#### 改善 bit_mask 的實作
####
:::info
unaligned/aligned memory
memcpy()
:::
####
:::info
TODO
:::
### Linux 核心對於 `bit_cpy` 的實作
:::info
TODO
:::

---

## 測驗 4
### 解釋字串駐留 (String Interning) 運作原理
https://hackmd.io/@sysprog/linux2021-quiz2#%E6%B8%AC%E9%A9%97-4
:::info
TODO
:::
### 解釋程式碼運作原理
#### `cstr.h`
**`enum`**

enum {
    CSTR_PERMANENT = 1,
    CSTR_INTERNING = 2,
    CSTR_ONSTACK = 4,
};

* `CSTR_PERMANENT` - 表示字串儲存在 heap 的狀態。
* `CSTR_INTERNING` - 表示儲存字串的空間作為 string interning 使用的狀態。
* `CSTR_ONSTACK` - 表示字串儲存在 stack 的狀態。

**`struct`**

typedef struct __cstr_data {
    char *cstr;
    uint32_t hash_size;
    uint16_t type;
    uint16_t ref;
} * cstring;

* `cstr` - 儲存字串的空間。
* `hash_size` - 當字串的狀態為 `CSTR_ONSTACK`，`hash_size` 的值為字串的長度 (`size`)，否則其值為 hash values (`hash`)。
* `type` - 當前字串儲存在的空間的狀態。
* `ref` - reference counting。

`cstring` 為一個指向 `struct __cstr_data` 結構的指標。

typedef struct __cstr_buffer {
    cstring str;
} cstr_buffer[1];

* str - `cstring` type，為指向 `struct __cstr_data` 結構的指標。

**Function-like macro: `CSTR_BUFFER()`**

#define CSTR_BUFFER(var)                                                      \
    char var##_cstring[CSTR_STACK_SIZE] = {0};                                \
    struct __cstr_data var##_cstr_data = {var##_cstring, 0, CSTR_ONSTACK, 0}; \
    cstr_buffer var;                                                          \
    var->str = &var##_cstr_data;

:::info
Reference: C99 Standard - §6.10.3.3 The ## operator
:::
創造一個 `cstring` 指標結構的 buffer (`cstr_buffer`)，其字串指標成員 `cstr` 指向從 stack 上抓取的大小為 `CSTR_STACK_SIZE * sizeof(char)` 的一段空間，`hash_size` (在此為 `size`) 以及 `ref` (reference counting) 此時皆設為 `0`，狀態設為 `ON_STACK`。

**Function-like macro: `CSTR_LITERAL()`**

#define CSTR_LITERAL(var, cstr)                                               \
    static cstring var = NULL;                                                \
    if (!var) {                                                               \
        cstring tmp = cstr_clone("" cstr, (sizeof(cstr) / sizeof(char)) - 1); \
        if (tmp->type == 0) {                                                 \
            tmp->type = CSTR_PERMANENT;                                       \
            tmp->ref = 0;                                                     \
        }                                                                     \
        if (!__sync_bool_compare_and_swap(&var, NULL, tmp)) {                 \
            if (tmp->type == CSTR_PERMANENT)                                  \
                free(tmp);                                                    \
        }                                                                     \
    }

首先，被宣告的變數 `var` 為 static variable，擁有完整的程式執行生命週期 (life cycle)。
之後，被宣告的 `cstring` 變數 `tmp` 會接住 `cstr_clone()` 的回傳值，其中 `cstr_clone()` 會複製 `cstr` 字串並對此做 string interning，詳細情形會在 **`cstr.c`** 做說明。
而有關 `__sync_bool_compare_and_swap()` GNU C Extentions 的使用，則為考量到多執行緒的狀況下，因 `cstr_clone()` 執行過程中有機會動態配置記憶體，可能因此造成 memory leak 的問題。
:::info
Reference: [GNU C extensions - §5.44 Built-in functions for atomic memory access](https://gcc.gnu.org/onlinedocs/gcc-4.1.1/gcc/Atomic-Builtins.html)
:::

**Function-like macro: `CSTR_CLOSE()`**

#define CSTR_CLOSE(var)               \
    do {                              \
        if (!(var)->str->type)        \
            cstr_release((var)->str); \
    } while (0)

被傳進來的參數 `var` 預期的值為指向結構體 `struct __cstr_buffer` 的指標。而 `do{ ... } while (0)` 會強制讓整個迴圈內的行為只留在迴圈內，並且只執行一次。
`cstr_release()` 會釋放掉在 `cstring` 結構內的成員變數 `cstr` 被動態配置的記憶體。
有關 `var->str->type` 的值為 `0` 的狀況以及 `cstr_release()` 的作用會在 `cstr.c` 詳細說明。

#### `cstr.c`
**`struct`**

struct __cstr_node {
    char buffer[CSTR_INTERNING_SIZE];
    struct __cstr_data str;
    struct __cstr_node *next;
};

* `buffer` - 存成員 `str` 內部的字串值的 buffer。
* `str` - `struct __cstr_data` 型別，內容包含字串值，記憶體存放區域及狀態，hash value or size，以及 reference counting。
* `next` - 指向下一個 `__cstr_node` 結構的指標。

struct __cstr_pool {
    struct __cstr_node node[INTERNING_POOL_SIZE];
};

* `node` - 為 `__cstr_node` 結構體的陣列，陣列大小為 `INTERNING_POOL_SIZE`。

此結構存在的目的是為了讓 `malloc()` 在動態配置記憶體時，能夠配置出一段連續的記憶體空間。讓在 string interning 的過程中，實現 cache 機制優化效能，也避免了過多次 `malloc()` 造成 [memory fragmentation](https://www.researchgate.net/publication/295010953_Dynamic_Memory_Allocation_and_Fragmentation) 的問題。

struct __cstr_interning {
    int lock;
    int index;
    unsigned size;
    unsigned total;
    struct __cstr_node **hash;
    struct __cstr_pool *pool;
};

* `lock` - 考量多執行緒的情況，需要此成員變數來避免存取字串過程中造成錯誤。
* `index` - 存 `pool` 指向的陣列的某個 index。
* `size` - 存目前 hash table 的大小。
* `total` - 存目前被駐留的字串 (interned strings) 的數量。
* `hash` - 為一個指向 `struct __cstr_node` 結構體的指標的指標。在 string interning 過程中會連接 `pool` 裡面的 node 而逐漸成為一個以 `struct __cstr_node` 指標為單位所組成的 hash table。
* `pool` - 為一個指向 `struct __cstr_pool` 結構體的指標，其成員存著一塊連續的記憶體 (`node[INTERNING_POOL_SIZE]`)。而這塊連續的空間之後會在 string interning 的過程中，逐漸成為一個 hash table。

**global variable**

static struct __cstr_interning __cstr_ctx;

**函式： `xalloc()`**

static void *xalloc(size_t n)
{
    void *m = malloc(n);
    if (!m)
        exit(-1);
    return m;
}

動態配置記憶體。
`xalloc()` 用 `if` 條件式包裝 `malloc()`，讓 `malloc()` 若在動態配置記憶體失敗回傳 `NULL` 時，直接終止整支程式。

**函式：`insert_node()`**

static inline void insert_node(struct __cstr_node **hash,
                               int sz,
                               struct __cstr_node *node)
{
    uint32_t h = node->str.hash_size;
    int index = h & (sz - 1);
    node->next = hash[index];
    hash[index] = node;
}

將 `node` 放進 hash table `hash` 裡面。
其中 `h & (sz - 1)` 可以視為是 `h % sz`，目的是為了確保 hash value 沒有越界存取記憶體，造成 segmentation fault。但是此舉也有可能造成不同字串有著相同的 hash value，發生碰撞。

**函式： `expand()`**

static void expand(struct __cstr_interning *si)
{
    unsigned new_size = si->size * 2;
    if (new_size < HASH_START_SIZE)
        new_size = HASH_START_SIZE;

    struct __cstr_node **new_hash =
        xalloc(sizeof(struct __cstr_node *) * new_size);
    memset(new_hash, 0, sizeof(struct __cstr_node *) * new_size);

    for (unsigned i = 0; i < si->size; ++i) {
        struct __cstr_node *node = si->hash[i];
        while (node) {
            struct __cstr_node *tmp = node->next;
            insert_node(new_hash, new_size, node);
            node = tmp;
        }
    }

    free(si->hash);
    si->hash = new_hash;
    si->size = new_size;
}

增加 hash table size，每次增加一倍。
注意新宣告的 `unsigned` type 的變數 `new_size`，有可能在增加一倍的時候 overflow，所以必須要加上這段程式碼：

if (new_size < HASH_START_SIZE) new_size = HASH_START_SIZE;

在成功動態配置一段新的記憶體之後，將舊的 hash table 指向的每個 node 放進這塊新的空間裡面，再將舊的 hash table 佔的空間 `free()` 掉，然後再讓 `si->hash` 指向這段新的空間，成為一個新的 hash table。

**函式： `interning()`**

static cstring interning(struct __cstr_interning *si,
                         const char *cstr,
                         size_t sz,
                         uint32_t hash)

實現字串駐留 (string interning) 的實作。

if (!si->hash) return NULL;

當實現字串駐留 (string interning) 裡面的 hash table 為空，無法找到 interned strings，回傳 `NULL`。

int index = (int) (hash & (si->size - 1));
struct __cstr_node *n = si->hash[index];

`(int) (hash & (si->size - 1))` 可以視為是 `(int) (hash % si->size)`，此舉確保 hash value 不會超過 hash table 的 index 的最大值，同時確保與函式 `insert_node()` 在實際決定存取 hash table 的 index 值時，有著同樣的規則。

while (n) {
    if (n->str.hash_size == hash) {
        if (!strcmp(n->str.cstr, cstr))
            return &n->str;
    }
    n = n->next;
}

`while()` 迴圈內的行為是，找到實際真正對應的 interned string。
由於先前在 `insert_node()` 的實作，發現有可能發生 hash value 的碰撞，故而發生碰撞的資料會存成一個 singly linked list 連接在該 hash table 對應的位置。因此需要迴圈內跑完整個 linked list 找出實際真正對應的 interned string。
若成功找到對應的 interned string，則回傳該 interned string 的記憶體參照 (reference)。

// 80% (4/5) threshold
if (si->total * 5 >= si->size * 4)
    return NULL;

若先前沒有成功找到對應的 interned string，且 hash table 內節點密度太高，有可能發生 hash value 碰撞的次數太多(在這裡的情況是，interned string 的節點個數為 hash table 能容納的大小的 80%)，有可能因此影響到 hash 的效率，所以不宜再增加 interned string 的節點數，於是回傳 `NULL`。
但是此方法無法保證 hash table 內，interned string 節點皆是散在 hash table 的各處，此判斷方式並不嚴謹。

if (!si->pool) {
    si->pool = xalloc(sizeof(struct __cstr_pool));
    si->index = 0;
}
n = &si->pool->node[si->index++];
memcpy(n->buffer, cstr, sz);
n->buffer[sz] = 0;

cstring cs = &n->str;
cs->cstr = n->buffer;
cs->hash_size = hash;
cs->type = CSTR_INTERNING;
cs->ref = 0;

n->next = si->hash[index];
si->hash[index] = n;

return cs;

若先前沒有成功找到對應的 interned string，且 hash table 內的節點的密度沒有太大，則允許 hash table 加入更多的 interned string 節點。
首先確認可被拿來使用的空間 `pool` 是否為空，若為空，則動態配置記憶體並初始化其對應資料 (`si->index`)。之後拿這段空間，以`__cstr_node` 為單位，來當作即將放入 hash table 的節點。
由於先前已經有確認在 interned string 的節點個數為 hash table 大小的 80% 時會回傳 `NULL`，所以 `si->index++` 不會因此越界存取記憶體而造成 segmentation fault。
再加入 interned string 節點至 hash table 的過程中，首先先複製傳進來的字串參數至 buffer (`n->buffer`) 中，結尾要加上 null terminator `'\0'` (`0`)，之後再將真正要存 interned string 的字串指標 (`n->str->cstr`) 指向該 buffer (`n->buffer`) 的位置，之後再 interned string 的節點結構的內部成員 `cs->type` 狀態賦值為 `CSTR_INTERNING`，同時因為是新增至 hash table 的節點，所以 reference count `cs->ref` 為 `0`。
最後才真正將該節點放入 hash table 內，讓該 interned string 節點指向 hash table 對應的位置。

**函式： `cstr_interning()`**

static cstring cstr_interning(const char *cstr, size_t sz, uint32_t hash)
{
    cstring ret;
    CSTR_LOCK();
    ret = interning(&__cstr_ctx, cstr, sz, hash);
    if (!ret) {
        expand(&__cstr_ctx);
        ret = interning(&__cstr_ctx, cstr, sz, hash);
    }
    ++__cstr_ctx.total;
    CSTR_UNLOCK();
    return ret;
}

函式 `interning()` 的包裝以及，考量多執行緒環境下的字串駐留 (string interning) 實現。
當第一次實行字串駐留 (string interning) `interning()` 失敗，回傳 `NULL`，則呼叫 `expand()` 將 hash table 擴大一倍，再次實行字串駐留 (string interning) 呼叫 `interning()`。
:::danger
假使 total 變數的意義是記錄 interned strings 的個數，那麼這裡 `++__cstr_ctx.total` 便不應該出現在此 `cstr_interning()` 函式中，因為 `interning()` 函式有可能回傳的值是已經被駐留的字串 (interned strings) 在 hash table 裡的記憶體位置參照，而非新增至 hash table 裡面的 interned string 節點。
所以 `++__cstr_ctx.total` 這行 expression 應該要放在 `interning()` 函式中。

static cstring cstr_interning(const char *cstr, size_t sz, uint32_t hash)
{
    ...
-   ++__cstr_ctx.total;
    ...
}

static cstring interning(struct __cstr_interning *si,
                         const char *cstr,
                         size_t sz,
                         uint32_t hash)
{
    ...
    n->next = si->hash[index];
    si->hash[index] = n;
+   ++__cstr_ctx.total;
}

:::
**函式： `hash_blob()`**

static inline uint32_t hash_blob(const char *buffer, size_t len)
{
    const uint8_t *ptr = (const uint8_t *) buffer;
    size_t h = len;
    size_t step = (len >> 5) + 1;
    for (size_t i = len; i >= step; i -= step)
        h = h ^ ((h << 5) + (h >> 2) + ptr[i - 1]);
    return h == 0 ? 1 : h;
}

此為打散資料分布至 hash table 的 hash function。
:::info
TODO: explain this hash function.
:::

**函式： `cstr_clone()`**

cstring cstr_clone(const char *cstr, size_t sz)
{
    if (sz < CSTR_INTERNING_SIZE)
        return cstr_interning(cstr, sz, hash_blob(cstr, sz));
    cstring p = xalloc(sizeof(struct __cstr_data) + sz + 1);
    if (!p)
        return NULL;
    void *ptr = (void *) (p + 1);
    p->cstr = ptr;
    p->type = 0;
    p->ref = 1;
    memcpy(ptr, cstr, sz);
    ((char *) ptr)[sz] = 0;
    p->hash_size = 0;
    return p;
}

傳入要被讀取字串的資料的副本，確認是否符合 interned string 的大小，再決定要不要呼叫 `cstr_interning()`。若傳入的字串沒有做字串駐留 (string interning)，則動態配置記憶體，賦予其對應的 `cstring` 型別結構體，再回傳其地址。
:::info
這裡 `cstring p = xalloc(sizeof(struct __cstr_data) + sz + 1);` 可以保證記憶體連續，所以在存取此 `cstring` 型別比起額外 `malloc()` 或者 `strdup()` 動態配置記憶體給 `p->cstr`，可以增加效能。
:::
:::warning
因為已經有 `xalloc()` 包裝 `malloc()`，所以當 `malloc()` 回傳 `NULL` 時，就會直接終止程式，因此就不需要額外再關注 `p` 的值是否為 `NULL`。

cstring cstr_clone(const char *cstr, size_t sz)
{
    ...
    cstring p = xalloc(sizeof(struct __cstr_data) + sz + 1);
-   if (!p)
-       return NULL;
    ...
    return p;
}

但是若再多執行緒的情形下是否需要此 `if` 條件，尚待釐清。

cstring cstr_clone(const char *cstr, size_t sz)
{
    ...
-   void *ptr = (void *) (p + 1);
+   char *ptr = (char *) (p + 1);
    ...
}

此處的 `(void *)` 型別應改為 `(char *)`，但是其輸出卻與型別不同沒有什麼差別，且觀察 `p` 後面不管加何種數值，輸出皆為一致。
實驗： **`test.c`**

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <string.h>

typedef struct __cstr_data {
    char *cstr;
    uint32_t hash_size;
    uint16_t type;
    uint16_t ref;
} * cstring;

cstring cstr_clone(const char *cstr, size_t sz)
{
    cstring p = malloc(sizeof(struct __cstr_data) + sz + 1);
    void *ptr = (void *) (p + 1);
    p->cstr = ptr;
    p->type = 1;
    p->ref = 2;
    memcpy(ptr, cstr, sz);
    ((char *) ptr)[sz] = 0;
    p->hash_size = 3;
    return p;
}

cstring cstr_clone2(const char *cstr, size_t sz)
{
    cstring p = malloc(sizeof(struct __cstr_data) + sz + 1);
    char *ptr = (char *) (p + 9999);
    p->cstr = ptr;
    p->type = 1;
    p->ref = 2;
    memcpy(ptr, cstr, sz);
    ((char *) ptr)[sz] = 0;
    p->hash_size = 3;
    return p;
}

int main(int argc, char *argv[])
{
    char test[] = "hello world!";
    int len = strlen(test);
    cstring p = cstr_clone(test, len);
    cstring p2 = cstr_clone(test, len);
    printf("%d %d %d %s\n", p->hash_size, p->ref, p->type, p->cstr);
    printf("%d %d %d %s\n", p2->hash_size, p2->ref, p2->type, p2->cstr);
    return 0;
}

$ gcc test.c
$ ./a.out
3 2 1 hello world!
3 2 1 hello world!

尚待釐清原因。
// 推測指向字串的指標可為非連續記憶體
實驗：
printf("%p")...
:::
**函式： `cstr_grab()`**

cstring cstr_grab(cstring s)
{
    if (s->type & (CSTR_PERMANENT | CSTR_INTERNING))
        return s;
    if (s->type == CSTR_ONSTACK)
        return cstr_clone(s->cstr, s->hash_size);
    if (s->ref == 0)
        s->type = CSTR_PERMANENT;
    else
        __sync_add_and_fetch(&s->ref, 1);
    return s;
}

此函式為抓取一個 `cstring` 型別，為指向 `struct __cstr_data` 結構體的指標，判斷其內部資料後，對其做相對應的處理。
檢查此結構體裡面的成員 `type`，分為以下的 case：
* 若 `type` 是 `CSTR_PERMANENT` 或是 `CSTR_INTERNING`，意義上，為被動態配置記憶體但因字串大小過大而沒有做字串駐留 (string interning) 的字串，或是已經字串駐留的字串 (interned string)，則回傳 `s` 指標本身。
* 若 `type` 是 `CSTR_ONSTACK`，則代表 `__cstr_data` 結構體本身是作為一個 buffer 存在，因此呼叫 `cstr_clone()` 並回傳其回傳的 `cstring` 指標。
* 當 `type` 為 `0` 時，且 `ref` (reference count) 為 `0` 時，將 `type` 賦值為 `CSTR_PERMANENT`。
* 當 `type` 為 `0` 時，且 `ref` (reference count) 不為 `0`，則將 `ref` 的值 + 1。

**函式： `cstr_release()`**

void cstr_release(cstring s)
{
    if (s->type || !s->ref)
        return;
    if (__sync_sub_and_fetch(&s->ref, 1) == 0)
        free(s);
}

此函式會將符合條件的 `cstring` 指標指向的結構體，釋放其被動態配置的記憶體。
符合的條件如下：
* 其成員變數 `type` 必須為 `0`。
* 其成員變數 `ref` (reference counting) 被 `-1` 後必須為 `0`。

若 `type` 為 `0` 但 `ref` (reference count) 不為 `0`，則將 `ref` 的值 `-1`。
:::warning
但上述程式碼產生一個問題：若傳進來的 `cstring s` 一開始的 `type` 為 `0` 且 `ref` 為 `0` 時，就會直接 `return`，但是若只觀察在 `quiz2` 的程式碼，直覺上不會發生這種情況，不知此設計基於何種考量？是否為多執行緒上的考量？
:::

**函式： `cstr_hash()`**

static size_t cstr_hash(cstring s)
{
    if (s->type == CSTR_ONSTACK)
        return hash_blob(s->cstr, s->hash_size);
    if (s->hash_size == 0)
        s->hash_size = hash_blob(s->cstr, strlen(s->cstr));
    return s->hash_size;
}

對於傳進來 `cstring s`，判斷其內部成員的資料後，決定並回傳 `hash_size` 的值。
當傳進來的 `cstring s` 字串的狀態為 `CSTR_ONSTACK`，代表此結構體的 `hash_size` 的值為字串的長度 (`size`)，而非 hash values (`hash`)，因此呼叫 `hash_blob()` 計算並回傳其 hash value。
如果 `(hash_size == 0)` 成立，則代表傳進來的字串會是字串大小過大而沒有做字串駐留 (string interning) 的字串結構體。不會是作為 buffer 的結構體是因為 buffer 本身狀態是 `CSTR_ONSTACK`，所以會是上一個條件判斷的 case。，此情形亦會計算並回傳其 hash value。

**函式： `cstr_equal()`**

int cstr_equal(cstring a, cstring b)
{
    if (a == b)
        return 1;
    if ((a->type == CSTR_INTERNING) && (b->type == CSTR_INTERNING))
        return 0;
    if ((a->type == CSTR_ONSTACK) && (b->type == CSTR_ONSTACK)) {
        if (a->hash_size != b->hash_size)
            return 0;
        return memcmp(a->cstr, b->cstr, a->hash_size) == 0;
    }
    uint32_t hasha = cstr_hash(a);
    uint32_t hashb = cstr_hash(b);
    if (hasha != hashb)
        return 0;
    return !strcmp(a->cstr, b->cstr);
}

傳進來參數是 `cstring` 型別的 `a`、`b`，為指向 `struct __cstr_data` 結構體的指標，此函式會判斷兩個指標中，結構體內的字串是否相同。處理方式會分幾個 case，詳述如下：
* 若傳進來的 `a`、`b` 指標為同一個指標，則 `return 1` 代表字串內容相同。
* 若傳進來的 `a`、`b` 皆為 interned string，則皆為 hash table 內的節點，因此字串內容不會是一樣的，所以 `return 0`。
* 若傳進來的 `a`、`b` 其結構體內所存的字串皆在 stack 上，`type ` 皆為 `CSTR_ONSTACK`，則兩個結構體內的 `hash_size` 紀錄的會是字串的長度 (`size`)，而非 hash values (`hash`)，因此若兩者的長度不同，便可以得知兩個字串的內容不相符。若兩者長度相同，則交由 `memcmp()` 逐 byte (`unsigned char`) 檢查兩者是否相同。
* 若傳進來的 `a`、`b` 皆不符合上述的 case，則交由 hash function 比對兩者 hash 值，若 hash 值不相同，則 `return 0`。
* 最後若上述的所有 case 沒有一個是符合的，才交由 `strcmp()` 比對字串並回傳結果。

:::info
`memcmp()` vs `strcmp()`
// TODO
reference:
[What is the difference between memcmp, strcmp and strncmp in C? from Stack Overflow](https://stackoverflow.com/questions/13095513/what-is-the-difference-between-memcmp-strcmp-and-strncmp-in-c)
[memcmp versus strcmp, why is memcmp faster? from Tek-Tips.COM](https://www.tek-tips.com/viewthread.cfm?qid=1323083)

:::

**函式： `cstr_cat2()`**

static cstring cstr_cat2(const char *a, const char *b)
{
    size_t sa = strlen(a), sb = strlen(b);
    if (sa + sb < CSTR_INTERNING_SIZE) {
        char tmp[CSTR_INTERNING_SIZE];
        memcpy(tmp, a, sa);
        memcpy(tmp + sa, b, sb);
        tmp[sa + sb] = 0;
        return cstr_interning(tmp, sa + sb, hash_blob(tmp, sa + sb));
    }
    cstring p = xalloc(sizeof(struct __cstr_data) + sa + sb + 1);
    if (!p)
        return NULL;

    char *ptr = (char *) (p + 1);
    p->cstr = ptr;
    p->type = 0;
    p->ref = 1;
    memcpy(ptr, a, sa);
    memcpy(ptr + sa, b, sb);
    ptr[sa + sb] = 0;
    p->hash_size = 0;
    return p;
}

// duplicate & concat strings, case for heap allocated strings. Also interns the concatenated string after duplicate & concat is done.

**函式： `cstr_cat()`**

cstring cstr_cat(cstr_buffer sb, const char *str)
{
    cstring s = sb->str;
    if (s->type == CSTR_ONSTACK) {
        int i = s->hash_size;
        while (i < CSTR_STACK_SIZE - 1) {
            s->cstr[i] = *str;
            if (*str == 0)
                return s;
            ++s->hash_size;
            ++str;
            ++i;
        }
        s->cstr[i] = 0;
    }
    cstring tmp = s;
    sb->str = cstr_cat2(tmp->cstr, str);
    cstr_release(tmp);
    return sb->str;
}

// duplicate & concat strings, case for ONSTACK buffer.

### 對應測試程式
// TODO
:::danger
還沒改之前，用 valgrind 測試是否有 memory leak

$ valgrind --leak-check=full ./cstr
==45589== Memcheck, a memory error detector
==45589== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==45589== Using Valgrind-3.15.0 and LibVEX; rerun with -h for copyright info
==45589== Command: ./cstr
==45589== 
equal
==45589== 
==45589== HEAP SUMMARY:
==45589==     in use at exit: 57,472 bytes in 2 blocks
==45589==   total heap usage: 3 allocs, 1 frees, 58,496 bytes allocated
==45589== 
==45589== LEAK SUMMARY:
==45589==    definitely lost: 0 bytes in 0 blocks
==45589==    indirectly lost: 0 bytes in 0 blocks
==45589==      possibly lost: 0 bytes in 0 blocks
==45589==    still reachable: 57,472 bytes in 2 blocks
==45589==         suppressed: 0 bytes in 0 blocks
==45589== Reachable blocks (those to which a pointer was found) are not shown.
==45589== To see them, rerun with: --leak-check=full --show-leak-kinds=all
==45589== 
==45589== For lists of detected and suppressed errors, rerun with: -s
==45589== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)

有 memory leak，要改進．
TODO: rerun the valgrind for adding the option --leak-check=full --show-leak-kinds=all -s
for tracing the memory leak function.
:::

### 考量多執行緒實現字串駐留 (String Interning)
:::info
TODO
:::
### 分析效能表現
:::info
TODO
:::