2020q1 Homework4 (kcalc)

contributed by < nickyanggg >

tags: linux2020

作業要求

• 自我檢查清單
• livepatch 整合 fib()

Linux Kernel 使用 Fixed-point 案例

• 參考 Linux Kernel Load Average 計算分析、loadavg.h

Fixed-point

• 小數點為固定，因此稱作定點數。
• 以 10 進制為例，若表示小數點後三位，則數字 8.7 在定點數的表示法為
  $8.7\times {10}^3=8700$
• 定點數之加減法可直接運算。
• 定點數之乘法的結果需除以
  $b^n$ (b 為進制，n 為小數的位數)。
• 定點數之除法的結果需乘以
  $b^n$ (b 為進制，n 為小數的位數)。

計算 load average

• FSHIFT 為定點數的小數位數，這邊為 11。
• FIXED_1 用來將數字轉為定點數，或者是用來處理定點數乘除法的修正。
• EXP_{i} 代表第 i 分鐘的平滑常數 (以定點數表示)。

#define FSHIFT		11		/* nr of bits of precision */
#define FIXED_1        (1<<FSHIFT)	/* 1.0 as fixed-point */
#define LOAD_FREQ	(5*HZ+1)	/* 5 sec intervals */
#define EXP_1		1884		/* 1/exp(5sec/1min) as fixed-point */
#define EXP_5		2014		/* 1/exp(5sec/5min) */
#define EXP_15		2037		/* 1/exp(5sec/15min) */

/*
 * a1 = a0 * e + a * (1 - e)
 */
static inline unsigned long
calc_load(unsigned long load, unsigned long exp, unsigned long active)
{
    unsigned long newload;

    newload = load * exp + active * (FIXED_1 - exp);
    if (active >= load)
        newload += FIXED_1-1;

    return newload / FIXED_1;
}

分析 MathEx

main

• 呼叫 expr_create 並將算式 s 轉成 expression data type (expr)。
• 呼叫 expr_val 來把儲存好的 expression data type 計算出結果。

/*
 * expression.h
 */
struct expr {
    int type;
    union {
        struct { float value; } num;
        struct { float *value; } var;
        struct { vec_expr_t args; } op;
        struct {
            struct expr_func *f;
            vec_expr_t args;
            void *context;
        } func;
    } param;
};

/*
 * test-simple.c
 */
int main()
{
    const char *s = "x = 40, add(2, x)";
    struct expr_var_list vars = { 0 };
    struct expr *e = expr_create(s, strlen(s), &vars, user_funcs);
    if (!e) {
        printf("Syntax error");
        return 1;
    }

    float result = expr_eval(e);
    printf("result: %f\n", result);

    expr_destroy(e, &vars);
    return 0;
}

expr_create

• 呼叫 expr_next_token 來抓取下一個 token 的位置。
• 判斷 token 的類型來決定該進入哪個 if else block，並用對應到的結構儲存。

expr_eval

• 透過遞迴計算出整個結果。
• 若為單元運算子只取出一個數並做變化。
• 若為二元運算子則是取出 &e->param.op.args.buf 中的二數做運算。
• 若為自訂的運算函式如上面的 main ，或是其他也被歸類到運算符號的值，也會有相對應的呼叫處理。

float expr_eval(struct expr *e)
{
    float n;
    switch (e->type) {
    case OP_UNARY_MINUS:
        return -(expr_eval(&e->param.op.args.buf[0]));
    case OP_UNARY_LOGICAL_NOT:
        return !(expr_eval(&e->param.op.args.buf[0]));
    case OP_UNARY_BITWISE_NOT:
        return ~(to_int(expr_eval(&e->param.op.args.buf[0])));
    case OP_POWER:
        return powf(expr_eval(&e->param.op.args.buf[0]),
            expr_eval(&e->param.op.args.buf[1]));
    case OP_MULTIPLY:
        return expr_eval(&e->param.op.args.buf[0])
            * expr_eval(&e->param.op.args.buf[1]);
    case OP_DIVIDE:
        return expr_eval(&e->param.op.args.buf[0])
            / expr_eval(&e->param.op.args.buf[1]);
    
    ...
    
    default:
        return NAN;
    }
}

