Code Cache Management and Invalidation

Generated code is not like source code. It occupies memory that must be executable, it holds absolute addresses that are only valid while the process’s layout is stable, and it carries metadata that other parts of the runtime read while the program runs. A runtime that generates code continuously needs a place to put it, a way to reclaim space when code is no longer valid, and a way to guarantee that no thread is executing code while it is being removed. Those three requirements conflict, and the resolution shapes the runtime’s memory behaviour.

Layout of a Code Cache

The cache is usually one or a few large regions allocated with execute permission, subdivided by the code generator into blocks. Each compiled method gets a block sized to its code plus alignment, and the block is recorded in a side table that maps an address range back to the method and bytecode offset a return address belongs to.

The side table is as important as the code. It holds the method’s deoptimization metadata, its relocation information, its references to constants and class objects, and its safepoint table. When a thread stops at an arbitrary instruction, whether for a garbage collection, a stack walk, or a debugger, the runtime must determine, from the return address alone, which compiled method it is in and where the live references are. A cache without this table is a cache of uninterpretable bytes.

Alignment matters for two reasons. Instruction fetch happens in aligned blocks, so an entry point aligned to a block boundary cannot have its first fetch span two of them. More importantly, some architectures require call targets to be aligned, and a code generator that emits a direct call to an unaligned entry must use an indirect form.

Most runtimes give the cache a fixed maximum size, chosen at startup, because growing it later means the new region may be out of range of the direct branch displacements already emitted. A call instruction on x86-64 encodes a 32-bit displacement, so code more than about two gigabytes away from its target cannot be reached directly; the generator then emits a longer sequence through a register. Runtimes that allow the cache to grow must therefore either reserve a large virtual range up front or accept longer call sequences after growth.

Why Code Cannot Simply Be Freed

A compiled method that has become invalid cannot be deleted while any thread might be executing it or might return into it. The naive approach of stopping all threads, checking whether any frame is inside the block, and freeing it is correct but expensive if done per method, and it has a subtlety: a thread’s return address may point into a method that is not on any stack yet, because a call is in flight and the callee’s frame has not been pushed.

Runtimes therefore separate invalidation from reclamation. Invalidation marks the code as unusable and redirects new entries to an interpreter or to replacement code. Reclamation happens later, in bulk, at a safepoint where every thread’s stack is known and no thread is in the middle of a call sequence that could return into the block.

The two-phase design has a consequence that shows up as memory growth: invalidated code occupies space until the next reclamation cycle, and a program that compiles and invalidates rapidly can accumulate a large amount of dead code. Runtimes bound this by triggering reclamation when the invalid fraction of the cache crosses a threshold, rather than waiting for the cache to fill completely.

Dependency Tracking

Invalidation is driven by assumptions. Compiled code assumes that a class has no subclasses that override a method, that a field’s offset is what it was at compile time, that a call site’s receiver type is stable, that an interface has a particular set of implementors. Each assumption is recorded as a dependency, and each dependency is attached to the entity whose change would break it.

The natural structure is a dependency from the assumption to the compiled method, held in a table keyed by the assumed entity. When a class is loaded and it subclasses a class that some compiled code assumed had no subclasses, the runtime looks up that class in the table and finds every method that must be invalidated. The lookup is the reason dependencies are attached to the class rather than to the method: invalidation events are class-shaped, and the runtime needs to find the affected code quickly when a class loads.

Dependencies come in several forms, and each requires a different invalidation trigger.

A subtype dependency says “no subclass of C overrides method m”. It is broken when a class is loaded that subclasses C and overrides m. Loading is the only event that can break it in a closed-world sense, but a runtime that permits redefinition must also handle a class changing its superclass.

A leaf-type dependency says “this call site’s receiver is exactly class C, and C has no subclasses”. It is broken when any subclass of C is loaded, even one that overrides nothing, because the compiled code used the absence of subclasses to drop a check or to treat a C operation as non-polymorphic; the exact-class test on its own would still be sound, but the conclusions drawn from it would not be.

