---
tags: 2022 linux kernel
---

# 2022q1 Homework4 (quiz4)
contributed by < [`Risheng1128`](https://github.com/Risheng1128) >

> [作業說明](https://hackmd.io/@sysprog/linux2022-homework4)
> [測驗題目](https://hackmd.io/@sysprog/linux2022-quiz4)

## 測驗 `1`
:::info
延伸問題:
- [x] 解釋上述程式碼運作原理
- [ ] 改進程式碼，使其得以處理 `x = 0` 的狀況，並仍是 branchless
- [ ] 在 Linux 核心原始程式碼找出 ceil 和 log2 的組合 (類似的形式)，並解說應用案例 (提示: 在 Linux 核心排程器就有)
:::
### 程式碼運作原理
參考以下程式碼，目標是可計算出 $[log_2(x)]$

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;
}

這題的手法和 [quiz3](https://hackmd.io/@Risheng/linux2022-quiz3) 的第 `7` 題相似，相同處在於上述程式碼的 `line 5 ~ 14` ，目的是為了找到 `x` 最高位元為 `1` 的位置，接著可以發現最多只有右移 `30` 次，因此可以合理推論 `EXP1` 為判斷最後一個 bit 位置的判斷式，因此 `EXP1 = r | shift | x >> 1`

至於不同的地方在於 `line 4` 的 `x--` ，可以分成以下兩種情況
- 如果 `x` 為 2 的冪， `x--` 會讓整個位數少一位，最後在用 `line 15` 的加 `1` 補回正確解答
- 如果 `x` 不為 2 的冪， `x--` 不影響 `x` 位數的改變，最後 `line 15` 的加 `1` 會取 `ceil()`

int ceil_log2(uint32_t x)
{
    uint32_t r, shift;
    x--;
    // 判斷 x 是否需要 16 個 bit 去儲存
    r = (x > 0xFFFF) << 4;                                                                                                                                    
    x >>= r;
    // 判斷 x 是否需要 8 個 bit 去儲存
    shift = (x > 0xFF) << 3;
    x >>= shift;
    r |= shift;
    // 判斷 x 是否需要 4 個 bit 去儲存
    shift = (x > 0xF) << 2;
    x >>= shift;
    r |= shift;
    // 判斷 x 是否需要 2 個 bit 去儲存
    shift = (x > 0x3) << 1;
    x >>= shift;
    // x >> 1: 加上原本 x 的 MSB
    return (r | shift | x >> 1) + 1;
}

## 測驗 `2`
:::info
延伸問題:
- [ ] 解釋上述程式碼運作原理，並迴避 while, for, goto 等關鍵字以改寫出功能等價的實作
- [ ] 在 Linux 核心原始程式碼的 [include/asm-generic/bitops](https://github.com/torvalds/linux/tree/master/include/asm-generic/bitops) 目錄找出相關程式碼，並探討應用案例
:::

## 測驗 `3`
:::info
延伸問題:
- [ ] 解釋上述程式碼運作原理，並探討這樣區分 foo 和 foo_consumer 的好處
- [ ] 在 Linux 核心原始程式碼相似技巧的程式碼 (例如 [uprobe](https://docs.kernel.org/trace/uprobetracer.html))，並探討應用案例
:::

## 測驗 `4`
:::info
延伸問題:
- [ ] 解釋上述程式碼運作原理，舉出上述 [coroutine](https://en.wikipedia.org/wiki/Coroutine) 實作的限制 (注意 stack)
- [ ] 對比 [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
- [ ] 對比 [〈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 排程器的行為，並利用上述程式碼來模擬
:::

## 測驗 `5`
:::info
延伸問題:
- [ ] 解釋上述程式碼運作原理，並佐以〈[`ACCESS_ONCE()` and compiler bugs](https://lwn.net/Articles/624126/)〉及〈[你所不知道的 C 語言：編譯器和最佳化原理篇](https://hackmd.io/@sysprog/c-compiler-optimization)〉進行說明
- [ ] 研讀〈[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` 觀察)
:::