Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Detect partial deadlocks #3425

Open
RalfJung opened this issue Mar 27, 2024 · 1 comment
Open

Detect partial deadlocks #3425

RalfJung opened this issue Mar 27, 2024 · 1 comment
Labels
A-concurrency Area: affects our concurrency (multi-thread) support C-enhancement Category: a PR with an enhancement or an issue tracking an accepted enhancement

Comments

@RalfJung
Copy link
Member

Currently we only report a deadlock when all threads stop running. Ideally we'd be able to detect partial deadlocks, where two threads are waiting on each other but other, unrelated threads can still make progress.

This will require tracking more information about why a thread is blocked. We can then build a graph of "thread X blocked on thread Y", and if there's a cycle in that graph we have a (partial) deadlock. It might require asking libraries to provide us with such information: e.g. for POSIX locks we know which thread is currently holding a lock, so we can add the edge in the graph; but for futex-based locks we don't know which thread a futex_wait is waiting for, so we can't know where that graph edge is supposed to point to.

Following this paper we should actually treat deadlocks and memory leaks together and then we can detect partial deadlocks and partial leaks, but it's not clear to me how to best apply that to Miri -- and the sheer number of memory allocations may make that infeasible.

@RalfJung RalfJung added C-enhancement Category: a PR with an enhancement or an issue tracking an accepted enhancement A-diagnostics errors and warnings emitted by miri A-concurrency Area: affects our concurrency (multi-thread) support and removed A-diagnostics errors and warnings emitted by miri labels Mar 27, 2024
@RalfJung
Copy link
Member Author

#3471 implements the tracking of what a thread is blocked on. However, the isue with Futexes remains.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
A-concurrency Area: affects our concurrency (multi-thread) support C-enhancement Category: a PR with an enhancement or an issue tracking an accepted enhancement
Projects
None yet
Development

No branches or pull requests

1 participant