Layout de objeto no caso de funções virtuais e herança múltipla

Question

Recentemente fui questionado em uma entrevista sobre layout de objetos com funções virtuais e herança múltipla envolvida.
Expliquei isso no contexto de como ele é implementado sem o envolvimento de herança múltipla (ou seja,como o compilador gerou a tabela virtual, insira um ponteiro secreto para a tabela virtual em cada objeto e assim por diante).
Pareceu-me que faltava alguma coisa na minha explicação.
Então aqui estão as perguntas (veja o exemplo abaixo)

1. Qual é o layout exato da memória do objeto da classe C.
2. Entradas de tabelas virtuais para classe C.
3. Tamanhos (conforme retornados por sizeof) de objetos das classes A, B e C.(8, 8, 16 ??)
4. E se a herança virtual for usada.Certamente os tamanhos e entradas da tabela virtual devem ser afetados?

Código de exemplo:

class A {  
  public:   
    virtual int funA();     
  private:  
    int a;  
};

class B {  
  public:  
    virtual int funB();  
  private:  
    int b;  
};  

class C : public A, public B {  
  private:  
    int c;  
};   

Obrigado!

Answer 1

O layout da memória e o layout vtable dependem do seu compilador. Usando meu GCC, por exemplo, eles se parecem com o seguinte:

sizeof(int) == 4
sizeof(A) == 8
sizeof(B) == 8
sizeof(C) == 20

Observe que o sizeof (int) e o espaço necessário para o ponteiro vtable também podem variar de compilador para compilador e plataforma para plataforma. A razão pela qual tamanho de (c) == 20 e não 16 é que o GCC confere 8 bytes para o subobjeto A, 8 bytes para o subobjeto B e 4 bytes para seu membro int c.

Vtable for C
C::_ZTV1C: 6u entries
0     (int (*)(...))0
4     (int (*)(...))(& _ZTI1C)
8     A::funA
12    (int (*)(...))-0x00000000000000008
16    (int (*)(...))(& _ZTI1C)
20    B::funB

Class C
   size=20 align=4
   base size=20 base align=4
C (0x40bd5e00) 0
    vptr=((& C::_ZTV1C) + 8u)
  A (0x40bd6080) 0
      primary-for C (0x40bd5e00)
  B (0x40bd60c0) 8
      vptr=((& C::_ZTV1C) + 20u)

Usando herança virtual

class C : public virtual A, public virtual B

o layout muda para

Vtable for C
C::_ZTV1C: 12u entries
0     16u
4     8u
8     (int (*)(...))0
12    (int (*)(...))(& _ZTI1C)
16    0u
20    (int (*)(...))-0x00000000000000008
24    (int (*)(...))(& _ZTI1C)
28    A::funA
32    0u
36    (int (*)(...))-0x00000000000000010
40    (int (*)(...))(& _ZTI1C)
44    B::funB

VTT for C
C::_ZTT1C: 3u entries
0     ((& C::_ZTV1C) + 16u)
4     ((& C::_ZTV1C) + 28u)
8     ((& C::_ZTV1C) + 44u)

Class C
   size=24 align=4
   base size=8 base align=4
C (0x40bd5e00) 0
    vptridx=0u vptr=((& C::_ZTV1C) + 16u)
  A (0x40bd6080) 8 virtual
      vptridx=4u vbaseoffset=-0x0000000000000000c vptr=((& C::_ZTV1C) + 28u)
  B (0x40bd60c0) 16 virtual
      vptridx=8u vbaseoffset=-0x00000000000000010 vptr=((& C::_ZTV1C) + 44u)

Usando o GCC, você pode adicionar -fdump-class-hierarchy Para obter essas informações.

Answer 2

1 coisa a esperar com a herança múltipla é que seu ponteiro pode mudar ao lançar para uma subclasse (normalmente não a primeira). Algo que você deve estar ciente ao depurar e responder a perguntas da entrevista.

Answer 3

Primeiro, uma classe polimórfica possui pelo menos uma função virtual, portanto possui um vptr:

struct A {
    virtual void foo();
};

é compilado para:

struct A__vtable { // vtable for objects of declared type A
    void (*foo__ptr) (A *__this); // pointer to foo() virtual function
};

void A__foo (A *__this); // A::foo ()

