H07: kcalc

tags: linux2020

主講人: jserv / 課程討論區: 2020 年系統軟體課程

返回「Linux 核心設計」課程進度表

作業說明直播錄影

預期目標

• 學習數值系統：浮點運算和定點數
• 整合 fibdrv 和 quiz4 開發成果
• 學習 Livepatch 運作機制
• 撰寫可適用於使用者和核心層級的程式
• 自動測試機制

Linux 核心的浮點數運算

Robert Love 在 Linux Kernel Development 一書論及浮點運算:

No (Easy) Use of Floating Point
When using floating-point instructions kernel normally catches a trap and then initiates the transition from integer to floating point mode. Unlike user-space, the kernel does not have the luxury of seamless support for floating point because it cannot easily trap itself. Using a floating point inside the kernel requires manually saving and restoring the floating point registers. Except in the rare cases, no floating-point operations are in the kernel.

• 解說: Use of floating point in the Linux kernel

Rusty Russell 在 Unreliable Guide To Hacking The Linux Kernel 則說:

The FPU context is not saved; even in user context the FPU state probably won't correspond with the current process: you would mess with some user process' FPU state. If you really want to do this, you would have to explicitly save/restore the full FPU state (and avoid context switches). It is generally a bad idea; use fixed point arithmetic first.

Lazy FP state restore

CVE-2018-3665 存在於 Intel Core 系列微處理器中，因為 speculative execution（推測執行）技術中的一些缺陷加上特定作業系統中對 FPU（Floating point unit）進行 context switch 所產生的漏洞，允許一個本地端的程式洩漏其他程序的 FPU 暫存器內容。

Lazy FP state leak 的原理是透過 FPU 的 lazy state switching 機制達成。因為 FPU 和 SIMD 暫存器不一定會在每個任務持續被使用到，因此作業系統排程器可將不需要使用到 FPU 的任務，標註為不可使用 FPU，而不更改裡面的內容。

然而，在現今的亂序執行 CPU 中，lazy state switching 裡會設定的 "FPU not available" 可能沒辦法馬上被偵測到，導致我們在 process B，但仍然可以存取到 process A 的 FPU 暫存器內容。

基於上述原因，儘管我們在 Linux 核心模式中仍可使用浮點運算，但這不僅會拖慢執行速度，還需要手動儲存/取回相關的 FPU 暫存器，因此核心文件不建議在核心中使用到浮點運算。

浮點運算時間差異比較

afcidk 透過開發簡單的 Linux 核心模組，來測試在單純的浮點數運算及整數運算花費的時間差異。

相關的程式碼可見這裡

可見到核心模式中的浮點數運算，時間成本較整數運算高。

數學式計算器

Reverse Polish Notation

• Reverse Polish notation (RPN) 中 operator 會放在所有 operand 後面
• 平常人們慣用 infix notation，用括號 ( ) 表示順序

範例:

• Infix notation
  
  • 運算子標為藍色，數值標為黑色
  • human friendly
• Reverse Polish notation (RPN)
  
  • computer friendly
  • infix notation 轉 postfix notation
    • Shunting-yard algorithm
  • RPN evaluated from left to right
  • 遇到數值 push 進 stack
  • 遇到運算子取出 stack 前兩個運算，再把結果 push 進 stack
  • 最後 stack 中剩下的該數 (在 s[0]) 即為答案
  ​​​​a : s[0] = a
  ​​​​1 : s[1] = 1
  ​​​​2 : s[2] = 2
  ​​​​+ : s[1] = s[1] + s[2]
  ​​​​b : s[2] = b
  ​​​​* : s[1] = s[1] * s[2]
  ​​​​+ : s[0] = s[0] + s[1]
  ​​​​3 : s[1] = 3
  ​​​​- : s[0] = s[0] - s[1]
  

MathEX 是成功大學師生開發的數學表示式求值工具，接受一組數學表達式，輸出這段數學表達式所對應的答案。

Ex 是 "expression" 的簡稱

取得 MathEX 原始程式碼並測試:

$ git clone https://github.com/jserv/MathEx
$ cd MathEx
$ make check

