System and Method for Performing Memory Management Using Hardware Transactions

• US 20120310987A1
• Filed: 06/23/2011
• Published: 12/06/2012
• Est. Priority Date: 06/03/2011
• Status: Active Grant

• Current Assignee: Oracle International Corporation (Oracle Corporation)
• Original Assignee: Oracle International Corporation (Oracle Corporation)
• Inventors: Dragojevic, Aleksandar, Herlihy, Maurice, Lev, Yosef, Moir, Mark S.
• Granted Patent: US 9,043,363 B2
• Time in Patent Office: Days
• US Class Current: 707/792
• CPC Class Codes: G06F 12/0261 using reference counting
• CPC Class Codes: G06F 12/0815 Cache consistency protocols
• CPC Class Codes: G06F 9/467 Transactional memory G06F9/528 takes precedence

Abstract

The systems and methods described herein may be used to implement a shared dynamic-sized data structure using hardware transactional memory to simplify and/or improve memory management of the data structure. An application (or thread thereof) may indicate (or register) the intended use of an element of the data structure and may initialize the value of the data structure element. Thereafter, another thread or application may use hardware transactions to access the data structure element while confirming that the data structure element is still part of the dynamic data structure and/or that memory allocated to the data structure element has not been freed. Various indicators may be used determine whether memory allocated to the element element can be freed.

Claims

1. A method, comprising:

performing by a computer;

beginning execution of an application that comprises one or more accesses to a dynamic-sized data structure, wherein the data structure is accessible by a plurality of threads of the application or by a plurality of applications;

the application designating that an element of the data structure is available to be accessed by the application; and

using a hardware transaction to access the data structure element while confirming that the data structure element is still an element of the data structure.

2. The method of claim 1, wherein said confirming comprises determining that the memory allocated to the data structure element has not yet been freed.

3. The method of claim 1, wherein said designating comprises updating an indicator associated with the data structure to reflect that the element of the data structure is available to be accessed by the application.

4. The method of claim 3, wherein the value of the indicator is usable to determine whether the data structure element is still an element of the data structure, and wherein said confirming comprises examining the indicator associated with the data structure element.

5. The method of claim 3, wherein the indicator is a reference counter associated with the data structure element, an indicator field within the data structure element, a pointer to the data structure element, or a pointer within the data structure element.

6. The method of claim 3, further comprising:

subsequent to updating the indicator to reflect that the data structure element is available to be accessed by the application, the application updating the indicator to reflect that the data structure element will no longer be accessed by or available to be accessed by the application; and

freeing memory allocated to the data structure element.

7. The method of claim 1, wherein the data structure comprises a last-in-first-out stack, a first-in-first-out queue, a linked list, or a dynamic-sized array.

8. The method of claim 1, wherein said designating further comprises the application initializing the value of the data structure, and wherein said initializing comprises writing an initial value to the data structure non-transactionally.

9. The method of claim 1, further comprising:

using another hardware transaction to attempt to write a value to the data structure element; and

in response to determining that the data structure element is not still an element of the data structure, the other hardware transaction completing without writing the value to the data structure element.

10. A system comprising:

one or more processors; and

a memory coupled to the one or more processors and comprising a shared memory space;

wherein the memory stores program instructions executable on the one or more processors to implement;

beginning execution of an application that comprises one or more accesses to a dynamic-sized data structure, wherein the data structure is accessible by a plurality of threads of the application or by a plurality of applications;

the application designating that an element of the data structure is available to be accessed by the application; and

using a hardware transaction to access the data structure element while confirming that the data structure element is still an element of the data structure.

11. The system of claim 10, wherein said confirming comprises determining that the memory allocated to the data structure element has not yet been freed.

12. The system of claim 10,

wherein said designating comprises updating an indicator associated with the data structure to reflect that the element of the data structure is available to be accessed by the application, wherein the value of the indicator is usable to determine whether the data structure element is still an element of the data structure;

and

wherein said confirming comprises examining the indicator associated with the data structure element.

13. The system of claim 12, wherein the program instructions are further executable on the one or more processors to implement:

subsequent to updating the indicator to reflect that the data structure element is available to be accessed by the application, the application updating the indicator to reflect that the data structure element will no longer be accessed by or available to be accessed by the application; and

freeing memory allocated to the data structure element.

14. The system of claim 10, wherein said designating further comprises the application initializing the value of the data structure, and wherein said initializing comprises writing an initial value to the data structure non-transactionally.

15. The system of claim 10, wherein the program instructions are further executable on the one or more processors to implement:

using another hardware transaction to attempt to write a value to the data structure element; and

in response to determining that the data structure element is not still an element of the data structure, the other hardware transaction completing without writing the value to the data structure element.

16. A non-transitory, computer readable storage medium storing program instructions that when executed on one or more computers cause the one or more computers to perform:

beginning execution of an application that comprises one or more accesses to a dynamic-sized data structure, wherein the data structure is accessible by a plurality of threads of the application or by a plurality of applications;

the application designating that an element of the data structure is available to be accessed by the application; and

using a hardware transaction to access the data structure element while confirming that the data structure element is still an element of the data structure.

17. The storage medium of claim 16, wherein said confirming comprises determining that the memory allocated to the data structure element has not yet been freed.

18. The storage medium of claim 16,

wherein said designating comprises updating an indicator associated with the data structure to reflect that the element of the data structure is available to be accessed by the application, wherein the value of the indicator is usable to determine whether the data structure element is still an element of the data structure;

and

wherein said confirming comprises examining the indicator associated with the data structure element.

19. The storage medium of claim 18, wherein when executed on the one or more computers, the program instructions further cause the one or more computers to perform:

subsequent to updating the indicator to reflect that the data structure element is available to be accessed by the application, the application updating the indicator to reflect that the data structure element will no longer be accessed by or available to be accessed by the application; and

freeing memory allocated to the data structure element.

20. The storage medium of claim 16, wherein when executed on the one or more computers, the program instructions further cause the one or more computers to perform:

using another hardware transaction to attempt to write a value to the data structure element; and

in response to determining that the data structure element is not still an element of the data structure, the other hardware transaction completing without writing the value to the data structure element.