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
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
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.
- Lock-free data structures: the stack
- Lock-free data structures: the queue
- Lock-free data structures: the free list
- Lock-free data structures: the limited-priority queue
- Lock-free data structures: redux
- Lock-free data structures: the code
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
SyncMethods class and put it elsewhere. The
Threading namespace also includes the
class from this article.