預期可見以下測試輸出:

OK: six=6, seven=7, six*seven == 42.000000
OK: 小熊=6, 維尼=7, 小熊*維尼 == 42.000000
OK: τ=1.618, 3*τ == 4.854000
OK: $(τ, 1.618), 3*τ() == 4.854000
...
Execute build/test-bench...
BENCH                                        5:	9.383917 ns/op (106M op/sec)
BENCH                      5+5+5+5+5+5+5+5+5+5:	137.161016 ns/op (7M op/sec)
BENCH                      5*5*5*5*5*5*5*5*5*5:	127.733946 ns/op (7M op/sec)
BENCH                      5,5,5,5,5,5,5,5,5,5:	102.152109 ns/op (9M op/sec)
BENCH        ((5+5)+(5+5))+((5+5)+(5+5))+(5+5):	126.007080 ns/op (7M op/sec)
...

MathEX 基本的使用方式：

#include "expression.h"

/* 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;
}

static struct expr_func user_funcs[] = {
    {"add", add, 0}, {NULL, NULL, 0},
};

int main() {
    const char *s = "x = 40, add(2, x)";
    struct expr_var_list vars = {0};
    struct expr *e = expr_create(s, strlen(s), &vars, user_funcs);
    if (!e) { printf("Syntax error"); return 1; }

    printf("result: %f\n", expr_eval(e));

    expr_destroy(e, &vars);
    return 0;
}

上面的程式碼為範例，利用 expr_create() 將字串 x = 40, add(2, x) 輸入，再使用 expr_eval() 來產生輸出結果

MathEx API

MathEx 提供 4 個 API：

• struct expr *expr_create(const char *s, size_t len, struct expr_var_list *vars, struct expr_func *funcs)：將輸入的字串數學表達式編譯成 struct expr 型態，並且回傳
• float expr_eval(struct expr *e)：計算 struct expr 的結果並回傳
• void expr_destroy(struct expr *e, struct expr_var_list *vars)：清除記憶體，vars 可為 NULL (不清除 vars 的記憶體)
• struct expr_var *expr_var(struct expr_var_list *vars, const char *s, size_t len)：在給定的變數清單 vars 中回傳對應名稱 s 的變數，如果清單中不存在該變數則會產生一個並回傳

應用情境

這類的數學表達式分析工具可以被應用於工程計算機類的軟體，如：insect 是個支援物理單位的工程計算機，其中程式碼 insect/src/Insect/Parser.purs 就是計算機的數學表達式的解析器

解析 MathEx 程式碼

透過 expression.h 的 macro 以及 struct 可以找到用來表示 expression 的 struct：

#define vec(T)
    struct {
        T *buf;
        int len;
        int cap;
    }

typedef vec(struct expr) vec_expr_t;
struct expr {
    int type;
    union {
        struct { float value; } num;
        struct { float *value; } var;
        struct { vec_expr_t args; } op;
        struct {
            struct expr_func *f;
            vec_expr_t args;
            void *context;
        } func;
    } param;
};

從上面的定義可見在 struct expr 中，param.op.args 裡面其實包裝著 struct expr 的指標，在後續的程式中可發現該指標指向 1 或 2 個 struct expr，因此可推測 struct expr 是個 tree 的結構。

其中 T *buf 是存放此 vector 所要儲存的目標資料的起始位置，len 為這個 vector 的長度，cap（即 "capability" 的意思) 表示此 vector 可容納幾個 vector 項目的空間，故條件

$len\le cap$ 永遠成立。

expression.h 為 vec 相關的資料結構定義了以下的操作 (巨集)

• vec_nth
• vec_peek
• vec_push
• vec_pop
• vec_free
• vec_foreach

以上這些巨集與 Linux 核心的 include/linux/list.h 手段相似，都隱藏背後的實做，讓撰寫程式碼時更為簡潔，更專注在邏輯上。

可見 vec_push 的實做

#define vec_unpack(v) \
    (char **) &(v)->buf, &(v)->len, &(v)->cap, sizeof(*(v)->buf)
    
#define vec_push(v, val) \
    vec_expand(vec_unpack(v)) ? -1 : ((v)->buf[(v)->len++] = (val), 0)

/* Simple expandable vector implementation */
static inline int vec_expand(char **buf, int *length, int *cap, int memsz)
{
    if (*length + 1 > *cap) {
        void *ptr;
        int n = (*cap == 0) ? 1 : *cap << 1;
        ptr = realloc(*buf, n * memsz);
        if (ptr == NULL) {
            return -1; /* allocation failed */
        }
        *buf = (char *) ptr;
        *cap = n;
    }
    return 0;
}

