2020q3 Homework1 (lab0)

--- tags: 進階電腦系統理論與實作, NCKU Linux Kernel Internals, 作業系統 --- # 2020q3 Homework1 (lab0) ###### tags: `RusselCK` contributed by <`RusselCK`> - ==[進階電腦系統理論與實作 lab0](https://hackmd.io/@sysprog/2020-lab0)== - [作業繳交區](https://hackmd.io/@sysprog/2020-homework3) ## 環境 * 看環境 ``` $ uname -a ``` * 看規格說明 ( Linux Programmer's Manual ) ``` $ man * ``` ## [開發工具](https://hackmd.io/@sysprog/gnu-linux-dev/) #### [Vim](https://hackmd.io/@sysprog/gnu-linux-dev/https%3A%2F%2Fhackmd.io%2Fs%2FHJv9naEwl) * 安裝 Vim `$ sudo apt-get install vim` * [相關指令](http://linux.vbird.org/linux_basic/0310vi.php) ``` * 編輯 Vim 設定檔(在家目錄下): $ vim .vimrc * 切換游標至左側欄：ctrl + w + h * 切換游標至右側欄：ctrl + w + l * 下拉選單往下選：ctrl + n * 下拉選單往下選：ctrl + p ``` ##### 使用方式 * 開啟想編輯的檔案 ``` $ vi *.[ch] ``` * 存檔 ``` :wq ``` * 編譯 ``` $ gcc -o * *.c ``` * 看 Code ``` $ cat *.[ch] ``` ![](https://i.imgur.com/oeqPF2l.png) ## 提升程式碼品質 #### 一致的程式撰寫風格 * 安裝 [clang-format](https://clang.llvm.org/docs/ClangFormat.html) `$ sudo apt install clang-format ` * 執行 ( 在有程式的資料夾下 ) ``` $ clang-format -i *.[ch] ``` #### [Git Hooks](https://www.atlassian.com/git/tutorials/git-hooks) 自動程式碼排版檢查 * 安裝 [pre-commit](https://pre-commit.com/#install) `$ sudo snap install pre-commit --classic` * 安裝 tig ，更便利地瀏覽 git repository 資訊 `$ sudo apt install tig` #### 好的 Git commit message 應符合七條規則: 1. 用一行空白行分隔標題與內容 1. 限制標題最多只有 50 字元 1. 標題開頭要大寫 1. 標題不以句點結尾 1. 以祈使句撰寫標題 1. 內文每行最多 72 字 1. 用內文解釋 what 以及 why vs. how ## 閱讀 [C Programming Lab](https://www.cs.cmu.edu/afs/cs/academic/class/15213-s20/www/labs/cprogramminglab.pdf) #### Overview * `queue.h`：Queue structure ```c= /* 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; ``` ![](https://i.imgur.com/uXzI1Gz.png) * 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`. ```c= 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? ```c= 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? ```c= 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? ```c= 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; } ``` :::info * **`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 ```c= 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.) ```c= 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; } ``` :::warning * `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 ```c= 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 ```c= 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; } ``` :::warning * 用 pointer to pointer 較好 * 使用者可以知道執行完之後 head的位址 * 2 個 element 可以用更簡單的方式完成 ::: #### 9. `q_sort` * Sort elements of queue in ascending order ```c= 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; } ``` :::info * **`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 | ::: :::warning * 若 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](https://valgrind.org/) * 安裝 [Valgrind](https://valgrind.org/) `$ sudo snap install valgrind --classic` * Valgrind 是個在使用者層級 (user space) 對程式在執行時期的行為提供動態分析的系統軟體框架，具備多種工具，可以用來追蹤及分析程式效能，最為人們所熟知的特性就是幫助使用者偵測記憶體錯誤，諸如使用未初始化的記憶體、不當的記憶體配置、或取消配置記憶體，並加以分析。所有工具都包含在 valgrind 套件中，可以透過以下命令執行： ``` $ valgrind --tool=<toolname> <program> ``` ``` $ valgrind -q --leak-check=full ./<program> ``` * 由於 Valgrind 是動態追蹤，會從給定的程式一路追蹤到 [glibc](https://www.gnu.org/software/libc/) (GNU C library)，為了更好的分析效果，需要安裝對應包含除錯訊息的套件: `$ sudo apt install libc6-dbg` * 看更多 * [Valgrind User Manual](https://valgrind.org/docs/manual/manual.html) #### [Massif](https://valgrind.org/docs/manual/ms-manual.html) * 安裝 Massif `$ sudo apt install massif-visualizer ` * Valgrind 可支援多種工具，其中分析記憶體使用狀況的工具叫做 Massif 可分析以下: * Heap blocks; * Heap administration blocks; * Stack sizes. #### 視覺化結果 * 執行 ``` $ make valgrind $ valgrind --tool=massif ./<prog> $ ms_print outputfile ``` ![](https://i.imgur.com/wAe5q8u.png)