-fcatch-undefined-behavior checking for appropriate vptr value: library side.

git-svn-id: https://llvm.org/svn/llvm-project/compiler-rt/trunk@166660 91177308-0d34-0410-b5e6-96231b3b80d8

7 files changed, 397 insertions, 4 deletions

diff --git a/lib/ubsan/CMakeLists.txt b/lib/ubsan/CMakeLists.txt
index fa6393f84..616e0650c 100644
--- a/lib/ubsan/CMakeLists.txt
+++ b/lib/ubsan/CMakeLists.txt
@@ -3,6 +3,8 @@
 set(UBSAN_SOURCES
   ubsan_diag.cc
   ubsan_handlers.cc
+  ubsan_handlers_cxx.cc
+  ubsan_type_hash.cc
   ubsan_value.cc
   )
 
diff --git a/lib/ubsan/lit_tests/TypeCheck/vptr.cpp b/lib/ubsan/lit_tests/TypeCheck/vptr.cpp
new file mode 100644
index 000000000..c8e2820f1
--- /dev/null
+++ b/lib/ubsan/lit_tests/TypeCheck/vptr.cpp
@@ -0,0 +1,74 @@
+// RUN: %clang -ccc-cxx -fcatch-undefined-behavior %s -O3 -o %t
+// RUN: %t rT && %t mT && %t fT
+// RUN: %t rU && %t mU && %t fU
+// RUN: %t rS 2>&1 | FileCheck %s --check-prefix=CHECK-REFERENCE
+// RUN: %t mS 2>&1 | FileCheck %s --check-prefix=CHECK-MEMBER
+// RUN: %t fS 2>&1 | FileCheck %s --check-prefix=CHECK-MEMFUN
+// RUN: %t rV 2>&1 | FileCheck %s --check-prefix=CHECK-REFERENCE
+// RUN: %t mV 2>&1 | FileCheck %s --check-prefix=CHECK-MEMBER
+// RUN: %t fV 2>&1 | FileCheck %s --check-prefix=CHECK-MEMFUN
+
+struct S {
+  S() : a(0) {}
+  ~S() {}
+  int a;
+  int f() { return 0; }
+  virtual int v() { return 0; }
+};
+
+struct T : S {
+  T() : b(0) {}
+  int b;
+  int g() { return 0; }
+  virtual int v() { return 1; }
+};
+
+struct U : S, T { virtual int v() { return 2; } };
+
+int main(int, char **argv) {
+  T t;
+  (void)t.a;
+  (void)t.b;
+  (void)t.f();
+  (void)t.g();
+  (void)t.v();
+  (void)t.S::v();
+
+  U u;
+  (void)u.T::a;
+  (void)u.b;
+  (void)u.T::f();
+  (void)u.g();
+  (void)u.v();
+  (void)u.T::v();
+  (void)((T&)u).S::v();
+
+  T *p = 0;
+  switch (argv[1][1]) {
+  case 'S':
+    p = reinterpret_cast<T*>(new S);
+    break;
+  case 'T':
+    p = new T;
+    break;
+  case 'U':
+    p = new U;
+    break;
+  case 'V':
+    p = reinterpret_cast<T*>(new U);
+    break;
+  }
+
+  switch (argv[1][0]) {
+  case 'r':
+    // CHECK-REFERENCE: vptr.cpp:65:13: fatal error: reference binding to address 0x{{[0-9a-f]*}} which does not point to an object of type 'T'
+    {T &r = *p;}
+    break;
+  case 'm':
+    // CHECK-MEMBER: vptr.cpp:69:15: fatal error: member access within address 0x{{[0-9a-f]*}} which does not point to an object of type 'T'
+    return p->b;
+  case 'f':
+    // CHECK-MEMFUN: vptr.cpp:72:12: fatal error: member call on address 0x{{[0-9a-f]*}} which does not point to an object of type 'T'
+    return p->g();
+  }
+}
diff --git a/lib/ubsan/ubsan_handlers.cc b/lib/ubsan/ubsan_handlers.cc
index 2cb12c459..ae0f1f6c3 100644
--- a/lib/ubsan/ubsan_handlers.cc
+++ b/lib/ubsan/ubsan_handlers.cc
@@ -1,4 +1,4 @@
-//===-- ubsan_report.cc ---------------------------------------------------===//
+//===-- ubsan_handlers.cc -------------------------------------------------===//
 //
 //                     The LLVM Compiler Infrastructure
 //
