Skip to content

← Unsafe and Soundness step 12 of 24

Medium Primitives

Validity invariants vs safety invariants 

struct Rec { kind: u8, flag: bool, ch: char }

pub fn parse_records(bytes: Vec<u8>) -> Vec<i64>

parse_records decodes a byte stream into records. Each record is six consecutive bytes:

bytes meaning accepted when
0 kind, a u8 always (any value 0 to 255)
1 flag, to become a bool the byte is exactly 0 or 1
2 to 5 a little-endian u32, to become a char the number is a Unicode scalar value (defined below)

Process the complete records in input order and append three numbers to the output for each one:

  • accepted record: [kind, flag, scalar], where flag is 0 or 1 and scalar is the decoded u32;
  • rejected record (a bad flag, a bad scalar, or both): [-1, -1, -1].

The output therefore always has exactly three numbers per complete record. If the input length is not a multiple of six, the last one to five bytes are an incomplete record and produce no output. Empty input produces an empty output.

Example: the bytes [2, 1, 0x00, 0xF6, 0x01, 0x00] decode to kind 2, flag 1 and scalar 0x1F600 (128512, the 😀 emoji), so the output is [2, 1, 128512]. Changing the second byte to 2 gives [-1, -1, -1].

The rule of the exercise is validate before constructing: check the raw bytes first, and create a bool, a char or a Rec only from values that passed. The rest of this page explains why checking a Rec after building it from unchecked bytes is too late.

Two kinds of invariant

An invariant is a property that every value of a type is expected to have. Unsafe Rust distinguishes two kinds.

A type's validity invariant is set by the language, and the compiler relies on it everywhere. Producing a value that breaks it is undefined behavior (UB) immediately. In the Rust Reference's terms, a value is produced whenever it is assigned to or read from a place (a variable, field or memory location), passed to a function or operation, or returned from one. Nothing has to inspect the value afterwards for the program to have UB.

A type's safety invariant is set by the code that defines the type, and its safe API relies on it. Examples: a Vec's first len elements are initialized and len <= capacity; a str holds UTF-8. Breaking a safety invariant is not in itself UB. The danger is what happens next: safe code that relies on the invariant, such as indexing a Vec or iterating over a str, can then cause UB. Code that lets a broken safety invariant reach such safe code is unsound.

This leads to a practical rule. Unsafe code inside the module that owns a type may break that type's safety invariant for a while, provided it is restored before any code that relies on it can observe the value. A common pattern is to write elements into a Vec's spare capacity and then call Vec::set_len. The validity invariant has no such grace period: an invalid bool exists the moment it is produced, however briefly it would have lived.

Check your understanding Vec::<u8>::with_capacity(8) followed by set_len(8) before Show answer

writing anything. Which invariant does that break? It breaks Vec's safety invariant, and it breaks the documented precondition of set_len, which requires the elements from the old length to the new length to be initialized.

It does not by itself produce an invalid value. The Vec struct holds a pointer, a length and a capacity, and all three are ordinary initialized values. But every safe operation now trusts a length that is false. v[0] reads an uninitialized u8, and an integer read from uninitialized memory is an invalid value, so that read is UB. Because set_len is an unsafe fn, the code that called it without meeting its precondition is the code at fault.

For Vec<bool> the problem has the same shape, with one addition: even initialized bytes would be invalid bool values unless each is 0 or 1.

Clippy's uninit_vec lint is in its correctness group, which is deny-by-default, and it reports this exact pattern:

error: calling `set_len()` immediately after reserving a buffer creates uninitialized values

Common validity requirements

The Rust Reference lists these requirements. Its list is explicitly not exhaustive, and some entries are still under discussion, as noted below.

type requirement for a valid value
bool the byte is 0 (false) or 1 (true)
char at most char::MAX (0x10FFFF) and not a surrogate (0xD800 to 0xDFFF)
! no valid value exists
integers, floats, raw pointers any bit pattern, as long as it is initialized
fn pointers non-null
structs, tuples, arrays every field or element is valid
enums a valid discriminant, and valid fields for the variant it names
&T, &mut T, Box<T> aligned, non-null, not dangling; pointing at a valid T (this last part is still debated)
wide pointers (&[T], &dyn Trait, raw wide pointers) the metadata matches the pointee: a correct vtable, or a slice length that keeps the total size at most isize::MAX for references and Box
NonNull<T>, NonZero<T> a restricted range: never null, never zero

