1 //===-- ubsan_type_hash_itanium.cpp ---------------------------------------===//
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
7 //===----------------------------------------------------------------------===//
9 // Implementation of type hashing/lookup for Itanium C++ ABI.
11 //===----------------------------------------------------------------------===//
13 #include "sanitizer_common/sanitizer_platform.h"
14 #include "ubsan_platform.h"
15 #if CAN_SANITIZE_UB && !defined(_MSC_VER)
16 #include "ubsan_type_hash.h"
18 #include "sanitizer_common/sanitizer_common.h"
19 #include "sanitizer_common/sanitizer_ptrauth.h"
21 // The following are intended to be binary compatible with the definitions
22 // given in the Itanium ABI. We make no attempt to be ODR-compatible with
23 // those definitions, since existing ABI implementations aren't.
30 const char *__type_name
;
34 namespace __cxxabiv1
{
36 /// Type info for classes with no bases, and base class for type info for
37 /// classes with bases.
38 class __class_type_info
: public std::type_info
{
39 ~__class_type_info() override
;
42 /// Type info for classes with simple single public inheritance.
43 class __si_class_type_info
: public __class_type_info
{
45 ~__si_class_type_info() override
;
47 const __class_type_info
*__base_type
;
50 class __base_class_type_info
{
52 const __class_type_info
*__base_type
;
55 enum __offset_flags_masks
{
62 /// Type info for classes with multiple, virtual, or non-public inheritance.
63 class __vmi_class_type_info
: public __class_type_info
{
65 ~__vmi_class_type_info() override
;
68 unsigned int base_count
;
69 __base_class_type_info base_info
[1];
74 namespace abi
= __cxxabiv1
;
76 using namespace __sanitizer
;
78 // We implement a simple two-level cache for type-checking results. For each
79 // (vptr,type) pair, a hash is computed. This hash is assumed to be globally
80 // unique; if it collides, we will get false negatives, but:
81 // * such a collision would have to occur on the *first* bad access,
82 // * the probability of such a collision is low (and for a 64-bit target, is
84 // * the vptr, and thus the hash, can be affected by ASLR, so multiple runs
85 // give better coverage.
87 // The first caching layer is a small hash table with no chaining; buckets are
88 // reused as needed. The second caching layer is a large hash table with open
89 // chaining. We can freely evict from either layer since this is just a cache.
91 // FIXME: Make these hash table accesses thread-safe. The races here are benign:
92 // assuming the unsequenced loads and stores don't misbehave too badly,
93 // the worst case is false negatives or poor cache behavior, not false
94 // positives or crashes.
96 /// Find a bucket to store the given hash value in.
97 static __ubsan::HashValue
*getTypeCacheHashTableBucket(__ubsan::HashValue V
) {
98 static const unsigned HashTableSize
= 65537;
99 static __ubsan::HashValue __ubsan_vptr_hash_set
[HashTableSize
];
101 unsigned First
= (V
& 65535) ^ 1;
102 unsigned Probe
= First
;
103 for (int Tries
= 5; Tries
; --Tries
) {
104 if (!__ubsan_vptr_hash_set
[Probe
] || __ubsan_vptr_hash_set
[Probe
] == V
)
105 return &__ubsan_vptr_hash_set
[Probe
];
106 Probe
+= ((V
>> 16) & 65535) + 1;
107 if (Probe
>= HashTableSize
)
108 Probe
-= HashTableSize
;
110 // FIXME: Pick a random entry from the probe sequence to evict rather than
111 // just taking the first.
112 return &__ubsan_vptr_hash_set
[First
];
115 /// \brief Determine whether \p Derived has a \p Base base class subobject at
116 /// offset \p Offset.
117 static bool isDerivedFromAtOffset(const abi::__class_type_info
*Derived
,
118 const abi::__class_type_info
*Base
,
120 if (Derived
->__type_name
== Base
->__type_name
||
121 __ubsan::checkTypeInfoEquality(Derived
, Base
))
124 if (const abi::__si_class_type_info
*SI
=
125 dynamic_cast<const abi::__si_class_type_info
*>(Derived
))
126 return isDerivedFromAtOffset(SI
->__base_type
, Base
, Offset
);
128 const abi::__vmi_class_type_info
*VTI
=
129 dynamic_cast<const abi::__vmi_class_type_info
*>(Derived
);
131 // No base class subobjects.
134 // Look for a base class which is derived from \p Base at the right offset.
135 for (unsigned int base
= 0; base
!= VTI
->base_count
; ++base
) {
136 // FIXME: Curtail the recursion if this base can't possibly contain the
138 sptr OffsetHere
= VTI
->base_info
[base
].__offset_flags
>>
139 abi::__base_class_type_info::__offset_shift
;
140 if (VTI
->base_info
[base
].__offset_flags
&
141 abi::__base_class_type_info::__virtual_mask
)
142 // For now, just punt on virtual bases and say 'yes'.
143 // FIXME: OffsetHere is the offset in the vtable of the virtual base
144 // offset. Read the vbase offset out of the vtable and use it.
146 if (isDerivedFromAtOffset(VTI
->base_info
[base
].__base_type
,
147 Base
, Offset
- OffsetHere
))
154 /// \brief Find the derived-most dynamic base class of \p Derived at offset
156 static const abi::__class_type_info
*findBaseAtOffset(
157 const abi::__class_type_info
*Derived
, sptr Offset
) {
161 if (const abi::__si_class_type_info
*SI
=
162 dynamic_cast<const abi::__si_class_type_info
*>(Derived
))
163 return findBaseAtOffset(SI
->__base_type
, Offset
);
165 const abi::__vmi_class_type_info
*VTI
=
166 dynamic_cast<const abi::__vmi_class_type_info
*>(Derived
);
168 // No base class subobjects.
171 for (unsigned int base
= 0; base
!= VTI
->base_count
; ++base
) {
172 sptr OffsetHere
= VTI
->base_info
[base
].__offset_flags
>>
173 abi::__base_class_type_info::__offset_shift
;
174 if (VTI
->base_info
[base
].__offset_flags
&
175 abi::__base_class_type_info::__virtual_mask
)
176 // FIXME: Can't handle virtual bases yet.
178 if (const abi::__class_type_info
*Base
=
179 findBaseAtOffset(VTI
->base_info
[base
].__base_type
,
180 Offset
- OffsetHere
))
189 struct VtablePrefix
{
190 /// The offset from the vptr to the start of the most-derived object.
191 /// This will only be greater than zero in some virtual base class vtables
192 /// used during object con-/destruction, and will usually be exactly zero.
194 /// The type_info object describing the most-derived class type.
195 std::type_info
*TypeInfo
;
197 VtablePrefix
*getVtablePrefix(void *Vtable
) {
198 Vtable
= ptrauth_auth_data(Vtable
, ptrauth_key_cxx_vtable_pointer
, 0);
199 VtablePrefix
*Vptr
= reinterpret_cast<VtablePrefix
*>(Vtable
);
200 VtablePrefix
*Prefix
= Vptr
- 1;
201 if (!IsAccessibleMemoryRange((uptr
)Prefix
, sizeof(VtablePrefix
)))
203 if (!Prefix
->TypeInfo
)
204 // This can't possibly be a valid vtable.
211 bool __ubsan::checkDynamicType(void *Object
, void *Type
, HashValue Hash
) {
212 // A crash anywhere within this function probably means the vptr is corrupted.
213 // FIXME: Perform these checks more cautiously.
215 // Check whether this is something we've evicted from the cache.
216 HashValue
*Bucket
= getTypeCacheHashTableBucket(Hash
);
217 if (*Bucket
== Hash
) {
218 __ubsan_vptr_type_cache
[Hash
% VptrTypeCacheSize
] = Hash
;
222 void *VtablePtr
= *reinterpret_cast<void **>(Object
);
223 VtablePrefix
*Vtable
= getVtablePrefix(VtablePtr
);
226 if (Vtable
->Offset
< -VptrMaxOffsetToTop
|| Vtable
->Offset
> VptrMaxOffsetToTop
) {
227 // Too large or too small offset are signs of Vtable corruption.
231 // Check that this is actually a type_info object for a class type.
232 abi::__class_type_info
*Derived
=
233 dynamic_cast<abi::__class_type_info
*>(Vtable
->TypeInfo
);
237 abi::__class_type_info
*Base
= (abi::__class_type_info
*)Type
;
238 if (!isDerivedFromAtOffset(Derived
, Base
, -Vtable
->Offset
))
241 // Success. Cache this result.
242 __ubsan_vptr_type_cache
[Hash
% VptrTypeCacheSize
] = Hash
;
247 __ubsan::DynamicTypeInfo
248 __ubsan::getDynamicTypeInfoFromVtable(void *VtablePtr
) {
249 VtablePrefix
*Vtable
= getVtablePrefix(VtablePtr
);
251 return DynamicTypeInfo(nullptr, 0, nullptr);
252 if (Vtable
->Offset
< -VptrMaxOffsetToTop
|| Vtable
->Offset
> VptrMaxOffsetToTop
)
253 return DynamicTypeInfo(nullptr, Vtable
->Offset
, nullptr);
254 const abi::__class_type_info
*ObjectType
= findBaseAtOffset(
255 static_cast<const abi::__class_type_info
*>(Vtable
->TypeInfo
),
257 return DynamicTypeInfo(Vtable
->TypeInfo
->__type_name
, -Vtable
->Offset
,
258 ObjectType
? ObjectType
->__type_name
: "<unknown>");
261 bool __ubsan::checkTypeInfoEquality(const void *TypeInfo1
,
262 const void *TypeInfo2
) {
263 auto TI1
= static_cast<const std::type_info
*>(TypeInfo1
);
264 auto TI2
= static_cast<const std::type_info
*>(TypeInfo2
);
265 return SANITIZER_NON_UNIQUE_TYPEINFO
&& TI1
->__type_name
[0] != '*' &&
266 TI2
->__type_name
[0] != '*' &&
267 !internal_strcmp(TI1
->__type_name
, TI2
->__type_name
);
270 #endif // CAN_SANITIZE_UB && !SANITIZER_WINDOWS