How does this MSDN CompareExchange sample not need a volatile read?

Question

I was looking for a thread-safe counter implementation using Interlocked that supported incrementing by arbitrary values, and found this sample straight from the Interlocked.CompareExchange documentation (slightly changed for simplicity):

private int totalValue = 0;

public int AddToTotal(int addend)
{
    int initialValue, computedValue;
    do
    {
        // How can we get away with not using a volatile read of totalValue here?
        // Shouldn't we use CompareExchange(ref TotalValue, 0, 0)
        // or Thread.VolatileRead
        // or declare totalValue to be volatile?           
        initialValue = totalValue;

        computedValue = initialValue + addend;

    } while (initialValue != Interlocked.CompareExchange(
        ref totalValue, computedValue, initialValue));

    return computedValue;
}

 public int Total
 {
    // This looks *really* dodgy too, but isn't 
    // the target of my question.
    get { return totalValue; }
 }

I get what this code is trying to do, but I'm not sure how it can get away with not using a volatile read of the shared variable when assigning to the temporary variable that is added to.

Is there a chance that initialValue will hold a stale value throughout the loop, making the function never return? Or does the memory-barrier (?) in CompareExchange eliminate any such possibility? Any insight would be appreciated.

EDIT: I should clarify that I understand that if CompareExchange caused the subsequent read of totalValue to be up to date as of the last CompareExchange call, then this code would be fine. But is that guaranteed?

Answer 1

Edit:

Someone gave me an upvote after all this time so I re-read the question and the answer and noticed a problem.

I either didn't know about introduced reads or it hasn't crossed my mind. Assuming Interlocked.CompareExchange doesn't introduce any barriers (since it's not documented anywhere), the compiler is allowed to transform your AddToTotal method into the following broken version, where the last two arguments to Interlocked.CompareExchange could see different totalValue values!

public int AddToTotal(int addend)
{
    int initialValue;
    do
    {        
        initialValue = totalValue;
    } while (initialValue != Interlocked.CompareExchange(
        ref totalValue, totalValue + addend, totalValue));

    return initialValue + addend;
}

For this reason, you can use Volatile.Read. On x86, Volatile.Read is just a standard read anyway (it just prevents compiler reorderings) so there's no reason not to do it. Then the worst that the compiler should be able to do is:

public int AddToTotal(int addend)
{
    int initialValue;
    do
    {
        initialValue = Volatile.Read (ref totalValue);
    } while (initialValue != Interlocked.CompareExchange(
        ref totalValue, initialValue + addend, initialValue));

    return initialValue + addend;
}

Unfortunately, Eric Lippert once claimed volatile read doesn't guarantee protection against introduced reads. I seriously hope he's wrong because that would mean lots of low-lock code is almost impossible to write correctly in C#. He himself did mention somewhere that he doesn't consider himself an expert on low-level synchronization so I just assume his statement was incorrect and hope for the best.

---

Original answer:

Contrary to popular misconception, acquire/release semantics don't ensure a new value gets grabbed from the shared memory, they only affect the order of other memory operations around the one with acquire/release semantics. Every memory access must be at least as recent as the last acquire read and at most as stale as the next release write. (Similar for memory barriers.)

In this code, you only have a single shared variable to worry about: totalValue. The fact that CompareExchange is an atomic RMW operation is enough to ensure that the variable it operates on will get updated. This is because atomic RMW operations must ensure all processors agree on what the most recent value of the variable is.

Regarding the other Total property you mentioned, whether it's correct or not depends on what is required of it. Some points:

• int is guaranteed to be atomic, so you will always get a valid value (in this sense, the code you've shown could be viewed as "correct", if nothing but some valid, possibly stale value is required)
• if reading without acquire semantics (Volatile.Read or a read of volatile int) means that all memory operations written after it may actually happen before (reads operating on older values and writes becoming visible to other processors before they should)
• if not using an atomic RMW operation to read (like Interlocked.CompareExchange(ref x, 0, 0)), a value received may not be what some other processors see as the most recent value
• if both the freshest value and ordering in regards to other memory operations is required, Interlocked.CompareExchange should work (the underlying WinAPI's InterlockedCompareExchange uses a full barrier, not so sure about C# or .Net specifications) but if you wish to be sure, you could add an explicit memory barrier after the read

Answer 2

If we read a stale value, then the CompareExchange won't perform the exchange - we're basically saying, "Only do the operation if the value really is the one we've based our calculation on." So long as at some point we get the right value, it's fine. It would be a problem if we kept reading the same stale value forever, so CompareExchange never passed the check, but I strongly suspect that the CompareExchange memory barriers mean that at least after the time through the loop, we'll read an up-to-date value. The worst that could happen would be cycling forever though - the important point is that we can't possibly update the variable in an incorrect way.

(And yes, I think you're right that the Total property is dodgy.)

EDIT: To put it another way:

CompareExchange(ref totalValue, computedValue, initialValue)

means: "If the current state really was initialValue, then my calculations are valid and you should set it to computedValue."

The current state could be wrong for at least two reasons:

• The initialValue = totalValue; assignment used a stale read with a different old value
• Something changed totalValue after that assignment

We don't need to handle those situations differently at all - so it's fine to do a "cheap" read so long as at some point we'll starting seeing up-to-date values... and I believe the memory barriers involved in CompareExchange will ensure that as we loop round, the stale value we see is only ever as stale as the previous CompareExchange call.

EDIT: To clarify, I think the sample is correct if and only if CompareExchange constitutes a memory barrier with respect to totalValue. If it doesn't - if we can still read arbitrarily-old values of totalValue when we keep going round the loop - then the code is indeed broken, and may never terminate.

Answer 3

The managed Interlocked.CompareExchange maps directly to the InterlockedCompareExchange in the Win32 API (there is also a 64 bit version).

As you can see in the function signatures, the native API requires the destination to be volatile and, even though it is not required by the managed API, using volatile is recommended by Joe Duffy in his excellent book Concurrent Programming on Windows.