From 3c6725959d949c0dcb9c4fc9d3276ae350cb21f5 Mon Sep 17 00:00:00 2001 From: Mathieu Desnoyers Date: Fri, 3 Jun 2011 10:02:59 -0400 Subject: [PATCH] rbtree API change: handle node memory allocation internally Signed-off-by: Mathieu Desnoyers --- tests/test_urcu_rbtree.c | 28 ++++++++++++---------------- urcu-rbtree.c | 24 +++++++++++++++++++----- urcu/rcurbtree.h | 14 ++++++-------- 3 files changed, 37 insertions(+), 29 deletions(-) diff --git a/tests/test_urcu_rbtree.c b/tests/test_urcu_rbtree.c index 170659f..ac6425f 100644 --- a/tests/test_urcu_rbtree.c +++ b/tests/test_urcu_rbtree.c @@ -72,16 +72,14 @@ static inline pid_t gettid(void) #include /* TODO: error handling testing for -ENOMEM */ -struct rcu_rbtree_node *rbtree_alloc(void) +void *rbtree_alloc(size_t size) { - return calloc(1, sizeof(struct rcu_rbtree_node)); + return malloc(size); } -void rbtree_free(struct rcu_head *head) +void rbtree_free(void *ptr) { - struct rcu_rbtree_node *node = - caa_container_of(head, struct rcu_rbtree_node, head); - free(node); + free(ptr); } int tree_comp(void *a, void *b) @@ -367,16 +365,16 @@ void *thr_writer(void *_count) rcu_copy_mutex_lock(); for (i = 0; i < NR_RAND; i++) { - node = rbtree_alloc(); //key[i] = (void *)(unsigned long)(rand() % 2048); key[i] = (void *)(unsigned long)(((unsigned long) rand() * 4) % 2048); //For more collisions //key[i] = (void *)(unsigned long)(rand() % 6); - node->begin = key[i]; + //node->begin = key[i]; //node->end = (void *)((unsigned long) key[i] + 1); - node->end = (void *)((unsigned long) key[i] + 4); + //node->end = (void *)((unsigned long) key[i] + 4); rcu_read_lock(); - rcu_rbtree_insert(&rbtree, node); + rcu_rbtree_insert(&rbtree, key[i], + (void *)((unsigned long) key[i] + 4)); rcu_read_unlock(); } rcu_copy_mutex_unlock(); @@ -406,7 +404,6 @@ void *thr_writer(void *_count) assert(!rcu_rbtree_is_nil(&rbtree, node)); rcu_rbtree_remove(&rbtree, node); rcu_read_unlock(); - call_rcu(&node->head, rbtree_free); } rcu_copy_mutex_unlock(); @@ -562,15 +559,15 @@ int main(int argc, char **argv) rcu_read_lock(); /* Insert items looked up by readers */ for (i = 0; i < global_items; i++) { - node = rbtree_alloc(); global_key[i] = (void *)(unsigned long)(((unsigned long) rand() * 4) % 2048); //global_key[i] = (void *)(unsigned long)(rand() % 2048); //For more collisions //global_key[i] = (void *)(unsigned long)(rand() % 6); - node->begin = global_key[i]; + //node->begin = global_key[i]; //node->end = (void *)((unsigned long) global_key[i] + 1); - node->end = (void *)((unsigned long) global_key[i] + 4); - rcu_rbtree_insert(&rbtree, node); + //node->end = (void *)((unsigned long) global_key[i] + 4); + rcu_rbtree_insert(&rbtree, global_key[i], + (void *)((unsigned long) global_key[i] + 4)); } rcu_read_unlock(); @@ -600,7 +597,6 @@ int main(int argc, char **argv) node = rcu_rbtree_search(&rbtree, rbtree.root, global_key[i]); assert(!rcu_rbtree_is_nil(&rbtree, node)); rcu_rbtree_remove(&rbtree, node); - call_rcu(&node->head, rbtree_free); } rcu_read_unlock(); rcu_unregister_thread(); diff --git a/urcu-rbtree.c b/urcu-rbtree.c index 2d170f2..1eb653f 100644 --- a/urcu-rbtree.c +++ b/urcu-rbtree.c @@ -240,6 +240,14 @@ struct rcu_rbtree_node *is_decay(struct rcu_rbtree_node *x) return x->decay_next; } +static +void _rcu_rbtree_free(struct rcu_head *head) +{ + struct rcu_rbtree_node *node = + caa_container_of(head, struct rcu_rbtree_node, head); + node->rbtree->rbfree(node); +} + static struct rcu_rbtree_node *dup_decay_node(struct rcu_rbtree *rbtree, struct rcu_rbtree_node *x) @@ -249,11 +257,11 @@ struct rcu_rbtree_node *dup_decay_node(struct rcu_rbtree *rbtree, if (rcu_rbtree_is_nil(rbtree, x)) return x; - xc = rbtree->rballoc(); - memcpy(xc, x, sizeof(struct rcu_rbtree_node)); + xc = rbtree->rballoc(sizeof(*xc)); + memcpy(xc, x, sizeof(*xc)); xc->decay_next = NULL; set_decay(x, xc); - call_rcu(&x->head, rbtree->rbfree); + call_rcu(&x->head, _rcu_rbtree_free); return xc; } @@ -931,9 +939,13 @@ static void rcu_rbtree_insert_fixup(struct rcu_rbtree *rbtree, * Returns 0 on success, or < 0 on error. */ int rcu_rbtree_insert(struct rcu_rbtree *rbtree, - struct rcu_rbtree_node *z) + void *begin, void *end) { - struct rcu_rbtree_node *x, *y; + struct rcu_rbtree_node *x, *y, *z; + + z = rbtree->rballoc(sizeof(*z)); + z->begin = begin; + z->end = end; dbg_printf("insert %p\n", z->begin); assert(!is_decay(rbtree->root)); @@ -953,6 +965,7 @@ int rcu_rbtree_insert(struct rcu_rbtree *rbtree, z->color = COLOR_RED; z->decay_next = NULL; z->max_end = z->end; + z->rbtree = rbtree; if (rcu_rbtree_is_nil(rbtree, y)) { set_parent(z, y, IS_RIGHT); /* pos arbitrary for root node */ @@ -1260,6 +1273,7 @@ int rcu_rbtree_remove(struct rcu_rbtree *rbtree, * Commit all _CMM_STORE_SHARED(). */ cmm_smp_wmc(); + call_rcu(&z->head, _rcu_rbtree_free); return 0; } diff --git a/urcu/rcurbtree.h b/urcu/rcurbtree.h index 23289ba..59fecc7 100644 --- a/urcu/rcurbtree.h +++ b/urcu/rcurbtree.h @@ -48,10 +48,10 @@ typedef int (*rcu_rbtree_comp)(void *a, void *b); /* - * Node allocation and deletion functions. + * Allocation and deletion functions. */ -typedef struct rcu_rbtree_node *(*rcu_rbtree_alloc)(void); -typedef void (*rcu_rbtree_free)(struct rcu_head *head); +typedef void *(*rcu_rbtree_alloc)(size_t size); +typedef void (*rcu_rbtree_free)(void *ptr); /* * struct rcu_rbtree_node must be aligned at least on 2 bytes. @@ -60,17 +60,16 @@ typedef void (*rcu_rbtree_free)(struct rcu_head *head); * Set "high" to key + 1 to insert single-value nodes. */ struct rcu_rbtree_node { - /* must be set upon insertion */ + /* internally reserved */ void *begin; /* Start of range (inclusive) */ void *end; /* range end (exclusive) */ - - /* internally reserved */ void *max_end; /* max range end of node and children */ /* parent uses low bit for "0 -> is left, 1 -> is right" */ unsigned long parent; /* _left and _right must be updated with set_left(), set_right() */ struct rcu_rbtree_node *_left, *_right; struct rcu_rbtree_node *decay_next; + struct rcu_rbtree *rbtree; struct rcu_head head; /* For delayed free */ unsigned int color:1; }; @@ -109,7 +108,7 @@ struct rcu_rbtree { * Caller must have exclusive write access and hold RCU read-side lock. */ int rcu_rbtree_insert(struct rcu_rbtree *rbtree, - struct rcu_rbtree_node *node); + void *begin, void *end); /* * Remove node from tree. @@ -120,7 +119,6 @@ int rcu_rbtree_insert(struct rcu_rbtree *rbtree, * "node". * Returns 0 on success. May fail with -ENOMEM. * - * The caller is responsible for freeing the node after a grace period. * Caller must have exclusive write access and hold RCU read-side lock * across "search" and "remove". */ -- 2.34.1