# 2020q1 Homework1 (lab0)
contributed by < `a20034294` >

## 實驗環境
* 硬體環境:
* Guest CPU kvm64 QEMU(1:2.11+dfsg-1ubuntu7.23) in Proxmox VE
* Host CPU X5650 2.66G*2
* 2GB RAM
* 作業系統: Ubuntu 18.04.4
* 核心版本: Linux 4.15.0-88-generic
* gcc 版本: 7.4.0-1ubuntu1~18.04.1

## 作業目標
- [x] 在 GitHub 上 fork [lab0-c](https://github.com/sysprog21/lab0-c)
- [x] 參閱 [Git 教學和 GitHub 設定指引](https://hackmd.io/@sysprog/git-with-github) ^附教學影片^
- [x] ==詳細閱讀 [C Programming Lab](http://www.cs.cmu.edu/~213/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/)
- [x] 不用理會 [Autolab](http://www.autolabproject.com/) 和檔案下載的描述，這兩者都是 CMU 專屬
- [x] 修改排序所用的比較函式，變更為 [natural sort](https://github.com/sourcefrog/natsort)，在 "simulation" 也該做對應的修改，得以反映出 [natural sort](https://github.com/sourcefrog/natsort) 的使用。
- [x] 除了修改程式，也要編輯「[作業區](https://hackmd.io/@sysprog/linux2020-homework1)」，增添開發紀錄和 GitHub 連結，除了提及你如何逐步達到自動評分程式的要求外，共筆也要涵蓋以下:
- [x] 運用 Valgrind 排除 `qtest` 實作的記憶體錯誤，並透過 Massif 視覺化 "simulation" 過程中的記憶體使用量，需要設計對應的實驗
- [ ] 研讀論文 [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) 及程式實作的原理;
- [ ] 解釋 [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)，強化 `qtest` 命令列功能，使其支援單行或多行編輯、歷史命令處理、命令自動補完 (例如輸入 `h` 之後按下 Tab 按鍵，自動接續補上 `elp`，成為完整的 `help` 命令)。除了整合程式碼外，應當說明 [antirez/linenoise](https://github.com/antirez/linenoise) 的運作原理，注意到 [termios](http://man7.org/linux/man-pages/man3/termios.3.html) 的運用
- [ ] 思考如何預設開啟 AddressSanitizer，卻又能滿足效能測試所需 (可能需要兩種以上的 build target)
- [ ] 指出現有程式的缺陷 (提示: 和 [RIO 套件](http://csapp.cs.cmu.edu/2e/ch10-preview.pdf) 有關)，嘗試強化並提交 pull request
- [ ] 截止日期：
- [ ] Mar 2, 2020 (含) 之前
> [name=a20034294] 大失敗
- [ ] 越早在 GitHub 上有動態、越早接受 code review，評分越高

## 實作

依照 [C Programming Lab](http://www.cs.cmu.edu/~213/labs/cprogramminglab.pdf) 裡的說明，需要更改以下的 function 以完成作業要求
* q_new
* q_free
* q_insert_head
* q_insert_tail
* q_remove_head
* q_size
* q_reverse
* q_sort

### q_new
新增 `malloc return NULL` 時的例外狀況，以及初始化 queue

   13 queue_t *q_new()
   14 {
   15     queue_t *q = malloc(sizeof(queue_t));
~  16
+  17     if (!q) {
+  18         return NULL;
+  19     }
   20     q->head = NULL;
+  21     q->tail = NULL;
+  22     q->size = 0;
   23     return q;
   24 }

### q_free
將所使用的 string 空間以及 `list_ele_t` 所使用的 node 空間釋放

   27 void q_free(queue_t *q)
   28 {
~  29     // cppcheck-suppress variableScope
~  30     list_ele_t *p, *tmp;
+  31
+  32     if (!q)
+  33         return;
+  34
+  35     p = q->head;
+  36     while (p) {
+  37         free(p->value);
+  38         tmp = p;
+  39         p = p->next;
+  40         free(tmp);
+  41     }
   42     free(q);
   43 }

### q_insert_head
與 `q_insert_tail` 差距不大，只貼其中一個
動態分配記憶體 copy 需要 insert 的 string 然後維護 queue
原本使用 `strcpy()` 進行 copy，但被報 Warnning

   52 bool q_insert_head(queue_t *q, char *s)
   53 {
   54     list_ele_t *newh;
~  55     char *tmp_s;
+  56
+  57     if (!q)
+  58         return false;
+  59
   60     newh = malloc(sizeof(list_ele_t));
~  61     if (!newh)
~  62         return false;
+  63
+  64     tmp_s = malloc(strlen(s) + 1);
+  65     if (!tmp_s) {
+  66         free(newh);
+  67         return false;
+  68     }
+  69     strncpy(tmp_s, s, strlen(s) + 1);
+  70
+  71     newh->value = tmp_s;
   72     newh->next = q->head;
   73     q->head = newh;
+  74     if (!q->size)
+  75         q->tail = newh;
+  76     q->size++;
   77     return true;
   78 }

### q_remove_head
利用 `strncpy` 進行 copy 並在尾端補 `\0`
最後釋放記憶體空間

  125 bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
  126 {
~ 127     list_ele_t *head;
~ 128
+ 129     if (!q || !q->head)
+ 130         return false;
+ 131
+ 132     head = q->head;
+ 133     if (sp) {
+ 134         strncpy(sp, head->value, bufsize);
+ 135         sp[bufsize - 1] = '\0';
+ 136     }
  137     q->head = q->head->next;
+ 138     q->size--;
+ 139     free(head->value);
+ 140     free(head);
  141     return true;
  142 }

### q_size
由於在各個會變動大小的函數內已經維護 size，因此直接 `return q->size`

  148 int q_size(queue_t *q)
  149 {
+ 150     if (!q)
+ 151         return 0;
+ 152
+ 153     return q->size;
  154 }

:::warning
可改寫為:

int q_size(queue_t *q)
{
    return q ? q->size : 0;
}

:notes: jserv
> [name=a20034294]已經修改完成 謝謝老師 [4b2c0a](https://github.com/a20034294/lab0-c/commit/4b2c0ab687bf3311fe45b987b1a111cafa85c883)
:::

### q_reverse
走訪 list 並將 `next` 指標反指
最後將 `head`、`tail` 互換

  163 void q_reverse(queue_t *q)
  164 {
~ 165     list_ele_t *p, *prev, *next;
~ 166
+ 167     if (!q || q->size <= 1)
+ 168         return;
+ 169
+ 170     p = q->head;
+ 171     prev = NULL;
+ 172     while (p) {
+ 173         next = p->next;
+ 174         p->next = prev;
+ 175         prev = p;
+ 176         p = next;
+ 177     }
+ 178
+ 179     // swap
+ 180     p = q->head;
+ 181     q->head = q->tail;
+ 182     q->tail = p;
  183 }

### q_sort
使用 merge sort 由於 code 太長了就不貼了
值得一提的是原本直接引入 [natural sort](https://github.com/sourcefrog/natsort) 作為比較使用，結果 `make test` 出現 `TLE + seg fault`，`make valgrind` 執行可以正常通過，判斷應是太慢導致。

調整 insert 的數量，從 $2e6$ 到 $8e5$ 之後可以通過，認為成因可能是 QEMU + x5650 2.66G 太慢。

突然想到可以用 hash 表，讓他可以在判斷字串不同之後才進行比較。
以下為 hash function

/*
 * Get the string hash
 * @char* s string
 */
inline void hash(list_ele_t *e)
{
    e->hash = 0;
    for (int i = 0; i < e->len; ++i) {
        e->hash *= 10000007;
        e->hash += e->value[i];
    }
}

然後正常通過，不過這對 $aaaa...aab$、$aaaa...aaa$ 這樣的字串比對沒有幫助，因為 hash 值無法比較大小，用紅黑樹的 [map(c++ STL)](http://www.cplusplus.com/reference/map/map/) 或是 hash map 做 hash 比較結果的 cache 可以顯著提升效率，但是實作太難，也沒有必要就不實作了。

---
未完

==7135==ERROR: AddressSanitizer: global-buffer-overflow on address 0x55b6cb8c19c0 at pc 0x55b6cb6b1d17 bp 0x7ffdba43b8d0 sp 0x7ffdba43b8c
0
READ of size 4 at 0x55b6cb8c19c0 thread T0
    #0 0x55b6cb6b1d16 in do_option_cmd /home/a20034294/lab0-c/console.c:368
    #1 0x55b6cb6b0ddc in interpret_cmda /home/a20034294/lab0-c/console.c:220
    #2 0x55b6cb6b10cc in interpret_cmd /home/a20034294/lab0-c/console.c:243
    #3 0x55b6cb6b1fb6 in cmd_select /home/a20034294/lab0-c/console.c:569
    #4 0x55b6cb6b223f in run_console /home/a20034294/lab0-c/console.c:628
    #5 0x55b6cb6ad26b in main /home/a20034294/lab0-c/qtest.c:772
    #6 0x7fbfe07dfb96 in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x21b96)
    #7 0x55b6cb6ad549 in _start (/home/a20034294/lab0-c/qtest+0x7549)

0x55b6cb8c19c1 is located 0 bytes to the right of global variable 'simulation' defined in 'console.c:20:6' (0x55b6cb8c19c0) of size 1
  'simulation' is ascii string ''
SUMMARY: AddressSanitizer: global-buffer-overflow /home/a20034294/lab0-c/console.c:368 in do_option_cmd