src/mcas/stm_herlihy.c

   1 /******************************************************************************
   2  * stm_herlihy.c
   3  *
   4  * Obstruction-free software transactional memory (STM).
   5  *
   6  * For more information see:
   7  *  Software Transactional Memory for Dynamic-sized Data Structures
   8  *  Maurice Herlihy, Victor Luchangco, Mark Moir, and William Scherer III
   9  *  Proceedings of 2003 ACM Symposium on Principles of Distributed Computing
  10  *
  11  * Copyright (c) 2003, K A Fraser
  12
  13 Redistribution and use in source and binary forms, with or without
  14 modification, are permitted provided that the following conditions are
  15 met:
  16
  17     * Redistributions of source code must retain the above copyright
  18     * notice, this list of conditions and the following disclaimer.
  19     * Redistributions in binary form must reproduce the above
  20     * copyright notice, this list of conditions and the following
  21     * disclaimer in the documentation and/or other materials provided
  22     * with the distribution.  Neither the name of the Keir Fraser
  23     * nor the names of its contributors may be used to endorse or
  24     * promote products derived from this software without specific
  25     * prior written permission.
  26
  27 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  28 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  29 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
  30 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
  31 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  32 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
  33 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  34 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  35 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  36 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  37 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  38  */
  39
  40 #include "portable_defns.h"
  41 #include "ptst.h"
  42 #include "gc.h"
  43 #include <assert.h>
  44 #include <stdarg.h>
  45 #include <stdlib.h>
  46 #include <stdio.h>
  47 #include <string.h>
  48 #include <setjmp.h>
  49 #include <signal.h>
  50 #include <unistd.h>
  51 #ifdef SPARC
  52 #include <time.h>
  53 #include <errno.h>
  54 #endif
  55
  56 #define POLITE
  57
  58 typedef struct stm_loc_st stm_loc;
  59 typedef struct stm_blk_st stm_blk;
  60 typedef struct stm_tx_entry_st stm_tx_entry;
  61 typedef struct stm_tx_st stm_tx;
  62 typedef struct stm_st stm;
  63
  64 struct stm_loc_st {
  65     unsigned long status; /* TXS_FAILED, TXS_SUCCESSFUL, descriptor. */
  66     void   *old;
  67     void   *new;
  68 };
  69
  70 struct stm_blk_st {
  71     stm_loc *loc;
  72 };
  73
  74 struct stm_tx_entry_st {
  75     stm_blk *b;
  76     stm_loc *l;
  77     void    *data;
  78     stm_tx_entry *next;
  79 };
  80
  81 struct stm_tx_st {
  82     unsigned int status;
  83     int rc;
  84     stm_tx *next_free;
  85     stm_tx_entry *reads;
  86     stm_tx_entry *writes;
  87     stm_tx_entry *alloc_ptr, *check;
  88     void *dummy;
  89     int gc_data_id, blk_size; /* copied from 'stm' structure */
  90     sigjmp_buf *penv;
  91 };
  92
  93 struct stm_st {
  94     int gc_data_id;
  95     int blk_size;
  96 };
  97
  98 /* Private per-thread state. The array is indexed off ptst->id. */
  99 typedef struct {
 100     void *arena, *arena_lim;
 101     stm_tx *next_descriptor;
 102     stm_tx *cur_tx;
 103 #ifdef SPARC
 104     unsigned int random_counter;
 105 #endif
 106     CACHE_PAD(0);
 107 } priv_t;
 108
 109 static priv_t priv_ptst[MAX_THREADS];
 110 static int gc_blk_id;  /* Allocation id for block descriptors. */
 111 static int gc_loc_id;  /* Allocation id for locators. */
 112 static int do_padding; /* Should all allocations be padded to a cache line? */
 113
 114 #ifdef POLITE
 115 #define MAX_RETRIES      8
 116 #ifdef SPARC
 117 #define MIN_LOG_BACKOFF  4
 118 #define MAX_LOG_BACKOFF 31
 119 #define RANDOM_BITS      8
 120 #define RANDOM_SIZE      (1 << RANDOM_BITS)
 121 #define RANDOM_MASK      (RANDOM_SIZE - 1)
 122 static unsigned int rand_arr[RANDOM_SIZE];
 123 #endif
 124 #endif
 125
 126 static stm_blk *dummy_obj; /* Dummy object (used by red-black trees). */
 127 static void *dummy_data;
 128
 129 #define ALLOCATOR_SIZE(_s) (do_padding ? CACHE_LINE_SIZE : (_s))
 130
 131 #define ARENA_SIZE      40960
 132 #define DESCRIPTOR_SIZE  4096
 133
 134 #define TXS_IN_PROGRESS 0U
 135 #define TXS_FAILED      1U
 136 #define TXS_SUCCESSFUL  2U
 137
 138 #define is_descriptor(_p) (((unsigned long)(_p) & 3) == 0)
 139 #define mk_descriptor(_p) ((stm_tx *)(_p))
 140
 141 /* Is transaction read-only? */
 142 #define read_only(_t)         ((_t)->writes == NULL)
 143
 144 /* Is transaction definitely doomed to fail? */
 145 #define is_stale(_t, _e) \
 146     (((_t)->status != TXS_IN_PROGRESS) || ((_e)->b->loc != (_e)->l))
 147
 148 bool_t commit_stm_tx(ptst_t *ptst, stm_tx *t);
 149
 150 static void new_arena (priv_t *priv, int size)
 151 {
 152     priv->arena = malloc(size);
 153     if ( priv->arena == NULL ) abort();
 154     priv->arena_lim = (((char *) priv->arena) + size);
 155 }
 156
 157 static void release_descriptor(ptst_t *ptst, stm_tx *t)
 158 {
 159     stm_tx_entry *ent;
 160     priv_t *priv = &priv_ptst[ptst->id];
 161     void *data;
 162
 163     t->next_free = priv->next_descriptor;
 164     priv->next_descriptor = t;
 165 }
 166
 167 static int rc_delta_descriptor(stm_tx *t, int delta)
 168 {
 169     int rc, new_rc = t->rc;
 170
 171     do { rc = new_rc; }
 172     while ( (new_rc = CASIO (&t->rc, rc, rc + delta)) != rc );
 173
 174     return rc;
 175 }
 176
 177 static void rc_up_descriptor(stm_tx *t)
 178 {
 179     rc_delta_descriptor(t, 2);
 180     MB();
 181 }
 182
 183 static void rc_down_descriptor(ptst_t *ptst, stm_tx *t)
 184 {
 185     int old_rc, new_rc, cur_rc = t->rc;
 186
 187     WMB();
 188
 189     do {
 190         old_rc = cur_rc;
 191         new_rc = old_rc - 2;
 192         if ( new_rc == 0 ) new_rc = 1;
 193     }
 194     while ( (cur_rc = CASIO (&t->rc, old_rc, new_rc)) != old_rc );
 195
 196     if ( old_rc == 2 ) release_descriptor(ptst, t);
 197 }
 198
 199 static stm_tx *new_descriptor(priv_t *priv)
 200 {
 201     stm_tx *t;
 202
 203     t = priv->next_descriptor;
 204
 205     if ( t != NULL )
 206     {
 207         priv->next_descriptor = t->next_free;
 208         /* 'Unfree' descriptor, if it was previously freed. */
 209         if ( (t->rc & 1) == 1 ) rc_delta_descriptor(t, 1);
 210     }
 211     else
 212     {
 213         t = (stm_tx *) priv->arena;
 214         priv->arena = ((char *) (priv->arena)) + DESCRIPTOR_SIZE;
 215
 216         if ( priv->arena >= priv->arena_lim )
 217         {
 218             new_arena(priv, ARENA_SIZE);
 219             t = (stm_tx *) priv->arena;
 220             priv->arena = ((char *) (priv->arena)) + DESCRIPTOR_SIZE;
 221         }
 222
 223         t->next_free = NULL;
 224         t->rc = 2;
 225     }
 226
 227     return t;
 228 }
 229
 230
 231 static stm_tx_entry *alloc_stm_tx_entry(stm_tx *t)
 232 {
 233     stm_tx_entry *ent = t->alloc_ptr++;
 234     assert(((unsigned long)t->alloc_ptr - (unsigned long)t) <=
 235            DESCRIPTOR_SIZE);
 236     return ent;
 237 }
 238
 239
 240 static stm_tx_entry **search_stm_tx_entry(stm_tx_entry **pnext, stm_blk *b)
 241 {
 242     stm_tx_entry *next = *pnext;
 243
 244     while ( (next != NULL) && ((unsigned long)next->b < (unsigned long)b) )
 245     {
 246         pnext = &next->next;
 247         next  = *pnext;
 248     }
 249
 250     return pnext;
 251 }
 252
 253
 254 static int contention_wait(ptst_t *ptst, int attempts)
 255 {
 256 #ifdef POLITE
 257     if ( (attempts > 1) && (attempts <= MAX_RETRIES) )
 258     {
 259 #ifdef SPARC /* Exactly as it was done by the original authors. */
 260         priv_t *priv = &priv_ptst[ptst->id];
 261         struct timespec rqtp;
 262         unsigned int log_backoff, mask;
 263         log_backoff = attempts - 2 + MIN_LOG_BACKOFF;
 264         if ( log_backoff > MAX_LOG_BACKOFF )
 265             log_backoff = MAX_LOG_BACKOFF;
 266         mask = (1 << log_backoff) - 1;
 267         rqtp.tv_nsec = rand_arr[priv->random_counter++ & RANDOM_MASK] & mask;
 268         rqtp.tv_sec  = 0;
 269         while ( nanosleep(&rqtp, NULL) != 0 ) continue;
 270 #else
 271         usleep(1);
 272 #endif
 273     }
 274
 275     return attempts < MAX_RETRIES;
 276 #else
 277     return FALSE;
 278 #endif
 279 }
 280
 281
 282 static void *read_loc_data(ptst_t *ptst, stm_loc *l)
 283 {
 284     void           *data;
 285     stm_tx         *t;
 286     unsigned long   st;
 287     stm_tx_entry  **pent;
 288     int attempts = 0;
 289
 290     for ( ; ; )
 291     {
 292         switch ( (st = l->status) )
 293         {
 294         case TXS_SUCCESSFUL:
 295             return l->new;
 296         case TXS_FAILED:
 297             return l->old;
 298         default:
 299             t = mk_descriptor(st);
 300             rc_up_descriptor(t);
 301             if ( l->status == st )
 302             {
 303                 switch ( t->status )
 304                 {
 305                 case TXS_SUCCESSFUL:
 306                     rc_down_descriptor(ptst, t);
 307                     l->status = TXS_SUCCESSFUL;
 308                     return l->new;
 309                 case TXS_FAILED:
 310                     rc_down_descriptor(ptst, t);
 311                     l->status = TXS_FAILED;
 312                     return l->old;
 313                 default:
 314                     if ( !contention_wait(ptst, ++attempts) )
 315                     {
 316                         attempts = 0;
 317                         CASIO(&t->status, TXS_IN_PROGRESS, TXS_FAILED);
 318                     }
 319                 }
 320             }
 321             rc_down_descriptor(ptst, t);
 322         }
 323     }
 324 }
 325
 326
 327 static stm_loc *install_loc(ptst_t *ptst, stm_tx *t,
 328                             stm_blk *b, stm_loc *old_loc)
 329 {
 330     stm_loc *new_loc = gc_alloc(ptst, gc_loc_id);
 331
 332     new_loc->status = (unsigned long)t;
 333     new_loc->new    = gc_alloc(ptst, t->gc_data_id);
 334     new_loc->old    = read_loc_data(ptst, old_loc);
 335     memcpy(new_loc->new, new_loc->old, t->blk_size);
 336
 337     if ( CASPO(&b->loc, old_loc, new_loc) != old_loc )
 338     {
 339         gc_unsafe_free(ptst, new_loc->new, t->gc_data_id);
 340         gc_unsafe_free(ptst, new_loc     , gc_loc_id);
 341         new_loc = NULL;
 342     }
 343     else
 344     {
 345         gc_free(ptst, old_loc, gc_loc_id);
 346     }
 347
 348     return new_loc;
 349 }
 350
 351
 352 stm *new_stm(ptst_t *ptst, int blk_size)
 353 {
 354     stm *mem = malloc(CACHE_LINE_SIZE);
 355     mem->blk_size = blk_size;
 356     mem->gc_data_id = gc_add_allocator(ALLOCATOR_SIZE(blk_size));
 357     return mem;
 358 }
 359
 360
 361 void free_stm(ptst_t *ptst, stm *mem)
 362 {
 363     gc_remove_allocator(mem->gc_data_id);
 364     free(mem);
 365 }
 366
 367
 368 stm_blk *new_stm_blk(ptst_t *ptst, stm *mem)
 369 {
 370     stm_blk *b = gc_alloc(ptst, gc_blk_id);
 371     stm_loc *l = gc_alloc(ptst, gc_loc_id);
 372     b->loc     = l;
 373     l->status  = TXS_SUCCESSFUL;
 374     l->old     = NULL;
 375     l->new     = gc_alloc(ptst, mem->gc_data_id);
 376     return b;
 377 }
 378
 379
 380 void free_stm_blk(ptst_t *ptst, stm *mem, stm_blk *b)
 381 {
 382     stm_loc *l;
 383     void    *data;
 384
 385     l    = FASPO(&b->loc, NULL);
 386     data = read_loc_data(ptst, l);
 387
 388     gc_free(ptst, data, mem->gc_data_id);
 389     gc_free(ptst, l, gc_loc_id);
 390     gc_free(ptst, b, gc_blk_id);
 391 }
 392
 393
 394 void *init_stm_blk(ptst_t *ptst, stm *mem, stm_blk *b)
 395 {
 396     return b->loc->new;
 397 }
 398
 399
 400 int sizeof_stm_blk(ptst_t *ptst, stm *mem, stm_blk *b)
 401 {
 402     return mem->blk_size;
 403 }
 404
 405
 406 stm_tx *new_stm_tx(ptst_t *ptst, stm *mem, sigjmp_buf *penv)
 407 {
 408     priv_t *priv = &priv_ptst[ptst->id];
 409     stm_tx *t;
 410
 411     if ( priv->cur_tx != NULL ) goto nesting;
 412     t = new_descriptor(priv);
 413     t->status = TXS_IN_PROGRESS;
 414     t->reads = t->writes = NULL;
 415     t->alloc_ptr = t->check = (stm_tx_entry *)(t + 1);
 416     t->gc_data_id = mem->gc_data_id;
 417     t->blk_size = mem->blk_size;
 418     t->penv = penv;
 419     t->dummy = NULL;
 420     priv->cur_tx = t;
 421     return t;
 422
 423  nesting:
 424     fprintf(stderr, "No nesting of transactions is allowed\n");
 425     return NULL;
 426 }
 427
 428
 429 bool_t commit_stm_tx(ptst_t *ptst, stm_tx *t)
 430 {
 431     unsigned int desired_st = TXS_SUCCESSFUL, st;
 432     stm_tx_entry *ent;
 433     priv_t *priv = &priv_ptst[ptst->id];
 434
 435     priv->cur_tx = NULL;
 436
 437     MB();
 438
 439     for ( ent = t->reads; ent != NULL; ent = ent->next )
 440     {
 441         if ( ent->b->loc != ent->l )
 442             desired_st = TXS_FAILED;
 443     }
 444
 445     if ( read_only(t) )
 446     {
 447         /* A very fast path: we can immediately reuse the descriptor. */
 448         if ( t->dummy != NULL )
 449             gc_unsafe_free(ptst, t->dummy, t->gc_data_id);
 450         t->next_free = priv->next_descriptor;
 451         priv->next_descriptor = t;
 452         return desired_st == TXS_SUCCESSFUL;
 453     }
 454
 455     st = CASIO(&t->status, TXS_IN_PROGRESS, desired_st);
 456     if ( st == TXS_IN_PROGRESS )
 457         st = desired_st;
 458
 459     assert((st == TXS_FAILED) || (st == TXS_SUCCESSFUL));
 460
 461     WMB_NEAR_CAS();
 462
 463     for ( ent = t->writes; ent != NULL; ent = ent->next )
 464     {
 465         ent->l->status = (unsigned long)st;
 466         gc_free(ptst,
 467                 (st == TXS_SUCCESSFUL) ? ent->l->old : ent->l->new,
 468                 t->gc_data_id);
 469     }
 470
 471     if ( t->dummy != NULL )
 472         gc_unsafe_free(ptst, t->dummy, t->gc_data_id);
 473
 474     rc_down_descriptor(ptst, t);
 475
 476     return st == TXS_SUCCESSFUL;
 477 }
 478
 479
 480 bool_t validate_stm_tx(ptst_t *ptst, stm_tx *t)
 481 {
 482     stm_tx_entry *ent;
 483
 484     RMB();
 485
 486     /* A conflict on a pending update will cause us to get failed. */
 487     if ( t->status == TXS_FAILED )
 488         goto fail;
 489
 490     /* Reads must be explicitly checked. */
 491     for ( ent = t->reads; ent != NULL; ent = ent->next )
 492     {
 493         if ( ent->b->loc != ent->l )
 494             goto fail;
 495     }
 496
 497     return TRUE;
 498
 499  fail:
 500     t->status = TXS_FAILED;
 501     return FALSE;
 502 }
 503
 504
 505 void abort_stm_tx(ptst_t *ptst, stm_tx *t)
 506 {
 507     t->status = TXS_FAILED;
 508 }
 509
 510
 511 void *read_stm_blk(ptst_t *ptst, stm_tx *t, stm_blk *b)
 512 {
 513     stm_tx_entry **pent, *ent;
 514     sigjmp_buf *penv;
 515     void *result;
 516
 517     if ( b == dummy_obj )
 518     {
 519         if ( t->dummy == NULL )
 520         {
 521             t->dummy = gc_alloc(ptst, t->gc_data_id);
 522             memcpy(t->dummy, dummy_data, t->blk_size);
 523         }
 524         return t->dummy;
 525     }
 526
 527     pent = search_stm_tx_entry(&t->writes, b);
 528     ent  = *pent;
 529     if ( (ent != NULL) && (ent->b == b) ) goto found;
 530
 531     pent = search_stm_tx_entry(&t->reads, b);
 532     ent  = *pent;
 533     if ( (ent != NULL) && (ent->b == b) ) goto found;
 534
 535     ent = alloc_stm_tx_entry(t);
 536     ent->b    = b;
 537     if ( (ent->l = b->loc) == NULL )
 538         goto fail;
 539     ent->data = read_loc_data(ptst, ent->l);
 540     ent->next = *pent;
 541     *pent = ent;
 542
 543     return ent->data;
 544
 545  found:
 546     result = ent->data;
 547     ent = t->check;
 548     if ( is_stale(t, ent) ) goto fail;
 549     if ( ++t->check == t->alloc_ptr ) t->check = (stm_tx_entry *)(t + 1);
 550     return result;
 551
 552  fail:
 553     penv = t->penv;
 554     abort_stm_tx(ptst, t);
 555     commit_stm_tx(ptst, t);
 556     siglongjmp(*penv, 0);
 557     assert(0);
 558     return NULL;
 559 }
 560
 561
 562 void *write_stm_blk(ptst_t *ptst, stm_tx *t, stm_blk *b)
 563 {
 564     stm_tx_entry **r_pent, **w_pent, *ent;
 565     stm_loc *loc;
 566     sigjmp_buf *penv;
 567     void *result;
 568
 569     if ( b == dummy_obj )
 570     {
 571         if ( t->dummy == NULL )
 572         {
 573             t->dummy = gc_alloc(ptst, t->gc_data_id);
 574             memcpy(t->dummy, dummy_data, t->blk_size);
 575         }
 576         return t->dummy;
 577     }
 578
 579     w_pent = search_stm_tx_entry(&t->writes, b);
 580     ent = *w_pent;
 581     if ( (ent != NULL) && (ent->b == b) ) goto found;
 582
 583     r_pent = search_stm_tx_entry(&t->reads, b);
 584     ent = *r_pent;
 585     if ( (ent != NULL) && (ent->b == b) )
 586     {
 587         *r_pent = ent->next;
 588     }
 589     else
 590     {
 591         ent       = alloc_stm_tx_entry(t);
 592         ent->b    = b;
 593         if ( (ent->l = b->loc) == NULL )
 594             goto fail;
 595     }
 596
 597     loc = install_loc(ptst, t, b, ent->l);
 598     if ( loc == NULL ) goto fail;
 599
 600     ent->l    = loc;
 601     ent->data = loc->new;
 602     ent->next = *w_pent;
 603     *w_pent = ent;
 604
 605     return ent->data;
 606
 607  found:
 608     result = ent->data;
 609     ent = t->check;
 610     if ( is_stale(t, ent) ) goto fail;
 611     if ( ++t->check == t->alloc_ptr ) t->check = (stm_tx_entry *)(t + 1);
 612     return result;
 613
 614  fail:
 615     penv = t->penv;
 616     abort_stm_tx(ptst, t);
 617     commit_stm_tx(ptst, t);
 618     siglongjmp(*penv, 0);
 619     assert(0);
 620     return NULL;
 621 }
 622
 623
 624 void remove_from_tx(ptst_t *ptst, stm_tx *t, stm_blk *b)
 625 {
 626     if ( dummy_obj == NULL )
 627     {
 628         dummy_obj  = b;
 629         dummy_data = read_loc_data(ptst, b->loc);
 630     }
 631 }
 632
 633
 634 static void handle_fault(int sig)
 635 {
 636     ptst_t *ptst;
 637     stm_tx *t;
 638
 639     ptst = critical_enter();
 640     t = priv_ptst[ptst->id].cur_tx;
 641     if ( (t != NULL) && !validate_stm_tx(ptst, t) )
 642     {
 643         sigjmp_buf *penv = t->penv;
 644         commit_stm_tx(ptst, t);
 645         critical_exit(ptst);
 646         siglongjmp(*penv, 0);
 647     }
 648
 649  fail:
 650     fprintf(stderr, "Error: unhandleable SIGSEGV!\n");
 651     abort();
 652 }
 653
 654
 655 void _init_stm_subsystem(int pad_data)
 656 {
 657     struct sigaction act;
 658
 659 #ifdef SPARC
 660     int i;
 661     struct timespec rqtp;
 662
 663     rqtp.tv_sec  = 0;
 664     rqtp.tv_nsec = 1000;
 665
 666     while ( nanosleep(&rqtp, NULL) != 0 )
 667     {
 668         if ( errno != EINTR )
 669         {
 670             printf("Urk! Nanosleep not supported!\n");
 671             exit(1);
 672         }
 673     }
 674
 675     for ( i = 0; i < RANDOM_SIZE; i++ )
 676         rand_arr[i] = (unsigned int)random();
 677 #endif
 678
 679     do_padding = pad_data;
 680     gc_blk_id = gc_add_allocator(ALLOCATOR_SIZE(sizeof(stm_blk)));
 681     gc_loc_id = gc_add_allocator(ALLOCATOR_SIZE(sizeof(stm_loc)));
 682     memset(priv_ptst, 0, sizeof(priv_ptst));
 683
 684     act.sa_handler = handle_fault;
 685     sigemptyset(&act.sa_mask);
 686     act.sa_flags = 0;
 687     sigaction(SIGSEGV, &act, NULL);
 688 }