Jump to content

  • Log In with Google      Sign In   
  • Create Account

C99: strict aliasing rule vs compatible pointers


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
7 replies to this topic

#1 carangil   Members   -  Reputation: 490

Like
2Likes
Like

Posted 06 April 2013 - 02:28 PM

I'm cleaning up some of my code by compiling with gcc -Wall and -Wstrict-aliasing=1 to look for unclean things I've done.

 

 

This is a fairly common pattern in my C code:

 

typedef struct generic_list_s
{
	int type;
	struct generic_list_s* next;
} generic_list_t;

typedef struct
{
	generic_list_t gen;
	char* str;
} string_t;

typedef struct 
{
	generic_list_t gen;
	int x;
} int_t;

 

The general idea is I have some generic structure that I reuse as the 1st element of larger, more specific structures.  The C standard allows you to cast a pointer back and forth between a struct, and it's 1st member.  A pointer to an int_t or a string_t in the above examples is also a pointer to a generic_list_t.

 

GCC however likes to complain.  If I compile a snippet like this:

	string_t* node0;
	int_t* node1;
	string_t* node2;
		
	node0 = mk_string("Hello");
	node1 = mk_int(123);
	node2 = mk_string("World");

	/* Below seems correct
	  node1 is a pointer to an int_t
	  int_t starts with generic_list_t, so
	  a pointer to int_t is also a pointer to int_t
	  (6.7.2.1.13 says )
	  */
	node0->gen.next = (generic_list_t*) node1;
	node1->gen.next = (generic_list_t*) node2;

with -Wstring-aliasing =1, I get this warning:

 

warning: dereferencing type-punned pointer might break strict-aliasing rules

 

This makes sense, in that node1 is a pointer to an int_t, and node0->gen.next is technically a pointer to a generic_list_t.  I have two different types of pointers pointing to the same thing.  I can make it go away by doing this:

 

node0->gen.next = &(node1->gen);
node1->gen.next = &(node2->gen);

 

Which is more correct, although a pointer to the first element of a struct or a pointer to the struct are supposed to be compatible with each other.

 

The real problem comes with functions like:

 

void print_thing(generic_list_t* n)
{
	if (n->type == TYPE_STRING)
	{
		string_t* s = (string_t*) n;/* warning: dereferencing type-punned pointer might break strict-aliasing rules*/
		printf("%s\n", s->str);
	}

	if (n->type == TYPE_INT)
	{
		int_t* i = (int_t*) n;  /* warning: dereferencing type-punned pointer might break strict-aliasing rules*/
		printf("%d\n", i->x);
	}


}

 Hoe do I clean up these warnings? 


Edited by DracoLacertae, 06 April 2013 - 02:39 PM.


Sponsor:

#2 ultramailman   Prime Members   -  Reputation: 1571

Like
0Likes
Like

Posted 06 April 2013 - 03:27 PM

gcc allows the use of unions for type punning. So maybe something like this?
 
(untested):
 
union tmp{
    int_t i;
    generic_list_t n;
} pun = {.n = *n};
printf("%d\n", pun.i.x);

 
edit:
Sorry, that was wrong. What if you cast n to void*, then cast that to int_t* ?

Edited by ultramailman, 06 April 2013 - 03:33 PM.


#3 carangil   Members   -  Reputation: 490

Like
0Likes
Like

Posted 06 April 2013 - 04:45 PM

Unions are often used for type punning, but I'm not really punning.  Punning is taking something like a float*, and casting it an an int*, say for instance to manipulate the bits of the float in some goofy way.  (For instance the classic absolute value trick where you just clear out the sign bit without bothering the fpu).

 

Using a union does help, since I could do this:

typedef union {
  generic_list_t as_generic;
  int_t as_int;
  string_t as_string;
  }   generic_list_u;

And then I can pass around generic_list_u's around all I want.  Technically writing to the as_int field and then reading from the as_generic field is implementation-specific behavior, but gcc and I think most sane compilers would do the expected thing.  But this requires that I know all the possible list types in advance.  The whole point was to not specify this.  The example here are slightly contrived, but in my real code I have linked list implementaion that just deals with how to insert/remove generic_list_t elements from a double linked list.  I'm free to make lists of anything I want, as long as I put a generic_list_t at the top of whatever struct I want to make a list of.

 

If I use void pointers, the warning goes away:

 

void print_thing_void(generic_list_t* n)
{
    void* v  = (void*) n;      

    if (n->type == TYPE_STRING)
    {
        string_t* s = (string_t*) v;
        printf("%s\n", s->str);
    }

    if (n->type == TYPE_INT)
    {
        int_t* i = (int_t*) v;
        printf("%d\n", i->x);
    }
}

 

