Practical lock-free doubly-linked list

Abstract

One embodiment of the present invention provides a system that supports inserting or deleting nodes at any location within a doubly-linked list which is lock-free, wherein lock-free means that the doubly-linked list can be simultaneously accessed by multiple processes without requiring the processes to perform locking operations (non-blocking) and furthermore that a finite number of steps performed by a process will guarantee progress by at least one process (lock-free). During operation, the system receives a reference to a target node to be deleted from the doubly-linked list. Next, the system atomically marks a forward pointer in the target node to indicate that the target node is deleted, wherein the forward pointer contains the address of an immediately following node in the doubly-linked list, and wherein the marking operation does not destroy the address of the immediately following node. Additional cleanup steps are then done by this or any other process. The system may also receive a new node which is accessible by only the requesting thread and may then insert the new node into the doubly linked list after a reference node. The system accomplishes this by setting the new node's backward pointer to the reference node and forward pointer to the successor of the reference node. Next, the system atomically changes the forward pointer of the reference node from the successor node to the new node. Additional cleanup steps are then done by this or any other process. An update operation that atomically performs a delete of an old node and an insert of its replacement node is also described.