2019q1 Homework1 (lab0)

contributed by < 0n3t04ll >

說明

• 作業說明
• C Programming Lab

作業要求

實作 FIFO、LIFO 的 Queue

• q_new(): Create a new, empty queue
• q_free(): Free all storage used by a queue
• q_insert_head(): Attempt to insert a new element at the head of the queue (LIFO discipline).
• q_insert_tail(): Attempt to insert a new element at the tail of the queue (FIFO discipline).
• q_remove_head(): Attempt to remove the element at the head of the queue.
• q_size(): Compute the number of elements in the queue.
  –- 以上節錄自 C Programming Lab

環境

$ uname -a
Linux starpt-K55VD 4.15.0-45-generic #48~16.04.1-Ubuntu SMP Tue Jan 29 18:03:48 UTC 2019 x86_64 x86_64 x86_64 GNU/Linux

實作

queue.h

在 queue.h 中看到 queue structure 的註解有說要加入其他 fields 來更有效率的實作 q_size(), q_insert_tail() ，在此我添加了 tail pointer 指向 queue 的尾端，用 size 在新增刪除中更新 queue 的大小，考慮到 size 應該不會出現負數，我用 unsigned int 來保存 data 。

typedef struct{
    list_ele_t *head; /*linked list of elements*/
    
    list_ele_t *tail; 
    unsigned int size;
}

q_new()

透過 malloc 要一個 queue structure 的空間並初始化，需要判斷 malloc 成功與否。

/*
   Create empty queue.
   Return NULL if could not allocate space.
   */
queue_t *q_new()
{
    queue_t *q = (queue_t *) malloc(sizeof(queue_t));
    /* What if malloc returned NULL? */
    if (!q)
        return NULL;
    // initial queue
    q->head = NULL;
    q->tail = NULL;
    q->size = 0;
    return q;
}

q_free()

用一個 element pointer curr 來遍歷整個 queue。
用另一個 element pointer tmp 來接收準備要被 free 掉的 element ，在 curr 更新後再 free 掉 tmp

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

q_insert_head()

要確認 newh, value 都有 malloc 成功，失敗就要 free 掉之前 malloc 的空間。
以 strlen(), strcpy() 來存資料，新增的同時也要更新 q->size ，由於增加了 tail pointer ，所以我透過 q->size 判斷是否要更新 q->tail。

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

    strcpy(newh->value, s);
    newh->next = q->head;
    q->head = newh;
    q->size += 1;
    if (q->size == 1)  // the first one
        q->tail = newh;
    return true;
}

q_insert_tail()

先判斷 newh, value 是否 malloc 成功，其中一個失敗就要 free 掉先前 malloc 的。
insert tail 的時候要特別注意 tail, head 的更新。

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)
        return false;
    list_ele_t *newh = (list_ele_t *) malloc(sizeof(list_ele_t));
    if (!newh)
        return false;
    newh->next = NULL;
    newh->value = (char *) malloc(strlen(s) + 1);
    if (!(newh->value)) {
        free(newh);
        return false;
    }
    strcpy(newh->value, s);
    if (q->tail)
        q->tail->next = newh;
    q->tail = newh;
    if (!(q->head))
        q->head = q->tail;
    q->size += 1;
    return true;
}

q_remove_head()

先判斷 queue 的 pointer 和 size，確保不為 NULL 或 empty。
用 tmp pointer 接收原本的 head 再對 queue 做更新，再判斷 sp 地址的有無來決定要不要複製 head->value ，最後 free 掉 tmp。

bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
    /* You need to fix up this code. */
    if (!q || q->size == 0)  // q is NULL or q is empty
        return false;
    list_ele_t *tmp = q->head;
    q->head = q->head->next;
    q->size -= 1;
    if (q->size <= 1)
        q->tail = q->head;

    // if(sp && q->head != tmp)
    if (sp) {
        strncpy(sp, tmp->value, bufsize - 1);
        sp[bufsize - 1] = '\0';
    }
    free(tmp->value);
    free(tmp);
    return true;
}

q_size()

由於在增減 queue 的過程就在維護 queue 的 size ，故在此只需回傳 q->size 即可

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)
        return 0;
    return q->size;
}

q_reverse()

