2018q3 Homework2 (lab0)

contributed by < ofAlpaca >

tags: CSIE5006 HW

實驗環境

NAME="Ubuntu"
VERSION="18.04.1 LTS (Bionic Beaver)"
ID=ubuntu
ID_LIKE=debian
PRETTY_NAME="Ubuntu 18.04.1 LTS"
VERSION_ID="18.04"
HOME_URL="https://www.ubuntu.com/"
SUPPORT_URL="https://help.ubuntu.com/"
BUG_REPORT_URL="https://bugs.launchpad.net/ubuntu/"
PRIVACY_POLICY_URL="https://www.ubuntu.com/legal/terms-and-policies/privacy-policy"
VERSION_CODENAME=bionic
UBUNTU_CODENAME=bionic

---

Makefile

可以透過了解 Makefile 來得知此程式的流程，以本次作業的 Makefile 為例 :

• 此處是變數宣告， CC 代表的是使用 GNU compiler ， CFLAGS 則是相關參數。其中的 -O0 是最佳化參數， -Werror 則是把所有警告都轉為錯誤 (source)。

CC = gcc
CFLAGS = -O0 -g -Wall -Werror

• 在 all target 裡的相依性項目有 GIT_HOOKS 與 qtest ，前者會透過 script 去檢查是否有安裝 git hook 需要的套件並安裝上 git hook ，後者 qtest target 則會繼續照法則往下去找相依性項目。

GIT_HOOKS := .git/hooks/applied
all: $(GIT_HOOKS) qtest

$(GIT_HOOKS):
    @scripts/install-git-hooks
    @echo

• queueu.o target 下的相依性項目有 queue.[ch] 與 harness.h ，前者是本次作業的核心檔案，後者則是作業提供的 malloc() 與 free() ；經過編譯後產生 queue 的 object 檔，同時也是 qtest 的相依性項目。在 qtest target 執行編譯命令後會產生 qtest ，一個可執行檔。

queue.o: queue.c queue.h harness.h
	$(CC) $(CFLAGS) -c queue.c 

qtest: qtest.c report.c console.c harness.c queue.o
    $(CC) $(CFLAGS) -o qtest qtest.c report.c console.c harness.c queue.o

• 可以使用 make test 或 make clean 來執行 Makefile 下相對應的命令，make test 就會去執行 driver.py 來跑測試並計算分數， make clean 則會清除過程中產生的多餘檔案。

test: qtest scripts/driver.py
    scripts/driver.py

clean:
    rm -f *.o *~ qtest 
    rm -rf *.dSYM
    (cd traces; rm -f *~)

---

Queue Structure

• 根據作業提供的文件有提到目前的 queue_t 結構不完整，需要再增加其他欄位。為了能以
  $O(1)$ 的時間複雜度從尾端插入節點與計算 queue 的大小，增加了 list_ele_t *tail 與 size_t size 。

  The top-level representation of a queue is a structure of type queue_t. In the starter code, this structure contains only a single field head, but you will want to add other fields.

typedef struct {
    list_ele_t *head;  /* Linked list of elements */
                       /*
                         You will need to add more fields to this structure
                         to efficiently implement q_size and q_insert_tail
                       */
    list_ele_t *tail;  // ptr to tail of the queue
    size_t size;       // size of the queue
} queue_t;

---

Operations of Queue

q_new()

新增 if statement 來判斷佇列是否為 NULL ，並對 tail 與 size 初始化。

queue_t *q_new()
{
    queue_t *q = malloc(sizeof(queue_t));
    /* What if malloc returned NULL? */
    if (q == NULL)
        return NULL;
    q->head = NULL;
    q->tail = NULL;
    q->size = 0;  // initialization
    return q;
}

q_free()

新增 if statement 來判斷佇列是否為空，如果是，則 do nothing ，否則宣告 nptr pointer 去尋訪佇列中的每一個節點並釋放它，最後再釋放佇列。

void q_free(queue_t *q)
{
    /* How about freeing the list elements and the strings? */
    /* Free queue structure */
    if (q != NULL) {
        list_ele_t *nptr = q->head;
        list_ele_t *rm;
        while (nptr != NULL) {
            rm = nptr;
            nptr = nptr->next;
            // free(rm->value);
            free(rm);
        }

        free(q);
    }
}

q_insert_head()

新增 if statement 來判斷佇列是否為 NULL ，是則回傳 false ，否則配置記憶體給 newh ，使用 strdup() 配置 string 的副本給 newh->value 接著把 newh->next 指向 head 。如果 head 與 tail 皆為 NULL ，則表示目前新增的節點為佇列的第一個，故 tail 也需要指向此節點，最後再 size++。

bool q_insert_head(queue_t *q, char *s)
{
    list_ele_t *newh;
    /* What should you do if the q is NULL? */
    if (q != NULL) {
        /* Don't forget to allocate space for the string and copy it */
        /* What if either call to malloc returns NULL? */
        newh = malloc(sizeof(list_ele_t));
        if (newh != NULL) {
            newh->value = strdup(s);
            newh->next = q->head;
            /* case : the first node */
            if (q->head == NULL && q->tail == NULL)
                q->tail = newh;

            q->head = newh;
            q->size++;
            return true;
        }
    }
    return false;
}

