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