Efficient garbage collection and exception handling in a hardware accelerated transactional memory system

• US 8,402,218 B2
• Filed: 12/15/2009
• Issued: 03/19/2013
• Est. Priority Date: 12/15/2009
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Gray, Jan, Taillefer, Martin, Levanoni, Yosseff, Adl-Tabatabai, Ali-Reza, Detlefs, Dave, Grover, Vinod K., Magruder, Michael, Sheaffer, Gad
• Primary Examiner(s): TSAI, SHENG JEN
• Application Number:
  US12/638,929
• Publication Number:
  US 20110145304A1
• Time in Patent Office: 1,190 Days
• Field of Search: 711/115, 711/E12.001, 711/E12.011, 707/820
• US Class Current: 711/115
• CPC Class Codes: G06F 12/0253 Garbage collection, i.e. reclamation of unreferenced memory
• CPC Class Codes: G06F 12/0815 Cache consistency protocols
• CPC Class Codes: G06F 12/082 Associative directories G06F12/0822 takes precedence
• CPC Class Codes: G06F 9/3004 to perform operations on memory
• CPC Class Codes: G06F 9/30087 Synchronisation or serialisation instructions
• CPC Class Codes: G06F 9/30185 according to one or more bits in the instruction, e.g. prefix, sub-opcode
• CPC Class Codes: G06F 9/3834 Maintaining memory consistency
• CPC Class Codes: G06F 9/466 Transaction processing
• CPC Class Codes: G06F 9/467 Transactional memory G06F9/528 takes precedence

Abstract

Handling garbage collection and exceptions in hardware assisted transactions. Embodiments are practiced in a computing environment including a hardware assisted transaction system. Embodiments includes acts for writing to a card table outside of a transaction; handling garbage collection compaction occurring when a hardware transaction is active by using a common global variable and instructing one or more agents to write to the common global variable any time an operation is performed which may change an object'"'"'s virtual address; acts for managing a thread-local allocation context; acts for handling exceptions while in a hardware assisted transaction. A method includes beginning a hardware assisted transaction, raising an exception while in the hardware assisted transaction, including creating an exception object, determining that the transaction should be rolled back, and as a result of determining that the transaction should be rolled back, marshaling the exception object out of the hardware assisted transaction.

Claims

1. In a computing environment comprising a hardware assisted transaction system, a method of writing to a card table in a generational garbage collection system that gives preference to performing garbage collection activities on newer generation generational objects, and where writing to the card table marks older generation generational objects that are updated with references pointing to newer generation generational objects so that references by the older generation generational objects can be given preference in garbage collection activities, the method comprising:

beginning a hardware assisted transaction to cause reads and writes to be buffered and monitored to prevent conflicting reads and writes, using an isolated cache memory structure;

determining, while the transaction is running, that a write entry needs to be made to a card table to keep track of a reference from an older generation generational object in a generational garbage collection system to a newer generation generational object in the generational garbage collection system; and

as a result of determining that a write entry needs to be made to a card table performing a write to an entry in the card table outside of the transaction, such that the entry is not added to the transaction'"'"'s write set and such that the write does not establish read or write monitoring on the entry, and such that the reference from the older generation generational object to the newer generation generational object in the card table remains even if the transaction is subsequently rolled back, thus causing garbage collection operations to be performed using the reference to the newer generational object irrespective of whether the reference is valid as a result of the transaction having committed or invalid as a result of the transaction having been rolled back.

2. The method of claim 1, wherein writing to the card table outside of the transaction comprises executing a specialized instruction that performs an explicitly non-hardware-transacted load and/or store.

3. The method of claim 1, further comprising:

suspending the transaction;

wherein writing to the card table outside of the transaction is performed while the transaction is suspended; and

resuming the transaction after writing to the card table.

4. The method of claim 1, further comprising:

aborting the hardware assisted transaction and rolling back any buffered writes performed during the transaction without rolling back the un-buffered non-transacted write to the card table.

5. The method of claim 4, further comprising performing a garbage collection including checking for objects that are still in use at a location pointed to by the un-buffered non-transacted write to the card table.

6. The method of claim 5, further comprising clearing the card table entry once no intergenerational references remain as indicated by the card table entry.

7. In a computing environment comprising a hardware assisted transaction system, a system for writing to a card table in a generational garbage collection system that gives preference to performing garbage collection activities on newer generation generational objects, and where writing to the card table marks older generation generational objects that are updated with references pointing to newer generation generational objects so that references by the older generation generational objects can be given preference in garbage collection activities, the system comprising:

