死のダイアモンド継承のメモリレイアウト

なんか C++ Advent Calendar 2018 の 12/25 が空いているので、登録してみた。
先日まで埋まっていたような気がしたんだけど、気のせいかなぁ。

それはともかく。

C++ は多重継承ができる珍しい言語で。
ダイアモンド継承とそうでない継承が両方できる。便利。

ダイアモンド継承、たまに必要になるよね。

で。
メモリレイアウトがどうなっているのか、clang++ と g++-8 ( いずれも x86-64, macOS )の場合を調べてみた。

まずはソースコード。

#ソースコード

```c++:c++
#include <iostream>

template <typename p0t, typename p1t>
std::ptrdiff_t offset_of(p0t const *p0, p1t const *p1)
{
  return reinterpret_cast<char const *>(p0) - reinterpret_cast<char const *>(p1);
}

struct BaseA
{
  int a_head;
};

struct InterB : public virtual BaseA
{
  int b_head;
};

struct InterC : public virtual BaseA
{
  int c_head;
};

struct DerivedD : public InterB, public InterC
{
  int d_head;
};

int main()
{
  InterB b;
  DerivedD d;
  std::cout
      << "InterB:\n"
      << "  a_head: " << offset_of(&b.a_head, &b) << "\n"
      << "  b_head: " << offset_of(&b.b_head, &b) << "\n"
      << "  (BaseA*)&b: " << offset_of(static_cast<BaseA*>(&b), &b) << "\n";

  std::cout
      << "DerivedD:\n"
      << "  a_head: " << offset_of(&d.a_head, &d) << "\n"
      << "  b_head: " << offset_of(&d.b_head, &d) << "\n"
      << "  c_head: " << offset_of(&d.c_head, &d) << "\n"
      << "  d_head: " << offset_of(&d.d_head, &d) << "\n"
      << "  (BaseA*) &d: " << offset_of(static_cast<BaseA*>(&d), &d) << "\n"
      << "  (InterB*)&d: " << offset_of(static_cast<InterB*>(&d), &d) << "\n"
      << "  (InterC*)&d: " << offset_of(static_cast<InterC*>(&d), &d) << "\n";
  return 0;
}
```

# 出力

そして出力。

```text
InterB:
  a_head: 12
  b_head: 8
  (BaseA*)&b: 12
DerivedD:
  a_head: 32
  b_head: 8
  c_head: 24
  d_head: 28
  (BaseA*) &d: 32
  (InterB*)&d: 0
  (InterC*)&d: 16
```

g++-8 と clang は出力同じだった。

# メモリレイアウト

出力をもとに、表を作ると。

## InterB の メモリレイアウト

|オフセット|サイズ|内容|誰のもの？|
|:--|:--|:--|:--|
|0|8|仮想基底を管理するための情報|B|
|8|4|int b_head|B|
|12|4|BaseA(int a_head)|A,B|

## DerivedD の メモリレイアウト

|オフセット|サイズ|内容|誰のもの？|
|:--|:--|:--|:--|
|0|8|InterB の 仮想基底を管理するための情報|B,D|
|8|4|int b_head|B,D|
|12|4|パディング|D|
|16|8|InterC の 仮想基底を管理するための情報|C,D|
|24|4|int c_head|C,D|
|28|4|int d_head|D|
|32|4|BaseA(int a_head)|A,B,C,D|

となっているようだ。

仮想基底は後ろに追いやられるらしい。

見どころは「InterB」の領域。 
InterB 単体の場合、a_head は InterBの先頭から12バイト目にあるが、DerivedD の中にある InterB の場合、a_head は InterB の先頭から 32バイト目にある。
このレイアウトのズレを吸収するために InterB の先頭に 8バイトの情報が必要になる。

しかし。
仮想基底を管理するための情報に何が入っているのかは、よくわからなかった。

