# 2022q1 Homework1 (labc0)
contributed by < `void110916` >
## 實驗環境
~~~shell
$ gcc --version
gcc (Ubuntu 9.3.0-17ubuntu1~20.04) 9.3.0
$ uname -a
Linux void-pc 5.13.0-28-generic #31~20.04.1-Ubuntu SMP Wed Jan 19 14:08:10 UTC 2022 x86_64 x86_64 x86_64 GNU/Linux
$ 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-8750H CPU @ 2.20GHz
Stepping: 10
CPU MHz: 2200.000
CPU max MHz: 4100.0000
CPU min MHz: 800.0000
BogoMIPS: 4399.99
Virtualization: VT-x
L1d cache: 192 KiB
L1i cache: 192 KiB
L2 cache: 1.5 MiB
L3 cache: 9 MiB
NUMA node0 CPU(s): 0-11
~~~
## 作業要求
- [x] 在 GitHub 上 fork [lab0-c](https://github.com/sysprog21/lab0-c)
* 參閱 [Git 教學和 GitHub 設定指引](https://hackmd.io/@sysprog/git-with-github) ^附教學影片^
- [x] 依據上述指示著手修改 `queue.[ch]` 和連帶的檔案，測試後用 Git 管理各項修改，要能滿足 `$ make test` 自動評分系統的所有項目。
- [x] 在提交程式變更前，務必詳閱 [如何寫好 Git Commit Message](https://blog.louie.lu/2017/03/21/%E5%A6%82%E4%BD%95%E5%AF%AB%E4%B8%80%E5%80%8B-git-commit-message/)
:::spoiler `queue.c`實做
- [x] q_new: 建立空 (empty) 佇列
- [x] q_free: 釋放所有被佇列使用的空間
- [x] q_insert_head: 從佇列開頭插入新節點
- [x] q_insert_tail: 從佇列結尾插入新節點
- [x] q_remove_head: 從佇列開頭**移除**新節點
- [x] q_remove_tail: 從佇列結尾**移除**新節點
- [x] q_size: 回傳佇列個數
- [x] q_delete_mid: **刪除**佇列中間的節點
- [x] q_delete_dup: **刪除**佇列中重複字串的節點
- [x] q_swap: 交換鄰近的節點
- [x] q_reverse: 反向排列佇列
- [x] q_sort: 以升幕排列佇列
:::
- [x] 詳閱「[你所不知道的 C 語言: linked list 和非連續記憶體](https://hackmd.io/@sysprog/c-linked-list)」並應用裡頭提及的手法，例如 pointer to pointer (指向某個指標的指標，或說 indirect pointer)，讓程式碼更精簡且有效
- [ ] 研讀 Linux 核心原始程式碼的 [lib/list_sort.c](https://github.com/torvalds/linux/blob/master/lib/list_sort.c) 並嘗試引入到 `lab0-c` 專案，比較你自己實作的 merge sort 和 Linux 核心程式碼之間效能落差
- [ ] 在 `qtest` 提供新的命令 `shuffle`，允許藉由 [Fisher–Yates shuffle](https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle) 演算法，對佇列中所有節點進行洗牌 (shuffle) 操作
- [ ] 在 `qtest` 提供新的命令 `web`，提供 web 伺服器功能，注意: web 伺服器運作過程中，`qtest` 仍可接受其他命令
- [ ] 可依據前述說明，嘗試整合 [tiny-web-server](https://github.com/7890/tiny-web-server)
- [ ] 除了修改程式，也要編輯「[作業區](https://hackmd.io/@sysprog/linux2022-homework1)」，增添開發紀錄和 GitHub 連結，除了提及你如何逐步達到自動評分程式的要求外，共筆也要涵蓋以下:
- [ ] 開啟 [Address Sanitizer](https://github.com/google/sanitizers/wiki/AddressSanitizer)，修正 `qtest` 執行過程中的錯誤
- [ ] 先執行 `qtest` 再於命令提示列輸入 `help` 命令，會使 開啟 [Address Sanitizer](https://github.com/google/sanitizers/wiki/AddressSanitizer) 觸發錯誤，應予以排除
- [ ] 運用 Valgrind 排除 `qtest` 實作的記憶體錯誤，並透過 Massif 視覺化 "simulation" 過程中的記憶體使用量，需要設計對應的實驗
- [ ] 解釋 [select](http://man7.org/linux/man-pages/man2/select.2.html) 系統呼叫在本程式的使用方式，並分析 [console.c](https://github.com/sysprog21/lab0-c/blob/master/console.c) 的實作，說明其中運用 CS:APP [RIO 套件](http://csapp.cs.cmu.edu/2e/ch10-preview.pdf) 的原理和考量點。可對照參考 [CS:APP 第 10 章重點提示](https://hackmd.io/@sysprog/H1TtmVTTz)
- [ ] 研讀論文〈[Dude, is my code constant time?](https://eprint.iacr.org/2016/1123.pdf)〉，解釋本程式的 "simulation" 模式是如何透過以實驗而非理論分析，達到驗證時間複雜度，需要解釋 [Student's t-distribution](https://en.wikipedia.org/wiki/Student%27s_t-distribution) 及程式實作的原理。注意：現有實作存在若干致命缺陷，請討論並提出解決方案;
- [ ] 指出現有程式的缺陷 (提示: 和 [RIO 套件](http://csapp.cs.cmu.edu/2e/ch10-preview.pdf) 有關) 或者可改進之處 (例如更全面地使用 Linux 核心風格的鏈結串列 API)，嘗試實作並提交 pull request
## Knowledge in This Homeworks
[Linux 核心原始程式碼巨集: container_of](https://hackmd.io/@sysprog/linux-macro-containerof): 如何取得該子結構的父結構
## 程式開發紀錄
### q_new
::: spoiler 問題程式
問題連結：[記憶體釋放錯誤](#記憶體釋放錯誤)
```c
struct list_head *q_new()
{
struct list_head *q_head = malloc(sizeof(struct list_head));
if (!q_head)
return NULL;
INIT_LIST_HEAD(q_head);
return q_head;
}
```
:::
修正後程式：
```c
struct list_head *q_new()
{
struct list_head *q_head = malloc(sizeof(struct list_head));
INIT_LIST_HEAD(q_head);
return q_head;
}
```
### q_free
:::spoiler 問題程式
問題連結：[記憶體釋放錯誤](#記憶體釋放錯誤)
```c
void q_free(struct list_head *l)
{
struct list_head *node = l->next;
while (!list_empty(l)) {
list_del(node);
element_t *e=container_of(node,element_t,list);
free(e->value);
free(node);
node = l->next;
}
free(l);
}
```
:::
修正後程式：
```c
void q_free(struct list_head *l)
{
if (!l)
return;
while (!list_empty(l)) {
element_t *e = list_entry(l->next, element_t, list);
list_del(&e->list);
free(e->value);
free(e);
}
free(l);
}
```
### q_insert_head
:::spoiler 問題程式
問題連結：[記憶體釋放錯誤](#記憶體釋放錯誤)
```c
bool q_insert_head(struct list_head *head, char *s)
{
if (head == NULL)
return false;
element_t *e = malloc(sizeof(element_t));
list_add(&(e->list), head);
int len = strlen(s);
e->value = malloc(sizeof(char) * ++len);
strncpy(e->value, s, len);
return true;
}
```
由 `man strlen`的敘述：
> The strlen() function calculates the length of the string pointed to by
s, excluding the terminating null byte ('\0').
strlen 回傳的值不包含'\\0'，因此要先將長度值加一再動作。
:::
修正後程式：
```c
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;
}
```
### q_insert_tail
:::spoiler 問題程式
問題連結：[記憶體釋放錯誤](#記憶體釋放錯誤)
```c
bool q_insert_tail(struct list_head *head, char *s)
{
if (head == NULL)
return false;
element_t *e = malloc(sizeof(element_t));
list_add_tail(&(e->list), head);
int len = strlen(s);
e->value = malloc(sizeof(char) * ++len);
strncpy(e->value, s, len);
return true;
}
```
:::
修正後程式：
```c
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_insert_head](#q_insert_head)
### q_remove_head
```c
element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
element_t *e = NULL;
if (!head)
return NULL;
if (!list_empty(head)) {
e = container_of(head->next, element_t, list);
list_del(&e->list);
if (sp) {
strncpy(sp, e->value, bufsize - 1);
sp[bufsize - 1] = '\0';
}
}
return e;
}
```
### q_remove_tail
[trace-17 無法總是通過](#trace_17-無法總是通過)
```c
element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize)
{
element_t *e = NULL;
if (!head)
return NULL;
if (!list_empty(head)) {
e = container_of(head->prev, element_t, list);
list_del(&e->list);
if (sp) {
strncpy(sp, e->value, bufsize - 1);
sp[bufsize - 1] = '\0';
}
}
return e;
}
```
### q_size: 回傳佇列個數
```c
int q_size(struct list_head *head)
{
if (!head)
return 0;
int num = 0;
struct list_head *node = head;
while (node->next != head) {
node = node->next;
num++;
}
return num;
}
```
### q_delete_mid: **刪除**佇列中間的節點
~~~c
bool q_delete_mid(struct list_head *head)
{
struct list_head *front, *tail;
int i = 0;
if (!head)
return false;
if (list_empty(head))
return false;
for (front = head->next, tail = head->prev;
front != tail && front->next != tail;
front = front->next, tail = tail->prev, i++) {
}
list_del(tail);
q_release_element(list_entry(tail, element_t, list));
return true;
}
~~~
### q_delete_dup: **刪除**佇列中重複字串的節點
~~~c
bool q_delete_dup(struct list_head *head)
{
if (!head)
return false;
element_t *e, *safe, *tmp = NULL;
for (e = list_entry((head)->next, element_t, list),
safe = list_entry(e->list.next, element_t, list);
&safe->list != (head);
e = safe, safe = list_entry(safe->list.next, element_t, list)) {
if (!(strcmp(e->value, safe->value) & 0x7fffffff) ||
!(strcmp(e->value, safe->value))) {
list_del(&e->list);
q_release_element(e);
tmp = safe;
} else if (tmp) {
list_del(&tmp->list);
q_release_element(tmp);
tmp = NULL;
}
}
if (tmp) {
list_del(&tmp->list);
q_release_element(tmp);
tmp = NULL;
}
return true;
}
~~~
程式內使用到的遞迴幾乎等效於 list_for_each_entry_safe ，但是因為 list_for_each_entry_safe 的條件判斷是判斷 entry 而非 safe ，以至於最後會對 head 取 entry 並造成 segement fault。
### q_swap: 交換鄰近的節點
~~~c
void q_swap(struct list_head *head)
{
struct list_head *next, *nnext;
for (next = head->next, nnext = next->next;
(next != head) && (nnext != head);
next = next->next, nnext = next->next) {
list_move(next, nnext);
}
}
~~~
### q_reverse: 反向排列佇列
~~~c
void q_reverse(struct list_head *head)
{
if (!head)
return;
struct list_head *iter = head;
do {
struct list_head *tmp = iter->next;
iter->next = iter->prev;
iter->prev = tmp;
iter = iter->next;
} while (iter != head);
}
~~~
### q_sort: 以升幕排列佇列
~~~c
void q_sort(struct list_head *head)
{
if (!head)
return;
int count = 0;
// insertion sort
struct list_head *i, *j, *isafe, *jsafe;
for (i = (head->next)->next, isafe = i->next; i != head;
i = isafe, isafe = i->next) {
for (j = head->next, jsafe = j->next; j != i;
j = jsafe, jsafe = j->next) {
char *s1, *s2;
s1 = list_entry(i, element_t, list)->value;
s2 = list_entry(j, element_t, list)->value;
int cmp = strcmp(s1, s2);
count++;
if (cmp < 0) {
list_move(i, j->prev);
break;
}
}
}
}
~~~
## 問題紀錄
### cppcheck
#### 遇到問題
```shell
$ git commit -m "edit function q_new, q_insert_head/tail, q_remove_head/tail"
Following files need to be cleaned up:
queue.c
queue.c:50:5: error: Memory leak: e [memleak]
return true;
^
queue.c:69:5: error: Memory leak: e [memleak]
return true;
^
queue.c:50:5: error: Memory leak: e.value [memleak]
return true;
^
queue.c:69:5: error: Memory leak: e.value [memleak]
return true;
^
Fail to pass static analysis.
```
該位置為 [q_insert_tail](#q_insert_tail) 及 [q_insert_head](#q_insert_head) 的 return 位置，不知道為何導致 git 無法 commit 成功。
這裡指的 memory leak 是記憶體洩漏那個 memory leak 嗎？
:::warning
是的，你應該追蹤「完整」的程式碼，而非只注視單一函式。
:notes: jserv
:::
#### 解決方法
此處有兩個問題：
1. git commit 首字英文要大寫，且不能超過 50 個字元
2. 因為 cppcheck 有檢查，所以 list 需要用 INIT_LIST_HEAD 做初使化： value 要用 strdup 配置動態記憶體，不能使用 calloc 或 malloc 。
### 記憶體釋放錯誤
#### 遇到問題：
```shell
ERROR: Attempted to free unallocated block. Address = 0x55b5876a7e50
ERROR: Attempted to free unallocated or corrupted block. Address = 0x55b5876a7e50
ERROR: Corruption detected in block with address 0x55b5876a7e50 when attempting to free it
Segmentation fault occurred. You dereferenced a NULL or invalid pointer
[1] 73359 abort (core dumped) ./qtest
```
確定能從該位置取得字串，但不確定為何無法釋放。
#### 解決方法
測試後得知，在 `harness.h` 中， malloc 、 free 、 strdup 被重新撰寫以追蹤記憶體配置，因此此作業在動態記憶體配置上只能用此三個函式，無法使用像 calloc 、 strndup 等函式。
### trace_17 無法總是通過
#### 遇到問題：
q_remove_head 及 q_remove_tail函式幾乎一樣，差別只在移除 head 前面的還是後面的 list ，但是在跑 trace-17 的測試時 q_remove_tail 有機率無法通過。
::: spoiler q_remove_head disassemble
```assembler
0000000000000158 <q_remove_head>:
158: f3 0f 1e fa endbr64
15c: 41 54 push r12
15e: 55 push rbp
15f: 53 push rbx
160: 48 85 ff test rdi,rdi
163: 74 45 je 1aa <q_remove_head+0x52>
165: 48 89 f5 mov rbp,rsi
168: 49 89 d4 mov r12,rdx
16b: 48 8b 47 08 mov rax,QWORD PTR [rdi+0x8]
16f: 48 39 c7 cmp rdi,rax
172: 74 3b je 1af <q_remove_head+0x57>
174: 48 8d 58 f8 lea rbx,[rax-0x8]
178: 48 8b 48 08 mov rcx,QWORD PTR [rax+0x8]
17c: 48 8b 10 mov rdx,QWORD PTR [rax]
17f: 48 89 11 mov QWORD PTR [rcx],rdx
182: 48 89 4a 08 mov QWORD PTR [rdx+0x8],rcx
186: 48 85 f6 test rsi,rsi
189: 74 17 je 1a2 <q_remove_head+0x4a>
18b: 49 8d 54 24 ff lea rdx,[r12-0x1]
190: 48 8b 70 f8 mov rsi,QWORD PTR [rax-0x8]
194: 48 89 ef mov rdi,rbp
197: e8 00 00 00 00 call 19c <q_remove_head+0x44>
19c: 42 c6 44 25 ff 00 mov BYTE PTR [rbp+r12*1-0x1],0x0
1a2: 48 89 d8 mov rax,rbx
1a5: 5b pop rbx
1a6: 5d pop rbp
1a7: 41 5c pop r12
1a9: c3 ret
1aa: 48 89 fb mov rbx,rdi
1ad: eb f3 jmp 1a2 <q_remove_head+0x4a>
1af: bb 00 00 00 00 mov ebx,0x0
1b4: eb ec jmp 1a2 <q_remove_head+0x4a>
```
:::
:::spoiler q_remove_tail disassemble
```assembler
00000000000001b6 <q_remove_tail>:
1b6: f3 0f 1e fa endbr64
1ba: 41 54 push r12
1bc: 55 push rbp
1bd: 53 push rbx
1be: 48 85 ff test rdi,rdi
1c1: 74 45 je 208 <q_remove_tail+0x52>
1c3: 48 89 f5 mov rbp,rsi
1c6: 49 89 d4 mov r12,rdx
1c9: 48 3b 7f 08 cmp rdi,QWORD PTR [rdi+0x8]
1cd: 74 3e je 20d <q_remove_tail+0x57>
1cf: 48 8b 07 mov rax,QWORD PTR [rdi]
1d2: 48 8d 58 f8 lea rbx,[rax-0x8]
1d6: 48 8b 48 08 mov rcx,QWORD PTR [rax+0x8]
1da: 48 8b 10 mov rdx,QWORD PTR [rax]
1dd: 48 89 11 mov QWORD PTR [rcx],rdx
1e0: 48 89 4a 08 mov QWORD PTR [rdx+0x8],rcx
1e4: 48 85 f6 test rsi,rsi
1e7: 74 17 je 200 <q_remove_tail+0x4a>
1e9: 49 8d 54 24 ff lea rdx,[r12-0x1]
1ee: 48 8b 70 f8 mov rsi,QWORD PTR [rax-0x8]
1f2: 48 89 ef mov rdi,rbp
1f5: e8 00 00 00 00 call 1fa <q_remove_tail+0x44>
1fa: 42 c6 44 25 ff 00 mov BYTE PTR [rbp+r12*1-0x1],0x0
200: 48 89 d8 mov rax,rbx
203: 5b pop rbx
204: 5d pop rbp
205: 41 5c pop r12
207: c3 ret
208: 48 89 fb mov rbx,rdi
20b: eb f3 jmp 200 <q_remove_tail+0x4a>
20d: bb 00 00 00 00 mov ebx,0x0
212: eb ec jmp 200 <q_remove_tail+0x4a>
```
:::
並且，不管字串複製是使用 memcpy 還是 strncpy ，在轉譯後的組語是完全一樣的。
#### 解決方法（未解決）
目前觀測到在測量 q_remove_tail 時會發生執行核心交換的情況( ex. 原本在 cpu0 執行，但是跑到一半變成 cpu12 執行 )，當發生時，便會發生測量時間非常數的錯誤。
Sign in with Wallet
Connect another wallet