---

為什麼cache預料之外的hit會導致data外流....

其實表面來說 資料沒有被讀出來 但是是被窮舉的方式猜出來的

基本原理

0.   int64 a = rdtsc()

RDTSC = Read the Time Stamp Counter,
這個數字從開機的時候就從0開始增加,一個cycle + 1.
這個指令不用進入高權限模式就可以執行
Pentium 75開始就有,在1995之後大量被使用
來測試效能 或者是作速度控制.
導致為了相容性不容易把它拔掉或者禁止低權限模式使用

有些範例會用進階的rdtscp(),這個是修正版本
需要SSE2,但是跟多核心cpu相容...RDTSC在多核心cpu的值
不一樣,本用途則差異不大

     b = load_mem(ADR_A)

這時候a會相近於這次load_mem所花掉的cycle數,
有一些誤差 但是通常在10 cycle以下



所以很直覺的, >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的大小跟規格???



2.

     a = rdtsc()
     b = load_mem(SYSTEM_A)



正常來說, 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)
     mem_fense()

第一次做無效的SYSTEM_A的load, B不會得到結果

但是,我這端不知道B的值 可是CPU知道X陣列的第B個元素

至於exception的問題同前,但是多跑幾次在這組行為中看到cache miss

與cache hit的時間差異


然後我找個樣本

     a = rdtsc()
     b = load_mem(DUMMY)
     mem_fense()

找出U[10MB]之中,對第二次&X + 0
具有cache互斥性的384 Byte資料為一組

抽出來 跟
     a = rdtsc()
     b = load_mem(SYSTEM_A)
     mem_fense()
一起玩

如果發現&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,並且在最後取消

     a = rdtsc()
     if (V > 0)
     else
     {
     b = load_mem(DUMMY)
     }

==>speculative execution化

     a = rdtsc()
     SPEC_TRUE(V) { }
     SPEC_FALSE(V)
     {
     b = load_mem(DUMMY)
     }


偵測到你一直在產生GPF,降低被發現的機率


F.最後結論


  以上的用法有需多前提條件 因此了解這個條件後有對應的話
  可能可以避開.....對這沒甚麼自信 降低發生問題的洞

  1.電腦Cache讀取的時間與外部記憶體差異巨大
    現況一定是這樣 未來也一定是 無解

  2.rdtsc精確度太高 來個1000 cycle誤差就行
    或者限制僅kernel mode可以用(規格上已經支援 但為了相容性不開)
    總之rdtsc要背太多舊程式相容性的鍋..

  3.直覺上,跑一個記憶體載入指令,應該要在合法的位置才啟動啊

    但實際上:

    |FETCH|DECODE|MEM-----|ADR  |WRITE|


    MEM/Cache Stage都不啟動的話則降低這種事情被分析跟被窮舉的可能

  4.上面的例子等於一個指令中有Indirect Memory的存取.但沒有支援
    這種指令的RISC並沒有完全避掉問題 所以單一指令有沒有MEM[MEM[ADR]]
    這樣的存取能力是不是重點就不知道了

--
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 111.243.156.56
※ 文章代碼(AID): #1QJwNfvM (PC_Shopping)
※ 文章網址: https://www.ptt.cc/bbs/PC_Shopping/M.1515169257.A.E56.html