From 7ba89e62d72f1ce6f677aeccb48c273197463951 Mon Sep 17 00:00:00 2001 From: Mathieu Desnoyers Date: Sun, 29 May 2011 12:38:13 -0400 Subject: [PATCH] Atomicize parent pointer and position update/read Signed-off-by: Mathieu Desnoyers --- urcu-rbtree.c | 335 +++++++++++++++++++++++++---------------------- urcu/rcurbtree.h | 9 +- 2 files changed, 186 insertions(+), 158 deletions(-) diff --git a/urcu-rbtree.c b/urcu-rbtree.c index b6e2e13..de2f911 100644 --- a/urcu-rbtree.c +++ b/urcu-rbtree.c @@ -85,6 +85,36 @@ void unlock_test_mutex(void) } #endif +static +void set_parent(struct rcu_rbtree_node *node, + struct rcu_rbtree_node *parent, + unsigned int pos) +{ + node->parent = ((unsigned long) parent) | pos; +} + +static +struct rcu_rbtree_node *get_parent(struct rcu_rbtree_node *node) +{ + return (struct rcu_rbtree_node *) (node->parent & ~1UL); +} + +static +unsigned int get_pos(struct rcu_rbtree_node *node) +{ + return (unsigned int) (node->parent & 1UL); +} + +static +struct rcu_rbtree_node *get_parent_and_pos(struct rcu_rbtree_node *node, + unsigned int *pos) +{ + unsigned long parent_pos = rcu_dereference(node->parent); + + *pos = (unsigned int) (parent_pos & 1UL); + return (struct rcu_rbtree_node *) (parent_pos & ~1UL); +} + static void set_decay(struct rcu_rbtree_node *x, struct rcu_rbtree_node *xc) { @@ -142,11 +172,11 @@ void show_tree(struct rcu_rbtree *rbtree) assert(!is_decay(node)); printf("{ 0x%lX p:%lX r:%lX l:%lX %s %s %s} ", (unsigned long)node->key, - (unsigned long) node->p->key, + (unsigned long) get_parent(node)->key, (unsigned long) node->right->key, (unsigned long) node->left->key, node->color ? "red" : "black", - node->pos ? "right" : "left", + get_pos(node) ? "right" : "left", node->nil ? "nil" : ""); node = rcu_rbtree_next(rbtree, node); } @@ -195,8 +225,8 @@ struct rcu_rbtree_node *rcu_rbtree_min_dup_decay(struct rcu_rbtree *rbtree, while (!rcu_rbtree_is_nil(xl = rcu_dereference(x->left))) { x = dup_decay_node(rbtree, xl); - x->p = get_decay(x->p); - x->p->left = get_decay(x->p->left); + set_parent(x, get_decay(get_parent(x)), get_pos(x)); + get_parent(x)->left = get_decay(get_parent(x)->left); } return x; } @@ -212,14 +242,18 @@ struct rcu_rbtree_node *rcu_rbtree_min_update_decay(struct rcu_rbtree *rbtree, if (rcu_rbtree_is_nil(x)) return x; else { - x->right->p = get_decay(x->right->p); - x->left->p = get_decay(x->left->p); + set_parent(x->right, get_decay(get_parent(x->right)), + get_pos(x->right)); + set_parent(x->left, get_decay(get_parent(x->left)), + get_pos(x->left)); } while (!rcu_rbtree_is_nil(xl = rcu_dereference(x->left))) { x = xl; - xl->right->p = get_decay(xl->right->p); - xl->left->p = get_decay(xl->left->p); + set_parent(x->right, get_decay(get_parent(x->right)), + get_pos(x->right)); + set_parent(x->left, get_decay(get_parent(x->left)), + get_pos(x->left)); } return x; } @@ -262,22 +296,23 @@ struct rcu_rbtree_node *rcu_rbtree_max(struct rcu_rbtree *rbtree, */ /* - * next and prev need to have mutex held to ensure that parent pointer is - * coherent. + * RCU read lock must be held across the next/prev calls to ensure validity of + * the returned node. */ struct rcu_rbtree_node *rcu_rbtree_next(struct rcu_rbtree *rbtree, struct rcu_rbtree_node *x) { struct rcu_rbtree_node *xr, *y; + unsigned int x_pos; x = rcu_dereference(x); if (!rcu_rbtree_is_nil(xr = rcu_dereference(x->right))) return rcu_rbtree_min(rbtree, xr); - y = rcu_dereference(x->p); - while (!rcu_rbtree_is_nil(y) && x->pos == IS_RIGHT) { + y = get_parent_and_pos(x, &x_pos); + while (!rcu_rbtree_is_nil(y) && x_pos == IS_RIGHT) { x = y; - y = rcu_dereference(y->p); + y = get_parent_and_pos(y, &x_pos); } return y; } @@ -286,15 +321,16 @@ struct rcu_rbtree_node *rcu_rbtree_prev(struct rcu_rbtree *rbtree, struct rcu_rbtree_node *x) { struct rcu_rbtree_node *xl, *y; + unsigned int x_pos; x = rcu_dereference(x); if (!rcu_rbtree_is_nil(xl = rcu_dereference(x->left))) return rcu_rbtree_min(rbtree, xl); - y = rcu_dereference(x->p); - while (!rcu_rbtree_is_nil(y) && x->pos == IS_LEFT) { + y = get_parent_and_pos(x, &x_pos); + while (!rcu_rbtree_is_nil(y) && x_pos == IS_LEFT) { x = y; - y = rcu_dereference(y->p); + y = get_parent_and_pos(y, &x_pos); } return y; } @@ -304,9 +340,9 @@ struct rcu_rbtree_node *rcu_rbtree_prev(struct rcu_rbtree *rbtree, * traversal: * * with x being a right child, the assumption that: - * x->p->right == x + * get_parent(x)->right == x * or if x is a left child, the assumption that: - * x->p->left == x + * get_parent(x)->left == x * * This explains why we have to allocate a vc copy of the node for left_rotate, * right_rotate and transplant operations. @@ -336,20 +372,16 @@ void left_rotate(struct rcu_rbtree *rbtree, y = dup_decay_node(rbtree, y); y_left = dup_decay_node(rbtree, y_left); - x_pos = x->pos; - x_p = x->p; + x_pos = get_pos(x); + x_p = get_parent(x); /* Internal node modifications */ x->right = y_left; - y->p = x->p; - y->pos = x->pos; - x->pos = IS_LEFT; + set_parent(y, get_parent(x), get_pos(x)); + set_parent(x, y, IS_LEFT); y->left = x; - x->p = y; - if (!rcu_rbtree_is_nil(y_left)) { - y_left->p = x; - y_left->pos = IS_RIGHT; - } + if (!rcu_rbtree_is_nil(y_left)) + set_parent(y_left, x, IS_RIGHT); cmm_smp_wmb(); /* write into node before publish */ @@ -362,20 +394,24 @@ void left_rotate(struct rcu_rbtree *rbtree, _CMM_STORE_SHARED(x_p->right, y); /* Point children to new copy (parent only used by updates/next/prev) */ - x->left->p = get_decay(x->left->p); - y->right->p = get_decay(y->right->p); + set_parent(x->left, get_decay(get_parent(x->left)), + get_pos(x->left)); + set_parent(y->right, get_decay(get_parent(y->right)), + get_pos(y->right)); if (!rcu_rbtree_is_nil(y_left)) { - y_left->right->p = get_decay(y_left->right->p); - y_left->left->p = get_decay(y_left->left->p); + set_parent(y_left->right, get_decay(get_parent(y_left->right)), + get_pos(y_left->right)); + set_parent(y_left->left, get_decay(get_parent(y_left->left)), + get_pos(y_left->left)); } /* Sanity checks */ - assert(y == rbtree->root || y->p->left == y || y->p->right == y); - assert(x == rbtree->root || x->p->left == x || x->p->right == x); - assert(rcu_rbtree_is_nil(x->right) || x->right->p == x); - assert(rcu_rbtree_is_nil(x->left) || x->left->p == x); - assert(rcu_rbtree_is_nil(y->right) || y->right->p == y); - assert(rcu_rbtree_is_nil(y->left) || y->left->p == y); + assert(y == rbtree->root || get_parent(y)->left == y || get_parent(y)->right == y); + assert(x == rbtree->root || get_parent(x)->left == x || get_parent(x)->right == x); + assert(rcu_rbtree_is_nil(x->right) || get_parent(x->right) == x); + assert(rcu_rbtree_is_nil(x->left) || get_parent(x->left) == x); + assert(rcu_rbtree_is_nil(y->right) || get_parent(y->right) == y); + assert(rcu_rbtree_is_nil(y->left) || get_parent(y->left) == y); assert(!is_decay(rbtree->root)); assert(!is_decay(x)); assert(!is_decay(y)); @@ -397,23 +433,18 @@ void left_rotate(struct rcu_rbtree *rbtree, lock_test_mutex(); y = x->right; x->right = y->left; - if (!rcu_rbtree_is_nil(y->left)) { - y->left->p = x; - y->left->pos = IS_RIGHT; - } - y->p = x->p; - if (rcu_rbtree_is_nil(x->p)) + if (!rcu_rbtree_is_nil(y->left)) + set_parent(y->left, x, IS_RIGHT); + set_parent(y, get_parent(x), get_pos(x)); + if (rcu_rbtree_is_nil(get_parent(x))) rbtree->root = y; - else if (x == x->p->left) { - x->p->left = y; - y->pos = IS_LEFT; + else if (x == get_parent(x)->left) { + get_parent(x)->left = y; } else { - x->p->right = y; - y->pos = IS_RIGHT; + get_parent(x)->right = y; } y->left = x; - x->pos = IS_LEFT; - x->p = y; + set_parent(x, y, IS_LEFT); unlock_test_mutex(); } @@ -435,20 +466,16 @@ void right_rotate(struct rcu_rbtree *rbtree, y = dup_decay_node(rbtree, y); y_right = dup_decay_node(rbtree, y_right); - x_pos = x->pos; - x_p = x->p; + x_pos = get_pos(x); + x_p = get_parent(x); /* Internal node modifications */ x->left = y_right; - y->p = x->p; - y->pos = x->pos; - x->pos = IS_RIGHT; + set_parent(y, get_parent(x), get_pos(x)); + set_parent(x, y, IS_RIGHT); y->right = x; - x->p = y; - if (!rcu_rbtree_is_nil(y_right)) { - y_right->p = x; - y_right->pos = IS_LEFT; - } + if (!rcu_rbtree_is_nil(y_right)) + set_parent(y_right, x, IS_LEFT); cmm_smp_wmb(); /* write into node before publish */ @@ -461,20 +488,24 @@ void right_rotate(struct rcu_rbtree *rbtree, _CMM_STORE_SHARED(x_p->left, y); /* Point children to new copy (parent only used by updates/next/prev) */ - x->right->p = get_decay(x->right->p); - y->left->p = get_decay(y->left->p); + set_parent(x->right, get_decay(get_parent(x->right)), + get_pos(x->right)); + set_parent(y->left, get_decay(get_parent(y->left)), + get_pos(y->left)); if (!rcu_rbtree_is_nil(y_right)) { - y_right->left->p = get_decay(y_right->left->p); - y_right->right->p = get_decay(y_right->right->p); + set_parent(y_right->left, get_decay(get_parent(y_right->left)), + get_pos(y_right->left)); + set_parent(y_right->right, get_decay(get_parent(y_right->right)), + get_pos(y_right->right)); } /* Sanity checks */ - assert(y == rbtree->root || y->p->right == y || y->p->left == y); - assert(x == rbtree->root || x->p->right == x || x->p->left == x); - assert(rcu_rbtree_is_nil(x->left) || x->left->p == x); - assert(rcu_rbtree_is_nil(x->right) || x->right->p == x); - assert(rcu_rbtree_is_nil(y->left) || y->left->p == y); - assert(rcu_rbtree_is_nil(y->right) || y->right->p == y); + assert(y == rbtree->root || get_parent(y)->right == y || get_parent(y)->left == y); + assert(x == rbtree->root || get_parent(x)->right == x || get_parent(x)->left == x); + assert(rcu_rbtree_is_nil(x->left) || get_parent(x->left) == x); + assert(rcu_rbtree_is_nil(x->right) || get_parent(x->right) == x); + assert(rcu_rbtree_is_nil(y->left) || get_parent(y->left) == y); + assert(rcu_rbtree_is_nil(y->right) || get_parent(y->right) == y); assert(!is_decay(rbtree->root)); assert(!is_decay(x)); assert(!is_decay(y)); @@ -496,23 +527,18 @@ void right_rotate(struct rcu_rbtree *rbtree, lock_test_mutex(); y = x->left; x->left = y->right; - if (!rcu_rbtree_is_nil(y->right)) { - y->right->p = x; - y->right->pos = IS_LEFT; - } - y->p = x->p; - if (rcu_rbtree_is_nil(x->p)) + if (!rcu_rbtree_is_nil(y->right)) + set_parent(y->right, x, IS_LEFT); + set_parent(y, get_parent(x), get_pos(x)); + if (rcu_rbtree_is_nil(get_parent(x))) rbtree->root = y; - else if (x == x->p->right) { - x->p->right = y; - y->pos = IS_RIGHT; + else if (x == get_parent(x)->right) { + get_parent(x)->right = y; } else { - x->p->left = y; - y->pos = IS_LEFT; + get_parent(x)->left = y; } y->right = x; - x->pos = IS_RIGHT; - x->p = y; + set_parent(x, y, IS_RIGHT); unlock_test_mutex(); } @@ -526,47 +552,47 @@ static void rcu_rbtree_insert_fixup(struct rcu_rbtree *rbtree, dbg_printf("insert fixup %p\n", z->key); assert(!is_decay(rbtree->root)); - while (z->p->color == COLOR_RED) { - if (z->p == z->p->p->left) { - y = z->p->p->right; + while (get_parent(z)->color == COLOR_RED) { + if (get_parent(z) == get_parent(get_parent(z))->left) { + y = get_parent(get_parent(z))->right; if (y->color == COLOR_RED) { - z->p->color = COLOR_BLACK; + get_parent(z)->color = COLOR_BLACK; y->color = COLOR_BLACK; - z->p->p->color = COLOR_RED; - z = z->p->p; + get_parent(get_parent(z))->color = COLOR_RED; + z = get_parent(get_parent(z)); } else { - if (z == z->p->right) { - z = z->p; + if (z == get_parent(z)->right) { + z = get_parent(z); left_rotate(rbtree, z); z = get_decay(z); assert(!is_decay(rbtree->root)); } - z->p->color = COLOR_BLACK; - z->p->p->color = COLOR_RED; + get_parent(z)->color = COLOR_BLACK; + get_parent(get_parent(z))->color = COLOR_RED; assert(!is_decay(z)); - assert(!is_decay(z->p)); - assert(!is_decay(z->p->p)); - right_rotate(rbtree, z->p->p); + assert(!is_decay(get_parent(z))); + assert(!is_decay(get_parent(get_parent(z)))); + right_rotate(rbtree, get_parent(get_parent(z))); assert(!is_decay(z)); assert(!is_decay(rbtree->root)); } } else { - y = z->p->p->left; + y = get_parent(get_parent(z))->left; if (y->color == COLOR_RED) { - z->p->color = COLOR_BLACK; + get_parent(z)->color = COLOR_BLACK; y->color = COLOR_BLACK; - z->p->p->color = COLOR_RED; - z = z->p->p; + get_parent(get_parent(z))->color = COLOR_RED; + z = get_parent(get_parent(z)); } else { - if (z == z->p->left) { - z = z->p; + if (z == get_parent(z)->left) { + z = get_parent(z); right_rotate(rbtree, z); z = get_decay(z); assert(!is_decay(rbtree->root)); } - z->p->color = COLOR_BLACK; - z->p->p->color = COLOR_RED; - left_rotate(rbtree, z->p->p); + get_parent(z)->color = COLOR_BLACK; + get_parent(get_parent(z))->color = COLOR_RED; + left_rotate(rbtree, get_parent(get_parent(z))); assert(!is_decay(z)); assert(!is_decay(rbtree->root)); } @@ -600,8 +626,6 @@ int rcu_rbtree_insert(struct rcu_rbtree *rbtree, x = x->right; } - z->p = y; - z->left = make_nil(rbtree); z->right = make_nil(rbtree); z->color = COLOR_RED; @@ -609,11 +633,11 @@ int rcu_rbtree_insert(struct rcu_rbtree *rbtree, z->decay_next = NULL; if (rcu_rbtree_is_nil(y)) - z->pos = IS_RIGHT; /* arbitrary for root node */ + set_parent(z, y, IS_RIGHT); /* pos arbitrary for root node */ else if (rbtree->comp(z->key, y->key) < 0) - z->pos = IS_LEFT; + set_parent(z, y, IS_LEFT); else - z->pos = IS_RIGHT; + set_parent(z, y, IS_RIGHT); /* * Order stores to z (children/parents) before stores that will make it @@ -653,24 +677,26 @@ void rcu_rbtree_transplant(struct rcu_rbtree *rbtree, if (!rcu_rbtree_is_nil(v)) v = dup_decay_node(rbtree, v); - if (rcu_rbtree_is_nil(u->p)) { - v->p = u->p; + if (rcu_rbtree_is_nil(get_parent(u))) { + /* pos is arbitrary for root node */ + set_parent(v, get_parent(u), IS_RIGHT); cmm_smp_wmb(); /* write into node before publish */ _CMM_STORE_SHARED(rbtree->root, v); } else { - v->pos = u->pos; - v->p = u->p; + set_parent(v, get_parent(u), get_pos(u)); cmm_smp_wmb(); /* write into node before publish */ - if (u->pos == IS_LEFT) - _CMM_STORE_SHARED(u->p->left, v); + if (get_pos(u) == IS_LEFT) + _CMM_STORE_SHARED(get_parent(u)->left, v); else - _CMM_STORE_SHARED(u->p->right, v); + _CMM_STORE_SHARED(get_parent(u)->right, v); } /* Point children to new copy (parent only used by updates/next/prev) */ if (!rcu_rbtree_is_nil(v)) { - v->right->p = get_decay(v->right->p); - v->left->p = get_decay(v->left->p); + set_parent(v->right, get_decay(get_parent(v->right)), + get_pos(v->right)); + set_parent(v->left, get_decay(get_parent(v->left)), + get_pos(v->left)); } assert(!is_decay(rbtree->root)); } @@ -686,16 +712,13 @@ void rcu_rbtree_transplant(struct rcu_rbtree *rbtree, dbg_printf("transplant %p\n", v->key); lock_test_mutex(); - if (rcu_rbtree_is_nil(u->p)) + if (rcu_rbtree_is_nil(get_parent(u))) rbtree->root = v; - else if (u == u->p->left) { - u->p->left = v; - v->pos = IS_LEFT; - } else { - u->p->right = v; - v->pos = IS_RIGHT; - } - v->p = u->p; + else if (u == get_parent(u)->left) + get_parent(u)->left = v; + else + get_parent(u)->right = v; + set_parent(v, get_parent(u), get_pos(u)); unlock_test_mutex(); } @@ -707,25 +730,25 @@ static void rcu_rbtree_remove_fixup(struct rcu_rbtree *rbtree, dbg_printf("remove fixup %p\n", x->key); while (x != rbtree->root && x->color == COLOR_BLACK) { - assert(!is_decay(x->p)); - assert(!is_decay(x->p->left)); - if (x == x->p->left) { + assert(!is_decay(get_parent(x))); + assert(!is_decay(get_parent(x)->left)); + if (x == get_parent(x)->left) { struct rcu_rbtree_node *w; - w = x->p->right; + w = get_parent(x)->right; if (w->color == COLOR_RED) { w->color = COLOR_BLACK; - x->p->color = COLOR_RED; - left_rotate(rbtree, x->p); + get_parent(x)->color = COLOR_RED; + left_rotate(rbtree, get_parent(x)); x = get_decay(x); assert(!is_decay(rbtree->root)); - w = x->p->right; + w = get_parent(x)->right; } if (w->left->color == COLOR_BLACK && w->right->color == COLOR_BLACK) { w->color = COLOR_RED; - x = x->p; + x = get_parent(x); assert(!is_decay(rbtree->root)); assert(!is_decay(x)); } else { @@ -735,32 +758,32 @@ static void rcu_rbtree_remove_fixup(struct rcu_rbtree *rbtree, right_rotate(rbtree, w); assert(!is_decay(rbtree->root)); x = get_decay(x); - w = x->p->right; + w = get_parent(x)->right; } - w->color = x->p->color; - x->p->color = COLOR_BLACK; + w->color = get_parent(x)->color; + get_parent(x)->color = COLOR_BLACK; w->right->color = COLOR_BLACK; - left_rotate(rbtree, x->p); + left_rotate(rbtree, get_parent(x)); assert(!is_decay(rbtree->root)); x = rbtree->root; } } else { struct rcu_rbtree_node *w; - w = x->p->left; + w = get_parent(x)->left; if (w->color == COLOR_RED) { w->color = COLOR_BLACK; - x->p->color = COLOR_RED; - right_rotate(rbtree, x->p); + get_parent(x)->color = COLOR_RED; + right_rotate(rbtree, get_parent(x)); assert(!is_decay(rbtree->root)); x = get_decay(x); - w = x->p->left; + w = get_parent(x)->left; } if (w->right->color == COLOR_BLACK && w->left->color == COLOR_BLACK) { w->color = COLOR_RED; - x = x->p; + x = get_parent(x); assert(!is_decay(rbtree->root)); assert(!is_decay(x)); } else { @@ -770,12 +793,12 @@ static void rcu_rbtree_remove_fixup(struct rcu_rbtree *rbtree, left_rotate(rbtree, w); assert(!is_decay(rbtree->root)); x = get_decay(x); - w = x->p->left; + w = get_parent(x)->left; } - w->color = x->p->color; - x->p->color = COLOR_BLACK; + w->color = get_parent(x)->color; + get_parent(x)->color = COLOR_BLACK; w->left->color = COLOR_BLACK; - right_rotate(rbtree, x->p); + right_rotate(rbtree, get_parent(x)); assert(!is_decay(rbtree->root)); x = rbtree->root; } @@ -800,12 +823,12 @@ void rcu_rbtree_remove_nonil(struct rcu_rbtree *rbtree, assert(!is_decay(z)); assert(!is_decay(y)); assert(!is_decay(y->right)); - assert(!is_decay(y->p)); + assert(!is_decay(get_parent(y))); x = y->right; assert(!is_decay(x)); - if (y->p == z) { + if (get_parent(y) == z) { y = dup_decay_node(rbtree, y); - x->p = y; + set_parent(x, y, get_pos(x)); /* parent for nil */ y->left = z->left; rcu_rbtree_transplant(rbtree, z, y); } else { @@ -819,7 +842,7 @@ void rcu_rbtree_remove_nonil(struct rcu_rbtree *rbtree, assert(!is_decay(z)); oy_right = y->right; y->right = z_right; - y->right->p = y; + set_parent(y->right, y, IS_RIGHT); assert(!is_decay(z->left)); y->left = z->left; assert(!is_decay(oy_right)); @@ -832,8 +855,8 @@ void rcu_rbtree_remove_nonil(struct rcu_rbtree *rbtree, assert(!is_decay(z)); assert(!is_decay(z->left)); y->color = z->color; - y->left->p = y; - y->right->p = get_decay(y->right->p); + set_parent(y->left, y, IS_LEFT); + set_parent(y->right, get_decay(get_parent(y->right)), IS_RIGHT); assert(!is_decay(y->left)); assert(!is_decay(y->right)); } diff --git a/urcu/rcurbtree.h b/urcu/rcurbtree.h index bb6f3d8..3296bca 100644 --- a/urcu/rcurbtree.h +++ b/urcu/rcurbtree.h @@ -53,16 +53,21 @@ typedef int (*rcu_rbtree_comp)(void *a, void *b); typedef struct rcu_rbtree_node *(*rcu_rbtree_alloc)(void); typedef void (*rcu_rbtree_free)(struct rcu_head *head); +/* + * struct rcu_rbtree_node must be aligned at least on 2 bytes. + * Lowest bit reserved for position (left/right) in pointer to parent. + */ struct rcu_rbtree_node { /* must be set upon insertion */ void *key; /* internally reserved */ - struct rcu_rbtree_node *p, *left, *right; + /* parent uses low bit for "0 -> is left, 1 -> is right" */ + unsigned long parent; + struct rcu_rbtree_node *left, *right; struct rcu_rbtree_node *decay_next; struct rcu_head head; /* For delayed free */ unsigned int color:1; - unsigned int pos:1; unsigned int nil:1; }; -- 2.34.1