# Linux 核心專題: 改進 lab0
> 執行人: yihsuan1011
> [專題講解影片](https://youtu.be/4pMY1n8CoU8)
:::success
:question: 提問清單
* ?
:::
## 任務簡述
重做 [lab0](https://hackmd.io/@sysprog/linux2023-lab0) 並彙整其他學員的成果。
## TODO: 達成作業所有要求
### 開發環境
``` shell
$ gcc --version
gcc (Ubuntu 9.4.0-1ubuntu1~20.04.1) 9.4.0
Copyright (C) 2019 Free Software Foundation, Inc.
This is free software; see the source for copying conditions. There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
$ lscpu
Architecture: x86_64
CPU op-mode(s): 32-bit, 64-bit
Byte Order: Little Endian
Address sizes: 39 bits physical, 48 bits virtual
CPU(s): 16
On-line CPU(s) list: 0-15
Thread(s) per core: 2
Core(s) per socket: 8
Socket(s): 1
NUMA node(s): 1
Vendor ID: GenuineIntel
CPU family: 6
Model: 141
Model name: 11th Gen Intel(R) Core(TM) i7-11800H @ 2.30GHz
Stepping: 1
CPU MHz: 800.000
CPU max MHz: 4600.0000
CPU min MHz: 800.0000
BogoMIPS: 4608.00
```
### 開發過程
#### `q_new`
用`malloc`來配置記憶體，若配置失敗則會回傳`NULL`，配置成功則接著使用`INIT_LIST_HEAD`來初始化。
```c
struct list_head *q_new()
{
struct list_head *q = malloc(sizeof(struct list_head));
if (!q) // If allocate failed
return NULL;
INIT_LIST_HEAD(q);
return q;
}
```
#### `q_free`
用`list_for_each_entry_safe`來走訪佇列中的每個節點，並透過`list_del`與`q_release_element`將每個節點的空間釋放。`list_for_each_entry_safe`中除了用`entry`儲存當前節點外，還會使用另一個指標`safe`來儲存下一個節點，因此不必擔心當前節點空間被釋放後會導致循環無法繼續。
```c
void q_free(struct list_head *l)
{
if (!l)
return;
element_t *entry, *safe;
list_for_each_entry_safe (entry, safe, l, list) {
list_del(&entry->list);
q_release_element(entry);
}
free(l);
}
```
#### `q_insert_head`
使用`malloc`為新節點配置記憶體，並檢查該，`element_t`有無配置成功，接著使用`strdup`複製字串`s`到`entry->value`，若檢查到`entry->value`配置失敗，則要將整個`entry`都釋放，最後再透過`list_add`將新節點加入佇列中。
```c
bool q_insert_head(struct list_head *head, char *s)
{
if (!head)
return false;
element_t *entry = malloc(sizeof(element_t));
if (!entry)
return false;
entry->value = strdup(s);
if (!entry->value) {
free(entry);
return false;
}
list_add(&entry->list, head);
return true;
}
```
#### `q_insert_tail`
`q_insert_tail`與`q_insert_head`的目標類似，僅在插入節點的位置有所不同，因此直接用`head->prev`作為`q_insert_head`的第一個引數就可以完成目標，只需要額外考慮空佇列的特例即可。
```c
bool q_insert_tail(struct list_head *head, char *s)
{
if (!head)
return false;
if (list_empty(head))
return q_insert_head(head, s);
else
return q_insert_head(head->prev, s);
}
```
#### `q_remove_head`
使用`list_first_entry`找到開頭節點，並使用`strncpy`將被刪除的節點字串複製到`sp`中，字串長度由`bufsize`限制，且需要加上結尾字元，最後再由`list_del_init`刪除開頭節點。
```c
element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
if (!head || list_empty(head))
return NULL;
element_t *target = list_first_entry(head, element_t, list);
if (sp) {
strncpy(sp, target->value, bufsize - 1);
sp[bufsize - 1] = '\0';
}
list_del_init(head->next);
return target;
}
```
#### `q_remove_tail`
使用`list_last_entry`找到結尾節點，並使用`strncpy`將被刪除的節點字串複製到`sp`中，字串長度由`bufsize`限制，且需要加上結尾字元，最後再由`list_del_init`刪除結尾節點。
```c
element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize)
{
if (!head || list_empty(head))
return NULL;
element_t *target = list_last_entry(head, element_t, list);
if (sp) {
strncpy(sp, target->value, bufsize - 1);
sp[bufsize - 1] = '\0';
}
list_del_init(head->prev);
return target;
}
```
#### `q_size`
使用`list_for_each`走訪佇列中的每個節點，宣告一個整數`len`來累計`list_for_each`的迴圈次數，達到計算佇列長度的效果。
```c
int q_size(struct list_head *head)
{
if (!head || list_empty(head))
return 0;
int len = 0;
struct list_head *li;
list_for_each (li, head)
len++;
return len;
}
```
#### `q_delete_mid`
首先需要找到佇列的中點，原本使用課程中提到的快慢指標完成，後來參考同學們的作法，善用雙向鏈結佇列的特性，用兩個指標以相反方向走訪，兩個指標指向同個節點時即為中點。此種做法比快慢指標法需要走訪的節點數少三分之一。
```c
bool q_delete_mid(struct list_head *head)
{
if (!head || list_empty(head))
return false;
struct list_head *front = head->next, *back = head->prev;
while (front != back && front->next != back) {
front = front->next;
back = back->prev;
}
element_t *node = list_entry(back, element_t, list);
list_del(&node->list);
q_release_element(node);
return true;
}
```
#### `q_delete_dup`
根據[LeetCode 82](https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/)的題意，該函式的目標是刪除所有重複的節點。使用`list_for_each_entry_safe`走訪所有節點，並且使用`bool dup`來標示當前節點是否為多個連續重複節點組成的重複節點群。用`strcmp`比較當前節點和下一個節點的字串是否相同，如果相同，則刪除當前節點，同時`dup`設置為`1`表示已進入重複節點群。直到當前節點與下一個點的字串不同時，會進到`else if (dup)`的區塊，刪除最後一個重複節點並將`dup`重新設置為`0`。
```c
bool q_delete_dup(struct list_head *head)
{
if (!head || list_empty(head))
return false;
element_t *curr, *next;
bool dup = 0;
list_for_each_entry_safe (curr, next, head, list) {
if (&next->list != head && strcmp(curr->value, next->value) == 0) {
list_del(&curr->list);
q_release_element(curr);
dup = 1;
} else if (dup) {
list_del(&curr->list);
q_release_element(curr);
dup = 0;
}
}
return true;
}
```
#### `q_swap`
使用一個`for`迴圈走訪所有節點，且當前節點`node`和`node->next`皆不能為`head`，再使用`list_move`將當前節點與下一個節點交換位置，完成一個成對節點的交換，而此時的`node->next`就會指向下一組成對節點的第一個節點，重複直到佇列結束。
```c
void q_swap(struct list_head *head)
{
if (!head || list_empty(head))
return;
for (struct list_head *node = head->next;
node != head && node->next != head; node = node->next) {
struct list_head *tmp = node;
list_move(node, tmp->next);
}
}
```
#### `q_reverse`
使用`list_for_each_entry_safe`走訪所有節點，並將當前節點依序移動至佇列最前端，即完成佇列排列順序反轉。
```c
void q_reverse(struct list_head *head)
{
if (!head || list_empty(head))
return;
struct list_head *node, *safe;
list_for_each_safe (node, safe, head)
list_move(node, head);
}
```
#### `q_reverseK`
使用`list_for_each_entry_safe`走訪所有節點，使用`count`計次，每`k`個節點擷取成一個子佇列`sub_q`，並將`sub_q`透過`q_reverse`進行順序反轉，再將子佇列移動回原佇列的位置。
```c
void q_reverseK(struct list_head *head, int k)
{
if (!head || list_empty(head))
return;
int count = 0;
struct list_head sub_q, *node, *safe, *tmp = head;
INIT_LIST_HEAD(&sub_q);
list_for_each_safe (node, safe, head) {
count++;
if (count == k) {
list_cut_position(&sub_q, tmp, node);
q_reverse(&sub_q);
list_splice_init(&sub_q, tmp);
count = 0;
tmp = safe->prev;
}
}
}
```
#### `q_merge_two`
參考上課中的merge方法，另外定義了`q_merge_two`。引數為兩個佇列，宣告了一個儲存結果的`list_head result`，依序比較兩個佇列的最前端節點，將字串較大者移動到`result`的末端，完成排序後，原本的兩個佇列會有一個變為空佇列，再將另一個有剩餘節點的佇列移動到`result`的末端，最終結果`result`會儲存再原先第一個佇列的位址。
後面新增了引數` bool descend`，目前先簡單依`descend`不同分成兩種`while`迴圈，但兩種迴圈有很多相同處，應可再簡化。
```c
void q_merge_two(struct list_head *q1, struct list_head *q2, bool descend)
{
if (!q1 || !q2)
return;
struct list_head result;
INIT_LIST_HEAD(&result);
element_t *node;
if (descend) {
while (!list_empty(q1) && !list_empty(q2)) {
element_t *e1 = list_first_entry(q1, element_t, list);
element_t *e2 = list_first_entry(q2, element_t, list);
node = (strcmp(e1->value, e2->value) > 0) ? e1 : e2;
list_move_tail(&node->list, &result);
}
} else {
while (!list_empty(q1) && !list_empty(q2)) {
element_t *e1 = list_first_entry(q1, element_t, list);
element_t *e2 = list_first_entry(q2, element_t, list);
node = (strcmp(e1->value, e2->value) < 0) ? e1 : e2;
list_move_tail(&node->list, &result);
}
}
struct list_head *residual = (list_empty(q2)) ? q1 : q2;
list_splice_tail_init(residual, &result);
list_splice(&result, q1);
}
```
#### `q_sort`
此處實作了課程中的Merge Sort方法。首先用快慢指標方法找到中間節點，從中間節點切成左右兩個子佇列，用遞迴的方式重複分割佇列，直到每個子佇列都只有一個節點，最後再用前面定義的`q_merge_two`兩兩合併，最終得到排序完成的佇列。
```c
void q_sort(struct list_head *head, bool descend)
{
if (!head || list_empty(head) || head->next == head->prev)
return;
struct list_head *mid = head;
for (struct list_head *fast = head->next;
fast != head && fast->next != head; fast = fast->next->next)
mid = mid->next;
struct list_head left;
INIT_LIST_HEAD(&left);
list_cut_position(&left, head, mid);
// head will become right half
q_sort(&left, descend);
q_sort(head, descend);
q_merge_two(head, &left, descend);
}
```
#### `q_ascend`
使用雙向鏈結佇列的特性，反向走訪所有節點，比較當前節點`curr`和前一個節點`curr->list.prev`位置的字串大小，若前一個節點大於當前節點則將前一個節點刪除。
```c
int q_ascend(struct list_head *head)
{
if (!head || list_empty(head))
return 0;
element_t *curr = list_entry(head->prev, element_t, list);
while (curr->list.prev != head) {
element_t *next = list_entry(curr->list.prev, element_t, list);
if (strcmp(next->value, curr->value) > 0) {
list_del(&next->list);
q_release_element(next);
} else {
curr = next;
}
}
return q_size(head);
}
```
#### `q_descend`
與`q_ascend`相同作法，反向走訪所有節點，比較當前節點`curr`和前一個節點`curr->list.prev`位置的字串大小，若前一個節點小於當前節點則將前一個節點刪除。
```c
int q_descend(struct list_head *head)
{
if (!head || list_empty(head))
return 0;
element_t *curr = list_entry(head->prev, element_t, list);
while (curr->list.prev != head) {
element_t *next = list_entry(curr->list.prev, element_t, list);
if (strcmp(next->value, curr->value) < 0) {
list_del(&next->list);
q_release_element(next);
} else {
curr = next;
}
}
return q_size(head);
}
```
#### `q_merge`
首先先檢查是否只有一個佇列，如果有大於一個佇列，會先將第一個佇列儲存到`first`，接著再從第二個佇列開始依序透過`q_merge_two`合併至`first`中，最後返回first的大小。
```c
int q_merge(struct list_head *head, bool descend)
{
if (!head || list_empty(head))
return 0;
if (head->next == head->prev)
return list_first_entry(head, queue_contex_t, chain)->size;
queue_contex_t *first = list_first_entry(head, queue_contex_t, chain);
queue_contex_t *curr, *safe;
list_for_each_entry_safe (curr, safe, head, chain) {
if (curr != first) {
q_merge_two(first->q, curr->q, descend);
curr->q = NULL;
}
}
return q_size(first->q);
}
```
### 引入 lib/list_sort.c
此處參考同學 [chiangkd](https://github.com/chiangkd) 筆記中的步驟。
#### 加入 [list_sort.c](https://github.com/torvalds/linux/blob/master/lib/list_sort.c) 和 [list_sort.h](https://github.com/torvalds/linux/blob/master/include/linux/list_sort.h)
將 [list_sort.c](https://github.com/torvalds/linux/blob/master/lib/list_sort.c) 和 [list_sort.h](https://github.com/torvalds/linux/blob/master/include/linux/list_sort.h) 兩者加入`lab0-c`資料夾中，直接加入會出現很多錯誤，大多數都是因為`include`許多沒有使用到的header，確認那些header不會使用到則直接刪除即可。
#### 修改 Makefile
修改Makefile，加入`list_sort.o`
```diff
OBJS := qtest.o report.o console.o harness.o queue.o \
random.o dudect/constant.o dudect/fixture.o dudect/ttest.o \
shannon_entropy.o \
- linenoise.o web.o
+ linenoise.o web.o list_sort.o
```
#### 修改 `qtest`
參考`qtest`當中`do_sort`的內容，在`qtset`中新增`do_lsort`，以執行`list_sort`，作法同[chiangkd](https://github.com/chiangkd)同學之實作。
```c
int cmp(void *priv, const struct list_head *a, const struct list_head *b)
{
element_t *a_ele = list_entry(a, element_t, list); // get mother element
element_t *b_ele = list_entry(b, element_t, list);
return strcmp(a_ele->value, b_ele->value) < 0 ? 0 : 1;
}
bool do_lsort(int argc, char *argv[])
{
if (argc != 1) {
report(1, "%s takes no arguments", argv[0]);
return false;
}
int cnt = 0;
if (!current || !current->q)
report(3, "Warning: Calling sort on null queue");
else
cnt = q_size(current->q);
error_check();
if (cnt < 2)
report(3, "Warning: Calling sort on single node");
error_check();
set_noallocate_mode(true);
if (current && exception_setup(true))
list_sort(NULL, current->q, cmp);
exception_cancel();
set_noallocate_mode(false);
bool ok = true;
if (current && current->size) {
for (struct list_head *cur_l = current->q->next;
cur_l != current->q && --cnt; cur_l = cur_l->next) {
/* Ensure each element in ascending order */
/* FIXME: add an option to specify sorting order */
element_t *item, *next_item;
item = list_entry(cur_l, element_t, list);
next_item = list_entry(cur_l->next, element_t, list);
if (strcmp(item->value, next_item->value) > 0) {
report(1, "ERROR: Not sorted in ascending order");
ok = false;
break;
}
}
}
q_show(3);
return ok && !error_check();
}
```
最後再加入新命令 `lsort`。
```c
ADD_COMMAND(lsort, "Sort queue in ascending order provided by linux kernel", "");
```
## TODO: 研讀 Linux 的 `lib/list_sort.c` 並量化分析
解讀 Linux 核心原始程式碼的 `lib/list_sort.c`，設計實驗來量化分析，探討其實作手法，需要善用 perf 一類的工具。解析程式碼要有完整的圖文、數學證明，和如何達到 cache 友善。
### 研讀 `list_sort` 內容
`list_sort` 的排序步驟如下：
* 宣告了兩個指標 `list` 和 `pending` 分別指向佇列的當前節點和暫存節點
* 檢查是否為空佇列或只有一個節點，是則直接返回
* 透過 `head->prev->next = NULL` 將佇列以 `NULL` 為結尾
* 用`for`迴圈走訪每個節點，找到最小的子佇列，就進行 `merge` ，並更新指標和計數。
* 最後用 `merge_final` 完成最後合併。
上述為最簡略的步驟解釋，中間的一些條件判斷方式我還不完全理解，查閱的資料顯示這樣的佇列排序方法能達到高效率及高穩定性。
此方法為 Tim Sort 的排序演算法的變體，結合了上課提到的 merge sort 和 insertion sort。主要概念是將輸入資料分割成許多小佇列，對每一小佇列使用 insertion sort 進行排序，接著再使用 merge 將這些已經排序好的小佇列合併成排序好的大佇列，最終完成排序。
:::warning
:warning: 確認上述陳述是否正確！
:notes: jserv
:::
## TODO: 改進 qtest 以切換不同的排序實作
在 qtest 新增 `option`，允許使用者切換不同的排序實作 (例如 Linux 核心的 `list_sort.c` 和自行實作的 merge sort)。
上述步驟透過新增了`do_lsort`功能，以及新增了`lsort`指令，即可讓使用者透過`cmd>`選擇排序方法。
```shell
cmd> new
l = []
cmd> ih RAND 1000
l = [bairbyrip jltlqum vwndfsce nucefk cwxzxkt blbzozhyd abjxfpgk egsvt dobyffwh vcjdyx trgwmnw feshg fiecplk jcjrl nhrvknat qjlsix wgvttx ernhzmidp fhzxluuto soyrojs jbdlziapd benrs vfgzvod yfpngg fbysew paqqh dlfot hvqvyctlq zwxpqz pxexhawae ... ]
cmd> lsort
l = [aacsgl aamaga abjxfpgk acfhmcjt acswijwsz acwcpzmye adqpkt adxmkcww afbfx aglwnbops ahhtr ahincpmw ajtxuja akcngotau akodcaj aliwy alnnzaad ambhdg amhcs aoekbho aoictluys apkser apogs aqjzhzst aqmgbxj ashap askzhuqxr asufdf asxgvswkd asxlc ... ]
```
## TODO: 改進原有常數時間複雜度判斷程式
搭配研讀必要的統計原理，探討如何改進原有常數時間複雜度判斷程式
Sign in with Wallet
Connect another wallet