Value recycling facility for multithreaded computations

• US 20030182462A1
• Filed: 01/10/2003
• Published: 09/25/2003
• Est. Priority Date: 01/11/2002
• 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
• Granted Patent: US 7,908,441 B2
• Time in Patent Office: Days
• US Class Current: 719/310
• CPC Class Codes: G06F 9/52 Program synchronisation; Mutual exclusion, e.g. by means of semaphores
• CPC Class Codes: Y10S 707/955 Object-oriented
• CPC Class Codes: Y10S 707/99953 Recoverability
• CPC Class Codes: Y10S 707/99957 Garbage collection

Abstract

Solutions to a value recycling problem 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 allow non-blocking, shared data structures to be implemented using standard dynamic allocation mechanisms (such as malloc and free). Some exploitations allow non-blocking, indeed even lock-free or wait-free, implementations of dynamic storage allocation for shared data structures. In some exploitations, our techniques provide a way to manage dynamically allocated memory in a non-blocking manner without depending on garbage collection. While exploitations of solutions to the value recycling problem that we propose include management of dynamic storage allocation wherein values managed and recycled tend to include values that encode pointers, they are not limited thereto. Indeed, the techniques are more generally applicable to management of values in a multithreaded computation. For example, value recycling techniques may be exploited, in some cases, apart from dynamic storage allocation, to allow a multithreaded computation to avoid the classic ABA hazard.

Claims

1. A lock-free method of managing a set of values in a multithreaded computation the method comprising:

indicating an intention to use a particular one of the values; and

as a condition precedent to use of the particular value, determining that the indication was sufficient to prevent recycling of the particular value.

2. The method of claim 1, employed, at least in part, in management of an ABA hazard of the multithreaded computation.

3. The method of claim 1,

wherein at least some of the values encode pointers;

and

wherein the use includes pointer dereferencing.

4. The method of claim 3, employed, at least in part, in management of memory for a data structure shared amongst at least two threads of the multithreaded computation, wherein the values are used to reference respective components of the data structure.

5. The method of claim 3, employed, at least in part, in management of an ABA hazard of the multithreaded computation.

6. The method of claim 3, further comprising:

the recycling.

7. The method of claim 3,

wherein the recycling includes qualifying particular storage for deallocation, the particular storage referenced by a pointer encoded by the particular value.

8. The method of claim 7, further comprising:

reusing the particular storage in the data structure prior to any freeing thereof.

9. The method of claim 7, further comprising:

freeing the particular storage.

10. The method of claim 3,

wherein the prevented recycling includes freeing particular storage referenced by a pointer encoded by the particular value.

11. The method of claim 3,

wherein the prevented recycling includes overwriting with the particular value, a first value in a storage location that previously encoded the particular value.

12. The method of claim 11,

wherein the particular value encodes a pointer.

13. The method of claim 11,

wherein the particular value encodes a non-pointer value.

14. The method of claim 1, further comprising:

canceling each indication sufficient to prevent the recycling.

15. The method of claim 1, further comprising:

as a condition precedent to the recycling of the particular value, determining that no indication sufficient to prevent the recycling remains uncancelled.

16. The method of claim 1,

wherein the particular value encodes a pointer to a dynamically-allocated component of a data structure.

17. The method of claim 1,

wherein the particular value encodes a non-pointer value.

18. The method of claim 1,

wherein the indicating includes storing the particular value in a structure shared amongst plural threads of a computation.

19. The method of claim 1,

wherein the sufficiency determination includes determining whether the indication was made in time to prevent the particular value from being recycled.

20. The method of claim 1,

wherein the indication once completed, remains in effect until cancelled.

21. The method of claim 1, further comprising:

recycling the particular value, wherein the recycling coincides with freeing of a data structure component corresponding to the particular value.

22. The method of claim 1,

wherein the indication the use of the particular value and cancellation of the indication are performed by a first thread of execution;

and

wherein the recycling is performed by a second thread of execution.

23. The method of claim 1, further comprising:

prior to the indicating, obtaining exclusive ownership of a handle,

wherein the indicating is made via the handle.

24. The method of claim 23,

wherein the exclusivity is obtained, at least in part, using a Compare-And-Swap (CAS) operation.

25. The method of claim 23,

