# 2021q1 Homework1 (lab0)
contributed by < `asahsieh` >
> [作業說明](https://hackmd.io/@sysprog/linux2021-lab0)
:::spoiler [作業 TODO list](https://hackmd.io/@sysprog/linux2021-lab0#-作業要求)
- [X] 開啟 [Address Sanitizer](https://github.com/google/sanitizers/wiki/AddressSanitizer)，修正 `qtest` 執行過程中的錯誤
- 先執行 `qtest` 再於命令提示列輸入 `help` 命令，會使 開啟 [Address Sanitizer](https://github.com/google/sanitizers/wiki/AddressSanitizer) 觸發錯誤，應予以排除
- [ ] 運用 Valgrind 排除 `qtest` 實作的記憶體錯誤，並透過 Massif 視覺化 “simulation” 過程中的記憶體使用量，需要設計對應的實驗
- [ ] 在 `qtest` 中實作 [coroutine](https://en.wikipedia.org/wiki/Coroutine)，並提供新的命令 `web`，提供 web 伺服器功能，注意: web 伺服器運作過程中，`qtest` 仍可接受其他命令
- 可嘗試整合 [tiny-web-server](https://github.com/7890/tiny-web-server)，將 `FORK_COUNT` 變更為 `0`，並以 [coroutine](https://en.wikipedia.org/wiki/Coroutine) 取代原本的 fork 系統呼叫
- [ ] 解釋 [select](http://man7.org/linux/man-pages/man2/select.2.html) 系統呼叫在本程式的使用方式，並分析 [console.c](https://github.com/sysprog21/lab0-c/blob/master/console.c) 的實作，說明其中運用 CS:APP [RIO 套件](http://csapp.cs.cmu.edu/2e/ch10-preview.pdf) 的原理和考量點。可對照參考 [CS:APP 第 10 章重點提示](https://hackmd.io/@sysprog/H1TtmVTTz)  為避免「舉燭」，請比照 `qtest` 實作，撰寫獨立的終端機命令解譯器 (可建立新的 GitHub repository)
- [ ] 說明 [antirez/linenoise](https://github.com/antirez/linenoise) 的運作原理，注意到 [termios](http://man7.org/linux/man-pages/man3/termios.3.html) 的運用
- [ ] 研讀論文 [Dude, is my code constant time?](https://eprint.iacr.org/2016/1123.pdf)，解釋本程式的 “simulation” 模式是如何透過以實驗而非理論分析，達到驗證時間複雜度，需要解釋 [Student’s t-distribution](https://en.wikipedia.org/wiki/Student%27s_t-distribution) 及程式實作的原理。注意：現有實作存在若干致命缺陷，請討論並提出解決方案;
- [ ] 指出現有程式的缺陷 (提示: 和 [RIO 套件](http://csapp.cs.cmu.edu/2e/ch10-preview.pdf) 有關)，嘗試強化並提交 pull request
:::
## 作答內容
> **作答說明**: 作答包含閱讀作業中的筆記及延伸閱讀或實驗；老師要求涵蓋的部份會在各section中以 ==題目== 來表示
### [](https://hackmd.io/7GxMpQwbSGuOl93CDEAr2g?view#-取得程式碼並進行開發 "-取得程式碼並進行開發") 取得程式碼並進行開發
**Git commit**
- 從今以後，不要用 `git commit -m`, 改用 `git commit -a` (或其他參數) 並詳細查驗變更的檔案。
#### ==題目==：開啟 [Address Sanitizer](https://github.com/google/sanitizers/wiki/AddressSanitizer)，修正 `qtest` 執行過程中的錯誤。
執行`make test`後的error messages太多，故[redirect stderr到stdout並ouput到一個檔案](https://linuxize.com/post/bash-redirect-stderr-stdout/)中:
- `$make test > asan.log 2>&1`
- 以`AddressSanitizer`當作keyword搜尋the output file:
```c=
=================================================================
==939025==ERROR: AddressSanitizer: global-buffer-overflow on address 0x5641671c2720 at pc 0x5641671abcac bp 0x7fffd94ced10 sp 0x7fffd94ced00
READ of size 4 at 0x5641671c2720 thread T0
#0 0x5641671abcab in do_option_cmd /home/ubuntu/linux2021/lab0-c/console.c:371
#1 0x5641671aaa91 in interpret_cmda /home/ubuntu/linux2021/lab0-c/console.c:223
#2 0x5641671ab276 in interpret_cmd /home/ubuntu/linux2021/lab0-c/console.c:246
#3 0x5641671ac4a5 in cmd_select /home/ubuntu/linux2021/lab0-c/console.c:596
#4 0x5641671aca1f in run_console /home/ubuntu/linux2021/lab0-c/console.c:669
#5 0x5641671a95a6 in main /home/ubuntu/linux2021/lab0-c/qtest.c:800
#6 0x7feabfbc00b2 in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x270b2)
#7 0x5641671a6bcd in _start (/home/ubuntu/linux2021/lab0-c/qtest+0x9bcd)
0x5641671c2721 is located 0 bytes to the right of global variable 'simulation' defined in 'console.c:21:6' (0x5641671c2720) of size 1
'simulation' is ascii string ''
SUMMARY: AddressSanitizer: global-buffer-overflow /home/ubuntu/linux2021/lab0-c/console.c:371 in do_option_cmd
Shadow bytes around the buggy address:
0x0ac8ace30490: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0x0ac8ace304a0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0x0ac8ace304b0: 00 00 00 00 00 00 00 00 f9 f9 f9 f9 00 f9 f9 f9
0x0ac8ace304c0: f9 f9 f9 f9 00 f9 f9 f9 f9 f9 f9 f9 00 f9 f9 f9
0x0ac8ace304d0: f9 f9 f9 f9 00 f9 f9 f9 f9 f9 f9 f9 00 f9 f9 f9
=>0x0ac8ace304e0: f9 f9 f9 f9[01]f9 f9 f9 f9 f9 f9 f9 00 00 00 00
0x0ac8ace304f0: 01 f9 f9 f9 f9 f9 f9 f9 04 f9 f9 f9 f9 f9 f9 f9
0x0ac8ace30500: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0x0ac8ace30510: 00 00 00 00 00 00 00 00 00 f9 f9 f9 f9 f9 f9 f9
0x0ac8ace30520: 01 f9 f9 f9 f9 f9 f9 f9 01 f9 f9 f9 f9 f9 f9 f9
0x0ac8ace30530: 04 f9 f9 f9 f9 f9 f9 f9 00 f9 f9 f9 f9 f9 f9 f9
Shadow byte legend (one shadow byte represents 8 application bytes):
Addressable: 00
Partially addressable: 01 02 03 04 05 06 07
Heap left redzone: fa
Freed heap region: fd
Stack left redzone: f1
Stack mid redzone: f2
Stack right redzone: f3
Stack after return: f5
Stack use after scope: f8
Global redzone: f9
Global init order: f6
Poisoned by user: f7
Container overflow: fc
Array cookie: ac
Intra object redzone: bb
ASan internal: fe
Left alloca redzone: ca
Right alloca redzone: cb
Shadow gap: cc
==939025==ABORTING
```
==**Shadow bytes**==
- mapping方式：
- ++8 bytes++ of *main memory* is mapped to ++1 byte++ of *shadow memory*, 故Shadow addr = Application addr >> 3
- 於此例，即`0x0ac01f9f9434` = `0x5600fcfca721 >> 3`; :question: bit 5跟8對不起來 => *to be checked*.
- shadow byte的值
- 代表Good bytes的數量；因對應main memory的8 bytes，所以有9種可能的值。其++0++代表*8 bytes都是good*, ++-1++代表*8 bytes都是bad*.
- 若要得知從bit 0開始直到bytes結束為bad bytes，可用`8 - N, N: number of Good bytes`.
- 沒有將ASan打開時，program可以work, 所以需要以ASan為方向debug.
> 在搜尋error message中提及的*simulation*變數時，發現在 *add_param\(\)* 中透過reference operator & 取得位置後，會轉型由integer pointer指向該位置, 在console.c對應的code如下：
```c=20
/* Some global values */
bool simulation = false;
static cmd_ptr cmd_list = NULL;
```
```c=104
add_param("simulation", (int *) &simulation, "Start/Stop simulation mode",
NULL);
```
:::info
於ISO_C99 Standard確認bool與int之前的conversion.
在§6.3.1.1 Boolean, characters, and integers的第2點提到:
:::
> 2 The following may be used in an expression wherever an int or unsigned int may be used:
\- An object or expression with an integer type whose integer conversion rank is less than or equal to the rank of int and unsigned int.
\- A bit-field of type _Bool, int, signed int, or unsigned int.
第二項提到type _Bool, int, signed int or unsigned int都可以用int或unsigned int來表示。
> 由上可知，將Bool type cast成int是合法的；於是我們再回頭看ASan給我們的ERROR message，其中有提到兩個不同的sizes, 分別是size 1與size 4; 如下:
```c=
==939025==ERROR: AddressSanitizer: global-buffer-overflow on address 0x5641671c2720 at pc 0x5641671abcac bp 0x7fffd94ced10 sp 0x7fffd94ced00 READ of size 4 at 0x5641671c2720 thread T0
```
```c=+
0x5641671c2721 is located 0 bytes to the right of global variable 'simulation' defined in 'console. c:21:6' (0x5641671c2720) of size 1
```
==總結上述兩個描述，在存取'simulation'時，起始位置是 0x5641671c2720, 且以int type的長度讀取4個bytes；但'simulation'宣告的type是bool，長度是1個byte，故存取下一個位址 0x5641671c2721 時，因這個byte沒有被initailized，故ASan印出"is located 0 bytes"的訊息==
### [Valgrind使用案例](https://hackmd.io/@sysprog/linux2021-lab0#Valgrind-使用案例)
#### ==題目==:運用 Valgrind 排除 `qtest` 實作的記憶體錯誤，並透過 Massif 視覺化 “simulation” 過程中的記憶體使用量，需要設計對應的實驗
1. 運用 Valgrind 排除 `qtest` 實作的記憶體錯誤
```shell=
# Test of insert_head and remove_head
8 ERROR: Failed to store removed value
7 ERROR: Failed to store removed value
6 ERROR: Failed to store removed value
5 ==24532== 4 bytes in 1 blocks are still reachable in loss record 1 of 30
4 ==24532== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck- amd64-linux.so)
3 ==24532== by 0x4A4450E: strdup (strdup.c:42)
2 ==24532== by 0x110E93: linenoiseHistoryAdd (linenoise.c:1236)
1 ==24532== by 0x111A26: linenoiseHistoryLoad (linenoise.c:1325)
33 ==24532== by 0x10D31C: main (qtest.c:789)
1 ==24532==
```
2. [使用 Massif 側寫堆積與堆疊空間](https://access.redhat.com/documentation/zh-tw/red_hat_enterprise_linux/6/html/performance_tuning_guide/ch05s03s03)
- 執行 Massif 的程式之執行速度會比正常情況慢約 20 倍。
### 追蹤記憶體配置和釋放的狀況
- :question: Why need two magic numbers on ==Header== and ==Footer==?
- Ref.: [Working with Magic numbers in Linux](https://www.geeksforgeeks.org/working-with-magic-numbers-in-linux/)
- is usually be used as `File Signatures`
- These bytes can be used by the system to “**differentiate between and recognize different files**” without a file extension.
- (:small_red_triangle:) On the example of Queue in Lab0, the magic numbers are used to separate elements in the queue.
- size_t
**size_t**是一些C/C\+\+標準在stddef.h中定義的，size_t 型別表示C中++任何物件所能達到的最大長度++，它是*無符號整數(unsigned integer)*。
### `qtest` 命令直譯器的實作
程式執行到此，會將之前解析的輸入傳遞過去。以 `it` 命令為例：
```
cmd> it LookAtMe
```
- ==My ran result:==
- [X] (TO-DEBUG)
> how to print call stack in C or C++[^first].
1. A queue should be initiated before use, but the insertion is still failed:
2. We change the other command `ih` to insert the string on the Head of queue:
- we get `SIGSEGV, Segmentation fault.`:
[只是缺少__strlen_avx2的source code(strlen_avx2.S), 無法trace到該function內部的code; root cause 需往前trace](https://stackoverflow.com/q/50461574)
- 因為`ih`指令呼叫的`q_insert_head()`尚未實作當`q is NULL`的情況：
- 呼叫`q_insert_head()`後會呼叫`show_queue()`來印出`q`的內容，而pass給`report_noreturn`的**q->value**因`e`指向NULL，所以發生core dump:
### [Signal](http://man7.org/linux/man-pages/man7/signal.7.html)處理和應用
#### POSIX
- Not to be confused with [Unix](x-dictionary:r:'Unix?lang=en&signature=com.apple.DictionaryApp.Wikipedia' "Unix"), [Unix-like](x-dictionary:r:'Unix-like?lang=en&signature=com.apple.DictionaryApp.Wikipedia' "Unix-like"), or [Linux](x-dictionary:r:'Linux?lang=en&signature=com.apple.DictionaryApp.Wikipedia' "Linux").
- The **Portable Operating System Interface** (**POSIX**) is a family of [standards](x-dictionary:r:'Standardization?lang=en&signature=com.apple.DictionaryApp.Wikipedia' "Standardization") specified by the [IEEE Computer Society](x-dictionary:r:'IEEE_Computer_Society?lang=en&signature=com.apple.DictionaryApp.Wikipedia' "IEEE Computer Society") for maintaining compatibility between [operating systems](x-dictionary:r:'Operating_system?lang=en&signature=com.apple.DictionaryApp.Wikipedia' "Operating system").[\[1\]](https://en.wikipedia.org/wiki/POSIX#cite_note-1) POSIX defines the [application programming interface](x-dictionary:r:'Application_programming_interface?lang=en&signature=com.apple.DictionaryApp.Wikipedia' "Application programming interface") (API), along with command line [shells](x-dictionary:r:'Unix_shell?lang=en&signature=com.apple.DictionaryApp.Wikipedia' "Unix shell") andutility interfaces, for software compatibility with variants of [Unix](x-dictionary:r:'Unix?lang=en&signature=com.apple.DictionaryApp.Wikipedia' "Unix") and other operating systems.[\[2\]](https://en.wikipedia.org/wiki/POSIX#cite_note-FAQ-2)[\[3\]](https://en.wikipedia.org/wiki/POSIX#cite_note-IET-3)
翻閱《[The Linux Programming Interface](http://man7.org/tlpi/)》，得知 signal 運用上的議題:
1. `sigsetjmp` 跟 `siglongjmp` 是能在 signal handler 內部使用的非區域跳躍。不使用 `setjmp`或`longjmp` 的考量點[^second]
### 命令直譯器的初始化準備
### Coroutine
- [ ] 參考實作:
- [Coroutines in less than 20 lines of standard C](https://fanf.livejournal.com/105413.html)
- [Coroutines in one page of C](https://yosefk.com/blog/coroutines-in-one-page-of-c.html)
- [ ] 延伸閱讀: [你所不知道的C語言: goto 和流程控制篇](https://hackmd.io/@sysprog/c-control-flow?type=view)
[^first]: - Use `bt` cmd in GDB (used in lecuture note of Lab0):
- Programmatic methods
- Ref.:
[Programmatic access to the call stack in C/C++](https://eli.thegreenplace.net/2015/programmatic-access-to-the-call-stack-in-c/)
[print call stack in C or C++](https://stackoverflow.com/a/54365144)
- [x] **GNU backtrace functions**:
function addresses with partial function names are shown
- [ ] **libunwind**
issue on GCC link process:
- [ ] **libdwfl**
is more complex to program
[^second]: [man setjmp](https://man7.org/linux/man-pages/man3/setjmp.3.html)
setjmp, sigsetjmp, longjmp, siglongjmp - performing a [nonlocal goto](https://www.csl.mtu.edu/cs4411.ck/www/NOTES/non-local-goto/goto.html)
- The **setjmp**() function dynamically establishes the target to which control will later be transferred, and **longjmp**() performs the transfer of execution.
- **setjmp**() and **longjmp**() are paired and execution order: **setjmp**() -> **longjmp**() -> return transfer control back to the point where **setjmp**() was called.
- **sigsetjmp**() and **siglongjmp**() also perform nonlocal gotos, but ==provide _predictable handling_ of the process signal mask==.
> **[Process Signal Mask](https://www.gnu.org/software/libc/manual/html_node/Process-Signal-Mask.html)**
>
> - The collection of signals that are currently blocked is called the _signal mask_.
> - Each process has its own signal mask. When you create a new process (see [Creating a Process](https://www.gnu.org/software/libc/manual/html_node/Creating-a-Process.html)), it inherits its parent’s mask.
> - You can block or unblock signals with total flexibility by modifying the signal mask.
- **Notes**
- POSIX does not specify whether setjmp() will save the signal mask. In System V it will not. In 4.3BSD it will, and there is a function \_setjmp that will not.
--> [System V and Unix History tree](https://en.wikipedia.org/wiki/UNIX_System_V#/media/File:Unix_history-simple.svg)
- If you want to portably save and restore signal masks, use sigsetjmp() and siglongjmp(3).
--> [有prefix "sig"的functions，代表會做save and restore signal masks(portable)](https://diigo.com/0kw5lc)
::::info
From Tr. Jserv: [簡言之，當某個 signal handler 被觸發時，該 signal 會在執行 signal handler 時會被遮罩住，並在 signal handler 回傳時恢復。]( https://diigo.com/0kw7ez)
::::
###### tags: `linux2021`
Sign in with Wallet
Connect another wallet