Lock Free Deque that supports removing an arbitrary node

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?

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.

In a garbage-collected system, it's possible to have a singly linked list support lock-free logical removal of items, if you don't care about when the memory for the items physically gets freed, and if it's not possible to add an item immediately following an item that's being deleted. Give each item a deleted flag, and have a list-traversal routine that will check as it visits each item whether the following node has been deleted; if it has, use compare and swap to swing the present node's "next" pointer around it. Note that it's possible that the "next" pointer of the node which was being deleted might get changed, but only to skip the node following it. It's possible that swinging a next pointer might cause a node which has just been unlinked from the list to get relinked (e.g. A->B->C->D might, if B and C are removed simultaneously, become A->B->D (swinging B s pointer) and then A->C->D (swinging A's pointer to the latched value of B's 'next' pointer). If node C was and continues to be flagged as "deleted", however, that shouldn't pose a problem, since the next time the list is iterated, A's pointer will swing to D.

Two caveats: -1- In a non-garbage-collected system, it may be difficult to know when a node can really be freed; freeing a node and then swinging a pointer back to it could cause Undefined Behavior; -2- If a node is added immediately following a deleted node, a pointer may swing so as to disconnect the new node. If nodes will always be added to the end of the queue, one can avoid this latter problem by ending the queue with a dummy node, which cannot be deleted until there's another node following it.