2022q1 Homework4 (quiz4)

測驗題目

測驗 1

程式碼運作原理

功能

輸入大於 0 的無號整數，計算

$\lceil lo{g}_2(x)\rceil$

實做

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 lo{g}_2(x)\rceil =lo{g}_2(x-1)+1,x\ne 1$$

此算法在 x = 1 時會輸出 1 ，為錯誤答案。

根據第三周測驗 7 的作法，EXP1 必須包含尚未完成的 r | shift 以及剩下最後 2 bits 的判斷與處理，而最後 2 bits 的判斷可以用 x >> 1 來實做，因此

• EXP1 = r | shift | x << 1

TODO

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

---

測驗 2

程式碼運作原理

ffs (find first set)

找到從低位開始的第一個 1，並回傳其索引值。

實做

#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

TODO

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

---

測驗 3

程式碼運作原理

功能

從結構體 struct foo 中刪除特定的 struct foo_consumer。

改寫自 Linux 核心的實做

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。

TODO

1. 探討這樣區分 foo 和 foo_consumer 的好處
2. 在 Linux 核心原始程式碼相似技巧的程式碼 (例如 uprobe)，並探討應用案例

---

測驗 4

程式碼運作原理

setjmp 和 longjmp

co-coutine 實做

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()

struct task {
    jmp_buf env;
    struct list_head list;
};

task 的結構包含以個 list 以及一個 jmp_buf。

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。

/* 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。

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)

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 的尾端。

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 來避免編譯器對該變數進行最佳化。

實作

#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 關鍵字。

#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]。

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 觀察)