Try   HackMD

2018q3 Homework2 (lab0)

contributed by <AlecJY>

commit message 中,將 "Complete" 改為 "Implement" 更為適當
課重助教

好的,謝謝助教的建議
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-commitcommit-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.cqtest.c 都有定義 INTERNAL 以避免使用 test_malloc()test_free()

test_malloc() 裡面會檢查現在是否處於 noallocate_mode ,並根據機率隨機決定是否要讓 malloc 強制失敗,之後會建立 block_ele_t 的變數 new_blocktest_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 裡面設定 SIGSEGVSIGALRM 的 handler 來處理 Segmentation Fault 和執行超時。

console.c / console.h

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