contributed by < Tonr01 >
建立虛擬機
設定硬碟大小
設定存儲裝置,並選擇下載好的 Ubuntu 版本
因為是在虛擬機上分割磁區,不會有 EFI 跟 Bios ,所以都須自己分割出來
一開始最簡單的想法是,配置記憶體給head,並檢查是否配置成功。
出現了 Segmentation fault occurred. You dereferenced a NULL or invalid pointermake
,再看完程式碼的 comment Notice: sometimes, Cppcheck would find the potential NULL pointer bugs
與巨集後,發現我忽略了 pointer 的指向。
於是加入 INIT_LIST_HEAD(head);
,將 head 的 prev 與 next 都指向自己。
一開始先檢查 list 是否存在,若不存在則無須進行 q_free
,再看完 list.h
定義的巨集後,發現 list_for_each_entry_safe
適合用來走訪每個 entry
,再使用 q_release_element(entry);
來釋放該 entry
的 entry->value
及 entry->list
,最後將 head 也釋放掉,釋放整個 list。
首先先檢查 list 是否存在,再配置記憶體給新的 entry
,並檢查 entry
與 entry->value
的空間是否配置成功,將節點的value值用strdup(s);
將s的值複製給它,最後將new_element
用list_add
加入到list開頭的位置上。
有出現 Test of malloc failure
錯誤訊息,才發現 entry
裡的 entry->value
的空間也可能配置失敗,於是加入配置記憶體的檢查。
修改後。
大致上與 q_insert_head
思路一樣,首先先檢查 list 是否存在,再配置記憶體給新的 entry
,並檢查 entry
與 entry->value
的空間是否配置成功,將 entry->value
用 strdup(s);
將s的值複製給它,最後將 new_element
用 list_add_tail
加入到list最後的位置上。
一開始先檢查 list 使否存在與 list 是否為空,再使用 list_first_entry
找出第一個 entry
的位置,再使用 list_del_init
將此 entry
remove ,並將此 entry
的 prev 與 next 都指向自己,最後將 entry->value
用 strncpy
複製到 sp 裡。
大致上與 q_remove_head
思路一樣,一開始先檢查 list 使否存在與 list 是否為空,再使用 list_last_entry
找出最後一個 entry
的位置,再使用 list_del_init
將此 entry
remove ,並將此 entry
的 prev 與 next 都指向自己,最後將 entry->value
用 strncpy
複製到 sp 裡。
一開始先檢查 list 使否存在與 list 是否為空,再宣告一個節點用 list_for_each
去走訪 list ,並紀錄 list 大小。
我的想法是用 two-pointer 的方式實作,首先宣告兩個 pointer pre
與 nex
分別代表 list 的頭跟尾的位置,這兩個 pointer 會一直往中心移動,會有兩種 case
pre
與 nex
在同個位置的節點即為中心點。pre
與 nex
交錯時, pre
即為中心點。用 list_del
將該節點從 list 中分離出來,再用 list_entry
取得 entry
位置,最後釋放該 entry
。
先用 list_for_each_entry_safe
去走訪每個元素 ,分別用 target
與 temp
去紀錄第一個元素與下一個元素,再檢查它們是否相同,若相同,則釋放掉 target
,用一個二元變數 dup
去紀錄是否有重複,若 dup == true
,則 target
也為重複的元素,再將其釋放。
在實作時出現 Segmentation fault occurred. You dereferenced a NULL or invalid pointer
,發現是因為在比較時, temp
存取去到 head
,所以加入了 target->list.next != head
去使 temp
不會去存取到 head
。
想到的方法為逐一將 list 走訪,每走訪一個 entry
就將該 entry
從 list 中分離出來,再加入到 list 的第一個位置。
作法跟 q_reverse
類似,但不像 q_reverse
總是將節點插入第一個位置,這裡使用一個 pointer insert
指向一組 k 個節點的第一個插入位置,再使用 count
去紀錄走訪的節點數,當走訪的節點數恰 k 個時,將 pointer insert
指向下一組 k 個節點的第一個插入位置,也就是上一組的最後一個節點(目前節點的 prev)。
q_swap
其實就是 q_reverseK(2)
,於是用q_reverseK
去實作。
從 list 最尾端開始往前做,設 target
為最後一個元素、 prev
為 target
的前一個元素、 size
紀錄 list 中剩餘元素個數。
target
還大的元素,再將 target
指向此元素。head
為止。在跑測試時,在執行 q_free
後尚有未被刪除的元素,發現因為將元素移出 list 後,並未將其釋放而造成錯誤。
修改後
使用
diff
或git diff
產生程式碼差異的列表
:notes: jserv
我選擇採用 merge sort,因為 merge sort 為 stable sorting algorithm ,而其最壞的時間複雜度只有 ,這裡參考了 Linked List Sort 的實作方法,將 merge sort 分成三個部份,分別是:
mergelist
mergesort
fast
與 slow
,採用 Floyd Cycle Detection Algorithm ,當較快的指標到達終點時,較慢的指標會恰好在中心位置,並以遞迴的方式將 list 拆解,再呼叫 mergelist
將拆解後的 list 排序並重新組合成一條 list。q_sort
注意連字號的位置,書寫為 "doubly-linked list"
:notes: jserv
👌 (以修改)
mergelist
mergesort
q_sort
一開始有兩種想法,第一種是使用 mergelist
迭代的將兩條 list 合併成一條,但因為 mergelist
實作的關係,輸入需要是沒有 head
的兩條 list ,所以在迭代前都需要先對 list head
做處理,而在合併後還須將 list 變回 doubly-linked list,以上步驟會讓程式碼變得較為冗長。於是採用第二種方法,第二種為先將所有 list 串接在一起,再對這條 list 做 q_sort
,這樣一來就無須對 head
做變更,整體程式碼可以較為簡短。
cur
表示第一條 queue, temp
為指向下一條佇列的指標,迭代的將後面的佇列連接到第一條佇列後面,最後再對這條佇列做 q_sort
,最後回傳佇列長度。
list_sort
檔案及修改首先引入 list_sort.h
,刪除不必要的 header
。
list_sort.c
使到兩個巨集 likely
與 unlikely
,定義於<linux/compiler.h>
,將其定義加入 list_sort.h
中,在 merge_final
函式中宣告了 u8 count = 0;
,將其改成 uint_8 count = 0;
。
最後是將 list_sort.o
寫入 makefile
裡。
在 qtest
中先複製一份 do_sort
給 list_sort
使用,在 list_sort.h
中有定義函式,於是需要自己實作,這個函式是用來比較字串大小,回傳值為 int
。
所以在 qtest
中加入 cmp
函式實作。
在 qtest
中的命令 mysort
與 list_sort
都能正常執行。
這裡用 qtest
中的 time
進行時間的比較,有三種測資,分別用命令 RAND
加入100000、300000、500000筆隨機資料給 queue 。
加入自己寫的 trace-mysort.cmd
與 trace-list_sort.cmd
到測試資料中, ./qtest -v 3 -f traces/trace-list_sort.cmd
會執行以下命令。
測試次數 | 100000筆 | 300000筆 | 500000筆 |
---|---|---|---|
1 | 0.042 | 0.196 | 0.407 |
2 | 0.041 | 0.194 | 0.419 |
3 | 0.042 | 0.200 | 0.430 |
average | 0.0417 | 0.1967 | 0.4187 |
測試次數 | 100000筆 | 300000筆 | 500000筆 |
---|---|---|---|
1 | 0.041 | 0.170 | 0.368 |
2 | 0.043 | 0.170 | 0.388 |
3 | 0.039 | 0.171 | 0.364 |
average | 0.041 | 0.1703 | 0.3733 |
100000筆 | 300000筆 | 500000筆 | |
---|---|---|---|
效能差距 | 2% | 14% | 11% |
因為測試資料都是隨機生成的,加上測試次數不多,所以以 Perf 來分析效能。
測試方式不足以反映出上述實作的特性。
:notes: jserv
👌 (以修改)
用此指令確認是否安裝 perf。
確認 kernel 版本。
安裝 perf。
確認 perf 權限。
將權限全開
最後如果要檢測 cache miss event,需要先取消 kernel pointer 的禁用。
使用./qtest -v 3 -f traces/trace-list_sort.cmd
會執行以下命令,這裡以500000筆隨機資料做測試。
執行 perf stat --repeat 5 -e cache-misses,cache-references,instructions,cycles ./qtest -f traces/trace-mysort.cmd
,會執行5次上述命令,再去觀察其效能。
event data | my_sort | list_sort |
---|---|---|
cache-misses | 16,049,539 | 14,022,127 |
cache-references | 32,954,397 | 25,688,333 |
instructions | 2,203,807,317 | 2,251,606,244 |
cycles | 2,958,082,501 | 2,867,416,95 |
測試次數 | my_sort 花費時間 | list_sort 花費時間 |
---|---|---|
1 | 0.357 | 0.398 |
2 | 0.361 | 0.412 |
3 | 0.362 | 0.407 |
4 | 0.364 | 0.411 |
5 | 0.365 | 0.402 |
average | 0.3618 | 0.406 |
可以看出 list_sort
的 cache-misses 比 my_sort
少很多, list_sort
所需的 instructions 與 cycles 都比 my_sort
少, my_sort
只能達到 list_sort
的 89% 效能 (0.3618/0.406 = 0.89) 。
q_size
取得佇列的大小 len。len | random | queue | result |
---|---|---|---|
0–5 | 5 | A B C D E |
F |
0–4 | 3 | A B C |
F D |
0–3 | 1 | A |
F D B |
0–2 | 1 | A |
F D B C |
0–1 | 0 | F D B C A | |
0–0 | 0 | F D B C A E |
len
為佇列的大小,random
為隨機數,也同時代表被抽到的節點位置,將 node
移動到第 random 個節點位置,再將該節點移動到佇列最後的位置,當每個節點都做過一輪就結束。
將 shuffle
加入到 qtest
裡面,這裡的 do_shuffle
是參考 do_reverse
的實作,因為這兩個函式都是用來改變佇列的位置。
這篇論文主要闡述提供了一個新的工具 dudect ,可以不限定任何平台去檢測部份的程式碼是否達到 constant time ,提供 leakage detection 的方法。
這個方法會先去測量兩種不同的輸入的執行時間,並用統計學去判定這兩種執行時間的差異性,其中一種輸入為固定的數值,另一種為隨機數值。在進行統計分析前會先裁掉極值,這些極值可能是測量的誤差或是程式執行被中斷導致。
這裡採用 Welch's t-test ,為 Student's t-test 的改編版, Welch's t-test 處理兩個樣本間不同的標準差與樣本大小會比較可靠,這個方法會去計算兩個樣本的均值是否相等,並計算出 t 值。其中 為樣本均值, 為標準差。
這裡提到的預處理指的是在進行統計分析前裁剪掉極值的動作,而裁剪的方法為裁剪掉大於 百分比的測量值。這部份也就是 simulation 的缺陷,因為沒有將極值裁剪掉,導致影響到測量的速度。
首先在 trace-17-complexity.cmd
會先執行 option simulation 1
,先開啟 simulation mode ,再呼叫 it
, ih
, rh
, rt
四個函式。以呼叫 ih
為例,在 qtest
中會執行 bool do_ih
函式。
可以看到決定執行時間是否為 constant time 且程式正確執行,由函式 is_insert_head_const
決定,此函式在 fixture.h
定義。
在 fixture.c
中 is_##op##_const
會回傳函式 test_const
的結果 result
, result
為函式 doit
的回傳值。
其中 result
由兩個函式的回傳值做 AND 而來, measure()
, report()
。
首先為函式measure
,主要對四種模式 it
, ih
, rh
, rt
進行執行正確性的判定,判定依據為執行完該函式,其改變後的佇列大小是否正確。
再來是函式 report
,主要是用來判定執行時間是否為 constant time 。
首先將參數 百分比 percentiles
加入到宣告中,但因為作者有多宣告了一種結構,而 Simulation 實作是將宣告直接寫在函式中,於是這裡將 percentiles
在 t_context_t
結構中宣告。
再將相關程式引入到專案中,詳細修改在 commit 中。
加入了 percentiles
的實作後,測試都能在 constant time 內完成。