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-call-rcu.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         call_rcu(&x->head, rbtree->rbfree);
  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(v))
 469                 v = dup_decay_node(rbtree, v);
 470
 471         if (rcu_rbtree_is_nil(u->p)) {
 472                 v->p = u->p;
 473                 cmm_smp_wmb();  /* write into node before publish */
 474                 _CMM_STORE_SHARED(rbtree->root, v);
 475         } else if (u == u->p->left) {
 476                 v->pos = IS_LEFT;
 477                 v->p = u->p;
 478                 cmm_smp_wmb();  /* write into node before publish */
 479                 _CMM_STORE_SHARED(u->p->left, v);
 480         } else {
 481                 v->pos = IS_RIGHT;
 482                 v->p = u->p;
 483                 cmm_smp_wmb();  /* write into node before publish */
 484                 _CMM_STORE_SHARED(u->p->right, v);
 485         }
 486         /* Set children parent to new node */
 487         if (!rcu_rbtree_is_nil(v)) {
 488                 v->right->p = v;
 489                 v->left->p = v;
 490         }
 491         assert(!is_decay(rbtree->root));
 492 }
 493
 494 static void rcu_rbtree_remove_fixup(struct rcu_rbtree *rbtree,
 495                                     struct rcu_rbtree_node *x)
 496 {
 497         dbg_printf("remove fixup %p\n", x->key);
 498
 499         while (x != rbtree->root && x->color == COLOR_BLACK) {
 500                 assert(!is_decay(x->p));
 501                 assert(!is_decay(x->p->left));
 502                 if (x == x->p->left) {
 503                         struct rcu_rbtree_node *w;
 504
 505                         w = x->p->right;
 506
 507                         if (w->color == COLOR_RED) {
 508                                 w->color = COLOR_BLACK;
 509                                 x->p->color = COLOR_RED;
 510                                 left_rotate(rbtree, x->p);
 511                                 x = get_decay(x);
 512                                 assert(!is_decay(rbtree->root));
 513                                 w = x->p->right;
 514                         }
 515                         if (w->left->color == COLOR_BLACK
 516                             && w->right->color == COLOR_BLACK) {
 517                                 w->color = COLOR_RED;
 518                                 x = x->p;
 519                                 assert(!is_decay(rbtree->root));
 520                                 assert(!is_decay(x));
 521                         } else {
 522                                 if (w->right->color == COLOR_BLACK) {
 523                                         w->left->color = COLOR_BLACK;
 524                                         w->color = COLOR_RED;
 525                                         right_rotate(rbtree, w);
 526                                         assert(!is_decay(rbtree->root));
 527                                         x = get_decay(x);
 528                                         w = x->p->right;
 529                                 }
 530                                 w->color = x->p->color;
 531                                 x->p->color = COLOR_BLACK;
 532                                 w->right->color = COLOR_BLACK;
 533                                 left_rotate(rbtree, x->p);
 534                                 assert(!is_decay(rbtree->root));
 535                                 x = rbtree->root;
 536                         }
 537                 } else {
 538                         struct rcu_rbtree_node *w;
 539
 540                         w = x->p->left;
 541
 542                         if (w->color == COLOR_RED) {
 543                                 w->color = COLOR_BLACK;
 544                                 x->p->color = COLOR_RED;
 545                                 right_rotate(rbtree, x->p);
 546                                 assert(!is_decay(rbtree->root));
 547                                 x = get_decay(x);
 548                                 w = x->p->left;
 549                         }
 550                         if (w->right->color == COLOR_BLACK
 551                             && w->left->color == COLOR_BLACK) {
 552                                 w->color = COLOR_RED;
 553                                 x = x->p;
 554                                 assert(!is_decay(rbtree->root));
 555                                 assert(!is_decay(x));
 556                         } else {
 557                                 if (w->left->color == COLOR_BLACK) {
 558                                         w->right->color = COLOR_BLACK;
 559                                         w->color = COLOR_RED;
 560                                         left_rotate(rbtree, w);
 561                                         assert(!is_decay(rbtree->root));
 562                                         x = get_decay(x);
 563                                         w = x->p->left;
 564                                 }
 565                                 w->color = x->p->color;
 566                                 x->p->color = COLOR_BLACK;
 567                                 w->left->color = COLOR_BLACK;
 568                                 right_rotate(rbtree, x->p);
 569                                 assert(!is_decay(rbtree->root));
 570                                 x = rbtree->root;
 571                         }
 572                 }
 573         }
 574         x->color = COLOR_BLACK;
 575 }
 576
 577 /*
 578  * Delete z. All non-copied children left/right positions are unchanged.
 579  */
 580 static
 581 void rcu_rbtree_remove_nonil(struct rcu_rbtree *rbtree,
 582                              struct rcu_rbtree_node *z,
 583                              struct rcu_rbtree_node *y)
 584 {
 585         struct rcu_rbtree_node *x;
 586
 587         dbg_printf("remove nonil %p\n", z->key);
 588         show_tree(rbtree);
 589
 590         assert(!is_decay(z));
 591         assert(!is_decay(y));
 592         assert(!is_decay(y->right));
 593         assert(!is_decay(y->p));
 594         x = y->right;
 595         assert(!is_decay(x));
 596         if (y->p == z)
 597                 x->p = y;
 598         else {
 599                 rcu_rbtree_transplant(rbtree, y, y->right);
 600                 assert(!is_decay(y));
 601                 assert(!is_decay(z));
 602                 assert(!is_decay(z->right));
 603                 y->right = z->right;
 604                 y->right->p = y;
 605         }
 606         rcu_rbtree_transplant(rbtree, z, y);
 607         y = get_decay(y);
 608         assert(!is_decay(z));
 609         assert(!is_decay(z->left));
 610         y->left = z->left;
 611         y->left->p = y;
 612         y->color = z->color;
 613 }
 614
 615 int rcu_rbtree_remove(struct rcu_rbtree *rbtree,
 616                       struct rcu_rbtree_node *z)
 617 {
 618         struct rcu_rbtree_node *x, *y;
 619         unsigned int y_original_color;
 620
 621         assert(!is_decay(rbtree->root));
 622         dbg_printf("remove %p\n", z->key);
 623         show_tree(rbtree);
 624
 625         assert(!is_decay(z));
 626         y = z;
 627         y_original_color = y->color;
 628
 629         if (rcu_rbtree_is_nil(z->left)) {
 630                 rcu_rbtree_transplant(rbtree, z, z->right);
 631                 assert(!is_decay(z));
 632                 x = get_decay(z->right);
 633                 show_tree(rbtree);
 634         } else if (rcu_rbtree_is_nil(z->right)) {
 635                 rcu_rbtree_transplant(rbtree, z, z->left);
 636                 assert(!is_decay(z));
 637                 x = get_decay(z->left);
 638                 show_tree(rbtree);
 639         } else {
 640                 y = rcu_rbtree_min(rbtree, z->right);
 641                 assert(!is_decay(y));
 642                 y_original_color = y->color;
 643                 rcu_rbtree_remove_nonil(rbtree, z, y);
 644                 x = get_decay(y->right);
 645                 show_tree(rbtree);
 646         }
 647         if (y_original_color == COLOR_BLACK)
 648                 rcu_rbtree_remove_fixup(rbtree, x);
 649         show_tree(rbtree);
 650         /*
 651          * Commit all _CMM_STORE_SHARED().
 652          */
 653         cmm_smp_wmc();
 654
 655         return 0;
 656 }