實做 vec_push 要考慮到許多議題，例如記憶體不足、vector 本身資料結構的更新維護。但都透過巨集定義，隱藏實作細節。這邊 vector 的作法，每當空間不夠就 realloc 兩倍的空間，這樣預先分配多的記憶體，可以減少之後每次需要增加記憶體的次數。

接著可透過 expression.c 中的 expr_eval() 中得知如何計算 expression 結果：

float expr_eval(struct expr *e)
{
    float n;
    switch (e->type) {
    case OP_UNARY_MINUS:
        return -(expr_eval(&e->param.op.args.buf[0]));
    case OP_UNARY_LOGICAL_NOT:
        return !(expr_eval(&e->param.op.args.buf[0]));
    case OP_UNARY_BITWISE_NOT:
        return ~(to_int(expr_eval(&e->param.op.args.buf[0])));
    case OP_POWER:
        return powf(expr_eval(&e->param.op.args.buf[0]),
            expr_eval(&e->param.op.args.buf[1]));
    case OP_MULTIPLY:
        return expr_eval(&e->param.op.args.buf[0])
            * expr_eval(&e->param.op.args.buf[1]);
    case OP_DIVIDE:
        return expr_eval(&e->param.op.args.buf[0])
            / expr_eval(&e->param.op.args.buf[1]);
    case OP_REMAINDER:
        return fmodf(expr_eval(&e->param.op.args.buf[0]),
            expr_eval(&e->param.op.args.buf[1]));
    }
    ...
}

從上面可以知道，它透過遞迴呼叫，計算目前節點的左子節點跟右子節點的結果，最後根據自己的 operator 將左子節點跟右子節點的結果作運算

效能分析

利用 test-bench.c 來查看結果：

BENCH                                        5: 5.650043 ns/op (176M op/sec)
BENCH                      5+5+5+5+5+5+5+5+5+5: 39.499998 ns/op (25M op/sec)
BENCH                      5*5*5*5*5*5*5*5*5*5: 38.609982 ns/op (25M op/sec)
BENCH                      5,5,5,5,5,5,5,5,5,5: 42.056084 ns/op (23M op/sec)
BENCH        ((5+5)+(5+5))+((5+5)+(5+5))+(5+5): 34.670115 ns/op (28M op/sec)
BENCH                                      x=5: 3.753185 ns/op (266M op/sec)
BENCH                  x=5,x+x+x+x+x+x+x+x+x+x: 44.126987 ns/op (22M op/sec)
BENCH    x=5,((x+x)+(x+x))+((x+x)+(x+x))+(x+x): 43.509007 ns/op (22M op/sec)
BENCH a=1,b=2,c=3,d=4,e=5,f=6,g=7,h=8,i=9,j=10: 59.928894 ns/op (16M op/sec)
BENCH a=1,a=2,a=3,a=4,a=5,a=6,a=7,a=8,a=9,a=10: 58.668852 ns/op (17M op/sec)

學習浮點運算和定點數操作

• 你所不知道的 C 語言: 浮點數運算
• Fixed-point arithmetic
• fixed point arithmetic for RT-Linux
  • include/rt_fix.h
  • src/rt_fix.c
