# 2020q1 Homework1 (lab0)
contributed by < `eric5800602` >
## 開發環境
```shell
$ uname -a
Linux os2018 4.15.0-34-generic #37-Ubuntu SMP Mon Aug 27 15:21:48 UTC 2018 x86_64 x86_64 x86_64 GNU/Linux
$ gcc --version
gcc (Ubuntu 7.3.0-16ubuntu3) 7.3.0
$ lscpu
Architecture: x86_64
CPU op-mode(s): 32-bit, 64-bit
Byte Order: Little Endian
CPU(s): 1
On-line CPU(s) list: 0
Thread(s) per core: 1
Core(s) per socket: 1
Socket(s): 1
NUMA node(s): 1
Vendor ID: GenuineIntel
CPU family: 6
Model: 158
Model name: Intel(R) Core(TM) i5-7300HQ CPU @ 2.50GHz
Stepping: 9
CPU MHz: 2496.004
BogoMIPS: 4992.00
Hypervisor vendor: KVM
Virtualization type: full
L1d cache: 32K
L1i cache: 32K
L2 cache: 256K
L3 cache: 6144K
NUMA node0 CPU(s): 0
Flags: fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov pat pse36 clflush mmx fxsr sse sse2 ht syscall nx rdtscp lm constant_tsc rep_good nopl xtopology nonstop_tsc cpuid pni pclmulqdq monitor ssse3 cx16 pcid sse4_1 sse4_2 x2apic movbe popcnt aes xsave avx rdrand hypervisor lahf_lm abm 3dnowprefetch invpcid_single pti fsgsbase avx2 invpcid rdseed clflushopt flush_l1d
```
## 作業要求
在 `queue.[c/h]` 中完成以下實作
* `q_new`: 建立新的空 `queue`
* `q_free`: 釋放 `queue` 所佔用的記憶體
* `q_insert_head`: 在 `queue` 開頭加入給定的新元素，並以LIFO準則
* `q_insert_tail`: 在 `queue` 尾部加入給定的新元素，並以FIFO準則
* `q_remove_head`: 移除在 `queue` 開頭的元素。
* `q_size`: 計算 `queue` 中的元素數量。
* `q_reverse`: 將 `queue` 反轉，此函式不能配置或釋放任何記憶體，也就是說只能重新鏈結已經存在的元素;
* `q_sort`: 以 [natural sort](https://github.com/sourcefrog/natsort)來排序鏈結的元素
## 實作
### `queue_t` 資料結構
為了讓 `q_insert_tail` 與 `q_size` 的實作能在時間複雜度為$O(1)$的條件下完成，所以根據 [linux2020-lab0#牛刀小試](https://hackmd.io/@sysprog/linux2020-lab0#%E7%89%9B%E5%88%80%E5%B0%8F%E8%A9%A6) 所述，在 `queue_t` 的結構中增加：
- `tail` 記錄 `queue` 的尾部元素的記憶體位置
- `size` 儲存 `queue` 的總元素個數
```cpp
typedef struct {
list_ele_t *head; /* Linked list of elements */
list_ele_t *tail; /* Recording the tail of queue can make q_insert_tail
operate in O(1) time*/
int size;
} queue_t;
```
### q_new
* 因`malloc`可能會回傳 `NULL`，為提高程式碼的穩固程度，所以必須進行處理。
* 根據[ISO/IEC 9899 (a.k.a C99 Standard)](http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1124.pdf)中7.20.3.3所述，`malloc` 後記憶體區塊的 value is indeterminate，所以加入 `memset` 來初始化記憶體區塊
```clike=
queue_t *q_new()
{
queue_t *q = malloc(sizeof(queue_t));
/* Return NULL if malloc return NULL. */
if (!q) {
return NULL;
}
memset(q, 0, sizeof(queue_t));
q->head = NULL;
q->tail = NULL;
/* Initial the size of queue to zero. */
q->size = 0;
return q;
}
```
### q_free
* 因傳入的 `queue` 有可能為 `NULL`，為提高程式碼的穩固程度，所以需要加入判斷
* 為避免出現 memory leak 之情況，須確保每個元素都被釋放掉
* 利用 `tmp` 儲存當前 `head` 下一個元素的位置，並釋放 `head` 元素，再讓 `queue` 的 `head` 指到下一個元素(也就是 `tmp`)，直到下一個元素位置為 `NULL`
* 最後釋放 `queue` 本身的記憶體
```clike=
void q_free(queue_t *q)
{
/* Free queue structure */
/* Check whether q is NULL. */
if (!q) {
return;
}
/* Free all elements in queue. */
while (q->head) {
list_ele_t *tmp = q->head->next;
free(q->head->value);
free(q->head);
q->head = tmp;
}
free(q);
return;
}
```
### q_insert_head
* 判斷 input `queue` 是否為空，因需插入新的元素，所以也須判斷 `malloc` 之回傳值
* 新元素的 `value` 申請空間為本身字數加上最後的`'\0'` 也就是 `(strlen(s) + 1) * sizeof(char)`
* 新元素的 `value` 在 `malloc` 後也要記得判斷回傳值
* 使用 `memset` 確保記憶體區塊初始化
* 使用 `strncpy` 確保不會發生緩衝區溢位之問題
* 讓新創建元素的 `next` 指向當前 `queue` 中的 `head` ，再將 `queue` 中的 `head` 指向新創建的元素
```clike=
bool q_insert_head(queue_t *q, char *s)
{
/* Check whether q is NULL. */
if (!q) {
return false;
}
list_ele_t *newh;
newh = malloc(sizeof(list_ele_t));
/* Return NULL if malloc return NULL. */
if (!newh) {
return false;
}
/* Allocate space for the string. */
newh->value = malloc((strlen(s) + 1) * sizeof(char));
/* Return NULL if malloc return NULL. */
if (!newh->value) {
free(newh);
return false;
}
/* Reset the space of string malloc just recently*/
memset(newh->value, 0, sizeof(char) * (strlen(s) + 1));
strncpy(newh->value, s, strlen(s));
newh->next = q->head;
q->head = newh;
/* If the tail in queue is NULL, assign newh to it. */
if (!q->tail) {
q->tail = newh;
}
/* The size of queue plus one. */
q->size++;
return true;
}
```
### q_insert_tail
* 為在時間複雜度為$O(1)$的條件下完成，利用 `queue` 中本身已儲存之 `tail` 的記憶體位置以達成
* 基本之考慮點與 `q_insert_head` 同
* 如果在 `q_insert_tail` 之前 `queue` 中無元素，需額外更新 `queue` 中 `head` 之值
```clike=
bool q_insert_tail(queue_t *q, char *s)
{
/* Check whether q is NULL. */
if (!q) {
return false;
}
list_ele_t *newt;
newt = malloc(sizeof(list_ele_t));
/* Return NULL if malloc return NULL. */
if (!newt) {
return false;
}
/* Allocate space for the string. */
newt->value = malloc(sizeof(char) * (strlen(s) + 1));
/* Return NULL if malloc return NULL. */
if (!newt->value) {
free(newt);
return false;
}
/* Reset the space of string malloc just recently*/
memset(newt->value, 0, sizeof(char) * (strlen(s) + 1));
strncpy(newt->value, s, strlen(s));
newt->next = NULL;
if (q->tail) {
q->tail->next = newt;
}
q->tail = newt;
/* If the head in queue is NULL, assign newt to it. */
if (!q->head) {
q->head = newt;
}
/* The size of queue plus one. */
q->size++;
return true;
}
```
### q_remove_head
* 先確認 `queue` 是否為空，以及其中是否有元素可以被移除
* 初始化 `sp` 中的內容，以免舊資料未清空造成錯誤，並全部指定為 `'\0'`
* 同樣使用 `strncpy` 確保無緩衝區溢位問題，只更新到 `bufsize-1` 是因為確保字串結尾為原本初始化之 `'\0'`
* 紀錄原始的 `head` 位置，並更新 `queue` 中 `head` 的位置至下一個
* 釋放原始 `head` 的記憶體空間
```clike=
bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
/* Return false if queue is NULL or empty. */
if (!q || !q->size) {
return false;
}
/* If sp is non-NULL and an element is removed, copy the removed string to sp. */
if (sp != NULL && q->head->value) {
memset(sp, '\0', bufsize);
strncpy(sp, q->head->value, bufsize - 1);
}
list_ele_t *tmp = q->head;
q->head = q->head->next;
/* Free the spaces used by the list element and the string. */
free(tmp->value);
free(tmp);
q->size--;
return true;
}
```
### q_reverse
* 原本沒看到不能新增釋放記憶體，使用類似 [Reversing a Queue](https://www.geeksforgeeks.org/reversing-a-queue) 的方法，結果在 `malloc` 時一直出現 `FATAL ERROR: Calls to malloc disallowed` ，最後在看 comment 時才看到不能新增及釋放記憶體，現已修正
* 在 `queue` 為 `NULL` 、 `queue` 中無元素 、 `queue` 中只有一個元素之狀況無須 reverse
* 先把 `tail` 改為 `head` ，並利用 `back` 及 `front` 兩 pointer 紀錄下一個以及前一個的元素
* 記得要將 `q->tail->next` 清除為 `NULL`，不然會造成環狀結構
* 利用 while loop 將當前元素的指標方向顛倒，直到 `q->head->next` 為 `NULL` 也就是到原本 `queue` 的尾巴
* 曾試過只利用一個 `tmp` 來暫時存放前一個元素位置但發現還有原本的 `q->head->next` 需要存，不然一旦將 `q->head->next` 改變，就再也找不到它了，所以才有第 25 行錯誤寫法的 comment
```clike=
void q_reverse(queue_t *q)
{
/* Return if queue is NULL or empty. */
if (!q || q->size == 0 || q->size == 1) {
return;
}
/* Declare back & front pointer for reversing. */
list_ele_t *back, *front;
/* Reverse elements in queue. */
/* Change the tail of queue and record previous pointer in back. */
q->tail = q->head;
back = q->head;
/* Move the head pointer to the next and record next pointer in fornt.*/
q->head = q->head->next;
front = q->head->next;
/* Clear the next of tail to NULL*/
q->tail->next = NULL;
while (front) {
/* Change the next pointer of current head to previous. */
q->head->next = back;
/* Repeat recording back & front pointer and
* move the head of q to the next. */
back = q->head;
/* Wrong writage: q->head = q->head->next.
* Because q->head->next had been changed before.*/
q->head = front;
front = q->head->next;
}
q->head->next = back;
}
```
### q_size
* 因為在 `queue.h` 中 queue_t 有加入 size 紀錄 queue 的大小，可以直接作為回傳值，因此時間複雜度是$O(1)$
```clike=
int q_size(queue_t *q)
{
if (q && q->size) {
return q->size;
}
return 0;
}
```
### q_sort
* 根據 [LinkedListSort](https://npes87184.github.io/2015-09-12-linkedListSort/) 中的 Merge Sort 製作 q_sort，用以達成時間複雜度為 $O(nlogn)$ 並通過自動測試程式
* 因不能新增或釋放記憶體，所以也不能使用 Pseudo Node 實作
* 在 2/17 前實作，所以也沒有用到 [natural sort](https://github.com/sourcefrog/natsort)
```clike=
list_ele_t *mergeSortList(list_ele_t *head)
{
// merge sort
if (!head || !head->next)
return head;
list_ele_t *fast = head->next;
list_ele_t *slow = head;
// split list
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
}
fast = slow->next;
slow->next = NULL;
// sort each list
list_ele_t *l1 = mergeSortList(head);
list_ele_t *l2 = mergeSortList(fast);
// merge sorted l1 and sorted l2
return merge(l1, l2);
}
list_ele_t *merge(list_ele_t *l1, list_ele_t *l2)
{
/* Using merge with pseudo node will cause following error
* FATAL ERROR: Calls to malloc disallowed
* FATAL Error. Exiting */
/* Declare pointer q as result for returning. */
list_ele_t *temp = NULL, *q = NULL;
/* Initial temp and q pointers for merge starting. */
if (strnatcmp(l1->value, l2->value) < 0) {
q = l1;
temp = q;
l1 = l1->next;
} else {
q = l2;
temp = q;
l2 = l2->next;
}
/* Merge two list(l1 & l2) until the end of one. */
while (l1 && l2) {
if (strnatcmp(l1->value, l2->value) < 0) {
temp->next = l1;
temp = temp->next;
l1 = l1->next;
} else {
temp->next = l2;
temp = temp->next;
l2 = l2->next;
}
}
/* Another list may not be over yet. */
if (l1)
temp->next = l1;
if (l2)
temp->next = l2;
return q;
}
```
* 以上之程式碼會造成 `Program received signal SIGSEGV, Segmentation fault.` 之錯誤，並在 valgrind 中出現`ERROR: Time limit exceeded. Either you are in an infinite loop, or your code is too inefficient` 及 `Address 0x0 is not stack'd, malloc'd or (recently) free'd`
* 利用 GDB 測試程式碼在 gdb bt 發現以下情況，一直不斷地呼叫merge，查詢及看到社團中有人有同樣的情況，說明是 stack overflow 造成的
```jsx=
#3335 0x0000555555558c60 in merge (l1=l1@entry=0x555560e7ece0, l2=0x55555f1080e0)
at queue.c:224
#3336 0x0000555555558c60 in merge (l1=l1@entry=0x555560e7ece0, l2=0x55555f108060)
at queue.c:224
#3337 0x0000555555558c60 in merge (l1=l1@entry=0x555560e7ece0, l2=0x55555f107fe0)
at queue.c:224
#3338 0x0000555555558c60 in merge (l1=l1@entry=0x555560e7ece0, l2=0x55555f107f60)
at queue.c:224
#3339 0x0000555555558c60 in merge (l1=l1@entry=0x555560e7ece0, l2=0x55555f107ee0)
at queue.c:224
#3340 0x0000555555558c60 in merge (l1=l1@entry=0x555560e7ece0, l2=0x55555f107e60)
at queue.c:224
#3341 0x0000555555558c60 in merge (l1=l1@entry=0x555560e7ece0, l2=0x55555f107de0)
at queue.c:224
#3342 0x0000555555558c60 in merge (l1=l1@entry=0x555560e7ece0, l2=0x55555f107d60)
at queue.c:224
#3343 0x0000555555558c60 in merge (l1=l1@entry=0x555560e7ece0, l2=0x55555f107ce0)
at queue.c:224
#3344 0x0000555555558c60 in merge (l1=l1@entry=0x555560e7ece0, l2=0x55555f107c60)
at queue.c:224
#3345 0x0000555555558c60 in merge (l1=l1@entry=0x555560e7ece0, l2=0x55555f107be0)
at queue.c:224
#3346 0x0000555555558c60 in merge (l1=l1@entry=0x555560e7ece0, l2=0x55555f107b60)
```
* 為證明此情況為 stack overflow 所造成的另外寫一個程式並同樣利用 GDB 觀察
* 程式碼：
```clike=
#include <stdio.h>
void foo()
{
int c = 1;
foo();
}
int main()
{
foo();
}
```
* gdb bt 後也發生同樣的情況，在 valgrind 中也清楚地表示發生 `Stack overflow in thread #1: can't grow stack to 0x1ffe801000` 之情況
```jsx=
#5428 0x0000555555554613 in foo ()
#5429 0x0000555555554613 in foo ()
#5430 0x0000555555554613 in foo ()
#5431 0x0000555555554613 in foo ()
#5432 0x0000555555554613 in foo ()
#5433 0x0000555555554613 in foo ()
#5434 0x0000555555554613 in foo ()
#5435 0x0000555555554613 in foo ()
#5436 0x0000555555554613 in foo ()
#5437 0x0000555555554613 in foo ()
#5438 0x0000555555554613 in foo ()
#5439 0x0000555555554613 in foo ()
#5440 0x0000555555554613 in foo ()
#5441 0x0000555555554613 in foo ()
#5442 0x0000555555554613 in foo ()
#5443 0x0000555555554613 in foo ()
#5444 0x0000555555554613 in foo ()
#5445 0x0000555555554613 in foo ()
#5446 0x0000555555554613 in foo ()
#5447 0x0000555555554613 in foo ()
#5448 0x0000555555554613 in foo ()
#5449 0x0000555555554613 in foo ()
#5450 0x0000555555554613 in foo ()
```
* 為改善上述錯誤情況，將 merge sort 從遞迴形式改寫為迭代的方式，並改用 `natsort` 中的 `strnatcmp` 函式做比較
* 將 queue sort 問題 divide and conquer，最後 return 結果之 `queue->head`
```clike=
list_ele_t *mergeSortList(list_ele_t *head)
{
// merge sort
if (!head || !head->next)
return head;
list_ele_t *fast = head->next;
list_ele_t *slow = head;
// split list
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
}
fast = slow->next;
slow->next = NULL;
// sort each list
list_ele_t *l1 = mergeSortList(head);
list_ele_t *l2 = mergeSortList(fast);
// merge sorted l1 and sorted l2
return merge(l1, l2);
}
list_ele_t *merge(list_ele_t *l1, list_ele_t *l2)
{
/* Using merge with pseudo node will cause following error
* FATAL ERROR: Calls to malloc disallowed
* FATAL Error. Exiting
*/
/* Declare pointer q as result for returning. */
list_ele_t *temp = NULL, *q = NULL;
/* Initial temp and q pointers for merge starting. */
if (strnatcmp(l1->value, l2->value) < 0) {
q = l1;
temp = q;
l1 = l1->next;
} else {
q = l2;
temp = q;
l2 = l2->next;
}
/* Merge two list(l1 & l2) until the end of one. */
while (l1 && l2) {
if (strnatcmp(l1->value, l2->value) < 0) {
temp->next = l1;
temp = temp->next;
l1 = l1->next;
} else {
temp->next = l2;
temp = temp->next;
l2 = l2->next;
}
}
/* Another list may not be over yet. */
if (l1)
temp->next = l1;
if (l2)
temp->next = l2;
return q;
}
```
* 利用 `q_sort` 呼叫 `mergeSortList`
* 呼叫完成後須變更 `q->tail` 中的位置，避免 `sort` 後呼叫 `q_insert_tail` 造成錯誤
```clike=
void q_sort(queue_t *q)
{
// merge sort
if (!q || q->size == 1 || q->size == 0) {
return;
}
q->head = mergeSortList(q->head);
/* Check the tail of queue. */
list_ele_t *tail = q->head;
while (tail->next) {
tail = tail->next;
}
q->tail = tail;
}
```
* 根據 natsort 原專案內的 test 寫出類似的 trace file
* 例如：
```clike=
new
ih 1.2-15
ih 0.95.6-1
ih 1.2-5
ih 8.1.2-6
ih 0.10-4
ih 990522-1
ih 3.1.1-0
ih 3.22-7
.
.
.
ih 2.1-11
ih 1.0-13
ih 0.9.4-4
sort
free
quit
```
* 但利用 nasort 卻會出現 `ERROR: Not sorted in ascending order`
* 我認為這與自動測試程式的測試方式有關係，於是去找了 `qtest` 中測試 `q_sort` 的部分
```clike=
if (q) {
for (list_ele_t *e = q->head; e && --cnt; e = e->next) {
/* Ensure each element in ascending order */
/* FIXME: add an option to specify sorting order */
if (strcasecmp(e->value, e->next->value) > 0) {
report(1, "ERROR: Not sorted in ascending order");
ok = false;
break;
}
}
}
```
* 其中檢查比較的函式是利用 strcasecmp 與 natsort 不同
* 在下述範例中，可看出在某些情況時兩函式之相異結果
```clike=
new
ih pic02000
ih pic05
ih pic2
ih pic120
ih pic121
ih pic01
ih pic02
ih pic02a
ih pic3
ih pic4
ih pic100
ih pic100a
sort
free
quit
```
* strcasecmp 之排序結果會是：
`pic01 pic02 pic02000 pic02a pic05 pic100 pic100a pic120 pic121 pic2 pic3..`
* strnatcmp 之排序結果會是：
`pic01 pic02 pic02a pic02000 pic05 pic2 pic3 pic4 pic100 pic100a pic120..`
## Valgrind 的運用
* 使用 `make valgrind`
```clike=
scripts/driver.py -p /tmp/qtest.VCatNi --valgrind
--- Trace Points
+++ TESTING trace trace-01-ops:
# Test of insert_head and remove_head
--- trace-01-ops 6/6
+++ TESTING trace trace-02-ops:
# Test of insert_head, insert_tail, and remove_head
--- trace-02-ops 6/6
+++ TESTING trace trace-03-ops:
# Test of insert_head, insert_tail, reverse, and remove_head
--- trace-03-ops 6/6
+++ TESTING trace trace-04-ops:
# Test of insert_head, insert_tail, size, and sort
--- trace-04-ops 6/6
+++ TESTING trace trace-05-ops:
# Test of insert_head, insert_tail, remove_head, reverse, size, and sort
--- trace-05-ops 5/5
+++ TESTING trace trace-06-string:
# Test of truncated strings
--- trace-06-string 6/6
+++ TESTING trace trace-07-robust:
# Test operations on NULL queue
--- trace-07-robust 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-malloc:
# Test of malloc failure on new
--- trace-10-malloc 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-perf:
# Test performance of insert_tail
--- trace-13-perf 6/6
+++ TESTING trace trace-14-perf:
# Test performance of size
--- trace-14-perf 6/6
+++ TESTING trace trace-15-perf:
# Test performance of insert_tail, size, reverse, and sort
--- trace-15-perf 6/6
+++ TESTING trace trace-16-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-16-perf 6/6
+++ TESTING trace trace-17-complexity:
# Test if q_insert_tail and q_size is constant time complexity
Probably constant time
Probably constant time
--- trace-17-complexity 5/5
--- TOTAL 100/100
```
* **2/22 make valgrind 時出現重大錯誤(2/23 解決)**
* 今天在 fetch upstream 後在嘗試 make valgrind 時，出現 `Call of 'valgrind /tmp/qtest.lgvfhA -v 1 -f ./traces/trace-01-ops.cmd' failed: [Errno 2] No such file or directory` 類似錯誤，檢查發現全部測試檔案都還在 traces 目錄中沒有錯
:::warning
“directory” 一詞的翻譯是「目錄」，不要跟 folder (檔案夾) 搞混了，後者是 Microsoft Windows 提出的用語。“directory” 這詞彙已行之有年，我們會說 UNIX directory，而非 folder。
:notes: jserv
:::
> [name=SymbolWu]瞭解，感謝提供觀念釐清
* 而我利用舊的 `driver.py` 進行 `make valgrind` 時，就回復正常，研判可能是 `driver.py` 的問題
* 在此附上正常執行與有錯誤的 `dirver.py`
* 正常執行：
```clike=
#!/usr/bin/python
import subprocess
import sys
import getopt
# Driver program for C programming exercise
class Tracer:
traceDirectory = "./traces"
qtest = "./qtest"
command = qtest
verbLevel = 0
autograde = False
useValgrind = False
traceDict = {
1 : "trace-01-ops",
2 : "trace-02-ops",
3 : "trace-03-ops",
4 : "trace-04-ops",
5 : "trace-05-ops",
6 : "trace-06-string",
7 : "trace-07-robust",
8 : "trace-08-robust",
9 : "trace-09-robust",
10 : "trace-10-malloc",
11 : "trace-11-malloc",
12 : "trace-12-malloc",
13 : "trace-13-perf",
14 : "trace-14-perf",
15 : "trace-15-perf"
}
traceProbs = {
1 : "Trace-01",
2 : "Trace-02",
3 : "Trace-03",
4 : "Trace-04",
5 : "Trace-05",
6 : "Trace-06",
7 : "Trace-07",
8 : "Trace-08",
9 : "Trace-09",
10 : "Trace-10",
11 : "Trace-11",
12 : "Trace-12",
13 : "Trace-13",
14 : "Trace-14",
15 : "Trace-15"
}
maxScores = [0, 6, 6, 6, 6, 6, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7]
def __init__(self, qtest = "", verbLevel = 0, autograde = False, useValgrind = False):
if qtest != "":
self.qtest = qtest
self.verbLevel = verbLevel
self.autograde = autograde
self.useValgrind = useValgrind
def runTrace(self, tid):
if not tid in self.traceDict:
print("ERROR: No trace with id %d" % tid)
return False
fname = "%s/%s.cmd" % (self.traceDirectory, self.traceDict[tid])
vname = "%d" % self.verbLevel
clist = [self.command, self.qtest, "-v", vname, "-f", fname]
try:
retcode = subprocess.call(clist)
except Exception as e:
print("Call of '%s' failed: %s" % (" ".join(clist), e))
return False
return retcode == 0
def run(self, tid = 0):
scoreDict = { k : 0 for k in self.traceDict.keys() }
print("---\tTrace\t\tPoints")
if tid == 0:
tidList = self.traceDict.keys()
else:
if not tid in self.traceDict:
print("ERROR: Invalid trace ID %d" % tid)
return
tidList = [tid]
score = 0
maxscore = 0
if self.useValgrind:
self.command = 'valgrind'
else:
self.command = self.qtest
self.qtest = ''
for t in tidList:
tname = self.traceDict[t]
if self.verbLevel > 0:
print("+++ TESTING trace %s:" % tname)
ok = self.runTrace(t)
maxval = self.maxScores[t]
tval = maxval if ok else 0
print("---\t%s\t%d/%d" % (tname, tval, maxval))
score += tval
maxscore += maxval
scoreDict[t] = tval
print("---\tTOTAL\t\t%d/%d" % (score, maxscore))
if self.autograde:
# Generate JSON string
jstring = '{"scores": {'
first = True
for k in scoreDict.keys():
if not first:
jstring += ', '
first = False
jstring += '"%s" : %d' % (self.traceProbs[k], scoreDict[k])
jstring += '}}'
print(jstring)
def usage(name):
print("Usage: %s [-h] [-p PROG] [-t TID] [-v VLEVEL] [--valgrind]" % name)
print(" -h Print this message")
print(" -p PROG Program to test")
print(" -t TID Trace ID to test")
print(" -v VLEVEL Set verbosity level (0-3)")
sys.exit(0)
def run(name, args):
prog = ""
tid = 0
vlevel = 1
levelFixed = False
autograde = False
useValgrind = False
optlist, args = getopt.getopt(args, 'hp:t:v:A', ['valgrind'])
for (opt, val) in optlist:
if opt == '-h':
usage(name)
elif opt == '-p':
prog = val
elif opt == '-t':
tid = int(val)
elif opt == '-v':
vlevel = int(val)
levelFixed = True
elif opt == '-A':
autograde = True
elif opt == '--valgrind':
useValgrind = True
else:
print("Unrecognized option '%s'" % opt)
usage(name)
if not levelFixed and autograde:
vlevel = 0
t = Tracer(qtest = prog, verbLevel = vlevel, autograde = autograde, useValgrind = useValgrind)
t.run(tid)
if __name__ == "__main__":
run(sys.argv[0], sys.argv[1:])
```
* 有錯誤：
```clike=
#!/usr/bin/python
import subprocess
import sys
import getopt
# Driver program for C programming exercise
class Tracer:
traceDirectory = "./traces"
qtest = "./qtest"
command = qtest
verbLevel = 0
autograde = False
useValgrind = False
traceDict = {
1: "trace-01-ops",
2: "trace-02-ops",
3: "trace-03-ops",
4: "trace-04-ops",
5: "trace-05-ops",
6: "trace-06-string",
7: "trace-07-robust",
8: "trace-08-robust",
9: "trace-09-robust",
10: "trace-10-malloc",
11: "trace-11-malloc",
12: "trace-12-malloc",
13: "trace-13-perf",
14: "trace-14-perf",
15: "trace-15-perf",
16: "trace-16-perf",
17: "trace-17-complexity"
}
traceProbs = {
1: "Trace-01",
2: "Trace-02",
3: "Trace-03",
4: "Trace-04",
5: "Trace-05",
6: "Trace-06",
7: "Trace-07",
8: "Trace-08",
9: "Trace-09",
10: "Trace-10",
11: "Trace-11",
12: "Trace-12",
13: "Trace-13",
14: "Trace-14",
15: "Trace-15",
16: "Trace-16",
17: "Trace-17"
}
maxScores = [0, 6, 6, 6, 6, 5, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 5]
def __init__(self,
qtest="",
verbLevel=0,
autograde=False,
useValgrind=False):
if qtest != "":
self.qtest = qtest
self.verbLevel = verbLevel
self.autograde = autograde
self.useValgrind = useValgrind
def runTrace(self, tid):
if not tid in self.traceDict:
print("ERROR: No trace with id %d" % tid)
return False
fname = "%s/%s.cmd" % (self.traceDirectory, self.traceDict[tid])
vname = "%d" % self.verbLevel
clist = [self.command, "-v", vname, "-f", fname]
try:
retcode = subprocess.call(clist)
except Exception as e:
print("Call of '%s' failed: %s" % (" ".join(clist), e))
return False
return retcode == 0
def run(self, tid=0):
scoreDict = {k: 0 for k in self.traceDict.keys()}
print("---\tTrace\t\tPoints")
if tid == 0:
tidList = self.traceDict.keys()
else:
if not tid in self.traceDict:
print("ERROR: Invalid trace ID %d" % tid)
return
tidList = [tid]
score = 0
maxscore = 0
if self.useValgrind:
self.command = 'valgrind ' + self.qtest
else:
self.command = self.qtest
for t in tidList:
tname = self.traceDict[t]
if self.verbLevel > 0:
print("+++ TESTING trace %s:" % tname)
ok = self.runTrace(t)
maxval = self.maxScores[t]
tval = maxval if ok else 0
print("---\t%s\t%d/%d" % (tname, tval, maxval))
score += tval
maxscore += maxval
scoreDict[t] = tval
print("---\tTOTAL\t\t%d/%d" % (score, maxscore))
if self.autograde:
# Generate JSON string
jstring = '{"scores": {'
first = True
for k in scoreDict.keys():
if not first:
jstring += ', '
first = False
jstring += '"%s" : %d' % (self.traceProbs[k], scoreDict[k])
jstring += '}}'
print(jstring)
def usage(name):
print("Usage: %s [-h] [-p PROG] [-t TID] [-v VLEVEL] [--valgrind]" % name)
print(" -h Print this message")
print(" -p PROG Program to test")
print(" -t TID Trace ID to test")
print(" -v VLEVEL Set verbosity level (0-3)")
sys.exit(0)
def run(name, args):
prog = ""
tid = 0
vlevel = 1
levelFixed = False
autograde = False
useValgrind = False
optlist, args = getopt.getopt(args, 'hp:t:v:A', ['valgrind'])
for (opt, val) in optlist:
if opt == '-h':
usage(name)
elif opt == '-p':
prog = val
elif opt == '-t':
tid = int(val)
elif opt == '-v':
vlevel = int(val)
levelFixed = True
elif opt == '-A':
autograde = True
elif opt == '--valgrind':
useValgrind = True
else:
print("Unrecognized option '%s'" % opt)
usage(name)
if not levelFixed and autograde:
vlevel = 0
t = Tracer(qtest=prog,
verbLevel=vlevel,
autograde=autograde,
useValgrind=useValgrind)
t.run(tid)
if __name__ == "__main__":
run(sys.argv[0], sys.argv[1:])
```
:::warning
用 `diff -up` 列出程式差異即可，之後請送 pull request 修正 Valgrind 使用的問題
:notes: jserv
:::
* 在使用 `massif` 前要將 `.valgrindrc` 檔案中的 `--show-leak-kinds=all` 移除才能夠運作
* 下圖為利用 `massif-visualizer` 對 `trace01` 做出的記憶體行為視覺化
* 嘗試錯誤：
* 在撰寫 `queue.c` 的 `q_free` 過程中曾經忘記將 `queue` 的節點 `value` 的記憶體也釋放，因而造成 `memory leak`，利用 `massif` 實驗此情況
* 實驗 command：
```clike=
new
ih a
ih b
ih c
sort
free
quit
```
* **有**將節點的 `value` 釋放：
* **無**將節點的 `value` 釋放：
* 根據結果圖可看出在無釋放時，最後 `memory heap size` 為 126B ；有釋放時則回到 0B ，所以根據 `valgrind` 能確確實實的看到 memory leak，並利用 `massif` 可以更清楚的觀察
### 找出 2/22 所發生的問題點 (2/23 解決)
* 先更新到最新的 `driver.py` 並根據 `diff -up` 找出程式差異，在處理一些無關緊要的差異後發現可能的錯誤點
```clike=
def runTrace(self, tid):
if not tid in self.traceDict:
self.printInColor("ERROR: No trace with id %d" % tid, self.RED)
return False
fname = "%s/%s.cmd" % (self.traceDirectory, self.traceDict[tid])
vname = "%d" % self.verbLevel
clist = [self.command, "-v", vname, "-f", fname]
try:
retcode = subprocess.call(clist)
except Exception as e:
self.printInColor("Call of '%s' failed: %s" % (" ".join(clist), e), self.RED)
return False
return retcode == 0
def run(self, tid=0):
scoreDict = {k: 0 for k in self.traceDict.keys()}
print("---\tTrace\t\tPoints")
if tid == 0:
tidList = self.traceDict.keys()
else:
if not tid in self.traceDict:
self.printInColor("ERROR: Invalid trace ID %d" % tid, self.RED)
return
tidList = [tid]
score = 0
maxscore = 0
if self.useValgrind:
self.command = 'valgrind ' + self.qtest
else:
self.command = self.qtest
.
.
.
```
* 問題出現在第 28 行的 `self.command = 'valgrind ' + self.qtest` 使 `self.command` 值會更動為 `'valgrind /tmp/qtest.xxxxxx'` 然後放在第 7 行的 `clist` 中，並在第 9 行時利用 `subprocess.call` 來進行子進程的呼叫，但這裡的 `subprocess.call` 會直接 fail 並丟出 Exception，所以我根據這個問題進行以下測試
### Test and resolve
* 測試環境：
```shell
$ python3 -V
Python 3.6.5
```
* 測試程式：
1. ```python
import subprocess
subprocess.call(["ls -l"])
```
2. ```python
import subprocess
subprocess.call(["ls","-l"])
```
* 上述兩程式主要差異在於 `subprocess.call` 中的參數不同
* 測試結果：
1. ```python=
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
File "/usr/lib/python3.6/subprocess.py", line 267, in call
with Popen(*popenargs, **kwargs) as p:
File "/usr/lib/python3.6/subprocess.py", line 709, in __init__
restore_signals, start_new_session)
File "/usr/lib/python3.6/subprocess.py", line 1344, in _execute_child
raise child_exception_type(errno_num, err_msg, err_filename)
FileNotFoundError: [Errno 2] No such file or directory: 'ls -l': 'ls -l'
```
2. ```python=
total 524
-rw-rw-r-- 1 os2018 os2018 15909 Feb 22 15:50 console.c
-rw-rw-r-- 1 os2018 os2018 1972 Feb 22 15:50 console.h
-rw-rw-r-- 1 os2018 os2018 52072 Feb 23 11:46 console.o
drwxrwxr-x 2 os2018 os2018 4096 Feb 23 11:46 dudect
.
.
.
```
* 從結果可看出第一種寫法會造成程式不可執行，也就是 `driver.py` 可能的問題，所以只要將寫法改成第二種就可以執行了
* WHY?
* 在查閱一些資料後得出結論，在 `subprocess.py` 中定義`call` 函式的第一個參數 `args` ，可以是一個字串，可以是一個包含程序參數的 list。要执行的程序一般就是这个列表的第一项，或者是字串本身。
`subprocess.call(["ls","-l"])`
`subprocess.call(["ls -l"])`
這兩者中，第二個將不能執行。若參數要為字串時，該字串須為程式的路徑才可以。
但是下面的程式碼可以成功執行
` subprocess.call(["ls -l"], shell=True)`
原因是，它相當於
` subprocess.call(["/bin/sh", "-c", "ls -l"]) `
當 shell=False 時 (預設值)，call 使用 os.execvp() 來執行子行程。args 一般須為一個 list。如果 args 是字元的話，會作為可執行檔案之路徑，無法傳入參數。
但是，在 Windows 下，兩種皆可以運作，由於 windows 下的 `CreateProcess` 接受的一個字串。即使是 list 型別的參數，也需要先合併成字串再傳遞給 api，都會變成類似下面的程式碼去執行
`subprocess.call("notepad.exe tmp.txt" shell=True)`
* 結論：
* 完成下述兩點後即可運作：
* 將 `clist = [self.command, "-v", vname, "-f", fname]` 修改成 `clist = [self.command, self.qtest, "-v", vname, "-f", fname]`
* 將 `self.command = 'valgrind ' + self.qtest` 修改成 `self.command = "valgrind"`
## Dude, is my code constant time?
* 根據 [Dude, is my code constant time?](https://eprint.iacr.org/2016/1123.pdf) 所述，`dudect` 的運作步驟如下：
1. 此首先定義兩種 class 的 input data，一種是 fixed constant value ，另一種是隨機的 random input data ，一種用以測試自己的程式運作時長是否與另一種一樣，來驗證時間複雜度，而另一種則是用以 trigger certain "special" corner-case processing (若是驗證 constant time，就做一定符合的運算式，用以做比對)
2. 利用 Modern CPUs 提供的 cycle counters 做為運作時長的標準
3. Two sample t-test：比較兩組 data 的平均運作時長是否有差異
* 試著利用 t-test 去證明 null hypothesis 是錯的，反證出兩組 data 的平均運作時長是相同的
4. 計算有顯著性差異的數據筆數，若 $\dfrac{顯著性差異的數據筆數}{總數據筆數}$ 在 0.05 之上，兩組數據具備顯著性差異的可能性為95％。兩個數據所代表的樣本還有5％的可能性是沒有差異的，反之則也可用同樣的觀念表達，而其中5％的可能性是由於隨機誤差造成的
* 在 `dudect` 中，則是同時檢驗顯著性差異水平達到 0.05 以及 0.01，其中預設總筆數為 10000 ，所以若有 500 筆以上的資料具有顯著性差異則基本可以確認不符合 constant time ，若界在 500 與 10 筆之間代表其實有 99% 的機率該程式符合 contant time
```cpp
#define enough_measurements 10000 // pretty arbitrary
#define number_percentiles 100
// threshold values for Welch's t-test
#define t_threshold_bananas 500 // test failed, with overwhelming probability
#define t_threshold_moderate 10
if (max_t > t_threshold_bananas) {
printf(" Definitely not constant time.\n");
exit(0);
}
if (max_t > t_threshold_moderate) {
printf(" Probably not constant time.\n");
}
if (max_t < t_threshold_moderate) {
printf(" For the moment, maybe constant time.\n");
}
```
* Simulation 之實作方式
* 基本上的流程與 `dudect` 相同，主要差別在於如何定義兩種 class 的 input data 以及因為要驗證 constant time，所以需要一個一定符合 constant time 的基本運算式，後續的流程基本上無相異
* ```clike=
if (mode == test_insert_tail) {
for (size_t i = drop_size; i < number_measurements - drop_size; i++) {
char *s = get_random_string();
dut_new();
dut_insert_head(
get_random_string(),
*(uint16_t *) (input_data + i * chunk_size) % 10000);
before_ticks[i] = cpucycles();
dut_insert_tail(s, 1);
after_ticks[i] = cpucycles();
dut_free();
}
```
* 在進行 Simulation 時，上面程式之第 5~7 行會執行 `q_insert_head` ，因為此函式一定為 constant time ，適合用以做實驗與比對，其插入之字串也是 random 產生的。在第 9 行時則做 simulation 的主要目標，也就是測試 `q_insert_tail`，並紀錄所使用的 cpucycles ，在總筆數達到 `number_measurements` 後進行顯著性差異的驗證，若可 disprove null hypothesis 則代表該函式時間複雜度真的為 constant time
## select 系統呼叫在本程式的使用方式
* select 的使用方式
* 在 `console.c` 中 select 是用以觀察 `run_console` 函式之參數 `infile_name` ，等待該檔案描述詞狀態的改變或者直到 `timeout` ，不過在 `console.c` 中第 630 行 `cmd_select(0, NULL, NULL, NULL, NULL)` 的 timeout 設為 NULL 表示 select() 沒有 timeout
* 當 Commandline input available ，也就是 `readfds`不為空且 `FD_ISSET(infd, readfds)`為 `True` 就會讓呼叫 `readline()` ，並在成功時呼叫 `interpret_cmd(cmdline)` 用以執行該命令
* `console.c` 中處理 `fd_set*` 的函式：
1. `FD_SET(int fd, fd_set *set)`：新增 fd 至 set 中
2. `FD_CLR(int fd, fd_set *set)`：移除 set 中的 fd
3. `FD_ISSET(int fd, fd_set *set)`：確認 set 中有 fd
:::warning
除了「舉燭」外，你做了實驗去確認 select 系統呼叫的行為了嗎？
:notes: jserv
:::
* 實驗select運作
* read 與 readline 問題：
```clike=
int main() {
int keyboard;
fd_set readfd;
char cmd[10] = "";
struct timeval timeout;
keyboard = open("/dev/tty", O_RDONLY | O_NONBLOCK);
assert(keyboard > 0);
while (1) {
FD_ZERO(&readfd);
FD_SET(keyboard, &readfd);
select(keyboard + 1, &readfd, NULL, NULL, NULL);
if (FD_ISSET(keyboard, &readfd)) {
read(keyboard, &cmd, 10);
printf("You type:%s\n", cmd);
}
}
}
```
* 從鍵盤讀入自己的輸入的文字並輸出，當運作後輸入"short count"之運作結果：
```bash=
short count
You type:short coun
You type:t
ort coun
```
* 改成使用 `console.c` 中的 `readline()` 來取代 `read()`，並定義 `RIO_BUFSIZE` 為 10
```clike=
#define RIO_BUFSIZE 10
int main() {
int keyboard;
int ret, i;
char c;
fd_set readfd;
struct timeval timeout;
char *cmdline;
FILE * fp;
keyboard = open("/dev/tty", O_RDONLY | O_NONBLOCK);
assert(keyboard > 0);
rio_ptr rnew = malloc(sizeof(rio_t));
rnew->fd = keyboard;
rnew->cnt = 0;
rnew->bufptr = rnew->buf;
rnew->prev = buf_stack;
buf_stack = rnew;
while (1) {
FD_ZERO(&readfd);
FD_SET(keyboard, &readfd);
ret = select(keyboard + 1, &readfd, NULL, NULL,NULL);
if (FD_ISSET(keyboard, &readfd)) {
cmdline = readline();
//read(keyboard,cmdline,1);
printf("You type cmd : %s\n",cmdline);
}
}
}
```
* 從鍵盤讀入自己的輸入的文字並輸出，當運作後輸入 "short count" 之運作結果：
```bash=
short count
You type cmd : short coun
You type cmd : t
```
* 使用 `readline` 發現不會造成像 `read` 多出 `ort coun` 的問題
* select 實際函式運作
* 以一程式做實驗，並預期以下結果
* 可輸入 "dir" 來運作 "ls -l" 並輸出
* 可以藉由輸入 "sleep" 來執行 `FD_CLR(keyboard, &readfd)`，並在下一個 loop 時因 `FD_ISSET(keyboard, &readfd)` 為 false 所以會執行 `FD_SET(keyboard, &readfd)` 且輸出 `readfd is not in set`
```clike=
int main() {
int keyboard;
int ret, i;
char c;
fd_set readfd;
struct timeval timeout;
char *cmdline;
FILE * fp;
keyboard = open("/dev/tty", O_RDONLY | O_NONBLOCK);
assert(keyboard > 0);
rio_ptr rnew = malloc(sizeof(rio_t));
rnew->fd = keyboard;
rnew->cnt = 0;
rnew->bufptr = rnew->buf;
rnew->prev = buf_stack;
buf_stack = rnew;
FD_SET(keyboard, &readfd);
while (1) {
if (FD_ISSET(keyboard, &readfd)) {
ret = select(keyboard + 1, &readfd, NULL, NULL,NULL);
cmdline = readline();
if(strcmp(cmdline,"dir\n") == 0){
if ((fp = popen("ls -l","r")) == NULL){
printf("open ls fail\n");
return -1;
}
char buf[256];
while (fgets(buf, 255, fp) != NULL)
printf("%s", buf);
if (pclose(fp) == -1){
printf("open ls fail\n");
return -1;
}
}
else if(strcmp(cmdline,"sleep\n") == 0){
if(FD_ISSET(keyboard, &readfd)){
FD_CLR(keyboard, &readfd);
}
}
else{
printf("You type unknown cmd : %s",cmdline);
}
}
else{
printf("readfd is not in set\n");
FD_SET(keyboard, &readfd);
}
}
}
```
* 實際輸出結果：
1. 輸入 `sleep` 後執行 `dir`：
```bash=
sleep
readfd is not in set
dir
total 20
-rwxrwxr-x 1 os2018 os2018 13008 Feb 27 19:24 test
-rw-rw-r-- 1 os2018 os2018 3329 Feb 27 19:18 test.c
```
* 運用 [RIO 套件](http://csapp.cs.cmu.edu/2e/ch10-preview.pdf) 的考量點
1. 避免 short count 造成的 error，在某些情況 `read` 會 transfer 比 user 請求還少的 bytes
1. 若在 read file 時遭遇 EOF 可能會造成 short count 之情況
2. 從終端機 Read line 可能會因為 text line 的大小而造成同等的 short count
2. 藉由快取到內部記憶體 buffer，使得 read text line 更有效率
* 讀取終止條件：
1. 已讀取至 `RIO_BUFSIZE`
2. 遇到 EOF
3. 遇到 Newline
* 將 text 存至 buffer
```clike=
c = *buf_stack->bufptr++;
*lptr++ = c;
buf_stack->cnt--;
/* Break when encounter newline */
if (c == '\n')
break;
```
* 整體 `console.c` 運作情境與流程
1. 從 `bool run_console(char *infile_name)` 進入
2. 呼叫 `push_file` 以 read only 方式開啟 file，並建立新的 `rio_ptr` 儲存 File descriptor 等資料，assign 給 `buf_stack`
3. 持續運作 `cmd_select(0, NULL, NULL, NULL, NULL)` 直至 `buf_stack` 為空或者 `quit` 指令輸入
4. 在 `cmd_select` 中會先利用 `read_ready()` check input buffer 是否真的為一整行 command line，其中就是利用是否有遇到 newline 來判斷的
5. 從 input file 中讀取指令，並在成功返回時利用 `interpret_cmd()` 執行該目標指令
6. 持續讀取指令並運作直至 quit command 或者 EOF
Sign in with Wallet
Connect another wallet