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 顛倒過來,利用了三個指標 lastcurrnext 指向三個連續的節點,來將 curr 中所指的下一個節點從 next 改為 last ,並且不斷將全部的指標移往下一個節點。
    • 最後要交換 headtail ,讓指標正確指向 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 ...

又因為只有當 okTrue 時才能得到整題的分數 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; }