urcu-rbtree.c

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