14 ms·

A bug story: data alignment on x86

151 points by sconxu 10y ago

amelius 10y ago
TL;DR: Even though most instructions of your processor (x86) allow data to be aligned on any byte, your compiler might not.
pjc50 10y ago
Well, that's pretty horrendous. Note that the naive code which just casts the input to uint16_t would work fine. I can't help but wonder if the solution to this might have been better expressed as naive implementation + platform-specific assembly implementation. 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?)
- Kubuxu 10y ago
  No it is not, the author even cited the rule from C99 himself. > 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.
- shakna 10y ago
  Going off a few answers similar to this one [0], I'd say that it isn't defined behaviour. It'll be specific to your compiler, and its optimisations. The memcpy solution is what I've seen throughout the industry when you are trying to cast between non-trivial types. [0] http://stackoverflow.com/a/4318446 http://stackoverflow.com/a/4318446
- userbinator 10y ago
  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? 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 ;-)
- pjmlp 10y ago
  People people still try hard to believe ANSI C is 1:1 to Asm, which is only kind of true when using language extensions. So then better drop down to Assembly, or if there is no need for compiler portability, intrinsics.
- Dylan16807 10y ago
  > if you have to understand the underlying instructions executed in order to fix the problem 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.
slededit 10y ago
At some point you might as well byte the bullet and just write the code in assembly.
- krylon 10y ago
  > byte the bullet Is that a clever pun or Freudian slip?
  - deleted 10y ago
    [deleted]
  - slededit 10y ago
    Accidental but I'll keep it.
koverstreet 10y ago
Attribute((aligned)) might be useful here.
rwmj 10y ago
These SSE instructions that operate only on aligned data are a pain. It's not well known that Linux/x86 stack frames must always be 16 byte aligned. GCC uses this knowledge to use the SSE aligned instructions when accessing certain fields on the stack. 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: https://caml.inria.fr/mantis/view.php?id=5700#c10779 https://caml.inria.fr/mantis/view.php?id=5700#c10779
- userbinator 10y ago
  Agreed, I've always found them unusual and perhaps a bit of a shortsighted decision --- they've been making processors seamlessly handle any alignment with perhaps an extra cycle, even for the MMX instructions, yet somehow felt the need to restrict much of the SSE ones into aligned and only provide one unaligned move. 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.
  - jjoonathan 10y ago
    > seamlessly handle any alignment with perhaps an extra cycle 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.
    - qb45 10y ago
      Case in point: a simple example of code which copies 1MB of data with SSE and slows down on misalignment: https://news.ycombinator.com/item?id=12718625 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.
qb45 10y ago
The correct solution for GCC is specifying 1-byte alignment for this particular array: #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; } Probably works on clang too and IIRC the MS compiler provides similar functionality with different syntax. AFAIK there is no portable solution. And I'm not sure how exactly this code will fail on architectures which don't support unaligned uint32_t.
- speps 10y ago
  In C++11 there is a standard for this : http://en.cppreference.com/w/cpp/language/alignas http://en.cppreference.com/w/cpp/language/alignas
  - d33 10y ago
    Anybody knows how Rust handles this problem?
    - alkonaut 10y ago
      Not sure if this is what you are asking: Last time I tried alignment in Rust I worked around the lack of explicit alignment support by adding a zero length array of the correct size to the end of the struct. Not sure if alignment support from proper attributes has landed yet. [repr(C)] struct Something { pub foo: f32, pub _alignment: [EightBytes, 0] } where "EightBytes" is a data type of size 8, to align the whole struct on 8 bytes.
      - wyldfire 10y ago
        I doubt you can count on all items being allocated at addresses that are multiples if their size. It's not optimal but you can always use libc::posix_memalign()
        10y ago
lukego 10y ago
Related Snabb experiments with IP checksum in C with automatic vectorization, C with vector intrinsics, and AVX2 assembler: https://github.com/snabbco/snabb/pull/899 https://github.com/snabbco/snabb/pull/899
Hello71 10y ago
You can probably also just pass -fno-strict-aliasing to gcc.
GlitchMr 10y ago
Compiler is allowed to assume alignment of pointers (what are you doing is creating a pointer to a value with invalid alignment, hence undefined behaviour (just creating a pointer is undefined behaviour)). The correct solution would be to read values indirectly. For example, a function like that could be used to replace every access to "q" variable. static uint32_t read(const char *p, size_t index) { uint32_t out; memcpy(&out, &p[index * sizeof out], sizeof out); return out; } A compiler can recognize this pattern, and continue to use unaligned accesses that would work. 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.
- asveikau 10y ago
  The article's final solution (sum3) is exactly this. It does a memcpy into a temporary.
