2020q3 Homework1 (lab0)

contributed by < guyleaf >

環境

$ uname -a
Linux guyleaf-GS637RD 5.4.0-47-generic #51-Ubuntu SMP Fri Sep 4 19:50:52 UTC 2020 x86_64 x86_64 x86_64 GNU/Linux

$ gcc --version
gcc (Ubuntu 9.3.0-10ubuntu2) 9.3.0
Copyright (C) 2019 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 函式。
• 運用 Valgrind 排除 qtest 實作的記憶體錯誤，並透過 Massif 視覺化 “simulation” 過程中的記憶體使用量，需要設計對應的實驗
• 研讀論文 Dude, is my code constant time?，解釋本程式的 “simulation” 模式是如何透過以實驗而非理論分析，達到驗證時間複雜度，需要解釋 Student’s t-distribution 及程式實作的原理。

程式實做

詳細程式內容: Github

Macro

#define min(a, b) (a < b ? a : b)
#define IS_NULL_EMPTY(s) (!s)

新增兩個 macro

• min(a, b) 用於取最小值
• IS_NULL_EMPTY(s) 用於檢查指標為NULL或變數為0

Queue structure

typedef struct {
    list_ele_t *head; 
    list_ele_t *tail;
    int size;
} queue_t;

新增 tail 指標以及 list size

• tail: 指向 queue 的尾端，用於實現 insert_from_tail 時間複雜度為 O(1)
• size: 紀錄該 queue 的 list 個數，用於實現 q_size 時間複雜度為 O(1)

New queue

queue_t *q_new()
{
    queue_t *q = malloc(sizeof(queue_t));
    if (IS_NULL_EMPTY(q))
        return NULL;

    q->head = NULL;
    q->tail = NULL;
    q->size = 0;
    return q;
}

功能: 初始化 queue

特別注意，在分配記憶體空間後，需檢查是否有分配成功
有則回傳指標，沒有則回傳NULL

Free queue

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

    /* Free the list elements and the strings */
    list_ele_t *current = q->head;
    while (current) {
        q->head = current->next;
        free(current->value);
        current->value = NULL;
        current->next = NULL;
        free(current);
        current = q->head;
    }
    /* Free queue structure */
    q->size = 0;
    free(q);
}

功能: 釋放 queue 所有的記憶體空間

個人偏向釋放記憶體之前，先把變數內容全部歸零，清除敏感資料

Insert from head

bool q_insert_head(queue_t *q, char *s)
{
    if (IS_NULL_EMPTY(q))
        return false;

    list_ele_t *newh = NULL;
    newh = malloc(sizeof(list_ele_t));
    if (IS_NULL_EMPTY(newh))
        return false;

    /* allocate space and copy the string into it */
    newh->value = malloc(strlen(s) + 1);
    if (IS_NULL_EMPTY(newh->value)) {
        free(newh);
        return false;
    }
    memcpy(newh->value, s, strlen(s) + 1);
    newh->next = q->head;

    q->head = newh;
    if (IS_NULL_EMPTY(q->size))
        q->tail = newh;
    q->size++;
    return true;
}

功能: 新增一個 list node 並從 head 插入

• 特別注意，有用到 malloc 分配 heap 記憶體空間，記得都需要檢查是否分配成功
• 第二個 malloc 分配記憶體空間給 newh->value，如果分配失敗，回傳 false 前，記得釋放指標所指的記憶體空間

Insert from tail

bool q_insert_tail(queue_t *q, char *s)
{
    if (IS_NULL_EMPTY(q))
        return false;

    list_ele_t *newt = NULL;
    newt = malloc(sizeof(list_ele_t));
    if (IS_NULL_EMPTY(newt))
        return false;

    /* allocate space and copy the string into it */
    newt->value = malloc(strlen(s) + 1);
    if (IS_NULL_EMPTY(newt->value)) {
        free(newt);
        return false;
    }
    memcpy(newt->value, s, strlen(s) + 1);
    newt->next = NULL;

    if (IS_NULL_EMPTY(q->size))
        q->head = newt;
    else
        q->tail->next = newt;
    q->tail = newt;
    q->size++;
    return true;
}

功能: 新增一個 list node 並從 tail 插入

• 時間複雜度需為 O(1)
• 從 tail 插入時，記得更新原先 tail 的 next 指標，在實做過程中，造成無法找到後面的 node

Remove from head

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

    list_ele_t *oldh = q->head;
    q->head = q->head->next;

    if (!IS_NULL_EMPTY(sp)) {
        size_t length = min(strlen(oldh->value), bufsize - 1);
        memcpy(sp, oldh->value, length);
        sp[length] = '\0';
    }

    oldh->next = NULL;
    free(oldh->value);
    free(oldh);
    q->size--;

    if (IS_NULL_EMPTY(q->size))
        q->tail = NULL;
    return true;
}

功能: 移除 queue 的最前面 node

• 如果 sp 指標不為NULL ，需把該 node 所儲存的文字內容，複製到該指標內
• 特別注意，bufsize 需與原先儲存在 node 內的文字空間比較，取其中最小值，複製適當的字數至 sp 指標，避免 Segmentation Fault

Get queue's Size

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

功能: 取得該 queue 所擁有的 list node 數量

這裡也需要判斷 queue 是否為 NULL ，沒有則回傳0

Reverse queue

void q_reverse(queue_t *q)
{
    if (IS_NULL_EMPTY(q) || IS_NULL_EMPTY(q->size))
        return;

    list_ele_t *cursor = q->head, *prev = NULL;
    while (cursor) {
        list_ele_t *next = cursor->next;
        cursor->next = prev;
        prev = cursor;
        cursor = next;
    }

    q->tail = q->head;
    q->head = prev;
}

功能: 反轉在 queue 中所有的 list node

• 需注意，除了判斷 queue 是否為 NULL ，也需要判斷該 queue 中是否有 list node

if (IS_NULL_EMPTY(q) || IS_NULL_EMPTY(q->size))
        return;

Queue sort

/*
 * Merge two lists in ascending order
 * return head of list
 */
list_ele_t *merge(list_ele_t *a, list_ele_t *b)
{
    list_ele_t newh;
    list_ele_t *current, *head;
    newh.next = NULL;
    current = head = &newh;

    while (a && b) {
        int tmp = strcmp(a->value, b->value);
        if (tmp > 0) {
            current->next = b;
            current = current->next;
            b = b->next;
        } else {
            current->next = a;
            current = current->next;
            a = a->next;
        }
        current->next = NULL;
    }

    if (a)
        current->next = a;
    if (b)
        current->next = b;

    head = head->next;
    return head;
}

/*
 * Split list into two lists
 * return head of 2nd splited list
 */
list_ele_t *splitList(list_ele_t *head, size_t size)
{
    for (size_t halfSize = size / 2; halfSize > 1; halfSize--) {
        head = head->next;
    }

    list_ele_t *tmp = head;
    head = head->next;
    tmp->next = NULL;
    return head;
}

/*
 * Do merge sort algorithm
 * return head of sorted list
 */
list_ele_t *mergeSort(list_ele_t *head, size_t size)
{
    if (size <= 1)
        return head;

    list_ele_t *node = splitList(head, size);
    size_t halfSize = size / 2;
    return merge(mergeSort(head, halfSize), mergeSort(node, size - halfSize));
}

/*
 * 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 q_sort(queue_t *q)
{
    if (IS_NULL_EMPTY(q) || IS_NULL_EMPTY(q->size))
        return;

    q->head = mergeSort(q->head, q->size);

    list_ele_t *current = q->head;
    while (current->next) {
        current = current->next;
    }
    q->tail = current;
}

功能: 依 node 儲存的文字由小到大排列

• 參考 Linked list sort 之 merge sort 的寫法
• 時間複雜度為 O(n*logn)
• 實做時，卡在 merge 的部份，參考 Merge two sorted linked list 的 dummy node 的方式後解決

AddressSanitizer - global buffer overflow

使用 make SANITIZER=1 並 make test ，遇到 global buffer overflow ，發現是關於_Bool (C99 新增) 記憶體位址轉型為 int * 存取時所發生的錯誤

• sizeof(_Bool): 1 byte
• sizeof(int): 4 bytes

原先空間只有 1 byte 的 bool 型態 ，其記憶體位址轉型成 int *，並由 int *valp 所指向，造成 *valp 存取時比原先多讀取 3 bytes，直接存取記憶體中的其他資料，造成錯誤

情境模擬

假如使用以下程式碼進行測試，如果未開啟 AddressSanitizer ，正常情況下也很難察覺會有問題

#include <stdio.h>
#include <stdlib.h>

_Bool simulation = 0;

int main(void)
{
    int *test = (int *)&simulation; /* it's ok here to do type casting */
    int test2 = *test; /* global buffer overflow */
    printf("sizeof(bool): %ld, sizeof(int): %ld\n", sizeof(_Bool), sizeof(int));
    printf("bool: %d, int: %d\n", simulation, test2);
    return 0;
}

解決方法

1. 改變 struct PELE 之儲存方式，改由使用 void * 以及 type size

struct PELE {
    char *name;
    void *valp;
    size_t valp_size;
    char *documentation;
    /* Function that gets called whenever parameter changes */
    setter_function setter;
    param_ptr next;
};

2. 修改 add_param 之傳入參數，一樣改成傳入 void * 以及 type size

void add_param(char *name,
               void *valp,
               size_t valp_size,
               char *documentation,
               setter_function setter)
{
    param_ptr next_param = param_list;
    param_ptr *last_loc = &param_list;
    while (next_param && strcmp(name, next_param->name) > 0) {
        last_loc = &next_param->next;
        next_param = next_param->next;
    }

    param_ptr ele = (param_ptr) malloc_or_fail(sizeof(param_ele), "add_param");
    ele->name = name;
    ele->valp = valp;
    ele->valp_size = valp_size;
    ele->documentation = documentation;
    ele->setter = setter;
    ele->next = next_param;
    *last_loc = ele;
}

3. 新增 read_valp 和 write_valp function

• 依照 type size 判斷型態，日後也可新增其他型態
• write_valp 的 size 參數為 value 之大小

static int read_valp(void *valp, size_t size)
{
    if (size == sizeof(bool))
        return *(bool *) valp;
    else
        return *(int *) valp;
}

static bool write_valp(void *valp, void *value, size_t size)
{
    if (!valp || !value)
        return false;

    memcpy(valp, value, size);
    return true;
}

4. 原先有用到 param 的 function ，依原本功能比照修改對應程式碼

Valgrind - massif 視覺化記憶體用量

• 進入qtest初始化後，在 push_file function 會先allocate大約 9.9Kib 的空間給 rio_ptr 型態的 rnew ，如果輸入 ./qtest 時，沒有輸入 -f <input_file> ，就會改成讀取 stdin 的方式，再由 rio_ptr 型態的 buf_stack 指向 rnew ， 呼叫 readline function 讀取 buf_stack->fd 資料流，讀取 cmd 或 檔案中的指令

• 之後隨著指令執行插入、刪除，由下圖可知輸入 ih head 20 時，記憶體用量上升， 輸入 rhq 多次，可以看到記憶體用量以階梯式逐漸減少，最後輸入 free 時，直接下降到當初初始化完成後的用量，再輸入 new 時，圖表顯示微微上升，輸入 quit 結束程式並完全釋放

Dude, is my code constant time?

• TODO