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