Re: understanding strict aliasing
Hello,
and thanks a lot for the exhaustive reply first of all.
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.
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):
[...]
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.
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
--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]