Realtime-safe read copy update with lock-free readers

• US 20070083565A1
• Filed: 10/12/2005
• Published: 04/12/2007
• Est. Priority Date: 10/12/2005
• Status: Active Grant

• Current Assignee: Meta Platforms, Inc. (f/k/a Facebook, Inc.)
• Original Assignee: International Business Machines Corporation
• Inventors: McKenney, Paul
• Granted Patent: US 7,395,263 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/2329 using versioning
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99938 Concurrency, e.g. lock management in shared database
• CPC Class Codes: Y10S 707/99952 Coherency, e.g. same view to multiple users
• CPC Class Codes: Y10S 707/99953 Recoverability

Abstract

A technique for realtime-safe detection of a grace period for deferring the destruction of a shared data element until pre-existing references to the data element have been removed. A pair of counters is established for each of one or more processors. A global counter selector determines which counter of each per-processor counter pair is a current counter. When reading a shared data element at a processor, the processor'"'"'s current counter is incremented. Following counter incrementation, the processor'"'"'s counter pair is tested for reversal to ensure that the incremented counter is still the current counter. If a counter reversal has occurred, such that the incremented counter is no longer current, the processor'"'"'s other counter is incremented. Following referencing of the shared data element, any counter that remains incremented is decremented. Following an update to the shared data element wherein a pre-update version of the element is maintained, the global counter selector is switched to establish a new current counter of each per-processor counter pair. The non-current counter of each per-processor counter pair is tested for zero. The shared data element'"'"'s pre-update version is destroyed upon the non-current counter of each per-processor counter pair being zero.

Claims

1. A method for realtime-safe detection of a grace period for deferring the destruction of a shared data element until pre-existing references to the data element are removed, comprising:

establishing a pair of counters for each of one or more processors;

establishing a global counter selector that determines which counter of each per-processor counter pair is a current counter;

when reading a shared data element at a processor;

incrementing the current counter of said processor'"'"'s counter pair that corresponds to said global counter selector;

testing for reversal of said processor'"'"'s counter pair to ensure that the incremented counter is still the current counter corresponding to said global counter selector;

if a counter pair reversal has occurred such that said incremented counter has become the non-current counter, incrementing the other counter of said processor'"'"'s counter pair that has become the current counter;

referencing said shared data element; and

decrementing whichever counter of said processor'"'"'s counter pair remains incremented.

2. A method in accordance with claim 1 further including:

updating said shared data element in a manner that preserves a pre-update version of said data element;

switching said global counter selector to establish a new current counter of each per-processor counter pair;

testing the non-current counter of each per-processor counter pair for zero; and

destroying said shared data element'"'"'s pre-update version upon the non-current counter of each per-processor counter pair being zero.

3. A method in accordance with claim 1 wherein said reading includes maintaining both counters of said processor'"'"'s counter pair in an incremented state until referencing of said shared data element has completed in the event that a counter pair reversal has occurred.

4. A method in accordance with claim 1 wherein said reading includes decrementing said non-current counter prior to referencing said shared data element in the event that a counter pair reversal has occurred.

5. A method in accordance with claim 1 wherein no counter incrementation is performed in the event that said reading is a recursive read operation.

6. A method in accordance with claim 1 wherein said counters are implemented as per-processor data structures and said global counter selector is implemented as a Boolean value.

7. A method in accordance with claim 1 wherein said reading is performed by an executable task having an associated task structure, and wherein said task structure maintains a pointer to one or both counters of said processor'"'"'s counter pair until said counter decrementation has occurred.

8. 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 perform realtime-safe grace detection of a grace period for deferring removal of a shared data element until pre-existing references to the data element are removed, and comprising:

a pair of counters for each of said one or more processors;

a global counter selector that determines which counter of each per-processor counter pair is a current counter;

a reader adapted to read a shared data element at a processor;

a counter incrementer adapted to;

