2021q1 Homework2 (quiz2)

# 2021q1 Homework2 (quiz2) contributed by < `shanihsu` > ###### tags: `linux2021` ## 測驗 1 ### 作答區 #### Q1、Q2、Q4 ```c= static list_ele_t *get_middle(struct list_head *list) { struct list_head *fast = list->next, *slow; list_for_each (slow, list) { if (COND1 || COND2) break; fast = fast->next->next; } return list_entry(TTT, list_ele_t, list); } ``` * COND1 : `fast->next == list` * COND2 : `fast->next->next == list` * TTT : `slow` * `get_middle` 這個 function 功能主要用於尋找 linked list 的中間點，並回傳該中間點的位址 * 由 `list_for_each` 的迭代可看出，透過 `fast` 跟 `slow` 兩變數來尋找 linked list 的中間點，在每圈迭代中 : * `fast` : 暫存 linked list 中與前次 `fast` 相隔兩格的 node * `slow` : 暫存 linked list 中與前次 `slow` 相隔一格的 node * 迭代終止條件 : 因為此 linked list 是 circuler doubly linked list，所以當 `fast->next == list` 或 `fast->next->next == list` 時，代表整個 linked list 已搜尋完畢，即停止迭代搜尋。 * 回傳值 : 當迭代完畢時，fast 會停留在 linked list 的尾端或倒數第二個，而 `slow` 會停留在linked list 中間值的位置，此時只需要呼叫 `list_entry` ，回傳 `slow` 這個 struct 的位址，即可得到該 linked list 的中間點位址。 #### Q3 ```c= void list_merge_sort(queue_t *q) { if (list_is_singular(&q->list)) return; queue_t left; struct list_head sorted; INIT_LIST_HEAD(&left.list); list_cut_position(&left.list, &q->list, MMM); list_merge_sort(&left); list_merge_sort(q); list_merge(&left.list, &q->list, &sorted); INIT_LIST_HEAD(&q->list); list_splice_tail(&sorted, &q->list); } ``` * MMM : `&get_middle(&q->list)->list` * `list_cut_position` 這個 function 功能用來將 linked list 依照中間點分成兩個 linked list ， function 定義 : ```c= static inline void list_cut_position(struct list_head *head_to, struct list_head *head_from, struct list_head *node) ``` * function 第三個參數要傳入 struct `list_head` 型態， `get_middle` 回傳的型態為 `list_ele_t *` ，須將其取址後，找到 `__element` 型別，再取出其中的 `list` 元素。 ### 解釋程式碼原理 #### `INIT_LIST_HEAD` * 初始化空的 linked list `head` ```c= static inline void INIT_LIST_HEAD(struct list_head *head) { head->next = head; head->prev = head; } ``` ```graphviz digraph structs { node[shape=record] struct1 [label="<f0> prev|<f1> next", xlabel = "head"]; struct1:f0 -> struct1; struct1:f1 -> struct1; } ``` #### `list_add_tail` * 將 `node` 接在 linked list 的尾端 * 因為是 circuler doubly linked list ，所以其 `head->prev` 相當於此 linked list 的尾端 * 先宣告 `prev` 暫存 `head->prev` ，再將 node 接上 ```c= 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; } ``` ```graphviz digraph structs { rankdir=LR; node [shape=record]; a [label="{ <prev> prev | <next> next}", xlabel = "head"] b [label="{ <prev> prev | <next> next }"]; c [label="{ <prev> prev | <next> next}",xlabel = "node"]; a -> b ; b -> a ; b -> c ; c -> b ; c:next -> a:prev ; a:prev -> c:next ; } ``` #### `list_del` * 先將欲刪除之 `node` 的 `prev` 與 `next` 暫存 * 再將`prev` 與 `next`相連接，以達到刪除此 `node` * 因為是 circuler doubly linked list ，所以當 `node == head | tail` 時，視為刪除一般 `ndoe` ，不需要特別考慮其狀況 ```c= static inline void list_del(struct list_head *node) { struct list_head *next = node->next, *prev = node->prev; next->prev = prev; prev->next = next; } ``` #### `list_empty` * 當 `head->next == head` 時，代表 `head` 指回自己，此 linked list 為空 ```c= static inline int list_empty(const struct list_head *head) { return (head->next == head); } ``` #### `list_is_singular` * 當 linked list 非空，且 `head->prev` 與 `head->next` 指向同一塊記憶體，表示 linked list 中只有一個 node ```c= static inline int list_is_singular(const struct list_head *head) { return (!list_empty(head) && head->prev == head->next); } ``` #### `list_splice_tail` * 將 `list` 接到 `head` 的尾端 * 運用其為 circuler doubly linked list ，可得知兩個 linked list 之頭尾，並將其暫存後，重新串接 ```c= 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_cut_position` * `head_from` : 欲切割的 linked list * `node` : 欲切割點 * `head_to` : 切割後以 `node` 為開頭，並串接原本 `head_from` 的下一個點 * 將 `head_from` 以 `node` 為切點切割，切割後分別得到以 `node` 為分界的兩個 linked list * `node` 左邊的 linked list 由 `head_to` 串接，並將 `node` 串接於首 * `node` 右邊的 linked list 由 `head_from`串接 ```c= 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; } ``` #### `get_middle` * `fast` : 暫存 linked list 中與前次 `fast` 相隔兩格的 node * `slow` : 暫存 linked list 中與前次 `slow` 相隔一格的 node * 透過 `fast` 與 `slow` 兩變數在每次迴圈中移動速度不同，尋找 linked list 的中間點，並回傳該中間點的位址 * 因為此 linked list 是 circuler doubly linked list，所以當 `fast->next == list` 或 `fast->next->next == list` 時，代表整個 linked list 已搜尋完畢，即停止迭代搜尋。 * 回傳值 : 當迭代完畢時，fast 會停留在 linked list 的尾端或倒數第二個，而 `slow` 會停留在linked list 中間值的位置，此時只需要呼叫 `list_entry` ，回傳 `slow` 這個 struct 的位址，即可得到該 linked list 的中間點位址。 ```c= static list_ele_t *get_middle(struct list_head *list) { struct list_head *fast = list->next, *slow; list_for_each (slow, list) { if (fast->next == list || fast->next->next == list) break; fast = fast->next->next; } return list_entry(slow, list_ele_t, list); } ``` #### `list_merge` * 判斷 `lhs->next` 跟 `rhs->next` 的 `value` 大小，將小的 node 從原本所在的 linked list 中刪除，並將其接到 `head` 之後 * 重複上述動作，直到 `lhs` 或 `rhs` 其中之一為空時，將另一 linked list 串接到 `head` 後 ```c= static void list_merge(struct list_head *lhs, struct list_head *rhs, struct list_head *head) { INIT_LIST_HEAD(head); if (list_empty(lhs)) { list_splice_tail(lhs, head); return; } if (list_empty(rhs)) { list_splice_tail(rhs, head); return; } while (!list_empty(lhs) && !list_empty(rhs)) { char *lv = list_entry(lhs->next, list_ele_t, list)->value; char *rv = list_entry(rhs->next, list_ele_t, list)->value; struct list_head *tmp = strcmp(lv, rv) <= 0 ? lhs->next : rhs->next; list_del(tmp); list_add_tail(tmp, head); } list_splice_tail(list_empty(lhs) ? rhs : lhs, head); } ``` ### 改進空間 :::danger 不該急著列出程式碼，相反地，你該討論上述程式碼有哪些缺失，詳列可改進的空間及策略，提出落實的方案，最後才是程式碼和實驗。 :notes: jserv ::: #### `list_merge` * 下面程式碼在第7行及第12行中邏輯有誤，當該 linked list 為空時，將此空的 list 加到 `head` 之後已無意義，應做以下調整，將另一個非空的 linked list 加到 `head` 之後。 ```diff= static void list_merge(struct list_head *lhs, struct list_head *rhs, struct list_head *head) { INIT_LIST_HEAD(head); if (list_empty(lhs)) { - list_splice_tail(lhs, head); + list_splice_tail(rhs, head); return; } if (list_empty(rhs)) { - list_splice_tail(rhs, head); + list_splice_tail(lhs, head); return; } } ``` #### 現有的程式架構 * 有以下三種架構 : ```graphviz digraph structs { subgraph cluster_b{ label = "list_head" node[shape=record] struct1 [label="<f0> *prev|<f1> *next" ]; } } ``` ```graphviz digraph structs { subgraph cluster_head { label="list_ele_t"; node [shape=record]; head [label="value"]; head1 [label="*next"]; list_head [label="{*prev|*next}"]; } } ``` ```graphviz digraph G { subgraph cluster_b { node [shape=record]; label = "queue_t" subgraph cluster_head { label="list_ele_t *head"; node [shape=record]; head [label="value"]; head1 [label="*next"]; list_head [label="{*prev|*next}"]; } list_ele1 [label="size"]; subgraph cluster_tail { label="list_ele_t *tail"; node [shape=record]; tail [label="value"]; tail1 [label="*next"]; list_tail [label="{*prev|*next}"]; } subgraph cluster_list { label="list_head *list"; node [shape=record]; list [label="{*prev|*next}"]; } } } ``` * 由上圖可看出，list_ele_t 中已有 `struct list_head` 紀錄 `*next` ，所以 `struct __element *next` 是多餘的。 * 對於整個 list 而言，有 `list_ele_t` 就可串接整個 list ，也可以紀錄 `head` 跟 `tail` ，不需要再額外使用 `queue_t`。 * 故原本的程式碼可改成以下 : ```diff= typedef struct __element { char *value; - struct __element *next; struct list_head list; } 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; ``` #### malloc 的回傳值型態 * 在 `q_insert_head` 中 malloc `list_ele_t` 寫法如下 : ```c= list_ele_t *newh = malloc(sizeof(list_ele_t)); ``` * 在[你所不知道的C語言：指標篇](https://hackmd.io/@sysprog/c-pointer#%E4%BD%A0%E6%89%80%E4%B8%8D%E7%9F%A5%E9%81%93%E7%9A%84C%E8%AA%9E%E8%A8%80%EF%BC%9A%E6%8C%87%E6%A8%99%E7%AF%87)中有提到 > `void *` 存在的目的就是為了強迫使用者使用顯式轉型或是強制轉型，以避免 Undefined behavior 產生但在上述使用 `list_ele_t *` 型態直接取用，沒有先將 `*void` 強制轉型，卻沒有發生錯誤，以下為此問題的探討 : * 根據 [C11 standard](http://open-std.org/JTC1/SC22/WG14/www/docs/n1570.pdf) > C11 [6.3.2.3] Pointers 第一點 A pointer to void may be converted to or from a pointer to any object type. A pointer to any object type may be converted to a pointer to void and back again; the result shall compare equal to the original pointer. > C11 [6.5.16.1] Simple assignment 第二點 In simple assignment (=), the value of the right operand is converted to the type of the assignment expression and replaces the value stored in the object designated by the left operand. 由此可知，在 C 語言中，使用 simple assignment (=)， `void*` 是可以被 implicit cast 成為其他型別的 pointer。 :::warning 但在 [sysprog21/linux-list](https://github.com/sysprog21/linux-list/blob/master/examples/insert-sort.c) 中的第 55 行 ```c= item = (struct listitem *) malloc(sizeof(*item)); ``` 卻仍將 `void *` 強制轉型成 `struct listitem` 型態，想請問以 `malloc` 而言，是否一定要強制轉型才是安全的？ > 對 C 語言沒影響，但對 C++ 語言則需要 explicit casting ::: ### 將 `lib/list_sort.c` 的實作抽離為可單獨執行 (standalone) 的使用層級應用程式 > [GitHub](https://github.com/shanihsu/Linux_2021/blob/main/quiz2/list_sort.c) 學習 [sysprog21/linux-list](https://github.com/sysprog21/linux-list) 的手法，將 [lib/list_sort.c](https://github.com/torvalds/linux/blob/master/lib/list_sort.c) 的實作抽離為可單獨執行 (standalone) 的使用層級應用程式，並利用隨機產生的 256 個 value 做測試。以下為實作方法 : #### 架構 ```graphviz digraph structs { rankdir=LR; node[shape=record]; subgraph cluster_b{ label = "list_head testlist"; struct1 [label="<f0> *prev|<f1> *next" ]; } subgraph cluster_1 { label="listitem"; head [label="i"]; subgraph cluster_c{ label = "list_head list" node[shape=record] struct2 [label="<f0> *prev|<f1> *next" ]; } } subgraph cluster_2 { label="listitem"; node [shape=record]; head1 [label="i"]; subgraph cluster_d{ label = "list_head list" node[shape=record] struct3 [label="<f0> *prev|<f1> *next" ]; } } subgraph cluster_head { label="listitem"; node [shape=record]; head2 [label="i"]; subgraph cluster_e{ label = "list_head list" node[shape=record] struct4 [label="<f0> *prev|<f1> *next" ]; } } struct1:f1->struct2; struct2:f1->struct3; struct3:f1->struct4; struct2:f0->struct1; struct3:f0->struct2; struct4:f0->struct3; } ``` #### 新增 `listitem` 其中的 `i` 所存的值為欲排序的 `value` 值 ```c= struct listitem { uint16_t i; struct list_head list; }; ``` #### 移除`cmp_func` * 將`lib/list_sort.c` 中的`cmp_func` 移除，改用 `cmpint` 替代，使 `lib/list_sort.c` 成功抽離為可單獨執行的程式。 ```c= static inline int cmpint(const void *p1, const void *p2) { const uint16_t *i1 = (const uint16_t *) p1; const uint16_t *i2 = (const uint16_t *) p2; return *i1 - *i2; } ``` * 使用 `list_entry` ，從 `listitem` 搜尋，並取出存在 `listitem` 中欲比較的值 `i` ，存入 `value_a` 、 `value_b` ，再將此兩個值取址，並傳入 `cmpint` 中比較。 ```c= static struct list_head *merge(struct list_head *a, struct list_head *b) { struct list_head *head, **tail = &head; for (;;) { struct listitem *item = NULL; uint16_t value_a = list_entry(a, __typeof__(*item), list)->i; uint16_t value_b = list_entry(b, __typeof__(*item), list)->i; /* if equal, take 'a' -- important for sort stability */ if (cmpint(&value_a, &value_b) <= 0) { *tail = a; tail = &a->next; a = a->next; if (!a) { *tail = b; break; } } else { *tail = b; tail = &b->next; b = b->next; if (!b) { *tail = a; break; } } } return head; } ``` #### 移除 `likely` 與 `unlikely` macro * `likely` 與 `unlikely` 這兩個 macro 被定義在 `/include/linux/compiler.h` 中，可以讓 compiler 在編譯 assembly code 的時候最佳化，將其移除對程式的正確性沒有影響，故移除以成功抽離 `lib/list_sort.c` ### 說明 Linux 核心的 `lib/list_sort.c` 最佳化手法 #### `likely` 與 `unlikely` branch predictor * 在 `/include/linux/compiler.h` 中有以下定義: ```cpp #define likely(x) __builtin_expect(!!(x), 1) #define unlikely(x) __builtin_expect(!!(x), 0) ``` * 範例 : ```cpp if (likely(x)) { /* execute when x is true */ } else { /* execute when x is false */ } ``` * 使用 `likely` 時，表示其 (x == true) 較常發生， compiler 會將 `likely` 敘述後方的程式碼編譯在判斷之後。 * 使用 `unlikely` 時，表示其 (x == false) 較常發生， compiler 會將 `unlikely` 敘述後方的程式碼編譯在判斷之後。 * 透過 `likely` 跟 `unlikely` ，可以調整編譯器轉換的組合語言順序，將較常發生的判斷式敘述與條件程式碼，編譯到接近的位置 * 當 mispredict 時，需從 memory 一次搬一個區塊記憶體的資料到 cache ，當程式碼透過 `likely` 跟 `unlikely` 編譯後，會產生對 branch predictor 較友善的程式碼，從而縮減 mispredict 的執行成本，但若 `likely` 和 `unlikely` 誤用，會有反效果 #### 將 circular doubly-linked list 轉成 null-terminated singly-linked list 在一開始先將 doubly linked list 轉成 singly-linked list ，再做排序，可以在運算過程減少不必要的 assign ```cpp /* Convert to a null-terminated singly-linked list. */ head->prev->next = NULL; ``` 在最後運算完成，再將其改回 doubly-linked list ```cpp /* And the final links to make a circular doubly-linked list */ tail->next = head; head->prev = tail; ``` #### 將 mergesort 盡可能地以 2:1 的比例合併 [linux/lib/list_sort.c](https://github.com/torvalds/linux/blob/master/lib/list_sort.c) ```c=129 /* * This mergesort is as eager as possible while always performing at least * 2:1 balanced merges. Given two pending sublists of size 2^k, they are * merged to a size-2^(k+1) list as soon as we have 2^k following elements. * * Thus, it will avoid cache thrashing as long as 3*2^k elements can * fit into the cache. Not quite as good as a fully-eager bottom-up * mergesort, but it does use 0.2*n fewer comparisons, so is faster in * the common case that everything fits into L1. */ ``` * 不同於一般對半切的 mergesort ，此 mergesort 盡可能採用 2:1 的比例合併，意思是當有 3 * 2^k^ 個元素存在時，會先將兩個 size 是 2^k^ 的 pending sublists ，合併成一個 size 是 2^k+1^ 的 list ，這個新合併的 list 跟剩下的 2^k^ 個元素剛好是 2:1 ，以此類推一直合併下去。 * 如果這 3 * 2^k^ 個元素可以剛好都在 cache 中，即可避免 cache thrashing 。 :::info TODO: 註解中寫到 "Not quite as good as a fully-eager bottom-up mergesort, but it does use 0.2 * n fewer comparisons" ，深入探討為何可以少 0.2 * n 次的比較。 ::: ```c=139 /* * The merging is controlled by "count", the number of elements in the * pending lists. This is beautifully simple code, but rather subtle. * * Each time we increment "count", we set one bit (bit k) and clear * bits k-1 .. 0. Each time this happens (except the very first time * for each bit, when count increments to 2^k), we merge two lists of * size 2^k into one list of size 2^(k+1). */ ``` * merge 是由變數 `count` 控制， `count` 為整個 list 的元素數量，其第 k 個 bit 代表現存大小為 2^k^ sublist 的數量。 * 當 count 每增加 1 時，set one bit (bit k) and clear bits k-1 .. 0 ，這邊的 bit k 指的是 the least-significant clear bit in count 。 * `count` 以二進位表示，遇到進位的情況，即表示有兩組相同的 2^k^ 個 sublists 要合併，連續進位表示連續合併。 ```c=196 /* * Data structure invariants: * - All lists are singly linked and null-terminated; prev * pointers are not maintained. * - pending is a prev-linked "list of lists" of sorted * sublists awaiting further merging. * - Each of the sorted sublists is power-of-two in size. * - Sublists are sorted by size and age, smallest & newest at front. * - There are zero to two sublists of each size. * - A pair of pending sublists are merged as soon as the number * of following pending elements equals their size (i.e. * each time count reaches an odd multiple of that size). * That ensures each later final merge will be at worst 2:1. * - Each round consists of: * - Merging the two sublists selected by the highest bit * which flips when count is incremented, and * - Adding an element from the input as a size-1 sublist. */ ``` 從註解中我們可以知道，在每圈迴圈中主要會做兩件事 : * 需要 merge 時，將兩個 sublist merge * 將新的 element 加入 pending 中 * `count` + 1 下方利用表格探討每次迴圈執行結果，舉 `count` = 0~16 為例 : | count decimal | count binary | sublist 4 | sublist 3 | sublist 2 | sublist 1 | new sublist | merge range | merge length | | ------------- | ------------ | --------- | --------- | --------- | --------- | ----------- | ----------- | ------------ | | 0 | 00000 | | | | | 1 | | | | 1 | 00001 | | | | 1 | 1 | | | | 2(merge) | 00010 | | | | 2 | 1 | [0,1] | 2 | | 3 | 00011 | | | 2 | 1 | 1 | | | | 4(merge) | 00100 | | | 2 | 2 | 1 | [2,3] | 2 | | 5(merge) | 00101 | | | 4 | 1 | 1 | [0,3] | 4 | | 6(merge) | 00110 | | | 4 | 2 | 1 | [4,5] | 2 | | 7 | 00111 | | 4 | 2 | 1 | 1 | | | | 8(merge) | 01000 | | 4 | 2 | 2 | 1 | [6,7] | 2 | | 9(merge) | 01001 | | 4 | 4 | 1 | 1 | [4,7] | 4 | | 10(merge) | 01010 | | 4 | 4 | 2 | 1 | [8,9] | 2 | | 11(merge) | 01011 | | 8 | 2 | 1 | 1 | [0,7] | 8 | | 12(merge) | 01100 | | 8 | 2 | 2 | 1 | [10,11] | 2 | | 13(merge) | 01101 | | 8 | 4 | 1 | 1 | [8,11] | 4 | | 14(merge) | 01110 | | 8 | 4 | 2 | 1 | [12,13] | 2 | | 15 | 01111 | 8 | 4 | 2 | 1 | 1 | | | | 16(merge) | 10000 | 8 | 4 | 2 | 2 | 1 | [14,15] | 2 | 其中，`pending` 是一個 list of lists 的結構，將所有等待 merge 的 sublist 串接起來，為了方便理解，我們將這些串接起來的 sublist 編號， sublist k 最大可串接 2^k^ 個元素，當到達容納上限，就會 merge ；而每次新增的 element 則會串接到 new sublist 。由上表我們可以發現 : * 當 `count` = 2 的冪 - 1 時不會 merge * merge length 在 2^k^-1 ~ 2^k+1^-1 之間的最大值會剛好落在 $$ (2^k-1) + (2^{k+1}-1) \over 2 $$ ### 效能評比將 [linux/lib/list_sort.c](https://github.com/torvalds/linux/blob/master/lib/list_sort.c) 中的 merge sort 抽出獨立成 [quiz2/list_sort.c](https://github.com/shanihsu/Linux_2021/blob/main/quiz2/list_sort.c) ，並嘗試對 [sysprog21/linux-list](https://github.com/sysprog21/linux-list) 中的 insert sort 與 quick sort 和 [quiz2/list_sort.c](https://github.com/shanihsu/Linux_2021/blob/main/quiz2/list_sort.c) 中的 merge sort 做效能評比 * 先使用 valgrind 測試 memory leak ，發現這三個 sort 均會出現以下的錯誤訊息，但他們執行後的排序結果均是正確的，進一步觀察發現這三個 sort 的錯誤訊息完全相同， heap 狀態也都一樣，這部份使用 gdb 偵錯還是找不出問題，不知道問題出在哪。 :::info TODO: 找出三個程式中 memory leak 的地方。 ::: ``` $ valgrind -v --leak-check=full ./list_sort ==67361== Memcheck, a memory error detector ==67361== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al. ==67361== Using Valgrind-3.15.0-608cb11914-20190413 and LibVEX; rerun with -h for copyright info ==67361== Command: ./list_sort ==67361== --67361-- Valgrind options: --67361-- -v --67361-- --leak-check=full --67361-- Contents of /proc/version: --67361-- Linux version 5.8.0-59-generic (buildd@lcy01-amd64-022) (gcc (Ubuntu 9.3.0-17ubuntu1~20.04) 9.3.0, GNU ld (GNU Binutils for Ubuntu) 2.34) #66~20.04.1-Ubuntu SMP Thu Jun 17 11:14:10 UTC 2021 --67361-- --67361-- Arch and hwcaps: AMD64, LittleEndian, amd64-cx16-lzcnt-rdtscp-sse3-ssse3-avx-avx2-bmi-f16c-rdrand --67361-- Page sizes: currently 4096, max supported 4096 --67361-- Valgrind library directory: /usr/lib/x86_64-linux-gnu/valgrind --67361-- Reading syms from /media/shani/0FEA0DDE0FEA0DDE/jserv/Linux_2021/quiz2/list_sort --67361-- Reading syms from /usr/lib/x86_64-linux-gnu/ld-2.31.so --67361-- Considering /usr/lib/x86_64-linux-gnu/ld-2.31.so .. --67361-- .. CRC mismatch (computed 975d0390 wanted 30bd717f) --67361-- Considering /lib/x86_64-linux-gnu/ld-2.31.so .. --67361-- .. CRC mismatch (computed 975d0390 wanted 30bd717f) --67361-- Considering /usr/lib/debug/lib/x86_64-linux-gnu/ld-2.31.so .. --67361-- .. CRC is valid --67361-- Reading syms from /usr/lib/x86_64-linux-gnu/valgrind/memcheck-amd64-linux --67361-- object doesn't have a symbol table --67361-- object doesn't have a dynamic symbol table --67361-- Scheduler: using generic scheduler lock implementation. --67361-- Reading suppressions file: /usr/lib/x86_64-linux-gnu/valgrind/default.supp ==67361== embedded gdbserver: reading from /tmp/vgdb-pipe-from-vgdb-to-67361-by-shani-on-??? ==67361== embedded gdbserver: writing to /tmp/vgdb-pipe-to-vgdb-from-67361-by-shani-on-??? ==67361== embedded gdbserver: shared mem /tmp/vgdb-pipe-shared-mem-vgdb-67361-by-shani-on-??? ==67361== ==67361== TO CONTROL THIS PROCESS USING vgdb (which you probably ==67361== don't want to do, unless you know exactly what you're doing, ==67361== or are doing some strange experiment): ==67361== /usr/lib/x86_64-linux-gnu/valgrind/../../bin/vgdb --pid=67361 ...command... ==67361== ==67361== TO DEBUG THIS PROCESS USING GDB: start GDB like this ==67361== /path/to/gdb ./list_sort ==67361== and then give GDB the following command ==67361== target remote | /usr/lib/x86_64-linux-gnu/valgrind/../../bin/vgdb --pid=67361 ==67361== --pid is optional if only one valgrind process is running ==67361== --67361-- REDIR: 0x4022e10 (ld-linux-x86-64.so.2:strlen) redirected to 0x580c9ce2 (???) --67361-- REDIR: 0x4022be0 (ld-linux-x86-64.so.2:index) redirected to 0x580c9cfc (???) --67361-- Reading syms from /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_core-amd64-linux.so --67361-- object doesn't have a symbol table --67361-- Reading syms from /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so --67361-- object doesn't have a symbol table ==67361== WARNING: new redirection conflicts with existing -- ignoring it --67361-- old: 0x04022e10 (strlen ) R-> (0000.0) 0x580c9ce2 ??? --67361-- new: 0x04022e10 (strlen ) R-> (2007.0) 0x0483f060 strlen --67361-- REDIR: 0x401f5f0 (ld-linux-x86-64.so.2:strcmp) redirected to 0x483ffd0 (strcmp) --67361-- REDIR: 0x4023370 (ld-linux-x86-64.so.2:mempcpy) redirected to 0x4843a20 (mempcpy) --67361-- Reading syms from /usr/lib/x86_64-linux-gnu/libc-2.31.so --67361-- Considering /usr/lib/x86_64-linux-gnu/libc-2.31.so .. --67361-- .. CRC mismatch (computed 86b78530 wanted e380f01c) --67361-- Considering /lib/x86_64-linux-gnu/libc-2.31.so .. --67361-- .. CRC mismatch (computed 86b78530 wanted e380f01c) --67361-- Considering /usr/lib/debug/lib/x86_64-linux-gnu/libc-2.31.so .. --67361-- .. CRC is valid --67361-- REDIR: 0x4900600 (libc.so.6:memmove) redirected to 0x48311d0 (_vgnU_ifunc_wrapper) --67361-- REDIR: 0x48ff900 (libc.so.6:strncpy) redirected to 0x48311d0 (_vgnU_ifunc_wrapper) --67361-- REDIR: 0x4900930 (libc.so.6:strcasecmp) redirected to 0x48311d0 (_vgnU_ifunc_wrapper) --67361-- REDIR: 0x48ff220 (libc.so.6:strcat) redirected to 0x48311d0 (_vgnU_ifunc_wrapper) --67361-- REDIR: 0x48ff960 (libc.so.6:rindex) redirected to 0x48311d0 (_vgnU_ifunc_wrapper) --67361-- REDIR: 0x4901dd0 (libc.so.6:rawmemchr) redirected to 0x48311d0 (_vgnU_ifunc_wrapper) --67361-- REDIR: 0x491ce60 (libc.so.6:wmemchr) redirected to 0x48311d0 (_vgnU_ifunc_wrapper) --67361-- REDIR: 0x491c9a0 (libc.so.6:wcscmp) redirected to 0x48311d0 (_vgnU_ifunc_wrapper) --67361-- REDIR: 0x4900760 (libc.so.6:mempcpy) redirected to 0x48311d0 (_vgnU_ifunc_wrapper) --67361-- REDIR: 0x4900590 (libc.so.6:bcmp) redirected to 0x48311d0 (_vgnU_ifunc_wrapper) --67361-- REDIR: 0x48ff890 (libc.so.6:strncmp) redirected to 0x48311d0 (_vgnU_ifunc_wrapper) --67361-- REDIR: 0x48ff2d0 (libc.so.6:strcmp) redirected to 0x48311d0 (_vgnU_ifunc_wrapper) --67361-- REDIR: 0x49006c0 (libc.so.6:memset) redirected to 0x48311d0 (_vgnU_ifunc_wrapper) --67361-- REDIR: 0x491c960 (libc.so.6:wcschr) redirected to 0x48311d0 (_vgnU_ifunc_wrapper) --67361-- REDIR: 0x48ff7f0 (libc.so.6:strnlen) redirected to 0x48311d0 (_vgnU_ifunc_wrapper) --67361-- REDIR: 0x48ff3b0 (libc.so.6:strcspn) redirected to 0x48311d0 (_vgnU_ifunc_wrapper) --67361-- REDIR: 0x4900980 (libc.so.6:strncasecmp) redirected to 0x48311d0 (_vgnU_ifunc_wrapper) --67361-- REDIR: 0x48ff350 (libc.so.6:strcpy) redirected to 0x48311d0 (_vgnU_ifunc_wrapper) --67361-- REDIR: 0x4900ad0 (libc.so.6:memcpy@@GLIBC_2.14) redirected to 0x48311d0 (_vgnU_ifunc_wrapper) --67361-- REDIR: 0x491e0d0 (libc.so.6:wcsnlen) redirected to 0x48311d0 (_vgnU_ifunc_wrapper) --67361-- REDIR: 0x491c9e0 (libc.so.6:wcscpy) redirected to 0x48311d0 (_vgnU_ifunc_wrapper) --67361-- REDIR: 0x48ff9a0 (libc.so.6:strpbrk) redirected to 0x48311d0 (_vgnU_ifunc_wrapper) --67361-- REDIR: 0x48ff280 (libc.so.6:index) redirected to 0x48311d0 (_vgnU_ifunc_wrapper) --67361-- REDIR: 0x48ff7b0 (libc.so.6:strlen) redirected to 0x48311d0 (_vgnU_ifunc_wrapper) --67361-- REDIR: 0x4908d20 (libc.so.6:memrchr) redirected to 0x48311d0 (_vgnU_ifunc_wrapper) --67361-- REDIR: 0x49009d0 (libc.so.6:strcasecmp_l) redirected to 0x48311d0 (_vgnU_ifunc_wrapper) --67361-- REDIR: 0x4900550 (libc.so.6:memchr) redirected to 0x48311d0 (_vgnU_ifunc_wrapper) --67361-- REDIR: 0x491cab0 (libc.so.6:wcslen) redirected to 0x48311d0 (_vgnU_ifunc_wrapper) --67361-- REDIR: 0x48ffc60 (libc.so.6:strspn) redirected to 0x48311d0 (_vgnU_ifunc_wrapper) --67361-- REDIR: 0x49008d0 (libc.so.6:stpncpy) redirected to 0x48311d0 (_vgnU_ifunc_wrapper) --67361-- REDIR: 0x4900870 (libc.so.6:stpcpy) redirected to 0x48311d0 (_vgnU_ifunc_wrapper) --67361-- REDIR: 0x4901e10 (libc.so.6:strchrnul) redirected to 0x48311d0 (_vgnU_ifunc_wrapper) --67361-- REDIR: 0x4900a20 (libc.so.6:strncasecmp_l) redirected to 0x48311d0 (_vgnU_ifunc_wrapper) --67361-- REDIR: 0x49e8490 (libc.so.6:__strrchr_avx2) redirected to 0x483ea10 (rindex) --67361-- REDIR: 0x48fa260 (libc.so.6:malloc) redirected to 0x483b780 (malloc) --67361-- REDIR: 0x49eb650 (libc.so.6:__mempcpy_avx_unaligned_erms) redirected to 0x4843660 (mempcpy) --67361-- REDIR: 0x49eb670 (libc.so.6:__memcpy_avx_unaligned_erms) redirected to 0x48429f0 (memmove) --67361-- REDIR: 0x48fa850 (libc.so.6:free) redirected to 0x483c9d0 (free) --67361-- REDIR: 0x49e82a0 (libc.so.6:__strchrnul_avx2) redirected to 0x4843540 (strchrnul) ==67361== ==67361== HEAP SUMMARY: ==67361== in use at exit: 0 bytes in 0 blocks ==67361== total heap usage: 257 allocs, 257 frees, 7,168 bytes allocated ==67361== ==67361== All heap blocks were freed -- no leaks are possible ==67361== ==67361== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0) ``` 由於原本要做效能評比的三個 sort 目前還找不到 memory leak 的原因，沒辦法進一步做分析 cache 效益，但仍有嘗試使用以下工具 :::info TODO: 解決上述三個 sort memory leak 問題之後，再重新利用以下工具進行效能評比與 cache 效益分析。 ::: * 使用 perf 比較三個 sort 的 cache miss ``` $ sudo sh -c " echo -1 > /proc/sys/kernel/perf_event_paranoid" $ perf stat --repeat 6 -e cache-misses,cache-references,instructions,cycles,L1-dcache-load-misses ./list_sort ``` - [ ] merge sort in Linux kernel ``` Performance counter stats for './list_sort' (6 runs): 1,6311 cache-misses # 29.129 % of all cache refs ( +- 11.83% ) 5,5997 cache-references ( +- 2.07% ) 131,8244 instructions # 1.04 insn per cycle ( +- 0.31% ) 126,6532 cycles ( +- 1.37% ) 1,4966 L1-dcache-load-misses ( +- 2.14% ) 0.0013360 +- 0.0000469 seconds time elapsed ( +- 3.51% ) ``` - [ ] insert sort ``` Performance counter stats for './examples/insert-sort' (6 runs): 2,7948 cache-misses # 47.922 % of all cache refs ( +- 5.11% ) 5,8320 cache-references ( +- 2.57% ) 182,6139 instructions # 1.12 insn per cycle ( +- 0.19% ) 163,5738 cycles ( +- 1.82% ) 1,5430 L1-dcache-load-misses ( +- 2.83% ) 0.0018266 +- 0.0000739 seconds time elapsed ( +- 4.04% ) ``` - [ ] quick sort ``` Performance counter stats for './examples/quick-sort' (6 runs): 1,4498 cache-misses # 25.137 % of all cache refs ( +- 12.04% ) 5,7675 cache-references ( +- 2.51% ) 148,7628 instructions # 1.08 insn per cycle ( +- 0.22% ) 138,1092 cycles ( +- 1.66% ) 1,5233 L1-dcache-load-misses ( +- 2.50% ) 0.001906 +- 0.000127 seconds time elapsed ( +- 6.64% ) ``` 對於目前有 memory leak 的三個 sort 程式而言，觀察到 cache miss 的比例為 insert sort > merge sort in Linux kernel > quick sort 。 * 使用 Cachegrind 觀察 merge sort in Linux kernel 的 cache 狀況 ``` $ valgrind --tool=cachegrind ./list_sort ``` ``` ==68266== Cachegrind, a cache and branch-prediction profiler ==68266== Copyright (C) 2002-2017, and GNU GPL'd, by Nicholas Nethercote et al. ==68266== Using Valgrind-3.15.0 and LibVEX; rerun with -h for copyright info ==68266== Command: ./list_sort ==68266== --68266-- warning: L3 cache found, using its data for the LL simulation. ==68266== ==68266== I refs: 740,995 ==68266== I1 misses: 1,199 ==68266== LLi misses: 1,173 ==68266== I1 miss rate: 0.16% ==68266== LLi miss rate: 0.16% ==68266== ==68266== D refs: 309,024 (200,368 rd + 108,656 wr) ==68266== D1 misses: 3,377 ( 2,570 rd + 807 wr) ==68266== LLd misses: 2,829 ( 2,087 rd + 742 wr) ==68266== D1 miss rate: 1.1% ( 1.3% + 0.7% ) ==68266== LLd miss rate: 0.9% ( 1.0% + 0.7% ) ==68266== ==68266== LL refs: 4,576 ( 3,769 rd + 807 wr) ==68266== LL misses: 4,002 ( 3,260 rd + 742 wr) ==68266== LL miss rate: 0.4% ( 0.3% + 0.7% ) ``` 我們可以進一步了解程式碼每一行的 cache 狀況 ``` $ cg_annotate --auto=yes cachegrind.out.68266 ``` 得到[結果](https://github.com/shanihsu/Linux_2021/blob/main/quiz2/cache_detail.txt)，並從中觀察此 merge sort 對 cache 的效益。 :::info TODO : 1. 設計效能評比程式 2. 完成 quiz1 ，將在 quiz1 提出的改進實作，和 Linux 核心的 lib/list_sort.c 進行效能比較 3. 使用 ==[Cachegrind](https://valgrind.org/docs/manual/cg-manual.html)== 工具分析 cache 效益 :::

Read more

2021-04-06 `shanihsu`

2021q1 Homework1 (lab0)