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