contributed by < MetalheadKen
>
Some of the skills tested are :
Implementing a queue
Resources
The task is to modify the code in queue.h
and queue.c
to fully implement the following functions
q_new
: Create a new, empty queueq_free
: Free all storage used by a queueq_insert_head
: Attempt to insert a new element at the head of the queue (LIFO discipline)q_insert_tail
: Attempt to insert a new element at the tail of the queue (FIFO discipline)q_remove_head
: Attempt to remove the element at the head of the queueq_size
: Compute the number of elements in the queueq_reverse
: Reorder the list so that the queue elements are reversed in order.q_sort
: Sort elements of queue in ascending order.Precautions
NULL
. An empty queue is one pointing to a valid structure, but the head
field has value NULL
malloc
to allocate space and then copying from the source to the newly allocated spaceq_insert_tail
and q_size
will require that your implementations operate in time q_reverse
should not allocate or free any list elements. Instead, it should rearrange the existing elementsqueue.h
依據題意,為了讓函式 q_insert_tail
和 q_size
的時間複雜度為 ,在 struct queue_t
裡新增成員 tail
和 size
,使得在 runtime 的時候可以動態紀錄 queue 的尾端和其大小
q_new
需注意若 malloc
失敗時需回傳 NULL
q_free
釋放 queue 的空間,注意記得一併釋放節點和字串所佔的記憶體空間
q_insert_head
malloc
失敗時,在回傳 NULL 前需釋放之前已經配置好的記憶體空間
goto
來作錯誤處理,可參考 goto in Linux kernel coding style 章節q_insert_tail
q_insert_head
的實作方向相同tail
來串接新節點tail
的 data type 為 list_ele_t**
,使得可以減少 branch penalty,可參考
q_remove_head
sp
不為 NULL 時代表需把移除的字串複製到 sp
中sp
的大小,因而最多只需複製長度為 bufsize - 1
,並注意要在結尾上加上 terminating null byteq_size
size
動態紀錄 queue 的大小,並在此函式直接回傳 size
的內容new
command 的情況下直接使用 size
command,所以需判斷若 queue 為 NULL queue 或 empty queue 則直接回傳數值 0q_reverse
prev
, curr
, next
來紀錄反轉的過程
prev
紀錄 queue 前一個的節點curr
紀錄 queue 當前的節點,在反轉過程中,curr
的下一個節點應指派為 curr
的前一個節點next
紀錄 queue 下一個的節點head
和 tail
需重設方向q_sort
merge_sort
裡面透過 fast
和 slow
pointer 來找到該 list 的中間點為何這邊採用 sourcefrog/natsort 所實作的 natural sort 的 compare function - strnatcmp
。從原專案中取得 strnatcmp.[ch]
後放入 lab0-c
的專案中。
這邊為了明確的表示是使用別人的專案,原本是想採用 git submodule 的方式建構的,但是考慮到若要對 natsort 專案做改動,勢必要 push 回去到原專案中,或者在當初 submodule init 時只能指定 fork 後的專案,但都相對的要麻煩許多。
不知道有什麼方式可以除了把有 reference 到的專案之相關訊息寫進 commit message 以外達到明確的使用到以及隨時跟新進度在別人的專案上。
MetalheadKen
這是練習撰寫清晰的 git commit messages 的好機會
接著把在排序中採用到的 strcmp
一律改成 strnatcmp
qtest.c
queue.c
更改 Makefile
,使其可以編譯 strnatcmp.c
Makefile
為了對現有的 natsort 做測試,增加新的 trace file
traces/trace-18-natsort.cmd
script/driver.py
對 trace-16-perf.cmd
採用到的 RAND
提供英文與數字的亂數排序,其實只要新增數字到 charset
就可以了
qtest.c
執行 make test
後出現以下錯誤,依錯誤訊息可得知為超時
這是因為在 natsort 中所使用的 strnatcmp
比 glibc 所提供的 strcmp
的執行時間還要長的緣故。為了解決這個問題,這邊採用的方法為新增一個新的 command option time
,藉由 option time <limit=1>
可以指定在這次測試中所會參考的 time limit。
qtest.c
為了要讓 time_limit
可以動態更改,必須把 time_limit
改為 global variable
harness.c
harness.h
加入 option time
到會因為 natsort 的緣故而造成 Time limit exceeded 的 trace 中
traces/trace-15-perf.cmd
執行 make SANITIZER=1 test
後出現下列錯誤
先用 GDB 定位問題
從這邊可以知道由於 simulation
從 bool
轉成 int *
並存入 valp
,之後當直接 dereference 的時候就會因為要取出 4 bytes 的資料而存取到不該存取的地方故造成 buffer overflow
為了要解決 global-buffer-overflow,我們需要把轉型成 int *
的地方改為 void *
,根據 C99 規格,pointer to void 做為一個 generic pointer 可以把原本的 object type 轉成 pointer to void 再轉回來。藉由於此,我們可以透過 pointer to void 來做到不同的 data type 的存取
C99 Spec 6.3.2.3:1 [Pointers]
A pointer to void may be converted to or from a pointer to any incomplete or object type. A pointer to any incomplete or object type may be converted to a pointer to void and back again; the result shall compare equal to the original pointer.
除了 void *
來儲存各種的 data type 以外,還需要一個 variable 來儲存原本的 object 所佔的大小。最後,根據上面所述,我們需要修改以下動作來解決所需的問題
PELE
來儲存 void *
和原始的 object sizevoid *
和原始的 object size 的動作void *
可以透過原始的 object size 來轉型回原來的 data type修改如下
console.h
console.c
qtest.c
$ sudo apt install massif-visualizer
$ massif-visualizer massif.out
一開始使用者執行 qtest
後,輸入命令時,會先執行 console.c
中的 interpret_cmd
並呼叫 parse_args
來將輸入的字串以空白為區隔,轉換為 argc
和 argv
,如下
之後在函式 interpret_cmda
中,利用迴圈走訪 singly linked list,並利用 strcmp
找出函式相對應的字串。可以發現在 qtest
中使用函式指標的方式可以很簡單方便的維護使用者可輸入的命令
在 qtest
中有提供參數 -f <filename>
來讀取 trace file。當使用者輸入命令後,在 qtest.c
中的 main
函式會呼叫 getopt
來解析使用者先前輸入命令的後面所添加的參數,節錄如下
getopt
是一個可以很方便的去 parse 從 command line 傳過來的參數的函式,該函式會一直讀取參數直到沒有更多的參數可以讀時才回傳 -1
int getopt(int argc, char *argv[], const char *optstring)
int argc
: the argument count passed to the main()
functionchar *argv[]
: the argument array passed to the main()
functionconst char *optstring
: a string containing the legitimate option characters
getopt
回傳數值後
optstring
找不到 option 字元則回傳 ?
,在 optstring
設定需帶參數的 option 沒有帶參數的話則回傳 :
optarg
變數儲存該 option 後面所帶的參數optind
變數儲存下次呼叫 getopt
時要處理的 argv 的 indexoptopt
變數儲存當 getopt
找不到 option 字元或是缺少某些參數時的該 optiongetopt
是 POSIX standard 但是並不是 C standard 並在 glibc 實作中的某些行為是 GNU extensions,這點需要特別注意在 console.c
中定義以下 structure 來儲存每個要使用的檔案的 file descritptor
RIO 在 CS:APP 第 10.5 章提及,全名為 Robust I/O
Ref: System-Level I/O (preview version)
並在 push_file
函式中把開啟檔案的 file descriptor 放進 struct RIO_ELE
中的 fd
,若無指定開啟檔案的路徑則選擇為標準輸入 (也就是 stdin
)
harness.[ch]
中藉由替換掉 malloc
和 free
的實作方式使得可以檢查到 allocation error
從 harness.h
中可以見到 qtest
使用 macro 來把 malloc
和 free
替換成 test_malloc
和 test_free
而從 test_malloc
所配置出來的記憶體都會被紀錄在 struct BELE
中,structure 在 harness.c
中定義如下並以 doubly-linked list 來串接節點
在 structure 中 payload[0]
是一個 struct hack,在 GCC manual 中稱呼為 Arry of Length Zero,藉由這種方式可以做到讓 structure 中的成員可以動態的配置記憶體又不用因為多次呼叫 malloc
造成記憶體碎片化
用法如下
這樣的手法其實就是利用 GNU C compiler 預設不會去檢查 Array index out of bounds 的問題來做到的,但是使用這個技巧需要思考以下的問題
sizeof
不能用在 incomplete type 上Note that clang does support flexible array members (arrays with zero or unspecified size at the end of a structure).
clang does not support static initialization of flexible array members. This appears to be a rarely used extension, but could be implemented pending user demand.
另外在 ISO C90 可以使用 Array of Length One 來做到同樣的事情,而從 ISO C99 開始支援 Flexible Array Members,請參照
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.
test_malloc
把經由 malloc
配置出來的新的記憶體空間,將其串連到 doubly linked list allocated
中,其中配置出記憶體空間的寫法如下
可以看到除了 size
和 sizeof(block_ele_t)
以外,還多了 sizeof(size_t)
,這是因為在 qtest
中,藉由在尾端多配置出一個空間並填入 magic number 來查看若當該數值有被更動過的話,即表示出現 memory corruption (array access out of bounds),以及偵測是否是由 test_malloc
配置出來的記憶體空間,而前一個成員 magic_header
也是基於此用途的。harness.c
中的 test_malloc
節錄如下
在 fail_allocation
中,實作了當亂數產生出來的數小於 0.01 乘上預先設定好的失敗機率 (fail_probability
) 的話,即 malloc failure,為何需要如此實作?
MetalheadKen
回去複習機率統計,思考上述做法是否合理,若有疑慮就提出論證和實驗
其中為了方便取得到 payload
的尾端來指派 magic number (MAGICFOOTER
),qtest
實作了 find_footer
函式,如下
藉由傳進來的 block_ele_t *
的開頭,在加上 payload size 和該 structure 本身的大小來取得到 payload
的尾端