MathEx 實作自訂函數

• name 為函式名字。
• f 為函式的地址。

/*
 * expression.h
 */
typedef float (*exprfn_t)(struct expr_func *f, vec_expr_t args, void *context);
 
struct expr_func {                         
    const char *name;
    exprfn_t f;
    exprfn_cleanup_t cleanup;
    size_t ctxsz;
};


/*
 * test-simple.c
 */
static float add(struct expr_func *f, vec_expr_t args, void *c)
{
    float a = expr_eval(&vec_nth(&args, 0));
    float b = expr_eval(&vec_nth(&args, 1));
    return a + b;
}

static struct expr_func user_funcs[] = {
    { "add", add, 0 },
    { NULL, NULL, 0 },
};

而在上面的 main 中，除了傳入整個表示式 s 之外，user_funcs 也會一起被丟入 expr_create 中，為了就是在之後呼叫 expr_func 來比對表示式 s 中是否有出現自訂義的函式。

• 可看出是依函式名字來比對是否有自訂函式。

struct expr_func *expr_func(
    struct expr_func *funcs, const char *s, size_t len)
{
    for (struct expr_func *f = funcs; f->name; f++) {
        if (strlen(f->name) == len && strncmp(f->name, s, len) == 0) {
            return f;
        }
    }
    return NULL;
}

處理 MathEx 負數、overflow

除法

• 被除數為負數時結果錯誤，因為在 while 這個 block 並沒有考慮 n1 < 0 的狀況，所以會一直乘以 10 直到 overflow 並且大於 ((1 << 25) - 1) 才跳出迴圈。
• 處理方式為若發現被除數為負數時，被除數和除數皆乘以 -1，如此 n1 再轉換成其他定點數的值才不會出錯。
• 新增 if (n1 < 0) 的 block 即可。

static int divid(int a, int b)
{
    int frac1 = GET_FRAC(a);
    int frac2 = GET_FRAC(b);
    int n1 = GET_NUM(a);
    int n2 = GET_NUM(b);
    if (n1 == 0 && n2 == 0)
        return NAN_INT;
    if (n2 == 0)
        return INF_INT;
    if (n1 < 0) {
        n1 = -n1;
        n2 = -n2;
    }

    while (n1 * 10 < ((1 << 25) - 1)) {
        --frac1;
        n1 *= 10;
    }
    int n3 = n1 / n2;
    int frac3 = frac1 - frac2;
    return FP2INT(n3, frac3);
}

乘法

• 處理 NUM、FRAC overflow 問題。
• 用結果
  $÷$ 被乘數是否等於乘數來驗證是否發生 overflow。
• 呼叫 FP2INT 並重新觀察它的 FRAC 是否合理，若不合理則是發生 overflow。
• overflow 皆回傳 -1。
• 這邊假設參數 a、b 為合理結果。

static int mult(int a, int b)
{
    int frac1 = GET_FRAC(a);
    int frac2 = GET_FRAC(b);
    int n1 = GET_NUM(a);
    int n2 = GET_NUM(b);
    int n3 = n1 * n2; n3);
    if (n2 != 0 && n1 != n3 / n2) {
        printk("Warning: NUM overflow!");
        return FP2INT(-1, 0);
    }

    int c = FP2INT(n3, (frac1 + frac2));
    int frac3 = GET_FRAC(c);
    if (frac1 > 0 && frac2 > 0 && frac3 < 0) {
        printk("Warning: FRAC overflow!");
        return FP2INT(-1, 0);
    }
    if (frac1 < 0 && frac2 < 0 && frac3 > 0) {
        printk("Warning: FRAC overflow!");
        return FP2INT(-1, 0);
    }
    return c;
}

加法

• 和 mult 處理 FRAC overflow 的方式一樣。
• 這邊假設參數 a、b 為合理結果。

