libsanitizer/ubsan/ubsan_type_hash.cc

   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
  22 namespace std {
  23   class type_info {
  24   public:
  25     virtual ~type_info();
  26
  27     const char *__type_name;
  28   };
  29 }
  30
  31 namespace __cxxabiv1 {
  32
  33 /// Type info for classes with no bases, and base class for type info for
  34 /// classes with bases.
  35 class __class_type_info : public std::type_info {
  36   virtual ~__class_type_info();
  37 };
  38
  39 /// Type info for classes with simple single public inheritance.
  40 class __si_class_type_info : public __class_type_info {
  41 public:
  42   virtual ~__si_class_type_info();
  43
  44   const __class_type_info *__base_type;
  45 };
  46
  47 class __base_class_type_info {
  48 public:
  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.
  60 class __vmi_class_type_info : public __class_type_info {
  61 public:
  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
  71 namespace 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.
  92 static __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.
 116 static 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.
 154 static 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
 185 namespace {
 186
 187 struct VtablePrefix {
 188   /// The offset from the vptr to the start of the most-derived object.
 189   /// This should never be greater than zero, and will usually be exactly
 190   /// zero.
 191   sptr Offset;
 192   /// The type_info object describing the most-derived class type.
 193   std::type_info *TypeInfo;
 194 };
 195 VtablePrefix *getVtablePrefix(void *Object) {
 196   VtablePrefix **VptrPtr = reinterpret_cast<VtablePrefix**>(Object);
 197   if (!*VptrPtr)
 198     return 0;
 199   VtablePrefix *Prefix = *VptrPtr - 1;
 200   if (Prefix->Offset > 0 || !Prefix->TypeInfo)
 201     // This can't possibly be a valid vtable.
 202     return 0;
 203   return Prefix;
 204 }
 205
 206 }
 207
 208 bool __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 }