2019q3 Homework2 (lab0)

contribyted by < nckuoverload >

tags: `sysprog2019`

作業要求

在 GitHub 上 fork lab0-c
- 參閱 GitHub 設定指引
詳細閱讀 C Programming Lab (英文閱讀正是我們想強化的議題，你應該在共筆上摘要題目要求)，依據指示著手修改 queue.[ch] 和連帶的檔案，測試後用 Git 管理各項修改。
- 在提交程式前，務必詳閱如何寫好 Git Commit Message
- 不用理會 Autolab 和檔案下載的描述，這兩者都是 CMU 專屬
除了修改程式，也要編輯「作業區」，增添開發紀錄和 GitHub 連結，提及如何逐步達到要求，以及如何改善效能
- 解釋自動評分系統運作的原理
- 提及 qtest 的行為和裡頭的技巧，特別是 signal handler
- 解析 Valgrind 的運作原理和針對本程式的使用
- 根據 dudect 工具以及提出的對應論文 Dude, is my code constant time?，探討一種以實驗而非理論驗證時間複雜度的方法
- 留意 MAGICHEADER, MAGICFREE, MAGICFOOTER, FILLCHAR 等巨集的使用，並探討其動機和用法
截止日期：
- Oct 2, 2019 (含) 之前
- 越早在 GitHub 上有動態、越早接受 code review，評分越高

實驗環境

Operating System: Ubuntu 16.04 64bit
Compiler: gcc 8.3.0

測試結果

$ python ./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
please new a queue first
---     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

實作紀錄

queue_t

在queue.h中，修改queue_t結構。
新增list_ele_t *tail;用來指向尾巴。
新增int size;用來記錄目前的長度。

typedef struct {
    list_ele_t *head; /* Linked list of elements */
    list_ele_t *tail;
    int size;
} queue_t;

q_new()

首先是建立一個queue ，過程沒太大問題，要注意malloc 有可能會返回NULL ，所以在第29行要針對這個情況特別處理。













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

q_free()

釋放佇列，主要使用一個loop 去對每一個節點做處理。


















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

q_insert_head(queue_t q, char s)

和_insert_tail() 可以搭配一起來看，主要在第一個if 判斷該佇列是否為空，第二、三個判斷malloc 是否返回NULL (在測資中，會針對這個部分做測試)。
從頭插入的部分主要是新增一個節點，並將該節點指向原本的head ，並將佇列的head 指向該節點，並且size 增加。





























bool q_insert_head(queue_t *q, char *s)
{
    if (q == NULL) {
        return false;
    }
    list_ele_t *newh;
    /* What should you do if the q is NULL? */
    newh = malloc(sizeof(list_ele_t));
    if (newh == NULL) {
        free(newh);
        return false;
    }
    /* Don't forget to allocate space for the string and copy it */
    /* What if either call to malloc returns NULL? */
    newh->next = q->head;
    newh->value = malloc(sizeof(char) * (strlen(s) + 1));
    if (newh->value == NULL) {
        free(newh->value);
        free(newh);
        return false;
    }
    strcpy(newh->value, s);
    if (q->head == NULL) {
        q->tail = newh;
    }
    q->head = newh;
    q->size += 1;
    return true;
}

q_insert_tail(queue_t q, char s)

和q_insert_head() 相似，前三個判斷式相同效果，但應該有更好的寫法。
從尾端插入的部分，主要是將原本的尾端指向即將插入的節點，並將佇列中的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 */
    if (q == NULL) {
        return false;
    }
    list_ele_t *newQ;
    newQ = malloc(sizeof(list_ele_t));
    if (newQ == NULL) {
        free(newQ);
        return false;
    }
    newQ->value = malloc(sizeof(char) * (strlen(s) + 1));
    if (newQ->value == NULL) {
        free(newQ->value);
        free(newQ);
        return false;
    }
    strcpy(newQ->value, s);
    q->tail->next = newQ;
    q->tail = newQ;
    newQ->next = NULL;
    q->size += 1;
    return true;
}

