The wrong side of the war

I picked the wrong side...I've done a lot of work on PPC hardware, I think in Big Endian,
and I can read PPC assembly. With Apple's move to x86 hardware, how is that useful??

I thought this link provides a nice intro into stack frames and register usage in x86 assembly. This is very important - the x86 has so few registers that code that looks clean and simple on the PPC gets quite obtuse as things get juggled around. Between that, 453 addressing modes and 102,249 instructions, x86 assembler can look like the mad scribblings of Russel Crow in "A Beautiful Mind".

Any idea what this does? :-)

0x00000000: 55 push ebp
0x00000001: 89E5 mov ebp,esp
0x00000003: 56 push esi
0x00000004: 83EC04 sub esp,0x4
0x00000007: B8CCCCCCCC mov eax,0xcccccccc
0x0000000c: 890424 mov dword ptr [esp],eax
0x0000000f: C745F800000000 mov dword ptr [ebp-0x8],offset ?b@@3Vbar@@A
0x00000016: 8B45F8 mov eax,dword ptr [ebp-0x8]
0x00000019: 8B5004 mov edx,dword ptr [eax+0x4]
0x0000001c: 89D1 mov ecx,edx
0x0000001e: 8B31 mov esi,dword ptr [ecx]
0x00000020: 89D1 mov ecx,edx
0x00000022: FF16 call dword ptr [esi] near
0x00000024: 8B1504000000 mov edx,dword ptr ?b@@3Vbar@@A+0x4
0x0000002a: 89D1 mov ecx,edx
0x0000002c: 8B31 mov esi,dword ptr [ecx]
0x0000002e: 89D1 mov ecx,edx
0x00000030: FF16 call dword ptr [esi] near
0x00000032: B800000000 mov eax,0x0
0x00000037: 8D65FC lea esp,dword ptr [ebp-0x4]
0x0000003a: 8B3424 mov esi,dword ptr [esp]
0x0000003d: 8B6C2404 mov ebp,dword ptr [esp+0x4]
0x00000041: 83C408 add esp,0x8
0x00000044: C3 ret near

C++ Objects Part 7: Dynamic Casts and Ambiguous Bases

Continuing with our discussion of how C++ objects are implemented in CodeWarrior, let's look at dynamic casts when an ambiguous base class is present.

Because a dynamic cast always down-casts to the full class, and then goes back up, a cast that would be trivial for a static cast becomes more complex for dynamic cast, and can introduce ambiguous base cases that otherwise would not be an issue. But you really have to work to see this. Here is a class hierarchy that requires run-time resolution of a dynamic cast with an ambiguous base:

class R { };
class A : public R { };
class B1 : public A { };
class B2: public A { };
class D: public B1, public B2 { };

So what do we have to do to get an ambiguous base class dynamic cast?

First declare an instance of D.

Then cast a pointer to D to B1, then R. (We must cast to R via B1 because the up-cast from D to R is ambiguous - we have two equally valid copies of R within D.)

Now dynamic cast from our pointer to R to a pointer to A. What happens?

Not what you think? You might think that since A has one copy of R, we simply update the pointer and go home, but the dynamic cast must do runtime checks to make sure that we really are an R that is embedded in A. So the dynamic cast operator casts R all the way down to its full class (D) and then tries to up-cast from D to A, which is ambiguous. Oops!

The type-info structure has enough information to manage this. Every type-info structure has an array of all base classes (both direct and indirect).

An ambiguous base class has a flag, indicating that it is ambiguous (it will be listed multiple times) and an integer indicating how many of the following classes are all accessed via the ambiguous base class.

(This implies that we have to iterate over the base class array because it is not a true array - the items are variable size!)

There are a lot of conditions on using an ambiguous base class as we search for our class when looking at the list of base classes for a type during a dynamic cast. We must meet three conditions:

- We can only accept a base class if it is the same as the destination type we are casting too.
- We can only accept a base class if its offset in the struct matches the offset we used to get from our initial pointer to our full type.
- We can only accept base class if our starting type is a parent class of this particular base class.

