Single-word lock-free reference counting

• US 7,299,242 B2
• Filed: 01/10/2003
• Issued: 11/20/2007
• Est. Priority Date: 01/12/2001
• Status: Active Grant

• Current Assignee: Oracle America, Inc. (Oracle Corporation)
• Original Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Inventors: Moir, Mark S., Herlihy, Maurice, Luchangco, Victor
• Primary Examiner(s): Bullock, Jr.; Lewis A.
• Application Number:
  US10/340,150
• Publication Number:
  US 20030140085A1
• Time in Patent Office: 1,775 Days
• Field of Search: 707/103, 707/107, 707/206, 719/315, 718/100, 718/102
• US Class Current: 1/1
• CPC Class Codes: G06F 9/52 Program synchronisation; Mutual exclusion, e.g. by means of semaphores
• CPC Class Codes: Y10S 707/99944 Object-oriented database structure
• CPC Class Codes: Y10S 707/99947 Object-oriented database structure reference
• CPC Class Codes: Y10S 707/99953 Recoverability

Abstract

Solutions to a value recycling problem that we define herein facilitate implementations of computer programs that may execute as multithreaded computations in multiprocessor computers, as well as implementations of related shared data structures. Some exploitations of the techniques described herein allow non-blocking, shared data structures to be implemented using standard dynamic allocation mechanisms (such as malloc and free). A class of general solutions to value recycling is described in the context of an illustration we call the Repeat Offender Problem (ROP), including illustrative Application Program Interfaces (APIs) defined in terms of the ROP terminology. Furthermore, specific solutions, implementations and algorithm, including a Pass-The-Buck (PTB) implementation are also described. Solutions to the proposed value recycling problem have a variety of uses. For example, a single-word lock-free reference counting (SLFRC) technique may build on any of a variety of value recycling solutions to transform, in a straight-forward manner, many lock-free data structure implementations that assume garbage collection (i.e., which do not explicitly free memory) into dynamic-sized data structures.

Claims

1. A lock-free method of managing storage reclamation in a multi-threaded computation, the method comprising:

maintaining respective reference counts for storage blocks of a data structure shared amongst threads of the multi-threaded computation; and

accessing pointers to the storage blocks using pointer operations to coordinate modification of the respective reference counts, wherein as a condition precedent to dereferencing a particular pointer loaded from the shared data structure, at least one of the pointer operations ensures that (i) an indication is made that one of the threads intends to dereference the particular pointer and (ii) the indication is sufficient to prevent freeing of a particular storage block referenced by the particular pointer.

2. The method of claim 1, wherein, if and when eventually fired, the particular storage block is returned for general reuse.

3. The method of claim 1, further comprising:

qualifying the particular storage block for deallocation once the respective reference count indicates that the particular storage block is unreferenced by shared memory and unreferenced by another thread.

4. The method of claim 3, further comprising:

freeing the qualified storage block only after no indication thereon sufficient to prevent freeing remains uncancelled.

5. The method of claim 1, wherein the pointer operations employ no multi-target synchronization constructs in coordination of modifications of the respective reference counts.

6. The method of claim 1, wherein the pointer operations employ no DCAS operations in coordination of modifications of the respective reference counts.

7. The method of claim 1, wherein the pointer operations include a load-type operation that loads a shared pointer value to a local pointer variable and employs a value recycling solution to coordinate access to a corresponding reference count.

8. The method of claim 1, wherein the pointer operations include a destroy-type operation that employs a value recycling solution to ensure that threads of the multithreaded computation do not access freed objects.

9. The method of claim 1, wherein the pointer operations ensure, in the absence of thread failures, that:

if a number of pointers referencing the particular storage block is nonzero, then so too is the corresponding reference count; and

if no pointers reference the particular storage block, then the corresponding reference count eventually becomes zero.

10. The method of claim 9, wherein at any given instant, the number of pointers to the particular storage block may differ from the corresponding reference count.

11. The method of claim 1, wherein the pointer operations include a destroy-type operation that:

decrements a reference count for a storage block identified by a supplied pointer value; and

