46 ms·

Type-based aliasing in C

71 points by Kristine1975 10y ago

kazinator 10y ago
The float/int aliasing via pointer is the strawman version of this which is used to sell the undefinedness and the optimizations as a good thing. In fact, int/int aliasing is also undefined behavior: { struct foo { int x; } sfoo = { 42; }; struct bar { int x; } *psbar = (struct bar *) &sfoo; return psbar->x; // UB, even though int accessed. } Why this is undefined ias that psbar->x is actually (* psbar).x. There is an lvalue ere which is (* psbar) and that is of type struct bar; it doesn't match the type of the object which is struct foo. Maybe it's time for an alternative to ISO C: a safe C with more behaviors pinned down. It should be that when an lvalue is formed by a chained expression like a->b[2].c.d the type of the access should be considered to be the final type which designates the data object, without regard for the intermediate types in the chain. The object should be deemed to be accessed via that type. So if the .d member in a->b[2].c.d has type int, and the object being designated has that type, everything is good.
- lifthrasiir 10y ago
  > Maybe it's time for an alternative to ISO C: a safe C with more behaviors pinned down. There was a proposal for such alternative [1], which was abandoned later [2] due to the difficulty to get a single set of limitations that everybody would expect. [1] http://blog.regehr.org/archives/1180 http://blog.regehr.org/archives/1180 [2] http://blog.regehr.org/archives/1287 http://blog.regehr.org/archives/1287
- startling 10y ago
  Is it really fair to call this int/int aliasing?
  - J_Darnley 10y ago
    Since one of the ints is italicised then I assume that the HN software has eaten an asterisk. The second one is probably pointer-to-int.
    - kazinator 10y ago
      The italics were for emphasis.
    - kazinator 10y ago
      The italics were for emphasis. There is no pointer-to-int there.
- DannyBee 10y ago
  First, this is not undefined, so you are going to need to find another example :) 6.7.2.1/13 "Within a structure object, the non-bit-field members and the units in which bit-fields reside have addresses that increase in the order in which they are declared. A pointer to a structure object, suitably converted, points to its initial member (or if that member is a bit-field, then to the unit in which it resides), and vice versa. There may be unnamed padding within a structure object, but not at its beginning." (This is also known as the first member rule) 6.5/7 then says: " An object shall have its stored value accessed only by an lvalue expression that has one of the following types: a type compatible with the effective type of the object, a qualified version of a type compatible with the effective type of the object, a type that is the signed or unsigned type corresponding to the effective type of the object, a type that is the signed or unsigned type corresponding to a qualified version of the effective type of the object, 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), or a character type." These are both types compatible with the effective type of the object. IE your first pointer is really also an int*, as is your second pointer. Your dereference attempt, which is an access to an int, through something with an effective type of pointer to an int, is a valid thing to do. (Note: I implemented a large part of of GCC's current pointer aliasing analysis and rules, though the underlying TBAA set construction predates me by quite a while :P) Now, if you added a field and tried this with the second member, of a different type than the first, you'd maybe get a different answer. However, pay close attention to: 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), or GCC takes this very seriously. So if you construct types that contain both compatible types, and use that, gcc will consider it okay, no matter how weird what you are doing is. (Note also i do not claim either set of rules produces sane results, and in fact, can easily construct examples where the standard says nonsensical things, or rules seem to change depending on whether you have one source file or two or ...) In general, however, your complaint is basically: "C is not a pure structural type system, it's a name based one for the most part". This is true, and it is meant to be that way. There are other programming languages with structural type systems (OCaml is a good example).
  - pascal_cuoq 10y ago
