2022q1 Homework4 (quiz4)

contributed by < kevinshieh0225 >

測驗題目

測驗 1 : ceil log_2(x)

以下程式碼實現對 x 取

$\lceil lo{g}_2(x)\rceil$ ，我們先依序為程式碼下十進位理解下的註解：

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

    x--;                        // x 減一
    r = (x > 0xFFFF) << 4;      // 如果 x 大於 (2 ^ 16 - 1)，指派 r 為 16                                         
    x >>= r;                    // 若 r 非 0，x 除以 (2 ^ 16) 捨去餘數
    
    shift = (x > 0xFF) << 3;    // 如果 x 大於 (2 ^ 8 - 1)，指派 shift 為 8
    x >>= shift;                // 若 shift 非 0，x 除以 (2 ^ 8) 捨去餘數
    r |= shift;                 // 若 shift 非 0，等價於 16 + 8 = 24
    
    shift = (x > 0xF) << 2;     // 如果 x 大於 (2 ^ 4 - 1)，指派 shift 為 4
    x >>= shift;                // 若 shift 非 0，x 除以 (2 ^ 4) 捨去餘數
    r |= shift;                 // 若 shift 非 0，等價於 24 + 4 = 28
    
    shift = (x > 0x3) << 1;     // 如果 x 大於 (2 ^ 2 - 1)，指派 shift 為 2
    x >>= shift;                // 若 shift 非 0，x 除以 (2 ^ 2) 捨去餘數
    return (EXP1) + 1;          // 應等價於 (r | shift | x >> 1) + 1：28 + 2 然後自動補位
}

大約歸納程式碼後說明流程：

1. 首先了解對於
   $\lceil lo{g}_2(x)\rceil$來說輸出輸入的數值對應範圍表示為：
   $f((2^{n-1},2^n])=n$，可以發現數值對應範圍裡，上界會比其他值多一個位元，這使的處理上會有不一致。所以 x 先減一的目的是要將上界數值下修，最後再一同無條件進位
2. 逐一檢查剩餘的 x 是否比
   $2^n-1$ 還大，如果大於的話我就把值加進到我的 r 紀錄中，並把 x 除以
   $2^n$。紀錄在 record 的代表是說我的 x 起碼大於
   $2^r$。
3. 最後比較向左還是向右找值，x >> 1
4. 最終回傳結果並將差值補回。

EXP1 = r | shift | x >> 1

參考 jim12312321，發現這個函式是 binary search！我們用改成用二進位視角來理解：

/* 我們要找 lg(n) 的天花板
 * 從二進位來看就等於是我們要找 find first set 的意思
 * 最後再加一來達到無條件進位
 */
 
 0000 0000 0000 0000 | 0000 0000 0000 0000 // 是否 x 有高於 16 位元的值
                                           // 並以此決定往高或低位元半側繼續尋找最高位元。

0000 0000 | 0000 0000                      // 循序並記錄累加在 r 內。
...
0 | 0                                      //最後剩下兩個位元，使用 x >> 1 來確認最高位元在左或右。

例外狀況 x = 0

在數學定義上

$log(0)$ 是未定義行為，而如果以上面的函式帶入 x = 0，會導致 x-- 溢位而使輸出結果變成 33。

如果我們 x-- 的目的是為了處理上界的不一致，那其實也可以在最後對輸出做調整：

int ceil_log2(uint32_t x)
{
    int cps = (x & (x-1)) != 0;
    uint32_t r, shift;

    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 (r | shift | x >> 1) + cps;       
}

在我們開始對 x 作位移之前先計算 int cps = (x & (x-1)) != 0; ，用以判斷此數是否為

$2^n$ 的數值，如果是的話我們就不在最後做加一的補償。這除了解決了數值對應範圍不一致的問題，也處理了 x = 0 的例外狀況。此時我們帶入 0 的結果是 0，這樣的結果對我來說是相對可以接受的。

實作詳見 ceil_log2.c

---

測驗 2 : find first set

根據 Find first set 的定義，此函式回傳 least significant 1-bit 的位置。方法本身如同上一題 find last set 的手法，利用 binary search 尋值：

