Search code examples
c#multithreadinglock-freeinterlocked

Is the "Interlocked Anything Pattern" from CLR via C# not threadsafe

Reading on the Interlocked Anything Pattern as coined by Jeffrey Richter in CLR via C# 4th Edition he gives the following example demonstrating that we can do more than just Add for Interlocked

Although the Interlocked class doesn’t offer these methods, there is a well-known pattern that allows you to perform any operation on an Int32 in an atomic way by using Interlocked.CompareExchange.

public static Int32 Maximum(ref Int32 target, Int32 value)
{ 
    Int32 currentVal = target, startVal, desiredVal; 
     
    // Don't access target in the loop except in an attempt 
    // to change it because another thread may be touching it 
    do
    { 
        // Record this iteration's starting value 
        startVal = currentVal; 
     
        // Calculate the desired value in terms of startVal and value 
        desiredVal = Math.Max(startVal, value); 
     
        // NOTE: the thread could be preempted here! 
     
        // if (target == startVal) target = desiredVal 
        // Value prior to potential change is returned 
        currentVal = Interlocked.CompareExchange(ref target, desiredVal, startVal); 
     
        // If the starting value changed during this iteration, repeat 
    } while (startVal != currentVal); 
     
    // Return the maximum value when this thread tried to set it 
    return desiredVal; 
}

A very similar version of pattern is to be found for the add and remove methods generated by the C# compiler for events:

[CompilerGenerated]
{
    EventHandler eventHandler = this.MyEvent;
    EventHandler eventHandler2;
    do
    {
        eventHandler2 = eventHandler;
        EventHandler value2 = (EventHandler)Delegate.Combine(eventHandler2, value);
        eventHandler = Interlocked.CompareExchange(ref this.MyEvent, value2, eventHandler2);
    }
    while ((object)eventHandler != eventHandler2);
}

However the one big difference is how we get the "target" value - ref argument vs. field access.

The original example using the ref argument, what is there to prevent the target value from changing before it is assigned to the temp value via:

Int32 currentVal = target, startVal, desiredVal;

For example by another thread changing the value just as we jump to the beginning of the method?

EDIT: Here is an example of what I mean (LINQPad style)

void Main() {
    var current = 33;
    var otherThread = new Thread(() => MutateLocal(ref current));
    otherThread.Start();
    var result = Maximum(ref current, 55); // at this point current is 33

    current.Dump(); // 100
    result.Dump(); // 100 
}

public static void MutateLocal(ref int target) {
    Thread.Sleep(100);
    target = 100; 
}

public static Int32 Maximum(ref Int32 target, Int32 value) {
    Console.WriteLine(target);
    Thread.Sleep(200);
    Console.WriteLine(target);

    Int32 currentVal = target; // this is atomic...
// ... rest of the Maximum method from above

So Max doesn't seem very atomic when the result of Maximum(ref 33, 55) is 100 which is the stated goal of the pattern.

Solution

  • You seem to have a misconception here which you are struggling with.

    We don't care if the value of target changed before or after running the loop. We are completely agnostic to that happening, and we are not trying to do Maximum(35, 55), we are trying to do Maximum(ref target, 55).

    So all we need to do is retrieve the value of that location at some given point in time, then do some arbitrarily complex calculation on it, and ensure that we store the value back before anyone else has changed it. We simply do not care if any changes happened before or after, we only care that our calculation was atomic with respect to its start and end.

    This algorithm guarantees that, as explained in the article:

    • First take the current value of target and store it in currentVal
    • We then loop, attempting to make the modification we want, and we continuously loop until we successfully manage to pre-empt both the read and store to target before anyone else.
      From this point on, all bets are off regarding pre-emption of other threads, so we need to check the value hasn't changed.
    • Store what we think is the current value into startVal.
    • Using the startVal we make some calculation, which we store in desiredVal.
    • We use Interlocked.CompareExchange to atomically check and possibly store the new value. The value is only stored if the current live value in target is the same as what we thought it was in startVal, in other words we have not been pre-empted.
      If we have been pre-empted then the value will be different, so no store happens.
    • CompareExchange returns that latest live value, which we store back into currentVal. We compare that with startVal to check if it's different, which tells us whether to loop again.
      • If they are the same then the store was successful and we can go on with our day.
      • Otherwise we were pre-empted and must loop again.
    • When we loop, we already have the new live value, we don't need to retrieve it again.

    Note that you must use a ref for target, so that we work directly on a memory location. We are passing by reference, so that CompareExchange can directly check the live value of that location.

    Also we don't touch target at all within the loop, except in the CompareExchange statement. This is essential: you must use startVal as your working area.