title: Lockless queue implementation ends up having a loop under stress
body: <p>I have lockless queues written in C in form of a linked list that contains requests from several threads posted to and handled in a single thread. After a few hours of stress I end up having the last request's next pointer pointing to itself, which creates an endless loop and locks up the handling thread.</p>
  
  <p>The application runs (and fails) on both Linux and Windows. I'm debugging on Windows, where my <code>COMPARE_EXCHANGE_PTR</code> maps to <a href="http://msdn.microsoft.com/en-us/library/ms683568(VS.85).aspx" rel="nofollow noreferrer">InterlockedCompareExchangePointer</a>. </p>
  
  <p>This is the code that pushes a request to the head of the list, and is called from several threads:</p>
  
  <pre><code>void push_request(struct request * volatile * root, struct request * request)
  {
      assert(request);
  
      do {
          request-&gt;next = *root;
      } while(COMPARE_EXCHANGE_PTR(root, request, request-&gt;next) != request-&gt;next);
  }
  </code></pre>
  
  <p>This is the code that gets a request from the end of the list, and is only called by a single thread that is handling them:</p>
  
  <pre><code>struct request * pop_request(struct request * volatile * root)
  {
      struct request * volatile * p;
      struct request * request;
  
      do {
          p = root;
          while(*p &amp;&amp; (*p)-&gt;next) p = &amp;(*p)-&gt;next; // &lt;- loops here
          request = *p;
      } while(COMPARE_EXCHANGE_PTR(p, NULL, request) != request);
  
       assert(request-&gt;next == NULL);
  
       return request;
  }
  </code></pre>
  
  <p>Note that I'm not using a tail pointer because I wanted to avoid the complication of having to deal with the tail pointer in <code>push_request</code>. However I suspect that the problem might be in the way I find the end of the list.</p>
  
  <p>There are several places that push a request into the queue, but they all look generaly like this:</p>
  
  <pre><code>// device-&gt;requests is defined as struct request * volatile requests;
  struct request * request = malloc(sizeof(struct request));
  if(request) {
      // fill out request fields
      push_request(&amp;device-&gt;requests, request);
      sem_post(device-&gt;request_sem);
  }
  </code></pre>
  
  <p>The code that handles the request is doing more than that, but in essence does this in a loop:</p>
  
  <pre><code>if(sem_wait_timeout(device-&gt;request_sem, timeout) == sem_success) {
      struct request * request = pop_request(&amp;device-&gt;requests);
      // handle request
      free(request);
  }
  </code></pre>
  
  <p>I also just added a function that is checking the list for duplicates before and after each operation, but I'm afraid that this check will change the timing so that I will never encounter the point where it fails. (I'm waiting for it to break as I'm writing this.)</p>
  
  <p>When I break the hanging program the handler thread loops in <code>pop_request</code> at the marked position. I have a valid list of one or more requests and the last one's next pointer points to itself. The request queues are usually short, I've never seen more then 10, and only 1 and 3 the two times I could take a look at this failure in the debugger.</p>
  
  <p>I thought this through as much as I could and I came to the conclusion that I should never be able to end up with a loop in my list unless I push the same request twice. I'm quite sure that this never happens. I'm also fairly sure (although not completely) that it's not the <a href="http://en.wikipedia.org/wiki/ABA_problem" rel="nofollow noreferrer">ABA problem</a>.</p>
  
  <p>I know that I might pop more than one request at the same time, but I believe this is irrelevant here, and I've never seen it happening. (I'll fix this as well)</p>
  
  <p>I thought long and hard about how I can break my function, but I don't see a way to end up with a loop.</p>
  
  <p><strong>So the question is:</strong> Can someone see a way how this can break? Can someone prove that this can not?</p>
  
  <p>Eventually I will solve this (maybe by using a tail pointer or some other solution - locking would be a problem because the threads that post should not be locked, I do have a RW lock at hand though) but I would like to make sure that changing the list actually solves my problem (as opposed to makes it just less likely because of different timing).</p>