# 2019q1 Homework2 (kcalc)
contributed by < `rebvivi` >
###### tags: `linux2019`
* [F04: kcalc](https://hackmd.io/s/SyC9V0gUE#F04-kcalc)

Reviewed by <`jserv`>
1. 提及 `if (0.1 + 0.2 == 0.3)` 判斷式不成立，但沒有說到浮點數值運算的解決方法，請提出; (考慮到計算誤差)
2. 尚未用 Linux 程式碼解釋 `Lazy context switch` 原理和運作機制;
3. 探討 `register_chrdev` vs. `alloc_chrdev_region` 時，僅列出 API 差異，但沒有詳細探討應用場景和考量點的落差
4. 下方提到「如果使用`copy_to_user`時，要複製的資料量太大，就會讓 buffer 產生 overflow，導致效能降低」，那解決方案為何？請舉出 Linux 核心的案例 (最好列出對應的 Git commits)
5. 下方提到的 `fixed point arithmetic`，實際可完整表達的數值範圍為何？既然精準度下降了，那麼我們更需要知道衝擊，可參考 CS:APP 第 2 章的分析方法

---

## 作業要求
- 回答「自我檢查清單」的所有問題，需要附上對應的參考資料和必要的程式碼，以第一手材料 (包含自己設計的實驗) 為佳
- 在 GitHub 上 fork kcalc，主要目標是將 MathEx 整合到 calc.c 中 (作為 LKM 的形式)，過程中需要一併完成以下:
* 將 MathEx 的浮點數運算換為 fixed point，應該先在使用者層級驗證，然後再搬到 Linux 核心中。可斟酌移除 MathEx 裡頭的功能，但需要充分解釋;
* 量化 MathEx 在核心的執行時間，搭配 fibdrv 撰寫的工具程式使用;
* 設計 micro-benchmarking 實驗，用以驗證 MathEx 移植到 Linux 核心後的表現;
* 嘗試解讀上述時間分佈，特別是隨著 Fibonacci 數列增長後，對於 Linux 核心的影響;
* 改善 MathEx 的執行效率;
* 請善用 perf 一類地效能分析工具;

## 自我檢查清單
1. 解釋浮點運算在 Linux 核心中為何需要特別對待，以及 context switch 的過程中，涉及到 FPU/SIMD context，該注意什麼？
* 提示: 參照 Lazy FP state restore 和上方參考資料
* 應該撰寫對應包含浮點運算的 Linux 核心模組，實際編譯和測試
2. 在給定的 `calc.c` 檔案中，和 fibdrv 一樣有 character device，但註冊用的 kernel API 不同 (`register_chrdev` vs. `alloc_chrdev_region`)，能否解釋其差異和適用場合呢？
3. 在 `scripts/test.sh` 檔案中，有一道命令為 `sudo chmod 0666`，這個作用為何？對於我們測試有何幫助？能否對 fibdrv 建立的 `/dev/fibonacci` device file 也套用類似修改呢？另外，請解釋 device file 在核心及使用者層級的功能
4. 在 `calc.c` 檔案中，用到 `copy_to_user` 這個 kernel API，其作用為何？本例使用該 API 做了什麼事？若是資料量增長，是否會有效能的嚴重衝擊呢？
5. 找出至少 3 個 Linux 核心中使用定點數的案例，搭配程式碼解說
* 提示: 參照 Linux Kernel Load Average 計算分析
, What Every Computer Scientist Should Know About Floating-Point Arithmetic, Load average explained
6. 是否知曉 `MathEx` 如何解析給定字串，從而分離出變數和對應數學表示法呢？
7. 如何對 `MathEx` 進行效能分析？能否找出相似的 math expression 來分析比較呢？
* 提示: 參照 muparserSSE - A Math Expression Compiler
8. 在 `MathEx` 原始程式碼的 `expression.[ch] `裡頭 `vec` 相關的程式碼，主要做什麼事？有沒有發現類似 list 使用到的技巧呢？
* 提示: 參照 `mathex/test-unit.c` 的測試項目
9. 解釋 `MathEx` 一類的 math expression 在真實世界有哪些應用？甚至，是否在 Linux 核心就存在類似的程式碼？
* 提示: 參照 A thorough introduction to eBPF
10. 如果要將使用者層級的 C 語言程式，搬到 Linux 核心作為核心模組 (LKM)，該注意哪些議題呢？請舉例說明
* 提示: 注意 `__KERNEL__` 巨集的定義, kmalloc 的使用, vmalloc 的使用 (以及後兩者的差異)
11. fixed point arithmetic for RT-Linux 的運作原理為何？給定的程式碼已經存在超過 20 年，很多細節已有出入，可否嘗試移植到 Linux `v4.15+` 呢？

### 1. 解釋浮點運算在 Linux 核心中為何需要特別對待，以及 context switch 的過程中，涉及到 FPU/SIMD context，該注意什麼？提示: 參照 Lazy FP state restore 和上方參考資料。應該撰寫對應包含浮點運算的 Linux 核心模組，實際編譯和測試

- 進行浮點數運算的時候，往往會遇到許多問題，例如：
* 輸入與儲存的值不一定精確，可能原因：
* 輸入值本身就不精確
* 儲存浮點數用的記憶體有限
* 不同底數之間的轉換不精確
* 輸入與儲存產生 overflow
* 計算的結果會有誤差：
使用浮點數進行運算時會有上述產生的許多誤差，這些誤差經過反覆而且大量運算之後很有可能會蔓延到其它所在，從而產生不可收拾的後果

- 浮點數容易犯的錯誤：直接用 == 或 != 比較兩個浮點數。
>以下的判斷式是不成立的

if (0.1 + 0.2 == 0.3)

>二進位表示的浮點數並沒有辦法精確儲存 0.1、0.2、0.3 這些十進位實數，只能以最接近的浮點數表示，所以會和原本的數值有微小的誤差
>三個各自帶有誤差的數字要碰巧讓整個等式成立，是非常困難的

- `Floating Point Unit（FPU）`：專用於浮點運算的處理器
- `Single Instruction Multiple Data (SIMD)` : 同時對多個數據執行同一條CPU指令，達到平行運算的目的
- `Lazy context switch`：硬體會先 disable FPU，一直等到 FP 指令被執行的時候才 enable CPU
>每次 context switch 的時候如果 CPU 和 FPU 都要做 context switch 會使系統的 overloading 增大，因為存取 FPU 的 hardware context 需要更多的 CPU time

- 在 context switch 的過程中，如果涉及到 FPU context ，會執行`Lazy context switch`，也就是僅在需要時保存並還原 FPU ，但這可能會面臨一些安全性的問題：
* 可以利用 Lazy FP 狀態還原功能，潛在允許一個 process 從另一個 process 推斷數據
* 推斷到的數據也可能包括已加密操作的信息，這個安全漏洞會影響到CPU的預測執行推測執行機制

### 2. 在給定的 `calc.c` 檔案中，和 fibdrv 一樣有 character device，但註冊用的 kernel API 不同 (`register_chrdev` vs. `alloc_chrdev_region`)，能否解釋其差異和適用場合呢？
- 為了將 device file 與 driver 連起來，driver 必須向 kernel 註冊 major number
- `register_chrdev` : 在 kernel 中註冊字元型的 driver

- 將 driver 自己註冊到 kernel 的 VFS 層，註冊時所要呼叫的函數根據裝置類型的不同而不同
- 將 driver 註冊至 kernel 的動作必須在 init_module() 裡實作
- 註冊的動作是寫在 init_module() 裡，因此當使用者執行 insmod 載入 driver時， register_chrdev() 便會執行

>`major` : 欲請求的 major number
>>如果 major 是0，表示動態的分配給此 driver 一個 major number，如果 major 不是0，表示 driver 向系統申請 major number
>>
>`name` : driver 的名稱
`fops` : 指向 kernel 定義的 file_operations 的 struct 中

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

- `alloc_chrdev_region` : 動態取得 major number ，在 kernel 中註冊字元型的 driver

- 依 driver 名稱用來取得 major number，並從指定的起點開始預留指定數目的 minor number
>`dev`: 僅供輸出的 parameter，當配置成功，這個 parameter 持有配置的 device number
`firstminor`: 請求的 first minor number ，通常為 0
`count`: minor number 個數
`name`: driver 的名稱

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

- `register_chrdev` 除了請求 major number 以外，還一併將 0~255 的 minor number 註冊好，並自動分配了新的 cdev structure ， `alloc_chrdev_region` 的 cdev stucture 成員則可自行增加
- 如果我們提前知道 device driver 的 major number，那麼就用`register_chrdev`,但是如果不知道就使用動態申請 device number

### 3. 在 `scripts/test.sh` 檔案中，有一道命令為 `sudo chmod 0666`，這個作用為何？對於我們測試有何幫助？能否對 fibdrv 建立的 `/dev/fibonacci` device file 也套用類似修改呢？另外，請解釋 device file 在核心及使用者層級的功能
- 在 `scripts/test.sh`中有一道命令：
>`chmod`：控制用戶對檔案的權限的命令
>以下命令代表每個人對 $CALC_DEV 都有讀和寫的權限

sudo chmod 0666 $CALC_DEV

- `device file`:
- `device driver` 與 user 的重要溝通橋梁，我們透過 `device file` 與實體硬體溝通
- 都有兩個數字分別是 `major number` 與 `minor number`，用來區別不同的 `device driver` 與個別的硬體
- `major number` 相同，代表他們使用一樣的 `device driver`
- 不同的 `minor number`，則連結到不同的硬體

- User 以 open() 打開 device file 後:
- 可以透過 write() 將資料傳給 driver
- 可以透過 read() 從 driver 取得資料
- 處理完畢後，再以 close() 關閉 device file。

### 4. 在 `calc.c` 檔案中，用到 `copy_to_user` 這個 kernel API，其作用為何？本例使用該 API 做了什麼事？若是資料量增長，是否會有效能的嚴重衝擊呢？

- `copy_to_user` : kernel space 的內容複製到 user space
>`to`：destination address in user space
`from`：source address in kernel space
`n`: number of bytes to copy
返回不能被複制的 bytes，如果完全複製成功則返回0

unsigned long copy_to_user
(void *to, const void *from, unsigned long n);

>將 kernel space 裡的 message ，長度為 size_of_message 的 char type array 複製到 user space 的 buffer 所指的 address

error_count = copy_to_user(buffer, message, size_of_message);

- 如果使用`copy_to_user`時，要複製的資料量太大，就會讓 buffer 產生 overflow，導致效能降低
- 如果 user 讀取到錯誤的資料，可能導致程式崩潰
- 如果後面的記憶體存放著應用程式的資料，則會導致其他功能讀取到錯誤的資料，因此工作不正常，也可能導致程式崩潰。

### 5. 找出至少 3 個 Linux 核心中使用定點數的案例，搭配程式碼解說。提示: 參照 Linux Kernel Load Average 計算分析。What Every Computer Scientist Should Know About Floating-Point Arithmetic, Load average explained

### 6. 是否知曉 `MathEx` 如何解析給定字串，從而分離出變數和對應數學表示法呢？

### 7. 如何對 `MathEx` 進行效能分析？能否找出相似的 math expression 來分析比較呢？提示: 參照 muparserSSE - A Math Expression Compiler

### 8. 在 `MathEx` 原始程式碼的 `expression.[ch] `裡頭 `vec` 相關的程式碼，主要做什麼事？有沒有發現類似 list 使用到的技巧呢？提示: 參照 `mathex/test-unit.c` 的測試項目

### 9. 解釋 `MathEx` 一類的 math expression 在真實世界有哪些應用？甚至，是否在 Linux 核心就存在類似的程式碼？提示: 參照 A thorough introduction to eBPF

### 10. 如果要將使用者層級的 C 語言程式，搬到 Linux 核心作為核心模組 (LKM)，該注意哪些議題呢？請舉例說明。提示: 注意 `__KERNEL__` 巨集的定義, kmalloc 的使用, vmalloc 的使用 (以及後兩者的差異)

- `__KERNEL__`：user space process 需要訪問 kernel header file ,但 kernel header file 中的某些資訊僅適用於 kernel，所以我們在 #ifdef __KERNEL __ /#endif 中封裝一些語句可確保 user space process 不會看到這些語句

/* only for userspace compatibility */
#ifndef __KERNEL__

/* IP6 Hooks */
/* After promisc drops, checksum checks. */
#define NF_IP6_PRE_ROUTING  0
/* If the packet is destined for this box. */
#define NF_IP6_LOCAL_IN     1
/* If the packet is destined for another interface. */
#define NF_IP6_FORWARD      2
/* Packets coming from a local process. */
#define NF_IP6_LOCAL_OUT        3
/* Packets about to hit the wire. */
#define NF_IP6_POST_ROUTING 4
#define NF_IP6_NUMHOOKS     5
#endif /* ! __KERNEL__ */

- `kmalloc`：在 kernel 中 allocate memory

- `kmalloc`是 kernel 中最常用的一種 allocate memory 的方式，它通過呼叫`kmem_cache_alloc`函數來實現
- `kmalloc` 一次可配置的容量上限是128KBytes
- `kmalloc` 能夠配置的記憶體容量是有上限的，因為配置出來的空間是連續的==實體==記憶體
>`size_t size`：how many bytes of memory are required
>`gfp_t flags`：the type of memory to allocate

void * kmalloc (size_t size,gfp_t flags);

- `vmalloc`：在 virtual space allocate 一段連續的 memory

- `vmalloc` 所得到的每一頁的記憶體都是個別呼叫`alloc_page`所得來的
- `vmalloc`對一次能分配的記憶體大小沒有明確限制
- 配置出來的是連續==虛擬==位址的實體記憶體, 不一定是連續的, 而只是被核心是為一段連續的位址範圍
-`vmalloc`速度比`kmalloc`慢
>`unsigned long size`：allocation size Allocate enough pages to cover size from the page level allocator and map them into contiguous kernel virtual space.

void * vmalloc (unsigned long size);

- `malloc`是 allocate user 的 memory ，所以當移到 kernel 之後應該改用 `kmalloc` 或是 `vmalloc`

### 11. fixed point arithmetic for RT-Linux 的運作原理為何？給定的程式碼已經存在超過 20 年，很多細節已有出入，可否嘗試移植到 Linux `v4.15+` 呢？

- `fixed point number`：一種實數資料類型，小數點永遠固定在定點，利用 integer 運算模擬 floating-point 運算
* 1-bit 的 sign bit
* 17-bits 的 integral part
* integral part 的 range :
-131072~131071
* 14-bits 的 fractional part
* `fixed point number`的 accuracy :
2^-14^，four digits after the decimal point

- `rt_fix`：`fixed point number`的基本類型，佔 32-bits word 的空間
* 初始化`rt_fix`之後，integral part 和 fractional part 固定了
* 運作方式為左對齊，為了保持 fractional part 的 precision

- 使用 `fixed point arithmetic` 目的為避免在 kernel space 使用 FPU，因為 floating-point 運算需要花費較多的時間，雖然會降低 precision，卻可以提升運算速度