# 2018q3 Homework2 (lab0)
contributed by <`AlecJY`>

>commit message 中，將 "Complete" 改為 "Implement" 更為適當
>[name=課重助教][color=red]
>> 好的，謝謝助教的建議
>> [name=AlecJY]

## 實驗環境
* 作業系統：openSUSE Leap 15.0
* gcc：7.3.1
* Cppcheck：1.8
* clang-format：5.0.1

查詢指令及結果如下

$ cat /etc/os-release
NAME="openSUSE Leap"
VERSION="15.0"
ID="opensuse-leap"
ID_LIKE="suse opensuse"
VERSION_ID="15.0"
PRETTY_NAME="openSUSE Leap 15.0"
ANSI_COLOR="0;32"
CPE_NAME="cpe:/o:opensuse:leap:15.0"
BUG_REPORT_URL="https://bugs.opensuse.org"
HOME_URL="https://www.opensuse.org/"

$ gcc --version
gcc (SUSE Linux) 7.3.1 20180323 [gcc-7-branch revision 258812]
Copyright (C) 2017 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

$ cppcheck --version
Cppcheck 1.8

$ clang-format --version
clang-format version 5.0.1 (tags/RELEASE_501/final 312548)

## 開發紀錄
### 環境設定
* 主要因為在上這堂課之前就已經安裝 openSUSE ，加上硬碟空間不足，所以沒有另外安裝 Lubuntu ，直接使用原本已經安裝好的 openSUSE
* 在 GitHub 上面 fork sysprog21/lab0-c ，然後把 fork 出來的 repo clone 下來
* 之後執行 `make` ，會編譯程式碼並且把 git hook 設定好
* 發現沒有安裝 `cppcheck` 以及 `clang-format`，因為使用 openSUSE ， `clang-format` 直接放在 `clang5` 這個 package 裡面，安裝指令如下

$ sudo zypper in cppcheck clang5

* 在提交第一個 commit 之後才發現原始 repo 已經變動，查了一下怎麼把原始 repo 的變動加進去

$ git remote add upstream https://github.com/sysprog21/lab0-c.git
$ git pull upstream master

### 程式碼更動
#### q_new()
這邊根據註解的提示加了檢查 `malloc()` 是否回傳 `NULL` 的檢查，如果是 NULL 的話就直接回傳變數 `q` ，避免之後存取到 `NULL` 指標。

#### q_insert_head() 和 q_remove_head()
`q_insert_head()` 這部分就是檢查 queue 和字串是否為 `NULL` ，然後利用 `strlen()` 計算字串長度後使用 `malloc()`` ，新增一個 `list_ele_t` 之後加到 queue

`q_remove_head()` 這部分也是檢查 queue 和字串是否為 `NULL` ，然後在 `sp` 不是 `NULL` 的情況下把 head 的值複製過去，這邊使用 `strncpy` 複製，然後留下最後一個位置放 null character ，避免字串沒有結尾，之後把 queue 的 head 指到新的 head 後把舊的 head free

在複製字串的部分忘記文件有提到過一定要用 `malloc()` 來分配空間，所以原本想要用 `strdup()` 的，結果在 free 的時候就直接 segmentation fault ，原本還以為誤會了 `strdup()` 的用法，所以仔細檢查了一遍發現好像沒有問題。後來想說不透過 qtest 直接呼叫 function 操作看看，在把測試用程式寫完想要編譯的時候發現出現底下的錯誤

/tmp/ccTDe3Rw.o: In function `q_new':
queue.c:(.text+0xe): undefined reference to `test_malloc'
/tmp/ccTDe3Rw.o: In function `q_free':
queue.c:(.text+0x48): undefined reference to `test_free'
/tmp/ccTDe3Rw.o: In function `q_insert_head':
queue.c:(.text+0x65): undefined reference to `test_malloc'
queue.c:(.text+0x8f): undefined reference to `test_malloc'
queue.c:(.text+0xb1): undefined reference to `test_free'
/tmp/ccTDe3Rw.o: In function `q_remove_head':
queue.c:(.text+0x193): undefined reference to `test_free'
queue.c:(.text+0x19f): undefined reference to `test_free'
collect2: error: ld returned 1 exit status

