# 2021q1 Week1/2/3/4

:::warning
課堂問答簡記
請填入你的 GitHub 帳號名稱
:::

## Uduru0522
:question: `linux/list.h` 的 `list_swap()` 實做原理 ？

/**
 * list_swap - replace entry1 with entry2 
 *             and re-add entry1 at entry2's position
 * @entry1: the location to place entry2
 * @entry2: the location to place entry1
 */
static inline void list_swap(struct list_head *entry1,
			     struct list_head *entry2)
{
	struct list_head *pos = entry2->prev;

	list_del(entry2);
	list_replace(entry1, entry2);
	if (pos == entry1)
		pos = entry2;
	list_add(entry1, pos);
}

:thinking_face:
:::spoiler {state="open"} **先試著把一些函式展開 ：**

static inline void list_swap(struct list_head *entry1,
			      struct list_head *entry2)
{
    struct list_head *pos = entry2->prev;

    /* list_del(entry2); */{
        /* __list_del_entry(entry2); */{
            if (!__list_del_entry_valid(entry2))
		        return;
            /* __list_del(entry2->prev, entry2->next); */{
                entry2->next->prev = entry2->prev;
                WRITE_ONCE(entry2->prev->next, entry2->next);
            }
        }
        entry2->next = LIST_POISON1;
        entry2->prev = LIST_POISON2;
    }
    
    /* list_replace(entry1, entry2); */{
        entry2->next = entry1->next;
        entry2->next->prev = entry2;
        entry2->prev = entry1->prev;
        entry2->prev->next = entry2;
    }
    
    if (pos == entry1)
        pos = entry2;
        
    /* list_add(entry1, pos); */
        /* __list_add(entry1, pos, pos->next) */{
            if (!__list_add_valid(entry1, pos, pos->next))
                return;
            pos->next->prev = entry1;
            entry1->next = pos->next;
            entry1->prev = pos;
            WRITE_ONCE(pos->next, entry1);
        }
}

:::

+ Line 11,12: 將 `entry2` 的前後接上，其中 `WRITE_ONCE()` 可以防止賦值的指令被拆分成多個小指令，或是在多執行緒被其他函式調用時時造成錯誤。
> `#define WRITE_ONCE(var, val) (*((volatile typeof(val) *)(&(var))) = (val))`

+ Line 15,16: 將 `entry2` 自 list 之中分離出來，經過 `__list_del_entry_valid()` 確認資料可用之後, 把當下 `entry2` 的 `prev` 以及 `next` 設為預設的 dead pointer (`LIST_POISON1` 以及 `LIST_POISON1`)，當調用 `LIST_POISON` 時會導致 Page Fault。

+ Line 20-23: 調整指標至如下形式

digraph G{
    rankdir = LR
    splines=ortho
    
    node[
        style = filled;
        shape = record;
        color = darkolivegreen2;
    ] entry1 entry2
    
    node[color = gray73, shape = box] e1_next e2_next e1_prev e2_prev
    node[color = lightgoldenrod1, shape = cds] pos
    node[style=invis, shape=record] ivs1 ivs2
    
    {rank = same; e1_prev; e2_prev; ivs1;} 
    {rank = same; entry1; entry2;} 
    {rank = same; e1_next; e2_next; ivs2;}
    
    e2_prev -> e2_next;
    e2_prev -> e1_prev -> ivs1 [style=invis];
    e2_next -> e1_next -> ivs2 [style=invis];
    e1_prev -> entry1 -> e1_next;
    e1_prev -> entry2 -> e1_next;
    e1_next -> entry2 -> e1_prev [constraint=false];
    pos -> e2_prev [shape=none];
}

+ Line 31-36: 利用 `list_add(new, prev, next)` 將新節點插入 `prev` 及 `next` 之間的行為，將 `entry1` 加入至原先 `entry2` 所在地點。

+ Line 26,27 用以對應傳入的兩個 node 是 `XXX` -> `entry1` -> `entry2` -> `YYY` 的情況。

---

## Nahemah1022
### 1. 在 [lab0](https://hackmd.io/B3s8kNxJSG6IdbE7EHBMSw) 作業中的 merge_sort 有什麼可以改進的地方
- merge sort 本身
- 程式中的註解太過簡短，可以針對 `if` 與 `else` 兩個區段分別註解會更加清晰
- 變數的命名也不夠直覺，`indirect` 的目的無法直接望文生義
- 其他做法
- 有嘗試過使用 quick sort 算法，但因為測試資料中含有 quick sort 的 worst case，造成效能下降無法通過 qtest
:::warning
TODO：弄清楚 qtest 如何檢驗效能
:::

### 2. 在 qtest 中 [Address Sanitize 的問題與解決方](https://hackmd.io/B3s8kNxJSG6IdbE7EHBMSw#%E4%BA%8C%E3%80%81%E4%BF%AE%E6%AD%A3-Address-Sanitize-%E4%B8%AD%E7%9A%84-qtest-%E9%8C%AF%E8%AA%A4)
- 存取到超出 `bool` 本身一個 byte 大小的空間造成錯誤
- 可以將所有 `bool` 都改成 `int`，但會需要連帶修改其他東西，不好維護
- 我的方法是直接分成兩個不同參數的 function，可以解決問題但可能會讓兩個 fucniton 的內容過於相似，應有更好的辦法

