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