Re: False positives in deadlock detection

On Fri, 15 Mar 2024 at 14:53, Stas Boukarev <[email protected]> wrote:
> You don't need to stop the world because if there is a deadlock the threads are aleady stopped.

I haven't thought much about whether real deadlocks would get detected.
But deadlocks may be detected where there aren't any.

> Which part is racy?

I suspect it's racy because I couldn't convince myself otherwise in
half an hour. Here is my thinking.

While CHECK-DEADLOCK is running, other threads are acquiring and
releasing locks, leading to situations like in this report. The chain
can be completely bogus in that it does not correspond to a consistent
snapshot (that one could get with the world stopped). Even a single
step in the chain -- looking up the owner of a lock and then looking
up what the owner thread is waiting for -- can give us a lock-to-lock
edge in the graph that never existed, if between the two lookups the
owner thread releases the lock and proceeds to block on another.

If the read barriers somehow guarantee that this cannot happen, I
can't see it.

The recheck needs to do what the comment [1] says:

    ;; Recheck that the mutex is still owned by the same thread.

... while the code that follows seems happy if the mutex is owned
_again_ by the same thread, or if the change of ownership is not yet
visible to this thread.



[1]: https://github.com/sbcl/sbcl/blob/1aaeffe0bc7319f07413077a9a0c17877f995a4a/src/code/target-thread.lisp#L588C45-L588C102