有一個有趣的問題: 假如 cache size 是 8KB, 而 virtual memory 的 page 是 4KB 會怎麼樣? 這個就是 cache alias的問題.
根據新版的 “See MIPS Run" 這本書的 10.3.4 Cache Aliases and Page Coloring, 名詞定義是這樣:
1. index range = the size of one “set" of cache. 舉例來說 4 KB 的 page 可以對應到 8KB 的 direct map, 或是 32KB 的 4-way set-associative cache.
2. page color = the value of those one or more virtual address bits that choose a page size chunk within the propriate page set.
3. cache aliases = two virtual pointers to the same physical data can produce an alias only if they have different page colors.
若是把 32KB 4-way associative cache memory 看作 4 塊 8KB 的 cache memory, 那麼每一塊都比 4KB page 大一倍, 一抓就有機會抓到和另外一個 way 重疊的內容.
解法: 只要 virtual address 彼此距離夠遠, 比方說在 4KB page 下間隔 64KB, 那麼每個 page 的 color 都會一樣.
另外有人說, 可以讓 virtual address 的 bit 12 (假設 page 是 4KB, 12 bis) 強制和 physical address 的 bit 12 一樣, 也就是說每 8KB 的第一個 4KB, 和第二個 4KB 在 physical address 上都沒有重疊. 由於每一個 way 不會抓到一樣的東西, 這就確保了兩個 way 之間的 cache 不會重複. 它聽起來等效於 page size 變成 8KB, 所以應該會沒問題.
先不管軟體實作上的困難, 這種 work around 的 hit rate 將會很低. 每次 hit 到奇數 page, 就要連前一個偶數 page 都抓進來. 那些資料通常已經是過去式了, 所以 cache 的效率應該挺差的.
——————————————————–
20090320 重新整理
cache alias 可能發生在 Linux 的 user mode 之間, 也可能發生在 user mode 與 kernel mode 之間.
單純在 user mode 的解法有很多種:
1. 只要 virtual address 彼此距離夠遠, 比方說在 4KB page 下間隔 64KB, 那麼每個 page 的 color 都會一樣均勻, 如小魚的第一個回覆一樣.
2. 根據小魚的說法: 奇數 8KB (i.e. 4(2n+1)KB) 和偶數 8KB (i.e. 4(2n)KB) 的 physical address 都對應到不同組的 virtual address. 而 memory cache 既然是根據 virtual address 所做的, 那麼就沒有機會 cache 到重複的 physical address.
有人說用這種說法: “可以讓 virtual address 的 bit 12 (假設 page 是 4KB, 12 bis) 強制和 physical address 的 bit 12 一樣, 也就是說每 8KB 的第一個 4KB, 和第二個 4KB 在 physical address 上都沒有重疊. 由於每一個 way 不會抓到一樣的東西, 這就確保了兩個 way 之間的 cache 不會重複. 它聽起來等效於 page size 變成 8KB, 所以應該會沒問題.
為了 hit 到 8KB 裡的一個 Linux 4KB page, 現在必須抓 8 KB 的 cache. 和原來的方式相比, 原來讀到 0x80001-000 的時候, 我們 cache 0x80001-000~0x80002-FFF, 是指望後面進到 cache 的 0x80002-000~0x80002-FFF 這個 page 等一下會用到. 根據新的方式, 就會變成 cache 0x80000-000~0x80001-FFF 這 8 KB. 所以還是會有一些差別, 如小魚第四篇回覆所說的: " 0×00410_000 和 0×00411_000 是無法同時對到 0×40400_000 的“.
本來我有個直覺, 覺得分了類之後, 對於大量連續資料, 又放在虛擬記憶體的連續位置時, 上面的做法可能會降低效率. 但想想也只是 cache 到不同 way 的 cache memory 去了, 應該是還好.
[後記]
1. Kernel space 和 user space 存取同一個 page 的話, 也會有 virtual alias 的問題.
2. 還是要感謝小魚啦! 哈!
Cash Chou's Blog 
這個 page-coloring 應該有兩種用法
針對不同的場合
一是避免 cache conflict，假設我們有很大的 cache 比方說 64K direct map，
採用 4K 當 page size，所以 cache 裡面可以塞 16 個 page。如此可以將所有的 memory 分成 16 種顏色，分別對應到 cache 不同的位置。如果說 OS 不好好分配 page 的位置的話，會使得 cache 使用率變差，有的地方很容易 cache miss，有的地方卻總是空的。所以比較好的做法是讓 OS 分配的顏色均勻一點。
另一個就是避 virtual aliasing 了。
以 8K-direct map 為例，4k 的 page 會造成 VIPT (virtual index, physical tag) 下產生 aliasing，不同的 VAddr 對到相同的 PAddr；在同時查找 cache 和 TLB 的情況下，簡單的硬體無法解掉這個問題。
軟體上的解法一樣叫 page coloring，就是把所有的實體記憶體頁面以地址分成兩類，一類叫 4nKB，一類叫 (4n+1)KB；同樣的所有的虛擬記憶體頁面也是這樣。並規定虛實的對應 4n 那一類只能對到 4n 的頁面，(4n+1) 也是一樣。如此才能避掉 aliasing 的問題。
還有 Cash 你最後的一段看不太懂啊 XD
是跟 MIPS 的 dual-mapped 的 TLB 有關嗎？
感謝 “小魚" 熱情回覆, 讓我獲益良多. 明天我可以去公司進一步的研究.
最後一段, 並不是指 dual-mapped, 我的原意是說: 強制 virtual address 的 bit 12 等於 physical address 的 bit 12,這個 idea 是聽來的, 我想不通要如何做到? 並且對它的效果質疑. 文字我再想想怎麼修改好了.
但它有沒有可能是 page coloring 解法的另一種說法呢? 現在有點昏了, 明天再推敲一下. 感謝!
“但它有沒有可能是 page coloring 解法的另一種說法呢?"
沒錯 就是這樣低
比方說我們使用一虛擬地址 0x00400_000, TLB page size 是 4KB 的話，
TLB 的轉譯就是把前面 20 bits 換成實體位置，
0S 在資源許可的範圍內可以任意指定
可以對應到 0x00000_xxx (最前面)
也可以對到 0x00001_xxx (下面 4KB) [別的位置也可以]
但是如果考慮解 cache aliasing 的問題
就只能選 第一個 0x00000_xxx，或是 0x00002_xxx…
不能挑 0x00001_xxx
繼續補充
所以 “強制讓第 12 bit 相同" 就是這麼一回事
之前也有寫錯的地方，正確的分類應該是 8nKB 和 (8n+4)KB
附帶一提的是，
這樣的解法在 memory share 時有時會有麻煩
因為要顧及 cache aliasing
所以不同的虛擬頁面對到同一個實體頁面時
這些不同的頁面必須是同一個分類
像是 0x00410_000 和 0x00411_000 是無法同時對到 0x40400_000 的
本來 OS 不需要考慮這種 memory share 的問題的。
這樣又清楚多了. 雖然依稀記得以前讀過類似的東西, 但是還是你講得比較明白, 哈! Thanks!
嗯…
其實 cache aliasing 有時是沒問題的
狀況發生的時候就會很大條
沿用上面的例子
假設我們的系統有 8KB 的 direct-map dcache，使用 4KB 的 page
(幾個 way 沒有關係)
當我們讓 0×00410_000 和 0×00411_000 同時對到 0×40400_000
TLB 會把 0x00410 和 0x00411 都對應到 0x40400，這一直都不是問題
問題是使用 virtual index 的 cache
現在系統是 8KB (= 2^13)
所以我們會拿 13 bit 出來找 cache 有沒有 hit
所以有兩組 address: 0x0_000 和 0x1_000，
(不同的地方在於先頭的 bit，沒經過 V to P 的轉換就拿來用了
這也是 PIPT 決不會發生 aliasing 的原因)
分別對應到 dcache 裡 0 和 4K 的位置
如果我們兩邊都是 read only，那就沒問題
(icache 很少聽過要解 aliasing 就是這樣)
但如果有人想寫入，大條的情況就發生了：
使用 0x00410_000 的人，改到的是 cache 0 位置的 data
使用 0x00411_000 的人，改到的是 cache 4K 位置的 data
這就造成了 data 不同步
所以 8K-1way 的系統裡 任何一個實體的 address，
cache 中都有兩個可能產生 aliasing 的位置
如果我們有一個 16K 2way-associate 的系統，page 也是 4K 的話
狀況跟上面其實一樣，有兩個產生 aliasing 的位置
教科書上面的一個硬體解範例是
只要發生 cache miss
就 write-back-invalid 所有可能的 cacheline
16K-2way 的話，可能的 cacheline 就是四條
確保再次抓進來的 line 一定是被更新過的
拜小魚之賜, 現在本 blog 的技術含金量可是上升了不少, 哈!