# Linux 核心專題: 重作第一次作業
> 執行人: jerry7961
> [專題解說影片](?)
### Reviewed by 'ken-LuWeiRu'
可以參考 https://hackmd.io/@sysprog/Syc7ROemA#%E6%95%88%E8%83%BD%E5%88%86%E6%9E%90
做效能分析
## 任務簡介
重作第一次作業，並強化若干子任務。
## TODO: 重做 lab0，整合 Timsort，比較 Linux 核心的 `list_sort`
> 量化並分析程式表現 (設計實驗，考慮到資料排序演算法最差的狀況、cache / locality of reference, 資料亂度/分佈)
:::danger
HackMD 不是讓你張貼完整程式碼的地方，而 GitHub 才是。
你若要張貼程式碼，就必定是因為你想討論或者提出後續的改進。
務必詳細閱讀第一次作業的規範！
:::
### `q_free`
先檢查佇列是否為空，若為空則 `return` 。
用 `list_for_each_entry_safe` 巨集走訪所有節點，並釋放節點。
最後釋放開頭節點。
```c
void q_free(struct list_head *head)
{
if (!head)
return;
element_t *cur, *next;
list_for_each_entry_safe (cur, next, head, list) {
q_release_element(cur);
}
free(head);
}
```
### `q_insert_head`
一開始誤用 `strcpy` (如下) 。
```c
bool q_insert_head(struct list_head *head, char *s)
{
if(!head)
return false;
element_t *new_element=malloc(sizeof(element_t));
if(!new_element)
return false;
strcpy(new_element->value,s);
if(!new_element->value){
free(new_element);
return false;
}
list_add(&new_element->list,head);
return true;
}
```
`strcpy(s1,s2)` 的功能是複製字串 `s2` 到字串 `s1` ，不會為 `s1` 分配内存， `s1` 的長度必須大於 `s2` 的長度。
因此在沒有為 `new_element->value` 分配內存的情況下直接用 `strcpy(new_element->value,s)` 會造成錯誤。
事先為 `new_element->value` 分配內存再用 `strcpy` 複製字串即可修正錯誤。
```c
bool q_insert_head(struct list_head *head, char *s)
{
if(!head)
return false;
element_t *new_element=malloc(sizeof(element_t));
if(!new_element)
return false;
new_element->value=malloc(strlen(s) + 1);
if(!new_element->value){
free(new_element);
return false;
}
strcpy(new_element->value,s);
list_add(&new_element->list,head);
return true;
}
```
另一種做法是使用 `strdup` 來代替 `strcpy` ，`strdup` 會為字串分配內存空間，並返回新分配空間的指標。
```c
bool q_insert_head(struct list_head *head, char *s)
{
if(!head)
return false;
element_t *new_element=malloc(sizeof(element_t));
if(!new_element)
return false;
new_element->value=strdup(s);
if(!new_element->value){
free(new_element);
return false;
}
list_add(&new_element->list,head);
return true;
}
```
### `q_insert_tail`
與 `q_insert_head` 的做法類似，差別是改用 `list_add_tail`。
```c
bool q_insert_tail(struct list_head *head, char *s)
{
if (!head)
return false;
element_t *new_element = malloc(sizeof(element_t));
if (!new_element)
return false;
new_element->value = strdup(s);
if (!new_element->value) {
free(new_element);
return false;
}
list_add_tail(&new_element->list, head);
return true;
}
```
### `q_remove_head`
`q_remove_head` 的作用是從鏈結串列的開頭移除一個元素。
首先檢查 `head` 是否為空指標，以及鏈結串列中是否至少有一個節點，確保鏈結串列存在且不為空。接著用 `list_first_entry` 取得鏈結串列第一個元素的指標，並透過 `list_del` 將這個元素從鏈結串列中移除。
如果 `sp` 不為 `NULL` ，使用 `strncpy` 函式將被移除元素的字串 `(to_delete->value)` 複製到 `sp` 指向的位址中。複製的字元數量最多為 `bufsize - 1` ，這是為了在字串結尾預留一個位置，用來存放 `\0` 。
```c
element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
if (head && !list_empty(head)) {
element_t *to_remove = list_first_entry(head, element_t, list);
list_del(&to_remove->list);
if (sp) {
strncpy(sp, to_remove->value, bufsize - 1);
sp[bufsize - 1] = '\0';
}
return to_remove;
}
return NULL;
}
```
### `q_remove_tail`
與 `q_remove_head` 類似，差別在使用 `list_last_entry` 來取得要移除的元素。
### `q_size`
使用 `list_for_each` 來走訪所有節點，每走訪一個節點 `count` 值就加一。
```c
int q_size(struct list_head *head)
{
if (!head || list_empty(head))
return 0;
int count = 0;
struct list_head *temp;
list_for_each (temp, head)
count++;
return count;
}
```
### `q_delete_mid`
使用快慢指標，快指標每次前進兩步，慢指標每次前進一步。
* 當鏈結串列包含奇數個節點時，快指標會停在最後一個節點上，此時慢指標正好指向鏈結串列的中間節點。
* 當鏈結串列包含偶數個節點時，快指標會回到鏈結串列的 `head` ，此時慢指標將指向中間兩個節點中的第二個。為了使 `q_delete_mid` 能夠刪除中間兩個節點中的第一個，需要增加一個 `if` 語句來調整慢指標的位置。
```c
if (fast == head) {
slow = slow->prev;
}
```
### `q_delete_dup`
`q_delete_dup` 是要在鏈結串列已經排序好的狀況下，移走其中具有重複內容的節點。
* 使用 `list_for_each_safe` 來走訪鏈結串列中的每個節點。
* `mark_del` 用來標記是否遇到重複節點。
* 在走訪過程中，根據當前節點與前後節點的關係，需要處理以下幾種情況：
1. 當前節點已經是最後一個節點，此時用 `mark_del` 來判斷當前節點是否與前一個節點重複，如果重複則刪除它。
2. 當前節點與下一個節點內容相同，此時刪除當前節點，並將 `mark_del` 設為 `true` ，表示已遇到重複節點。
3. 當前節點與下一個節點內容不同，但 `mark_del` 為 `true`，這表示當前節點與上一個節點內容相同，因此刪除當前節點，並將 `mark_del` 設為 `false`。
4. 非前三種情況，代表當前節點與下一個節點內容不同，與上一個節點也不同，無需執行任何操作。
### `q_swap`
`q_swap` 的作用是交換鏈結串列中鄰近的節點。
* 如果鏈結串列中的節點數量小於等於 1 ，無需執行任何操作。
* 如果鏈結串列中的節點數量大於 1 ，則 `q_swap` 從頭部節點的下一個節點開始走訪鏈結串列。對於每對相鄰節點，`q_swap` 會先將它們從鏈結串列中移除，然後以交換後的順序將它們重新插入到鏈結串列中。這個過程會一直重複，直到走訪完鏈結串列的所有節點。
```c
void q_swap(struct list_head *head)
{
if (!head || list_empty(head) || list_is_singular(head))
return;
struct list_head *node = head->next;
while (node != head && node->next != head) {
struct list_head *nextNode = node->next;
list_del(node);
list_del(nextNode);
list_add(nextNode, node->prev);
list_add(node, nextNode);
node = node->next;
}
}
```
### `q_reverse`
從頭部節點開始走訪鏈結串列，交換每個節點的 `next` 和 `prev` 指標以反轉鏈結串列方向，直到走訪完整個鏈結串列。
```c
void q_reverse(struct list_head *head)
{
if (!head || list_empty(head)) {
return;
}
struct list_head *current = head;
struct list_head *temp = NULL;
do {
temp = current->next;
current->next = current->prev;
current->prev = temp;
current = current->prev;
} while (current != head);
}
```
### `q_sort`
一開始使用 Insertion Sort ，無法通過測資，後來參考同學寫法，改用 Merge Sort 。
```c
void merge(struct list_head *l_head,
struct list_head *r_head,
struct list_head *head)
{
struct list_head temp_list;
INIT_LIST_HEAD(&temp_list);
while (!list_empty(l_head) || !list_empty(r_head)) {
struct list_head *chosen;
if (list_empty(l_head)) {
chosen = r_head;
} else if (list_empty(r_head)) {
chosen = l_head;
} else {
element_t *l_entry = list_entry(l_head->next, element_t, list);
element_t *r_entry = list_entry(r_head->next, element_t, list);
chosen =
(strcmp(l_entry->value, r_entry->value) <= 0) ? l_head : r_head;
}
list_move_tail(chosen->next, &temp_list);
}
list_splice_tail_init(&temp_list, head);
}
void merge_sort_recursive(struct list_head *head, int length)
{
if (length <= 1)
return;
int mid = length / 2;
struct list_head left, right;
INIT_LIST_HEAD(&left);
INIT_LIST_HEAD(&right);
struct list_head *current = head->next;
for (int i = 0; i < mid; i++) {
struct list_head *next = current->next;
list_move_tail(current, &left);
current = next;
}
list_splice_tail_init(head, &right);
merge_sort_recursive(&left, mid);
merge_sort_recursive(&right, length - mid);
INIT_LIST_HEAD(head);
merge(&left, &right, head);
}
void merge_sort(struct list_head *head)
{
if (!head || list_empty(head) || list_is_singular(head))
return;
int length = 0;
struct list_head *pos;
list_for_each (pos, head) {
length++;
}
merge_sort_recursive(head, length);
}
void q_sort(struct list_head *head, bool descend)
{
merge_sort(head);
if (descend) {
q_reverse(head);
}
}
```
### `q_merge`
<s>
</s>
```
+++ TESTING trace trace-03-ops:
# Test of insert_head, insert_tail, remove_head, reverse and merge
ERROR: Freed queue, but 2 blocks are still allocated
==665== 112 bytes in 2 blocks are still reachable in loss record 1 of 1
==665== at 0x4848899: malloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==665== by 0x10F2E7: test_malloc (harness.c:133)
==665== by 0x10F6EC: q_new (queue.c:17)
==665== by 0x10CDA3: do_new (qtest.c:155)
==665== by 0x10DFD1: interpret_cmda (console.c:181)
==665== by 0x10E586: interpret_cmd (console.c:201)
==665== by 0x10E987: cmd_select (console.c:610)
==665== by 0x10F273: run_console (console.c:705)
==665== by 0x10D3C3: main (qtest.c:1258)
==665==
trace-03-ops 0/6
```
:::danger
文字訊息「不要」用圖片展現。
:::
:::info
收到，已更正
:::
在 trace-03-ops 出現以上錯誤，經過排查，問題出在 `q_merge` 函式。原始版本的 `q_merge` 創建了一個新的 `first_queue` 指標，它用來指向第一個遇到的非空鏈結串列，這個鏈結串列將作為所有鏈結串列合併的目標，所有其他鏈結串列的元素都會被合併到這個 `first_queue` 中，其他鏈結串列在合併到 `first_queue` 後 `q` 指標會被設為 `NULL`，但相關記憶體沒有被釋放，導致錯誤。修改 `q_merge` 函式後， trace-03-ops 可順利通過。
:::danger
注意用語：
* memory 是「記憶體」
務必使用本課程教材規範的術語。
:::
:::info
收到，已更正
:::
原始版本：
```c
int q_merge(struct list_head *head, bool descend)
{
if (!head || list_empty(head)) {
return 0;
}
if (list_is_singular(head)) {
return 1;
}
int total_elements = 0;
queue_contex_t *context, *tmp;
struct list_head *first_queue = NULL;
list_for_each_entry_safe (context, tmp, head, chain) {
if (!first_queue) {
first_queue = context->q;
total_elements += context->size;
} else {
list_splice_init(context->q, first_queue);
context->q = NULL;
total_elements += context->size;
}
}
q_sort(first_queue, false);
return total_elements;
}
```
修改版本：
```c
int q_merge(struct list_head *head, bool descend)
{
if (!head || list_empty(head)) {
return 0;
}
queue_contex_t *base_queue = list_first_entry(head, queue_contex_t, chain);
if (list_is_singular(head)) {
return base_queue->size;
}
queue_contex_t *queue_to_merge;
struct list_head *current, *next;
list_for_each_safe (current, next, head) {
if (current == &base_queue->chain) {
continue;
}
queue_to_merge = list_entry(current, queue_contex_t, chain);
list_splice_tail_init(queue_to_merge->q, base_queue->q);
base_queue->size += queue_to_merge->size;
}
q_sort(base_queue->q, descend);
return base_queue->size;
}
```
## TODO: 留意 lab0-c 記憶體佔用分析
> 善用 valgrind, massif, perf 等工具
### 透過 Massif 分析記憶體使用量
- 參考 [alanjiang85](https://hackmd.io/@alanjian85/lab0-2023#%E9%80%8F%E9%81%8E-Massif-%E5%88%86%E6%9E%90%E8%A8%98%E6%86%B6%E9%AB%94%E4%BD%BF%E7%94%A8%E9%87%8F) 的說明，用 `trace-eg.cmd` 進行分析
- 透過 Valgrind 產生 massif 檔案
```
$ valgrind --tool=massif ./qtest -f traces/trace-eg.cmd
```
- 產生記憶體使用情形的時間分佈圖
```
$ massif-visualizer ./massif.out.59554
```
## TODO: 修正 lab0-c 網頁伺服器的整合問題並整合 coroutine 來改進性能
> 留意 I/O Multiplexing Model，務必詳閱 [Linux 核心設計: 針對事件驅動的 I/O 模型演化](https://hackmd.io/@sysprog/linux-io-model)和[並行程式設計: 排程器原理](https://hackmd.io/@sysprog/concurrency-sched)
Sign in with Wallet
Connect another wallet