SharedMutex - a small fast scalable reader-writer lock

SharedMutex - a small fast scalable reader-writer lock

Summary:
SharedMutex is a reader-writer lock.  It is small, very fast, scalable
on multi-core, and suitable for use when readers or writers may block.
Unlike most other reader-writer locks, its throughput with concurrent
readers scales linearly; it is able to acquire and release the lock
in shared mode without cache line ping-ponging.  It is suitable for a
wide range of lock hold times because it starts with spinning, proceeds
to using sched_yield with a preemption heuristic, and then waits using
futex and precise wakeups.

SharedMutex provides all of the methods of folly::RWSpinLock,
boost::shared_mutex, boost::upgrade_mutex, and C++14's
std::shared_timed_mutex.  All operations that can block are available in
try, try-for, and try-until (system_clock or steady_clock) versions.
Both reader-priority and writer-priority versions are provided.
Writer-priority is the default at the moment.

In my tests SharedMutex is as good or better than the other reader-writer
locks in use at Facebook for almost all use cases, sometimes by a wide
margin.  (If it is rare that there are actually concurrent readers
then RWSpinLock can be a few nanoseconds faster.)  I compared it to
folly::RWSpinLock, folly::RWTicketSpinLock64, boost::shared_mutex,
pthread_rwlock_t, and an internal RWLock that uses spinlocks to guard
its state and pthread_mutex_t+pthread_cont_t to perform blocking.
(The other ReadWriteMutex-s I found use pthread_rwlock_t underneath.)
It is generally as good or better than the rest when evaluating size,
speed, scalability, or latency outliers.  In the corner cases where
it is not the fastest (such as single-threaded use or heavy write
contention) it is never very much worse than the best.  See the bottom
of SharedMutexTest.cpp for lots of microbenchmark results.

Test Plan:
1. new unit tests
2. new microbenchmarks included here
3. uncommitted microbenchmark from bmaurer's RWSleepLock
4. replace admarket's RWSpinLock and RWLock with SharedMutex, observe
neutral adindexer perf in canary
5. replace multifeed's thrift ReadWriteLock with SharedMutex, observe
neutral perf in canary

Reviewed By: hans@fb.com

Subscribers: fbcode-common-diffs@, tnovak, march, davejwatson, trunkagent, philipp, folly-diffs@, yfeldblum, bwatling, bmaurer, bol, marccelani, adri, strager, macsyz, dzhulgakov, zamsden

FB internal diff: D1798929

Signature: t1:1798929:1425575976:1c9221317eaa47628a2b8c374f90c7a2d4e3f0f9