2020q1 Homework1 (lab0)

contributed by < rest5387 >

作業要求

作業說明

修改 queue.[ch] 並實作 q_sort 函式
基本需求

• q_new : 新增空的 queue
• q_free : 清除整個 queue
• q_insert_head : 以 FIFO 方式新增元素
• q_insert_tail : 以 FILO 方式新增元素（須為 constant time)
• q_remove_head : 移除 queue 開頭元素
• q_size : 計算 queue 的所含元素個數（須為 constant time)
• q_sort : 將 queue 中元素，依遞增順序作排序

實作流程

q_insert_head

基本上根據註解實作，不過若節點本身 malloc 成功，但字串所需空間 malloc 失敗的話，除了要回傳 false 之外，還需要釋放掉剛剛配置成功的節點空間，以防止記憶體洩漏（memory leak) 的問題發生。

bool q_insert_head(queue_t *q, char *s)
{
    list_ele_t *newh;
    /* TODO: What should you do if the q is NULL? */
    if (!q)
        return false;
    else {
        newh = malloc(sizeof(list_ele_t));
        /* Don't forget to allocate space for the string and copy it */
        /* What if either call to malloc returns NULL? */
        if (!newh)
            return false;
        int buff_size = strlen(s) + 1;
        newh->value = (char *) malloc(sizeof(char) * buff_size);
        if (!newh->value) {
            free(newh);
            return false;
        }
        memset(newh->value, '\0', buff_size);
        strncpy(newh->value, s, buff_size - 1);
        newh->next = q->head;
        q->head = newh;
        if (q->size == 0)
            q->tail = newh;
        ++q->size;
        return true;
    }
}

q_remove_head

先判斷 q 是否為 NULL ，若是則回傳 false ，若否則用 list_ele_t *tmp 指向當前 head node ，再將 queue 中的 head pointer 往後更新一位。依據 sp 是否為 NULL 設定 ret 值並判斷是否該複製 node 中的 value 。

「大致上依據註解來實作」這句話不需要多提，你應該論述你的手段和後續改進的方向，作為工程討論和精進的題材。

jserv

此部份已更正

rest5387

bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
    if (!q || q->size == 0)
        return false;
    list_ele_t *tmp = q->head;
    q->head = q->head->next;
    bool ret = false;
    if (sp) {
        memset(sp, '\0', bufsize);
        strncpy(sp, tmp->value, bufsize - 1);
        ret = true;
    }

    free(tmp->value);
    free(tmp);
    --q->size;
    return ret;
}

考慮到以下變更:

@@ -1,22 +1,19 @@
 bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
 {
-    if (!q)
-        return false;
-    if (q->size == 0)
+    if (!q || !q->size)
         return false;
+
     list_ele_t *tmp = q->head;
     q->head = q->head->next;
+    bool ret = false;
     if (sp) {
         memset(sp, '\0', bufsize);
         strncpy(sp, tmp->value, bufsize - 1);
-        free(tmp->value);
-        free(tmp);
-        --q->size;
-        return true;
-    } else {
-        free(tmp->value);
-        free(tmp);
-        --q->size;
-        return false;
+        ret = true;
     }
+
+    free(tmp->value);
+    free(tmp);
+    --q->size;
+    return ret;
 }

要點:

1. 將前兩次的 if 合併為一行敘述;
2. 避免重複的資源釋放和佇列空間調整的程式碼;

jserv

此部份已更正

rest5387

q_reverse

大致上以註解上的需求實作

void q_reverse(queue_t *q)
{
    if (q) {
        if (q->size == 2) {
            list_ele_t *tmp = q->head;
            q->tail->next = q->head;
            q->head->next = NULL;
            q->head = q->tail;
            q->tail = tmp;
        } else if (q->size > 2) {
            list_ele_t *tmp1, *tmp2, *tmp3;
            tmp1 = q->head;
            tmp2 = tmp1->next;
            tmp3 = tmp2->next;
            q->head->next = NULL;
            while (tmp3 != q->tail) {
                tmp2->next = tmp1;
                tmp1 = tmp2;
                tmp2 = tmp3;
                tmp3 = tmp3->next;
            }
            tmp2->next = tmp1;
            tmp3->next = tmp2;
            tmp1 = q->head;  // swap q->head and q->tail
            q->head = q->tail;
            q->tail = tmp1;
        }
    }
}

q_sort

merge

因為使用遞迴方式實作 merge 的話，在執行 trace 15 的測試時，將會發生 stack overflow ，所以改用迴圈的方式實作。

list_ele_t *merge(list_ele_t *l1, list_ele_t *l2)
{
    if (!l2)
        return l1;
    if (!l1)
        return l2;

    list_ele_t *head, *tmp;
    if (strcmp(l1->value, l2->value) <= 0) {
        head = l1;
        tmp = l1;
        l1 = l1->next;
    } else {
        head = l2;
        tmp = l2;
        l2 = l2->next;
    }

    while (l1 || l2) {
        if (l1 && l2) {
            if (strcmp(l1->value, l2->value) <= 0) {
                tmp->next = l1;
                l1 = l1->next;
            } else {
                tmp->next = l2;
                l2 = l2->next;
            }
            tmp = tmp->next;
        } else if (l1 && !l2) {
            tmp->next = l1;
            break;
        } else if (!l1 && l2) {
            tmp->next = l2;
            break;
        }
    }

    return head;
}

merge_sort