requests qualification of the identified storage block for deallocation once the respective reference count indicates that the identified storage block is unreferenced by shared memory and unreferenced by another thread.

12. The method of claim 11, wherein the destroy-type operation further qualifies the identified storage block for deallocation.

13. The method of claim 11, wherein the destroy-type operation further frees a qualified storage block if no indication thereon sufficient to prevent freeing remains uncancelled.

14. The method of claim 13, wherein the qualified storage block was identified by the supplied pointer value.

15. The method of claim 13, wherein the qualified storage block was identified by a pointer value supplied to another invocation of the destroy-type operation.

16. The method of claim 11, wherein the destroy-type operation recursively follows pointers defined in the storage block if the respective reference counts indicate that respective storage is unreferenced by shared memory and unreferenced by another thread.

17. The method of claim 1, wherein the pointer operations include a store-type operation that stores a local pointer value to a shared pointer variable and employs:

a first single-target synchronization construct to increment a reference count for a first storage block, if any, referenced by the local pointer value;

a second single-target synchronization construct to update the shared pointer variable with the local pointer value; and

a third single-target synchronization construct to decrement a reference count of a second storage block, if any, referenced by a pre-store value for the shared pointer variable.

18. The method of claim 17, wherein one or more of the first, second and third synchronization constructs include, or are emulated using, one of:

a compare-and-swap (CAS) operation;

a Load-Linked (LL) and Store-Conditional (SC) operation pair; and

transactional memory.

19. The method of claim 1, wherein the pointer operations include a copy-type operation that copies a local pointer value to a local pointer variable and employs:

a first single-target synchronization construct to increment a reference count for a first storage block, if any, referenced by the local pointer value; and

a second single-target synchronization construct to decrement a reference count for a second storage block, if any, referenced by a pre-copy value of the local pointer variable.

20. An implementation of a shared data structure comprising:

plural component blocks of dynamically-allocated shared storage; and

access operations that, prior to attempting creation or replication of a pointer to any of the component blocks, increment a corresponding reference count, and upon failure of the attempt, thereafter decrement the corresponding reference count,

the access operations decrementing a particular reference count, except when handling a pointer creation failure, no earlier than upon destruction of a pointer to a corresponding one of the component blocks,

wherein as a condition precedent to dereferencing a pointer loaded from the shared data structure, a guard is posted on the loaded pointer sufficient to prevent freeing of a particular one of the component blocks referenced by the loaded pointer.

21. The shared data structure implementation of claim 20, wherein the access operations employ lock-free, reference-count-maintaining pointer operations.

22. The shared data structure implementation of claim 20, wherein the access operations include one or more of:

a lock-free, reference-count-maintaining load-type operation;

a lock-free, reference-count-maintaining store-type operation;

a lock-free, reference-count-maintaining copy-type operation;

a lock-free, reference-count-maintaining destroy-type operation; and

a lock-free, reference-count-maintaining compare-and-swap (CAS) operation.

23. The shared data structure implementation of claim 20, wherein each of the access operations are lock-free.

24. The shared data structure implementation of claim 20, wherein each of the access operations employs a respective synchronization construct selected from a set of single-target synchronization constructs.

25. The shared data structure implementation of claim 20, wherein each of the access operations employs a respective synchronization construct that includes, or is emulated using one of:

a compare-and-swap (CAS) operation;

a Load-Linked (LL) and Store-Conditional (SC) operation pair; and

transactional memory.

26. The shared data structure implementation of claim 20, wherein each of the access operations employ a same single-target synchronization construct.

27. The shared data structure implementation of claim 20, wherein the access operations employ no multi-target synchronization constructs in coordinating access to the shared data structure.

28. A method of transforming an implementation of a shared data structure from garbage collection (GC-) dependent to GC-independent form, the method comprising:

associating a reference count with each shared object instance;

modifying the implementation, if necessary, to ensure cycle-free garbage;

