What is happening under the hood of virtual inheritance?

Question

Recently I have been trying to make a plugin for an old game, and running into a problem similar to Diamond Inheritance.

I have a very reduced example, write as follows:

#include <iostream>
#include <stdint.h>
#include <stddef.h>

using namespace std;

struct CBaseEntity
{
    virtual void Spawn() = 0;
    virtual void Think() = 0;

    int64_t m_ivar{};
};

struct CBaseWeapon : virtual public CBaseEntity
{
    virtual void ItemPostFrame() = 0;

    double m_flvar{};
};

struct Prefab : virtual public CBaseEntity
{
    void Spawn() override { cout << "Prefab::Spawn\n"; }
    void Think() override { cout << "Prefab::Think\n"; }
};

struct WeaponPrefab : virtual public CBaseWeapon, virtual public Prefab
{
    void Spawn() override { cout << boolalpha << m_ivar << '\n'; }
    void ItemPostFrame() override { m_flvar += 1; cout << m_flvar << '\n'; }

    char words[8];
};

int main() noexcept
{
    cout << sizeof(CBaseEntity) << '\n';
    cout << sizeof(CBaseWeapon) << '\n';
    cout << sizeof(Prefab) << '\n';
    cout << sizeof(WeaponPrefab) << '\n';

    cout << offsetof(WeaponPrefab, words) << '\n';
}

The first two are extracted from the game's source code and I made them pure virtual classes since I have no need to instantiate them. The third class (Prefab) is the one I extend all my classes in my mod from.

The problem is: I just noticed that the class size changed, which could potentially indicate an ABI-breaking thingy waiting for me. When I removed all virtual keywords from inheritances, the class size is quite small, and the memory layout make sense to me. But whenever I put virtual inheritance on, the size suddenly blows up, and the layout seems like a mystery.

Like I printed out the offsetof a variable in my WeaponPrefab class, it shows 8, but the total size is 48, which doesn't make any sense - where are the m_ivar and m_flvar?

(I am not trying to provoke people with undefined behavior, but just trying to cope with the existing ABI in the original game.)

Link to Compiler Explorer: https://godbolt.org/z/YvWTbf8j8

Ochre

You have to read some about Vptr and Vtable in C++. When you have virtual methods, the size of the class will be greater by size of the Vptr, which will be 4 bytes on x86 machine and 8 bytes on x64. offsetof(WeaponPrefab, words) returns 8, because the first 8 bytes are occupied by Vptr. – Torrietorrin

What happens under the hood is not so important. The C++ standard only describes the observable behavior. In most implementations/cases an extra table with function pointers is added to the class (in derived classes those function pointers may point to overriden functions). And instead of making a direct call to a member function, a call is made using an entry from the function pointer table. (thus selecting the correct function based on the class type). Look up information about vtables if you want to know more – Kulturkampf

WeaponPrefab : virtual public CBaseWeapon, virtual public Prefab You don't need virtual here (unless you plan to extend your inheritance lattice hierarchy further—not recommended). – Lymphocyte

Did you get offsetof m_flvar and m_ilvar? Trying that one might give you some clues. – Bradstreet

"I just noticed that [X], which could potentially indicate an ABI-breaking thingy waiting for me" -- This seems backwards to me. You made changes, then looked for an indication that ABI broke. I would start with the assumption that any change breaks ABI, then for each proposed change look for an assurance that it will not. – Girder

The implementation of virtual bases is one of the most complex part of a C++ ABI and it's a part that varies a lot: most of C++ ABI layout tend to pretty close from one compiler to the next, but how virtual inheritance is done can be 100% different, because there isn't a "_one and only efficient way that's also trivial to implement", as for simple virtual functions for SI (vptr and vtable for virtual function in single inheritance is really easy to implement, easy to explain, nothing is "tricky"). Non virtual MI is slightly harder but not too tricky. Virtual inheritance is tricky. – Fayefayette

Answer 1

Warning: this is all implementation-detail. Different compilers may implement the specifics differently, or may use different mechanisms all together. This is just how GCC does it in this specific situation.

Note that I'm ignoring the vtable pointers used to implement virtual method dispatch throughout this answer to focus on how virtual inheritance is implemented.

