--- tags: linux2022 --- # 2022q1 Homework3 (quiz3) contributed by < [`qwe661234`](https://github.com/qwe661234) > > [測驗題目](https://hackmd.io/@sysprog/linux2022-quiz3) ## 測驗一 GENMASK(h, l) 是用來產生 mask, 而 mask 中 0 開始算起位在 l ~ h 的 bit 會是 1, 而其餘會是 0, 也就是 0 ~ l - 1 以及 h + 1 ~ 63 會是 0。 1. `((~0UL) >> (63 - h))` 使得 0 開始算起位在第 h + 1 ~ 63 的 bit 為 0 其餘是 1 2. `((~0UL) >> (l) << (l))` 使得 0 開始算起位在第 l + 1 ~ 63 以及 0 ~ l - 1 的 bit 為 0 其餘是 1 3. 將兩個結果做 `and` operation 可得 0 ~ l - 1 以及 h + 1 ~ 63 會是 0, l ~ h 的 bit 會是 1 的 mask ```c #include <stdio.h> #define GENMASK(h, l) \ (((~0UL) >> (63 - h)) & ((~0UL) >> (l) << (l))) ``` 我們可以進一步縮減程式碼為, 因為由以上操作可以發現最終 mask, 0 開始算起位在第 h + 1 ~ 63 的 bit 為 0 是由 `(~0UL) >> (63 - h)`, 因此無需左移 l 。 ```c #include <stdio.h> #define GENMASK(h, l) \ (((~0UL) >> (63 - h)) & ((~0UL) << (l))) ``` ## 比較 Linux 核心 GENMASK 巨集的實作，闡述其額外的考量 ```c #define GENMASK_INPUT_CHECK(h, l) \ (BUILD_BUG_ON_ZERO(__builtin_choose_expr( \ __is_constexpr((l) > (h)), (l) > (h), 0))) #define __GENMASK(h, l) \ (((~UL(0)) - (UL(1) << (l)) + 1) & \ (~UL(0) >> (BITS_PER_LONG - 1 - (h)))) #define GENMASK(h, l) \ (GENMASK_INPUT_CHECK(h, l) + __GENMASK(h, l)) ``` 我們可以看到 `__GENMASK(h, l)` 的部分 `(~UL(0) >> (BITS_PER_LONG - 1 - (h))` 對應到 `((~0UL) >> (63 - h))`, 考量到硬體架構, 部分硬體架構的 `long` 是 32 bit, 因此改以 `BITS_PER_LONG`, 而不是直接將 `long` 寫成 64 bit。 `((~UL(0)) - (UL(1) << (l)) + 1)` 對應到 `((~0UL) << (l))`, `(~UL(0)) - (UL(1) << (l))` 可得到除了從 0 開始算起第 l 個 bit 是 0 其他是 1 的 mask, 接著我們可以思考, 31 寫成 2 進位會是 `011111`, 將 31 + 1 就會成為 32, 寫成 2 進位就是 `100000`, 由以上觀察可知, 目前產生的 mask, 從 0 開始算起第 l 個 bit 是 0 而 0 ~ l - 1 的 bit 是 1, 我們如果將 mask 加上 1, 會使得第 l 個 bit 變成 1 而第 0 ~ l - 1 的 bit 變成 0, 最後得到位於 0 ~ l - 1 的 bit 為 0, 其餘為 1 的 mask, 與 `((~0UL) << (l))` 的結果相同。 ### GENMASK_INPUT_CHECK(h, l) Linux 和心中的 GENMASK 還有一個額外的考量 1. 檢查 l > h 是否為 constant expersion, constant expression 會在編譯時期就被評估，而不是在執行時期進行評估。 2. 檢查 l 是否大於 h, 因為 GENMASK 正確輸出的前提是 h >= l 。 ```c #define GENMASK_INPUT_CHECK(h, l) \ (BUILD_BUG_ON_ZERO(__builtin_choose_expr( \ __is_constexpr((l) > (h)), (l) > (h), 0))) ``` #### __builtin_choose_expr(exp, e1, e2) `builtin_choose_expr` 為 gnu extension, 功能類似 `if-else`, 但他可以在編譯時期決定要使用 `e1` or `e2`, 而非執行時期 。 #### __is_constexpr(x) `__is_constexpr(x)` 也是 gun extension, 用來判斷巨集的輸入是否為 constant expression。 ```c #define __is_constexpr(x) \ (sizeof(int) == sizeof(*(8 ? ((void *) ((long) (x) *0l)) : (int *) 8))) ``` 依據 C11 標準 §6.3.2.3 > An integer constant expression with the value 0, or such an expression cast to type void *, is called a null pointer constant. 此處就是 __is_constexpr 巨集的關鍵：constant expression 0 轉型為 (void *) 會導致 null pointer constant。相反地，如果本來不是 constant expression，就算乘以 0，只會得到數值 0，予以轉型後，不會得到 null pointer constant，而是一個內含值為 0 的指標，之後仍有機會變動。 若是將 0 轉型成 void *, 可將其視為 null pointer constant, 因此 ```c 8 ? ((void *) ((long) (x) *0l)) : (int *) 8 ``` 如果 x 是 constant expersion, 上述表示式等價於 ```c 8 ? [null pointer constant] : (int *) 8 ``` 接著, 依據 依據 C11 標準 §6.5.15 Conditional operator > If both the second and third operands are pointers or one is a null pointer constant and the other is a pointer, the result type is a pointer to a type qualified with all the type qualifiers of the types referenced by both operands. Furthermore, if both operands are pointers to compatible types or to differently qualified versions of compatible types, the result type is a pointer to an appropriately qualified version of the composite type; if one operand is a null pointer constant, the result has the type of the other operand; otherwise, one operand is a pointer to void or a qualified version of void, in which case the result type is a pointer to an appropriately qualified version of void. 也就是說, 如果 x 是 constant expersion, 那 `((void *) ((long) (x) *0l))` 就會成為 null pointer constant, 而 `8 ? ((void *) ((long) (x) *0l)) : (int *) 8` 得出的結果會是 `(int *) 8`, 主要依據 > if one operand is a null pointer constant, the result has the type of the other operand; 反之, 如果 x 不是 constant expersion, 則 `8 ? ((void *) ((long) (x) *0l)) : (int *) 8` 的回傳結果會是 `(void *) 0`, 在 gcc 中，sizeof(void) 為 1, 因此, `sizeof(int) == sizeof(void)` 結果為 0 。 #### BUILD_BUG_ON_ZERO(e) ```c #define BUILD_BUG_ON_ZERO(e) (sizeof(struct { int:(-!!(e)); })) ``` 這個 macro 是用來檢查是否會有 compilation error，e 是 expression，當它經由這個 macro 結果為 true ，則可以在 compile-time 的時候被告知有錯。(因為宣告發生在 compile-time) !!(e)：對 e 做兩次 NOT，確保結果一定是 0 或 1 -!!(e)：對 !!(e) 乘上 -1，因此結果會是 0 或 -1 因此，當 e 這個判斷式不合法時，即 !!(e) = 1 也就是 -!!(e) = -1，代表宣告一個 structure 中有一個 int ，其中 32 bits 中有 -1 bit 的 bit field。 反之當 e 合法時，則會宣告 int 有 0 bit 的 bit field。 綜合以上, 如果 l > h 是 constant experssion, 那 macro 就會檢查 l 是否大於 h, 如果 l > h 會在 `BUILD_BUG_ON_ZERO(e)` 報錯, 如果不是, 則編譯時期無法檢查, 在 `BUILD_BUG_ON_ZERO(e)` 部份會傳入 0, 因此不會報錯。 ### reference: [Linux 核心原始程式碼巨集: max, min](https://hackmd.io/@sysprog/linux-macro-minmax#%E6%9B%B4%E5%A4%9A%E7%9A%84%E6%AA%A2%E6%9F%A5) [bit-field](https://hackmd.io/@sysprog/c-bitfield) ## 測驗三 ```c #include <stdint.h> uint8_t rev8(uint8_t x) { x = (x >> 4) | (x << 4); x = ((x & 0xCC) >> 2) | ((x & 0x33) << 2); x = ((x & 0xAA) >> 1) | ((x & 0x55) << 1); return x; } ``` ## 測驗四 ```c #include <assert.h> #define _foreach_no_nullval(i, p, arr) \ assert((i) >= sizeof(arr) / sizeof(arr[0]) || (p)) #define foreach_int(i, ...) \ for (unsigned _foreach_i = (((i) = ((int[]){__VA_ARGS__})[0]), 0); \ _foreach_i < sizeof((int[]){__VA_ARGS__}) / sizeof(int); \ (i) = ((int[]){__VA_ARGS__, 0})[++_foreach_i]) #define foreach_ptr(i, ...) \ for (unsigned _foreach_i = \ (((i) = (void *) ((typeof(i)[]){__VA_ARGS__})[0]), 0); \ (i); (i) = (void *) ((typeof(i)[]){__VA_ARGS__, \ NULL})[++_foreach_i], \ _foreach_no_nullval(_foreach_i, i, \ ((const void *[]){__VA_ARGS__}))) ``` ### 分析 foreach_int ```c unsigned _foreach_i = (((i) = ((int[]){__VA_ARGS__})[0]), 0) ``` `(int[]){__VA_ARGS__}` 這邊利用 compound literal 的方式初始化整數陣列為傳入的不定參數, 將 i 設為 array 的第 0 個 element, 將 `_foreach_i` 設為 0 。 > C99 [6.5.2.5] Compound literals >* The type name shall specify an object type or an array of unknown size, but not a variable length array type. >* A postfix expression that consists of a parenthesized type name followed by a braceenclosed list of initializers is a compound literal. It provides an unnamed object whose value is given by the initializer list. >* If the type name specifies an array of unknown size, the size is determined by the initializer list as specified in 6.7.8, and the type of the compound literal is that of the completed array type. Otherwise (when the type name specifies an object type), the type of the compound literal is that specified by the type name. In either case, the result is an lvalue. ```c _foreach_i < sizeof((int[]){__VA_ARGS__}) / sizeof(int); ``` 將 `_foreach_i` 的中止條件設為小於 array size ```c (i) = ((int[]){__VA_ARGS__, 0})[++_foreach_i]) ``` 由於 for loop 中止條件是 `_foreach_i` 要遞增到等於 array size, 因此答案為 `++_foreach_i`, 將 `_foreach_i` 的值加 1, 並將 i 設為下一個 element ### foreach_ptr foreach_ptr 的作法和 foreach_int 類似, 只是中止條件改為 ptr 為空指標時停止, 並且 foreach_ptr 會檢查 array 和指標是否為 null ## 在 Linux 核心原始程式碼找出類似技巧的實作並解說其應用場景 在 [include/linux/list.h](https://github.com/torvalds/linux/blob/fa2e1ba3e9e39072fa7a6a9d11ac432c505b4ac7/include/linux/list.h) 也就是作業 lab0 使用到的 header file list.h 中, 使用到類似的實做技巧, 將 for loop 以 macro 實作。 ```c #define list_for_each_entry(pos, head, member) \ for (pos = list_first_entry(head, typeof(*pos), member); \ !list_entry_is_head(pos, head, member); \ pos = list_next_entry(pos, member)) ``` `list_for_each_entry(pos, head, member)` 走訪 doubly linked-list, 從第一個 node 走訪到一圈回到 head, pos 代表 for loop 目前走訪到的 node, head 即 doubly linked-list 的 head, member 是結構體的成員, 用來回推 node 的起始位置。 透過 macro 實做可以讓程式碼更簡潔, 也可以當成是 API, 使用者只需要 call `list_for_each_entry(pos, head, member)`, 就能走訪 doubly linked-list 中的每個 node 並做對應的操作, 而不需要懂這個 `for_each` API 的實做細節。 ## 測驗十 透過四捨五入決定是否進位, 所以當 `x / divisor` 的餘數比 `__d / 2` 大時要進位, 反之, 則不進位。 `x / divisor` 的餘數比 `__d / 2` 大也可以看成 `x / divisor` 的餘數加上 `__d / 2` 比 __d 大時要進位，因此改寫成 `__x + (__d >> 1)` 。 `(typeof(x)) -1) > 0 || ((typeof(divisor)) -1) > 0` 這邊是用來判斷 x 或 divisor 其中一個是不是 unsigned, 只要其中一個是 unsigned, 另外一個也會轉形成 unsigned, `((__x) > 0) == ((__d) > 0))` 用來判斷 x 和 divisor 是否同號, 如果都成立則代表 x 和 divisor 不同號, x < 0, 因此 `__x + (__d >> 1)` 應改成 `__x - (__d >> 1)`。 ```c #define DIVIDE_ROUND_CLOSEST(x, divisor) \ ({ \ typeof(x) __x = x; \ typeof(divisor) __d = divisor; \ (((typeof(x)) -1) > 0 || ((typeof(divisor)) -1) > 0 || \ (((__x) > 0) == ((__d) > 0))) \ ? ((__x + (__d >> 1)) / (__d)) \ : ((__x - (__d >> 1)) / (__d)); \ }) ```
Last changed by  
 
