Atomically moving list elements between lists using read-copy update

• US 20060112121A1
• Filed: 11/23/2004
• Published: 05/25/2006
• Est. Priority Date: 11/23/2004
• Status: Abandoned Application

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: McKenney, Paul E., Sarma, Dipankar, Krieger, Orran Y., Soni, Manneesh
• Application Number:
  US10/995,657
• Publication Number:
  US 20060112121A1
• Time in Patent Office: Days
• US Class Current: 1/1
• 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 atomically moving a shared list element from a first list location to a second list location, comprising:

inserting a placeholder element at said second list location for use by readers to monitor moving of said shared list element;

removing said shared list element from said first list location;

re-identifying said shared list element to reflect its move from said first list location to said second list location;

inserting said shared list element at said second list location and unlinking said placeholder element;

performing deferred removal of said placeholder element following a period in which readers maintain no references to said placeholder element.

2. A method in accordance with claim 1, wherein said placeholder element includes an indication of whether said move operation has completed.

3. A method in accordance with claim 1, wherein said placeholder element includes a reference count representing a count of readers maintaining references to said placeholder element, and wherein said period is determined by said reference count and by readers of said placeholder element passing through a quiescent state following said unlinking.

4. A method in accordance with claim 1, wherein said shared list element is a directory entry element in a file system directory list and said move operation is part of a file rename( ) operation.

5. A method in accordance with claim 1, wherein said shared list element is a directory entry element in a file system hash table chain and said move operation is part of a file rename( ) operation.

6. A method for performing a lookup of a target list element that is subject to being atomically moved from a first list to a second list, comprising:

initiating a list traversal beginning at a first list element; and

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

7. A method in accordance with claim 6, 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.

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

9. A method in accordance with claim 6, 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.

10. A method in accordance with claim 6, 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.

11. A data processing system having plural data processors, said system being adapted to atomically move a shared list element from a first list location to a second list location, comprising:

means for inserting a placeholder element at said second list location for use by readers to monitor moving of said shared list element;

means for removing said shared list element from said first list location;

means for re-identifying said shared list element to reflect its move from said first list location to said second list location;

means for inserting said shared list element at said second list location and unlinking said placeholder element;

means for performing deferred removal of said placeholder element following a period in which readers maintain no references to said placeholder element.

12. A system in accordance with claim 11, wherein said placeholder element includes an indication of whether said move operation has completed.

13. A system in accordance with claim 11, wherein said placeholder element includes a reference count representing a count of readers maintaining references to said placeholder element, and wherein said period is determined by said reference count and by readers of said placeholder element passing through a quiescent state following said unlinking.

14. A system in accordance with claim 11, wherein said shared list element is a directory entry element in a file system directory list and said move operation is part of a file rename( ) operation.

15. A system in accordance with claim 11, wherein said shared list element is a directory entry element in a file system hash table chain and said move operation is part of a file rename( ) operation.

16. A data processing system adapted to perform a lookup of a target list element that is subject to being atomically moved from a first list to a second list, comprising:

means for initiating a list traversal beginning at a first list element; and

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

17. A system in accordance with claim 16, 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.

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

19. A system in accordance with claim 16, 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.

20. A system in accordance with claim 16, 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.

21. A computer program product atomically moving a shared list element from a first list location to a second list location, comprising:

one or more data storage media;

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

inserting a placeholder element at said second list location for use by readers to monitor moving of said shared list element;

removing said shared list element from said first list location;

re-identifying said shared list element to reflect its move from said first list location to said second list location;

inserting said shared list element at said second list location and unlinking said placeholder element;

performing deferred removal of said placeholder element following a period in which readers maintain no references to said placeholder element.

22. A computer program product in accordance with claim 21, wherein said placeholder element includes an indication of whether said move operation has completed.

23. A computer program product in accordance with claim 21, wherein said placeholder element includes a reference count representing a count of readers maintaining references to said placeholder element, and wherein said grace period is determined by said reference count and by readers of said placeholder element passing through a quiescent state following said unlinking.

24. A computer program product in accordance with claim 21, wherein said shared list element is a directory entry element in a file system directory list and said move operation is part of a file rename( ) operation.

25. A computer program product in accordance with claim 21, wherein said shared list element is a directory entry element in a file system hash table chain and said move operation is part of a file rename( ) operation.

26. A computer program product for performing a lookup of a target list element that is subject to being atomically moved from a first list to a second list, comprising:

one or more data storage media;

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

initiating a list traversal beginning at a first list element; and

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

27. A computer program product in accordance with claim 26, 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.

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

29. A computer program product in accordance with claim 26, 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.

30. A computer program product in accordance with claim 26, 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.