contributed by < jason53415
>
commit 應切分為更小的 commit,每個 commit 都應該專注在小部份的修改
課程助教
queue_t
增加 list_ele_t *tail
指向 queue 的末端,以及 int size
記錄 queue 的大小。q_new
malloc()
配置記憶體,並且初始所有的變數。malloc()
失敗時要回傳 NULL
。q_free
q_insert_head
strcpy()
將字串內容複製過去。false
。next
先指向原本的 head
,再將 queue 的 head
指向這個節點。size
增加 1 ,並且回傳 true
。NULL
,尤其是配置字串的記憶體失敗時,還要記得把先前配置給節點的記憶體也釋放掉。q_insert_tail
tail
指向 queue 的末端,大致內容與 q_insert_head()
一樣,只是建立完節點之後要先讓原本的 tail->next
指向新增的節點,再讓 queue 的 tail
指向新節點。q_remove_head
false
。memset()
將 sp
的內容全部初始為 \0
後,在將 head
所指到的節點的字串使用 strncpy()
複製到 sp
,以避免超過 bufsize
。head
的位址,然後將 head
指向下一個節點後,把指標所指的節點的字串以及本身的記憶體釋放掉。size
減少 1 ,並且回傳 true
。q_size
size
的大小,所以除非 queue 本身沒有建立時要直接回傳 0 之外,都可以直接回傳 queue 中記錄的 size
。q_reverse
size
小於等於 1 時,就直接 return 。last
、 curr
、 next
指向三個連續的節點,來將 curr
中所指的下一個節點從 next
改為 last
,並且不斷將全部的指標移往下一個節點。head
及 tail
,讓指標正確指向 queue 的頭尾端。從 Makefile 中可以得知,執行 $ make test
時實際上就是執行 scripts/driver.py 這個程式。
透過執行 $ scripts/driver.py -h
可以看到有許多參數可以調整。
其中 TID 表示要使用哪一筆測試資料,預設的 TID 為 0 ,用來表示要使用所有的測試資料; verbosity level 則表示執行時所印出的訊息的多寡程度,以下利用了第一筆測試資料來實驗不同 verbosity level 的差異:
可以看出當 verbosity level 為 0 時只會印出分數,為 1 的時候會印出測試的項目,為 2 會印出執行的每一個指令,為 3 時則會將執行完每一個指令後的 queue 的內容一起印出。
處理完輸入的參數後, scripts/driver.py 接下來就會依此去執行 qtest ,讓 qtest 從 trace 資料夾中讀取相對應的 .cmd 檔來測試。
第 9 行的 subprocess.call()
是 python 中增加子行程的函式,可以直接執行外部程式並且加上執行時需要的命令列參數,直到外部程式結束後回傳 return code 。
觀察以上整段 runTrace()
後可以發現只有當 qtest 回傳的 retcode
等於 0
的時候,整個函式才有可能回傳 True
,並且存在下面 run()
函式第 7 行的 ok
中。
又因為只有當 ok
為 True
時才能得到整題的分數 maxval
,我們可以推論是否能得到分數完全取決於 qtest 最後的回傳值是否等於 0
。
在 harness.h 中有以下的程式碼,將原本 C 語言定義的函式 malloc()
與 free()
重新定義到 test_malloc()
與 test_malloc()
。
其中 test_malloc()
會呼叫 fail_allocation()
這個函式,並依據當前的 malloc 失敗機率 fail_probability
決定這次配置記憶體是否成功。
在 harness.c 中可以發現,實際上所有透過 test_malloc()
配置的記憶體會使用以下的資料結構存成一個 doubly-linked list。
這裡的 payload[0]
是一個長度為零的陣列,放在 struct 的最後面,可以用來標示其後所接的記憶體的起始位置。
上面第四行的程式碼顯示,我們實際上配置的記憶體大小是由 block_ele_t
加上我們原本要配置的記憶體大小 size
,以及一個 footer 所組成。
因此我們以為用 malloc()
配置到的一整塊記憶體實際上是跟在一個 block_ele_t
的 struct 後面,並且最後還跟著一個 footer,而且從第十行程式碼可以看到 test_malloc()
回傳的指標 p
就是指向 payload 所在的位址。
與 test_malloc()
相對應的,使用 test_free()
時則會先呼叫 find_header()
,並且如以下的程式碼所示,減掉 block_ele_t
的大小來往前找到當初宣告記憶體的起始位址,之後會再對 doubly-linked list 的指標進行操作後,把整塊配置的記憶體釋放掉。