A bug story: data alignment on x86
pzemtsov.github.io
pzemtsov.github.io
The author did not know "What Every C Programmer Should Know About Undefined Behavior": http://blog.llvm.org/2011/05/what-every-c-programmer-should-...
Another good link about that: http://blog.regehr.org/archives/213
Note, though, that a compiler simply doing a particular thing now isn't good enough to specify it in the sense that I mean. The compiler writers would have to explain (in a blog post or the like) the behavior and that they plan to keep that behavior in all future versions.
This is a great way to make your programs "fun" to port to new platforms with new compilers in terrifyingly subtle ways. I prefer not to recommend this approach to solving specific cases of undefined behavior, although if you happen to disable strict aliasing (with e.g. -fno-strict-aliasing) as an additional layer of defensive paranoia, I'm not necessarily against that.
Hell, even if you don't think you'll ever need to do that, you should still avoid doing things that are platform or compiler specific.
Just don't use undefined behavior.
2. Users report that it started crashing sometimes in version V.
3. After lots of debugging, you discover an input that reliably crashes your program after 30 minutes.
4. A bit later, you discover that your compiler started compiling function f so that it no longer works with unaligned data/buffers of exactly 8 bytes/whatever.
5. At the start of main, you add a dummy call to f with data that reliably crashes if your compiler decides to do that optimization again.
6. The program has become worse: it now always crashes, independent of its input, but you don't have to wait 30 minutes before finding out. That makes it way less likely that you ship a binary again that has the problem. It also makes it easier to tweak source code/compiler flags/whatever until the problem disappears.
Is that perfect? Absolutely not, it is more something of last resort, but depending on the costs of crashing versus those of sometimes crashing half-way through a run, it can be an improvement.
(this technique also can be used when your code hits compiler bugs)
(famous reply from Sparta, Laconia, to Philip II of Macedon)
That said, you can use -fsanitize=undefined to verify correctness of a program (as far specification is concerned). Just be prepared for it being a bit slow.
I also think it is fairly unlikely that any C compiler will say anything about how it handles undefined behaviour because it would mean it has to generate awfully inefficient code. For example, a compiler could not optimize away most pointer dereferencing code if it promised that dereferencing odd addressses segfaults.
Yes, such checks might add at most a few percent to a normal program's running time, but add in all the other corner cases (int overflow, boundary checks, etc.) that also dat a few percent, amd before you know it your program runs at half the speed it could run at. If you find that acceptable, you shouldn't be writing C in the 21st century.
Undefined behavior is 'anything goes'. An implementation can choose a particular behavior that you can rely on for a particular case of UB, because, if the only rule is that 'anything goes', it doesn't violate that rule.
I'll admit that compilers don't generally do that - because specifying it could lead to fewer optimizations. But I did say "if", and there's no reason they couldn't do so in principle.
One could imagine a compiler with an extremely strict debug mode that traps on a number of situations that the standard deems undefined behavior via a segfault, in order to help people avoid relying on UB. Again - saying something like "casting misaligned pointers causes a segfault on [system]" would in no way violate a standard that says "casting misaligned pointers can do anything", because segfaulting falls under the umbrella of anything.
I think you're misinterpreting the fact that the results of undefined behavior can be ignored by a compiler for a requirement that it must be ignored by a compiler.
While true, your comment doesn't get at the root of the problem. The obvious fact here is that there is a mismatch between the C standard and how the users really use it. The less obvious fact/opinion/fallacy, is that it is not automatically the user's fault.
The standard could be wrong.
Sure, there are reasons why such and such behaviour ended up undefined. Those reason are sometimes weak however: some behaviour ended up undefined on all platforms because some of them couldn't handle it reasonably. The alignment bug here is such an example.
To this day I don't understand why undefined behaviour wasn't specified on a platform-by-platform basis. We already have implementation defined behaviour, after all. I guess this is because it lets compiler writers unify their front-ends and optimizers, but as a result, we cannot use our platforms to their fullest potential.
I would even claim that the language on all platforms definitely should be able to specify the "inconvenient" alignments, but that the platforms which can produce the fast code should. If you actually need some suboptimal alignment, you'll need it no matter if the '"language lawyers" cry now. I'd agree, the standard is potentially wrong for not having the possibility. It should be visually obvious that it's not optimal, but it shouldn't be too ugly to use it.
It's better to be able to declare something uniformly than to have pages of #ifdefs or to write a lot of ugly code.
This article and the comments here are good example. The article doesn't end there, it hopefully ends here in the comments, as qb45 claims that there is actually a declarative way for gcc, which at least on one version (the one which he tried) did produce the correct code:
https://news.ycombinator.com/item?id=12890429
But also see the other comments where some question if it realy works across the gcc versions.
C and C++ blame the victim - as do, in practice, compilers for them - by labeling what they've done "undefined behavior" and telling you to do better. I'm kind of sick of C and C++ too. Plenty better than I have attempted to argue the case for optimizers to hold back and behave saner, to stop their abuse. They have failed. I've done plenty of arguing against choosing C or C++ for projects that do not need it. I have failed. I can educate on undefined behavior, that victims may attempt to avoid and combat their abuse. Maybe someday they will break the cycle, and I will have had a hand in enabling them.
While perhaps ogoffart does not perfectly outline that maybe the language is at fault for some UB, ogoffart's links make the case. TIL about yet another source of undefined behavior:
>>> An unmatched ‘ or ” character is encountered on a logical source line during tokenization.
>> With all due respect to the C standard committee, this is just lazy.
My understanding is that this:
int main() { return !"
If only they did that. But no, they instead label what they've done "undefined behavior", and silently perform optimizations that may or may not break their program entirely. Double emphasis on silently.
> The alignment bug here is such an example.
It is not since it allows vectorisation. The error was to assume that what one writes in C translates directly to assembly.
It's a fact of life that not all syntactic forms will have meaning. What's sqrt(-1)? Trick question, There's no meaningful answer (in terms of real numbers alone)! Why should anyone specify if it crashes the program, returns 0, throws an exception, etc.? Who cares? garbage in, garbage out.
Another example, "the floor had a pretty day with his melted spaceship" that is a grammatically well formed sentence but what does it mean? Don't answer that!
I agree, actually. They just went too far. Too many things are undefined for no good reason. Even sqrt(-1) is debatable, by the way: if your platform provides an efficient way to trap, it should probably trap, and the compiler should not assume it will never happen.
And if you want crazy optimizations, consider introducing unsafe assertions into the language. That is, arbitrary boolean expressions the compiler is allowed to assume will always return true.
I'd prefer it if the decision to trap or not were an option to the compiler.
It would be nice if there were a GUARANTEE() macro so that the programmer could specify conditions that would never happen even in a production build like: GUARANTEE(n >= 0). Also if trapping was enabled, it would trap at runtime. This is a nice post about that idea http://blog.regehr.org/archives/1096
Engineering is full of needlessly awkward tools that end up being misused because of their useless warts. Every time that happens, the engineer that uses it is kind of a victim. And of course, there are the end users, who end up irradiated, spied upon, or robbed because of a technical failure allowed by needlessly unsafe tools.
(Big emphasis on "needlessly". Sometimes, the requirements are so stringent that only the unsafe tools do the job. Embedded environments, AAA games, or video encoders come to mind. Most of the time though, safer, less efficient tools are more than enough.)
Of course we have to conform to the standard, however crazy. The only alternative is forking the language itself.
#include <stdlib.h>
#include <stdint.h>
typedef uint32_t __attribute__((__aligned__(1))) uint32_t_unaligned;
uint64_t sum (const uint32_t_unaligned * p, size_t nwords)
{
uint64_t res = 0;
size_t i;
for (i = 0; i < nwords; i++) res += p [i];
return res;
}
And I'm not sure how exactly this code will fail on architectures which don't support unaligned uint32_t.
[repr(C)]
struct Something
{
pub foo: f32,
pub _alignment: [EightBytes, 0]
}
It's not optimal but you can always use libc::posix_memalign()
[repr(C)]
struct StructA
{
pub foo: f32,
_alignment: [SixteenBytes, 0]
}
[repr(C)]
struct StructB
{
pub foo: f32,
_alignment: [ThirtytwoBytes, 0]
}
[repr(C)]
struct StructAPadded
{
pub foo: f32,
_padding : TwelveBytes;
} struct One {
foo: u8,
}
struct Two {
bar: u16,
}
struct Three {
foo: u8,
bar: u16,
}
struct Four {
foo: u16,
bar: u16,
}
fn main() {
assert_eq!(1, std::mem::size_of::<One>());
assert_eq!(2, std::mem::size_of::<Two>());
assert_eq!(4, std::mem::size_of::<Three>());
assert_eq!(4, std::mem::size_of::<Four>());
}It seems that at present, if you want to generate an unaligned SSE2 load/store, you have to rely on modern memcpy (spelled copy_nonoverlapping in Rust) optimization. See the first reply to https://internals.rust-lang.org/t/unaligned-simd-sse2-in-par...
If the strictest (largest) alignas on a declaration is weaker than the alignment it would have without any alignas specifiers (that is, weaker than its natural alignment or weaker than alignas on another declaration of the same object or type), the program is ill-formed.
Also, using alignas on pointer variable will probably specify alignment of the pointer itself, not the pointed object. I suppose you can create a wrapper class around int with alignas(32) and specify the pointer as pointing to that, but this is going to be nasty given that you can't derive from int and have to write all those operators by hand.
struct S { short f[3]; } __attribute__ ((aligned (8)));
.L13:
movdqa (%r8), %xmm2
...> "The aligned attribute can only increase the alignment; but you can decrease it by specifying packed as well. See below."
but gcc-6.2 documentation adds:
> "When used as part of a typedef, the aligned attribute can both increase and decrease alignment, and specifying the packed attribute generates a warning."
FWIW, Clang has supported reducing alignment in this fashion for a few years now.
[1] it's possible (likely, even) that it has been working for a while but the documentation was only recently brought up to date; I haven't investigated too carefully.
#define __packed2__ __attribute__((packed, aligned(2)))
/*
* SystemV FS comes in two variants:
* sysv2: System V Release 2 (e.g. Microport), structure elements aligned(2).
* sysv4: System V Release 4 (e.g. Consensys), structure elements aligned(4).
*/
struct sysv2_super_block {
__fs16 s_isize; /* index of first data zone */
__fs32 s_fsize __packed2__; /* total number of zones of this fs */
At least that would be a failure at compile-time, rather than run-time.
And yes, it's a compile-time failure, which is great. My comment should not be read as criticism at all (though I would likely use `uint16_t`, as the OP says the code is intended to work with [presumably aligned] 16-bit words).
Data written as int may be read as char, but going the other way is usually a standards violation. (an exception being if you had used char to implement a memcpy-like function, but in that case you should expect compiler bugs to bite you)
And yes, as for other casts, I'm well aware that they cause problems.
Unless __aligned__ or __packed__ is documented as also relaxing the strict aliasing rules - if such documentation exists, I haven't found it - there's still undefined behavior from the strict aliasing violation by type punning size_t <-> uint32_t.
Bad alignment is not the only possible "bad" optimization compilers can apply that relies on this being undefined behavior. For example, they may mistakenly assume a size_t value in memory can be cached in a register, and not reloaded from memory when it calls code that uses only uint32_t* pointers, because in a standards compliant program these cannot be used to modify size_t values.
You need __may_alias__ as well.
#include <stdlib.h>
#include <stdint.h>
uint64_t sum (char *p, size_t nwords)
{
uint64_t res = 0;
size_t i;
for (i = 0; i < nwords; i += 8) {
uint64_t tmp;
memcpy(&tmp, &p[i], sizeof(tmp));
res += tmp;
}
return res;
}Deal breaker: your memcpy invocation requires a sufficiently smart compiler to convert into normal unaligned load on x86 and seems to prevent GCC autovectorization. In this case OP actually didn't want vectorization, but in general it happens that such workarounds confuse compilers and produce worse code.
Vectorization is in general not applicable here since it usually requires aligned memory... not all implementations do, but most. In any case, benchmarking is more appropriate than armchair optimizing.
I prefer to just add alignment specification and move on, assuming I don't care about portability. If portability matters, reread my original post ;)
I'd call compiler specific alignment attributes more arcane, convoluted, and susceptible to future bugs.
Vectorization isn't a panacea. You need to benchmark to be sure, lacking that I expect GCC to be better at optimizing code than you. If you disagree, please manually write a vectorized one that handles non-aligned addition and post your results :)
Unfortunately a while back the OCaml compiler generated non-aligned stack frames. Which is no problem for pure OCaml code and even saves a little bit of memory. However if the code called out to C, then sometimes and unpredictably (think different call stacks, ASLR) the C code would crash. That was a horrible bug to track down:
The stack alignment restriction is also annoying when handwriting Asm, although fortunately it's only when calling into other C libraries that it needs to be minded.
I'm not up to date on the latest mitigation strategies, but the hairball of cache implications caused by unaligned access make me suspicious of that claim. If you (or your compiler) signal that you want performance by using vector instructions, I think it's completely fair for Intel to demand that you pay attention to alignment.
https://news.ycombinator.com/item?id=12718625
Presumably due to the hairball of cache implications, as you put it.
But it also is true that the choice of aligned/unaligned instructions makes no difference if the array is aligned.
Because it wasn't worth spending die space on that as opposed to other things that matter a lot more for performance, presumably.
> It's not well known that Linux/x86 stack frames must always be 16 byte aligned.
After all, if you have to understand the underlying instructions executed in order to fix the problem, why not stop trying to make the compiler emit the "right" instructions and just write them yourself?
(Language lawyers: is casting a char* to a uint32_t* actually defined behavior? For unaligned data?)
> 6.3.2.3 A pointer to an object or incomplete type may be converted to a pointer to a different object or incomplete type. If the resulting pointer is not correctly aligned for the pointed-to type, the behavior is undefined. Otherwise, when converted back again, the result shall compare equal to the original pointer. When a pointer to an object is converted to a pointer to a character type, the result points to the lowest addressed byte of the object. Successive increments of the result, up to the size of the object, yield pointers to the remaining bytes of the object.
The fist sentence is what is in play over here. If you have undefined behaviour in your program anything can happen.
The memcpy solution is what I've seen throughout the industry when you are trying to cast between non-trivial types.
My thoughts exactly. It's especially true for something like this tiny sum-loop, where amusingly enough the "portable C" and C++ versions are longer than the sequence of Asm instructions itself! All the other typical arguments about maintainability etc. don't apply here either --- IPv4 checksum calculation has been defined and implemented in billions of other devices, and is never going to change.
Although what I think Intel could've done is added an optimised REP ADDSW ;-)
So then better drop down to Assembly, or if there is no need for compiler portability, intrinsics.
You don't. You can simply write the code without casting pointers. Sticking to char* will give you straightforward, working, annoying-looking code.
C is surprisingly poor-suited for doing input and output with data structures.
static uint32_t read(const char *p, size_t index) {
uint32_t out;
memcpy(&out, &p[index * sizeof out], sizeof out);
return out;
}
This has a cost of unaligned accesses on non-x86 platforms (a quite big at that), but considering the original code didn't work on these at all, it's an improvement.
static uint32 read(const void *ptr) {
const uint8 *b = (const uint8 *)ptr;
return (b[3] << 24) | (b[2] << 16) | (b[1] << 8) | (b[0]);
}On dumb compilers it may be faster if a few bitops happen to be faster than a call to memcpy. Which sounds plausible.
On modern compilers it boils down to whether your compiler can optimize either one or both of these patterns into a single unaligned load. GCC for example certainly optimizes 4 byte memcpy, probably already at -O2, but whether it recognizes your pattern I don't know. Compile it and check.
Is that a clever pun or Freudian slip?
Actually two out of three inet checksum implementations in lwIP have this bug [1].
And like the problem discovered in the article, this is NOT theoretical. I have personally seen code "miscompiled" due to strict aliasing violations (in that case, packed structures were involved).
I think the only way to do this "manual alignment handling" is to use assembly, either by writing the entire thing in assembly, or using inline asm sections for doing the individual 32-bit memory reads/writes.
Funny story... When I was looking for a fast inet checksum implementation to use for an embedded ARM project, I took the one from RTEMS, which is written in C with much inline asm, and like the lwIP code, it has strict aliasing violations (and also problems compiling correctly with clang). What I did was, compiled it to assembly with gcc once, then included this compiled assembly in the source code. Assuming that this was compiled correctly, I don't need to be afraid of future compiler change breaking it.
[1] http://git.savannah.gnu.org/cgit/lwip.git/tree/src/core/inet...
http://cellperformance.beyond3d.com/articles/2006/06/underst...
"It depends."
Thus an aligned read of a 32-bit integer took one memory access; an unaligned read took two, which took twice as long. This killed performance.
Rather than quietly performing badly, the processor threw an exception to encourage you to fix your code.
The ARM2 worked a bit differently. It ignored the bottom two bits of the address when it read a value from memory. When the read was complete the value was rotated by the value of the bottom 2 bits multiplied by 8. This had the effect of putting the byte referenced by the full address in the bottom 8 bits of the 32-bit register. A flag in the instruction let you optionally mask off the top 24 bits to simulate a byte read.
Folly has a generic `loadUnaligned()` that uses this trick: https://github.com/facebook/folly/blob/5d52fb8c30e567403b8cc...
I suggest this because it would be portable without any compiler specific stuff.