# 2022q1 Homework1 (lab0)
contributed by < [tommy2234](https://github.com/tommy2234/lab0-c) >
[作業要求](https://hackmd.io/@sysprog/linux2022-lab0)
## 實驗環境
```shell
$ 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: 140
Model name: 11th Gen Intel(R) Core(TM) i5-1135G7 @ 2.40GHz
Stepping: 1
CPU MHz: 2400.000
CPU max MHz: 4200.0000
CPU min MHz: 400.0000
BogoMIPS: 4838.40
Virtualization: VT-x
L1d cache: 192 KiB
L1i cache: 128 KiB
L2 cache: 5 MiB
L3 cache: 8 MiB
NUMA node0 CPU(s): 0-7
```
:::danger
更新作業要求！
:notes: jserv
:::
## 開發過程
### q_new
將 queue 的頭部用 malloc 創造之後套用 INIT_LIST_HEAD 將其初始化。
:::danger
用通順的漢語書寫，考慮到日後會去科技公司面試，你現在所準備的，其實就是日後面試過程的「逐字稿」
:notes: jserv
:::
```cpp
struct list_head *q_new()
{
struct list_head *queue = malloc(sizeof(struct list_head));
if (!queue)
return NULL;
INIT_LIST_HEAD(queue);
return queue;
}
```
### q_free
先 free element 裡面的 value，再 free 外層element，最後再把 head free掉
```cpp
void q_free(struct list_head *l)
{
if (!l)
return;
struct list_head *tmp = l->next;
while (!list_empty(l)) {
list_del(tmp);
element_t *ele = container_of(tmp, element_t, list);
free(ele->value);
free(ele);
tmp = l->next;
}
free(l);
}
```
### q_insert_head
malloc 一個新的 element，value 所需的大小可用 strlen(s)+1 取得。
另外 strcpy 不安全故使用 strncpy。
```cpp
bool q_insert_head(struct list_head *head, char *s)
{
if (!head)
return false;
element_t *ele = malloc(sizeof(element_t));
if (!ele)
return false;
ele->value = malloc(strlen(s) + 1);
if (!ele->value) {
free(ele);
return false;
}
strncpy(ele->value, s, strlen(s) + 1);
list_add(&ele->list, head);
return true;
}
```
### q_insert_tail
和 q_insert_head 概念相同，只是改成修改 list 尾端
```cpp
bool q_insert_tail(struct list_head *head, char *s)
{
if (!head)
return false;
element_t *ele = malloc(sizeof(element_t));
if (!ele)
return false;
ele->value = malloc(strlen(s) + 1);
if (!ele->value) {
free(ele);
return false;
}
strncpy(ele->value, s, strlen(s) + 1);
list_add_tail(&ele->list, head);
return true;
}
```
### q_remove_head
移除頭部之後將 value copy 到 sp，重要的是 strncpy 可能不會 copy 到最後的 '\0'，因此要手動加上。
根據 man page:
> The strncpy() function is similar, except that at most n bytes of src
> are copied. Warning: If there is no null byte among the first n bytes
> of src, the string placed in dest will not be null-terminated.
```cpp
element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
if (!head || list_empty(head))
return NULL;
struct list_head *target = head->next;
element_t *tmp = container_of(target, element_t, list);
list_del_init(target);
if (sp) {
strncpy(sp, tmp->value, bufsize - 1);
sp[bufsize - 1] = '\0';
}
return tmp;
}
```
### q_size
把 list 走一遍，數數看有幾個
```cpp
int q_size(struct list_head *head)
{
if (!head || list_empty(head))
return 0;
struct list_head *node;
int count = 0;
list_for_each (node, head)
count++;
return count;
}
```
### q_reverse
從頭開始，利用 ptr1(current node) 和 ptr2(next node) 兩個指標將每個 node 的 next 和 prev 交換
```cpp
void q_reverse(struct list_head *head)
{
if (!head || list_empty(head))
return;
struct list_head *ptr1 = head, *ptr2 = ptr1->next;
do {
ptr2->prev = ptr2->next;
ptr2->next = ptr1;
ptr1 = ptr2;
ptr2 = ptr2->prev;
} while (ptr1 != head);
}
```
### q_delete_mid
先算出 mid 是誰，走訪到他的時候把它刪除並 free 掉
```cpp
if (!head || list_empty(head))
return NULL;
struct list_head *node;
int count = 0, mid = 0;
list_for_each (node, head)
count++;
mid = (float) count / 2 > count / 2 ? count / 2 + 1 : count / 2;
count = 0;
element_t *ele;
list_for_each_entry (ele, head, list) {
if (++count == mid) {
list_del(&ele->list);
free(ele->value);
free(ele);
break;
}
}
return true;
}
```
### q_delete_dup
start 指向目前的 node ，end 指向和目前 value 開始不同的第一個 node ，並且判斷是否有多個 node 包含目前的 value ，是的話就可以一路從 start 刪到 end 前一個。
```cpp
bool q_delete_dup(struct list_head *head)
{
if (!head)
return false;
if (list_empty(head) || list_is_singular(head))
return true;
struct list_head *start = head->next, *end = start->next;
while (start != head) {
element_t *ele1 = container_of(start, element_t, list);
element_t *ele2 = container_of(end, element_t, list);
bool found = false;
while (strcmp(ele1->value, ele2->value) == 0) {
found = true;
end = end->next;
if (end == head)
break;
ele2 = container_of(end, element_t, list);
}
while (start != end) {
struct list_head *next = start->next;
if (found) {
list_del(start);
element_t *tmp = container_of(start, element_t, list);
free(tmp->value);
free(tmp);
}
start = next;
}
end = start->next;
}
return true;
}
```
### q_swap
只要將相鄰兩個人的 value 指到彼此的就好了
```cpp
void q_swap(struct list_head *head)
{
if (!head || list_empty(head) || list_is_singular(head))
return;
struct list_head *first = head->next, *second = first->next;
element_t *ele1, *ele2;
while (first != head && second != head) {
ele1 = container_of(first, element_t, list);
ele2 = container_of(second, element_t, list);
char *tmp = ele1->value;
ele1->value = ele2->value;
ele2->value = tmp;
first = first->next->next;
second = second->next->next;
}
}
```
### q_sort
為了方便判定 sort 時終結走訪的時機，我先將尾端指到NULL，等 sort 完再接回來。
另外 sort 時我只針對 next 串接，因此最後也要接回 prev
```cpp
void q_sort(struct list_head *head)
{
if (!head || list_empty(head))
return;
// set tail to NULL for the convenience of terminating the iteration
head->prev->next = NULL;
// merge sort
head->next = merge_sort(head->next);
// set prev of each node, and connect head and tail
struct list_head *tmp;
for (tmp = head; tmp->next; tmp = tmp->next)
tmp->next->prev = tmp;
tmp->next = head;
head->prev = tmp;
}
```
merge_sort 參考下圖
```cpp
struct list_head *merge_sort(struct list_head *head)
{
if (!head || !head->next)
return head;
struct list_head *right = head->next;
struct list_head *left = head;
// split list
while (right && right->next) {
left = left->next;
right = right->next->next;
}
right = left->next;
left->next = NULL;
// sort each list
struct list_head *l1 = merge_sort(head);
struct list_head *l2 = merge_sort(right);
// merge sorted l1 and sorted l2
return merge(l1, l2);
}
```
merge 階段練習採用〈[你所不知道的 C 語言: linked list 和非連續記憶體](https://hackmd.io/@sysprog/c-linked-list)〉中的"有品味"版本
```cpp
struct list_head *merge(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 = container_of(L1, element_t, list);
ele2 = container_of(L2, element_t, list);
node = strcmp(ele1->value, ele2->value) < 0 ? &L1 : &L2;
*ptr = *node;
ptr = &(*node)->next;
}
*ptr = (struct list_head *) ((uintptr_t) L1 | (uintptr_t) L2);
return head;
}
```
## 我的 merge sort 和 linux kernel 中的lib/list_sort.c 效能比較
- 一開始整份複製過來，慘了！type 有缺，於是在以下三個地方找到缺漏的 type。（bootlin真好用！）
[list_cmp_func_t](https://elixir.bootlin.com/linux/latest/source/include/linux/list_sort.h#L9)
[likely , unlikely](https://elixir.bootlin.com/linux/latest/source/tools/include/linux/compiler.h#L93)
[u8](https://elixir.bootlin.com/linux/latest/source/arch/powerpc/boot/types.h#L9)
- 可以使用了！，接著修改 qtest.c ， 將 sort 新增一個 argument "l" ， sort l 代表要使用 list_sort.c 中的版本。
```cpp
ADD_COMMAND(sort,
" [option] | Sort queue in ascending order. Use linux's "
```
- 開始測試
輸到脫褲了！，linux 的 merge sort 大約只要我的6成時間。
原因可從註解中略知一二
```cpp
* This mergesort is as eager as possible while always performing at least
* 2:1 balanced merges. Given two pending sublists of size 2^k, they are
* merged to a size-2^(k+1) list as soon as we have 2^k following elements.
*
* Thus, it will avoid cache thrashing as long as 3*2^k elements can
* fit into the cache. Not quite as good as a fully-eager bottom-up
* mergesort, but it does use 0.2*n fewer comparisons, so is faster in
* the common case that everything fits into L1.
```
:::danger
文字訊息不要用圖片展現。考量:
1. 對視覺障礙者更友善
2. 後續資訊檢索的便利
:notes: jserv
:::
## 新增 Shuffle command
從 ADD_COMMAND 這 macro 可知道只要新增 shuffle 命令 ， add_cmd 就會吃到 do_shuffle 函式
```cpp
#define ADD_COMMAND(cmd, msg) add_cmd(#cmd, do_##cmd, msg)
```
使用 Fisher–Yates shuffle
```cpp
void q_shuffle(struct list_head *head)
{
if (!head || list_empty(head))
return;
srand(time(NULL));
int size = q_size(head);
struct list_head *ptr = head->prev;
element_t *target, *last;
for (int i = size - 1; i >= 1; i--, ptr = ptr->prev) {
int idx = rand() % (i + 1); // random index in range [0, i]
last = container_of(ptr, element_t, list);
target = container_of(get_node(head, idx), element_t, list);
char *tmp = last->value;
last->value = target->value;
target->value = tmp;
}
}
```
## 增加 web command
- 首先引用 [tiny-web-server](https://github.com/7890/tiny-web-server) 的 tiny.c 並稍做修改。
除了刪減用不到的程式碼之外，也將其中的 main function 簡化成回傳 listenfd ，當成一個外部的接口。
```cpp
int get_listenfd(int argc, char **argv)
{
if (argc > 1 && (!strcmp(argv[1], "-h") || !strcmp(argv[1], "--help"))) {
print_help();
return 0;
}
// struct sockaddr_in clientaddr;
int default_port = DEFAULT_PORT, listenfd;
// connfd;
char buf[256];
char *path = getcwd(buf, 256);
// socklen_t clientlen = sizeof clientaddr;
if (argc == 2) {
if (argv[1][0] >= '0' && argv[1][0] <= '9') {
default_port = atoi(argv[1]);
} else {
path = argv[1];
if (chdir(path) != 0) {
perror(path);
exit(1);
}
}
} else if (argc == 3) {
default_port = atoi(argv[2]);
path = argv[1];
if (chdir(path) != 0) {
perror(path);
exit(1);
}
}
printf("serve directory '%s'\n", path);
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);
return listenfd;
}
```
- 在 tiny.c 加入處理遠端輸入的 process() 函式 ，將收到的 command 取出整理格式並且回傳。
```cpp
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.function_name);
char *p = req.function_name;
/* Change '/' to ' ' */
while (*p) {
++p;
if (*p == '/') {
*p = ' ';
}
}
#ifdef LOG_ACCESS
log_access(status, clientaddr, &req);
#endif
char *ret = malloc(strlen(req.function_name) + 1);
strncpy(ret, req.function_name, strlen(req.function_name) + 1);
return ret;
}
```
- 模仿老師的範例，在 linenoiseEdit 稍做修改 ，將 listenfd 加入 set 之中，利用 select() 同時監控 stdin_fd 和 listenfd，若 listenfd != 0 ，就可以接收遠端的輸入並當成 command line 處理。
```cpp
while (1) {
signed char c;
int nread;
char seq[3];
fd_set set;
FD_ZERO(&set);
FD_SET(listenfd, &set);
FD_SET(stdin_fd, &set);
int rv = select(listenfd + 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 (listenfd && FD_ISSET(listenfd, &set)) {
connfd = accept(listenfd, (SA *) &clientaddr, &clientlen);
char *p = process(connfd, &clientaddr);
strncpy(buf, p, strlen(p) + 1);
close(connfd);
free(p);
return strlen(p);
} else if (FD_ISSET(stdin_fd, &set)) {
nread = read(l.ifd, &c, 1);
if (nread <= 0)
return l.len;
......
```
- 新增 do_web 函式
```cpp
static bool do_web(int argc, char *argv[])
{
if (!listenfd) {
listenfd = get_listenfd(argc, argv);
report(3, "Launching tiny web server");
} else
report(3, "Tiny web server has already been launched");
return true;
}
```
- 使用 curl 測試
```shell
curl http://localhost:9999/it/cat/3
curl http://localhost:9999/ih/dog/4
```
```shell
cmd> new
l = []
cmd> web
serve directory '/home/tommy/desktop/linux/lab0-c'
listen on port 9999, fd is 3
Launching tiny web server
cmd> accept request, fd is 4, pid is 14574
127.0.0.1:52928 200 - 'it cat 3' (text/plain)
l = [cat cat cat]
cmd> accept request, fd is 4, pid is 14574
127.0.0.1:52930 200 - 'ih dog 4' (text/plain)
l = [dog dog dog dog cat cat cat]
cmd>
```
## 運用 Valgrind 排除 `qtest` 實作的記憶體錯誤
- 使用 make valgrind 進行編譯時產生 memory leak 的訊息
```shell
==17406== 10 bytes in 1 blocks are still reachable in loss record 1 of 3
==17406== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==17406== by 0x4A5150E: strdup (strdup.c:42)
==17406== by 0x110E2A: linenoiseHistoryAdd (linenoise.c:1236)
==17406== by 0x1119BD: linenoiseHistoryLoad (linenoise.c:1325)
==17406== by 0x10CB4E: main (qtest.c:1113)
==17406==
==17406== 160 bytes in 1 blocks are still reachable in loss record 2 of 3
==17406== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==17406== by 0x110DEA: linenoiseHistoryAdd (linenoise.c:1224)
==17406== by 0x1119BD: linenoiseHistoryLoad (linenoise.c:1325)
==17406== by 0x10CB4E: main (qtest.c:1113)
==17406==
==17406== 193 bytes in 19 blocks are still reachable in loss record 3 of 3
==17406== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==17406== by 0x4A5150E: strdup (strdup.c:42)
==17406== by 0x110D9E: linenoiseHistoryAdd (linenoise.c:1236)
==17406== by 0x1119BD: linenoiseHistoryLoad (linenoise.c:1325)
==17406== by 0x10CB4E: main (qtest.c:1113)
==17406==
```
- 從訊息中可以看到在 linenoiseHistoryLoad() 之中的某個環節呼叫了 strdup 去動態配置記憶卻沒有被 free 掉。
```cpp
/* Add an heap allocated copy of the line in the history.
* If we reached the max length, remove the older line. */
linecopy = strdup(line);
if (!linecopy)
return 0;
if (history_len == history_max_len) {
free(history[0]);
memmove(history, history + 1, sizeof(char *) * (history_max_len - 1));
history_len--;
}
history[history_len] = linecopy;
history_len++;
```
- 觀察程式碼，history 這個 global pointer 會在
呼叫 freeHistory() 時被釋放記憶體。
```cpp
static void freeHistory(void)
{
if (history) {
int j;
for (j = 0; j < history_len; j++)
free(history[j]);
free(history);
}
}
```
- 繼續追蹤程式碼，發現 freeHistory() 是經由 linenoise() 所開啟的連鎖呼叫而被呼叫的。
過程如下：
linenoise() -> linenoiseRaw() -> enableRawMode() -> linenoiseAtExit() -> freeHistory()
- 觀察 run_console() 中的程式碼，發現 qtest 在沒有 input file 的時候的時候才會經由 linenoise() 讀取命令，並且此時會需要藉由 linenoiseHistoryLoad() 將使用者之前的歷史紀錄 load 進來。
```cpp
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);
}
```
- 然而，再觀察 qtest.c 的 main function ，會發現他在任何情況下都會呼叫 linenoiseHistoryLoad()，導致我們使用檔案輸入時，由於不呼叫 linenoise() 讀取命令，所以也不會呼叫到 freeHistory()，造成了 memory leak。
```cpp
/* Trigger call back function(auto completion) */
linenoiseSetCompletionCallback(completion);
linenoiseHistorySetMaxLen(HISTORY_LEN);
linenoiseHistoryLoad(HISTORY_FILE); /* Load the history at startup */
```
- 解決方案 : 在沒有輸入檔案時才呼叫 linenoiseHistoryLoad()
```cpp=
if(!infile_name)
linenoiseHistoryLoad(HISTORY_FILE); /* Load the history at startup */
```
- 再次執行 make valgrind 已經沒有了錯誤訊息
## 研讀論文〈Dude, is my code constant time?〉
論文中提出了工具 **dudect**，可以用來檢測一段程式是否以 constant time 執行。
雖然現在已經出現很多評估效能的工具，例如作者提到的 ctgrind, ctverif, Valgrind，但是這些工具往往需要針對不同的硬體去做 modeling，且 CPU 供應商往往對產品細節不願透漏太多，這導致建模變得困難。
於是論文提出了以 leakage detection 方式，針對兩組 input data 的執行時間做統計分析，觀察他們的 distribution 是否有顯著差異，因而避開了對硬體的 dependency。
論文中採用的 Welch’s t-test 是 t-test 的其中一種變形，其在針對兩個 variance 不同的 sample 時能有更好的 numeric stability
當 t-test 試圖否定『 兩個 timing distributions 相同 』的假設失敗時，代表無法證明平均值的差異，implies 執行時間為constant time。
### 可能的缺陷：
套用這種統計的方式可能需要很大量的測資才能夠反映出較真實的 distribution，測試上沒有直接測量時間的方法來得容易。
Sign in with Wallet
Connect another wallet