Geogram Version 1.8.5
A programming library of geometric algorithms
Loading...
Searching...
No Matches
thread_sync.h
Go to the documentation of this file.
1/*
2 * Copyright (c) 2000-2022 Inria
3 * All rights reserved.
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions are met:
7 *
8 * * Redistributions of source code must retain the above copyright notice,
9 * this list of conditions and the following disclaimer.
10 * * Redistributions in binary form must reproduce the above copyright notice,
11 * this list of conditions and the following disclaimer in the documentation
12 * and/or other materials provided with the distribution.
13 * * Neither the name of the ALICE Project-Team nor the names of its
14 * contributors may be used to endorse or promote products derived from this
15 * software without specific prior written permission.
16 *
17 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
18 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
19 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
20 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
21 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
22 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
23 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
24 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
25 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
26 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
27 * POSSIBILITY OF SUCH DAMAGE.
28 *
29 * Contact: Bruno Levy
30 *
31 * https://www.inria.fr/fr/bruno-levy
32 *
33 * Inria,
34 * Domaine de Voluceau,
35 * 78150 Le Chesnay - Rocquencourt
36 * FRANCE
37 *
38 */
39
40#ifndef GEOGRAM_BASIC_THREAD_SYNC
41#define GEOGRAM_BASIC_THREAD_SYNC
42
48#include <vector>
49
50#ifdef GEO_OS_APPLE
51# define GEO_USE_DEFAULT_SPINLOCK_ARRAY
52# include <AvailabilityMacros.h>
53# if defined(MAC_OS_X_VERSION_10_12) && MAC_OS_X_VERSION_MIN_REQUIRED >= MAC_OS_X_VERSION_10_12
54# define GEO_APPLE_HAS_UNFAIR_LOCK 1
55# include <os/lock.h>
56# endif
57# if defined(__IPHONE_OS_VERSION_MIN_REQUIRED) && __IPHONE_OS_VERSION_MIN_REQUIRED >= __IPHONE_10_0
58# define GEO_APPLE_HAS_UNFAIR_LOCK 1
59# include <os/lock.h>
60# endif
61#endif
62
63#ifdef geo_debug_assert
64#define geo_thread_sync_assert(x) geo_debug_assert(x)
65#else
66#define geo_thread_sync_assert(x)
67#endif
68
74namespace GEO {
75
76 namespace Process {
77
78#if defined(GEO_OS_RASPBERRY)
79
81 typedef arm32_mutex_t spinlock;
82
84# define GEOGRAM_SPINLOCK_INIT 0
89 inline void acquire_spinlock(spinlock& x) {
90 lock_mutex_arm32(&x);
91 }
92
97 inline void release_spinlock(spinlock& x) {
98 unlock_mutex_arm32(&x);
99 }
100
101#elif defined(GEO_OS_ANDROID)
102
104 typedef android_mutex_t spinlock;
105
107# define GEOGRAM_SPINLOCK_INIT 0
112 inline void acquire_spinlock(spinlock& x) {
113 lock_mutex_android(&x);
114 }
115
120 inline void release_spinlock(spinlock& x) {
121 unlock_mutex_android(&x);
122 }
123
124#elif defined(GEO_OS_LINUX) || defined(GEO_COMPILER_MINGW)
125
127 typedef unsigned char spinlock;
128
130# define GEOGRAM_SPINLOCK_INIT 0
135 inline void acquire_spinlock(volatile spinlock& x) {
136 while(__sync_lock_test_and_set(&x, 1) == 1) {
137 // Intel recommends to have a PAUSE asm instruction
138 // in the spinlock loop.
139 geo_pause();
140 }
141 }
142
147 inline void release_spinlock(volatile spinlock& x) {
148 // Note: Since on intel processor, memory writes
149 // (of data types <= bus size) are atomic, we could
150 // simply write 'x=0' instead, but this would
151 // lack the 'memory barrier with release semantics'
152 // required to avoid compiler and/or processor
153 // reordering (important for relaxed memory
154 // models such as Itanium processors).
155 __sync_lock_release(&x);
156 }
157
158#elif defined(GEO_OS_APPLE)
159
160#if defined(GEO_APPLE_HAS_UNFAIR_LOCK)
162 typedef os_unfair_lock spinlock;
163
165# define GEOGRAM_SPINLOCK_INIT OS_UNFAIR_LOCK_INIT
166 //inline void init_spinlock(spinlock & s) { s = OS_UNFAIR_LOCK_INIT; }
167 //inline bool try_acquire_spinlock (spinlock & s) { return os_unfair_lock_trylock(&s); }
168 inline void acquire_spinlock (spinlock & s) { os_unfair_lock_lock(&s); }
169 inline void release_spinlock (spinlock & s) { os_unfair_lock_unlock(&s); }
170#else
172 typedef OSSpinLock spinlock;
173
175# define GEOGRAM_SPINLOCK_INIT OS_SPINLOCK_INIT
176 inline void acquire_spinlock(volatile spinlock& x) {
177 OSSpinLockLock(&x);
178 }
179
180 inline void release_spinlock(volatile spinlock& x) {
181 OSSpinLockUnlock(&x);
182 }
183#endif // __MAC_10_12
184
185#elif defined(GEO_OS_WINDOWS) && !defined(GEO_COMPILER_MINGW)
186
188 typedef short spinlock;
189
191# define GEOGRAM_SPINLOCK_INIT 0
192 inline void acquire_spinlock(volatile spinlock& x) {
193 while(_InterlockedCompareExchange16(&x, 1, 0) == 1) {
194 // Intel recommends to have a PAUSE asm instruction
195 // in the spinlock loop. Under MSVC/Windows,
196 // YieldProcessor() is a macro that calls the
197 // (undocumented) _mm_pause() intrinsic function
198 // that generates a PAUSE opcode.
199 YieldProcessor();
200 }
201 // We do not need _ReadBarrier() here since
202 // _InterlockedCompareExchange16
203 // "acts as a full barrier in VC2005" according to the doc
204 }
205
206 inline void release_spinlock(volatile spinlock& x) {
207 _WriteBarrier(); // prevents compiler reordering
208 x = 0;
209 }
210
211#endif
212
213#if defined(GEO_USE_DEFAULT_SPINLOCK_ARRAY)
214
215 // TODO: implement memory-efficient version for
216 // MacOSX MacOSX does have atomic bit
217 // manipulation routines (OSAtomicTestAndSet()),
218 // and also has OSAtomicAnd32OrigBarrier() and
219 // OSAtomicOr32OrigBarrier() functions that can
220 // be used instead (Orig for 'return previous value'
221 // and Barrier for ('include a memory barrier').
222 // Android needs additional routines in atomics.h/atomics.cpp
223
234 class SpinLockArray {
235 public:
239 SpinLockArray() {
240 }
241
246 SpinLockArray(index_t size_in) {
247 resize(size_in);
248 }
249
255 void resize(index_t size_in) {
256 spinlocks_.assign(size_in, GEOGRAM_SPINLOCK_INIT);
257 }
258
262 void clear() {
263 spinlocks_.clear();
264 }
265
269 index_t size() const {
270 return index_t(spinlocks_.size());
271 }
272
279 void acquire_spinlock(index_t i) {
280 geo_thread_sync_assert(i < size());
281 GEO::Process::acquire_spinlock(spinlocks_[i]);
282 }
283
289 void release_spinlock(index_t i) {
290 geo_thread_sync_assert(i < size());
291 GEO::Process::release_spinlock(spinlocks_[i]);
292 }
293
294 private:
295 std::vector<spinlock> spinlocks_;
296 };
297
298#elif defined(GEO_OS_RASPBERRY)
299
308 class SpinLockArray {
309 public:
314 typedef Numeric::uint32 word_t;
315
319 SpinLockArray() : size_(0) {
320 }
321
326 SpinLockArray(index_t size_in) : size_(0) {
327 resize(size_in);
328 }
329
335 void resize(index_t size_in) {
336 if(size_ != size_in) {
337 size_ = size_in;
338 index_t nb_words = (size_ >> 5) + 1;
339 spinlocks_.assign(nb_words, 0);
340 }
341 }
342
346 index_t size() const {
347 return size_;
348 }
349
353 void clear() {
354 spinlocks_.clear();
355 }
356
363 void acquire_spinlock(index_t i) {
364 geo_thread_sync_assert(i < size());
365 index_t w = i >> 5;
366 word_t b = word_t(i & 31);
367 // Loop while previously stored value has its bit set.
368 while((atomic_bitset_arm32(&spinlocks_[w], b)) != 0) {
369 // If somebody else has the lock, sleep.
370 // It is important to sleep here, else atomic_bitset_xxx()
371 // keeps acquiring the exclusive monitor (even for testing)
372 // and this slows down everything.
373 wait_for_event_arm32();
374 }
375 memory_barrier_arm32();
376 }
377
383 void release_spinlock(index_t i) {
384 geo_thread_sync_assert(i < size());
385 memory_barrier_android();
386 index_t w = i >> 5;
387 word_t b = word_t(i & 31);
388 atomic_bitreset_arm32(&spinlocks_[w], b);
389 // Now wake up the other threads that started
390 // sleeping if they did not manage to acquire
391 // the lock.
392 send_event_arm32();
393 }
394
395 private:
396 std::vector<word_t> spinlocks_;
397 index_t size_;
398 };
399
400#elif defined(GEO_OS_ANDROID)
401
410 class SpinLockArray {
411 public:
416 typedef Numeric::uint32 word_t;
417
421 SpinLockArray() : size_(0) {
422 }
423
428 SpinLockArray(index_t size_in) : size_(0) {
429 resize(size_in);
430 }
431
437 void resize(index_t size_in) {
438 if(size_ != size_in) {
439 size_ = size_in;
440 index_t nb_words = (size_ >> 5) + 1;
441 spinlocks_.assign(nb_words, 0);
442 }
443 }
444
448 index_t size() const {
449 return size_;
450 }
451
455 void clear() {
456 spinlocks_.clear();
457 }
458
465 void acquire_spinlock(index_t i) {
466 geo_thread_sync_assert(i < size());
467 index_t w = i >> 5;
468 word_t b = word_t(i & 31);
469 // Loop while previously stored value has its bit set.
470 while((atomic_bitset_android(&spinlocks_[w], b)) != 0) {
471 // If somebody else has the lock, sleep.
472 // It is important to sleep here, else atomic_bitset_xxx()
473 // keeps acquiring the exclusive monitor (even for testing)
474 // and this slows down everything.
475 wait_for_event_android();
476 }
477 memory_barrier_android();
478 }
479
485 void release_spinlock(index_t i) {
486 geo_thread_sync_assert(i < size());
487 memory_barrier_android();
488 index_t w = i >> 5;
489 word_t b = word_t(i & 31);
490 atomic_bitreset_android(&spinlocks_[w], b);
491 // Now wake up the other threads that started
492 // sleeping if they did not manage to acquire
493 // the lock.
494 send_event_android();
495 }
496
497 private:
498 std::vector<word_t> spinlocks_;
499 index_t size_;
500 };
501
502#elif defined(GEO_OS_LINUX)
503
514 public:
520
524 SpinLockArray() : size_(0) {
525 }
526
531 SpinLockArray(index_t size_in) : size_(0) {
532 resize(size_in);
533 }
534
540 void resize(index_t size_in) {
541 if(size_ != size_in) {
542 size_ = size_in;
543 index_t nb_words = (size_ >> 5) + 1;
544 spinlocks_.assign(nb_words, 0);
545 }
546 }
547
551 index_t size() const {
552 return size_;
553 }
554
558 void clear() {
559 spinlocks_.clear();
560 }
561
569 geo_thread_sync_assert(i < size());
570 index_t w = i >> 5;
571 index_t b = i & 31;
572 while(atomic_bittestandset_x86(&spinlocks_[w], Numeric::uint32(b))) {
573 // Intel recommends to have a PAUSE asm instruction
574 // in the spinlock loop. It is generated using the
575 // following intrinsic function of GCC.
576 geo_pause();
577 }
578 }
579
586 geo_thread_sync_assert(i < size());
587 index_t w = i >> 5;
588 index_t b = i & 31;
589 // Note: we need here to use a synchronized bit reset
590 // since &= is not atomic.
592 }
593
594 private:
595 std::vector<word_t> spinlocks_;
596 index_t size_;
597 };
598
599#elif defined(GEO_OS_WINDOWS)
609 class SpinLockArray {
610 public:
618 typedef LONG word_t;
619
623 SpinLockArray() : size_(0) {
624 }
625
630 SpinLockArray(index_t size_in) : size_(0) {
631 resize(size_in);
632 }
633
639 void resize(index_t size_in) {
640 if(size_ != size_in) {
641 size_ = size_in;
642 index_t nb_words = (size_ >> 5) + 1;
643 spinlocks_.assign(nb_words, 0);
644 }
645 }
646
650 index_t size() const {
651 return size_;
652 }
653
657 void clear() {
658 spinlocks_.clear();
659 }
660
667 void acquire_spinlock(index_t i) {
668 geo_thread_sync_assert(i < size());
669 index_t w = i >> 5;
670 index_t b = i & 31;
671 while(_interlockedbittestandset((long *)(&spinlocks_[w]), long(b))) {
672 // Intel recommends to have a PAUSE asm instruction
673 // in the spinlock loop. Under MSVC/Windows,
674 // YieldProcessor() is a macro that calls the
675 // (undocumented) _mm_pause() intrinsic function
676 // that generates a PAUSE opcode.
677 YieldProcessor();
678 }
679 // We do not need here _ReadBarrier() since
680 // _interlockedbittestandset
681 // "acts as a full barrier in VC2005" according to the doc
682 }
683
689 void release_spinlock(index_t i) {
690 geo_thread_sync_assert(i < size());
691 index_t w = i >> 5;
692 index_t b = i & 31;
693 // Note1: we need here to use a synchronized bit reset
694 // since |= is not atomic.
695 // Note2: We do not need here _WriteBarrier() since
696 // _interlockedbittestandreset
697 // "acts as a full barrier in VC2005" according to the doc
698 _interlockedbittestandreset((long*)(&spinlocks_[w]), long(b));
699 }
700
701 private:
702 std::vector<word_t> spinlocks_;
703 index_t size_;
704 };
705
706#else
707
708#error Found no implementation of SpinLockArray
709
710#endif
711
712
713 }
714
715#ifdef GEO_OS_WINDOWS
716
717 // Emulation of pthread mutexes using Windows API
718
719 typedef CRITICAL_SECTION pthread_mutex_t;
720 typedef unsigned int pthread_mutexattr_t;
721
722 inline int pthread_mutex_lock(pthread_mutex_t *m) {
723 EnterCriticalSection(m);
724 return 0;
725 }
726
727 inline int pthread_mutex_unlock(pthread_mutex_t *m) {
728 LeaveCriticalSection(m);
729 return 0;
730 }
731
732 inline int pthread_mutex_trylock(pthread_mutex_t *m) {
733 return TryEnterCriticalSection(m) ? 0 : EBUSY;
734 }
735
736 inline int pthread_mutex_init(pthread_mutex_t *m, pthread_mutexattr_t *a) {
737 geo_argused(a);
738 InitializeCriticalSection(m);
739 return 0;
740 }
741
742 inline int pthread_mutex_destroy(pthread_mutex_t *m) {
743 DeleteCriticalSection(m);
744 return 0;
745 }
746
747
748 // Emulation of pthread condition variables using Windows API
749
750 typedef CONDITION_VARIABLE pthread_cond_t;
751 typedef unsigned int pthread_condattr_t;
752
753 inline int pthread_cond_init(pthread_cond_t *c, pthread_condattr_t *a) {
754 geo_argused(a);
755 InitializeConditionVariable(c);
756 return 0;
757 }
758
759 inline int pthread_cond_destroy(pthread_cond_t *c) {
760 geo_argused(c);
761 return 0;
762 }
763
764 inline int pthread_cond_broadcast(pthread_cond_t *c) {
765 WakeAllConditionVariable(c);
766 return 0;
767 }
768
769 inline int pthread_cond_wait(pthread_cond_t *c, pthread_mutex_t *m) {
770 SleepConditionVariableCS(c, m, INFINITE);
771 return 0;
772 }
773
774#endif
775
776}
777
778#endif
779
A function to suppress unused parameters compilation warnings.
Assertion checking mechanism.
Functions for atomic operations.
void geo_pause()
Issues a processor pause (INTEL only)
Definition atomics.h:243
char atomic_bittestandreset_x86(volatile unsigned int *ptr, unsigned int bit)
Atomically tests and resets a bit (INTEL only)
Definition atomics.h:298
char atomic_bittestandset_x86(volatile unsigned int *ptr, unsigned int bit)
Atomically tests and sets a bit (INTEL only)
Definition atomics.h:266
Common include file, providing basic definitions. Should be included before anything else by all head...
An array of light-weight synchronisation primitives (spinlocks).
void clear()
Resets size to 0 and clears all the memory.
void release_spinlock(index_t i)
Releases a spinlock at a given index.
index_t size() const
Gets the number of spinlocks in this array.
void acquire_spinlock(index_t i)
Acquires a spinlock at a given index.
Numeric::uint32 word_t
Internal representation of SpinLockArray elements.
void resize(index_t size_in)
Resizes a SpinLockArray.
SpinLockArray()
Constructs a new SpinLockArray of size 0.
SpinLockArray(index_t size_in)
Constructs a new SpinLockArray of size size_in.
uint32_t uint32
Definition numeric.h:96
int spinlock
Definition psm.h:125
Global Vorpaline namespace.
Definition algorithm.h:64
void geo_argused(const T &)
Suppresses compiler warnings about unused parameters.
Definition argused.h:60
geo_index_t index_t
The type for storing and manipulating indices.
Definition numeric.h:287
Types and functions for numbers manipulation.