- amadvance 10y ago
  Is this equivalent ? At least to me this seems a more common pattern than using memcpy(), and I expect to work better on old compilers. static uint32 read(const void *ptr) { const uint8 *b = (const uint8 *)ptr; return (b[3] << 24) | (b[2] << 16) | (b[1] << 8) | (b[0]); }
  - qb45 10y ago
    Functionally it seems equivalent, except that it doesn't work on big endian machines (assuming the ints are in native endian). 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.
novia 10y ago
I'm taking assembly right now, and we're working on our first RISC project after spending all semester working with the x86. Why does RISC crash if the bytes are not aligned?
- monocasa 10y ago
  It costs a non trivial amount of transistors (when compared with an ascetic RISC core) to load words from arbitrarily aligned addresses. 'RISC' used to be about removing those kinds of features, although the term has been a bit bastardized since then).
- kabdib 10y ago
  Depends on the processor. Some RISC systems won't generate a fault, but others will. Some of the non-faulting ones will load unaligned data correctly (even across page boundaries), while others will helpfully swizzle bytes around in the result for you, or ignore the low bits. "It depends."
- brassic 10y ago
  Early RISC processors read data from memory 32 bits (4 bytes) at a time, and these reads had to be aligned on 4-byte boundaries. This was a feature of the memory architecture, not just the processor. 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.
ogoffart 10y ago
Again someone who relies on undefined behavior. Casting pointer of wrong alignement is not a platform specific behavior, it's an undefined behavior. Relying on it is an error. 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-know.html http://blog.llvm.org/2011/05/what-every-c-programmer-should-... Another good link about that: http://blog.regehr.org/archives/213 http://blog.regehr.org/archives/213
- Sagiri 10y ago
  If a particular compiler specified that casting pointers of wrong alignments causes a segfault, it'd be perfectly acceptable to rely on that behavior. The standard would consider it UB, but that compiler has defined that behavior sufficiently. 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.
  - konstmonst 10y ago
    "If a particular compiler specified that casting pointers of wrong alignments causes a segfault" Sure it does. It says using undefined behaviour can cause daemons fly out of your nose, among other things (including but not limited to segfaulting).
    - Sagiri 10y ago
      If the semantics of casting pointers of wrong alignments were defined to be demons flying out of your nose, it would be perfectly acceptable to rely on that behavior.
  - MaulingMonkey 10y ago
    > If a particular compiler specified that casting pointers of wrong alignments causes a segfault, it'd be perfectly acceptable to rely on that behavior. 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.
ot 10y ago
If you're willing to use compiler extensions, you can avoid the memcpy by using packed structs. This can generate better code. Folly has a generic `loadUnaligned()` that uses this trick: https://github.com/facebook/folly/blob/5d52fb8c30e567403b8ccb65e5c1a159fb92d707/folly/Bits.h#L539 https://github.com/facebook/folly/blob/5d52fb8c30e567403b8cc...
pklausler 10y ago
So much HTML to complain about C working the way C is defined rather than the way the OP wants it to work! It's not that hard to write a fast ones'-complement checksum that's portable and compliant, but whining's always easier than coding.
ambrop7 10y ago
Note that even if you try to manually correct the pointer to work on aligned data (read any initial bytes via char pointer and read the rest via uint32_t pointer), you still generally have undefined behavior: strict-aliasing violation. And the worst thing here is that whether you do have a violation depends on how other code accesses the same data / how the object is initially declared. E.g., you're fine if the original declaration is char[] or uint32_t[], but not if it's uint16_t[]. Because that would entail access to the same data via both uint16_t and uint32_t, a violation of strict-aliasing. 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_chksum.c http://git.savannah.gnu.org/cgit/lwip.git/tree/src/core/inet...
- nikanj 10y ago
  For what it's worth, people like Linus seem to despise the strict aliasing optimization. https://lkml.org/lkml/2003/2/26/158 https://lkml.org/lkml/2003/2/26/158
- dmm 10y ago
  Strict aliasing can worked around by casting through a union, essentially introducing a new type which can alias any of its component types. Mike Acton has a good description of it with lots of assembly examples here: http://cellperformance.beyond3d.com/articles/2006/06/understanding-strict-aliasing.html http://cellperformance.beyond3d.com/articles/2006/06/underst...
phkahler 10y ago
What if you put the array in a struct and made a union of both uint32_t and uint8_t? Would the union with the larger size force the compiler to generate a 4-byte aligned array for the bytes? I suggest this because it would be portable without any compiler specific stuff.
- mzs 10y ago
  It's already too late, the data is read from a file so the base of the array can be say at address 0xYYYYY2.
