contributed by < PigeonSir >
kk908676
部份 commit message 可以描述的更加詳細
分配 list_head 的空間,再透過 INIT_LIST_HEAD 將 prev 和 next 指向自身。
後來加入對 malloc 失敗時做處置, c 語言規格書 ISO/IEC 9899:2024 7.24.3 節的第一段提到
If the space cannot be allocated, a null pointer is returned.
在後續的實作中遇到 malloc 都要這麼做
commit d95ee65
再新增節點時需要字串的複製,作業解說提到的 strcpy 屬於危險的操作,原因如下
The strcpy built-in function does not check buffer lengths and may very well overwrite memory zone contiguous to the intended destination. In fact, the whole family of functions is similarly vulnerable: strcpy, strcat and strcmp.
CERN Compter Security
故選擇使用 strncpy ,需注意當愈複製的長度小於目標地址配置的大小時會自動補 '\0' ,反之則會被截斷,所以複製完後再強制將最後一個字節設為 '\0'
後續發現以上方法未能通過 constant time 測試,初步推測為 strlen() 和 strncpy() 造成的,因為這兩個函式會隨著字串的長度增加執行時間
在 csappE3 5.4 節中提到 strlen() 對執行時間的影響, 並給出 strlen() 的簡單版本如下 :
而觀看手冊中 strncpy 的實現方式,其執行時間亦會使用 strlen,故推測這兩個函式造成 insert_head 和 insert_tail 無法通過 constant time 測試。
待後續閱讀論文以及研究 simulaion 的測試條件後再著手改善
commit 6530b15
研究關於字串複製的方式,發現 strdup 可以更精簡程式碼,但還是無法通過 constant time 的測試
commit 785ea1b
參考 你所不知道的 C 語言: linked list 和非連續記憶體 當中對於快慢指標的操作,在節點個數 \(n\) 為偶數時移除第 \(n / 2 + 1\) 個節點
head
為 NULL
或 queue 為空,直接返回 false
。temp
為 head->next
的指標的指標,作為慢指標。fast
指標為 head->next
,作為快指標。head->prev
和 node5->next
temp
: *temp
為下一個節點的記憶體位置,故 temp = &(*temp)->next
會將 temp
指向下一個節點的 next
fast
: 執行 fast = fast->next->next
讓 fast
指向下下一個節點fast
為最後一個節點或 head
時跳出迴圈temp
指向 node2
的 next
,所以移除的節點是 *temp
,但要先定義另一個節點 del
指向 *temp
,才能使用 list_del
和 q_release_element
移除 del
commit b99d99b
在課堂上有提到 q_swap 和 q_reverse 都只是 q_reverseK 的特例,實現 q_reserveK 後 q_swap 和 q_reserve 分別只要將 K 代入 2 和 queue size 即可
以 k = 3 為例
end
k - 1 次,此時 start
和 end
間的區間即要反轉的節點temp
指向 end->next
,以更新下一輪的 end
start->next->prev
commit 9b1be79
新增函式 mergeTwo
以合併兩個已經排序完成的 queue
, 在 q_sort
和 q_merge
中都需要使用到 mergeTwo
,參考教材中的實作方式合併兩個斷開且單向的鏈結串列並在過程中僅維護 next
指標,升序排列的合併流程如下
struct list_head * L, R
: 分別指向兩個生序排列的鍊結串列的第一個節點bool descend
: 為 true
時使用降序合併,此範例中為 false
temp
最初為 NULL
,它將存儲合併後的新鍊結串列的起始節點。indirect
是一個指標的指標,用來追蹤新鏈表的尾端,以便逐步建立新的鏈表。node
是 指標的指標,其值為 &left
或 &right
,指向該輪中應該接到 indirect
上的節點strcmp
的結果選擇節點,範例中 strcmp
結果為負,因此在升序排列的情況下,node
和 indirect
指向 L
indirect
存放的是 temp
的記憶體位置,因此 *indirect = *node
等價於 temp = L
,後續操作中 temp
的值將不再改變indirect
指向合併完的節點的 next
的記憶體位置*node
(即更新 L
)指向該鍊結串列的下一個節點L
或 R
為 NULL
後跳出迴圈L
或 R
中剩餘的節點接上 indirect
並返回 temp
commit49bd087
q_merge 會用到結構體 queue_contex_t ,其中保存了 queue 的 size, id 和 queue 的 head , 並透過 chain 鍊結。
含有兩個 queue 的示意圖如下
先透過最容易實現的方法實做,將每一個 queue 都和第一個 queue 執行 mergeTwo
list_srot 內包含三個函式 : merge, merge_final 和 list_sort ,將這些函式修改後加入 queue.c
在 list_sort.c 中,cmp 參數是一個比較函式的指標,被定義於 list_sort.h:
上述程式碼定義了一種函式指標類型 list_cmp_func_t 指向一個接收三個參數並回傳 int 的函式:
這樣做是為了在呼叫 list_sort() 時,傳遞不同的比較函式來決定排序方式。而我選擇直接在 queue.c 中定義比較函式為一個全域的函式,直接在排序的過程中呼叫它,參考 list_sort.c 中對於比較函式的描述:
The comparison function cmp must return > 0 if a should sort after b (”a > b” if you want an ascending sort), and <= 0 if a should sort before b or their original order should be preserved. It is always called with the element that came first in the input in a, and list_sort is a stable sort, so it is not necessary to distinguish the a < b and a == b cases.
The comparison function must adhere to specific mathematical properties to ensure correct and stable sorting: - Antisymmetry: cmp(a, b) must return the opposite sign of cmp(b, a). - Transitivity: if cmp(a, b) <= 0 and cmp(b, c) <= 0, then cmp(a, c) <= 0.
This is compatible with two styles of cmp function: - The traditional style which returns <0 / =0 / >0, or - Returning a boolean 0/1. The latter offers a chance to save a few cycles in the comparison (which is used by e.g. plug_ctx_cmp() in block/blk-mq.c).
考量 cmp (a, b)
當 a > b
若先計算 ret = a - b ,升序時回傳 ret (正數) 因為 a 要排在後面,而降序時回傳 -ret (負數),實作細節如下
commit af0ee40
在 console_init() 中新增命令 listSort ,並新增函式 do_listSort ,其內容和 do_sort 相同。
撰寫比較兩個排序法執行時間用的 command file
此測試會對四種不同數量的元素(10,000 / 50,000 / 100,000 / 500,000)執行排序,並計算:
測試結果如下:
第一次排序
資料數 | q_sort | list sort |
---|---|---|
10000 | 0.0044 | 0.0034 |
50000 | 0.0454 | 0.0362 |
100000 | 0.1230 | 0.090 |
500000 | 0.7658 | 0.5580 |
反轉後排序
資料數 | q_sort | list sort |
---|---|---|
10000 | 0.0028 | 0.0012 |
50000 | 0.0530 | 0.0418 |
100000 | 0.1442 | 0.1052 |
500000 | 0.9460 | 0.6144 |
發現 list sort 在各個資料數下都快於 q_sort
接下來運用效能分析工具 pref 分析此效能
,執行 500000 個元素的排序五次,監控 instructions, cycles 和 branches
list sort
q_sort
從 cycles 來看,q_sort 需要更多的 CPU cycle,且執行時間比 list sort 長。
為了分析兩種排序法進行比較的次數,更新 q_sort
的比較方式為呼叫 cmp
commit 4c2ac8b
透過 perf probe 加入觀察點於 cmp
但加入觀察點後執行 record 發現次數為 0
發現 cmp
的呼叫次數為 0,表示 perf probe 未能成功攔截 cmp
,需要進一步調查問題可能的原因
該論文介紹了名為 dudect 的工具,主要用來檢測某段程式碼是否以 constant-time 執行,有別於傳統檢測方式,dudect 採用的是「統計分析」的方法而非傳統的「靜態分析」,具體步驟如下:
在 qtest.c 中函式 queue_insert
和 queue_remove
都會依據全域變數 simulation 決定是否進行 constant time 檢查,且檢查都是發生在實際插入/移除節點之前,檢查方式如下
定義於 dudect/constant.h
在 fixture.h 展開成函式
在 fixture.c 定義函式的內容
經過展開後變為呼叫 test_const 的函式,其中 DUT() 代表該測試的編號