# 2023q1 Homework1 (lab0) contributed by < `sherrygottalent` > ## 開發環境 ```shell $ gcc --version gcc (Ubuntu 12.2.0-3ubuntu1) 12.2.0 $ lscpu Architecture: aarch64 CPU op-mode(s): 64-bit Byte Order: Little Endian CPU(s): 4 On-line CPU(s) list: 0-3 Vendor ID: 0x00 Model name: - Model: 0 Thread(s) per core: 1 Core(s) per socket: 4 Socket(s): 1 Stepping: 0x0 BogoMIPS: 48.00 ``` ## 閱讀資料 - [lab0-c](https://hackmd.io/@sysprog/linux2023-lab0/) - [The Linux Kernel API](https://www.kernel.org/doc/html/latest/core-api/kernel-api.html) - [Valgrind 記憶體問題分析](https://hackmd.io/@sysprog/linux2023-lab0-b) ## ToDo :::spoiler todo-list - [x] q_new: 建立新的「空」佇列; - [x] q_free: 釋放佇列所佔用的記憶體; - [x] q_insert_head: 在佇列開頭 (head) 插入 (insert) 給定的新節點 (以 LIFO 準則); - [x] q_insert_tail: 在佇列尾端 (tail) 插入 (insert) 給定的新節點 (以 FIFO 準則); - [x] q_remove_head: 在佇列開頭 (head) 移去 (remove) 給定的節點; - [x] q_release_element: 釋放特定節點的記憶體空間; - [x] q_size: 計算目前佇列的節點總量; - [x] q_delete_mid: 移走佇列中間的節點，詳見 LeetCode 2095. Delete the Middle Node of a Linked List - [x] q_delete_dup: 在已經排序的狀況，移走佇列中具備重複內容的節點，詳見 LeetCode 82. Remove Duplicates from Sorted List II - [x] q_swap: 交換佇列中鄰近的節點，詳見 LeetCode 24. Swap Nodes in Pairs :warning: find better way - [x] q_reverse: 以反向順序重新排列鏈結串列，該函式不該配置或釋放任何鏈結串列節點，換言之，它只能重排已經存在的節點; - [ ] q_reverseK: 類似 q_reverse，但指定每 k 個節點為一組，進行反向順序排列，詳見 LeetCode 25. Reverse Nodes in k-Group - [ ] q_sort: 以遞增順序來排序鏈結串列的節點，可參閱 Linked List Sort 得知實作手法; - [x] Selection Sort - [ ] QSort - [ ] q_merge: 合併所有已排序的佇列，並合而為一個新的已排序佇列，詳見 LeetCode 23. Merge k Sorted Lists - [x] q_descend: 參閱 LeetCode 2487. Remove Nodes From Linked List **~TOTAL 53/100~** ::: ## 實作過程 :::danger 注意書寫規範：中英文間用一個半形空白區隔。改進你的漢語表達。標點符號也該合理運用，例如該區分「，」和 comma (即 `,`) :notes: jserv ::: ### q_new() - **初始想法** list.h 有現成巨集, 想用 `LIST_HEAD` 作為宣告，再利用 `INIT_LIST_HEAD()` 初始化 - **遇到問題** `LIST_HEAD` 型別非指標, 作為 `q_new()` 的return value也會碰到 `return local address` 錯誤 - **解決/實作方式** 自己 malloc 記憶體宣告 `struct *list_head` - **Question** - [x] 1. 在函式內 malloc 的記憶體區塊不受函式 lifetime 限制, 不會被 free 掉, 這個理解應該是對的 - heap vs stack - [x] 2. malloc 完沒有 free 是 bad coding，那此處 malloc 的 head 作為回傳值, 好的習慣是接收回傳值的地方要負責 free 此塊 memory? - yes - [ ] 3. trace-13-malloc.cmd 的 multiple `new` 測試 ### q_free - **解決/實作方式** 釋放參數傳入的記憶體位置, 起始位置為指標指向位置, 根據指標型別釋放記憶體大小 :warning: 只有 free list_head，沒有 free element的block ### q_insert_head - **初始想法** 參考現有資料 queue.h - `element_t`, list.h - `list_add`, `list_empty`進行實作 - **遇到問題** <s>使用 strndup() 賦值給`node->value`</s>指派strndup()結果到 `node->value`, 在 remove element時會碰到 segmentation fault :::warning 避免說「賦值」，這是違反漢語文法的偷懶翻譯，可改說「指派 `strndup()` 結果到 `node->value`」 :notes: jserv ::: 實際原因是賦職是 local variable, 函式生命週期結束後變數位置記憶體已經被釋放 後續程式執行 q_release_element()會重複釋放記憶體, 造成 segmentation fault. 1. 作業要求: > * Argument s points to the string to be stored. > * The function must explicitly allocate space and copy the string into it. 2. q_release_element() 實作也是會先 free e->value ``` c= static inline void q_release_element(element_t *e) { test_free(e->value); test_free(e); } ``` - **解決/實作方式** 實際分配一塊記憶體, 並賦值產生有一個結尾符號的`char *`變數 再將 element->val 指向該變數 - **延伸問題** 實作時嘗試過直接寫 ``` c= element->val = malloc(size); ... ``` 可以跑過`make test`, 但 commit 碰到錯誤訊息: > Following files need to be cleaned up: > queue.c > queue.c:99:5: error: Memory leak: node.value [memleak] > return true; > ^ > > Fail to pass static analysis. Code section: ``` c= size_t size = strlen(s) + 1; // Fail statis analysic version node->value = malloc(sizeof(char) * size); for (int i = 0; i < size - 1; i++) { *(node->value + i) = s[i]; } node->value[size - 1] = '\0'; /* // Pass statis analysic version char *val = malloc(sizeof(char) * size); for (int i = 0; i < size - 1; i++) { *(val + i) = s[i]; } val[size - 1] = '\0'; node->value = val; */ ``` 還不知道怎麼解. 重寫（還沒整理筆記）： ```clike= bool q_insert_head(struct list_head *head, char *s) { struct list_head *node = malloc(sizeof(struct list_head)); INIT_LIST_HEAD(node); element_t *entry = list_entry(node, element_t, list); /* Allocate space and copy string to value */ size_t buflen = sizeof(s); entry->value = malloc(buflen); entry->value = strncpy(entry->value, s, buflen-1); entry->value[buflen-1] = '\0'; list_add(node, head); if(!node) return false; return true; } ``` :::warning #### 實驗 ```clike= #include<stdio.h> #include<stdlib.h> struct B { struct B *prev; struct B *next; }; struct A{ char * ptr; struct B stB; }ele_A; int main(){ printf("sizeof(char *) = %ld\n", sizeof(char *)); printf("sizeof(struct B) = %ld\n", sizeof(struct B)); printf("sizeof(ele_A) = %ld\n", sizeof(ele_A)); char *s = "0123456789"; printf("s = %s, sizeof(s) = %ld\n", s, sizeof(s)); ele_A.ptr = malloc(8*sizeof(s)); printf("sizeof(ele_A) = %ld\n", sizeof(ele_A)); return 0; } ``` output: ``` sizeof(char *) = 8 sizeof(struct B) = 16 sizeof(ele_A) = 24 s = 0123456789, sizeof(s) = 8 sizeof(ele_A) = 24 ``` #### 問題 [C Language Data Type Models: LP64 and ILP32](https://docs.oracle.com/cd/E19620-01/805-3024/lp64-1/index.html) 指標大小在不同的電腦架構下不同，指標的大小也跟指標型態無關 這題只要複製`char *s`內容到指標的記憶體位置就可以了 為什麼指標還需要配置記憶體 `malloc`？ #### 自己回 ::: ### q_insert_tail - **初始想法** ~~Find tail, then add node. (`list_for_each`, `list_is_last`)~~ 參考前題**q_insert_head**實作, list.h - `list_add_tail` 遇到的問題也是類似的。 ### q_remove_head - **初始想法** 參考list.h - `list_del`, `list_first_entry`進行實作 - **遇到問題** 把`strndup`回傳值當return value, 未free memory, 改用`strncpy` ``` char *strndup( const char *str, size_t size ); (dynamic memory TR) Returns a pointer to a null-terminated byte string, which contains copies of at most size bytes from the string pointed to by str. If the null terminator is not encountered in the first size bytes, it is added to the duplicated string. The returned pointer must be passed to free to avoid a memory leak. If an error occurs, a null pointer is returned and errno may be set. ``` ::: info **strcpy()** - *will not allocate the memory space* to copy. A pointer to the string to copy and a pointer to place to copy it to should be given. **strdup()** - *will occupy / grab itself the memory space for copying the string to*. This memory space needs to be *freed up later when it is of no use anymore*. ::: - **Question/Extension** - [x] 1. `list_entry(node, type, member)` 為什麼有指向結構中成員 node 的指標，可以反向取得 entry ？ 參考：[Linux 核心原始程式碼巨集: container_of](https://hackmd.io/@sysprog/linux-macro-containerof)、[Understanding container_of macro in the Linux kernel](https://stackoverflow.com/questions/15832301/understanding-container-of-macro-in-the-linux-kernel) 利用指標指向記憶體位置（pointer to node），和結構中成員的記憶體排序，反向取得對應結構的起始位置，和成員的值。 > ... 但我們見識到 Linux 核心開發者追求的「優雅」 —— 清晰地界定介面和實作本體。 - [ ] 2. `list_for_each_entry` 的 FIXME `FIXME: remove dependency of __typeof__ extension` [Remove all usage of typeof() and change .xcconfig to disallow GCC extensions #846](https://github.com/material-components/material-components-ios/issues/846) material-components-ios 有在討論移除 `__typeof__` 的用法，建議以實際變數類型取代 `typeof()` :question: 為什麼針對`list_for_each_entry`，`list_for_each_entry_safe` 移除 `__typeof__` 猜：（待討論） 1. In list.h, 非標準函式庫 > "typeof" is a GNU extension. 2. `list_entry` 的設計很明確是要給 `element_t` 使用 修改： `__typeof__(*entry)` 明確指定型別 `element_t` 那麼，為什麼 list.h 能辨別 `element_t` ？？ :warning:引用 stddef 函式庫，如何找 dependency ？ :warning:怎麼找 linux 的原始碼，要把 torvalds/linux 的 github repository 拉下來 grep ? ### q_remove_tail - **初始想法** 仿效`q_remove_head`實作, 參考list.h - `list_del`, `list_last_entry`進行實作 ### q_delete_mid - **初始想法** Implement with `q_size()`, `list_for_each_entry_safe` - [X] 未刪除對應node!!!!! - [ ] refinement leetcode - [X] fail to free!! ### q_delete_dup - **初始想法** 1. No idea... delete `list_for_each_entry_safe` 2. 參考leetcode solution 用兩個 node 走訪 相當於是兩層 for-loop 走訪的概念 定住 prev node, 往後找到duplicate node 2-1. `list_for_each_entry_safe` 實際實作第二層`list_for_each_entry_safe`不是完整circular linked-list, 走訪卡住 2-2. 一樣走兩層, 但改成 ptr 走訪 :question:作業需求疑問: 沒有指定是否跟leetcode敘述一樣是已經排序的list - 加入 `q_release_element` 會 Segmentation fault. 不加會成功從 queue 移除 element, 但 memory 未釋放:warning:, 仍未搞懂原因 ### q_reverse - **解決/實作方式** head node 指標掉頭, 在走訪中間的節點把 next, prev 指標都調頭 ### q_descend - **遇到問題** 作業需求疑問: 用 pointer to char 比大小? 最後自己實作有加上 `atoi` 轉換 ### q_merge 寫出的第一版可以完成 first queue排序正確，函示也跑完，跑測試卻會跳 `Segmentation fault`。 使用工具協助分析 segmentation fault！！ ==> [Valgrind 記憶體問題分析](https://hackmd.io/@sysprog/linux2023-lab0-b) --- [gcc options](https://web.mit.edu/rhel-doc/3/rhel-gcc-en-3/invoking-gcc.html)