Optimized resizing for RCU-protected hash tables

• US 9,009,122 B2
• Filed: 12/08/2011
• Issued: 04/14/2015
• Est. Priority Date: 12/08/2011
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: McKenney, Paul E., Triplett, Joshua A.
• Primary Examiner(s): Saeed, Usmaan
• Assistant Examiner(s): VO, CECILE H
• Application Number:
  US13/314,223
• Publication Number:
  US 20130151488A1
• Time in Patent Office: 1,223 Days
• Field of Search: 707/1/1, 707/709, 707800-801, 707/798, 707/747, 707/802, 707693-695
• US Class Current: 707/695
• CPC Class Codes: G06F 16/9014 hash tables

Abstract

A technique for resizing a first RCU-protected hash table stored in a memory. A second RCU-protected hash table is allocated in the memory as a resized version of the first hash table having a different number of hash buckets, with the hash buckets being defined but initially having no hash table elements. The second hash table is populated by linking each hash bucket thereof to all hash buckets of the first hash table containing elements that hash to the second hash bucket. The second hash table is then published so that it is available for searching by hash table readers. The first table is freed from memory after waiting for a grace period which guarantees that no readers searching the first hash table will be affected by the freeing.

Claims

1. A system, comprising:

one or more processors;

a memory coupled to said one or more processors, said memory including a computer usable medium storing a first RCU [Read-Copy Update]-protected first hash table and at least one program of instructions executable by said processor to perform operations, said operations comprising;

allocating a second RCU-protected hash table in said memory, said second hash table representing a resized version of said first hash table that has a different number of hash buckets than said first hash table, said second hash table buckets being defined but initially having no hash table elements;

populating said second hash table without copying or moving any hash table elements in memory by linking each hash bucket of said second hash table to all hash buckets of said first hash table containing elements that hash to said second hash table bucket;

publishing said second hash table so that it is available for searching by hash table readers; and

freeing said first hash table from said memory after waiting for a grace period which guarantees that no readers searching said first hash table will be affected by said freeing.

2. The system in accordance with claim 1, wherein said second hash table has a size that is an integral factor of a size of said first hash table.

3. The system in accordance with claim 1, wherein said resizing comprises shrinking said first hash table and wherein (1) a hash function is selected for said second hash table so that elements of a given hash bucket of said first hash table map to a single hash bucket of said second hash table, and (2) said second hash table bucket links to a first hash bucket of said first hash table that in turn links to at least one additional hash bucket of said first hash table, such that said second hash table bucket chains through different buckets of said first hash table whose elements map to said second hash table bucket.

4. The system in accordance with claim 1, wherein said resizing comprises expanding said first hash table and wherein (1) a hash function is selected for said second hash table so that elements of a given hash bucket in said first hash table map to a predictable set of hash buckets of said second hash table, and (2) at least two hash buckets of said second hash table link to the same hash bucket of said first hash table due to said first hash table bucket containing elements that map to different hash buckets of said second hash table.

5. The system in accordance with claim 4, wherein said resizing comprises expanding said first hash table and at least two hash buckets of said second hash table are linked to the same hash bucket of said first hash table, and wherein said operations further include separating said same hash bucket of said first hash table into said at least two hash buckets of said second hash table, said separating being performed by de-linking chains of elements in said same hash bucket of said first hash table that respectively hash to different ones of said at least two hash buckets of said second hash table.

6. The system in accordance with claim 5, wherein said separating includes waiting for a grace period before de-linking any two of said chains from each other, said grace period guaranteeing that no readers searching said second hash table will be affected by said de-linking.

7. A computer program product, comprising:

one or more non-transitory machine-usable storage media;

program instructions provided by said one or more media for programming a data processing platform having one or more processors operatively coupled to a memory to perform operations, said memory storing a first RCU [Read-Copy Update]-protected hash table, and said operations comprising;

allocating a second RCU-protected hash table in said memory, said second hash table representing a resized version of said first hash table that has a different number of hash buckets than said first hash table, said second hash table buckets being defined but initially having no hash table elements;

populating said second hash table without copying or moving any hash table elements in memory by linking each hash bucket of said second hash table to all hash buckets of said first hash table containing elements that hash to said second hash bucket;

publishing said second hash table so that it is available for searching by hash table readers; and

freeing said first hash table from said memory after waiting for a grace period which guarantees that no readers searching said first hash table will be affected by said freeing.

8. The computer program product in accordance with claim 7, wherein said second hash table has a size that is an integral factor of a size of said first hash table.

9. The computer program product in accordance with claim 7, wherein said resizing comprises shrinking said first hash table and wherein (1) a hash function is selected for said second hash table so that elements of a given hash bucket of said first hash table map to a single hash bucket of said second hash table, and (2) said second hash table bucket links to a first hash bucket of said first hash table that in turn links to at least one additional hash bucket of said first hash table, such that said second hash table bucket chains through different buckets of said first hash table whose elements map to said second hash table bucket.

10. The computer program product in accordance with claim 7, wherein said resizing comprises expanding said first hash table and wherein (1) a hash function is selected for said second hash table so that elements of a given hash bucket in said first hash table map to a predictable set of hash buckets of said second hash table, and (2) at least two hash buckets of said second hash table link to the same hash bucket of said first hash table due to said first hash table bucket containing elements that map to different hash buckets of said second hash table.

11. The computer program product in accordance with claim 10, wherein said resizing comprises expanding said first hash table and at least two hash buckets of said second hash table are linked to the same hash bucket of said first hash table, and wherein said operations further include separating said same hash bucket of said first hash table into said at least two hash buckets of said second hash table, said separating being performed by de-linking chains of elements in said same hash bucket of said first hash table that respectively hash to different ones of said at least two hash buckets of said second hash table.

12. The computer program product in accordance with claim 11, wherein said separating includes waiting for a grace period before de-linking any two of said chains from each other, said grace period guaranteeing that no readers searching said second hash table will be affected by said de-linking.