Re: understanding strict aliasing
On Nov 19, 12: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)];
};
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)?
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.
--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]