<deque>: Add missed masking of _First_used_block_idx in deque::shrink_to_fit to correctly end the loop (#4955)

frederick-vs-ja · web-flow · commit 397901c5fd6d · 2024-09-19T14:02:32.000-07:00
diff --git a/stl/inc/deque b/stl/inc/deque
@@ -997,7 +997,8 @@ public:
 
         const auto _Mask = static_cast<size_type>(_Mapsize() - 1);
 
-        const auto _First_used_block_idx = static_cast<size_type>(_Myoff() / _Block_size);
+        const auto _Unmasked_first_used_block_idx = static_cast<size_type>(_Myoff() / _Block_size);
+        const auto _First_used_block_idx          = static_cast<size_type>(_Unmasked_first_used_block_idx & _Mask);
 
         // (_Myoff() + _Mysize() - 1) is for the last element, i.e. the back() of the deque.
         // Divide by _Block_size to get the unmasked index of the last used block.
@@ -1017,7 +1018,8 @@ public:
             }
         }
 
-        const auto _Used_block_count = static_cast<size_type>(_Unmasked_first_unused_block_idx - _First_used_block_idx);
+        const auto _Used_block_count =
+            static_cast<size_type>(_Unmasked_first_unused_block_idx - _Unmasked_first_used_block_idx);
 
         size_type _New_block_count = _Minimum_map_size; // should be power of 2
 
diff --git a/tests/std/tests/GH_002769_handle_deque_block_pointers/test.cpp b/tests/std/tests/GH_002769_handle_deque_block_pointers/test.cpp
@@ -7,6 +7,7 @@
 #include <deque>
 #include <iterator>
 #include <memory>
+#include <random>
 #include <type_traits>
 
 using namespace std;
@@ -328,8 +329,31 @@ void test_inconsistent_difference_types() {
     assert(counter == 0);
 }
 
+// Also test GH-4954: Endless loop in deque::shrink_to_fit()
+void test_gh_4954() {
+    deque<int> qu;
+    mt19937_64 mteng;
+
+    for (int i = 0; i < 256; ++i) {
+        const auto push_count = static_cast<size_t>((mteng() & 32767U) + 1);
+        for (size_t j = 0; j < push_count; ++j) {
+            qu.push_back(0);
+        }
+
+        auto pop_count = static_cast<size_t>((mteng() & 32767U) + 1);
+        if (i % 100 == 0 || pop_count > qu.size()) {
+            pop_count = qu.size();
+        }
+        for (size_t j = 0; j < pop_count; ++j) {
+            qu.pop_front();
+        }
+        qu.shrink_to_fit();
+    }
+}
+
 int main() {
     test_gh_2769();
     test_gh_3717();
+    test_gh_4954();
     test_inconsistent_difference_types();
 }

Original file line number	Diff line number	Diff line change
`@@ -997,7 +997,8 @@ public:`
`997`	`997`
`998`	`998`	`const auto _Mask = static_cast<size_type>(_Mapsize() - 1);`
`999`	`999`
`1000`		`- const auto _First_used_block_idx = static_cast<size_type>(_Myoff() / _Block_size);`
	`1000`	`+ const auto _Unmasked_first_used_block_idx = static_cast<size_type>(_Myoff() / _Block_size);`
	`1001`	`+ const auto _First_used_block_idx = static_cast<size_type>(_Unmasked_first_used_block_idx & _Mask);`
`1001`	`1002`
`1002`	`1003`	`// (_Myoff() + _Mysize() - 1) is for the last element, i.e. the back() of the deque.`
`1003`	`1004`	`// Divide by _Block_size to get the unmasked index of the last used block.`
`@@ -1017,7 +1018,8 @@ public:`
`1017`	`1018`	`}`
`1018`	`1019`	`}`
`1019`	`1020`
`1020`		`- const auto _Used_block_count = static_cast<size_type>(_Unmasked_first_unused_block_idx - _First_used_block_idx);`
	`1021`	`+ const auto _Used_block_count =`
	`1022`	`+ static_cast<size_type>(_Unmasked_first_unused_block_idx - _Unmasked_first_used_block_idx);`
`1021`	`1023`
`1022`	`1024`	`size_type _New_block_count = _Minimum_map_size; // should be power of 2`
`1023`	`1025`