# 2021q1 Homework2 (quiz2) contributed by < [`DokiDokiPB`](https://github.com/a1091150) > ## 相關資訊 - [課程資訊](http://wiki.csie.ncku.edu.tw/sysprog/schedule) - [交作業區](https://hackmd.io/@sysprog/linux2021-homework2) - [測驗題目](https://hackmd.io/@sysprog/linux2021-quiz2) - [筆記觀摩](https://hackmd.io/@toastcheng/w2-quiz2) ## 測驗一 ### 選擇題 #### COND1 && COND2 - ( c ) fast->next == list - ( b ) fast->next->next == list - fast 移動距離為 slow 兩倍，因為 queue 採取 circular queue 的方式，透過判斷否走回 head 的方式中斷 list_for_each。 - fast 的起始點為 list->next - 如果 queue node 數量為偶數，當 fast->next == list head 時， slow 就會在中間。 - 如果 queue node 數量為奇數，當 fast->next->next == list head 時， slow 就會在中間。 #### MMM - (e) &get_middle(&q->list)->list #### TTT - 這裡要求傳回 middle，依據上面 CONT1 & CONT2 的結果，也就是傳回 slow。 ### 解釋程式碼運作原理 #### container_of - [container_of](https://hackmd.io/@sysprog/linux2021-quiz2) - [gcc gnu typeof](https://gcc.gnu.org/onlinedocs/gcc/Typeof.html) - [你所不知道的 C 語言：技巧篇 善用 GNU extension 的 typeof](https://hackmd.io/@sysprog/c-trick?type=view#善用-GNU-extension-的-typeof) #### list_head ```clike= struct list_head { struct list_head *prev, *next; }; #define LIST_HEAD(head) struct list_head head = {&(head), &(head)} static inline void INIT_LIST_HEAD(struct list_head *head) { head->next = head; head->prev = head; } ``` - 依據測驗題目筆記的說明，只要在自己的 struct 引入 list_head，無須自己維護一套 doubly-linked list - 當 head 指向自己時候，表示此 head 為空，沒有東西。 在本程式碼實作，會有兩種情況 - queue_t 中的 list，用於記錄 head，不用於記錄資料內容 - list_ele_t 中的 node，用於記錄 node，不用於記錄 linked list. 在 function 中的命名有反應此情況： - 以 struct list_head *node 表示其為 node，非 head - 以 struct list_head *head 表示其為 head， head->next 為其 node - 以 struct list_head *list 表示其為 head 並且很多 node #### list_add_tail ``` static inline void list_add_tail(struct list_head *node, struct list_head *head) { struct list_head *prev = head->prev; prev->next = node; node->next = head; node->prev = prev; head->prev = node; } ``` - head->prev 就是取得 list tail，並將新的 node 接上 list tail 之後。 #### list_del ``` static inline void list_del(struct list_head *node) { struct list_head *next = node->next, *prev = node->prev; next->prev = prev; prev->next = next; } ``` - 刪除 node 的方式就是將 prev 跟 next 相連結 - 如果 node == prev 或是 node == next， list_del 不會有作用 - 只是將目標 node 移除該 list #### list_empty ``` static inline int list_empty(const struct list_head *head) { return (head->next == head); } ``` - 就是判斷 list_head 是否只有自己(head) #### list_is_singular ``` static inline int list_is_singular(const struct list_head *head) { return (!list_empty(head) && head->prev == head->next); } ``` - head->prev == head->next 表示指向 head 或是指向同一個 node，再透過 !list_empty 排除指向 head 的情況，即可獲得 head 中只有一個 node #### list_splice_tail ``` static inline void list_splice_tail(struct list_head *list, struct list_head *head) { struct list_head *head_last = head->prev; struct list_head *list_first = list->next, *list_last = list->prev; if (list_empty(list)) return; head->prev = list_last; list_last->next = head; list_first->prev = head_last; head_last->next = list_first; } ``` - list_splice_tail 的目的是將 list 整串加入 head 尾端中 - 因為 list_head 為 doubly-linked list，也就是取得頭尾，並且重新串接。 #### list_cut_position ``` static inline void list_cut_position(struct list_head *head_to, struct list_head *head_from, struct list_head *node) { struct list_head *head_from_first = head_from->next; if (list_empty(head_from)) return; if (head_from == node) { INIT_LIST_HEAD(head_to); return; } head_from->next = node->next; head_from->next->prev = head_from; head_to->prev = node; node->next = head_to; head_to->next = head_from_first; head_to->next->prev = head_to; } ``` - list_cut_position 的目標是切割成兩串 list - head_to 為存放切割過後的左半 list，切割後存放範圍為原本 head_from->next 至 node - head_from 為被切割的 list，切割後的存放右半 list，存放範圍為 node->next 至 head_from->prev - node 為切割的點 #### list_entry ``` #define list_entry(node, type, member) container_of(node, type, member) ``` - list_head 新增至使用者自定義的結構中，原本可以透過自定義的結構體取得 list_head，但是 list_head 不能反查自定義的結構。 - 透過 container_of 的特性，可以反查結構，並取得該結構。 ### 改進部份 第一版本 #### 移除不必要的程式碼 - 在 list_head 中，有明顯的分別 list_head node 跟 list_head head 兩者操作方式不一樣，需要修改名稱以符合定義 - 修改 list_ele_t 中 list 改為 node - queue_t 保持原樣 - queue_t 中不需要去額外新增 head, tail - queue_t 中 size 沒有使用，也是可以移除。 ```diff typedef struct __element { char *value; - struct list_head list; + struct list_head node; } list_ele_t; typedef struct { - list_ele_t *head; /* Linked list of elements */ - list_ele_t *tail; - size_t size; struct list_head list; } queue_t; ``` #### function 名稱錯誤 - delete 一字的意思為刪除，表示會刪除其資料內容，應改為 remove - 操作的對象為 node，名稱應修正成 list_remove_node 表示這是移除 node ```diff - static inline void list_del(struct list_head *node) + static inline void list_remove_node(struct list_head *node) ``` ### 研讀 Linux 核心的 lib/list_sort.c 原始程式碼 - 請參閱筆記 [**研讀 Linux 核心的 lib/list_sort.c 原始程式碼**](https://hackmd.io/@DokiDokiPB/SJfES914O) :::info TODO: - ~~閱讀程式碼並且回答選擇題~~ - 回答延伸問題 - ~~解釋上述程式碼運作原理，指出改進空間並著手實作~~ - 研讀 Linux 核心的 lib/list_sort.c 原始程式碼，學習 sysprog21/linux-list 的手法，將 lib/list_sort.c 的實作抽離為可單獨執行 (standalone) 的使用層級應用程式，並設計效能評比的程式碼，說明 Linux 核心的 lib/list_sort.c 最佳化手法 - 將你在 quiz1 提出的改進實作，和 Linux 核心的 lib/list_sort.c 進行效能比較，需要提出涵蓋足夠廣泛的 benchmark ::: ## 測驗二 :::info - 閱讀程式碼並且回答選擇題 - 回答延伸問題 - 解釋上述程式碼運作原理 - 在 The Linux Kernel API 頁面搜尋 “power of 2”，可見 is_power_of_2，查閱 Linux 核心原始程式碼，舉例說明其作用和考量，特別是 round up/down power of 2 - 特別留意 __roundup_pow_of_two 和 __rounddown_pow_of_two 的實作機制 - 研讀 slab allocator，探索 Linux 核心的 slab 實作，找出運用 power-of-2 的程式碼和解讀 ::: ## 測驗三 :::info - 閱讀程式碼並且回答選擇題 - 回答延伸問題 - 解釋上述程式碼運作原理，並嘗試重寫為同樣功能但效率更高的實作 - 在 Linux 核心原始程式碼找出逐 bit 進行資料複製的程式碼，並解說相對應的情境 ::: ## 測驗四 :::info - 閱讀程式碼並且回答選擇題 - 回答延伸問題 - 上述程式碼使用到 gcc atomics builtins，請透過 POSIX Thread 在 GNU/Linux 驗證多執行緒的環境中，string interning 能否符合預期地運作？若不能，請提出解決方案 - chriso/intern 是個更好的 string interning 實作，請探討其特性和設計技巧，並透過內建的 benchmark 分析其效能表現 :::