Implementing strong atomicity in software transactional memory

• US 8,099,726 B2
• Filed: 03/23/2006
• Issued: 01/17/2012
• Est. Priority Date: 12/07/2005
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Harris, Timothy Lawrence
• Primary Examiner(s): Puente, Emerson
• Assistant Examiner(s): Labud, Jonathan R
• Application Number:
  US11/389,334
• Publication Number:
  US 20070143276A1
• Time in Patent Office: 2,126 Days
• Field of Search: None
• US Class Current: 717/159
• CPC Class Codes: G06F 12/0253 Garbage collection, i.e. reclamation of unreferenced memory
• CPC Class Codes: G06F 12/0802 Addressing of a memory level in which the access to the desired data or data block requires associative addressing means, e.g. caches
• CPC Class Codes: G06F 8/443 Optimisation
• CPC Class Codes: G06F 8/4435 Detection or removal of dead or redundant code
• CPC Class Codes: G06F 8/4441 Reducing the execution time required by the program code
• CPC Class Codes: G06F 9/3004 to perform operations on memory
• CPC Class Codes: G06F 9/30047 Prefetch instructions; cache control instructions
• CPC Class Codes: G06F 9/30181 Instruction operation extension or modification
• CPC Class Codes: G06F 9/3802 Instruction prefetching
• CPC Class Codes: G06F 9/45525 Optimisation or modification within the same instruction set architecture, e.g. HP Dynamo
• CPC Class Codes: G06F 9/466 Transaction processing
• CPC Class Codes: G06F 9/467 Transactional memory G06F9/528 takes precedence

Abstract

A software transactional memory system is described which utilizes decomposed software transactional memory instructions as well as runtime optimizations to achieve efficient performance. The decomposed instructions allow a compiler with knowledge of the instruction semantics to perform optimizations which would be unavailable on traditional software transactional memory systems. Additionally, high-level software transactional memory optimizations are performed such as code movement around procedure calls, addition of operations to provide strong atomicity, removal of unnecessary read-to-update upgrades, and removal of operations for newly-allocated objects. During execution, multi-use header words for objects are extended to provide for per-object housekeeping, as well as fast snapshots which illustrate changes to objects. Additionally, entries to software transactional memory logs are filtered using an associative table during execution, preventing needless writes to the logs. Finally a garbage collector with knowledge of the software transactional memory system compacts software transactional memory logs during garbage collection.

Claims

1. A method for analyzing and modifying computer code to comprise atomic memory operations in a transactional memory system for memory operations contained outside of memory transactions, the method comprising:

compiling computer code comprising memory transactions comprising atomic blocks of code;

during compilation of the computer code comprising memory transactions comprising atomic blocks of code;

identifying one or more non-transactional memory operations which access objects outside of memory transactions comprising atomic blocks of code; and

augmenting an identified non-transactional memory operation which accesses an object outside of a memory transaction comprising an atomic block of code creating a new atomic block of code comprising the identified non-transactional memory operation and an open operation which opens the object for access by the non-transactional memory operation before the identified non-transactional memory operation, the new atomic block of code ensuring atomicity between transactional memory accesses to the object and accesses to the object by the new atomic block of code.

2. The method of claim 1, wherein augmenting a non-transactional memory operation comprises:

inserting a commit operation after the non-transactional memory operation which determines if there was a conflicting access to the object during execution of the non-transactional memory operation.

3. The method of claim 2, wherein:

the non-transactional memory operation is a read operation;

the open operation is configured to retrieve an indication of the state of the object before execution of the non-transactional memory operation; and

the commit operation is configured to;

retrieve an indication of the state of the object after execution of the non-transactional memory operation; and

if the state of the object indicates a conflicting access, cause the open, read, and commit operations to loop until a read is possible.

4. The method of claim 2, wherein:

the non-transactional memory operation is a write operation;

the open operation is configured to obtain write access to the object; and

the commit operation is configured to commit the write made to the object.

5. The method of claim 4, wherein:

the open operation is configured to update a software transactional memory word for the object to indicate that the object is being written to; and

the commit operation is configured to replace the software transactional memory word to indicate that the object has been updated.

