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=2b369add76b7df205789f0aa0687639f32ae18a8;hpb=b4540e8adb5a4d726e9dbcf2388b6e9b628ce990;p=userspace-rcu.git diff --git a/rcuja/rcuja-shadow-nodes.c b/rcuja/rcuja-shadow-nodes.c index 2b369ad..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; @@ -171,12 +170,12 @@ int match_pointer(struct cds_lfht_node *node, const void *key) 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 cds_ja_shadow_node *rcuja_shadow_lookup_lock(struct cds_lfht *ht, - struct cds_ja_inode *node) + struct cds_ja_inode_flag *node_flag) { struct cds_lfht_iter iter; struct cds_lfht_node *lookup_node; @@ -186,8 +185,8 @@ struct cds_ja_shadow_node *rcuja_shadow_lookup_lock(struct cds_lfht *ht, 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) { @@ -196,6 +195,7 @@ struct cds_ja_shadow_node *rcuja_shadow_lookup_lock(struct cds_lfht *ht, } shadow_node = caa_container_of(lookup_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)) { @@ -213,14 +213,16 @@ 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 cds_ja_inode *new_node, - struct cds_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 cds_ja_shadow_node *shadow_node; struct cds_lfht_node *ret_node; @@ -228,37 +230,48 @@ int rcuja_shadow_set(struct cds_lfht *ht, 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 @@ -266,7 +279,16 @@ void free_shadow_node_and_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->node); + 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); } @@ -275,35 +297,42 @@ void free_shadow_node_and_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->node); + 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 cds_ja_inode *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 cds_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 cds_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,9 +351,20 @@ 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(); @@ -343,18 +385,37 @@ void rcuja_shadow_prune(struct cds_lfht *ht, 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) { - assert((flags & RCUJA_SHADOW_CLEAR_FREE_NODE) - && (flags & RCUJA_SHADOW_CLEAR_FREE_LOCK)); - flavor->update_call_rcu(&shadow_node->head, - free_shadow_node_and_node_and_lock); + 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); }