Try   HackMD

2020q1 第 8 週測驗題

tags: linux2020

目的: 檢驗學員對 C 語言流程控制前置處理器的認知

作答表單


測驗 1

Go 語言沒有內建例外處理機制,而是運用 defer 關鍵字,後者可指定某個函式延遲執行,直到函式即將返回之際才會執行之前 defer 指定的敘述。

依據 Cambridge Dictionarydefer 的解釋為:

to delay something until a later time; to postpone

例句:

You can order the furniture now and defer payment until Sep.

例如:

package main import "fmt" func deferredFunc() { fmt.Println("deferredFunc") } func main() { defer deferredFunc() fmt.Println("Hello World") }

上方的程式碼中,deferredFunc() 之前加上 defer (第 7 行),因此會在 main() 函式回傳前執行,結果就是先顯示 "Hello World",再顯示 "deferredFunc"。

若有多個函式被 defer,那麼在函式回傳前,會依 defer 的相反順序執行,也就是 LIFO。例如:

package main import "fmt" func deferredFunc1() { fmt.Println("deferredFunc1") } func deferredFunc2() { fmt.Println("deferredFunc2") } func main() { defer deferredFunc1() defer deferredFunc2() fmt.Println("Hello World") }

由於先對 deferredFunc1defer (第 11 行),才對 deferredFunc2defer (第 12 行),因此執行結果會是 "Hello World", "deferredFunc2", "deferredFunc1" 這樣的順序。

A Tour of Go 提供線上執行環境,可見 Defer 頁面。

接著我們嘗試用 C 語言搭配 GNU extension (所以程式碼只能透過 gcc 或 clang 來編譯) 來實作 Go 語言的 defer 特徵。測試程式碼: (demo.c):

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include "defer.h"

void test1(void) {
    DEFER_INIT;
    char *x = malloc(32);
    Defer(free(x));

    Defer({
        printf("x   : %s\n", x);
        x[5] = '\0';
        ;
        printf("now : %s\n", x);
    });

    strcpy(x, "Hello world");
    Return;
}

int test2(void) {
    DEFER_INIT;
    puts("0");

    Defer(puts("3"));
    Defer(puts("2"));
    puts("1");
    Return puts("4");
}

int main(void) {
    test1();
    test2();
    return 0;
}

預期執行輸出:

x   : Hello world
now : Hello
0
1
2
3
4

對應的 defer.h 實作如下:

#ifndef DEFER_H #define DEFER_H #ifndef __MAX_DEFERRED_STATEMENTS #define __MAX_DEFERRED_STATEMENTS 32 #endif #define DEFER_INIT \ unsigned char __deferral_num = 0; \ void *__defer_return_label = 0, \ *__deferrals[__MAX_DEFERRED_STATEMENTS] = {0} #define Defer(block) __Defer(block, __COUNTER__) #define Return __Return(__COUNTER__) #define __defer_concat(a, b) a##b #define __Defer(block, n) \ do { \ __deferrals[__deferral_num++] = &&__defer_concat(__defer_init, n); \ if (AAA) { \ __defer_concat(__defer_init, n) : block; \ if (__deferral_num) \ goto *__deferrals[BBB]; \ goto *__defer_return_label; \ } \ } while (0) #define __Return(n) \ if (__deferral_num) { \ __defer_return_label = &&__defer_fini_##n; \ goto *__deferrals[CCC]; \ } \ __defer_fini_##n : return #endif

針對 GNU extensions 說明:

  1. 第 20 行的 &&Labels as Values,搭配第 25 行 goto *__defer_return_label 一類的敘述使用,第 32 行同理
  2. 第 13 行和第 14 行的 __COUNTER__ 是 gcc/clang 在編譯過程中給予的遞增流水號,可搭配 label 名稱運用,詳見 Common Predefined Macros

作答區

AAA = ?

  • (a) 0
  • (b) 1
  • (c) deferral_num
  • (d) deferral_num++
  • (e) ++deferral_num
  • (f) deferral_num--
  • (g) --deferral_num

BBB = ?

  • (a) 0
  • (b) 1
  • (c) deferral_num
  • (d) deferral_num++
  • (e) ++deferral_num
  • (f) deferral_num--
  • (g) --deferral_num

CCC = ?

  • (a) 0
  • (b) 1
  • (c) deferral_num
  • (d) deferral_num++
  • (e) ++deferral_num
  • (f) deferral_num--
  • (g) --deferral_num

延伸問題:

  1. 透過 gcc -E 來解析前置處理器產生的程式碼,從而解釋上述 defer.h 運作機制,若發現程式碼的缺失,也一併修正;
  2. 在 Linux 核心原始程式碼 (版本號碼 >= 5.5) 找出上述 GNU extension 的應用案例並說明。提示: 在 kernel/bpf/core.c 可見 computed goto 的精美應用

