1=============
2Type Metadata
3=============
4
5Type metadata is a mechanism that allows IR modules to co-operatively build
6pointer sets corresponding to addresses within a given set of globals. LLVM's
7`control flow integrity`_ implementation uses this metadata to efficiently
8check (at each call site) that a given address corresponds to either a
9valid vtable or function pointer for a given class or function type, and its
10whole-program devirtualization pass uses the metadata to identify potential
11callees for a given virtual call.
12
13To use the mechanism, a client creates metadata nodes with two elements:
14
151. a byte offset into the global (generally zero for functions)
162. a metadata object representing an identifier for the type
17
18These metadata nodes are associated with globals by using global object
19metadata attachments with the ``!type`` metadata kind.
20
21Each type identifier must exclusively identify either global variables
22or 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
29An intrinsic, :ref:`llvm.type.test <type.test>`, is used to test whether a
30given pointer is associated with a type identifier.
31
32.. _control flow integrity: http://clang.llvm.org/docs/ControlFlowIntegrity.html
33
34Representing Type Information using Type Metadata
35=================================================
36
37This section describes how Clang represents C++ type information associated with
38virtual tables using type metadata.
39
40Consider 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
62The 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
72When an object of type A is constructed, the address of ``&A::f`` in A's
73virtual table object is stored in the object's vtable pointer.  In ABI parlance
74this address is known as an `address point`_. Similarly, when an object of type
75B is constructed, the address of ``&B::f`` is stored in the vtable pointer. In
76this way, the vtable in B's virtual table object is compatible with A's vtable.
77
78D is a little more complicated, due to the use of multiple inheritance. Its
79virtual table object contains two vtables, one compatible with A's vtable and
80the other compatible with C's vtable. Objects of type D contain two virtual
81pointers, one belonging to the A subobject and containing the address of
82the vtable compatible with A's vtable, and the other belonging to the C
83subobject and containing the address of the vtable compatible with C's vtable.
84
85The full set of compatibility information for the above class hierarchy is
86shown below. The following table shows the name of a class, the offset of an
87address point within that class's vtable and the name of one of the classes
88with 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
101The next step is to encode this compatibility information into the IR. The way
102this is done is to create type metadata named after each of the compatible
103classes, with which we associate each of the compatible address points in
104each vtable. For example, these type metadata entries encode the compatibility
105information 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
120With this type metadata, we can now use the ``llvm.type.test`` intrinsic to
121test whether a given pointer is compatible with a type identifier. Working
122backwards, if ``llvm.type.test`` returns true for a particular pointer,
123we can also statically determine the identities of the virtual functions
124that a particular virtual call may call. For example, if a program assumes
125a pointer to be a member of ``!"_ZST1A"``, we know that the address can
126be only be one of ``_ZTV1A+16``, ``_ZTV1B+16`` or ``_ZTV1D+16`` (i.e. the
127address points of the vtables of A, B and D respectively). If we then load
128an 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://mentorembedded.github.io/cxx-abi/abi.html#vtable-general
132
133Testing Addresses For Type Membership
134=====================================
135
136If a program tests an address using ``llvm.type.test``, this will cause
137a link-time optimization pass, ``LowerTypeTests``, to replace calls to this
138intrinsic with efficient code to perform type member tests. At a high level,
139the pass will lay out referenced globals in a consecutive memory region in
140the object file, construct bit vectors that map onto that memory region,
141and generate code at each of the ``llvm.type.test`` call sites to test
142pointers against those bit vectors. Because of the layout manipulation, the
143globals' definitions must be available at LTO time. For more information,
144see the `control flow integrity design document`_.
145
146A type identifier that identifies functions is transformed into a jump table,
147which is a block of code consisting of one branch instruction for each
148of the functions associated with the type identifier that branches to the
149target function. The pass will redirect any taken function addresses to the
150corresponding jump table entry. In the object file's symbol table, the jump
151table entries take the identities of the original functions, so that addresses
152taken outside the module will pass any verification done inside the module.
153
154Jump tables may call external functions, so their definitions need not
155be available at LTO time. Note that if an externally defined function is
156associated with a type identifier, there is no guarantee that its identity
157within the module will be the same as its identity outside of the module,
158as the former will be the jump table entry if a jump table is necessary.
159
160The `GlobalLayoutBuilder`_ class is responsible for laying out the globals
161efficiently 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: http://llvm.org/klaus/llvm/blob/master/include/llvm/Transforms/IPO/LowerTypeTests.h
227