SpinWaitLock

[racker]

Hi,

I have implemented a simple spinlock based on the intrinsic InterlockedCompareExchange.
The waiting thread loops for some time. After a while it gives up and waits on a condition variable until the lock becomes free again.

I believe to code is correct, as long as everything is executed in the order defined by the code.
Still it happens that a thread is sleeping forever, while the lock is free and sleeping is 1.

It appears that sleeping is incremented _after_ the waiting thread sleeps. I just don't get it.
Any hints are appreciated.

Thanks,
Ralph

[cpp]static volatile unsigned long spinlock;
static volatile unsigned long sleeping;

lock()
{  while(_InterlockedCompareExchange(&spinlock, 1, 0))
   {  nloops++;
   
      if(nloops > threshold)
      {  pthread_mutex_lock(&mutex);
         sleeping++;
         while(_InterlockedCompareExchange(&spinlock, 1, 0))
            pthread_cond_wait(&cond, &mutex);
         sleeping--;
         pthread_mutex_unlock(&mutex);
         break;
      }
   }
}

unlock()
{  spinlock=0;
   if(sleeping)
   {  pthread_mutex_lock(&mutex);
      pthread_cond_signal(&cond);
      pthread_mutex_unlock(&mutex);
   }
}[/cpp]

[Dmitry_Vyukov · Accepted solution]

You need #StoreLoad style memory fence in critical store-load sequence. You have basically an instance of Dekker/Peterson algorithm in your slow-path:
http://en.wikipedia.org/wiki/Peterson%27s_algorithm
It won't work without StoreLoad memory fence.

In order to fix you need to insert:
lock()
...
sleeping++;
_mm_mfence();
while(_InterlockedCompareExchange(&spinlock, 1, 0))

unlock()
...
spinlock=0;
_mm_mfence();
if(sleeping)