Efficient support of consistent cyclic search with read-copy-update
First Claim
1. A method for updating a shared data element group while preserving group integrity on behalf of one or more readers that are concurrently referencing group data elements without using locks or atomic instructions, comprising:
- generating a new group data element;
assigning a new generation number to said new data element that is different than an existing 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;
establishing a first version link from said new data element to a prior version thereof having a different generation number;
establishing a second version link from said prior version to said new data element;
linking said new data element into said data element group so that it is reachable by readers;
updating said global generation number associated with said data element group to correspond to said new generation number; and
freeing said prior version and said first and second version links following a grace period.
1 Assignment
0 Petitions
Accused Products
Abstract
A method, system and computer program product for modifying data elements in a shared data element group that must be updated atomically for the benefit of readers requiring group integrity. A global generation number is associated with the data element group and each member receives a copy of this number when it is created. Each time an update is performed, the global generation number is incremented and the updated element'"'"'s copy of this number is set to the same value. For each updated data element, a link is maintained from the new version to the pre-update version thereof, either directly or using pointer-forwarding entities. When a search is initiated, the current global generation number is referenced at the commencement of the search. As data elements in the group are traversed, the reader traverses the links between new and old data element versions to find a version having a matching generation number, if any. Following the occurrence of a grace period in which all readers have passed through quiescent states, all old data element versions are freed.
56 Citations
10 Claims
-
1. A method for updating a shared data element group while preserving group integrity on behalf of one or more readers that are concurrently referencing group data elements without using locks or atomic instructions, comprising:
-
generating a new group data element; assigning a new generation number to said new data element that is different than an existing 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; establishing a first version link from said new data element to a prior version thereof having a different generation number; establishing a second version link from said prior version to said new data element; linking said new data element into said data element group so that it is reachable by readers; updating said global generation number associated with said data element group to correspond to said new generation number; and freeing said prior version and said first and second version links following a grace period. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9)
-
-
10. A method for updating a shared data element group while preserving group integrity on behalf of one or more readers that are concurrently referencing group data elements without using locks or atomic instructions, comprising:
-
generating a pointer-forwarding entity that points to a data element in said data element group; assigning a new generation number to said pointer-forwarding entity that is different than an existing global generation number associated with said data element group and which allows a reader of said data element group to determine whether said pointer-forwarding entity is a correct version for said reader; establishing a first version link from said pointer-forwarding entity to a prior version thereof; establishing a second version link from said prior version to said new data linking said pointer-forwarding entity into said data element group so that said data element pointed to by said pointer-forwarding entity is reachable by readers through said pointer-forwarding entity; updating said global generation number associated with said data element group to correspond to said new generation number; and freeing said prior version and said first and second version links following a grace period.
-
Specification