reverse 的部份我是以三個 pointer: prev, curr, last 來遍歷整個queue ，每經過一個 element 就修正 next pointer ，使其指回 prev ，最後更新這三個 pointer 。
head, tail 的更新是當所有 element reverse 後將 head assign 給 tail ， last assign 給 head。

void q_reverse(queue_t *q)
{
    /* You need to write the code for this function */
    if (!q)
        return;
    if (q->size == 0 || q->size == 1)
        return;
    list_ele_t *prev = NULL;
    list_ele_t *curr = q->head;
    list_ele_t *last = NULL;
    while (curr != q->tail) {
        last = curr->next;
        // reverse link
        curr->next = prev;

        // update
        prev = curr;
        curr = last;
    }
    last->next = prev;
    q->tail = q->head;
    q->head = last;
}

Valgrind Test

之前有用過 valgrind 一個一個測試過 qtest ，大致上跟 Naetw 說的一樣，會在13、14的時候壞掉，不過那時有看到 Naetw 跟老師說會 PR ，所以我就乖乖的等更新。

實際跑過一次是沒有問題的，只不過在測試13、14、15的時後跑的特別慢，讓我一度以為壞掉。

「路見不平，拿 patch 來填」，請見 PR #5
jserv

$ make valgrind

cp qtest /tmp/qtest.TLAtCE
chmod u+x /tmp/qtest.TLAtCE
sed -i "s/alarm/isnan/g" /tmp/qtest.TLAtCE
scripts/driver.py -p /tmp/qtest.TLAtCE --valgrind
...
+++ TESTING trace trace-01-ops:
---	trace-01-ops	6/6
+++ TESTING trace trace-02-ops:
---	trace-02-ops	6/6
+++ TESTING trace trace-03-ops:
---	trace-03-ops	6/6
+++ TESTING trace trace-04-ops:
---	trace-04-ops	6/6
+++ TESTING trace trace-05-ops:
---	trace-05-ops	6/6
+++ TESTING trace trace-06-string:
---	trace-06-string	7/7
+++ TESTING trace trace-07-robust:
---	trace-07-robust	7/7
+++ TESTING trace trace-08-robust:
---	trace-08-robust	7/7
+++ TESTING trace trace-09-robust:
---	trace-09-robust	7/7
+++ TESTING trace trace-10-malloc:
---	trace-10-malloc	7/7
+++ TESTING trace trace-11-malloc:
---	trace-11-malloc	7/7
+++ TESTING trace trace-12-malloc:
---	trace-12-malloc	7/7
+++ TESTING trace trace-13-perf:
---	trace-13-perf	7/7
+++ TESTING trace trace-14-perf:
---	trace-14-perf	7/7
+++ TESTING trace trace-15-perf:
---	trace-15-perf	7/7
---	TOTAL		100/100

AddressSanitizer 檢測

修改了 Makefile 中的 CFLAGS ，添加 sanitizer 參數，若有發生 UAF, heap overflow, memory leak 就會報錯。
參數如下：

CFLAGS = -O0 -g -Wall -Werror -fsanitize=address

因為沒有問題，所以什麼都沒顯示。

研究 q_test

q_test.c

qtest.c main function 中的 while loop 主要是用來接收外部傳進來的參數，像是 verbose level, testcase file 等等，在此先忽略避免程式區塊過大。

後續主要程式如下：

    queue_init();    // set q ptr, file_cnt, signalhandler
    init_cmd();      // use linked list to link global cmd structure, paramter
                     // structure
    console_init();  // same with above but linked queue function
    set_verblevel(level);
    if (level > 1) {
        set_echo(true);
    }
    if (logfile_name)
        set_logfile(logfile_name);
    add_quit_helper(queue_quit);
    bool ok = true;
    ok = ok && run_console(infile_name);
    ok = ok && finish_cmd();
    return ok ? 0 : 1;
}

queue_init() 負責初始化 queue pointer 為 NULL 和註冊 sigsegv, sigalrm 的 handler 。

init_cmd() 用 add_cmd() 函數把跟 queue 無關的 cmd 用 cmd_ptr 保存並串成 linked list 。
之所以用 linked list ，個人猜測是為了之後修改做的彈性設定。
下面是 cmd 的 structure ：

struct CELE {
    char *name;
    cmd_function operation;  // funtion ptr point to cmd function
    char *documentation;
    cmd_ptr next;
};

而 console_init() 用了一樣的方式串連跟 queue 相關的 cmd 成 linked list 。

