How compiler works with uninitialized memory?

[lifr0m]

I have read many resources about this topic, here a some of them:

• "What The Hardware Does" is not What Your Program Does: Uninitialized Memory
• Here's My Type, So Initialize Me Maybe - Faultlore
• Understanding the basic idea of uninitialized memory - #10 by jorendorff
• Warning I received trying to solve my problem: Clippy Lints
• Answer which confused me even more: How does the compiler understand that memory is initialized? - #2 by derspiny

I'm trying to implement contiguous deque buffer for my program needs where content is placed in the middle of allocated memory. I need to use some internal structure as allocated array for my data. The most straightforward path is to use Vec<u8> and create with vec![0; capacity];. But that is obviously performance - zeroing memory, especially when buffer is reallocated for more space and content is copied.

I found unsafe method set_len on Vec struct and tried to use it right after calling Vec::with_capacity and received warning from clippy. Then I started my investigation about llvm quirks.

The first thing I understood is that I can't use Vec for my purpose, I need some array struct which stores pointer and length.

Here is the code I wrote.

use std::ops::{Deref, DerefMut};
use std::{alloc, ptr, slice};

pub struct Array {
    ptr: *mut u8,
    len: usize,
}

unsafe impl Send for Array {}

unsafe impl Sync for Array {}

impl Array {
    pub fn new() -> Self {
        Self {
            ptr: ptr::dangling_mut(),
            len: 0,
        }
    }

    pub fn alloc(len: usize) -> Self {
        assert_ne!(len, 0);

        let layout = Self::layout(len);
        let ptr = unsafe { alloc::alloc(layout) };

        if ptr.is_null() {
            alloc::handle_alloc_error(layout);
        }

        Self { ptr, len }
    }

    fn layout(len: usize) -> alloc::Layout {
        alloc::Layout::array::<u8>(len)
            .unwrap()
    }
}

impl Drop for Array {
    fn drop(&mut self) {
        if self.len != 0 {
            let layout = Self::layout(self.len);
            unsafe { alloc::dealloc(self.ptr, layout) };
        }
    }
}

impl Deref for Array {
    type Target = [u8];

    fn deref(&self) -> &Self::Target {
        unsafe { slice::from_raw_parts(self.ptr, self.len) }
    }
}

impl DerefMut for Array {
    fn deref_mut(&mut self) -> &mut Self::Target {
        unsafe { slice::from_raw_parts_mut(self.ptr, self.len) }
    }
}

Buffer struct.

pub struct Buffer {
    data: Array,
    head: usize,
    tail: usize,
}

I need to use my buffer in various scenarios. But the core part is working with network - passing &mut buf[pos..] to AsyncReadExt::read. The way I do this is ensuring data has enough space and then adding x to tail, resulting in data[pos..tail] being uninitialized but valid data which I can write to.

After, I realized I can't do even that. Also I found out that unsafe Rust is not C or C++, it's much more complicated and dangerous place. I learned about MaybeUninit but it can't be used in all places, for example rand::fill.

My question: is there any way to tell the compiler: don't optimize / assume initialized / don't mess up my allocated array without actually writing to it?

[robofinch]

Code taking &mut [u8] is allowed to read that data, unless it specifically guarantees that it doesn’t. Nothing you tell the compiler can stop arbitrary user code which takes &mut [u8] from reading the slice.

&mut [MaybeUninit<u8>] is the stable std way to indicate what you want. (There are also crates like bytes which provide a interfaces for write-only buffers.)

If rand doesn’t provide a way to work with uninit buffers, the compiler can’t do anything about that.

In one of my own crates, I ended up using initialized buffers together with a buffer pool. When I need a buffer, I first try to grab one from the pool with an appropriate capacity; else, I allocate a new zeroed-out buffer. When I need to reallocate a buffer, I get a buffer with appropriate capacity (either from the pool or newly allocated), copy over the data, and return the old buffer’s allocation to the pool. Dropping a buffer likewise returns its allocation.

The buffer is more-or-less a Vec, except the spare capacity is guaranteed to be initialized (to possibly-random init data, not necessarily zero) instead of maybe being uninit.

