Cache on delivery

There was a period of two to three years where I conducted a couple technical interviews per week, totaling hundreds of interviews. We were trying to fill a role, and had somewhat esoteric requirements (getting the right personal, technical, and interpersonal skills for our team was quite demanding). One of my favorite questions was this: “Describe in detail what this line of code does: uint8_t value = anAddress[index];”

The reason I liked this question isn’t because it’s a trick question or anything (I was pretty open about it not being a trick or joke), but because it allowed the interviewee to explore depths ranging from “C” to “transistors”, to gauge how comfortable they were traveling the “full stack” (before that came to mean the client/server goop it does today). Registers, Address translation (virtual to physical), cache effects, page faults, DRAM, and more, fall out of this simple question with just a tiny bit of well-placed followup questions. It can also branch into compiler optimization, heap behavior, and even ASLR. You could also add a const and/or volatile to get even more fun without much additional interruption.

Now, I don’t share this to indicate that I have some kind of excellent interviewing skills (I don’t), or as a spoiler question for your own technical interview (these experiences of mine were nearly a decade ago at this point), but because this question among others lead me to my own curiosities. I like to reflect on my own questions to see how else I can explore these problems.

Here’s the curiosity that once came to me: When you write a byte to ram, the cache subsystem will need to read the remaining bytes in the cache line in order to have a coherent view of memory (this doesn’t always apply to “non-temporal” reads and writes). But what if you knew you were going to write a lot of bytes (zero-filling or initializing a large data structure, or doing some kind of semi-expensive computation where you’d fill in elements, but not all right away)? Could you tell the cache subsystem “Don’t worry about the extra bits, I’m going to set those too”? Some architectures, like x86, have pretty limited cache manipulation controls. Others, like ARM or MIPS, have relatively rich, or at least implementation-defined cache control mechanisms. As it turns out, Aarch64, such as Apple’s M-series of CPUs, features an instruction that will let you zero a cache line rather than fetching it, saving precious DRAM bandwidth. Just as in the last article, we’re running into needing to know the real cache line size of the CPU, not the marketing materials. This time, it’s the data cache though, not the instruction cache.

The instruction in question is dc zva, standing for Data Cache - Zero by Virtual Address (Obviously. Remember, this is a RISC machine). It essentially allocates a cache line for the virtual address in question, and fills it with zeros rather than fetching the backing bytes. This behavior, zero-filling, allows us to inspect just how large a cache line is — we can allocate a few cache lines (or speculated cache lines), initialize them with non-zeros, then ZVA somewhere inside the allocation. We can then look at the allocation, and see how big the zero’d out section is.

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <string.h>
// compile with clang -Os zva.c -o zva
static inline void dc_zva(void *addr) {
    asm volatile("dc zva, %0" :: "r"(addr));
}
int main(void) {
    uint64_t zva_size = 128;
    printf("ZVA block size: %llu bytes\n", (unsigned long long)zva_size);
    // Allocate memory aligned to ZVA block size
    void *buf = NULL;
    if (posix_memalign(&buf, zva_size, zva_size) != 0) {
        perror("posix_memalign");
        return 1;
    }
    // Fill with 0xaa
    memset(buf, 0xAA, zva_size);
    printf("Before ZVA: first 8 bytes = ");
    for (int i = 0; i < 8; i++)
        printf("%02X ", ((unsigned char*)buf)[i]);
    printf("... mid 8 bytes = ");
    for (int i = 0; i < 8; i++)
        printf("%02X ", ((unsigned char*)buf)[60 + i]);
    printf("...\n");
    dc_zva(buf);
    printf("After  ZVA: first 8 bytes = ");
    for (int i = 0; i < 8; i++)
        printf("%02X ", ((unsigned char*)buf)[i]);
    printf("... mid 8 bytes = ");
    for (int i = 0; i < 8; i++)
        printf("%02X ", ((unsigned char*)buf)[60 + i]);
    printf("...\n");
    free(buf);
    return 0;
}

When we run this, we get the following output:

% ./zva
ZVA block size: 128 bytes
Before ZVA: first 8 bytes = AA AA AA AA AA AA AA AA ... mid 8 bytes = AA AA AA AA AA AA AA AA ...
After  ZVA: first 8 bytes = 00 00 00 00 00 00 00 00 ... mid 8 bytes = 00 00 00 00 AA AA AA AA ...

Looking carefully, we can see bytes 60 to 68 transition from 00 to AA. This would be the middle of a 128-byte cache line, or the transition between 2 64-byte cache lines. Our allocation is 128-byte aligned, so the start will be cache-line aligned for both 64- and 128-byte cache line sizes. From this, we can see that the data cache lines are also 64 bytes.

One caveat if you wish to deploy this yourself: If your address isn’t cache-line aligned, you’ll also zero some bytes behind your allocation. This might clobber important data! Be extremely careful using this!

So, just where did this 128-byte line size nonsense even come from?! None of our cache abuse tests have revealed a 128-byte cache line size. I think the only evidence for this (other than sysctl) are microbenchmarks that attempt to characterize cache behavior by timing strided reads and writes. In those cases, I suspect the predictors a simply able to anticipate 2-cache-line-sized walks?

(The above is from an M2 in a MacBook Air. Comment if you’re able to get a different behavior!)