Role of UB / uninitialized memory

[RalfJung]

@le-jzr

That’s all well and good, but I fail to see how it pertains to the discussion at hand. I’m not debating the usefulness of certain methods and constructs having more assumptions attached to it.

The discussion at hand was about what the behavior should be around uninitialized memory, and you were claiming malloc is not special ("little more than an external function that returns a pointer"). I was arguing why that is not the case. It was not clear to me that you were not saying this is what heap allocations are, but rather what heap allocations could be, if we wanted to deviate from the typical C-like model. Sorry for the confusion.

@le-jzr

It’s not intended as an argument against the model, it’s an explanation aimed to show that some aspects of the model can be relaxed easily and without breaking the universe or touching many things (even if certain optimizations become inapplicable). I merely proposed that a compiler switch can be added that removes certain assumptions for the purpose of hardening against UB. The point of all I’ve written is that eliminating all sources of undefined memory is much easier than it sounds.

All sources, I do not agree. How would you specify casting whatever you get back from malloc (or an uninitialized stack slot) to a function pointer and calling that, without making it UB?

Many sources, maybe -- if you are willing to swap out LLVM with something else. Taming down LLVM far enough may prove hard to impossible. But anyway I doubt this is a realistic option, the performance loss will likely be enormous. So this discussion does not seem useful to me.

[le-jzr]

@RalfJung

It was not clear to me that you were not saying this is what heap allocations are, but rather what heap allocations could be, if we wanted to deviate from the typical C-like model. Sorry for the confusion.

I'm sorry as well. I'm aware that understanding what I mean can be difficult.

@RalfJung

All sources, I do not agree. How would you specify casting whatever you get back from malloc (or an uninitialized stack slot) to a function pointer and calling that, without making it UB?

I admit I don't understand you at all here.

What part of Rust actually depends on the idea that individual bytes of allocated memory are undefined? You can just as well cast a zeroed (or randomized) byte slice to a function pointer and call that. Whether or not the memory is valid for a given type is a separate issue.

@RalfJung

Many sources, maybe – if you are willing to swap out LLVM with something else. Taming down LLVM far enough may prove hard to impossible. But anyway I doubt this is a realistic option, the performance loss will likely be enormous. So this discussion does not seem useful to me.

Taming what? There are exactly three sources of uninitialized memory, which I'm sure I've enumerated before.

It's mem::uninitialized() (solution: just switch the intrinsic to mem::zeroed()), heap::allocate() (solution: treat it as you would a standard FFI function that returns a pointer), and padding bytes (solution: emit padding explicitly as data).

That done, there would be no way to get undefined memory in Rust.

@RalfJung

the performance loss will likely be enormous.

Evaluating the performance impact of those three adjustments is exactly why I think they should be implemented as an option.

[RalfJung]

Sorry, you wrote "undefined memory" and I read "undefined behavior". So my answer made no sense.

But, this actually leads me to a higher-level point -- there are plenty of sources of UB, and I don't find uninitialized memory a particularly troublesome one. I would not see getting rid of this UB as a significant achievement, given that Rust is almost certainly going to have more subtle kinds of UB form some form of aliasing constraints.

@le-jzr

Taming what? There are exactly three sources of uninitialized memory, which I’m sure I’ve enumerated before.

It’s mem::uninitialized() (solution: just switch the intrinsic to mem::zeroed()), heap::allocate() (solution: treat it as you would a standard FFI function that returns a pointer), and padding bytes (solution: emit padding explicitly as data).

That done, there would be no way to get undefined memory in Rust.

I'm not sure doing this in LLVM is as easy as you make it sound, but I am not an LLVM expert. LLVM represents uninitialized memory with its special undef value, and undef can I think also occur in other situations; you can't just "disable" undef in LLVM.

[hanna-kruppe]

@RalfJung

I’m not sure doing this in LLVM is as easy as you make it sound, but I am not an LLVM expert. LLVM represents uninitialized memory with its special undef value, and undef can I think also occur in other situations; you can’t just “disable” undef in LLVM.

This is true, though the only way for such an undef to make its way into memory is if you compute a value that is undef, and store it in memory. But if you can do that, you can probably just use the undef value (and cause UB by using it in particular ways) without going through memory.

So it's very true that we can't avoid having to deal with "different bit pattern on every access" values, but I'm not sure how relevant that is for preventing memory from being the source of such values.

[le-jzr]

@RalfJung

