2020q1 Homework4 (kcalc)

contributed by < kylekylehaha >

作業內容

tags: `linux2020`

測試環境

$ cat /etc/os-release 
NAME="Ubuntu"
VERSION="18.04.4 LTS (Bionic Beaver)"
$ cat /proc/version
Linux version 5.3.0-42-generic (buildd@lcy01-amd64-019) 
(gcc version 7.4.0 (Ubuntu 7.4.0-1ubuntu1~18.04.1))

作業要求

找出至少 2 個 Linux 核心中使用定點數的案例，搭配程式碼解說
MathEx 如何解析給定字串，從而分離出變數和對應數學表示法呢？
在 MathEx 中，nop 一類使用者自訂的函數如何實作呢？
是否發現 MathEx 對於負數的除法結果不正確、乘法和加法的 overflow 沒有做處理，且缺乏對減法的 underflow 處理機制呢？你預計如何克服？
將 fibdrv 作業的成果透過 livepatch，整合進 kcalc。
觀察原始程式碼的 expression.[ch] 裡頭 vec 相關的程式碼，將 quiz4 使用到的技巧予以應用，提出對空間效率更好的實作

Linux 核心中使用定點數的案例

Linux kernel load average

計算 load average 時，採用指數平滑法以及定點數。這邊我們主要討論定點數的運用。

這邊簡單介紹定點數:

定點數的加法和減法可直接進行
定點數的乘法需要將乘法運算後的結果除以
$b^{n}$ (b: 進制 ; n: 小數的位數)
定點數的除法需要將除法運算後的結果乘以
$b^{n}$ (b: 進制 ; n: 小數的位數)

e.g.
浮點數 0.5 換成 3 位精準度的定點數:

0.5 \times 10^{3} = 500

當兩浮點數 0.5 + 0.5 = 1.0 時，轉成定點數 500 + 500 = 1000 ，轉成浮點數仍為 1。同理，減法也是。
當兩浮點數 0.5 * 0.5 = 0.25，轉成定點數 500 * 500 = 250000，轉成浮點數為 250000/1000 = 250，和原本答案 0.25 不同。修正方法為定點數: (500 * 500) / 1000 = 250，轉成浮點數為0.25
除法和乘法一樣需要做修正，然而是將運算結果乘以1000。浮點數0.5/0.02 = 25，定點數500/20 = 25，轉成浮點數為0.025，和正確答案25有所不同，故須乘以1000來修正。

在探討code之前，需要先了解 linux load average 如何計算。

l o a d_{t} = l o a d_{t - 1} * α + n * (1 - α)

其中，

α

對應於 1min, 5min, 15min 分别是0.920044415, 0.983471454, 0.994459848。

由於該公式不能直接在 linux kernel 用浮點數計算，因此採用定點數來運算。這裡我們用 1min 來解釋，將小數位數定為 2 進制的的 11 位。

$α$ : 0.920044415 轉成定點數
$0.920044415 * 2^{11}$ = 1884
將 n 和常數 1 也轉成定點數
$n * 2^{11}$ ,
$1 * 2^{11}$
將
$n * (1 - α)$ 轉成
$((n * 2^{11}) * (1 * 2^{11} - 1884)) / 2^{11}$

最後可以將原本公式改寫成

l o a d_{t} * 2^{11} = (l o a d_{t - 1} * 1884 + (n * 2^{11}) * ((1 * 2^{11}) - 1884)) / 2^{11}

終於，來進入我們的程式碼。
在include/linux/sched.h 中，先來看一些marco

#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) */

FSHIFT: 定點運算中11位表示小數的精度。
FIXED_1: 定點數的1
LOAD_FREQ: linux 每 5 秒計算一次。
EXP_1: 1min 的
$α$
EXP_5: 5min 的
$α$
EXP_15: 15min 的
$α$

接著，在kernel/sched/proc.c，我們來看calc_global_load，當中呼叫calc_load即為上述公式的運算。

void calc_global_load(unsigned long ticks)
{
	long active, delta;

	if (time_before(jiffies, calc_load_update + 10))
		return;

	/*
	 * Fold the 'old' idle-delta to include all NO_HZ cpus.
	 */
	delta = calc_load_fold_idle();
	if (delta)
		atomic_long_add(delta, &calc_load_tasks);

	active = atomic_long_read(&calc_load_tasks);
	active = active > 0 ? active * FIXED_1 : 0;

	avenrun[0] = calc_load(avenrun[0], EXP_1, active);
	avenrun[1] = calc_load(avenrun[1], EXP_5, active);
	avenrun[2] = calc_load(avenrun[2], EXP_15, active);

	calc_load_update += LOAD_FREQ;

	/*
	 * In case we idled for multiple LOAD_FREQ intervals, catch up in bulk.
	 */
	calc_global_nohz();
}