• Linux 核心的 CFS 排程器就用到 fixed-point
  • linux/include/linux/sched.h
  ​​​​/*
  ​​​​ * Integer metrics need fixed point arithmetic, e.g., sched/fair
  ​​​​ * has a few: load, load_avg, util_avg, freq, and capacity.
  ​​​​ *
  ​​​​ * We define a basic fixed point arithmetic range, and then formalize
  ​​​​ * all these metrics based on that basic range.
  ​​​​ */
  

  • linux/kernel/sched/fair.c
  ​​​​/*
  ​​​​ * The exact cpuload calculated at every tick would be:
  ​​​​ *
  ​​​​ *   load' = (1 - 1/2^i) * load + (1/2^i) * cur_load
  ​​​​ *
  ​​​​ * If a CPU misses updates for n ticks (as it was idle) and update gets
  ​​​​ * called on the n+1-th tick when CPU may be busy, then we have:
  ​​​​ *
  ​​​​ *   load_n   = (1 - 1/2^i)^n * load_0
  ​​​​ *   load_n+1 = (1 - 1/2^i)   * load_n + (1/2^i) * cur_load
  ​​​​ *
  ​​​​ * decay_load_missed() below does efficient calculation of
  ​​​​ *
  ​​​​ *   load' = (1 - 1/2^i)^n * load
  ​​​​ *
  ​​​​ * Because x^(n+m) := x^n * x^m we can decompose any x^n in power-of-2 factors.
  ​​​​ * This allows us to precompute the above in said factors, thereby allowing the
  ​​​​ * reduction of an arbitrary n in O(log_2 n) steps. (See also
  ​​​​ * fixed_power_int())
  ​​​​ *
  ​​​​ * The calculation is approximated on a 128 point scale.
  ​​​​ */
  

• Floating Point Numbers and printk()

kcalc: 將 MathEx 整合進 Linux 核心模組

原本 MathEx 使用單精度浮點數格式 (即 float)，為了將其移植到 Linux 核心，我們將所有會使用到浮點數的程式碼操作都改為 32-bit 整數，並自行規範 fixed-point 用以計算。在現行 kcalc 實作中，LSB 4 bit 作為 exponent，MSB 28 bit 則挪作 mantissa。

取得 kcalc 程式碼並測試

由於驗證 kcalc 運算結果會用到 bc 這個工具程式，需要先確定安裝:

$ sudo apt install bc

取得 kcalc 原始程式碼並編譯:

$ git clone https://github.com/sysprog21/kcalc
$ cd kcalc
$ make

預期在 kcalc 目錄可見到兩個新檔案:

• calc.ko: 將 MathEx 整合進 Linux 核心作為 character device，對使用者層級提供 /dev/calc 裝置檔案;
• livepatch-calc.ko: 運用 Livepatch (後方會解釋) 技術來動態變更 calc 核心模組的行為，藉此變更 MathEx 裡頭使用者自訂函數的實作;

測試方式:

$ sudo insmod calc.ko
$ sudo chmod 0666 /dev/calc

接著就可輸入欲計算數學式:

$ echo -ne "3*5\0" > /dev/calc

執行 $ dmesg 可傾印 Linux 核心訊息，預期會有相關的訊息，例如:

[415096.766537] calc: Initializing the module
[415096.766599] calc: registered correctly with major number 236
[415096.766668] calc: device class registered correctly
[415096.766782] calc: device class created correctly
[415110.111843] calc: Received 4 -> 3*5
[415110.111910] calc: Result: 240

你一定會納悶，為何 3 * 5 的結果竟是 240 呢？因為這是自行定義的 fixed-point 表示法，我們可在 bash 裡頭執行以下操作，透過 kcalc 提供的工具來轉換: (第一個命令僅需要執行一次)

$ source scripts/eval.sh
$ fromfixed 240

預期會得到 15 這個數值，也就是

$3\times 5$ 的運算結果。

如果你不用 bash 做為預設的 shell，可能會遇到無法正確執行 $ source scripts/eval.sh 命令，請自行更換為 bash

kcalc 提供一套內建的自動測試工具，使用方式:

$ make check

預期輸出: (僅列出最後 15 行)

Testing  $(number, 1), $(number, 2+3), number() ...
5
Testing  nop() ...
-.10000000000000000000
livepatch was applied
Testing  nop() ...
0
[417351.062510] calc: Received 6 -> nop()
[417351.062580] livepatch_calc: function nop is now patched
[417351.062641] calc: Result: 0
[417351.062696] calc: Device successfully closed
[417351.063787] calc: size: 2 result: 0
[417351.063861] calc: Device successfully closed
Disabling livepatch...
Complete

