Source/wtf/HashTable.h - Issue 219413002: Hash iterators: Check for concurrent modification and fix 1 place where it happened

Unified Diff: Source/wtf/HashTable.h

Issue 219413002: Hash iterators: Check for concurrent modification and fix 1 place where it happened (Closed) Base URL: svn://svn.chromium.org/blink/trunk

Patch Set: Created 6 years, 9 months ago

Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.

Jump to:

View side-by-side diff with in-line comments

Download patch

Index: Source/wtf/HashTable.h

diff --git a/Source/wtf/HashTable.h b/Source/wtf/HashTable.h

index 566fda8164554a8c67cf060641d6f9965f5e03b9..5259afb6a0b5fdd18b25fdf70567b3d443f69565 100644

--- a/Source/wtf/HashTable.h

+++ b/Source/wtf/HashTable.h

@@ -85,17 +85,32 @@ namespace WTF {

++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)

+#ifndef NDEBUG

+ , 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)

+#ifndef NDEBUG

Mikhail 2014/03/31 14:08:09 Since the actual check is assertion, maybe it's be

Erik Corry 2014/03/31 19:45:38 Done.

+ , m_container(container)

+ , m_containerModifications(container->modifications())

+#endif

{

}

+ void checkModifications() const

+ {

+ ASSERT(m_containerModifications == m_container->modifications());

+ }

public:

HashTableConstIterator()

{

@@ -103,6 +118,7 @@ namespace WTF {

GetType get() const

{

+ checkModifications();

return m_position;

}

typename Traits::IteratorConstReferenceType operator*() const { return Traits::getToReferenceConstConversion(get()); }

@@ -111,6 +127,7 @@ namespace WTF {

const_iterator& operator++()

{

ASSERT(m_position != m_endPosition);

+ checkModifications();

++m_position;

skipEmptyBuckets();

return *this;

@@ -139,11 +156,16 @@ namespace WTF {

private:

PointerType m_position;

PointerType m_endPosition;

+#ifndef NDEBUG

+ 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;

@@ -152,8 +174,8 @@ namespace WTF {

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() { }

@@ -349,6 +371,20 @@ namespace WTF {

void trace(typename Allocator::Visitor*);

+#ifdef NDEBUG

+ int64_t modifications() const { return 0; }

+ void registerModification() { }

+ void checkModifications(int64_t mods) const { }

Mads Ager (chromium) 2014/03/31 14:18:47 mods -> modifications (or better, remove the name)

Erik Corry 2014/03/31 19:45:38 gone

+#else

+ int64_t modifications() const { return m_modifications; }

+ void registerModification() { m_modifications++; }

Mikhail 2014/03/31 14:08:09 modified() ?

Erik Corry 2014/03/31 19:45:38 That looks more like a question than an action to

+ // 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.

+ void checkModifications(int64_t mods) const { ASSERT(mods == m_modifications); }

Mikhail 2014/03/31 14:08:09 is this method used?

Mads Ager (chromium) 2014/03/31 14:18:47 mods -> modifications (but as Mikhail writes, it l

Erik Corry 2014/03/31 19:45:38 It's not used yet, so I removed it for now.

+#endif

private:

static ValueType* allocateTable(unsigned size);

static void deallocateTable(ValueType* table, unsigned size);

@@ -377,10 +413,10 @@ namespace WTF {

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;

@@ -390,6 +426,9 @@ namespace WTF {

unsigned m_tableSizeMask;

unsigned m_keyCount;

unsigned m_deletedCount;

+#ifndef NDEBUG

+ unsigned m_modifications;

+#endif

#if DUMP_HASHTABLE_STATS_PER_TABLE

public:

@@ -444,6 +483,9 @@ namespace WTF {

, m_tableSizeMask(0)

, m_keyCount(0)

, m_deletedCount(0)

+#ifndef NDEBUG

+ , m_modifications(0)

+#endif

#if DUMP_HASHTABLE_STATS_PER_TABLE

, m_stats(adoptPtr(new Stats))

#endif

@@ -521,6 +563,7 @@ namespace WTF {

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();

size_t k = 0;

ValueType* table = m_table;

@@ -583,6 +626,7 @@ namespace WTF {

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();

size_t k = 0;

ValueType* table = m_table;

@@ -669,6 +713,7 @@ namespace WTF {

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>::add(const T& key, const Extra& extra)

{

+ registerModification();

if (!m_table)

expand();

@@ -759,6 +804,7 @@ namespace WTF {

template<typename HashTranslator, typename T, typename Extra>

{

+ registerModification();

if (!m_table)

expand();

@@ -798,6 +844,7 @@ namespace WTF {

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

@@ -842,6 +889,7 @@ namespace WTF {

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

@@ -960,6 +1008,7 @@ namespace WTF {

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;

@@ -977,6 +1026,9 @@ namespace WTF {

, m_tableSizeMask(0)

, m_keyCount(0)

, m_deletedCount(0)

+#ifndef NDEBUG

+ , m_modifications(0)

+#endif

#if DUMP_HASHTABLE_STATS_PER_TABLE

, m_stats(adoptPtr(new Stats(*other.m_stats)))

#endif

@@ -997,6 +1049,12 @@ namespace WTF {

std::swap(m_keyCount, other.m_keyCount);

std::swap(m_deletedCount, other.m_deletedCount);

+#ifndef NDEBUG

+ int64_t tmpModifications = m_modifications;

+ m_modifications = other.m_modifications;

+ other.m_modifications = tmpModifications;

Mikhail 2014/03/31 14:08:09 why not 'swap' ?

Erik Corry 2014/03/31 19:45:38 Done.

+#endif

#if DUMP_HASHTABLE_STATS_PER_TABLE

m_stats.swap(other.m_stats);

#endif

@@ -1034,6 +1092,7 @@ namespace WTF {

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--;

« no previous file with comments | « Source/core/animation/DocumentTimeline.cpp ('k') | no next file » | no next file with comments »