- technion 10y ago
  I can't get that to compile, is that semi colon wayward? structs.c:5:39: error: unexpected ';' before '}' If I remove that, I can't even get tis-interpreter to complain, strongly suggesting this is fine.
  - pascal_cuoq 10y ago
    tis-interpreter does not detect strict aliasing violations yet. An analysis for exactly that is being worked on, and it will warn on this example, but this is a minefield of ambiguous specification by the standard, compiler practices that seem to go beyond what the standard says in some cases, and existing programs that “work” and that no-one wants to read thousands of warnings about.
    - technion 10y ago
      Thanks for this clarification. Also, thanks for the product, it's been invaluable. You're correct though, there are plenty of common applications that are either meant to be compiled with strict aliasing disabled, or which just produce tonnes of warnings under normal circumstances as it is. It also seems to be compiler dependant. I found a popular complained about type aliasing, but I moved to a newer GCC and the error went away.
  - int0x80 10y ago
    s/42;/42,/
- gpderetta 10y ago
  Why would you expect the above to work? It is a pretty clear violation of the type rules on any sane language. For what is worth, I would love to be able to wrap logically different types of float and ints in distinct structures so that I can benefit from TBAA more, but I believe that GCC, for many reasons, internally uses a structural type system to track TBAA.
  - nitrogen 10y ago
    Because C's type rules are often thought of as syntactic sugar for pointer arithmetic, not sacrosanct definitions of what is or is not an X or a Y.
  - kazinator 10y ago
    > Why would you expect the above to work? Because 1. What it is trying to do is perfectly clear. 2. What it is trying to do is not only perfectly clear, but has a completely machine independent interpretation. 3. "Work" is better than "not work", all round, for everyone involved.
    - gpderetta 10y ago
      1. It is so perfectly clear that no two C programmers can agree to a common set of rules. 2. A machine independent interpretation would prevent any memory safety santiizer to do its job, which it seems to me much more useful than allowing such shenanigans. 3. The best resolution for everyone involved is for the program to abort as soon as it detect a rule violation. "Working" for some ill defined definition of working is not useful to anyone.
      - kazinator 10y ago
        No two C programmers can possibly disagree about what that code should do if it were to be defined. There are many ways of adding requirements to make it defined (and those ways will differ in what else they make defined). > The best resolution for everyone involved is for the program to abort as soon as it detect a rule violation. The pointer cast in the code makes it clear that the aliasing between the identically structured struct is intentional.　(If we remove the cast, we have a diagnosable constraint violation: no need to whip out the memory sanitizers). At least we seem to agree as far as that optimizing based on the assumption that aliasing does not take place is one of the worst things that could happen. The rule violation is not diagnosed, and the obvious meaning doesn't occur either, but rather some weird result. For instance, garbage is accessed because the underlying struct is not yet initialized (on grounds that it's not necessary to initialize something before an improperly typed access to it).
ekr 10y ago
One of the way to achieve encapsulation in C, is to have a certain definition of a structure in the implementation file, that you use internally, and a different (usually smaller, sometimes no structure at all, just a handle), exposed to the public (in the header). As far as I can see, this would break this approach, (if this strict type aliasing would also be used at LTO).
- gpderetta 10y ago
  In C++ this already breaks the One Definition Rule at compile time, even before any aliasing issues come into play. I'm not sure what's the ODR equivalent in C (or whether it exists at all).
_yosefk 10y ago
I didn't know the part where the standard lets you malloc a buffer, write it as int, read it as int, then write it as float, and read it as float, all without freeing, and how the compiler thus has to treat heap memory differently from other memory. The part where compilers are too aggressive to follow this rule actually makes sense (as it seems to greatly increase the chance of valid optimizations based on type-based alias analysis to actually happen; it's hard to prove that a given pointer wasn't malloced.) I wonder if the story is different with C++'s operator new, which returns a typed result.
- gpderetta 10y ago
  Yes, the C rules are weird as that. I believe that GCC semi official stance is that stores always change the effective type of memory, not just for anonymous memory (this is more relaxed than the C rules, but handles correctly cases which are ambiguous under the standard rules). C++ has the same rules as C for trivially constructible objects, but for objects with non trivial constructors, things are more complicated (and keep being revised at every standard update).
haberman 10y ago
There is a big problem AFAIK with the "effective type" (C99) or "dynamic type" (C++) rules. If you are writing your own allocator (malloc() or some arena allocator), there is no legal way AFAIK to seed it with global/stack memory. Your global/stack memory has a declared type of char[], and there is no way to convert this into the type-less kind of memory you need to get back from malloc().

