Precise Exceptions from an Imprecise Machine

An out-of-order core executes instructions in an order that has nothing to do with the program. An operating system, a debugger, and the language runtime all assume the opposite: that when a page fault or a divide-by-zero is delivered, the saved program counter names the instruction responsible, every instruction before it has completed, and no instruction after it has had any effect. These two assumptions are contradictory unless the machine is designed to hide its own disorder.

The contract an operating system depends on

Take a demand-paging fault on a load. The kernel’s handler needs three things to be true:

1. The faulting address is available in a register or a control structure.
2. All instructions preceding the load have committed, including their stores.
3. No instruction after the load has committed, so that restarting at the load re-executes exactly the missing work and nothing twice.

If any of these fails, the kernel must reconstruct state it cannot see. Instruction 3 is the hard one: if a later store had already drained to memory, restarting would duplicate it, and the page-fault mechanism would be unsound for any code that writes. This is why the reorder buffer’s retirement rule exists and why “precise” means precisely this ordering property, not “accurate” in any vague sense.

The contract is the same for a supervisor call, an illegal instruction, a misaligned access, a debug breakpoint, and a floating-point invalid operation. It differs only in which piece of saved state the handler inspects.

Fault, trap, and the restart point

The architecture distinguishes classes by the program counter they save:

• Faults are reported before the instruction’s effect. The saved PC is the faulting instruction, which will be re-executed. A page fault on a load is a fault.
• Traps are reported after the instruction completes. The saved PC is the next instruction. A system call, a breakpoint, and a floating-point exception that is taken after the result is written are traps.
• Aborts are reported for a condition where restarting is not possible and the PC may be unreliable, typically a hardware error in the memory subsystem.

For the hardware the distinction collapses into a question asked at retirement: does this entry report before or after its effect becomes visible? A fault entry stops retirement at its own slot; a trap entry completes its effect and then stops retirement at the following slot. Because retirement is a scan of the head of the queue, both are implementable with a condition bit.

Detecting exceptions early without reporting them early

The machine’s problem is that exceptions are discovered early — a load’s page-table walk fails at execute time, possibly hundreds of instructions before any of those instructions can retire. The resolution is to separate detection from reporting.

Each reorder buffer entry carries a flag once an exception has been detected for it. Detection suppresses dependent side effects: a load that faults does not write its destination, and an instruction whose input is a faulting instruction’s output does not execute (or executes and is discarded). The flag itself is enough to prevent propagation. Reporting waits for the head.

This creates two secondary mechanisms:

Precise-state tracking for operands. Because a faulting instruction does not write a register, its consumers must know their source is invalid. Designs either mark the consumer’s entry as poisoned or simply prevent the dependent from completing. The latter is safer but costs a comparison; the former requires the bit to travel with the operand.

Memory ordering with stores. A store whose address translation fails must not enter the store queue as a pending write, and a younger store must not commit if an older instruction faults. Because stores leave the queue in retirement order, and retirement stops at the oldest fault, the invariant is preserved automatically.

Where the visibility boundary is blurry

Two hardware behaviours make the naive contract insufficient, and both are handled by architecture rather than by microarchitecture.

Architecturally invisible work. A faulting load may have caused a cache line to be brought in, a TLB entry to be created, or a prefetch to be issued. None of this is visible to software, so the restart is unaffected. The exception is a speculative read of memory-mapped I/O, which is visible and therefore must not be speculated — which is why such regions are mapped as non-speculatable or uncacheable, and why the behavior of speculative accesses to device memory is either undefined or architecturally forbidden depending on the platform.

Changes to memory by another agent. A speculative load may read a value that another core then modifies. On restart after a fault, the load may see a different value. This is normal and permitted: a precise exception does not promise a time-travel-correct memory image, only that the restart observes the program’s own ordering. Code that assumes otherwise — a sequence that reads a device register, faults, and restarts — is broken for reasons the machine cannot fix.

The design consequence is that the exception mechanism is not a transactional memory. It guarantees single-instruction restart, nothing more.

Interrupts, which arrive out of nowhere

A synchronous fault belongs to an instruction and can wait in the reorder buffer for its turn. An external interrupt belongs to no instruction and has no natural position in the stream. Architectures specify that an interrupt is taken at an instruction boundary, which means the hardware must pick a point in the program’s execution that is somewhere between two instructions, and report that point.

Because retirement is the only serializing point, interrupts are sampled and then delivered when the retiring instruction’s boundary is reached. Typical behaviour: the interrupt request is latched, the pipeline commits instructions until the next retirement boundary, and then the request is taken with the saved PC of the next instruction. Instructions already in the pipeline are squashed. Some architectures allow an implementation to take the interrupt only at a specified instruction (for example, after a branching instruction) to simplify delivery, at the cost of latency.

