Fix a deadlock bug in MCS-PDR locks
authorBarret Rhoden <brho@cs.berkeley.edu>
Fri, 4 Dec 2015 20:31:03 +0000 (15:31 -0500)
committerBarret Rhoden <brho@cs.berkeley.edu>
Tue, 8 Dec 2015 20:59:08 +0000 (15:59 -0500)
commit41e798408dfc7afca23797cc55f5769599b1bebc
tree7d46f83b260ce2716f18190158beb54a29d33e8b
parenta919327b086035f8d0dcf4484c90bbff83665277
Fix a deadlock bug in MCS-PDR locks

The MCS-PDR locks have an optimization built in where most vcores ensure the
lockholder runs.  The other style is to ensure whoever is directly ahead in
line (the predecessor) runs, which we fall back to in some tricky corner
cases.  That all is fine.

In the unlock case, the lockholder needs to ensure whoever is next in line
runs (the lockholder's successor).  Waiting on a_tail requires that
everyone in line is ensuring their predecessor runs, which is not what
happens by default.  By clearing the lockholder_vcoreid, we can fall back
to this "get out of corner cases by following the chain" approach.

I've been chasing this one off and on for a couple years.  I managed to
recreate it once or twice and was able to peak at the userspace contexts.
I could see all but one of them were calling ensure_vcore_runs(2), and VC 2
was calling ensure_vcore_runs(1).  Two other vcores were preempted.  I
could see VC 2 was in an unlock.  There were no syscalls coming from that
process.

It was actually simple after that.  What happened was that a vcore signed
up for the lock (L391), but hadn't set pred->next yet (L396).  Then it gets
preempted.  VC 2 was its pred, and it acquired the lock with no issues.
When it went to unlock, it needed to ensure it's successor was running.  VC
2 was the lockholder_vcoreid.  Everyone in the chain behind the preempted
VC kept ensuring 2 ran.  No one ensured the preempted VC ran.

Signed-off-by: Barret Rhoden <brho@cs.berkeley.edu>
user/parlib/mcs.c