# 2020q1 Homework4 (kcalc)
contributed by < `nickyanggg` >
###### tags: `linux2020`
## [作業要求](https://hackmd.io/@sysprog/linux2020-kcalc?fbclid=IwAR2b_HwsaQ12hqD7ZdEsfX8ghTi9xMYZJGc2FrkRPs5CeP_0tuwbRcsfDCk#-%E4%BD%9C%E6%A5%AD%E8%A6%81%E6%B1%82)
- [自我檢查清單](https://hackmd.io/@sysprog/linux2020-kcalc?fbclid=IwAR2b_HwsaQ12hqD7ZdEsfX8ghTi9xMYZJGc2FrkRPs5CeP_0tuwbRcsfDCk#-%E8%87%AA%E6%88%91%E6%AA%A2%E6%9F%A5%E6%B8%85%E5%96%AE)
- livepatch 整合 fib()
## Linux Kernel 使用 Fixed-point 案例
- 參考 [Linux Kernel Load Average 計算分析](http://brytonlee.github.io/blog/2014/05/07/linux-kernel-load-average-calc/)、[loadavg.h](https://github.com/torvalds/linux/blob/345671ea0f9258f410eb057b9ced9cefbbe5dc78/include/linux/sched/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 分鐘的平滑常數 (以定點數表示)。
```cpp
#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 計算出結果。
```cpp
/*
* 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` ，或是其他也被歸類到運算符號的值，也會有相對應的呼叫處理。
```cpp
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` 為函式的地址。
```cpp
/*
* 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` 中是否有出現自訂義的函式。
- 可看出是依函式名字來比對是否有自訂函式。
```cpp
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 即可。
```cpp
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 問題。
- 用結果 $\div$ 被乘數是否等於乘數來驗證是否發生 overflow。
- 呼叫 `FP2INT` 並重新觀察它的 `FRAC` 是否合理，若不合理則是發生 overflow。
- overflow 皆回傳 -1。
- 這邊假設參數 `a`、`b` 為合理結果。
```cpp
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` 為合理結果。
```cpp
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` 為合理結果。
```cpp
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 實作自訂函式方式一樣。
```cpp
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` 結果，結果如預期一樣。
```shell
$ ./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` 來<s>覆蓋</s> 修補 `myfib`。
:::danger
回頭看 Livepatch 運作機制，不是透過「覆蓋」，用語要精準
:notes: jserv
:::
```cpp
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,
},
{},
};
```
驗證後，結果沒有問題。
```shell
$ ./scripts/test.sh
...
Testing fib(10) ...
0
livepatch was applied
Testing fib(10) ...
55
```
Sign in with Wallet
Connect another wallet