Virtual tables layout

[Christophe de Dinechin]

Ooops, I just forgot to send this.


Here is a short description of the virtual tables layout. This is
mostly taken out of the existing Taligent runtime.


Virtual tables

Virtual tables (vtables) are used to dispatch virtual functions, to  
access virtual base class subobjects, and to access information for  
runtime type identification (RTTI). Each class that has virtual
member functions or virtual bases has an associated set of vtables.  
The vtable pointers within all the objects (instances) of a class
point to the same set of vtables.


Vtable layout

Each vtable consists of the following parts, in the order listed.
All offsets in a vtable are of type ptrdiff_t.

"Virtual base offsets" are used to access the virtual bases of an
object and to non virtual bases when pointer adjustment is required  
for some overriden virtual function. Each entry is a displacement to  
a virtual base subobject from the location within the object of the  
vtable pointer that addresses this vtable. These entries are only
necessary if the class directly or indirectly inherits from virtual  
base classes, or if it overrides a virtual function defined in a base  
class and if  adjustment from the based to the derived class is
needed. The values can be positive or negative.

"Offset to top" holds the displacement to the top of the object from  
the location within the object of the vtable pointer that addresses  
this vtable. A negative value indicates the vtable pointer is part of  
an embedded base class subobject; otherwise it is zero. The offset
provides a way to find the top of the object from any base subobject  
with a vtable
pointer. This is necessary for dynamic_cast<void*> in particular.
The virtual pointer points to the "offset to top" field.

"Typeinfo pointer" points to the typeinfo object used for RTTI. All  
entries in each of the vtables for a given class point to the same
typeinfo object.

"Duplicate base information pointer" points to a table used to
perform runtime disambiguation of duplicate base classes for dynamic  
casts. The entries in each of the vtables for a given class do not
all point to the same table of duplicate base information.

Function pointers are used for virtual function dispatch. Each
pointer holds either the address of a virtual function of the class,  
or the address of a secondary entry point that performs certain
adjustments before transferring control to a virtual function. [To be  
discussed] In the case of shared library builds, [Solution 1] a
function pointer entry contains the address of a function descriptor,  
which contains the target GP value and the actual function address
[Solution 2] a function pointer entry contains two words: the value  
of the target GP value and the actual function address [Solution 3] a  
function pointer points to an import table generated by the dynamic  
loader, which will transfer control to the target function.

The function pointers are grouped so that the entries for all
virtual functions introduced by a base class are kept together, in
declaration order. Function pointers from a derived class immediately  
follow those for the base class. The order of function pointers
therefore depends on the static type of subobject whose vtable
pointer points to that virtual table.

A vtable pointer in an object addresses the "offset to top" field
of a vtable. This location is known as the address point of the
vtable. Note that the virtual base offsets are at negative
displacements from the address point.

The typeinfo and duplicate base information are covered in separate  
discussions.



Types of vtables

The following categories describe the rules for how vtables of a
class are constructed from the vtables of its bases.

Category 1

This category is for a class that inherits no base classes. If the
class declares no virtual functions, then it has no vtable, and its  
objects have no vtable pointers.

If the class declares virtual functions, then it has a single vtable  
containing RTTI fields followed by function pointer entries. There  
is one function pointer entry for each virtual function declared in  
the class. The vtable pointer in an object of the class addresses
this vtable.

Category 2

This category is for a class that inherits only non-virtual base
classes, and the non- virtual base classes have no base classes, and  
there is no adjustment in any of the overriden virtual functions.

If none of the base classes have vtables, a vtable is constructed
for the class according to the same rules as in Category 1. Otherwise  
the class has a vtable for each base class that has a vtable. The
class's vtables are constructed from copies of the base class
vtables. The entries are the same, except:
- The RTTI fields contain information for the class, rather than
for the base class.
- The function pointer entries for virtual functions inherited from  
the base class and
overridden by this class are replaced with the addresses of the
overridden functions
(or the corresponding adjustor secondary entry points),
- At negative offsets, offsets to the base classes are generated if  
used by adjustor secondary entry points.

Informally, each of these vtables has a name in the form
Base-in-Derived vtable, where Base is a base class and Derived is the  
derived class. Each vtable pointer in an object addresses one of
these vtables for the class. The vtable pointer of an A subobject
within a B object would address the A-in-B vtable.

The vtable copied from the primary base class is also called the
primary vtable; it is addressed by the vtable pointer at the top of  
the object. The other vtables of the class are called secondary
vtables; they are addressed by vtable pointers inside the object.