去看了其中一個 include 的 header `harness.h` 的時候才發現原來 `malloc()` 和 `free()` 被 Macro 改成了 `test_malloc()` 和 `test_free()` ，所以 `strdup()` 呼叫原本的 `malloc()` 所創建的記憶體空間被*不知道做了什麼事情的* `test_free()` 釋放掉，所以產生錯誤，所以嘗試把 `harness.h` 註解掉之後用自己寫的測試小程式跑發現就沒有產生 Segmentation Fault 了
> 等把程式寫完去看 qtest 程式碼後會再補上 `test_malloc()` 和 `test_free()` 做了什麼

#### q_insert_tail()
大致上步驟跟 `q_insert_head()` 差不多，由於要求時間複雜度為 O(1) ，所以在 `queue_t` 中新增了一個新的欄位 `tail` 來記錄 queue 的結尾，並且同時更改了 `q_insert_head()` 和 `q_remove_head()` 在新增至空 queue 和將 queue 清空的情況變動 tail 中的值

#### q_size()
這部分在 `queue_t` 中新增了一個欄位 `size` 來記錄 queue 的長度，一開始先初始化成0，當有新增或刪除的動作時再將 `size` 的數值做增減

#### q_free()
這邊使用了一個迴圈走訪 queue 中的所有元素並把他們以及他們裡面值得記憶體空間釋放，最後再將 queue 本身釋放

#### q_reverse()
這邊先把 tail 的值設定為反轉前的 head ，再使用一個迴圈走訪 queue 並移動 head 的位置，移動時把 next 改為前一個值的位址，走訪完的時候由於最後一個元素因為條件判斷的關係沒有更改到 next 值，所以在迴圈執行完後單獨處理

## 程式碼閱讀
### Git Hooks
* Makefile 中在執行 `make` 的時候會檢查 `.git/hooks/applied` 是否存在，如果不存在就執行 `scripts/install-git-hooks` 這個腳本
* `install-git-hooks` 會在 `.git/hooks/` 這個資料夾裡面建立 `pre-commit` 和 `commit-msg` 的 symbolic link，並建立 `.git/hooks/applied`

#### `pre-commit.hook`
* 這個腳本會檢查有沒有安裝 clang-format 和 cppcheck
* 如果有安裝 colordiff 會使用 colordiff ，沒有的話會使用 diff
* 會將程式碼送至 clang-format 及 cppcheck 檢查
* 使用 clang-format 檢查是將修改過得檔案送到 clang-format 自動排版一次，再比較有沒有修改過

### qtest
#### `harness.c` / `harness.h`
因為之前被改過的 `malloc()` 和 `free()` 弄到產生 bug ，因此想說先從這兩個檔案開始看

`harness.h` 裡面有一段程式碼

#ifdef INTERNAL
...
#else
/* Tested program use our versions of malloc and free */
#define malloc test_malloc
#define free test_free
#endif

在有定義 `INTERNAL` 的時候就不會將 `malloc()` 和 `free()` 取代成 `test_malloc()` 和 `test_free()` 了，在 `harness.c` 和 `qtest.c` 都有定義 `INTERNAL` 以避免使用 `test_malloc()` 和 `test_free()`

在 `test_malloc()` 裡面會檢查現在是否處於 `noallocate_mode` ，並根據機率隨機決定是否要讓 malloc 強制失敗，之後會建立 `block_ele_t` 的變數 `new_block` ，`test_malloc()` 實際上回傳的記憶體空間是 `block_ele_t` 中的 `payload`，並在 `payload` 的前後塞一些固定的值作為檢查，之後把 `new_block` 和其他之前 allocate 的 block 串起來

在 `test_free()` 裡面會透過 `find_header()` 算出 `block_ele_t` 這個資料結構真正的位置，並且確認是否真的存在，檢查 `magic_header` 等處理，之後檢查 footer 有沒有錯誤，跟檢查有沒有發生 buffer overflow 而放在 stack 裡面的 canary 有點像，最後把 header 和 footer 都設定成 `MAGICFREE` 之後把整塊空間釋放

在 `exception_setup()` 裡面有用到一個 `sigsetjmp()` ，如果回傳 0 的話就代表它是直接 return ，如果不是 0 就代表是使用 `longjump()` 或是 `siglongjump()` 過來這裡的，這邊利用這種方式設定一秒的限制執行時間，之後在 `qtest.c` 裡面設定 `SIGSEGV` 和 `SIGALRM` 的 handler 來處理 Segmentation Fault 和執行超時。

#### `console.c` / `console.h`
這邊使用了一個 list 紀錄指令，利用 `add_cmd()` ，在裡面放入指令名稱、執行指令的函式以及說明，之後在 `interpret_cmda()` 的時候就會去 list 中找到對應的指令並呼叫函式