The URCU hash table API [LWN.net]

November 12, 2013

This article was contributed by Paul E. McKenney, Mathieu Desnoyers, and Lai Jiangshan

The RCU-protected hash-table API allows hash tables to be created, destroyed, and resized. The resize operations can be carried out manually using cds_lfht_resize(), but they will be carried out automatically when needed if the CDS_LFHT_AUTO_RESIZE flag is passed to cds_lfht_new(). There are API member functions to carry out lookups (cds_lfht_lookup(), cds_lfht_first(), cds_lfht_next(), and cds_lfht_next_duplicate()), additions (cds_lfht_add(), cds_lfht_add_unique(), and cds_lfht_add_replace()), deletions (cds_lfht_del()), and replacements (cds_lfht_replace()). There are also several functions that iterate over elements in the hash table, namely cds_lfht_for_each(), cds_lfht_for_each_duplicate(), cds_lfht_for_each_entry(), and cds_lfht_for_each_entry_duplicate().

The individual API members are as follows:

struct cds_lfht *cds_lfht_new(unsigned long init_size,
			      unsigned long min_nr_alloc_buckets,
			      unsigned long max_nr_buckets,
			      int flags,
			      pthread_attr_t *attr)

The cds_lfht_new() function allocates a new hash table and returns a pointer to it, or NULL on error. Its arguments are as follows:

init_size: Specifies the number of hash buckets to allocate initially, which must be a power of two.
min_nr_alloc_buckets: Specifies the minimum number of hash buckets, which also must be a power of two.
max_nr_buckets: Specifies the maximum number of hash buckets, which once more must be a power of two. Zero means “unlimited”.
flags: Specifies hash-table options. A value of zero takes default values, otherwise the following flags may be specified, using bitwise OR (‘|’) to combine, if desired:

CDS_LFHT_AUTO_RESIZE: Automatically resize the hash table. Note that the cds_lfht_resize() function may be invoked to manually resize the table.
CDS_LFHT_ACCOUNTING: Maintain counts of the number of nodes in the table. This flag is required to enabling shrinking a hash table. So CDS_LFHT_AUTO_RESIZE allows the hash table to grow, but “CDS_LFHT_AUTO_RESIZE | CDS_LFHT_ACCOUNTING” is required to also allow the hash table to shrink.

attr: Optional pthread_create() thread-creation attributes for the resize worker thread (or NULL to use the default attributes). One important use of attr occurs in real-time applications, where it can be important to set the priorities of the resize worker threads so as to avoid starvation of these threads by an endless deluge of cds_lfht_add() invocations. After all, such starvation could result in a too-small hash table having the lookup performance of a linked list. Note that attr is ignored unless or until the hash table is actually resized.

Threads invoking cds_lfht_new() are not required to be registered as RCU readers, which means that it is permissible to invoke cds_lfht_new() very early, for example, before RCU has been initialized.

int cds_lfht_destroy(struct cds_lfht *ht, pthread_attr_t **attr)

The cds_lfht_destroy() function deletes a hash table that was previously created using cds_lfht_new(). If the deletion is successful, zero is returned. The cds_lfht_destroy() function's arguments are as follows:

ht: A pointer to the hash table to destroy.
attr: A pointer to a pointer in which to store the attr pointer that was passed to the corresponding call to cds_lfht_new. The purpose is to allow the caller to deallocate the storage. If the caller does not need to deallocate storage (for example, if attr was statically allocated), NULL may be passed in.

Threads invoking cds_lfht_destroy() must be registered as RCU readers (using rcu_register_thread()). It is illegal to invoke cds_lfht_destroy() from within either an RCU read-side critical section or any function passed to call_rcu().
The hash table must be empty before this function is called, otherwise it will return failure. In addition, all other operations on the hash table must have ceased prior to the call to cds_lfht_destroy().

void cds_lfht_resize(struct cds_lfht *ht, unsigned long new_size)

The cds_lfht_resize() function initiates a resize operation. Its arguments are as follows:

ht: A pointer to the hash table to be resized.
new_size: The desired size, which should be a power of two.

Threads invoking cds_lfht_resize() must be registered as RCU readers (using rcu_register_thread()). Note that this function does not necessarily execute any memory barriers.