測驗 2

研讀 A (Bare-Bones) User-Level Thread Library 一文後,下方程式碼嘗試給予更進階的 user-level thread (ULT) 實作: (檔名: task_sched.c)

#define _GNU_SOURCE
#include <signal.h>
#include <stdbool.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <ucontext.h>
#include <unistd.h>

#include "list.h"

static int preempt_count = 0;
static void preempt_disable(void) { DDD; }
static void preempt_enable(void) { EEE; }

static void local_irq_save(sigset_t *sig_set) {
    sigset_t block_set;
    sigfillset(&block_set);
    HHH(&block_set, SIGINT);
    sigprocmask(SIG_BLOCK, &block_set, sig_set);
}

static void local_irq_restore(sigset_t *sig_set) {
    sigprocmask(SIG_SETMASK, sig_set, NULL);
}

#define task_printf(...)     \
    ({                       \
        preempt_disable();   \
        printf(__VA_ARGS__); \
        preempt_enable();    \
    })

typedef void(task_callback_t)(void *arg);

struct task_struct {
    struct list_head list;
    ucontext_t context;
    void *stack;
    task_callback_t *callback;
    void *arg;
    bool reap_self;
};

static struct task_struct *task_current, task_main;
static LIST_HEAD(task_reap);

static void task_init(void) {
    INIT_LIST_HEAD(&task_main.list);
    task_current = &task_main;
}

static struct task_struct *task_alloc(task_callback_t *func, void *arg) {
    struct task_struct *task = calloc(1, sizeof(*task));
    task->stack = calloc(1, 1 << 20);
    task->callback = func;
    task->arg = arg;
    return task;
}

static void task_destroy(struct task_struct *task) {
    list_del(&task->list);
    free(task->stack);
    free(task);
}

static void task_switch_to(struct task_struct *from, struct task_struct *to) {
    task_current = to;
    swapcontext(&from->context, &to->context);
}

static void schedule(void) {
    sigset_t set;
    local_irq_save(&set);
    struct task_struct *next_task =
        list_first_entry(&task_current->list, struct task_struct, list);
    if (next_task) {
        if (task_current->reap_self) list_move(&task_current->list, &task_reap);
        task_switch_to(task_current, next_task);
    }

    struct task_struct *task, *tmp;
    list_for_each_entry_safe (task, tmp, &task_reap, list) /* clean reaps */
        task_destroy(task);
    local_irq_restore(&set);
}

union task_ptr {
    void *p;
    int i[2];
};

static void local_irq_restore_trampoline(struct task_struct *task) {
    JJJ(&task->context.uc_sigmask, SIGALRM);
    local_irq_restore(&task->context.uc_sigmask);
}

__attribute__((noreturn)) static void task_trampoline(int i0, int i1) {
    union task_ptr ptr = {.i = {i0, i1}};
    struct task_struct *task = ptr.p;

    /* We switch to trampoline with blocked timer.  That is safe.
     * So the first thing that we have to do is to unblock timer signal.
     * Paired with task_add().
     */
    local_irq_restore_trampoline(task);
    task->callback(task->arg);
    task->reap_self = true;
    schedule();
    __builtin_unreachable(); /* shall not reach here */
}

static void task_add(task_callback_t *func, void *param) {
    struct task_struct *task = task_alloc(func, param);
    if (getcontext(&task->context) == -1) abort();
    task->context.uc_stack.ss_sp = task->stack;
    task->context.uc_stack.ss_size = 1 << 20;
    task->context.uc_stack.ss_flags = 0;
    task->context.uc_link = NULL;

    union task_ptr ptr = {.p = task};
    makecontext(&task->context, (void (*)(void)) task_trampoline, 2, ptr.i[0],
                ptr.i[1]);
    /* When we switch to it for the first time, timer signal must be blocked.
     * Paired with task_trampoline().
     */
    sigaddset(&task->context.uc_sigmask, SIGALRM);

    preempt_disable();
    FFF(&task->list, &task_main.list);
    preempt_enable();
}

static void timer_handler(int signo, siginfo_t *info, ucontext_t *ctx) {
    if (preempt_count) /* once preemption is disabled */
        return;

    /* We can schedule directly from sighandler because Linux kernel cares only
     * about proper sigreturn frame in the stack.
     */
    schedule();
}

static void timer_init(void) {
    struct sigaction sa = {.sa_handler = (void (*)(int)) timer_handler,
                           .sa_flags = SA_SIGINFO};
    sigfillset(&sa.sa_mask);
    sigaction(SIGALRM, &sa, NULL);
}

