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