2023q1 第 3 週測驗題

--- tags: linux2023 --- # [2023q1](http://wiki.csie.ncku.edu.tw/linux/schedule) 第 3 週測驗題 :::info 目的: 檢驗學員對 bitwise, alignment, C 語言程式設計的認知 ::: ==[作答表單: 測驗 1-2](https://docs.google.com/forms/d/e/1FAIpQLSeBT6aUILfntZvv4I73IU3qw-rbpdu7GuosBz1gnw7Er5lkuw/viewform)== (針對 Linux 核心「設計」課程) ==[作答表單: 測驗 3-4](https://docs.google.com/forms/d/e/1FAIpQLSeSwhdbw3Rh7fghROajaiuFlN55SsMHYt-yazpqjWZiSPN8QQ/viewform)== (針對 Linux 核心「實作」課程) ### 測驗 `1` 考慮一個 [Tree sort](https://en.wikipedia.org/wiki/Tree_sort) 的實作，搭配 [Red–black tree](https://en.wikipedia.org/wiki/Red%E2%80%93black_tree) 作為排序所需的自我平衡樹，原始程式碼可見 [treesort.c](https://gist.github.com/jserv/920766d1fd893d0efd66ac7fdaf23401)。部分程式碼已遮蔽，請補完程式碼，使其運作符合預期。作答規範: * `AAAA` : 利用〈[你所不知道的 C 語言：記憶體管理、對齊及硬體特性](https://hackmd.io/@sysprog/c-memory)〉提到利用 ABI 特性來「標示不用的節點」手段，以 bitwise 操作，對給定的引數 `(r)` 計算合法的記憶體地址 (記得要考慮 alignment)。 * `BBBB` 和 `CCCC` : 運用〈[你所不知道的 C 語言：數值系統篇](https://hackmd.io/@sysprog/c-numerics)〉和〈[你所不知道的 C 語言: bitwise 操作](https://hackmd.io/@sysprog/c-bitwise)〉，以 bitwise 操作分別設定紅黑數節點的顏色。 * `DDDD`, `EEEE`, `HHHH` 是 C 語言敘述 * `FFFF` 和 `GGGG` 則運用〈[你所不知道的 C 語言: linked list 和非連續記憶體](https://hackmd.io/@sysprog/c-linked-list)〉，是合法的 C 語言敘述 * 當使用 bitwise 操作時，應該將變數/引數名稱放在左側，常數 (儘量用最精簡的形式！) 放在右側，例如 `r | 1` * 上述皆不包含 `;`，並該依循 [CONTRIBUTING.md](https://github.com/sysprog21/lab0-c) 程式碼風格規範 (注意空白！)，用最精簡的程式碼書寫 :::success 延伸問題: 1. 指出 `treesort.c` 程式碼的缺失並改進 2. 利用 Linux 核心的 [list.h](https://github.com/torvalds/linux/blob/master/include/linux/list.h) 標頭檔改寫並整合進第一次作業的實驗程式碼中，探討 [Tree sort](https://en.wikipedia.org/wiki/Tree_sort) 的效率 3. 研讀 Linux 核心的 [Red–black tree](https://en.wikipedia.org/wiki/Red%E2%80%93black_tree) 程式碼，比較給定的 `treesort.c` 實作手法，指出後者的改進空間並予以實作 ::: --- ### 測驗 `2` 考慮一個使用 [AVL tree](https://en.wikipedia.org/wiki/AVL_tree) 實作的 [priority queue](https://en.wikipedia.org/wiki/Priority_queue)，部分程式碼如下: ```c #include "avltree.h" struct avl_prio_queue { struct avl_root root; struct avl_node *min_node; }; static inline void avl_prio_queue_init(struct avl_prio_queue *queue) { INIT_AVL_ROOT(&queue->root); queue->min_node = NULL; } static inline void avl_prio_queue_insert_unbalanced( struct avl_prio_queue *queue, struct avlitem *new_entry) { struct avl_node *parent = NULL; struct avl_node **cur_nodep = &queue->root.node; struct avlitem *cur_entry; int isminimal = 1; while (*cur_nodep) { cur_entry = avl_entry(*cur_nodep, struct avlitem, avl); parent = *cur_nodep; if (cmpint(&new_entry->i, &cur_entry->i) <= 0) { cur_nodep = &((*cur_nodep)->left); } else { cur_nodep = &((*cur_nodep)->right); isminimal = 0; } } if (isminimal) queue->min_node = &new_entry->avl; avl_link_node(&new_entry->avl, parent, cur_nodep); } static inline struct avlitem *avl_prio_queue_pop_unbalanced( struct avl_prio_queue *queue) { struct avlitem *item; bool removed_right; if (!queue->min_node) return NULL; item = avl_entry(queue->min_node, struct avlitem, avl); queue->min_node = avl_next(queue->min_node); avl_erase_node(&item->avl, &queue->root, &removed_right); return item; } tatic inline void avl_prio_queue_insert_balanced( struct avl_prio_queue *queue, struct avlitem *new_entry) { struct avl_node *parent = NULL; struct avl_node **cur_nodep = &queue->root.node; struct avlitem *cur_entry; int isminimal = 1; while (*cur_nodep) { cur_entry = avl_entry(*cur_nodep, struct avlitem, avl); parent = *cur_nodep; if (cmpint(&new_entry->i, &cur_entry->i) <= 0) { cur_nodep = &((*cur_nodep)->left); } else { cur_nodep = &((*cur_nodep)->right); isminimal = 0; } } if (isminimal) queue->min_node = &new_entry->avl; avl_insert(&new_entry->avl, parent, cur_nodep, &queue->root); } static inline struct avlitem *avl_prio_queue_pop_balanced( struct avl_prio_queue *queue) { struct avlitem *item; if (!queue->min_node) return NULL; item = avl_entry(queue->min_node, struct avlitem, avl); queue->min_node = avl_next(queue->min_node); avl_erase(&item->avl, &queue->root); return item; } ``` 其中 `avltree.h` 的程式碼可見 [avltree.h](https://gist.github.com/jserv/d03098d57fec03c89fdb2a449d7f6be2)。部分程式碼已遮蔽，請補完程式碼，使其運作符合預期。作答規範: * `IIII`, `JJJJ`, `KKKK`, `LLLL` 利用〈[你所不知道的 C 語言：記憶體管理、對齊及硬體特性](https://hackmd.io/@sysprog/c-memory)〉提到利用 ABI 特性來「標示不用的節點」手段，以 bitwise 操作，計算合法的記憶體地址 (記得要考慮 alignment)。 * `MMMM` 和 `NNNN` 為函式名稱 * 當使用 bitwise 操作時，應該將變數/引數名稱放在左側，常數 (儘量用最精簡的形式！) 放在右側，例如 `r | 1` * 上述皆不包含 `;`，並該依循 [CONTRIBUTING.md](https://github.com/sysprog21/lab0-c) 程式碼風格規範 (注意空白！)，用最精簡的程式碼書寫 :::success 延伸問題 1. 解釋上述程式碼運作原理，並比較用紅黑樹實作的 [priority queue](https://en.wikipedia.org/wiki/Priority_queue)，應提供完整的測試程式和效能分析 2. Linux 核心也有 AVL tree 的身影，但陸續被紅黑樹替代，請揣摩 Linux 核心開發者的考慮因素，並搭配 git log 來解讀 > 見 commit [b145425](https://github.com/torvalds/linux/commit/b145425f269a17ed344d737f746b844dfac60c82) 3. 研讀 Linux 核心原始程式碼，指出曾經/現在使用 AVL tree 的部分，對照 Linux 核心的 `rbtree.h`，探究是否可用後者替換，從而爭取到貢獻程式碼到 Linux 核心的機會 ::: --- ### 測驗 `3` ![](https://hackmd.io/_uploads/H1ChcH00j.png) [Linear feedback shift register](https://en.wikipedia.org/wiki/Linear-feedback_shift_register) (LFSR) 是指給定前一狀態，將該輸出的線性函數作為輸入的移位暫存器，其應用包括 [PRNG](https://en.wikipedia.org/wiki/Pseudorandom_number_generator) 場景。 LFSR 範例: ![](https://hackmd.io/_uploads/SJn1iB0Cs.png) 1. 初始狀態 $s = [s_2, s_1, s_0] = [1, 0, 0]$ 2. 反饋 $p = [p_2, p_1, p_0] = [0, 1, 1]$ 3. 線性運算 `s[n+1] = s[n]*p[2] ^ s[n-1]*p[1] ^ s[n-2]*p[0]` 考慮一個運用 LFSR 來產生隨機數，並使其均勻分佈於 64 位元無號整數的有效空間 (distribution of uniformly arbitrarily large `uint64_t`)。參考執行輸出如下: ``` 0:91263 | 1:93093 | 2:92113 | 3:92503 | 4:92253 | 5:91833 | 6:93023 | 7:92283 | 8:93473 | 9:92983 | 10:90433 | 11:92373 | 12:91733 | 13:93733 | 14:92193 | ... 105:81623 | 106:82253 | 107:82573 | 108:82393 | 109:82483 | 110:82643 | 111:81483 | 112:82473 | 113:80623 | 114:82833 | 115:81703 | 116:82213 | 117:80603 | 118:81143 | 119:81253 | ``` 程式碼可參見 [bucket_uniform.c](https://gist.github.com/jserv/15c6ef4383d5d010326cdc4382ffdd1d) (部分程式碼遮蔽): * `log2_64` : 計算以 2 為底的 x 的對數 (logarithm of x to the base b)，且下取整函數 (floor) * `bucket_number` : 在指定區間內，使產生的 LFSR 數值得以均勻分佈請補上程式碼，使程式碼的執行結果符合參考輸出。作答規範: * `AAAA`, `BBBB`, `CCCC`, `DDDD`, `EEEE`, `FFFF`, `GGGG`, `HHHH` 皆為大於或等於 `0` 的整數 * `IIII` 和 `JJJJ` 是 `mask111` 或 `mask011` :::success 延伸問題: 1. 解釋 [Linear feedback shift register](https://en.wikipedia.org/wiki/Linear-feedback_shift_register) (LFSR) 的運作原理，搭配在 [Linux 核心原始程式碼](https://github.com/torvalds/linux)中，用 `git log` 和 `grep` 找出 LFSR 的應用案例 2. 解釋上述程式碼運作的原理 3. 在 Linux 核心原始程式碼中找到 $\log_2(x)$ 的實作 (整數)，要涵蓋不同的整數型態寬度，以及是否能運用微處理器提供的指令來加速。也從 Linux 核心找出整數 $\log_2(x)$ 的應用案例並解說。 4. `lab0-c` 提供類似的實作 [log2_lshift16.h](https://github.com/sysprog21/lab0-c/blob/master/log2_lshift16.h)，解釋其原理並嘗試改進其效能 ::: --- ### 測驗 `4` 已知輸入必為大於 `0` 的數值 (即 `x > 0`)，以下程式碼可計算 $\lceil log_2(x) \rceil$ ，也就是 [ceil](https://man7.org/linux/man-pages/man3/ceil.3.html) 和 [log2](https://man7.org/linux/man-pages/man3/log2.3.html) 的組合並轉型為整數: ```cpp int ceil_log2(uint32_t x) { uint32_t r, shift; x--; r = (x > 0xFFFF) << 4; x >>= r; shift = (x > 0xFF) << 3; x >>= shift; r |= shift; shift = (x > 0xF) << 2; x >>= shift; r |= shift; shift = (x > 0x3) << 1; x >>= shift; return (KKKK) + 1; } ``` 請補完，使其行為符合預期。作答規範: * `KKKK` 應以最簡潔的形式撰寫，且符合[作業一](https://hackmd.io/@sysprog/linux2023-lab0)排版規範 (近似 Linux 核心程式碼排版風格) * `KKKK` 為表示式，限制使用 `^`, `&`, `|`, `<<`, `>`> 這幾個運算子，可能會出現常數 * `KKKK` 不該包含小括號 (即 `(` 和 `)`) * 為了自動批改的便利，變數出現的順序 (可從缺) 從左到右為 `r`, `shift`, `x` * `KKKK` 不可包含 `,` 和 `;` 這樣的分隔符號 (separator) :::success 延伸問題: 1. 解釋上述程式碼運作原理 2. 改進程式碼，使其得以處理 `x = 0` 的狀況，並仍是 branchless 3. 在 Linux 核心原始程式碼找出 ceil 和 log2 的組合 (類似的形式)，並解說應用案例，例如在 Linux 核心排程器就有 > 善用 [lxr](https://elixir.bootlin.com/linux/latest/source) 和 `git log` ::: ---