HackMD
2022q1 Homework1 (lab0)
contributed by < cymizer >
開發環境
$ uname -a
Linux notebook 5.8.0-55-generic #62~20.04.1-Ubuntu SMP Wed Jun 2 08:55:04 UTC 2021 x86_64 x86_64 x86_64 GNU/Linux
$ gcc -v
gcc version 9.3.0 (Ubuntu 9.3.0-17ubuntu1~20.04)
$ 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): 4
On-line CPU(s) list: 0-3
Thread(s) per core: 2
Core(s) per socket: 2
Socket(s): 1
NUMA node(s): 1
Vendor ID: GenuineIntel
CPU family: 6
Model: 69
Model name: Intel(R) Core(TM) i5-4210U CPU @ 1.70GHz
Stepping: 1
CPU MHz: 800.000
CPU max MHz: 2700.0000
CPU min MHz: 800.0000
BogoMIPS: 4788.69
Virtualization: VT-x
L1d cache: 64 KiB
L1i cache: 64 KiB
L2 cache: 512 KiB
L3 cache: 3 MiB
NUMA node0 CPU(s): 0-3
作業要求
- Implement queue.[ch]
- 在
qtest提供新的命令shuffle，允許藉由 Fisher–Yates shuffle 演算法，對佇列中所有節點進行洗牌 (shuffle) 操作 - 在
qtest提供新的命令web，提供 web 伺服器功能，注意: web 伺服器運作過程中，qtest 仍可接受其他命令- 可依據前述說明，嘗試整合 tiny-web-server
- 共筆涵蓋項目
- 修正執行 Address Sanitizer 時會發生的錯誤
- 運用 Valgrind 排除 qtest 實作的記憶體錯誤，並透過 Massif 視覺化 “simulation” 過程中的記憶體使用量，需要設計對應的實驗
- 解釋 select 系統呼叫在本程式的使用方式，並分析 console.c 的實作，說明其中運用 CS:APP RIO 套件 的原理和考量點。可對照參考 CS:APP 第 10 章重點提示 為避免「舉燭」，請比照 qtest 實作，撰寫獨立的終端機命令解譯器 (可建立新的 GitHub repository)Image Not Showing Possible Reasons
- The image file may be corrupted
- The server hosting the image is unavailable
- The image path is incorrect
- The image format is not supported
- 研讀論文 Dude, is my code constant time?，解釋本程式的 “simulation” 模式是如何透過以實驗而非理論分析，達到驗證時間複雜度，需要解釋 Student’s t-distribution 及程式實作的原理。注意：現有實作存在若干致命缺陷，請討論並提出解決方案;
- 2021q1, 說明 antirez/linenoise 的運作原理，注意到 termios 的運用
- 指出現有程式的缺陷 (提示: 和 RIO 套件 有關)，嘗試強化並提交 pull request
透過 linux style API 實作佇列操作
閱讀及思考 list.h 裡面的 API 相關用法
- TODO
- container_of()
q_new
- 此函式的目標為建立一個新的 queue
- 首先，去 malloc 一個 head node，如果在
分配記憶體空間失敗，則會回傳NULL. - 初始化 head，將 prev, next 都指向自己. 發現到可以使用
INIT_LIST_HEAD(head)來做簡化.
- 首先，去 malloc 一個 head node，如果在
struct list_head *q_new()
{
struct list_head *head = malloc(sizeof(struct list_head));
if (!head)
return NULL;
+ INIT_LIST_HEAD(head);
- head->next = head;
- head->prev = head;
return head;
}
q_free
- 去把 queue 所用到的空間的做釋放
- 先檢查所傳入的 list_head node 是否為
NULL - 透過
list_for_each_safe()來尋訪 list 之 node 並從 list 中移除，在閱讀list.h裡面相關的註解，可以知道用此 api 去保證在尋訪 list node 並移除時的安全，因為他多使用了一個list_head *safe來保存下一個 node. - 透過
container_of來得到 entry address，透過element_t pointer釋放其資源.
- 先檢查所傳入的 list_head node 是否為
void q_free(struct list_head *l)
{
if (!l)
return;
struct list_head *head = l;
struct list_head *node, *safe;
list_for_each_safe (node, safe, head) {
list_del(node);
element_t *ele = container_of(node, element_t, list);
q_release_element(ele);
}
free(head);
}
q_insert_head / q_insert_tail
- 要將 node 加入 list 的 head or tail
- q_insert_head
- 檢查傳入的 node 是否為 NULL, 避免 access invalid address
- 接著 allocate memory 給
element *ele，接著檢查是否 allocate 成功 - 用 strdup() 將複製 string 給
ele->value，再做完之後檢查是否有 allocate 成功。 - 最後用
list_add()將 node 加入 list 中
- q_insert_tail
- 將 line 17 改成
list_add_tail()即可
- 將 line 17 改成
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;
}
struct list_head *ele_list = &ele->list;
ele->value = strdup(s);
if (!ele->value) {
free(ele);
return false;
}
list_add(ele_list, head);
return true;
}
q_remove_head / q_remove_tail
- 將 node 從 head or tail "移除"
- q_remove_head
- 檢查 list head 為 NULL or list 裡面是 empty，是的話則回傳 NULL
- 利用 container_of 得到
head->next本身element_t的 address - 將
head->next從 list 的 head 移除 - 檢查 sp 是否為 NULL, 否的話則會進入。 將 element->val 複製到 sp buff 上。
- 需要注意 len 是否大於 bufsize，以及需要再最後填上
\0當做
- 需要注意 len 是否大於 bufsize，以及需要再最後填上
- q_remove_tail
- 將 line 5 改為
*prev = head->prev;,和 line 6,7 改動為next=>prev即可
- 將 line 5 改為
element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
if (!head || list_empty(head))
return NULL;
struct list_head *next = head->next;
element_t *ele = container_of(next, element_t, list);
list_del(next);
// if sp is non-NULL (handling)
if (sp) {
int len;
for (len = 0; *(ele->value + len); len++)
;
if (len > bufsize) {
strncpy(sp, ele->value, bufsize - 1);
sp[bufsize - 1] = '\0';
} else {
strncpy(sp, ele->value, len);
sp[len] = '\0';
}
}
return ele;
}
q_size
- 計算 list 中 node 的個數
- 檢查是否為 head 是否為 null，是的話則回傳 0
- 利用
list_for_each()尋訪 list ，最後回傳 list 長度
int q_size(struct list_head *head)
{
if (!head)
return 0;
int len = 0;
struct list_head *node;
list_for_each (node, head)
len++;
return len;
}
q_delete_mid
- 刪除 list 中間的節點
- 檢查 head 是否為 null，是的話則回傳 false; 如果 list 在 empty 則回傳 false
- 在寫筆記時發現沒有做
list_empty()的檢查。 如果沒有做檢查的話，會造成後面程式執行的 invalid memory access。 - commit 2694889
- 在寫筆記時發現沒有做
- 透過 slow & fast 的方式來找到 mid node
- 從 list 中移除 slow node 並釋放其資源後，回傳 ture
bool q_delete_mid(struct list_head *head)
{
if (!head || list_empty(head))
return false;
struct list_head *slow, *fast;
for (slow = head->next, fast = head->next->next;
fast != head && fast->next != head;
slow = slow->next, fast = fast->next->next)
;
element_t *ele_mid = container_of(slow, element_t, list);
list_del(slow);
q_release_element(ele_mid);
return true;
}
q_delete_dup
- 移除 value 重複的 element
- 檢查 head 是否為 null，是的話則回傳 false; 如果 list 在 empty 則回傳 false
- 透過
list_for_each()尋訪 list node - 因為可能會移除節點，所以除了
next之外，還特別使用safe來保存下下個 node - 如果比較結果相同
strcmp = 0，則將該 node 移除
bool q_delete_dup(struct list_head *head)
{
if (!head || list_empty(head))
return false;
struct list_head *node;
list_for_each (node, head) {
struct list_head *next = node->next;
element_t *ele_node = container_of(node, element_t, list);
for (struct list_head *safe = next->next; next != head;
next = safe, safe = next->next) {
element_t *ele_next = container_of(next, element_t, list);
if (!strcmp(ele_node->value, ele_next->value)) {
list_del(next);
q_release_element(ele_next);
} else
break;
}
}
return true;
}
q_swap
- 參考 https://leetcode.com/problems/swap-nodes-in-pairs/ 之敘述，交換兩個 node 位置而非其值
- 一樣採用
list_for_each()尋訪 - 將兩個相鄰 node 互相交換，要特別注意的是如果是 "奇數" 個 node 要特別處理，避免和 head node 交換造成結果錯誤。
void q_swap(struct list_head *head)
{
if (!head || list_empty(head) || list_is_singular(head))
return;
struct list_head *node;
list_for_each (node, head) {
if (node->next == head)
break;
struct list_head *next = node->next;
node->next = next->next;
next->next->prev = node;
next->next = node;
next->prev = node->prev;
node->prev->next = next;
node->prev = next;
}
}
q_reverse
- 透過
list_for_each_safe()走訪並將其 node 移到 head 的位置
void q_reverse(struct list_head *head)
{
if (!head || list_empty(head)) {
return;
}
struct list_head *node, *safe;
list_for_each_safe (node, safe, head) {
list_move(node, head);
}
}
q_sort
- 使用 merge sort ，並採用遞迴的方式來完成，參考 Linked List Sort 使用 list.h 來做改寫
- 共分為兩階段 ( divide and conquer )
- Split
- 用 slow & fast 的方法將 list 切半。並將其各自從 head list 加到 left, right list 中，並透過遞迴的方式將其分割到只剩一個 node 在透過 Merge 來做合併。
- Merge
- 尋訪 left 和 right list，兩兩 node 互相比較把值比較小的從 list 中移除加到 head list tail 直到其中一個 list 為空沒有 node。並使用 list_splice_tail() 將還不為空的 list 加到 head list tail。
- 在寫 Merge 時, 在要去寫
移除的節點並加入 head時會發生錯誤。如果使用原本的 code，會讀取到 head list 中的下個 node ，而非原本的所預期的 l or r 的 list node 中所指向的下個 node。將 line 1, 9, 10 移除，改成 line 10 才會符合預期情況。
- struct list_head *l = left.next, *r = right.next; while (!list_empty(&left) && !list_empty(&right)) { + struct list_head *l = left.next, *r = right.next; element_t *ele_l = container_of(l, element_t, list); element_t *ele_r = container_of(r, element_t, list); if (strcmp(ele_l->value, ele_r->value) <= 0) { list_del(l); list_add_tail(l, head); - l = l->next; } else { list_del(r); list_add_tail(r, head); - r = r->next; } }
- Split
- 完整 q_sort
void q_sort(struct list_head *head)
{
if (!head || list_empty(head) || list_is_singular(head))
return;
// split
struct list_head *slow, *fast;
for (slow = head->next, fast = head->next->next;
fast != head && fast->next != head;
slow = slow->next, fast = fast->next->next)
;
LIST_HEAD(left);
LIST_HEAD(right);
list_cut_position(&left, head, slow);
// check node is odd or even
fast = fast != head ? fast : fast->prev;
list_cut_position(&right, head, fast);
q_sort(&left);
q_sort(&right);
// Merge
while (!list_empty(&left) && !list_empty(&right)) {
struct list_head *l = left.next, *r = right.next;
element_t *ele_l = container_of(l, element_t, list);
element_t *ele_r = container_of(r, element_t, list);
// strcmp 1: str1 > str2, 0: equal, -1: str1 < str2
if (strcmp(ele_l->value, ele_r->value) <= 0) {
list_del(l);
list_add_tail(l, head);
} else {
list_del(r);
list_add_tail(r, head);
}
}
if (!list_empty(&left))
list_splice_tail(&left, head);
if (!list_empty(&right))
list_splice_tail(&right, head);
}
以 Valgrind 分析記憶體問題
執行程式：
$make valgrind
會執行 Makefile 裡面valgrind 的部份
valgrind: valgrind_existence
# Explicitly disable sanitizer(s)
$(MAKE) clean SANITIZER=0 qtest
$(eval patched_file := $(shell mktemp /tmp/qtest.XXXXXX))
cp qtest $(patched_file)
chmod u+x $(patched_file)
sed -i "s/alarm/isnan/g" $(patched_file)
scripts/driver.py -p $(patched_file) --valgrind $(TCASE)
@echo
@echo "Test with specific case by running command:"
@echo "scripts/driver.py -p $(patched_file) --valgrind -t <tid>"
會產生以下相關錯誤訊息
# Explicitly disable sanitizer(s)
make clean SANITIZER=0 qtest
...
cp qtest /tmp/qtest.pK4SCR
chmod u+x /tmp/qtest.pK4SCR
sed -i "s/alarm/isnan/g" /tmp/qtest.pK4SCR
scripts/driver.py -p /tmp/qtest.pK4SCR --valgrind
--- Trace Points
+++ TESTING trace trace-01-ops:
# Test of insert_head and remove_head
==85920== 6 bytes in 1 blocks are still reachable in loss record 1 of 3
==85920== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==85920== by 0x4A4E50E: strdup (strdup.c:42)
==85920== by 0x110B86: linenoiseHistoryAdd (linenoise.c:1236)
==85920== by 0x111719: linenoiseHistoryLoad (linenoise.c:1325)
==85920== by 0x10C77C: main (qtest.c:975)
==85920==
==85920== 126 bytes in 19 blocks are still reachable in loss record 2 of 3
==85920== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==85920== by 0x4A4E50E: strdup (strdup.c:42)
==85920== by 0x110AFA: linenoiseHistoryAdd (linenoise.c:1236)
==85920== by 0x111719: linenoiseHistoryLoad (linenoise.c:1325)
==85920== by 0x10C77C: main (qtest.c:975)
==85920==
==85920== 160 bytes in 1 blocks are still reachable in loss record 3 of 3
==85920== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==85920== by 0x110B46: linenoiseHistoryAdd (linenoise.c:1224)
==85920== by 0x111719: linenoiseHistoryLoad (linenoise.c:1325)
==85920== by 0x10C77C: main (qtest.c:975)
==85920==
--- trace-01-ops 5/5
...
==86183== 40 bytes in 1 blocks are still reachable in loss record 30 of 32
==86183== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==86183== by 0x10CE21: malloc_or_fail (report.c:189)
==86183== by 0x10D925: add_param (console.c:110)
==86183== by 0x10C75A: console_init (qtest.c:826)
==86183== by 0x10C75A: main (qtest.c:969)
...
Test with specific case by running command:
scripts/driver.py -p /tmp/qtest.pK4SCR --valgrind -t <tid>
錯誤處理：
錯誤訊息告訴我們記憶體 still reachable ，代表程式結束時仍有記憶體未釋放。
- 可以參考 valgrind manual，搜尋 still reachable
依照錯誤訊息查看相關程式碼
- 問題一 ：linenoiseHistoryLoad()
- qtest.c
linenoiseHistorySetMaxLen(HISTORY_LEN);
linenoiseHistoryLoad(HISTORY_FILE); /* Load the history at startup */
- linenoise.c
int linenoiseHistoryLoad(const char *filename)
{
FILE *fp = fopen(filename, "r");
char buf[LINENOISE_MAX_LINE];
if (fp == NULL)
return -1;
while (fgets(buf, LINENOISE_MAX_LINE, fp) != NULL) {
char *p;
p = strchr(buf, '\r');
if (!p)
p = strchr(buf, '\n');
if (p)
*p = '\0';
linenoiseHistoryAdd(buf);
}
fclose(fp);
return 0;
}
int linenoiseHistoryAdd(const char *line)
{
char *linecopy;
if (history_max_len == 0)
return 0;
/* Initialization on first call. */
if (history == NULL) {
history = malloc(sizeof(char *) * history_max_len);
if (history == NULL)
return 0;
memset(history, 0, (sizeof(char *) * history_max_len));
}
/* Don't add duplicated lines. */
if (history_len && !strcmp(history[history_len - 1], line))
return 0;
/* 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++;
return 1;
}
它做的事情是將 HISTORY_FILE = .cmd_history 的資料載入到在 linenoise.c:132 的 static char **history。
註： HISTORY_FILE 可以用
grep -r HISTORY_FILE找到在console.c定義
可以發現無相關釋放記憶體的程式碼在其中。所以嘗試在程式碼中搜尋 free 關鍵字可以找到 freeHistory 。以 freeHistory 為關鍵字搜尋可以找到在 linenoiseAtExit 被使用。
呼叫關係為 run_console() => linenosie() => linenoiseRaw() => enableRawMode() => atexit(linenoiseAtExit()) => freeHistory()，其中 atexit() 是去註冊在程序離開結束被調用指定的函數。
所以將 main.c:975 => 移到 console.c:651 更為合理，在有 infile 的時候才會去載入HISTORY_FILE
- qtest.c
linenoiseHistorySetMaxLen(HISTORY_LEN);
- linenoiseHistoryLoad(HISTORY_FILE); /* Load the history at startup */
- console.c
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. */
+ linenoiseHistoryLoad(HISTORY_FILE); /* Load the history at startup */
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;
}
- 問題2. 經由
console_init()init 的 cmd_list 沒有被 release 掉
-
因為在使用
make valgrind的時候會造成運算速度下降導致 不是constant time，近而造成ok這個 flag 變成false，因為使用&&連帶影響到不會執行finish_cmd()。所以將其順序調換就可以進行finish_cmd()的動作。 -
qtest.c
bool ok = true;
ok = ok && run_console(infile_name);
+ ok = finish_cmd() && ok;
- ok = finish_cmd() && ok;
