# 2024q1 Homework1 (lab0)
contributed by < [`Hualing-Chiu`](https://github.com/Hualing-Chiu) >
## 開發環境
```bash
$ gcc --version
gcc (Ubuntu 11.4.0-1ubuntu1~22.04) 11.4.0
$ lscpu
Architecture: x86_64
CPU op-mode(s): 32-bit, 64-bit
Address sizes: 39 bits physical, 48 bits virtual
Byte Order: Little Endian
CPU(s): 8
On-line CPU(s) list: 0-7
Vendor ID: GenuineIntel
Model name: Intel(R) Core(TM) i7-7700 CPU @ 3.60GHz
CPU family: 6
Model: 158
Thread(s) per core: 2
Core(s) per socket: 4
Socket(s): 1
Stepping: 9
CPU max MHz: 4200.0000
CPU min MHz: 800.0000
BogoMIPS: 7200.00
```
## 佇列實作與程式碼改進
### `q_new`
透過 `malloc` 配置記憶體，並使用 `list.h` 內提供的`INIT_LIST_HEAD` 去初始化 `struct list_head`
> 需判斷是否有成功配置記憶體位址給指標
:::danger
改進你的漢語表達。
:::
```diff
struct list_head *q_new()
{
struct list_head *new = malloc(sizeof(struct list_head));
+ if(!new)
+ new = NULL;
INIT_LIST_HEAD(new); // use the function in list.h
return new;
}
```
:::danger
無論標題和內文中，中文和英文字元之間要有空白字元
> 已修正 [name=Sheena Chiu]
:::
### `q_free`
使用 `list.h` 提供的 `list_for_each_entry_safe` 走訪包含 `struct list_head` 的另外一個結構之 entry ，並透過額外的 `safe` 紀錄每個 iteration 所操作的節點的下一個節點。
```c
void q_free(struct list_head *head)
{
if(head){
element_t *entry, *safe;
list_for_each_entry_safe(entry, safe, head, list){
q_release_element(entry);
}
free(head);
}
}
```
### `q_insert_head`
使用 `strncpy` 而非 `strcpy` 來達成字串複製
> 因為`strcpy`可能會造成 buffer overflow 的問題
當 `node->value` 沒有成功配置記憶體位址的話，需要 free 掉此節點，否則在執行 `git commit -a` 時會出現 memory leak 的錯誤。
```diff
bool q_insert_head(struct list_head *head, char *s)
{
if (!head)
return false;
element_t *node = malloc(sizeof(element_t));
if (!node)
return false;
int slen = strlen(s) + 1;
node->value = malloc(slen * sizeof(char));
if (node->value) {
- strcpy(node->value, s);
+ strncpy(node->value, s, slen);
list_add(&node->list, head);
return true;
} else {
+ free(node);
return false;
}
return false;
}
```
:::danger
使用 `git diff` 或 `diff -u` 命令來產生程式碼之間的變革列表，不要憑感覺填入，注意位移量。
:::
### `q_insert_tail`
做法跟 `q_insert_head()` 一樣，`list_add()` 改成 `list_add_tail()` 即可。
### `q_remove_head`
使用 `list.h` 提供的`list_first_entry` 找出佇列中第一個 `element`，再使用 `strncpy` 複製此 `element` 的 value 到 `sp` 中。
> 要注意需手動把<s>空字元</s>結尾字元 '\0' 加上去
:::danger
`'\0'` 不是「空」字元，你會把數字 0 叫做「空」數字嗎？
:::
```c
element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
if (!head || list_empty(head))
return NULL;
element_t *node = list_first_entry(head, element_t, list);
list_del(&node->list);
if (sp && bufsize) {
strncpy(sp, node->value, bufsize);
sp[bufsize - 1] = '\0';
}
return node;
}
```
### `q_remove_tail`
做法與 `q_remove_head` 一樣，`list_first_entry` 改成 `list_last_entry` 即可。
### `q_size`
```c
int q_size(struct list_head *head)
{
if(!head)
return 0;
int count = 0;
struct list_head *node;
list_for_each(node, head){
count++;
}
return count;
}
```
### `q_delete_mid`
:::danger
給定的佇列具備環狀且雙向的特性，不該說「反方向」，改進你的漢語表達，使用精準的詞彙。
:::
從 `list_head` 結構可知此佇列為雙向鏈結串列，除了使用快慢指標去實作之外，也可以使用兩個指標指向串列的頭尾，分別朝<s>反方向</s> 走訪節點，需要考慮兩個狀況:
* 節點個數為奇數，則兩個指標會相遇，因此判斷 `left != right`
* 節點個數為偶數，則兩個指標會相鄰，因此判斷 `left->next != right`
```c
bool q_delete_mid(struct list_head *head)
{
if (!head || list_empty(head))
return false;
struct list_head *left = head->prev;
struct list_head *right = head->next;
while (left != right && left->next != right) {
left = left->prev;
right = right->next;
}
list_del(right);
element_t *element = list_entry(right, element_t, list);
q_release_element(element);
return true;
}
```
### `q_delete_dup`
此函式目的為刪除佇列中出現重複字串的節點，使用 `list_for_each_entry_safe` 迭代去紀錄下個節點，當遇到下個節點與當前節點字串相同時，刪除並釋放記憶體。
而須注意的是當刪除完後續重複節點時，當前指向的節點也必須刪除，因此使用了 `flag` 去紀錄該節點是否刪除。
```c
bool q_delete_dup(struct list_head *head)
{
// https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/
if (!head || list_empty(head)) {
return false;
}
element_t *cur, *next;
bool flag = false;
list_for_each_entry_safe (cur, next, head, list) {
if (&next->list != head && !strcmp(cur->value, next->value)) {
list_del(&cur->list);
q_release_element(cur);
flag = true;
} else if (flag) {
list_del(&cur->list);
q_release_element(cur);
flag = false;
}
}
return true;
}
```
### `q_swap`
當實作到 `q_reverseK` 時，可以發現 `q_swap` 其實就是 `q_reverseK` 的其中一種例子，因此直接套用 `q_reverseK` 的內容即可。
```c
/* Swap every two adjacent nodes */
void q_swap(struct list_head *head)
{
q_reverseK(head, 2);
}
```
### `q_reverse`
:::danger
給定的佇列具備環狀且雙向的特性，不該說「反向」，改進你的漢語表達，使用精準的詞彙。
:::
利用 `list.h` 內提供的 `list_for_each_safe` 去走訪每個節點，使用 `list_move` 將節點從原本的` linked list` 移動到另一個 `linked list head` 的開頭，就能達成<s>反向順序</s> 重新排列。
```c
struct list_head *node, *safe;
list_for_each_safe(node, safe, head){
list_move(node, head);
}
```
:::danger
無論標題和內文中，中文和英文字元之間要有空白字元
:::
### `q_reverseK`
使用 `count` 變數紀錄已走訪的節點個數，當 `count == 0` 時，使用 `list_cut_position` 切斷目前節點位址並放到 `tmp` 上，再使用前面實作好的 `q_reverse` 對 `tmp` 進行反轉，最後用 `list_splice` 把 `tmp` 接回 `tmp_head` 上。
```c
void q_reverseK(struct list_head *head, int k)
{
// https://leetcode.com/problems/reverse-nodes-in-k-group/
if (!head || list_empty(head))
return;
int count = k;
struct list_head *node, *safe, tmp, *tmp_head;
tmp_head = head;
INIT_LIST_HEAD(&tmp);
list_for_each_safe (node, safe, head) {
count--;
if (count == 0) {
count = k;
list_cut_position(&tmp, tmp_head, node);
q_reverse(&tmp);
list_splice(&tmp, tmp_head);
tmp_head = safe->prev;
}
}
}
```
### `q_sort`
使用的排序演算法為 `Merge Sort`，首先使用 `NULL` 將最後一個節點的 `next` 與 `head` 斷開，接著使用 `mergeSort` 函式找出中間節點，分成左右兩段 `list`
```c
head->prev->next = NULL;
head->next = mergeSort(head->next);
```
實作完 `mergeSort` 後會回傳排序好的指標串列，但由於先前使用 `NULL` 將最後一個節點與 `head` 斷開，因此需要手動將 `head` 跟最後一個 `node` 的 `prev` 及 `next` 都接回去。
```c
struct list_head *last = head;
while (last->next)
last = last->next;
head->prev = last;
last->next = head;
head->next->prev = head;
```
:::danger
你如何確保目前的測試已涵蓋排序演算法的最差狀況？
:::
### `mergeSort`
採用遞迴呼叫搭配快慢指標的概念將指標串列左右對半分，直到分割成單一節點再使用 `mergeTwoLists` 函式合併成排序好的串列。
```c
struct list_head *mergeSort(struct list_head *head)
{
if (!head->next)
return head;
struct list_head *slow = head;
for (struct list_head *fast = head; fast && fast->next;
fast = fast->next->next)
slow = slow->next;
slow->prev->next = NULL;
struct list_head *left, *right;
left = mergeSort(head);
right = mergeSort(slow);
return mergeTwoLists(left, right);
}
```
### `mergeTwoLists`
此函式的目的是依照字串大小順序合併兩個指標串列。
參照 [你所不知道的C語言：linked list 和非連續記憶體](https://hackmd.io/@sysprog/c-linked-list#%E6%A1%88%E4%BE%8B%E6%8E%A2%E8%A8%8E-LeetCode-21-Merge-Two-Sorted-Lists) 提供的較直觀的做法進行修改，但程式碼會顯的冗長，因尚未完整研讀 `list_sort.c`，之後改進並嘗試引入 `list_sort.c`。
```c
struct list_head *mergeTwoLists(struct list_head *L1, struct list_head *L2)
{
struct list_head *head, *ptr;
if (strcmp(list_entry(L1, element_t, list)->value,
list_entry(L2, element_t, list)->value) <= 0) {
head = L1;
ptr = head;
L1 = L1->next;
} else {
head = L2;
ptr = head;
L2 = L2->next;
}
while (L1 && L2) {
if (strcmp(list_entry(L1, element_t, list)->value,
list_entry(L2, element_t, list)->value) <= 0) {
ptr->next = L1;
L1->prev = ptr;
L1 = L1->next;
} else {
ptr->next = L2;
L2->prev = ptr;
L2 = L2->next;
}
ptr = ptr->next;
}
if (L1) {
ptr->next = L1;
L1->prev = ptr;
} else {
ptr->next = L2;
L2->prev = ptr;
}
head->prev = NULL;
return head;
}
```
### `q_descend`
> commit [f766e18](https://github.com/Hualing-Chiu/lab0-c/commit/f766e18072c8554bab111e8ed1a193d0927596e7)
從指標串列尾端走訪至 `head`，若下一個節點小於當前節點的 `value`，則刪除下一個節點。
### `q_merge`
```c
int q_merge(struct list_head *head, bool descend)
{
if (!head || list_empty(head))
return 0;
if (list_is_singular(head))
return q_size(list_first_entry(head, queue_contex_t, chain)->q);
queue_contex_t *q1 = container_of(head->next, queue_contex_t, chain);
for (struct list_head *cur = head->next->next; cur != head;
cur = cur->next) {
queue_contex_t *q = container_of(cur, queue_contex_t, chain);
list_splice_init(q->q, q1->q);
q->size = 0;
}
q_sort(q1->q, false);
q1->size = q_size(q1->q);
return q1->size;
}
```
## Valgrind + 自動測試程式
參照[ Massif: a heap profiler](https://valgrind.org/docs/manual/ms-manual.html)，Massif 可以量測程式用了多少的 heap memory，除了可以幫忙加速程式，讓程式可以跟機器快取有更好的互動且避免 paging 發生，還可以減少耗盡 swap space 的機會。
參考 [var-x](https://hackmd.io/@vax-r/linux2024-homework1#Massif) 的測試步驟，首先先在 Makefile 中新增以下指令：
```diff
+ check-massif: qtest
+ valgrind --tool=massif ./$< -v 3 -f traces/trace-massif.cmd
```
`trace-massif.cmd` 是我們自己定義的 trace 檔，裡面的內容可以複製 `trace-17-complexity.cmd`，如果只要測試 `q_insert_head` 的話，稍微修改一下 `trace-17-complexity.cmd` 的內容即可。
```=
# Test if time complexity of q_insert_tail, q_insert_head, q_remove_tail, and q_remove_head is constant
option simulation 1
it
option simulation 0
```
接著執行 `make check-massif` 後可以獲得一個輸出檔案為 `massif.out.xxxxx`，執行 `ms_print massif.out.xxxxx` 可以顯示程式執行期間的記憶體消耗圖表，可以讓 user 更容易閱讀。
```
MB
1.231^ #
| #
| #
| # :: : :
| # : : :
| # : : :
| # : : :
| # @@ : : :
| # @ : : : :
| # :: :: @ : : : : :
| # : : @ : : :: : : : :
| # : : @ : : : : : : :
| # : : :@ : : ::: : :: :@@ @@ : : :
| # : : :@ :: :: : : : : : :@ :: @ : : ::: :
| # : : :@ :::: : : : : : : :@ : @ ::: : :: :
| # : : :@ : :: : : : : : : :@ : :@ :::::: :: : :
| # ::: : :@ : :: : :: : : : : : : :@ : ::@ :::: : :: :: :
| # : : : :@ : :: : : : : : : :::: :@ : ::@ :::: : :: :: ::@@:
| # : : : :@ :: : :: : : : : : : :: : :@ : ::@ :::: : : :: ::@ :
| # : : ::: :@ :::: ::::: : :: : : : :: : :@ : ::@ :::: ::: ::: ::@ :
0 +----------------------------------------------------------------------->Gi
0 14.71
Number of snapshots: 51
Detailed snapshots: [1 (peak), 8, 31, 35, 48]
```
以上圖表顯示 Massif 對這個程式做了56次的 snapshot，而 Massif 在 heap allocation/deallocation 時才會做 snapshot，但隨著程式運行時間增加，Massif 會減少 snapshot 的次數。
* `:` 是 normal snapshot
* `@` 是 detailed snapshots
* `#` 是 peak snapshot，紀錄 memory 消耗最大的時候
如果想要更直觀去看記憶體用量的話，可以執行 `massif-visualizer massif.out.xxxxx`，會顯示出以下圖形：
:::danger
只要摘錄你認為值得討論的訊息片段即可。
:::
## 研讀 Linux 核心原始程式碼 [lib/list_sort.c](https://github.com/torvalds/linux/blob/master/lib/list_sort.c) 並嘗試引入
將 `list_sort.c` 跟 `list_sort.h` 引入專案中。
一開始會遇到 include 相關的錯誤，檢查是否引入多餘的標頭檔，將不需要用到的全部刪除。
```diff
- #include <linux/bug.h>
- #include <linux/compiler.h>
- #include <linux/export.h>
+ #include "list_sort.h"
```
再來則會遇到 `unknown type name ‘u8’` 的錯誤，在 [/include/linux/types.h](https://github.com/torvalds/linux/blob/master/include/linux/types.h) 可以發現 `u8` 被定義為 `uint8_t`，因此將型別宣告改成 `uint8_t`。
```diff
+ uint8_t count = 0;
```
再來處理 `cmp` 參數，list_sort.c 的設計是傳入 cmp 比較函式，這邊我參考 [gaberplaysgame](https://hackmd.io/@GaberPlaysGame/linux2023-lab0#%E5%BC%95%E9%80%B2-liblist_sortc) 實作的 `q_list_cmp` 函式放入 `list_sort.c` 中，並刪掉 `priv` 與 `cmp` 參數。
```c
__attribute__((nonnull(1, 2))) int q_list_cmp(const struct list_head *a,
const struct list_head *b)
{
element_t *element_a = list_entry(a, element_t, list); // cppcheck-suppress nullPointer
element_t *element_b = list_entry(b, element_t, list); // cppcheck-suppress nullPointer
int res = strcmp(element_a->value, element_b->value);
return res;
}
```
接著在 `qtest.c` 中加入一個新的函式 `do_lsort` ，寫法與 `do_sort` 大同小異，差異在呼叫的函式需改成 Linux 核心風格的 `list_sort` 函式。
在 `qtest.c` 中新增 `lsort` <s>指令</s> 命令
:::danger
command 的翻譯是「命令」，而非「指令」(instruction)
:::
```diff
+ ADD_COMMAND(lsort, "Sort queue in ascending order by using Linux kernel sorting algorithm", "");
```
TODO: 使用 perf 分析效能
Sign in with Wallet
Connect another wallet