陳彥甫
230

Read more

實作 Thread package

contributed by < qwe661234 >

10/8/2023
Cache Coherency & I/O ordering

在多處理器的機器上，每個 CPU 都有自己的 cache，以彌補 CPU 和主記憶體(Main memory) 之間較慢的存取速度，當一個特定資料首次被特定的 CPU 讀取時，此資料顯然不存在於該 CPU 的 cache 中 (即 cache miss)，意味著 CPU 需要自主記憶體中讀取資料 (為此，CPU 通常要等待數百個 cycle)，此資料最終將會存放於 CPU 的 cache 中，這樣後續就能直接自 cache 上快速存取，不需要再透過主記憶體。因為每個 CPU 上的 cache 資料是 private 的，因此在進行寫入操作時，會造成其他 CPU 上的 cache 資料不一致的問題。

10/2/2023
CO Final

(15pt) 1. Assume there is no forwarding in a 5-stage pipline processor 1 (1) (5pt) Please indicate all the potential hazards in the following instruction sequence ? xori x1, x1, 2 addi x6, x5, -4 lw x10, 8(x6) add x5, x6, x6 sub, x2, x2, x1 Ans: addi && lw (2.5pt)

6/8/2023
New EBB Strategy

考量到 JIT 中 codegen 以及 compilation 的 overhead 過高，我們需要讓一個 EBB 含有更多的指令，理想是希望將一整個 loop body 涵蓋在一個 EBB 中。 我們參考 rvemu， rvemu 先將 block 以 unconditional jump 作切分，接著將其 block 中所有 branch taken 會走到的 block 都涵蓋進來，一個 block 含有大量的指令且有好的效能表現。 我們的新策略也是希望一個 block 中含有大量的指令，所以我們 trace 整個 control flow graph 並把 trace 過的 block 都涵蓋進來。 control flow graph 的終點有兩種情形，一種是 unconditional jump，而另一個則是遇到 back edge，也就是指向已經 trace 過的節點，下圖展示一個簡單的 EBB 案例。 過去的策略我們是直接指向某個 block 的 ir，一旦 block 被 cache 置換掉，EBB 就會變小。過去的另一個策略是用 memcpy，然而頻繁的 memcpy 成本過高，導致效能沒有很好的提昇。於是我們選用成本較低的 instruction fetch & decode，將 trace 到的 block 使用 instruction fetch & decode 存到 EBB 中，這個作法也不用擔心其他 block 被 cache 置換掉使 EBB 變小的問題。 另外，過去 EBB 有兩種版本，一種是 for interpter 而另一種是 for JIT 的，這導致作 JIT 時還要重新 extend 一次，現在則統一一種版本。 original EBB vs new EBB 指令數量

5/10/2023
Read more from 陳彥甫
Published on HackMD