1 //===-- ubsan_type_hash_itanium.cc ----------------------------------------===//
3 // This file is distributed under the University of Illinois Open Source
4 // License. See LICENSE.TXT for details.
6 //===----------------------------------------------------------------------===//
8 // Implementation of type hashing/lookup for Itanium C++ ABI.
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.
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
{
43 ~__si_class_type_info() override
;
45 const __class_type_info
*__base_type
;
48 class __base_class_type_info
{
50 const __class_type_info
*__base_type
;
53 enum __offset_flags_masks
{
60 /// Type info for classes with multiple, virtual, or non-public inheritance.
61 class __vmi_class_type_info
: public __class_type_info
{
63 ~__vmi_class_type_info() override
;
66 unsigned int base_count
;
67 __base_class_type_info base_info
[1];
72 namespace abi
= __cxxabiv1
;
74 using namespace __sanitizer
;
76 // We implement a simple two-level cache for type-checking results. For each
77 // (vptr,type) pair, a hash is computed. This hash is assumed to be globally
78 // unique; if it collides, we will get false negatives, but:
79 // * such a collision would have to occur on the *first* bad access,
80 // * the probability of such a collision is low (and for a 64-bit target, is
82 // * the vptr, and thus the hash, can be affected by ASLR, so multiple runs
83 // give better coverage.
85 // The first caching layer is a small hash table with no chaining; buckets are
86 // reused as needed. The second caching layer is a large hash table with open
87 // chaining. We can freely evict from either layer since this is just a cache.
89 // FIXME: Make these hash table accesses thread-safe. The races here are benign:
90 // assuming the unsequenced loads and stores don't misbehave too badly,
91 // the worst case is false negatives or poor cache behavior, not false
92 // positives or crashes.
94 /// Find a bucket to store the given hash value in.
95 static __ubsan::HashValue
*getTypeCacheHashTableBucket(__ubsan::HashValue V
) {
96 static const unsigned HashTableSize
= 65537;
97 static __ubsan::HashValue __ubsan_vptr_hash_set
[HashTableSize
];
99 unsigned First
= (V
& 65535) ^ 1;
100 unsigned Probe
= First
;
101 for (int Tries
= 5; Tries
; --Tries
) {
102 if (!__ubsan_vptr_hash_set
[Probe
] || __ubsan_vptr_hash_set
[Probe
] == V
)
103 return &__ubsan_vptr_hash_set
[Probe
];
104 Probe
+= ((V
>> 16) & 65535) + 1;
105 if (Probe
>= HashTableSize
)
106 Probe
-= HashTableSize
;
108 // FIXME: Pick a random entry from the probe sequence to evict rather than
109 // just taking the first.
110 return &__ubsan_vptr_hash_set
[First
];
113 /// \brief Determine whether \p Derived has a \p Base base class subobject at
114 /// offset \p Offset.
115 static bool isDerivedFromAtOffset(const abi::__class_type_info
*Derived
,
116 const abi::__class_type_info
*Base
,
118 if (Derived
->__type_name
== Base
->__type_name
||
119 (SANITIZER_NON_UNIQUE_TYPEINFO
&&
120 !internal_strcmp(Derived
->__type_name
, Base
->__type_name
)))
123 if (const abi::__si_class_type_info
*SI
=
124 dynamic_cast<const abi::__si_class_type_info
*>(Derived
))
125 return isDerivedFromAtOffset(SI
->__base_type
, Base
, Offset
);
127 const abi::__vmi_class_type_info
*VTI
=
128 dynamic_cast<const abi::__vmi_class_type_info
*>(Derived
);
130 // No base class subobjects.
133 // Look for a base class which is derived from \p Base at the right offset.
134 for (unsigned int base
= 0; base
!= VTI
->base_count
; ++base
) {
135 // FIXME: Curtail the recursion if this base can't possibly contain the
137 sptr OffsetHere
= VTI
->base_info
[base
].__offset_flags
>>
138 abi::__base_class_type_info::__offset_shift
;
139 if (VTI
->base_info
[base
].__offset_flags
&
140 abi::__base_class_type_info::__virtual_mask
)
141 // For now, just punt on virtual bases and say 'yes'.
142 // FIXME: OffsetHere is the offset in the vtable of the virtual base
143 // offset. Read the vbase offset out of the vtable and use it.
145 if (isDerivedFromAtOffset(VTI
->base_info
[base
].__base_type
,
146 Base
, Offset
- OffsetHere
))
153 /// \brief Find the derived-most dynamic base class of \p Derived at offset
155 static const abi::__class_type_info
*findBaseAtOffset(
156 const abi::__class_type_info
*Derived
, sptr Offset
) {
160 if (const abi::__si_class_type_info
*SI
=
161 dynamic_cast<const abi::__si_class_type_info
*>(Derived
))
162 return findBaseAtOffset(SI
->__base_type
, Offset
);
164 const abi::__vmi_class_type_info
*VTI
=
165 dynamic_cast<const abi::__vmi_class_type_info
*>(Derived
);
167 // No base class subobjects.
170 for (unsigned int base
= 0; base
!= VTI
->base_count
; ++base
) {
171 sptr OffsetHere
= VTI
->base_info
[base
].__offset_flags
>>
172 abi::__base_class_type_info::__offset_shift
;
173 if (VTI
->base_info
[base
].__offset_flags
&
174 abi::__base_class_type_info::__virtual_mask
)
175 // FIXME: Can't handle virtual bases yet.
177 if (const abi::__class_type_info
*Base
=
178 findBaseAtOffset(VTI
->base_info
[base
].__base_type
,
179 Offset
- OffsetHere
))
188 struct VtablePrefix
{
189 /// The offset from the vptr to the start of the most-derived object.
190 /// This will only be greater than zero in some virtual base class vtables
191 /// used during object con-/destruction, and will usually be exactly zero.
193 /// The type_info object describing the most-derived class type.
194 std::type_info
*TypeInfo
;
196 VtablePrefix
*getVtablePrefix(void *Vtable
) {
197 VtablePrefix
*Vptr
= reinterpret_cast<VtablePrefix
*>(Vtable
);
200 VtablePrefix
*Prefix
= Vptr
- 1;
201 if (!Prefix
->TypeInfo
)
202 // This can't possibly be a valid vtable.
209 bool __ubsan::checkDynamicType(void *Object
, void *Type
, HashValue Hash
) {
210 // A crash anywhere within this function probably means the vptr is corrupted.
211 // FIXME: Perform these checks more cautiously.
213 // Check whether this is something we've evicted from the cache.
214 HashValue
*Bucket
= getTypeCacheHashTableBucket(Hash
);
215 if (*Bucket
== Hash
) {
216 __ubsan_vptr_type_cache
[Hash
% VptrTypeCacheSize
] = Hash
;
220 void *VtablePtr
= *reinterpret_cast<void **>(Object
);
221 VtablePrefix
*Vtable
= getVtablePrefix(VtablePtr
);
224 if (Vtable
->Offset
< -VptrMaxOffsetToTop
|| Vtable
->Offset
> VptrMaxOffsetToTop
) {
225 // Too large or too small offset are signs of Vtable corruption.
229 // Check that this is actually a type_info object for a class type.
230 abi::__class_type_info
*Derived
=
231 dynamic_cast<abi::__class_type_info
*>(Vtable
->TypeInfo
);
235 abi::__class_type_info
*Base
= (abi::__class_type_info
*)Type
;
236 if (!isDerivedFromAtOffset(Derived
, Base
, -Vtable
->Offset
))
239 // Success. Cache this result.
240 __ubsan_vptr_type_cache
[Hash
% VptrTypeCacheSize
] = Hash
;
245 __ubsan::DynamicTypeInfo
246 __ubsan::getDynamicTypeInfoFromVtable(void *VtablePtr
) {
247 VtablePrefix
*Vtable
= getVtablePrefix(VtablePtr
);
249 return DynamicTypeInfo(nullptr, 0, nullptr);
250 if (Vtable
->Offset
< -VptrMaxOffsetToTop
|| Vtable
->Offset
> VptrMaxOffsetToTop
)
251 return DynamicTypeInfo(nullptr, Vtable
->Offset
, nullptr);
252 const abi::__class_type_info
*ObjectType
= findBaseAtOffset(
253 static_cast<const abi::__class_type_info
*>(Vtable
->TypeInfo
),
255 return DynamicTypeInfo(Vtable
->TypeInfo
->__type_name
, -Vtable
->Offset
,
256 ObjectType
? ObjectType
->__type_name
: "<unknown>");
259 #endif // CAN_SANITIZE_UB && !SANITIZER_WINDOWS