Opensource internals

Provenance in Eight Bytes: How rustc Packs a Pointer's Identity

6 min read Jay Hubbert

rustc's const evaluator packs an allocation id plus two flags into one NonZero u64, and stores provenance sparsely - as whole-pointer relocations - instead of per byte.

TL;DR: A pointer in rustc’s const evaluator needs to say which allocation it points into, whether it is immutable, and whether it is a shared reference. rustc packs all three into one NonZero<u64> using the top two bits as flags — and stores the provenance of the bytes in memory sparsely, as whole-pointer relocations, so ordinary data carries almost no overhead.

The packed provenance

rust 
// compiler/rustc_middle/src/mir/interpret/pointer.rs:82-116

/// The type of provenance in the compile-time interpreter.
/// This is a packed representation of:
/// - an `AllocId` (non-zero)
/// - an `immutable: bool`
/// - a `shared_ref: bool`
///
/// with the extra invariant that if `immutable` is `true`, then so
/// is `shared_ref`.
#[derive(Copy, Clone, Eq, Hash, Ord, PartialEq, PartialOrd)]
pub struct CtfeProvenance(NonZero<u64>);

impl From<AllocId> for CtfeProvenance {
    fn from(value: AllocId) -> Self {
        let prov = CtfeProvenance(value.0);
        assert!(
            prov.alloc_id() == value,
            "`AllocId` with the highest bits set cannot be used in CTFE"
        );
        prov
    }
}
...
const IMMUTABLE_MASK: u64 = 1 << 63; // the highest bit
const SHARED_REF_MASK: u64 = 1 << 62;
const ALLOC_ID_MASK: u64 = u64::MAX & !IMMUTABLE_MASK & !SHARED_REF_MASK;

impl CtfeProvenance {
    /// Returns the `AllocId` of this provenance.
    #[inline(always)]
    pub fn alloc_id(self) -> AllocId {
        AllocId(NonZero::new(self.0.get() & ALLOC_ID_MASK).unwrap())
    }

Three facts in eight bytes:

  • the AllocId, which is already a NonZero<u64>;
  • immutable, in bit 63;
  • shared_ref, in bit 62.

And the invariant “immutable implies shared_ref” means the pair encodes only four states, not eight — the flags are not independent.

Because it is a NonZero, Option<CtfeProvenance> is niche-optimized to 8 bytes, and the pointer stays small:

rust 
// compiler/rustc_middle/src/mir/interpret/pointer.rs:224-234

#[derive(Copy, Clone, Eq, PartialEq, TyEncodable, TyDecodable, Hash)]
#[derive(StableHash)]
pub struct Pointer<Prov = CtfeProvenance> {
    pub(super) offset: Size, // kept private to avoid accidental misinterpretation (meaning depends on `Prov` type)
    pub provenance: Prov,
}

static_assert_size!(Pointer, 16);
// `Option<Prov>` pointers are also passed around quite a bit
// (but not stored in permanent machine state).
static_assert_size!(Pointer<Option<CtfeProvenance>>, 16);

Sixteen bytes for a pointer (offset + provenance), whether or not the provenance is optional. That matters because every load and store in the interpreter goes through a Pointer.

The naive design — struct Provenance { alloc: AllocId, immutable: bool, shared: bool } — would be 16 bytes with padding, and Option<Provenance> would be 24. That is a 50% increase in the size of every pointer the interpreter touches.

The sparse provenance map

The provenance of pointers stored in memory is a separate structure:

rust 
// compiler/rustc_middle/src/mir/interpret/allocation/provenance_map.rs:1-42

//! Store the provenance for each byte in the range, with a more efficient
//! representation for the common case where PTR_SIZE consecutive bytes have the same provenance.
...
/// Stores the provenance information of pointers stored in memory.
#[derive(Clone, PartialEq, Eq, Hash, Debug)]
#[derive(StableHash)]
pub struct ProvenanceMap<Prov = CtfeProvenance> {
    /// `Provenance` in this map applies from the given offset for an entire pointer-size worth of
    /// bytes. Two entries in this map are always at least a pointer size apart.
    ptrs: SortedMap<Size, Prov>,
    /// This stores byte-sized provenance fragments.
    bytes: Option<Box<SortedMap<Size, PointerFrag<Prov>>>>,
}

Two levels:

  • ptrs — the common case. A whole pointer stored at an aligned offset gets one entry, not one per byte. This is exactly the “relocation” model that LLVM’s constant materializer uses, so intern can hand the same list to the backend without translation.
  • bytes — the rare case of a partially overwritten pointer. It is Option<Box<...>>, so for essentially every allocation it is None: one null pointer.

The alternative — provenance per byte — would need 8 bytes of metadata per 8 bytes of data, doubling the memory of every allocation, plus a hash lookup per byte.

Merging the fragments back

rust 
// compiler/rustc_middle/src/mir/interpret/allocation/provenance_map.rs:151-182

/// Attempt to merge per-byte provenance back into ptr chunks, if the right fragments
/// sit next to each other. Return `false` if that is not possible due to partial pointers.
pub fn merge_bytes(&mut self, cx: &impl HasDataLayout) -> bool {
    let Some(bytes) = self.bytes.as_deref_mut() else {
        return true;
    };
    let ptr_size = cx.data_layout().pointer_size();
    while let Some((offset, first_frag)) = bytes.iter().next() {
        let offset = *offset;
        // Check if this fragment starts a pointer.
        let range = offset..offset + ptr_size;
        let frags = bytes.range(range.clone());
        if frags.len() != ptr_size.bytes_usize() {
            // We can't merge this one, no point in trying to merge the rest.
            return false;
        }
        for (idx, (_offset, frag)) in frags.iter().enumerate() {
            if !(frag.prov == first_frag.prov
                && frag.bytes == first_frag.bytes
                && frag.idx == idx as u8)
            {
                return false;
            }
        }
        // Looks like a pointer! Move it over to the ptr provenance map.
        self.ptrs.insert(offset, first_frag.prov);
        bytes.remove_range(range);
    }
    // We managed to convert everything into whole pointers.
    self.bytes = None;
    true
}

If the byte fragments happen to describe a real pointer (same provenance, contiguous, in order), they are folded back into a single ptrs entry and the byte map is dropped entirely. This is what allows a backend to receive a plain relocation list.

Hashing large allocations

One more place where “big data, small hash” shows up:

rust 
// compiler/rustc_middle/src/mir/interpret/allocation.rs:228-274

/// This is the maximum size we will hash at a time, when interning an `Allocation` and its
/// `InitMask`. Note, we hash that amount of bytes twice: at the start, and at the end of a buffer.
/// Used when these two structures are large: we only partially hash the larger fields in that
/// situation. See the comment at the top of their respective `Hash` impl for more details.
const MAX_BYTES_TO_HASH: usize = 64;

/// This is the maximum size (in bytes) for which a buffer will be fully hashed, when interning.
/// Otherwise, it will be partially hashed in 2 slices, requiring at least 2 `MAX_BYTES_TO_HASH`
/// bytes.
const MAX_HASHED_BUFFER_LEN: usize = 2 * MAX_BYTES_TO_HASH;
...
impl hash::Hash for Allocation {
    fn hash<H: hash::Hasher>(&self, state: &mut H) {
        ...
        let byte_count = bytes.len();
        if byte_count > MAX_HASHED_BUFFER_LEN {
            // Hash the buffer's length.
            byte_count.hash(state);

            // And its head and tail.
            bytes[..MAX_BYTES_TO_HASH].hash(state);
            bytes[byte_count - MAX_BYTES_TO_HASH..].hash(state);
        } else {
            bytes.hash(state);
        }

The comment above it explains the reasoning:

Const allocations are only hashed for interning. However, they can be large, making the hashing expensive especially since it uses FxHash: it’s better suited to short keys, not potentially big buffers like the actual bytes of allocation.

So for buffers over 128 bytes: hash the length, the first 64 bytes and the last 64 bytes. Collisions are caught by the interner’s equality check anyway, and the length+head+tail triple is highly discriminating in practice. O(size) hashing of every const allocation becomes O(1).

The same trick is applied to the init mask’s blocks.

Where it lives

  • compiler/rustc_middle/src/mir/interpret/pointer.rs — CtfeProvenance, the masks, Pointer.
  • compiler/rustc_middle/src/mir/interpret/allocation/provenance_map.rs — the sparse map and merge_bytes.
  • compiler/rustc_middle/src/mir/interpret/allocation.rs — partial hashing.

Takeaway

Two related lessons here. First: niche packing — AllocId is already a NonZero<u64>, and NonZero has a niche, so the two boolean flags cost nothing. Second: representation follows the common case — provenance is stored per pointer, not per byte, and the per-byte fallback is behind an Option<Box<...>> that is None almost always. Both tricks are about the same thing: the rare case should not cost the common case anything.

RustInternalsCompilerConst evalMemoryPerformance