Caches and Virtual Memory

A cache needs an address to look up, and a processor with virtual memory has two to choose from: the virtual address the program uses, or the physical address the memory uses. Translation takes time, so waiting for it slows every hit; but using virtual addresses creates strange problems when two addresses mean the same place. Real first-level caches use a clever mix of both. This article explains the options, the synonym problem, the size rule that VIPT caches must obey, and how designers get around it.

12 min read | Intermediate

What You'll Learn

• Compare physically and virtually addressed caches
• Explain synonyms and homonyms
• Explain how a VIPT cache looks up data before translation finishes
• Calculate the largest VIPT cache for a page size and associativity

The Problem

Cache Organization described a cache that takes an address, splits it into tag, index and offset, and looks it up. TLBs and Page Table Walks described a TLB that turns a virtual address into a physical one. Both must happen on every load, in very little time. The question is in what order, and which address the cache uses for its index and tag.

Four combinations exist in principle. Three are used. They are named by what forms the index and what forms the tag: V for virtual and P for physical.

PIPT: Physically Indexed, Physically Tagged

The cleanest choice is to translate first and then use the physical address for everything. A physical address names a unique location, so there is no ambiguity at all. Two processes that share a page find the same cache line, a context switch needs no cache flush, and other agents, such as other cores, can look in the cache with a physical address.

The drawback is time. The TLB lookup comes before the cache lookup, in series, which adds at least a cycle to every hit, or forces a longer clock period. For a first-level cache, this hurts. For L2 and L3, it is fine: by then the physical address is already known. So nearly all second- and third-level caches are PIPT.

VIVT: Virtually Indexed, Virtually Tagged

The opposite choice uses the virtual address for everything, so the TLB is needed only on a miss. That is as fast as possible. But the virtual address does not uniquely name a location, and this creates two problems.

A homonym is one virtual address that means two different things: address 0x1000 in process A and address 0x1000 in process B. Without care, B could read A's data from the cache. The fix is either to flush the cache on every context switch, which is painful, or to add the ASID to each tag.

A synonym, or alias, is the reverse: two virtual addresses for the same physical location, for example a shared library mapped at different addresses in two processes, or the same file mapped twice in one process. Now two copies of the same data can sit in the cache at different places. A write to one leaves the other stale, which is a real correctness bug. Handling this in a VIVT cache is complicated, and few modern processors use one for data. A VIVT design does still make sense for an instruction cache, in some designs, because instructions are rarely written.

VIPT: The Best of Both

Most first-level caches use the third option: virtually indexed, physically tagged. The key insight is that the page offset, the low 12 bits of the address for 4 KB pages, does not change in translation. If the cache's index and line offset come entirely from those bits, then the virtual and physical index are the same thing. So the cache can start its lookup right away, at the same time as the TLB:

Both finish at about the same moment. The cache has read the tags of the selected set, and the TLB gives the physical page number, which is compared with those tags. The tag is physical, so synonyms are no problem: both virtual names of a location have the same physical tag and, with the rule below, the same index. Homonyms are no problem either, since the physical tag is different.

This gives the speed of a virtual cache and the safety of a physical one.

The Size Rule

There is a catch. The index and line offset must fit inside the page offset:

index bits + line offset bits <= page offset bits

The number of index and offset bits together sets the size of one way of the cache:

size of one way = cache size / ways = number of sets x line size
one way must be no larger than a page

With 4 KB pages, each way can be at most 4 KB. A direct-mapped VIPT cache can be only 4 KB. To make it larger, you must add ways:

This is why so many processors have a 32 KB, 8-way L1 data cache, and it explains the 48 KB, 12-way caches of some recent designs. The size is limited by page size, more than by anything else, and associativity is partly a way of getting more capacity. So high associativity at L1 is not only for reducing misses, as Cache Sizing Studies shows.

A chip designed around a larger minimum page has more freedom. A system that uses 16 KB as its base page size can have a much larger VIPT L1. Some phone and laptop processors do exactly that.

Going Past the Limit

If the index does use a bit or two above the page offset, the synonym problem returns, because those bits may differ between two virtual names of the same location. Designers deal with this in a few ways:

• Page coloring: the OS guarantees that two virtual pages mapped to one frame also agree in those bits. It is a software rule, and it restricts allocation slightly.
• Alias detection in hardware: on a miss, the cache checks the other possible sets for the same physical tag, and it removes or moves the copy. This adds some logic and a few cycles on misses, and they are rare.
• Using L2 inclusion: a physically addressed L2 records where each line lives in L1, and can find and remove a copy.

Timing in a Real Pipeline

In a load's path through the pipeline, the sequence looks like this:

cycle 1: compute the virtual address in the AGU
cycle 2: index into the cache, read all tags in the set; TLB lookup at the same time
cycle 3: compare the physical page with the tags, select the way, align the data
cycle 4: data forwarded to dependent instructions

The way selection can be sped up by way prediction, which guesses the matching way from the virtual address, and delivers the data early, checking afterwards. A TLB miss during this sequence stalls the load, and the walker runs, while other work may continue in a large core.

Beyond the First Level

At L2 and L3, the choice is easy: they are PIPT. By the time a request leaves L1, the physical address is known, and coherence traffic from other cores and from I/O uses physical addresses too. Cache Coherence Protocols depends on that.

The hardware page table walker also goes through this path. It reads PTEs by physical address, usually through the L2 cache. A VIPT L1 is often bypassed by the walker, or it can use it, depending on the design.

Instruction caches face the same choice as data caches, and they are usually VIPT as well. Since code is shared far more often than data, for example one copy of a library in many processes, physical tags are especially valuable there: every process finds the same cached instructions, however its own map arranges them.

Side Channels Through the Cache

A cache shared between processes leaks information: one program can tell which lines another used by timing its own accesses. Physical tags do not stop this. Some attacks depend on the fact that the index comes from known bits of the address, so that an attacker can pick addresses that land in a chosen set, and watch it. Defenses include hashing the set index in large shared caches, so that this mapping is secret, and flushing or partitioning caches between security domains.

This is a recent concern. For decades, caches were designed purely for performance, and it was assumed that timing could not be used to leak secrets. The result is that a great deal of recent architecture research is about closing those channels without losing the speed.

Physical tags also mean that a VIPT cache needs no flush on a context switch. A line stored for one process can only hit if a later access translates to the same physical address. Different processes translate to different frames, unless they really do share that memory, and in that case a hit is correct.

When you read that a core has a 32 KB, 8-way cache, you can now see more than a size. That shape is a direct result of the 4 KB page.

Common Mistakes