• Advertisement
Sign in to follow this  

Strict aliasing rule and memory allocation

This topic is 2258 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hello, today I was writing some container class that pre-allocates uninitialized memory and uses placement new when needed. After a long search, I realized I can't possibly do that due to the strict aliasing rule.

To my understanding, void* can be casted to something else only if the original variable holding the pointer to void has not been casted to something else yet. So:


void* myMem = malloc(sizeof(int) * 5);
int* a = (int*) myMem; // OK
short int* b = (short int*) myMem; //WRONG



Is this correct?

If so, writing a stack-based allocator is impossible, or is there any technique I don't know of to achieve that? I'd like to get the equivalent of the following (incorrect) code:


void* StackAlloc(int size) {
static char mem[64];
static int used = 0;
void* ret = mem + used;
used += size;
return ret;
}



From what I gathered, this is only valid if client code casts the returned pointer back to a char. Note that I'm aware of the alignment issues, but this is just a simplified example.

From this discussion with Linus I take it I should disable the no aliasing optimization for the memory lib, but most of the code is templated so I should disable that optimization for every client of the memory lib. From that same discussion understand that the gain in performance and code size is very small to be generous. Do you think I should go ahead and disable said optimization? If so, will I find a way to do the same on compilers other than gcc (ie: Visual Studio), or will I end up with non-standard unportable code? 

Share this post


Link to post
Share on other sites
Advertisement

void* myMem = malloc(sizeof(int) * 5);
int* a = (int*) myMem; // OK
short int* b = (short int*) myMem; //WRONG

This is perfectly valid code. There will be no compiler errors, nor any other errors during runtime. An explanation of what a pointer is will probably help. . .

A pointer is simply a number. Your systems ram is broken up into single bytes.

If you cast a pointer into an int and output that, it will be a number. Lets assume, the number returned by malloc(sizeof(int) * 5); is 100 (its not, but lets assume it is).

In the following code the pointer a is now 100
int* a = (int*) myMem;

In the following code the pointer b is now 100
short int* b = (short int*) myMem;

The only difference comes when you do something like this

*b = 10;

The type of the pointer indicates how many bytes to write. In this case, an short int is 2 bytes. So, *b =10; will write 10 to the first two bytes, at the memory address 100 and 101.
If *a = 10, then the value of 10 would be written over the span of 4 bytes, because an int is 4 bytes.

So, when working with pointers its good to think of them solely as a number ( at least for me).

Share this post


Link to post
Share on other sites
Hello smasherprog, thanks for your reply but this is not what I asked. My concern is about the strict aliasing rule. Specifically, it means that casting a pointer to a type incompatible with the one of the value at the address being casted will give undefined behaviour. That is:


int a;
*(float*)&a = 10.0f;



is not going to work, or at least is against the standard. And that's assuming that int and float have the same alignment and size.




I've continued my research on the internet, and I have experimented a bit myself. gcc seems to skip quite a few warnings about type punning, but luckily ekopath seems to work a little better. What's puzzling me now is that casting a float* to int* makes a warning, while casting a char* to int* and vice-versa doesn't. This is opposite to my understanding that anything can be casted to a char* but not the other way round:


If a program attempts to access the stored value of an object through a glvalue of other than one of the following types the behavior is undefined:
* the dynamic type of the object,
* a cv-qualified version of the dynamic type of the object,
* a type similar (as defined in 4.4) to the dynamic type of the object,
* a type that is the signed or unsigned type corresponding to the dynamic type of the object,
* a type that is the signed or unsigned type corresponding to a cv-qualified version of the dynamic type of the object,
* an aggregate or union type that includes one of the aforementioned types among its elements or non-static data members (including, recursively, an element or non-static data member of a subaggregate or contained union),
* a type that is a (possibly cv-qualified) base class type of the dynamic type of the object,
* a char or unsigned char type.
[/quote]

Any clarification is appreciated!

Edit: Thinking a little, I'm wondering if this is really an issue in my case. The problem is that casting to an incompatible type and then dereferencing both pointers and reading/writing to them will cause a problem because the compiler will reorder the writes as it believes the two objects are unrelated. BUT in my case I only use char to hold memory, and I never really dereference anything. So casting to another type should be 100% safe, no? I'll keep on searching, but this issue is very confusing, I think.


Share this post


Link to post
Share on other sites
I had already found that, but it didn't provide any solution to my problem.

I think I just stumbled upon something interesting though:

