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