Updating documentation for folly::Synchronized to include upgradable
[folly.git] / folly / docs / Synchronized.md
1 `folly/Synchronized.h`
2 ----------------------
3
4 `folly/Synchronized.h` introduces a simple abstraction for mutex-
5 based concurrency. It replaces convoluted, unwieldy, and just
6 plain wrong code with simple constructs that are easy to get
7 right and difficult to get wrong.
8
9 ### Motivation
10
11 Many of our multithreaded C++ programs use shared data structures
12 associated with locks. This follows the time-honored adage of
13 mutex-based concurrency control "associate mutexes with data, not code".
14 Consider the following example:
15
16 ``` Cpp
17
18     class RequestHandler {
19       ...
20       RequestQueue requestQueue_;
21       SharedMutex requestQueueMutex_;
22
23       std::map<std::string, Endpoint> requestEndpoints_;
24       SharedMutex requestEndpointsMutex_;
25
26       HandlerState workState_;
27       SharedMutex workStateMutex_;
28       ...
29     };
30 ```
31
32 Whenever the code needs to read or write some of the protected
33 data, it acquires the mutex for reading or for reading and
34 writing. For example:
35
36 ``` Cpp
37     void RequestHandler::processRequest(const Request& request) {
38       stop_watch<> watch;
39       checkRequestValidity(request);
40       SharedMutex::WriteHolder lock(requestQueueMutex_);
41       requestQueue_.push_back(request);
42       stats_->addStatValue("requestEnqueueLatency", watch.elapsed());
43       LOG(INFO) << "enqueued request ID " << request.getID();
44     }
45 ```
46
47 However, the correctness of the technique is entirely predicated on
48 convention.  Developers manipulating these data members must take care
49 to explicitly acquire the correct lock for the data they wish to access.
50 There is no ostensible error for code that:
51
52 * manipulates a piece of data without acquiring its lock first
53 * acquires a different lock instead of the intended one
54 * acquires a lock in read mode but modifies the guarded data structure
55 * acquires a lock in read-write mode although it only has `const` access
56   to the guarded data
57
58 ### Introduction to `folly/Synchronized.h`
59
60 The same code sample could be rewritten with `Synchronized`
61 as follows:
62
63 ``` Cpp
64     class RequestHandler {
65       ...
66       Synchronized<RequestQueue> requestQueue_;
67       Synchronized<std::map<std::string, Endpoint>> requestEndpoints_;
68       Synchronized<HandlerState> workState_;
69       ...
70     };
71
72     void RequestHandler::processRequest(const Request& request) {
73       stop_watch<> watch;
74       checkRequestValidity(request);
75       requestQueue_.wlock()->push_back(request);
76       stats_->addStatValue("requestEnqueueLatency", watch.elapsed());
77       LOG(INFO) << "enqueued request ID " << request.getID();
78     }
79 ```
80
81 The rewrite does at maximum efficiency what needs to be done:
82 acquires the lock associated with the `RequestQueue` object, writes to
83 the queue, and releases the lock immediately thereafter.
84
85 On the face of it, that's not much to write home about, and not
86 an obvious improvement over the previous state of affairs. But
87 the features at work invisible in the code above are as important
88 as those that are visible:
89
90 * Unlike before, the data and the mutex protecting it are
91   inextricably encapsulated together.
92 * If you tried to use `requestQueue_` without acquiring the lock you
93   wouldn't be able to; it is virtually impossible to access the queue
94   without acquiring the correct lock.
95 * The lock is released immediately after the insert operation is
96   performed, and is not held for operations that do not need it.
97
98 If you need to perform several operations while holding the lock,
99 `Synchronized` provides several options for doing this.
100
101 The `wlock()` method (or `lock()` if you have a non-shared mutex type)
102 returns a `LockedPtr` object that can be stored in a variable.  The lock
103 will be held for as long as this object exists, similar to a
104 `std::unique_lock`.  This object can be used as if it were a pointer to
105 the underlying locked object:
106
107 ``` Cpp
108     {
109       auto lockedQueue = requestQueue_.wlock();
110       lockedQueue->push_back(request1);
111       lockedQueue->push_back(request2);
112     }
113 ```
114
115 The `rlock()` function is similar to `wlock()`, but acquires a shared lock
116 rather than an exclusive lock.
117
118 We recommend explicitly opening a new nested scope whenever you store a
119 `LockedPtr` object, to help visibly delineate the critical section, and
120 to ensure that the `LockedPtr` is destroyed as soon as it is no longer
121 needed.
122
123 Alternatively, `Synchronized` also provides mechanisms to run a function while
124 holding the lock.  This makes it possible to use lambdas to define brief
125 critical sections:
126
127 ``` Cpp
128     void RequestHandler::processRequest(const Request& request) {
129       stop_watch<> watch;
130       checkRequestValidity(request);
131       requestQueue_.withWLock([](auto& queue) {
132         // withWLock() automatically holds the lock for the
133         // duration of this lambda function
134         queue.push_back(request);
135       });
136       stats_->addStatValue("requestEnqueueLatency", watch.elapsed());
137       LOG(INFO) << "enqueued request ID " << request.getID();
138     }
139 ```
140
141 One advantage of the `withWLock()` approach is that it forces a new
142 scope to be used for the critical section, making the critical section
143 more obvious in the code, and helping to encourage code that releases
144 the lock as soon as possible.
145
146 ### Template class `Synchronized<T>`
147
148 #### Template Parameters
149
150 `Synchronized` is a template with two parameters, the data type and a
151 mutex type: `Synchronized<T, Mutex>`.
152
153 If not specified, the mutex type defaults to `std::mutex`.  However, any
154 mutex type supported by `folly::LockTraits` can be used instead.
155 `folly::LockTraits` can be specialized to support other custom mutex
156 types that it does not know about out of the box.  See
157 `folly/LockTraitsBoost.h` for an example of how to support additional mutex
158 types.
159
160 `Synchronized` provides slightly different APIs when instantiated with a
161 shared mutex type or an upgrade mutex type then with a plain exclusive mutex.
162 If instantiated with either of the two mutex types above (either through
163 having a member called lock_shared() or specializing `LockTraits` as in
164 `folly/LockTraitsBoost.h`) the `Synchronized` object has corresponding
165 `wlock`, `rlock` or `ulock` methods to acquire different lock types.  When
166 using a shared or upgrade mutex type, these APIs ensure that callers make an
167 explicit choice to acquire a shared, exclusive or upgrade lock and that
168 callers do not unintentionally lock the mutex in the incorrect mode.  The
169 `rlock()` APIs only provide `const` access to the underlying data type,
170 ensuring that it cannot be modified when only holding a shared lock.
171
172 #### Constructors
173
174 The default constructor default-initializes the data and its
175 associated mutex.
176
177
178 The copy constructor locks the source for reading and copies its
179 data into the target. (The target is not locked as an object
180 under construction is only accessed by one thread.)
181
182 Finally, `Synchronized<T>` defines an explicit constructor that
183 takes an object of type `T` and copies it. For example:
184
185 ``` Cpp
186     // Default constructed
187     Synchronized<map<string, int>> syncMap1;
188
189     // Copy constructed
190     Synchronized<map<string, int>> syncMap2(syncMap1);
191
192     // Initializing from an existing map
193     map<string, int> init;
194     init["world"] = 42;
195     Synchronized<map<string, int>> syncMap3(init);
196     EXPECT_EQ(syncMap3->size(), 1);
197 ```
198
199 #### Assignment, swap, and copying
200
201 The canonical assignment operator locks both objects involved and
202 then copies the underlying data objects. The mutexes are not
203 copied. The locks are acquired in increasing address order, so
204 deadlock is avoided. For example, there is no problem if one
205 thread assigns `a = b` and the other assigns `b = a` (other than
206 that design probably deserving a Razzie award). Similarly, the
207 `swap` method takes a reference to another `Synchronized<T>`
208 object and swaps the data. Again, locks are acquired in a well-
209 defined order. The mutexes are not swapped.
210
211 An additional assignment operator accepts a `const T&` on the
212 right-hand side. The operator copies the datum inside a
213 critical section.
214
215 In addition to assignment operators, `Synchronized<T>` has move
216 assignment operators.
217
218 An additional `swap` method accepts a `T&` and swaps the data
219 inside a critical section. This is by far the preferred method of
220 changing the guarded datum wholesale because it keeps the lock
221 only for a short time, thus lowering the pressure on the mutex.
222
223 To get a copy of the guarded data, there are two methods
224 available: `void copy(T*)` and `T copy()`. The first copies data
225 to a provided target and the second returns a copy by value. Both
226 operations are done under a read lock. Example:
227
228 ``` Cpp
229     Synchronized<vector<string>> syncVec1, syncVec2;
230     vector<string> vec;
231
232     // Assign
233     syncVec1 = syncVec2;
234     // Assign straight from vector
235     syncVec1 = vec;
236
237     // Swap
238     syncVec1.swap(syncVec2);
239     // Swap with vector
240     syncVec1.swap(vec);
241
242     // Copy to given target
243     syncVec1.copy(&vec);
244     // Get a copy by value
245     auto copy = syncVec1.copy();
246 ```
247
248 #### `lock()`
249
250 If the mutex type used with `Synchronized` is a simple exclusive mutex
251 type (as opposed to a shared mutex), `Synchronized<T>` provides a
252 `lock()` method that returns a `LockedPtr<T>` to access the data while
253 holding the lock.
254
255 The `LockedPtr` object returned by `lock()` holds the lock for as long
256 as it exists.  Whenever possible, prefer declaring a separate inner
257 scope for storing this variable, to make sure the `LockedPtr` is
258 destroyed as soon as the lock is no longer needed:
259
260 ``` Cpp
261     void fun(Synchronized<vector<string>, std::mutex>& vec) {
262       {
263         auto locked = vec.lock();
264         locked->push_back("hello");
265         locked->push_back("world");
266       }
267       LOG(INFO) << "successfully added greeting";
268     }
269 ```
270
271 #### `wlock()` and `rlock()`
272
273 If the mutex type used with `Synchronized` is a shared mutex type,
274 `Synchronized<T>` provides a `wlock()` method that acquires an exclusive
275 lock, and an `rlock()` method that acquires a shared lock.
276
277 The `LockedPtr` returned by `rlock()` only provides const access to the
278 internal data, to ensure that it cannot be modified while only holding a
279 shared lock.
280
281 ``` Cpp
282     int computeSum(const Synchronized<vector<int>>& vec) {
283       int sum = 0;
284       auto locked = vec.rlock();
285       for (int n : *locked) {
286         sum += n;
287       }
288       return sum;
289     }
290
291     void doubleValues(Synchronized<vector<int>>& vec) {
292       auto locked = vec.wlock();
293       for (int& n : *locked) {
294         n *= 2;
295       }
296     }
297 ```
298
299 This example brings us to a cautionary discussion.  The `LockedPtr`
300 object returned by `lock()`, `wlock()`, or `rlock()` only holds the lock
301 as long as it exists.  This object makes it difficult to access the data
302 without holding the lock, but not impossible.  In particular you should
303 never store a raw pointer or reference to the internal data for longer
304 than the lifetime of the `LockedPtr` object.
305
306 For instance, if we had written the following code in the examples
307 above, this would have continued accessing the vector after the lock had
308 been released:
309
310 ``` Cpp
311     // No. NO. NO!
312     for (int& n : *vec.wlock()) {
313       n *= 2;
314     }
315 ```
316
317 The `vec.wlock()` return value is destroyed in this case as soon as the
318 internal range iterators are created.  The range iterators point into
319 the vector's data, but lock is released immediately, before executing
320 the loop body.
321
322 Needless to say, this is a crime punishable by long debugging nights.
323
324 Range-based for loops are slightly subtle about the lifetime of objects
325 used in the initializer statement.  Most other problematic use cases are
326 a bit easier to spot than this, since the lifetime of the `LockedPtr` is
327 more explicitly visible.
328
329 #### `withLock()`
330
331 As an alternative to the `lock()` API, `Synchronized` also provides a
332 `withLock()` method that executes a function or lambda expression while
333 holding the lock.  The function receives a reference to the data as its
334 only argument.
335
336 This has a few benefits compared to `lock()`:
337
338 * The lambda expression requires its own nested scope, making critical
339   sections more visible in the code.  Callers are recommended to define
340   a new scope when using `lock()` if they choose to, but this is not
341   required.  `withLock()` ensures that a new scope must always be
342   defined.
343 * Because a new scope is required, `withLock()` also helps encourage
344   users to release the lock as soon as possible.  Because the critical
345   section scope is easily visible in the code, it is harder to
346   accidentally put extraneous code inside the critical section without
347   realizing it.
348 * The separate lambda scope makes it more difficult to store raw
349   pointers or references to the protected data and continue using those
350   pointers outside the critical section.
351
352 For example, `withLock()` makes the range-based for loop mistake from
353 above much harder to accidentally run into:
354
355 ``` Cpp
356     vec.withLock([](auto& locked) {
357       for (int& n : locked) {
358         n *= 2;
359       }
360     });
361 ```
362
363 This code does not have the same problem as the counter-example with
364 `wlock()` above, since the lock is held for the duration of the loop.
365
366 When using `Synchronized` with a shared mutex type, it provides separate
367 `withWLock()` and `withRLock()` methods instead of `withLock()`.
368
369 #### `ulock()` and `withULockPtr()` 
370
371 `Synchronized` also supports upgrading and downgrading mutex lock levels as
372 long as the mutex type used to instantiate the `Synchronized` type has the
373 same interface as the mutex types in the C++ standard library, or if
374 `LockTraits` is specialized for the mutex type and the specialization is
375 visible.
376
377 An upgrade lock can be acquired as usual either with the `ulock()` method or
378 the `withULockPtr()` method as so
379
380 ``` Cpp
381     {
382       // only const access allowed to the underlying object when an upgrade lock
383       // is acquired
384       auto ulock = vec.ulock();
385       auto newSize = ulock->size();
386     }
387
388     auto newSize = vec.withULockPtr([](auto ulock) {
389       // only const access allowed to the underlying object when an upgrade lock
390       // is acquired
391       return ulock->size();
392     });
393 ```
394
395 An upgrade lock acquired via `ulock()` or `withULockPtr()` can be upgraded or
396 downgraded by calling any of the following methods on the `LockedPtr` proxy
397
398 * `moveFromUpgradeToWrite()`
399 * `moveFromWriteToUpgrade()`
400 * `moveFromWriteToShared()`
401 * `moveFromUpgradeToShared()`
402
403 Calling these leaves the `LockedPtr` object on which the method was called in
404 an invalid `null` state and returns another LockedPtr proxy holding the
405 specified lock.  The upgrade or downgrade is done atomically - the
406 `Synchronized` object is never in an unlocked state during the lock state
407 transition.  For example
408
409 ``` Cpp
410     auto ulock = obj.ulock();
411     if (ulock->needsUpdate()) {
412       auto wlock = ulock.moveFromUpgradeToWrite();
413
414       // ulock is now null
415
416       wlock->updateObj();
417     }
418 ```
419
420 This "move" can also occur in the context of a `withULockPtr()`
421 (`withWLockPtr()` or `withRLockPtr()` work as well!) function as so
422
423 ``` Cpp
424     auto newSize = obj.withULockPtr([](auto ulock) {
425       if (ulock->needsUpdate()) {
426
427         // release upgrade lock get write lock atomically
428         auto wlock = ulock.moveFromUpgradeToWrite();
429         // ulock is now null
430         wlock->updateObj();
431
432         // release write lock and acquire shared lock atomically
433         auto rlock = wlock.moveFromWriteToShared();
434         // wlock is now null
435         return rlock->newSize();
436
437       } else {
438
439         // release upgrade lock and acquire shared lock atomically
440         auto rlock = ulock.moveFromUpgradeToShared();
441         // ulock is now null
442         return rlock->newSize();
443       }
444     });
445 ```
446
447 #### Timed Locking
448
449 When `Synchronized` is used with a mutex type that supports timed lock
450 acquisition, `lock()`, `wlock()`, and `rlock()` can all take an optional
451 `std::chrono::duration` argument.  This argument specifies a timeout to
452 use for acquiring the lock.  If the lock is not acquired before the
453 timeout expires, a null `LockedPtr` object will be returned.  Callers
454 must explicitly check the return value before using it:
455
456 ``` Cpp
457     void fun(Synchronized<vector<string>>& vec) {
458       {
459         auto locked = vec.lock(10ms);
460         if (!locked) {
461           throw std::runtime_error("failed to acquire lock");
462         }
463         locked->push_back("hello");
464         locked->push_back("world");
465       }
466       LOG(INFO) << "successfully added greeting";
467     }
468 ```
469
470 #### `unlock()` and `scopedUnlock()`
471
472 `Synchronized` is a good mechanism for enforcing scoped
473 synchronization, but it has the inherent limitation that it
474 requires the critical section to be, well, scoped. Sometimes the
475 code structure requires a fleeting "escape" from the iron fist of
476 synchronization, while still inside the critical section scope.
477
478 One common pattern is releasing the lock early on error code paths,
479 prior to logging an error message.  The `LockedPtr` class provides an
480 `unlock()` method that makes this possible:
481
482 ``` Cpp
483     Synchronized<map<int, string>> dic;
484     ...
485     {
486       auto locked = dic.rlock();
487       auto iter = locked->find(0);
488       if (iter == locked.end()) {
489         locked.unlock();  // don't hold the lock while logging
490         LOG(ERROR) << "key 0 not found";
491         return false;
492       }
493       processValue(*iter);
494     }
495     LOG(INFO) << "succeeded";
496 ```
497
498 For more complex nested control flow scenarios, `scopedUnlock()` returns
499 an object that will release the lock for as long as it exists, and will
500 reacquire the lock when it goes out of scope.
501
502 ``` Cpp
503
504     Synchronized<map<int, string>> dic;
505     ...
506     {
507       auto locked = dic.wlock();
508       auto iter = locked->find(0);
509       if (iter == locked->end()) {
510         {
511           auto unlocker = locked.scopedUnlock();
512           LOG(INFO) << "Key 0 not found, inserting it."
513         }
514         locked->emplace(0, "zero");
515       } else {
516         *iter = "zero";
517       }
518     }
519 ```
520
521 Clearly `scopedUnlock()` comes with specific caveats and
522 liabilities. You must assume that during the `scopedUnlock()`
523 section, other threads might have changed the protected structure
524 in arbitrary ways. In the example above, you cannot use the
525 iterator `iter` and you cannot assume that the key `0` is not in the
526 map; another thread might have inserted it while you were
527 bragging on `LOG(INFO)`.
528
529 Whenever a `LockedPtr` object has been unlocked, whether with `unlock()`
530 or `scopedUnlock()`, it will behave as if it is null.  `isNull()` will
531 return true.  Dereferencing an unlocked `LockedPtr` is not allowed and
532 will result in undefined behavior.
533
534 #### `Synchronized` and `std::condition_variable`
535
536 When used with a `std::mutex`, `Synchronized` supports using a
537 `std::condition_variable` with its internal mutex.  This allows a
538 `condition_variable` to be used to wait for a particular change to occur
539 in the internal data.
540
541 The `LockedPtr` returned by `Synchronized<T, std::mutex>::lock()` has a
542 `getUniqueLock()` method that returns a reference to a
543 `std::unique_lock<std::mutex>`, which can be given to the
544 `std::condition_variable`:
545
546 ``` Cpp
547     Synchronized<vector<string>, std::mutex> vec;
548     std::condition_variable emptySignal;
549
550     // Assuming some other thread will put data on vec and signal
551     // emptySignal, we can then wait on it as follows:
552     auto locked = vec.lock();
553     emptySignal.wait_for(locked.getUniqueLock(),
554                          [&] { return !locked->empty(); });
555 ```
556
557 ### `acquireLocked()`
558
559 Sometimes locking just one object won't be able to cut the mustard. Consider a
560 function that needs to lock two `Synchronized` objects at the
561 same time - for example, to copy some data from one to the other.
562 At first sight, it looks like sequential `wlock()` calls will work just
563 fine:
564
565 ``` Cpp
566     void fun(Synchronized<vector<int>>& a, Synchronized<vector<int>>& b) {
567       auto lockedA = a.wlock();
568       auto lockedB = b.wlock();
569       ... use lockedA and lockedB ...
570     }
571 ```
572
573 This code compiles and may even run most of the time, but embeds
574 a deadly peril: if one threads call `fun(x, y)` and another
575 thread calls `fun(y, x)`, then the two threads are liable to
576 deadlocking as each thread will be waiting for a lock the other
577 is holding. This issue is a classic that applies regardless of
578 the fact the objects involved have the same type.
579
580 This classic problem has a classic solution: all threads must
581 acquire locks in the same order. The actual order is not
582 important, just the fact that the order is the same in all
583 threads. Many libraries simply acquire mutexes in increasing
584 order of their address, which is what we'll do, too. The
585 `acquireLocked()` function takes care of all details of proper
586 locking of two objects and offering their innards.  It returns a
587 `std::tuple` of `LockedPtr`s:
588
589 ``` Cpp
590     void fun(Synchronized<vector<int>>& a, Synchronized<vector<int>>& b) {
591       auto ret = folly::acquireLocked(a, b);
592       auto& lockedA = std::get<0>(ret);
593       auto& lockedB = std::get<1>(ret);
594       ... use lockedA and lockedB ...
595     }
596 ```
597
598 Note that C++ 17 introduces
599 (structured binding syntax)[(http://wg21.link/P0144r2)]
600 which will make the returned tuple more convenient to use:
601
602 ``` Cpp
603     void fun(Synchronized<vector<int>>& a, Synchronized<vector<int>>& b) {
604       auto [lockedA, lockedB] = folly::acquireLocked(a, b);
605       ... use lockedA and lockedB ...
606     }
607 ```
608
609 An `acquireLockedPair()` function is also available, which returns a
610 `std::pair` instead of a `std::tuple`.  This is more convenient to use
611 in many situations, until compiler support for structured bindings is
612 more widely available. 
613
614 ### Synchronizing several data items with one mutex
615
616 The library is geared at protecting one object of a given type
617 with a mutex. However, sometimes we'd like to protect two or more
618 members with the same mutex. Consider for example a bidirectional
619 map, i.e. a map that holds an `int` to `string` mapping and also
620 the converse `string` to `int` mapping. The two maps would need
621 to be manipulated simultaneously. There are at least two designs
622 that come to mind.
623
624 #### Using a nested `struct`
625
626 You can easily pack the needed data items in a little struct.
627 For example:
628
629 ``` Cpp
630     class Server {
631       struct BiMap {
632         map<int, string> direct;
633         map<string, int> inverse;
634       };
635       Synchronized<BiMap> bimap_;
636       ...
637     };
638     ...
639     bimap_.withLock([](auto& locked) {
640       locked.direct[0] = "zero";
641       locked.inverse["zero"] = 0;
642     });
643 ```
644
645 With this code in tow you get to use `bimap_` just like any other
646 `Synchronized` object, without much effort.
647
648 #### Using `std::tuple`
649
650 If you won't stop short of using a spaceship-era approach,
651 `std::tuple` is there for you. The example above could be
652 rewritten for the same functionality like this:
653
654 ``` Cpp
655     class Server {
656       Synchronized<tuple<map<int, string>, map<string, int>>> bimap_;
657       ...
658     };
659     ...
660     bimap_.withLock([](auto& locked) {
661       get<0>(locked)[0] = "zero";
662       get<1>(locked)["zero"] = 0;
663     });
664 ```
665
666 The code uses `std::get` with compile-time integers to access the
667 fields in the tuple. The relative advantages and disadvantages of
668 using a local struct vs. `std::tuple` are quite obvious - in the
669 first case you need to invest in the definition, in the second
670 case you need to put up with slightly more verbose and less clear
671 access syntax.
672
673 ### Summary
674
675 `Synchronized` and its supporting tools offer you a simple,
676 robust paradigm for mutual exclusion-based concurrency. Instead
677 of manually pairing data with the mutexes that protect it and
678 relying on convention to use them appropriately, you can benefit
679 of encapsulation and typechecking to offload a large part of that
680 task and to provide good guarantees.