/*
 * a1 = a0 * e + a * (1 - e)
 */
static unsigned long
calc_load(unsigned long load, unsigned long exp, unsigned long active)
{
	load *= exp;
	load += active * (FIXED_1 - exp);
	load += 1UL << (FSHIFT - 1);
	return load >> FSHIFT;
}

當 load average 計算出來後，我們必須正確的將結果顯示出來。
在fs/proc/loadavg.c 可以找到一下程式碼。

#define LOAD_INT(x) ((x) >> FSHIFT)
#define LOAD_FRAC(x) LOAD_INT(((x) & (FIXED_1-1)) * 100)

static int loadavg_proc_show(struct seq_file *m, void *v)
{
	unsigned long avnrun[3];

	get_avenrun(avnrun, FIXED_1/200, 0);

	seq_printf(m, "%lu.%02lu %lu.%02lu %lu.%02lu %ld/%d %d\n",
		LOAD_INT(avnrun[0]), LOAD_FRAC(avnrun[0]),
		LOAD_INT(avnrun[1]), LOAD_FRAC(avnrun[1]),
		LOAD_INT(avnrun[2]), LOAD_FRAC(avnrun[2]),
		nr_running(), nr_threads,
		task_active_pid_ns(current)->last_pid);
	return 0;
}

LOAD_INT: 即為將小數去掉，顯示整數部份。
LOAD_FRAC: 因 FIXED_1 =

100000000000_{2}

，FIXED_1 - 1 =

011111111111_{2}

。透過 AND 的方式即可取出小數部份。

接著將其乘以 100 後，再取 LOAD_INT，即為小數前面的兩位數。

time(7)

MathEx 如何解析給定字串，從而分離出變數和對應數學表示法呢？

從 test-simple.c中，可以看到在 main中主要呼叫兩個函式: expr_create & expr_eval。

expr_create: 將字串轉成 expr type。
expr_eval: 則是計算結果，並回傳 float 型態。

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:

在503行，呼叫expr_next_token，去找出token。



for (;;) {
        int n = expr_next_token(s, len, &flags);
...

找出token後，依照不同的類型進入不同的 if else block

expr_calc:

採用遞迴的方式
若為單元運算子，則取出一個即可。e.g. case OP_UNARY_MINUS
若為二元運算子，則須取出兩個做運算。e.g. case OP_DIVIDE

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_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 中，nop 一類使用者自訂的函數如何實作呢？

在 experssion.h中，可以找到 struct expr_func。

name: 函式名稱
f: function pointer

/*
 * Functions
 */
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.h中，我們定義 add，並將自己定義的函式加入 user_funcs[]。之後，user_func 也會一同被丟入 expr_create，去判斷字串中是否含有自定義的函式。

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

在 expression.c 中可以找到 expr_func，用來判斷字串中是否含有自定義的函式。

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 沒有做處理，且缺乏對減法的 underflow 處理機制呢？你預計如何克服？

除法負數處理

在做除法之前，我們先判斷被除數或除數是否為負數，用 sign 來紀錄該運算結果為正或負。因此我們將 n1 及 n2 都變為正數後再去做除法運算後，其結果與正確結果差一個原本的 sign 。故在最後 n3 乘上 sign 做修正。

static int divid(int a, int b)
{
    ...
    int sign = 1;
    ...

    /* check if there is negative number */
    if (n1 < 0) {
        sign = -sign;
        n1 = -n1;
    }
    if (n2 < 0) {
        sign = -sign;
        n2 = -n2;
    }
    ...
    int n3 = (n1 / n2) * sign;
    int frac3 = frac1 - frac2;

    return FP2INT(n3, frac3);
}

加法的 overflow 處理
當計算完 n1 + n2 時，須檢查是否產生 overflow。如果產生 overflow，則一律回傳 -1，並用 printk 印出發生overflow。

static int plus(int a, int b)
{
    ...
    /* check whether it is overflow */
    int n3 = n1 + n2;
    if ((n3 > 0) && (n1 < 0) && (n2 < 0)) {
        printk("Error: overflow\n");
        return FP2INT(-1, 0);
    }
    if ((n3 < 0) && (n1 > 0) && (n2 > 0)) {
        printk("Error: overflow\n");
        return FP2INT(-1, 0);
    }
    return FP2INT(n3,  frac1);
}

乘法的 overflow 處理
乘法的部份，分成 frac 與 num 兩個部份:

frac 判斷方式和加法一樣: 當兩個正數相加變成負數時，即為發生overflow ; 當兩個負數相加變成正數時，即為發生 overflow。

num 判斷方式我們採乘完的結果除乘數，應為被乘數，來判斷是否發生 overflow。

如果發生 overflow，則印出警告訊息，並回傳 -1。

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;

    /* check whether num is overflow */
    if ((n2 != 0) && (n1 != n3 / n2)) {
        printk("Error: overflow\n");
        return FP2INT(-1, 0);
    } 

    /* check whether frac is overflow */
    int frac3 = frac1 + frac2;
    if ((frac3 > 0) && (frac1 < 0) && (frac2 < 0)) {
        printk("Error: overflow\n");
        return FP2INT(-1, 0);
    }
    if ((frac3 < 0) && (frac1 > 0) && (frac2 > 0)) {
        printk("Error: overflow\n");
        return FP2INT(-1 , 0)
    }
    return FP2INT(n3, frac3);
}

