2022q1 Homework4 (quiz4)

contributed by < YiChainLin >

測驗題目

實驗的 gcc 編譯器版本

$ gcc --version
gcc (Ubuntu 9.3.0-17ubuntu1~20.04) 9.3.0

測驗 1

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

$log2(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;       
}

• 題目解析:對一個數字取以 2 為底對數，並取到最接近的整數，以 2 為底在二進位的對數運算中可以舉例表示成，以 64₁₀ = 0010 0000₂為例:
  $$lo{g}_2{2}^6=6$$可以發現 64 為二進位的第六位數
• 運作方式透過對半檢查的方式分別進行 16 bits(0xFFFF) 、 8 bits(0xFF)延續下去
• 看到最後 shift = (x > 0x3) << 1; 是對最後 2 bits 去作檢查，因此還需要對最後 1 個 bit 檢查，可延伸成:

shift = (x > 0x1) << 0;

再將結果存下來:

r |= shift;

最後還要檢查最後一個 bit，依照前面的邏輯要 x >>= shift，所以根據 (x > 0x1) << 0; 的敘述為了達到，直接右移一位判斷，再結合 r 存下結果，可將上述兩段整理成

(r | shift | x >> 1) + 1

參考至運算子的優先度: Operator Precedence，可得知 >> 的處理順序先於 |，所以先進行 x >> 1 再進行 r | shift ，最後再將 x 結果存下
因此:

EXP1 = r | shift | x >> 1

---

測驗 2

改寫第 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;
}

• fls 函式也就是要找出從右數來第一個 1 的 bit 位置，運用的方式透過 1 的 bitmask 進行查找，舉例:

  • 15₁₀ = 01111₂， fls(15) = 1
  • 16₁₀ = 10000₂， fls(16) = 5

• 可以觀察到 #define BITS_PER_LONG (sizeof(unsigned long) * BITS_PER_BYTE) 的定義方式，輸入的數字型態為 long ，而 long 在不同的電腦架構中所定義的位元數也不同，可參考不同資料模型，舉例不同 long 型態:

  • LP32、ILP32、LLP64 的 long 為 32 bits
  • LP64、ILP64 的 long 為 64 bits (本題測試環境為 LP64)

• 透過這樣的宣告方式在建立起對應的 bitmask (unsigned long t = ~0UL;, 1111…11₂)，每次檢查的方式也是對半檢查，分別用 32 bits 、 16 bits 、 8 bits 、 4 bits 、 2 bits 、 1 bits 的 bitmask ，檢查的手段就是在 EXP2 中，利用不同長度的 bitmask 把 first set bit 前的 0 bit 消除( x >>= shift; )，所以 EXP2 為 x 數與 bitmask t 比較，透過 & 運算子確認

EXP2 = x & t

• 而 EXP3 可看出要將結果記錄下來，因為是要計算位置，所以每次的檢查所位移的次數為 shift (也就是消除 0 bit 的個數)，因此

EXP3 = o += shift

• 另外 ffs 函式在 gcc built-in 文件中也有相對應的函式

int __builtin_ffs (int x); 
/* Returns one plus the index of the least significant 1-bit of x, or if x is zero, returns zero. */

• 對應到輸入的 x 型態為 long 或 long long

int __builtin_ffsl (long x); 
int __builtin_ffsll (long long x); 

---

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

• 題目分析:將 struct foo *foo 的 linked list 成員移除(remove, 不是刪除 delete)，實作的方式可參考 Linux API 中的 list_del()，將要移除成員的前一個與後一個成員連結一起
• 為了避免暫時指標的操作方式，實作方式參考了你所不知道的 C 語言: linked list 和非連續記憶體，使用指標的指標 (indirect pointer) 技巧，直接對 next 的記憶體位址進行

可參考這張圖:

圖源

• 觀察 for 迴圈的 EXP4 目的為了要走訪到每一個成員，因此在 con 變數在 linked list 之間不斷走訪

EXP4 = con = &(*con)->next

所以 EXP5 要將進行資料成員的移除，也就是改變 linked list 成員的連接目標，也就是目標成員的下一個成員

EXP5 = fc->next

---

測驗 4

以下嘗試用 lab0 提及的 setjmp 和 longjmp，用以實作〈你所不知道的 C 語言: goto 和流程控制篇〉闡述的 coroutine。

• main()
  首先，創建兩個任務分別為 task0 、 task1，以陣列的方式儲存，以 void * 指標指向這兩個任務的函式，在進入 schedule() 進行任務的排程

void * 指標可以轉換成任何其他類型的資料指標，一種間接資料型態儲存的指標

int main(void)
{
    void (*registered_task[])(void *) = {task0, task1};
    tasks = registered_task;
    ntasks = ARRAY_SIZE(registered_task);
    schedule();
    return 0;
}

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 相似，分別使用在 task0/task1 和 schedule 中，目的是為了都要移除由 list_first_entry 所得到的第一個任務，觀察到函式中有 free 敘述，所以 EXP6 和 EXP7 要將任務移除任務列表中，因此:

EXP6 = list_del(&t->list)
EXP7 = list_del(&t->list)

再來看到 task

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

• 觀察到 EXP8 和 EXP9 都是接在加入任務後，加入後在透過 longjmp 返回至 schedule 所設定的 setjmp(sched); 中，在函式之間能有 goto 的效果，所以在新的任務加入後進行 schedule 排程:

EXP8 = longjmp(sched, 1)
EXP9 = longjmp(sched, 1)

• jmp_buf 變數 : 可以看到定義上為 "沒有一定的型態的變數宣告"，這個變數型態是一個陣列儲存環境資訊，也就是一個指標，儲存由 setjmp() longjmp() 中"返回地址"(return address)與"堆疊指標"(stack pointer)