q_insert_tail()

大致步驟和 q_insert_head() 相同，只差在換成從尾部接上。為了達到時間複雜度

$O(1)$ 的要求，所以使用 tail 而非從頭開始。

bool q_insert_tail(queue_t *q, char *s)
{
    /* You need to write the complete code for this function */
    /* Remember: It should operate in O(1) time */
    list_ele_t *newh;
    if (q != NULL) {
        newh = malloc(sizeof(list_ele_t));
        if (newh != NULL) {
            newh->value = strdup(s);
            newh->next = NULL;

            /* case : the first node */
            if (q->head == NULL && q->tail == NULL)
                q->head = newh;
            else
                q->tail->next = newh;

            q->tail = newh;
            q->size++;
            return true;
        }
    }
    return false;
}

q_remove_head()

除了判斷佇列與 queue->head 是否為 NULL外，還須判斷 sp 是否為 NULL ，如果不是，則需要將最長為 bufsize - 1 的字串複製至 sp 並在其尾部加上 terminator ，最後再更新 head 。

bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
    /* You need to fix up this code. */
    if (q != NULL) {
        list_ele_t *rm_t = q->head;
        if (rm_t != NULL) {  // if the removed node is not NULL
            if (sp != NULL) {
                memcpy(sp, rm_t->value,
                       bufsize);         // copy the removed string to sp
                sp[bufsize - 1] = '\0';  // add terminator at the end
            }

            q->head = q->head->next;  // move head ptr to next node
            q->size--;
            // free(rm_t->value);
            free(rm_t);   // free the removed node
            rm_t = NULL;  // tmp ptr to NULL
            return true;
        }
    }

    return false;
}

q_size()

因為先前有新增刪除節點時都有維護 size ，所以此處只要判斷佇列是否為 NULL 並回傳就好。

int q_size(queue_t *q)
{
    /* You need to write the code for this function */
    /* Remember: It should operate in O(1) time */
    return q != NULL ? q->size : 0;
}

q_reverse()

