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 EpochTrackerHostBase { 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) { + bumpEpoch(); if (Size > getNumBuckets()) grow(Size); } void clear() { + bumpEpoch(); 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) { + bumpEpoch(); + // 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,7 +995,7 @@ template -class DenseMapIterator { +class DenseMapIterator : EpochTrackerHandleBase { typedef DenseMapIterator ConstIterator; friend class DenseMapIterator; @@ -1003,8 +1011,11 @@ public: DenseMapIterator() : Ptr(nullptr), End(nullptr) {} - DenseMapIterator(pointer Pos, pointer E, bool NoAdvance = false) - : Ptr(Pos), End(E) { + DenseMapIterator(pointer Pos, pointer E, + const EpochTrackerHostBase *EpochHost, + bool NoAdvance = false) + : EpochTrackerHandleBase(EpochHost), Ptr(Pos), End(E) { + assert(isHandleInSync() && "invalid construction!"); if (!NoAdvance) AdvancePastEmptyBuckets(); } @@ -1013,12 +1024,14 @@ // Otherwise this is a copy constructor for iterator. DenseMapIterator( const DenseMapIterator &I) - : Ptr(I.Ptr), End(I.End) {} + : EpochTrackerHandleBase(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; } @@ -1030,11 +1043,13 @@ } 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,88 @@ +//===- 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 EpochTrackerHostBase and EpochTrackerHandleBase +// 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 { + +/// \brief A base class for data structure classes ("hosts") wishing to make +/// iterators ("handles") pointing into themselves fail-fast. When building +/// without asserts, this class is empty and does nothing. +/// +/// EpochTrackerHostBase does not by itself track handles pointing into the +/// host. 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 EpochTrackerHostBase { + friend class EpochTrackerHandleBase; + +#ifdef NDEBUG +public: + void bumpEpoch() {} +#else + uint64_t Epoch; + +public: + EpochTrackerHostBase() : Epoch(0) {} + + /// \brief Host classes call bumpEpoch to invalidate all handles pointing into + /// the calling instance. + void bumpEpoch() { ++Epoch; } + + /// \brief The destructor calls bumpEpoch to make use-after-free bugs more + /// likely to crash deterministically. + ~EpochTrackerHostBase() { bumpEpoch(); } +#endif +}; + +/// \brief A base class for iterator classes ("handles") that wish to poll for +/// iterator invalidating modifications in the underlying data structure +/// ("hosts"). When LLVM is built without asserts, this class is empty and does +/// nothing. +/// +/// EpochTrackerHandleBase does not track the host data structure by itself. It +/// expects the routines modifying the data structure to call bumpEpoch when +/// they make an iterator-invalidating modification. +/// +class EpochTrackerHandleBase { +#ifdef NDEBUG +public: + EpochTrackerHandleBase() {} + explicit EpochTrackerHandleBase(const EpochTrackerHostBase *) {} + bool isHandleInSync() { return true; } +#else + const uint64_t *HostEpochAddress; + uint64_t EpochAtCreation; + +public: + EpochTrackerHandleBase() + : HostEpochAddress(nullptr), EpochAtCreation(UINT64_MAX) {} + + explicit EpochTrackerHandleBase(const EpochTrackerHostBase *Host) + : HostEpochAddress(&Host->Epoch), EpochAtCreation(Host->Epoch) {} + + /// \brief Returns true if the host has not called bumpEpoch on itself since + /// the creation of this EpochTrackerHandleBase instance. + bool isHandleInSync() const { return *HostEpochAddress == EpochAtCreation; } +#endif +}; + +} // namespace llvm + +#endif