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         int comp;
 393
 394         while (!rcu_rbtree_is_nil(x) && (comp = rbtree->comp(k, x->key)) != 0) {
 395                 usleep(10);
 396                 if (comp < 0)
 397                         x = rcu_dereference(x->_left);
 398                 else
 399                         x = rcu_dereference(x->_right);
 400         }
 401         return x;
 402 }
 403
 404 struct rcu_rbtree_node* rcu_rbtree_search_min(struct rcu_rbtree *rbtree,
 405                                           struct rcu_rbtree_node *x,
 406                                           void *range_low, void *range_high)
 407 {
 408         x = rcu_dereference(x);
 409
 410         while (!rcu_rbtree_is_nil(x)) {
 411                 usleep(10);
 412                 if (rbtree->comp(x->max_child_key, range_low) > 0) {
 413                         x = rcu_dereference(x->_left);
 414                 } else if (rbtree->comp(x->key, range_low) >= 0
 415                            && rbtree->comp(x->key, range_high) <= 0) {
 416                         break;
 417                 } else if (rbtree->comp(range_low, x->min_child_key) > 0) {
 418                         x = rcu_dereference(x->_right);
 419                 } else {
 420                         x = make_nil(rbtree);
 421                 }
 422         }
 423         return x;
 424 }
 425
 426 struct rcu_rbtree_node* rcu_rbtree_search_max(struct rcu_rbtree *rbtree,
 427                                           struct rcu_rbtree_node *x,
 428                                           void *range_low, void *range_high)
 429 {
 430         x = rcu_dereference(x);
 431
 432         while (!rcu_rbtree_is_nil(x)) {
 433                 usleep(10);
 434                 if (rbtree->comp(x->min_child_key, range_high) < 0) {
 435                         x = rcu_dereference(x->_right);
 436                 } else if (rbtree->comp(x->key, range_low) >= 0
 437                            && rbtree->comp(x->key, range_high) <= 0) {
 438                         break;
 439                 } else if (rbtree->comp(range_high, x->max_child_key) < 0) {
 440                         x = rcu_dereference(x->_left);
 441                 } else {
 442                         x = make_nil(rbtree);
 443                 }
 444         }
 445         return x;
 446 }
 447
 448 static
 449 struct rcu_rbtree_node *rcu_rbtree_min_dup_decay(struct rcu_rbtree *rbtree,
 450                                                  struct rcu_rbtree_node *x,
 451                                                  struct rcu_rbtree_node **zr)
 452 {
 453         struct rcu_rbtree_node *xl;
 454
 455         x = rcu_dereference(x);
 456
 457         if (rcu_rbtree_is_nil(x)) {
 458                 *zr = x;
 459                 return x;
 460         } else
 461                 *zr = x = dup_decay_node(rbtree, x);
 462
 463         while (!rcu_rbtree_is_nil(xl = rcu_dereference(x->_left))) {
 464                 x = dup_decay_node(rbtree, xl);
 465                 set_parent(x, get_decay(get_parent(x)), get_pos(x));
 466                 get_parent(x)->_left = get_decay(get_parent(x)->_left);
 467         }
 468         return x;
 469 }
 470
 471 static
 472 struct rcu_rbtree_node *rcu_rbtree_min_update_decay(struct rcu_rbtree *rbtree,
 473                                                     struct rcu_rbtree_node *x)
 474 {
 475         struct rcu_rbtree_node *xl;
 476
 477         x = rcu_dereference(x);
 478
 479         if (rcu_rbtree_is_nil(x))
 480                 return x;
 481         else {
 482                 set_parent(x->_right, get_decay(get_parent(x->_right)),
 483                            get_pos(x->_right));
 484                 set_parent(x->_left, get_decay(get_parent(x->_left)),
 485                            get_pos(x->_left));
 486         }
 487
 488         while (!rcu_rbtree_is_nil(xl = rcu_dereference(x->_left))) {
 489                 x = xl;
 490                 set_parent(x->_right, get_decay(get_parent(x->_right)),
 491                            get_pos(x->_right));
 492                 set_parent(x->_left, get_decay(get_parent(x->_left)),
 493                            get_pos(x->_left));
 494         }
 495         return x;
 496 }
 497
 498 struct rcu_rbtree_node *rcu_rbtree_min(struct rcu_rbtree *rbtree,
 499                                        struct rcu_rbtree_node *x)
 500 {
 501         struct rcu_rbtree_node *xl;
 502
 503         x = rcu_dereference(x);
 504
 505         if (rcu_rbtree_is_nil(x))
 506                 return x;
 507
 508         while (!rcu_rbtree_is_nil(xl = rcu_dereference(x->_left)))
 509                 x = xl;
 510         return x;
 511 }
 512
 513 struct rcu_rbtree_node *rcu_rbtree_max(struct rcu_rbtree *rbtree,
 514                                        struct rcu_rbtree_node *x)
 515 {
 516         struct rcu_rbtree_node *xr;
 517
 518         x = rcu_dereference(x);
 519
 520         if (rcu_rbtree_is_nil(x))
 521                 return x;
 522
 523         while (!rcu_rbtree_is_nil(xr = rcu_dereference(x->_right)))
 524                 x = xr;
 525         return x;
 526 }
 527
 528 /*
 529  * FIXME:
 530  * Updates should wait for a grace period between update of the
 531  * redirect pointer and update of the parent child pointer. This is to make sure
 532  * that no reference to the old entry exist.
 533  */
 534
 535 /*
 536  * RCU read lock must be held across the next/prev calls to ensure validity of
 537  * the returned node.
 538  */
 539 struct rcu_rbtree_node *rcu_rbtree_next(struct rcu_rbtree *rbtree,
 540                                         struct rcu_rbtree_node *x)
 541 {
 542         struct rcu_rbtree_node *xr, *y;
 543         unsigned int x_pos;
 544
 545         x = rcu_dereference(x);
 546
 547         if (!rcu_rbtree_is_nil(xr = rcu_dereference(x->_right)))
 548                 return rcu_rbtree_min(rbtree, xr);
 549         y = get_parent_and_pos(x, &x_pos);
 550         while (!rcu_rbtree_is_nil(y) && x_pos == IS_RIGHT) {
 551                 x = y;
 552                 y = get_parent_and_pos(y, &x_pos);
 553         }
 554         return y;
 555 }
 556
 557 struct rcu_rbtree_node *rcu_rbtree_prev(struct rcu_rbtree *rbtree,
 558                                         struct rcu_rbtree_node *x)
 559 {
 560         struct rcu_rbtree_node *xl, *y;
 561         unsigned int x_pos;
 562
 563         x = rcu_dereference(x);
 564
 565         if (!rcu_rbtree_is_nil(xl = rcu_dereference(x->_left)))
 566                 return rcu_rbtree_max(rbtree, xl);
 567         y = get_parent_and_pos(x, &x_pos);
 568         while (!rcu_rbtree_is_nil(y) && x_pos == IS_LEFT) {
 569                 x = y;
 570                 y = get_parent_and_pos(y, &x_pos);
 571         }
 572         return y;
 573 }
 574
 575 /*
 576  * We have to ensure these assumptions are correct for prev/next
 577  * traversal:
 578  *
 579  * with x being a right child, the assumption that:
 580  *   get_parent(x)->_right == x
 581  * or if x is a left child, the assumption that:
 582  *   get_parent(x)->_left == x
 583  *
 584  * This explains why we have to allocate a vc copy of the node for left_rotate,
 585  * right_rotate and transplant operations.
 586  *
 587  * We always ensure that the right/left child and correct parent is set in the
 588  * node copies *before* we reparent the children and make the upper-level point
 589  * to the copy.
 590  */
 591
 592 /* RCU: copy x and y, atomically point to new versions. GC old. */
 593 /* Should be eventually followed by a cmm_smp_wmc() */
 594
 595 #ifdef RBTREE_RCU_SUPPORT_ROTATE_LEFT
 596
 597 static
 598 void left_rotate(struct rcu_rbtree *rbtree,
 599                  struct rcu_rbtree_node *x)
 600 {
 601         struct rcu_rbtree_node *y, *y_left, *top, *top_child;
 602         unsigned int top_child_pos;
 603
 604         y = x->_right;
 605         y_left = y->_left;
 606
 607         /* Now operate on new copy, decay old versions */
 608         x = dup_decay_node(rbtree, x);
 609         y = dup_decay_node(rbtree, y);
 610         y_left = dup_decay_node(rbtree, y_left);
 611
 612         /* Internal node modifications */
 613         set_parent(y, get_parent(x), get_pos(x));
 614         set_parent(x, y, IS_LEFT);
 615         set_left_dup_decay(rbtree, y, x, &top, &top_child, &top_child_pos);
 616         set_right_dup_decay(rbtree, x, y_left, NULL, NULL, NULL);
 617         assert(!is_decay(top));
 618         assert(!is_decay(top_child));
 619
 620         if (!rcu_rbtree_is_nil(y_left))
 621                 set_parent(y_left, x, IS_RIGHT);
 622
 623         cmm_smp_wmb();  /* write into node before publish */
 624
 625         /* External references update (visible by readers) */
 626         if (rcu_rbtree_is_nil(top))
 627                 _CMM_STORE_SHARED(rbtree->root, top_child);
 628         else if (top_child_pos == IS_LEFT)
 629                 _CMM_STORE_SHARED(top->_left, top_child);
 630         else
 631                 _CMM_STORE_SHARED(top->_right, top_child);
 632
 633         /* Point children to new copy (parent only used by updates/next/prev) */
 634         set_parent(x->_left, get_decay(get_parent(x->_left)),
 635                 get_pos(x->_left));
 636         set_parent(y->_right, get_decay(get_parent(y->_right)),
 637                 get_pos(y->_right));
 638         if (!rcu_rbtree_is_nil(y_left)) {
 639                 set_parent(y_left->_right,
 640                         get_decay(get_parent(y_left->_right)),
 641                         get_pos(y_left->_right));
 642                 set_parent(y_left->_left,
 643                         get_decay(get_parent(y_left->_left)),
 644                         get_pos(y_left->_left));
 645         }
 646         set_left_update_decay(rbtree, y, x);
 647
 648         /* Sanity checks */
 649         assert(y == rbtree->root || get_parent(y)->_left == y
 650                 || get_parent(y)->_right == y);
 651         assert(x == rbtree->root || get_parent(x)->_left == x
 652                 || get_parent(x)->_right == x);
 653         assert(rcu_rbtree_is_nil(x->_right) || get_parent(x->_right) == x);
 654         assert(rcu_rbtree_is_nil(x->_left) || get_parent(x->_left) == x);
 655         assert(rcu_rbtree_is_nil(y->_right) || get_parent(y->_right) == y);
 656         assert(rcu_rbtree_is_nil(y->_left) || get_parent(y->_left) == y);
 657         assert(!is_decay(rbtree->root));
 658         assert(!is_decay(x));
 659         assert(!is_decay(y));
 660         assert(!is_decay(x->_right));
 661         assert(!is_decay(x->_left));
 662         assert(!is_decay(y->_right));
 663         assert(!is_decay(y->_left));
 664 }
 665
 666 #else
 667
 668 /* non-rcu version */
 669 static
 670 void left_rotate(struct rcu_rbtree *rbtree,
 671                  struct rcu_rbtree_node *x)
 672 {
 673         struct rcu_rbtree_node *y;
 674
 675         lock_test_mutex();
 676         y = x->_right;
 677         x->_right = y->_left;
 678         if (!rcu_rbtree_is_nil(y->_left))
 679                 set_parent(y->_left, x, IS_RIGHT);
 680         set_parent(y, get_parent(x), get_pos(x));
 681         if (rcu_rbtree_is_nil(get_parent(x)))
 682                 rbtree->root = y;
 683         else if (x == get_parent(x)->_left) {
 684                 get_parent(x)->_left = y;
 685         } else {
 686                 get_parent(x)->_right = y;
 687         }
 688         y->_left = x;
 689         set_parent(x, y, IS_LEFT);
 690         unlock_test_mutex();
 691 }
 692
 693 #endif
 694
 695 #ifdef RBTREE_RCU_SUPPORT_ROTATE_RIGHT
 696 static
 697 void right_rotate(struct rcu_rbtree *rbtree,
 698                   struct rcu_rbtree_node *x)
 699 {
 700         struct rcu_rbtree_node *y, *y_right, *top, *top_child;
 701         unsigned int top_child_pos;
 702
 703         y = x->_left;
 704         y_right = y->_right;
 705
 706         /* Now operate on new copy, decay old versions */
 707         x = dup_decay_node(rbtree, x);
 708         y = dup_decay_node(rbtree, y);
 709         y_right = dup_decay_node(rbtree, y_right);
 710
 711         /* Internal node modifications */
 712         set_parent(y, get_parent(x), get_pos(x));
 713         set_parent(x, y, IS_RIGHT);
 714         set_right_dup_decay(rbtree, y, x, &top, &top_child, &top_child_pos);
 715         set_left_dup_decay(rbtree, x, y_right, NULL, NULL, NULL);
 716         assert(!is_decay(top));
 717         assert(!is_decay(top_child));
 718
 719         if (!rcu_rbtree_is_nil(y_right))
 720                 set_parent(y_right, x, IS_LEFT);
 721
 722         cmm_smp_wmb();  /* write into node before publish */
 723
 724         /* External references update (visible by readers) */
 725         if (rcu_rbtree_is_nil(top))
 726                 _CMM_STORE_SHARED(rbtree->root, top_child);
 727         else if (top_child_pos == IS_RIGHT)
 728                 _CMM_STORE_SHARED(top->_right, top_child);
 729         else
 730                 _CMM_STORE_SHARED(top->_left, top_child);
 731
 732         /* Point children to new copy (parent only used by updates/next/prev) */
 733         set_parent(x->_right, get_decay(get_parent(x->_right)),
 734                 get_pos(x->_right));
 735         set_parent(y->_left, get_decay(get_parent(y->_left)),
 736                 get_pos(y->_left));
 737         if (!rcu_rbtree_is_nil(y_right)) {
 738                 set_parent(y_right->_left,
 739                         get_decay(get_parent(y_right->_left)),
 740                         get_pos(y_right->_left));
 741                 set_parent(y_right->_right,
 742                         get_decay(get_parent(y_right->_right)),
 743                         get_pos(y_right->_right));
 744         }
 745         set_right_update_decay(rbtree, y, x);
 746
 747
 748         /* Sanity checks */
 749         assert(y == rbtree->root || get_parent(y)->_right == y
 750                 || get_parent(y)->_left == y);
 751         assert(x == rbtree->root || get_parent(x)->_right == x
 752                 || get_parent(x)->_left == x);
 753         assert(rcu_rbtree_is_nil(x->_left) || get_parent(x->_left) == x);
 754         assert(rcu_rbtree_is_nil(x->_right) || get_parent(x->_right) == x);
 755         assert(rcu_rbtree_is_nil(y->_left) || get_parent(y->_left) == y);
 756         assert(rcu_rbtree_is_nil(y->_right) || get_parent(y->_right) == y);
 757         assert(!is_decay(rbtree->root));
 758         assert(!is_decay(x));
 759         assert(!is_decay(y));
 760         assert(!is_decay(x->_left));
 761         assert(!is_decay(x->_right));
 762         assert(!is_decay(y->_left));
 763         assert(!is_decay(y->_right));
 764 }
 765
 766 #else
 767
 768 /* non-rcu version */
 769 static
 770 void right_rotate(struct rcu_rbtree *rbtree,
 771                   struct rcu_rbtree_node *x)
 772 {
 773         struct rcu_rbtree_node *y;
 774
 775         lock_test_mutex();
 776         y = x->_left;
 777         x->_left = y->_right;
 778         if (!rcu_rbtree_is_nil(y->_right))
 779                 set_parent(y->_right, x, IS_LEFT);
 780         set_parent(y, get_parent(x), get_pos(x));
 781         if (rcu_rbtree_is_nil(get_parent(x)))
 782                 rbtree->root = y;
 783         else if (x == get_parent(x)->_right) {
 784                 get_parent(x)->_right = y;
 785         } else {
 786                 get_parent(x)->_left = y;
 787         }
 788         y->_right = x;
 789         set_parent(x, y, IS_RIGHT);
 790         unlock_test_mutex();
 791 }
 792
 793 #endif
 794
 795 static void rcu_rbtree_insert_fixup(struct rcu_rbtree *rbtree,
 796                                     struct rcu_rbtree_node *z)
 797 {
 798         struct rcu_rbtree_node *y;
 799
 800         dbg_printf("insert fixup %p\n", z->key);
 801         assert(!is_decay(rbtree->root));
 802
 803         while (get_parent(z)->color == COLOR_RED) {
 804                 if (get_parent(z) == get_parent(get_parent(z))->_left) {
 805                         y = get_parent(get_parent(z))->_right;
 806                         if (y->color == COLOR_RED) {
 807                                 get_parent(z)->color = COLOR_BLACK;
 808                                 y->color = COLOR_BLACK;
 809                                 get_parent(get_parent(z))->color = COLOR_RED;
 810                                 z = get_parent(get_parent(z));
 811                         } else {
 812                                 if (z == get_parent(z)->_right) {
 813                                         z = get_parent(z);
 814                                         left_rotate(rbtree, z);
 815                                         z = get_decay(z);
 816                                         assert(!is_decay(rbtree->root));
 817                                 }
 818                                 get_parent(z)->color = COLOR_BLACK;
 819                                 get_parent(get_parent(z))->color = COLOR_RED;
 820                                 assert(!is_decay(z));
 821                                 assert(!is_decay(get_parent(z)));
 822                                 assert(!is_decay(get_parent(get_parent(z))));
 823                                 right_rotate(rbtree, get_parent(get_parent(z)));
 824                                 assert(!is_decay(z));
 825                                 assert(!is_decay(rbtree->root));
 826                         }
 827                 } else {
 828                         y = get_parent(get_parent(z))->_left;
 829                         if (y->color == COLOR_RED) {
 830                                 get_parent(z)->color = COLOR_BLACK;
 831                                 y->color = COLOR_BLACK;
 832                                 get_parent(get_parent(z))->color = COLOR_RED;
 833                                 z = get_parent(get_parent(z));
 834                         } else {
 835                                 if (z == get_parent(z)->_left) {
 836                                         z = get_parent(z);
 837                                         right_rotate(rbtree, z);
 838                                         z = get_decay(z);
 839                                         assert(!is_decay(rbtree->root));
 840                                 }
 841                                 get_parent(z)->color = COLOR_BLACK;
 842                                 get_parent(get_parent(z))->color = COLOR_RED;
 843                                 left_rotate(rbtree, get_parent(get_parent(z)));
 844                                 assert(!is_decay(z));
 845                                 assert(!is_decay(rbtree->root));
 846                         }
 847                 }
 848         }
 849         rbtree->root->color = COLOR_BLACK;
 850 }
 851
 852 /*
 853  * rcu_rbtree_insert - Insert a node in the RCU rbtree
 854  *
 855  * Returns 0 on success, or < 0 on error.
 856  */
 857 int rcu_rbtree_insert(struct rcu_rbtree *rbtree,
 858                       struct rcu_rbtree_node *z)
 859 {
 860         struct rcu_rbtree_node *x, *y, *top, *top_child;
 861         unsigned int top_child_pos;
 862
 863         dbg_printf("insert %p\n", z->key);
 864         assert(!is_decay(rbtree->root));
 865
 866         y = make_nil(rbtree);
 867         x = rbtree->root;
 868         while (!rcu_rbtree_is_nil(x)) {
 869                 y = x;
 870                 if (rbtree->comp(z->key, x->key) < 0)
 871                         x = x->_left;
 872                 else
 873                         x = x->_right;
 874         }
 875
 876         z->_left = make_nil(rbtree);
 877         z->_right = make_nil(rbtree);
 878         z->min_child_key = z->key;
 879         z->max_child_key = z->key;
 880         z->color = COLOR_RED;
 881         z->nil = 0;
 882         z->decay_next = NULL;
 883
 884         if (rcu_rbtree_is_nil(y))
 885                 set_parent(z, y, IS_RIGHT); /* pos arbitrary for root node */
 886         else if (rbtree->comp(z->key, y->key) < 0)
 887                 set_parent(z, y, IS_LEFT);
 888         else
 889                 set_parent(z, y, IS_RIGHT);
 890
 891         /*
 892          * Order stores to z (children/parents) before stores that will make it
 893          * visible to the rest of the tree.
 894          */
 895         cmm_smp_wmb();
 896
 897         if (rcu_rbtree_is_nil(y)) {
 898                 _CMM_STORE_SHARED(rbtree->root, z);
 899         } else if (rbtree->comp(z->key, y->key) < 0) {
 900                 set_left_dup_decay(rbtree, y, z, &top, &top_child,
 901                                 &top_child_pos);
 902                 if (rcu_rbtree_is_nil(top))
 903                         _CMM_STORE_SHARED(rbtree->root, top_child);
 904                 else if (top_child_pos == IS_LEFT)
 905                         _CMM_STORE_SHARED(top->_left, top_child);
 906                 else
 907                         _CMM_STORE_SHARED(top->_right, top_child);
 908                 set_left_update_decay(rbtree, y, z);
 909         } else {
 910                 set_right_dup_decay(rbtree, y, z, &top, &top_child,
 911                                 &top_child_pos);
 912                 if (rcu_rbtree_is_nil(top))
 913                         _CMM_STORE_SHARED(rbtree->root, top_child);
 914                 else if (top_child_pos == IS_LEFT)
 915                         _CMM_STORE_SHARED(top->_left, top_child);
 916                 else
 917                         _CMM_STORE_SHARED(top->_right, top_child);
 918                 set_right_update_decay(rbtree, y, z);
 919         }
 920         rcu_rbtree_insert_fixup(rbtree, z);
 921         /*
 922          * Make sure to commit all _CMM_STORE_SHARED() for non-coherent caches.
 923          */
 924         cmm_smp_wmc();
 925         show_tree(rbtree);
 926
 927         return 0;
 928 }
 929
 930 /*
 931  * Transplant v into u position.
 932  */
 933
 934 #ifdef RBTREE_RCU_SUPPORT_TRANSPLANT
 935
 936 static
 937 void rcu_rbtree_transplant(struct rcu_rbtree *rbtree,
 938                         struct rcu_rbtree_node *u,
 939                         struct rcu_rbtree_node *v,
 940                         unsigned int copy_parents)
 941 {
 942         struct rcu_rbtree_node *top, *top_child;
 943         unsigned int top_child_pos;
 944
 945         dbg_printf("transplant %p\n", v->key);
 946
 947         if (!rcu_rbtree_is_nil(v))
 948                 v = dup_decay_node(rbtree, v);
 949
 950         if (rcu_rbtree_is_nil(get_parent(u))) {
 951                 /* pos is arbitrary for root node */
 952                 set_parent(v, get_parent(u), IS_RIGHT);
 953                 cmm_smp_wmb();  /* write into node before publish */
 954                 _CMM_STORE_SHARED(rbtree->root, v);
 955         } else {
 956                 set_parent(v, get_parent(u), get_pos(u));
 957                 cmm_smp_wmb();  /* write into node before publish */
 958
 959                 if (get_pos(u) == IS_LEFT) {
 960                         _set_left_dup_decay(rbtree, get_parent(u), v,
 961                                         &top, &top_child, &top_child_pos,
 962                                         copy_parents);
 963                 } else {
 964                         assert(copy_parents);
 965                         set_right_dup_decay(rbtree, get_parent(u), v,
 966                                         &top, &top_child, &top_child_pos);
 967                 }
 968
 969                 if (rcu_rbtree_is_nil(top))
 970                         _CMM_STORE_SHARED(rbtree->root, top_child);
 971                 else if (top_child_pos == IS_LEFT)
 972                         _CMM_STORE_SHARED(top->_left, top_child);
 973                 else
 974                         _CMM_STORE_SHARED(top->_right, top_child);
 975
 976                 /* Point children to new copy (parent only used by updates/next/prev) */
 977                 if (get_pos(u) == IS_LEFT) {
 978                         if (copy_parents)
 979                                 set_left_update_decay(rbtree, get_parent(u), v);
 980                 } else {
 981                         assert(copy_parents);
 982                         set_right_update_decay(rbtree, get_parent(u), v);
 983                 }
 984         }
 985
 986         /* Point children to new copy (parent only used by updates/next/prev) */
 987         if (!rcu_rbtree_is_nil(v)) {
 988                 set_parent(v->_right, get_decay(get_parent(v->_right)),
 989                         get_pos(v->_right));
 990                 set_parent(v->_left, get_decay(get_parent(v->_left)),
 991                         get_pos(v->_left));
 992         }
 993         assert(!is_decay(rbtree->root));
 994 }
 995
 996 #else
 997
 998 /* Non-RCU version */
 999 static
