# 2020q1 Homework4 (kcalc)
contributed by < `OscarShiang` >
###### tags: `linux2020`
## 測試環境
```shell
$ 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 作業](https://hackmd.io/@sysprog/linux2020-fibdrv)的成果透過 livepatch，整合進 kcalc
* [ ] 觀察原始程式碼的 `expression.[ch]` 裡頭 `vec` 相關的程式碼，將 [quiz4](https://hackmd.io/@sysprog/linux2020-quiz4) 使用到的技巧予以應用，提出對空間效率更好的實作
* [ ] 指出原本 fixed-point 實作的限制，觀察 Linux 核心所用的 fixed-point 運算程式碼，提出針對 kcalc 的改進方案
* [ ] 原有的測試程式不會檢驗輸出數值，應予以擴充，得以自動和預先輸入的期望數值進行比對
## Linux 核心使用定點數案例
### 計算 Load Average
在 Linux 的核心中為了計算 load average 的數值，使用到了定點數的概念，首先看到 [`include/linux/sched.h`](https://elixir.bootlin.com/linux/v4.0/source/include/linux/sched.h#L154) 中相關的 macro :
```cpp
...
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](https://en.wikipedia.org/wiki/Exponential_smoothing) 會用到的常數 `EXP_1`, `EXP_5` 與 `EXP_15`
而在實作的部分在 [`kernel/sched/proc.c`](https://elixir.bootlin.com/linux/v4.0/source/kernel/sched/proc.c) 中可以看到在 `calc_global_load` 函式中
```cpp
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` 的函式如下：
```cpp
/*
* 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` 的實作中
```cpp
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` 的定義如下
```cpp
#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. 函式指標
而在測試程式的實作如下：
```cpp
static struct expr_func user_funcs[] = {
{ "add", add, 0 },
{ NULL, NULL, 0 },
};
```
上述實作中，在填入完函式的名稱與指標後，第三個參數 `0` 是為了讓編譯器可以將後面的資料初始化為 0。而最後一個 field data 全部都是 0 的元素是用來標記結尾的。
在 `expr_create` 的分析中，如下列的程式碼：
```cpp
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 的自定義函式。
```cpp
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` 函式進行運算
```cpp
noinline int kfib(int n)
{
return 0;
}
```
在 `livepatch_calc.c` 中新增 `livepatch_fib` 函式作為 `kfib` 的替代函式
```cpp
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` 檢查函式是否被替換：
```shell
$ 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`](https://elixir.bootlin.com/linux/v4.0/source/include/linux/sched.h#L154) 中所使用的定點數，並設計以下結構：
```cpp
typedef union __fixedp {
struct {
uint32_t frac;
uint32_t inte;
};
uint64_t data;
} fixedp;
```
也就是使用 32 bit 記錄 「整數」 部分，以及另外 32 bit 記錄 「小數」 部分。
除了擴充可記錄的數值範圍外，更減少在存取整數部分時的計算步驟：在 [`include/linux/sched.h`](https://elixir.bootlin.com/linux/v4.0/source/include/linux/sched.h#L154) 中所使用的結構在存取整數部分時需要做位移，但在此結構中只需取出 `inte` 的 field member 即可；
而在進行加減運算時，不需要考慮 exponent 不同的議題，直接運算即可。在進行乘除時，則可以利用 `data` 的 field member 來做位移修正。
將字串轉換為 fixed-point 的實作如下：
```cpp
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`
```cpp
const uint64_t INF_INT = 9223372036854775808;
const uint64_t NAN_INT = 1;
```
將 `main.c` 中，為了符合新的 fixed-point 的實作，將 `user_func_fib` 進行修改：
```cpp
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 轉換的程式：
```cpp
#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`：
```shell
#!/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` 檢查結果：
```shell
$ 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](https://en.wikipedia.org/wiki/Exponential_smoothing)
2. [kernel/sched/proc.c](https://elixir.bootlin.com/linux/v4.0/source/kernel/sched/proc.c)
3. [include/linux/sched.h](https://elixir.bootlin.com/linux/v4.0/source/include/linux/sched.h#L154)
4. [IEEE 754 - Wikipedia](https://en.wikipedia.org/wiki/IEEE_754)
Sign in with Wallet
Connect another wallet