The if statement within the lock block misses an else clause which gets a new incrementedCurrentLow. The if statement detects if another thread has gotten a new high, but you use the already invalidated incrementedCurrentLow to calculate the ID. Which results in the same ID being generated more than once.

When 2 threads are waiting at lock (generatorLock) the second thread will have the same Id as the first thread.

// Ryan

There's no synchronization on currentHi or capacity.

The result is calculated from these outside of the lock, and hence may not be thread safe.

If the bug is not in the HiLo algorithm and has to do with the language itself I would change the code to use Monitor.Enter's overload that takes a boolean parameter indicating if the lock was actually taken in case of an exception. For volatile fields I would use the Interlocked constructs to ensure that increment/decrement will be done in atomic fashion.

Boolean lockTaken = false;

            Monitor.Enter(generatorLock, ref lockTaken);

            try

            {

                if (Interlocked.Read(ref currentLo) > capacity)

                {

                    currentHi = GetNextHi();

                    currentLo = 1;

                    incrementedCurrentLow = 1;

                }

            }

            finally

            {

                if (lockTaken) { Monitor.Exit(generatorLock); }

            }

long incrementedCurrentLow = Interlocked.Increment(ref currentLo);

        if (incrementedCurrentLow > capacity)

        {

            lock (generatorLock)

            {..}}

It's useless to use interlocked.

Actually, you enter lock twice in case of couinter adjustments, and you enter lock anyway.

I'm really not shure Interlocked.Increment lock is faster then Monitor.Enter();

If two threads increments together while you are around capacity, they both do GetNextHi().

oops. I was wrong about two GetNextHi().

Someone will get overflowed incrementedCurrentLow and two threads will get same Id.

If currentLo is a long, then currentLo = 1 is not atomic on a 32-bit machine; this does not play well with the atomic increment outside the lock.

If currentLo == capacity, and two threads enter NextId() simultaniously, the first one to do the Interlocked.Increment will have incrementedCurrentLow == capacity, while it could have the same currentHi as the second thread.

If a thread context switch is made for the first thread between the increment and the return, the second thread has the opportunity to do a GetNextHi() in between.

Assuming currentHi is a volatile field, the return for the first thread will get the currentHi as the second thread set it. If it's not a volatile field, well then all bets are off for what the value of currentHi is.

@Andrew Borodin

Interlocked.Increment is a lot faster than using a Monitor. When two threads attempt to increment simultaneously, the Monitor will cause a context switch for the unlucky thread, which you don't want. And all that just because you were a few processor cycles to soon or late compared to the other thread.

If you want to make multithreaded code faster, use volatile and interlocked instead of Monitor. Be prepared to deal with the added complexity (and therefor development time) that such lock free code brings with it.

And as Oren showed with his example, it's sometimes very hard, if not impossible, to get (partially) lock free correct.

Oren,

You don't have to do a Thread.VolatileRead inside a lock. Monitor.Enter already generates a MemoryBarrier, which will guarantee you get the latest value of currentLo.

I see two ways of making NextId() correct and lock free.

1. instead of calculating the id from currentLo and Hi, calculate the currentLo and Hi from the id, and increment only that in NextId().

so the method NextId() would become "return Interlocked.Increment(ref currentId);"

the property CurrentLo would become "get { return CurrentId) % capacity; }"

and the property CurrentHi would become "get { return CurrentId / capacity + 1; }"

I will leave the lock free set { } implementations for CurrentLo, CurrentHi and Capacity as an exercise for the reader. ;-)

1. create an immutable class CurrentId with the members Lo and Hi. Every update that involves the current id, lo and hi will then need to be performed with a loop and Interlocked.CompareExchange. Be aware however that this can create a livelock-like situation when you have a lot of concurrent threads trying to modify it.

Of course there's always the option of using a big honking lock that wraps the entire NextId() method. :-)

I dug up my LockFreeUpdate() wich you could use for solution 2:
  
  
		/// 
<summary  
		/// Updates the specified 
<paramref with the result of the specified
  
		/// 
<paramref. The specified 
<paramref may be invoked
  
		/// multiple times if the value of 
<paramref was changed during the
  
		/// execution of 
<paramref.
  
		/// 
>  
		/// 
<returnsThe new value of 
<paramref.
>  
		/// 
<exceptionIf 
<paramref is null.
>  
		public static T LockFreeUpdate
<t(ref T location, Func
<t,>
 change)
  
			where T : class
  
		{
  
			if (change == null)
  
				throw new ArgumentNullException("change");
  
  
			T oldValue;
  
			T newValue;
  
  
			Thread.MemoryBarrier(); // CompareReplace will cause MemoryBarrier at end of loop
  
			do
  
			{
  
				oldValue = location;
  
				newValue = change(oldValue);
  
			} while (Interlocked.CompareExchange(ref location, newValue, oldValue) != oldValue);
  
  
			return newValue;
  
		}
  
  
Anyone may use it as they wish, as long as no one blames me when there is a problem. :)
>

whoops, it seems I lost all the < and > in the above code.

Take a look at the html source if you want to know the secret ingredients of LockFreeUpdate(). I don't feel like making it readable myself. :-P

Problem sits with the "if (Thread.VolatileRead(ref currentLo) > capacity)" line.

What happens if it is no longer > capacity when, as stated earlier, 2 threads make the call to Interlocked.Increment when it is equal to capacity and both enter the lock .

To follow on from my above comment, if "(Thread.VolatileRead(ref currentLo) > capacity)" is no longer true when the second thread enter then it will simply use the value it has in incrementedCurrentLow, which is the wrong value as it was meant to be reset

That just doesn't seem to read right. You're incrementing the currentLo in an atomic operation so it cannot be interrupted by a thread swap. That makes sense, but then afterwards you are performing a lock and inspecting the incremented value to see it it's rolled over the capacity.

This looks to me that a race could result in-between the increment and the generator lock.

My guess would be that this would do the job:

long result;

lock (generatorLock)

{

Interlocked.Increment(ref currentLo);

if (Thread.VolatileRead(ref currentLo) > capacity)

{

    currentHi = GetNextHi();

    currentLo = 1;

}

result = (currentHi - 1)*capacity + (currentLow);

}

return result;

The bug may be that while you are guarding the increment as an atomic unit, the operation to calculate the result isn't guarded.

@Steve Py,

But in your implementation it will lock every time you generate a new ID. Ayende's implementation will only lock when generating a new high value. The real issue (I think) is what @Frank said. If the current thread is the second one to hit the lock, it will not end up executing the code in the if (incrementedCurrentLow > capacity) block so it will use the stale value of incrementedCurrentLow with the newly updated value of CurrentHi. Later on, another thread will eventually request the same ID.

@Patrick Huizinga:

Compare and swap implemetation of Interlocked.Increment() could be slower. It can be easyly googled.

Many concurrent CAS operations on different CPUs will never agree. It would be better someone give up his CPU in spinlock.

Of course, it's arguable, it's just not the case we deal with. Anyway, aggregate sum of CPU time this code works is a lot smaller then we are talking about. Monitor.Eneter() here will never be performance bottleneck.

@Andrew Borodin

I know the CAS is slower than a simple increment. I didn't mean to replace just the 'increment Lo' with the CAS, but the entire NextId method, including checking capacity and generating a new Hi.

I didn't knew concurrent CAS operations could result in a livelock. I always assumed the cpu would guarantee at least one win.

And as far as I know the SpinLock was introduced in .Net 4.0.