From: Jeff Preshing Date: Sat, 30 Dec 2017 16:33:49 +0000 (-0500) Subject: Fix #31: Entries can disappear when deleted key is reassigned during a migration X-Git-Url: http://plrg.eecs.uci.edu/git/?p=junction.git;a=commitdiff_plain;h=fdaa2b5b2a5c1d2e40a7b8ffb1616933c9feda6d;hp=14f74b75cedcd90e8fb735d6c6845f9f4c022785 Fix #31: Entries can disappear when deleted key is reassigned during a migration Bug was in the Mutator classes. In the Mutator constructor: If an existing cell was found, and that cell's value was Redirect, Mutator::m_value was assigned to Redirect. The constructor would then loop a second time. On the second iteration of the loop, if no existing cell was found, a new cell was inserted, but Mutator::m_value was left set to Redirect. This left the Mutator in an inconsistent state, so that on the next exchangeValue(), it thought there was a racing write to the same key (which there wasn't), and neglected to write the new value. Fix is to avoid ever setting Mutator::m_value to Redirect. --- diff --git a/.gitignore b/.gitignore index 3c10c08..adf8787 100644 --- a/.gitignore +++ b/.gitignore @@ -1,3 +1,4 @@ *build*/ CMakeLists.txt.user *~ +*.log diff --git a/junction/ConcurrentMap_Grampa.h b/junction/ConcurrentMap_Grampa.h index 8422b22..dc4749c 100644 --- a/junction/ConcurrentMap_Grampa.h +++ b/junction/ConcurrentMap_Grampa.h @@ -280,9 +280,12 @@ public: m_cell = Details::find(hash, m_table, m_sizeMask); if (!m_cell) return; - m_value = m_cell->value.load(turf::Consume); - if (m_value != Value(ValueTraits::Redirect)) - return; // Found an existing value + Value value = m_cell->value.load(turf::Consume); + if (value != Value(ValueTraits::Redirect)) { + // Found an existing value + m_value = value; + return; + } // We've encountered a Redirect value. Help finish the migration. TURF_TRACE(ConcurrentMap_Grampa, 11, "[Mutator] find was redirected", uptr(m_table), 0); m_table->jobCoordinator.participate(); @@ -307,13 +310,15 @@ public: } case Details::InsertResult_AlreadyFound: { // The hash was already found in the table. - m_value = m_cell->value.load(turf::Consume); - if (m_value == Value(ValueTraits::Redirect)) { + Value value = m_cell->value.load(turf::Consume); + if (value == Value(ValueTraits::Redirect)) { // We've encountered a Redirect value. TURF_TRACE(ConcurrentMap_Grampa, 13, "[Mutator] insertOrFind was redirected", uptr(m_table), uptr(m_value)); break; // Help finish the migration. } - return; // Found an existing value + // Found an existing value + m_value = value; + return; } case Details::InsertResult_Overflow: { Details::beginTableMigration(m_map, m_table, overflowIdx); diff --git a/junction/ConcurrentMap_Leapfrog.h b/junction/ConcurrentMap_Leapfrog.h index 4850f0d..8edb1fb 100644 --- a/junction/ConcurrentMap_Leapfrog.h +++ b/junction/ConcurrentMap_Leapfrog.h @@ -81,9 +81,12 @@ public: m_cell = Details::find(hash, m_table); if (!m_cell) return; - m_value = m_cell->value.load(turf::Consume); - if (m_value != Value(ValueTraits::Redirect)) - return; // Found an existing value + Value value = m_cell->value.load(turf::Consume); + if (value != Value(ValueTraits::Redirect)) { + // Found an existing value + m_value = value; + return; + } // We've encountered a Redirect value. Help finish the migration. TURF_TRACE(ConcurrentMap_Leapfrog, 1, "[Mutator] find was redirected", uptr(m_table), 0); m_table->jobCoordinator.participate(); @@ -105,13 +108,15 @@ public: } case Details::InsertResult_AlreadyFound: { // The hash was already found in the table. - m_value = m_cell->value.load(turf::Consume); - if (m_value == Value(ValueTraits::Redirect)) { + Value value = m_cell->value.load(turf::Consume); + if (value == Value(ValueTraits::Redirect)) { // We've encountered a Redirect value. TURF_TRACE(ConcurrentMap_Leapfrog, 3, "[Mutator] insertOrFind was redirected", uptr(m_table), uptr(m_value)); break; // Help finish the migration. } - return; // Found an existing value + // Found an existing value + m_value = value; + return; } case Details::InsertResult_Overflow: { // Unlike ConcurrentMap_Linear, we don't need to keep track of & pass a "mustDouble" flag. diff --git a/junction/ConcurrentMap_Linear.h b/junction/ConcurrentMap_Linear.h index 6e74efa..6799c91 100644 --- a/junction/ConcurrentMap_Linear.h +++ b/junction/ConcurrentMap_Linear.h @@ -81,9 +81,12 @@ public: m_cell = Details::find(hash, m_table); if (!m_cell) return; - m_value = m_cell->value.load(turf::Consume); - if (m_value != Value(ValueTraits::Redirect)) - return; // Found an existing value + Value value = m_cell->value.load(turf::Consume); + if (value != Value(ValueTraits::Redirect)) { + // Found an existing value + m_value = value; + return; + } // We've encountered a Redirect value. Help finish the migration. TURF_TRACE(ConcurrentMap_Linear, 1, "[Mutator] find was redirected", uptr(m_table), 0); m_table->jobCoordinator.participate(); @@ -105,13 +108,15 @@ public: } case Details::InsertResult_AlreadyFound: { // The hash was already found in the table. - m_value = m_cell->value.load(turf::Consume); - if (m_value == Value(ValueTraits::Redirect)) { + Value value = m_cell->value.load(turf::Consume); + if (value == Value(ValueTraits::Redirect)) { // We've encountered a Redirect value. TURF_TRACE(ConcurrentMap_Linear, 3, "[Mutator] insertOrFind was redirected", uptr(m_table), uptr(m_value)); break; // Help finish the migration. } - return; // Found an existing value + // Found an existing value + m_value = value; + return; } case Details::InsertResult_Overflow: { Details::beginTableMigration(m_map, m_table, mustDouble); diff --git a/samples/MapCorrectnessTests/MapCorrectnessTests.cpp b/samples/MapCorrectnessTests/MapCorrectnessTests.cpp index 3fee1b3..bfd22f2 100644 --- a/samples/MapCorrectnessTests/MapCorrectnessTests.cpp +++ b/samples/MapCorrectnessTests/MapCorrectnessTests.cpp @@ -15,6 +15,7 @@ #include "TestInsertSameKeys.h" #include "TestInsertDifferentKeys.h" #include "TestChurn.h" +#include "TestDoubleAssign.h" #include #include // for GrampaStats @@ -26,11 +27,13 @@ int main(int argc, const char** argv) { TestInsertSameKeys testInsertSameKeys(env); TestInsertDifferentKeys testInsertDifferentKeys(env); TestChurn testChurn(env); + TestDoubleAssign testDoubleAssign(env); for (;;) { for (ureg c = 0; c < IterationsPerLog; c++) { testInsertSameKeys.run(); testInsertDifferentKeys.run(); testChurn.run(); + testDoubleAssign.run(); } turf::Trace::Instance.dumpStats(); diff --git a/samples/MapCorrectnessTests/TestDoubleAssign.h b/samples/MapCorrectnessTests/TestDoubleAssign.h new file mode 100644 index 0000000..7a924c4 --- /dev/null +++ b/samples/MapCorrectnessTests/TestDoubleAssign.h @@ -0,0 +1,69 @@ +/*------------------------------------------------------------------------ + Junction: Concurrent data structures in C++ + Copyright (c) 2016, 2017 Jeff Preshing + + Distributed under the Simplified BSD License. + Original location: https://github.com/preshing/junction + + This software is distributed WITHOUT ANY WARRANTY; without even the + implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. + See the LICENSE file for more information. +------------------------------------------------------------------------*/ + +#ifndef SAMPLES_MAPCORRECTNESSTESTS_TESTDOUBLEASSIGN_H +#define SAMPLES_MAPCORRECTNESSTESTS_TESTDOUBLEASSIGN_H + +#include +#include "TestEnvironment.h" +#include + +class TestDoubleAssign { +public: + static const ureg KeysToInsert = 1000; + TestEnvironment& m_env; + MapAdapter::Map* m_map; + turf::Atomic m_index; + + TestDoubleAssign(TestEnvironment& env) : m_env(env), m_map(NULL), m_index(0) { + } + + void doubleAssignKeys(ureg threadIndex) { + for (;;) { + u32 key = m_index.fetchAdd(1, turf::Relaxed); + if (key >= KeysToInsert + 2) + break; + + m_map->assign(key, (void*) (key * 20)); + m_map->erase(key); + m_map->assign(key, (void*) (key * 20)); + } + m_env.threads[threadIndex].update(); + } + + void checkMapContents() { +#if TEST_CHECK_MAP_CONTENTS + for (MapAdapter::Map::Iterator iter(*m_map); iter.isValid(); iter.next()) { + u32 key = iter.getKey(); + if (iter.getValue() != (void*) (key * 20)) + TURF_DEBUG_BREAK(); + } + + for (ureg i = 2; i < KeysToInsert + 2; i++) { + auto r = m_map->find(i); + if (r.getValue() != (void*) (i * 20)) + TURF_DEBUG_BREAK(); + } +#endif + } + + void run() { + m_map = new MapAdapter::Map(MapAdapter::getInitialCapacity(KeysToInsert)); + m_index = 2; + m_env.dispatcher.kick(&TestDoubleAssign::doubleAssignKeys, *this); + checkMapContents(); + delete m_map; + m_map = NULL; + } +}; + +#endif // SAMPLES_MAPCORRECTNESSTESTS_TESTDOUBLEASSIGN_H