2020q3 Homework1 (lab0)

tags: RusselCK

contributed by <RusselCK>

• 進階電腦系統理論與實作 lab0
• 作業繳交區

環境

• 看環境

$ uname -a

• 看規格說明 ( Linux Programmer's Manual )

$ man *

開發工具

Vim

• 安裝 Vim
  $ sudo apt-get install vim

• 相關指令

* 編輯 Vim 設定檔(在家目錄下): $ vim .vimrc
* 切換游標至左側欄：ctrl + w + h
* 切換游標至右側欄：ctrl + w + l
* 下拉選單往下選：ctrl + n
* 下拉選單往下選：ctrl + p

使用方式

• 開啟想編輯的檔案

$ vi *.[ch]

• 存檔

:wq

• 編譯

$ gcc -o * *.c

• 看 Code

$ cat *.[ch]

提升程式碼品質

一致的程式撰寫風格

• 安裝 clang-format
  $ sudo apt install clang-format
• 執行 ( 在有程式的資料夾下 )

$ clang-format -i *.[ch]

Git Hooks 自動程式碼排版檢查

• 安裝 pre-commit
  $ sudo snap install pre-commit --classic
• 安裝 tig ，更便利地瀏覽 git repository 資訊
  $ sudo apt install tig

好的 Git commit message 應符合七條規則:

1. 用一行空白行分隔標題與內容
2. 限制標題最多只有 50 字元
3. 標題開頭要大寫
4. 標題不以句點結尾
5. 以祈使句撰寫標題
6. 內文每行最多 72 字
7. 用內文解釋 what 以及 why vs. how

閱讀 C Programming Lab

Overview

• queue.h：Queue structure

/* Linked list element */
typedef struct ELE {
    char *value;
    struct ELE *next;
} list_ele_t;
/* Queue structure */
typedef struct {
    list_ele_t *head; /* Linked list of elements */
} queue_t;

• Linked-list implementation of a queue. Each list element has a value field, pointing to an array of characters (C’s representation of strings), and a next field pointing to the next list element. Characters are encoded according to the ASCII encoding (shown in hexadecimal.)

Task

• Your task is to modify the code in queue.h and queue.c to fully implement the following functions.
  • q_new: Create a new, empty queue.
  • q_free: Free all storage used by a queue.
  • q_insert_head: Attempt to insert a new element at the head of the queue (LIFO discipline).
  • q_insert_tail: Attempt to insert a new element at the tail of the queue (FIFO discipline).
  • q_remove_head: Attempt to remove the element at the head of the queue.
  • q_size: Compute the number of elements in the queue.

下列程式碼的都簡單的註記功能

1. queue.h

• You will need to add more fields to this structure to efficiently implement q_size and q_insert_tail.

typedef struct ELE {
    char *value;
    struct ELE *next;
} list_ele_t;

typedef struct {
    list_ele_t *head; 
    //queue can know its tail
    list_ele_t *tail;
    //queue can know its size
    int size;
} queue_t;

2. q_new

• What if malloc returned NULL?

queue_t *q_new()
{
    queue_t *q = malloc(sizeof(queue_t));
    /* TODO: What if malloc returned NULL? */
    if(!q) 
        return NULL;
    
    q->head = NULL;
    q->tail = NULL;
    q->size = 0;
    return q;
}

3. q_free

• How about freeing the list elements and the strings?

void q_free(queue_t *q)
{
    if(!q) 
        return;
    
    /* TODO: How about freeing the list elements and the strings? */
    while (q->head) {
        list_ele_t *tmp = q->head;
        q->head = q->head->next;
        free(tmp->value);
        free(tmp);
    }
    /* Free queue structure */
    free(q);
}

4. q_insert_head

• What should you do if the q is NULL?
• What if either call to malloc returns NULL?

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

    list_ele_t *newh;
    newh = malloc(sizeof(list_ele_t));
    if (!newh)
        return false;
    /* Don't forget to allocate space for the string and copy it */
    size_t length = strlen(s) + 1;
    newh->value = (char *) malloc(length * sizeof(char));
    if (!newh->value) {
        free(newh);
        return false;
    }
    newh->next = NULL;

    // memset(newh->value, '\0', strlen(s) + 1);
    // strncpy(newh->value, s, strlen(s));
    // memcpy(newh->value, s, strlen(s) + 1);
    snprintf(newh->value, length, "%s", s);

    // insert head
    newh->next = q->head;
    q->head = newh;
    /* What if either call to malloc returns NULL? */
    if (!q->tail)
        q->tail = newh;
    (q->size)++;
    return true;
}

