urcu-rbtree.c

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