folly/Synchronized.h

   1 /*
   2  * Copyright 2012 Facebook, Inc.
   3  *
   4  * Licensed under the Apache License, Version 2.0 (the "License");
   5  * you may not use this file except in compliance with the License.
   6  * You may obtain a copy of the License at
   7  *
   8  *   http://www.apache.org/licenses/LICENSE-2.0
   9  *
  10  * Unless required by applicable law or agreed to in writing, software
  11  * distributed under the License is distributed on an "AS IS" BASIS,
  12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  13  * See the License for the specific language governing permissions and
  14  * limitations under the License.
  15  */
  16
  17 /**
  18  * This module implements a Synchronized abstraction useful in
  19  * mutex-based concurrency.
  20  *
  21  * @author: Andrei Alexandrescu (andrei.alexandrescu@fb.com)
  22  */
  23
  24 #ifndef SYNCHRONIZED_H_
  25 #define SYNCHRONIZED_H_
  26
  27 #include <type_traits>
  28 #include <mutex>
  29 #include <boost/thread.hpp>
  30 #include "folly/Preprocessor.h"
  31 #include "folly/Traits.h"
  32
  33 namespace folly {
  34
  35 namespace detail {
  36 enum InternalDoNotUse {};
  37
  38 /**
  39  * Free function adaptors for std:: and boost::
  40  */
  41
  42 /**
  43  * Yields true iff T has .lock() and .unlock() member functions. This
  44  * is done by simply enumerating the mutexes with this interface in
  45  * std and boost.
  46  */
  47 template <class T>
  48 struct HasLockUnlock {
  49   enum { value = IsOneOf<T,
  50          std::mutex, std::recursive_mutex,
  51          std::timed_mutex, std::recursive_timed_mutex,
  52          boost::mutex, boost::recursive_mutex, boost::shared_mutex,
  53          boost::timed_mutex, boost::recursive_timed_mutex
  54          >::value };
  55 };
  56
  57 /**
  58  * Acquires a mutex for reading by calling .lock(). The exception is
  59  * boost::shared_mutex, which has a special read-lock primitive called
  60  * .lock_shared().
  61  */
  62 template <class T>
  63 typename std::enable_if<
  64   HasLockUnlock<T>::value && !std::is_same<T, boost::shared_mutex>::value>::type
  65 acquireRead(T& mutex) {
  66   mutex.lock();
  67 }
  68
  69 /**
  70  * Special case for boost::shared_mutex.
  71  */
  72 template <class T>
  73 typename std::enable_if<std::is_same<T, boost::shared_mutex>::value>::type
  74 acquireRead(T& mutex) {
  75   mutex.lock_shared();
  76 }
  77
  78 /**
  79  * Acquires a mutex for reading with timeout by calling .timed_lock(). This
  80  * applies to three of the boost mutex classes as enumerated below.
  81  */
  82 template <class T>
  83 typename std::enable_if<std::is_same<T, boost::shared_mutex>::value, bool>::type
  84 acquireRead(T& mutex,
  85             unsigned int milliseconds) {
  86   return mutex.timed_lock_shared(boost::posix_time::milliseconds(milliseconds));
  87 }
  88
  89 /**
  90  * Acquires a mutex for reading and writing by calling .lock().
  91  */
  92 template <class T>
  93 typename std::enable_if<HasLockUnlock<T>::value>::type
  94 acquireReadWrite(T& mutex) {
  95   mutex.lock();
  96 }
  97
  98 /**
  99  * Acquires a mutex for reading and writing with timeout by calling
 100  * .try_lock_for(). This applies to two of the std mutex classes as
 101  * enumerated below.
 102  */
 103 template <class T>
 104 typename std::enable_if<
 105   IsOneOf<T, std::timed_mutex, std::recursive_timed_mutex>::value, bool>::type
 106 acquireReadWrite(T& mutex,
 107                  unsigned int milliseconds) {
 108   return mutex.try_lock_for(std::chrono::milliseconds(milliseconds));
 109 }
 110
 111 /**
 112  * Acquires a mutex for reading and writing with timeout by calling
 113  * .timed_lock(). This applies to three of the boost mutex classes as
 114  * enumerated below.
 115  */
 116 template <class T>
 117 typename std::enable_if<
 118   IsOneOf<T, boost::shared_mutex, boost::timed_mutex,
 119           boost::recursive_timed_mutex>::value, bool>::type
 120 acquireReadWrite(T& mutex,
 121                  unsigned int milliseconds) {
 122   return mutex.timed_lock(boost::posix_time::milliseconds(milliseconds));
 123 }
 124
 125 /**
 126  * Releases a mutex previously acquired for reading by calling
 127  * .unlock(). The exception is boost::shared_mutex, which has a
 128  * special primitive called .unlock_shared().
 129  */
 130 template <class T>
 131 typename std::enable_if<
 132   HasLockUnlock<T>::value && !std::is_same<T, boost::shared_mutex>::value>::type
 133 releaseRead(T& mutex) {
 134   mutex.unlock();
 135 }
 136
 137 /**
 138  * Special case for boost::shared_mutex.
 139  */
 140 template <class T>
 141 typename std::enable_if<std::is_same<T, boost::shared_mutex>::value>::type
 142 releaseRead(T& mutex) {
 143   mutex.unlock_shared();
 144 }
 145
 146 /**
 147  * Releases a mutex previously acquired for reading-writing by calling
 148  * .unlock().
 149  */
 150 template <class T>
 151 typename std::enable_if<HasLockUnlock<T>::value>::type
 152 releaseReadWrite(T& mutex) {
 153   mutex.unlock();
 154 }
 155
 156 } // namespace detail
 157
 158 /**
 159  * Synchronized<T> encapsulates an object of type T (a "datum") paired
 160  * with a mutex. The only way to access the datum is while the mutex
 161  * is locked, and Synchronized makes it virtually impossible to do
 162  * otherwise. The code that would access the datum in unsafe ways
 163  * would look odd and convoluted, thus readily alerting the human
 164  * reviewer. In contrast, the code that uses Synchronized<T> correctly
 165  * looks simple and intuitive.
 166  *
 167  * The second parameter must be a mutex type. Supported mutexes are
 168  * std::mutex, std::recursive_mutex, std::timed_mutex,
 169  * std::recursive_timed_mutex, boost::mutex, boost::recursive_mutex,
 170  * boost::shared_mutex, boost::timed_mutex,
 171  * boost::recursive_timed_mutex, and the folly/RWSpinLock.h
 172  * classes.
 173  *
 174  * You may define Synchronized support by defining 4-6 primitives in
 175  * the same namespace as the mutex class (found via ADL).  The
 176  * primitives are: acquireRead, acquireReadWrite, releaseRead, and
 177  * releaseReadWrite. Two optional primitives for timout operations are
 178  * overloads of acquireRead and acquireReadWrite. For signatures,
 179  * refer to the namespace detail below, which implements the
 180  * primitives for mutexes in std and boost.
 181  */
 182 template <class T, class Mutex = boost::shared_mutex>
 183 struct Synchronized {
 184   /**
 185    * Default constructor leaves both members call their own default
 186    * constructor.
 187    */
 188   Synchronized() = default;
 189   /**
 190
 191    * Copy constructor copies the data (with locking the source and
 192    * all) but does NOT copy the mutex. Doing so would result in
 193    * deadlocks.
 194    */
 195   Synchronized(const Synchronized& rhs) {
 196     auto guard = rhs.operator->();
 197     datum_ = rhs.datum_;
 198   }
 199
 200   /**
 201    * Move constructor moves the data (with locking the source and all)
 202    * but does not move the mutex.
 203    */
 204   Synchronized(Synchronized&& rhs) {
 205     auto guard = rhs.operator->();
 206     datum_ = std::move(rhs.datum_);
 207   }
 208
 209   /**
 210    * Constructor taking a datum as argument copies it. There is no
 211    * need to lock the constructing object.
 212    */
 213   explicit Synchronized(const T& rhs) : datum_(rhs) {}
 214
 215   /**
 216    * Constructor taking a datum rvalue as argument moves it. Again,
 217    * there is no need to lock the constructing object.
 218    */
 219   explicit Synchronized(T && rhs) : datum_(std::move(rhs)) {}
 220
 221   /**
 222    * The canonical assignment operator only assigns the data, NOT the
 223    * mutex. It locks the two objects in ascending order of their
 224    * addresses.
 225    */
 226   Synchronized& operator=(const Synchronized& rhs) {
 227     if (this < *rhs) {
 228       auto guard1 = operator->();
 229       auto guard2 = rhs.operator->();
 230       datum_ = rhs.datum_;
 231     } else {
 232       auto guard1 = rhs.operator->();
 233       auto guard2 = operator->();
 234       datum_ = rhs.datum_;
 235     }
 236     return *this;
 237   }
 238
 239   /**
 240    * Lock object, assign datum.
 241    */
 242   Synchronized& operator=(const T& rhs) {
 243     auto guard = operator->();
 244     datum_ = rhs;
 245     return *this;
 246   }
 247
 248   /**
 249    * A LockedPtr lp keeps a modifiable (i.e. non-const)
 250    * Synchronized<T> object locked for the duration of lp's
 251    * existence. Because of this, you get to access the datum's methods
 252    * directly by using lp->fun().
 253    */
 254   struct LockedPtr {
 255     /**
 256      * Found no reason to leave this hanging.
 257      */
 258     LockedPtr() = delete;
 259
 260     /**
 261      * Takes a Synchronized and locks it.
 262      */
 263     explicit LockedPtr(Synchronized* parent) : parent_(parent) {
 264       acquire();
 265     }
 266
 267     /**
 268      * Takes a Synchronized and attempts to lock it for some
 269      * milliseconds. If not, the LockedPtr will be subsequently null.
 270      */
 271     LockedPtr(Synchronized* parent, unsigned int milliseconds) {
 272       using namespace detail;
 273       if (acquireReadWrite(parent->mutex_, milliseconds)) {
 274         parent_ = parent;
 275         return;
 276       }
 277       // Could not acquire the resource, pointer is null
 278       parent_ = NULL;
 279     }
 280
 281     /**
 282      * This is used ONLY inside SYNCHRONIZED_DUAL. It initializes
 283      * everything properly, but does not lock the parent because it
 284      * "knows" someone else will lock it. Please do not use.
 285      */
 286     LockedPtr(Synchronized* parent, detail::InternalDoNotUse)
 287         : parent_(parent) {
 288     }
 289
 290     /**
 291      * Copy ctor adds one lock.
 292      */
 293     LockedPtr(const LockedPtr& rhs) : parent_(rhs.parent_) {
 294       acquire();
 295     }
 296
 297     /**
 298      * Assigning from another LockedPtr results in freeing the former
 299      * lock and acquiring the new one. The method works with
 300      * self-assignment (does nothing).
 301      */
 302     LockedPtr& operator=(const LockedPtr& rhs) {
 303       if (parent_ != rhs.parent_) {
 304         if (parent_) parent_->mutex_.unlock();
 305         parent_ = rhs.parent_;
 306         acquire();
 307       }
 308       return *this;
 309     }
 310
 311     /**
 312      * Destructor releases.
 313      */
 314     ~LockedPtr() {
 315       using namespace detail;
 316       if (parent_) releaseReadWrite(parent_->mutex_);
 317     }
 318
 319     /**
 320      * Safe to access the data. Don't save the obtained pointer by
 321      * invoking lp.operator->() by hand. Also, if the method returns a
 322      * handle stored inside the datum, don't use this idiom - use
 323      * SYNCHRONIZED below.
 324      */
 325     T* operator->() {
 326       return parent_ ? &parent_->datum_ : NULL;
 327     }
 328
 329     /**
 330      * This class temporarily unlocks a LockedPtr in a scoped
 331      * manner. It is used inside of the UNSYNCHRONIZED macro.
 332      */
 333     struct Unsynchronizer {
 334       explicit Unsynchronizer(LockedPtr* p) : parent_(p) {
 335         using namespace detail;
 336         releaseReadWrite(parent_->parent_->mutex_);
 337       }
 338       Unsynchronizer(const Unsynchronizer&) = delete;
 339       Unsynchronizer& operator=(const Unsynchronizer&) = delete;
 340       ~Unsynchronizer() {
 341         parent_->acquire();
 342       }
 343       LockedPtr* operator->() const {
 344         return parent_;
 345       }
 346     private:
 347       LockedPtr* parent_;
 348     };
 349     friend struct Unsynchronizer;
 350     Unsynchronizer typeHackDoNotUse();
 351
 352     template <class P1, class P2>
 353     friend void lockInOrder(P1& p1, P2& p2);
 354
 355   private:
 356     void acquire() {
 357       using namespace detail;
 358       if (parent_) acquireReadWrite(parent_->mutex_);
 359     }
 360
 361     // This is the entire state of LockedPtr.
 362     Synchronized* parent_;
 363   };
 364
 365   /**
 366    * ConstLockedPtr does exactly what LockedPtr does, but for const
 367    * Synchronized objects. Of interest is that ConstLockedPtr only
 368    * uses a read lock, which is faster but more restrictive - you only
 369    * get to call const methods of the datum.
 370    *
 371    * Much of the code between LockedPtr and
 372    * ConstLockedPtr is identical and could be factor out, but there
 373    * are enough nagging little differences to not justify the trouble.
 374    */
 375   struct ConstLockedPtr {
 376     ConstLockedPtr() = delete;
 377     explicit ConstLockedPtr(const Synchronized* parent) : parent_(parent) {
 378       acquire();
 379     }
 380     ConstLockedPtr(const Synchronized* parent, detail::InternalDoNotUse)
 381         : parent_(parent) {
 382     }
 383     ConstLockedPtr(const ConstLockedPtr& rhs) : parent_(rhs.parent_) {
 384       acquire();
 385     }
 386     explicit ConstLockedPtr(const LockedPtr& rhs) : parent_(rhs.parent_) {
 387       acquire();
 388     }
 389     ConstLockedPtr(const Synchronized* parent, unsigned int milliseconds) {
 390       if (parent->mutex_.timed_lock(
 391             boost::posix_time::milliseconds(milliseconds))) {
 392         parent_ = parent;
 393         return;
 394       }
 395       // Could not acquire the resource, pointer is null
 396       parent_ = NULL;
 397     }
 398
 399     ConstLockedPtr& operator=(const ConstLockedPtr& rhs) {
 400       if (parent_ != rhs.parent_) {
 401         if (parent_) parent_->mutex_.unlock_shared();
 402         parent_ = rhs.parent_;
 403         acquire();
 404       }
 405     }
 406     ~ConstLockedPtr() {
 407       using namespace detail;
 408       if (parent_) releaseRead(parent_->mutex_);
 409     }
 410
 411     const T* operator->() const {
 412       return parent_ ? &parent_->datum_ : NULL;
 413     }
 414
 415     struct Unsynchronizer {
 416       explicit Unsynchronizer(ConstLockedPtr* p) : parent_(p) {
 417         using namespace detail;
 418         releaseRead(parent_->parent_->mutex_);
 419       }
 420       Unsynchronizer(const Unsynchronizer&) = delete;
 421       Unsynchronizer& operator=(const Unsynchronizer&) = delete;
 422       ~Unsynchronizer() {
 423         using namespace detail;
 424         acquireRead(parent_->parent_->mutex_);
 425       }
 426       ConstLockedPtr* operator->() const {
 427         return parent_;
 428       }
 429     private:
 430       ConstLockedPtr* parent_;
 431     };
 432     friend struct Unsynchronizer;
 433     Unsynchronizer typeHackDoNotUse();
 434
 435     template <class P1, class P2>
 436     friend void lockInOrder(P1& p1, P2& p2);
 437
 438   private:
 439     void acquire() {
 440       using namespace detail;
 441       if (parent_) acquireRead(parent_->mutex_);
 442     }
 443
 444     const Synchronized* parent_;
 445   };
 446
 447   /**
 448    * This accessor offers a LockedPtr. In turn. LockedPtr offers
 449    * operator-> returning a pointer to T. The operator-> keeps
 450    * expanding until it reaches a pointer, so syncobj->foo() will lock
 451    * the object and call foo() against it.
 452   */
 453   LockedPtr operator->() {
 454     return LockedPtr(this);
 455   }
 456
 457   /**
 458    * Same, for constant objects. You will be able to invoke only const
 459    * methods.
 460    */
 461   ConstLockedPtr operator->() const {
 462     return ConstLockedPtr(this);
 463   }
 464
 465   /**
 466    * Attempts to acquire for a given number of milliseconds. If
 467    * acquisition is unsuccessful, the returned LockedPtr is NULL.
 468    */
 469   LockedPtr timedAcquire(unsigned int milliseconds) {
 470     return LockedPtr(this, milliseconds);
 471   }
 472
 473   /**
 474    * As above, for a constant object.
 475    */
 476   ConstLockedPtr timedAcquire(unsigned int milliseconds) const {
 477     return ConstLockedPtr(this, milliseconds);
 478   }
 479
 480   /**
 481    * Used by SYNCHRONIZED_DUAL.
 482    */
 483   LockedPtr internalDoNotUse() {
 484     return LockedPtr(this, detail::InternalDoNotUse());
 485   }
 486
 487   /**
 488    * ditto
 489    */
 490   ConstLockedPtr internalDoNotUse() const {
 491     return ConstLockedPtr(this, detail::InternalDoNotUse());
 492   }
 493
 494   /**
 495    * Sometimes, although you have a mutable object, you only want to
 496    * call a const method against it. The most efficient way to achieve
 497    * that is by using a read lock. You get to do so by using
 498    * obj.asConst()->method() instead of obj->method().
 499    */
 500   const Synchronized& asConst() const {
 501     return *this;
 502   }
 503
 504   /**
 505    * Swaps with another Synchronized. Protected against
 506    * self-swap. Only data is swapped. Locks are acquired in increasing
 507    * address order.
 508    */
 509   void swap(Synchronized& rhs) {
 510     if (this == &rhs) {
 511       return;
 512     }
 513     if (this > &rhs) {
 514       return rhs.swap(*this);
 515     }
 516     auto guard1 = operator->();
 517     auto guard2 = rhs.operator->();
 518     datum_.swap(rhs.datum_);
 519   }
 520
 521   /**
 522    * Swap with another datum. Recommended because it keeps the mutex
 523    * held only briefly.
 524    */
 525   void swap(T& rhs) {
 526     LockedPtr guard = operator->();
 527     datum_.swap(rhs);
 528   }
 529
 530   /**
 531    * Copies datum to a given target.
 532    */
 533   void copy(T* target) const {
 534     ConstLockedPtr guard = operator->();
 535     *target = datum_;
 536   }
 537
 538   /**
 539    * Returns a fresh copy of the datum.
 540    */
 541   T copy() const {
 542     ConstLockedPtr guard = operator->();
 543     return datum_;
 544   }
 545
 546 private:
 547   T datum_;
 548   mutable Mutex mutex_;
 549 };
 550
 551 // Non-member swap primitive
 552 template <class T, class M>
 553 void swap(Synchronized<T, M>& lhs, Synchronized<T, M>& rhs) {
 554   lhs.swap(rhs);
 555 }
 556
 557 /**
 558  * SYNCHRONIZED is the main facility that makes Synchronized<T>
 559  * helpful. It is a pseudo-statement that introduces a scope where the
 560  * object is locked. Inside that scope you get to access the unadorned
 561  * datum.
 562  *
 563  * Example:
 564  *
 565  * Synchronized<vector<int>> svector;
 566  * ...
 567  * SYNCHRONIZED (svector) { ... use svector as a vector<int> ... }
 568  * or
 569  * SYNCHRONIZED (v, svector) { ... use v as a vector<int> ... }
 570  *
 571  * Refer to folly/docs/Synchronized.md for a detailed explanation and more
 572  * examples.
 573  */
 574 #define SYNCHRONIZED(...)                                       \
 575   if (bool SYNCHRONIZED_state = false) {} else                  \
 576     for (auto SYNCHRONIZED_lockedPtr =                          \
 577            (FB_ARG_2_OR_1(__VA_ARGS__)).operator->();           \
 578          !SYNCHRONIZED_state; SYNCHRONIZED_state = true)        \
 579       for (auto& FB_ARG_1(__VA_ARGS__) =                        \
 580              *SYNCHRONIZED_lockedPtr.operator->();              \
 581            !SYNCHRONIZED_state; SYNCHRONIZED_state = true)
 582
 583 #define TIMED_SYNCHRONIZED(timeout, ...)                           \
 584   if (bool SYNCHRONIZED_state = false) {} else                     \
 585     for (auto SYNCHRONIZED_lockedPtr =                             \
 586            (FB_ARG_2_OR_1(__VA_ARGS__)).timedAcquire(timeout);     \
 587          !SYNCHRONIZED_state; SYNCHRONIZED_state = true)           \
 588       for (auto FB_ARG_1(__VA_ARGS__) =                            \
 589              SYNCHRONIZED_lockedPtr.operator->();                  \
 590            !SYNCHRONIZED_state; SYNCHRONIZED_state = true)
 591
 592 /**
 593  * Similar to SYNCHRONIZED, but only uses a read lock.
 594  */
 595 #define SYNCHRONIZED_CONST(...)                         \
 596   SYNCHRONIZED(FB_ARG_1(__VA_ARGS__),                   \
 597                (FB_ARG_2_OR_1(__VA_ARGS__)).asConst())
 598
 599 /**
 600  * Similar to TIMED_SYNCHRONIZED, but only uses a read lock.
 601  */
 602 #define TIMED_SYNCHRONIZED_CONST(timeout, ...)                  \
 603   TIMED_SYNCHRONIZED(timeout, FB_ARG_1(__VA_ARGS__),            \
 604                      (FB_ARG_2_OR_1(__VA_ARGS__)).asConst())
 605
 606 /**
 607  * Temporarily disables synchronization inside a SYNCHRONIZED block.
 608  */
 609 #define UNSYNCHRONIZED(name)                                    \
 610   for (decltype(SYNCHRONIZED_lockedPtr.typeHackDoNotUse())      \
 611          SYNCHRONIZED_state3(&SYNCHRONIZED_lockedPtr);          \
 612        !SYNCHRONIZED_state; SYNCHRONIZED_state = true)          \
 613     for (auto name = *SYNCHRONIZED_state3.operator->();         \
 614          !SYNCHRONIZED_state; SYNCHRONIZED_state = true)
 615
 616 /**
 617  * Locks two objects in increasing order of their addresses.
 618  */
 619 template <class P1, class P2>
 620 void lockInOrder(P1& p1, P2& p2) {
 621   if (static_cast<const void*>(p1.operator->()) >
 622       static_cast<const void*>(p2.operator->())) {
 623     p2.acquire();
 624     p1.acquire();
 625   } else {
 626     p1.acquire();
 627     p2.acquire();
 628   }
 629 }
 630
 631 /**
 632  * Synchronizes two Synchronized objects (they may encapsulate
 633  * different data). Synchronization is done in increasing address of
 634  * object order, so there is no deadlock risk.
 635  */
 636 #define SYNCHRONIZED_DUAL(n1, e1, n2, e2)                       \
 637   if (bool SYNCHRONIZED_state = false) {} else                  \
 638     for (auto SYNCHRONIZED_lp1 = (e1).internalDoNotUse();       \
 639          !SYNCHRONIZED_state; SYNCHRONIZED_state = true)        \
 640       for (auto& n1 = *SYNCHRONIZED_lp1.operator->();           \
 641            !SYNCHRONIZED_state;  SYNCHRONIZED_state = true)     \
 642         for (auto SYNCHRONIZED_lp2 = (e2).internalDoNotUse();   \
 643              !SYNCHRONIZED_state;  SYNCHRONIZED_state = true)   \
 644           for (auto& n2 = *SYNCHRONIZED_lp2.operator->();       \
 645                !SYNCHRONIZED_state; SYNCHRONIZED_state = true)  \
 646             if ((::folly::lockInOrder(                          \
 647                    SYNCHRONIZED_lp1, SYNCHRONIZED_lp2),         \
 648                  false)) {}                                     \
 649             else
 650
 651 } /* namespace folly */
 652
 653 #endif // SYNCHRONIZED_H_