Role of UB / uninitialized memory

[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?

[RalfJung]

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.

Oh, I missed that comment. And I don’t think it is true. I already quoted malloc above as yielding indeterminate values; the padding bytes of a struct will usually stay indeterminate. In fact, a quick search for “padding” in the standard brings up “The contents of ‘‘holes’’ used as padding for purposes of alignment within structure objects are indeterminate.”

Canvas unsafe code in the wild

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?

I think there is general agreement in the unsafe code guidelines team that there are some optimizations we want to do on safe code, and that we are willing to make things UB for that purpose. See https://github.com/nikomatsakis/rust-memory-model/tree/master/optimizations for some examples. I agree that UB is bad, but slow code is also bad. This is a trade-off. Making fewer things UB is one way to improve the situation here; another one that we are looking into is making UB testable. That would be a big thing, and put us in a totally different spot than where C sits. If we have a way to run your test suite in “UB checking mode”, so that you can be sure it doesn’t do anything the compiler doesn’t want you to do – that makes it much less of a problem for the UB rules to be subtle. Still, we want them to be as “un-subtle” as reasonable while still permitting sufficient optimization. After all, if people use C or assembly over Rust for reasons of performance, we haven’t gained much in terms of overall safety. (Also notice that the UB rules will only ever affect people the use unsafe, so most Rust programmers should not have to care.)

Also, is some forum moderator reading this? I think most everything since https://internals.rust-lang.org/t/canvas-unsafe-code-in-the-wild/4990/23 is interesting discussion and very valuable feedback, but it’s not on-topic in this thread any more, so maybe we could have it split into a new thread?

[le-jzr]

Canvas unsafe code in the wild

Oh, I missed that comment. And I don’t think it is true. I already quoted malloc above as yielding indeterminate values; the padding bytes of a struct will usually stay indeterminate.

Whether or not it’s currently true in Rust (or C, which is even less relevant), the question here is whether it should be. Half the text I wrote in this thread tries to explain that these definitions of indeterminate/undefined/uninitialized memory (all conflated into one package in Rust) don’t affect anything except for arbitrarily restricting what code is legal by definition…

Canvas unsafe code in the wild

I agree that UB is bad, but slow code is also bad. This is a trade-off.

…by which I also mean that this particular UB doesn’t make any reasonable optimizations possible.

Canvas unsafe code in the wild

another one that we are looking into is making UB testable

Determining whether a piece of memory is uninitialized, or whether uninitialized memory is read, is undecidable in general. Any realistic checking would necessarily flag lots of existing code as possible UB. But if there is a possibility to make it somehow work, I’m all for it.

Canvas unsafe code in the wild

(Also notice that the UB rules will only ever affect people the use unsafe, so most Rust programmers should not have to care.)

The people who use unsafe are also exactly the population whose mistakes break security assumptions in all surrounding code. I wouldn’t say it’s a niche concern.

Canvas unsafe code in the wild

maybe we could have it split into a new thread?

That would be very appreciated.

[notriddle]

Canvas unsafe code in the wild

Determining whether a piece of memory is uninitialized, or whether uninitialized memory is read, is undecidable in general. Any realistic checking would necessarily flag lots of existing code as possible UB. But if there is a possibility to make it somehow work, I’m all for it.

“Making UB testable” means (at least, as I understand it) being able to instrument a Rust program to detect if Undefined Behavior is invoked at runtime. Static analysis to detect UB already exists for Rust; the “testable UB” planning is centered around runtime checks for when static analysis is too conservative.

[RalfJung]

Whether or not it’s currently true in Rust (or C, which is even less relevant), the question here is whether it should be. Half the text I wrote in this thread tries to explain that these definitions of indeterminate/undefined/uninitialized memory (all conflated into one package in Rust) don’t affect anything except for arbitrarily restricting what code is legal by definition…

…by which I also mean that this particular UB doesn’t make any reasonable optimizations possible.

Well so one practical reason is that LLVM uses this semantics, so if we want to say something like “freshly allocated memory (heap or stack) is essentially a non-deterministically initialized bag of bits”, we’d have to actually zero-initialize everything to make LLVM play by these rules. I will concede that this is not a great reason to change our semantics, but it has to be taken into account. What you seem to be asking for, however, is a concrete useful optimization that would be disallowed by these semantics. I would be seriously surprised if there isn’t something LLVM does here that is actually useful, but that’s pretty far outside of my expertise. Maybe @eddyb or @arielb1 have an idea.

I will assume here that we use the same rule for heap and stack, for multiple reasons. Some have been outlined above by @rkruppe, I would also add that my personal view of the stack is that it’s just an optimization: Really, we could allocate every local variable on the heap individually, and deallocate them explicitly; doing this with a stack discipline is just a lot more efficient.

“Making UB testable” means (at least, as I understand it) being able to instrument a Rust program to detect if Undefined Behavior is invoked at runtime. Static analysis to detect UB already exists for Rust; the “testable UB” planning is centered around runtime checks for when static analysis is too conservative.

Right, that’s why I said “run your test suite”. This is not a static analysis, it is a dynamic check. Much like address sanitizer, only we could actually make it check for everything. We could even make this the definition of what it means to be UB. I wrote some blog posts about this: How to specify program behavior and Exploring MIR semantics through miri.

[catenary]

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

My understanding is that reading from an allocated (but as yet unwritten to) page will typically produce zeros, while reading after that page has been touched will produce some consistent garbage. So uninitialized memory would definitely be a meaningful concept at runtime.

[le-jzr]

we’d have to actually zero-initialize everything to make LLVM play by these rules

That’s not true. Apart from the padding bytes, which would indeed need to be initialized, and mem::uninitialized, which is just plain evil, Rust doesn’t allow anyone to touch or point to uninitialized stack memory, not even unsafe code. It’s statically prevented by the compiler.

Heap allocations are a non-issue because even if LLVM itself has special handling for the malloc function, and even if LTO makes those malloc calls bubble up all the way from the allocator crate to the consumer code (both very possible), all you have to do is to alias the function under a different symbol name. Then it’s just an extern function that returns a pointer, no special considerations involved.

Right, that’s why I said “run your test suite”. This is not a static analysis, it is a dynamic check.

Ah, right! That would be indeed very helpful.

We could even make this the definition of what it means to be UB.

Please don’t. It’s bad enough as it is, that Rust isn’t fully specified separately from implementation. It makes it harder to understand the language, and writing non-trivial code with borrows is already basically “make random changes until it compiles”.

I will assume here that we use the same rule for heap and stack, for multiple reasons. Some have been outlined above by @rkruppe, I would also add that my personal view of the stack is that it’s just an optimization: Really, we could allocate every local variable on the heap individually, and deallocate them explicitly; doing this with a stack discipline is just a lot more efficient.

I never, I repeat, never, suggested that heap and stack should be treated differently. I said previously that @rkruppe is attacking strawmen and I stand by that sentiment.

It could make it more clear to separate the two conflated concepts. For the purposes of discussion, let’s call them “undefined memory” and “not-initialized memory” (to disambiguate from “uninitialized”).

“undefined memory” is the concept that leaks from the LLVM level, it’s the memory that is considered uninitialized by LLVM, and reading it is UB as per LLVM’s rules. On Rust level, this maps exactly to padding bytes and std::mem::uninitialized(), and nothing more, assuming LLVM is disavowed of its knowledge about what is heap allocation (as explained earlier).

“not-initialized memory”, on the other hand, is the rust concept of uninitialized memory (https://doc.rust-lang.org/nomicon/uninitialized.html).

“undefined memory” is “not-initialized memory” by definition, but the opposite doesn’t hold. “not-initialized memory” which is not “undefined memory” is unsafe to read, but is not necessarily UB.

Now that the language is established, it should be clear that it’s possible for heap allocations to be “not-initialized memory”, while not being “undefined memory”. For the programmer, this is no more of a concern than the current definition of uninitialized memory. The argument that you would somehow need to care about the distinction is completely unfounded… if you can write unsafe code today without freaking out about uninitialized memory, you can do it just the same without freaking out about “undefined memory”. In fact, you can hold on to your current intuition. Anything that’s legal today would be legal with my suggestion. It would just make more code legal, including some cases that unexperienced programmers intuitively expect to be correct, but are in fact UB by current definition.

[le-jzr]

My understanding is that reading from an allocated (but as yet unwritten to) page will typically produce zeros, while reading after that page has been touched will produce some consistent garbage. So uninitialized memory would definitely be a meaningful concept at runtime.

The OS actually has to zero out the physical page you receive. Not doing so would be a security problem (privileged application allocates page to store confidential data, page is deallocated or swapped to disk without being cleared, another application maps the freed physical frame and reads confidential data).

[RalfJung]

The OS actually has to zero out the physical page you receive. Not doing so would be a security problem (privileged application allocates page to store confidential data, page is deallocated or swapped to disk without being cleared, another application maps the freed physical frame and reads confidential data).

However, the in-process memory allocator will happily re-use allocations. So whatever malloc returns may not be zeroed.