src/mcas/mcas.c

   1 /******************************************************************************
   2  * mcas.c
   3  *
   4  * MCAS implemented as described in:
   5  *  A Practical Multi-Word Compare-and-Swap Operation
   6  *  Timothy Harris, Keir Fraser and Ian Pratt
   7  *  Proceedings of the IEEE Symposium on Distributed Computing, Oct 2002
   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 #include <sys/resource.h>
  39 #include <assert.h>
  40 #include <stdarg.h>
  41 #include <stdio.h>
  42 #include <string.h>
  43
  44 typedef struct CasDescriptor CasDescriptor_t;
  45 typedef struct CasEntry CasEntry_t;
  46 typedef struct per_thread_state_t per_thread_state_t;
  47
  48 extern int num_threads;
  49
  50 #define ARENA_SIZE 40960
  51
  52 struct per_thread_state_t
  53 {
  54     int              id;
  55     CasDescriptor_t *next_descriptor;
  56     void            *arena;
  57     void            *arena_lim;
  58 };
  59
  60
  61 static pthread_key_t mcas_ptst_key;
  62
  63 typedef struct pad128 { char pad[128]; } pad128_t;
  64
  65
  66 /* CAS descriptors. */
  67
  68 #define STATUS_IN_PROGRESS  0
  69 #define STATUS_SUCCEEDED    1
  70 #define STATUS_FAILED       2
  71 #define STATUS_ABORTED      3
  72
  73 struct CasEntry {
  74     void **ptr;
  75     void *old;
  76     void *new;
  77 };
  78
  79 struct CasDescriptor {
  80     int              status;
  81     int              length;
  82     CasDescriptor_t *pt[MAX_THREADS];
  83     int              rc;
  84     CasDescriptor_t *fc; /* free chain */
  85     CasEntry_t       entries[1];
  86 };
  87
  88 /* Marked pointers. */
  89 typedef unsigned long ptr_int;
  90 #ifndef MARK_IN_PROGRESS
  91 #define MARK_IN_PROGRESS 1
  92 #endif
  93 #ifndef MARK_PTR_TO_CD
  94 #define MARK_PTR_TO_CD   2
  95 #endif
  96
  97 #define get_markedness(p) (((ptr_int) (p)) & 3)
  98 #define get_unmarked_reference(p) ((void *) (((ptr_int) (p)) & (~3)))
  99 #define get_marked_reference(p,m) ((void *) (((ptr_int) (p)) | m))
 100
 101 static bool_t mcas0 (per_thread_state_t *ptst, CasDescriptor_t *cd);
 102 static per_thread_state_t *get_ptst (void);
 103
 104 pad128_t p0; /* I'm worried these important RO vars might be false shared */
 105 static int cas_sz;
 106 static int num_ptrs = 1024;
 107 static int ptr_mult = 1;
 108 pad128_t p1;
 109
 110 static void *ALLOC(int size)
 111 {
 112     void *a = calloc(1, size);
 113     if ( a == NULL ) abort();
 114     return a;
 115 }
 116
 117 static void *ALLOC_ALONE (int size)
 118 {
 119     int ps = sysconf(_SC_PAGESIZE);
 120     int req = ps + size + ps;
 121     char *res = ALLOC(req);
 122     return (void *)(res + ps);
 123 }
 124
 125 static int next_thread_id = 0;
 126 static per_thread_state_t *ptsts = NULL;
 127
 128 static void new_arena (per_thread_state_t *ptst, int size)
 129 {
 130     ptst->arena = ALLOC(size);
 131     if ( !ptst->arena ) abort();
 132     ptst->arena_lim = (((char *) ptst->arena) + size);
 133 }
 134
 135 static per_thread_state_t *get_ptst (void)
 136 {
 137     per_thread_state_t *result;
 138     int r;
 139
 140     result = pthread_getspecific(mcas_ptst_key);
 141
 142     if ( result == NULL )
 143     {
 144         int my_id;
 145         int largest = sysconf(_SC_PAGESIZE);
 146
 147         if ( largest < sizeof (per_thread_state_t) )
 148             largest = sizeof (per_thread_state_t);
 149
 150         ALLOC (largest);
 151         result = ALLOC (largest);
 152         ALLOC (largest);
 153
 154         do { my_id = next_thread_id; }
 155         while ( CASIO (&next_thread_id, my_id, my_id + 1) != my_id );
 156
 157         result->id = my_id;
 158         ptsts = result;
 159
 160         new_arena(result, ARENA_SIZE);
 161
 162         r = pthread_setspecific(mcas_ptst_key, result);
 163         assert(r == 0);
 164     }
 165
 166     return result;
 167 }
 168
 169 static void release_descriptor (CasDescriptor_t *cd)
 170 {
 171     per_thread_state_t *ptst = get_ptst ();
 172     cd->fc = ptst->next_descriptor;
 173     ptst->next_descriptor = cd;
 174 }
 175
 176 static int rc_delta_descriptor (CasDescriptor_t *cd,
 177                                 int delta)
 178 {
 179     int rc, new_rc = cd->rc;
 180
 181     do { rc = new_rc; }
 182     while ( (new_rc = CASIO (&(cd->rc), rc, rc + delta)) != rc );
 183
 184     return rc;
 185 }
 186
 187 static void rc_up_descriptor (CasDescriptor_t *cd)
 188 {
 189     rc_delta_descriptor(cd, 2);
 190     MB();
 191 }
 192
 193 static void rc_down_descriptor (CasDescriptor_t *cd)
 194 {
 195     int old_rc, new_rc, cur_rc = cd->rc;
 196
 197     do {
 198         old_rc = cur_rc;
 199         new_rc = old_rc - 2;
 200         if ( new_rc == 0 ) new_rc = 1; else MB();
 201     }
 202     while ( (cur_rc = CASIO(&(cd->rc), old_rc, new_rc)) != old_rc );
 203
 204     if ( old_rc == 2 )
 205         release_descriptor(cd);
 206 }
 207
 208 static CasDescriptor_t *new_descriptor (per_thread_state_t *ptst, int length)
 209 {
 210     CasDescriptor_t *result;
 211     int i;
 212
 213     CasDescriptor_t **ptr = &(ptst->next_descriptor);
 214     result = *ptr;
 215     while ( (result != NULL) && (result->length != length) )
 216     {
 217         ptr = &(result->fc);
 218         result = *ptr;
 219     }
 220
 221     if ( result == NULL )
 222     {
 223         int alloc_size;
 224
 225         alloc_size = sizeof (CasDescriptor_t) +
 226             ((length - 1) * sizeof (CasEntry_t));
 227
 228         result = (CasDescriptor_t *) ptst->arena;
 229         ptst->arena = ((char *) (ptst->arena)) + alloc_size;
 230
 231         if ( ptst->arena >= ptst->arena_lim )
 232         {
 233             new_arena(ptst, ARENA_SIZE);
 234             result = (CasDescriptor_t *) ptst->arena;
 235             ptst->arena = ((char *) (ptst->arena)) + alloc_size;
 236         }
 237
 238         for ( i = 0; i < num_threads; i++ )
 239             result->pt[i] = result;
 240
 241         result->length = length;
 242         result->rc = 2;
 243     }
 244     else
 245     {
 246         *ptr = result->fc;
 247         assert((result->rc & 1) == 1);
 248         rc_delta_descriptor(result, 1); /* clears lowest bit */
 249     }
 250
 251     assert(result->length == length);
 252
 253     return result;
 254 }
 255
 256 static void *read_from_cd (void **ptr, CasDescriptor_t *cd, bool_t get_old)
 257 {
 258     CasEntry_t *ce;
 259     int         i;
 260     int         n;
 261
 262     n = cd->length;
 263     for ( i = 0; i < n; i++ )
 264     {
 265         ce = &(cd->entries[i]);
 266         if ( ce->ptr == ptr )
 267             return get_old ? ce->old : ce->new;
 268     }
 269
 270     assert(0);
 271     return NULL;
 272 }
 273
 274 static void *read_barrier_lite (void **ptr)
 275 {
 276     CasDescriptor_t *cd;
 277     void            *v;
 278     int              m;
 279
 280  retry_read_barrier:
 281     v = *ptr;
 282     m = get_markedness(v);
 283
 284     if ( m == MARK_PTR_TO_CD )
 285     {
 286         WEAK_DEP_ORDER_RMB();
 287         cd = get_unmarked_reference(v);
 288
 289         rc_up_descriptor(cd);
 290         if ( *ptr != v )
 291         {
 292             rc_down_descriptor(cd);
 293             goto retry_read_barrier;
 294         }
 295
 296         v = read_from_cd(ptr, cd, (cd->status != STATUS_SUCCEEDED));
 297
 298         rc_down_descriptor(cd);
 299     }
 300     else if ( m == MARK_IN_PROGRESS )
 301     {
 302         WEAK_DEP_ORDER_RMB();
 303         cd = *(CasDescriptor_t **)get_unmarked_reference(v);
 304
 305         rc_up_descriptor(cd);
 306         if ( *ptr != v )
 307         {
 308             rc_down_descriptor(cd);
 309             goto retry_read_barrier;
 310         }
 311
 312         v = read_from_cd(ptr, cd, (cd->status != STATUS_SUCCEEDED));
 313
 314         rc_down_descriptor(cd);
 315     }
 316
 317     return v;
 318 }
 319
 320 static void clean_descriptor (CasDescriptor_t *cd)
 321 {
 322     int   i;
 323     void *mcd;
 324     int   status;
 325
 326     status = cd->status;
 327     assert(status == STATUS_SUCCEEDED || status == STATUS_FAILED);
 328
 329     mcd = get_marked_reference(cd, MARK_PTR_TO_CD);
 330
 331     if (status == STATUS_SUCCEEDED)
 332         for ( i = 0; i < cd->length; i++ )
 333             CASPO (cd->entries[i].ptr, mcd, cd->entries[i].new);
 334     else
 335         for ( i = 0; i < cd->length; i++ )
 336             CASPO(cd->entries[i].ptr, mcd, cd->entries[i].old);
 337 }
 338
 339 static bool_t mcas_fixup (void **ptr,
 340                           void *value_read)
 341 {
 342     int m;
 343
 344  retry_mcas_fixup:
 345     m = get_markedness(value_read);
 346     if ( m == MARK_PTR_TO_CD )
 347     {
 348         CasDescriptor_t *helpee;
 349         helpee = get_unmarked_reference(value_read);
 350
 351         rc_up_descriptor(helpee);
 352         if ( *ptr != value_read )
 353         {
 354             rc_down_descriptor(helpee);
 355             value_read = *ptr;
 356             goto retry_mcas_fixup;
 357         }
 358
 359         mcas0(NULL, helpee);
 360
 361         rc_down_descriptor(helpee);
 362
 363         return TRUE;
 364     }
 365     else if ( m == MARK_IN_PROGRESS )
 366     {
 367         CasDescriptor_t *other_cd;
 368
 369         WEAK_DEP_ORDER_RMB();
 370         other_cd = *(CasDescriptor_t **)get_unmarked_reference(value_read);
 371
 372         rc_up_descriptor(other_cd);
 373         if ( *ptr != value_read )
 374         {
 375             rc_down_descriptor(other_cd);
 376             value_read = *ptr;
 377             goto retry_mcas_fixup;
 378         }
 379
 380         if ( other_cd->status == STATUS_IN_PROGRESS )
 381             CASPO(ptr,
 382                   value_read,
 383                   get_marked_reference(other_cd, MARK_PTR_TO_CD));
 384         else
 385             CASPO(ptr,
 386                   value_read,
 387                   read_from_cd(ptr, other_cd, TRUE));
 388
 389         rc_down_descriptor (other_cd);
 390         return TRUE;
 391     }
 392
 393     return FALSE;
 394 }
 395
 396 static void *read_barrier (void **ptr)
 397 {
 398     void *v;
 399
 400     do { v = *ptr; }
 401     while ( mcas_fixup(ptr, v) );
 402
 403     return v;
 404 }
 405
 406 static bool_t mcas0 (per_thread_state_t *ptst, CasDescriptor_t *cd)
 407 {
 408     int     i;
 409     int     n;
 410     int     desired_status;
 411     bool_t  final_success;
 412     void   *mcd;
 413     void   *dmcd;
 414     int     old_status;
 415
 416     if ( ptst == NULL )
 417         ptst = get_ptst();
 418
 419     MB(); /* required for sequential consistency */
 420
 421     if ( cd->status == STATUS_SUCCEEDED )
 422     {
 423         clean_descriptor(cd);
 424         final_success = TRUE;
 425         goto out;
 426     }
 427     else if ( cd->status == STATUS_FAILED )
 428     {
 429         clean_descriptor(cd);
 430         final_success = FALSE;
 431         goto out;
 432     }
 433
 434     /* Attempt to link in all entries in the descriptor. */
 435     mcd = get_marked_reference(cd, MARK_PTR_TO_CD);
 436     dmcd = get_marked_reference(&(cd->pt[ptst->id]), MARK_IN_PROGRESS);
 437
 438     desired_status = STATUS_SUCCEEDED;
 439
 440  retry:
 441     n = cd->length;
 442     for (i = 0; i < n; i ++)
 443     {
 444         CasEntry_t *ce         = &(cd->entries[i]);
 445         void       *value_read = CASPO(ce->ptr, ce->old, dmcd);
 446
 447         if ( (value_read != ce->old) &&
 448              (value_read != dmcd) &&
 449              (value_read != mcd) )
 450         {
 451             if ( mcas_fixup(ce->ptr, value_read) )
 452                 goto retry;
 453             desired_status = STATUS_FAILED;
 454             break;
 455         }
 456
 457         RMB_NEAR_CAS(); /* ensure check of status occurs after CASPO. */
 458         if ( cd->status != STATUS_IN_PROGRESS )
 459         {
 460             CASPO(ce->ptr, dmcd, ce->old);
 461             break;
 462         }
 463
 464         if ( value_read != mcd )
 465         {
 466             value_read = CASPO(ce->ptr, dmcd, mcd);
 467             assert((value_read == dmcd) ||
 468                    (value_read == mcd) ||
 469                    (cd->status != STATUS_IN_PROGRESS));
 470         }
 471     }
 472
 473     /*
 474      * All your ptrs are belong to us (or we've been helped and
 475      * already known to have succeeded or failed).  Try to
 476      * propagate our desired result into the status field.
 477      */
 478
 479     /*
 480      * When changing to success, we must have all pointer ownerships
 481      * globally visible. But we get this without a memory barrier, as
 482      * 'desired_status' is dependent on the outcome of each CASPO
 483      * to MARK_IN_PROGRESS.
 484      *
 485      * Architectures providing CAS natively all specify that the operation
 486      * is _indivisible_. That is, the write will be done when the CAS
 487      * completes.
 488      *
 489      * Architectures providing LL/SC are even better: any following
 490      * instruction in program order is control-dependent on the CAS, because
 491      * CAS may be retried if SC fails. All we need is that SC gets to point
 492      * of coherency before producing its result: even Alpha provides this!
 493      */
 494     WEAK_DEP_ORDER_WMB();
 495     old_status = CASIO((int *)&cd->status,
 496                        STATUS_IN_PROGRESS,
 497                        desired_status);
 498     /*
 499      * This ensures final sequential consistency.
 500      * Also ensures that the status update is visible before cleanup.
 501      */
 502     WMB_NEAR_CAS();
 503
 504     clean_descriptor(cd);
 505     final_success = (cd->status == STATUS_SUCCEEDED);
 506
 507  out:
 508     return final_success;
 509 }
 510
 511
 512 void mcas_init (void)
 513 {
 514     int r = pthread_key_create(&mcas_ptst_key, NULL);
 515     if ( r != 0 ) abort();
 516 }
 517
 518 /***********************************************************************/
 519
 520 bool_t mcas (int n,
 521              void **ptr, void *old, void *new,
 522              ...)
 523 {
 524     va_list             ap;
 525     int                 i;
 526     CasDescriptor_t    *cd;
 527     CasEntry_t         *ce;
 528     int                 result = 0;
 529     per_thread_state_t *ptst = get_ptst();
 530
 531     cd = new_descriptor(ptst, n);
 532
 533     cd->status = STATUS_IN_PROGRESS;
 534     cd->length = n;
 535
 536     ce = cd->entries;
 537     ce->ptr = ptr;
 538     ce->old = old;
 539     ce->new = new;
 540
 541     va_start(ap, new);
 542     for ( i = 1; i < n; i++ )
 543     {
 544         ce ++;
 545         ce->ptr = va_arg(ap, void **);
 546         ce->old = va_arg(ap, void *);
 547         ce->new = va_arg(ap, void *);
 548     }
 549     va_end (ap);
 550
 551     /* Insertion sort. Fail on non-unique pointers. */
 552     for ( i = 1, ce = &cd->entries[1]; i < n; i++, ce++ )
 553     {
 554         int j;
 555         CasEntry_t *cei, tmp;
 556         for ( j = i-1, cei = ce-1; j >= 0; j--, cei-- )
 557             if ( cei->ptr <= ce->ptr ) break;
 558         if ( cei->ptr == ce->ptr ) goto out;
 559         if ( ++cei != ce )
 560         {
 561             tmp = *ce;
 562             memmove(cei+1, cei, (ce-cei)*sizeof(CasEntry_t));
 563             *cei = tmp;
 564         }
 565     }
 566
 567     result = mcas0(ptst, cd);
 568     assert(cd->status != STATUS_IN_PROGRESS);
 569
 570  out:
 571     rc_down_descriptor (cd);
 572     return result;
 573 }
 574