interpret_cmda

真正處理 cmd 的輸入和操作是在 cmd_select() 內部 ，可以分為從檔案讀取 cmd 或是從 stdin 讀取。
讀取後後進入 interpret_cmd ，在裡面做 parse 接著傳給 interpret_cmda() 操作該 cmd ，方法是遍歷 cmd_list 並用 strcmp() 比對 cmd name 並且用該 cmd structure 中的 function ptr 執行 cmd 。

static bool interpret_cmda(int argc, char *argv[])
{
    if (argc == 0)
        return true;
    /* Try to find matching command */
    cmd_ptr next_cmd = cmd_list;
    bool ok = true;
    while (next_cmd && strcmp(argv[0], next_cmd->name) != 0)
        next_cmd = next_cmd->next;
    if (next_cmd) {
        ok = next_cmd->operation(argc, argv);
        if (!ok)
            record_error();
    } else {
        report(1, "Unknown command '%s'", argv[0]);
        record_error();
        ok = false;
    }
    return ok;
}

Exception Handler

cmd 操作都是透過 function ptr ，而在我比對所有的 cmd 後發現執行自己寫的 queue 操作前都會有一段應該跟 exception handler 相關的 statement ，以 do_new() 的 13~15 為例：

bool do_new(int argc, char *argv[])
{
    if (argc != 1) {
        report(1, "%s takes no arguments", argv[0]);
        return false;
    }
    bool ok = true;
    if (q != NULL) {
        report(3, "Freeing old queue");
        ok = do_free(argc, argv);
    }
    error_check();
    if (exception_setup(true))
        q = q_new();
    exception_cancel();
    qcnt = 0;
    show_queue(3);
    return ok && !error_check();
}

從名稱上來看應該是 exception 的前置作業，進入後發現用了 sigsetjmp ，該 function 從 manual 來看是用來保存 stack context/ environment ，好在處理 interrupt 或 error 後可以繼續執行。

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

而專司處理 signal 的兩個 handler 內部都是執行 harness.c 中的 trigger expression

其中的 siglongjmp() 根據 manual 描述為回復在 sigsetjmp 中保存的 env 好返回先前執行狀態以便繼續執行，達到 exception handler 的效果。

void trigger_exception(char *msg)
{
    error_occurred = true;
    error_message = msg;
    if (jmp_ready)
        siglongjmp(env, 1);
    else
        exit(1);
}

因為對 signal 處理過程不熟，所以決定親自用 gdb 跟蹤一次。
若用單純的下斷點對 signal 是行不通的，必須要用 handle 處理，根據這份manual，必須用

gdb$ handle SIGSEGV pass

讓該 sigsegv pass 到 handler 才能繼續，不然 gdb 只會卡死在發生 sigsegv 的指令上。

發現過程如下：

1. 進入 sigsegvhandler
2. 進入 trigger_expression
3. 由 jmp_ready 判斷 sigjmp_buf 是否準備好
   • 若尚未準備好，立即 exit(1)
   • 準備好則進入下個步驟

   這邊我是參考 0xff77 同學的描述

4. 由 siglongjmp() 跳回 exception_setup() 中的 sigsetjmp() ， code 如下：

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;

5. 由於是從 siglongjmp 過來，故 return value 不為 0 ，進入 if scope ，重設好相關變數並印出錯誤訊息，最後返回至 exception_cancel()
6. exception_cancel() 取消 alarm 限制和重設

至此完成了一個 exception handler 的過程。

test_malloc, test_free

在跟進 harness.c 後，發現裡面有個比較特別的 test_malloc, test_free ，在 harness.h 找了一下後發現程式測試的 malloc, free 會被 test_malloc, test_free 取代：

/* Tested program use our versions of malloc and free */
#define malloc test_malloc
#define free test_free

下面為 test_malloc 程式碼，我把程式碼分為數個片段搭配文字解釋。

line 122 中用 noallocate_mode 來決定要不要 malloc 。

