# 2023q1 Homework1 (lab0)
contributed by < [p96114175](https://github.com/p96114175) >
:::danger
不要打錯自己的 GitHub 帳號名稱！
:notes: jserv
:::
## 作業要求
參考自[2023 年 Linux 核心設計/實作課程作業 —— lab0](https://hackmd.io/@sysprog/linux2023-lab0/%2F%40sysprog%2Flinux2023-lab0-f)
* 著手修改 queue.[ch] 和連帶的檔案，測試後用 Git 管理各項修改，要能滿足 $ make test 自動評分系統的所有項目。
* 研讀 Linux 核心原始程式碼的 [lib/list_sort.c](https://github.com/torvalds/linux/blob/master/lib/list_sort.c) 並嘗試引入到 lab0-c 專案，比較你自己實作的 merge sort 和 Linux 核心程式碼之間效能落差
* 確保 qtest 提供的 web 命令得以搭配上述佇列實作使用，目前一旦網頁伺服器啟動後，原本處理命令列操作的 linenoise 套件就無法使用，請提出改善機制
* 在 qtest 提供新的命令 shuffle，允許藉由 [Fisher–Yates shuffle](https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle) 演算法，對佇列中所有節點進行洗牌 (shuffle) 操作，需要以統計的原理來分析你的實作，探究洗牌的「亂度」
* 在 qtest 中執行 option entropy 1 並搭配 ih RAND 10 一類的命令，觀察亂數字串的分布，並運用「資訊與熵互補，資訊就是負熵」的觀念，設計一組新的命令或選項，得以在 qtest 切換不同的 PRNG 的實作 (可選定 Xorshift)，搭配統計分析工具，比較亂數產生器 (如 Xorshift vs. 內建) 的品質
* 研讀論文〈[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) 及程式實作的原理。
## 開發環境
```shell
$ gcc --version
gcc (Ubuntu 9.4.0-1ubuntu1~20.04.1) 9.4.0
$ lscpu
架構： x86_64
CPU 作業模式： 32-bit, 64-bit
Byte Order: Little Endian
Address sizes: 39 bits physical, 48 bits virtual
CPU(s): 24
On-line CPU(s) list: 0-23
每核心執行緒數： 1
每通訊端核心數： 16
Socket(s): 1
NUMA 節點： 1
供應商識別號： GenuineIntel
CPU 家族： 6
型號： 151
Model name: 12th Gen Intel(R) Core(TM) i9-12900F
製程： 2
CPU MHz： 2400.000
CPU max MHz: 5100.0000
CPU min MHz: 800.0000
BogoMIPS: 4838.40
虛擬： VT-x
L1d 快取： 384 KiB
L1i 快取： 256 KiB
L2 快取： 10 MiB
```
## q_new 實作
```c
struct list_head *q_new()
{
struct list_head *new = malloc(sizeof(*new));
if (!new)
return NULL;
INIT_LIST_HEAD(new);
return new;
}
```
:::danger
注意作業書寫規範：中英文間用一個半形空白字元區隔。
程式碼縮排亦有相關規範，請依循！
:notes: jserv
:::
:::success
好的
:::
首先取得大小為 `list_head` 並指向分配到的記憶體的 `pointer` ，倘若新增失敗便返回 `NULL` ，成功的話就 `INIT_LIST_HEAD` ，最終返回新增好的 `list_head`
:::danger
改進你的漢語表達。
:notes: jserv
:::
:::success
好的
:::
## q_free 實作
```c
void q_free(struct list_head *l) {
if (!l) return;
element_t *entry, *safe;
list_for_each_entry_safe (entry, safe, l, list){
list_del(&entry->list);
q_release_element(entry);
}
free(l);
}
```
## q_insert_head 實作
```c
bool q_insert_head(struct list_head *head, char *s)
{
if(!head) return false;
element_t *new_element = malloc(sizeof(element_t));
if(!new_element) return false;
size_t len = strlen(s) + 1;
new_element->value = malloc(len * sizeof(char));
if(!new_element->value){
free(new_element);
return false;
}
memcpy(new_element->value, s,len);
list_add(&new_element->list, head);
return true;
}
```
首先確認 `head` 是否為空，接著使用 `malloc` 得到 `new_element` ，再使用 `strlen` 取得s的 `size` 並加上1，加1的涵義為 `\0` ，再應用剛得到的 `len` 去分配大小為 `char` 的記憶體空間給 `new_element` 的 value。
第二步，將 `new_element->value` 的記憶體值複製給 `s` ，完成後將 `new_element` 插入 `head` 的開頭。
## q_insert_tail 實作
```c
bool q_insert_tail(struct list_head *head, char *s)
{
if(!head) return NULL;
element_t *new_element = malloc(sizeof(element_t));
if(!new_element) return NULL;
size_t len = strlen(s) + 1;
new_element->value = malloc(len * sizeof(char));
if(!new_element->value){
free(new_element);
return NULL;
}
memcpy(new_element->value,s,strlen(s)+1);
list_add_tail(&new_element->list, head);
return true;
}
```
此處和 `q_insert_head` 只差在倒數第二段，我使用了 `list_add_tail`。
## q_remove_head 實作
```c
element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
if(!head||list_empty(head)) return NULL;
return q_remove(list_first_entry(head, element_t, list), sp, bufsize);
}
```
此處我先用 `list_first_entry`，將 `head` 中第一個 `entry` 找出來後，再丟入 `q_remove` 進行 `remove`
## q_remove_tail 實作
```c
element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize)
{
return q_remove(list_last_entry(head, element_t, list), sp, bufsize);
}
```
和 `q_remove_head` 差一點在於，使用了 `list_last_entry` 找出 `head` 中最後一個 `entry` 再進行 `remove`
## q_size 實作
```c
int q_size(struct list_head *head)
{
if (!head) return 0;
int len = 0;
struct list_head *cur;
list_for_each (cur, head)
len++;
return len;
}
```
宣告變數名為 `len` 並給值為 `0`，透過 `list_for_each` 去 `iterate` 得到 `q_size`
## q_delete_mid 實作
```c
bool q_delete_mid(struct list_head *head)
{
if(!head||list_empty(head)) return NULL;
struct list_head **indir = &head;
for(struct list_head *cur = head->next; (*indir)->prev!=cur && (*indir)!=cur; indir = &(*indir)->prev){
cur = cur->next;
}
struct list_head *mid = (*indir)->prev;
list_del(mid);
q_release_element(list_entry(mid, element_t, list));
return true;
}
```
這裡使用了 `indir` 和 `cur`，分別從不同方向前進，最終找到 `mid` 並消除。
## q_delete_dup 實作
```c
bool q_delete_dup(struct list_head *head)
{
if(!head||list_empty(head)) return NULL;
element_t *cur, *safe;
bool del_final = false;
list_for_each_entry_safe (cur, safe, head, list){
if(cur->list.next!=head && strcmp(cur->value, safe->value) == 0){
list_del(&cur->list);
q_release_element(cur);
del_final = true;
}
else if(del_final){
list_del(&cur->list);
q_release_element(cur);
del_final = false;
}
}
return true;
}
```
查看 list_for_each_entry_safe 的說明
> #define list_for_each_entry_safe(entry, safe, head, member) ，透過額外的 safe 紀錄每個迭代 (iteration) 所操作的節點的下一個節點，因此目前的節點可允許被移走，其他操作則同為不可預期行為
使用 `list_for_each_entry_safe` 進行 iterate，第一個 loop 時，先確認 `cur` 和 `safe` 值是否相等，若相等則刪除 `cur`，同時將 `del_final` 更改為 true，假設進入第二個 loop 時發現，`cur` 和 `safe` 不相同，則跳入 `else if(del_final)`，將重複的 `cur` 進行刪除
## q_swap 實作
```c
void q_swap(struct list_head *head)
{
if(!head) return;
struct list_head *node;
list_for_each(node, head){
if(node->next == head) break;
list_move(node, node->next);
}
}
```
透過 `list_for_each` 對 `head` 進行 iterate，若 `node->next` 遇見 `head`，則跳出 loop。將 `node` 從原本的 linked list 移動到另一個 linked list `node->next` 的開頭
## q_reverse 實作
```c
void q_reverse(struct list_head *head) {
if(!head) return;
struct list_head *node, *safe;
list_for_each_safe(node, safe, head)
list_move(node, head);
}
```
將 `node` 從原本的 linked list 移動到另一個 linked list `head` 的開頭
## q_reverseK 實作
```c
void q_reverseK(struct list_head *head, int k)
{
if(!head) return;
struct list_head *node, *safe, head_to, *head_from = head;
int count = 0;
INIT_LIST_HEAD(&head_to);
list_for_each_safe(node, safe, head){
count++;
if(count!=k){
list_cut_position(&head_to, head_from, node);
q_reverse(&head_to);
list_splice_init(&head_to, head_from);
head_from = safe->prev;
count=0;
}
}
}
```
建立一個 `count` 和初始化 `head_to`，在每次 iterate 中 count 進行累加，倘若 `count` 不等於 `K` 則進入 if 判斷式中。將從 `head_from` 的第一個節點到 node 間的一系列節點都移動到 `head_to` 上。其中`head_to` 必須是 empty 狀態，再將 `head_to` 進行 `q_reverse` 。將 `head_to` 的所有 node 都插入到 `head_from` 的開始。接著 `head_from` 指向 `safe` 的 `prev`
## q_sort 實作
**q_sort**
```c
void q_sort(struct list_head *head) {
if(!head || list_empty(head)) return;
head->prev->next = NULL;
head->next = q_divide(head->next);
struct list_head *cur=head, *safe = head->next;
while(safe){
safe->prev = cur;
cur = safe;
safe = safe->next;
}
cur->next = head;
head->prev = cur;
}
```
**q_divide**
```c
struct list_head *q_divide(struct list_head *head) {
if(!head->next) return head;
struct list_head *l=head, *r=head->next, *left, *right;
while(r && r->next){
r = r->next->next;
l = l->next;
}
struct list_head *mid=l->next;
l->next=NULL;
left = q_divide(head);
right = q_divide(mid);
return merge_two(left, right);
}
```
透過 `l` 和 `r` 將 head 拆成兩段，再丟入 `merge_two` 中
**merge_two**
```c
struct list_head *merge_two(struct list_head *left, struct list_head *right){
struct list_head head;
struct list_head *cur=&head;
if(!left && !right) return NULL;
for(;left && right;cur = cur->next){
if(strcmp(list_entry(left, element_t, list)->value, list_entry(right, element_t, list)->value)<0){
(cur)->next = left;
left = left->next;
}
else{
(cur)->next = right;
right = right->next;
}
}
if(left) (cur)->next = left;
else if(right) (cur)->next = right;
return head.next;
}
```
使用cur指向 `head` 的位址，當 `left` 和 `right` 都存在時，便進行 `left` 和 `right` 的值比較，若 `left` 小於 `right`，則將 `cur` 的 `next` 指向 `left`，`left` 向前推進一個，結束該 loop 前， `cur` 也向前推進一個，若 `left` 大於 `right` ，則將 `cur` 的 `next` 指向 `right` ， `right` 向前推進一個，當 `left` 和 `right` 都不存在時，跳出 for loop。
若 `left` 存在， `cur` 的 `next` 指向 `left` ，若 `right` 存在， `cur` 的 `next` 指向 `right` ，最後返回 `head` 的 `next`。
## q_descend 實作
```c
int q_descend(struct list_head *head)
{
if(!head) return false;
struct list_head *a = head->prev, *b = a->prev;
while(b!=head){
if(strcmp(list_entry(b, element_t,list)->value, list_entry(a, element_t, list)->value)<0){
list_del(b);
}
else {
a=b;
}
b=b->prev;
}
return q_size(head);
}
```
## q_merge 實作
```c
int q_merge(struct list_head *head)
{
if(!head || list_empty(head)) return false;
queue_contex_t *init = container_of(head->next, queue_contex_t, chain);
struct list_head *cur = head->next->next;
for(;cur !=head;cur=cur->next){
queue_contex_t *queue = container_of(cur, queue_contex_t, chain);
list_splice_init(queue->q, init->q);
queue->size = 0;
}
q_sort(init->q);
init->size = q_size(init->q);
return init->size;
}
```
原理為，先將全部的 queue 合併成為一個 queue , 接著再將合併好的 queue 放入 q_sort 進行排序
:::danger
注意作業書寫規範：中英文間用一個半形空白字元區隔。
程式碼縮排亦有相關規範，請依循！
:notes: jserv
:::
:::success
已修正，還請多多指教
:::
老師在教材中有提到，[lab0-c](https://github.com/sysprog21/lab0-c) 已整合 [Valgrind](https://valgrind.org/) 來協助學員細緻地找出記憶體相關的問題，諸如 memory leak, buffer overflow, Dangling pointer 等等。使用方式如下:
```
$ make valgrind
```
```
# Test if time complexity of q_insert_tail, q_insert_head, q_remove_tail, and q_remove_head is constant
Probably constant time
ERROR: Probably not constant time or wrong implementation
Probably constant time
Probably constant time
==475928==
==475928== HEAP SUMMARY:
==475928== in use at exit: 0 bytes in 0 blocks
==475928== total heap usage: 625,085,604 allocs, 625,085,604 frees, 34,977,448,704 bytes allocated
==475928==
==475928== All heap blocks were freed -- no leaks are possible
==475928==
==475928== For lists of detected and suppressed errors, rerun with: -s
==475928== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)
--- trace-17-complexity 0/5
--- TOTAL 89/100
```
從上圖結果中我們可以全部 heap blocks 都被釋放了，沒有 leak 存在的可能
## 比較自己實作的 merge sort 和 Linux 核心程式碼之間效能落差
Sign in with Wallet
Connect another wallet