11 ms·

The Strict Aliasing Situation Is Pretty Bad

150 points by pascal_cuoq 11y ago

Pxtl 11y ago
... I am so happy I don't code in C right now. That's icky.
- DannyBee 11y ago
  C++ is just as bad :)
  - deleted 11y ago
    [deleted]
adrianN 11y ago
See also this older post http://blog.regehr.org/archives/959 http://blog.regehr.org/archives/959
haberman 11y ago
I thought this article was unnecessarily dire. One section claims "Physical Subtyping is Broken", where "physical subtyping" is defined as "the struct-based implementation of inheritance in C." I assume this means the typical pattern of: typedef struct { int base_member_1; int base_member_2; } Base; typedef struct { Base base; int derived_member 1; } Derived; The article claims physical subtyping is broken because casting between pointer types results in undefined behavior. The article gives this example: #include <stdio.h> typedef struct { int i1; } s1; typedef struct { int i2; } s2; void f(s1 *s1p, s2 *s2p) { s1p->i1 = 2; s2p->i2 = 3; printf("%i\n", s1p->i1); } int main() { s1 s = {.i1 = 1}; f(&s, (s2 *)&s); } I agree this example is broken, but casting between pointer types in this way is totally unnecessary for C-based inheritance. You can do upcasts and downcasts that are totally legal: Derived d; // Legal upcast: Base* base = &d->base; // Legal downcast: Derived* derived = (Derived*)base; So I don't think the article has proved that "Physical Subtyping is Broken." The next section says that "Chunking Optimizations Are Broken," because code like this is illegal: void copy_8_bytes(char *dst, const char *src) { *(uint64_t*)dst = *(uint64_t*)src; } While this is true, such optimizations are generally unnecessary. For example, write this instead as: void copy_8_bytes(char *dst, const char *src) { memcpy(dst, src, 8); } If you compile this on an architecture like x86 that truly allows unaligned reads, you'll see that modern compilers do the "chunking optimization" for you: 0000000000000000 <copy_8_bytes>: 0: 48 8b 06 mov rax,QWORD PTR [rsi] 3: 48 89 07 mov QWORD PTR [rdi],rax 6: c3 ret It says next that "int8_t and uint8_t Are Not Necessarily Character Types." That is indeed a good point and probably not well-known. So I agree this is something people should keep in mind. But most of this article is warning against practices that are generally unnecessary and known to be bad C in 2016. It's true that a lot of legacy code-bases still break these rules. But many are cleaning up their act, fixing practices that were never correct but used to work. For example, here is an example of Python fixing its API to comply with strict aliasing, and this is from almost 10 years ago: https://www.python.org/dev/peps/pep-3123/ https://www.python.org/dev/peps/pep-3123/
- TorKlingberg 11y ago
  If you do this Derived* derived = (Derived*)base; and then use both base and derived, is that not violating aliasing rules?
  - haberman 11y ago
    Pretty sure it's safe! Take this program: typedef struct { int x; } Base; typedef struct { Base base; int y; } Derived; int f(Base* b, Derived* d) { b->x = 0; d->base.x = 1; return b->x; } Notice that if we are accessing the base members of "d", we are still accessing them through a struct of type "Base" (d->base.x). If we compile this with strict aliasing, you can see the output is allowing that the two might alias (while this isn't a proof, it's a strong indication that this is aliasing-correct). 0000000000000000 <f>: 0: c7 07 00 00 00 00 mov DWORD PTR [rdi],0x0 6: c7 06 01 00 00 00 mov DWORD PTR [rsi],0x1 c: 8b 07 mov eax,DWORD PTR [rdi] e: c3 ret
    - vc98mvco 11y ago
      It is defined. 6.5.7. An object shall have its stored value accessed only by an lvalue expression that has one of the following types: - an aggregate or union type that includes one of the aforementioned types among its members (including, recursively, a member of a subaggregate or contained union) This means Derived is allowed to alias Base.
    - TorKlingberg 11y ago
      Thanks, this is good to know.
- _yosefk 11y ago
  I understand the upcast (which is certainly legal but it forces the casting code to know the depth of the inheritance hierarchy - as in &derived->base1.base2), but what's the argument making the downcast back to Derived legal C? (I honestly wonder; personally I either compile with -fno-strict-aliasing or trust my tests to validate the build...)
