Role of UB / uninitialized memory

[zackw]

Canvas unsafe code in the wild

What do you mean exactly by “trigger”,

… I don’t know how to put that any more clearly. What do you want to call it when the compiler starts pruning entire control flow paths because they can never be executed without executing a construct whose behavior is undefined?

Canvas unsafe code in the wild

can you show an example of this happening?

Sure:

int foo(void);
int bar(void)
{
    int x;
    if (foo())
        x = 3;
    return x;
}

compiles, using GCC 6.3 for x86-64, to

bar:
	subq	$8, %rsp
	call	foo@PLT
	movl	$3, %eax
	addq	$8, %rsp
	ret

See how the return value is unconditionally 3? This optimization would not be allowed if reading an uninitialized variable produced a merely “unspecified” value. If you tag the declaration of foo with __attribute__((pure)) (this means “I solemnly swear that foo has no side effects”), it won’t even bother calling foo. And, due to a long-standing pass-ordering problem, you don’t get a warning about the use of an uninitialized variable! (The lack of a warning is GCC bug 18501.)

Clang 3.8 does the same thing (the generated assembly language is not quite the same but that’s only because it does the stack alignment a little differently), but at least it does warn about the uninitialized variable.

[le-jzr]

Canvas unsafe code in the wild

int foo(void);
int bar(void)
{
    int x;
    if (foo())
        x = 3;
    return x;
}

This is not a memory access. Uninitialized locals and uninitialized memory (indirectly accessed through a pointer) have very different properties. In particular, there is no way for compiler to discern what’s on the other side of the pointer (apart from the declared type), so it can’t make any optimization that take that into account.

[zackw]

Canvas unsafe code in the wild

Uninitialized locals and uninitialized memory (indirectly accessed through a pointer) have very different properties.

I understand why you think that, but it’s not true anymore. This small modification of the program I posted earlier…

#include <stdlib.h>
extern int foo(void);

int bar(void)
{
    int *x = malloc(sizeof(int));
    if (!x) abort();
    if (foo())
	*x = 3;
    int r = *x;
    free(x);
    return r;
}

compiles to…

bar:
	pushq	%rax
	callq	foo
	movl	$3, %eax
	popq	%rcx
	retq

… with clang 3.8. (gcc6 isn’t this clever.)

I suspect clang/LLVM managed to do this by “lowering” the malloc allocation to a local variable, thus converting the program into the previous program, but if there were a distinction between uninitialized locals and uninitialized memory, that transformation would be invalid.

[RalfJung]

To get this to a somewhat more high-level point, LLVM has undef and poison values that both have very special behavior, and in particular, neither of them corresponds to any particular bit pattern. The sad truth is that we cannot have both “everything is a bit pattern” and keep all the fancy optimizations compilers do. Rust will have to have something similar. miri has Undef, which ironically is more like LLVM’s poison than LLVM’s undef (but that’s good, LLVM’s undef is pretty crazy).

C decided to treat unsigned char* specially to make it possible to implement memcpy. Rust could do the same with u8, but that somewhat feels wrong – why u8 and not the other integer types? And this is why @nikomatsakis brought up this union type, which is supposed to express "either T or Undef":

union Uninit<T> { init: T, uninit: () }

[zackw]

Canvas unsafe code in the wild

Rust could do the same with u8, but that somewhat feels wrong – why u8 and not the other integer types?

I concur, char in C tries to be too many different things at once and it just causes trouble. std::mem::byte maybe?

[le-jzr]

Canvas unsafe code in the wild

And this is why @nikomatsakis brought up this union type, which is supposed to express “either T or Undef”:

union Uninit<T> { init: T, uninit: () }

I might be missing something, but if you can’t tell statically whether or not something is initialized, how does a union like that help? If you read init from uninitialized memory, it’s still UB, and you have no way of knowing whether it is.

[le-jzr]

Perhaps I should clarify what I’m talking about. Let’s go with a very specific example.

