# 2020q1 Homework4 (kcalc)
contributed by < `StevenChen8759` >
###### tags: `linux2020`
> [作業說明 - kcalc](https://hackmd.io/@sysprog/linux2020-kcalc#-%E9%A0%90%E6%9C%9F%E7%9B%AE%E6%A8%99)
> [作業繳交區](https://hackmd.io/@sysprog/linux2020-homework4)
> [Github](https://github.com/StevenChen8759/kcalc)
> [color=lightgreen]
# :computer: 開發記錄
## :keyboard: 基本運作原理分析
* 核心模組 `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 的功能。
## :keyboard: 實作 LivePatched 費氏數列計算函式
* 首先，我們先在 `main.c` 中仿照 `nop()` 相關函式的宣告，在 `main.c` 中實作使用者函式 `fib()` 的呼叫介面。
```cpp=135
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},
};
```
```cpp=119
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()` 函式，以求得輸入函式的結果。
```cpp=141
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 介面。
```cpp=124
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,
},
{},
};
```
```cpp=87
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 自定義的浮點數型別](https://hackmd.io/@sysprog/linux2020-kcalc#kcalc-%E5%B0%87-MathEx-%E6%95%B4%E5%90%88%E9%80%B2-Linux-%E6%A0%B8%E5%BF%83%E6%A8%A1%E7%B5%84)，在此採用 `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 中定義的函式取代之 (應有更佳的做法)，參考以下的實作：
```cpp=11
#define GET_NUM_LP(n) ((n) >> 4)
```
```cpp=18
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;
}
```
* 修改測試程式並執行測試，輸出結果如下：
```shell
$ 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。
# :bulb: 問題與討論
## :arrow_forward: `MathEx` 中會造成計算錯誤部分的改善
* 在程式測試時，發現 `fib()` 函式輸入空值進行 `vec_pop()` 造成記憶體存取錯誤，原因是未檢查 vector 內的元素數量而使程式存取到非法的記憶體位址。我們將 `livepatch-calc.c` 中 `livepatch_fib()` 函式內實現的元素數量檢查部分移除，並在程式測試時輸入空的參數 `fib()` 函式內，即可重現此錯誤：
```shell
$ 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，如此即可避免錯誤的記憶體存取
>
## :arrow_forward: Linux Kernel 中的定點數使用案例
* 參考[先前的 `kcalc` 作業說明](https://hackmd.io/@sysprog/SyC9V0gUE?type=view#%E9%87%8D%E6%96%B0%E5%AD%B8%E7%BF%92%E6%B5%AE%E9%BB%9E%E9%81%8B%E7%AE%97%E5%92%8C%E5%AE%9A%E9%BB%9E%E6%93%8D%E4%BD%9C)，Linux Kernel 的 CFS (Completely Fair Scheduler) 使用了定點數的技巧。
* 參閱 [`linux/include/linux/sched.h`](https://github.com/torvalds/linux/blob/master/include/linux/sched.h)，可發現 Linux Kernel 中的定點數使用了 10 bits 作為小數，並使用剩餘位元表示整數。
```cpp=311
/*
* 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`](https://github.com/torvalds/linux/blob/master/kernel/sched/fair.c) 中也使用了定點數的技巧，參考以下的說明：
```cpp
/*
* 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.
*/
```
Sign in with Wallet
Connect another wallet