How to deal with VIPT alias? – Page colour

为获得更好的阅读体验，请移步：http://tek-life.github.io/blog/how-to-deal-with-vipt-alias-page-color/

Agenda

1. Introduction
2. Cache aliases issue for VIPT
3. How to solve alias
4. Implement in Linux

Introduction

VIPT是Cache的一种Policy。如果Cache_Size/numbers_of_way > Page_Size/Cache_Line_Size就会产生alias问题。

Cache aliases issue for VIPT

何谓alias

If the same PA is mapped into the different VAs, they could have different virtual indexes and certainly has the same physical tags, so multiple cacheline might have data for the single PA.

Reference From: http://mail-index.netbsd.org/port-sh3/2006/09/07/0000.html

alias会造成什么问题

由于相同的物理页在Cache中有多份拷贝，那么某一份拷贝更改而没有及时刷(clean)到Memory中，其他的Cache拷贝就不能获知其更改，而造成错误。

How to solve alias issue

解决alias问题的方法有以下三种
1. 存在多VA映射的物理页的PTE(page table entry)中的属性全部设置为 uncacheable.
2. flush cache
3. 多VA映射相同的物理页，如果能让VA在索引Cache的时候，都索引到相同的Cache sets中，那就不会产生alias问题了（因为在Cache set中识别Cache是否命中是用Physical Address Tag）。

第一种uncacheable的方法让memory不进Cache缓存的方式不可取，因为会导致系统的性能急剧下降。
第二种flush Cache的方法会需要系统程序员非常小心才可。
第三种的方法被称之为page colour。本文重点介绍这种方法。

理解 page colour

举个例子来说明page colour。以PIPT/32KB/32Bytes/4-way VM中页面的大小是4KB为例。
第0页所对应的Cache sets Index为0～127，第1页所对应的Cache Sets Index为128～255。有人将一个页所占用的Cache Sets称之为一个Cache Bin.
该Cache的set Index一共为32KB/(32B * 4way)=2¹⁵ / 2⁷ = 2⁸ 每个页所用的Sets为2^{7。因此，一共有两个Cache} Bin. 第2个页和第0个页共用一个Cache Bin,第3个页和第0个页共用一个Cache Bin.依次类推：
二进制索引第00,10,100,110,…的虚拟页面共用一个Cache Bin；第01,11,101,111,…的虚拟页面共用一个Cache Bin.
由此，可以得到页面的索引最低为决定了页面放在哪个Cache Bin中。即，对于虚拟页面的Virtual Address来说，第13位既是决定了该页面放在哪个Cache Bin中。
在页面的virtual address中决定该页面放在哪个Cache Bin的bit(s)称之为page colour. 在本例中，page colour位只有1位(第13位)。

Implement in Linux

在Linux中，利用page colour解决alias issue问题有两个地方。
1. 分配零页面
2. COW(copy-on-write)时拷贝页面。 这两个地方运用page colour来解决alias的核心思想就是内核态在操作物理页时，所使用的虚拟地址要和该物理页在用户空间虚拟地址的page colour位相同。在ARMV6的spec.中有所描述：

• If multiple virtual addresses are mapped onto the same physical addresses, then for all mappings bits [13:12] of the virtual address must be equal, and must also be equal to bits [13:12] of the physical address. The same physical address can be mapped by TLB entries of different page sizes. These can be 4KB, 64KB, or sections.
• If all mappings to a physical address are of a page size equal to 4KB, the restriction that bits [13:12] of the virtual address must equal bits [13:12] of the physical address is not required. Bits [13:12] of all virtual address aliases must still be equal.

Reference From: DDI0406B.P1985.

分配零页面

kernel通过page fault给分配匿名页的时候，需要分配零页面。分配零页面运用page colour思想来解决VIPT alias问题的函数是：__alloc_zeroed_user_highpage-> clear_user_highpage->cpu_user.cpu_clear_user_highpage->v6_clear_user_highpage_aliasing

107 /*
108  * Clear the user page.  We need to deal with the aliasing issues,
109  * so remap the kernel page into the same cache colour as the user
110  * page.
111  */
112 static void v6_clear_user_highpage_aliasing(struct page *page, unsigned long vaddr)
113 {
114         unsigned int offset = CACHE_COLOUR(vaddr);
115         unsigned long to = to_address + (offset << PAGE_SHIFT);
116
117         /* FIXME: not highmem safe */
118         discard_old_kernel_data(page_address(page));
119
120         /*
121          * Now clear the page using the same cache colour as
122          * the pages ultimate destination.
123          */
124         raw_spin_lock(&v6_lock);
125
126         set_pte_ext(TOP_PTE(to_address) + offset, pfn_pte(page_to_pfn(page), PAGE_KERNEL), 0);
127         flush_tlb_kernel_page(to);
128         clear_page((void *)to);
129
130         raw_spin_unlock(&v6_lock);
131 }

114～115行，根据用户空间虚拟地址设置内核区间虚拟地址的Page color位，然后通过128行的clear_page()函数调用memset()操作内核区间虚拟地址达到给物理页面清0的目的。

COW时拷贝页面

在发生COW时，内核需要操纵物理页面对应的内核区间地址帮助用户进程进行页面的拷贝。 cow_user_page->copy_user_highpage->__cpu_copy_user_highpage->cpu_user.cpu_copy_user_highpage->v6_copy_user_highpage_aliasing

 72 /*
 73  * Copy the page, taking account of the cache colour.
 74  */
 75 static void v6_copy_user_highpage_aliasing(struct page *to,
 76         struct page *from, unsigned long vaddr, struct vm_area_struct *vma)
 77 {
 78         unsigned int offset = CACHE_COLOUR(vaddr);
 79         unsigned long kfrom, kto;
 80
 81         if (!test_and_set_bit(PG_dcache_clean, &from->flags))
 82                 __flush_dcache_page(page_mapping(from), from);
 83
 84         /* FIXME: not highmem safe */
 85         discard_old_kernel_data(page_address(to));
 86
 87         /*
 88          * Now copy the page using the same cache colour as the
 89          * pages ultimate destination.
 90          */
 91         raw_spin_lock(&v6_lock);
 92
 93         set_pte_ext(TOP_PTE(from_address) + offset, pfn_pte(page_to_pfn(from), PAGE_KERNEL), 0);
 94         set_pte_ext(TOP_PTE(to_address) + offset, pfn_pte(page_to_pfn(to), PAGE_KERNEL), 0);
 95
 96         kfrom = from_address + (offset << PAGE_SHIFT);
 97         kto   = to_address + (offset << PAGE_SHIFT);
 98
 99         flush_tlb_kernel_page(kfrom);
100         flush_tlb_kernel_page(kto);
101
102         copy_page((void *)kto, (void *)kfrom);
103
104         raw_spin_unlock(&v6_lock);
105 }

kfrom和kto分别是内核虚拟地址的源地址和目的地址。他们具有相同的page colour。copy_page通过调用memcpy使kfrom对应的物理页的内容拷贝到kto中。

Reference

1. ARMV7 Spec，DDI0406B,P1985.
2. http://mail-index.netbsd.org/port-sh3/2006/09/07/0000.html.
3. 浅谈高端CPU Cache Page-Coloring，陈怀临.
4. Page Colouring on ARMv6 (and a bit on ARMv7)，http://blogs.arm.com/software-enablement/716-page-colouring-on-armv6-and-a-bit-on-armv7/