Lock Free Deque that supports removing an arbitrary node

Question

This needs to be lock free as it has to run in the interrupt handler of an SMP system. I cannot take locks.

I have a contiguous array holding some values. Some of the entries in this array are "free", they are not occupied. I want to make a list of these entries so that I can quickly allocate one. However, I occasionally have to allocate an arbitrary entry.

Therefore, I see the following would be a nice way of doing things: The contiguous array holds not just values but also left and right pointers, thus making a deque. Only free values have valid left/right pointers. I can quickly get to arbitrary nodes because it is just an index access into the deque.

Now, to the crux of it: Is there a nice lock free deque algorithm that is relatively efficient and can support the removal of an arbitrary node?

Answer 1

The contiguous array holds not just values but also left and right pointers, thus making a deque.

[snip]

Now, to the crux of it: Is there a nice lock free deque algorithm that is relatively efficient and can support the removal of an arbitrary node?

A deque with the ability to remove arbitrary elements is really a doubly linked list; the only thing you've given up is the ability to insert arbitrary elements and removing is the hard part - if you can remove, you can certainly add.

A lock-free doubly linked list exists, but it requires garbage collection.

How about this; have a freelist. This represents available nodes. The nodes are actually an array, so you can index into them. When you have to use an arbitrary node, index into the array and then CAS a flag in that element but leave it in the freelist (you have to of course, since it's not at the top of the freelist). When you come in future to pop and you find you pop an element which has already been used, just keep popping till you find one which is free.