Hash iterators: Check for concurrent modification and fix 1 place where it happened

Source/wtf/HashTable.h

 /*
  * Copyright (C) 2005, 2006, 2007, 2008, 2011, 2012 Apple Inc. All rights reserved.
  * Copyright (C) 2008 David Levin <levin@chromium.org>
  *
  * This library is free software; you can redistribute it and/or
  * modify it under the terms of the GNU Library General Public
  * License as published by the Free Software Foundation; either
  * version 2 of the License, or (at your option) any later version.
  *
  * This library is distributed in the hope that it will be useful,
@@ skipping 67 matching lines @@
 
         friend class HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>;
         friend class HashTableIterator<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>;
 
         void skipEmptyBuckets()
         {
             while (m_position != m_endPosition && HashTableType::isEmptyOrDeletedBucket(*m_position))
                 ++m_position;
         }
 
-        HashTableConstIterator(PointerType position, PointerType endPosition)
-            : m_position(position), m_endPosition(endPosition)
+        HashTableConstIterator(PointerType position, PointerType endPosition, const HashTableType* container)
+            : m_position(position)
+            , m_endPosition(endPosition)
+#ifdef ASSERT_ENABLED
+            , m_container(container)
+            , m_containerModifications(container->modifications())
+#endif
         {
             skipEmptyBuckets();
         }
 
-        HashTableConstIterator(PointerType position, PointerType endPosition, HashItemKnownGoodTag)
-            : m_position(position), m_endPosition(endPosition)
+        HashTableConstIterator(PointerType position, PointerType endPosition, const HashTableType* container, HashItemKnownGoodTag)
+            : m_position(position)
+            , m_endPosition(endPosition)
+#ifdef ASSERT_ENABLED
+            , m_container(container)
+            , m_containerModifications(container->modifications())
+#endif
         {
         }
 
+        void checkModifications() const
+        {
+            // HashTable and collections that build on it do not support
+            // modifications while there is an iterator in use. The exception
+            // is ListHashSet, which has its own iterators that tolerate
+            // modification of the underlying set.
+            ASSERT(m_containerModifications == m_container->modifications());
+        }
+
     public:
         HashTableConstIterator()
         {
         }
 
         GetType get() const
         {
+            checkModifications();
             return m_position;
         }
         typename Traits::IteratorConstReferenceType operator*() const { return Traits::getToReferenceConstConversion(get()); }
         GetType operator->() const { return get(); }
 
         const_iterator& operator++()
         {
             ASSERT(m_position != m_endPosition);
+            checkModifications();
             ++m_position;
             skipEmptyBuckets();
             return *this;
         }
 
         // postfix ++ intentionally omitted
 
         // Comparison.
         bool operator==(const const_iterator& other) const
         {
             return m_position == other.m_position;
         }
         bool operator!=(const const_iterator& other) const
         {
             return m_position != other.m_position;
         }
         bool operator==(const iterator& other) const
         {
             return *this == static_cast<const_iterator>(other);
         }
         bool operator!=(const iterator& other) const
         {
             return *this != static_cast<const_iterator>(other);
         }
 
     private:
         PointerType m_position;
         PointerType m_endPosition;
+#ifdef ASSERT_ENABLED
+        const HashTableType* m_container;
+        int64_t m_containerModifications;
+#endif
     };
 
     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits, typename Allocator>
     class HashTableIterator {
     private:
+        typedef HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator> HashTableType;
         typedef HashTableIterator<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator> iterator;
         typedef HashTableConstIterator<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator> const_iterator;
         typedef Value ValueType;
         typedef typename Traits::IteratorGetType GetType;
         typedef ValueType* PointerType;
 
         friend class HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>;
 
-        HashTableIterator(PointerType pos, PointerType end) : m_iterator(pos, end) { }
-        HashTableIterator(PointerType pos, PointerType end, HashItemKnownGoodTag tag) : m_iterator(pos, end, tag) { }
+        HashTableIterator(PointerType pos, PointerType end, const HashTableType* container) : m_iterator(pos, end, container) { }
+        HashTableIterator(PointerType pos, PointerType end, const HashTableType* container, HashItemKnownGoodTag tag) : m_iterator(pos, end, container, tag) { }
 
     public:
         HashTableIterator() { }
 
         // default copy, assignment and destructor are OK
 
         GetType get() const { return const_cast<GetType>(m_iterator.get()); }
         typename Traits::IteratorReferenceType operator*() const { return Traits::getToReferenceConversion(get()); }
         GetType operator->() const { return get(); }
 
@@ skipping 175 matching lines @@
 
         static bool isEmptyBucket(const ValueType& value) { return isHashTraitsEmptyValue<KeyTraits>(Extractor::extract(value)); }
         static bool isDeletedBucket(const ValueType& value) { return KeyTraits::isDeletedValue(Extractor::extract(value)); }
         static bool isEmptyOrDeletedBucket(const ValueType& value) { return HashTableHelper<ValueType, Extractor, KeyTraits>:: isEmptyOrDeletedBucket(value); }
 
         ValueType* lookup(KeyPeekInType key) { return lookup<IdentityTranslatorType>(key); }
         template<typename HashTranslator, typename T> ValueType* lookup(const T&);
 
         void trace(typename Allocator::Visitor*);
 
+#ifdef ASSERT_ENABLED
+        int64_t modifications() const { return m_modifications; }
+        void registerModification() { m_modifications++; }
+#else
+        int64_t modifications() const { return 0; }
+        void registerModification() { }
+#endif
+
     private:
         static ValueType* allocateTable(unsigned size);
         static void deallocateTable(ValueType* table, unsigned size);
 
         typedef std::pair<ValueType*, bool> LookupType;
         typedef std::pair<LookupType, unsigned> FullLookupType;
 
         LookupType lookupForWriting(const Key& key) { return lookupForWriting<IdentityTranslatorType>(key); };
         template<typename HashTranslator, typename T> FullLookupType fullLookupForWriting(const T&);
         template<typename HashTranslator, typename T> LookupType lookupForWriting(const T&);
 
         void remove(ValueType*);
 
         bool shouldExpand() const { return (m_keyCount + m_deletedCount) * m_maxLoad >= m_tableSize; }
         bool mustRehashInPlace() const { return m_keyCount * m_minLoad < m_tableSize * 2; }
         bool shouldShrink() const { return m_keyCount * m_minLoad < m_tableSize && m_tableSize > KeyTraits::minimumTableSize; }
         void expand();
         void shrink() { rehash(m_tableSize / 2); }
 
         void rehash(unsigned newTableSize);
         void reinsert(ValueType&);
 
         static void initializeBucket(ValueType& bucket);
         static void deleteBucket(ValueType& bucket) { bucket.~ValueType(); Traits::constructDeletedValue(bucket); }
 
         FullLookupType makeLookupResult(ValueType* position, bool found, unsigned hash)
             { return FullLookupType(LookupType(position, found), hash); }
 
-        iterator makeIterator(ValueType* pos) { return iterator(pos, m_table + m_tableSize); }
-        const_iterator makeConstIterator(ValueType* pos) const { return const_iterator(pos, m_table + m_tableSize); }
-        iterator makeKnownGoodIterator(ValueType* pos) { return iterator(pos, m_table + m_tableSize, HashItemKnownGood); }
-        const_iterator makeKnownGoodConstIterator(ValueType* pos) const { return const_iterator(pos, m_table + m_tableSize, HashItemKnownGood); }
+        iterator makeIterator(ValueType* pos) { return iterator(pos, m_table + m_tableSize, this); }
+        const_iterator makeConstIterator(ValueType* pos) const { return const_iterator(pos, m_table + m_tableSize, this); }
+        iterator makeKnownGoodIterator(ValueType* pos) { return iterator(pos, m_table + m_tableSize, this, HashItemKnownGood); }
+        const_iterator makeKnownGoodConstIterator(ValueType* pos) const { return const_iterator(pos, m_table + m_tableSize, this, HashItemKnownGood); }
 
         static const unsigned m_maxLoad = 2;
         static const unsigned m_minLoad = 6;
 
         ValueType* m_table;
         unsigned m_tableSize;
         unsigned m_tableSizeMask;
         unsigned m_keyCount;
         unsigned m_deletedCount;
+#ifdef ASSERT_ENABLED
+        unsigned m_modifications;
+#endif
 
 #if DUMP_HASHTABLE_STATS_PER_TABLE
     public:
         mutable OwnPtr<Stats> m_stats;
 #endif
 
         template<bool x, typename T, typename U, typename V, typename W, typename X, typename Y, typename Z> friend struct WeakProcessingHashTableHelper;
     };
 
     // Set all the bits to one after the most significant bit: 00110101010 -> 00111111111.
@@ skipping 34 matching lines @@
         COMPILE_ASSERT(value > (2 * size), HashTableCapacityHoldsContentSize);
     };
 
     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits, typename Allocator>
     inline HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>::HashTable()
         : m_table(0)
         , m_tableSize(0)
         , m_tableSizeMask(0)
         , m_keyCount(0)
         , m_deletedCount(0)
+#ifdef ASSERT_ENABLED
+        , m_modifications(0)
+#endif
 #if DUMP_HASHTABLE_STATS_PER_TABLE
         , m_stats(adoptPtr(new Stats))
 #endif
     {
     }
 
     inline unsigned doubleHash(unsigned key)
     {
         key = ~key + (key >> 23);
         key ^= (key << 12);
@@ skipping 57 matching lines @@
                 k = 1 | doubleHash(h);
             i = (i + k) & sizeMask;
         }
     }
 
     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits, typename Allocator>
     template<typename HashTranslator, typename T>
     inline typename HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>::LookupType HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>::lookupForWriting(const T& key)
     {
         ASSERT(m_table);
+        registerModification();

[Mikhail, 2014/04/01 09:28:33]

'lookupForWriting()' does not actually do modifications itself and it is be
called only from 'reinsert()' atm. So maybe it's better to leave
'registerModification()' only inside 'reinsert()' (and it should save a bit of
binary size =) ).

[Erik Corry, 2014/04/01 10:21:29]

Done.

 
         size_t k = 0;
         ValueType* table = m_table;
         size_t sizeMask = m_tableSizeMask;
         unsigned h = HashTranslator::hash(key);
         size_t i = h & sizeMask;
 
 #if DUMP_HASHTABLE_STATS
         atomicIncrement(&HashTableStats::numAccesses);
         int probeCount = 0;
@@ skipping 42 matching lines @@
                 k = 1 | doubleHash(h);
             i = (i + k) & sizeMask;
         }
     }
 
     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits, typename Allocator>
     template<typename HashTranslator, typename T>
     inline typename HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>::FullLookupType HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>::fullLookupForWriting(const T& key)
     {
         ASSERT(m_table);
+        registerModification();

[Mikhail, 2014/04/01 09:28:33]

I guess this can be also omitted as 'fullLookupForWriting' is only called from
'addPassingHashCode' and modification is already registered there.

[Erik Corry, 2014/04/01 10:21:29]

Done.

 
         size_t k = 0;
         ValueType* table = m_table;
         size_t sizeMask = m_tableSizeMask;
         unsigned h = HashTranslator::hash(key);
         size_t i = h & sizeMask;
 
 #if DUMP_HASHTABLE_STATS
         atomicIncrement(&HashTableStats::numAccesses);
         int probeCount = 0;
@@ skipping 126 matching lines @@
 #if DUMP_HASHTABLE_STATS_PER_TABLE
             ++perTableProbeCount;
             m_stats->recordCollisionAtCount(perTableProbeCount);
 #endif
 
             if (!k)
                 k = 1 | doubleHash(h);
             i = (i + k) & sizeMask;
         }
 
+        registerModification();
+
         if (deletedEntry) {
             initializeBucket(*deletedEntry);
             entry = deletedEntry;
             --m_deletedCount;
         }
 
         HashTranslator::translate(*entry, key, extra);
 
         ++m_keyCount;
 
@@ skipping 10 matching lines @@
             return result;
         }
 
         return AddResult(entry, true);
     }
 
     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits, typename Allocator>
     template<typename HashTranslator, typename T, typename Extra>
     typename HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>::AddResult HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>::addPassingHashCode(const T& key, const Extra& extra)
     {
+        registerModification();

[Mikhail, 2014/04/01 09:28:33]

looks like it should be consistent with the check at 'add' method and register
modifications only if a new entry (which did not exist before) is added.

[Erik Corry, 2014/04/01 10:21:29]

Done.

         if (!m_table)
             expand();
 
         FullLookupType lookupResult = fullLookupForWriting<HashTranslator>(key);
 
         ValueType* entry = lookupResult.first.first;
         bool found = lookupResult.first.second;
         unsigned h = lookupResult.second;
 
         if (found)
@@ skipping 19 matching lines @@
             return result;
         }
 
         return AddResult(entry, true);
     }
 
     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits, typename Allocator>
     inline void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>::reinsert(ValueType& entry)
     {
         ASSERT(m_table);
+        registerModification();
         ASSERT(!lookupForWriting(Extractor::extract(entry)).second);
         ASSERT(!isDeletedBucket(*(lookupForWriting(Extractor::extract(entry)).first)));
 #if DUMP_HASHTABLE_STATS
         atomicIncrement(&HashTableStats::numReinserts);
 #endif
 #if DUMP_HASHTABLE_STATS_PER_TABLE
         ++m_stats->numReinserts;
 #endif
 
         Mover<ValueType, Traits::needsDestruction>::move(entry, *lookupForWriting(Extractor::extract(entry)).first);
@@ skipping 24 matching lines @@
     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits, typename Allocator>
     template <typename HashTranslator, typename T>
     bool HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>::contains(const T& key) const
     {
         return const_cast<HashTable*>(this)->lookup<HashTranslator>(key);
     }
 
     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits, typename Allocator>
     void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>::remove(ValueType* pos)
     {
+        registerModification();
 #if DUMP_HASHTABLE_STATS
         atomicIncrement(&HashTableStats::numRemoves);
 #endif
 #if DUMP_HASHTABLE_STATS_PER_TABLE
         ++m_stats->numRemoves;
 #endif
 
         deleteBucket(*pos);
         ++m_deletedCount;
         --m_keyCount;
@@ skipping 98 matching lines @@
                 reinsert(oldTable[i]);
 
         m_deletedCount = 0;
 
         deallocateTable(oldTable, oldTableSize);
     }
 
     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits, typename Allocator>
     void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>::clear()
     {
+        registerModification();
         if (!m_table)
             return;
 
         deallocateTable(m_table, m_tableSize);
         m_table = 0;
         m_tableSize = 0;
         m_tableSizeMask = 0;
         m_keyCount = 0;
     }
 
     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits, typename Allocator>
     HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>::HashTable(const HashTable& other)
         : m_table(0)
         , m_tableSize(0)
         , m_tableSizeMask(0)
         , m_keyCount(0)
         , m_deletedCount(0)
+#ifdef ASSERT_ENABLED
+        , m_modifications(0)
+#endif
 #if DUMP_HASHTABLE_STATS_PER_TABLE
         , m_stats(adoptPtr(new Stats(*other.m_stats)))
 #endif
     {
         // Copy the hash table the dumb way, by adding each element to the new table.
         // It might be more efficient to copy the table slots, but it's not clear that efficiency is needed.
         const_iterator end = other.end();
         for (const_iterator it = other.begin(); it != end; ++it)
             add(*it);
     }
 
     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits, typename Allocator>
     void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>::swap(HashTable& other)
     {
         std::swap(m_table, other.m_table);
         std::swap(m_tableSize, other.m_tableSize);
         std::swap(m_tableSizeMask, other.m_tableSizeMask);
         std::swap(m_keyCount, other.m_keyCount);
         std::swap(m_deletedCount, other.m_deletedCount);
 
+#ifdef ASSERT_ENABLED
+        std::swap(m_modifications, other.m_modifications);
+#endif
+
 #if DUMP_HASHTABLE_STATS_PER_TABLE
         m_stats.swap(other.m_stats);
 #endif
     }
 
     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits, typename Allocator>
     HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>& HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>::operator=(const HashTable& other)
     {
         HashTable tmp(other);
         swap(tmp);
@@ skipping 17 matching lines @@
             if (table->m_table) {
                 // This just marks it live and does not push anything onto the
                 // marking stack.
                 Allocator::markNoTracing(visitor, table->m_table);
                 // Now perform weak processing (this is a no-op if the backing
                 // was accessible through an iterator and was already marked
                 // strongly).
                 for (typename HashTableType::ValueType* element = table->m_table + table->m_tableSize - 1; element >= table->m_table; element--) {
                     if (!HashTableType::isEmptyOrDeletedBucket(*element)) {
                         if (Allocator::hasDeadMember(visitor, *element)) {
+                            table->registerModification();
                             HashTableType::deleteBucket(*element); // Also calls the destructor.
                             table->m_deletedCount++;
                             table->m_keyCount--;
                             // We don't rehash the backing until the next add
                             // or delete, because that would cause allocation
                             // during GC.
                         }
                     }
                 }
             }
@@ skipping 119 matching lines @@
     inline bool operator!=(const HashTableIteratorAdapter<T, U>& a, const HashTableConstIteratorAdapter<T, U>& b)
     {
         return a.m_impl != b.m_impl;
     }
 
 } // namespace WTF
 
 #include "wtf/HashIterators.h"
 
 #endif // WTF_HashTable_h