The lifetime of an object of type T begins when:
— storage with the proper alignment and size for type T is obtained, and
— if the object has non-trivial initialization, its initialization is complete.
The lifetime of an object of type T ends when:
— if T is a class type with a non-trivial destructor (12.4), the destructor call starts, or
— the storage which the object occupies is reused or released.




Or in code (well, kind of an extreme example):



int a = 10;
float* b = new(&a) float;
*b = 10.0f; // OK
a = 10; // WRONG!




I'm starting to see the point of Linus in his rant...
Well, hopefully this is going to work, it looks like old gcc versions had a bug here (http://gcc.gnu.org/bugzilla/show_bug.cgi?id=29286).


Share this post


Link to post
Share on other sites
This isn't very helpful to your question -- but in C++98/03, I use wrong code like in your first post quite often on a variety of compilers, with my naive expectations working out in reality. i.e. the undefined behaviour in my experience so far has been: it works, even if it shouldn't.

Many C++98/03 programmers that I know seem to be ignorant of the strict aliasing rule and assume that all pointers can alias, unless specifically disabled with the (compiler-specific) restrict keywords... and for better or worse, plenty of products have been shipped after having been written using these wrong assumptions (which creates pressure on the compiler-writers to continue to support this 'wrong' code).

Though Linus communicates like a total douche, I'm personally with him on this one, that treating two identical memory addresses as being the same piece of memory makes much more sense, rather than one piece of memory being treated as if it could possibly hold two different values. It's not a quantum computing language after all tongue.gif

All of the examples that I've seen where strict aliasing produces better assembly are actually what I'd consider to be badly written code anyway -- after performing clean-up so that the code does things like reading members into locals before using them multiple times, or only writing to members at the end of a function, etc, then these examples end up producing optimal code, even without "strict aliasing optimisations".
e.g. in the example in your "this discussion" link, the value of "[font="Courier New"]uniform->b[/font]" should be copied into a local before the loop body, which provides the optimisation explicitly, instead of relying on the compiler to perform it's alias-deduction magic.

Share this post


Link to post
Share on other sites


void* StackAlloc(int size) {
static char mem[64];
static int used = 0;
void* ret = mem + used;
used += size;
return ret;
}


My copy of the standard is at work, so I'll try to remember to have a look when I'm back on Monday. Off the top of my head though, I think your concerns are indeed well-founded, at least theoretically.


From what I gathered, this is only valid if client code casts the returned pointer back to a char. Note that I'm aware of the alignment issues, but this is just a simplified example.
[/quote]
That sounds about right to me. Alternatively, the StackAlloc() function could return a char*.

Do you think I should go ahead and disable said optimization? If so, will I find a way to do the same on compilers other than gcc (ie: Visual Studio), or will I end up with non-standard unportable code? 
[/quote]
Visual C++ has "#pragma optimize" which allows you to control optimizations in your source. It's probably more than you want, but on the other hand the function is quite simple anyway, so disabling optimizations therein may not hurt at all.

It's perhaps also worth noting that the Windows API itself is rife with aliasing violations, punning via unions, etc, so I would be surprised if Visual C++ generates code other than that which you intended in this situation.

Might be one for comp.lang.c++ if you want the definitive answer in terms of standardese.

Share this post


Link to post
Share on other sites



void* StackAlloc(int size) {
static char mem[64];
static int used = 0;
void* ret = mem + used;
used += size;
return ret;
}

The above is not stack allocator. It cannot be, since stack is popped when function returns and allocator goes away.

Stack allocator would be something like this:struct StackAllocator {
T data;
size_t used;
}

...
Pool pool; // auto-allocated, probably on stack
T * t = pool.allocate();
...
void foo(Pool & pool) {
...
}

----
Finding a correct solution isn't easy. Even if it seems like overcomplication, it's possible to come up with reasons why aliasing rules exist and how they can break generated code. Simplest reason perhaps is this:[a][ b][ c ]
a = 1 byte, b = 2, c = 3 bytes


In above example, type C will be allocated at offset of 3. But most non-x86 architectures require data to be aligned. Were 'c' allocated on heap or on stack, it would not be a problem. Internal layout is guaranteed to work due to padding, malloc also works. But in our case we break aliasing rule, so even though char[] is allocated correctly, when we force it into another type, result is invalid.

First solution that comes to mind (manually enforce such constraints) doesn't work. Guessing the internals of how compiler generates code and why isn't a viable option.

The correct solution obviously becomes unions. While clumsy, they would do the trick (syntax might be slightly off):union Foo {
char dummy[MAXIMUM_SIZE_OF_ALL_CONTAINED_TYPES];
A a;
B b;
C c;
...
Z z;
}
The above works. Sizes of types can be determined via sizeof, struct layout rules guarantee the rest. Compiler will the operate with some opaque type of size MAX, which it may additionally conform to arbitrary requirements.

In C++, template lists could be used to automatically construct such proxies.
----

Even if above seems like academic excercise, it's not. Serialization:int a = readInt();
bool b = readBool();
float c = readFloat();

Using naive type casting to conform bytes at offset (buf+curr) into requested type causes precisely the same type of problem. After reading b, c is perhaps located at offset 5, which causes unaligned access error.

Solution, in above particular case, which also happens to be portable (minus endianess/encoding issues) is memcpy:float readFloat() {
char * ptr = buf + offset;
float result;
memcpy(&result, ptr, 4); // assuming float is encoded in compatible way
}


Unfortunately, we cannot use such approach for allocators.

Share this post


Link to post
Share on other sites
Well, just to scare you a little bit then, I *am* getting "unexpected" results :) This is my sample program:

#include <iostream>

class MyClass {
public:
int* GetNew() {
int* retVal = reinterpret_cast<int*>(mem + sizeof(int) * used);
*retVal = 0;
used++;
return retVal;
}
char mem[sizeof(int) * 4];
int used;

MyClass() {
used = 0;
}
};

int main() {
MyClass getter;

int pool[64];

int* a = new int; //getter.GetNew();
*a = 2;
*(short*)a = 1;

int* b = getter.GetNew();
*b = 2;
*(short*)b = 1;

char* c = (char*)pool;
*c = 2;
pool[0] = 3;
*(short*)c = 1;

std::cout << *a << " " << *b << " " << (int)*c << "\n";
return 0;
}


And here's what I'm getting as the output:



[dev00@dev00 ~]$ g++ -fstrict-aliasing -O3 -o StrictAliasing -Wall StrictAliasing.cpp && ./StrictAliasing
2 2 1
[dev00@dev00 ~]$ g++ -fno-strict-aliasing -O3 -o StrictAliasing -Wall StrictAliasing.cpp && ./StrictAliasing
1 1 1
[dev00@dev00 ~]$ pathCC -fno-strict-aliasing -O3 -o StrictAliasing -Wall StrictAliasing.cpp && ./StrictAliasing
Warning: variable .init.0 in _GLOBAL__I_main might be used uninitialized
1 1 1
[dev00@dev00 ~]$ pathCC -fstrict-aliasing -O3 -o StrictAliasing -Wall StrictAliasing.cpp && ./StrictAliasing
Warning: variable .init.0 in _GLOBAL__I_main might be used uninitialized
1 1 1
[dev00@dev00 ~]$ icpc -fstrict-aliasing -O3 -o StrictAliasing -Wall StrictAliasing.cpp && ./StrictAliasing
1 1 1
[dev00@dev00 ~]$ icpc -fno-strict-aliasing -O3 -o StrictAliasing -Wall StrictAliasing.cpp && ./StrictAliasing
1 1 1



So yeah, unless you shovel it in gcc's face with the *(int*)&myFloat obvious example, you don't even get a warning. Anyways in many cases I doubt the compiler can figure out the real original type, and only gcc seems to strive for this insanity. I'll try the VS compiler tomorrow at work (but as you said I expect it to tolerate aliasing), and if anyone can try clang and comeau, that would be interesting...

Anyways if I'm correct the placement new should tell the compiler that the official type for a given address is changing, so whatever I copy and pass around from that point on is only allowed to be of the newly declared type. If I use a void* instead, as from malloc(), then the first time you cast that pointer to a type tells the compiler what type it's going to be. You can't dereference void* anyways. Hopefully this is going to work... x.x 

Edit:
Visual Studio has a /Oa switch (as well as a /Ow), but I get "1 1 1" as the result both with /Oa and without anything.


Share this post


Link to post
Share on other sites
@Antheus: you're right, I just tried to write my allocator in a more compact manner. The code I just posted better reflects my real code. Anyways, using unions is tolerated but still non-standard. In practice it would work except that you can't put anything with a non-trivial constructor in a union and that the type must be known when you declare it. Counter-example: you can't possibly use a union for the fast pimpl idiom. So, as for the non-trivial constructor, my allocator is going to return a constructed object of type T, so it must work both for PODs as well as the rest.

Share this post


Link to post
Share on other sites
*(int*)&myFloat[/quote]

Conversions like this are completely undefined, but many compilers will try to generate expected result due to legacy code.

For use cases like above, one would need to use memcpy.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement