---
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 的缺點。
Sign in with Wallet
Connect another wallet