1 //===-- ubsan_type_hash_itanium.cc ----------------------------------------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // Implementation of type hashing/lookup for Itanium C++ ABI.
12 //===----------------------------------------------------------------------===//
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"
19 #include "sanitizer_common/sanitizer_common.h"
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.
30 const char *__type_name;
34 namespace __cxxabiv1 {
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;
42 /// Type info for classes with simple single public inheritance.
43 class __si_class_type_info : public __class_type_info {
45 ~__si_class_type_info() override;
47 const __class_type_info *__base_type;
50 class __base_class_type_info {
52 const __class_type_info *__base_type;
55 enum __offset_flags_masks {
62 /// Type info for classes with multiple, virtual, or non-public inheritance.
63 class __vmi_class_type_info : public __class_type_info {
65 ~__vmi_class_type_info() override;
68 unsigned int base_count;
69 __base_class_type_info base_info[1];
74 namespace abi = __cxxabiv1;
76 using namespace __sanitizer;
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
84 // * the vptr, and thus the hash, can be affected by ASLR, so multiple runs
85 // give better coverage.
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.
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.
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];
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;
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];
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,
120 if (Derived->__type_name == Base->__type_name ||
121 (SANITIZER_NON_UNIQUE_TYPEINFO &&
122 !internal_strcmp(Derived->__type_name, Base->__type_name)))
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);
129 const abi::__vmi_class_type_info *VTI =
130 dynamic_cast<const abi::__vmi_class_type_info*>(Derived);
132 // No base class subobjects.
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
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.
147 if (isDerivedFromAtOffset(VTI->base_info[base].__base_type,
148 Base, Offset - OffsetHere))
155 /// \brief Find the derived-most dynamic base class of \p Derived at offset
157 static const abi::__class_type_info *findBaseAtOffset(
158 const abi::__class_type_info *Derived, sptr Offset) {
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);
166 const abi::__vmi_class_type_info *VTI =
167 dynamic_cast<const abi::__vmi_class_type_info*>(Derived);
169 // No base class subobjects.
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.
179 if (const abi::__class_type_info *Base =
180 findBaseAtOffset(VTI->base_info[base].__base_type,
181 Offset - OffsetHere))
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.
195 /// The type_info object describing the most-derived class type.
196 std::type_info *TypeInfo;
198 VtablePrefix *getVtablePrefix(void *Vtable) {
199 VtablePrefix *Vptr = reinterpret_cast<VtablePrefix*>(Vtable);
200 VtablePrefix *Prefix = Vptr - 1;
201 if (!IsAccessibleMemoryRange((uptr)Prefix, sizeof(VtablePrefix)))
203 if (!Prefix->TypeInfo)
204 // This can't possibly be a valid vtable.
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.
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;
222 void *VtablePtr = *reinterpret_cast<void **>(Object);
223 VtablePrefix *Vtable = getVtablePrefix(VtablePtr);
226 if (Vtable->Offset < -VptrMaxOffsetToTop || Vtable->Offset > VptrMaxOffsetToTop) {
227 // Too large or too small offset are signs of Vtable corruption.
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);
237 abi::__class_type_info *Base = (abi::__class_type_info*)Type;
238 if (!isDerivedFromAtOffset(Derived, Base, -Vtable->Offset))
241 // Success. Cache this result.
242 __ubsan_vptr_type_cache[Hash % VptrTypeCacheSize] = Hash;
247 __ubsan::DynamicTypeInfo
248 __ubsan::getDynamicTypeInfoFromVtable(void *VtablePtr) {
249 VtablePrefix *Vtable = getVtablePrefix(VtablePtr);
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),
257 return DynamicTypeInfo(Vtable->TypeInfo->__type_name, -Vtable->Offset,
258 ObjectType ? ObjectType->__type_name : "<unknown>");
261 #endif // CAN_SANITIZE_UB && !SANITIZER_WINDOWS