wherein the exclusivity is obtained, at least in part, using Load-Linked (LL) and Store-Conditional (SC) operation pairs.

26. The method of claim 23,

wherein the exclusivity is obtained, at least in part, using transactional memory.

27. The method of claim 1,

wherein the indication is made by a particular thread of an execution sequence of states that includes one or more threads.

28. The method of claim 1, wherein operation thereof is one or more of:

wait-free;

lock-free; and

non-blocking.

29. The method of claim 1, employed, at least in part, in management of storage for an implementation of a dynamically sizable data structure, wherein the data structure implementation is one or more of:

wait-free;

lock-free; and

non-blocking.

30. The method of claim 1, employed, at least in part, in management of storage for an implementation of a dynamically sizable data structure, wherein the data structure implementation is not necessarily non-blocking.

31. In a computational system, a method of avoiding an ABA hazard, the method comprising:

recording an intention to use value A;

using the value A only after the recording is safely completed; and

overwriting a value B with the value A only after all safely completed recording for the value A are cancelled.

32. The method of claim 31,

wherein both A and B encode respective pointers.

33. The method of claim 31,

wherein both A and B encode respective non-pointer values.

34. The method of claim 31,

wherein one of A and B encodes a pointer;

another of A and B encodes a non-pointer value.

35. In a computational system, a method of avoiding improperly dereferencing a pointer, the method comprising:

recording an intention to use a particular pointer value;

using the particular pointer value only after the recording is safely completed; and

recycling the particular pointer value only after all safely completed recordings therefor are cancelled.

36. The method of claim 35,

wherein the recycling includes qualifying for deallocation storage referenced by the particular pointer value.

37. The method of claim 36, further comprising:

reusing the storage qualified for deallocation.

38. The method of claim 36, further comprising:

freeing the storage qualified for deallocation.

39. The method of claim 35,

wherein the recycling is performed without suspending threads of a mutator computation that accesses the object.

40. The method of claim 35,

wherein the use and the recycling are performed by different threads.

41. The method of claim 35,

wherein the recording includes storing the particular pointer value in a structure shared amongst plural threads of a computation.

42. The method of claim 35,

embodied as part of a garbage collector implementation.

43. The method of claim 35, wherein operation thereof is one or more of:

wait-free

lock-free; and

non-blocking.

44. A dynamic-sized, non-blocking data structure encoded in a computer readable medium, wherein failure of any computational thread operating on the non blocking data structure prevents future reclamation of no more than a bounded number of storage blocks thereof.

45. The dynamic-sized, non-blocking data structure of claim 44,

wherein synchronization amongst operations on the dynamic-sized, non-blocking data structure is mediated, at least in part, using a Compare-And-Swap (CAS) operation.

46. The dynamic-sized, non-blocking data structure of claim 44,

wherein synchronization amongst operations on the dynamic-sized, non-blocking data structure is mediated, at least in part, using Load-Linked (LL) and Store-Conditional (SC) operation pairs.

47. The dynamic-sized, non-blocking data structure of claim 44,

wherein synchronization amongst operations on the dynamic-sized, non-blocking data structure is mediated, at least in part, using transactional memory.

48. The dynamic-sized, non-blocking data structure of claim 44, implementing one or more of a list, queue, deque, tree and a stack.

49. The dynamic-sized, non-blocking data structure of claim 44, embodied as an object that:

records an intention to use a particular pointer value that identifies storage of the dynamic-sized, non-blocking data structure; and

as a condition precedent to use of the particular pointer value, determines that the recording was sufficient to prevent recycling of the particular value.

50. The dynamic-sized, non-blocking data structure of claim 49, embodied as an object that recycles the particular pointer value only after each sufficient recording has been cancelled.

51. The dynamic-sized, non-blocking data structure of claim 49, for use in an execution environment with one or more worker threads that recycle the particular pointer value only after each sufficient recording thereof has been cancelled.

52. The dynamic-sized, non-blocking data structure of claim 44,

wherein the computer readable medium is selected from the set of a disk, tape or other magnetic, optical or electronic storage medium.

53. One or more instruction sequences that, when executed, produce a multithreaded computation that, prior to use of a particular value, determines that a recording of an intent to use the particular value was sufficient to prevent recycling thereof the instruction sequences encoded in one or more computer readable media.

54. The instruction sequences of claim 53,