[#inline(never)]
fn memcpy64(dest: &mut [u64], src: &[u64]) {
    for i in 0..src.len() {
        dest[i] = src[i];
    }
}

As far as I can tell, when this function compiles, the resulting machine code is always correct, even if the memory that src points to hasn’t been touched since the motherboard first powered on. Here, the function must never be inline because there is no other way to express the constraint that compiler doesn’t make assumptions about src, but it shows that “uninitialized memory” is a dubious concept. Making those reads “UB by definition” doesn’t seem well motivated. There is no actual “uninitialized memory” in a running computer.

[RalfJung]

Canvas unsafe code in the wild

If you read init from uninitialized memory, it’s still UB, and you have no way of knowing whether it is.

The idea is that you wouldn’t read the init field. You have a memcpy somewhat like this:

fn memcpy64(dest: &mut [Uninit<u8>], src: &[Uninit<u8>]) {
    for i in 0..src.len() {
        dest[i] = src[i];
    }
}

I have to say though that this does feel pretty hacky. Not sure I am happy with this as the work-around to access Undef.

Canvas unsafe code in the wild

As far as I can tell, when this function compiles, the resulting machine code is always correct

The machine code being correct doesn’t mean anything except that the compiler is not “smart” enough to notice all instances of UB.

Canvas unsafe code in the wild

There is no actual “uninitialized memory” in a running computer.

That’s true. However, unitialized memory is still a very useful concept in describing the behavior of programs, in particular if we want to consider out programs at a higher level than assembly languages do. I suggest you do some Googling about LLVM’s poison and undef, there should be numerous examples out there explaining why the LLVM developers considered it necessary to add these concepts even though they do not “exist” in a running computer. A brief search brought up this note and this first of a series of blog posts, for example.

in a running computer, pointers and usize are also “the same” type. If we constrain ourselves by what things are on a running computer, there are many valuable optimizations that we cannot do. For example, we could never move a variable access across a function call – after all, the unknown function we call could “guess” the address of our local variables in memory, and access them. In a running computer, nothing stops them. But we don’t want to permit functions to do that, precisely because we do want to perform optimizations. To this end, when we specify the behavior of programs, we imagine our computer to have “extra bits” that we use to keep track of things like whether something is a pointer or an integer, or whether memory is initialized. I also recently wrote a blog post motivating this kind of “extra state”: https://www.ralfj.de/blog/2017/06/06/MIR-semantics.html

“Really” high-level languages like Java have a much easier time with all of this because they don’t allow programmers to ever observe things like uninitalized memory. “Really” low-level languages like Assembly do not permit interesting optimizations, so they can get away with a very bare-bone kind of representation. Languages like C and Rust, on the other hand, want to eat the cake and have it, too – they want to do optimizations based on high-level intuition while at the same time permitting the programmer to observe low-level details (like the fact that padding bytes exist). Properly doing this is a hard and unsolved problem.

[le-jzr]

The nomicon gives an exhaustive list of UBs in Rust, and it’s pretty short. “Reading uninitialized memory” is the odd man out. Every single one of the remaining sources of UB is motivated by pure technical necessity. But “reading uninitialized memory” is not UB by necessity, that one’s an arbitrary choice. It’s perfectly possible, even simple, to let Rustc emit code with no undefined memory.

Think about it. It’s already impossible to read or reference undefined locals on Rust level, except for that one ugly intrinsic. If the intrinsic didn’t exist, Rust would be one of those “really” high-level languages already.

On the other hand, the decision whether or not the heap allocator returns “uninitialized” memory is completely arbitrary metadata, and while it’s certainly unsafe to access that memory (interpreting it as certain types is UB), there is nothing that would make it inherently broken.

Edit: To clarify, I’m not arguing against the concept of uninitialized (heap) memory. I’m arguing that the blanket statement “reads of uninitialized memory are UB” doesn’t make sense. It should be unsafe, not UB. The result of std::mem::uninitialized() is the obvious exception, and should be considered as a separate category.

[RalfJung]

Canvas unsafe code in the wild

Think about it. It’s already impossible to read or reference undefined locals on Rust level, except for that one ugly intrinsic. If the intrinsic didn’t exist, Rust would be one of those “really” high-level languages already.

I don’t think that’s the case. Rust permits you to do all sorts of nefarious things with pointers, things that involve observing the offset of fields and how structs are laid out in memory. Have a look at the code of Rc::from_raw. Another example is HashMap, which allocates one large chunk of memory and then splits it into three pieces, namely, an array of hashes, keys, and values. This is only possible if you take a low-level view of memory, where everything is ultimately just a bunch of bytes.

Canvas unsafe code in the wild

To clarify, I’m not arguing against the concept of uninitialized memory. I’m arguing that the blanket statement “reads of uninitialized memory are UB” doesn’t make sense. It should be unsafe, not UB.

Oh, I see. I misunderstood you then, sorry. What is your stanza on reading uninitialized memory at type bool? That type is an enum, which typically guarantees that the value is either 0 or 1. If you now pass an uninitialized bool somewhere, is it okay for that to be UB?

Canvas unsafe code in the wild

The result of std::mem::uninitialized() is the obvious exception, and should be considered as a separate category.

The point that mem::unitiailized and malloc yield “the same kind of” unitialized memory has already been made above in this thread. Existing compiler transformations will happily turn a malloc into a local variable if they can prove that it is not used after the function returns. I also feel there’s little gained from distinguishing the two.

[le-jzr]

Canvas unsafe code in the wild

What is your stanza on reading uninitialized memory at type bool? That type is an enum, which typically guarantees that the value is either 0 or 1. If you now pass an uninitialized bool somewhere, is it okay for that to be UB?

Definitely UB. There is no limit to the harm you can make by breaking type invariants. This is not strictly limited to fundamental types or uninitialized memory either. Transmute from an initialized byte will do the same thing, and plenty library types have internal invariants that will cause UB if broken.

Canvas unsafe code in the wild

The point that mem::uninitialized and malloc yield “the same kind of” uninitialized memory has already been made above in this thread.

Rust doesn’t use malloc() (not necessarily, anyway), and LLVM doesn’t either AFAICT. It’s just an external function that clang in particular has special optimizations for. Doesn’t mean it’s a good idea for Rust to treat heap the same way.

I mean, what are the odds that your code just happens to not require the heap allocations you are making, and you never noticed?

Canvas unsafe code in the wild

I also feel there’s little gained from distinguishing the two.

Less UBs in tricky unsafe code is IMO a gain well worth the distinction.

[le-jzr]

Canvas unsafe code in the wild

I don’t think that’s the case. Rust permits you to do all sorts of nefarious things with pointers, things that involve observing the offset of fields and how structs are laid out in memory. Have a look at the code of Rc::from_raw. Another example is HashMap, which allocates one large chunk of memory and then splits it into three pieces, namely, an array of hashes, keys, and values. This is only possible if you take a low-level view of memory, where everything is ultimately just a bunch of bytes.

What I meant is, it doesn’t allow any way to create undefined values you can legally read (apart from said mem::uninitialized(), and putting aside the ambiguity of heap allocation). Of course you can always use unsafe code, to create pointers to places on stack you shouldn’t see, but that’s UB by virtue of breaking the aliasing rules I think.

[rkruppe]

The idea of treating heap memory and stack memory differently w.r.t. UB is an interesting one. It goes completely against my intuition, but it took me a while to understand why. I believe the reason why stack and heap memory should be the same in this regard is that all memory should be interchangeable. I don’t mean that the optimization discussed earlier (demoting mallocs) should be legal, I mean that I want to choose how I allocate memory solely based on considerations like allocation lifetime and performance and availability (e.g. whether I even have a heap), not by language lawyering about UB.

Especially when I’m doing low-level, unsafe work where I treat something as a bag of bits and do dangerous things with it, I don’t want to care where in memory those bits reside. I have enough trouble getting the actual bit bashing right. I don’t want to track down a misoptimization caused by moving a temporary buffer from a Vec to a stack-allocated array (or the other way around).

The virtue of treating heap and stack alike also shows elsewhere: Your proposed memcpy64 is only well-defined (under the proposed “reading uninit heap memory is okay”) if it copies from a heap allocation into another heap allocation. IIUC, the inline(never) is supposed to force the compiler to conservatively assume the heap-heap case, but that’s not how this works. Language semantics must be defined independently of “what the compiler can see” and if you say “reading uninitialized bits from the stack is UB”, then calling memcpy64 with stack buffers as arguments is UB, period. (And this will inevitably be exploited by a compiler author trying to squeeze out a few percent out of a benchmark suite.) So a rule that distinguishes stack and heap memory makes it actually harder to write a correct memcpy, because it’s easy to write something that’s only UB for stack memory (i.e., where it’s even harder to observe the UB).

Of course, one could invent arbitrary semantics that are aimed at preventing certain reasoning steps by the compiler. For example, one solution would be to draw a line at function boundaries (perhaps only those that are inline(never)) and say that pointer arguments are to be treated “as if” they were referring to heap memory. Besides being very inelegant and throwing the whole object model into disarray, this will inevitably have fallout for the compiler’s ability to analyze and optimize. So I am not a fan of this approach either (at least in principle, I won’t rule out that there’s some twist that is relatively simple and brings much advantage.)

---

PS:

Canvas unsafe code in the wild

I mean, what are the odds that your code just happens to not require the heap allocations you are making, and you never noticed?

That can easily happen in overly general code spread over multiple functions. But aside from the specifics, it doesn’t sound very appealing to rule out optimizations just because they sound like good code shouldn’t need them.

[arielb1]

Canvas unsafe code in the wild

Rc::drop calls RcBoxPtr::dec_weak after decrementing the strong count and droping the content of the RcBox. This is somewhat interesting because RcBoxPtr::dec_weak takes &Rc<T> as an argument and is a perfectly safe function, but it is actually called on an Rc that is in a bad state – it doesn’t satisfy the usual invariants that Rc typically satisfies. However, the Rc passed to dec_weak is still a valid instance of a “syntactic Rc”, so I don’t think the compiler could exploit this in any way.

That’s safety vs. definedness again. The language should not “guess” your types’ semantics - if you don’t use any “magic” attributes, the language should only care about whether your types are “syntactically” valid - e.g. you should be able to use an RcBox to store 2 random words (as long as you don’t call any Rc functions in a way that would crash).

[le-jzr]

Canvas unsafe code in the wild

The idea of treating heap memory and stack memory differently

That’s not what I said, you are attacking a strawman. All memory is same, but pointers have different sources, and they don’t necessarily lower to memory access. Specifically, if you reference a local, LLVM is allowed to optimize the memory access away completely in certain cases. In order to do so, it must know statically which value is in the memory, which basically means that the memory is allocated and accessed in the same function (that’s why inlining matters in my example).

The problem is that if LLVM knows that the memory is not written to before read, it can do anything it wants with the access, but this is only doable with memory allocated with alloca, and the only way to achieve this in Rust is std::mem::uninitialized.

Heap allocation (not heap memory) is different because it’s an external function with no special LLVM semantics. Defining heap allocations to be uninitiated is an explicit special case in Rust’s definition (lawyering by the language, as you put it). In fact, all memory coming from heap allocator is just subdivided regions of initialized memory provided by the OS. There are no LLVM optimizations taking place, and Rust-specific optimizations don’t​ benefit from uninitialized reads being UB, since any such optimizable code would almost certainly be invalid by definition, not to mention that most uses of heap go through safe abstractions anyway.

[rkruppe]

Canvas unsafe code in the wild

Specifically, if you reference a local, LLVM is allowed to optimize the memory access away completely in certain cases.

If we’re only talking about accesses, then heap vs. locals (or, if you prefer to talk about that, the means of memory allocation) is not inherently relevant. The compiler is, and absolutely should be, allowed to remove (or introduce, or shuffle around) memory accesses no matter the source. More importantly, it’s absolutely possible for LLVM to deduce that a load through a pointer yields uninitialzed bytes even without seeing where that memory is allocated. Consider this function for example:

unsafe fn make_and_read_undef(p: *mut u8) -> u8 {
    let u = mem::uninitialized();
    *p = u;
    *p
}

Even leaving aside any knowledge of uninitialized memory, it ought to be possible to optimize that code into this:

unsafe fn make_and_read_undef(p: *mut u8) -> u8 {
    let u = mem::uninitialized();
    *p = u;
    u // <- changed
}

… which has the effect of making the memory access *p yield uninitialized bytes, regardless of how and where it was allocated. So as long as “all memory is the same” and there is some source of uninitialized memory, any memory can be made uninitialized, unless we start randomly restricting useful optimizations such as store forwarding.

Canvas unsafe code in the wild

The problem is that if LLVM knows

Again, whether something is UB or not is a semantic question, and so if we want to make certain operations defined or not, we need to lay out the criteria in terms of Rust semantics. What some compiler does or doesn’t know, and what it does with that knowledge, is only relevant when testing whether said compiler is faithful to the semantics. These two concerns only intersect when it comes to judging how practical some proposed semantics are.

I tried to guess at what semantics you are proposing by reading it as “reading uninit stack memory is UB, reading uninit heap memory is fine” but apparently that was wrong. I apologize and would like to learn what semantics you are proposing. I believe that would be easier for me if you explained these semantics separately from how they can or cannot be implemented on LLVM.

Canvas unsafe code in the wild

Heap allocation (not heap memory) is different because it’s an external function with no special LLVM semantics. Defining heap allocations to be uninitiated is an explicit special case in Rust’s definition (lawyering by the language, as you put it).

This is not entirely true, LLVM knows about the symbol malloc (among others) and will treat it as the C function of the same name. So Rust code using the system allocator will also be affected by this, assuming some interprocedural analysis or inlining (which we’d like to have, at the very least to avoid additional overhead from wrapper functions compared to calling malloc directly—zero cost abstractions and all that jazz) .

[RalfJung]

Canvas unsafe code in the wild

In fact, all memory coming from heap allocator is just subdivided regions of initialized memory provided by the OS. There are no LLVM optimizations taking place,

To add to what @rkruppe said, the C standard explicitly says that memory returned by malloc is uninitialized: "The malloc function allocates space for an object whose size is specified by size and whose value is indeterminate." The motivation for this is to abstract away from details like allocating memory from the OS, and describe what all C programs can rely on when calling malloc.

[RalfJung]

Canvas unsafe code in the wild

What I meant is, it doesn’t allow any way to create undefined values you can legally read (apart from said mem::uninitialized(), and putting aside the ambiguity of heap allocation).

(Where “it” is “Rust”.)

That’s not entirely true: If you write something like let x = Struct { f1, f2, f3 };, the padding between the fields can well remain uninitialized. Still it should be legal to pass &x to memcpy to access mem::size_of::<Struct> many bytes.

[le-jzr]

Canvas unsafe code in the wild

That’s not entirely true: If you write something like let x = Struct { f1, f2, f3 };, the padding between the fields can well remain uninitialized. Still it should be legal to pass &x to memcpy to access mem::size_of::<Struct> many bytes.

Right, I kind of internalized what @zackw said

Canvas unsafe code in the wild

So in C, padding bytes are special-cased in several places with the intention that you can always interact with a struct safely (byte-by-byte or otherwise) as long as all of its value fields have been initialized. Specifically, padding bytes have unspecified, but never indeterminate, values. That would be a sensible way to deal with them in Rust if it doesn’t already work that way.

I can’t see why anyone would want to disagree with this, so I stashed it away to “resolved issues” in my head.

[le-jzr]

I’ll try to break up my argument into small, independent pieces, so that it’s more understandable (and more easy to determine which parts are not agreeable). The problem I’m having explaining my rationale is that so many concepts and layers of abstractions are involved.

First off, let’s settle the general assumption: Undefined behavior is bad. If it’s not intuitive, it’s even worse. Things should only be classified as undefined behavior if doing them necessarily breaks assumptions programmer makes about the code. More to the point, giving the compiler freedom to do more optimizations is not by itself a sufficient argument to make something UB. There are numerous examples where C code doesn’t work as expected, because of things that are counterintuitively defined to be UB. Notorious examples in C are signed integer overflow and strict aliasing rules. They break correct-looking programs, silently. Any disagreements?