# 2020q1 Homework4 (kcalc)
contributed by < `Yu-Wei-Chang` >
> [2020q1 作業 kcalc](https://hackmd.io/@sysprog/ByJyk6HrL)
>
## 實驗環境
```shell
$ uname -a
Linux ywc-ThinkPad-X220 5.3.0-46-generic #38~18.04.1-Ubuntu SMP Tue Mar 31 04:17:56 UTC 2020 x86_64 x86_64 x86_64 GNU/Linux
$ gcc --version
gcc (Ubuntu 7.5.0-3ubuntu1~18.04) 7.5.0
```
## MathEx 解析給定字串的原理
* 分析字串並轉成 struct expr 的工作由 `expr_create()` 函式完成。其中 expr_next_token() 負責從給定字串中分析出下一個 token 在字串中的位置。
* token 的類型可能是數字、文字、括號。
* 遇到 '#'、EOL、空格都會整行略過。
* 針對不同類型的 token，還需要搭配 `flags` 來標記目前分析的狀態，以方便對下一個 token 做適當的判斷並處理。
* 接著 `expr_create()` 函式會搭配 `expr_var()`、`expr_string()`、`expr_const()`、`expr_op()` 將字串表示的運算元、運算子放入 `vec_expr_t es` 中。
## 使用者自訂的函數如何實作？
* 自定義函式宣告於 `main.c` 中，每個自定義函式由 `struct expr_func` 來描述。
```cpp
static struct expr_func user_funcs[] = {
{"nop", user_func_nop, user_func_nop_cleanup, 0},
{NULL, NULL, NULL, 0},
};
```
* 在分析數學表示式字串時 (`expr_create()` 函式)，若有分析到字串和自定義函式名稱一致時，就會將 `struct expr_func` 轉成類行為 OP_FUNC 的 struct expr，並且放入 `es` 中。
```cpp
} 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 = kcalloc(1, f->ctxsz, GFP_KERNEL);
if (!p)
goto cleanup; /* allocation failed */
bound_func.param.func.context = p;
}
vec_push(&es, bound_func);
}
```
* 在運算數學表示式時 (`expr_eval()` 函式)，碰到類型為 OP_FUNC 的 struct expr，則會呼叫它的 `struct expr_func`，讓使用者自定義的函式去計算。
```
case OP_FUNC:
return e->param.func.f->f(e->param.func.f, e->param.func.args,
e->param.func.context);
```
## 將 fibdrv 透過 livepatch 整合進 kcalc
* 在 `main.c` 實作自定義的 fib 函式。 (實作內容先不管，後續會實作在 `livepatch-calc.c` 中)
```cpp
noinline void user_func_fib_cleanup(struct expr_func *f, void *c)
{
/* suppress compilation warnings */
(void) f;
(void) c;
}
noinline int user_func_fib(struct expr_func *f, vec_expr_t args, void *c)
{
/* suppress compilation warnings */
(void) args;
(void) c;
if (f->ctxsz == 0)
return -1;
return 0;
}
static struct expr_func user_funcs[] = {
{"nop", user_func_nop, user_func_nop_cleanup, 0},
{"fib", user_func_fib, user_func_fib_cleanup, 1},
{NULL, NULL, NULL, 0},
};
```
* 在 `livepatch-calc.c` 加入要 patch 的 fib 函式。(還未完成，先做個雛型出來。)
```cpp
void livepatch_fib_cleanup(struct expr_func *f, void *c)
{
pr_info("%d %s(): CALLED\n", __LINE__, __FUNCTION__);
/* suppress compilation warnings */
(void) f;
(void) c;
}
int livepatch_fib(struct expr_func *f, vec_expr_t args, void *c)
{
int n = 0;
if (args.len == 0) {
pr_info("%d %s(): Index value of Fibonacci sequenc needed!\n", __LINE__,
__FUNCTION__);
return -1;
}
n = expr_eval(&vec_peek(&args));
pr_info("%d %s(): CALLED, n = %d\n", __LINE__, __FUNCTION__, n);
return 0;
}
/* clang-format off */
static struct klp_func funcs[] = {
...
{
.old_name = "user_func_fib",
.new_func = livepatch_fib,
},
{
.old_name = "user_func_fib_cleanup",
.new_func = livepatch_fib_cleanup,
},
{},
};
```
* 編譯時發現 `livepatch-calc.ko` ==認不得 expression.o 中實作的函式==。
```shell
make -f ./scripts/Makefile.build obj=/home/ywc/training_data/linux_kernel/Week6_homework/kcalc need-modorder=1
{ echo /home/ywc/training_data/linux_kernel/Week6_homework/kcalc/calc.ko; echo /home/ywc/training_data/linux_kernel/Week6_homework/kcalc/livepatch-calc.ko; :; } \
| awk '!x[$0]++' - > /home/ywc/training_data/linux_kernel/Week6_homework/kcalc/modules.order
make -f ./scripts/Makefile.modpost
sed 's/ko$/o/' /home/ywc/training_data/linux_kernel/Week6_homework/kcalc/modules.order | scripts/mod/modpost -a -i ./Module.symvers -I /home/ywc/training_data/linux_kernel/Week6_homework/kcalc/Module.symvers -o /home/ywc/training_data/linux_kernel/Week6_homework/kcalc/Module.symvers -s -T -
ERROR: "expr_eval" [/home/ywc/training_data/linux_kernel/Week6_homework/kcalc/livepatch-calc.ko] undefined!
scripts/Makefile.modpost:92: recipe for target '__modpost' failed
```
* 參照 [modules.rst](https://github.com/torvalds/linux/blob/master/Documentation/kbuild/modules.rst) 的說明，將 `expression.o` 加入到 module `livepatch-calc.ko` 的來源中，==但編譯時會警告 `livepatch-calc.ko` 沒有 license，也無法 insert 進到系統中==。
```shell
Makefile:
obj-m += livepatch-calc.o
livepatch-calc-y := expression.o
Build warning:
LD [M] /home/ywc/training_data/linux_kernel/Week6_homework/kcalc/livepatch-calc.o
Building modules, stage 2.
MODPOST 2 modules
WARNING: modpost: missing MODULE_LICENSE() in /home/ywc/training_data/linux_kernel/Week6_homework/kcalc/livepatch-calc.o
see include/linux/module.h for more information
```
* 先把會動用到 `expresssion.o` 實作的內容先放在 `main.c` 中，只 patch 費氏數列的運算函式就好 (livepatch_kfib()) 。
```cpp
main.c
noinline int kfib(int n)
{
pr_info("%d %s(): Unpatch function called!, n [%d]\n", __LINE__,
__FUNCTION__, n);
return 0;
}
void user_func_fib_cleanup(struct expr_func *f, void *c)
{
/* suppress compilation warnings */
(void) f;
(void) c;
}
int user_func_fib(struct expr_func *f, vec_expr_t args, void *c)
{
int n = 0;
if (args.len == 0) {
pr_info("%d %s(): Index value of Fibonacci sequenc needed!\n", __LINE__,
__FUNCTION__);
return -1;
}
n = expr_eval(&vec_peek(&args));
kfib(n);
return 0;
}
---------------------------
livepatch-calc.c
noinline int livepatch_kfib(int n)
{
/* The position of the highest bit of n. */
/* So we need to loop `rounds` times to get the answer. */
int rounds = 0;
int a = 0, b = 1; /* F(0), F(1) */
for (int i = n; i; ++rounds, i >>= 1)
;
for (int i = rounds; i > 0; i--) {
int t1, t2;
/* F(2n) = F(n)[2F(n+1) − F(n)] */
t1 = a * (2 * b - a);
/* F(2n+1) = F(n+1)^2 + F(n)^2 */
t2 = b * b + a * a;
if ((n >> (i - 1)) & 1) {
a = t2; /* Threat F(2n+1) as F(n) next round. */
b = t1 + t2; /* Threat F(2n) + F(2n+1) as F(n+1) next round. */
} else {
a = t1; /* Threat F(2n) as F(n) next round. */
b = t2; /* Threat F(2n+1) as F(n+1) next round. */
}
}
pr_info("%d %s(): n [%d], fib [%d]\n", __LINE__, __FUNCTION__, n, a);
return a;
}
/* clang-format off */
static struct klp_func funcs[] = {
.....
{
.old_name = "kfib",
.new_func = livepatch_kfib,
},
{},
};
```
### 轉換 MathEX 自定義的 Fixed-point 表示法
* `expr_eval()` 函式運算後的數值是以 [MathEX](https://github.com/sysprog21/kcalc/blob/master/README.md) 自定義的 Fixed-point 表示法來表示，在交給 `kfib()` 前要先轉成一般的整數表示法，運算完費氏數列後再轉回去 Fixed-point 表示法。
* 將部份 `expression.c` 中的巨集和函式由 static 改為 extern。 (E.g. `GET_NUM()`、`GET_FRAC()`、`isNan()`、`FP2INT()`..等)
* 詳細轉換過程見 [commit](https://github.com/Yu-Wei-Chang/kcalc/commit/64027018831a032da5a2062576b897cce7a31790)。
### 增加測試內容
* 在 `scripts/test.sh` 增加 `test_fib()` 函式，並且預先定義好費氏數列，然後將經由 `kcalc` 計算的結果與其比對，顯示出結果。
* 目前 `kcalc` 只能計算 F(0) ~ F(40) 範圍內的費氏數列，超過範圍數值會錯誤。
```shell
test_fib() {
local fib_seq=(0 1 1 2 3 5 8 13 21 34 55 89 144
233 377 610 987 1597 2584 4181 6765 10946
17711 28657 46368 75025 121393 196418 317811
514229 832040 1346269 2178309 3524578 5702887
9227465 14930352 24157817 39088169 63245986
102334155 165580141)
for i in ${!fib_seq[*]}
do
echo "Testing fib("$i")..."
echo -ne "fib("$i")\0" > $CALC_DEV
if [ $(fromfixed $(cat $CALC_DEV)) != ${fib_seq[$i]} ]; then
echo "Failed! Fib("$i") should be "${fib_seq[$i]}
fi
done
}
```
## Linux Kernel 中的定點數使用案例
* [linux/drivers/hwmon/ltc4245.c](https://github.com/torvalds/linux/blob/master/drivers/hwmon/ltc4245.c) 是 `ltc4245` 熱插拔控制晶片的驅動程式，它透過 I2C 匯流排和處理器溝通，以 I2C subsystem 的角度上，`ltc4245.c` 屬於是 i2c client 的部份，負責存取 `ltc4245` 晶片上的暫存器。
* 雖然此例和 MathEX 自定義的 fixed-point representation 不太一樣，但概念類似，主要都是避免在核心中做浮點數的運算。程式碼如下，需要除以浮點數 3.5 的時候，改成 `voltage * 10 / 35`，來避免浮點數運算。
```cpp
/* Return the current in the given sense register in milliAmperes */
static unsigned int ltc4245_get_current(struct device *dev, u8 reg)
{
...
/*
* The strange looking conversions that follow are fixed-point
* math, since we cannot do floating point in the kernel.
*
* Step 1: convert sense register to microVolts
* Step 2: convert voltage to milliAmperes
*
* If you play around with the V=IR equation, you come up with
* the following: X uV / Y mOhm == Z mA
*
* With the resistors that are fractions of a milliOhm, we multiply
* the voltage and resistance by 10, to shift the decimal point.
* Now we can use the normal division operator again.
*/
switch (reg) {
case LTC4245_12VSENSE:
voltage = regval * 250; /* voltage in uV */
curr = voltage / 50; /* sense resistor 50 mOhm */
break;
case LTC4245_5VSENSE:
voltage = regval * 125; /* voltage in uV */
curr = (voltage * 10) / 35; /* sense resistor 3.5 mOhm */
break;
case LTC4245_3VSENSE:
voltage = regval * 125; /* voltage in uV */
curr = (voltage * 10) / 25; /* sense resistor 2.5 mOhm */
break;
...
```
###### tags: `Linux核心課程筆記 - Homework`
Sign in with Wallet
Connect another wallet