contrib/compiler-rt/lib/ubsan/ubsan_type_hash.cc

   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(sptr Object,
 119                                   const abi::__class_type_info *Derived,
 120                                   const abi::__class_type_info *Base,
 121                                   sptr Offset) {
 122   if (Derived->__type_name == Base->__type_name)
 123     return Offset == 0;
 124
 125   if (const abi::__si_class_type_info *SI =
 126         dynamic_cast<const abi::__si_class_type_info*>(Derived))
 127     return isDerivedFromAtOffset(Object, SI->__base_type, Base, Offset);
 128
 129   const abi::__vmi_class_type_info *VTI =
 130     dynamic_cast<const abi::__vmi_class_type_info*>(Derived);
 131   if (!VTI)
 132     // No base class subobjects.
 133     return false;
 134
 135   // Look for a base class which is derived from \p Base at the right offset.
 136   for (unsigned int base = 0; base != VTI->base_count; ++base) {
 137     // FIXME: Curtail the recursion if this base can't possibly contain the
 138     //        given offset.
 139     sptr OffsetHere = VTI->base_info[base].__offset_flags >>
 140                       abi::__base_class_type_info::__offset_shift;
 141     if (VTI->base_info[base].__offset_flags &
 142           abi::__base_class_type_info::__virtual_mask) {
 143       sptr VTable = *reinterpret_cast<const sptr *>(Object);
 144       OffsetHere = *reinterpret_cast<const sptr *>(VTable + OffsetHere);
 145     }
 146     if (isDerivedFromAtOffset(Object + OffsetHere,
 147                               VTI->base_info[base].__base_type, Base,
 148                               Offset - OffsetHere))
 149       return true;
 150   }
 151
 152   return false;
 153 }
 154
 155 /// \brief Find the derived-most dynamic base class of \p Derived at offset
 156 /// \p Offset.
 157 static const abi::__class_type_info *
 158 findBaseAtOffset(sptr Object, const abi::__class_type_info *Derived,
 159                  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(Object, 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       sptr VTable = *reinterpret_cast<const sptr *>(Object);
 179       OffsetHere = *reinterpret_cast<const sptr *>(VTable + OffsetHere);
 180     }
 181     if (const abi::__class_type_info *Base = findBaseAtOffset(
 182             Object + OffsetHere, VTI->base_info[base].__base_type,
 183             Offset - OffsetHere))
 184       return Base;
 185   }
 186
 187   return 0;
 188 }
 189
 190 namespace {
 191
 192 struct VtablePrefix {
 193   /// The offset from the vptr to the start of the most-derived object.
 194   /// This should never be greater than zero, and will usually be exactly
 195   /// zero.
 196   sptr Offset;
 197   /// The type_info object describing the most-derived class type.
 198   std::type_info *TypeInfo;
 199 };
 200 VtablePrefix *getVtablePrefix(void *Object) {
 201   VtablePrefix **VptrPtr = reinterpret_cast<VtablePrefix**>(Object);
 202   if (!*VptrPtr)
 203     return 0;
 204   VtablePrefix *Prefix = *VptrPtr - 1;
 205   if (Prefix->Offset > 0 || !Prefix->TypeInfo)
 206     // This can't possibly be a valid vtable.
 207     return 0;
 208   return Prefix;
 209 }
 210
 211 }
 212
 213 bool __ubsan::checkDynamicType(void *Object, void *Type, HashValue Hash) {
 214   // A crash anywhere within this function probably means the vptr is corrupted.
 215   // FIXME: Perform these checks more cautiously.
 216
 217   // Check whether this is something we've evicted from the cache.
 218   HashValue *Bucket = getTypeCacheHashTableBucket(Hash);
 219   if (*Bucket == Hash) {
 220     __ubsan_vptr_type_cache[Hash % VptrTypeCacheSize] = Hash;
 221     return true;
 222   }
 223
 224   VtablePrefix *Vtable = getVtablePrefix(Object);
 225   if (!Vtable)
 226     return false;
 227
 228   // Check that this is actually a type_info object for a class type.
 229   abi::__class_type_info *Derived =
 230     dynamic_cast<abi::__class_type_info*>(Vtable->TypeInfo);
 231   if (!Derived)
 232     return false;
 233
 234   abi::__class_type_info *Base = (abi::__class_type_info*)Type;
 235   if (!isDerivedFromAtOffset(reinterpret_cast<sptr>(Object), Derived, Base,
 236                              -Vtable->Offset))
 237     return false;
 238
 239   // Success. Cache this result.
 240   __ubsan_vptr_type_cache[Hash % VptrTypeCacheSize] = Hash;
 241   *Bucket = Hash;
 242   return true;
 243 }
 244
 245 __ubsan::DynamicTypeInfo __ubsan::getDynamicTypeInfo(void *Object) {
 246   VtablePrefix *Vtable = getVtablePrefix(Object);
 247   if (!Vtable)
 248     return DynamicTypeInfo(0, 0, 0);
 249   const abi::__class_type_info *ObjectType = findBaseAtOffset(
 250       reinterpret_cast<sptr>(Object),
 251       static_cast<const abi::__class_type_info *>(Vtable->TypeInfo),
 252       -Vtable->Offset);
 253   return DynamicTypeInfo(Vtable->TypeInfo->__type_name, -Vtable->Offset,
 254                          ObjectType ? ObjectType->__type_name : "<unknown>");
 255 }