void *test_malloc(size_t size)
{
    if (noallocate_mode) {
        report_event(MSG_FATAL, "Calls to malloc disallowed");
        return NULL;

比較有趣的是 fail_allocation() ，用隨機的方式判斷 malloc 有沒有成功，我以前都是直接測完全失敗或完全成功，用隨機的方式進行測試應該是模擬 malloc 突然壞掉的情形下有無做好檢查。

    }
    if (fail_allocation()) {
        report_event(MSG_WARN, "Malloc returning NULL");
        return NULL;
    }

malloc 出來的 chunk 還要再包一層 block_ele_t ， block_ele_t 在實作上用到了之前在 C_and_CPP 板上看到的一篇討論提過的技巧，透過 zero length array 可以動態改變 struct 空間，這邊因為 user 要求的空間不固定但又想包在同個 struct 所以用這種方法。

typedef struct BELE {
    struct BELE *next;
    struct BELE *prev;
    size_t payload_size;
    size_t magic_header; /* Marker to see if block seems legitimate */
    unsigned char payload[0];
    /* Also place magic number at tail of every block */
} block_ele_t;

malloc 出來的 block 會拆分為三個部分：原本放 data 的空間、額外的 block metadata 空間、 footer 空間。

    block_ele_t *new_block =
        malloc(size + sizeof(block_ele_t) + sizeof(size_t));
    if (new_block == NULL) {
        report_event(MSG_FATAL, "Couldn't allocate any more memory");
        error_occurred = true;
    }

從下面程式碼可以看出 qtest 透過 double linked list 維護 malloc 出來的 block。
除了自己用 double linked list 維護 block 外， test_malloc 還在 block 的 header, footer 加上 MAGICHEADER, MAGICFOOTER 兩個常數，猜測是為了要檢查有無 heap overflow 的發生。

    new_block->magic_header = MAGICHEADER;
    new_block->payload_size = size;
    *find_footer(new_block) = MAGICFOOTER;
    void *p = (void *) &new_block->payload;
    memset(p, FILLCHAR, size);
    new_block->next = allocated;
    new_block->prev = NULL;
    if (allocated)
        allocated->prev = new_block;
    allocated = new_block;
    allocated_count++;
    return p;
}

test_free() 對 test_malloc() 出來的 block 做操作，開頭先判斷有無設定 noallocate_mode 和 p 的合法性。

void test_free(void *p)
{
    if (noallocate_mode) {
        report_event(MSG_FATAL, "Calls to free disallowed");
        return;
    }
    if (p == NULL) {
        report(MSG_ERROR, "Attempt to free NULL");
        error_occurred = true;
        return;
    }

透過找出 block footer 位置並且比對 MAGICFOOTER 有無被修改來確認是否發生 heap overflow ，驗證了上面的猜想。這種設計理念跟 canary 如出一轍。

    block_ele_t *b = find_header(p);
    size_t footer = *find_footer(b);
    if (footer != MAGICFOOTER) {
        report_event(MSG_ERROR,
                     "Corruption detected in block with address %p when "
                     "attempting to free it",
                     p);
        error_occurred = true;
    }

在 header, footer 的地方放上 MAGICFREE ，在 data 的地方填上 FILLCHAR ，表示該 block 已經被 free 掉。把要 free 的 block 從 double linked list 中 unlink 掉後再將之 free 。

    b->magic_header = MAGICFREE;
    *find_footer(b) = MAGICFREE;
    memset(p, FILLCHAR, b->payload_size);

    /* Unlink from list */
    block_ele_t *bn = b->next;
    block_ele_t *bp = b->prev;
    if (bp)
        bp->next = bn;
    else
        allocated = bn;
    if (bn)
        bn->prev = bp;

    free(b);
    allocated_count--;
}

test_free(), test_malloc() 之所以用額外的 double linked list 做串連是為了在測試結束後，透過遍歷 block list 評估 leak memory 的情形。這點在 do_free() 中的 allocation_check() 得到解答。

/scripts/driver.py

從 Makefile 的 test 可以發現用來自動評測的方式是透過 python script 實現。

主要的評測 class 為 Tracer ，而評測主要的 method 為 Tracer.run() 。

scoreDict 用字典保存 testcase 和相對應的得分， tid 顧名思義為 testcase 的 id 。

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 = ''

從 self.traceDict[t] 取出 testcase name 輸出測是訊息，接著把從 tidList 取出的 t 傳入 self.runTrace() ，裡面會透過 subprocess 執行：

./qtest -v 1 -f [testcase name]

subprocess 的回傳值再傳回給 Tracer.run ，並將字串格式化輸出檔名、得分、總分。然後把該項得分加總至 score 當作最後的總分。

        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