Try   HackMD

2022q1 Homework4 (quiz4)

contributed by < hsuedw >

測驗 1

題目

延伸第 3 週測驗題的測驗 7，已知輸入必為大於 0 的數值 (即 x > 0)，以下程式碼可計算

⌈log 2 (x)⌉，也就是 ceil 和 log2 的組合並轉型為整數:

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 應以最簡潔的形式撰寫，且符合作業一排版規範 (近似 Linux 核心程式碼排版風格)
  • EXP1 為表示式，限制使用 ^, &, |, <<, >> 這幾個運算子，可能會出現常數
  • EXP1 不該包含小括號 (即 ( 和 ))
  • 為了自動批改的便利，變數出現的順序 (可從缺) 從左到右為 r, shift, x
  • EXP1 不可包含 , 和 ; 這樣的分隔符號 (separator)

作答

  • EXP1: r | shift | x >> 1

延伸問題 1. 解釋上述程式碼運作原理

為了說明方便，將題目的程式碼改寫如下。程式長得跟題目有點不一樣，但效果是等價的。這個程式的運做原理與第 3 週測驗題的測驗 7 如出一轍，事實上就是 binary search。請參閱其說明。
讀完第 3 周測驗題第 7 題的說明後，請將注意力集中在第 22~26 行。因為本周的這一題就是要把這幾行濃縮成一行，並且取代第 28 行的變數 r。
如果可以理解下面兩點，就可以理解為什麼　EXP1　要實作為 r | shift | x >> 1。

  1. EXP1 中的 shift 就是第 22 行的 shift。
  2. EXP1 中的 x >> 1 就是第 26 行的 shift。
    因為第 3 週測驗題的測驗 7 是計算
    ⌊log2⁡2x⌋    。而本題是計算
    ⌈log2⁡2x⌉    。所以 ceil_log2() 在回傳時要加 1。





























int ceil_log2(uint32_t x)
{
    uint32_t r, shift;

    x--;

    r = 0;
    shift = (x > 0xFFFF) << 4;
    x >>= shift;
    r |= shift;

    shift = (x > 0xFF) << 3;
    x >>= shift;
    r |= shift;

    shift = (x > 0xF) << 2;
    x >>= shift;
    r |= shift;

    shift = (x > 0x3) << 1;
    x >>= shift;
    r |= shift;

    shift = x > 1;
    x >>= shift;   //x >>= (x > 1)
    r |= shift;    //r = r | shift | x >> 1

    return (r) + 1;
}

延伸問題 2. 改進程式碼，使其得以處理 x = 0 的狀況，並仍是 branchless

延伸問題 3. 在 Linux 核心原始程式碼找出 ceil 和 log2 的組合 (類似的形式)，並解說應用案例 (提示: 在 Linux 核心排程器就有)

測驗 2

題目

複習〈你所不知道的 C 語言: bitwise 操作〉，改寫第 3 週測驗題的測驗 11 裡頭的 fls 函式 (fls 意謂 “find last set”)，使其得以計算 Find first set:

#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 應以最簡潔的形式撰寫，且符合作業一排版規範 (近似 Linux 核心程式碼排版風格)
  • EXP2 和 EXP3 限制使用 ^, &, |, <<=, >>=, +=, -= 這幾個運算子，可能會出現常數
  • EXP2 和 EXP3 不該包含小括號 (即 ( 和 ))
  • 為了自動批改的便利，變數出現的順序 (可從缺) 從左到右為 x, o, t, shift，也就是說，你應該寫 x ^ t 而非 t ^ x
  • EXP2 和 EXP3 不可包含 , 和 ; 這樣的分隔符號 (separator)

作答

  • EXP2: x & t
  • EXP3: o += shift

延伸問題 1. 解釋上述程式碼運作原理，並迴避 while, for, goto 等關鍵字以改寫出功能等價的實作

  • 程式碼運作原理

    為了說明方便，將程式碼補齊後，如下所示:

    




























    ​​#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 ((x & t) == 0) {
​​            x >>= shift;
​​            o += shift;
​​        }

​​        shift >>= 1;
​​        t >>= shift;
​​    }

