src/mcas/stm_lock.c

   1 /******************************************************************************
   2  * stm_lock.c
   3  *
   4  * Lock-based software transactional memory (STM).
   5  * Uses two-phase locking with multi-reader locks.
   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 #include "portable_defns.h"
  37 #include "ptst.h"
  38 #include "gc.h"
  39 #include <assert.h>
  40 #include <stdarg.h>
  41 #include <stdlib.h>
  42 #include <stdio.h>
  43 #include <string.h>
  44 #include <setjmp.h>
  45 #include <signal.h>
  46
  47 typedef struct stm_blk_st stm_blk;
  48 typedef struct stm_tx_entry_st stm_tx_entry;
  49 typedef struct stm_tx_st stm_tx;
  50 typedef struct stm_st stm;
  51
  52 struct stm_blk_st {
  53     void *data;
  54     mrsw_lock_t lock;
  55 };
  56
  57 struct stm_tx_entry_st {
  58     stm_blk *b;
  59     void    *old;
  60     void    *new;
  61     stm_tx_entry *next;
  62 };
  63
  64 struct stm_tx_st {
  65     int status;
  66     stm_tx_entry *blocks;
  67     stm_tx_entry *alloc_ptr, *check;
  68     int gc_data_id, blk_size; /* copied from 'stm' structure */
  69     sigjmp_buf *penv;
  70 };
  71
  72 struct stm_st {
  73     int gc_data_id;
  74     int blk_size;
  75 };
  76
  77 #define DESCRIPTOR_IN_USE(_t) ((_t)->penv != NULL)
  78
  79 #define DESCRIPTOR_SIZE  4096
  80 #define MAX_TX_ENTS      (DESCRIPTOR_SIZE / sizeof(stm_tx_entry))
  81
  82 /* Private per-thread state. The array is indexed off ptst->id. */
  83 typedef struct {
  84     char desc[DESCRIPTOR_SIZE];
  85 } priv_t;
  86
  87 static priv_t priv_ptst[MAX_THREADS];
  88 static int gc_blk_id;  /* Allocation id for block descriptors. */
  89 static int do_padding; /* Should all allocations be padded to a cache line? */
  90
  91 #define ALLOCATOR_SIZE(_s) (do_padding ? CACHE_LINE_SIZE : (_s))
  92
  93 #define TXS_IN_PROGRESS 0
  94 #define TXS_FAILED      1
  95 #define TXS_SUCCESSFUL  2
  96
  97 bool_t commit_stm_tx(ptst_t *ptst, stm_tx *t);
  98
  99 static stm_tx_entry *alloc_stm_tx_entry(stm_tx *t)
 100 {
 101     stm_tx_entry *ent = t->alloc_ptr++;
 102     assert(((unsigned long)t->alloc_ptr - (unsigned long)t) <=
 103            DESCRIPTOR_SIZE);
 104     return ent;
 105 }
 106
 107
 108 static stm_tx_entry **search_stm_tx_entry(stm_tx_entry **pnext, stm_blk *b)
 109 {
 110     stm_tx_entry *next = *pnext;
 111
 112     while ( (next != NULL) && ((unsigned long)next->b < (unsigned long)b) )
 113     {
 114         pnext = &next->next;
 115         next  = *pnext;
 116     }
 117
 118     return pnext;
 119 }
 120
 121
 122 stm *new_stm(ptst_t *ptst, int blk_size)
 123 {
 124     stm *mem = malloc(CACHE_LINE_SIZE);
 125     mem->blk_size = blk_size;
 126     mem->gc_data_id = gc_add_allocator(ALLOCATOR_SIZE(blk_size));
 127     return mem;
 128 }
 129
 130
 131 void free_stm(ptst_t *ptst, stm *mem)
 132 {
 133     gc_remove_allocator(mem->gc_data_id);
 134     free(mem);
 135 }
 136
 137
 138 stm_blk *new_stm_blk(ptst_t *ptst, stm *mem)
 139 {
 140     stm_blk *b;
 141     b       = gc_alloc(ptst, gc_blk_id);
 142     b->data = gc_alloc(ptst, mem->gc_data_id);
 143     mrsw_init(&b->lock);
 144     return b;
 145 }
 146
 147
 148 void free_stm_blk(ptst_t *ptst, stm *mem, stm_blk *b)
 149 {
 150     gc_free(ptst, b->data, mem->gc_data_id);
 151     gc_free(ptst, b,       gc_blk_id);
 152 }
 153
 154
 155 void *init_stm_blk(ptst_t *ptst, stm *mem, stm_blk *b)
 156 {
 157     return b->data;
 158 }
 159
 160
 161 int sizeof_stm_blk(ptst_t *ptst, stm *mem, stm_blk *b)
 162 {
 163     return mem->blk_size;
 164 }
 165
 166
 167 stm_tx *new_stm_tx(ptst_t *ptst, stm *mem, sigjmp_buf *penv)
 168 {
 169     stm_tx *t = (stm_tx *)&priv_ptst[ptst->id];
 170     if ( DESCRIPTOR_IN_USE(t) ) goto nesting;
 171     t->status = TXS_IN_PROGRESS;
 172     t->blocks = NULL;
 173     t->alloc_ptr = t->check = (stm_tx_entry *)(t + 1);
 174     t->gc_data_id = mem->gc_data_id;
 175     t->blk_size = mem->blk_size;
 176     t->penv = penv;
 177     return t;
 178
 179  nesting:
 180     fprintf(stderr, "No nesting of transactions is allowed\n");
 181     return NULL;
 182 }
 183
 184
 185 bool_t commit_stm_tx(ptst_t *ptst, stm_tx *t)
 186 {
 187     stm_tx_entry *ent, *last_ent;
 188     mrsw_qnode_t qn[MAX_TX_ENTS];
 189     stm_blk *b;
 190     void *old;
 191     int i;
 192
 193     t->penv = NULL;
 194
 195     /* Outcome may have been decided by an 'abort' or 'validate' operation. */
 196     if ( t->status != TXS_IN_PROGRESS ) goto out;
 197
 198     /* We start by taking locks in order, and checking old values. */
 199     for ( i = 0, ent = t->blocks; ent != NULL; i++, ent = ent->next )
 200     {
 201         b = ent->b;
 202         if ( (old = ent->old) == ent->new )
 203         {
 204             rd_lock(&b->lock, &qn[i]);
 205         }
 206         else
 207         {
 208             wr_lock(&b->lock, &qn[i]);
 209         }
 210         /* Check old value, and shortcut to failure if we mismatch. */
 211         if ( b->data != old ) goto fail;
 212     }
 213
 214     /*
 215      * LINEARISATION POINT FOR SUCCESS:
 216      * We haven't written new values yet, but that's okay as we have write
 217      * locks on those locations. Noone can see old value now and yet still
 218      * commit (as they'll be waiting for the read lock).
 219      */
 220     t->status = TXS_SUCCESSFUL;
 221
 222     /* We definitely succeed now: release locks and write new values. */
 223     for ( i = 0, ent = t->blocks; ent != NULL; i++, ent = ent->next )
 224     {
 225         b = ent->b;
 226         if ( ent->old == ent->new )
 227         {
 228             rd_unlock(&b->lock, &qn[i]);
 229         }
 230         else
 231         {
 232             b->data = ent->new;
 233             wr_unlock(&b->lock, &qn[i]);
 234         }
 235     }
 236
 237  out:
 238     if ( t->status == TXS_SUCCESSFUL )
 239     {
 240         for ( ent = t->blocks; ent != NULL; ent = ent->next )
 241         {
 242             if ( ent->old == ent->new ) continue;
 243             gc_free(ptst, ent->old, t->gc_data_id);
 244         }
 245         return TRUE;
 246     }
 247     else
 248     {
 249         for ( ent = t->blocks; ent != NULL; ent = ent->next )
 250         {
 251             if ( ent->old == ent->new ) continue;
 252             gc_unsafe_free(ptst, ent->new, t->gc_data_id);
 253         }
 254         return FALSE;
 255     }
 256
 257     /*
 258      * We put (hopefully rare) failure case out-of-line here.
 259      * This is also the LINEARISTAION POINT FOR FAILURE.
 260      */
 261  fail:
 262     last_ent = ent->next;
 263     t->status = TXS_FAILED;
 264     for ( i = 0, ent = t->blocks; ent != last_ent; i++, ent = ent->next )
 265     {
 266         b = ent->b;
 267         if ( ent->old == ent->new )
 268         {
 269             rd_unlock(&b->lock, &qn[i]);
 270         }
 271         else
 272         {
 273             wr_unlock(&b->lock, &qn[i]);
 274         }
 275     }
 276     goto out;
 277 }
 278
 279
 280 bool_t validate_stm_tx(ptst_t *ptst, stm_tx *t)
 281 {
 282     stm_tx_entry *ent, *last_ent = NULL;
 283     mrsw_qnode_t qn[MAX_TX_ENTS];
 284     stm_blk *b;
 285     void *old;
 286     int i;
 287
 288     RMB();
 289
 290     /* Lock-acquire phase */
 291     for ( i = 0, ent = t->blocks; ent != NULL; i++, ent = ent->next )
 292     {
 293         b = ent->b;
 294
 295         if ( (old = ent->old) == ent->new )
 296         {
 297             rd_lock(&b->lock, &qn[i]);
 298         }
 299         else
 300         {
 301             wr_lock(&b->lock, &qn[i]);
 302         }
 303
 304         if ( b->data != old )
 305         {
 306             t->status = TXS_FAILED;
 307             last_ent = ent->next;
 308             break;
 309         }
 310     }
 311
 312     /* Lock-release phase */
 313     for ( i = 0, ent = t->blocks; ent != last_ent; i++, ent = ent->next )
 314     {
 315         b = ent->b;
 316         if ( ent->old == ent->new )
 317         {
 318             rd_unlock(&b->lock, &qn[i]);
 319         }
 320         else
 321         {
 322             wr_unlock(&b->lock, &qn[i]);
 323         }
 324     }
 325
 326     return t->status != TXS_FAILED;
 327 }
 328
 329
 330 void abort_stm_tx(ptst_t *ptst, stm_tx *t)
 331 {
 332     t->status = TXS_FAILED;
 333 }
 334
 335
 336 void *read_stm_blk(ptst_t *ptst, stm_tx *t, stm_blk *b)
 337 {
 338     stm_tx_entry **pent, *ent;
 339     sigjmp_buf *penv;
 340     void *result;
 341
 342     pent = search_stm_tx_entry(&t->blocks, b);
 343     ent  = *pent;
 344     if ( (ent != NULL) && (ent->b == b) ) goto found;
 345
 346     ent = alloc_stm_tx_entry(t);
 347     ent->b    = b;
 348     ent->old  = b->data;
 349     ent->new  = ent->old;
 350     ent->next = *pent;
 351     *pent = ent;
 352     return ent->new;
 353
 354  found:
 355     result = ent->new;
 356     ent = t->check;
 357     if ( ent->b->data != ent->old ) goto fail;
 358     if ( ++t->check == t->alloc_ptr ) t->check = (stm_tx_entry *)(t + 1);
 359     return result;
 360
 361  fail:
 362     penv = t->penv;
 363     abort_stm_tx(ptst, t);
 364     commit_stm_tx(ptst, t);
 365     siglongjmp(*penv, 0);
 366     assert(0);
 367     return NULL;
 368 }
 369
 370
 371 void *write_stm_blk(ptst_t *ptst, stm_tx *t, stm_blk *b)
 372 {
 373     stm_tx_entry **pent, *ent;
 374     sigjmp_buf *penv;
 375     void *result;
 376
 377     pent = search_stm_tx_entry(&t->blocks, b);
 378     ent = *pent;
 379     if ( (ent != NULL) && (ent->b == b) )
 380     {
 381         if ( ent->old != ent->new ) goto found;
 382     }
 383     else
 384     {
 385         ent = alloc_stm_tx_entry(t);
 386         ent->b    = b;
 387         ent->old  = b->data;
 388         ent->next = *pent;
 389         *pent = ent;
 390     }
 391
 392     ent->new  = gc_alloc(ptst, t->gc_data_id);
 393     memcpy(ent->new, ent->old, t->blk_size);
 394     return ent->new;
 395
 396  found:
 397     result = ent->new;
 398     ent = t->check;
 399     if ( ent->b->data != ent->old ) goto fail;
 400     if ( ++t->check == t->alloc_ptr ) t->check = (stm_tx_entry *)(t + 1);
 401     return result;
 402
 403  fail:
 404     penv = t->penv;
 405     abort_stm_tx(ptst, t);
 406     commit_stm_tx(ptst, t);
 407     siglongjmp(*penv, 0);
 408     assert(0);
 409     return NULL;
 410 }
 411
 412
 413 void remove_from_tx(ptst_t *ptst, stm_tx *t, stm_blk *b)
 414 {
 415     stm_tx_entry **pent, *ent;
 416     void *data;
 417
 418     pent = search_stm_tx_entry(&t->blocks, b);
 419     ent  = *pent;
 420     if ( (ent != NULL) && (ent->b == b) )
 421     {
 422         *pent = ent->next;
 423         if ( (data = ent->new) != ent->old )
 424         {
 425             gc_free(ptst, data, t->gc_data_id);
 426         }
 427     }
 428 }
 429
 430
 431 static void handle_fault(int sig)
 432 {
 433     ptst_t *ptst;
 434     stm_tx *t;
 435
 436     ptst = critical_enter();
 437     t = (stm_tx *)&priv_ptst[ptst->id];
 438     if ( DESCRIPTOR_IN_USE(t) && !validate_stm_tx(ptst, t) )
 439     {
 440         sigjmp_buf *penv = t->penv;
 441         commit_stm_tx(ptst, t);
 442         critical_exit(ptst);
 443         siglongjmp(*penv, 0);
 444     }
 445
 446  fail:
 447     fprintf(stderr, "Error: unhandleable SIGSEGV!\n");
 448     abort();
 449 }
 450
 451
 452 void _init_stm_subsystem(int pad_data)
 453 {
 454     struct sigaction act;
 455
 456     do_padding = pad_data;
 457     gc_blk_id = gc_add_allocator(ALLOCATOR_SIZE(sizeof(stm_blk)));
 458     memset(priv_ptst, 0, sizeof(priv_ptst));
 459
 460     act.sa_handler = handle_fault;
 461     sigemptyset(&act.sa_mask);
 462     act.sa_flags = 0;
 463     sigaction(SIGSEGV, &act, NULL);
 464 }