contributed by < ChihAnLin0607
>
最終目標為實作一個queue,結構示意圖如下:
不過整個程式結構已經完成,只需要修改、實作以下功能就可以:
make之後執行qtest,可以進到測試環境,輸入help可以查看可用指令,包含用new創立新的queue、ih插入資料到queue的頭等等。除此之外,也可以用make test讀取traces資料夾內預先些好的測試指令,進行測試並且評分。
當我push時,我發現我沒有在branch上面,如下方gitk的截圖:
原因:
是開發過程中(上圖中master位置的commit),曾使用git checkout $(commit的SHA1)的方式切換到較早的commit,然後在用同方法切換回原本的commit。
而checkout到別的未被任何分支指向的commit時會出現以下訊息:
簡單來說就是在告訴我,我正處於「斷頭(detached HEAD)」狀態,而斷頭是指當下這個 HEAD沒有指向任何的分支。換句話說,唯一的master分支是指向 commit message為''Implement Reverse''的commit,當我切換到之前的commit時,HEAD就離開了唯一的分支,造成斷頭狀態。另外值得一提的是,就算我是用 checkout $(commit的SHA1)的方式回到 master分支指向的 commit,git還是不會判定我離開斷頭狀態,雖然上方第一張圖看起來全部的commit都是在同一條線上,但其實邏輯上來說,master以上的是另外一個分支,如下方示意圖:
所以當時回到master分支的正確方式應該是要用git checkout master、用git checkout $(分支名稱)的方式回去才對。
解決:
其實解決辦法就在上方git的敘述中,我只需要在現在的位置建立一個暫時的新分支,然後跟 master分支做 merge,最後在刪除這個新分支就可以了。
最後成功的將master指向最新的commit了:
參考:
新增 tail指標指向 queue的最後一筆資料,這樣能讓q_insert_tail的時間複雜度為O(1),只要直接對tail做操作就好。
size則是紀錄queue中資料的數量,為了是讓q_size的時間複雜度為O(1)。
在#16取得s的長度時,原本是用sizeof(s)來做取得,卻發現不管怎麼樣都是得到8,也就是s本身這個指標的大小,稍微整理一下後發現:
明明都是在sizeof內放一個指向一段記憶體空間的指標,為什麼一個就是得到該記憶體空間的大小,另一個就是得到該指標本身的大小呢?
為了釐清為什麼,我試著去查sizeof的定義,結果發現他並不是一個巨集甚至函式,他就跟加減乘除的符號一樣,對編譯器來說只是一個運算子,基本上他的值會在編譯階段被算出來(說基本上是因為C99新增了對動態宣告陣列做sizeof的功能)。
了解sizeof是什麼之後,我得到了以下的推測:回到上面的例子,在編譯階段時,因為array的空間是被靜態配置的,編譯器已經能夠確定他所佔用的記憶體空間,就能夠確定sizeof(array)為100;但是ptr指向的記憶體空間是動態配置的,在編譯階段無法確定他是否能夠成功利用malloc取得想要的記憶體大小,malloc也許會因為種種原因失敗,所以編譯器並無法確定ptr執行期間指向的記憶體大小為多少(甚至會不會指向記憶體位置都不確定),只好退而求其次的將sizeof(ptr)算成ptr本身的大小。
過去總以為array和指標完全是同一件回事,原來在sizeof這件事上這兩者的行為並不一樣。
參考:sizeof- function or macro? [duplicate]
一、
#4原本是寫成下方這樣
結果測試發現如果q是NULL,就會跳出對NULL指標做操作的錯誤,但反過來寫成if (!q || !q->size)
就沒有問題,這很明顯是因為在判斷||兩旁的expression時,會先判斷左邊的,如果他是True,才會在繼續判斷右邊的。
不過不放心還是去查了cppreference,也得到了證實確實如此,除了||,做&&運算時也是一樣,若左邊判斷為0,則右邊完全不會被計算。這稱為 short-circuit evaluation。
二、
一開始reverse採用的方式為,先建立一個長度和queue內資料數一樣的陣列,將queue內的資料按順序放入,然後在從array後方開始重新建立queue。
不過這樣會好需要 q->size的8倍的記憶體空間,在最後一項測試中,將會進行一個長度為2000000的queue反轉,這樣就需要16MB的記憶體空間,會產生「程式記憶體區段錯誤(core dump)」的錯誤。
研究了一下到底多少以上的記憶體空間才會造成區段錯誤,發現ulimit可以告訴我一些相關的資訊:
其中比較關心的是 stack size,其大小為8 MB。但首先要先確定動態配置的array其記憶體位置是放在stack中而不是heap中,所以做了以下的測試:
知道foo的參數n會放在esp+4、也就是stack中;ptr指向一個用malloc配置的記憶體,然後malloc出的空間會配置在heap中。結果顯示array位置和n非常靠近,因此判斷動態配置的array仍然是放在stack中。
所以說若我的q_reverse若要求了16 MB,明顯超過ulimit -a告訴我的stack size 8 MB,一定會產生錯誤。
待解問題:
查看Makefile內的test命令:
其程式內容摘要如下:
一、
在qtest中有以下程式碼:
原本我來寫的話應該會寫成以下這樣:
qtest中的程式碼利用 &&避開 if判斷式,我想可樣降低branch-miss的發生。
二、 Exception的處理
一開始就會先登入兩個 signal的信號處理函式:
由上方程式碼看的出來,其實兩個信號處理函式都是呼叫trigger_excption,只是輸出的信息不一樣而已。
SIGALRM是由函式 alarm發出,當呼叫 alarm(n)的 n秒後,就會發出 SIGALRM信號。
qtest在進行任何 queue的操作(我們實作的內容)前,都會先呼叫 exception_setup,替接下來的高風險行為做好準備:
#3的sigsetjmp很重要,他能夠將當下的環境紀錄下來,並在其位置做個標記,供之後呼叫siglongjmp時能夠跳回該位置。另外當呼叫sigsetjmp的時候,他會回傳0,但如果是透過longjmp呼叫,他就會回傳一個非零的數字,所以上方#3和#15的 if els條件式就是利用此特性區分。
建立好環境紀錄後,如果有設置時間限制,也會呼叫 alarm(time_limit),讓程式於time_limit秒後,發出SIGALRM,並丟出「ERROR: Time limit exceeded.」。
接下來以q_new當作例子:
exception_setup會在實際操作(q_new())之前被呼叫,他不但用sigsetjmp紀錄了當前環境,還根據 time_limit值設定了 alarm,所以若q_new的執行時間超過這個time_limit,就會丟出SIGALRM信號;或是q_new執行期間做了不正確的記憶體操作,就會出了SIGSEGV信號。不論是丟出哪個信號,因為之前queue_init有登入其相對的處理函式,所以會跳去執行trigger_exception:
如果之前已經有使用 siglongjmp的紀錄,那 trigger_exception就會呼叫siglongjmp跳回之前紀錄的點,也就是執行 q_new()前的exception_setup()中,然後使他回傳 false,跳過q_new(),然後從do_new()中回傳。
簡單來說qtest會在高風險程式執行前先紀錄位置,當該程式真的發生問題時,就jmp回紀錄的位置與環境,然後繞過有問題的程式繼續執行。
在進行較大筆資料的測試時(例如 trace-13-perf.cmd中的 ih doplhin 1000000),使用Valgrind會丟出「ERROR: Time limit exceeded.」的錯誤,但是如果不用 Valgrind的話就不會。稍微查了一下,雖然 valgrind的使用不需要重新編譯,他會參雜新的指令到執行檔中,然後在一個虛擬的 CPU上面執行新程式碼,所以我猜這就是為什麼會造成時間過長的原因,因為多了許多valgrind的指令。
但還是要做記憶體檢查,所以決定將qtest中的時間限制加大,他的定義在 harness.c中,修改time_limit的值就可以增長時間限制了。
參考:Using and understanding the Valgrind core