动态调度之道—虚表

此文为旧博客文章的搬运重写。原博文大概只是介绍了 C++ 和多个不同版本的 Python 在复杂继承下类成员的解析顺序,最近重新研究了一波,重写了一下内容。

虚表是实现动态调度的方法之一,动态调度是一个运行期选择多态实现的过程。相比于其它一些实现,虚表是在某些限定条件下,时间和空间效率还算不错的方法。

主要使用虚表的语言是 C++ 系的,比如 C++ 、 Java 、 Delphi 等的实现。但是需要注意的是,虚表不是 C++ 标准或 Java 规范概念,它只是动态调度的一种常见实现。

本文从 x86-64 下的 GNU C++ Compiler (g++) 的实现来分析虚表是如何运作的。提示:自己分析的时候善用 g++ -fdump-class-hierarchy 来输出源文件中类的虚函数表,不过 clang++ 没有这个选项。

单继承

考虑下述代码:

#include <unistd.h>

struct A {
  int a;
  virtual void foo() {
    write(STDOUT_FILENO, "A::foo()\n", 9);
  }
  virtual void bar() {
    write(STDOUT_FILENO, "A::bar()\n", 9);
  }
  void baz() {
    write(STDOUT_FILENO, "A::baz()\n", 9);
  }
};

struct B: A {
  int b;
  virtual void foo() override {
    write(STDOUT_FILENO, "B::foo()\n", 9);
  }
  void baz() {
    write(STDOUT_FILENO, "B::baz()\n", 9);
  }
};

int main() {
  A *aptr = new A;
  A *bptr = new B;
}

因为太简单了,所以继承图就不画了。源码中, A::fooA::bar 均为虚函数, A::baz 为普通函数, B::foo overrides A::fooB::bar 继承自 A::barB::baz 为普通函数。

虚表如下图所示:

首先和没有任何虚成分的函数相比,结构体中多出了一个 sizeof(void *) 大小的 _vptr (当然不能直接被程序员使用)指向内存中的虚表,实际指向地址为虚表中的第一个函数。在下面的多继承中我们可以看到一个类其实是可以有多个虚指针的,事实上,只有每支继承路线的祖先才会有一个虚指针,每个虚指针的指向略有不同,不一定就是第一个函数。

单继承的动态调度非常简单,比如说我只有一个 A *ptr ,不需要知道它指向 A 还是 B ,调用 ptr->foo() 的时候,编译器知道 A::foo 是一个虚函数,所以运行时会去虚表中找。因为在 AB 的虚表中 foo bar 各自的偏移完全相同,所以可以直接加上偏移,然后调用即可,这样就不会有类型不同的影响。编译出来的 GAS x86-64 汇编中调度部分可能是这样的:

movq  -40(%rbp), %rax
movq  (%rax), %rax
movq  (%rax), %rax
movq  -40(%rbp), %rdi
call  *%rax

首先从栈上 -40(%rbp) 取得 ptr 的值,解引用一次后得到的是 _vptr 的值,也就是虚表地址,再解引用一次得到的是 foo 的地址(如果需要调用 bar 可以在第二次解引用前 addl 一个指针大小),最后准备好参数直接 callq 即可。

我在源码中留了一对 baz 函数,但是并没有在虚表中出现。这是因为 baz 调用的时候不会有动态调度,编译器可以直接根据指针类型确定调用的是 A::baz 还是 B::baz 静态绑定,所以根本不会涉及到虚表,也没有被放到虚表中。

多继承

好了,接下来只考虑虚函数,非虚的就无视了。考虑下述代码——

#include <unistd.h>

struct A {
  int a;
  virtual void foo() {
    write(STDOUT_FILENO, "A::foo()\n", 9);
  }
};

struct B {
  int b;
  virtual void bar() {
    write(STDOUT_FILENO, "B::bar()\n", 9);
  }
};

