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