// vtable for objects of real (dynamic) type A
const A__vtable A__real = { // vtable is never modified
    /*foo__ptr =*/ A__foo
};

struct A {
    A__vtable const *__vptr; // ptr to const not const ptr
                             // vptr is modified at runtime
};

// default constructor for class A (implicitly declared)
void A__ctor (A *__that) { 
    __that->__vptr = &A__real;
}

Observação:C++ pode ser compilado para outra linguagem de alto nível como C (como fez o cfront) ou até mesmo para um subconjunto C++ (aqui C++ sem virtual).Eu coloco __ em nomes gerados pelo compilador.

Observe que este é um simplista modelo onde RTTI não é suportado;compiladores reais adicionarão dados na vtable para suportar typeid.

Agora, uma classe derivada simples:

struct Der : A {
    override void foo();
    virtual void bar();
};

Subobjetos de classe base não virtuais (*) são subobjetos como subobjetos de membros, mas enquanto subobjetos de membros são objetos completos, ou seja.seu tipo real (dinâmico) é o tipo declarado, os subobjetos da classe base não estão completos e seu tipo real muda durante a construção.

(*) as bases virtuais são muito diferentes, assim como as funções de membro virtual são diferentes dos membros não virtuais

struct Der__vtable { // vtable for objects of declared type Der
    A__vtable __primary_base; // first position
    void (*bar__ptr) (Der *__this); 
};

// overriding of a virtual function in A:
void Der__foo (A *__this); // Der::foo ()

// new virtual function in Der:
void Der__bar (Der *__this); // Der::bar ()

// vtable for objects of real (dynamic) type Der
const Der__vtable Der__real = { 
    { /*foo__ptr =*/ Der__foo },
    /*foo__ptr =*/ Der__bar
};

struct Der { // no additional vptr
    A __primary_base; // first position
};

Aqui, "primeira posição" significa que o membro deve ser o primeiro (outros membros podem ser reordenados):eles estão localizados no deslocamento zero para que possamos reinterpret_cast ponteiros, os tipos são compatíveis;em deslocamento diferente de zero, teríamos que fazer ajustes de ponteiro com aritmética em char*.

A falta de ajuste pode não parecer grande coisa em termos de código gerado (apenas alguns adicionam instruções imediatas), mas significa muito mais do que isso, significa que tais ponteiros podem ser vistos como tendo tipos diferentes:um objeto do tipo A__vtable* pode conter um ponteiro para Der__vtable e ser tratado como um Der__vtable* ou um A__vtable*.O mesmo objeto ponteiro serve como um ponteiro para um A__vtable em funções que lidam com objetos do tipo A e como um ponteiro para um Der__vtable em funções que lidam com objetos do tipo Der.

// default constructor for class Der (implicitly declared)
void Der__ctor (Der *__this) { 
    A__ctor (reinterpret_cast<A*> (__this));
    __this->__vptr = reinterpret_cast<A__vtable const*> (&Der__real);
}