void cds_lfht_count_nodes(struct cds_lfht *ht,
			  long *split_count_before,
			  unsigned long *count,
			  long *split_count_after)

The cds_lfht_count_nodes() function counts the number of elements in the hash table. Note that nodes can be added to or removed from that hash table at any time, so that any count will necessarily be approximate unless the caller has prevented updates to the hash table for the duration.

ht: A pointer to the hash table.
split_count_before: If CDS_LFHT_ACCOUNTING was specified at hash-table creation, the sum of the resulting counts will be stored to the referenced variable prior to traversing the hash table. On the other hand, without CDS_LFHT_ACCOUNTING, the value stored will always be zero.
count: The actual count of elements will be stored to the referenced variable. This count is obtained by iterating over the full hash table.
split_count_after: If CDS_LFHT_ACCOUNTING was specified at hash-table creation, the sum of the resulting counts will be stored to the referenced variable after traversing the hash table. Again, without CDS_LFHT_ACCOUNTING, the value stored will always be zero.

The caller must be in an RCU read-side critical section, and therefore must have been registered as an RCU reader (using rcu_register_thread()).

Quick Quiz 1: But if the caller to cds_lfht_count_nodes() needs to be in an RCU read-side critical section, that sounds a lot like this function really is counting the elements in the hash table one at a time, which would be ridiculously slow on a large hash table. Why not just keep a simple count of the number of elements in the hash table? You could just increment it when an element is added and decrement it when that element is removed. What could be simpler?
Answer

struct cds_lfht_node *cds_lfht_iter_get_node(struct cds_lfht_iter *iter)

This function extracts a pointer to the cds_lfht_node structure from a cds_lfht_iter structure, such as that produced by cds_lfht_lookup(). The caller will normally need to apply caa_container_of() to map the cds_lfht_node to the enclosing data structure.

iter: A pointer to a cds_lfht_iter structure.

The caller must be in an RCU read-side critical section, and therefore must have been registered as an RCU reader (using rcu_register_thread()). Note that this RCU read-side critical section must enclose the full code path from the initial cds_lfht_lookup() or cds_lfht_first() that initiated hash-table traversal resulting in iter being produced.

void cds_lfht_lookup(struct cds_lfht *ht,
		     unsigned long hash,
		     cds_lfht_match_fct match,
		     const void *key,
		     struct cds_lfht_iter *iter)

The cds_lfht_lookup() function looks up the specified element.
ht: A pointer to the hash table.
hash: The hash of the desired element.
match: The match function, which must be defined as follows:
	int match(struct cds_lfht_node *node, const void *key)
	
This function must return non-zero if key matches that associated with node and zero otherwise.
key: The key of the desired element. Note that prior to calling cds_lfht_lookup(), the caller must have computed hash from the object referenced by key.
iter: A pointer to a caller-supplied cds_lfht_iter structure into which cds_lfht_lookup() places the results of the lookup. The cds_lfht_iter_get_node() function may be used to extract the resulting node from iter.
The caller must be in an RCU read-side critical section, and therefore must have been registered as an RCU reader (using rcu_register_thread()). Note that the cds_lfht_lookup() function takes on the role of rcu_dereference(), allowing the element's fields to be accessed normally.

void cds_lfht_first(struct cds_lfht *ht, struct cds_lfht_iter *iter)

The cds_lfht_first() function looks up the first element in the hash table. This function may be used in place of cds_lfht_lookup() in order to begin a full scan of all elements in the hash table.

ht: A pointer to the hash table.
iter: A pointer to a caller-supplied cds_lfht_iter structure into which cds_lfht_first() places the results of the lookup. The cds_lfht_iter_get_node() function may be used to extract the resulting node from iter.

The caller must be in an RCU read-side critical section, and therefore must have been registered as an RCU reader (using rcu_register_thread()). Note that the cds_lfht_first() function takes on the role of rcu_dereference(), allowing the element's fields to be read and written normally.

void cds_lfht_next(struct cds_lfht *ht, struct cds_lfht_iter *iter)

Advances the specified iterator to the next hash element, even if that element is in some later hash bucket.

ht: A pointer to the hash table.
iter: A pointer to a caller-supplied iterator marking the current element in the hash table. Upon return, this will be updated to reference the next element, or the NULL element if there is no next element. Either way, the cds_lfht_iter_get_node() function may be used to extract the resulting node from iter.

