Line in the sand, or, Cache me outside

Recently I’ve been poking at a JIT. Long ago, The Story of Mel captivated me with the line “If a program can’t rewrite its own code, what good is it?” The idea of self-modifying code was fascinating, but also infuriatingly annoying on x86 with its variable instruction length. ARM thankfully makes it pretty straightforward, with uniform instruction sizes (4 bytes).

One non-annoyance of x86, however, is its strong ordering and coherency. If you write to a few bytes ahead of the program counter, you’ll probably be fine? A ton of transistors are burned on cache snooping to make this magic happen. ARM, on the other hand, makes you need to do this yourself. Not doing so, however, allows us to peel back some of the magic and get a better idea of what’s going on under the hood.

Apple’s M-series silicon achieves a lot of its performance by caching substantial amounts of data. Going all the way out to DRAM is a performance and power killer, so a large, complex cache subsystem operates to minimize that expense. Like most Harvard Architecture designs, instructions are treated differently from data. Quite differently from x86, in fact (which also treats instructions differently, but still does a bunch of snoops to maintain the illusion of a Von Neumann Architecture machine. Making changes to instructions on ARM requires manual cache invalidation. We’re given a couple tools to do this: sys_icache_invalidate (man page) or maybe __builtin___clear_cache. The latter eventually falls through the former, and the former is, luckily, open source via libPlatform. Unluckily, it’s written in assembly. Doubly-unluckily, the assembly is apparently written by hardware engineers or something, because it’s pretty bad (check out the comment — “//we did some invalidates, time to maybe DSB?” — they’re not sure if they should inject a store barrier or not, mid-loop. And they check the comm_page every time to see if they should DSB (Data Store Barrier), doing a bunch of extraneous work). Silicon engineers are often geniuses, but I generally find their software source code to be … unsatisfying.

There are a couple neat parts of this code though. You can see some arcane instructions like ic ivau, isb, and dsb ish (RISC? Ha), and with some thought you can see that generally it’s a for loop over a range of addresses, stepping by 64 bytes, via the line

#define MMU_I_CLINE 6       // cache line size as 1<<MMU_I_CLINE (64)

Wait a minute. 64 bytes. What is this, a cache line for ants? Everyone knows that M2s have a cache line size of 128 bytes! sysctl says so:

% sysctl hw.cachelinesize
hw.cachelinesize: 128

Even ChatGPT says so:

I want to trust the experts, but the experts don’t agree with the experts, and only an expert can deal with the problem. So now we really actually have twice the problem. Maybe this code was just written in darker times, with smaller cache lines, and it’s now pumping out twice as many barriers and invalidations? Or maybe the instruction cache line size isn’t actually 128 bytes? Rather than speculate, let’s explore.

To do this experiment (determining the One True Instruction Cache Line Size), we’re going to need to do some dancing because of security junk. We’ll also implement our own simplified instruction cache invalidation function that takes different step sizes so we can watch what happens.

Specifically, we’re going to need to use a special flag with mmap to get W^X memory for a JIT (MAP_JIT), and we’re going to need to use pthread_jit_write_protect_np (man page) to toggle the write/execute bits (how this function works is another cool story for another time). Then we’ll set up a function that does some known work (increment a counter each instruction for a known number of instructions). We’ll run it, and then we’ll toggle W^X, change it to no-ops, and run it again. This will, surprisingly for those coming from x86-land, give the old result, because it’s all in the instruction cache. Then we’ll invalidate the instruction cache with varying strides, run it again, and see what happens. These two modes — adding 1, and adding 0 — will allow us to calculate roughly how many instructions ‘flip’ for each invalidation. We could also just invalidate the first address and see what the difference is in the output, but where’s the fun in that?

Here’s the code:

#include <pthread.h>
#include <stdint.h>
#include <stdlib.h>
#include <sys/mman.h>
#include <stdio.h>
// Compile with: clang icl.c -o icl -std=c17
uint64_t (*compute)(uint64_t initial);
static void invalidate(uint64_t start, uint64_t stop, const uint32_t size)
{
    for (; start < stop + (size - 1); start += size)
        __asm__("ic ivau, %[in]" ::[in] "r" (start));
    __asm__("dsb ish\nisb");
}
int main(int argc, char **argv)
{
    const uint32_t step = argc > 1 ? atoi(argv[1]) : 64;
    void *base = mmap(NULL, 16384, PROT_WRITE | PROT_EXEC | PROT_READ, MAP_PRIVATE | MAP_ANON | MAP_JIT, -1, 0);
    printf("base address: %p\n", base);
    uint32_t *instructions = (uint32_t*)base;
    pthread_jit_write_protect_np(0);    // make it writable (not executable)
    for (int i = 0; i < 1024; ++i)
        instructions[i] = 0x91000000 | (1 << 10);   // add x0, x0, #1
    instructions[1024] = 0xd65f03c0;    // ret
    compute = (void*)base;
    pthread_jit_write_protect_np(1);    // make it executable (not writable)
    uint64_t result = compute(0);   // execute it
    printf("First run result: %lld\n", result);
    pthread_jit_write_protect_np(0);
    for (int i = 0; i < 1024; ++i)
        instructions[i] = 0x91000000;   // add x0, x0, 0 (nop)
    pthread_jit_write_protect_np(1);
    result = compute(0);
    printf("second result (modified but cached): %lld\n", result);
    invalidate((uint64_t)base, ((uint64_t)base) + 4096, step);
    result = compute(0);
    printf("third result (cache invalidated): %lld\n", result);
    return 0;
}

This program maps 16KB (the page size on this machine), and makes a 1025-instruction function that adds 1 to x0 for each instruction except the last one, which is a ret. x0 is both the first argument and the return value, making it an easy ABI-compliant way to get values into and out of our function (we’ll just pass zero for this example though).

We get a program called icl that takes an optional argument for the step size. Without it, it defaults to 64. Probably don’t use 0 or it’ll just loop forever uselessly. Anyway, running it with no arguments gives us the following output:

% ./icl
base address: 0x102c90000
First run result: 1024
second result (modified but cached): 1024
third result (cache invalidated): 0

We can clearly see the effect of the instruction cache clinging on to our function. The second run should produce 0, but it returns 1024 still. Once we invalidate in 64-byte steps, we get the expected 0 though.

When we run with a step size of 128, we get something different:

% ./icl 128
base address: 0x104b64000
First run result: 1024
second result (modified but cached): 1024
third result (cache invalidated): 512

512?! How is that even possible? The answer lies in stepping too large — by walking in 128-byte steps, we miss every other 64-byte instruction cache line, so those instructions (add 1) remain, while the rest are re-fetched to their new add-0 state. In aggregate, we get half the old function and half the new. With a non-trivial function, this of course would be complete and utter chaos.

Curiously, if we use 65 as the step, we also correctly get 0. This might just be down to luck though - 4096 bytes is 64 64-byte cache lines, so we still touch them all (the ret doesn’t change so it doesn’t need to get invalidated to behave properly).

Feel free to try some other values and see what neat results pop out. We now know by experimental proof that at least some of the cache lines on M-series silicon are not 128 bytes. We verified this empirically, and without waiting for an expert to tell us. When in doubt, You Can Just Do Things.