[PATCH] D50372: Introduce the VTable interleaving scheme to the CFI design documentation

[Peter Collingbourne via Phabricator via cfe-commits]

This revision was automatically updated to reflect the committed changes.
Closed by commit rC341989: Introduce the VTable interleaving scheme to the CFI 
design documentation (authored by pcc, committed by ).

Changed prior to commit:
  https://reviews.llvm.org/D50372?vs=164964=164967#toc

Repository:
  rC Clang

https://reviews.llvm.org/D50372

Files:
  docs/ControlFlowIntegrityDesign.rst

Index: docs/ControlFlowIntegrityDesign.rst
===
--- docs/ControlFlowIntegrityDesign.rst
+++ docs/ControlFlowIntegrityDesign.rst
@@ -274,6 +274,154 @@
 need to check that the address is in range and well aligned. This is more
 likely to occur if the virtual tables are padded.
 
+Forward-Edge CFI for Virtual Calls by Interleaving Virtual Tables
+-
+
+Dimitar et. al. proposed a novel approach that interleaves virtual tables in [1]_.  
+This approach is more efficient in terms of space because padding and bit vectors are no longer needed. 
+At the same time, it is also more efficient in terms of performance because in the interleaved layout 
+address points of the virtual tables are consecutive, thus the validity check of a virtual 
+vtable pointer is always a range check. 
+
+At a high level, the interleaving scheme consists of three steps: 1) split virtual table groups into 
+separate virtual tables, 2) order virtual tables by a pre-order traversal of the class hierarchy 
+and 3) interleave virtual tables.
+
+The interleaving scheme implemented in LLVM is inspired by [1]_ but has its own
+enhancements (more in `Interleave virtual tables`_).
+
+.. [1] `Protecting C++ Dynamic Dispatch Through VTable Interleaving `_. Dimitar Bounov, Rami Gökhan Kıcı, Sorin Lerner.
+
+Split virtual table groups into separate virtual tables
+~~~
+
+The Itanium C++ ABI glues multiple individual virtual tables for a class into a combined virtual table (virtual table group). 
+The interleaving scheme, however, can only work with individual virtual tables so it must split the combined virtual tables first.
+In comparison, the old scheme does not require the splitting but it is more efficient when the combined virtual tables have been split.
+The `GlobalSplit`_ pass is responsible for splitting combined virtual tables into individual ones. 
+
+.. _GlobalSplit: https://llvm.org/viewvc/llvm-project/llvm/trunk/lib/Transforms/IPO/GlobalSplit.cpp?view=markup
+
+Order virtual tables by a pre-order traversal of the class hierarchy 
+
+
+This step is common to both the old scheme described above and the interleaving scheme. 
+For the interleaving scheme, since the combined virtual tables have been split in the previous step, 
+this step ensures that for any class all the compatible virtual tables will appear consecutively. 
+For the old scheme, the same property may not hold since it may work on combined virtual tables. 
+
+For example, consider the following four C++ classes:
+
+.. code-block:: c++
+
+  struct A {
+virtual void f1();
+  };
+
+  struct B : A {
+virtual void f1();
+virtual void f2();
+  };
+
+  struct C : A {
+virtual void f1();
+virtual void f3();
+  };
+
+  struct D : B {
+virtual void f1();
+virtual void f2();
+  };
+
+This step will arrange the virtual tables for A, B, C, and D in the order of *vtable-of-A, vtable-of-B, vtable-of-D, vtable-of-C*.
+
+Interleave virtual tables
+~
+
+This step is where the interleaving scheme deviates from the old scheme. Instead of laying out 
+whole virtual tables in the previously computed order, the interleaving scheme lays out table 
+entries of the virtual tables strategically to ensure the following properties:  
+
+(1) offset-to-top and RTTI fields layout property
+
+The Itanium C++ ABI specifies that offset-to-top and RTTI fields appear at the offsets behind the 
+address point. Note that libraries like libcxxabi do assume this property. 
+
+(2) virtual function entry layout property
+
+For each virtual function the distance between an virtual table entry for this function and the corresponding 
+address point is always the same. This property ensures that dynamic dispatch still works with the interleaving layout.
+
+Note that the interleaving scheme in the CFI implementation guarantees both properties above whereas the original scheme proposed   
+in [1]_ only guarantees the second property. 
+
+To illustrate how the interleaving algorithm works, let us continue with the running example.
+The algorithm first separates all the virtual table entries into two work lists. To do so, 
+it starts by allocating two work lists, one initialized with all the offset-to-top entries of virtual tables in the order 
+computed in the last step, one initialized 

[PATCH] D50372: Introduce the VTable interleaving scheme to the CFI design documentation

[Zhaomo Yang via Phabricator via cfe-commits]

zhaomo updated this revision to Diff 164964.
zhaomo added a comment.

Fixed typos pointed out by pcc.


https://reviews.llvm.org/D50372

Files:
  clang/docs/ControlFlowIntegrityDesign.rst

Index: clang/docs/ControlFlowIntegrityDesign.rst
===
--- clang/docs/ControlFlowIntegrityDesign.rst
+++ clang/docs/ControlFlowIntegrityDesign.rst
@@ -274,6 +274,154 @@
 need to check that the address is in range and well aligned. This is more
 likely to occur if the virtual tables are padded.
 
+Forward-Edge CFI for Virtual Calls by Interleaving Virtual Tables
+-
+
+Dimitar et. al. proposed a novel approach that interleaves virtual tables in [1]_.  
+This approach is more efficient in terms of space because padding and bit vectors are no longer needed. 
+At the same time, it is also more efficient in terms of performance because in the interleaved layout 
+address points of the virtual tables are consecutive, thus the validity check of a virtual 
+vtable pointer is always a range check. 
+
+At a high level, the interleaving scheme consists of three steps: 1) split virtual table groups into 
+separate virtual tables, 2) order virtual tables by a pre-order traversal of the class hierarchy 
+and 3) interleave virtual tables.
+
+The interleaving scheme implemented in LLVM is inspired by [1]_ but has its own
+enhancements (more in `Interleave virtual tables`_).
+
+.. [1] `Protecting C++ Dynamic Dispatch Through VTable Interleaving `_. Dimitar Bounov, Rami Gökhan Kıcı, Sorin Lerner.
+
+Split virtual table groups into separate virtual tables
+~~~
+
+The Itanium C++ ABI glues multiple individual virtual tables for a class into a combined virtual table (virtual table group). 
+The interleaving scheme, however, can only work with individual virtual tables so it must split the combined virtual tables first.
+In comparison, the old scheme does not require the splitting but it is more efficient when the combined virtual tables have been split.
+The `GlobalSplit`_ pass is responsible for splitting combined virtual tables into individual ones. 
+
+.. _GlobalSplit: https://llvm.org/viewvc/llvm-project/llvm/trunk/lib/Transforms/IPO/GlobalSplit.cpp?view=markup
+
+Order virtual tables by a pre-order traversal of the class hierarchy 
+
+
+This step is common to both the old scheme described above and the interleaving scheme. 
+For the interleaving scheme, since the combined virtual tables have been split in the previous step, 
+this step ensures that for any class all the compatible virtual tables will appear consecutively. 
+For the old scheme, the same property may not hold since it may work on combined virtual tables. 
+
+For example, consider the following four C++ classes:
+
+.. code-block:: c++
+
+  struct A {
+virtual void f1();
+  };
+
+  struct B : A {
+virtual void f1();
+virtual void f2();
+  };
+
+  struct C : A {
+virtual void f1();
+virtual void f3();
+  };
+
+  struct D : B {
+virtual void f1();
+virtual void f2();
+  };
+
+This step will arrange the virtual tables for A, B, C, and D in the order of *vtable-of-A, vtable-of-B, vtable-of-D, vtable-of-C*.
+
+Interleave virtual tables
+~
+
+This step is where the interleaving scheme deviates from the old scheme. Instead of laying out 
+whole virtual tables in the previously computed order, the interleaving scheme lays out table 
+entries of the virtual tables strategically to ensure the following properties:  
+
+(1) offset-to-top and RTTI fields layout property
+
+The Itanium C++ ABI specifies that offset-to-top and RTTI fields appear at the offsets behind the 
+address point. Note that libraries like libcxxabi do assume this property. 
+
+(2) virtual function entry layout property
+
+For each virtual function the distance between an virtual table entry for this function and the corresponding 
+address point is always the same. This property ensures that dynamic dispatch still works with the interleaving layout.
+
+Note that the interleaving scheme in the CFI implementation guarantees both properties above whereas the original scheme proposed   
+in [1]_ only guarantees the second property. 
+
+To illustrate how the interleaving algorithm works, let us continue with the running example.
+The algorithm first separates all the virtual table entries into two work lists. To do so, 
+it starts by allocating two work lists, one initialized with all the offset-to-top entries of virtual tables in the order 
+computed in the last step, one initialized with all the RTTI entries in the same order. 
+
+.. csv-table:: Work list 1 Layout 
+  :header: 0, 1, 2, 3
+  
+  A::offset-to-top, B::offset-to-top, D::offset-to-top, C::offset-to-top
+
+

