# 2020q1 Homework4 (kcalc)
contributed by < `ambersun1234` >

## 環境

$ uname -a
Linux 4.15.0-74-generic #83~16.04.1-Ubuntu SMP Wed Dec 18 04:56:23 UTC 2019 x86_64 x86_64 x86_64 GNU/Linux
$ gcc --version
gcc (Ubuntu 5.4.0-6ubuntu1~16.04.12) 5.4.0 20160609

## 作業說明
+ [作業說明](https://hackmd.io/@sysprog/linux2020-kcalc#-%E9%A0%90%E6%9C%9F%E7%9B%AE%E6%A8%99)

## 作業要求
### 自我檢查清單
* 找出至少 2 個 Linux 核心中使用定點數的案例，搭配程式碼解說
* 提示: 參照以下文章:
* [Linux Kernel Load Average 計算分析
](http://brytonlee.github.io/blog/2014/05/07/linux-kernel-load-average-calc/)
* [Load average explained](https://wiki.nix-pro.com/view/Load_average_explained)
* `MathEx` 如何解析給定字串，從而分離出變數和對應數學表示法呢？
* 在 `MathEx` 中，`nop` 一類使用者自訂的函數如何實作呢？
* 是否發現 `MathEx` 對於負數的除法結果不正確、乘法和加法的 overflow 沒有做處理，且缺乏對減法的 underflow 處理機制呢？你預計如何克服？

### 作業要求
* 回答上述「自我檢查清單」的所有問題，需要附上對應的參考資料和必要的程式碼，以第一手材料 (包含自己設計的實驗) 為佳
:::warning
:warning: 如果你在 2020 年 3 月 27 日前，已從 GitHub [sysprog21/kcalc](https://github.com/sysprog21/kcalc) 進行 fork，請依據 [Alternatives to forking into the same account](https://github.community/t5/Support-Protips/Alternatives-to-forking-into-the-same-account/ba-p/7428) 一文，對舊的 repository 做對應處置，然後重新 fork
:::
* 在 GitHub 上 fork [kcalc](https://github.com/sysprog21/kcalc)，目標是將 [fibdrv 作業](https://hackmd.io/@sysprog/linux2020-fibdrv)的成果透過 livepatch，整合進 kcalc。過程中應一併完成以下:
* 觀察原始程式碼的 `expression.[ch]` 裡頭 `vec` 相關的程式碼，將 [quiz4](https://hackmd.io/@sysprog/linux2020-quiz4) 使用到的技巧予以應用，提出對空間效率更好的實作;
* 在 `main.c` 提供自行定義的 `fib()` 函式，一開始僅有不完整實作 (可直接回傳 `0`，一如 `nop()` 所為)，但在 livepatch 端 (即 `livepatch-calc.c`) 就該有正確的 Fibonacci 數求值實作 $\to$ 不用考慮大數運算，但仍要留意有效數值範圍和運算效率;
* 修正現有 kcalc 內部數值運算的錯誤，並留意到不合法的記憶體操作;
* 指出原本 fixed-point 實作的限制，觀察 Linux 核心所用的 fixed-point 運算程式碼，提出針對 kcalc 的改進方案 $\to$ 避免直接用 `int` 型態描述，可透過 `typedef` 來定義 [binary32_t](https://en.wikipedia.org/wiki/Single-precision_floating-point_format) 一類的衍生型態;
* 原有的測試程式不會檢驗輸出數值，應予以擴充，得以自動和預先輸入的期望數值進行比對;

## 自我檢查清單
+ 找出至少 2 個 Linux 核心中使用定點數的案例，搭配程式碼解說
+ c.f. Linux Kernel 浮點運算
+ 浮點數計算相當的耗費資源，而且對 FPU 需要手動操作，對於整體的開銷來說是非常大的
+ 且浮點數運算並非那麼的長使用
+ 因此不建議在 kernel 中使用浮點數運算
+ c.f. 定點數，浮點數
+ 舉例來說，`500`是一個定點數，在`3精度`的表示下，浮點數為 `0.5`
+ 精度丟失 :arrow_right: 浮點數`1.5005`轉換為`3精度`定點數的答案為`1500`
+ 四則運算
+ `+, -` :arrow_right: 定點數 2500 + 定點數 2500 = 定點數 5000，轉換為浮點數(3精度)後 0.25 + 0.25 = 0.5
+ `*` :arrow_right: 定點數 2500 * 定點數 2500 = 定點數 625000，轉換為浮點數 0.25 * 0.25 = 0.0625
+ ==需進行修正==, 乘法 :arrow_right: 除以 $進制^{精度}$, 除法 :arrow_right: 乘以 $進制^{精度}$
+ [linux/loadavg.h](https://github.com/torvalds/linux/blob/345671ea0f9258f410eb057b9ced9cefbbe5dc78/include/linux/sched/loadavg.h#L18) 裡面定義了一系列計算系統 load average 的定點數常數，

        #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) */

kernel 計算 load average 的方式是 $S_t = \alpha * X_{t-1} + (1 - \alpha) * S_{t-1}$，最後計算完成後，需將定點數轉換為浮點數

        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` 如何解析給定字串，從而分離出變數和對應數學表示法呢？
+ MathEX 根據輸入的值，會建立 expression。在 [MathEX/expression.c](https://github.com/jserv/MathEX/blob/master/expression.c#L480) 裡面，定義了一系列的操作；
+ 比如說 expression `x = 40, add(2, x)`，MathEX 會建立三個 vector(expression, string, value)，根據輸入的字串分別判斷並存入 vector 中
+ `expr_var`, `expr_fuct` 的方法都是採用判斷 `字串長度` 以及 `名稱是否相等` 為依據
+ 依照這些方法即可分離出變數，表示法以及其他
+ 在 `MathEx` 中，`nop` 一類使用者自訂的函數如何實作呢？
+ 給定的範例程式中，[MathEX/test-simple.c](https://github.com/jserv/MathEX/blob/master/test-simple.c) 中展示了基本的自訂函數操作

    /* Custom function that returns the sum of its two arguments */
    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;
    }

+ 在經由簡單的確認後(長度以及名稱)，在將其的 expression 加入到 vector 中 [MathEX/expression.c](https://github.com/jserv/MathEX/blob/master/expression.c#L666) 並視為一般表示式，也就是在 compile 時期(這裡指的是表示式轉換時期)將自定義函數直接整合。在後續的計算呼叫中，就是直接操作已經處理過後的表示式了

    } 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);
    }

+ 是否發現 `MathEx` 對於負數的除法結果不正確、乘法和加法的 overflow 沒有做處理，且缺乏對減法的 underflow 處理機制呢？你預計如何克服？

# 實做
+ 觀察原始程式碼的 `expression.[ch]` 裡頭 `vec` 相關的程式碼，將 [quiz4](https://hackmd.io/@sysprog/linux2020-quiz4) 使用到的技巧予以應用，提出對空間效率更好的實作;
+ `NEXT_POWER_OF_2`
+ 給定整數 n，求大於 n 且最小的 $2^m$

        #define NEXT_POWER_OF_2(s) \
            (s&(s-1)) == 0         \
                ? s                \
                : (size_t) 1 << (64 - __builtin_clzl(s)) /* next power of 2 */

###### tags: `linux2020`