為什麼cache預料之外的hit會導致data外流....
其實表面來說 資料沒有被讀出來 但是是被窮舉的方式猜出來的
基本原理
0. int64 a = rdtsc()
RDTSC = Read the Time Stamp Counter,
這個數字從開機的時候就從0開始增加,一個cycle + 1.
這個指令不用進入高權限模式就可以執行
Pentium 75開始就有,在1995之後大量被使用
來測試效能 或者是作速度控制.
導致為了相容性不容易把它拔掉或者禁止低權限模式使用
有些範例會用進階的rdtscp(),這個是修正版本
需要SSE2,但是跟多核心cpu相容...RDTSC在多核心cpu的值
不一樣,本用途則差異不大
int64 a = rdtsc()
b = load_mem(ADR_A)
a = rdtsc() - a
這時候a會相近於這次load_mem所花掉的cycle數,
有一些誤差 但是通常在10 cycle以下
如果我做兩次 一次得到的a是> 200 , 一次是 < 20,
對cpu有點了解的就知道,cpu有一種叫做cache的機制
讓讀取有些時候可以加快不用那麼慢
所以很直覺的, >200 應該表示cache miss , 原本不在cache中,
< 20 , 上次應該就在cache中
這個後面會應用到
<======想按左鍵嗎??
1. 假設已知CPU的最後一層Cache 有10MB, 而且為12-way,
如果我有一個陣列U[10MB].考慮最簡單的情況
我連續讀取這10MB之後那一瞬間,是不是會把cache中原本的資料幾乎
全部洗出來,cache中幾乎全部是我這10MB的資料.
是的 這是基本假設
然後我們進階一點,cache被U[10MB]塞滿之後 我再load_mem(A),
這時候因為cache沒有他的資料,一定是cache miss,然後放棄掉U[10MB]中的
某區塊不在cache中,下次就是這個區塊的記憶體萬一又要讀取到 就會miss
(中間省略)最後針對一個Address A,我都可以在U中找到32Byte*12
總共384Byte的位址 只要這群資料用12個load_mem()讀入,就會
保證Address A的資料被擠出Cache
Q1:所以要先知道cpu cache的大小跟規格???
A:不用 用前面的方法本身就可以探索出cpu cache的最大值
跟way-associative的數值,其實就是拿各種size的陣列U
讀取跟分割讀取,可以求到的數值
2.
a = rdtsc()
b = load_mem(SYSTEM_A)
a = rdtsc() - a
會發生甚麼事情?如果SYSTEM_A是一個猜的Address,位在保護區段且不可讀取
其實正常就是產生General Protection Fault,但可以Program自己接手回來
這個Exception
正常來說, B不會被更新, 但關鍵在第二次的rdtsc()甚麼時候執行
Out of order 有可能
a. load_mem之前
b. load_mem之後,exception之前
c. exception之後
第一種情況會得到一個特小個位數的值 也可以用mem_barrier()
或者mem_fence() (這兩種指令是規定指令與mem_load要排隊)
隔離開 第一種情況基本上就不會發生
第二種情況 驚異的是它很接近一般的mem_load,有時候可以看到
> 200t, 有時候看到 < 20t,明明SYSTEM_A就不給讀取...
第三種就是rdtsc會超長,1000cycle內不太可能,或者.多核心之下不一定正常
可以當雜訊值排除
不是用這個方法 但是繼續進化的話...
3.設定一個陣列X,可以是256 Byte,或者適當的倍數
然後我同樣有個U[10MB]的陣列
a = rdtsc()
b = load_mem(SYSTEM_A)
c = load_mem(&X + b)
mem_fense()
a = rdtsc() - a
第一次做無效的SYSTEM_A的load, B不會得到結果
但是,我這端不知道B的值 可是CPU知道X陣列的第B個元素
加起來是多少,他去載入這個位置了.....會在C拿到嗎
不會 第一次load_mem無效,第二次load_mem一樣無效
至於exception的問題同前,但是多跑幾次在這組行為中看到cache miss
與cache hit的時間差異
然後我找個樣本
a = rdtsc()
b = load_mem(DUMMY)
c = load_mem(&X + 0)
mem_fense()
a = rdtsc() - a
找出U[10MB]之中,對第二次&X + 0
具有cache互斥性的384 Byte資料為一組
抽出來 跟
a = rdtsc()
b = load_mem(SYSTEM_A)
c = load_mem(&X + B)
mem_fense()
a = rdtsc() - a
一起玩
如果發現&X + B的載入行為,Cache Miss的時間
和&X + 0的對照組相同
那麼, B的內容就是0
如果比照起來不相似&X + 0與它的384 byte伙伴的相處關係
那就要再找&X + 1,這時候是另外384 byte快樂伙伴
來比較.....最多比較256次來確定一個Byte
實際上這整個流程都在窮舉 應該全速運作也要十萬個cycle以上
才能確定1 Byte的資料
3a.Speculative Execution
我不太確定正確的方法要不要應用speculative execution的指令
在這件事情需要用被動的指令speculativity還是主動指定為
speculative execution 但假設是的話 可以應用的範圍為
無效的mem_load,原本會產生exception,
但是我可以用speculative execution,放在不會執行的if-else中
但CPU不具有足夠條件做出正確的branch prediction的話,
在不執行那端的mem_load也會排入pipeline,並且在最後取消
volatile V = *Y
a = rdtsc()
if (V > 0)
else
{
b = load_mem(DUMMY)
c = load_mem(&X + 0)
}
a = rdtsc() - a
==>speculative execution化
volatile V = *Y
a = rdtsc()
SPEC_TRUE(V) { }
SPEC_FALSE(V)
{
b = load_mem(DUMMY)
c = load_mem(&X + 0)
}
a = rdtsc() - a
這時候CPU ooo會同時開始執行SPEC_TRUE與SPEC_FALSE的指令
最後SPEC_FALSE因為不成立,所以load_mem執行到中間就被取消
但這中間已經去Memory動作了 因此Cache也產生變化,但是取消
後不發exception,可能速度會加快很多 然後Host OS無法
偵測到你一直在產生GPF,降低被發現的機率
F.最後結論
以上的用法有需多前提條件 因此了解這個條件後有對應的話
可能可以避開.....對這沒甚麼自信 降低發生問題的洞
1.電腦Cache讀取的時間與外部記憶體差異巨大
現況一定是這樣 未來也一定是 無解
2.rdtsc精確度太高 來個1000 cycle誤差就行
或者限制僅kernel mode可以用(規格上已經支援 但為了相容性不開)
總之rdtsc要背太多舊程式相容性的鍋..
3.直覺上,跑一個記憶體載入指令,應該要在合法的位置才啟動啊
但實際上:
|TLB/PF |VALID|
|FETCH|DECODE|MEM