---

## RZHuangJeff
### 1. 在[quiz3](https://hackmd.io/@sysprog/linux2021-quiz3)中`xs_trim`如何比對欲移除的字元
* 問題
由於`xs_trim`支援讓呼叫者自訂欲剪除的字元，因此若欲排除的字元太多使用逐一比對的話將造成執行效能低落，因此引入另外的方法。
* 解決方法
透過查表的方式直接確認是否欲移除該字元。

在程式碼中，可以看到一個長度為32的`mask`陣列，`mask`陣列的初始值為0，並且可透過兩個macro: `set_bit`及`check_bit`進行建表及查詢。在通常的執行環境中，單一個位元所站的空間為1個byte，而程式碼中`mask`中元素的型態為`uint8_t`，因此可以將所有不同的字元對應到`mask`中的不同個bit，而這個工作由`set_bit`完成，具體的內容如下:

#define set_bit(byte) (mask[(uint8_t) byte / 8] |= 1 << (uint8_t) byte % 8)

可以發現到`set_bit`將給定的`byte`分成上5位元及下3位元，分別成為存取`mask`的索引及其中的第幾個位元。以`byte = 'A'`為例: A的ascii碼為`0x41`，則存取`mask`的索引為8，並且其對應到的是`mask[8]`中的第2個字元(1 << 1 是2)。找到對應的位元後則透過or將該位元設成1。
表建好後，透過`check_bit`在常數時間內查詢該表，便可得知該字元是否為欲刪除之字元，`check_bit`的具體內容為:

#define check_bit(byte) (mask[(uint8_t) byte / 8] & 1 << (uint8_t) byte % 8)

由上可知，只要透過與`set_bit`相同之方式找到`mask`中對應的位元，並且確認該位元是否為1。

### 2. 為何`xs_new`要分兩種方式儲存短字串及長字串
在`xs_new`中是將長度小於 16 的字串放在 stack，並為長度大於 16 的字串分配 heap 上的空間。這樣做的原因主要是效能考量，有以下兩點:
1. 分配 heap 空間較直接儲存於 stack 上更費時，因此為短字串分配 heap 空間的時間開銷較大
2. stack 的較 heap 接近先前已使用過的位址，如此可善用 cache 的 spatial locality

---

## hankluo6

https://hackmd.io/@hankluo6/2021q1quiz1

### 1. quiz2 的 get_middle 方式遇到的 worst case

上課時將 merge sort 想成 quick sort，merge sort 的 worst case 不應該為不平衡的切割，如果為不平衡切割的話，複雜度應為：

$$
T(n) = T(n - 1) + cn=T(1)+\frac{(n-1)}{n}-\frac{(n-1)(n-2)}{2}=O(n^2)
$$

這樣就與 quick sort 一樣為 $O(n^2)$，但 merge sort 的概念為 divide and conquer，worst case 應為 $O(nlogn)$，演算法需以 list 的中心點切割，使兩個 sub-list 皆盡量等長，再對 sub-list 做 merge sort，故 worst case 的複雜度與 best case 相同，應為：

$$
T(n) = T(\frac{n}{2})+T(\frac{n}{2})=O(nlogn)
$$

而會造成 merge sort 產生 worst case 的為 merge 時 compare 的次數，當兩個 sub-list 間的大小排序為互相交叉時會發生：

digraph G {

        rankdir=LR;
        node [shape=record];
        a [label="{ <data> 1 | <ref>  }"]
        b [label="{ <data> 3 | <ref>  }"];
        c [label="{ <data> 5 | <ref>  }"];
        g [label="{ <data> 7 | <ref>  }"];
        a:ref:c -> b:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false, arrowsize=1.2];
        b:ref:c -> c:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        c:ref:g -> g:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        d [label="{ <data> 2 | <ref>  }"]
        e [label="{ <data> 4 | <ref>  }"];
        f [label="{ <data> 6 | <ref>  }"];
        d:ref:f -> e:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false, arrowsize=1.2];
        e:ref:f -> f:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        
        node [shape=plaintext]
        "sublist B"->a [style=invis]
        "sublist A"->d [style=invis]
}

此時 merge 將需要 m + n - 1 次的 comparison，根據 [Wikipedia](https://en.wikipedia.org/wiki/Merge_sort#cite_note-5)，此數值最高為 $n ⌈lg n⌉ − 2⌈lg n⌉ + 1$。

### 2. Linux 核心的 `list_sort.c` 的切割方式

實現 botton-up 方式的 merge sort，以每兩個元素為單位切割，當合併後產生兩個 $2^k$ 數量的 list 時，便會合併成 $2^{k+1}$，並保證 $2^{k-1}, ..., 2^1$ 數量的 linked list 皆存在，這樣就能維持每次 merge （包含最後一次 `merge_final`）皆最高只會有 2:1 的數量比例，所以只要 $3 \times 2^{k}$ 數量的元素都可以容納在 cache 中，便能減少 cache miss。