Efficient support of consistent cyclic search with read-copy update and parallel updates

• US 7,953,778 B2
• Filed: 05/20/2008
• Issued: 05/31/2011
• Est. Priority Date: 05/20/2008
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Walpole, Jonathan, McKenney, Paul E.
• Primary Examiner(s): AL HASHEMI, SANA A
• Application Number:
  US12/123,496
• Publication Number:
  US 20090292705A1
• Time in Patent Office: 1,106 Days
• Field of Search: 707/791, 707/795, 707/802, 707/807, 707/823, 707/955
• US Class Current: N/A
• CPC Class Codes: G06F 16/2329 using versioning
• CPC Class Codes: Y10S 707/955 Object-oriented

Abstract

A method, system and computer program product for supporting concurrent updates to 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. Two or more updaters may be invoked to generate new group data elements. Each new data element created by the same updater is assigned a new generation number that is different than a global generation number associated with the data element group and which allows a reader of the data element group to determine whether the new data element is a correct version for the reader. The new generation numbers are different for each updater and assigned according to an order in which the updaters respectively begin update operations. The global generation number is updated so that when all of the updaters have completed data element update processing, the global generation number will correspond to the new generation number that is associated with the last of the updaters to begin update operations.

Claims

1. A method for supporting concurrent updates to 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:

invoking two or more concurrent updaters to generate new group data elements;

assigning each new data element created by the same 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;

said new generation numbers being different for each updater and being assigned according to an order in which said updaters respectively begin update operations;

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 the last of said updaters to begin update operations; 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.

2. The method of claim 1, wherein said updating of said global generation number takes into account said updaters completing said data element update processing in a different order than said updaters begin update operations.

3. The method of claim 1, wherein said updating of said global generation number is performed in one or more stages as groups of one or more of said updaters complete said data element update processing.

4. The method of claim 3, wherein each global generation number update stage produces a global generation number that corresponds to one of said new generation numbers that is the last of a consecutive sequence of one or more new generation numbers associated with updaters that have completed said data element update processing, and wherein the first element of said sequence represents the only possible next global generation number.

5. The method of claim 1, wherein:

said updaters cooperatively assign themselves said new generation numbers by maintaining a global update sequencing number that is incremented by each updater as it commences update operations and assigns itself said new generation number;

an updater updates said global generation number if said new generation number for said updater'"'"'s new data element represents the only possible next global generation number;

an updater adds said new generation number for said updater'"'"'s new data element to a set of stored new generation numbers if said updater'"'"'s new generation number does not represent the only possible next global generation number; and

an updater updates said global generation number if said set of new generation numbers contains a sequence of new generation numbers that begins with the only possible next global generation number, in which case the last new generation number of said sequence is assigned to be said global generation number and said sequence is removed from said set of new generation numbers.

6. The method of claim 1, wherein said method further includes waiting for a grace period to elapse before updating said global generation number so that readers of said data element group do not need to execute memory barrier instructions prior to reading.

7. A system for supporting concurrent updates to 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 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, comprising;

invoking two or more concurrent updaters to generate new group data elements;

assigning each new data element created by the same 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;

said new generation numbers being different for each updater and being assigned according to an order in which said updaters respectively begin update operations;

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 establish 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 the last of said updaters to begin update operations; 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.

8. The system of claim 7, wherein said updating of said global generation number takes into account said updaters completing said data element update processing in a different order than said updaters begin update operations.

9. The system of claim 7, wherein said updating of said global generation number is performed in one or more stages as groups of one or more of said updaters complete said data element update processing.

10. The system of claim 9, wherein each global generation number update stage produces a global generation number that corresponds to one of said new generation numbers that is the last of a consecutive sequence of one or more new generation numbers associated with updaters that have completed said data element update processing, and wherein the first element of said sequence represents the only possible next global generation number.

11. The system of claim 7, wherein:

said updaters cooperatively assign themselves said new generation numbers by maintaining a global update sequencing number that is incremented by each updater as it commences update operations and assigns itself said new generation number;

an updater updates said global generation number if said new generation number for said updater'"'"'s new data element represents the only possible next global generation number;

an updater adds said new generation number for said updater'"'"'s new data element to a set of stored new generation numbers if said updater'"'"'s new generation number does not represent the only possible next global generation number; and

an updater updates said global generation number if said set of new generation numbers contains a sequence of new generation numbers that begins with the only possible next global generation number, in which case the last new generation number of said sequence is assigned to be said global generation number and said sequence is removed from said set of new generation numbers.

12. The system of claim 7, wherein said method further includes waiting for a grace period to elapse before updating said global generation number so that readers of said data element group do not need to execute memory barrier instructions prior to reading.

13. A computer program product, comprising:

one or more machine-useable media;

logic provided by said one or more media for programming a data processing platform to support concurrent updates to 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, as by;

invoking two or more concurrent updaters to generate new group data elements;

assigning each new data element created by the same 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;

said new generation numbers being different for each updater and being assigned according to an order in which said updaters respectively begin update operations;

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 the last of said updaters to begin update operations; 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.

14. The computer program product of claim 13, wherein said updating of said global generation number takes into account said updaters completing said data element update processing in a different order than said updaters begin update operations.

15. The computer program product of claim 13, wherein said updating of said global generation number is performed in one or more stages as groups of one or more of said updaters complete said data element update processing.

16. The computer program product of claim 15, wherein each global generation number update stage produces a global generation number that corresponds to one of said new generation numbers that is the last of a consecutive sequence of one or more new generation numbers associated with updaters that have completed said data element update processing, and wherein the first element of said sequence represents the only possible next global generation number.

17. The computer program product of claim 13, wherein:

said updaters cooperatively assign themselves said new generation numbers by maintaining a global update sequencing number that is incremented by each updater as it commences update operations and assigns itself said new generation number;

an updater updates said global generation number if said new generation number for said updater'"'"'s new data element represents the only possible next global generation number;

an updater adds said new generation number for said updater'"'"'s new data element to a set of stored new generation numbers if said updater'"'"'s new generation number does not represent the only possible next global generation number; and

an updater updates said global generation number if said set of new generation numbers contains a sequence of new generation numbers that begins with the only possible next global generation number, in which case the last new generation number of said sequence is assigned to be said global generation number and said sequence is removed from said set of new generation numbers.

18. The computer program product of claim 13, wherein said method further includes waiting for a grace period to elapse before updating said global generation number so that readers of said data element group do not need to execute memory barrier instructions prior to reading.

19. A method for supporting concurrent updates to 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:

invoking two or more concurrent updaters to generate new group data elements;

assigning each new data element created by the same 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;

said new generation numbers being different for each updater and being assigned according to an order in which said updaters respectively begin update operations;

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 the last of said updaters to begin update operations;

said updating of said global generation number being performed using a data structure that tracks updaters that have completed said data element update operations out-of-order;

said updating of said global generation number being further performed by setting said global generation number one or more times to correspond to the largest of a sequence of said new generation numbers that are represented by value or by position in said data structure, and which sequence begins with a new generation number that is the only possible next global generation number; 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.

20. The method of claim 19, wherein said updating of said global generation number is performed in a manner that allows readers of said data element group to search using a snapshot of said global generation number without implementing a memory barrier to ensure that said global generation number is valid.