The pool I made is pretty bad, I didn’t have time to optimize it much, but it was still good enough to improve the speed of my code by several percent: anchored-leveldb/crates/anchored-leveldb/src/pub_traits/pool/bad_pool.rs at 7cc38877ba4670a390474fcd9faad81f3d208e4b · robofinch/anchored-leveldb · GitHub

@lifr0m

After, I realized I can't do even that. Also I found out that unsafe Rust is not C or C++, it's much more complicated and dangerous place.

I don’t really have that experience TBH. Instead, it feels like C and C++ can be just as dangerous, it’s just mostly undocumented. E.g., C and C++ predate the formalized idea of pointer provenance, so when working with pointers, the question of “when exactly is a pointer invalidated” feels very undocumented and best-effort to me.

[lifr0m]

I was also thinking about buffer pool, but with some timeout for each, to release memory after like 5 minutes if it's not needed. In theory it would be even better than creating every time new buffer with MaybeUninit because on large data buffer can reallocate several times.

So if I understand correctly, the only way to work with uninitialized memory is MaybeUninit and there are no way to tell compiler memory is initialized without writing to it? For initialized memory I should use &[u8], for uninitialized &[MaybeUninit<u8>] and for both I can use pointer?

[robofinch]

@lifr0m

In theory it would be even better than creating every time new buffer with MaybeUninit because on large data buffer can reallocate several times.

I do worry that a sufficiently complicated buffer pool is just a memory allocator. Using with_capacity hints is usually good enough, I think.

To the second paragraph: mostly, yes, I think you understand it correctly. However, I wouldn’t overstate how special MaybeUninit is. The reason that it can store uninit data is because MaybeUninit<T> is a union between () and T. (It does have a special property: its ABI is guaranteed to be the same as that of T, which is a capability not yet exposed to user-defined code using stable Rust, but that’s not about uninit.)

As for treating data as initialized without writing it, there’s the “mythical freeze intrinsic” which does not yet exist in Rust. Treating data in the stack or registers as initialized without writing it is possible in LLVM via its freeze intrinsic (if my understanding is correct), but freezing heap data might actually require writes. That latter problem feels like quite a blocker for any sort of freeze in Rust.

[kpreid]

@lifr0m

The most straightforward path is to use Vec<u8> and create with vec![0; capacity];. But that is obviously performance - zeroing memory, especially when buffer is reallocated for more space and content is copied.

You should check this assumption by measuring the performance. Zero-initializing can be nearly free because the CPU, MMU, and standard library functions recognize it as an important special case and optimize it, recording “this virtual memory page contains all zeros” instead of writing zeros to physical memory.

[lifr0m]

Interesting, but I'm also trying to understand how compiler works, not only trying to optimize my program.

[kpreid]

Sure. But one of the reasons why Rust doesn’t already have a stable, complete, and convenient set of operations for doing IO with partially-uninitialized buffers is — besides that it’s tricky to do well — that zero-initialization is actually cheap. The standard library Read trait does have read_buf() to read into uninitialized memory. But that method is unstable, because the design isn’t complete, and the reason it hasn’t been worked on eagerly and moved to stability by now is that it isn’t as valuable as you might think. These factors are part of the whole picture.

[lifr0m]

Ok, now the only thing I don't understand is how compiler decides if something is UB. Let's pretend we compile code with max optimizations and compiler can do anything with our code if it meets UB. Let's pretend it will for example remove code.

Compiler considers this is UB and nothing will be printed:

let mut x = MaybeUninit::<u8>::uninit();
let x = unsafe { x.assume_init() };
if x < 150 || x > 100 { println!("hello"); }

Compiler considers this is not UB and hello will be printed:

let mut x = MaybeUninit::<u8>::uninit();
x.write(42);
let x = unsafe { x.assume_init() };
if x < 150 || x > 100 { println!("hello"); }

Now my question is: will compiler remove code/do something weird here:

let mut x = MaybeUninit::<u8>::uninit();
if some_unknown_at_compile_time_ffi_function() {
    x.write(42);
}
let x = unsafe { x.assume_init() };
if x < 150 || x > 100 { println!("hello"); }

