---
image: https://graph.facebook.com/2536009636498820/picture?width=96
---
###### tags: ```Linux 核心設計 2022```
# [2022q1 quiz4](https://hackmd.io/@sysprog/linux2022-quiz4)
### 測驗 1
延伸第 3 週測驗題的測驗 7，已知輸入必為大於 0 的數值 (即 x > 0)，以下程式碼可計算 $\lceil log_2(x) \rceil$ ，也就是 ceil 和 log2 的組合並轉型為整數：
```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;
}
```
```EXP1``` 取 ```(r | shift | (x >> 1))```
#### 解釋程式碼原理
參考第 6, 10, 13 行，可推得```EXP1``` 中應有表示式 ```r | shift```。
思考 $\lceil log_2(1) \rceil = 1$, $\lceil log_2(2)\rceil = 1$, $\lceil log_2(3)\rceil = 2$ 的輸出，對應原本的程式碼應有
```c
x--;
......
shift = (x > 0x1) << 0;
x >>= shift;
r |= shift;
```
將以上程式碼簡化成 ```r | shift | (x >> 1)```
#### 改進程式碼
> 改進程式碼，使其得以處理 x = 0 的狀況，並仍是 branchless
原本的程式碼對於 $\lceil log_2(0)\rceil = 1$ 的輸出結果為 32，考量只有 0 的輸出不正確，只要針對 0 做處理即可。在程式碼中加入
```diff
+ if(x){
x--;
+ }
```
再改成 branchless 的方式
```diff
- x--;
+ x -= !!x;
```
#### 在 Linux 核心原始程式碼找出 ceil 和 log2 的組合 (類似的形式)，並解說應用案例
> (提示: 在 Linux 核心排程器就有)
### 測驗 2
複習〈你所不知道的 C 語言: bitwise 操作〉，改寫第 3 週測驗題的測驗 11 裡頭的 fls 函式 (fls 意謂 “find last set”)，使其得以計算 Find first set:
```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;
}
```
取 ```EXP2``` 為 ```t & x```
取 ```EXP3``` 為 ```o += shift```
#### 解說程式碼
參考 [include/asm-generic/bitops/ffs.h](https://github.com/torvalds/linux/blob/master/include/asm-generic/bitops/ffs.h) 實作
#### 在 Linux 核心原始程式碼的 include/asm-generic/bitops 目錄找出相關程式碼，並探討應用案例
### 測驗 3
考慮以下改寫自 Linux 核心的程式碼:
```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;
}
```
取 ```EXP4``` 為 ```&(**con).next```
取 ```EXP5``` 為 ```(**con).next```
#### 解釋上述程式碼運作原理，並探討這樣區分 foo 和 foo_consumer 的好處
考量以下程式碼，這是一種 indirect pointer 應用
```c
int main(){
int x = 123456;
int *xx = &x;
int **xxx = &xx;
// 或是 int **xxx; xxx = &xx;
return 0;
}
```
#### 在 Linux 核心原始程式碼相似技巧的程式碼 (例如 [uprobe](https://docs.kernel.org/trace/uprobetracer.html))，並探討應用案例
### 測驗 4
以下嘗試用 lab0 提及的 setjmp 和 longjmp，用以實作〈你所不知道的 C 語言: goto 和流程控制篇〉闡述的 coroutine，參考的程式執行輸出如下:
```
Task 0: n = 3
Task 1: n = 3
Task 0: resume
Task 1: resume
Task 0: resume
Task 0: complete
Task 1: resume
Task 1: complete
```
原始程式碼如下: (檔名 jmp.c)
```c
#include <setjmp.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "list.h"
struct task {
jmp_buf env;
struct list_head list;
};
static LIST_HEAD(tasklist);
static void (**tasks)(void *);
static int ntasks;
static jmp_buf sched;
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);
}
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);
}
}
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);
}
/* 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);
}
#define ARRAY_SIZE(arr) (sizeof(arr) / sizeof((arr)[0]))
int main(void)
{
void (*registered_task[])(void *) = {task0, task1};
tasks = registered_task;
ntasks = ARRAY_SIZE(registered_task);
schedule();
return 0;
}
```
```EXP6``` 取 ```list_del(&(*t).list);```
```EXP7``` 取 ```list_del(&(*t).list);```
```EXP8``` 取 ```task_switch(&tasklist);```
```EXP9``` 取 ```task_switch(&tasklist);```
#### 解釋上述程式碼運作原理，舉出上述 coroutine 實作的限制 (注意 stack)
新增以下程式碼
```c
#define FUNCTION_TASK(xx, yy) \
void task##xx(void *arg) \
{ \
jmp_buf env; \
static int n; \
n = *(int *) arg; \
\
printf("Task " yy ": n = %d\n", n); \
\
if (setjmp(env) == 0) { \
task_add(&tasklist, env); \
task_switch(&tasklist); \
} \
\
for (int i = 0; i < n; i++) { \
if (setjmp(env) == 0) { \
task_add(&tasklist, env); \
task_switch(&tasklist); \
} \
printf("Task " yy ": resume\n"); \
} \
\
printf("Task " yy ": complete\n"); \
longjmp(sched, 1); \
}
FUNCTION_TASK(2,"2")
FUNCTION_TASK(3,"3")
FUNCTION_TASK(4,"4")
```
使用 ```FUNCTION_TASK(2,"2")``` 即可造出 ```task2```, ```task3```, ```task4``` 函式，將程式碼放入 ```lab0-c``` 專案即可編譯並輸出
輸出一：
```
Task 0: n = 2
Task 0: resume
Task 0: resume
Task 0: complete
Task 1: n = 4
Task 1: resume
Task 1: resume
Task 1: resume
Task 1: resume
Task 1: complete
Task 2: n = 1
Task 2: resume
Task 2: complete
Task 3: n = 3
Task 3: resume
Task 3: resume
Task 3: resume
Task 3: complete
Task 4: n = 0
Task 4: complete
```
輸出二：
```
Task 0: n = 0
Task 0: complete
Task 1: n = 4
Task 1: resume
Task 1: resume
Task 1: resume
Task 1: resume
Task 1: complete
Task 2: n = 2
Task 2: resume
Task 2: resume
Task 2: complete
Task 3: n = 4
Task 3: resume
Task 3: resume
Task 3: resume
Task 3: resume
Task 3: complete
Task 4: n = 2
Task 4: resume
Task 4: resume
Task 4: complete
```
函式 ```task0``` 會輸出 ```n``` 次的 ```Task 0: resume``` ，例如輸出一中 ```Task 0: resume``` 輸出兩次；同理 ```task2```, ```task3```, ```task4``` 函式
參考其它在作業區中的同學([@Masamaloka](https://hackmd.io/@Masamaloka/linux2022-quiz4#%E6%B8%AC%E9%A9%97-4-Coroutine), [@bakudr18](https://hackmd.io/@bakudr18/r1b8zzCbc#%E6%B8%AC%E9%A9%97-4))輸出，有時 Task 0 與 Task 1 交替輸出，但是我的沒有。
將每個 ```task``` 函式的 ```static int n```, 迴圈中的 ```int i``` 位址輸出
```
The seed: 531222422
0x55f0d557a138 Task 0: n = 1
0x7fffa08c764c Task 0: resume
Task 0: complete
0x55f0d557a13c Task 1: n = 3
0x7fffa08c764c Task 1: resume
0x7fffa08c764c Task 1: resume
0x7fffa08c764c Task 1: resume
Task 1: complete
0x55f0d557a12c Task 2: n = 4
0x7fffa08c764c Task 2: resume
0x7fffa08c764c Task 2: resume
0x7fffa08c764c Task 2: resume
0x7fffa08c764c Task 2: resume
Task 2: complete
0x55f0d557a130 Task 3: n = 4
0x7fffa08c764c Task 3: resume
0x7fffa08c764c Task 3: resume
0x7fffa08c764c Task 3: resume
0x7fffa08c764c Task 3: resume
Task 3: complete
0x55f0d557a134 Task 4: n = 1
0x7fffa08c764c Task 4: resume
Task 4: complete
```
可以發現 the address of ```static int n``` 為不同的數值，而 the address of ```int i``` 為相同數值。可以推定 ```void schedule(void)``` 函式中使用 ```tasks[i++](&n);``` 會使每個 ```task``` 函式(callee) 中的變數指向同個位址。
#### 對比 concurrent-programs 裡頭的 coroutine 程式碼，如 tinync 和 preempt_sched，嘗試引入 UNIX Signal 來做到 preemptive scheduling
#### 對比〈A brief history of the Linux Kernel’s process scheduler: The very first scheduler, v0.01〉，解說早期 Linux 核心 CPU 排程器的行為，並利用上述程式碼來模擬
### 測驗 5
〈你所不知道的 C 語言：前置處理器應用篇〉已提過若干 Linux 核心的巨集，不難發現這些巨集經歷多次演變。Linux 核心一度有個巨集 ACCESS_ONCE，其作用是確實地讀取所指定記憶體位址的內容值，且限這一次，其原始定義如下:
```c
#define ACCESS_ONCE(x) (*(volatile typeof(x) *)&(x))
```
ACCESS_ONCE 巨集的使用情境，可參照 Linux v4.0 的 kernel/locking/mutex.c:
```c
while (true) {
struct task_struct *owner;
...
/*
* If there's an owner, wait for it to either
* release the lock or go to sleep.
*/
owner = ACCESS_ONCE(lock->owner);
if (owner && !mutex_spin_on_owner(lock, owner))
break;
```
然而，如果不使用 ACCESS_ONCE 巨集，程式碼如下:
```c
while (true) {
struct task_struct *owner;
...
/*
* If there's an owner, wait for it to either
* release the lock or go to sleep.
*/
owner = lock->owner;
if (owner && !mutex_spin_on_owner(lock, owner))
break;
```
由於，編譯器偵測到第 8 行的 owner = lock->owner 在迴圈中沒有被更改，所以其最佳化機制可能將第 8 行的程式碼搬出 while 迴圈之外，如此不用每次都實際地讀取 lock->owner，其程式碼變成:
```c
struct task_struct *owner = lock->owner;
while (true) {
...
if (owner && !mutex_spin_on_owner(lock, owner))
break;
```
但問題來了，lock->owner 有可能被其它核心執行緒修改，從而造成資料不一致。因此使用 ACCESS_ONCE 巨集可以防止編譯器做相關最佳化工作，並確保每次都能到實體記憶體位址讀取。其做法便是將某參數暫時性地轉換成具備 volatile 的型態。如此，存取該參數在非引入 ACESS_ONCE 巨集之處 (不具 volatile 特性)，仍可享用編譯器最佳化的好處。
在 ACCESS_ONCE() and compiler bugs 則提及 Linux 核心捨棄上述 ACCESS_ONCE 巨集，改為 READ_ONCE 巨集。在 Linux 核心原始程式碼曾存在以下註解:
> ACCESS_ONCE will only work on scalar types. For union types, ACCESS_ONCE on a union member will work as long as the size of the member matches the size of the union and the size is smaller than word size.
> The major use cases of ACCESS_ONCE used
> 1. to be Mediating communication between process-level code and irq/NMI handlers, all running on the same CPU, and
> 2. Ensuring that the compiler does not fold, spindle, or otherwise mutilate accesses that either do not require ordering or that interact with an explicit memory barrier or atomic instruction that provides the required ordering.
以下是可能的實作:
```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 巨集會判斷變數的寬度，針對寬度為 1, 2, 4, 8 位元組的變數，將其轉換為對應的純量 (scalar) 型態並增加 volatile 關鍵字，而對於其他資料寬度的類型，改呼叫 memcpy 來避免編譯器對該變數進行最佳化。
取 ```DEL0``` 為 ```char c[1]```
#### 解釋上述程式碼運作原理，並佐以〈ACCESS_ONCE() and compiler bugs〉及〈你所不知道的 C 語言：編譯器和最佳化原理篇〉進行說明
#### 研讀〈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