src/mcas/bst_lock_manber.c

   1 /******************************************************************************
   2  * bst_lock_manber.c
   3  *
   4  * Lock-based binary search trees (BSTs), based on:
   5  *  Udi Manber and Richard E. Ladner.
   6  *  "Concurrency control in a dynamic search structure".
   7  *  ACM Transactions on Database Systems, Vol. 9, No. 3, September 1984.
   8  *
   9  * Copyright (c) 2002-2003, K A Fraser
  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 #define __SET_IMPLEMENTATION__
  38
  39 #include <ucontext.h>
  40 #include <signal.h>
  41 #include <stdio.h>
  42 #include <limits.h>
  43 #include <errno.h>
  44 #include <stdlib.h>
  45 #include <assert.h>
  46 #include <sys/types.h>
  47 #include <sys/stat.h>
  48 #include <fcntl.h>
  49 #include <unistd.h>
  50 #include <stdarg.h>
  51 #include "portable_defns.h"
  52 #include "gc.h"
  53 #include "set.h"
  54
  55 #define GARBAGE_FLAG   1
  56 #define REDUNDANT_FLAG 2
  57
  58 #define IS_GARBAGE(_n)   ((int)(_n)->v & GARBAGE_FLAG)
  59 #define MK_GARBAGE(_n)   \
  60     ((_n)->v = (setval_t)((unsigned long)(_n)->v | GARBAGE_FLAG))
  61
  62 #define IS_REDUNDANT(_n) ((int)(_n)->v & REDUNDANT_FLAG)
  63 #define MK_REDUNDANT(_n) \
  64     ((_n)->v = (setval_t)((unsigned long)(_n)->v | REDUNDANT_FLAG))
  65
  66 #define GET_VALUE(_n) ((setval_t)((unsigned long)(_n)->v & ~3UL))
  67
  68 #define FOLLOW(_n, _k) (((_n)->k < (_k)) ? (_n)->r : (_n)->l)
  69
  70 typedef struct node_st node_t;
  71 typedef struct set_st set_t;
  72
  73 struct node_st
  74 {
  75     setkey_t k;
  76     setval_t v;
  77     node_t *l, *r, *p;
  78     int copy;
  79     mcs_lock_t lock;
  80 };
  81
  82 struct set_st
  83 {
  84     node_t root;
  85 };
  86
  87 static int gc_id, hook_id;
  88
  89 #define LOCK(_n, _pqn)   mcs_lock(&(_n)->lock, (_pqn))
  90 #define UNLOCK(_n, _pqn) mcs_unlock(&(_n)->lock, (_pqn))
  91
  92
  93 static node_t *weak_search(node_t *n, setkey_t k)
  94 {
  95     while ( (n != NULL) && (n->k != k) ) n = FOLLOW(n, k);
  96     return n;
  97 }
  98
  99
 100 static node_t *strong_search(node_t *n, setkey_t k, qnode_t *qn)
 101 {
 102     node_t *b = n;
 103     node_t *a = FOLLOW(b, k);
 104
 105  retry:
 106     while ( (a != NULL) && (a->k != k) )
 107     {
 108         b = a;
 109         a = FOLLOW(a, k);
 110     }
 111
 112     if ( a == NULL )
 113     {
 114         LOCK(b, qn);
 115         if ( IS_GARBAGE(b) )
 116         {
 117             UNLOCK(b, qn);
 118             a = b->p;
 119             goto retry;
 120         }
 121         else if ( (a = FOLLOW(b, k)) != NULL )
 122         {
 123             UNLOCK(b, qn);
 124             goto retry;
 125         }
 126
 127         a = b;
 128     }
 129     else
 130     {
 131         LOCK(a, qn);
 132         if ( IS_GARBAGE(a) )
 133         {
 134             UNLOCK(a, qn);
 135             a = a->p;
 136             goto retry;
 137         }
 138         else if ( IS_REDUNDANT(a) )
 139         {
 140             UNLOCK(a, qn);
 141             a = a->r;
 142             goto retry;
 143         }
 144     }
 145
 146     return a;
 147 }
 148
 149
 150 static void redundancy_removal(ptst_t *ptst, void *x)
 151 {
 152     node_t *d, *e, *r;
 153     qnode_t d_qn, e_qn;
 154     setkey_t k;
 155
 156     if ( x == NULL ) return;
 157
 158     e = x;
 159     k = e->k;
 160
 161     if ( e->copy )
 162     {
 163         r = weak_search(e->l, k);
 164         assert((r == NULL) || !IS_REDUNDANT(r) || (r->r == e));
 165         assert(r != e);
 166         redundancy_removal(ptst, r);
 167     }
 168
 169     do {
 170         if ( IS_GARBAGE(e) ) return;
 171         d = e->p;
 172         LOCK(d, &d_qn);
 173         if ( IS_GARBAGE(d) ) UNLOCK(d, &d_qn);
 174     }
 175     while ( IS_GARBAGE(d) );
 176
 177     LOCK(e, &e_qn);
 178
 179     if ( IS_GARBAGE(e) || !IS_REDUNDANT(e) ) goto out_de;
 180
 181     if ( d->l == e )
 182     {
 183         d->l = e->l;
 184     }
 185     else
 186     {
 187         assert(d->r == e);
 188         d->r = e->l;
 189     }
 190
 191     assert(e->r != NULL);
 192     assert(e->r->k == k);
 193     assert(e->r->copy);
 194     assert(!IS_GARBAGE(e->r));
 195     assert(!e->copy);
 196
 197     MK_GARBAGE(e);
 198
 199     if ( e->l != NULL ) e->l->p = d;
 200
 201     e->r->copy = 0;
 202
 203     gc_free(ptst, e, gc_id);
 204
 205  out_de:
 206     UNLOCK(d, &d_qn);
 207     UNLOCK(e, &e_qn);
 208 }
 209
 210
 211 /* NB. Node X is not locked on entry. */
 212 static void predecessor_substitution(ptst_t *ptst, set_t *s, node_t *x)
 213 {
 214     node_t *a, *b, *e, *f, **pac;
 215     qnode_t a_qn, b_qn, e_qn, f_qn;
 216     setkey_t k;
 217
 218     b = x;
 219     k = x->k;
 220
 221     do {
 222         if ( (b == NULL) || (b->v != NULL) ) return;
 223         a = b->p;
 224         LOCK(a, &a_qn);
 225         if ( IS_GARBAGE(a) ) UNLOCK(a, &a_qn);
 226     }
 227     while ( IS_GARBAGE(a) );
 228
 229  regain_lock:
 230     LOCK(b, &b_qn);
 231
 232     /*
 233      * We do nothing if:
 234      *  1. The node is already deleted (and is thus garbage); or
 235      *  2. The node is redundant (redundancy removal will do it); or
 236      *  3. The node has been reused.
 237      * These can all be checked by looking at the value field.
 238      */
 239     if ( b->v != NULL ) goto out_ab;
 240
 241     /*
 242      * If this node is a copy, then we can do redundancy removal right now.
 243      * This is an improvement over Manber and Ladner's work.
 244      */
 245     if ( b->copy )
 246     {
 247         e = weak_search(b->l, k);
 248         UNLOCK(b, &b_qn);
 249         assert((e == NULL) || !IS_REDUNDANT(e) || (e->r == b));
 250         assert(e != b);
 251         redundancy_removal(ptst, e);
 252         goto regain_lock;
 253     }
 254
 255     pac = (a->k < k) ? &a->r : &a->l;
 256     assert(*pac == b);
 257     assert(b->p == a);
 258
 259     if ( (b->l == NULL) || (b->r == NULL) )
 260     {
 261         if ( b->r == NULL ) *pac = b->l; else *pac = b->r;
 262         MK_GARBAGE(b);
 263         if ( *pac != NULL ) (*pac)->p = a;
 264         gc_free(ptst, b, gc_id);
 265         goto out_ab;
 266     }
 267     else
 268     {
 269         e = strong_search(b->l, b->k, &e_qn);
 270         assert(!IS_REDUNDANT(e) && !IS_GARBAGE(e) && (b != e));
 271         assert(e->k < b->k);
 272         f = gc_alloc(ptst, gc_id);
 273         f->k = e->k;
 274         f->v = GET_VALUE(e);
 275         f->copy = 1;
 276         f->r = b->r;
 277         f->l = b->l;
 278         mcs_init(&f->lock);
 279         LOCK(f, &f_qn);
 280
 281         e->r = f;
 282         MK_REDUNDANT(e);
 283         *pac = f;
 284         f->p = a;
 285         f->r->p = f;
 286         f->l->p = f;
 287
 288         MK_GARBAGE(b);
 289         gc_free(ptst, b, gc_id);
 290         gc_add_ptr_to_hook_list(ptst, e, hook_id);
 291         UNLOCK(e, &e_qn);
 292         UNLOCK(f, &f_qn);
 293     }
 294
 295  out_ab:
 296     UNLOCK(a, &a_qn);
 297     UNLOCK(b, &b_qn);
 298 }
 299
 300
 301 set_t *set_alloc(void)
 302 {
 303     set_t *s;
 304
 305     s = malloc(sizeof(*s));
 306     mcs_init(&s->root.lock);
 307     s->root.k = SENTINEL_KEYMIN;
 308     /* Dummy root isn't redundant, nor is it garbage. */
 309     s->root.v = (setval_t)(~3UL);
 310     s->root.l = NULL;
 311     s->root.r = NULL;
 312     s->root.p = NULL;
 313     s->root.copy = 0;
 314
 315     return s;
 316 }
 317
 318
 319 setval_t set_update(set_t *s, setkey_t k, setval_t v, int overwrite)
 320 {
 321     node_t  *a, *new;
 322     qnode_t  qn;
 323     setval_t ov = NULL;
 324     ptst_t  *ptst;
 325
 326     k = CALLER_TO_INTERNAL_KEY(k);
 327
 328     ptst = critical_enter();
 329
 330     a = strong_search(&s->root, k, &qn);
 331     if ( a->k != k )
 332     {
 333         new = gc_alloc(ptst, gc_id);
 334         mcs_init(&new->lock);
 335         new->k = k;
 336         new->v = v;
 337         new->l = NULL;
 338         new->r = NULL;
 339         new->p = a;
 340         new->copy = 0;
 341         if ( a->k < k ) a->r = new; else a->l = new;
 342     }
 343     else
 344     {
 345         /* Direct A->V access is okay, as A isn't garbage or redundant. */
 346         ov = a->v;
 347         if ( overwrite || (ov == NULL) ) a->v = v;
 348     }
 349
 350     UNLOCK(a, &qn);
 351
 352     critical_exit(ptst);
 353
 354     return ov;
 355 }
 356
 357
 358 setval_t set_remove(set_t *s, setkey_t k)
 359 {
 360     node_t *a;
 361     qnode_t qn;
 362     setval_t v = NULL;
 363     ptst_t *ptst;
 364
 365     k = CALLER_TO_INTERNAL_KEY(k);
 366
 367     ptst = critical_enter();
 368
 369     a = strong_search(&s->root, k, &qn);
 370     /* Direct check of A->V is okay, as A isn't garbage or redundant. */
 371     if ( (a->k == k) && (a->v != NULL) )
 372     {
 373         v = a->v;
 374         a->v = NULL;
 375         UNLOCK(a, &qn);
 376         predecessor_substitution(ptst, s, a);
 377     }
 378     else
 379     {
 380         UNLOCK(a, &qn);
 381     }
 382
 383     critical_exit(ptst);
 384
 385     return v;
 386 }
 387
 388
 389 setval_t set_lookup(set_t *s, setkey_t k)
 390 {
 391     node_t *n;
 392     setval_t v = NULL;
 393     ptst_t *ptst;
 394
 395     k = CALLER_TO_INTERNAL_KEY(k);
 396
 397     ptst = critical_enter();
 398
 399     n = weak_search(&s->root, k);
 400     if ( n != NULL ) v = GET_VALUE(n);
 401
 402     critical_exit(ptst);
 403     return v;
 404 }
 405
 406
 407 void _init_set_subsystem(void)
 408 {
 409     gc_id = gc_add_allocator(sizeof(node_t));
 410     hook_id = gc_add_hook(redundancy_removal);
 411 }