one or more processors; and

one or more computer readable media, wherein the one or more computer readable media comprise computer executable instructions that when executed by at least one of the one or more processors cause at least one of the one or more processors to perform the following;

beginning a hardware assisted transaction to cause reads and writes to be buffered and monitored to prevent conflicting reads and writes, using an isolated cache memory structure;

determining, while the transaction is running, that a write entry needs to be made to a card table to keep track of a reference from an older generation generational object in a generational garbage collection system to a newer generation generational object in the generational garbage collection system; and

as a result of determining that a write entry needs to be made to a card table performing a write to an entry in the card table outside of the transaction, such that the entry is not added to the transaction'"'"'s write set and such that the write does not establish read or write monitoring on the entry, and such that the reference from the older generation generational object to the newer generation generational object in the card table remains even if the transaction is subsequently rolled back, thus causing garbage collection operations to be performed using the reference to the newer generational object irrespective of whether the reference is valid as a result of the transaction having committed or invalid as a result of the transaction having been rolled back.

8. The system of claim 7, wherein writing to the card table outside of the transaction comprises executing a specialized instruction that performs an explicitly non-hardware-transacted load and/or store.

9. The system of claim 7, the one or more computer readable media further comprising computer executable instructions that when executed by at least one of the one or more processors cause at least one of the one or more processors to perform the following:

suspending the transaction;

wherein writing to the card table outside of the transaction is performed while the transaction is suspended; and

resuming the transaction after writing to the card table.

10. The system of claim 7, the one or more computer readable media further comprising computer executable instructions that when executed by at least one of the one or more processors cause at least one of the one or more processors to perform the following:

aborting the hardware assisted transaction and rolling back any buffered writes performed during the transaction without rolling back the un-buffered non-transacted write to the card table.

11. The method of claim 10, the one or more computer readable media further comprising computer executable instructions that when executed by at least one of the one or more processors cause at least one of the one or more processors to perform a garbage collection including checking for objects that are still in use at a location pointed to by the un-buffered non-transacted write to the card table.

12. The method of claim 11, the one or more computer readable media further comprising computer executable instructions that when executed by at least one of the one or more processors cause at least one of the one or more processors to clear the card table entry once no intergenerational references remain as indicated by the card table entry.

13. One or more computer readable storage media, wherein the one or more computer readable storage media comprise computer executable instructions that when executed by at least one of the one or more processors cause at least one of the one or more processors to perform the following:

beginning a hardware assisted transaction to cause reads and writes to be buffered and monitored to prevent conflicting reads and writes, using an isolated cache memory structure;

determining, while the transaction is running, that a write entry needs to be made to a card table to keep track of a reference from an older generation generational object in a generational garbage collection system to a newer generation generational object in the generational garbage collection system; and

as a result of determining that a write entry needs to be made to a card table performing a write to an entry in the card table outside of the transaction, such that the entry is not added to the transaction'"'"'s write set and such that the write does not establish read or write monitoring on the entry, and such that the reference from the older generation generational object to the newer generation generational object in the card table remains even if the transaction is subsequently rolled back, thus causing garbage collection operations to be performed using the reference to the newer generational object irrespective of whether the reference is valid as a result of the transaction having committed or invalid as a result of the transaction having been rolled back.

14. The one or more computer readable storage media of claim 13, wherein writing to the card table outside of the transaction comprises executing a specialized instruction that performs an explicitly non-hardware-transacted load and/or store.

15. The one or more computer readable storage media of claim 13 further comprising computer executable instructions that when executed by at least one of the one or more processors cause at least one of the one or more processors to perform the following:

suspending the transaction;

wherein writing to the card table outside of the transaction is performed while the transaction is suspended; and

resuming the transaction after writing to the card table.

16. The one or more computer readable storage media of claim 13 further comprising computer executable instructions that when executed by at least one of the one or more processors cause at least one of the one or more processors to perform the following:

aborting the hardware assisted transaction and rolling back any buffered writes performed during the transaction without rolling back the un-buffered non-transacted write to the card table.

17. The one or more computer readable storage media of claim 16 further comprising computer executable instructions that when executed by at least one of the one or more processors cause at least one of the one or more processors to perform a garbage collection including checking for objects that are still in use at a location pointed to by the un-buffered non-transacted write to the card table.

18. The one or more computer readable storage media of claim 17 further comprising computer executable instructions that when executed by at least one of the one or more processors cause at least one of the one or more processors to clear the card table entry once no intergenerational references remain as indicated by the card table entry.