​​    return o;
​​}
    • 首先，了解一下甚麼是 find first set。

      Find first set

    • 其實運作原理就是 binary search。
    • 假設此程式運作在 64 bit 的電腦中。
    • 在經過第 11~13 行後，o ， t ， shift 初值如下
      • o = 1 (o 就是 output，也就是 first set bit 的位置)
      • t = 0xffffffffffffffff (t 的功能就是 bit mask)
      • shift = 64
    • 經第 15~16 行後，t 的值變為 0x00000000ffffffff ， shift 的值變為 32。
      • 也就是在進入 while 迴圈後，判斷 first set bit 在左半邊 (bit 63~32) 還是右半邊 (bit 31~0)。
    • 進入 while 迴圈後，
      • 第一次 iteration:
        • 若第 19 行的條件成立，也就是變數 x 的 bit 31~0 皆為 0。所以， first set bit 在 bit 63~32 之間。
          • x 左移 shift = 32 個 bits。
          • o 累加 shift 的值，也就是 32。
        • 不論第 19 行的條件是否成立，經第 24~25 行後， shifh = 16 ， t = 0x000000000000ffff。
          • 也就是在進入下一個 iteration 後，判斷 first set bit 在左半邊 (bit 31~16) 還是右半邊 (bit 15~0)。
      • 其餘的 iteration 以此類推。
    • 最後的結果，即 first set bit 的位置，會被累計在變數 o 中。

  • 迴避 while, for, goto 等關鍵字以改寫出功能等價的實作

    ​​static inline size_t ffs(unsigned long x)
​​{
​​    int r = 1;

​​    if (!x)
​​        return 0;
​​    if (!(x & 0xffffffff)) {
​​        x >>= 32;
​​        r += 32;
​​    }
​​    if (!(x & 0xffff)) {
​​        x >>= 16;
​​        r += 16;
​​    }
​​    if (!(x & 0xff)) {
​​        x >>= 8;
​​        r += 8;
​​    }
​​    if (!(x & 0xf)) {
​​        x >>= 4;
​​        r += 4;
​​    }
​​    if (!(x & 3)) {
​​        x >>= 2;
​​        r += 2;
​​    }
​​    if (!(x & 1)) {
​​        x >>= 1;
​​        r += 1;
​​    }
​​    return r;
​​}

延伸問題 2. 在 Linux 核心原始程式碼的 include/asm-generic/bitops 目錄找出相關程式碼，並探討應用案例

ffs(linux/blob/master/include/asm-generic/bitops/ffs.h) 實作在 linux/blob/master/include/asm-generic/bitops/ffs.h 中。

測驗 3

題目

考慮以下改寫自 Linux 核心的程式碼:

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

請補完，使 consumer_del 行為符合註解規範。作答規範:

  1. EXP4 和 EXP5 應以最簡潔的形式撰寫，且符合作業一排版規範 (近似 Linux 核心程式碼排版風格)
  2. EXP4 和 EXP5 都包含指標操作 (如 ->)

作答

  • EXP4: con = &(*con)->next
  • EXP5: fc->next 或 (*con)->next

延伸問題 1. 解釋上述程式碼運作原理，並探討這樣區分 foo 和 foo_consumer 的好處

  • 上述程式碼運作原理
    為了說明方便，將程式碼補齊後，還原如下:

    































    ​​  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; con = &(*con)->next) {
​​        if (*con == fc) {
​​            *con = fc->next;
​​            ret = true;
​​            break;
​​        }
​​    }

​​    return ret;
​​}
    • 其實就是用指標的指標對單向鏈結串列進行移除節點的動作。
    • 第 18 行中的 foo 指標，即 consumer_del() 的第一個參數，就是指向單向鏈結串列的第一個節點。
    • 第 18 行中的 fc 指標，即 consumer_del() 的第二個參數，就是指向單向鏈結串列要被移除的節點。
    • 第 20 行中的 con 變數是指標的指標。其作用就是被用來在單向鏈結串列中逐一尋訪個節點，以找尋所要被移除的節點。
      • 在 for 迴圈的迭帶過程中，con 內存著節點中 next 指標的記憶體位址。
      • 當找到所要移除的節點時， con 內存著 fc 前一個節點的 next 的記憶體位址。所以只要把 con 內的值設定為 fc->next 就可以把 fc 所指向的節點自單向鏈結串列中移除。這就是第 25 行 (EXP5) 的作用。

  • 探討這樣區分 foo 和 foo_consumer 的好處

    這樣的實作的精神與 struct list_head 一樣。就是將鏈結串列抽象化。把鏈結串列的實作與節點資料結構的實作分離。當要尋訪鏈結串列中的各個節點時，就沿著 next 指標一路往下走。當找到目標節點時，可用 container_of 這樣的巨集找到目標節點的起始位址，進而存取目標節點的其他 member。
    最明顯的好處就是所有對單向鏈結操作的程式碼 (如新增、刪除節點) 可被所有的單向鏈結串列共用。不需要為每一種資料結構重複實作類似的程式碼 (如新增、刪除節點)。