# タイトルについて
「死のダイアモンド継承」は、[Multiple inheritance - Wikipedia]( https://en.wikipedia.org/wiki/Multiple_inheritance ) にある

> "deadly diamond of death"

を訳したもの。ではなく、どこかで聞いた「**Diamond inheritance of Death**」を訳したもの。しかしググっても見つからない。空耳かなぁ。

# 最後に

メリークリスマス

# virtual table の中身を探索 -- 以下追記 --

[コメント]( https://qiita.com/Nabetani/items/338887f41a7301c59dca#comment-56f861d3e3517ba55f24 )を受けて、virtual table の中身を探索することにした。

## ソースコード

まずはソースコード：

```c++:c++
#include <iostream>
#include <typeinfo>

template <typename p0t, typename p1t>
std::ptrdiff_t offset_of(p0t const *p0, p1t const *p1)
{
  return reinterpret_cast<char const *>(p0) - reinterpret_cast<char const *>(p1);
}

struct BaseA
{
  ptrdiff_t a_head[1];
};

struct BaseB
{
  ptrdiff_t b_head[2];
};

struct BaseC
{
  ptrdiff_t c_head[4];
};

struct DerivedX
    : public virtual BaseA
{
  ptrdiff_t x_head[8];
};

struct DerivedY
    : public virtual BaseA,
      public virtual BaseB
{
  ptrdiff_t y_head[16];
  virtual ~DerivedY(){}
};

struct DerivedZ
    : public virtual BaseA,
      public virtual BaseB,
      public virtual BaseC
{
  ptrdiff_t z_head[32];
  virtual ~DerivedZ(){}
};

struct DerivedW
    : public DerivedX,
      public DerivedY,
      public DerivedZ
{
  ptrdiff_t w_head[64];
};

void testY(DerivedY &y, char const * title)
{
  ptrdiff_t *vt = *reinterpret_cast<ptrdiff_t **>(&y);
  std::cout
      << title << ":\n"
      << "  (BaseA*)&y: " << offset_of(static_cast<BaseA *>(&y), &y) << "\n"
      << "  (BaseB*)&y: " << offset_of(static_cast<BaseB *>(&y), &y) << "\n";
  for (int i = -4; i <= -1; ++i)
  {
    std::cout << "  vt[" << i << "]: " << vt[i] << "\n";
  }
  if ( DerivedW * w = dynamic_cast<DerivedW*>(&y) ){
    std::cout << "  (DerivedW*)&y: " << offset_of(w, &y) << "\n";
  }
  std::type_info *t = reinterpret_cast<std::type_info *>(vt[-1]);
  std::cout << "  (typeinfo*)vt[-1]: " << t->name() << "\n";
}

void testZ(DerivedZ &z, char const * title)
{
  ptrdiff_t *vt = *reinterpret_cast<ptrdiff_t **>(&z);
  std::cout
      << title << ":\n"
      << "  (BaseA*)&z: " << offset_of(static_cast<BaseA *>(&z), &z) << "\n"
      << "  (BaseB*)&z: " << offset_of(static_cast<BaseB *>(&z), &z) << "\n"
      << "  (BaseC*)&z: " << offset_of(static_cast<BaseC *>(&z), &z) << "\n";
  for (int i = -5; i <= -1; ++i)
  {
    std::cout << "  vt[" << i << "]: " << vt[i] << "\n";
  }
  if ( DerivedW * w = dynamic_cast<DerivedW*>(&z) ){
    std::cout << "  (DerivedW*)&z: " << offset_of(w, &z) << "\n";
  }
  std::type_info *t = reinterpret_cast<std::type_info *>(vt[-1]);
  std::cout << "  (typeinfo*)vt[-1]: " << t->name() << "\n";
}

int main()
{
  DerivedY y;
  DerivedZ z;
  DerivedW w;
  testY(y, "DerivedY");
  testY(w, "DerivedW as Y");
  testZ(z, "DerivedZ");
  testZ(w, "DerivedW as Z");
  return 0;
}
```

## 出力

上記のソースをコンパイル・実行すると、以下を得る：

```text

DerivedY:
  (BaseA*)&y: 136
  (BaseB*)&y: 144
  vt[-4]: 144
  vt[-3]: 136
  vt[-2]: 0
  vt[-1]: 4323349408
  (typeinfo*)vt[-1]: 8DerivedY
DerivedW as Y:
  (BaseA*)&y: 912
  (BaseB*)&y: 920
  vt[-4]: 920
  vt[-3]: 912
  vt[-2]: -72
  vt[-1]: 4323349264
  (DerivedW*)&y: -72
  (typeinfo*)vt[-1]: 8DerivedW
DerivedZ:
  (BaseA*)&z: 264
  (BaseB*)&z: 272
  (BaseC*)&z: 288
  vt[-5]: 288
  vt[-4]: 272
  vt[-3]: 264
  vt[-2]: 0
  vt[-1]: 4323349336
  (typeinfo*)vt[-1]: 8DerivedZ
DerivedW as Z:
  (BaseA*)&z: 776
  (BaseB*)&z: 784
  (BaseC*)&z: 800
  vt[-5]: 800
  vt[-4]: 784
  vt[-3]: 776
  vt[-2]: -208
  vt[-1]: 4323349264
  (DerivedW*)&z: -208
  (typeinfo*)vt[-1]: 8DerivedW
```

## virtual table の中身

virtual table の中身は以下の内容だと推測できそうだ：

|オフセット|内容|
|:--|:--|
| ︙ | ︙ |
|-5 ×`sizeof(void*)`|3番目の仮想基底クラスのオフセット|
|-4 ×`sizeof(void*)`|2番目の仮想基底クラスのオフセット|
|-3 ×`sizeof(void*)`|1番目の仮想基底クラスのオフセット|
|-2 ×`sizeof(void*)`|オブジェクトの先頭へのオフセット(註1)|
|-1 ×`sizeof(void*)`|`std::type_info` へのポインタ|

註1) 上記の例だと、`testY(w, "DerivedW as Y");` という呼び出しは、`w` の `DerivedY` 部の先頭のポインタを受け取る。とはいえ、オブジェクトとしては `DerivedW` 型。`DerivedY` 部よりも前に 72バイトある。その「前に72バイト」を「-72」として埋め込んである。


上記の結果は、clang++ / g++-8 で、 `-m32` / `-m64` のいずれでも成立する感じ。
OS は macOS しか確認していない。