The Init Mask Is a Single Boolean Until It Isn't: How rustc Tracks Uninitialised Memory
rustc's const evaluator tracks which bytes of an allocation are initialised, but keeps that as one bool until a partial write forces it to materialise a bitmap - and it can go back to a bool.
TL;DR: Rust has to know which bytes of a
constare initialised, because reading an uninitialised byte is UB. The naive representation is a bitmap — one bit per byte, so a 1 MiB allocation costs 128 KiB. rustc instead starts with a single boolean and only materialises the bitmap when a partial write happens. A full overwrite materialises it back to a boolean.
The representation
// compiler/rustc_middle/src/mir/interpret/allocation/init_mask.rs:14-42
type Block = u64;
/// A bitmask where each bit refers to the byte with the same index. If the bit is `true`, the byte
/// is initialized. If it is `false` the byte is uninitialized.
/// The actual bits are only materialized when needed, and we try to keep this data lazy as long as
/// possible. Currently, if all the blocks have the same value, then the mask represents either a
/// fully initialized or fully uninitialized const allocation, so we can only store that single
/// value.
#[derive(Clone, Debug, Eq, PartialEq, Encodable_NoContext, Decodable_NoContext, Hash, StableHash)]
pub struct InitMask {
blocks: InitMaskBlocks,
len: Size,
}
#[derive(Clone, Debug, Eq, PartialEq, Encodable_NoContext, Decodable_NoContext, Hash, StableHash)]
enum InitMaskBlocks {
Lazy {
/// Whether the lazy init mask is fully initialized or uninitialized.
state: bool,
},
Materialized(InitMaskMaterialized),
}The doc comment says it plainly: “The actual bits are only materialized when needed.”
A freshly allocated buffer is InitMask::new(size, false) — one byte of
state, zero bits of bitmap.
Reading it
// compiler/rustc_middle/src/mir/interpret/allocation/init_mask.rs:48-65
#[inline]
pub fn is_range_initialized(&self, range: AllocRange) -> Result<(), AllocRange> {
let end = range.end();
if end > self.len {
return Err(AllocRange::from(self.len..end));
}
match self.blocks {
InitMaskBlocks::Lazy { state } => {
// Lazily allocated blocks represent the full mask, and cover the requested range by
// definition.
if state { Ok(()) } else { Err(range) }
}
InitMaskBlocks::Materialized(ref blocks) => {
blocks.is_range_initialized(range.start, end)
}
}
}The lazy case is O(1) and touches no memory beyond the single bool.
Writing it, and the two-way transition
// compiler/rustc_middle/src/mir/interpret/allocation/init_mask.rs:69-100
/// Sets a specified range to a value. If the range is out-of-bounds, the mask will grow to
/// accommodate it entirely.
pub fn set_range(&mut self, range: AllocRange, new_state: bool) {
let start = range.start;
let end = range.end();
let is_full_overwrite = start == Size::ZERO && end >= self.len;
// Optimize the cases of a full init/uninit state, while handling growth if needed.
match self.blocks {
InitMaskBlocks::Lazy { ref mut state } if is_full_overwrite => {
// This is fully overwriting the mask, and we'll still have a single initialization
// state: the blocks can stay lazy.
*state = new_state;
self.len = end;
}
InitMaskBlocks::Materialized(_) if is_full_overwrite => {
// This is also fully overwriting materialized blocks with a single initialization
// state: we'll have no need for these blocks anymore and can make them lazy.
self.blocks = InitMaskBlocks::Lazy { state: new_state };
self.len = end;
}
InitMaskBlocks::Lazy { state } if state == new_state => {
// Here we're partially overwriting the mask but the initialization state doesn't
// change: the blocks can stay lazy.
if end > self.len {
self.len = end;
}
}
_ => {
// Otherwise, we have a partial overwrite that can result in a mix of initialization
// states, so we'll need materialized blocks.
let len = self.len;
let blocks = self.materialize_blocks();Four cases, and note the second one: a full overwrite of an already
materialised mask de-materialises it. So the representation is not a
one-way ratchet; a memset-style write over a previously partially-written
region returns to the one-byte representation.
The third case is subtle and good: a partial write whose value equals the current uniform state also keeps the mask lazy. Writing zeros into a fully-uninitialised buffer does not make it “partially initialised” — it stays fully uninitialised.
The bit-level search
When the mask is materialised, finding the first bit with a given value uses word-at-a-time tricks:
// compiler/rustc_middle/src/mir/interpret/allocation/init_mask.rs:365-548
/// Search one block, returning the index of the first bit equal to `is_init`.
fn search_block(
bits: Block,
block: usize,
start_bit: usize,
is_init: bool,
) -> Option<Size> {
// Invert bits so we're always looking for the first set bit.
// ! 0b00111011
// bits = 0b11000100
let bits = if is_init { bits } else { !bits };
// Mask off unused start bits.
// 0b11000100
// & 0b11111000
// bits = 0b11000000
let bits = bits & (!0 << start_bit);
// Find set bit, if any.
// bit = trailing_zeros(0b11000000)
// bit = 6
if bits == 0 {
None
} else {
let bit = bits.trailing_zeros();
Some(InitMaskMaterialized::size_from_bit_index(block, bit))
}
}trailing_zeros on a u64 is a single TZCNT instruction, and whole
blocks that are uniformly 0 or 1 are skipped entirely.
And the loop is written for codegen:
// compiler/rustc_middle/src/mir/interpret/allocation/init_mask.rs:493-503
if start_block < end_block_inclusive {
// This loop is written in a specific way for performance.
// Notably: `..end_block_inclusive + 1` is used for an inclusive range instead of `..=end_block_inclusive`,
// and `.zip(start_block + 1..)` is used to track the index instead of `.enumerate().skip().take()`,
// because both alternatives result in significantly worse codegen.
The proof that it is correct
The fast implementation is checked against a naive reference in debug builds:
// compiler/rustc_middle/src/mir/interpret/allocation/init_mask.rs:530-547
fn find_bit_slow(
init_mask: &InitMaskMaterialized,
start: Size,
end: Size,
is_init: bool,
) -> Option<Size> {
(start..end).find(|&i| init_mask.get(i) == is_init)
}
let result = find_bit_fast(self, start, end, is_init);
debug_assert_eq!(
result,
find_bit_slow(self, start, end, is_init),
"optimized implementation of find_bit is wrong for start={start:?} end={end:?} is_init={is_init} init_mask={self:#?}"
);Keeping the naive version in the tree as an executable specification is a lovely practice: it costs nothing in release builds and catches any divergence immediately.
The run-length encoding for repeated copies
// compiler/rustc_middle/src/mir/interpret/allocation/init_mask.rs:646-724
/// Run-length encoding of the uninit mask.
/// Used to copy parts of a mask multiple times to another allocation.
pub struct InitCopy {
/// Whether the first range is initialized.
initial: bool,
/// The lengths of ranges that are run-length encoded.
/// The initialization state of the ranges alternate starting with `initial`.
ranges: smallvec::SmallVec<[u64; 1]>,
}The comment explains the motivation:
Since we are copying
sizebytes fromsrctodest + i * size(for i in 0..repeat), a naive initialization mask copying algorithm would repeatedly have to read the initialization mask from the source and write it to the destination. Even if we optimized the memory accesses, we’d be doing all of thisrepeattimes. Therefore we precompute a compressed version of the initialization mask of the source value and then write it backrepeattimes without computing any more information from the source.
So [x; 1000] does O(1) work per repeat instead of O(repeat × size). And
the uniform case short-circuits entirely:
// compiler/rustc_middle/src/mir/interpret/allocation/init_mask.rs:699
pub fn apply_copy(&mut self, defined: InitCopy, range: AllocRange, repeat: u64) {
// An optimization where we can just overwrite an entire range of initialization bits if
// they are going to be uniformly `1` or `0`. ...
if defined.ranges.len() <= 1 {
let start = range.start;
let end = range.start + range.size * repeat; // `Size` operations
self.set_range(AllocRange::from(start..end), defined.initial);
return;
}Where it lives
compiler/rustc_middle/src/mir/interpret/allocation/init_mask.rs— the whole file:InitMask,InitMaskBlocks,find_bit,InitCopy.compiler/rustc_middle/src/mir/interpret/allocation/provenance_map.rs— the sibling trick for provenance (a lazily allocated byte map).
Takeaway
This is the “one bit can carry a lot of information” pattern: most allocations are either fully initialised or fully uninitialised, and the representation should reflect the common case, not the worst case. The transition is bidirectional, so the mask degrades and recovers gracefully instead of monotonically growing.