src/mcas/skip_stm.c

   1 /******************************************************************************
   2  * skip_stm.c
   3  *
   4  * Skip lists, allowing concurrent update by use of the STM abstraction.
   5  *
   6  * Copyright (c) 2003, K A Fraser
   7  *
   8
   9 Redistribution and use in source and binary forms, with or without
  10 modification, are permitted provided that the following conditions are
  11 met:
  12
  13     * Redistributions of source code must retain the above copyright
  14     * notice, this list of conditions and the following disclaimer.
  15     * Redistributions in binary form must reproduce the above
  16     * copyright notice, this list of conditions and the following
  17     * disclaimer in the documentation and/or other materials provided
  18     * with the distribution.  Neither the name of the Keir Fraser
  19     * nor the names of its contributors may be used to endorse or
  20     * promote products derived from this software without specific
  21     * prior written permission.
  22
  23 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  24 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  25 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
  26 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
  27 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  28 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
  29 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  30 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  31 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  32 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  33 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  34  */
  35
  36 #define __SET_IMPLEMENTATION__
  37
  38 #include <unistd.h>
  39 #include <stdlib.h>
  40 #include <string.h>
  41 #include <assert.h>
  42 #include "portable_defns.h"
  43 #include "gc.h"
  44 #include "stm.h"
  45 #include "set.h"
  46
  47 typedef struct node_st node_t;
  48 typedef stm_blk set_t;
  49
  50 struct node_st
  51 {
  52     int       level;
  53     setkey_t  k;
  54     setval_t  v;
  55     stm_blk  *next[NUM_LEVELS];
  56 };
  57
  58 static struct {
  59     CACHE_PAD(0);
  60     stm *memory;    /* read-only */
  61     CACHE_PAD(2);
  62 } shared;
  63
  64 #define MEMORY (shared.memory)
  65
  66 /*
  67  * Random level generator. Drop-off rate is 0.5 per level.
  68  * Returns value 1 <= level <= NUM_LEVELS.
  69  */
  70 static int get_level(ptst_t *ptst)
  71 {
  72     unsigned long r = rand_next(ptst);
  73     int l = 1;
  74     r = (r >> 4) & ((1 << (NUM_LEVELS-1)) - 1);
  75     while ( (r & 1) ) { l++; r >>= 1; }
  76     return l;
  77 }
  78
  79
  80 /*
  81  * Search for first non-deleted node, N, with key >= @k at each level in @l.
  82  * RETURN VALUES:
  83  *  Array @pa: @pa[i] is non-deleted predecessor of N at level i
  84  *  Array @na: @na[i] is N itself, which should be pointed at by @pa[i]
  85  *  MAIN RETURN VALUE: same as @na[0], direct pointer open for reading.
  86  */
  87 static node_t *search_predecessors(
  88     ptst_t *ptst, stm_tx *tx, set_t *l, setkey_t k, stm_blk **pa, stm_blk **na)
  89 {
  90     stm_blk *xb, *x_nextb;
  91     node_t  *x,  *x_next;
  92     int      i;
  93
  94     xb = l;
  95     x  = read_stm_blk(ptst, tx, l);
  96     for ( i = NUM_LEVELS - 1; i >= 0; i-- )
  97     {
  98         for ( ; ; )
  99         {
 100             x_nextb = x->next[i];
 101             x_next  = read_stm_blk(ptst, tx, x_nextb);
 102             if ( x_next->k >= k ) break;
 103             xb = x_nextb;
 104             x  = x_next;
 105         }
 106
 107         if ( pa ) pa[i] = xb;
 108         if ( na ) na[i] = x_nextb;
 109     }
 110
 111     return x_next;
 112 }
 113
 114
 115 /*
 116  * PUBLIC FUNCTIONS
 117  */
 118
 119 set_t *set_alloc(void)
 120 {
 121     ptst_t  *ptst;
 122     stm_blk *hb, *tb;
 123     node_t  *h, *t;
 124     int      i;
 125
 126     ptst = critical_enter();
 127
 128     tb = new_stm_blk(ptst, MEMORY);
 129     t  = init_stm_blk(ptst, MEMORY, tb);
 130     memset(t, 0, sizeof(*t));
 131     t->k = SENTINEL_KEYMAX;
 132
 133     hb = new_stm_blk(ptst, MEMORY);
 134     h  = init_stm_blk(ptst, MEMORY, hb);
 135     memset(h, 0, sizeof(*h));
 136     h->k     = SENTINEL_KEYMIN;
 137     h->level = NUM_LEVELS;
 138     for ( i = 0; i < NUM_LEVELS; i++ )
 139         h->next[i] = tb;
 140
 141     critical_exit(ptst);
 142
 143     return hb;
 144 }
 145
 146
 147 setval_t set_update(set_t *l, setkey_t k, setval_t v, int overwrite)
 148 {
 149     ptst_t   *ptst;
 150     stm_tx   *tx;
 151     setval_t  ov;
 152     stm_blk  *bpreds[NUM_LEVELS], *bsuccs[NUM_LEVELS], *newb = NULL;
 153     node_t   *x, *p, *new;
 154     int       i;
 155
 156     k = CALLER_TO_INTERNAL_KEY(k);
 157
 158     ptst = critical_enter();
 159
 160     do {
 161         new_stm_tx(tx, ptst, MEMORY);
 162         x = search_predecessors(ptst, tx, l, k, bpreds, bsuccs);
 163
 164         if ( x->k == k )
 165         {
 166             x    = write_stm_blk(ptst, tx, bsuccs[0]);
 167             ov   = x->v;
 168             x->v = v;
 169         }
 170         else
 171         {
 172             ov = NULL;
 173
 174             if ( newb == NULL )
 175             {
 176                 newb = new_stm_blk(ptst, MEMORY);
 177                 new  = init_stm_blk(ptst, MEMORY, newb);
 178                 new->k = k;
 179                 new->v = v;
 180                 new->level = get_level(ptst);
 181             }
 182
 183             for ( i = 0; i < new->level; i++ )
 184             {
 185                 new->next[i] = bsuccs[i];
 186                 p = write_stm_blk(ptst, tx, bpreds[i]);
 187                 p->next[i] = newb;
 188             }
 189         }
 190     }
 191     while ( !commit_stm_tx(ptst, tx) );
 192
 193     if ( (ov != NULL) && (newb != NULL) )
 194         free_stm_blk(ptst, MEMORY, newb);
 195
 196     critical_exit(ptst);
 197
 198     return ov;
 199 }
 200
 201
 202 setval_t set_remove(set_t *l, setkey_t k)
 203 {
 204     setval_t  v;
 205     ptst_t   *ptst;
 206     stm_tx   *tx;
 207     stm_blk  *bpreds[NUM_LEVELS], *bsuccs[NUM_LEVELS];
 208     node_t   *p, *x;
 209     int       i;
 210
 211     k = CALLER_TO_INTERNAL_KEY(k);
 212
 213     ptst = critical_enter();
 214
 215     do {
 216         new_stm_tx(tx, ptst, MEMORY);
 217         x = search_predecessors(ptst, tx, l, k, bpreds, bsuccs);
 218         if ( x->k == k )
 219         {
 220             v = x->v;
 221             for ( i = 0; i < x->level; i++ )
 222             {
 223                 p = write_stm_blk(ptst, tx, bpreds[i]);
 224                 p->next[i] = x->next[i];
 225             }
 226         }
 227         else
 228         {
 229             v = NULL;
 230         }
 231     }
 232     while ( !commit_stm_tx(ptst, tx) );
 233
 234     if ( v != NULL )
 235         free_stm_blk(ptst, MEMORY, bsuccs[0]);
 236
 237     critical_exit(ptst);
 238
 239     return v;
 240 }
 241
 242
 243 setval_t set_lookup(set_t *l, setkey_t k)
 244 {
 245     setval_t  v;
 246     ptst_t   *ptst;
 247     stm_tx   *tx;
 248     node_t   *x;
 249
 250     k = CALLER_TO_INTERNAL_KEY(k);
 251
 252     ptst = critical_enter();
 253
 254     do {
 255         new_stm_tx(tx, ptst, MEMORY);
 256         x = search_predecessors(ptst, tx, l, k, NULL, NULL);
 257         v = (x->k == k) ? x->v : NULL;
 258     }
 259     while ( !commit_stm_tx(ptst, tx) );
 260
 261     critical_exit(ptst);
 262
 263     return v;
 264 }
 265
 266
 267 void _init_set_subsystem(void)
 268 {
 269     ptst_t *ptst = critical_enter();
 270     _init_stm_subsystem(0);
 271     MEMORY = new_stm(ptst, sizeof(node_t));
 272     critical_exit(ptst);
 273 }