--- tags: linux2023 --- # 2023q1 Homework3 (quiz3) contributed by < [chiangkd](https://github.com/chiangkd) > ## 開發環境 ```shell $ gcc --version gcc (Ubuntu 11.3.0-1ubuntu1~22.04) 11.3.0 Copyright (C) 2021 Free Software Foundation, Inc. This is free software; see the source for copying conditions. There is NO warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. $ 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): 8 On-line CPU(s) list: 0-7 Vendor ID: GenuineIntel Model name: Intel(R) Core(TM) i7-7700HQ CPU @ 2.80GHz CPU family: 6 Model: 158 Thread(s) per core: 2 Core(s) per socket: 4 Socket(s): 1 Stepping: 9 CPU max MHz: 3800.0000 CPU min MHz: 800.0000 BogoMIPS: 5599.85 ``` ## 測驗 1 **延伸問題**: 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 **延伸問題**: 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 **延伸問題**: 1. 解釋 [Linear feedback shift register (LFSR)](https://en.wikipedia.org/wiki/Linear-feedback_shift_register) 的運作原理，搭配在 [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)，解釋其原理並嘗試改進其效能 函式執行時設定 `num_of_buckets = 120`、`num_of_iterations` 設定大約為 100 萬，透過 `set_N_BUCKETS` 以及 `set_N_BITS()` ，設定全域變數 `N_BUCKETS = 120`， `N_BITS = log2_64(N_BUCKETS) = 6` ，接著將 `buckets` 分配空間並初始化，透過 `fill_buckets` 迭代 `iterations` 次並填滿 `buckets` 在 `fill_buckets` 中定義 `x = 0x98765421b16b00b5`、`lfsr_iter = 6 << 1 = 12`，每次迭代中 `tmp_bucket` 都會透過 `bucket_number(x)` 更新，且每一次迭代 `x` 值都會進行 `lfsr_iter = 12` 次 LFSR 操作 其中 `lfsr()` 函式實作 ```c static void lfsr(uint64_t *up) { uint64_t new_bit = ((*up) ^ ((*up) >> 3) ^ ((*up) >> 30) ^ ((*up) >> 55)) & 1u; /* don't have to map '+1' in polynomial */ *up = ((*up) >> 1) | (new_bit << 63); /* shift *up by 1 to RIGHT and insert new_bit at "empty" position */ } ``` ```graphviz digraph g{ node[shape=record, style=bold]; series[label="<1>1|...|<9>9|...|<34>34|...|...|<61>61|...|...|<64>64"] xor1[label=xor][shape=circle] xor2[label=xor][shape=circle] xor3[label=xor][shape=circle] {rank=same;xor3;xor2;xor1} series:64:s->xor3:e series:61:s->xor3:e series:34:s->xor2:e series:9:s->xor1:e xor3:w->xor2:e[constraint=none] xor2:w->xor1:e[constraint=none] xor1:w->series:1:w } ``` 可表示為多項式 $x^{64}+x^{61}+x^{34}+x^{9}+1$ 其中 `log2_64` 須計算以 2 為底的 x 的對數，且向下取整，程式一開始已藉由，巨集展開建立大小為 256 的表格的對數值，其中對數值 n 佔表格的 $2^n$ 格，以 `2, 3` 為例，預計輸出為 `1`，即查表中的第 2、第 3 格為 `1` 在程式內將輸入值 right shift 及 `if` 條件判斷其屬於哪個級距 ($2^1<x<2^8$、$2^8<x<2^{16}$...) 並查表作答，故 `AAAA` 至 `HHHH` 為 `56` 至 `0` ，等差為 `8` 的數值。 ```c unsigned int bucket_number(uint64_t x) { uint64_t mask111 = (1 << (N_BITS + 1)) - 1; uint64_t mask011 = (1 << (N_BITS)) - 1; /* one 1 less */ unsigned char leq = ((x & mask111) < N_BUCKETS); /* leq (less or equal) is 0 or 1. */ return (leq * (x & IIII)) + ((1 - leq) * ((x >> (N_BITS + 1)) & JJJJ)); /* 'x >> (N_BITS + 1)' : take different set of bits -> better uniformity. * '... & mask011' guarantees that the result is less or equal N_BUCKETS. */ } ``` `bucket_number` 函數將產生的 LFSR 數值得以均勻分佈，以原程式為例 - `mask111 = (1 << (N_BITS + 1)) - 1 = 127 (0b0111 1111)` - `mask011 = (1 << (N_BITS)) - 1 = 63 (0b0011 1111)` 接著如果 `leg` = 1，代表 `(x & mask111) < N_BUCKETS` 及他的值可以直接 return，如果 `leg` = 0，代表 `(x & mask111) >= N_BUCKETS` 即需要透過運算，否則 return value 會超過 `N_BUCKETS` 數值。 根據註解 - `IIII = mask111` - `JJJJ = mask011` ## 測驗 4 **延伸問題**: 1. 解釋程式碼運作原理 2. 改進程式碼，使其得以處理 `x = 0` 的狀況，並仍是 branchless 3. 在 Linux 核心原始程式碼找出 ceil 和 log2 的組合 (類似的形式)，並解說應用案例 (提示: 在 Linux 核心排程器就有) ```c 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; } ``` 題目要求輸出 $log_{2}^{x}$ 並向上取整 本質上是 binary search，假設輸入為 `33`，預期輸出為 `6` (因 $2^{6}=64>33$) 可表示為 ```shell 33 = 0b110011 輸出 6 = 110 r=0 shift=0 x= 0b0000 0000 0000 0000 0000 0000 0010 0001 x--; *start* --- x= 0b0000 0000 0000 0000 0000 0000 0010 0000 --- ↑ x<0xFFFF 1111 1111 1111 1111 --- r = 0 shift = 0 --- x= 0b0000 0000 0000 0000 0000 0000 0010 0000 --- ↑ x<0xFF 1111 1111 --- r = 0 shift = 0 --- x= 0b0000 0000 0000 0000 0000 0000 0010 0000 --- ↑ x>0xF 1111 --- r = 0 shift = 1 << 2 = 4 --- x >>= shift x = 0b0000 0000 0000 0000 0000 0000 0000 0010 = 4(decimal) --- ↑ r |= shift = 0b100 | x<0x3 11 --- x = 2 shift = 0 r = 4 --- need return (KKKK) + 1 KKKK = 5 = 0b101 ``` 以上述流程可知，在每次判斷是否大於判斷值 (`0xFFFF`, `0xFF`, `0xF`, `0x3`) 時，將是否大於儲存於 `r`，有進行偏移就會有 `shift` 值，每次 `x` 的偏移量儲存於 `shift`，且最後 `x` 會剩下最後兩個 bits `0bxx` 基本上最高位為 `1` 的 bit 就會決定這個數值夾在哪兩個 2 的冪次之間，所以這個過程旨在找到最高位為 `1` 的 bit 在哪一個位置，在第一個 `0xFFFF` 若需要偏移，代表輸入的 `x` 值大於 65537 (開頭有先 `x--`)，即代表輸入的值大於 $2^{16}$，故 `r` 會先儲存 `0b10000 = 16` 代表，後續則以此類推。 最後以 `r | shift | x>>1` 統計準確在哪一個位置上，因題目要求 ceil，所以才會有開頭先 `x--` 最後算完再 +1