The caller must be in an RCU read-side critical section, and therefore must have been registered as an RCU reader (using rcu_register_thread()). Note that the cds_lfht_next() function takes on the role of rcu_dereference(), allowing the element's fields to be read and written normally.

void cds_lfht_next_duplicate(struct cds_lfht *ht,
			     cds_lfht_match_fct match,
			     const void *key,
			     struct cds_lfht_iter *iter)

Advances the specified iterator to the next hash element, but only if the next element matches the specified key.

ht: A pointer to the hash table.
match: The match function, which must be defined as described in cds_lfht_lookup().
key: The key of the desired element.
iter: A pointer to a caller-supplied iterator marking the current element in the hash table. Upon return, this will be updated to reference the next element, or the NULL element if there is no next element. Either way, the cds_lfht_iter_get_node() function may be used to extract the resulting node from iter.

The caller must be in an RCU read-side critical section, and therefore must have been registered as an RCU reader (using rcu_register_thread()). Note that the cds_lfht_next_duplicate() function takes on the role of rcu_dereference(), allowing the element's fields to be read and written normally.

Quick Quiz 2: Why doesn't the caller supply a hash to cds_lfht_next_duplicate()? Wouldn't that speed up the rejection of the mismatches?
Answer

int cds_lfht_is_node_deleted(struct cds_lfht_node *node)

Checks to see whether the specified node has been deleted, returning non-zero if so.

node: A pointer to the node to be checked for deletion.

The caller must be in an RCU read-side critical section, and therefore must have been registered as an RCU reader (using rcu_register_thread()). Note that this RCU read-side critical section must enclose the full code path from the initial cds_lfht_lookup() or cds_lfht_first() that initiated this hash-table traversal.

cds_lfht_for_each(ht, iter, node)

Iterates over all entries in the hash table. This macro expands to a for statement, so it must be immediately followed by either a statement or a statement block.

ht: A pointer to the hash table.
iter: A pointer to a caller-supplied cds_lfht_iter structure that cds_lfht_for_each() uses to control the traversal.
node: A cds_lfht_node pointer that is iterated over all nodes in the hash table. Use caa_container_of() to map the node to the enclosing data structure.

The caller must be in an RCU read-side critical section, and therefore must have been registered as an RCU reader (using rcu_register_thread()). This RCU read-side critical section must enclose the entire loop: It is illegal to momentarily exit the RCU read-side critical section in the body of the loop.

Quick Quiz 3: Why bother with the cds_lfht_iter structure? Why not just iterate over the cds_lfht_node structures making up the hash table itself?
Answer

cds_lfht_for_each_duplicate(ht, hash, match, key, iter, node)

Iterates over all entries in the hash table having the specified key. This macro expands to a for statement, so it must be immediately followed by either a statement or a statement block.

ht: A pointer to the hash table.
hash: The hash of the key value.
match: The match function, which must be defined as described in cds_lfht_lookup().
key: The desired key.
iter: A pointer to a caller-supplied cds_lfht_iter structure that cds_lfht_for_each() uses to control the traversal.
node: A cds_lfht_node pointer that is iterated over all nodes in the hash table. Use caa_container_of() to map the node to the enclosing data structure.

The caller must be in an RCU read-side critical section, and therefore must have been registered as an RCU reader (using rcu_register_thread()). This RCU read-side critical section must enclose the entire loop: It is illegal to momentarily exit the RCU read-side critical section in the body of the loop.

cds_lfht_for_each_entry(ht, iter, pos, member)

Iterates over the enclosing data structure of each entry in the hash table. This macro expands to a for statement, so it must be immediately followed by either a statement or a statement block.

ht: A pointer to the hash table.
iter: A pointer to a caller-supplied cds_lfht_iter structure that cds_lfht_for_each() uses to control the traversal.
pos: A pointer of the type of the enclosing data structure.
member: The name of the cds_lfht_node field within the enclosing data structure.

The caller must be in an RCU read-side critical section, and therefore must have been registered as an RCU reader (using rcu_register_thread()). This RCU read-side critical section must enclose the entire loop: It is illegal to momentarily exit the RCU read-side critical section in the body of the loop.

