2019q1 Homework1 (lab0)

contributed by <jeffcarl67>

要求

• 實做 queue
  • first in, first out
  • first in, last out
• 完成以下函式
  • 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
  • q insert tail: Attempt to insert a new element at the tail of the queue
  • q remove head: Attempt to remove the element at the head of the queue
  • q size: Compute the number of elements in the queue
  • q reverse: Reorder the list so that the queue elements are reversed in order
• 解釋自動評分系統運作的原理
• 提及 qtest 的行為和裡頭的技巧

環境

Linux 4.15.0-45-generic #48~16.04.1-Ubuntu SMP 

實做

q_new

分配一個 queue，要注意 malloc 失敗後的錯誤處理以及 queue_t 結構的初始化

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

q_free

釋放 queue 使用的所有記憶體，此處的作法是每次都刪除第一個元素，直到 linked list 中沒有元素為止

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

q_insert_head

在 queue 的開頭插入一個元素，要比較注意的地方是在用於儲存字串的指針 newh->value 取得記憶體失敗後，在錯誤處理時除了 return false 外還要將先前取得的記憶體一併釋放，才不會有記憶體洩漏的問題

/*
  Attempt to insert element at head of queue.
  Return true if successful.
  Return false if q is NULL or could not allocate space.
  Argument s points to the string to be stored.
  The function must explicitly allocate space and copy the string into it.
 */
bool q_insert_head(queue_t *q, char *s)
{
    list_ele_t *newh = NULL;
    /* What should you do if the q is NULL? */
    if (!q)
        return false;
    newh = malloc(sizeof(list_ele_t));
    if (!newh)
        return false;
    newh->value = (char *) malloc(strlen(s) + 1);
    if (!newh->value) {
        free(newh);
        return false;
    }
    newh->next = NULL;
    memcpy(newh->value, s, strlen(s) + 1);
    q->size++;
    /* Don't forget to allocate space for the string and copy it */
    /* What if either call to malloc returns NULL? */
    newh->next = q->head;
    q->head = newh;
    if (!q->tail)
        q->tail = newh;
    return true;
}

q_insert_tail

在 queue 的尾端插入一個元素

/*
  Attempt to insert element at tail of queue.
  Return true if successful.
  Return false if q is NULL or could not allocate space.
  Argument s points to the string to be stored.
  The function must explicitly allocate space and copy the string into it.
 */
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 = NULL;
    if (!q)
        return false;
    newh = malloc(sizeof(list_ele_t));
    if (!newh)
        return false;
    newh->value = malloc(strlen(s) + 1);
    if (!newh->value) {
        free(newh);
        return false;
    }

    memcpy(newh->value, s, strlen(s) + 1);
    newh->next = NULL;
    if (!q->head)
        q->head = newh;
    if (!q->tail)
        q->tail = newh;
    else {
        q->tail->next = newh;
        q->tail = newh;
    }
    q->size++;
    return true;
}

q_remove_head

從 queue 前端移除一個元素，並在參數 char *sp 不為 NULL 的情況下將被刪除元素的字串複製最多 bufsize-1 長度到 char *sp 中

/*
  Attempt to remove element from head of queue.
  Return true if successful.
  Return false if queue is NULL or empty.
  If sp is non-NULL and an element is removed, copy the removed string to *sp
  (up to a maximum of bufsize-1 characters, plus a null terminator.)
  The space used by the list element and the string should be freed.
*/
bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
    /* You need to fix up this code. */
    list_ele_t *cur;
    size_t len;
    if (!q)
        return false;
    if (!q->head)
        return false;
    cur = q->head;
    len = strlen(cur->value) < bufsize - 1 ? strlen(cur->value) : bufsize - 1;
    if (sp) {
        memcpy(sp, cur->value, len);
        sp[len] = '\0';
    }
    q->head = q->head->next;
    free(cur->value);
    free(cur);
    q->size--;
    return true;
}

