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 generation number to said new data element that allows a reader of said data element group to determine whether said new data element is a correct version for said reader;
if a prior version of said new data element exists, establishing a version link between said new data element and said prior version;
linking said new data element into said data element group so that it is reachable by readers;
updating a global generation number associated with said data element group; and
if a prior version of said new data element exists, freeing said prior version following a grace period.
2 Assignments
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.
-
Citations
31 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 generation number to said new data element that allows a reader of said data element group to determine whether said new data element is a correct version for said reader;
if a prior version of said new data element exists, establishing a version link between said new data element and said prior version;
linking said new data element into said data element group so that it is reachable by readers;
updating a global generation number associated with said data element group; and
if a prior version of said new data element exists, freeing said prior version following a grace period. - View Dependent Claims (2, 3, 4, 5, 7, 8, 9, 10, 27, 28, 29, 30)
-
-
6. 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 generation number to said pointer-forwarding entity that allows a reader of said data element group to determine whether said pointer-forwarding entity is a correct version for said reader;
if there is a prior version of said pointer-forwarding entity, establishing a version link between said pointer-forwarding entity and said prior version;
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 a global generation number associated with said data element group; and
if a prior version of said pointer-forwarding entity exists, freeing said prior version following a grace period.
-
-
11. A data processing system having one or more central processing units, a memory and a communication pathway between the one or more central processing units and the memory, said system being adapted to update a shared data element group in said memory while preserving group integrity on behalf of one or more readers that are concurrently referencing group data elements without using locks or atomic instructions, and comprising:
-
means for generating a new group data element;
means for assigning a generation number to said new data element that allows a reader of said data element group to determine whether said new data element is a correct version for said reader;
means for establishing, if a prior version of said new data element exists, a version link between said new data element and said prior version;
means for linking said new data element into said data element group so that it is reachable by readers;
means for updating a global generation number associated with said data element group; and
means for freeing, if a prior version of said new data element exists, said prior version following a grace period. - View Dependent Claims (12, 13, 14, 15, 17, 18, 19, 20)
-
-
16. A data processing system having one or more central processing units, a memory and a communication pathway between the one or more central processing units and the memory, said system being adapted to update a shared data element group in said memory while preserving group integrity on behalf of one or more readers that are concurrently referencing group data elements without using locks or atomic instructions, and comprising:
-
means for generating a pointer-forwarding entity that points to a data element in said data element group;
means for assigning a generation number to said pointer-forwarding entity that allows a reader of said data element group to determine whether said pointer-forwarding entity is a correct version for said reader;
means for establishing, if there is a prior version of said pointer-forwarding entity, a version link between said pointer-forwarding entity and said prior version;
means for 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;
means for updating a global generation number associated with said data element group; and
means for freeing, if a prior version of said pointer-forwarding entity exists, said prior version following a grace period.
-
-
21. A computer program product 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:
-
one or more data storage media;
means recorded on said data storage media for programming a data processing platform to operate as by;
generating a new group data element;
assigning a generation number to said new data element that allows a reader of said data element group to determine whether said new data element is a correct version for said reader;
if a prior version of said new data element exists, establishing a version link between said new data element and said prior version;
linking said new data element into said data element group so that it is reachable by readers;
updating a global generation number associated with said data element group; and
if a prior version of said new data element exists, freeing said prior version following a grace period. - View Dependent Claims (22, 23, 24, 25)
-
-
26. A computer program product 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:
-
one or more data storage media;
means recorded on said data storage media for programming a data processing platform to operate as by;
generating a pointer-forwarding entity that points to a data element in said data element group;
assigning a generation number to said pointer-forwarding entity that allows a reader of said data element group to determine whether said pointer-forwarding entity is valid for said reader;
if there is a prior version of said pointer-forwarding entity, establishing a version link between said pointer-forwarding entity and said prior version;
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 a global generation number associated with said data element group; and
if a prior version of said pointer-forwarding entity exists, freeing said prior version following a grace period.
-
-
31. A computer program product for managing a shared data element group so as to allow updates thereof 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:
-
one or more data storage media;
means recorded on said data storage media for programming a data processing platform to operate as by;
performing a first-phase update operation that preserves a consistent pre-update view of said data element group on behalf of pre-update readers and a consistent post-update view of the data element group on behalf of post-update readers;
providing means by which readers can locate all data elements of said data element group that belong to each of said pre-update and post-update views as readers search said data element group;
performing one or more read operations following said first-phase update operation in which one or more readers search said data element group with each reader referencing only data elements belonging to one of said pre-update and post-update views; and
performing a second-phase update operation following a grace period that frees said pre-update view of said data element group.
-
Specification