Cache and TLB Flushing Under Linux

Cache and TLB Flushing Under Linux

저자는 David S. Miller <[email protected]>입니다.

이 문서는 Linux VM subsystem이 호출하는 cache/TLB flushing interface를 열거하고, 각 interface의 목적과 호출 뒤에 기대되는 side effect를 설명합니다.

아래의 side effect는 uniprocessor 구현과 그 단일 processor에서 일어나야 하는 동작을 기준으로 서술합니다. SMP에서는 해당 interface의 side effect가 시스템의 모든 processor에서 발생하도록 정의를 확장하면 됩니다.

그렇다고 SMP cache/TLB flush가 반드시 비효율적이어야 하는 것은 아니며, 많은 최적화가 가능합니다. 예를 들어 어떤 user address space가 특정 CPU에서 실행된 적이 없음을 `mm_cpumask()`로 증명할 수 있다면 그 CPU에서는 해당 address space를 flush할 필요가 없습니다.

TLB 추상화와 flush_tlb_all()

먼저 더 단순한 TLB flushing interface를 설명합니다. Linux에서 TLB는 CPU가 software page table에서 얻은 virtual-to-physical address translation을 cache하는 대상으로 추상화됩니다. 따라서 software page table이 바뀌면 TLB cache에 오래된 translation이 남을 수 있습니다.

이 때문에 kernel은 software page table을 변경한 뒤 다음 flush method 가운데 하나를 호출합니다.

1) ``void flush_tlb_all(void)``

`flush_tlb_all()`은 가장 강력한 flush입니다. 호출이 끝나면 그 전에 이루어진 모든 page table 변경이 CPU에 보여야 합니다. 보통 translation이 global 성격을 갖는 kernel page table을 변경할 때 호출합니다.

전체 user address space TLB flush

2) ``void flush_tlb_mm(struct mm_struct *mm)``

`flush_tlb_mm()`은 user address space 전체를 TLB에서 flush합니다. 실행 뒤에는 `mm` address space에 대해 이전에 수행된 모든 page table 변경이 CPU에 보여야 하며, TLB에 `mm`의 entry가 하나도 남아 있지 않아야 합니다.

이 interface는 `fork`와 `exec`에서 일어나는 것과 같은 전체 address space page table 작업을 처리할 때 사용합니다.

가상 주소 범위 TLB flush

3) ``void flush_tlb_range(struct vm_area_struct *vma,
   unsigned long start, unsigned long end)``

`flush_tlb_range()`는 특정 user virtual address translation 범위를 TLB에서 flush합니다. 실행 뒤에는 `vma->vm_mm` address space의 `start`부터 `end-1`까지에 대한 이전 page table 변경이 CPU에 보여야 하며, 해당 범위의 TLB entry가 남아 있지 않아야 합니다.

`vma`는 이 영역에 사용되는 backing store입니다. 주된 용도는 `munmap()` 유형의 작업입니다.

이 interface는 수정될 수 있는 각 entry마다 kernel이 아래의 `flush_tlb_page()`를 호출하는 대신, port가 page 크기의 translation 여러 개를 TLB에서 효율적으로 제거할 수 있도록 제공합니다.

단일 page TLB flush

4) ``void flush_tlb_page(struct vm_area_struct *vma, unsigned long addr)``

`flush_tlb_page()`는 TLB에서 `PAGE_SIZE` 크기의 translation을 제거합니다. `vma`는 process의 mmap 영역을 추적하는 backing structure이고 address space는 `vma->vm_mm`으로 얻습니다. `(vma->vm_flags & VM_EXEC)`를 검사하면 이 영역이 실행 가능하여 split-TLB 구성의 instruction TLB에 들어갈 수 있는지도 알 수 있습니다.

실행 뒤에는 `vma->vm_mm`의 user virtual address `addr`에 대해 이전의 모든 page table 변경이 CPU에 보여야 하며, 그 주소의 TLB entry가 없어야 합니다. 주로 fault 처리 중에 사용합니다.

page fault 뒤 translation 통지

5) ``void update_mmu_cache_range(struct vm_fault *vmf,
   struct vm_area_struct *vma, unsigned long address, pte_t *ptep,
   unsigned int nr)``

모든 page fault의 끝에서 `update_mmu_cache_range()`를 호출하여 architecture-specific code에 `vma->vm_mm` address space의 virtual address `address`부터 연속된 `nr`개 page에 대한 translation이 software page table에 생겼음을 알립니다.

