src/mcas/skip_lock.c

   1 /******************************************************************************
   2  * skip_lock.c (Variable-granularity Mutexes)
   3  *
   4  * Mutex only taken for write operations (reads are unprotected). Write
   5  * mutexes come in three flavours, selected by a compile-time flag.
   6  *
   7  * If FAT_MTX is defined:
   8  *  A skip list is protected by one mutex for the entire list. Note that this
   9  *  differs from skip_bm.c, which  takes the mutex for read operations as well.
  10  *
  11  * If TINY_MTX is defined:
  12  *  Mutex per forward pointer in each node.
  13  *
  14  * If neither flag is defined:
  15  *  Mutex per node.
  16  *
  17  * Copyright (c) 2001-2003, K A Fraser
  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.h"
  54
  55
  56 /*
  57  * SKIP LIST
  58  */
  59
  60 typedef struct node_st node_t;
  61 typedef struct set_st set_t;
  62 typedef VOLATILE node_t *sh_node_pt;
  63
  64 typedef struct ptr_st ptr_t;
  65 struct ptr_st
  66 {
  67 #ifdef TINY_MTX /* mutex per forward pointer */
  68     mcs_lock_t m;
  69 #endif
  70     sh_node_pt      p;
  71 };
  72
  73 struct node_st
  74 {
  75     int             level;
  76     setkey_t       k;
  77     setval_t       v;
  78 #ifndef FAT_MTX
  79     mcs_lock_t m;
  80 #endif
  81     ptr_t           next[1];
  82 };
  83
  84 struct set_st
  85 {
  86 #ifdef FAT_MTX
  87     mcs_lock_t m;
  88 #endif
  89     node_t          head;
  90 };
  91
  92 static int gc_id[NUM_LEVELS];
  93
  94 /*
  95  * LOCKING
  96  */
  97
  98 #ifdef FAT_MTX
  99
 100 #define LIST_LOCK(_l,_qn)            ((void)mcs_lock((void*)&(_l)->m, (_qn)))
 101 #define LIST_UNLOCK(_l,_qn)          ((void)mcs_unlock((void*)&(_l)->m, (_qn)))
 102 #define NODE_LOCK(_x,_qn)            ((void)0)
 103 #define NODE_UNLOCK(_x,_qn)          ((void)0)
 104 #define PTR_UPDATE_LOCK(_x,_i,_qn)   ((void)0)
 105 #define PTR_UPDATE_UNLOCK(_x,_i,_qn) ((void)0)
 106 #define PTR_DELETE_LOCK(_x,_i,_qn)   ((void)0)
 107 #define PTR_DELETE_UNLOCK(_x,_i,_qn) ((void)0)
 108
 109 #else
 110
 111 #define LIST_LOCK(_l,_qn)         ((void)0)
 112 #define LIST_UNLOCK(_l,_qn)       ((void)0)
 113
 114 /* We take the main node lock to get exclusive rights on insert/delete ops. */
 115 #define NODE_LOCK(_x,_qn)         ((void)mcs_lock((void*)&(_x)->m, (_qn)))
 116 #define NODE_UNLOCK(_x,_qn)       ((void)mcs_unlock((void*)&(_x)->m, (_qn)))
 117
 118 #ifdef TINY_MTX
 119
 120 /*
 121  * Predecessor's pointer is locked before swinging (on delete), or
 122  * replumbing (on insert).
 123  */
 124 #define PTR_UPDATE_LOCK(_x, _i, _qn)   \
 125     ((void)mcs_lock((void*)&(_x)->next[(_i)].m, (_qn)))
 126 #define PTR_UPDATE_UNLOCK(_x, _i, _qn) \
 127     ((void)mcs_unlock((void*)&(_x)->next[(_i)].m, (_qn)))
 128 /*
 129  * When deleting a node, we take the lock on each of its pointers in turn,
 130  * to prevent someone from inserting a new node directly after, or deleting
 131  * immediate successor.
 132  */
 133 #define PTR_DELETE_LOCK(_x, _i, _qn)   PTR_UPDATE_LOCK(_x,_i,(_qn))
 134 #define PTR_DELETE_UNLOCK(_x, _i, _qn) PTR_UPDATE_UNLOCK(_x,_i,(_qn))
 135
 136 #else /* LITTLE_MTX */
 137
 138 /*
 139  * Predecessor must certainly be locked for insert/delete ops. So we take
 140  * the only lock we can.
 141  */
 142 #define PTR_UPDATE_LOCK(_x, _i, _qn)   NODE_LOCK(_x,(_qn))
 143 #define PTR_UPDATE_UNLOCK(_x, _i, _qn) NODE_UNLOCK(_x,(_qn))
 144 /*
 145  * We can't lock individual pointers. There's no need anyway, since we have
 146  * the node's lock already (to allow us exclusive delete rights).
 147  */
 148 #define PTR_DELETE_LOCK(_x, _i, _qn)   ((void)0)
 149 #define PTR_DELETE_UNLOCK(_x, _i, _qn) ((void)0)
 150
 151 #endif
 152
 153 #endif
 154
 155
 156 /*
 157  * PRIVATE FUNCTIONS
 158  */
 159
 160 /*
 161  * Random level generator. Drop-off rate is 0.5 per level.
 162  * Returns value 1 <= level <= NUM_LEVELS.
 163  */
 164 static int get_level(ptst_t *ptst)
 165 {
 166     unsigned long r = rand_next(ptst);
 167     int l = 1;
 168     r = (r >> 4) & ((1 << (NUM_LEVELS-1)) - 1);
 169     while ( (r & 1) ) { l++; r >>= 1; }
 170     return(l);
 171 }
 172
 173
 174 /*
 175  * Allocate a new node, and initialise its @level field.
 176  * NB. Initialisation will eventually be pushed into garbage collector,
 177  * because of dependent read reordering.
 178  */
 179 static node_t *alloc_node(ptst_t *ptst)
 180 {
 181     int l;
 182     node_t *n;
 183     l = get_level(ptst);
 184     n = gc_alloc(ptst, gc_id[l - 1]);
 185     n->level = l;
 186 #ifndef FAT_MTX
 187     mcs_init(&n->m);
 188 #endif
 189 #ifdef TINY_MTX
 190     for ( l = 0; l < n->level; l++ )
 191     {
 192         mcs_init(&n->next[l].m);
 193     }
 194 #endif
 195     return(n);
 196 }
 197
 198
 199 /* Free a node to the garbage collector. */
 200 static void free_node(ptst_t *ptst, sh_node_pt n)
 201 {
 202     gc_free(ptst, (void *)n, gc_id[n->level - 1]);
 203 }
 204
 205
 206 /*
 207  * Find and lock predecessor at level @i of node with key @k. This
 208  * predecessor must have key >= @x->k.
 209  */
 210 #ifndef FAT_MTX
 211 static sh_node_pt get_lock(sh_node_pt x, setkey_t k, int i, qnode_t *qn)
 212 {
 213     sh_node_pt y;
 214     setkey_t  y_k;
 215
 216     for ( ; ; )
 217     {
 218         READ_FIELD(y,   x->next[i].p);
 219         READ_FIELD(y_k, y->k);
 220         if ( y_k >= k ) break;
 221     retry:
 222         x = y;
 223     }
 224
 225     PTR_UPDATE_LOCK(x, i, qn); /* MB => no need for READ_FIELD on x or y. */
 226     y = x->next[i].p;
 227     if ( y->k < k )
 228     {
 229         PTR_UPDATE_UNLOCK(x, i, qn);
 230         goto retry;
 231     }
 232
 233     return(x);
 234 }
 235 #else
 236 #define get_lock(_x,_k,_i,_qn) (_x)
 237 #endif
 238
 239
 240 /*
 241  * Search for first non-deleted node, N, with key >= @k at each level in @l.
 242  * RETURN VALUES:
 243  *  Array @pa: @pa[i] is non-deleted predecessor of N at level i
 244  *  MAIN RETURN VALUE: N at level 0.
 245  */
 246 static sh_node_pt search_predecessors(set_t *l, setkey_t k, sh_node_pt *pa)
 247 {
 248     sh_node_pt x, y;
 249     setkey_t  y_k;
 250     int        i;
 251
 252     x = &l->head;
 253     for ( i = NUM_LEVELS - 1; i >= 0; i-- )
 254     {
 255         for ( ; ; )
 256         {
 257             READ_FIELD(y,   x->next[i].p);
 258             READ_FIELD(y_k, y->k);
 259             if ( y_k >= k ) break;
 260             x = y; /* remember largest predecessor so far */
 261         }
 262
 263         if ( pa ) pa[i] = x;
 264     }
 265
 266     return(y);
 267 }
 268
 269
 270 /*
 271  * PUBLIC FUNCTIONS
 272  */
 273
 274 set_t *set_alloc(void)
 275 {
 276     set_t *l;
 277     node_t *n;
 278     int i;
 279
 280     n = malloc(sizeof(*n) + (NUM_LEVELS-1)*sizeof(ptr_t));
 281     memset(n, 0, sizeof(*n) + (NUM_LEVELS-1)*sizeof(ptr_t));
 282     n->k = SENTINEL_KEYMAX;
 283
 284     l = malloc(sizeof(*l) + (NUM_LEVELS-1)*sizeof(ptr_t));
 285     l->head.k = SENTINEL_KEYMIN;
 286     l->head.level = NUM_LEVELS;
 287 #ifdef FAT_MTX
 288     mcs_init(&l->m);
 289 #else
 290     mcs_init(&l->head.m);
 291 #endif
 292     for ( i = 0; i < NUM_LEVELS; i++ )
 293     {
 294         l->head.next[i].p = n;
 295 #ifdef TINY_MTX
 296         mcs_init(&l->head.next[i].m);
 297 #endif
 298     }
 299
 300     return(l);
 301 }
 302
 303
 304 setval_t set_update(set_t *l, setkey_t k, setval_t v, int overwrite)
 305 {
 306     setval_t  ov = NULL;
 307     ptst_t    *ptst;
 308     sh_node_pt update[NUM_LEVELS];
 309     sh_node_pt x, y;
 310     int        i;
 311     qnode_t    l_qn, x_qn, y_qn;
 312
 313     k = CALLER_TO_INTERNAL_KEY(k);
 314
 315     ptst = critical_enter();
 316     LIST_LOCK(l, &l_qn);
 317
 318     (void)search_predecessors(l, k, update);
 319
 320     x = get_lock(update[0], k, 0, &x_qn);
 321     y = x->next[0].p;
 322     if ( y->k == k )
 323     {
 324         ov = y->v;
 325         if ( overwrite ) y->v = v;
 326         PTR_UPDATE_UNLOCK(x, 0, &x_qn);
 327         goto out;
 328     }
 329
 330     /* Not in the list, so do the insertion. */
 331     y    = alloc_node(ptst);
 332     y->k = k;
 333     y->v = v;
 334     NODE_LOCK(y, &y_qn);
 335
 336     for ( i = 0; i < y->level; i++ )
 337     {
 338         if ( i != 0 ) x = get_lock(update[i], k, i, &x_qn);
 339         y->next[i].p = x->next[i].p;
 340         WMB();
 341         x->next[i].p = y;
 342         PTR_UPDATE_UNLOCK(x, i, &x_qn);
 343     }
 344
 345     NODE_UNLOCK(y, &y_qn);
 346
 347  out:
 348     LIST_UNLOCK(l, &l_qn);
 349     critical_exit(ptst);
 350     return(ov);
 351 }
 352
 353
 354 setval_t set_remove(set_t *l, setkey_t k)
 355 {
 356     setval_t  v = NULL;
 357     ptst_t    *ptst;
 358     sh_node_pt update[NUM_LEVELS];
 359     sh_node_pt x, y;
 360     int        i;
 361     qnode_t    l_qn, x_qn, y_qn, yd_qn;
 362
 363     k = CALLER_TO_INTERNAL_KEY(k);
 364
 365     ptst = critical_enter();
 366     LIST_LOCK(l, &l_qn);
 367
 368     y = search_predecessors(l, k, update);
 369
 370 #ifdef FAT_MTX
 371     if ( y->k != k ) goto out;
 372 #else
 373     y = update[0];
 374     for ( ; ; )
 375     {
 376         setkey_t y_k;
 377         y = y->next[0].p; /* no need for READ_FIELD() */
 378         READ_FIELD(y_k, y->k);
 379         if ( y_k > k ) goto out;
 380         NODE_LOCK(y, &y_qn);
 381         if ( (y_k == k) && (y_k <= y->next[0].p->k) ) break;
 382         NODE_UNLOCK(y, &y_qn);
 383     }
 384 #endif
 385
 386     /* @y is the correct node, and we have it locked, so now delete it. */
 387     for ( i = y->level - 1; i >= 0; i-- )
 388     {
 389         x = get_lock(update[i], k, i, &x_qn);
 390         PTR_DELETE_LOCK(y, i, &yd_qn);
 391         x->next[i].p = y->next[i].p;
 392         WMB();
 393         y->next[i].p = x;
 394         PTR_DELETE_UNLOCK(y, i, &yd_qn);
 395         PTR_UPDATE_UNLOCK(x, i, &x_qn);
 396     }
 397
 398     v = y->v;
 399     free_node(ptst, y);
 400     NODE_UNLOCK(y, &y_qn);
 401
 402  out:
 403     LIST_UNLOCK(l, &l_qn);
 404     critical_exit(ptst);
 405     return(v);
 406 }
 407
 408
 409 setval_t set_lookup(set_t *l, setkey_t k)
 410 {
 411     setval_t  v = NULL;
 412     ptst_t    *ptst;
 413     sh_node_pt x;
 414
 415     k = CALLER_TO_INTERNAL_KEY(k);
 416
 417     ptst = critical_enter();
 418
 419     x = search_predecessors(l, k, NULL);
 420     if ( x->k == k ) READ_FIELD(v, x->v);
 421
 422     critical_exit(ptst);
 423     return(v);
 424 }
 425
 426
 427 void _init_set_subsystem(void)
 428 {
 429     int i;
 430
 431     for ( i = 0; i < NUM_LEVELS; i++ )
 432     {
 433         gc_id[i] = gc_add_allocator(sizeof(node_t) + i*sizeof(ptr_t));
 434     }
 435 }