2020q1 Homework1 (lab0)

contributed by < eric5800602 >

開發環境

$ 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來排序鏈結的元素

實作

`queue_t` 資料結構

為了讓 q_insert_tail 與 q_size 的實作能在時間複雜度為\(O(1)\)的條件下完成，所以根據 linux2020-lab0#牛刀小試所述，在 queue_t 的結構中增加：

tail 記錄 queue 的尾部元素的記憶體位置
size 儲存 queue 的總元素個數

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)中7.20.3.3所述，malloc 後記憶體區塊的 value is indeterminate，所以加入 memset 來初始化記憶體區塊














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 本身的記憶體

















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 指向新創建的元素
































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 之值



































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 的記憶體空間



















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 的方法，結果在 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






























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)\)







int q_size(queue_t *q)
{
    if (q && q->size) {
        return q->size;
    }
    return 0;
}

q_sort

根據 LinkedListSort 中的 Merge Sort 製作 q_sort，用以達成時間複雜度為 \(O(nlogn)\) 並通過自動測試程式
因不能新增或釋放記憶體，所以也不能使用 Pseudo Node 實作
在 2/17 前實作，所以也沒有用到 natural sort






























































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 造成的























#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 觀察
程式碼：












#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 之情況























#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































































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 造成錯誤














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
例如：


















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 的部分











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 不同
在下述範例中，可看出在某些情況時兩函式之相異結果
















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



























































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 目錄中沒有錯

“directory” 一詞的翻譯是「目錄」，不要跟 folder (檔案夾) 搞混了，後者是 Microsoft Windows 提出的用語。“directory” 這詞彙已行之有年，我們會說 UNIX directory，而非 folder。
:notes: jserv

SymbolWu瞭解，感謝提供觀念釐清

而我利用舊的 driver.py 進行 make valgrind 時，就回復正常，研判可能是 driver.py 的問題

在此附上正常執行與有錯誤的 dirver.py

正常執行：
































































































































































#!/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:])

有錯誤：












































































































































































#!/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:])

用 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：
```
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 找出程式差異，在處理一些無關緊要的差異後發現可能的錯誤點

































    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

測試環境：

$ python3 -V
Python 3.6.5

測試程式：

import subprocess
subprocess.call(["ls -l"])

import subprocess
subprocess.call(["ls","-l"])

上述兩程式主要差異在於 subprocess.call 中的參數不同

測試結果：









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'








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? 所述，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
```
#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 的基本運算式，後續的流程基本上無相異
- ```
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
除了「舉燭」外，你做了實驗去確認 select 系統呼叫的行為了嗎？
:notes: jserv

實驗select運作

read 與 readline 問題：

















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"之運作結果：




short count
You type:short coun
You type:t
ort coun

改成使用 console.c 中的 readline() 來取代 read()，並定義 RIO_BUFSIZE 為 10




























#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" 之運作結果：




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


















































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);
      }
  }

}

實際輸出結果：

輸入 sleep 後執行 dir：






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 套件的考量點
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
```
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