src/mcas/skip_mcas.c

   1 /******************************************************************************
   2  * skip_mcas.c
   3  *
   4  * Skip lists, allowing concurrent update by use of MCAS primitive.
   5  *
   6  * Copyright (c) 2001-2003, K A Fraser
   7
   8 Redistribution and use in source and binary forms, with or without
   9 modification, are permitted provided that the following conditions are
  10 met:
  11
  12     * Redistributions of source code must retain the above copyright
  13     * notice, this list of conditions and the following disclaimer.
  14     * Redistributions in binary form must reproduce the above
  15     * copyright notice, this list of conditions and the following
  16     * disclaimer in the documentation and/or other materials provided
  17     * with the distribution.  Neither the name of the Keir Fraser
  18     * nor the names of its contributors may be used to endorse or
  19     * promote products derived from this software without specific
  20     * prior written permission.
  21
  22 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  23 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  24 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
  25 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
  26 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  27 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
  28 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  29 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  30 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  31 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  32 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  33  */
  34
  35 #define __SET_IMPLEMENTATION__
  36
  37 #include <unistd.h>
  38 #include <stdlib.h>
  39 #include <string.h>
  40 #include <assert.h>
  41 #include "portable_defns.h"
  42 #include "ptst.h"
  43 #include "set.h"
  44
  45 #define MCAS_MARK(_v) ((unsigned long)(_v) & 3)
  46
  47 #define PROCESS(_v, _pv)                        \
  48   while ( MCAS_MARK(_v) ) {                     \
  49     mcas_fixup((void **)(_pv), _v);             \
  50     (_v) = *(_pv);                              \
  51   }
  52
  53 #define WALK_THRU(_v, _pv)                      \
  54   if ( MCAS_MARK(_v) ) (_v) = read_barrier_lite((void **)(_pv));
  55
  56 /* Pull in the MCAS implementation. */
  57 #include "mcas.c"
  58
  59 /*
  60  * SKIP LIST
  61  */
  62
  63 typedef struct node_st node_t;
  64 typedef struct set_st set_t;
  65 typedef VOLATILE node_t *sh_node_pt;
  66
  67 struct node_st
  68 {
  69     int        level;
  70     setkey_t  k;
  71     setval_t  v;
  72     sh_node_pt next[1];
  73 };
  74
  75 struct set_st
  76 {
  77     node_t head;
  78 };
  79
  80 static int gc_id[NUM_LEVELS];
  81
  82 /*
  83  * PRIVATE FUNCTIONS
  84  */
  85
  86 /*
  87  * Random level generator. Drop-off rate is 0.5 per level.
  88  * Returns value 1 <= level <= NUM_LEVELS.
  89  */
  90 static int get_level(ptst_t *ptst)
  91 {
  92     unsigned long r = rand_next(ptst);
  93     int l = 1;
  94     r = (r >> 4) & ((1 << (NUM_LEVELS-1)) - 1);
  95     while ( (r & 1) ) { l++; r >>= 1; }
  96     return(l);
  97 }
  98
  99
 100 /*
 101  * Allocate a new node, and initialise its @level field.
 102  * NB. Initialisation will eventually be pushed into garbage collector,
 103  * because of dependent read reordering.
 104  */
 105 static node_t *alloc_node(ptst_t *ptst)
 106 {
 107     int l;
 108     node_t *n;
 109     l = get_level(ptst);
 110     n = gc_alloc(ptst, gc_id[l - 1]);
 111     n->level = l;
 112     return(n);
 113 }
 114
 115
 116 /* Free a node to the garbage collector. */
 117 static void free_node(ptst_t *ptst, sh_node_pt n)
 118 {
 119     gc_free(ptst, (void *)n, gc_id[n->level - 1]);
 120 }
 121
 122
 123 /*
 124  * Search for first non-deleted node, N, with key >= @k at each level in @l.
 125  * RETURN VALUES:
 126  *  Array @pa: @pa[i] is non-deleted predecessor of N at level i
 127  *  Array @na: @na[i] is N itself, which should be pointed at by @pa[i]
 128  *  MAIN RETURN VALUE: same as @na[0].
 129  */
 130 static sh_node_pt search_predecessors(
 131     set_t *l, setkey_t k, sh_node_pt *pa, sh_node_pt *na)
 132 {
 133     sh_node_pt x, x_next;
 134     setkey_t  x_next_k;
 135     int        i;
 136
 137     RMB();
 138
 139     x = &l->head;
 140     for ( i = NUM_LEVELS - 1; i >= 0; i-- )
 141     {
 142         for ( ; ; )
 143         {
 144             READ_FIELD(x_next, x->next[i]);
 145             WALK_THRU(x_next, &x->next[i]);
 146
 147             READ_FIELD(x_next_k, x_next->k);
 148             if ( x_next_k >= k ) break;
 149
 150             x = x_next;
 151         }
 152
 153         if ( pa ) pa[i] = x;
 154         if ( na ) na[i] = x_next;
 155     }
 156
 157     return(x_next);
 158 }
 159
 160 static setval_t finish_delete(sh_node_pt x, sh_node_pt *preds)
 161 {
 162     per_thread_state_t *mcas_ptst = get_ptst();
 163     CasDescriptor_t *cd;
 164     int level, i, ret = FALSE;
 165     sh_node_pt x_next;
 166     setkey_t x_next_k;
 167     setval_t v;
 168
 169     READ_FIELD(level, x->level);
 170
 171     cd = new_descriptor(mcas_ptst, (level << 1) + 1);
 172     cd->status = STATUS_IN_PROGRESS;
 173     cd->length = (level << 1) + 1;
 174
 175     /* First, the deleted node's value field. */
 176     READ_FIELD(v, x->v);
 177     PROCESS(v, &x->v);
 178     if ( v == NULL ) goto fail;
 179     cd->entries[0].ptr = (void **)&x->v;
 180     cd->entries[0].old = v;
 181     cd->entries[0].new = NULL;
 182
 183     for ( i = 0; i < level; i++ )
 184     {
 185         READ_FIELD(x_next, x->next[i]);
 186         PROCESS(x_next, &x->next[i]);
 187         READ_FIELD(x_next_k, x_next->k);
 188         if ( x->k > x_next_k ) { v = NULL; goto fail; }
 189         cd->entries[i      +1].ptr = (void **)&x->next[i];
 190         cd->entries[i      +1].old = x_next;
 191         cd->entries[i      +1].new = preds[i];
 192         cd->entries[i+level+1].ptr = (void **)&preds[i]->next[i];
 193         cd->entries[i+level+1].old = x;
 194         cd->entries[i+level+1].new = x_next;
 195     }
 196
 197     ret = mcas0(mcas_ptst, cd);
 198     if ( ret == 0 ) v = NULL;
 199
 200  fail:
 201     rc_down_descriptor(cd);
 202     return v;
 203 }
 204
 205
 206 /*
 207  * PUBLIC FUNCTIONS
 208  */
 209
 210 set_t *set_alloc(void)
 211 {
 212     set_t *l;
 213     node_t *n;
 214     int i;
 215
 216     static int mcas_inited = 0;
 217     if ( !CASIO(&mcas_inited, 0, 1) ) mcas_init();
 218
 219     n = malloc(sizeof(*n) + (NUM_LEVELS-1)*sizeof(node_t *));
 220     memset(n, 0, sizeof(*n) + (NUM_LEVELS-1)*sizeof(node_t *));
 221     n->k = SENTINEL_KEYMAX;
 222
 223     /*
 224      * Set the forward pointers of final node to other than NULL,
 225      * otherwise READ_FIELD() will continually execute costly barriers.
 226      * Note use of 0xfc -- that doesn't look like a marked value!
 227      */
 228     memset(n->next, 0xfc, NUM_LEVELS*sizeof(node_t *));
 229
 230     l = malloc(sizeof(*l) + (NUM_LEVELS-1)*sizeof(node_t *));
 231     l->head.k = SENTINEL_KEYMIN;
 232     l->head.level = NUM_LEVELS;
 233     for ( i = 0; i < NUM_LEVELS; i++ )
 234     {
 235         l->head.next[i] = n;
 236     }
 237
 238     return(l);
 239 }
 240
 241
 242 setval_t set_update(set_t *l, setkey_t k, setval_t v, int overwrite)
 243 {
 244     setval_t  ov, new_ov;
 245     ptst_t    *ptst;
 246     sh_node_pt preds[NUM_LEVELS], succs[NUM_LEVELS];
 247     sh_node_pt succ, new = NULL;
 248     int        i, ret;
 249     per_thread_state_t *mcas_ptst = NULL;
 250     CasDescriptor_t *cd;
 251
 252     k = CALLER_TO_INTERNAL_KEY(k);
 253
 254     ptst = critical_enter();
 255
 256     do {
 257     retry:
 258         ov = NULL;
 259
 260         succ = search_predecessors(l, k, preds, succs);
 261
 262         if ( succ->k == k )
 263         {
 264             /* Already a @k node in the list: update its mapping. */
 265             READ_FIELD(new_ov, succ->v);
 266             do {
 267                 ov = new_ov;
 268                 PROCESS(ov, &succ->v);
 269                 if ( ov == NULL ) goto retry;
 270             }
 271             while ( overwrite && ((new_ov = CASPO(&succ->v, ov, v)) != ov) );
 272
 273             if ( new != NULL ) free_node(ptst, new);
 274             goto out;
 275         }
 276
 277 #ifdef WEAK_MEM_ORDER
 278         /* Free node from previous attempt, if this is a retry. */
 279         if ( new != NULL )
 280         {
 281             free_node(ptst, new);
 282             new = NULL;
 283         }
 284 #endif
 285
 286         /* Not in the list, so initialise a new node for insertion. */
 287         if ( new == NULL )
 288         {
 289             new    = alloc_node(ptst);
 290             new->k = k;
 291             new->v = v;
 292         }
 293
 294         for ( i = 0; i < new->level; i++ )
 295         {
 296             new->next[i] = succs[i];
 297         }
 298
 299         if ( !mcas_ptst ) mcas_ptst = get_ptst();
 300         cd = new_descriptor(mcas_ptst, new->level);
 301         cd->status = STATUS_IN_PROGRESS;
 302         cd->length = new->level;
 303         for ( i = 0; i < new->level; i++ )
 304         {
 305             cd->entries[i].ptr = (void **)&preds[i]->next[i];
 306             cd->entries[i].old = succs[i];
 307             cd->entries[i].new = new;
 308         }
 309         ret = mcas0(mcas_ptst, cd);
 310         rc_down_descriptor(cd);
 311     }
 312     while ( !ret );
 313
 314  out:
 315     critical_exit(ptst);
 316     return(ov);
 317 }
 318
 319
 320 setval_t set_remove(set_t *l, setkey_t k)
 321 {
 322     setval_t  v = NULL;
 323     ptst_t    *ptst;
 324     sh_node_pt preds[NUM_LEVELS], x;
 325
 326     k = CALLER_TO_INTERNAL_KEY(k);
 327
 328     ptst = critical_enter();
 329
 330     do {
 331         x = search_predecessors(l, k, preds, NULL);
 332         if ( x->k > k ) goto out;
 333     } while ( (v = finish_delete(x, preds)) == NULL );
 334
 335     free_node(ptst, x);
 336
 337  out:
 338     critical_exit(ptst);
 339     return(v);
 340 }
 341
 342
 343 setval_t set_lookup(set_t *l, setkey_t k)
 344 {
 345     setval_t  v = NULL;
 346     ptst_t    *ptst;
 347     sh_node_pt x;
 348
 349     k = CALLER_TO_INTERNAL_KEY(k);
 350
 351     ptst = critical_enter();
 352
 353     x = search_predecessors(l, k, NULL, NULL);
 354     if ( x->k == k )
 355     {
 356         READ_FIELD(v, x->v);
 357         WALK_THRU(v, &x->v);
 358     }
 359
 360     critical_exit(ptst);
 361     return(v);
 362 }
 363
 364
 365 void _init_set_subsystem(void)
 366 {
 367     int i;
 368
 369     for ( i = 0; i < NUM_LEVELS; i++ )
 370     {
 371         gc_id[i] = gc_add_allocator(sizeof(node_t) + i*sizeof(node_t *));
 372     }
 373
 374 }