Try   HackMD

2018q3 Homework2 (lab0)

contributed by < jason53415 >

commit 應切分為更小的 commit，每個 commit 都應該專注在小部份的修改
課程助教

測試環境

$ uname -a
Linux scream-47860 4.15.0-34-generic #37-Ubuntu SMP Mon Aug 27 15:21:48 UTC 2018 x86_64 x86_64 x86_64 GNU/Linux

實做內容

queue.h

  • 為了要達成可以
    O(1)     時間取得 queue 的大小以及從尾端插入元素，需要在 queue.h 中的 queue_t 增加 list_ele_t *tail 指向 queue 的末端，以及 int size 記錄 queue 的大小。





typedef struct {
    list_ele_t *head;
    list_ele_t *tail;
    int size;
} queue_t;

queue.c

  • q_new

    • 使用 malloc() 配置記憶體，並且初始所有的變數。
    • 需要注意在 malloc() 失敗時要回傳 NULL 。

  • q_free

    • 因為每個 queue 的節點中都有一個指向字串的指標，所以在處理時必須先釋放掉字串的記憶體，再釋放節點的記憶體。
    • 確認所有節點都被釋放掉後，最後則是將 queue 本身佔用的記憶體釋放掉。

  • q_insert_head

    • 配置節點的記憶體，並且依照傳入字串的大小配置字串的記憶體，最後使用 strcpy() 將字串內容複製過去。
    • 如果 queue 本來就還沒建立，或者配置記憶體沒有成功，則回傳 false 。
    • 建立完節點之後，要讓這個節點的 next 先指向原本的 head ，再將 queue 的 head 指向這個節點。
    • 加入新的節點後，將 queue 的 size 增加 1 ，並且回傳 true 。
    • 需要特別注意在配置記憶體失敗時要回傳 NULL ，尤其是配置字串的記憶體失敗時，還要記得把先前配置給節點的記憶體也釋放掉。
    • 時間複雜度：
      O(1)

  • q_insert_tail

    • 因為我們有新增一個指標 tail 指向 queue 的末端，大致內容與 q_insert_head() 一樣，只是建立完節點之後要先讓原本的 tail->next 指向新增的節點，再讓 queue 的 tail 指向新節點。
    • 時間複雜度：
      O(1)

  • q_remove_head

    • 先確認 queue 是否有建立以及 queue 是否是空的，如果是空的直接回傳 false 。
    • 先使用 memset() 將 sp 的內容全部初始為 \0 後，在將 head 所指到的節點的字串使用 strncpy() 複製到 sp ，以避免超過 bufsize 。
    • 最後先用一個指標存下目前 head 的位址，然後將 head 指向下一個節點後，把指標所指的節點的字串以及本身的記憶體釋放掉。
    • 刪除節點後，將 queue 的 size 減少 1 ，並且回傳 true 。
    • 時間複雜度：
      O(1)

  • q_size

    • 因為在 queue 中插入或刪除資料時都會更新 size 的大小，所以除非 queue 本身沒有建立時要直接回傳 0 之外，都可以直接回傳 queue 中記錄的 size 。
    • 時間複雜度：
      O(1)

  • q_reverse

    • 如果 queue 還沒建立，或者 queue 的 size 小於等於 1 時，就直接 return 。
    • 為了要實現在不新增節點的情況下將 queue 顛倒過來，利用了三個指標 last 、 curr 、 next 指向三個連續的節點，來將 curr 中所指的下一個節點從 next 改為 last ，並且不斷將全部的指標移往下一個節點。
    • 最後要交換 head 及 tail ，讓指標正確指向 queue 的頭尾端。
    • 時間複雜度：
      O(n)

評分結果

$ make test
scripts/driver.py
---     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, and size
---     trace-04-ops    6/6
+++ TESTING trace trace-05-ops:
# Test of insert_head, insert_tail, remove_head reverse, and size
---     trace-05-ops    6/6
+++ TESTING trace trace-06-string:
# Test of truncated strings
---     trace-06-string 7/7
+++ TESTING trace trace-07-robust:
# Test operations on NULL queue
---     trace-07-robust 7/7
+++ TESTING trace trace-08-robust:
# Test operations on empty queue
---     trace-08-robust 7/7
+++ TESTING trace trace-09-robust:
# Test remove_head with NULL argument
---     trace-09-robust 7/7
+++ TESTING trace trace-10-malloc:
# Test of malloc failure on new
---     trace-10-malloc 7/7
+++ TESTING trace trace-11-malloc:
# Test of malloc failure on insert_head
---     trace-11-malloc 7/7
+++ TESTING trace trace-12-malloc:
# Test of malloc failure on insert_tail
---     trace-12-malloc 7/7
+++ TESTING trace trace-13-perf:
# Test performance of insert_tail
---     trace-13-perf   7/7
+++ TESTING trace trace-14-perf:
# Test performance of size
---     trace-14-perf   7/7
+++ TESTING trace trace-15-perf:
# Test performance of insert_tail, size, and reverse
---     trace-15-perf   7/7
---     TOTAL           100/100

自動評分系統運作原理

從 Makefile 中可以得知，執行 $ make test 時實際上就是執行 scripts/driver.py 這個程式。

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

透過執行 $ scripts/driver.py -h 可以看到有許多參數可以調整。

