Possibly incorrect implementation of double double-lock checking

  • A+
Category:Languages

I've found in our project's code the following implementation of double-lock checking:

  public class SomeComponent   {     private readonly object mutex = new object();      public SomeComponent()     {     }      public bool IsInitialized { get; private set; }      public void Initialize()     {         this.InitializeIfRequired();     }      protected virtual void InitializeIfRequired()     {         if (!this.OnRequiresInitialization())         {             return;         }          lock (this.mutex)         {             if (!this.OnRequiresInitialization())             {                 return;             }              try             {                 this.OnInitialize();             }             catch (Exception)             {                 throw;             }              this.IsInitialized = true;         }     }      protected virtual void OnInitialize()     {         //some code here     }      protected virtual bool OnRequiresInitialization()     {         return !this.IsInitialized;     } } 

From my point of view, this is the wrong implementation due to the absence of guarantees that different threads will see the freshest value of the IsInitialized property.

And the question is "Am I right?".

Update: The scenario that I'm afraid to happen, is the following:

Step 1. Thread1 is executed on Processor1 and writes true into IsInitialized inside the lock section. This time old value of IsInitialized ( it's false) is in the cache of Processor1 As we know, processors have store buffers, so Processor1 can put new value (true) into its store buffer, not into its cache.

Step 2. Thread2 is inside InitializeIfRequired, executed on Processor2 and reads IsInitialized. There is no value of IsInitialized inside the cache of Processor2, so Processor2 ask the value of IsInitialized from other processors' caches or from memory. Processor1 has the value of IsInitialized inside its cache ( but remember it's old value, the updated value is still in the store buffer of Processor1 ), so it sends the old value to Processor2. As a result, Thread2 can read false instead of true.

Update 2:
If the lock (this.mutex) flushes processors' store buffers, then everything is ok, but is that guaranteed?

 


this is the wrong implementation due to the absence of guarantees that different threads will see the freshest value of the IsInitialized property. The question is "Am I right?".

You are correct that this is a broken implementation of double-checked locking. You are wrong in multiple subtle ways about why it is wrong.

First, let's disabuse you of your wrongness.

The belief that there is a "freshest" value of any variable in a multithreaded program is a bad belief, for two reasons. The first reason is that yes, C# makes guarantees about certain constraints on how reads and writes may be re-ordered. However, those guarantees do not include any promise that a globally consistent ordering exists and can be deduced by all threads. It is legal in the C# memory model for there to be reads and writes on variables, and for there to be ordering constraints on those reads and writes. But in cases where those constraints are not strong enough to enforce exactly one ordering of reads and writes, it is permissible for there to be no "canonical" order observed by all threads. It is permitted for two threads to agree that the constraints were all met, but still disagree upon what order was chosen. This logically implies that the notion that there is a single, canonical "freshest" value for each variable is simply wrong. Different threads can disagree as to which writes are "fresher" than others.

The second reason is that even without this weird property that the model admits two threads to disagree on the sequence of reads and writes, it would still be wrong to say that in any low-lock program you have a way to read the "freshest" value. All the primitive operations you have guarantee you is that certain writes and reads will not be moved forwards or backwards in time past certain points in the code. Nothing in there says anything whatsoever about "freshest", whatever that means. The best you can say is that some reads will read a fresher value. The notion of "freshest" is not defined by the memory model.

Another way you are wrong is very subtle indeed. You are doing a great job of reasoning about what might happen based on processors flushing caches. But nowhere in the C# documentation does it say one word about processors flushing caches! That's a chip implementation detail that is subject to change any time your C# program runs on a different architecture. Do not reason about processors flushing caches unless you know your program will run on exactly one architecture, and that you thoroughly understand that architecture. Rather, reason about the constraints imposed by the memory model. I am aware that the documentation on the model is sorely lacking, but that's the thing you should be reasoning about, because that's what you can actually depend on.

The other way that you are wrong is that though yes, the implementation is broken, it is not broken because you are not reading an up-to-date value of the initialized flag. The problem is that the initialized state that is controlled by the flag is not subject to restrictions on being moved around in time!

Let's make your example a bit more concrete:

private C c = null; protected virtual void OnInitialize() {      c = new C(); } 

And a usage site:

this.InitializeIfRequired(); this.c.Frob(); 

Now we come to the real problem. Nothing is stopping the reads of IsInitialized and c from being moved around in time.

Suppose threads Alpha and Bravo are both running this code. Thread Bravo wins the race and the first thing it does is reads c as null. Remember, it is allowed to do so because there is no ordering constraint on the reads and writes because Bravo is never going to enter the lock.

Realistically, how might this happen? The C# compiler or the jitter are permitted to move the read instruction earlier, but they don't. Briefly returning to the real world of cached architectures, the read of c might be logically moved up in front of the read of the flag because c is already in the cache. Maybe it was close to a different variable that was read recently. Or maybe branch prediction is predicting that the flag is going to cause you to skip the lock, and the processor pre-fetches the value. But again, it doesn't matter what the real-world scenario is; that's all chip implementation details. The C# spec permits this read to be done early, so assume that at some point it will be done early!

Back to our scenario. We immediately switch to thread Alpha.

Thread Alpha runs as you expect it to. It sees that the flag says that initialization is required, takes the lock, initializes c, sets the flag, and leaves.

Now thread Bravo runs again, the flag now says that initialization is not required, and so we use the version of c that we read earlier, and dereference null.

Double-checked locking is correct in C# as long as you strictly follow the exact double-checked locking pattern. The moment you diverge from it even slightly you are off in the weeds of horrible, unreproducible, race condition bugs like the one I just described. Just don't go there:

  • Don't share memory across threads. The takeaway that I take from knowing everything I just told you is I am not smart enough to write multithreaded code that shares memory and works by design. I am only smart enough to write multithreaded code that works by accident, and that's not acceptable to me.
  • If you must share memory across threads, lock every access, without exception. It's not that expensive! And you know what is more expensive? Dealing with a series of unreproducible fatal crashes that all lose user data.
  • If you must share memory across threads and you must have low lock lazy initialization good heavens do not write it yourself. Use Lazy<T>; it contains a correct implementation of low-locked lazy initialization that you can rely on being correct on all processor architectures.

Follow-up question:

If the lock (this.mutex) flushes processors' store buffers, then everything is ok, but is that guaranteed?

To clarify, this question is about whether the initialized flag is read correctly in the double-checked locking scenario. Let's again address your misconceptions here.

The initialized flag is guaranteed to be read correctly inside the lock because it is written inside the lock.

However, the correct way to think about this, as I mentioned before, is not to reason anything about flushing caches. The correct way to reason about this is that the C# specification puts restrictions on how reads and writes can be moved around in time with respect to locks.

In particular, a read inside a lock may not be moved to before the lock, and a write inside a lock may not be moved to after the lock. Those facts, combined with the fact that locks provide mutual exclusion, is sufficient to conclude that the read of the initialized flag is correct inside the lock.

Again, if you are not comfortable making these kinds of deductions -- and I am not! -- then do not write low-lock code.

Comment

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: