Voyage en C++ie : un diamant d'innocence

MISC HS n° 018 | novembre 2018 | Serge Guelton
Creative Commons
  • Actuellement 0 sur 5 étoiles
0
Merci d'avoir participé !
Vous avez déjà noté cette page, vous ne pouvez la noter qu'une fois !
Votre note a été changée, merci de votre participation !
Cet article est le troisième d'une mini-série sur le C++, ou plutôt sur les binaires compilés depuis C++, leurs particularités, comment les concepts du langage se retrouvent parfois dans le binaire final.

Cet opus corrige un oublie lors de l'épisode précèdent (Voyage en C++ie : les objets, publié dans MISC n°96), et présente le boss final : le fameux « deadly diamond of death ». Manquement d'autant plus intolérable dans une revue des Éditions Diamond…

1. Le problème du diamant

Imaginons la (mauvaise) hiérarchie de classe suivante, qui n'est pas sans rappeler certains jeux très ancrés dans l'imaginaire médiéval fantastique.

struct Fighter {
    int hp = 10;
    int chop() const;
};
 
struct Warrior : Fighter {
};
 
struct Monk : Fighter {
};

Osons maintenant créer un type de personnage bi-classé (et d'une humilité sans faille) :

struct Me : Warrior, Monk {
    void strike(Fighter& other) const {
        if(hp>0)
            other.hp -= chop();
    };
};

Ce code ne compile pas, et pour cause : Warrior et Monk ont une base commune, Fighter et l'accès à hp est ambigu. Quand on veut que les membres communs ne soient présents qu'une seule fois, et c'est le cas ici, on utilise l'héritage virtuel, le fameux héritage en diamant.

struct Warrior : virtual Fighter {
};
 
struct Monk : virtual Fighter {
};

Il n'y aura alors qu'une seule instance de Fighter instanciée par instance de Me (notez l'élégante référence à une célèbre licence de jeux de baston édités par SEGA).

2. Initialisation d'un objet avec héritage virtuel

Si l'on tente d'instancier un objet de la classe Me :

Me spontaneaous_me() {
    return {};
}

On obtient le bitcode LLVM suivant (d'après clang++ -S -emit-llvm -O0 -o - diamond.cpp -std=c++11 | c++filt, on regardera le code optimisé une fois qu'on a bien tout compris) que nous allons décortiquer. Notons le filtrage par c++filt pour appliquer le demangling (décodage des symboles, cf. épisodes précédents disponibles chez tous les bons libraires) sur le bitcode LLVM, cette commande est bien pensée ! J'ai enlevé quelques attributs (genre align 8 sur les store) pour ne garder que l'essentiel.

define linkonce_odr void @Me::Me()(%struct.Me*) {
  ; copy parameter to a register through the stack,

  ; let's call this register `this'
  %2 = alloca %struct.Me*
  store %struct.Me* %0, %struct.Me** %2
  %3 = load %struct.Me*, %struct.Me** %2
  ; access the 16th byte of `this' and

  ;cast it to Fighter* to initialize it
  %4 = bitcast %struct.Me* %3 to i8*
  %5 = getelementptr inbounds i8, i8* %4, i64 16
  %6 = bitcast i8* %5 to %struct.Fighter*
  call void @Fighter::Fighter()(%struct.Fighter* %6)
 
  ; cast this as warrior and call a specific constructor

  ;that uses the 1st element of the VTT
  %7 = bitcast %struct.Me* %3 to %struct.Warrior*
  call void @Warrior::Warrior()(%struct.Warrior* %7, i8** getelementptr inbounds ([4 x i8*], [4 x i8*]* @VTT for Me, i64 0, i64 1))
 
  ; access the 8th byte of `this' and

  ;cast it to Monk* to initialize it
  %8 = bitcast %struct.Me* %3 to i8*
  %9 = getelementptr inbounds i8, i8* %8, i64 8
  %10 = bitcast i8* %9 to %struct.Monk*
  call void @Monk::Monk()(%struct.Monk* %10, i8** getelementptr inbounds ([4 x i8*], [4 x i8*]* @VTT for Me, i64 0, i64 2))
 
  ;;;;;;;;;;;;;;;; PAUSE ;;;;;;;;;;;;;;;;
 
  ; store values from the vtable in the 0st bytes of `this'
  %11 = bitcast %struct.Me* %3 to i32 (...)***
  store i32 (...)** bitcast (i8** getelementptr inbounds ({ [3 x i8*], [3 x i8*] }, { [3 x i8*], [3 x i8*] }* @vtable for Me, i32 0, inrange i32 0, i32 3) to i32 (...)**), i32 (...)*** %11,
 
  ; store other values from the vtable in the 8th bytes of `this'
  %12 = bitcast %struct.Me* %3 to i8*
  %13 = getelementptr inbounds i8, i8* %12, i64 8
  %14 = bitcast i8* %13 to i32 (...)***
  store i32 (...)** bitcast (i8** getelementptr inbounds ({ [3 x i8*], [3 x i8*] }, { [3 x i8*], [3 x i8*] }* @vtable for Me, i32 0, inrange i32 1, i32 3) to i32 (...)**), i32 (...)*** %14
  ret void
}

Mmmmh, notre diamant a de multiples facettes qui reflètent autant de subtilités du langage ! On retrouve bien les constructeurs de chaque classe parente @Fighter::Fighter, @Warrior::Warrior et @Monk::Monk(), mais les deux derniers constructeurs prennent un nouveau paramètre, la VTT, la Virtual Table Table… Qu'est-ce donc ? Regardons son initialisation, en s'arrêtant à la ; PAUSE ; :

@VTT for Me = constant [4 x i8*] [
    i8* bitcast (i8** getelementptr inbounds ({ [3 x i8*], [3 x i8*] }, { [3 x i8*], [3 x i8*] }* @vtable for Me, i32 0, inrange i32 0, i32 3) to i8*),
    i8* bitcast (i8** getelementptr inbounds ({ [3 x i8*] }, { [3 x i8*] }* @construction vtable for Warrior-in-Me, i32 0, inrange i32 0, i32 3) to i8*),
    i8* bitcast (i8** getelementptr inbounds ({ [3 x i8*] }, { [3 x i8*] }* @construction vtable for Monk-in-Me, i32 0, inrange i32 0, i32 3) to i8*),
    i8* bitcast (i8** getelementptr inbounds ({ [3 x i8*], [3 x i8*] }, { [3 x i8*], [3 x i8*] }* @vtable for Me, i32 0, inrange i32 1, i32 3) to i8*)
]

Okay… On parle de construction vtable for Warrior-in-Me et de construction vtable for Monk-in-Me, inspectons cela :

@construction vtable for Warrior-in-Me = constant { [3 x i8*] } { [3 x i8*] [
    i8* inttoptr (i64 16 to i8*),
    i8* null,
    i8* bitcast ({ i8*, i8*, i32, i32, i8*, i64 }* @typeinfo for Warrior to i8*)
] }
@construction vtable for Monk-in-Me = constant { [3 x i8*] } { [3 x i8*] [
    i8* inttoptr (i64 8 to i8*),
    i8* null,
    i8* bitcast ({ i8*, i8*, i32, i32, i8*, i64 }* @typeinfo for Monk to i8*)
] }

Soit, un pointeur à null, des typeinfo et un entier qui ressemble à un offset… regardons comment cette VTT est utilisée par les constructeurs :

define void @Warrior::Warrior()(%struct.Warrior*, i8**) {
  : typical copy-arg-to-stack-then-load
  %3 = alloca %struct.Warrior*
  %4 = alloca i8**
  store %struct.Warrior* %0, %struct.Warrior** %3
  store i8** %1, i8*** %4
  %5 = load %struct.Warrior*, %struct.Warrior** %3
  %6 = load i8**, i8*** %4
 
  ; %5 = `this', %6 = `construction vtable for Warrior-in-Me'
  %7 = load i8*, i8** %6
  %8 = bitcast %struct.Warrior* %5 to i32 (...)***
  %9 = bitcast i8* %7 to i32 (...)**
 
  ; the VTT is stored in `this'
  store i32 (...)** %9, i32 (...)*** %8
  ret void
}

Le même schéma se retrouve pour l'appel au constructeur de Monk, on a donc maintenant une idée un peu plus précise de l’organisation mémoire du bouzin à la ; PAUSE ; :

---------------------------------------
 construction vtable for Warrior-in-Me
---------------------------------------
  construction vtable for Monk-in-Me
---------------------------------------
           actual attributes
---------------------------------------

Et si on continue après la ; PAUSE ;, on voit que les deux premiers champs sont écrasés par les vtables des deux parents ! En fait, les construction vtable for Warrior-in-Me et construction vtable for Monk-in-Me sont des tables temporaires qui permettent de construire l'objet alors qu'il n'est pas encore complètement initialisé. Effectivement, si on appelle une méthode virtuelle dans le constructeur de Warrior, l'ordre de résolution sera différent que si on l'appelle depuis le constructeur de Me, d'où cette rustine temporaire de la vtable. Extra !

Comme notre exemple est trop simple, ces tables ne sont pas vraiment utiles, comme le montre le code craché par clang en -02 :

define void @spontaneaous_me()(%struct.Me* noalias nocapture sret) {
  ; first set everything to zero
  %2 = bitcast %struct.Me* %0 to i8*
  tail call void @llvm.memset.p0i8.i64(i8* %2, i8 0, i64 24, i32 8, i1 false)
 
  ; store the actual attribute in the 2nd slot
  %3 = getelementptr inbounds %struct.Me, %struct.Me* %0, i64 0, i32 2, i32 0
  store i32 10, i32* %3
 
  ; store the two vtables in the 0th and 1st slot
  %4 = bitcast %struct.Me* %0 to <2 x i32 (...)**>*
  store <2 x i32 (...)**> <i32 (...)** bitcast (i8** getelementptr inbounds ({ [3 x i8*], [3 x i8*] }, { [3 x i8*], [3 x i8*] }* @vtable for Me, i64 0, i32 1, i64 0) to i32 (...)**), i32 (...)** bitcast (i8** getelementptr inbounds ({ [3 x i8*], [3 x i8*] }, { [3 x i8*], [3 x i8*] }* @vtable for Me, i64 1, i32 0, i64 0) to i32 (...)**)>, <2 x i32 (...)**>* %4
  ret void
}

Comme les vtable temporaires ne sont pas utilisées, l'optimiseur les a proprement dégagées. On remarquera combien l'optimisation faite par clang est raccord avec le discours :-)

Vérification par le code :

int main() {
  Me me = spontaneaous_me();
  void* raw = &me;
  void** as_ptr = (void**)raw;
  printf("%p - %p - %p\n", as_ptr[0], as_ptr[1], as_ptr[2]);
  return 0;
}

Qui à l'exécution affiche le tant attendu résultat :

$ ./diamond
0x4008a0 - 0x4008b8 - 0xa

Et un petit objdump -C -t diamond | grep 4008 nous confirme que la vtable de Me prend 48 octets chargés de 0x400888 à 0x4008b8, on est bon !

3. Poussière de diamant

Continuons avec un scénario d'apparence banale :

int chop(Me const& ref) {
    return ref.chop();
}

Une fois compilé sans optimisation, on obtient ce gros pavé, commenté au fil de l'eau :

define i32 @chop(Me&)(%struct.Me* dereferenceable(24)) #4 {

; copy-arg-to-stack-then-load-to-ref

%2 = alloca %struct.Me*

store %struct.Me* %0, %struct.Me** %2

%3 = load %struct.Me*, %struct.Me** %2

 

; load the first pointer inthis, i.e. the vtable for Warrior

%4 = bitcast %struct.Me* %3 to i8** %5 = load i8*, i8** %4

 

; access an element before this vtable, taking advantage of the vtable layout for Me

%6 = getelementptr i8, i8* %5, i64 -24

%7 = bitcast i8* %6 to i64*

%8 = load i64, i64* %7

 

; perform a small correction of thethisptr using the value from the vtable

%9 = bitcast %struct.Me* %3 to i8*

%10 = getelementptr inbounds i8, i8* %9, i64 %8

%11 = bitcast i8* %10 to %struct.Fighter*

%12 = call i32 @Fighter::chop() const(%struct.Fighter* %11)

ret i32 %12

}

L'offset de -24 peut paraître surprenant ! Mais si on se souvient de l'initialisation du premier champ de this, c'était à travers :

store i32 (...)** bitcast (i8** getelementptr inbounds ({ [3 x i8*], [3 x i8*] }, { [3 x i8*], [3 x i8*] }* @vtable for Me, i32 0, inrange i32 0, i32 3) to i32 (...)**), i32 (...)*** %11

Soit le 4ème élément du premier élément du tableau @vtable for Me qui n'en contient que 3… Donc le premier du deuxième élément. Et en reculant de 24 octets, on tombe (ouille) sur le premier champ du premier item, à savoir :

@vtable for Me = constant { [3 x i8*], [3 x i8*] } {
    [3 x i8*] [i8* inttoptr (i64 16 to i8*), i8* null, i8* bitcast ({ i8*, i8*, i32, i32, i8*, i64, i8*, i64 }* @typeinfo for Me to i8*)],
    [3 x i8*] [i8* inttoptr (i64 8 to i8*), i8* inttoptr (i64 -8 to i8*), i8* bitcast ({ i8*, i8*, i32, i32, i8*, i64, i8*, i64 }* @typeinfo for Me to i8*)]
}

Soit la valeur 0x10. Dans le doute, le code suivant permet de le confirmer :

int main() {
  Me me = spontaneaous_me();
  void* raw = &me;
  void** as_ptr = (void**)raw;
  void* vtable = as_ptr[0];
  printf("%p",(void*)*(intptr_t*)((char*)vtable -24));
  return 0;
}

À l’exécution, on obtient :

$ ./diamond
0x10

Ouf ! Ce petit ajustement de +16 permet de repositionner this après les deux vtable des classes filles, de façon à ce que this ressemble à une instance de Fighter normale :-)

Conclusion

Cette exploration de code devrait avoir un peu démystifié le diagramme en diamant à la sauce C++, avec pour effet de bord une piqûre de rappel sur les vtables. Comme quoi il y avait de quoi creuser !

Remerciements

Cet article a bénéficié des conseils et relectures de neitsa, papa zours et lancelot. Un grand merci à eux !