How are virtual functions and vtable implemented?

Question

We all know what virtual functions are in C++, but how are they implemented at a deep level?

Can the vtable be modified or even directly accessed at runtime?

Does the vtable exist for all classes, or only those that have at least one virtual function?

Do abstract classes simply have a NULL for the function pointer of at least one entry?

Does having a single virtual function slow down the whole class? Or only the call to the function that is virtual? And does the speed get affected if the virtual function is actually overwritten or not, or does this have no effect so long as it is virtual.

Solution 1

How are virtual functions implemented at a deep level?

From "Virtual Functions in C++":

Whenever a program has a virtual function declared, a v - table is constructed for the class. The v-table consists of addresses to the virtual functions for classes that contain one or more virtual functions. The object of the class containing the virtual function contains a virtual pointer that points to the base address of the virtual table in memory. Whenever there is a virtual function call, the v-table is used to resolve to the function address. An object of the class that contains one or more virtual functions contains a virtual pointer called the vptr at the very beginning of the object in the memory. Hence the size of the object in this case increases by the size of the pointer. This vptr contains the base address of the virtual table in memory. Note that virtual tables are class specific, i.e., there is only one virtual table for a class irrespective of the number of virtual functions it contains. This virtual table in turn contains the base addresses of one or more virtual functions of the class. At the time when a virtual function is called on an object, the vptr of that object provides the base address of the virtual table for that class in memory. This table is used to resolve the function call as it contains the addresses of all the virtual functions of that class. This is how dynamic binding is resolved during a virtual function call.

Can the vtable be modified or even directly accessed at runtime?

Universally, I believe the answer is "no". You could do some memory mangling to find the vtable but you still wouldn't know what the function signature looks like to call it. Anything that you would want to achieve with this ability (that the language supports) should be possible without access to the vtable directly or modifying it at runtime. Also note, the C++ language spec does not specify that vtables are required - however that is how most compilers implement virtual functions.

Does the vtable exist for all objects, or only those that have at least one virtual function?

I believe the answer here is "it depends on the implementation" since the spec doesn't require vtables in the first place. However, in practice, I believe all modern compilers only create a vtable if a class has at least 1 virtual function. There is a space overhead associated with the vtable and a time overhead associated with calling a virtual function vs a non-virtual function.

Do abstract classes simply have a NULL for the function pointer of at least one entry?

The answer is it is unspecified by the language spec so it depends on the implementation. Calling the pure virtual function results in undefined behavior if it is not defined (which it usually isn't) (ISO/IEC 14882:2003 10.4-2). In practice it does allocate a slot in the vtable for the function but does not assign an address to it. This leaves the vtable incomplete which requires the derived classes to implement the function and complete the vtable. Some implementations do simply place a NULL pointer in the vtable entry; other implementations place a pointer to a dummy method that does something similar to an assertion.

Note that an abstract class can define an implementation for a pure virtual function, but that function can only be called with a qualified-id syntax (ie., fully specifying the class in the method name, similar to calling a base class method from a derived class). This is done to provide an easy to use default implementation, while still requiring that a derived class provide an override.

Does having a single virtual function slow down the whole class or only the call to the function that is virtual?

This is getting to the edge of my knowledge, so someone please help me out here if I'm wrong!

I believe that only the functions that are virtual in the class experience the time performance hit related to calling a virtual function vs. a non-virtual function. The space overhead for the class is there either way. Note that if there is a vtable, there is only 1 per class, not one per object.

Does the speed get affected if the virtual function is actually overridden or not, or does this have no effect so long as it is virtual?

I don't believe the execution time of a virtual function that is overridden decreases compared to calling the base virtual function. However, there is an additional space overhead for the class associated with defining another vtable for the derived class vs the base class.

Additional Resources:

http://www.codersource.net/published/view/325/virtual_functions_in.aspx (via way back machine)
http://en.wikipedia.org/wiki/Virtual_table
http://www.codesourcery.com/public/cxx-abi/abi.html#vtable

Solution 2

• Can the vtable be modified or even directly accessed at runtime?

Not portably, but if you don't mind dirty tricks, sure!

WARNING: This technique is not recommended for use by children, adults under the age of 969, or small furry creatures from Alpha Centauri. Side effects may include demons which fly out of your nose, the abrupt appearence of Yog-Sothoth as a required approver on all subsequent code reviews, or the retroactive addition of IHuman::PlayPiano() to all existing instances]

