src/mcas/bst_mcas.c

   1 /******************************************************************************
   2  * bst_mcas.c
   3  *
   4  * Lock-free binary search trees (BSTs), based on MCAS.
   5  * Uses a threaded representation to synchronise searches with deletions.
   6  *
   7  * Copyright (c) 2002-2003, K A Fraser
   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 <stdio.h>
  39 #include <stdlib.h>
  40 #include <unistd.h>
  41 #include "portable_defns.h"
  42 #include "gc.h"
  43 #include "set.h"
  44
  45 /* Allow MCAS marks to be detected using a single bitop (see IS_MCAS_OWNED). */
  46 #define MARK_IN_PROGRESS 2
  47 #define MARK_PTR_TO_CD   3
  48
  49 #define MARK_THREAD      1
  50 #define MARK_GARBAGE     4
  51
  52 #define THREAD(_p)     ((node_t *)((int_addr_t)(_p)|(MARK_THREAD)))
  53 #define GARBAGE(_p)    ((node_t *)((int_addr_t)(_p)|(MARK_GARBAGE)))
  54 #define UNTHREAD(_p) ((node_t *)((int_addr_t)(_p)&~MARK_THREAD))
  55 #define UNGARBAGE(_p) ((node_t *)((int_addr_t)(_p)&~MARK_GARBAGE))
  56 /* Following only matches 2 and 3 (mod 4). Those happen to be MCAS marks :) */
  57 #define IS_MCAS_OWNED(_p)   ((int)((int_addr_t)(_p)&2))
  58 /* Matches 1 and 3 (mod 4). So only use if the ref is *not* owned by MCAS!! */
  59 #define IS_THREAD(_p)       ((int)((int_addr_t)(_p)&MARK_THREAD))
  60 /* Only use if the ref is *not* owned by MCAS (which may use bit 2)!! */
  61 #define IS_GARBAGE(_p)      ((int)((int_addr_t)(_p)&MARK_GARBAGE))
  62
  63 #include "mcas.c"
  64
  65 typedef struct node_st node_t;
  66 typedef struct set_st set_t;
  67
  68 struct node_st
  69 {
  70     setkey_t k;
  71     setval_t v;
  72     node_t *l, *r;
  73 };
  74
  75 struct set_st
  76 {
  77     node_t root;
  78     node_t sentinel;
  79 };
  80
  81 static int gc_id;
  82
  83 #define READ_LINK(_var, _link)                              \
  84     do {                                                    \
  85         (_var) = (_link);                                   \
  86         if ( !IS_MCAS_OWNED(_var) ) break;                  \
  87         mcas_fixup((void **)&(_link), (_var));              \
  88     } while ( 1 )
  89
  90 #define WEAK_READ_LINK(_var, _link)                         \
  91     do {                                                    \
  92         READ_LINK(_var, _link);                             \
  93         (_var) = UNGARBAGE(_var);                           \
  94     } while ( 0 )
  95
  96 #define STRONG_READ_LINK(_var, _link)                       \
  97     do {                                                    \
  98         READ_LINK(_var, _link);                             \
  99         if ( IS_GARBAGE(_var) ) goto retry;                 \
 100     } while ( 0 )
 101
 102 #define PROCESS_VAL(_v,_pv)                                 \
 103     do {                                                    \
 104         while ( IS_MCAS_OWNED(_v) )                         \
 105         {                                                   \
 106             mcas_fixup((void **)(_pv), (_v));               \
 107             (_v) = *(_pv);                                  \
 108         }                                                   \
 109     } while ( 0 )
 110
 111
 112 /*
 113  * Search for node with key == k. Return NULL if none such, else ptr to node.
 114  * @ppn is filled in with parent node, or closest leaf if no match.
 115  * p and n will both be unmarked and adjacent on return.
 116  */
 117 static node_t *search(set_t *s, setkey_t k, node_t **ppn)
 118 {
 119     node_t *p, *n, *c;
 120
 121  retry:
 122     p = &s->root;
 123     WEAK_READ_LINK(n, p->r);
 124
 125     while ( !IS_THREAD(n) )
 126     {
 127         if ( k < n->k ) {
 128             WEAK_READ_LINK(c, n->l);
 129             assert(UNTHREAD(c)->k < n->k);
 130         } else if ( k > n->k ) {
 131             WEAK_READ_LINK(c, n->r);
 132             assert(UNTHREAD(c)->k > n->k);
 133         } else /* k == n->k */
 134             goto found;
 135
 136         p = n; n = c;
 137     }
 138
 139     /* Follow final thread, just in case. */
 140     c = UNTHREAD(n);
 141     if ( k == c->k ) goto followed_thread;
 142
 143  found:
 144     if ( ppn ) *ppn = p;
 145     return n;
 146
 147  followed_thread:
 148     if ( ppn ) { RMB(); goto retry; }
 149     return c;
 150 }
 151
 152
 153 set_t *set_alloc(void)
 154 {
 155     set_t *s;
 156
 157     static int mcas_inited = 0;
 158     if ( !CASIO(&mcas_inited, 0, 1) )
 159     {
 160         if ( (sizeof(node_t) % 8) != 0 )
 161         {
 162             fprintf(stderr, "FATAL: node_t must be multiple of 8 bytes\n");
 163             *((int*)0)=0;
 164         }
 165         mcas_init();
 166     }
 167
 168     s = malloc(sizeof(*s));
 169     s->root.k = SENTINEL_KEYMIN;
 170     s->root.v = NULL;
 171     s->root.l = THREAD(&s->root);
 172     s->root.r = THREAD(&s->sentinel);
 173
 174     s->sentinel.k = SENTINEL_KEYMAX;
 175
 176     return s;
 177 }
 178
 179
 180 setval_t set_update(set_t *s, setkey_t k, setval_t v, int overwrite)
 181 {
 182     setval_t ov, nov;
 183     node_t *p, *n, *new = NULL, **ppc;
 184     ptst_t *ptst;
 185
 186     k = CALLER_TO_INTERNAL_KEY(k);
 187
 188     ptst = critical_enter();
 189
 190     do {
 191     retry:
 192         ov = NULL;
 193
 194         n = search(s, k, &p);
 195         if ( !IS_THREAD(n) )
 196         {
 197             /* Already a @k node in the set: update its mapping. */
 198             nov = n->v;
 199             do {
 200                 ov = nov;
 201                 PROCESS_VAL(ov, &n->v);
 202                 if ( ov == NULL ) goto retry;
 203             }
 204             while ( overwrite && ((nov = CASPO(&n->v, ov, v)) != ov) );
 205
 206             goto out;
 207         }
 208
 209         if ( new == NULL )
 210         {
 211             new = gc_alloc(ptst, gc_id);
 212             new->k = k;
 213             new->v = v;
 214         }
 215
 216         if ( p->k < k )
 217         {
 218             /* Ensure we insert in the correct interval. */
 219             if ( UNTHREAD(n)->k < k ) goto retry;
 220             new->l = THREAD(p);
 221             new->r = n;
 222             ppc = &p->r;
 223         }
 224         else
 225         {
 226             if ( UNTHREAD(n)->k > k ) goto retry;
 227             new->l = n;
 228             new->r = THREAD(p);
 229             ppc = &p->l;
 230         }
 231
 232         WMB_NEAR_CAS();
 233     }
 234     while ( CASPO(ppc, n, new) != n );
 235
 236     new = NULL;
 237
 238  out:
 239     if ( new ) gc_free(ptst, new, gc_id);
 240     critical_exit(ptst);
 241     return ov;
 242 }
 243
 244
 245 #define FIND_HELPER(_d1, _d2, _n, _ap, _a)                               \
 246 {                                                                        \
 247     node_t *ac;                                                          \
 248     (_ap) = NULL;                                                        \
 249     (_a)  = (_n);                                                        \
 250     WEAK_READ_LINK(ac, (_a)->_d1);                                       \
 251     while ( !IS_THREAD(ac) )                                             \
 252     {                                                                    \
 253         (_ap) = (_a);                                                    \
 254         (_a)  = ac;                                                      \
 255         WEAK_READ_LINK(ac, (_a)->_d2);                                   \
 256     }                                                                    \
 257 }
 258
 259
 260 /*
 261  * Order of first two cases does matter! If @n is the left-link of @p, then
 262  * we use DELETE_HELPER(l, r). What matters is what we do when @n is a leaf.
 263  * In this case we end up choosing n->l to propagate to p->l -- this
 264  * happens to be the correct choice :-)
 265  *
 266  * NB. Note symmetric deletion cases dependent on parameter @dir. We
 267  * could simplify the algorithm by always following one direction. In fact,
 268  * that is slightly worse, or much worse, depending on the chosen case
 269  * (hint: works best with dir hardwired to zero :-)....
 270  */
 271 #define dir 0
 272 #define DELETE_HELPER(_d1, _d2)                                              \
 273     FIND_HELPER(_d1, _d2, n, pal, al);                                       \
 274     FIND_HELPER(_d2, _d1, n, par, ar);                                       \
 275     if ( IS_THREAD(n ## _d2) )                                               \
 276     {                                                                        \
 277         if ( IS_THREAD(n ## _d1) )                                           \
 278         {                                                                    \
 279             r = mcas(4,                                                      \
 280                      (void **)&n->v, v,  NULL,                               \
 281                      (void **)&n->l, nl, GARBAGE(nl),                        \
 282                      (void **)&n->r, nr, GARBAGE(nr),                        \
 283                      (void **)p_pc,  n,  n ## _d1);                          \
 284         }                                                                    \
 285         else                                                                 \
 286         {                                                                    \
 287             if ( al == n ) goto retry;                                       \
 288             r = mcas(5,                                                      \
 289                      (void **)&n->v, v,  NULL,                               \
 290                      (void **)&n->l, nl, GARBAGE(nl),                        \
 291                      (void **)&n->r, nr, GARBAGE(nr),                        \
 292                      (void **)p_pc,  n,  n ## _d1,                           \
 293                      (void **)&al->_d2, THREAD(n), n ## _d2);                \
 294         }                                                                    \
 295     }                                                                        \
 296     else if ( IS_THREAD(n ## _d1) )                                          \
 297     {                                                                        \
 298         if ( ar == n ) goto retry;                                           \
 299         r = mcas(5,                                                          \
 300                  (void **)&n->v, v,  NULL,                                   \
 301                  (void **)&n->l, nl, GARBAGE(nl),                            \
 302                  (void **)&n->r, nr, GARBAGE(nr),                            \
 303                  (void **)p_pc,  n,  n ## _d2,                               \
 304                  (void **)&ar->_d1, THREAD(n), n ## _d1);                    \
 305     }                                                                        \
 306     else if ( dir )                                                          \
 307     {                                                                        \
 308         if ( (al == n) || (ar == n) ) goto retry;                            \
 309         if ( par == n )                                                      \
 310         {                                                                    \
 311             r = mcas(6,                                                      \
 312                      (void **)&n->v, v,  NULL,                               \
 313                      (void **)&ar->_d1, THREAD(n), n ## _d1,                 \
 314                      (void **)&al->_d2, THREAD(n), THREAD(ar),               \
 315                      (void **)&n->l,    nl, GARBAGE(nl),                     \
 316                      (void **)&n->r,    nr, GARBAGE(nr),                     \
 317                      (void **)p_pc,     n,  ar);                             \
 318         }                                                                    \
 319         else                                                                 \
 320         {                                                                    \
 321             STRONG_READ_LINK(ac, ar->_d2);                                   \
 322             r = mcas(8,                                                      \
 323                      (void **)&n->v, v,  NULL,                               \
 324                      (void **)&par->_d1, ar,                                 \
 325                                          (IS_THREAD(ac) ? THREAD(ar) : ac),  \
 326                      (void **)&ar->_d2, ac, n ## _d2,                        \
 327                      (void **)&ar->_d1, THREAD(n), n ## _d1,                 \
 328                      (void **)&al->_d2, THREAD(n), THREAD(ar),               \
 329                      (void **)&n->l,    nl, GARBAGE(nl),                     \
 330                      (void **)&n->r,    nr, GARBAGE(nr),                     \
 331                      (void **)p_pc,     n,  ar);                             \
 332         }                                                                    \
 333     }                                                                        \
 334     else                                                                     \
 335     {                                                                        \
 336         if ( (al == n) || (ar == n) ) goto retry;                            \
 337         if ( pal == n )                                                      \
 338         {                                                                    \
 339             r = mcas(6,                                                      \
 340                      (void **)&n->v, v,  NULL,                               \
 341                      (void **)&al->_d2, THREAD(n), n ## _d2,                 \
 342                      (void **)&ar->_d1, THREAD(n), THREAD(al),               \
 343                      (void **)&n->l,    nl, GARBAGE(nl),                     \
 344                      (void **)&n->r,    nr, GARBAGE(nr),                     \
 345                      (void **)p_pc,     n,  al);                             \
 346         }                                                                    \
 347         else                                                                 \
 348         {                                                                    \
 349             STRONG_READ_LINK(ac, al->_d1);                                   \
 350             r = mcas(8,                                                      \
 351                      (void **)&n->v, v,  NULL,                               \
 352                      (void **)&pal->_d2, al,                                 \
 353                                          (IS_THREAD(ac) ? THREAD(al) : ac),  \
 354                      (void **)&al->_d1, ac, n ## _d1,                        \
 355                      (void **)&al->_d2, THREAD(n), n ## _d2,                 \
 356                      (void **)&ar->_d1, THREAD(n), THREAD(al),               \
 357                      (void **)&n->l,    nl, GARBAGE(nl),                     \
 358                      (void **)&n->r,    nr, GARBAGE(nr),                     \
 359                      (void **)p_pc,     n,  al);                             \
 360         }                                                                    \
 361     }
 362
 363
 364 /* @k: key of node to be deleted */
 365 setval_t set_remove(set_t *s, setkey_t k)
 366 {
 367     node_t *p, *n, *nl, *nr, *al, *ar, *pal, *par, *ac, **p_pc;
 368     int r = 0;
 369     setval_t v;
 370     ptst_t *ptst;
 371
 372     k = CALLER_TO_INTERNAL_KEY(k);
 373
 374     ptst = critical_enter();
 375
 376     do
 377     {
 378     retry:
 379         v = NULL;
 380
 381         /* Node present? */
 382         n = search(s, k, &p);
 383         if ( IS_THREAD(n) ) goto out;
 384
 385         /* Already deleted? */
 386         v = n->v;
 387         PROCESS_VAL(v, &n->v);
 388         if ( v == NULL ) goto out;
 389
 390         STRONG_READ_LINK(nl, n->l);
 391         STRONG_READ_LINK(nr, n->r);
 392         p_pc = (p->k > n->k) ? &p->l : &p->r;
 393
 394         if ( p->k > n->k )
 395         {
 396             /* @n is leftwards link from @p. */
 397             DELETE_HELPER(l, r);
 398         }
 399         else
 400         {
 401             /* @n is rightwards link from @p. */
 402             DELETE_HELPER(r, l);
 403         }
 404     } while ( !r );
 405
 406     gc_free(ptst, n, gc_id);
 407
 408  out:
 409     critical_exit(ptst);
 410     return v;
 411 }
 412
 413
 414 setval_t set_lookup(set_t *s, setkey_t k)
 415 {
 416     node_t *n;
 417     setval_t v;
 418     ptst_t *ptst;
 419
 420     k = CALLER_TO_INTERNAL_KEY(k);
 421
 422     ptst = critical_enter();
 423
 424     n = search(s, k, NULL);
 425     v = (!IS_THREAD(n)) ? n->v : NULL;
 426     PROCESS_VAL(v, &n->v);
 427
 428     critical_exit(ptst);
 429     return v;
 430 }
 431
 432
 433 void _init_set_subsystem(void)
 434 {
 435     gc_id = gc_add_allocator(sizeof(node_t));
 436 }