Fix ConcurrentQueue.TryDequeue spuriously reporting empty during a segment freeze

Project: dotnet/runtime | Language: C# | Concepts: concurrency, data-structures, error-handling, testing-strategy | Difficulty: senior
Link: https://github.com/dotnet/runtime/pull/132737

The problem

ConcurrentQueue<T> could incorrectly report that the queue was empty during a rare race condition when a segment was being frozen for enqueues. Specifically, if a dequeuer thread observed the _frozenForEnqueues flag set to true before the Tail pointer had been bumped by FreezeOffset, it could subtract FreezeOffset from a not-yet-bumped tail and falsely conclude the segment was empty, even though there were still items present.

Why it's non-trivial

A naive fix might try to add more memory barriers or make the flag atomic, but the root cause is the publication order between the flag (_frozenForEnqueues) and the tail pointer. Memory fences alone do not guarantee the correct visibility order between threads, especially under heavy concurrency. The fix must ensure that any thread observing _frozenForEnqueues == true is also guaranteed to see the updated tail value.

The approach

1. Fixing the publication order in EnsureFrozenForEnqueues

Previously, the code set the frozen flag before updating the tail:

-                _frozenForEnqueues = true;
-                Interlocked.Add(ref _headAndTail.Tail, FreezeOffset);
+                // Bump the Tail before setting the flag, as TryDequeue reads the flag and then
+                // the Tail: a set flag must guarantee that the Tail read includes the FreezeOffset.
+                Interlocked.Add(ref _headAndTail.Tail, FreezeOffset);
+                _frozenForEnqueues = true;

Annotation:
This change ensures that once _frozenForEnqueues is observed as true, any subsequent read of the tail will see the value after the freeze offset is applied. This closes the race window where a thread could see the flag set but not the updated tail.

2. Strengthening the read order in TryDequeue and TryPeek

The reads of the flag and tail are reordered to ensure the flag is read with a volatile read, and the tail is read after:

-                    bool frozen = _frozenForEnqueues;
-                    int currentTail = Volatile.Read(ref _headAndTail.Tail);
+                    bool frozen = Volatile.Read(ref _frozenForEnqueues);
+                    int currentTail = _headAndTail.Tail;

Annotation:
Reading _frozenForEnqueues with Volatile.Read ensures the latest value is seen, and reading the tail after the flag ensures the correct order: if the flag is true, the tail must reflect the freeze. This pattern is applied to both TryDequeue and TryPeek.

3. Adding a regression test

A new test is added to ensure the bug does not regress:

[ConditionalFact(typeof(PlatformDetection), nameof(PlatformDetection.IsMultithreadingSupported))]
public void Concurrent_TryDequeue_DoesNotReportEmptyWhileItemsAreQueued()
{
    // Each worker holds at most one of the seeded items at a time, so an item is always
    // queued and TryDequeue must never report empty
    const int WorkerCount = 4;

    var q = new ConcurrentQueue<object>();
    for (int i = 0; i < WorkerCount; i++) q.Enqueue(new object());

    bool stop = false;
    int falseEmpties = 0;

    // Snapshotting freezes the tail segment, racing the freeze against the empty check
    Task snapshotter = Task.Run(() =>
    {
        while (!Volatile.Read(ref stop)) q.ToArray();
    });

    // Workers dequeue and immediately re-enqueue, counting any spurious empty
    Task[] workers = new Task[WorkerCount];
    for (int i = 0; i < WorkerCount; i++)
    {
        workers[i] = Task.Run(() =>
        {
            while (!Volatile.Read(ref stop))
            {
                if (!q.TryDequeue(out object item))
                {
                    Interlocked.Increment(ref falseEmpties);
                    item = new object();
                }
                q.Enqueue(item);
            }
        });
    }

    Thread.Sleep(TimeSpan.FromMilliseconds(200));
    Volatile.Write(ref stop, true);
    Task.WaitAll(workers);
    snapshotter.Wait();

    Assert.Equal(0, falseEmpties);
}

Annotation:
This test sets up a scenario with multiple threads dequeuing and re-enqueuing items while another thread repeatedly snapshots the queue (which triggers segment freezes). If the bug is present, TryDequeue can spuriously report empty, incrementing falseEmpties. The test asserts this never happens.

From the review thread

VSadov:
nothing seems to guarantee that frozen is read before Tail in the following:

bool frozen = _frozenForEnqueues;                       // reads flag first
long currentTail = Volatile.Read(ref _headAndTail.Tail); // reads tail second

can there still be a problem for the ordering that we want, if frozen is read after Tail?

AlanLiu90:
I did some additional testing today and found a race that my proposed fix doesn't cover:

1. Thread-1 is inside TryDequeue, in the diff < 0 branch, and has not yet read _frozenForEnqueues
2. Other threads enqueue and dequeue multiple items, so both Head and Tail advance. Assume Tail advances to a value 64 (FreezeOffset) greater than the Head that Thread-1 read, and the segment becomes full
3. Thread-2 tries to enqueue a new item, fails because the segment is full, and calls EnsureFrozenForEnqueues, which sets _frozenForEnqueues to true. It has not yet executed Interlocked.Add(ref _headAndTail.Tail, FreezeOffset)
4. Thread-1 reads _frozenForEnqueues and Tail. Since frozen && currentTail - FreezeOffset - currentHead == 0 is true, it returns false even though the segment still contains items

Apologies for the back and forth — @kafka1991's approach looks like the safer one to me. @VSadov Let me know if you'd still like the == change as diff suggestions on top of it.

Takeaways

• In concurrent data structures, the publication order of state changes is critical—flags indicating a state change must only be set after all dependent data is fully published.
• Use volatile reads and writes to ensure correct visibility and ordering of memory operations between threads, but do not rely solely on memory barriers to enforce logical dependencies.
• Regression tests that reproduce concurrency bugs are essential; they should be designed to maximize the probability of hitting race conditions, even if the bug is rare.