X-Git-Url: http://git.liburcu.org/?a=blobdiff_plain;f=rcuja%2Frcuja-shadow-nodes.c;h=b27812e3a74429efaaa945603499a7004421a1e8;hb=refs%2Fheads%2Furcu%2Frcuja-range;hp=5ef68d58631bd5d7a673496f78e755ce78b97a90;hpb=e1db2db589f05c48ae9e8b0199989d76bb2f7b14;p=userspace-rcu.git diff --git a/rcuja/rcuja-shadow-nodes.c b/rcuja/rcuja-shadow-nodes.c index 5ef68d5..b27812e 100644 --- a/rcuja/rcuja-shadow-nodes.c +++ b/rcuja/rcuja-shadow-nodes.c @@ -3,7 +3,7 @@ * * Userspace RCU library - RCU Judy Array Shadow Node Hash Table * - * Copyright 2012 - Mathieu Desnoyers + * Copyright 2012-2013 - Mathieu Desnoyers * * This library is free software; you can redistribute it and/or * modify it under the terms of the GNU Lesser General Public @@ -24,16 +24,15 @@ #include #include #include +#include +#include +#include #include #include #include -#include #include -#include -#include #include "rcuja-internal.h" -#include "bitfield.h" static unsigned long hash_seed; @@ -168,26 +167,26 @@ unsigned long hash_pointer(const void *_key, unsigned long seed) static int match_pointer(struct cds_lfht_node *node, const void *key) { - struct rcu_ja_shadow_node *shadow = - caa_container_of(node, struct rcu_ja_shadow_node, ht_node); + struct cds_ja_shadow_node *shadow = + caa_container_of(node, struct cds_ja_shadow_node, ht_node); - return (key == shadow->node); + return (key == shadow->node_flag); } __attribute__((visibility("protected"))) -struct rcu_ja_shadow_node *rcuja_shadow_lookup_lock(struct cds_lfht *ht, - struct rcu_ja_node *node) +struct cds_ja_shadow_node *rcuja_shadow_lookup_lock(struct cds_lfht *ht, + struct cds_ja_inode_flag *node_flag) { struct cds_lfht_iter iter; struct cds_lfht_node *lookup_node; - struct rcu_ja_shadow_node *shadow_node; + struct cds_ja_shadow_node *shadow_node; const struct rcu_flavor_struct *flavor; int ret; flavor = cds_lfht_rcu_flavor(ht); flavor->read_lock(); - cds_lfht_lookup(ht, hash_pointer(node, hash_seed), - match_pointer, node, &iter); + cds_lfht_lookup(ht, hash_pointer(node_flag, hash_seed), + match_pointer, node_flag, &iter); lookup_node = cds_lfht_iter_get_node(&iter); if (!lookup_node) { @@ -195,7 +194,8 @@ struct rcu_ja_shadow_node *rcuja_shadow_lookup_lock(struct cds_lfht *ht, goto rcu_unlock; } shadow_node = caa_container_of(lookup_node, - struct rcu_ja_shadow_node, ht_node); + struct cds_ja_shadow_node, ht_node); + dbg_printf("Lock %p\n", shadow_node->lock); ret = pthread_mutex_lock(shadow_node->lock); assert(!ret); if (cds_lfht_is_node_deleted(lookup_node)) { @@ -209,101 +209,130 @@ rcu_unlock: } __attribute__((visibility("protected"))) -void rcuja_shadow_unlock(struct rcu_ja_shadow_node *shadow_node) +void rcuja_shadow_unlock(struct cds_ja_shadow_node *shadow_node) { int ret; + dbg_printf("Unlock %p\n", shadow_node->lock); ret = pthread_mutex_unlock(shadow_node->lock); assert(!ret); } __attribute__((visibility("protected"))) -int rcuja_shadow_set(struct cds_lfht *ht, - struct rcu_ja_node *new_node, - struct rcu_ja_shadow_node *inherit_from) +struct cds_ja_shadow_node *rcuja_shadow_set(struct cds_lfht *ht, + struct cds_ja_inode_flag *new_node_flag, + struct cds_ja_shadow_node *inherit_from, + struct cds_ja *ja, int level) { - struct rcu_ja_shadow_node *shadow_node; + struct cds_ja_shadow_node *shadow_node; struct cds_lfht_node *ret_node; const struct rcu_flavor_struct *flavor; shadow_node = calloc(sizeof(*shadow_node), 1); if (!shadow_node) - return -ENOMEM; + return NULL; - shadow_node->node = new_node; + shadow_node->node_flag = new_node_flag; + shadow_node->ja = ja; /* * Lock can be inherited from previous node at this position. */ if (inherit_from) { shadow_node->lock = inherit_from->lock; + shadow_node->level = inherit_from->level; } else { shadow_node->lock = calloc(sizeof(*shadow_node->lock), 1); if (!shadow_node->lock) { free(shadow_node); - return -ENOMEM; + return NULL; } pthread_mutex_init(shadow_node->lock, NULL); + shadow_node->level = level; } flavor = cds_lfht_rcu_flavor(ht); flavor->read_lock(); ret_node = cds_lfht_add_unique(ht, - hash_pointer(new_node, hash_seed), + hash_pointer(new_node_flag, hash_seed), match_pointer, - new_node, + new_node_flag, &shadow_node->ht_node); flavor->read_unlock(); if (ret_node != &shadow_node->ht_node) { free(shadow_node); - return -EEXIST; + return NULL; } - return 0; + return shadow_node; +} + +static +void free_shadow_node(struct rcu_head *head) +{ + struct cds_ja_shadow_node *shadow_node = + caa_container_of(head, struct cds_ja_shadow_node, head); + free(shadow_node); } static void free_shadow_node_and_node(struct rcu_head *head) { - struct rcu_ja_shadow_node *shadow_node = - caa_container_of(head, struct rcu_ja_shadow_node, head); - free(shadow_node->node); + struct cds_ja_shadow_node *shadow_node = + caa_container_of(head, struct cds_ja_shadow_node, head); + free_cds_ja_node(shadow_node->ja, ja_node_ptr(shadow_node->node_flag)); + free(shadow_node); +} + +static +void free_shadow_node_and_lock(struct rcu_head *head) +{ + struct cds_ja_shadow_node *shadow_node = + caa_container_of(head, struct cds_ja_shadow_node, head); + free(shadow_node->lock); free(shadow_node); } static void free_shadow_node_and_node_and_lock(struct rcu_head *head) { - struct rcu_ja_shadow_node *shadow_node = - caa_container_of(head, struct rcu_ja_shadow_node, head); - free(shadow_node->node); + struct cds_ja_shadow_node *shadow_node = + caa_container_of(head, struct cds_ja_shadow_node, head); + assert(shadow_node->level); + free_cds_ja_node(shadow_node->ja, ja_node_ptr(shadow_node->node_flag)); free(shadow_node->lock); free(shadow_node); } __attribute__((visibility("protected"))) int rcuja_shadow_clear(struct cds_lfht *ht, - struct rcu_ja_node *node, + struct cds_ja_inode_flag *node_flag, + struct cds_ja_shadow_node *shadow_node, unsigned int flags) { struct cds_lfht_iter iter; struct cds_lfht_node *lookup_node; - struct rcu_ja_shadow_node *shadow_node; const struct rcu_flavor_struct *flavor; int ret, lockret; + int lookup_shadow = 0; flavor = cds_lfht_rcu_flavor(ht); flavor->read_lock(); - cds_lfht_lookup(ht, hash_pointer(node, hash_seed), - match_pointer, node, &iter); + + cds_lfht_lookup(ht, hash_pointer(node_flag, hash_seed), + match_pointer, node_flag, &iter); lookup_node = cds_lfht_iter_get_node(&iter); if (!lookup_node) { ret = -ENOENT; goto rcu_unlock; } - shadow_node = caa_container_of(lookup_node, - struct rcu_ja_shadow_node, ht_node); - lockret = pthread_mutex_lock(shadow_node->lock); - assert(!lockret); + + if (!shadow_node) { + shadow_node = caa_container_of(lookup_node, + struct cds_ja_shadow_node, ht_node); + lockret = pthread_mutex_lock(shadow_node->lock); + assert(!lockret); + lookup_shadow = 1; + } /* * Holding the mutex across deletion, and by also re-checking if @@ -311,8 +340,10 @@ int rcuja_shadow_clear(struct cds_lfht *ht, * don't let RCU JA use a node being removed. */ ret = cds_lfht_del(ht, lookup_node); - if (!ret) { - assert(flags & RCUJA_SHADOW_CLEAR_FREE_NODE); + if (ret) + goto unlock; + if ((flags & RCUJA_SHADOW_CLEAR_FREE_NODE) + && shadow_node->level) { if (flags & RCUJA_SHADOW_CLEAR_FREE_LOCK) { flavor->update_call_rcu(&shadow_node->head, free_shadow_node_and_node_and_lock); @@ -320,15 +351,77 @@ int rcuja_shadow_clear(struct cds_lfht *ht, flavor->update_call_rcu(&shadow_node->head, free_shadow_node_and_node); } + } else { + if (flags & RCUJA_SHADOW_CLEAR_FREE_LOCK) { + flavor->update_call_rcu(&shadow_node->head, + free_shadow_node_and_lock); + } else { + flavor->update_call_rcu(&shadow_node->head, + free_shadow_node); + } + } +unlock: + if (lookup_shadow) { + lockret = pthread_mutex_unlock(shadow_node->lock); + assert(!lockret); } - lockret = pthread_mutex_unlock(shadow_node->lock); - assert(!lockret); rcu_unlock: flavor->read_unlock(); return ret; } +/* + * Delete all shadow nodes and nodes from hash table, along with their + * associated lock. + */ +__attribute__((visibility("protected"))) +void rcuja_shadow_prune(struct cds_lfht *ht, + unsigned int flags) +{ + const struct rcu_flavor_struct *flavor; + struct cds_ja_shadow_node *shadow_node; + struct cds_lfht_iter iter; + int ret, lockret; + + flavor = cds_lfht_rcu_flavor(ht); + /* + * Read-side lock is needed to ensure hash table node existence + * vs concurrent resize. + */ + flavor->read_lock(); + cds_lfht_for_each_entry(ht, &iter, shadow_node, ht_node) { + lockret = pthread_mutex_lock(shadow_node->lock); + assert(!lockret); + + ret = cds_lfht_del(ht, &shadow_node->ht_node); + if (ret) + goto unlock; + if ((flags & RCUJA_SHADOW_CLEAR_FREE_NODE) + && shadow_node->level) { + if (flags & RCUJA_SHADOW_CLEAR_FREE_LOCK) { + flavor->update_call_rcu(&shadow_node->head, + free_shadow_node_and_node_and_lock); + } else { + flavor->update_call_rcu(&shadow_node->head, + free_shadow_node_and_node); + } + } else { + if (flags & RCUJA_SHADOW_CLEAR_FREE_LOCK) { + flavor->update_call_rcu(&shadow_node->head, + free_shadow_node_and_lock); + } else { + flavor->update_call_rcu(&shadow_node->head, + free_shadow_node); + } + } + unlock: + lockret = pthread_mutex_unlock(shadow_node->lock); + assert(!lockret); + } + flavor->read_unlock(); +} + __attribute__((visibility("protected"))) struct cds_lfht *rcuja_create_ht(const struct rcu_flavor_struct *flavor) { @@ -338,12 +431,9 @@ struct cds_lfht *rcuja_create_ht(const struct rcu_flavor_struct *flavor) } __attribute__((visibility("protected"))) -void rcuja_delete_ht(struct cds_lfht *ht) +int rcuja_delete_ht(struct cds_lfht *ht) { - int ret; - - ret = cds_lfht_destroy(ht, NULL); - assert(!ret); + return cds_lfht_destroy(ht, NULL); } __attribute__((constructor))