title: c++ how to make lock free stack push atomic
body: <p>I need to write a <code>void push(const T&amp; val)</code> implementation for lock free stack.
  The problem is that compare_exchange_weak expects non atomic <code>node*</code> but I must use <code>std::atomic&lt;node*&gt; next</code> field instead of regular <code>node* next</code>.
  I tried to solve this problem by doing this</p>
  
  <pre><code>void push(const T&amp; val) {
      node* new_node = new node(val);
      node* local_next = new_node-&gt;next.load();
      while (!head.compare_exchange_weak(local_next, new_node));
  }
  </code></pre>
  
  <p>But creating if <code>local_next</code> makes things even worse. I tested 2 variants of code. The first one has non-atomic field <code>node* next</code> and I lost about 20-30 elements in the test code below. And using the second variant I got a deadlock.</p>
  
  <p>Test code:</p>
  
  <pre><code>#include &lt;iostream&gt;
  #include &lt;thread&gt;
  #include &lt;atomic&gt;
  #include "lock_free_stack.h"
  
  using namespace std;
  
  void test(lock_free_stack&lt;int&gt;&amp; st, atomic&lt;int&gt;&amp; sum) {
      st.push(1);
      shared_ptr&lt;int&gt; val(st.pop());
      while (val == nullptr) { }
      sum.store(sum.load() + *val);
  }
  
  int main(int argc, const char * argv[]) {
      atomic&lt;int&gt; sum;
      sum.store(0);
      for (int i = 0; i &lt; 100; ++i) {
          lock_free_stack&lt;int&gt; st;
          thread t1(test, ref(st), ref(sum));
          thread t2(test, ref(st), ref(sum));
          thread t3(test, ref(st), ref(sum));
          thread t4(test, ref(st), ref(sum));
          thread t5(test, ref(st), ref(sum));
          thread t6(test, ref(st), ref(sum));
          thread t7(test, ref(st), ref(sum));
          thread t8(test, ref(st), ref(sum));
          t1.join();
          t2.join();
          t3.join();
          t4.join();
          t5.join();
          t6.join();
          t7.join();
          t8.join();
      }
      if (sum.load() == 800) {
          cout &lt;&lt; "CORRECT" &lt;&lt; endl;
      } else {
          cout &lt;&lt; "TIME TO REWRITE STACK " &lt;&lt; sum &lt;&lt; endl;
      }
      return 0;
  }
  </code></pre>
  
  <p>And the code of my lock free stack (first variant):</p>
  
  <pre><code>#ifndef lock_free_stack_hard_lock_free_stack_h
  #define lock_free_stack_hard_lock_free_stack_h
  
  template &lt;typename T&gt;
  class lock_free_stack {
  private:
      struct node {
          node* next;
          std::shared_ptr&lt;T&gt; value;
          node (const T&amp; val) : value(std::make_shared&lt;T&gt;(val)) { }
      };
      std::atomic&lt;node*&gt; head;
      std::shared_ptr&lt;T&gt; default_value;
  
  public:
      lock_free_stack() : head(nullptr), default_value(std::make_shared&lt;T&gt;()) { }
  
      void push(const T&amp; val) {
          node* new_node = new node(val);
          new_node-&gt;next = head.load();
          while (!head.compare_exchange_weak(new_node-&gt;next, new_node));
      }
  
      std::shared_ptr&lt;T&gt; pop() {
          node* old_head = head.load();
          while (old_head &amp;&amp; !head.compare_exchange_weak(old_head, old_head-&gt;next));
          if (old_head) {
              return old_head-&gt;value;
          } else {
              return std::shared_ptr&lt;T&gt;();
          }
      }
  };
  
  #endif
  </code></pre>
  
  <p>And the second variant: </p>
  
  <pre><code>#ifndef lock_free_stack_hard_lock_free_stack_h
      #define lock_free_stack_hard_lock_free_stack_h
  
      template &lt;typename T&gt;
      class lock_free_stack {
      private:
          struct node {
              std::atomic&lt;node*&gt; next;
              std::shared_ptr&lt;T&gt; value;
              node (const T&amp; val) : value(std::make_shared&lt;T&gt;(val)) { }
          };
          std::atomic&lt;node*&gt; head;
          std::shared_ptr&lt;T&gt; default_value;
  
      public:
          lock_free_stack() : head(nullptr), default_value(std::make_shared&lt;T&gt;()) { }
  
          void push(const T&amp; val) {
              node* new_node = new node(val);
              new_node-&gt;next = head.load();
              node* local_next = new_node-&gt;next.load();
              while (!head.compare_exchange_weak(local_next, new_node)); 
          }
  
          std::shared_ptr&lt;T&gt; pop() {
              node* old_head = head.load();
              while (old_head &amp;&amp; !head.compare_exchange_weak(old_head, old_head-&gt;next));
              if (old_head) {
                  return old_head-&gt;value;
              } else {
                  return std::shared_ptr&lt;T&gt;();
              }
          }
      };
  
      #endif
  </code></pre>
  
  <p>So the final question is how to create that <code>local_next</code> correctly?</p>
  
  <p>Thank you.</p>