Optimized deletion and insertion for high-performance resizable RCU-protected hash tables

• US 8,666,952 B2
• Filed: 04/25/2012
• Issued: 03/04/2014
• 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/455,220
• Publication Number:
  US 20130151811A1
• Time in Patent Office: 678 Days
• Field of Search: 707/693, 707/709, 707800-801, 707/695, 707/737, 711/202, 711/221, 717/168
• US Class Current: 707/695
• CPC Class Codes: G06F 16/9014 hash tables

Abstract

Concurrent resizing and modification of a first RCU-protected hash table includes allocating a second RCU-protected hash table, populating it by linking each hash bucket of the second hash table to all hash buckets of the first hash table containing elements that hash to the second hash table bucket, and publishing the second hash table. If the modifying comprises insertion, a new element is inserted at the head of a corresponding bucket in the second hash table. If the modifying comprises deletion, then within an RCU read-side critical section: (1) all pointers in hash buckets of the first and second hash tables that reference the element being deleted are removed or redirected, and (2) the element is freed following a grace period that protects reader references to the deleted element. The first table is freed from memory after awaiting a grace period that protects reader references to the first hash table.

Claims

1. A method for concurrently resizing and modifying an Read-Copy Update (RCU)-protected hash table in a computer system having one or more processors operatively coupled to a memory, said memory including a computer usable medium storing an RCU-protected first hash table and at least one program of instructions executable by said processor to concurrently perform hash table resizing and modifying operations representing said method, 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 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;

if said modifying comprises an inserting a new hash table element, inserting said new hash table element at the head of a corresponding bucket in said second hash table;

if said modifying comprises deleting an existing hash table element, entering an RCU read-side critical section, removing or redirecting all pointers in one or more hash buckets of said first hash table and said second hash table that reference said existing hash table element, exiting said RCU read-side critical section, waiting for a grace period which guarantees that no readers searching said first hash table or said second hash table will be referencing said existing hash table element, and freeing said existing hash table element from said memory; 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 method in accordance with claim 1, wherein said modifying includes first determining whether said resizing is underway, and if not, performing said modifying on said first hash table only.

3. The method in accordance with claim 2, wherein said determining is performed after acquiring a lock on a hash bucket in said first hash table where said modifying is to be performed, and releasing said lock if said resizing is determined to be underway.

4. The method in accordance with claim 2, wherein said modifying comprises inserting a new hash table element, and wherein a lock is acquired on a hash bucket in said second hash table where said inserting is to be performed.

5. The method in accordance with claim 2, wherein said modifying comprises deleting an existing hash table element, and wherein locks are acquired on all hash buckets in said first hash table and said second hash table where said pointer removing or redirecting is to be performed.

6. The method in accordance with claim 1, wherein said modifying further includes performing an action to prevent starvation by successive invocations of said resizing.

7. A method for concurrently resizing and modifying Read-Copy Update (RCU)-protected hash table in a computer system having one or more processors operatively coupled to a memory, said memory including a computer usable medium storing an RCU-protected first hash table and at least one program of instructions executable by said processor to perform hash table resizing operations representing said method, 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 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;

if said modifying comprises an inserting a new hash table element, inserting said new hash table element at the head of a corresponding bucket in said second hash table;

if said modifying comprises deleting an existing hash table element, removing or redirecting all pointers in one or more hash buckets of said first hash table and said second hash table that reference said existing hash table element, exiting said RCU read-side critical section, waiting for a grace period which guarantees that no readers searching said first hash table or said second hash table will be referencing said existing hash table element, and freeing said existing hash table element from said memory;

said modifying includes first determining whether said resizing is underway, and if not, performing said modifying on said first hash table only, said determining being performed after acquiring a lock on a hash bucket in said first hash table where said modifying is to be performed, and releasing said first lock if said resizing is determined to be underway;

if said modifying comprises inserting a new hash table element, acquiring a lock on a hash bucket in said second hash table where said inserting is to be performed;

if said modifying comprises deleting an existing hash table element, acquiring locks on all hash buckets in said first hash table and said second hash table where said pointer removing or redirecting is to be performed; and

said modifying further includes performing an action to prevent starvation by successive invocations of said resizing; and

freeing said first hash table from 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 method 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.