2020q1 Homework4 (kcalc)

contributed by < StevenChen8759 >

tags: linux2020

作業說明 - kcalc
作業繳交區
Github

開發記錄

基本運作原理分析

• 核心模組 calc.ko 在啟動時會向 Kernel 註冊裝置，可在 /dev 資料夾下找到裝置 calc ，透過檔案裝置讀寫的方式實作運算式輸入與結果輸出，可在 main.c 中找到相關操作函式的實作。
• calc.ko 整合了 expression.[ch]，基於 Marco Defined Vector 提供運算式剖析與運算式計算功能，在 main.c 中的 calc() 函式可找到相對應的函式呼叫。
• 在使用者定義的 nop() 函式上採用了 Livepatching 的技巧，在 main.c 中會預設呼叫 user_func_fib() 函式，在 Livepatching 模組插入核心後，將會改成呼叫 livepatch_nop() 函式，如此即可在不卸載 calc.ko 核心模組的情況下，達成抽換 callback 的功能。

實作 LivePatched 費氏數列計算函式

• 首先，我們先在 main.c 中仿照 nop() 相關函式的宣告，在 main.c 中實作使用者函式 fib() 的呼叫介面。

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

noinline void user_func_fib_cleanup(struct expr_func *f, void *c)
{
    (void) f;
    (void) c;
}

noinline int user_func_fib(struct expr_func *f, vec_expr_t args, void *c)
{
    (void) args;
    (void) c;

    pr_info("user_func_fib");

    return 77777;
}

• 在變數 user_funcs 中，包含了使用者定義函式的名稱與 callback 等資訊，在函式 calc() 中會一併將此參數輸入 expression.[ch] 的函式 expr_create() 中，並回傳包含使用者定義函式 fib() 的運算式剖析器。在剖析器產生後，呼叫 expr_eval() 函式，以求得輸入函式的結果。

static void calc(void)
{
    struct expr_var_list vars = {0};
    struct expr *e = expr_create(message, strlen(message), &vars, user_funcs);
    if (!e) {
        pr_alert("Syntax error");
        return;
    }

    result = expr_eval(e);
    pr_info("Result: %d\n", result);
    expr_destroy(e, &vars);
}

• 在 livepatch-calc.c 中，我們同樣仿照 nop() 的 livepatching 的相關函式，宣告 fib() 的 livepatching 介面。

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

void livepatch_fib_cleanup(struct expr_func *f, void *c)
{
    (void) f;
    (void) c;
}

int livepatch_fib(struct expr_func *f, vec_expr_t args, void *c)
{
    (void) args;
    (void) c;

    pr_info("function fib is now patched, address of args: %p\n", &args);

    if (args.len == 0) {
        pr_err("No any parameter input...");
        return -1;
    }

    if (args.buf[0].type != 25) {  // For marco OP_CONST
        pr_err("Input argument for fib() error...");
        return -1;
    }

    struct expr x = vec_pop(&args);
    int ipn = GET_NUM_LP(x.param.num.value),
        cnt = GET_FRAC_LP(x.param.num.value);

    while (cnt--)
        ipn *= 10;

    pr_info("%d, %d, %d, %d\n", x.param.num.value, ipn, cnt,
            FP2INT_LP(ipn, cnt));

    return FP2INT_LP(fibn(ipn), 0);
}

• 在 expression.[ch] 中，數值的表示方式採用了 MathEX 自定義的浮點數型別，在此採用 int 型別儲存，LSB 4 bit 存放 exponent，剩下 28 bit 則存放 mantissa，因此在 Livepatching 端的 fib() 函式會將已轉換的數值還原成整數，再導入 fibdrv 中，基於 Fast Doubling 方法的費氏數列計算函式 fibn() 計算出費氏數後，再轉換成自定義的浮點數型別並回傳之。
• 其中，因為 expression.[ch] 中的函式GET_NUM、GET_FRAC 以及 FP2INT 在 livepatching-calc.ko 編譯時並未連接 expression.o，因此會跳出 Symbol NOT Found 的警告，並在嘗試 insmod 時失敗，在此暫時以我們自行在 Livepatching 中定義的函式取代之 (應有更佳的做法)，參考以下的實作：

