# 2021q1 Homework1 (quiz1)
contributed by < `D4nnyLee` >
> [quiz1 題目連結](https://hackmd.io/@sysprog/linux2021-quiz1)
## 重新回答問題並解釋程式運作原理
### 各個重要函式的功能
#### `list_add_node_t`
:::info
這個函式的功能則是將一個新的節點加到一個 linked list 的開頭。
:::
```graphviz
digraph {
subgraph objects {
rank = same
node [shape = box];
node_t [label = "new\nnode"];
head_node [label = "head\nnode"];
many [label = "...", shape = none]
null [label = "NULL" shape = none]
head_node -> node1 -> many -> nodex -> null
}
subgraph pointers {
node [shape = ellipse]
_node_t [label = "node_t"]
_list [label = "*list"]
__list [label = "list"]
}
_node_t -> node_t
__list -> _list -> head_node
}
```
圖中方形的圖像為實體物件，而圓形的則是指標。
上圖為將代入的參數視覺化之後的預期結果，從上圖中可以看到：
* `node_t` 為指向一個即將新增到 linked list 裡的新節點 `new node` 的指標
* `list` 為一個指標的指標， `**list` 為一個 linked list 的開頭節點
具體執行的步驟如下：
1. 新節點指向舊開頭
```cpp
node_t->next = *list;
```
這段程式碼會新增一條從 `new node` 指向 `head node` 的邊，如下圖：
```graphviz
digraph {
subgraph objects {
rank = same
node [shape = box];
node_t [label = "new\nnode"];
head_node [label = "head\nnode"];
many [label = "...", shape = none]
null [label = "NULL" shape = none]
node_t -> head_node [color = red]
head_node -> node1 -> many -> nodex -> null
}
subgraph pointers {
node [shape = ellipse]
_node_t [label = "node_t"]
_list [label = "*list"]
__list [label = "list"]
}
_node_t -> node_t
__list -> _list -> head_node
}
```
2. 更新開頭節點的位址
因為此函式的使用方法為先有一個 `node_t *head_ptr` 變數儲存開頭節點的位址，然後在呼叫函式的時候傳入 `&head_ptr` ，所以可以在此函式裡面就直接更新到外部的變數。
此技巧可以讓在使用這個函式時不用特地去維護 `head_ptr` ，因此用起來更加方便。
這邊利用以下程式碼去更新外部的 `head_ptr` 變數
```cpp
*list = node_t;
```
造成的結果如下圖：
```graphviz
digraph {
subgraph objects {
rank = same
node [shape = box];
node_t [label = "new\nnode"];
head_node [label = "head\nnode"];
many [label = "...", shape = none]
null [label = "NULL" shape = none]
node_t -> head_node -> node1 -> many -> nodex -> null
}
subgraph pointers {
node [shape = ellipse]
_node_t [label = "node_t"]
_list [label = "*list"]
__list [label = "list"]
}
_node_t -> node_t
__list -> _list
_list -> node_t [color = red]
}
```
這邊的 `*list` 實際上就是外部的 `head_ptr` 變數
#### `list_concat`
:::info
根據函式名稱可以知道這個函式的功能是將兩個 linked list 連接在一起。
:::
將參數視覺化：
```graphviz
digraph {
subgraph objects {
node [shape = box]
head_node [label = "head\nnode"]
many [label = "...", shape = none]
null [label = "NULL", shape = none]
{
rank = same
head_node -> node1 -> many -> nodex -> null
}
}
subgraph pointers {
node [shape = ellipse]
_left [label = "*left"]
left -> _left -> head_node
}
}
```
```graphviz
digraph {
subgraph objects {
node [shape = box]
head_node [label = "head\nnode"]
many [label = "...", shape = none]
null [label = "NULL", shape = none]
{
rank = same
head_node -> node1 -> many -> nodex -> null
}
}
subgraph pointers {
node [shape = ellipse]
right -> head_node
}
}
```
可以看到這個函式的一部分程式碼被替換成 `LLL` ，而 `LLL` 的答案應該為
`left = &((*left)->next)` 。
以下簡略解釋其他三個選項的錯誤原因：
* `left = left->next`
會造成編譯錯誤，因為 `node_t **` 指向的 `node_t *` 物件並沒有 `next` 這個欄位。
* `left = (*left)->next`
`left` 的型別和 `(*left)->next` 的型別不符。
* `*left = (*left)->next`
雖然這個選項可以正常編譯，但是試著將 `LLL` 替換為這個選項之後：
```cpp
while (*left)
*left = (*left)->next;
*left = right;
```
可以看到從頭到尾都只是一直修改外部的 `*left` 變數，且沒有什麼實質的作用。
更慘的是這可能會讓程式無法存取到原本在左半部的 linked list 裡的節點，也無法釋放那些空間，而造成記憶體的浪費。
在這個函式中，也有利用到指標的指標來實作，而這邊可以看到使用這個技巧的另一個好處，就是不用特判空 list 的情況。
如果 `left` 的型別是 `node_t *` ，雖然也可以做到同樣的功能，但是就需要分成 `left` 為 NULL 以及 `left` 不為 NULL 的情況來撰寫。
利用指標的指標的技巧就可以用相同的步驟處理這兩種情況。
#### `quicksort`
:::info
將 linked list 中的節點依照 `value` **由小到大**來排序
:::
實作可以分成以下四個步驟：
1. 選出 pivot
```cpp
node_t *pivot = *list;
int value = pivot->value;
node_t *p = pivot->next;
pivot->next = NULL;
```
這邊只有單純的選第一個節點當作 `pivot` ，並且把 `pivot` 與剩下的節點分離，形成兩個獨立的 linked list 。
2. 將剩下的節點分成兩個 linked list
```cpp
node_t *left = NULL, *right = NULL;
while (p) {
node_t *n = p;
p = p->next;
list_add_node_t(n->value > value ? AAA : BBB, n);
}
```
依據 `pivot` 的值分成 `left`, `right` 兩個 linked list ，因為是**由小到大**排序，所以 `AAA` 應該選 `&right` ，且 `BBB` 為 `&left` 。
這段程式碼執行完之後 `left` 為所有 `value` 小於等於 `pivot` 的節點， `right` 則是其他剩下的 (所有 `value` 大於 pivot 的) 節點。
3. 分別排序小的 linked list
```cpp
quicksort(&left);
quicksort(&right);
```
利用遞迴呼叫，將兩個小的 linked list 進行排序。
4. 合併結果
```cpp
node_t *result = NULL;
list_concat(&result, left);
CCC;
*list = result;
```
在合併之前，原本的 linked list 總共被分為三個部分，分別為 `left`, `pivot` 以及 `right` 。
因為 `left`, `right` 都已經排序完畢，且 `left` 裡的所有節點都小於等於 `pivot` ， `right` 的都大於 `pivot` ，這就代表依照 `left`, `pivot`, `right` 的順序把 linked list 連接起來也會是個排序好的 linked list 。
因此 `CCC` 應該選 `list_concat(&result, pivot); list_concat(&result, right)` 。
### 修正 `rand()` 問題
題目中的測試程式執行多次之後會發現明明有用到 `rand()` 來隨機產生排序前的值，但是每次出來的結果都是一模一樣的。
根據 [man page](https://man7.org/linux/man-pages/man3/rand.3.html) 中的敘述：
> The srand() function sets its argument as the seed for a new
> sequence of pseudo-random integers to be returned by rand().
> These sequences are repeatable by calling srand() with the same
> seed value.
>
> If no seed value is provided, the rand() function is
> automatically seeded with a value of 1.
只要給相同的 `seed` ，就可以讓 `rand()` 回傳相同的順序。
而如果沒有事先用 `srand()` 函式設定 `seed` 的話 `seed` 的預設值為 `1` 。
這也就代表只要沒有呼叫 `srand()` ，每次執行程式時 `rand()` 的行為都會一樣。
解決方法也很簡單，就是多呼叫 `srand()` 就可以了。
## 避免遞迴呼叫
### 開發歷程
為了減少 `rand()` 所帶來的影響，以下測試都會先將前面[修正 `rand()` 問題](#修正-rand-問題)所提到的 `srand()` 註解掉。
#### stack-use-after-scope
先參照 [Optimized QuickSort — C Implementation (Non-Recursive)](https://alienryderflex.com/quicksort/) 試著實做出非遞迴版本的 quicksort ：
```cpp=
void quicksort(node_t **list)
{
if (!*list)
return;
#define MAX_LEVEL 300
node_t **beg[MAX_LEVEL], *end[MAX_LEVEL];
beg[0] = list;
end[0] = NULL;
for (int i = 0; i >= 0;) {
if (*beg[i] == end[i])
--i;
else {
node_t *pivot = *beg[i], *n = pivot->next;
int val = pivot->value;
pivot->next = NULL;
node_t *left = NULL, *right = NULL;
while (n != end[i]) {
node_t *tmp = n;
n = n->next;
list_add_node_t(tmp->value > val ? &right : &left, tmp);
}
list_concat(&right, end[i]);
list_concat(&pivot, right);
list_concat(&left, pivot);
*beg[i] = left;
beg[i + 1] = &right;
end[i + 1] = end[i];
end[i++] = pivot;
}
}
#undef MAX_LEVEL
}
```
將上述程式編譯後執行時，很不幸的發生了 segmentation fault ：
```shell
$ ./test
NOT IN ORDER : 1016 84 706 124 326 483 763 498 939 186 205 809 236 74 255 81 115 105 966 359
zsh: segmentation fault ./test
```
在編譯參數中多加了 `-fsanitize=address -g` 之後再執行一次之後可以看到：
```shell
NOT IN ORDER : 1016 84 706 124 326 483 763 498 939 186 205 809 236 74 255 81 115 105 966 359
=================================================================
==3477==ERROR: AddressSanitizer: stack-use-after-scope on address 0x7ffeddf2e660 at pc 0x55ef0a448b2a bp 0x7ffeddf2e5c0 sp 0x7ffeddf2e5b8
READ of size 8 at 0x7ffeddf2e660 thread T0
#0 0x55ef0a448b29 in quicksort /home/d4nnylee/Documents/linux_kernel_internal/quiz1/list.c:59
#1 0x55ef0a44859a in main /home/d4nnylee/Documents/linux_kernel_internal/quiz1/test.c:46
#2 0x7efc00f77d09 in __libc_start_main ../csu/libc-start.c:308
#3 0x55ef0a448199 in _start (/home/d4nnylee/Documents/linux_kernel_internal/quiz1/test+0x1199)
Address 0x7ffeddf2e660 is located in stack of thread T0 at offset 96 in frame
#0 0x55ef0a4488d2 in quicksort /home/d4nnylee/Documents/linux_kernel_internal/quiz1/list.c:47
This frame has 5 object(s):
[32, 40) 'pivot' (line 62)
[64, 72) 'left' (line 66)
[96, 104) 'right' (line 66) <== Memory access at offset 96 is inside this variable
[128, 8128) 'beg' (line 53)
[8384, 16384) 'end' (line 53)
HINT: this may be a false positive if your program uses some custom stack unwind mechanism, swapcontext or vfork
(longjmp and C++ exceptions *are* supported)
SUMMARY: AddressSanitizer: stack-use-after-scope /home/d4nnylee/Documents/linux_kernel_internal/quiz1/list.c:59 in quicksort
Shadow bytes around the buggy address:
0x10005bbddc70: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0x10005bbddc80: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0x10005bbddc90: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0x10005bbddca0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0x10005bbddcb0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
=>0x10005bbddcc0: f1 f1 f1 f1 f8 f2 f2 f2 f8 f2 f2 f2[f8]f2 f2 f2
0x10005bbddcd0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0x10005bbddce0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0x10005bbddcf0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0x10005bbddd00: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0x10005bbddd10: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
Shadow byte legend (one shadow byte represents 8 application bytes):
Addressable: 00
Partially addressable: 01 02 03 04 05 06 07
Heap left redzone: fa
Freed heap region: fd
Stack left redzone: f1
Stack mid redzone: f2
Stack right redzone: f3
Stack after return: f5
Stack use after scope: f8
Global redzone: f9
Global init order: f6
Poisoned by user: f7
Container overflow: fc
Array cookie: ac
Intra object redzone: bb
ASan internal: fe
Left alloca redzone: ca
Right alloca redzone: cb
Shadow gap: cc
==3477==ABORTING
```
從上面的錯誤訊息可以看到，這是因為發生了 `stack-use-after-scope` 的錯誤。
問題的主因為上述程式碼第 33 行的地方，這邊我是將 `&right` 存到 `beg[i + 1]` 且 `beg[i + 1]` 有可能會在下一次的迴圈被 dereference 。
但是 `right` 為 for 迴圈內的區域變數， scope 的範圍只有在一次的迴圈，並不會延續到下一次的迴圈，因此上述 `beg[i + 1] = &right` 的寫法就會出錯。
我的解法為將 `&right` 改成 `&pivot->next` 。
這兩者的共通點為 dereference 之後都是一個指向右邊 linked list 開頭的指標，
而不同的點是 `pivot->next` 為待排序節點中的變數，因此 scope 並不限定在 `quicksort()` 內，所以不會發生前面的 `stack-use-after-scope` 錯誤。
最終修正：
```diff
- beg[i + 1] = &right;
+ beg[i + 1] = &pivot->next;
```
#### No-Fail Version
Quicksort 的 Worst-Case 非常經典，就是接近排序完成的序列。
這樣的情況時間複雜度會變成 $O(N^2)$ ，$N$ 為序列長度。
且遞迴深度也會變成 $O(N)$ ，容易造成 stack 空間不夠用。
而在這個非遞迴實做中，則會造成 `i >= MAX_LEVEL` 情況。
將 `main()` 做以下修改：
```diff
int main(int argc, char **argv)
{
// srand(time(NULL));
- size_t count = 20;
+ size_t count = 2000;
node_t *list = NULL;
while (count--)
- list = list_make_node_t(list, rand() % 1024);
+ list = list_make_node_t(list, count);
list_display(list);
quicksort(&list);
list_display(list);
if (!list_is_ordered(list))
return EXIT_FAILURE;
list_free(&list);
return EXIT_SUCCESS;
}
```
測試後也如同預期的發生了 segmentation fault ：
```shell
$ ./test
IN ORDER : 0 1 2
...
1989 1990 1991 1992 1993 1994 1995 1996 1997 1998 1999
zsh: segmentation fault ./test
```
在 [Optimized QuickSort — C Implementation (Non-Recursive)](https://alienryderflex.com/quicksort/) 中提到的 No-Fail Version 的原理是先將原本的 `[beg[i], end[i])` 範圍分成兩個部份後， 先從比較短的部份開始做，並使的 `i` 不會超過 `MAX_LEVEL`。
修改如下：
```diff
+ int cnt_left = 0, cnt_right = 0;
node_t *left = NULL, *right = NULL;
while (n != end[i]) {
node_t *tmp = n;
n = n->next;
- list_add_node_t(tmp->value > val ? &right : &left, tmp);
+
+ if (tmp->value > val) {
+ ++cnt_right;
+ list_add_node_t(&right, tmp);
+ } else {
+ ++cnt_left;
+ list_add_node_t(&left, tmp);
+ }
}
```
```diff
beg[i + 1] = &pivot->next;
end[i + 1] = end[i];
end[i++] = pivot;
+
+ if (cnt_left < cnt_right) {
+ node_t **beg_swap = beg[i];
+ beg[i] = beg[i - 1];
+ beg[i - 1] = beg_swap;
+
+ node_t *end_swap = end[i];
+ end[i] = end[i - 1];
+ end[i - 1] = end_swap;
+ }
```
### 小優化
在合併 `left`, `pivot`, `right` 的地方我稍微調換了一下順序。
照著原本題目的寫法，最直觀的用法為：
```cpp
*beg[i] = left;
list_concat(beg[i], pivot);
list_concat(beg[i], right);
list_concat(beg[i], end[i]);
```
但是這個寫法會多跑了許多不必要的迴圈。
舉個例子：
```graphviz
digraph {
subgraph pointers {
node [shape = ellipse]
{
rank = same
left
pivot
right
}
}
subgraph objects {
node [shape = box]
{
rank = same
node_1 -> node_2 -> node_3
node_4
node_5
}
}
left -> node_1
pivot -> node_4
right -> node_5
}
```
來算一下 `list_concat()` 中的 while 迴圈執行次數：
* `list_concat(beg[i], pivot)` : 3 次
* `list_concat(beg[i], right)` : 4 次
* `list_concat(beg[i], end[i])` : 5 次
總共跑了 12 次迴圈
較好的合併方法為：
```cpp
list_concat(&right, end[i]);
list_concat(&pivot, right);
list_concat(&left, pivot);
*begin = left;
```
再算一次 while 迴圈的執行次數：
* `list_concat(&right, end[i])` : 1 次
* `list_concat(&pivot, right)` : 1 次
* `list_concat(&left, pivot)` : 3 次
總共只有執行 5 次，可以看到調換順序之後可以減少無謂的操作。
以下為利用 `perf stat` 來測試兩者排序 2 * 10^5^ 個節點的效率的結果：
重排前：
```
Performance counter stats for './worst':
606.27 msec task-clock # 0.818 CPUs utilized
37 context-switches # 0.061 K/sec
1 cpu-migrations # 0.002 K/sec
1,613 page-faults # 0.003 M/sec
2,030,268,114 cycles # 3.349 GHz
1,684,564,030 instructions # 0.83 insn per cycle
247,652,632 branches # 408.483 M/sec
1,563,034 branch-misses # 0.63% of all branches
0.740974650 seconds time elapsed
0.591300000 seconds user
0.015873000 seconds sys
```
重排後：
```
Performance counter stats for './better':
365.69 msec task-clock # 0.823 CPUs utilized
8 context-switches # 0.022 K/sec
0 cpu-migrations # 0.000 K/sec
1,615 page-faults # 0.004 M/sec
1,206,934,798 cycles # 3.300 GHz
1,345,761,978 instructions # 1.12 insn per cycle
205,406,361 branches # 561.698 M/sec
1,209,013 branch-misses # 0.59% of all branches
0.444207927 seconds time elapsed
0.359031000 seconds user
0.008068000 seconds sys
```
可以看到重排後的排序比較省時。
Sign in with Wallet
Connect another wallet