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