Because compiler can't know whether x is initialized or not at compiler time, it can't decide whether this code UB or not.

[kpreid]

For example, the compiler is free to rewrite your last example as if it were

let mut x = MaybeUninit::<u8>::uninit();
some_unknown_at_compile_time_ffi_function();
x.write(42);
let x = unsafe { x.assume_init() };
if x < 150 || x > 100 { println!("hello"); }

because

• if the write does not happen, UB happens
• the foundation of all reasoning about programs is that UB does not happen
• therefore, in all meaningful executions of the program, the write always happens
• therefore there is no need to make the write conditional.

Further (or simultaneous) optimization can then realize that the code is simplifiable to

some_unknown_at_compile_time_ffi_function();
println!("hello");

because nothing else matters to the actual run-time outcome.

[lifr0m]

That's interesting, because in the second post I mentioned in the question, author said compilers love to optimize and remove code because it will be "faster".

Unfortunately, what compilers most love in the world is to prove that something is Undefined Behaviour. Undefined Behaviour means they can apply aggressive optimizations and make everything go fast! Usually by deleting all your code.

[marlez]

@lifr0m

Undefined Behaviour means ...

The problem with undefined behaviour is in its very name. It's undefined behaviour, as in: no one has taken the time to draft up a contract in between the given language's specification (be it C or C++ or Rust), its abstract machine (see the first link in your post), and the underlying compiler toolchain (GCC or LLVM or MSVC) with regards to what must happen in the latter, should the former ever surface in your code. Since no one has defined what must happen, anything could happen.

Some parts of your code might get scrapped. Some parts may get optimized. Some parts could collapse into a single ud2 instruction (see the assembly generated for this example). Asking "what will the compiler do if I send some UB code its way?" is akin to wondering what your boss will do come tomorrow, should you decide to forego all of your usual responsibilities, as defined by the contract you've signed the day you got hired, and instead .. pretend to be your boss's wife?

He might appreciate the effort. He might not, for some god awful reason. He might decide to divorce his wife and marry you, instead. Or he might proceed to humiliate, threaten, and berate you in front of all your colleagues, before promptly kicking you out on the street without any 2-week notice. If you'd rather not find out what it is exactly that he's going to do, you might want to stick to your usual job description, and not come poking all over the place. That's what (avoiding) UB is about.

[lifr0m]

So you are trying to say that possibility of UB is UB, and possibility of possibility of ... of UB is UB too and compiler can do whatever he wants?

[kpreid]

@marlez

The problem with undefined behaviour is in its very name. It's undefined behaviour, as in: no one has taken the time to draft up a contract ...

That is the origin of the name, but it is not how UB is treated in Rust. Most things that are UB were chosen to be UB either because they enable optimizations, because the cost of the runtime checks to make them not UB would be too high (which is sort of like optimization except that it is not a compiler pass, but rather a language design choice), or, rarely, because it's not yet clear what sub-cases should be defined behavior.

@lifr0m

So you are trying to say that possibility of UB is UB, and possibility of possibility of ... of UB is UB too and compiler can do whatever he wants?

Depends on what you mean by "possibility".

• A program which has a branch that is UB, but which is never actually taken, is valid.
• But the compiler is allowed to delete that branch, because it is allowed to assume that UB does not happen.

[scottmcm]

@lifr0m

Let's pretend we compile code with max optimizations and compiler can do anything with our code if it meets UB.

It's not that it "meets" UB and then does stuff accordingly. Instead, the vast majority of it is that because UB is impossible (that's the rule) it does transformations that are possible as a result without checking.

My go-to example is things like putting local variables into registers. If you do something like let mut x = 3; let mut y = 4; (&raw mut x).add(1).write(5); dbg!(y);, it's not that it "meets" the UB and optimizes something away. It's that it says "well, you didn't use y in any way that's allowed to have edited it, so you must not have edited it, and thus obviously it's going to write 4". It doesn't have to go "oh, what you did there is UB".