In most compilers I've seen, the vtbl * is the first 4 bytes of the object, and the vtbl contents are simply an array of member pointers there (generally in the order they were declared, with the base class's first). There are of course other possible layouts, but that's what I've generally observed.

class A {
  public:
  virtual int f1() = 0;
};
class B : public A {
  public:
  virtual int f1() { return 1; }
  virtual int f2() { return 2; }
};
class C : public A {
  public:
  virtual int f1() { return -1; }
  virtual int f2() { return -2; }
};

A *x = new B;
A *y = new C;
A *z = new C;

Now to pull some shenanigans...

Changing class at runtime:

std::swap(*(void **)x, *(void **)y);
// Now x is a C, and y is a B! Hope they used the same layout of members!

Replacing a method for all instances (monkeypatching a class)

This one's a little trickier, since the vtbl itself is probably in read-only memory.

int f3(A*) { return 0; }

mprotect(*(void **)x,8,PROT_READ|PROT_WRITE|PROT_EXEC);
// Or VirtualProtect on win32; this part's very OS-specific
(*(int (***)(A *)x)[0] = f3;
// Now C::f1() returns 0 (remember we made x into a C above)
// so x->f1() and z->f1() both return 0

The latter is rather likely to make virus-checkers and the link wake up and take notice, due to the mprotect manipulations. In a process using the NX bit it may well fail.

Solution 3

Does having a single virtual function slow down the whole class?

Or only the call to the function that is virtual? And does the speed get affected if the virtual function is actually overwritten or not, or does this have no effect so long as it is virtual.

Having virtual functions slows down the whole class insofar as one more item of data has to be initialized, copied, … when dealing with an object of such a class. For a class with half a dozen members or so, the difference should be neglible. For a class which just contains a single char member, or no members at all, the difference might be notable.

Apart from that, it is important to note that not every call to a virtual function is a virtual function call. If you have an object of a known type, the compiler can emit code for a normal function invocation, and can even inline said function if it feels like it. It's only when you do polymorphic calls, via a pointer or reference which might point at an object of the base class or at an object of some derived class, that you need the vtable indirection and pay for it in terms of performance.

struct Foo { virtual ~Foo(); virtual int a() { return 1; } };
struct Bar: public Foo { int a() { return 2; } };
void f(Foo& arg) {
  Foo x; x.a(); // non-virtual: always calls Foo::a()
  Bar y; y.a(); // non-virtual: always calls Bar::a()
  arg.a();      // virtual: must dispatch via vtable
  Foo z = arg;  // copy constructor Foo::Foo(const Foo&) will convert to Foo
  z.a();        // non-virtual Foo::a, since z is a Foo, even if arg was not
}

The steps the hardware has to take are essentially the same, no matter whether the function is overwritten or not. The address of the vtable is read from the object, the function pointer retrieved from the appropriate slot, and the function called by pointer. In terms of actual performance, branch predictions might have some impact. So for example, if most of your objects refer to the same implementation of a given virtual function, then there is some chance that the branch predictor will correctly predict which function to call even before the pointer has been retrieved. But it doesn't matter which function is the common one: it could be most objects delegating to the non-overwritten base case, or most objects belonging to the same subclass and therefore delegating to the same overwritten case.

how are they implemented at a deep level?

I like the idea of jheriko to demonstrate this using a mock implementation. But I'd use C to implement something akin to the code above, so that the low level is more easily seen.

parent class Foo

typedef struct Foo_t Foo;   // forward declaration
struct slotsFoo {           // list all virtual functions of Foo
  const void *parentVtable; // (single) inheritance
  void (*destructor)(Foo*); // virtual destructor Foo::~Foo
  int (*a)(Foo*);           // virtual function Foo::a
};
struct Foo_t {                      // class Foo
  const struct slotsFoo* vtable;    // each instance points to vtable
};
void destructFoo(Foo* self) { }     // Foo::~Foo
int aFoo(Foo* self) { return 1; }   // Foo::a()
const struct slotsFoo vtableFoo = { // only one constant table
  0,                                // no parent class
  destructFoo,
  aFoo
};
void constructFoo(Foo* self) {      // Foo::Foo()
  self->vtable = &vtableFoo;        // object points to class vtable
}
void copyConstructFoo(Foo* self,
                      Foo* other) { // Foo::Foo(const Foo&)
  self->vtable = &vtableFoo;        // don't copy from other!
}

derived class Bar

typedef struct Bar_t {              // class Bar
  Foo base;                         // inherit all members of Foo
} Bar;
void destructBar(Bar* self) { }     // Bar::~Bar
int aBar(Bar* self) { return 2; }   // Bar::a()
const struct slotsFoo vtableBar = { // one more constant table
  &vtableFoo,                       // can dynamic_cast to Foo
  (void(*)(Foo*)) destructBar,      // must cast type to avoid errors
  (int(*)(Foo*)) aBar
};
void constructBar(Bar* self) {      // Bar::Bar()
  self->base.vtable = &vtableBar;   // point to Bar vtable
}

function f performing virtual function call

void f(Foo* arg) {                  // same functionality as above
  Foo x; constructFoo(&x); aFoo(&x);
  Bar y; constructBar(&y); aBar(&y);
  arg->vtable->a(arg);              // virtual function call
  Foo z; copyConstructFoo(&z, arg);
  aFoo(&z);
  destructFoo(&z);
  destructBar(&y);
  destructFoo(&x);
}

So you can see, a vtable is just a static block in memory, mostly containing function pointers. Every object of a polymorphic class will point to the vtable corresponding to its dynamic type. This also makes the connection between RTTI and virtual functions clearer: you can check what type a class is simply by looking at what vtable it points at. The above is simplified in many ways, like e.g. multiple inheritance, but the general concept is sound.

If arg is of type Foo* and you take arg->vtable, but is actually an object of type Bar, then you still get the correct address of the vtable. That's because the vtable is always the first element at the address of the object, no matter whether it's called vtable or base.vtable in a correctly-typed expression.

Solution 4

Here is a runnable manual implementation of virtual table in modern C++. It has well-defined semantics, no hacks and no void*.

Note: .* and ->* are different operators than * and ->. Member function pointers work differently.

#include <iostream>
#include <vector>
#include <memory>

struct vtable; // forward declare, we need just name

class animal
{
public:
    const std::string& get_name() const { return name; }

    // these will be abstract
    bool has_tail() const;
    bool has_wings() const;
    void sound() const;

protected: // we do not want animals to be created directly
    animal(const vtable* vtable_ptr, std::string name)
    : vtable_ptr(vtable_ptr), name(std::move(name)) { }

private:
    friend vtable; // just in case for non-public methods

    const vtable* const vtable_ptr;
    std::string name;
};

class cat : public animal
{
public:
    cat(std::string name);

    // functions to bind dynamically
    bool has_tail() const { return true; }
    bool has_wings() const { return false; }
    void sound() const
    {
        std::cout << get_name() << " does meow\n"; 
    }
};

class dog : public animal
{
public:
    dog(std::string name);

    // functions to bind dynamically
    bool has_tail() const { return true; }
    bool has_wings() const { return false; }
    void sound() const
    {
        std::cout << get_name() << " does whoof\n"; 
    }
};

class parrot : public animal
{
public:
    parrot(std::string name);

    // functions to bind dynamically
    bool has_tail() const { return false; }
    bool has_wings() const { return true; }
    void sound() const
    {
        std::cout << get_name() << " does crrra\n"; 
    }
};

// now the magic - pointers to member functions!
struct vtable
{
    bool (animal::* const has_tail)() const;
    bool (animal::* const has_wings)() const;
    void (animal::* const sound)() const;

    // constructor
    vtable (
        bool (animal::* const has_tail)() const,
        bool (animal::* const has_wings)() const,
        void (animal::* const sound)() const
    ) : has_tail(has_tail), has_wings(has_wings), sound(sound) { }
};

// global vtable objects
const vtable vtable_cat(
    static_cast<bool (animal::*)() const>(&cat::has_tail),
    static_cast<bool (animal::*)() const>(&cat::has_wings),
    static_cast<void (animal::*)() const>(&cat::sound));
const vtable vtable_dog(
    static_cast<bool (animal::*)() const>(&dog::has_tail),
    static_cast<bool (animal::*)() const>(&dog::has_wings),
    static_cast<void (animal::*)() const>(&dog::sound));
const vtable vtable_parrot(
    static_cast<bool (animal::*)() const>(&parrot::has_tail),
    static_cast<bool (animal::*)() const>(&parrot::has_wings),
    static_cast<void (animal::*)() const>(&parrot::sound));

// set vtable pointers in constructors
cat::cat(std::string name) : animal(&vtable_cat, std::move(name)) { }
dog::dog(std::string name) : animal(&vtable_dog, std::move(name)) { }
parrot::parrot(std::string name) : animal(&vtable_parrot, std::move(name)) { }

// implement dynamic dispatch
bool animal::has_tail() const
{
    return (this->*(vtable_ptr->has_tail))();
}

bool animal::has_wings() const
{
    return (this->*(vtable_ptr->has_wings))();
}

void animal::sound() const
{
    (this->*(vtable_ptr->sound))();
}

int main()
{
    std::vector<std::unique_ptr<animal>> animals;
    animals.push_back(std::make_unique<cat>("grumpy"));
    animals.push_back(std::make_unique<cat>("nyan"));
    animals.push_back(std::make_unique<dog>("doge"));
    animals.push_back(std::make_unique<parrot>("party"));

    for (const auto& a : animals)
        a->sound();

    // note: destructors are not dispatched virtually
}

Solution 5

Usually with a VTable, an array of pointers to functions.

View more solutions

Comments

[Steve Jessop]

It would not be in line with Stroustrup's philosophy of C++ for a compiler to put an unnecessary vtable pointer in an object which doesn't need it. The rule is that you don't get overhead that isn't in C unless you ask for it, and it's rude for compilers to break that.

[Asim Ihsan]

Also, I don't think that an abstract class can define an implementation for a pure virtual function. By defintion, a pure virtual function has no body (e.g. bool my_func() = 0;). You can however, provide implementations for regular virtual functions.

[Michael Burr]

A pure virtual function can have a definition. See Scott Meyers' "Effective C++, 3rd Ed" Item #34, ISO 14882-2003 10.4-2, or bytes.com/forum/thread572745.html

[Andrew Stein]

I have added my comment to the answer to the second question as a separate answer.

[Michael Burr]

This is not correct for 2 reasons: 1) an abstract class may have regular virtual methods in addition to pure virtual methods, and 2) pure virtual methods may optionally have a definition that can be called with a fully qualified name.

[Michael Burr]

Right - on second thought I imagine that if all virtual methods were pure virtual the compiler might optimize the vtable away (it would need help form the linker to ensure there were no definitions as well).

[MSalters]

Even virtual functions can be called non-virtually. This is in fact quite common: if the object is on the stack, within scope the compiler will know the exact type and optimizes out the vtable lookup. This is especially true for the dtor, which must be called in the same stack scope.

[Asim Ihsan]

There are a number of tricks and gotchas that the compiler can use/introduce, depending on its implementation. I tried to stay away implementation specific answers as much as I could, but that was impossible since his questions are not answered by the language spec. I had to draw the line somewhere.

[Asaf R]

I believe when a class that has at least one virtual function, every object has a vtable, and not one for the entire class.

[Asim Ihsan]

Asaf R - I don't believe this is correct. You define functions on a per class basis, not on a per instance basis. Therefore there is no need for vtables on a per object basis. However, there is some special "magic" during object construction/destruction since the object is not fully formed yet.

[MSalters]

Common implementation: Each object has a pointer to a vtable; the class owns the table. The construction magic simply consists of updating the vtable pointer in the derived ctor, after the base ctor has finished.

[curiousguy]

"The answer is that no virtual table is created at all for abstract classes." Wrong. "There is no need since no objects of these classes can be created!" Wrong.

[curiousguy]

"This leaves the vtable incomplete which requires the derived classes to implement the function and complete the vtable." No, a derived class does not "complete" the base class vtable: a derived class has its own vtable. There is no such thing as an "incomplete" vtable.

[Asim Ihsan]

There are no incomplete vtables that are instantiated, but from the compiler's view, the derived class has an empty slot in the vtable for a function that the derived class must fulfill.

[MvG]

I can follow your rationale that no vtable for B should be needed. Just because some of its methods have (default) implementations doesn't mean they have to be stored in a vtable. But I just ran your code (modulo some fixes to make it compile) through gcc -S followed by c++filt and there clearly is a vtable for B included in there. I guess that might be because the vtable also stores RTTI data like class names and inheritance. It might be required for a dynamic_cast<B*>. Even -fno-rtti doesn't make the vtable go away. With clang -O3 instead of gcc it's suddenly gone.

[LThode]

@ZachBurlingame -- I'm pretty sure that you are correct in that the virtual dispatch mechanism is only used for functions explicitly marked virtual...

[puetzk]

Hmm. It feels ominous that this received a bounty. I hope that doesn't mean @Mobilewits thinks such shenanigans are actually a good idea...

[curiousguy]

void(*)(Foo*) MyFunc; is this some Java syntax?

