--- tags: linux2023-homework1 --- > [Linux 核心設計/實作 (Spring 2023)](http://wiki.csie.ncku.edu.tw/linux/schedule) ## 作業要求 > [2023q1 Homework1 (作業區)](https://hackmd.io/@sysprog/linux2023-homework1) > [L01: lab0](https://hackmd.io/@sysprog/linux2023-lab0/) - [ ] 在 GitHub 上 fork lab0-c - [ ] 著手修改 `queue.[ch]` 和連帶的檔案，測試後用 Git 管理各項修改，要能滿足 `$ make test` 自動評分系統的所有項目。 - [ ] 研讀 Linux 核心原始程式碼的 [lib/list_sort.c](https://github.com/torvalds/linux/blob/master/lib/list_sort.c) 並嘗試引入到 `lab0-c` 專案，比較你自己實作的 merge sort 和 Linux 核心程式碼之間效能落差 - [ ] 確保 `qtest` 提供的 `web` 命令得以搭配上述佇列實作使用，目前一旦網頁伺服器啟動後，原本處理命令列操作的 `linenoise` 套件就無法使用，請提出改善機制 - [ ] 在 `qtest` 提供新的命令 `shuffle`，允許藉由 [Fisher–Yates shuffle](https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle) 演算法，對佇列中所有節點進行洗牌 (shuffle) 操作，需要以統計的原理來分析你的實作，探究洗牌的「亂度」 - [ ] 在 `qtest` 中執行 `option entropy 1` 並搭配 `ih RAND 10` 一類的命令，觀察亂數字串的分布，並運用「資訊與熵互補，資訊就是負熵」的觀念，設計一組新的命令或選項，得以在 `qtest` 切換不同的 PRNG 的實作 (可選定 [Xorshift](https://en.wikipedia.org/wiki/Xorshift))，搭配統計分析工具，比較亂數產生器 (如 Xorshift vs. 內建) 的品質 - [ ] 研讀論文〈[Dude, is my code constant time?](https://eprint.iacr.org/2016/1123.pdf)〉，解釋本程式的 "simulation" 模式是如何透過以實驗而非理論分析，達到驗證時間複雜度，需要解釋 [Student's t-distribution](https://en.wikipedia.org/wiki/Student%27s_t-distribution) 及程式實作的原理。 - [ ] 指出現有程式的缺陷或者可改進之處 (例如更全面地使用 Linux 核心風格的鏈結串列 API)，嘗試實作並提交 pull request ## 開發環境 ``` $ gcc --version gcc (Ubuntu 11.3.0-1ubuntu1~22.04) 11.3.0 ``` ``` $ lscpu Architecture: x86_64 CPU op-mode(s): 32-bit, 64-bit Address sizes: 39 bits physical, 48 bits virtual Byte Order: Little Endian CPU(s): 4 On-line CPU(s) list: 0-3 Vendor ID: GenuineIntel Model name: Intel(R) Core(TM) i5-4460 CPU @ 3.20GHz CPU family: 6 Model: 60 Thread(s) per core: 1 Core(s) per socket: 4 Socket(s): 1 Stepping: 3 CPU max MHz: 3400.0000 CPU min MHz: 800.0000 BogoMIPS: 6385.16 Caches (sum of all): L1d: 128 KiB (4 instances) L1i: 128 KiB (4 instances) L2: 1 MiB (4 instances) L3: 6 MiB (1 instance) NUMA: NUMA node(s): 1 NUMA node0 CPU(s): 0-3 ``` ## 開發進度 (53/100) - [x] `q_new` - [x] `q_free` - [x] `q_insert_head` - [x] `q_insert_tail` - [x] `q_remove_head` - [x] `q_remove_tail` - [x] `q_size` ## 開發過程 ### q_new 使用 `malloc` 函式進行記憶體配置，若配置記憶體空間失敗則回傳 `NULL` ，使用 `queue.h` 及連帶的 `list.h` 中所提供的巨集與函式。以 `INIT_LIST_HEAD()` 取代將 `next` 和 `prev` 都指向自身 (`head`) 的初始化實作。 ```c= struct list_head *q_new() { struct list_head *new = malloc(sizeof(struct list_head)); if (!new) return NULL; INIT_LIST_HEAD(new); return new; } ``` ### q_free 最初以 `list.h` 中提供的 `list_for_each_safe()` 來走訪節點，並以`q_release_element()` 來釋放走訪到的節點，但在編譯時卻產生出 **error: passing argument 1 of ‘q_release_element’ from incompatible pointer type** 。經檢查後發現 `q_release_element()` 中的 **expected type** 應該要為`element_t *` ，且 `struct element_t` 才有包含 `char` 與 `*value` 的變數宣告。 改進方案: 改以 `element_t *` 宣告 `entry` 和 `safe` ，並且以`list_for_each_entry_safe()` 取代 ~~`list_for_each_safe()`~~ 。 ```c= void q_free(struct list_head *l) { if (!l) return; element_t *cur, *safe; list_for_each_entry_safe (cur, safe, l, list) { q_release_element(cur); } free(l); } ``` ### q_insert_head 確認 `head` 是否為空，以及確認 `ele` 記憶體配置是否成功後，宣告新增字串的長度 (包含`\0`) 並串接字串 `s` 。使用 `list.h` 中提供的 `list_add()` 將新增的節點加入至串列的 `head` 。 ```c= bool q_insert_head(struct list_head *head, char *s) { element_t *ele = malloc(sizeof(element_t)); if (!head || !ele) return false; ele->value = malloc((strlen(s) + 1) * sizeof(char)); if (!ele->value) { free(ele); return false; } strncpy(ele->value, s, strlen(s) + 1); list_add(&ele->list, head); return true; } ``` ### q_insert_tail 以 `q_insert_head()` 為基礎，僅將 `list.h` 中提供的 `list_add()` 改為 `list_add_tail()` 。 ```c= bool q_insert_tail(struct list_head *head, char *s) { element_t *ele = malloc(sizeof(element_t)); if (!head || !ele) return false; ele->value = malloc((strlen(s) + 1) * sizeof(char)); if (!ele->value) { free(ele); return false; } strncpy(ele->value, s, strlen(s) + 1); list_add_tail(&ele->list, head); return true; } ``` ### q_remove_head 使用 `list_first_entry()` 取得 queue 中的第一個節點後，以 `list_del_init()` 來移除找到的第一個節點，並將移除之節點中所包含的字串存於 `sp` ，最後再回傳這個被移除的節點。 ```c= element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize) { if (!head || list_empty(head)) return NULL; element_t *ele = list_first_entry(head, element_t, list); list_del_init(head->next); if (ele && bufsize) { strncpy(sp, ele->value, bufsize - 1); sp[bufsize - 1] = '\0'; } return ele; } ``` ### q_remove_tail 以 `q_remove_head()` 為基礎，僅將 `list.h` 中提供的 `list_first_entry()` 改為 `list_last_entry()` ，即為找到並取得 queue 中的最後一個節點。 ```c= element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize) { if (!head || list_empty(head)) return NULL; element_t *ele = list_last_entry(head, element_t, list); list_del_init(head->next); if (ele && bufsize) { strncpy(sp, ele->value, bufsize - 1); sp[bufsize - 1] = '\0'; } return ele; } ``` ### q_size 使用 `list_for_each()` 來走訪所有的節點，並參照 [L01: lab0](https://hackmd.io/@sysprog/linux2023-lab0/%2F%40sysprog%2Flinux2023-lab0-a) 來實作此介面。 ```c= int q_size(struct list_head *head) { if (!head) return 0; int len = 0; struct list_head *li; list_for_each (li, head) len++; return len; } ``` ### q_delete_mid 參考 [你所不知道的 C 語言: linked list 和非連續記憶體](https://hackmd.io/@sysprog/c-linked-list) ，並以 [Leetcode 2095. Delete the Middle Node of a Linked List](https://leetcode.com/problems/delete-the-middle-node-of-a-linked-list/) 案例，應用快慢指標的技巧，並刪除找到的中間節點。 ```c= bool q_delete_mid(struct list_head *head) { // https://leetcode.com/problems/delete-the-middle-node-of-a-linked-list/ if (!head || list_empty(head)) return false; struct list_head *cur = head->next; struct list_head *fast = head->next; while (fast != head && fast->next != head) { cur = cur->next; fast = fast->next->next; } list_del(cur); q_release_element(list_entry(cur, element_t, list)); return true; } ``` ### q_delete_dup 走訪每個節點，並檢查每個節點往後至尾端的最後一個節點，檢查節點之中是否存在相同的字串。 ```c= bool q_delete_dup(struct list_head *head) { // https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/ if (!head || list_empty(head)) return false; struct list_head *cur = head->next, *del; while (cur->next != head) { if (strcmp(list_entry(cur, element_t, list)->value, list_entry(cur->next, element_t, list)->value) == 0) { del = cur->next; list_del(del); q_release_element(list_entry(del, element_t, list)); } else { cur = cur->next; } } return true; } ``` ## 預期進度
Last changed by  
 
chien1214
200
Published on HackMD