6. The method of claim 2, wherein the open and commit commands utilize synchronization on the object to ensure that the non-transactional memory operation performs atomically.

7. The method of claim 2, wherein the open command blocks until it can open the object for access.

8. The method of claim 1, wherein identifying one or more memory operations comprises:

analyzing transactional memory accesses to determine fields which may be accessed by transactional memory operations during execution of the software;

identifying one or more non-transactional memory operations which access fields which may be accessed by transactional memory operations.

9. The method of claim 8, wherein analyzing transactional memory accesses comprises performing a type-based analysis on atomic blocks in the software.

10. The method of claim 8, wherein, for any field which is guaranteed not to be accessed by transactional memory operations, augmenting of non-transactional memory operations which access that field is avoided.

11. The method of claim 10, wherein augmenting a non-transactional memory operation which accesses an object outside of a memory transaction with one or more transactional memory operations comprises inserting atomic memory transaction blocks around the non-transactional memory operation.

12. The method of claim 1, wherein the one or more transactional memory operations log an access by the non-transactional memory operation to the object.

13. A computer system for providing strong atomicity for software containing memory operations outside of transactional memory atomic blocks, the computer system comprising:

at least one processing unit and memory; and

a compiler comprising an optimization module configured to;

during compilation of the software comprising the transactional memory atomic blocks comprising software transactional memory operations;

identify non-transactional memory operations outside of atomic blocks in the software by;

performing a type analysis on transactional memory atomic blocks to determine fields accessible by transactional memory operations during execution of the software;

identifying non-transactional memory operations which access fields that are accessible by transactional memory operations;

and

insert transactional memory operations into the software creating new atomic blocks in the software comprising the identified non-transactional memory operations which prevent runtime conflicts with the non-transactional memory operations of the new atomic blocks in the software.

14. The system of claim 13, wherein the optimization module is configured to insert transactional memory operations by:

before a non-transactional read memory operation configured to read an object, inserting a transactional memory operation which verifies that no transactional memory operation is updating the object;

after the non-transactional read memory operation, inserting a transactional memory operation which verifies if the object has been updated since before the read operation, and which causes the process to repeat if an update has occurred.

15. The system of claim 13, wherein the optimization module is configured to insert transactional memory operations by:

before a non-transactional write memory operation configured to write to an object, inserting a transactional memory operation which obtains a software transactional memory word for the object;

after the non-transactional write memory operation, inserting a transactional memory operation which performs a write commit for the object, and updates the version number of the object.

16. One or more computer-readable storage media containing instructions which, when executed by a computer, cause the computer to perform a method for preventing conflicts in a transactional memory system, the method comprising:

during compilation of software comprising transactional memory blocks comprising atomic blocks of source code comprising software transactional memory instructions;

analyzing the software to locate non-transactional memory instructions which are performed outside of the transactional memory blocks comprising atomic blocks of source code, wherein the analyzing comprises;

performing a type analysis on the transactional memory blocks to determine fields accessible by transactional memory instructions during execution of the software;

identifying non-transactional memory instructions which access fields that are determined accessible by the transactional memory instructions;

inserting software transactional memory instructions into the software creating new atomic blocks of code comprising the located non-transactional memory instructions, the new atomic blocks of code preventing conflicts between transactional memory accesses to an object and accesses to the object by the located non-transactional memory instructions of the new atomic blocks of code; and

wherein the inserting software transactional memory instructions into the software creating the new atomic blocks of code comprises for a non-transactional update instruction which updates the object;

inserting an open for update instruction before the non-transactional update instruction which updates a software transaction memory word for the object that indicates to memory transactions that the object is being updated; and

inserting an update commit instruction after the update instruction which confirms committing the update instruction and which updates the software transaction memory word for the object with a version number to indicate that it has been updated; and

wherein the software transactional memory word for the object at least indicates whether the object is open for update by a transaction.

17. The computer-readable storage media of claim 16, wherein inserting software transactional memory instructions further comprises for a non-transactional read instruction which reads an object:

inserting a open for read instruction before the read instruction which records the state of the object before the read; and

inserting a read check instruction after the read instruction which confirms that the state of the object does not indicate a conflicting memory operation on the object since the open for read instruction, and which allows the software to proceed if the no such conflicting memory operation is indicated.