---
tags: linux kernel, linux2022
---
# 2022q1 Homework4 (quiz4)
> [測驗題目](https://hackmd.io/@sysprog/linux2022-quiz4)
## 測驗 `1`
### 程式碼運作原理
#### 功能
輸入大於 `0` 的無號整數，計算 $\lceil log_2(x) \rceil$
#### 實做
```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` 的作法，最後在回傳值 `+1` 處理 `ceil`。
最開頭 `x--` 目的是處理當 `x` 為 2 的冪時，取 `ceil` 不應 `+1`。
其公式如下：
$$
\lceil log_2(x) \rceil = log_2(x-1)+1,~ x \neq 1
$$
:::danger
:warning: 此算法在 `x = 1` 時會輸出 `1` ，為錯誤答案。
:::
根據第三周測驗 `7` 的作法，`EXP1` 必須包含尚未完成的 `r | shift` 以及剩下最後 2 bits 的判斷與處理，而最後 2 bits 的判斷可以用 `x >> 1` 來實做，因此
* `EXP1` = `r | shift | x << 1`
:::success
TODO
2. 改進程式碼，使其得以處理 x = 0 的狀況，並仍是 branchless
3. 在 Linux 核心原始程式碼找出 ceil 和 log2 的組合 (類似的形式)，並解說應用案例 (提示: 在 Linux 核心排程器就有)
:::
---
## 測驗 `2`
### 程式碼運作原理
#### ffs (find first set)
找到從低位開始的第一個 `1`，並回傳其索引值。
#### 實做
```c
#define BITS_PER_BYTE 8
#define BITS_PER_LONG (sizeof(unsigned long) * BITS_PER_BYTE)
#include <stddef.h>
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;
shift >>= 1;
t >>= shift;
while (shift) {
if ((EXP2) == 0) {
x >>= shift;
EXP3;
}
shift >>= 1;
t >>= shift;
}
return o;
}
```
其作法也是利用 binary search 找到 `1` 的位置。
首先，`shift` 為 `BITS_PER_LONG` 除以 2，接著將 `t` 右移 `shift` 位，使 `t` 成為高位半邊全為 `0` 的 `unsigned long`。
然後是 `while` 迴圈的部份，目的是要找到 `1` 位於高位還是低位，所以利用 `x` 與 `t` 作 AND 運算，為 `0` 代表在低位沒有 `1` 出現，將 `x` 右移 `shift` 位，並計算 `o += shift` 紀錄位置。
因此：
* `EXP2` = `x & t`
* `EXP3` = `o += shift`
:::success
TODO
1. 迴避 while, for, goto 等關鍵字以改寫出功能等價的實作
2. 在 Linux 核心原始程式碼的 include/asm-generic/bitops 目錄找出相關程式碼，並探討應用案例
:::
---
## 測驗 `3`
### 程式碼運作原理
#### 功能
從結構體 `struct foo` 中刪除特定的 `struct foo_consumer`。
#### 改寫自 Linux 核心的實做
```c
truct 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;
}
```
用一個 pointer to pointer `con` 走訪 `foo->consumers` 的所有 `foo_consumers`，因此每次 `con` 應該都要址向下一個 `foo_consumers` 位置，所以：
* `EXP4` = `con = &(*con)->next`
當找到目標 `fc` 後，`con` 要指向 `fc` 下一個 `foo_consumers`，所以：
* `EXP5` = `fc->next`。
:::success
TODO
1. 探討這樣區分 foo 和 foo_consumer 的好處
2. 在 Linux 核心原始程式碼相似技巧的程式碼 (例如 uprobe)，並探討應用案例
:::
---
## 測驗 `4`
### 程式碼運作原理
#### setjmp 和 longjmp
#### co-coutine 實做
```c
int main(void)
{
void (*registered_task[])(void *) = {task0, task1};
tasks = registered_task;
ntasks = ARRAY_SIZE(registered_task);
schedule();
return 0;
}
```
首先，宣告一個 `*registered_task[]` 陣列，包含 `task0` 與 `task1`。
`tasks` 是一個指標的指標，指向 `registered_task`。
`ntasks` 是負責紀錄 `registered_task` 中 `task` 的數量。
接著，執行 `schedule()`
```c
struct task {
jmp_buf env;
struct list_head list;
};
```
`task` 的結構包含以個 list 以及一個 `jmp_buf`。
```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);
}
```
先 `setjump` 紀錄當下的 `jump_buf` 使後續初始化還可以跳回 `schedule()`。
while loop 的地方負責隨機呼叫 `tasks` 中的 function pointer 並進行初始化，接著`tasklist` 會紀錄每一個 task，然後呼叫 `task_join()` 執行 `tasklist` 中的 task。
```c
/* A task yields control n times */
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);
}
void task1(void *arg)
{
jmp_buf env;
static int n;
n = *(int *) arg;
printf("Task 1: n = %d\n", n);
if (setjmp(env) == 0) {
task_add(&tasklist, env);
EXP9;
}
for (int i = 0; i < n; i++) {
if (setjmp(env) == 0) {
task_add(&tasklist, env);
task_switch(&tasklist);
}
printf("Task 1: resume\n");
}
printf("Task 1: complete\n");
longjmp(sched, 1);
}
```
`task0` 和 `task1` 的內容結構式是相同的，會先進行 `setjump`，然後把 `jump_buf` 加入 `tasklist` 中，初始化完成後再跳回 `schedule`，所以：
* `EXP8` = `longjmp(sched, 1)`
後續藉由 `task_join` 切回來時，由於 `longjmp` 的參數設為 `1`，所以 `setjmp` 的回傳值就會都是 `1`，因此會接續執行後面的 for loop。
在 for loop 中，會先 `setjmp`，並執行 `task_switch` 切換到下一個 task，當再一次跳回來時，會印出 resume。直到執行 `arg` 次，跳出迴圈，會印出 complete。最後再 `longjmp` 到 `schedule`。
```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);
}
}
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_switch` 與 `task_join` 的內容是一樣的，只是 `task_join` 是在 `schedule` 被呼叫；而 `task_switch` 是在 `task0`、`task1` 被呼叫。
這兩個涵式的目的是取出 `tasklist` 的第一個 entry 的 `jump_buf`，並跳到其對應的位置執行。
1. 首先判斷 `tasklist` 是否為空
2. 不為空的話，先取出第一個 entry，並將其從 list 刪除
3. 然後複製該 entry 的 `jump_buf`
4. 釋放該 entry，接著 `longjmp` 到 `env` 對應的位置
因此:
* `EXP6` = `list_del(&t->list)`
* `EXP7` = `list_del(&t->list)`
```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` 負責將 `env` 加入到 `tasklist` 的尾端。
:::success
TODO
1. 舉出上述 coroutine 實作的限制 (注意 stack)
2. 對比 concurrent-programs 裡頭的 coroutine 程式碼，如 tinync 和 preempt_sched，嘗試引入 UNIX Signal 來做到 preemptive scheduling
3. 對比〈A brief history of the Linux Kernel’s process scheduler: The very first scheduler, v0.01〉，解說早期 Linux 核心 CPU 排程器的行為，並利用上述程式碼來模擬
:::
---
## 測驗 `5`
### 程式碼運作原理
#### READ_ONCE
> 巨集會判斷變數的寬度，針對寬度為 1, 2, 4, 8 位元組的變數，將其轉換為對應的純量 (scalar) 型態並增加 volatile 關鍵字，而對於其他資料寬度的類型，改呼叫 memcpy 來避免編譯器對該變數進行最佳化。
#### 實作
```c
#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;
}
```
巨集 `__READ_ONCE_SIZE` 利用 switch 配別不同 `size`，並根據 `size` 轉換對應的純量型態並加上 `volatile` 關鍵字。
```c
#define READ_ONCE(x) \
({ \
union { \
typeof(x) __val; \
DECL0; \
} __u; \
__read_once_size(&(x), __u.__c, sizeof(x)); \
__u.__val; \
})
```
巨集 `READ_ONCE` 宣告一個 uion `__u`，而 uion 所佔的記憶體大小是根據佔據的最大空間成員的大小來定，因此 `__c` 必須為佔據空間最小的型態，所以：
* `DECL0` = `char __c[1]`。
:::success
TODO
1. 佐以〈ACCESS_ONCE() and compiler bugs〉及〈你所不知道的 C 語言：編譯器和最佳化原理篇〉進行說明
2. 研讀〈Why the “volatile” type class should not be used〉和〈並行程式設計: Atomics 操作〉，並分析近期 include/asm-generic/rwonce.h 中 READ_ONCE / WRITE_ONCE 巨集的實作和其演化 (使用 git log 觀察)
:::
Sign in with Wallet
Connect another wallet