Cache Miss Handling and Patching Code at the Access Site

Every inline cache is empty once. The first execution of a property access performs the full lookup, and the interesting engineering is what the runtime does with the result: it must arrange for the second execution to be fast, and it must do so while the program continues to run, possibly on several threads, possibly inside a function that is itself being executed.

The simplest arrangement is a data table. Each access site has an index, the interpreter looks up the site’s entry in a per-function array, and the entry holds the cached layout and offset. Patching this table is a store, which is safe and requires no code modification. The cost is an extra load and an index computation on every access, and the index has to be kept in the instruction stream, which consumes code space.

The alternative is to rewrite the instruction sequence itself. The site’s code initially jumps to a runtime routine that performs the lookup; after the lookup, the runtime redirects that jump to a small block containing a guard and a load. The second execution never reaches the runtime. The cost is the patching machinery, which has to deal with instruction cache coherence, atomicity, and the possibility that another thread is executing the code being modified.

The miss stub as an entry point

The initial code at a site is not the full lookup. It is a short sequence that jumps to a shared stub, passing the identity of the site. The stub is shared across every uninitialized site in the isolate, so the code size cost of the uninitialized state is one jump per site rather than a copy of the lookup per site.

The stub performs three steps. It reads the receiver’s layout, determines the property’s offset for that layout, and records both in the site’s cache entry. It then jumps back into the patched site, which takes the fast path on the retry.

The middle step is where the property name is needed, and the name is not available at the stub unless it is passed. Two conventions exist. The stub can take the name from a side table indexed by site, which costs a load. Or the initial code sequence at the site can push the name before jumping, which costs a few instructions of code per site but no load. The first keeps sites small, the second keeps the stub simple, and engines choose based on how much code size the uninitialized state consumes in practice.

The jump back is the part that makes this a patching scheme rather than a table. The stub does not return to the caller; it returns to the site, which has been rewritten in the meantime, so the retry takes the fast path. That is a controlled form of self-modification: the code being executed changes between the jump out and the jump back.

Writing to executable memory

Code pages are writable during compilation and read-only during execution on most systems, which means a patch requires a transition between the two states. The standard mechanism is a call to the operating system to change the protection of the page, followed by the store, followed by a change back. On POSIX systems that is mprotect with PROT_WRITE and then PROT_READ|PROT_EXEC; on Windows it is VirtualProtect. Both are system calls and both have a cost measured in microseconds, not cycles.

A system call per patch would make the first execution of every access site absurdly expensive. Engines therefore patch in batches or keep a small pool of pages permanently writable, or use a per-thread writable alias of the code page through a second mapping. The last is the cheapest: the code is mapped twice, once executable and once writable, and the patch is a store through the writable alias. It requires that the two mappings stay coherent, which on architectures with virtually indexed caches means the alias must be congruent in the cache index bits, and on architectures with physically indexed caches means nothing special is required.

Instruction cache coherence is the other constraint. After writing new instructions, the core’s instruction cache may still hold the old ones, and the pipeline may have already fetched past the patch point. The architecture’s documented sequence for this is: write the data, execute a memory barrier, then invalidate the instruction cache for the affected range and flush the pipeline. On x86 the instruction cache is coherent with respect to writes by the same core, so a serializing instruction is sufficient; on ARM the explicit IC IVAU sequence is required. Getting this wrong produces a core that executes stale instructions, which is a failure that appears only under specific timing and is correspondingly hard to diagnose.

Making the patch atomic

A patch that overwrites several instructions cannot be performed with a single store, and a thread executing those instructions concurrently could observe a half-written sequence. The standard solution is to make the patch a single aligned store of at most one machine word.

That constraint shapes the instruction sequence at the site. The site must be laid out so that the transition from “call the stub” to “guard and load” is expressible as replacing one word. A common arrangement puts a single jump instruction at the site and stores the target in a separate word aligned for atomic access: the code is always a jump, and the patch changes only the jump’s target. Before the patch the target is the miss stub; after it, the target is a small trampoline containing the guard and the load.

This is the same structure a dynamic linker uses for a procedure linkage table entry, and for the same reason. The jump is unconditional and its encoding does not change, so overwriting the target word is atomic on any architecture that can store a pointer atomically, which is every architecture the runtime supports.

A variant patches the instruction in place when the replacement fits in one word, which is possible for a guard against a layout stored in a register plus a load at a small offset. The condition is that the original and the replacement have the same length, so no bytes outside the patched word change meaning.

