... so it's not UB
- in LLVM to invoke
@llvm.memcpy.p0i8.p0i8.i64on unitialized memory? - and in C/C++ to
memcpyfrom unitialized memory?
This is not UB, correct.
I wish I could tell you for sure, but unfortunately the C/C++ standards are rather vague around this topic. However, since memcpy is supposed to be used to copy structs with padding, certainly the intention is to allow copying uninit data with memcpy. So you are fine if you are using the primitive. Whether you can implement that primitive yourself with a loop copying char is unclear.
memcmp, on the other hand, is most certainly UB on uninitialized memory.
3 Likes
memcpy treats the arguments as though they were pointing to an array of the appropriate size of an unsigned narrow character type. Accessing indeterminate values (C/++ terms for "read from uninit memory") of unsigned narrow character types only yields an unspecified value, so it is not undefined behaviour to memcpy from uninitialized memory.
Note that using char itself is predicated on char being unsigned (if its signed, its still UB to perform a value computation on an indeterminate value), though its very much correct to implement the primitive with a type like unsigned char.
I agree that that is the intent of the standard. However, when I tried to pin down "indeterminate values" more precisely in C/C++, I got stuck. There's lots of talk about "trap representations" but very little about the behavior of indeterminate values on types that have no "trap representation".
See for example this paper discussing a defect report. The standard is still not clear on whether "indeterminate values" are stable or whether they can change when being read multiple times.
Lucky enough, none of this affects us in Rust. 
John Regehr has done experiments that demonstrate that LLVM, GCC, icc, and MSVC all take the strong statement about indeterminate values in informative annex J.2
The behavior is undefined if ... the value of an object
with automatic storage durationis used while it is indeterminate
as if it were 100% normative and also as if the crossed-out phrase were not present. Doesn't matter if there are trap representations, doesn't matter if it's unsigned char, doesn't matter if the address was taken. IIRC one can usually get away with reading padding bytes without getting your code deleted as unreachable, especially if it appears you're doing an open-coded memcpy of an entire structure, but sometimes not.
I don't think the normative text supports this reading, but I would expect the GCC and LLVM teams, at least, to argue that that is a defect in the standard, not a bug in the compilers. And based on experience with other places where Rust tries to nail down something that C++ leaves undefined, I think that means we're going to have an uphill battle if we want to nail this one down too.
@moderators could you split this discussion of uninit memory (starting here I'd say) into a separate thread? Thanks. 
Do you have a link for this?
Your interpretation seems to be that even just a read of uninit memory is considered UB in LLVM. I do not think this is true, and in particular it is not true in this formal model of LLVM of which John Regehr is a coauthor. Instead, this model says that reading uninit memory produces a poison value, and as long as you don't do a conditional branch on it, you are fine -- but any computation into which poison flows, returns poison.
Not one I can find easily right now, sorry. I recall seeing it on his blog circa 2015, possibly even earlier than that, and it was talking about LLVM's old undef...
... whereas this is dated 2018 and talks about poison. So maybe I'm out of date here wrt LLVM.
However, the code fragments I recall from Regehr's blog involved control dependencies on uninitialized data; in the simplest case something like
extern void a(void), b(void);
void c(void) {
unsigned char x;
if (x) { a(); } else { b(); }
}
If reading an indeterminate value, using a type without trap representations, has only unspecified behavior, then one could argue that the compiler is not allowed to compile c as-if it had made an unconditional call to either a or b — for the same reason that it can't in
extern void a(void), b(void);
union u { uint32_t wide; uint16_t narrow[2]; };
void c(uint32_t x)
{
union u u;
u.wide = x;
if (u.narrow[0]) { a(); } else { b(); }
}
From immediate research, in C++, cppreference, which I have noted is a reasonable place to find an good interpretation, mentioned here that in particular uses of specifically unsigned char and (in C++17 on), std::byte, since C++14 are valid even with indeterminate values https://en.cppreference.com/w/cpp/language/default_initialization.
Use of an indeterminate value obtained by default-initializing a non-class variable of any type is undefined behavior (in particular, it may be a trap representation), except in the following cases:
- if an indeterminate value of type unsigned char or std::byte (since C++17) is assigned to another variable of type (possibly cv-qualified) unsigned char or std::byte (since C++17)(the value of the variable becomes indeterminate, but the behavior is not undefined);
- ... (other omited similar statements, which imply you can manipulate indetermindate values of unsigned char or
std::byte, enough to move them, but can't doing anything else about it)
This wording from C, seems to support my argument though in that language in particular:
If an object representation does not represent any value of the object type, it is known as trap representation . Accessing a trap representation in any way other than reading it through an lvalue expression of character type is undefined behavior. The value of a structure or union is never a trap representation even if any particular member is one.
From: https://en.cppreference.com/w/c/language/object. Note that an indeterminate value is defined in C as "Either an unspecified value or a trap representation", so if its valid to access a trap representation through an lvalue of a character type, barring any specific prohibitations for indeterminate values, it should be elevated to unspecified. Beyond this, this wording implies that all indeterminate values of character types are simply unspecified values
For the objects of type char, signed char, and unsigned char, every bit of the object representation is required to participate in the value representation and each possible bit pattern represents a distinct value (no padding, trap bits, or multiple representations allowed).
Why not? An unspecified value can be assigned by the compiler. The compiler can assign a non-zero value to x, or a zero value to x.
3.19.3 unspecified value
valid value of the relevant type where this International Standard imposes no requirements on which value is chosen in any instance
From: http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1548.pdf.
Given this, I cannot see any cause for memcpy(x,y,n) to have undefined behaviour in the case where the range [y,y+n) includes uninitialized memory or padding bytes, provided the other constraints of memcpy are satisfied.
Ah yes, branching on poison is UB. But that is very different from saying that using poison is UB. For example, arithmetic on poison is allowed -- and it returns poison. Loading poison from memory into a local variable is also fine. (This is all talking about LLVM, not C/C++).
For undef vs poison, see this paper.
@InfernoDeity thanks for digging this out! But then if we take those lines at face value, how do you explain the UB when branching on poison, which is present in most compilers (I assume this is what John Regehr explored in the post @zackw referred to above)? Do all compilers just ignore the spec?
I think we all agree on this one. And we also agree that the committee likely wants this to be the case even for a hand-written memcpy. But the only reason a hand-written memcpy is fine in modern compilers is that it doesn't branch on the uninitialized values it read from memory -- that's why memcpy is okay but memcmp is UB. And the standard doesn't reflect this, to my knowledge.
Btw, in Rust we currently avoid these problems by saying that loading uninit memory into i* or bool or so is immediate UB. Loading it into MaybeUninit<u8> is okay, but you cannot branch on such a value. In other words, we successfully avoid the question.
It's not clear (to me, as I read the C standard) whether the compiler is allowed to choose a particular constant value as the result of the read access to x. The argument against would be that "reading an object whose value is indeterminate" is an operation that cannot be optimized away—precisely because the value is indeterminate and so the compiler cannot assume it knows the actual number that will result. That argument is agreed to hold for type-punning with a union, and I don't see any normative text that would distinguish the two cases.
For the record, I do agree with both of these assertions.
How cannot it not know the number if it wants to. "Unspecified Value" is entirely clear. The implementation can choose any value for an unspecified value it wants, provided its not a trap representation. The standard imposes no restrictions on the value chosen, including the restriction that "whatever happens to exist there is whats read", just how the standard imposes no restrictions on the results of undefined behaviour. The definition of Indeterminate value is an Unspecified Value or a trap representation, and if the value cannot be a trap representation by merit of the fact there is no such trap representation for it to be, it therefore must be an unspecified value.
The compiler can most certainly know what a particular unspecified value is, if it wants to, because its allowed to choose whatever value it wants. unsigned char x; x==0 is perfectly valid to be asserted by the compiler, as is x==1, x==42, or any other value.
Now the question you've mentioned is still valid, if asserting that x==0 or x==1 locks the unspecified value to a particular value, or if the compiler is allowed to let it "float", allow each of the comparisons to result in true without an intervening side effect (or, alternatively, fail an exhaustive cascading if or switch).
I'd add that in the union type-punning case, its also valid for the compiler to yield an indeterminate value for any "inactive" variants of the union, in would simply have to document this (Accessing a member of a union which was not the member last written to has implementation-defined behaviour), It just happens that the compiler vendors agree and document that accessing the inactive members reinterpret the active members object representation (potentially resulting in an indeterminate value if the active member is too small or any padding bytes aren't padding in the result)
Aha, that's where you're confused. Accessing a member of a union which was not the member last written to, in fact, has unspecified behavior. (See 6.2.6.1.) There is no normative text that I can find, anywhere in the standard, that makes any distinction between this operation and a read access to an uninitialized automatic variable whose type has no trap representations. So, if you're going to argue that the compiler can pick a constant value for a read access to an uninitialized automatic variable, you are also making an argument that it can also pick a constant value for a read access to a union member that was not the one last written to, which is not what anyone wants. And conversely, if you're going to argue that it can't pick a constant value for a read access to a union member that was not the one last written to, then you're also making an argument that it can't pick a constant value for a read access to an uninitialized automatic variable.
Fair, implementation-defined behaviour is just unspecified behaviour that has a documentation requirement.
Also, it never says that unspecified behaviour has to be consistent, or even determinisitic (see for example, int x; int y; &x<&y && &y < &x). The compile can pick a constant value for read access to an uninitialized automatic variable, and still allow unions to reintrerpret the object representation, as they can be discussed as independent cases of unspecified behaviour. Saying that one implies the other implies a restriction imposed on the standard, when that would, in fact, be refuted by the definition of unspecified value, which states
valid value of the relevant type where this International Standard imposes no requirements on which value is chosen in any instance
So in fact, you can not reason that because the implementation chooses to resolve unspecified behaviour in any particular way in a specific instance, that it must resolve similar (not even the same) unspecified behaviour in a different way, because no such limitation exists.
OK, I can see where that's a valid argument (although I will tell you from bitter personal experience that you'll get absolutely nowhere trying to make that argument with someone who's annoyed that the new version of the C compiler broke their dusty deck) but it doesn't really help us make design decisions for Rust. If the C standard has next to nothing to say about what happens when you read an uninitialized variable, then we can't look to it for guidance much, can we?
If we're doing language design in a vacuum, I think it's reasonable for the compiler to pick an arbitrary, constant value for x in
extern void a(void), b(void);
void c(void) {
unsigned char x;
if (x) { a(); } else { b(); }
}
However, there's another thing it could potentially do with this unconditional control dependency on an indeterminate value: infer that c is never called. Specifically, in
extern void a(void), b(void);
static inline void c(void) {
unsigned char x;
if (x) { a(); } else { b(); }
}
int d(int n) {
if (n <= 0) {
c();
return 0;
}
return n;
}
is the compiler allowed to emit code for d equivalent to
int d(int n) { return n; }
? A quick test on godbolt indicates that neither GCC nor clang actually does that in the most recent available version, but I think it would be valuable for Rust to guarantee that it will not happen.
... This is pretty far from memcpy. Maybe I should make a new thread.
However, I would argue it is far from self-evident that this can lead to things like x == x returning false (in a UB-free program). And yet this is what the committee says is the right interpretation, and they do not even deem it worth saying so explicitly in the standard.
TBH, most of the time in Rust I would only use the C/C++ standards as guidance for how to not do something. 
UB in C is an ambiguous mess that takes many people many years to clean up, I think we can do much better than that.
In Rust, we have no "indeterminate values", but we have an explicit notion of whether some memory or value is initialized or not. Most types consider uninitialized data invalid outside their padding bytes, leading to UB when reading them from uninit memory. In particular this includes all types on which we support primitive operations, so the question of what happens when the input of a conditional branch or an addition is uninit does not even arise -- the program has already caused UB by even constructing that uninit input.
4 Likes
What about this footnote?
If the member used to read the contents of a union object is not the same as the member last used to store a value in the object, the appropriate part of the object representation of the value is reinterpreted as an object representation in the new type as described in 6.2.6 (a process sometimes called ''type punning''). This might be a trap representation.
Unfortunately, footnotes are non-normative. That particular footnote ought to be normative, though, and I'm not aware of any C compilers that don't implement that behavior. (C++ is different.)
Rust doesn't need unions for bit reinterpretation between scalar types, but it might need to make certain classes of union-based type punning be well-defined for system ABI compatibility (e.g. access to the sa_family field of socket addresses) (whether or not this is well-defined in C has been angrily disputed for decades now 
and we definitely should not copy the C standard's wording on the subject).
In my reading, Rust makes all union-based type punning well-defined -- or rather, as well-defined as transmute. Unions are basically just syntactic sugar for transmuting to/from the field type on every write/read.
5 Likes