aboutsummaryrefslogtreecommitdiff
path: root/lib/ubsan/ubsan_type_hash_itanium.cc
diff options
context:
space:
mode:
Diffstat (limited to 'lib/ubsan/ubsan_type_hash_itanium.cc')
-rw-r--r--lib/ubsan/ubsan_type_hash_itanium.cc251
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