diff options
Diffstat (limited to 'lib/ubsan/ubsan_type_hash_itanium.cc')
-rw-r--r-- | lib/ubsan/ubsan_type_hash_itanium.cc | 251 |
1 files changed, 251 insertions, 0 deletions
diff --git a/lib/ubsan/ubsan_type_hash_itanium.cc b/lib/ubsan/ubsan_type_hash_itanium.cc new file mode 100644 index 000000000000..b84e88d4c71d --- /dev/null +++ b/lib/ubsan/ubsan_type_hash_itanium.cc @@ -0,0 +1,251 @@ +//===-- ubsan_type_hash_itanium.cc ----------------------------------------===// +// +// The LLVM Compiler Infrastructure +// +// 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; + +// 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) + 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 0; + + 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 0; +} + +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); + if (!Vptr) + return 0; + VtablePrefix *Prefix = Vptr - 1; + if (!Prefix->TypeInfo) + // This can't possibly be a valid vtable. + return 0; + 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; + + // 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(0, 0, 0); + 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 |