The interesting case is the interaction with long-latency operations that have not retired. The interrupt is taken on time and the operations complete later in the abandoned path. Their results are discarded. This is why interrupt latency is a function of the longest thing at the head of the reorder buffer, not of the pipeline depth alone: an instruction waiting for a DRAM access at the head of a full buffer delays delivery of the interrupt by the miss latency.

There is a documented class of exception here: some architectures permit a fault to be reported during the handling of an interrupt, or permit an instruction-in-progress to be re-executed. The rules differ per architecture and are stated in the respective privileged-architecture manuals; a portable kernel must treat an imprecise fault as possible unless the architecture forbids it.

Precise interrupts and the cost of fences

Because the interrupt mechanism requires a retirement boundary, any instruction that must be ordered against everything previous — a cache flush, a TLB invalidation that affects speculative fetches, a write to a control register that changes translation — must wait for the reorder buffer to drain. In some architectures these operations are themselves defined to serialize the pipeline, and their cost is the window depth. On a machine with a window of several hundred instructions and a memory-subsystem latency of hundreds of cycles, a serialize can cost far more than the operation itself.

The mitigation is to make the operation less demanding: invalidation instructions that only order against later memory operations of a specified kind, fences with scope qualifiers, and instructions that retire in order but do not require a full drain. Each is a relaxation of the precise-exception rule into a narrower rule, and each must be matched by a removal of the corresponding assumption in software.

A model of retirement and fault delivery

The following model in C shows why the flag-at-detection, stop-at-retirement structure is necessary, by comparing it against a machine that reports the exception immediately.

#include <stdio.h>

struct entry { int seq; int done; int fault; };

/* retire up to `width` entries; returns the seq of the instruction that
   stopped retirement (faulting or incomplete), or -1 for none. */
static int retire(struct entry *rob, int n, int width, int *retired)
{
    int i = 0;
    *retired = 0;
    while (i < n && *retired < width) {
        if (rob[i].fault) {
            return rob[i].seq;          /* report here; do not retire it */
        }
        if (!rob[i].done) {
            return -1;                  /* head-of-line block, not an exception */
        }
        (*retired)++;
        i++;
    }
    return -1;
}

int main(void)
{
    /* a faulting load at seq 3, a store at seq 5 that must not commit */
    struct entry rob[] = {
        { .seq = 2, .done = 1, .fault = 0 },
        { .seq = 3, .done = 1, .fault = 1 },
        { .seq = 4, .done = 1, .fault = 0 },
        { .seq = 5, .done = 1, .fault = 0 },
    };
    int retired = 0;
    int stop = retire(rob, 4, 4, &retired);
    printf("retired %d, stopped at seq %d\n", retired, stop);
    return 0;
}

The output pattern is the whole argument: one instruction commits, the next reports, and the two behind it — both complete, one of them a store — do not commit. Any design that reports the fault at detection instead would have already committed the store, and the restart would duplicate it.

The visible consequences for software

Three practical facts follow from this design.

Handler complexity is bounded by definition. A fault handler sees a state that is exactly the architectural state at an instruction boundary. It never sees partial writes, never needs an undo log, and can always restart the faulting instruction. An operating system’s page-fault path therefore does not need to know anything about the microarchitecture. The one hardware detail that leaks through is the faulting address itself, and it is the address the instruction would have used in program order — the machine reports an architectural address, not an intermediate one.

Instruction-restartable operations must be restartable. Any instruction that can fault must be restartable without side effects. An instruction that performs two memory accesses and faults on the second must either be restartable from the beginning or be architecturally required to complete both. Architectures that allow a vector or string operation to fault partway through specify a restart address and a partially-updated count so the handler can resume; the hardware guarantees the partial effects are exactly those the specification allows. This is the one place where the precise-exception model is deliberately relaxed, and it is relaxed in a documented, measurable way. The relaxation is visible in the architecture as an element-count or index operand that the handler must inspect, which is why the affected instructions carry one.

Debugging single-step depends on it. A single-step trap is delivered at instruction boundaries, which means a debugger sees exactly one instruction retired per trap. On an out-of-order machine, this requires that the retirement of that one instruction also drain the pipeline far enough that no following instruction commits — which is why single-stepping is slow, and why hardware debugging features often provide a separate mechanism rather than relying on repeated traps. The trap itself is taken through the same retirement path, so the mechanism is the checkpoint-free version of the control transfer described in Checkpointing and Recovery from Misprediction: no speculative state is restored, because the machine simply stops renaming and lets the window drain.

The retirement machinery that makes all of this possible is the same structure that reclaims physical registers and releases stores, which is why the ordering guarantees in The Reorder Buffer and In-Order Retirement cannot be relaxed without breaking the exception model. Each property — precision, store visibility, register reclamation — is a consequence of the same in-order commit point.