# 2021q1 Homework1 (lab0)
contributed by < [paul90317](https://github.com/paul90317) >
## 實驗環境
```shell
$ gcc -v
gcc version 9.3.0 (Ubuntu 9.3.0-17ubuntu1~20.04)
$ lscpu
架構： x86_64
CPU 作業模式： 32-bit, 64-bit
Byte Order: Little Endian
Address sizes: 39 bits physical, 48 bits virtual
CPU(s): 8
On-line CPU(s) list: 0-7
每核心執行緒數： 2
每通訊端核心數： 4
Socket(s): 1
NUMA 節點： 1
供應商識別號： GenuineIntel
CPU 家族： 6
型號： 158
Model name: Intel(R) Core(TM) i5-9300H CPU @ 2.40GHz
製程： 10
CPU MHz： 2400.000
CPU max MHz: 4100.0000
CPU min MHz: 800.0000
BogoMIPS: 4800.00
虛擬： VT-x
L1d 快取： 128 KiB
L1i 快取： 128 KiB
L2 快取： 1 MiB
L3 快取： 8 MiB
NUMA node0 CPU(s)： 0-7
```
## [作業要求](https://hackmd.io/@sysprog/linux2022-lab0)
- [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` 自動評分系統的所有項目。
- 在提交程式變更前，務必詳閱 [如何寫好 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/)
- 詳閱「[你所不知道的 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
## 開發過程
### q_new
檢查 malloc 是否正常運作
```cpp
struct list_head *q_new()
{
// don't LIST_HEAD maybe it's calloc
// auto return NULL
// not a node, just a queue.
struct list_head *head =
(struct list_head *) malloc(sizeof(struct list_head));
if (!head)
return NULL;
INIT_LIST_HEAD(head);
return head;
}
```
### q_free
要記得先清掉 value
```cpp
void q_free(struct list_head *l)
{
if (l == NULL)
return;
struct list_head *node = l->next;
while (node != l) {
list_del(node);
q_release_element(container_of(node, element_t, list));
node = l->next;
}
free(l);
}
```
### q_insert_head
一開始我遇到的問題是，我以為以為 head 外面有一個 contaier（資料型別為 element_t） 且包含 value。
然而我後來發現不是，它只是被一個 list_head_meta_t 的 struct 裡的指標所指到，且他的記憶體一開始已經挖好了。
**element_t**
```cpp
typedef struct {
/* Pointer to array holding string.
* This array needs to be explicitly allocated and freed
*/
char *value;
struct list_head list;
} element_t;
```
**list_head_meta_t**
```cpp
typedef struct {
struct list_head *l;
/* meta data of list */
int size;
} list_head_meta_t;
```
在 head 右邊插入新的節點
```cpp
bool q_insert_head(struct list_head *head, char *s)
{
if (head == NULL || s == NULL)
return false;
element_t *new_node = (element_t *) malloc(sizeof(element_t));
if (new_node == NULL)
return false;
list_add(&new_node->list, head);
int len = strlen(s);
new_node->value = (char *) malloc(len + 1);
if (new_node->value == NULL)
return false;
memcpy(new_node->value, s, len + 1);
return true;
}
```
### q_insert_tail
跟 insert head 滿像的
```cpp
bool q_insert_tail(struct list_head *head, char *s)
{
if (head == NULL || s == NULL)
return false;
element_t *new_node = (element_t *) malloc(sizeof(element_t));
if (new_node == NULL)
return false;
list_add_tail(&new_node->list, head);
int len = strlen(s);
new_node->value = (char *) malloc(len + 1);
if (new_node->value == NULL)
return false;
memcpy(new_node->value, s, len + 1);
return true;
}
```
### q_remove_head
移除 head 右邊的節點
```cpp
element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
if (head == NULL || list_empty(head))
return NULL;
element_t *ele = container_of(head->next, element_t, list);
if (sp) {
char *src = ele->value;
int len = min(strlen(src), bufsize - 1);
memcpy(sp, src, len);
sp[len] = 0;
}
list_del(&(ele->list));
return ele;
}
```
### q_remove_tail
移除 head 左邊的節點
```cpp
element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize)
{
if (head == NULL || list_empty(head))
return NULL;
element_t *ele = container_of(head->prev, element_t, list);
if (sp) {
char *src = ele->value;
int len = min(strlen(src), bufsize - 1);
memcpy(sp, src, len);
sp[len] = 0;
}
list_del(&(ele->list));
return ele;
}
```
### q_size
回傳 queue 大小，這是非常數時間的寫法。
原本是常數時間的，但那個解法有錯，因為我以為 list_head_meta_t 是 container (對於 member l 來說)，然而其實 l 型別是 struct list_head*，是一個使到容器的指標，這讓我們無法透過 head 去得到 l_meta 的位置，所以出錯。
還有一點就是 因為 qtest.c 已經 include queue.h 這個檔案，而 struct list_head_meta_t 是在 qtest.c 定義的，導致我不能使用 container_of，必須自己計算出（雖然前面已經證明是不行的，但這是我一開始的做法）。
```cpp
int q_size(struct list_head *head)
{
if (head == NULL)
return 0;
int ret = 0;
struct list_head *node;
list_for_each (node, head) {
ret++;
}
return ret;
}
```
### q_delete_mid
我是先計算出中間位置在哪裡，在用 list_for_each 到那個位置把節點刪除，非常數時間。
```cpp
bool q_delete_mid(struct list_head *head)
{
// https://leetcode.com/problems/delete-the-middle-node-of-a-linked-list/
int size = q_size(head);
if (head == NULL || size == 0)
return false;
struct list_head *node;
size = size / 2;
list_for_each (node, head) {
if (size == 0) {
list_del(node);
q_release_element(container_of(node, element_t, list));
break;
}
size--;
}
return true;
}
```
### q_delete_dup
把重複的節點一個不留的刪除，輸入是以排序 queue
```cpp
bool q_delete_dup(struct list_head *head)
{
// https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/
if (head == NULL)
return false;
struct list_head *node = head->next, *next;
while (node != head) {
int flag = 0;
while ((next = node->next) != head && n_cmp(node, next) == 0) {
list_del(next);
q_release_element(container_of(next, element_t, list));
flag = 1;
}
if (flag) {
list_del(node);
q_release_element(container_of(node, element_t, list));
}
node = next;
}
return true;
}
```
### q_swap
節點位置兩兩交換
若長度是奇數，最後一個不動
作法： 先從 head 取出兩個節點，再變換順序堆入 tail。
```cpp
void q_swap(struct list_head *head)
{
// https://leetcode.com/problems/swap-nodes-in-pairs/
int size = q_size(head);
if (head == NULL || size <= 1)
return;
struct list_head *a;
for (int i = 0; i < size / 2; i++) {
a = head->next;
list_del(a);
struct list_head *b = head->next;
list_del(b);
list_add_tail(b, head);
list_add_tail(a, head);
}
if ((size & 0b1) == 1) {
a = head->next;
list_del(a);
list_add_tail(a, head);
}
}
```
### q_reverse
先宣告新的 queue h2 ，頭尾接到 head 的 prev, next，這代表 h2 會有跟 head 相同的 element。
接著將 head 初始化，把 h2 所有 element 從頭取出放進 head 的前面，達到反轉。
```cpp
void q_reverse(struct list_head *head)
{
if (head == NULL)
return;
struct list_head h2;
int size = q_size(head);
h2.next = head->next;
h2.prev = head->prev;
head->next->prev = &h2;
head->prev->next = &h2;
INIT_LIST_HEAD(head);
for (int i = 0; i < size; i++) {
struct list_head *node = h2.next;
list_del(node);
list_add(node, head);
}
}
```
有看到別人是將每個 element 的 prev, next 反轉，應該之後會改(等到 action 拿到滿分後)
以下是改進版
```cpp
inline void swap_child(struct list_head *node)
{
struct list_head *t;
t = node->next;
node->next = node->prev;
node->prev = t;
}
void q_reverse(struct list_head *head)
{
if (head == NULL || head->next == NULL || head->prev == NULL)
return;
struct list_head *node;
swap_child(head);
for (node = head->prev; node != head; node = node->prev) {
swap_child(node);
}
}
```
### q_sort
merge sort，我是採用迴圈寫法，但這個跑在 action 會 TLE，我覺得應該是我移動到中間節點的方式是用迴圈慢慢移，應該有更快的方法。
```cpp
static inline struct list_head *merge(struct list_head *a,
struct list_head *b,
int asize,
int bsize)
{
struct list_head *tmp, htmp, *h;
h = a->prev;
INIT_LIST_HEAD(&htmp);
int i = 0, j = 0;
while ((i < asize) || (j < bsize)) {
if ((j == bsize) || ((i < asize) && (n_cmp(a, b) < 0))) {
tmp = a->next;
list_del(a);
list_add_tail(a, &htmp);
a = tmp;
i++;
} else {
tmp = b->next;
list_del(b);
list_add_tail(b, &htmp);
b = tmp;
j++;
}
}
tmp = h->next; // last
tmp->prev = htmp.prev;
htmp.prev->next = tmp;
h->next = htmp.next;
htmp.next->prev = h;
return tmp;
}
```
```cpp
void q_sort(struct list_head *head)
{
int size = q_size(head);
if (head == NULL || size <= 1)
return;
for (int iter = 1; iter < size; iter <<= 1) {
int rem = size;
struct list_head *a = head->next;
while (rem > iter) {
rem -= iter;
struct list_head *b = a;
for (int i = 0; i < iter; i++)
b = b->next;
a = merge(a, b, iter, min(iter, rem));
rem -= iter;
}
}
}
```
### qsort 改進
我覺得我之前寫的 merge sort 之所以會跑的慢，應該是因為我太拘泥於使用 linux list.h 內建的函式。
我發現，其實要排序 linked list，只要一個指標 (prev) 就夠了，而 next 就可以用來指向其他以排序的列表，而 prev 只想列表內已經排序的元素
經過預處理後如下
我們可以看橫向的每個元素都是以排序的列表，他們是各自列表唯一的元素。
接著我們就能進行 merge，先將最左兩以排序列表取出（無須查找中間點），進行合併，並且放到最右，這個操作相當於用迭代寫法 merge 兩個序列，並且當隨著時間推移我們一開始合併的序列，又會來到最左，這相當於迭代寫法合併序列長度增大，但不一樣的是，迭代寫法需要跳出巢狀迴圈把合併序列長度增加，但是我的改進版從頭到尾只用做同一件事。
當合併到剩下兩個序列的時候，需要跳出迴圈，進行最後的合併，再去把剩下的一條垂直序列變成 linux doubly linked list，完成。
為何不要合併到剩最後一條時，再轉成 doubly linked list，原因是我在合併前，會先把兩條序列取出，可是當我們取出剩下的兩條時，front 會變成 null，這樣在推到 back 時，就需要多一 if 取檢測 front 是否為 null，且要多傳遞一個變數到 h_push ，不符合 C 語言簡潔的風格。
**程式碼**
```cpp
static inline void h_push(struct list_head *node, struct list_head **back)
{
(*back)->next = node;
node->next = NULL;
*back = node;
}
static inline struct list_head *h_pop(struct list_head **front)
{
struct list_head *node = *front;
*front = node->next;
return node;
}
static inline void v_push(struct list_head *node, struct list_head **back)
{
(*back)->prev = node;
node->prev = NULL;
*back = node;
}
static inline struct list_head *v_pop(struct list_head **front)
{
struct list_head *node = *front;
*front = node->prev;
return node;
}
```
```cpp
static inline struct list_head *merge(struct list_head *a, struct list_head *b)
{
struct list_head front = {0, 0}, *back = &front;
struct list_head *tmp;
while (a || b) {
if (!b || (a && n_cmp(a, b) < 0)) {
tmp = v_pop(&a);
} else {
tmp = v_pop(&b);
}
v_push(tmp, &back);
}
return front.prev;
}
void q_sort(struct list_head *head)
{
if (head == NULL || q_size(head) <= 1)
return;
struct list_head *front = head->next, *back = head->prev;
// make vertival one node
struct list_head *node;
list_for_each (node, head) {
node->prev = NULL;
}
back->next = NULL; // cut down horizonal back
while (front->next != back) {
node = h_pop(&front);
node = merge(node, h_pop(&front));
h_push(node, &back);
}
front = merge(front, back);
INIT_LIST_HEAD(head);
for (node = front; node; node = back) {
back = node->prev;
list_add_tail(node, head);
}
}
```
Sign in with Wallet
Connect another wallet