Fast path for grace-period detection for read-copy update system

• US 8,706,706 B2
• Filed: 09/13/2007
• Issued: 04/22/2014
• Est. Priority Date: 09/13/2007
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: McKenney, Paul E.
• Primary Examiner(s): CHEMPAKASERIL, ANN J
• Application Number:
  US11/854,840
• Publication Number:
  US 20090077080A1
• Time in Patent Office: 2,413 Days
• Field of Search: 707/8
• US Class Current: 707/704
• CPC Class Codes: G06F 16/2329 using versioning
• CPC Class Codes: G06F 16/273 Asynchronous replication or reconciliation
• CPC Class Codes: G06F 2209/523 Mode
• CPC Class Codes: G06F 9/52 Program synchronisation; Mutual exclusion, e.g. by means of semaphores
• CPC Class Codes: G06F 9/526 Mutual exclusion algorithms

Abstract

A technique for implementing fast path grace period detection for deferring the destruction of a shared data element until pre-existing references to the data element are removed. A check is made, without using locks to exclude other updaters, for the presence of readers that are accessing the shared data elements. Grace period detection is terminated to initiate deferred destruction of the data element if there are no readers accessing the shared data element. If there are readers accessing the shared data element, a lock is implemented and another check is made for the presence of the readers.

Claims

1. A method for fast path detection by an updater of a grace period for deferring the destruction of a shared data element by said updater until pre-existing references to said shared data element are removed, comprising:

checking for the presence of readers that are accessing said shared data element without using locks to exclude other updaters;

terminating grace period detection to initiate deferred destruction of said data element if there are no readers accessing said shared data element;

if there are readers accessing said shared data element, implementing a lock and checking again for the presence of said readers;

wherein said checking comprises consulting a pair of counters that readers manipulate when accessing said shared data element;

wherein said checking comprises summing said counters.

2. A method in accordance with claim 1 wherein said checking comprises performing two counter summations.

3. A method in accordance with claim 2 wherein said checking comprises implementing a memory barrier between said summations.

4. A method in accordance with claim 2 wherein said checking comprises performing a first summation of said counters, implementing a memory barrier if the result of said first counter summation is a value indicating the absence of readers accessing said shared data element, performing a second summation of said counters, and terminating grace period detection if the result of each of said first counter summation and said second counter summation is a value indicating the absence of readers accessing said shared data element.

5. A method in accordance with claim 4 wherein one of said counters has a bias value indicating that said counter is a current counter and said value indicating the absence of readers accessing said shared data element is any value that is less than or equal to said bias value.

6. A data processing system having one or more processors, a memory and a communication pathway between the one or more processors and the memory, said system being adapted to perform fast path detection by an updater of a grace period for deferring the destruction of a shared data element by said updater until pre-existing references to said shared data element are removed, comprising:

a grace period detection component adapted to check for the presence of readers that are accessing said shared data element without using locks to exclude other updaters;

terminating grace period detection to initiate deferred destruction of said data element if there are no readers accessing said shared data element;

if there are readers accessing said shared data element, implementing a lock and checking again for the presence of said readers;

wherein said check comprises consulting a pair of counters that readers manipulate when accessing said shared data 3 element;

wherein said check comprises summing said counters.

7. A system in accordance with claim 6 wherein said check comprises performing two counter summations.

8. A system in accordance with claim 7 wherein said check comprises implementing a memory barrier between said summations.

9. A system in accordance with claim 7 wherein said check comprises performing a first summation of said counters, implementing a memory barrier if the result of said first counter summation is a value indicating the absence of readers accessing said shared data element, performing a second summation of said counters, and terminating grace period detection if the result of each of said first counter summation and said second counter summation is a value indicating the absence of readers accessing said shared data element.

10. A computer program product, comprising:

one or more non-transitory machine-useable media;

logic provided by said one or more media for programming a data processing platform to perform fast path detection by an updater of a grace period for deferring the destruction of a shared data element by said updater until pre-existing references to said shared data element are removed, as by;

checking for the presence of readers that are accessing said shared data element without using locks to exclude other updaters;

terminating grace period detection to initiate deferred destruction of said data element;

if there are no readers accessing said shared data element;

if there are readers accessing said shared data element, implementing a lock and checking again for the presence of said readers;

wherein said checking comprises consulting a pair of counters that readers manipulate when accessing said shared data element;

wherein said checking comprises summing said counters.

11. A computer program product in accordance with claim 10 wherein said check comprises performing two counter summations.

12. A computer program product in accordance with claim 11 wherein said checking comprises implementing a memory barrier between said summations.

13. A computer program product in accordance with claim 11 wherein said checking comprises performing a first summation of said counters, implementing a memory barrier if the result of said first counter summation is a value indicating the absence of readers accessing said shared data element, performing a second summation of said counters, and terminating grace period detection if the result of each of said first counter summation and said second counter summation is a value indicating the absence of readers accessing said shared data element.

14. A computer program product in accordance with claim 13 wherein one of said counters has a bias value indicating that said counter is a current counter and said value indicating the absence of readers accessing said shared data element is any value that is less than or equal to said bias value.