# 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` 裡面有一段程式碼 ``` C #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 中找到對應的指令並呼叫函式