2020q1 Homework1 (lab0)

contributed by < amyhsieh16 >

tags: `linux2020`

開發環境

$ uname -a
Linux  4.15.0-88-generic #88-Ubuntu SMP Tue Feb 11 20:11:34 UTC 2020 x86_64 x86_64 x86_64 GNU/Linux

$ gcc --version
gcc (Ubuntu 7.4.0-1ubuntu1~18.04.1) 7.4.0

作業

說明

作業說明： lab0

作業要求

在 GitHub 上 fork lab0-c
詳細閱讀 C Programming Lab ，依據指示著手修改 queue.[ch] 和連帶的檔案
- 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:以遞增順序來排序鏈結串列的元素
修改排序所用的比較函式，變更為 natural sort，在 “simulation” 也該做對應的修改，得以反映出 natural sort 的使用。

開發過程

Define `queue_t`

為了使 q_size和 q_insert_tail在
$O (1)$ 條件下完成，新增
- size:紀錄 queue的元素數量
- tail:紀錄 queue最後一個元素的記憶體位置

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

`q_new`

用 malloc 動態配置記憶體
失敗後，回傳 NULL
成功後，則初始化 head及 tail為 NULL， size為 0

queue_t *q_new()
{
    queue_t *q = malloc(sizeof(queue_t));
    if (!q)
        return;
    
    q->head = NULL;
    q->tail = NULL;
    q->size = 0;
    return q;
}

`q_free`

queue 為 NULL時，不進行 free
先 free 每一個元素的結構，最後才 free 整個 queue

void q_free(queue_t *q)
{
    /* What should you do if the q is NULL? */
    if (!q)
        return;

    /* Free queue structure */
    while (q->head) {
        list_ele_t *tmp = q->head;
        q->head = q->head->next;
        free(tmp->value);
        free(tmp);
    }
    free(q);
}

`q_insert_head`

如果 q 是 NULL 或沒有配置動態記憶體，回傳 false
當使用 malloc 函數後，須確認是否成功，若否則須回傳 false
- 需確定要新增的型別，在使用malloc 時，需使用到sizeof(型別)*物件大小
從 queue 的 head 插入一個元素
- 設定元素的內容： value, next與記憶體位置
- 考量到 CREN 的安全建議，棄置 strcpy而使用 strncpy
- 當插入元素後， queue的 size, tail的設定

bool q_insert_head(queue_t *q, char *s)
{
    /* What should you do if the q is NULL? */
    if (!q) 
        return false;

    /* allocate space for list_ele_t */
    list_ele_t *newh;
    newh = malloc(sizeof(list_ele_t));
    if (!newh) 
        return false;

    /* allocate space for the string and copy it */
    newh->value = malloc(strlen(s) + 1);
    if (!newh->value) {
        free(newh);
        return false;
    }
    memset(newh->value, '\0', strlen(s) + 1);
    strncpy(newh->value, s, strlen(s));

    newh->next = q->head;
    q->head = newh;
    q->tail = q->size ? q->tail : newh;
    q->size++;
    return true;
}

查閱malloc ，可知在使用malloc 設定記憶體大小時，需sizeof(型別)相乘物件大小

@@ -58,7 +58,7 @@ bool q_insert_head(queue_t *q, char *s)
         return false;
 
     /* allocate space for the string and copy it */