q_size

用於取得 queue 中元素總數

/*
  Return number of elements in queue.
  Return 0 if q is NULL or empty
 */
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 || !q->head)
        return 0;
    return q->size;
}

q_reverse

在不使用額外分配記憶體的情況下翻轉 queue 中元素的順序，此處使用了三個指針prev curr next ，在循環中 curr 從 queue 中第一個元素開始走訪到最後一個元素，每次 prev指向 curr 前一個元素而 next 指向後一個元素，透過更改這三個元素間的連接達成逆序的目的。在迴圈結束時 curr 指向 NULL 而 prev 指向最後一個元素

/*
  Reverse elements in queue
  No effect if q is NULL or empty
  This function should not allocate or free any list elements
  (e.g., by calling q_insert_head, q_insert_tail, or q_remove_head).
  It should rearrange the existing ones.
 */
void q_reverse(queue_t *q)
{
    /* You need to write the code for this function */
    list_ele_t *prev, *curr, *next;

    if (!q)
        return;
    if (!q->head)
        return;

    prev = NULL;
    curr = q->head;
    q->tail = q->head;
    next = NULL;
    while (curr) {
        next = curr->next;
        curr->next = prev;
        prev = curr;
        curr = next;
    }
    q->head = prev;
}

自動評分系統

driver

在輸入 make test 進行測試時，Makefile 並沒有直接執行 qtest, 觀察 Makefile 中的規則可以發現, Makefile 以 scripts/driver.py 調用 qtest 進行測試

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

再看到 scipts/driver.py 中的內容, 其中最主要的程式碼都在 class Tracer 中, 這個 class 負責按照變數 traceDirectory 與 traceDict 中紀錄的測試檔案逐一調用 qtest 進行測試，可以發現變數 traceDirectory紀錄了測試檔案所在資料夾而 traceDict 中紀錄了測試檔的檔名

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

......

在 class Tracer 的函式 run 中, 調用 runTrace 執行單項測試後依據 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))

觀察調用 qtest 的函式 runTrace 後可知, 當執行 make test 時, 對於 qtest 的調用為命令 ./qtest -v 1 -f ./traces/trace-XX-XXXX, 其中 trace-XX-XXXX為對應的測試檔名, 此命令的意思為設定 verblevel 為 1 並將 trace-XX-XXXX 作為輸入檔案

    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

qtest

• getopt
  在 main 的開頭會先初始化一些區域變數, 緊接著就直接調用 getopt 函式對命令行參數進行處理, 從程式碼中可知 qtest 接受 4 種選項, 分別為 -h -f -v -l, 功能如下：
  • h : 印出幫助消息
  • f : 後接一個參數, 指名要輸入的檔案
  • v : 後接一個數字參數, 指名 verblevel
  • l : 後接一個參數, 指名要輸出的檔案

    while ((c = getopt(argc, argv, "hv:f:l:")) != -1) {
        switch (c) {
        case 'h':
            usage(argv[0]);
            break;
        case 'f':
            strncpy(buf, optarg, BUFSIZE);
            buf[BUFSIZE - 1] = '\0';
            infile_name = buf;
            break;
        case 'v':
            level = atoi(optarg);
            break;
        case 'l':
            strncpy(lbuf, optarg, BUFSIZE);
            buf[BUFSIZE - 1] = '\0';
            logfile_name = lbuf;
            break;
        default:
            printf("Unknown option '%c'\n", c);
            usage(argv[0]);
            break;
        }
    }

資料參考自:

http://man7.org/linux/man-pages/man3/getopt.3.html

• queue_init
  設定 signal handler 用於處理 SIGSEGV 及 SIGALRM 兩種信號, SIGSEGV 為發生 segment fault 後產生的信號, SIGALRM 為設定的定時器到時觸發的信號

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

qtest 中用於處理 signal 函式都在 harness.c 中,

