contributed by < 25077667 >
25077667編輯中…
人在做,Google/GitHub 在看,不用特別強調你的閒置,快去動手!
jservImage Not Showing Possible ReasonsLearn More →
- The image file may be corrupted
- The server hosting the image is unavailable
- The image path is incorrect
- The image format is not supported
作業要求:【連結】
$ neofetch
很明顯,就是要 new
一個 queue,像這樣
可是呢~ 我原本其實是想用 calloc,像下面這樣,但是會:
ERROR: Attempted to free unallocated block. Address = 0x7ffff4e93890
接下來這邊要先看過追蹤記憶體配置和釋放的狀況才能知道我說 function hooking 在 harness.c
的部分
原本以為是 function hooking 沒改,所以會錯,但是進去看了之後似乎不是。因為報錯是 "Attempted to free unallocated block…",而這是在 harness.c
的 find_header()
的這幾行描述的:
很明顯,這是線性走訪所有 allocated heap 去找有沒有申請過這塊記憶體。
可是當我們回顧到 harness.c
的 test_calloc()
的 line 7
同樣是走 test_malloc
就是不知道為啥沒有把 test_calloc
的 address 放到 allocated
裡面去。不然怎麼會找不到呢?
25077667所以就先 malloc + memset 湊合著用,先解決其他問題在深入去追 code
因為太直觀,所以就不放 code 了。
就是一個一個 free,不然還有其他辦法嗎?
跟下面 q_insert_tail
很像。
總之就是要 完成插入。
目前程式碼如下
第 6 行,一開始是使用 calloc,因為 newTail->next
要設成 NULL
,NULL本質上也是 0,所以就打算 calloc = malloc + memset(0)。
但是問題同上 q_new
出現:
ERROR: Attempted to free unallocated or corrupted block. Address = 0x7fffbae30820
這東西。
再來這邊還可以優化的地方,大概是把他跟 q_insert_head 寫再一起(當 q == NULL
或加入一個新節點時: line 6-13 )。
原本我 line 8 是用 memcpy,可是跑 Valgrind 的時候,被告知越界讀取,我還不是很懂為什麼,我猜是 memcpy 會往後多看一格(這應該是舉燭吧)
工程人員用字遣詞應當精準!
25077667 fixed
原本寫法在這 commit,現在看一看覺得我 commit 名子寫錯,這才不是 buffer overflow,這是 Out-of-Bounds Reading。
為了要 ,就多放一個元素在 queue_t
叫做 size 存起來。
就是動一動指標最快,所以就直接寫了。
寫完後覺得好像還可以改善,我想了一下下,就發現 q->tail->next
可以當作 cache 用,所以變成下面這樣子。恩這也很顯而易見。
這 q_sort
不是 quick sort
而是對 queue sort
。
遇到的問題是 Stack Overflow,因為我原本 merge 的寫法是:
list1->next = merge(list1->next, list2);
而這肯定是要遍歷完全部節點在 stack 上。
每一次 recursive function call 都要 push RBP,所以,會有很大的需求在 stack size 上。
(這是我在 Facebook 群組的討論串,感謝大家花時間教我><)
改善方式:把 merge
function 換成 iterative 的方式
目前寫法還有改善空間(不優雅、不利他)。
剛剛看覺得糟糕,我 sort 啥東西都沒動,竟然有次會出現:
+++ TESTING trace trace-15-perf:
# Test performance of insert_tail, size, reverse, and sort
ERROR: Time limit exceeded. Either you are in an infinite loop, or your code is too inefficient
–- trace-15-perf 0/6
難道真落在那 5% 拒絕區?還是我的表現只是近似 const time,但不是 const?
這我還要在找找原因(也可能是我 merge 太沒效率啦)
Makefile
在 Makefile 的 OBJS 中加入 strnatcmp.o 讓他生成 strnatcmp 的 object file
replace strcmp()
to strnatcmp()
in queue.c and qtest.c:
原本以為這樣就 ok 了,但是在 git pre-commit 的 hook 擋下來:
於是我把 nat_char ca, cb;
移進 while(1)
中,把未使用的 strnatcmp
註解起來。
25077667 CPPCHECK 好嚴格QQ
然後就可以成功 commit 了。
在這邊,每次 make test
的第 15 個測試都會超時。
跟上面的 "偶爾" 超時,有很大差異。
但是因為修改的部分只有 compare function 因此考慮的是 code 本身的效率問題與 function call 的成本。
因此我們拿 perf 去看他
使用 natsort 超時的關鍵發現:
Overhead Shared Objec Symbol
28.64% qtest [.] strnatcasecmp
20.87% qtest [.] mergeSort
12.11% qtest [.] show_queue
6.43% libc-2.27.so [.] _int_malloc
3.21% qtest [.] test_malloc
3.05% qtest [.] q_reverse
2.80% qtest [.] test_strdup
2.78% qtest [.] merge
2.39% qtest [.] __ctype_toupper_loc@plt
2.24% libc-2.27.so [.] __ctype_toupper_loc
2.19% qtest [.] q_sort
1.47% libc-2.27.so [.] __random
1.32% libc-2.27.so [.] malloc
1.06% libc-2.27.so [.] __strcasecmp_l_avx
0.96% [kernel] [k] prepare_exit_to_usermode
我們應該先解決高 cpu 週期占比的。
所以是先考慮 標註起來 的這三個
但是 strnatcasecmp
跟 show_queue
不可控。因此我就再確認如果不用 strnatcasecmp
的 cpu 使用週期其況。
Overhead Shared Objec Symbol
27.15% qtest [.] mergeSort
17.55% qtest [.] show_queue
6.96% libc-2.27.so [.] _int_malloc
6.58% libc-2.27.so [.] __strcmp_sse2_unaligned
4.31% qtest [.] q_reverse
3.97% qtest [.] merge
果然消耗最大的是 mergeSort
。但是我不知道從何改善起,讓我想想這要怎麼優化。
TODO: 優化 mergeSort()
$ make valgrind
25077667這在 WSL 上有可能會錯誤。
基本上就可能 RAM 吃太飽 malloc 不到東西。其他沒啥問題:
$ htop
$ valgrind --tool=massif ./qtest -f traces/trace-18-natsort.cmd
這是跑 nat_sort 的 valgrind 結果
論文連結
論文說他這方法是時序攻擊的一種,然後是基於統計分析的,不會因為硬體環境差異而有所錯誤。
他也提到一個 ctgrind,挺有趣的,也是檢測一你是否為 const time。
至於他的統計分析,就是拿兩個不同的 data 丟進去,統計上透過 Student-T 的 model 去做用 Welch’s 去算 p-value.
至於 Welch’s 可以參考我去年統計學寫的筆記,這是關於母體常態,變異數皆未知的情況。
這篇方法主要分三個步驟
和 higher-order function 無關,後者是 programming language 的範疇。這裡著重 "preprocessing",注意看論文的訴求。另外,不懂就標註出來,不要說「看不太懂」這種含糊的話 —— 誠實面對自己!
這作法跟我之前的寫統計學作業的經驗不太一樣,過去我們統計學要求出 p-value,所以多個麻煩的積分。(那時候不能用 for loop 因為 IEEE-754 的誤差會影響到,然後每次的黎曼求法的 dx 又很小,所以浮點數的影響就會對後續的數據造成有點嚴重的 誤差)
https://jonisalonen.com/2013/deriving-welfords-method-for-computing-variance/
File: ttest.[ch]
計算檢定統計數,在 分配底下。
這邊挺直覺得,就是
這其實是提供 mean、m2 給 fixture.c
的 update_statistics
。
dalta
:
double delta = x - ctx->mean[class];
x
就是他的執行時間ctx->n[class]++
mean
m2
根據平均值公式:
然後根據變異數的平移對稱性(之前筆記),把m2
展開
就是這行了
File: fixture.[ch]
mode
: 傳入constant.c
的 measure
用於控制要 test_insert_tail
還是 test_insert_tail
。
有疑問的點:
calloc
,其中 input_data
就是測試資料,竟然沒有出現跟我上面相同的錯誤:Attempted to free unallocated block. Address = 0x7ffff4e93890
prepare_inputs
: 產生 input ,而這邊比較有趣的是 rand 出來的 class[i] 有二分之一的機率,會把下面兩個 byte 也寫成 0。控制下面 measure
函式的插入次數。
*(uint16_t *) (input_data + i * chunk_size) = 0x00;
randombytes
會使用到 /dev/urandom/
,去填 input_data
。但是似乎沒有 close(fd)。不確定是什麼原因不需要,或是沒有寫 close(fd)。measure
: 對頭尾插入 *(uint16_t *) (input_data + i * chunk_size)
次。分別儲存於 before_ticks
與 after_ticks
。
differentiate
: 將前述 before_ticks
與 after_ticks
的相差,儲存於 exec_times
。
update_statistics
: 根據 differentiate
算完,放在exec_times
的時間差,去做 T 檢定。
cpucycles
: 這是在 measure
中測量執行時間的關鍵,他定義在 cpucycles.h
中。
這邊覺得有趣的是 bitwise
運算,為何這會是 cpucycles
呢?
cpu_high, cpu_low 都是使用 RDTSC 這個 x86_Read Time-Stamp Counter
hi
: 就是 cpu_high ,lo
: 就是 cpu_low
我們可見在 ((int64_t) lo) | (((int64_t) hi) << 32);
就是把 cpu_high
放在高位元(32),把 cpu_low
放在低位元(32)。一起組成 64 位元。傳回 before_ticks
跟 after_ticks
。
然後這邊有關於 volatile 的參考資料
覺得看完重點提示,還是只有舉燭。
所以以下是我的舉燭。
select
:
int select(int nfds, fd_set *readfds, fd_set *writefds, fd_set *exceptfds, struct timeval *timeout);
nfds
: An integer one more than the maximum of any file descriptor in any of the sets.readfds
: Holding the file descriptors to be checked for being ready to read, and on output indicates which file descriptors are ready to read.writefds
: Holding the file descriptors to be checked for being ready to write, and on output indicates which file descriptors are ready to write.errorfds
: Holding the file descriptors to be checked for error conditions pending, and on output indicates which file descriptors have error conditions pending.timeout
: Specifies a maximum interval to wait for the selection to complete.readfds
, writefds
, errorfds
可以為 NULL
select()
and pselect()
allow a program to monitor multiple file descriptors, waiting until one or more of the file descriptors become "ready" for some class of I/O operation (e.g., input possible). A file descriptor is considered ready if it is possible to perform a corresponding I/O operation (e.g., read(2)
, or a sufficiently small write(2)
) without blocking.select()
作用:
select()
read()
是一種 Blocking I/Orecvfrom()
是一種 Non-blocking I/Oselect
多個 fd
時,可以同時觀察多個 I/O 是否 "is ready"。 然後我們可以從 select()
的 return 值,取得第幾個 fd
使用 read()
進行 I/O。寫不完 la