---
tags: System Software, 作業系統
---

# 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](https://github.com/Jeongseob/linux-page-coloring)

## Reference
* [Cache coloring](https://en.wikipedia.org/wiki/Cache_coloring)
* [Page Colouring on ARMv6 (and a bit on ARMv7)](https://community.arm.com/developer/ip-products/processors/b/processors-ip-blog/posts/page-colouring-on-armv6-and-a-bit-on-armv7)
* [Towards practical page coloring-based multicore cache management](
https://dl.acm.org/doi/10.1145/1519065.1519076)
* [Managing Shared L2 Caches on Multicore Systems in Softwar](
https://web.archive.org/web/20110806125837/http://www.eecg.toronto.edu/~tamda/papers/softpart.pdf)