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 #include <urcu/compiler.h>
  43
  44 #ifdef DEBUG
  45 #define dbg_printf(args...)     printf(args)
  46 #define dbg_usleep(usecs)       usleep(usecs)
  47 #else
  48 #define dbg_printf(args...)
  49 #define dbg_usleep(usecs)
  50 #endif
  51
  52 /*
  53  * Undefine this to enable the non-RCU rotate and transplant functions
  54  * (for debugging).
  55  */
  56 #define RBTREE_RCU_SUPPORT_ROTATE_LEFT
  57 #define RBTREE_RCU_SUPPORT_ROTATE_RIGHT
  58 #define RBTREE_RCU_SUPPORT_TRANSPLANT
  59
  60 #ifdef EXTRA_DEBUG
  61 static pthread_mutex_t test_mutex = PTHREAD_MUTEX_INITIALIZER;
  62 static pthread_mutex_t outer_mutex = PTHREAD_MUTEX_INITIALIZER;
  63
  64 static
  65 void lock_outer_mutex(void)
  66 {
  67         pthread_mutex_lock(&outer_mutex);
  68 }
  69
  70 static
  71 void unlock_outer_mutex(void)
  72 {
  73         pthread_mutex_unlock(&outer_mutex);
  74 }
  75
  76 static
  77 void lock_test_mutex(void)
  78 {
  79         pthread_mutex_lock(&test_mutex);
  80 }
  81
  82 static
  83 void unlock_test_mutex(void)
  84 {
  85         pthread_mutex_unlock(&test_mutex);
  86 }
  87 #endif
  88
  89 static
  90 void set_parent(struct rcu_rbtree_node *node,
  91                 struct rcu_rbtree_node *parent,
  92                 unsigned int pos)
  93 {
  94         _CMM_STORE_SHARED(node->parent, ((unsigned long) parent) | pos);
  95 }
  96
  97 static
  98 struct rcu_rbtree_node *get_parent(struct rcu_rbtree_node *node)
  99 {
 100         return (struct rcu_rbtree_node *) (node->parent & ~1UL);
 101 }
 102
 103 static
 104 unsigned int get_pos(struct rcu_rbtree_node *node)
 105 {
 106         return (unsigned int) (node->parent & 1UL);
 107 }
 108
 109 static
 110 struct rcu_rbtree_node *get_parent_and_pos(struct rcu_rbtree_node *node,
 111                                 unsigned int *pos)
 112 {
 113         unsigned long parent_pos = rcu_dereference(node->parent);
 114
 115         *pos = (unsigned int) (parent_pos & 1UL);
 116         return (struct rcu_rbtree_node *) (parent_pos & ~1UL);
 117 }
 118
 119 static
 120 void set_decay(struct rcu_rbtree_node *x, struct rcu_rbtree_node *xc)
 121 {
 122         x->decay_next = xc;
 123 }
 124
 125 static
 126 struct rcu_rbtree_node *get_decay(struct rcu_rbtree_node *x)
 127 {
 128         if (!x)
 129                 return NULL;
 130         while (x->decay_next)
 131                 x = x->decay_next;
 132         return x;
 133 }
 134
 135 static
 136 struct rcu_rbtree_node *is_decay(struct rcu_rbtree_node *x)
 137 {
 138         return x->decay_next;
 139 }
 140
 141 static
 142 struct rcu_rbtree_node *dup_decay_node(struct rcu_rbtree *rbtree,
 143                                 struct rcu_rbtree_node *x)
 144 {
 145         struct rcu_rbtree_node *xc;
 146
 147         if (rcu_rbtree_is_nil(rbtree, x))
 148                 return x;
 149
 150         xc = rbtree->rballoc();
 151         memcpy(xc, x, sizeof(struct rcu_rbtree_node));
 152         xc->decay_next = NULL;
 153         set_decay(x, xc);
 154         call_rcu(&x->head, rbtree->rbfree);
 155         return xc;
 156 }
 157
 158 /*
 159  * Info for range lookups:
 160  * Range lookup information is only valid when used when searching for
 161  * ranges. It should never be used in next/prev traversal because the
 162  * pointers to parents are not in sync with the parent vision of the
 163  * children range.
 164  */
 165 static
 166 void _set_left_dup_decay(struct rcu_rbtree *rbtree,
 167                         struct rcu_rbtree_node *node,
 168                         struct rcu_rbtree_node *left,
 169                         struct rcu_rbtree_node **top,
 170                         struct rcu_rbtree_node **top_child,
 171                         unsigned int *top_child_pos, int copy)
 172 {
 173         struct rcu_rbtree_node *first_node = node;      /* already a copy */
 174
 175         node->_left = left;
 176         do {
 177                 void *min_child_key;
 178
 179                 if (rcu_rbtree_is_nil(rbtree, left)) {
 180                         min_child_key = node->key;
 181                 } else {
 182                         min_child_key = left->min_child_key;
 183                         assert(rbtree->comp(left->key, left->min_child_key) >= 0);
 184                         assert(rbtree->comp(node->key, left->min_child_key) >= 0);
 185                 }
 186                 if (min_child_key != node->min_child_key) {
 187                         if (node != first_node) {
 188                                 if (copy) {
 189                                         node = dup_decay_node(rbtree, node);
 190                                         node->_left = left;
 191                                         set_parent(left, node, IS_LEFT);
 192                                 }
 193                         }
 194                         node->min_child_key = min_child_key;
 195                 } else {
 196                         if (node != first_node) {
 197                                 if (top)
 198                                         *top = node;
 199                                 if (top_child)
 200                                         *top_child = left;
 201                                 if (top_child_pos)
 202                                         *top_child_pos = get_pos(left);
 203                         } else {
 204                                 if (top)
 205                                         *top = get_parent(node);
 206                                 if (top_child)
 207                                         *top_child = node;
 208                                 if (top_child_pos)
 209                                         *top_child_pos = get_pos(node);
 210                         }
 211                         return;
 212                 }
 213                 left = node;
 214         } while (get_pos(node) == IS_LEFT
 215                  && !rcu_rbtree_is_nil(rbtree, node = get_parent(node)));
 216
 217         if (rcu_rbtree_is_nil(rbtree, node)) {
 218                 if (top)
 219                         *top = node;
 220                 if (top_child)
 221                         *top_child = left;
 222                 if (top_child_pos)
 223                         *top_child_pos = IS_LEFT;       /* arbitrary */
 224         } else {
 225                 assert(get_pos(node) == IS_RIGHT);
 226                 if (top)
 227                         *top = get_parent(node);
 228                 if (top_child)
 229                         *top_child = node;
 230                 if (top_child_pos)
 231                         *top_child_pos = IS_RIGHT;
 232         }
 233 }
 234
 235 static
 236 void set_left_dup_decay(struct rcu_rbtree *rbtree,
 237                         struct rcu_rbtree_node *node,
 238                         struct rcu_rbtree_node *left,
 239                         struct rcu_rbtree_node **top,
 240                         struct rcu_rbtree_node **top_child,
 241                         unsigned int *top_child_pos)
 242 {
 243         _set_left_dup_decay(rbtree, node, left, top, top_child,
 244                             top_child_pos, 1);
 245 }
 246
 247 static
 248 void set_left_update_decay(struct rcu_rbtree *rbtree, struct rcu_rbtree_node *node,
 249               struct rcu_rbtree_node *left)
 250 {
 251         struct rcu_rbtree_node *first_node = node;      /* already a copy */
 252
 253         do {
 254                 if (node != first_node) {
 255                         set_parent(node->_right,
 256                                 get_decay(get_parent(node->_right)), IS_RIGHT);
 257                 }
 258         } while (get_pos(node) == IS_LEFT
 259                  && !rcu_rbtree_is_nil(rbtree, node = get_parent(node)));
 260 }
 261
 262 static
 263 void set_right_dup_decay(struct rcu_rbtree *rbtree, struct rcu_rbtree_node *node,
 264                         struct rcu_rbtree_node *right,
 265                         struct rcu_rbtree_node **top,
 266                         struct rcu_rbtree_node **top_child,
 267                         unsigned int *top_child_pos)
 268 {
 269         struct rcu_rbtree_node *first_node = node;      /* already a copy */
 270
 271         node->_right = right;
 272         do {
 273                 void *max_child_key;
 274
 275                 if (rcu_rbtree_is_nil(rbtree, right)) {
 276                         max_child_key = node->key;
 277                 } else {
 278                         max_child_key = right->max_child_key;
 279                         assert(rbtree->comp(right->key, right->max_child_key) <= 0);
 280                         assert(rbtree->comp(node->key, right->max_child_key) <= 0);
 281                 }
 282                 if (max_child_key != node->max_child_key) {
 283                         if (node != first_node) {
 284                                 node = dup_decay_node(rbtree, node);
 285                                 node->_right = right;
 286                                 set_parent(right, node, IS_RIGHT);
 287                         }
 288                         node->max_child_key = max_child_key;
 289                 } else {
 290                         if (node != first_node) {
 291                                 if (top)
 292                                         *top = node;
 293                                 if (top_child)
 294                                         *top_child = right;
 295                                 if (top_child_pos)
 296                                         *top_child_pos = get_pos(right);
 297                         } else {
 298                                 if (top)
 299                                         *top = get_parent(node);
 300                                 if (top_child)
 301                                         *top_child = node;
 302                                 if (top_child_pos)
 303                                         *top_child_pos = get_pos(node);
 304                         }
 305                         return;
 306                 }
 307                 right = node;
 308         } while (get_pos(node) == IS_RIGHT
 309                  && !rcu_rbtree_is_nil(rbtree, node = get_parent(node)));
 310
 311         if (rcu_rbtree_is_nil(rbtree, node)) {
 312                 if (top)
 313                         *top = node;
 314                 if (top_child)
 315                         *top_child = right;
 316                 if (top_child_pos)
 317                         *top_child_pos = IS_RIGHT;      /* arbitrary */
 318         } else {
 319                 assert(get_pos(node) == IS_LEFT);
 320                 if (top)
 321                         *top = get_parent(node);
 322                 if (top_child)
 323                         *top_child = node;
 324                 if (top_child_pos)
 325                         *top_child_pos = IS_LEFT;
 326         }
 327 }
 328
 329 static
 330 void set_right_update_decay(struct rcu_rbtree *rbtree, struct rcu_rbtree_node *node,
 331               struct rcu_rbtree_node *right)
 332 {
 333         struct rcu_rbtree_node *first_node = node;      /* already a copy */
 334
 335         do {
 336                 if (node != first_node) {
 337                         set_parent(node->_left,
 338                                 get_decay(get_parent(node->_left)), IS_LEFT);
 339                 }
 340         } while (get_pos(node) == IS_RIGHT
 341                  && !rcu_rbtree_is_nil(rbtree, node = get_parent(node)));
 342 }
 343
 344 /*
 345  * TODO
 346  * Deal with memory allocation errors.
 347  * Can be ensured by reserving a pool of memory entries before doing the
 348  * insertion, which will have to be function of number of
 349  * transplantations/rotations required for the operation.
 350  */
 351
 352 #ifdef DEBUG
 353 static
 354 void show_tree(struct rcu_rbtree *rbtree)
 355 {
 356         struct rcu_rbtree_node *node;
 357
 358         node = rcu_rbtree_min(rbtree, rbtree->root);
 359         while (!rcu_rbtree_is_nil(rbtree, node)) {
 360                 assert(!is_decay(node));
 361                 printf("{ 0x%lX p:%lX r:%lX l:%lX %s %s %s} ",
 362                         (unsigned long)node->key,
 363                         (unsigned long) get_parent(node)->key,
 364                         (unsigned long) node->_right->key,
 365                         (unsigned long) node->_left->key,
 366                         node->color ? "red" : "black",
 367                         get_pos(node) ? "right" : "left",
 368                         node->nil ? "nil" : "");
 369                 node = rcu_rbtree_next(rbtree, node);
 370         }
 371         printf("\n");
 372 }
 373 #else /* DEBUG */
 374 static
 375 void show_tree(struct rcu_rbtree *rbtree)
 376 {
 377 }
 378 #endif /* DEBUG */
 379
 380 static
 381 struct rcu_rbtree_node *make_nil(struct rcu_rbtree *rbtree)
 382 {
 383         return &rbtree->nil_node;
 384 }
 385
 386 /*
 387  * Iterative rbtree search.
 388  */
 389 struct rcu_rbtree_node *rcu_rbtree_search(struct rcu_rbtree *rbtree,
 390                                           struct rcu_rbtree_node *x,
 391                                           void *k)
 392 {
 393         x = rcu_dereference(x);
 394         int comp;
 395
 396         while (!rcu_rbtree_is_nil(rbtree, x) && (comp = rbtree->comp(k, x->key)) != 0) {
 397                 dbg_usleep(10);
 398                 if (comp < 0)
 399                         x = rcu_dereference(x->_left);
 400                 else
 401                         x = rcu_dereference(x->_right);
 402         }
 403         return x;
 404 }
 405
 406 struct rcu_rbtree_node *rcu_rbtree_search_min(struct rcu_rbtree *rbtree,
 407                                           struct rcu_rbtree_node *x,
 408                                           void *range_low, void *range_high)
 409 {
 410         struct rcu_rbtree_node *xl;
 411         x = rcu_dereference(x);
 412
 413         dbg_printf("start search min x %lx low %lx high %lx\n",
 414                 (unsigned long) x->key,
 415                 (unsigned long) range_low, (unsigned long) range_high);
 416         while (!rcu_rbtree_is_nil(rbtree, x)) {
 417                 dbg_usleep(10);
 418                 xl = rcu_dereference(x->_left);
 419                 dbg_printf("search min x %lx\n", (unsigned long) x->key);
 420                 dbg_printf("search min xl %lx\n", (unsigned long) xl->key);
 421                 if (!rcu_rbtree_is_nil(rbtree, xl)
 422                     && (rbtree->comp(xl->max_child_key, range_low) >= 0
 423                         || rbtree->comp(xl->key, range_low) == 0)) {
 424                         dbg_printf("go left\n");
 425                         x = xl;
 426                 } else if (rbtree->comp(x->key, range_low) >= 0
 427                            && rbtree->comp(x->key, range_high) <= 0) {
 428                         dbg_printf("got it!\n");
 429                         break;
 430                 } else if (rbtree->comp(range_low, x->min_child_key) >= 0) {
 431                         dbg_printf("go right\n");
 432                         x = rcu_dereference(x->_right);
 433                 } else {
 434                         dbg_printf("not found!\n");
 435                         x = make_nil(rbtree);
 436                 }
 437         }
 438         return x;
 439 }
 440
 441 struct rcu_rbtree_node *rcu_rbtree_search_max(struct rcu_rbtree *rbtree,
 442                                           struct rcu_rbtree_node *x,
 443                                           void *range_low, void *range_high)
 444 {
 445         struct rcu_rbtree_node *xr;
 446         x = rcu_dereference(x);
 447
 448         dbg_printf("start search max x %lx low %lx high %lx\n",
 449                 (unsigned long) x->key,
 450                 (unsigned long) range_low, (unsigned long) range_high);
 451         while (!rcu_rbtree_is_nil(rbtree, x)) {
 452                 dbg_usleep(10);
 453                 xr = rcu_dereference(x->_right);
 454                 dbg_printf("search max x %lx\n", (unsigned long) x->key);
 455                 dbg_printf("search max xl %lx\n", (unsigned long) xr->key);
 456                 if (!rcu_rbtree_is_nil(rbtree, xr)
 457                     && (rbtree->comp(xr->min_child_key, range_high) <= 0
 458                         || rbtree->comp(xr->key, range_high) == 0)) {
 459                         dbg_printf("go right\n");
 460                         x = xr;
 461                 } else if (rbtree->comp(x->key, range_low) >= 0
 462                            && rbtree->comp(x->key, range_high) <= 0) {
 463                         dbg_printf("got it!\n");
 464                         break;
 465                 } else if (rbtree->comp(range_high, x->max_child_key) <= 0) {
 466                         dbg_printf("go left\n");
 467                         x = rcu_dereference(x->_left);
 468                 } else {
 469                         dbg_printf("not found!\n");
 470                         x = make_nil(rbtree);
 471                 }
 472         }
 473         return x;
 474 }
 475
 476 static
 477 struct rcu_rbtree_node *rcu_rbtree_min_dup_decay(struct rcu_rbtree *rbtree,
 478                                                  struct rcu_rbtree_node *x,
 479                                                  struct rcu_rbtree_node **zr)
 480 {
 481         struct rcu_rbtree_node *xl;
 482
 483         x = rcu_dereference(x);
 484
 485         if (rcu_rbtree_is_nil(rbtree, x)) {
 486                 *zr = x;
 487                 return x;
 488         } else
 489                 *zr = x = dup_decay_node(rbtree, x);
 490
 491         while (!rcu_rbtree_is_nil(rbtree, xl = rcu_dereference(x->_left))) {
 492                 x = dup_decay_node(rbtree, xl);
 493                 set_parent(x, get_decay(get_parent(x)), get_pos(x));
 494                 get_parent(x)->_left = get_decay(get_parent(x)->_left);
 495         }
 496         return x;
 497 }
 498
 499 static
 500 struct rcu_rbtree_node *rcu_rbtree_min_update_decay(struct rcu_rbtree *rbtree,
 501                                                     struct rcu_rbtree_node *x)
 502 {
 503         struct rcu_rbtree_node *xl;
 504
 505         x = rcu_dereference(x);
 506
 507         if (rcu_rbtree_is_nil(rbtree, x))
 508                 return x;
 509         else {
 510                 set_parent(x->_right, get_decay(get_parent(x->_right)),
 511                            get_pos(x->_right));
 512                 set_parent(x->_left, get_decay(get_parent(x->_left)),
 513                            get_pos(x->_left));
 514         }
 515
 516         while (!rcu_rbtree_is_nil(rbtree, xl = rcu_dereference(x->_left))) {
 517                 x = xl;
 518                 set_parent(x->_right, get_decay(get_parent(x->_right)),
 519                            get_pos(x->_right));
 520                 set_parent(x->_left, get_decay(get_parent(x->_left)),
 521                            get_pos(x->_left));
 522         }
 523         return x;
 524 }
 525
 526 struct rcu_rbtree_node *rcu_rbtree_min(struct rcu_rbtree *rbtree,
 527                                        struct rcu_rbtree_node *x)
 528 {
 529         struct rcu_rbtree_node *xl;
 530
 531         x = rcu_dereference(x);
 532
 533         if (rcu_rbtree_is_nil(rbtree, x))
 534                 return x;
 535
 536         while (!rcu_rbtree_is_nil(rbtree, xl = rcu_dereference(x->_left)))
 537                 x = xl;
 538         return x;
 539 }
 540
 541 struct rcu_rbtree_node *rcu_rbtree_max(struct rcu_rbtree *rbtree,
 542                                        struct rcu_rbtree_node *x)
 543 {
 544         struct rcu_rbtree_node *xr;
 545
 546         x = rcu_dereference(x);
 547
 548         if (rcu_rbtree_is_nil(rbtree, x))
 549                 return x;
 550
 551         while (!rcu_rbtree_is_nil(rbtree, xr = rcu_dereference(x->_right)))
 552                 x = xr;
 553         return x;
 554 }
 555
 556 /*
 557  * FIXME:
 558  * Updates should wait for a grace period between update of the
 559  * redirect pointer and update of the parent child pointer. This is to make sure
 560  * that no reference to the old entry exist.
 561  */
 562
 563 /*
 564  * RCU read lock must be held across the next/prev calls to ensure validity of
 565  * the returned node.
 566  */
 567 struct rcu_rbtree_node *rcu_rbtree_next(struct rcu_rbtree *rbtree,
 568                                         struct rcu_rbtree_node *x)
 569 {
 570         struct rcu_rbtree_node *xr, *y;
 571         unsigned int x_pos;
 572
 573         x = rcu_dereference(x);
 574
 575         if (!rcu_rbtree_is_nil(rbtree, xr = rcu_dereference(x->_right)))
 576                 return rcu_rbtree_min(rbtree, xr);
 577         y = get_parent_and_pos(x, &x_pos);
 578         while (!rcu_rbtree_is_nil(rbtree, y) && x_pos == IS_RIGHT) {
 579                 x = y;
 580                 y = get_parent_and_pos(y, &x_pos);
 581         }
 582         return y;
 583 }
 584
 585 struct rcu_rbtree_node *rcu_rbtree_prev(struct rcu_rbtree *rbtree,
 586                                         struct rcu_rbtree_node *x)
 587 {
 588         struct rcu_rbtree_node *xl, *y;
 589         unsigned int x_pos;
 590
 591         x = rcu_dereference(x);
 592
 593         if (!rcu_rbtree_is_nil(rbtree, xl = rcu_dereference(x->_left)))
 594                 return rcu_rbtree_max(rbtree, xl);
 595         y = get_parent_and_pos(x, &x_pos);
 596         while (!rcu_rbtree_is_nil(rbtree, y) && x_pos == IS_LEFT) {
 597                 x = y;
 598                 y = get_parent_and_pos(y, &x_pos);
 599         }
 600         return y;
 601 }
 602
 603 /*
 604  * We have to ensure these assumptions are correct for prev/next
 605  * traversal:
 606  *
 607  * with x being a right child, the assumption that:
 608  *   get_parent(x)->_right == x
 609  * or if x is a left child, the assumption that:
 610  *   get_parent(x)->_left == x
 611  *
 612  * This explains why we have to allocate a vc copy of the node for left_rotate,
 613  * right_rotate and transplant operations.
 614  *
 615  * We always ensure that the right/left child and correct parent is set in the
 616  * node copies *before* we reparent the children and make the upper-level point
 617  * to the copy.
 618  */
 619
 620 /* RCU: copy x and y, atomically point to new versions. GC old. */
 621 /* Should be eventually followed by a cmm_smp_wmc() */
 622
 623 #ifdef RBTREE_RCU_SUPPORT_ROTATE_LEFT
 624
 625 static
 626 void left_rotate(struct rcu_rbtree *rbtree,
 627                  struct rcu_rbtree_node *x)
 628 {
 629         struct rcu_rbtree_node *y, *y_left, *top, *top_child;
 630         unsigned int top_child_pos;
 631
 632         y = x->_right;
 633         y_left = y->_left;
 634
 635         /* Now operate on new copy, decay old versions */
 636         x = dup_decay_node(rbtree, x);
 637         y = dup_decay_node(rbtree, y);
 638         y_left = dup_decay_node(rbtree, y_left);
 639
 640         /* Internal node modifications */
 641         set_parent(y, get_parent(x), get_pos(x));
 642         set_parent(x, y, IS_LEFT);
 643         set_left_dup_decay(rbtree, y, x, &top, &top_child, &top_child_pos);
 644         set_right_dup_decay(rbtree, x, y_left, NULL, NULL, NULL);
 645         assert(!is_decay(top));
 646         assert(!is_decay(top_child));
 647
 648         if (!rcu_rbtree_is_nil(rbtree, y_left))
 649                 set_parent(y_left, x, IS_RIGHT);
 650
 651         cmm_smp_wmb();  /* write into node before publish */
 652
 653         /* External references update (visible by readers) */
 654         if (rcu_rbtree_is_nil(rbtree, top))
 655                 _CMM_STORE_SHARED(rbtree->root, top_child);
 656         else if (top_child_pos == IS_LEFT)
 657                 _CMM_STORE_SHARED(top->_left, top_child);
 658         else
 659                 _CMM_STORE_SHARED(top->_right, top_child);
 660
 661         /* Point children to new copy (parent only used by updates/next/prev) */
 662         set_parent(x->_left, get_decay(get_parent(x->_left)),
 663                 get_pos(x->_left));
 664         set_parent(y->_right, get_decay(get_parent(y->_right)),
 665                 get_pos(y->_right));
 666         if (!rcu_rbtree_is_nil(rbtree, y_left)) {
 667                 set_parent(y_left->_right,
 668                         get_decay(get_parent(y_left->_right)),
 669                         get_pos(y_left->_right));
 670                 set_parent(y_left->_left,
 671                         get_decay(get_parent(y_left->_left)),
 672                         get_pos(y_left->_left));
 673         }
 674         set_left_update_decay(rbtree, y, x);
 675
 676         /* Sanity checks */
 677         assert(y == rbtree->root || get_parent(y)->_left == y
 678                 || get_parent(y)->_right == y);
 679         assert(x == rbtree->root || get_parent(x)->_left == x
 680                 || get_parent(x)->_right == x);
 681         assert(rcu_rbtree_is_nil(rbtree, x->_right) || get_parent(x->_right) == x);
 682         assert(rcu_rbtree_is_nil(rbtree, x->_left) || get_parent(x->_left) == x);
 683         assert(rcu_rbtree_is_nil(rbtree, y->_right) || get_parent(y->_right) == y);
 684         assert(rcu_rbtree_is_nil(rbtree, y->_left) || get_parent(y->_left) == y);
 685         assert(!is_decay(rbtree->root));
 686         assert(!is_decay(x));
 687         assert(!is_decay(y));
 688         assert(!is_decay(x->_right));
 689         assert(!is_decay(x->_left));
 690         assert(!is_decay(y->_right));
 691         assert(!is_decay(y->_left));
 692 }
 693
 694 #else
 695
 696 /* non-rcu version */
 697 static
 698 void left_rotate(struct rcu_rbtree *rbtree,
 699                  struct rcu_rbtree_node *x)
 700 {
 701         struct rcu_rbtree_node *y;
 702
 703         lock_test_mutex();
 704         y = x->_right;
 705         x->_right = y->_left;
 706         if (!rcu_rbtree_is_nil(rbtree, y->_left))
 707                 set_parent(y->_left, x, IS_RIGHT);
 708         set_parent(y, get_parent(x), get_pos(x));
 709         if (rcu_rbtree_is_nil(rbtree, get_parent(x)))
 710                 rbtree->root = y;
 711         else if (x == get_parent(x)->_left) {
 712                 get_parent(x)->_left = y;
 713         } else {
 714                 get_parent(x)->_right = y;
 715         }
 716         y->_left = x;
 717         set_parent(x, y, IS_LEFT);
 718         unlock_test_mutex();
 719 }
 720
 721 #endif
 722
 723 #ifdef RBTREE_RCU_SUPPORT_ROTATE_RIGHT
 724 static
 725 void right_rotate(struct rcu_rbtree *rbtree,
 726                   struct rcu_rbtree_node *x)
 727 {
 728         struct rcu_rbtree_node *y, *y_right, *top, *top_child;
 729         unsigned int top_child_pos;
 730
 731         y = x->_left;
 732         y_right = y->_right;
 733
 734         /* Now operate on new copy, decay old versions */
 735         x = dup_decay_node(rbtree, x);
 736         y = dup_decay_node(rbtree, y);
 737         y_right = dup_decay_node(rbtree, y_right);
 738
 739         /* Internal node modifications */
 740         set_parent(y, get_parent(x), get_pos(x));
 741         set_parent(x, y, IS_RIGHT);
 742         set_right_dup_decay(rbtree, y, x, &top, &top_child, &top_child_pos);
 743         set_left_dup_decay(rbtree, x, y_right, NULL, NULL, NULL);
 744         assert(!is_decay(top));
 745         assert(!is_decay(top_child));
 746
 747         if (!rcu_rbtree_is_nil(rbtree, y_right))
 748                 set_parent(y_right, x, IS_LEFT);
 749
 750         cmm_smp_wmb();  /* write into node before publish */
 751
 752         /* External references update (visible by readers) */
 753         if (rcu_rbtree_is_nil(rbtree, top))
 754                 _CMM_STORE_SHARED(rbtree->root, top_child);
 755         else if (top_child_pos == IS_RIGHT)
 756                 _CMM_STORE_SHARED(top->_right, top_child);
 757         else
 758                 _CMM_STORE_SHARED(top->_left, top_child);
 759
 760         /* Point children to new copy (parent only used by updates/next/prev) */
 761         set_parent(x->_right, get_decay(get_parent(x->_right)),
 762                 get_pos(x->_right));
 763         set_parent(y->_left, get_decay(get_parent(y->_left)),
 764                 get_pos(y->_left));
 765         if (!rcu_rbtree_is_nil(rbtree, y_right)) {
 766                 set_parent(y_right->_left,
 767                         get_decay(get_parent(y_right->_left)),
 768                         get_pos(y_right->_left));
 769                 set_parent(y_right->_right,
 770                         get_decay(get_parent(y_right->_right)),
 771                         get_pos(y_right->_right));
 772         }
 773         set_right_update_decay(rbtree, y, x);
 774
 775
 776         /* Sanity checks */
 777         assert(y == rbtree->root || get_parent(y)->_right == y
 778                 || get_parent(y)->_left == y);
 779         assert(x == rbtree->root || get_parent(x)->_right == x
 780                 || get_parent(x)->_left == x);
 781         assert(rcu_rbtree_is_nil(rbtree, x->_left) || get_parent(x->_left) == x);
 782         assert(rcu_rbtree_is_nil(rbtree, x->_right) || get_parent(x->_right) == x);
 783         assert(rcu_rbtree_is_nil(rbtree, y->_left) || get_parent(y->_left) == y);
 784         assert(rcu_rbtree_is_nil(rbtree, y->_right) || get_parent(y->_right) == y);
 785         assert(!is_decay(rbtree->root));
 786         assert(!is_decay(x));
 787         assert(!is_decay(y));
 788         assert(!is_decay(x->_left));
 789         assert(!is_decay(x->_right));
 790         assert(!is_decay(y->_left));
 791         assert(!is_decay(y->_right));
 792 }
 793
 794 #else
 795
 796 /* non-rcu version */
 797 static
 798 void right_rotate(struct rcu_rbtree *rbtree,
 799                   struct rcu_rbtree_node *x)
 800 {
 801         struct rcu_rbtree_node *y;
 802
 803         lock_test_mutex();
 804         y = x->_left;
 805         x->_left = y->_right;
 806         if (!rcu_rbtree_is_nil(rbtree, y->_right))
 807                 set_parent(y->_right, x, IS_LEFT);
 808         set_parent(y, get_parent(x), get_pos(x));
 809         if (rcu_rbtree_is_nil(rbtree, get_parent(x)))
 810                 rbtree->root = y;
 811         else if (x == get_parent(x)->_right) {
 812                 get_parent(x)->_right = y;
 813         } else {
 814                 get_parent(x)->_left = y;
 815         }
 816         y->_right = x;
 817         set_parent(x, y, IS_RIGHT);
 818         unlock_test_mutex();
 819 }
 820
 821 #endif
 822
 823 static void rcu_rbtree_insert_fixup(struct rcu_rbtree *rbtree,
 824                                     struct rcu_rbtree_node *z)
 825 {
 826         struct rcu_rbtree_node *y;
 827
 828         dbg_printf("insert fixup %p\n", z->key);
 829         assert(!is_decay(rbtree->root));
 830
 831         while (get_parent(z)->color == COLOR_RED) {
 832                 if (get_parent(z) == get_parent(get_parent(z))->_left) {
 833                         y = get_parent(get_parent(z))->_right;
 834                         if (y->color == COLOR_RED) {
 835                                 get_parent(z)->color = COLOR_BLACK;
 836                                 y->color = COLOR_BLACK;
 837                                 get_parent(get_parent(z))->color = COLOR_RED;
 838                                 z = get_parent(get_parent(z));
 839                         } else {
 840                                 if (z == get_parent(z)->_right) {
 841                                         z = get_parent(z);
 842                                         left_rotate(rbtree, z);
 843                                         z = get_decay(z);
 844                                         assert(!is_decay(rbtree->root));
 845                                 }
 846                                 get_parent(z)->color = COLOR_BLACK;
 847                                 get_parent(get_parent(z))->color = COLOR_RED;
 848                                 assert(!is_decay(z));
 849                                 assert(!is_decay(get_parent(z)));
 850                                 assert(!is_decay(get_parent(get_parent(z))));
 851                                 right_rotate(rbtree, get_parent(get_parent(z)));
 852                                 assert(!is_decay(z));
 853                                 assert(!is_decay(rbtree->root));
 854                         }
 855                 } else {
 856                         y = get_parent(get_parent(z))->_left;
 857                         if (y->color == COLOR_RED) {
 858                                 get_parent(z)->color = COLOR_BLACK;
 859                                 y->color = COLOR_BLACK;
 860                                 get_parent(get_parent(z))->color = COLOR_RED;
 861                                 z = get_parent(get_parent(z));
 862                         } else {
 863                                 if (z == get_parent(z)->_left) {
 864                                         z = get_parent(z);
 865                                         right_rotate(rbtree, z);
 866                                         z = get_decay(z);
 867                                         assert(!is_decay(rbtree->root));
 868                                 }
 869                                 get_parent(z)->color = COLOR_BLACK;
 870                                 get_parent(get_parent(z))->color = COLOR_RED;
 871                                 left_rotate(rbtree, get_parent(get_parent(z)));
 872                                 assert(!is_decay(z));
 873                                 assert(!is_decay(rbtree->root));
 874                         }
 875                 }
 876         }
 877         rbtree->root->color = COLOR_BLACK;
 878 }
 879
 880 /*
 881  * rcu_rbtree_insert - Insert a node in the RCU rbtree
 882  *
 883  * Returns 0 on success, or < 0 on error.
 884  */
 885 int rcu_rbtree_insert(struct rcu_rbtree *rbtree,
 886                       struct rcu_rbtree_node *z)
 887 {
 888         struct rcu_rbtree_node *x, *y, *top, *top_child;
 889         unsigned int top_child_pos;
 890
 891         dbg_printf("insert %p\n", z->key);
 892         assert(!is_decay(rbtree->root));
 893
 894         y = make_nil(rbtree);
 895         x = rbtree->root;
 896         while (!rcu_rbtree_is_nil(rbtree, x)) {
 897                 y = x;
 898                 if (rbtree->comp(z->key, x->key) < 0)
 899                         x = x->_left;
 900                 else
 901                         x = x->_right;
 902         }
 903
 904         z->_left = make_nil(rbtree);
 905         z->_right = make_nil(rbtree);
 906         z->min_child_key = z->key;
 907         z->max_child_key = z->key;
 908         z->color = COLOR_RED;
 909         z->decay_next = NULL;
 910
 911         if (rcu_rbtree_is_nil(rbtree, y))
 912                 set_parent(z, y, IS_RIGHT); /* pos arbitrary for root node */
 913         else if (rbtree->comp(z->key, y->key) < 0)
 914                 set_parent(z, y, IS_LEFT);
 915         else
 916                 set_parent(z, y, IS_RIGHT);
 917
 918         if (rcu_rbtree_is_nil(rbtree, y)) {
 919                 /*
 920                  * Order stores to z (children/parents) before stores
 921                  * that will make it visible to the rest of the tree.
 922                  */
 923                 cmm_smp_wmb();
 924                 _CMM_STORE_SHARED(rbtree->root, z);
 925         } else if (rbtree->comp(z->key, y->key) < 0) {
 926                 set_left_dup_decay(rbtree, y, z, &top, &top_child,
 927                                 &top_child_pos);
 928                 /*
 929                  * Order stores to z (children/parents) before stores
 930                  * that will make it visible to the rest of the tree.
 931                  */
 932                 cmm_smp_wmb();
 933                 if (rcu_rbtree_is_nil(rbtree, top))
 934                         _CMM_STORE_SHARED(rbtree->root, top_child);
 935                 else if (top_child_pos == IS_LEFT)
 936                         _CMM_STORE_SHARED(top->_left, top_child);
 937                 else
 938                         _CMM_STORE_SHARED(top->_right, top_child);
 939                 set_left_update_decay(rbtree, y, z);
 940         } else {
 941                 set_right_dup_decay(rbtree, y, z, &top, &top_child,
 942                                 &top_child_pos);
 943                 /*
 944                  * Order stores to z (children/parents) before stores
 945                  * that will make it visible to the rest of the tree.
 946                  */
 947                 cmm_smp_wmb();
 948                 if (rcu_rbtree_is_nil(rbtree, top))
 949                         _CMM_STORE_SHARED(rbtree->root, top_child);
 950                 else if (top_child_pos == IS_LEFT)
 951                         _CMM_STORE_SHARED(top->_left, top_child);
 952                 else
 953                         _CMM_STORE_SHARED(top->_right, top_child);
 954                 set_right_update_decay(rbtree, y, z);
 955         }
 956         rcu_rbtree_insert_fixup(rbtree, z);
 957         /*
 958          * Make sure to commit all _CMM_STORE_SHARED() for non-coherent caches.
 959          */
 960         cmm_smp_wmc();
 961         show_tree(rbtree);
 962
 963         return 0;
 964 }
 965
 966 /*
 967  * Transplant v into u position.
 968  */
 969
 970 #ifdef RBTREE_RCU_SUPPORT_TRANSPLANT
 971
 972 static
 973 void rcu_rbtree_transplant(struct rcu_rbtree *rbtree,
 974                         struct rcu_rbtree_node *u,
 975                         struct rcu_rbtree_node *v,
 976                         unsigned int copy_parents)
 977 {
 978         struct rcu_rbtree_node *top, *top_child;
 979         unsigned int top_child_pos;
 980
 981         dbg_printf("transplant %p\n", v->key);
 982
 983         if (!rcu_rbtree_is_nil(rbtree, v))
 984                 v = dup_decay_node(rbtree, v);
 985
 986         if (rcu_rbtree_is_nil(rbtree, get_parent(u))) {
 987                 /* pos is arbitrary for root node */
 988                 set_parent(v, get_parent(u), IS_RIGHT);
 989                 cmm_smp_wmb();  /* write into node before publish */
 990                 _CMM_STORE_SHARED(rbtree->root, v);
 991         } else {
 992                 set_parent(v, get_parent(u), get_pos(u));
 993
 994                 if (get_pos(u) == IS_LEFT) {
 995                         _set_left_dup_decay(rbtree, get_parent(u), v,
 996                                         &top, &top_child, &top_child_pos,
 997                                         copy_parents);
 998                 } else {
 999                         assert(copy_parents);
1000                         set_right_dup_decay(rbtree, get_parent(u), v,
1001                                         &top, &top_child, &top_child_pos);
1002                 }
1003
1004                 cmm_smp_wmb();  /* write into node before publish */
1005
1006                 if (rcu_rbtree_is_nil(rbtree, top))
1007                         _CMM_STORE_SHARED(rbtree->root, top_child);
1008                 else if (top_child_pos == IS_LEFT)
1009                         _CMM_STORE_SHARED(top->_left, top_child);
1010                 else
1011                         _CMM_STORE_SHARED(top->_right, top_child);
1012
1013                 /* Point children to new copy (parent only used by updates/next/prev) */
1014                 if (get_pos(u) == IS_LEFT) {
1015                         if (copy_parents)
1016                                 set_left_update_decay(rbtree, get_parent(u), v);
1017                 } else {
1018                         assert(copy_parents);
1019                         set_right_update_decay(rbtree, get_parent(u), v);
1020                 }
1021         }
1022
1023         /* Point children to new copy (parent only used by updates/next/prev) */
1024         if (!rcu_rbtree_is_nil(rbtree, v)) {
1025                 set_parent(v->_right, get_decay(get_parent(v->_right)),
1026                         get_pos(v->_right));
1027                 set_parent(v->_left, get_decay(get_parent(v->_left)),
1028                         get_pos(v->_left));
1029         }
1030         assert(!is_decay(rbtree->root));
1031 }
1032
1033 #else
1034
1035 /* Non-RCU version */
1036 static
1037 void rcu_rbtree_transplant(struct rcu_rbtree *rbtree,
1038                            struct rcu_rbtree_node *u,
1039                            struct rcu_rbtree_node *v,
1040                            unsigned int copy_parents)
1041 {
1042         dbg_printf("transplant %p\n", v->key);
1043
1044         lock_test_mutex();
1045         if (rcu_rbtree_is_nil(rbtree, get_parent(u)))
1046                 rbtree->root = v;
1047         else if (u == get_parent(u)->_left)
1048                 get_parent(u)->_left = v;
1049         else
1050                 get_parent(u)->_right = v;
1051         set_parent(v, get_parent(u), get_pos(u));
1052         unlock_test_mutex();
1053 }
1054
1055 #endif
1056
1057 static void rcu_rbtree_remove_fixup(struct rcu_rbtree *rbtree,
1058                                     struct rcu_rbtree_node *x)
1059 {
1060         dbg_printf("remove fixup %p\n", x->key);
1061
1062         while (x != rbtree->root && x->color == COLOR_BLACK) {
1063                 assert(!is_decay(get_parent(x)));
1064                 assert(!is_decay(get_parent(x)->_left));
1065                 if (x == get_parent(x)->_left) {
1066                         struct rcu_rbtree_node *w;
1067
1068                         w = get_parent(x)->_right;
1069
1070                         if (w->color == COLOR_RED) {
1071                                 w->color = COLOR_BLACK;
1072                                 get_parent(x)->color = COLOR_RED;
1073                                 left_rotate(rbtree, get_parent(x));
1074                                 x = get_decay(x);
1075                                 assert(!is_decay(rbtree->root));
1076                                 w = get_parent(x)->_right;
1077                         }
1078                         if (w->_left->color == COLOR_BLACK
1079                             && w->_right->color == COLOR_BLACK) {
1080                                 w->color = COLOR_RED;
1081                                 x = get_parent(x);
1082                                 assert(!is_decay(rbtree->root));
1083                                 assert(!is_decay(x));
1084                         } else {
1085                                 if (w->_right->color == COLOR_BLACK) {
1086                                         w->_left->color = COLOR_BLACK;
1087                                         w->color = COLOR_RED;
1088                                         right_rotate(rbtree, w);
1089                                         assert(!is_decay(rbtree->root));
1090                                         x = get_decay(x);
1091                                         w = get_parent(x)->_right;
1092                                 }
1093                                 w->color = get_parent(x)->color;
1094                                 get_parent(x)->color = COLOR_BLACK;
1095                                 w->_right->color = COLOR_BLACK;
1096                                 left_rotate(rbtree, get_parent(x));
1097                                 assert(!is_decay(rbtree->root));
1098                                 x = rbtree->root;
1099                         }
1100                 } else {
1101                         struct rcu_rbtree_node *w;
1102
1103                         w = get_parent(x)->_left;
1104
1105                         if (w->color == COLOR_RED) {
1106                                 w->color = COLOR_BLACK;
1107                                 get_parent(x)->color = COLOR_RED;
1108                                 right_rotate(rbtree, get_parent(x));
1109                                 assert(!is_decay(rbtree->root));
1110                                 x = get_decay(x);
1111                                 w = get_parent(x)->_left;
1112                         }
1113                         if (w->_right->color == COLOR_BLACK
1114                             && w->_left->color == COLOR_BLACK) {
1115                                 w->color = COLOR_RED;
1116                                 x = get_parent(x);
1117                                 assert(!is_decay(rbtree->root));
1118                                 assert(!is_decay(x));
1119                         } else {
1120                                 if (w->_left->color == COLOR_BLACK) {
1121                                         w->_right->color = COLOR_BLACK;
1122                                         w->color = COLOR_RED;
1123                                         left_rotate(rbtree, w);
1124                                         assert(!is_decay(rbtree->root));
1125                                         x = get_decay(x);
1126                                         w = get_parent(x)->_left;
1127                                 }
1128                                 w->color = get_parent(x)->color;
1129                                 get_parent(x)->color = COLOR_BLACK;
1130                                 w->_left->color = COLOR_BLACK;
1131                                 right_rotate(rbtree, get_parent(x));
1132                                 assert(!is_decay(rbtree->root));
1133                                 x = rbtree->root;
1134                         }
1135                 }
1136         }
1137         x->color = COLOR_BLACK;
1138 }
1139
1140 /*
1141  * Delete z. All non-copied children left/right positions are unchanged.
1142  */
1143 static
1144 void rcu_rbtree_remove_nonil(struct rcu_rbtree *rbtree,
1145                              struct rcu_rbtree_node *z,
1146                              struct rcu_rbtree_node *y)
1147 {
1148         struct rcu_rbtree_node *x, *top, *top_child;
1149         unsigned int top_child_pos;
1150
1151         dbg_printf("remove nonil %p\n", z->key);
1152         show_tree(rbtree);
1153
1154         assert(!is_decay(z));
1155         assert(!is_decay(y));
1156         assert(!is_decay(y->_right));
1157         assert(!is_decay(get_parent(y)));
1158         x = y->_right;
1159         assert(!is_decay(x));
1160         if (get_parent(y) == z) {
1161                 y = dup_decay_node(rbtree, y);
1162                 set_parent(x, y, get_pos(x));   /* parent for nil */
1163                 /* y is z's right node: set left will just update y */
1164                 set_left_dup_decay(rbtree, y, z->_left,
1165                                 &top, &top_child, &top_child_pos);
1166                 assert(top_child == y);
1167                 rcu_rbtree_transplant(rbtree, z, y, 1);
1168         } else {
1169                 struct rcu_rbtree_node *oy_right, *z_right;
1170
1171                 /*
1172                  * Need to make sure y is always visible by readers.
1173                  */
1174                 y = rcu_rbtree_min_dup_decay(rbtree, z->_right, &z_right);
1175                 assert(!is_decay(y));
1176                 assert(!is_decay(z));
1177                 oy_right = y->_right;
1178
1179                 /*
1180                  * The max child key of z_right does not change, because
1181                  * we're only changing its left children.
1182                  */
1183                 y->_right = z_right;
1184                 set_parent(y->_right, y, IS_RIGHT);
1185                 if (rcu_rbtree_is_nil(rbtree, y->_right))
1186                         y->max_child_key = y->key;
1187                 else
1188                         y->max_child_key = y->_right->max_child_key;
1189
1190                 assert(!is_decay(z->_left));
1191                 y->_left = z->_left;
1192                 if (rcu_rbtree_is_nil(rbtree, y->_left))
1193                         y->min_child_key = y->key;
1194                 else
1195                         y->min_child_key = y->_left->min_child_key;
1196
1197                 assert(!is_decay(oy_right));
1198                 /*
1199                  * Transplant of oy_right to old y's location will only
1200                  * trigger a min/max update of the already copied branch
1201                  * (which is not visible yet). We are transplanting
1202                  * oy_right as a left child of old y's parent, so the
1203                  * min values update propagated upward necessarily stops
1204                  * at z_right.
1205                  */
1206                 rcu_rbtree_transplant(rbtree, y, oy_right, 0);
1207                 rcu_rbtree_transplant(rbtree, z, y, 1);
1208                 /* Update children */
1209                 (void) rcu_rbtree_min_update_decay(rbtree, y->_right);
1210         }
1211         y = get_decay(y);
1212         assert(!is_decay(z));
1213         assert(!is_decay(z->_left));
1214         y->color = z->color;
1215         set_parent(y->_left, y, IS_LEFT);
1216         set_parent(y->_right, get_decay(get_parent(y->_right)), IS_RIGHT);
1217         assert(!is_decay(y->_left));
1218         assert(!is_decay(y->_right));
1219 }
1220
1221 int rcu_rbtree_remove(struct rcu_rbtree *rbtree,
1222                       struct rcu_rbtree_node *z)
1223 {
1224         struct rcu_rbtree_node *x, *y;
1225         unsigned int y_original_color;
1226
1227         assert(!is_decay(rbtree->root));
1228         dbg_printf("remove %p\n", z->key);
1229         show_tree(rbtree);
1230
1231         assert(!is_decay(z));
1232         y = z;
1233         y_original_color = y->color;
1234
1235         if (rcu_rbtree_is_nil(rbtree, z->_left)) {
1236                 rcu_rbtree_transplant(rbtree, z, z->_right, 1);
1237                 assert(!is_decay(z));
1238                 x = get_decay(z->_right);
1239                 show_tree(rbtree);
1240         } else if (rcu_rbtree_is_nil(rbtree, z->_right)) {
1241                 rcu_rbtree_transplant(rbtree, z, z->_left, 1);
1242                 assert(!is_decay(z));
1243                 x = get_decay(z->_left);
1244                 show_tree(rbtree);
1245         } else {
1246                 y = rcu_rbtree_min(rbtree, z->_right);
1247                 assert(!is_decay(y));
1248                 y_original_color = y->color;
1249                 x = y->_right;
1250                 rcu_rbtree_remove_nonil(rbtree, z, y);
1251                 x = get_decay(x);
1252                 show_tree(rbtree);
1253         }
1254         if (y_original_color == COLOR_BLACK)
1255                 rcu_rbtree_remove_fixup(rbtree, x);
1256         show_tree(rbtree);
1257         /*
1258          * Commit all _CMM_STORE_SHARED().
1259          */
1260         cmm_smp_wmc();
1261
1262         return 0;
1263 }