[PATCH] RFC v5: Mutex with spinning

[Nadav Har'El]

[Due to renewed interest, this is a repost of my "Mutex with spinning" patch
from a while back. Please watch out, this patch is lightly tested, and also
the amount of spinning is a silly constant (100), and probably should be
lower, and perhaps should be parameterized (a template?) so we can only
use this for specific mutexes known to be held for short durations?]

When a thread locks an already-held mutex, it goes to sleep, which incurs
the penalty of a context switch, and on SMP, likely also a slow cross-CPU
wakeup. In many cases, the lock holder will be holding the lock for a very
short time, and it will be beneficial to spin a bit waiting for the lock
to be released, before going to sleep.

This patch implements such spinning, using technique 2 described in
issue #25: we spin after incrementing the mutex's count, but before
adding ourselves to the queue, so unlock() may wake us using the handoff
mechanism.

For uncontended locks, the added spinning does nothing (we only spin when
we find a taken lock). For heavily-contended locks it also usually does
nothing as well, because as soon as the mutex's wait queue becomes
non-empty spinning stops, so if the wait queue is never empty (on a
very heavily contended lock) we never spin. So I believe this patch
will mostly be beneficial for moderatedly-contended mutexes.

In the test/misc-mutex.so benchmarks, this patch didn't change the
uncontended measurements and only sporadically improves the heavily
contended (20 threads constantly trying to obtain the mutex).
Performance is signficantly improved in the less heavily contended
benchmarks where context switches aren't necessary, with 2 or 4
lock-unlock loop threads on 4 cpus: From around 800ns and 1800ns for the
2 and 4 thread cases respectively, with this patch we are down to 33ns
and 153ns, respectively, more or less the same results we obtain with
a spinlock.

Please do not commit this patch, but feel free to try it on your favorite
benchmark. I'm continuing to investigate different ways of doing spinning
and their tradoffs.

Signed-off-by: Nadav Har'El <n...@scylladb.com>
---
core/lfmutex.cc | 52 ++++++++++++++++++++++++++++++++++++++++++++++++----
include/osv/sched.hh | 6 +++++-
2 files changed, 53 insertions(+), 5 deletions(-)

diff --git a/core/lfmutex.cc b/core/lfmutex.cc
index 542ca51..31b6b02 100644
--- a/core/lfmutex.cc
+++ b/core/lfmutex.cc
@@ -9,6 +9,7 @@
#include <osv/trace.hh>
#include <osv/sched.hh>
#include <osv/wait_record.hh>
+#include <osv/preempt-lock.hh>

namespace lockfree {

@@ -44,6 +45,40 @@ void mutex::lock()
++depth;
return;
}
+ // If we're still here, the lock is owned by a different thread. Before
+ // going to sleep, let's try to spin for a bit, to avoid the context
+ // switch costs when the critical section is very short. We're spinning
+ // without putting ourselves in the waitqueue first, so when the lock
+ // holder unlock()s, we expect to see a handoff.
+ // FIXME: do not spin when there is just one CPU.
+ // FIXME: change or parametrize the silly "100" number.
+ // If someone is on the waitqueue, there's no point in continuing to
+ // spin, as it will be woken first, and no handoff will be done.
+ for (int c = 0; c < 100 && waitqueue.empty(); c++) {
+ // If the lock holder got preempted, we would better be served
+ // by going to sleep and let it run again, than futile spinning.
+ // Especially if the lock holder wants to run on this CPU.
+ barrier(); // trying. didn't help
+ auto holder = owner.load(std::memory_order_relaxed);
+ // FIXME: what if thread exits while we want to check if it's
+ // running? as soon as we find the owner above, it might already
+ // be gone... Switch to using detached_thread as owner?
+ if (!holder || !holder->running()) {
+ break;
+ }
+ // If the lock holder is on the same CPU as us, better go to sleep
+ // and let it run than to futily spin
+// if (holder && holder->tcpu() == sched::cpu::current()) {
+// break;
+// }
+ auto old_handoff = handoff.load();
+ if (old_handoff && handoff.compare_exchange_strong(old_handoff, 0U)) {
+ owner.store(current, std::memory_order_relaxed);
+ depth = 1;
+ return;
+ }
+ asm volatile ("pause");
+ }

// If we're here still here the lock is owned by a different thread.
// Put this thread in a waiting queue, so it will eventually be woken
@@ -222,10 +257,19 @@ void mutex::unlock()
if (--depth)
return; // recursive mutex still locked.

- // When we return from unlock(), we will no longer be holding the lock.
- // We can't leave owner==current, otherwise a later lock() in the same
- // thread will think it's a recursive lock, while actually another thread
- // is in the middle of acquiring the lock and has set count>0.
+ // Disable preemption before we set owner=null, so that we don't context
+ // switch to a different thread who might end up spinning on this mutex.
+ // Alternatives to this change include remembering the lock holder's cpu
+ // (makes the mutex larger...), stopping spinning when !holder (makes
+ // "apart" ctxsw benchmark slower).
+ SCOPE_LOCK(preempt_lock);
+
+ // We can't return with owner==current, otherwise a later lock() in the
+ // same thread will think it's a recursive lock, while actually another
+ // thread is in the middle of acquiring the lock and has set count>0.
+ // So we need to zero owner, and we must do it *now*, before decrementing
+ // count (as soon as count goes down to 0, we released the lock and some
+ // other thread might alread set its own owner).
owner.store(nullptr, std::memory_order_relaxed);

// If there is no waiting lock(), we're done. This is the easy case :-)
diff --git a/include/osv/sched.hh b/include/osv/sched.hh
index 1db23af..d453b1c 100644
--- a/include/osv/sched.hh
+++ b/include/osv/sched.hh
@@ -540,7 +540,11 @@ public:
* wait queue for) a crucial mutex (e.g., for I/O or memory allocation),
* which could cause the whole system to block. So use at your own peril.
*/
- bool unsafe_stop();
+ bool unsafe_stop();
+ bool running() {
+ return _detached_state.get()->st.load(std::memory_order_relaxed) ==
+ status::running;
+ }
private:
static void wake_impl(detached_state* st,
unsigned allowed_initial_states_mask = 1 << unsigned(status::waiting));
--
2.5.0