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_ele 的 struct ，用來紀錄各個 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() ，其中將 SIGSEGV 及 SIGALRM 兩個訊號各利用 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
Last changed by 
 
Iris Wu
0
349
Published on HackMD