#define GET_NUM_LP(n) ((n) >> 4)

int GET_FRAC_LP(int n)
{
    int x = n & 15;
    if (x & 8)
        return -(((~x) & 15) + 1);

    return x;
}

int FP2INT_LP(int n, int d)
{
    /* Tailed zero counting */
    while (n && n % 10 == 0) {
        ++d;
        n /= 10;
    }
    if (d == -1) {
        n *= 10;
        --d;
    }

    return ((n << 4) | (d & 15));
}

/* Fibonacci Number calculating via fast doubling */
int fibn(int n)
{
    int t0 = 1, t1 = 1;  // For F[n], F[n+1]
    int t3 = 1, t4 = 0;  // For F[2n], F[2n+1]

    int i = 1;

    if (n <= 0)
        return 0;
    else if (n > 40)  // Limitation for fixed point number
        return -1;

    while (i < n) {
        if ((i << 1) <= n) {
            t4 = t1 * t1 + t0 * t0;
            t3 = t0 * (2 * t1 - t0);
            t0 = t3;
            t1 = t4;
            i = i << 1;
        } else {
            t0 = t3;
            t3 = t4;
            t4 = t0 + t4;
            i++;
        }
    }
    return t3;
}

• 修改測試程式並執行測試，輸出結果如下：

$ make check FIBN=10
make -C /lib/modules/4.15.0-96-generic/build M=/home/stch/linux2020/kcalc modules

...

scripts/test.sh
filename:       /home/stch/linux2020/kcalc/calc.ko
version:        0.1
description:    Math expression evaluation
author:         National Cheng Kung University, Taiwan
license:        Dual MIT/GPL
srcversion:     90FFBFE01F8E40CA140EE46
depends:        
retpoline:      Y
name:           calc
vermagic:       4.15.0-96-generic SMP mod_unload 

...

Testing  nop() ...
-.10000000000000000000
Testing  fib() ...
48610
livepatch was applied
Testing  nop() ...
40
[ 6477.032543] calc: Received 6 -> nop()
[ 6477.032558] livepatch_calc: function nop is now patched
[ 6477.032560] calc: Result: 640
[ 6477.032568] calc: Device successfully closed
[ 6477.036158] calc: size: 4 result: 640
[ 6477.036279] calc: Device successfully closed
Testing  fib(10) ...
55
[ 6477.152202] livepatch_calc: function fib is now patched
[ 6477.152206] livepatch_calc: 17, 10, -1, 16
[ 6477.152208] calc: Result: 880
[ 6477.152218] calc: Device successfully closed
[ 6477.155352] calc: size: 4 result: 880
[ 6477.155875] calc: Device successfully closed
Disabling livepatch...
Complete

• 目前因為變數儲存空間的限制，僅能計算 F[0] ~ F[40] 項，超過範圍會回傳 0 or -1。

問題與討論

MathEx 中會造成計算錯誤部分的改善

• 在程式測試時，發現 fib() 函式輸入空值進行 vec_pop() 造成記憶體存取錯誤，原因是未檢查 vector 內的元素數量而使程式存取到非法的記憶體位址。我們將 livepatch-calc.c 中 livepatch_fib() 函式內實現的元素數量檢查部分移除，並在程式測試時輸入空的參數 fib() 函式內，即可重現此錯誤：

$ make check
make -C /lib/modules/4.15.0-96-generic/build M=/home/stch/linux2020/kcalc modules
make[1]: Entering directory '/usr/src/linux-headers-4.15.0-96-generic'
  CC [M]  /home/stch/linux2020/kcalc/livepatch-calc.o
  Building modules, stage 2.
  MODPOST 2 modules
  CC      /home/stch/linux2020/kcalc/livepatch-calc.mod.o
  LD [M]  /home/stch/linux2020/kcalc/livepatch-calc.ko