[PATCH] D50372: Introduce the VTable interleaving scheme to the CFI design documentation

[Peter Collingbourne via Phabricator via cfe-commits]

pcc added a comment.

Can you update this patch please? Then I will commit.


https://reviews.llvm.org/D50372



___
cfe-commits mailing list
cfe-commits@lists.llvm.org
http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D50372: Introduce the VTable interleaving scheme to the CFI design documentation

[Peter Collingbourne via Phabricator via cfe-commits]

pcc accepted this revision.
pcc added a comment.
This revision is now accepted and ready to land.

LGTM except for a few spelling/grammar nits.




Comment at: clang/docs/ControlFlowIntegrityDesign.rst:361
+it starts by allocating two work lists, one initialized with all the 
offset-to-top entries of virtual tables in the order 
+computed in the last step, one initlized with all the RTTI entries in the same 
order. 
+

initialized



Comment at: clang/docs/ControlFlowIntegrityDesign.rst:374
+
+Then for each virtual funciton the algorithm goes through all the virtual 
tables in the previously computed order
+to collect all the relted entries into a virtual function list. 

function



Comment at: clang/docs/ControlFlowIntegrityDesign.rst:375
+Then for each virtual funciton the algorithm goes through all the virtual 
tables in the previously computed order
+to collect all the relted entries into a virtual function list. 
+After this step, there are the following virtual function lists:

related



Comment at: clang/docs/ControlFlowIntegrityDesign.rst:395
+
+Next, the algorithm picks the longest remaining virtual function list and 
append the whole list to the shortest work list
+until no function list is left, and pads the shorter work list so that they 
are of the same length. 

appends



Comment at: clang/docs/ControlFlowIntegrityDesign.rst:396
+Next, the algorithm picks the longest remaining virtual function list and 
append the whole list to the shortest work list
+until no function list is left, and pads the shorter work list so that they 
are of the same length. 
+In the example, f1 list will be first added to work list 1, then f2 list will 
be added 

lists are left


https://reviews.llvm.org/D50372



___
cfe-commits mailing list
cfe-commits@lists.llvm.org
http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D50372: Introduce the VTable interleaving scheme to the CFI design documentation

[Zhaomo Yang via Phabricator via cfe-commits]

zhaomo updated this revision to Diff 159636.
zhaomo added a comment.

Fix mistakes and provide more information about the interleaving algorithm


https://reviews.llvm.org/D50372

Files:
  clang/docs/ControlFlowIntegrityDesign.rst

Index: clang/docs/ControlFlowIntegrityDesign.rst
===
--- clang/docs/ControlFlowIntegrityDesign.rst
+++ clang/docs/ControlFlowIntegrityDesign.rst
@@ -274,6 +274,154 @@
 need to check that the address is in range and well aligned. This is more
 likely to occur if the virtual tables are padded.
 
