---
tags: Linux_hw
---
# 2023q1 Homework1 (lab0)
contributed by < `milan0801` >
## 開發環境
```bash
$ gcc --version
gcc (Ubuntu 11.3.0-1ubuntu1~22.04) 11.3.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: 11th Gen Intel(R) Core(TM) i5-1135G7 @ 2.40GHz
CPU family: 6
Model: 140
Thread(s) per core: 2
Core(s) per socket: 4
Socket(s): 1
Stepping: 1
CPU max MHz: 4200.0000
CPU min MHz: 400.0000
BogoMIPS: 4838.40
```
## 開發過程
:::spoiler To-do List
- [ ] 修改 queue.[ch]
- [ ] 開啟 Address Sanitizer，修正 qtest 執行過程中的錯誤
- [ ] 運用 Valgrind 排除 qtest 實作的記憶體錯誤
- [ ] 透過 Massif 視覺化 “simulation” 過程中的記憶體使用量，需要設計對應的實驗
- [ ] 整合與比較 Linux kernl Linked List 的排序演算法
- [ ] 改善 web server (用 select 或 epoll)
- [ ] 研讀論文〈Dude, is my code constant time?〉
- [ ] 解釋本程式的 “simulation” 模式是如何透過以實驗而非理論分析，達到驗證時間複雜度
- [ ] 需要解釋 Student’s t-distribution 及程式實作的原理。
:::
### 修改 `queue.c`
:::danger
說好的進度呢？
:notes: jserv
:::
<s>這邊僅貼上部份 functions 在實作上須注意的地方：</s>
#### q_free
這邊原先是使用 `list_for_each_entry`，但會出錯，後來改成使用 list_for_each_entry_safe 此 macro 就成功了，是因為迴圈內會用到 free 來釋放當前節點的空間，藉由新增 safe 這個變數來紀錄下一個節點，就可以成功在釋放當前節點後還能進入下個節點。
另外，我參考其他同學的 code，如 komark06、Ji Zhuang，發現他們使用 q_release_element() 來代替 free()，但我還不太清楚這個函式的使用方式，所以暫時先不用。
:::danger
倘若參考他人的成果，務必標注。將心比心，你不會希望自己被他人用一句「其他同學」帶過吧？
:notes: jserv
:hamster: 好的，會再補上！
:::
```c
void q_free(struct list_head *l)
{
if (!l)
return;
element_t *node, *safe;
list_for_each_entry_safe (node, safe, l, list) {
free(node->value);
free(node);
}
free(l);
}
```
#### q_insert_head
這邊要注意的是，element_t 中的字串 `char *value` 也須使用 malloc 配置好空間，且若配置失敗，則須要釋放原先 `element_t` 已經配置好的空間，否則會產生 error message。
:writing_hand: 養成好習慣每次使用 malloc，都要去檢測是否有成功。
```c
bool q_insert_head(struct list_head *head, char *s)
{
element_t *node = malloc(sizeof(element_t));
if (!node) {
return false;
}
/* Allocate space for value in element_te */
int s_len = strlen(s) + 1;
node->value = malloc(s_len * sizeof(char));
if (!node->value) {
free(node);
return false;
}
memcpy(node->value, s, s_len);
list_add(&node->list, head);
return true;
}
```
#### q_reverse
原本是從佇列的尾端針對每個節點交換他們各自的 next 與 prev，但會一直出現錯誤訊息，後來發現是因為這不適用於 prev pointer 不直接連接到前一個節點的情況，這樣會無法反轉那些被跳過得節點。
```c
void q_reverse(struct list_head *head)
{
if (!head || list_empty(head))
return;
element_t *item = NULL;
struct list_head *curr = head->prev;
struct list_head *tmp = NULL;
for (; curr != head; curr = curr->next) {
tmp = curr->next;
curr->next = curr->prev;
curr->prev = tmp;
}
tmp = head->prev;
head->prev = head->next;
head->next = tmp;
}
```
不適用的情境如下圖，head 的 prev 連接到 fish，而非 meekat，如此一來 meekat 會被跳過，無法順利反轉 prev 跟 next。
之後參考 @komark06 的做法修改成：
```c
void q_reverse(struct list_head *head)
{
if (!head || list_empty(head))
return;
struct list_head *cur, *safe;
list_for_each_safe (cur, safe, head) {
list_move(cur, head);
}
}
```
他的作法是依序走訪佇列的每個節點，移除當前節點再移至佇列的 head 之後，充分利用到 list.h 提供的 API，值得學習。
#### q_descend
參考 leetcode 的提示，先對佇列進行 reverse，之後設第一個節點為 max，如果後續節點的值大於 max 的值，則以此節點取代 max 原本指向的節點；如果後續節點的值小於 max 的值，則刪除此節點。
```c
int q_descend(struct list_head *head)
{
if (!head || list_empty(head))
return 0;
q_reverse(head);
element_t *max = list_entry(head->next, element_t, list);
struct list_head *cur, *safe;
list_for_each_safe (cur, safe, head) {
element_t *cur_elem = list_entry(cur, element_t, list);
char *cur_val = cur_elem->value;
int cmp_res = strcmp(cur_val, max->value);
if (cmp_res == 0)
continue;
else if (cmp_res > 0)
max = cur_elem;
else {
list_del(cur);
free(cur_elem->value);
free(cur_elem);
}
}
q_reverse(head);
int final_cnt = q_size(head);
return final_cnt;
}
```
#### q_merge
寫函式前，先看 qtest.c 如何使用這個函式：
```c
if (current && exception_setup(true))
len = q_merge(&chain.head);
```
> 函式回傳的資料是合併後的佇列的節點數。
```c
if (q_size(&chain.head) > 1) {
chain.size = 1;
current = list_entry(chain.head.next, queue_contex_t, chain);
current->size = len;
```
> 這個函式的參數 head 跟其他函式不同，不是指到 element_t，而是 queue_contex_t，queue_contex_t 結構中的 q 指標才會指到佇列節點 element_t。
```c
struct list_head *cur = chain.head.next->next;
while ((uintptr_t) cur != (uintptr_t) &chain.head) {
queue_contex_t *ctx = list_entry(cur, queue_contex_t, chain);
cur = cur->next;
q_free(ctx->q);
free(ctx);
}
```
> 會將被合併的佇列釋放，合併時需要注意指標是否有效。
知道如何使用此函式後，可以開始撰寫了。首先，先找到第一個佇列並用一個指標 q1 指向它。之後在依序走訪後續的佇列，並用指標 q2 指向這些佇列。
走訪的過程中，會將 q2 合併到 q1 中。合併使用到的函式跟在 q_sort 使用的是同一個，參數皆為非循環的連結串列，所以這邊需要先將 q1->q->prev->next 和 q2->q->prev->next 都設為 NULL。合併完成後，因為 q2 的節點已經亂掉，可能有指向 q1 的節點，這樣釋放 q2 會導致後續存取 q1 產生 segmentation fault，所以需要將 q2 進行初始化，這邊使用 INIT_LIST_HEAD(q2->q)。
將全部 queues 都合併到 q1 後，因為 q1 的節點的 prev 指標是亂的，所以需要依序走訪設定指到前面節點。
```c
int q_merge(struct list_head *head)
{
// https://leetcode.com/problems/merge-k-sorted-lists/
if (!head || list_empty(head))
return 0;
struct list_head *cur = head->next;
queue_contex_t *q1 = list_entry(cur, queue_contex_t, chain);
if (list_is_singular(head))
return q1->size;
cur = cur->next;
while (cur != head) {
queue_contex_t *q2 = list_entry(cur, queue_contex_t, chain);
cur = cur->next;
if (!q1->q->next || !q2->q->next)
continue;
q1->q->prev->next = NULL;
q2->q->prev->next = NULL;
q1->q->next = mergeTwoLists(q1->q->next, q2->q->next);
INIT_LIST_HEAD(q2->q);
}
/* Reconnect the prev pointer */
struct list_head *prev_tmp = q1->q, *cur_tmp = q1->q->next;
while (cur_tmp->next != NULL) {
cur_tmp->prev = prev_tmp;
prev_tmp = cur_tmp;
cur_tmp = cur_tmp->next;
}
cur_tmp->next = q1->q;
q1->size = q_size(q1->q);
return q1->size;
}
```
#### q_sort
這邊使用 merge sort，除了教材有提供 merge sort 的示範程式碼外，也因為 quick sort、insertion sort、bubble sort 等常見排序演算法最差情況時間會到 $O(n^2)$ 等級，而 merge sort 最好/平均/最差皆為$O(nlog(n))$ 等級，故先用用看 merge sort。
使用 non-recursion 的方式，會在 nodes 數 為 2,000,000 的測試資料時失敗。
```c
static struct list_head *mergeTwoLists(struct list_head *list1,
struct list_head *list2)
{
struct list_head *head = NULL, **ptr = &head;
for (struct list_head **node = NULL; list1 && list2;
*node = (*node)->next) {
char *s1 = list_entry(list1, element_t, list)->value;
char *s2 = list_entry(list2, element_t, list)->value;
node = (strcmp(s1, s2) < 0) ? &list1 : &list2;
*ptr = *node;
ptr = &(*ptr)->next;
}
*ptr = (struct list_head *) ((uintptr_t) list1 | (uintptr_t) list2);
return head;
}
void q_sort(struct list_head *head)
{
if (!head || list_empty(head) || list_is_singular(head))
return;
int top = 0;
int listsSize = 0;
/* The tested queue size is 2,000,000.
* If lists size is changed to 2,000,000, it would be crashed.
*/
struct list_head *stack[1000] = {NULL};
struct list_head *lists[100000] = {NULL};
stack[top] = head->next;
head->prev->next = NULL;
while (top >= 0) {
struct list_head *left = stack[top--];
if (left) {
struct list_head *slow = left;
struct list_head *fast;
for (fast = left->next; fast && fast->next;
fast = fast->next->next) {
slow = slow->next;
}
struct list_head *right = slow->next;
slow->next = NULL;
stack[++top] = left;
stack[++top] = right;
} else {
lists[listsSize++] = stack[top--];
}
}
while (listsSize > 1) {
for (int i = 0, j = listsSize - 1; i < j; i++, j--)
lists[i] = mergeTwoLists(lists[i], lists[j]);
listsSize = (listsSize + 1) / 2;
}
head->next = lists[0];
struct list_head *ptr = head;
for (; ptr->next; ptr = ptr->next) {
ptr->next->prev = ptr;
}
ptr->next = head;
head->prev = ptr;
}
```
故參考 @komark06，改成遞迴的方式：
```c
struct list_head *merge_sort(struct list_head *head)
{
if (!head || !head->next)
return head;
struct list_head *slow = head;
struct list_head *fast;
for (fast = head->next; fast && fast->next; fast = fast->next->next) {
slow = slow->next;
}
fast = slow->next;
slow->next = NULL;
return mergeTwoLists(merge_sort(head), merge_sort(fast));
}
/* Recursive method */
void q_sort(struct list_head *head)
{
if (!head || list_empty(head) || list_is_singular(head))
return;
head->prev->next = NULL;
head->next = merge_sort(head->next);
struct list_head *cur = head;
for (; cur->next; cur = cur->next) {
cur->next->prev = cur;
}
cur->next = head;
head->prev = cur;
}
```
目前這樣在 local 端可以通過測試，但 github action 在 trace-14-perf 與 trace-17-complexity 卻失敗（89/100），詳細原因還需要再研究。
Sign in with Wallet
Connect another wallet