---
tags : Linux kernel Design
---
# 2021q1 Howework1 (lab0)
contributed by < `waynelinbo` >

> GitHub: [waynelinbo/lab0-c](https://github.com/waynelinbo/lab0-c)

## Environment
[Installing Multipass on macOS](https://multipass.run/docs/installing-on-macos?fbclid=IwAR2llJvbssQHQ-X2gUk2a6UO9eIKTTl67MoOfJ5EwhTvBIEd0L93tnPHxT4)

$ uname -a
Linux ubuntu 5.4.0-62-generic #70-Ubuntu SMP Tue Jan 12 12:45:47 UTC 2021 x86_64 x86_64 x86_64 GNU/Linux
$ gcc --version | head -1
gcc (Ubuntu 9.3.0-17ubuntu1~20.04) 9.3.0

## Requirements
- [x] 在 GitHub 上 fork [lab0-c](https://github.com/sysprog21/lab0-c)
* 參閱 [Git 教學和 GitHub 設定指引](https://hackmd.io/@sysprog/git-with-github) ^附教學影片^
- [x] ==詳細閱讀 [C Programming Lab](https://www.cs.cmu.edu/afs/cs/academic/class/15213-s20/www/labs/cprogramminglab.pdf)== ，依據指示著手修改 `queue.[ch]` 和連帶的檔案，測試後用 Git 管理各項修改，記得也該實作 `q_sort` 函式。
- [x] 在提交程式變更前，務必詳閱 [如何寫好 Git Commit Message](https://blog.louie.lu/2017/03/21/%E5%A6%82%E4%BD%95%E5%AF%AB%E4%B8%80%E5%80%8B-git-commit-message/)
- [ ] 除了修改程式，也要編輯「[作業區](https://hackmd.io/@sysprog/linux2021-homework1)」，增添開發紀錄和 GitHub 連結，除了提及你如何逐步達到自動評分程式的要求外，共筆也要涵蓋以下:
- [ ] 開啟 [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) :arrow_forward: 為避免「舉燭」，請比照 `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

## Implement queue.[ch]
### Work List
- [x] **queue.c**
|Done?|function name|time complexity|description|
|:-:|:-|:-:|:---|
|:o:|`q_new`|O(1)|Create empty queue|
|:o:|`q_free`|O(n)|==Free all storage== used by queue|
|:o:|`q_insert_head`|O(1)|Insert an new element at head of queue|
|:o:|`q_insert_tail`|==O(1)==|Insert an new element at tail of queue|
|:o:|`q_remove_head`|O(1)|Remove the element from head of queue|
|:o:|`q_size`|==O(1)==|Return number of elements in queue|
|:o:|`q_reverse`|O(n)|Reverse all elements in queue|
|:o:|`q_sort`|==$O(n \log n)$==|Sort elements of queue in ascending order|
- [x] **queue.h**
- [x] `struct queue_t` :

    $ git diff 8107 d47c
    
    diff --git a/queue.c b/queue.c
    index a77dbf7..553d49c 100644
    --- a/queue.c
    +++ b/queue.c
    @@ -13,7 +13,11 @@ queue_t *q_new()
     {
         queue_t *q = malloc(sizeof(queue_t));
         /* TODO: What if malloc returned NULL? */
    -    q->head = NULL;
    +    if (q) {
    +        q->head = NULL;
    +        q->tail = NULL;
    +        q->size = 0;
    +    }
         return q;
     }

:::warning
標題寫 queue.h，但內容卻改 queue.c，很混亂。
:notes: jserv
:::

### Implementation details

:::danger
如果你想用英文書寫，那就要改進文法和用字的精準度。
:notes: jserv
:::
:::success
* [name=waynelinbo] : Thanks for your advice, I will improve in the future.
:::

* q_new
1. Create empty queue

  queue_t *q = malloc(sizeof(queue_t));

:::warning
sizeof() is an **"operator"** in C programing language.

:::
2. Return NULL if could not allocate space
Use malloc to
* q_free
* q_insert_head
* q_insert_tail
* q_remove_head
* q_size
* q_reverse
* q_sort