libsanitizer/ubsan/ubsan_type_hash_itanium.cc

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