# 2022q1 Homework1 (lab0)
contributed by < [`Pepitaw`](https://github.com/Pepitaw/lab0-c) >
###### tags: `linux2022`
## 實驗環境
```shell
$ gcc --version
gcc (Ubuntu 9.3.0-17ubuntu1~20.04) 9.3.0
$ 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): 12
On-line CPU(s) list: 0-11
Thread(s) per core: 2
Core(s) per socket: 6
Socket(s): 1
NUMA node(s): 1
Vendor ID: GenuineIntel
CPU family: 6
Model: 158
Model name: Intel(R) Core(TM) i7-9750H CPU @ 2.60GHz
Stepping: 10
CPU MHz: 2600.000
CPU max MHz: 4500.0000
CPU min MHz: 800.0000
BogoMIPS: 5199.98
L1d cache: 192 KiB
L1i cache: 192 KiB
L2 cache: 1.5 MiB
L3 cache: 12 MiB
NUMA node0 CPU(s): 0-11
```
## 開發紀錄
:::info
作業要求
- [x] q_new: 建立新的「空」佇列
- [x] q_free: 釋放佇列所佔用的記憶體
- [x] q_insert_head: 在佇列開頭 (head) 插入 (insert) 給定的新節點 (以 LIFO 準則)
- [x] q_insert_tail: 在佇列尾端 (tail) 插入 (insert) 給定的新節點 (以 FIFO 準則)
- [x] q_remove_head: 在佇列開頭 (head) 移去 (remove) 給定的節點
- [x] q_release_element: 釋放特定節點的記憶體空間
- [x] q_size: 計算目前佇列的節點總量
- [x] q_delete_mid: 移走佇列中間的節點
- [x] q_delete_dup: 在已經排序的狀況，移走佇列中具備重複內容的節點
- [x] q_swap: 交換佇列中鄰近的節點
- [x] q_reverse: 以反向順序重新排列鏈結串列，該函式不該配置或釋放任何鏈結串列節點，換言之，它只能重排已經存在的節點
- [x] q_sort: 以遞增順序來排序鏈結串列的節點
:::
### q_new
根據 `list.h` 參考函式 `INIT_LIST_HEAD` 初始化 q ，將 q 的 `next` 與 `prev` 指向自己。
:::spoiler 實際程式碼
```clike
struct list_head *q_new()
{
struct list_head *q = malloc(sizeof(struct list_head));
if (!q)
return NULL;
INIT_LIST_HEAD(q);
return q;
}
```
:::
- 實作流程
1. 使用 `malloc` 分配記憶體空間給指標 q
2. 如果 `malloc` 分配空間失敗，會回傳 `NULL`
3. 使用 `INIT_LIST_HEAD` 初始化指標 q
### q_free
根據 `list.h` 參考函式 `list_for_each_entry_safe` ，藉由副本遍歷各個 `entry` ，不會受到移除 `entry` 的影響
:::spoiler 實際程式碼
```clike
void q_free(struct list_head *l)
{
if (!l)
return;
element_t *pos, *n;
list_for_each_entry_safe (pos, n, l, list)
q_release_element(pos);
free(l);
}
```
:::
- 實作流程
1. 若 `head` 指向 NULL 就 `return`
2. 走訪整個 `linked list` ，對每個 `entry` 呼叫 `q_release_element` 釋放其空間
3. 釋放 `head` 的記憶體空間
### q_insert_head
根據 `list.h` 參考函式 `list_add` ，將新增的 `element_t` 加到 `head` 的 `next`
:::spoiler 實際程式碼
```clike
bool q_insert_head(struct list_head *head, char *s)
{
if (!head)
return false;
element_t *e = malloc(sizeof(element_t));
if (!e)
return false;
e->value = strdup(s);
if (!e->value) {
free(e);
return false;
}
list_add(&e->list, head);
return true;
}
```
:::
- 實作流程
1. 若 `head` 指向 NULL 就回傳 `false`
2. 使用 `malloc()` 分配 `element_t` 大小的記憶體空間給 e ，若分配失敗則回傳 `false`
3. 利用 `strdup` 會用 `malloc` 分配記憶體儲存字串的特性，直接指派給 e->value
4. 若 `strdup` 分配記憶體失敗就清除 e 與回傳 `false`
5. 加入新 `entry` 到list
:::spoiler 過去嘗試與心路歷程
1. 不知道在 queue.h 有定義 element_t ，自行定義 node
```clike
bool q_insert_head(struct list_head *head, char *s)
{
struct node{
char *str;
struct list_head list;
};
struct node *n = malloc(sizeof(struct node));
strcpy(n->str, s);
list_add(&n->list, head);
return true;
}
```
2. 遇到以下問題 Segmentation fault occurred. You dereferenced a NULL or invalid pointer
發現是 e->value 未配置記憶體，利用 strdup 配置記憶體與複製 *s (規格書中提到 Memory for the new string is obtained with malloc ，有malloc仍有配置失敗的時候)
```clike
element_t *e = malloc(sizeof(element_t));
if(!e)
return false;
strcpy(e->value, s);
list_add(&e->list, head);
return true;
```
3. 去看 list_add 加入 node 的位置
```clike
struct list_head *tmp = head->next;
list_del(tmp);
list_add(tmp, head->next->next);
```
由以下結果得知，可以直接插入指定位置的下一個 `entry`
```shell
cmd> ih ant
l = [ant dolphin dolphin dolphin gerbil bear dolphin meerkat bear bear bear cat]
cmd> reverse
l = [dolphin dolphin ant dolphin gerbil bear dolphin meerkat bear bear bear cat]
```
:::
### q_insert_tail
根據 `list.h` 參考函式 `list_add_tail` ，將新增的 `element_t` 加到 `head` 的 `prev` ，其餘同 `q_insert_head`
:::spoiler 實際程式碼
```clike
bool q_insert_tail(struct list_head *head, char *s)
{
if (!head)
return false;
element_t *e = malloc(sizeof(element_t));
if (!e)
return false;
e->value = strdup(s);
if (!e->value) {
free(e);
return false;
}
list_add_tail(&e->list, head);
return true;
}
```
:::
### q_remove_head
根據 `list.h` 參考函式 `list_first_entry` ，找到第一個 `entry` ，也參考函式 `list_del` 將目標 `entry` remove ，成為單一節點
:::spoiler 實際程式碼
```clike
element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
if (!head || head->next == head)
return NULL;
element_t *e = list_first_entry(head, element_t, list);
list_del(&e->list);
if (sp) {
strncpy(sp, e->value, bufsize - 1);
sp[bufsize - 1] = '\0';
}
return e;
}
```
:::
- 實作流程
1. 如果 `head` 指向 NULL 或只有 `head` 就回傳 `NULL`
2. 利用 `list_first_entry` 找到第一個 `entry`
3. 再用`list_del` 將目標 `entry` remove ，成為單一節點
4. 若 sp 存在，複製 e->value 到 sp 並補結尾 `\0`
:::spoiler 過去嘗試與心路歷程（有問題待解）
1. 想說用 strdup 修改 sp 不但有配置記憶體，還會自動補 `\0` ，但卻報錯還不知道原因。
```clike
if(sp){
sp = strndup(e->value, bufsize - 1);
}
```
ERROR: Failed to store removed value
:::
### q_remove_tail
根據 `list.h` 參考函式 `list_last_entry` ，找到最後一個 `entry` ，其餘與 `q_remove_head` 相同
:::spoiler 實際程式碼
```clike
element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
if (!head || head->next == head)
return NULL;
element_t *e = list_last_entry(head, element_t, list);
list_del(&e->list);
if (sp) {
strncpy(sp, e->value, bufsize - 1);
sp[bufsize - 1] = '\0';
}
return e;
}
```
:::
### q_size
根據 `list.h` 參考函式 `list_for_each()` 遍歷各個 `entry`
:::spoiler 實際程式碼
```clike
int q_size(struct list_head *head)
{
if (!head)
return false;
int i = 0;
struct list_head *lh;
list_for_each (lh, head)
i++;
return i;
}
```
:::
- 實作流程
1. 若傳入的 `head` 指向 NULL 就回傳 `false`
2. 每經過一個 `entry` i 就加一，最後即為size
### q_delete_mid
依據「龜兔賽跑」[Floyd’s Cycle detection](https://en.wikipedia.org/wiki/Cycle_detection)，當 `rabbit` 跑完 list 時， `turtle` 跑到一半的特性，來尋找中間的節點
:::spoiler 實際程式碼
```clike
bool q_delete_mid(struct list_head *head)
{
struct list_head *fast = head->next, *slow = head->next;
for (; fast != head->prev && fast->next != head->prev;
fast = fast->next->next, slow = slow->next)
;
/*while(fast != NULL && fast->next != NULL){
fast = fast->next->next;
slow = slow->next;
}*/
slow->prev->next = slow->next;
slow->next->prev = slow->prev;
q_release_element(list_entry(slow, element_t, list));
return true;
}
```
:::
- 實作流程
1. 設置兩個 pointer ， fast 一次跑一個 `entry` ， slow 跑兩個 `entry`
2. 兩 pointer 開始遍歷 list ，當其中一個 pointer 跑完 list 時結束
3. 利用 q_release_element 對 slow 做 delete
:::spoiler 過去嘗試與心路歷程
1. 實做龜兔賽跑找中間節點，遇到以下問題
ERROR: Time limit exceeded. Either you are in an infinite loop, or your code is too inefficient
因為迴圈結束方式是判斷是否為 NULL ，但 circular linked list 是頭尾相接不會 NULL
```clike
for(struct list_head *fast = head, *slow = head; fast && fast->next; \
fast = fast->next->next, slow = slow->next);
```
:::
### q_delete_dup
:::spoiler 實際程式碼
```clike
bool q_delete_dup(struct list_head *head)
{
if (!head)
return false;
element_t *pos, *n;
bool used = false;
list_for_each_entry_safe (pos, n, head, list) {
if (pos->list.next != head &&
!strcmp(pos->value,
list_entry(pos->list.next, element_t, list)->value)) {
list_del(&pos->list);
q_release_element(pos);
used = true;
} else if (used) {
list_del(&pos->list);
q_release_element(pos);
used = false;
}
}
return true;
}
```
:::
- 實作流程
1. 如果 `head` 指向 NULL 就回傳 `false`
2. 利用 `list_for_each_entry_safe` 遍歷各個 `entry`
3. 利用 `strcmp` 比較 pos 跟下一個 `entry` 的 value 是否相同
4. 若 value 相同且 pos 不是結尾，就將 pos delete
5. 用 use 去紀錄該 `entry` 是否跟以刪除 `entry` 有相同的 value
### q_swap
根據 `list.h` 參考函式 `list_move_tail` 將 `entry` 放到 `head->prev`
:::spoiler 實際程式碼
```clike
void q_swap(struct list_head *head)
{
bool odd = q_size(head) & 0x01;
for (int i = q_size(head) >> 1; i > 0; i--) {
list_move_tail(head->next->next, head);
list_move_tail(head->next, head);
}
if (odd)
list_move_tail(head->next, head);
}
```
:::
- 實作流程
1. 先將第二個的 `entry` 放到尾巴
2. 再將第一個的 `entry` 放到尾巴
3. 總共做"總數的一半"次
4. 若總數為奇數，就要再做一次流程二
:::spoiler 過去嘗試與心路歷程 （有問題待解）
1. 想使用 `list.h` 函式 `list_swap` ，但發現未定義
我是在 linux kernel 版本 5.13.0 查到的函式，與我的 linux kernel 5.13.0-30-generic 相符，但還是找不到原因
```clike
void q_shuffle(struct list_head *head)
{
srand( time(NULL) );
for (int i = q_size(head); i > 0; i--) {
struct list_head *tmp = head->next;
for (int x = rand()%i; x > 0; x--){
tmp = tmp->next;
}
list_swap(tmp, head->prev);
//list_move_tail(tmp, head);
}
}
```
```shell
queue.c: In function ‘q_shuffle’:
queue.c:347:2: error: implicit declaration of function ‘list_swap’ [-Werror=implicit-function-declaration]
347 | list_swap(tmp, head->prev);
| ^~~~~~~~~
cc1: all warnings being treated as errors
make: *** [Makefile:50：queue.o] 錯誤 1
```
:::
### q_reverse
:::spoiler 實際程式碼
```clike
void q_reverse(struct list_head *head)
{
if (!head || head->next->next == head)
return;
struct list_head *pos = head->prev;
for (int i = q_size(head); i > 1; i--)
list_move_tail(pos->prev, head);
}
```
:::
- 實作流程
1. 若 `head` 指向 NULL 或 list 只有一個 `entry` 就回傳 NULL
2. 從尾巴開始反向遍歷，將 `entry` 依序放到尾巴
### q_sort
:::spoiler 實際程式碼
```clike
struct list_head *mergesort(struct list_head *node)
{
if (!node || !node->next)
return node;
struct list_head *fast = node, *slow = node;
for (; fast->next && fast->next->next;
fast = fast->next->next, slow = slow->next)
;
fast = slow->next;
slow->next = NULL;
struct list_head *l1 = mergesort(node);
struct list_head *l2 = mergesort(fast);
struct list_head t_head, *tmp = &t_head;
while (l1 && l2) {
if (strcmp(list_entry(l1, element_t, list)->value,
list_entry(l2, element_t, list)->value) > 0) {
tmp->next = l2;
l2 = l2->next;
} else {
tmp->next = l1;
l1 = l1->next;
}
tmp = tmp->next;
}
if (l1)
tmp->next = l1;
else
tmp->next = l2;
return t_head.next;
}
void q_sort(struct list_head *head)
{
if (!head || !head->next)
return;
head->prev->next = NULL;
struct list_head *list = head->next;
list = mergesort(list);
head->next = list;
struct list_head *i = head;
while (i->next != NULL) {
i->next->prev = i;
i = i->next;
}
head->prev = i;
i->next = head;
}
```
:::
- 實作流程
1. 若 `head` 指向 NULL 或 list 沒有 `entry` 就 return
2. 將尾巴的 next 指向 NULL，切斷 next 方向的 circular
3. 將去除 `head` 的 list 進行 mergesort
- 以下為 mergesort
4. 利用「龜兔賽跑」將 list 從中間一分為二
5. 再用 `strcmp` 比較大小，依小到大排列
6. 將 `head` 指向 排序好的 list
7. 最後利用 `list` 的 `next->prev` 將所有 `prev` 重新排列
## 理解 [Linux 核心中的排序實作](https://github.com/torvalds/linux/blob/master/lib/list_sort.c)
:::spoiler merge (pointer to pointer version)
```clike
static struct list_head *merge(void *priv, list_cmp_func_t cmp,
struct list_head *a, struct list_head *b)
{
struct list_head *head, **tail = &head;
for (;;) {
/* if equal, take 'a' -- important for sort stability */
if (cmp(priv, a, b) <= 0) {
*tail = a;
tail = &a->next;
a = a->next;
if (!a) {
*tail = b;
break;
}
} else {
*tail = b;
tail = &b->next;
b = b->next;
if (!b) {
*tail = a;
break;
}
}
}
return head;
}
```
:::
- 程式碼理解
1. 用 pointer to pointer 指向 a 與 b 之間較小的
2. 但沒有處理 prev 的部份
:::spoiler merge_final (pointer version)
```clike
static void merge_final(void *priv, list_cmp_func_t cmp, struct list_head *head,
struct list_head *a, struct list_head *b)
{
struct list_head *tail = head;
u8 count = 0;
for (;;) {
/* if equal, take 'a' -- important for sort stability */
if (cmp(priv, a, b) <= 0) {
tail->next = a;
a->prev = tail;
tail = a;
a = a->next;
if (!a)
break;
} else {
tail->next = b;
b->prev = tail;
tail = b;
b = b->next;
if (!b) {
b = a;
break;
}
}
}
/* Finish linking remainder of list b on to tail */
tail->next = b;
do {
/*
* If the merge is highly unbalanced (e.g. the input is
* already sorted), this loop may run many iterations.
* Continue callbacks to the client even though no
* element comparison is needed, so the client's cmp()
* routine can invoke cond_resched() periodically.
*/
if (unlikely(!++count))
cmp(priv, b, b);
b->prev = tail;
tail = b;
b = b->next;
} while (b);
/* And the final links to make a circular doubly-linked list */
tail->next = head;
head->prev = tail;
}
```
:::
- 程式碼理解
1. 比較 a 跟 b 的大小，用 tail 的 next 指向比較小的 entry
2. 一路遍歷兩個 linked list 直到其中一個 linked list 結束(a 或 b 指向 NULL)
3. 用 b 指向還未走到尾巴的 linked list (未經過的 entry)
4. 用 tail 的 next 指向剩下的 entry
5. 遍歷完剩下的 entry ，並用 count 紀錄剩下的 entry 數量
6. 利用 unlikely 將 count 轉成 bool
7. 頭尾相接成為 circular
- 程式碼差異
1. 在每次 merge 時就處理好 prev 與 next 的 link
我則是只看 next ，將 linked list 用 next 排列完後，再一次將所有的 prev 處理好
2. 計算兩個 linked list 的 merge 是否 entry 數量相近，我則沒有考慮
:::spoiler list_sort
```clike
void list_sort(void *priv, struct list_head *head, list_cmp_func_t cmp)
{
struct list_head *list = head->next, *pending = NULL;
size_t count = 0; /* Count of pending */
if (list == head->prev) /* Zero or one elements */
return;
/* Convert to a null-terminated singly-linked list. */
head->prev->next = NULL;
do {
size_t bits;
struct list_head **tail = &pending;
/* Find the least-significant clear bit in count */
for (bits = count; bits & 1; bits >>= 1)
tail = &(*tail)->prev;
/* Do the indicated merge */
if (likely(bits)) {
struct list_head *a = *tail, *b = a->prev;
a = merge(priv, cmp, b, a);
/* Install the merged result in place of the inputs */
a->prev = b->prev;
*tail = a;
}
/* Move one element from input list to pending */
list->prev = pending;
pending = list;
list = list->next;
pending->next = NULL;
count++;
} while (list);
/* End of input; merge together all the pending lists. */
list = pending;
pending = pending->prev;
for (;;) {
struct list_head *next = pending->prev;
if (!next)
break;
list = merge(priv, cmp, pending, list);
pending = next;
}
/* The final merge, rebuilding prev links */
merge_final(priv, cmp, head, pending, list);
}
```
:::
- 程式碼理解
1. 用 head->next == head->prev 去判斷是否只有一個 entry 或沒有 entry
2. 將 circular 的 next 部份斷開
- 程式碼差異
## 運用 Valgrind 排除 qtest 實作的記憶體錯誤
:::info
作業目標
- [ ] 運用 Valgrind 排除 qtest 實作的記憶體錯誤，並透過 Massif 視覺化 “simulation” 過程中的記憶體使用量，需要設計對應的實驗
:::
==更新中==
:::spoiler
```shell
$ valgrind -q --leak-check=full ./qtest -f traces/trace-01-ops.cmd
==2951== 5 bytes in 1 blocks are still reachable in loss record 1 of 2
==2951== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==2951== by 0x4A5250E: strdup (strdup.c:42)
==2951== by 0x1108BE: linenoiseHistoryAdd (linenoise.c:1236)
==2951== by 0x111451: linenoiseHistoryLoad (linenoise.c:1325)
==2951== by 0x10C6B0: main (qtest.c:951)
==2951==
==2951== 160 bytes in 1 blocks are still reachable in loss record 2 of 2
==2951== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==2951== by 0x11087E: linenoiseHistoryAdd (linenoise.c:1224)
==2951== by 0x111451: linenoiseHistoryLoad (linenoise.c:1325)
==2951== by 0x10C6B0: main (qtest.c:951)
```
```clike
linecopy = strdup(line);
```
:::
## 在 qtest 提供新的命令 shuffle
:::info
作業目標
- [x] 在 `qtest` 提供新的命令 `shuffle` ，允許藉由 [Fisher–Yates shuffle](https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle) 演算法，對佇列中所有節點進行洗牌 (shuffle) 操作
- [ ] 解釋 [select](https://man7.org/linux/man-pages/man2/select.2.html) 系統呼叫在本程式的使用方式，並分析 console.c 的實作，說明其中運用 CS:APP [RIO](http://csapp.cs.cmu.edu/2e/ch10-preview.pdf) 套件 的原理和考量點。可對照參考 CS:APP [第 10 章重點提示](https://hackmd.io/@sysprog/H1TtmVTTz)
:::
:::spoiler 程式碼
```clike
void q_shuffle(struct list_head *head)
{
srand(time(NULL));
for (int i = q_size(head); i > 0; i--) {
struct list_head *tmp = head->next, *tail = head->prev;
for (int x = rand() % i; x > 0; x--)
tmp = tmp->next;
list_del(tail);
list_add(tail, tmp->prev);
list_move_tail(tmp, head);
}
}
```
:::
- 實作流程
1. 將 `linked list` 的 size 不斷減一，作為隨機變數的範圍
2. 遍歷去找隨機變數所指定的 `entry`
3. 用 `list_del` 將尾巴成為獨立的 `entry` ，將尾巴用 `list_add` 加到目標 `entry` 的下一個 `entry` ，再將目標 `entry` 移動到尾巴，作為交換
## 在 qtest 提供新的命令 web
## 參考資料
- HackMD 模板參考 [`Risheng1128`](https://hackmd.io/kZtEa_LdSGKVQGg8jczrLQ?view)
- Mergesort 分割部分 參考 [`Risheng1128`](https://hackmd.io/kZtEa_LdSGKVQGg8jczrLQ?view)
- [K01: lab0](https://hackmd.io/@sysprog/linux2022-lab0)
- [你所不知道的 C 語言: linked list 和非連續記憶體](https://hackmd.io/@sysprog/c-linked-list)
- [Floyd’s Cycle detection](https://en.wikipedia.org/wiki/Cycle_detection)
- [quick-sort.c](https://github.com/sysprog21/linux-list/blob/master/examples/quick-sort.c)
Sign in with Wallet
Connect another wallet