Provenance: a pointer is not an integer

pub fn tagged_pointers(vals: Vec<u32>, tags: Vec<u64>) -> Vec<u64>

Build a tagged-pointer table. For each element of vals, take a raw pointer to it with &raw const, stash the low two bits of the matching tag inside the pointer’s address, and store the result. Then walk the table, recover the tag from the low bits, mask them off, dereference, and emit (value << 2) | tag.

If tags is shorter than vals, missing tags are 0. Only the low two bits of each tag are used.

Do the address arithmetic with the strict-provenance API: map_addr, addr, with_addr. Not as usize. The reason is the whole item.

A pointer is an address plus provenance

Here is the model. At the language level a pointer is two things:

1. an address — a number;
2. provenance — permission to access a particular set of bytes, for a particular span of the program, with a particular mutability.

Provenance is not stored anywhere. It does not exist at runtime. It is a property the compiler tracks, and it is what licenses an access. The consequence is the sentence that changes how you read unsafe code:

Two pointers with the same numeric address can have different provenance, and accessing memory a pointer has no provenance for is undefined behaviour even though the address is correct.

Provenance is inherited — a pointer derived from another carries the parent’s permission — and it can only ever shrink, never grow. Offsetting a pointer keeps you inside the parent’s allocation or takes you out of bounds; there is no operation that widens permission.

::: question Two allocations end up adjacent in memory. You take a pointer into a, offset it forward until its address equals a byte inside b, and read. The address is right. What is wrong? The pointer has provenance for a, not for b, so the read is undefined behaviour.

It will “work” — the address is mapped, the bytes are there, the load will return them. And it is exactly the pattern that breaks under optimisation: the compiler knows a pointer derived from a can only reach a, so it is free to keep b‘s contents in a register across your read, or to reorder your store to b past it.

This is the difference between Rust’s model and the C folklore that “a pointer is just an address”. C’s abstract machine has the same rule — it is why restrict and strict aliasing exist — but decades of practice taught people to reason about addresses. Rust made the rule explicit and gave it an API. :::

Why tagged pointers are the right example

A u32 is 4-aligned, so any pointer to one has its low two bits zero. Those bits are free storage: pack a 2-bit tag into them and you get a pointer and a discriminant in one word. Real allocators, garbage collectors, and Vec-of-enum optimisations all do this.

The naive way to write it is:

let tagged = (p as usize | tag) as *const u32;      // do not
let clean  = (tagged as usize & !MASK) as *const u32;
unsafe { *clean }                                    // UB under the model

The round trip through usize throws the provenance away. clean has the right address and, formally, no permission to access anything. The strict version says the same thing without the loss:

let tagged = p.map_addr(|a| a | tag);
let clean  = tagged.map_addr(|a| a & !MASK);
unsafe { *clean }                                    // fine

map_addr changes the address and carries the provenance along. That is the entire difference, and it is invisible at runtime — the two versions compile to identical machine code today.

Two stable API families

Strict provenance, all stable since 1.84:

• p.addr() -> usize — the address, explicitly discarding provenance;
• p.with_addr(a) -> *const T — p‘s provenance, a‘s address;
• p.map_addr(f) -> *const T — with_addr(f(p.addr()));
• p.is_aligned(), p.align_offset(n).

This family lets you do arbitrary address arithmetic while keeping the provenance chain explicit, which means Miri can check it and CHERI-style hardware can enforce it.

Exposed provenance, for the cases where you genuinely have only an integer — an FFI handle, an MMIO register, a bootloader-supplied address:

• p.expose_provenance() -> usize — announce this pointer’s provenance;
• with_exposed_provenance(a) -> *const T — reconstruct some previously exposed provenance for that address.

Use it when you must, and know that the std documentation is candid about its semantics not being rigorously specified. It is an escape hatch with a disclaimer attached.

::: question If map_addr and as usize produce identical machine code, why does the distinction matter at all? Because the model is what the optimiser is allowed to assume, and the optimiser gets smarter than your test suite.

Nothing today miscompiles the as usize version. That is a statement about LLVM’s current conservatism, not about your program’s meaning. When a pass lands that exploits “an integer-derived pointer has no provenance”, the code that changes behaviour will be the code that was already undefined — and it will change behaviour in a build you did not touch.

The second reason is tooling. Miri can prove your strict-provenance code respects the model, and it will flag the as usize version. Anything the model cannot see, no checker can check for you. Writing in the checkable subset is how you get a tool that helps. :::

The punchline, stated honestly

The same program written with as usize casts passes every test in this harness. It compiles, it is clippy-clean, it produces the right numbers, and it is undefined behaviour under the model rustc documents. That is precisely the point of this item, and precisely the limit of this grader.

The unstable rustc lints fuzzy_provenance_casts and lossy_provenance_casts exist to catch the casts, and being unstable they cannot run here, so strict-provenance discipline cannot be graded directly. Grade it yourself.

Two related on-by-default rustc lints worth knowing, because they are the same family of “pointers are not numbers” mistake: unpredictable_function_pointer_comparisons (two fn pointers to the same function need not compare equal — the linker may deduplicate or duplicate) and ambiguous_wide_pointer_comparisons (comparing *const dyn Trait compares the vtable too, which is almost never what you meant).

Remember the grade is compile + tests + clippy -D warnings.