1// Ceres Solver - A fast non-linear least squares minimizer 2// Copyright 2010, 2011, 2012 Google Inc. All rights reserved. 3// http://code.google.com/p/ceres-solver/ 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 Google Inc. nor the names of its contributors may be 14// used to endorse or promote products derived from this software without 15// 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 OWNER 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// Author: Craig Silverstein. 30// 31// A simple mutex wrapper, supporting locks and read-write locks. 32// You should assume the locks are *not* re-entrant. 33// 34// This class is meant to be internal-only and should be wrapped by an 35// internal namespace. Before you use this module, please give the 36// name of your internal namespace for this module. Or, if you want 37// to expose it, you'll want to move it to the Google namespace. We 38// cannot put this class in global namespace because there can be some 39// problems when we have multiple versions of Mutex in each shared object. 40// 41// NOTE: by default, we have #ifdef'ed out the TryLock() method. 42// This is for two reasons: 43// 1) TryLock() under Windows is a bit annoying (it requires a 44// #define to be defined very early). 45// 2) TryLock() is broken for NO_THREADS mode, at least in NDEBUG 46// mode. 47// If you need TryLock(), and either these two caveats are not a 48// problem for you, or you're willing to work around them, then 49// feel free to #define GMUTEX_TRYLOCK, or to remove the #ifdefs 50// in the code below. 51// 52// CYGWIN NOTE: Cygwin support for rwlock seems to be buggy: 53// http://www.cygwin.com/ml/cygwin/2008-12/msg00017.html 54// Because of that, we might as well use windows locks for 55// cygwin. They seem to be more reliable than the cygwin pthreads layer. 56// 57// TRICKY IMPLEMENTATION NOTE: 58// This class is designed to be safe to use during 59// dynamic-initialization -- that is, by global constructors that are 60// run before main() starts. The issue in this case is that 61// dynamic-initialization happens in an unpredictable order, and it 62// could be that someone else's dynamic initializer could call a 63// function that tries to acquire this mutex -- but that all happens 64// before this mutex's constructor has run. (This can happen even if 65// the mutex and the function that uses the mutex are in the same .cc 66// file.) Basically, because Mutex does non-trivial work in its 67// constructor, it's not, in the naive implementation, safe to use 68// before dynamic initialization has run on it. 69// 70// The solution used here is to pair the actual mutex primitive with a 71// bool that is set to true when the mutex is dynamically initialized. 72// (Before that it's false.) Then we modify all mutex routines to 73// look at the bool, and not try to lock/unlock until the bool makes 74// it to true (which happens after the Mutex constructor has run.) 75// 76// This works because before main() starts -- particularly, during 77// dynamic initialization -- there are no threads, so a) it's ok that 78// the mutex operations are a no-op, since we don't need locking then 79// anyway; and b) we can be quite confident our bool won't change 80// state between a call to Lock() and a call to Unlock() (that would 81// require a global constructor in one translation unit to call Lock() 82// and another global constructor in another translation unit to call 83// Unlock() later, which is pretty perverse). 84// 85// That said, it's tricky, and can conceivably fail; it's safest to 86// avoid trying to acquire a mutex in a global constructor, if you 87// can. One way it can fail is that a really smart compiler might 88// initialize the bool to true at static-initialization time (too 89// early) rather than at dynamic-initialization time. To discourage 90// that, we set is_safe_ to true in code (not the constructor 91// colon-initializer) and set it to true via a function that always 92// evaluates to true, but that the compiler can't know always 93// evaluates to true. This should be good enough. 94 95#ifndef CERES_INTERNAL_MUTEX_H_ 96#define CERES_INTERNAL_MUTEX_H_ 97 98#if defined(CERES_NO_THREADS) 99 typedef int MutexType; // to keep a lock-count 100#elif defined(_WIN32) || defined(__CYGWIN32__) || defined(__CYGWIN64__) 101# define CERES_WIN32_LEAN_AND_MEAN // We only need minimal includes 102# ifdef CERES_GMUTEX_TRYLOCK 103 // We need Windows NT or later for TryEnterCriticalSection(). If you 104 // don't need that functionality, you can remove these _WIN32_WINNT 105 // lines, and change TryLock() to assert(0) or something. 106# ifndef _WIN32_WINNT 107# define _WIN32_WINNT 0x0400 108# endif 109# endif 110// Unfortunately, windows.h defines a bunch of macros with common 111// names. Two in particular need avoiding: ERROR and min/max. 112// To avoid macro definition of ERROR. 113# define NOGDI 114// To avoid macro definition of min/max. 115# define NOMINMAX 116# include <windows.h> 117 typedef CRITICAL_SECTION MutexType; 118#elif defined(CERES_HAVE_PTHREAD) && defined(CERES_HAVE_RWLOCK) 119 // Needed for pthread_rwlock_*. If it causes problems, you could take it 120 // out, but then you'd have to unset CERES_HAVE_RWLOCK (at least on linux -- 121 // it *does* cause problems for FreeBSD, or MacOSX, but isn't needed for 122 // locking there.) 123# if defined(__linux__) && !defined(_XOPEN_SOURCE) 124# define _XOPEN_SOURCE 500 // may be needed to get the rwlock calls 125# endif 126# include <pthread.h> 127 typedef pthread_rwlock_t MutexType; 128#elif defined(CERES_HAVE_PTHREAD) 129# include <pthread.h> 130 typedef pthread_mutex_t MutexType; 131#else 132# error Need to implement mutex.h for your architecture, or #define NO_THREADS 133#endif 134 135// We need to include these header files after defining _XOPEN_SOURCE 136// as they may define the _XOPEN_SOURCE macro. 137#include <assert.h> 138#include <stdlib.h> // for abort() 139 140namespace ceres { 141namespace internal { 142 143class Mutex { 144 public: 145 // Create a Mutex that is not held by anybody. This constructor is 146 // typically used for Mutexes allocated on the heap or the stack. 147 // See below for a recommendation for constructing global Mutex 148 // objects. 149 inline Mutex(); 150 151 // Destructor 152 inline ~Mutex(); 153 154 inline void Lock(); // Block if needed until free then acquire exclusively 155 inline void Unlock(); // Release a lock acquired via Lock() 156#ifdef CERES_GMUTEX_TRYLOCK 157 inline bool TryLock(); // If free, Lock() and return true, else return false 158#endif 159 // Note that on systems that don't support read-write locks, these may 160 // be implemented as synonyms to Lock() and Unlock(). So you can use 161 // these for efficiency, but don't use them anyplace where being able 162 // to do shared reads is necessary to avoid deadlock. 163 inline void ReaderLock(); // Block until free or shared then acquire a share 164 inline void ReaderUnlock(); // Release a read share of this Mutex 165 inline void WriterLock() { Lock(); } // Acquire an exclusive lock 166 inline void WriterUnlock() { Unlock(); } // Release a lock from WriterLock() 167 168 // TODO(hamaji): Do nothing, implement correctly. 169 inline void AssertHeld() {} 170 171 private: 172 MutexType mutex_; 173 // We want to make sure that the compiler sets is_safe_ to true only 174 // when we tell it to, and never makes assumptions is_safe_ is 175 // always true. volatile is the most reliable way to do that. 176 volatile bool is_safe_; 177 178 inline void SetIsSafe() { is_safe_ = true; } 179 180 // Catch the error of writing Mutex when intending MutexLock. 181 Mutex(Mutex* /*ignored*/) {} 182 // Disallow "evil" constructors 183 Mutex(const Mutex&); 184 void operator=(const Mutex&); 185}; 186 187// Now the implementation of Mutex for various systems 188#if defined(CERES_NO_THREADS) 189 190// When we don't have threads, we can be either reading or writing, 191// but not both. We can have lots of readers at once (in no-threads 192// mode, that's most likely to happen in recursive function calls), 193// but only one writer. We represent this by having mutex_ be -1 when 194// writing and a number > 0 when reading (and 0 when no lock is held). 195// 196// In debug mode, we assert these invariants, while in non-debug mode 197// we do nothing, for efficiency. That's why everything is in an 198// assert. 199 200Mutex::Mutex() : mutex_(0) { } 201Mutex::~Mutex() { assert(mutex_ == 0); } 202void Mutex::Lock() { assert(--mutex_ == -1); } 203void Mutex::Unlock() { assert(mutex_++ == -1); } 204#ifdef CERES_GMUTEX_TRYLOCK 205bool Mutex::TryLock() { if (mutex_) return false; Lock(); return true; } 206#endif 207void Mutex::ReaderLock() { assert(++mutex_ > 0); } 208void Mutex::ReaderUnlock() { assert(mutex_-- > 0); } 209 210#elif defined(_WIN32) || defined(__CYGWIN32__) || defined(__CYGWIN64__) 211 212Mutex::Mutex() { InitializeCriticalSection(&mutex_); SetIsSafe(); } 213Mutex::~Mutex() { DeleteCriticalSection(&mutex_); } 214void Mutex::Lock() { if (is_safe_) EnterCriticalSection(&mutex_); } 215void Mutex::Unlock() { if (is_safe_) LeaveCriticalSection(&mutex_); } 216#ifdef GMUTEX_TRYLOCK 217bool Mutex::TryLock() { return is_safe_ ? 218 TryEnterCriticalSection(&mutex_) != 0 : true; } 219#endif 220void Mutex::ReaderLock() { Lock(); } // we don't have read-write locks 221void Mutex::ReaderUnlock() { Unlock(); } 222 223#elif defined(CERES_HAVE_PTHREAD) && defined(CERES_HAVE_RWLOCK) 224 225#define CERES_SAFE_PTHREAD(fncall) do { /* run fncall if is_safe_ is true */ \ 226 if (is_safe_ && fncall(&mutex_) != 0) abort(); \ 227} while (0) 228 229Mutex::Mutex() { 230 SetIsSafe(); 231 if (is_safe_ && pthread_rwlock_init(&mutex_, NULL) != 0) abort(); 232} 233Mutex::~Mutex() { CERES_SAFE_PTHREAD(pthread_rwlock_destroy); } 234void Mutex::Lock() { CERES_SAFE_PTHREAD(pthread_rwlock_wrlock); } 235void Mutex::Unlock() { CERES_SAFE_PTHREAD(pthread_rwlock_unlock); } 236#ifdef CERES_GMUTEX_TRYLOCK 237bool Mutex::TryLock() { return is_safe_ ? 238 pthread_rwlock_trywrlock(&mutex_) == 0 : 239 true; } 240#endif 241void Mutex::ReaderLock() { CERES_SAFE_PTHREAD(pthread_rwlock_rdlock); } 242void Mutex::ReaderUnlock() { CERES_SAFE_PTHREAD(pthread_rwlock_unlock); } 243#undef CERES_SAFE_PTHREAD 244 245#elif defined(CERES_HAVE_PTHREAD) 246 247#define CERES_SAFE_PTHREAD(fncall) do { /* run fncall if is_safe_ is true */ \ 248 if (is_safe_ && fncall(&mutex_) != 0) abort(); \ 249} while (0) 250 251Mutex::Mutex() { 252 SetIsSafe(); 253 if (is_safe_ && pthread_mutex_init(&mutex_, NULL) != 0) abort(); 254} 255Mutex::~Mutex() { CERES_SAFE_PTHREAD(pthread_mutex_destroy); } 256void Mutex::Lock() { CERES_SAFE_PTHREAD(pthread_mutex_lock); } 257void Mutex::Unlock() { CERES_SAFE_PTHREAD(pthread_mutex_unlock); } 258#ifdef CERES_GMUTEX_TRYLOCK 259bool Mutex::TryLock() { return is_safe_ ? 260 pthread_mutex_trylock(&mutex_) == 0 : true; } 261#endif 262void Mutex::ReaderLock() { Lock(); } 263void Mutex::ReaderUnlock() { Unlock(); } 264#undef CERES_SAFE_PTHREAD 265 266#endif 267 268// -------------------------------------------------------------------------- 269// Some helper classes 270 271// Note: The weird "Ceres" prefix for the class is a workaround for having two 272// similar mutex.h files included in the same translation unit. This is a 273// problem because macros do not respect C++ namespaces, and as a result, this 274// does not work well (e.g. inside Chrome). The offending macros are 275// "MutexLock(x) COMPILE_ASSERT(false)". To work around this, "Ceres" is 276// prefixed to the class names; this permits defining the classes. 277 278// CeresMutexLock(mu) acquires mu when constructed and releases it 279// when destroyed. 280class CeresMutexLock { 281 public: 282 explicit CeresMutexLock(Mutex *mu) : mu_(mu) { mu_->Lock(); } 283 ~CeresMutexLock() { mu_->Unlock(); } 284 private: 285 Mutex * const mu_; 286 // Disallow "evil" constructors 287 CeresMutexLock(const CeresMutexLock&); 288 void operator=(const CeresMutexLock&); 289}; 290 291// CeresReaderMutexLock and CeresWriterMutexLock do the same, for rwlocks 292class CeresReaderMutexLock { 293 public: 294 explicit CeresReaderMutexLock(Mutex *mu) : mu_(mu) { mu_->ReaderLock(); } 295 ~CeresReaderMutexLock() { mu_->ReaderUnlock(); } 296 private: 297 Mutex * const mu_; 298 // Disallow "evil" constructors 299 CeresReaderMutexLock(const CeresReaderMutexLock&); 300 void operator=(const CeresReaderMutexLock&); 301}; 302 303class CeresWriterMutexLock { 304 public: 305 explicit CeresWriterMutexLock(Mutex *mu) : mu_(mu) { mu_->WriterLock(); } 306 ~CeresWriterMutexLock() { mu_->WriterUnlock(); } 307 private: 308 Mutex * const mu_; 309 // Disallow "evil" constructors 310 CeresWriterMutexLock(const CeresWriterMutexLock&); 311 void operator=(const CeresWriterMutexLock&); 312}; 313 314// Catch bug where variable name is omitted, e.g. MutexLock (&mu); 315#define CeresMutexLock(x) \ 316 COMPILE_ASSERT(0, ceres_mutex_lock_decl_missing_var_name) 317#define CeresReaderMutexLock(x) \ 318 COMPILE_ASSERT(0, ceres_rmutex_lock_decl_missing_var_name) 319#define CeresWriterMutexLock(x) \ 320 COMPILE_ASSERT(0, ceres_wmutex_lock_decl_missing_var_name) 321 322} // namespace internal 323} // namespace ceres 324 325#endif // CERES_INTERNAL_MUTEX_H_ 326