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_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 24 namespace std { 25 class type_info { 26 public: 27 virtual ~type_info(); 28 29 const char *__type_name; 30 }; 31 } 32 33 namespace __cxxabiv1 { 34 35 /// Type info for classes with no bases, and base class for type info for 36 /// classes with bases. 37 class __class_type_info : public std::type_info { 38 virtual ~__class_type_info(); 39 }; 40 41 /// Type info for classes with simple single public inheritance. 42 class __si_class_type_info : public __class_type_info { 43 public: 44 virtual ~__si_class_type_info(); 45 46 const __class_type_info *__base_type; 47 }; 48 49 class __base_class_type_info { 50 public: 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. 62 class __vmi_class_type_info : public __class_type_info { 63 public: 64 virtual ~__vmi_class_type_info(); 65 66 unsigned int flags; 67 unsigned int base_count; 68 __base_class_type_info base_info[1]; 69 }; 70 71 } 72 73 namespace abi = __cxxabiv1; 74 75 // We implement a simple two-level cache for type-checking results. For each 76 // (vptr,type) pair, a hash is computed. This hash is assumed to be globally 77 // unique; if it collides, we will get false negatives, but: 78 // * such a collision would have to occur on the *first* bad access, 79 // * the probability of such a collision is low (and for a 64-bit target, is 80 // negligible), and 81 // * the vptr, and thus the hash, can be affected by ASLR, so multiple runs 82 // give better coverage. 83 // 84 // The first caching layer is a small hash table with no chaining; buckets are 85 // reused as needed. The second caching layer is a large hash table with open 86 // chaining. We can freely evict from either layer since this is just a cache. 87 // 88 // FIXME: Make these hash table accesses thread-safe. The races here are benign: 89 // assuming the unsequenced loads and stores don't misbehave too badly, 90 // the worst case is false negatives or poor cache behavior, not false 91 // positives or crashes. 92 93 /// Find a bucket to store the given hash value in. 94 static __ubsan::HashValue *getTypeCacheHashTableBucket(__ubsan::HashValue V) { 95 static const unsigned HashTableSize = 65537; 96 static __ubsan::HashValue __ubsan_vptr_hash_set[HashTableSize]; 97 98 unsigned First = (V & 65535) ^ 1; 99 unsigned Probe = First; 100 for (int Tries = 5; Tries; --Tries) { 101 if (!__ubsan_vptr_hash_set[Probe] || __ubsan_vptr_hash_set[Probe] == V) 102 return &__ubsan_vptr_hash_set[Probe]; 103 Probe += ((V >> 16) & 65535) + 1; 104 if (Probe >= HashTableSize) 105 Probe -= HashTableSize; 106 } 107 // FIXME: Pick a random entry from the probe sequence to evict rather than 108 // just taking the first. 109 return &__ubsan_vptr_hash_set[First]; 110 } 111 112 /// A cache of recently-checked hashes. Mini hash table with "random" evictions. 113 __ubsan::HashValue 114 __ubsan::__ubsan_vptr_type_cache[__ubsan::VptrTypeCacheSize]; 115 116 /// \brief Determine whether \p Derived has a \p Base base class subobject at 117 /// offset \p Offset. 118 static bool isDerivedFromAtOffset(const abi::__class_type_info *Derived, 119 const abi::__class_type_info *Base, 120 sptr Offset) { 121 if (Derived->__type_name == Base->__type_name) 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 0; 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 0; 185 } 186 187 namespace { 188 189 struct VtablePrefix { 190 /// The offset from the vptr to the start of the most-derived object. 191 /// This should never be greater than zero, and will usually be exactly 192 /// 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 *Object) { 198 VtablePrefix **VptrPtr = reinterpret_cast<VtablePrefix**>(Object); 199 if (!*VptrPtr) 200 return 0; 201 VtablePrefix *Prefix = *VptrPtr - 1; 202 if (Prefix->Offset > 0 || !Prefix->TypeInfo) 203 // This can't possibly be a valid vtable. 204 return 0; 205 return Prefix; 206 } 207 208 } 209 210 bool __ubsan::checkDynamicType(void *Object, void *Type, HashValue Hash) { 211 // A crash anywhere within this function probably means the vptr is corrupted. 212 // FIXME: Perform these checks more cautiously. 213 214 // Check whether this is something we've evicted from the cache. 215 HashValue *Bucket = getTypeCacheHashTableBucket(Hash); 216 if (*Bucket == Hash) { 217 __ubsan_vptr_type_cache[Hash % VptrTypeCacheSize] = Hash; 218 return true; 219 } 220 221 VtablePrefix *Vtable = getVtablePrefix(Object); 222 if (!Vtable) 223 return false; 224 225 // Check that this is actually a type_info object for a class type. 226 abi::__class_type_info *Derived = 227 dynamic_cast<abi::__class_type_info*>(Vtable->TypeInfo); 228 if (!Derived) 229 return false; 230 231 abi::__class_type_info *Base = (abi::__class_type_info*)Type; 232 if (!isDerivedFromAtOffset(Derived, Base, -Vtable->Offset)) 233 return false; 234 235 // Success. Cache this result. 236 __ubsan_vptr_type_cache[Hash % VptrTypeCacheSize] = Hash; 237 *Bucket = Hash; 238 return true; 239 } 240 241 __ubsan::DynamicTypeInfo __ubsan::getDynamicTypeInfo(void *Object) { 242 VtablePrefix *Vtable = getVtablePrefix(Object); 243 if (!Vtable) 244 return DynamicTypeInfo(0, 0, 0); 245 const abi::__class_type_info *ObjectType = findBaseAtOffset( 246 static_cast<const abi::__class_type_info*>(Vtable->TypeInfo), 247 -Vtable->Offset); 248 return DynamicTypeInfo(Vtable->TypeInfo->__type_name, -Vtable->Offset, 249 ObjectType ? ObjectType->__type_name : "<unknown>"); 250 } 251