static int plus(int a, int b)
{
    int frac1 = GET_FRAC(a);
    int frac2 = GET_FRAC(b);
    int n1 = GET_NUM(a);
    int n2 = GET_NUM(b);

    while (frac1 != frac2) {
        if (frac1 > frac2) {
            --frac1;
            n1 *= 10;
        } else if (frac1 < frac2) {
            --frac2;
            n2 *= 10;
        }
    }

    int n3 = n1 + n2;
    if (n1 > 0 && n2 > 0 && n3 < 0) {
        printk("Warning: NUM overflow!");
        return FP2INT(-1, 0);
    }
    if (n1 < 0 && n2 < 0 && n3 > 0) {
        printk("Warning: FRAC overflow!");
        return FP2INT(-1, 0);
    }
    return FP2INT(n3, frac1);
}

減法

• 當被減數比結果大時，減數卻小於 0，則發生 overflow。
• 當被減數比結果小時，減數卻大於 0，則發生 overflow。
• 這邊假設參數 a、b 為合理結果。

static int minus(int a, int b)
{
    int frac1 = GET_FRAC(a);
    int frac2 = GET_FRAC(b);
    int n1 = GET_NUM(a);
    int n2 = GET_NUM(b);

    while (frac1 != frac2) {
        if (frac1 > frac2) {
            --frac1;
            n1 *= 10;
        } else {
            --frac2;
            n2 *= 10;
        }
    }

    int n3 = n1 - n2;
    if ((n3 < n1) != (n2 > 0)) {
        printk("Warning: NUM overflow!");
        return FP2INT(-1, 0);
    }
    return FP2INT(n3, frac1);
}

Livepatch

main.c

和前面 MathEx 實作自訂函式方式一樣。

noinline int myfib(int n)
{
    printk("myfib in main.c");
    return 0;
}

noinline int user_func_fib(struct expr_func *f, vec_expr_t args, void *c)
{
    int n = expr_eval(&vec_nth(&args, 0));
    return myfib(n);
}

static struct expr_func user_funcs[] = {
    {"nop", user_func_nop, user_func_nop_cleanup, 0},
    {"fib", user_func_fib, user_func_fib_cleanup, 0},
    {NULL, NULL, NULL, 0},
};

修改 test.sh，並觀看 dmesg 結果，結果如預期一樣。

$ ./scripts/test.sh > /dev/null
$ dmesg

...

[282890.857900] calc: Received 7 -> fib(4)
[282890.857902] myfib in main.c
[282890.857902] calc: Result: 0
[282890.857904] calc: Device successfully closed

livepatch-calc.c

• 由於參數 n 為 fixed-point，因此作運算前要先轉換。
• 回傳之前要將結果再轉回 fixed-point，這邊就沒有去處理 overflow 的問題 (只剩 27 bits 可使用，也就是最大只能到
  $2^{27}-1$)。
• 註冊實作出的函式 livepatch_fib 來覆蓋 修補 myfib。

回頭看 Livepatch 運作機制，不是透過「覆蓋」，用語要精準

jserv

int livepatch_fib(int n)
{
    pr_err("function nop is now patched\n");
    int num = n >> 4;
    int frac = n & 15;
    if (frac >= 8) {
        printk("Warning: Invalid number!");
        return -1;
    }
    for (int i = 0; i < frac; i++)
        num *= 10;

    if (num < 0)
        return -1;
    int a = 0, b = 1, t1, t2;
    int i = 31 - __builtin_clz(num);
    for (; i >= 0; i--) {
        t1 = a * (2 * b - a);
        t2 = b * b + a * a;
        a = t1;
        b = t2;
        if ((num >> i) & 1) {
            t1 = a + b;
            a = b;
            b = t1;
        }
    }
    return a << 4;
}

static struct klp_func funcs[] = {
    {
        .old_name = "user_func_nop",
        .new_func = livepatch_nop,
    },
    {
        .old_name = "user_func_nop_cleanup",
        .new_func = livepatch_nop_cleanup,
    },
    {
        .old_name = "myfib",
        .new_func = livepatch_fib,
    },
    {},
};

驗證後，結果沒有問題。

$ ./scripts/test.sh

...

Testing  fib(10) ...
0
livepatch was applied
Testing  fib(10) ...
55