urcu-rbtree.c

   1 /*
   2  * urcu-rbtree.c
   3  *
   4  * Userspace RCU library - Red-Black Tree
   5  *
   6  * Copyright (c) 2010 Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
   7  *
   8  * This library is free software; you can redistribute it and/or
   9  * modify it under the terms of the GNU Lesser General Public
  10  * License as published by the Free Software Foundation; either
  11  * version 2.1 of the License, or (at your option) any later version.
  12  *
  13  * This library is distributed in the hope that it will be useful,
  14  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  15  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  16  * Lesser General Public License for more details.
  17  *
  18  * You should have received a copy of the GNU Lesser General Public
  19  * License along with this library; if not, write to the Free Software
  20  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
  21  *
  22  * Implementation of RCU-adapted data structures and operations based on the RB
  23  * tree algorithms found in chapter 12 of:
  24  *
  25  * Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and
  26  * Clifford Stein. Introduction to Algorithms, Third Edition. The MIT
  27  * Press, September 2009.
  28  */
  29
  30 #define _BSD_SOURCE
  31 #define _LGPL_SOURCE
  32
  33 #include <stdio.h>
  34 #include <pthread.h>
  35 #include <assert.h>
  36
  37 #include <urcu/rcurbtree.h>
  38 #include <urcu-pointer.h>
  39 #include <urcu-defer.h>
  40
  41 #define DEBUG
  42
  43 #ifdef DEBUG
  44 #define dbg_printf(args...)     printf(args)
  45 #else
  46 #define dbg_printf(args...)
  47 #endif
  48
  49 /*
  50  * TODO
  51  * Deal with memory allocation errors.
  52  * Can be ensured by reserving a pool of memory entries before doing the
  53  * insertion, which will have to be function of number of
  54  * transplantations/rotations required for the operation.
  55  */
  56
  57 static
  58 void show_tree(struct rcu_rbtree *rbtree)
  59 {
  60         struct rcu_rbtree_node *node;
  61
  62         node = rcu_rbtree_min(rbtree, rbtree->root);
  63         while (!rcu_rbtree_is_nil(node)) {
  64                 printf("{ 0x%lX p:%lX r:%lX l:%lX %s %s %s} ",
  65                         (unsigned long)node->key,
  66                         node->p->key,
  67                         node->right->key,
  68                         node->left->key,
  69                         node->color ? "red" : "black",
  70                         node->pos ? "right" : "left",
  71                         node->nil ? "nil" : "");
  72                 node = rcu_rbtree_next(rbtree, node);
  73         }
  74         printf("\n");
  75 }
  76
  77 static
  78 struct rcu_rbtree_node *make_nil(struct rcu_rbtree *rbtree)
  79 {
  80         return &rbtree->nil_node;
  81 }
  82
  83 /*
  84  * Iterative rbtree search.
  85  */
  86 struct rcu_rbtree_node* rcu_rbtree_search(struct rcu_rbtree *rbtree,
  87                                           struct rcu_rbtree_node *x,
  88                                           void *k)
  89 {
  90         x = rcu_dereference(x);
  91
  92         while (!rcu_rbtree_is_nil(x) && k != x->key) {
  93                 if (rbtree->comp(k, x->key) < 0)
  94                         x = rcu_dereference(x->left);
  95                 else
  96                         x = rcu_dereference(x->right);
  97         }
  98         return x;
  99 }
 100
 101 struct rcu_rbtree_node *rcu_rbtree_min(struct rcu_rbtree *rbtree,
 102                                        struct rcu_rbtree_node *x)
 103 {
 104         struct rcu_rbtree_node *xl;
 105
 106         x = rcu_dereference(x);
 107
 108         if (rcu_rbtree_is_nil(x))
 109                 return x;
 110
 111         while (!rcu_rbtree_is_nil(xl = rcu_dereference(x->left)))
 112                 x = xl;
 113         return x;
 114 }
 115
 116 struct rcu_rbtree_node *rcu_rbtree_max(struct rcu_rbtree *rbtree,
 117                                        struct rcu_rbtree_node *x)
 118 {
 119         struct rcu_rbtree_node *xr;
 120
 121         x = rcu_dereference(x);
 122
 123         if (rcu_rbtree_is_nil(x))
 124                 return x;
 125
 126         while (!rcu_rbtree_is_nil(xr = rcu_dereference(x->right)))
 127                 x = xr;
 128         return x;
 129 }
 130
 131 /*
 132  * FIXME:
 133  * Updates should wait for a grace period between update of the
 134  * redirect pointer and update of the parent child pointer. This is to make sure
 135  * that no reference to the old entry exist.
 136  */
 137
 138 /*
 139  * next and prev need to have mutex held to ensure that parent pointer is
 140  * coherent.
 141  */
 142 struct rcu_rbtree_node *rcu_rbtree_next(struct rcu_rbtree *rbtree,
 143                                         struct rcu_rbtree_node *x)
 144 {
 145         struct rcu_rbtree_node *xr, *y, *yr;
 146
 147         x = rcu_dereference(x);
 148
 149         if (!rcu_rbtree_is_nil(xr = rcu_dereference(x->right)))
 150                 return rcu_rbtree_min(rbtree, xr);
 151         y = rcu_dereference(x->p);
 152         while (!rcu_rbtree_is_nil(y) && x->pos == IS_RIGHT) {
 153                 x = y;
 154                 y = rcu_dereference(y->p);
 155         }
 156         return y;
 157 }
 158
 159 struct rcu_rbtree_node *rcu_rbtree_prev(struct rcu_rbtree *rbtree,
 160                                         struct rcu_rbtree_node *x)
 161 {
 162         struct rcu_rbtree_node *xl, *y, *yl;
 163
 164         x = rcu_dereference(x);
 165
 166         if (!rcu_rbtree_is_nil(xl = rcu_dereference(x->left)))
 167                 return rcu_rbtree_min(rbtree, xl);
 168         y = rcu_dereference(x->p);
 169         while (!rcu_rbtree_is_nil(y) && x->pos == IS_LEFT) {
 170                 x = y;
 171                 y = rcu_dereference(y->p);
 172         }
 173         return y;
 174 }
 175
 176 /*
 177  * We have to ensure these assumptions are correct for prev/next
 178  * traversal:
 179  *
 180  * with x being a right child, the assumption that:
 181  *   x->p->right == x
 182  * or if x is a left child, the assumption that:
 183  *   x->p->left == x
 184  *
 185  * This explains why we have to allocate a vc copy of the node for left_rotate,
 186  * right_rotate and transplant operations.
 187  *
 188  * We always ensure that the right/left child and correct parent is set in the
 189  * node copies *before* we reparent the children and make the upper-level point
 190  * to the copy.
 191  */
 192
 193 /* RCU: copy x and y, atomically point to new versions. GC old. */
 194 /* Should be eventually followed by a cmm_smp_wmc() */
 195 /* Returns the new x. Previous x->right references are changed to yc.
 196  * Previous y->left->right is changed to bc. */
 197
 198 static
 199 struct rcu_rbtree_node *left_rotate(struct rcu_rbtree *rbtree,
 200                         struct rcu_rbtree_node *x)
 201 {
 202         struct rcu_rbtree_node *y;
 203         struct rcu_rbtree_node *t;
 204
 205         t = x->p;
 206         y = x->right;
 207         x->right = y->left;
 208         if (!rcu_rbtree_is_nil(y->left)) {
 209                 y->left->p = x;
 210                 y->left->pos = IS_RIGHT;
 211         }
 212         y->p = x->p;
 213         if (rcu_rbtree_is_nil(x->p))
 214                 rbtree->root = y;
 215         else if (x == x->p->left) {
 216                 x->p->left = y;
 217                 y->pos = IS_LEFT;
 218         } else {
 219                 x->p->right = y;
 220                 y->pos = IS_RIGHT;
 221         }
 222         y->left = x;
 223         x->pos = IS_LEFT;
 224         x->p = y;
 225         return t;
 226 }
 227
 228 static
 229 struct rcu_rbtree_node *right_rotate(struct rcu_rbtree *rbtree,
 230                         struct rcu_rbtree_node *x)
 231 {
 232         struct rcu_rbtree_node *y;
 233         struct rcu_rbtree_node *t;
 234
 235         t = x->p;
 236         y = x->left;
 237         x->left = y->right;
 238         if (!rcu_rbtree_is_nil(y->right)) {
 239                 y->right->p = x;
 240                 y->right->pos = IS_LEFT;
 241         }
 242         y->p = x->p;
 243         if (rcu_rbtree_is_nil(x->p))
 244                 rbtree->root = y;
 245         else if (x == x->p->right) {
 246                 x->p->right = y;
 247                 y->pos = IS_RIGHT;
 248         } else {
 249                 x->p->left = y;
 250                 y->pos = IS_LEFT;
 251         }
 252         y->right = x;
 253         x->pos = IS_RIGHT;
 254         x->p = y;
 255         return t;
 256 }
 257
 258 static void rcu_rbtree_insert_fixup(struct rcu_rbtree *rbtree,
 259                                     struct rcu_rbtree_node *z)
 260 {
 261         struct rcu_rbtree_node *y;
 262
 263         dbg_printf("insert fixup %p\n", z->key);
 264
 265         while (z->p->color == COLOR_RED) {
 266                 if (z->p == z->p->p->left) {
 267                         y = z->p->p->right;
 268                         if (y->color == COLOR_RED) {
 269                                 z->p->color = COLOR_BLACK;
 270                                 y->color = COLOR_BLACK;
 271                                 z->p->p->color = COLOR_RED;
 272                                 z = z->p->p;
 273                         } else {
 274                                 if (z == z->p->right) {
 275                                         z = z->p;
 276                                         left_rotate(rbtree, z);
 277                                 }
 278                                 z->p->color = COLOR_BLACK;
 279                                 z->p->p->color = COLOR_RED;
 280                                 right_rotate(rbtree, z->p->p);
 281                         }
 282                 } else {
 283                         y = z->p->p->left;
 284                         if (y->color == COLOR_RED) {
 285                                 z->p->color = COLOR_BLACK;
 286                                 y->color = COLOR_BLACK;
 287                                 z->p->p->color = COLOR_RED;
 288                                 z = z->p->p;
 289                         } else {
 290                                 if (z == z->p->left) {
 291                                         z = z->p;
 292                                         right_rotate(rbtree, z);
 293                                 }
 294                                 z->p->color = COLOR_BLACK;
 295                                 z->p->p->color = COLOR_RED;
 296                                 left_rotate(rbtree, z->p->p);
 297                         }
 298                 }
 299         }
 300         rbtree->root->color = COLOR_BLACK;
 301 }
 302
 303 /*
 304  * rcu_rbtree_insert - Insert a node in the RCU rbtree
 305  *
 306  * Returns 0 on success, or < 0 on error.
 307  */
 308 int rcu_rbtree_insert(struct rcu_rbtree *rbtree,
 309                       struct rcu_rbtree_node *z)
 310 {
 311         struct rcu_rbtree_node *x, *y;
 312
 313         dbg_printf("insert %p\n", z->key);
 314
 315         y = make_nil(rbtree);
 316         if (!rbtree->root)
 317                 rbtree->root = make_nil(rbtree);
 318         x = rbtree->root;
 319         while (!rcu_rbtree_is_nil(x)) {
 320                 y = x;
 321                 if (rbtree->comp(z->key, x->key) < 0)
 322                         x = x->left;
 323                 else
 324                         x = x->right;
 325         }
 326
 327         z->p = y;
 328
 329         z->left = make_nil(rbtree);
 330         z->right = make_nil(rbtree);
 331         z->color = COLOR_RED;
 332         z->nil = 0;
 333
 334         if (rcu_rbtree_is_nil(y))
 335                 z->pos = IS_RIGHT;      /* arbitrary for root node */
 336         else if (rbtree->comp(z->key, y->key) < 0)
 337                 z->pos = IS_LEFT;
 338         else
 339                 z->pos = IS_RIGHT;
 340
 341         /*
 342          * Order stores to z (children/parents) before stores that will make it
 343          * visible to the rest of the tree.
 344          */
 345         cmm_smp_wmb();
 346
 347         if (rcu_rbtree_is_nil(y))
 348                 _CMM_STORE_SHARED(rbtree->root, z);
 349         else if (rbtree->comp(z->key, y->key) < 0)
 350                 _CMM_STORE_SHARED(y->left, z);
 351         else
 352                 _CMM_STORE_SHARED(y->right, z);
 353         rcu_rbtree_insert_fixup(rbtree, z);
 354         /*
 355          * Make sure to commit all _CMM_STORE_SHARED() for non-coherent caches.
 356          */
 357         cmm_smp_wmc();
 358         show_tree(rbtree);
 359
 360         return 0;
 361 }
 362
 363 /*
 364  * Transplant v into u position.
 365  * Returns new copy of v.
 366  */
 367 static struct rcu_rbtree_node *
 368 rcu_rbtree_transplant(struct rcu_rbtree *rbtree,
 369                       struct rcu_rbtree_node *u,
 370                       struct rcu_rbtree_node *v)
 371 {
 372         struct rcu_rbtree_node *vc;
 373
 374         dbg_printf("transplant %p\n", v->key);
 375
 376         if (rcu_rbtree_is_nil(u->p))
 377                 rbtree->root = v;
 378         else if (u == u->p->left) {
 379                 u->p->left = v;
 380                 v->pos = IS_LEFT;
 381         } else {
 382                 u->p->right = v;
 383                 v->pos = IS_RIGHT;
 384         }
 385         v->p = u->p;
 386         return v;
 387 }
 388
 389 static void rcu_rbtree_remove_fixup(struct rcu_rbtree *rbtree,
 390                                     struct rcu_rbtree_node *x)
 391 {
 392         dbg_printf("remove fixup %p\n", x->key);
 393
 394         while (x != rbtree->root && x->color == COLOR_BLACK) {
 395                 if (x == x->p->left) {
 396                         struct rcu_rbtree_node *w, *t;
 397
 398                         w = x->p->right;
 399
 400                         if (w->color == COLOR_RED) {
 401                                 w->color == COLOR_BLACK;
 402                                 x->p->color = COLOR_RED;
 403                                 t = left_rotate(rbtree, x->p);
 404                                 assert(x->p->left == t->left);
 405                                 /* x is a left node, not copied by rotation */
 406                                 w = x->p->right;
 407                         }
 408                         if (w->left->color == COLOR_BLACK
 409                             && w->right->color == COLOR_BLACK) {
 410                                 w->color = COLOR_RED;
 411                                 x = x->p;
 412                         } else {
 413                                 if (w->right->color == COLOR_BLACK) {
 414                                         w->left->color = COLOR_BLACK;
 415                                         w->color = COLOR_RED;
 416                                         right_rotate(rbtree, w);
 417                                         w = x->p->right;
 418                                 }
 419                                 w->color = x->p->color;
 420                                 x->p->color = COLOR_BLACK;
 421                                 w->right->color = COLOR_BLACK;
 422                                 left_rotate(rbtree, x->p);
 423                                 x = rbtree->root;
 424                         }
 425                 } else {
 426                         struct rcu_rbtree_node *w, *t;
 427
 428                         w = x->p->left;
 429
 430                         if (w->color == COLOR_RED) {
 431                                 w->color == COLOR_BLACK;
 432                                 x->p->color = COLOR_RED;
 433                                 t = right_rotate(rbtree, x->p);
 434                                 assert(x->p->right == t->right);
 435                                 /* x is a right node, not copied by rotation */
 436                                 w = x->p->left;
 437                         }
 438                         if (w->right->color == COLOR_BLACK
 439                             && w->left->color == COLOR_BLACK) {
 440                                 w->color = COLOR_RED;
 441                                 x = x->p;
 442                         } else {
 443                                 if (w->left->color == COLOR_BLACK) {
 444                                         w->right->color = COLOR_BLACK;
 445                                         w->color = COLOR_RED;
 446                                         left_rotate(rbtree, w);
 447                                         w = x->p->left;
 448                                 }
 449                                 w->color = x->p->color;
 450                                 x->p->color = COLOR_BLACK;
 451                                 w->left->color = COLOR_BLACK;
 452                                 right_rotate(rbtree, x->p);
 453                                 x = rbtree->root;
 454                         }
 455                 }
 456         }
 457         x->color = COLOR_BLACK;
 458 }
 459
 460 /*
 461  * Returns the new copy of y->right.
 462  * Delete z. All non-copied children left/right positions are unchanged. */
 463 static struct rcu_rbtree_node *
 464 rcu_rbtree_remove_nonil(struct rcu_rbtree *rbtree,
 465                         struct rcu_rbtree_node *z,
 466                         struct rcu_rbtree_node *y)
 467 {
 468         struct rcu_rbtree_node *x, *xc, *yc;
 469
 470         dbg_printf("remove nonil %p\n", z->key);
 471         show_tree(rbtree);
 472
 473         x = y->right;
 474         if (y->p == z)
 475                 x->p = y;
 476         else {
 477                 rcu_rbtree_transplant(rbtree, y, y->right);
 478                 y->right = z->right;
 479                 y->right->p = y;
 480         }
 481         rcu_rbtree_transplant(rbtree, z, y);
 482         y->left = z->left;
 483         y->left->p = y;
 484         y->color = z->color;
 485         return x;
 486 }
 487
 488 int rcu_rbtree_remove(struct rcu_rbtree *rbtree,
 489                       struct rcu_rbtree_node *z)
 490 {
 491         struct rcu_rbtree_node *x, *y;
 492         unsigned int y_original_color;
 493
 494         dbg_printf("remove %p\n", z->key);
 495         show_tree(rbtree);
 496
 497         y = z;
 498         y_original_color = y->color;
 499
 500         if (rcu_rbtree_is_nil(z->left)) {
 501                 x = rcu_rbtree_transplant(rbtree, z, z->right);
 502                 show_tree(rbtree);
 503         } else if (rcu_rbtree_is_nil(z->right)) {
 504                 x = rcu_rbtree_transplant(rbtree, z, z->left);
 505                 show_tree(rbtree);
 506         } else {
 507                 y = rcu_rbtree_min(rbtree, z->right);
 508                 y_original_color = y->color;
 509                 x = rcu_rbtree_remove_nonil(rbtree, z, y);
 510                 show_tree(rbtree);
 511         }
 512         if (y_original_color == COLOR_BLACK)
 513                 rcu_rbtree_remove_fixup(rbtree, x);
 514         show_tree(rbtree);
 515         /*
 516          * Commit all _CMM_STORE_SHARED().
 517          */
 518         cmm_smp_wmc();
 519
 520         return 0;
 521 }