Performance of RCU-based searches and updates of cyclic data structures
First Claim
1. A method for improving the performance of read-copy update (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.
0 Assignments
0 Petitions
Accused Products
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.
-
Citations
21 Claims
-
1. A method for improving the performance of read-copy update (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. - View Dependent Claims (2, 3, 4, 5, 6, 7)
-
-
8. A system, comprising:
-
one or more processors; a memory coupled to said one or more processors, said memory including a computer useable medium tangibly embodying at least one program of instructions executable by said processor to perform operations for improving the performance of read-copy update (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, said operations 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. - View Dependent Claims (9, 10, 11, 12, 13, 14)
-
-
15. A computer program product, comprising:
-
one or more non-transitory machine-useable storage media; logic provided by said one or more media for improving the performance of read-copy update (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, as by; 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. - View Dependent Claims (16, 17, 18, 19, 20, 21)
-
Specification