Thunksgiving
Posted 31/10/2010
on:Quoting Wikipedia:
The word thunk has at least three related meanings in computing science. A “thunk” may be:
- A piece of code to perform a delayed computation (similar to a closure)
- A feature of some virtual function table implementations (similar to a wrapper function)
- A mapping of machine data from one system-specific form to another, usually for compatibility reasons
In all three senses, the word refers to a piece of low-level code, usually machine-generated, that implements some detail of a particular software system.
In this post (whose name looks like an unrelated typo) we shall observe the need for a thunk of the second kind, in C++.
Let us consider the following multiple inheritance hierarchy:
#include <iostream> struct A { virtual A *clone () const { return new A(); } int a; }; struct B { virtual B *clone () const { return new B(); } int b; }; struct C : A, B { virtual C *clone () const { C *c = new C(); std::cout << c << std::endl; return c; } int c; }; int main () { B *b = new C(); B *b_cloned = b->clone(); std::cout << b_cloned << std::endl; }
Please, do not let the length of the code snippet intimidate you. The illustrated test case is actually pretty simple; Three classes are defined — A, B, and C. C is derived from the unrelated other classes. All classes share a single virtual function which allows to clone() them, and a single member variable – just so they aren’t empty. The purpose of the two printouts will be made clear soon.
One nuance worth paying attention to is the fact that the clone() function is refined within C::clone() to yield a pointer-to-C instead of pointer-to-A/B. This is called Covariance. I could talk a lot more about Covariance, Contravariance, and C++’s lack of support for Contravariance in function parameters, but these topics will have to wait for a later post.
Let us recap what memory layout do A, B, and C have (on a 32bit machine):
A: [ Avptr | int(a) ] 8bytes
B: [ Bvptr | int(b) ] 8bytes
C: [ Cvptr | int(a) | BCvptr | int(b) | int(c) ] 20bytes
Needless to say that a cast from C* to A* requires no effort at all, while the virtual table pointer (vptr) of class B (notice that it is labelled BCvptr, which is intentionally different from Bvptr) is where it is to allow convenient casts of the form C* to B*. Therefore, it is not surprising to discover that the compiler will actually carry out much needed pointer adjustments in the following case:
C c; B *b = &c; // b != &c. Actually, b = &c+8.
Now, onwards to the interesting part; What happens when we write line #31 in the original code snippet (invocation of C::clone() which yields a pointer-to-C, from a B context)? And more importantly, what is actually going on under the hood?
The call b->clone() is invoked through the BCvptr. Due to the dynamic type of the object being C, we expect C::clone() to be called. But here’s the catch — a call to C::clone() yields a pointer (to a newly constructed C object) which points to the head of a C object, rather than to a B object! If C::clone() would be called normally, we would have a pointer-to-B which points on the wrong memory area, and that would just make us all unhappy.. So what dark magic is there, within BCvptr, that allows this code to work flawlessly?
Using the magical -fdump-class-hierarchy flag for g++, and the wondrous c++filt utility, we can obtain the actual structure of C’s virtual table:
Vtable for C
C::vtable for C: 6u entries
0 (int (*)(...))0
4 (int (*)(...))(& typeinfo for C)
8 C::clone
12 (int (*)(...))-0x00000000000000008
16 (int (*)(...))(& typeinfo for C)
20 C::covariant return thunk to C::clone() const
I will not go into much detail about the whole structure as it is enough information for one post, but I do believe that what’s important to us is pretty apparent here: at offset 8 there’s the normal invocation of C::clone within a Cvptr, while at offset 20 (which is exactly 12+8) there’s a call to a “covariant return thunk to C::clone”. As you have probably guessed by now, BCvptr is actually a pointer to offset 12 within Cvptr. Therefore, when making the aforementioned b->clone() call — a call is made to the function whose address resides at offset 8 from the current vptr; And since the current vptr is BCvptr, a call to the thunk is made.
Obviously, the compiler essentially implements this thunk as a simple wrapper around C::clone() combined with the required pointer adjustment to yield a proper pointer-to-B. Some of you may find this technique pretty similar to the notion of a Trampoline.
To wrap things up, it should come as no surprise to you, that both printouts produce addresses which differ by 8bytes — which is the exact required adjustment.
13 Responses to "Thunksgiving"
Nice writeup!
i think the ‘pointer adjustment to yield a proper pointer-to-B’ cannot be part of the thunk itself – as it cannot know its return value is casted to a B*.
I also vaguely recall reading about a more complicated case that required a similar thunk. Something involving virtual bases – gonna look it up..
Ah, there: http://www.freepatentsonline.com/5297284.html
The case you described is in the paragraph starting with ‘The first case occurs when a function member in a derived class overrides a function member that is defined in more than one base class…’.
The other case is on the following paragraph: ‘The second case occurs when a derived class has a base class that overrides a function member in a virtual base class and the derived class itself does not override the function member…’
This stuff is exactly the reason multiple inheritance is banned in most coding standards, and thrown right out in C# (and i think also in most other modern languages).
[…] Roman just posted a nice investigation he did, mostly using the g++ switch -fdump-class-hierarchy – which dumps to stdout a graphical representation of generated classes layout. […]
1 | Michal Mocny
01/11/2010 at 17:48
Very Interesting.
I have never considered how covariance works with multiple inheritance.
Thanks!