1287516Sdim//===-- ubsan_type_hash_itanium.cc ----------------------------------------===// 2287516Sdim// 3287516Sdim// The LLVM Compiler Infrastructure 4287516Sdim// 5287516Sdim// This file is distributed under the University of Illinois Open Source 6287516Sdim// License. See LICENSE.TXT for details. 7287516Sdim// 8287516Sdim//===----------------------------------------------------------------------===// 9287516Sdim// 10287516Sdim// Implementation of type hashing/lookup for Itanium C++ ABI. 11287516Sdim// 12287516Sdim//===----------------------------------------------------------------------===// 13287516Sdim 14287516Sdim#include "sanitizer_common/sanitizer_platform.h" 15287516Sdim#include "ubsan_platform.h" 16287516Sdim#if CAN_SANITIZE_UB && !SANITIZER_WINDOWS 17287516Sdim#include "ubsan_type_hash.h" 18287516Sdim 19287516Sdim#include "sanitizer_common/sanitizer_common.h" 20287516Sdim 21287516Sdim// The following are intended to be binary compatible with the definitions 22287516Sdim// given in the Itanium ABI. We make no attempt to be ODR-compatible with 23287516Sdim// those definitions, since existing ABI implementations aren't. 24287516Sdim 25287516Sdimnamespace std { 26287516Sdim class type_info { 27287516Sdim public: 28287516Sdim virtual ~type_info(); 29287516Sdim 30287516Sdim const char *__type_name; 31287516Sdim }; 32287516Sdim} 33287516Sdim 34287516Sdimnamespace __cxxabiv1 { 35287516Sdim 36287516Sdim/// Type info for classes with no bases, and base class for type info for 37287516Sdim/// classes with bases. 38287516Sdimclass __class_type_info : public std::type_info { 39287516Sdim ~__class_type_info() override; 40287516Sdim}; 41287516Sdim 42287516Sdim/// Type info for classes with simple single public inheritance. 43287516Sdimclass __si_class_type_info : public __class_type_info { 44287516Sdimpublic: 45287516Sdim ~__si_class_type_info() override; 46287516Sdim 47287516Sdim const __class_type_info *__base_type; 48287516Sdim}; 49287516Sdim 50287516Sdimclass __base_class_type_info { 51287516Sdimpublic: 52287516Sdim const __class_type_info *__base_type; 53287516Sdim long __offset_flags; 54287516Sdim 55287516Sdim enum __offset_flags_masks { 56287516Sdim __virtual_mask = 0x1, 57287516Sdim __public_mask = 0x2, 58287516Sdim __offset_shift = 8 59287516Sdim }; 60287516Sdim}; 61287516Sdim 62287516Sdim/// Type info for classes with multiple, virtual, or non-public inheritance. 63287516Sdimclass __vmi_class_type_info : public __class_type_info { 64287516Sdimpublic: 65287516Sdim ~__vmi_class_type_info() override; 66287516Sdim 67287516Sdim unsigned int flags; 68287516Sdim unsigned int base_count; 69287516Sdim __base_class_type_info base_info[1]; 70287516Sdim}; 71287516Sdim 72287516Sdim} 73287516Sdim 74287516Sdimnamespace abi = __cxxabiv1; 75287516Sdim 76287516Sdim// We implement a simple two-level cache for type-checking results. For each 77287516Sdim// (vptr,type) pair, a hash is computed. This hash is assumed to be globally 78287516Sdim// unique; if it collides, we will get false negatives, but: 79287516Sdim// * such a collision would have to occur on the *first* bad access, 80287516Sdim// * the probability of such a collision is low (and for a 64-bit target, is 81287516Sdim// negligible), and 82287516Sdim// * the vptr, and thus the hash, can be affected by ASLR, so multiple runs 83287516Sdim// give better coverage. 84287516Sdim// 85287516Sdim// The first caching layer is a small hash table with no chaining; buckets are 86287516Sdim// reused as needed. The second caching layer is a large hash table with open 87287516Sdim// chaining. We can freely evict from either layer since this is just a cache. 88287516Sdim// 89287516Sdim// FIXME: Make these hash table accesses thread-safe. The races here are benign: 90287516Sdim// assuming the unsequenced loads and stores don't misbehave too badly, 91287516Sdim// the worst case is false negatives or poor cache behavior, not false 92287516Sdim// positives or crashes. 93287516Sdim 94287516Sdim/// Find a bucket to store the given hash value in. 95287516Sdimstatic __ubsan::HashValue *getTypeCacheHashTableBucket(__ubsan::HashValue V) { 96287516Sdim static const unsigned HashTableSize = 65537; 97287516Sdim static __ubsan::HashValue __ubsan_vptr_hash_set[HashTableSize]; 98287516Sdim 99287516Sdim unsigned First = (V & 65535) ^ 1; 100287516Sdim unsigned Probe = First; 101287516Sdim for (int Tries = 5; Tries; --Tries) { 102287516Sdim if (!__ubsan_vptr_hash_set[Probe] || __ubsan_vptr_hash_set[Probe] == V) 103287516Sdim return &__ubsan_vptr_hash_set[Probe]; 104287516Sdim Probe += ((V >> 16) & 65535) + 1; 105287516Sdim if (Probe >= HashTableSize) 106287516Sdim Probe -= HashTableSize; 107287516Sdim } 108287516Sdim // FIXME: Pick a random entry from the probe sequence to evict rather than 109287516Sdim // just taking the first. 110287516Sdim return &__ubsan_vptr_hash_set[First]; 111287516Sdim} 112287516Sdim 113287516Sdim/// \brief Determine whether \p Derived has a \p Base base class subobject at 114287516Sdim/// offset \p Offset. 115287516Sdimstatic bool isDerivedFromAtOffset(const abi::__class_type_info *Derived, 116287516Sdim const abi::__class_type_info *Base, 117287516Sdim sptr Offset) { 118287516Sdim if (Derived->__type_name == Base->__type_name) 119287516Sdim return Offset == 0; 120287516Sdim 121287516Sdim if (const abi::__si_class_type_info *SI = 122287516Sdim dynamic_cast<const abi::__si_class_type_info*>(Derived)) 123287516Sdim return isDerivedFromAtOffset(SI->__base_type, Base, Offset); 124287516Sdim 125287516Sdim const abi::__vmi_class_type_info *VTI = 126287516Sdim dynamic_cast<const abi::__vmi_class_type_info*>(Derived); 127287516Sdim if (!VTI) 128287516Sdim // No base class subobjects. 129287516Sdim return false; 130287516Sdim 131287516Sdim // Look for a base class which is derived from \p Base at the right offset. 132287516Sdim for (unsigned int base = 0; base != VTI->base_count; ++base) { 133287516Sdim // FIXME: Curtail the recursion if this base can't possibly contain the 134287516Sdim // given offset. 135287516Sdim sptr OffsetHere = VTI->base_info[base].__offset_flags >> 136287516Sdim abi::__base_class_type_info::__offset_shift; 137287516Sdim if (VTI->base_info[base].__offset_flags & 138287516Sdim abi::__base_class_type_info::__virtual_mask) 139287516Sdim // For now, just punt on virtual bases and say 'yes'. 140287516Sdim // FIXME: OffsetHere is the offset in the vtable of the virtual base 141287516Sdim // offset. Read the vbase offset out of the vtable and use it. 142287516Sdim return true; 143287516Sdim if (isDerivedFromAtOffset(VTI->base_info[base].__base_type, 144287516Sdim Base, Offset - OffsetHere)) 145287516Sdim return true; 146287516Sdim } 147287516Sdim 148287516Sdim return false; 149287516Sdim} 150287516Sdim 151287516Sdim/// \brief Find the derived-most dynamic base class of \p Derived at offset 152287516Sdim/// \p Offset. 153287516Sdimstatic const abi::__class_type_info *findBaseAtOffset( 154287516Sdim const abi::__class_type_info *Derived, sptr Offset) { 155287516Sdim if (!Offset) 156287516Sdim return Derived; 157287516Sdim 158287516Sdim if (const abi::__si_class_type_info *SI = 159287516Sdim dynamic_cast<const abi::__si_class_type_info*>(Derived)) 160287516Sdim return findBaseAtOffset(SI->__base_type, Offset); 161287516Sdim 162287516Sdim const abi::__vmi_class_type_info *VTI = 163287516Sdim dynamic_cast<const abi::__vmi_class_type_info*>(Derived); 164287516Sdim if (!VTI) 165287516Sdim // No base class subobjects. 166287516Sdim return 0; 167287516Sdim 168287516Sdim for (unsigned int base = 0; base != VTI->base_count; ++base) { 169287516Sdim sptr OffsetHere = VTI->base_info[base].__offset_flags >> 170287516Sdim abi::__base_class_type_info::__offset_shift; 171287516Sdim if (VTI->base_info[base].__offset_flags & 172287516Sdim abi::__base_class_type_info::__virtual_mask) 173287516Sdim // FIXME: Can't handle virtual bases yet. 174287516Sdim continue; 175287516Sdim if (const abi::__class_type_info *Base = 176287516Sdim findBaseAtOffset(VTI->base_info[base].__base_type, 177287516Sdim Offset - OffsetHere)) 178287516Sdim return Base; 179287516Sdim } 180287516Sdim 181287516Sdim return 0; 182287516Sdim} 183287516Sdim 184287516Sdimnamespace { 185287516Sdim 186287516Sdimstruct VtablePrefix { 187287516Sdim /// The offset from the vptr to the start of the most-derived object. 188287516Sdim /// This will only be greater than zero in some virtual base class vtables 189287516Sdim /// used during object con-/destruction, and will usually be exactly zero. 190287516Sdim sptr Offset; 191287516Sdim /// The type_info object describing the most-derived class type. 192287516Sdim std::type_info *TypeInfo; 193287516Sdim}; 194287516SdimVtablePrefix *getVtablePrefix(void *Vtable) { 195287516Sdim VtablePrefix *Vptr = reinterpret_cast<VtablePrefix*>(Vtable); 196287516Sdim if (!Vptr) 197287516Sdim return 0; 198287516Sdim VtablePrefix *Prefix = Vptr - 1; 199287516Sdim if (!Prefix->TypeInfo) 200287516Sdim // This can't possibly be a valid vtable. 201287516Sdim return 0; 202287516Sdim return Prefix; 203287516Sdim} 204287516Sdim 205287516Sdim} 206287516Sdim 207287516Sdimbool __ubsan::checkDynamicType(void *Object, void *Type, HashValue Hash) { 208287516Sdim // A crash anywhere within this function probably means the vptr is corrupted. 209287516Sdim // FIXME: Perform these checks more cautiously. 210287516Sdim 211287516Sdim // Check whether this is something we've evicted from the cache. 212287516Sdim HashValue *Bucket = getTypeCacheHashTableBucket(Hash); 213287516Sdim if (*Bucket == Hash) { 214287516Sdim __ubsan_vptr_type_cache[Hash % VptrTypeCacheSize] = Hash; 215287516Sdim return true; 216287516Sdim } 217287516Sdim 218287516Sdim void *VtablePtr = *reinterpret_cast<void **>(Object); 219287516Sdim VtablePrefix *Vtable = getVtablePrefix(VtablePtr); 220287516Sdim if (!Vtable) 221287516Sdim return false; 222287516Sdim 223287516Sdim // Check that this is actually a type_info object for a class type. 224287516Sdim abi::__class_type_info *Derived = 225287516Sdim dynamic_cast<abi::__class_type_info*>(Vtable->TypeInfo); 226287516Sdim if (!Derived) 227287516Sdim return false; 228287516Sdim 229287516Sdim abi::__class_type_info *Base = (abi::__class_type_info*)Type; 230287516Sdim if (!isDerivedFromAtOffset(Derived, Base, -Vtable->Offset)) 231287516Sdim return false; 232287516Sdim 233287516Sdim // Success. Cache this result. 234287516Sdim __ubsan_vptr_type_cache[Hash % VptrTypeCacheSize] = Hash; 235287516Sdim *Bucket = Hash; 236287516Sdim return true; 237287516Sdim} 238287516Sdim 239287516Sdim__ubsan::DynamicTypeInfo 240287516Sdim__ubsan::getDynamicTypeInfoFromVtable(void *VtablePtr) { 241287516Sdim VtablePrefix *Vtable = getVtablePrefix(VtablePtr); 242287516Sdim if (!Vtable) 243287516Sdim return DynamicTypeInfo(0, 0, 0); 244287516Sdim const abi::__class_type_info *ObjectType = findBaseAtOffset( 245287516Sdim static_cast<const abi::__class_type_info*>(Vtable->TypeInfo), 246287516Sdim -Vtable->Offset); 247287516Sdim return DynamicTypeInfo(Vtable->TypeInfo->__type_name, -Vtable->Offset, 248287516Sdim ObjectType ? ObjectType->__type_name : "<unknown>"); 249287516Sdim} 250287516Sdim 251287516Sdim#endif // CAN_SANITIZE_UB && !SANITIZER_WINDOWS 252