2018q3 Homework2(lab0)

contributed by <datuiji>

實驗環境

NAME="Ubuntu" VERSION="16.04.5 LTS (Xenial Xerus)" ID=ubuntu ID_LIKE=debian PRETTY_NAME="Ubuntu 16.04.5 LTS" VERSION_ID="16.04" HOME_URL="http://www.ubuntu.com/" SUPPORT_URL="http://help.ubuntu.com/" BUG_REPORT_URL="http://bugs.launchpad.net/ubuntu/" VERSION_CODENAME=xenial UBUNTU_CODENAME=xenial

實驗結果

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

開發紀錄

queue.h

/* Queue structure */ typedef struct { list_ele_t *head; /* Linked list of elements */ list_ele_t *tail; int size; /* You will need to add more fields to this structure to efficiently implement q_size and q_insert_tail */ } queue_t;
  • 在queue.h中,新增了 tail 指標與 int size,新增 tail 指標原因是為了紀錄 queue 的 tail ,如此才能實做 bool q_queue_tail(queue_t *q,char *s) 在 O(1) 時間內,而新增 int size 是因為能夠實做 int q_size(queue_t *q) 在 O(1) 時間內。

queue_t *q_new()

queue_t *q_new() { queue_t *q = malloc(sizeof(queue_t)); /* What if malloc returned NULL? */ if (q == NULL) { return NULL; } else { q->head = NULL; q->tail = NULL; q->size = 0; return q; } }
  • 此處因為做了 malloc 所以必須考慮到 malloc 是否成功,如果失敗則回傳 NULL 。

q_free()

void q_free(queue_t *q) { /* How about freeing the list elements and the strings? */ if (q == NULL) { return; } else { while (q->head) { list_ele_t *temp = q->head; free(temp->value); q->head = q->head->next; free(temp); } }
  • 在這個函式中,功能為刪除整個 queue ,所以需要拜訪完整個 queue 並 free 節點與它的數值。

bool q_insert_head(queue_t *q, char *s)

bool q_insert_head(queue_t *q, char *s) { /* What should you do if the q is NULL? */ if (q == NULL) { return false; } else { /* Don't forget to allocate space for the string and copy it */ /* What if either call to malloc returns NULL? */ list_ele_t *newh; newh = malloc(sizeof(list_ele_t)); if (newh == NULL) { return false; } else { newh->value = malloc(sizeof(char) * (strlen(s) + 1)); if (newh->value == NULL) { free(newh); return false; } strcpy(newh->value, s); if (q->head == NULL) { q->head = newh; q->tail = newh; newh->next = NULL; } else { newh->next = q->head; q->head = newh; } q->size++; return true; } } }
  • 實作邏輯為:
    • 先 malloc 記憶體給欲插入節點的數值,之後判斷 malloc 是否成功,再來將新節點的數值 s 複製給剛 malloc 的記憶體空間,之後移動指標,如果插入 queue 還沒有節點,就把新節點設為 head 與 tail 否則將新節點加入 queue 中,並移動指標。
  • 在處理這函式的時候一開使用的是 strdup 。
bool q_insert_head(queue_t *q, char *s) { /* What should you do if the q is NULL? */ if(q == NULL){ return false; } else{ /* Don't forget to allocate space for the string and copy it */ /* What if either call to malloc returns NULL? */ list_ele_t *newh; newh = malloc(sizeof(list_ele_t)); if(newh == NULL){ return false; } else{ newh->value = strdup(s); if(q->head == NULL){ q->head = newh; q->tail = newh; newh->next = NULL; } else{ newh->next = q->head; q->head = newh; } q->size++; return true; } } }
  • 導致以下錯誤:
+++ TESTING trace trace-01-ops: # Test of insert_head and remove_head ERROR: Attempted to free unallocated block. Address = 0xc56500 ERROR: Attempted to free unallocated or corrupted block. Address = 0xc56500 ERROR: Segmentation fault occurred. You dereferenced a NULL or invalid pointer ERROR: Removal from queue failed (1 failures total) ERROR: Attempted to free unallocated block. Address = 0xc56520 ERROR: Attempted to free unallocated or corrupted block. Address = 0xc56520 ERROR: Corruption detected in block with address 0xc56520 when attempting to free it ERROR: Segmentation fault occurred. You dereferenced a NULL or invalid pointer ERROR: Removal from queue failed (2 failures total) ERROR: Attempted to free unallocated block. Address = 0xc56560 ERROR: Attempted to free unallocated or corrupted block. Address = 0xc56560 ERROR: Corruption detected in block with address 0xc56560 when attempting to free it ERROR: Segmentation fault occurred. You dereferenced a NULL or invalid pointer ERROR: Removal from queue failed (3 failures total) --- trace-01-ops 0/6
  • 在函式中用了 strdup 所以 free 時造成以上錯誤,這邊不能使用 strdup 原因是因為原本使用 strdup 是用了原本 c 語言定義的 malloc 與 free,而在這個 harness.h 中已經把 malloc 重新定義為 *test_malloc 而 free 重新定義為 test_free 。

bool q_insert_tail(queue_t *q, char *s)

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 == NULL) { return false; } else { list_ele_t *newh; newh = malloc(sizeof(list_ele_t)); if (newh == NULL) { return false; } else { newh->value = malloc(sizeof(char) * (strlen(s) + 1)); if (newh->value == NULL) { free(newh); return false; } strcpy(newh->value, s); if (q->head == NULL) { q->head = newh; q->tail = newh; newh->next = NULL; } else { q->tail->next = newh; q->tail = newh; newh->next = NULL; } q->size++; return true; } } }
  • 在實作 insert_tail 這個函式沒什麼問題,因為邏輯跟insert_head差不多。

