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