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

## 測驗1
### COND1 & COND2
閱讀 get_middle 程式碼，並將巨集 list_for_each 解開，其程式碼如下:

static list_ele_t *get_middle(struct list_head *list)
{
    struct list_head *fast = list->next, *slow;
    for (slow = (list)->next; slow != (list); slow = slow->next) {
        if (COND1 || COND2)
            break;
        fast = fast->next->next;
    }
    return list_entry(TTT, list_ele_t, list);
}

可以發現每當 slow 走 n 個節點，fast 就會走 n+2 個節點，考慮到是找到中間的節點，將 linked list 為奇數以及雙數的情況都畫出來

1. 雙數 linked list, slow 移動了1個節點到達節點3，fast 移動了2個節點到達節點4

digraph {
    node [shape=box]
    
    head -> 6 [dir=both, label="     "]
    6->3 [dir=both]
    3->4 [dir=both]
    4->5 [dir=both]
    5->head [dir=both]
    slow -> 3
    fast -> 4

    {rank=same; 3, 4, 5, 6, head}
}

2. 單數 linked list, slow 移動了2個節點到達節點4，fast 移動了4個節點到達節點7

digraph {
    node [shape=box]
    head -> 6 [dir=both, label="     "]
    6->3 [dir=both]
    4->5 [dir=both]
    7->head [dir=both]
    3->4 [dir=both]
    5->7 [dir=both]
    slow-> 4
    fast->7
    {rank=same; head, 6, 3, 4, 5, 7}
}

所以如果要將以上兩種情況都概括，`COND1` 和 `COND2` 必須分別為 `fast->next == list`, `fast->next->next == list`

## TTT
根據上方作業敘述，傳入成員位址，型態以及名稱給 list_entry，它會回傳當下 struct 的位址。我們需要知道當下 slow 指向的節點位址，故 TTT 應為 `slow`

## MMM
先解析 list_cut_position 的作用:
註解指出，list_cut_position，會從 head_from 指向的 linked list，在 node 點切開，並讓 head_to 接收另一段 linked list，如下圖

digraph {
    node [shape=box]
    head_from -> 6 [dir=both, label="     "]
    6->3 [dir=both]
    "node"->5 [dir=both]
    7->head_from [dir=both]
    5->7 [dir=both]
    3->"node" [dir=both]
    head_from_first->6
    head_to
    {rank=same; head_from, 6, 3, 5, 7, "node"}
}

head_from->next = node->next;
head_from->next->prev = head_from;

digraph {
    node [shape=box]
    6->head_from [label="     "]
    head_from->5 [dir=both]
    6->3 [dir=both]
    "node"->5 
    7->head_from [dir=both]
    5->7 [dir=both]
    3->"node" [dir=both]
    
    head_from_first->6
    head_to
    {rank=same; 6, 3, 5, 7, "node"}
}

head_to->prev = node;
node->next = head_to;

digraph {
    node [shape=box]
    6->head_from [label="     "]
    head_from->5 [dir=both]
    6->3 [dir=both]

    7->head_from [dir=both]
    5->7 [dir=both]
    3->"node" [dir=both]
    
    head_from_first->6
    "node"->head_to [dir=both]

    {rank=same; 6, 3, 5, 7, "node"}
}

head_to->next = head_from_first;
head_to->next->prev = head_to;

digraph {
    node [shape=box]

    head_from->5 [dir=both,  label="     "]
    6->3 [dir=both]

    7->head_from [dir=both]
    5->7 [dir=both]
    3->"node" [dir=both]
    
    head_from_first->6
    "node"->head_to [dir=both]
    head_to->6 [dir=both]

    {rank=same; 6, 3, 5, 7, "node"}
}

其參數MMM必須是要切開的節點，也就是透過 get_middle 得到的 struct 位址，而 get_middle 的參數要是 list_head 的指標型態，故要得到當下 struct 的地址，程式碼應為 `get_middle(&q->list)`

:::warning
TODO:
解釋上述程式碼運作原理，指出改進空間並著手實作
研讀 Linux 核心的 lib/list_sort.c 原始程式碼，學習 sysprog21/linux-list 的手法，將 lib/list_sort.c 的實作抽離為可單獨執行 (standalone) 的使用層級應用程式，並設計效能評比的程式碼，說明 Linux 核心的 lib/list_sort.c 最佳化手法
將你在 quiz1 提出的改進實作，和 Linux 核心的 lib/list_sort.c 進行效能比較，需要提出涵蓋足夠廣泛的 benchmark
:::

---

## 測驗2

:::warning
TODO:
1.解釋上述程式碼運作原理
2. 在 The Linux Kernel API 頁面搜尋 “power of 2”，可見 is_power_of_2，查閱 Linux 核心原始程式碼，舉例說明其作用和考量，特別是 round up/down power of 2 。特別留意 `__roundup_pow_of_two` 和 `__rounddown_pow_of_two` 的實作機制
3. 研讀 slab allocator，探索 Linux 核心的 slab 實作，找出運用 power-of-2 的程式碼和解讀
:::