8 ms·
GCC always assumes aligned pointer accesses
- ajross 7y agoThe complaint isn't about alignment at all, it's that the optimizer assumes that two pointers to the same basic type cannot overlap in memory. The generated code is correct except for the fact that the two arguments are distinct pointers to the same three bytes in memory. I believe this behavior is actually specified in the standard, actually, in the same section that defines the aliasing rules.
- loeg 7y agoYes, this is the compiler optimizing UB due to aliasing, not due to alignment.
- not2b 7y agoYes, the optimization assumes that given two pointers to int, either they point to the same int, or they point to distinct, non-overlapping ints. Under that restriction the result is guaranteed to be 1. It's allowed to do so by the standard because those are the rules. C was portable assembly back in the early 1980s. The result was that it was crushed in performance by Fortran for scientific codes, and most of the difference had to do with assumptions the compiler could make about aliasing (or the lack of it). This was fixed by the first ANSI C standard (finalized in 1989). Yet I still see people who weren't even born then, or were young children then, talk as if C is supposed to be "portable assembly". It isn't.
- naniwaduni 7y ago> The result was that it was crushed in performance by Fortran for scientific codes, and most of the difference had to do with assumptions the compiler could make about aliasing (or the lack of it). This was fixed Calling it "fixed", as if it were a problem of the language rather than programmers' expectations, is a rather slanted view of the history.
- pascal_cuoq 7y agoCould you clarify which clause of the C standard you are referring to when you say “due to aliasing, not due to alignment”? I make sense of the C standard for a living (this is literally my day job) and I do not see what clause of the C standard you are referring to. It would be very useful to me to know which clause you are referring to, and I would be eternally thankful.
- loeg 7y agohttps://news.ycombinator.com/item?id=22911286 https://news.ycombinator.com/item?id=22911286
- pascal_cuoq 7y agoSo the clause about assignment? Thanks, that was helpful.
- Spivak 7y agoIsn’t that in practice the same as an alignment problem? Can you have two ints overlap without a misaligned access?
- deleted 7y ago[deleted]
- ajross 7y agoNo, but you can have two otherwise-perfectly-legal aligned accesses that overlap (consider two long longs on a 32 bit platform), and that's disallowed by the standard.
- eqvinox 7y agoThe compiler would know that the alignment is smaller than the type itself, which would disable the optimization mentioned in the post.
- ajross 7y agoIt literally cannot. The function in the linked article, that takes two pointers, must be compiled in isolation. If it needs to depend on alignment or overlapping, it needs to emit code to check it. And the standard does not require it to, nor do typical users want that. It's true that fancy tricks like LTO can make that kind of behavior visible to the optimizer, but the standard predates that kind of magic by several decades.
- eqvinox 7y agoThat's not what I meant. On an architecture where "long long" is 8 bytes, but only has a 4 byte alignment requirement, the compiler knows this, and knows that 2 pointers of type "long long * " may overlap. Therefore it would disable the optimization. (Except the pointers still aren't supposed to overlap, but...)
- bonzini 7y ago
- __s 7y ago-fno-strict-aliasing: https://stackoverflow.com/questions/98650/what-is-the-strict-aliasing-rule https://stackoverflow.com/questions/98650/what-is-the-strict... Torvalds rant: https://www.yodaiken.com/2018/06/07/torvalds-on-aliasing https://www.yodaiken.com/2018/06/07/torvalds-on-aliasing edit: I misread the parent as wondering about a compiler flag
- eqvinox 7y agoIrrelevant to the post, even without strict aliasing the compiler will assume pointers/objects are properly aligned.
- hedora 7y agoDo you have an example where the compiler generates bad code that doesn’t involve misaligned aliases? Many programs rely on misaligned access, and features like pragma packed do too. I doubt they’ll be able to break all of that legacy code.
- eqvinox 7y ago> Many programs rely on misaligned access, and features like pragma packed do too. I doubt they’ll be able to break all of that legacy code. It's already broken. You're just not seeing it on x86. (Not sure how tolerant ARM is.) I work in network software engineering, i.e. PowerPC used to be a common architecture. Those never accepted misaligned pointers (albeit you could of course trap the misalignment exception and emulate the access, or print a backtrace to identify the location.) Really this is a problem caused by the "common case" (x86) being permissive in what it accepts, creating fallout further down the line if you ever need the code to run on something less permissive. [Edit: actually, oops, it's not PowerPC; those are relatively permissive too. Pretty sure DEC Alpha and m68k are restrictive.]
- loeg 7y agoI think newer aarch64 allows misaligned access to regular memory.
- eqvinox 7y ago> I believe this behavior is actually specified in the standard, actually, in the same section that defines the aliasing rules. It is, indirectly, since pointers are required to point to valid objects, and valid objects are required to be correctly aligned.
- pascal_cuoq 7y agoI have heard this reaction to this article a lot, but sorry, there is nothing in the C standard that says that objects should not overlap, except a rule that only apply to “lvalue = lvalue;” assignments and is not relevant here. Plus on a some 32-bit ISA, a long long and a double only need to be aligned to 32-bit boundaries, so I note that in the made-up C rules that you are referring to, “basic type” is not very well defined. > I believe this behavior is actually specified in the standard, actually, > in the same section that defines the aliasing rules. The strict aliasing rules are here: https://port70.net/~nsz/c/c11/n1570.html#6.5p7 https://port70.net/~nsz/c/c11/n1570.html#6.5p7 Go ahead and point to the rule that says that “basic types” cannot overlap with themselves.
- ajross 7y agoI genuinely can't follow you completely, but half suspect you're violently agreeing with me. Are you saying the optimization in the linked article is, or is not, in violation of the standard? Edit: this is the text I was remembering, from 6.5.16.1 ("Simple Assignment"): "If the value being stored in an object is read from another object that overlaps in any way the storage of the first object, then the overlap shall be exact and the two objects shall have qualified or unqualified versions of a compatible type; otherwise, the behavior is undefined.". That pretty much matches exactly what I was saying: compilers are free to assume that basic types don't overlap, because if they do then any generated code will be undefined behavior anyway.
- pascal_cuoq 7y ago6.5.16.1 is the “rule that only apply to “lvalue = lvalue;” assignments and is not relevant here” It does not apply to “lvalue = 1;” or to “lvalue = 2;”, which are the two relevant assignments in the example in the article. For context, I think I made it clear in the article that the program being discussed is UB, and therefore that the compiler is not to blame. But since I wrote this article, I have had people telling me “The complaint isn't about alignment at all, it's that the optimizer assumes that two pointers to the same basic type cannot overlap in memory”. My reply to this specific sentence is: No. You are wrong. There are no words in the standard that say that “basic types cannot overlap in memory”. There is not even a notion of “basic type”. There are clauses about pointer alignment, that are explicitly cited in the article, and there are clauses about strict aliasing, that are shown in the article not to be the reason for GCC optimizing the program by using -fno-strict-aliasing. There are no rules about “basic types not overlapping” in the C standard. You only think there are. Or please cite them. (6.5.16.1 is a rule about assignment, it only applies for the code pattern lvalue1 = lvalue2;)
- LennyWhiteJr 7y agoThis isn't just an issue with GCC but embedded compilers as well. On embedded systems its common to work with packed data structures to maximize serial protocol efficiency. Lets say you have a packed structure with a type of struct MyPackedStruct { uint8_t byteValue; uint32_t intValues[5]; } Normally a compiler would add 3 extra bytes between the uint8_t value and the uint32_t array to keep alignment of the int array, but that won't be the case if you force it to be packed. This results in uint32 values that span two word boundaries. If you access one of those array values in code directly, the compiler is smart enough to perform 2 separate memory reads and combine the resulting value so you don't have to really think about it. But if you do something like this: uint32_t *intValues = myPacktedStruct.intValues; The compiler allows this, but the resulting intValues pointer loses all packed awareness, and trying to dereference that pointer will result in an unaligned memory access exception. Moral of the story - only use packed data types when serializing/deserializing a protocol stream. Avoid using packed data types 'at rest', because it can cause subtle issues like this. The downside is that it results in extra parsing work when converting between packed and unpacked types.
- loeg 7y agoOr if you're going to use packed structs, pass around a pointer to the full struct instead of to a member.
- Asooka 7y agoI would argue that this is a bug and should probably be fixed in a future C/C++ standard that allows declaring misaligned types. Something like "members of a packed struct have [[aligned(1)]] attribute and cannot be converted to a pointer type with different alignment except with a reinterpret_cast", so you'd have to do uint32_t [[aligned(1)]]*intValues = myPackedStruct.intValues; Would be nice if we also got e.g. float/intNua_t for unaligned types. Any code that gets broken by this change was broken to begin with.
- MaxBarraclough 7y agoForcing packing of a struct isn't possible in standard C, only through compiler extensions. Presumably that's the reason: you have the strange situation where it's legal (and well-defined) to read the member, or to write it, but to take its address and perform a read through that pointer, causes undefined behaviour. I believe that situation is impossible in standard C.
- eqvinox 7y agoNo. [as in: this isn't about GCC.] The C standard requires that pointers generally be created from referencing a valid, existing object. A misaligned integer is not a valid "object", thus the compiler may assume that all pointers to ints are aligned (to 4 bytes.) https://en.cppreference.com/w/cpp/language/pointer https://en.cppreference.com/w/cpp/language/pointer Every value of pointer type is one of the following: - a pointer to an object or function (in which case the pointer is said to point to the object or function), or - a pointer past the end of an object, or - the null pointer value for that type, or - an invalid pointer value. Relatedly, `malloc` is required to return a pointer with the largest alignment of any type ("suitably aligned to hold an object".) Edit/Add: that's C++ in the link above, but it's the same in C. You can get a pointer from either a valid static/stack object, or malloc, which is "max" aligned. Either way it's required to point to a valid object, which includes correct alignment. If you implement your own memory management / allocator, it's also your responsibility to meet these same alignment requirements. https://en.cppreference.com/w/c/language/object https://en.cppreference.com/w/c/language/object
- dooglius 7y agoWhy "no", you're agreeing with the conclusion
- eqvinox 7y ago"No, it's not GCC's fault / doing something weird." :) But, yes. Edited to clarify. FWIW this isn't a new problem either. If you wrote some C code in the 90ies using misaligned pointers, and then tried porting it to, say, a DEC Alpha, you'd get a SIGBUS in your face on first dereferencing such a pointer.
- guenthert 7y agoMC68k (anno 1979) didn't like misaligned memory access either and I have no reasons to believe that this started with Motorola. But yes, it's always fun watching a new generation falling into the old traps.
- hedora 7y agoThe example of bad gcc behavior was essentially type punning, which is well-known to cause trouble. Is there an example where things break on misaligned access to non-overlapping objects?
- eqvinox 7y agoMisaligned accesses, in general, without any qualification, can earn you a SIGSEGV or SIGBUS. It's mostly x86 that's being very tolerant here; other architectures are much less forgiving to varying degrees. That's also why this rule is in the C standard to begin with. Misaligned accesses need different / multiple instructions on some of these architectures, making them significantly more expensive. So the decision was made in favor of assuming things are aligned.
- loeg 7y agoAll (or almost all) of the big architectures that have survived to this day and attempt to compete with x86 permit misaligned accesses in general purpose memory. It's true that if you threw a dart at a historical computer architecture, they would likely not be tolerated. But e.g., aarch64 tolerates misaligned access.
- twoodfin 7y agoPutting aside that gcc’s behavior is totally in line with the standard, I’d rather have a compiler (& language spec) with more effective room for auto-vectorization than support for unaligned pointers.
- notacoward 7y agoAbout 30 years ago, I was porting an Ethernet driver to the MC88K, which also didn't allow misaligned accesses. Guess what happens when you fill a page-aligned buffer with an Ethernet packet, go past the 14-byte Ethernet header, and try to read the first 4-byte value in the IP header as a single word? You guessed it: SIGBUS. Every time. The same problem existed many other places, so I had to go find all of them. Eventually I implemented an exception handler that would emulate the access, and also log an error message. For months afterward, this turned up ever more obscure cases until there seemed to be none left. Coming next: how modern programmers can't imagine a different word size or byte order. After that: different memory-ordering models. That one's really fun.
- anticensor 7y agoMixed memory order as in, a memory write stores the data in an order like 5, 7, 6, 4 instead of 4, 5, 6, 7?
- notacoward 7y agoBasically yeah, but it gets much more complicated. For example, when a write hits memory is actually not the same thing as when it's observable by some particular other processor. There might be particular rules for writes that have dependencies too. Here's some good reading material if you have a spare afternoon. https://www.kernel.org/doc/Documentation/memory-barriers.txt https://www.kernel.org/doc/Documentation/memory-barriers.txt Amusingly, it treats dependency issues as obsolete, but I worked on a processor as late as 2009 that had all of the weak-memory-ordering issues of the Alpha (because it was the same design team). We uncovered lots of missing memory barriers in the Linux kernel. Good times.
- loeg 7y agoThe modern thing is using acquire/release semantics on the variables you actually care about intra-thread ordering on, rather than full barriers, which impose a higher cost.
- unwind 7y agoSpecifying a target architecture (ISA) when compiling does not change the programming language's semantics. C is not a high-level assembly language, as pointed out in the article. So just because you know that the target CPU supports e.g. unaligned accesses does not make them suddenly valid C.
- vardump 7y agoFew seem to know x86 can generate misaligned access exception. Enabling EFLAGS Alignment Check (bit 18) flag causes an exception on any misaligned access, if the kernel has enabled this feature by setting CR0 register Alignment Mask (bit 18).
- SomeoneFromCA 7y agoYou do not need to enable anything. SSE instructions require aligned access, and will crash if used with wrong alignment, irrespective of the flag.
- vardump 7y agoI was talking about scalar 16, 32 and 64 bit alignments. You're confusing that with SSE alignment requirements. Besides, SSE has unaligned load & store as well.
- magicalhippo 7y agoI noticed this when I discovered the NVIDIA OpenGL driver used SSE without thinking. Nothing in the OpenGL specs says the buffers passed to it (think it was glBufferData) has to be 16byte aligned, but with NVIDIA it would crash with an alignment exception if they were not. The memory allocater in the language I used, Delphi, only used 4 byte alignment (32bit). They might have fixed this, this was well over a decade ago.
- SomeoneFromCA 7y agoInterestingly enough, I've just checked the code from this article (https://pzemtsov.github.io/2016/11/06/bug-story-alignment-on-x86.html https://pzemtsov.github.io/2016/11/06/bug-story-alignment-on...), linked by the OP's article, and guess what - CLANG generates code that does not crash, although it still uses SSE4.
- vkaku 7y agoWhy not? We program with a model that assumes NULL is zero, that we have a flat memory model... If it's meant to be in a certain way, it is because it would not only simplify the implementation, but also - "I hope you know what you are doing." Of course, the point of this is that if you feel strongly against it, I'd rather you submit a patch / use a fork where it shows benefit. If enough people require this behaviour, they may enable it in the tree. They're looking for more contributors, not less.