understanding strict aliasing
Alberto Griggio
Hello,
consider the following piece of code, which is a variant of the Pool
allocator from Stroustroup's book (chapter 19 IIRC)
[disclaimer, I'm recalling the code from memory, I don't have the book in
front of me right now]:
struct Pool {
struct Link { Link *next; };
struct Chunk {
Chunk *next;
char mem[4 * sizeof(Link)];
};
Link *head;
Chunk *chunks;
Pool()
{
chunks = new Chunk();
char *start = chunks->mem;
// ...
head = reinterpret_cast<Link *>(start);
}
void *alloc()
{
Link *p = head;
head = head->next;
return p;
}
void free(void *p)
{
Link *l = static_cast<Link *>(p);
l->next = head;
head = l;
}
};
My question is: doesn't the above code break the strict aliasing
requirements (3.10/15 of the C++03 standard)? My understanding is that it
does, since both in alloc() and in free() we are accessing chunks->mem[0]
from a Link *, or am I wrong? If I'm wrong, can somebody clarify this? If
I'm right, is there a portable, standards-compliant way of achieving the
same (i.e. implementing a pooled allocator along the above lines)?
Thanks in advance,
Alberto
--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
Joshua Maurice
On Nov 19, 12:17 pm, Alberto Griggio <alberto.grig...@gmail.com>
wrote:
At:
head = head->next;
You are accessing that object through a Link lvalue. The dynamic type
of the object is a Chunk lvalue. They are not related by inheritance,
nor does it meet any other allowed ways to alias, so I'm pretty sure
this is a violation of the strict aliasing rules.
How could you fix this? I think the following would work (modulo any
issues which weren't dealt with in the original code, like running out
of chunks, alignment, and other things of which I'm unaware atm):
#include <cstddef>
#include <new>
struct Pool {
struct Link { Link *next; };
static std::size_t const sizeOfChunk = 4 * sizeof(Link);
Link *head;
Pool()
{
char* start = new char[sizeof(Link) + sizeOfChunk];
head = new(start) Link;
// ...
}
void *alloc()
{
Link *p = head;
head = head->next;
return p + 1;
}
void free(void *p)
{
if ( ! p)
return;
Link *l = static_cast<Link *>(p) - 1;
l->next = head;
head = l;
}
};
For the record, the rules are quite flaky in the standard in this
regard. I'm about to going into a rather long discussion of how I see
the rules as they stand. Just a warning.
Before we continue, let's talk about the union DR (Defect Report),
which finds its roots in C. Ex:
int foo(int* x, float*y)
{ int tmp = 1;
*x = 1;
tmp += *x;
*y = 1;
tmp += *y;
return tmp;
}
int main()
{ union { int x; float y; };
return foo(&x, &y);
}
This program demonstrates a bug in the standard. In the above program,
as written, I am not type punning through the union - I only read a
member of the union after a previous write to that member of the
union. However, the idea of the standard is that ::foo could be
defined in another translation unit, and with the strict aliasing rule
the compiler could assume that *x and *y do not refer to the same
memory location, allowing it to reorder the above instructions to
produce code which reads from a member of the union after a write to a
different member of the union, aka bad.
What follows is my /interpretation/ of the standard, not what it
literally says. I believe that it is the well supported and understood
reading, however.
A piece of storage can be "raw", or it can contain an object, either
POD or non-POD.
You can end the lifetime of the object in the storage, either by
releasing the storage, calling its destructor if it has one, or
constructing a new object in the same storage. (See 3.8 Object
Lifetime / 1.)
You can start the lifetime of a new object in that storage (which ends
the lifetime of any object already in that storage). For a POD type,
you can start the lifetime of the new POD object by simply writing to
that storage through a lvalue of that POD type (which may involve a
reinterpret_cast, a placement new, a static_cast to void*, then to T*,
and so on). (Note that the first access must be a write because
reading uninitialized data, or data from another object type, is
undefined behavior [except for char and unsigned char].) For a non-POD
type, you can start the lifetime with placement new. (See 3.8 Object
Lifetime / 1.)
When doing fun casting and stuff, such as in your allocator example, a
simple rule must be followed: The rule is that whenever you end an
object's lifetime and put a new one in its place of a different type,
that piece of storage cannot be aliased anywhere else in the program.
The idea is that you want to avoid situations similar to the union DR.
(If it's the exact same type [ignoring top-level cv-qualifies], then
3.8 Object Lifetime / 7 let's you get away with it, and it doesn't run
afoul of the union DR either.) I would be curious if this could be
weakened in any useful way while still avoiding the union DR
problems.
With those restrictions in mind, the rules of 3.10 / 15 of the C++03
standard make a bit more sense. You can end the lifetime of an object
and create a new object in a piece of storage - such things are
related to the union DR and mostly unrelated to 3.10 / 15. However,
for the lifetime of any particular object, it must be accessed through
lvalues of the correct type, which 3.10 / 15 lists. For a object of
type T, this includes: T itself or lvalues of base class types, a few
other cases which I've forgotten or omitted, and notably char and
unsigned char.
So, if you want to change the object type of a piece of memory, then
make sure it's not aliased anywhere in the program, destroy the old
object and construct the new object, and ensure that for the duration
of the new object's lifetime, it is accessed only through lvalues of
that type.
Finally, be careful of some of the minor rules laid out in 3.8 Object
Lifetime. Some of the more interesting gotchas are:
3.8 Object Lifetime / 2 is incredibly poorly phrased, enough that I
would call it bullshit. A much more sensible wording is that the
lifetime of a POD object starts as soon as storage with proper size
and alignment is obtained /and a write through the POD lvalue is made
to that storage/. (That POD object then has lifetime which extends to
the usual terminators - storage is released or reused.) Otherwise, the
storage of every POD object contains a limitless number of POD objects
and the strict aliasing rule has no point. This is pretty intimately
tied to the union DR, so I'm not terribly surprised that the current
wording is in the standard.
3.8 Object Lifetime / 4. Basically, don't end the lifetime of an
object with a non-trivial destructor without calling the destructor.
Undefined behavior results if anything would depend on a result of the
destructor.
3.8 Object Lifetime / 5 and 6. Basically, if you intend to put an
object of non-POD type T in some raw storage, then don't refer to that
storage as type T except during the T object's lifetime. Otherwise
undefined behavior can result. (See the passages for the specific
rules.) Those two sections are a pretty verbose way of saying that,
but I think that's what they're saying. I think they're also
misleading when they single out char and unsigned char. Specifically,
if you write to the raw storage through any POD lvalue, that
immediately creates a POD object of that POD type in that storage ala /
my interpretation/ of 3.8 Object Lifetime / 1 and 4. (Note again that
the first access must be a write because reading uninitialized data,
or data from another type, is undefined behavior [except for char and
unsigned char].) You can thereafter construct an object of non-POD
type T in that same storage which will end the lifetime of the POD
object ala 3.8 Object Lifetime / 1 and 4.
3.8 Object Lifetime / 8. Basically, don't try to reuse storage which
contains, did contain, or will contain a const object of static or
automatic storage.
Johannes Schaub (litb)
Joshua Maurice wrote:
>
> On Nov 19, 12:17 pm, Alberto Griggio <alberto.grig...@gmail.com>
> wrote:
>> [...]
>
> What follows is my /interpretation/ of the standard, not what it
> literally says. I believe that it is the well supported and understood
> reading, however.
>
> A piece of storage can be "raw", or it can contain an object, either
> POD or non-POD.
>
> You can end the lifetime of the object in the storage, either by
> releasing the storage, calling its destructor if it has one, or
> constructing a new object in the same storage. (See 3.8 Object
> Lifetime / 1.)
>
This is my interpretation too.
> You can start the lifetime of a new object in that storage (which ends
> the lifetime of any object already in that storage). For a POD type,
> you can start the lifetime of the new POD object by simply writing to
> that storage through a lvalue of that POD type (which may involve a
> reinterpret_cast, a placement new, a static_cast to void*, then to T*,
> and so on). (Note that the first access must be a write because
> reading uninitialized data, or data from another object type, is
> undefined behavior [except for char and unsigned char].) For a non-POD
> type, you can start the lifetime with placement new. (See 3.8 Object
> Lifetime / 1.)
>
This is also my interpretation. I wonder why that way of creating an object
(by writing through an lvalue) isn't listed in 1.8/1 though? That one always
caused headaches to me.
My understanding is that these lifetime-starting and stopping rules are the
basics of how unions change their active member in C++.
> Finally, be careful of some of the minor rules laid out in 3.8 Object
> Lifetime. Some of the more interesting gotchas are:
>
> 3.8 Object Lifetime / 2 is incredibly poorly phrased, enough that I
> would call it bullshit. A much more sensible wording is that the
> lifetime of a POD object starts as soon as storage with proper size
> and alignment is obtained /and a write through the POD lvalue is made
> to that storage/. (That POD object then has lifetime which extends to
> the usual terminators - storage is released or reused.) Otherwise, the
> storage of every POD object contains a limitless number of POD objects
> and the strict aliasing rule has no point. This is pretty intimately
> tied to the union DR, so I'm not terribly surprised that the current
> wording is in the standard.
>
I was glad when I saw this is being worked on lately, by core issue #1116 .
I brought up a potential problem of their proposed solution here:
https://groups.google.com/group/comp.std.c++/browse_thread/thread/69c81befe0cea264?hl=en
. Would be glad if I could hear your opinion on that! I'm also unsure what
exactly they mean with obtaining "storage for an object of a particular type
A".
> 3.8 Object Lifetime / 4. Basically, don't end the lifetime of an
> object with a non-trivial destructor without calling the destructor.
> Undefined behavior results if anything would depend on a result of the
> destructor.
>
I always wondered what "depending" means here. Does it mean that if side
effects are not produced if the destructor invocation is omitted, behavior
is undefined? Or does it mean if undefined behavior would result by omitting
the call to the destructor, behavior would be undefined (i.e then it would
merely a clarifying note?).
Alberto Griggio
Hello,
and thanks a lot for the exhaustive reply first of all.
To be precise, I'm accessing a char * through a Link lvalue, i.e.
chunks->mem. (the snippet above is a bit misleading in that both Chunk and
Link have a member called "next"), but I see your point, thanks.
> How could you fix this? I think the following would work (modulo any
> issues which weren't dealt with in the original code, like running out
> of chunks, alignment, and other things of which I'm unaware atm):
[...]
Ok, let's see if I am understanding you correctly then.
Given what you write above (and after having read also the relevant parts of
the standard again) and your previous example, if I understood everything
correctly, then this should work:
Pool()
{
chunks = new Chunk();
char *start = chunks->mem;
head = new (start) Link();
char *last = &(start[(4-1) * sizeof(Link)]);
for (char *p = start; p < last; p += sizeof(Link)) {
Link *n = new (p + sizeof(Link)) Link();
reinterpret_cast<Link *>(p)->next = n;
}
reinterpret_cast<Link *>(last)->next = 0;
}
void *alloc()
{
Link *p = head;
head = head->next;
return p;
}
void free(void *p)
{
Link *l = new (p) Link();
l->next = head;
head = l;
}
When Pool::free is called, p is a pointer to a memory block that must be
freed, and therefore it will not be accessed from the rest of the program
before a subsequent call to Pool::alloc. Therefore, p is not aliased
anywhere else in the program. Then, I'm starting the life of the POD Link
object by using a placement new. Therefore, it is safe to access l->next in
Pool::free. A similar situtation occurs also in Pool::alloc, since I've used
a placement new in Pool::Pool() for setting up the linked list.
Or am I still wrong?
Alberto
Mathias Gaunard
On Nov 19, 9:17 pm, Alberto Griggio <alberto.grig...@gmail.com> wrote:
> Hello,
> consider the following piece of code, which is a variant of the Pool
> allocator from Stroustroup's book (chapter 19 IIRC)
> [disclaimer, I'm recalling the code from memory, I don't have the book in
> front of me right now]:
>
> struct Pool {
> struct Link { Link *next; };
> struct Chunk {
> Chunk *next;
> char mem[4 * sizeof(Link)];
In addition to violating the strict aliasing rule, there is no
guarantee mem is sufficiently aligned to accept objects of types Link.
Joshua Maurice
If you post some complete code, I might be better able to determine
it's correctness. Are you using the same definitions of chunk and
link?
At the very least, you still have alignment problems for a generic
implementation, which is undefined behavior, which could cause it to
crash. It's possible that you could have a data type, say double,
which requires a certain alignment, and that char array member sub-
object may not be correctly aligned to hold a double object.
I'm not actually sure the best way offhand to deal with the alignment
problem. I would probably first find out what the biggest basic data
type is, pointer, double, whatever, on the hardware which I care
about, and just return memory to the user which is aligned on that
alignment so the user can put whatever object he wants into it. (This
is also a requirement for the type of function the C++ standard calls
"an allocation function". I don't remember much offhand.)
Also, I'm not quite sure what you're trying to do with that new code.
I would probably take my code, ensure it's actually bug free, fix the
alignment issues, and use that. Notice how mine has exactly one cast,
the static_cast in free to get the void pointer back to the Link
pointer - whereas your code has many more casts. Casts should be kept
to a minimum in code, and generally casting is a sign of a bad design.
In this case, I would argue that malloc and free are an example of bad
design, a lack of type safety. This is related to how C also lets
void* be cast to any pointer type implicitly in order to make malloc
not excessively annoying to use, and other similar generic data
structures and algorithms. In C++, this mostly isn't needed because of
new and delete, its type safe containers based on templates. With C+
+0x with variadic templates, void* casting hackery will be needed even
less.
Alberto Griggio
Hello again,
> If you post some complete code, I might be better able to determine
> it's correctness. Are you using the same definitions of chunk and
> link?
Yes, the same definitions as in my initial post. Sorry if this was unclear
(more below).
> At the very least, you still have alignment problems for a generic
> implementation, which is undefined behavior, which could cause it to
> crash. It's possible that you could have a data type, say double,
> which requires a certain alignment, and that char array member sub-
> object may not be correctly aligned to hold a double object.
Your're right, thanks. However, I should have been more explicit in my post,
and say that I was ignoring alignment issues for simplicitly. In the actual
implementation, I'm taking care of alignment properly (well... depending on
the definition of "properly"... let's say that I am reasonably confident
that what I have should work on my target platforms :-)
> I'm not actually sure the best way offhand to deal with the alignment
> problem. I would probably first find out what the biggest basic data
> type is, pointer, double, whatever, on the hardware which I care
> about, and just return memory to the user which is aligned on that
> alignment so the user can put whatever object he wants into it. (This
> is also a requirement for the type of function the C++ standard calls
> "an allocation function". I don't remember much offhand.)
Yes, this is more or less what I'm doing already, thanks.
> Also, I'm not quite sure what you're trying to do with that new code.
> I would probably take my code, ensure it's actually bug free, fix the
> alignment issues, and use that. Notice how mine has exactly one cast,
> the static_cast in free to get the void pointer back to the Link
> pointer - whereas your code has many more casts. Casts should be kept
> to a minimum in code, and generally casting is a sign of a bad design.
> In this case, I would argue that malloc and free are an example of bad
> design, a lack of type safety. This is related to how C also lets
> void* be cast to any pointer type implicitly in order to make malloc
> not excessively annoying to use, and other similar generic data
> structures and algorithms. In C++, this mostly isn't needed because of
> new and delete, its type safe containers based on templates. With C+
> +0x with variadic templates, void* casting hackery will be needed even
> less.
Hmmmm... I'm not sure I follow your here. My new code has exactly two casts,
and the extra one is in the for loop that sets up the links for the whole
chunk, and that in the original post I omitted for brevity (this was denoted
with the "// ..." comment in the original post). Again, my apologies for the
confusion: I should have definitely been clearer here.
Also, it seems to me that your code and mine aren't actually doing the same
thing, and I think this is again due to a lack of complete specification in
my post, which probably confused you... (I thought that the example in
Strousroup's book -- which my original code here basically mirrors -- was
more well known).
The meaning of Chunk in my code is "a region of memory for N objects of size
at most sizeof(Link)" (in the original code N was fixed to be 4). Link is
used to keep the list of free blocks. Whenever a client wants to allocate an
object, a portion (slice, or whatever is the appropriate terminology here,
I'm not sure) of the mem array of the cunk is returned. The protocol is that
the user can occupy at most sizeof(Link) bytes per allocation. When memory
is freed, then, that slice is reinserted into the free list of LinkS, by
putting a Link object in it and attaching it to the top of the head of the
free list. Now, also Chunk has a member called "next", but it's purpose is
different: also chunks are kept in a linked list, because whenever the
memory in the current chunk is exhausted, a new chunk is created and
attached to the list of all chunks. This part of the code was missing in my
original post, because I thought it was not relevant.
I hope the picture is clearer now. On any case, thanks again for your posts,
they helped me a lot in better understanding the strict aliasing rule!
Alberto
Joshua Maurice
Interesting. I looked for active issues on this topic, and I found:
http://www.open-std.org/jtc1/sc22/wg21/docs/cwg_active.html
1116. Aliasing of union members
which allows for even less than what I suggested. It seems like a
reasonable fix though, breaking only really hacky pre-existing
programs. In short, once you allocate storage and put an object in
that storage, you may only reuse that storage to put a new object into
it iff it's legal to access the new object through an lvalue of the
original type.
At least, I think that's the intent. The wording is less than clear.
However, I don't think that's good enough. I think they're trying to
resolve the problem related to the union DR (mentioned in my first
post) by requiring that all aliases to a storage location remain
"valid" for the duration of the storage, aka until the storage is
released.
First, if that is the intent, they should clear up the wording so it
reads "You may reuse storage to put a new object into it iff the new
object can be accessed through all of the lvlalues of all of the
previous objects existing at that storage".
However, it's still not good enough. The following program
demonstrates the problem:
#include <new>
struct A { int x; };
struct B { double y; };
struct C : A, B { void* z; };
int main()
{
char * p = new char[sizeof(A) + sizeof(B) + sizeof(C)];
B* b = new(p) B;
C* c = new(p) C;
}
Presumably we're fine up to and including "B* b = new(p) B". We can
access a "B" object through a char lvalue via the exception in 3.8 /
15, so it's fine under the proposed wording in "issue 1116. Aliasing
of union members".
Next we have "C* c = new(p) C;". Here is where things start getting
fun.
First off, is the requirement that "the 'C' object is accessible
through a char lvalue", or "the 'C' object is accessible through a 'B'
lvalue", or both? In this case, it is accessible through both (quote
unquote), so let's proceed.
Then have a deeper problem. With multiple inheritance and virtual
inheritance, pointer casts are no longer no-ops. That is, a
reinterpret_cast and an implicit cast can and will produce different
results. I would expect that code like above would crash horribly on
real implementations because the "B" sub-object in the "C" object is
not at "offset" 0. By the rules as written, it's fine because you can
access a "C" object through a "B" lvalue, but in practice (and perhaps
by standard?) that only works when the "B" lvalue is ... properly
"aligned(?)". This aspect is not captured at all in the proposed
wording as far as I can tell.
I'll possibly make a DR post to comp.std.c++ in a couple of days, in
which time I hope I get some feedback here.
Rubanets Myroslav
On Nov 19, 10:17 pm, Alberto Griggio <alberto.grig...@gmail.com>
wrote:
> Hello,
> consider the following piece of code, which is a variant of the Pool
It definitely breaks strict aliasing rules.
In our project we hit similar issue with custom pool. GCC reordered
read of next free block and writes by pool item constructor and we got
segmentation fault on one platform.
memcpy() saved our day.
There is similar code in the boost::pool in simple_segregated_storage
so this is a common mistake.
Rant. I hope that people will take back control on what the compiler
is doing somehow.
Best regards, Myroslav Rubanets
George Ryan
On Nov 20, 9:21 pm, Mathias Gaunard <loufo...@gmail.com> wrote:
> On Nov 19, 9:17 pm, Alberto Griggio <alberto.grig...@gmail.com> wrote:
>
>> Hello,
>> consider the following piece of code, which is a variant of the Pool
>> allocator from Stroustroup's book (chapter 19 IIRC)
>> [disclaimer, I'm recalling the code from memory, I don't have the book in
>> front of me right now]:
>
>> struct Pool {
>> struct Link { Link *next; };
>> struct Chunk {
>> Chunk *next;
>> char mem[4 * sizeof(Link)];
>
> In addition to violating the strict aliasing rule, there is no
> guarantee mem is sufficiently aligned to accept objects of types Link.
Can someone elaborate on this?
Alberto Griggio
Hello,
> wrote:
>> Hello,
>> consider the following piece of code, which is a variant of the Pool
> allocator ...>
>
> It definitely breaks strict aliasing rules.
>
> In our project we hit similar issue with custom pool. GCC reordered
> read of next free block and writes by pool item constructor and we got
> segmentation fault on one platform.
>
> memcpy() saved our day.
>
> There is similar code in the boost::pool in simple_segregated_storage
> so this is a common mistake.
>
> Rant. I hope that people will take back control on what the compiler
> is doing somehow.
I think I've almost solved it now, thanks to all the comments of the people here (especially Joshua), and some further digging and playing with the compiler. It turned out that this exposed a GCC bug, fixed in the latest versions, but still present on the
versions which are shipped on commonly-
used "enterprise editions" of some Linux distributions :-(
The relevant bug report is here, in case someone else bumps into this:
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=29286
Alberto