2020q3 Homework1 (lab0)

contributed by < Holychung >
2020q3 Homework1 (lab0) 題目

Outline

• 2020q3 Homework1 (lab0)
  • Outline
  • 開發環境
  • 作業要求
  • 開發過程
    • queue.h
    • queue.c
  • Valgrind
    • massif
    • massif-visualizer
    • 設計實驗
  • 研讀論文 Dude, is my code constant time?
  • linenoise
    • 強化 qtest 命令列功能
  • TODO

開發環境

$ uname -a
Linux holy-VirtualBox 5.4.0-47-generic #51~18.04.1-Ubuntu SMP Sat Sep 5 14:35:50 UTC 2020 x86_64 x86_64 x86_64 GNU/Linux

$ gcc --version
gcc (Ubuntu 7.5.0-3ubuntu1~18.04) 7.5.0
Copyright (C) 2017 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

作業要求

詳細閱讀 C Programming Lab ，依據指示著手修改 queue.[ch] 和連帶的檔案，測試後用 Git 管理各項修改，記得也該實作 q_sort 函式。

• q_new: 建立新的「空」佇列;
• q_free: 釋放佇列所佔用的記憶體;
• q_insert_head: 在佇列開頭 (head) 加入 (insert) 給定的新元素 (以 LIFO 準則);
• q_insert_tail: 在佇列尾端 (tail) 加入 (insert) 給定的新元素 (以 FIFO 準則);
• q_remove_head: 在佇列開頭 (head) 移除 (remove) 給定的元素。
• q_size: 計算佇列中的元素數量。
• q_reverse: 以反向順序重新排列鏈結串列，該函式不該配置或釋放任何鏈結串列元素，換言之，它只能重排已經存在的元素;
• q_sort: 以遞增順序來排序鏈結串列的元素，可參閱 Linked List Sort 得知實作手法;

開發過程

queue.h

要在

$O(1)$ 內完成 q_insert_tail 與 q_size 的話，必須在 queue_t 中加入 size 與 tail。

typedef struct ELE {
    char *value;
    struct ELE *next;
} list_ele_t;

/* Queue structure */
typedef struct {
    list_ele_t *head; /* Linked list of elements */
    list_ele_t *tail;
    int size;
} queue_t;

queue.c

q_new

• Create empty queue
• Return NULL if could not allocate space

queue_t *q_new()
{
    queue_t *q = malloc(sizeof(queue_t));
    /* TODO: What if malloc returned NULL? */
    if (!q)
        return NULL;
    q->head = NULL;
    q->tail = NULL;
    q->size = 0;
    return q;
}

q_free

• Free all storage used by queue

void q_free(queue_t *q)
{
    if (!q)
        return;

    list_ele_t *target = q->head;
    while (target) {
        q->head = target;
        target = target->next;
        free(q->head->value);
        free(q->head);
    }
    free(q);
}

q_insert_head

• Attempt to insert element at head of queue.
• Return true if successful.
• Return false if q is NULL or could not allocate space.
• Argument s points to the string to be stored.
• The function must explicitly allocate space and copy the string into it.

bool q_insert_head(queue_t *q, char *s)
{
    if (!q)
        return false;
    list_ele_t *new;
    new = malloc(sizeof(list_ele_t));
    if (!new)
        return false;
    /* Allocate space for the string and copy it */
    new->value = malloc(sizeof(char) * (strlen(s) + 1));
    if (new->value == NULL) {
        free(new);
        return false;
    }
    memset(new->value, '\0', strlen(s) + 1);
    strncpy(new->value, s, strlen(s));
    /* Insert element to head */
    new->next = q->head;
    q->head = new;
    if (q->tail == NULL)
        q->tail = new;

    q->size += 1;
    return true;
}

q_insert_tail

• Attempt to insert element at tail of queue.
• Return true if successful.
• Return false if q is NULL or could not allocate space.
• Argument s points to the string to be stored.
• The function must explicitly allocate space and copy the string into it.

bool q_insert_tail(queue_t *q, char *s)
{
    if (!q)
        return false;
    list_ele_t *new;
    new = malloc(sizeof(list_ele_t));
    if (!new)
        return false;
    /* Allocate space for the string and copy it */
    new->value = malloc(sizeof(char) * (strlen(s) + 1));
    if (new->value == NULL) {
        free(new);
        return false;
    }
    memset(new->value, '\0', strlen(s) + 1);
    strncpy(new->value, s, strlen(s));
    new->next = NULL;
    /* Insert element to tail */
    if (q->tail == NULL) {
        q->tail = new;
        q->head = new;
    } else {
        q->tail->next = new;
        q->tail = new;
    }

    q->size += 1;
    return true;
}

q_remove_head

• Attempt to remove element from head of queue.
• Return true if successful.
• Return false if queue is NULL or empty.
• If sp is non-NULL and an element is removed, copy the removed string to *sp
• (up to a maximum of bufsize-1 characters, plus a null terminator.)
• The space used by the list element and the string should be freed.

bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
    if (!q || q->size == 0)
        return false;

    /* Copy the removed string to *sp */
    if (sp) {
        size_t head_size = strlen(q->head->value);
        size_t size = head_size > bufsize - 1 ? bufsize - 1 : head_size;
        strncpy(sp, q->head->value, size);
        sp[size] = '\0';
    }

    /* Remove head element */
    list_ele_t *tmp = q->head;
    q->head = tmp->next;
    if (q->head == NULL) {
        /* Queue is empty after removing */
        q->tail = NULL;
    }
    free(tmp->value);
    free(tmp);

    q->size -= 1;
    return true;
}

q_size

• Return number of elements in queue.
• Return 0 if q is NULL or empty

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

q_reverse

• Reverse elements in queue
• No effect if q is NULL or empty
• This function should not allocate or free any list elements
• (e.g., by calling q_insert_head, q_insert_tail, or q_remove_head).
• It should rearrange the existing ones.

void q_reverse(queue_t *q)
{
    if (!q || q->size == 0 || q->size == 1)
        return;

    list_ele_t *prev_ele = NULL;
    list_ele_t *current_ele = q->head;
    list_ele_t *next_ele;
    q->tail = q->head;
    while (current_ele) {
        next_ele = current_ele->next;
        current_ele->next = prev_ele;
        prev_ele = current_ele;
        current_ele = next_ele;
    }
    q->head = prev_ele;
}

q_sort

為了達到時間複雜度

$O(NlogN)$，參考 Linked List Sort 使用 Merge Sort，排序的過程中把 q->head 指向最左邊的位置，排序完後也需額外尋找尾端來更新。

• Sort elements of queue in ascending order
• No effect if q is NULL or empty. In addition, if q has only one element, do nothing.

void merge_sort(list_ele_t **head)
{
    if (*head == NULL || (*head)->next == NULL)
        return;

    /* Partition */
    list_ele_t *slow = *head;
    list_ele_t *fast = (*head)->next;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
    }

    fast = slow->next;
    slow->next = NULL;
    slow = *head;

    merge_sort(&slow);
    merge_sort(&fast);

    /* Start merge elements of queue in ascending order */
    list_ele_t *prev;
    if (strcmp(slow->value, fast->value) < 0) {
        prev = slow;
        slow = slow->next;
    } else {
        prev = fast;
        fast = fast->next;
    }
    /* Find queue head */
    *head = prev;
    /* Merge elements of queue in ascending order */
    while (slow && fast) {
        if (strcmp(slow->value, fast->value) < 0) {
            prev->next = slow;
            prev = slow;
            slow = slow->next;
        } else {
            prev->next = fast;
            prev = fast;
            fast = fast->next;
        }
    }
    prev->next = slow ? slow : fast;
}

void q_sort(queue_t *q)
{
    if (!q || q->size == 0 || q->size == 1)
        return;

    merge_sort(&q->head);

    /* Find queue tail */
    while (q->tail->next)
        q->tail = q->tail->next;
}

Valgrind

使用 Valgrind 動態程式分析工具，對記憶體進行分析和除錯，使用方式如下。

$ valgrind --tool=<toolname> <program>

lab0 已整合 Valgrind 找出記憶體相關的問題，使用方式如下

$ make valgrind

程式輸出

# Explicitly disable sanitizer(s)
make clean SANITIZER=0 qtest
make[1]: Entering directory '/home/holy/linux2020/lab0-c'
.
.
scripts/driver.py -p /tmp/qtest.cduVEu --valgrind
---     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-16-perf:
# Test performance of sort with random and descending orders
# 10000: all correct sorting algorithms are expected pass
# 50000: sorting algorithms with O(n^2) time complexity are expected failed
# 100000: sorting algorithms with O(nlogn) time complexity are expected pass
---     trace-16-perf   6/6
+++ TESTING trace trace-17-complexity:
# Test if q_insert_tail and q_size is constant time complexity
Probably constant time
Probably constant time
---     trace-17-complexity     5/5
---     TOTAL           100/100

Test with specific case by running command:
scripts/driver.py -p /tmp/qtest.cduVEu --valgrind -t <tid>

massif

搭配記憶體分析工具 Massif 使用，Massif 是一個 heap profiler，可以追蹤程式使用 heap memory 的狀況，使用方式如下，更細節可以參考 User Manual 操作。

$ valgrind --tool=massif <program>

執行完後，當前目錄底下會出現 massif.out.<執行程式 PID>， 透過 ms_print 顯示分析結果。若程式有正確釋放記憶體，會看到最終記憶體使用量會回到 0。

$ ms_print massif.out.<執行程式 PID>

Massif starts by taking snapshots for every heap allocation/deallocation

然後 snapshots 又分三種：

• : Normal snapshot
• @ Detail snapshot
• # Peak snapshot

massif-visualizer

相比 ms_print，massif-visualizer 有圖形化的介面更方便分析，不過需要額外安裝

$ sudo apt-get install -y massif-visualizer

使用方式如下

$ massif-visualizer massif.out.<執行程式 PID>

設計實驗

假設在 q_free 當中忘記把 q->head->value 給釋放掉，就會造成 memory leak

void q_free(queue_t *q)
{
    if (!q)
        return;

    list_ele_t *target = q->head;
    while (target) {
        q->head = target;
        target = target->next;
-        free(q->head->value);
+        // free(q->head->value);
        free(q->head);
    }
    free(q);
}

$ valgrind --tool=massif ./qtest -f traces/trace-16-perf.cmd

可以明顯看出最後的記憶體沒有完全釋放掉，接下來使用 make valgrind 來觀察，可以看到很多記憶體 still reachable，代表程式結束時有未釋放的記憶體，不過卻還有指標指著。

+++ TESTING trace trace-16-perf:
# Test performance of sort with random and descending orders
# 10000: all correct sorting algorithms are expected pass
# 50000: sorting algorithms with O(n^2) time complexity are expected failed
# 100000: sorting algorithms with O(nlogn) time complexity are expected pass
ERROR: Freed queue, but 10000 blocks are still allocated
ERROR: Freed queue, but 60000 blocks are still allocated
ERROR: Freed queue, but 160000 blocks are still allocated
==29127== 4 bytes in 1 blocks are still reachable in loss record 1 of 29
==29127==    at 0x4C2FB0F: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==29127==    by 0x5277A29: strdup (strdup.c:42)
==29127==    by 0x10F285: linenoiseHistoryAdd (linenoise.c:1236)
==29127==    by 0x10FE3B: linenoiseHistoryLoad (linenoise.c:1325)
==29127==    by 0x10B48F: main (qtest.c:769)
==29127==
==29127== 32 bytes in 1 blocks are still reachable in loss record 2 of 29
==29127==    at 0x4C2FB0F: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==29127==    by 0x10BB12: malloc_or_fail (report.c:189)
==29127==    by 0x10C55A: add_cmd (console.c:127)
==29127==    by 0x10C63B: init_cmd (console.c:96)
==29127==    by 0x10B30C: main (qtest.c:762)
==29127==

研讀論文 Dude, is my code constant time?

論文閱讀：Dude, is my code constant time?

linenoise

參照 antirez/linenoise 改善 qtest 命令列。

研讀筆記 linenoise

強化 qtest 命令列功能

linenoise 的 API 相當的完善，可以直接應用到 qtest 當中，不過我 fork 作業的時候(9/18 以後)老師已經把 linenoise 整合 merge 進去，所以看到的 code 是已經整合過的>< 不過底下還是稍微提一下 trace 的過程。

先找到 qtest.c main function 裡面，找到 run_console 的地方，再到 console.c 看到這個函式，run_console 有呼叫到 readline 這個函式，把這邊替換成 linenoise 的 API。

while (!block_flag && read_ready()) {
    cmdline = readline();
    interpret_cmd(cmdline);
    prompt_flag = true;
}

while (!has_infile && !block_flag &&
       (cmdline = linenoise(prompt)) != NULL) {
    interpret_cmd(cmdline);
    prompt_flag = true;
    linenoiseFree(cmdline);
}

completion

一樣在啟動時要先註冊 callback function，然後這邊會用 cmd_list 去記下輸入過的 command，用 cmd_maybe 去跟現在 buf 的字串比對，如果比對相似就會呼叫 linenoiseAddCompletion。

history

這邊在一開始呼叫 linenoiseHistoryLoad 去讀實體的檔案 .cmd_history，再直接呼叫 linenoise 的 API，每次輸入指令後就加入 history 並且儲存到 HISTORY_FILE 當中。

#define HISTORY_FILE ".cmd_history"

bool run_console(char *infile_name)
{
    if (!push_file(infile_name)) {
        report(1, "ERROR: Could not open source file '%s'", infile_name);
        return false;
    }

    if (!has_infile) {
        char *cmdline;
        while ((cmdline = linenoise(prompt)) != NULL) {
            interpret_cmd(cmdline);
            linenoiseHistoryAdd(cmdline);       /* Add to the history. */
            linenoiseHistorySave(HISTORY_FILE); /* Save the history on disk. */
            linenoiseFree(cmdline);
        }
    } else {
        while (!cmd_done())
            cmd_select(0, NULL, NULL, NULL, NULL);
    }

    return err_cnt == 0;
}

TODO

TODO

• AddressSanitizer
• 指出現有程式的缺陷 (提示: 和 RIO 套件 有關)