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 3c10c0850ce969d70c6d6a99bf8cd3113ddf93f5..adf8787a1e091168002d6e141e40bbd9eb013dda 100644 (file)
--- a/.gitignore
+++ b/.gitignore
@@ -1,3 +1,4 @@
 *build*/
 CMakeLists.txt.user
 *~
 *build*/
 CMakeLists.txt.user
 *~

+*.log

diff --git a/junction/ConcurrentMap_Grampa.h b/junction/ConcurrentMap_Grampa.h
index 8422b2261a278855a214f6595dfb02c1dcad777f..dc4749cb60128095b9f508b1c3d07681dec9ea54 100644 (file)
--- 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_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();
                 // 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.
                     }
                     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.
                         }
                             // 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);
                     }
                     case Details::InsertResult_Overflow: {
                         Details::beginTableMigration(m_map, m_table, overflowIdx);

diff --git a/junction/ConcurrentMap_Leapfrog.h b/junction/ConcurrentMap_Leapfrog.h
index 4850f0db0006fd822283ba0584ede5349288901b..8edb1fbd9081b0e5f04112e5aa8bd6d2b49f24f0 100644 (file)
--- 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_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();
                 // 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.
                 }
                 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.
                     }
                         // 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.
                 }
                 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 6e74efacf0a2b5ddb67b5c9882de1d354ec6cf3a..6799c916e557aaf2a16e70b0b5c8c887e2a0764b 100644 (file)
--- 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_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();
                 // 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.
                 }
                 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.
                     }
                         // 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);
                 }
                 case Details::InsertResult_Overflow: {
                     Details::beginTableMigration(m_map, m_table, mustDouble);

diff --git a/samples/MapCorrectnessTests/MapCorrectnessTests.cpp b/samples/MapCorrectnessTests/MapCorrectnessTests.cpp
index 3fee1b38158a84d0a6a80905efe14d4c09e3f777..bfd22f229ffe774deedab7544c1b3eb3915bc3f9 100644 (file)
--- a/samples/MapCorrectnessTests/MapCorrectnessTests.cpp
+++ b/samples/MapCorrectnessTests/MapCorrectnessTests.cpp
@@ -15,6 +15,7 @@
 #include "TestInsertSameKeys.h"
 #include "TestInsertDifferentKeys.h"
 #include "TestChurn.h"
 #include "TestInsertSameKeys.h"
 #include "TestInsertDifferentKeys.h"
 #include "TestChurn.h"

+#include "TestDoubleAssign.h"

 #include <turf/extra/Options.h>
 #include <junction/details/Grampa.h> // for GrampaStats
 
 #include <turf/extra/Options.h>
 #include <junction/details/Grampa.h> // for GrampaStats
 


@@ -26,11 +27,13 @@ int main(int argc, const char** argv) {
     TestInsertSameKeys testInsertSameKeys(env);
     TestInsertDifferentKeys testInsertDifferentKeys(env);
     TestChurn testChurn(env);
     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();
     for (;;) {
         for (ureg c = 0; c < IterationsPerLog; c++) {
             testInsertSameKeys.run();
             testInsertDifferentKeys.run();
             testChurn.run();

+            testDoubleAssign.run();

         }
         turf::Trace::Instance.dumpStats();
 
         }
         turf::Trace::Instance.dumpStats();
 

diff --git a/samples/MapCorrectnessTests/TestDoubleAssign.h b/samples/MapCorrectnessTests/TestDoubleAssign.h
new file mode 100644 (file)
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 <junction/Core.h>
+#include "TestEnvironment.h"
+#include <turf/extra/Random.h>
+
+class TestDoubleAssign {
+public:
+    static const ureg KeysToInsert = 1000;
+    TestEnvironment& m_env;
+    MapAdapter::Map* m_map;
+    turf::Atomic<u32> 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