|
120
|
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://mentorembedded.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: http://llvm.org/klaus/llvm/blob/master/include/llvm/Transforms/IPO/LowerTypeTests.h
|