q_remove_head(queue_t q, char sp, size_t bufsize)

主要要注意測試中，有兩種測試方式，一個為rh [str] 和rhq ，前者主要會和輸入的字串做判斷，在這個部分要特別注意輸入字串的大小是否大於佇列中第一個節點的大小，在第147行針對這個部分做處理，如果超過不處理的話會造成溢出(overflow)。





















bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
    /* You need to fix up this code. */
    if (q == NULL || q->size == 0) {
        return false;
    }
    if (bufsize != 0) {
        memset(sp, '\0', bufsize);
        if (strlen(q->head->value) > bufsize) {
            strncpy(sp, q->head->value, bufsize - 1);
        } else {
            strcpy(sp, q->head->value);
        }
    }
    list_ele_t *tmp = q->head;
    q->head = q->head->next;
    free(tmp->value);
    free(tmp);
    q->size--;
    return true;
}

q_size(queue_t *q)

使用額外的int size 來儲存佇列大小，為了符合題目的

O (1)

。









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

q_reverse(queue_t *q)

總共寫了兩個版本，原先使用類似bubble sort 的演算法來做倒轉，簡單來說就是模擬bubble sort 最壞情況，每一個迴圈讓一個節點移到適當的位置，並讓其他節點往前移一個位置，複雜度為

O (n^{2})

。但這樣做的話在test 會一直因為時間超過而無法通過。
第二個版本主要是多用了三個暫存變數，每一次將一個節點的指標轉向，並在最後處理q的head 和tail。也是很直觀的做法，但一開始因為題目敘述理解錯誤，誤解為不能多使用額外空間設置變數來處理。




















