---
tags: linux2022
---
# 2022q1 Homework4 (quiz4)
contributed by < [ganoliz](https://github.com/ganoliz) >
## 測驗一
延伸[第 3 週測驗題](https://hackmd.io/@sysprog/linux2022-quiz3)的測驗 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``` = ?
### 解題思路
這題的方式其實就是應用 $log_2$ 以二為底的方式，因此可以只用 bit-wise 操作來完成這個計算
```graphviz
digraph test{
rankdir="LR"
Node[shape=record]
Node1[label="X|{0|x| F| F| F| F|<1>F | F| F|F}"]
Node2[label="{0|x|<1>F | F| F|F}"]
Node3[label="{0|x|<1> F| F|F}"]
Node4[label="{0|x|<1> F|F}"]
Node2:1 -> Node1:1 [label="test bigger than"]
}
```
當我們確認到 x 大於 2 的 16 次方，我們就將 shift 設為 16 次方，然後位移後繼續計算是否 x 大於 2 的 8次方、四次方與 2 次方。所以當我們做到二次方之後，我們位移完可以知道 x 是介於 0~3 之間， 因此我們需要先將 result 與 shift 加起來之後再對剩下的 x 做 shift 看看值是否大於 2 ( 2 的一次方) 做加法。
那因為我們的 "加法" 都是不同的位元沒有進位的問題，因此我們加法都用 or 運算代替來加速即可。
```EXP1 = r | shift | x >> 1```
整個式子為
```c
return (r | shift | x >> 1 ) + 1;
```
值得一提的是最前面的 `x--` 與 最後的 +1 為做ceil 的動作。因為無論是剛好 x 是剛好在 2 的 n 次方 或是 更小介於 2 的 n-1 ~ n 次方的值最後都會對應到依樣的值， 當超過 1 時就會自動進一位。
:::warning
雖然這個答案與正確答案一致， 但這裡有一個 bug 。當我們 x = 1 時 $\lceil log_2(x) \rceil$ 應為 0 ，但是考慮這個值代表我們要多用一個判斷式來去輸出 0 。
:::
:::success
延伸問題:
1. 解釋上述程式碼運作原理
2. 改進程式碼，使其得以處理 x = 0 的狀況，並仍是 branchless
3. 在 Linux 核心原始程式碼找出 ceil 和 log2 的組合 (類似的形式)，並解說應用案例 (提示: 在 Linux 核心排程器就有)
:::
---
## 測驗二
複習[〈你所不知道的 C 語言: bitwise 操作〉](https://hackmd.io/@sysprog/c-bitwise)，改寫[第 3 週測驗題](https://hackmd.io/@sysprog/linux2022-quiz3)的測驗 11 裡頭的 fls 函式 (fls 意謂 “find last set”)，使其得以計算 [Find first set](https://en.wikipedia.org/wiki/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``` = ?
```EXP3``` = ?
### 解題思路
首先我們先看看整個程式碼， 首先 t 的值初始化為 0xFFFFFFFF 而 shift 則為 32 >> 1 = 16，
t 經過 shift 之後變成 0xFF 。 在 while 迴圈下 shift 要大於 1 ，而 shift 每次會右移 1 因此在 shift 在未知條件下沒有動到這個值， 則 shift 四次就為 1 。 t 則是會右移 shift 的值(16、8、4、2、1)。
那我們就來看看比較簡單的 ```EXP2``` 由於是一個要等於 0 的判斷式，我們知道 find first set 是要找到第一個為 1 的最低位元 bits 。因此
```EXP2 = x & t```
當我們的值為 0 時代表 x 這些 bits 沒有任何為 1 的值 (t 的 bits 在 shift 前都為 1 )，於是 x 就可以往下一個 shift 前進。
接著看一下我們要回傳的值為 o ，那這裡位移的話，肯定跟輸出有關係。這是一個改變 o 的表示式，而且跟 shift 位移有關，因此我們可以得到:
```EXP3 = o += shift```
為此題的解。
值得一提的是 shift 透過拆成一半一半的方式來找 find first set 。假如右邊那一半沒有找到， x 直接往右 shift (相當於 t 左移)。 若有則透過 t 右移 來縮小的範圍來找 fiest set 。
```graphviz
digraph test{
rankdir="LR"
Data[label="X|{0|x|F|F|F|F|<1>F|F|F|F}" ,shape=record]
t1[label="t1 shift = 16|{<1>0xFFFF}" ,shape=record]
t2[label="t2 shift = 8|{0xFF}" ,shape=record]
t3[label="t3 shift = 4|{0xF}" ,shape=record]
t4[label="t4 shift = 2|{0x3}" ,shape=record]
t1:1 -> Data:1 [label="and operation "]
}
```
:::success
延伸問題:
1. 解釋上述程式碼運作原理，並迴避 while, for, goto 等關鍵字以改寫出功能等價的實作
2. 在 Linux 核心原始程式碼的 [include/asm-generic/bitops](https://github.com/torvalds/linux/tree/master/include/asm-generic/bitops) 目錄找出相關程式碼，並探討應用案例
:::
---
## 測驗三
考慮以下改寫自 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 successfully
* 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``` = ?
```EXP5``` = ?
### 解題思路
首先我們可以知道這題就是要刪除掉目標 foo_consumer 節點 *fc 。這裡透過 **con 指標的指標來尋找 foo 的 foo_consumer 成員， 因此 for 迴圈的敘述我們可以知道:
```EXP4 : con=&(*con->next)```
也可以寫成
```EXP4 : con=&(*con)->next```
因為 -> 的優先度高於 & 取址運算子
然後我們要刪節點的話，我們需要將刪除節點的上一個 foo_comsumer 指向下一個 foo_comsumer ，仔細想想可以用函數引數的 *fc 來寫，因此:
```EXP5 : fc->next```
:::success
延伸問題:
1. 解釋上述程式碼運作原理，並探討這樣區分 foo 和 foo_consumer 的好處
2. 在 Linux 核心原始程式碼相似技巧的程式碼 (例如 [uprobe](https://docs.kernel.org/trace/uprobetracer.html))，並探討應用案例
:::
---
## 測驗四
以下嘗試用 [lab0](https://hackmd.io/@sysprog/linux2022-lab0) 提及的 [setjmp](https://man7.org/linux/man-pages/man3/setjmp.3.html) 和 [longjmp](https://man7.org/linux/man-pages/man3/setjmp.3.html)，用以實作[〈你所不知道的 C 語言: goto 和流程控制篇〉](https://hackmd.io/@sysprog/c-control-flow)闡述的 [coroutine](https://en.wikipedia.org/wiki/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``` = ?
```EXP7``` = ?
```EXP8``` = ?
```EXP9``` = ?
1. EXP6 和 EXP7 都包含 List API 的使用
2. EXP8 和 EXP9 應有函式呼叫
### 解題思路
我們先以 Top-Down 的方式來看程式碼，在 main() 裡， 首先我們創造一個指標陣列，裡面存放 task0 以及 task1 ，接著我們將 registered_task 對應於 前面宣告的 static void (**tasks)(void *); ， ntasks 則是看看 registered_task 有幾個 task (這題為兩個) ，然後進行 schedule() 。在 schedule 裡我們會設定跳躍的目的 setjump(sched) ，然後根據我們的 i 來去執行 tasks[i++] (task0 或是 task1)。
當我們在 task0 或 task1 時，都會 setjump(env) 作為跳躍目的地點。因此我們可以知道 tasklist 保存許多 task 的目前的 env 位置。 於是我們可以先將 task_switch 的 EXP6 補齊 。
```EXP6 = list_del(&t->list)```
將我們的 task 切換到 t 的成員env ，把這個節點刪除後， longjump 到這個節點的中斷位置繼續執行。
至於 task_join 的地方，我們可以看到是在 schedule 的最後才會呼叫，且條件是 ntasks-- <=0 意思是 tasklist 裡只剩一個節點。 因此我們可以知道這裡 依舊是:
```EXP7 = list_del(&t->list) ```
至於 ```EXP8``` 和 ```EXP9``` 也是相同的東西。這裡比較細一點，我們看看輸出 log :
```
Task 0: n = 3
Task 1: n = 3
Task 0: resume
Task 1: resume
......
```
```graphviz
digraph test {
scheduler[label="scheduler "]
task0
task1
tasks[label="[i++](&n)" shape=diamond];
task_join
scheduler->setjump
setjump->tasks [label="nsize-- > 0"]
setjump->task_join[label="nsize-- <= 0"]
tasks->task0[label="i=0"]
tasks->task1[label="i=1"]
task0->setjump
task1->setjump
task_join->task_join[label="while(task_list != empty)"]
}
```
```graphviz
digraph test{
rankdir="LR"
tasklist[label="tasklist|{<1>env1|<2>env2|env3|env4| <3> new }" shape="record" ]
env1[shape=record]
task_join->tasklist:1[label="long_jump(env)"]
tasklist:1->env1[label="1. task work"]
env1->tasklist:2[label="3. task_switch"]
env1->tasklist:3[label="2. task_add" arrowhead=vee]
}
```
我們可以知道說我們先 print 出了 Task 0: n = 3 然後換到另一個執行程序去 print Task 1: n = 3 ， 因此我們可以確定 ```EXP8``` 和 ```EXP9``` 就是一個跳出或是此行程的函式呼叫(這裡不用 task_switch 是因為其他行程還沒有加入此 task_list ，要先跳回 scheduler 繼續註冊)。
因此
```EXP8 = longjmp(sched, 1)```
```EXP9 = longjmp(sched, 1)```
:::success
延伸問題:
1. 解釋上述程式碼運作原理，舉出上述 coroutine 實作的限制 (注意 stack)
2. 對比 [concurrent-programs](https://github.com/sysprog21/concurrent-programs) 裡頭的 coroutine 程式碼，如 [tinync](https://github.com/sysprog21/concurrent-programs/tree/master/tinync) 和 [preempt_sched](https://github.com/sysprog21/concurrent-programs/tree/master/preempt_sched)，嘗試引入 UNIX Signal 來做到 preemptive scheduling
3. 對比[〈A brief history of the Linux Kernel’s process scheduler: The very first scheduler, v0.01〉](https://dev.to/satorutakeuchi/a-brief-history-of-the-linux-kernel-s-process-scheduler-the-very-first-scheduler-v0-01-9e4)，解說早期 Linux 核心 CPU 排程器的行為，並利用上述程式碼來模擬
:::
---
## 測驗五
[〈你所不知道的 C 語言：前置處理器應用篇〉](https://hackmd.io/@sysprog/c-preprocessor)已提過若干 Linux 核心的巨集，不難發現這些巨集經歷多次演變。Linux 核心一度有個巨集 ACCESS_ONCE，其作用是確實地讀取所指定記憶體位址的內容值，且限這一次，其原始定義如下:
```c
#define ACCESS_ONCE(x) (*(volatile typeof(x) *)&(x))
```
> 注意 volatile 關鍵字的使用
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;
```
但問題來了，lock->owner 有可能被其它核心執行緒修改，從而造成資料不一致。因此使用 ACCESS_ONCE 巨集可以防止編譯器做相關最佳化工作，並確保每次都能到實體記憶體位址讀取。其做法便是將某參數暫時性地轉換成具備 volatile 的型態。如此，存取該參數在非引入 ACESS_ONCE 巨集之處 (不具 volatile 特性)，仍可享用編譯器最佳化的好處。
在 [ACCESS_ONCE() and compiler bugs](https://lwn.net/Articles/624126/) 則提及 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.
1. The major use cases of ACCESS_ONCE used 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 來避免編譯器對該變數進行最佳化。
請問，
`DECL0` = ?
> DECL0 為變數宣告，不該存在 ; 和 , 分隔字元
### 解題思路
簡單看一下程式碼，我們知道 DECL0 是一個宣告，一個 .`__c` 的宣告。而這個值會是我們要傳入的 __read_once_size() 的 `*res`，亦即 `__c` 是一個指標指向一個位置。因為我們不能宣告一個指標 `char *__c` 卻沒有告訴它要指向甚麼位置。 因此我們使用 `char[]` 來代替，這個 `__c` 就會有一個明確指向某個記憶體區段為 `char *` 的位置，因此 DECL0 為 `char __c[1]`。
:::success
延伸問題:
1. 解釋上述程式碼運作原理，並佐以[〈ACCESS_ONCE() and compiler bugs〉](https://lwn.net/Articles/624126/)及[〈你所不知道的 C 語言：編譯器和最佳化原理篇〉](https://hackmd.io/@sysprog/c-compiler-optimization)進行說明
2. 研讀[〈Why the “volatile” type class should not be used〉](https://docs.kernel.org/process/volatile-considered-harmful.html)和[〈並行程式設計: Atomics 操作〉](https://hackmd.io/@sysprog/concurrency-atomics)，並分析近期 [include/asm-generic/rwonce.h ](https://github.com/torvalds/linux/blob/master/include/asm-generic/rwonce.h)中 READ_ONCE / WRITE_ONCE 巨集的實作和其演化 (使用 git log 觀察)
:::
Sign in with Wallet
Connect another wallet