# 2021q1 Week1/2/3/4 :::warning 課堂問答簡記 請填入你的 GitHub 帳號名稱 ::: ## Uduru0522 :question: `linux/list.h` 的 `list_swap()` 實做原理 ？ ```cpp /** * 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"} **先試著把一些函式展開 ：** ```c= 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: 調整指標至如下形式 ```graphviz 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`完成，具體的內容如下: ```cpp #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`的具體內容為: ```cpp #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 間的大小排序為互相交叉時會發生： ```graphviz 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。