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