make[1]: Leaving directory '/usr/src/linux-headers-4.15.0-96-generic'
scripts/test.sh
[sudo] password for stch: 
filename:       /home/stch/linux2020/kcalc/calc.ko
version:        0.1
description:    Math expression evaluation
author:         National Cheng Kung University, Taiwan
license:        Dual MIT/GPL
srcversion:     90FFBFE01F8E40CA140EE46
depends:        
retpoline:      Y
name:           calc
vermagic:       4.15.0-96-generic SMP mod_unload 

...

Testing  nop() ...
-.10000000000000000000
Testing  fib() ...
48610
livepatch was applied
Testing  nop() ...
40
[ 7802.137687] calc: Received 6 -> nop()
[ 7802.137701] livepatch_calc: function nop is now patched
[ 7802.137703] calc: Result: 640
[ 7802.137710] calc: Device successfully closed
[ 7802.140320] calc: size: 4 result: 640
[ 7802.140409] calc: Device successfully closed
Testing  fib() ...
Makefile:40: recipe for target 'check' failed
make: *** [check] Killed

$ dmesg
...

[ 7802.193924] livepatch_calc: function fib is now patched
[ 7802.193955] BUG: unable to handle kernel NULL pointer dereference at 0000000000000000
[ 7802.193973] IP: livepatch_fib+0x20/0x230 [livepatch_calc]
[ 7802.193977] PGD 8000000012b9b067 P4D 8000000012b9b067 PUD d829067 PMD 0 
[ 7802.193986] Oops: 0000 [#1] SMP PTI
... 
[ 7802.195082] RIP: livepatch_fib+0x20/0x230 [livepatch_calc] RSP: ffffac948299fe20
[ 7802.195084] CR2: 0000000000000000
[ 7802.195091] ---[ end trace bf22f4e274b1adf4 ]--

• 因此，我們應仿效呼叫 malloc() 時的記憶體檢查方式，在進行 vec_pop() 時，皆須檢查對應 Vector 的 len 值是否為0，如此即可避免錯誤的記憶體存取

Linux Kernel 中的定點數使用案例

• 參考先前的 kcalc 作業說明，Linux Kernel 的 CFS (Completely Fair Scheduler) 使用了定點數的技巧。
• 參閱 linux/include/linux/sched.h，可發現 Linux Kernel 中的定點數使用了 10 bits 作為小數，並使用剩餘位元表示整數。

/*
 * Integer metrics need fixed point arithmetic, e.g., sched/fair
 * has a few: load, load_avg, util_avg, freq, and capacity.
 *
 * We define a basic fixed point arithmetic range, and then formalize
 * all these metrics based on that basic range.
 */
# define SCHED_FIXEDPOINT_SHIFT		10
# define SCHED_FIXEDPOINT_SCALE		(1L << SCHED_FIXEDPOINT_SHIFT)

/* Increase resolution of cpu_capacity calculations */
# define SCHED_CAPACITY_SHIFT		SCHED_FIXEDPOINT_SHIFT
# define SCHED_CAPACITY_SCALE		(1L << SCHED_CAPACITY_SHIFT)

• 除此之外，linux/kernel/sched/fair.c 中也使用了定點數的技巧，參考以下的說明：

/*
 * The exact cpuload calculated at every tick would be:
 *
 *   load' = (1 - 1/2^i) * load + (1/2^i) * cur_load
 *
 * If a CPU misses updates for n ticks (as it was idle) and update gets
 * called on the n+1-th tick when CPU may be busy, then we have:
 *
 *   load_n   = (1 - 1/2^i)^n * load_0
 *   load_n+1 = (1 - 1/2^i)   * load_n + (1/2^i) * cur_load
 *
 * decay_load_missed() below does efficient calculation of
 *
 *   load' = (1 - 1/2^i)^n * load
 *
 * Because x^(n+m) := x^n * x^m we can decompose any x^n in power-of-2 factors.
 * This allows us to precompute the above in said factors, thereby allowing the
 * reduction of an arbitrary n in O(log_2 n) steps. (See also
 * fixed_power_int())
 *
 * The calculation is approximated on a 128 point scale.
 */