2020 第六週作業

--- 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 的測試版了，其實這些版本早就有了，只是網站更新時間剛好是這份作業我上去翻閱的這幾天，所以感受特別深刻。