---
tags: linux kernel, linux2022
---
# 2022q1 Homework1 (lab0)
contributed by < [`linjohnss`](https://github.com/linjohnss) >
## 作業要求
### 針對 Queue 的操作
滿足 `$ make test` 自動評分系統的所有項目
也可以用 `$ ./qtest -f traces/trace-XX-CAT.cmd` 來針對單一項目測試
* `q_new`: 建立新的「空」佇列
* `q_free`: 釋放佇列所佔用的記憶體
* `q_insert_head`: 在佇列開頭 (head) 插入 (insert) 給定的新節點 (以 LIFO 準則)
* `q_insert_tail`: 在佇列尾端 (tail) 插入 (insert) 給定的新節點 (以 FIFO 準則)
* `q_remove_head`: 在佇列開頭 (head) 移去 (remove) 給定的節點
* `q_release_element`: 釋放特定節點的記憶體空間
* `q_size`: 計算目前佇列的節點總量
* `q_delete_mid`: 移走佇列中間的節點
* `q_delete_dup`: 在已經排序的狀況，移走佇列中具備重複內容的節點
* `q_swap`: 交換佇列中鄰近的節點
* `q_reverse`: 以反向順序重新排列鏈結串列，該函式不該配置或釋放任何鏈結串列節點，換言之，它只能重排已經存在的節點
* `q_sort`: 以==遞增順序==來排序鏈結串列的節點
### 在 qtest 提供新的命令 shuffle
允許藉由 Fisher–Yates shuffle 演算法，對佇列中所有節點進行洗牌 (shuffle) 操作
### 在 qtest 提供新的命令 web
提供 web 伺服器功能，注意: web 伺服器運作過程中，qtest 仍可接受其他命令
- 可依據前述說明，嘗試整合 tiny-web-server
### 引入 lib/list_sort.c 至 lab0-c 專案
研讀 Linux 核心原始程式碼的 lib/list_sort.c 並嘗試引入到 lab0-c 專案，比較你自己實作的 merge sort 和 Linux 核心程式碼之間效能落差
### 運用 Valgrind 排除 qtest 實作的記憶體錯誤
運用 Valgrind 排除 qtest 實作的記憶體錯誤，並透過 Massif 視覺化 “simulation” 過程中的記憶體使用量，需要設計對應的實驗
## 開發環境
```
$ 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): 8
On-line CPU(s) list: 0-7
Thread(s) per core: 2
Core(s) per socket: 4
Socket(s): 1
NUMA node(s): 1
Vendor ID: GenuineIntel
CPU family: 6
Model: 142
Model name: Intel(R) Core(TM) i5-8250U CPU @ 1.60GHz
Stepping: 10
CPU MHz: 1800.000
CPU max MHz: 3400.0000
CPU min MHz: 400.0000
BogoMIPS: 3600.00
Virtualization: VT-x
L1d cache: 128 KiB
L1i cache: 128 KiB
L2 cache: 1 MiB
L3 cache: 6 MiB
NUMA node0 CPU(s): 0-7
```
## 針對 Queue 的操作
### q_size
> db70a3
```c
int q_size(struct list_head *head)
{
if (!head)
return 0;
int len = 0;
struct list_head *li;
list_for_each (li, head)
len++;
return len;
}
```
根據作業說明進行 queue 長度計算的實作。
- 回傳 queue 內 element 的數量。
- 如果 queue 為 NULL 或 empty，則回傳 0。
### q_new
> 0a8131
```c
struct list_head *q_new()
{
struct list_head *head = malloc(sizeof(struct list_head));
// malloc return NULL if allocate failed.
if (head)
INIT_LIST_HEAD(head);
return head;
}
```
利用 `list.h` 裡的函式 `INIT_LIST_HEAD` 來初始化 `head`。
當無法分配空間時 `molloc` 會回傳 `NULL`，因此需要在 `molloc` 後檢查 `head` 是否為 `NULL`。
### q_free
```c
void q_free(struct list_head *l)
{
if (!l)
return;
// traverse all entries and free the entry and its value
element_t *entry, *safe;
list_for_each_entry_safe (entry, safe, l, list) {
free(entry->value);
free(entry);
}
free(l);
}
```
利用 `list.h` 裡的函式 `list_for_each_entry_safe` 來走訪 list 中的 `element`，並釋放其佔用的記憶體。
> 9cd1fa
原先為用 `free` 實做得的部份，可以改用 `q_release_element` 來代替，進而提昇程式碼精簡度。
```c
void q_free(struct list_head *l)
{
if (!l)
return;
// traverse all entries and free the entry and its value
element_t *entry, *safe;
list_for_each_entry_safe (entry, safe, l, list)
q_release_element(entry);
free(l);
}
```
### q_insert_head
> 0a8131
```c
bool q_insert_head(struct list_head *head, char *s)
{
if (!head)
return false;
element_t *node = malloc(sizeof(element_t));
if (!node)
return false;
// allocate string space
size_t length = strlen(s);
node->value = malloc(length + 1);
if (!node->value) {
free(node);
return false;
}
// copy the string into space
strncpy(node->value, s, length);
node->value[length] = '\0';
// add new node in begining of head
list_add(&node->list, head);
return true;
}
```
由於 `strlen` 不會算到結束字元`\0`，因此要`+1`用來放結束字元。
:::warning
:warning: 當無法分配 `node->value` 的空間時，除了回傳 `false` 外，還要釋放 `node` 的空間。
:::
### q_insert_tail
> 0a8131
```c
bool q_insert_tail(struct list_head *head, char *s)
{
if (!head)
return false;
element_t *node = malloc(sizeof(element_t));
if (!node)
return false;
// allocate string space
size_t length = strlen(s);
node->value = malloc(length + 1);
if (!node->value) {
free(node);
return false;
}
// copy the string into space
strncpy(node->value, s, length);
node->value[length] = '\0';
// add new node in begining of head
list_add_tail(&node->list, head);
return true;
}
```
同 `q_insert_head` 改用 `list_add_tail` 加入 list
### q_reverse
> 0cf3af
```c
void q_reverse(struct list_head *head)
{
if (!head)
return;
else if (list_empty(head))
return;
struct list_head *node, *safe, *tmp;
list_for_each_safe (node, safe, head) {
tmp = node->next;
node->next = node->prev;
node->prev = tmp;
}
tmp = head->next;
head->next = head->prev;
head->prev = tmp;
}
```
利用 `list_for_each_safe` 走訪 list 中的 `node`，並將該 `node` 的 `prev` 以及 `next` 交換。
走訪完畢後，需要將 `head->next` 與 `head->prev` 交換。
> 2aa8d7
```c
void q_reverse(struct list_head *head)
{
if (!head)
return;
else if (list_empty(head))
return;
struct list_head *node, *safe;
list_for_each_safe (node, safe, head) {
node->next = node->prev;
node->prev = safe;
}
head->next = head->prev;
head->prev = safe;
}
```
參考 [Kevin-Shih 的開發紀錄](https://hackmd.io/@Kevin-Shih/linux2022q1-lab0) 提到使用 `list_for_each_safe` 時，可以利用 `safe` 紀錄的下一個節點替代 `tmp`，因此根據此特性作修改。
### q_remove_head
> e60602
```c
element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
if (!head || list_empty(head))
return NULL;
element_t *ptr = list_first_entry(head, element_t, list);
list_del_init(&ptr->list);
size_t length = strlen(ptr->value);
if (sp) {
length = length > bufsize ? bufsize : length;
strncpy(sp, ptr->value, length);
sp[length] = '\0';
}
return ptr;
}
```
先透過 `list_first_entry` 找到第一個 `element`，接著利用 `list_del_init` 移除。
若 `sp` 不為 `NULL` 則將 `element` 的 `value` 複製到 `sp`（須判斷 `vlaue` 與 `bufsize` 的大小）。
> 3edcaf
```c
element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
if (!head || list_empty(head))
return NULL;
element_t *ptr = list_first_entry(head, element_t, list);
list_del_init(&ptr->list);
size_t length = strlen(ptr->value);
if (sp) {
length = length > bufsize - 1 ? bufsize - 1 : length;
strncpy(sp, ptr->value, length);
sp[length] = '\0';
}
return ptr;
}
```
把比較值 `bufsize` 改為 `bufsize -1`，因為要留一個字元存取 `Null-terminated`。
### q_remove_tail
> e60602
```c
element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize)
{
if (!head || list_empty(head))
return NULL;
element_t *ptr = list_last_entry(head, element_t, list);
list_del_init(&ptr->list);
size_t length = strlen(ptr->value);
if (sp) {
length = length > bufsize ? bufsize : length;
strncpy(sp, ptr->value, length);
sp[length] = '\0';
}
return ptr;
}
```
同 `q_remove_head`，改用 `list_last_entry` 找到最後一個 `element`。
> 3edcaf
```c
element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize)
{
if (!head || list_empty(head))
return NULL;
element_t *ptr = list_last_entry(head, element_t, list);
list_del_init(&ptr->list);
size_t length = strlen(ptr->value);
if (sp) {
length = length > bufsize - 1 ? bufsize - 1 : length;
strncpy(sp, ptr->value, length);
sp[length] = '\0';
}
return ptr;
}
```
把比較值 `bufsize` 改為 `bufsize -1`，因為要留一個字元存取 `Null-terminated`。
### q_delete_mid
> 3edcaf
```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 NULL;
element_t *ptr;
struct list_head *rear, *front;
rear = head->prev;
front = head->next;
while (front != rear && front->next != rear) {
front = front->next;
rear = rear->prev;
}
list_del_init(front);
ptr = list_entry(front, element_t, list);
q_release_element(ptr);
return true;
}
```
利用兩個指標 `rear`、`front` 指向 list 的頭尾，兩個指標反向移動，當指標發生交會時，及找到 list 的中間值。
### q_swap
> eeca3c
```c
void q_swap(struct list_head *head)
{
// https://leetcode.com/problems/swap-nodes-in-pairs/
if (!head || list_empty(head) || list_is_singular(head))
return;
struct list_head *right, *left;
left = head->next;
right = left->next;
while (left != head && right != head) {
list_move(left, right);
left = left->next;
right = left->next;
}
}
```
根據 leetcode 解釋，是將 `queue` 分兩兩一組，並進行交換。
1. 首先，判斷當 `head` 不存在、空的或是只有一個 `node`，則什麼都不用作。
2. 利用兩個指標 `left`、`right` 分別指向開頭相鄰的左右兩個 `node`。
3. 將這兩個 `node` 用 `list_move` 交換。此時，原本在左邊的 `node` 就會移到右邊。
4. 因此，下一組的指標即為 `left = left->next`、`right = right->next`。
5. 重複 3.、4. 步驟，直到無法在兩兩一組為止 `left == head || right == head`。
:arrow_down: 原本的 double circular link list 結構，順序為 `1、2、3、4`。
```graphviz
digraph "Doubly Linked List" {
rankdir=LR;
node [shape=record];
a [label="{ <ref1> | <data> head | <ref2> }"]
b [label="{ <ref1> | <data> 1 | <ref2> }"];
c [label="{ <ref1> | <data> 2 | <ref2> }"];
d [label="{ <ref1> | <data> 3 | <ref2> }"];
e [label="{ <ref1> | <data> 4 | <ref2> }"];
e:data:s -> a:ref1:s [arrowhead=dot, arrowtail=vee, dir=both, headclip=false];
a:ref2:c -> b:data:n [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
b:ref2:c -> c:data:n [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
c:ref2:c -> d:data:n [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
c:ref1:c -> b:data:s [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
b:ref1:c -> a:data:s [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
d:ref2:c -> e:data:n [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
d:ref1:c -> c:data:s [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
e:ref2:n -> a:data:n [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
e:ref1:c -> d:data:s [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
}
```
:arrow_down: `left`、`right` 指向前兩個相鄰的 `node`。
```graphviz
digraph "Doubly Linked List" {
rankdir=LR;
node [shape=record];
a [label="{ <ref1> | <data> head | <ref2> }"]
b [label="{ <ref1> | <data> 1 | <ref2> }"];
c [label="{ <ref1> | <data> 2 | <ref2> }"];
d [label="{ <ref1> | <data> 3 | <ref2> }"];
e [label="{ <ref1> | <data> 4 | <ref2> }"];
l [label="left ",shape=circle];
r [label="right" shape=circle];
e:data:s -> a:ref1:s [arrowhead=dot, arrowtail=vee, dir=both, headclip=false];
a:ref2:c -> b:data:n [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
b:ref2:c -> c:data:n [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
c:ref2:c -> d:data:n [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
c:ref1:c -> b:data:s [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
b:ref1:c -> a:data:s [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
d:ref2:c -> e:data:n [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
d:ref1:c -> c:data:s [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
e:ref2:n -> a:data:n [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
e:ref1:c -> d:data:s [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
l:data:c -> b:data:n [arrowhead=vee, arrowtail=dot, dir=both, headclip=false];
r:data:c -> c:data:n [arrowhead=vee, arrowtail=dot, dir=both, headclip=false];
}
```
:arrow_down: 將這兩個 `node` 用 `list_move` 交換。因此，`left` 會成為右側的 `node`。
```graphviz
digraph "Doubly Linked List" {
rankdir=LR;
node [shape=record];
a [label="{ <ref1> | <data> head | <ref2> }"]
b [label="{ <ref1> | <data> 2 | <ref2> }"];
c [label="{ <ref1> | <data> 1 | <ref2> }"];
d [label="{ <ref1> | <data> 3 | <ref2> }"];
e [label="{ <ref1> | <data> 4 | <ref2> }"];
l [label="left ",shape=circle];
r [label="right" shape=circle];
e:data:s -> a:ref1:s [arrowhead=dot, arrowtail=vee, dir=both, headclip=false];
a:ref2:c -> b:data:n [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
b:ref2:c -> c:data:n [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
c:ref2:c -> d:data:n [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
c:ref1:c -> b:data:s [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
b:ref1:c -> a:data:s [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
d:ref2:c -> e:data:n [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
d:ref1:c -> c:data:s [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
e:ref2:n -> a:data:n [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
e:ref1:c -> d:data:s [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
r:data:c -> b:data:n [arrowhead=vee, arrowtail=dot, dir=both, headclip=false];
l:data:c -> c:data:n [arrowhead=vee, arrowtail=dot, dir=both, headclip=false];
}
```
:arrow_down: 接著，`left = left->next, right = right->next`，並重複這兩個動作，直到沒辦法相鄰兩兩一組為止。
```graphviz
digraph "Doubly Linked List" {
rankdir=LR;
node [shape=record];
a [label="{ <ref1> | <data> head | <ref2> }"]
b [label="{ <ref1> | <data> 2 | <ref2> }"];
c [label="{ <ref1> | <data> 1 | <ref2> }"];
d [label="{ <ref1> | <data> 3 | <ref2> }"];
e [label="{ <ref1> | <data> 4 | <ref2> }"];
l [label="left ",shape=circle];
r [label="right" shape=circle];
e:data:s -> a:ref1:s [arrowhead=dot, arrowtail=vee, dir=both, headclip=false];
a:ref2:c -> b:data:n [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
b:ref2:c -> c:data:n [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
c:ref2:c -> d:data:n [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
c:ref1:c -> b:data:s [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
b:ref1:c -> a:data:s [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
d:ref2:c -> e:data:n [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
d:ref1:c -> c:data:s [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
e:ref2:n -> a:data:n [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
e:ref1:c -> d:data:s [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
r:data:c -> d:data:n [arrowhead=vee, arrowtail=dot, dir=both, headclip=false];
l:data:c -> e:data:n [arrowhead=vee, arrowtail=dot, dir=both, headclip=false];
}
```
:arrow_down: 即為相鄰兩兩一組交換的成果。
```graphviz
digraph "Doubly Linked List" {
rankdir=LR;
node [shape=record];
a [label="{ <ref1> | <data> head | <ref2> }"]
b [label="{ <ref1> | <data> 2 | <ref2> }"];
c [label="{ <ref1> | <data> 1 | <ref2> }"];
d [label="{ <ref1> | <data> 4 | <ref2> }"];
e [label="{ <ref1> | <data> 3 | <ref2> }"];
e:data:s -> a:ref1:s [arrowhead=dot, arrowtail=vee, dir=both, headclip=false];
a:ref2:c -> b:data:n [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
b:ref2:c -> c:data:n [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
c:ref2:c -> d:data:n [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
c:ref1:c -> b:data:s [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
b:ref1:c -> a:data:s [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
d:ref2:c -> e:data:n [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
d:ref1:c -> c:data:s [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
e:ref2:n -> a:data:n [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
e:ref1:c -> d:data:s [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
}
```
### mergeTwoList ,mergesort_list and q_sort
> eeca3c
```c
struct list_head *mergeTwoList(struct list_head *L1, struct list_head *L2)
{
struct list_head *head = NULL, **ptr = &head, **node = NULL;
for (element_t *ele1, *ele2; L1 && L2; *node = (*node)->next) {
ele1 = list_entry(L1, element_t, list);
ele2 = list_entry(L2, element_t, list);
node = (strcmp(ele1->value, ele2->value) <= 0) ? &L1 : &L2;
*ptr = *node;
ptr = &(*ptr)->next;
}
*ptr = (struct list_head *) ((__UINTPTR_TYPE__) L1 | (__UINTPTR_TYPE__) L2);
//*ptr = L1 ? L1 : L2;
return head;
}
```
```c
struct list_head *mergesort_list(struct list_head *head)
{
if (!head || !head->next)
return head;
struct list_head *slow = head;
for (struct list_head *fast = head->next; fast && fast->next;
fast = fast->next->next)
slow = slow->next;
struct list_head *mid = slow->next;
slow->next = NULL;
struct list_head *left = mergesort_list(head), *right = mergesort_list(mid);
return mergeTwoList(left, right);
}
```
```c
void q_sort(struct list_head *head)
{
if (!head || list_empty(head) || list_is_singular(head))
return;
head->prev->next = NULL;
head->next = mergesort_list(head->next);
struct list_head *ptr;
for (ptr = head; ptr->next; ptr = ptr->next)
ptr->next->prev = ptr;
ptr->next = head;
head->prev = ptr;
}
```
利用 Merge Sort 對 Queue 進行排序，因為 Merge Sort 為 O(nlogn)，可以通過 `trace-14` 與 `trace-15`。
### q_delete_dup
> d38186
```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 *entry, *safe;
list_for_each_entry_safe (entry, safe, head, list) {
if (&safe->list != head && !strcmp(entry->value, safe->value)) {
list_del(&entry->list);
q_release_element(entry);
}
}
return true;
}
```
利用 `list_for_each_entry_safe` 走訪整個 Queue，當 `entry->value` 與 `safe->value`（下一個 `node` 的值） 相同時，刪除 `entry->value`。
:::warning
:warning: 此作法是刪除所有重複的 `node` 直到剩下單獨一個 `node`，並不符合題意，須要刪除所有重複的 `node`。
:::
```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 *entry, *safe;
bool left = false; // use left to delete the last duplicate element
list_for_each_entry_safe (entry, safe, head, list) {
if (&safe->list != head && !strcmp(entry->value, safe->value)) {
list_del(&entry->list);
q_release_element(entry);
left = true;
} else if (left) {
list_del(&entry->list);
q_release_element(entry);
left = false;
}
}
return true;
}
```
為了刪除留下的一個 `element`，先宣告一個變數 `left`，用來判斷是否為留下來的重複 `element`（當重複發生時，令 `left` 為 `true`。如此一來，若與下一個 `safe->value` 不相同，但是`left` 為 `true`則代表為留下來的element），並將其刪除。
## 在 qtest 提供新的命令 shuffle
### shuffle 實作
> 4532cd
閱讀 [Fisher–Yates shuffle](https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle) 演算法，在 `queue.c` 加入函式 `q_shuffle`：
```c
void q_shuffle(struct list_head *head)
{
if (!head || list_empty(head) || list_is_singular(head))
return;
struct list_head *i = head, *j;
int r;
for (size_t length = q_size(head); length > 0; length--) {
j = head->next;
for (r = rand() % length; r > 0; r--)
j = j->next;
list_move_tail(i->prev, j);
list_move_tail(j, i);
i = i->prev;
}
}
```
### 如何加入新的指令（command）
> 4532cd
在 `qtest.c` 先宣告 `q_shuffle` 函式其定義在 `queue.c` 中。
```c
void q_shuffle(struct list_head *head);
```
接著在 `console_init()` 加入一行
```c
ADD_COMMAND(shuffle, " | Shuffle all nodes in queue");
```
並加入 `do_shuffle`
```c
static bool do_shuffle(int argc, char *argv[])
{
if (argc != 1) {
report(1, "%s takes no arguments", argv[0]);
return false;
}
if (!l_meta.l)
report(3, "Warning: Try to access null queue");
error_check();
set_noallocate_mode(true);
if (exception_setup(true))
q_shuffle(l_meta.l);
exception_cancel();
set_noallocate_mode(false);
show_queue(3);
return !error_check();
}
```
## 在 qtest 提供新的命令 web
### 加入 [`tiny.c`](https://github.com/7890/tiny-web-server) 至 lab0-c
將 `tiny.c` 加入 lab0-c，並修改 `Makefile` 來編譯它。在 `Makefile` 的 `OBJS` 加入 `tiny.o` 即可。
```
OBJS := qtest.o report.o console.o harness.o queue.o \
random.o dudect/constant.o dudect/fixture.o dudect/ttest.o \
linenoise.o tiny.o
```
### 加入 `tiny.h` 至 lab0-c
宣告兩個全域變數 `listenfd` 與 `noise`，提供 `console.c` 讀取。
```c
#ifndef TINY_H
#define TINY_H
#include <netinet/in.h>
#include <stdbool.h>
extern int listenfd;
extern bool noise;
/* Simplifies calls to bind(), connect(), and accept() */
typedef struct sockaddr SA;
void socket_init();
char *process(int fd, struct sockaddr_in *clientaddr);
#endif
```
### socket_init
改寫自 `tiny.c` 的 `main`，只需保留啟動 `server` 與忽略 `SIGPIPE` 訊號的部份。並且將 socket 改為 non-blocking，防止程式停止接收使用者輸入。
```c
void socket_init()
{
int default_port = DEFAULT_PORT;
listenfd = open_listenfd(default_port);
if (listenfd > 0) {
printf("listen on port %d, fd is %d\n", default_port, listenfd);
} else {
perror("ERROR");
exit(listenfd);
}
// Ignore SIGPIPE signal, so if browser cancels the request, it
// won't kill the whole process.
signal(SIGPIPE, SIG_IGN);
int flags = fcntl(listenfd, F_GETFL);
fcntl(listenfd, F_SETFL, flags | O_NONBLOCK);
return;
}
```
### process
參照 [lab0-c](https://hackmd.io/@sysprog/linux2022-lab0#tip1) 作業提示改寫。原先給的程式碼無法通過 pre-commit。
```c
char *process(int fd, struct sockaddr_in *clientaddr)
{
#ifdef LOG_ACCESS
printf("accept request, fd is %d, pid is %d\n", fd, getpid());
#endif
http_request req;
parse_request(fd, &req);
int status = 200;
// handle_request(fd, req.filename);
char *p = req.filename;
/* Change '/' to ' ' */
if (*p) {
while ((*p) != '\0') {
++p;
if (*p == '/') {
*p = ' ';
}
}
}
#ifdef LOG_ACCESS
log_access(status, clientaddr, &req);
#endif
char *ret = malloc(strlen(req.filename) + 1);
strncpy(ret, req.filename, strlen(req.filename) + 1);
return ret;
}
```
:::warning
TODO：handle_request(fd, req.filename)，負責處理 reply message。
:::
### cmd_select
根據 [lab0-c](https://hackmd.io/@sysprog/linux2022-lab0#tip1) 作業提示，`cmd_select` 可以滿足同時處理命令列輸入與網頁伺服器。因此我們根據提示下去改。
```c
int cmd_select(int nfds,
fd_set *readfds,
fd_set *writefds,
fd_set *exceptfds,
struct timeval *timeout)
{
int infd;
fd_set local_readset;
if (cmd_done())
return 0;
if (!block_flag) {
/* Process any commands in input buffer */
if (!readfds)
readfds = &local_readset;
/* Add input fd to readset for select */
infd = buf_stack->fd;
+ FD_ZERO(readfds);
FD_SET(infd, readfds);
+ /* If web not ready listen */
+ if (listenfd != -1)
+ FD_SET(listenfd, readfds);
if (infd == STDIN_FILENO && prompt_flag) {
printf("%s", prompt);
fflush(stdout);
prompt_flag = true;
}
if (infd >= nfds)
nfds = infd + 1;
+ if (listenfd >= nfds)
+ nfds = listenfd + 1;
}
if (nfds == 0)
return 0;
int result = select(nfds, readfds, writefds, exceptfds, timeout)
if (result <= 0)
return result;
infd = buf_stack->fd;
if (readfds && FD_ISSET(infd, readfds)) {
/* Commandline input available */
FD_CLR(infd, readfds);
result--;
- if (has_infile) {
char *cmdline;
cmdline = readline();
if (cmdline)
interpret_cmd(cmdline);
- }
+ } else if (readfds && FD_ISSET(listenfd, readfds)) {
+ FD_CLR(listenfd, readfds);
+ result--;
+ int connfd;
+ struct sockaddr_in clientaddr;
+ socklen_t clientlen = sizeof(clientaddr);
+ connfd = accept(listenfd,(SA *) &clientaddr, &clientlen);
+ char *p = process(connfd, &clientaddr);
+ if (p)
+ interpret_cmd(p);
+ free(p);
+ close(connfd);
+ }
return result;
}
```
### 加入 web 命令
這次嘗試在 `console.c` 中加入 command。先實做 `do_web` 函式。
```c
static bool do_web(int argc, char *argv[])
{
socket_init();
noise = false;
return true;
}
```
接著在 `init_cmd()` 中加入一行。
```c
ADD_COMMAND(web, " | Response to web client");
```
### 執行成果
```c
cmd> web
listen on port 9999, fd is 3
cmd> accept request, fd is 4, pid is 219443
127.0.0.1:56212 200 - 'new' (text/plain)
l = []
cmd> accept request, fd is 4, pid is 219443
127.0.0.1:56214 200 - 'ih bear' (text/plain)
l = [bear]
cmd> accept request, fd is 4, pid is 219443
127.0.0.1:56216 200 - 'ih tiger' (text/plain)
l = [tiger bear]
cmd> accept request, fd is 4, pid is 219443
127.0.0.1:56218 200 - 'ih dolphin' (text/plain)
l = [dolphin tiger bear]
cmd> accept request, fd is 4, pid is 219443
127.0.0.1:56222 200 - 'reverse' (text/plain)
l = [bear tiger dolphin]
cmd> accept request, fd is 4, pid is 219443
127.0.0.1:56224 200 - 'rh bear' (text/plain)
Removed bear from queue
l = [tiger dolphin]
cmd> accept request, fd is 4, pid is 219443
127.0.0.1:56226 200 - 'rh tiger' (text/plain)
Removed tiger from queue
l = [dolphin]
cmd> accept request, fd is 4, pid is 219443
127.0.0.1:56228 200 - 'rh dolphin' (text/plain)
Removed dolphin from queue
l = []
cmd>
```
## 引入 lib/list_sort.c 至 lab0-c 專案
### 研讀 [lib/list_sort.c](https://github.com/torvalds/linux/blob/master/lib/list_sort.c)
### 引入 queu.c
> 0399d2
1. 將 `lib/list_sort.c` 改寫成 `linux_sort.h`，並在 `queue.c` include
2. 宣告函式 `string_cmp` 與 `q_linux_sort`
```c
int string_cmp(void *t,const struct list_head *L1,const struct list_head *L2)
{
return strcmp(list_entry(L1, element_t, list)->value, list_entry(L2, element_t, list)->value);
}
void q_linux_sort(struct list_head *head)
{
if (!head || list_empty(head) || list_is_singular(head))
return;
list_sort(NULL, head, string_cmp);
}
```
### 加入命令 LinuxSort
> 0399d2
在 `qtest.c` 裡加入 `do_LinuxSort`
```c
bool do_LinuxSort(int argc, char *argv[])
{
if (argc != 1) {
report(1, "%s takes no arguments", argv[0]);
return false;
}
if (!l_meta.l)
report(3, "Warning: Calling sort on null queue");
error_check();
int cnt = q_size(l_meta.l);
if (cnt < 2)
report(3, "Warning: Calling sort on single node");
error_check();
set_noallocate_mode(true);
if (exception_setup(true))
q_linux_sort(l_meta.l);
exception_cancel();
set_noallocate_mode(false);
bool ok = true;
if (l_meta.size) {
for (struct list_head *cur_l = l_meta.l->next;
cur_l != l_meta.l && --cnt; cur_l = cur_l->next) {
/* Ensure each element in ascending order */
/* FIXME: add an option to specify sorting order */
element_t *item, *next_item;
item = list_entry(cur_l, element_t, list);
next_item = list_entry(cur_l->next, element_t, list);
if (strcasecmp(item->value, next_item->value) > 0) {
report(1, "ERROR: Not sorted in ascending order");
ok = false;
break;
}
}
}
show_queue(3);
return ok && !error_check();
}
```
接著在 `console_init()` 加入一行
```c
ADD_COMMAND(LinuxSort, " | Use linux list_sort to sort queue in ascending order");
```
### 比較自己寫的 merge sort 與 linux 的 list_sort 效能落差
撰寫一個用於比較 merge sort 與 linux 的 list_sort 效能落差的 `.cmd` 檔案
```shell
cmd> # Test of sort and LinuxSort
cmd> option fail 0
cmd> option malloc 0
cmd> new
l = []
cmd> ih gerbil 100000
l = [gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil ... ]
cmd> it bear 100000
l = [gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil ... ]
cmd> ih dolphin 100000
l = [dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin ... ]
cmd> reverse
l = [bear bear bear bear bear bear bear bear bear bear bear bear bear bear bear bear bear bear bear bear bear bear bear bear bear bear bear bear bear bear ... ]
cmd> time sort
l = [bear bear bear bear bear bear bear bear bear bear bear bear bear bear bear bear bear bear bear bear bear bear bear bear bear bear bear bear bear bear ... ]
Delta time = 0.130
cmd> time LinuxSort
l = [bear bear bear bear bear bear bear bear bear bear bear bear bear bear bear bear bear bear bear bear bear bear bear bear bear bear bear bear bear bear ... ]
Delta time = 0.065
Freeing queue
```
:::info
從上述成果，可以看出 Linux 的 list_sort 相較我的 merge sort 快了一倍。
:::
## 運用 Valgrind 排除 qtest 實作的記憶體錯誤
### command history 錯誤
首先，執行 `qtest` 並開啟 Valgrind
```shell
$ make valgrind
```
可以看到報告不斷顯示 `blocks are still reachable`，代表在 `linenoise.c` 的 `linenoiseHistoryAdd` 有記憶體未被釋放。
```shell
==79220== 4 bytes in 1 blocks are still reachable in loss record 1 of 3
==79220== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==79220== by 0x4A7A50E: strdup (strdup.c:42)
==79220== by 0x111237: linenoiseHistoryAdd (linenoise.c:1236)
==79220== by 0x111DCA: linenoiseHistoryLoad (linenoise.c:1325)
==79220== by 0x10CBEE: main (qtest.c:1122)
```
根據 Valgrind 報告，找到 `linenoise.c` 的這行出現問題。在 `qtest.c` 執行 `linenoiseHistoryLoad` 會使用到。
```c=1236
linecopy = strdup(line);
```
> 根據作業說明，`still reachable` 代表程式結束時有未釋放的記憶體，不過卻還有指標指著，通常會發生在 global 變數。
`strdup` 會進行 `malloc`，而在 `linenoise.c` 中複製後的字串會被放入陣列 `history`。而這個 `history` 會在
從 `linenoise.c` 中可以發現有一個函式 `freeHistory` 會釋放 `history` 的記憶體。
```c=1190
static void freeHistory(void)
{
if (history) {
int j;
for (j = 0; j < history_len; j++)
free(history[j]);
free(history);
}
}
```
接著，我們從 `console.c` 中的 `run_console` 找到當 `has_infile ＝ true` 時，並不會對 `history` 有任何改動（包含釋放記憶體空間）。
> `has_infile ＝ true` 代表為 command 為從檔案輸入的。
```c=639
bool run_console(char *infile_name)
{
if (!push_file(infile_name)) {
report(1, "ERROR: Could not open source file '%s'", infile_name);
return false;
}
if (!has_infile) {
char *cmdline;
while ((cmdline = linenoise(prompt)) != NULL) {
interpret_cmd(cmdline);
linenoiseHistoryAdd(cmdline); /* Add to the history. */
linenoiseHistorySave(HISTORY_FILE); /* Save the history on disk. */
linenoiseFree(cmdline);
}
} else {
while (!cmd_done())
cmd_select(0, NULL, NULL, NULL, NULL);
}
return err_cnt == 0;
}
```
然後我們可以在 `qtest.c` 中發現，無論 command 是否為從檔案輸入它都會將 command history 載入（`linenoiseHistoryLoad`），進而導致記憶體空間沒有被釋放。
```c=1119
linenoiseSetCompletionCallback(completion);
linenoiseHistorySetMaxLen(HISTORY_LEN);
linenoiseHistoryLoad(HISTORY_FILE); /* Load the history at startup */
set_verblevel(level);
if (level > 1) {
set_echo(true);
}
if (logfile_name)
set_logfile(logfile_name);
add_quit_helper(queue_quit);
bool ok = true;
ok = ok && run_console(infile_name);
ok = ok && finish_cmd();
return ok ? 0 : 1;
}
```
針對上述觀察，我們可以改由讀取鍵盤指令的方式判斷是否有記憶體錯誤發生。發現確實沒有發生錯誤，驗證了我們的觀察。
```shell
$ valgrind -q --leak-check=full ./qtest
```
因此，我們可以藉由判斷 command 是否為從檔案（`infile_name`）輸入來判斷要不要使用 command history。重新執行 `make valgrind` 後就沒有回報記憶體錯誤了。
```c=1119
linenoiseSetCompletionCallback(completion);
linenoiseHistorySetMaxLen(HISTORY_LEN);
/* Do not load history when command input is from file*/
if (!infile_name)
linenoiseHistoryLoad(HISTORY_FILE); /* Load the history at startup */
set_verblevel(level);
if (level > 1) {
set_echo(true);
}
if (logfile_name)
set_logfile(logfile_name);
add_quit_helper(queue_quit);
bool ok = true;
ok = ok && run_console(infile_name);
ok = ok && finish_cmd();
return ok ? 0 : 1;
}
```
## 論文〈Dude, is my code constant time?〉
### 解釋 Student’s t-distribution
Student’s t-distribution，簡稱 t 分佈，改善 z 檢定在小樣本誤差大的問題。
Sign in with Wallet
Connect another wallet