이 routine은 여러 다른 위치에서도 호출되며, 이때는 `vmf`에 `NULL`을 전달합니다. Port는 이 정보를 원하는 방식으로 활용할 수 있습니다. 예를 들어 software-managed TLB 구성에서는 이 event를 이용해 TLB translation을 미리 load할 수 있으며, 현재 sparc64 port가 그렇게 합니다.

cache flush와 page table 변경 순서

다음은 cache flushing interface입니다. Linux가 기존 virtual-to-physical mapping을 새 값으로 바꿀 때의 순서는 보통 다음 세 형태 가운데 하나입니다.

1) flush_cache_mm(mm);
   change_all_page_tables_of(mm);
   flush_tlb_mm(mm);

2) flush_cache_range(vma, start, end);
   change_range_of_page_tables(mm, start, end);
   flush_tlb_range(vma, start, end);

3) flush_cache_page(vma, addr, pfn);
   set_pte(pte_pointer, new_pte_val);
   flush_tlb_page(vma, addr);

cache level flush는 항상 먼저 수행됩니다. 이는 virtual address를 cache에서 flush할 때 그 주소의 virtual-to-physical translation이 존재해야 하는 strict cache 시스템을 올바르게 처리하기 위해서입니다. HyperSparc CPU가 이 특성을 갖습니다.

아래 routine은 특정 CPU에 필요한 범위까지만 cache flush를 처리하면 됩니다. 대체로 virtual-to-physical translation을 변경하거나 제거할 때 flush해야 하는 virtually indexed cache를 가진 CPU에서 구현해야 합니다.

반대로 IA32 processor의 physically indexed, physically tagged cache는 완전히 동기화되어 있고 translation 정보에 의존하지 않으므로 이 interface를 구현할 필요가 없습니다.

전체 address space cache flush

1) ``void flush_cache_mm(struct mm_struct *mm)``

`flush_cache_mm()`은 user address space 전체를 cache에서 flush합니다. 실행 뒤에는 `mm`과 연관된 cache line이 하나도 남지 않아야 합니다. `exit`와 `exec` 같은 전체 address space page table 작업에 사용합니다.

2) ``void flush_cache_dup_mm(struct mm_struct *mm)``

`flush_cache_dup_mm()`도 user address space 전체를 flush하여 `mm` 관련 cache line을 모두 제거하지만, `fork` 중의 전체 address space page table 작업에 사용합니다. VIPT cache를 위한 최적화를 허용하기 위해 `flush_cache_mm()`과 분리되어 있습니다.

가상 주소 범위 cache flush

3) ``void flush_cache_range(struct vm_area_struct *vma,
   unsigned long start, unsigned long end)``

`flush_cache_range()`는 특정 user virtual address 범위를 cache에서 flush합니다. 실행 뒤에는 `vma->vm_mm`의 `start`부터 `end-1`까지에 해당하는 cache entry가 남지 않아야 합니다.

`vma`는 이 영역의 backing store이며 주된 용도는 `munmap()` 유형 작업입니다. Kernel이 수정 가능한 entry마다 아래의 `flush_cache_page()`를 호출하는 대신, port가 page 크기 영역 여러 개를 효율적으로 제거할 수 있도록 이 interface를 제공합니다.

page, kmap, vmap cache flush

4) ``void flush_cache_page(struct vm_area_struct *vma, unsigned long addr, unsigned long pfn)``

`flush_cache_page()`는 cache에서 `PAGE_SIZE` 크기의 범위를 제거합니다. `vma`는 process의 mmap 영역을 추적하고, address space는 `vma->vm_mm`으로 얻습니다. `(vma->vm_flags & VM_EXEC)`로 실행 가능한 영역인지 검사하면 Harvard형 cache layout의 instruction cache에 들어갈 수 있는지도 판단할 수 있습니다.

`pfn`은 `addr`이 translation되는 physical page frame을 나타냅니다. 이 값을 `PAGE_SHIFT`만큼 왼쪽으로 shift하면 physical address가 됩니다. 호출 뒤에는 `addr`에서 `pfn`으로 translation되는 `vma->vm_mm` cache entry가 없어야 하며, 주로 fault 처리 중에 사용합니다.

5) ``void flush_cache_kmaps(void)``

