src/mcas/skip_cas_adt.c

   1 /******************************************************************************
   2  * skip_cas_adt.c
   3  *
   4  * Skip lists, allowing concurrent update by use of CAS primitives.
   5  *
   6  * Matt Benjamin <matt@linuxbox.com>
   7  *
   8  * Adapts MCAS skip list to use a pointer-key and typed comparison
   9  * function style (because often, your key isn't an integer).
  10  *
  11  * Also, set_for_each (and future additions) allow a set to be iterated.
  12  * Current set_for_each iteration is unordered.
  13  *
  14  * Caution, pointer values 0x0, 0x01, and 0x02 are reserved.  Fortunately,
  15  * no real pointer is likely to have one of these values.
  16
  17 Copyright (c) 2003, Keir Fraser All rights reserved.
  18
  19 Redistribution and use in source and binary forms, with or without
  20 modification, are permitted provided that the following conditions are
  21 met:
  22
  23     * Redistributions of source code must retain the above copyright
  24     * notice, this list of conditions and the following disclaimer.
  25     * Redistributions in binary form must reproduce the above
  26     * copyright notice, this list of conditions and the following
  27     * disclaimer in the documentation and/or other materials provided
  28     * with the distribution.  Neither the name of the Keir Fraser
  29     * nor the names of its contributors may be used to endorse or
  30     * promote products derived from this software without specific
  31     * prior written permission.
  32
  33 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  34 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  35 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
  36 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
  37 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  38 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
  39 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  40 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  41 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  42 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  43 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  44 */
  45
  46 #define __SET_IMPLEMENTATION__
  47
  48 #include <stdlib.h>
  49 #include <string.h>
  50 #include <assert.h>
  51 #include "portable_defns.h"
  52 #include "ptst.h"
  53 #include "set_queue_adt.h"
  54
  55 // todo:  get rid of me
  56 typedef struct {
  57     unsigned long key;
  58     unsigned long secret_key;
  59 } harness_ulong_t;
  60
  61
  62
  63 /*
  64  * SKIP LIST
  65  */
  66
  67 typedef struct node_st node_t;
  68 typedef struct set_st osi_set_t;
  69 typedef VOLATILE node_t *sh_node_pt;
  70
  71 struct node_st {
  72     int level;
  73 //      int                xxx[1024]; /* XXXX testing gc */
  74 #define LEVEL_MASK     0x0ff
  75 #define READY_FOR_FREE 0x100
  76     setkey_t k;
  77     setval_t v;
  78     sh_node_pt next[1];
  79 };
  80
  81 typedef int (*osi_set_cmp_func) (const void *lhs, const void *rhs);
  82
  83 struct set_st {
  84     CACHE_PAD(0);
  85     osi_set_cmp_func cmpf;
  86       CACHE_PAD(1);
  87     node_t head;
  88       CACHE_PAD(2);
  89 };
  90
  91 static int gc_id[NUM_LEVELS];
  92
  93 /*
  94  * PRIVATE FUNCTIONS
  95  */
  96
  97 #define compare_keys(s, k1, k2) (s->cmpf((const void*) k1, (const void *) k2))
  98
  99 /*
 100  * Random level generator. Drop-off rate is 0.5 per level.
 101  * Returns value 1 <= level <= NUM_LEVELS.
 102  */
 103 static int
 104 get_level(ptst_t * ptst)
 105 {
 106     unsigned long r = rand_next(ptst);
 107     int l = 1;
 108     r = (r >> 4) & ((1 << (NUM_LEVELS - 1)) - 1);
 109     while ((r & 1)) {
 110         l++;
 111         r >>= 1;
 112     }
 113     return (l);
 114 }
 115
 116
 117 /*
 118  * Allocate a new node, and initialise its @level field.
 119  * NB. Initialisation will eventually be pushed into garbage collector,
 120  * because of dependent read reordering.
 121  */
 122 static node_t *
 123 alloc_node(ptst_t * ptst)
 124 {
 125     int l;
 126     node_t *n;
 127     l = get_level(ptst);
 128     n = gc_alloc(ptst, gc_id[l - 1]);
 129     n->level = l;
 130     return (n);
 131 }
 132
 133
 134 /* Free a node to the garbage collector. */
 135 static void
 136 free_node(ptst_t * ptst, sh_node_pt n)
 137 {
 138     gc_free(ptst, (void *)n, gc_id[(n->level & LEVEL_MASK) - 1]);
 139 }
 140
 141
 142 /*
 143  * Search for first non-deleted node, N, with key >= @k at each level in @l.
 144  * RETURN VALUES:
 145  *  Array @pa: @pa[i] is non-deleted predecessor of N at level i
 146  *  Array @na: @na[i] is N itself, which should be pointed at by @pa[i]
 147  *  MAIN RETURN VALUE: same as @na[0].
 148  */
 149 static sh_node_pt
 150 strong_search_predecessors(osi_set_t * l, setkey_t k, sh_node_pt * pa,
 151                            sh_node_pt * na)
 152 {
 153     sh_node_pt x, x_next, old_x_next, y, y_next;
 154     setkey_t y_k;
 155     int i;
 156
 157   retry:
 158     RMB();
 159
 160     x = &l->head;
 161     for (i = NUM_LEVELS - 1; i >= 0; i--) {
 162         /* We start our search at previous level's unmarked predecessor. */
 163         READ_FIELD(x_next, x->next[i]);
 164         /* If this pointer's marked, so is @pa[i+1]. May as well retry. */
 165         if (is_marked_ref(x_next))
 166             goto retry;
 167
 168         for (y = x_next;; y = y_next) {
 169             /* Shift over a sequence of marked nodes. */
 170             for (;;) {
 171                 READ_FIELD(y_next, y->next[i]);
 172                 if (!is_marked_ref(y_next))
 173                     break;
 174                 y = get_unmarked_ref(y_next);
 175             }
 176
 177             READ_FIELD(y_k, y->k);
 178             if (compare_keys(l, y_k, k) >= 0)
 179                 break;
 180
 181             /* Update estimate of predecessor at this level. */
 182             x = y;
 183             x_next = y_next;
 184         }
 185
 186         /* Swing forward pointer over any marked nodes. */
 187         if (x_next != y) {
 188             old_x_next = CASPO(&x->next[i], x_next, y);
 189             if (old_x_next != x_next)
 190                 goto retry;
 191         }
 192
 193         if (pa)
 194             pa[i] = x;
 195         if (na)
 196             na[i] = y;
 197     }
 198
 199     return (y);
 200 }
 201
 202
 203 /* This function does not remove marked nodes. Use it optimistically. */
 204 static sh_node_pt
 205 weak_search_predecessors(osi_set_t * l, setkey_t k, sh_node_pt * pa,
 206                          sh_node_pt * na)
 207 {
 208     sh_node_pt x, x_next;
 209     setkey_t x_next_k;
 210     int i;
 211
 212     x = &l->head;
 213     for (i = NUM_LEVELS - 1; i >= 0; i--) {
 214         for (;;) {
 215             READ_FIELD(x_next, x->next[i]);
 216             x_next = get_unmarked_ref(x_next);
 217
 218             READ_FIELD(x_next_k, x_next->k);
 219             if (compare_keys(l, x_next_k, k) >= 0)
 220                 break;
 221
 222             x = x_next;
 223         }
 224
 225         if (pa)
 226             pa[i] = x;
 227         if (na)
 228             na[i] = x_next;
 229     }
 230
 231     return (x_next);
 232 }
 233
 234
 235 /*
 236  * Mark @x deleted at every level in its list from @level down to level 1.
 237  * When all forward pointers are marked, node is effectively deleted.
 238  * Future searches will properly remove node by swinging predecessors'
 239  * forward pointers.
 240  */
 241 static void
 242 mark_deleted(sh_node_pt x, int level)
 243 {
 244     sh_node_pt x_next;
 245
 246     while (--level >= 0) {
 247         x_next = x->next[level];
 248         while (!is_marked_ref(x_next)) {
 249             x_next = CASPO(&x->next[level], x_next, get_marked_ref(x_next));
 250         }
 251         WEAK_DEP_ORDER_WMB();   /* mark in order */
 252     }
 253 }
 254
 255
 256 static int
 257 check_for_full_delete(sh_node_pt x)
 258 {
 259     int level = x->level;
 260     return ((level & READY_FOR_FREE) ||
 261             (CASIO(&x->level, level, level | READY_FOR_FREE) != level));
 262 }
 263
 264
 265 static void
 266 do_full_delete(ptst_t * ptst, osi_set_t * l, sh_node_pt x, int level)
 267 {
 268     setkey_t k = x->k;
 269 #ifdef WEAK_MEM_ORDER
 270     sh_node_pt preds[NUM_LEVELS];
 271     int i = level;
 272   retry:
 273     (void)strong_search_predecessors(l, k, preds, NULL);
 274     /*
 275      * Above level 1, references to @x can disappear if a node is inserted
 276      * immediately before and we see an old value for its forward pointer. This
 277      * is a conservative way of checking for that situation.
 278      */
 279     if (i > 0)
 280         RMB();
 281     while (i > 0) {
 282         node_t *n = get_unmarked_ref(preds[i]->next[i]);
 283         while (compare_keys(l, n->k, k) < 0) {
 284             n = get_unmarked_ref(n->next[i]);
 285             RMB();              /* we don't want refs to @x to "disappear" */
 286         }
 287         if (n == x)
 288             goto retry;
 289         i--;                    /* don't need to check this level again, even if we retry. */
 290     }
 291 #else
 292     (void)strong_search_predecessors(l, k, NULL, NULL);
 293 #endif
 294     free_node(ptst, x);
 295 }
 296
 297
 298 /*
 299  * PUBLIC FUNCTIONS
 300  */
 301
 302 /*
 303  * Called once before any set operations, including set_alloc
 304  */
 305 void
 306 _init_osi_cas_skip_subsystem(void)
 307 {
 308     int i;
 309
 310     for (i = 0; i < NUM_LEVELS; i++) {
 311         gc_id[i] = gc_add_allocator(sizeof(node_t) + i * sizeof(node_t *));
 312     }
 313 }
 314
 315
 316 osi_set_t *
 317 osi_cas_skip_alloc(osi_set_cmp_func cmpf)
 318 {
 319     osi_set_t *l;
 320     node_t *n;
 321     int i;
 322
 323     n = malloc(sizeof(*n) + (NUM_LEVELS - 1) * sizeof(node_t *));
 324     memset(n, 0, sizeof(*n) + (NUM_LEVELS - 1) * sizeof(node_t *));
 325     n->k = (setkey_t *) SENTINEL_KEYMAX;
 326
 327     /*
 328      * Set the forward pointers of final node to other than NULL,
 329      * otherwise READ_FIELD() will continually execute costly barriers.
 330      * Note use of 0xfe -- that doesn't look like a marked value!
 331      */
 332     memset(n->next, 0xfe, NUM_LEVELS * sizeof(node_t *));
 333
 334     l = malloc(sizeof(*l) + (NUM_LEVELS - 1) * sizeof(node_t *));
 335     l->cmpf = cmpf;
 336     l->head.k = (setkey_t *) SENTINEL_KEYMIN;
 337     l->head.level = NUM_LEVELS;
 338     for (i = 0; i < NUM_LEVELS; i++) {
 339         l->head.next[i] = n;
 340     }
 341
 342     return (l);
 343 }
 344
 345
 346 setval_t
 347 osi_cas_skip_update(osi_set_t * l, setkey_t k, setval_t v, int overwrite)
 348 {
 349     setval_t ov, new_ov;
 350     ptst_t *ptst;
 351     sh_node_pt preds[NUM_LEVELS], succs[NUM_LEVELS];
 352     sh_node_pt pred, succ, new = NULL, new_next, old_next;
 353     int i, level;
 354
 355     ptst = critical_enter();
 356
 357     succ = weak_search_predecessors(l, k, preds, succs);
 358
 359   retry:
 360     ov = NULL;
 361
 362     if (compare_keys(l, succ->k, k) == 0) {
 363         /* Already a @k node in the list: update its mapping. */
 364         new_ov = succ->v;
 365         do {
 366             if ((ov = new_ov) == NULL) {
 367                 /* Finish deleting the node, then retry. */
 368                 READ_FIELD(level, succ->level);
 369                 mark_deleted(succ, level & LEVEL_MASK);
 370                 succ = strong_search_predecessors(l, k, preds, succs);
 371                 goto retry;
 372             }
 373         } while (overwrite && ((new_ov = CASPO(&succ->v, ov, v)) != ov));
 374
 375         if (new != NULL)
 376             free_node(ptst, new);
 377         goto out;
 378     }
 379 #ifdef WEAK_MEM_ORDER
 380     /* Free node from previous attempt, if this is a retry. */
 381     if (new != NULL) {
 382         free_node(ptst, new);
 383         new = NULL;
 384     }
 385 #endif
 386
 387     /* Not in the list, so initialise a new node for insertion. */
 388     if (new == NULL) {
 389         new = alloc_node(ptst);
 390         new->k = k;
 391         new->v = v;
 392     }
 393     level = new->level;
 394
 395     /* If successors don't change, this saves us some CAS operations. */
 396     for (i = 0; i < level; i++) {
 397         new->next[i] = succs[i];
 398     }
 399
 400     /* We've committed when we've inserted at level 1. */
 401     WMB_NEAR_CAS();             /* make sure node fully initialised before inserting */
 402     old_next = CASPO(&preds[0]->next[0], succ, new);
 403     if (old_next != succ) {
 404         succ = strong_search_predecessors(l, k, preds, succs);
 405         goto retry;
 406     }
 407
 408     /* Insert at each of the other levels in turn. */
 409     i = 1;
 410     while (i < level) {
 411         pred = preds[i];
 412         succ = succs[i];
 413
 414         /* Someone *can* delete @new under our feet! */
 415         new_next = new->next[i];
 416         if (is_marked_ref(new_next))
 417             goto success;
 418
 419         /* Ensure forward pointer of new node is up to date. */
 420         if (new_next != succ) {
 421             old_next = CASPO(&new->next[i], new_next, succ);
 422             if (is_marked_ref(old_next))
 423                 goto success;
 424             assert(old_next == new_next);
 425         }
 426
 427         /* Ensure we have unique key values at every level. */
 428         if (compare_keys(l, succ->k, k) == 0)
 429             goto new_world_view;
 430
 431         assert((compare_keys(l, pred->k, k) < 0) &&
 432                (compare_keys(l, succ->k, k) > 0));
 433
 434         /* Replumb predecessor's forward pointer. */
 435         old_next = CASPO(&pred->next[i], succ, new);
 436         if (old_next != succ) {
 437           new_world_view:
 438             RMB();              /* get up-to-date view of the world. */
 439             (void)strong_search_predecessors(l, k, preds, succs);
 440             continue;
 441         }
 442
 443         /* Succeeded at this level. */
 444         i++;
 445     }
 446
 447   success:
 448     /* Ensure node is visible at all levels before punting deletion. */
 449     WEAK_DEP_ORDER_WMB();
 450     if (check_for_full_delete(new)) {
 451         MB();                   /* make sure we see all marks in @new. */
 452         do_full_delete(ptst, l, new, level - 1);
 453     }
 454   out:
 455     critical_exit(ptst);
 456     return (ov);
 457 }
 458
 459 setval_t
 460 osi_cas_skip_remove(osi_set_t * l, setkey_t k)
 461 {
 462     setval_t v = NULL, new_v;
 463     ptst_t *ptst;
 464     sh_node_pt preds[NUM_LEVELS], x;
 465     int level, i;
 466
 467     ptst = critical_enter();
 468
 469     x = weak_search_predecessors(l, k, preds, NULL);
 470     if (compare_keys(l, x->k, k) > 0)
 471         goto out;
 472
 473     READ_FIELD(level, x->level);
 474     level = level & LEVEL_MASK;
 475
 476     /* Once we've marked the value field, the node is effectively deleted. */
 477     new_v = x->v;
 478     do {
 479         v = new_v;
 480         if (v == NULL)
 481             goto out;
 482     } while ((new_v = CASPO(&x->v, v, NULL)) != v);
 483
 484     /* Committed to @x: mark lower-level forward pointers. */
 485     WEAK_DEP_ORDER_WMB();       /* enforce above as linearisation point */
 486     mark_deleted(x, level);
 487
 488     /*
 489      * We must swing predecessors' pointers, or we can end up with
 490      * an unbounded number of marked but not fully deleted nodes.
 491      * Doing this creates a bound equal to number of threads in the system.
 492      * Furthermore, we can't legitimately call 'free_node' until all shared
 493      * references are gone.
 494      */
 495     for (i = level - 1; i >= 0; i--) {
 496         if (CASPO(&preds[i]->next[i], x, get_unmarked_ref(x->next[i])) != x) {
 497             if ((i != (level - 1)) || check_for_full_delete(x)) {
 498                 MB();           /* make sure we see node at all levels. */
 499                 do_full_delete(ptst, l, x, i);
 500             }
 501             goto out;
 502         }
 503     }
 504
 505     free_node(ptst, x);
 506
 507   out:
 508     critical_exit(ptst);
 509     return (v);
 510 }
 511
 512
 513 setval_t
 514 osi_cas_skip_lookup(osi_set_t * l, setkey_t k)
 515 {
 516     setval_t v = NULL;
 517     ptst_t *ptst;
 518     sh_node_pt x;
 519
 520     ptst = critical_enter();
 521
 522     x = weak_search_predecessors(l, k, NULL, NULL);
 523     if (compare_keys(l, x->k, k) == 0)
 524         READ_FIELD(v, x->v);
 525
 526     critical_exit(ptst);
 527     return (v);
 528 }
 529
 530
 531 /* Hybrid Set/Queue Operations (Matt) */
 532
 533 /* Iterate over a sequential structure, calling callback_func
 534  * on each (undeleted) element visited. */
 535
 536 /* Each-element function passed to set_for_each */
 537 typedef void (*osi_set_each_func) (osi_set_t * l, setval_t v, void *arg);
 538 void
 539 osi_cas_skip_for_each(osi_set_t * l, osi_set_each_func each_func, void *arg)
 540 {
 541     sh_node_pt x, y, x_next, old_x_next;
 542     setkey_t x_next_k;
 543     ptst_t *ptst;
 544     int i;
 545
 546     ptst = critical_enter();
 547
 548     x = &l->head;
 549     for (i = NUM_LEVELS - 1; i >= 0; i--) {
 550         /* must revisit x at each level to see all
 551          * nodes in the structure */
 552         y = x;
 553
 554         for (;;) {
 555             READ_FIELD(x_next, y->next[i]);
 556             x_next = get_unmarked_ref(x_next);
 557
 558             READ_FIELD(x_next_k, x_next->k);
 559             if (x_next_k == (setkey_t) SENTINEL_KEYMAX)
 560                 break;
 561
 562             /* in our variation, a (stored) k is a v,
 563              * ie, x_next_k is x_next_v */
 564             each_func(l, x_next_k, arg);
 565
 566             y = x_next;
 567         }
 568     }
 569
 570     critical_exit(ptst);
 571 }