Two definitions from the Reference help when reading the table.

Dangling means that not all of the bytes the pointer points to are part of the same live allocation. A pointer to zero bytes (for example to a zero-sized type) is never dangling, although a reference must still be non-null and aligned.

A place based on a misaligned pointer (a place reached through *ptr where ptr is not aligned for its type) causes UB only when it is loaded from or stored to. That is why &raw const on such a place is allowed while & is not: & produces a reference, and a reference must be aligned. The raw reference operator problem works through this.

Why char needs a check

A char is four bytes and holds a Unicode scalar value: a number from 0 to 0x10FFFF that is not in the surrogate range 0xD800 to 0xDFFF. Surrogates are not characters. In UTF-16, a character above 0xFFFF is written as a pair of surrogate code units, so those numbers are reserved for that encoding and are not assigned to characters.

So a u32 can fail to be a scalar value in two ways: it is above 0x10FFFF, or it is a surrogate. char::from_u32(n) returns Option<char> and rejects both. std::mem::transmute::<u32, char>(n) checks neither, and for a value in either range it produces an invalid char, which is UB. The char exists as soon as the transmute returns, so a check afterwards comes too late.

Check your understanding Why does char exclude surrogates instead of treating them as Show answer

unusual characters? Because they are not characters in Unicode, and UTF-8, the encoding str uses, has no valid encoding for them. If a char could hold 0xD800, then String::push(c) would have to write bytes that are not valid UTF-8, breaking String's safety invariant. Since every char is a scalar value, encoding one into a String never needs a check.

Validity invariants also let the compiler represent and optimize types more tightly. Because bool has only two valid values, current rustc stores Option<bool> in one byte, using an otherwise invalid byte value to mean None. In the same way Option<char> is four bytes, and Option<NonNull<T>> is guaranteed to be the size of a pointer. Code that produces an invalid value breaks assumptions like these, so the result may be far worse than one wrong number.

Related facts

std::mem::zeroed::<T>() returns a value whose bytes are all zero. That is a valid u32, a valid bool (false) and a valid struct made only of such fields. It is UB for &T, fn pointers, NonNull<T> and NonZero<T>, because all-zero is not a valid value of those types. rustc's warn-by-default invalid_value lint flags these cases when it can see the type, and it also flags the deprecated std::mem::uninitialized::<T>() for both bool and u32, because an uninitialized integer is invalid too.

The UTF-8 property of str is a safety invariant, not a validity one: the Reference treats str like [u8], which only needs initialized bytes. std::str::from_utf8_unchecked requires valid UTF-8 as its safety precondition, so passing other bytes is still a bug that safe string operations can turn into UB. rustc's deny-by-default invalid_from_utf8_unchecked lint rejects the call when the bytes are a visible constant.

Padding bytes, the gaps between a type's fields, do not need to be initialized. Together with unions, padding is the only place where reading uninitialized memory is allowed. The union and transmute problem builds on this.

What the tests cannot check

Undefined behavior does not reliably show up as a wrong answer. A version that builds the Rec from unchecked bytes and checks it afterwards could print the expected numbers for every test on one compiler version and fail on another, so passing tests cannot show that code is free of UB. (Tools such as Miri can detect many cases at run time, but they are not part of this grader.)

The starter shows the problem. It builds Rec with two transmutes and then checks only the upper bound of the scalar. On the current toolchain it fails some tests, and it also fails linting: rustc's unnecessary_transmutes lint flags the u32 to char transmute and Clippy's transmute_int_to_bool flags the u8 to bool one. Those lints recognize the transmute calls; they do not detect the UB itself.

A submission is graded on compiling, passing the tests, and producing no warnings under cargo clippy -- -D warnings.