wherein failure of any thread of the multithreaded computation prevents the recycling of no more than a bounded number of values used thereby.

55. The instruction sequences of claim 53,

employed, at least in part, in management of storage for a data structure shared amongst threads of the multithreaded computation, wherein the particular values is used to reference a respective component of the data structure.

56. The instruction sequences of claim 53,

employed, at least in part, in management of an ABA hazard of the multithreaded computation.

57. The instruction sequences of claim 53,

wherein the particular value encodes a pointer.

58. The instruction sequences of claim 57,

wherein the use includes dereferencing the pointer.

59. The instruction sequences of claim 53,

wherein the particular value encodes a non-pointer value.

60. The instruction sequences of claim 53,

wherein the recycling includes qualifying the particular value for deallocation.

61. The instruction sequences of claim 60,

wherein the recycling further includes freeing storage corresponding to the particular value.

62. The instruction sequences of claim 53,

wherein the computer readable media are selected from the set of a disk, tape or other magnetic, optical or electronic storage medium.

63. A method of managing dynamically allocated memory for a dynamic sized data structure, the method comprising:

in a multithreaded computation, allocating storage from, and returning freed storage to, the dynamically allocated memory, at least some of the allocated and returned storage employed in the dynamic sized data structure; and

continuing to return freed storage to the dynamically allocated memory despite failure of any thread of the computation.

64. The method of claim 63, further comprising:

recording in storage shared amongst plural threads of the multithreaded computation a particular pointer value that identifies storage to be modified in the dynamic sized, lock-free data structure; and

as a condition precedent to use of the particular pointer value, determining that the recording was sufficient to prevent freeing of the storage identified thereby.

65. The method of claim 64, further comprising:

freeing the storage identified by the particular pointer value only after each sufficient recording there of is cancelled.

66. A computer program product-encoded in one or more computer readable media and including a mechanism for management of a value set, the mechanism comprising:

a first instruction sequence responsive to a first execution thread of a computation to announce a particular value, prior to use thereof by the first execution thread; and

a second instruction sequence responsive to the first execution thread to cancel the announcement and thereby mark the particular value as unsafe for use by the first execution thread; and

a third instruction sequence executable to recycle values, the recycling occurring for the particular value only if no sufficient announcement thereof remains uncancelled.

67. The computer program product of claim 66,

wherein the particular value encodes a pointer;

and

wherein the recycling includes qualifying for deallocation particular storage referenced by the pointer.

68. The computer program product of claim 67,

wherein the recycling further includes freeing the particular storage.

69. The computer program product of claim 66,

wherein the recycling includes overwriting with the particular value, a first value in a storage location that previously encoded the particular value.

70. The computer program product of claim 66, further comprising:

an encoding of a set of handles whereby announcement of the particular value and of other values is made, wherein ownership of respective ones of the handles is mediated using a synchronization construct.

71. The computer program product of claim 70,

wherein the synchronization construct is a single-target synchronization construct.

72. The computer program product of claim 70,

wherein the synchronization construct includes a Compare-and-Swap (CAS) operation.

73. The computer program product of claim 70,

wherein the synchronization construct includes a load-linked (LL) and store-conditional (SC) operation pair.

74. The computer program product of claim 70,

wherein the synchronization primitive employs, or is emulated using, a transactional memory facility.

75. The computer program product of claim 66,

embodied at least in part as part of a memory allocator.

76. The computer program product of claim 66,

embodied at least in part as part of a garbage collection facility.

77. The computer program product of claim 66,

wherein the one or more computer readable media are selected from the set of a disk, tape or other magnetic, optical or electronic storage medium and a network, wireline, wireless or other communications medium.

78. A computer readable encoding of a multithreaded computation wherein individual threads thereof employ an exit mechanism that allows the respective individual thread to exit without leaking values or resources associated therewith and without waiting for operation of another one of the threads, the exit mechanism handing off values for which a preuse announcement remains uncancelled.

79. The computer readable encoding of claim 78,

wherein the values encode pointers;

and

wherein the associated resources include storage referenced by respective ones of the pointers.

80. The computer readable encoding of claim 78,

wherein the exit mechanism directly or indirectly recycles the values or resources associated therewith.

81. The computer readable encoding of claim 78,

embodied as instruction sequences executable to produce the individual threads.