src/mcas/bst_lock_kung.c

   1 /******************************************************************************
   2  * bst_lock_kung.c
   3  *
   4  * Lock-based binary search trees (BSTs), based on:
   5  *  H. T. Kung and Philip L. Lehman.
   6  *  "Concurrent manipulation of binary search trees".
   7  *  ACM Tranactions on Database Systems, Vol. 5, No. 3, September 1980.
   8  *
   9  * Copyright (c) 2002-2003, K A Fraser
  10
  11 Redistribution and use in source and binary forms, with or without
  12 modification, are permitted provided that the following conditions are
  13 met:
  14
  15     * Redistributions of source code must retain the above copyright
  16     * notice, this list of conditions and the following disclaimer.
  17     * Redistributions in binary form must reproduce the above
  18     * copyright notice, this list of conditions and the following
  19     * disclaimer in the documentation and/or other materials provided
  20     * with the distribution.  Neither the name of the Keir Fraser
  21     * nor the names of its contributors may be used to endorse or
  22     * promote products derived from this software without specific
  23     * prior written permission.
  24
  25 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  26 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  27 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
  28 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
  29 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  30 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
  31 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  32 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  33 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  34 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  35 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  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 IS_BLUE(_n)      ((int)(_n)->v & 1)
  57 #define MK_BLUE(_n)      ((_n)->v = (setval_t)((unsigned long)(_n)->v | 1))
  58
  59 #define GET_VALUE(_n) ((setval_t)((unsigned long)(_n)->v & ~1UL))
  60
  61 #define LEFT  0
  62 #define RIGHT 1
  63 #define FOLLOW(_n, _d) ((_d) ? (_n)->r : (_n)->l)
  64 #define UPDATE(_n, _d, _x) ((_d) ? ((_n)->r = (_x)) : ((_n)->l = (_x)))
  65 #define FLIP(_d) ((_d)^1)
  66
  67 typedef struct node_st node_t;
  68 typedef struct set_st set_t;
  69
  70 struct node_st
  71 {
  72     setkey_t k;
  73     setval_t v;
  74     node_t *l, *r, *p;
  75     mcs_lock_t lock;
  76 };
  77
  78 struct set_st
  79 {
  80     node_t root;
  81 };
  82
  83 static int gc_id;
  84
  85 #define LOCK(_n, _pqn)   mcs_lock(&(_n)->lock, (_pqn))
  86 #define UNLOCK(_n, _pqn) mcs_unlock(&(_n)->lock, (_pqn))
  87
  88
  89 static node_t *weak_find(node_t *n, setkey_t k)
  90 {
  91     while ( n != NULL )
  92     {
  93         if ( n->k < k )
  94             n = n->r;
  95         else if ( n->k > k )
  96             n = n->l;
  97         else
  98             break;
  99     }
 100     return n;
 101 }
 102
 103
 104 static node_t *find(node_t *n, setkey_t k, qnode_t *qn, int *pdir)
 105 {
 106     int dir;
 107     node_t *f, *s;
 108
 109     s = n;
 110
 111     do {
 112         f = s;
 113     retry:
 114         if ( k < f->k )
 115         {
 116             dir = LEFT;
 117             s   = f->l;
 118         }
 119         else
 120         {
 121             dir = RIGHT;
 122             s   = f->r;
 123         }
 124     }
 125     while ( (s != NULL) && (s->k != k) );
 126
 127     LOCK(f, qn);
 128     if ( IS_BLUE(f) )
 129     {
 130         UNLOCK(f, qn);
 131         f = f->p;
 132         goto retry;
 133     }
 134     if ( s != FOLLOW(f, dir) )
 135     {
 136         UNLOCK(f, qn);
 137         goto retry;
 138     }
 139
 140     *pdir = dir;
 141     return f;
 142 }
 143
 144
 145 static node_t *rotate(ptst_t *ptst, node_t *a, int dir1,
 146                       int dir2, node_t **pc, qnode_t *pqn[])
 147 {
 148     node_t *b = FOLLOW(a, dir1), *c = FOLLOW(b, dir2);
 149     node_t *bp = gc_alloc(ptst, gc_id), *cp = gc_alloc(ptst, gc_id);
 150     qnode_t c_qn;
 151
 152     LOCK(c, &c_qn);
 153
 154     memcpy(bp, b, sizeof(*b));
 155     memcpy(cp, c, sizeof(*c));
 156
 157     mcs_init(&bp->lock);
 158     mcs_init(&cp->lock);
 159
 160     LOCK(bp, pqn[3]);
 161     LOCK(cp, pqn[2]);
 162
 163     assert(!IS_BLUE(a));
 164     assert(!IS_BLUE(b));
 165     assert(!IS_BLUE(c));
 166
 167     UPDATE(cp, FLIP(dir2), bp);
 168     UPDATE(bp, dir2,       FOLLOW(c, FLIP(dir2)));
 169
 170     UPDATE(a, dir1, cp);
 171     b->p = a;
 172     MK_BLUE(b);
 173     c->p = cp;
 174     MK_BLUE(c);
 175
 176     gc_free(ptst, b, gc_id);
 177     gc_free(ptst, c, gc_id);
 178
 179     UNLOCK(a, pqn[0]);
 180     UNLOCK(b, pqn[1]);
 181     UNLOCK(c, &c_qn);
 182
 183     *pc = bp;
 184     return cp;
 185 }
 186
 187
 188 static void _remove(ptst_t *ptst, node_t *a, int dir1, int dir2, qnode_t **pqn)
 189 {
 190     node_t *b = FOLLOW(a, dir1), *c = FOLLOW(b, dir2);
 191     assert(FOLLOW(b, FLIP(dir2)) == NULL);
 192     assert(!IS_BLUE(a));
 193     assert(!IS_BLUE(b));
 194     UPDATE(a, dir1,       c);
 195     UPDATE(b, FLIP(dir2), c);
 196     b->p = a;
 197     MK_BLUE(b);
 198     gc_free(ptst, b, gc_id);
 199     UNLOCK(a, pqn[0]);
 200     UNLOCK(b, pqn[1]);
 201 }
 202
 203
 204 static void delete_by_rotation(ptst_t *ptst, node_t *f, int dir,
 205                                qnode_t *pqn[], int lock_idx)
 206 {
 207     node_t *g, *h, *s = FOLLOW(f, dir);
 208
 209     if ( s->v != NULL )
 210     {
 211         UNLOCK(f, pqn[lock_idx+0]);
 212         UNLOCK(s, pqn[lock_idx+1]);
 213         return;
 214     }
 215
 216     if ( s->l == NULL )
 217         _remove(ptst, f, dir, RIGHT, pqn+lock_idx);
 218     else if ( s->r == NULL )
 219         _remove(ptst, f, dir, LEFT, pqn+lock_idx);
 220     else
 221     {
 222         g = rotate(ptst, f, dir, LEFT, &h, pqn+lock_idx);
 223         lock_idx ^= 2;
 224         if ( h->l == NULL )
 225         {
 226             assert(h->v == NULL);
 227             _remove(ptst, g, RIGHT, RIGHT, pqn+lock_idx);
 228         }
 229         else
 230         {
 231             delete_by_rotation(ptst, g, RIGHT, pqn, lock_idx);
 232             LOCK(f, pqn[0]);
 233             if ( (g != FOLLOW(f, dir)) || IS_BLUE(f) )
 234             {
 235                 UNLOCK(f, pqn[0]);
 236             }
 237             else
 238             {
 239                 LOCK(g, pqn[1]);
 240                 /*
 241                  * XXX Check that there is a node H to be rotated up.
 242                  * This is missing from the original paper, and must surely
 243                  * be a bug (we lost all locks at previous delete_by_rotation,
 244                  * so we can't know the existence of G's children).
 245                  */
 246                 if ( g->r != NULL )
 247                 {
 248                     g = rotate(ptst, f, dir, RIGHT, &h, pqn);
 249                     UNLOCK(g, pqn[2]);
 250                     UNLOCK(h, pqn[3]);
 251                 }
 252                 else
 253                 {
 254                     UNLOCK(f, pqn[0]);
 255                     UNLOCK(g, pqn[1]);
 256                 }
 257             }
 258         }
 259     }
 260 }
 261
 262
 263 set_t *set_alloc(void)
 264 {
 265     set_t *s;
 266
 267     s = malloc(sizeof(*s));
 268     mcs_init(&s->root.lock);
 269     s->root.k = SENTINEL_KEYMIN;
 270     s->root.v = (setval_t)(~1UL); /* dummy root node is white. */
 271     s->root.l = NULL;
 272     s->root.r = NULL;
 273
 274     return s;
 275 }
 276
 277
 278 setval_t set_update(set_t *s, setkey_t k, setval_t v, int overwrite)
 279 {
 280     node_t  *f, *w;
 281     qnode_t  f_qn, w_qn;
 282     int dir;
 283     setval_t ov = NULL;
 284     ptst_t  *ptst;
 285
 286     k = CALLER_TO_INTERNAL_KEY(k);
 287
 288     ptst = critical_enter();
 289
 290  retry:
 291     f = find(&s->root, k, &f_qn, &dir);
 292
 293     if ( (w = FOLLOW(f, dir)) != NULL )
 294     {
 295         /* Protected by parent lock. */
 296         assert(!IS_BLUE(w));
 297         ov = w->v;
 298         if ( overwrite || (ov == NULL) ) w->v = v;
 299     }
 300     else
 301     {
 302         w = gc_alloc(ptst, gc_id);
 303         w->l = NULL;
 304         w->r = NULL;
 305         w->v = v;
 306         w->k = k;
 307         mcs_init(&w->lock);
 308         UPDATE(f, dir, w);
 309     }
 310
 311     UNLOCK(f, &f_qn);
 312
 313     critical_exit(ptst);
 314
 315     return ov;
 316 }
 317
 318
 319 setval_t set_remove(set_t *s, setkey_t k)
 320 {
 321     node_t *f, *w;
 322     qnode_t qn[4], *pqn[] = { qn+0, qn+1, qn+2, qn+3, qn+0, qn+1 };
 323     int dir;
 324     setval_t v = NULL;
 325     ptst_t *ptst;
 326
 327     k = CALLER_TO_INTERNAL_KEY(k);
 328
 329     ptst = critical_enter();
 330
 331     f = find(&s->root, k, pqn[0], &dir);
 332     if ( (w = FOLLOW(f, dir)) != NULL )
 333     {
 334         LOCK(w, pqn[1]);
 335         v = w->v;
 336         w->v = NULL;
 337         assert(!IS_BLUE(w));
 338         delete_by_rotation(ptst, f, dir, pqn, 0);
 339     }
 340     else
 341     {
 342         UNLOCK(f, pqn[0]);
 343     }
 344
 345     critical_exit(ptst);
 346
 347     return v;
 348 }
 349
 350
 351 setval_t set_lookup(set_t *s, setkey_t k)
 352 {
 353     node_t *n;
 354     setval_t v = NULL;
 355     ptst_t *ptst;
 356
 357     k = CALLER_TO_INTERNAL_KEY(k);
 358
 359     ptst = critical_enter();
 360
 361     n = weak_find(&s->root, k);
 362     if ( n != NULL ) v = GET_VALUE(n);
 363
 364     critical_exit(ptst);
 365     return v;
 366 }
 367
 368
 369 void _init_set_subsystem(void)
 370 {
 371     gc_id = gc_add_allocator(sizeof(node_t));
 372 }