title: How do I safely write a test and test-and-set (TATAS) spinlock with C++11 for x86(-64)?
body: <p>I'm currently working on a Spinlock class and trying to make it as reasonable as possible, mostly based on advice here: <a href="https://software.intel.com/en-us/articles/implementing-scalable-atomic-locks-for-multi-core-intel-em64t-and-ia32-architectures" rel="nofollow">https://software.intel.com/en-us/articles/implementing-scalable-atomic-locks-for-multi-core-intel-em64t-and-ia32-architectures</a></p>
  
  <p>The work-in-progress looks like this:</p>
  
  <pre><code>class Spinlock
  {
  public:
      Spinlock() : m_lock(false) {}
  
      void lock()
      {
          // heavy test here for the usual uncontested case
          bool exp = false;
          if (!m_lock.compare_exchange_weak(exp, true, std::memory_order_acquire))
          {
              int failCount = 0;
              for (;;)
              {
                  // processor spin loop hint
                  _mm_pause();
  
                  // spin on mov instead of lock instruction
                  if (!m_lock.load(std::memory_order_relaxed))
                  {
                      // heavy test now that we suspect success
                      exp = false;
                      if (m_lock.compare_exchange_weak(exp, true, std::memory_order_acquire))
                      {
                          return;
                      }
                  }
  
                  // backoff (potentially make exponential later)
                  if (++failCount == SOME_VALUE)
                  {
                      // Yield somehow.
                      failCount = 0;
                  }
              }
          }
      }
  
      void unlock()
      {
          m_lock.store(false, std::memory_order_release);
      }
  
      std::atomic_bool m_lock;
  };
  </code></pre>
  
  <p>However, it seems like having that relaxed read in there can theoretically allow generated code to do unexpected things like create deadlocks: <a href="http://joeduffyblog.com/2009/02/23/the-magical-dueling-deadlocking-spin-locks/" rel="nofollow">http://joeduffyblog.com/2009/02/23/the-magical-dueling-deadlocking-spin-locks/</a></p>
  
  <p>This code shouldn't deadlock in the same way as the linked example because the outer acquire should keep the relaxed load from drifting behind, but I don't really have a handle on all the code transformations that could exist. What memory orders and/or fences do I need to keep this code safe without losing performance? Is it possible for a backoff implementation to occur significantly more or less frequently (> a few loops) than intended because the surrounding memory orders are too relaxed?</p>
  
  <p>On a related note, why are spinlock examples around the web using acquire/release memory order for spinlocks instead of sequentially consistent? I found a comment saying that allowing a spinlock release to cross a later spinlock acquire could lead to problems: <a href="http://preshing.com/20120913/acquire-and-release-semantics/#IDComment721195810" rel="nofollow">http://preshing.com/20120913/acquire-and-release-semantics/#IDComment721195810</a></p>