+Forward-Edge CFI for Virtual Calls by Interleaving Virtual Tables
+-
+
+Dimitar et. al. proposed a novel approach that interleaves virtual tables in [1]_.  
+This approach is more efficient in terms of space because padding and bit vectors are no longer needed. 
+At the same time, it is also more efficient in terms of performance because in the interleaved layout 
+address points of the virtual tables are consecutive, thus the validity check of a virtual 
+vtable pointer is always a range check. 
+
+At a high level, the interleaving scheme consists of three steps: 1) split virtual table groups into 
+separate virtual tables, 2) order virtual tables by a pre-order traversal of the class hierarchy 
+and 3) interleave virtual tables.
+
+The interleaving scheme implemented in LLVM is inspired by [1]_ but has its own
+enhancements (more in `Interleave virtual tables`_).
+
+.. [1] `Protecting C++ Dynamic Dispatch Through VTable Interleaving `_. Dimitar Bounov, Rami Gökhan Kıcı, Sorin Lerner.
+
+Split virtual table groups into separate virtual tables
+~~~
+
+The Itanium C++ ABI glues multiple individual virtual tables for a class into a combined virtual table (virtual table group). 
+The interleaving scheme, however, can only work with individual virtual tables so it must split the combined virtual tables first.
+In comparison, the old scheme does not require the splitting but it is more efficient when the combined virtual tables have been split.
+The `GlobalSplit`_ pass is responsible for splitting combined virtual tables into individual ones. 
+
+.. _GlobalSplit: https://llvm.org/viewvc/llvm-project/llvm/trunk/lib/Transforms/IPO/GlobalSplit.cpp?view=markup
+
+Order virtual tables by a pre-order traversal of the class hierarchy 
+
+
+This step is common to both the old scheme described above and the interleaving scheme. 
+For the interleaving scheme, since the combined virtual tables have been split in the previous step, 
+this step ensures that for any class all the compatible virtual tables will appear consecutively. 
+For the old scheme, the same property may not hold since it may work on combined virtual tables. 
+
+For example, consider the following four C++ classes:
+
+.. code-block:: c++
+
+  struct A {
+virtual void f1();
+  };
+
+  struct B : A {
+virtual void f1();
+virtual void f2();
+  };
+
+  struct C : A {
+virtual void f1();
+virtual void f3();
+  };
+
+  struct D : B {
+virtual void f1();
+virtual void f2();
+  };
+
+This step will arrange the virtual tables for A, B, C, and D in the order of *vtable-of-A, vtable-of-B, vtable-of-D, vtable-of-C*.
+
+Interleave virtual tables
+~
+
+This step is where the interleaving scheme deviates from the old scheme. Instead of laying out 
+whole virtual tables in the previously computed order, the interleaving scheme lays out table 
+entries of the virtual tables strategically to ensure the following properties:  
+
+(1) offset-to-top and RTTI fields layout property
+
+The Itanium C++ ABI specifies that offset-to-top and RTTI fields appear at the offsets behind the 
+address point. Note that libraries like libcxxabi do assume this property. 
+
+(2) virtual function entry layout property
+
+For each virtual function the distance between an virtual table entry for this function and the corresponding 
+address point is always the same. Note that dynamic dispatch relies on this property.
+
+Note that the interleaving scheme in the CFI implementation guarantees both properties above whereas the original scheme proposed   
+in [1]_ only guarantees the second property. 
+
+To illustrate how the interleaving algorithm works, let us continue with the running example.
+The algorithm first separates all the virtual table entries into two work lists. To do so, 
+it starts by allocating two work lists, one initialized with all the offset-to-top entries of virtual tables in the order 
+computed in the last step, one initlized with all the RTTI entries in the same order. 
+
+.. csv-table:: Work list 1 Layout 
+  :header: 0, 1, 2, 3
+  
+  A::offset-to-top, B::offset-to-top, D::offset-to-top, 

[PATCH] D50372: Introduce the VTable interleaving scheme to the CFI design documentation

[Zhaomo Yang via Phabricator via cfe-commits]

zhaomo updated this revision to Diff 159606.
zhaomo added a comment.

Updated version of the patch


https://reviews.llvm.org/D50372

Files:
  clang/docs/ControlFlowIntegrityDesign.rst


Index: clang/docs/ControlFlowIntegrityDesign.rst
===
--- clang/docs/ControlFlowIntegrityDesign.rst
+++ clang/docs/ControlFlowIntegrityDesign.rst
@@ -274,6 +274,90 @@
 need to check that the address is in range and well aligned. This is more
 likely to occur if the virtual tables are padded.
 
