Re: False positives in deadlock detection

If it finds a thread that waits for a mutex owned by the current thread
then from this point nothing can change, so then it goes back and rechecks
that the previous mutex is still owned by this thread and so on.
Since the write to thread-waits-for happens after the write to mutex-owner
if we can observe thread-waits-for then we can be sure mutex-owner is
correct.

On Fri, Mar 15, 2024 at 7:41 PM Gábor Melis <[email protected]> wrote:

> 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
>

_______________________________________________
Sbcl-help mailing list
[email protected]
https://lists.sourceforge.net/lists/listinfo/sbcl-help