Try   HackMD

2020q3 Homework1 (lab0)

contributed by <hsiehong>

tags: 進階電腦系統理論與實作

作業要求

outline

實做queue.c以下功能

  • 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 得知實作手法;

開發紀錄

q_new

queue_t *q_new() { queue_t *q = malloc(sizeof(queue_t)); if (q == NULL) return NULL; q->size = 0; q->head = NULL; q->tail = NULL; return q; }
  • 若 malloc failed ,return NULL pointer
  • 初始化 queue

q_free

void q_free(queue_t *q) { if (q == NULL) return; while (q->head) { list_ele_t *tmp; tmp = q->head; q->head = q->head->next; if (tmp->value) free(tmp->value); free(tmp); } free(q); }
  • 很直覺的方法,要注意每個 node 的 value 也要釋放記憶體

q_insert_head

bool q_insert_head(queue_t *q, char *s) { if (!q) return false; list_ele_t *newh; newh = malloc(sizeof(list_ele_t)); if (newh == NULL) { free(newh); return false; } int len = strlen(s) + 1; newh->value = (char *) malloc(len * sizeof(char)); if (!newh->value) { free(newh); return false; } strncpy(newh->value, s, len); newh->next = q->head; q->head = newh; if (!q->tail) q->tail = newh; ++q->size; return true; }
  • 若 queue is NULL , 無法新增,回傳 NULL , 若 queue is empty , 更新 q->head , q->tail , q->size

  • newh->value 要注意是新增 strlen(s) + 1 的大小,要保留 \0 的空間

  • 依據 CERN Common vulnerabilities guide for C programmers 建議而移除 strcpy 等不安全的函式 , 這裡使用strncpy()

  • line20 原本是要處理 q->size == 0 的情況,後來覺得讀性不是很好,所以改成下面

if (q->size == 0) {
        q->head = newt;
    } else {
        q->tail->next = newt;
    }
q->tail = newt;

不懂 line 15,為什麼不是 free(newh->value) , 測資會過不了

q_insert_tail

bool q_insert_tail(queue_t *q, char *s) { if (!q) return false; list_ele_t *newt; newt = malloc(sizeof(list_ele_t)); if (!newt) { free(newt); return false; } size_t len = strlen(s) + 1; newt->value = (char *) malloc(len * sizeof(char)); if (!newt->value) { free(newt); return false; } strncpy(newt->value, s, len); newt->next = NULL; if (!q->tail) { q->head = newt; } else q->tail->next = newt; q->tail = newt; ++q->size; return true; }
  • 概念同 q_insert_head,換湯不換藥
  • 同樣處理 q->size == 0 的特殊狀況且增加可讀性,line19-23 改成下面
if (q->size == 0) {
        q->head = newt;
    } else {
        q->tail->next = newt;
    }
q->tail = newt;

q_remove_head

bool q_remove_head(queue_t *q, char *sp, size_t bufsize) { if (!q || !q->head) return false; if (q->head->value) strncpy(sp, q->head->value, bufsize); list_ele_t *tmp = q->head; q->head = q->head->next; free(tmp->value); free(tmp); --q->size; return true; }
  • 移除當前 head node 並更新 head node,q->size - 1
  • 若 head node value 不為空,將值複製到 *sp

q_size

int q_size(queue_t *q) { if (q != NULL) return q->size; else return 0; }

q_reverse

void q_reverse(queue_t *q) { if (!q || !q->head) return; list_ele_t *curr, *pre, *nxt; curr = q->head; pre = NULL; q->head = q->tail; q->tail = curr; while (curr) { nxt = curr->next; curr->next = pre; pre = curr; curr = nxt; } }
  • 參考文章作法
  • 若 queue 為 NULL 或 empty 不用動作

q_sort

void q_sort(queue_t *q) { if (!q || q->size == 1) return; list_ele_t *curr, *pre, *tmp, *tail; tail = NULL; while (q->head != q->tail) { curr = pre = q->head; while (curr && curr->next && curr->next != tail) { if (strcmp(curr->value, curr->next->value) > 0) { tmp = curr->next; curr->next = tmp->next; tmp->next = curr; if (curr == q->head) { q->head = tmp; pre = tmp; } else { pre->next = tmp; pre = pre->next; } } else { if (curr != q->head) pre = pre->next; curr = curr->next; } } tail = curr; } }
  • 參考 文章 作法,這裡選擇 bubble sort,不過不意外測資全過不了 (TLE) QQ

依據上面程式碼第一次跑完的成績,有排序的部份都沒過
--- TOTAL 71/100