Sorry, you wrote “undefined memory” and I read “undefined behavior”. So my answer made no sense.

Ah, I see, now it makes sense.

@RalfJung

But, this actually leads me to a higher-level point – there are plenty of sources of UB, and I don’t find uninitialized memory a particularly troublesome one.

Arguably true, but it's one of the least "obvious" ones. To be honest, I only really care about padding bytes, because everything else is so easily avoidable as to be trivial, and there are some low-level things that work out much simpler when all bytes (within a particular range) are born equal (e.g. memcpy).

For padding bytes to be "safe", you could either make sure the backing storage always starts out as well-defined in the entire length, or you could treat padding bytes as data (which is probably simpler). Each approach has different effect on possible optimizations, but nothing is free, sadly.

You can see that the consideration of heap and stack memory is involved, but I probably got carried away with the technical discussion.

@RalfJung

I’m not sure doing this in LLVM is as easy as you make it sound, but I am not an LLVM expert. LLVM represents uninitialized memory with its special undef value, and undef can I think also occur in other situations; you can’t just “disable” undef in LLVM.

I'm not an LLVM expert myself, but my logic is that if regular language constructs can generate undef, then it would necessarily cause opportunities for UB in safe Rust, and safe Rust is assumed to be, well, safe. This very much limits ways undef can enter the picture.

[djzin]

@le-jzr

I’m not an LLVM expert myself, but my logic is that if regular language constructs can generate undef, then it would necessarily cause opportunities for UB in safe Rust, and safe Rust is assumed to be, well, safe. This very much limits ways undef can enter the picture.

AFAIK undefined behaviour is already a problem for safe rust code, inherently because it lowers to llvm and you need to be very careful because undef is everywhere. For instance

fn main() {
    let x = 100000.0 as u8;
    if x > 0 {
        println!("debug");
    } else {
        println!("release");
    }
}

Now I know there was discussion of this particular case before, so I'm not sure if this actually causes "real" undef, but I'm almost certain that there will be something very much like this if you go looking for it.

[le-jzr]

Undefined behavior in safe rust is always a bug in rustc. “safe” in “safe rust” is specifically defined as “cannot cause UB”.

Your example is invalid. While as isn’t exactly the cleanest thing in Rust (I’d certainly love to see it gone), its intended behavior is pretty thoroughly specified, and your example is a known bug.

[hanna-kruppe]

@djzin

AFAIK undefined behaviour is already a problem for safe rust code, inherently because it lowers to llvm and you need to be very careful because undef is everywhere.

Rust is specified to not have UB in safe code. Thus, any time a Rust compiler accepts safe code and lowers it to LLVM IR that does execute UB, that's a bug in the compiler, not UB in Rust-the-language. That LLVM has easily accessible UB just means the compiler needs to be careful with how it lowers Rust to LLVM IR, not that safe Rust can have UB. See Undefined Behavior != Unsafe Programming by John Regehr.

[le-jzr]

@djzin The idea that LLVM just randomly throws around undef is completely unfounded, and in fact it would make it totally useless for most languages other than C. The cases where undefs are generated by LLVM instructions are completely specified and in general, safe languages work around them with extra code.

For example, division by zero is undefined behavior in LLVM, but not in Rust. Rust simply emits a zero check for the divisor, and panics if division by zero would occur. Same goes for any other operations that are UB in specific testable cases. Those remaining bits of untestable, intrinsic UB (e.g. invalid memory and pointers) are eliminated by safe Rust not allowing invalid memory and pointers to exist at all. That’s the whole point of borrow checker and lifetime analysis.

[djzin]

Thanks guys, the “AFAIK” was because I was unsure, guess I was wrong (my example being considered a bug). Good to know that there’s a little more sanity around undef in llvm! null

[gnzlbg]

There is an intrinsic in the stdsimd crate that initializes a vector register to zero. The way that intrinsic ought to implemented is by a pxor instruction that xors the register with itself [0]. In a nutshell:

fn main() {
    unsafe {
        // u32 for exposition only, the real type is LLVM's x86_mmx
        // which in rust is a `#[repr(simd)] struct __m64(i64);`
        let a: u32 = ::std::mem::uninitialized();
        let b = a ^ a;  // read of uninitialized memory
        println!("{}", b); // should always print: "0"
    }
}

The question is: is this undefined behavior? The nomicon says:

Attempting to interpret this memory as a value of any type will cause Undefined Behavior. Do Not Do This.

and the docs of mem::uninitialized say:

It is undefined behavior to read uninitialized memory, even just an uninitialized boolean.

Citing the reference which says:

Behavior considered undefined: Reads of undef (uninitialized) memory.

So I would guess that the answer is yes?

In the same spirit, this is just a personal question of mine, is this:

fn main() {
    unsafe {
        let a: u32 = ::std::mem::uninitialized();
        let b = a * 0;  // read of uninitialized memory
        println!("{}", b); // should always print: "0"
    }
}

undefined behavior?

[0]: In particular, we are implementing _mm_setzero_si64, which is the function that sets an MMX register to zero, that is, our let a: MMX = 0, so we can't really set the register to anything but mem::uninitialized, and the only way to implement it is by xoring the uninitialized register with itself.

[hanna-kruppe]

I really strongly thing these should both be UB or yield a “poison” value or whatever we decide to say about all other computations that involve loading uninitialized memory. I can see no good reason to allow it (more on this in a second), it’s just the programmer being too clever for their own good. And it really constrains the optimizer. LLVM for example can’t really implement this, neither with undef nor with the future poison, at least if it wants to keep doing routine transformations on values that it has not proven to not be undef/poison.

As for why I don’t see a good reason to allow it: If the programmer knows that the computation will always result in a constant, they should just write that constant out instead of fooling around with uninitialized memory. _mm_setzero_si64 for example should really simply be return MMX(0) or whatever way you use to construct an MMX value with a certain bit pattern (worst case transmute but I really hope you have a better way). The backend can and will materialize that constant with a pxor (assuming it even has to materialize it). Likewise for any other constant one might be tempted to construct in such a dangerous fashion.

[gnzlbg]

The Intel Intrinsic guide defines that _mm_setzero_si64 as the intrinsic that generates the pxor mm, mm assembly sequence. The only way to force LLVM to generate that instruction is to use llvm.x86.mmx.pxor directly.

@hanna-kruppe

_mm_setzero_si64 for example should really simply be return MMX(0) [...] The backend can and will materialize that constant with a pxor (assuming it even has to materialize it).

It doesn't materialize a pxor in this case, and if the backend doesn't materialize exactly just a pxor mm, mm we deviate from the spec.

[Amanieu]

This is the implementation that Clang uses:

static __inline__ __m64 __DEFAULT_FN_ATTRS
_mm_setzero_si64(void)
{
    return (__m64){ 0LL };
}

[hanna-kruppe]

@gnzlbg

It doesn’t materialize a pxor in this case, and if the backend doesn’t materialize exactly just a pxor mm, mm we deviate from the spec.

Interesting that the backend does something different [1], but as long as it's functionally equivalent and not slower, it doesn't really matter. None of the "intrinsics" are really guaranteed to map to a specific instruction (in C compilers, too) and this is a good thing because it enables optimizations.

If whatever the backend does instead is slower, well, that should be fixed, but it should be fixed in the backend (or possibly by using the LLVM intrinsic, but that likely negatively impacts optimizations).

[1]: Assuming that materializing the constant is really necessary. In many test cases one might write, it can just be removed or folded into a different instruction, and doing that is not just fine, it's expected.

[gnzlbg]

Yes, violating the spec (it generates xorps instead of pxor; pxor always runs in the ivec domain, while xorps runs on the float domain in some CPUs and crossing domains incurs a cost in these CPUs).

---

@hanna-kruppe

I’ll fill an LLVM bug.

[hanna-kruppe]

@gnzlbg

Yes, violating the spec (it generates xorps instead of pxor; pxor always runs in the ivec domain, while xorps runs on the float domain in some CPUs and crossing domains incurs a cost in these CPUs).

To be completely clear: there is no expectation at all of generating exactly the instruction that the intrinsic corresponds to. There is no violation of any spec or even of a reasonable expectation. At most this is a performance bug.

[gnzlbg]

Users that want to use xorps can do so via the _mm_setzero_ps intrinsic, and arguably if LLVM would emit something better than pxor in all cases then it wouldn’t be a bug (there are some intrinsics for which this is the case, and we just documented what LLVM does and why, add a test for this to detect LLVM changes, and call it a day).

In sufficiently modern CPUs (SandyBridge and better) it doesn’t matter which one is used (both take effectively 0 cycles), but xorps is in general (without targeting a particular CPU) arguably worse than pxor because it has less throughput. Anyways I’ve filled an LLVM bug for this, thanks! https://bugs.llvm.org/show_bug.cgi?id=35869