Validity of integers and floating point

[RalfJung]

Discussing the validity invariant of integer and floating point types.

Clearly, every possible bit pattern is allowed. For integers they all have a distinct and meaningful interpretation, and we have a safe NOP-conversion between f32 and u32, and f64 and u64, through to_bits and from_bits.

The remaining open question is: is it ever allowed to have an uninitialized bit in an integer or floating point value? We could reasonably decide either way. Also, when an integer is partially uninitialized, does that "infect" the entire integer or do we exactly preserve which byte is initialized?

2022-09-07: This has now pretty much been answered.

[RalfJung]

Arguments for allowing uninitialized bits:

• There does not seem to be a reasonable optimization that is broken by this.
• It does not contradict anything we currently tell LLVM.
• It simplifies writing code with mem::unintiailized()/MaybeUninit::uninitialized() when the type is known to consist of integers only.

Arguments for disallowing uninitialized bits:

• If we allow uninitialized bits, we have to define what happens with arithmetic operations when an input contains an uninitialized bit. Is that insta-UB? Is the result fully uninitialized? Does uninitializedness somehow propagate bitwise? These are hard choices, because it is easy to break arithmetic equations here. By disallowing uninitialized bits, we successfully avoid the question.
• "No uninitialized data outside of unions" is a nice and and easy to teach principle.
• Ruling out uninitialized bits in integers and floating points makes it easier to find bugs where people accidentally have such variables not properly initialized: A bug-finding tool can flag any occurrence of uninitialized memory in integers/floating points as a bug immediately. Also see https://www.youtube.com/watch?v=yG1OZ69H_-o: The fact that C makes integer overflow on unsigned variables defined to wrap-around actually has lead to real-world bugs (caused by unintended overflow) not being detected by bug-finding tools, because you cannot just mark every overflow as a bug. If there is a rare exception to a common principle ("integer overflow is a bug", "uninitialized data is a bug"), then it is preferable to have the programmer state their intent of violating that principle explicitly (use explicitly overflowing arithmetic operations like wrapping_add, use types like MaybeUninit for explicitly handling uninitialized data).

[RalfJung]

Here's an example of a piece of code that relies on uninitialized integers (and raw pointers, and AtomicPtr) being valid: https://github.com/carllerche/bytes/blob/456221d16521cf54cea0e6569669e47120a1b738/src/bytes.rs#L1810

[RalfJung]

An interesting use of uninitialized bits in integers is in crossbeam's AtomicCell: for types of certain sizes, it will use the AtomicU* types.

But this means that with a type like (u8, u16), it will use AtomicU32 and thus carry uninitialized bits in a u32. Also see crossbeam-rs/crossbeam#315.

Cc @stjepang

[gnzlbg]

If we allow uninitialized bits, we have to define what happens with arithmetic operations when an input contains an uninitialized bit. Is that insta-UB? Is the result fully uninitialized? Does uninitializedness somehow propagate bitwise? These are hard choices, because it is easy to break arithmetic equations here. By disallowing uninitialized bits, we successfully avoid the question.

If we were to allow uninitialized bits, it might be reasonable to say, at least initially, that any operation that's not a read or a write is UB. That would allow us to define those operations later on. For example, that would mean that adding an initialized integer with an uninitialized one is UB, but later on, we could define that to something else, like the result of that operation being uninitialized.

That is, we wouldn't need to answer these hard questions right now.

---

I wonder whether it is possible to allow uninitialized bits later on in a backwards compatible way or whether we do have to make this decision right now ?

I think we have to make this decision right now, because, e.g. if we forbid uninitialized bits, all unsafe code assumes that integers are always initialized, and we can't change that later to support uninitialized bits without breaking that assumption.

In the same way, if we allow uninitialized bits, we can't later on disallow them without breaking code that uses them.

---

"No uninitialized data outside of unions" is a nice and and easy to teach principle.

Agreed.

A bug-finding tool can flag any occurrence of uninitialized memory in integers/floating points as a bug immediately.

I don't think it can flag every occurence, for example, extern fn foo() -> MaybeUninit<i32>, but it would be able to do so for all code that the tool is able to instrument at least.

[hanna-kruppe]

I think we have to make this decision right now, because, e.g. if we forbid uninitialized bits, all unsafe code assumes that integers are always initialized, and we can't change that later to support uninitialized bits without breaking that assumption.

I don't see how. If a type's validity invariant rules out certain initialized bit patterns, unsafe code can use those bit patterns for its own purposes, which will clash with later allowing those bit patterns in the validity invariant. However, uninitialized bits -- even if they are valid -- cannot be detected by the program: reading them is either UB or perhaps produces some string or zeros or ones (possibly a non-deterministic one). So that kind of counter-example is right out.

Moreover, because uninitialized bits will never be safe, unsafe code can't be fed them from unknown/external sources. IOW the only way a library/module/etc. will ever see uninitialized bits is if it produces them itself or obtains them from its "trusted base" (e.g., a function whose functional correctness is relevant to the soundness of the library/module/etc.), in which case it's UB today and its problem is an internal bug, not the interface with the rest of the world.

[nikomatsakis]

I would be inclined to permit uninitialized data in integers.

My reasoning is as follows:

I think that backwards compatibility around mem::uninitialized is a real concern. It is a very common pattern to allocate an uninitialized [u8] array in practice, and I am reluctant to declare all of that pre-existing code UB (even if we deprecate uninitialized).

Second, I think that the crossbeam example which @RalfJung raised earlier feels like the kind of tricky thing that people shouldn't have to fret about. In particular, if you have uninitialized padding bits in structs and things like that which are known to be less than word size, I think you should be able to treat them as integers for convenience, and it seems like that would be Insta-UB under this proposal.

