Peeter Joot's (OLD) Blog.

Math, physics, perl, and programming obscurity.

Use of unions to deal with aliasing problems.

Posted by peeterjoot on July 9, 2010

In C pointer aliasing violations and aggressive compiler optimizations, I discussed some examples of aliasing violations. Some types of aliasing violations can be fixed with the use of unions, and an example of that can be found in the -fstrict-aliasing documentation block copied into the above post.

What I didn’t notice despite reading that GCC documentation, was the subtlety of their example that “may not work”. Using that documentation block as an example, here are a couple variations on the theme:

union a_union
{
   int i[2] ;
   double d ;
} ;

int bad( double * d )
{
   *d = 3.0 ;

   int * ip = (int *)d ;

   return *ip ;
}

int maybeBad()
{
   a_union t ;

   t.d = 3.0 ;

   int * ip = &t.i[0] ;

   return *ip ;
}

int good()
{
   a_union t ;

   t.d = 3.0 ;

   return t.i[0] ;
}

All versions of the code should compile, and you probably won’t find any compiler that will complain about the code unless coerced. The first example is a clear example of an aliasing violation. There’s a cast from one pointer type to another, and the data is accessed via different types using the same address. Illegal!

However, how about the second example function maybeBad? What is so wrong with that? The compiler has been “told” via the use of the union that the address &t.d and &t.i[0] are aliased. So what is wrong with the code? It isn’t any different logically than the good function, and one would expect an optimizing compiler to just eliminate the temporary variable ip. The problem is that once this temporary is introduced, the optimizer may loose track of the fact that the addresses were aliased. You can imagine the typical peephole optimization strategies in use by compilers becoming a factor here. So the rules for use of unions to fix alias issues become even more strict. You can’t safely do address of operations on union members unless the union object in question is only ever accessed through one of the type fields. Wow. Basically, the rule of thumb appears to be, don’t use unions. Period. As soon as you do, somebody who doesn’t know the subtleties of these issues is liable to come behind you and do an address of operation. The next thing you know, a build three months later with just the right profile directed feedback optimization coverage to hit the code in question changes some innocent change into a runtime time bomb that will take somebody else a month or two to figure out (if ever).

So basically, as a developer working on a massive codebase where nobody knew these rules, and even those who did didn’t understand the subtleties of them, you are toast. If your product is built with aliasing optimizations (which may be a default) it is basically time to cross your fingers and hope for the best. The idea of even trying to identify all the places in the code where there could be problems like this could very well be overwhelming, and that’s without even trying to fix them once found. The only real safe option is to disable aliasing optimizations and take the performance hit of doing so.

Now all of this was for unions of types. Things can get even more fun with unions of pointers. At one point in time a compiler developer had informed me that this was allowed, and was in fact what unions were for … the correct handling of just this sort of aliasing issue. Here’s an example:

union b_union
{
   int *    i ;
   short *  s ;
} ;

short evenWorse( int * i )
{
   b_union u ;
   u.i = i ;

   return *u.s ;   
}

Again, we have no casts. But this code is just as illegal. A method that has been suggested for dealing with this sort of problem is the use of temporaries as in the following example

short evenWorse( int * i )
{
   short s[2] ;

   memcpy( s, i, sizeof(*i) ) ;
   assert( sizeof(s) == sizeof(*i) ) ;

   return s[0] ;
}

Basically this relies on the automatic inlining and optimization of the memcpy routine to do the operation with no more cost than the function evenWorse. This assumes that the compilers for all platforms that you care about performance for can do such an optimized memcpy, or as one compiler developer expressed it, can “see through the memcpy”. In this day and age that is probably true. For a fix of this sort one probably ought to restrict such memcpy operations and the use of the associated temporaries to be of very local scope, and to be copies into small types, not into big temporary structures.

I can imagine that this could get to be a real pain in the butt if you have to deal with large structures using the versioning idiom. By example, suppose you have an on-disk structure that utilizes an initial integer value as a version field so that one can deal with old and current variations of the structure.

struct fooV1
{
   int32_t  version ;

   int8_t   f1 ;
   int8_t   f2 ;
   int16_t  f3 ;

   char spare[12] ;
} ;

struct foo
{
   int32_t  version ;

   int16_t  f1 ;
   int16_t  f2 ;
   int32_t  f3 ;

   char spare[4] ;
} ;

void BadWayToOperateOnVersionedStruct( foo * f )
{
   if ( 1 == f->version )
   {
      handleBackwardCompatableData( (fooV1 *)f ) ;
   }
   else
   {
      handleCurrentTypeOfData( f ) ;
   }
}

void NotAnyBetterWayToOperateOnVersionedStruct( foo * f )
{
   union {
      int32_t *   v ;
      foo *       f ;
      fooV1 *     f1 ;
   } u ;

   u.f = f ;

   if ( 1 == *u.v )
   {
      handleBackwardCompatableData( u.f1 ) ;
   }
   else
   {
      handleCurrentTypeOfData( u.f ) ;
   }
}