increment the current counter of said processor'"'"'s counter pair that corresponds to said global counter selector;

test for reversal of said processor'"'"'s counter pair to ensure that the incremented counter is still the current counter corresponding to said global counter selector; and

responsive to said counter pair reversal occurring such said incremented counter has become the non-current counter, incrementing the other counter of said processor'"'"'s counter pair that has become the current counter;

a data referencer adapted to reference said shared data element; and

a counter decrementer adapted to decrement whichever counter of said processor'"'"'s counter pair remains incremented.

9. A system in accordance with claim 8 further including a subsystem adapted to process the destruction of a pre-update version of said shared data element following updating thereof in a manner that preserves a pre-update version of said data element, said subsystem comprising:

a counter switch adapted to switch said global counter selector to establish a new current counter of each per-processor counter pair;

a counter monitor adapted to test the non-current counter of each per-processor counter pair for zero; and

a callback processor adapted to destroy said shared data element'"'"'s pre-update version upon the non-current counter of each per-processor counter pair being zero.

10. A system in accordance with claim 9 wherein said incrementer is adapted to maintain both counters of said processor'"'"'s counter pair in an incremented state in the event that a counter pair reversal has occurred and said decrementer is adapted to decrement both counters of said processor'"'"'s counter pair following referencing said shared data element in the event that a counter pair reversal has occurred.

11. A system in accordance with claim 8 wherein said incrementer is further adapted to decrement said non-current counter in the event that a counter pair reversal has occurred.

12. A system in accordance with claim 8 wherein said incrementer is adapted to perform no counter incrementation in the event that said reading is a recursive read operation.

13. A system in accordance with claim 8 wherein said counters are implemented as per-processor data structures and said global counter selector is implemented as a Boolean value.

14. A computer program product for realtime-safe grace detection of a grace period for deferring the destruction of a shared data element until pre-existing references to the data element are removed, comprising:

one or more machine-useable media;

means provided by said one or more media for programming a data processing platform to operate as by;

establishing a pair of counters for each of one or more processors;

establishing a global counter selector that determines which counter of each per-processor counter pair is a current counter;

when reading a shared data element at a processor;

incrementing the current counter of said processor'"'"'s counter pair that corresponds to said global counter selector;

testing for reversal of said processor'"'"'s counter pair to ensure that the incremented counter is still the current counter corresponding to said global counter selector;

if a counter pair reversal has occurred such said incremented counter has become the non-current counter, incrementing the other counter of said processor'"'"'s counter pair that has become the current counter;

referencing said shared data element; and

decrementing whichever counter of said processor'"'"'s counter pair remains incremented.

15. A computer program product in accordance with claim 14 wherein said means provided by said one or more media are adapted to further program said data processing platform to operate as by:

updating said shared data element in a manner that preserves a pre-update version of the shared data element;

switching said global counter selector to establish a new current counter of each per-processor counter pair;

testing the non-current counter of each per-processor counter pair for zero; and

destroying said shared data element'"'"'s pre-update version upon the non-current counter of each per-processor counter pair being zero.

16. A computer program product in accordance with claim 15 wherein said reading includes maintaining both counters of said processor'"'"'s counter pair in an incremented state until referencing of said shared data element has completed in the event that a counter pair reversal has occurred.

17. A computer program product in accordance with claim 14 wherein said reading includes decrementing said non-current counter prior to referencing said shared data element in the event that a counter pair reversal has occurred.

18. A computer program product in accordance with claim 14 wherein no counter incrementation is performed in the event that said reading is a recursive read operation.

19. A computer program product in accordance with claim 14 wherein said counters are implemented as per-processor data structures and said global counter selector is implemented as a Boolean value.

20. A computer program product in accordance with claim 14 wherein said reading is performed by an executable task having an associated task structure, and wherein said task structure maintains a pointer to one or both counters of said processor'"'"'s counter pair until said counter decrementation has occurred.