Try   HackMD

2019q1 Homework1 (lab0)

contributed by < Rispolyv0n >

認真看作業要求,除了提及如何逐步達到要求,還需要進行:

  1. 改善程式效能
  2. 解釋自動評分系統運作的原理
  3. 提及 qtest 的行為和裡頭的技巧

還未達成符合預期目標,請繼續付出!

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →
jserv

題目要求

根據C Programming Lab in CMU,此作業需修改 queue.c, queue.h 兩個檔案,實作以下七個函式:

  • q_new() : 建立一個新的空佇列
  • q_free() : 清空一個佇列所用到的空間
  • q_insert_head() : 試圖在佇列頭端插入一個節點 (用於LIFO)
  • q_insert_tail() : 試圖在佇列尾端插入一個節點 (用於FIFO)
  • q_remove_head() : 試圖刪除佇列頭端的第一個節點
  • q_size() : 計算佇列所含的節點數量
  • q_reverse() : 將佇列中的節點做倒序,並且不得 free 或 allocate 佇列中的節點,只能做重新排列。

不能對佇列中所儲存的字串長度設上限。
q_insert_tail()q_size() 兩個函式需為

O(1)
測試檔會測試超過 1,000,000 個節點的佇列,作業分數會利用15個 trace 檔做計算(自動評分系統)。

程式說明

queue.h

作業要求 q_insert_tail()q_size() 兩個函式需為

O(1) ,因此修改 struct queue_t 如下 (註解標示處):

typedef struct { list_ele_t *head; unsigned int size; // 新增此field用來紀錄 queue size list_ele_t *tail; // 新增此field用來紀錄 tail element 的位置 } queue_t;

queue.c

有了以上的結構,就可以在必要的地方對 queue.h 中所定義的各個 field 做適當的操作,如下 (註解標示處):

q_new() 第 5 ~ 7 行將 structure 中 各 field 初始化,包括將 q->head, q->tail 初始化為 NULL, 以及將 q->size 初始化為 0 :

queue_t *q_new() { queue_t *q = malloc(sizeof(queue_t)); if (q) { q->head = NULL; // 新增 queue 時將 q->head, q->tail 初始化為 NULL q->size = 0; // 將 q->size 初始化為 0 q->tail = NULL; } return q; }

q_insert_head() 第 14 ~ 17 行,在確定插入節點時將 q->size 加 1, 並調整 q->tail :

bool q_insert_head(queue_t *q, char *s) { if (q) { list_ele_t *newh; newh = malloc(sizeof(list_ele_t)); if (newh) { newh->value = (char *) malloc((strlen(s) + 1) * sizeof(char)); if (newh->value) { memset(newh->value, '\0', strlen(s) + 1); strcpy(newh->value, s); newh->next = q->head; q->head = newh; q->size += 1; // insert 新節點時,將 q->size 加 1 if (q->size == 1) { // 若新增的節點為第一個節點,則 q->tail 也需指向此節點 q->tail = newh; } return true; } free(newh); } } return false; }

q_remove_head() 第 12 ~ 14 行,在確定移除節點時將 q->size 減 1, 並調整 q->tail :

bool q_remove_head(queue_t *q, char *sp, size_t bufsize) { if (q && q->size > 0) { if (sp) { strncpy(sp, q->head->value, bufsize - 1); sp[bufsize - 1] = '\0'; } list_ele_t *tmp = q->head; q->head = q->head->next; free(tmp->value); free(tmp); q->size -= 1; // 移除節點時將 q->size 減 1 if (q->size == 0) // 若移除節點後, queue 為空,則需將 q->tail 變為 NULL q->tail = NULL; return true; } return false; }

有了以上適當的操作後,即可將 q_insert_tail()q_size() 兩個函式修改為如下,以達到

O(1)

q_insert_tail() 中可直接找到 queue 的 tail 位置,對其插入節點,不用從頭遍歷整個 queue ,因此執行時間就不會受 queue 長度影響:

bool q_insert_tail(queue_t *q, char *s) { if (q) { list_ele_t *newh; // newh 為即將被 insert 的新節點 newh = malloc(sizeof(list_ele_t)); if (newh) { newh->value = (char *) malloc((strlen(s) + 1) * sizeof(char)); if (newh->value) { memset(newh->value, '\0', strlen(s) + 1); strcpy(newh->value, s); newh->next = NULL; if (q->tail) // 若 q->tail 已指向某節點,則將該節點的 next 指向新節點 newh q->tail->next = newh; else // 若 q->tail 尚未指向任何節點,表示此時 queue 中無任何節點,因此也需要將 q->head 指向新節點 newh q->head = newh; q->tail = newh; // 直接將 q->tail 指到新的 element 上,不用每次都從 q->head 走過整個 linked-list 直到尾端 q->size += 1; return true; } free(newh); } } return false; }

q_size() 函式中可直接 return structure queue_t 中的 field size ,不用每次都遍歷 queue 中所有節點,邊計算節點數,因此執行時間就不會受 queue 長度影響:

int q_size(queue_t *q) { if (q) { return q->size; } return 0; }

自動評分系統運作原理

啟動評分系統

執行 $make test 時,會去呼叫 scripts/driver.py ,而 scripts/driver.py 中紀錄著所有測試檔的檔名 (traceDict) 及測試檔所在的資料夾位置 (traceDirectory)。若執行時無特別指定測試檔編號,則會依序利用所有 traceDict 中的測試檔做測試。可於 runTrace() 函式中看到利用 subprocess.call() 執行了 $./qtest ,同時指定用某測試檔去做測試。 (如以下程式碼的第 7, 9 行) :

# in scripts/driver.py 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

執行測試檔內容

首先 console.h 中定義了 cmd_elestruct ,用來紀錄各個 command 及其相關資訊。如下:

// in console.h typedef struct CELE cmd_ele, *cmd_ptr; struct CELE { char *name; // command 名稱 cmd_function operation; // 要執行的 function char *documentation; // command 描述 cmd_ptr next; // 指向下一個 cmd_ele };

qtest.c 的 main() 中呼叫 init_cmd()console_init() 定義了各種 command 、有關 command 的描述、以及讀取該 command 後要呼叫的函式,並將這些 command element 用 console.c 中的 add_cmd() 以 linked list 的方式紀錄於 cmd_list 。如下:

// in console.c void add_cmd(char *name, cmd_function operation, char *documentation) { cmd_ptr next_cmd = cmd_list; cmd_ptr *last_loc = &cmd_list; while (next_cmd && strcmp(name, next_cmd->name) > 0) { last_loc = &next_cmd->next; next_cmd = next_cmd->next; } cmd_ptr ele = (cmd_ptr) malloc_or_fail(sizeof(cmd_ele), "add_cmd"); ele->name = name; ele->operation = operation; ele->documentation = documentation; ele->next = next_cmd; *last_loc = ele; }

而測試檔中所寫的就是這些 command ,qtest.c 中的 run_console() 會去一行行讀取測試檔中的 command ,並在 interpret_cmda() 中從 cmd_list 找到對應的 cmd_ele ,呼叫對應函式。

錯誤處理

qtest.c 中的 main() 接完參數後,會呼叫 queue_init() ,其中將 SIGSEGVSIGALRM 兩個訊號各利用 signal() 設定了各自的 signal handler ,以便處理「 access 到不合法的記憶體」與「超時操作」兩種情況,如下:

// in qtest.c static void queue_init() { fail_count = 0; q = NULL; signal(SIGSEGV, sigsegvhandler); signal(SIGALRM, sigalrmhandler); }

而兩個 signal handler 中皆會傳各自的 message 給 harness.c 中的 trigger_exception() 。其中 jmp_ready 為一 volatile 變量,是為了防止編譯器完全根據程式碼中的上下文去優化,導致執行時的值可能與實際上 jmp_ready 記憶體中的值不一樣而產生不可預期的執行結果,這樣可以強迫編譯器每次用到 jmp_ready 時都要乖乖的去記憶體中重新讀取它當下的值。此處為了防止讀取 jmp_ready 值時,值又被意外更動的可能,用了 type sig_atomic_t ,確保讀取的動作不會被中斷。

// in harness.c static volatile sig_atomic_t jmp_ready = false; void trigger_exception(char *msg) { error_occurred = true; error_message = msg; if (jmp_ready) siglongjmp(env, 1); else exit(1); }

由以上程式碼可知,當 jmp_ready 為真時,就跳到上次做 sigsetjump() 時所存的 env 下。而 sigsetjump() 會在每次讀取新 command 時要呼叫大家自己實作的函式前,在 exception_setup() 中被呼叫,因此若執行自己實作的函式時發生「超時操作」與「 access 到不合法的記憶體」兩種情況,即可回溯記憶體環境至執行自己實作的函式前,並且跳過已知執行後會出錯的函式,結束整個執行 command 的包裝函式。

linux man page 可知若是從 siglongjmp() 返回,則 segsetjump() 會返回非零,因此 exception_setup() 中即可對「初始程式回溯點」與「console指令函式後續操作發生錯誤而啟動 trigger_exception() 返回回溯點」兩種情況做對應處理。

jmp_ready 的值在準備要呼叫大家自己寫的 queue.c 中的 function 前會被設為 true ,若安全執行完沒有出錯,或者中途執行時出錯了返回程式回溯點,都會將 jmp_ready 設回 false

// in harness.c 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; } }

由以上程式碼可知,若為「初始程式回溯點」,則 exception_setup() 會返回 true 。而若為「 console 指令函式後續操作發生錯誤而啟動 trigger_exception() 返回回溯點」,則 exception_setup() 會返回 false 。因此只要像其它 console 指令函式一樣,將可能引起錯誤的程式碼片段用 if (exception_setup()) 包起來,第一次執行時,初始程式回溯點完,就會繼續執行 if 中有風險的程式碼。萬一執行過程中發生錯誤,就會跳回到 if (exception_setup()) ,這時 exception_setup() 會返回 false ,即可安全的跳過會引起錯誤的程式碼,繼續完成 console 指令函式。以下拿 do_new() 函式為範例:

// in qtest.c bool do_new(int argc, char *argv[]) { if (argc != 1) { report(1, "%s takes no arguments", argv[0]); return false; } bool ok = true; if (q != NULL) { report(3, "Freeing old queue"); ok = do_free(argc, argv); } error_check(); if (exception_setup(true)) // 此處設下程式回溯點 q = q_new(); // 此行呼叫大家自己寫的可能引起錯誤的 q_new() 函式,若出錯則會返回273行,且excpetion_setup()返回零,因此整個 if 中的程式碼會被跳過,直接執行下一行的 exception_cancel() exception_cancel(); qcnt = 0; show_queue(3); return ok && !error_check(); }

其它筆記

"volatile" qualifier

1498 114) A volatile declaration may be used to describe an object corresponding to a memory-mapped input/output port or an object accessed by an asynchronously interrupting function.
—— The New C Standard

被宣告 volatile 的變數,會防止編譯器根據程式碼上下文對該變數做過度優化。以下為一編譯器優化後卻導致非預期的執行結果範例:

uint32 status = 0; while (status == 0) { /* * 假設變數status並沒有在此迴圈中的程式碼被更新, * 而我們實際上期待變數status會在迴圈進行到某個階段時 * 被其它不同步的線程或硬體更新後即跳出迴圈 */ }

則以上程式碼可能因編譯器不知道變數 status 的值可能意外被改變,只根據程式碼判定變數 status 從頭到尾並未被更動,因此直接將迴圈改為一個無限迴圈如 while(1) ,減少訪問變數 status 值的次數,以達到優化目的。而這樣的編譯結果卻與我們所預期的不一樣,導致執行結果錯誤。因此我們需要 volatile 這個 qualifier,去防止編譯器過度優化,每次都去重新讀取變數 status 的值。

被宣告為 volatile 的變數代表它可能有著以下特性:

  • Memory-mapped peripheral registers (硬體可直接讀寫的已定義的記憶體位址)
  • Global variables modified by an interrupt service routine (會被中斷處理機制所更改的全域變數)
  • Global variables within a multi-threaded application (多線程應用中通用的全域變數)

也就是此變數的值可能被硬體更新,或者被其它同時執行中的線程更新,不是完全根據當下執行中程式碼上下文的操作去做更動。讓編譯器知道變數具有這樣的特性,編譯器就不會對被宣告為 volatile 的變數做過度的優化了。

參考

TO-DO

  • valgrind
  • popen.returncode