src/mcas/bst_lock_fraser.c

   1 /******************************************************************************
   2  * bst_lock_fraser.c
   3  *
   4  * Lock-free binary serach trees (BSTs), based on per-node spinlocks.
   5  * Uses threaded tree presentation as described in my PhD dissertation:
   6  *  "Practical Lock-Freedom", University of Cambridge, 2003.
   7  *
   8  * Copyright (c) 2002-2003, K A Fraser
   9
  10 Redistribution and use in source and binary forms, with or without
  11 modification, are permitted provided that the following conditions are
  12 met:
  13
  14     * Redistributions of source code must retain the above copyright
  15     * notice, this list of conditions and the following disclaimer.
  16     * Redistributions in binary form must reproduce the above
  17     * copyright notice, this list of conditions and the following
  18     * disclaimer in the documentation and/or other materials provided
  19     * with the distribution.  Neither the name of the Keir Fraser
  20     * nor the names of its contributors may be used to endorse or
  21     * promote products derived from this software without specific
  22     * prior written permission.
  23
  24 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  25 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  26 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
  27 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
  28 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  29 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
  30 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  31 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  32 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  33 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  34 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  35  *
  36  */
  37
  38 #define __SET_IMPLEMENTATION__
  39
  40 #include <ucontext.h>
  41 #include <signal.h>
  42 #include <stdio.h>
  43 #include <limits.h>
  44 #include <errno.h>
  45 #include <stdlib.h>
  46 #include <assert.h>
  47 #include <sys/types.h>
  48 #include <sys/stat.h>
  49 #include <fcntl.h>
  50 #include <unistd.h>
  51 #include <stdarg.h>
  52 #include "portable_defns.h"
  53 #include "gc.h"
  54 #include "set.h"
  55
  56 #define MARK_THREAD      1
  57 #define THREAD(_p)     ((node_t *)((int_addr_t)(_p)|(MARK_THREAD)))
  58 #define UNTHREAD(_p) ((node_t *)((int_addr_t)(_p)&~MARK_THREAD))
  59 #define IS_THREAD(_p)       ((int)((int_addr_t)(_p)&MARK_THREAD))
  60
  61 #define IS_GARBAGE(_n)      ((_n)->v == NULL)
  62
  63 typedef struct node_st node_t;
  64 typedef struct set_st set_t;
  65
  66 struct node_st
  67 {
  68     setkey_t k;
  69     setval_t v;
  70     node_t *l, *r;
  71     mcs_lock_t lock;
  72 };
  73
  74 struct set_st
  75 {
  76     node_t root;
  77     node_t sentinel;
  78 };
  79
  80 static int gc_id;
  81
  82 /* We use these flags to determine whch nodes are currently locked. */
  83 #define P_LOCKED    0x01
  84 #define N_LOCKED    0x02
  85 #define PAL_LOCKED  0x04
  86 #define PAR_LOCKED  0x08
  87 #define AL_LOCKED   0x10
  88 #define AR_LOCKED   0x20
  89
  90 #define LOCK(_n, _qn, _flag)                                  \
  91     do {                                                      \
  92         mcs_lock(&(_n)->lock, &(_qn));                        \
  93         if ( IS_GARBAGE(_n) ) {                               \
  94             mcs_unlock(&(_n)->lock, &(_qn));                  \
  95             goto retry;                                       \
  96         }                                                     \
  97         lock_flags |= (_flag);                                \
  98     } while ( 0 )
  99
 100 #define UNLOCK(_n, _qn, _flag)                                \
 101     do {                                                      \
 102         if ( (lock_flags & (_flag)) )                         \
 103              mcs_unlock(&(_n)->lock, &(_qn));                 \
 104     } while ( 0 )
 105
 106
 107 /*
 108  * Search for node with key == k. Return NULL if none such, else ptr to node.
 109  * @ppn is filled in with parent node, or closest leaf if no match.
 110  * p and n will both be unmarked and adjacent on return.
 111  */
 112 static node_t *search(set_t *s, setkey_t k, node_t **ppn)
 113 {
 114     node_t *p, *n, *c;
 115
 116  retry:
 117     p = &s->root;
 118     n = p->r;
 119
 120     while ( !IS_THREAD(n) )
 121     {
 122         if ( k < n->k ) {
 123             c = n->l;
 124             assert(UNTHREAD(c)->k < n->k);
 125         } else if ( k > n->k ) {
 126             c = n->r;
 127             assert(UNTHREAD(c)->k > n->k);
 128         } else /* k == n->k */
 129             goto found;
 130
 131         p = n; n = c;
 132     }
 133
 134     /* Follow final thread, just in case. */
 135     c = UNTHREAD(n);
 136     if ( k == c->k ) goto followed_thread;
 137
 138  found:
 139     if ( ppn ) *ppn = p;
 140     return n;
 141
 142  followed_thread:
 143     if ( ppn ) { RMB(); goto retry; }
 144     return c;
 145 }
 146
 147
 148 set_t *set_alloc(void)
 149 {
 150     set_t *s;
 151
 152     s = malloc(sizeof(*s));
 153     mcs_init(&s->root.lock);
 154     s->root.k = SENTINEL_KEYMIN;
 155     s->root.v = (setval_t)(~0UL);
 156     s->root.l = THREAD(&s->root);
 157     s->root.r = THREAD(&s->sentinel);
 158
 159     mcs_init(&s->sentinel.lock);
 160     s->sentinel.k = SENTINEL_KEYMAX;
 161
 162     return s;
 163 }
 164
 165
 166 setval_t set_update(set_t *s, setkey_t k, setval_t v, int overwrite)
 167 {
 168     setval_t ov;
 169     node_t *p, *n, *new = NULL;
 170     qnode_t qp, qn;
 171     ptst_t *ptst;
 172     int lock_flags, r = 0;
 173
 174     k = CALLER_TO_INTERNAL_KEY(k);
 175
 176     ptst = critical_enter();
 177
 178     do {
 179         ov = NULL;
 180         lock_flags = 0;
 181
 182         n = search(s, k, &p);
 183
 184         if ( !IS_THREAD(n) )
 185         {
 186             LOCK(n, qn, N_LOCKED);
 187             ov = n->v;
 188             if ( overwrite ) n->v = v;
 189         }
 190         else
 191         {
 192             if ( new == NULL )
 193             {
 194                 new = gc_alloc(ptst, gc_id);
 195                 mcs_init(&new->lock);
 196                 new->k = k;
 197                 new->v = v;
 198             }
 199
 200             LOCK(p, qp, P_LOCKED);
 201
 202             if ( p->k < k )
 203             {
 204                 if ( (p->r != n) || (UNTHREAD(n)->k < k) ) goto retry;
 205                 new->l = THREAD(p);
 206                 new->r = n;
 207                 WMB();
 208                 p->r = new;
 209             }
 210             else
 211             {
 212                 if ( (p->l != n) || (UNTHREAD(n)->k > k) ) goto retry;
 213                 new->l = n;
 214                 new->r = THREAD(p);
 215                 WMB();
 216                 p->l = new;
 217             }
 218
 219             new = NULL; /* node is now in tree */
 220         }
 221
 222         r = 1; /* success */
 223
 224     retry:
 225         UNLOCK(p, qp, P_LOCKED);
 226         UNLOCK(n, qn, N_LOCKED);
 227     }
 228     while ( !r );
 229
 230     if ( new ) gc_free(ptst, new, gc_id);
 231     critical_exit(ptst);
 232     return ov;
 233 }
 234
 235
 236 #define FIND_HELPER(_d1, _d2, _n, _ap, _a)                               \
 237 {                                                                        \
 238     node_t *ac;                                                          \
 239     (_ap) = NULL;                                                        \
 240     (_a)  = (_n);                                                        \
 241     ac    = (_a)->_d1;                                                   \
 242     while ( !IS_THREAD(ac) )                                             \
 243     {                                                                    \
 244         (_ap) = (_a);                                                    \
 245         (_a)  = ac;                                                      \
 246         ac    = (_a)->_d2;                                               \
 247     }                                                                    \
 248 }
 249
 250
 251 /*
 252  * Order of first two cases does matter! If @n is the left-link of @p, then
 253  * we use DELETE_HELPER(l, r). What matters is what we do when @n is a leaf.
 254  * In this case we end up choosing n->l to propagate to p->l -- this
 255  * happens to be the correct choice :-)
 256  *
 257  * NB. Note symmetric deletion cases dependent on parameter @dir. We
 258  * could simplify the algorithm by always following one direction. In fact,
 259  * that is slightly worse, or much worse, depending on the chosen case
 260  * (hint: works best with dir hardwired to zero :-)....
 261  */
 262 #define dir 0
 263 #define DELETE_HELPER(_d1, _d2)                                              \
 264     FIND_HELPER(_d1, _d2, n, pal, al);                                       \
 265     FIND_HELPER(_d2, _d1, n, par, ar);                                       \
 266     if ( IS_THREAD(n ## _d2) )                                               \
 267     {                                                                        \
 268         if ( IS_THREAD(n ## _d1) )                                           \
 269         {                                                                    \
 270             *p_pc = n ## _d1;                                                \
 271         }                                                                    \
 272         else                                                                 \
 273         {                                                                    \
 274             LOCK(al, qal, AL_LOCKED);                                        \
 275             if ( al->_d2 != THREAD(n) ) goto retry;                          \
 276             *p_pc = n ## _d1;                                                \
 277             al->_d2 = n ## _d2;                                              \
 278         }                                                                    \
 279     }                                                                        \
 280     else if ( IS_THREAD(n ## _d1) )                                          \
 281     {                                                                        \
 282         LOCK(ar, qar, AR_LOCKED);                                            \
 283         if ( ar->_d1 != THREAD(n) ) goto retry;                              \
 284         *p_pc = n ## _d2;                                                    \
 285         ar->_d1 = n ## _d1;                                                  \
 286     }                                                                        \
 287     else if ( dir )                                                          \
 288     {                                                                        \
 289         if ( par != n )                                                      \
 290         {                                                                    \
 291             LOCK(par, qpar, PAR_LOCKED);                                     \
 292             if ( par->_d1 != ar ) goto retry;                                \
 293         }                                                                    \
 294         LOCK(al, qal, AL_LOCKED);                                            \
 295         LOCK(ar, qar, AR_LOCKED);                                            \
 296         if ( (al->_d2 != THREAD(n)) || (ar->_d1 != THREAD(n)) ) goto retry;  \
 297         al->_d2 = THREAD(ar);                                                \
 298         ar->_d1 = n ## _d1;                                                  \
 299         if ( par != n )                                                      \
 300         {                                                                    \
 301             ac = ar->_d2;                                                    \
 302             ar->_d2 = n ## _d2;                                              \
 303             par->_d1 = IS_THREAD(ac) ? THREAD(ar) : ac;                      \
 304         }                                                                    \
 305         WMB(); /* New links in AR must appear before it is raised. */        \
 306         *p_pc = ar;                                                          \
 307     }                                                                        \
 308     else                                                                     \
 309     {                                                                        \
 310         if ( pal != n )                                                      \
 311         {                                                                    \
 312             LOCK(pal, qpal, PAL_LOCKED);                                     \
 313             if ( pal->_d2 != al ) goto retry;                                \
 314         }                                                                    \
 315         LOCK(al, qal, AL_LOCKED);                                            \
 316         LOCK(ar, qar, AR_LOCKED);                                            \
 317         if ( (al->_d2 != THREAD(n)) || (ar->_d1 != THREAD(n)) ) goto retry;  \
 318         al->_d2 = n ## _d2;                                                  \
 319         ar->_d1 = THREAD(al);                                                \
 320         if ( pal != n )                                                      \
 321         {                                                                    \
 322             ac = al->_d1;                                                    \
 323             al->_d1 = n ## _d1;                                              \
 324             pal->_d2 = IS_THREAD(ac) ? THREAD(al) : ac;                      \
 325         }                                                                    \
 326         WMB(); /* New links in AL must appear before it is raised. */        \
 327         *p_pc = al;                                                          \
 328     }
 329
 330
 331 /* @k: key of node to be deleted */
 332 setval_t set_remove(set_t *s, setkey_t k)
 333 {
 334     node_t *p, *n, *nl, *nr, *al, *ar, *pal, *par, *ac, **p_pc;
 335     qnode_t qp, qn, qal, qar, qpal, qpar;
 336     int r = 0, lock_flags;
 337     setval_t v;
 338     ptst_t *ptst;
 339
 340     k = CALLER_TO_INTERNAL_KEY(k);
 341
 342     ptst = critical_enter();
 343
 344     do {
 345         v = NULL;
 346         lock_flags = 0;
 347
 348         n = search(s, k, &p);
 349         if ( IS_THREAD(n) ) goto out;
 350
 351         LOCK(p, qp, P_LOCKED);
 352         p_pc = (p->k > n->k) ? &p->l : &p->r;
 353         if ( *p_pc != n ) goto retry;
 354
 355         LOCK(n, qn, N_LOCKED);
 356
 357         nl = n->l;
 358         nr = n->r;
 359
 360         if ( p->k > n->k )
 361         {
 362             /* @n is leftwards link from @p. */
 363             DELETE_HELPER(l, r);
 364         }
 365         else
 366         {
 367             /* @n is rightwards link from @p. */
 368             DELETE_HELPER(r, l);
 369         }
 370
 371         r = 1;
 372         v = n->v;
 373         n->v = NULL;
 374
 375     retry:
 376         UNLOCK(p, qp, P_LOCKED);
 377         UNLOCK(n, qn, N_LOCKED);
 378         UNLOCK(pal, qpal, PAL_LOCKED);
 379         UNLOCK(par, qpar, PAR_LOCKED);
 380         UNLOCK(al, qal, AL_LOCKED);
 381         UNLOCK(ar, qar, AR_LOCKED);
 382     }
 383     while ( !r );
 384
 385     gc_free(ptst, n, gc_id);
 386
 387  out:
 388     critical_exit(ptst);
 389     return v;
 390 }
 391
 392
 393 setval_t set_lookup(set_t *s, setkey_t k)
 394 {
 395     node_t *n;
 396     setval_t v;
 397     ptst_t *ptst;
 398
 399     k = CALLER_TO_INTERNAL_KEY(k);
 400
 401     ptst = critical_enter();
 402
 403     n = search(s, k, NULL);
 404     v = (!IS_THREAD(n)) ? n->v : NULL;
 405
 406     critical_exit(ptst);
 407     return v;
 408 }
 409
 410
 411 void _init_set_subsystem(void)
 412 {
 413     gc_id = gc_add_allocator(sizeof(node_t));
 414 }