]> CyberLeo.Net >> Repos - FreeBSD/releng/10.0.git/blob - contrib/subversion/subversion/libsvn_subr/named_atomic.c
- Copy stable/10 (r259064) to releng/10.0 as part of the
[FreeBSD/releng/10.0.git] / contrib / subversion / 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 #if APR_HAS_MMAP
255 /* Initialization flag for the above used by svn_atomic__init_once.
256  */
257 static volatile svn_atomic_t mutex_initialized = FALSE;
258
259 /* Initialize the thread sync. structures.
260  * To be called by svn_atomic__init_once.
261  */
262 static svn_error_t *
263 init_thread_mutex(void *baton, apr_pool_t *pool)
264 {
265   /* let the mutex live as long as the APR */
266   apr_pool_t *global_pool = svn_pool_create(NULL);
267
268   return svn_mutex__init(&thread_mutex, USE_THREAD_MUTEX, global_pool);
269 }
270 #endif /* APR_HAS_MMAP */
271
272 /* Utility that acquires our global mutex and converts error types.
273  */
274 static svn_error_t *
275 lock(struct mutex_t *mutex)
276 {
277   svn_error_t *err;
278
279   /* Get lock on the filehandle. */
280   SVN_ERR(svn_mutex__lock(thread_mutex));
281   err = svn_io_lock_open_file(mutex->lock_file, TRUE, FALSE, mutex->pool);
282
283   return err
284     ? svn_mutex__unlock(thread_mutex, err)
285     : err;
286 }
287
288 /* Utility that releases the lock previously acquired via lock().  If the
289  * unlock succeeds and OUTER_ERR is not NULL, OUTER_ERR will be returned.
290  * Otherwise, return the result of the unlock operation.
291  */
292 static svn_error_t *
293 unlock(struct mutex_t *mutex, svn_error_t * outer_err)
294 {
295   svn_error_t *unlock_err
296       = svn_io_unlock_open_file(mutex->lock_file, mutex->pool);
297   return svn_mutex__unlock(thread_mutex,
298                            svn_error_compose_create(outer_err,
299                                                     unlock_err));
300 }
301
302 #if APR_HAS_MMAP
303 /* The last user to close a particular namespace should also remove the
304  * lock file.  Failure to do so, however, does not affect further uses
305  * of the same namespace.
306  */
307 static apr_status_t
308 delete_lock_file(void *arg)
309 {
310   struct mutex_t *mutex = arg;
311   const char *lock_name = NULL;
312
313   /* locks have already been cleaned up. Simply close the file */
314   apr_status_t status = apr_file_close(mutex->lock_file);
315
316   /* Remove the file from disk. This will fail if there ares still other
317    * users of this lock file, i.e. namespace. */
318   apr_file_name_get(&lock_name, mutex->lock_file);
319   if (lock_name)
320     apr_file_remove(lock_name, mutex->pool);
321
322   return status;
323 }
324 #endif /* APR_HAS_MMAP */
325
326 /* Validate the ATOMIC parameter, i.e it's address.  Correct code will
327  * never need this but if someone should accidentally to use a NULL or
328  * incomplete structure, let's catch that here instead of segfaulting.
329  */
330 static svn_error_t *
331 validate(svn_named_atomic__t *atomic)
332 {
333   return atomic && atomic->data && atomic->mutex
334     ? SVN_NO_ERROR
335     : svn_error_create(SVN_ERR_BAD_ATOMIC, 0, _("Not a valid atomic"));
336 }
337
338 /* Auto-initialize and return in *ATOMIC the API-level object for the
339  * atomic with index I within NS. */
340 static void
341 return_atomic(svn_named_atomic__t **atomic,
342               svn_atomic_namespace__t *ns,
343               int i)
344 {
345   *atomic = &ns->atomics[i];
346   if (ns->atomics[i].data == NULL)
347     {
348       (*atomic)->mutex = &ns->mutex;
349       (*atomic)->data = &ns->data->atomics[i];
350     }
351 }
352
353 /* Implement API */
354
355 svn_boolean_t
356 svn_named_atomic__is_supported(void)
357 {
358 #if !APR_HAS_MMAP
359   return FALSE;
360 #elif !defined(_WIN32)
361   return TRUE;
362 #else
363   static svn_tristate_t result = svn_tristate_unknown;
364
365   if (result == svn_tristate_unknown)
366     {
367       /* APR SHM implementation requires the creation of global objects */
368       HANDLE handle = CreateFileMappingA(INVALID_HANDLE_VALUE,
369                                          NULL,
370                                          PAGE_READONLY,
371                                          0,
372                                          1,
373                                          "Global\\__RandomXZY_svn");
374       if (handle != NULL)
375         {
376           CloseHandle(handle);
377           result = svn_tristate_true;
378         }
379       else
380         result = svn_tristate_false;
381     }
382
383   return result == svn_tristate_true;
384 #endif /* _WIN32 */
385 }
386
387 svn_boolean_t
388 svn_named_atomic__is_efficient(void)
389 {
390   return NA_SYNCHRONIZE_IS_FAST;
391 }
392
393 svn_error_t *
394 svn_atomic_namespace__create(svn_atomic_namespace__t **ns,
395                              const char *name,
396                              apr_pool_t *result_pool)
397 {
398 #if !APR_HAS_MMAP
399   return svn_error_create(APR_ENOTIMPL, NULL, NULL);
400 #else
401   apr_status_t apr_err;
402   svn_error_t *err;
403   apr_file_t *file;
404   apr_mmap_t *mmap;
405   const char *shm_name, *lock_name;
406   apr_finfo_t finfo;
407
408   apr_pool_t *subpool = svn_pool_create(result_pool);
409
410   /* allocate the namespace data structure
411    */
412   svn_atomic_namespace__t *new_ns = apr_pcalloc(result_pool, sizeof(**ns));
413
414   /* construct the names of the system objects that we need
415    */
416   shm_name = apr_pstrcat(subpool, name, SHM_NAME_SUFFIX, NULL);
417   lock_name = apr_pstrcat(subpool, name, MUTEX_NAME_SUFFIX, NULL);
418
419   /* initialize the lock objects
420    */
421   SVN_ERR(svn_atomic__init_once(&mutex_initialized, init_thread_mutex, NULL,
422                                 result_pool));
423
424   new_ns->mutex.pool = result_pool;
425   SVN_ERR(svn_io_file_open(&new_ns->mutex.lock_file, lock_name,
426                            APR_READ | APR_WRITE | APR_CREATE,
427                            APR_OS_DEFAULT,
428                            result_pool));
429
430   /* Make sure the last user of our lock file will actually remove it.
431    * Please note that only the last file handle begin closed will actually
432    * remove the underlying file (see docstring for apr_file_remove).
433    */
434   apr_pool_cleanup_register(result_pool, &new_ns->mutex,
435                             delete_lock_file,
436                             apr_pool_cleanup_null);
437
438   /* Prevent concurrent initialization.
439    */
440   SVN_ERR(lock(&new_ns->mutex));
441
442   /* First, make sure that the underlying file exists.  If it doesn't
443    * exist, create one and initialize its content.
444    */
445   err = svn_io_file_open(&file, shm_name,
446                           APR_READ | APR_WRITE | APR_CREATE,
447                           APR_OS_DEFAULT,
448                           result_pool);
449   if (!err)
450     {
451       err = svn_io_stat(&finfo, shm_name, APR_FINFO_SIZE, subpool);
452       if (!err && finfo.size < sizeof(struct shared_data_t))
453         {
454            /* Zero all counters, values and names.
455             */
456            struct shared_data_t initial_data;
457            memset(&initial_data, 0, sizeof(initial_data));
458            err = svn_io_file_write_full(file, &initial_data,
459                                         sizeof(initial_data), NULL,
460                                         subpool);
461         }
462     }
463
464   /* Now, map it into memory.
465    */
466   if (!err)
467     {
468       apr_err = apr_mmap_create(&mmap, file, 0, sizeof(*new_ns->data),
469                                 APR_MMAP_READ | APR_MMAP_WRITE , result_pool);
470       if (!apr_err)
471         new_ns->data = mmap->mm;
472       else
473         err = svn_error_createf(apr_err, NULL,
474                                 _("MMAP failed for file '%s'"), shm_name);
475     }
476
477   svn_pool_destroy(subpool);
478
479   if (!err && new_ns->data)
480     {
481       /* Detect severe cases of corruption (i.e. when some outsider messed
482        * with our data file)
483        */
484       if (new_ns->data->count > MAX_ATOMIC_COUNT)
485         return svn_error_create(SVN_ERR_CORRUPTED_ATOMIC_STORAGE, 0,
486                        _("Number of atomics in namespace is too large."));
487
488       /* Cache the number of existing, complete entries.  There can't be
489        * incomplete ones from other processes because we hold the mutex.
490        * Our process will also not access this information since we are
491        * either being called from within svn_atomic__init_once or by
492        * svn_atomic_namespace__create for a new object.
493        */
494       new_ns->min_used = new_ns->data->count;
495       *ns = new_ns;
496     }
497
498   /* Unlock to allow other processes may access the shared memory as well.
499    */
500   return unlock(&new_ns->mutex, err);
501 #endif /* APR_HAS_MMAP */
502 }
503
504 svn_error_t *
505 svn_atomic_namespace__cleanup(const char *name,
506                               apr_pool_t *pool)
507 {
508   const char *shm_name, *lock_name;
509
510   /* file names used for the specified namespace */
511   shm_name = apr_pstrcat(pool, name, SHM_NAME_SUFFIX, NULL);
512   lock_name = apr_pstrcat(pool, name, MUTEX_NAME_SUFFIX, NULL);
513
514   /* remove these files if they exist */
515   SVN_ERR(svn_io_remove_file2(shm_name, TRUE, pool));
516   SVN_ERR(svn_io_remove_file2(lock_name, TRUE, pool));
517
518   return SVN_NO_ERROR;
519 }
520
521 svn_error_t *
522 svn_named_atomic__get(svn_named_atomic__t **atomic,
523                       svn_atomic_namespace__t *ns,
524                       const char *name,
525                       svn_boolean_t auto_create)
526 {
527   apr_uint32_t i, count;
528   svn_error_t *error = SVN_NO_ERROR;
529   apr_size_t len = strlen(name);
530
531   /* Check parameters and make sure we return a NULL atomic
532    * in case of failure.
533    */
534   *atomic = NULL;
535   if (len > SVN_NAMED_ATOMIC__MAX_NAME_LENGTH)
536     return svn_error_create(SVN_ERR_BAD_ATOMIC, 0,
537                             _("Atomic's name is too long."));
538
539   /* If no namespace has been provided, bail out.
540    */
541   if (ns == NULL || ns->data == NULL)
542     return svn_error_create(SVN_ERR_BAD_ATOMIC, 0,
543                             _("Namespace has not been initialized."));
544
545   /* Optimistic lookup.
546    * Because we never change the name of existing atomics and may only
547    * append new ones, we can safely compare the name of existing ones
548    * with the name that we are looking for.
549    */
550   for (i = 0, count = svn_atomic_read(&ns->min_used); i < count; ++i)
551     if (strncmp(ns->data->atomics[i].name, name, len + 1) == 0)
552       {
553         return_atomic(atomic, ns, i);
554         return SVN_NO_ERROR;
555       }
556
557   /* Try harder:
558    * Serialize all lookup and insert the item, if necessary and allowed.
559    */
560   SVN_ERR(lock(&ns->mutex));
561
562   /* We only need to check for new entries.
563    */
564   for (i = count; i < ns->data->count; ++i)
565     if (strncmp(ns->data->atomics[i].name, name, len + 1) == 0)
566       {
567         return_atomic(atomic, ns, i);
568
569         /* Update our cached number of complete entries. */
570         svn_atomic_set(&ns->min_used, ns->data->count);
571
572         return unlock(&ns->mutex, error);
573       }
574
575   /* Not found.  Append a new entry, if allowed & possible.
576    */
577   if (auto_create)
578     {
579       if (ns->data->count < MAX_ATOMIC_COUNT)
580         {
581           ns->data->atomics[ns->data->count].value = 0;
582           memcpy(ns->data->atomics[ns->data->count].name,
583                  name,
584                  len+1);
585
586           return_atomic(atomic, ns, ns->data->count);
587           ++ns->data->count;
588         }
589         else
590           error = svn_error_create(SVN_ERR_BAD_ATOMIC, 0,
591                                   _("Out of slots for named atomic."));
592     }
593
594   /* We are mainly done here.  Let others continue their work.
595    */
596   SVN_ERR(unlock(&ns->mutex, error));
597
598   /* Only now can we be sure that a full memory barrier has been set
599    * and that the new entry has been written to memory in full.
600    */
601   svn_atomic_set(&ns->min_used, ns->data->count);
602
603   return SVN_NO_ERROR;
604 }
605
606 svn_error_t *
607 svn_named_atomic__read(apr_int64_t *value,
608                        svn_named_atomic__t *atomic)
609 {
610   SVN_ERR(validate(atomic));
611   NA_SYNCHRONIZE(atomic, *value = synched_read(&atomic->data->value));
612
613   return SVN_NO_ERROR;
614 }
615
616 svn_error_t *
617 svn_named_atomic__write(apr_int64_t *old_value,
618                         apr_int64_t new_value,
619                         svn_named_atomic__t *atomic)
620 {
621   apr_int64_t temp;
622
623   SVN_ERR(validate(atomic));
624   NA_SYNCHRONIZE(atomic, temp = synched_write(&atomic->data->value, new_value));
625
626   if (old_value)
627     *old_value = temp;
628
629   return SVN_NO_ERROR;
630 }
631
632 svn_error_t *
633 svn_named_atomic__add(apr_int64_t *new_value,
634                       apr_int64_t delta,
635                       svn_named_atomic__t *atomic)
636 {
637   apr_int64_t temp;
638
639   SVN_ERR(validate(atomic));
640   NA_SYNCHRONIZE(atomic, temp = synched_add(&atomic->data->value, delta));
641
642   if (new_value)
643     *new_value = temp;
644
645   return SVN_NO_ERROR;
646 }
647
648 svn_error_t *
649 svn_named_atomic__cmpxchg(apr_int64_t *old_value,
650                           apr_int64_t new_value,
651                           apr_int64_t comperand,
652                           svn_named_atomic__t *atomic)
653 {
654   apr_int64_t temp;
655
656   SVN_ERR(validate(atomic));
657   NA_SYNCHRONIZE(atomic, temp = synched_cmpxchg(&atomic->data->value,
658                                                 new_value,
659                                                 comperand));
660
661   if (old_value)
662     *old_value = temp;
663
664   return SVN_NO_ERROR;
665 }