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