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