Cache and TLB Flushing Under Linux¶

Author:

David S. Miller <davem@redhat.com>

This document describes the cache/tlb flushing interfaces calledby the Linux VM subsystem. It enumerates over each interface,describes its intended purpose, and what side effect is expectedafter the interface is invoked.

The side effects described below are stated for a uniprocessorimplementation, and what is to happen on that single processor. TheSMP cases are a simple extension, in that you just extend thedefinition such that the side effect for a particular interface occurson all processors in the system. Don’t let this scare you intothinking SMP cache/tlb flushing must be so inefficient, this is infact an area where many optimizations are possible. For example,if it can be proven that a user address space has never executedon a cpu (seemm_cpumask()), one need not perform a flushfor this address space on that cpu.

First, the TLB flushing interfaces, since they are the simplest. The“TLB” is abstracted under Linux as something the cpu uses to cachevirtual-->physical address translations obtained from the softwarepage tables. Meaning that if the software page tables change, it ispossible for stale translations to exist in this “TLB” cache.Therefore when software page table changes occur, the kernel willinvoke one of the following flush methods _after_ the page tablechanges occur:

1. voidflush_tlb_all(void)

   The most severe flush of all. After this interface runs,any previous page table modification whatsoever will bevisible to the cpu.

   This is usually invoked when the kernel page tables arechanged, since such translations are “global” in nature.

2. voidflush_tlb_mm(structmm_struct*mm)

   This interface flushes an entire user address space fromthe TLB. After running, this interface must make sure thatany previous page table modifications for the address space‘mm’ will be visible to the cpu. That is, after running,there will be no entries in the TLB for ‘mm’.

   This interface is used to handle whole address spacepage table operations such as what happens duringfork, and exec.

3. voidflush_tlb_range(structvm_area_struct*vma,unsignedlongstart,unsignedlongend)

   Here we are flushing a specific range of (user) virtualaddress translations from the TLB. After running, thisinterface must make sure that any previous page tablemodifications for the address space ‘vma->vm_mm’ in the range‘start’ to ‘end-1’ will be visible to the cpu. That is, afterrunning, there will be no entries in the TLB for ‘mm’ forvirtual addresses in the range ‘start’ to ‘end-1’.

   The “vma” is the backing store being used for the region.Primarily, this is used formunmap() type operations.

   The interface is provided in hopes that the port can finda suitably efficient method for removing multiple pagesized translations from the TLB, instead of having the kernelcall flush_tlb_page (see below) for each entry which may bemodified.

4. voidflush_tlb_page(structvm_area_struct*vma,unsignedlongaddr)

   This time we need to remove the PAGE_SIZE sized translationfrom the TLB. The ‘vma’ is the backing structure used byLinux to keep track of mmap’d regions for a process, theaddress space is available via vma->vm_mm. Also, one maytest (vma->vm_flags & VM_EXEC) to see if this region isexecutable (and thus could be in the ‘instruction TLB’ insplit-tlb type setups).

   After running, this interface must make sure that any previouspage table modification for address space ‘vma->vm_mm’ foruser virtual address ‘addr’ will be visible to the cpu. Thatis, after running, there will be no entries in the TLB for‘vma->vm_mm’ for virtual address ‘addr’.

   This is used primarily during fault processing.

5. voidupdate_mmu_cache_range(structvm_fault*vmf,structvm_area_struct*vma,unsignedlongaddress,pte_t*ptep,unsignedintnr)

   At the end of every page fault, this routine is invoked to tellthe architecture specific code that translations now existsin the software page tables for address space “vma->vm_mm”at virtual address “address” for “nr” consecutive pages.

   This routine is also invoked in various other places which passa NULL “vmf”.

   A port may use this information in any way it so chooses.For example, it could use this event to pre-load TLBtranslations for software managed TLB configurations.The sparc64 port currently does this.

Next, we have the cache flushing interfaces. In general, when Linuxis changing an existing virtual-->physical mapping to a new value,the sequence will be in one of the following forms:

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);

The cache level flush will always be first, because this allowsus to properly handle systems whose caches are strict and requirea virtual-->physical translation to exist for a virtual addresswhen that virtual address is flushed from the cache. The HyperSparccpu is one such cpu with this attribute.

The cache flushing routines below need only deal with cache flushingto the extent that it is necessary for a particular cpu. Mostly,these routines must be implemented for cpus which have virtuallyindexed caches which must be flushed when virtual-->physicaltranslations are changed or removed. So, for example, the physicallyindexed physically tagged caches of IA32 processors have no need toimplement these interfaces since the caches are fully synchronizedand have no dependency on translation information.

Here are the routines, one by one:

1. voidflush_cache_mm(structmm_struct*mm)

   This interface flushes an entire user address space fromthe caches. That is, after running, there will be no cachelines associated with ‘mm’.

   This interface is used to handle whole address spacepage table operations such as what happens during exit and exec.

2. voidflush_cache_dup_mm(structmm_struct*mm)

   This interface flushes an entire user address space fromthe caches. That is, after running, there will be no cachelines associated with ‘mm’.

   This interface is used to handle whole address spacepage table operations such as what happens during fork.

   This option is separate from flush_cache_mm to allow someoptimizations for VIPT caches.

3. voidflush_cache_range(structvm_area_struct*vma,unsignedlongstart,unsignedlongend)

   Here we are flushing a specific range of (user) virtualaddresses from the cache. After running, there will be noentries in the cache for ‘vma->vm_mm’ for virtual addresses inthe range ‘start’ to ‘end-1’.

   The “vma” is the backing store being used for the region.Primarily, this is used formunmap() type operations.

   The interface is provided in hopes that the port can finda suitably efficient method for removing multiple pagesized regions from the cache, instead of having the kernelcall flush_cache_page (see below) for each entry which may bemodified.

4. voidflush_cache_page(structvm_area_struct*vma,unsignedlongaddr,unsignedlongpfn)

   This time we need to remove a PAGE_SIZE sized rangefrom the cache. The ‘vma’ is the backing structure used byLinux to keep track of mmap’d regions for a process, theaddress space is available via vma->vm_mm. Also, one maytest (vma->vm_flags & VM_EXEC) to see if this region isexecutable (and thus could be in the ‘instruction cache’ in“Harvard” type cache layouts).

   The ‘pfn’ indicates the physical page frame (shift this valueleft by PAGE_SHIFT to get the physical address) that ‘addr’translates to. It is this mapping which should be removed fromthe cache.

   After running, there will be no entries in the cache for‘vma->vm_mm’ for virtual address ‘addr’ which translatesto ‘pfn’.

   This is used primarily during fault processing.

5. voidflush_cache_kmaps(void)

   This routine need only be implemented if the platform utilizeshighmem. It will be called right before all of the kmapsare invalidated.

   After running, there will be no entries in the cache forthe kernel virtual address range PKMAP_ADDR(0) toPKMAP_ADDR(LAST_PKMAP).

   This routing should be implemented in asm/highmem.h

6. voidflush_cache_vmap(unsignedlongstart,unsignedlongend)voidflush_cache_vunmap(unsignedlongstart,unsignedlongend)

   Here in these two interfaces we are flushing a specific rangeof (kernel) virtual addresses from the cache. After running,there will be no entries in the cache for the kernel addressspace for virtual addresses in the range ‘start’ to ‘end-1’.

   The first of these two routines is invoked aftervmap_range()has installed the page table entries. The second is invokedbeforevunmap_range() deletes the page table entries.

There exists another whole class of cpu cache issues which currentlyrequire a whole different set of interfaces to handle properly.The biggest problem is that of virtual aliasing in the data cacheof a processor.

Is your port susceptible to virtual aliasing in its D-cache?Well, if your D-cache is virtually indexed, is larger in size thanPAGE_SIZE, and does not prevent multiple cache lines for the samephysical address from existing at once, you have this problem.

If your D-cache has this problem, first define asm/shmparam.h SHMLBAproperly, it should essentially be the size of your virtuallyaddressed D-cache (or if the size is variable, the largest possiblesize). This setting will force the SYSv IPC layer to only allow userprocesses to mmap shared memory at address which are a multiple ofthis value.

Next, you have to solve the D-cache aliasing issue for allother cases. Please keep in mind that fact that, for a given pagemapped into some user address space, there is always at least one moremapping, that of the kernel in its linear mapping starting atPAGE_OFFSET. So immediately, once the first user maps a givenphysical page into its address space, by implication the D-cachealiasing problem has the potential to exist since the kernel alreadymaps this page at its virtual address.

voidcopy_user_page(void*to,void*from,unsignedlongaddr,structpage*page)voidclear_user_page(void*to,unsignedlongaddr,structpage*page)

These two routines store data in user anonymous or COWpages. It allows a port to efficiently avoid D-cache aliasissues between userspace and the kernel.

For example, a port may temporarily map ‘from’ and ‘to’ tokernel virtual addresses during the copy. The virtual addressfor these two pages is chosen in such a way that the kernelload/store instructions happen to virtual addresses which areof the same “color” as the user mapping of the page. Sparc64for example, uses this technique.

The ‘addr’ parameter tells the virtual address where theuser will ultimately have this page mapped, and the ‘page’parameter gives a pointer to thestructpage of the target.

If D-cache aliasing is not an issue, these two routines maysimply call memcpy/memset directly and do nothing more.

voidflush_dcache_folio(structfolio*folio)

This routines must be called when:

1. the kernel did write to a page that is in the page cache pageand / or in high memory

2. the kernel is about to read from a page cache page and user spaceshared/writable mappings of this page potentially exist. Notethat {get,pin}_user_pages{_fast} already call flush_dcache_folioon any page found in the user address space and thus drivercode rarely needs to take this into account.

Note

This routine need only be called for page cache pageswhich can potentially ever be mapped into the addressspace of a user process. So for example, VFS layer codehandling vfs symlinks in the page cache need not callthis interface at all.

The phrase “kernel writes to a page cache page” means, specifically,that the kernel executes store instructions that dirty data in thatpage at the kernel virtual mapping of that page. It is important toflush here to handle D-cache aliasing, to make sure these kernel storesare visible to user space mappings of that page.

The corollary case is just as important, if there are users which haveshared+writable mappings of this file, we must make sure that kernelreads of these pages will see the most recent stores done by the user.

If D-cache aliasing is not an issue, this routine may simply be definedas a nop on that architecture.

There is a bit set aside in folio->flags (PG_arch_1) as “architectureprivate”. The kernel guarantees that, for pagecache pages, it willclear this bit when such a page first enters the pagecache.

This allows these interfaces to be implemented much moreefficiently. It allows one to “defer” (perhaps indefinitely) theactual flush if there are currently no user processes mapping thispage. See sparc64’s flush_dcache_folio and update_mmu_cache_rangeimplementations for an example of how to go about doing this.

The idea is, first atflush_dcache_folio() time, iffolio_flush_mapping() returns a mapping, andmapping_mapped() on thatmapping returns %false, just mark the architecture private pageflag bit. Later, inupdate_mmu_cache_range(), a check is madeof this flag bit, and if set the flush is done and the flag bitis cleared.

Important

It is often important, if you defer the flush,that the actual flush occurs on the same CPUas did the cpu stores into the page to make itdirty. Again, see sparc64 for examples of howto deal with this.

voidcopy_to_user_page(structvm_area_struct*vma,structpage*page,unsignedlonguser_vaddr,void*dst,void*src,intlen)voidcopy_from_user_page(structvm_area_struct*vma,structpage*page,unsignedlonguser_vaddr,void*dst,void*src,intlen)

When the kernel needs to copy arbitrary data in and outof arbitrary user pages (f.e. forptrace()) it will usethese two routines.

Any necessary cache flushing or other coherency operationsthat need to occur should happen here. If the processor’sinstruction cache does not snoop cpu stores, it is verylikely that you will need to flush the instruction cacheforcopy_to_user_page().

voidflush_anon_page(structvm_area_struct*vma,structpage*page,unsignedlongvmaddr)

When the kernel needs to access the contents of an anonymouspage, it calls this function (currently onlyget_user_pages()). Note:flush_dcache_folio() deliberatelydoesn’t work for an anonymous page. The defaultimplementation is a nop (and should remain so for all coherentarchitectures). For incoherent architectures, it should flushthe cache of the page at vmaddr.

voidflush_icache_range(unsignedlongstart,unsignedlongend)

When the kernel stores into addresses that it will executeout of (eg when loading modules), this function is called.

If the icache does not snoop stores then this routine will needto flush it.

voidflush_icache_page(structvm_area_struct*vma,structpage*page)

All the functionality of flush_icache_page can be implemented inflush_dcache_folio and update_mmu_cache_range. In the future, the hopeis to remove this interface completely.

The final category of APIs is for I/O to deliberately aliased addressranges inside the kernel. Such aliases are set up by use of thevmap/vmalloc API. Since kernel I/O goes via physical pages, the I/Osubsystem assumes that the user mapping and kernel offset mapping arethe only aliases. This isn’t true for vmap aliases, so anything inthe kernel trying to do I/O to vmap areas must manually managecoherency. It must do this by flushing the vmap range before doingI/O and invalidating it after the I/O returns.

voidflush_kernel_vmap_range(void*vaddr,intsize)

flushes the kernel cache for a given virtual address range inthe vmap area. This is to make sure that any data the kernelmodified in the vmap range is made visible to the physicalpage. The design is to make this area safe to perform I/O on.Note that this API doesnot also flush the offset map aliasof the area.

voidinvalidate_kernel_vmap_range(void*vaddr,intsize)invalidates

the cache for a given virtual address range in the vmap areawhich prevents the processor from making the cache stale byspeculatively reading data while the I/O was occurring to thephysical pages. This is only necessary for data reads into thevmap area.