struct D: A, B {
  int d;
  virtual void bar() override {
    write(STDOUT_FILENO, "D::bar()\n", 9);
  }
};

int main() {
  B *bptr = new B;
  B *dptr = new D;
  D *ptr = new D;
}

逻辑还是很简单,继承图不画了,就是 D 同时继承于 A B ,于是 D 的实例中就分别嵌入了 AB 的实体、虚表则突然变得有点复杂,如下:

首先如果用指向 DA * 来调用 foo ,它的表现和单继承一模一样,所以这里不再考虑,让我们通过两个指向不同的 B * 调用 bar 来分析此时动态调度的流程。

如果用 bptr 调用 bar() ,则编译器生成的代码也和单继承逻辑相同,首先从栈上取指针,解引用一次得到虚表中第一个函数地址 _vptr ,再加上函数 B::bar 的地址在虚表中的偏移(此处为 0 )第二次解引用得到函数的地址,就可以直接 callqB::bar 了。

如果用 dptr 调用 bar() ,和之前的逻辑类似。首先我们可以认为当我们用 B * 指向 D 实际上指向的是嵌入到 D 中的 B ,所以当调用 dptr->bar() 的时候,会使用 DB_vptr ,这时候解引用得到的是 non-virtual thunk to D::bar 这部分只有两个指令,首先调整 this 指针为 D * ——上面说过 this 原来指向 D 中的 B ——这之后立刻 jmpqD::bar 函数体。

这和用 D *ptr 调用 bar 的区别在于:由于 D *ptr 指向的是 D 的首地址,使用的是 A_vptr ,而且编译器知道这个类型就是 D * ,所以可以直接通过解引用 _vptr 加上一个偏移(此处偏移为一个指针大小)得到 D::bar ,不需要调整 this 就可以直接 callq

菱形继承

和普通继承相同,非虚的菱形继承会将顶端的基类嵌入到两个中间的类中,再将两个中间的类嵌入到派生类中,于是继承的终点就会嵌入两个继承的顶点。

这里和上面的逻辑是完全相同的,不详细解释,就给出几个图示。

struct O {
  int o;
  virtual void foo() {
  }
};

struct A: O {
  virtual void bar() {
  }
  int a;
};

struct B: O {
  virtual void baz() {
  }
  int b;
};

struct D: A, B {
  int d;
};

虚表是这样的:

当然,由于一个 D 中存在两个 O ,所以不能直接用 O * 指向 D ,会报错。

菱形虚继承

为了避免菱形继承中出现的两个 O 的拷贝而导致无法直接用 O * 指向 D ,或者 D *ptr 无法直接 ptr->o 或者 ptr->foo() (虽然可以通过指明是哪个父类的 O ,如 ptr->A::foo() 或者 ptr->B::foo() 来调用,当然两者是互不影响的)。 C++ 使用虚继承来解决这个问题。

接下来是最难的部分,还是从源码开始——

#include <unistd.h>

struct O {
  int o;
  O() {
    write(STDOUT_FILENO, "O::O()\n", 7);
  }
  virtual void foo() {
    write(STDOUT_FILENO, "O::foo()\n", 9);
  }
};

struct A: virtual O {
  int a;
  A() {
    write(STDOUT_FILENO, "A::A()\n", 7);
  }
  virtual void bar() {
    write(STDOUT_FILENO, "A::bar()\n", 9);
  }
};

struct B: virtual O {
  int b;
  B() {
    write(STDOUT_FILENO, "B::B()\n", 7);
  }
  virtual void baz() {
    write(STDOUT_FILENO, "B::baz()\n", 9);
  }
};

struct D: A, B {
  D() {
    write(STDOUT_FILENO, "D::D()\n", 7);
  }
  int d;
};

再次分析 g++ -fdump-class-hierarchy 得到的结果,会发现结构中多了很多 VTT ,也就是 Virtual Table Table 的缩写(虚表表),这是用来给构造和析构使用的,这里先来看实例和虚表的结构:

到这里为止,都和上面多继承的没有差别,用父类指针调用的流程也是一样的。

从这里开始,我们来考虑这一类结构体如何构造或析构。

在没有虚继承的时候,在构造派生类的时候,先通过当前的 this 指针计算出基类嵌入到子类中的偏移,然后在偏移处调用基类的构造。遇到没有基类的时候,另外分配一个虚指针并指向相应的虚表地址。

在有虚继承的时候,首先自然是调用 O 的构造,结束后再调用下一个 A 的构造——不对, A 的构造函数本来也会调用 O 的构造函数,但是在 D 中的 A 中并没有 OA 怎么知道自己需不需要在自己体内构造一个 O

显然,这里的构造函数没这么简单。 g++ 是通过 VTT ,也就是 Virtual Table Table 来实现构造函数的动态调度的。在我们调用子类构造函数隐式调用基类构造函数的时候, g++ 会调用另一个隐式生成的构造函数,并隐式地传入一个参数,这个参数就是子类 VTT 的地址。 VTT 表中有一个指针指向一个 construction vtable for BaseClass-in-DerivedClass ,这个构造虚表中的第一项是虚基类在基类中的偏移,这样的话,基类对虚基类的构造就不会修改非法内存 。

首先看 AB 的 VTT ,长这样:

D 的 VTT 长这样:

我稍微写一下几个构造函数流程的伪代码,因为是直接从汇编翻译过来的,所以就不用去理会类型系统了:

O::O(this) {
  this->O_vptr = &O::foo;
  write(STDOUT_FILENO, "O::O()\n", 7);
}
A::A(this, __vtt_parm) {
  this->_vptr = *__vtt_parm;
  *(this + *(this->_vptr - 0x18)) = *(__vtt_parm + 0x08);
  write(STDOUT_FILENO, "A::A()\n", 7);
}
B::B(this, __vtt_parm) {
  this->_vptr = *__vtt_parm;
  *(this + *(this->_vptr - 0x18)) = *(__vtt_parm + 0x08);
  write(STDOUT_FILENO, "B::B()\n", 7);
}
D::D(this) {
    O::O(this + 0x20 /* offset of O in D */);
    A::A(this + 0x00 /* offset of A in D */, VTT_for_D + 0x08);
    B::B(this + 0x10 /* offset of B in D */, VTT_for_D + 0x18);
    this->O::_vptr = &O::foo;
    this->A::_vptr = &A::bar;
    this->B::_vptr = &B::baz;
    write(STDOUT_FILENO, "D::D()\n", 7);
}

A::A()B::B() 这两个函数,首先第一次解引用会将虚指针指向虚表中的第一个函数地址,其 – 0x18 即为 vbase offset ,也就是当前 this 指针和虚基类基址的偏移量,于是这里就将虚基类的 _vptr 设置为 *(__vtt_parm + 0x08) ,也就是 VTT 表中下一项指向的函数地址,也就是 O::foo 地址。

虽然有很多重复无用的操作,不过总算是成功建立起来了整个结构。 D::D() 中最后的几个赋值是没必要的,如果不去理会这些的话,其实这种代码非常容易拓展,只需要传入子类 VTT 中第一个指向“基类-in-子类”构造虚表的指针的地址就可以正常构造基类了。而且用这样的代码,即使构造父类也是可以直接传父类的 VTT 的。虽然这份代码中,编译器为父类另外生成了优化后的构造代码。

同理的析构函数也是用类似的方法逐个析构的,不再细讲。

最后的最后,虚表中除了奇怪的 offset vbase 和 offset to this 还多一个这里没有被用到的东西: typeinfo ,这其实是为了运行时类型转换用的, dynamic_cast 会检查虚表中的 typeinfo ,不再展开。

发表评论

电子邮件地址不会被公开。 必填项已用*标注