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