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