Rambly Musings of a Reverse Engineer #0: How the Tables Have Turned!

Greetings, one and all!
Welcome to my first ever series on my website!

Here, I plan to delve into the many things I learn while reverse-engineering that I find worth sharing.

For context, this was a topic I explored while reverse-engineering Net High—a visual novel for the PlayStation Vita from 2015—for a project (more details to come soon).

Disclaimer: Given the topic at hand, a familiarity with Object-Oriented Programming—and therefore inheritance and polymorphism (ideally in C++)—is recommended. There is only so much I can explain at one time without it going in one ear and out the other.

If you’ve done a somewhat decent amount of OOP in C++ (or similar languages), you’ve most likely heard of the term Virtual Table, or vtable, for short.

I know I have, and given that I was left reverse-engineering a C++ binary, sooner or later I was forced to roll up my sleeves and learn exactly how they work.

And so, after a couple days of reading up on them and double-checking with compiler outputs (God bless godbolt.org (pun not intended)), I managed to learn how they’re implemented, how they work, and how they’re used.

With that said, given my incorrigible penchant for yapping, I have brought you what I’ve learned in a digestible format for your reading pleasure! Or at least, that’s what I hope.

What Are They? And… Can I Eat Them?#

No, you cannot, in fact.

You can do so much more than that!

All jokes aside, vtables—when chosen as an implementation—are the cornerstone of dynamic dispatch, the process that takes place during runtime in which an implementation of a polymorphic method is chosen based on the class hierarchy for the given object type. They’re data structures that hold the type information for a given class, offsets (more on that later), and function pointers to the methods defined for that class. Each class has its own vtable, and every instance of that class will have a pointer into it at the beginning of its memory layout.

How Do They Work?#

Now, if that was a lot, fret not. heh

We’ll start with a simple example and go from there.

class A {
  protected:
    virtual void foo() {}
};

class B {
  protected:
    virtual void bar() {}
};

class C : public A, public B {
};

As we can see, class A and B both define two distinct virtual methods, which class C inherits from them.

In terms of class hierarchy, we have the following:

Whenever a class declares/defines a virtual method, it and any of its subclasses will have a vtable generated for them. In this scenario, there are three vtables in total, one for each of the defined classes.

Let’s take a look at what the vtable for class A would look like:

But don’t take my word for it, check it out for yourself!

Note: While I could delve into the specifics of the typeinfo structure, that’s outside the scope of this post.

Naturally, given their similar layouts, the vtable for class B looks near identical to that of class A.

We now turn our attention to class C. Being the subclass of two polymorphic classes, its vtable layout will be a tad bit more complicated.

Before that, however, let’s first quickly go over regular inheritance with the following example:

class X {
  protected:
    int x;
};

class Y {
  protected:
    const char *y;
};

class Z: public X, public Y {
  protected:
    float z;
};

The way inheritance works in practice is that subclasses will contain instances of their superclasses within them, like so:

As seen above, the memory layout for subclasses is decided by the order the superclasses are listed in the base clause¹. The exception to this is when there’s a mix of polymorphic and regular superclasses, in which case the first polymorphic superclass in the list is moved to the front so that both the subclass and superclass vtable pointers can line up at offset +0.

With that out of the way, we can now finally direct our attention back to class C.

Just like regular inheritance, the instance of class C does contain an instance of both class A and class B within it in the order they’re listed in the base clause. Likewise, as we can see, the vtable for the subclass contains a section for each of its superclasses.

We can also now talk about the role of offsetToTop: given an instance of a superclass inside one of its subclass instances, offsetToTop is an offset that, when added to the offset at which the superclass instance lives, will resolve to the base address of the respective subclass instance.

A More Cowmplicated Example#

In order to make clear the key takeaways, we’ll need a more, let’s say, thorough example, taking into account both the inheritance and vtable example classes.

#include <iostream>

class Animal {
  private:
    unsigned int weight;
  public:
    Animal(unsigned int weight) : weight(weight) {}
    unsigned int getWeight() { return weight; }
    
    virtual void speak() = 0;
};

class Movable {
  protected:
    int x, y;

    Movable(int x, int y) : x(x), y(y) {}
    
    virtual void move(int xTo, int yTo) = 0;
};


class Cow : public Animal, public Movable {
  private:
    bool asleep;
    float milk;
  public:
    Cow(unsigned int weight, int x, int y, bool asleep) : Animal(weight), Movable(x, y), asleep(asleep) {}
    void sleepOrWake() { asleep ^= true; }
    
    void speak() override {
        std::cout << "Moo!" << std::endl;
    }

    void move(int xTo, int yTo) override {
        if (asleep) { std::cout << "Zzzzz..." << std::endl; return; }
        x = xTo; y = yTo;
    }

    virtual void produceMilk() { milk += 5.0f; }
};

Note: Technically, both Animal and Movable are abstract base classes, and cannot have any standalone instances. However, this isn’t always true in real-word scenarios. As such, we’ll go over everything from a general point of view to cover our bases.

Now, as, erm, contrived as as example it may seem, let’s take it step by step:

Grass Hierarchy#

Quite similar to our previous examples, but, as always, the devil is in the details. What’s important to cement, however, is that—just like before—the vtable will have two separate sections—one for each superclass—just like how the subclass instance will have two superclass instances: one for Animal and one for Movable.

Memoooooory Layout#

As denoted before, the order of the superclass instances follows the order set in the base clause, after which we have the subclass member variables.

The core idea behind this way of laying out memory is that the subclasses can be cast to one of their superclasses, which is simply a matter of offsetting the subclass instance pointer to the relevant superclass instance—this is called upcasting (as you likely already know), as in, casting up the class hierarchy. Any method or function taking in one of the superclasses will therefore, by design, be unable to distinguish between a standalone superclass instance and a superclass instance within a subclass, as, naturally, accessing any data outside of the known size of a structure is undefined behavior.

A Beefed-Up Vtable#

More on what a thunk is later.

You may have noticed earlier that the diagram for the class layout grouped the function table for Animal and Cow together. Indeed, while the subclass member variables are placed at the end of its memory layout, when it comes its polymorphic methods, it’s not so simple. Keeping in mind that the first section of the vtable corresponds to the first class in its base clause—Animal, in this case—any of the subclass’s own virtual methods, or polymorphic methods it implements from any of its other superclasses—namely, Movable—always lay at the bottom of that section, after the function pointers to the first superclass—i.e. Animal—’s methods implemented in the subclass.

The reason for this is that both the instance of the first superclass in the base clause—in this case, Animal— and the subclass instance will occupy the same memory address. Furthermore, as mentioned previously, with one vtable section for each superclass, and one function table pointer at the base of each polymorphic superclass instance within the subclass instance—both, in our case—that will leave us with two vtable sections, two function table pointers into said vtable, but three separate sets of methods: Animal’s, Movable’s, and, of course, Cow’s. Then, following the same logic that enables upcasting, Cow’s vtable will be structured in such a way that the function table in the first section will both function as Animal’s and Cow’s vtable: since the former’s polymorphic methods are a subset of the latter’s, it is simply a matter of laying them out as such.

Cownfirming Our Findungs#

I really ought to stop with the puns.

Putting it all together:

You’re welcome to accompany along on godbolt yourself if you’d like.
Or if you don’t trust me…

Let’s get the low-hanging fruit out of the way. The following

std::cout << "Cow: " << sizeof(Cow) << std::endl;

outputs:

Just as expected! Now, for the vtable layout:

Another win for us!

Now, to address the elephant (cow?) in the room. From Wikipedia:

“In computer programming, a thunk is a subroutine used to inject a calculation into another subroutine.”

Now, what manner of calculation would be necessary in this case?
That’s right! Offsetting pointers!

Given that for the Cow class, the relevant move implementation is its own, and not one of its superclasses’ (in this case there’s none), the method will in fact take a Cow object for its this argument. However, when the method is called through the Movable superclass instance, the “active” instance won’t be of the right type, which then requires a calculation: adding offsetToTop from its respective vtable section to the address of the superclass instance, which will result in the address of the subclass instance—exactly what we need to call the function.

And that is, in fact, what we see:

The funny thing is, we have just gone over dynamic dispatching without realizing it! We have taken a polymorphic method, and called it with the expected type by offsetting the pointer of an object. It doesn’t get any simpler than that.

Vtables in Action#

Given all that we’ve gone over, we can now understand what is really going on for code like the following:

Movable *m = new Cow(700, 0, 0, true);
m->move(10, 10);

1. For the assignment, the pointer returned by new is offset by +16, such that it points to the Movable instance within the returned Cow object.
2. For the function call, the relevant vtable section is looked up, and the move thunk is called, which then removes the offset from the previous step so that the move method implemented for Cow can be called with the right type.

In other words, the code above can be rewritten like this:

Movable *m = reinterpret_cast<Movable *>(reinterpret_cast<char *>(new Cow(700, 0, 0, true)) + 16);

// Not actually valid C++, as the `this` argument can't be passed in manually, but it is effectively what's happening
Cow::move(reinterpret_cast<Cow*>(reinterpret_cast<char *>(m) - 16), 10, 10);

Feel free to try it for yourself!

Final Thoughts#

Whew, what a ride. And what a way to kick off my first blog post!
I can only hope it’s been informative.

This will likely suffer a few edits as I inevitably become aware of any mistakes I made or things I forgot to mention, but hopefully their frequency should diminish as time goes on and I get used to this. And while hopefully not an exercise in futility, regardless of how many (or how few, in all likelihood) people stumble across this place, writing these is a great way to review these topics and further cement my understanding of them. It is in fact part of the reason why imparting things I learn unto others feels so rewarding to me.

I’m still not sure as to how frequently these blog posts will be, but I’ll do my best to not let this place be left to rot (famous last words).

As always, stay sharp and take care!

For any questions, thoughts or any further inquiries, feel free to email me at contact@itsleah.dev.
Alternatively, you can find me on Discord by the username @solanni.