urcu-rbtree.c

   1 /*
   2  * urcu-rbtree.c
   3  *
   4  * Userspace RCU library - Red-Black Tree
   5  *
   6  * Copyright (c) 2010 Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
   7  *
   8  * This library is free software; you can redistribute it and/or
   9  * modify it under the terms of the GNU Lesser General Public
  10  * License as published by the Free Software Foundation; either
  11  * version 2.1 of the License, or (at your option) any later version.
  12  *
  13  * This library is distributed in the hope that it will be useful,
  14  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  15  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  16  * Lesser General Public License for more details.
  17  *
  18  * You should have received a copy of the GNU Lesser General Public
  19  * License along with this library; if not, write to the Free Software
  20  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
  21  *
  22  * Implementation of RCU-adapted data structures and operations based on the RB
  23  * tree algorithms found in chapter 12 of:
  24  *
  25  * Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and
  26  * Clifford Stein. Introduction to Algorithms, Third Edition. The MIT
  27  * Press, September 2009.
  28  */
  29
  30 #define _BSD_SOURCE
  31 #define _LGPL_SOURCE
  32
  33 #include <stdio.h>
  34 #include <pthread.h>
  35 #include <assert.h>
  36
  37 #include <urcu-rbtree.h>
  38 #include <urcu-pointer.h>
  39
  40 /*
  41  * TODO
  42  * Deal with memory allocation errors.
  43  * Can be ensured by reserving a pool of memory entries before doing the
  44  * insertion, which will have to be function of number of
  45  * transplantations/rotations required for the operation.
  46  */
  47
  48 /* Sentinel (bottom nodes). Don't care about p, left, right and key values */
  49 struct rcu_rbtree_node rcu_rbtree_nil = {
  50         .color = COLOR_BLACK,
  51 };
  52
  53 /*
  54  * Iterative rbtree search.
  55  */
  56 struct rcu_rbtree_node* rcu_rbtree_search(struct rcu_rbtree_node *x,
  57                                           void *k, rcu_rbtree_comp comp)
  58 {
  59         x = rcu_dereference(x);
  60
  61         while (x != &rcu_rbtree_nil && k != x->key) {
  62                 if (k < x->key)
  63                         x = rcu_dereference(x->left);
  64                 else
  65                         x = rcu_dereference(x->right);
  66         }
  67         return x;
  68 }
  69
  70 struct rcu_rbtree_node *rcu_rbtree_min(struct rcu_rbtree_node *x,
  71                                        rcu_rbtree_comp comp)
  72 {
  73         struct rcu_rbtree_node *xl;
  74
  75         x = rcu_dereference(x);
  76
  77         while ((xl = rcu_dereference(x->left)) != &rcu_rbtree_nil)
  78                 x = xl;
  79         return x;
  80 }
  81
  82 struct rcu_rbtree_node *rcu_rbtree_max(struct rcu_rbtree_node *x,
  83                                        rcu_rbtree_comp comp)
  84 {
  85         struct rcu_rbtree_node *xr;
  86
  87         x = rcu_dereference(x);
  88
  89         while ((xr = rcu_dereference(x->right)) != &rcu_rbtree_nil)
  90                 x = xr;
  91         return x;
  92 }
  93
  94 /*
  95  * next and prev need to have mutex held to ensure that parent pointer is
  96  * coherent.
  97  */
  98 struct rcu_rbtree_node *rcu_rbtree_next(struct rcu_rbtree_node *x,
  99                                         rcu_rbtree_comp comp)
 100 {
 101         struct rcu_rbtree_node *xr, *y, *yredir;
 102
 103         x = rcu_dereference(x);
 104
 105         if ((xr = rcu_dereference(x->right)) != &rcu_rbtree_nil)
 106                 return rcu_rbtree_min(xr, comp);
 107         y = rcu_dereference(x->p);
 108         while ((yredir = rcu_dereference(y->redir)) != NULL)
 109                 y = yredir;
 110         while (y != &rcu_rbtree_nil && x == rcu_dereference(y->right)) {
 111                 x = y;
 112                 y = rcu_dereference(y->p);
 113                 while ((yredir = rcu_dereference(y->redir)) != NULL)
 114                         y = yredir;
 115         }
 116         return y;
 117 }
 118
 119 struct rcu_rbtree_node *rcu_rbtree_prev(struct rcu_rbtree_node *x,
 120                                         rcu_rbtree_comp comp)
 121 {
 122         struct rcu_rbtree_node *xl, *y, *yredir;
 123
 124         x = rcu_dereference(x);
 125
 126         if ((xl = rcu_dereference(x->left)) != &rcu_rbtree_nil)
 127                 return rcu_rbtree_max(xl, comp);
 128         y = rcu_dereference(x->p);
 129         while ((yredir = rcu_dereference(y->redir)) != NULL)
 130                 y = yredir;
 131         while (y != &rcu_rbtree_nil && x == rcu_dereference(y->left)) {
 132                 x = y;
 133                 y = rcu_dereference(y->p);
 134                 while ((yredir = rcu_dereference(y->redir)) != NULL)
 135                         y = yredir;
 136         }
 137         return y;
 138 }
 139
 140 /*
 141  * We have to ensure these assumptions are correct for prev/next
 142  * traversal:
 143  *
 144  * with x being a right child, the assumption that:
 145  *   x->p->right == x
 146  * or if x is a left child, the assumption that:
 147  *   x->p->left == x
 148  *
 149  * This explains why we have to allocate a vc copy of the node for left_rotate,
 150  * right_rotate and transplant operations.
 151  *
 152  * We always ensure that the right/left child and correct parent is set in the
 153  * node copies *before* we reparent the children and make the upper-level point
 154  * to the copy.
 155  */
 156
 157 /* RCU: copy x and y, atomically point to new versions. GC old. */
 158 /* Should be eventually followed by a smp_wmc() */
 159 /* Returns the new x. Previous x->right references are changed to yc. */
 160 static struct rcu_rbtree_node *left_rotate(struct rcu_rbtree_node **root,
 161                                            struct rcu_rbtree_node *x,
 162                                            rcu_rbtree_alloc rballoc,
 163                                            rcu_rbtree_free rbfree)
 164 {
 165         struct rcu_rbtree_node *xc, *y, *yc;
 166
 167         y = x->right;
 168
 169         if (x != &rcu_rbtree_nil) {
 170                 xc = rballoc();
 171                 *xc = *x;
 172         }
 173
 174         if (y != &rcu_rbtree_nil) {
 175                 yc = rballoc();
 176                 *yc = *y;
 177         }
 178
 179         /* Modify children and parents in the node copies */
 180         if (x != &rcu_rbtree_nil) {
 181                 xc->right = y->left;
 182                 xc->p = yc;
 183         } else
 184                 xc = &rcu_rbtree_nil;
 185
 186         if (y != &rcu_rbtree_nil) {
 187                 yc->left = xc;
 188                 yc->p = x->p;
 189         } else
 190                 yc = &rcu_rbtree_nil;
 191
 192         /*
 193          * Order stores to node copies (children/parents) before stores that
 194          * will make the copies visible to the rest of the tree.
 195          */
 196         smp_wmb();
 197
 198         /*
 199          * redirect old nodes to new.
 200          */
 201         _STORE_SHARED(x->redir, xc);
 202         _STORE_SHARED(y->redir, yc);
 203
 204         /*
 205          * Ensure that redirections are visible before updating external
 206          * pointers.
 207          */
 208         smp_wmb();
 209
 210         /* Make parents point to the copies */
 211         if (x->p == &rcu_rbtree_nil)
 212                 _STORE_SHARED(*root, yc);
 213         else if (x == x->p->left)
 214                 _STORE_SHARED(x->p->left, yc);
 215         else
 216                 _STORE_SHARED(x->p->right, yc);
 217
 218         /* Assign children parents to copies */
 219         if (x != &rcu_rbtree_nil) {
 220                 _STORE_SHARED(xc->right->p, xc);
 221                 _STORE_SHARED(xc->left->p, xc);
 222                 defer_rcu(rbfree, x);
 223         }
 224         if (y != &rcu_rbtree_nil) {
 225                 _STORE_SHARED(yc->right->p, yc);
 226                 defer_rcu(rbfree, y);
 227                 /* yc->left is xc, its parent is already set in node copy */
 228         }
 229         return xc;
 230 }
 231
 232 #if 0 /* orig */
 233 static void left_rotate(struct rcu_rbtree_node **root,
 234                         struct rcu_rbtree_node *x,
 235                         rcu_rbtree_alloc rballoc)
 236 {
 237         struct rcu_rbtree_node *y;
 238
 239         y = x->right;
 240         x->right = y->left;
 241         if (y->left != &rcu_rbtree_nil)
 242                 y->left->p = x;
 243         y->p = x->p;
 244         if (x->p == &rcu_rbtree_nil)
 245                 *root = y;
 246         else if (x == x->p->left)
 247                 x->p->left = y;
 248         else
 249                 x->p->right = y;
 250         y->left = x;
 251         x->p = y;
 252 }
 253 #endif //0
 254
 255 /* RCU: copy x and y, atomically point to new versions. GC old. */
 256 /* Should be eventually followed by a smp_wmc() */
 257 /* Returns the new x. Previous x->left references are changed to yc. */
 258 static struct rcu_rbtree_node *right_rotate(struct rcu_rbtree_node **root,
 259                                             struct rcu_rbtree_node *x,
 260                                             rcu_rbtree_alloc rballoc,
 261                                             rcu_rbtree_free rbfree)
 262 {
 263         struct rcu_rbtree_node *xc, *y, *yc;
 264
 265         y = x->left;
 266
 267         if (x != &rcu_rbtree_nil) {
 268                 xc = rballoc();
 269                 *xc = *x;
 270         }
 271
 272         if (y != &rcu_rbtree_nil) {
 273                 yc = rballoc();
 274                 *yc = *y;
 275         }
 276
 277         /* Modify children and parents in the node copies */
 278         if (x != &rcu_rbtree_nil) {
 279                 xc->left = y->right;
 280                 xc->p = yc;
 281         } else
 282                 xc = &rcu_rbtree_nil;
 283
 284         if (y != &rcu_rbtree_nil) {
 285                 yc->right = xc;
 286                 yc->p = x->p;
 287         } else
 288                 yc = &rcu_rbtree_nil;
 289
 290         /*
 291          * Order stores to node copies (children/parents) before stores that
 292          * will make the copies visible to the rest of the tree.
 293          */
 294         smp_wmb();
 295
 296         /*
 297          * redirect old nodes to new.
 298          */
 299         _STORE_SHARED(x->redir, xc);
 300         _STORE_SHARED(y->redir, yc);
 301
 302         /*
 303          * Ensure that redirections are visible before updating external
 304          * pointers.
 305          */
 306         smp_wmb();
 307
 308         /* Make parents point to the copies */
 309         if (x->p == &rcu_rbtree_nil)
 310                 _STORE_SHARED(*root, yc);
 311         else if (x == x->p->right)
 312                 _STORE_SHARED(x->p->right, yc);
 313         else
 314                 _STORE_SHARED(x->p->left, yc);
 315
 316         /* Assign children parents to copies */
 317         if (x != &rcu_rbtree_nil) {
 318                 _STORE_SHARED(xc->left->p, xc);
 319                 _STORE_SHARED(xc->right->p, xc);
 320                 defer_rcu(rbfree, x);
 321         }
 322         if (y != &rcu_rbtree_nil) {
 323                 _STORE_SHARED(yc->left->p, yc);
 324                 defer_rcu(rbfree, y);
 325                 /* yc->right is xc, its parent is already set in node copy */
 326         }
 327         return xc;
 328 }
 329
 330 #if 0 //orig
 331 static void right_rotate(struct rcu_rbtree_node **root,
 332                          struct rcu_rbtree_node *x,
 333                          rcu_rbtree_alloc rballoc)
 334 {
 335         struct rcu_rbtree_node *y;
 336
 337         y = x->left;
 338         x->left = y->right;
 339         if (y->right != &rcu_rbtree_nil)
 340                 y->right->p = x;
 341         y->p = x->p;
 342         if (x->p == &rcu_rbtree_nil)
 343                 *root = y;
 344         else if (x == x->p->right)
 345                 x->p->right = y;
 346         else
 347                 x->p->left = y;
 348         y->right = x;
 349         x->p = y;
 350 }
 351 #endif //0
 352
 353 static void rcu_rbtree_insert_fixup(struct rcu_rbtree_node **root,
 354                                     struct rcu_rbtree_node *z,
 355                                     rcu_rbtree_alloc rballoc,
 356                                     rcu_rbtree_free rbfree)
 357 {
 358         struct rcu_rbtree_node *y;
 359
 360         while (z->p->color == COLOR_RED) {
 361                 if (z->p == z->p->p->left) {
 362                         y = z->p->p->right;
 363                         if (y->color == COLOR_RED) {
 364                                 z->p->color = COLOR_BLACK;
 365                                 y->color = COLOR_BLACK;
 366                                 z->p->p->color = COLOR_RED;
 367                                 z = z->p->p;
 368                         } else {
 369                                 if (z == z->p->right) {
 370                                         z = z->p;
 371                                         z = left_rotate(root, z,
 372                                                         rballoc, rbfree);
 373                                 }
 374                                 z->p->color = COLOR_BLACK;
 375                                 z->p->p->color = COLOR_RED;
 376                                 right_rotate(root, z->p->p, rballoc, rbfree);
 377                         }
 378                 } else {
 379                         y = z->p->p->left;
 380                         if (y->color == COLOR_RED) {
 381                                 z->p->color = COLOR_BLACK;
 382                                 y->color = COLOR_BLACK;
 383                                 z->p->p->color = COLOR_RED;
 384                                 z = z->p->p;
 385                         } else {
 386                                 if (z == z->p->left) {
 387                                         z = z->p;
 388                                         z = right_rotate(root, z,
 389                                                          rballoc, rbfree);
 390                                 }
 391                                 z->p->color = COLOR_BLACK;
 392                                 z->p->p->color = COLOR_RED;
 393                                 left_rotate(root, z->p->p, rballoc, rbfree);
 394                         }
 395                 }
 396         }
 397         (*root)->color = COLOR_BLACK;
 398 }
 399
 400 /*
 401  * rcu_rbtree_insert - Insert a node in the RCU rbtree
 402  *
 403  * Returns 0 on success, or < 0 on error.
 404  */
 405 int rcu_rbtree_insert(struct rcu_rbtree_node **root,
 406                       struct rcu_rbtree_node *z,
 407                       rcu_rbtree_comp comp,
 408                       rcu_rbtree_alloc rballoc,
 409                       rcu_rbtree_free rbfree)
 410 {
 411         struct rcu_rbtree_node *x, *y;
 412
 413         y = &rcu_rbtree_nil;
 414         x = *root;
 415
 416         while (x != &rcu_rbtree_nil) {
 417                 y = x;
 418                 if (comp(z->key, x->key) < 0)
 419                         x = x->left;
 420                 else
 421                         x = x->right;
 422         }
 423
 424         z->p = y;
 425         z->left = &rcu_rbtree_nil;
 426         z->right = &rcu_rbtree_nil;
 427         z->color = COLOR_RED;
 428         z->redir = NULL;
 429
 430         /*
 431          * Order stores to z (children/parents) before stores that will make it
 432          * visible to the rest of the tree.
 433          */
 434         smp_wmb();
 435
 436         if (y == &rcu_rbtree_nil)
 437                 _STORE_SHARED(*root, z);
 438         else if (comp(z->key, y->key) < 0)
 439                 _STORE_SHARED(y->left, z);
 440         else
 441                 _STORE_SHARED(y->right, z);
 442         rcu_rbtree_insert_fixup(root, z, rballoc, rbfree);
 443         /*
 444          * Make sure to commit all _STORE_SHARED() for non-coherent caches.
 445          */
 446         smp_wmc();
 447
 448         return 0;
 449 }
 450
 451 /*
 452  * Transplant v into u position.
 453  * Returns new copy of v.
 454  */
 455 static struct rcu_rbtree_node *
 456 rcu_rbtree_transplant(struct rcu_rbtree_node **root,
 457                       struct rcu_rbtree_node *u,
 458                       struct rcu_rbtree_node *v,
 459                       rcu_rbtree_alloc rballoc,
 460                       rcu_rbtree_free rbfree)
 461 {
 462         struct rcu_rbtree_node *vc;
 463
 464         if (v != &rcu_rbtree_nil) {
 465                 vc = rballoc();
 466                 *vc = *v;
 467
 468                 /* Change vc parent pointer */
 469                 vc->p = u->p;
 470
 471                 /*
 472                  * Order stores to node copies (children/parents) before stores
 473                  * that will make the copies visible to the rest of the tree.
 474                  */
 475                 smp_wmb();
 476
 477                 /*
 478                  * redirect old node to new.
 479                  */
 480                 _STORE_SHARED(v->redir, vc);
 481
 482                 /*
 483                  * Ensure that redirections are visible before updating external
 484                  * pointers.
 485                  */
 486                 smp_wmb();
 487         } else {
 488                 vc = &rcu_rbtree_nil;
 489         }
 490
 491         /* Assign upper-level pointer to vc, replacing u. */
 492         if (u->p == &rcu_rbtree_nil)
 493                 _STORE_SHARED(*root, vc);
 494         else if (u == u->p->left)
 495                 _STORE_SHARED(u->p->left, vc);
 496         else
 497                 _STORE_SHARED(u->p->right, vc);
 498
 499         if (v != &rcu_rbtree_nil) {
 500                 /*
 501                  * The children pointers in vc are the same as v. We can
 502                  * therefore reparent v's children to vc safely.
 503                  */
 504                 _STORE_SHARED(vc->right->p, vc);
 505                 _STORE_SHARED(vc->left->p, vc);
 506
 507                 defer_rcu(rbfree, v);
 508         }
 509         return vc;
 510 }
 511
 512 static void rcu_rbtree_remove_fixup(struct rcu_rbtree_node **root,
 513                                     struct rcu_rbtree_node *x,
 514                                     rcu_rbtree_alloc rballoc,
 515                                     rcu_rbtree_free rbfree)
 516 {
 517         while (x != *root && x->color == COLOR_BLACK) {
 518                 if (x == x->p->left) {
 519                         struct rcu_rbtree_node *w, *t;
 520
 521                         w = x->p->right;
 522                         if (w->color == COLOR_RED) {
 523                                 w->color == COLOR_BLACK;
 524                                 x->p->color = COLOR_RED;
 525                                 t = left_rotate(root, x->p, rballoc, rbfree);
 526                                 assert(x->p->left == t->left);
 527                                 /* x is a left node, not copied by rotation */
 528                                 w = x->p->right;
 529                         }
 530                         if (w->left->color == COLOR_BLACK
 531                             && w->right->color == COLOR_BLACK) {
 532                                 w->color = COLOR_RED;
 533                                 x = x->p;
 534                         } else {
 535                                 if (w->right->color == COLOR_BLACK) {
 536                                         w->left->color = COLOR_BLACK;
 537                                         w->color = COLOR_RED;
 538                                         right_rotate(root, w, rballoc, rbfree);
 539                                         w = x->p->right;
 540                                 }
 541                                 w->color = x->p->color;
 542                                 x->p->color = COLOR_BLACK;
 543                                 w->right->color = COLOR_BLACK;
 544                                 left_rotate(root, x->p, rballoc, rbfree);
 545                                 x = *root;
 546                         }
 547                 } else {
 548                         struct rcu_rbtree_node *w;
 549
 550                         w = x->p->left;
 551                         if (w->color == COLOR_RED) {
 552                                 w->color == COLOR_BLACK;
 553                                 x->p->color = COLOR_RED;
 554                                 right_rotate(root, x->p, rballoc, rbfree);
 555                                 /* x is a right node, not copied by rotation */
 556                                 w = x->p->left;
 557                         }
 558                         if (w->right->color == COLOR_BLACK
 559                             && w->left->color == COLOR_BLACK) {
 560                                 w->color = COLOR_RED;
 561                                 x = x->p;
 562                         } else {
 563                                 if (w->left->color == COLOR_BLACK) {
 564                                         w->right->color = COLOR_BLACK;
 565                                         w->color = COLOR_RED;
 566                                         left_rotate(root, w, rballoc, rbfree);
 567                                         w = x->p->left;
 568                                 }
 569                                 w->color = x->p->color;
 570                                 x->p->color = COLOR_BLACK;
 571                                 w->left->color = COLOR_BLACK;
 572                                 right_rotate(root, x->p, rballoc, rbfree);
 573                                 x = *root;
 574                         }
 575                 }
 576         }
 577         x->color = COLOR_BLACK;
 578 }
 579
 580 /* Returns the new copy of y->right */
 581 static struct rcu_rbtree_node *
 582 rcu_rbtree_remove_nonil(struct rcu_rbtree_node **root,
 583                         struct rcu_rbtree_node *z,
 584                         struct rcu_rbtree_node *y,
 585                         rcu_rbtree_comp comp,
 586                         rcu_rbtree_alloc rballoc,
 587                         rcu_rbtree_free rbfree)
 588 {
 589         struct rcu_rbtree_node *x, *xc, *yc;
 590
 591         x = y->right;
 592
 593         if (x != &rcu_rbtree_nil) {
 594                 xc = rballoc();
 595                 *xc = *x;
 596         } else
 597                 xc = &rcu_rbtree_nil;
 598
 599         yc = rballoc();
 600         *yc = *y;
 601
 602         /* Update parent and children pointers within copies */
 603         if (y->p == z)
 604                 xc->p = yc;
 605         else {
 606                 /* Transplant y->right (xc) into y, within copy */
 607                 xc->p = y->p;
 608                 /* But also change the right pointer of yc */
 609                 yc->right = z->right;
 610         }
 611         /* Transplant y into z, within copy */
 612         yc->p = z->p;
 613
 614         yc->left = z->left;
 615         yc->color = z->color;
 616
 617         /*
 618          * Order stores to node copies (children/parents) before stores that
 619          * will make the copies visible to the rest of the tree.
 620          */
 621         smp_wmb();
 622
 623         /*
 624          * redirect old nodes to new.
 625          */
 626         if (x != &rcu_rbtree_nil)
 627                 _STORE_SHARED(x->redir, xc);
 628         _STORE_SHARED(y->redir, yc);
 629
 630         /*
 631          * Ensure that redirections are visible before updating external
 632          * pointers.
 633          */
 634         smp_wmb();
 635
 636         /* Update external pointers */
 637
 638         if (y->p != z) {
 639                 /* Transplant y->right into y, external parent links */
 640
 641                 /* Assign upper-level pointer to xc, replacing y. */
 642                 if (y->p == &rcu_rbtree_nil)
 643                         _STORE_SHARED(*root, xc);
 644                 else if (y == y->p->left)
 645                         _STORE_SHARED(y->p->left, xc);
 646                 else
 647                         _STORE_SHARED(y->p->right, xc);
 648         }
 649
 650         /* Transplant y into z, update external parent links */
 651         if (z->p == &rcu_rbtree_nil)
 652                 _STORE_SHARED(*root, yc);
 653         else if (z == z->p->left)
 654                 _STORE_SHARED(z->p->left, yc);
 655         else
 656                 _STORE_SHARED(z->p->right, yc);
 657
 658         if (x != &rcu_rbtree_nil) {
 659                 /* Reparent xc's children to xc. */
 660                 _STORE_SHARED(xc->right->p, xc);
 661                 _STORE_SHARED(xc->left->p, xc);
 662                 defer_rcu(rbfree, x);
 663         }
 664
 665         /* Reparent yc's children to yc */
 666         _STORE_SHARED(yc->right->p, yc);
 667         _STORE_SHARED(yc->left->p, yc);
 668         defer_rcu(rbfree, y);
 669
 670         return xc;
 671 }
 672
 673 int rcu_rbtree_remove(struct rcu_rbtree_node **root,
 674                       struct rcu_rbtree_node *z,
 675                       rcu_rbtree_comp comp,
 676                       rcu_rbtree_alloc rballoc,
 677                       rcu_rbtree_free rbfree)
 678 {
 679         struct rcu_rbtree_node *x, *y;
 680         unsigned int y_original_color;
 681
 682         y = z;
 683         y_original_color = y->color;
 684
 685         if (z->left == &rcu_rbtree_nil) {
 686                 x = rcu_rbtree_transplant(root, z, z->right, rballoc, rbfree);
 687         } else if (z->right == &rcu_rbtree_nil) {
 688                 x = rcu_rbtree_transplant(root, z, z->left, rballoc, rbfree);
 689         } else {
 690                 y = rcu_rbtree_min(z->right, comp);
 691                 y_original_color = y->color;
 692                 x = rcu_rbtree_remove_nonil(root, z, y, comp, rballoc, rbfree);
 693         }
 694         if (y_original_color == COLOR_BLACK)
 695                 rcu_rbtree_remove_fixup(root, x, rballoc, rbfree);
 696         /*
 697          * Commit all _STORE_SHARED().
 698          */
 699         smp_wmc();
 700
 701         return 0;
 702 }