Introduce the VTable interleaving scheme to the CFI design documentation

[zhaomo]

Summary

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

[pcc]

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

clang/docs/ControlFlowIntegrityDesign.rst

277

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

286

On the high level -> At a high level

322

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.

331

funtion -> function

339

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.

[vlad.tsyrklevich]

clang/docs/ControlFlowIntegrityDesign.rst

283

simplified to a range check -> always a range check

[zhaomo]

Updated version of the patch

[zhaomo]

Fix mistakes and provide more information about the interleaving algorithm

[pcc]

LGTM except for a few spelling/grammar nits.

clang/docs/ControlFlowIntegrityDesign.rst

361

initialized

374

function

375

related

395

appends

396

lists are left

[pcc]

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

[zhaomo]

Fixed typos pointed out by pcc.

clang/docs/ControlFlowIntegrityDesign.rst

 
 Eliminating Bit Vector Checks for All-Ones Bit Vectors
 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 
 If the bit vector is all ones, the bit vector check is redundant; we simply
 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 <https://cseweb.ucsd.edu/~lerner/papers/ivtbl-ndss16.pdf>`_. 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, &A::rtti, B::offset-to-top, &B::rtti, D::offset-to-top, &D::rtti, C::offset-to-top, &C::rtti, &A::f1, &B::f1, &D::f1, &C::f1, &B::f2, &D::f2, &C::f3, &D::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 &B::f2 
+and its address point D::offset-to-top (the entry immediately after &B::rtti) is 7 entry-length, so is the distance between &D::f2 and C::offset-to-top (the entry immediately after &D::rtti).
+
 Forward-Edge CFI for Indirect Function Calls
 ============================================
 
 Under forward-edge CFI for indirect function calls, each unique function
 type has its own bit vector, and at each call site we need to check that the
 function pointer is a member of the function type's bit vector. This scheme
 works in a similar way to forward-edge CFI for virtual calls, the distinction
 being that we need to build bit vectors of function entry points rather than
 of virtual tables.
 
 Unlike when re-arranging global variables, we cannot re-arrange functions
 in a particular order and base our calculations on the layout of the
 functions' entry points, as we have no idea how large a particular function
 will end up being (the function sizes could even depend on how we arrange
 the functions). Instead, we build a jump table, which is a block of code
 consisting of one branch instruction for each of the functions in the bit
 set that branches to the target function, and redirect any taken function
 addresses to the corresponding jump table entry. In this way, the distance
 between function entry points is predictable and controllable. In the object
 file's symbol table, the symbols for the target functions also refer to the
 jump table entries, so that addresses taken outside the module will pass
 any verification done inside the module.
 
 In more concrete terms, suppose we have three functions ``f``, ``g``,
 ``h`` which are all of the same type, and a function foo that returns their
 addresses:
 
 .. code-block:: none
 
   f:
   mov 0, %eax
   ret
 
   g:
   mov 1, %eax
   ret
 
   h:
   mov 2, %eax
   ret
 
   foo:
   mov f, %eax
   mov g, %edx