contributed by < pjchiou
>
strdup
?- clang-format 的使用方法中有提到可以與 vim 結合使用,其中第二個方法寫著可以把以下的指令加入 .vimrc
檔內,如此一來就會在存檔時自動修好格式。
但是如果你跟我一樣,最近才安裝 vim 與 clang-format 可能會跟我遇到一樣的問題。
*.c
首先我下載了 clang 整個專案之後會得到 clang-format.py
這個檔案,之後試著在 vim 內存檔,會看到以下訊息。
E319: Sorry, the command is not available in this version.
後來 google 了很久,發現是 python 版本的問題,把指令 pyf
改成 py3f
如下,就搞定了。
Two of the functions: q_insert_tail and q_size will require some effort on your part to meet the required performance standards. Naive implementations would require O(n) steps for a queue with n elements. We require that your implementations operate in time O(1), i.e., that the operation will require only a fixed number of steps, regardless of the queue size. You can do this by including other fields in the queue_t data structure and managing these values properly as list elements are inserted, removed and reversed.
q==NULL
;q->head == NULL
;因為先知道了會需要 O(1) 得到長度與 insert_tail 的操作,所以先改 structure 。
man strdup
的描述, strdup 會自己去呼叫 malloc ,並傳回一個可以被 free 的 pointer。newh->value = strdup(s)
就好,但後面會提不能用的理由,所以只能自己來。malloc
或 free
還可以用。#4 如果
q = NULL
,是不是就不能再做q->head
了?YanJiunSat, Sep 29, 2018 3:30 PM
||
左邊如果是 true 後面就不會去做了,因此沒關係。所以說if (!q || !q->head)
絕對不能反過來。可以參考 The C programming language 2.6 節的描述與範例。
More interesting are the logical operators &&, and . Expressions connected by && or are evaluated left to right, and evaluation stops as soon as the truth or falsehood of the result is known.
意即在確認結果是 true or false 的時候會立刻停下。
pjciou2018 Sep 29 Sat 15:44了解了。我英文很爛 QQ,我一直在逃避規格書。
看來我該看一下 The C programming language 了。
謝謝你,受教了。YanJiunSat, Sep 29, 2018 4:57 PM
用張圖來說明這個想法,簡單來說就是把把 *cur 走過的點轉向。
初始化的時候。
prev = cur;
cur = next;
next = next->next;
cur->next = prev;
Test performance of insert_tail, size, and reverse
–- trace-15-perf 7/7
–- TOTAL 100/100
意外發現有個 bug ,就是如果在 insert_head 與 remove_head 中使用 strdup 去複製字串,然後刪除的過程中完全不要去釋放字串的空間,還是可以拿滿分。
這個程式一共由
等九個檔案所編繹而成。queue.h 與 queue.h 是我們所寫。其餘檔案我從以下議題開始逐步分析這個程式手動輸入的時候如何做到程式如何偵錯、如何分析使用者的指令、如何管理各項參數、如何輸出、最後做到自動測試。
strdup
?strdup
首先我們從 man strdup
看
The strdup() function returns a pointer to a new string which is a duplicate of the string s. Memory for the new string is obtained with malloc(3), and can be freed with free(3).
strdup
的行為是去呼叫 malloc
並把字串複製進這個新建立的位址,最後 return 這個新建的位址。跟我們要的功能一致,但在 harness.c
內有一段。
換句話說,在 queue.c
內的 malloc
與 free
會被置換成一個自定義的函式。若使用 strdup
,就會變成在用 malloc
與 test_free
,程式就會出錯。
doubly linked list
來做。harness.c
內 block_ele_t
的宣告順序。更精確一點地說,最後一定要是 magic_header
然後是 payload[0]
。block_ele_t
有一點小小的差距,因為我們要 malloc 的空間會變,所以不能把 magic_footer
也寫進來,不過在 malloc 的時候,要留空間給 magic_footer
,因此可以看到在 harness.c
裡面寫著下方程式碼size
就是我們要的空間,最後的 sizeof(size_t) 就是留給 magic_footer
的空間。
payload[0]
的意義在於定位 *next, *prev, payload_size, magic_header 這些額外資訊在記憶體內結束的位置,本身確實不佔空間。而且這個位置就是呼叫 test_malloc
時,回傳的位置;也是呼叫 test_free
時傳入的位置。
因此我們可以有以下關係式
payload_size
bytes定義幾個變數
接下來說明整個測驗的機制,首先假設我們做了 test_malloc(10);
會 return
一個 (void *)p
,如下圖所示。內部的值,可以透過上述三個關係式去設定。
這時如果再做一個 test_malloc(5);
會變成下圖,傳回 *p
。
如果我們做了一個 free(p)
,開始檢查幾個項目
接著把這塊空間移出這個 doubly linked list ,然候真的 free 掉。
仔細觀察上述 malloc
行為可以發現,如果我們都使用 strdup
去複製字串,在 free
的時候都不要去 free
字串的記憶體,還是可以拿滿分。因為用 strdup
得到的空間,並不會在上述的 doubly linked list 內,因此偵測不到它的存在。
我的 github 內有另一個分支 NoFree ,就是利用這個漏洞拿滿分的版本。
magic_head
、然候緊接著的是我們要的空間、最後是 magic_foot
。看了siahuat0727
同學的共筆,我發現我忽略了 alignment 的問題,如果我們把 block_ele_t
改成下列方式會有什麼問題?我們的結構變為下圖
因為我是 64 位元的系統,所以會有 7 bytes 的 padding,如果是 32 位元應該只會有 3 bytes(這裡我怕有錯,希望有人手邊有 32 位元系統幫驗證) 。當結構變為這樣, $block_ele_t = &payload - sizeof(block_ele_t) 就不會成立。
別忘了, &payload
是同時是 malloc
與 free
傳出、傳入的位置,如果記憶體內的配置變成這樣,我們無法在 free
的時候從 &payload 推得 &block_ele_t 的位置。
如果改成下方 structure ,做手動對準,又會沒問題。
所以 unsigned char payload[0]
前方會是一個 size_t
的變數,這樣的設計就可以保證對準。
這個程式會把所有可用的指令、參數以及準備讀取的資料用 linked list 去存, console.h 內有以下程式碼。
而程式內靠著以下函式將全部可用的指令,在程式開始執行初期加入到這個 linked list 內。(參數的版本也很類似,就不多做解釋了)
這程式碼有點熟悉阿…跟 Week3 隨堂測驗最後一題有點像,就是由小到大排的插入排序法
另外在 console.c 內有一個 structure 用以儲存每個 input file 。一樣是用 linked list 的方式將所有的檔案連起來。( stdin
也算是其中一個檔案 )
stdin
。總結一下手動測試的流程
stdin
)quit
就會結束,並逐步釋放 cmd_list, para_list, file_list 及 我們在 queue.c 使用的空間。這兩個檔案跟其它檔比起來比較特別,兩者都沒有 #include 這個專案內的其它檔案,因此最泛用,可以拿到任何其它專案用去使用。
首先這個專案內把所有的例外狀況分級,並分別對應到不同的後續行為。
stdout
有一個比較特別的函式 vfprintf
我是第一次看到,可以先 man vfprintf
看一下其與相關函式的用法。
利用這個函式就可以做到變動參數個數的輸出,類似 printf
接下來有兩個最主要的函式
前者一旦觸發,程式一定會強制結束。使用在 malloc 空間來存指令、參數、輸入檔的時候,一旦無法拿到所需要的記憶體時;後者只有在 fatal error 時才會強制結束,其它狀況下會依使用者設定的參數決定是否輸出。這個參數可以在 ./qtest 內以 option verbose [number]
指令設定。
檔案的開頭可以看到一堆指令被塞到存指令的 linked list (我在 console.c 提過的那個)內,為什麼這些指令要寫在 qtest.c 內而不是 console.c 內?我自己的想法是因為這些指令都直接操作題目要的那個 linked list 內的元素,題目要的 linked list q 就作為一個全域變數宣告在 qtest.c 內。
getopt
函式我是第一次看到,以前不知道有那麼方便的函式可以自動解析程式代入的參數,建議跟我一樣第一次看到的人先 man getopt
看看在做什麼,對閱讀 qtest.c 會大有幫助。
qtest.c 裡大致上有兩個功能
如果我們輸入
可以看到它提供了直接從檔案讀取指令的功能。我們可以用
看 qtest 去執行這個檔案內的所有指令的過程。看到這裡對如何做自動測試已經有個底了,就是利用一個 script 去丟一堆存有預設好指令的檔案,而這些檔案就存在 traces 資料夾內。
前面幾個段落我討論了這個測驗機制的原理,但最後幾個測試是在看 performance ,這個程式利用 signal
函式來達到這樣的效果。
簡單來說這個功能可以指定當程式執行途中接收到編號 signum
訊號的時候,去執行 handler
這個函式。以下兩個 signum
在這個程式內有用到。更多 signum 可以參考這裡
signum | description |
---|---|
SIGALRM | Alarm clock (POSIX) Indicates expiration of a timer. Used by the alarm() function. |
SIGSEGV | (Signal Segmentation Violation) Invalid access to storage − When a program tries to read or write outside the memory it is allocated for it. |
在 qtest.c 可以看到以下程式碼
而 alarm(unsigned int sec)
函式可以讓我們在 sec 秒後,發一個 SIGALRM 訊號到程式。因此我們可以利用以下流程來做效能測試。
alarm(0)
取消尚未發出的 SIGALRM 。signal
設定的函式內。接下來還有最後一個問題要釐清。
如果程式進了無窮迴圈,就算發出 SIGALRM 到自定義的函式內,但是離開自定義的函式後,不是又回到了無窮迴圈內?測試還是要繼續下去吧。
以上這個問題利用 sigsetjmp
與 siglongjmp
兩個函式來處理,這兩個函式簡單來說就是跨函式的 goto 。我們觀察 qtest.c 內 do_reverse
有一段
假設我的 q_reverse
寫到進無窮迴圈,我來看一下 exception_setup
與 exception_cancel
是怎樣讓我跳離無窮迴圈?以下程式碼在 harness.c 內
我們看 man sigsetjmp
的描述,有幾個重點
setjmp() and sigsetjmp() return 0 when called directly; on the "fake" return that occurs after longjmp() or siglongjmp(), the nonzero value specified in val is returned.
The longjmp() or siglongjmp() functions do not return.
sigsetjmp
會 return 0 ,如果是從 siglongjmp
回來的話會 return val 。所以當我們執行以下程式的時候
exception_setup
#16~#22 內設定好 sec 秒(預設是 1 )內發出 SIGALRM ,然後 jmp_ready=true, return true 。trigger_exception
jmp_ready==true , 所以做 siglongjmp(env,1)
回到 exception_setup #3
的判斷式,因為這次是從 siglongjmp
回來,會 return 1 (也就是 siglongjmp
的第二個參數),所以執行 #4~#14 , jmp_ready=false 並記錄下發生的例外後, return false 。trigger_exception #41
,而是回到 call exception_setup
的地方。也就是判斷要不要做 q_reverse 之前。透過 Makefile 的內容我們可以知道輸入 make test
的時候實際上是去執行 scripts/driver.py
這個檔案。一打開我們就可以看到 15 個測試分別對應到的指令檔。許多部分都只是輸出而已,比較主要的是以下函式。
從這之中我們可以知道兩點
./qtest -v 1 -f [filename]
這樣的方式去呼叫 qtestmain
之中的 return 去判斷是否成功,所以每個測試只會有滿分跟零分兩種可能。其餘的部分就是用一個陣列 hard code 所有的測試檔,然後逐個執行上述指令。