2020q1 Homework4 (kcalc)

contributed by < OscarShiang >

tags: linux2020

測試環境

$ cat /etc/os-release 
NAME="Ubuntu"
VERSION="18.04.4 LTS (Bionic Beaver)"
$ cat /proc/version
Linux version 5.3.0-40-generic (buildd@lcy01-amd64-024) 
(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 使用到的技巧予以應用，提出對空間效率更好的實作
• 指出原本 fixed-point 實作的限制，觀察 Linux 核心所用的 fixed-point 運算程式碼，提出針對 kcalc 的改進方案
• 原有的測試程式不會檢驗輸出數值，應予以擴充，得以自動和預先輸入的期望數值進行比對

Linux 核心使用定點數案例

計算 Load Average

在 Linux 的核心中為了計算 load average 的數值，使用到了定點數的概念，首先看到 include/linux/sched.h 中相關的 macro :

...

extern unsigned long avenrun[];		/* Load averages */
extern void get_avenrun(unsigned long *loads, unsigned long offset, int shift);

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

#define CALC_LOAD(load,exp,n) \
	load *= exp; \
	load += n*(FIXED_1-exp); \
	load >>= FSHIFT;
...

可以看到在計算時會使用到的精度 FSHIFT 與在使用 Exponential smoothing 會用到的常數 EXP_1, EXP_5 與 EXP_15

而在實作的部分在 kernel/sched/proc.c 中可以看到在 calc_global_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();
}

為了分別計算 1, 5, 15 秒的 load average，在實作上對 avenrun 三個元素進行運算，利用 calc_load 計算數值

而 calc_load 的函式如下：

/*
 * 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;
}

可以看到數值使用是 unsigned long 來實作，而為了維持定點數計算的正確性，在結束乘法運算後需要將數值向右 shift 才會是計算的結果

當 load average 被算出來之後，接著就是讓其可以正確地顯示出來。
在 fs/proc/loadavg.c 的實作中

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 的定義如下

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

LOAD_INT 的實作就是將小數部分捨棄，就可以直接使用。

而 LOAD_FRAC 的話，首先將 x 與 FIXED_1-1 進行 AND 運算，因為 FIXED_1 = 1 << FSHIFT 也就是

${100000000000}_2$，減 1 後就變成

${011111111111}_2$ 所以透過遮罩的方式就可以將 x 的小數部分取出。

接著將其乘以 100 再使用 LOAD_INT 就可以取出小數部分的前兩位了

time 命令的 real time 計算

在 Linux Programmer's Manual 的 time(7) 有提到

Real time is defined as time measured from some fixed point, either from a standard point in the past (see the description of the Epoch and calendar time below), or from some point (e.g., the start) in the life of a process (elapsed time).

MathEx 解析字串與變數原理

在 test_simple.c 中可以看到，解析字串的函式是 expr_create，該函式中首先利用 expr_next_token 尋找 token 在字串的位置。
expr_next_token 最主要的功能如下：

1. 遇到 # 標注的註解時忽略整行內容
2. 遇到 空白 或是 \n 時向後尋找其他內容

最後將 token 所在的 index 回傳給 n。

回到 expr_create 函式後，依據 token 的類型（數字、運算子、變數等等），分別存入不同的 vec 之中。因為 vec 的 push 與 pop 都是處理 vec 尾端的元素，所以可以知道在 vec 是作為 stack 使用

在遇到 '(' 與 '{' 等等字元時，就會把儲存在 os 與 as 中的運算子與參數進行包裝，利用迴圈的方式重複這樣的過程，讓 result 在傳入 expr_eval 時可以用遞迴的方式將傳入的表示式算出數值。

在分析完所有的字元後，將 es 這個 vec 的元素 pop 到 result 中，並將 result 回傳，結束字串的解析。

如何在 MathEx 中實作自定義函式

在 MathEx/test-simple.c 中有示範使用 user_funcs 陣列包裝函式並在使用 expr_create 時一併傳入。而 struct expr_func 需要的 field data 有二個：

1. 函式名稱
2. 函式指標

而在測試程式的實作如下：

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

上述實作中，在填入完函式的名稱與指標後，第三個參數 0 是為了讓編譯器可以將後面的資料初始化為 0。而最後一個 field data 全部都是 0 的元素是用來標記結尾的。

在 expr_create 的分析中，如下列的程式碼：

struct expr *expr_create(const char *s, size_t len,
    struct expr_var_list *vars, struct expr_func *funcs)
{
    ...
                    } else {
                        struct expr_func *f = expr_func(funcs, str.s, str.n);
                        struct expr bound_func = expr_init();
                        bound_func.type = OP_FUNC;
                        bound_func.param.func.f = f;
                        bound_func.param.func.args = arg.args;
                        if (f->ctxsz > 0) {
                            void *p = calloc(1, f->ctxsz);
                            if (!p) {
                                goto cleanup; /* allocation failed */
                            }
                            bound_func.param.func.context = p;
                        }
                        vec_push(&es, bound_func);
                    }
    ...
}