`flush_cache_kmaps()`는 platform이 highmem을 사용할 때만 구현하면 됩니다. 모든 kmap을 invalidate하기 직전에 호출되며, 실행 뒤에는 `PKMAP_ADDR(0)`부터 `PKMAP_ADDR(LAST_PKMAP)`까지의 kernel virtual address 범위에 cache entry가 없어야 합니다. 이 routine은 `asm/highmem.h`에 구현해야 합니다.

6) ``void flush_cache_vmap(unsigned long start, unsigned long end)``
   ``void flush_cache_vunmap(unsigned long start, unsigned long end)``

`flush_cache_vmap()`과 `flush_cache_vunmap()`은 특정 kernel virtual address 범위를 cache에서 flush합니다. 실행 뒤에는 kernel address space의 `start`부터 `end-1`까지에 cache entry가 없어야 합니다.

첫 번째 routine은 `vmap_range()`가 page table entry를 설치한 뒤 호출하고, 두 번째 routine은 `vunmap_range()`가 page table entry를 삭제하기 전에 호출합니다.

D-cache virtual aliasing

CPU cache 문제 가운데에는 별도의 interface 집합이 필요한 또 다른 부류가 있으며, 가장 큰 문제는 processor data cache의 virtual aliasing입니다.

D-cache가 virtually indexed이고 크기가 `PAGE_SIZE`보다 크며, 같은 physical address에 대한 cache line 여러 개가 동시에 존재하는 것을 막지 않는다면 이 문제가 발생합니다.

해당 port는 먼저 `asm/shmparam.h`의 `SHMLBA`를 올바르게 정의해야 합니다. 값은 본질적으로 virtually addressed D-cache의 크기여야 하며, 크기가 가변이면 가능한 최대 크기를 써야 합니다. 그러면 SYSV IPC layer는 user process가 이 값의 배수인 address에만 shared memory를 mmap하도록 제한합니다.

그 밖의 모든 경우에 대해서도 D-cache aliasing을 해결해야 합니다. 어떤 page가 user address space에 mapping되면 `PAGE_OFFSET`에서 시작하는 kernel linear mapping에도 항상 적어도 하나의 mapping이 있습니다. 따라서 첫 user가 physical page를 mapping하는 즉시 kernel의 virtual address mapping과 aliasing할 가능성이 생깁니다.

anonymous 및 COW page 복사와 초기화

``void copy_user_page(void *to, void *from, unsigned long addr, struct page *page)``
``void clear_user_page(void *to, unsigned long addr, struct page *page)``

`copy_user_page()`와 `clear_user_page()`는 user anonymous page 또는 COW page에 data를 저장하며, port가 userspace와 kernel 사이의 D-cache alias 문제를 효율적으로 피할 수 있게 합니다.

예를 들어 copy 중에 `from`과 `to`를 임시 kernel virtual address에 mapping할 수 있습니다. 두 page의 virtual address는 kernel load/store instruction이 user mapping과 같은 cache "color"의 virtual address에 접근하도록 선택합니다. sparc64가 이 기법을 사용합니다.

`addr` parameter는 user가 최종적으로 이 page를 mapping할 virtual address를 알리고, `page` parameter는 target의 `struct page` pointer를 제공합니다. D-cache aliasing이 문제가 아니라면 두 routine은 단순히 `memcpy` 또는 `memset`을 직접 호출해도 됩니다.

page cache의 flush_dcache_folio()

``void flush_dcache_folio(struct folio *folio)``

`flush_dcache_folio()`는 다음 상황에서 호출해야 합니다.

• kernel이 page cache에 있으면서 또는 high memory에 있는 page에 data를 쓴 경우
• kernel이 page cache page를 읽으려 하고, 이 page의 user space shared/writable mapping이 존재할 가능성이 있는 경우. `{get,pin}_user_pages{_fast}`는 user address space에서 찾은 모든 page에 이미 `flush_dcache_folio()`를 호출하므로 driver code가 이를 직접 고려해야 하는 일은 드뭅니다.

"kernel이 page cache page에 쓴다"는 말은 구체적으로 kernel이 해당 page의 kernel virtual mapping에서 store instruction을 실행해 data를 dirty하게 만든다는 뜻입니다. 이러한 kernel store가 page의 user space mapping에 보이도록 D-cache aliasing을 처리하기 위해 여기서 flush하는 것이 중요합니다.

반대 경우도 중요합니다. 이 file의 shared+writable mapping을 가진 user가 있다면 kernel이 이 page를 읽을 때 user의 최신 store를 보도록 보장해야 합니다. D-cache aliasing이 문제가 아니면 architecture에서 이 routine을 nop으로 정의할 수 있습니다.

