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?
Last changed by 
 
hsieh
0
436

Read more

Weekly Report

imagenet SAF done variation 跑完一次，或許要再多跑幾次 SAF + variation ongoing TODO 整理 & 分析 3/15 改 journal

Mar 28, 2023
AIC2021 Project1 - TPU

Project Description Design a Tensor Processing Unit(TPU) which has 4x4 Processing elements(PEs) that is capable to calculate (4*K)*(K*4) 8-bit integer matrix muplication. (Where is K is limited by the size of input global buffer) Project Constraints Your designs should be written in verilog language. Your PEs shouldn&apos;t more than 4x4, where a 2D systolic array architecture is recommended. An 8-bit data length design. 3KiBytes in total of global buffer size.

May 6, 2021
gnuplot

reference: &#x6E2C;&#x91CF;&#x57F7;&#x884C;&#x6642;&#x9593; clock_gettime &#x5176;&#x4ED6;&#x65B9;&#x5F0F; List of performance analysis tools &#x6E2C;&#x91CF; cycle &#x6578; GCC &#x53C3;&#x6578;

Jan 12, 2021
CA note

Computer Architecture note 2020 Fall IEEE754 Floating Point Representation bias 127 Single Precision : 32 bits sign

Dec 26, 2020
Read more from hsieh
Published on HackMD