Realtime-safe read copy update with lock-free readers

• US 7,395,263 B2
• Filed: 10/12/2005
• Issued: 07/01/2008
• 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 E.
• Primary Examiner(s): Ali; Mohammad
• Assistant Examiner(s): Smith; Brannon W
• Application Number:
  US11/248,096
• Publication Number:
  US 20070083565A1
• Time in Patent Office: 993 Days
• Field of Search: 707/8, 707/100, 707/101, 718/100
• 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;

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.

2. 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.

3. 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.

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

5. 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.

6. 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.