kbenson 11y ago
Although I have no evidence that it is being miscompiled, OpenSSL’s AES implementation uses chunking and is undefined. Oh, that's nice. :/
- kazinator 11y ago
  It's nonsense. The function is external, called from a separately compiled file. The pointer comes in as a char *. The code checks its alignment before assuming it can be cast to a block. There is no way in it could be "miscompiled". The ivec argument could in fact have come from an object that is of type aes_block_t. The only thing which might reveal that it didn't is wrong alignment. In other regards, there is no way to tell. Lastly, any cross-compilation-unit optimization which could break code of this type is forbidden, because ISO C says that semantic analysis ends in translation phase 7. I'm looking at C99, not the latest, but I think it's the same. In translation phase 7 (second last), "The resulting tokens are syntactically and semantically analyzed and translated as a translation unit." Note the "semantically analyzed": semantic analysis is where the compiler tries to break your code due to strict aliasing. In translation phase 8 "All external object and function references are resolved. Library components are linked to satisfy external references to functions and objects not defined in the current translation. All such translator output is collected into a program image which contains information needed for execution in its execution environment." No mention of any more semantic analysis! So unless somehow the mere resolution of external symbols can somehow break OpenSSL's AES, I don't see how anything can go wrong. One thing I woudl do in that code, though is to make sure that it doesn't use the original ivec pointer. In the case where "chunking" goes on, it should just cast it to the block type, and put the result of that cast in a local variable. All the ememcpy's, load/store macros would be gone, and the increments by AES_BLOCK_SIZE would just be + 1.
  - xorblurb 11y ago
    Translation phases are all fun and games, but WPO can still break your code thanks to as-if rules - and because nothing prevent alias analysis to be performed regardless of the TU boundaries. And compilers are doing it.
eternalban 11y ago
This was an eye opener for me. Bell Labs tech is as usual a mountain of hidden complexity hiding under a "simple" facade. No more excuses for me. Time to learn Rust.
- aidenn0 11y ago
  C is actually quite simple, even the aliasing rules (I think the aliasing rules all fit on about a quarter page). Programming in C though is anything but. The tension between weakly typed pointers and the desire to generate efficient code is where there is a problem. More or less anywhere you violate the aliasing rules you are doing something that Fortran doesn't allow at all, and by disallowing it semantically the hope was that C programmers could have their cake and eat it too. The reality is that all systems code should probably be compiled with alias analysis disabled.
  - xorblurb 11y ago
    I completely agree. A spec of a quarter page can already be incredibly convoluted and with very hard to anticipate consequences -- even more so when crazy people are interpreting it without caring about the consequence of their acts in the real world. And C is not just about aliasing rules; the current situation is that ANY undefined behavior is a landmine waiting to kill you, regardless of whether is seems to makes sens for your target architecture. And that is mostly because compiler writer have an insane interpretation of the standard: the definition of "undefined behavior" is "behavior, upon use of a nonportable or erroneous program construct or of erroneous data, for which this International Standard imposes no requirements" A key word here is "nonportable" and it is clearly not considered often enough by some compiler writers, who generally prefer to see all undefined behaviors as a licence to "optimize" your code without carrying too much about warning you about potential bad side effects because it's "hard" according to them. This does not make even the beginning of any sense. If it is not what many programmers are expecting (a majority ? -- most coworkers I know including my direct boss are not even aware of all that mess), is costly during the translation phase, has unclear/unquantified runtime performance benefits, is dangerous in the real world and is hard to detect when bugs are activated by those "optimizations", then WHY they are doing them in the first place? From an engineering point of view this is just plain insane. Correct executions and in depth safety are extremely valuable, and only becoming more so year after year, and when they pretend that it's not their fault that programs are breaking they are being even more ridiculous; a compiler does not exist in a vacuum, and neither just to reproduce itself and satisfy the curiosity of geeks for mathematical logic. Obviously some amount of alias analysis can be useful, and this is clearly one of the topic really intended from scratch in the standard to address some performance issues, but maybe it would be enough to explicitly identify what you want to not alias. Seeing the bug when they discuss about allowing uint8_t to not behave in general as an unsigned char in regard with aliasing is just plain disgusting and makes me lose yet again a portion of the tiny remaining trust I had in them. It will soon get to the point that C/C++ will not be realistic languages to consider if you want any kind of reliability. Maybe I'm even deluded in thinking this is not already the case.