Aside from the function pointer entries that correspond to those of  
the primary base class, the primary vtable holds the following
additional entries at its tail:
- Entries for virtual functions introduced by this class
- Entries for overridden virtual functions not already in the
vtable. (These are also called replicated entries because they are
already in the secondary vtables of the class.) [I wonder if this is  
actually needed, this seems to be a consequence of RRBC]

The primary vtable, therefore, has the base class functions
appearing before the derived
class functions. The primary vtable can be viewed as two vtables
accessed from a shared
vtable pointer.


Note Another benefit of replicating virtual function entries is
that it reduces the number of this pointer adjustments during virtual  
calls. Without replication, there would be more cases where the this  
pointer would have to be adjusted to access a secondary vtable prior  
to the call. These additional cases would be exactly those where the  
function is overridden in the derived class, implying an additional  
thunk adjustment back to the original pointer. Thus replication saves  
two adjustments for each virtual call to an overridden function
introduced by a non-primary base class.


Category 3

This category is for a class that inherits only virtual base
classes, and the virtual base classes have no base classes.

The class has a vtable for each virtual base class that has a
vtable. These are all secondary vtables and are constructed from
copies of the base class vtables according to the same rules as in
Category 2. The vtable pointers of the virtual base subobjects within  
the object address these vtables.

The class also has a vtable that is not copied from the virtual base  
class vtables. This vtable is the primary vtable of the class and
addressed by the vtable pointer at the top of the object, which is
not shared. It holds the following function pointer entries:
- Entries for virtual functions introduced by this class
- Entries for overridden virtual functions. (These are also called
replicated entries, because they are already in the secondary vtables  
of the class)

The primary vtable also has virtual base offset entries to allow
finding the virtual base subobjects. There is one virtual base
offset entry for each virtual base class. For a class that inherits  
only virtual bases, the entries are in the reverse order in which the  
virtual bases appear in the class declaration, that is, the entry
for the leftmost virtual base is
closest to the address point of the vtable.


Category 4

This category is for a class that directly or indirectly inherits
base classes that are either virtual or non-virtual.

The rules for constructing vtables of the class are a combination of  
the rules from Categories 2 and 3, and for the most part can be
determined inductively. However the rules for placing virtual base
offset entries in the vtables requires elaboration.

The primary vtable has virtual base offset entries for all virtual
bases directly or indirectly inherited by the class. Each secondary  
vtable has entries only for virtual bases visible to the
corresponding base class. The entries in the primary vtable are
ordered so that entries for virtual bases visible to the primary base  
class appear below entries for virtual bases only visible to this
class.

For virtual bases only visible to this class, the entries are in the  
reverse order in which the virtual bases are encountered in a
depth-first, left-to-right traversal of the inheritance graph formed  
by the class definitions. Note
that this does not follow the order that virtual bases are placed in  
the object.



[To be discussed] Vtables for partially constructed objects

In some situations, a special vtable, called a construction vtable
is used during the execution of base class constructors and
destructors. These vtables are for specific cases of virtual
inheritance.

During the construction of a class object, the object assumes the
type of each of its base classes, as each base class subobject is
constructed. RTTI queries in the base class constructor will return  
the type of the base class, and virtual calls will resolve to member  
functions of the base class rather than the complete class. Normally,  
this behavior is accomplished by setting, in the base class
constructor, the object's vtable pointers to the addresses of the
vtables for the base class.

However, if the base class has direct or indirect virtual bases, the  
vtable pointers have to be set to the addresses of construction
vtables. This is because the normal base class vtables may not hold  
the correct virtual base index values to access the virtual bases of  
the object under construction, and adjustment addressed by these
vtables may hold
the wrong this parameter adjustment if the adjustment is to cast
from a virtual base to another part of the object. The problem is
that a complete object of a base class and a complete object of a
derived class do not have virtual bases at the same offsets.

A construction vtable holds the virtual function addresses and the
RTTI information associated with the base class and the virtual base  
indexes and the addresses of adjustor entry points with this
parameter adjustments associated with objects of the complete class.

To ensure that the vtable pointers are set to the appropriate
vtables during base class construction, a table of vtable pointers,  
called the VTT, which holds the addresses of construction and
non-construction vtables is generated for the complete class. The
constructor for the complete class passes to each base class
constructor a pointer to the appropriate place in the VTT where the  
base class constructor can find its set of vtables. Construction
vtables are used in a similar way during the execution of base class  
destructors.