What the fast path looks like after patching

The patched sequence has three parts: compare the receiver’s layout against the cached value, branch to the slow path on mismatch, and load from the constant offset. The cached value and the offset are constants in the instruction stream or in a nearby data word.

The comparison is against a value that the code must keep alive. If the cached value is a pointer to a descriptor and the descriptor can be collected, the pointer becomes dangling. Engines either hold the descriptor weakly and clear the cache when it dies, or hold it strongly and accept that a cached descriptor is not collected. The second is simpler and the retention is bounded by the number of descriptors that have been cached, which is bounded by the number of access sites. Why the comparison is against descriptor identity rather than structural equality is covered in Shape Identity, Interning, and Structural Equality.

The slow path on mismatch does not immediately patch. It calls the miss stub again, which now finds the site in a state that already has one cached layout and must decide whether to extend or replace. A second distinct layout may cause the site to be rebuilt as a polymorphic chain, which means the patch is no longer a single word; the site’s jump target is redirected to a new code block containing the chain, and the old block is abandoned. The site’s single-word patch point is preserved throughout: the jump target changes, the code at the site does not.

This is the reason the jump-through-a-word design dominates. A patch point that can only be redirected, never rewritten, can be updated for any change in the site’s state without re-deriving the atomicity argument. The cost is one indirect jump on every access, which the branch predictor handles well because the target is stable once the site settles.

Interaction with optimization tiers

An optimized function does not use the per-site patches in the same way. The optimizing compiler reads the feedback, which is the state of the site after warm-up, and compiles the fast path with the layout as a compile-time constant. There is no patch point inside the optimized code for the common case; the guard is inline and its failure goes to a deoptimization stub.

The interaction is that a site may be patched in the interpreter, then recompiled, then patched again if the optimized code deoptimizes. Each transition changes which code is executing at the site, and the caches must be coherent across the transition. Engines handle this by keeping the feedback attached to the site rather than to the code, so that recompilation reads the same record the interpreter was updating.

The worst case is a site that oscillates: it becomes polymorphic in the interpreter, gets compiled with two cases, deoptimizes when a third layout arrives, returns to the interpreter, and repeats. The runtime’s defence is the deoptimization counter described in Type Feedback and the Speculation Budget; after enough cycles it stops compiling the function and leaves it in the interpreter with a polymorphic or megamorphic cache.

The first access is the expensive one

The total cost of an access site over a program’s execution is the cost of the first execution plus the cost of every subsequent execution. The first is hundreds to thousands of times the steady-state cost: the lookup, the offset computation, the patch, possibly a protection change, and an instruction cache flush. The steady state is a compare, a predicted branch, and a load.

This asymmetry is the reason a program that executes each access site only a handful of times is not helped by inline caching at all, and may be slightly hurt by it. The runtime’s tiering decisions are built around the same asymmetry: interpret first, compile only functions that run enough times to amortize the compilation, and within compilation only speculate where the feedback is strong enough that the guard will not fail.

The asymmetry also explains why the number of distinct access sites in a program matters. A large program has many sites, each paying the first-access cost once, and the aggregate cost of warming up is proportional to the site count. That is why the code size of the uninitialized state is worth optimizing: a smaller miss stub means the uninitialized sites of a function occupy less of the instruction cache, and a warm-up phase that is spread over many small interpreted functions is dominated by instruction fetch rather than by the lookups themselves.

Failure modes at the patch point

Three failure modes are specific to this machinery.

A patch performed without the instruction cache maintenance sequence leaves a core executing the old instructions. The symptom is a cache that never fills, or one that fills with a stale value, and the failure is timing-dependent.

A patch that overwrites more than one word without atomicity lets a concurrent thread execute a torn instruction sequence. The symptom is an illegal instruction or a jump to an arbitrary address, and the failure depends on thread scheduling.

A site whose jump target is updated but whose old target block is freed lets a thread that read the old target before the update jump into freed memory. Engines handle this by deferring the free until no thread can be executing the old block, which is a quiescence protocol of the same kind a garbage collector uses.

None of these are language-level problems; they are the price of putting the cache in the instruction stream rather than in a table. The table-based alternative avoids all three and pays a load per access instead. Which is better depends on how much the extra load costs on the target architecture and how much a runtime values keeping its sites uniform, and interpreters tend to take the table route for exactly that reason while JIT-compiling runtimes take the patching route once code is native.