#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;        // 提供 UL 位元長度的 1 遮罩
    size_t shift = BITS_PER_LONG;  // unsigned long 位元數

    shift >>= 1;                   // shift 除以 2
    t >>= shift;                   // shift 位移一半，高位元半側為 0 ，低位元半側為 1

    while (shift) {
        if ((EXP2) == 0) {         // 如果低位元半側無值：fs 必在高位元半側
            x >>= shift;           // 將 x 位移並記錄位元位置於 o 中
            EXP3;
        }

        shift >>= 1;               // 製作新的半側遮罩，以對剩餘半側尋值
        t >>= shift;
    }

    return o;
}

EXP2 : x & t
EXP3 : o += shift

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

在第一題由於我們輸入參數型態為 unsigned int32_t 所以數值長度必定為 32 位元，但本題 unsigned long 會因為不同的資料模型而有 32 或 64 的差異，我們利用條件式來判斷第一次（32 bit）的位移是否執行，接著使用第一題的技巧實作一個幾乎 branchless 的函式：

#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;
    
    int r, shift;
    
    r = (BITS_PER_LONG == 64 && ((x & 0xFFFFFFFF) == 0)) << 5;
    x >>= r;
    
    shift = ((x & 0xFFFF) == 0) << 4;
    x >>= shift;
    r |= shift;
    
    shift = ((x & 0xFF) == 0) << 3;
    x >>= shift;
    r |= shift;
    
    shift = ((x & 0xF) == 0) << 2;
    x >>= shift;
    r |= shift;
    
    shift = ((x & 0x3) == 0) << 1;
    x >>= shift;
    r |= shift;
    
    return r + ((x & 0x1) == 0);
}

實作詳見 ffs.c

linux/include/asm-generic/bitops/

根據不同的使用情境，ffs 有了不同的定義，好比說是否能用 gnu built_in、輸入型態 int , long…。

在其中有一份 __ffs.h 與本題實作情境相同：

/**
 * __ffs - find first bit in word.
 * @word: The word to search
 *
 * Undefined if no bit exists, so code should check against 0 first.
 */
static __always_inline unsigned long __ffs(unsigned long word)
{
	int num = 0;

#if BITS_PER_LONG == 64
	if ((word & 0xffffffff) == 0) {
		num += 32;
		word >>= 32;
	}
#endif
	if ((word & 0xffff) == 0) {
		num += 16;
		word >>= 16;
	}
	if ((word & 0xff) == 0) {
		num += 8;
		word >>= 8;
	}
	if ((word & 0xf) == 0) {
		num += 4;
		word >>= 4;
	}
	if ((word & 0x3) == 0) {
		num += 2;
		word >>= 2;
	}
	if ((word & 0x1) == 0)
		num += 1;
	return num;
}

程式碼邏輯相同，不過他沒有定義 word 為 0 時的特例。

---

測驗 3 : 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 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;
}

consumer_del 函式要從串鏈 *foo 中刪除 *fc 節點，使用 indirect pointer 找到該節點後移除節點，並最後回傳執行是否成功。

使用 foo_consumer 的好處就是透過將功能抽離，達到模組化，可提升程式的重複利用性、可維護性。

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

---

測驗 4: Coroutine

以下嘗試用 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

setjmp 與 longjmp 函數可以讓程式往回跳到函數呼叫堆疊中的某個函數中，就像是一種跨函數的 goto。
根據文件：

/*
 * The functions described on this page are used for performing
 * "nonlocal gotos": transferring execution from one function to a
 * predetermined location in another function.  The setjmp()
 * function dynamically establishes the target to which control will
 * later be transferred, and longjmp() performs the transfer of
 * execution.
 */

/*
 * setjmp() function saves various information about the calling
 * environment (typically, the stack pointer, the instruction
 * pointer, possibly the values of other registers and the signal
 * mask) in the buffer env for later use by longjmp().  In this
 * case, setjmp() returns 0.
 */
int setjmp(jmp_buf env);

/*
 * longjmp() function uses the information saved in env to
 * transfer control back to the point where setjmp() was called and
 * to restore ("rewind") the stack to its state at the time of the
 * setjmp() call.  In addition, and depending on the implementation
 * (see NOTES), the values of some other registers and the process
 * signal mask may be restored to their state at the time of the
 * setjmp() call.
 */
noreturn void longjmp(jmp_buf env, int val);

在我們達成跨函式 goto 的前提，我們使用 jmp_buf 來記錄此刻在這個函式執行的資訊。setjmp 紀錄此刻的 jmp_buf ，並提供跳躍點。我們透過 setjmp 的回傳值來確認目前是在做紀錄（return 0），還是我們從其他函式跳躍回來到目前指令（return non-zero）。