注意到上述輸出，nop() 是定義在 kcalc/main.c 的函式，第一次呼叫 nop() 時，得到返回值是 0，但在 livepatch 成功變更 kcalc 行為後，第二次呼叫 nop() 就會看到 function nop is now patched 這則核心訊息，顯然 main.c 裡頭根本沒有這個字串，上述訊息是預先定義在 kcalc/livepatch-calc.c 裡頭，並藉由 livepatch 改變 user_func_nop 和 user_func_nop_cleanup 這兩個函式的實作。

關於 MathEx 支援的語法範例，可參見 kcalc/scripts/test.sh 內容。

核心 API

在給定的 kcalc/main.c 檔案中，和 fibdrv 一樣提供 character device，但註冊用的核心 API 不同 (register_chrdev vs. alloc_chrdev_region)，差異和適用場合為何呢？

int register_chrdev_region(dev_t from, unsigned count, const char *name)

參數:

• from: the first in the desired range of device numbers; must include the major number.
• count: the number of consecutive device numbers required
• name: the name of the device or driver

搭配 MKDEV 這個 macro 使用。
行為：

• 先使用 major number(12 bits) 與 minor number (20 bits) 使用MKDEV取得from 這個參數，即這個裝置驅動程式獨一無二的識別碼;
• 呼叫 register_chrdev_region，若回傳值為 0，即成功;
• 即使上述成功，還要使用 cdev_init() 將把 file operations 註冊到 remapping table 裡;
• 最後 cdev_add， 將裝置驅動程式註冊到 Linux 核心;

int register_chrdev(unsigned int major, const char *name,
                    const struct file_operations *fops);

參數:

• major: major device number or 0 for dynamic allocation
• name: name of this range of devices
• fops: file operations associated with the devices

行為：

• 該函式回傳值就是 major number
• 因此只要 = 0 或 < 0 都是失敗的情況。

int alloc_chrdev_region (dev_t *dev, unsigned baseminor,
                         unsigned count, const char *name);

參數:

• dev: output parameter for first assigned number
• baseminor: first of the requested range of minor numbers
• count: the number of minor numbers required
• name: the name of the associated device or driver

行為：

• 這邊的 dev 這個參數不需要事先指定數值;
• 傳入 baseminor 到函式，核心會開始找可用的 minor number

For instance, baseminor = 10, your minor number could be any number >= 10!

• 此數 major number 都由系統配置
• 回傳值若等於 0，即成功。
• 同樣，後面要做 cdev_init, cdev_add

比較上述 3 個核心 API:

核心 API	Major number	Minor number
register_chrdev	可自動分配也可開發者指定	系統分配
alloc_chrdev_region	系統自動分配	開發者自行指定基底和範圍
register_chrdev_region	開發者指定	系統分配

簡言之，register_chrdev 承包大部分的工作，也可自動分配，不過沒辦法指定 minor number。alloc_chrdev_region 與 register_chrdev_region 作用相似，只分配 major, minor number，剩下的 file operations remapping 跟後續核心的動作仍要由開發者自行處理。register_chrdev_region 可指定 major number。

在 Char Drivers 可看到下面這段描述:

If you dig through much driver code in the 2.6 kernel, you may notice that quite a few char drivers do not use the cdev interface that we have just described. What you are seeing is older code that has not yet been upgraded to the 2.6 interface. Since that code works as it is, this upgrade may not happen for a long time. For completeness, we describe the older char device registration interface, but new code should not use it; this mechanism will likely go away in a future kernel.

大意是說在 Linux 核心 2.6 版以前，只有 register_chrdev 可使用，但核心開發者建議我們用新的 API (即 alloc_chrdev_region)，因為在日後的版本，原本的 register_chrdev 可能會移去。

Livepatch

想像你是個任職於某間企業的系統管理員，公司提供社交網路或網頁搜尋一類的熱門服務，你無可避免會遇到以下的議題:

1. 不易找個停機時間去給 Linux 系統安裝安全修補 (patch)，後者企圖修復 Linux 核心或關鍵服務的系統漏洞。畢竟一旦公司的服務暫停，就意味著喪失客戶或觸發客戶的不信任。此外，公司內部的官僚作風也可能延遲批准停機時間。
2. 你確實負擔不起停機造成的損失，但現行 Linux 核心的資訊安全漏洞卻可能釀造更大的惡意攻擊，或相關的潛在風險。

Linux 核心 4.0 版推出時，就主打 "Linux Kernel Live Patching Technology" 功能，允許使用者在不重啟系統的前提下，完成系統更新之動作，從而實現 zero downtime。需要留意到，livepatch 目的主要是在不停機的前提下, 修復關鍵缺失和安全漏洞，無法對核心進行全面升級。

已知的核心 live patch 技術有:

1. ksplice: 2008 年由 4 位 MIT 學生創立該技術和 Ksplice, Inc. 公司，2011 年，Oracle 公司宣布收購 Ksplice, Inc.，隨後成為 Oracle Linux 的核心更新機制
2. kGraft: 2014 年 SUSE 公司提出
3. kPatch: 2014 年 Red Hat 公司提出
4. KernelCare: 2014 年由 Cloud Linux, Inc. 提出的方案

2014 年，SUSE 和 Red Hat 分別發佈各自的 live patch 技術 —— kGraft 和 kPatch，隔年 Linux 核心 v4.0 整合前兩者技術，可參見 Linux 原始程式碼的 kernel/livepatch 目錄。

概念示意圖:

延伸閱讀:

• 淺談 Live patching technology (2015 年)
• Linux Kernel Live Patching (2018 年)

自我檢查清單

• 找出至少 2 個 Linux 核心中使用定點數的案例，搭配程式碼解說
  • 提示: 參照以下文章:
  • Linux Kernel Load Average 計算分析
    
  • Load average explained
• MathEx 如何解析給定字串，從而分離出變數和對應數學表示法呢？
• 在 MathEx 中，nop 一類使用者自訂的函數如何實作呢？
• 是否發現 MathEx 對於負數的除法結果不正確、乘法和加法的 overflow 沒有做處理，且缺乏對減法的 underflow 處理機制呢？你預計如何克服？

作業要求

• 回答上述「自我檢查清單」的所有問題，需要附上對應的參考資料和必要的程式碼，以第一手材料 (包含自己設計的實驗) 為佳

如果你在 2020 年 3 月 27 日前，已從 GitHub sysprog21/kcalc 進行 fork，請依據 Alternatives to forking into the same account 一文，對舊的 repository 做對應處置，然後重新 fork

• 在 GitHub 上 fork kcalc，目標是將 fibdrv 作業的成果透過 livepatch，整合進 kcalc。過程中應一併完成以下:
  • 觀察原始程式碼的 expression.[ch] 裡頭 vec 相關的程式碼，將 quiz4 使用到的技巧予以應用，提出對空間效率更好的實作;
  • 在 main.c 提供自行定義的 fib() 函式，一開始僅有不完整實作 (可直接回傳 0，一如 nop() 所為)，但在 livepatch 端 (即 livepatch-calc.c) 就該有正確的 Fibonacci 數求值實作
    $\to$ 不用考慮大數運算，但仍要留意有效數值範圍和運算效率;
  • 修正現有 kcalc 內部數值運算的錯誤，並留意到不合法的記憶體操作;
  • 指出原本 fixed-point 實作的限制，觀察 Linux 核心所用的 fixed-point 運算程式碼，提出針對 kcalc 的改進方案
    $\to$ 避免直接用 int 型態描述，可透過 typedef 來定義 binary32_t 一類的衍生型態;
  • 原有的測試程式不會檢驗輸出數值，應予以擴充，得以自動和預先輸入的期望數值進行比對;

繳交方式

編輯 Homework4 作業區共筆，將你的觀察、上述要求的解說、應用場合探討，以及各式效能改善過程，善用 gnuplot 製圖，紀錄於新建立的共筆

截止日期

• Apr 18, 2020 (含) 之前

越早在 GitHub 上有動態、越早接受 code review，評分越高