A field-offset dependency says “field f of class C is at offset N”. It is broken when a class is redefined with a different layout, which most runtimes disallow, or when the layout is changed by a class hierarchy change that reorders inherited fields.

A constant dependency says “this static final field has this value”. It is broken when the field is modified, which requires the runtime to either forbid such modification or instrument the write to invalidate dependents.

// Dependency table: assumed entity -> the compiled methods that rely on it.
struct Dependency {
    void *assumed_entity;                 // class, field, or method
    std::vector<CompiledMethod *> dependents;
};

void on_class_loaded(Class *k) {
    for (Class *c = k->super(); c != nullptr; c = c->super()) {
        auto it = deps.find(c);
        if (it == deps.end()) continue;
        for (CompiledMethod *m : it->second.dependents) {
            if (breaks(m->assumption(), k)) invalidate(m);   // mark, do not free
        }
    }
}

Walking the superclass chain is what makes subtype dependencies work with a single table: a new class can only break an assumption about one of its ancestors, so the runtime checks each ancestor rather than searching all classes.

Invalidation and Threads

Marking a method invalid is not enough; threads must stop entering it. Two mechanisms handle this.

The first is patching the entry. Every compiled method has an entry point that can be redirected, and invalidation overwrites it with a jump to a stub that performs the fallback. Threads that call the method after invalidation enter the stub. Threads already inside the method continue executing, which is acceptable only if the code they are executing is still correct for them, and it is not, because the assumption they relied on has been broken. So the second mechanism is required.

The second is forced deoptimization. At the next safepoint, every thread whose stack contains the invalidated method is deoptimized, reconstructing interpreted frames from the compiled state. The reconstruction uses the metadata described under deoptimization frame state reconstruction, and it must handle a thread stopped anywhere inside the method, including inside an inlined callee, which is why invalidation is one of the strongest arguments for keeping accurate frame maps at every safepoint.

Between the patching and the deoptimization, a window exists in which a thread is executing invalid code. The window is bounded by the time to the next safepoint, which in a loop with a safepoint poll at each back edge is short, and in a long-running tight loop without polls could be long. Compilers insert safepoint polls at back edges precisely to bound this window, at a cost of one predictable branch per iteration.

When the Cache Fills

A full cache is a policy problem, not a memory problem. Three responses are available.

Refuse new compilations. The runtime stops compiling and leaves remaining hot methods at their current tier. This preserves existing code and degrades performance for code that would have been compiled. It is the safest response and the one that produces the least surprising behaviour.

Evict. The runtime frees invalid code, or code for methods that are cold, and reuses the space. Eviction requires a reclamation safepoint and a policy for choosing victims. Choosing by recency of execution is natural; choosing by method size is also common, because freeing one large method recovers as much space as freeing many small ones.

Grow. Allocate a new region and continue. This requires that calls between regions remain encodable, which, as above, means reserving address space in advance or accepting longer call sequences.

The choice interacts with the compilation budget described in compilation budgets and recompilation policy: a cache that refuses compilation effectively imposes a budget of zero on new code, and a runtime that does this without reporting it looks like a runtime that has stopped optimizing for no reason.

Metadata Lifetime

The last subtlety is that metadata must outlive code. A compiled method can be invalidated and its code reclaimed, but a stack frame that deoptimizes from it needs the metadata. The runtime therefore keeps metadata alive as long as any frame could reference it, which means metadata lifetime is tied to stack contents rather than to code presence.

The practical consequence is that metadata is reclaimed at safepoints, alongside code, by scanning all stacks for references into the invalidated method’s metadata range. A runtime that frees metadata eagerly, when the code is invalidated, leaves the deoptimization that the invalidation triggered reading freed memory, which is why runtimes that implement invalidation state the lifetime rule explicitly.