static void timer_create(unsigned int usecs) { ualarm(usecs, usecs); }
static void timer_cancel(void) { ualarm(0, 0); }

static void timer_wait(void) {
    sigset_t mask;
    sigprocmask(0, NULL, &mask);
    GGG(&mask, SIGALRM);
    sigsuspend(&mask);
}

static int cmp_u32(const void *a, const void *b, void *arg) {
    uint32_t x = *(uint32_t *) a, y = *(uint32_t *) b;
    uint32_t diff = x ^ y;
    if (!diff) return 0; /* *a == *b */
    diff = diff | (diff >> 1);
    diff |= diff >> 2;
    diff |= diff >> 4;
    diff |= diff >> 8;
    diff |= diff >> 16;
    diff KKK diff >> 1;                       
    return x & diff ? 1 : -1; /* if *a > *b, then 1; if *a < *b, then -1; */
}

static inline uint32_t random_shuffle(uint32_t x) {
    /* by Chris Wellons, see: <https://nullprogram.com/blog/2018/07/31/> */
    x ^= x >> 16;
    x *= 0x7feb352dUL;
    x ^= x >> 15;
    x *= 0x846ca68bUL;
    x ^= x >> 16;
    return x;
}

#define ARR_SIZE 1000000
static void sort(void *arg) {
    char *name = arg;

    preempt_disable();
    uint32_t *arr = malloc(ARR_SIZE * sizeof(uint32_t));
    preempt_enable();

    task_printf("[%s] %s: begin\n", name, __func__);

    uint32_t r = getpid();
    for (int i = 0; i < ARR_SIZE; i++) arr[i] = (r = random_shuffle(r));

    task_printf("[%s] %s: start sorting\n", name, __func__);

    qsort_r(arr, ARR_SIZE, sizeof(uint32_t), cmp_u32, name);

    for (int i = 0; i < ARR_SIZE - 1; i++)
        if (arr[i] > arr[i + 1]) {
            task_printf("[%s] %s: failed: a[%d]=%u, a[%d]=%u\n", name, __func__,
                        i, arr[i], i + 1, arr[i + 1]);
            abort();
        }

    task_printf("[%s] %s: end\n", name, __func__);

    preempt_disable();
    free(arr);
    preempt_enable();
}

int main() {
    timer_init();
    task_init();

    task_add(sort, "1"), task_add(sort, "2"), task_add(sort, "3");

    preempt_disable();
    timer_create(10000); /* 10 ms */

    while (!list_empty(&task_main.list) || !list_empty(&task_reap)) {
        preempt_enable();
        timer_wait();
        preempt_disable();
    }
    preempt_enable();
    timer_cancel();

    return 0;
}

其中 list.h 取自 linux-list/include/list.h。該 ULT 原理是透過 SIGALRM signal 來模擬作業系統的 timer 中斷,設定的時間間隔為 10 ms,於是每 10 ms 觸發模擬的 timer 中斷,帶動 ULT 排程器,實作 round-robin 排程策略。留意到 trampoline 的使用:

Trampolines (sometimes referred to as indirect jump vectors) are memory locations holding addresses pointing to interrupt service routines, I/O routines, etc. Execution jumps into the trampoline and then immediately jumps out, or bounces, hence the term trampoline.

出處: Trampoline mirror may push laser pulse through fabric of the Universe

預期程式執行輸出:

[1] sort: begin
[1] sort: start sorting
[2] sort: begin
[2] sort: start sorting
[3] sort: begin
[3] sort: start sorting
[2] sort: end
[3] sort: end
[1] sort: end

注意後 3 行的順序可能是 \(3 \to 2 \to 1\)\(2 \to 3 \to 1\)

請補完程式碼。
參考資訊:

作答區

DDD = ?

  • (a) preempt_count = 0
  • (b) preempt_count = 1
  • (c) preempt_count--
  • (d) preempt_count++

EEE = ?

  • (a) preempt_count = 0
  • (b) preempt_count = 1
  • (c) preempt_count--
  • (d) preempt_count++

FFF = ?

  • (a) list_add
  • (b) list_add_tail

GGG = ?

  • (a) sigaddset
  • (b) sigdelset
  • (c) sigfillset

HHH = ?

  • (a) sigaddset
  • (b) sigdelset
  • (c) sigfillset

JJJ = ?

  • (a) sigaddset
  • (b) sigdelset
  • (c) sigfillset

KKK = ?

  • (a) =
  • (b) &=
  • (c) |=
  • (d) ^=

延伸問題:

  1. 解釋上述程式碼運作原理,以及對應到 Linux 核心原始碼的若干機制,如 preempt_disable, preempt_enable, local_irq_save, local_irq_restore 等等
  2. 探討上述程式碼的 signal 使用機制,指出其正確性或效率疑慮,並著手改進