From f6e888c552945c36a78d445ee72f13e7c602a715 Mon Sep 17 00:00:00 2001 From: Mathieu Desnoyers Date: Tue, 9 Mar 2010 09:23:25 -0500 Subject: [PATCH] rcu rbtree: add redirections for prev/next walk We need to atomically make the parent/child relationship visible atomically to the rest of the world. Add redirections in the old nodes to the new nodes which atomically override the old nodes from the prev/next walk point of view. Note that it does not affect search, because these do not need to consider the parents. Signed-off-by: Mathieu Desnoyers --- urcu-rbtree.c | 67 ++++++++++++++++++++++++++++++++++++++++++++++++--- urcu-rbtree.h | 4 +-- 2 files changed, 65 insertions(+), 6 deletions(-) diff --git a/urcu-rbtree.c b/urcu-rbtree.c index 7292b97..e1df343 100644 --- a/urcu-rbtree.c +++ b/urcu-rbtree.c @@ -32,6 +32,7 @@ #include #include +#include #include #include @@ -97,16 +98,20 @@ struct rcu_rbtree_node *rcu_rbtree_max(struct rcu_rbtree_node *x, struct rcu_rbtree_node *rcu_rbtree_next(struct rcu_rbtree_node *x, rcu_rbtree_comp comp) { - struct rcu_rbtree_node *xr, *y; + struct rcu_rbtree_node *xr, *y, *yredir; x = rcu_dereference(x); if ((xr = rcu_dereference(x->right)) != &rcu_rbtree_nil) return rcu_rbtree_min(xr, comp); y = rcu_dereference(x->p); + while ((yredir = rcu_dereference(y->redir)) != NULL) + y = yredir; while (y != &rcu_rbtree_nil && x == rcu_dereference(y->right)) { x = y; y = rcu_dereference(y->p); + while ((yredir = rcu_dereference(y->redir)) != NULL) + y = yredir; } return y; } @@ -114,16 +119,20 @@ struct rcu_rbtree_node *rcu_rbtree_next(struct rcu_rbtree_node *x, struct rcu_rbtree_node *rcu_rbtree_prev(struct rcu_rbtree_node *x, rcu_rbtree_comp comp) { - struct rcu_rbtree_node *xl, *y; + struct rcu_rbtree_node *xl, *y, *yredir; x = rcu_dereference(x); if ((xl = rcu_dereference(x->left)) != &rcu_rbtree_nil) return rcu_rbtree_max(xl, comp); y = rcu_dereference(x->p); + while ((yredir = rcu_dereference(y->redir)) != NULL) + y = yredir; while (y != &rcu_rbtree_nil && x == rcu_dereference(y->left)) { x = y; y = rcu_dereference(y->p); + while ((yredir = rcu_dereference(y->redir)) != NULL) + y = yredir; } return y; } @@ -186,6 +195,18 @@ static struct rcu_rbtree_node *left_rotate(struct rcu_rbtree_node **root, */ smp_wmb(); + /* + * redirect old nodes to new. + */ + x->redir = xc; + y->redir = yc; + + /* + * Ensure that redirections are visible before updating external + * pointers. + */ + smp_wmb(); + /* Make parents point to the copies */ if (x->p == &rcu_rbtree_nil) _STORE_SHARED(*root, yc); @@ -272,6 +293,18 @@ static struct rcu_rbtree_node *right_rotate(struct rcu_rbtree_node **root, */ smp_wmb(); + /* + * redirect old nodes to new. + */ + x->redir = xc; + y->redir = yc; + + /* + * Ensure that redirections are visible before updating external + * pointers. + */ + smp_wmb(); + /* Make parents point to the copies */ if (x->p == &rcu_rbtree_nil) _STORE_SHARED(*root, yc); @@ -392,6 +425,7 @@ int rcu_rbtree_insert(struct rcu_rbtree_node **root, z->left = &rcu_rbtree_nil; z->right = &rcu_rbtree_nil; z->color = COLOR_RED; + z->redir = NULL; /* * Order stores to z (children/parents) before stores that will make it @@ -439,6 +473,17 @@ rcu_rbtree_transplant(struct rcu_rbtree_node **root, * that will make the copies visible to the rest of the tree. */ smp_wmb(); + + /* + * redirect old node to new. + */ + v->redir = vc; + + /* + * Ensure that redirections are visible before updating external + * pointers. + */ + smp_wmb(); } else { vc = &rcu_rbtree_nil; } @@ -471,13 +516,14 @@ static void rcu_rbtree_remove_fixup(struct rcu_rbtree_node **root, { while (x != *root && x->color == COLOR_BLACK) { if (x == x->p->left) { - struct rcu_rbtree_node *w; + struct rcu_rbtree_node *w, *t; w = x->p->right; if (w->color == COLOR_RED) { w->color == COLOR_BLACK; x->p->color = COLOR_RED; - left_rotate(root, x->p, rballoc, rbfree); + t = left_rotate(root, x->p, rballoc, rbfree); + assert(x->p->left == t->left); /* x is a left node, not copied by rotation */ w = x->p->right; } @@ -574,6 +620,19 @@ rcu_rbtree_remove_nonil(struct rcu_rbtree_node **root, */ smp_wmb(); + /* + * redirect old nodes to new. + */ + if (x != &rcu_rbtree_nil) + x->redir = xc; + y->redir = yc; + + /* + * Ensure that redirections are visible before updating external + * pointers. + */ + smp_wmb(); + /* Update external pointers */ if (y->p != z) { diff --git a/urcu-rbtree.h b/urcu-rbtree.h index 954d493..3477992 100644 --- a/urcu-rbtree.h +++ b/urcu-rbtree.h @@ -56,7 +56,7 @@ struct rcu_rbtree_node { void *key; /* internally reserved */ - struct rcu_rbtree_node *p, *left, *right; + struct rcu_rbtree_node *p, *left, *right, *redir; unsigned int color:1; }; @@ -101,7 +101,7 @@ int rcu_rbtree_remove(struct rcu_rbtree_node **root, /* RCU read-side */ /* - * Search key starting from node x. Returns NULL if not found. + * Search key starting from node x. Returns &rcu_rbtree_nil if not found. */ struct rcu_rbtree_node* rcu_rbtree_search(struct rcu_rbtree_node *x, void *key, rcu_rbtree_comp comp); -- 2.34.1