---
title: 2020 第六週作業
tags: _核心設計
date: Aprial 9, 2020
breaks: true
---
# 2020q1 Homework4 (kcalc)
contributed by < [babysuse](https://github.com/babysuse) >
# 大綱
[toc]
# 作業描述
參見 [H07: kcalc](https://hackmd.io/@sysprog/linux2020-kcalc)
# 定點數 (Fixed Point) 在 Linux 核心應用
## Load Average
程式碼取自[核心 v5.6.3 原始碼](https://elixir.bootlin.com/linux/latest/source/include/linux/sched/loadavg.h#L29)
```c=18
#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;
}
```
```c=43
#define LOAD_INT(x) ((x) >> FSHIFT)
#define LOAD_FRAC(x) LOAD_INT(((x) & (FIXED_1-1)) * 100)
```
根據提示引導的[文章](http://brytonlee.github.io/blog/2014/05/07/linux-kernel-load-average-calc/)和[介紹](https://wiki.nix-pro.com/view/Load_average_explained),可以得知第一個應用在於 linux 核心計算 CPU 平均負載。這個實作中的程式碼牽涉到兩個學問
- 首先是所謂指數平滑法 (exponential smoothing method) 來求平均。這是基於加權移動平均法 (Weighted Moving Average),以指數來調整近期資料的權重。
$A_{t} = \alpha A_{t-1} + (1 - \alpha)N_t$
而在 $\alpha$ 的取值是 $e^{-(\frac{f}{T})} = \frac{1}{\exp(\frac{f}{T})}$
- $f$ 是測量時間差,預設是每 5 秒一次,[介紹](https://wiki.nix-pro.com/view/Load_average_explained)中也有提到如果基於現有的精度想要更精確的話也可以取到兩秒
- $T$ 是測量的時長,預設是分別取 1、5、15 分鐘
- 其次就是定點數運算。定點數的核心思想就是以整數運算來取代小數運算。而實作方式就是三個步驟,先進位,進行運算,再退位回來顯示。
- 以十進制來說,3.1415926535 如果精度取五位,就是先乘上 $10^5$ 轉成整數為 314159 做運算,完了之後再除以 $10^5$ 退位回來。
- 在這裡 Linux 核心為了使用左移 `<<` 右移 `>>` 加速運算,以二進制來進位,`FSHIFT` 取 11 位精度,就是乘上 $2^{11}$,也就是 `<< 11`
- 因此 $\alpha$ 就分別是
$\begin{split}
e^{-(\frac{f}{T})} &= e^{-(\frac{5}{1*60})}\ /\ e^{-(\frac{5}{1*60})}\ /\ e^{-(\frac{5}{1*60})}\ \times 2^{11}\\
&\approx 0.9200444\ /\ 0.9834715\ /\ 0.9944598\ \times 2^{11}\\
&\approx 1884\ /\ 2014\ /\ 2037
\end{split}$
也就是 `EXP_1`、`EXP_5`、`EXP_15`
- 最後還有一個問題在於,為了要確保運算完退位的結果是對的,在做乘除時要進行修正
- 好比說 $(1.0_{\times 10^3} \times 1.0_{\times 10^3})_{\div\ 10^3} = 10^3$ (上下標表示定點數的進退位),結果並不是預期的 1,因此每次做完乘法運算時,都要除以 $X^N$ (X 進制取 N 位精度,也就是這裡的 `FIXED_1`) 來修正,如 [37 行](https://elixir.bootlin.com/linux/latest/source/include/linux/sched/loadavg.h#L37)所作
- 同理,每次做完除法運算時,都要乘上 $X^N$ (`FIXED_1`) 來修正
- 最後就是輸出過程,有鑑於核心設計中並沒有支援浮點數運算,所以輸出仍舊是靠整數運算而不是單純靠退位。
- 程式碼取自[核心 v5.6.3 原始碼](https://elixir.bootlin.com/linux/latest/source/kernel/debug/kdb/kdb_main.c#L2542)
```c=2542
kdb_printf("load avg %ld.%02ld %ld.%02ld %ld.%02ld\n",
LOAD_INT(val.loads[0]), LOAD_FRAC(val.loads[0]),
LOAD_INT(val.loads[1]), LOAD_FRAC(val.loads[1]),
LOAD_INT(val.loads[2]), LOAD_FRAC(val.loads[2]));
```
其中 `LOAD_FRAC` 在第一段程式碼中就有,就是分成整數和小數分別輸出。
# MathEx 運作原理
## 解析字串
#### 資料結構
在 header 的宣告和定義中,分為以下幾種
- `expr_string`, `expr_arg`, `expr`
- 用來表示運算子,運算元,常數
- 他們各有一個 list type,`vec_str_t` 和 `vec_arg_t`
- `expr_var`
- 儲存運算元
- 有個 list type,`expr_var_list`
- `expr_func`
- 儲存運算子
- 用 `struct expr_func *expr_func(struct expr_func *funcs, const char *s, size_t len);` 來取得相對的函式
#### Main Work
以下列出相對費解的部份。
- vector `es`, `os`, `as` 分別存放
- 依序分段出來的表達式
- 依序使用到的運算子或是函式呼叫
- 運算子或是函式相對應的參數 (一個參數的 struct 就是對應一個運算子)
- [`int expr_next_token(const char *s, size_t len, int *flags)`](https://github.com/jserv/MathEX/blob/master/expression.c#L300) 有兩個功能
- 切割 token,包括空白、換行、註解 (以 # 開頭) 都各算是一個 token。
- 用 `flags` 來檢查表達式的合法性
- 好比說 `EXPR_TDEFAULT` 就是不允許運算元和逗號作為開頭
- [`struct expr *expr_create(const char *s, size_t len, struct expr_var_list *vars, struct expr_func *funcs)`](https://github.com/jserv/MathEX/blob/master/expression.c#L480)
- 主要工作是將字串轉成 struct expr 存入 vec_expr_t,在交給 [float expr_eval(struct expr *e)](https://github.com/jserv/MathEX/blob/master/expression.c#L198) 用遞迴完成整個表達式的運算
- 在分析表達式的過程中,在表達式插入了一些特殊字元來分析或檢查表達式的合法性,像是 `'$'`,`'{'` 和 `'}'`
- 像是 [574 行](https://github.com/jserv/MathEX/blob/master/expression.c#L574) 和 [589 行](https://github.com/jserv/MathEX/blob/master/expression.c#L589) 這兩個判斷式中處理遇到 `'('` 和 `')'` 的狀況
- 或者像是 [556 行](https://github.com/jserv/MathEX/blob/master/expression.c#L556)將函式呼叫放進 `os` 和 [606 行](https://github.com/jserv/MathEX/blob/master/expression.c#L606)檢查參數
- 而在遇到 `'('` 和 `')'` 也不見得是呼叫函式,[666 行](https://github.com/jserv/MathEX/blob/master/expression.c#L666)就是單純提升優先順序的狀況
- 最後 [684 行](https://github.com/jserv/MathEX/blob/master/expression.c#L684)和 [687 行](https://github.com/jserv/MathEX/blob/master/expression.c#L687) 就是簡單的常數和運算式
## MathEx 使用者自訂的函數實作
從 test-simple.c
```c
static struct expr_func user_funcs[] = {
{ "add", add, 0 },
{ NULL, NULL, 0 },
};
```
和 expression.c
```c
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;
}
```
可以得知自訂函式是用 array of `struct expr_func` 來傳遞再用字串比對來呼叫。
# 修正 MathEx 運算錯誤問題
TBC
# Livepatch
# 後記
核心程式更新和釋出速度之快從這份作業可以見得,4 / 13 第一次擷取核心程式碼時,最新版是 v5.6.3,過兩天 v5.6.4 就釋出了,再過兩天網站就更新到 v5.7 的測試版了,其實這些版本早就有了,只是網站更新時間剛好是這份作業我上去翻閱的這幾天,所以感受特別深刻。