folly/Synchronized.h

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