就會去比對傳入的函式的列表，如果與輸入的字串吻合的話，就會將函式的指標與參數一同 compile 成 bound_func，讓 expr_eval 可以呼叫對應的函式來進行計算。

使用 livepatch 整合 fibdrv

為了讓 livepatch 能夠找到對應的函式進行替換，我在 main.c 中加入 user_func_fib 作為 MathEx 的自定義函式。

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

在使用 user_func_fib 分析完參數後，將參數傳入 kfib 函式進行運算

noinline int kfib(int n)
{
    return 0;
}

在 livepatch_calc.c 中新增 livepatch_fib 函式作為 kfib 的替代函式

int livepatch_fib(int n)
{
    if (unlikely(!n))
        return 0;

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

掛載 livepatch_calc 檢查函式是否被替換：

$ sudo dmesg
...

[25658.424649] calc: Initializing the module
[25658.424652] calc: registered correctly with major number 241
[25658.424665] calc: device class registered correctly
[25658.426054] calc: device class created correctly
[25689.644432] calc: Received 7 -> fib(3)

[25689.644438] calc: Result: 0
[25689.644444] calc: Device successfully closed
[25714.831552] livepatch: enabling patch 'livepatch_calc'
[25714.845684] livepatch: 'livepatch_calc': starting patching transition
[25714.846236] livepatch: 'livepatch_calc': patching complete
[25721.820212] calc: Received 7 -> fib(3)

[25721.820223] calc: Result: 512559680
[25721.820226] calc: Device successfully closed

從 fromfixed 指令檢查計算結果，發現因為 livepatch_fib 未按照 fixed-point 的格式計算而產生錯誤

接著著手修改 livepatch_fib 以符合 fixed-point 的格式

現行的 fixed-point 實作原理

目前的 fixed-point 所採取的作法是與 floating-point 類似的計算方式，就是將 32 bits 寬度的數值拆成三個部分： exponent 用以表示次方， mantissa 用以表示尾數以及 sign 來表示正負號

$$mantissa\times {10}^{exponent}$$

因為在 exponent 的表示方法是以 10 為底數，所以不需要像 IEEE 754 所規範的 32 位元浮點數一樣使用 8 個位元來表示。而在這樣的表示法中可以表示的最大數值為 1342177270000000，最小的數值為 -1342177280000000

但是在數值較大時會產生精度的問題，像是現行的表示法可以表示 1342177270，但卻不能表示 1342177271，因為 1342177271 已經超過 mantissa 所能表示的大小，但卻不到 exponent 可以表示的範圍，就會導致

$1342177270+1=-9$ 的情況產生

更改 fixed-point 結構

參考 include/linux/sched.h 中所使用的定點數，並設計以下結構：

typedef union __fixedp {
    struct {
        uint32_t frac;
        uint32_t inte;
    };
    uint64_t data;
} fixedp;

也就是使用 32 bit 記錄 「整數」 部分，以及另外 32 bit 記錄 「小數」 部分。

除了擴充可記錄的數值範圍外，更減少在存取整數部分時的計算步驟：在 include/linux/sched.h 中所使用的結構在存取整數部分時需要做位移，但在此結構中只需取出 inte 的 field member 即可；

而在進行加減運算時，不需要考慮 exponent 不同的議題，直接運算即可。在進行乘除時，則可以利用 data 的 field member 來做位移修正。

將字串轉換為 fixed-point 的實作如下：

static uint64_t expr_parse_number(const char *s, size_t len)
{
    fixedp num = {0};
    int frac = 0;
    int dot = 0;
    unsigned int digits = 0;
    for (unsigned int i = 0; i < len; i++) {
        if (s[i] == '.' && dot == 0) {
            dot = i + 1;
            continue;
        }
        if (isdigit(s[i])) {
            if (dot)
                frac++;
            else
                digits++;
        } else
            return NAN_INT;
    }

    static int pow10[] = {
        1,      10,      100,      1000,      10000,
        100000, 1000000, 10000000, 100000000, 1000000000,
    };

    if (dot) {
        uint32_t ipt = 0, tmp;
        uint32_t mask = pow10[frac];
        int i = 31;
        sscanf(s, "%u.%u", &tmp, &ipt);
        while (ipt && i) {
            ipt <<= 1;
            if (ipt >= mask) {
                num.frac |= 1 << i;
                ipt %= mask;
            }
            i--;
        }
    }

    if (digits)
        sscanf(s, "%u", &num.inte);

    return (digits > 0 ? num.data : NAN_INT);
}

設計特殊值的表示法

因為在計算時可能會碰到 NaN, INF 等情況發生，所以需要定義這些特殊值的表示方法：

1. INF: 調用 fraction 全為 1 的情況記錄
2. NaN: 最小的數值來表示 NaN

const uint64_t INF_INT = 9223372036854775808;
const uint64_t NAN_INT = 1;

將 main.c 中，為了符合新的 fixed-point 的實作，將 user_func_fib 進行修改：

uint64_t user_func_fib(struct expr_func *f, vec_expr_t args, void *c)
{
    uint64_t n = expr_eval(&vec_nth(&args, 0));
    return kfib(n >> 32) << 32;
}

因為在新的 fixed-point 的定義下，整數部分實際上能運算到的最大範圍還是

$2^{31}-1$，所以在這樣的實作下 fib 實際能正確計算出的最大數值是 fib(75)。

實作 fixed-point 轉換程式

因為更改了 fixed-point 的實作，所以為了能檢驗運算的結果，需要一個新的 fixed-point 轉換的程式：

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

#include "fixed-point.h"

int main(int argc, char *argv[])
{
    if (argc < 2)
        return -1;

    fixedp ipt = {0};
    ipt.data = strtoul(argv[1], NULL, 10);

    if (ipt.data == NAN_INT)
        puts("NAN_INT");
    else if (ipt.data == INF_INT)
        puts("INF_INT");
    else {
        double result = (int) ipt.inte + ((double) ipt.frac / UINT32_MAX);
        printf("%lf\n", result);
    }
    return 0;
}

使用定義在 <stdint.h> 中的 UINT32_MAX 將小數部分轉換為浮點數形式，並印出對應的浮點數數值。

接著修改 scripts/test.sh 的轉換機制，將 fromfixed 改成執行編譯好的 scripts/eval：

#!/usr/bin/env bash

CALC_DEV=/dev/calc
CALC_MOD=calc.ko
LIVEPATCH_CALC_MOD=livepatch-calc.ko

EVAL=scripts/eval

test_op() {
    local expression=$1
    echo "Testing " ${expression} "..."
    echo -ne ${expression}'\0' > $CALC_DEV
    $EVAL $(cat $CALC_DEV)
}
...

執行 make check 檢查結果：

$ make check

...

Testing  x=5, x = x+1 ...
6.000000
Testing  six=6, seven=7, six*seven ...
42.000000
Testing  小熊=6, 維尼=7, 小熊*維尼 ...
42.000000
Testing  τ=1.618, 3*τ ...
4.854000
Testing  $(τ, 1.618), 3*τ() ...
4.854000
Testing  $(zero), zero() ...
0.000000
Testing  $(one, 1), one()+one(1)+one(1, 2, 4) ...
3.000000
Testing  $(number, 1), $(number, 2+3), number() ...
5.000000
Testing  nop() ...
0.000000
livepatch was applied
Testing  nop() ...
0.000000
[99614.133466] calc: Received 6 -> nop()
[99614.133476] livepatch_calc: function nop is now patched
[99614.133477] calc: Result: 0
[99614.133481] calc: Device successfully closed
[99614.139096] calc: size: 2 result: 0
[99614.139134] calc: Device successfully closed
Disabling livepatch...
Complete

從上面的結果可以看到完成 fixed-point 的轉換。

參考資料

1. Exponential smoothing
2. kernel/sched/proc.c
3. include/linux/sched.h
4. IEEE 754 - Wikipedia