static list_ele_t *merge_sort_list(list_ele_t *head)
{
    if (!head || !head->next) {
        return head;
    }
    list_ele_t *fast = head->next;
    list_ele_t *slow = head;
    while (fast && fast->next) {
        fast = fast->next->next;
        slow = slow->next;
    }
    fast = slow->next;
    slow->next = NULL;

    list_ele_t *l1, *l2;
    l1 = merge_sort_list(head);
    l2 = merge_sort_list(fast);
    return merge(l1, l2);
}

merge_sort_list 這個函式沒有必要揭露 (exposed，即 visibility 為公開)，在宣告加上 static，表示僅在本 compilation unit 範疇可見。這樣也有助於編譯器施加最佳化。

jserv

此部份已更正

rest5387

q_sort

void q_sort(queue_t *q)
{
    if (q && q->size > 1) {
        q->head = merge_sort_list(q->head);
        list_ele_t *tmp = q->head;
        while (tmp->next) {
            tmp = tmp->next;
        }
        q->tail = tmp;
    }
}

減少程式縮排的深度 (depth)，可改為:

if (q && q->size > 1) { ... }

jserv

此部份已更正

rest5387

使用 valgrind 排除 qtest 的記憶體錯誤

運用 massif 工具繪製視覺化 “simulation” 過程中的記憶體使用量

在使用 massif 工具前，須先到 .valgrindrc 中刪除 –show-leak-find=full 這項指令，在執行

$ valgrind --tool=massif ./qtest -f <file_name>

或是直接執行

$ valgrind --tool=massif ./qtest

再手動輸入想對 queue 做的實驗操作指令

當執行完結束程式後， massif 會輸出名為 massif.out.<num_id> 的檔案。

這時輸入下令指令，開啟 massif visualizer 將輸出檔繪製成圖。

$ massif-visualizer massif.out.<num_id>

此時可得如下圖：(此圖為執行 trace-16-perf.cmd 的輸出檔案)

由上可見，因 trace-16 中最後有 free 命令，且 test_malloc 記憶體用量在最後歸為 0 。可知在此測試檔下，應該沒有 memery leak 的情形發生。

Dude, is my code constant time?

在 Dude, is my code constant time? 中提出一種以實驗而非理論分析的方法驗證程式是否為常數時間複雜度。

根據文中所述，此方法是利用對 execution time 進行 time leakage detection 來驗證。

簡單來說，可分為以下兩個步驟：

• 對兩組不同的 input data 量測其 execution time
• 比較兩者的時間分佈，是否有差異

對兩組不同的 input data 量測其 execution time

1. Class definition: 因採用的 time leakage detection 方法為 fix-vs-random test ，故 input 會有固定與隨機的兩種資料。其中隨機的第二種 iuput 會在每次測量時隨機的選取出。
2. Cycle counters: CPU 上提供的 cycle counter

比較兩者的時間分佈，是否有差異

經過測量得出的數據在此時還不能直接使用來比較，須再經過ㄧ些後製處理 (post-processing)

如：cropping: 因典型的時間分佈為 positively skewed distribution ，但這可能是因為測量錯誤 (measurement artifacts) 而導致的結果，比如interrupted by OS 或是其他外來行為導致。因此需要將這些不適的測量做剪枝。

圖片取自：維基百科

在經過後處理後，將運用統計檢定 (statical test) 去否定虛無假設 (null hypothesis)

統計檢定: 採用 t-test
虛無假設： the two timing distributions are equal

t-test ： 可用來估計呈常態分布且變異數未知的總體的平均值，以此來判斷兩種 input 資料的時間分佈是否相同

dudect 工具實作原理

觀察 dudect/constant.c 中的 measure 函式

void measure(int64_t *before_ticks,
             int64_t *after_ticks,
             uint8_t *input_data,
             int mode)
{
    assert(mode == test_insert_tail || mode == test_size);
    if (mode == test_insert_tail) {
        for (size_t i = drop_size; i < number_measurements - drop_size; i++) {
            char *s = get_random_string();
            dut_new();
            dut_insert_head(
                get_random_string(),
                *(uint16_t *) (input_data + i * chunk_size) % 10000);
            before_ticks[i] = cpucycles();
            dut_insert_tail(s, 1);
            after_ticks[i] = cpucycles();
            dut_free();
        }
    } else {
        for (size_t i = drop_size; i < number_measurements - drop_size; i++) {
            dut_new();
            dut_insert_head(
                get_random_string(),
                *(uint16_t *) (input_data + i * chunk_size) % 10000);
            before_ticks[i] = cpucycles();
            dut_size(1);
            after_ticks[i] = cpucycles();
            dut_free();
        }
    }
}

可見到當 mode 為 test_insert_tail 或 test_size 時，將藉由呼叫 cpucycles() ，將每次進行欲測試的函式前後的 cpucycle 存入 array 中，以此得出 execution time。

cpucycles()的實作可見同目錄中的 cpucycles.h

"directory" 的翻譯叫做「目錄」，絕非「檔案夾」，請以 UNIX 術語為主

jserv

#include <stdint.h>
// http://www.intel.com/content/www/us/en/embedded/training/ia-32-ia-64-benchmark-code-execution-paper.html
static inline int64_t cpucycles(void)
{
#if defined(__i386__) || defined(__x86_64__)
    unsigned int hi, lo;
    __asm__ volatile("rdtsc\n\t" : "=a"(lo), "=d"(hi));
    return ((int64_t) lo) | (((int64_t) hi) << 32);
#else
#error Unsupported Architecture
#endif
}