Pointer Provenance and the Cost of Integer Round-Trips

On a flat-address machine a pointer is an integer with a type attached, and the type is a fiction the compiler maintains for its own purposes. The fiction is not decorative. When a compiler decides that two stores cannot alias, or that a load can be hoisted above a call, it is relying on the fact that a pointer was derived from a particular object by a particular sequence of operations. That derivation history is the pointer’s provenance, and it exists only in the abstract machine. The hardware has no record of it.

The separation becomes visible the moment a pointer is converted to an integer and back. The bits survive. The derivation does not. Everything the compiler was entitled to assume about the pointer is now unsupported, and the code that depended on those assumptions is undefined behaviour even though every byte at the address is exactly where it was.

What a provenance model has to say

A provenance model answers one question: given a pointer value, which objects may it be used to access, and how does that set change under arithmetic and conversion? The answer is needed because the optimiser’s alias analysis is not sound on raw addresses alone. Two pointers with different addresses can still be required to alias after a store through a third pointer, and two pointers with the same address can be required not to alias if they were derived from different objects.

The model used by mainstream compilers is roughly this. A pointer is a pair of an address and a provenance set naming the allocations it may access. Pointer arithmetic within the bounds of the originating object preserves provenance; arithmetic that leaves the object’s one-past-the-end boundary produces a pointer with no valid access, though forming the one-past pointer itself is legal and comparing it is legal. Dereferencing anything outside the originating object is undefined, regardless of whether the address happens to fall inside a different live object. The rule is the pointer-level counterpart of the reference aliasing rules in Aliasing Rules for References and the Role of UnsafeCell.

The C standard does not phrase it this way, but its rules imply the same thing. Pointer subtraction is defined only when both pointers point into the same array object, and pointer comparison with a relational operator is defined only within the same object. The standard also permits an implementation to place objects adjacently such that one object’s last byte is followed by another’s first byte, and it permits the comparison of unrelated pointers to be unspecified. Those permissions only make sense if the compiler is tracking which object each pointer came from.

The formal treatments make the model explicit. The provenance semantics developed for C distinguishes concrete provenance, where a pointer is a plain address and any access to mapped memory is permitted, from abstract provenance, where access is restricted to the object the pointer was derived from. Which one a compiler implements determines whether programs that walk across object boundaries work. The abstract model matches what optimisers actually assume; the concrete model matches what programmers who write allocators expect.

The round-trip that discards the record

The problematic idiom is short and common:

void *base = malloc(n);
uintptr_t raw = (uintptr_t)base;      /* pointer to integer */
raw += offset;
void *p = (void *)raw;                /* integer back to pointer */
memset(p, 0, len);

The cast to uintptr_t is implementation-defined but legal, and on every mainstream platform it produces the address. The addition is ordinary integer arithmetic. The cast back is implementation-defined and produces a pointer with the same address. Nothing in that sequence is a diagnosable error, and the resulting pointer dereferences to the intended bytes on every real CPU.

What has been lost is the claim that p is derived from base. In an abstract-provenance model, p may be assigned an empty or unknown provenance, and a store through it may be treated as unable to affect the object that base names. An optimiser that has cached a field of base in a register across the memset is then entitled to keep the stale value. This is the mechanism behind the well-known pattern where a structure’s field appears not to update after being modified through a pointer that travelled through an integer.

The same hazard appears without malloc. Casting a function pointer to a data pointer, storing it, and calling it after a round-trip is undefined in C for a separate reason: the standard does not guarantee that function and object pointers have the same representation. POSIX requires it for dlsym, which is why the idiom works on POSIX systems and is still not portable.

Strict provenance as an API

Rust has moved from describing the problem to offering an interface that keeps provenance explicit. The std::ptr module exposes the address of a pointer as an integer and provides ways to construct a new pointer from an address while retaining an existing pointer’s provenance, and to replace a pointer’s address while keeping its provenance. The intent is that address arithmetic on integers is expressed as a change of address attached to a known provenance, rather than as a lossy round-trip.

let base = vec![0u8; 64];
let p = base.as_ptr();
let addr = p.addr();               // address as usize, provenance not involved
let q = p.with_addr(addr + 8);     // same provenance, different address

The API does not make the resulting pointer valid. If addr + 8 lies outside the allocation, q is still out of bounds and dereferencing it is still undefined. What it preserves is the compiler’s ability to reason: q is known to derive from the same allocation as p, so alias analysis can treat stores through either as possibly affecting the other.

The cost is that code which treats pointers as integers must be rewritten to say which provenance it means. Code that genuinely needs to forge a pointer from an arbitrary integer, such as a kernel building a user-space pointer from a system call argument, must use an explicit exposure operation and accept that the resulting pointer’s provenance is unknown. That is a real requirement rather than a formality: it tells the optimiser not to assume anything.

Where the address is genuinely the only thing available

Some interfaces only carry integers. A system call that takes a buffer address passes a machine word; the kernel has no way to receive a provenance tag from user space. A device writes a physical address into a descriptor ring, and the driver reconstructs a virtual address from it. A serialisation format stores offsets as integers.

In these cases the integer is the ground truth and the compiler’s model has to be told so. The usual technique is to keep the integer and the derived pointer in a form the optimiser cannot reason across: an asm block that the compiler treats as opaque, or a volatile store and load, or a call through a function pointer the compiler cannot analyse. Each of these is a way of saying “the provenance here is not derivable from the program text”.

The alternative is to accept that the compiler may assume the pointer was never forged. That assumption is what makes the fast path fast, and it is also what makes the code break when a compiler version changes its inlining heuristics. The breakage is not a regression in the compiler; the program was always undefined.

Reading the boundary

Two rules summarise the practical position. First, pointer arithmetic on a pointer that was never converted to an integer keeps provenance and is the form the compiler can reason about; do the arithmetic in pointer type whenever the language allows it. Second, when an integer must be converted to a pointer, do it once at the boundary where the integer originates, and keep the resulting pointer in pointer form afterwards.

The failure mode of the second rule is subtle. A pointer forged from an integer and then converted back to an integer and forged again is no worse than a single forgery, but a pointer forged from an integer and then passed to code that expects a pointer derived from a known allocation can break alias analysis in ways that are invisible locally. The store appears to execute; the load it was meant to affect does not observe it.

This is one instance of the general pattern covered in Undefined Behaviour as a Compiler Permission: the compiler’s transformations are justified by assumptions the source makes implicitly. Provenance is the assumption most often broken by code that looks correct, because the address is right and the bug is in a fact that has no representation at runtime.