150 points by pascal_cuoq 11y ago

Pxtl 11y ago

... I am so happy I don't code in C right now. That's icky.

DannyBee 11y ago
C++ is just as bad :)
- deleted 11y ago
  [deleted]

adrianN 11y ago

See also this older post http://blog.regehr.org/archives/959 http://blog.regehr.org/archives/959

haberman 11y ago

I thought this article was unnecessarily dire. One section claims "Physical Subtyping is Broken", where "physical subtyping" is defined as "the struct-based implementation of inheritance in C." I assume this means the typical pattern of: typedef struct { int base_member_1; int base_member_2; } Base; typedef struct { Base base; int derived_member 1; } Derived; The article claims physical subtyping is broken because casting between pointer types results in undefined behavior. The article gives this example: #include <stdio.h> typedef struct { int i1; } s1; typedef struct { int i2; } s2; void f(s1 *s1p, s2 *s2p) { s1p->i1 = 2; s2p->i2 = 3; printf("%i\n", s1p->i1); } int main() { s1 s = {.i1 = 1}; f(&s, (s2 *)&s); } I agree this example is broken, but casting between pointer types in this way is totally unnecessary for C-based inheritance. You can do upcasts and downcasts that are totally legal: Derived d; // Legal upcast: Base* base = &d->base; // Legal downcast: Derived* derived = (Derived*)base; So I don't think the article has proved that "Physical Subtyping is Broken." The next section says that "Chunking Optimizations Are Broken," because code like this is illegal: void copy_8_bytes(char *dst, const char *src) { *(uint64_t*)dst = *(uint64_t*)src; } While this is true, such optimizations are generally unnecessary. For example, write this instead as: void copy_8_bytes(char *dst, const char *src) { memcpy(dst, src, 8); } If you compile this on an architecture like x86 that truly allows unaligned reads, you'll see that modern compilers do the "chunking optimization" for you: 0000000000000000 <copy_8_bytes>: 0: 48 8b 06 mov rax,QWORD PTR [rsi] 3: 48 89 07 mov QWORD PTR [rdi],rax 6: c3 ret It says next that "int8_t and uint8_t Are Not Necessarily Character Types." That is indeed a good point and probably not well-known. So I agree this is something people should keep in mind. But most of this article is warning against practices that are generally unnecessary and known to be bad C in 2016. It's true that a lot of legacy code-bases still break these rules. But many are cleaning up their act, fixing practices that were never correct but used to work. For example, here is an example of Python fixing its API to comply with strict aliasing, and this is from almost 10 years ago: https://www.python.org/dev/peps/pep-3123/ https://www.python.org/dev/peps/pep-3123/

TorKlingberg 11y ago
If you do this Derived* derived = (Derived*)base; and then use both base and derived, is that not violating aliasing rules?
- haberman 11y ago
  Pretty sure it's safe! Take this program: typedef struct { int x; } Base; typedef struct { Base base; int y; } Derived; int f(Base* b, Derived* d) { b->x = 0; d->base.x = 1; return b->x; } Notice that if we are accessing the base members of "d", we are still accessing them through a struct of type "Base" (d->base.x). If we compile this with strict aliasing, you can see the output is allowing that the two might alias (while this isn't a proof, it's a strong indication that this is aliasing-correct). 0000000000000000 <f>: 0: c7 07 00 00 00 00 mov DWORD PTR [rdi],0x0 6: c7 06 01 00 00 00 mov DWORD PTR [rsi],0x1 c: 8b 07 mov eax,DWORD PTR [rdi] e: c3 ret
  - vc98mvco 11y ago
    It is defined. 6.5.7. An object shall have its stored value accessed only by an lvalue expression that has one of the following types: - an aggregate or union type that includes one of the aforementioned types among its members (including, recursively, a member of a subaggregate or contained union) This means Derived is allowed to alias Base.
  - TorKlingberg 11y ago
    Thanks, this is good to know.
_yosefk 11y ago
I understand the upcast (which is certainly legal but it forces the casting code to know the depth of the inheritance hierarchy - as in &derived->base1.base2), but what's the argument making the downcast back to Derived legal C? (I honestly wonder; personally I either compile with -fno-strict-aliasing or trust my tests to validate the build...)

kbenson 11y ago

