Friday, February 17, 2006

Demystifying virtual functions

Yesterday, I got caught up with a problem where a virtual function in a derived class was never getting called. Foolishly, I decided to see how gcc implemented virtual functions and what I was doing wrong, instead of debugging the code from a different angle (vis-a-vis gdb). Anyway, it turned out, the virtual function was indeed getting called, and the problem was in another part of the code. But, the silver lining of all this heinous activity was that I kinda got an idea of how virtual functions are actually implemented by the compiler. Let's start with some basic code.

class BASE_CLASS
{
public:
virtual void PRINT_FUNCTION(void);
};

class DERIVED_CLASS : public BASE_CLASS
{
public:
void PRINT_FUNCTION(void);
};

void BASE_CLASS::PRINT_FUNCTION(void)
{
printf("Base Function\n");
}

void DERIVED_CLASS::PRINT_FUNCTION(void)
{
printf("Derived Function\n");
}

int main()
{
DERIVED_CLASS *dobject=new DERIVED_CLASS;
dobject->PRINT_FUNCTION();
return 0;
}

This has to be self-explanatory. Obviously, the print from the above code, if run, would be "Derived Function". The basic concepts of how virtual functions are implemented using vtables & vptr are explained beautifully here. To surmise, each object has a vptr that points to the correct vtable of the class, where the vtable is a list of pointers to virtual functions defined in that class.

Now, let's put this code under the magnifying glass.

g++ -fdump-tree-gimple -fdump-class-hierarchy -S virtual.cpp

Compiling it with -fdump-tree-gimple gives us the GIMPLE output, which I recently found out from here.
-fdump-class-hierarchy "dumps a representation of each class' hierarchy and virtual function table layout to a file." (quoting the man page of gcc).
-S gives us the assembler output.

Before analyzing the dumps, let me just explain whatever little name-mangling I had to learn for this experiment. The G++ ABI mangles all names with a preceding _Z. After this, certain patterns occur, followed by the mangled name :

TV - Vtables. Pointed to by polymorphic objects and those with virtual bases.
TI - Type information. Returned by the typeid operator, pointed to by the vtable.
TS - Type string. Returned by type_info::name, and used for type comparisons.
In most of the cases, the mangled name consists of two things - a number specifying the length of the string following and the string itself (usually the name of a class or a function).

Okay, let's look at the class hierarchy dump first:

Vtable for BASE_CLASS
BASE_CLASS::_ZTV10BASE_CLASS: 3u entries
0 (int (*)(...))0
4 (int (*)(...))(& _ZTI10BASE_CLASS)
8 BASE_CLASS::PRINT_FUNCTION

Class BASE_CLASS
size=4 align=4
base size=4 base align=4
BASE_CLASS (0xb7d1bbc0) 0 nearly-empty
vptr=((& BASE_CLASS::_ZTV10BASE_CLASS) + 8u)

Vtable for DERIVED_CLASS
DERIVED_CLASS::_ZTV13DERIVED_CLASS: 3u entries
0 (int (*)(...))0
4 (int (*)(...))(& _ZTI13DERIVED_CLASS)
8 DERIVED_CLASS::PRINT_FUNCTION
Class DERIVED_CLASS
size=4 align=4
base size=4 base align=4
DERIVED_CLASS (0xb7d1bc80) 0 nearly-empty
vptr=((& DERIVED_CLASS::_ZTV13DERIVED_CLASS) + 8u)
BASE_CLASS (0xb7d1bcc0) 0 nearly-empty
primary-for DERIVED_CLASS (0xb7d1bc80)
The first thing we see is that the vtable (if it exists) always consists of two entries, by default. The first one is a NULL pointer and the second one is a pointer to the type-info of the class ( Maybe this is used for RTTI? ). Right, from then on, we have one pointer each for each virtual function in the class. The vptr for the base class is defined to be the value &(Base Class's virtual table) + 8. The 8 bytes skip the first two entries (on a 32-bit machine). Similarly, the vptr for the derived class is &(Derived Class's virtual table) + 8. Now, where is the vptr for each object stored? In the case of gcc, it is always the first word in the object's memory. Well, that's pretty much the vtable structure. So, calling a virtual function is now simply finding the vptr for the object ( in the first word ) & getting the address of the corresponding vtable. Index into the table using the appropriate index (calculated during compile-time), and you get the actual function to be called.

Let's move on to the GIMPLE output (unnecessary output skipped):


;; Function BASE_CLASS::BASE_CLASS() (_ZN10BASE_CLASSC2Ev)

BASE_CLASS::BASE_CLASS() (this)
{
int (*__vtbl_ptr_type) (void) * D.2250;

try
{
{
D.2250 = &_ZTV10BASE_CLASS + 8;
this->_vptr.BASE_CLASS = D.2250;
}
}
catch
{
<<>>
{
__cxa_call_unexpected (<<>>);
}
}
}

;; Function DERIVED_CLASS::DERIVED_CLASS() (_ZN13DERIVED_CLASSC1Ev)

DERIVED_CLASS::DERIVED_CLASS() (this)
{
struct BASE_CLASS * D.2259;
int (*__vtbl_ptr_type) (void) * D.2260;

try
{
{
D.2259 = &this->D.2202;
__base_ctor (D.2259);
D.2260 = &_ZTV13DERIVED_CLASS + 8;
this->D.2202._vptr.BASE_CLASS = D.2260;
}
}
catch
{
<<>>
{
__cxa_call_unexpected (<<>>);
}
}
}

;; Function int main() (main)

int main() ()
{
struct DERIVED_CLASS * D.2215;
void * D.2261;
int (*__vtbl_ptr_type) (void) * D.2262;
int (*__vtbl_ptr_type) (void) D.2263;
int D.2264;

{
{
struct DERIVED_CLASS * dobject;

D.2261 = operator new (4);
D.2215 = (struct DERIVED_CLASS *) D.2261;
try
{
__comp_ctor (D.2215);
}
catch
{
operator delete (D.2215);
}
dobject = D.2215;
D.2262 = dobject->D.2202._vptr.BASE_CLASS;
D.2263 = *D.2262;
OBJ_TYPE_REF(D.2263;dobject->0) (dobject);
....

We first see that the constructor for the base class and the derived class are implicitly called with the "this" pointer. This pointer points to the object in memory. Let's look at the base constructor. All we're doing here is getting the vtable for this class and making the vptr point to it. The vptr is depicted here as "this->_vptr.BASE_CLASS". Next comes the derived class's constructor. Since the derived class also has access to the base class's members/functions, it does contain a "pointer" to the base class within itself. In our case, this is the pointer &this->D.2202, which we pass on to the base' constructor. I haven't been able to figure out how the pointer is being obtained. Anyway, after the call to the base constructor, the vptr is now made to point correctly to the derived class's vtable as:
this->D.2202._vptr.BASE_CLASS = D.2260;
Remember, the base and derived classes both share the same vptr, hence it gets overwritten after the call to the base constructor has finished.
Now, let's look at how the virtual function is called from main() :
We first get the vptr of the object as :
vptr->D.2202._vptr.BASE_CLASS and then dereference it directly to get the function. Since the function is at the 0th index, we don't need any indexing here. We then call this deferenced function, which is pointing to the derived PRINT_FUNCTION and voila! There's your rabbit out of the hat!

On a more personal note, I just had an amazing last 3 weeks. Went to Goa (my second visit), the Jethro Tull concert, Bryan Adams concert, started on a couple of B&N free courses and still trying to keep my head above all this. It's now 3:35 AM and I've to leave for Mangalore in half an hour ( I've decided getting even a wink of sleep won't work for me now ). Maybe, I can nap along the way....