291 lines · plain
1=============2Type Metadata3=============4 5Type metadata is a mechanism that allows IR modules to co-operatively build6pointer sets corresponding to addresses within a given set of globals. LLVM's7`control flow integrity`_ implementation uses this metadata to efficiently8check (at each call site) that a given address corresponds to either a9valid vtable or function pointer for a given class or function type, and its10whole-program devirtualization pass uses the metadata to identify potential11callees 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 type17 18These metadata nodes are associated with globals by using global object19metadata attachments with the ``!type`` metadata kind.20 21Each type identifier must exclusively identify either global variables22or functions.23 24.. admonition:: Limitation25 26 The current implementation only supports attaching metadata to functions on27 the x86-32 and x86-64 architectures.28 29An intrinsic, :ref:`llvm.type.test <type.test>`, is used to test whether a30given pointer is associated with a type identifier.31 32.. _control flow integrity: https://clang.llvm.org/docs/ControlFlowIntegrity.html33 34Representing Type Information using Type Metadata35=================================================36 37This section describes how Clang represents C++ type information associated with38virtual 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, D65 :header: Class, 0, 1, 2, 3, 4, 5, 666 67 A, A::offset-to-top, &A::rtti, &A::f68 B, B::offset-to-top, &B::rtti, &B::f, &B::g69 C, C::offset-to-top, &C::rtti, &C::h70 D, D::offset-to-top, &D::rtti, &D::f, &D::h, D::offset-to-top, &D::rtti, thunk for &D::h71 72When an object of type A is constructed, the address of ``&A::f`` in A's73virtual table object is stored in the object's vtable pointer. In ABI parlance74this address is known as an `address point`_. Similarly, when an object of type75B is constructed, the address of ``&B::f`` is stored in the vtable pointer. In76this 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. Its79virtual table object contains two vtables, one compatible with A's vtable and80the other compatible with C's vtable. Objects of type D contain two virtual81pointers, one belonging to the A subobject and containing the address of82the vtable compatible with A's vtable, and the other belonging to the C83subobject and containing the address of the vtable compatible with C's vtable.84 85The full set of compatibility information for the above class hierarchy is86shown below. The following table shows the name of a class, the offset of an87address point within that class's vtable and the name of one of the classes88with which that address point is compatible.89 90.. csv-table:: Type Offsets for A, B, C, D91 :header: VTable for, Offset, Compatible Class92 93 A, 16, A94 B, 16, A95 , , B96 C, 16, C97 D, 16, A98 , , D99 , 48, C100 101The next step is to encode this compatibility information into the IR. The way102this is done is to create type metadata named after each of the compatible103classes, with which we associate each of the compatible address points in104each vtable. For example, these type metadata entries encode the compatibility105information for the above hierarchy:106 107::108 109 @_ZTV1A = constant [...], !type !0110 @_ZTV1B = constant [...], !type !0, !type !1111 @_ZTV1C = constant [...], !type !2112 @_ZTV1D = constant [...], !type !0, !type !3, !type !4113 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 to121test whether a given pointer is compatible with a type identifier. Working122backwards, if ``llvm.type.test`` returns true for a particular pointer,123we can also statically determine the identities of the virtual functions124that a particular virtual call may call. For example, if a program assumes125a pointer to be a member of ``!"_ZST1A"``, we know that the address can126be only be one of ``_ZTV1A+16``, ``_ZTV1B+16`` or ``_ZTV1D+16`` (i.e. the127address points of the vtables of A, B and D respectively). If we then load128an address from that pointer, we know that the address can only be one of129``&A::f``, ``&B::f`` or ``&D::f``.130 131.. _address point: https://itanium-cxx-abi.github.io/cxx-abi/abi.html#vtable-general132 133Testing Addresses For Type Membership134=====================================135 136If a program tests an address using ``llvm.type.test``, this will cause137a link-time optimization pass, ``LowerTypeTests``, to replace calls to this138intrinsic with efficient code to perform type member tests. At a high level,139the pass will lay out referenced globals in a consecutive memory region in140the object file, construct bit vectors that map onto that memory region,141and generate code at each of the ``llvm.type.test`` call sites to test142pointers against those bit vectors. Because of the layout manipulation, the143globals' 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 each148of the functions associated with the type identifier that branches to the149target function. The pass will redirect any taken function addresses to the150corresponding jump table entry. In the object file's symbol table, the jump151table entries take the identities of the original functions, so that addresses152taken outside the module will pass any verification done inside the module.153 154Jump tables may call external functions, so their definitions need not155be available at LTO time. Note that if an externally defined function is156associated with a type identifier, there is no guarantee that its identity157within 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 globals161efficiently to minimize the sizes of the underlying bitsets.162 163.. _control flow integrity design document: https://clang.llvm.org/docs/ControlFlowIntegrityDesign.html164 165:Example:166 167::168 169 target datalayout = "e-p:32:32"170 171 @a = internal global i32 0, !type !0172 @b = internal global i32 0, !type !0, !type !1173 @c = internal global i32 0, !type !1174 @d = internal global [2 x i32] [i32 0, i32 0], !type !2175 176 define void @e() !type !3 {177 ret void178 }179 180 define void @f() {181 ret void182 }183 184 declare void @g() !type !3185 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 readnone192 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 %x197 }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 %x203 }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 %x209 }210 211 define void @main() {212 %a1 = call i1 @foo(i32* @a) ; returns 1213 %b1 = call i1 @foo(i32* @b) ; returns 1214 %c1 = call i1 @foo(i32* @c) ; returns 0215 %a2 = call i1 @bar(i32* @a) ; returns 0216 %b2 = call i1 @bar(i32* @b) ; returns 1217 %c2 = call i1 @bar(i32* @c) ; returns 1218 %d02 = call i1 @bar(i32* getelementptr ([2 x i32]* @d, i32 0, i32 0)) ; returns 0219 %d12 = call i1 @bar(i32* getelementptr ([2 x i32]* @d, i32 0, i32 1)) ; returns 1220 %e = call i1 @baz(void ()* @e) ; returns 1221 %f = call i1 @baz(void ()* @f) ; returns 0222 %g = call i1 @baz(void ()* @g) ; returns 1223 ret void224 }225 226.. _GlobalLayoutBuilder: https://github.com/llvm/llvm-project/blob/main/llvm/include/llvm/Transforms/IPO/LowerTypeTests.h227 228``!vcall_visibility`` Metadata229==============================230 231In order to allow removing unused function pointers from vtables, we need to232know whether every virtual call which could use it is known to the compiler, or233whether another translation unit could introduce more calls through the vtable.234This is not the same as the linkage of the vtable, because call sites could be235using a pointer of a more widely-visible base class. For example, consider this236code: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 250With LTO, we know that all code which can see the declaration of ``B`` is251visible to us. However, a pointer to a ``B`` could be cast to ``A*`` and passed252to another linkage unit, which could then call ``f`` on it. This call would253load from the vtable for ``B`` (using the object pointer), and then call254``B::f``. This means we can't remove the function pointer from ``B``'s vtable,255or the implementation of ``B::f``. However, if we can see all code which knows256about any dynamic base class (which would be the case if ``B`` only inherited257from classes with hidden visibility), then this optimisation would be valid.258 259This concept is represented in IR by the ``!vcall_visibility`` metadata260attached to vtable objects, with the following values:261 262.. list-table::263 :header-rows: 1264 :widths: 10 90265 266 * - Value267 - Behavior268 269 * - 0 (or omitted)270 - **Public**271 Virtual function calls using this vtable could be made from external272 code.273 274 * - 1275 - **Linkage Unit**276 All virtual function calls which might use this vtable are in the277 current LTO unit, meaning they will be in the current module once278 LTO linking has been performed.279 280 * - 2281 - **Translation Unit**282 All virtual function calls which might use this vtable are in the283 current module.284 285In addition, all function pointer loads from a vtable marked with the286``!vcall_visibility`` metadata (with a non-zero value) must be done using the287:ref:`llvm.type.checked.load <type.checked.load>` intrinsic, so that virtual288calls sites can be correlated with the vtables which they might load from.289Other parts of the vtable (RTTI, offset-to-top, ...) can still be accessed with290normal loads.291