-
Notifications
You must be signed in to change notification settings - Fork 269
Deadlock in SelfContainedMutex #2557
Description
Broken out of #2552
I think this can only happen when the mutex is under contention, which I don't think currently ever happens in Shadow, but it'd be good to fix.
I have a prototype loom test locally that finds a deadlock. It's a little rough to trace through, but mostly by eyeballing the code again, I think at least one possibility is:
Thread1 Thread2
------- -------
stores LOCKED
loads LOCKED
stores UNLOCKED
loads sleepers==0
Skips FUTEX_WAKE
increments sleepers
FUTEX_WAIT
I locally have a fix that adds a LOCKED_PENDING_UNLOCK state which seems to fix it, but forces a thread that's trying to unlock to spin if it finds the lock in that state. This would probably be ok in practice, but loom tests don't play very well with such spinning (even with a thread::yield_now in the loop), and it'd be nice to have a solution that loom is able to fully validate.
I think a better solution is probably to store the sleeper-count and mutex-state together in a single atomic, so that a thread that's unlocking can atomically unlock and get the sleeper count. I think it doesn't need to be part of the futex word, so we can use an atomic64 to store both a 32-bit sleeper count and 32-bit mutex-state. Otherwise we can cram both into 32 bits.