用 longjmp 來執行跳躍，引數 env 指出我們將跳躍的 env 指令位置？val 是設定我們跳躍到該 setjmp 位置時的函式回傳值。

在 coroutine 的實作中，我們需要頻繁在任務函式間跳躍，如何管理跳躍資訊 jmp_buf 是一大問題。本次實作我們利用雙向佇列 tasklist 來紀錄並管理我們跳躍的排程。task_add 函式將 jmp_buf 安插在佇列的末尾，供未來排程排序。task_switch與 task_join 將從佇列選擇首節點進行指令跳躍，也同時刪除節點取消追蹤。

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

static LIST_HEAD(tasklist);

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_join similar to task_switch, but to be the form of multitask-threads-join
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);
        list_del(&t->list);
        memcpy(env, t->env, sizeof(jmp_buf));
        free(t);
        longjmp(env, 1);
    }
}

schedule 規劃 coroutine 的執行，他規劃每個 task 應該要執行幾次、確認 task 是否完成所有任務。
首先 schedule 確認是否所有的任務都被指派任務次數了，如果尚未指派完就會進到 while 迴圈內，提供一個小於 5 的正整數 n
執行 tasks[i++](&n); 的函式。printf("Never reached\n"); 這一條不會被執行，因為每個 task 在執行完時會跳躍到 setjmp(sched);。
在確認任務都被指派任務次數後，每次跳躍到setjmp(sched);後，會直接略過 while 迴圈進到 task_join(&tasklist); 檢查任務是否執行完畢。

static void (**tasks)(void *);
static int ntasks;
static jmp_buf sched;

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

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

最後來理解一下 task 在做的事情：task 初始化後，設立跳躍點 setjmp(env)，將 env 加入 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);
        longjmp(sched, 1);
    }

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

區域變數追蹤

詳見實驗：jmp.c 、jmp_v1.c

我們將任務改為三個，並把執行中的 i 顯示出來確認變數的變化狀況：

void task0(void *arg)
{
    ...
    for (int i = 0; i < n; i++) {
        if (setjmp(env) == 0) {
            task_add(&tasklist, env);
            task_switch(&tasklist);
        }
        printf("Task 0: resume %d\n", i);
    }
    ...
}

Task 0: n = 3
Task 1: n = 4
Task 2: n = 3
Task 0: resume 0
Task 1: resume 1
Task 2: resume 2
Task 2: complete
Task 0: resume 22075
Task 0: complete
Task 1: resume 22075
Task 1: complete

我發現區域變數 i 在不同函式運行間竟然會互相影響！以本次執行結果觀察：任務切換過程中變數 i 受到任務迴圈的運算影響而累加，並且在Task 2 完成程式後，變數 i 存值變成未定義的存值，task_switch 回到 Task 0,1 時，發現大於區域變數 static n 進而跳出迴圈。

從 gdb 追蹤區域變數 i，發現三個函式對 i 的地址是相同的：

Breakpoint 4, task0 (arg=0x555555558010 <tasklist>) at jmp.c:90
90              printf("Task 0: resume %d\n", i);
(gdb) p i
$7 = 0
(gdb) p &i
$8 = (int *) 0x7fffffffdaec

Task 0: resume 0

Breakpoint 5, task1 (arg=0x555555558010 <tasklist>) at jmp.c:116
116             printf("Task 1: resume %d\n", i);
(gdb) p i
$9 = 1
(gdb) p &i
$10 = (int *) 0x7fffffffdaec

Task 1: resume 1

Breakpoint 6, task2 (arg=0x555555558010 <tasklist>) at jmp.c:142
142             printf("Task 2: resume %d\n", i);
(gdb) p i
$11 = 2
(gdb) p &i
$12 = (int *) 0x7fffffffdaec

Task 2: resume 2
Task 2: complete

Breakpoint 4, task0 (arg=0x555555558010 <tasklist>) at jmp.c:90
90              printf("Task 0: resume %d\n", i);
(gdb) p i
$13 = 21845
(gdb) p &i
$14 = (int *) 0x7fffffffdaec

Task 0: resume 21845
Task 0: complete