@@ -31,12 +31,15 @@ NORETURN void __sanitizer::CheckFailed(const char *File, int Line,
   Die();
 }
 
-void __ubsan::__ubsan_handle_type_mismatch(TypeMismatchData *Data,
-                                           ValueHandle Pointer) {
+namespace __ubsan {
   const char *TypeCheckKinds[] = {
     "load of", "store to", "reference binding to", "member access within",
-    "member call on"
+    "member call on", "constructor call on"
   };
+}
+
+void __ubsan::__ubsan_handle_type_mismatch(TypeMismatchData *Data,
+                                           ValueHandle Pointer) {
   if (!Pointer)
     Diag(Data->Loc, "%0 null pointer of type %1")
       << TypeCheckKinds[Data->TypeCheckKind] << Data->Type;
diff --git a/lib/ubsan/ubsan_handlers_cxx.cc b/lib/ubsan/ubsan_handlers_cxx.cc
new file mode 100644
index 000000000..e0d3442e8
--- /dev/null
+++ b/lib/ubsan/ubsan_handlers_cxx.cc
@@ -0,0 +1,49 @@
+//===-- ubsan_handlers_cxx.cc ---------------------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// Error logging entry points for the UBSan runtime, which are only used for C++
+// compilations. This file is permitted to use language features which require
+// linking against a C++ ABI library.
+//
+//===----------------------------------------------------------------------===//
+
+#include "ubsan_handlers_cxx.h"
+#include "ubsan_diag.h"
+#include "ubsan_type_hash.h"
+
+#include "sanitizer_common/sanitizer_common.h"
+
+using namespace __sanitizer;
+using namespace __ubsan;
+
+namespace __ubsan {
+  extern const char *TypeCheckKinds[];
+}
+
+void __ubsan::__ubsan_handle_dynamic_type_cache_miss(
+  DynamicTypeCacheMissData *Data, ValueHandle Pointer, ValueHandle Hash) {
+  if (checkDynamicType((void*)Pointer, Data->TypeInfo, Hash))
+    // Just a cache miss. The type matches after all.
+    return;
+
+  Diag(Data->Loc, "%0 address %1 which does not point to an object of type %2")
+    << TypeCheckKinds[Data->TypeCheckKind] << (void*)Pointer << Data->Type;
+  // FIXME: If possible, say what type it actually points to. Produce a note
+  //        pointing out the vptr:
+  // lib/VMCore/Instructions.cpp:2020:10: fatal error: member call on address
+  //       0xb7a4440 which does not point to an object of type
+  //       'llvm::OverflowingBinaryOperator'
+  //   return cast<OverflowingBinaryOperator>(this)->hasNoSignedWrap();
+  //                                               ^
+  // 0xb7a4440: note: object is of type 'llvm::BinaryOperator'
+  //   00 00 00 00  e0 f7 c5 09 00 00 00 00  20 00 00 00
+  //                ^~~~~~~~~~~
+  //                vptr for 'llvm::BinaryOperator'
+  Die();
+}
diff --git a/lib/ubsan/ubsan_handlers_cxx.h b/lib/ubsan/ubsan_handlers_cxx.h
new file mode 100644
index 000000000..8192e6527
--- /dev/null
+++ b/lib/ubsan/ubsan_handlers_cxx.h
@@ -0,0 +1,36 @@
+//===-- ubsan_handlers_cxx.h ------------------------------------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// Entry points to the runtime library for Clang's undefined behavior sanitizer,
+// for C++-specific checks. This code is not linked into C binaries.
+//
+//===----------------------------------------------------------------------===//
+#ifndef UBSAN_HANDLERS_CXX_H
+#define UBSAN_HANDLERS_CXX_H
+
+#include "ubsan_value.h"
+
+namespace __ubsan {
+
+struct DynamicTypeCacheMissData {
+  SourceLocation Loc;
+  const TypeDescriptor &Type;
+  void *TypeInfo;
+  unsigned char TypeCheckKind;
+};
+
+/// \brief Handle a runtime type check failure, caused by an incorrect vptr.
+/// When this handler is called, all we know is that the type was not in the
+/// cache; this does not necessarily imply the existence of a bug.
+extern "C" void __ubsan_handle_dynamic_type_cache_miss(
+  DynamicTypeCacheMissData *Data, ValueHandle Pointer, ValueHandle Hash);
+
+}
+
+#endif // UBSAN_HANDLERS_H
diff --git a/lib/ubsan/ubsan_type_hash.cc b/lib/ubsan/ubsan_type_hash.cc
new file mode 100644
index 000000000..6d0443692
--- /dev/null
+++ b/lib/ubsan/ubsan_type_hash.cc
@@ -0,0 +1,200 @@
+//===-- ubsan_type_hash.cc ------------------------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// Implementation of a hash table for fast checking of inheritance
+// relationships. This file is only linked into C++ compilations, and is
+// permitted to use language features which require a C++ ABI library.
+//
+//===----------------------------------------------------------------------===//
+
+#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();
+  private:
+    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 {
+  virtual ~__class_type_info();
+};
+
+/// Type info for classes with simple single public inheritance.
+class __si_class_type_info : public __class_type_info {
+public:
+  virtual ~__si_class_type_info();
+
+  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:
+  virtual ~__vmi_class_type_info();
+
+  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
+//        (worst-case, we could miss a bug or see a slowdown) but we should
+//        avoid upsetting race detectors.
+
+// Find a bucket to store the given value in.
+static __ubsan::HashValue *getTypeCacheHashTableBucket(__ubsan::HashValue V) {
+  static const unsigned HashTableSize = 65537;
+  static __ubsan::HashValue __ubsan_vptr_hash_set[HashTableSize] = { 1 };
+
+  unsigned Probe = V & 65535;
+  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[V];
+}
+
+// A cache of recently-checked hashes. Mini hash table with "random" evictions.
+// The bottom 7 bits of the hash are used as the key.
+static const unsigned CacheSize = 128;
+extern "C" __ubsan::HashValue __ubsan_vptr_type_cache[CacheSize] = { 1 };
+
+/// \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 == Base)
+    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 zero-offset base class which is derived from \p Base.
+  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;
+}
+
+namespace {
+
+struct VtablePrefix {
+  /// The offset from the vptr to the start of the most-derived object.
+  /// This should never be greater than zero, 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 *Object) {
+  VtablePrefix **Ptr = reinterpret_cast<VtablePrefix**>(Object);
+  return *Ptr - 1;
+}
+
+}
+
+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 % CacheSize] = Hash;
+    return true;
+  }
+
+  VtablePrefix *Vtable = getVtablePrefix(Object);
+  if (Vtable + 1 == 0 || Vtable->Offset > 0)
+    // This can't possibly be a valid 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 % CacheSize] = Hash;
+  *Bucket = Hash;
+  return true;
+}
diff --git a/lib/ubsan/ubsan_type_hash.h b/lib/ubsan/ubsan_type_hash.h
new file mode 100644
index 000000000..982ebdfbc
--- /dev/null
+++ b/lib/ubsan/ubsan_type_hash.h
@@ -0,0 +1,29 @@
+//===-- ubsan_type_hash.h ---------------------------------------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// Hashing of types for Clang's undefined behavior checker.
+//
+//===----------------------------------------------------------------------===//
+#ifndef UBSAN_TYPE_HASH_H
+#define UBSAN_TYPE_HASH_H
+
+#include "sanitizer_common/sanitizer_common.h"
+
+namespace __ubsan {
+
+typedef uptr HashValue;
+
+/// \brief Check whether the dynamic type of \p Object has a \p Type subobject
+/// at offset 0.
+/// \return \c true if the type matches, \c false if not.
+bool checkDynamicType(void *Object, void *Type, HashValue CacheSlot);
+
+} // namespace __ubsan
+
+#endif // UBSAN_TYPE_HASH_H