Facilitating stack read and write operations in a software transactional memory system

• US 7,895,582 B2
• Filed: 08/04/2006
• Issued: 02/22/2011
• Est. Priority Date: 08/04/2006
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Duffy, John Joseph, Graefe, Goetz, Detlefs, David, Magruder, Michael M.
• Primary Examiner(s): Khatri; Anil
• Application Number:
  US11/499,012
• Publication Number:
  US 20080127150A1
• Time in Patent Office: 1,663 Days
• Field of Search: 717139-148, 717150-154
• US Class Current: 717/140
• CPC Class Codes: G06F 8/443 Optimisation
• CPC Class Codes: G06F 9/466 Transaction processing

Abstract

Various technologies and techniques facilitate stack read and write operations in a software transactional memory system. If the compiler determines that an address for a variable in a code segment is a stack location, the stack location is live on entry, and the address of the variable has not been taken and passed to another thread, the code is changed to ensure failure atomicity. One example includes modifying the code so a shadow copy is saved for local variables that are live on entry. If the same prior criteria are true except the stack location is not live on entry, the code is optimized by ensuring code for logging and software transactional memory operations are not included. If the compiler does not know the address is the stack location or that the address is not passed to another thread, the code is changed to ensure failure and concurrency atomicity.

Claims

1. A method for facilitating operation of a software transactional memory system with stack locations comprising the steps of:

providing a software transactional memory system, the software transactional memory system interacting with a compiler; and

if the compiler determines at compile time that a particular address for a variable in an original code segment is a stack location, that the stack location is live on entry to a current transaction scope, and that the particular address of the variable has not been taken and passed to another thread, then making a change to the original code segment, using a processing unit, in a manner that ensures failure atomicity to provide a changed original code segment;

wherein the change comprises modifying the original code segment so that a shadow copy is saved for each local variable that is live on entry to the current transaction scope.

2. The method of claim 1, wherein the change further comprises adding a call to a function that logs a prior value of the variable.

3. The method of claim 2, wherein the call to the function that logs the prior value of the variable ensures that if a transaction rolls back, the prior value of the variable can be retrieved and restored.

4. The method of claim 3, wherein the change further comprises adding a transaction stack base operation upon entry into the current transaction scope and prior to the function that logs the prior value, the transaction stack base operation being operable to log a stack pointer value.

5. The method of claim 1, wherein the change further comprises modifying the original code segment so that if a transaction subsequently aborts, the shadow copy of each local variable is copied back to the stack location.

6. The method of claim 5, wherein by using the shadow copy of each local variable to ensure failure atomicity, any involvement with the software transactional memory system is avoided at runtime.

7. A computer-readable storage medium having computer-executable instructions for causing a computer to perform the steps recited in claim 1.

8. A method for facilitating operation of a software transactional memory system with stack locations comprising the steps of:

providing a software transactional memory system, the software transactional memory system interacting with a compiler; and

if the compiler determines at compile time that a particular address for a variable in an original code segment is a stack location, that the stack location is live on entry to a current transaction scope, and that the particular address of the variable has not been taken and passed to another thread, then making a change to the original code segment, using a processing unit, in a manner that ensures failure atomicity to provide a changed original code segment;

wherein the compiler determines based upon at least one factor whether to use a first approach or a second approach for ensuring failure atomicity for the current transaction scope, the first approach comprising changing the original code segment by adding a call to a function that logs a prior value of the variable, and the second approach comprising changing the original code segment so that a shadow copy is saved for each local variable that is live on entry to the current transaction scope.

9. A computer-readable storage medium having computer-executable instructions for causing a computer to perform the steps recited in claim 8.

10. The method of claim 8, wherein the call to the function that logs the prior value of the variable ensures that if a transaction rolls back, the prior value of the variable can be retrieved and restored.

11. A computer-readable storage medium having computer-executable instructions for causing a computer to perform steps comprising:

if a compiler determines that a particular address for a variable in an original code segment is a stack location, that the stack location is live on entry to a current transaction scope, and that the particular address of the variable has not been taken and passed to another thread, then make a first type of change to an original code segment to provide a changed original code segment, the first type of change being made in a manner that ensures failure atomicity;

if the compiler determines that a particular address for the variable in the original code segment is the stack location, that the stack location is not live on entry to the current transaction scope, and that the particular address of the variable has not been taken and passed to another thread, then make a second type of change to the original code segment to provide a changed original code segment, the second type of change being made in a manner that is optimized by ensuring that code for logging of a prior value of the variable is not included and that code for calling a software transactional memory operation is not included; and

if the compiler does not know whether or not the particular address for the variable is the stack location or if the compiler does not know if the particular address is passed to another thread, then make a third type of change to the original code segment to provide a changed original code segment, the third type of change being made in a manner that ensures both failure atomicity and concurrency atomicity.

12. The computer-readable storage medium of claim 11, wherein the first type of change comprises adding a call to a function that logs a prior value of the variable that can be retrieved and restored if a rollback is necessary.

13. The computer-readable storage medium of claim 12, wherein the first type of change further comprises adding a call to a transaction stack base procedure upon entry into the current transaction scope and prior to the function that logs the prior value, the call to the transaction stack base procedure being operable to log a stack pointer value.

14. The computer-readable storage medium of claim 11, wherein the second type of change comprises modifying the original code segment so that a shadow copy is saved for each local variable that is live on entry to the current transaction scope.

15. The computer readable storage medium of claim 14, wherein the second type of change further comprises modifying the original code segment so that if the current transaction subsequently aborts, the shadow copy of each local variable is copied back to the stack location.

16. The computer readable storage medium of claim 15, wherein by using the shadow copy of each local variable to ensure failure atomicity, any involvement with a software transactional memory system is avoided at runtime.

17. A method for rolling back a transaction in a software transactional memory system comprising the steps of:

determining that a rollback is necessary;

traversing a log backwards;

determining that a particular field value to be restored is a local variable;

if a stack address of the local variable is greater than a saved stack base that was saved during a call to a transaction stack base procedure, restoring the value using a processing unit to provide a restored field value in response to the stack address of the local variable being greater than the saved stack base; and

if the stack address of the local variable is less than the saved stack base, not restoring the value in response to the stack address of the local variable being less than the saved stack base.

18. The method of claim 17, wherein the value is not restored since data was logged for the local variable that has gone out of scope.

19. The method of claim 18, wherein the data was logged in a called method.

20. A computer-readable storage medium having computer-executable instructions for causing a computer to perform the steps recited in claim 17.