What that means is: we can only cast to am ambiguous base directly from one of its parents. If we do, we need to make sure we have the right copy of this ambiguous base, which is why we check not only the type name, but the offset to this base from the full object (which disambiguates it.)

(How is this possible when this layout will vary from full class to full class? Well, remember that EVERY base that EVER goes into a class is part of the casting table for a type-ID, and you never have to use more than one type-id structure to perform a cast. So when we say "class D has two A's, one at 0 bytes and one at 16 bytes", that info is truly only in the typeID for class D. For some other class (also with A) we'd have a totally different set of casting info. In other words, the casting info is effectively contained WITHIN the typeID so that it can be unique to this FULL class.)

Note one case that won't cast for us:

R1
R2
A: R1, R2
B1: A
B2: A
D: B1, B2

Given obj of type D and a ptr via R1 (through B1), we can't dynamic cast from R1 to R2. Why? When we iterate through the ambiguous bases (A) we haven't STARTED on an A so we don't find the perfect match to the A from B1. Thus we fail with a bad cast!

(Is this right? I think so. As far as I can tell from the C++ spec, dynamic cast must succeed when we explicitly down-cast and the full class has some ambiguity in it, but cross-casts do not have to succeed. So casting from R1 to A is legal, but casting from R1 to R2 is not. This isn't hugely surprising, and I suspect that if your design depends on this cast, you need to reconsider the design!)

Debugging Memory Value Meanings

The Visual Studio compiler automatically assigns default values to certain types of variables depending on how they were declared (stack based vs heap based) and what types of variables they are (pointers etc). These values become very useful during debugging because you can tell what went wrong when an exception is thrown. Here are some common values and their meanings:

• 0xfeeefeee - Memory reserved to heap allocation but has not been allocated yet
• 0xcdcdcdcd - Uninitialized heap variable (Think of the "C" as Clean memory)
  
• 0xcccccccc -Uninitialized stack variable (Think of the "C" as Clean memory)
• 0xfdfdfdfd - Padding around an array (Think of the "F" as Fences around your variable)
• 0xdddddddd - Released heap variable (delete or free) (Think of the "D" as in Dead)
  

C++ Objects Part 6: Ambiguous Base Classes

An ambiguous base class is a base class that is included in a derived class twice. Because you can't just derive from a class twice, this usually happens by having parent classes who both derive from the same class without virtualizing that common base.

The storage implications of ambiguous base classes are relatively simple. Because each parent class's memory layout contains the base, we know where the two bases will be in memory - we simply apply our pattern for inheritance via containment recursively.

class R { };
class B1 : public R { };
class B2 : public R { };
class D : public B1, public B2 { };

gives us

struct R {
vtable * vt;
};

struct B1 {
R base;
};

struct B2 {
R base;
};

struct D {
B1 base;
B2 base;
};

Thus we have two instance of R: obj.base1.base and obj.base2.base reference each copy of R.

Static casts are casts that can be computed knowing only compile-time information - that is, casts that don't require knowing the full class of the casted object.

A static cast from D to R is illegal because it is ambiguous. Do we want R via B1 or B2? We don't know, and because the cast is static the compiler knows we don't know at compile time and generates an error.

If you cast to B1 first and then R it is legal - you have disambiguated. (This should not be surprising - if we simply had an object of type B1, casting to R would work! Remember, memory layout doesn't change with type!)

Static casts give us compile-time checking of all casts for ambiguity - we always know what we are getting. Next I'll cover dynamic casts and ambiguous base classes, which are more complex.

C++ Objects Part 5: Virtual Base Classes

A virtual base class is a class that is included only once in your derived class no matter how many base classes refer to it. How does this happen?

The answer is two-fold:

First, the actual layout of a class with a virtual base depends on the full class. Consider this case:

class R { };
class B1 : public virtual R { };
class B2 : public virtual R { };
class D : public B1, public B2 { };

In this case R is a virtual base that is included twice in D. The location of R will be different for B1, B2 and D. Each time one of these classes is set up, R is placed in the class once. Since R cannot be in D twice, clearly the location of R relative to B1 and B2 can't be the same when B1 or B2 is the final class vs. D. (If both B1 and B2 took R with them, we'd have two copies in D, which is not acceptable!)

To get around this, we hit the second part of our answer: classes contain pointers to their virtual bases. With non-virtual containment, bases are contained, e.g. a fixed chunk of the derived class's memory is used for the base class. With a virtual base, the derived class simply contains a pointer to the base class. This lets us move R around and adjust the pointer to R (in B1 or B2) at runtime in a way that lets us use different memory layouts for R with various classes that contain B1 or B2.

It should be noted that in D while there is only one copy of R, there are multiple pointers to R - one in B1 and one in B2. This is what assures that the memory layout of B1 and B2 don't change when they are used in a derived class. Only the contents of the layout of B1 and B2 change. The compiler generates code to set up these pointers for us.

For CodeWarrior, pointers to virtual bases come before the pointer to the vtable. This means that to find the vtable we have to know how many virtual bases a class has. Fortunately this information is dependent only on class info that is available at compile time - it never changes.

Here's a C version of what we have above:

struct R {
R_vtable * vtbl;
// R data
};

struct B1_partial {
R * vbase;
B1_vtable * vtbl;
// data for B1
};

struct B1_final {
B1_partial self;
R vbase;
};

struct B2_partial {
R * base;
B2_vtable * vtbl;
// data for B2
};

strut B2_final {
B2_partial self;
R vbase;
};

struct D {
R * vbase;
R vbase_data;
B1_partial base1;
B2_partial base2;
};

One of the interesting things to note here is that B1 and B2 as included in D are not as large as B1 and B2 when used by themselves. This is because B1 and B2 must have storage for the virtual base R at their end when used by themselves. But when used in D, that storage is provided by D.

Now we can see why dynamic cast first goes to the most derived base. Given a ptr to R we have no
idea where the rest of the object is -- position of R varies with the actual final type - that is, the relative position of R in the object is not the same relative to B1 if the real object is B1 or D.

Fortunately the vtable of any object tells us where the final object's real start is. So when R is a virtual base, depending on its final type, it will refer to a vtable that takes into account the actual full class's layout, letting us recover the full type and figure out the true relationship between the virtual base and the whole object.

Note that a static down-cast from a virtual base will cause a compiler error. This is the compiler telling us that it can't even speculate what the memory layout of the virtual base in the final class might be without inspecting the real type at runtime. But dynamic down-casts and even cross-casts are legal, since all dynmic casts are a maximum down cast followed by a possible up-cast.

C++ Objects Part 4: typeid and casts

Now that we have described how multiple inheritance in CodeWarrior C++ works, we can look at how casting and type works in C++. We needed to discuss multiple inheritance first; recall from part 2 that for single inheritance, the "front" of an object in memory is its base. With this system, no work is needed at all to cast when we have only one base class.

For the purpose of this discussion, "full class" means the actual class of an object when it is instantiated - in other-words, the "biggest" downcast we can apply - it's real class.

Please also remember from our previous post that an object that inherits from two base classes has at least two vtables with different layouts. Clearly a pointer to a vtable is not a unique identifier of an object's class, if one object can have two different vtable pointers of different values.

So instead CodeWarrior creates a separate static structure for each class that uniquely identifies it: a type_info structure. This shouldn't be surprising - this is the same structure that you can use with the typeid operator. That is if you do this:

D obj;
const std::type_info& t = (typeid(obj));

"t" is a pointer to the internal type_info structure for class D that is used by the runtime for all operations that require typing. (t is a pointer - it looks like a reference in the C++ code, but in truth they are one and the same to the compiler.)

Every vtable starts with a pointer to a type_info structure, identifying the full type of an object. When an object has two vtables (as in our multiple inheritance case), both vtables point to the same type_info structure. No two classes will ever share a vtable (even if a derived class never overrides any member functions) so this is okay. Because both vtables point to the same type_info, we can get our full runtime class for an object no matter which base we have a pointer to.

Static Casts

With this in mind, let's look at static casts. A static cast is a cast between C++ class types whose effects are fully known at compile time. That is, the compiler uses compile-time type information to change the type (and possibly the pointer value) for an object. The compiler looks at the layout in memory of the base class and the derived class and adjusts the pointer as much as is needed. (When we have only one base class, a static cast will not need to adjust the pointer at all, because the base class is always first in memory.)

There are some casts that cannot be performed statically at all, but we will get to this later. Also, we can't check whether the cast is safe at compile time. If we have a pointer to X that we cast to type Y but the object is not actually of type Y, the compiler will not care and we may crash later.

Full Class and Offsets

When we first introduced the layout of a vtable we mentioned that there is an "offset" right after the type_info. But what is this offset?

The offset in a vtable is the number of bytes that a pointer to an object whose type uses this vtable must be adjusted to find the full class of the object.

So in our case where we have two bases, each embedded somewhere in a class, the vtable of each base contains the offset to recover the full object. Note that one vtable will probably have an offset of 0, and this vtable is the one we will use for the "full" class, so that we never adjust the pointer when we already have the full class.

(As far as I can tell, CodeWarrior layers all static vtables for a class consecutively, so when given a pointer to the first one, it can actually generate calls into any vtable, because their relative positioning is fixed.)

Dynamic Casts

A dynamic cast converts the type of an object using run-time information. The cast returns NULL if the object can't be viewed as a given type. Since dynamic casts look at the object at run-time and can see the full class of the object, they can perform casts that we can't do using only compile-time information.

(Consider a DLL that returns an object of some unknown type, but as a pointer to a base type. Without run-time type information, the compiler has no idea what real type that object is, because it doesn't have the source code. In practice even if we did have the code, the compiler can't track that object's pointers through all of the strange things C++ can do to memory.)

A dynamic cast works by examining the type_info structures of an object and using that information to perform the cast. So to understand dynamic casts, we'll need to look a the type_info structure.

The type_info structure contains a pointer to a static string that names the class - all dynamic casts will use class string-name comparisons to find equivalent type. It then contains a pointer to a "null-terminated" variable-length array of info about base classes. Each item in this array contains a pointer to the type_info of a base class (if this pointer is null, that indicates null termination) and an offset indicating how much the pointer to the full object must be adjusted to cast to this type.

It should be noted that this list of base classes contains all bases, not just immediate bases! In other words, if we have a class Z that derives from Y and Y derives from X, the array of base classes for Z contains X and Y! This means that with a single linear search of the list, we can find any possible base. We do not have to search the entire tree.

(As a side note, each type_info's array contains pointers to parents, so you can follow the chain of inheritance from type_info to type_info. As far as I can tell in CodeWarrior there is no recording of which bases are "immediate bases", as you never need this info in C++. Perhaps the order of the bases in the list would tell us but I am not sure.)

Dynamic cast is therefore a two-step process:

1. Given the vtable of a pointer to an object, use the offset to recover a pointer to the full class. (All adjustments will then be made from this pointer.) This is the equivalent of down-casting to the full class.

2. Search the type_info of the full class for the type we want - in other words, go through a list of all bases. If we find one, use the offset to adjust the pointer again. If the search in step 2 fails, return NULL.

(I am leaving out ambiguous base classes - we'll cover that later!)

C++ Objects Part 3: Multiple Inheritance

In my previous post I described how single inheritance works with the CodeWarrior C++ compiler - by placing the superclass as the first item in the subclass in memory (and pulling the same trick for the vtable). Now to something more complicated: multiple inheritance!

One thing is clear: we can't do the same trick for multiple inheritance as we can for single inheritance...only one superclass can be first!

The trick: change the pointer when we change the "class" of the pointer. We simply stick both bases into our subclass, but if we cast from the superclass to the second base, we move the pointer in memory to point to the second base class (since it isn't at the same address).

You can see this for yourself with a program like this:
class a { int a_; };
class b { int b_; };
class c : public a, public b { };
int main()
{
c obj;
printf("a=0x%08x, b=0x%08x, c=0x%08x\n", (a*)&obj,(b*)&obj,(c*)&obj);
}

When we print out a ptr to our object casted, we get this
a=0xbffff460, b=0xbffff464, c=0xbffff460

Note that when we cast to b, the address of our pointer moves in memory! This is because c contains a first in memory, then b second.

So we've at least solved the problem for object data: we'll put the base classes into the derived class sequentially and adjust the pointer any time we change the type, so that we point to the base WITHIN the derived class no matter where it is. This meets our rule that a pointer to the base must look like the base. It does because we move the pointer until it does.

Now let's apply the rule to vtables. We must have a pointer to a vtable as the first item in an object. So if the pointer to an object can point to either of two memory locations (the start of the first or second base) then we can't escape logic: we need TWO pointers to vtables!

The format of a vtable depends on the class we think we have; the contents of a vtable depend on the class we really have. So when we have multiple inheritance, we will have multiple vtables, so that each one can be formatted based on the base class (but filled with function pointers from the derived classes.

This example will get lengthy, so I will abridge it a little bit...

class B1 { virtual void b1(); };
class B2 { virtual void b2(); };
class D : public B1, public B2 { virtual void b1(),virtual void b2(),virtual void d(); } ;

In C we might have this:

struct B1_vtable {
typeid * type_id_ptr;
int offset;
// ptrs to B1 virt funcs
};
struct B2_vtable {
typeid * type_id_ptr;
int offset;
// ptrs to B2 virt funcs
};
struct D_vtable {
B1_vtable parent1;
B2_vtable parent2;
// ptrs to D vfuncs
};

Because D contains the first base's virtual function table first, the "header" information (type-id and offset) for the first base are used for the derived class. This will be important later. Because all of the virtual functions are consecutive in memory, when we have the derived class we can easily find any virtual method's function pointer.

(So when I say we have two vtables really we have one big vtable with two vtables embedded inside it.)

void B1_b1() {}
void B2_b2() {}
void D_b1() {}
void D_b2() {}
void D_d() {}

static type_id B1_type_id = { ... };
static type_id B2_type_id = { ... };
static type_id D_type_id = { ... };

// Virtual functions for B1:
static D_vtable sB1_vtable = { &B1_type_id, 0, B1_b1 };
// Virtual functions for B2:
static B2_vtable sB2_vtable = { &B2_type_id, 0, B2_b2 };

So far there are no surprises here, until we look at the virtual function tables for D:

// Virtual functions for D
static D_vtable sD_vtable = { { &D_type_id,0, D_b1 }, { &D_type_id, -sizeof(B1), D_b2 }, D_d };

Here we have a vtable that contains two vtables within it. Thus we have two pointers to our type-IDs. If we have a pointer to the second one, it looks like the vtable used when looking at our object of type D as if it was a B2. Remember that the pointer to the object changes as we cast, and that controls which vtables is used. (Whenever we call the virtual method b2(), we have a pointer to a B2* and therefore our object pointer is adjusted to the second vtable where we get a D_b2 object.

This is the first time the 'offset' parameter of the vtable isn't 0. I'll explain this in the next post, but for now trust that, since B2 is not the first parent class inside D, it needs a non-zero offset.

struct B1 {
B1_vtable * vtable;
// data for b2
};

struct B2 {
B2_vtable * vtable;
// data for b2
};

struct D {
B1 base1; // base1.vtable inited to &sD_vtable.parent1
B2 base2; // base2.vtable inited to &sD_vtable.parent2
// derived data for D
}

When D is initialized, the vtable for B1 is inited to one value and the vtable for B2 is inited to another value.