From 784545fba0e1fcbb5e12cde76d13d91fd0972323 Mon Sep 17 00:00:00 2001 From: Sanjoy Das Date: Thu, 26 Mar 2015 19:25:01 +0000 Subject: [PATCH] [ADT][CMake][AutoConf] Fail-fast iterators for DenseMap Summary: This patch is an attempt at making `DenseMapIterator`s "fail-fast". Fail-fast iterators that have been invalidated due to insertion into the host `DenseMap` deterministically trip an assert (in debug mode) on access, instead of non-deterministically hitting memory corruption issues. Enabling fail-fast iterators breaks the LLVM C++ ABI, so they are predicated on `LLVM_ENABLE_ABI_BREAKING_CHECKS`. `LLVM_ENABLE_ABI_BREAKING_CHECKS` by default flips with `LLVM_ENABLE_ASSERTS`, but can be clamped to ON or OFF using the CMake / autoconf build system. Reviewers: chandlerc, dexonsmith, rnk, zturner Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D8351 git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@233310 91177308-0d34-0410-b5e6-96231b3b80d8 --- CMakeLists.txt | 3 + autoconf/configure.ac | 16 ++++ cmake/modules/HandleLLVMOptions.cmake | 14 ++++ configure | 31 ++++++++ docs/CMake.rst | 9 +++ docs/ProgrammersManual.rst | 16 ++++ include/llvm/ADT/DenseMap.h | 63 +++++++++++----- include/llvm/ADT/EpochTracker.h | 99 +++++++++++++++++++++++++ include/llvm/Config/config.h.in | 3 + include/llvm/Config/llvm-config.h.cmake | 4 + include/llvm/Config/llvm-config.h.in | 3 + 11 files changed, 241 insertions(+), 20 deletions(-) create mode 100644 include/llvm/ADT/EpochTracker.h diff --git a/CMakeLists.txt b/CMakeLists.txt index bef66ec4774..be78ac26f08 100644 --- a/CMakeLists.txt +++ b/CMakeLists.txt @@ -252,6 +252,9 @@ else() option(LLVM_ENABLE_ASSERTIONS "Enable assertions" ON) endif() +set(LLVM_ABI_BREAKING_CHECKS "WITH_ASSERTS" CACHE STRING + "Enable abi-breaking checks. Can be WITH_ASSERTS, FORCE_ON or FORCE_OFF.") + option(LLVM_FORCE_USE_OLD_HOST_TOOLCHAIN "Set to ON to force using an old, unsupported host toolchain." OFF) diff --git a/autoconf/configure.ac b/autoconf/configure.ac index 4d70acdf80a..9617543e477 100644 --- a/autoconf/configure.ac +++ b/autoconf/configure.ac @@ -701,8 +701,10 @@ AC_ARG_ENABLE(assertions,AS_HELP_STRING( --enable-assertions,[Compile with assertion checks enabled (default is YES)]),, enableval="yes") if test ${enableval} = "yes" ; then AC_SUBST(DISABLE_ASSERTIONS,[[]]) + assertions_enabled="yes" else AC_SUBST(DISABLE_ASSERTIONS,[[DISABLE_ASSERTIONS=1]]) + assertions_enabled="no" fi dnl --enable-werror : check whether we want Werror on by default @@ -726,6 +728,20 @@ else AC_SUBST(EXPENSIVE_CHECKS,[[no]]) fi +dnl --enable-abi-breaking-checks : decide whether we should compile in asserts and +dnl checks that make the build ABI incompatible with an llvm built without these +dnl checks enabled. +AC_ARG_ENABLE(abi-breaking-checks,AS_HELP_STRING( + --enable-abi-breaking-checks,[Compile with abi-breaking asserts support (default is with-asserts)]),, enableval="with-asserts") +case "$enableval" in + with-asserts) if test ${assertions_enabled} = "yes" ; then + AC_DEFINE([LLVM_ENABLE_ABI_BREAKING_CHECKS],[1],[Define to enable checks that alter the LLVM C++ ABI]) + fi ;; + yes) AC_DEFINE([LLVM_ENABLE_ABI_BREAKING_CHECKS],[1],[Define to enable checks that alter the LLVM C++ ABI]) ;; + no) ;; + *) AC_MSG_ERROR([Invalid setting for --enable-abi-breaking-checks. Use "with-asserts", "yes" or "no"]) +esac + dnl --enable-debug-runtime : should runtime libraries have debug symbols? AC_ARG_ENABLE(debug-runtime, AS_HELP_STRING(--enable-debug-runtime,[Build runtime libs with debug symbols (default is NO)]),,enableval=no) diff --git a/cmake/modules/HandleLLVMOptions.cmake b/cmake/modules/HandleLLVMOptions.cmake index 2878f4d2e6e..67f86a64526 100644 --- a/cmake/modules/HandleLLVMOptions.cmake +++ b/cmake/modules/HandleLLVMOptions.cmake @@ -78,6 +78,20 @@ if( LLVM_ENABLE_ASSERTIONS ) endif() endif() +string(TOUPPER "${LLVM_ABI_BREAKING_CHECKS}" uppercase_LLVM_ABI_BREAKING_CHECKS) + +if( uppercase_LLVM_ABI_BREAKING_CHECKS STREQUAL "WITH_ASSERTS" ) + if( LLVM_ENABLE_ASSERTIONS ) + set( LLVM_ENABLE_ABI_BREAKING_CHECKS 1 ) + endif() +elseif( uppercase_LLVM_ABI_BREAKING_CHECKS STREQUAL "FORCE_ON" ) + set( LLVM_ENABLE_ABI_BREAKING_CHECKS 1 ) +elseif( uppercase_LLVM_ABI_BREAKING_CHECKS STREQUAL "FORCE_OFF" ) + # We don't need to do anything special to turn off ABI breaking checks. +else() + message(FATAL_ERROR "Unknown value for LLVM_ABI_BREAKING_CHECKS: \"${LLVM_ABI_BREAKING_CHECKS}\"!") +endif() + if(WIN32) set(LLVM_HAVE_LINK_VERSION_SCRIPT 0) if(CYGWIN) diff --git a/configure b/configure index 5a313feb709..4ad1f21ed3b 100755 --- a/configure +++ b/configure @@ -1426,6 +1426,9 @@ Optional Features: --enable-expensive-checks Compile with expensive debug checks enabled (default is NO) + --enable-abi-breaking-checks + Compile with abi-breaking asserts support (default + is with-asserts) --enable-debug-runtime Build runtime libs with debug symbols (default is NO) --enable-debug-symbols Build compiler with debug symbols (default is NO if @@ -4980,9 +4983,11 @@ fi if test ${enableval} = "yes" ; then DISABLE_ASSERTIONS= + assertions_enabled="yes" else DISABLE_ASSERTIONS=DISABLE_ASSERTIONS=1 + assertions_enabled="no" fi # Check whether --enable-werror was given. @@ -5023,6 +5028,32 @@ else fi +# Check whether --enable-abi-breaking-checks was given. +if test "${enable_abi_breaking_checks+set}" = set; then + enableval=$enable_abi_breaking_checks; +else + enableval="with-asserts" +fi + +case "$enableval" in + with-asserts) if test ${assertions_enabled} = "yes" ; then + +cat >>confdefs.h <<\_ACEOF +#define LLVM_ENABLE_ABI_BREAKING_CHECKS 1 +_ACEOF + + fi ;; + yes) +cat >>confdefs.h <<\_ACEOF +#define LLVM_ENABLE_ABI_BREAKING_CHECKS 1 +_ACEOF + ;; + no) ;; + *) { { echo "$as_me:$LINENO: error: Invalid setting for --enable-abi-breaking-checks. Use \"with-asserts\", \"yes\" or \"no\"" >&5 +echo "$as_me: error: Invalid setting for --enable-abi-breaking-checks. Use \"with-asserts\", \"yes\" or \"no\"" >&2;} + { (exit 1); exit 1; }; } +esac + # Check whether --enable-debug-runtime was given. if test "${enable_debug_runtime+set}" = set; then enableval=$enable_debug_runtime; diff --git a/docs/CMake.rst b/docs/CMake.rst index 4d96466c901..b9e473fab2b 100644 --- a/docs/CMake.rst +++ b/docs/CMake.rst @@ -270,6 +270,15 @@ LLVM-specific variables **LLVM_ENABLE_WERROR**:BOOL Stop and fail build, if a compiler warning is triggered. Defaults to OFF. +**LLVM_ABI_BREAKING_CHECKS**:STRING + Used to decide if LLVM should be built with ABI breaking checks or + not. Allowed values are `WITH_ASSERTS` (default), `FORCE_ON` and + `FORCE_OFF`. `WITH_ASSERTS` turns on ABI breaking checks in an + assertion enabled build. `FORCE_ON` (`FORCE_OFF`) turns them on + (off) irrespective of whether normal (`NDEBUG` based) assertions are + enabled or not. A version of LLVM built with ABI breaking checks + is not ABI compatible with a version built without it. + **LLVM_BUILD_32_BITS**:BOOL Build 32-bits executables and libraries on 64-bits systems. This option is available only on some 64-bits unix systems. Defaults to OFF. diff --git a/docs/ProgrammersManual.rst b/docs/ProgrammersManual.rst index 3b05280fb16..2c7e4a9954a 100644 --- a/docs/ProgrammersManual.rst +++ b/docs/ProgrammersManual.rst @@ -2553,6 +2553,22 @@ section on :ref:`isa and dyn_cast ` and our :doc:`detailed document ` which describes how you can implement this pattern for use with the LLVM helpers. +.. _abi_breaking_checks: + +ABI Breaking Checks +------------------- + +Checks and asserts that alter the LLVM C++ ABI are predicated on the +preprocessor symbol `LLVM_ENABLE_ABI_BREAKING_CHECKS` -- LLVM +libraries built with `LLVM_ENABLE_ABI_BREAKING_CHECKS` are not ABI +compatible LLVM libraries built without it defined. By default, +turning on assertions also turns on `LLVM_ENABLE_ABI_BREAKING_CHECKS` +so a default +Asserts build is not ABI compatible with a +default -Asserts build. Clients that want ABI compatibility +between +Asserts and -Asserts builds should use the CMake or autoconf +build systems to set `LLVM_ENABLE_ABI_BREAKING_CHECKS` independently +of `LLVM_ENABLE_ASSERTIONS`. + .. _coreclasses: The Core LLVM Class Hierarchy Reference diff --git a/include/llvm/ADT/DenseMap.h b/include/llvm/ADT/DenseMap.h index d947ffaa7ed..8c65f70838e 100644 --- a/include/llvm/ADT/DenseMap.h +++ b/include/llvm/ADT/DenseMap.h @@ -15,6 +15,7 @@ #define LLVM_ADT_DENSEMAP_H #include "llvm/ADT/DenseMapInfo.h" +#include "llvm/ADT/EpochTracker.h" #include "llvm/Support/AlignOf.h" #include "llvm/Support/Compiler.h" #include "llvm/Support/MathExtras.h" @@ -50,7 +51,7 @@ class DenseMapIterator; template -class DenseMapBase { +class DenseMapBase : public DebugEpochBase { public: typedef unsigned size_type; typedef KeyT key_type; @@ -62,16 +63,17 @@ public: const_iterator; inline iterator begin() { // When the map is empty, avoid the overhead of AdvancePastEmptyBuckets(). - return empty() ? end() : iterator(getBuckets(), getBucketsEnd()); + return empty() ? end() : iterator(getBuckets(), getBucketsEnd(), *this); } inline iterator end() { - return iterator(getBucketsEnd(), getBucketsEnd(), true); + return iterator(getBucketsEnd(), getBucketsEnd(), *this, true); } inline const_iterator begin() const { - return empty() ? end() : const_iterator(getBuckets(), getBucketsEnd()); + return empty() ? end() + : const_iterator(getBuckets(), getBucketsEnd(), *this); } inline const_iterator end() const { - return const_iterator(getBucketsEnd(), getBucketsEnd(), true); + return const_iterator(getBucketsEnd(), getBucketsEnd(), *this, true); } bool LLVM_ATTRIBUTE_UNUSED_RESULT empty() const { @@ -81,11 +83,13 @@ public: /// Grow the densemap so that it has at least Size buckets. Does not shrink void resize(size_type Size) { + incrementEpoch(); if (Size > getNumBuckets()) grow(Size); } void clear() { + incrementEpoch(); if (getNumEntries() == 0 && getNumTombstones() == 0) return; // If the capacity of the array is huge, and the # elements used is small, @@ -118,13 +122,13 @@ public: iterator find(const KeyT &Val) { BucketT *TheBucket; if (LookupBucketFor(Val, TheBucket)) - return iterator(TheBucket, getBucketsEnd(), true); + return iterator(TheBucket, getBucketsEnd(), *this, true); return end(); } const_iterator find(const KeyT &Val) const { const BucketT *TheBucket; if (LookupBucketFor(Val, TheBucket)) - return const_iterator(TheBucket, getBucketsEnd(), true); + return const_iterator(TheBucket, getBucketsEnd(), *this, true); return end(); } @@ -137,14 +141,14 @@ public: iterator find_as(const LookupKeyT &Val) { BucketT *TheBucket; if (LookupBucketFor(Val, TheBucket)) - return iterator(TheBucket, getBucketsEnd(), true); + return iterator(TheBucket, getBucketsEnd(), *this, true); return end(); } template const_iterator find_as(const LookupKeyT &Val) const { const BucketT *TheBucket; if (LookupBucketFor(Val, TheBucket)) - return const_iterator(TheBucket, getBucketsEnd(), true); + return const_iterator(TheBucket, getBucketsEnd(), *this, true); return end(); } @@ -163,12 +167,13 @@ public: std::pair insert(const std::pair &KV) { BucketT *TheBucket; if (LookupBucketFor(KV.first, TheBucket)) - return std::make_pair(iterator(TheBucket, getBucketsEnd(), true), + return std::make_pair(iterator(TheBucket, getBucketsEnd(), *this, true), false); // Already in map. // Otherwise, insert the new element. TheBucket = InsertIntoBucket(KV.first, KV.second, TheBucket); - return std::make_pair(iterator(TheBucket, getBucketsEnd(), true), true); + return std::make_pair(iterator(TheBucket, getBucketsEnd(), *this, true), + true); } // Inserts key,value pair into the map if the key isn't already in the map. @@ -177,14 +182,15 @@ public: std::pair insert(std::pair &&KV) { BucketT *TheBucket; if (LookupBucketFor(KV.first, TheBucket)) - return std::make_pair(iterator(TheBucket, getBucketsEnd(), true), + return std::make_pair(iterator(TheBucket, getBucketsEnd(), *this, true), false); // Already in map. - + // Otherwise, insert the new element. TheBucket = InsertIntoBucket(std::move(KV.first), std::move(KV.second), TheBucket); - return std::make_pair(iterator(TheBucket, getBucketsEnd(), true), true); + return std::make_pair(iterator(TheBucket, getBucketsEnd(), *this, true), + true); } /// insert - Range insertion of pairs. @@ -431,6 +437,8 @@ private: } BucketT *InsertIntoBucketImpl(const KeyT &Key, BucketT *TheBucket) { + incrementEpoch(); + // If the load of the hash table is more than 3/4, or if fewer than 1/8 of // the buckets are empty (meaning that many are filled with tombstones), // grow the table. @@ -987,9 +995,10 @@ private: template -class DenseMapIterator { +class DenseMapIterator : DebugEpochBase::HandleBase { typedef DenseMapIterator ConstIterator; friend class DenseMapIterator; + friend class DenseMapIterator; public: typedef ptrdiff_t difference_type; @@ -1003,8 +1012,10 @@ private: public: DenseMapIterator() : Ptr(nullptr), End(nullptr) {} - DenseMapIterator(pointer Pos, pointer E, bool NoAdvance = false) - : Ptr(Pos), End(E) { + DenseMapIterator(pointer Pos, pointer E, const DebugEpochBase &Epoch, + bool NoAdvance = false) + : DebugEpochBase::HandleBase(&Epoch), Ptr(Pos), End(E) { + assert(isHandleInSync() && "invalid construction!"); if (!NoAdvance) AdvancePastEmptyBuckets(); } @@ -1015,28 +1026,40 @@ public: typename = typename std::enable_if::type> DenseMapIterator( const DenseMapIterator &I) - : Ptr(I.Ptr), End(I.End) {} + : DebugEpochBase::HandleBase(I), Ptr(I.Ptr), End(I.End) {} reference operator*() const { + assert(isHandleInSync() && "invalid iterator access!"); return *Ptr; } pointer operator->() const { + assert(isHandleInSync() && "invalid iterator access!"); return Ptr; } bool operator==(const ConstIterator &RHS) const { - return Ptr == RHS.operator->(); + assert((!Ptr || isHandleInSync()) && "handle not in sync!"); + assert((!RHS.Ptr || RHS.isHandleInSync()) && "handle not in sync!"); + assert(getEpochAddress() == RHS.getEpochAddress() && + "comparing incomparable iterators!"); + return Ptr == RHS.Ptr; } bool operator!=(const ConstIterator &RHS) const { - return Ptr != RHS.operator->(); + assert((!Ptr || isHandleInSync()) && "handle not in sync!"); + assert((!RHS.Ptr || RHS.isHandleInSync()) && "handle not in sync!"); + assert(getEpochAddress() == RHS.getEpochAddress() && + "comparing incomparable iterators!"); + return Ptr != RHS.Ptr; } inline DenseMapIterator& operator++() { // Preincrement + assert(isHandleInSync() && "invalid iterator access!"); ++Ptr; AdvancePastEmptyBuckets(); return *this; } DenseMapIterator operator++(int) { // Postincrement + assert(isHandleInSync() && "invalid iterator access!"); DenseMapIterator tmp = *this; ++*this; return tmp; } diff --git a/include/llvm/ADT/EpochTracker.h b/include/llvm/ADT/EpochTracker.h new file mode 100644 index 00000000000..d593073317b --- /dev/null +++ b/include/llvm/ADT/EpochTracker.h @@ -0,0 +1,99 @@ +//===- llvm/ADT/EpochTracker.h - ADT epoch tracking --------------*- C++ -*-==// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file defines the DebugEpochBase and DebugEpochBase::HandleBase classes. +// These can be used to write iterators that are fail-fast when LLVM is built +// with asserts enabled. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_ADT_EPOCH_TRACKER_H +#define LLVM_ADT_EPOCH_TRACKER_H + +#include "llvm/Config/llvm-config.h" + +#include + +namespace llvm { + +#ifndef LLVM_ENABLE_ABI_BREAKING_CHECKS + +class DebugEpochBase { +public: + void incrementEpoch() {} + + class HandleBase { + public: + HandleBase() {} + explicit HandleBase(const DebugEpochBase *) {} + bool isHandleInSync() const { return true; } + const void *getEpochAddress() const { return nullptr; } + }; +}; + +#else + +/// \brief A base class for data structure classes wishing to make iterators +/// ("handles") pointing into themselves fail-fast. When building without +/// asserts, this class is empty and does nothing. +/// +/// DebugEpochBase does not by itself track handles pointing into itself. The +/// expectation is that routines touching the handles will poll on +/// isHandleInSync at appropriate points to assert that the handle they're using +/// is still valid. +/// +class DebugEpochBase { + uint64_t Epoch; + +public: + DebugEpochBase() : Epoch(0) {} + + /// \brief Calling incrementEpoch invalidates all handles pointing into the + /// calling instance. + void incrementEpoch() { ++Epoch; } + + /// \brief The destructor calls incrementEpoch to make use-after-free bugs + /// more likely to crash deterministically. + ~DebugEpochBase() { incrementEpoch(); } + + /// \brief A base class for iterator classes ("handles") that wish to poll for + /// iterator invalidating modifications in the underlying data structure. + /// When LLVM is built without asserts, this class is empty and does nothing. + /// + /// HandleBase does not track the parent data structure by itself. It expects + /// the routines modifying the data structure to call incrementEpoch when they + /// make an iterator-invalidating modification. + /// + class HandleBase { + const uint64_t *EpochAddress; + uint64_t EpochAtCreation; + + public: + HandleBase() : EpochAddress(nullptr), EpochAtCreation(UINT64_MAX) {} + + explicit HandleBase(const DebugEpochBase *Parent) + : EpochAddress(&Parent->Epoch), EpochAtCreation(Parent->Epoch) {} + + /// \brief Returns true if the DebugEpochBase this Handle is linked to has + /// not called incrementEpoch on itself since the creation of this + /// HandleBase instance. + bool isHandleInSync() const { return *EpochAddress == EpochAtCreation; } + + /// \brief Returns a pointer to the epoch word stored in the data structure + /// this handle points into. Can be used to check if two iterators point + /// into the same data structure. + const void *getEpochAddress() const { return EpochAddress; } + }; +}; + +#endif // LLVM_ENABLE_ABI_BREAKING_CHECKS + +} // namespace llvm + +#endif diff --git a/include/llvm/Config/config.h.in b/include/llvm/Config/config.h.in index 865caae0067..67d7c8485a4 100644 --- a/include/llvm/Config/config.h.in +++ b/include/llvm/Config/config.h.in @@ -417,6 +417,9 @@ /* Installation directory for documentation */ #undef LLVM_DOCSDIR +/* Define to enable checks that alter the LLVM C++ ABI */ +#undef LLVM_ENABLE_ABI_BREAKING_CHECKS + /* Define if threads enabled */ #undef LLVM_ENABLE_THREADS diff --git a/include/llvm/Config/llvm-config.h.cmake b/include/llvm/Config/llvm-config.h.cmake index d54003d993a..bb7dc067ea0 100644 --- a/include/llvm/Config/llvm-config.h.cmake +++ b/include/llvm/Config/llvm-config.h.cmake @@ -101,4 +101,8 @@ /* Define if we link Polly to the tools */ #cmakedefine LINK_POLLY_INTO_TOOLS +/* Define if LLVM is built with asserts and checks that change the layout of + client-visible data structures. */ +#cmakedefine LLVM_ENABLE_ABI_BREAKING_CHECKS + #endif diff --git a/include/llvm/Config/llvm-config.h.in b/include/llvm/Config/llvm-config.h.in index 25a92954483..03e482ac175 100644 --- a/include/llvm/Config/llvm-config.h.in +++ b/include/llvm/Config/llvm-config.h.in @@ -98,4 +98,7 @@ /* LLVM version string */ #undef LLVM_VERSION_STRING +/* Define to enable checks that alter the LLVM C++ ABI */ +#undef LLVM_ENABLE_ABI_BREAKING_CHECKS + #endif -- 2.34.1