# 2020q1 Homework4 (kcalc)
Contributed by < [AdrianHuang](https://github.com/AdrianHuang/bitcpy) >
###### tags: `linux2020`
# 自我檢查清單
## 找出至少 2 個 Linux 核心中使用定點數的案例，搭配程式碼解說
### 1. Linux Kernel Load Average 計算分析
指令 `uptime` 可顯示過去 1/5/15 分鐘的系統平均負載 ("load average: 0.01, 0.06, 0.02")，如下所示:
```
$ uptime
11:40:45 up 49 days, 2:47, 3 users, load average: 0.01, 0.06, 0.02
```
計算公式使用 [Exponential smoothing](https://en.wikipedia.org/wiki/Exponential_smoothing)，或者可以參考此篇詳盡文章 [Linux Kernel Load Average计算分析](http://brytonlee.github.io/blog/2014/05/07/linux-kernel-load-average-calc/)。其公式如下:
S~t~ = α * X~t-1~ + (1 - α) * S~t-1~, where 0 < α < 1
S~t~ : 時間 `t` 的平滑均值。
S~t-1~ : 時間 `t-1` 的平滑均值。
X~t-1~ : 時間 `t-1` 的實際值。
α : 平滑因子 (smoothing factor)。
對應 Linux 核心程式碼如下所示:
`newload = load * exp + active * (FIXED_1 - exp);`
S~t~ = newload
S~t-1~ = load
X~t-1~ = active (當前 'RUNNABLE + TASK_UNINTERRUPTIBLE' Process 總數: 全域變數 `calc_load_tasks`)
α = exp
使用定點數 (Fixed-point):
* LSB 11 bits : mantissa (第18行)
* MSB 53 bits : exponent
因此定點數 `1.0` 為 `(1 << 11)`，也就是 `FIXED_1` (第19行)，這就是為何 (1 - α) -> (FIXED_1 - exp)。
第20行: 每隔 5 秒計算 1/5/15 分鐘的系統平均負載。
第21-23行: 定義 1/5/15 分鐘的 `α` 值。
* 1 分鐘 `α` 值: 1/exp(5sec/1min) = 0.92004441462，其定點數 0.92004441462 * FIXED_1 = 1884
* 5 分鐘 `α` 值: 1/exp(5sec/5min) = 0.98347145382，其定點數 0.98347145382 * FIXED_1 = 2014
* 15 分鐘 `α` 值: 1/exp(5sec/15min) = 0.994459848，其定點數 0.994459848 * FIXED_1 = 2037
第34-35行: 該判斷式成立的話，代表當前 'RUNNABLE + TASK_UNINTERRUPTIBLE' Process 總數大於上次的 load average，則 `newload` 無條件進位。
第37行: 由於在第33行做定點數乘法運算，所以其結果需要還原 (除以 `FIXED_1`)。
```cpp
include/linux/sched/loadavg.h
18 #define FSHIFT 11 /* nr of bits of precision */
19 #define FIXED_1 (1<<FSHIFT) /* 1.0 as fixed-point */
20 #define LOAD_FREQ (5*HZ+1) /* 5 sec intervals */
21 #define EXP_1 1884 /* 1/exp(5sec/1min) as fixed-point */
22 #define EXP_5 2014 /* 1/exp(5sec/5min) */
23 #define EXP_15 2037 /* 1/exp(5sec/15min) */
24
25 /*
26 * a1 = a0 * e + a * (1 - e)
27 */
28 static inline unsigned long
29 calc_load(unsigned long load, unsigned long exp, unsigned long active)
30 {
31 unsigned long newload;
32
33 newload = load * exp + active * (FIXED_1 - exp);
34 if (active >= load)
35 newload += FIXED_1-1;
36
37 return newload / FIXED_1;
38 }
39
40 extern unsigned long calc_load_n(unsigned long load, unsigned long exp,
41 unsigned long active, unsigned int n);
42
43 #define LOAD_INT(x) ((x) >> FSHIFT)
44 #define LOAD_FRAC(x) LOAD_INT(((x) & (FIXED_1-1)) * 100)
```
`calc_global_load()`:
* 第355-256行: 每隔 5 秒 (其實是，5秒 + 10 ticks) 計算 1/5/15 分鐘的系統平均負載 。
* 第362-367行: 計算當下 'RUNNABLE + TASK_UNINTERRUPTIBLE' Process/Task 總數。為何需要加入 `TASK_UNINTERRUPTIBLE` task 呢? Brendan Gregg 這篇文章 [Linux Load Averages: Solving the Mystery](http://www.brendangregg.com/blog/2017-08-08/linux-load-averages.html)，詳盡地解說其來龍去脈，Brendan 一開始想透過 `git log -p kernel/sched/loadavg.c` 歷史紀錄找出作者的 patch 描述。但對應 patch 歷史更久遠，回溯至 0.99.13~0.99.15 (1993年)，如下所示 (節錄自 [Linux Load Averages: Solving the Mystery](http://www.brendangregg.com/blog/2017-08-08/linux-load-averages.html)):
```diff
From: Matthias Urlichs <urlichs@smurf.sub.org>
Subject: Load average broken ?
Date: Fri, 29 Oct 1993 11:37:23 +0200
The kernel only counts "runnable" processes when computing the load average.
I don't like that; the problem is that processes which are swapping or
waiting on "fast", i.e. noninterruptible, I/O, also consume resources.
It seems somewhat nonintuitive that the load average goes down when you
replace your fast swap disk with a slow swap disk...
Anyway, the following patch seems to make the load average much more
consistent WRT the subjective speed of the system. And, most important, the
load is still zero when nobody is doing anything. ;-)
--- kernel/sched.c.orig Fri Oct 29 10:31:11 1993
+++ kernel/sched.c Fri Oct 29 10:32:51 1993
@@ -414,7 +414,9 @@
unsigned long nr = 0;
for(p = &LAST_TASK; p > &FIRST_TASK; --p)
- if (*p && (*p)->state == TASK_RUNNING)
+ if (*p && ((*p)->state == TASK_RUNNING) ||
+ (*p)->state == TASK_UNINTERRUPTIBLE) ||
+ (*p)->state == TASK_SWAPPING))
nr += FIXED_1;
return nr;
}
--
Matthias Urlichs \ XLink-POP N|rnberg | EMail: urlichs@smurf.sub.org
Schleiermacherstra_e 12 \ Unix+Linux+Mac | Phone: ...please use email.
90491 N|rnberg (Germany) \ Consulting+Networking+Programming+etc'ing 42
```
==考慮 System load average，而不是 CPU load average==
作者 `Matthias` 認為 load average 代表以使用者角度觀察系統忙碌程度，也就是 system load average，而不是 CPU load average。`TASK_UNINTERRUPTIBLE` 表示 process 正在等待某特定事件 (例如: Task swapping、Disk I/O等等)，這也需要算在 system load。底下場景說明為何需要考慮 `TASK_UNINTERRUPTIBLE` (節錄自 [Linux Load Averages: Solving the Mystery](http://www.brendangregg.com/blog/2017-08-08/linux-load-averages.html)):
```
A heavily disk-bound system might be extremely sluggish but only have a
TASK_RUNNING average of 0.1, which doesn't help anybody.
```
* 第369-371行: 計算 1/5/15 分鐘的系統平均負載。全域變數 `avenrun` 用定點數格式儲存，所以使用 `printk` 輸出時，需做對應轉換。
* 第373行: 更新下次計算系統平均負載時間，即 `n + 5 秒`。
```cpp
kernel/sched/loadavg.c
...
344 /*
345 * calc_load - update the avenrun load estimates 10 ticks after the
346 * CPUs have updated calc_load_tasks.
347 *
348 * Called from the global timer code.
349 */
350 void calc_global_load(unsigned long ticks)
351 {
352 unsigned long sample_window;
353 long active, delta;
354
355 sample_window = READ_ONCE(calc_load_update);
356 if (time_before(jiffies, sample_window + 10))
357 return;
358
359 /*
360 * Fold the 'old' NO_HZ-delta to include all NO_HZ CPUs.
361 */
362 delta = calc_load_nohz_read();
363 if (delta)
364 atomic_long_add(delta, &calc_load_tasks);
365
366 active = atomic_long_read(&calc_load_tasks);
367 active = active > 0 ? active * FIXED_1 : 0;
368
369 avenrun[0] = calc_load(avenrun[0], EXP_1, active);
370 avenrun[1] = calc_load(avenrun[1], EXP_5, active);
371 avenrun[2] = calc_load(avenrun[2], EXP_15, active);
372
373 WRITE_ONCE(calc_load_update, sample_window + LOAD_FREQ);
374
375 /*
376 * In case we went to NO_HZ for multiple LOAD_FREQ intervals
377 * catch up in bulk.
378 */
379 calc_global_nohz();
380 }
```
`loadavg_proc_show` 輸出 1/5/15 分鐘的系統平均負載:
* `LOAD_INT`: 取得整數部分。
* `LOAD_FRAC`: 取得小數點部分。因為只取小數點兩位，所以此巨集裡可看到乘以 100。
```cpp
fs/proc/loadavg.c
...
13 static int loadavg_proc_show(struct seq_file *m, void *v)
14 {
15 unsigned long avnrun[3];
16
17 get_avenrun(avnrun, FIXED_1/200, 0);
18
19 seq_printf(m, "%lu.%02lu %lu.%02lu %lu.%02lu %ld/%d %d\n",
20 LOAD_INT(avnrun[0]), LOAD_FRAC(avnrun[0]),
21 LOAD_INT(avnrun[1]), LOAD_FRAC(avnrun[1]),
22 LOAD_INT(avnrun[2]), LOAD_FRAC(avnrun[2]),
23 nr_running(), nr_threads,
24 idr_get_cursor(&task_active_pid_ns(current)->idr) - 1);
25 return 0;
26 }
```
==使用 eBPF 測量 Uninterruptible Tasks 與解析系統負載==
底下腳本 (kickoff_tar.sh) 使用 `tar`、`pidstat`、`offcputime.py`等等工具測量 Uninterruptible Tasks 與系統負載，可參考此 [github repo: load-average-measurement](https://github.com/AdrianHuang/load-average-measurement)。
```script
#!/bin/bash
PGM=tar
TAR_SRC=/home/adrian/git-repo/linux
TAR_DEST=/home/adrian/archive/linux-archive.tar
SGV_TGT_FOLDER=/var/www/html/misc/ebpf/tar/v3/
if [ ! -d $SGV_TGT_FOLDER ]; then
mkdir $SGV_TGT_FOLDER
fi
uptime > uptime.log
${PGM} -cf $TAR_DEST $TAR_SRC &
tar_pid=$!
(pidstat -C ${PGM} 60 2>&1 | tee pidstat-${PGM}.log) &
(iostat -x 60 /dev/sda2 2>&1 | tee iostat-${PGM}.log) &
~/git-repo/bcc-master/tools/offcputime.py -K --state 2 -f 60 > ${PGM}.stacks
# Get more uptime data for 5-second interval
for i in {1..4}
do
uptime >> uptime.log && sleep 5
done
# Generate flame graph
awk '{ print $1, $2 / 1000 }' ${PGM}.stacks | /home/adrian/git-repo/FlameGraph/flamegraph.pl --title="Off-CPU Time Flame Graph" --color=io --countname=ms > ${PGM}.svg
mv ${PGM}.svg $SGV_TGT_FOLDER
# kill the running process
kill -9 $tar_pid
killall pidstat iostat
```
執行底下命令後，數據如下:
```shell
# 測試前，先清除 kernel page cache、dentries 與 inodes。
$ sudo sh -c 'echo 3 > /proc/sys/vm/drop_caches'
$ sudo ./kickoff_tar.sh
$ cat pidstat-tar.log
Linux 5.7.0-050700-generic (adrian-ubuntu) 06/09/2020 _x86_64_ (72 CPU)
10:27:18 AM UID PID %usr %system %guest %wait %CPU CPU Command
10:28:18 AM 0 30839 2.83 31.35 0.00 0.02 34.18 63 tar
$ cat iostat-tar.log
Linux 5.7.0-050700-generic (adrian-ubuntu) 06/09/2020 _x86_64_ (72 CPU)
avg-cpu: %user %nice %system %iowait %steal %idle
0.01 0.00 0.01 0.01 0.00 99.98
Device r/s w/s rkB/s wkB/s rrqm/s wrqm/s %rrqm %wrqm r_await w_await aqu-sz rareq-sz wareq-sz svctm %util
sda2 9.12 2.07 517.78 444.53 0.63 0.35 6.49 14.32 0.43 2.59 0.01 56.79 214.61 0.35 0.40
avg-cpu: %user %nice %system %iowait %steal %idle
0.07 0.00 0.51 1.35 0.00 98.07
Device r/s w/s rkB/s wkB/s rrqm/s wrqm/s %rrqm %wrqm r_await w_await aqu-sz rareq-sz wareq-sz svctm %util
sda2 2685.00 423.51 151832.83 107654.59 0.00 2.28 0.00 0.54 0.48 2.73 2.43 56.55 254.19 0.32 99.98
$ cat uptime.log
10:27:18 up 3 days, 16:10, 3 users, load average: 0.05, 0.25, 0.27
10:28:20 up 3 days, 16:11, 3 users, load average: 1.07, 0.51, 0.36
10:28:25 up 3 days, 16:11, 3 users, load average: 1.14, 0.53, 0.37
10:28:30 up 3 days, 16:11, 3 users, load average: 1.13, 0.54, 0.37
10:28:35 up 3 days, 16:11, 3 users, load average: 1.20, 0.57, 0.38
```
Kernel Uninterrutible Off-CPU圖如下所示: 點擊此鏈結[Kernel Uninterruptible Off-CPU Flame Graph](https://raw.githubusercontent.com/AdrianHuang/svg/master/tar.svg) 可查看細節。
其中會發現很多 `kworker` 相關的 call path，例如: `kworker/17:1;ret_from_fork;kthread;worker_thread;schedule;finish_task_switch`。因為，在 `kthread` 函數就會設置 `TASK_UNINTERRUPTIBLE`，所以不管該 `kworker` 是否有工作要做，都會被 ebpf 記錄下來 (該 `kworker` 發現沒有工作可做，就直接呼叫排程器)。
```cpp
/* Source file: "kernel/kthread.c" */
static int kthread(void *_create)
{
...
/* OK, tell user we're spawned, wait for stop or wakeup */
_set_current_state(TASK_UNINTERRUPTIBLE);
create->result = current;
...
}
```
有工作可做的 `kworker` (可找是否有 `process_one_work` 函數): `kworker/u146:3;ret_from_fork;kthread;worker_thread;process_one_work;wb_workfn;wb_writeback;__writeback_inodes_wb;writeback_sb_inodes;__writeback_single_inode;do_writepages;ext4_writepages;ext4_io_submit;submit_bio;generic_make_request;blk_mq_make_request;__rq_qos_throttle;wbt_wait;rq_qos_wait;io_schedule;schedule;finish_task_switch `
因此，把 call path `kworker/17:1;ret_from_fork;kthread;worker_thread;schedule;finish_task_switch` 移除後的 [Flame Gragh](https://raw.githubusercontent.com/AdrianHuang/svg/master/tar-trim.svg) (可點擊觀看細節) 如下:
**解析系統負載**
* pidstat: 0.34 CPU 使用率
* `tar` offcpu flame graph (uninterruptible task): 0.68 (40.521 / 60)。
* kernel kworker: 17.557 / 60 (kworker/u146:3) + 4.685 / 60(kworker/u146:2) = 0.29 + 0.08 = 0.37
測量所得 load average: 0.34 + 0.68 + 0.37 = 1.39。
對照 `uptime` 指令: 從 'cat uptime.log' 選取這個時間點 "10:28:25 .... load average: 1.14, 0.53, 0.37" (因為，`uptime` 每 5 秒 + 10 ticks 更新一次)，所以 load average = 1.14
1.39 - 1.14 = 0.25。多了 0.25 系統負載，反覆做了 5 次測試，得出的結果都差不多。比對 [Brendan Gregg - Linux Load Averages: Solving the Mystery](http://www.brendangregg.com/blog/2017-08-08/linux-load-averages.html)，其結果跟 Brendan 不太一致 (已寫信問 Brendan 相關問題，如有回覆，再做更新)。
### 2. PSI - Pressure Stall Information (kernel/sched/psi.c)
[註:下述內容大多翻譯至 `kernel/sched/psi.c` 程式碼註解]
PSI 由 Fackbook 提出來 (隨後，Google 也加入原始碼貢獻)，用來觀察處理器、記憶體與 I/O 裝置使用狀態。處理器、記憶體與 I/O 裝置發生競爭時，工作任務 (Task or Process) 會有延遲，且吞吐量 (Throughtput) 下降。當只有記憶體與 I/O 裝置發生競爭時，處理器處於等待狀態 (idle)，處理器什麼事情都不能做。
#### 名詞定義
壓力 (Pressure): 因為資源競爭所導致的等待時間。
生產力 (Productivity): 處理器執行一個工作任務所花費時間，所包含兩個元素 `工作量 (Workload)` 與 `處理器 (CPU)`。為了量測這個兩個元素的壓力影響，定義兩個狀態 `SOME` 與 `FULL`。
* SOME: 一個資源的 `SOME` 狀態，代表一個或多個任務因為等待此資源，所產生的執行延遲。此狀態影響工作量 (workload) 的執行時間。但處理器仍可以執行其它任務。其對應判斷式如下:
* SOME = nr_delayed_tasks != 0
* %SOME = time(SOME) / period -> 代表工作量延遲 (workload slowdown) 百分比，或稱壓力數值 (Pressure number) 百分比。
* 考慮多處理器情境: 257 tasks 跑在 256 個處理器。依據公式，處理器 SOME 百分比為 100 % (因為有一個 task 無法被處理器執行)。但實際上，正確的處理器 SOME 百分比為 0.4% (1/257 * 100%)
* 多處理器情境下的 `SOME` 與 `FULL` 正確公式:
```
threads = min(nr_nonidle_tasks, nr_cpus)
SOME = min(nr_delayed_tasks / threads, 1)
FULL = (threads - min(nr_running_tasks, threads)) / threads
套用情境"257 tasks 跑在 256 個處理器":
threads = min(257, 256) = 256
SOME = min(1 / 256, 1) = 0.4%
FULL = (256 - min(257, 256)) / 256 = 0%
```
* FULL: 一個資源的 `FULL` 狀態，代表所有非空閒任務 (all non-idle task) 因為等待此資源，所產生的執行延遲。處理器處於空閒狀態，什麼事情都沒得做。其對應判斷式如下:
* FULL = nr_delayed_tasks != 0 && nr_running_tasks == 0
* %FULL = time(FULL) / period -> 代表處理器使用率降低百分比，或稱壓力數值 (pressure number) 百分比。
* 考慮多處理器情境: 4 tasks 跑在 4 個處理器，但有一個 task 因為等待記憶體資源，並沒有被處理器繼續執行。依據公式，記憶體壓力數值百分比為 0% (因為 nr_running_tasks = 3)。但實際上，正確記憶體壓力數值百分比為 25% (1/4 處理器因為等待記憶體，而無法繼續執行該 task)。
* 使用多處理器情境下的 `SOME` 與 `FULL` 公式:
```
threads = min(4, 4) = 4
SOME = min(1 / 4, 1) = 25%
FULL = (4 - min(3, 4)) / 4 = 25%
```
依據上述定義，處理器沒有 `FULL` 狀態。底下命令列觀察這三個資源內容
```shell
$ ls /proc/pressure/
cpu io memory
$ cat /proc/pressure/cpu
some avg10=0.00 avg60=0.00 avg300=0.00 total=77688342
$ cat /proc/pressure/memory
some avg10=0.00 avg60=0.00 avg300=0.00 total=0
full avg10=0.00 avg60=0.00 avg300=0.00 total=0
$ cat /proc/pressure/io
some avg10=0.00 avg60=0.00 avg300=0.00 total=1187416912
full avg10=0.00 avg60=0.00 avg300=0.00 total=1185350967
```
從 `cat` 命令輸出可看到 `avg10=0.00 avg60=0.00 avg300=0.00`，即代表每10/60/300秒更新數據。
從底下程式碼可看出 PSI 使用定點數 (跟 `Linux Kernel Load Average` 設計很像)，每2秒計算 avg10/avg60/avg300 數據。
```cpp
kernel/sched/psi.c
...
/* Running averages - we need to be higher-res than loadavg */
#define PSI_FREQ (2*HZ+1) /* 2 sec intervals */
#define EXP_10s 1677 /* 1/exp(2s/10s) as fixed-point */
#define EXP_60s 1981 /* 1/exp(2s/60s) */
#define EXP_300s 2034 /* 1/exp(2s/300s) */
...
static void calc_avgs(unsigned long avg[3], int missed_periods,
u64 time, u64 period)
{
unsigned long pct;
/* Fill in zeroes for periods of no activity */
if (missed_periods) {
avg[0] = calc_load_n(avg[0], EXP_10s, 0, missed_periods);
avg[1] = calc_load_n(avg[1], EXP_60s, 0, missed_periods);
avg[2] = calc_load_n(avg[2], EXP_300s, 0, missed_periods);
}
/* Sample the most recent active period */
pct = div_u64(time * 100, period);
pct *= FIXED_1;
avg[0] = calc_load(avg[0], EXP_10s, pct);
avg[1] = calc_load(avg[1], EXP_60s, pct);
avg[2] = calc_load(avg[2], EXP_300s, pct);
}
...
```
## `MathEx` 如何解析給定字串，從而分離出變數和對應數學表示法呢？
### 資料結構簡介 (這些結構會搭配 `gdb` 有詳盡的圖文解說):
* vec_expr_t: 儲存 `struct expr` 結構的 vector 結構。`struct expr` 用來表示一個數學表示式，其形態如: +, -, *, /, >>, <<, relational operator (>, >=, <, <=), Bitwise AND/OR/XOR, assignment, ',', variable, function 等等。 MathEx 所以定義的型態如下:
```cpp
10 /*
11 * Expression data types
12 */
13
14 enum expr_type {
15 OP_UNKNOWN,
16 OP_UNARY_MINUS,
17 OP_UNARY_LOGICAL_NOT,
18 OP_UNARY_BITWISE_NOT,
19
20 OP_POWER,
21 OP_DIVIDE,
22 OP_MULTIPLY,
23 OP_REMAINDER,
24
25 OP_PLUS,
26 OP_MINUS,
27
28 OP_SHL,
29 OP_SHR,
30
31 OP_LT,
32 OP_LE,
33 OP_GT,
34 OP_GE,
35 OP_EQ,
36 OP_NE,
37
38 OP_BITWISE_AND,
39 OP_BITWISE_OR,
40 OP_BITWISE_XOR,
41
42 OP_LOGICAL_AND,
43 OP_LOGICAL_OR,
44
45 OP_ASSIGN,
46 OP_COMMA,
47
48 OP_CONST,
49 OP_VAR,
50 OP_FUNC,
51 };
```
* vec_str_t: 儲存 `struct expr_string` 結構的 vector 結構。其儲存的字串用途:
* 用來保存解析運算式字串的某特定位址，以便後續解析子串可向前參考。
* 特定的字串: 譬如 "{"，用來標註一個 `function`, `$` 與 `macro` 的起始位址，以便後續解析子串可向前參考。
* vec_arg_t: 儲存 `struct expr_arg` 結構的 vector 結構。`struct expr_arg` 用來保存 function/macro 的 argument。如 `add(x, 10)`，`x` 與 `10` 會被保存在 `struct expr_arg` 結構中，並用 `struct expr` 表示 `x` 與 `10`。以便後續解析子串可向前參考。
* struct expr_var_list: `struct expr_var` 結構鏈表的第一個元素。 `struct expr_var` 用來保存變數名稱。
### 使用 gdb 觀察 MathEx 行為
使用 gdb 觀看變數內容 (尤其是本地變數 - Local Variable)，gdb 會顯示 `<optimized out>` 訊息，導致無法得知變數內容。
```
(gdb) b expression.c:512
Breakpoint 1 at 0x4b80: file expression.c, line 512.
(gdb) r
Starting program: /home/adrian/archive/jserv/linux2020/MathEX/build/test-simple
Breakpoint 1, expr_create (s=0x8007444 "xyz = 4 + 5, xyz = xyz + 8", len=26,
vars=0x7ffffffee2e0, funcs=0x8209020 <user_funcs>) at expression.c:512
512 if (*tok == '#') {
(gdb) p idn
$7 = <optimized out>
```
其原因使用 gcc 編譯時，加入優化等級 (-O1, -O2 等等)，改為 -O0 就可以得知變數內容:
```diff
MathEX$ git diff
diff --git a/Makefile b/Makefile
index c1d4a6b..78a2040 100644
--- a/Makefile
+++ b/Makefile
@@ -11,7 +11,7 @@ all: $(EXEC)
.PHONY: check clean
CC ?= gcc
-CFLAGS = -Wall -std=c99 -g -O2 -I.
+CFLAGS = -Wall -std=c99 -g -O0 -I.
LDFLAGS = -lm
OBJS := \
```
使用 `test-simple.c` 的表示式 "x = 40, add(2, x)" 為例，並把中斷點設在 `expression.c` 512行。
```
$ gdb ./build/test-simple
(gdb) b expression.c:512
Breakpoint 1 at 0x2a95: file expression.c, line 512.
```
執行該程式後，觀察其 token = 'x' (*tok = 'x') 且長度為 1 (n = 1)，也可使用 `s` 命令單步執行觀察其程式行為。呼叫其它函數，如果不想單步執行該函數程式，可使用 `finish` 命令，回到呼叫該函數的地方 如底下範例所示。
```
(gdb) r
Starting program: /home/adrian/archive/jserv/linux2020/MathEX/build/test-simple
Breakpoint 1, expr_create (s=0x8004ad9 " = 40, add(2, x)", len=16,
vars=0x7ffffffee2e0, funcs=0x8206020 <user_funcs>) at expression.c:512
512 if (*tok == '#') {
(gdb) p *tok
$1 = 120 'x'
(gdb) p n
$2 = 1
(gdb) s
515 if (flags & EXPR_UNARY) {
(gdb) s
533 if (*tok == '\n' && (flags & EXPR_COMMA)) {
(gdb) s
538 if (isspace(*tok)) {
(gdb) s
__ctype_b_loc () at ../include/ctype.h:38
38 ../include/ctype.h: No such file or directory.
(gdb) finish
Run till exit from #0 __ctype_b_loc () at ../include/ctype.h:38
0x0000000008002b5e in expr_create (s=0x8004ad9 " = 40, add(2, x)", len=16,
vars=0x7ffffffee2e0, funcs=0x8206020 <user_funcs>) at expression.c:538
538 if (isspace(*tok)) {
Value returned is $4 = (const uint16_t **) 0x7fffff7c06d8
(gdb) s
541 int paren_next = EXPR_PAREN_ALLOWED;
...
```
***tok = 'x' 且 n = 1**: 滿足底下 720 行條件。
```cpp
719 } else {
720 if (n > 0 && !isdigit(*tok)) {
721 /* Valid identifier, a variable or a function */
722 id = tok;
723 idn = n;
724 } else {
725 goto cleanup; // Bad variable name, e.g. '2.3.4' or '4ever'
726 }
727 }
```
(省略空白字元解說) 執行 `c` 命令，讓程式繼續執行。
```
(gdb) c
Continuing.
Breakpoint 1, expr_create (s=0x8004adb " 40, add(2, x)", len=14,
vars=0x7ffffffee2e0, funcs=0x8206020 <user_funcs>) at expression.c:512
512 if (*tok == '#') {
(gdb) p *tok
$9 = 61 '='
(gdb) p n
$10 = 1
...
(gdb) s
564 } else if ((v = expr_var(vars, id, idn))) {
(gdb) s
expr_var (vars=0x7ffffffee2e0, s=0x8004ad8 "x = 40, add(2, x)", len=1)
at expression.c:169
169 struct expr_var *v = NULL;
(gdb) finish
Run till exit from #0 expr_var (vars=0x7ffffffee2e0,
s=0x8004ad8 "x = 40, add(2, x)", len=1) at expression.c:169
0x0000000008002d7b in expr_create (s=0x8004adb " 40, add(2, x)", len=14,
vars=0x7ffffffee2e0, funcs=0x8206020 <user_funcs>) at expression.c:564
564 } else if ((v = expr_var(vars, id, idn))) {
Value returned is $12 = (struct expr_var *) 0x8407260
(gdb) s
565 vec_push(&es, expr_varref(v));
```
**idn = 1, n =1, *tok = '='**: 執行 564-567行。
```cpp
543 if (idn > 0) {
544 if (n == 1 && *tok == '(') {
545 int i;
546 int has_macro = 0;
547 struct macro m;
548 vec_foreach(¯os, m, i)
549 {
550 if (strlen(m.name) == idn
551 && strncmp(m.name, id, idn) == 0) {
552 has_macro = 1;
553 break;
554 }
555 }
556 if ((idn == 1 && id[0] == '$') || has_macro
557 || expr_func(funcs, id, idn)) {
558 struct expr_string str = { id, (int)idn };
559 vec_push(&os, str);
560 paren = EXPR_PAREN_EXPECTED;
561 } else {
562 goto cleanup; /* invalid function name */
563 }
564 } else if ((v = expr_var(vars, id, idn))) {
565 vec_push(&es, expr_varref(v));
566 paren = EXPR_PAREN_FORBIDDEN;
567 }
568 id = NULL;
569 idn = 0;
570 }
```
執行 564-567行，觀察 `es` 與 `v` 變數。
```
(gdb) p es
$15 = {
buf = 0x8407280,
len = 1,
cap = 1
}
(gdb) p es.buf[0]
$16 = {
type = 26,
param = {
num = {
value = 5.79123455e-34
},
var = {
value = 0x8407260
},
op = {
args = {
buf = 0x8407260,
len = 0,
cap = 0
}
},
func = {
f = 0x8407260,
args = {
buf = 0x0,
len = 0,
cap = 0
},
context = 0x0
}
}
}
(gdb) p v
$17 = (struct expr_var *) 0x8407260
(gdb) p *v
$18 = {
value = 0,
next = 0x0,
name = 0x8407270 "x"
}
```
其對應結構關係圖如下，可看出變數 `x` 物件 (expr_var) 已經被建立，其變數名稱 (name) 已經被設置，但內容值 (value) 還沒被設置。
**idn = 1, n =1, *tok = '='**: 執行 687 行程式區塊的 703-707行
```
(gdb) f
#0 expr_create (s=0x8004adb " 40, add(2, x)", len=14, vars=0x7ffffffee2e0,
funcs=0x8206020 <user_funcs>) at expression.c:706
706 break;
(gdb) p str
$28 = {
s = 0x8004ada "= 40, add(2, x)",
n = 1
}
(gdb) p os
$29 = {
buf = 0x84072b0,
len = 1,
cap = 1
}
(gdb) p os.buf[0]
$30 = {
s = 0x8004ada "= 40, add(2, x)",
n = 1
}
```
```cpp
687 } else if (expr_op(tok, n, -1) != OP_UNKNOWN) {
688 enum expr_type op = expr_op(tok, n, -1);
689 struct expr_string o2 = { NULL, 0 };
690 if (vec_len(&os) > 0) {
691 o2 = vec_peek(&os);
692 }
693 for (;;) {
694 if (n == 1 && *tok == ',' && vec_len(&os) > 0) {
695 struct expr_string str = vec_peek(&os);
696 if (str.n == 1 && *str.s == '{') {
697 struct expr e = vec_pop(&es);
698 vec_push(&vec_peek(&as).args, e);
699 break;
700 }
701 }
702 enum expr_type type2 = expr_op(o2.s, o2.n, -1);
703 if (!(type2 != OP_UNKNOWN && expr_prec(op, type2))) {
704 struct expr_string str = { tok, n };
705 vec_push(&os, str);
706 break;
707 }
708
709 if (expr_bind(o2.s, o2.n, &es) == -1) {
710 goto cleanup;
711 }
712 (void)vec_pop(&os);
713 if (vec_len(&os) > 0) {
714 o2 = vec_peek(&os);
715 } else {
716 o2.n = 0;
717 }
718 }
719 } else {
```
其對應結構圖如下:
**idn = 0, n = 2, *tok = '4'**: 執行 684-686 行。
```
(gdb) c
Continuing.
Breakpoint 1, expr_create (s=0x8004ade ", add(2, x)", len=11,
vars=0x7ffffffee2e0, funcs=0x8206020 <user_funcs>) at expression.c:512
512 if (*tok == '#') {
(gdb) p *tok
$34 = 52 '4'
(gdb) p n
$35 = 2
...
(gdb) s
expr_const (value=40) at expression.c:424
424 struct expr e = expr_init();
(gdb) finish
Run till exit from #0 expr_const (value=40) at expression.c:424
0x0000000008003ccf in expr_create (s=0x8004ade ", add(2, x)", len=11,
vars=0x7ffffffee2e0, funcs=0x8206020 <user_funcs>) at expression.c:685
685 vec_push(&es, expr_const(num));
Value returned is $41 =
{type = 25, param = {num = {value = 40}, var = {value = 0x42200000}, op = {args = {buf = 0x42200000, len = 0, cap = 0}}, func = {f = 0x42200000, args = {buf = 0x0, len = 0, cap = 0}, context = 0x0}}}
(gdb) s
686 paren_next = EXPR_PAREN_FORBIDDEN;
```
```cpp
684 } else if (!isnan(num = expr_parse_number(tok, n))) {
685 vec_push(&es, expr_const(num));
686 paren_next = EXPR_PAREN_FORBIDDEN;
687 } else if (expr_op(tok, n, -1) != OP_UNKNOWN) {
```
觀察 `es` 變數結構，由此可看出常數 `40` 的 expr 結構被加入至 `es.buf[1]`。
```
(gdb) p es
$42 = {
buf = 0x84072d0,
len = 2,
cap = 2
}
(gdb) p es.buf[0]
$43 = {
type = 26,
param = {
num = {
value = 5.79123455e-34
},
var = {
value = 0x8407260
},
op = {
args = {
buf = 0x8407260,
len = 0,
cap = 0
}
},
func = {
f = 0x8407260,
args = {
buf = 0x0,
len = 0,
cap = 0
},
context = 0x0
}
}
}
(gdb) p es.buf[1]
$44 = {
type = 25,
param = {
num = {
value = 40
},
var = {
value = 0x42200000
},
op = {
args = {
buf = 0x42200000,
len = 0,
cap = 0
}
},
func = {
f = 0x42200000,
args = {
buf = 0x0,
len = 0,
cap = 0
},
context = 0x0
}
}
}
```
其對應結構圖如下。可以看出解析到 x = 40 時，`x` (OP_VAR) 與 `40` (OP_CONST) 有對應的 `expr` 結構，`=` 運算子對應結構在哪呢?
**idn = 0, n = 1, *tok = ','**:
* 執行 687 行程式區塊的 709行，也就是遇到逗號時且 `os` 的 expr_type != OP_UNKNOWN 時，將 `es` 最後兩個 `buf` 元素合併為一個。
```
(gdb) s
709 if (expr_bind(o2.s, o2.n, &es) == -1) {
(gdb) s
expr_bind (s=0x8004ada "= 40, add(2, x)", len=1, es=0x7ffffffee0f0)
at expression.c:389
389 {
(gdb) finish
Run till exit from #0 expr_bind (s=0x8004ada "= 40, add(2, x)", len=1,
es=0x7ffffffee0f0) at expression.c:389
0x00000000080040c6 in expr_create (s=0x8004adf " add(2, x)", len=10,
vars=0x7ffffffee2e0, funcs=0x8206020 <user_funcs>) at expression.c:709
709 if (expr_bind(o2.s, o2.n, &es) == -1) {
Value returned is $59 = 0
(gdb) p es
$61 = {
buf = 0x84072d0,
len = 1,
cap = 2
}
(gdb) p es.buf[0]
$62 = {
type = 23,
param = {
num = {
value = 5.79133006e-34
},
var = {
value = 0x8407330
},
op = {
args = {
buf = 0x8407330,
len = 2,
cap = 2
}
},
func = {
f = 0x8407330,
args = {
buf = 0x200000002,
len = 0,
cap = 0
},
context = 0x0
}
}
}
(gdb) p es.buf[0].param.op.args.buf[0]
$71 = {
type = 26,
param = {
num = {
value = 5.79123455e-34
},
var = {
value = 0x8407260
},
op = {
args = {
buf = 0x8407260,
len = 0,
cap = 0
}
},
func = {
f = 0x8407260,
args = {
buf = 0x0,
len = 0,
cap = 0
},
context = 0x0
}
}
}
(gdb) p es.buf[0].param.op.args.buf[1]
$72 = {
type = 25,
param = {
num = {
value = 40
},
var = {
value = 0x42200000
},
op = {
args = {
buf = 0x42200000,
len = 0,
cap = 0
}
},
func = {
f = 0x42200000,
args = {
buf = 0x0,
len = 0,
cap = 0
},
context = 0x0
}
}
}
(gdb) p es.buf[0].param.op.args.buf[0].param.var.value
$94 = (float *) 0x8407260
(gdb) p (struct expr_var) *es.buf[0].param.op.args.buf[0].param.var.value
$93 = {
value = 0,
next = 0x0,
name = 0x8407270 "x"
}
```
一旦解析到逗號運算子，`expression.c:709 if (expr_bind(o2.s, o2.n, &es) == -1) {` 會將 `x` (OP_VAR) 與 `40` (OP_CONST) 對應的 `expr` 結構合併至一個新的 `=` (OP_ASSIGN) `expr` 結構。其對應結構圖如下 (可搭配上面 gdb 資訊)。故解析至 "x = 40,"，`MathEx` 知道 `x` 是一個變數，其值為 40。
* 執行 712 行，將 `os` 變數的最後一個元素結構提取/移除 (stack 結構的 `pop` 操作) 出來。
```
(gdb) f
#0 0x00000000080040c6 in expr_create (s=0x8004adf " add(2, x)", len=10,
vars=0x7ffffffee2e0, funcs=0x8206020 <user_funcs>) at expression.c:709
709 if (expr_bind(o2.s, o2.n, &es) == -1) {
(gdb) s
712 (void)vec_pop(&os);
(gdb) p os
$98 = {
buf = 0x84072b0,
len = 1,
cap = 1
}
(gdb) s
713 if (vec_len(&os) > 0) {
(gdb) p os
$99 = {
buf = 0x84072b0,
len = 0,
cap = 1
}
(gdb) p *os.buf
$106 = {
s = 0x8004ada "= 40, add(2, x)",
n = 1
}
```
其對應 `os` 變數結構如下，留意 `os.len = 0`。
* 因為 `expression.c:693 for (;;) {` 迴圈，執行 703-707 行並跳出該迴圈。
```
(gdb) f
#0 expr_create (s=0x8004adf " add(2, x)", len=10, vars=0x7ffffffee2e0,
funcs=0x8206020 <user_funcs>) at expression.c:694
694 if (n == 1 && *tok == ',' && vec_len(&os) > 0) {
(gdb) s
702 enum expr_type type2 = expr_op(o2.s, o2.n, -1);
(gdb) s
expr_op (s=0x8004ada "= 40, add(2, x)", len=0, unary=-1) at expression.c:112
112 for (unsigned int i = 0; i < sizeof(OPS) / sizeof(OPS[0]); i++) {
(gdb) finish
Run till exit from #0 expr_op (s=0x8004ada "= 40, add(2, x)", len=0, unary=-1)
at expression.c:112
0x0000000008003ff1 in expr_create (s=0x8004adf " add(2, x)", len=10,
vars=0x7ffffffee2e0, funcs=0x8206020 <user_funcs>) at expression.c:702
702 enum expr_type type2 = expr_op(o2.s, o2.n, -1);
Value returned is $107 = OP_UNKNOWN
(gdb) s
703 if (!(type2 != OP_UNKNOWN && expr_prec(op, type2))) {
(gdb) s
704 struct expr_string str = { tok, n };
(gdb) s
705 vec_push(&os, str);
(gdb) s
vec_expand (buf=0x7ffffffee100, length=0x7ffffffee108, cap=0x7ffffffee10c,
memsz=16) at expression.h:37
37 if (*length + 1 > *cap) {
(gdb) finish
Run till exit from #0 vec_expand (buf=0x7ffffffee100, length=0x7ffffffee108,
cap=0x7ffffffee10c, memsz=16) at expression.h:37
0x0000000008004061 in expr_create (s=0x8004adf " add(2, x)", len=10,
vars=0x7ffffffee2e0, funcs=0x8206020 <user_funcs>) at expression.c:705
705 vec_push(&os, str);
Value returned is $108 = 0
(gdb) p os
$109 = {
buf = 0x84072b0,
len = 0,
cap = 1
}
(gdb) s
706 break;
(gdb) p os
$110 = {
buf = 0x84072b0,
len = 1,
cap = 1
}
(gdb) p *os.buf
$111 = {
s = 0x8004ade ", add(2, x)",
n = 1
}
```
其對應 `os` 變數結構如下。
**idn = 0, n = 3, *tok = 'a'**: 執行 720-723 行
```
(gdb) f
#0 expr_create (s=0x8004ae3 "(2, x)", len=6, vars=0x7ffffffee2e0,
funcs=0x8206020 <user_funcs>) at expression.c:720
720 if (n > 0 && !isdigit(*tok)) {
(gdb) p *tok
$122 = 97 'a'
(gdb) p n
$123 = 3
(gdb) s
__ctype_b_loc () at ../include/ctype.h:38
38 ../include/ctype.h: No such file or directory.
(gdb) finish
Run till exit from #0 __ctype_b_loc () at ../include/ctype.h:38
0x000000000800413e in expr_create (s=0x8004ae3 "(2, x)", len=6,
vars=0x7ffffffee2e0, funcs=0x8206020 <user_funcs>) at expression.c:720
720 if (n > 0 && !isdigit(*tok)) {
Value returned is $124 = (const uint16_t **) 0x7fffff7c06d8
(gdb) s
722 id = tok;
(gdb) s
723 idn = n;
(gdb) s
728 paren = paren_next;
(gdb) p id
$127 = 0x8004ae0 "add(2, x)"
(gdb) p idn
$128 = 3
```
**idn = 3, n = 1, *tok = '('**:
* 執行 543-570 程式區塊的 556-560 行。
```
(gdb) c
Continuing.
Breakpoint 1, expr_create (s=0x8004ae4 "2, x)", len=5, vars=0x7ffffffee2e0,
funcs=0x8206020 <user_funcs>) at expression.c:512
512 if (*tok == '#') {
(gdb) p *tok
$129 = 40 '('
(gdb) p n
$130 = 1
(gdb) p idn
$131 = 3
...
(gdb) s
expr_func (funcs=0x8206020 <user_funcs>, s=0x8004ae0 "add(2, x)", len=3)
at expression.c:154
154 for (struct expr_func *f = funcs; f->name; f++) {
(gdb) finish
Run till exit from #0 expr_func (funcs=0x8206020 <user_funcs>,
s=0x8004ae0 "add(2, x)", len=3) at expression.c:154
0x0000000008002cc6 in expr_create (s=0x8004ae4 "2, x)", len=5,
vars=0x7ffffffee2e0, funcs=0x8206020 <user_funcs>) at expression.c:557
557 || expr_func(funcs, id, idn)) {
Value returned is $133 = (struct expr_func *) 0x8206020 <user_funcs>
(gdb) s
558 struct expr_string str = { id, (int)idn };
(gdb) s
559 vec_push(&os, str);
(gdb) p os
$134 = {
buf = 0x84072b0,
len = 1,
cap = 1
}
(gdb) s
vec_expand (buf=0x7ffffffee100, length=0x7ffffffee108, cap=0x7ffffffee10c,
memsz=16) at expression.h:37
37 if (*length + 1 > *cap) {
(gdb) finish
Run till exit from #0 vec_expand (buf=0x7ffffffee100, length=0x7ffffffee108,
cap=0x7ffffffee10c, memsz=16) at expression.h:37
0x0000000008002d14 in expr_create (s=0x8004ae4 "2, x)", len=5,
vars=0x7ffffffee2e0, funcs=0x8206020 <user_funcs>) at expression.c:559
559 vec_push(&os, str);
Value returned is $135 = 0
(gdb) p os
$137 = {
buf = 0x8407390,
len = 2,
cap = 2
}
(gdb) p os.buf[0]
$138 = {
s = 0x8004ade ", add(2, x)",
n = 1
}
(gdb) p os.buf[1]
$139 = {
s = 0x8004ae0 "add(2, x)",
n = 3
}
```
其對應 `os` 變數結構如下。
* 執行 572-584 程式區塊的 573-578 行。
```
...
(gdb) s
572 if (n == 1 && *tok == '(') {
(gdb) s
573 if (paren == EXPR_PAREN_EXPECTED) {
(gdb) s
574 struct expr_string str = { "{", 1 };
(gdb) s
575 vec_push(&os, str);
(gdb) s
vec_expand (buf=0x7ffffffee100, length=0x7ffffffee108, cap=0x7ffffffee10c,
memsz=16) at expression.h:37
37 if (*length + 1 > *cap) {
(gdb) finish
Run till exit from #0 vec_expand (buf=0x7ffffffee100, length=0x7ffffffee108,
cap=0x7ffffffee10c, memsz=16) at expression.h:37
0x0000000008002ec6 in expr_create (s=0x8004ae4 "2, x)", len=5,
vars=0x7ffffffee2e0, funcs=0x8206020 <user_funcs>) at expression.c:575
575 vec_push(&os, str);
Value returned is $141 = 0
(gdb) s
577 = { vec_len(&os), vec_len(&es), vec_init() };
(gdb) s
576 struct expr_arg arg
(gdb) s
577 = { vec_len(&os), vec_len(&es), vec_init() };
(gdb) s
576 struct expr_arg arg
(gdb) s
578 vec_push(&as, arg);
(gdb) s
vec_expand (buf=0x7ffffffee110, length=0x7ffffffee118, cap=0x7ffffffee11c,
memsz=24) at expression.h:37
37 if (*length + 1 > *cap) {
(gdb) finish
Run till exit from #0 vec_expand (buf=0x7ffffffee110, length=0x7ffffffee118,
cap=0x7ffffffee11c, memsz=24) at expression.h:37
0x0000000008002f5f in expr_create (s=0x8004ae4 "2, x)", len=5,
vars=0x7ffffffee2e0, funcs=0x8206020 <user_funcs>) at expression.c:578
578 vec_push(&as, arg);
Value returned is $142 = 0
(gdb) s
573 if (paren == EXPR_PAREN_EXPECTED) {
(gdb) p os
$160 = {
buf = 0x8407390,
len = 3,
cap = 4
}
(gdb) p os.buf[0]
$161 = {
s = 0x8004ade ", add(2, x)",
n = 1
}
(gdb) p os.buf[1]
$162 = {
s = 0x8004ae0 "add(2, x)",
n = 3
}
(gdb) p os.buf[2]
$163 = {
s = 0x8004bc0 "{",
n = 1
}
(gdb) p as
$164 = {
buf = 0x84072b0,
len = 1,
cap = 1
}
(gdb) p as.buf[0]
$165 = {
oslen = 3,
eslen = 1,
args = {
buf = 0x0,
len = 0,
cap = 0
}
}
```
其對應 `os` 變數結構如下。當前一個 token 為函數、巨集或 `$` 開頭算式，則產生一個字串為 "{" 的 `expr_string` 結構，並加入至 `os` 變數結構，以便後續處理。
其對應 `as` 變數結構如下。同上條件，產生一個 `expr_arg` 結構並加入 `as` 變數結構。
**idn = 0, n = 1, *tok = '2'**: 執行 684-686 行
```
(gdb) c
Continuing.
Breakpoint 1, expr_create (s=0x8004ae5 ", x)", len=4, vars=0x7ffffffee2e0,
funcs=0x8206020 <user_funcs>) at expression.c:512
512 if (*tok == '#') {
(gdb) p *tok
$167 = 50 '2'
(gdb) p n
$168 = 1
(gdb) p idn
$169 = 0
...
(gdb) s
684 } else if (!isnan(num = expr_parse_number(tok, n))) {
(gdb) s
expr_parse_number (s=0x8004ae4 "2, x)", len=1) at expression.c:123
123 float num = 0;
(gdb) finish
Run till exit from #0 expr_parse_number (s=0x8004ae4 "2, x)", len=1)
at expression.c:123
0x0000000008003c34 in expr_create (s=0x8004ae5 ", x)", len=4,
vars=0x7ffffffee2e0, funcs=0x8206020 <user_funcs>) at expression.c:684
684 } else if (!isnan(num = expr_parse_number(tok, n))) {
Value returned is $21 = 2
(gdb) s
685 vec_push(&es, expr_const(num));
(gdb) s
vec_expand (buf=0x7ffffffee0f0, length=0x7ffffffee0f8, cap=0x7ffffffee0fc,
memsz=40) at expression.h:37
warning: Source file is more recent than executable.
37 if (*length + 1 > *cap) {
(gdb) finish
Run till exit from #0 vec_expand (buf=0x7ffffffee0f0, length=0x7ffffffee0f8,
cap=0x7ffffffee0fc, memsz=40) at expression.h:37
0x0000000008003c79 in expr_create (s=0x8004ae5 ", x)", len=4,
vars=0x7ffffffee2e0, funcs=0x8206020 <user_funcs>) at expression.c:685
685 vec_push(&es, expr_const(num));
Value returned is $172 = 0
(gdb) s
expr_const (value=2) at expression.c:424
424 struct expr e = expr_init();
(gdb) finish
Run till exit from #0 expr_const (value=2) at expression.c:424
0x0000000008003ccf in expr_create (s=0x8004ae5 ", x)", len=4,
vars=0x7ffffffee2e0, funcs=0x8206020 <user_funcs>) at expression.c:685
685 vec_push(&es, expr_const(num));
Value returned is $173 =
{type = 25, param = {num = {value = 2}, var = {value = 0x40000000}, op = {args = {buf = 0x40000000, len = 0, cap = 0}}, func = {f = 0x40000000, args = {buf = 0x0, len = 0, cap = 0}, context = 0x0}}}
(gdb) s
686 paren_next = EXPR_PAREN_FORBIDDEN;
(gdb) p es
$177 = {
buf = 0x84072d0,
len = 2,
cap = 2
}
(gdb) p es.buf[0]
$178 = {
type = 23,
param = {
num = {
value = 5.79133006e-34
},
var = {
value = 0x8407330
},
op = {
args = {
buf = 0x8407330,
len = 2,
cap = 2
}
},
func = {
f = 0x8407330,
args = {
buf = 0x200000002,
len = 0,
cap = 0
},
context = 0x0
}
}
}
(gdb) p es.buf[1]
$179 = {
type = 25,
param = {
num = {
value = 2
},
var = {
value = 0x40000000
},
op = {
args = {
buf = 0x40000000,
len = 0,
cap = 0
}
},
func = {
f = 0x40000000,
args = {
buf = 0x0,
len = 0,
cap = 0
},
context = 0x0
}
}
}
```
其對應 `es` 變數結構如下，可看到常數 `2` 的 `expr` 結構被加入至 es 變數結構。
**idn = 0, n = 1, *tok = ','**: 執行 687-718 程式區塊的 694-701 行
```
(gdb) c
Continuing.
Breakpoint 1, expr_create (s=0x8004ae6 " x)", len=3, vars=0x7ffffffee2e0,
funcs=0x8206020 <user_funcs>) at expression.c:512
512 if (*tok == '#') {
(gdb) p *tok
$180 = 44 ','
(gdb) p n
$181 = 1
(gdb) p idn
$182 = 0
...
(gdb) s
687 } else if (expr_op(tok, n, -1) != OP_UNKNOWN) {
(gdb) s
expr_op (s=0x8004ae5 ", x)", len=1, unary=-1) at expression.c:112
112 for (unsigned int i = 0; i < sizeof(OPS) / sizeof(OPS[0]); i++) {
(gdb) finish
Run till exit from #0 expr_op (s=0x8004ae5 ", x)", len=1, unary=-1)
at expression.c:112
0x0000000008003d34 in expr_create (s=0x8004ae6 " x)", len=3,
vars=0x7ffffffee2e0, funcs=0x8206020 <user_funcs>) at expression.c:687
687 } else if (expr_op(tok, n, -1) != OP_UNKNOWN) {
Value returned is $185 = OP_COMMA
(gdb) s
688 enum expr_type op = expr_op(tok, n, -1);
...
(gdb) s
694 if (n == 1 && *tok == ',' && vec_len(&os) > 0) {
(gdb) s
695 struct expr_string str = vec_peek(&os);
(gdb) s
696 if (str.n == 1 && *str.s == '{') {
(gdb) p str
$187 = {
s = 0x8004bc0 "{",
n = 1
}
...
(gdb) s
vec_expand (buf=0x84072b8, length=0x84072c0, cap=0x84072c4, memsz=40)
at expression.h:37
37 if (*length + 1 > *cap) {
(gdb) finish
Run till exit from #0 vec_expand (buf=0x84072b8, length=0x84072c0,
cap=0x84072c4, memsz=40) at expression.h:37
0x0000000008003f1d in expr_create (s=0x8004ae6 " x)", len=3,
vars=0x7ffffffee2e0, funcs=0x8206020 <user_funcs>) at expression.c:698
698 vec_push(&vec_peek(&as).args, e);
Value returned is $189 = 0
(gdb) s
699 break;
(gdb) p as
$192 = {
buf = 0x84072b0,
len = 1,
cap = 1
}
(gdb) p as.buf[0]
$193 = {
oslen = 3,
eslen = 1,
args = {
buf = 0x8407280,
len = 1,
cap = 1
}
}
(gdb) p as.buf[0].args.buf[0]
$194 = {
type = 25,
param = {
num = {
value = 2
},
var = {
value = 0x40000000
},
op = {
args = {
buf = 0x40000000,
len = 0,
cap = 0
}
},
func = {
f = 0x40000000,
args = {
buf = 0x0,
len = 0,
cap = 0
},
context = 0x0
}
}
}
(gdb) p es
$195 = {
buf = 0x84072d0,
len = 1,
cap = 2
}
```
其對應 `es` 、 `as` 變數結構如下，可看到常數 `2` 的 `expr` 結構被加入至 `as` 變數結構的 `args` 成員，並從 `es` 變數結構移除。
**idn = 0, n = 1, *tok = 'x'**: 執行 720-723 行
```
(gdb) c
Continuing.
Breakpoint 1, expr_create (s=0x8004ae8 ")", len=1, vars=0x7ffffffee2e0,
funcs=0x8206020 <user_funcs>) at expression.c:512
512 if (*tok == '#') {
(gdb) p *tok
$218 = 120 'x'
(gdb) p n
$219 = 1
(gdb) p idn
$220 = 0
...
720 if (n > 0 && !isdigit(*tok)) {
(gdb) s
__ctype_b_loc () at ../include/ctype.h:38
38 ../include/ctype.h: No such file or directory.
(gdb) finish
Run till exit from #0 __ctype_b_loc () at ../include/ctype.h:38
0x000000000800413e in expr_create (s=0x8004ae8 ")", len=1, vars=0x7ffffffee2e0,
funcs=0x8206020 <user_funcs>) at expression.c:720
720 if (n > 0 && !isdigit(*tok)) {
Value returned is $224 = (const uint16_t **) 0x7fffff7c06d8
(gdb) s
722 id = tok;
(gdb) s
723 idn = n;
(gdb) s
728 paren = paren_next;
(gdb) p id
$225 = 0x8004ae7 "x)"
(gdb) p idn
$226 = 1
```
**idn = 1, n = 1, *tok = ')'**:
* 執行 543-570 程式區塊的 564-566 行
```
(gdb) c
Continuing.
Breakpoint 1, expr_create (s=0x8004ae9 "", len=0, vars=0x7ffffffee2e0,
funcs=0x8206020 <user_funcs>) at expression.c:512
512 if (*tok == '#') {
(gdb) p *tok
$227 = 41 ')'
(gdb) p n
$228 = 1
(gdb) p idn
$229 = 1
...
(gdb) s
expr_var (vars=0x7ffffffee2e0, s=0x8004ae7 "x)", len=1) at expression.c:169
169 struct expr_var *v = NULL;
(gdb) finish
Run till exit from #0 expr_var (vars=0x7ffffffee2e0, s=0x8004ae7 "x)", len=1)
at expression.c:169
0x0000000008002d7b in expr_create (s=0x8004ae9 "", len=0, vars=0x7ffffffee2e0,
funcs=0x8206020 <user_funcs>) at expression.c:564
564 } else if ((v = expr_var(vars, id, idn))) {
Value returned is $232 = (struct expr_var *) 0x8407260
(gdb) s
565 vec_push(&es, expr_varref(v));
(gdb) s
vec_expand (buf=0x7ffffffee0f0, length=0x7ffffffee0f8, cap=0x7ffffffee0fc,
memsz=40) at expression.h:37
37 if (*length + 1 > *cap) {
(gdb) finish
Run till exit from #0 vec_expand (buf=0x7ffffffee0f0, length=0x7ffffffee0f8,
cap=0x7ffffffee0fc, memsz=40) at expression.h:37
0x0000000008002dba in expr_create (s=0x8004ae9 "", len=0, vars=0x7ffffffee2e0,
funcs=0x8206020 <user_funcs>) at expression.c:565
565 vec_push(&es, expr_varref(v));
Value returned is $234 = 0
(gdb) p es
$235 = {
buf = 0x84072d0,
len = 1,
cap = 2
}
(gdb) s
expr_varref (v=0x8407260) at expression.c:432
432 struct expr e = expr_init();
(gdb) s
433 e.type = OP_VAR;
(gdb) finish
Run till exit from #0 expr_varref (v=0x8407260) at expression.c:433
0x0000000008002e02 in expr_create (s=0x8004ae9 "", len=0, vars=0x7ffffffee2e0,
funcs=0x8206020 <user_funcs>) at expression.c:565
565 vec_push(&es, expr_varref(v));
Value returned is $236 =
{type = 26, param = {num = {value = 5.79123455e-34}, var = {value = 0x8407260}, op = {args = {buf = 0x8407260, len = 0, cap = 0}}, func = {f = 0x8407260, args = {buf = 0x0, len = 0, cap = 0}, context = 0x0}}}
(gdb) s
566 paren = EXPR_PAREN_FORBIDDEN;
(gdb) p es
$237 = {
buf = 0x84072d0,
len = 2,
cap = 2
}
(gdb) p es.buf[1]
$239 = {
type = 26,
param = {
num = {
value = 5.79123455e-34
},
var = {
value = 0x8407260
},
op = {
args = {
buf = 0x8407260,
len = 0,
cap = 0
}
},
func = {
f = 0x8407260,
args = {
buf = 0x0,
len = 0,
cap = 0
},
context = 0x0
}
}
}
```
其對應 `es` 、 `as` 變數結構如下。可看到變數 `x` 的 `expr` 結構被加入至 `es` 變數結構的 `buf[1]` 成員。
* 執行 587-683 程式區塊的 600-682 行: 代表是函數、巨集或 `$` 開頭的結束右括號
* 執行 603-604 行: 代表還有函數或巨集的引數 (argument) 在 `es` 變數結構中，必須將之移除並新增至 `expr_arg` 結構。
```
(gdb) p es
$245 = {
buf = 0x84072d0,
len = 2,
cap = 2
}
(gdb) p arg.eslen
$246 = 1
(gdb) s
604 vec_push(&arg.args, vec_pop(&es));
(gdb) s
vec_expand (buf=0x7ffffffee148, length=0x7ffffffee150, cap=0x7ffffffee154,
memsz=40) at expression.h:37
37 if (*length + 1 > *cap) {
(gdb) finish
Run till exit from #0 vec_expand (buf=0x7ffffffee148, length=0x7ffffffee150,
cap=0x7ffffffee154, memsz=40) at expression.h:37
0x00000000080032a8 in expr_create (s=0x8004ae9 "", len=0, vars=0x7ffffffee2e0,
funcs=0x8206020 <user_funcs>) at expression.c:604
604 vec_push(&arg.args, vec_pop(&es));
Value returned is $247 = 0
(gdb) p es
$248 = {
buf = 0x84072d0,
len = 1,
cap = 2
}
(gdb) p arg
$249 = {
oslen = 3,
eslen = 1,
args = {
buf = 0x84073e0,
len = 2,
cap = 2
}
}
(gdb) p as
$250 = {
buf = 0x84072b0,
len = 0,
cap = 1
}
(gdb) p arg.args.buf[0]
$255 = {
type = 25,
param = {
num = {
value = 2
},
var = {
value = 0x40000000
},
op = {
args = {
buf = 0x40000000,
len = 0,
cap = 0
}
},
func = {
f = 0x40000000,
args = {
buf = 0x0,
len = 0,
cap = 0
},
context = 0x0
}
}
}
(gdb) p arg.args.buf[1]
$256 = {
type = 26,
param = {
num = {
value = 5.79123455e-34
},
var = {
value = 0x8407260
},
op = {
args = {
buf = 0x8407260,
len = 0,
cap = 0
}
},
func = {
f = 0x8407260,
args = {
buf = 0x0,
len = 0,
cap = 0
},
context = 0x0
}
}
}
(gdb) p os
$258 = {
buf = 0x8407390,
len = 1,
cap = 4
}
```
其對應 `es` 、 `as` 與 `arg` 變數結構如下。可看到變數 `x` 的 `expr` 結構被加入至 `arg` 變數結構的 `args` 成員，並從 `es` 變數結構移除。
其對應 `os` 與 `str` 變數結構如下。
* 執行 667-679 行:
```
(gdb) s
667 struct expr_func *f = expr_func(funcs, str.s, str.n);
(gdb) s
expr_func (funcs=0x8206020 <user_funcs>, s=0x8004ae0 "add(2, x)", len=3)
at expression.c:154
154 for (struct expr_func *f = funcs; f->name; f++) {
(gdb) finish
Run till exit from #0 expr_func (funcs=0x8206020 <user_funcs>,
s=0x8004ae0 "add(2, x)", len=3) at expression.c:154
0x0000000008003abc in expr_create (s=0x8004ae9 "", len=0, vars=0x7ffffffee2e0,
funcs=0x8206020 <user_funcs>) at expression.c:667
667 struct expr_func *f = expr_func(funcs, str.s, str.n);
Value returned is $262 = (struct expr_func *) 0x8206020 <user_funcs>
(gdb) s
668 struct expr bound_func = expr_init();
(gdb) s
669 bound_func.type = OP_FUNC;
(gdb) s
670 bound_func.param.func.f = f;
(gdb) s
671 bound_func.param.func.args = arg.args;
(gdb) s
672 if (f->ctxsz > 0) {
(gdb) s
679 vec_push(&es, bound_func);
(gdb) s
vec_expand (buf=0x7ffffffee0f0, length=0x7ffffffee0f8, cap=0x7ffffffee0fc,
memsz=40) at expression.h:37
37 if (*length + 1 > *cap) {
(gdb) finish
Run till exit from #0 vec_expand (buf=0x7ffffffee0f0, length=0x7ffffffee0f8,
cap=0x7ffffffee0fc, memsz=40) at expression.h:37
0x0000000008003ba3 in expr_create (s=0x8004ae9 "", len=0, vars=0x7ffffffee2e0,
funcs=0x8206020 <user_funcs>) at expression.c:679
679 vec_push(&es, bound_func);
Value returned is $263 = 0
(gdb) s
683 paren_next = EXPR_PAREN_FORBIDDEN;
(gdb) p es
$267 = {
buf = 0x84072d0,
len = 2,
cap = 2
}
(gdb) p os
$268 = {
buf = 0x8407390,
len = 1,
cap = 4
}
(gdb) p as
$269 = {
buf = 0x84072b0,
len = 0,
cap = 1
}
(gdb) p es.buf[0]
$270 = {
type = 23,
param = {
num = {
value = 5.79133006e-34
},
var = {
value = 0x8407330
},
op = {
args = {
buf = 0x8407330,
len = 2,
cap = 2
}
},
func = {
f = 0x8407330,
args = {
buf = 0x200000002,
len = 0,
cap = 0
},
context = 0x0
}
}
}
(gdb) p es.buf[1]
$271 = {
type = 27,
param = {
num = {
value = 4.8261243e-34
},
var = {
value = 0x8206020 <user_funcs>
},
op = {
args = {
buf = 0x8206020 <user_funcs>,
len = 138441696,
cap = 0
}
},
func = {
f = 0x8206020 <user_funcs>,
args = {
buf = 0x84073e0,
len = 2,
cap = 2
},
context = 0x0
}
}
}
```
其對應 `es` 變數結構如下。可看到 es 變數結構有兩個 `struct expr` 結構，分別代表 `x = 40` 與 `add(2, x)` 這兩個表示式。
**所有字元都已經解析完畢，故跳出 502 行 `for (;;) {` 迴圈**:
* 執行 735-743 程式區塊的 740 行 `if (expr_bind(rest.s, rest.n, &es) == -1) {`，將 `es` 變數結構的兩個 `struct expr` 合併成一個 `struct expr` (此 `struct expr` 的運算子以 `os` 變數結構的運算子為主)
```
...
(gdb) s
735 while (vec_len(&os) > 0) {
(gdb) s
736 struct expr_string rest = vec_pop(&os);
(gdb) s
737 if (rest.n == 1 && (*rest.s == '(' || *rest.s == ')')) {
(gdb) p rest
$289 = {
s = 0x8004ade ", add(2, x)",
n = 1
}
(gdb) s
740 if (expr_bind(rest.s, rest.n, &es) == -1) {
(gdb) s
expr_bind (s=0x8004ade ", add(2, x)", len=1, es=0x7ffffffee0f0)
at expression.c:389
389 {
(gdb) finish
Run till exit from #0 expr_bind (s=0x8004ade ", add(2, x)", len=1,
es=0x7ffffffee0f0) at expression.c:389
0x000000000800430a in expr_create (s=0x8004ae9 "", len=0, vars=0x7ffffffee2e0,
funcs=0x8206020 <user_funcs>) at expression.c:740
740 if (expr_bind(rest.s, rest.n, &es) == -1) {
Value returned is $290 = 0
(gdb) p es
$291 = {
buf = 0x84072d0,
len = 1,
cap = 2
}
(gdb) p es.buf[0]
$292 = {
type = 24,
param = {
num = {
value = 5.79145495e-34
},
var = {
value = 0x8407440
},
op = {
args = {
buf = 0x8407440,
len = 2,
cap = 2
}
},
func = {
f = 0x8407440,
args = {
buf = 0x200000002,
len = 0,
cap = 0
},
context = 0x0
}
}
}
```
其對應 `es` 變數結構如下。仔細看一下 `struct expr` 分佈圖，此結構是 `tree` 結構 (如同 [H07: kcalc](https://hackmd.io/@sysprog/linux2020-kcalc) 作業提及)。
* 執行 746-752 程式區塊的 750 行: `*result = vec_pop(&es);`，即把 `es` 變數結構的最後一個 `struct expr` 內容值複製到 `result`，並把該元素 (buf 元素) 移除。依據上圖，`es` 只有一個 buf 元素 (buf[0])。換言之，把 `tree` 的頂點元素 (strcut expr) 取出來並複製至 `result`，最後回傳 `result` 位址。
```cpp
480 struct expr *expr_create(const char *s, size_t len,
481 struct expr_var_list *vars, struct expr_func *funcs)
482 {
...
745 result = (struct expr *)calloc(1, sizeof(struct expr));
746 if (result) {
747 if (vec_len(&es) == 0) {
748 result->type = OP_CONST;
749 } else {
750 *result = vec_pop(&es);
751 }
752 }
753
754 int i, j;
755 struct macro m;
756 struct expr e;
757 struct expr_arg a;
758 cleanup:
759 vec_foreach(¯os, m, i)
760 {
761 struct expr e;
762 vec_foreach(&m.body, e, j) { expr_destroy_args(&e); }
763 vec_free(&m.body);
764 }
765 vec_free(¯os);
766
767 vec_foreach(&es, e, i) { expr_destroy_args(&e); }
768 vec_free(&es);
769
770 vec_foreach(&as, a, i)
771 {
772 vec_foreach(&a.args, e, j) { expr_destroy_args(&e); }
773 vec_free(&a.args);
774 }
775 vec_free(&as);
776
777 /*vec_foreach(&os, o, i) {vec_free(&m.body);}*/
778 vec_free(&os);
779 return result;
780 }
```
**呼叫 expr_eval(struct expr \*e) 函數**: `struct expr` 結構樹在 `expr_create()`建構完畢後，便呼叫 `expr_eval()` 遞迴地解析每一個 `struct expr` 結構。如底下 `test.simple.c` 為例，呼叫 `expr_eval(e)` 便能遞迴地解析每一個 `struct expr` 結構，並將回傳計算結果。
```cpp
1 #include "expression.h"
2
3 #include <stdio.h>
4 #include <string.h>
5
6 /* Custom function that returns the sum of its two arguments */
7 static float add(struct expr_func *f, vec_expr_t args, void *c)
8 {
9 float a = expr_eval(&vec_nth(&args, 0));
10 float b = expr_eval(&vec_nth(&args, 1));
11 return a + b;
12 }
13
14 static struct expr_func user_funcs[] = {
15 { "add", add, 0 },
16 { NULL, NULL, 0 },
17 };
18
19 int main()
20 {
21 const char *s = "x = 40, add(2, x)";
22 struct expr_var_list vars = { 0 };
23 struct expr *e = expr_create(s, strlen(s), &vars, user_funcs);
24 if (!e) {
25 printf("Syntax error");
26 return 1;
27 }
28
29 float result = expr_eval(e);
30 printf("result: %f\n", result);
31
32 expr_destroy(e, &vars);
33 return 0;
34 }
```
當執行完畢 test-simple.c:23 後，其對應的 `struct expr` 樹狀結構如下所示:
搭配底下 `expr_eval()` 程式碼 (只列出本範例會執行部分)。
```cpp
198 float expr_eval(struct expr *e)
199 {
200 float n;
201 switch (e->type) {
...
279 case OP_ASSIGN:
280 n = expr_eval(&e->param.op.args.buf[1]);
281 if (vec_nth(&e->param.op.args, 0).type == OP_VAR) {
282 *e->param.op.args.buf[0].param.var.value = n;
283 }
284 return n;
285 case OP_COMMA:
286 expr_eval(&e->param.op.args.buf[0]);
287 return expr_eval(&e->param.op.args.buf[1]);
288 case OP_CONST:
289 return e->param.num.value;
290 case OP_VAR:
291 return *e->param.var.value;
292 case OP_FUNC:
293 return e->param.func.f->f(
294 e->param.func.f, e->param.func.args, e->param.func.context);
295 default:
296 return NAN;
297 }
298 }
```
搭配上圖的 `struct expr` 樹狀結構，分析如下:
1. e->type = 24 (OP_COMMA): 執行 285-287 程式區塊，並把再次呼叫 `expr_eval()` 並將 `e->param.op.args.buf[0]` 位址傳入該函數。
```
...
(gdb) s
expr_eval (e=0x84074a0) at expression.c:201
201 switch (e->type) {
(gdb) p e
$309 = (struct expr *) 0x84074a0
(gdb) p *e
$310 = {
type = 24,
param = {
num = {
value = 5.79145495e-34
},
var = {
value = 0x8407440
},
op = {
args = {
buf = 0x8407440,
len = 2,
cap = 2
}
},
func = {
f = 0x8407440,
args = {
buf = 0x200000002,
len = 0,
cap = 0
},
context = 0x0
}
}
}
(gdb) s
286 expr_eval(&e->param.op.args.buf[0]);
```
2. e->type = 23 (OP_ASSIGN): 執行 279-284 程式區塊。呼叫 `expr_eval()` 並將 `e->param.op.args.buf[1]` 位址傳入該函數 (即 e->type = OP_CONST 且 num.value = 40 的 `struct expr` 結構)。
```
(gdb) s
expr_eval (e=0x8407440) at expression.c:201
201 switch (e->type) {
(gdb) p e->type
$311 = 23
(gdb) s
280 n = expr_eval(&e->param.op.args.buf[1]);
```
3. e->type = 25 (OP_CONST): 執行 289 行，即回傳 `e->param.num.value` 內容值，即數值 `40`。
```
(gdb) s
expr_eval (e=0x8407358) at expression.c:201
201 switch (e->type) {
(gdb) p *e
$313 = {
type = 25,
param = {
num = {
value = 40
},
var = {
value = 0x42200000
},
op = {
args = {
buf = 0x42200000,
len = 0,
cap = 0
}
},
func = {
f = 0x42200000,
args = {
buf = 0x0,
len = 0,
cap = 0
},
context = 0x0
}
}
}
(gdb) s
289 return e->param.num.value;
```
4. e->type = 23 (OP_ASSIGN) 且 n = 40: 執行 281 行。因 `e->param.op.args.buf[0].type = OP_VAR`，故將數值 `40` 存入 `struct expr_var` 結構的 `value` 成員，如下圖所示 (圖中左下角紅色框處)，且可搭配底下 gdb 除錯訊息:
```
(gdb) s
298 }
(gdb) s
281 if (vec_nth(&e->param.op.args, 0).type == OP_VAR) {
(gdb)
(gdb) s
282 *e->param.op.args.buf[0].param.var.value = n;
(gdb) p n
$314 = 40
(gdb) p *e->param.op.args.buf[0].param.var.value
$316 = 0
(gdb) s
284 return n;
(gdb) p *e->param.op.args.buf[0].param.var.value
$317 = 40
```
5. 執行逗號運算子右邊算式 `add(2, x)`: 程式回到 287 行，再次呼叫 `expr_eval()` 並將 `e->param.op.args.buf[1]` 位址傳入該函數。
```
(gdb) s
298 }
(gdb) s
expr_eval (e=0x84074a0) at expression.c:287
287 return expr_eval(&e->param.op.args.buf[1]);
(gdb) s
expr_eval (e=0x8407468) at expression.c:201
201 switch (e->type) {
(gdb) p e->type
$1 = 27
```
6. e->type = 27 (OP_FUNC): 執行 293 行函數呼叫 `return e->param.func.f->f(e->param.func.f, e->param.func.args, e->param.func.context);`
```
(gdb) p e->type
$1 = 27
(gdb) s
293 return e->param.func.f->f(
```
7. 呼叫 test-simple.c: 7 的 `add()``: 再次呼叫 `expr_eval` 把 `func.args` 的兩個引數值取出來。
```cpp
7 static float add(struct expr_func *f, vec_expr_t args, void *c)
8 {
9 float a = expr_eval(&vec_nth(&args, 0));
10 float b = expr_eval(&vec_nth(&args, 1));
11 return a + b;
12 }
```
7.1 解析第一個引數 `struct expr` 的 e->type = 25 (OP_CONST): 執行 289 行，即回傳 `e->param.num.value` 內容值，即數值 `2`，故 `a` 變數為 2。
```
(gdb) s
add (f=0x8206020 <user_funcs>, args=..., c=0x0) at test-simple.c:9
9 float a = expr_eval(&vec_nth(&args, 0));
(gdb) s
expr_eval (e=0x84073e0) at expression.c:201
201 switch (e->type) {
(gdb) p *e
$4 = {
type = 25,
param = {
num = {
value = 2
},
var = {
value = 0x40000000
},
op = {
args = {
buf = 0x40000000,
len = 0,
cap = 0
}
},
func = {
f = 0x40000000,
args = {
buf = 0x0,
len = 0,
cap = 0
},
context = 0x0
}
}
}
(gdb) s
289 return e->param.num.value;
(gdb) s
add (f=0x8206020 <user_funcs>, args=..., c=0x0) at test-simple.c:10
10 float b = expr_eval(&vec_nth(&args, 1));
(gdb) p a
$5 = 2
```
7.2 解析第二個引數 `struct expr` 的 e->type = 26 (OP_VAR): 執行 291 行，即回傳 `*e->param.var.value` 內容值，即數值 `40`，故 `b` 變數為 2。
```
(gdb) f
#0 add (f=0x8206020 <user_funcs>, args=..., c=0x0) at test-simple.c:10
10 float b = expr_eval(&vec_nth(&args, 1));
(gdb) s
expr_eval (e=0x8407408) at expression.c:201
201 switch (e->type) {
(gdb) p *e
$7 = {
type = 26,
param = {
num = {
value = 5.79123455e-34
},
var = {
value = 0x8407260
},
op = {
args = {
buf = 0x8407260,
len = 0,
cap = 0
}
},
func = {
f = 0x8407260,
args = {
buf = 0x0,
len = 0,
cap = 0
},
context = 0x0
}
}
}
(gdb) p *e->param.var.value
$9 = 40
(gdb) s
291 return *e->param.var.value;
(gdb) s
298 }
(gdb) s
add (f=0x8206020 <user_funcs>, args=..., c=0x0) at test-simple.c:11
11 return a + b;
(gdb) p b
$10 = 40
```
8. 所有 `struct expr` 結構樹解析完畢: 執行 test-simple.c: 30 的 `printf`，將其結果輸出 `result: 42.000000`。
```
(gdb) s
12 }
(gdb) s
expr_eval (e=0x8407468) at expression.c:298
298 }
(gdb) s
298 }
(gdb) s
main () at test-simple.c:30
30 printf("result: %f\n", result);
(gdb) s
__printf (format=0x8004af7 "result: %f\n") at printf.c:28
28 printf.c: No such file or directory.
(gdb) finish
Run till exit from #0 __printf (format=0x8004af7 "result: %f\n") at printf.c:28
result: 42.000000
```
終於可以回答 `MathEx 如何解析給定字串，從而分離出變數和對應數學表示法呢？`。從上述 `gdb` 訊息並搭配圖文解說，解釋如下:
* `分離出變數`: 在 `expr_create()->expr_next_token()` 先找到該變數的名稱 (或稱token)，並為該變數建立一個 `struct expr` (type: OP_VAR) 與建立一個 `struct expr_var` (該結構保存變數名稱與變數內容值)，最後藉由 `(struct expr).param.var.value` 將這兩個結構連結在一起。事實上，是將 `(struct expr_var).value` 的位址指定給(struct expr).param.var.value。如底下 expression.c: 430 `expr_varref()` 程式碼所示:
```cpp
430 static struct expr expr_varref(struct expr_var *v)
431 {
432 struct expr e = expr_init();
433 e.type = OP_VAR;
434 e.param.var.value = &v->value;
435 return e;
436 }
```
* `對應數學表示法`: 將 test-simple.c 字串改為底下。
```diff
diff --git a/test-simple.c b/test-simple.c
index 36b9dd5..4dfc5ea 100644
--- a/test-simple.c
+++ b/test-simple.c
@@ -18,7 +18,7 @@ static struct expr_func user_funcs[] = {
int main()
{
- const char *s = "x = 40, add(2, x)";
+ const char *s = "xyz = 4 + 5, xyz = xyz + 8";
struct expr_var_list vars = { 0 };
struct expr *e = expr_create(s, strlen(s), &vars, user_funcs);
if (!e) {
```
使用 `gdb` 把程式碼停在 expression.c: 745
```
(gdb) b expression.c:745
Breakpoint 1 at 0x4321: file expression.c, line 745.
(gdb) r
Starting program: /home/adrian/archive/jserv/linux2020/MathEX/build/test-simple
Breakpoint 1, expr_create (s=0x8004af2 "", len=0, vars=0x7ffffffee2e0,
funcs=0x8206020 <user_funcs>) at expression.c:745
745 result = (struct expr *)calloc(1, sizeof(struct expr));
(gdb) p es
$1 = {
buf = 0x8407360,
len = 1,
cap = 4
}
```
* 觀察第一個運算式 `xyz = 4 + 5`: 其對應的 `es.buf[0].param.op.args.buf[0]` 結構樹如下所式。可看出 `struct expr` (type = OP_VAR) 屬於 `xyz` 變數。`4 + 5` 數學表示式則由 `struct expr` (type = OP_PLUS) 結構樹表示，可以看出兩個子節點都為 `struct expr` (type = OP_CONST)。
* 觀察第二個運算式 `xyz = xyz + 8`: 其對應的 `es.buf[0].param.op.args.buf[1]` 結構樹如下所式。
綜合上述討論，由 `expr_create()` 建構出 `struct expr` 結構樹，並搭配 `expr_eval()`，針對不同的運算子操作，便能分離出變數和對應數學表示法。
## 在 `MathEx` 中，`nop` 一類使用者自訂的函數如何實作呢？
使用者將自訂函數宣告為 `expr_func` 陣列，如下所示 (test-unit.c):
```cpp
160 static struct expr_func user_funcs[] = {
161 { "nop", user_func_nop, user_func_nop_cleanup,
162 sizeof(struct nop_context) },
163 { "add", user_func_add, NULL, 0 }, { "next", user_func_next, NULL, 0 },
164 { "print", user_func_print, NULL, 0 }, { NULL, NULL, NULL, 0 },
165 };
```
在呼叫 `expr_create()` 時，將此 `struct expr_func` 陣列 `user_funcs` 傳入該函數中。當 `expr_create()` 解析字串時，比對 token 名稱跟自訂函數名字相同的話，會建立一個 `struct expr` (type = OP_FUNC) 結構，並在 `expr_eval()` 呼叫對應的函數。
**以 test-unit.c:312 的程式碼 `test_expr("nop()", 0);`**: `gdb` 除錯訊息如下所示，可看 `es` 結構樹已建立完成。
```
(gdb) b expression.c:731
Breakpoint 1 at 0x5806: file expression.c, line 731.
(gdb) r
Starting program: /home/adrian/archive/jserv/linux2020/MathEX/build/test-unit
Breakpoint 1, expr_create (s=0x8006490 "", len=0, vars=0x7ffffffee2b8,
funcs=0x8208020 <user_funcs>) at expression.c:731
731 if (idn > 0) {
(gdb) s
735 while (vec_len(&os) > 0) {
(gdb) p es
$1 = {
buf = 0x84092d0,
len = 1,
cap = 1
}
(gdb) p es.buf[0]
$2 = {
type = 27,
param = {
num = {
value = 4.82988588e-34
},
var = {
value = 0x8208020 <user_funcs>
},
op = {
args = {
buf = 0x8208020 <user_funcs>,
len = 0,
cap = 0
}
},
func = {
f = 0x8208020 <user_funcs>,
args = {
buf = 0x0,
len = 0,
cap = 0
},
context = 0x84092b0
}
}
}
```
其對應的 `es` 結構樹如下所示:
## 是否發現 `MathEx` 對於負數的除法結果不正確、乘法和加法的 overflow 沒有做處理，且缺乏對減法的 underflow 處理機制呢？你預計如何克服？
### 除法: 被除數為負數，運算結果錯誤
底下為被除數為負數的範例，其運算結果不正確。
```
$ echo -ne "-4.5/0.25" > /dev/calc
$ dmesg | tail
calc: Received 9 -> -4.5/0.25
calc: Result: -1312209288
calc: Device successfully closed
$ fromfixed -1312209288
-.82013081000000000000
```
其主要原因為 divid() 的 while 迴圈預設 n1 為正數，n1 為負數則導致計算錯誤。
```cpp
static int divid(int a, int b)
{
int frac1 = GET_FRAC(a);
int frac2 = GET_FRAC(b);
int n1 = GET_NUM(a);
int n2 = GET_NUM(b);
if (n1 == 0 && n2 == 0)
return NAN_INT;
if (n2 == 0)
return INF_INT;
while (n1 * 10 < ((1 << 25) - 1)) {
--frac1;
n1 *= 10;
}
int n3 = n1 / n2;
int frac3 = frac1 - frac2;
return FP2INT(n3, frac3);
}
```
直覺的解法把 'n1' 與 'n2' 做負數運算，確保 n1 為正數，如下所示 ([github patch](https://github.com/AdrianHuang/kcalc/commit/902235ab271971a81403f9deb0fcb900ee6d4c18)):
```diff
diff --git a/expression.c b/expression.c
index 6922987..d5460e7 100644
--- a/expression.c
+++ b/expression.c
@@ -214,6 +214,10 @@ static int divid(int a, int b)
return NAN_INT;
if (n2 == 0)
return INF_INT;
+ if (n1 < 0) {
+ n1 = ~n1 + 1; /* Equal to: n1 = -n1; */
+ n2 = ~n2 + 1;
+ }
while (n1 * 10 < ((1 << 25) - 1)) {
--frac1;
```
### 乘法 overflow
乘法 overflow 偵測分兩部分:
* Integer 欄位 overflow 偵測: 此判斷式 `n3 > (n3 << 4)` 偵測是否 overflow。當然，也可用 `n3 / n1 == n2`，但此判斷式沒有考慮到此定點數的整數部分只佔 28 位元，如果要使用此方法需做另外處理。
* Fraction 欄位 overflow 偵測
其對應修正 [patch](https://github.com/AdrianHuang/kcalc/commit/3cfe290893b150279ee0300eb264bbd302f69f6f) 如下:
```diff
@@ -201,7 +203,22 @@ static int mult(int a, int b)
int n2 = GET_NUM(b);
int n3 = n1 * n2;
- return FP2INT(n3, (frac1 + frac2));
+ /* Check if the integer field is overflowed. */
+ if (n3 > (n3 << 4)) {
+ printk("Overflow detected for integer field!\n");
+ return NAN_INT;
+ }
+
+ int res = FP2INT(n3, (frac1 + frac2));
+ int res_frac = GET_FRAC(res);
+
+ /* Only need to care about the fraction with the negative number. */
+ if (frac1 < 0 && frac2 < 0 && res_frac > 0) {
+ printk("Overflow detected for fraction field!\n");
+ return NAN_INT;
+ }
+
+ return res;
}
```
四個驗證測試:
* 72444*1852: 沒有 integer overflow，故得出正確值 (134166288)。
* 72444*1853: 發生 integer overflow，印出 'Overflow detected for integer field!'，並回傳 NAN_INT。
* 0.123456*0.01: 沒有 fraction overflow，故得出正確值 (.00123456000000000000)。
* 0.123456*0.001: 發生 fraction overflow，印出 'Overflow detected for fraction field!'，並回傳 NAN_INT。
```
$ echo -ne "72444*1852\0" > /dev/calc && dmesg | tail -n 3
calc: Received 11 -> 72444*1852
calc: Result: 2146660608
calc: Device successfully closed
$ fromfixed 2146660608
134166288
$ echo -ne "72444*1853\0" > /dev/calc && dmesg | tail -n 4
calc: Received 11 -> 72444*1853
Overflow detected for integer field!
calc: Result: 31
calc: Device successfully closed
$ echo -ne "0.123456*0.01\0" > /dev/calc && dmesg | tail -n 3
calc: Received 14 -> 0.123456*0.01
calc: Result: 1975304
calc: Device successfully closed
$ fromfixed 1975304
.00123456000000000000
$ echo -ne "0.123456*0.001\0" > /dev/calc && dmesg | tail -n 4
calc: Received 15 -> 0.123456*0.001
Overflow detected for fraction field!
calc: Result: 31
calc: Device successfully closed
```
### 加法 overflow
加法 overflow 偵測，跟乘法一樣，使用判斷式 `n3 > (n3 << 4)` 偵測是否 overflow。其對應 [patch](https://github.com/AdrianHuang/kcalc/commit/df4a803ddc9aaea05406f15830122aa762017e65) 如下:
```diff
diff --git a/expression.c b/expression.c
index 5345cb5..6d31aa2 100644
--- a/expression.c
+++ b/expression.c
@@ -328,6 +328,12 @@ static int plus(int a, int b)
n1 += n2;
+ /* Check if the integer field is overflowed. */
+ if (n1 > (n1 << 4)) {
+ printk("Overflow detected for integer field!\n");
+ return NAN_INT;
+ }
+
return FP2INT(n1, frac1);
}
```
其驗證如下 (注意: 134217727 為 28-bit integer field 最大正整數):
```
$ echo -ne "134217726 + 1\0" > /dev/calc && dmesg | tail -n 4
[505364.641716] calc: Device successfully closed
[505413.060386] calc: Received 14 -> 134217726 + 1
[505413.060393] calc: Result: 2147483632
[505413.060397] calc: Device successfully closed
$ fromfixed 2147483632
134217727
$ echo -ne "134217726 + 2\0" > /dev/calc && dmesg | tail -n 4
[505430.976430] calc: Received 14 -> 134217726 + 2
[505430.976437] Overflow detected for integer field!
[505430.976438] calc: Result: 31
[505430.976442] calc: Device successfully closed
```
### 減法 underflow
[Under Construction]
# 作業要求
## 測試環境
```shell
$ cat /etc/os-release
NAME="Ubuntu"
VERSION="18.04.4 LTS (Bionic Beaver)"
$ cat /proc/version
Linux version 5.7.0-050700-generic (kernel@tangerine) (gcc version 9.3.0 (Ubuntu 9.3.0-13ubuntu1), GNU ld (GNU Binutils for Ubuntu) 2.34) #202005312130 SMP Mon Jun 1 01:33:12 UTC 2020
$ lscpu
Architecture: x86_64
CPU op-mode(s): 32-bit, 64-bit
Byte Order: Little Endian
CPU(s): 72
On-line CPU(s) list: 0-71
Thread(s) per core: 2
Core(s) per socket: 18
Socket(s): 2
NUMA node(s): 2
Vendor ID: GenuineIntel
CPU family: 6
Model: 79
Model name: Intel(R) Xeon(R) CPU E5-2695 v4 @ 2.10GHz
Stepping: 1
CPU MHz: 1769.935
CPU max MHz: 2100.0000
CPU min MHz: 1200.0000
BogoMIPS: 4199.81
Virtualization: VT-x
L1d cache: 32K
L1i cache: 32K
L2 cache: 256K
L3 cache: 46080K
NUMA node0 CPU(s): 0-17,36-53
NUMA node1 CPU(s): 18-35,54-71
$ free -h
total used free shared buff/cache available
Mem: 125G 1.3G 82G 2.9M 41G 122G
Swap: 0B 0B 0B
```
## Bug Fixes
1. 執行 `make check`，出現錯誤訊息 `rmmod: ERROR: Module livepatch_calc is in use`
錯誤訊息如下:
```
$ make check
...
Testing nop() ...
0
[3358338.123572] calc: Received 6 -> nop()
[3358338.123578] livepatch_calc: function nop is now patched
[3358338.123581] calc: Result: 0
[3358338.123584] calc: Device successfully closed
[3358338.124581] calc: size: 2 result: 0
[3358338.124602] calc: Device successfully closed
Disabling livepatch...
rmmod: ERROR: Module livepatch_calc is in use
Complete
```
觀察關閉 livepatch_calc 共花費 4 秒鐘，但 `scripts/test.sh` 只等待 2 秒鐘。
```
Jul 14 15:30:47 adrian-ubuntu kernel: [3359642.034720] livepatch: 'livepatch_calc': starting unpatching transition
Jul 14 15:30:51 adrian-ubuntu kernel: [3359646.179160] livepatch: 'livepatch_calc': unpatching complete
```
對應修正: 一直等待資料夾 `/sys/kernel/livepatch/livepatch_calc` 被移除，修正提交 commit [c36b9ed2a39e](https://github.com/AdrianHuang/kcalc/commit/c36b9ed2a39e63e3a7176c0344acf5c5d9dceba8)。
2. [Kernel] Call Trace - "use-after-free reference count"
執行 `sudo rmmod calc`，有時候會出現底下核心 `call trace`:
```
------------[ cut here ]------------
refcount_t: underflow; use-after-free.
WARNING: CPU: 66 PID: 63879 at lib/refcount.c:28 refcount_warn_saturate+0xae/0xf0
Modules linked in: calc(OE-) nls_utf8 isofs cpuid ipmi_ssif intel_rapl_msr intel_rapl_common sb_edac x86_pkg_temp_thermal intel_powerclamp coretemp kvm_intel cdc_ether usbnet joydev input_leds mii kvm intel_cstate lpc_ich mei_me intel_rapl_perf mei ipmi_si ipmi_devintf ipmi_msghandler mac_hid acpi_power_meter acpi_pad binfmt_misc sch_fq_codel ib_iser rdma_cm iw_cm ib_cm ib_core iscsi_tcp libiscsi_tcp libiscsi scsi_transport_iscsi parport_pc ppdev lp nfsd parport auth_rpcgss nfs_acl lockd grace sunrpc ip_tables x_tables autofs4 btrfs blake2b_generic raid10 raid456 async_raid6_recov async_memcpy async_pq async_xor async_tx xor raid6_pq libcrc32c raid1 raid0 multipath linear hid_generic usbhid hid ses enclosure scsi_transport_sas crct10dif_pclmul crc32_pclmul mgag200 ghash_clmulni_intel drm_vram_helper drm_ttm_helper i2c_algo_bit ttm drm_kms_helper syscopyarea sysfillrect sysimgblt fb_sys_fops aesni_intel cec rc_core ixgbe crypto_simd cryptd glue_helper drm mxm_wmi xfrm_algo tg3 megaraid_sas dca mdio wmi
CPU: 66 PID: 63879 Comm: rmmod Tainted: G OE 5.7.0-050700-generic #202005312130
Hardware name: LENOVO System x3650 M5 -[8871AC1]-/01GR174, BIOS -[TCE140H-2.91]- 06/03/2019
RIP: 0010:refcount_warn_saturate+0xae/0xf0
Code: cf 79 2d 01 01 e8 67 d3 b4 ff 0f 0b 5d c3 80 3d bc 79 2d 01 00 75 91 48 c7 c7 80 50 5f a8 c6 05 ac 79 2d 01 01 e8 47 d3 b4 ff <0f> 0b 5d c3 80 3d 9a 79 2d 01 00 0f 85 6d ff ff ff 48 c7 c7 d8 50
RSP: 0018:ffffb0dc4844fe50 EFLAGS: 00010282
RAX: 0000000000000000 RBX: ffff968c36443a00 RCX: 0000000000000007
RDX: 0000000000000007 RSI: 0000000000000096 RDI: ffff968c3fb99c80
RBP: ffffb0dc4844fe50 R08: 00000000000005fa R09: 0000000000000004
R10: 0000000000000000 R11: 0000000000000001 R12: ffff968c32662c18
R13: 0000000000000000 R14: 0000000000000000 R15: 0000000000000000
FS: 00007fc2fb6a4540(0000) GS:ffff968c3fb80000(0000) knlGS:0000000000000000
CS: 0010 DS: 0000 ES: 0000 CR0: 0000000080050033
CR2: 0000557d53d06118 CR3: 0000001f7288c001 CR4: 00000000003606e0
DR0: 0000000000000000 DR1: 0000000000000000 DR2: 0000000000000000
DR3: 0000000000000000 DR6: 00000000fffe0ff0 DR7: 0000000000000400
Call Trace:
kobject_put+0xfc/0x1c0
kset_unregister+0x1f/0x30
class_unregister+0x2c/0x50
class_destroy+0x1c/0x20
calc_exit+0x31/0xe28 [calc]
__x64_sys_delete_module+0x147/0x2b0
do_syscall_64+0x57/0x1d0
entry_SYSCALL_64_after_hwframe+0x44/0xa9
RIP: 0033:0x7fc2fb1c6367
Code: 73 01 c3 48 8b 0d 21 8b 2c 00 f7 d8 64 89 01 48 83 c8 ff c3 66 2e 0f 1f 84 00 00 00 00 00 0f 1f 44 00 00 b8 b0 00 00 00 0f 05 <48> 3d 01 f0 ff ff 73 01 c3 48 8b 0d f1 8a 2c 00 f7 d8 64 89 01 48
RSP: 002b:00007fff250c4788 EFLAGS: 00000206 ORIG_RAX: 00000000000000b0
RAX: ffffffffffffffda RBX: 00007fff250c47e8 RCX: 00007fc2fb1c6367
RDX: 0000557d53d037e0 RSI: 0000000000000a00 RDI: 0000557d53d037c8
RBP: 0000557d53d03760 R08: 0000000000000000 R09: 0000000000000000
R10: 0000557d53d03010 R11: 0000000000000206 R12: 00007fff250c49b8
R13: 00007fff250c68e9 R14: 0000557d53d03260 R15: 0000557d53d03760
---[ end trace 5362e040934e367e ]---
calc: Goodbye!
```
詳盡說明請參考 commit [d1fa63d6a0f8](https://github.com/AdrianHuang/kcalc/commit/d1fa63d6a0f81a7c5dd511c4fded56c74054ca16)
## 觀察原始程式碼的 expression.[ch] 裡頭 vec 相關的程式碼，將 quiz4 使用到的技巧予以應用，提出對空間效率更好的實作
### 方法一: 比照 `quiz4` 相關程式碼把結構放在 `stack` (不可行)
在 `vec` 巨集宣告一個 union，其中 `T buf[DEFAULT_VECTOR_ELEMENT_IN_STACK];` 目的在於把此結構放在 `stack`，一旦結構使用量超過 `DEFAULT_VECTOR_ELEMENT_IN_STACK`，則從 heap 分配記憶體空間。但此方法在編譯期間就會出錯。
```cpp
#define STRUCT_BODY(type) \
struct { \
unsigned int len; \
/* cap[31]: on_heap flag */ \
unsigned int cap; \
type *ptr; \
}
#define vec(T) \
union { \
STRUCT_BODY(T); \
struct { \
size_t filler; \
T buf[DEFAULT_VECTOR_ELEMENT_IN_STACK]; \
}; \
}
```
編譯結果顯示 `T` 結構在 `vec()` 之後宣告 (限制於 `struct expr` 結構裡有 `vec_expr_t args;`)，所以編譯器不知道 `T` 結構的大小，所以無法在 `stack` 預留空間。
```
$ make
make -C /lib/modules/5.7.0-050700-generic/build M=/home/adrian/linux2020/kcalc modules
make[1]: Entering directory '/usr/src/linux-headers-5.7.0-050700-generic'
CC [M] /home/adrian/linux2020/kcalc/main.o
In file included from /home/adrian/linux2020/kcalc/main.c:12:0:
/home/adrian/linux2020/kcalc/expression.h:33:15: error: array type has incomplete element type ‘struct expr’
T buf[DEFAULT_VECTOR_ELEMENT_IN_STACK]; \
^
/home/adrian/linux2020/kcalc/expression.h:82:9: note: in expansion of macro ‘vec
’
typedef vec(struct expr) vec_expr_t;
^~~
scripts/Makefile.build:266: recipe for target '/home/adrian/linux2020/kcalc/main.o' failed
make[2]: *** [/home/adrian/linux2020/kcalc/main.o] Error 1
Makefile:1729: recipe for target '/home/adrian/linux2020/kcalc' failed
make[1]: *** [/home/adrian/linux2020/kcalc] Error 2
make[1]: Leaving directory '/usr/src/linux-headers-5.7.0-050700-generic'
Makefile:11: recipe for target 'all' failed
make: *** [all] Error 2
```
除此之外，如果暫時把 `buf` 改成指標陣列，且 `STRCUT_BODY` 用 bit-field 宣告對應的變數 (比照 `quiz4` 方法)。編譯還是會出錯。因為 `vec_unpack()` 對 `len` 與 `cap` 取址，但 bit-field 不能取址，請參考底下錯誤訊息。
```cpp
#define STRUCT_BODY(type) \
struct { \
size_t len : 30, cap: 30, on_heap : 1, flag1 : 1, flag2 : 1, \
flag3 : 1; \
type *ptr; \
}
#define vec(T) \
union { \
STRUCT_BODY(T); \
struct { \
size_t filler; \
T *buf[DEFAULT_VECTOR_ELEMENT_IN_STACK]; \
}; \
}
```
```
$ make
/home/adrian/linux2020/kcalc/expression.h:45:26: error: cannot take address of bit-field ‘len’
(char **) &(v)->buf, &(v)->len, &(v)->cap, sizeof(*(v)->buf)
```
所以，此方法並不適用。
### 方法二: 在 `vector` 初始化階段，預先透過 kmalloc/krealloc 分配多個結構
在 `vector` 結構初始化階段，預先分配多個結構，其 patch 如下所示 (對應 commit [557fa1ca14e2](https://github.com/AdrianHuang/kcalc/commit/557fa1ca14e250977232ffccbe0ee503e0f348bd)):
此方法跟原本設計一樣: 都是從 `heap` 空間取得記憶體空間，但可省去一開始 `vec_push()` 跟作業系統核心要求分配記憶體空間的 overhead。eecheng同學也提出類似想法，且有量測數據，詳見[此篇文章](https://hackmd.io/@eecheng/H1UbfU1PI)。
```diff
diff --git a/expression.c b/expression.c
index 8fa95bb..355b795 100644
--- a/expression.c
+++ b/expression.c
@@ -738,15 +738,15 @@ struct expr *expr_create(const char *s,
struct expr *result = NULL;
- vec_expr_t es = vec_init();
- vec_str_t os = vec_init();
- vec_arg_t as = vec_init();
+ define_vec(vec_expr_t, es);
+ define_vec(vec_str_t, os);
+ define_vec(vec_arg_t, as);
struct macro {
char *name;
vec_expr_t body;
};
- vec(struct macro) macros = vec_init();
+ define_vec(vec(struct macro), macros);
int flags = EXPR_TDEFAULT;
int paren = EXPR_PAREN_ALLOWED;
@@ -819,7 +819,8 @@ struct expr *expr_create(const char *s,
if (paren == EXPR_PAREN_EXPECTED) {
struct expr_string str = {"{", 1};
vec_push(&os, str);
- struct expr_arg arg = {vec_len(&os), vec_len(&es), vec_init()};
+ struct expr_arg arg = {vec_len(&os), vec_len(&es),
+ vec_init(arg.args)};
vec_push(&as, arg);
} else if (paren == EXPR_PAREN_ALLOWED) {
struct expr_string str = {"(", 1};
diff --git a/expression.h b/expression.h
index 6d5b57f..bc47678 100644
--- a/expression.h
+++ b/expression.h
@@ -22,10 +22,18 @@ extern "C" {
int len; \
int cap; \
}
-#define vec_init() \
- { \
- NULL, 0, 0 \
+
+#define PRE_ALLOCATED_VEC_NR 4
+
+#define vec_init(var) \
+ { \
+ (__typeof__(var.buf)) krealloc( \
+ NULL, PRE_ALLOCATED_VEC_NR * sizeof(*var.buf), GFP_KERNEL), \
+ 0, PRE_ALLOCATED_VEC_NR \
}
+
+#define define_vec(v, var) v var = vec_init(var);
+
#define vec_len(v) ((v)->len)
#define vec_unpack(v) \
(char **) &(v)->buf, &(v)->len, &(v)->cap, sizeof(*(v)->buf)
```
## 在 main.c 提供自行定義的 fib() 函式，一開始僅有不完整實作 (可直接回傳 0，一如 nop() 所為)，但在 livepatch 端 (即 livepatch-calc.c) 就該有正確的 Fibonacci 數求值實作 -> 不用考慮大數運算，但仍要留意有效數值範圍和運算效率
實作詳見 [Commit 207f15e31328 ("Support Fibonacci number via livepatch")](https://github.com/AdrianHuang/kcalc/commit/207f15e31328b83622d972acc2260ccf927c403a)。Fibonacci 演算法使用 fast doubling，留意定點數乘法的結果需還原正確定點數的內容值，也就是除以 `1` 的定點數內容值，也就是 `1 << 4`。如下所示。
```cpp
static int fib_sequence_fast_dobuling_clz(int k)
{
int a = 0, b = FIXED_1;
k = GET_NUM(k);
if (!k)
return 0;
for (int i = ilog2(k); i >= 0; i--) {
int t1, t2;
t1 = a * ((b << 1) - a);
t2 = b * b + a * a;
/*
* Reflect the 'correct' fixed-point value by dividing
* FIXED_1 since the 't1' and 't2' calculation involves
* multiplication operator.
*/
a = t1 / FIXED_1;
b = t2 / FIXED_1;
if (k & (1ULL << i)) {
t1 = a + b;
a = b;
b = t1;
}
}
return a;
}
```
驗證結果如下所示，`calc` livepatch 的 fib(19) 運算結果為 `66896`，從定點數還原成整數 `66896 >> 4 = 4181`，符合預期。
```
$ make check
...
Testing nop() ...
-.10000000000000000000
Testing fib(19) ...
-.10000000000000000000
livepatch was applied
Testing nop() ...
0
[109101.847910] calc: Received 6 -> nop()
[109101.847917] livepatch_calc: function nop is now patched
[109101.847920] calc: Result: 0
[109101.847923] calc: Device successfully closed
[109101.848935] calc: size: 2 result: 0
[109101.848955] calc: Device successfully closed
Testing fib(19) ...
4181
[109101.873901] calc: Received 8 -> fib(19)
[109101.873907] livepatch_calc: function fib is now patched
[109101.873909] calc: Result: 66896
[109101.873912] calc: Device successfully closed
[109101.874893] calc: size: 6 result: 66896
[109101.874912] calc: Device successfully closed
Disabling livepatch...
Complete
$ fromfixed 66896
4181
```
## 修正現有 kcalc 內部數值運算的錯誤，並留意到不合法的記憶體操作
測試 fibonacci number 發現 fib(10) 回傳底下錯誤結果
```
Testing fib(10) ...
1
```
重新檢視 FP2INT() 程式碼發現其轉換的定點數內容值不正確，對應的[修正](https://github.com/AdrianHuang/kcalc/commit/946823b51a0c50d1e4340529b1f170fb48e850d4)如下:
```diff
diff --git a/expression.c b/expression.c
index ef9a34f..6922987 100644
--- a/expression.c
+++ b/expression.c
@@ -27,6 +27,9 @@ static int GET_FRAC(int n)
static int FP2INT(int n, int d)
{
+ if (!d)
+ return (n << 4);
+
while (n && n % 10 == 0) {
++d;
n /= 10;
```
修正後的程式碼能正確轉換定點數內容值，且 fib(10) 能計算出正確的值，如下所示:
```
Testing fib(10) ...
55
```
## 指出原本 fixed-point 實作的限制，觀察 Linux 核心所用的 fixed-point 運算程式碼，提出針對 kcalc 的改進方案 -> 避免直接用 int 型態描述，可透過 typedef 來定義 binary32_t 一類的衍生型態
`kcalc` 定點數實作把 32 位元整數規劃成如下格式:
```
| integer | sign | fraction |
Bit 31 3 2 0
```
fraction 是 10 的次方，留意 `sign` 位元指 fraction 為正數或負數 (對比IEEE Standard for Floating-Point Arithmetic - IEEE 754 所定義的 `sign` 位元，其用途大相逕庭)，其對應的公式為 $integer * 10^{(-1)^{sign} * fraction}$。
`sign` + `fraction` 組成四個位元的**有號數整數** (即二補數編碼)，詳見 [解讀計算機編碼](https://hackmd.io/@sysprog/binary-representation)。這就是為何 `FP2INT()` 回傳值有這段描述 `(d & 15)`，且小數點最多支援小數點後八位 (因為四位元二補數編碼數值範圍: `-8 to 7`)。然而，並非所有小數點八位的值都可以正確地表示，主要受限於 28 位元 `integer` 的最大值，可參考底下實驗。
```cpp
static int FP2INT(int n, int d)
{
while (n && n % 10 == 0) {
++d;
n /= 10;
}
if (d == -1) {
n *= 10;
--d;
}
return ((n << 4) | (d & 15));
}
```
對比 `scripts/eval.sh` 的 `frac=$((-((~$frac & 15) + 1)))`，即把四位元有號數的負數，轉換成真實的負數數值，即再做一次 `2補數` 。
```bash
fromfixed() {
local ret=$1
local NAN_INT=31
local INF_INT=47
num=$(($ret >> 4))
frac=$(($ret & 15))
neg=$((($frac & 8) >> 3))
[[ $neg -eq 1 ]] && frac=$((-((~$frac & 15) + 1)))
if [ "$ret" -eq "$NAN_INT" ]
then
echo "NAN_INT"
elif [ "$ret" -eq "$INF_INT" ]
then
echo "INF_INT"
else
echo "$num*(10^$frac)" | bc -l
fi
}
```
實驗一: 宣告底下小數點八位，可以正確表示。
```
test_op 'x=1.12345678'
...
Testing x=1.12345678 ...
1.12345678000000000000
```
實驗二: 宣告底下小數點八位，無法正確表示。其原因為 Bit 31 為 1'。
```
test_op 'x=1.87654321'
...
Testing x=1.87654321 ...
-.80781135000000000000
```
## 原有的測試程式不會檢驗輸出數值，應予以擴充，得以自動和預先輸入的期望數值進行比對
擴充 `scripts/test.sh` 的函式 `test_op()`，新增第二個參數，該參數代表三種型態 ([github patch](https://github.com/AdrianHuang/kcalc/commit/92c36dbc6c26db22492d5c337a84f05fa4966d3d)):
* native_bash: 支援 `bash` 算術運算子 (Ex: +, -, *, /, &, ^, logical shift 等等)，可傳入 'native_bash'
* do_bc: 由於 `bash` 算術結果不支援浮點運算, 故使用 `bc` 計算浮點數。
* 直接帶入手動計算結果: 有些算式無法透過 'native_bash' 與 `do_bc` 計算，故直接帶入手動計算結果。
其測試輸出如下:
```shell
$ make check
...
Testing 6*7 ...PASS
Testing 1980+1 ...PASS
Testing 2019-1 ...PASS
Testing 42/6 ...PASS
Testing 1/3 ...PASS
Testing 1/3*6+2/4 ...PASS
Testing (1/3)+(2/3) ...PASS
Testing (2145%31)+23 ...PASS
Testing 0/0 ...PASS
Testing (3%0)|0 ...PASS
Testing 1+2<<3 ...PASS
Testing 123&42 ...PASS
Testing 123^42 ...PASS
Testing (((3)))*(1+(2)) ...PASS
Testing x=5, x=(x!=0) ...PASS
Testing x=5, x = x+1 ...PASS
Testing six=6, seven=7, six*seven ...PASS
Testing 小熊=6, 維尼=7, 小熊*維尼 ...PASS
Testing τ=1.618, 3*τ ...PASS
Testing $(τ, 1.618), 3*τ() ...PASS
Testing $(zero), zero() ...PASS
Testing $(one, 1), one()+one(1)+one(1, 2, 4) ...PASS
Testing $(number, 1), $(number, 2+3), number() ...PASS
Testing nop() ...FAIL (expect_ans: 0, kcal_ans=-.10000000000000000000)
Testing fib(19) ...FAIL (expect_ans: 4181, kcal_ans=-.10000000000000000000)
livepatch was applied
Testing nop() ...PASS
[549304.089808] calc: Received 6 -> nop()
[549304.089814] livepatch_calc: function nop is now patched
[549304.089816] calc: Result: 0
[549304.089819] calc: Device successfully closed
[549304.091243] calc: size: 2 result: 0
[549304.091264] calc: Device successfully closed
Testing fib(19) ...PASS
[549304.161694] calc: Received 8 -> fib(19)
[549304.161700] livepatch_calc: function fib is now patched
[549304.161701] calc: Result: 66896
[549304.161704] calc: Device successfully closed
[549304.163045] calc: size: 6 result: 66896
[549304.163064] calc: Device successfully closed
Disabling livepatch...
Complete
```
## Reference
[1] [Brendan Gregg's Blog - Linux Load Averages: Solving the Mystery](http://www.brendangregg.com/blog/2017-08-08/linux-load-averages.html)
[2] [Brendan Gregg's Blog - Off-CPU Analysis](http://www.brendangregg.com/offcpuanalysis.html)
[3] [Brendan Gregg's Blog - Off-CPU Flame Graphs](http://www.brendangregg.com/FlameGraphs/offcpuflamegraphs.html)
Google Drive
Gist
Clipboard
Sign in with Wallet
