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 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 25 namespace std { 26 class type_info { 27 public: 28 virtual ~type_info(); 29 30 const char *__type_name; 31 }; 32 } 33 34 namespace __cxxabiv1 { 35 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; 40 }; 41 42 /// Type info for classes with simple single public inheritance. 43 class __si_class_type_info : public __class_type_info { 44 public: 45 ~__si_class_type_info() override; 46 47 const __class_type_info *__base_type; 48 }; 49 50 class __base_class_type_info { 51 public: 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. 63 class __vmi_class_type_info : public __class_type_info { 64 public: 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 74 namespace abi = __cxxabiv1; 75 76 using namespace __sanitizer; 77 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 83 // negligible), and 84 // * the vptr, and thus the hash, can be affected by ASLR, so multiple runs 85 // give better coverage. 86 // 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. 90 // 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. 95 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]; 100 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; 109 } 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]; 113 } 114 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, 119 sptr Offset) { 120 if (Derived->__type_name == Base->__type_name || 121 __ubsan::checkTypeInfoEquality(Derived, Base)) 122 return Offset == 0; 123 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); 127 128 const abi::__vmi_class_type_info *VTI = 129 dynamic_cast<const abi::__vmi_class_type_info*>(Derived); 130 if (!VTI) 131 // No base class subobjects. 132 return false; 133 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 137 // given offset. 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. 145 return true; 146 if (isDerivedFromAtOffset(VTI->base_info[base].__base_type, 147 Base, Offset - OffsetHere)) 148 return true; 149 } 150 151 return false; 152 } 153 154 /// \brief Find the derived-most dynamic base class of \p Derived at offset 155 /// \p Offset. 156 static const abi::__class_type_info *findBaseAtOffset( 157 const abi::__class_type_info *Derived, sptr Offset) { 158 if (!Offset) 159 return Derived; 160 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); 164 165 const abi::__vmi_class_type_info *VTI = 166 dynamic_cast<const abi::__vmi_class_type_info*>(Derived); 167 if (!VTI) 168 // No base class subobjects. 169 return nullptr; 170 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. 177 continue; 178 if (const abi::__class_type_info *Base = 179 findBaseAtOffset(VTI->base_info[base].__base_type, 180 Offset - OffsetHere)) 181 return Base; 182 } 183 184 return nullptr; 185 } 186 187 namespace { 188 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. 193 sptr Offset; 194 /// The type_info object describing the most-derived class type. 195 std::type_info *TypeInfo; 196 }; 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))) 202 return nullptr; 203 if (!Prefix->TypeInfo) 204 // This can't possibly be a valid vtable. 205 return nullptr; 206 return Prefix; 207 } 208 209 } 210 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. 214 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; 219 return true; 220 } 221 222 void *VtablePtr = *reinterpret_cast<void **>(Object); 223 VtablePrefix *Vtable = getVtablePrefix(VtablePtr); 224 if (!Vtable) 225 return false; 226 if (Vtable->Offset < -VptrMaxOffsetToTop || Vtable->Offset > VptrMaxOffsetToTop) { 227 // Too large or too small offset are signs of Vtable corruption. 228 return false; 229 } 230 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); 234 if (!Derived) 235 return false; 236 237 abi::__class_type_info *Base = (abi::__class_type_info*)Type; 238 if (!isDerivedFromAtOffset(Derived, Base, -Vtable->Offset)) 239 return false; 240 241 // Success. Cache this result. 242 __ubsan_vptr_type_cache[Hash % VptrTypeCacheSize] = Hash; 243 *Bucket = Hash; 244 return true; 245 } 246 247 __ubsan::DynamicTypeInfo 248 __ubsan::getDynamicTypeInfoFromVtable(void *VtablePtr) { 249 VtablePrefix *Vtable = getVtablePrefix(VtablePtr); 250 if (!Vtable) 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), 256 -Vtable->Offset); 257 return DynamicTypeInfo(Vtable->TypeInfo->__type_name, -Vtable->Offset, 258 ObjectType ? ObjectType->__type_name : "<unknown>"); 259 } 260 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); 268 } 269 270 #endif // CAN_SANITIZE_UB && !SANITIZER_WINDOWS 271