+Forward-Edge CFI for Virtual Calls by Interleaving Virtual Tables
+-
+
+Dimitar et. al. first proposed a novel approach that interleaves virtual 
tables in [1]_. 
+This approach is more efficient in terms of space because padding and bit 
vectors are no longer needed. 
+At the same time, it is also more efficient in terms of performance because in 
the interleaved layout 
+address points of the virtual tables are consecutive, thus the validity check 
of a virtual 
+vtable pointer is simplified  to a range check. 
+
+At a high level, the interleaving scheme consists of three steps: 1) split 
virtual table groups into 
+separate virtual tables, 2) order virtual tables by a pre-order traversal of 
the class hierarchy 
+and 3) interleave virtual tables.
+
+.. [1] `Protecting C++ Dynamic Dispatch Through VTable Interleaving 
`_. Dimitar Bounov, 
Rami Gökhan Kıcı, Sorin Lerner.
+
+Split virtual table groups into separate virtual tables
+~~~
+
+The Itanium C++ ABI glues multiple individual virtual tables for a class into 
a combined virtual table (virtual table group). 
+The interleaving scheme, however, can only work with individual virtual tables 
so it must split the combined virtual tables first.
+In comparison, the old scheme does not require the splitting but it is more 
efficient when the combined virtual tables have been split.
+The `GlobalSplit`_ pass is responsible for splitting combined virtual tables 
into individual ones. 
+
+.. _GlobalSplit: 
https://llvm.org/viewvc/llvm-project/llvm/trunk/lib/Transforms/IPO/GlobalSplit.cpp?view=markup
+
+Order virtual tables by a pre-order traversal of the class hierarchy 
+
+
+This step is common to both the old scheme described above and the 
interleaving scheme. 
+For the interleaving scheme, since the combined virtual tables have been split 
in the previous step, 
+this step ensures that for any class all the compatible virtual tables will 
appear consecutively. 
+For the old scheme, the same property may not hold since it may work on 
combined virtual tables. 
+
+For example, consider the following four C++ classes:
+
+.. code-block:: c++
+
+  struct A {
+virtual void f1();
+  };
+
+  struct B : A {
+virtual void f1();
+virtual void f2();
+  };
+
+  struct C : A {
+virtual void f1();
+virtual void f3();
+  };
+
+  struct D : B {
+virtual void f1();
+virtual void f2();
+virtual void f4();
+  };
+
+This step will arrange the virtual tables for A, B, C, and D in the order of 
*vtable-of-A, vtable-of-B, vtable-of-D, vtable-of-C*.
+
+Interleave virtual tables
+~
+
+This step is where the interleaving scheme deviates from the old scheme. 
Instead of laying out 
+whole virtual tables in the previously computed order, the interleaving scheme 
lays out table 
+entries one by one from the virtual tables in that order. Note that the 
Itanium C++ ABI specifies 
+that offset-to-top and RTTI fields appear at the offsets behind the address 
point, and libraries like 
+libcxxabi do assume this. To ensure the interleaved layout is compatible with 
the Itanium C++ ABI, 
+the interleaving scheme always lays out these two fields consecutively, and 
the address of the entry after the RTTI field 
+is considered the new address point for the virtual table in the interleave 
layout. Dynamic dispatch still 
+works under this scheme because the interleaved layout has the property that 
for 
+each virtual function the distance between an virtual table entry for this 
function and the corresponding 
+address point is always the same. 
+
+To follow the example used in the previous step, the interleaved layout will 
look like this:
+
+.. csv-table:: Interleaved Virtual Table Layout for A, B, C, D
+  :header: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15
+  
+  A::offset-to-top, ::rtti, B::offset-to-top, ::rtti, D::offset-to-top, 
::rtti, C::offset-to-top, ::rtti, ::f1, ::f1, ::f1, ::f1, ::f2, 
::f2, ::f3, ::f4
+
+Let us take f2 as an example to see the aforementioned property. In the 
interleaved layout, 
+there are two entries for f2: B::f2 and D::f2. The distance between ::f2 
+and its address point D::offset-to-top (the entry immediately after ::rtti) 