延伸問題 2. 在 Linux 核心原始程式碼相似技巧的程式碼 (例如 uprobe)，並探討應用案例

測驗 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)

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

請補完，使行為符合註解規範。作答規範:

  1. EXP6, EXP7, EXP8, EXP9 應以最簡潔的形式撰寫，且符合作業一排版規範 (近似 Linux 核心程式碼排版風格)
  2. EXP6 和 EXP7 都包含 List API 的使用
  3. EXP8 和 EXP9 應有函式呼叫

作答

  • EXP6: list_del(&t->list)
  • EXP7: list_del(&t->list)
  • EXP8: longjmp(sched, 1)
  • EXP9: longjmp(sched, 1)

延伸問題 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

題目

〈你所不知道的 C 語言：前置處理器應用篇〉已提過若干 Linux 核心的巨集，不難發現這些巨集經歷多次演變。Linux 核心一度有個巨集 ACCESS_ONCE，其作用是確實地讀取所指定記憶體位址的內容值，且限這一次，其原始定義如下:

#define ACCESS_ONCE(x) (*(volatile typeof(x) *)&(x))

注意 volatile 關鍵字的使用

    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 巨集，程式碼如下:











    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，其程式碼變成:

    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 to be

  1. 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.

以下是可能的實作:

#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: unsigned char __c[1]

延伸問題 1. 解釋上述程式碼運作原理，並佐以〈ACCESS_ONCE() and compiler bugs〉及〈你所不知道的 C 語言：編譯器和最佳化原理篇〉進行說明

因為在 union 中，所有的 member 共用記憶體空間，起始位址相同。所以對其中一個 member 進行讀寫，等同於對其他 member 進行讀寫。
將 __c 宣告為只有一個 unsigned char 元素的陣列，有下列目的:

  1. 此陣列與 __val 在 union 中佔用相同的記憶體空間。且第一個元素的起始位址與 __val 相同。
  2. 陣列的名稱可被視為記憶體位址。所以 __c 就是 __val 的位址。對 __c 這個記憶體位址讀寫，就是對 __val 所佔的記憶體空間做讀寫。又因為 __read_once_size() 的第二個參數的型別是 void * ，也就是個指標，所以將 __c 宣告為陣列正好可以滿足這個需要。剛好可以把 __c 這個記憶體位址傳給 res 這個指標。
  3. 為什麼要把 __c 宣告為 unsigned char 的陣列? 由前面的描述可知我們只是想要對 __val 所佔的記憶體空間做讀寫。但題目的程式碼有沒有對 __val 做取址的動作。我們只是單純的利用 union 的特性與 __c 這個陣列名稱(也就是 __val 的記憶體位址)對 __val 做讀寫。所以，陣列 __c 只需要佔用最小空間。這就是為什麼要將 __c 宣告為 unsigned char 陣列，且只有一個元素的原因。事實上，我覺得也可以將 __c 宣告為其他型別的陣列，且有多個元素。只是比較佔用記憶體空間而已。

延伸問題 2. 研讀〈Why the “volatile” type class should not be used〉和〈並行程式設計: Atomics 操作〉，並分析近期 include/asm-generic/rwonce.h 中 READ_ONCE / WRITE_ONCE 巨集的實作和其演化 (使用 git log 觀察)

答案卷

2022 年 Linux 核心設計第 4 週隨堂測驗 (A)
2022 年 Linux 核心設計第 4 週隨堂測驗 (B)
2022 年 Linux 核心實作第 4 週隨堂測驗 ©

Last changed by 
 
Edward Hsu
2
330
Published on HackMD