From f0c29ed7ca7129056f5c757a9fbcbbfa8c14da44 Mon Sep 17 00:00:00 2001 From: Mathieu Desnoyers Date: Sat, 3 Sep 2011 11:16:02 -0400 Subject: [PATCH] RCU hash table API documentation Signed-off-by: Mathieu Desnoyers --- rculfhash.c | 28 ++++++++++------- urcu/rculfhash.h | 78 ++++++++++++++++++++++++++++++++++++++++++++---- 2 files changed, 91 insertions(+), 15 deletions(-) diff --git a/rculfhash.c b/rculfhash.c index 9854785..380665b 100644 --- a/rculfhash.c +++ b/rculfhash.c @@ -113,7 +113,7 @@ #include #ifdef DEBUG -#define dbg_printf(fmt, args...) printf(fmt, ## args) +#define dbg_printf(fmt, args...) printf("[debug rculfhash] " fmt, ## args) #else #define dbg_printf(fmt, args...) #endif @@ -358,7 +358,7 @@ void check_resize(struct rcu_ht *ht, struct rcu_table *t, uint32_t chain_len) { if (chain_len > 100) - dbg_printf("rculfhash: WARNING: large chain length: %u.\n", + dbg_printf("WARNING: large chain length: %u.\n", chain_len); if (chain_len >= CHAIN_LEN_RESIZE_THRESHOLD) ht_resize_lazy(ht, t, @@ -579,7 +579,7 @@ void init_table(struct rcu_ht *ht, struct rcu_table *t, { unsigned long i, end_order; - dbg_printf("rculfhash: init table: first_order %lu end_order %lu\n", + dbg_printf("init table: first_order %lu end_order %lu\n", first_order, first_order + len_order); end_order = first_order + len_order; t->size = !first_order ? 0 : (1UL << (first_order - 1)); @@ -587,10 +587,10 @@ void init_table(struct rcu_ht *ht, struct rcu_table *t, unsigned long j, len; len = !i ? 1 : 1UL << (i - 1); - dbg_printf("rculfhash: init order %lu len: %lu\n", i, len); + dbg_printf("init order %lu len: %lu\n", i, len); t->tbl[i] = calloc(len, sizeof(struct _rcu_ht_node)); for (j = 0; j < len; j++) { - dbg_printf("rculfhash: init entry: i %lu j %lu hash %lu\n", + dbg_printf("init entry: i %lu j %lu hash %lu\n", i, j, !i ? 0 : (1UL << (i - 1)) + j); struct rcu_ht_node *new_node = (struct rcu_ht_node *) &t->tbl[i][j]; @@ -602,7 +602,7 @@ void init_table(struct rcu_ht *ht, struct rcu_table *t, } /* Update table size */ t->size = !i ? 1 : (1UL << i); - dbg_printf("rculfhash: init new size: %lu\n", t->size); + dbg_printf("init new size: %lu\n", t->size); if (CMM_LOAD_SHARED(ht->in_progress_destroy)) break; } @@ -652,7 +652,7 @@ struct rcu_ht_node *ht_lookup(struct rcu_ht *ht, void *key, size_t key_len) index = hash & (t->size - 1); order = get_count_order_ulong(index + 1); lookup = &t->tbl[order][index & ((1UL << (order - 1)) - 1)]; - dbg_printf("rculfhash: lookup hash %lu index %lu order %lu aridx %lu\n", + dbg_printf("lookup hash %lu index %lu order %lu aridx %lu\n", hash, index, order, index & ((1UL << (order - 1)) - 1)); node = (struct rcu_ht_node *) lookup; for (;;) { @@ -730,7 +730,7 @@ int ht_delete_dummy(struct rcu_ht *ht) len = !order ? 1 : 1UL << (order - 1); for (i = 0; i < len; i++) { - dbg_printf("rculfhash: delete order %lu i %lu hash %lu\n", + dbg_printf("delete order %lu i %lu hash %lu\n", order, i, bit_reverse_ulong(t->tbl[order][i].reverse_hash)); assert(is_dummy(t->tbl[order][i].next)); @@ -787,7 +787,7 @@ void ht_count_nodes(struct rcu_ht *ht, (nr_dummy)++; node = clear_flag(next); } while (node); - dbg_printf("rculfhash: number of dummy nodes: %lu\n", nr_dummy); + dbg_printf("number of dummy nodes: %lu\n", nr_dummy); } static @@ -813,7 +813,7 @@ void _do_ht_resize(struct rcu_ht *ht) if (old_size == new_size) return; new_order = get_count_order_ulong(new_size) + 1; - printf("rculfhash: resize from %lu (order %lu) to %lu (order %lu) buckets\n", + dbg_printf("resize from %lu (order %lu) to %lu (order %lu) buckets\n", old_size, old_order, new_size, new_order); new_t = malloc(sizeof(struct rcu_table) + (new_order * sizeof(struct _rcu_ht_node *))); @@ -839,6 +839,14 @@ void ht_resize(struct rcu_ht *ht, int growth) struct rcu_table *t = rcu_dereference(ht->t); unsigned long target_size; + if (growth < 0) { + /* + * Silently refuse to shrink hash table. (not supported) + */ + dbg_printf("shrinking hash table not supported.\n"); + return; + } + target_size = resize_target_update(t, growth); if (t->size < target_size) { CMM_STORE_SHARED(t->resize_initiated, 1); diff --git a/urcu/rculfhash.h b/urcu/rculfhash.h index 40fe4df..8ee9bdd 100644 --- a/urcu/rculfhash.h +++ b/urcu/rculfhash.h @@ -1,6 +1,28 @@ #ifndef _URCU_RCULFHASH_H #define _URCU_RCULFHASH_H +/* + * urcu/rculfhash.h + * + * Userspace RCU library - Lock-Free RCU Hash Table + * + * Copyright 2011 - Mathieu Desnoyers + * + * This library is free software; you can redistribute it and/or + * modify it under the terms of the GNU Lesser General Public + * License as published by the Free Software Foundation; either + * version 2.1 of the License, or (at your option) any later version. + * + * This library is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public + * License along with this library; if not, write to the Free Software + * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA + */ + #include #include @@ -39,6 +61,9 @@ typedef unsigned long (*ht_hash_fct)(void *key, size_t length, typedef unsigned long (*ht_compare_fct)(void *key1, size_t key1_len, void *key2, size_t key2_len); +/* + * ht_node_init - initialize a hash table node + */ static inline void ht_node_init(struct rcu_ht_node *node, void *key, size_t key_len) @@ -48,6 +73,8 @@ void ht_node_init(struct rcu_ht_node *node, void *key, } /* + * ht_new - allocate a hash table. + * * init_size must be power of two. */ struct rcu_ht *ht_new(ht_hash_fct hash_fct, @@ -57,29 +84,70 @@ struct rcu_ht *ht_new(ht_hash_fct hash_fct, void (*ht_call_rcu)(struct rcu_head *head, void (*func)(struct rcu_head *head))); +/* + * ht_destroy - destroy a hash table. + */ int ht_destroy(struct rcu_ht *ht); -/* Count the number of nodes in the hash table. Call with rcu_read_lock held. */ + +/* + * ht_count_nodes - count the number of nodes in the hash table. + * + * Call with rcu_read_lock held. + */ void ht_count_nodes(struct rcu_ht *ht, unsigned long *count, unsigned long *removed); -/* Call with rcu_read_lock held. */ +/* + * ht_lookup - lookup a node by key. + * + * Returns NULL if not found. + * Call with rcu_read_lock held. + */ struct rcu_ht_node *ht_lookup(struct rcu_ht *ht, void *key, size_t key_len); -/* Call with rcu_read_lock held. */ -void ht_add(struct rcu_ht *ht, struct rcu_ht_node *node); +/* + * ht_next - get the next item with same key (after a lookup). + * + * Returns NULL if no following node exists with same key. + * RCU read-side lock must be held across ht_lookup and ht_next calls, and also + * between ht_next calls using the node returned by a previous ht_next. + * Call with rcu_read_lock held. + */ +struct rcu_ht_node *ht_next(struct rcu_ht *ht, struct rcu_ht_node *node); /* + * ht_add - add a node to the hash table. + * * Call with rcu_read_lock held. + */ +void ht_add(struct rcu_ht *ht, struct rcu_ht_node *node); + +/* + * ht_add_unique - add a node to hash table, if key is not present. + * * Returns the node added upon success. * Returns the unique node already present upon failure. If ht_add_unique fails, * the node passed as parameter should be freed by the caller. + * Call with rcu_read_lock held. */ struct rcu_ht_node *ht_add_unique(struct rcu_ht *ht, struct rcu_ht_node *node); -/* Call with rcu_read_lock held. */ +/* + * ht_remove - remove node from hash table. + * + * Node can be looked up with ht_lookup. RCU read-side lock must be held between + * lookup and removal. + * Call with rcu_read_lock held. + */ int ht_remove(struct rcu_ht *ht, struct rcu_ht_node *node); +/* + * ht_resize - Force a hash table resize + * @growth: growth order (current size is multiplied by 2^growth) + * + * Currently, only expand operation is supported (growth >= 0). + */ void ht_resize(struct rcu_ht *ht, int growth); #ifdef __cplusplus -- 2.34.1