1//===-- ubsan_type_hash_itanium.cpp ---------------------------------------===// 2// 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 6// 7//===----------------------------------------------------------------------===// 8// 9// Implementation of type hashing/lookup for Itanium C++ ABI. 10// 11//===----------------------------------------------------------------------===// 12 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" 17 18#include "sanitizer_common/sanitizer_common.h" 19#include "sanitizer_common/sanitizer_ptrauth.h" 20#include <stdint.h> 21 22// The following are intended to be binary compatible with the definitions 23// given in the Itanium ABI. We make no attempt to be ODR-compatible with 24// those definitions, since existing ABI implementations aren't. 25 26namespace std { 27 class type_info { 28 public: 29 typedef const char *__type_name_t; 30 virtual ~type_info(); 31 32 const char *__type_name; 33 34 __type_name_t name() const { 35#if defined(__APPLE__) && defined(__LP64__) && !defined(__x86_64__) 36 uintptr_t __non_unique_rtti_bit = 37 (1ULL << ((__CHAR_BIT__ * sizeof(__type_name_t)) - 1)); 38 return (__type_name_t)((uintptr_t)__type_name & ~__non_unique_rtti_bit); 39#else 40 return __type_name; 41#endif 42 } 43 }; 44} 45 46namespace __cxxabiv1 { 47 48/// Type info for classes with no bases, and base class for type info for 49/// classes with bases. 50class __class_type_info : public std::type_info { 51 ~__class_type_info() override; 52}; 53 54/// Type info for classes with simple single public inheritance. 55class __si_class_type_info : public __class_type_info { 56public: 57 ~__si_class_type_info() override; 58 59 const __class_type_info *__base_type; 60}; 61 62class __base_class_type_info { 63public: 64 const __class_type_info *__base_type; 65 long __offset_flags; 66 67 enum __offset_flags_masks { 68 __virtual_mask = 0x1, 69 __public_mask = 0x2, 70 __offset_shift = 8 71 }; 72}; 73 74/// Type info for classes with multiple, virtual, or non-public inheritance. 75class __vmi_class_type_info : public __class_type_info { 76public: 77 ~__vmi_class_type_info() override; 78 79 unsigned int flags; 80 unsigned int base_count; 81 __base_class_type_info base_info[1]; 82}; 83 84} 85 86namespace abi = __cxxabiv1; 87 88using namespace __sanitizer; 89 90// We implement a simple two-level cache for type-checking results. For each 91// (vptr,type) pair, a hash is computed. This hash is assumed to be globally 92// unique; if it collides, we will get false negatives, but: 93// * such a collision would have to occur on the *first* bad access, 94// * the probability of such a collision is low (and for a 64-bit target, is 95// negligible), and 96// * the vptr, and thus the hash, can be affected by ASLR, so multiple runs 97// give better coverage. 98// 99// The first caching layer is a small hash table with no chaining; buckets are 100// reused as needed. The second caching layer is a large hash table with open 101// chaining. We can freely evict from either layer since this is just a cache. 102// 103// FIXME: Make these hash table accesses thread-safe. The races here are benign: 104// assuming the unsequenced loads and stores don't misbehave too badly, 105// the worst case is false negatives or poor cache behavior, not false 106// positives or crashes. 107 108/// Find a bucket to store the given hash value in. 109static __ubsan::HashValue *getTypeCacheHashTableBucket(__ubsan::HashValue V) { 110 static const unsigned HashTableSize = 65537; 111 static __ubsan::HashValue __ubsan_vptr_hash_set[HashTableSize]; 112 113 unsigned First = (V & 65535) ^ 1; 114 unsigned Probe = First; 115 for (int Tries = 5; Tries; --Tries) { 116 if (!__ubsan_vptr_hash_set[Probe] || __ubsan_vptr_hash_set[Probe] == V) 117 return &__ubsan_vptr_hash_set[Probe]; 118 Probe += ((V >> 16) & 65535) + 1; 119 if (Probe >= HashTableSize) 120 Probe -= HashTableSize; 121 } 122 // FIXME: Pick a random entry from the probe sequence to evict rather than 123 // just taking the first. 124 return &__ubsan_vptr_hash_set[First]; 125} 126 127/// \brief Determine whether \p Derived has a \p Base base class subobject at 128/// offset \p Offset. 129static bool isDerivedFromAtOffset(const abi::__class_type_info *Derived, 130 const abi::__class_type_info *Base, 131 sptr Offset) { 132 if (Derived->name() == Base->name() || 133 __ubsan::checkTypeInfoEquality(Derived, Base)) 134 return Offset == 0; 135 136 if (const abi::__si_class_type_info *SI = 137 dynamic_cast<const abi::__si_class_type_info*>(Derived)) 138 return isDerivedFromAtOffset(SI->__base_type, Base, Offset); 139 140 const abi::__vmi_class_type_info *VTI = 141 dynamic_cast<const abi::__vmi_class_type_info*>(Derived); 142 if (!VTI) 143 // No base class subobjects. 144 return false; 145 146 // Look for a base class which is derived from \p Base at the right offset. 147 for (unsigned int base = 0; base != VTI->base_count; ++base) { 148 // FIXME: Curtail the recursion if this base can't possibly contain the 149 // given offset. 150 sptr OffsetHere = VTI->base_info[base].__offset_flags >> 151 abi::__base_class_type_info::__offset_shift; 152 if (VTI->base_info[base].__offset_flags & 153 abi::__base_class_type_info::__virtual_mask) 154 // For now, just punt on virtual bases and say 'yes'. 155 // FIXME: OffsetHere is the offset in the vtable of the virtual base 156 // offset. Read the vbase offset out of the vtable and use it. 157 return true; 158 if (isDerivedFromAtOffset(VTI->base_info[base].__base_type, 159 Base, Offset - OffsetHere)) 160 return true; 161 } 162 163 return false; 164} 165 166/// \brief Find the derived-most dynamic base class of \p Derived at offset 167/// \p Offset. 168static const abi::__class_type_info *findBaseAtOffset( 169 const abi::__class_type_info *Derived, sptr Offset) { 170 if (!Offset) 171 return Derived; 172 173 if (const abi::__si_class_type_info *SI = 174 dynamic_cast<const abi::__si_class_type_info*>(Derived)) 175 return findBaseAtOffset(SI->__base_type, Offset); 176 177 const abi::__vmi_class_type_info *VTI = 178 dynamic_cast<const abi::__vmi_class_type_info*>(Derived); 179 if (!VTI) 180 // No base class subobjects. 181 return nullptr; 182 183 for (unsigned int base = 0; base != VTI->base_count; ++base) { 184 sptr OffsetHere = VTI->base_info[base].__offset_flags >> 185 abi::__base_class_type_info::__offset_shift; 186 if (VTI->base_info[base].__offset_flags & 187 abi::__base_class_type_info::__virtual_mask) 188 // FIXME: Can't handle virtual bases yet. 189 continue; 190 if (const abi::__class_type_info *Base = 191 findBaseAtOffset(VTI->base_info[base].__base_type, 192 Offset - OffsetHere)) 193 return Base; 194 } 195 196 return nullptr; 197} 198 199namespace { 200 201struct VtablePrefix { 202 /// The offset from the vptr to the start of the most-derived object. 203 /// This will only be greater than zero in some virtual base class vtables 204 /// used during object con-/destruction, and will usually be exactly zero. 205 sptr Offset; 206 /// The type_info object describing the most-derived class type. 207 std::type_info *TypeInfo; 208}; 209VtablePrefix *getVtablePrefix(void *Vtable) { 210 Vtable = ptrauth_auth_data(Vtable, ptrauth_key_cxx_vtable_pointer, 0); 211 VtablePrefix *Vptr = reinterpret_cast<VtablePrefix*>(Vtable); 212 VtablePrefix *Prefix = Vptr - 1; 213 if (!IsAccessibleMemoryRange((uptr)Prefix, sizeof(VtablePrefix))) 214 return nullptr; 215 if (!Prefix->TypeInfo) 216 // This can't possibly be a valid vtable. 217 return nullptr; 218 return Prefix; 219} 220 221} 222 223bool __ubsan::checkDynamicType(void *Object, void *Type, HashValue Hash) { 224 // A crash anywhere within this function probably means the vptr is corrupted. 225 // FIXME: Perform these checks more cautiously. 226 227 // Check whether this is something we've evicted from the cache. 228 HashValue *Bucket = getTypeCacheHashTableBucket(Hash); 229 if (*Bucket == Hash) { 230 __ubsan_vptr_type_cache[Hash % VptrTypeCacheSize] = Hash; 231 return true; 232 } 233 234 void *VtablePtr = *reinterpret_cast<void **>(Object); 235 VtablePrefix *Vtable = getVtablePrefix(VtablePtr); 236 if (!Vtable) 237 return false; 238 if (Vtable->Offset < -VptrMaxOffsetToTop || Vtable->Offset > VptrMaxOffsetToTop) { 239 // Too large or too small offset are signs of Vtable corruption. 240 return false; 241 } 242 243 // Check that this is actually a type_info object for a class type. 244 abi::__class_type_info *Derived = 245 dynamic_cast<abi::__class_type_info*>(Vtable->TypeInfo); 246 if (!Derived) 247 return false; 248 249 abi::__class_type_info *Base = (abi::__class_type_info*)Type; 250 if (!isDerivedFromAtOffset(Derived, Base, -Vtable->Offset)) 251 return false; 252 253 // Success. Cache this result. 254 __ubsan_vptr_type_cache[Hash % VptrTypeCacheSize] = Hash; 255 *Bucket = Hash; 256 return true; 257} 258 259__ubsan::DynamicTypeInfo 260__ubsan::getDynamicTypeInfoFromVtable(void *VtablePtr) { 261 VtablePrefix *Vtable = getVtablePrefix(VtablePtr); 262 if (!Vtable) 263 return DynamicTypeInfo(nullptr, 0, nullptr); 264 if (Vtable->Offset < -VptrMaxOffsetToTop || Vtable->Offset > VptrMaxOffsetToTop) 265 return DynamicTypeInfo(nullptr, Vtable->Offset, nullptr); 266 const abi::__class_type_info *ObjectType = findBaseAtOffset( 267 static_cast<const abi::__class_type_info*>(Vtable->TypeInfo), 268 -Vtable->Offset); 269 return DynamicTypeInfo(Vtable->TypeInfo->name(), -Vtable->Offset, 270 ObjectType ? ObjectType->name() : "<unknown>"); 271} 272 273bool __ubsan::checkTypeInfoEquality(const void *TypeInfo1, 274 const void *TypeInfo2) { 275 auto TI1 = static_cast<const std::type_info *>(TypeInfo1); 276 auto TI2 = static_cast<const std::type_info *>(TypeInfo2); 277 return SANITIZER_NON_UNIQUE_TYPEINFO && TI1->name()[0] != '*' && 278 TI2->name()[0] != '*' && !internal_strcmp(TI1->name(), TI2->name()); 279} 280 281#endif // CAN_SANITIZE_UB && !SANITIZER_WINDOWS 282