`folio->flags`에는 architecture private 용도의 `PG_arch_1` bit가 마련되어 있습니다. Kernel은 pagecache page가 처음 pagecache에 들어갈 때 이 bit를 clear하도록 보장합니다.

이를 이용하면 현재 이 page를 mapping한 user process가 없을 때 실제 flush를 나중으로, 어쩌면 무기한 연기할 수 있습니다. 구현 예는 sparc64의 `flush_dcache_folio()`와 `update_mmu_cache_range()`를 참고하십시오.

`flush_dcache_folio()` 시점에 `folio_flush_mapping()`이 mapping을 반환하고 그 mapping에 대한 `mapping_mapped()`가 `%false`를 반환하면 architecture private page flag bit만 set합니다. 나중에 `update_mmu_cache_range()`에서 이 bit를 검사하여 set되어 있으면 flush한 뒤 bit를 clear합니다.

user page와 instruction cache interface

``void copy_to_user_page(struct vm_area_struct *vma, struct page *page,
unsigned long user_vaddr, void *dst, void *src, int len)``
``void copy_from_user_page(struct vm_area_struct *vma, struct page *page,
unsigned long user_vaddr, void *dst, void *src, int len)``

Kernel이 `ptrace()` 등의 목적으로 임의의 user page에 임의 data를 복사하거나 그 page에서 복사할 때 `copy_to_user_page()`와 `copy_from_user_page()`를 사용합니다. 필요한 cache flush 또는 coherency 작업은 여기에서 수행해야 합니다. Processor instruction cache가 CPU store를 snoop하지 않는다면 `copy_to_user_page()`에서 instruction cache를 flush해야 할 가능성이 큽니다.

``void flush_anon_page(struct vm_area_struct *vma, struct page *page,
unsigned long vmaddr)``

Kernel이 anonymous page 내용에 접근해야 할 때, 현재는 `get_user_pages()`에서 `flush_anon_page()`를 호출합니다. `flush_dcache_folio()`는 의도적으로 anonymous page에 동작하지 않습니다. 기본 구현은 nop이며 모든 coherent architecture에서도 그대로여야 합니다. Incoherent architecture에서는 `vmaddr`에 있는 page의 cache를 flush해야 합니다.

``void flush_icache_range(unsigned long start, unsigned long end)``

Kernel이 module을 load할 때처럼 나중에 실행할 address에 store하면 `flush_icache_range()`를 호출합니다. I-cache가 store를 snoop하지 않는다면 이 routine이 I-cache를 flush해야 합니다.

``void flush_icache_page(struct vm_area_struct *vma, struct page *page)``

`flush_icache_page()`의 모든 기능은 `flush_dcache_folio()`와 `update_mmu_cache_range()`로 구현할 수 있습니다. 향후에는 이 interface를 완전히 제거하는 것이 목표입니다.

vmap alias의 I/O coherency

마지막 API 부류는 kernel 내부에서 의도적으로 alias된 address range에 대한 I/O를 다룹니다. 이러한 alias는 `vmap`/`vmalloc` API로 만듭니다. Kernel I/O는 physical page를 통해 이루어지므로 I/O subsystem은 user mapping과 kernel offset mapping만 alias라고 가정하지만, vmap alias에서는 이 가정이 맞지 않습니다.

따라서 vmap 영역에 I/O를 수행하는 kernel code는 I/O 전에 vmap range를 flush하고 I/O가 돌아온 뒤 invalidate하여 coherency를 직접 관리해야 합니다.

``void flush_kernel_vmap_range(void *vaddr, int size)``

`flush_kernel_vmap_range()`는 vmap 영역의 주어진 virtual address range에 대해 kernel cache를 flush합니다. Kernel이 vmap range에서 수정한 data가 physical page에 보이게 하여 이 영역에서 I/O를 안전하게 수행하도록 합니다. 이 API는 해당 영역의 offset map alias까지 flush하지는 않습니다.

``void invalidate_kernel_vmap_range(void *vaddr, int size) invalidates``

`invalidate_kernel_vmap_range()`는 vmap 영역의 주어진 virtual address range cache를 invalidate합니다. I/O가 physical page에서 진행되는 동안 processor가 data를 speculative read하여 cache를 stale하게 만드는 것을 막습니다. 이 작업은 vmap 영역으로 data를 읽어 들이는 경우에만 필요합니다.