這裡使用的 reverse 算是最直觀的，先準備三個指標，分別指向現在節點、過去節點、下個節點。迴圈內的執行順序為：
1. 先將現在節點的 next 指向過去節點( #11 )
2. 過去節點指向現在節點( #12 )
3. 現在節點指向下個節點( #13 )
4. 下個節點指向現在節點的 next ( #14 )
5. 檢查下個節點是否為 NULL ，是則停止迴圈
6. 將最後一個節點的 next 指向過去節點
7. 最後再更新 head 與 tail 指標

void q_reverse(queue_t *q)
{
    /* You need to write the code for this function */
    if (q != NULL && q->size != 0) {
        list_ele_t *pre = NULL;       // previous
        list_ele_t *cur = q->head;    // current
        list_ele_t *nxt = cur->next;  // next

        q->tail = q->head;
        while (nxt != NULL) {
            cur->next = pre;
            pre = cur;
            cur = nxt;
            nxt = cur->next;
        }

        cur->next = pre;
        q->head = cur;
    }
}

---

測試結果

TOTAL 100/100

$ make test
scripts/driver.py
---	Trace		Points
+++ TESTING trace trace-01-ops:
# Test of insert_head and remove_head
---	trace-01-ops	6/6

   ........ 
   
---	TOTAL		100/100

---

自動評分系統

這裡主要是說明自動評分系統 driver.py 的運作流程。

前言

• 根據說明文件提到，可以透過下 ./driver.py 或 make test 來執行自動評分。
• 再看看 Makefile 的 test tag 下執行的命令也是 script/driver.py 。
• 由此可知，自動評分的主要程式就是 driver.py 。

driver.py 的運作流程

1. 當執行 driver.py 後，第一個被呼叫的函式為 run() 。

2. run() 主要是設定參數，例如要測試哪個程式，要測試什麼命令之類的。

   • -h : 說明參數用途
   • -p : 所要測試的程式， default "./qtest"
   • -v : 測試訊息的 level (0-3) 設定， default 0
   • -t : 所要測試的命令的編號， default 0
   • -A : 自動產生 json 格式的成績單
   • 下 -A 參數 :
   ​​​​$ ./scripts/driver.py  -A
   ​​​​---	Trace		Points
   ​​​​---	trace-01-ops	6/6
   ​​​​---	trace-02-ops	6/6
   ​​​​---	trace-03-ops	6/6
   ​​​​---	trace-04-ops	6/6
   ​​​​---	trace-05-ops	6/6
   ​​​​---	trace-06-string	7/7
   ​​​​---	trace-07-robust	7/7
   ​​​​---	trace-08-robust	7/7
   ​​​​---	trace-09-robust	7/7
   ​​​​---	trace-10-malloc	7/7
   ​​​​---	trace-11-malloc	7/7
   ​​​​---	trace-12-malloc	7/7
   ​​​​---	trace-13-perf	7/7
   ​​​​---	trace-14-perf	7/7
   ​​​​---	trace-15-perf	7/7
   ​​​​---	TOTAL		100/100
   ​​​​{"scores": {"Trace-01" : 6, "Trace-02" : 6, "Trace-03" : 6, "Trace-04" : 6, "Trace-05" : 6, "Trace-06" : 7, "Trace-07" : 7, "Trace-08" : 7, "Trace-09" : 7, "Trace-10" : 7, "Trace-11" : 7, "Trace-12" : 7, "Trace-13" : 7, "Trace-14" : 7, "Trace-15" : 7}}
   

   預設參數 t = 0 會把所有的測試都跑過。
   ofAlpaca

3. 之後會產生 Tracer 的 instance ，並執行 method Tracer.run() ，此 method 會去把所有的測試透過 method Tracer.runTrace() 來執行一次，並根據回傳值決定此測試是否 "通過"。

   所有的測試都放在 ./traces 這個資料夾裡。
   這裡會用 "通過" 是因為程式碼裡面只有滿分跟 0 分兩種而已。
   ofAlpaca

4. Tracer.runTrace() 會呼叫 python 函式庫的 subprocess 來執行 ./qtest 並傳入相關參數給 qtest ，通過就回傳 true 。

   subprocess 其用法為 subprocess.call([./qtest -v 0 -f "trace-01-ops.cmd"])ofAlpaca

5. 當所有測試都執行完後，便會印出總成績。

---

qtest

qtest 行為

1. 其本身是個 command line interpreter
2. 初始化各項參數，例如 : -f FILE 。
3. 命令是否合理，例如在 q == NULL 的情況下跑 reverse 指令則會讓 do_reverse() 產生 "Warning: Calling reverse on null queue" 的警告。
4. 檢查 queue.[ch]裡的佇列實作是否有誤，例如 do_reverse() 就是去檢查 q_reverse() 是否有 Timeout 或 Segmentation fault 的問題。

Command information as linked list

qtest 其中有個吸引我注意的技巧，那就是所有的命令都是透過 linked list 結構來儲存的。在 console.h 可以看到其節點結構為下 :

typedef struct CELE cmd_ele, *cmd_ptr;
struct CELE {
    char *name;                // 命令名稱
    cmd_function operation;    // 命令的 function pointer
    char *documentation;       // 命令的說明
    cmd_ptr next;
};

過去在寫需要 command line 的程式時，通常都是用 if-else 或 switch 這種 hard-coded 的方式決定命令的流程，如果使用 linked list 的話就可以省去許多冗長的程式碼，例如 :

switch(cmd) {
    case "add" :
        add();
        break;
    case "remove" :
        remove();
        break;
    case "reverse" :
        reverse();
        break;
}

使用 linked list 可以改為 :

while( strcmp(cmd, cmd_list->name) != 0 )
    cmd_list = cmd_list->next;
cmd_list->operation();

如果命令很多，使用 switch 就會導致程式碼雜亂無章又不易維護，但使用 linked list 短短幾行就可以達到同樣的效果卻又有品味。另一點是，如果今天想要看到命令的說明或者其他操作，前者還要再跑一次 switch ，但後者卻只需要改為 cmd_list->documentation 就可以辦到。

Signal handling

在本次作業中， qtest 是透過 void (*signal(int sig, void (*func)(int)))(int) 這個函式來檢查程式是否 Timeout 或 Segmentation fault 的，以下一一講解。

• signal 是個軟體中斷，像 Ctrl-C 就是個中斷，而 signal() 函式提供了一個可以處理非同步事件的方法。
  • sig 為 signal number ，為中斷的編號，定義在 C 函式庫的 signal.h 裡，變數是 SIG 開頭，像是 SIGINT 、 SIGSEGV 。
  • func 可以有三種值 :
    1. SIG_IGN ，訊號忽略。
    2. SIG_DEF ，訊號會照預設情況處理。
    3. 當訊號發生時的 func 就會被呼叫，此稱為 signal handler 或 signal-catching function。
• qtest.c 的 queue_init() 就可以見到其用法 :

static void queue_init() {
    fail_count = 0;
    q = NULL;
    signal(SIGSEGV, sigsegvhandler);
    signal(SIGALRM, sigalrmhandler);
}

• 第 4 行設置了 catch SIGSEGV 的訊號，當訊號發生時就呼叫 sigsegvhandler 。
• 第 5 行設置了 catch SIGALRM 的訊號，當訊號發生時就呼叫 sigalrmhandler 。
• 當發生了 SIGSEGV 、 SIGALRM 的中斷，便會呼叫其各自的 signal handler 。這也是為什麼每次 queue.c 一發生問題，就會產生這些錯誤訊息的原因。

/* Signal handlers */
void sigsegvhandler(int sig)
{
    trigger_exception(
        "Segmentation fault occurred.  You dereferenced a NULL or invalid "
        "pointer");
}

void sigalrmhandler(int sig)
{
    trigger_exception(
        "Time limit exceeded.  Either you are in an infinite loop, or your "
        "code is too inefficient");
}