# 2023q1 Homework1 (lab0)
contributed by < [Welly0902](https://github.com/Welly0902) >
本作業參考 [zeddyuu](https://hackmd.io/@zeddyuu/2023lab0) 同學及 [paul90317](https://hackmd.io/@paul90317/linux2023-spring-lab0) 同學
:::danger
注意書寫規範：中英文間用一個半形空白字元區隔。
:notes: jserv
:::
## 作業要求
:::info
- [x] 完成實作 queue.c 所有功能
- [x] `make test` 取得 100 分
- [ ] 研讀 `lib/list_sort.c` 並將其加入專案中
- [ ] 實作新的命令 `shuffle`
- [ ] 完成 entropy 相關命令 / 選項
- [ ] 研讀論文[〈Dude, is my code constant time?〉](https://eprint.iacr.org/2016/1123.pdf)並且解釋 [Student’s t-distribution](https://en.wikipedia.org/wiki/Student%27s_t-distribution) 及程式實作的原理
- [ ] 使用 Valgrind 排除 qtest 實作的記憶體錯誤
- [ ] 開啟 Address Sanitizer，修正 qtest 執行過程中的錯誤
:::
## 環境設置
使用 WSL2 Ubuntu 22.04
* Perf 在 WSL2上使用:
Perf 在 WSL2上需另外下載[WSL2-Linux-Kernel](https://github.com/microsoft/WSL2-Linux-Kernel)
再把 `/tools/perf` make 起來，過程如下:
```shell
$ git clone https://github.com/microsoft/WSL2-Linux-Kernel --depth 1
$ cd WSL2-Linux-Kernel/tools/perf
$ make -j8
$ sudo cp perf /usr/local/bin
```
* 修改 `kernel.perf_event_paranoid` 的方式:
在 `/etc/sysctl.conf` 中加入 `kernel.perf_event_paranoid = -1`
修改完成後 `sudo sysctl -p` 即修改完成
* Perf 測試使用:
```shell
$ perf record ./example
$ perf report
```
## 開發環境
```shell
$ 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: 46 bits physical, 48 bits virtual
Byte Order: Little Endian
CPU(s): 20
On-line CPU(s) list: 0-19
Vendor ID: GenuineIntel
Model name: 12th Gen Intel(R) Core(TM) i7-12700
CPU family: 6
Model: 151
Thread(s) per core: 2
Core(s) per socket: 10
Socket(s): 1
Stepping: 2
BogoMIPS: 4224.00
```
## 開發過程
Q: 如何實際檢驗所寫 function 對 queue 的運行狀況?
A: 修改完程式後執行 `make` 再運用 `./qtest` 去模擬各個 function 的運行狀態
目標: 利用 list.h 中[定義好的 API](https://www.kernel.org/doc/html/latest/core-api/kernel-api.html)
### q_new
```c
/* Create an empty queue */
struct list_head *q_new()
{
struct list_head *head = malloc(sizeof(*head));
if (head)
INIT_LIST_HEAD(head);
return head;
}
```
### q_free
```c
/* Free all storage used by queue */
void q_free(struct list_head *l) {
if (!l || list_empty(l)) {
free(l);
return;
}
element_t *entry = NULL, *safe = NULL;
list_for_each_entry_safe (entry, safe, l, list) {
list_del(&entry->list);
q_release_element(entry);
}
free(l);
}
```
### q_insert_head
```c
/* Insert an element at head of queue */
bool q_insert_head(struct list_head *head, char *s)
{
if(!head)
return false;
element_t *entry = malloc(sizeof(*entry));
if (!entry)
return false;
size_t len = strlen(s) + 1;
entry->value = malloc(len * sizeof(char));
if (!entry->value) {
free(entry);
return false;
}
memcpy(entry->value, s, len);
INIT_LIST_HEAD(&entry->list);
list_add(&entry->list, head);
return true;
}
```
### q_insert_tail
```c
/* Insert an element at tail of queue */
bool q_insert_tail(struct list_head *head, char *s)
{
if(!head)
return false;
element_t *entry = malloc(sizeof(*entry));
if (!entry)
return false;
size_t len = strlen(s) + 1;
entry->value = malloc(len * sizeof(char));
if (!entry->value) {
free(entry);
return false;
}
memcpy(entry->value, s, len);
INIT_LIST_HEAD(&entry->list);
list_add_tail(&entry->list, head);
return true;
}
```
### q_remove_head
Q: 為何 romove element 需要 return element_t 型態的 pointer?
```c
/* Remove an element from head of queue */
element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
if (!head || list_empty(head)) {
return NULL;
}
element_t *element = list_first_entry(head, element_t, list);
if (sp && bufsize > 0) {
strncpy(sp, element->value, bufsize - 1);
sp[bufsize - 1] = '\0';
}
list_del(&element->list);
return element;
}
```
strncpy: 將 source 的前 num 個字元從 source 複製到 destination。
`char * strncpy ( char * destination, const char * source, size_t num );`
需注意要預留 null terminator `\0` 的位置。
### q_remove_tail
`list_first_entry` 換成 `list_first_entry` 即可找到 tail
```c
/* Remove an element from tail of queue */
element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize)
{
if (!head || list_empty(head)) {
return NULL;
}
element_t *element = list_last_entry(head, element_t, list);
if (sp && bufsize > 0) {
strncpy(sp, element->value, bufsize - 1);
sp[bufsize - 1] = '\0';
}
list_del(&element->list);
return element;
}
```
### q_size
```clike=
int q_size(struct list_head *head)
{
if (!head || list_empty(head)){
return 0;
}
int len = 0;
struct list_head *node;
list_for_each (node, head) {
len++;
}
return len;
}
```
### q_delete_mid
`list_for_each_entry_safe` delete 後需要break
```c
bool q_delete_mid(struct list_head *head)
{
// https://leetcode.com/problems/delete-the-middle-node-of-a-linked-list/
if (!head || list_empty(head)){
return false;
}
int half = q_size(head)/2;
element_t *node, *t;
int cnt = 0;
list_for_each_entry_safe(node, t, head, list){
if (cnt++ == half){
list_del(&node->list);
q_release_element(node);
break;
}
}
return true;
}
```
### q_delete_dup
根據 list.h 註解，`list_for_each_entry_safe(entry, safe, head, member)` 中的 `safe` 參數為當前節點的下一個節點，先記錄下一個節點的位置以避免在刪除節點時發生錯誤。
```c
bool q_delete_dup(struct list_head *head)
{
// https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/
if (!head || list_empty(head)){
return false;
}
element_t *node, *t;
bool flag = false;
list_for_each_entry_safe(node, t, head, list){
// head is the start and end of the linked list
// strcmp = 0 when strings are equal
if (node->list.next != head && strcmp(node->value, t->value) == 0) {
list_del(&node->list);
q_release_element(node);
flag = true;
}
else if (flag) {
list_del(&node->list);
q_release_element(node);
flag = false;
}
}
return true;
}
```
運用 `flag` 去紀錄是否重複，以刪除最後一個重複節點。
### q_swap
運用 `list_move(node, head)` ，可以用 `list_move(node, node->next)` 來達到交換節點的效果。 `list_move` 會進行兩個動作: `list_del` 及 `list_add` ，以下面是意圖來呈現如何交換:
:::warning
此處再以graphviz改進
:::
```
list_del(node):
x
n1 <-> n2 <-> n3 n1 n2 <-> n3
| | => | |
node node->next node node->next
```
```graphviz
digraph g {
label="Before list_del"
// fontname="Courier New"
rankdir=LR;
node [shape=record, colorscheme=reds9];
ptr1[shape=plaintext, label="node", fontname="Arial"]
ptr2[shape=plaintext, label="node->next", fontname="Arial"]
a [label="{<ref1> | <data> n1 | <ref2>}", color=red];
b [label="{<ref1> | <data> n2 | <ref2>}"];
c [label="{<ref1> | <data> n3 | <ref2>}"];
a:ref2:c -> b:data:n [arrowhead=normal, arrowtail=none, dir=both, tailclip=false];
b:ref1:c -> a:data:s [arrowhead=normal, arrowtail=none, dir=both, tailclip=false];
b:ref2:c -> c:data:n [arrowhead=normal, arrowtail=none, dir=both, tailclip=false];
c:ref1:c -> b:data:s [arrowhead=normal, arrowtail=none, dir=both, tailclip=false];
c:ref1:c -> b:data:w[weight = 100, style = invis];
b:ref1:c -> a:data:w[weight = 100, style = invis];
a:ref1:c -> c:data:n [arrowhead=normal, arrowtail=none, dir=both, tailclip=false, style=dashed];
c:ref2:c -> a:data:s [arrowhead=normal, arrowtail=none, dir=both, tailclip=false, style=dashed];
ptr1 -> a:data:n[color=blue]
ptr2 -> b:data:n[color=blue]
}
```
```graphviz
digraph g {
label="After list_del"
// fontname="Courier New"
rankdir=LR;
node [shape=record, colorscheme=reds9];
ptr1[shape=plaintext, label="node", fontname="Arial"]
ptr2[shape=plaintext, label="node->next", fontname="Arial"]
a [label="{<ref1> | <data> n1 | <ref2>}",color=6];
b [label="{<ref1> | <data> n2 | <ref2>}"];
c [label="{<ref1> | <data> n3 | <ref2>}"];
a:ref2:c -> b:data:n [arrowhead=normal, arrowtail=none, dir=both, tailclip=false,style=invis];
b:ref1:c -> a:data:s [arrowhead=normal, arrowtail=none, dir=both, tailclip=false,style=invis];
b:ref2:c -> c:data:n [arrowhead=normal, arrowtail=none, dir=both, tailclip=false];
c:ref1:c -> b:data:s [arrowhead=normal, arrowtail=none, dir=both, tailclip=false];
c:ref1:c -> b:data:w[weight = 100, style = invis];
b:ref1:c -> a:data:w[weight = 100, style = invis];
a:ref1:c -> c:data:n [arrowhead=normal, arrowtail=none, dir=both, tailclip=false, style=dashed,style=invis];
c:ref2:c -> a:data:s [arrowhead=normal, arrowtail=none, dir=both, tailclip=false, style=dashed,style=invis];
ptr1 -> a:data:n[color=blue]
ptr2 -> b:data:n[color=blue]
}
```
`list_add` 的部分在 `list.h` 中為:
```clike=
static inline void list_add(struct list_head *node, struct list_head *head)
{
struct list_head *next = head->next; //1
next->prev = node; //2
node->next = next; //3
node->prev = head; //4
head->next = node; //5
}
```
因此 `list_add(node, node->next)` 為:
```graphviz
digraph g {
label="struct list_head *next = head->next; //1"
// fontname="Courier New"
rankdir=LR;
node [shape=record, colorscheme=reds9];
ptr1[shape=plaintext, label="node", fontname="Arial"]
ptr2[shape=plaintext, label="node->next", fontname="Arial"]
ptr3[shape=circle label="next", color=6]
a [label="{<ref1> | <data> n1 | <ref2>}"];
b [label="{<ref1> | <data> n2 | <ref2>}"];
c [label="{<ref1> | <data> n3 | <ref2>}"];
a:ref2:c -> b:data:n [arrowhead=normal, arrowtail=none, dir=both, tailclip=false,style=invis];
b:ref1:c -> a:data:s [arrowhead=normal, arrowtail=none, dir=both, tailclip=false,style=invis];
b:ref2:c -> c:data:n [arrowhead=normal, arrowtail=none, dir=both, tailclip=false];
c:ref1:c -> b:data:s [arrowhead=normal, arrowtail=none, dir=both, tailclip=false];
c:ref1:c -> b:data:w[weight = 100, style = invis];
b:ref1:c -> a:data:w[weight = 100, style = invis];
a:ref1:c -> c:data:n [arrowhead=normal, arrowtail=none, dir=both, tailclip=false, style=dashed,style=invis];
c:ref2:c -> a:data:s [arrowhead=normal, arrowtail=none, dir=both, tailclip=false, style=dashed,style=invis];
ptr1 -> a:data:n[color=blue]
ptr2 -> b:data:n[color=blue]
ptr3 -> c:data:s[color=red]
}
```
```graphviz
digraph g {
label="next->prev = node; //2"
// fontname="Courier New"
rankdir=LR;
node [shape=record, colorscheme=reds9];
ptr1[shape=plaintext, label="node", fontname="Arial"]
ptr2[shape=plaintext, label="node->next", fontname="Arial"]
ptr3[shape=circle label="next"]
a [label="{<ref1> | <data> n1 | <ref2>}"];
b [label="{<ref1> | <data> n2 | <ref2>}"];
c [label="{<ref1> | <data> n3 | <ref2>}"];
a:ref2:c -> b:data:n [arrowhead=normal, arrowtail=none, dir=both, tailclip=false,style=invis];
b:ref1:c -> a:data:s [arrowhead=normal, arrowtail=none, dir=both, tailclip=false,style=invis];
b:ref2:c -> c:data:n [arrowhead=normal, arrowtail=none, dir=both, tailclip=false];
c:ref1:c -> a:data:s [arrowhead=normal, arrowtail=none, dir=both, tailclip=false, color=red];
c:ref1:c -> b:data:w[weight = 100, style = invis];
b:ref1:c -> a:data:w[weight = 100, style = invis];
a:ref1:c -> c:data:n [arrowhead=normal, arrowtail=none, dir=both, tailclip=false, style=dashed,style=invis];
c:ref2:c -> a:data:s [arrowhead=normal, arrowtail=none, dir=both, tailclip=false, style=dashed,style=invis];
ptr1 -> a:data:n[color=blue]
ptr2 -> b:data:n[color=blue]
ptr3 -> c:data:s
}
```
```graphviz
digraph g {
label="node->next = next; //3"
// fontname="Courier New"
rankdir=LR;
node [shape=record, colorscheme=reds9];
ptr1[shape=plaintext, label="node", fontname="Arial"]
ptr2[shape=plaintext, label="node->next", fontname="Arial"]
ptr3[shape=circle label="next"]
a [label="{<ref1> | <data> n1 | <ref2>}"];
b [label="{<ref1> | <data> n2 | <ref2>}"];
c [label="{<ref1> | <data> n3 | <ref2>}"];
a:ref2:c -> c:data:n [arrowhead=normal, arrowtail=none, dir=both, tailclip=false, color=red];
b:ref1:c -> a:data:s [arrowhead=normal, arrowtail=none, dir=both, tailclip=false,style=invis];
b:ref2:c -> c:data:n [arrowhead=normal, arrowtail=none, dir=both, tailclip=false];
c:ref1:c -> a:data:s [arrowhead=normal, arrowtail=none, dir=both, tailclip=false];
c:ref1:c -> b:data:w[weight = 100, style = invis];
b:ref1:c -> a:data:w[weight = 100, style = invis];
a:ref1:c -> c:data:n [arrowhead=normal, arrowtail=none, dir=both, tailclip=false, style=dashed,style=invis];
c:ref2:c -> a:data:s [arrowhead=normal, arrowtail=none, dir=both, tailclip=false, style=dashed,style=invis];
ptr1 -> a:data:n[color=blue]
ptr2 -> b:data:n[color=blue]
ptr3 -> c:data:s
}
```
```graphviz
digraph g {
label="node->prev = head; //4"
// fontname="Courier New"
rankdir=LR;
node [shape=record, colorscheme=reds9];
ptr1[shape=plaintext, label="node", fontname="Arial"]
ptr2[shape=plaintext, label="node->next", fontname="Arial"]
ptr3[shape=circle label="next"]
a [label="{<ref1> | <data> n1 | <ref2>}"];
b [label="{<ref1> | <data> n2 | <ref2>}"];
c [label="{<ref1> | <data> n3 | <ref2>}"];
a:ref2:c -> c:data:n [arrowhead=normal, arrowtail=none, dir=both, tailclip=false];
b:ref1:c -> a:data:s [arrowhead=normal, arrowtail=none, dir=both, tailclip=false,style=invis];
b:ref2:c -> c:data:n [arrowhead=normal, arrowtail=none, dir=both, tailclip=false];
c:ref1:c -> a:data:s [arrowhead=normal, arrowtail=none, dir=both, tailclip=false];
c:ref1:c -> b:data:w[weight = 100, style = invis];
b:ref1:c -> a:data:w[weight = 100, style = invis];
a:ref1:c -> b:data:n [arrowhead=normal, arrowtail=none, dir=both, tailclip=false, color=red];
c:ref2:c -> a:data:s [arrowhead=normal, arrowtail=none, dir=both, tailclip=false, style=dashed,style=invis];
ptr1 -> a:data:n[color=blue]
ptr2 -> b:data:n[color=blue]
ptr3 -> c:data:s
}
```
```graphviz
digraph g {
label="head->next = node; //5"
// fontname="Courier New"
rankdir=LR;
node [shape=record, colorscheme=reds9];
ptr2[shape=plaintext, label="node->next", fontname="Arial"]
ptr1[shape=plaintext, label="node", fontname="Arial"]
ptr3[shape=circle label="next"]
b [label="{<ref1> | <data> n2 | <ref2>}"];
a [label="{<ref1> | <data> n1 | <ref2>}"];
c [label="{<ref1> | <data> n3 | <ref2>}"];
b:ref2:c -> a:data:n [arrowhead=normal, arrowtail=none, dir=both, tailclip=false, color=red];
a:ref1:c -> b:data:s [arrowhead=normal, arrowtail=none, dir=both, tailclip=false];
b:ref1:c -> a:data:w[weight = 100, style = invis];
a:ref1:c -> c:data:w[weight = 100, style = invis];
a:ref2:c -> c:data:n [arrowhead=normal, arrowtail=none, dir=both, tailclip=false];
// b:ref1:c -> a:data:s [arrowhead=normal, arrowtail=none, dir=both, tailclip=false,style=invis];
c:ref1:c -> a:data:s [arrowhead=normal, arrowtail=none, dir=both, tailclip=false];
// c:ref1:c -> b:data:w[weight = 100, style = invis];
// b:ref1:c -> a:data:w[weight = 100, style = invis];
c:ref2:c -> a:data:s [arrowhead=normal, arrowtail=none, dir=both, tailclip=false, style=dashed,style=invis];
ptr1 -> a:data:n[color=blue]
ptr2 -> b:data:n[color=blue]
ptr3 -> c:data:s
}
```
```
list_add(node, node->next):
n1 n2 <-> n3
| |
node node->next //head
//1//
next
|
n1 n2 <-> n3
| |
node node->next
//2//
node->next next
| |
n2 n1<-n3
| | ^
| node |
---------------
//3//
node->next next
| |
n2 n1<->n3
| | ^
| node |
-----------------
//4//
node->next next
| |
n2 <- n1<->n3
| | ^
| node |
-----------------
//5//
node->next next
| |
n2 <-> n1<->n3
|
node
```
由上過程可見，兩個 node 前後 swap了，程式碼為下:
```c
/* Swap every two adjacent nodes */
void q_swap(struct list_head *head)
{
// https://leetcode.com/problems/swap-nodes-in-pairs/
if (!head || list_empty(head)){
return;
}
for (struct list_head *node = head->next; node != head && node->next != head;
node = node->next) {
list_move(node, node->next);
}
}
```
### q_reverse
用 `list_for_each_safe` 走訪每個節點，走訪該節點時從 list 中刪除再加到 head 下一個即可達到 list reverse 的效果。
考量第一個 iteration 不會對 list 造成任何變動，加一個變數 flag 來跳過第一個 iteration。
```c
/* Reverse elements in queue */
void q_reverse(struct list_head *head) {
if (!head || list_empty(head)) {
return;
}
struct list_head *node, *t;
bool flag = true;
list_for_each_safe (node, t, head) {
if (flag) {flag = false; continue;}
list_del(node);
list_add(node, head);
}
}
```
### q_reverseK
此為每 k 個元素做一次 reverse。可利用上一個 `q_reverse` 每走過k個元素用 `list_cut_position` 拆分成剩餘 list 中前方 k 個要 reverse 的，以及後方剩餘還沒做的。再將切出來的前 k 個 cut 用 `q_reverse` 做 reverse。最後再以 `list_splice_init` 接到目前 `tmp_head` 的前方。達成 [reverse](https://leetcode.com/problems/reverse-nodes-in-k-group/) 的效果。
```clike=
void q_reverseK(struct list_head *head, int k)
{
// https://leetcode.com/problems/reverse-nodes-in-k-group/
if (!head || list_empty(head)) {
return;
}
struct list_head *node, *t, *tmp_head = head;
struct list_head cut;
INIT_LIST_HEAD(&cut);
int counter = 0;
list_for_each_safe (node, t, head) {
counter++;
// every k element do reverse
if (counter == k) {
list_cut_position(&cut, tmp_head, node);
q_reverse(&cut);
list_splice_init(&cut, tmp_head);
// reset count
counter = 0;
// record the start of the list to be dealed with
tmp_head = t->prev;
}
}
return;
}
```
### q_sort
`merge` 的部分取兩 list 的節點出來比大小:
```c
static inline void merge(struct list_head *head, struct list_head *l1, struct list_head *l2)
{
while (!list_empty(l1) && !list_empty(l2)) {
if (strcmp(list_entry(l1->next, element_t, list)->value, list_entry(l2->next, element_t, list)->value) < 0) {
list_move_tail(l1->next, head);
} else {
list_move_tail(l2->next, head);
}
}
if (!list_empty(l1)) {
list_splice_tail_init(l1, head);
} else {
list_splice_tail_init(l2, head);
}
}
```
再來將 input linked list 切分為二後，用前面寫好的 `q_sort` 排好，再進行 merge:
```clike=
/* Sort elements of queue in ascending order */
void q_sort(struct list_head *head) {
if (!head || q_size(head) < 2) {
return;
}
// split the target linked list to two list for merging
struct list_head *fast = head, *slow = head;
do {
slow = slow->next;
fast = fast->next->next;
} while (fast != head && fast->next != head);
LIST_HEAD(left);
LIST_HEAD(right);
list_splice_init(head, &right);
// get left and right list
list_cut_position(&left, &right, slow);
//sort left and right list and ready for merging
q_sort(&left);
q_sort(&right);
// merge
merge(head, &left, &right);
}
```
Q: `merge` function 中初始為何是l1->next，而不是l1?
### q_descend
此實作若節點右側有值比他大，則當下點刪除。思路可利用 doubly linked list 雙向的特性，從又往左走訪各節點。以一個變數記錄當下最大，小於即刪除來達到相同效果。
```c
/* Remove every node which has a node with a strictly greater value anywhere to
* the right side of it */
int q_descend(struct list_head *head)
{
// https://leetcode.com/problems/remove-nodes-from-linked-list/
if (!head || list_empty(head)) {
return 0;
}
element_t *entry = list_entry(head->prev, element_t, list);
element_t *np = list_entry(entry->list.prev, element_t, list);
char *curr_max = entry->value;
while (&entry->list != head) {
if (strcmp(entry->value, curr_max) < 0) {
list_del(&entry->list);
q_release_element(entry);
} else {
curr_max = entry->value;
}
// move the pointer backward
entry = np;
np = list_entry(entry->list.prev, element_t, list);
}
return q_size(head);
}
```
### q_merge
此實作的 input 為一個 linked list，每個節點連著一個 queue。故透過 while 迴圈每次合成 `floor((q_count + 1) / 2) ` 個 queue。
```c
/* Merge all the queues into one sorted queue, which is in ascending order */
int q_merge(struct list_head *head)
{
// https://leetcode.com/problems/merge-k-sorted-lists/
if (!head || list_empty(head)) {
return 0;
}
int q_count = q_size(head);
while (q_count > 1) {
// fast pointer for merging
struct list_head *fast = head->next;
// slow pointer for recording the position for the final result queue list
struct list_head *slow = head->next;
for (int i = 0; i < q_count / 2; i++) {
// create a head for the temp merging list
LIST_HEAD(temp_head);
merge(&temp_head, container_of(fast, queue_contex_t, chain)->q, container_of(fast->next, queue_contex_t, chain)->q);
list_splice_tail(&temp_head, container_of(slow, queue_contex_t, chain)->q);
fast = fast->next->next;
slow = slow->next;
}
if (q_count & 1)
list_splice_tail_init(container_of(fast, queue_contex_t, chain)->q, container_of(slow, queue_contex_t, chain)->q);
q_count = (q_count + 1) / 2;
}
return q_size(container_of(head->next, queue_contex_t, chain)->q);
}
```
Sign in with Wallet
Connect another wallet