Safely rolling back transactions in a transactional memory system with concurrent readers

• US 9,459,963 B2
• Filed: 09/03/2009
• Issued: 10/04/2016
• Est. Priority Date: 09/03/2009
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: McKenney, Paul E., Triplett, Joshua A.
• Primary Examiner(s): Hutton, Nan
• Application Number:
  US12/553,160
• Publication Number:
  US 20110055630A1
• Time in Patent Office: 2,588 Days
• Field of Search: 707/813, 711/159
• US Class Current: 1/1
• CPC Class Codes: G06F 11/141 for bus or memory accesses
• CPC Class Codes: G06F 11/1482 by means of middleware or OS functionality
• CPC Class Codes: G06F 16/1847 specifically adapted to static storage, e.g. adapted to flash memory or SSD
• CPC Class Codes: G06F 9/467 Transactional memory G06F9/528 takes precedence
• CPC Class Codes: G06F 9/52 Program synchronisation; Mutual exclusion, e.g. by means of semaphores

Abstract

A technique for safely rolling back transactional memory transactions without impacting concurrent readers of the uncommitted transaction data. An updater uses a transactional memory technique to perform an data update on data that is shared with a reader. The update is implemented as a transaction in which the updated data is initially uncommitted due to the transaction being subject to roll back. The reader is allowed to perform a data read on the uncommitted data during the transaction. Upon a rollback of the transaction, reclamation of memory locations used by the uncommitted data is deferred until a grace period has elapsed after which the reader can no longer be referencing the uncommitted data.

Claims

1. In a data processing system having at least one CPU, a memory operatively coupled to said CPU, said memory including a storage medium tangibly embodying data that is subject to concurrent access by a data updater that updates said data and a data reader that reads said data, a method for safely rolling back transactions implemented by said updater to update said data using a transactional memory technique as said reader reads said updated data while said transactions are uncommitted and subject to roll back, comprising:

said updater executing on said at least one CPU to perform a data update on said data to produce updated data using a transactional memory technique wherein said data update is implemented as a transaction in which said updated data is initially uncommitted data due to said transaction being subject to roll back in the event of said transaction aborting, said uncommitted data comprising a transaction write set representing shared memory locations that are written to during said transaction;

said reader executing on said at least one CPU to perform a data read on said uncommitted data after said transaction has started and prior to said transaction either committing or aborting; and

upon an abort of said transaction, deferring reclamation of said memory locations used by said uncommitted data until a grace period has elapsed after which said reader can no longer be referencing said uncommitted data.

2. The method of claim 1, further including:

upon a commit of said transaction, deferring reclamation of memory locations used by data that has been removed by said transaction until a grace period has elapsed after which said reader can no longer be referencing said removed data.

3. The method of claim 1, wherein said deferred reclamation of said uncommitted data is performed using a transactional memory subsystem that performs said rollback using an internal deferred reclamation mechanism that is part of said transactional memory subsystem.

4. The method of claim 3, wherein said deferred reclamation of said uncommitted data is performed using a read-copy update deferred reclamation technique.

5. The method of claim 1, wherein said deferred reclamation of said uncommitted data is performed using a transactional memory subsystem that calls an external deferred reclamation mechanism that is part of a read-copy update subsystem.

6. The method of claim 1, wherein said reader is a read-copy update reader that uses read-copy update primitives to read said uncommitted data.

7. A system, comprising:

a CPU;

a memory operatively coupled to said CPU, said memory including a storage medium tangibly embodying data that is subject to concurrent access by a data updater that updates said data and a data reader that reads said data;

said memory further tangibly embodying a program of instructions executable by said CPU to perform operations for safely rolling back transactions implemented by said updater to update said data using a transactional memory technique as said reader reads said updated data while said transactions are uncommitted and subject to roll back, comprising;

said updater executing on said at least one CPU to perform a data update on said data to produce updated data using a transactional memory technique wherein said data update is implemented as a transaction in which said updated data is initially uncommitted data due to said transaction being subject to roll back in the event of said transaction aborting, said uncommitted data comprising a transaction write set representing shared memory locations that are written to during said transaction;

said reader executing on said at least one CPU to perform a data read on said uncommitted data after said transaction has started and prior to said transaction either committing or aborting; and

upon an abort of said transaction, deferring reclamation of memory locations used by said uncommitted data until a grace period has elapsed after which said reader can no longer be referencing said uncommitted data.

