title: SEGFAULT when using shared_ptr
body: <p>I'm trying to implement the <strong>Lazy Concurrent List-based Set</strong> in C++ by using <code>shared_ptr</code>. My reasoning is that <code>unreachable nodes</code> will be automatically freed by the last <code>shared_ptr</code>. As per my understanding, increment and decrement operation on a <code>shared_ptr's reference count</code> is atomic. Which means only the <strong>last shared_ptr</strong> with reference to the node should call <strong>delete/free</strong> for that node. I ran the program for <strong>multiple threads</strong>, but my program is crashing with the error <code>double free called</code> or just <strong>Segmentation Fault(SIGSEGV)</strong>. I don't understand how this is possible. Given below is my code for the implementation, with the method names signifying their intended operation.<br/> </p>
  
  <pre><code>#include&lt;thread&gt;
  #include&lt;iostream&gt;
  #include&lt;mutex&gt;
  #include&lt;climits&gt;
  
  using namespace std;
  
  class Thread
  {
     public:
        std::thread t;  
  };
  int n=50,ki=100,kd=100,kc=100;`/*no of threads, no of inserts,deletes &amp; searches*/`
  
  
  class Node
  {
  public:
        int key;
        shared_ptr&lt;Node&gt; next;
        bool marked;
        std::mutex nodeLock;
  
        Node() {
           key=0;
           next = nullptr;
           marked = false;
        }
  
        Node(int k) {
           key = k;
           next = nullptr;
           marked = false;
        }
  
        void lock() {
           nodeLock.lock();
        }
  
        void unlock() {
           nodeLock.unlock();
        }
  
        ~Node()
        {
        }
  };
  
  class List {
     shared_ptr&lt;Node&gt; head;
     shared_ptr&lt;Node&gt; tail;
  
  public:
  
     bool validate(shared_ptr&lt;Node&gt; pred, shared_ptr&lt;Node&gt; curr) {
        return !(pred-&gt;marked) &amp;&amp; !(curr-&gt;marked) &amp;&amp; ((pred-&gt;next) == curr);
     }
  
     List() {
        head=make_shared&lt;Node&gt;(INT_MIN);
        tail=make_shared&lt;Node&gt;(INT_MAX);
        head-&gt;next=tail;
     }
  
     bool add(int key)
     {
        while(true)
        {
           /*shared_ptr&lt;Node&gt; pred = head;
           shared_ptr&lt;Node&gt; curr = pred-&gt;next;*/
          auto pred = head;
          auto curr = pred-&gt;next;
  
           while (key&gt;(curr-&gt;key))
           {
              pred = curr;
              curr = curr-&gt;next;
           }
  
           pred-&gt;lock();
           curr-&gt;lock();
  
           if (validate(pred,curr))
           {
              if (curr-&gt;key == key)
              {
                 curr-&gt;unlock();
                 pred-&gt;unlock();
                 return false;
              }
              else
              {
                  shared_ptr&lt;Node&gt; newNode(new Node(key));
                 //auto newNode = make_shared&lt;Node&gt;(key);
                  //shared_ptr&lt;Node&gt; newNode = make_shared&lt;Node&gt;(key);
                  newNode-&gt;next = curr;
                  pred-&gt;next = newNode;
                  curr-&gt;unlock();
                  pred-&gt;unlock();
                  return true;
              }
           }
           curr-&gt;unlock();
           pred-&gt;unlock();
        }
     }
  
     bool remove(int key)
     {
        while(true)
        {
           /*shared_ptr&lt;Node&gt; pred = head;
           shared_ptr&lt;Node&gt; curr = pred-&gt;next;*/
  
          auto pred = head;
          auto curr = pred-&gt;next;
  
           while (key&gt;(curr-&gt;key))
           {
              pred = curr;
              curr = curr-&gt;next;
           }
  
           pred-&gt;lock();
           curr-&gt;lock();
  
           if (validate(pred,curr))
           {
              if (curr-&gt;key != key)
              {
                 curr-&gt;unlock();
                 pred-&gt;unlock();
                 return false;
              }
              else
              {
                 curr-&gt;marked = true;
                 pred-&gt;next = curr-&gt;next;
                 curr-&gt;unlock();
                 pred-&gt;unlock();
                 return true;
              }
           }
           curr-&gt;unlock();
           pred-&gt;unlock();
        }
     }
  
     bool contains(int key) {
        //shared_ptr&lt;Node&gt; curr = head-&gt;next;
      auto curr = head-&gt;next;
  
        while (key&gt;(curr-&gt;key)) {
           curr = curr-&gt;next;
        }
        return curr-&gt;key == key &amp;&amp; !curr-&gt;marked;
     }
  }list;
  
  void test(int curr)
  {
     bool test;
      int time;
  
      int val, choice;
      int total,k=0;
      total=ki+kd+kc;
  
      int i=0,d=0,c=0;
  
      while(k&lt;total)
      {
          choice = (rand()%3)+1;
  
          if(choice==1)
          {
              if(i&lt;ki)
              {
                  val = (rand()%99)+1;
                  test = list.add(val);
                  i++;
                  k++;
              }
          }
          else if(choice==2)
          {
              if(d&lt;kd)
              {
                  val = (rand()%99)+1;
                  test = list.remove(val);
                  d++;
                  k++;
              }
          }
          else if(choice==3)
          {
              if(c&lt;kc)
              {
                  val = (rand()%99)+1;
                  test = list.contains(val);
                  c++;
                  k++;
              }
          }
      }
  }
  
  int main()
  {
     int i;
  
     vector&lt;Thread&gt;thr(n);
  
     for(i=0;i&lt;n;i++)
     {
        thr[i].t = thread(test,i+1);
     }
     for(i=0;i&lt;n;i++)
     {
        thr[i].t.join();
     }
     return 0;
  }
  </code></pre>
  
  <p>I'm not able to figure out what's wrong with the above code. The errors differ every time, some of which are just <code>SEGFAULTS</code> or</p>
  
  <pre><code>pure virtual method called
  terminate called without an active exception
  Aborted (core dumped)
  </code></pre>
  
  <p>Could you please point out what I'm doing wrong in the above code? And how to fix that error?<br/>
  <strong>EDIT:</strong> Added a very crude <code>test function</code> which randomly calls the three <code>list methods</code>. Also, number of threads and number of each operations are declared globally. Crude programming, but it recreates the <strong>SEGFAULT</strong>.</p>