1000 void rcu_rbtree_transplant(struct rcu_rbtree *rbtree,
1001                            struct rcu_rbtree_node *u,
1002                            struct rcu_rbtree_node *v,
1003                            unsigned int copy_parents)
1004 {
1005         dbg_printf("transplant %p\n", v->key);
1006
1007         lock_test_mutex();
1008         if (rcu_rbtree_is_nil(get_parent(u)))
1009                 rbtree->root = v;
1010         else if (u == get_parent(u)->_left)
1011                 get_parent(u)->_left = v;
1012         else
1013                 get_parent(u)->_right = v;
1014         set_parent(v, get_parent(u), get_pos(u));
1015         unlock_test_mutex();
1016 }
1017
1018 #endif
1019
1020 static void rcu_rbtree_remove_fixup(struct rcu_rbtree *rbtree,
1021                                     struct rcu_rbtree_node *x)
1022 {
1023         dbg_printf("remove fixup %p\n", x->key);
1024
1025         while (x != rbtree->root && x->color == COLOR_BLACK) {
1026                 assert(!is_decay(get_parent(x)));
1027                 assert(!is_decay(get_parent(x)->_left));
1028                 if (x == get_parent(x)->_left) {
1029                         struct rcu_rbtree_node *w;
1030
1031                         w = get_parent(x)->_right;
1032
1033                         if (w->color == COLOR_RED) {
1034                                 w->color = COLOR_BLACK;
1035                                 get_parent(x)->color = COLOR_RED;
1036                                 left_rotate(rbtree, get_parent(x));
1037                                 x = get_decay(x);
1038                                 assert(!is_decay(rbtree->root));
1039                                 w = get_parent(x)->_right;
1040                         }
1041                         if (w->_left->color == COLOR_BLACK
1042                             && w->_right->color == COLOR_BLACK) {
1043                                 w->color = COLOR_RED;
1044                                 x = get_parent(x);
1045                                 assert(!is_decay(rbtree->root));
1046                                 assert(!is_decay(x));
1047                         } else {
1048                                 if (w->_right->color == COLOR_BLACK) {
1049                                         w->_left->color = COLOR_BLACK;
1050                                         w->color = COLOR_RED;
1051                                         right_rotate(rbtree, w);
1052                                         assert(!is_decay(rbtree->root));
1053                                         x = get_decay(x);
1054                                         w = get_parent(x)->_right;
1055                                 }
1056                                 w->color = get_parent(x)->color;
1057                                 get_parent(x)->color = COLOR_BLACK;
1058                                 w->_right->color = COLOR_BLACK;
1059                                 left_rotate(rbtree, get_parent(x));
1060                                 assert(!is_decay(rbtree->root));
1061                                 x = rbtree->root;
1062                         }
1063                 } else {
1064                         struct rcu_rbtree_node *w;
1065
1066                         w = get_parent(x)->_left;
1067
1068                         if (w->color == COLOR_RED) {
1069                                 w->color = COLOR_BLACK;
1070                                 get_parent(x)->color = COLOR_RED;
1071                                 right_rotate(rbtree, get_parent(x));
1072                                 assert(!is_decay(rbtree->root));
1073                                 x = get_decay(x);
1074                                 w = get_parent(x)->_left;
1075                         }
1076                         if (w->_right->color == COLOR_BLACK
1077                             && w->_left->color == COLOR_BLACK) {
1078                                 w->color = COLOR_RED;
1079                                 x = get_parent(x);
1080                                 assert(!is_decay(rbtree->root));
1081                                 assert(!is_decay(x));
1082                         } else {
1083                                 if (w->_left->color == COLOR_BLACK) {
1084                                         w->_right->color = COLOR_BLACK;
1085                                         w->color = COLOR_RED;
1086                                         left_rotate(rbtree, w);
1087                                         assert(!is_decay(rbtree->root));
1088                                         x = get_decay(x);
1089                                         w = get_parent(x)->_left;
1090                                 }
1091                                 w->color = get_parent(x)->color;
1092                                 get_parent(x)->color = COLOR_BLACK;
1093                                 w->_left->color = COLOR_BLACK;
1094                                 right_rotate(rbtree, get_parent(x));
1095                                 assert(!is_decay(rbtree->root));
1096                                 x = rbtree->root;
1097                         }
1098                 }
1099         }
1100         x->color = COLOR_BLACK;
1101 }
1102
1103 /*
1104  * Delete z. All non-copied children left/right positions are unchanged.
1105  */
1106 static
1107 void rcu_rbtree_remove_nonil(struct rcu_rbtree *rbtree,
1108                              struct rcu_rbtree_node *z,
1109                              struct rcu_rbtree_node *y)
1110 {
1111         struct rcu_rbtree_node *x, *top, *top_child;
1112         unsigned int top_child_pos;
1113
1114         dbg_printf("remove nonil %p\n", z->key);
1115         show_tree(rbtree);
1116
1117         assert(!is_decay(z));
1118         assert(!is_decay(y));
1119         assert(!is_decay(y->_right));
1120         assert(!is_decay(get_parent(y)));
1121         x = y->_right;
1122         assert(!is_decay(x));
1123         if (get_parent(y) == z) {
1124                 y = dup_decay_node(rbtree, y);
1125                 set_parent(x, y, get_pos(x));   /* parent for nil */
1126                 /* y is z's right node: set left will just update y */
1127                 set_left_dup_decay(rbtree, y, z->_left,
1128                                 &top, &top_child, &top_child_pos);
1129                 assert(top_child == y);
1130                 rcu_rbtree_transplant(rbtree, z, y, 1);
1131         } else {
1132                 struct rcu_rbtree_node *oy_right, *z_right;
1133
1134                 /*
1135                  * Need to make sure y is always visible by readers.
1136                  */
1137                 y = rcu_rbtree_min_dup_decay(rbtree, z->_right, &z_right);
1138                 assert(!is_decay(y));
1139                 assert(!is_decay(z));
1140                 oy_right = y->_right;
1141
1142                 /*
1143                  * The max child key of z_right does not change, because
1144                  * we're only changing its left children.
1145                  */
1146                 y->_right = z_right;
1147                 set_parent(y->_right, y, IS_RIGHT);
1148                 if (rcu_rbtree_is_nil(y->_right))
1149                         y->max_child_key = y->key;
1150                 else
1151                         y->max_child_key = y->_right->max_child_key;
1152
1153                 assert(!is_decay(z->_left));
1154                 y->_left = z->_left;
1155                 if (rcu_rbtree_is_nil(y->_left))
1156                         y->min_child_key = y->key;
1157                 else
1158                         y->min_child_key = y->_left->min_child_key;
1159
1160                 assert(!is_decay(oy_right));
1161                 /*
1162                  * Transplant of oy_right to old y's location will only
1163                  * trigger a min/max update of the already copied branch
1164                  * (which is not visible yet). We are transplanting
1165                  * oy_right as a left child of old y's parent, so the
1166                  * min values update propagated upward necessarily stops
1167                  * at z_right.
1168                  */
1169                 rcu_rbtree_transplant(rbtree, y, oy_right, 0);
1170                 rcu_rbtree_transplant(rbtree, z, y, 1);
1171                 /* Update children */
1172                 (void) rcu_rbtree_min_update_decay(rbtree, y->_right);
1173         }
1174         y = get_decay(y);
1175         assert(!is_decay(z));
1176         assert(!is_decay(z->_left));
1177         y->color = z->color;
1178         set_parent(y->_left, y, IS_LEFT);
1179         set_parent(y->_right, get_decay(get_parent(y->_right)), IS_RIGHT);
1180         assert(!is_decay(y->_left));
1181         assert(!is_decay(y->_right));
1182 }
1183
1184 int rcu_rbtree_remove(struct rcu_rbtree *rbtree,
1185                       struct rcu_rbtree_node *z)
1186 {
1187         struct rcu_rbtree_node *x, *y;
1188         unsigned int y_original_color;
1189
1190         assert(!is_decay(rbtree->root));
1191         dbg_printf("remove %p\n", z->key);
1192         show_tree(rbtree);
1193
1194         assert(!is_decay(z));
1195         y = z;
1196         y_original_color = y->color;
1197
1198         if (rcu_rbtree_is_nil(z->_left)) {
1199                 rcu_rbtree_transplant(rbtree, z, z->_right, 1);
1200                 assert(!is_decay(z));
1201                 x = get_decay(z->_right);
1202                 show_tree(rbtree);
1203         } else if (rcu_rbtree_is_nil(z->_right)) {
1204                 rcu_rbtree_transplant(rbtree, z, z->_left, 1);
1205                 assert(!is_decay(z));
1206                 x = get_decay(z->_left);
1207                 show_tree(rbtree);
1208         } else {
1209                 y = rcu_rbtree_min(rbtree, z->_right);
1210                 assert(!is_decay(y));
1211                 y_original_color = y->color;
1212                 x = y->_right;
1213                 rcu_rbtree_remove_nonil(rbtree, z, y);
1214                 x = get_decay(x);
1215                 show_tree(rbtree);
1216         }
1217         if (y_original_color == COLOR_BLACK)
1218                 rcu_rbtree_remove_fixup(rbtree, x);
1219         show_tree(rbtree);
1220         /*
1221          * Commit all _CMM_STORE_SHARED().
1222          */
1223         cmm_smp_wmc();
1224
1225         return 0;
1226 }