• void * memset ( void * ptr, int value, size_t num );
  • Fill block of memory
  • Sets the first num bytes of the block of memory pointed by ptr to the specified value (interpreted as an unsigned char).
• char * strncpy ( char * destination, const char * source, size_t num );
  • Copy characters from string
  • Copies the first num characters of source to destination.
  • If the end of the source C string (which is signaled by a null-character) is found before num characters have been copied, destination is padded with zeros until a total of num characters have been written to it.
• void * memcpy ( void * destination, const void * source, size_t num );
  • Copy block of memory
  • Copies the values of num bytes from the location pointed to by source directly to the memory block pointed to by destination.
• int snprintf ( char * s, size_t n, const char * format, ... );
  • Write formatted output to sized buffer
  • Composes a string with the same text that would be printed if format was used on printf, but instead of being printed, the content is stored as a C string in the buffer pointed by s (taking n as the maximum buffer capacity to fill).
• size_t
  • Unsigned integral type
  • Alias of one of the fundamental unsigned integer types
• Source: http://www.cplusplus.com

5. q_insert_tail

• It should operate in
  $O(1)$ time

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)
        return false;
    /* Don't forget to allocate space for the string and copy it */
    size_t length = strlen(s) + 1;
    newt->value = (char *) malloc(length * sizeof(char));
    if (!newt->value) {
        free(newt);
        return false;
    }

    snprintf(newt->value, length, "%s", s);

    // insert tail
    newt->next = NULL;
    if (!q->tail) {
        q->head = newt;
        q->tail = newt;
        return true;
    }
    q->tail->next = newt;
    q->tail = newt;
    (q->size)++;

    return true;
}

6. q_remove_head

• 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.)

bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
    /*Return false if queue is NULL or empty.*/
    if (!q || !q->head)
        return false;
    /*
     *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.)
     */
    list_ele_t *tmp = q->head;
    if (sp){
        // strncpy(sp, tmp->value, bufsize - 1);
        // sp[bufsize - 1] = '\0';
        snprintf(sp, bufsize, "%s", tmp->value);
    }
    
    // remove head
    q->head = q->head->next;
    free(tmp->value);
    free(tmp);
    q->size--;

    return true;
}

• sp[bufsize-1] = '\0';

7. q_size

• Return number of elements in queue.
• Return 0 if q is NULL or empty
• It should operate in
  $O(1)$ time

int q_size(queue_t *q)
{
    /* Remember: It should operate in O(1) time */
    // return !q ? 0 : q->size;
    if (!q) {
        return 0;
    }
    return q->size;
}

8. q_reverse

• Reverse elements in queue
• No effect if q is NULL or empty

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

     q->tail = q->head;

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

• 用 pointer to pointer 較好
  • 使用者可以知道 執行完之後 head的位址
• 2 個 element 可以用更簡單的方式完成

9. q_sort

• Sort elements of queue in ascending order

void split_list(list_ele_t **head, list_ele_t **list1, list_ele_t **list2)
{
    list_ele_t **slow = list1;
    list_ele_t **fast = list2;

    while ((*fast) && (*fast)->next) {
        *slow = (*slow)->next;
        *fast = (*fast)->next->next;
    }
    // slow is at the midnode

    *list2 = (*slow)->next;
    // Split actually
    (*slow)->next = NULL;
    
    *list1 = *head;
}

void merge_list(list_ele_t **head, list_ele_t **list1, list_ele_t **list2)
{
    list_ele_t **cursor = head;

    while ((*list1) && (*list2)) {
        if (strcmp((*list1)->value, (*list2)->value) < 0) {
            *cursor = *list1;
            *list1 = (*list1)->next;
        } else {
            *cursor = *list2;
            *list2 = (*list2)->next;
        }
        cursor = &((*cursor)->next);
    }
    // avoid dropped off
    if (*list1)
        *cursor = *list1;
    if (*list2)
        *cursor = *list2;
}

void merge_sort(list_ele_t **head)
{
    // Base case
    if (!(*head) || !(*head)->next)
        return;

    // Splitting list
    list_ele_t *list1 = (*head)->next;
    list_ele_t *list2 = *head;

    split_list(head, &list1, &list2);

    // Recursive sorting two list
    merge_sort(&list1);
    merge_sort(&list2);

    // Merge sorted lists
    merge_list(head, &list1, &list2);
}

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

    merge_sort(&q->head);

    while (q->tail->next)
        q->tail = q->tail->next;
}

