Type punning, code reordering and overloaded operator new() withcustom allocator

[chris42f]

Hi all,

I'm having some trouble understanding how the strict aliasing rules
apply to
code reordering across a call to operator new() when using a custom
allocator.
(The reordering is due to compiler optimizations.)

I'm not the original author of the allocator and by no means an
expert, but it
seems like a typical simple free-list based allocator for fixed-sized
objects.
Internally the allocator works by keeping a linked list of unused
object-sized
blocks of memory, with the link pointers embedded inside the unused
blocks.

When alloc() is called, a new block is returned from the front of the
list.
If the list is empty, a new chunk (large compared to the objects being
allocated) is allocated and filled with links.

When free(void* p) is called, the memory pointed to by p is added to
the front
of the list to be reused by the next alloc(). Here is the complete
allocator
code for reference. It's not incredibly long, so I hope it's OK to
post here -
the important part is the alloc() function.

//------------------------------------------------------------------------------
template <class T, int CS=8>
class CqObjectPool
{
struct SqLink
{
SqLink* m_next;
};
struct SqChunk
{
enum { size = CS*1024-16, };
SqChunk* m_next;
char m_mem[size];
};
SqChunk* m_chunks;

const unsigned int m_esize;
SqLink* m_head;

void grow() // Allocate new 'chunk', organize it as a
linked list of elements of size 'm_esize'
{
SqChunk* n = new SqChunk;
n->m_next = m_chunks;
m_chunks = n;

const int nelem = SqChunk::size/m_esize;
char* start = n->m_mem;
char* last = &start[(nelem-1)*m_esize];
for (char* p = start; p<last; p+=m_esize) // assume
sizeof(SqLink)<=m_esize
reinterpret_cast<SqLink*>(p)->m_next =
reinterpret_cast<SqLink*>(p+m_esize);
reinterpret_cast<SqLink*>(last)->m_next = 0;
m_head = reinterpret_cast<SqLink*>(start);
}

// debug function, exists so I can easily find what I'm after
in the
// generated assembly
void printHead() __attribute__((noinline))
{
std::cout << m_head << "\n";
}

public:
CqObjectPool()
: m_esize(sizeof(T)<sizeof(SqLink*)?
sizeof(SqLink*):sizeof(T))
{
m_head = 0;
m_chunks = 0;
}

~CqObjectPool() // free all chunks
{
SqChunk* n = m_chunks;
while(n)
{
SqChunk* p = n;
n = n->m_next;
delete(p);
}
}

void* alloc()
{
printHead();
if (m_head==0)
grow();
SqLink* p = m_head;
m_head = p->m_next;
return(p);
}

void free(void* b)
{
SqLink* p = static_cast<SqLink*>(b);
p->m_next = m_head;
m_head = p;
}
};
//------------------------------------------------------------------------------

My problem is with interpreting how the strict aliasing rules should
apply to
the fact that we're accessing the allocated memory blocks in two ways:
1) As the link type inside alloc(), used to maintain the linked list,
and
2) As the object type T which is to be allocated.

I have code which uses the object pool via overloading operators new
and
delete as follows:

class CqLath
{
public:
CqLath( /* some args */ )
: m_pClockwiseVertex(0)
// other instance data
{ }

// lots of methods
// ...

void* operator new( size_t size )
{
return( m_thePool.alloc() );
}
void operator delete( void* p )
{
m_thePool.free( p );
}
private:
CqLath* m_pClockwiseVertex;
// ... more instance data

// The following allocator will allocate all objects of type
CqLath
static CqObjectPool<CqLath> m_thePool;
};

// allocate an object (inside some loop)
CqLath* pLathA = new CqLath( /* some args */ );

I found that this was causing a very large amount of memory to be
allocated,
but only on when compiling with optimizations (-O3 with gcc-3.4.4 or
gcc-3.4.6). Unfortunately the problems went away when debug
information
was turned on.

After a very frustrating day (eventually degenerating into reading the
generated assembly code), I've tracked this down to reordering of
operations
by the compiler. What is happening is a corruption of the linked list
held by
the allocator such that a new (large) chunk is allocated each time
alloc() is
called, rather than taking the first block off the linked list.

In particular, in the line calling the operator new above,
1) alloc() is inlined
2) the constructor is inlined, immediately following alloc()
3) code from alloc and the constructor get mixed, such that the update
of the
m_head link uses the memory for the object which has just been
overwritten by
the object constructor. That is, the following

// alloc()
printHead();
if (m_head==0)
grow();
SqLink* p = m_head;
m_head = p->m_next;
// constructor
CqLath* pLathA = (CqLath*)p;
pLathA->m_pClockwiseVertex = 0;
// init other instance data

turns into

// mixed alloc() and CqLath constructor
printHead();
if (m_head==0)
grow();
SqLink* p = m_head;
CqLath* pLathA = (CqLath*)p; // < Reinterpretation conceptually
inserted here by the compiler for operator new
pLathA->m_pClockwiseVertex = 0;
m_head = p->m_next; // < This has been moved to *after* the
constructor

When written out in full like this, it looks as though our code breaks
the
strict aliasing rules, and indeed when compiled with -fno-strict-alias
(using
gcc-3.4.4 on x86_64 linux) the problem magically goes away. This
makes some
sense, since according to strict aliasing, a compiler should be free
to
reorder if it knows two pointers cannot alias each other.

However, it seems like highly non-obvious behaviour to reorder around
calls to
new(), and something which AFAICT is impossible to work around with
the usual
hacks based on type-punning with unions - the problematic cast from p
to
pLathA is nothing we have control over.

So, the real question:
Q: Is the implicit type-punning and resulting reordering around a call
to new
my fault, or is this a compiler bug?

If someone could provide a little light I'd be most grateful. I've
already
found that the problem doesn't occur with gcc-4.1.2, but maybe it's a
bug in
gcc-3.4.* ... Before I blame the compiler, I'd really like to know if
it's
our code violating the aliasing assumptions.

Thanks, and apologies for the mammoth post,
~Chris F.