Lock-free algorithms: Choosing a unique value (solutions)


Last time, I left a warm-up exercise consisting of a code fragment which tries to compute a unique process-wide value. Here it is again:

dwUniqueId = InterlockedCompareExchange(&g_dwUniqueId, 
                                        g_dwUniqueId+1, 
                                        g_dwUniqueId);

It may be easier to enumerate what the function does right rather than what it does wrong.

Um, the words are correctly-spelled.

That's about it.

Damien was the first to note that the author basically reimplemented Interlocked­Increment. Poorly.

As we saw earlier, the algorithm for performing complex calculations with interlocked functions is (capture, compute, compare-exchange, retry). But the above code didn't do any of these things.

By failing to capture the values, the code is vulnerable to another thread modifying the g_dwUniqueId value simultaneously. This means that the computation step can fail, because the inconsistent reads of g_dwUniqueId result in who-knows-what getting passed to the Interlocked­Compare­Exchange function.

Okay, they managed to spell Interlocked­Compare­Exchange correctly.

And then they forgot to retry the operation if the compare-exchange failed, which means that they will just proceed with whatever value the g_dwUniqueId variable held at the time of the Interlocked­Compare­Exchange call. If it just got incremented by another thread, then this thread and the other thread will be using the same "unique" value.

Joshua points out that compiler optimization can prevent the capture from being a true capture. Though I would put the volatile keyword on g_dwUniqueId rather than scv, because the volatile object is the global variable, not the local. Marking the local as volatile forces all accesses to the local to be executed as written, but the compiler can still optimize the access to g_dwUniqueId. (It might, for example, propagate the value in from a previous read earlier in the function.)

And do take into consideration Leo Davidson's warning: This series of articles is a peek behind the scenes series, not a here's how you should do it series. We're taking apart a bunch of toasters to see how they work. When possible, take advantage of code written by people smarter than you.

Comments (7)
  1. Anonymous says:

    Windows should make this easier.

    [InterlockedIncrement isn't easy enough? -Raymond]
  2. Anonymous says:

    @dot

    And really, how can Windows make interlocking and synchronization easier.  The concepts are simple, but the combination of concept and execution timeline is extremely difficult.  Windows can't make that easier.

  3. Anonymous says:

    (It might, for example, propagate the value in from a previous read earlier in the function.)

    I would seriously question the ability of the optimizer to optimize if it made that transform; however even if it did the penalty is one pass through the loop on rare occasions rather than the code not working.

    Instead of:

    @1:  mov  eax, [g_dwUniqueId]

        mov  [scv], eax

        push [scv]

        mov  eax, [scv]

        inc  eax

        push eax

        lea  eax, [g_dwUniqueId]

        push eax

        call InterlockedCompareExchange

        cmp  eax, [scv]

        jne  @1

        mov  eax, [scv]

        mov  [dwUniqueId], eax

    It would have to write:

    @1:  mov  [scv], edx

        push [scv]

        mov  eax, [scv]

        inc  eax

        push eax

        lea  eax, [g_dwUniqueId]

        push eax

        call InterlockedCompareExchange

        cmp  eax, [scv]

        je   @2

        mov  edx, [g_dwUniqueId]

        jmp  @1

    @2:  mov  eax, [scv]

        mov  [dwUniqueId], eax

    All the same Raymond is correct that volatie on g_dwUniqueId allows for better code as follows:

    @1:  mov  esi, [g_dwUniqueId]

        push esi

        mov  eax, esi

        inc  eax

        push eax

        lea  eax, [g_dwUniqueId]

        push eax

        call InterlockedCompareExchange

        cmp  eax, esi

        mov  [dwUniqueId], esi

  4. Joshua Ganes says:

    The last few posts have sufficiently garbled my brain to the point where programming feels like an exercise in magic and wizardry.

    This just goes to show that threaded programming is (almost) always evil.

  5. Anonymous says:

    @dot

    Windows <= 3.x did!

  6. Anonymous says:

    This series has once again made me realize that I am in the wrong field and would better server mankind as either a shepherd or the owner of a tiki bar.

  7. Anonymous says:

    I think maybe what the programmer of that horrible snippet thought was that "Interlocked" in InterlockedCompareExchange implied an invisible mutex around the entire function call expression, including the argument expressions. That would (a) explain how anyone thought this code could possibly be correct, but (b) betray a fundamental misunderstanding of how the C(++) programming language works.

Comments are closed.