deleted 10y ago
[deleted]

151 points by sconxu 10y ago

TL;DR: Even though most instructions of your processor (x86) allow data to be aligned on any byte, your compiler might not.

pjc50 10y ago

Well, that's pretty horrendous. Note that the naive code which just casts the input to uint16_t would work fine. I can't help but wonder if the solution to this might have been better expressed as naive implementation + platform-specific assembly implementation. 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?)

Kubuxu 10y ago
No it is not, the author even cited the rule from C99 himself. > 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.
shakna 10y ago
Going off a few answers similar to this one [0], I'd say that it isn't defined behaviour. It'll be specific to your compiler, and its optimisations. The memcpy solution is what I've seen throughout the industry when you are trying to cast between non-trivial types. [0] http://stackoverflow.com/a/4318446 http://stackoverflow.com/a/4318446
userbinator 10y ago
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? 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 ;-)
pjmlp 10y ago
People people still try hard to believe ANSI C is 1:1 to Asm, which is only kind of true when using language extensions. So then better drop down to Assembly, or if there is no need for compiler portability, intrinsics.
Dylan16807 10y ago
> if you have to understand the underlying instructions executed in order to fix the problem 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.

slededit 10y ago

At some point you might as well byte the bullet and just write the code in assembly.

krylon 10y ago
> byte the bullet Is that a clever pun or Freudian slip?
- deleted 10y ago
  [deleted]
- slededit 10y ago
  Accidental but I'll keep it.

koverstreet 10y ago

Attribute((aligned)) might be useful here.

rwmj 10y ago

These SSE instructions that operate only on aligned data are a pain. It's not well known that Linux/x86 stack frames must always be 16 byte aligned. GCC uses this knowledge to use the SSE aligned instructions when accessing certain fields on the stack. 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: https://caml.inria.fr/mantis/view.php?id=5700#c10779 https://caml.inria.fr/mantis/view.php?id=5700#c10779

userbinator 10y ago
Agreed, I've always found them unusual and perhaps a bit of a shortsighted decision --- they've been making processors seamlessly handle any alignment with perhaps an extra cycle, even for the MMX instructions, yet somehow felt the need to restrict much of the SSE ones into aligned and only provide one unaligned move. 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.
- jjoonathan 10y ago
  > seamlessly handle any alignment with perhaps an extra cycle 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.
  - qb45 10y ago
    Case in point: a simple example of code which copies 1MB of data with SSE and slows down on misalignment: https://news.ycombinator.com/item?id=12718625 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.

qb45 10y ago

The correct solution for GCC is specifying 1-byte alignment for this particular array: #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; } Probably works on clang too and IIRC the MS compiler provides similar functionality with different syntax. AFAIK there is no portable solution. And I'm not sure how exactly this code will fail on architectures which don't support unaligned uint32_t.

speps 10y ago
In C++11 there is a standard for this : http://en.cppreference.com/w/cpp/language/alignas http://en.cppreference.com/w/cpp/language/alignas
- d33 10y ago
  Anybody knows how Rust handles this problem?
  - alkonaut 10y ago
    Not sure if this is what you are asking: Last time I tried alignment in Rust I worked around the lack of explicit alignment support by adding a zero length array of the correct size to the end of the struct. Not sure if alignment support from proper attributes has landed yet. [repr(C)] struct Something { pub foo: f32, pub _alignment: [EightBytes, 0] } where "EightBytes" is a data type of size 8, to align the whole struct on 8 bytes.
    - wyldfire 10y ago
      I doubt you can count on all items being allocated at addresses that are multiples if their size. It's not optimal but you can always use libc::posix_memalign()
      - 10y ago

lukego 10y ago

Related Snabb experiments with IP checksum in C with automatic vectorization, C with vector intrinsics, and AVX2 assembler: https://github.com/snabbco/snabb/pull/899 https://github.com/snabbco/snabb/pull/899

Hello71 10y ago

You can probably also just pass -fno-strict-aliasing to gcc.

GlitchMr 10y ago

Compiler is allowed to assume alignment of pointers (what are you doing is creating a pointer to a value with invalid alignment, hence undefined behaviour (just creating a pointer is undefined behaviour)). The correct solution would be to read values indirectly. For example, a function like that could be used to replace every access to "q" variable. static uint32_t read(const char *p, size_t index) { uint32_t out; memcpy(&out, &p[index * sizeof out], sizeof out); return out; } A compiler can recognize this pattern, and continue to use unaligned accesses that would work. 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.

