Reworks MCS-PDR locks to avoid preempt storms
authorBarret Rhoden <brho@cs.berkeley.edu>
Sat, 25 May 2013 21:55:56 +0000 (14:55 -0700)
committerBarret Rhoden <brho@cs.berkeley.edu>
Sat, 25 May 2013 22:09:02 +0000 (15:09 -0700)
commitd9b0e8d8c06087c9bc46b1310ece70b0435ae279
treefd0507c9b775173c6aceb7422887c7642cba752e
parentb949bdaeb2f3020e1e50c0d018c8f4c47422aa1a
Reworks MCS-PDR locks to avoid preempt storms

The old style would aggressively switch to its pred, which made it
extremely unlikely to ever have a vcore outside the MCS chain recover
one of the vcores in the chain.  This means that we would always have a
vcore in the chain that was preempted, leading to at least one syscall
per lock acquisition.  This causes a massive amount of
preemption/change-tos that last until all vcores are given back.

The new style tries to restart the lockholder, instead of pred, only
relying on pred when there is no other way out.  This style recovers
quickly from a preemption, even if the vcores are never given back.

While it might be a little slower than the old PDR locks, it is
significantly safer, and is now the default.

The old style PDR locks are now called mcs_pdro_locks (o for
old).

Note there are a few optimizations that the first version of PDR locks
didn't have that were important.  (First version being the one from over
a year ago).  The lockholder handoff is handed off when we unlock our
qnode->next, which saves a lot on cache line contention.  We use the
qnodes address for pointer arithmetic to determine vcoreid.  And we
properly memalign the qnode storage, ensuring cache line alignment.

As far as cache lines go, some prefetching ruins our "independent" cache
lines.  For now, I turn off things like Adjacent Cacheline Prefetching,
or whatever it's called these days.  Would be nice if we had an
instruction that explicitly didn't trigger a prefetch on a load or
store.
tests/lock_test.c
user/parlib/include/mcs.h
user/parlib/mcs.c
user/pthread/futex.c
user/pthread/pthread.c