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
  38 #include <urcu/rcurbtree.h>
  39 #include <urcu-pointer.h>
  40 #include <urcu-defer.h>
  41
  42 #define DEBUG
  43
  44 #ifdef DEBUG
  45 #define dbg_printf(args...)     printf(args)
  46 #else
  47 #define dbg_printf(args...)
  48 #endif
  49
  50 static
  51 void set_decay(struct rcu_rbtree_node *x, struct rcu_rbtree_node *xc)
  52 {
  53         x->decay_next = xc;
  54 }
  55
  56 static
  57 struct rcu_rbtree_node *get_decay(struct rcu_rbtree_node *x)
  58 {
  59         while (x->decay_next)
  60                 x = x->decay_next;
  61         return x;
  62 }
  63
  64 static
  65 struct rcu_rbtree_node *is_decay(struct rcu_rbtree_node *x)
  66 {
  67         return x->decay_next;
  68 }
  69
  70 static
  71 struct rcu_rbtree_node *dup_decay_node(struct rcu_rbtree *rbtree,
  72                                 struct rcu_rbtree_node *x)
  73 {
  74         struct rcu_rbtree_node *xc;
  75
  76         if (rcu_rbtree_is_nil(x))
  77                 return x;
  78
  79         xc = rbtree->rballoc();
  80         memcpy(xc, x, sizeof(struct rcu_rbtree_node));
  81         xc->decay_next = NULL;
  82         set_decay(x, xc);
  83         defer_rcu(rbtree->rbfree, x);
  84         return xc;
  85 }
  86
  87 /*
  88  * TODO
  89  * Deal with memory allocation errors.
  90  * Can be ensured by reserving a pool of memory entries before doing the
  91  * insertion, which will have to be function of number of
  92  * transplantations/rotations required for the operation.
  93  */
  94
  95 static
  96 void show_tree(struct rcu_rbtree *rbtree)
  97 {
  98         struct rcu_rbtree_node *node;
  99
 100         node = rcu_rbtree_min(rbtree, rbtree->root);
 101         while (!rcu_rbtree_is_nil(node)) {
 102                 assert(!is_decay(node));
 103                 printf("{ 0x%lX p:%lX r:%lX l:%lX %s %s %s} ",
 104                         (unsigned long)node->key,
 105                         (unsigned long) node->p->key,
 106                         (unsigned long) node->right->key,
 107                         (unsigned long) node->left->key,
 108                         node->color ? "red" : "black",
 109                         node->pos ? "right" : "left",
 110                         node->nil ? "nil" : "");
 111                 node = rcu_rbtree_next(rbtree, node);
 112         }
 113         printf("\n");
 114 }
 115
 116 static
 117 struct rcu_rbtree_node *make_nil(struct rcu_rbtree *rbtree)
 118 {
 119         return &rbtree->nil_node;
 120 }
 121
 122 /*
 123  * Iterative rbtree search.
 124  */
 125 struct rcu_rbtree_node* rcu_rbtree_search(struct rcu_rbtree *rbtree,
 126                                           struct rcu_rbtree_node *x,
 127                                           void *k)
 128 {
 129         x = rcu_dereference(x);
 130
 131         while (!rcu_rbtree_is_nil(x) && k != x->key) {
 132                 if (rbtree->comp(k, x->key) < 0)
 133                         x = rcu_dereference(x->left);
 134                 else
 135                         x = rcu_dereference(x->right);
 136         }
 137         return x;
 138 }
 139
 140 struct rcu_rbtree_node *rcu_rbtree_min(struct rcu_rbtree *rbtree,
 141                                        struct rcu_rbtree_node *x)
 142 {
 143         struct rcu_rbtree_node *xl;
 144
 145         x = rcu_dereference(x);
 146
 147         if (rcu_rbtree_is_nil(x))
 148                 return x;
 149
 150         while (!rcu_rbtree_is_nil(xl = rcu_dereference(x->left)))
 151                 x = xl;
 152         return x;
 153 }
 154
 155 struct rcu_rbtree_node *rcu_rbtree_max(struct rcu_rbtree *rbtree,
 156                                        struct rcu_rbtree_node *x)
 157 {
 158         struct rcu_rbtree_node *xr;
 159
 160         x = rcu_dereference(x);
 161
 162         if (rcu_rbtree_is_nil(x))
 163                 return x;
 164
 165         while (!rcu_rbtree_is_nil(xr = rcu_dereference(x->right)))
 166                 x = xr;
 167         return x;
 168 }
 169
 170 /*
 171  * FIXME:
 172  * Updates should wait for a grace period between update of the
 173  * redirect pointer and update of the parent child pointer. This is to make sure
 174  * that no reference to the old entry exist.
 175  */
 176
 177 /*
 178  * next and prev need to have mutex held to ensure that parent pointer is
 179  * coherent.
 180  */
 181 struct rcu_rbtree_node *rcu_rbtree_next(struct rcu_rbtree *rbtree,
 182                                         struct rcu_rbtree_node *x)
 183 {
 184         struct rcu_rbtree_node *xr, *y;
 185
 186         x = rcu_dereference(x);
 187
 188         if (!rcu_rbtree_is_nil(xr = rcu_dereference(x->right)))
 189                 return rcu_rbtree_min(rbtree, xr);
 190         y = rcu_dereference(x->p);
 191         while (!rcu_rbtree_is_nil(y) && x->pos == IS_RIGHT) {
 192                 x = y;
 193                 y = rcu_dereference(y->p);
 194         }
 195         return y;
 196 }
 197
 198 struct rcu_rbtree_node *rcu_rbtree_prev(struct rcu_rbtree *rbtree,
 199                                         struct rcu_rbtree_node *x)
 200 {
 201         struct rcu_rbtree_node *xl, *y;
 202
 203         x = rcu_dereference(x);
 204
 205         if (!rcu_rbtree_is_nil(xl = rcu_dereference(x->left)))
 206                 return rcu_rbtree_min(rbtree, xl);
 207         y = rcu_dereference(x->p);
 208         while (!rcu_rbtree_is_nil(y) && x->pos == IS_LEFT) {
 209                 x = y;
 210                 y = rcu_dereference(y->p);
 211         }
 212         return y;
 213 }
 214
 215 /*
 216  * We have to ensure these assumptions are correct for prev/next
 217  * traversal:
 218  *
 219  * with x being a right child, the assumption that:
 220  *   x->p->right == x
 221  * or if x is a left child, the assumption that:
 222  *   x->p->left == x
 223  *
 224  * This explains why we have to allocate a vc copy of the node for left_rotate,
 225  * right_rotate and transplant operations.
 226  *
 227  * We always ensure that the right/left child and correct parent is set in the
 228  * node copies *before* we reparent the children and make the upper-level point
 229  * to the copy.
 230  */
 231
 232 /* RCU: copy x and y, atomically point to new versions. GC old. */
 233 /* Should be eventually followed by a cmm_smp_wmc() */
 234
 235 static
 236 void left_rotate(struct rcu_rbtree *rbtree,
 237                  struct rcu_rbtree_node *x)
 238 {
 239         struct rcu_rbtree_node *y;
 240
 241         y = x->right;
 242
 243         /* Now operate on new copy, decay old versions */
 244         x = dup_decay_node(rbtree, x);
 245         y = dup_decay_node(rbtree, y);
 246
 247         x->right = y->left;
 248         if (!rcu_rbtree_is_nil(y->left)) {
 249                 y->left->p = x;
 250                 y->left->pos = IS_RIGHT;
 251         }
 252         y->p = x->p;
 253         if (rcu_rbtree_is_nil(x->p))
 254                 rbtree->root = y;
 255         else if (x->pos == IS_LEFT) {
 256                 x->p->left = y;
 257                 y->pos = IS_LEFT;
 258         } else {
 259                 x->p->right = y;
 260                 y->pos = IS_RIGHT;
 261         }
 262         y->left = x;
 263         x->pos = IS_LEFT;
 264         x->p = y;
 265         /* Point children to new copy */
 266         if (!rcu_rbtree_is_nil(x->left))
 267                 x->left->p = x;
 268         if (!rcu_rbtree_is_nil(y->right))
 269                 y->right->p = y;
 270
 271         /* Sanity checks */
 272         assert(y == rbtree->root || y->p->left == y || y->p->right == y);
 273         assert(x == rbtree->root || x->p->left == x || x->p->right == x);
 274         assert(rcu_rbtree_is_nil(x->right) || x->right->p == x);
 275         assert(rcu_rbtree_is_nil(x->left) || x->left->p == x);
 276         assert(rcu_rbtree_is_nil(y->right) || y->right->p == y);
 277         assert(rcu_rbtree_is_nil(y->left) || y->left->p == y);
 278         assert(!is_decay(rbtree->root));
 279         assert(!is_decay(x));
 280         assert(!is_decay(y));
 281         assert(!is_decay(x->right));
 282         assert(!is_decay(x->left));
 283         assert(!is_decay(y->right));
 284         assert(!is_decay(y->left));
 285 }
 286
 287 static
 288 void right_rotate(struct rcu_rbtree *rbtree,
 289                   struct rcu_rbtree_node *x)
 290 {
 291         struct rcu_rbtree_node *y;
 292
 293         y = x->left;
 294
 295         /* Now operate on new copy, decay old versions */
 296         x = dup_decay_node(rbtree, x);
 297         y = dup_decay_node(rbtree, y);
 298
 299         x->left = y->right;
 300         if (!rcu_rbtree_is_nil(y->right)) {
 301                 y->right->p = x;
 302                 y->right->pos = IS_LEFT;
 303         }
 304         y->p = x->p;
 305         if (rcu_rbtree_is_nil(x->p))
 306                 rbtree->root = y;
 307         else if (x->pos == IS_RIGHT) {
 308                 x->p->right = y;
 309                 y->pos = IS_RIGHT;
 310         } else {
 311                 x->p->left = y;
 312                 y->pos = IS_LEFT;
 313         }
 314         y->right = x;
 315         x->pos = IS_RIGHT;
 316         x->p = y;
 317         /* Point children to new copy */
 318         if (!rcu_rbtree_is_nil(x->right))
 319                 x->right->p = x;
 320         if (!rcu_rbtree_is_nil(y->left))
 321                 y->left->p = y;
 322
 323         /* Sanity checks */
 324         assert(y == rbtree->root || y->p->right == y || y->p->left == y);
 325         assert(x == rbtree->root || x->p->right == x || x->p->left == x);
 326         assert(rcu_rbtree_is_nil(x->left) || x->left->p == x);
 327         assert(rcu_rbtree_is_nil(x->right) || x->right->p == x);
 328         assert(rcu_rbtree_is_nil(y->left) || y->left->p == y);
 329         assert(rcu_rbtree_is_nil(y->right) || y->right->p == y);
 330         assert(!is_decay(rbtree->root));
 331         assert(!is_decay(x));
 332         assert(!is_decay(y));
 333         assert(!is_decay(x->left));
 334         assert(!is_decay(x->right));
 335         assert(!is_decay(y->left));
 336         assert(!is_decay(y->right));
 337 }
 338
 339 static void rcu_rbtree_insert_fixup(struct rcu_rbtree *rbtree,
 340                                     struct rcu_rbtree_node *z)
 341 {
 342         struct rcu_rbtree_node *y;
 343
 344         dbg_printf("insert fixup %p\n", z->key);
 345         assert(!is_decay(rbtree->root));
 346
 347         while (z->p->color == COLOR_RED) {
 348                 if (z->p == z->p->p->left) {
 349                         y = z->p->p->right;
 350                         if (y->color == COLOR_RED) {
 351                                 z->p->color = COLOR_BLACK;
 352                                 y->color = COLOR_BLACK;
 353                                 z->p->p->color = COLOR_RED;
 354                                 z = z->p->p;
 355                         } else {
 356                                 if (z == z->p->right) {
 357                                         z = z->p;
 358                                         left_rotate(rbtree, z);
 359                                         z = get_decay(z);
 360                                         assert(!is_decay(rbtree->root));
 361                                 }
 362                                 z->p->color = COLOR_BLACK;
 363                                 z->p->p->color = COLOR_RED;
 364                                 assert(!is_decay(z));
 365                                 assert(!is_decay(z->p));
 366                                 assert(!is_decay(z->p->p));
 367                                 right_rotate(rbtree, z->p->p);
 368                                 assert(!is_decay(z));
 369                                 assert(!is_decay(rbtree->root));
 370                         }
 371                 } else {
 372                         y = z->p->p->left;
 373                         if (y->color == COLOR_RED) {
 374                                 z->p->color = COLOR_BLACK;
 375                                 y->color = COLOR_BLACK;
 376                                 z->p->p->color = COLOR_RED;
 377                                 z = z->p->p;
 378                         } else {
 379                                 if (z == z->p->left) {
 380                                         z = z->p;
 381                                         right_rotate(rbtree, z);
 382                                         z = get_decay(z);
 383                                         assert(!is_decay(rbtree->root));
 384                                 }
 385                                 z->p->color = COLOR_BLACK;
 386                                 z->p->p->color = COLOR_RED;
 387                                 left_rotate(rbtree, z->p->p);
 388                                 assert(!is_decay(z));
 389                                 assert(!is_decay(rbtree->root));
 390                         }
 391                 }
 392         }
 393         rbtree->root->color = COLOR_BLACK;
 394 }
 395
 396 /*
 397  * rcu_rbtree_insert - Insert a node in the RCU rbtree
 398  *
 399  * Returns 0 on success, or < 0 on error.
 400  */
 401 int rcu_rbtree_insert(struct rcu_rbtree *rbtree,
 402                       struct rcu_rbtree_node *z)
 403 {
 404         struct rcu_rbtree_node *x, *y;
 405
 406         dbg_printf("insert %p\n", z->key);
 407         assert(!is_decay(rbtree->root));
 408
 409         y = make_nil(rbtree);
 410         if (!rbtree->root)
 411                 rbtree->root = make_nil(rbtree);
 412         x = rbtree->root;
 413         while (!rcu_rbtree_is_nil(x)) {
 414                 y = x;
 415                 if (rbtree->comp(z->key, x->key) < 0)
 416                         x = x->left;
 417                 else
 418                         x = x->right;
 419         }
 420
 421         z->p = y;
 422
 423         z->left = make_nil(rbtree);
 424         z->right = make_nil(rbtree);
 425         z->color = COLOR_RED;
 426         z->nil = 0;
 427         z->decay_next = NULL;
 428
 429         if (rcu_rbtree_is_nil(y))
 430                 z->pos = IS_RIGHT;      /* arbitrary for root node */
 431         else if (rbtree->comp(z->key, y->key) < 0)
 432                 z->pos = IS_LEFT;
 433         else
 434                 z->pos = IS_RIGHT;
 435
 436         /*
 437          * Order stores to z (children/parents) before stores that will make it
 438          * visible to the rest of the tree.
 439          */
 440         cmm_smp_wmb();
 441
 442         if (rcu_rbtree_is_nil(y))
 443                 _CMM_STORE_SHARED(rbtree->root, z);
 444         else if (rbtree->comp(z->key, y->key) < 0)
 445                 _CMM_STORE_SHARED(y->left, z);
 446         else
 447                 _CMM_STORE_SHARED(y->right, z);
 448         rcu_rbtree_insert_fixup(rbtree, z);
 449         /*
 450          * Make sure to commit all _CMM_STORE_SHARED() for non-coherent caches.
 451          */
 452         cmm_smp_wmc();
 453         show_tree(rbtree);
 454
 455         return 0;
 456 }
 457
 458 /*
 459  * Transplant v into u position.
 460  */
 461 static
 462 void rcu_rbtree_transplant(struct rcu_rbtree *rbtree,
 463                         struct rcu_rbtree_node *u,
 464                         struct rcu_rbtree_node *v)
 465 {
 466         dbg_printf("transplant %p\n", v->key);
 467
 468         if (rcu_rbtree_is_nil(u->p))
 469                 rbtree->root = v;
 470         else if (u == u->p->left) {
 471                 u->p->left = v;
 472                 v->pos = IS_LEFT;
 473         } else {
 474                 u->p->right = v;
 475                 v->pos = IS_RIGHT;
 476         }
 477         v->p = u->p;
 478         assert(!is_decay(rbtree->root));
 479 }
 480
 481 static void rcu_rbtree_remove_fixup(struct rcu_rbtree *rbtree,
 482                                     struct rcu_rbtree_node *x)
 483 {
 484         dbg_printf("remove fixup %p\n", x->key);
 485
 486         while (x != rbtree->root && x->color == COLOR_BLACK) {
 487                 if (x == x->p->left) {
 488                         struct rcu_rbtree_node *w;
 489
 490                         w = x->p->right;
 491
 492                         if (w->color == COLOR_RED) {
 493                                 w->color = COLOR_BLACK;
 494                                 x->p->color = COLOR_RED;
 495                                 left_rotate(rbtree, x->p);
 496                                 x = get_decay(x);
 497                                 assert(!is_decay(rbtree->root));
 498                                 w = x->p->right;
 499                         }
 500                         if (w->left->color == COLOR_BLACK
 501                             && w->right->color == COLOR_BLACK) {
 502                                 w->color = COLOR_RED;
 503                                 x = x->p;
 504                         } else {
 505                                 if (w->right->color == COLOR_BLACK) {
 506                                         w->left->color = COLOR_BLACK;
 507                                         w->color = COLOR_RED;
 508                                         right_rotate(rbtree, w);
 509                                         x = get_decay(x);
 510                                         w = x->p->right;
 511                                 }
 512                                 w->color = x->p->color;
 513                                 x->p->color = COLOR_BLACK;
 514                                 w->right->color = COLOR_BLACK;
 515                                 left_rotate(rbtree, x->p);
 516                                 assert(!is_decay(rbtree->root));
 517                                 x = rbtree->root;
 518                         }
 519                 } else {
 520                         struct rcu_rbtree_node *w;
 521
 522                         w = x->p->left;
 523
 524                         if (w->color == COLOR_RED) {
 525                                 w->color = COLOR_BLACK;
 526                                 x->p->color = COLOR_RED;
 527                                 right_rotate(rbtree, x->p);
 528                                 x = get_decay(x);
 529                                 w = x->p->left;
 530                         }
 531                         if (w->right->color == COLOR_BLACK
 532                             && w->left->color == COLOR_BLACK) {
 533                                 w->color = COLOR_RED;
 534                                 x = x->p;
 535                         } else {
 536                                 if (w->left->color == COLOR_BLACK) {
 537                                         w->right->color = COLOR_BLACK;
 538                                         w->color = COLOR_RED;
 539                                         left_rotate(rbtree, w);
 540                                         assert(!is_decay(rbtree->root));
 541                                         x = get_decay(x);
 542                                         w = x->p->left;
 543                                 }
 544                                 w->color = x->p->color;
 545                                 x->p->color = COLOR_BLACK;
 546                                 w->left->color = COLOR_BLACK;
 547                                 right_rotate(rbtree, x->p);
 548                                 x = rbtree->root;
 549                         }
 550                 }
 551         }
 552         x->color = COLOR_BLACK;
 553 }
 554
 555 /*
 556  * Delete z. All non-copied children left/right positions are unchanged.
 557  */
 558 static
 559 void rcu_rbtree_remove_nonil(struct rcu_rbtree *rbtree,
 560                              struct rcu_rbtree_node *z,
 561                              struct rcu_rbtree_node *y)
 562 {
 563         struct rcu_rbtree_node *x;
 564
 565         dbg_printf("remove nonil %p\n", z->key);
 566         show_tree(rbtree);
 567
 568         x = y->right;
 569         if (y->p == z)
 570                 x->p = y;
 571         else {
 572                 rcu_rbtree_transplant(rbtree, y, y->right);
 573                 assert(!is_decay(y));
 574                 assert(!is_decay(z));
 575                 y->right = z->right;
 576                 y->right->p = y;
 577         }
 578         rcu_rbtree_transplant(rbtree, z, y);
 579         assert(!is_decay(y));
 580         assert(!is_decay(z));
 581         y->left = z->left;
 582         y->left->p = y;
 583         y->color = z->color;
 584 }
 585
 586 int rcu_rbtree_remove(struct rcu_rbtree *rbtree,
 587                       struct rcu_rbtree_node *z)
 588 {
 589         struct rcu_rbtree_node *x, *y;
 590         unsigned int y_original_color;
 591
 592         assert(!is_decay(rbtree->root));
 593         dbg_printf("remove %p\n", z->key);
 594         show_tree(rbtree);
 595
 596         y = z;
 597         y_original_color = y->color;
 598
 599         if (rcu_rbtree_is_nil(z->left)) {
 600                 rcu_rbtree_transplant(rbtree, z, z->right);
 601                 assert(!is_decay(z));
 602                 x = z->right;
 603                 show_tree(rbtree);
 604         } else if (rcu_rbtree_is_nil(z->right)) {
 605                 rcu_rbtree_transplant(rbtree, z, z->left);
 606                 assert(!is_decay(z));
 607                 x = z->left;
 608                 show_tree(rbtree);
 609         } else {
 610                 y = rcu_rbtree_min(rbtree, z->right);
 611                 y_original_color = y->color;
 612                 rcu_rbtree_remove_nonil(rbtree, z, y);
 613                 assert(!is_decay(y));
 614                 x = y->right;
 615                 show_tree(rbtree);
 616         }
 617         if (y_original_color == COLOR_BLACK)
 618                 rcu_rbtree_remove_fixup(rbtree, x);
 619         show_tree(rbtree);
 620         /*
 621          * Commit all _CMM_STORE_SHARED().
 622          */
 623         cmm_smp_wmc();
 624
 625         return 0;
 626 }