RFC: fail-fast iterators for DenseMap

[sanjoy]

Summary

This patch is an attempt at making DenseMapIterators "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.

(This exact same thing can be done for SmallPtrSets, but that is a
later change.)

This change is fairly rough at the moment, but I want to get some
early feedback on the approach and style before I spend too much time
on this.

This change, in its current form, has already helped me fix two
existing bugs:

http://reviews.llvm.org/rL230718
http://reviews.llvm.org/rL230719

[ruiu]

Is it possible to catch an error caused by an expression like m[x] = m[y]? Generally, the last statement v in auto &v = m[x]; m[newkey] = somevalue; v; is invalid because it uses an invalid reference.

[sanjoy]

In D7931#131003, @ruiu wrote:

Is it possible to catch an error caused by an expression like m[x] = m[y]?

Do you mean the expression m[x] = m[y] itself is invalid? Or that it is one more way to "clobber" a DenseMap and invalidate all iterators?

Generally, the last statement v in auto &v = m[x]; m[newkey] = somevalue; v; is invalid because it uses an invalid reference.

That's a harder problem. The way I'd catch in the snippet you mentioned would be by getting operator[] return a wrapper object which would, like the iterator, check its validity on access. It would also have to be implicitly castable to the DenseMaps range type. However, I don't think any approach will work with int &v = m[x]; m[y] = foo; use(v) since we lose any possibility of intercepting the use of v as soon as it gets cast to an int &.

[chandlerc]

include/llvm/ADT/ADTModCountTracker.h

16 ↗

(On Diff #20826)

Heh. Pick a name and be consistent?

And please don't repeat 'ADT' in it. We don't do that anywhere else. =]

35–46 ↗

(On Diff #20826)

I have to admit, I don't find the naming convention really useful here. Here is my suggested naming. Here are the key points:

1. I would just use the term epoch. That's what you have.
2. I would make it say debugging-only on the tin.
3. I would hint heavily that it is intended to be used as base classes so that the empty base class optimization kicks in.
4. I would handle the NDEBUG stuff at this layer. See more on why in my comment below.

template <> struct DebugEpochBaseImpl<true> {
  uint64_t Epoch;

  struct HandleBase {
    const uint64_t *Epoch;
    uint64_t InitialEpoch;

    ...

    bool hasEpochAdvanced() const { ... }
  };
};

#ifndef NDEBUG
typedef DebugEpochBaseImpl<true> DebugEpochBase;
#else
typedef DebugEpochBaseImpl<false> DebugEpochBase;
#endif

I'm not 100% on "hasEpochAdvanced" though. Maybe there is a better name there. But I would just name these as general Epoch utilities, and I would merge the parent into the containing template. I think handle or ref is a better model than "child".

include/llvm/ADT/DenseMap.h

52–56 ↗

(On Diff #20826)

Hmm...

What do you think about making this be automatically handled by the epoch utility? That is, localize the NDEBUG behavior there. There is no getting around the fact that this makes data-structures ABI-incompatible between NDEBUG and !NDEBUG, so I'd probably just make it a conditional typedef of the implementation class template.

1013 ↗

(On Diff #20826)

This still makes the iterator object larger even when the class is empty.

You need to arrange for this to be the base class of the iteartor so that the empty base optimization kicks in (or to be a base class of a "compressed pair" style member type, but that seems much more complicated than we need).

[sanjoy]

Address Chandler's review.

• no "ADT" in the file or class names.
• changed the vocabulary to "Handle" and "Host"
• suffixed the class names with "Base" and change the DenseMap implementation to use inheritance over composition.
• handled the NDEBUG-only-ness directly in the header file. Once this was locked down, I could not justify the additional complexity from the template specialization, so I removed that too.

[sanjoy]

Address Duncan's review comments.

[chandlerc]

The advantage of setting a template argument via a typedef based on NDEBUG is that it ensures these types *mangle* differently which will give a hard error at link time if you mix code. With this implementation, it looks like you'll just get weird miscompiles if TUs have different values of NDEBUG.

I also think you should put the word "debug" in the name to indicate that this cannot be used for epoch-based data structures.

The word "host" doesn't seem to really add much for me at least.

How about: DebugEpochBase and DebugEpochBase::HandleBase?

[sanjoy]

Address Chandler's comments:

• change vocabulary to DebugEpochBase and DebugEpochBase::HandleBase
• move the #ifdef to outside the classes since with (1) in place, #ifdef within the classes looks confusing.

[chandlerc]

Minor nits only. Feel free to submit, but probably submit when you can clean up substantial fallout... I expect this to cause chaos when it lands.

include/llvm/ADT/DenseMap.h

1014 ↗

(On Diff #20979)

Is Epoch ever false here? If not, pass by reference?

include/llvm/ADT/EpochTracker.h

25–35 ↗

(On Diff #20979)

Looking at what this will do with doxygen and other things, I think it would be better to sink the #ifdef stuff inside the class and method bodies. That will ensure code navigation and such always have a consistent target. A very minor point though.

56 ↗

(On Diff #20979)

What do you think about calling this "next"? or "increment"? I don't feel strongly, but "bump" seems fairly imprecise...

[sanjoy]

Thanks for the review! I'll land this sometime in the next couple of days.

include/llvm/ADT/DenseMap.h

1014 ↗

(On Diff #20979)

Will do.

include/llvm/ADT/EpochTracker.h

25–35 ↗

(On Diff #20979)

Frankly, I'd rather have an easy to understand .h file over easy to read doxygen, so I went against too many #ifdefs. I'll push the #ifdefs inside class bodies if people actually complain about bad doxygen. :)

56 ↗

(On Diff #20979)

Will change to incrementEpoch

llvm/trunk/include/llvm/ADT/DenseMap.h

 // This file defines the DenseMap class.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_ADT_DENSEMAP_H
 #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"
 #include "llvm/Support/PointerLikeTypeTraits.h"
 #include "llvm/Support/type_traits.h"
 #include <algorithm>
 #include <cassert>
 #include <climits>

 
 template <
     typename KeyT, typename ValueT, typename KeyInfoT = DenseMapInfo<KeyT>,
     typename Bucket = detail::DenseMapPair<KeyT, ValueT>, bool IsConst = false>
 class DenseMapIterator;
 
 template <typename DerivedT, typename KeyT, typename ValueT, typename KeyInfoT,
           typename BucketT>
-class DenseMapBase {
+class DenseMapBase : public DebugEpochBase {
 public:
   typedef unsigned size_type;
   typedef KeyT key_type;
   typedef ValueT mapped_type;
   typedef BucketT value_type;
 
   typedef DenseMapIterator<KeyT, ValueT, KeyInfoT, BucketT> iterator;
   typedef DenseMapIterator<KeyT, ValueT, KeyInfoT, BucketT, true>
       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 {
     return getNumEntries() == 0;
   }
   unsigned size() const { return getNumEntries(); }
 
   /// 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,
     // shrink the array.
     if (getNumEntries() * 4 < getNumBuckets() && getNumBuckets() > 64) {
       shrink_and_clear();
       return;
     }
public:
   size_type count(const KeyT &Val) const {
     const BucketT *TheBucket;
     return LookupBucketFor(Val, TheBucket) ? 1 : 0;
   }
 
   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();
   }
 
   /// Alternate version of find() which allows a different, and possibly
   /// less expensive, key type.
   /// The DenseMapInfo is responsible for supplying methods
   /// getHashValue(LookupKeyT) and isEqual(LookupKeyT, KeyT) for each key
   /// type used.
   template<class LookupKeyT>
   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<class LookupKeyT>
   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();
   }
 
   /// lookup - Return the entry for the specified key, or a default
   /// constructed value if no such entry exists.
   ValueT lookup(const KeyT &Val) const {
     const BucketT *TheBucket;
     if (LookupBucketFor(Val, TheBucket))
       return TheBucket->getSecond();
     return ValueT();
   }
 
   // Inserts key,value pair into the map if the key isn't already in the map.
   // If the key is already in the map, it returns false and doesn't update the
   // value.
   std::pair<iterator, bool> insert(const std::pair<KeyT, ValueT> &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.
   // If the key is already in the map, it returns false and doesn't update the
   // value.
   std::pair<iterator, bool> insert(std::pair<KeyT, ValueT> &&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.
   template<typename InputIt>
   void insert(InputIt I, InputIt E) {
     for (; I != E; ++I)
       insert(*I);
   }
BucketT *InsertIntoBucket(KeyT &&Key, ValueT &&Value, BucketT *TheBucket) {
     TheBucket = InsertIntoBucketImpl(Key, TheBucket);
 
     TheBucket->getFirst() = std::move(Key);
     new (&TheBucket->getSecond()) ValueT(std::move(Value));
     return TheBucket;
   }
 
   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.
     //
     // The later case is tricky.  For example, if we had one empty bucket with
     // tons of tombstones, failing lookups (e.g. for insertion) would have to
     // probe almost the entire table until it found the empty bucket.  If the
     // table completely filled with tombstones, no lookup would ever succeed,
LargeRep Rep = {
       static_cast<BucketT*>(operator new(sizeof(BucketT) * Num)), Num
     };
     return Rep;
   }
 };
 
 template <typename KeyT, typename ValueT, typename KeyInfoT, typename Bucket,
           bool IsConst>
-class DenseMapIterator {
+class DenseMapIterator : DebugEpochBase::HandleBase {
   typedef DenseMapIterator<KeyT, ValueT, KeyInfoT, Bucket, true> ConstIterator;
   friend class DenseMapIterator<KeyT, ValueT, KeyInfoT, Bucket, true>;
 
 public:
   typedef ptrdiff_t difference_type;
   typedef typename std::conditional<IsConst, const Bucket, Bucket>::type
   value_type;
   typedef value_type *pointer;
   typedef value_type &reference;
   typedef std::forward_iterator_tag iterator_category;
 private:
   pointer Ptr, End;
 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();
   }
 
   // If IsConst is true this is a converting constructor from iterator to
   // const_iterator and the default copy constructor is used.
   // Otherwise this is a copy constructor for iterator.
   DenseMapIterator(
       const DenseMapIterator<KeyT, ValueT, KeyInfoT, Bucket, false> &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->();
   }
   bool operator!=(const ConstIterator &RHS) const {
     return Ptr != RHS.operator->();
   }
 
   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;
   }
 
 private:
   void AdvancePastEmptyBuckets() {
     const KeyT Empty = KeyInfoT::getEmptyKey();
     const KeyT Tombstone = KeyInfoT::getTombstoneKey();
 

llvm/trunk/include/llvm/ADT/EpochTracker.h

+//===- 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 <cstdint>
+
+namespace llvm {
+
+#ifdef NDEBUG
+
+class DebugEpochBase {
+public:
+  void incrementEpoch() {}
+
+  class HandleBase {
+  public:
+    HandleBase() {}
+    explicit HandleBase(const DebugEpochBase *) {}
+    bool isHandleInSync() { return true; }
+  };
+};
+
+#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; }
+  };
+};
+
+#endif
+
+} // namespace llvm
+
+#endif