This is a very typical pattern of aliasing violation, at least in code that I have seen. Handling something like this could get very ugly. One way that would work, would be to create a field by field copy of the structure, and work with the new one only

void CrappyWayToOperateOnVersionedStruct( foo * f )
{
   int32_t version ;
   memcpy( &version, f->v, sizeof(version) ) ; 
   assert( sizeof(version) == sizeof(f->v) ) ;

   if ( 1 == version )
   {
      struct foo copy ;
      copy.version = f->version ;
      copy.f1 = f->f1 ;
      copy.f2 = f->f2 ;
      copy.f3 = f->f3 ;

      handleCurrentTypeOfData( &copy ) ;
   }
   else
   {
      handleCurrentTypeOfData( u.f ) ;
   }
}

There are only some types of code that something like this would work on. If the handleCurrentTypeOfData and handleBackwardCompatableData functions had side effects, especially complex ones, where it also modified the data, perhaps for subsequent use, then one is toast. Again, there’s no obvious general answer on how to resolve something like this.

Advertisements

8 Responses to “Use of unions to deal with aliasing problems.”

  1. Robin McNeill said

    For the versioned structure example, it seems we cannot simply use a union because taking the address of a member of the union violates aliasing rules as you discussed earlier? That is unfortunate…

    There may be a way to use C++ to mitigate this by hiding the union as a private member inside of a class that restricts how people access the members of the union. Would need to be careful though, because returning a reference to a member of the union through an accessor function may not be sufficient, as one can simply turn around and take the address of the reference (which should be equivalent to taking the address of the referenced value directly). I am not sure if that would introduce aliasing issues again.

    In fact it may be necessary to completely prevent access to members of the union, instead having member functions that manipulate fields of the versioned structure directly.

    Something like this…

    class VersionedStructureFoo
    {
    private:
       struct fooV1
       {
          int32_t  version ;
    
          int8_t   f1 ;
          int8_t   f2 ;
          int16_t  f3 ;
    
          char spare[12] ;
       } ;
    
       struct foo
       {
          int32_t  version ;
    
          int16_t  f1 ;
          int16_t  f2 ;
          int32_t  f3 ;
    
          char spare[4] ;
       } ;
    
       union
       {
          int32_t version;
          fooV1 v1;
          foo v2;
          // etc
       } data;
    
    public:
       int getF1() const
       {
          switch(data.version)
          {
          case 1: return data.v1.f1;
          case 2: return data.v2.f1;
          // etc
          }
       }
    
       // etc
    };
    
    • peeterjoot said

      Yeah, I think that something like that is correct. In some circumstances it could be an acceptable way to do it. There will be other cases where it isn’t because of the runtime cost of the accessor methods. It would also be a pain in the butt to code these accessor methods in many cases. Each of these types of issues we’ll likely have to deal with in a case by case basis.

      • Robin McNeill said

        It is easy enough to create a new code generation step in our build process that can generate the code for these versioned structures and all accessor/mutator functions given a simple enough definition of the desired structures in a reasonably well structured format, so that shouldn’t be much of a concern.

        The runtime cost of the switch() on the version field is interesting though. Definitely a case by case situation that depends on how often the switch() on the version field needs to be executed compared with the size of the structure and frequency that it would be copied to determine whether copying the structure is cheaper or not in the long run.

        But, is the potential for run time gain worth the risk of passing a local copy of a versioned structure to some function that will end up modifying the structure through some hidden side effect and causing a run time problem because the update is lost?

      • peeterjoot said

        I’d not be prepared to judge if the performance cost is worth the gain without looking at the specifics. There could easily be another valid way of dealing with the problem that doesn’t have the same runtime cost.

  2. I know this post is more than a year old now, but I just found your blog and is really full of a lot of things I’m interested in (C,C++ compiler dark corners, atomics, barriers etc).
    Very interested in the whole aliasing battle, I can’t really understand why the case with union of pointers is not going to work (i.e. : aren’t we satisfying the contract of only accessing things through the union itself?). I’m probably missing something, could you elaborate a bit?
    Thanks,
    Andrea

    • peeterjoot said

      The compiler developer who explained it to me something to the effect of: they keep “alias sets”, some sort of compiler data structure that tracks variables that are known to refer to the same or overlapping memory. He said that only the union member that is assigned to, if that member is a pointer, is added to the alias set, so once there is an access through a different pointer in the union, the alias set becomes incomplete, and one can end up with an optimization issue.

      Why all the pointer members in the union wouldn’t be added to the alias set is not clear to me, since the intuitive view of a union of pointers is for just this. However, I’m sure the answer to that is that the standard allows for them to not _have_ to add it, so there’s a performance benefit to omit this.

  3. […] pointer aliasing c    11     c pointer aliasing    11 https://peeterjoot.wordpress.com/2010/07/09/use-of-unions-to-deal-with-aliasing-problems/ […]

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

 
%d bloggers like this: