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 的好機會
:notes: jserv
接著把在排序中採用到的 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
回去複習機率統計,思考上述做法是否合理,若有疑慮就提出論證和實驗
:notes: jserv
其中為了方便取得到 payload
的尾端來指派 magic number (MAGICFOOTER
),qtest
實作了 find_footer
函式,如下
藉由傳進來的 block_ele_t *
的開頭,在加上 payload size 和該 structure 本身的大小來取得到 payload
的尾端