cds_lfht_for_each_entry_duplicate(ht, hash, match, key, iter, pos, member)

Iterates over the enclosing data structure of each entry in the hash table matching the specified key. This macro expands to a for statement, so it must be immediately followed by either a statement or a statement block.

ht: A pointer to the hash table.
hash: The hash of the key value.
match: The match function, which must be defined as described in cds_lfht_lookup().
key: The desired key.
iter: A pointer to a caller-supplied cds_lfht_iter structure that cds_lfht_for_each() uses to control the traversal.
pos: A pointer of the type of the enclosing data structure.
member: The name of the cds_lfht_node field within the enclosing data structure.

The caller must be in an RCU read-side critical section, and therefore must have been registered as an RCU reader (using rcu_register_thread()). This RCU read-side critical section must enclose the entire loop: It is illegal to momentarily exit the RCU read-side critical section in the body of the loop.

void cds_lfht_add(struct cds_lfht *ht,
		  unsigned long hash,
		  struct cds_lfht_node *node)

Adds the specified node to the hash table. This function is the only way to add duplicate keys.

ht: A pointer to the hash table.
hash: The hash of the key value.
node: A pointer to the cds_lfht_node field of the enclosing data structure to be added.

The caller must be in an RCU read-side critical section, and therefore must have been registered as an RCU reader (using rcu_register_thread()). This function issues a full memory barrier before and after its atomic commit.

struct cds_lfht_node *cds_lfht_add_unique(struct cds_lfht *ht,
					  unsigned long hash,
					  cds_lfht_match_fct match,
					  const void *key,
					  struct cds_lfht_node *node)

Adds the specified node to the hash table, but only if there is not already a node with the specified key. Returns the node added, if successful, otherwise returns the node from the hash table that has the specified key.

ht: A pointer to the hash table.
hash: The hash of the key value.
match: The match function, which must be defined as described in cds_lfht_lookup().
key: The desired key.
node: A pointer to the cds_lfht_node field of the replacement enclosing data structure.

The caller must be in an RCU read-side critical section, and therefore must have been registered as an RCU reader (using rcu_register_thread()).
Upon success, this function issues a full memory barrier before and after its atomic commit. Upon failure, this function takes on the role of rcu_dereference(), allowing the conflicting element's fields to be read and written normally.

struct cds_lfht_node *cds_lfht_add_replace(struct cds_lfht *ht,
					   unsigned long hash,
					   cds_lfht_match_fct match,
					   const void *key,
					   struct cds_lfht_node *node)

Replaces the node with the specified key, or, if there is no such node, adds one. Returns the node replaced, if such a node existed, otherwise returns NULL.

ht: A pointer to the hash table.
hash: The hash of the key value.
match: The match function, which must be defined as described in cds_lfht_lookup().
key: The desired key.
node: A pointer to the cds_lfht_node field of the replacement enclosing data structure.

