8 ms·
A bug story: data alignment in C on x86 (2016)
- deleted 8y ago[deleted]
- ericand 8y agoAlso posted on reddit which has some interesting discussion: https://www.reddit.com/r/cpp/comments/5bn8jx/a_bug_story_data_alignment_on_x86/ https://www.reddit.com/r/cpp/comments/5bn8jx/a_bug_story_dat...
- scottlamb 8y agoCan't this also segfault by overreading across a page boundary? It's assuming "size" is >= 20 and is a multiple of 4. That might be true for all valid headers, but at least in this snippet, there's no comment or anything stating the precondition that callers ensure the headers are valid. That's a(nother) bug. If it's not true, it will read too much data. This means producing the wrong result. It also could make the read happen to cross a page boundary into space that isn't mapped into the process's virtual address space.
- klodolph 8y agoDepending on which page boundary, increasingly severe exceptions will be raised, but it is typical for an OS to service those exceptions by performing the operation and jumping back into the code… maintaining the illusion that it worked. This is what happened to all unaligned accesses in the PowerPC 601 -> 603e transition in ~1995. Game developers writing their own “optimized” blit code suddenly found that every single unaligned access on the 603 would succeed, but it would go through an ISR to get there! I feel for these kind of routines, either write it in dumb, straightforward C code and just use -O2 or -Os, or make an assembler version—possibly just a saved copy of the compiler’s output, but that’s enough to completely kill any interprocedural optimization. Trying to write ultra-optimized C code gives me a bit of a headache, unless it’s something that you can express straightforwardly as SSE intrinsics or something like that. You end up going through contortions to satisfy constraints imposed by the language which aren’t imposed by the machine. > It's assuming "size" is >= 20 and is a multiple of 4. That might be true for all valid headers, but at least in this snippet, there's no comment or anything stating the precondition that callers ensure the headers are valid. That's a(nother) bug. That’s too much of a reach to call it a bug. The IP header’s size is measured in multiples of 4 bytes, there is simply no way to encode a header which is not a multiple of 4 bytes. It becomes a question of how gracefully you want to handle true garbage being passed into the function… at best this is a matter of style. Should strlen() call assert(p!=NULL)? These days with asan, I’m not so sure that writing these assert() is the best way to spend my time.
- scottlamb 8y ago> Depending on which page boundary, increasingly severe exceptions will be raised, but it is typical for an OS to service those exceptions by performing the operation and jumping back into the code… maintaining the illusion that it worked. I'd expect crossing a boundary between two valid pages to be fine; that's just part of making unaligned accesses work. I'm talking specifically about an unmapped page. I don't have any data, but I'm pretty confident access to an unmapped page (such as null pointers) is a much more common source of SIGSEGV in general than unaligned access, to the extent that most programmers probably don't even know the latter is a possibility. > That’s too much of a reach to call it a bug. The IP header’s size is measured in multiples of 4 bytes, there is simply no way to encode a header which is not a multiple of 4 bytes. I take a pretty hard stance on this kind of thing. The function might be used in a way you're not expecting. The article mentioned the IP frames can be read from a file. Maybe they're in some record-delimited format that states length in bytes, and that's the length that gets passed in rather than the original one. Redundant framing information like that is pretty common I think when you're using some general-purpose code (a library that handles a variety of record formats as well as some functions that operate on specific types like IP frames). Those records could get corrupted, even maliciously so; callers probably expect then to get back a nonsense result then but not an out-of-bounds read. Or there could be a bug in the logic that decodes the header's length. By itself that won't cause memory errors, but combined with this assumption it does, and so I'm uncomfortable with the assumption being implicit. I think a lot of C code's memory safety is dependent on this sort of implicit assumption that rots over time (if it was ever correct to begin with), and every time I see it I prefer memory-safe languages a little more. Working in a language (Rust) that requires you to explicitly annotate such places with "unsafe" and have your public interfaces be "sound" (have it be impossible for safe code to cause the unsafe code to do the wrong thing) makes this more clear to me. > Should strlen() call assert(p!=NULL)? If it behaves in a surprising way when called with NULL, it should mention that case (either in an interface comment/manpage or via explicit assert). In practice on modern machines strlen raises SIGSEGV. [1] When folks see a SIGSEGV from strlen, they probably think wild pointer or missing terminator and will figure out exactly what happened before long. [1] Although I imagine it's actually undefined behavior according to the C standard, so now I wonder if some compiler does / my compiler will someday do something more strange, and I'm sad.
- caf 8y agoIt does actually say that: > In addition, the size can never be less than that – this is checked before calling this function.
- pcwalton 8y agoIn Clang, you can get the adc instruction using __builtin_addcl (and similar), but the compiler isn't that great of making optimal use of it. A few minutes of playing around got me [1], which isn't very good code. [1]: https://godbolt.org/z/hTzECo https://godbolt.org/z/hTzECo
- dronemallone 8y agoWhy not use the routines from the Linux kernel, which are battle tested? https://elixir.bootlin.com/linux/latest/source/arch/x86/include/asm/checksum_64.h#L45 https://elixir.bootlin.com/linux/latest/source/arch/x86/incl... Or even NetBSD: http://ftp.netbsd.org/pub/NetBSD/NetBSD-current/src/sys/net/npf/npf_inet.c http://ftp.netbsd.org/pub/NetBSD/NetBSD-current/src/sys/net/... EDIT: freebsd: https://github.com/freebsd/freebsd/blob/master/sys/netinet/in_cksum.c https://github.com/freebsd/freebsd/blob/master/sys/netinet/i... openbsd: https://github.com/openbsd/src/blob/master/sys/netinet/in4_cksum.c https://github.com/openbsd/src/blob/master/sys/netinet/in4_c...
- ahmedalsudani 8y agoIt’s impressive of you to dig out all those implementations! Do you have a trick for navigating codebases?
- saagarjha 8y agoNot to downplay their achievements, but it seems to me that they just dug up the implementations in the IP stack for each OS.
- dronemallone 8y agoThat's true, pretty easy to do once you look in the "net" or "inet" or "netinet" folders and then look for ipv4.
- valarauca1 8y agoThe first provided link is extremely useful as it lets you jump to declarations, files, and line numbers in the current Linux Kernel source. For digging up kernel code snippets it it is extremely useful. Also like the kernel is fairly sanely laid out. Its a project with literally hundreds of contributors so keeping the code base organized is important.
- cryptonector 8y agoI mean, there are LXR and OpenGrok indexes of the various kernels... E.g., http://src.illumos.org/source/ http://src.illumos.org/source/ https://elixir.bootlin.com/linux/latest/source https://elixir.bootlin.com/linux/latest/source etc... If you make a local clone, then cscope is great.
- firethief 8y ago> I didn’t have to bother about portability This is where it became evident that the class of bug was going to be "assumed the language's machine model gets out of the way if you know the target platform". It's funny how easily we all forget about the nasal demons, but UB != implementation defined.
- tom_ 8y agoBut it could by treated equivalently in many cases. The standard, after all, imposes no restrictions. It might not explicitly say that the implementation could behave like that - I don't know what phrase would work - "a documented manner characteristic of the platform", something like that - but by imposing no restriction it leaves the option open. Which is a large part of why people complain.
- gok 8y agoThat’s not accurate in this example. In C, uint32_t* literally means “a 4 byte-aligned pointer to a 32 bit unsigned int” on every platform. The author wasn’t getting bitten by UB so much as misunderstanding how pointer types work in C.
- saagarjha 8y agoThe undefined behavior was that casting an uint32_t * from a char * requires the char * to have pointed to a uint32_t * before, which is not possible for an unaligned pointer.
- jcranmer 8y agouint32_t literally means "an unsigned integer type with width 32 [bits] and no padding bits" (I'm quoting from the C standard here). It does not imply anything about what the alignment is; a 16-bit processor may well defined the alignment of the 32-bit unsigned integer type to be 2 bytes instead of 4. The incorrect logic that causes the bug is thinking "I know that I can do X in assembly, therefore the naive translation to C should let me do the same thing." The idea that C is portable assembler is very widespread, but it is quite wrong, and it has been wrong for decades. A lot of people complain when they find out that the compiler doesn't work when they to write what is effectively assembler in C syntax, but quite frankly, many more people (including many of those who want it to be portable assembler) would complain if the compiler were to actually treat all C code as portable assembler.
- camgunz 8y agoHey look, another strict aliasing bug.
- dmitrygr 8y agoWhy the surprise? x86 ABI says that a uint32 shall be 32-bit aligned. The fact that CPU can cope with others does not mean ABI allows it. Compiler complies with ABI and assumes your uint32* is 32-bit aligned.
- crististm 8y agoI assume because ABI is just a convention for application interoperability. Hardware interface was the problem here. You can ignore ABI if you are standalone. But you can't ignore the CPU.
- dmitrygr 8y agoCompiler sees "function" and understands "ABI says that pointer is 32-bit aligned, I can count on that because whoever calls it will also be ABI compatible and make it so"
- crististm 8y agoYou confirmed my interoperability claim with your answer - whoever calls. Consider just the main function. You are free to ignore the ABI there but you still need to obey the cpu spec.
- dmitrygr 8y agoNot really. If main ignores abi for example by not saving callee saved regs, you'll crash. Ignoring abi is never safe unless your entire project is written in asm
- Asooka 8y agoA note of warning: memcpy and memmove are not optimized away on msvc and icc. That is, every call to those functions is always a function call. Contrast to gcc and clang which always inline those calls even in no-optimizations builds. To do away with memcpy calls, you can use this: _Bool check_ip_header_sum(const char* p, size_t size) { struct Chunk { char arr[4]; }; const Chunk* chunks = (const Chunk*)p; union { Chunk chunk; uint32_t n; } helper; uint64_t sum=0; for (size_t i=.....) { helper.chunk=chunks[i]; sum+=helper.n; } ........ } Technically speaking, going through a union like that is also undefined behaviour, however this is used everywhere in the Linux kernel, so both GCC and Clang will support it indefinitely, while MSVC is very conservative anyway, so you can rely on it supporting it as well. There is pretty much zero reason for the compiler to produce garbage code here. Note also that you can't cast p to the union type directly, because the union type has uint32_t alignment, so you have to do it this way. And you have to go through a struct, because you can't copy-assign arrays... Anyway the union+chunk trick seems more readable to me as well, but that's down to personal preference.
- Karliss 8y agoWhen was the last time you checked that msvc and icc always use a function call form memcpy? At least the latest versions of msvc and icc can replace memcpy with appropriate move instruction. You can see here https://godbolt.org/z/BX0Wya https://godbolt.org/z/BX0Wya that msvc 2017, msvc 2015, icc 18.0 and even icc 13.0.1 used a mov instruction for memcpy to uint32 instead of function call.
- userbinator 8y agoI believe even MSVC6 will inline memcpy() (and a few others), but it has to be enabled with one of the optimisation switches (intrinsic functions.)
- Asooka 8y agoOk, I stand corrected. However, at lower optimisation levels they do not inline memcpy calls, which might matter for you. It's never fun if the debug build is 10 times slower in a hot function...
- saagarjha 8y agoThe correct way to do this is to use memcpy, as was pointed out in the article. Given a half-decent compiler, it will give the most portable, standards-compliant, and often fastest code. Please just use memcpy instead of limiting yourself with "defined (__GNUC__) && (defined (__x86_64__) || defined (__i386__))".
- mjg59 8y agoThe article points out that, for the author's use case, memcpy doesn't generate the fastest code.
- saagarjha 8y agoI qualified my statement with an "often" for a reason ;) But looking back at the article, it seems like the author is complaining that the compiler used an unaligned move instead of an aligned one–but based on the code they wrote, this seems necessary. The compiler has no knowledge of any data alignment (how would it know that the data is always aligned without telling it?), so it emits conservative instructions.
- mjg59 8y agoNot really - the initial implementation (without memcpy) resulted in an aligned move, and hence the crash. The memcpy implementation results in an SSE-based unaligned instruction that does the right thing, but is slower (in the specific case that the author cares about, ie cases where the loop will rarely trigger and will basically never go through more than three iterations) than not using SSE. There's no real way to hint to the compiler that this is the case, so the author chooses to disable the use of SSE in that function on architectures that support it - this way they can use memcpy() (for correctness) and still get the hoped for code generation.
- valarauca1 8y agocode sample + name (and already dealing with SIMD alignment issues) told me what the problem is. Pointer casts are ALWAYS bad in C. Try to avoid them. Reply and down vote you old hat C programmers who will defend this. Your old practices are actively harmful to people learning the language.
- rightbyte 8y agoHow do you prefer to use e.g. malloc?
- icedchai 8y agoYou don't need to cast there... malloc returns a void*.
- AnimalMuppet 8y agoWhich you are going to use how? Don't you have to cast it to something to be able to use it?
- deathanatos 8y agoNo, you don't. The following, int *i = malloc(sizeof(int)); is valid C, and will compile just fine. I think it's considered good form, too, as the cast doesn't really add anything not already present, and might even drift out of date with the surrounding code. (And just gets in the way of legibility.) IIRC, it is not valid C++. But malloc()/void * is somewhat rarer to find there, as you have better options.
- userbinator 8y agoAlignment issues are not only relevant for RISC processors. SSE makes them valid for x86, too (in both 32 and 64-bit mode). Requiring alignment with certain SSE instructions was the original poorly-thought-out misstep that lead to this bug. One of the basic principles of CISC is to implement instructions flexibly in hardware even if it requires microcode, then optimise that hardware to gain a performance advantage with each new generation. If the original SSE instructions worked fine with unaligned data, perhaps being slower in such cases like all the other instructions did, then no expectations would be violated and everything would've worked out nicely. The fact that the explicitly unaligned version is now actually slightly faster in the benchmarks shown (because there doesn't need to be extra code to do alignment) is evidence enough that the original decision to have separate aligned/unaligned versions was really shortsighted. Very wide memory buses and multistage pipelines make alignment pretty much a non-issue. The other big point this article doesn't mention is that rather than fighting with the compiler, if you already know what instructions you want, it would be better to write the Asm directly. For short sequences like these the Asm is going to be even clearer and shorter than "truly portable" C. In practice there really aren't that many architectures your code is going to run on.
- pif 8y ago> Suddenly, our x86 behaves just like RISC: it crashes when a pointer to uint32_t is not aligned by 4. No, my friend, you're wrong! Neither x86 nor RISC know anything about a pointer to uint32_t! > The transformation it performed on the program contradicts to the usual expectations of a programmer who is used to x86. Sorry, but only poor programmers have any expectations related to a CPU architecture when dealing with C, or any other high-level language! Your compiler did the right thing in assuming you had done the right thing. If the compiler had to protect you against your own errors, it would have to give up providing valuable support to those fellow programmers who do their homework correctly.