Role of UB / uninitialized memory

[RalfJung]

Padding bytes themselves aren’t a source of uninitialized bytes, so they don’t fit into the same category as heap allocations and mem::uninitialized. The reason padding bytes come up is that they can remain uninitialized even if the struct is otherwise fully initialized. If heap allocs and mem::uninitialized are always zero, uninitialized bytes cannot enter the program (except via FFI), and hence padding bytes are never uninitialized.

[cuviper]

providing a compiler switch that turns all padding bytes, heap allocations and mem::uninitialized() into explicitly zeroed (or at least random but well-defined) memory.

For the heap, glibc has mallopt(M_PERTURB, val) or MALLOC_PERTURB_=val in the environment.

If heap allocs and mem::uninitialized are always zero, uninitialized bytes cannot enter the program (except via FFI), and hence padding bytes are never uninitialized.

What about padding bytes in a value on the stack?

[RalfJung]

What about padding bytes in a value on the stack?

How would a stack value have uninitialized bytes, other than via mem::uninitialized?

[cuviper]

let x = (0u8, 0u32);

Aren’t the padding bytes here still uninitialized?

(edit: removed an “incremental” initialization example - I forgot that doesn’t work.)

[RalfJung]

Ah, you are right. Yes, struct (and enum) literals also have to ensure to zero-initialize things. I think in LLVM this compiles effectively to let x; x.0 = ...; x.1 = ...;.

[comex]

They are a source of uninitialized bytes in C:

When a value is stored in an object of structure or union type, including in a member object, the bytes of the object representation that correspond to any padding bytes take unspecified values.

So even a struct which is initially zero-initialized can become uninitialized. Not sure if LLVM ever takes this wording to heart and creates undefs.

(Note that “indeterminate value” is defined as “either an unspecified value or a trap representation”, so aside from trap representations, “unspecified” is just as bad as “indeterminate”. In particular, while reading them theoretically isn’t undefined behavior - which @zackw suggested above is a drafting error, at least in the case of indeterminate values - it’s almost as dangerous. “Unspecified value” is defined as “valid value of the relevant type where this International Standard imposes no requirements on which value is chosen in any instance”, and at least some people interpret “in any instance” as “any time it’s read/used”, i.e. the value doesn’t have to be consistent.)

[RalfJung]

aside from trap representations, “unspecified” is just as bad as “indeterminate”

I am not sure what you base this on - as far as I know, it’s the trap representations that make indeterminate values “really bad”.

In particular, while reading them theoretically isn’t undefined behavior - which @zackw suggested above is a drafting error, at least in the case of indeterminate values

As you said, he was speaking about indeterminate, not unspecified, values.

at least some people interpret “in any instance” as “any time it’s read/used”, i.e. the value doesn’t have to be consistent.)

That article is behind a paywall. Could you cite the relevant parts?

Anyway we don’t depend on C here, we depend on LLVM. I would be hard-pressed to believe that copying an undef-free range of memory at the right type could result in undefs.

[comex]

That article is behind a paywall. Could you cite the relevant parts? Anyway we don’t depend on C here, we depend on LLVM. I would be hard-pressed to believe that copying an undef-free range of memory at the right type could result in undefs.

Sorry. Actually, I read it through Google cache - here’s a link.

Relevant bits:

In all cases, an uninitialized object has an indeterminate value. The C standard states that an indeterminate value can be either an unspecified value or a trap representation. An unspecified value is a valid value of the relevant type where the C standard imposes no requirements on which value is chosen in any instance. The phrase “in any instance” is unclear. The word instance is defined in English as “a case or occurrence of anything,” but it is unclear from the context what is occurring. The obvious interpretation is that the occurrence is a read.[9] A trap representation is an object representation that need not represent a value of the object type. Note that an unspecified value cannot be a trap representation.

[…]

Defect Report #451[11] deals with the instability of uninitialized automatic variables. The proposed committee response to this defect report states that any operation performed on indeterminate values will have an indeterminate value as a result. Library functions will exhibit undefined behavior when used on indeterminate values.

