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
  38 #include <urcu/rcurbtree.h>
  39 #include <urcu-pointer.h>
  40 #include <urcu-call-rcu.h>
  41
  42 #define DEBUG
  43
  44 #ifdef DEBUG
  45 #define dbg_printf(args...)     printf(args)
  46 #else
  47 #define dbg_printf(args...)
  48 #endif
  49
  50 static
  51 void set_decay(struct rcu_rbtree_node *x, struct rcu_rbtree_node *xc)
  52 {
  53         x->decay_next = xc;
  54 }
  55
  56 static
  57 struct rcu_rbtree_node *get_decay(struct rcu_rbtree_node *x)
  58 {
  59         while (x->decay_next)
  60                 x = x->decay_next;
  61         return x;
  62 }
  63
  64 static
  65 struct rcu_rbtree_node *is_decay(struct rcu_rbtree_node *x)
  66 {
  67         return x->decay_next;
  68 }
  69
  70 static
  71 struct rcu_rbtree_node *dup_decay_node(struct rcu_rbtree *rbtree,
  72                                 struct rcu_rbtree_node *x)
  73 {
  74         struct rcu_rbtree_node *xc;
  75
  76         if (rcu_rbtree_is_nil(x))
  77                 return x;
  78
  79         xc = rbtree->rballoc();
  80         memcpy(xc, x, sizeof(struct rcu_rbtree_node));
  81         xc->decay_next = NULL;
  82         set_decay(x, xc);
  83         call_rcu(&x->head, rbtree->rbfree);
  84         return xc;
  85 }
  86
  87 /*
  88  * TODO
  89  * Deal with memory allocation errors.
  90  * Can be ensured by reserving a pool of memory entries before doing the
  91  * insertion, which will have to be function of number of
  92  * transplantations/rotations required for the operation.
  93  */
  94
  95 static
  96 void show_tree(struct rcu_rbtree *rbtree)
  97 {
  98         struct rcu_rbtree_node *node;
  99
 100         node = rcu_rbtree_min(rbtree, rbtree->root);
 101         while (!rcu_rbtree_is_nil(node)) {
 102                 assert(!is_decay(node));
 103                 printf("{ 0x%lX p:%lX r:%lX l:%lX %s %s %s} ",
 104                         (unsigned long)node->key,
 105                         (unsigned long) node->p->key,
 106                         (unsigned long) node->right->key,
 107                         (unsigned long) node->left->key,
 108                         node->color ? "red" : "black",
 109                         node->pos ? "right" : "left",
 110                         node->nil ? "nil" : "");
 111                 node = rcu_rbtree_next(rbtree, node);
 112         }
 113         printf("\n");
 114 }
 115
 116 static
 117 struct rcu_rbtree_node *make_nil(struct rcu_rbtree *rbtree)
 118 {
 119         return &rbtree->nil_node;
 120 }
 121
 122 /*
 123  * Iterative rbtree search.
 124  */
 125 struct rcu_rbtree_node* rcu_rbtree_search(struct rcu_rbtree *rbtree,
 126                                           struct rcu_rbtree_node *x,
 127                                           void *k)
 128 {
 129         x = rcu_dereference(x);
 130
 131         while (!rcu_rbtree_is_nil(x) && k != x->key) {
 132                 if (rbtree->comp(k, x->key) < 0)
 133                         x = rcu_dereference(x->left);
 134                 else
 135                         x = rcu_dereference(x->right);
 136         }
 137         return x;
 138 }
 139
 140 struct rcu_rbtree_node *rcu_rbtree_min(struct rcu_rbtree *rbtree,
 141                                        struct rcu_rbtree_node *x)
 142 {
 143         struct rcu_rbtree_node *xl;
 144
 145         x = rcu_dereference(x);
 146
 147         if (rcu_rbtree_is_nil(x))
 148                 return x;
 149
 150         while (!rcu_rbtree_is_nil(xl = rcu_dereference(x->left)))
 151                 x = xl;
 152         return x;
 153 }
 154
 155 struct rcu_rbtree_node *rcu_rbtree_max(struct rcu_rbtree *rbtree,
 156                                        struct rcu_rbtree_node *x)
 157 {
 158         struct rcu_rbtree_node *xr;
 159
 160         x = rcu_dereference(x);
 161
 162         if (rcu_rbtree_is_nil(x))
 163                 return x;
 164
 165         while (!rcu_rbtree_is_nil(xr = rcu_dereference(x->right)))
 166                 x = xr;
 167         return x;
 168 }
 169
 170 /*
 171  * FIXME:
 172  * Updates should wait for a grace period between update of the
 173  * redirect pointer and update of the parent child pointer. This is to make sure
 174  * that no reference to the old entry exist.
 175  */
 176
 177 /*
 178  * next and prev need to have mutex held to ensure that parent pointer is
 179  * coherent.
 180  */
 181 struct rcu_rbtree_node *rcu_rbtree_next(struct rcu_rbtree *rbtree,
 182                                         struct rcu_rbtree_node *x)
 183 {
 184         struct rcu_rbtree_node *xr, *y;
 185
 186         x = rcu_dereference(x);
 187
 188         if (!rcu_rbtree_is_nil(xr = rcu_dereference(x->right)))
 189                 return rcu_rbtree_min(rbtree, xr);
 190         y = rcu_dereference(x->p);
 191         while (!rcu_rbtree_is_nil(y) && x->pos == IS_RIGHT) {
 192                 x = y;
 193                 y = rcu_dereference(y->p);
 194         }
 195         return y;
 196 }
 197
 198 struct rcu_rbtree_node *rcu_rbtree_prev(struct rcu_rbtree *rbtree,
 199                                         struct rcu_rbtree_node *x)
 200 {
 201         struct rcu_rbtree_node *xl, *y;
 202
 203         x = rcu_dereference(x);
 204
 205         if (!rcu_rbtree_is_nil(xl = rcu_dereference(x->left)))
 206                 return rcu_rbtree_min(rbtree, xl);
 207         y = rcu_dereference(x->p);
 208         while (!rcu_rbtree_is_nil(y) && x->pos == IS_LEFT) {
 209                 x = y;
 210                 y = rcu_dereference(y->p);
 211         }
 212         return y;
 213 }
 214
 215 /*
 216  * We have to ensure these assumptions are correct for prev/next
 217  * traversal:
 218  *
 219  * with x being a right child, the assumption that:
 220  *   x->p->right == x
 221  * or if x is a left child, the assumption that:
 222  *   x->p->left == x
 223  *
 224  * This explains why we have to allocate a vc copy of the node for left_rotate,
 225  * right_rotate and transplant operations.
 226  *
 227  * We always ensure that the right/left child and correct parent is set in the
 228  * node copies *before* we reparent the children and make the upper-level point
 229  * to the copy.
 230  */
 231
 232 /* RCU: copy x and y, atomically point to new versions. GC old. */
 233 /* Should be eventually followed by a cmm_smp_wmc() */
 234
 235 static
 236 void left_rotate(struct rcu_rbtree *rbtree,
 237                  struct rcu_rbtree_node *x)
 238 {
 239         struct rcu_rbtree_node *y, *y_left, *x_p;
 240         unsigned int x_pos;
 241
 242         y = x->right;
 243         y_left = y->left;
 244
 245         /* Now operate on new copy, decay old versions */
 246         x = dup_decay_node(rbtree, x);
 247         y = dup_decay_node(rbtree, y);
 248         y_left = dup_decay_node(rbtree, y_left);
 249
 250         x_pos = x->pos;
 251         x_p = x->p;
 252
 253         /* Internal node modifications */
 254         x->right = y_left;
 255         y->p = x->p;
 256         y->pos = x->pos;
 257         x->pos = IS_LEFT;
 258         y->left = x;
 259         x->p = y;
 260         if (!rcu_rbtree_is_nil(y_left)) {
 261                 y_left->p = x;
 262                 y_left->pos = IS_RIGHT;
 263         }
 264
 265         cmm_smp_wmb();  /* write into node before publish */
 266
 267         /* External references update (visible by readers) */
 268         if (rcu_rbtree_is_nil(x_p))
 269                 _CMM_STORE_SHARED(rbtree->root, y);
 270         else if (x_pos == IS_LEFT)
 271                 _CMM_STORE_SHARED(x_p->left, y);
 272         else
 273                 _CMM_STORE_SHARED(x_p->right, y);
 274
 275         /* Point children to new copy (parent only used by updates) */
 276         if (!rcu_rbtree_is_nil(x->left))
 277                 x->left->p = x;
 278         if (!rcu_rbtree_is_nil(y->right))
 279                 y->right->p = y;
 280
 281         /* Sanity checks */
 282         assert(y == rbtree->root || y->p->left == y || y->p->right == y);
 283         assert(x == rbtree->root || x->p->left == x || x->p->right == x);
 284         assert(rcu_rbtree_is_nil(x->right) || x->right->p == x);
 285         assert(rcu_rbtree_is_nil(x->left) || x->left->p == x);
 286         assert(rcu_rbtree_is_nil(y->right) || y->right->p == y);
 287         assert(rcu_rbtree_is_nil(y->left) || y->left->p == y);
 288         assert(!is_decay(rbtree->root));
 289         assert(!is_decay(x));
 290         assert(!is_decay(y));
 291         assert(!is_decay(x->right));
 292         assert(!is_decay(x->left));
 293         assert(!is_decay(y->right));
 294         assert(!is_decay(y->left));
 295 }
 296
 297 static
 298 void right_rotate(struct rcu_rbtree *rbtree,
 299                   struct rcu_rbtree_node *x)
 300 {
 301         struct rcu_rbtree_node *y, *y_right, *x_p;
 302         unsigned int x_pos;
 303
 304         y = x->left;
 305         y_right = y->right;
 306
 307         /* Now operate on new copy, decay old versions */
 308         x = dup_decay_node(rbtree, x);
 309         y = dup_decay_node(rbtree, y);
 310         y_right = dup_decay_node(rbtree, y_right);
 311
 312         x_pos = x->pos;
 313         x_p = x->p;
 314
 315         /* Internal node modifications */
 316         x->left = y_right;
 317         y->p = x->p;
 318         y->pos = x->pos;
 319         x->pos = IS_RIGHT;
 320         y->right = x;
 321         x->p = y;
 322         if (!rcu_rbtree_is_nil(y_right)) {
 323                 y_right->p = x;
 324                 y_right->pos = IS_LEFT;
 325         }
 326
 327         cmm_smp_wmb();  /* write into node before publish */
 328
 329         /* External references update (visible by readers) */
 330         if (rcu_rbtree_is_nil(x_p))
 331                 _CMM_STORE_SHARED(rbtree->root, y);
 332         else if (x_pos == IS_RIGHT)
 333                 _CMM_STORE_SHARED(x_p->right, y);
 334         else
 335                 _CMM_STORE_SHARED(x_p->left, y);
 336
 337         /* Point children to new copy (parent only used by updates) */
 338         if (!rcu_rbtree_is_nil(x->right))
 339                 x->right->p = x;
 340         if (!rcu_rbtree_is_nil(y->left))
 341                 y->left->p = y;
 342
 343         /* Sanity checks */
 344         assert(y == rbtree->root || y->p->right == y || y->p->left == y);
 345         assert(x == rbtree->root || x->p->right == x || x->p->left == x);
 346         assert(rcu_rbtree_is_nil(x->left) || x->left->p == x);
 347         assert(rcu_rbtree_is_nil(x->right) || x->right->p == x);
 348         assert(rcu_rbtree_is_nil(y->left) || y->left->p == y);
 349         assert(rcu_rbtree_is_nil(y->right) || y->right->p == y);
 350         assert(!is_decay(rbtree->root));
 351         assert(!is_decay(x));
 352         assert(!is_decay(y));
 353         assert(!is_decay(x->left));
 354         assert(!is_decay(x->right));
 355         assert(!is_decay(y->left));
 356         assert(!is_decay(y->right));
 357 }
 358
 359 static void rcu_rbtree_insert_fixup(struct rcu_rbtree *rbtree,
 360                                     struct rcu_rbtree_node *z)
 361 {
 362         struct rcu_rbtree_node *y;
 363
 364         dbg_printf("insert fixup %p\n", z->key);
 365         assert(!is_decay(rbtree->root));
 366
 367         while (z->p->color == COLOR_RED) {
 368                 if (z->p == z->p->p->left) {
 369                         y = z->p->p->right;
 370                         if (y->color == COLOR_RED) {
 371                                 z->p->color = COLOR_BLACK;
 372                                 y->color = COLOR_BLACK;
 373                                 z->p->p->color = COLOR_RED;
 374                                 z = z->p->p;
 375                         } else {
 376                                 if (z == z->p->right) {
 377                                         z = z->p;
 378                                         left_rotate(rbtree, z);
 379                                         z = get_decay(z);
 380                                         assert(!is_decay(rbtree->root));
 381                                 }
 382                                 z->p->color = COLOR_BLACK;
 383                                 z->p->p->color = COLOR_RED;
 384                                 assert(!is_decay(z));
 385                                 assert(!is_decay(z->p));
 386                                 assert(!is_decay(z->p->p));
 387                                 right_rotate(rbtree, z->p->p);
 388                                 assert(!is_decay(z));
 389                                 assert(!is_decay(rbtree->root));
 390                         }
 391                 } else {
 392                         y = z->p->p->left;
 393                         if (y->color == COLOR_RED) {
 394                                 z->p->color = COLOR_BLACK;
 395                                 y->color = COLOR_BLACK;
 396                                 z->p->p->color = COLOR_RED;
 397                                 z = z->p->p;
 398                         } else {
 399                                 if (z == z->p->left) {
 400                                         z = z->p;
 401                                         right_rotate(rbtree, z);
 402                                         z = get_decay(z);
 403                                         assert(!is_decay(rbtree->root));
 404                                 }
 405                                 z->p->color = COLOR_BLACK;
 406                                 z->p->p->color = COLOR_RED;
 407                                 left_rotate(rbtree, z->p->p);
 408                                 assert(!is_decay(z));
 409                                 assert(!is_decay(rbtree->root));
 410                         }
 411                 }
 412         }
 413         rbtree->root->color = COLOR_BLACK;
 414 }
 415
 416 /*
 417  * rcu_rbtree_insert - Insert a node in the RCU rbtree
 418  *
 419  * Returns 0 on success, or < 0 on error.
 420  */
 421 int rcu_rbtree_insert(struct rcu_rbtree *rbtree,
 422                       struct rcu_rbtree_node *z)
 423 {
 424         struct rcu_rbtree_node *x, *y;
 425
 426         dbg_printf("insert %p\n", z->key);
 427         assert(!is_decay(rbtree->root));
 428
 429         y = make_nil(rbtree);
 430         if (!rbtree->root)
 431                 rbtree->root = make_nil(rbtree);
 432         x = rbtree->root;
 433         while (!rcu_rbtree_is_nil(x)) {
 434                 y = x;
 435                 if (rbtree->comp(z->key, x->key) < 0)
 436                         x = x->left;
 437                 else
 438                         x = x->right;
 439         }
 440
 441         z->p = y;
 442
 443         z->left = make_nil(rbtree);
 444         z->right = make_nil(rbtree);
 445         z->color = COLOR_RED;
 446         z->nil = 0;
 447         z->decay_next = NULL;
 448
 449         if (rcu_rbtree_is_nil(y))
 450                 z->pos = IS_RIGHT;      /* arbitrary for root node */
 451         else if (rbtree->comp(z->key, y->key) < 0)
 452                 z->pos = IS_LEFT;
 453         else
 454                 z->pos = IS_RIGHT;
 455
 456         /*
 457          * Order stores to z (children/parents) before stores that will make it
 458          * visible to the rest of the tree.
 459          */
 460         cmm_smp_wmb();
 461
 462         if (rcu_rbtree_is_nil(y))
 463                 _CMM_STORE_SHARED(rbtree->root, z);
 464         else if (rbtree->comp(z->key, y->key) < 0)
 465                 _CMM_STORE_SHARED(y->left, z);
 466         else
 467                 _CMM_STORE_SHARED(y->right, z);
 468         rcu_rbtree_insert_fixup(rbtree, z);
 469         /*
 470          * Make sure to commit all _CMM_STORE_SHARED() for non-coherent caches.
 471          */
 472         cmm_smp_wmc();
 473         show_tree(rbtree);
 474
 475         return 0;
 476 }
 477
 478 /*
 479  * Transplant v into u position.
 480  */
 481 static
 482 void rcu_rbtree_transplant(struct rcu_rbtree *rbtree,
 483                         struct rcu_rbtree_node *u,
 484                         struct rcu_rbtree_node *v)
 485 {
 486         dbg_printf("transplant %p\n", v->key);
 487
 488         if (!rcu_rbtree_is_nil(v))
 489                 v = dup_decay_node(rbtree, v);
 490
 491         if (rcu_rbtree_is_nil(u->p)) {
 492                 v->p = u->p;
 493                 cmm_smp_wmb();  /* write into node before publish */
 494                 _CMM_STORE_SHARED(rbtree->root, v);
 495         } else if (u == u->p->left) {
 496                 v->pos = IS_LEFT;
 497                 v->p = u->p;
 498                 cmm_smp_wmb();  /* write into node before publish */
 499                 _CMM_STORE_SHARED(u->p->left, v);
 500         } else {
 501                 v->pos = IS_RIGHT;
 502                 v->p = u->p;
 503                 cmm_smp_wmb();  /* write into node before publish */
 504                 _CMM_STORE_SHARED(u->p->right, v);
 505         }
 506         /* Set children parent to new node (only used by updates) */
 507         if (!rcu_rbtree_is_nil(v)) {
 508                 v->right->p = v;
 509                 v->left->p = v;
 510         }
 511         assert(!is_decay(rbtree->root));
 512 }
 513
 514 static void rcu_rbtree_remove_fixup(struct rcu_rbtree *rbtree,
 515                                     struct rcu_rbtree_node *x)
 516 {
 517         dbg_printf("remove fixup %p\n", x->key);
 518
 519         while (x != rbtree->root && x->color == COLOR_BLACK) {
 520                 assert(!is_decay(x->p));
 521                 assert(!is_decay(x->p->left));
 522                 if (x == x->p->left) {
 523                         struct rcu_rbtree_node *w;
 524
 525                         w = x->p->right;
 526
 527                         if (w->color == COLOR_RED) {
 528                                 w->color = COLOR_BLACK;
 529                                 x->p->color = COLOR_RED;
 530                                 left_rotate(rbtree, x->p);
 531                                 x = get_decay(x);
 532                                 assert(!is_decay(rbtree->root));
 533                                 w = x->p->right;
 534                         }
 535                         if (w->left->color == COLOR_BLACK
 536                             && w->right->color == COLOR_BLACK) {
 537                                 w->color = COLOR_RED;
 538                                 x = x->p;
 539                                 assert(!is_decay(rbtree->root));
 540                                 assert(!is_decay(x));
 541                         } else {
 542                                 if (w->right->color == COLOR_BLACK) {
 543                                         w->left->color = COLOR_BLACK;
 544                                         w->color = COLOR_RED;
 545                                         right_rotate(rbtree, w);
 546                                         assert(!is_decay(rbtree->root));
 547                                         x = get_decay(x);
 548                                         w = x->p->right;
 549                                 }
 550                                 w->color = x->p->color;
 551                                 x->p->color = COLOR_BLACK;
 552                                 w->right->color = COLOR_BLACK;
 553                                 left_rotate(rbtree, x->p);
 554                                 assert(!is_decay(rbtree->root));
 555                                 x = rbtree->root;
 556                         }
 557                 } else {
 558                         struct rcu_rbtree_node *w;
 559
 560                         w = x->p->left;
 561
 562                         if (w->color == COLOR_RED) {
 563                                 w->color = COLOR_BLACK;
 564                                 x->p->color = COLOR_RED;
 565                                 right_rotate(rbtree, x->p);
 566                                 assert(!is_decay(rbtree->root));
 567                                 x = get_decay(x);
 568                                 w = x->p->left;
 569                         }
 570                         if (w->right->color == COLOR_BLACK
 571                             && w->left->color == COLOR_BLACK) {
 572                                 w->color = COLOR_RED;
 573                                 x = x->p;
 574                                 assert(!is_decay(rbtree->root));
 575                                 assert(!is_decay(x));
 576                         } else {
 577                                 if (w->left->color == COLOR_BLACK) {
 578                                         w->right->color = COLOR_BLACK;
 579                                         w->color = COLOR_RED;
 580                                         left_rotate(rbtree, w);
 581                                         assert(!is_decay(rbtree->root));
 582                                         x = get_decay(x);
 583                                         w = x->p->left;
 584                                 }
 585                                 w->color = x->p->color;
 586                                 x->p->color = COLOR_BLACK;
 587                                 w->left->color = COLOR_BLACK;
 588                                 right_rotate(rbtree, x->p);
 589                                 assert(!is_decay(rbtree->root));
 590                                 x = rbtree->root;
 591                         }
 592                 }
 593         }
 594         x->color = COLOR_BLACK;
 595 }
 596
 597 /*
 598  * Delete z. All non-copied children left/right positions are unchanged.
 599  */
 600 static
 601 void rcu_rbtree_remove_nonil(struct rcu_rbtree *rbtree,
 602                              struct rcu_rbtree_node *z,
 603                              struct rcu_rbtree_node *y)
 604 {
 605         struct rcu_rbtree_node *x;
 606
 607         dbg_printf("remove nonil %p\n", z->key);
 608         show_tree(rbtree);
 609
 610         assert(!is_decay(z));
 611         assert(!is_decay(y));
 612         assert(!is_decay(y->right));
 613         assert(!is_decay(y->p));
 614         x = y->right;
 615         assert(!is_decay(x));
 616         if (y->p == z)
 617                 x->p = y;
 618         else {
 619                 rcu_rbtree_transplant(rbtree, y, y->right);
 620                 assert(!is_decay(y));
 621                 assert(!is_decay(z));
 622                 assert(!is_decay(z->right));
 623                 y->right = z->right;
 624                 y->right->p = y;
 625         }
 626         rcu_rbtree_transplant(rbtree, z, y);
 627         y = get_decay(y);
 628         assert(!is_decay(z));
 629         assert(!is_decay(z->left));
 630         y->left = z->left;
 631         y->left->p = y;
 632         y->color = z->color;
 633 }
 634
 635 int rcu_rbtree_remove(struct rcu_rbtree *rbtree,
 636                       struct rcu_rbtree_node *z)
 637 {
 638         struct rcu_rbtree_node *x, *y;
 639         unsigned int y_original_color;
 640
 641         assert(!is_decay(rbtree->root));
 642         dbg_printf("remove %p\n", z->key);
 643         show_tree(rbtree);
 644
 645         assert(!is_decay(z));
 646         y = z;
 647         y_original_color = y->color;
 648
 649         if (rcu_rbtree_is_nil(z->left)) {
 650                 rcu_rbtree_transplant(rbtree, z, z->right);
 651                 assert(!is_decay(z));
 652                 x = get_decay(z->right);
 653                 show_tree(rbtree);
 654         } else if (rcu_rbtree_is_nil(z->right)) {
 655                 rcu_rbtree_transplant(rbtree, z, z->left);
 656                 assert(!is_decay(z));
 657                 x = get_decay(z->left);
 658                 show_tree(rbtree);
 659         } else {
 660                 y = rcu_rbtree_min(rbtree, z->right);
 661                 assert(!is_decay(y));
 662                 y_original_color = y->color;
 663                 rcu_rbtree_remove_nonil(rbtree, z, y);
 664                 x = get_decay(y->right);
 665                 show_tree(rbtree);
 666         }
 667         if (y_original_color == COLOR_BLACK)
 668                 rcu_rbtree_remove_fixup(rbtree, x);
 669         show_tree(rbtree);
 670         /*
 671          * Commit all _CMM_STORE_SHARED().
 672          */
 673         cmm_smp_wmc();
 674
 675         return 0;
 676 }