Instead of print_list, what if I have a contrived example like increment:

void increment(generic_list_t* n)
{
	if (n->type == TYPE_INT)
	{
		int_t* i = (int_t*) n;

		i->x++;
	}
}

// then sometime later:


int_t some_int;

//...

before_increment = some_int->x;

increment( &(some_int->gen)); 

after_increment = some_int->x;        //what value is this?

printf(" %d %d\n", before_increment, after_increment);

In the above code, is gcc free to do something like : "hey, increment takes a generic_list_t*, so nothing is messing with the 'x' value, so when increment returns, I won't bother to dereference some_int again, and I'll just say that after_increment is the same as before_increment, optimize out the after_increment variable, and just call printf with two before_increments"  ?

 

 

Is there a proper way to reconcile strict aliasing rules with 'struct inheritance' in c99?

 

Am I missing something?



#4 Cornstalks   Crossbones+   -  Reputation: 6989

Like
0Likes
Like

Posted 06 April 2013 - 05:15 PM

In the above code, is gcc free to do something like : "hey, increment takes a generic_list_t*, so nothing is messing with the 'x' value, so when increment returns, I won't bother to dereference some_int again, and I'll just say that after_increment is the same as before_increment, optimize out the after_increment variable, and just call printf with two before_increments"  ?

From this answer, it sounds like that's a yes.

 

Is there a proper way to reconcile strict aliasing rules with 'struct inheritance' in c99?

I'm not sure. I can understand the warning when doing something like string_t* s = (string_t*) n; but I was surprised (generic_list_t*) node1 caused a warning. It makes sense, yes, since there are two (different types of) pointers pointing to the same address (like you say), but I'm surprised that it emits an error given the fact that the assigned pointer type is the same as the type of the first member. I'm honestly not sure what to say...