Using normal, non-virtual inheritance, a WeaponPrefab would include two CBaseEntity sub-objects: one that it inherits via CBaseWeapon and one that it inherits via Prefab. It would look something like this:

 WeaponPrefab
 ┌─────────────────────┐
 │ CBaseWeapon         │
 │ ┌─────────────────┐ │
 │ │ CBaseEntity     │ │
 │ │ ┌─────────────┐ │ │
 │ │ │ int64_t     │ │ │
 │ │ │ ┌─────────┐ │ │ │
 │ │ │ │ m_ivar  │ │ │ │
 │ │ │ └─────────┘ │ │ │
 │ │ └─────────────┘ │ │
 │ │  double         │ │
 │ │  ┌─────────┐    │ │
 │ │  │ m_flvar │    │ │
 │ │  └─────────┘    │ │
 │ └─────────────────┘ │
 │ Prefab              │
 │ ┌─────────────────┐ │
 │ │ CBaseEntity     │ │
 │ │ ┌─────────────┐ │ │
 │ │ │ int64_t     │ │ │
 │ │ │ ┌─────────┐ │ │ │
 │ │ │ │ m_ivar  │ │ │ │
 │ │ │ └─────────┘ │ │ │
 │ │ └─────────────┘ │ │
 │ └─────────────────┘ │
 │  char[8]            │
 │  ┌─────────┐        │
 │  │ words   │        │
 │  └─────────┘        │
 └─────────────────────┘

virtual inheritance allows you to avoid this. Each object will have only one sub-object of each type that it inherits from virtually. In this case, the two CBaseObjects are combined into one:

WeaponPrefab
┌───────────────────┐
│   char[8]         │
│   ┌─────────┐     │
│   │ words   │     │
│   └─────────┘     │
│ Prefab            │
│ ┌───────────────┐ │
│ └───────────────┘ │
│ CBaseWeapon       │
│ ┌───────────────┐ │
│ │  double       │ │
│ │  ┌─────────┐  │ │
│ │  │ m_flvar │  │ │
│ │  └─────────┘  │ │
│ └───────────────┘ │
│ CBaseEntity       │
│ ┌───────────────┐ │
│ │  int64_t      │ │
│ │  ┌─────────┐  │ │
│ │  │ m_ivar  │  │ │
│ │  └─────────┘  │ │
│ └───────────────┘ │
└───────────────────┘

This presents a problem though. Notice that in the non-virtual example CBaseEntity::m_ivar is always 0-bytes into a Prefab object, whether it's standalone or a sub-object of a WeaponPrefab. But in the virtual example the offset is different. For a standalone Prefab object CBaseEntity::m_ivar would be offset 0-bytes from the start of the object, but for a Prefab that's a sub-object of a WeaponPrefab it would be offset 8-bytes from the start of the Prefab object.

To get around this problem, objects generally carry an extra pointer to a static table generated by the compiler that contains offsets to each of their virtual base classes:

                              Offset Table for
WeaponPrefab                  standalone WeaponPrefab
┌────────────────────┐        ┌──────────────────────┐
│   Offset Table Ptr │        │Prefab offset:      16│
│   ┌─────────┐      │        │CBaseWeapon offset: 24│
│   │         ├──────┼───────►│CBaseEntity offset: 40│
│   └─────────┘      │        └──────────────────────┘
│   char[8]          │
│   ┌─────────┐      │
│   │ words   │      │
│   └─────────┘      │
│ Prefab             │        Offset Table for
│ ┌────────────────┐ │        Prefab in WeaponPrefab
│ │Offset Table Ptr│ │        ┌──────────────────────┐
│ │  ┌─────────┐   │ │        │CBaseEntity offset: 24│
│ │  │         ├───┼─┼───────►│                      │
│ │  └─────────┘   │ │        └──────────────────────┘
│ └────────────────┘ │
│ CBaseWeapon        │        Offset Table for
│ ┌────────────────┐ │        CBaseWeapon in WeaponPrefab
│ │Offset Table Ptr│ │        ┌──────────────────────┐
│ │  ┌─────────┐   │ │        │CBaseEntity offset: 16│
│ │  │         ├───┼─┼───────►│                      │
│ │  └─────────┘   │ │        └──────────────────────┘
│ │  double        │ │
│ │  ┌─────────┐   │ │
│ │  │ m_flvar │   │ │
│ │  └─────────┘   │ │
│ └────────────────┘ │
│ CBaseEntity        │
│ ┌────────────────┐ │
│ │  int64_t       │ │
│ │  ┌─────────┐   │ │
│ │  │ m_ivar  │   │ │
│ │  └─────────┘   │ │
│ └────────────────┘ │
└────────────────────┘

Note that this isn't precisely accurate. Since Prefab has no data members, GCC actually avoids giving it its own offset table and instead has it share WeaponPrefab's table and pointer. This diagram is how GCC would lay the object out if Prefab did have at least one data member.

Dicker

How does WeaponPrefab determines locations of Prefab and CBaseWeapon? It also inherits them virtually. Do you mean it stores pointers to them as well? But then the results he gets for object sizes is too small. – Cupidity

@Cupidity You're right, that first pointer in WeaponPrefab should have been a CBaseWeapon* rather than a CBaseEntity*; fixed. WeaponPrefab can always chase the pointers through CBaseWeapon or Prefab if it needs to find its CBaseEntity sub-object. – Dicker

