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 #include <string.h>
  37 #include <unistd.h>
  38
  39 #include <urcu/rcurbtree.h>
  40 #include <urcu-pointer.h>
  41 #include <urcu-call-rcu.h>
  42
  43 #ifdef DEBUG
  44 #define dbg_printf(args...)     printf(args)
  45 #else
  46 #define dbg_printf(args...)
  47 #endif
  48
  49 /*
  50  * Undefine this to enable the non-RCU rotate and transplant functions
  51  * (for debugging).
  52  */
  53 #define RBTREE_RCU_SUPPORT_ROTATE_LEFT
  54 #define RBTREE_RCU_SUPPORT_ROTATE_RIGHT
  55 #define RBTREE_RCU_SUPPORT_TRANSPLANT
  56
  57 #ifdef EXTRA_DEBUG
  58 static pthread_mutex_t test_mutex = PTHREAD_MUTEX_INITIALIZER;
  59 static pthread_mutex_t outer_mutex = PTHREAD_MUTEX_INITIALIZER;
  60
  61 static
  62 void lock_outer_mutex(void)
  63 {
  64         pthread_mutex_lock(&outer_mutex);
  65 }
  66
  67 static
  68 void unlock_outer_mutex(void)
  69 {
  70         pthread_mutex_unlock(&outer_mutex);
  71 }
  72
  73 static
  74 void lock_test_mutex(void)
  75 {
  76         pthread_mutex_lock(&test_mutex);
  77 }
  78
  79 static
  80 void unlock_test_mutex(void)
  81 {
  82         pthread_mutex_unlock(&test_mutex);
  83 }
  84 #endif
  85
  86 static
  87 void set_parent(struct rcu_rbtree_node *node,
  88                 struct rcu_rbtree_node *parent,
  89                 unsigned int pos)
  90 {
  91         node->parent = ((unsigned long) parent) | pos;
  92 }
  93
  94 static
  95 struct rcu_rbtree_node *get_parent(struct rcu_rbtree_node *node)
  96 {
  97         return (struct rcu_rbtree_node *) (node->parent & ~1UL);
  98 }
  99
 100 static
 101 unsigned int get_pos(struct rcu_rbtree_node *node)
 102 {
 103         return (unsigned int) (node->parent & 1UL);
 104 }
 105
 106 static
 107 struct rcu_rbtree_node *get_parent_and_pos(struct rcu_rbtree_node *node,
 108                                 unsigned int *pos)
 109 {
 110         unsigned long parent_pos = rcu_dereference(node->parent);
 111
 112         *pos = (unsigned int) (parent_pos & 1UL);
 113         return (struct rcu_rbtree_node *) (parent_pos & ~1UL);
 114 }
 115
 116 static
 117 void set_decay(struct rcu_rbtree_node *x, struct rcu_rbtree_node *xc)
 118 {
 119         x->decay_next = xc;
 120 }
 121
 122 static
 123 struct rcu_rbtree_node *get_decay(struct rcu_rbtree_node *x)
 124 {
 125         if (!x)
 126                 return NULL;
 127         while (x->decay_next)
 128                 x = x->decay_next;
 129         return x;
 130 }
 131
 132 static
 133 struct rcu_rbtree_node *is_decay(struct rcu_rbtree_node *x)
 134 {
 135         return x->decay_next;
 136 }
 137
 138 static
 139 struct rcu_rbtree_node *dup_decay_node(struct rcu_rbtree *rbtree,
 140                                 struct rcu_rbtree_node *x)
 141 {
 142         struct rcu_rbtree_node *xc;
 143
 144         if (rcu_rbtree_is_nil(x))
 145                 return x;
 146
 147         xc = rbtree->rballoc();
 148         memcpy(xc, x, sizeof(struct rcu_rbtree_node));
 149         xc->decay_next = NULL;
 150         set_decay(x, xc);
 151         call_rcu(&x->head, rbtree->rbfree);
 152         return xc;
 153 }
 154
 155 /*
 156  * TODO
 157  * Deal with memory allocation errors.
 158  * Can be ensured by reserving a pool of memory entries before doing the
 159  * insertion, which will have to be function of number of
 160  * transplantations/rotations required for the operation.
 161  */
 162
 163 #ifdef DEBUG
 164 static
 165 void show_tree(struct rcu_rbtree *rbtree)
 166 {
 167         struct rcu_rbtree_node *node;
 168
 169         node = rcu_rbtree_min(rbtree, rbtree->root);
 170         while (!rcu_rbtree_is_nil(node)) {
 171                 assert(!is_decay(node));
 172                 printf("{ 0x%lX p:%lX r:%lX l:%lX %s %s %s} ",
 173                         (unsigned long)node->key,
 174                         (unsigned long) get_parent(node)->key,
 175                         (unsigned long) node->right->key,
 176                         (unsigned long) node->left->key,
 177                         node->color ? "red" : "black",
 178                         get_pos(node) ? "right" : "left",
 179                         node->nil ? "nil" : "");
 180                 node = rcu_rbtree_next(rbtree, node);
 181         }
 182         printf("\n");
 183 }
 184 #else /* DEBUG */
 185 static
 186 void show_tree(struct rcu_rbtree *rbtree)
 187 {
 188 }
 189 #endif /* DEBUG */
 190
 191 static
 192 struct rcu_rbtree_node *make_nil(struct rcu_rbtree *rbtree)
 193 {
 194         return &rbtree->nil_node;
 195 }
 196
 197 /*
 198  * Iterative rbtree search.
 199  */
 200 struct rcu_rbtree_node* rcu_rbtree_search(struct rcu_rbtree *rbtree,
 201                                           struct rcu_rbtree_node *x,
 202                                           void *k)
 203 {
 204         x = rcu_dereference(x);
 205
 206         while (!rcu_rbtree_is_nil(x) && k != x->key) {
 207                 usleep(10);
 208                 if (rbtree->comp(k, x->key) < 0)
 209                         x = rcu_dereference(x->left);
 210                 else
 211                         x = rcu_dereference(x->right);
 212         }
 213         return x;
 214 }
 215
 216 static
 217 struct rcu_rbtree_node *rcu_rbtree_min_dup_decay(struct rcu_rbtree *rbtree,
 218                                                  struct rcu_rbtree_node *x,
 219                                                  struct rcu_rbtree_node **zr)
 220 {
 221         struct rcu_rbtree_node *xl;
 222
 223         x = rcu_dereference(x);
 224
 225         if (rcu_rbtree_is_nil(x)) {
 226                 *zr = x;
 227                 return x;
 228         } else
 229                 *zr = x = dup_decay_node(rbtree, x);
 230
 231         while (!rcu_rbtree_is_nil(xl = rcu_dereference(x->left))) {
 232                 x = dup_decay_node(rbtree, xl);
 233                 set_parent(x, get_decay(get_parent(x)), get_pos(x));
 234                 get_parent(x)->left = get_decay(get_parent(x)->left);
 235         }
 236         return x;
 237 }
 238
 239 static
 240 struct rcu_rbtree_node *rcu_rbtree_min_update_decay(struct rcu_rbtree *rbtree,
 241                                                     struct rcu_rbtree_node *x)
 242 {
 243         struct rcu_rbtree_node *xl;
 244
 245         x = rcu_dereference(x);
 246
 247         if (rcu_rbtree_is_nil(x))
 248                 return x;
 249         else {
 250                 set_parent(x->right, get_decay(get_parent(x->right)),
 251                            get_pos(x->right));
 252                 set_parent(x->left, get_decay(get_parent(x->left)),
 253                            get_pos(x->left));
 254         }
 255
 256         while (!rcu_rbtree_is_nil(xl = rcu_dereference(x->left))) {
 257                 x = xl;
 258                 set_parent(x->right, get_decay(get_parent(x->right)),
 259                            get_pos(x->right));
 260                 set_parent(x->left, get_decay(get_parent(x->left)),
 261                            get_pos(x->left));
 262         }
 263         return x;
 264 }
 265
 266 struct rcu_rbtree_node *rcu_rbtree_min(struct rcu_rbtree *rbtree,
 267                                        struct rcu_rbtree_node *x)
 268 {
 269         struct rcu_rbtree_node *xl;
 270
 271         x = rcu_dereference(x);
 272
 273         if (rcu_rbtree_is_nil(x))
 274                 return x;
 275
 276         while (!rcu_rbtree_is_nil(xl = rcu_dereference(x->left)))
 277                 x = xl;
 278         return x;
 279 }
 280
 281 struct rcu_rbtree_node *rcu_rbtree_max(struct rcu_rbtree *rbtree,
 282                                        struct rcu_rbtree_node *x)
 283 {
 284         struct rcu_rbtree_node *xr;
 285
 286         x = rcu_dereference(x);
 287
 288         if (rcu_rbtree_is_nil(x))
 289                 return x;
 290
 291         while (!rcu_rbtree_is_nil(xr = rcu_dereference(x->right)))
 292                 x = xr;
 293         return x;
 294 }
 295
 296 /*
 297  * FIXME:
 298  * Updates should wait for a grace period between update of the
 299  * redirect pointer and update of the parent child pointer. This is to make sure
 300  * that no reference to the old entry exist.
 301  */
 302
 303 /*
 304  * RCU read lock must be held across the next/prev calls to ensure validity of
 305  * the returned node.
 306  */
 307 struct rcu_rbtree_node *rcu_rbtree_next(struct rcu_rbtree *rbtree,
 308                                         struct rcu_rbtree_node *x)
 309 {
 310         struct rcu_rbtree_node *xr, *y;
 311         unsigned int x_pos;
 312
 313         x = rcu_dereference(x);
 314
 315         if (!rcu_rbtree_is_nil(xr = rcu_dereference(x->right)))
 316                 return rcu_rbtree_min(rbtree, xr);
 317         y = get_parent_and_pos(x, &x_pos);
 318         while (!rcu_rbtree_is_nil(y) && x_pos == IS_RIGHT) {
 319                 x = y;
 320                 y = get_parent_and_pos(y, &x_pos);
 321         }
 322         return y;
 323 }
 324
 325 struct rcu_rbtree_node *rcu_rbtree_prev(struct rcu_rbtree *rbtree,
 326                                         struct rcu_rbtree_node *x)
 327 {
 328         struct rcu_rbtree_node *xl, *y;
 329         unsigned int x_pos;
 330
 331         x = rcu_dereference(x);
 332
 333         if (!rcu_rbtree_is_nil(xl = rcu_dereference(x->left)))
 334                 return rcu_rbtree_max(rbtree, xl);
 335         y = get_parent_and_pos(x, &x_pos);
 336         while (!rcu_rbtree_is_nil(y) && x_pos == IS_LEFT) {
 337                 x = y;
 338                 y = get_parent_and_pos(y, &x_pos);
 339         }
 340         return y;
 341 }
 342
 343 /*
 344  * We have to ensure these assumptions are correct for prev/next
 345  * traversal:
 346  *
 347  * with x being a right child, the assumption that:
 348  *   get_parent(x)->right == x
 349  * or if x is a left child, the assumption that:
 350  *   get_parent(x)->left == x
 351  *
 352  * This explains why we have to allocate a vc copy of the node for left_rotate,
 353  * right_rotate and transplant operations.
 354  *
 355  * We always ensure that the right/left child and correct parent is set in the
 356  * node copies *before* we reparent the children and make the upper-level point
 357  * to the copy.
 358  */
 359
 360 /* RCU: copy x and y, atomically point to new versions. GC old. */
 361 /* Should be eventually followed by a cmm_smp_wmc() */
 362
 363 #ifdef RBTREE_RCU_SUPPORT_ROTATE_LEFT
 364
 365 static
 366 void left_rotate(struct rcu_rbtree *rbtree,
 367                  struct rcu_rbtree_node *x)
 368 {
 369         struct rcu_rbtree_node *y, *y_left, *x_p;
 370         unsigned int x_pos;
 371
 372         y = x->right;
 373         y_left = y->left;
 374
 375         /* Now operate on new copy, decay old versions */
 376         x = dup_decay_node(rbtree, x);
 377         y = dup_decay_node(rbtree, y);
 378         y_left = dup_decay_node(rbtree, y_left);
 379
 380         x_pos = get_pos(x);
 381         x_p = get_parent(x);
 382
 383         /* Internal node modifications */
 384         x->right = y_left;
 385         set_parent(y, get_parent(x), get_pos(x));
 386         set_parent(x, y, IS_LEFT);
 387         y->left = x;
 388         if (!rcu_rbtree_is_nil(y_left))
 389                 set_parent(y_left, x, IS_RIGHT);
 390
 391         cmm_smp_wmb();  /* write into node before publish */
 392
 393         /* External references update (visible by readers) */
 394         if (rcu_rbtree_is_nil(x_p))
 395                 _CMM_STORE_SHARED(rbtree->root, y);
 396         else if (x_pos == IS_LEFT)
 397                 _CMM_STORE_SHARED(x_p->left, y);
 398         else
 399                 _CMM_STORE_SHARED(x_p->right, y);
 400
 401         /* Point children to new copy (parent only used by updates/next/prev) */
 402         set_parent(x->left, get_decay(get_parent(x->left)),
 403                 get_pos(x->left));
 404         set_parent(y->right, get_decay(get_parent(y->right)),
 405                 get_pos(y->right));
 406         if (!rcu_rbtree_is_nil(y_left)) {
 407                 set_parent(y_left->right, get_decay(get_parent(y_left->right)),
 408                         get_pos(y_left->right));
 409                 set_parent(y_left->left, get_decay(get_parent(y_left->left)),
 410                         get_pos(y_left->left));
 411         }
 412
 413         /* Sanity checks */
 414         assert(y == rbtree->root || get_parent(y)->left == y || get_parent(y)->right == y);
 415         assert(x == rbtree->root || get_parent(x)->left == x || get_parent(x)->right == x);
 416         assert(rcu_rbtree_is_nil(x->right) || get_parent(x->right) == x);
 417         assert(rcu_rbtree_is_nil(x->left) || get_parent(x->left) == x);
 418         assert(rcu_rbtree_is_nil(y->right) || get_parent(y->right) == y);
 419         assert(rcu_rbtree_is_nil(y->left) || get_parent(y->left) == y);
 420         assert(!is_decay(rbtree->root));
 421         assert(!is_decay(x));
 422         assert(!is_decay(y));
 423         assert(!is_decay(x->right));
 424         assert(!is_decay(x->left));
 425         assert(!is_decay(y->right));
 426         assert(!is_decay(y->left));
 427 }
 428
 429 #else
 430
 431 /* non-rcu version */
 432 static
 433 void left_rotate(struct rcu_rbtree *rbtree,
 434                  struct rcu_rbtree_node *x)
 435 {
 436         struct rcu_rbtree_node *y;
 437
 438         lock_test_mutex();
 439         y = x->right;
 440         x->right = y->left;
 441         if (!rcu_rbtree_is_nil(y->left))
 442                 set_parent(y->left, x, IS_RIGHT);
 443         set_parent(y, get_parent(x), get_pos(x));
 444         if (rcu_rbtree_is_nil(get_parent(x)))
 445                 rbtree->root = y;
 446         else if (x == get_parent(x)->left) {
 447                 get_parent(x)->left = y;
 448         } else {
 449                 get_parent(x)->right = y;
 450         }
 451         y->left = x;
 452         set_parent(x, y, IS_LEFT);
 453         unlock_test_mutex();
 454 }
 455
 456 #endif
 457
 458 #ifdef RBTREE_RCU_SUPPORT_ROTATE_RIGHT
 459 static
 460 void right_rotate(struct rcu_rbtree *rbtree,
 461                   struct rcu_rbtree_node *x)
 462 {
 463         struct rcu_rbtree_node *y, *y_right, *x_p;
 464         unsigned int x_pos;
 465
 466         y = x->left;
 467         y_right = y->right;
 468
 469         /* Now operate on new copy, decay old versions */
 470         x = dup_decay_node(rbtree, x);
 471         y = dup_decay_node(rbtree, y);
 472         y_right = dup_decay_node(rbtree, y_right);
 473
 474         x_pos = get_pos(x);
 475         x_p = get_parent(x);
 476
 477         /* Internal node modifications */
 478         x->left = y_right;
 479         set_parent(y, get_parent(x), get_pos(x));
 480         set_parent(x, y, IS_RIGHT);
 481         y->right = x;
 482         if (!rcu_rbtree_is_nil(y_right))
 483                 set_parent(y_right, x, IS_LEFT);
 484
 485         cmm_smp_wmb();  /* write into node before publish */
 486
 487         /* External references update (visible by readers) */
 488         if (rcu_rbtree_is_nil(x_p))
 489                 _CMM_STORE_SHARED(rbtree->root, y);
 490         else if (x_pos == IS_RIGHT)
 491                 _CMM_STORE_SHARED(x_p->right, y);
 492         else
 493                 _CMM_STORE_SHARED(x_p->left, y);
 494
 495         /* Point children to new copy (parent only used by updates/next/prev) */
 496         set_parent(x->right, get_decay(get_parent(x->right)),
 497                 get_pos(x->right));
 498         set_parent(y->left, get_decay(get_parent(y->left)),
 499                 get_pos(y->left));
 500         if (!rcu_rbtree_is_nil(y_right)) {
 501                 set_parent(y_right->left, get_decay(get_parent(y_right->left)),
 502                         get_pos(y_right->left));
 503                 set_parent(y_right->right, get_decay(get_parent(y_right->right)),
 504                         get_pos(y_right->right));
 505         }
 506
 507         /* Sanity checks */
 508         assert(y == rbtree->root || get_parent(y)->right == y || get_parent(y)->left == y);
 509         assert(x == rbtree->root || get_parent(x)->right == x || get_parent(x)->left == x);
 510         assert(rcu_rbtree_is_nil(x->left) || get_parent(x->left) == x);
 511         assert(rcu_rbtree_is_nil(x->right) || get_parent(x->right) == x);
 512         assert(rcu_rbtree_is_nil(y->left) || get_parent(y->left) == y);
 513         assert(rcu_rbtree_is_nil(y->right) || get_parent(y->right) == y);
 514         assert(!is_decay(rbtree->root));
 515         assert(!is_decay(x));
 516         assert(!is_decay(y));
 517         assert(!is_decay(x->left));
 518         assert(!is_decay(x->right));
 519         assert(!is_decay(y->left));
 520         assert(!is_decay(y->right));
 521 }
 522
 523 #else
 524
 525 /* non-rcu version */
 526 static
 527 void right_rotate(struct rcu_rbtree *rbtree,
 528                   struct rcu_rbtree_node *x)
 529 {
 530         struct rcu_rbtree_node *y;
 531
 532         lock_test_mutex();
 533         y = x->left;
 534         x->left = y->right;
 535         if (!rcu_rbtree_is_nil(y->right))
 536                 set_parent(y->right, x, IS_LEFT);
 537         set_parent(y, get_parent(x), get_pos(x));
 538         if (rcu_rbtree_is_nil(get_parent(x)))
 539                 rbtree->root = y;
 540         else if (x == get_parent(x)->right) {
 541                 get_parent(x)->right = y;
 542         } else {
 543                 get_parent(x)->left = y;
 544         }
 545         y->right = x;
 546         set_parent(x, y, IS_RIGHT);
 547         unlock_test_mutex();
 548 }
 549
 550 #endif
 551
 552 static void rcu_rbtree_insert_fixup(struct rcu_rbtree *rbtree,
 553                                     struct rcu_rbtree_node *z)
 554 {
 555         struct rcu_rbtree_node *y;
 556
 557         dbg_printf("insert fixup %p\n", z->key);
 558         assert(!is_decay(rbtree->root));
 559
 560         while (get_parent(z)->color == COLOR_RED) {
 561                 if (get_parent(z) == get_parent(get_parent(z))->left) {
 562                         y = get_parent(get_parent(z))->right;
 563                         if (y->color == COLOR_RED) {
 564                                 get_parent(z)->color = COLOR_BLACK;
 565                                 y->color = COLOR_BLACK;
 566                                 get_parent(get_parent(z))->color = COLOR_RED;
 567                                 z = get_parent(get_parent(z));
 568                         } else {
 569                                 if (z == get_parent(z)->right) {
 570                                         z = get_parent(z);
 571                                         left_rotate(rbtree, z);
 572                                         z = get_decay(z);
 573                                         assert(!is_decay(rbtree->root));
 574                                 }
 575                                 get_parent(z)->color = COLOR_BLACK;
 576                                 get_parent(get_parent(z))->color = COLOR_RED;
 577                                 assert(!is_decay(z));
 578                                 assert(!is_decay(get_parent(z)));
 579                                 assert(!is_decay(get_parent(get_parent(z))));
 580                                 right_rotate(rbtree, get_parent(get_parent(z)));
 581                                 assert(!is_decay(z));
 582                                 assert(!is_decay(rbtree->root));
 583                         }
 584                 } else {
 585                         y = get_parent(get_parent(z))->left;
 586                         if (y->color == COLOR_RED) {
 587                                 get_parent(z)->color = COLOR_BLACK;
 588                                 y->color = COLOR_BLACK;
 589                                 get_parent(get_parent(z))->color = COLOR_RED;
 590                                 z = get_parent(get_parent(z));
 591                         } else {
 592                                 if (z == get_parent(z)->left) {
 593                                         z = get_parent(z);
 594                                         right_rotate(rbtree, z);
 595                                         z = get_decay(z);
 596                                         assert(!is_decay(rbtree->root));
 597                                 }
 598                                 get_parent(z)->color = COLOR_BLACK;
 599                                 get_parent(get_parent(z))->color = COLOR_RED;
 600                                 left_rotate(rbtree, get_parent(get_parent(z)));
 601                                 assert(!is_decay(z));
 602                                 assert(!is_decay(rbtree->root));
 603                         }
 604                 }
 605         }
 606         rbtree->root->color = COLOR_BLACK;
 607 }
 608
 609 /*
 610  * rcu_rbtree_insert - Insert a node in the RCU rbtree
 611  *
 612  * Returns 0 on success, or < 0 on error.
 613  */
 614 int rcu_rbtree_insert(struct rcu_rbtree *rbtree,
 615                       struct rcu_rbtree_node *z)
 616 {
 617         struct rcu_rbtree_node *x, *y;
 618
 619         dbg_printf("insert %p\n", z->key);
 620         assert(!is_decay(rbtree->root));
 621
 622         y = make_nil(rbtree);
 623         if (!rbtree->root)
 624                 rbtree->root = make_nil(rbtree);
 625         x = rbtree->root;
 626         while (!rcu_rbtree_is_nil(x)) {
 627                 y = x;
 628                 if (rbtree->comp(z->key, x->key) < 0)
 629                         x = x->left;
 630                 else
 631                         x = x->right;
 632         }
 633
 634         z->left = make_nil(rbtree);
 635         z->right = make_nil(rbtree);
 636         z->color = COLOR_RED;
 637         z->nil = 0;
 638         z->decay_next = NULL;
 639
 640         if (rcu_rbtree_is_nil(y))
 641                 set_parent(z, y, IS_RIGHT); /* pos arbitrary for root node */
 642         else if (rbtree->comp(z->key, y->key) < 0)
 643                 set_parent(z, y, IS_LEFT);
 644         else
 645                 set_parent(z, y, IS_RIGHT);
 646
 647         /*
 648          * Order stores to z (children/parents) before stores that will make it
 649          * visible to the rest of the tree.
 650          */
 651         cmm_smp_wmb();
 652
 653         if (rcu_rbtree_is_nil(y))
 654                 _CMM_STORE_SHARED(rbtree->root, z);
 655         else if (rbtree->comp(z->key, y->key) < 0)
 656                 _CMM_STORE_SHARED(y->left, z);
 657         else
 658                 _CMM_STORE_SHARED(y->right, z);
 659         rcu_rbtree_insert_fixup(rbtree, z);
 660         /*
 661          * Make sure to commit all _CMM_STORE_SHARED() for non-coherent caches.
 662          */
 663         cmm_smp_wmc();
 664         show_tree(rbtree);
 665
 666         return 0;
 667 }
 668
 669 /*
 670  * Transplant v into u position.
 671  */
 672
 673 #ifdef RBTREE_RCU_SUPPORT_TRANSPLANT
 674
 675 static
 676 void rcu_rbtree_transplant(struct rcu_rbtree *rbtree,
 677                         struct rcu_rbtree_node *u,
 678                         struct rcu_rbtree_node *v)
 679 {
 680         dbg_printf("transplant %p\n", v->key);
 681
 682         if (!rcu_rbtree_is_nil(v))
 683                 v = dup_decay_node(rbtree, v);
 684
 685         if (rcu_rbtree_is_nil(get_parent(u))) {
 686                 /* pos is arbitrary for root node */
 687                 set_parent(v, get_parent(u), IS_RIGHT);
 688                 cmm_smp_wmb();  /* write into node before publish */
 689                 _CMM_STORE_SHARED(rbtree->root, v);
 690         } else {
 691                 set_parent(v, get_parent(u), get_pos(u));
 692                 cmm_smp_wmb();  /* write into node before publish */
 693                 if (get_pos(u) == IS_LEFT)
 694                         _CMM_STORE_SHARED(get_parent(u)->left, v);
 695                 else
 696                         _CMM_STORE_SHARED(get_parent(u)->right, v);
 697         }
 698
 699         /* Point children to new copy (parent only used by updates/next/prev) */
 700         if (!rcu_rbtree_is_nil(v)) {
 701                 set_parent(v->right, get_decay(get_parent(v->right)),
 702                         get_pos(v->right));
 703                 set_parent(v->left, get_decay(get_parent(v->left)),
 704                         get_pos(v->left));
 705         }
 706         assert(!is_decay(rbtree->root));
 707 }
 708
 709 #else
 710
 711 /* Non-RCU version */
 712 static
 713 void rcu_rbtree_transplant(struct rcu_rbtree *rbtree,
 714                            struct rcu_rbtree_node *u,
 715                            struct rcu_rbtree_node *v)
 716 {
 717         dbg_printf("transplant %p\n", v->key);
 718
 719         lock_test_mutex();
 720         if (rcu_rbtree_is_nil(get_parent(u)))
 721                 rbtree->root = v;
 722         else if (u == get_parent(u)->left)
 723                 get_parent(u)->left = v;
 724         else
 725                 get_parent(u)->right = v;
 726         set_parent(v, get_parent(u), get_pos(u));
 727         unlock_test_mutex();
 728 }
 729
 730 #endif
 731
 732 static void rcu_rbtree_remove_fixup(struct rcu_rbtree *rbtree,
 733                                     struct rcu_rbtree_node *x)
 734 {
 735         dbg_printf("remove fixup %p\n", x->key);
 736
 737         while (x != rbtree->root && x->color == COLOR_BLACK) {
 738                 assert(!is_decay(get_parent(x)));
 739                 assert(!is_decay(get_parent(x)->left));
 740                 if (x == get_parent(x)->left) {
 741                         struct rcu_rbtree_node *w;
 742
 743                         w = get_parent(x)->right;
 744
 745                         if (w->color == COLOR_RED) {
 746                                 w->color = COLOR_BLACK;
 747                                 get_parent(x)->color = COLOR_RED;
 748                                 left_rotate(rbtree, get_parent(x));
 749                                 x = get_decay(x);
 750                                 assert(!is_decay(rbtree->root));
 751                                 w = get_parent(x)->right;
 752                         }
 753                         if (w->left->color == COLOR_BLACK
 754                             && w->right->color == COLOR_BLACK) {
 755                                 w->color = COLOR_RED;
 756                                 x = get_parent(x);
 757                                 assert(!is_decay(rbtree->root));
 758                                 assert(!is_decay(x));
 759                         } else {
 760                                 if (w->right->color == COLOR_BLACK) {
 761                                         w->left->color = COLOR_BLACK;
 762                                         w->color = COLOR_RED;
 763                                         right_rotate(rbtree, w);
 764                                         assert(!is_decay(rbtree->root));
 765                                         x = get_decay(x);
 766                                         w = get_parent(x)->right;
 767                                 }
 768                                 w->color = get_parent(x)->color;
 769                                 get_parent(x)->color = COLOR_BLACK;
 770                                 w->right->color = COLOR_BLACK;
 771                                 left_rotate(rbtree, get_parent(x));
 772                                 assert(!is_decay(rbtree->root));
 773                                 x = rbtree->root;
 774                         }
 775                 } else {
 776                         struct rcu_rbtree_node *w;
 777
 778                         w = get_parent(x)->left;
 779
 780                         if (w->color == COLOR_RED) {
 781                                 w->color = COLOR_BLACK;
 782                                 get_parent(x)->color = COLOR_RED;
 783                                 right_rotate(rbtree, get_parent(x));
 784                                 assert(!is_decay(rbtree->root));
 785                                 x = get_decay(x);
 786                                 w = get_parent(x)->left;
 787                         }
 788                         if (w->right->color == COLOR_BLACK
 789                             && w->left->color == COLOR_BLACK) {
 790                                 w->color = COLOR_RED;
 791                                 x = get_parent(x);
 792                                 assert(!is_decay(rbtree->root));
 793                                 assert(!is_decay(x));
 794                         } else {
 795                                 if (w->left->color == COLOR_BLACK) {
 796                                         w->right->color = COLOR_BLACK;
 797                                         w->color = COLOR_RED;
 798                                         left_rotate(rbtree, w);
 799                                         assert(!is_decay(rbtree->root));
 800                                         x = get_decay(x);
 801                                         w = get_parent(x)->left;
 802                                 }
 803                                 w->color = get_parent(x)->color;
 804                                 get_parent(x)->color = COLOR_BLACK;
 805                                 w->left->color = COLOR_BLACK;
 806                                 right_rotate(rbtree, get_parent(x));
 807                                 assert(!is_decay(rbtree->root));
 808                                 x = rbtree->root;
 809                         }
 810                 }
 811         }
 812         x->color = COLOR_BLACK;
 813 }
 814
 815 /*
 816  * Delete z. All non-copied children left/right positions are unchanged.
 817  */
 818 static
 819 void rcu_rbtree_remove_nonil(struct rcu_rbtree *rbtree,
 820                              struct rcu_rbtree_node *z,
 821                              struct rcu_rbtree_node *y)
 822 {
 823         struct rcu_rbtree_node *x;
 824
 825         dbg_printf("remove nonil %p\n", z->key);
 826         show_tree(rbtree);
 827
 828         assert(!is_decay(z));
 829         assert(!is_decay(y));
 830         assert(!is_decay(y->right));
 831         assert(!is_decay(get_parent(y)));
 832         x = y->right;
 833         assert(!is_decay(x));
 834         if (get_parent(y) == z) {
 835                 y = dup_decay_node(rbtree, y);
 836                 set_parent(x, y, get_pos(x));   /* parent for nil */
 837                 y->left = z->left;
 838                 rcu_rbtree_transplant(rbtree, z, y);
 839         } else {
 840                 struct rcu_rbtree_node *oy_right, *z_right;
 841
 842                 /*
 843                  * Need to make sure y is always visible by readers.
 844                  */
 845                 y = rcu_rbtree_min_dup_decay(rbtree, z->right, &z_right);
 846                 assert(!is_decay(y));
 847                 assert(!is_decay(z));
 848                 oy_right = y->right;
 849                 y->right = z_right;
 850                 set_parent(y->right, y, IS_RIGHT);
 851                 assert(!is_decay(z->left));
 852                 y->left = z->left;
 853                 assert(!is_decay(oy_right));
 854                 rcu_rbtree_transplant(rbtree, y, oy_right);
 855                 rcu_rbtree_transplant(rbtree, z, y);
 856                 /* Update children */
 857                 (void) rcu_rbtree_min_update_decay(rbtree, y->right);
 858         }
 859         y = get_decay(y);
 860         assert(!is_decay(z));
 861         assert(!is_decay(z->left));
 862         y->color = z->color;
 863         set_parent(y->left, y, IS_LEFT);
 864         set_parent(y->right, get_decay(get_parent(y->right)), IS_RIGHT);
 865         assert(!is_decay(y->left));
 866         assert(!is_decay(y->right));
 867 }
 868
 869 int rcu_rbtree_remove(struct rcu_rbtree *rbtree,
 870                       struct rcu_rbtree_node *z)
 871 {
 872         struct rcu_rbtree_node *x, *y;
 873         unsigned int y_original_color;
 874
 875         assert(!is_decay(rbtree->root));
 876         dbg_printf("remove %p\n", z->key);
 877         show_tree(rbtree);
 878
 879         assert(!is_decay(z));
 880         y = z;
 881         y_original_color = y->color;
 882
 883         if (rcu_rbtree_is_nil(z->left)) {
 884                 rcu_rbtree_transplant(rbtree, z, z->right);
 885                 assert(!is_decay(z));
 886                 x = get_decay(z->right);
 887                 show_tree(rbtree);
 888         } else if (rcu_rbtree_is_nil(z->right)) {
 889                 rcu_rbtree_transplant(rbtree, z, z->left);
 890                 assert(!is_decay(z));
 891                 x = get_decay(z->left);
 892                 show_tree(rbtree);
 893         } else {
 894                 y = rcu_rbtree_min(rbtree, z->right);
 895                 assert(!is_decay(y));
 896                 y_original_color = y->color;
 897                 x = y->right;
 898                 rcu_rbtree_remove_nonil(rbtree, z, y);
 899                 x = get_decay(x);
 900                 show_tree(rbtree);
 901         }
 902         if (y_original_color == COLOR_BLACK)
 903                 rcu_rbtree_remove_fixup(rbtree, x);
 904         show_tree(rbtree);
 905         /*
 906          * Commit all _CMM_STORE_SHARED().
 907          */
 908         cmm_smp_wmc();
 909
 910         return 0;
 911 }