typedef /* unspecified */ jmp_buf;

The jmp_buf type is an array type suitable for storing information to restore a calling environment. The stored information is sufficient to restore execution at the correct block of the program and invocation of that block. The state of floating-point status flags, or open files, or any other data is not stored in an object of type jmp_buf.
來源

• setjmp 與 longjmp 可用於在流程控制中函式之間，相較 goto 只能在同一個函式內部中，程式在執行中，函式呼叫的堆疊結構從高記憶體位址中往低記憶體位址成長，而每個函式的區域變數都會存取在自己的 stack frame 中，而 setjmp 與 longjmp 可用來設定函式在呼叫 stack 的位置

參考文章 、 Call Stack

• 利用 setjmp 在程式中標示一個目標點，在起初設定的時候會返回 0 的值，在設定變數的時候使用 jmp_buf 進行宣告變數，用來儲存程式跳要的資訊

setjmp man page
The 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.

• 再利用 longjmp 進行跳躍，在 longjmp 所返回的值可在跳躍後改變 jmp_buf 變數的值，就可以利用改變的值進行判斷並處裡對應的程序

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

應修正原程式碼的錯誤

jserv

---

• 在 Task0 與 Task1 中迴圈中加入輸出的程式並觀察

    for (int i = 0; i < n; i++) {
        printf("Task 1, before longjmp i = %d\n", i); /* 進入 longjmp 前 */

        if (setjmp(env) == 0) {
            task_add(&tasklist, env);
            task_switch(&tasklist);
        }
        printf("Task 1, after longjmp i = %d\n", i); /* 進入 longjmp 後 */
        printf("Task 1: resume\n");
    }

• 執行程式後會發現產生出下列的結果，在迴圈的區域變數中會產生錯誤的訊息

Task 0: n = 3
Task 1: n = 3
Task 0, before longjmp i = 0
Task 1, before longjmp i = 0
Task 0, after longjmp i = 0
Task 0: resume
Task 0, before longjmp i = 1
Task 1, after longjmp i = 1
Task 1: resume
Task 1, before longjmp i = 2
Task 0, after longjmp i = 2
Task 0: resume
Task 0: complete
Task 1, after longjmp i = 21867
Task 1: resume
Task 1: complete

• 觀察 Task0 與 Task1 中 for 迴圈中 i 值的變化:

  • Task0 Task1 先後進入迴圈中，此時 i 值為 0
  • Task0 先經過一次的 longjmp 經過一次迴圈後 i++ 變為 1(可以看到 resume 訊息出現的時候)
  • 這時看到 Task1 在做第一次的 longjmp 時，這時就發現 i = 1 並不是 0 因為經過了 Task0 所以 i 值發生了改變
  • 再來 Task1 經過一次的 longjmp 因此 i 變成 2
  • 所以在下一次的 Task0 中 i 因為 Task1 的關係變成 2 在經過下一次的 longjmp 後 i 變成 3 就跳出迴圈 Task0 結束
  • 由於 Task0 把 i 更改導致 Task1 在運行的時候產生錯誤的值

• setjmp/longjmp 在使用上，對於 volatile 變數之外，如區域變數在返回流程時都有可能產生不可預期的結果，由上述的例子可看出在區域變數 i 在經過 longjmp 後值產生改變

參考文章 : setjmp/longjmp and local variables
The documentation of setjmp/longjmp says:
"All accessible objects have values as of the time longjmp() was called, except that the values of objects of automatic storage duration which are local to the function containing the invocation of the corresponding setjmp() which do not have volatile-qualified type and which are changed between the setjmp() invocation and longjmp() call are indeterminate."

• 改善方法，將 for 迴圈中的 i 加入 static 靜態變數的修飾字，防止在 longjmp 跳出時改變 i 的值

- for (int i = 0; i < n; i++)
+ static int i = 0
+ for (; i < n; i++)

• 改善後結果顯示的結果就正常運行了

Task 0: n = 3
Task 1: n = 3
Task 0, before longjmp i = 0
Task 1, before longjmp i = 0
Task 0, after longjmp i = 0
Task 0: resume
Task 0, before longjmp i = 1
Task 1, after longjmp i = 0
Task 1: resume
Task 1, before longjmp i = 1
Task 0, after longjmp i = 1
Task 0: resume
Task 0, before longjmp i = 2
Task 1, after longjmp i = 1
Task 1: resume
Task 1, before longjmp i = 2
Task 0, after longjmp i = 2
Task 0: resume
Task 0: complete
Task 1, after longjmp i = 2
Task 1: resume
Task 1: complete

• 編譯器進行最佳化，如: global(全域變數)、volatile、static 三種變數還是維持其最後所指定的值，而 register 變數則始終都會自動回復原來的值，但區域變數會被改變。
• 使用 setjmp 與 longjmp 時，位於記憶體中的變數會維持其最後的值，而位於 CPU 或浮點數 register 中的變數則會回復至原來的值，local 變數原本位於記憶體中，經過了最佳化後，被放置在 register 中，所以產生了不同的結果。

測驗 5

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

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

在 ACCESS_ONCE() and compiler bugs 則提及 Linux 核心捨棄上述 ACCESS_ONCE 巨集，改為 READ_ONCE 巨集。

READ_ONCE 巨集會判斷變數的寬度，針對寬度為 1, 2, 4, 8 位元組的變數，將其轉換為對應的純量 (scalar) 型態並增加 volatile 關鍵字，而對於其他資料寬度的類型，改呼叫 memcpy 來避免編譯器對該變數進行最佳化。

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

• 透過 union 的記憶體對齊的特性，在不確定 x 型態時，可利用只佔 1 byte 的 char 進行宣告，對齊的方式可參考 quiz2 第六題

DECL0 = char __c[1]