contributed by < ChenBoSyun
>
linux2021
在 queue.[h/c]
完成以下要求
q_new
: 建立新的「空」佇列;q_free
: 釋放佇列所佔用的記憶體;q_insert_head
: 在佇列開頭 (head) 加入 (insert) 給定的新元素 (以 LIFO 準則);q_insert_tail
: 在佇列尾端 (tail) 加入 (insert) 給定的新元素 (以 FIFO 準則);q_remove_head
: 在佇列開頭 (head) 移除 (remove) 給定的元素。q_size
: 計算佇列中的元素數量。q_reverse
: 以反向順序重新排列鏈結串列,該函式不該配置或釋放任何鏈結串列元素,換言之,它只能重排已經存在的元素;q_sort
: 以遞增順序來排序鏈結串列的元素除了實作上述的功能外,還要考慮以下記憶體檢測的議題
list_ele_t *tail
與 unsigned int size
,為了讓 q_insert_tail()
與 q_size()
能在O(1) 時間內完成malloc
回傳值不是 NULL
)可調整程式碼風格如下:
與之相似,if (q != NULL)
可簡化為 if (q)
:notes: jserv
list_ele_t *curr
被 free
後,無法取得下一個 list_ele_t
,記得先curr->next
指派給 tmp
問題: 是否需要指派 NULL
給 queue_t*
,避免 dangling pointer
你可用設計實驗並用 ASan 檢測,看會不會遇到 use-after-free 的警告
:notes: jserv
function return
之前記得把已經配置過的記憶體 free
掉strlen()
在計算字串長度時不會包含空字元('\0'
),記得還要再加一個 byte 存放 '\0'
The strlen() function calculates the length of the string pointed
to by s, excluding the terminating null byte ('\0'). - man strlen
q_insert_tail
在 O(1) 時間內完成,在 queue_t
內加上 tail
讓它指向佇列的最後一個元素merge()
: left 跟 right 是已排序狀態,因此只要將 left right 兩個佇列的元素兩兩 (strcmp) 比較再串接即可我原先沒搞清楚 strcmp
的回傳值代表的意思,從 man strcmp 的 DESCRIPTION 也沒有說明回傳值的細節
strcmp() returns an integer indicating the result of the
comparison, as follows:
• 0, if the s1 and s2 are equal;
• a negative value if s1 is less than s2;
• a positive value if s1 is greater than s2.
參照 strcmp.c 原始碼,發現strcmp是照順序比較 str1 str2 的字元大小,
若兩個字元一樣,則繼續比較下一組字元。
值得注意的是,我在看原始碼時注意到
當下我覺得為何只針對 c1 檢查 '\0'
,後來推測是避免當 str1 str2 所有字元一樣時,可能造成 buffer overflow 問題 (*s1++
超過字串的邊界),且程式與預期的結果會不符
這邊的檢查換成 if (c2 == '\0')
也是可以的
一開始實作 merge two sorted linked list,使用的是遞迴的作法
執行測資 trace-15-perf.cmd,會出現 segmentation fault。
參考 RinHizakura 的筆記,發現有可能是因為頻繁使用遞迴導致 stack overflow
我使用 make SANITIZER=1,trace-15-perf.cmd 沒有輸出任何訊息
merge_list()
: 實作將 linked list 分成 left 和 right,在 merge_list()
的最後會呼叫 merge()
,因此 merge_list()
回傳的佇列是已排序的
開啟 Address Sanitizer 後,執行 help 命令會出現以下錯誤訊息
從錯誤訊息中得知該程式出現 global-buffer-overflow
global-buffer-overflow 是因為存取全域變數時,超過系統配置給你的記憶體範圍時,所產生的記憶體錯誤
追蹤程式碼發現,宣告全域變數 echo 是 bool 型態
呼叫 add_param
時會將 &echo
轉型成 (int *)
,但這裡還不會出現問題,因為並沒有存取記憶體的動作
在 do_help_cmd
會呼叫以下程式,%d
這個格式化輸出會讀取一個 int 的大小(4 bytes)
這樣會超過原本配置的(1 bytes)的記憶體空間
修正方法: 將 echo
宣告成 int
型態,同理 simulation
也是。