Thank you so much for the time you spend editing these 'image'! I would need some time to understand this. Correct me if I were wrong - a lot of spaces are used for padding and actually don't serve any real use? – Ochre

@Ochre No. Generally, when people talk about padding they're referring to unused space that's just there to maintain the alignment of data members. There is no padding in this example. All of the storage is being used (much of it for extra pointers used to implement virtual inheritance and virtual method dispatch). – Dicker

The 'boxes and lines' are really cool, do you have some tool to help creating them? – Hygienic

@Hygienic asciiflow.com – Dicker

Ahhhh, thank you I think I just understand why am I getting a different address if I do a dynamic_cast at runtime... Casting from WeaponPrefab to CBaseEntity actually queries something inside of the memory region... – Ochre

@MilesBudnek you sure it stores vptr as a raw pointer? This makes the class not-relocatable and not-trivially copyable. If it stores difference in location, then one can use like 1 or 2 bytes instead of 8 for the pointer. That's being said, in typical situations, 1-2 end up being 8 due to padding. – Cupidity

@Cupidity You are, once again, correct. It actually stores a pointer to a static offset table instead of directly to the parent class. I was basing that assumption on what I thought was a 16-byte offset from the start of the object to the first member, but it turns out I was reading the output wrong. I should have just looked at the assembly from the beginning. – Dicker

@MilesBudnek oh, excellent. I was wondering how it was implemented, that it stores pointer to an offset-table makes a lot of sense. I've heard some complains that virtual classes cause substantial increase in size of executables, which is very relevant to embedded. – Cupidity

@Cupidity The part that's easy to overlook is that virtual methods are often implemented as function-pointers. And it then becomes difficult for the optimizer to prove the runtime value of these function-pointers at the call site. And if the optimizer can't prove the runtime value, then it cannot inline methods, and has to push/pop data between registers and the stack for each method call. So not only are the objects in memory larger, but the code is as well. – Dichromaticism

It might be worth noting in the answer that the Offset tables also have pointers to Spawn, Think and/or ItemPostFrame as well. It's not needed to answer this specific question, but they are there. Also that classes with virtual methods should definitely have virtual destructors. – Dichromaticism

@MooingDuck actually, inlining frequently results in larger code... so not sure about virtualizing increasing code size, except when the virtual function is rather trvial or would be optimized very well. – Cupidity

@ALX23z: You're right that it depends on if the method body is bigger or smaller than the code to push/pop between the stack and registers. If the methods are small, then it makes the code larger. Even for larger methods, if it knows the impl, it can skip some of the push/pop. – Dichromaticism

@Cupidity The term vptr means vtable ptr, not virtual base ptr. Having a real full size pointer to any part of the same object is absolutely a possible approach. As you say, it implies such object can't be copied byte by byte (or compared byte by byte). But then so what? As for saving size by packing", the best way to store no base subobject offset in each an every subobject, just a vptr to a vtable with all the info (which is specific to the subobject). That's one vptr by class in the hierarchy, max. Less because there is non virtual inheritance (and for other reasons). – Fayefayette

Answer 2

I've run the code and the answers to sizes of Classes' sizes were

sizeof(CBaseEntity) = 16 
sizeof(CBaseWeapon) = 32
sizeof(Prefab) = 24
sizeof(WeaponPrefab) = 48

Generally speaking, implementation of virtual functions and virtual inheritance are implementation defined and can vary depending on compiler and other options. That's being said, perhaps I can provide some explanations over the sizes of the objects, at least for a possible implementation.

CBaseEntity is simply a polymorphic type and thus has a pointer towards vtable (true for all implementations of C++ I am aware of, but not mandated by standard), it also contains int64. Size of pointer = 8, size of int64 = 8, so in total it is exactly 16.

CBaseWeapon inherits from CBaseEntity and holds a double. It already has to be at least of size 24. Now virtual inheritance means that the difference between location of objects of CBaseWeapon and CBaseEntity is not fixed - only final class determines it. This information needs to be stored inside the class' instance. I believe the info is located somewhere in the beginning of CBaseWeapon's layout. And to contain this info, one ought to add padding so size is divisible by 8 due to alignment requirements. Thus, the total size sums up to 32. Basically, it adds 16 on top of CBaseEntity

Prefab similarly to CBaseWeapon, but it doesn't hold double. So 24 or 8 on top of CBaseEntity.

WeaponPrefab inherits virtually from CBaseEntity, CBaseWeapon, Prefab, and contains char[8]. So, it already needs 16+16+8+8 = 48. If anything, it is surprising that WeaponPrefab isn't bigger. It is likely because Prefab doesn't store any objects and the two classes somehow share the layout-location variable optimizing the storage size of the class. Say, if you add a double member to Prefab, the size of WeaponPrefab will increase to 64.

But, as I previously said, it depends a lot on exact specification. I don't know for which platform you code. I am sure the ABI's specification is somewhere on the internet and you can look up the details. For instance, check out the Itanium C++ ABI which may or may not be relevant to you.

Edit: as was analyzed by @MilesBudnek the "layout-location variable" is actually pointer to compiler generated offset-table. So it takes 8 bytes in or whatever the platform dictates.

Cupidity

Thank you so much for explaining! Just curious why Prefab would be 24? To me, it should only contain a vptr and a CBaseEntity::m_ivar, thus 16 in total. – Ochre

@Ochre Prefab contains CBaseEntity which is already 16. +8 more for layout-info. – Cupidity

@Ochre But you are both correct! There is ambiguity in Q: "what is size of a class that has virtual bases". It's two Q and so it has two A, and you gave one, ALX23z gave the other. Both answers are essential for defining layout: ALX23z gave the value of the allocation of a complete object (or member subobject, or array subobject). You gave the answer for defining the layout of a base subobject in a hierarchy. Only virtual inheritance has such property. – Fayefayette

"16+16+8+8 = 48" I am not convince you should be making additions, except as estimates. These aren't data members sizes! We can't always add sizes of bases, even with your precaution: you added sizes that aren't complete (sizeof). To evaluate a size, you have to understand how vtables work, what they need to contain, which requires knowing class layout, based on the ... vtables. It's intricated. – Fayefayette

My previous comment was simplistic. You should do additions when vtables have different uses, that is, bases must different virtual tables because of divergence of their invariants, so you must count vtable invariants: classes with different virtual functions always have different vtables. (Virtual functions with the same signature can be the same or different depending on the class layout, depending on the number of vptr, in the end: depending on whether virtual functions are the same.) For overriders, it depends whether the ABI stipulates that an overrider has its own vtable entry for speed. – Fayefayette

Answer 3

Unlike the rules for layout of a vptr (short for vtable pointer) in each instance, and vtable, for SI (single inheritance) which are pretty simple (1), the rules here are quite complicated and while I'm willing to discuss these in extreme details, I assume it can be slightly boring - and totally irrelevant if the request is simply: can I keep the same layout (and ABI) with virtual as with non virtual inheritance.

The rules are more complicated for virtual inheritance than for simple, non virtual inheritance, because virtual means basically the same thing (2) for member functions and for base classes: it adds a level of flexibility, a potential for changing behavior, as allowed by "overriding" (3) the assertion (4) in derived classes.

But virtual inheritance overrides base class inheritance so it affects data layout, unlike virtual function overriding!

That flexibility is implemented, as always, by adding a level of indirection. It can be done by either:

• an internal pointer for another object fragment inside a base class subobject;
• an offset representing the relative position of that fragment;
• or a vptr to a vtable with all that base class subobject (subobject of another given class) dependent, instance independent information: the information depends on which specific base class subobject (as specified by a complete inheritance path (5) from the most derived object) we are in, but not a specific instance (all specific bases of a complete object have the same relative positions).

That latest choice is the most space efficient: at most one pointer by base class subobject, often less (issue too complex to discuss when exactly another vptr will be introduced, unless you want me to give details (6)).

NOTES

(1) Even trivial if you exclude issues such as destructor calls vs. delete operator, the typeid operator, and the power of dynamic_cast (to a class pointer or a void pointer).

(2) I know many authors explain that the virtual keyword is overloaded for two totally unrelated purposes here, but I disagree.

(3) The word overriding isn't normally used for virtual bases: we don't usually define virtual inheritance as an overriding of another inheritance, but saying so fits in the analogy with virtual functions overriding.

(4) Because base class inheritance isn't "declared" in a derived class, as : public Base is not a declaration, I use "assertion" here; the syntax : public Base "asserts" that Base is a public base, just like virtual void foo(); "asserts" that foo() is a virtual member function.

(5) A complete inheritance path mentions every single direct base needed to reach a specific indirect base, like MostDerived::Derived2::Derived1::Base. Only with such path you can unambiguously designate a base class subobject in all cases. (7)

Derived-to-base pointer conversions are only specified in term of allowable complete path: a pointer can be converted to a base type only if one such path can be found (and with virtual inheritance, many such paths can exists which are equivalent).

(6) I can add a lot of fine details if you wish; it's a promise - or a threat if you fear fine ABI details...

(7) It's worth noting that early versions of C++ standards had no serious explanation of such paths, which is a fundamental C++ inheritance concept, especially when dealing with multiple inheritance.

It was left completely implicit, to be inferred by the intuitive reader: decoding the standard is an exercice of critical thoughts and intuition. If you stick to black and white letters and rules, you will often miss the whole idea and get stuff wrong! But that intuitive reading can only work if educated by serious C++ skills.

Fayefayette