Endless loop in deque::shrink_to_fit()

[CopaDataDevelopment]

Describe the bug

Commit c40a251887853dee30c406bbb94522b35195d912 (fixing issue #4091, merged into master in issue #4072) introduced an endless loop into deque::shrink_to_fit(). In specific constellations in regards to _First_used_block_idx, _First_unused_block_idx and _Mask the first loop for deallocating unused blocks runs infinetely.

Command-line test case

#define _CRT_SECURE_NO_WARNINGS

#include <windows.h>
#include <math.h>
#include <deque>

int main()
{
  std::deque<int> qu;

  long it = 0;
  while (1)
  {
    size_t numAlloc = rand() + 1;
    for (size_t i = 0; i < numAlloc; i++)
    {
      qu.push_back(0);
    }

    size_t numDealloc = rand() + 1;
    if (it % 100 == 0 || numDealloc > qu.size())
    {
      numDealloc = qu.size();
    }
    for (size_t i = 0; i < numDealloc; i++)
    {
      qu.pop_front();
    }
    qu.shrink_to_fit();

    printf("iteration %d: %lld\n", ++it, qu.size());
  }

  return 0;
}

After about 40 iterations deque::shrink_to_fit get's stuck.

Expected behavior

Termination condition for loop is correct so deque::shrink_to_fit() terminates.

STL version

• Visual Studio version

  Microsoft Visual Studio Enterprise 2022 
  Version 17.10

• Visual Studio version

  Microsoft Visual Studio Enterprise 2022 
  Version 17.11.1

[frederick-vs-ja]

_First_used_block_idx was incorrectly unmasked. In the problematic case, _First_used_block_idx became larger than _Mask, so the loop never ended. I'm fixing this.

[CDAlexanderW]

Can we get this fix backported to 17.11.x please?

[StephanTLavavej]

Given the timing of when this was reported, I don't believe that 17.11.x will be feasible (as it's odd-numbered and not long-term support). We can likely get it into 17.12 before GA. It may be worth backporting to 17.10, the original release where it regressed, although that's triple the work.

[dmayola]

Hello, I encountered this issue in 17.11.5, I haven't gotten into all the details or a potential fix, but we've seen some random freezes in our application due to an endless loop in:

        // deallocate unused blocks, traversing over the circular buffer until the first used block index
        for (auto _Block_idx = _First_unused_block_idx; _Block_idx != _First_used_block_idx;
             _Block_idx      = static_cast<size_type>((_Block_idx + 1) & _Mask)) {
            auto& _Block_ptr = _Map()[static_cast<_Map_difference_type>(_Block_idx)];
            if (_Block_ptr != nullptr) {
                _Getal().deallocate(_Block_ptr, _Block_size);
                _Block_ptr = nullptr;
            }
        }