HackMD
Page Coloring
Introduction
一言以蔽之，Page coloring 就是把 page「上色」，使 cache 和 page 之間產生某種 mapping。如圖，同一個顏色的 page，表示他們對應到同一個 cache line。
透過 Page coloring 這種軟體技巧，雖然 cache 對於程式設計者來說是一個透明的資源，但通過 cache 的特性，給每個 page 與 cache 的關係附加上 "color" 的屬性。在給 process allocate page的時候，就可以考慮到對 cache 的使用，allocate 合適的 page。
最早 page coloring 被用在 MIPS operating system 上，確保在 virtual 和 physical可以對 cache 的使用達到相同的效益。目的是希望可以從 CPU cache 的角度 allocate 連續的free memory，藉此最大化可以被 processor cached 住的page數量，平均對 cache 的使用，減少 cache miss 的發生。另外，page coloring 也可以被用來解決 cache 的 aliasing 問題。
比較近期的使用的話，則是透過這個機制來管理在 multi core 上的 cache space
沒有 page coloring 機制的話，cache 的 performance 將難以預測，同樣的 program 也可能因為 page allocation 的差異導致 performance 的差異。
Solving problem
透過 page coloring 的技巧，我們可以解決許多 OS 與 cache 的互動衍生的問題。
Reduce cache misses
physical indexed 的 cache 中，相鄰的 physical page 會對應到不同的 cache line。如下圖：
在 virtual memory 下，狀況明顯並非如此。連續的 virtural memory block 不一定對應到連續的 physical memory block。Worst case 的狀況下，所有的 virtual block 都對應到同一個 cache line，cache 將無法發揮其存在的價值。
因此，透過 page coloring 的技巧，以此圖來說，如果 virtual address 的 page0 map 到 block 0 的話，那 page coloring 就會避免 virtual address 的 page 1 map 到block 64、128…等，因為這會使得兩個 virtual page map 到同一個 cache 上。
Aliasing
In a VIPT cache lookup:
計架中有說過的 Virtual index Physical tag 的架構，目的是為了折衷 virtual address cache 不需轉換因此速度比較快的好處，以及 physical address cache 不必每次 context switch 就 flush 的優勢。
雖然 Virtual index Physical tag 也要 MMU 的 translation，但在為了得到 tag 把virtual 轉成 physical 的過程中，可以先用 virtual 的 index 去找對應的 cache block，等轉換完再用 tag 去看是否 hit。
然而 VIPT 中存在 aliasing 問題。假設有一個 physical address 0x9abcd678，map 到 0x12345678 和 0xfedcb678。因為 virtual index 不同，他們倆會被 map 到不同的 cache line。結果，兩個不同的 cache line 會map到一樣 physical address。假設 cache line A 改寫後被置換回memory，然後 cache line B 再被置換回 memory，那麼改寫的內容就會被覆蓋掉。
通過 Page coloring，限制 virtual page 只能 map 到同一個顏色的 physical page，可以解決此問題。如下圖，我們就不能像例子中選擇 0x12345678 和 0xfedcb678 來 map 同一塊virtual address，因為他們的顏色並不相同。
舉一個比較簡單的方法: 就是保證 virtaul address[12:13] bits 要跟 allocated 到的physical address的[12:13] bits 相同，保證這些 virtual address 可以 map 到同一個 cache。
Partition
在多核的 processor 中，L2 以上的 cache 有機會是共用的。如果兩個 core 都高度使用 cache，可能會因為互相排擠 cache 上位置，導致 process 的 performance 變差或者無法預期。
通過讓不同的 processor 只能 map 到限定顏色的 page，可以讓 multi core 上的 shared cache 達到切割的效果
Linus say…
Page coloring 看起來很棒，但使用 page coloring 會使得 page 的 allocation 更加複雜。
實際上，Linux 系統中就沒有實作 page coloring 的機制。Linus 認為，真實世界中，我們不一定會遭遇上述的 worst case。而且隨著cache的設計都是4-way/8-way associatiove，前面提到會導致cache miss的情境也就變得沒那麼嚴重。
而且page coloring使得kernel的設計更加複雜，舉例來說，在multi core的情況下，假如某一個core上發生了context switch，新的process和舊的process會有不同memory分配要求，但此時其他core上的process已經佔用了新的process原本選用的color，那你可能會需要額外的記憶體搬動來滿足，產生額外的overhead。
同時page coloring限制了page的選擇，因此當某一種顏色的page用完的的時候，即使還有其他可用的page，程式卻可能因為page coloring的限制無法使用。當然，程式可以選擇捨棄一些page(寫回硬碟)，或者乾脆也把其他顏色拿來用，但前者會造成page swapping造成速度變慢，後者則產生原本想要避免的cache conflicts的問題，同樣也會造成速度變慢。
這使得performance的問題不僅僅存在於cache上，同時也需要考慮page allocate 跟page free的問題。
linux implement
這是一個在 Github 上，基於 Linux 所嘗試的 page coloring 實作: linux-page-coloring
