ubsan_type_hash.cc revision eda8bd0fc07df35c9ad7de5b698bb717b063e7af
15c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)//===-- ubsan_type_hash.cc ------------------------------------------------===// 219cde67944066db31e633d9e386f2aa9bf9fadb3Torne (Richard Coles)// 35c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)// The LLVM Compiler Infrastructure 45c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)// 55c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)// This file is distributed under the University of Illinois Open Source 65c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)// License. See LICENSE.TXT for details. 75c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)// 85c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)//===----------------------------------------------------------------------===// 95c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)// 105c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)// Implementation of a hash table for fast checking of inheritance 115c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)// relationships. This file is only linked into C++ compilations, and is 125c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)// permitted to use language features which require a C++ ABI library. 135c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)// 145c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)//===----------------------------------------------------------------------===// 155c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 165c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#include "ubsan_type_hash.h" 175c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 185c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#include "sanitizer_common/sanitizer_common.h" 195c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 205c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)// The following are intended to be binary compatible with the definitions 215c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)// given in the Itanium ABI. We make no attempt to be ODR-compatible with 225c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)// those definitions, since existing ABI implementations aren't. 235c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 245c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)namespace std { 255c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) class type_info { 265c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) public: 275c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) virtual ~type_info(); 285c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) private: 295c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) const char *__type_name; 305c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) }; 3119cde67944066db31e633d9e386f2aa9bf9fadb3Torne (Richard Coles)} 327242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci 335c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)namespace __cxxabiv1 { 34c1847b1379d12d0e05df27436bf19a9b1bf12deaTorne (Richard Coles) 355c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)/// Type info for classes with no bases, and base class for type info for 3619cde67944066db31e633d9e386f2aa9bf9fadb3Torne (Richard Coles)/// classes with bases. 3719cde67944066db31e633d9e386f2aa9bf9fadb3Torne (Richard Coles)class __class_type_info : public std::type_info { 3819cde67944066db31e633d9e386f2aa9bf9fadb3Torne (Richard Coles) virtual ~__class_type_info(); 395c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)}; 40c1847b1379d12d0e05df27436bf19a9b1bf12deaTorne (Richard Coles) 41/// Type info for classes with simple single public inheritance. 42class __si_class_type_info : public __class_type_info { 43public: 44 virtual ~__si_class_type_info(); 45 46 const __class_type_info *__base_type; 47}; 48 49class __base_class_type_info { 50public: 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. 62class __vmi_class_type_info : public __class_type_info { 63public: 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 73namespace 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// (worst-case, we could miss a bug or see a slowdown) but we should 90// avoid upsetting race detectors. 91 92// Find a bucket to store the given value in. 93static __ubsan::HashValue *getTypeCacheHashTableBucket(__ubsan::HashValue V) { 94 static const unsigned HashTableSize = 65537; 95 static __ubsan::HashValue __ubsan_vptr_hash_set[HashTableSize] = { 1 }; 96 97 unsigned Probe = V & 65535; 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[V]; 108} 109 110// A cache of recently-checked hashes. Mini hash table with "random" evictions. 111// The bottom 7 bits of the hash are used as the key. 112static const unsigned CacheSize = 128; 113extern "C" __ubsan::HashValue __ubsan_vptr_type_cache[CacheSize] = { 1 }; 114 115/// \brief Determine whether \p Derived has a \p Base base class subobject at 116/// offset \p Offset. 117static bool isDerivedFromAtOffset(const abi::__class_type_info *Derived, 118 const abi::__class_type_info *Base, 119 sptr Offset) { 120 if (Derived == Base) 121 return Offset == 0; 122 123 if (const abi::__si_class_type_info *SI = 124 dynamic_cast<const abi::__si_class_type_info*>(Derived)) 125 return isDerivedFromAtOffset(SI->__base_type, Base, Offset); 126 127 const abi::__vmi_class_type_info *VTI = 128 dynamic_cast<const abi::__vmi_class_type_info*>(Derived); 129 if (!VTI) 130 // No base class subobjects. 131 return false; 132 133 // Look for a zero-offset base class which is derived from \p Base. 134 for (unsigned int base = 0; base != VTI->base_count; ++base) { 135 // FIXME: Curtail the recursion if this base can't possibly contain the 136 // given offset. 137 sptr OffsetHere = VTI->base_info[base].__offset_flags >> 138 abi::__base_class_type_info::__offset_shift; 139 if (VTI->base_info[base].__offset_flags & 140 abi::__base_class_type_info::__virtual_mask) 141 // For now, just punt on virtual bases and say 'yes'. 142 // FIXME: OffsetHere is the offset in the vtable of the virtual base 143 // offset. Read the vbase offset out of the vtable and use it. 144 return true; 145 if (isDerivedFromAtOffset(VTI->base_info[base].__base_type, 146 Base, Offset - OffsetHere)) 147 return true; 148 } 149 150 return false; 151} 152 153namespace { 154 155struct VtablePrefix { 156 /// The offset from the vptr to the start of the most-derived object. 157 /// This should never be greater than zero, and will usually be exactly 158 /// zero. 159 sptr Offset; 160 /// The type_info object describing the most-derived class type. 161 std::type_info *TypeInfo; 162}; 163VtablePrefix *getVtablePrefix(void *Object) { 164 VtablePrefix **Ptr = reinterpret_cast<VtablePrefix**>(Object); 165 return *Ptr - 1; 166} 167 168} 169 170bool __ubsan::checkDynamicType(void *Object, void *Type, HashValue Hash) { 171 // A crash anywhere within this function probably means the vptr is corrupted. 172 // FIXME: Perform these checks more cautiously. 173 174 // Check whether this is something we've evicted from the cache. 175 HashValue *Bucket = getTypeCacheHashTableBucket(Hash); 176 if (*Bucket == Hash) { 177 __ubsan_vptr_type_cache[Hash % CacheSize] = Hash; 178 return true; 179 } 180 181 VtablePrefix *Vtable = getVtablePrefix(Object); 182 if (Vtable + 1 == 0 || Vtable->Offset > 0) 183 // This can't possibly be a valid vtable. 184 return false; 185 186 // Check that this is actually a type_info object for a class type. 187 abi::__class_type_info *Derived = 188 dynamic_cast<abi::__class_type_info*>(Vtable->TypeInfo); 189 if (!Derived) 190 return false; 191 192 abi::__class_type_info *Base = (abi::__class_type_info*)Type; 193 if (!isDerivedFromAtOffset(Derived, Base, -Vtable->Offset)) 194 return false; 195 196 // Success. Cache this result. 197 __ubsan_vptr_type_cache[Hash % CacheSize] = Hash; 198 *Bucket = Hash; 199 return true; 200} 201