We tend to think of caches strictly in terms of capacity, and that suffices for most purposes. To understand chip designers’ motivation for a way predictor, we need to go beyond the idea that, say, a 32-KiB L1 cache can hold 32 KiB of data. Caches traffic in cache lines, aligned blocks of fixed size, that move between levels of the hierarchy as a unit. On x86, our 32-KiB cache can hold 512 cache lines, each 64 bytes in size. In that example, a fully associative cache would ignore the least significant 6 bits (as an offset into the 64-byte cache line) and examine all the other bits in the address to see if the cache line is resident. The bits used to make this determination are known as the tag. Examples of fully associative caches in modern CPUs include TLB entries for large pages (which can use a smaller tag due to discarding more least significant address bits) and store buffers, necessarily small structures, due to the high cost of exhaustive search.

For caches too big for full associativity, CPU designers use set-associative caches, where an address maps to a set and may occupy any of the several ways that make up that set; the number of ways is the number of lines one set can hold. Because a cache line covers a contiguous, aligned block of memory, an address divides into three fields: the low bits are the offset of a byte within its block, the next are the index of the set that block must occupy, and the rest identify which block it is, stored alongside the data as the tag. On Zen 4, whose 32-KiB L1 data cache is 8-way associative with 64-byte lines, that puts the offset in bits [5:0] and the index in bits [11:6], which together are the page offset and so are the same in the linear and physical addresses, while the tag is the physical address above bit 11, which is not available to the cache until it is supplied by the TLB1.

If a program’s accesses happen to fall unevenly across sets of a cache, thrashing may occur, with e.g. nine lines competing for residency in an 8-way set, however idle the rest of the cache may be. In such cases, the hardware’s behaviors that govern what happens are undocumented, and difficult to infer from software.

To check whether a line is resident, the cache reads every way of the set at once and discards all but the one whose tag matches, which is as wasteful as it is fast. Reading 8 ways for one hit means seven reads whose results are discarded, and the energy spent on them is spent on every load executed by the program. The way predictor exists to avoid that expense by guessing, before the tags have been compared, which single way is likely to hold the line.

AMD’s implementation keeps a small hash of the linear address that last brought each line into the L1 data cache, and consults it on every load. The guide states the arrangement directly: “the L1 data cache tags contain a linear-address-based microtag (utag) that tags each cache line with the linear address that was used to access the cache line initially. Loads use this utag to determine which way of the cache to read.”2 The structure therefore holds a derived summary of an address, not a copy of any data, and it predicts the physical way of a set where a program’s load will land.

The way predictor also provides an answer the machine does not have to wait for translation to produce, which amplifies the benefit of a correct prediction. A L1 data cache is indexed with untranslated bits and tagged with physical ones, so the set can be read while the TLB is still working, and only the tag comparison needs the physical address. Predicting the way from the linear address moves one more step ahead of the translation, and leaves the physical tag to confirm the guess afterward.

As far as our covert caches taxonomy is concerned3, the prediction is allowed to be incorrect, and AMD says so: “it is possible for the utag to be wrong in both directions: it can predict hit when the access will miss, and it can predict miss when the access could have hit.” Either way, the physical tag catches the error, and a fill from the L2 cache repairs the µtag. That places the way predictor in the second family of covert caches, the ones that are not kept consistent. It sits awkwardly there, though, because alongside the prediction runs a rule that is not a prediction at all: at a given index, only one cache line with a given linear hash is accessible at any time. That rule is a constraint on what the cache may hold, and it can impact program behavior. Two virtual addresses that translate to the same physical line are aliases of each other, an arrangement software deliberately creates when it maps a buffer twice, and that an operating system creates whenever two processes share a page. The rule says that only one alias at a time may reach a line through the L1 cache.

The idea predates the µtag by two decades: prediction by most-recently-used bit was studied in the late 1980s, and the MIPS R10000 shipped a form of it in 1996 for its off-chip secondary cache, keeping an on-chip bit array that recorded which way of each set had been used last, which enabled a two-way cache to be built with a single extra address pin. The Alpha 21264 applied it to the instruction cache, combining “the speed advantage of a direct-mapped cache with the lower miss ratio of a two-way set-associative cache,” at a misprediction cost its designers put at a single-cycle bubble and a hit rate of 85 percent or better4. AMD has predicted ways in the L1 data cache since Bulldozer in 2011, whose guide describes a “4-way predicted L1 data cache,” and the same µtag text appears in every Zen optimization guide through Zen 5.

Intel documents no way predictor in any current core, and the precedent on that side is older, and stranger: NetBurst’s L1 data cache could hold only one instance of a line at a time, and on early models, the conflict applied to addresses agreeing in bits 15 through 6, which Intel called a 64K aliasing conflict. The symptom is the one AMD’s µtag produces, arrived at by a different route.

Whether anyone besides AMD predicts ways today, public documentation does not say: nothing obliges a vendor to describe a structure whose only effect is on timing.

When the Hardware Misbehaves

The performance pathology follows from the one-alias rule rather than from misprediction, because when a program reaches the same physical line through two different virtual addresses, the two do not hash to the same µtag, so a load through the second alias misses in the L1 cache even though the data is resident. When this happens, AMD claims the latency “will generally be no larger than that of an L2 cache hit,” which on Zen 4 is no less than 14 cycles against four or five for a hit5. The penalty is not confined to one thread, because a load issued by the sibling thread of the same physical core disturbs the µtag in the same way.

The programs at risk are the ones that deliberately create multiple virtual mappings onto the same physical memory, of which the clearest case is a double-mapped ring buffer, which places the same physical pages at two consecutive virtual addresses so that a record spanning the end of the buffer can be read without splitting it; Linux’s BPF ring buffer maps each data page twice for the same reason6. Shared memory attached at different addresses in different processes is the other common case, and no measurement of any of these on an AMD core appears to have been published.

Collisions are possible without any aliasing at all, since two unrelated lines whose linear addresses happen to hash alike cannot both be accessible at one index, and it is therefore possible for an 8-way set to thrash with only two lines resident.

Ironically, AMD has been rewarded for its transparency in disclosing the existence and behavior of the way predictor with a security attack: Take A Way, disclosed to AMD in August 2019 and published in 20207. Its authors reverse-engineered the hash and built two attacks. Collide+Probe exploits µtag collisions to observe the memory accesses of a victim sharing a logical core, and needs neither shared memory nor knowledge of physical addresses, which distinguishes it from the cache attacks that require both. Load+Reload uses an alias to evict a shared line from the sibling thread’s L1 cache alone, which is stealthier than Flush+Reload because it disturbs nothing below the L1. They demonstrate a covert channel at 588.9 kilobytes per second, a break of kernel address space layout randomization, a reduction of address space randomization from JavaScript and across a hypervisor boundary, and recovery of AES keys from a T-table implementation.

AMD’s published response declined the framing: “AMD believes these are not new speculation-based attacks.” It issued no CVE and no numbered bulletin, only a web advisory recommending that users keep their systems updated and follow secure coding practices. One of the paper’s authors replied that the attacks had never been claimed to be speculative, and another observed that the way predictor continued to behave as described.

What the paper did not establish is how far the attacks reach, since its table of tested cores runs from Bulldozer to Zen 2, and Excavator, Zen 3, Zen 4, and Zen 5 were not tested. The mechanism is still documented in the Zen 3, Zen 4, and Zen 5 guides, the last of which has a load read one way “instead of all 12,” so the structure persists; whether Collide+Probe still works on those cores is unestablished either way.

How to Detect It

Nothing counts µtag hits or misses, and a search of the event lists for Zen 2 through Zen 5, and of AMD’s performance monitor counter document for Family 1Ah, finds no event mentioning the µtag, way prediction, or linear aliasing, and Intel’s cores have no such structure to count.

What remains is an indirect signal, which is the one Take A Way’s authors used: a working set that fits comfortably in the L1 cache, yet produces L1 misses served by the local L2 cache.

• Zen 4: ls_dmnd_fills_from_sys.local_l2, l2_cache_req_stat.dc_hit_in_l2

• Zen 3: ls_dmnd_fills_from_sys.lcl_l2

• Zen 2: ls_refills_from_sys.ls_mabresp_lcl_l2, l2_cache_hits_from_dc_misses

Note that LD_BLOCKS_PARTIAL.ADDRESS_ALIAS on Intel counts 4K aliasing between a load and an older store, which is a different mechanism in a different structure, and is no help here.

A direct measurement is straightforward to construct, and does not appear to have been published: create an anonymous file with memfd_create, map it twice, and pointer-chase alternately through the two mappings, comparing against the same chase through one mapping; the difference should be L2 latency on an affected core, and nothing on an Intel core.

Working Around It

Touch hot shared data through only one address. The remedy for linear aliasing is to pick a single virtual address for anything hot and reach it only that way. Where shared memory is attached by several processes, mapping it at the same address in each avoids the problem entirely, and the case to attend to is the one where those processes run as siblings on a single physical core. With a double-mapped ring buffer, reading each record through one alias, and not keeping the wrap region hot through both, would suffice. Since penalty is no worse than an L2 hit, this mitigation is only worth doing for hot data.

Constant-time discipline. Mitigating timing attacks on caches requires developers to build code whose memory access patterns do not depend on a secret. Since disabling way prediction is not yet possible, the paper proposed a keyed hash, and flushing the predictor on a context switch. Its software proposal was to map secret data many times and choose an address at random, which would manufacture precisely the condition that causes L1 cache hits to run at L2 cache performance.

Further Reading

• Lipp and coauthors, Take A Way — The reverse engineering of the µtag hash, and the two attacks built on it.

• Kessler, The Alpha 21264 Microprocessor — Way prediction applied to an instruction cache in 1998, with its hit rates and its single-cycle misprediction penalty.

• Yeager, The MIPS R10000 Superscalar Microprocessor — The earlier trick of predicting a way to save a pin, rather than to save energy.