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