• int strcmp ( const char * str1, const char * str2 );
  • Compare two strings
  • Compares the C string str1 to the C string str2.

return value	indicates
<0	the first character that does not match has a lower value in ptr1 than in ptr2
0	the contents of both strings are equal
>0	the first character that does not match has a greater value in ptr1 than in ptr2

• 若 input 只有 2 個，不應該進入 merge_sort
• 也許，沒有到一定的數量，就不要使用 merge_sort

自動評分程式

指令

• $ make test
• $ clang-format -i *.[ch]
• $ make valgrind
• $ valgrind ./test
• $ make SANITIZER=1
• $ ./qtest -f traces/trace-15-perf.cmd

$ make test 評分成果

---	Trace		Points
+++ TESTING trace trace-01-ops:
# Test of insert_head and remove_head
---	trace-01-ops	6/6
+++ TESTING trace trace-02-ops:
# Test of insert_head, insert_tail, and remove_head
---	trace-02-ops	6/6
+++ TESTING trace trace-03-ops:
# Test of insert_head, insert_tail, reverse, and remove_head
---	trace-03-ops	6/6
+++ TESTING trace trace-04-ops:
# Test of insert_head, insert_tail, size, and sort
---	trace-04-ops	6/6
+++ TESTING trace trace-05-ops:
# Test of insert_head, insert_tail, remove_head, reverse, size, and sort
---	trace-05-ops	5/5
+++ TESTING trace trace-06-string:
# Test of truncated strings
---	trace-06-string	6/6
+++ TESTING trace trace-07-robust:
# Test operations on NULL queue
---	trace-07-robust	6/6
+++ TESTING trace trace-08-robust:
# Test operations on empty queue
---	trace-08-robust	6/6
+++ TESTING trace trace-09-robust:
# Test remove_head with NULL argument
---	trace-09-robust	6/6
+++ TESTING trace trace-10-malloc:
# Test of malloc failure on new
---	trace-10-malloc	6/6
+++ TESTING trace trace-11-malloc:
# Test of malloc failure on insert_head
---	trace-11-malloc	6/6
+++ TESTING trace trace-12-malloc:
# Test of malloc failure on insert_tail
---	trace-12-malloc	6/6
+++ TESTING trace trace-13-perf:
# Test performance of insert_tail
---	trace-13-perf	6/6
+++ TESTING trace trace-14-perf:
# Test performance of size
---	trace-14-perf	6/6
+++ TESTING trace trace-15-perf:
# Test performance of insert_tail, size, reverse, and sort
---	trace-15-perf	6/6
+++ TESTING trace trace-16-perf:
# 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
---	trace-16-perf	6/6 
+++ TESTING trace trace-17-complexity:
# Test if q_insert_tail and q_size is constant time complexity
Probably constant time
Probably constant time
---     trace-17-complexity     5/5
---	TOTAL		100/100

運用 Valgrind 排除 qtest 實作的記憶體錯誤，並透過 Massif 視覺化 “simulation” 過程中的記憶體使用量

Valgrind

• 安裝 Valgrind
  $ sudo snap install valgrind --classic

• Valgrind 是個在使用者層級 (user space) 對程式在執行時期的行為提供動態分析的系統軟體框架，具備多種工具，可以用來追蹤及分析程式效能，最為人們所熟知的特性就是幫助使用者偵測記憶體錯誤，諸如使用未初始化的記憶體、不當的記憶體配置、或取消配置記憶體，並加以分析。所有工具都包含在 valgrind 套件中，可以透過以下命令執行：

$ valgrind --tool=<toolname> <program>

$ valgrind -q --leak-check=full ./<program>

• 由於 Valgrind 是動態追蹤，會從給定的程式一路追蹤到 glibc (GNU C library)，為了更好的分析效果，需要安裝對應包含除錯訊息的套件:
  $ sudo apt install libc6-dbg

• 看更多

  • Valgrind User Manual

Massif

• 安裝 Massif
  $ sudo apt install massif-visualizer

• Valgrind 可支援多種工具，其中分析記憶體使用狀況的工具叫做 Massif 可分析以下:

  • Heap blocks;
  • Heap administration blocks;
  • Stack sizes.

視覺化結果

• 執行

$ make valgrind
$ valgrind --tool=massif ./<prog>
$ ms_print outputfile