docs/TypeMetadata.rst

   1 =============
   2 Type Metadata
   3 =============
   4
   5 Type metadata is a mechanism that allows IR modules to co-operatively build
   6 pointer sets corresponding to addresses within a given set of globals. LLVM's
   7 `control flow integrity`_ implementation uses this metadata to efficiently
   8 check (at each call site) that a given address corresponds to either a
   9 valid vtable or function pointer for a given class or function type, and its
  10 whole-program devirtualization pass uses the metadata to identify potential
  11 callees for a given virtual call.
  12
  13 To use the mechanism, a client creates metadata nodes with two elements:
  14
  15 1. a byte offset into the global (generally zero for functions)
  16 2. a metadata object representing an identifier for the type
  17
  18 These metadata nodes are associated with globals by using global object
  19 metadata attachments with the ``!type`` metadata kind.
  20
  21 Each type identifier must exclusively identify either global variables
  22 or functions.
  23
  24 .. admonition:: Limitation
  25
  26   The current implementation only supports attaching metadata to functions on
  27   the x86-32 and x86-64 architectures.
  28
  29 An intrinsic, :ref:`llvm.type.test <type.test>`, is used to test whether a
  30 given pointer is associated with a type identifier.
  31
  32 .. _control flow integrity: http://clang.llvm.org/docs/ControlFlowIntegrity.html
  33
  34 Representing Type Information using Type Metadata
  35 =================================================
  36
  37 This section describes how Clang represents C++ type information associated with
  38 virtual tables using type metadata.
  39
  40 Consider the following inheritance hierarchy:
  41
  42 .. code-block:: c++
  43
  44   struct A {
  45     virtual void f();
  46   };
  47
  48   struct B : A {
  49     virtual void f();
  50     virtual void g();
  51   };
  52
  53   struct C {
  54     virtual void h();
  55   };
  56
  57   struct D : A, C {
  58     virtual void f();
  59     virtual void h();
  60   };
  61
  62 The virtual table objects for A, B, C and D look like this (under the Itanium ABI):
  63
  64 .. csv-table:: Virtual Table Layout for A, B, C, D
  65   :header: Class, 0, 1, 2, 3, 4, 5, 6
  66
  67   A, A::offset-to-top, &A::rtti, &A::f
  68   B, B::offset-to-top, &B::rtti, &B::f, &B::g
  69   C, C::offset-to-top, &C::rtti, &C::h
  70   D, D::offset-to-top, &D::rtti, &D::f, &D::h, D::offset-to-top, &D::rtti, thunk for &D::h
  71
  72 When an object of type A is constructed, the address of ``&A::f`` in A's
  73 virtual table object is stored in the object's vtable pointer.  In ABI parlance
  74 this address is known as an `address point`_. Similarly, when an object of type
  75 B is constructed, the address of ``&B::f`` is stored in the vtable pointer. In
  76 this way, the vtable in B's virtual table object is compatible with A's vtable.
  77
  78 D is a little more complicated, due to the use of multiple inheritance. Its
  79 virtual table object contains two vtables, one compatible with A's vtable and
  80 the other compatible with C's vtable. Objects of type D contain two virtual
  81 pointers, one belonging to the A subobject and containing the address of
  82 the vtable compatible with A's vtable, and the other belonging to the C
  83 subobject and containing the address of the vtable compatible with C's vtable.
  84
  85 The full set of compatibility information for the above class hierarchy is
  86 shown below. The following table shows the name of a class, the offset of an
  87 address point within that class's vtable and the name of one of the classes
  88 with which that address point is compatible.
  89
  90 .. csv-table:: Type Offsets for A, B, C, D
  91   :header: VTable for, Offset, Compatible Class
  92
  93   A, 16, A
  94   B, 16, A
  95    ,   , B
  96   C, 16, C
  97   D, 16, A
  98    ,   , D
  99    , 48, C
 100
 101 The next step is to encode this compatibility information into the IR. The way
 102 this is done is to create type metadata named after each of the compatible
 103 classes, with which we associate each of the compatible address points in
 104 each vtable. For example, these type metadata entries encode the compatibility
 105 information for the above hierarchy:
 106
 107 ::
 108
 109   @_ZTV1A = constant [...], !type !0
 110   @_ZTV1B = constant [...], !type !0, !type !1
 111   @_ZTV1C = constant [...], !type !2
 112   @_ZTV1D = constant [...], !type !0, !type !3, !type !4
 113
 114   !0 = !{i64 16, !"_ZTS1A"}
 115   !1 = !{i64 16, !"_ZTS1B"}
 116   !2 = !{i64 16, !"_ZTS1C"}
 117   !3 = !{i64 16, !"_ZTS1D"}
 118   !4 = !{i64 48, !"_ZTS1C"}
 119
 120 With this type metadata, we can now use the ``llvm.type.test`` intrinsic to
 121 test whether a given pointer is compatible with a type identifier. Working
 122 backwards, if ``llvm.type.test`` returns true for a particular pointer,
 123 we can also statically determine the identities of the virtual functions
 124 that a particular virtual call may call. For example, if a program assumes
 125 a pointer to be a member of ``!"_ZST1A"``, we know that the address can
 126 be only be one of ``_ZTV1A+16``, ``_ZTV1B+16`` or ``_ZTV1D+16`` (i.e. the
 127 address points of the vtables of A, B and D respectively). If we then load
 128 an address from that pointer, we know that the address can only be one of
 129 ``&A::f``, ``&B::f`` or ``&D::f``.
 130
 131 .. _address point: https://itanium-cxx-abi.github.io/cxx-abi/abi.html#vtable-general
 132
 133 Testing Addresses For Type Membership
 134 =====================================
 135
 136 If a program tests an address using ``llvm.type.test``, this will cause
 137 a link-time optimization pass, ``LowerTypeTests``, to replace calls to this
 138 intrinsic with efficient code to perform type member tests. At a high level,
 139 the pass will lay out referenced globals in a consecutive memory region in
 140 the object file, construct bit vectors that map onto that memory region,
 141 and generate code at each of the ``llvm.type.test`` call sites to test
 142 pointers against those bit vectors. Because of the layout manipulation, the
 143 globals' definitions must be available at LTO time. For more information,
 144 see the `control flow integrity design document`_.
 145
 146 A type identifier that identifies functions is transformed into a jump table,
 147 which is a block of code consisting of one branch instruction for each
 148 of the functions associated with the type identifier that branches to the
 149 target function. The pass will redirect any taken function addresses to the
 150 corresponding jump table entry. In the object file's symbol table, the jump
 151 table entries take the identities of the original functions, so that addresses
 152 taken outside the module will pass any verification done inside the module.
 153
 154 Jump tables may call external functions, so their definitions need not
 155 be available at LTO time. Note that if an externally defined function is
 156 associated with a type identifier, there is no guarantee that its identity
 157 within the module will be the same as its identity outside of the module,
 158 as the former will be the jump table entry if a jump table is necessary.
 159
 160 The `GlobalLayoutBuilder`_ class is responsible for laying out the globals
 161 efficiently to minimize the sizes of the underlying bitsets.
 162
 163 .. _control flow integrity design document: http://clang.llvm.org/docs/ControlFlowIntegrityDesign.html
 164
 165 :Example:
 166
 167 ::
 168
 169     target datalayout = "e-p:32:32"
 170
 171     @a = internal global i32 0, !type !0
 172     @b = internal global i32 0, !type !0, !type !1
 173     @c = internal global i32 0, !type !1
 174     @d = internal global [2 x i32] [i32 0, i32 0], !type !2
 175
 176     define void @e() !type !3 {
 177       ret void
 178     }
 179
 180     define void @f() {
 181       ret void
 182     }
 183
 184     declare void @g() !type !3
 185
 186     !0 = !{i32 0, !"typeid1"}
 187     !1 = !{i32 0, !"typeid2"}
 188     !2 = !{i32 4, !"typeid2"}
 189     !3 = !{i32 0, !"typeid3"}
 190
 191     declare i1 @llvm.type.test(i8* %ptr, metadata %typeid) nounwind readnone
 192
 193     define i1 @foo(i32* %p) {
 194       %pi8 = bitcast i32* %p to i8*
 195       %x = call i1 @llvm.type.test(i8* %pi8, metadata !"typeid1")
 196       ret i1 %x
 197     }
 198
 199     define i1 @bar(i32* %p) {
 200       %pi8 = bitcast i32* %p to i8*
 201       %x = call i1 @llvm.type.test(i8* %pi8, metadata !"typeid2")
 202       ret i1 %x
 203     }
 204
 205     define i1 @baz(void ()* %p) {
 206       %pi8 = bitcast void ()* %p to i8*
 207       %x = call i1 @llvm.type.test(i8* %pi8, metadata !"typeid3")
 208       ret i1 %x
 209     }
 210
 211     define void @main() {
 212       %a1 = call i1 @foo(i32* @a) ; returns 1
 213       %b1 = call i1 @foo(i32* @b) ; returns 1
 214       %c1 = call i1 @foo(i32* @c) ; returns 0
 215       %a2 = call i1 @bar(i32* @a) ; returns 0
 216       %b2 = call i1 @bar(i32* @b) ; returns 1
 217       %c2 = call i1 @bar(i32* @c) ; returns 1
 218       %d02 = call i1 @bar(i32* getelementptr ([2 x i32]* @d, i32 0, i32 0)) ; returns 0
 219       %d12 = call i1 @bar(i32* getelementptr ([2 x i32]* @d, i32 0, i32 1)) ; returns 1
 220       %e = call i1 @baz(void ()* @e) ; returns 1
 221       %f = call i1 @baz(void ()* @f) ; returns 0
 222       %g = call i1 @baz(void ()* @g) ; returns 1
 223       ret void
 224     }
 225
 226 .. _GlobalLayoutBuilder: https://github.com/llvm/llvm-project/blob/master/llvm/include/llvm/Transforms/IPO/LowerTypeTests.h
 227
 228 ``!vcall_visibility`` Metadata
 229 ==============================
 230
 231 In order to allow removing unused function pointers from vtables, we need to
 232 know whether every virtual call which could use it is known to the compiler, or
 233 whether another translation unit could introduce more calls through the vtable.
 234 This is not the same as the linkage of the vtable, because call sites could be
 235 using a pointer of a more widely-visible base class. For example, consider this
 236 code:
 237
 238 .. code-block:: c++
 239
 240   __attribute__((visibility("default")))
 241   struct A {
 242     virtual void f();
 243   };
 244
 245   __attribute__((visibility("hidden")))
 246   struct B : A {
 247     virtual void f();
 248   };
 249
 250 With LTO, we know that all code which can see the declaration of ``B`` is
 251 visible to us. However, a pointer to a ``B`` could be cast to ``A*`` and passed
 252 to another linkage unit, which could then call ``f`` on it. This call would
 253 load from the vtable for ``B`` (using the object pointer), and then call
 254 ``B::f``. This means we can't remove the function pointer from ``B``'s vtable,
 255 or the implementation of ``B::f``. However, if we can see all code which knows
 256 about any dynamic base class (which would be the case if ``B`` only inherited
 257 from classes with hidden visibility), then this optimisation would be valid.
 258
 259 This concept is represented in IR by the ``!vcall_visibility`` metadata
 260 attached to vtable objects, with the following values:
 261
 262 .. list-table::
 263    :header-rows: 1
 264    :widths: 10 90
 265
 266    * - Value
 267      - Behavior
 268
 269    * - 0 (or omitted)
 270      - **Public**
 271            Virtual function calls using this vtable could be made from external
 272            code.
 273
 274    * - 1
 275      - **Linkage Unit**
 276            All virtual function calls which might use this vtable are in the
 277            current LTO unit, meaning they will be in the current module once
 278            LTO linking has been performed.
 279
 280    * - 2
 281      - **Translation Unit**
 282            All virtual function calls which might use this vtable are in the
 283            current module.
 284
 285 In addition, all function pointer loads from a vtable marked with the
 286 ``!vcall_visibility`` metadata (with a non-zero value) must be done using the
 287 :ref:`llvm.type.checked.load <type.checked.load>` intrinsic, so that virtual
 288 calls sites can be correlated with the vtables which they might load from.
 289 Other parts of the vtable (RTTI, offset-to-top, ...) can still be accessed with
 290 normal loads.