title: Insertion and deletion in a latch-free linked list
body: <p>I'm working with a shared linked list in a multithreading program. Instead of using latches (mutexes), I'm relying on CAS operation to ensure correctness of insert and delete. All inserts and deletes happen at the head of the linked list (LIFO). The program is not working as expected, it randomly causes a segmentation fault and exits. Any thoughts?
  Here's a simplified version of my program. It breaks with four threads about 1% of the time.</p>
  
  <pre><code>struct Node {
    unsigned long num;
    Node* next;
  };
  
  Node* head = NULL;
  
  #define NUM_THREADS 4L
  #define Rounds 10000L
  #define Iterations 100L
  #define SumPerRound ((Iterations-1)*Iterations/2)
  #define SumPerThread (SumPerRound * Rounds)
  #define ExpectedSum (SumPerThread * NUM_THREADS)
  
  unsigned long totalSum = 0;
  void* Worker(void*) {
    for (unsigned int r = 0; r &lt; Rounds; r++) {
      for (unsigned int i = 0; i &lt; Iterations; i++) {
        Node* n = new Node();
        n-&gt; num = i;
        do {
          n-&gt;next = head;
        } while (!__sync_bool_compare_and_swap(&amp;head, n-&gt;next, n));
      }
  
      for (unsigned int i = 0; i &lt; Iterations; i++) {
        Node* n;
        do {
          n = head;
          assert(n);
        } while (!__sync_bool_compare_and_swap(&amp;head, n, n-&gt;next));
        __sync_fetch_and_add(&amp;totalSum, n-&gt;num);
        delete n;
      }
    }
    return NULL;
  }
  </code></pre>