$ scripts/driver.py -h
Usage: scripts/driver.py [-h] [-p PROG] [-t TID] [-v VLEVEL]
  -h        Print this message
  -p PROG   Program to test
  -t TID    Trace ID to test
  -v VLEVEL Set verbosity level (0-3)

其中 TID 表示要使用哪一筆測試資料，預設的 TID 為 0 ，用來表示要使用所有的測試資料； verbosity level 則表示執行時所印出的訊息的多寡程度，以下利用了第一筆測試資料來實驗不同 verbosity level 的差異：

$ scripts/driver.py -t 1 -v 0
---     Trace           Points
---     trace-01-ops    6/6
---     TOTAL           6/6

$ scripts/driver.py -t 1 -v 1
---     Trace           Points
+++ TESTING trace trace-01-ops:
# Test of insert_head and remove_head
---     trace-01-ops    6/6
---     TOTAL           6/6

$ scripts/driver.py -t 1 -v 2
---     Trace           Points
+++ TESTING trace trace-01-ops:
cmd># Test of insert_head and remove_head
cmd>option fail 0
cmd>option malloc 0
cmd>new
cmd>ih gerbil
cmd>ih bear
cmd>ih dolphin
cmd>rh dolphin
Removed dolphin from queue
cmd>rh bear
Removed bear from queue
cmd>rh gerbil
Removed gerbil from queue
cmd>
---     trace-01-ops    6/6
---     TOTAL           6/6

$ scripts/driver.py -t 1 -v 3
---     Trace           Points
+++ TESTING trace trace-01-ops:
cmd># Test of insert_head and remove_head
cmd>option fail 0
cmd>option malloc 0
cmd>new
q = []
cmd>ih gerbil
q = [gerbil]
cmd>ih bear
q = [bear gerbil]
cmd>ih dolphin
q = [dolphin bear gerbil]
cmd>rh dolphin
Removed dolphin from queue
q = [bear gerbil]
cmd>rh bear
Removed bear from queue
q = [gerbil]
cmd>rh gerbil
Removed gerbil from queue
q = []
cmd>
Freeing queue
---     trace-01-ops    6/6
---     TOTAL           6/6

可以看出當 verbosity level 為 0 時只會印出分數，為 1 的時候會印出測試的項目，為 2 會印出執行的每一個指令，為 3 時則會將執行完每一個指令後的 queue 的內容一起印出。

處理完輸入的參數後， scripts/driver.py 接下來就會依此去執行 qtest ，讓 qtest 從 trace 資料夾中讀取相對應的 .cmd 檔來測試。














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.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

第 9 行的 subprocess.call() 是 python 中增加子行程的函式，可以直接執行外部程式並且加上執行時需要的命令列參數，直到外部程式結束後回傳 return code 。

觀察以上整段 runTrace() 後可以發現只有當 qtest 回傳的 retcode 等於 0 的時候，整個函式才有可能回傳 True，並且存在下面 run() 函式第 7 行的 ok 中。













def run(self, tid = 0):
    ...
    score = 0
    ...
    for t in tidList:
        ...
        ok = self.runTrace(t)
        maxval = self.maxScores[t]
        tval = maxval if ok else 0
        ...
        score += tval
        ...

又因為只有當 ok 為 True 時才能得到整題的分數 maxval ，我們可以推論是否能得到分數完全取決於 qtest 最後的回傳值是否等於 0 。

qtest 的行為與技巧

在 harness.h 中有以下的程式碼，將原本 C 語言定義的函式 malloc() 與 free() 重新定義到 test_malloc() 與 test_malloc() 。

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

其中 test_malloc() 會呼叫 fail_allocation() 這個函式，並依據當前的 malloc 失敗機率 fail_probability 決定這次配置記憶體是否成功。







/* Should this allocation fail? */
static bool fail_allocation()
{
    double weight = (double) random() / RAND_MAX;
    return (weight < 0.01 * fail_probability);
}

在 harness.c 中可以發現，實際上所有透過 test_malloc() 配置的記憶體會使用以下的資料結構存成一個 doubly-linked list。









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;

這裡的 payload[0] 是一個長度為零的陣列，放在 struct 的最後面，可以用來標示其後所接的記憶體的起始位置。















void *test_malloc(size_t size)
{
    ...
    block_ele_t *new_block =
        malloc(size + sizeof(block_ele_t) + sizeof(size_t));
    ...
    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);
    ...
    return p;
}

上面第四行的程式碼顯示，我們實際上配置的記憶體大小是由 block_ele_t 加上我們原本要配置的記憶體大小 size ，以及一個 footer 所組成。

因此我們以為用 malloc() 配置到的一整塊記憶體實際上是跟在一個 block_ele_t 的 struct 後面，並且最後還跟著一個 footer，而且從第十行程式碼可以看到 test_malloc() 回傳的指標 p 就是指向 payload 所在的位址。



















void test_free(void *p)
{
    ...
    block_ele_t *b = find_header(p);
    ...
    /* 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_malloc() 相對應的，使用 test_free() 時則會先呼叫 find_header() ，並且如以下的程式碼所示，減掉 block_ele_t 的大小來往前找到當初宣告記憶體的起始位址，之後會再對 doubly-linked list 的指標進行操作後，把整塊配置的記憶體釋放掉。








static block_ele_t *find_header(void *p)
{
    ...
    block_ele_t *b = (block_ele_t *) ((size_t) p - sizeof(block_ele_t));
    ...
    return b;
}
Last changed by 
 
蕭佑丞
0
348
Published on HackMD