減法 underflow 的處理
判斷減法 underflow，分成兩種 case:

當被減數 n1 大於結果 n3，n2 小於零。
當被減數 n1 小於結果 n3，n2 大於零。

static int minus(int a, int b)
{
    ...
    /* check whether it is underflow */
    int n3 = n1 - n2;
    if ((n1 > n3) && (n2 < 0)) {
        printk("Error: overflow\n");
        return FP2INT(-1, 0);
    }
    if ((n1 < n3) && (n2 > 0)) {
        printk("Error: overflow\n");
        return FP2INT(-1, 0);
    }
    return FP2INT(n3, frac1);
}

將 fibdrv 作業的成果透過 livepatch，整合進 kcalc。

根據上面所談到的，若要加入自訂的函數，只須在 user_funcs[] 加入即可。這邊我們加入 user_func_fib 和 user_func_fib_cleanup。

我們在 user_func_fib 中先呼叫 expr_eval(&vec_nth(&args, 0))，來取得變數 n，也就是欲計算的第 n 項 fibonacci number。之後，在傳入計算 fibonacci 的函式 fib_clz。(此函式目前錯誤的，之後要利用 livepatch 進行修補。)

noinline void user_func_fib_cleanup(struct expr_func *f, void *c)
{
    /* suppress compilation warning */
    (void) f;
    (void) c;
}

noinline int fib_clz(int n)
{
    printk("Use fib_clz to calculate fib %d\n", n);
    return 0;
}

noinline int user_func_fib(struct expr_func *f, vec_expr_t args, void *c)
{
    /* test */
    int n = expr_eval(&vec_nth(&args, 0));
    return fib_clz(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}
};

接著來到 livepatch-calc.c 中，在 funcs 內加入欲修改的函式。

.old_name 為欲修改的函式名稱。
.new_func 為用來修補的函式名稱。

因此，我們在這邊利用 livepatch_fib 來修補原本的 fib_clz。

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 = "fib_clz",
        .new_func = livepatch_fib,
    },
    {
        .old_name = "user_func_fib_cleanup",
        .new_func = livepatch_fib_cleanup,
    },
    {},
};

這邊我們利用 fibdrv 中的 clz 指令，以及 fast doubling 來做 fibonacci 的計算。

n 為 expr_eval 的回傳值，其中 MathEx 的格式由左至右分別為:

int(28 bits)
sign(1 bit)
frac(3 bits)

故真實所代表的 number，其公式為:

n u m b e r = (i n t)_{10} * 10^{(f r a c)_{10}}

也就是 script/eval.sh 中 fromfixed 的內容。

int livepatch_fib(int n)
{
    printk("livepatch_fib 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 clz = __builtin_clz(num);
    int digit = 32 - clz;
    num <<= clz;
    int fn = 0, fn1 = 1;
    for (int i = 0; i < digit; i++) {
        int f2n, f2n1;
        f2n1 = fn1 * fn1 + fn * fn;
        f2n = fn * 2 * fn1 - fn * fn;
        fn = f2n;
        fn1 = f2n1;
        if (num & 0x80000000) {
            fn = f2n1;
            fn1 = f2n + f2n1;
        }
        num <<= 1;
    }
    printk("expecedt answer is %d\n", fn);
    return fn << 4;
}

來測試一下，在 scripts/test.sh 中加入 fib(11)。

# pre-defined function                         
test_op 'fib(11)'
# Livepatch
sudo insmod $LIVEPATCH_CALC_MOD
sleep 1
echo "livepatch was applied"
test_op 'fib(11)'

$ ./scripts/test.sh
...
Testing  fib(11) ...
0
livepatch was applied
Testing  fib(11) ...
89
[18690.427898] livepatch_calc: livepatch_fib is now patched
[18690.427904] expected answer is 89
[18690.427906] calc: Result: 1424
[18690.427913] calc: Device successfully closed
[18690.430197] calc: size: 5 result: 1424
[18690.430240] calc: Device successfully closed
Disabling livepatch...
Complete