為了學習 qtest 中對於 SIGSEGV, 寫了一個簡單的小程式嘗試使用 SIGSEGV 的 signal handler, 程式碼如下：

#include <stdio.h>
#include <signal.h>

void sigsegvhandler(int sig)
{
  printf("sig:%d \n",sig);
}

int main()
{
  int *p = NULL;
  signal(SIGSEGV, sigsegvhandler);
  *p = 100;
  return 0;
}

然而執行後卻發現 signal handler 被不停調用, 而非如預想中只執行一次, 經過資料搜尋與驗證後得知當 signal handler 返回後回到引發 SIGSEGV 的代碼繼續執行, 因此 SIGSEGV 一直被相同的程式碼觸發, 然而如此無法達到處理 SIGSEGV 的目的, 必須找出辦法在 signal handler 結束後不再執行惠引發錯誤的程式碼, 一種方法就是 qtest 中使用的 sigsetjmp 與 siglongjmp 函數, sigsetjmp 能夠存儲執行環境而 siglongjmp 能跳轉回預先除存的執行環境, 且 sigsetjmp 在直接調用時會返回 0, 在 siglongjmp 跳轉時會返回非 0 值, 在 qtest 中就利用了這個方式：

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

資料參考自：

https://blog.csdn.net/work_msh/article/details/8470277
http://man7.org/linux/man-pages/man2/signal.2.html

• init_cmd
  在 init_cmd 中會調用 add_cmd 與 `add_param`` 函式將一些命令存入一個 linked list 中, 並設定輸入檔案與時間
• console_init
  在 console_init 中會將剩下的所有命令都加入 linked list 中, 至此所有在 qtest 中可用的命令都已經加入了 linked list 中
• run_console
  run_console 是 qtest 程式用於處理輸入並且選擇指令執行的程式, 其中最主要執行命令的函式為 interpret_cmda, 其他相關函式大部分只用於分離命令與參數
• finish_cmd
  這個函式負責 qtest 最後的收尾工作, 其效果與直接輸入 quit 是一樣的, 而從 main函式的最後幾行可以發現, 只要在 run_console 與 finish_cmd 中發生一次諸如命令錯誤或記憶體洩漏, qtest 在最後都會返回非 0 值, 代表程式執行中發生錯誤, scripts/driver.py 就是利用這一點進行分數計算

    bool ok = true;
    ok = ok && run_console(infile_name);
    ok = ok && finish_cmd();
    return ok ? 0 : 1;

qtest 進行記憶體檢測的方式

在 harness.h 有這一段 macro:

#else
/* Tested program use our versions of malloc and free */
#define malloc test_malloc
#define free test_free
#define strdup test_strdup
#endif

因此在 queue.c 中所有的 malloc free strdup 都被替換為 qtest 自己實現的函數, 在分配記憶體時 qtest 會將所有的記憶體放入一個 linked list 中, 並利用 MAGICHEADER MAGICFREE MAGICFOOTER FILLCHAR 紀錄該塊記憶體的狀況，若是已分配的就用 MAGICHEADER 反之用 MAGICFREE, 並在既已體的末端填入 MAGICFOOTER 且在記憶體剛分配時將payload全部初始化為 FILLCHAR

/* Value at start of every allocated block */
#define MAGICHEADER 0xdeadbeef
/* Value when deallocate block */
#define MAGICFREE 0xffffffff
/* Value at end of every block */
#define MAGICFOOTER 0xbeefdead
/* Byte to fill newly malloced space with */
#define FILLCHAR 0x55

在檢查是否存在記憶體洩漏或破壞時只須檢測 linked list 中記憶體塊的分配情況與 magic number 是否被改寫就能進行判斷, 例如在函式 test_free 中的這一段程式碼:

    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;
    }
    b->magic_header = MAGICFREE;
    *find_footer(b) = MAGICFREE;
    memset(p, FILLCHAR, b->payload_size);