2022q1 Homework4 (quiz4)

contributed by < Risheng1128 >

作業說明
測驗題目

測驗 1

延伸問題:

• 解釋上述程式碼運作原理
• 改進程式碼，使其得以處理 x = 0 的狀況，並仍是 branchless
• 在 Linux 核心原始程式碼找出 ceil 和 log2 的組合 (類似的形式)，並解說應用案例 (提示: 在 Linux 核心排程器就有)

程式碼運作原理

參考以下程式碼，目標是可計算出

$[lo{g}_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 的第 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

延伸問題:

• 解釋上述程式碼運作原理，並迴避 while, for, goto 等關鍵字以改寫出功能等價的實作
• 在 Linux 核心原始程式碼的 include/asm-generic/bitops 目錄找出相關程式碼，並探討應用案例

測驗 3

延伸問題:

• 解釋上述程式碼運作原理，並探討這樣區分 foo 和 foo_consumer 的好處
• 在 Linux 核心原始程式碼相似技巧的程式碼 (例如 uprobe)，並探討應用案例

測驗 4

延伸問題:

• 解釋上述程式碼運作原理，舉出上述 coroutine 實作的限制 (注意 stack)
• 對比 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

延伸問題:

• 解釋上述程式碼運作原理，並佐以〈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 觀察)