try_enqueue() fail when queue size went down to 0

[solokacher]

Hi, I have the following code snippet that is stuck in the loop of doing try_enqueue(), and hence some remaining threads doing try_dequeue(). (not always repros, had to run it in a bash loop)

  ConcurrentQueue<int> queue(100);

  for (auto i = 0; i < 1000; ++i) {
    threads.push_back(thread([i, &queue, &bitmap, &count]() {
      auto index = i;
      while (!queue.try_enqueue(index)) {
        yield();
      }
    }));

    threads.push_back(thread([&queue, &bitmap, &count]() {
      int index = -1;
      while (!queue.try_dequeue(index)) {
        yield();
      }
    }));
  }

  for (auto& thread : threads) {
    thread.join();
  }

At the time of hang, I could see the queue.size_approx() is 0, but try_enqueue() cannot find a block to use so it fails all the time. My assumption is that we have freelist that holds the blocks, and size 0 implies freelist should hold something.

I feel that I made some wrong assumptions around the queue's internal logic. Would you please correct me :) and help me understand why there's a hang here.

When removing the initial size 100 from the constructor, and guarding the queue size to 100 with my own atomic<int>, the hang seems to go away.

Code compiled with g++ (Ubuntu 9.4.0-1ubuntu1~16.04) 9.4.0

[Homqyy]

Hi, I have the following code snippet that is stuck in the loop of doing try_enqueue(), and hence some remaining threads doing try_dequeue(). (not always repros, had to run it in a bash loop)

  ConcurrentQueue<int> queue(100);

  for (auto i = 0; i < 1000; ++i) {
    threads.push_back(thread([i, &queue, &bitmap, &count]() {
      auto index = i;
      while (!queue.try_enqueue(index)) {
        yield();
      }
    }));

    threads.push_back(thread([&queue, &bitmap, &count]() {
      int index = -1;
      while (!queue.try_dequeue(index)) {
        yield();
      }
    }));
  }

  for (auto& thread : threads) {
    thread.join();
  }

At the time of hang, I could see the queue.size_approx() is 0, but try_enqueue() cannot find a block to use so it fails all the time. My assumption is that we have freelist that holds the blocks, and size 0 implies freelist should hold something.

I feel that I made some wrong assumptions around the queue's internal logic. Would you please correct me :) and help me understand why there's a hang here.

When removing the initial size 100 from the constructor, and guarding the queue size to 100 with my own atomic<int>, the hang seems to go away.

Code compiled with g++ (Ubuntu 9.4.0-1ubuntu1~16.04) 9.4.0

you can try to modify 'FreeList::add_knowing_refcount_is_zero(N *node)' function as below:

inline void add_knowing_refcount_is_zero(N* node)
{
    // TODO: 1. delete it
    // auto head = freeListHead.load(std::memory_order_relaxed);

    while (true) {
        auto head = freeListHead.load(std::memory_order_relaxed); // TODO: 2. add it

        node->freeListNext.store(head, std::memory_order_relaxed);
        node->freeListRefs.store(1, std::memory_order_release);
        if (!freeListHead.compare_exchange_strong(head, node, std::memory_order_release, std::memory_order_relaxed)) {
            // Hmm, the add failed, but we can only try again when the refcount goes back to zero
            if (node->freeListRefs.fetch_add(SHOULD_BE_ON_FREELIST - 1, std::memory_order_release) == 1) {
                continue;
            }
        }
        return;
    }
}

[rpadmanabhan]

I am seeing something similar, try_enqueue_bulk hangs (i.e. always fails) when I pre-initialize the queue to a particular size. I am using explicit producers. I noticed this when I started using more threads in my program (~50+ threads)

[cameron314]

Sorry for the long delay, this one initially slipped through the cracks. I haven't had time to dig into this properly, just wanted to let you know it's not forgotten.

[trapexit]

I'm seeing this as well. Unfortunately, I'm not able to reproduce it myself but a user can do so consistently.