(Really, if it could reliably and consistently notice that you're doing UB then Rust would just make it not-UB and define what it does instead.)

[mroth]

@lifr0m

Compiler considers this is UB

A compiler does not "consider" whether something is UB in the same sense that a human does. A compiler is essentially a large collection of algorithms, and those algorithms are written under certain assumptions. If the input violates those assumptions, the result can be arbitrary.

A simple example is binary search on a list, slice, vector, or array. The author of the binary search function may state:

If you use this binary search function, the elements must be sorted in ascending order. If they are not sorted in ascending order, no guarantee is made about the result.

That is a form of undefined behavior. In a simple case, the binary search may just return the wrong element. In an extreme case, depending on the implementation, it might enter an infinite loop.

The difference with a compiler is mainly complexity. For a small function like binary search, it is relatively easy to control how the function behaves on invalid input, or to prove whether it can loop forever.

For complex algorithms, such as those used in compilers, this becomes much harder, and sometimes impossible in practice. In some cases, a compiler algorithm cannot even reliably determine whether a required precondition holds. If the program violates the language rules, the compiler is allowed to assume that such a case never occurs and optimize accordingly.

UB is not a runtime decision made by the compiler. UB is a property of a program execution that violates the rules or assumptions specified by the language or by an API contract. Once UB occurs, the implementation is no longer required to provide any particular result.

[jumpnbrownweasel]

@scottmcm

My go-to example is things like putting local variables into registers. If you do something like let mut x = 3; let mut y = 4; (&raw mut x).add(1).write(5); dbg!(y);, it's not that it "meets" the UB and optimizes something away. It's that it says "well, you didn't use y in any way that's allowed to have edited it, so you must not have edited it, and thus obviously it's going to write 3". It doesn't have to go "oh, what you did there is UB".

Did you mean "it's going to write 4"? If not, I'm missing something.

[robofinch]

Yeah, that’s a typo. (With the programmer perhaps expecting 5 via the UB write.)

[simonbuchan]

If it helps, the thing that made UB "click" for me is roughly this definition: a language defines the meaning of source code, creating an interface between you and the compiler that allows you to mutually agree on the behavior exhibited.

If the language says that some source code should have some behavior and the compiler fails to produce that behavior, that's a compiler bug. If a human fails to produce source code that defines behavior according to the language, that's a human bug. In either case, there's no way to reason about what the behavior of anything in the program could be because the language isn't being followed any more.

---

The idea that a compiler is trying to prove you have UB to optimize is a sort of mental shortcut to understand the effects when UB causes issues, eg deleting code; it's technically the opposite (it is proving facts about your program based on the assumption that you don't have UB), but it does end up mathematically the same if there was no unknown information. Unfortunately, most of the time the compiler either practically can't, or it's literally impossible to know if some source code is UB just by looking at it (eg. it's depending on the documented behavior of code that may not even exist yet, like a future version of an OS). Instead of giving up and being conservative, it's trusting you to follow the rules you need to follow, so it can do to best job it can do.

[blonk]

@scottmcm

(Really, if it could reliably and consistently notice that you're doing UB then Rust would just make it not-UB and define what it does instead.)

I carried around this misconception about UB for longer than I like to admit. I basically assumed there was a conceptual "big book of UB"[*], which all compiler developers eventually sat down with and thought "ok, let's implement some of these UB's in my compiler, so the optimizer can generate faster code".

In my defense, I don't think that the concept of UB is communicated very well. A friend of mine asked about UB a few years ago, and I directed him to a CppCon presentation specifically about UB. After watching it he could list of bunch of constructs that would cause UB in C and C++, but he still came away with the same misconception that I once had.

This thread would have set me straight immediately, though.

---

[*] One would think that the fact that I never encountered the book "The Complete Reference Of All UB All Compiler Developers Need To Implement" would have been a some kind of hint -- but apparently I am very stupid.

[lifr0m]

Thanks all for answers. It seems I just misunderstood what UB is. The language defines some rules, which compiler relies on to optimize code. If developer breaks these rules, compiler doesn't know about it and will generate unpredictable code, trying to optimize everything. Compiler blindly assumes developer always follows rules. One of these rules is not reading uninitialized memory.

In Rust, specifically, this rule is that reference should point to initialized memory, so &mut [u8] must not be created when data behind it is uninitialized. Pointers, though are allowed to point to uninitialized memory.