[PATCH] D50372: Introduce the VTable interleaving scheme to the CFI design documentation

[Vlad Tsyrklevich via Phabricator via cfe-commits]

vlad.tsyrklevich added inline comments.



Comment at: clang/docs/ControlFlowIntegrityDesign.rst:283
+At the same time, it is also more efficient in terms of performance because in 
the interleaved virtual 
+table address points are consecutive, thus the validity check of a virtual 
vtable pointer is simplified 
+to a range check. 

simplified to a range check -> always a range check


Repository:
  rC Clang

https://reviews.llvm.org/D50372



___
cfe-commits mailing list
cfe-commits@lists.llvm.org
http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D50372: Introduce the VTable interleaving scheme to the CFI design documentation

[Peter Collingbourne via Phabricator via cfe-commits]

pcc added a comment.

Please upload patches with context. `arc diff` will do this for you.




Comment at: clang/docs/ControlFlowIntegrityDesign.rst:277
 
+Forward-Edge CFI for Virtual Calls by Interleaving Virtual Tables
+=

I would add this as a subsection of "Forward-Edge CFI for Virtual Calls".



Comment at: clang/docs/ControlFlowIntegrityDesign.rst:286
+
+On the high level, the interleaving scheme consists of two steps: 1) order 
virtual tables by a pre-order 
+traversal of the class hierarchy and 2) interleave the virtual tables entry by 
entry.

On the high level -> At a high level



Comment at: clang/docs/ControlFlowIntegrityDesign.rst:322
+This step will arrange the virtual tables for A, B, C, and D in the order of 
*vtable-of-A, vtable-of-B, vtable-of-D, vtable-of-C*.
+In this order, for any class all the compatible virtual tables will appear 
consecutively.
+

I would move this sentence to the start of the subsection because it isn't 
specific to your example and clarify that although GlobalLayoutBuilder tries to 
place compatible vtables consecutively (but doesn't always succeed because the 
Itanium ABI glues vtables together), this algorithm requires them to appear 
consecutively.



Comment at: clang/docs/ControlFlowIntegrityDesign.rst:331
+works under this scheme because the interleaved virtual table has the property 
that for 
+each virtual funtion the distance between an entry of this function and the 
corresponding 
+address point is always the same. 

funtion -> function



Comment at: clang/docs/ControlFlowIntegrityDesign.rst:339
+  
+  A::offset-to-top, B::offset-to-top, D::offset-to-top, C::offset-to-top, 
::rtti, ::rtti, ::rtti, ::rtti, ::f1, ::f1, ::f1, ::f1, ::f2, 
::f2, ::f3, ::f4
+

This layout isn't necessarily going to work with traditional RTTI because the 
`__dynamic_cast` function is allowed to assume that the rtti and offset-to-top 
fields appear at the offsets behind the address point that the ABI says that 
they will appear at. Indeed, the libcxxabi implementation makes that assumption:

https://github.com/llvm-mirror/libcxxabi/blob/master/src/private_typeinfo.cpp#L627

It's probably more something to keep in mind for the implementation, but I 
think we at least need to mention the RTTI incompatibility here.


Repository:
  rC Clang

https://reviews.llvm.org/D50372



___
cfe-commits mailing list
cfe-commits@lists.llvm.org
http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D50372: Introduce the VTable interleaving scheme to the CFI design documentation

[Zhaomo Yang via Phabricator via cfe-commits]

zhaomo created this revision.
zhaomo added reviewers: pcc, vlad.tsyrklevich.
Herald added a subscriber: cfe-commits.

Dimitar et. al. in [1] proposed a novel VTable layout scheme that enables 
efficient implementation of virtual call CFI.

This patch adds an introduction of this scheme to the CFI design documentation.

[1] Protecting C++ Dynamic Dispatch Through VTable Interleaving. Dimitar 
Bounov, Rami Gökhan Kıcı, Sorin Lerner. 
https://cseweb.ucsd.edu/~lerner/papers/ivtbl-ndss16.pdf


Repository:
  rC Clang

https://reviews.llvm.org/D50372

