from Hacker News

A spin lock in C that does not require a machine level exchange instruction

by keithgabryelski on 5/4/14, 11:04 PM with 25 comments

• by colanderman on 5/5/14, 12:16 AM

  (EDITED; misread algorithm earlier.) No, sorry, that doesn't work. Consider the following sequence:

  1. A sets g1 = A

  2. A reads g2 = none

  3. A reads g1 = A

  4. B sets g1 = B

  5. B reads g2 = none

  6. B reads g1 = B

  7. A sets g2 = A (read in #3)

  8. A reads g1 = B

  9. A retries

  10. A reads g2 = A

  11. A succeeds

  12. B sets g2 = B (read in #6)

  13. B reads g1 = B

  14. B reads g2 = B

  15. B succeeds

  You also are missing memory fences, which are needed to ensure proper ordering of memory operations. (Otherwise the processor is free to speculate reads and delay writes between cores.) See https://www.kernel.org/doc/Documentation/memory-barriers.txt for a thorough explanation.

• by jacquesm on 5/5/14, 12:22 AM

  Hello dear Keith,

  I can see a few problems with this code, please consider the following constructive criticism.

    for (;;) {
      if (state->g2 == locker_id) {
        return;
      }
      while (state->g2 != SPIN_LOCK_NO_LOCKER) {
        if (spin_wait_callback != NULL) {
          spin_wait_callback();
        }
  

  You don't need this 'continue', the loop will do that just fine without it.

        continue;
      }
  

  The following four lines are problematic:

      state->g1 = locker_id;
  
      if (state->g2 == SPIN_LOCK_NO_LOCKER) {
  

  Imagine the consequences of a task switch right here.

        state->g2 = state->g1;
  

  This if does nothing.

        if (state->g1 == locker_id) {
  

  And you're going to do the following if without all the extra conditionals above when you do not return from here the next time you iterate through the loop. So all that extra testing of state->g1 above does nothing.

          if (state->g2 == locker_id) {
            return;
          }
        }
      }
    }
  
  

  I think I can see what you're trying to do here but once you fix the basic problems with the code and you test it under very high load locking and unlocking a resource you'll find that fairly soon two threads will be accessing the resource at the same time.

  Try a very tight loop that locks a counter, does a load, increment, store on it and then unlocks the counter again. Keep separate tallies per thread and use a third thread to keep track of the expected sum and the actual sum.

  That should show you reasonably quickly why atomicity in the basic operation of acquiring a lock is a base requirement.

  Locking issues almost never show up when you are running lightly loaded on a single core. But the lack of ensuring all cores see the same information, that race conditions can't occur and that instructions are executed in the right order will show up with a terrible certainty under load on multiple cores.

• by jpollock on 5/5/14, 12:23 AM

  Both the compiler and CPU will reorder operations. Proper locking requires a memory barrier which will prevent both CPU and compiler from doing that. For more information I recommend reading up on double checked locking. DDJ had a good pair of articles the first where they presented the faulty algorithm, the second where they talked about why it was broken.

  C/c++ doesn't have many guarantees about operation ordering. http://www.cs.umd.edu/~pugh/java/memoryModel/DoubleCheckedLo...

• by colin_mccabe on 5/5/14, 12:30 AM

  There seems to be an implicit assumption in this code that writes which one thread makes will be seen by other threads in the same order. This is not the case on modern architectures. You need both compiler and machine-level memory barriers to ensure this. C's "volatile" keyword does not provide either.

  The Linux kernel guys wrote an in-depth explanation of why volatile doesn't work for this use-case here: https://www.kernel.org/doc/Documentation/volatile-considered...

• by comex on 5/5/14, 12:37 AM

  For real solutions to this problem, see:

  http://www.di.ens.fr/~pouzet/cours/systeme/bib/dijkstra.pdf

  http://phoenix.goucher.edu/~kelliher/cs42/sep30.html

• by tsukikage on 5/5/14, 12:21 AM

      if (state->g2 == SPIN_LOCK_NO_LOCKER) {
        state->g2 = state->g1;
        if (state->g1 == locker_id) {
  		if (state->g2 == locker_id) {
  			return;
  		}
        }
      }
  

  You need to insert memory barriers between the writes and the reads. Without, on systems with multiple cores, other cores may not see the state changes in program order, which will make it possible for multiple threads to conclude they won the race.

  http://en.wikipedia.org/wiki/Memory_barrier http://en.wikipedia.org/wiki/Weak_consistency

• by Moral_ on 5/5/14, 12:11 AM

  The example code he provides doesn't even compile:

       real_test.c: In function ‘main’:
       real_test.c:14:10: error: too many arguments to function ‘spin_allocate’
       spin-lock.h:20:32: note: declared here
       real_test.c:16:3: error: too few arguments to function ‘spin_lock’
       spin-lock.h:19:13: note: declared here
  

  Easy to fix, just annoying.

• by asveikau on 5/5/14, 12:41 AM

  It seems like this is just storing a thread id in some shared variables a few times and double checking that your id "made it" and you win the race. My understanding of why this doesn't work is without atomics or memory barriers, what you read might not reflect what another core has in its cache, and when you write, it might not be immediately visible to others. So while in your thread's view of the world you might have successfully written those 2 words and won the race, it might not matter to the other guy. Though this depends on the consistency model of the CPU. The table here comes to mind: http://en.m.wikipedia.org/wiki/Memory_ordering - my memory is that x86 is generous in how much it lets you get away with this, you might have more trouble running on say, power.

• by nkurz on 5/5/14, 12:33 AM

  Here's a copy of the functions in question so that it's easier to see what people are talking about:

    void 
    spin_lock(struct spin_lock_state *state, int locker_id,
              void (*spin_wait_callback)()) {
      for (;;) {
        if (state->g2 == locker_id) {
          return;
        }
        while (state->g2 != SPIN_LOCK_NO_LOCKER) {
          if (spin_wait_callback != NULL) {
            spin_wait_callback();
          }
          continue;
        }
        state->g1 = locker_id;
        if (state->g2 == SPIN_LOCK_NO_LOCKER) {
          state->g2 = state->g1;
          if (state->g1 == locker_id) {
            if (state->g2 == locker_id) {
              return;
            }
          }
        }
      }
    }
  
    void
    spin_unlock(struct spin_lock_state *state, int locker_id)
    {
      state->g2 = SPIN_LOCK_NO_LOCKER;
    }

• by frozenport on 5/5/14, 12:15 AM

  I know how to do a spinlock in pthreads, and have done it using a while loop and what I hope was an atomic instruction.

  What is a `machine level exchange instruction`?

• by michaelmior on 5/5/14, 12:14 AM

  I'm confused why the description refers to it as a "user level" spinlock. Are there some architectures where exchange is a privileged operation?

• by keithgabryelski on 5/4/14, 11:51 PM

  a reasonable primer: http://en.wikipedia.org/wiki/Spinlock