2020q3 Homework1 (lab0)

contributed by < justapig9020 >

tags: sysprog2020

Outline

• 2020q3 Homework1 (lab0)
  • Outline
  • Link
  • 作業要求
  • 環境
  • lab0 實作
    • main structure
    • new
    • free
    • size
    • insert head
    • remove head
    • insert tail
    • reverse
    • half
    • sort
  • Valgrind 分析
    • qtest

Link

進階電腦系統理論與實作
lab-0
作業區

作業要求

• 在 GitHub 上 fork lab0-c
  • 參閱 Git 教學和 GitHub 設定指引 ^{附教學影片}
• 詳細閱讀 C Programming Lab ，依據指示著手修改 queue.[ch] 和連帶的檔案，測試後用 Git 管理各項修改，記得也該實作 q_sort 函式。
  • 在提交程式變更前，務必詳閱 如何寫好 Git Commit Message
  • 不用理會 Autolab 和檔案下載的描述，這兩者都是 CMU 專屬
• 除了修改程式，也要編輯「作業區」，增添開發紀錄和 GitHub 連結，除了提及你如何逐步達到自動評分程式的要求外，共筆也要涵蓋以下:
  • 運用 Valgrind 排除 qtest 實作的記憶體錯誤，並透過 Massif 視覺化 "simulation" 過程中的記憶體使用量，需要設計對應的

環境

~ uname -r
5.4.0-45-generic

~ 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.

lab0 實作

main structure

/* Linked list element (You shouldn't need to change this) */
typedef struct ELE {
    /* Pointer to array holding string.
     * This array needs to be explicitly allocated and freed
     */
    char *value;
    struct ELE *next;
} list_ele_t;

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

在結構部分，於 queue_t 中新增兩成員， tail 、 size 。
上述兩成員變數將會在後續用到的時候討論。

在使用 struct 的成員變數此一用詞時，突然發現自己只能肯定此用法在 cpp class 的狀況下正確，然而並不肯定可以使用於 c struct 的情況下。
既然有問題只好學學大文豪查字典了。

以下節錄自 c99 commit draft

a member of a structure, union, or enumeration
6.2.1
A structure or union shall not contain a member with incomplete or function type
6.7.2.1

由於與 staruct 相關章節中多次使用 member 一詞，因此認定

new

/*
 * Create empty queue.
 * Return NULL if could not allocate space.
 */
queue_t *q_new()
{
    queue_t *q = malloc(sizeof(queue_t));
    if (!q)
        return NULL;
    q->size = 0;
    q->head = NULL;
    q->tail = &q->head;
    return q;
}

本 function 實作只需考慮 queue malloc 失敗的情況。
根據 男人 ， On error, these functions return NULL. ， malloc 再失敗時會返回 NULL ，透過判斷回傳值來迴避失敗的情況。
其餘的部分依照題目需求來初始化數值，其中為了滿足 size 以及 insert tail O(1) 的要求，新增變數 size 、 tail ，兩者分別紀錄 queue 當前節點個數以及 指向最後一個節點的指標的指標 ，亦即指向倒數第二節點 next 成員的指標。
關於 tail 的設計思考，未來有時間再新增篇幅討論。

free

/* Free all storage used by queue */
void q_free(queue_t *q)
{
    if (!q)
        return;
    while (q->head) {
        list_ele_t *buf = q->head;
        q->head = buf->next;
        free(buf->value);
        buf->value = NULL;
        free(buf);
    }
    free(q);
}

依據理解以及與友人的討論得出 - 為避免資安上 uaf 以及 double free 的風險，被 free() 的指標應該被立即 assign 成 NULL 的結論。
然而在 free(q); 後加上 q = NULL; 則會導致 pre-commit 失敗。

queue.c:67:5: warning: Assignment of function parameter has no effect outside the function. Did you forget dereferencing it? [uselessAssignmentPtrArg]
    q = NULL;

首先檢查 q 是否存在，若存在則利用 q->head 作為 buffer 將整個 queue 從頭清空。
其中 list_ele_t 中的成員 value 是指向 char 的指標，須在 free 整個節點前先行將其 free 。