Looking at DR#451 itself, the proposed response that would specify ‘any operation on indeterminate values will have an indeterminate value as a result’ would also change the definition of “indeterminate” so this property doesn’t apply to merely “unspecified” values. However, there’s also a bit that says perhaps padding bytes should act that way anyway:

• Strong sentiment formed, in part based on prior experience in developing Annex L, that a new category of “wobbly” value is needed. The underlying issue is that modern compilers track value propagation, and uninitialized values synthesized for an initial use of an object may be discarded as inconsequential prior to synthesizing a different value for a subsequent use. To require otherwise defeats important compiler optimizations. All uses of “wobbly” values might be deemed undefined behavior.

[…later…]

• The committee agrees that this area would benefit from a new definition of something akin to a “wobbly” value and that this should be considered in any subsequent revision of this standard.
• The committee also notes that padding bytes within structures are possibly a distinct form of “wobbly” representation.

(emphasis mine)

Anyway, I think LLVM probably doesn’t actually generate undefs for this, but I’m not sure

[le-jzr]

For the heap, glibc has mallopt(M_PERTURB, val) or MALLOC_PERTURB_=val in the environment.

The issue for heap is not exactly about what’s in there. As I explained some time ago, heap allocations are little more than an external function that returns a pointer. The problem here is that Rust memory model itself considers the memory to be UB to read, as a special case. This has no analogy on the system level, it’s only there to admit optimizations by the compiler. The switch I’m suggesting wouldn’t actually need to involve any writes to the memory. It could very well just disallow the optimizations that depend on the memory being undefined (simply by not considering it to be undefined in the first place).

Ah, you are right. Yes, struct (and enum) literals also have to ensure to zero-initialize things. I think in LLVM this compiles effectively to let x; x.0 = …; x.1 = …;.

Not just literals, too. There is no guarantee that an arbitrary assignment uses any sort of memcpy() analog. That could be inefficient for data that have large amounts of padding. It is not unheard of for a structure to take up several times the size of its fields in memory, because of alignment requirements and whatnot.

They are a source of uninitialized bytes in C:

C is not exactly famed for running a tight ship when memory is concerned. In terms of LLVM, all you need to do is claim to it that those padding bytes are real data.

[RalfJung]

heap allocations are little more than an external function that returns a pointer. The problem here is that Rust memory model itself considers the memory to be UB to read, as a special case. This has no analogy on the system level, it’s only there to admit optimizations by the compiler. The switch I’m suggesting wouldn’t actually need to involve any writes to the memory. It could very well just disallow the optimizations that depend on the memory being undefined (simply by not considering it to be undefined in the first place).

malloc is special in a bunch of ways, e.g. it comes with an annotation saying that the resulting pointer does not alias any previously existing pointer. ptr::offset is UB if the pointer arithmetic leaves the “allocated object”, so a definition of this behavior has to know about how memory is allocated in blocks. None of this has an “analogy on the systems level”. The same applies for other sources of UB in C, like integer overflows.

This is not an accident, it is a feature. It turns out that programs are much easier to analyze, and hence much easier to optimize, if you have a more abstract model of the machine. Languages like Haskell take this very far. This results in a conundrum for C: One the one hand, people want code to be fast and optimized in smart ways – but on the other hand, these optimizations are actually wrong if you have the power to observe the machine “on the systems level”. Much of the complexity of the C standard arises from trying to reconcile these to worlds, and they are actually doing a remarkably good job.

One consequence of all of that is that “this abstract model is not actually how the machine works” is not an argument against using it as a model. That said, there should usually be a justification for deviating from “actual systems behavior”. The justification for doing this in the case of malloc has already been brought up – the compiler should be free to transform heap to stack allocations to registers and vice versa. Not having three different kinds of storage simplifies the model. Treating uninitialized data special for registers is immediately useful, it means the compiler can just insert any random register as the source of uninitialized data, with no guarantees about the data being stable or well-formed for any given type. Consequently, all storage has a form of uninitialized data that is different from “unknown bit patterns”.

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

One consequence of all of that is that “this abstract model is not actually how the machine works” is not an argument against using it as a model.

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.

[RalfJung]

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.

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]

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.

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.

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.

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.

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.

[rkruppe]

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]

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

Ah, I see, now it makes 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.

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.

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]

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.

[rkruppe]

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.