blob: 9df316e14be9b21316327b00e99faaafe8b2b66f [file] [log] [blame]
//===-- ubsan_type_hash_itanium.cc ----------------------------------------===//
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
// Implementation of type hashing/lookup for Itanium C++ ABI.
//
//===----------------------------------------------------------------------===//
#include "sanitizer_common/sanitizer_platform.h"
#include "ubsan_platform.h"
#if CAN_SANITIZE_UB && !SANITIZER_WINDOWS
#include "ubsan_type_hash.h"
#include "sanitizer_common/sanitizer_common.h"
// The following are intended to be binary compatible with the definitions
// given in the Itanium ABI. We make no attempt to be ODR-compatible with
// those definitions, since existing ABI implementations aren't.
namespace std {
class type_info {
public:
virtual ~type_info();
const char *__type_name;
};
}
namespace __cxxabiv1 {
/// Type info for classes with no bases, and base class for type info for
/// classes with bases.
class __class_type_info : public std::type_info {
~__class_type_info() override;
};
/// Type info for classes with simple single public inheritance.
class __si_class_type_info : public __class_type_info {
public:
~__si_class_type_info() override;
const __class_type_info *__base_type;
};
class __base_class_type_info {
public:
const __class_type_info *__base_type;
long __offset_flags;
enum __offset_flags_masks {
__virtual_mask = 0x1,
__public_mask = 0x2,
__offset_shift = 8
};
};
/// Type info for classes with multiple, virtual, or non-public inheritance.
class __vmi_class_type_info : public __class_type_info {
public:
~__vmi_class_type_info() override;
unsigned int flags;
unsigned int base_count;
__base_class_type_info base_info[1];
};
}
namespace abi = __cxxabiv1;
using namespace __sanitizer;
// We implement a simple two-level cache for type-checking results. For each
// (vptr,type) pair, a hash is computed. This hash is assumed to be globally
// unique; if it collides, we will get false negatives, but:
// * such a collision would have to occur on the *first* bad access,
// * the probability of such a collision is low (and for a 64-bit target, is
// negligible), and
// * the vptr, and thus the hash, can be affected by ASLR, so multiple runs
// give better coverage.
//
// The first caching layer is a small hash table with no chaining; buckets are
// reused as needed. The second caching layer is a large hash table with open
// chaining. We can freely evict from either layer since this is just a cache.
//
// FIXME: Make these hash table accesses thread-safe. The races here are benign:
// assuming the unsequenced loads and stores don't misbehave too badly,
// the worst case is false negatives or poor cache behavior, not false
// positives or crashes.
/// Find a bucket to store the given hash value in.
static __ubsan::HashValue *getTypeCacheHashTableBucket(__ubsan::HashValue V) {
static const unsigned HashTableSize = 65537;
static __ubsan::HashValue __ubsan_vptr_hash_set[HashTableSize];
unsigned First = (V & 65535) ^ 1;
unsigned Probe = First;
for (int Tries = 5; Tries; --Tries) {
if (!__ubsan_vptr_hash_set[Probe] || __ubsan_vptr_hash_set[Probe] == V)
return &__ubsan_vptr_hash_set[Probe];
Probe += ((V >> 16) & 65535) + 1;
if (Probe >= HashTableSize)
Probe -= HashTableSize;
}
// FIXME: Pick a random entry from the probe sequence to evict rather than
// just taking the first.
return &__ubsan_vptr_hash_set[First];
}
/// \brief Determine whether \p Derived has a \p Base base class subobject at
/// offset \p Offset.
static bool isDerivedFromAtOffset(const abi::__class_type_info *Derived,
const abi::__class_type_info *Base,
sptr Offset) {
if (Derived->__type_name == Base->__type_name ||
(SANITIZER_NON_UNIQUE_TYPEINFO &&
!internal_strcmp(Derived->__type_name, Base->__type_name)))
return Offset == 0;
if (const abi::__si_class_type_info *SI =
dynamic_cast<const abi::__si_class_type_info*>(Derived))
return isDerivedFromAtOffset(SI->__base_type, Base, Offset);
const abi::__vmi_class_type_info *VTI =
dynamic_cast<const abi::__vmi_class_type_info*>(Derived);
if (!VTI)
// No base class subobjects.
return false;
// Look for a base class which is derived from \p Base at the right offset.
for (unsigned int base = 0; base != VTI->base_count; ++base) {
// FIXME: Curtail the recursion if this base can't possibly contain the
// given offset.
sptr OffsetHere = VTI->base_info[base].__offset_flags >>
abi::__base_class_type_info::__offset_shift;
if (VTI->base_info[base].__offset_flags &
abi::__base_class_type_info::__virtual_mask)
// For now, just punt on virtual bases and say 'yes'.
// FIXME: OffsetHere is the offset in the vtable of the virtual base
// offset. Read the vbase offset out of the vtable and use it.
return true;
if (isDerivedFromAtOffset(VTI->base_info[base].__base_type,
Base, Offset - OffsetHere))
return true;
}
return false;
}
/// \brief Find the derived-most dynamic base class of \p Derived at offset
/// \p Offset.
static const abi::__class_type_info *findBaseAtOffset(
const abi::__class_type_info *Derived, sptr Offset) {
if (!Offset)
return Derived;
if (const abi::__si_class_type_info *SI =
dynamic_cast<const abi::__si_class_type_info*>(Derived))
return findBaseAtOffset(SI->__base_type, Offset);
const abi::__vmi_class_type_info *VTI =
dynamic_cast<const abi::__vmi_class_type_info*>(Derived);
if (!VTI)
// No base class subobjects.
return nullptr;
for (unsigned int base = 0; base != VTI->base_count; ++base) {
sptr OffsetHere = VTI->base_info[base].__offset_flags >>
abi::__base_class_type_info::__offset_shift;
if (VTI->base_info[base].__offset_flags &
abi::__base_class_type_info::__virtual_mask)
// FIXME: Can't handle virtual bases yet.
continue;
if (const abi::__class_type_info *Base =
findBaseAtOffset(VTI->base_info[base].__base_type,
Offset - OffsetHere))
return Base;
}
return nullptr;
}
namespace {
struct VtablePrefix {
/// The offset from the vptr to the start of the most-derived object.
/// This will only be greater than zero in some virtual base class vtables
/// used during object con-/destruction, and will usually be exactly zero.
sptr Offset;
/// The type_info object describing the most-derived class type.
std::type_info *TypeInfo;
};
VtablePrefix *getVtablePrefix(void *Vtable) {
VtablePrefix *Vptr = reinterpret_cast<VtablePrefix*>(Vtable);
VtablePrefix *Prefix = Vptr - 1;
if (!IsAccessibleMemoryRange((uptr)Prefix, sizeof(VtablePrefix)))
return nullptr;
if (!Prefix->TypeInfo)
// This can't possibly be a valid vtable.
return nullptr;
return Prefix;
}
}
bool __ubsan::checkDynamicType(void *Object, void *Type, HashValue Hash) {
// A crash anywhere within this function probably means the vptr is corrupted.
// FIXME: Perform these checks more cautiously.
// Check whether this is something we've evicted from the cache.
HashValue *Bucket = getTypeCacheHashTableBucket(Hash);
if (*Bucket == Hash) {
__ubsan_vptr_type_cache[Hash % VptrTypeCacheSize] = Hash;
return true;
}
void *VtablePtr = *reinterpret_cast<void **>(Object);
VtablePrefix *Vtable = getVtablePrefix(VtablePtr);
if (!Vtable)
return false;
if (Vtable->Offset < -VptrMaxOffsetToTop || Vtable->Offset > VptrMaxOffsetToTop) {
// Too large or too small offset are signs of Vtable corruption.
return false;
}
// Check that this is actually a type_info object for a class type.
abi::__class_type_info *Derived =
dynamic_cast<abi::__class_type_info*>(Vtable->TypeInfo);
if (!Derived)
return false;
abi::__class_type_info *Base = (abi::__class_type_info*)Type;
if (!isDerivedFromAtOffset(Derived, Base, -Vtable->Offset))
return false;
// Success. Cache this result.
__ubsan_vptr_type_cache[Hash % VptrTypeCacheSize] = Hash;
*Bucket = Hash;
return true;
}
__ubsan::DynamicTypeInfo
__ubsan::getDynamicTypeInfoFromVtable(void *VtablePtr) {
VtablePrefix *Vtable = getVtablePrefix(VtablePtr);
if (!Vtable)
return DynamicTypeInfo(nullptr, 0, nullptr);
if (Vtable->Offset < -VptrMaxOffsetToTop || Vtable->Offset > VptrMaxOffsetToTop)
return DynamicTypeInfo(nullptr, Vtable->Offset, nullptr);
const abi::__class_type_info *ObjectType = findBaseAtOffset(
static_cast<const abi::__class_type_info*>(Vtable->TypeInfo),
-Vtable->Offset);
return DynamicTypeInfo(Vtable->TypeInfo->__type_name, -Vtable->Offset,
ObjectType ? ObjectType->__type_name : "<unknown>");
}
#endif // CAN_SANITIZE_UB && !SANITIZER_WINDOWS