Basically, I think people are likely to do things (like crossbeam) that wind up using uninitialized bits in integers but which don't necessarily "feel" like cases where MaybeUninit should be required. I also think that people will commonly reason about uninitialized data informally and hence write code that is UB -- of course, a tool that detects such usage can help, but it's also nice if "common things" people write are not UB even if they neglect to run the tool.

That said, I find the most compelling argument against permitting uninitialized bits to be that it would allow us to declare such uses an error. But it seems like we could still have a sort of "lint", where we say "ah, you are using uninitialized data outside of a MaybeUninit struct -- while not technically UB, it is recommended to use MaybeUninit.

One meta-question:

Suppose that I do have a clever algorithm that makes use of uninitialized integers. For example, a trick I have used in a past life was to have an integer set that had O(1) initialization cost regardless of its capacity. This worked by having two vectors of integers. One of them started out with size N but had uninitialized data. The other started out as size 0 but had initialized data. To add to the set, you checked one against the other (I can give details if desired). The key point is that you had to read and use an uninitialized integer in the process and compare it against initialized data -- is reading such an integer UB?

[hanna-kruppe]

The crossbeam example and the "O(1) initialization" integer set, as well as all other clever uses of uninitalized memory that I'm aware of (i.e., not just allocating uninitialized memory and initializing it at your own pace before using it) require operating on uninitialized bits. So if we want to allow them, we need to not only allow reading uninitalized memory but also make arithmetic and comparisons on them defined (and reasonably deterministic! undef results are worse than useless). That is not possible at all with current LLVM (except by initializing all memory, or pretending to do so in ways that will block lots of unrelated optimizations) and even if/when freeze and poison is adopted, it'll have some negative codegen impact and I see no way to restrict that impact only to modules that really need it.

So even though I agree that it would be best to support these things, I do not see a reasonable way to achieve that.

[RalfJung]

The crossbeam example and the "O(1) initialization" integer set, as well as all other clever uses of uninitalized memory that I'm aware of (i.e., not just allocating uninitialized memory and initializing it at your own pace before using it) require operating on uninitialized bits.

Notice that this only applies to the compare_exchange part of crossbeam. Loads and stores do not operate on uninitialized data and hence are mostly fine.

So we have a two-level discussion here:

• Can we load/store uninitialized bits into integers?
• If yes, is there any other operation we can perform on them?

I'd prefer the answer to the first question to be "no" so that the second question doesn't even need answering, but unfortunately @nikomatsakis has some pretty good arguments. ;)
Just one word on these: at least under some proposed poison semantics for LLVM, poison acts on a value. That means if you load a (u8, u16) into a u32, if the padding was indeed uninitialized, you now have a fully uninitialized u32 -- if one byte of the memory is poison, the entire u32 becomes poison. So that would still not allow was crossbeam does. This behavior is, from what I know, one of the reasons why the proposal isn't officially adopted yet -- but if you don't do this, you lose some other optimizations.
However, this question of the "granularity" of poison/uninit (per-value, per-byte, per-bit) is somewhat orthogonal to whether or not a u32 must be initialized, and there are uses of uninitialized integers that never run into this.

Coming to the second question, as @rkruppe said these patterns (I think you are talking about https://research.swtch.com/sparse, right?) are still not legal. Comparing an uninitialized integer with anything is either UB or produces an uninitialized boolean, branching on which is UB. But once LLVM has freeze, we could make them legal very easily and (I think) without bad impact elsewhere by adding a freeze intrinsic and telling people to use that.

[hanna-kruppe]

But once LLVM has freeze, we could make them legal very easily and (I think) without bad impact elsewhere by adding a freeze intrinsic and telling people to use that.

Hm, if getting people to use such an intrinsic is acceptable (I think the biggest source of worry is people reasoning naively about uninitalized as "initialized to an arbitrary bit string" and not even checking), then we can already build such an intrinsic today, it just has to do something that all LLVM optimizations have to assume could initialized the memory (e.g., some inline asm). This will have some unfortunate impact on optimizations unrelated to uninitialized memory, but it will still be localized to uses of that intrinsic.

[RalfJung]

I think the biggest source of worry is people reasoning naively about uninitalized as "initialized to an arbitrary bit string" and not even checking

Fair, but I see no model that makes this work.

This is actually also a reason why I'd prefer to not allow uninitialized data in integers -- that may be more surprising, but it is easier to explain and very concise: "No uninitialized data outside MaybeUninit".

If we allow uninitialized bits but then almost all operations are UB, it becomes something more like "No uninitialized data outside MaybeUninit, except if it is an integer or a raw pointer and you are not actually looking at the data, just loading and storing" and then we still have to explain that x * 0 is also UB even though it doesn't really have to "look at" x -- and then people will be "screw this, that's too complicated, I will just do whatever and write some tests".

Basically, we are breaking expectations anyway, and maybe it is better to break them more but in simpler ways, than to figure out how to break them as little as possible while still breaking them in ways that are much more complicated to explain. That seems plausible to me. Not sure if it makes any sense.^^

[CAD97]

If uninitialized bits in an integer are made instantly invalid, is it possible to do the crossbeam::AtomicCell trick of making an atomic (u8, u16) by treating it as AtomicU32 at all? Is it possible to do that minus the CAS operation?

It seems like it should be possible to use an atomic (u8, u16) on a platform supporting 32 bit atomics. The only way I can see without requiring valid(T) \in initialized(u32) (and thus a very unsafe AtomicCell) is to provide some sort of mem::initialize_padding(&T).

I'm personally on the side of making uninitialized integers invalid so long as we don't lose anything (but mem::uninitialized) for it.