71 points by Kristine1975 10y ago

The float/int aliasing via pointer is the strawman version of this which is used to sell the undefinedness and the optimizations as a good thing. In fact, int/int aliasing is also undefined behavior: { struct foo { int x; } sfoo = { 42; }; struct bar { int x; } *psbar = (struct bar *) &sfoo; return psbar->x; // UB, even though int accessed. } Why this is undefined ias that psbar->x is actually (* psbar).x. There is an lvalue ere which is (* psbar) and that is of type struct bar; it doesn't match the type of the object which is struct foo. Maybe it's time for an alternative to ISO C: a safe C with more behaviors pinned down. It should be that when an lvalue is formed by a chained expression like a->b[2].c.d the type of the access should be considered to be the final type which designates the data object, without regard for the intermediate types in the chain. The object should be deemed to be accessed via that type. So if the .d member in a->b[2].c.d has type int, and the object being designated has that type, everything is good.

lifthrasiir 10y ago
> Maybe it's time for an alternative to ISO C: a safe C with more behaviors pinned down. There was a proposal for such alternative [1], which was abandoned later [2] due to the difficulty to get a single set of limitations that everybody would expect. [1] http://blog.regehr.org/archives/1180 http://blog.regehr.org/archives/1180 [2] http://blog.regehr.org/archives/1287 http://blog.regehr.org/archives/1287
startling 10y ago
Is it really fair to call this int/int aliasing?
- J_Darnley 10y ago
  Since one of the ints is italicised then I assume that the HN software has eaten an asterisk. The second one is probably pointer-to-int.
  - kazinator 10y ago
    The italics were for emphasis.
  - kazinator 10y ago
    The italics were for emphasis. There is no pointer-to-int there.
DannyBee 10y ago
First, this is not undefined, so you are going to need to find another example :) 6.7.2.1/13 "Within a structure object, the non-bit-field members and the units in which bit-fields reside have addresses that increase in the order in which they are declared. A pointer to a structure object, suitably converted, points to its initial member (or if that member is a bit-field, then to the unit in which it resides), and vice versa. There may be unnamed padding within a structure object, but not at its beginning." (This is also known as the first member rule) 6.5/7 then says: " An object shall have its stored value accessed only by an lvalue expression that has one of the following types: a type compatible with the effective type of the object, a qualified version of a type compatible with the effective type of the object, a type that is the signed or unsigned type corresponding to the effective type of the object, a type that is the signed or unsigned type corresponding to a qualified version of the effective type of the object, 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), or a character type." These are both types compatible with the effective type of the object. IE your first pointer is really also an int*, as is your second pointer. Your dereference attempt, which is an access to an int, through something with an effective type of pointer to an int, is a valid thing to do. (Note: I implemented a large part of of GCC's current pointer aliasing analysis and rules, though the underlying TBAA set construction predates me by quite a while :P) Now, if you added a field and tried this with the second member, of a different type than the first, you'd maybe get a different answer. However, pay close attention to: 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), or GCC takes this very seriously. So if you construct types that contain both compatible types, and use that, gcc will consider it okay, no matter how weird what you are doing is. (Note also i do not claim either set of rules produces sane results, and in fact, can easily construct examples where the standard says nonsensical things, or rules seem to change depending on whether you have one source file or two or ...) In general, however, your complaint is basically: "C is not a pure structural type system, it's a name based one for the most part". This is true, and it is meant to be that way. There are other programming languages with structural type systems (OCaml is a good example).
- pascal_cuoq 10y ago
technion 10y ago
I can't get that to compile, is that semi colon wayward? structs.c:5:39: error: unexpected ';' before '}' If I remove that, I can't even get tis-interpreter to complain, strongly suggesting this is fine.
- pascal_cuoq 10y ago
  tis-interpreter does not detect strict aliasing violations yet. An analysis for exactly that is being worked on, and it will warn on this example, but this is a minefield of ambiguous specification by the standard, compiler practices that seem to go beyond what the standard says in some cases, and existing programs that “work” and that no-one wants to read thousands of warnings about.
  - technion 10y ago
    Thanks for this clarification. Also, thanks for the product, it's been invaluable. You're correct though, there are plenty of common applications that are either meant to be compiled with strict aliasing disabled, or which just produce tonnes of warnings under normal circumstances as it is. It also seems to be compiler dependant. I found a popular complained about type aliasing, but I moved to a newer GCC and the error went away.
