contributed by <grant7163
>
sysprog2019_q1
依據 C Programming Lab 要求。
queue_t* 內的 head 指向 一個 queue 的開頭,queue 分爲兩種類型
實作如下function並加入一些 queue = NULL 的情況處理。
先了解 Makefile 語法和示範
從老師的 github 上 fork 完 lab0-c 之後,馬上先來測試看看。
到目標資料夾下,輸入如下指令。
$make
$./qtest
結果一推錯誤訊息,不過發現一個有趣的地方,原來老師的操作範例有先加入字串處理的部份。
在 qtest 跳出程式時出現會 Attempt to free NULL 的狀況,後來去 trace qtest.c 中發現 queue_quit() 裡會執行到 free 的動作,需在 free 中加入先判斷 queue 是否為 NULL, 否則會造成 double free 的狀況。
想法是從 queue 的 head 一邊依序搜尋一邊釋放 head 裡的 value 與 head 的記憶體空間,最後在釋放整個 queue 的記憶體空間。
依據 linux man
$ man strcpy
The strcpy() function copies the string pointed to by src, including the terminating null byte ('\0'), to the buffer pointed to by dest.
The strncpy if there is no null byte among the first n bytes of src, the string placed in dest will not be null-terminated.
使用 Naetw 同學提供的指令,額外測試 memory leak。
開啟 Address Sanitizer 分析工具,幫助釐清記憶體操作問題。
發現在 trace17 有記憶體操作錯誤的問題,從如下訊息指出 console.c 中的 simulation 變數發生 global-buffer-overflow 。
接著從 console.c 中收尋 simulation 變數在哪裡被用到,發現在 init_cmd()
函試中會呼叫 add_param()
函式且該函式會將 simulation 變數強制轉型為 int* 型別帶入,由於當初 simulation 是以 bool 型別來做宣告 (1 byte),但在這裡是以 int 型別去讀取 simulation 的記憶體位址 (4 bytes),造成在讀取的時候超出可讀取的範圍。
在剛開始 main 中使用 getopt 解析執行程式中的 commandline arguement,在做出相對應的 function。
Each option character may be followed by a colon ( : ), indicating that this option expects an argument.
If an option was found, the option character is returned as the function result. If the end of the option list was reached, getopt() returns –1. If an option has an argument, getopt() sets the global variable optarg to point to that argument.
接下來是初始化的部份,在 qtest.c main 中主要初始化的函式有 queue_init, init_cmd, console_init。
初始化一個測試用的 link list q,紀錄錯誤次數的 fail_count,並註冊二個 signal handler。
主要目的為當觸發如下條件時,可以在 signal handler 裡作想要觀察的訊息或提醒使用者
$ man 7 signal
Signal Value Action Comment
SIGALRM 14 Term Timer signal from alarm(2)
SIGSEGV 11 Core Invalid memory reference
簡單作個小實驗
註冊一個 signal handler,當有 segfault 發生時印出訊息。
宣告一個 pointer,並 dereference 為0。
確實當有 segfault 發生時有印出訊息來,不過有趣的是會進入一個無窮迴圈的狀態。
後來去查閱 linux man,看到一段說明從 SIGSEGV signal handler 返回是未定義行為。
$ man 2 signal
According to POSIX, the behavior of a process is undefined after it ignores a SIGFPE, SIGILL, or SIGSEGV signal that was not generated by kill(2) or raise(3).
在這篇 stackoverflow 中看到一段說明,在 x86 平台下, cpu 會重新執行這道錯誤指令的關係。
在 signaltest_handler 中加入 exit 讓程式直接跳出結束。
確實就沒有在無窮迴圈的狀態了。
在 qtest.c 的 signal handler 中最後會調用到 siglongjmp(env, 1) 這個函式。
查閱 linux man 了解相關使用說明
do_XXX 系列的函式,以 do_new() 為例 :
exception_setup() 主要作三件事
exception_cancel() 主要作二件事
當執行 exception_setup() 之後,若在 do_new() 中發生記憶體存取錯誤或超時的話,就會觸發如下流程 :
signal handler() -> siglongjmp() -> sigsetjmp() -> report_event() -> exception_cancel()
使用 sigsetjmp() and siglongjmp() 這二個函式也可以防止觸發 SIGSEGV signal handler 條件之後會進入無窮迴圈的狀態。
使用 qtest.c 的 exception 機制來作實驗觀察一些全域/區域/暫存器/ volatile 變數的變化。
印出來的結果發現只有 register 裡面的資料會恢復到先前的資料。
使用 GDB 觀察 sigsetjmp() 存放的訊息。
設 break point 在 exception_setup 函式進入點,將指令停在進入 __sigsetjmp 之前
接著到 __sigsetjmp 進入點
觀察此時 sp 往下位移 8 byte 並保存 __sigsetjmp 返回後下一道指令的位址
主要 __sigsetjmp 將資料複製到 env 中 __jmp_buf[8] 的部份:
利用 GDB 觀察 sigsetjmp() 確實保存當下在 exception_setup() 的 stack frame 與 sigsetjmp() 返回後的下一道指令。
沒想到複製 env 中 __jmp_buf[8] 的部份資料會先經過加密的步驟!
init_cmd 函式中主要是增加 command 與 parameter。
並在 consloe.h 中使用到 function pointer 的技巧,將函式的返回值與代入參數的資料類型一致就可以方便的新增新的 command。
用一個全域變數 cmd_list 紀錄已經加入的 command。
在 add_cmd 會依照 name string 由小到大的排序,並藉由 last_loc (pointer to pointer) 間接的把新的 command 加入到 cmd_list。
依據輸入的命令 make test
,去 makefile 中找尋如何執行自動化測試程式
在 makefile 中發現是以 scripts/driver.py
調用 qtest 進行測試
在 driver.py
中定義一個 class Tracer 並初始化
在 run 中主要執行測試程式的部份
self.runTrace()
會藉由 subprocess.call()
來執行 qtestsubprocess.call()
實際上會執行如下命令
增加自己的腳本
traceDict
中加入名稱 : 16 : "trace-16-user"traceProbs
中加入名稱 : 16 : "Trace-16"trace-16-user.cmd
成功加入並執行了
依據 linux man page 說明
select()
能夠監控多個 file descriptor 且會被 blocking(除了 timeout = 0),直到有 file descriptor 可以進行操作或被 interrupt 打斷或者超時才會返回。
select()
的返回值
fd_set
的相關 MACRO
當
select()
的返回時 3 種 set 會被修改(保留就緒的 fd),因此在呼叫select()
之前必須對 set 重新初始化。
在 qtest.c
中會呼叫 run_console()
,接著 push_file()
檢查是否有檔案輸入,若無則為鍵盤輸入(STDIN), while 迴圈判斷命令是否執行完成並呼叫 cmd_select()
。
在 cmd_select()
中將目標 fd 存在 infd 變數並加到 readfds 中。
接著透過 select()
判斷 readfds 中的 file 是否可讀,若檔案可讀時會從 blocking 中解除並回傳 >0 的結果。讀出 file 中的 commmand 且解析對應操作,並將該 fd 從 readfds 移除。
RIO 套件是 CSAPP 中提供的一種 system I/O 套件,基於一些情境下於原本的 read 與 write 系統呼叫上再做一層包裝(參考 csapp.c 與 csapp.h)
依據 linux man page 說明,回傳值會有以下幾種狀況
在一些情境下(network socket or terminal),對於 read 的操作可能一次只需讀少量的 byte 數,如此一來會因為頻繁的呼叫 read(system call) 導致程式會頻繁在 user mode and kernel mode 之間作切換而造成效能低落。
對於 read 回傳值也做相對應的處理,如遇到訊號中斷則會自動在重讀一次
在 harness.h 可以看到本次作業中使用到的 malloc
, free
其實都被改成呼叫 test_malloc
, test_free
在 test_malloc()
函式中看到是用一個全域 allocated 變數( doubly-linked list 結構)來管理配置記憶體的一些資訊
從 block_ele_t 結構中看到一個特別的成員 unsigned char payload[0];
,經 google 搜尋了解原來是用到 GCC 中一個叫 Arrays of Length Zero 的技巧
語法跟 C11 有以下幾點的不同
- As a special case, the last element of a structure with more than one named member may have an incomplete array type; this is called a flexible array member.
- In most situations, the flexible array member is ignored.
- In particular, the size of the structure is as if the flexible array member were omitted except that it may have more trailing padding than the omission would imply.
- If this array would have no elements, it behaves as if it had one element but the behavior is undefined if any attempt is made to access that element or to generate a pointer one past it.
valgrind 架構為一個主要運算核心,在搭配一些週邊的工具,核心會模擬 CPU 的環境,並提供服務給週邊工具,週邊工具則類似於一個模組,利用核心提供的服務來完成各種特定任務,也可以增加自己的工具進去測試。
在本次作業主要使用 Memcheck 來偵測記憶體漏洞
先單純使用 ih 命令並搭配 valgrind 中的 massif 觀察記憶體使用狀況
使用 massif-visualizer 圖形化界面,觀察使用 ih 命令增加10000個亂數所產生出的字串,記憶體消耗量最高達到將近 1 MB,在藉由 free cmd 將所配置的記憶體釋放。
嘗試使用 lab0-c 中所用到 Arrays of Length Zero 的技巧,改寫 q_insert_head
函式
首先修改 list_ele_t
中的 value 為 incomplete array type 並為此結構的最後一位成員。
原始要為 newh
與 newh->value
呼叫2次 malloc()
來配置記憶體空間,使用 Arrays of Length Zero 的技巧改為1次就一起將 newh
與 newh->value
配置記憶體空間。
如上相同情境下( ih 命令增加10000個亂數所產生出的字串) 觀察記憶體使用狀況,從下圖觀察記憶體消耗量最高達到 547 KB,發現整體程式執行時間有縮短,不過記憶體消耗有很明顯差別,將近比原始的版本少了快一半的記憶體使用量。
這次直接使用 trace-16 的測項來觀察記憶體使用狀況
原始版本
使用 Arrays of Length Zero 的版本
持續更新中