subversion/libsvn_subr/named_atomic.c

   1 /*
   2  * svn_named_atomic.c: routines for machine-wide named atomics.
   3  *
   4  * ====================================================================
   5  *    Licensed to the Apache Software Foundation (ASF) under one
   6  *    or more contributor license agreements.  See the NOTICE file
   7  *    distributed with this work for additional information
   8  *    regarding copyright ownership.  The ASF licenses this file
   9  *    to you under the Apache License, Version 2.0 (the
  10  *    "License"); you may not use this file except in compliance
  11  *    with the License.  You may obtain a copy of the License at
  12  *
  13  *      http://www.apache.org/licenses/LICENSE-2.0
  14  *
  15  *    Unless required by applicable law or agreed to in writing,
  16  *    software distributed under the License is distributed on an
  17  *    "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
  18  *    KIND, either express or implied.  See the License for the
  19  *    specific language governing permissions and limitations
  20  *    under the License.
  21  * ====================================================================
  22  */
  23
  24 #include "private/svn_named_atomic.h"
  25
  26 #include <apr_global_mutex.h>
  27 #include <apr_mmap.h>
  28
  29 #include "svn_private_config.h"
  30 #include "private/svn_atomic.h"
  31 #include "private/svn_mutex.h"
  32 #include "svn_pools.h"
  33 #include "svn_dirent_uri.h"
  34 #include "svn_io.h"
  35
  36 /* Implementation aspects.
  37  *
  38  * We use a single shared memory block (memory mapped file) that will be
  39  * created by the first user and merely mapped by all subsequent ones.
  40  * The memory block contains an short header followed by a fixed-capacity
  41  * array of named atomics. The number of entries currently in use is stored
  42  * in the header part.
  43  *
  44  * Finding / creating the MMAP object as well as adding new array entries
  45  * is being guarded by an APR global mutex. Since releasing the MMAP
  46  * structure and closing the underlying does not affect other users of the
  47  * same, cleanup will not be synchronized.
  48  *
  49  * The array is append-only.  Once a process mapped the block into its
  50  * address space, it may freely access any of the used entries.  However,
  51  * it must synchronize access to the volatile data within the entries.
  52  * On Windows and where otherwise supported by GCC, lightweight "lock-free"
  53  * synchronization will be used. Other targets serialize all access using
  54  * a global mutex.
  55  *
  56  * Atomics will be identified by their name (a short string) and lookup
  57  * takes linear time. But even that takes only about 10 microseconds for a
  58  * full array scan -- which is in the same order of magnitude than e.g. a
  59  * single global mutex lock / unlock pair.
  60  */
  61
  62 /* Capacity of our shared memory object, i.e. max number of named atomics
  63  * that may be created. Should have the form 2**N - 1.
  64  */
  65 #define MAX_ATOMIC_COUNT 1023
  66
  67 /* We choose the size of a single named atomic object to fill a complete
  68  * cache line (on most architectures).  Thereby, we minimize the cache
  69  * sync. overhead between different CPU cores.
  70  */
  71 #define CACHE_LINE_LENGTH 64
  72
  73 /* We need 8 bytes for the actual value and the remainder is used to
  74  * store the NUL-terminated name.
  75  *
  76  * Must not be smaller than SVN_NAMED_ATOMIC__MAX_NAME_LENGTH.
  77  */
  78 #define MAX_NAME_LENGTH (CACHE_LINE_LENGTH - sizeof(apr_int64_t) - 1)
  79
  80 /* Particle that will be appended to the namespace name to form the
  81  * name of the mutex / lock file used for that namespace.
  82  */
  83 #define MUTEX_NAME_SUFFIX ".mutex"
  84
  85 /* Particle that will be appended to the namespace name to form the
  86  * name of the shared memory file that backs that namespace.
  87  */
  88 #define SHM_NAME_SUFFIX ".shm"
  89
  90 /* Platform-dependent implementations of our basic atomic operations.
  91  * NA_SYNCHRONIZE(op) will ensure that the OP gets executed atomically.
  92  * This will be zero-overhead if OP itself is already atomic.
  93  *
  94  * (We don't call it SYNCHRONIZE because Windows has a preprocess macro by
  95  * that name.)
  96  *
  97  * The default implementation will use the same mutex for initialization
  98  * as well as any type of data access.  This is quite expensive and we
  99  * can do much better on most platforms.
 100  */
 101 #if defined(WIN32) && ((_WIN32_WINNT >= 0x0502) || defined(InterlockedExchangeAdd64))
 102
 103 /* Interlocked API / intrinsics guarantee full data synchronization
 104  */
 105 #define synched_read(mem) *mem
 106 #define synched_write(mem, value) InterlockedExchange64(mem, value)
 107 #define synched_add(mem, delta) InterlockedExchangeAdd64(mem, delta)
 108 #define synched_cmpxchg(mem, value, comperand) \
 109   InterlockedCompareExchange64(mem, value, comperand)
 110
 111 #define NA_SYNCHRONIZE(_atomic,op) op;
 112 #define NA_SYNCHRONIZE_IS_FAST TRUE
 113
 114 #elif SVN_HAS_ATOMIC_BUILTINS
 115
 116 /* GCC provides atomic intrinsics for most common CPU types
 117  */
 118 #define synched_read(mem) *mem
 119 #define synched_write(mem, value) __sync_lock_test_and_set(mem, value)
 120 #define synched_add(mem, delta) __sync_add_and_fetch(mem, delta)
 121 #define synched_cmpxchg(mem, value, comperand) \
 122   __sync_val_compare_and_swap(mem, comperand, value)
 123
 124 #define NA_SYNCHRONIZE(_atomic,op) op;
 125 #define NA_SYNCHRONIZE_IS_FAST TRUE
 126
 127 #else
 128
 129 /* Default implementation
 130  */
 131 static apr_int64_t
 132 synched_read(volatile apr_int64_t *mem)
 133 {
 134   return *mem;
 135 }
 136
 137 static apr_int64_t
 138 synched_write(volatile apr_int64_t *mem, apr_int64_t value)
 139 {
 140   apr_int64_t old_value = *mem;
 141   *mem = value;
 142
 143   return old_value;
 144 }
 145
 146 static apr_int64_t
 147 synched_add(volatile apr_int64_t *mem, apr_int64_t delta)
 148 {
 149   return *mem += delta;
 150 }
 151
 152 static apr_int64_t
 153 synched_cmpxchg(volatile apr_int64_t *mem,
 154                 apr_int64_t value,
 155                 apr_int64_t comperand)
 156 {
 157   apr_int64_t old_value = *mem;
 158   if (old_value == comperand)
 159     *mem = value;
 160
 161   return old_value;
 162 }
 163
 164 #define NA_SYNCHRONIZE(_atomic,op)\
 165   do{\
 166   SVN_ERR(lock(_atomic->mutex));\
 167   op;\
 168   SVN_ERR(unlock(_atomic->mutex,SVN_NO_ERROR));\
 169   }while(0)
 170
 171 #define NA_SYNCHRONIZE_IS_FAST FALSE
 172
 173 #endif
 174
 175 /* Structure describing a single atomic: its VALUE and NAME.
 176  */
 177 struct named_atomic_data_t
 178 {
 179   volatile apr_int64_t value;
 180   char name[MAX_NAME_LENGTH + 1];
 181 };
 182
 183 /* Content of our shared memory buffer.  COUNT is the number
 184  * of used entries in ATOMICS.  Insertion is append-only.
 185  * PADDING is used to align the header information with the
 186  * atomics to create a favorable data alignment.
 187  */
 188 struct shared_data_t
 189 {
 190   volatile apr_uint32_t count;
 191   char padding [sizeof(struct named_atomic_data_t) - sizeof(apr_uint32_t)];
 192
 193   struct named_atomic_data_t atomics[MAX_ATOMIC_COUNT];
 194 };
 195
 196 /* Structure combining all objects that we need for access serialization.
 197  */
 198 struct mutex_t
 199 {
 200   /* Inter-process sync. is handled by through lock file. */
 201   apr_file_t *lock_file;
 202
 203   /* Pool to be used with lock / unlock functions */
 204   apr_pool_t *pool;
 205 };
 206
 207 /* API structure combining the atomic data and the access mutex
 208  */
 209 struct svn_named_atomic__t
 210 {
 211   /* pointer into the shared memory */
 212   struct named_atomic_data_t *data;
 213
 214   /* sync. object; never NULL (even if unused) */
 215   struct mutex_t *mutex;
 216 };
 217
 218 /* This is intended to be a singleton struct.  It contains all
 219  * information necessary to initialize and access the shared
 220  * memory.
 221  */
 222 struct svn_atomic_namespace__t
 223 {
 224   /* Pointer to the shared data mapped into our process */
 225   struct shared_data_t *data;
 226
 227   /* Last time we checked, this was the number of used
 228    * (i.e. fully initialized) items.  I.e. we can read
 229    * their names without further sync. */
 230   volatile svn_atomic_t min_used;
 231
 232   /* for each atomic in the shared memory, we hand out
 233    * at most one API-level object. */
 234   struct svn_named_atomic__t atomics[MAX_ATOMIC_COUNT];
 235
 236   /* Synchronization object for this namespace */
 237   struct mutex_t mutex;
 238 };
 239
 240 /* On most operating systems APR implements file locks per process, not
 241  * per file. I.e. the lock file will only sync. among processes but within
 242  * a process, we must use a mutex to sync the threads. */
 243 /* Compare ../libsvn_fs_fs/fs.h:SVN_FS_FS__USE_LOCK_MUTEX */
 244 #if APR_HAS_THREADS && !defined(WIN32)
 245 #define USE_THREAD_MUTEX 1
 246 #else
 247 #define USE_THREAD_MUTEX 0
 248 #endif
 249
 250 /* Used for process-local thread sync.
 251  */
 252 static svn_mutex__t *thread_mutex = NULL;
 253
 254 /* Initialization flag for the above used by svn_atomic__init_once.
 255  */
 256 static volatile svn_atomic_t mutex_initialized = FALSE;
 257
 258 /* Initialize the thread sync. structures.
 259  * To be called by svn_atomic__init_once.
 260  */
 261 static svn_error_t *
 262 init_thread_mutex(void *baton, apr_pool_t *pool)
 263 {
 264   /* let the mutex live as long as the APR */
 265   apr_pool_t *global_pool = svn_pool_create(NULL);
 266
 267   return svn_mutex__init(&thread_mutex, USE_THREAD_MUTEX, global_pool);
 268 }
 269
 270 /* Utility that acquires our global mutex and converts error types.
 271  */
 272 static svn_error_t *
 273 lock(struct mutex_t *mutex)
 274 {
 275   svn_error_t *err;
 276
 277   /* Get lock on the filehandle. */
 278   SVN_ERR(svn_mutex__lock(thread_mutex));
 279   err = svn_io_lock_open_file(mutex->lock_file, TRUE, FALSE, mutex->pool);
 280
 281   return err
 282     ? svn_mutex__unlock(thread_mutex, err)
 283     : err;
 284 }
 285
 286 /* Utility that releases the lock previously acquired via lock().  If the
 287  * unlock succeeds and OUTER_ERR is not NULL, OUTER_ERR will be returned.
 288  * Otherwise, return the result of the unlock operation.
 289  */
 290 static svn_error_t *
 291 unlock(struct mutex_t *mutex, svn_error_t * outer_err)
 292 {
 293   svn_error_t *unlock_err
 294       = svn_io_unlock_open_file(mutex->lock_file, mutex->pool);
 295   return svn_mutex__unlock(thread_mutex,
 296                            svn_error_compose_create(outer_err,
 297                                                     unlock_err));
 298 }
 299
 300 /* The last user to close a particular namespace should also remove the
 301  * lock file.  Failure to do so, however, does not affect further uses
 302  * of the same namespace.
 303  */
 304 static apr_status_t
 305 delete_lock_file(void *arg)
 306 {
 307   struct mutex_t *mutex = arg;
 308   const char *lock_name = NULL;
 309
 310   /* locks have already been cleaned up. Simply close the file */
 311   apr_status_t status = apr_file_close(mutex->lock_file);
 312
 313   /* Remove the file from disk. This will fail if there ares still other
 314    * users of this lock file, i.e. namespace. */
 315   apr_file_name_get(&lock_name, mutex->lock_file);
 316   if (lock_name)
 317     apr_file_remove(lock_name, mutex->pool);
 318
 319   return status;
 320 }
 321
 322 /* Validate the ATOMIC parameter, i.e it's address.  Correct code will
 323  * never need this but if someone should accidentally to use a NULL or
 324  * incomplete structure, let's catch that here instead of segfaulting.
 325  */
 326 static svn_error_t *
 327 validate(svn_named_atomic__t *atomic)
 328 {
 329   return atomic && atomic->data && atomic->mutex
 330     ? SVN_NO_ERROR
 331     : svn_error_create(SVN_ERR_BAD_ATOMIC, 0, _("Not a valid atomic"));
 332 }
 333
 334 /* Auto-initialize and return in *ATOMIC the API-level object for the
 335  * atomic with index I within NS. */
 336 static void
 337 return_atomic(svn_named_atomic__t **atomic,
 338               svn_atomic_namespace__t *ns,
 339               int i)
 340 {
 341   *atomic = &ns->atomics[i];
 342   if (ns->atomics[i].data == NULL)
 343     {
 344       (*atomic)->mutex = &ns->mutex;
 345       (*atomic)->data = &ns->data->atomics[i];
 346     }
 347 }
 348
 349 /* Implement API */
 350
 351 svn_boolean_t
 352 svn_named_atomic__is_supported(void)
 353 {
 354 #ifdef _WIN32
 355   static svn_tristate_t result = svn_tristate_unknown;
 356
 357   if (result == svn_tristate_unknown)
 358     {
 359       /* APR SHM implementation requires the creation of global objects */
 360       HANDLE handle = CreateFileMappingA(INVALID_HANDLE_VALUE,
 361                                          NULL,
 362                                          PAGE_READONLY,
 363                                          0,
 364                                          1,
 365                                          "Global\\__RandomXZY_svn");
 366       if (handle != NULL)
 367         {
 368           CloseHandle(handle);
 369           result = svn_tristate_true;
 370         }
 371       else
 372         result = svn_tristate_false;
 373     }
 374
 375   return result == svn_tristate_true;
 376 #else
 377   return TRUE;
 378 #endif
 379 }
 380
 381 svn_boolean_t
 382 svn_named_atomic__is_efficient(void)
 383 {
 384   return NA_SYNCHRONIZE_IS_FAST;
 385 }
 386
 387 svn_error_t *
 388 svn_atomic_namespace__create(svn_atomic_namespace__t **ns,
 389                              const char *name,
 390                              apr_pool_t *result_pool)
 391 {
 392   apr_status_t apr_err;
 393   svn_error_t *err;
 394   apr_file_t *file;
 395   apr_mmap_t *mmap;
 396   const char *shm_name, *lock_name;
 397   apr_finfo_t finfo;
 398
 399   apr_pool_t *subpool = svn_pool_create(result_pool);
 400
 401   /* allocate the namespace data structure
 402    */
 403   svn_atomic_namespace__t *new_ns = apr_pcalloc(result_pool, sizeof(**ns));
 404
 405   /* construct the names of the system objects that we need
 406    */
 407   shm_name = apr_pstrcat(subpool, name, SHM_NAME_SUFFIX, NULL);
 408   lock_name = apr_pstrcat(subpool, name, MUTEX_NAME_SUFFIX, NULL);
 409
 410   /* initialize the lock objects
 411    */
 412   SVN_ERR(svn_atomic__init_once(&mutex_initialized, init_thread_mutex, NULL,
 413                                 result_pool));
 414
 415   new_ns->mutex.pool = result_pool;
 416   SVN_ERR(svn_io_file_open(&new_ns->mutex.lock_file, lock_name,
 417                            APR_READ | APR_WRITE | APR_CREATE,
 418                            APR_OS_DEFAULT,
 419                            result_pool));
 420
 421   /* Make sure the last user of our lock file will actually remove it.
 422    * Please note that only the last file handle begin closed will actually
 423    * remove the underlying file (see docstring for apr_file_remove).
 424    */
 425   apr_pool_cleanup_register(result_pool, &new_ns->mutex,
 426                             delete_lock_file,
 427                             apr_pool_cleanup_null);
 428
 429   /* Prevent concurrent initialization.
 430    */
 431   SVN_ERR(lock(&new_ns->mutex));
 432
 433   /* First, make sure that the underlying file exists.  If it doesn't
 434    * exist, create one and initialize its content.
 435    */
 436   err = svn_io_file_open(&file, shm_name,
 437                           APR_READ | APR_WRITE | APR_CREATE,
 438                           APR_OS_DEFAULT,
 439                           result_pool);
 440   if (!err)
 441     {
 442       err = svn_io_stat(&finfo, shm_name, APR_FINFO_SIZE, subpool);
 443       if (!err && finfo.size < sizeof(struct shared_data_t))
 444         {
 445            /* Zero all counters, values and names.
 446             */
 447            struct shared_data_t initial_data;
 448            memset(&initial_data, 0, sizeof(initial_data));
 449            err = svn_io_file_write_full(file, &initial_data,
 450                                         sizeof(initial_data), NULL,
 451                                         subpool);
 452         }
 453     }
 454
 455   /* Now, map it into memory.
 456    */
 457   if (!err)
 458     {
 459       apr_err = apr_mmap_create(&mmap, file, 0, sizeof(*new_ns->data),
 460                                 APR_MMAP_READ | APR_MMAP_WRITE , result_pool);
 461       if (!apr_err)
 462         new_ns->data = mmap->mm;
 463       else
 464         err = svn_error_createf(apr_err, NULL,
 465                                 _("MMAP failed for file '%s'"), shm_name);
 466     }
 467
 468   svn_pool_destroy(subpool);
 469
 470   if (!err && new_ns->data)
 471     {
 472       /* Detect severe cases of corruption (i.e. when some outsider messed
 473        * with our data file)
 474        */
 475       if (new_ns->data->count > MAX_ATOMIC_COUNT)
 476         return svn_error_create(SVN_ERR_CORRUPTED_ATOMIC_STORAGE, 0,
 477                        _("Number of atomics in namespace is too large."));
 478
 479       /* Cache the number of existing, complete entries.  There can't be
 480        * incomplete ones from other processes because we hold the mutex.
 481        * Our process will also not access this information since we are
 482        * either being called from within svn_atomic__init_once or by
 483        * svn_atomic_namespace__create for a new object.
 484        */
 485       new_ns->min_used = new_ns->data->count;
 486       *ns = new_ns;
 487     }
 488
 489   /* Unlock to allow other processes may access the shared memory as well.
 490    */
 491   return unlock(&new_ns->mutex, err);
 492 }
 493
 494 svn_error_t *
 495 svn_atomic_namespace__cleanup(const char *name,
 496                               apr_pool_t *pool)
 497 {
 498   const char *shm_name, *lock_name;
 499
 500   /* file names used for the specified namespace */
 501   shm_name = apr_pstrcat(pool, name, SHM_NAME_SUFFIX, NULL);
 502   lock_name = apr_pstrcat(pool, name, MUTEX_NAME_SUFFIX, NULL);
 503
 504   /* remove these files if they exist */
 505   SVN_ERR(svn_io_remove_file2(shm_name, TRUE, pool));
 506   SVN_ERR(svn_io_remove_file2(lock_name, TRUE, pool));
 507
 508   return SVN_NO_ERROR;
 509 }
 510
 511 svn_error_t *
 512 svn_named_atomic__get(svn_named_atomic__t **atomic,
 513                       svn_atomic_namespace__t *ns,
 514                       const char *name,
 515                       svn_boolean_t auto_create)
 516 {
 517   apr_uint32_t i, count;
 518   svn_error_t *error = SVN_NO_ERROR;
 519   apr_size_t len = strlen(name);
 520
 521   /* Check parameters and make sure we return a NULL atomic
 522    * in case of failure.
 523    */
 524   *atomic = NULL;
 525   if (len > SVN_NAMED_ATOMIC__MAX_NAME_LENGTH)
 526     return svn_error_create(SVN_ERR_BAD_ATOMIC, 0,
 527                             _("Atomic's name is too long."));
 528
 529   /* If no namespace has been provided, bail out.
 530    */
 531   if (ns == NULL || ns->data == NULL)
 532     return svn_error_create(SVN_ERR_BAD_ATOMIC, 0,
 533                             _("Namespace has not been initialized."));
 534
 535   /* Optimistic lookup.
 536    * Because we never change the name of existing atomics and may only
 537    * append new ones, we can safely compare the name of existing ones
 538    * with the name that we are looking for.
 539    */
 540   for (i = 0, count = svn_atomic_read(&ns->min_used); i < count; ++i)
 541     if (strncmp(ns->data->atomics[i].name, name, len + 1) == 0)
 542       {
 543         return_atomic(atomic, ns, i);
 544         return SVN_NO_ERROR;
 545       }
 546
 547   /* Try harder:
 548    * Serialize all lookup and insert the item, if necessary and allowed.
 549    */
 550   SVN_ERR(lock(&ns->mutex));
 551
 552   /* We only need to check for new entries.
 553    */
 554   for (i = count; i < ns->data->count; ++i)
 555     if (strncmp(ns->data->atomics[i].name, name, len + 1) == 0)
 556       {
 557         return_atomic(atomic, ns, i);
 558
 559         /* Update our cached number of complete entries. */
 560         svn_atomic_set(&ns->min_used, ns->data->count);
 561
 562         return unlock(&ns->mutex, error);
 563       }
 564
 565   /* Not found.  Append a new entry, if allowed & possible.
 566    */
 567   if (auto_create)
 568     {
 569       if (ns->data->count < MAX_ATOMIC_COUNT)
 570         {
 571           ns->data->atomics[ns->data->count].value = 0;
 572           memcpy(ns->data->atomics[ns->data->count].name,
 573                  name,
 574                  len+1);
 575
 576           return_atomic(atomic, ns, ns->data->count);
 577           ++ns->data->count;
 578         }
 579         else
 580           error = svn_error_create(SVN_ERR_BAD_ATOMIC, 0,
 581                                   _("Out of slots for named atomic."));
 582     }
 583
 584   /* We are mainly done here.  Let others continue their work.
 585    */
 586   SVN_ERR(unlock(&ns->mutex, error));
 587
 588   /* Only now can we be sure that a full memory barrier has been set
 589    * and that the new entry has been written to memory in full.
 590    */
 591   svn_atomic_set(&ns->min_used, ns->data->count);
 592
 593   return SVN_NO_ERROR;
 594 }
 595
 596 svn_error_t *
 597 svn_named_atomic__read(apr_int64_t *value,
 598                        svn_named_atomic__t *atomic)
 599 {
 600   SVN_ERR(validate(atomic));
 601   NA_SYNCHRONIZE(atomic, *value = synched_read(&atomic->data->value));
 602
 603   return SVN_NO_ERROR;
 604 }
 605
 606 svn_error_t *
 607 svn_named_atomic__write(apr_int64_t *old_value,
 608                         apr_int64_t new_value,
 609                         svn_named_atomic__t *atomic)
 610 {
 611   apr_int64_t temp;
 612
 613   SVN_ERR(validate(atomic));
 614   NA_SYNCHRONIZE(atomic, temp = synched_write(&atomic->data->value, new_value));
 615
 616   if (old_value)
 617     *old_value = temp;
 618
 619   return SVN_NO_ERROR;
 620 }
 621
 622 svn_error_t *
 623 svn_named_atomic__add(apr_int64_t *new_value,
 624                       apr_int64_t delta,
 625                       svn_named_atomic__t *atomic)
 626 {
 627   apr_int64_t temp;
 628
 629   SVN_ERR(validate(atomic));
 630   NA_SYNCHRONIZE(atomic, temp = synched_add(&atomic->data->value, delta));
 631
 632   if (new_value)
 633     *new_value = temp;
 634
 635   return SVN_NO_ERROR;
 636 }
 637
 638 svn_error_t *
 639 svn_named_atomic__cmpxchg(apr_int64_t *old_value,
 640                           apr_int64_t new_value,
 641                           apr_int64_t comperand,
 642                           svn_named_atomic__t *atomic)
 643 {
 644   apr_int64_t temp;
 645
 646   SVN_ERR(validate(atomic));
 647   NA_SYNCHRONIZE(atomic, temp = synched_cmpxchg(&atomic->data->value,
 648                                                 new_value,
 649                                                 comperand));
 650
 651   if (old_value)
 652     *old_value = temp;
 653
 654   return SVN_NO_ERROR;
 655 }