The caller must be in an RCU read-side critical section, and therefore must have been registered as an RCU reader (using rcu_register_thread()). This function issues a full memory barrier before and after its atomic commit.
If a cds_lfht_add_replace() successfully replaces an existing node, then any concurrent cds_lfht_lookup() using that same key is guaranteed not to fail, even momentarily.
The caller must wait a full grace period (e.g., by calling synchronize_rcu() between replacement and freeing the old node that was replaced.

int cds_lfht_replace(struct cds_lfht *ht,
		     struct cds_lfht_iter *old_iter,
		     unsigned long hash,
		     cds_lfht_match_fct match,
		     const void *key,
		     struct cds_lfht_node *new_node)

Replaces the node with the specified key, or, if there is no such node, returns failure (-ENOENT).

ht: A pointer to the hash table.
old_iter: A pointer to a caller-supplied iterator marking the current element in the hash table.
hash: The hash of the key value.
match: The match function, which must be defined as described in cds_lfht_lookup().
key: The desired key.
new_node: A pointer to the cds_lfht_node field of the replacement enclosing data structure.

The caller must be in an RCU read-side critical section, and therefore must have been registered as an RCU reader (using rcu_register_thread()).
Upon success, this function issues a full memory barrier before and after its atomic commit. Upon failure, this function provides no memory-ordering semantics.
If a cds_lfht_replace() successfully replaces an existing node, then any concurrent cds_lfht_lookup() using that same key is guaranteed not to fail, even momentarily.
The caller must wait a full grace period (e.g., by calling synchronize_rcu() between replacement and freeing the old node that was replaced.

int cds_lfht_del(struct cds_lfht *ht, struct cds_lfht_node *node)

Deletes the specified node from the hash table, returning zero on success or a negative error code upon failure.

ht: A pointer to the hash table.
node: A pointer to the cds_lfht_node field of the enclosing data structure to be deleted. A NULL node will result in failure.

The caller must be in an RCU read-side critical section, and therefore must have been registered as an RCU reader (using rcu_register_thread()). This RCU read-side critical section must enclose both cds_lfht_del() invocation as well as whatever chain of function calls looked up node.
Upon success, this function issues a full memory barrier before and after its atomic commit. Upon failure, this function provides no memory-ordering semantics.
The caller must wait a full grace period (e.g., by calling synchronize_rcu() between deletion and freeing the deleted node.

Answers to Quick Quizzes

Answer: That would indeed be simple, but it would also ruin the performance and scalability of element addition and removal. There are of course special purpose counters that perform and scale well, but these tend to be rather specialized. Therefore, if fast counting is important, the user of the hash table should enlist the aid of whatever parallel counter is appropriate. Several such counters may be found in the counting chapter of Is Parallel Programming Hard, And, If So, What Can You Do About It?.

Back to Quick Quiz 1.

Quick Quiz 2: Why doesn't the caller supply a hash to cds_lfht_next_duplicate()? Wouldn't that speed up the rejection of the mismatches?

Answer: Because cds_lfht_next_duplicate() continues a traversal from a node having the desired hash value, cds_lfht_next_duplicate() can load the key (already bit-reversed) from that previous node. This raises the question of why cds_lfht_next_duplicate() can't also access the key from that same previous node. The answer is that the hash table doesn't know where the key is. Instead, it is passed a caller-provided match() function that knows where the key is in the caller-defined portion of the node. This approach allows the caller to use an arbitrarily defined key, but also requires that cds_lfht_next_duplicate() be passed the key.

Back to Quick Quiz 2.

Quick Quiz 3: Why bother with the cds_lfht_iter structure? Why not just iterate over the cds_lfht_node structures making up the hash table itself?

Answer: The separate cds_lfht_iter structure is required in order to correctly handle cds_lfht_replace() and cds_lfht_add_replace() invocations executed concurrently with lookups and traversals.

The cds_lfht_replace() and cds_lfht_add_replace() operations provide their uniqueness guarantees by adding the replacement node immediately after the node being replaced. The trick is that a given node can be marked as deleted without actually removing it from the hash table by setting a bit in bottom bits of the pointer to the deleted node's next node. This means that the cds_lfht_replace() and cds_lfht_add_replace() operations can set the “deleted” bit in the pointer to the replacement node that is stored in the node being replaced, thus adding the replacement node and deleting the replaced node atomically with a single store.

Of course, nodes marked deleted must eventually be removed from the hash table, but this removal can be done in a lazy fashion. This process is (fancifully) illustrated in the following diagram:

Time advances from left to right through five states. In the first state, we have elements A, B, and C. An invocation of cds_lfht_replace() replaces element B with B', marking the pointer out of element B as shown in the second state. Note that this replacement of element B with B' is carried out with a single store to element B's ->next pointer, allowing the replacement to appear atomic to readers. At some later time, the now-obsolete element B will be removed from the list, as shown in the third state, after which it can no longer be accessed by new readers (hence the change in color from red to yellow). A later invocation of synchronize_rcu() waits for all pre-existing readers to complete, so that there are no longer any readers accessing the old element B (hence the change in color from yellow to green), as shown in the fourth state. At this point, it is safe to free element B, as shown in the fifth and final state.

On the lookup and traversal side, the problem is that we cannot fetch a given pointer twice, as the pointer might change in the meantime. In addition, before we return a pointer to a given object, we must check the pointer to the next object in order to check to see if it has been marked deleted. But we will need to refer to this same pointer on the next pass through the loop. Therefore, we need to track two pointers across the body of the loop, and the cds_lfht_iter structure is where these pointers are stored.

Back to Quick Quiz 3.