Breakpoint 5, task1 (arg=0x555555558010 <tasklist>) at jmp.c:116
116             printf("Task 1: resume %d\n", i);
(gdb) p i
$15 = 21845
(gdb) p &i
$16 = (int *) 0x7fffffffdaec

從 IBM 文件中可以看到這相關的警告：

• The values of register variables are unpredictable.
• Nonvolatile auto variables that are changed between calls to the setjmp and longjmp functions are also unpredictable.

為何會有這樣的問題？從 setjmp(3) — Linux manual page 裡有說明：

The compiler may optimize variables into registers, and longjmp() may restore the values of other registers in addition to the stack pointer and program counter. Consequently, the values of automatic variables are unspecified after a call to longjmp() if they meet all the following criteria:

• they are local to the function that made the corresponding setjmp() call;
• their values are changed between the calls to setjmp() and longjmp(); and
• they are not declared as volatile.

當我把變數 i 設定為 vollatile int i，仍然沒有解決上述問題。

如果我們把變數 i 改為 static，執行結果如下：

void task0(void *arg)
{
    static int n, i = 0;
    ...
    for (; i < n; i++) {
        if (setjmp(env) == 0) {
            task_add(&tasklist, env);
            task_switch(&tasklist);
        }
        printf("Task 0: resume %d\n", i);
    }
    ...
}

Task 0: n = 2
Task 1: n = 4
Task 2: n = 3
Task 0: resume 0
Task 1: resume 0
Task 2: resume 0
Task 0: resume 1
Task 0: complete
Task 1: resume 1
Task 2: resume 1
Task 1: resume 2
Task 2: resume 2
Task 2: complete
Task 1: resume 3
Task 1: complete

Breakpoint 1, task0 (arg=0x5555555596b0) at jmp_v1.c:90
90              printf("Task 0: resume %d\n", i);
(gdb) p i
$1 = 0
(gdb) p &i
$2 = (int *) 0x555555558130 <i>

Breakpoint 2, task1 (arg=0x5555555596b0) at jmp_v1.c:116
116             printf("Task 1: resume %d\n", i);
(gdb) p i 
$3 = 0
(gdb) p &i
$4 = (int *) 0x555555558138 <i>

Breakpoint 3, task2 (arg=0x5555555596b0) at jmp_v1.c:142
142             printf("Task 2: resume %d\n", i);
(gdb) p i
$5 = 0
(gdb) p &i
$6 = (int *) 0x555555558140 <i>

任務間運行次數獨立，我想這才是我們預期看到的結果。

---

測驗 5: ACCESS_ONCE

當一段程式被指派的變數只有被指派卻未被使用時，比如在一個迴圈中使用指派 lock owner時，這有可能被編譯器優化。使用ACCESS_ONCE 來防止該程式被優化而無法達到預期的 happens before。

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

如何防止執行的 x 被優化？這裡透過巨集假設讓 x 被指派一個新的變數，讓並設定 volatile 告訴編譯器這個變數不須優化。

這裡我們遇到一個問題是：不確定此變數的型態與大小為何，如果被指派的大小不一時，可能導致 overflow。我們透過 union 的特性來讓將要被指派的 __u.__c 能夠和 __u.__val 的配置空間一樣大：

union:
其中所有成員都共用相同的記憶體位置。 這項定義表示，在任何指定的時間， union 都只能在其成員清單中包含一個以上的物件。 這也表示無論有多少成員 union ，一律會使用足夠的記憶體來儲存最大的成員。

最後我們執行我們要做的事：我們根據其大小，轉型並指派固定大小空間的型別，並使用 volatile 達到目的。

DECL0 : char[1] __c

Why the “volatile” type class should not be used

許多程式撰寫者在撰寫 Read-Write 的多執行緒任務時，為了維持預期的 Happens Before 的結果，會透過 volatile 的型態使編譯器不做優化，得以保持程式的 atomic 不可分割。然而這樣卻是個不好的習慣。

首先如果在正確的方式使用 spinlock 下，應該能夠排除程式執行的正確性，反而使用 volatile 將會使速度被拖慢。

另一個可能導致系統優化的情境是 busy-waiting 的索要變數資訊情況：此文章建議我們可以使用 cpu_relax(); 的指令，可以降低 CPU 功耗，也讓編譯器不會判斷這是浪費的指派行動，而將指令搬出去的狀況。那也不需要使用 volatile。