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