# 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)
Last changed by  
 
Oscar Shiang
789

Read more

Interesting Facts of Pthread

It may exit immediately if we replace line 24 with return 0.

2/25/2024
OS HW1: Benchmark Your Computer Black Box

學號: F74076124 姓名: 向景亘 系級: 資訊 111 開發環境 OS: Ubuntu 20.04 CPU: Intel(R) Core(TM) i7-7700HQ CPU @ 2.80GHz CPU cores: 4 Memory: 16 GB Programming Language: C11, gcc (Ubuntu 9.3.0-10ubuntu2) 9.3.0

5/7/2023
程式設計(二) Lab 3 講解

lab3 A 部分 題目說明 根據從 file.in 讀入的資料，將最重的 5 隻牛的體重加總起來輸出 使用 fstream 使用前需要在原始碼的上方加上 #include <fstream> 利用 constructor 進行開檔或是利用 member function 的形式開啟檔案 open 函式的參數形式是 open(filename, open_mode)

5/7/2023
Qt Graphics 系列介紹

常見 QGraphics 系列元件介紹與使用示範

5/7/2023
Read more from Oscar Shiang
Published on HackMD