problems with empty base layout algorithm

[allen.chan at ca.ibm.com]

I probably misread the procudure in the document. Now that you clarified the
intent of the algorithm, it makes sense to me now. Please update the document by
adding the clause on how to handle component conflict to the empty base layout
procedure as well.

thanks,
Allen
--
Internet: allen.chan at ca.ibm.com
Notes: Allen Chan/Toronto/IBM at IBMCA
IBM TieLine 8-778-3908 / Tel 416-448-3908
VisualAge C++ Kernel Development
My opinions are my own.


dehnert at baalbek.engr.sgi.com (Jim Dehnert) on 09/09/99 01:46:08 AM

Please respond to dehnert at baalbek.engr.sgi.com (Jim Dehnert)

To:   cxx-abi at corp.sgi.com, Allen Chan/Toronto/IBM at IBMCA
cc:
Subject:  Re:  problems with empty base layout algorithm




> Date: Wed, 8 Sep 1999 16:51:02 -0400
> Reply-To: allen.chan at ca.ibm.com
>
> Looking at the non-virtual-base allocation procedure as outlined in the Data
> Layout document, I noticed a couple of problems with the empty base layout
> algorithm.
>
> Consider the following scenario:
>
> struct A {};
> struct B : public A {};
> struct C : public A {};
> struct D : public A {};
> struct E { int e; }
> struct F : public B, public C, public D, public E { };
>
> For the most derived class F, base classes B, C and D are empty bases. To map
> class F, we firsts have to allocate all base classes of F in declaration
order.
> If we were to follow the described procedure, this is what we will get:
>
> 1. The empty base B will be allocated at offset zero.
> 2. The empty base C (which has a type conflict with B, since they have the
same
> non-virtual base A), will be allocated at dsize(F), which is zero.

This isn't the intent (nor what's written, though perhaps not
clearly).  We attempt offset zero, which doesn't work because of the
type conflict with B.  Then we "proceed with attempts at dsize(C) as
for non-empty bases."  Such attempts, "[if] a component type conflict
occurs, increment the candidate offset by align(type(D)), and try again,
repeating until success occurs..."

So, when dsize(C) doesn't work (it's zero, and it still doesn't work),
we try dsize(C)+1, dsize(C)+2, ..., until one of them does work.
No subobject is placed without first verifying absence of type
conflicts.

> 3. The empty base D (which has a type conflict with B and C), will be
allocated
> at dsize(F), which is zero.
> 4. The base E will be allocated at dsize(F), which is zero.
> 5. sizeof(F) = 4.
>
> So, even though B, C and D conflict with each other, they are all allocated at
> offset zero.
>
> To solve the problems, I am proposing the following changes to the
> algorithm for lying out empty bases:
>
> 1. Maintain an index, ebase(C), which denotes the current offset for
> allocation of empty bases. In the beginning, ebase(C) = 0.
> 2. For each empty base class D in C,
>      2a. If D and all its non-virtual base classes have not been allocated
> before, place D at offset zero.
>      2b. If D or any of its non-virtual base classes have been allocated
before,
> place D at ebase(C) + 1. Update ebase(C) = ebase(C) + 1.

There's no reason to update ebase(C) unless the _next_ empty base
conflicts in type.  In addition, updating it doesn't guarantee that the
next empty base class won't conflict, since it (or a subclass) may
conflict with some part of an earlier-allocated base class.

> 3. After all components (virtual and non-virtual components) of C have been
laid
> out, update sizeof(C) to max(sizeof(C), ebase(C)).

-        Jim Dehnert          dehnert at sgi.com
                    (650)933-4272