System and Method for Implementing Nonblocking Zero-Indirection Transactional Memory

• US 20090171962A1
• Filed: 12/31/2007
• Published: 07/02/2009
• Est. Priority Date: 12/31/2007
• Status: Active Grant

• Current Assignee: Oracle America, Inc. (Oracle Corporation)
• Original Assignee: Oracle America, Inc. (Oracle Corporation)
• Inventors: Al Tabba', Fu'ad W. F., Moir, Mark S., Goodman, James R., Wang, Cong
• Granted Patent: US 8,140,497 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 9/467 Transactional memory G06F9/528 takes precedence

Abstract

Systems and methods for implementing and using nonblocking zero-indirection software transactional memory (NZSTM) are disclosed. NZSTM systems implement object-based software transactional memory that eliminates all levels of indirection except in the uncommon case of a conflict with an unresponsive thread. Shared data is co-located with a header in an NZObject, and is addressable at a fixed offset from the header. Conflicting transactions are requested to abort themselves without being forced to abort. NZObjects are modified in place when there are no conflicts, and when a conflicting transaction acknowledges the abort request. In the uncommon case, NZObjects are inflated to introduce a locator and some levels of indirection, and are restored to their un-inflated form following resolution of the conflict. In some embodiments, transactions are executed using best effort hardware transactional memory if it is available and effective, and software transactional memory if not, yielding a hybrid transactional memory system, NZTM.

Claims

1. A computer-implemented method, comprising:

a transaction initiating opening a shared object for writing;

the transaction determining that the shared object is owned for writing by another transaction;

the transaction requesting that the owning transaction abort itself;

wherein said requesting comprises indicating to the owning transaction that an abort is requested without forcing a change in status for the owning transaction.

2. The method of claim 1, wherein said indicating comprises setting a flag associated with the owning transaction to indicate a request that the owning transaction abort itself.

3. The method of claim 1, further comprising, in response to the owning transaction acknowledging that it will abort itself, the transaction assuming write ownership of the shared object.

4. The method of claim 1, further comprising, in response to the owning transaction not acknowledging the abort request:

the transaction creating a copy of the shared object in another location;

the transaction inflating the shared object to include a locator object, wherein the locator object comprises metadata associating the transaction with the copy of the shared object;

the transaction assuming write ownership of the shared object; and

the transaction modifying the copy of the shared object.

5. The method of claim 4, further comprising:

subsequent to said transaction assuming ownership, the owning transaction aborting itself; and

in response to the owning transaction aborting itself, another transaction restoring the shared object to its un-inflated form.

6. The method of claim 4, wherein the owning transaction is considered to have not acknowledged the abort request if the owning transaction does not acknowledge that it will abort itself within a pre-determined timeout period following said transaction requesting that the owning transaction abort itself.

7. The method of claim 4, wherein said creating a copy, inflating the shared object, assuming write ownership, and modifying the copy of the shared object are performed in response to a contention manager determining that the transaction should not wait for the owning transaction to acknowledge the abort request before proceeding.

8. The method of claim 1, wherein the shared object comprises a header portion and a data portion co-located with the header portion and addressable at a fixed offset from the header portion.

9. The method of claim 1,

wherein the shared object comprises a header portion and a data portion,

wherein the header portion comprises an indicator of the owning transaction;

and

wherein said determining comprises reading the value of the indicator.

10. The method of claim 9, wherein the header portion further comprises one or more of:

an indicator of a reader list comprising one or more transactions having read ownership of the shared object, an indicator of a location of a backup copy of the data portion, and an indicator of a clone function usable for creating backup copies of the data portion.

11. The method of claim 1,

wherein said initiating and said determining are performed by a hardware transaction;

and

wherein in response to said determining, said requesting is performed by a software transaction.

12. A system comprising:

one or more processors; and

a memory coupled to the one or more processors and comprising a shared object accessible by one or more threads executing on the one or more processors;

wherein the memory further comprises program instructions executable by the one or more processors to implement;

a transaction initiating opening the shared object for writing;

the transaction determining that the shared object is owned for writing by another transaction;

the transaction requesting that the owning transaction abort itself;

wherein said requesting comprises indicating to the owning transaction that an abort is requested without forcing a change in status for the owning transaction.

13. The system of claim 12, wherein the program instructions are further executable to implement, in response to the owning transaction acknowledging that it will abort itself, the transaction assuming write ownership of the shared object.

14. The system of claim 12, wherein the program instructions are further executable to implement, in response to the owning transaction not acknowledging the abort request:

the transaction creating a copy of the shared object in another location;

the transaction inflating the shared object to include a locator object, wherein the locator object comprises metadata associating the transaction with the copy of the shared object;

the transaction assuming write ownership of the shared object; and

the transaction modifying the copy of the shared object.

15. The system of claim 14, wherein the program instructions are further executable to implement:

subsequent to said transaction assuming ownership, the owning transaction aborting itself; and

in response to the owning transaction aborting itself, another transaction restoring the shared object to its un-inflated form.

16. The system of claim 12, wherein the shared object comprises:

a header portion; and

a data portion co-located with the header portion and addressable at a fixed offset from the header portion;

wherein the header portion comprises one or more of;

an indicator of the owning transaction, an indicator of a reader list comprising one or more transactions having read ownership of the shared object, an indicator of a location of a backup copy of the data portion, and an indicator of a clone function usable for creating backup copies of the data portion.

17. The system of claim 12, wherein the program instructions are further executable to implement:

performing said initiating and said determining using a hardware transaction; and

in response to said determining, performing said requesting using a software transaction.

18. A computer-readable storage medium comprising program instructions computer-executable to implement:

a transaction initiating opening a shared object for writing;

the transaction determining that the shared object is owned for writing by another transaction;

the transaction requesting that the owning transaction abort itself;

wherein the shared object comprises;

a header portion; and

a data portion co-located with the header portion and addressable at a fixed offset from the header portion;

wherein the header portion comprises one or more of;

an indicator of the owning transaction, an indicator of a reader list comprising one or more transactions having read ownership of the shared object, an indicator of a location of a backup copy of the data portion, and an indicator of a clone function usable for creating backup copies of the data portion.

wherein said requesting comprises indicating to the owning transaction that an abort is requested without forcing a change in status for the owning transaction.

19. The storage medium of claim 18, wherein the program instructions are further executable to implement, in response to the owning transaction acknowledging that it will abort itself, the transaction assuming write ownership of the shared object.

20. The storage medium of claim 18, wherein the program instructions are further executable to implement, in response to the owning transaction not acknowledging the abort request:

the transaction creating a copy of the shared object in another location;

the transaction inflating the shared object to include a locator object, wherein the locator object comprises metadata associating the transaction with the copy of the shared object;

the transaction assuming write ownership of the shared object;

the transaction modifying the copy of the shared object;

subsequent to said transaction assuming ownership, the owning transaction aborting itself; and

in response to the owning transaction aborting itself, another transaction restoring the shared object to its un-inflated form.