Lock-free data structures: redux

published: Wed, 12-Jul-2006   |   updated: Thu, 13-Jul-2006

Back in November 2005, I wrote a series of articles on writing lock-free data structures in C# and illustrated the concepts with a lock-free stack, queue, limited-priority queue, and a free list. All seemed well, except several people have commented that I never uploaded the source code and please could they have it? Why didn't I acquiesce?

Well, ladies and gentlemen, there was a bug in the code. A really horrible bug. Awful: if you used the free list, the queue would blow up, rather nastily. If you didn't use the free list, everything was fine. Having talked about the free list in a complete article and explained why it was a Good Thing, I could hardly upload the source without it being present.

So I spent some time at the end of last year trying to work out what was up. I tried this, that, and the other and completely failed to work out the issue. The problem was as if I could dequeue an item several times in a row, which was idiotic. Also I was seeing the tail field being more than one node away from the actual end of the linked list, which I'd pointed out couldn't happen. I was beginning to doubt my own logical reasoning. I threw in volatile everywhere thinking that that was it. To no avail. I'd look at the IL hoping for inspiration, or a clue that some field wouldn't be updated the way I thought.

It was, gentle readers, to put it mildly, ugly.

Eventually I just put it all away and hoped no one was reading the articles. No such luck. I got requests for the code. I'd reply there was a difficult bug that I hadn't found yet. And so on.

Until today. Someone in Argentina sent me an email, actually two, asking questions about the implementation. I decided enough time had passed by that I could look at the code again and try and work out the bug. Well, I found it after about half-an-hour and, boy, did I slap myself. Hard.

Essentially, I'd forgotten to null out the Next field in FreeList.GetNode(). So when Queue.Enqueue() would add the node to the end of the linked list, the linked list would be extended with all the nodes in the free list. Ouch. No wonder I was getting duplicate items in the queue, no wonder the tail reference was more than one node away from the end of the list.

Anyway, without further ado, here's a bunch of links for you to tie all this up.

The code includes a work-in-progress, my Threading namespace, but I warn you, some bits of it are certainly not finished (the ThreadPool class being the obvious one). You may want to take out the SyncMethods class and put it elsewhere. The Threading namespace also includes the WaitableThread class from this article.

Have fun!