[curiousguy]

@MvG "Just because some of its methods have (default) implementations doesn't mean they have to be stored in a vtable" Yes, it means just that.

[jheriko]

no, its C/C++ syntax for function pointers. To quote myself "You can recreate the functionality of virtual functions in C++ using function pointers". its a nasty bit of syntax, but something to be familiar with if you consider yourself a C programmer.

[Menace]

a c function pointer would look more like: int (PROC)(); and a pointer to a class member function would look like: int (ClassName:: MPROC)();

[jheriko]

@menace, you forgot some syntax there... you are thinking of the typedef maybe? typedef int(*PROC)(); so you can just do PROC foo later instead of int(*foo)() ?

[SMUsamaShah]

"Can the vtable be modified or even directly accessed at runtime? No" What about hooking using vtable like this code?

[Bhuwan]

"Every object of a polymorphic class will point to its own vtable." Are you saying every object has its own vtable ? AFAIK vtable is shared between all objects of the same class. Let me know if I'm wrong.

[MvG]

@Bhuwan: No, you are right: there is just one vtable per type (which might be per template instantiation in case of templates). I meant to say that each object of a polymorphic class with point to the vtable that applies to it, so each object has such a pointer, but for objects of the same type it will point to the same table. Probably I should reword this.

[curiousguy]

@MvG "objects of the same type it will point to the same table" not during construction of base classes with virtual base classes! (a very special case)

[MvG]

@curiousguy: I'd file that under “the above is simplified in many ways”, particularly since the main application of virtual bases is multiple inheritance, which I didn't model either. But thanks for the comment, it's useful to have this here for people who might need more depth.

[einpoklum]

Please consider discouraging the use of this technique, clearly and strongly, rather than "winking".

[curiousguy]

@ZachBurlingame "the derived class has an empty slot in the vtable for a function that the derived class must fulfill" What "empty slot"?

[curiousguy]

"vtbl contents are simply an array of member pointers" actually it's a record (a struct) with different entries, that happen to be evenly spaced

[puetzk]

You can look at it either way; the function pointers have different signatures, and thus different pointer types; in that sense, it's indeed structure-like. But in other contexts, but the idea of vtbl index is useful (e.g. ActiveX uses it in the way it describes dual interfaces in typelibs), which is a more array-like view.

[David R Tribble]

@ZachBurlingame - the derived class has an empty slot in the vtable for a function that the derived class must fulfill. No, the derived class has its own vtable with slots for its own member functions, included those that override the base class's functions. The base class vtable simply has undefined or NULL function pointers in the slots for its pure abstract member functions, which should not be directly callable through concrete (derived) objects. The derived class vtable has actual pointers to its own overriding implementations of those abstract functions.

[Sebastian Redl]

"However, in practice, I believe all modern compilers only create a vtable if a class has at least 1 virtual function." - The layout requirements for POD (standard layout) objects pretty much require that there isn't a vptr.

[Energy]

I am new to c++, can someone explain what this expression (*(int (***)(A *)x)[0] means? Is it casting x to a function pointer? But what does (***) means then?

[puetzk]

First, please understand that this whole aswer is kind of tongue-in-cheek. If you're new to C++, or even very experienced in reasonable use of C++, you are not expected (or even allowed) to assume anything about this level of "how stuff really works". The only people who have a real reason to think about his level are those implementing a compiler and choosing how it will realize the C++ abstraction of "virtual functions" on a specific set of hardware.

[puetzk]

But that disclaimer given - the *** represents a pointer to a pointer to a function pointer. We're taking the object's data, reinterpreting it as pointer to its vtbl (i.e. assuming the compiler has chosen to place that first) and dereferencing it and assuming that vtbl consists of an array of function pointers, indexing element [0], then replacing it with a pointer to f3. None of this is guaranteed by C++, but most of it is (at least usually) how most compilers implement it. Study this to satisfy your curiosity of how things "really work" deep down. Do not actually use the technique!