1 //===-- ubsan_type_hash.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 a hash table for fast checking of inheritance 11 // relationships. This file is only linked into C++ compilations, and is 12 // permitted to use language features which require a C++ ABI library. 13 // 14 //===----------------------------------------------------------------------===// 15 16 #include "ubsan_platform.h" 17 #if CAN_SANITIZE_UB 18 #include "ubsan_type_hash.h" 19 20 #include "sanitizer_common/sanitizer_common.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 26 namespace std { 27 class type_info { 28 public: 29 virtual ~type_info(); 30 31 const char *__type_name; 32 }; 33 } 34 35 namespace __cxxabiv1 { 36 37 /// Type info for classes with no bases, and base class for type info for 38 /// classes with bases. 39 class __class_type_info : public std::type_info { 40 ~__class_type_info() override; 41 }; 42 43 /// Type info for classes with simple single public inheritance. 44 class __si_class_type_info : public __class_type_info { 45 public: 46 ~__si_class_type_info() override; 47 48 const __class_type_info *__base_type; 49 }; 50 51 class __base_class_type_info { 52 public: 53 const __class_type_info *__base_type; 54 long __offset_flags; 55 56 enum __offset_flags_masks { 57 __virtual_mask = 0x1, 58 __public_mask = 0x2, 59 __offset_shift = 8 60 }; 61 }; 62 63 /// Type info for classes with multiple, virtual, or non-public inheritance. 64 class __vmi_class_type_info : public __class_type_info { 65 public: 66 ~__vmi_class_type_info() override; 67 68 unsigned int flags; 69 unsigned int base_count; 70 __base_class_type_info base_info[1]; 71 }; 72 73 } 74 75 namespace abi = __cxxabiv1; 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. 96 static __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 /// A cache of recently-checked hashes. Mini hash table with "random" evictions. 115 __ubsan::HashValue 116 __ubsan::__ubsan_vptr_type_cache[__ubsan::VptrTypeCacheSize]; 117 118 /// \brief Determine whether \p Derived has a \p Base base class subobject at 119 /// offset \p Offset. 120 static bool isDerivedFromAtOffset(const abi::__class_type_info *Derived, 121 const abi::__class_type_info *Base, 122 sptr Offset) { 123 if (Derived->__type_name == Base->__type_name) 124 return Offset == 0; 125 126 if (const abi::__si_class_type_info *SI = 127 dynamic_cast<const abi::__si_class_type_info*>(Derived)) 128 return isDerivedFromAtOffset(SI->__base_type, Base, Offset); 129 130 const abi::__vmi_class_type_info *VTI = 131 dynamic_cast<const abi::__vmi_class_type_info*>(Derived); 132 if (!VTI) 133 // No base class subobjects. 134 return false; 135 136 // Look for a base class which is derived from \p Base at the right offset. 137 for (unsigned int base = 0; base != VTI->base_count; ++base) { 138 // FIXME: Curtail the recursion if this base can't possibly contain the 139 // given offset. 140 sptr OffsetHere = VTI->base_info[base].__offset_flags >> 141 abi::__base_class_type_info::__offset_shift; 142 if (VTI->base_info[base].__offset_flags & 143 abi::__base_class_type_info::__virtual_mask) 144 // For now, just punt on virtual bases and say 'yes'. 145 // FIXME: OffsetHere is the offset in the vtable of the virtual base 146 // offset. Read the vbase offset out of the vtable and use it. 147 return true; 148 if (isDerivedFromAtOffset(VTI->base_info[base].__base_type, 149 Base, Offset - OffsetHere)) 150 return true; 151 } 152 153 return false; 154 } 155 156 /// \brief Find the derived-most dynamic base class of \p Derived at offset 157 /// \p Offset. 158 static const abi::__class_type_info *findBaseAtOffset( 159 const abi::__class_type_info *Derived, sptr Offset) { 160 if (!Offset) 161 return Derived; 162 163 if (const abi::__si_class_type_info *SI = 164 dynamic_cast<const abi::__si_class_type_info*>(Derived)) 165 return findBaseAtOffset(SI->__base_type, Offset); 166 167 const abi::__vmi_class_type_info *VTI = 168 dynamic_cast<const abi::__vmi_class_type_info*>(Derived); 169 if (!VTI) 170 // No base class subobjects. 171 return 0; 172 173 for (unsigned int base = 0; base != VTI->base_count; ++base) { 174 sptr OffsetHere = VTI->base_info[base].__offset_flags >> 175 abi::__base_class_type_info::__offset_shift; 176 if (VTI->base_info[base].__offset_flags & 177 abi::__base_class_type_info::__virtual_mask) 178 // FIXME: Can't handle virtual bases yet. 179 continue; 180 if (const abi::__class_type_info *Base = 181 findBaseAtOffset(VTI->base_info[base].__base_type, 182 Offset - OffsetHere)) 183 return Base; 184 } 185 186 return 0; 187 } 188 189 namespace { 190 191 struct VtablePrefix { 192 /// The offset from the vptr to the start of the most-derived object. 193 /// This should never be greater than zero, and will usually be exactly 194 /// zero. 195 sptr Offset; 196 /// The type_info object describing the most-derived class type. 197 std::type_info *TypeInfo; 198 }; 199 VtablePrefix *getVtablePrefix(void *Object) { 200 VtablePrefix **VptrPtr = reinterpret_cast<VtablePrefix**>(Object); 201 if (!*VptrPtr) 202 return 0; 203 VtablePrefix *Prefix = *VptrPtr - 1; 204 if (Prefix->Offset > 0 || !Prefix->TypeInfo) 205 // This can't possibly be a valid vtable. 206 return 0; 207 return Prefix; 208 } 209 210 } 211 212 bool __ubsan::checkDynamicType(void *Object, void *Type, HashValue Hash) { 213 // A crash anywhere within this function probably means the vptr is corrupted. 214 // FIXME: Perform these checks more cautiously. 215 216 // Check whether this is something we've evicted from the cache. 217 HashValue *Bucket = getTypeCacheHashTableBucket(Hash); 218 if (*Bucket == Hash) { 219 __ubsan_vptr_type_cache[Hash % VptrTypeCacheSize] = Hash; 220 return true; 221 } 222 223 VtablePrefix *Vtable = getVtablePrefix(Object); 224 if (!Vtable) 225 return false; 226 227 // Check that this is actually a type_info object for a class type. 228 abi::__class_type_info *Derived = 229 dynamic_cast<abi::__class_type_info*>(Vtable->TypeInfo); 230 if (!Derived) 231 return false; 232 233 abi::__class_type_info *Base = (abi::__class_type_info*)Type; 234 if (!isDerivedFromAtOffset(Derived, Base, -Vtable->Offset)) 235 return false; 236 237 // Success. Cache this result. 238 __ubsan_vptr_type_cache[Hash % VptrTypeCacheSize] = Hash; 239 *Bucket = Hash; 240 return true; 241 } 242 243 __ubsan::DynamicTypeInfo __ubsan::getDynamicTypeInfo(void *Object) { 244 VtablePrefix *Vtable = getVtablePrefix(Object); 245 if (!Vtable) 246 return DynamicTypeInfo(0, 0, 0); 247 const abi::__class_type_info *ObjectType = findBaseAtOffset( 248 static_cast<const abi::__class_type_info*>(Vtable->TypeInfo), 249 -Vtable->Offset); 250 return DynamicTypeInfo(Vtable->TypeInfo->__type_name, -Vtable->Offset, 251 ObjectType ? ObjectType->__type_name : "<unknown>"); 252 } 253 254 #endif // CAN_SANITIZE_UB 255
