How to get a stable version of mutiple values at a particular time without lock?

Question

I was reading the source code of ConcurrentQueue, here are some code:

/// <summary>
/// Store the position of the current head and tail positions.
/// </summary>
/// <param name="head">return the head segment</param>
/// <param name="tail">return the tail segment</param>
/// <param name="headLow">return the head offset, value range [0, SEGMENT_SIZE]</param>
/// <param name="tailHigh">return the tail offset, value range [-1, SEGMENT_SIZE-1]</param>
private void GetHeadTailPositions(out Segment head, out Segment tail,
    out int headLow, out int tailHigh)
{
    head = m_head;
    tail = m_tail;
    headLow = head.Low;
    tailHigh = tail.High;
    SpinWait spin = new SpinWait();

    //we loop until the observed values are stable and sensible.  
    //This ensures that any update order by other methods can be tolerated.
    while (
        //if head and tail changed, retry
        head != m_head || tail != m_tail
        //if low and high pointers, retry
        || headLow != head.Low || tailHigh != tail.High
        //if head jumps ahead of tail because of concurrent grow and dequeue, retry
        || head.m_index > tail.m_index)
    {
        spin.SpinOnce();
        head = m_head;
        tail = m_tail;
        headLow = head.Low;
        tailHigh = tail.High;
    }
}

GetHeadTailPositions() may want to get 4 variables at a particular time, however, there are 4 compare in the 'where' loop, think about the below sequence:

while (
    // 1. head equals m_head
    head != m_head 
    // 2. m_head was changed while other variables were unchanged
    || tail != m_tail || headLow != head.Low || tailHigh != tail.High || head.m_index > tail.m_index)
{
    // ...
}

then we get a unstable version of these variables. Is this method stable? How to get a stable version of mutiple values at a particular time without lock?

score 3 · Answer 1 · answered Jan 10 '23 at 03:29

It's a similar idea to a SeqLock: read a wide thing too large to be naturally atomic and then check for "tearing". Retry until you see the same sequence number before and after (with odd meaning an update is in progress). See Implementing 64 bit atomic counter with 32 bit atomics for a C++ example, and A readers/writer lock... without having a lock for the readers? for more about when SeqLock vs. RCU are appropriate.

But they're not using a separate sequence counter; they're sort of using all members as sequence counters, reading them each a 2nd time to see if any of them changed. Since it's a queue, head and tail increase monotonically until wrap-around, so you don't have ABA problems. That's what makes it safe in this case, not safe in general.

Also, we're not trying to get atomicity for updates to multiple members. If a writer does an InterlockedIncrement on headLow and head, we might get a consistent snapshot of the state after one increment, before the other. (A SeqLock could detect that if you needed it.)

PS: I didn't look at the queue implementation this is part of, so IDK if my example of a writer updating both headLow and head made sense. I think any kind of queue will avoid repeating a value of any member for long enough to be safe against ABA problems in practice, especially if it's not a linked list freeing and reusing nodes right away.

How to get a stable version of mutiple values at a particular time without lock?

1 Answers1

Linked