Você vê que o tipo dinâmico, conforme definido pelo vptr, muda durante a construção à medida que atribuímos um novo valor ao vptr (neste caso específico, a chamada ao construtor da classe base não faz nada de útil e pode ser otimizada, mas não é (é o caso de construtores não triviais).

Com herança múltipla:

struct C : A, B {};

A C instância conterá um A e um B, assim:

struct C {
    A base__A; // primary base
    B base__B;
};

Observe que apenas um desses subobjetos da classe base pode ter o privilégio de ficar no deslocamento zero;isso é importante de várias maneiras:

• A conversão de ponteiros em outras classes base (upcasts) precisará de um ajuste;por outro lado, os upcasts precisam de ajustes opostos;

• Isso implica que, ao fazer uma chamada virtual com um ponteiro de classe base, o this tem o valor correto para entrada no substituto da classe derivada.

Então o seguinte código:

void B::printaddr() {
    printf ("%p", this);
}

void C::printaddr () { // overrides B::printaddr()
    printf ("%p", this);
}

pode ser compilado para

void B__printaddr (B *__this) {
    printf ("%p", __this);
}

// proper C::printaddr taking a this of type C* (new vtable entry in C)
void C__printaddr (C *__this) {
    printf ("%p", __this);
}

// C::printaddr overrider for B::printaddr
// needed for compatibility in vtable
void C__B__printaddr (B *__this) {
    C__printaddr (reinterpret_cast<C*>(reinterpret_cast<char*> (__this) - offset__C__B));
}

Nós vemos o C__B__printaddr tipo e semântica declarados são compatíveis com B__printaddr, então podemos usar &C__B__printaddr na tabela v de B; C__printaddr não é compatível, mas pode ser usado para chamadas envolvendo um C objetos ou classes derivadas de C.

Uma função membro não virtual é como uma função gratuita que tem acesso a itens internos.Uma função de membro virtual é um "ponto de flexibilidade" que pode ser personalizado por substituição.a declaração de função de membro virtual desempenha um papel especial na definição de uma classe:como outros membros, fazem parte do contrato com o mundo externo, mas ao mesmo tempo fazem parte de um contrato com a classe derivada.

Uma classe base não virtual é como um objeto membro onde podemos refinar o comportamento por meio de substituição (também podemos acessar membros protegidos).Para o mundo externo, a herança para A em Der implica que existirão conversões implícitas derivadas para base para ponteiros, que um A& pode ser vinculado a um Der valor, etc.Para outras classes derivadas (derivadas de Der), isso também significa que funções virtuais de A são herdados no Der:funções virtuais em A pode ser substituído em outras classes derivadas.

Quando uma classe é derivada posteriormente, digamos Der2 é derivado de Der, conversões implícitas e ponteiros do tipo Der2* para A* é semanticamente realizado na etapa:primeiro, uma conversão para Der* é validado (o controle de acesso à relação de herança de Der2 de Der é verificado com as regras normais de público/protegido/privado/amigo), então o controle de acesso de Der para A.Uma relação de herança não virtual não pode ser refinada ou substituída em classes derivadas.

Funções de membros não virtuais podem ser chamadas diretamente e membros virtuais devem ser chamados indiretamente através da vtable (a menos que o tipo de objeto real seja conhecido pelo compilador), então o virtual palavra-chave adiciona uma indireção ao acesso às funções de membros.Assim como para os membros da função, o virtual palavra-chave adiciona uma indireção ao acesso ao objeto base;assim como acontece com as funções, as classes base virtuais adicionam um ponto de flexibilidade na herança.

Ao fazer herança múltipla não virtual, repetida:

struct Top { int i; };
struct Left : Top { };
struct Right : Top { };
struct Bottom : Left, Right { };

Existem apenas dois Top::i subobjetos em Bottom (Left::i e Right::i), como acontece com objetos membros:

struct Top { int i; };
struct mLeft { Top t; };
struct mRight { mTop t; };
struct mBottom { mLeft l; mRight r; }

Ninguém está surpreso que existam dois int submembros (l.t.i e r.t.i).

Com funções virtuais:

struct Top { virtual void foo(); };
struct Left : Top { }; // could override foo
struct Right : Top { }; // could override foo
struct Bottom : Left, Right { }; // could override foo (both)

isso significa que existem duas funções virtuais diferentes (não relacionadas) chamadas foo, com entradas vtable distintas (ambas como possuem a mesma assinatura, podem ter um overrider comum).

A semântica das classes base não virtuais decorre do fato de que a herança básica, não virtual, é uma relação exclusiva:a relação de herança estabelecida entre Esquerda e Topo não pode ser modificada por uma derivação adicional, então o fato de existir uma relação semelhante entre Right e Top não pode afetar esta relação.Em particular, significa que Left::Top::foo() pode ser substituído em Left e em Bottom, mas Right, que não tem relação de herança com Left::Top, não é possível configurar esse ponto de customização.

As classes base virtuais são diferentes:uma herança virtual é uma relação compartilhada que pode ser customizada em classes derivadas:

struct Top { int i; virtual void foo(); };
struct vLeft : virtual Top { }; 
struct vRight : virtual Top { };
struct vBottom : vLeft, vRight { }; 

Aqui, este é apenas um subobjeto da classe base Top, apenas um int membro.

Implementação:

O espaço para classes base não virtuais é alocado com base em um layout estático com deslocamentos fixos na classe derivada.Observe que o layout de uma classe derivada é incluído no layout de mais classes derivadas, portanto a posição exata dos subobjetos não depende do tipo real (dinâmico) do objeto (assim como o endereço de uma função não virtual é uma constante ).OTOH, a posição dos subobjetos em uma classe com herança virtual é determinada pelo tipo dinâmico (assim como o endereço da implementação de uma função virtual é conhecido apenas quando o tipo dinâmico é conhecido).

A localização do subobjeto será determinada em tempo de execução com o vptr e a vtable (a reutilização do vptr existente implica menos sobrecarga de espaço) ou um ponteiro interno direto para o subobjeto (mais sobrecarga, menos indireções necessárias).

Como o deslocamento de uma classe base virtual é determinado apenas para um objeto completo e não pode ser conhecido para um determinado tipo declarado, uma base virtual não pode ser alocada no deslocamento zero e nunca é uma base primária.Uma classe derivada nunca reutilizará o vptr de uma base virtual como seu próprio vptr.

Em termos de possível tradução:

struct vLeft__vtable { 
    int Top__offset; // relative vLeft-Top offset
    void (*foo__ptr) (vLeft *__this); 
    // additional virtual member function go here
};

// this is what a subobject of type vLeft looks like
struct vLeft__subobject { 
    vLeft__vtable const *__vptr;
    // data members go here
};

void vLeft__subobject__ctor (vLeft__subobject *__this) { 
    // initialise data members
}

// this is a complete object of type vLeft 
struct vLeft__complete {
    vLeft__subobject __sub;
    Top Top__base;
}; 

// non virtual calls to vLeft::foo
void vLeft__real__foo (vLeft__complete *__this);

// virtual function implementation: call via base class
// layout is vLeft__complete 
void Top__in__vLeft__foo (Top *__this) {
    // inverse .Top__base member access 
    char *cp = reinterpret_cast<char*> (__this);
    cp -= offsetof (vLeft__complete,Top__base);
    vLeft__complete *__real = reinterpret_cast<vLeft__complete*> (cp);
    vLeft__real__foo (__real);
}

void vLeft__foo (vLeft *__this) {
    vLeft__real__foo (reinterpret_cast<vLeft__complete*> (__this));
}

// Top vtable for objects of real type vLeft
const Top__vtable Top__in__vLeft__real = { 
    /*foo__ptr =*/ Top__in__vLeft__foo 
};

// vLeft vtable for objects of real type vLeft
const vLeft__vtable vLeft__real = { 
    /*Top__offset=*/ offsetof(vLeft__complete, Top__base),
    /*foo__ptr =*/ vLeft__foo 
};

void vLeft__complete__ctor (vLeft__complete *__this) { 
    // construct virtual bases first
    Top__ctor (&__this->Top__base); 

    // construct non virtual bases: 
    // change dynamic type to vLeft
    // adjust both virtual base class vptr and current vptr
    __this->Top__base.__vptr = &Top__in__vLeft__real;
    __this->__vptr = &vLeft__real;

    vLeft__subobject__ctor (&__this->__sub);
}

Para um objeto de tipo conhecido, o acesso à classe base é feito através vLeft__complete:

struct a_vLeft {
    vLeft m;
};

void f(a_vLeft &r) {
    Top &t = r.m; // upcast
    printf ("%p", &t);
}

é traduzido para:

struct a_vLeft {
    vLeft__complete m;
};

void f(a_vLeft &r) {
    Top &t = r.m.Top__base;
    printf ("%p", &t);
}

Aqui o tipo real (dinâmico) de r.m é conhecido e também a posição relativa do subobjeto é conhecida em tempo de compilação.Mas aqui:

void f(vLeft &r) {
    Top &t = r; // upcast
    printf ("%p", &t);
}

o tipo real (dinâmico) de r não é conhecido, então o acesso é através do vptr:

void f(vLeft &r) {
    int off = r.__vptr->Top__offset;
    char *p = reinterpret_cast<char*> (&r) + off;
    printf ("%p", p);
}

Esta função pode aceitar qualquer classe derivada com um layout diferente:

// this is what a subobject of type vBottom looks like
struct vBottom__subobject { 
    vLeft__subobject vLeft__base; // primary base
    vRight__subobject vRight__base; 
    // data members go here
};

// this is a complete object of type vBottom 
struct vBottom__complete {
    vBottom__subobject __sub; 
    // virtual base classes follow:
    Top Top__base;
}; 

Observe que o vLeft classe base está em um local fixo em um vBottom__subobject, então vBottom__subobject.__ptr é usado como um vptr para o todo vBottom.

Semântica:

A relação de herança é compartilhada por todas as classes derivadas;isso significa que o direito de anulação é compartilhado, então vRight pode substituir vLeft::foo.Isso cria um compartilhamento de responsabilidades: vLeft e vRight devem concordar sobre como eles personalizam Top:

struct Top { virtual void foo(); };
struct vLeft : virtual Top { 
    override void foo(); // I want to customise Top
}; 
struct vRight : virtual Top { 
    override void foo(); // I want to customise Top
}; 
struct vBottom : vLeft, vRight { };  // error

Aqui vemos um conflito: vLeft e vRight procuram definir o comportamento da única função virtual foo, e vBottom a definição está errada por falta de um overrider comum.

struct vBottom : vLeft, vRight  { 
    override void foo(); // reconcile vLeft and vRight 
                         // with a common overrider
};

Implementação:

A construção de classes com classes base não virtuais envolve chamar construtores de classes base na mesma ordem feita para variáveis ​​de membro, alterando o tipo dinâmico cada vez que inserimos um ctor.Durante a construção, os subobjetos da classe base realmente agem como se fossem objetos completos (isso é verdade até mesmo com subobjetos de classe base abstratos completos e impossíveis:são objetos com funções virtuais indefinidas (puras).Funções virtuais e RTTI podem ser chamadas durante a construção (exceto, é claro, funções virtuais puras).

A construção de uma classe com base não virtual classes com bases virtuais é mais complicada:durante a construção, o tipo dinâmico é o tipo da classe base, mas o layout da base virtual ainda é o layout do tipo mais derivado que ainda não foi construído, então precisamos de mais vtables para descrever este estado:

// vtable for construction of vLeft subobject of future type vBottom
const vLeft__vtable vLeft__ctor__vBottom = { 
    /*Top__offset=*/ offsetof(vBottom__complete, Top__base),
    /*foo__ptr =*/ vLeft__foo 
};

As funções virtuais são as de vLeft (durante a construção, a vida útil do objeto vBottom ainda não começou), enquanto as localizações da base virtual são aquelas de um vBottom (conforme definido no vBottom__complete traduzido contestado).

Semântica:

Durante a inicialização, é óbvio que devemos ter cuidado para não utilizar um objeto antes de ele ser inicializado.Como C++ nos dá um nome antes de um objeto ser totalmente inicializado, é fácil fazer isso:

int foo (int *p) { return *pi; }
int i = foo(&i); 

ou com o ponteiro this no construtor:

struct silly { 
    int i;
    std::string s;
    static int foo (bad *p) { 
        p->s.empty(); // s is not even constructed!
        return p->i; // i is not set!
    }
    silly () : i(foo(this)) { }
};

É bastante óbvio que qualquer uso de this no ctor-init-list deve ser verificado cuidadosamente.Após a inicialização de todos os membros, this pode ser passado para outras funções e registrado em algum conjunto (até o início da destruição).

O que é menos óbvio é que quando se constrói uma classe envolvendo bases virtuais compartilhadas, os subobjetos deixam de ser construídos:durante a construção de um vBottom:

• primeiro as bases virtuais são construídas:quando Top é construído, é construído como um sujeito normal (Top nem sabe que é base virtual)

• então as classes base são construídas na ordem da esquerda para a direita:o vLeft subobjeto é construído e se torna funcional como um objeto normal vLeft (mas com um vBottom layout), então o Top O subobjeto da classe base agora tem um vLeft tipo dinâmico;

• o vRight a construção do subobjeto começa e o tipo dinâmico da classe base muda para vRight;mas vRight não é derivado de vLeft, não sabe nada sobre vLeft, então o vLeft a base agora está quebrada;

• quando o corpo do Bottom o construtor começa, os tipos de todos os subobjetos foram estabilizados e vLeft está funcional novamente.

Answer 4

Não tenho certeza de como essa resposta pode ser tomada como uma resposta completa sem a menção dos bits de alinhamento ou preenchimento.

Deixe -me dar um pouco de alinhamento:

"Diz-se que um endereço de memória A está alinhado quando A é um múltiplo de n bytes (onde n é um poder de 2). Nesse contexto, um byte é a menor unidade de acesso à memória, ou seja, cada endereço de memória especifica Um byte diferente. Um endereço alinhado de N-byte teria zeros de menos significativos log2 (n) quando expresso em binário.

A redação alternativa alinhada Bit alinhada designa o endereço alinhado de AB/8 bytes (Ex. Alinhado de 64 bits é 8 bytes alinhados).

Diz-se que um acesso à memória está alinhado quando o dado acessado é n bytes de comprimento e o endereço de dado está alinhado por N-byte. Quando um acesso à memória não está alinhado, diz -se que está desalinhado. Observe que, por definição, os acessos por memória de bytes estão sempre alinhados.

Diz-se que um ponteiro de memória que se refere a dados primitivos que são n bytes de comprimento estão alinhados se forem permitidos apenas endereços que estejam alinhados com N-bytes, caso contrário, é considerado inalinado. Um ponteiro de memória que se refere a um agregado de dados (uma estrutura ou matriz de dados) está alinhado se (e somente se) cada dado primitivo no agregado estiver alinhado.

Observe que as definições acima assumem que cada dado primitivo é um poder de dois bytes de comprimento. Quando esse não é o caso (como no ponto flutuante de 80 bits no x86), o contexto influencia as condições em que o dado é considerado alinhado ou não.

As estruturas de dados podem ser armazenadas na memória na pilha com um tamanho estático conhecido como limitado ou na pilha com um tamanho dinâmico conhecido como ilimitado. " - do wiki ...

Para manter o alinhamento, o compilador insere bits de preenchimento no código compilado de um objeto de estrutura/classe. "Embora o compilador (ou intérprete) aloce normalmente itens de dados individuais sobre limites alinhados, as estruturas de dados geralmente têm membros com diferentes requisitos de alinhamento. Para manter o alinhamento adequado, o tradutor normalmente insere membros adicionais de dados não identificados para que cada membro esteja alinhado adequadamente. Além disso, o A estrutura de dados como um todo pode ser acolchoada com um membro final sem nome. Isso permite que cada membro de uma variedade de estruturas seja adequadamente alinhado. .... ....

O preenchimento é inserido apenas quando um membro da estrutura é seguido por um membro com um requisito de alinhamento maior ou no final da estrutura " - wiki

Para obter mais informações sobre como o GCC faz isso, olhe para

http://www.delorie.com/gnu/docs/gcc/gccint_111.html

e procure o texto "alinhamento básico"

Agora vamos chegar a este problema:

Usando a classe de exemplo, criei este programa para um compilador GCC em execução em um Ubuntu de 64 bits.

int main() {
    cout << "!!!Hello World!!!" << endl; // prints !!!Hello World!!!
    A objA;
    C objC;
    cout<<__alignof__(objA.a)<<endl;
    cout<<sizeof(void*)<<endl;
    cout<<sizeof(int)<<endl;
    cout<<sizeof(A)<<endl;
    cout<<sizeof(B)<<endl;
    cout<<sizeof(C)<<endl;
    cout<<__alignof__(objC.a)<<endl;
    cout<<__alignof__(A)<<endl;
    cout<<__alignof__(C)<<endl;
    return 0;
}

E o resultado deste programa é o seguinte:

4
8
4
16
16
32
4
8
8

Agora deixe -me explicar. Como ambos os A&B têm funções virtuais, eles criarão VTABLES separados e VPTR será adicionado no início de seus objetos, respectivamente.

Portanto, o objeto da Classe A terá um VPTR (apontando para a vtable de a) e um int. O ponteiro terá 8 byte de comprimento e o int terá 4 byte de comprimento. Portanto, antes da compilação, o tamanho é de 12 bytes. Mas o compilador adicionará 4 bytes extras no final de Int A como bits de preenchimento. Portanto, após a compilação, o tamanho dos objetos de A será 12+4 = 16.

Da mesma forma para os objetos da classe B.

Agora, o objeto de C terá dois VPTRs (um para cada classe A e classe B) e 3 INTs (A, B, C). Portanto, o tamanho deveria ter sido 8 (VPTR A) + 4 (int a) + 4 (bytes de preenchimento) + 8 (VPTR B) + 4 (int b) + 4 (int c) = 32 bytes. Portanto, o tamanho total de C será de 32 bytes.