Skip to content

Deadlock in SelfContainedMutex #2557

@sporksmith

Description

@sporksmith

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.

Metadata

Metadata

Assignees

Labels

Type: BugError or flaw producing unexpected results

Type

No type

Projects

No projects

Milestone

No milestone

Relationships

None yet

Development

No branches or pull requests

Issue actions