Fix possible infinite loop

[junction.git] / junction / ConcurrentMap_Grampa.h

diff --git a/junction/ConcurrentMap_Grampa.h b/junction/ConcurrentMap_Grampa.h
index 8d67f2219650c9a4b5603617489f3d95b46fc94d..cc2de0ff478b2821bff86455ec20c3ecfa0b7722 100644 (file)
--- a/junction/ConcurrentMap_Grampa.h
+++ b/junction/ConcurrentMap_Grampa.h
@@ -295,6 +295,7 @@ public:
             TURF_TRACE(ConcurrentMap_Grampa, 12, "[Mutator] insert constructor called", uptr(map.m_root.load(turf::Relaxed)),
                        uptr(key));
             Hash hash = KeyTraits::hash(key);
+            bool mustDouble = false;
             for (;;) {
                 if (!m_map.locateTable(m_table, m_sizeMask, hash)) {
                     m_map.createInitialTable(Details::MinTableSize);
@@ -316,13 +317,15 @@ public:
                         return; // Found an existing value
                     }
                     case Details::InsertResult_Overflow: {
-                        Details::beginTableMigration(m_map, m_table, overflowIdx);
+                        Details::beginTableMigration(m_map, m_table, overflowIdx, mustDouble);
                         break;
                     }
                     }
                     // A migration has been started (either by us, or another thread). Participate until it's complete.
                     m_table->jobCoordinator.participate();
                 }
+                // If we still overflow after this, avoid an infinite loop by forcing the next table to double.
+                mustDouble = true;
                 // Try again using the latest root.
             }
         }
@@ -337,6 +340,7 @@ public:
             TURF_ASSERT(desired != Value(ValueTraits::NullValue));
             TURF_ASSERT(m_cell); // Cell must have been found or inserted
             TURF_TRACE(ConcurrentMap_Grampa, 14, "[Mutator::exchangeValue] called", uptr(m_table), uptr(m_value));
+            bool mustDouble = false;
             for (;;) {
                 Value oldValue = m_value;
                 if (m_cell->value.compareExchangeStrong(m_value, desired, turf::ConsumeRelease)) {
@@ -367,7 +371,7 @@ public:
                     m_table->jobCoordinator.participate();
                     // Try again in the latest table.
                     // FIXME: locateTable() could return false if the map is concurrently cleared (m_root set to 0).
-                    // This is not concern yet since clear() is not implemented.
+                    // This is not a concern yet since clear() is not implemented.
                     bool exists = m_map.locateTable(m_table, m_sizeMask, hash);
                     TURF_ASSERT(exists);
                     TURF_UNUSED(exists);
@@ -387,12 +391,14 @@ public:
                     case Details::InsertResult_Overflow:
                         TURF_TRACE(ConcurrentMap_Grampa, 20, "[Mutator::exchangeValue] overflow after redirect", uptr(m_table),
                                    overflowIdx);
-                        Details::beginTableMigration(m_map, m_table, overflowIdx);
+                        Details::beginTableMigration(m_map, m_table, overflowIdx, mustDouble);
                         break;
                     }
                     // We were redirected... again
                 }
             breakOuter:;
+                // If we still overflow after this, avoid an infinite loop by forcing the next table to double.
+                mustDouble = true;
                 // Try again in the new table.
             }
         }