# 2023q1 Homework1 (lab0)
contributed by < [LiChiiiii](https://github.com/LiChiiiii/lab0-c) >
## 開發環境
```shell
$ gcc --version
gcc (Ubuntu 11.3.0-1ubuntu1~22.04) 11.3.0
Copyright (C) 2021 Free Software Foundation, Inc.
This is free software; see the source for copying conditions. There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
$ lscpu
Architecture: x86_64
CPU op-mode(s): 32-bit, 64-bit
Address sizes: 39 bits physical, 48 bits virtual
Byte Order: Little Endian
CPU(s): 8
On-line CPU(s) list: 0-7
Vendor ID: GenuineIntel
Model name: Intel(R) Core(TM) i7-6700 CPU @ 3.40GHz
CPU family: 6
Model: 94
Thread(s) per core: 2
Core(s) per socket: 4
Socket(s): 1
Stepping: 3
CPU max MHz: 4000.0000
CPU min MHz: 800.0000
BogoMIPS: 6799.81
```
## 完成 queue.c
:::success
TOTAL SCORE : 100/100
:::
:::danger
注意書寫規範：中英文間用一個半形空白字元區隔。
:notes: jserv
> 已修正
> [name=LiChiiiii]
:::
#### `q_new`
利用 `malloc()` 配置記憶體空間，若記憶體配置失敗回傳 `NULL`，成功則使用 `list.h` 中的 `INIT_LIST_HEAD()` 來初始化 `head`。
```c
struct list_head *q_new()
{
struct list_head *head = malloc(sizeof(*head));
if (!head)
return NULL;
INIT_LIST_HEAD(head);
return head;
}
```
#### `q_free`
使用` list.h` 中的 `list_for_each_entry_safe()` 走訪佇列中每個節點，並使用 `q_release_element()` 釋放每一個元素，迴圈做完只會剩下指向佇列的 `l`，最後`free(l)`完成此功能。
:::info
`list_for_each_entry_safe()` 會額外使用一個指標 `safe` 來暫存下一次循環的 entry，使得每次在執行 `q_release_element()` 時不會影響迴圈的執行。
:::
```c
void q_free(struct list_head *l)
{
if(!l)
return;
element_t *itm=NULL, *is=NULL;
list_for_each_entry_safe (itm, is, l, list)
{
q_release_element(itm);
}
free(l);
}
```
#### `q_insert_head`
先替 `new_itm` （欲新增至佇列的元素）配置一個資料結構為 `element_t` 的記憶體空間。
```c
typedef struct {
char *value;
struct list_head list;
} element_t;
```
計算 `s` （欲新增至 `new_itm->value` 的字元）大小，並依據計算出的大小配置記憶體空間至 `new_itm->value` ，透過條件式確認配置成功後，利用 `memcpy()` 將 `s` 複製到 `new_itm->value` 中，最後呼叫 `list_add()` 將 `new_itm` 元素加入佇列的第一個。
剛開始忘記在判斷配置失敗後要執行 `free(new_itm)` （第11行），導致報錯 `error: Memory leak: new_itm [memleak]` 。
```c=
bool q_insert_head(struct list_head *head, char *s)
{
if (!head)
return false;
element_t *new_itm = malloc(sizeof(*new_itm));
if (!new_itm)
return false;
size_t size = strlen(s) + 1;
new_itm->value = malloc(size * sizeof(char));
if (!new_itm->value) {
free(new_itm);
return false;
}
memcpy(new_itm->value, s, size);
list_add(&new_itm->list, head);
return true;
}
```
#### `q_insert_tail`
與 **`q_insert_head`** 的思路一樣，將第15行改成 `list_add_tail()` 。
```c=
bool q_insert_tail(struct list_head *head, char *s)
{
if (!head)
return false;
element_t *new_itm = malloc(sizeof(*new_itm));
if (!new_itm)
return false;
size_t size = strlen(s) + 1;
new_itm->value = malloc(size * sizeof(char));
if (!new_itm->value) {
free(new_itm);
return false;
}
memcpy(new_itm->value, s, size);
list_add_tail(&new_itm->list, head);
return true;
}
```
#### `q_remove_head`
使用 `list_first_entry()` 找到佇列中第一個元素，並透過 `list_del()` 刪除此元素。
使用 `strncpy()` 來複製字串至 `sp` 以避免 buffer overflow 的問題，但會產生以下狀況，若來源字元數小於限制複製字元的個數，剩下未填滿的部分會全部補上 '\0'，反之則要手動補 '\0'（第9行）。
```c=
element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
if (!head)
return NULL;
element_t *itm = list_first_entry(head, element_t, list);
list_del(&itm->list);
if (sp != NULL) {
strncpy(sp, itm->value, bufsize - 1);
sp[bufsize - 1] = '\0';
}
return itm;
}
```
#### `q_remove_tail`
與 **`q_remove_head`** 的思路一樣，將第5行改成 `list_last_entry()` 。
```c=
element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize)
{
if (!head)
return NULL;
element_t *itm = list_last_entry(head, element_t, list);
list_del(&itm->list);
if (sp != NULL) {
strncpy(sp, itm->value, bufsize - 1);
sp[bufsize - 1] = '\0';
}
return itm;
}
```
#### `q_size`
使用 `list.h` 中的 `list_for_each()` 走訪佇列，紀錄佇列長度。
```c
int q_size(struct list_head *head)
{
int size = 0;
if (!head)
return size;
struct list_head *itm;
list_for_each (itm, head) {
size++;
}
return size;
}
```
#### `q_delete_mid`
利用 doubly-linked list 的特性，宣告兩個指標 `front` 和 `rear` 分別**從前向後**和**從後到前**同時移動，直到重疊即可找到 `mid` 並刪除。利用 `front!=rear->prev` 條件式來尋找含偶數個元素的佇列之 `mid` ，利用 `front!=rear` 條件式來尋找含奇數個元素的佇列之 `mid` （第6行）。
原本的寫法是先寫 `q_release_element(mid)` ，才接著寫 `list_del(front)` ，這樣會先把 `front` 指向的元素之記憶體空間釋放掉，導致報錯： `Segmentation fault occurred. You dereferenced a NULL or invalid pointerAborted (core dumped)`
```c=
bool q_delete_mid(struct list_head *head)
{
if (!head)
return false;
struct list_head *front = head->next, *rear = head->prev;
while (front != rear->prev && front != rear) {
front = front->next;
rear = rear->prev;
}
element_t *mid = list_entry(front, element_t, list);
list_del(front);
q_release_element(mid);
return true;
}
// https://leetcode.com/problems/delete-the-middle-node-of-a-linked-list/
```
#### `q_delete_dup`
`flag` ：決定當前元素是否為應被刪除的元素
利用迴圈比較當前元素 `cur_el` 以及前一個元素 `cur_prev_el` 之值是否相同，若相同則刪除 `cur_prev_el` 並設定 `flag=1` ，若不相同但 `flag=1` 則代表當前元素 `cur_el` 為重複元素中最後一個元素，也就是應被刪除的元素。
```c
bool q_delete_dup(struct list_head *head)
{
if (!head || list_is_singular(head) || list_empty(head))
return false;
int flag = 0;
struct list_head *cur, *safe = NULL;
list_for_each_safe (cur, safe, head) {
if (cur->prev == head)
continue;
element_t *cur_el = list_entry(cur, element_t, list);
element_t *cur_prev_el = list_entry(cur->prev, element_t, list);
if (!strcmp(cur_el->value, cur_prev_el->value)) {
list_del(cur->prev);
q_release_element(cur_prev_el);
flag = 1;
if (cur == head->prev){
list_del(cur);
q_release_element(cur_el);
return true;
}
} else if (flag == 1) {
list_del(cur->prev);
q_release_element(cur_prev_el);
flag = 0;
}
}
return true;
}
// https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/
```
#### `q_swap`
`flag` ：決定當前元素是否與前一個元素交換
若 `flag=0` 則設定 `flag=1`並跳過此元素，若 `flag=1` 則當前元素與前一個元素交換（前一個元素移到當前元素後面）並設定 `flag=0` 。
```c
void q_swap(struct list_head *head)
{
if (!head || list_is_singular(head) || list_empty(head))
return;
int flag = 0;
struct list_head *cur, *safe = NULL;
list_for_each_safe (cur, safe, head) {
if (cur->prev == head || flag == 0) {
flag = 1;
continue;
} else if (flag == 1) {
list_move(cur->prev, cur);
flag = 0;
}
}
return;
}
// https://leetcode.com/problems/swap-nodes-in-pairs/
```
#### `q_reverse`
`list_move()` 會先執行 `list_del()` 將當前指向的元素刪除，在執行 `list_add()` 將元素新增至佇列最前端。第 7 行使用 `list_for_each_safe()` 可以允許當前節點從佇列中移除，用 `list_for_each()` 會導致 infinite loop 。
```c=
void q_reverse(struct list_head *head)
{
if(!head || list_is_singular(head) || list_empty(head))
return;
struct list_head *cur , *safe=NULL;
list_for_each_safe(cur, safe, head){
list_move(cur, head);
}
}
```
#### `q_reverseK`
讓指標邊走邊數 k 個元素，到第 k 個元素進行 reverse 。
`cur_prev_k` 存放 `top` 為 1 的元素之記憶體位址，也就是記錄當前元素要進行 reverse時的前 k 個元素之記憶體位址。
:::info
宣告改成 `*cur_prev_k = head->next` 會出現無限迴圈，因為 `cur_prev_k` 會跟著指向的元素做移動，導致 `cur_prev_k` 永遠不會等於 `tmp` ，也就是離不開 while 迴圈。
:::
```c
void q_reverseK(struct list_head *head, int k)
{
if(!head || list_is_singular(head) || list_empty(head))
return;
int top = 0;
struct list_head *cur, **cur_prev_k = &(head->next),
struct list_head *safe=NULL, *tmp=NULL;
list_for_each_safe(cur, safe, head){
top++;
if(top%k==0){
tmp = cur;
while(*cur_prev_k != tmp){
list_move(tmp->prev, cur);
cur = cur->next;
}
cur_prev_k = &(cur->next);
}
}
// https://leetcode.com/problems/reverse-nodes-in-k-group/
}
```
#### `q_sort`
參考[你所不知道的 c 語言: linked list 和非連續記憶體](https://hackmd.io/@sysprog/c-linked-list#Merge-Sort-%E7%9A%84%E5%AF%A6%E4%BD%9C)、 [Linked List Sort](https://npes87184.github.io/2015-09-12-linkedListSort/) 中提到的 Merge Sort 以及 [seasonwang0905](https://hackmd.io/@seasonwang/B1B0lVqpo) 的程式碼實作。
:::danger
避免張貼完整程式碼，列出關鍵程式碼並闡述你的觀察、推論，和考慮議題。
:notes: jserv
> 已修正
> [name=LiChiiiii]
:::
排序實作總共用到三個函式：
1. `merge_two_list()` ：將兩個佇列合併成一個已完成排序的佇列
2. `mergesort()`：將未排序的佇列進行不斷的分割，直到剩一個節點即開始執行`merge_two_list()`，直到遞迴結束。
3. `q_sort()`：先將尚未排序的佇列變成 singly-linked list ，這樣排序過程中就不用維持 doubly-linked list 。等到執行完 `mergesort()` 排序完畢後，再重新連結 prev 即可。
```c
/* Merge two list into one queue */
struct list_head *merge_two_list(struct list_head *l1, struct list_head *l2)
{
struct list_head *temp = NULL;
struct list_head **indirect = &temp;
for (struct list_head **node = NULL; l1 && l2; *node = (*node)->next) {
element_t *e1 = list_entry(l1, element_t, list);
element_t *e2 = list_entry(l2, element_t, list);
if (strcmp(e1->value, e2->value) < 0)
node = &l1;
else
node = &l2;
*indirect = *node;
indirect = &(*indirect)->next;
}
*indirect = (struct list_head *) ((u_int64_t) l1 | (u_int64_t) l2);
return temp;
}
/* Divide the queue and sort every element */
struct list_head *mergesort(struct list_head *head)
{
if (!head || !head->next)
return head;
struct list_head *fast = head, *slow = head;
while (fast && fast->next) {
fast = fast->next->next;
slow = slow->next;
}
fast = slow;
slow->prev->next = NULL;
struct list_head *l1 = mergesort(head);
struct list_head *l2 = mergesort(fast);
return merge_two_list(l1, l2);
}
/* Sort elements of queue in ascending order */
void q_sort(struct list_head *head)
{
if (!head || list_empty(head))
return;
head->prev->next = NULL;
head->next = mergesort(head->next);
struct list_head *current = head, *next = head->next;
while (next) {
next->prev = current;
current = next;
next = next->next;
}
current->next = head;
head->prev = current;
}
```
#### `q_descend`
從 list 尾端向前比較大小，比從 list 前端向後比較大小來的簡單。前者只要反向比較下一個元素小於當前元素即可刪除，後者則是順向比較當前元素之前的所有元素是否小於當前元素。
```c
int q_descend(struct list_head *head)
{
if (!head || list_is_singular(head) || list_empty(head))
return 0;
struct list_head *cur = head->prev;
while (cur->prev != head) {
element_t *cur_el = list_entry(cur, element_t, list);
element_t *cur_prev_el = list_entry(cur->prev, element_t, list);
int cmp = strcmp(cur_el->value, cur_prev_el->value);
if (cmp > 0) {
list_del(cur->prev);
q_release_element(cur_prev_el);
} else {
cur = cur->prev;
}
}
return q_size(head);
}
// https://leetcode.com/problems/remove-nodes-from-linked-list/
```
#### `q_merge`
使用 `queue.h` 中定義的資料結構 `queue_contex_t` 來表示每一個queue。
```c
typedef struct {
struct list_head *q;
struct list_head chain;
int size;
int id;
} queue_contex_t;
```
透過 `list_for_each_entry()` 查看所有的佇列，並將佇列合併，最後將合併起來的queue做排序。
```c
/* Merge all the queues into one sorted queue, which is in ascending order */
int q_merge(struct list_head *head)
{
if (!head || list_empty(head))
return 0;
else if(list_is_singular(head))
return list_entry(head, queue_contex_t,chain)->size;
queue_contex_t *que = list_entry(head->next, queue_contex_t,chain);
queue_contex_t *cur_que = NULL;
list_for_each_entry(cur_que, head, chain)
{
if(cur_que == que)
continue;
list_splice_init(cur_que->q, que->q);
que->size = que->size + cur_que->size;
cur_que->size = 0;
}
q_sort(que->q);
return que->size;
// https://leetcode.com/problems/merge-k-sorted-lists/
}
```
## 改進 `web` 命令
原始程式碼執行 `web` 命令可開啟網頁伺服器，一旦 web_fd > 0 表示成功開啟 web server 。
```c
/* console.c */
static int web_fd;
static bool do_web(int argc, char *argv[])
{
int port = 9999;
if (argc == 2) {
if (argv[1][0] >= '0' && argv[1][0] <= '9')
port = atoi(argv[1]);
}
web_fd = web_open(port);
if (web_fd > 0) {
printf("listen on port %d, fd is %d\n", port, web_fd);
use_linenoise = false;
} else {
perror("ERROR");
exit(web_fd);
}
return true;
}
```
在 `web.c` 可以看到已經寫好在 web 接收訊息和傳送訊息的處理方式。
```c
/* web.c */
char *web_recv(int fd, struct sockaddr_in *clientaddr)
{
http_request_t req;
parse_request(fd, &req);
char *p = req.filename;
/* Change '/' to ' ' */
while (*p) {
++p;
if (*p == '/')
*p = ' ';
}
char *ret = malloc(strlen(req.filename) + 1);
strncpy(ret, req.filename, strlen(req.filename) + 1);
return ret;
}
void web_send(int out_fd, char *buf)
{
writen(out_fd, buf, strlen(buf));
}
```
問題在於網頁伺服器開啟後，處理命令列的 `linenoise` 套件無法使用，因此嘗試改寫 `linenoise.c` 用 [select()](https://man7.org/linux/man-pages/man2/select.2.html) 同時處理 stdin 及 socket。
在`line_edit` 新增參數 `web_fd` ，當 web_fd != 0 就使用 `select()` 監聽。若從 web 輸入訊息（第33行），則將訊息複製到 buf 中並透過 linenoise 處理命令，同時也傳送 HTTP 回應的 header 訊息給客戶端，表示回應成功，並關閉 socket 。若從命令列輸入訊息（第43行），則保持原本做法處理。
```c=
/* linenoise.c */
static int line_edit(int stdin_fd,
int stdout_fd,
char *buf,
size_t buflen,
const char *prompt,
int web_fd)
{
...
while (1) {
signed char c;
int nread;
char seq[5];
if (web_fd) {
fd_set set;
FD_ZERO(&set);
FD_SET(web_fd, &set);
FD_SET(stdin_fd, &set);
int rv = select(web_fd + 1, &set, NULL, NULL, NULL);
struct sockaddr_in clientaddr;
socklen_t clientlen = sizeof(clientaddr);
int connfd;
switch (rv) {
case -1:
perror("select"); /* an error occurred */
continue;
case 0:
printf("timeout occurred\n"); /* a timeout occurred */
continue;
default:
if (FD_ISSET(web_fd, &set)) {
FD_CLR(web_fd, &set);
connfd = accept(web_fd, (struct sockaddr *) &clientaddr, &clientlen);
strncpy(buf, web_recv(connfd, &clientaddr), buflen);
char *header =
"HTTP/1.1 200 OK\r\nContent-Type: text/plain\r\n\r\n";
web_send(web_connfd, header);
close(web_connfd);
return strlen(buf);
} else if (FD_ISSET(stdin_fd, &set)) {
nread = read(l.ifd, &c, 1);
if (nread <= 0)
return l.len;
}
break;
}
} else {
nread = read(l.ifd, &c, 1);
if (nread <= 0)
return l.len;
}
}
...
}
```
> 參考老師的[整合網頁伺服器](https://hackmd.io/@sysprog/linux2023-lab0/%2F%40sysprog%2Flinux2023-lab0-c)
## 實作 `shuffle` 命令
利用 Fisher–Yates shuffle 演算法來實作洗牌。
```c
/* queue.c */
void value_swap(struct list_head *node1, struct list_head *node2)
{
element_t *node1_ele = list_entry(node1, element_t, list);
element_t *node2_ele = list_entry(node2, element_t, list);
char *temp;
temp = node1_ele->value;
node1_ele->value = node2_ele->value;
node2_ele->value = temp;
}
void q_shuffle(struct list_head *head)
{
if (!head || list_is_singular(head) || list_empty(head))
return;
struct list_head *last = head->prev;
struct list_head *cur = head->next;
int len = q_size(head);
srand(time(NULL));
while(len)
{
int i = rand() % len;
while(i)
{
cur = cur->next;
i--;
}
value_swap(cur,last);
last = last->prev;
cur = head->next;
len--;
}
}
```
原本 swap 的寫法是透過 `list_move()` 來移動兩個節點位置，但執行 shuffle 時偶爾會失敗，後來才改成交換 value 的方法。
```c
void node_swap(struct list_head *node1, struct list_head *node2)
{
struct list_head *node1_prev = node1->prev;
struct list_head *node2_prev = node2->prev;
list_move(node2, node1_prev);
list_move(node1, node2_prev);
}
```
除了實作程式碼，還需要在 `qtest.c` 新增命令和執行函式。
```c
ADD_COMMAND(shuffle, "Implement Fisher–Yates shuffle","");
```
```c
static inline bool do_shuffle(int argc, char *argv[])
{
if (argc != 1) {
report(1, "%s takes no arguments", argv[0]);
return false;
}
if (!current) {
report(3, "Warning: Try to operate null queue");
return false;
}
error_check();
set_noallocate_mode(true);
if (current && exception_setup(true))
q_shuffle(current->q);
exception_cancel();
set_noallocate_mode(false);
return q_show(3);
}
```
## Address Sanitizer
在 `Makefile` 中發現已定義一個變數稱 `SANITIZER` ，當 `SANITIZER` 變數設置為 1，即可啟用 address sanitizer。
```
# Enable sanitizer(s) or not
ifeq ("$(SANITIZER)","1")
# https://github.com/google/sanitizers/wiki/AddressSanitizerFlags
CFLAGS += -fsanitize=address -fno-omit-frame-pointer -fno-common
LDFLAGS += -fsanitize=address
endif
```
執行下列命令開啟 address sanitizer ，並重新編譯，沒有出現任何關於記憶體之錯誤。
```shell
make clean
make SANITIZER=1
make test
```
:::spoiler 執行結果
```shell
$ make test
scripts/driver.py -c
--- Trace Points
+++ TESTING trace trace-01-ops:
# Test of insert_head and remove_head
--- trace-01-ops 5/5
+++ TESTING trace trace-02-ops:
# Test of insert_head, insert_tail, remove_head, remove_tail, and delete_mid
--- trace-02-ops 6/6
+++ TESTING trace trace-03-ops:
# Test of insert_head, insert_tail, remove_head, reverse and merge
--- trace-03-ops 6/6
+++ TESTING trace trace-04-ops:
# Test of insert_head, insert_tail, size, swap, and sort
--- trace-04-ops 6/6
+++ TESTING trace trace-05-ops:
# Test of insert_head, insert_tail, remove_head, reverse, size, swap, and sort
--- trace-05-ops 6/6
+++ TESTING trace trace-06-ops:
# Test of insert_head, insert_tail, delete duplicate, sort, descend and reverseK
--- trace-06-ops 6/6
+++ TESTING trace trace-07-string:
# Test of truncated strings
--- trace-07-string 6/6
+++ TESTING trace trace-08-robust:
# Test operations on empty queue
--- trace-08-robust 6/6
+++ TESTING trace trace-09-robust:
# Test remove_head with NULL argument
--- trace-09-robust 6/6
+++ TESTING trace trace-10-robust:
# Test operations on NULL queue
--- trace-10-robust 6/6
+++ TESTING trace trace-11-malloc:
# Test of malloc failure on insert_head
--- trace-11-malloc 6/6
+++ TESTING trace trace-12-malloc:
# Test of malloc failure on insert_tail
--- trace-12-malloc 6/6
+++ TESTING trace trace-13-malloc:
# Test of malloc failure on new
--- trace-13-malloc 6/6
+++ TESTING trace trace-14-perf:
# Test performance of insert_tail, reverse, and sort
--- trace-14-perf 6/6
+++ TESTING trace trace-15-perf:
# Test performance of sort with random and descending orders
# 10000: all correct sorting algorithms are expected pass
# 50000: sorting algorithms with O(n^2) time complexity are expected failed
# 100000: sorting algorithms with O(nlogn) time complexity are expected pass
--- trace-15-perf 6/6
+++ TESTING trace trace-16-perf:
# Test performance of insert_tail
--- trace-16-perf 6/6
+++ TESTING trace trace-17-complexity:
# Test if time complexity of q_insert_tail, q_insert_head, q_remove_tail, and q_remove_head is constant
Probably constant time
Probably constant time
Probably constant time
Probably constant time
--- trace-17-complexity 5/5
--- TOTAL 100/100
```
:::
## Valgrind
執行 `make valgrind` 沒有出現相關問題
:::spoiler 執行結果
```
$ make valgrind
# Explicitly disable sanitizer(s)
make clean SANITIZER=0 qtest
make[1]: Entering directory '/home/lichi/Documents/lab0-c'
rm -f qtest.o report.o console.o harness.o queue.o random.o dudect/constant.o dudect/fixture.o dudect/ttest.o shannon_entropy.o linenoise.o web.o .qtest.o.d .report.o.d .console.o.d .harness.o.d .queue.o.d .random.o.d .dudect/constant.o.d .dudect/fixture.o.d .dudect/ttest.o.d .shannon_entropy.o.d .linenoise.o.d .web.o.d *~ qtest /tmp/qtest.*
rm -rf .dudect
rm -rf *.dSYM
(cd traces; rm -f *~)
CC qtest.o
CC report.o
CC console.o
CC harness.o
CC queue.o
CC random.o
CC dudect/constant.o
CC dudect/fixture.o
CC dudect/ttest.o
CC shannon_entropy.o
CC linenoise.o
CC web.o
LD qtest
make[1]: Leaving directory '/home/lichi/Documents/lab0-c'
cp qtest /tmp/qtest.J1q9iz
chmod u+x /tmp/qtest.J1q9iz
sed -i "s/alarm/isnan/g" /tmp/qtest.J1q9iz
scripts/driver.py -p /tmp/qtest.J1q9iz --valgrind
--- Trace Points
+++ TESTING trace trace-01-ops:
# Test of insert_head and remove_head
--- trace-01-ops 5/5
+++ TESTING trace trace-02-ops:
# Test of insert_head, insert_tail, remove_head, remove_tail, and delete_mid
--- trace-02-ops 6/6
+++ TESTING trace trace-03-ops:
# Test of insert_head, insert_tail, remove_head, reverse and merge
--- trace-03-ops 6/6
+++ TESTING trace trace-04-ops:
# Test of insert_head, insert_tail, size, swap, and sort
--- trace-04-ops 6/6
+++ TESTING trace trace-05-ops:
# Test of insert_head, insert_tail, remove_head, reverse, size, swap, and sort
--- trace-05-ops 6/6
+++ TESTING trace trace-06-ops:
# Test of insert_head, insert_tail, delete duplicate, sort, descend and reverseK
--- trace-06-ops 6/6
+++ TESTING trace trace-07-string:
# Test of truncated strings
--- trace-07-string 6/6
+++ TESTING trace trace-08-robust:
# Test operations on empty queue
--- trace-08-robust 6/6
+++ TESTING trace trace-09-robust:
# Test remove_head with NULL argument
--- trace-09-robust 6/6
+++ TESTING trace trace-10-robust:
# Test operations on NULL queue
--- trace-10-robust 6/6
+++ TESTING trace trace-11-malloc:
# Test of malloc failure on insert_head
--- trace-11-malloc 6/6
+++ TESTING trace trace-12-malloc:
# Test of malloc failure on insert_tail
--- trace-12-malloc 6/6
+++ TESTING trace trace-13-malloc:
# Test of malloc failure on new
--- trace-13-malloc 6/6
+++ TESTING trace trace-14-perf:
# Test performance of insert_tail, reverse, and sort
--- trace-14-perf 6/6
+++ TESTING trace trace-15-perf:
# Test performance of sort with random and descending orders
# 10000: all correct sorting algorithms are expected pass
# 50000: sorting algorithms with O(n^2) time complexity are expected failed
# 100000: sorting algorithms with O(nlogn) time complexity are expected pass
--- trace-15-perf 6/6
+++ TESTING trace trace-16-perf:
# Test performance of insert_tail
--- trace-16-perf 6/6
+++ TESTING trace trace-17-complexity:
# Test if time complexity of q_insert_tail, q_insert_head, q_remove_tail, and q_remove_head is constant
Probably constant time
Probably constant time
Probably constant time
Probably constant time
--- trace-17-complexity 5/5
--- TOTAL 100/100
```
:::
### 使用 Massif 查看記憶體的狀況
```
valgrind --tool=massif ./qtest -f traces/trace-17-complexity.cmd
```
以下是 `traces/trace-17-complexity.cmd` 的記憶體使用狀況
在 trace-17 執行了 `q_insert_head()` 、 `q_insert_tail()` 、 `q_remove_head()` 以及 `q_remove_tail()` 四個函式，在圖中的最右邊可以看到，執行結束後記憶體並沒有釋放完全，此部分待確認。
## Linux 核心原始程式碼的 `lib/list_sort.c `
#### 比較 `lib/list_sort.c` 與自行實作的合併排序演算法差異
由於無法新增 `queue.h` 的定義，所以就把 `lib_sort.c` 的程式放進 `qtest.c` ，新增一個 option 來切換 sort 的實作，這樣很快就可以看看自己實作的效能跟 Linux 核心程式碼的差距。
在 `qtest.c` 當中把 `do_sort()` 函式的部分改為這樣：
```c
if (exception_setup(true)) {
if (is_enable_linux_sort()) {
q_sort_linux(l_meta.l);
} else {
q_sort(l_meta.l);
}
}
```
參考 [komark06](https://hackmd.io/@komark06/SyCUIEYpj#引入-liblist_sortc) 對 `list_sort.c` 的修改方法，將程式放入 `qtest.c` 執行。
接著利用以下的 command 來比較排序時間：
```
option fail 0
option malloc 0
new
ih dolphin 1000000
it gerbil 1000000
reverseK 100
time sort
option linux_qsort 1
new
ih dolphin 1000000
it gerbil 1000000
reverseK 100
time sort
```
:::warning
執行 `list_sort.c` 會出現 `Segmentation fault occurred.` ，應是引入程式碼時有錯誤，待處理。
:::
## 研讀論文〈Dude, is my code constant time?〉
論文中提出了工具 **dudect** ，可以用來檢測一段程式是否 constant time 執行。
測試方式主要分成三個步驟：
1. Measure execution time : 輸入**固定資料**和**隨機資料**來量測目標函式耗費的時間。每次隨機選擇一種類型資料並重複執行得到量測結果。
2. Apply post-processing：大於某個 threshold 的執行時間不列入統計檢定。
3. Apply statistical test： 論文中提及兩個檢驗方式 `t-test` （採用 [Welch's t-test](https://en.wikipedia.org/wiki/Welch%27s_t-test) ） 和 `Non-parametric tests`
:::info
:stars: **t-test**
t-test 是一個常用來協助判斷**比較兩組資料是否具有顯著差異**的統計方法之一。在這裡我們試圖**反證兩組資料時間分佈相等**，也就是說當 t-test 拒絕假說（無法證明平均值的差異），表示執行時間為 constant time。
:::
### 程式實作原理
在 lab0-c 中，當 `simulation` 開啟後會將 `is_xx_xx_const()` 作為目標函式進行時間複雜度測試 `test_const()` $\rightarrow$ `doit()` ，並根據論文中的三個步驟實作：
1. `measure()` 和 `differentiate()`：計算目標函式執行時間
2. `update_statistics()`：處理取得的資料
3. `report()`：利用 [Welch's t-test](https://en.wikipedia.org/wiki/Welch%27s_t-test) 驗證目標函式是否為 constant time
```c
/* dudect/fixture.c */
static bool doit(int mode)
{
...
bool ret = measure(before_ticks, after_ticks, input_data, mode);
differentiate(exec_times, before_ticks, after_ticks);
update_statistics(exec_times, classes);
ret &= report();
...
return ret;
}
```
在 `measure()` 函式發現計算過程中**直接減掉要做刪除的次數**（第10行），但測試流程應該要是**紀錄所有資料再去做第二步驟的資料處理**。
```c
/* dudect/constant.h */
#define N_MEASURES 150
#define DROP_SIZE 20
```
```c=
/* dudect/constant.c */
bool measure(int64_t *before_ticks,
int64_t *after_ticks,
uint8_t *input_data,
int mode)
{
...
switch (mode) {
case DUT(insert_head):
for (size_t i = DROP_SIZE; i < N_MEASURES - DROP_SIZE; i++) {
char *s = get_random_string();
dut_new();
dut_insert_head(
get_random_string(),
*(uint16_t *) (input_data + i * CHUNK_SIZE) % 10000);
int before_size = q_size(l);
before_ticks[i] = cpucycles();
dut_insert_head(s, 1);
after_ticks[i] = cpucycles();
int after_size = q_size(l);
dut_free();
if (before_size != after_size - 1)
return false;
}
break;
...
```
因此將該部分改成做完 `N_MEASURES` 次的紀錄後進行排序再刪除前後各 `DROP_SIZE` 個資料點，即可每次皆通過 `trace-17-complexity` 的測試。
> 參考 [KHLee529](https://hackmd.io/@KHLee529/linux2023-lab0 ) 解決方法
## Debug 紀錄
* 編譯時出現以下錯誤訊息
```!
gcc: internal compiler error: Segmentation fault signal terminated program as
Please submit a full bug report,
with preprocessed source if appropriate.
See <file:///usr/share/doc/gcc-11/README.Bugs> for instructions.
make: *** [Makefile:54: qtest.o] Error 4
```
> 1. 檢查gcc版本
> 2. 檢查可用的記憶體空間
> 3. 重新啟動主機
Sign in with Wallet
Connect another wallet