replacing pointer accesses in the implementation with corresponding lock-free, reference-count-maintaining counterpart operations, wherein at least one of the counterpart operations ensures that, as a condition precedent to dereferencing a particular pointer loaded from the shared data structure, (i) a guard is posted on the particular pointer and (ii) the posting is sufficient to prevent freeing of a particular storage block referenced by the particular pointer.

29. The method of claim 28, further comprising:

managing local pointer variables using a lock-free, reference-count-maintaining destroy-type operation that frees the particular storage block only if a corresponding reference count indicates that no other thread maintains a reference thereto and only after no posting thereon sufficient to prevent freeing remains uncancelled.

30. The method of claim 28, wherein the replacement of pointer accesses includes one or more of:

replacing an access that assigns a shared pointer value to a local pointer variable with a lock-free, reference-count-maintaining load-type operation;

replacing an access that assigns a local pointer value to a shared pointer variable with a lock-free, reference-count-maintaining store-type operation; and

replacing an access that assigns a local pointer value to a local pointer variable with a lock-free, reference-count-maintaining copy-type operation.

31. The method of claim 28, wherein the lock-free, reference-count-maintaining counterpart operations include object type specific instances thereof.

32. The method of claim 28, wherein the lock-free, reference-count-maintaining counterpart operations are generic to plural object types.

33. The method of claim 28, wherein the lock-free, reference-count-maintaining destroy operation is recursive.

34. The method of claim 28, further comprising:

generating a computer program product including a computer readable encoding of the shared data structure, which is instantiable in dynamically-allocated shared storage, the computer readable encoding further including functional sequences that facilitate access to the shared data structure and that include the lock-free, reference-count-maintaining counterpart operations.

35. A computer-readable storage medium, comprising:

a representation of a shared object that is instantiable as zero or more component objects in dynamically-allocated shared storage of a multiprocessor; and

an instruction sequence executable by at least one thread of a computation by the multiprocessor, the instruction sequence including at least one access operation on the shared object and employing one or more lock-free pointer operations to maintain reference counts for one or more accessed component objects thereof, wherein at least one of the lock-free pointer operations ensures that, as a condition precedent to dereferencing a particular pointer loaded from the shared data structure, (i) a guard is posted on the particular pointer and (ii) the posting is sufficient to prevent freeing of a particular storage block referenced by the particular pointer.

36. The storage medium of claim 35, further comprising:

a second instruction sequence executable by at least one thread of a computation by the multiprocessor, the second instruction sequence providing explicit reclamation of the component objects, freeing storage associated with a particular one of the component objects only if a corresponding reference count indicates that no shared memory and no other thread maintains a reference thereto and only after no posting thereon sufficient to prevent freeing remains uncancelled.

37. The storage medium of claim 35, further comprising:

a second instruction sequence executable by at least one thread of a computation by the multiprocessor, the second instruction sequence at least partially implementing a mutator that provides explicit reclamation of the dynamically allocated shared storage.

38. The storage medium of claim 35, further comprising:

a second instruction sequence executable by at least one thread of a computation by the multiprocessor, the second instruction sequence at least partially implementing a garbage collector that reclaims shared storage dynamically-allocated for a mutator, and that employs the shared object in coordination thereof.

39. The storage medium of claim 35, wherein the storage medium is selected from the set of a disk, a tape, a magnetic storage medium, an optical storage medium, and another electronic storage medium.

40. An apparatus, comprising:

a plurality of processors;

one or more stores addressable by the plurality of processors;

one or more shared pointer variables accessible by each of the plurality of processors for referencing a shared object encoded in the one or more stores;

means for coordinating competing accesses to the shared object using one or more reference counts and one or more lock-free pointer operations that employ a value recycling solution free of multi-target synchronization constructs; and

means for ensuring that, as a condition precedent to dereferencing a particular pointer loaded from the shared object, (i) a guard is posted on the particular pointer and (ii) the posting is sufficient to prevent freeing of a particular storage block referenced by the particular pointer.

41. The apparatus of claim 40, further comprising:

means for freeing a storage block of the shared object only if a corresponding reference count indicates that no shared memory and no other processor maintains a reference thereto and only after no posting thereon sufficient to prevent freeing remains uncancelled.