2021q1 Homework2 (quiz2)

# 2021q1 Homework2 (quiz2) contributed by < `RainbowEye0486` > ###### tags: `面試` > [題目](https://hackmd.io/@sysprog/linux2021-quiz2) ## 測驗一 ### 解釋上述程式碼運作原理，指出改進空間並著手實作 ```cpp #define container_of(ptr, type, member) \ __extension__({ \ const __typeof__(((type *) 0)->member) *__pmember = (ptr); \ (type *) ((char *) __pmember - offsetof(type, member)); \ }) ``` `__extension__` 的作用透過查詢 [gcc(1) linux man page](https://linux.die.net/man/1/gcc) 得到敘述: > -pedantic does not cause warning messages for use of the alternate keywords whose names begin and end with __. Pedantic warnings are also disabled in the expression that follows "\_\_extension\_\_". However, only system header files should use these escape routes; application programs should avoid them. 因為編譯時，透過 `-pedantic` 選項 gcc 會主動警示不符合 ANSI 規範的程式碼，而這個操作會使一些 C 的擴展函式庫無法使用，但是我們如果使用 `__extension__` ，系統便不會報錯。首先分析第一個出現的函式 `get_middle` 目的是要找到一個 doubly linked list 中間的節點: ```cpp 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)//COND1 || COND2 break; fast = fast->next->next; } return list_entry(slow, list_ele_t, list);//TTT } ``` - 一開始的時候，先把 `fast` 跟 `slow` 同時設為第一個 node ，並且把 `slow` 當作迴圈的迭代條件(在 #define 裡面)，所以下面只看到 `fast = fast->next->next` ，也就是 `fast` 移動了兩個 node ，卻沒有看到 `slow` 移動的原因。這邊找到中點的辦法是 [Floyd Cycle Detection Algorithm](https://medium.com/@orionssl/%E6%8E%A2%E7%B4%A2-floyd-cycle-detection-algorithm-934cdd05beb9) ，又稱我們常見的**龜兔賽跑演算法**，當 `fast` 跑到 linked list 的最尾端的時候，速度是他一半的 `slow` 跑到整個 linked list 的一半。整個迴圈的終止條件是 ==**fast->next == list**== 以及 ==**fast->next->next == list**== ，代表 `fast` 走到尾端(分別是總共 node 數是奇數或是偶數) - 因為想要知道的是中間節點的指標，所以在 `list_entry` 中參數傳入 ==**TTT = slow**== ```cpp 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` ，分別是原本待切割的 list 、切一半之後要放的目標 list 以及切割的 node 。首先排除不需要切割的情形( `head_from` 只有一個節點，就是切割點或是 `head_from` 為空)，再將 `*node` 之後的 list 移動到 `list_to`。 ```cpp 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); } ``` - 如果 `*lhs` 或 `*rhs` 其中一個是 empty ，把另一個直接加到 `head` 的尾端 - `*lhs` `*rhs` 各取一個 node 出來比較大小，比較小的先加入尾端，繼續比較直到其中一個 list 空了為止，另一個剩下 node 再全部加到 `head` 的尾端 - 這個部分是排序法"**合併**"的部分關於 mergeSort 運作的程式碼: ```cpp 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, &get_middle(&q->list)->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); } ``` - 每次開始前先檢查 queue 裡面的元素是不是只剩下一個或是空了，直接回傳不用排 - 從中間分割，選 ==**&get_middle(&q->list)->list**== 的原因是在 `list_ele_t` 中放置的是 `list_head head` ，所以需要多加一個 & 去取址，而 `&q->list` 內部放置的 element 是 `list_ele_t` ，用 `&q->list` 去取得這個 element 。 - 分別兩端遞迴排序之後合併存放在 `sorted` ```graphviz digraph G { compound=true; node [ fontname="Handlee" ]; subgraph cluster_b { node [shape=record]; label = "queue_t" subgraph cluster_head { label="list_ele_t *head"; shape=none; node [shape=record]; head [label="{value|*next}"]; subgraph cluster_list { label="list_head *list"; node [shape=record]; list_head [label="{*prev|*next}"]; } } list_ele1 [label="size"]; subgraph cluster_tail { label="list_ele_t *tail"; node [shape=record]; tail [label="{value|*next}"]; subgraph cluster_list { label="list_head *list"; node [shape=record]; list_tail [label="{*prev|*next}"]; } } subgraph cluster_list { label="list_head *list"; node [shape=record]; list [label="{*prev|*next}"]; } } } ``` 原先的資料結構如上圖，雖然我們知道 `queue_t q` 只會創建一次，但是**使用上不直觀** 然而這段程式碼主要使用的資料結構是 double linked list ，這個資料結構透過對 `list_head` 的操作，既可以用 `prev` 操作尾端 node 也可以用 `next` 操作前端，不僅是讀取，更可以動態的新增或是刪除節點，因此 double linked list 的功能足以替代 queue 的作用。並且 `list_ele_t` 中的 `*next` 也可以去除。 **將 `queue_t` 移除** 將 `queue_t` 移除的時候，必須要改變節點之間串連的方式，我的作法是只用一個 `list_head` 去紀錄開頭串列，每次需要傳入其他函數的時候傳入 `list_head` 。但是在分割成兩半的時候為了能夠將 `lhs` 和 `rhs` 能夠把各自擁有的 head 傳入下一個遞迴，所以多使用了一個 `list_head` ```cpp struct list_head *list_r = new_head(); list_r->value = "head"; list_cut_position(list_r, list_l, &get_middle(list_l)->list); list_merge_sort(list_r); list_merge_sort(list_l); list_merge(list_l, list_r, list_l); ``` ```graphviz digraph G { compound=true; node [ fontname="Handlee" ]; subgraph cluster_list { label="list_head *head"; node [shape=record]; list [label="{*prev|*next}"]; } subgraph cluster_head { label="list_ele_t"; shape=none; node [shape=record]; head [label="{value}"]; subgraph cluster_list { label="list_head *list"; node [shape=record]; list_head [label="{*prev|*next}"]; } } subgraph cluster_tail { label="list_ele_t"; node [shape=record]; tail [label="{value}"]; subgraph cluster_list { label="list_head *list"; node [shape=record]; list_tail [label="{*prev|*next}"]; } } } ``` ### 利用 Perf 檢測效能變化執行 ```shell $ sudo perf stat ./mergeSort ``` 原本的 `mergeSort` 執行完之後的結果： ```shell Performance counter stats for './mergeSort': 83.64 msec task-clock # 0.991 CPUs utilized 0 context-switches # 0.000 K/sec 0 cpu-migrations # 0.000 K/sec 1,479 page-faults # 0.018 M/sec 169,676,875 cycles # 2.029 GHz 236,828,442 instructions # 1.40 insn per cycle 37,931,896 branches # 453.522 M/sec 915,883 branch-misses # 2.41% of all branches 0.084362295 seconds time elapsed 0.076350000 seconds user 0.008036000 seconds sys ``` 經過優化實做後得到結果 ```shell Performance counter stats for './mSort_improve': 52.46 msec task-clock # 0.995 CPUs utilized 0 context-switches # 0.000 K/sec 0 cpu-migrations # 0.000 K/sec 2,542 page-faults # 0.048 M/sec 192,778,361 cycles # 3.675 GHz 257,618,429 instructions # 1.34 insn per cycle 41,046,788 branches # 782.490 M/sec 931,736 branch-misses # 2.27% of all branches 0.052720136 seconds time elapsed 0.052743000 seconds user 0.000000000 seconds sys ``` 分析兩者的差異，可以發現總執行時間提昇了約 37% 的效能，但是 branches 跟 page-faults 數量皆上升 ![](https://i.imgur.com/q9XsXAI.png) :::spoiler 記憶體分析 ### 搭配 Valgrind 以及 massif 視覺化記憶體消耗情形當我們直接運行給定的程式碼，並且用 Valgrind 做記憶體分析的時候執行 ```shell= valgrind -q --tool=massif --stacks=yes --time-unit=i --massif-out-file=massif.out ./mergeSort ``` ![](https://i.imgur.com/gGO73HH.png) 實做完之後的成果 ![](https://i.imgur.com/G5wmRkf.png) 發現記憶體用量不降反升，可能是實做過程中有未釋放的記憶體，原因是下方橘色那塊在 insert list_head 的時候沒有釋放記憶體的原因 ::: ### 研讀 Linux 核心的 [lib/list_sort.c](https://github.com/torvalds/linux/blob/master/lib/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) 的使用層級應用程式，並設計效能評比的程式碼，說明 Linux 核心的 [lib/list_sort.c](https://github.com/torvalds/linux/blob/master/lib/list_sort.c) 最佳化手法 :::success TODO ::: ### 將你在 [quiz1](https://hackmd.io/@sysprog/linux2021-quiz1) 提出的改進實作，和 Linux 核心的 [lib/list_sort.c](https://github.com/torvalds/linux/blob/master/lib/list_sort.c) 進行效能比較，需要提出涵蓋足夠廣泛的 benchmark :::success TODO ::: --- ## 測驗二 ```cpp= uint16_t func(uint16_t N) { /* change all right side bits to 1 */ N |= N >> 1; N |= N >> 2; N |= N >> 4; N |= N >> 8; return (N + 1) >> 1; } ``` 這邊最主要 bitwise 操作的方式是 `|=` ，代表的是對某個位元 set bit | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | 我們先假設一開始的時候最高位元位於 bit 14 的位置，在這裡我只特別標註最高位，因為後面的 bit 不管是0或者是1之後都會被覆蓋掉，所以先假設都是0 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | 執行到 `N |= N >> 1` | 0 | 0 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | 執行到`N |= N >> 2;` | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | 執行到 `N |= N >> 4;` |0|0|1|1|1|1|1|1|1|1|1|1|1|1|1|1| | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | 執行到`N |= N >> 8;` ，不難發現以 MSB 往後每一個 bit 都被 set ，利用的就是類似將最高位元 **"複製"** ，向後 **"貼上"** ，再重複直到往後所有 bit 都被設定為 1 。總結下來，這段程式碼做的事情是先用位元覆蓋形成 $2^{MSB+1}-1$ 的形式，所以最後一行執行 `+ 1 >> 2` 的動作， ### overflow 的處理不難觀察出，這段程式碼在 MSB 為 1 (1001010...)的時候在第 8 行之前會得到全部都是 1 的結果。這也代表如果執行到第 8 行的時候， `return (N + 1) >> 1` ， $N+1$ 會直接 overflow 變成全部都是0。所以這邊我的想法是 |1|1|1|1|1|1|1|1|1|1|1|1|1|1|1|1| | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | 先向右位移 $>>1$ |0|1|1|1|1|1|1|1|1|1|1|1|1|1|1|1| | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | 再加一，得到的結果會是一樣的 |1|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0| | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | ### 在 [The Linux Kernel API](https://www.kernel.org/doc/html/latest/core-api/kernel-api.html) 頁面搜尋 `power of 2`，可見 `is_power_of_2`，查閱 Linux 核心原始程式碼，舉例說明其作用和考量，特別是 `round up/down power of 2` 查閱 [linux/log2.h](https://github.com/torvalds/linux/blob/master/include/linux/log2.h) 的 `is_power_of_2` ```cpp bool is_power_of_2(unsigned long n) { return (n != 0 && ((n & (n - 1)) == 0)); } ``` 如果是2的冪次的話， bit 排列形式必定只有一個也只存在一個 set bit ，因為二進位每個位元都代表 $2^{bit位置}$ ，所以 $2^N-1$ 從位元的角度去看就會是從 MSB 開始全部反轉的結果，舉例 |0|0|0|0|1|0|0|0|0|0|0|0|0|0|0|...| | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | $-1$ 後 |0|0|0|0|0|1|1|1|1|1|1|1|1|1|1|...| | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | 這時候將 $n-1$ 和 $n$ `&` 操作之後得到的就會都是0。好處是 Bitwise operation 在硬體實作上實現較為直覺(根據邏輯閘到 assembly code 等底層的運作方式)，可以讓運算所需的 mechine code 指令數更加簡短。 ```cpp unsigned long __roundup_pow_of_two(unsigned long n) { return 1UL << fls_long(n - 1); } ``` ```cpp unsigned long __rounddown_pow_of_two(unsigned long n) { return 1UL << (fls_long(n) - 1); } ``` [linux/bitops.h](https://github.com/torvalds/linux/blob/master/include/linux/bitops.h)中提到 `fls_long` 回傳 `fls` / `fls64` ，這邊是根據不同機器上編譯是將 `unsigned long` 當作 32 bit 還是 64 bit 去處理 ```cpp static inline unsigned fls_long(unsigned long l) { if (sizeof(l) == 4) return fls(l); return fls64(l); } ``` 繼續追蹤甚麼是 `fls` ，然後在 [linux/bitops/fls.h](https://github.com/torvalds/linux/blob/master/include/asm-generic/bitops/fls.h) 中找到定義 ```cpp static __always_inline int fls(unsigned int x) { int r = 32; if (!x) return 0; if (!(x & 0xffff0000u)) { x <<= 16; r -= 16; } if (!(x & 0xff000000u)) { x <<= 8; r -= 8; } if (!(x & 0xf0000000u)) { x <<= 4; r -= 4; } if (!(x & 0xc0000000u)) { x <<= 2; r -= 2; } if (!(x & 0x80000000u)) { x <<= 1; r -= 1; } return r; } ``` 做的事情是透過 bit mask 的方式過濾掉前面的 0 ，從而達到計算 MSB 的位元位置，而 `fls64` 的區別是使用的 bit mask 比較長，位移的次數多一次(先切32、16、8....)。 `__roundup_pow_of_two` 以及 `__roundup_pow_of_two` 的區別是對於 $2^N+1$ ~ $2^{N+1}$ 這個區間的所有數在 `__roundup_pow_of_two` 中會被進位成 $2^{N+1}$ (向上進位)，而 `__roundup_pow_of_two` 則只會進位為 $2^N$ (向下進位)，在 linux kernel 的考量中一直是以兼具效能、效率且不失優雅當作設計前提，我們可以看到以上例子包括函式引用都是以比較貼近硬體語言的方式實作，像是位移或是 `&` `|` 這類的運算，比起使用減法的速度還要快 ### 研讀 [slab allocator](https://en.wikipedia.org/wiki/Slab_allocation)，探索 Linux 核心的 slab 實作，找出運用 power-of-2 的程式碼和解讀為了瞭解甚麼是 slab allocator ，我參考了[多圖詳解 linux 記憶體分配器 slab](https://www.ipshop.xyz/8168.html) 這篇文章以及維基百科上的定義。原先 linux 使用的記憶體申請是基於 [buddy system](https://en.wikipedia.org/wiki/Buddy_memory_allocation) ，分配和管理都是以一個 page 作為單位，適用在大記憶體的分配，但是假設今天我們只需要 20 byte 的空間，而 buddy system 分配給我們一整個 page ，是不是會浪費許多空間以及造成 internal fragmentation ?所以 slab 為了改善這個問題，針對 buddy system 分配的一個或是多個連續的 page 再進一步切割成一個個對齊的 object ，再由 slab 包起來統一管理，文章中提到一個生動的比喻: > 什麼是 slab cache pool 呢？我的解釋是使用 struct kmem_cache 結構描述的一段記憶體就稱作一個 slab cache pool 。一個 slab cache pool 就像是一箱牛奶，一箱牛奶中有很多瓶牛奶，每瓶牛奶就是一個 object 。分配記憶體的時候，就相當於從牛奶箱中拿一瓶。總有拿完的一天。當箱子空的時候，你就需要去超市再買一箱回來。超市就相當於 partial linked list ，超市儲存著很多箱牛奶。如果超市也賣完了，自然就要從廠家進貨，然後出售給你。廠家就相當於 buddy system。 > [name=節錄自多圖詳解Linux記憶體分配器slub] ![](https://i.imgur.com/6ueydje.jpg) - **slab 狀態:**“ full ”、“ partial ”、“ free ” 三種，如果是 free 的狀態，一般來說還不需要被加進 partial 這個 linked list 之中，如果內部的 object 有一部分被用到、有一部分還可以使用，可能會被串進 partial linked list 之中，而當空間都已經使用完畢的 full slabs 就會像圖片的右下角一樣，不會被任何 linked list 管理，除非記憶體空間被釋放。 - **page**: 紀錄 slab 內部 object 的使用情形，哪些是可以使用的(freelist )，哪些是不能的( inuse )。 - **kmem_cache_create** :主要是填充 kmem_cache 成員，創建kmem_cache的時候需要指出 object 的 size 和對齊 align 作為參數輸入 - **kmem_cache_cpu** :分配給每個 CPU ，主要目的是管理 object 的分配以及釋放， `page` 管理的是 CPU 正在操作的 page ，如果記憶體分配失敗(像是 full 的情形)，會去 partial linked list 中尋找另一個替代的 slab 來用。如果 full slab 堆當中有記憶體被釋放出來的話，可以重新加入 cache_cpu 的 partial linked list 中，但是如果 partial linked list 已經滿了，則加入到 cache_node 的 partial 之中。 - **kmem_cache_node** :管理大部分 partial 的 slab ，這些 slab 用 `nr_partial` linked list 串接起來。和 `kmem_cache_cpu` 最大的區別是 `kmem_cache_cpu` 是每個 CPU 獨享 slab ，但是 `kmem_cache_node` 是 CPU 們共享的。我把他理解成類似第二層快取池的概念 [linux/slab.c](https://github.com/torvalds/linux/blob/master/mm/slab.c) 中 `__kmem_cache_create` 中在開啟 `FORCE_DEBUG` 模式的時候有一段偵測的程式碼 ```cpp=1929 #if DEBUG #if FORCED_DEBUG /* * Enable redzoning and last user accounting, except for caches with * large objects, if the increased size would increase the object size * above the next power of two: caches with object sizes just above a * power of two have a significant amount of internal fragmentation. */ if (size < 4096 || fls(size - 1) == fls(size-1 + REDZONE_ALIGN + 2 * sizeof(unsigned long long))) flags |= SLAB_RED_ZONE | SLAB_STORE_USER; if (!(flags & SLAB_TYPESAFE_BY_RCU)) flags |= SLAB_POISON; #endif #endif ``` > %SLAB_RED_ZONE - Insert 'Red' zones around the allocated memory to check for buffer overruns. > %SLAB_POISON - Poison the slab with a known test pattern (a5a5a5a5) to catch references to uninitialised memory. 這邊提到了 `redzone` 的概念，在 quiz1 時也出現過， `redzone` 的作用是檢測記憶體是否越界 (out_of_bounds)，所以會在分配出去的記憶體尾端加上一些特殊的辨識位元組合，只要這段特殊的組合被修改過，那就代表寫入位置超出分配空間，可能會汙染到其他被分配的記憶體。而這段程式碼的意思是如果比較大的 object 再加上 redzoning 和 last user accounting (包含在 object 內)的空間後整個 object 大小的數量級會超過下一個2的冪次，可能會造成許多的內部碎片空間浪費。用到 `power_of_2` 的概念是 `fls(size - 1)` 跟 `fls(size-1 + REDZONE_ALIGN + 2 * sizeof(unsigned long long)))` 之間的數量級比較，觀察加上額外配置的記憶體空間後是不是會進位。 :::success **Question:** ~~有點~~不明白為什麼要 size-1 而不是直接用 size 就好? > 「不明白」就說「不明白」，不要加「有點」，裝可愛無助於溝通。為何不做實驗呢？與其「舉燭」，不如實證。 > :notes: jserv >已補上實驗及後續的討論 >[name=RainbowEye0486] ::: :::info 實驗內容: - 重新理解註解，這個 slab 如果想要允許 redzone 空間以及多分配一個 word 的空間讓使用者儲存要求(看上下文推測是使用者對這個 slab 的註記)，第一是它的空間夠小，所以4096以下都是可以被接受的，如果超過這個大小( linux 默認的 page 大小)，系統就會考慮加上這一小段空間會不會超過下一個2的數量級，如果超過的話每個 kmem_cache_node 在記憶體對齊的時候就無法以最省空間的 page 對齊。如果夠小且加上這一段空間不會超過下個2的數量級，則可以配置 RED_ZONE 跟 STORE_USER - 首先，猜測可能為了處理邊界條件所以才使用了 size-1 而非 size ，經過測試，在我的電腦上 `2 * sizeof(unsigned long long)` 的大小是 16 ，輸入 `size = 8192` ，也就是 $2^{13}$ ，這代表我們剛剛好可以用 2 page 來做記憶體對齊； `REDZONE_ALIGN = 2` 當作測試條件 ```cpp= int size = 8192; bool flag = false; int REDZONE_ALIGN = 2; if (size < 4096 || fls(size - 1) == fls(size-1 + REDZONE_ALIGN + 2 * sizeof(unsigned long long))) flag = true; printf("%d\n",fls(size - 1)); printf("%d\n",fls(size-1 + REDZONE_ALIGN + 2 * sizeof(unsigned long long))); printf("%d",flag); ``` 輸出結果: >13 14 0 顯然加上需要額外配置的18 byte 後突破了下一個數量級到了 $2^{14}$，這樣就只能用比原先的 2 page 還要多的 page 來對齊。改用 `size = 8193` 進行測試之後的輸出: >14 >14 >1 `flag` 成功被修改了，表示可以配置新增的記憶體，因為原本的 kmem_cache_node 大小用兩個 page 就已經塞不下了，所以多配置一點記憶體也不會影響太多效能。這也說明了為什麼使用 `size-1` 而非 `size` ，因為在 `size` 剛好等於 $2^N$ 的時候，是可以剛好以 page 對齊的，但是數量級來說， $2^N$ 會跟 $(2^N+想多配置的記憶體)$ 一樣大，為了要讓兩者的數量級差一級，所以才會刻意減一。 ::: [linux/slab_commom.c](https://github.com/torvalds/linux/blob/master/mm/slab_common.c) 裡面 `create_boot_cache()` 中的一段程式碼 ```cpp=616 /* * For power of two sizes, guarantee natural alignment for kmalloc * caches, regardless of SL*B debugging options. */ if (is_power_of_2(size)) align = max(align, size); s->align = calculate_alignment(flags, align, size); s->useroffset = useroffset; s->usersize = usersize; err = __kmem_cache_create(s, flags); ``` `natural alignment` (自然對齊)方式是直接對齊該資料型態本身的大小，32位元的整數以4 byte 對齊、64位元的 long 則以8 byte 對齊。換句話說，**8-byte aligned**代表該物件的記憶體位址是8的倍數，記憶體地址的後三碼會是000，這種情況下 CPU 能最有效地執行對記憶體的讀寫操作。而這段程式碼的內容就是說初始化時，當第一個 `kmem_cache` 被創建的時候，對 `kmem_cache_node` 大小判斷，這時候分成兩種情況: 1. 用原先設定的 `align` 大小來對齊，預設大小是 \_\_alignof\_\_(unsigned long long) ，以64位元對齊 2. 特別對 size 是 $2^N$ (冪次)進行處理，確保快取可以以 N-byte 對齊假如 $2^N$ 比 `align` 大，則以 N-byte 對齊，否則維持原本的64位元對齊 :::warning 修正上方漢語描述，至少該通順。 :notes: jserv > 已修正 > [name=RainbowEye0486] ::: --- ## 測驗三 ### 解釋上述程式碼運作原理，並嘗試重寫為同樣功能但效率更高的實作 ```cpp size_t read_lhs = _read & 7; size_t read_rhs = 8 - read_lhs; ``` `_read & 7 = _read % 8` 的原因是只有倒數三個 bit 會被保留下來，其他的因為`&0`運算的關係會直接 set 成 0 ，所以相當於對8取餘數。會這麼做的原因是希望以 byte 對齊，如果取完以8為模數的餘數之後仍然有餘數，代表 `_read` 沒有對齊 ```cpp size_t read_lhs = _read & 7; size_t read_rhs = 8 - read_lhs; const uint8_t *source = (const uint8_t *) _src + (_read / 8); size_t write_lhs = _write & 7; size_t write_rhs = 8 - write_lhs; uint8_t *dest = (uint8_t *) _dest + (_write / 8); ``` - `*source` :指向原先 `_src` 8 byte 中開始讀取的那個 byte - `*dest` :指向 `_dest` 8 byte 中開始寫入的那個 byte `*source = (const uint8_t *) _src + (_read / 8)` 以及隨後的 `*dest` 都是在確認要從哪個地址開始去取 byte ，前面的 `_src` 是這一串 input 的起始指標，但是我們知道除法指令的運算速度遠比+、-、× 以及 bitwise operation 還要慢上許多，所以這邊可以將 `(_read / 8)` 替換成 `read >> 3`，運算出來的答案會是一樣的，並且消耗的指令數更少。 ```cpp while (count > 0) { uint8_t data = *source++; size_t bitsize = (count > 8) ? 8 : count; if (read_lhs > 0) { data <<= read_lhs;//RRR if (bitsize > read_rhs) data |= (*source >> read_rhs); } if (bitsize < 8) data &= read_mask[bitsize]; uint8_t original = *dest; uint8_t mask = read_mask[write_lhs]; if (bitsize > write_rhs) { /* Cross multiple bytes */ *dest++ = (original & mask) | (data >> write_lhs); original = *dest & write_mask[bitsize - write_rhs]; *dest = original | (data << write_rhs); } else { // Since write_lhs + bitsize is never >= 8, no out-of-bound access. mask |= write_mask[write_lhs + bitsize];//DDD *dest++ = (original & mask) | (data >> write_lhs); } count -= bitsize; } ``` ![](https://i.imgur.com/yPwIb9b.png) - `bitsize` :這次需要複製多少 bit 過去，因為一次最多限制複製 8 bit ，所以超過就以 8 最為最大值 - `if (read_lhs > 0)` :如果沒有以 byte 對齊，則需要將讀取資料向左位移 `read_lhs` 個位元，從這個 byte 中的第 `read_lhs` 個位元開始讀取變成是從這個 byte 的頭(0)開始讀取。所以接著的 ==**RRR** 選擇 `data <<= read_lhs`== 。 - `if (bitsize > read_rhs)` :如果沒有複製完這次需要複製的 bit 數(也就是 `count`)，就要從 `src` 下一個的 byte 去抓剩下的資料並且透過 `|=` 貼上 `data`。 - `read_mask` :因為 `data` 一次會直接抓滿 8 bit ，所以當我不需要複製到一整個 byte 的時候，用 bit mask 的方式只取前面 `bitsize` 個位元 - `mask = read_mask[write_lhs]` :注意到因為要從 `write_lhs` 開始**往後**貼上，所以反而後方的 bit 要維持0 - 如果 `bitsize > write_rhs` 成立，代表想要**貼上**的總位元會寫到下一個 byte 去。 - `original = *dest & write_mask[bitsize - write_rhs]` :為了在**下一個 byte** 中寫完剩下的 bit ，要先把想要寫入的位置先用 `write_mask` 清空。 - `*dest = original | (data << write_rhs)` :已經清空完畢，寫入 `data` 中沒寫完的部分 - 如果確保 `bitsize` 的大小全部寫完仍不會寫到下一個 byte 的話， `mask` 要再把後面不能被覆寫的部分保留下來，舉例來說，從4寫到6，最後中間0的資料會被清空，其他被保留下來，==**DDD** 選擇 `mask |= write_mask[write_lhs + bitsize]`==，因為前提是**一定寫得完**，所以可以把開頭( `write_lhs` )直接加上要貼上的字串長度( `bitsize` ) |1|1|1|0|0|0| <font color="#f00">1</font>| <font color="#f00">1</font>| | --- | --- | --- | --- | --- | --- | --- | --- | - `*dest++ = (original & mask) | (data >> write_lhs)` : 總結來說，這段程式碼想做的事情就是一次搬動 1 byte ，如果搬不動就下個迴圈再繼續搬，直到沒有為止，假設我想要從 `_src` 的第 10 個 bit 複製 23 bit 過去 `_dest` ，每次要先做的事情是找從哪個 bit 開始讀，如果讀到這個 bit 的尾端但是需要湊滿 1 byte 再一起複製，就必須從下一個 byte 抓剩下的 bit 來湊滿 8 bit ，貼上的時候一樣先檢查會不會寫到下一個 byte 去，然後再分別於自己的 mask 貼上。 :::success 可以改進的目標: - [x] 將除法替換成簡單的位移計算 - [ ] 發現到的最大問題應該是，如果在 `count` 的長度比較長的時候，可能出現每次複製的時候、貼上的時候，兩邊都需要跨 byte 儲存資料，這樣一來每次都必須要做兩次的 mask 跟填值上去 ::: ### 在 Linux 核心原始程式碼找出逐 bit 進行資料複製的程式碼，並解說相對應的情境 :::success **TODO**:找出逐 bit 進行資料複製的程式碼 ::: --- ## 測驗四 ### 解釋上述程式碼運作原理 ==`cstr.h`== ```cpp #pragma once ``` - `#pragma` :編譯時期，編譯器會去讀取後面的定義，如果讀得懂，就會進行一些特殊的動作，像是特殊的記憶體配置、使用 co-processor 等等，目的是希望編譯器能夠對此進行一些優化，但是為了維持程式碼的便攜性，能夠跨平台執行而能允許沒有這些特殊功能的編譯器一樣也能正常地執行程式碼的內容，所以內容均是"**可選**"的，如果編譯器看不懂會直接忽略。這邊的 `#pragma once` 意思是**引入防護**，對所有的標頭檔確定不會重複引入。 ```cpp typedef struct __cstr_data { char *cstr; uint32_t hash_size; uint16_t type; uint16_t ref; } * cstring; typedef struct __cstr_buffer { cstring str; } cstr_buffer[1]; ``` - `cstring`: - `cstr_buffer`: ```cpp #define CSTR_LITERAL(var, cstr) \ static cstring var = NULL; \ if (!var) { \ cstring tmp = cstr_clone("" cstr, (sizeof(cstr) / sizeof(char)) - 1); \ if (tmp->type == 0) { \ tmp->type = CSTR_PERMANENT; \ tmp->ref = 0; \ } \ if (!__sync_bool_compare_and_swap(&var, NULL, tmp)) { \ if (tmp->type == CSTR_PERMANENT) \ free(tmp); \ } \ } ``` - `CSTR_LITERAL` : ```cpp #define CSTR_BUFFER(var) \ char var##_cstring[CSTR_STACK_SIZE] = {0}; \ struct __cstr_data var##_cstr_data = {var##_cstring, 0, CSTR_ONSTACK, 0}; \ cstr_buffer var; \ var->str = &var##_cstr_data; ``` ==`cstr.c`== ```cpp #define CSTR_LOCK() \ ({ \ while (__sync_lock_test_and_set(&(__cstr_ctx.lock), 1)) { \ } \ }) #define CSTR_UNLOCK() ({ __sync_lock_release(&(__cstr_ctx.lock)); }) ``` - `CSTR_LOCK` : - `CSTR_UNLOCL` : ```cpp static cstring interning(struct __cstr_interning *si, const char *cstr, size_t sz, uint32_t hash) { if (!si->hash) return NULL; int index = (int) (hash & (si->size - 1)); struct __cstr_node *n = si->hash[index]; while (n) { if (n->str.hash_size == hash) { if (!strcmp(n->str.cstr, cstr)) return &n->str; } n = n->next; } // 80% (4/5) threshold if (si->total * 5 >= si->size * 4) return NULL; if (!si->pool) { si->pool = xalloc(sizeof(struct __cstr_pool)); si->index = 0; } n = &si->pool->node[si->index++]; memcpy(n->buffer, cstr, sz); n->buffer[sz] = 0; cstring cs = &n->str; cs->cstr = n->buffer; cs->hash_size = hash; cs->type = CSTR_INTERNING; cs->ref = 0; n->next = si->hash[index]; si->hash[index] = n; return cs; } ``` ```cpp static cstring cstr_interning(const char *cstr, size_t sz, uint32_t hash) { cstring ret; CSTR_LOCK(); ret = interning(&__cstr_ctx, cstr, sz, hash); if (!ret) { expand(&__cstr_ctx); ret = interning(&__cstr_ctx, cstr, sz, hash); } ++__cstr_ctx.total; CSTR_UNLOCK(); return ret; } ``` ```cpp static inline uint32_t hash_blob(const char *buffer, size_t len) { const uint8_t *ptr = (const uint8_t *) buffer; size_t h = len; size_t step = (len >> 5) + 1; for (size_t i = len; i >= step; i -= step) h = h ^ ((h << 5) + (h >> 2) + ptr[i - 1]); return h == 0 ? 1 : h; } ``` - `hash_blob` : #### 其他函式 - `` ### 上述程式碼使用到 gcc atomics builtins，請透過 POSIX Thread 在 GNU/Linux 驗證多執行緒的環境中，string interning 能否符合預期地運作？若不能，請提出解決方案 ### chriso/intern 是個更好的 string interning 實作，請探討其特性和設計技巧，並透過內建的 benchmark 分析其效能表現 ###### tags: `linux2021`

Syntax	Example	Reference
# Header	Header	基本排版
- Unordered List	Unordered List
1. Ordered List	Ordered List
- [ ] Todo List	Todo List
> Blockquote	Blockquote
Bold font	Bold font
Italics font	Italics font
~~Strikethrough~~	~~Strikethrough~~
19^th^	19^th
H~2~O	H₂O
++Inserted text++	Inserted text
==Marked text==	Marked text
[link text](https:// "title")	Link
![image alt](https:// "title")	Image
`Code`	`Code`	在筆記中貼入程式碼
```javascript var i = 0; ```	`var i = 0;`
:smile:		Emoji list
{%youtube youtube_id %}	Externals
$L^aT_eX$	L^aT_eX
:::info This is a alert area. :::	This is a alert area.