From 2ed9584921304d4b526b530c29dae75f24649c92 Mon Sep 17 00:00:00 2001 From: Mathieu Desnoyers Date: Sat, 26 Sep 2009 23:46:29 -0400 Subject: [PATCH] Initial urcu hash commit Signed-off-by: Mathieu Desnoyers --- Makefile.inc | 4 + urcu-hash.c | 230 +++++++++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 234 insertions(+) create mode 100644 urcu-hash.c diff --git a/Makefile.inc b/Makefile.inc index 6dba18d..9d566b7 100644 --- a/Makefile.inc +++ b/Makefile.inc @@ -8,6 +8,7 @@ all: checkarch liburcu.so urcu.o \ liburcu-mb.so urcu-mb.o \ liburcu-defer.so urcu-defer.o \ urcu-yield.o \ + urcu-hash.o \ subdirs checkarch: @@ -38,6 +39,9 @@ urcu-qsbr.o: urcu-qsbr.c urcu-qsbr.h urcu-defer.o: urcu-defer.c urcu-defer.h $(CC) -fPIC ${CFLAGS} -c -o $@ $(SRC_DEP) +urcu-hash.o: urcu-hash.c + $(CC) -fPIC ${CFLAGS} -c -o $@ $(SRC_DEP) + liburcu.so: urcu.o $(CC) ${LDFLAGS} -fPIC -shared -o $@ $< diff --git a/urcu-hash.c b/urcu-hash.c new file mode 100644 index 0000000..1267af5 --- /dev/null +++ b/urcu-hash.c @@ -0,0 +1,230 @@ + +#define _LGPL_SOURCE +#include +#include +#include +#include +#include +#include +#include +#include + +#define HASH_SIZE 4096 + +typedef unsigned long (*ht_hash_fct)(void *key); + +struct rcu_ht_node; + +struct rcu_ht_node { + struct rcu_ht_node *next; + void *key; + void *data; +}; + +struct rcu_ht { + struct rcu_ht_node *tbl[HASH_SIZE]; + ht_hash_fct hash_fct; + void (*free_fct)(void *data); /* fct to free data */ +}; + +struct rcu_ht *ht_new(ht_hash_fct hash_fct, void (*free_fct)(void *data)); + +void ht_delete_all(struct rcu_ht *ht); + +int ht_destroy(struct rcu_ht *ht); + +void *ht_lookup(struct rcu_ht *ht, void *key); + +int ht_add(struct rcu_ht *ht, void *key, void *data); + +int ht_delete(struct rcu_ht *ht, void *key); + +void *ht_steal(struct rcu_ht *ht, void *key); + + +/* Implementation */ + +static unsigned long stupid_hash(void *key) +{ + return (unsigned long)key % HASH_SIZE; +} + +struct rcu_ht *ht_new(ht_hash_fct hash_fct, void (*free_fct)(void *data)) +{ + struct rcu_ht *ht; + + ht = calloc(1, sizeof(struct rcu_ht)); + ht->hash_fct = hash_fct; + ht->free_fct = free_fct; +} + +/* delete all elements */ +void ht_delete_all(struct rcu_ht *ht) +{ + unsigned long i; + struct rcu_ht_node **prev, *node; + + for (i = 0; i < HASH_SIZE; i++) { + rcu_read_lock(); + + prev = &ht->tbl[i]; + node = rcu_dereference(*prev); + /* + * Cut the head, therefore whole bucket will be unused + * after GP. (except for concurrent additions) + */ + rcu_assign_pointer(prev, NULL); + for (;;) { + if (likely(!node)) { + break; + } + prev = &node->next; + if (node->data) + call_rcu(ht->free_fct, node->data); + call_rcu(free, node); + node = rcu_dereference(*prev); + } + rcu_read_unlock(); + } +} + +/* + * Should only be called when no more concurrent readers nor writers can + * possibly access the table. + */ +int ht_destroy(struct rcu_ht *ht) +{ + ht_delete_all(ht); + free(ht); +} + +void *ht_lookup(struct rcu_ht *ht, void *key) +{ + unsigned long hash; + struct rcu_ht_node *node; + void *ret; + + hash = ht->hash_fct(key); + + rcu_read_lock(); + node = rcu_dereference(ht->tbl[hash]); + for (;;) { + if (likely(!node)) { + ret = NULL; + break; + } + if (node->key == key) { + ret = node->data; + break; + } + node = rcu_dereference(node->next); + } + rcu_read_unlock(); +} + +/* + * Will re-try until either: + * - The key is already there (-EEXIST) + * - We successfully add the key at the head of a table bucket. + */ +int ht_add(struct rcu_ht *ht, void *key, void *data) +{ + struct rcu_ht_node *node, *old_head, *new_head; + unsigned long hash; + int ret = 0; + + new_head = calloc(1, sizeof(struct rcu_ht_node)); + new_head->key = key; + new_head->data = data; + hash = ht->hash_fct(key); + + /* here comes the fun and tricky part. + * Add at the beginning with a cmpxchg. + * Hold a read lock between the moment the first element is read + * and the nodes traversal (to find duplicates). This ensures + * the head pointer has not been reclaimed when cmpxchg is done. + * Always adding at the head ensures that we would have to + * re-try if a new item has been added concurrently. So we ensure that + * we never add duplicates. */ +retry: + rcu_read_lock(); + + old_head = node = rcu_dereference(ht->tbl[hash]); + for (;;) { + if (likely(!node)) { + break; + } + if (node->key == key) { + ret = -EEXIST; + goto end; + } + node = rcu_dereference(node->next); + } + if (rcu_cmpxchg_pointer(&ht->tbl[hash], old_head, new_head) != old_head) + goto restart; +end: + rcu_read_unlock(); + + return ret; + + /* restart loop, release and re-take the read lock to be kind to GP */ +restart: + rcu_read_unlock(); + goto retry; +} + +/* + * Restart until we successfully remove the entry, or no entry is left + * ((void *)(unsigned long)-ENOENT). + */ +struct rcu_ht_node *ht_steal(struct rcu_ht *ht, void *key); +{ + struct rcu_ht_node **prev, *node; + unsigned long hash; + + hash = ht->hash_fct(key); + +retry: + rcu_read_lock(); + + prev = &ht->tbl[hash]; + node = rcu_dereference(*prev); + for (;;) { + if (likely(!node)) { + node = (void *)(unsigned long)-ENOENT; + goto end; + } + if (node->key == key) { + break; + } + prev = &node->next; + node = rcu_dereference(*prev); + } + /* Found it ! pointer to object is in "prev" */ + if (rcu_cmpxchg_pointer(prev, node, node->next) != node) + goto restart; +end: + rcu_read_unlock(); + + return node; + + /* restart loop, release and re-take the read lock to be kind to GP */ +restart: + rcu_read_unlock(); + goto retry; +} + +int ht_delete(struct rcu_ht *ht, void *key) +{ + struct rcu_ht_node *node; + + node = ht_steal(ht, key); + if (node) { + if (free_fct && node->data) + call_rcu(ht->free_fct, node->data); + call_rcu(free, node); + return 0; + } else { + return -ENOENT; + } +} -- 2.34.1