Cache metadata for implementing bounded transactional memory

• US 8,813,052 B2
• Filed: 06/08/2007
• Issued: 08/19/2014
• Est. Priority Date: 12/07/2005
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Gray, Jan, Harris, Timothy L., Larus, James, Smith, Burton
• Primary Examiner(s): MITCHELL, JASON D
• Application Number:
  US11/811,370
• Publication Number:
  US 20070245099A1
• Time in Patent Office: 2,629 Days
• Field of Search: None
• US Class Current: 717/149
• CPC Class Codes: G06F 12/0808 with cache invalidating means G06F12/0815 takes precedence
• CPC Class Codes: G06F 12/0842 for multiprocessing or multitasking
• CPC Class Codes: G06F 2212/1016 Performance improvement
• CPC Class Codes: G06F 2212/466 Metadata, control data
• CPC Class Codes: G06F 2212/507 using speculative control
• 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/30087 Synchronisation or serialisation instructions
• CPC Class Codes: G06F 9/3834 Maintaining memory consistency
• CPC Class Codes: G06F 9/38585 with result invalidation, e.g. nullification
• CPC Class Codes: G06F 9/467 Transactional memory G06F9/528 takes precedence

Abstract

Various technologies and techniques are disclosed for providing a bounded transactional memory application that accesses cache metadata in a cache of a central processing unit. When performing a transactional read from the bounded transactional memory application, a cache line metadata transaction-read bit is set. When performing a transactional write from the bounded transactional memory application, a cache line metadata transaction-write bit is set and a conditional store is performed. At commit time, if any lines marked with the transaction-read bit or the transaction-write bit were evicted or invalidated, all speculatively written lines are discarded. The application can also interrogate a cache line metadata eviction summary to determine whether a transaction is doomed and then take an appropriate action.

Claims

1. A method for improving operations of a bounded transactional memory system using cache metadata in a cache of a central processing unit comprising the operations of:

providing a bounded transactional memory application with access to cache metadata in a cache of a central processing unit;

for every transactional read, setting a cache line metadata transaction-read bit;

for respective transactional writes, setting a cache line metadata transaction-write bit that designates a speculative write;

testing for evictions or invalidations of lines marked with the cache line metadata transaction-read bit or the cache line metadata transaction-write bit, the testing performed by determining if an eviction summary register is non-zero, the eviction summary register including state corresponding to each cache line, the state corresponding to a respective cache line propagated to the eviction summary register from the cache line metadata when the respective cache line is evicted or invalidated;

by the testing, finding that one or more of the lines marked with the cache line metadata transaction-read bit or the cache line metadata transaction-write bit were evicted or invalidated; and

at commit time, based on the finding that one or more of the lines marked with the cache line metadata transaction-read bit or the cache line metadata transaction-write bit were evicted or invalidated, discarding speculatively written lines and calling a cache metadata invalidate instruction to reset all cache line metadata and the eviction summary register to zero, wherein the discarding the speculatively written lines comprises invalidating the speculatively written lines, the speculatively written lines comprising the lines marked with the cache line metadata transaction-write bit.

2. The method of claim 1, wherein the cache metadata invalidate instruction is part of an instruction set architecture on the central processing unit.

3. A method for handling a doomed transaction, using cache metadata in a cache of a central processing unit (CPU) comprising the steps operations of:

providing a bounded transactional memory application with access to cache metadata in a cache of a central processing unit;

configuring the CPU to transfer control to a software eviction handler in response to an eviction summary register being updated when a cache line of the doomed transaction is evicted or invalidated prior to a commit attempt of the doomed transaction, the cache line marked with a transaction read bit or a transaction write bit in cache metadata corresponding to the cache line, the eviction summary register including state corresponding to each cache line, the state corresponding to cache metadata of a respective cache line propagated to the eviction summary register when the respective cache line is evicted or invalidated; and

using the software eviction handler to discard speculatively written lines of the doomed transaction, wherein the discarding the speculatively written lines comprises invalidating the speculatively written lines, the speculatively written lines comprising one or more lines marked with the cache metadata transaction-write bit.

4. The method of claim 3 further comprising, executing a cache metadata flash clear instruction.

5. The method of claim 4 further comprising calling a cache metadata invalidate instruction, wherein the cache metadata invalidate instruction is part of an instruction set architecture on the central processing unit.

6. The method of claim 3, wherein configuring the CPU to transfer control to the software eviction handler comprises setting an eviction handler mask register.

7. The method of claim 6 further comprising, clearing the eviction handler mask register when the software eviction handler is invoked.

8. A computer system comprising:

a central processing unit (CPU);

a cache connected to the CPU, the cache including a plurality of cache lines, and cache metadata corresponding to each cache line;

an eviction summary register including state corresponding to each cache line, the state corresponding to a respective cache line propagated to the eviction summary register form the cache line metadata when the respective cache line is evicted or invalidated; and

a non-volatile computer-readable storage medium storing computer-executable instructions for causing the CPU to perform operations for handling a doomed transaction, the operations comprising;

providing a bounded transactional memory application with access to the cache metadata;

configuring the CPU to transfer control to a software eviction handler in response to the eviction summary register being updated when a cache line of the doomed transaction is evicted or invalidated prior to a commit attempt of the doomed transaction, the cache line marked with a transaction read bit or a transaction write bit in the cache metadata corresponding to the respective cache line; and

using the software eviction handler to discard speculatively written lines of the doomed transaction by invalidating the speculatively written lines, the speculatively written lines marked with the cache metadata transaction-write bit.

9. The computer system of claim 8, wherein configuring the CPU to transfer control to the software eviction handler comprises setting an eviction handler mask register.

10. The computer system of claim 8, the operations further comprising clearing the eviction handler mask register when the software eviction handler is invoked.

11. The computer system of claim 8, the operations further comprising, executing a cache metadata flash clear instruction.

12. The computer system of claim 11, the operations further comprising calling a cache metadata invalidate instruction, wherein the cache metadata invalidate instruction is part of an instruction set architecture on the central processing unit.