Performance Of RCU-Based Searches And Updates Of Cyclic Data Structures

• US 20140108366A1
• Filed: 02/22/2013
• Published: 04/17/2014
• Est. Priority Date: 10/16/2012
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: McKenney, Paul E.
• Granted Patent: US 9,081,803 B2
• Time in Patent Office: Days
• US Class Current: 707/695
• CPC Class Codes: G06F 16/1873 Versioning file systems, temporal file systems, e.g. file system supporting different historic versions of files
• CPC Class Codes: G06F 16/20 of structured data, e.g. relational data
• CPC Class Codes: G06F 16/2308 Concurrency control transaction processing G06F9/466
• CPC Class Codes: G06F 9/4881 Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues

Abstract

A technique for improving the performance of RCU-based searches and updates to a shared data element group where readers must see consistent data with respect to the group as a whole. An updater creates one or more new group data elements and assigns each element a new generation number that is different than a global generation number associated with the data element group, allowing readers to track update versions. The updater links the new data elements into the data element group and then updates the global generation number so that referential integrity is maintained. This is done using a generation number element that is referenced by a header pointer for the data element group, and which in turn references or forms part of one of the data elements. After a grace period has elapsed, the any prior version of the generation number element may be freed.

Claims

1. A method for improving the performance of RCU-based searches and updates to a shared data element group where readers must see consistent data with respect to the group as a whole, comprising:

invoking an updater to generate one or more new group data elements;

assigning each new data element created by the updater a new generation number that is different than a global generation number associated with said data element group and which allows a reader of said data element group to determine whether said new data element is a correct version for said reader;

performing data element update processing by;

respectively establishing a first version link that links each of said new data elements to a prior version thereof having a different generation number;

respectively establishing a second version link that links each of said new data elements from its prior version; and

respectively establishing group links that link said new data elements into said data element group so that said new data elements are reachable by readers;

updating said global generation number associated with said data element group so that when all of said updaters have completed said data element update processing, said global generation number will correspond to said new generation number that is associated with said updater;

said global generation number being updated using a generation number element that is referenced by a header pointer for said data element group and which in turn references or forms part of one of said data elements; and

respectively freeing said prior version, said first version link, and said second version link for each of said new data elements following a grace period, together with any prior version of said generation number element.

2. The method of claim 1, wherein said generation number element comprises a pointer that references one of said data elements and whose address comprises said global generation number.

3. The method of claim 2, wherein said generation number element is allocated from a contiguous array of generation number elements.

4. The method of claim 1, wherein said generation number element comprises a data structure whose fields include a pointer that references one of said data elements and a variable storing said global generation number.

5. The method of claim 1, wherein said generation number element comprises one of said data elements implemented as a data structure whose fields include a variable storing said global generation number.

6. The method of claim 1, wherein said generation number element comprises a pointer-forwarding entity implemented as a data structure whose fields include a pointer reference to one of said data elements and a variable storing said global generation number.

7. The method of claim 1, wherein said updater executes a memory barrier instruction after establishing said first version link, said second version link and said group links, and prior to updating said global generation number.

8-21. -21. (canceled)