8. The system of claim 7, wherein said operations further include:

upon a commit of said transaction, deferring reclamation of memory locations used by data that has been removed by said transaction until a grace period has elapsed after which said reader can no longer be referencing said removed data.

9. The system of claim 7, wherein said deferred reclamation of said uncommitted data is performed using a transactional memory subsystem that performs said rollback using an internal deferred reclamation mechanism that is part of said transactional memory subsystem.

10. The system of claim 9, wherein said deferred reclamation of said uncommitted data is performed using a read-copy update deferred reclamation technique.

11. The method of claim 7, wherein said deferred reclamation of said uncommitted data is performed using a transactional memory subsystem that calls an external deferred reclamation mechanism that is part of a read-copy update subsystem.

12. The system of claim 7, wherein said reader is a read-copy update reader that uses read-copy update primitives to read said uncommitted data.

13. A computer program product, comprising:

one or more non-transitory computer-readable storage media;

program instructions stored on said one or more storage media for programming a CPU that is operatively coupled to a memory, said memory including a storage medium tangibly embodying data that is subject to concurrent access by a data updater that updates said data and a data reader that reads said data, said program instructions programming said CPU to perform operations, comprising;

said updater executing on said at least one CPU to perform a data update on said data to produce updated data using a transactional memory technique wherein said data update is implemented as a transaction in which said updated data is initially uncommitted data due to said transaction being subject to roll back in the event of said transaction aborting, said uncommitted data comprising a transaction write set representing shared memory locations that are written to during said transaction;

said reader executing on said at least one CPU to perform a data read on said uncommitted data after said transaction has started and prior to said transaction either committing or aborting; and

upon an abort of said transaction, deferring reclamation of memory locations used by said uncommitted data until a grace period has elapsed after which said reader can no longer be referencing said uncommitted data.

14. The computer program product of claim 13, wherein said operations further include:

upon a commit of said transaction, deferring reclamation of memory locations used by data that has been removed by said transaction until a grace period has elapsed after which said reader can no longer be referencing said removed data.

15. The computer program product of claim 13, wherein said deferred reclamation of said uncommitted data is performed using a transactional memory subsystem that performs said rollback using an internal deferred reclamation mechanism that is part of said transactional memory subsystem.

16. The computer program product of claim 15, wherein said deferred reclamation of said uncommitted data is performed using a read-copy update deferred reclamation technique.

17. The computer program product of claim 13, wherein said deferred reclamation of said uncommitted data is performed using a transactional memory subsystem that calls an external deferred reclamation mechanism that is part of a read-copy update subsystem.

18. The computer program product of claim 13, wherein said reader is a read-copy update reader that uses read-copy update primitives to read said uncommitted data.

19. In a data processing system having at least one CPU, a memory operatively coupled to said CPU that includes a storage medium tangibly embodying data that is subject to concurrent access by a data updater that updates said data and a data reader that reads said data, a method for safely rolling back transactions implemented by said updater to update said data using a transactional memory technique as said reader reads said updated data while said transactions are uncommitted and subject to roll back, comprising:

said updater executing on said at least one CPU to perform a data update on said data to produce updated data using a transactional memory technique wherein said data update is implemented as a transaction in which said updated data is initially uncommitted data due to said transaction being subject to roll back in the event of said transaction aborting, said uncommitted data comprising a transaction write set representing shared memory locations that are written to during said transaction;

said transactional memory technique being one of a hardware transactional memory technique or a software transactional memory technique;

said reader executing on said at least one CPU to perform a data read on said uncommitted data after said transaction has started and prior to said transaction either committing or aborting;

said reader being a read-copy update reader that uses read-copy update primitives to read said uncommitted data; and

upon an abort of said transaction, deferring reclamation of memory locations used by said uncommitted data until a grace period has elapsed after which said reader can no longer be referencing said uncommitted data; and

said deferred reclamation of memory locations used by said uncommitted data being performed using a read-copy update deferred reclamation technique.

20. The method of claim 19 wherein said deferred reclamation of said uncommitted data is performed using a transactional memory subsystem that either (1) performs said rollback using an internal read-copy update deferred reclamation mechanism that is part of said transactional memory subsystem, or (2) calls an external read-copy update deferred reclamation mechanism that is part of a read-copy update subsystem.