Method and apparatus for performing lock-free updates in a linked list

摘要

One embodiment of the present invention provides a system that performs a lock-free update to one or more fields in an existing node in a linked list. To perform the update, the system first obtains a new node to be added to the linked list, wherein other processes do not possess references to the new node and therefore cannot initially access the new node. Next, the system copies a snapshot of the existing node to the new node, and then updates one or more fields in the new node that correspond to the one or more fields in the existing node. Next, in a single atomic operation the system modifies a next pointer of the existing node to point to the new node and also marks the next pointer to indicate that the existing node is deleted. In this way, the new node becomes part of the linked list and the existing node is deleted in a single atomic operation.

主权项

1. A computer-implemented method for performing a lock-free update to one or more fields in an existing node in a linked list, comprising:
receiving a reference to the existing node in the linked list, wherein the existing node contains the one or more fields to be updated; obtaining a new node to be added to the linked list, wherein other processes do not possess references to the new node and therefore cannot initially access the new node; copying a snapshot of the existing node to the new node, which includes copying a next pointer of the existing node to the new node, so that the new node points to a node immediately following the existing node, wherein said copying involves locating a version of the existing node that has not been deleted, and wherein said locating involves iteratively examining and following one or more next pointers; updating one or more fields in the new node that correspond to the one or more fields in the existing node; performing a single atomic operation that modifies the next pointer of the existing node to point to the new node and also marks the next pointer to indicate that the existing node is deleted, whereby the new node becomes part of the linked list and the existing node is deleted in a single atomic operation; and splicing the existing node out of the linked list by atomically modifying the next pointer of a node immediately preceding the existing node in the linked list to point to the new node, instead of pointing to the existing node.