bool q_remove_head(queue_t *q, char *sp, size_t bufsize)

bool q_remove_head(queue_t *q, char *sp, size_t bufsize) { /* You need to fix up this code. */ if (q == NULL || q->size == 0) { return false; } else { list_ele_t *temp = q->head; q->head = q->head->next; if (sp != NULL) { memset(sp, '\0', bufsize); strncpy(sp, temp->value, bufsize - 1); } free(temp->value); free(temp); q->size--; if (q->size == 0) { q->tail = NULL; } return true; } }
  • 實作邏輯為:先判斷 queue 是否有節點,如果沒有節點做 remove head 就會回傳失敗,否則先宣告一個暫存節點,把欲刪除節點的數值存到 sp 中,之後陸續把欲刪除節點之數值與節點本身 free 掉。
  • 在實作 remove head 時,我一開始用了下列方法:
bool q_remove_head(queue_t *q, char *sp, size_t bufsize) { /* You need to fix up this code. */ if(q == NULL || q->size == 0){ return false; } else{ list_ele_t *temp = q->head; if(temp->value != NULL){ strncpy(sp, temp->value, bufsize); free(temp->value); } q->head = q->head->next; free(temp); q->size--; if(q->size == 0){ q->tail = NULL; } return true; } }
  • 造成以下錯誤:
+++ TESTING trace trace-06-string: # Test of truncated strings ERROR: Removed value meerkat_panda_squirrel_vulture_XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX != expected value meerkat_panda_squirrel_vulture ERROR: Removed value aardvark_bear_dolphin_gerbil_XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX != expected value aardvark_bear_dolphin_gerbil ERROR: Removed value aardvark_bear_dolphin_XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX != expected value aardvark_bear_dolphin ERROR: Removed value meerkat_panda_squirrel_XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX != expected value meerkat_panda_squirrel ERROR: Removed value meerkat_XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX != expected value meerkat Error limit exceeded. Stopping command execution --- trace-06-string 0/7
  • 後來找到在 if(temp->value != NULL) 這個判斷時出錯,因為改用 if (sp != NULL) 邏輯才合理,且以下動作改成 memset 先初始化 sp 為 '\0' 然後在用 strncpy 將節點數值複製到 sp ,最後把節點數值跟節點本身 free 掉,這樣就成功了。

int q_size(queue_t *q)

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 == NULL) { return 0; } else { return q->size; } }
  • 因為在前面的函式中都有紀錄 q->size 所以在此函式中就只需要回傳 q->size。

void q_reverse(queue_t *q)

void q_reverse(queue_t *q) { /* You need to write the code for this function */ if (q == NULL || q->size == 0) { return; } list_ele_t *pre = NULL; list_ele_t *cur = q->head; list_ele_t *next = NULL; while (cur != NULL) { next = cur->next; cur->next = pre; pre = cur; cur = next; } q->tail = q->head; q->head = pre; return; }

自動評分系統運作的原理

CC = gcc CFLAGS = -O0 -g -Wall -Werror GIT_HOOKS := .git/hooks/applied all: $(GIT_HOOKS) qtest $(GIT_HOOKS): @scripts/install-git-hooks @echo queue.o: queue.c queue.h harness.h $(CC) $(CFLAGS) -c queue.c qtest: qtest.c report.c console.c harness.c queue.o $(CC) $(CFLAGS) -o qtest qtest.c report.c console.c harness.c queue.o test: qtest scripts/driver.py scripts/driver.py clean: rm -f *.o *~ qtest rm -rf *.dSYM (cd traces; rm -f *~)
  • 在 Makefile 中發現當執行 make test 時會執行 scripts/driver.py 所以只要知道 driver.py 的功能就知道自動評分系統如何運作。
  • driver.py
#!/usr/bin/python import subprocess import sys import getopt # Driver program for C programming exercise class Tracer: traceDirectory = "./traces" qtest = "./qtest" verbLevel = 0 autograde = 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" } traceProbs = { 1 : "Trace-01", 2 : "Trace-02", 3 : "Trace-03", 4 : "Trace-04", 5 : "Trace-05", 6 : "Trace-06", 7 : "Trace-07", 8 : "Trace-08", 9 : "Trace-09", 10 : "Trace-10", 11 : "Trace-11", 12 : "Trace-12", 13 : "Trace-13", 14 : "Trace-14", 15 : "Trace-15" } maxScores = [0, 6, 6, 6, 6, 6, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7] def __init__(self, qtest = "", verbLevel = 0, autograde = False): if qtest != "": self.qtest = qtest self.verbLevel = verbLevel self.autograde = autograde 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 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 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)) if self.autograde: # Generate JSON string jstring = '{"scores": {' first = True for k in scoreDict.keys(): if not first: jstring += ', ' first = False jstring += '"%s" : %d' % (self.traceProbs[k], scoreDict[k]) jstring += '}}' print(jstring) def usage(name): print("Usage: %s [-h] [-p PROG] [-t TID] [-v VLEVEL]" % name) print(" -h Print this message") print(" -p PROG Program to test") print(" -t TID Trace ID to test") print(" -v VLEVEL Set verbosity level (0-3)") sys.exit(0) def run(name, args): prog = "" tid = 0 vlevel = 1 levelFixed = False autograde = False optlist, args = getopt.getopt(args, 'hp:t:v:A') for (opt, val) in optlist: if opt == '-h': usage(name) elif opt == '-p': prog = val elif opt == '-t': tid = int(val) elif opt == '-v': vlevel = int(val) levelFixed = True elif opt == '-A': autograde = True else: print("Unrecognized option '%s'" % opt) usage(name) if not levelFixed and autograde: vlevel = 0 t = Tracer(qtest = prog, verbLevel = vlevel, autograde = autograde) t.run(tid) if __name__ == "__main__": run(sys.argv[0], sys.argv[1:])
  • 當在 command line 輸入 make test 就會開始執行 run 函式執行自動測試,另外還有一個功能就是可以獨立測試15個 trace 。

qtest 的行為和裡頭的技巧

  • 當我們輸入 ./qtest 時,command line 會出現 cmd ,此時就可以開始輸入測資開始測試,所以我很好奇這項功能如何工作。打開 qtest.c 可以看見 static void console_init() 這個函式主要是讓我們能輸入測資進行測試,但在 qtest.c 中我找不到 add_cmd 的函式,於是我 google 一下發現這是運用 GDB 的技巧,透過此項功能可以讓我們更容易去除錯。
2.5. Adding Commands to GDB As noted in Section 2.2, GDB's command handling is extensible. Commands are grouped into a number of command lists (of type struct cmd_list_element), pointed to by a number of global variables (defined in cli-cmds.h). Of these, cmdlist is the list of all defined commands, with separate lists defined for sub-commands of various top level commands. For example infolist is the list of all info sub-commands. Each command (or sub-command) is associated with a callback function which implements the behavior of the functions. There are additional requirements for functions which set or show values within GDB. Each function also takes a documentation string (used by the help command). Functions for adding commands all return a pointer to the struct cmd_list_element for the command added (which is not necessarily the head of its command list). The most useful functions are: add_cmd. Add a function to a command list. add_com. Add a function to the main command list, cmdlist. This is a convenience wrapper for add_cmd. add_prefix_cmd. Add a new prefix command. This command should have its own function for use if it is called on its own, and a global command list pointer specific to the prefix command to which all its sub-commands will be added. If a prefix command is called with an unknown sub-command, it can either give an error or call the function of the prefix command itself. Which of these is used is specified by a flag in the call to add_prefix_cmd. add_alias_cmd. Add an alias for a command already defined. add_info. Add a sub-command to the info. A convenience wrapper for add_cmd. New commands are usually added in the _initialize_arch function after the struct gdbarch has been defined.
static void console_init() { add_cmd("new", do_new, " | Create new queue"); add_cmd("free", do_free, " | Delete queue"); add_cmd("ih", do_insert_head, " str [n] | Insert string str at head of queue n times " "(default: n == 1)"); add_cmd("it", do_insert_tail, " str [n] | Insert string str at tail of queue n times " "(default: n == 1)"); add_cmd("rh", do_remove_head, " [str] | Remove from head of queue. Optionally compare " "to expected value str"); add_cmd( "rhq", do_remove_head_quiet, " | Remove from head of queue without reporting value."); add_cmd("reverse", do_reverse, " | Reverse queue"); add_cmd("size", do_size, " [n] | Compute queue size n times (default: n == 1)"); add_cmd("show", do_show, " | Show queue contents"); add_param("length", &string_length, "Maximum length of displayed string", NULL); add_param("malloc", &fail_probability, "Malloc failure probability percent", NULL); add_param("fail", &fail_limit, "Number of times allow queue operations to return false", NULL); }

參考資料

Select a repo