改成 merge sort,也是參考上篇文章作法

list_ele_t *merge_2_list(list_ele_t *l1, list_ele_t *l2) { list_ele_t *n_head = NULL; list_ele_t **tmp = &n_head; while (l1 && l2) { if (strcmp(l1->value, l2->value) > 0) { *tmp = l2; l2 = l2->next; } else { *tmp = l1; l1 = l1->next; } tmp = &((*tmp)->next); } if (l1) *tmp = l1; else *tmp = l2; return n_head; }
  • 參考 ZhuMo 同學的,使用到 pointer to pointer
list_ele_t *merge_sort(list_ele_t *head) { if (!head || !head->next) return head; list_ele_t *fast, *slow; fast = head->next; slow = head; // split list into 2 half list while (fast && fast->next) { fast = fast->next->next; slow = slow->next; } fast = slow->next; slow->next = NULL; slow = head; list_ele_t *left = merge_sort(slow); list_ele_t *right = merge_sort(fast); return merge_2_list(left, right); }
void q_sort(queue_t *q) { if (!q || q->size <= 1) return; // sorting by merge sort q->head = merge_sort(q->head); q->tail = q->head; while (q->tail && q->tail->next) q->tail = q->tail->next; }
  • 排序完得更新新的 q->tail
  • 大多數測資都能通過 --- TOTAL 94/100

Valgrind 記憶體分析

執行 make valgrind
結果:--- TOTAL 94/100
問題在 test06

+++ TESTING trace trace-06-string:
# Test of truncated strings

錯誤訊息如下

==7368== 32 bytes in 1 blocks are still reachable in loss record 1 of 30
==7368==    at 0x4C2FB0F: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==7368==    by 0x10B490: malloc_or_fail (report.c:189)
==7368==    by 0x10BFA2: add_cmd (console.c:123)
==7368==    by 0x10C083: init_cmd (console.c:93)
==7368==    by 0x10ACAC: main (qtest.c:759)
  • 看到 truncated strings,直覺告訴我是 remove head 的部份出問題了,回去看了一次程式碼如下,還有 spec ,發現是字串結尾沒有忘記加上 null terminator
if (!q || !q->head)
    return false;
if (q->head->value)
    strncpy(sp, q->head->value, bufsize);
else
    return false;

修改如下

if (!q || !q->head)
        return false;
if (q->head->value) {
    strncpy(sp, q->head->value, bufsize-1);
    sp[bufsize - 1] = '\0';
} else
    return false;

test06過了,但換 test09 錯誤如下

# Test remove_head with NULL argument
==9611== Invalid write of size 1
==9611==    at 0x4C3331F: __strncpy_sse2_unaligned (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==9611==    by 0x10CD7A: strncpy (string_fortified.h:106)
==9611==    by 0x10CD7A: q_remove_head (queue.c:124)
==9611==    by 0x109F10: do_remove_head_quiet (qtest.c:430)
==9611==    by 0x10B992: interpret_cmda (console.c:220)
==9611==    by 0x10BF06: interpret_cmd (console.c:243)
==9611==    by 0x10C4D4: cmd_select (console.c:569)
==9611==    by 0x10C71C: run_console (console.c:628)
==9611==    by 0x10AE41: main (qtest.c:772)
==9611==  Address 0x0 is not stack'd, malloc'd or (recently) free'd

原來沒注意到 sp 也有可能是 NULL,判斷條件補上

...
if (q->head->value && sp)
...

這樣就沒問題了

---	TOTAL		100/100

Massidf 視覺化記憶體使用量

$ valgrind --tool=massif ./qtest

利用第 16 筆測資來做範例,測試腳本如下

# 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
option fail 0
option malloc 0
new
ih RAND 10000
sort
reverse
sort
free
new
ih RAND 50000
sort
reverse
sort
free
new
ih RAND 100000
sort
reverse
sort
free
$ valgrind --tool=massif ./qtest < traces/trace-16-perf.cmd
$ massif-visualizer massif.out.<PID>

  • 可以看到 memory heap consumption 的使用量是隨著 item 的數目升高的,並且可以看到每次 free 完 queue 記憶體幾乎都會被釋放,但有個問題是第一次釋放完跟第二次釋放完 queue 記憶體並不是回到相同的狀態,這部份還不知道怎麼回事。而程式結束時 memory heap consumption 也隨著歸零

TODO :

  • Valgrind 記憶體分析
  • Massif 視覺化記憶體使用量
  • 設計相關實驗,查看記憶體使用狀態
  • 論文閱讀 Dude, is my code constant time?