-    newh->value = malloc(sizeof(char) * (strlen(s) + 1));
+    newh->value = malloc(strlen(s) + 1);
     if (!newh->value) {

`q_insert_tail`

如果 q 是 NULL 或沒有配置動態記憶體，回傳 false
當使用 malloc 函數後，須確認是否成功，若否則須回傳 false
從 queue的 tail 插入一個元素
- 設定元素的內容： value, next 與記憶體位置
- 因為 CREN，不使用 strcpy而使用 strncpy
- 當插入元素後， queue的 size, head的設定
時間複雜度為
$O (1)$

bool q_insert_tail(queue_t *q, char *s)
{
        /* What should you do if the q is NULL? */
    if (!q) 
        return false;

    /* allocate space for list_ele_t */
    list_ele_t *newt;
    newt = malloc(sizeof(list_ele_t));
    if (!newt) 
        return false;

    /* allocate space for the string and copy it */
    newt->value = malloc(strlen(s) + 1);
    if (!newt->value) {
        free(newt);
        return false;
    }
    memset(newt->value, '\0', strlen(s) + 1);
    strncpy(newt->value, s, strlen(s));
    newt->next = NULL;

    q->tail->next = newt;
    q->tail = newt;
    q->head = q->size ? q->head : newt;
    q->size++;
    return true;
}

查閱malloc ，可知在使用malloc 設定記憶體大小時，需sizeof(型別)相乘物件大小

@@ -93,8 +93,7 @@ bool q_insert_tail(queue_t *q, char *s)
         return false;
 
     /* allocate space for the string and copy it */
-
-    newt->value = malloc(sizeof(char) * (strlen(s) + 1));
+    newt->value = malloc(strlen(s) + 1);
     if (!newt->value) {
         free(newt);
         return false;

`q_remove_head`

當 queue 是 NULL 或 empty 時，回傳 false
複製 head 的 value到 sp
移除 head

bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
    /* if queue is NULL or empty */
    if (!q || !q->size) 
        return false;
    
    list_ele_t *tmp = q->head;
    /* copy the removed string to *sp */
    if (sp) {
        memset(sp, '\0', bufsize);
        strncpy(sp, tmp->value, bufsize-1);
    }

    q->head = q->head->next;
    if (!q->head) 
        q->tail = q->head;
    
    q->size--;

    /* Free all storage used by q->head */
    free(tmp->value);
    free(tmp);
    return true;
}

`q_size`

回傳 queue的元素數量
queue為 NULL或為 empty時，回傳0
時間複雜度為
$O (1)$

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

`q_reverse`

當 queue是 NULL或 empty時，不進行 reverse
從 head開始，改變其 next的位置
宣告三個變數
- curr: 要修改的元素
- prev: 下一個要修改的元素
- tmp: 暫存 prev->next
  把原本 curr->prev->tmp ，改成 prev->curr

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

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

考慮以下的修改:

@@ -1,14 +1,13 @@
 void q_reverse(queue_t *q)
 {
-    if (!q || !q->size) {
+    if (!q || !q->size)
         return;
-    }
 
-    list_ele_t *curr = q->head, *prev = curr->next, *tmp = NULL;
+    list_ele_t *curr = q->head, *prev = curr->next;
     q->tail = curr;
     q->tail->next = NULL;
     while (prev) {
-        tmp = prev->next;
+        list_ele_t *tmp = prev->next;
         prev->next = curr;
         curr = prev;
         prev = tmp;

要點:

更精簡的排版，在 { ... } 裡頭只有 return 或變數指派的話，可縮減 { 和 } 的使用;
縮減變數 tmp 的 scope，不僅視覺上更清晰，而且日後引入 foreach 巨集 (Linux 核心原始程式碼的風格) 時，會更容易;

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

amyhsieh16已修正
1. commit ac17c81
2. commit 7b414e6

`q_sort`

參考 Linked List Sort
Approach 1: 使用 Bubble Sort，會出現 Time limit exceeded
因為 Bubble Sort 的時間複雜度為
$O (n^{2})$ ，而本作業所要求的時間複雜度為
$O (n l o g (n))$ ，所以需要使用Approach 2的Merge Sort

你需要解釋，為何會超時？

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

Approach 2: 使用 Merge Sort

藉由 quiz1 的參考題解 1與 divide and conquer 的觀念
用 recursive 手段實作 merge 函式時，在 trace-15-perf 一項中沒有得分，利用 $ make valgrind發現 stack overflow

==5065== Stack overflow in thread #1: can't grow stack to 0x1ffe801000
==5065== Stack overflow in thread #1: can't實做 grow stack to 0x1ffe801000
==5065== Can't extend stack to 0x1ffe8010a8 during signal delivery for thread 1:
==5065==   no stack segment
==5065== 
==5065== Process terminating with default action of signal 11 (SIGSEGV)
==5065==  Access not within mapped region at address 0x1FFE8010A8
==5065== Stack overflow in thread #1: can't grow stack to 0x1ffe801000
==5065==    at 0x10CE89: merge (queue.c:240)

改用 iteration手段實作 merge函式

Approach 1

void q_sort(queue_t *q)
{
    /* No effect if q is NULL or empty.*/
    if (!q || !q->head) 
        return;

    list_ele_t *head, *tail;
    head = q->head;
    tail = q->tail;

    while (head != tail) {
        list_ele_t *curr, *prev;
        curr = head;
        prev = head;
        while (curr != tail) {
            if (strncmp(curr->value, curr->next->value, 10) > 0 ) {
                list_ele_t *tmp = curr->next;
                if (curr != head) {
                    prev->next = tmp;
                } else {
                    head = tmp;
                }
                curr->next = tmp->next;
                tmp->next = curr;
                prev = tmp;
                if (tail == tmp) {
                    tail = curr;
                }
            } else {
                prev = curr;
                curr = curr->next;
            }
            if (!curr->next) 
                q->tail = curr;
        }
        tail = prev;
    }
    q->head = head;
}

Approach 2

list_ele_t *merge(list_ele_t *left, list_ele_t *right) {
    if (!left) 
        return right;
    if (!right) 
        return left;
    
    if (strcmp(left->value, right->value) > 0) {
        right->next = merge(left, right->next);
        return right;
    } else {
        left->next = merge(left->next, right);
        return left;
    }
}

list_ele_t *mergesort (list_ele_t *head)
{
    if (!head || !head->next) return head;

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

    slow = mergesort(head);
    fast = mergesort(fast);
    return merge(slow, fast);
}


void q_sort(queue_t *q)
{
    /* No effect if q is NULL or empty.*/
    if (!q || !q->head) {
        return;
    }
    
    q->tail = q->head = mergesort(q->head);
    
    while (q->tail->next) {
        q->tail = q->tail->next;
    }    
}

縮減上述程式碼:

用 for 迴圈改寫原本的 while 敘述，這樣之後可用 foreach 巨集改寫，而且會更清晰;
merge 和 mergesort 都以遞迴實作，但其實可減少遞迴次數;

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

amyhsieh16 1. 已修改，請參閱commit 83a3277

改用 for迴圈實作 merge函式

list_ele_t *merge(list_ele_t *left, list_ele_t *right)
{
    if (!left)
        return right;
    if (!right)
        return left;

    list_ele_t *head, *merge;
    for (merge = NULL; right || left;) {
        if (!right) {
            merge->next = left;
            break;
        } else if (!left) {
            merge->next = right;
            break;
        }

        if (strcmp(left->value, right->value) > 0) {
            if (!merge) {
                head = merge = right;
            } else {
                merge->next = right;
                merge = merge->next;
            }
            right = right->next;
        } else {
            if (!merge) {
                head = merge = left;
            } else {
                merge->next = left;
                merge = merge->next;
            }
            left = left->next;
        }
    }

    return head;
}

記憶體檢測

使用 $ make SANITIZER=1

+++ TESTING trace trace-17-complexity:
# Test if q_insert_tail and q_size is constant time complexity
=================================================================
==7506==ERROR: AddressSanitizer: global-buffer-overflow on address 0x5645f93159c0 at pc 0x5645f910686e bp 0x7ffd16b6c920 sp 0x7ffd16b6c910
READ of size 4 at 0x5645f93159c0 thread T0
    #0 0x5645f910686d in do_option_cmd linux2020/lab0-c/console.c:368
    #1 0x5645f910548a in interpret_cmda linux2020/lab0-c/console.c:220
    #2 0x5645f9105e8e in interpret_cmd linux2020/lab0-c/console.c:243
    #3 0x5645f9106b77 in cmd_select linux2020/lab0-c/console.c:569
    #4 0x5645f9106f94 in run_console linux2020/lab0-c/console.c:628
    #5 0x5645f91040ad in main linux2020/lab0-c/qtest.c:772
    #6 0x7f8f9df4fb96 in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x21b96)
    #7 0x5645f9101809 in _start (/home/amy/linux2020/lab0-c/qtest+0x6809)

0x5645f93159c1 is located 0 bytes to the right of global variable 'simulation' defined in 'console.c:20:6' (0x5645f93159c0) of size 1
  'simulation' is ascii string ''
SUMMARY: AddressSanitizer: global-buffer-overflow linux2020/lab0-c/console.c:368 in do_option_cmd
Shadow bytes around the buggy address:
  0x0ac93f25aae0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x0ac93f25aaf0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x0ac93f25ab00: 00 00 00 00 00 00 00 00 00 00 00 00 f9 f9 f9 f9
  0x0ac93f25ab10: 00 f9 f9 f9 f9 f9 f9 f9 00 f9 f9 f9 f9 f9 f9 f9
  0x0ac93f25ab20: 00 f9 f9 f9 f9 f9 f9 f9 00 f9 f9 f9 f9 f9 f9 f9
=>0x0ac93f25ab30: 00 f9 f9 f9 f9 f9 f9 f9[01]f9 f9 f9 f9 f9 f9 f9
  0x0ac93f25ab40: 00 00 00 00 01 f9 f9 f9 f9 f9 f9 f9 04 f9 f9 f9
  0x0ac93f25ab50: f9 f9 f9 f9 00 00 00 00 00 00 00 00 00 00 00 00
  0x0ac93f25ab60: 00 00 00 00 00 00 00 00 00 00 00 00 00 f9 f9 f9
  0x0ac93f25ab70: f9 f9 f9 f9 01 f9 f9 f9 f9 f9 f9 f9 01 f9 f9 f9
  0x0ac93f25ab80: f9 f9 f9 f9 04 f9 f9 f9 f9 f9 f9 f9 00 f9 f9 f9
Shadow byte legend (one shadow byte represents 8 application bytes):
  Addressable:           00
  Partially addressable: 01 02 03 04 05 06 07 
  Heap left redzone:       fa
  Freed heap region:       fd
  Stack left redzone:      f1
  Stack mid redzone:       f2
  Stack right redzone:     f3
  Stack after return:      f5
  Stack use after scope:   f8
  Global redzone:          f9
  Global init order:       f6
  Poisoned by user:        f7
  Container overflow:      fc
  Array cookie:            ac
  Intra object redzone:    bb
  ASan internal:           fe
  Left alloca redzone:     ca
  Right alloca redzone:    cb
==7506==ABORTING
---	trace-17-complexity	0/5

Natural Sort

修改排序所用的比較函式，變更為 natural sort，在 “simulation” 也該做對應的修改，得以反映出 natural sort 的使用。

Valgrind

運用 Valgrind 排除 qtest 實作的記憶體錯誤，Massif 視覺化 “simulation” 過程中的記憶體使用量，需要設計對應的實驗

參考資料

C99 規格書

2020q1 Homework1 (lab0)

tags: linux2020

開發環境

作業

說明

作業要求

開發過程

Define queue_t

q_new

q_free

q_insert_head

q_insert_tail

q_remove_head

q_size

q_reverse

q_sort

記憶體檢測

Natural Sort

Valgrind

參考資料

Read more

2020q3 Homework1 (lab0)

tags: `linux2020`

Define `queue_t`

`q_new`

`q_free`

`q_insert_head`

`q_insert_tail`

`q_remove_head`

`q_size`

`q_reverse`

`q_sort`