1 //===-- ubsan_type_hash.cc ------------------------------------------------===//
3 // This file is distributed under the University of Illinois Open Source
4 // License. See LICENSE.TXT for details.
6 //===----------------------------------------------------------------------===//
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.
12 //===----------------------------------------------------------------------===//
14 #include "ubsan_type_hash.h"
16 #include "sanitizer_common/sanitizer_common.h"
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.
27 const char *__type_name
;
31 namespace __cxxabiv1
{
33 /// Type info for classes with no bases, and base class for type info for
34 /// classes with bases.
35 class __class_type_info
: public std::type_info
{
36 virtual ~__class_type_info();
39 /// Type info for classes with simple single public inheritance.
40 class __si_class_type_info
: public __class_type_info
{
42 virtual ~__si_class_type_info();
44 const __class_type_info
*__base_type
;
47 class __base_class_type_info
{
49 const __class_type_info
*__base_type
;
52 enum __offset_flags_masks
{
59 /// Type info for classes with multiple, virtual, or non-public inheritance.
60 class __vmi_class_type_info
: public __class_type_info
{
62 virtual ~__vmi_class_type_info();
65 unsigned int base_count
;
66 __base_class_type_info base_info
[1];
71 namespace abi
= __cxxabiv1
;
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
79 // * the vptr, and thus the hash, can be affected by ASLR, so multiple runs
80 // give better coverage.
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.
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.
91 /// Find a bucket to store the given hash value in.
92 static __ubsan::HashValue
*getTypeCacheHashTableBucket(__ubsan::HashValue V
) {
93 static const unsigned HashTableSize
= 65537;
94 static __ubsan::HashValue __ubsan_vptr_hash_set
[HashTableSize
];
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
;
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
];
110 /// A cache of recently-checked hashes. Mini hash table with "random" evictions.
112 __ubsan::__ubsan_vptr_type_cache
[__ubsan::VptrTypeCacheSize
];
114 /// \brief Determine whether \p Derived has a \p Base base class subobject at
115 /// offset \p Offset.
116 static bool isDerivedFromAtOffset(const abi::__class_type_info
*Derived
,
117 const abi::__class_type_info
*Base
,
119 if (Derived
->__type_name
== Base
->__type_name
)
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
);
126 const abi::__vmi_class_type_info
*VTI
=
127 dynamic_cast<const abi::__vmi_class_type_info
*>(Derived
);
129 // No base class subobjects.
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
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.
144 if (isDerivedFromAtOffset(VTI
->base_info
[base
].__base_type
,
145 Base
, Offset
- OffsetHere
))
152 /// \brief Find the derived-most dynamic base class of \p Derived at offset
154 static const abi::__class_type_info
*findBaseAtOffset(
155 const abi::__class_type_info
*Derived
, sptr Offset
) {
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
);
163 const abi::__vmi_class_type_info
*VTI
=
164 dynamic_cast<const abi::__vmi_class_type_info
*>(Derived
);
166 // No base class subobjects.
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.
176 if (const abi::__class_type_info
*Base
=
177 findBaseAtOffset(VTI
->base_info
[base
].__base_type
,
178 Offset
- OffsetHere
))
187 struct 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.
192 /// The type_info object describing the most-derived class type.
193 std::type_info
*TypeInfo
;
195 VtablePrefix
*getVtablePrefix(void *Object
) {
196 VtablePrefix
**VptrPtr
= reinterpret_cast<VtablePrefix
**>(Object
);
199 VtablePrefix
*Prefix
= *VptrPtr
- 1;
200 if (!Prefix
->TypeInfo
)
201 // This can't possibly be a valid vtable.
208 bool __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.
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
;
219 VtablePrefix
*Vtable
= getVtablePrefix(Object
);
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
);
229 abi::__class_type_info
*Base
= (abi::__class_type_info
*)Type
;
230 if (!isDerivedFromAtOffset(Derived
, Base
, -Vtable
->Offset
))
233 // Success. Cache this result.
234 __ubsan_vptr_type_cache
[Hash
% VptrTypeCacheSize
] = Hash
;
239 __ubsan::DynamicTypeInfo
__ubsan::getDynamicTypeInfo(void *Object
) {
240 VtablePrefix
*Vtable
= getVtablePrefix(Object
);
242 return DynamicTypeInfo(0, 0, 0);
243 const abi::__class_type_info
*ObjectType
= findBaseAtOffset(
244 static_cast<const abi::__class_type_info
*>(Vtable
->TypeInfo
),
246 return DynamicTypeInfo(Vtable
->TypeInfo
->__type_name
, -Vtable
->Offset
,
247 ObjectType
? ObjectType
->__type_name
: "<unknown>");