asveikau 10y ago
The article's final solution (sum3) is exactly this. It does a memcpy into a temporary.
amadvance 10y ago
Is this equivalent ? At least to me this seems a more common pattern than using memcpy(), and I expect to work better on old compilers. static uint32 read(const void *ptr) { const uint8 *b = (const uint8 *)ptr; return (b[3] << 24) | (b[2] << 16) | (b[1] << 8) | (b[0]); }
- qb45 10y ago
  Functionally it seems equivalent, except that it doesn't work on big endian machines (assuming the ints are in native endian). 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.

novia 10y ago

I'm taking assembly right now, and we're working on our first RISC project after spending all semester working with the x86. Why does RISC crash if the bytes are not aligned?

monocasa 10y ago
It costs a non trivial amount of transistors (when compared with an ascetic RISC core) to load words from arbitrarily aligned addresses. 'RISC' used to be about removing those kinds of features, although the term has been a bit bastardized since then).
kabdib 10y ago
Depends on the processor. Some RISC systems won't generate a fault, but others will. Some of the non-faulting ones will load unaligned data correctly (even across page boundaries), while others will helpfully swizzle bytes around in the result for you, or ignore the low bits. "It depends."
brassic 10y ago
Early RISC processors read data from memory 32 bits (4 bytes) at a time, and these reads had to be aligned on 4-byte boundaries. This was a feature of the memory architecture, not just the processor. 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.

ogoffart 10y ago

Again someone who relies on undefined behavior. Casting pointer of wrong alignement is not a platform specific behavior, it's an undefined behavior. Relying on it is an error. 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-know.html http://blog.llvm.org/2011/05/what-every-c-programmer-should-... Another good link about that: http://blog.regehr.org/archives/213 http://blog.regehr.org/archives/213

Sagiri 10y ago
If a particular compiler specified that casting pointers of wrong alignments causes a segfault, it'd be perfectly acceptable to rely on that behavior. The standard would consider it UB, but that compiler has defined that behavior sufficiently. 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.
- konstmonst 10y ago
  "If a particular compiler specified that casting pointers of wrong alignments causes a segfault" Sure it does. It says using undefined behaviour can cause daemons fly out of your nose, among other things (including but not limited to segfaulting).
  - Sagiri 10y ago
    If the semantics of casting pointers of wrong alignments were defined to be demons flying out of your nose, it would be perfectly acceptable to rely on that behavior.
- MaulingMonkey 10y ago
  > If a particular compiler specified that casting pointers of wrong alignments causes a segfault, it'd be perfectly acceptable to rely on that behavior. 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.

ot 10y ago

If you're willing to use compiler extensions, you can avoid the memcpy by using packed structs. This can generate better code. Folly has a generic `loadUnaligned()` that uses this trick: https://github.com/facebook/folly/blob/5d52fb8c30e567403b8ccb65e5c1a159fb92d707/folly/Bits.h#L539 https://github.com/facebook/folly/blob/5d52fb8c30e567403b8cc...

pklausler 10y ago

So much HTML to complain about C working the way C is defined rather than the way the OP wants it to work! It's not that hard to write a fast ones'-complement checksum that's portable and compliant, but whining's always easier than coding.

ambrop7 10y ago

Note that even if you try to manually correct the pointer to work on aligned data (read any initial bytes via char pointer and read the rest via uint32_t pointer), you still generally have undefined behavior: strict-aliasing violation. And the worst thing here is that whether you do have a violation depends on how other code accesses the same data / how the object is initially declared. E.g., you're fine if the original declaration is char[] or uint32_t[], but not if it's uint16_t[]. Because that would entail access to the same data via both uint16_t and uint32_t, a violation of strict-aliasing. 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_chksum.c http://git.savannah.gnu.org/cgit/lwip.git/tree/src/core/inet...

nikanj 10y ago
For what it's worth, people like Linus seem to despise the strict aliasing optimization. https://lkml.org/lkml/2003/2/26/158 https://lkml.org/lkml/2003/2/26/158
dmm 10y ago
Strict aliasing can worked around by casting through a union, essentially introducing a new type which can alias any of its component types. Mike Acton has a good description of it with lots of assembly examples here: http://cellperformance.beyond3d.com/articles/2006/06/understanding-strict-aliasing.html http://cellperformance.beyond3d.com/articles/2006/06/underst...

phkahler 10y ago

What if you put the array in a struct and made a union of both uint32_t and uint8_t? Would the union with the larger size force the compiler to generate a 4-byte aligned array for the bytes? I suggest this because it would be portable without any compiler specific stuff.

mzs 10y ago
It's already too late, the data is read from a file so the base of the array can be say at address 0xYYYYY2.

deleted 10y ago

[deleted]