- int0x80 10y ago
  s/42;/42,/
gpderetta 10y ago
Why would you expect the above to work? It is a pretty clear violation of the type rules on any sane language. For what is worth, I would love to be able to wrap logically different types of float and ints in distinct structures so that I can benefit from TBAA more, but I believe that GCC, for many reasons, internally uses a structural type system to track TBAA.
- nitrogen 10y ago
  Because C's type rules are often thought of as syntactic sugar for pointer arithmetic, not sacrosanct definitions of what is or is not an X or a Y.
- kazinator 10y ago
  > Why would you expect the above to work? Because 1. What it is trying to do is perfectly clear. 2. What it is trying to do is not only perfectly clear, but has a completely machine independent interpretation. 3. "Work" is better than "not work", all round, for everyone involved.
  - gpderetta 10y ago
    1. It is so perfectly clear that no two C programmers can agree to a common set of rules. 2. A machine independent interpretation would prevent any memory safety santiizer to do its job, which it seems to me much more useful than allowing such shenanigans. 3. The best resolution for everyone involved is for the program to abort as soon as it detect a rule violation. "Working" for some ill defined definition of working is not useful to anyone.
    - kazinator 10y ago
      No two C programmers can possibly disagree about what that code should do if it were to be defined. There are many ways of adding requirements to make it defined (and those ways will differ in what else they make defined). > The best resolution for everyone involved is for the program to abort as soon as it detect a rule violation. The pointer cast in the code makes it clear that the aliasing between the identically structured struct is intentional.　(If we remove the cast, we have a diagnosable constraint violation: no need to whip out the memory sanitizers). At least we seem to agree as far as that optimizing based on the assumption that aliasing does not take place is one of the worst things that could happen. The rule violation is not diagnosed, and the obvious meaning doesn't occur either, but rather some weird result. For instance, garbage is accessed because the underlying struct is not yet initialized (on grounds that it's not necessary to initialize something before an improperly typed access to it).

ekr 10y ago

One of the way to achieve encapsulation in C, is to have a certain definition of a structure in the implementation file, that you use internally, and a different (usually smaller, sometimes no structure at all, just a handle), exposed to the public (in the header). As far as I can see, this would break this approach, (if this strict type aliasing would also be used at LTO).

gpderetta 10y ago
In C++ this already breaks the One Definition Rule at compile time, even before any aliasing issues come into play. I'm not sure what's the ODR equivalent in C (or whether it exists at all).

_yosefk 10y ago

I didn't know the part where the standard lets you malloc a buffer, write it as int, read it as int, then write it as float, and read it as float, all without freeing, and how the compiler thus has to treat heap memory differently from other memory. The part where compilers are too aggressive to follow this rule actually makes sense (as it seems to greatly increase the chance of valid optimizations based on type-based alias analysis to actually happen; it's hard to prove that a given pointer wasn't malloced.) I wonder if the story is different with C++'s operator new, which returns a typed result.

gpderetta 10y ago
Yes, the C rules are weird as that. I believe that GCC semi official stance is that stores always change the effective type of memory, not just for anonymous memory (this is more relaxed than the C rules, but handles correctly cases which are ambiguous under the standard rules). C++ has the same rules as C for trivially constructible objects, but for objects with non trivial constructors, things are more complicated (and keep being revised at every standard update).

haberman 10y ago

There is a big problem AFAIK with the "effective type" (C99) or "dynamic type" (C++) rules. If you are writing your own allocator (malloc() or some arena allocator), there is no legal way AFAIK to seed it with global/stack memory. Your global/stack memory has a declared type of char[], and there is no way to convert this into the type-less kind of memory you need to get back from malloc().