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