void q_reverse(queue_t *q)
{
    /* You need to write the code for this function */
    if (q == NULL || q->size < 2) {
        return;
    }
    list_ele_t *temp;
    list_ele_t *now = q->head->next;
    list_ele_t *pre = q->head;

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

討論

解釋自動評分系統運作的原理

主要使用Makefile 來自動評分，Makefile 寫起來類似shell script 但又不盡相同，詳細可以參考這篇範例，或是網路上應該有許多其他解說。
在原始的Makefile 中，主要是編譯後，呼叫scripts/driver.py 來評分，所以也可以在~/lab0-c 中直接使用python driver.py 來評分。
driver.py 又可以使用四個參數來使用。
h : 主要用來說明有哪些參數，類似一般使用的help 。
p : 可以選擇用哪個檔案來評分。 (不太確定式不是這個意思)
t : 可以選擇要選第幾個腳本來測試，腳本都在~/lab0-c/traces 底下。
v : 有0~3的級別，可以選擇要顯示多少測試的腳本資料。
A : 自動評分，功能等同於使用 make test 。
--valgrind : 如果直接搜尋會找到 Wikipedia 的解說，是一款GNU 的工具，用來處理記憶體除錯。稍後會再針對這部分解釋。

提及 `qtest` 的行為和裡頭的技巧，特別是 signal handler

在 qtest.c 中，會有許多 method 用來做測試，每一個都會使用 exception_setup() exception_cancel() 兩個來對 exception 做處理，同時裡面也有使用到 signal 的機制。
首先會先執行 queue_init() 並且呼叫兩個 signal ，SIGSEGV 用來處理記憶體部分的例外狀況；SIGALRM 用來處理執行時間的例外狀況。
之後以 do_new() 為例，在第107行的部分，當要執行 q_new() 前，會先執行 exception_setup(true) ，用來開啟 signal ，並且在執行完成後使用 exception_cancel() 關閉。
exception_setup() 和 exception_cancel() 都在 harness.c 中。以下將分別敘述。

exception_setup():
這邊可以分成兩個流程來說明，分別是正常運作和 exception 發生時的狀況。
- 正常運作: 在正常運作下，會從 do_new() 等執行 exception_setup() 跳入，因為是正常情況，所以 sigsetjmp() 並不會被執行，會直接跳到253 行執行，jmp_ready 參數主要是用來紀錄在 exception 發生後，是否可以執行 jump 。並且這時候會在257 行給予一個執行時間，程式必須在時間內完成，否則會觸發 signal 並且丟出 sigalrmhandler 讓 qtest.c 中的 sigalrmhandler() 去處理例外。並且會將狀態恢復到未執行 q_new() 前的狀態繼續往下執行。
- 例外狀況: 如果有發生例外狀況，因為一開始有先使用 sigsetjmp 來保存 stack 環境等，所以會把剩下的時間返回，並且將錯誤訊息印出，之後在兩個 handler 中都有使用到 trigger_exception() 去處理，trigger_exception() 會使用 siglongjmp 將環境恢復到原本儲存的狀態(尚未進入會發生例外狀況的 method 前的狀態)。
























bool exception_setup(bool limit_time)
{
    if (sigsetjmp(env, 1)) {
        /* Got here from longjmp */
        jmp_ready = false;
        if (time_limited) {
            alarm(0);
            time_limited = false;
        }
        if (error_message) {
            report_event(MSG_ERROR, error_message);
        }
        error_message = "";
        return false;
    } else {
        /* Got here from initial call */
        jmp_ready = true;
        if (limit_time) {
            alarm(time_limit);
            time_limited = true;
        }
        return true;
    }
}

exception_cancel():
當 method 順利執行完後，把 signal 關閉。









void exception_cancel()
{
    if (time_limited) {
        alarm(0);
        time_limited = false;
    }
    jmp_ready = false;
    error_message = "";
}

小結， qtest.c 因為不能確保每次執行實作者在 queue.c 中實作的 method 都是可靠的，所以每次要進入 queue.c 的方法前，都會先使用 sigsetjmp 保存狀態，並且開啟 signal ，如果例外狀況沒發生，則會使用 exception_cancel() 去關閉所有上述機制。如果例外狀況發生，則會使用 trigger_exception() 中的 siglongjmp() 來恢復到進入有問題方法前的環境。

實驗
很簡單的實驗，可以把限制時間長度的 signal 關閉，並且把 q_reverse 的部分改回第一版本氣泡排序法去執行，可以發現並不會有時間錯誤的問題出現，在第13個測試 trace-13-perf.cmd 正常情況下會發生錯誤。
q_reverse() using bubble sorting

void q_reverse(queue_t *q)
{
    /* You need to write the code for this function */
    if (q == NULL) {
        return;
    }
    int temp = q->size;
    list_ele_t *t;
    for (int i = 0; i < q->size; i++) {
        temp--;
        t = q->head;
        for (int z = 0; z < temp; z++) {
            *(t->value) ^= *(t->next->value);
            *(t->next->value) ^= *(t->value);
            *(t->value) ^= *(t->next->value);
            t = t->next;
        }
    }
}

未完成

解析 Valgrind 的運作原理和針對本程式的使用
[ ]根據 dudect 工具以及提出的對應論文 Dude, is my code constant time?，探討一種以實驗而非理論驗證時間複雜度的方法
[ ]留意 MAGICHEADER, MAGICFREE, MAGICFOOTER, FILLCHAR 等巨集的使用，並探討其動機和用法

2019q3 Homework2 (lab0)

tags: sysprog2019

作業要求

實驗環境

測試結果

實作紀錄

queue_t

q_new()

q_free()

q_insert_head(queue_t *q, char *s)

q_insert_tail(queue_t *q, char *s)

q_remove_head(queue_t *q, char *sp, size_t bufsize)

q_size(queue_t *q)

q_reverse(queue_t *q)

討論

解釋自動評分系統運作的原理

提及 qtest 的行為和裡頭的技巧，特別是 signal handler

未完成

參考資料

Read more

HW: advanced system 1

F2FS and BtrFS

Leetcode record

2019q3 Homework3 (list)

tags: `sysprog2019`

q_insert_head(queue_t q, char s)

q_insert_tail(queue_t q, char s)

q_remove_head(queue_t q, char sp, size_t bufsize)

提及 `qtest` 的行為和裡頭的技巧，特別是 signal handler