2022q1 Homework4 (quiz4)

--- tags: linux2022 --- # 2022q1 Homework4 (quiz4) contributed by < `sternacht` > > [作業要求](https://hackmd.io/@sysprog/HkJ-dN_-q) ### 測驗 1 #### 答案 EXP1 = `r | shift | x >> 1` #### 延伸 - 解釋上述程式碼運作原理 ```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 (EXP1) + 1; } ``` 本題延伸自 [第三周測驗 7 ](https://hackmd.io/@sysprog/linux2022-quiz3#測驗-7)，不同是的這題要計算 $\lceil log_2(x) \rceil$ ，因此在計算前後的方式有些不同，例如最前面有一個 `x--` 的動作，目的是要讓 2 的冪的數得到的值少一位，接著以 fls 計算，並在最後加回來，換言之就是一種減去 offset 概念的使用。看過第三周測驗 7 的話，我們可以知道這一段程式碼還缺少一小部分，而這個部分全部被整合到 EXP1 裡，若是把 EXP 1 攤開來看，還需要以下幾個步驟 ```c x >>= shift; // below code is equal to 'return (EXP1) + 1;' r |= shift; shift = (x > 0x1); x >>= shift; return (r | shift) + 1 ``` 其中 `x` 已經不會再用到，因此倒數第二行對 `x` 的數值指派可以省略，而 `x` 在經過一連串的右移過後，到第三行的時候數值範圍是從 0 到 3 ，對應二進位就是 `00`, `01`, `10`, `11`，大於 1 的判斷式表示只有後兩個要為 1 ，因此也可以寫成 `x >> 1`，最後整理起來就寫成 `return (r | shift | x >> 1) + 1` #### 延伸 - 改進程式碼，使其得以處理 x = 0 的狀況，並仍是 branchless 若要改寫成能夠處理 x = 0 的狀況，勢必不能在最前面預先減去 1 ，而不這麼做的話就需要在最後面判斷要不要再補上 1 ，這裡我選擇先將保留 `x` 的值在變數 `_x`，在最後的時候作為判斷用，如下 ```c int ceil_log2(uint32_t x) { uint32_t r, shift, _x = 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; r |= (shift | x >> 1); return r + (((1UL << r) ^ _x) > 0) - (_x < 1); } ``` `r` 基本上沒有變，就是去算最高位元的位置，但因為除了 2 的冪以外的數需要再加 1 ，因此這時候就需要用 `_x` 與 `1 << r` 做 ^ 的 bitwise 操作，來看扣掉最高位元之後還有沒有剩下，如果有的話就是需要加 1 ，然而這時候會遇到一個問題是因為數值 0 與 1 做 ^ 操作會有值，導致函式代入 0 的結果會是 1。因此還要再把這個值扣掉，使結果為 0 (雖然log(0)應該為無效輸入) 再進一步想，會需要多加一個減號是因為起初是用 `1UL << r` 這樣的操作，是否有辦法一開始就過濾為 0 狀況呢? 於是又將最後一行改成以下的樣子，當原本的傳入值不為 0 時，才會變成 `1UL << r` ，否則就相當於 `0 << r` ```c return r + ((((_x > 0) << r) ^ _x) > 0); ``` #### 延伸 - 在 Linux 核心原始程式碼找出 ceil 和 log2 的組合 (類似的形式)，並解說應用案例 (提示: 在 Linux 核心排程器就有) [linux/fair.c](https://github.com/torvalds/linux/blob/master/kernel/sched/fair.c) --- ### 測驗 2 #### 答案 EXP2 = `x & t` EXP3 = `o += shift` #### 延伸 - 解釋上述程式碼運作原理，並迴避 while, for, goto 等關鍵字以改寫出功能等價的實作 ```c static inline size_t ffs(unsigned long x) { if (x == 0) return 0; size_t o = 1; unsigned long t = ~0UL; size_t shift = BITS_PER_LONG; // 64 shift >>= 1; t >>= shift; while (shift) { if ((EXP2) == 0) { x >>= shift; EXP3; } shift >>= 1; t >>= shift; } return o; } ``` 題目提到這是改寫自 [第三周測驗 11 ](https://hackmd.io/@sysprog/linux2022-quiz3#測驗-11)的 fls 函式，這裡則是 ffs 的實作，許多概念上是相同的，都是利用二元搜尋的方式來找到答案，不一樣的地方是， fls 的實作是比較前半部分的 bits 是否為 0 ，來確認最高位元在哪一邊， ffs 則相反，透過 bitmask 的方式來判斷後半部分的 bits 是否為 0 ，來確定最低的 1 位元出現在哪一邊。概念大致就是這樣，接著看程式碼，shift 預設為 64，接著除以 2 ，這是我們第一次要比較的位元數， `t` 作為 mask，一開始全部的 64 bits 都是 1 ，接著在右移 shift 個 bits，就變成後半為 1 ，前半為 0 的 mask，接著用 mask `t` 與 `x` 用 & 操作做比較，如果結果為 0 ，表示在 x 的後 16bits 中沒有 1 存在，此時把 x 整個右移 32bits ，並將結果加到變數 `o`裡面。每經過一次迴圈，要比較的位元數就會減半，並且每當後半的位元沒有 1 的時候，就把 `x` 右移，去找前半部分。若是要迴避 while, for, goto等關鍵字，第一種方式可以參考第三周測驗 11 的寫法，也就是把原本的迴圈打開，改寫如下 ```c static inline unsigned long ffs(unsigned long word) { if (!word) return 0; int num = 1; if (!(word & (~0ul >> 32))) { num += 32; word >>= 32; } if (!(word & (~0ul >> (64 - 16)))) { num += 16; word >>= 16; } if (!(word & (~0ul >> (64 - 8)))) { num += 8; word >>= 8; } if (!(word & (~0ul >> (64 - 4)))) { num += 4; word >>= 4; } if (!(word & (~0ul >> (64 - 2)))) { num += 2; word >>= 2; } if (!(word & (~0ul >> (64 - 1)))) num += 1; return num; } ``` 以上 if 判斷式中減法的部分只是闡釋想法，因為都是定值，所以也可以直接寫出數值如 `0xff`, `0xf` 等。另一種想法就是使用 recursive 的方式來改寫，如下 ```c static inline size_t ffs(unsigned long x, size_t shift) { if (x == 0) return 0; if (shift == 0) return 1; size_t o = 0; unsigned long t = ~0UL >> (64 - shift); if ((x & t) == 0) { x >>= shift; o += shift; } shift >>= 1; return o + ffs(x, shift); } ``` #### 延伸 - 在 Linux 核心原始程式碼的 include/asm-generic/bitops 目錄找出相關程式碼，並探討應用案例目錄底下的 ffs 實作方式皆是不使用 while, for, goto ，而用多個 if 寫成的方式，例如 ```c static inline int ffs(int x) { int r = 1; if (!x) return 0; if (!(x & 0xffff)) { x >>= 16; r += 16; } if (!(x & 0xff)) { x >>= 8; r += 8; } if (!(x & 0xf)) { x >>= 4; r += 4; } if (!(x & 3)) { x >>= 2; r += 2; } if (!(x & 1)) { x >>= 1; r += 1; } return r; } ``` 應用案例如 [linux/sched.h](https://github.com/torvalds/linux/blob/5bfc75d92efd494db37f5c4c173d3639d4772966/include/asm-generic/bitops/sched.h) 裡用 ffs 來判斷地址 b 後的 100bits 內有沒有 1 存在，並且依照不同的 long 長度做調整，與 $O(1)$ schedule 挑選任務的方式頗有相似。 ```c static inline int sched_find_first_bit(const unsigned long *b) { #if BITS_PER_LONG == 64 if (b[0]) return __ffs(b[0]); return __ffs(b[1]) + 64; #elif BITS_PER_LONG == 32 if (b[0]) return __ffs(b[0]); if (b[1]) return __ffs(b[1]) + 32; if (b[2]) return __ffs(b[2]) + 64; return __ffs(b[3]) + 96; #else #error BITS_PER_LONG not defined #endif } #endif /* _ASM_GENERIC_BITOPS_SCHED_H_ */ ``` ### 測驗 3 #### 答案 EXP4 = `*con = (*con)->next` EXP5 = `fc->next` #### 延伸 - 解釋上述程式碼運作原理，並探討這樣區分 foo 和 foo_consumer 的好處 ```c struct foo_consumer { int (*handler)(struct foo_consumer *self, void *); struct foo_consumer *next; }; struct foo { struct foo_consumer *consumers; unsigned long flags; }; #include <stdbool.h> /* * For foo @foo, delete the consumer @fc. * Return true if the @fc is deleted sfccessfully * or return false. */ static bool consumer_del(struct foo *foo, struct foo_consumer *fc) { struct foo_consumer **con; bool ret = false; for (con = &foo->consumers; *con; EXP4) { if (*con == fc) { *con = EXP5; ret = true; break; } } return ret; } ``` 題目給的程式碼是要將 foo 裡特定的 foo_consumer 刪除，而看到 foo_consumer 的結構中有一個 next 的指標，可以確定這是一個 single linked-list 的結構，要找到特定節點的方式就是遍尋整個 linked-list。先看迴圈的條件， `con` 的型態是指標的指標，一開始先指向第一個 foo_consumer 的指標，結束條件是 `*con` 為 0 ，也可以說 `con` 指向 NULL ，遞迴則很明顯必須使 `con` 指向下一個 foo_consumer，EXP4 需填入 `*con = (*con)->next` > `con = &((*con)->next)` 作用相同，但不符合最簡潔的原則而如果找到要刪除的節點，就將 `con` 的內容，也就是指向 next 的指標，使其指向下一個 foo_consumer ，就完成刪除的動作了。當進行刪除之後，將結果紀錄為 true，若沒有刪除，表示沒有找到要刪除的節點，結果為 false。接著討論區分成 foo 與 foo_consumer 的好處，首先我聯想到的是 hash table 也有類似的結構，在 hash table 中，會有一個存放 hlist_head 的陣列，指向一個特定 hash 值的開頭(或是 NULL)，而真正存放 key 的 hlist_node，則是用 linked-list 的方式接在後面，這樣做的目的是因為 hlist_head(也就是 hash 值)的範圍要是固定的，而不會因為刪除 hlist_node 等因素就使長度改變。另一個可能的好處是同一個 foo 底下的 foo_consmuer 在進行特定操作時，可能會需要用到一個固定的參數，如果每一個 foo_consumer 都要放同一個參數，就會浪費空間，反之放在 foo 底下就可以供所有 foo_consumer 使用時去呼叫。這是對 foo 底下 flags 的猜想，題目並沒有使用到這個變數。 --- ### 測驗 4 #### 答案 EXP6 = `list_del(&t->list)` EXP7 = `list_del(&t->list)` EXP8 = `longjmp(sched, 1)` EXP9 = `longjmp(sched, 1)` #### 延伸 - 解釋上述程式碼運作原理，舉出上述 coroutine 實作的限制 (注意 stack) ```c static void task_add(struct list_head *tasklist, jmp_buf env) { struct task *t = malloc(sizeof(*t)); memcpy(t->env, env, sizeof(jmp_buf)); INIT_LIST_HEAD(&t->list); list_add_tail(&t->list, tasklist); } ``` `task_add` 的目的很簡單，就是把一項待作的任務所記錄的 jmp_buf 放到 list 的最後端，待需要的時候，取出來並跳躍到要執行的地方。 ```c static void task_switch(struct list_head *tasklist) { jmp_buf env; if (!list_empty(tasklist)) { struct task *t = list_first_entry(tasklist, struct task, list); EXP6; memcpy(env, t->env, sizeof(jmp_buf)); free(t); longjmp(env, 1); } } ``` `task_switch` 從 task list 中取出第一個 task (如果 list 不為空)，並將其從 list 中刪除，用 `memcpy` 取得該 task 跳躍的目標，並跳躍過去執行。 ```c static void task_join(struct list_head *tasklist) { jmp_buf env; while (!list_empty(tasklist)) { struct task *t = list_first_entry(tasklist, struct task, list); EXP7; memcpy(env, t->env, sizeof(jmp_buf)); free(t); longjmp(env, 1); } } ``` `task_join` 在做的事跟 `task_switch` 很像，不同的是 `task_join` 會一直執行到整個 task list 清空為止，也呼應 fork-join 中 join 的作用。 ```c void schedule(void) { static int i; srand(0xCAFEBABE ^ (uintptr_t) &schedule); /* Thanks to ASLR */ setjmp(sched); while (ntasks-- > 0) { int n = rand() % 5; tasks[i++](&n); printf("Never reached\n"); } task_join(&tasklist); } void task0(void *arg) { jmp_buf env; static int n; n = *(int *) arg; printf("Task 0: n = %d\n", n); if (setjmp(env) == 0) { task_add(&tasklist, env); EXP8; } for (int i = 0; i < n; i++) { if (setjmp(env) == 0) { task_add(&tasklist, env); task_switch(&tasklist); } printf("Task 0: resume\n"); } printf("Task 0: complete\n"); longjmp(sched, 1); } ``` `task0` 與 `task1` 是完全相同的兩個函式，用來模擬兩個不同的 task 在行程排序上的狀況。 ```c int main(void) { void (*registered_task[])(void *) = {task0, task1}; tasks = registered_task; ntasks = ARRAY_SIZE(registered_task); schedule(); return 0; } ``` --- ### 測驗 5 #### 答案 DECL0 = `char __c[1]` #### 延伸 - 解釋上述程式碼運作原理，並佐以〈[ACCESS_ONCE() and compiler bugs](https://lwn.net/Articles/624126/)〉及〈[你所不知道的 C 語言：編譯器和最佳化原理篇](https://hackmd.io/@sysprog/c-compiler-optimization)〉進行說明 ```c #include <stdint.h> #include <string.h> #include <stdlib.h> #define __READ_ONCE_SIZE \ ({ \ switch (size) { \ case 1: \ *(uint8_t *) res = *(volatile uint8_t *) p; \ break; \ case 2: \ *(uint16_t *) res = *(volatile uint16_t *) p; \ break; \ case 4: \ *(uint32_t *) res = *(volatile uint32_t *) p; \ break; \ case 8: \ *(uint64_t *) res = *(volatile uint64_t *) p; \ break; \ default: \ memcpy((void *) res, (const void *) p, size); \ } \ }) static inline void __read_once_size(const volatile void *p, void *res, int size) { __READ_ONCE_SIZE; } #define READ_ONCE(x) \ ({ \ union { \ typeof(x) __val; \ DECL0; \ } __u; \ __read_once_size(&(x), __u.__c, sizeof(x)); \ __u.__val; \ }) ``` 題目敘述 READ_ONCE 取代 ACCESS_ONCE，可以針對不同長度的變數，將其轉換成對應的 volatile 變數，避免編譯器對該變數做最佳化。因為之前不了解 union 的用法，因此先查了一下，union 裡存放的所有變數，其開頭的地址皆是一樣的，且一次只有一個結構中的變數能夠被使用，就是最近一次被賦值的變數，舊的則會被新賦的值覆蓋，如果這時候使用舊的變數則是未定義行為，好處是當結構中的變數彼此關聯不深的時候，用 union 可以節省空間，其所用空間是 union 裡最大的那個成員之大小。回到題目上， `__val` 是我們最終要回傳的變數，而 `__c` (變數名從倒數第二行就可以看出來了，重點是型態)則是用來轉換成對應純量，並給予 volatile 的變數，過程很簡單，就是依照傳入值 `x` 的長度去選擇要用哪一種整數長度的型態，並把 `x` 地址裡的值(就是 `x`)放進去。而根據前面所述， union 的大小是根據最大的成員而定，因此 `__c` 就不能夠比 `__val` 還大，否則空間就浪費掉了，佔用空間最小的型態就是 char，同時我們為了方便，希望 `__c` 是一個指標型態，因此就使用了陣列的形式來寫， `char __c[1]` 可以讓 `__c` 的長度為 1 ，且是一個指標的型態。 > 為何用指標更為方便? > C 語言傳遞參數時都是複製一份副本給函式，因此直接傳遞的值若是要更改，就必須透過返回值(return)來做更動，但是傳遞指標的話，根據指標指向的地址，我們可以直接修改裡面的內容，而不需透過返回值的方式，同時返回值也可用來做為發生錯誤時儲存錯誤資訊的地方。再透過 `__read_once_size` 函式，根據 `x` 所佔的空間大小，去讀取記憶體中相對應長度的空間裡的值，最後用到 union 的特性將值轉回到 `__val` 身上接著討論為何我們需要 `READ_ONCE` 這個巨集，首先我們從 [ACCESS_ONCE()](https://lwn.net/Articles/508991/) 這篇討論中可以知道 ACCESS_ONCE 明確的目標，主要就是賦予變數 volatile 的型態，使編譯器不會在編譯時期對該變數做最佳化，特別是在多執行續的執行環境中，我們需要確保該變數在被讀取的時候，是讀取到最新的值而非舊的值，特別是在確認 mutex lock 的這種狀況下尤其重要。ACCESS_ONCE 最一開始的實作為 ```c #define ACCESS_ONCE(x) (*(volatile typeof(x) *)&(x)) ``` 乍看之下沒有甚麼問題，就是將變數 `x` 加上 volatile 之後重新指派到 `x`，但問題就出在某一些版本下的 compiler ，在做這個動作的時候，如果遇到的不是純量型態(如 int, short, char, double 等)，而是較複雜的型態(如自定義的 struct)時，volatile 便會無效，好巧不巧 mutex lock 就是一個 struct 實作，因此前面所提到的情況便不能用了。最直接的解決辦法就是 ── 不要用會出現問題的 compiler 版本，或是針對結構中純量變數單獨做 volatile 的型態宣告。而 `READ_ONCE` 則是給出另一種解，強迫去使用純量型態，也就是上面提到的 `__read_once_size` 裡所做的事，如此一來就規避了非純量型態不能使用 volatile 的缺點。

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.