Although I have no evidence that it is being miscompiled, OpenSSL’s AES implementation uses chunking and is undefined. Oh, that's nice. :/

kazinator 11y ago
It's nonsense. The function is external, called from a separately compiled file. The pointer comes in as a char *. The code checks its alignment before assuming it can be cast to a block. There is no way in it could be "miscompiled". The ivec argument could in fact have come from an object that is of type aes_block_t. The only thing which might reveal that it didn't is wrong alignment. In other regards, there is no way to tell. Lastly, any cross-compilation-unit optimization which could break code of this type is forbidden, because ISO C says that semantic analysis ends in translation phase 7. I'm looking at C99, not the latest, but I think it's the same. In translation phase 7 (second last), "The resulting tokens are syntactically and semantically analyzed and translated as a translation unit." Note the "semantically analyzed": semantic analysis is where the compiler tries to break your code due to strict aliasing. In translation phase 8 "All external object and function references are resolved. Library components are linked to satisfy external references to functions and objects not defined in the current translation. All such translator output is collected into a program image which contains information needed for execution in its execution environment." No mention of any more semantic analysis! So unless somehow the mere resolution of external symbols can somehow break OpenSSL's AES, I don't see how anything can go wrong. One thing I woudl do in that code, though is to make sure that it doesn't use the original ivec pointer. In the case where "chunking" goes on, it should just cast it to the block type, and put the result of that cast in a local variable. All the ememcpy's, load/store macros would be gone, and the increments by AES_BLOCK_SIZE would just be + 1.
- xorblurb 11y ago
  Translation phases are all fun and games, but WPO can still break your code thanks to as-if rules - and because nothing prevent alias analysis to be performed regardless of the TU boundaries. And compilers are doing it.

eternalban 11y ago

This was an eye opener for me. Bell Labs tech is as usual a mountain of hidden complexity hiding under a "simple" facade. No more excuses for me. Time to learn Rust.

aidenn0 11y ago
C is actually quite simple, even the aliasing rules (I think the aliasing rules all fit on about a quarter page). Programming in C though is anything but. The tension between weakly typed pointers and the desire to generate efficient code is where there is a problem. More or less anywhere you violate the aliasing rules you are doing something that Fortran doesn't allow at all, and by disallowing it semantically the hope was that C programmers could have their cake and eat it too. The reality is that all systems code should probably be compiled with alias analysis disabled.
- xorblurb 11y ago
  I completely agree. A spec of a quarter page can already be incredibly convoluted and with very hard to anticipate consequences -- even more so when crazy people are interpreting it without caring about the consequence of their acts in the real world. And C is not just about aliasing rules; the current situation is that ANY undefined behavior is a landmine waiting to kill you, regardless of whether is seems to makes sens for your target architecture. And that is mostly because compiler writer have an insane interpretation of the standard: the definition of "undefined behavior" is "behavior, upon use of a nonportable or erroneous program construct or of erroneous data, for which this International Standard imposes no requirements" A key word here is "nonportable" and it is clearly not considered often enough by some compiler writers, who generally prefer to see all undefined behaviors as a licence to "optimize" your code without carrying too much about warning you about potential bad side effects because it's "hard" according to them. This does not make even the beginning of any sense. If it is not what many programmers are expecting (a majority ? -- most coworkers I know including my direct boss are not even aware of all that mess), is costly during the translation phase, has unclear/unquantified runtime performance benefits, is dangerous in the real world and is hard to detect when bugs are activated by those "optimizations", then WHY they are doing them in the first place? From an engineering point of view this is just plain insane. Correct executions and in depth safety are extremely valuable, and only becoming more so year after year, and when they pretend that it's not their fault that programs are breaking they are being even more ridiculous; a compiler does not exist in a vacuum, and neither just to reproduce itself and satisfy the curiosity of geeks for mathematical logic. Obviously some amount of alias analysis can be useful, and this is clearly one of the topic really intended from scratch in the standard to address some performance issues, but maybe it would be enough to explicitly identify what you want to not alias. Seeing the bug when they discuss about allowing uint8_t to not behave in general as an unsigned char in regard with aliasing is just plain disgusting and makes me lose yet again a portion of the tiny remaining trust I had in them. It will soon get to the point that C/C++ will not be realistic languages to consider if you want any kind of reliability. Maybe I'm even deluded in thinking this is not already the case.