Index: CMakeLists.txt =================================================================== --- CMakeLists.txt +++ CMakeLists.txt @@ -262,6 +262,9 @@ option(LLVM_ENABLE_ASSERTIONS "Enable assertions" ON) endif() +set(LLVM_FAIL_FAST_ITERATORS "WITH_ASSERTS" CACHE STRING + "Enable fail-fast iterators. 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) Index: Makefile.config.in =================================================================== --- Makefile.config.in +++ Makefile.config.in @@ -293,6 +293,10 @@ #ENABLE_EXPENSIVE_CHECKS = 0 @ENABLE_EXPENSIVE_CHECKS@ +# When ENABLE_FAIL_FAST_ITERATORS is enabled, LLVM will be built with +# support for fail-fast iterators. +ENABLE_FAIL_FAST_ITERATORS = @ENABLE_FAIL_FAST_ITERATORS@ + # When DEBUG_RUNTIME is enabled, the runtime libraries will retain debug # symbols. #DEBUG_RUNTIME = 1 Index: Makefile.rules =================================================================== --- Makefile.rules +++ Makefile.rules @@ -397,6 +397,13 @@ CPP.Defines += -D_GLIBCXX_DEBUG -DXDEBUG endif +# If ENABLE_FAIL_FAST_ITERATORS=1 specified (make command line or +# configured), then enable fail fast iterators by defining the +# appropriate preprocessor symbols. +ifeq ($(ENABLE_FAIL_FAST_ITERATORS), 1) + CPP.Defines += -DLLVM_ENABLE_FAIL_FAST_ITERATORS +endif + # LOADABLE_MODULE implies several other things so we force them to be # defined/on. ifdef LOADABLE_MODULE Index: autoconf/configure.ac =================================================================== --- autoconf/configure.ac +++ autoconf/configure.ac @@ -701,8 +701,10 @@ --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 @@ AC_SUBST(EXPENSIVE_CHECKS,[[no]]) fi +dnl --fail-fast-iterators : decide whether fail-fast iterators should be enabled +AC_ARG_ENABLE(fail-fast-iterators,AS_HELP_STRING( + --enable-fail-fast-iterators,[Compile with fail-fast iterator support (default is with-asserts)]),, enableval="with-asserts") +case "$enableval" in + with-asserts) if test ${assertions_enabled} = "yes" ; then + AC_SUBST(ENABLE_FAIL_FAST_ITERATORS,[1]) + else + AC_SUBST(ENABLE_FAIL_FAST_ITERATORS,[0]) + fi ;; + yes) AC_SUBST(ENABLE_FAIL_FAST_ITERATORS,[[1]]) ;; + no) AC_SUBST(ENABLE_FAIL_FAST_ITERATORS,[[0]]) ;; + *) AC_MSG_ERROR([Invalid setting for --enable-fail-fast-iterators. 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) @@ -741,7 +757,7 @@ AS_HELP_STRING(--enable-debug-symbols,[Build compiler with debug symbols (default is NO if optimization is on and YES if it's off)]),,enableval=no) if test ${enableval} = "no" ; then AC_SUBST(DEBUG_SYMBOLS,[[]]) -else + else AC_SUBST(DEBUG_SYMBOLS,[[DEBUG_SYMBOLS=1]]) fi Index: cmake/modules/HandleLLVMOptions.cmake =================================================================== --- cmake/modules/HandleLLVMOptions.cmake +++ cmake/modules/HandleLLVMOptions.cmake @@ -78,6 +78,20 @@ endif() endif() +string(TOUPPER "${LLVM_FAIL_FAST_ITERATORS}" uppercase_LLVM_FAIL_FAST_ITERATORS) + +if( uppercase_LLVM_FAIL_FAST_ITERATORS STREQUAL "WITH_ASSERTS" ) + if( LLVM_ENABLE_ASSERTIONS ) + add_llvm_definitions( -DLLVM_ENABLE_FAIL_FAST_ITERATORS ) + endif() +elseif( uppercase_LLVM_FAIL_FAST_ITERATORS STREQUAL "FORCE_ON" ) + add_llvm_definitions( -DLLVM_ENABLE_FAIL_FAST_ITERATORS ) +elseif( uppercase_LLVM_FAIL_FAST_ITERATORS STREQUAL "FORCE_OFF" ) + # We don't need to do anything special to turn off fail-fast iterators. +else() + message(FATAL_ERROR "Unknown value for LLVM_FAIL_FAST_ITERATORS: \"${LLVM_FAIL_FAST_ITERATORS}\"!") +endif() + if(WIN32) set(LLVM_HAVE_LINK_VERSION_SCRIPT 0) if(CYGWIN) Index: configure =================================================================== --- configure +++ configure @@ -697,6 +697,7 @@ ENABLE_WERROR ENABLE_EXPENSIVE_CHECKS EXPENSIVE_CHECKS +ENABLE_FAIL_FAST_ITERATORS DEBUG_RUNTIME DEBUG_SYMBOLS KEEP_SYMBOLS @@ -1426,6 +1427,9 @@ --enable-expensive-checks Compile with expensive debug checks enabled (default is NO) + --enable-fail-fast-iterators + Compile with fail-fast iterator 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 +4984,11 @@ 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 +5029,30 @@ fi +# Check whether --enable-fail-fast-iterators was given. +if test "${enable_fail_fast_iterators+set}" = set; then + enableval=$enable_fail_fast_iterators; +else + enableval="with-asserts" +fi + +case "$enableval" in + with-asserts) if test ${assertions_enabled} = "yes" ; then + ENABLE_FAIL_FAST_ITERATORS=1 + + else + ENABLE_FAIL_FAST_ITERATORS=0 + + fi ;; + yes) ENABLE_FAIL_FAST_ITERATORS=1 + ;; + no) ENABLE_FAIL_FAST_ITERATORS=0 + ;; + *) { { echo "$as_me:$LINENO: error: Invalid setting for --enable-fail-fast-iterators. Use \"with-asserts\", \"yes\" or \"no\"" >&5 +echo "$as_me: error: Invalid setting for --enable-fail-fast-iterators. 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; @@ -5048,7 +5078,7 @@ if test ${enableval} = "no" ; then DEBUG_SYMBOLS= -else + else DEBUG_SYMBOLS=DEBUG_SYMBOLS=1 fi @@ -18804,8 +18834,8 @@ ENABLE_WERROR!$ENABLE_WERROR$ac_delim ENABLE_EXPENSIVE_CHECKS!$ENABLE_EXPENSIVE_CHECKS$ac_delim EXPENSIVE_CHECKS!$EXPENSIVE_CHECKS$ac_delim +ENABLE_FAIL_FAST_ITERATORS!$ENABLE_FAIL_FAST_ITERATORS$ac_delim DEBUG_RUNTIME!$DEBUG_RUNTIME$ac_delim -DEBUG_SYMBOLS!$DEBUG_SYMBOLS$ac_delim _ACEOF if test `sed -n "s/.*$ac_delim\$/X/p" conf$$subs.sed | grep -c X` = 97; then @@ -18847,6 +18877,7 @@ ac_delim='%!_!# ' for ac_last_try in false false false false false :; do cat >conf$$subs.sed <<_ACEOF +DEBUG_SYMBOLS!$DEBUG_SYMBOLS$ac_delim KEEP_SYMBOLS!$KEEP_SYMBOLS$ac_delim JIT!$JIT$ac_delim TARGET_HAS_JIT!$TARGET_HAS_JIT$ac_delim @@ -18943,7 +18974,6 @@ MMAP_FILE!$MMAP_FILE$ac_delim SHLIBEXT!$SHLIBEXT$ac_delim LLVM_PREFIX!$LLVM_PREFIX$ac_delim -LLVM_BINDIR!$LLVM_BINDIR$ac_delim _ACEOF if test `sed -n "s/.*$ac_delim\$/X/p" conf$$subs.sed | grep -c X` = 97; then @@ -18985,6 +19015,7 @@ ac_delim='%!_!# ' for ac_last_try in false false false false false :; do cat >conf$$subs.sed <<_ACEOF +LLVM_BINDIR!$LLVM_BINDIR$ac_delim LLVM_DATADIR!$LLVM_DATADIR$ac_delim LLVM_DOCSDIR!$LLVM_DOCSDIR$ac_delim LLVM_ETCDIR!$LLVM_ETCDIR$ac_delim @@ -19004,7 +19035,7 @@ LTLIBOBJS!$LTLIBOBJS$ac_delim _ACEOF - if test `sed -n "s/.*$ac_delim\$/X/p" conf$$subs.sed | grep -c X` = 17; then + if test `sed -n "s/.*$ac_delim\$/X/p" conf$$subs.sed | grep -c X` = 18; then break elif $ac_last_try; then { { echo "$as_me:$LINENO: error: could not make $CONFIG_STATUS" >&5 Index: docs/CMake.rst =================================================================== --- docs/CMake.rst +++ docs/CMake.rst @@ -270,6 +270,16 @@ **LLVM_ENABLE_WERROR**:BOOL Stop and fail build, if a compiler warning is triggered. Defaults to OFF. +**LLVM_FAIL_FAST_ITERATORS**:STRING + Used to decide if LLVM should be built with fail-fast iterator + support or not. Allowed values are `WITH_ASSERTS` (default), + `FORCE_ON` and `FORCE_OFF`. `WITH_ASSERTS` turns on fail-fast + iterators in an assertion enabled build. `FORCE_ON` (`FORCE_OFF`) + turns fail-fast iterators on (off) irrespective of whether + assertions are enabled or not. A version of LLVM built with + fail-fast iterator support 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. Index: include/llvm/ADT/DenseMap.h =================================================================== --- include/llvm/ADT/DenseMap.h +++ 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 @@ template -class DenseMapBase { +class DenseMapBase : public DebugEpochBase { public: typedef unsigned size_type; typedef KeyT key_type; @@ -62,16 +63,17 @@ 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 @@ /// 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 @@ 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 @@ 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 @@ 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 @@ 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 @@ } 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 @@ 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 @@ 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 @@ 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; } Index: include/llvm/ADT/EpochTracker.h =================================================================== --- /dev/null +++ include/llvm/ADT/EpochTracker.h @@ -0,0 +1,97 @@ +//===- 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 + +namespace llvm { + +#ifndef LLVM_ENABLE_FAIL_FAST_ITERATORS + +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_FAIL_FAST_ITERATORS + +} // namespace llvm + +#endif