Virtually Indexed Caches and the Page Coloring Problem

A load cannot complete until its tag is compared, and the tag is physical because the cache must not care which virtual address a line arrived under. The translation itself takes time: a TLB hit costs a cycle or two, a TLB miss costs a page walk of tens to hundreds of cycles. If the cache waited for the translation before starting its array access, every load would pay that latency twice. The standard resolution is to split the address, start the array access with the bits that are already known, and compare the physical tag later. That split works cleanly only within one page, and the boundary is where the interesting problems begin.

Which bits survive translation

A virtual address and its physical counterpart differ in the page number and agree in the page offset. For a 4 KiB page, the low 12 bits are identical in both. The tag must come from the physical address, because two processes may map different virtual pages to the same physical frame and the cache must treat them as the same line. The index, however, may come from either, provided it is consistent.

If the index is taken from virtual bits that lie entirely within the page offset, the index is the same value the physical address would produce. The cache can therefore index and read the data array in parallel with the TLB lookup, then compare the physical tag once translation completes. This is the virtually indexed, physically tagged (VIPT) arrangement, and it is what almost every L1 does, because it removes the translation latency from the hit path.

The constraint is arithmetic. With S sets, the index needs log2(S) bits, and those bits occupy positions [log2(line), log2(line) + log2(S)) of the address. For the index to fit inside a 12-bit page offset with 64-byte lines, 6 + log2(S) ≤ 12, so S ≤ 64. A 64-set cache with 8 ways holds 512 lines, 32 KiB. That is exactly the size of a typical L1 data cache, and the coincidence is not one: the cache size is chosen to be the largest that a VIPT design can build without aliasing on 4 KiB pages.

/* VIPT lookup: index from the virtual address, tag from the physical. */
struct line *vipt_lookup(struct cache *c, unsigned long vaddr,
                         unsigned long paddr, unsigned long *tag)
{
    unsigned index = (vaddr >> LINE_BITS) & (c->sets - 1);   /* fits in page offset */
    unsigned long ptag = paddr >> (LINE_BITS + c->index_bits);
    struct set *s = &c->set[index];
    for (int w = 0; w < WAYS; w++)
        if (s->line[w].valid && s->line[w].tag == ptag)
            return &s->line[w];
    return NULL;
}

The index extraction happens before the TLB result is available; the tag comparison after. The two overlap in the pipeline, which is the whole point.

Synonyms, and why they are not allowed

If the index extended beyond the page offset, two virtual addresses in different pages could map to the same physical frame and produce different index bits — because the virtual page numbers differ while the physical frame number is the same. The same physical line would then be installed in two different sets, and a write through one copy would leave the other stale. These duplicate mappings are called synonyms or aliases, and they break the invariant that a physical address has one home in the cache.

Hardware handles the problem in two ways. The first is to prevent it: keep the index within the page offset, as above, so aliasing cannot arise from the index. The second is to detect it: search for a synonym when a line is installed, which requires either a reverse map from physical to virtual or a probe of every possible index — an operation whose cost scales with the cache size and which is impractical for a large array. A fill that has already reserved a way through the miss handling logic must complete that probe before it can place the line, which is one reason synonym searches are confined to small caches.

A third approach allows synonyms and fixes them at the point of write. A write to a line whose synonym may exist requires the cache to either invalidate the other copy or update it, and the cost is paid on every store to an aliased line. Systems that permit aliasing usually restrict it to read-only mappings — shared libraries, for instance, where two processes map the same physical page read-only — because a read-only alias cannot diverge. The index bits themselves come from the decomposition described in set associativity and index decoding, and the choice of how many bits to take is what decides whether a design is alias-free at all.

The page-size dependence is worth stating. A design that is alias-free on 4 KiB pages may alias on a larger page or a smaller one. With 64 KiB pages, the page offset is 16 bits and the index has far more room; with 1 KiB pages, only 10 bits are guaranteed and the same cache would exceed the boundary. Some architectures therefore specify a minimum page size, or require that all mappings of a page use the same virtual color, which is the software-side version of the same constraint.

Coloring: the software half of the problem