[ I was ninja'd 71 times before I stopped counting a long time ago ] [ f.k.a. MikeTacular ] [ My Blog ] [ SWFer: Gaplessly looped MP3s in your Flash games ]

#5 ultramailman   Prime Members   -  Reputation: 1571

Like
0Likes
Like

Posted 06 April 2013 - 05:19 PM

In the above code, is gcc free to do something like : "hey, increment takes a generic_list_t*, so nothing is messing with the 'x' value, so when increment returns, I won't bother to dereference some_int again, and I'll just say that after_increment is the same as before_increment, optimize out the after_increment variable, and just call printf with two before_increments" ?

Ah, that does sound like a resonable optimization. I guess you could qualify the variable as "volatile", then that should disable optimizations for that variable.
volatile int_t some_int;
That's still a work around though, no idea how to reconcile the way you wanted.

Edited by ultramailman, 06 April 2013 - 05:20 PM.


#6 carangil   Members   -  Reputation: 490

Like
0Likes
Like

Posted 08 April 2013 - 12:41 PM


After (not) thinking about it for a couple days, I think I've actually worked it out.  Skip to the end if you want to see what I came up with that's generic, typesafe, and seems to follow strict-alias rules.  Or stick with the whole post to see how I came to it.

 

The above examples are slightly contrived, but when I look at real uses in my code, it's easy to not mix things up.  This is the real list structure I'm using in my code:
 

 

typedef struct zlistnode_s
{
    struct zlistnode_s* next;
    struct zlistnode_s* prev;
} zlistnode_t;

typedef struct
{   zlistnode_t* head;
    zlistnode_t* tail;
} zlist_t;

zerr zlist_addtail( zlist_t* list, zlistnode_t* node);
...
 

 



When I use a zlist_t, it's usually a list of a single type.  Something like this:
 

 

typedef struct {
    zlistnode_t zlistnode;
    zchar* name;
    zbool important_boolean;
    zuint32 crazy_int;
} supernode_t;
 

 



I had list access macros like this:
 

 

#define zlist_head(ZLIST)      ((ZLIST)->head)
#define zlist_next(ZLISTNODE)  (   ((zlistnode_t*)(ZLISTNODE)) -> next )
 

 



so iterating a list looked like:
 

 

supernode_t*  n = zlist_head(&my_supernode_list);  // of course a warning converting from zlistnode_t* to supernode_t*
while(n)
{
    //do stuff with n
    n = zlist_next(n);  //of course another warning here too
}
 

 



I originally put(void*) casts in the zlist_* macros to make the warnings go away.  When adding an item to the list:

zlist_addtail( &mylist, (zlistnode_t*) mynode); // casting a supernode_t* to a zlistnode_t*

So instead I do this:

zlist_addtail( &mylist, &mynode->zlistnode);  //take the first element of supernode_t*  (it's still a zlistnode_t*, but 'safer')

Also I changes zlist_next to:

#define zlist_next(ZLISTNODE)   ((ZLISTNODE)->zlistnode.next)

This macro is very safe, in that, the list item (say, a supernode_t) just needs to make sure the zlistnode_t is named
zlistnode'.  And if I accidently use the macro on a non-zlistnode-ified struct, I'll get a compile error instead of run-time crash.

So what I've done is completely embedded the zlistnode's inside the structs, and the zlistnodes link to themselves to make the linked list.  The zlist functions now only deal with true, bona-fide zlistnode_t pointers, with no casting or trickery.  There's only 1 thing left unclean:  When I store a supernode_t* in the list, I'm not really storing a supernode_t, I'm storing the zlistnode_t that's 'inside' the supernode.  When I call zlist_next, I'm really getting supernode->zlistnode.next, which is a zlistnode_t*.  I can cast it to a supernode_t*, and since it's the first element, it's guaranteed to be the 'same' pointer, but it still smells of aliasing.

Here, I think is the solution:

 

t

 

ypedef struct zlistnode_s
{
    void* next;
    void* prev;
} zlistnode_t;

typedef struct
{   void* head;
    void* tail;
} zlist_t;

zerr zlist_addtail( zlist_t* list, zlistnode_t* node);

#define zlist_head(ZLIST)      ((ZLIST)->head)
#define zlist_next(ZLISTNODE)   ((ZLISTNODE)->zlistnode.next)
 

 


This almost 'does it all'

Typesafety:

  • The zlist_addtail function only accepts zlist_t*  and zlistnode_t*
  • zlist_head macro only compiles on things that have a 'head'
  • zlist_next macro only functions on things that a zlistnode 'inside'


But there's a nice key difference:  When I store the 'next' or 'head' or 'prev' pointers in the list, they are note other listnodes, they are 'void*'. Because any struct you allocate can be cast freely back and forth to void or their actual type, this is what's happening:

supernode_t* n = mk_supernode();   //n is really a supernode_t

zlist_addtail( &mylist, &n->zlistnode ); //stores 'n' aka 'n->zlistnode' in the list as a 'void*' (totally allowed)

later:

n = zlist_next(n);
which, if you do the macro substitution is:

n = n->zlistnode.next;    // You are not type-punning a zlistnode_t* into a supernode_t*.  You are just turning the zlistnode_t* back into itself from a void*.  (totally allowed)
 

If you want to get really pendantic, you can argue that I'm cheating by passing a zlistnode_t* into addhead/addtail, and I'm indirectly going from supernode_t* to zlistnode_t* to void* and then to supernode_t*, so I'm not playing completely by the rules.  But to that I say, a void* that points to a struct and a void* that points to the first member of a struct are the same void*.  And if I only access super_node_t specific elements from supernode_t*'s and only access listnode_t* elements (next/prev), there's no way the data of these overlapped structs can alias each other.

 

Unless I'm wrong is some way?

 


 



#7 ultramailman   Prime Members   -  Reputation: 1571

Like
0Likes
Like

Posted 08 April 2013 - 05:17 PM

Seems good. Using functions to add items is great for enforcing some type safety.

 

By the way, code involving these void pointers will not be optimized by strict aliasing, right?

 

Also, what happens if you want to add the same item to multiple lists? Since the node struct is always the first field.....

 

linux kernel uses a similar "mixed in" linked list, except structs can contain any number of nodes, so a struct can be added to many lists (as many as there are nodes). Have you seen this before? http://isis.poly.edu/kulesh/stuff/src/klist/



#8 carangil   Members   -  Reputation: 490

Like
0Likes
Like

Posted 08 April 2013 - 09:33 PM

I did come across the linux kernel lists when I was looking up list implementations.  I decided just to put it on the top of the struct to make it easier. 

 

The advantage of the linux kernel list struct over mine, is you could have an object that can be put in multiple lists, because the listnode struct can be anywhere inside the larger struct.  The disadvantage is you have to know what lists those are in advance:

 

typedef struct {

   struct list_head multiples_of_5;

   struct list_head multiples_of_7;

   struct list_head perfect_numbers;

   struct list_head prime_numbers;

 

   unsigned int number;

} natural_numbers_t;

 

In cases where I may need objects that can exist in multiple lists, and I don't know what those lists are in advance, I'm always free to construct one of these:

 

typedef struct

{

    zlistnode_t zlistnode;

    natural_number_t* natnum;

} natural_number_node_t;






Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS