# 2019q1 Homework2 (kcalc)
contributed by < `johnnylord` >
###### tags: `sysprog2019`
### Reviewed by `afcidk`
* 可以實驗一下最後面提到的 "每當空間不夠就 realloc 兩倍的空間" 這個作法帶來的效能提升
* Commit message 裏面可以多一點描述，像是在 [065a42](https://github.com/johnnylord/fibdrv/commit/065a42f6885260bdde0cd5119ca56d0abf16e1c0) 中可以提一下為什麼要再寫一個有 thread 版本的 client 程式
## 實驗環境
```shell
$ uname -a
Linux johnnylord 4.18.0-16-generic #17~18.04.1-Ubuntu SMP Tue Feb 12 13:35:51 UTC 2019 x86_64 x86_64 x86_64 GNU/Linux
```
## 自我檢查清單
### 在給定的 `calc.c` 檔案中，和 fibdrv 一樣有 character device，但註冊用的 kernel API 不同 (`register_chrdev` vs. `alloc_chrdev_region`)，能否解釋其差異和適用場合呢？
系統中的 device，都有代表其 driver 的 major number，和代表 device 本身的 minor number。所以在註冊一個 device 的時候 major number 和 minor number 是兩項很重要的資訊。
`alloc_chrdev_region` 可以由開發者指定 minor number 的基底和範圍，但動態的幫開發者選取 device 的 major number。而 `register_chrdev` 則是可以讓開發者指定 device 的 major number，或是讓系統自動分配，但是 minor number 的基點和範圍是固定的。
| API | Major number | Minor number |
| --- | --- | --- |
| `alloc_chrdev_region` | 系統自動分配 | 開發者自行指定基底和範圍 |
| `register_chrdev` | 可自動分配也可開發者指定 | 固定基底和範圍 |
`alloc_chrdev_region` 比較適合使用在當開發的 driver 要給別人使用時使用，而 `register_chrdev` 比較適合本地開發時使用或是這個 driver 本身就要榜定某個 major number。大部分情況我們應該使用 `alloc_chrdev_region`，這樣的作法使的 driver 更具可攜性。
:::success
以下連結是 linux 預定義的一些 major number 和 minor number 給不同的 device。
https://github.com/torvalds/linux/blob/master/Documentation/admin-guide/devices.txt
:::
### 在 `scripts/test.sh` 檔案中，有一道命令為 `sudo chmod 0666`，這個作用為何？對於我們測試有何幫助？能否對 fibdrv 建立的 `/dev/fibonacci` device file 也套用類似修改呢？另外，請解釋 device file 在核心及使用者層級的功能
每個 file 在系統中都有其可以存取的權限，最主要可以區分為 `user`, `group`, `other`
這種不同類別的權限。
以下查看 `chmod` 的 man page
```shell
$ man chmod
```
> This manual page documents the GNU version of chmod. **chmod changes the file mode bits** of each given file according to mode, which can be either a ==symbolic representation== of changes to make, or an ==octal number representing== the bit pattern for the new mode bits.
這邊用第一份作業 `fibdrv` 的 `/dev/fibnocci` 這個裝置檔案當解說
```shell
$ ls -l /dev/fibonacci
crw------- 1 root root 236, 0 三 17 11:08 /dev/fibonacci
```
輸出的第一行（column)，可以這樣去詮釋
```shell
TYPE USER GROUP OTHER
c rw- --- ---
TYPE: 檔案的類型，這邊表示 char device
USER: 擁有這個檔案的 owner 的權限，這邊代表有 read/write 權力
GROUP: 同在同一個 group，對於這個檔案的權限
OTHER: 不是此檔案的 owner 也不再同一個 group，對於檔案的權限
```
而第二，三行則表示此檔案的 user(owner), 和 group。因此上述 `/dev/fibnocci` 只有 `root` 有權限去對它做存取，所以在執行 `client.c` 這個程式時，必須提高權限。
```shell
$ sudo ./client
```
如果使用 `chmod 0666 /dev/fibnocci` 則便會開放給 group, other 讀寫的權限。
```
$ chmod 666 /dev/fibnocci
$ ls -l /dev/fibonacci
crw-rw-rw- 1 root root 236, 0 三 17 11:08 /dev/fibonacci
```
如此一來，執行 `client` 就不用加 `sudo` 了。
### 是否知曉 MathEx 如何解析給定字串，從而分離出變數和對應數學表示法呢？
由於作業說明已有充分說明如何 evaluate 一個 expression(`struct expr *`)，這邊就不做說明。
這邊我用 `gdb` 做 code tracing。測試檔為 `test-simple.c`，這邊專注於分析 `x = 40, add(2, x)` 是如何被解析。以及中間相關資料結構的變化。
:::danger
已使用 GDB 追蹤 code 和儲存資料的變化，但沒有完全理解細節，待補上＠＠
在 `expr_create` 中這三個資料結構會動態的做變化，解析的 token 會被放進以下資料節夠中
* vec_expr_t es
* vec_str_t os
* vec_arg_t as
:::
### 在 `MathEx` 原始程式碼的 `expression.[ch]` 裡頭 vec 相關的程式碼，主要做什麼事？有沒有發現類似 list 使用到的技巧呢？
有點類似於 C++ 的 template 的概念，為某一資料型態做出 vector。
```cpp
#define vec(T) \
struct { \
T *buf; \
int len; \
int cap; \
}
```
其中 `T *buf` 是存放此 vector 所要儲存的目標資料的起始位置，`len` 為這個 vector 的長度，`cap`（我比較傾向於 capability)表示此 vector 的可以容納幾個 vector item 的空間。所以以下條件 ==$len \le cap$== 永遠成立。
`expression.h` 為 `vec` 相關的資料結構定義了以下的操作(巨集)
* **vec_nth**
* **vec_peek**
* **vec_push**
* **vec_pop**
* **vec_free**
* **vec_foreach**
以上這些巨集與 linux kernel 中為 linked-list 所定義的一系列操作(巨集) 有異曲同工的意思。
它們都隱藏了背後的實做，讓撰寫程式碼時更為簡潔，更專注在邏輯上。
以下可以看到 `vec_push` 的實做
```cpp
#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 本身資料結構的更新維護。但是我們都用巨集定義將這些細節隱藏了起來。
:::success
這邊 vector 的作法，每當空間不夠就 realloc 兩倍的空間，這樣預先分配多的記憶體，可以減少之後每次需要增加記憶體的次數。
如果是 linked list 則每次增加元素，就要做一次記憶體分配，會脫慢速度。
:::
Sign in with Wallet
Connect another wallet