A physically indexed cache has no aliasing constraint at all, because the index comes from the physical address and the physical address is unique. What it has instead is a dependence on which physical frames the operating system assigns. Two virtual pages that a program accesses in sequence may be backed by physical frames whose index bits are identical, in which case both pages compete for the same sets.

This matters because the kernel’s page allocator hands out frames in whatever order is convenient. For a program that allocates a large array and touches it sequentially, the physical frames may be scattered arbitrarily, and the distribution across sets is effectively random. For a program with a working set slightly larger than the cache, random distribution is exactly what causes conflict misses: some sets hold three hot lines while others hold none.

Page coloring is the technique of making the assignment non-random. Coloring applies when the index is wider than the page offset: for a 256 KiB, four-way cache with 64-byte lines there are 1024 sets and 10 index bits, of which six lie inside a 4 KiB page offset and four above it. The four bits above the offset are the color, so there are 16 colors. Each physical page contributes 64 lines that cover 64 consecutive sets, and the color says which of the 16 groups of 64 sets the page occupies. The kernel allocates frames of a requested color to a process, so a program that needs many pages receives a spread across colors rather than an arbitrary mix.

/* Color of a physical frame: the cache index bits above the page offset. */
#define PAGE_SHIFT   12
#define LINE_SHIFT    6
#define INDEX_BITS   10                     /* 1024 sets */

static unsigned page_color(unsigned long pfn)
{
    unsigned long byte_addr = pfn << PAGE_SHIFT;
    unsigned long index = (byte_addr >> LINE_SHIFT) & ((1UL << INDEX_BITS) - 1);
    unsigned      in_page_bits = PAGE_SHIFT - LINE_SHIFT;   /* 6 index bits known */
    return (unsigned)(index >> in_page_bits);               /* 4 bits: 16 colors */
}

With a balanced assignment, a program whose pages span all 16 colors fills every group of sets evenly, and the conflict structure becomes predictable. The benefit is largest for programs whose working set is a few times the cache size, which is the regime where conflict misses dominate capacity misses. A cache whose index fits entirely within the page offset has one color — every page touches every set once — and coloring has nothing to control.

The cost is allocator complexity and fragmentation. A color-aware allocator must keep free lists per color, and a request for a specific color may have to wait or fall back when that color’s list is empty. On a machine with many processes and long uptime, the free lists of different colors drift apart, and a large contiguous allocation may not be satisfiable in a single color. Real kernels therefore apply coloring as a preference rather than a requirement, and some have removed it entirely when the cache’s indexing became hashed, which destroys the correspondence between physical address bits and sets.

Hashed indexing and the end of coloring

A cache that hashes the physical index bits before selecting a set removes the structured relationship between address and set. Two addresses that differ in a few bits no longer land in a predictable pair of sets, and a stride that would have hammered one set spreads across all of them. The benefit is tolerance for the access patterns that coloring was designed to fix; the cost is that the software cannot control the distribution at all, because the mapping is no longer invertible in a useful way.

Once the index is hashed, coloring loses its meaning: there is no color, because the set is not a function of a contiguous slice of the address. The kernel’s job reduces to giving the program frames that are physically distributed, which is what a normal buddy allocator does anyway. The trade is that the hardware now carries the burden of avoiding pathological distributions, and it does so with a hash function whose quality is fixed at design time rather than chosen per workload.

There is a middle ground in some designs: the index is hashed, but the hash is chosen so that the result is still computable from bits available before translation, preserving the VIPT property. That requires the hash to operate only on bits within the page offset, which limits the mixing to a few bits and reduces the benefit. The designs that hash aggressively are therefore the physically indexed last-level caches, where translation latency is not on the critical path because the access is already a miss in the upper levels.

The interaction with the rest of the hierarchy is what makes the topic practical. A VIPT L1 behind a physically indexed L2 means the L1 can alias in principle if the page size is smaller than the index span, while the L2 cannot. A design that mixes the two must therefore enforce the constraint at the L1’s boundary, which is why the page size and the L1 size are chosen together and why changing one without the other is a source of subtle bugs rather than a performance regression.