Atomically moving list elements between lists using read-copy update

• US 7,873,612 B2
• Filed: 10/11/2007
• Issued: 01/18/2011
• Est. Priority Date: 11/23/2004
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Soni, Maneesh, Sarma, Dipankar, Krieger, Orran Y., McKenney, Paul E.
• Primary Examiner(s): Jalil; Neveen Abel
• Assistant Examiner(s): Hicks; Michael J
• Application Number:
  US11/870,668
• Publication Number:
  US 20080033952A1
• Time in Patent Office: 1,195 Days
• Field of Search: 707/704, 707/999.008
• US Class Current: 707/704
• CPC Class Codes: G06F 16/9024 Graphs; Linked lists G06F16/9027 takes precedence

Abstract

A system, method and computer program product for atomically moving a shared list element from a first list location to a second list location includes inserting a placeholder element at the second list location to signify to readers that a move operation is underway, removing the shared list element from the first list location, re-identifying the list element to reflect its move from the first list location to the second list location, inserting it at the second list location and unlinking the placeholder element. A deferred removal of the placeholder element is performed following a period in which readers can no longer maintain references thereto. A method, system and computer program product are additionally provided for performing a lookup of a target list element that is subject to being atomically moved from a first list to a second list.

Claims

1. A method for performing a read operation lookup of a target list element that is subject to being atomically moved from a first list to a second list by a concurrent move operation, comprising:

initiating a read operation list traversal beginning at a first list element in said second list; and

upon encountering a list element that is a placeholder for said target list element in said second list that was generated as a result of said concurrent move operation involving said target list element being moved from said first list to said second list, waiting until said placeholder indicates that said move operation has completed, and thereafter returning read operation failure so that said lookup can be retried.

2. A method in accordance with claim 1, further including maintaining a count of elements traversed by said lookup and asserting a lock against concurrent move operations if said count reaches a computed maximum.

3. A method in accordance with claim 1, further including determining whether said lookup has been pulled from one list to another as a result of a concurrent move operation, and if true, returning to the initial list being traversed.

4. A method in accordance with claim 1, further including incrementing a reference count in said placeholder upon encountering said placeholder and decrementing said reference count if said placeholder indicates that said concurrent move operation has competed.

5. A method in accordance with claim 1, wherein said waiting on said placeholder comprises one of blocking on a global semaphore, blocking on a per-element semaphore, spinning on a global lock, and spinning on a per-element lock.

6. A data processing system adapted to perform a read operation lookup of a target list element that is subject to being atomically moved from a first list to a second list by a concurrent move operation, comprising:

means for initiating a read operation list traversal beginning at a first list element in said second list; and

means responsive to encountering a list element that is a placeholder for said target list element in said second list that was generated as a result of said concurrent move operation involving said target list element being moved from said first list to said second list for waiting until said placeholder indicates that said move operation has completed, and thereafter returning read operation failure so that said lookup can be retried.

7. A system in accordance with claim 6, further including means for maintaining a count of elements traversed by said lookup and for asserting a lock against concurrent move operations if said count reaches a computed maximum.

8. A system in accordance with claim 6, further including means for determining whether said lookup has been pulled from one list to another as a result of a concurrent move operation, and if true, returning to the initial list being traversed.

9. A system in accordance with claim 6, further including means for incrementing a reference count in said placeholder upon encountering said placeholder and decrementing said reference count if said placeholder indicates that said concurrent move operation has competed.

10. A system in accordance with claim 6, wherein said means for waiting on said placeholder comprises one of means for blocking on a global semaphore, means for blocking on a per-element semaphore, means for spinning on a global lock, and means for spinning on a per-element lock.

11. A computer program product for performing a read operation lookup of a target list element that is subject to being atomically moved from a first list to a second list by a concurrent move operation, comprising:

one or more data storage media;

means recorded on said data storage media for programming a data processing platform to operate during a read operation, as by;

initiating a read operation list traversal beginning at a first list element in said second list; and

upon encountering a list element that is a placeholder for said target list element in said second list that was generated as a result of said concurrent move operation involving said target list element being moved from said first list to said second list, waiting until said placeholder indicates that said move operation has completed, and thereafter returning read operation failure so that said lookup can be retried.

12. A computer program product in accordance with claim 11, further including maintaining a count of elements traversed by said lookup and asserting a lock against concurrent move operations if said count reaches a computed maximum.

13. A computer program product in accordance with claim 11, further including determining whether said lookup has been pulled from one list to another as a result of a concurrent move operation, and if true, returning to the initial list being traversed.

14. A computer program product in accordance with claim 11, further including incrementing a reference count in said placeholder upon encountering said placeholder and decrementing said reference count if said placeholder indicates that said concurrent move operation has competed.

15. A computer program product in accordance with claim 11, wherein said waiting on said placeholder comprises one of blocking on a global semaphore, blocking on a per-element semaphore, spinning on a global lock, and spinning on a per-element lock.