Lockless using InterlockedCompareExchange

Question

I am trying to make following snip of code lockless using interlocked operations, Any idea how to translate this?

if (m_Ref == 0xFFFF)
    m_Ref = 1;
else
{
    if (++m_Ref == 1)
        CallSomething(); //

}

I was thinking something like

if (InterlockedCompareExchange(&m_Ref, 1, 0xFFFF) != 0xFFFF))
{
    if (InterlockedIncrement(&m_Ref) == 1)
         CallSomething();
}

Is there any issues/race in this?

Moncrief

Answer 1

This looks correct at a superficial glance, but every time you use two interlocked operations in a row you are exposing yourself to the ABA problem. In this case one thread fail to change it from 0xFFFF to 1 (the ICX returns !=0xFFFF) so it goes ahead and takes the if branch and increments it. Before it runs the InterlockedIncrement another threads changes the m_ref back to 0xFFFF and the original thread increments 0xFFFF. Depending on the type/semantics of m_ref the effect will wary, but will surely be bad.

You should do one single ICX operation, for both the 0xFFF to 1 and X to X+1, and always retry if you lost the ICX:

volatile <type> m_ref;

<type> ref, newRef, icxref;
do
{
   ref = m_ref;
   newRef = (0xFFFF == ref) ? 1 : ++ref;
   icxref = InterlockedCompareExchange (&m_ref, newRef, ref);
} while (icxref != ref);
if (newRef == 1 && ref != 0xFFFF)
{
   DoSomething ();
}

Deflagrate

@Remus Rusanu - Thanks this makes perfect sense – Moncrief

@GMan: what would memory mapping have to do with volatile? – Deflagrate

@Remus: That's the only use for volatile, it makes reads and writes to it observable behavior, it has nothing to do with multi-threading. Your use of it as an argument to InterlockedCompareExchange provides observable behavior already. – Este

@Gman: how about the ref = m_ref;? W/o volatile decorator, it has no Acquire semantics. – Deflagrate

@Remus: It doesn't have it with volatile... Anyway, the compiler cannot elide that assignment, because it's used in the library call later. (i.e., it has observable behavior.) – Este

@GMan: actually it does have Acquire semantics with volatile: A read of a volatile object (volatile read) has Acquire semantics msdn.microsoft.com/en-us/library/12a04hfd%28v=VS.100%29.aspx. – Deflagrate

@Remus: That's a Visual Studio implementation-specific extension. Please find the equivalent quote in the C++ standard. – Este

@GMan: ICX is a Windows library function, one is to expect VC to be used in the OP. – Deflagrate

@Remus: You're missing the point. You still don't need volatile here, whether or not you get extra semantics, for the reasons I've already said. – Este

@Remus, @Gman: There is no need for load-with-acquire in ref = mref;. Acquire barrier would prevent hoisting of subsequent memory operations above the load, but the very next memory operation is ICX, which has a full barrier anyway. – Stepmother

Answer 2

Yes there's a race. Another context could do a lot in between InterlockedCompareExchange and InterlockedIncrement

Reta

Thanks, I was thinking the same, do you have any idea how to fix this? – Moncrief

@Suresh: Not really, not if you want it lockless. If you can change to allow 0 then use % on the return value from InterlockedIncrement – Reta

@Moncrief You can use InterlockedCompareExchange as an optimistic locking mechanism if you don't expect races to pop up too much in actual running code. – Vinnie