在實作此函數時重新思考了自己對 malloc 、 free 的認知。主要思考議題如下。

1. 若 malloc 嘗試分配 size 為 0 的空間時行為為何。
2. 若嘗試 free 上述空間時會發生什麼狀況。

根據男人敘述 If size is 0, then malloc() returns either NULL, or a unique pointer value that can later be successfully passed to free(). 可得知上述兩問題之解答。

1. Size 為 0 的 malloc 基本上會回傳 NULL。
2. 即便並非回傳 NULL ，這個回傳過後的位址依然可以被正常 free 。
   綜上所述，在 malloc 時需要考慮回傳為 NULL 的情況，以及在有可能 malloc size 為 0 的空間時，要注意不要在 size 為 0 的情況下讀寫該記憶體位址。

size

/*
 * Return number of elements in queue.
 * Return 0 if q is NULL or empty
 */
int q_size(queue_t *q)
{
    if (!q)
        return 0;
    return q->size;
}

透過在 queue_t 中新增成員變數 size 來紀錄當前結點個數，以達成 O(1) 之複雜度要求。
每逢新增刪除都需要對應的加減 size。

insert head

 static list_ele_t *new_ele(char *s)
{
    list_ele_t *newE = malloc(sizeof(list_ele_t));
    if (!newE)
        goto fail;
    size_t len = strlen(s) + 1;
    newE->value = malloc(len);
    if (!newE->value)
        goto freeEle;
    strncpy(newE->value, s, len);
    newE->next = NULL;
    return newE;

freeEle:
    free(newE);
    newE = NULL;
fail:
    return NULL;
}

首先考量之後還有其他 insert 系列 function 因此實作了一個靜態函數 new_ele 來提昇代碼的重用性。
判斷各個 malloc 的成功與否，並透過 goto 的方式構成一個類似於 try catch 的架構。實作此架構是為了確保任意的錯誤都能在返回前妥善的處理已經取用的資源。
此外需要注意的是，根據男人所述， The strlen() function calculates the length of the string pointed to by s, excluding the terminating null byte ('\0'). ， strlen 並不會包含 '\0' 因此在記憶體分配上需要將此數值加一以確保獲得的記憶體有足夠的空間保存 '\0' 。

/*
 * 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)
{
    list_ele_t *newh;
    if (!q)
        return false;

    newh = new_ele(s);
    if (!newh)
        return false;

    newh->next = q->head;
    q->head = newh;
    if (*q->tail == q->head)
        q->tail = &q->head->next;
    q->size += 1;
    return true;
}

透過 new_ele 函數生成新節點，透過回傳值判斷新節點是否有成功建立。
將新節點插入 queue 的 head ，並考慮當前 queue 為空時，要設定 tail 指向當前節點的成員變數 next 。

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->head)
        return false;

    list_ele_t *buf = q->head;
    if (&q->head->next == q->tail)
        q->tail = &q->head;
    q->head = q->head->next;
    q->size -= 1;

    if (sp) {
        strncpy(sp, buf->value, bufsize);
        sp[bufsize - 1] = '\0';
    }

    free(buf->value);
    buf->value = NULL;
    free(buf);
    return true;
}

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 *newE = new_ele(s);
    if (!newE)
        return false;

    *q->tail = newE;
    q->tail = &newE->next;

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

重複使用 new_ele 新增節點，由於 tail 為指向最後一個節點的 next 的指標，因此在 insert tail 的操作不用將 queue 為空時視為特殊狀況，可以直接更新。

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->head)
        return;

    list_ele_t *ptr = q->head;
    list_ele_t *prev = NULL;
    q->tail = &ptr->next;
    while (ptr) {
        list_ele_t *next = ptr->next;
        ptr->next = prev;
        prev = ptr;
        ptr = next;
    }
    q->head = prev;
}

使用 prev ptr next 三個指標進行節點反轉作業。
prev 用以保存前一個指標，在反轉後他將會成為 ptr 節點的 next。
ptr 指向當前操作的節點。
next 則指向原本的下一個節點，以確保 ptr 在其成員變數 next 更新後仍可以順利前往原本的下一節點。

half

static list_ele_t **find_mid_ele(list_ele_t **head)
{
    list_ele_t **faster = head;
    list_ele_t **slower = head;
    while (*faster && (*faster)->next) {
        slower = &(*slower)->next;
        faster = &(*faster)->next->next;
    }
    return slower;
}

void q_half(queue_t *q)
{
    if (!q || !q->head)
        return;

    list_ele_t **ptr = find_mid_ele(&q->head);
    printf("%s\n", (*ptr)->value);
}

首先再實作 sort 前，先實作 half 來找出 queue 的中間點 (實際上為

$n/2+1$ )。
藉由 2:1 的快慢指標找出 queue 的中間節點。
find_mid_ele 考量到後續操作實際上同時也需要改變

$n/2$ 的 next， 因此返回值為指標的指標。

sort

在實作時一度困惑於如何決定排序之順序，最後參考 ZhuMon 的開發紀錄才發現是使用 strcmp 作為排序依據。在文件上是否有需要對於排序依據有更清楚的指示？

Sort 的實現參考 linked list sort 使用 merge sort 作為排序演算法，並拆分成三個部分進行。

/*
 * 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.
 */
static list_ele_t *merge_sort(list_ele_t *head)
{
    if (!head || !head->next)
        return head;

    list_ele_t **ptr = find_mid_ele(&head);
    list_ele_t *mid = *ptr;
    *ptr = NULL;

    head = merge_sort(head);
    mid = merge_sort(mid);

    list_ele_t *mergered = NULL;
    ptr = &mergered;
    while (head && mid) {
        list_ele_t *smeller;
        if (strcmp(head->value, mid->value) > 0) {
            smeller = mid;
            mid = mid->next;
        } else {
            smeller = head;
            head = head->next;
        }
        *ptr = smeller;
        ptr = &(*ptr)->next;
    }

    while (head) {
        *ptr = head;
        head = head->next;
        ptr = &(*ptr)->next;
    }
    while (mid) {
        *ptr = mid;
        mid = mid->next;
        ptr = &(*ptr)->next;
    }
    *ptr = NULL;
    return mergered;
}

void q_sort(queue_t *q)
{
    if (!q || !q->head)
        return;

    q->head = merge_sort(q->head);
    while (*q->tail) {
        q->tail = &(*q->tail)->next;
    }
}

首先透過 find_mid_ele 找到指向中間節點的指標的指標。透鍋該指標可以便利的找出後半截 queue 的起始節點位址以及改動前半截 queue 的最後一個 next 為 NULL 以分割 queue 。
如同常規的 merge sort 藉由遞迴的方式將 queue 分割至最小單位，並依照大小逐一重組。

透過參考 ZhuMon 的實作，改進忽略 linked list 特性，而歷遍已經串好的串列。並且修復 tail 指向錯誤位址的 bug 。

Valgrind 分析

首先透過 Valgrind 逐一測試 trace 的測試腳本，發現以下腳本會發生警告。

1. 13

# Test performance of insert_tail
option fail 0
option malloc 0
new
ih dolphin 1000000
it gerbil 1000
reverse
it jaguar 1000

發生 memory leak 。

2. 14

# Test performance of size
option fail 0
option malloc 0
new
ih dolphin 1000000
size 1000

發生 memory leak 。

3. 15

# Test performance of insert_tail, size, reverse, and sort
option fail 0
option malloc 0
new
ih dolphin 1000000
it gerbil 1000000
size 1000
reverse
sort
size 1000

Valgrind 發生 core dumped 。

---

透過 masasif 產生 log 並藉由 massif-visualizer 視覺化，產生以下圖表(下圖為 trace-13 所產生的圖表)。

比對圖表與腳本後可以發現，在程式結束前，有大量的記憶體未被施放。而這歇腳本的共通點皆為未在最後執行 free 命令。
原本推測是 qtest 中並未在結束前檢查並施放記憶體，然而發現實際上在 main 裡就會透過 add_quit_helper 將 queue_quit (其中會引用 q_free() ) 存入 function pointer array quit_helpers ，最終在處理 quit 指令會依序執行 quit_helper 中的函數。

qtest