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

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