Files:
  clang/docs/ControlFlowIntegrityDesign.rst


Index: clang/docs/ControlFlowIntegrityDesign.rst
===
--- clang/docs/ControlFlowIntegrityDesign.rst
+++ clang/docs/ControlFlowIntegrityDesign.rst
@@ -274,6 +274,74 @@
 need to check that the address is in range and well aligned. This is more
 likely to occur if the virtual tables are padded.
 
+Forward-Edge CFI for Virtual Calls by Interleaving Virtual Tables
+=
+
+Alternatively, Dimitar et. al. in [1]_ proposed a novel approach that 
interleaves virtual tables. 
+This approach is more efficient in terms of space because padding and bit 
vectors are no longer needed. 
+At the same time, it is also more efficient in terms of performance because in 
the interleaved virtual 
+table address points are consecutive, thus the validity check of a virtual 
vtable pointer is simplified 
+to a range check. 
+
+On the high level, the interleaving scheme consists of two steps: 1) order 
virtual tables by a pre-order 
+traversal of the class hierarchy and 2) interleave the virtual tables entry by 
entry.
+
+.. [1] `Protecting C++ Dynamic Dispatch Through VTable Interleaving 
`_. Dimitar Bounov, 
Rami Gökhan Kıcı, Sorin Lerner.
+
+Order virtual tables by a pre-order traversal of the class hierarchy 
+
+
+This step is common to both the old scheme described above and the 
interleaving scheme. For each class 
+this step ensures that classes in sub-hierarchies of this class are laid out 
as close as possible.
+
+For example, consider the following four C++ classes:
+
+.. code-block:: c++
+
+  struct A {
+virtual void f1();
+  };
+
+  struct B : A {
+virtual void f1();
+virtual void f2();
+  };
+
+  struct C : A {
+virtual void f1();
+virtual void f3();
+  };
+
+  struct D : B {
+virtual void f1();
+virtual void f2();
+virtual void f4();
+  };
+
+This step will arrange the virtual tables for A, B, C, and D in the order of 
*vtable-of-A, vtable-of-B, vtable-of-D, vtable-of-C*.
+In this order, for any class all the compatible virtual tables will appear 
consecutively.
+
+Interleave the virtual tables entry by entry
+
+
+This step is where the interleaving scheme deviates from the old scheme. 
Instead of laying out 
+whole virtual tables in the previously computed order, the interleaving scheme 
lays out table 
+entries one by one from the virtual tables in that order. Dynamic dispatch 
still 
+works under this scheme because the interleaved virtual table has the property 
that for 
+each virtual funtion the distance between an entry of this function and the 
corresponding 
+address point is always the same. 
+
+To follow the example used in the previous step, the interleaved virtual table 
will look like this:
+
+.. csv-table:: Interleaved Virtual Table Layout for A, B, C, D
+  :header: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15
+  
+  A::offset-to-top, B::offset-to-top, D::offset-to-top, C::offset-to-top, 
::rtti, ::rtti, ::rtti, ::rtti, ::f1, ::f1, ::f1, ::f1, ::f2, 
::f2, ::f3, ::f4
+
+Let us take f2 as an example to see the aforementioned property. In the 
interleaved virtual table, 
+there are two entries for f2: B::f2 and D::f2. The distance between ::f2 
+and its address point ::f1 is 3 entry-length, so is the distance between 
::f2 and ::f1.
+
 Forward-Edge CFI for Indirect Function Calls
 
 


Index: clang/docs/ControlFlowIntegrityDesign.rst
===
--- clang/docs/ControlFlowIntegrityDesign.rst
+++ clang/docs/ControlFlowIntegrityDesign.rst
@@ -274,6 +274,74 @@
 need to check that the address is in range and well aligned. This is more
 likely to occur if the virtual tables are padded.
 
+Forward-Edge CFI for Virtual Calls by Interleaving Virtual Tables
+=
+
+Alternatively, Dimitar et. al. in [1]_ proposed a novel approach that interleaves virtual tables. 
+This approach is more efficient in terms of space because padding and bit vectors are no longer needed. 
+At the same time, it is also more efficient in terms of performance