Re: False positives in deadlock detection

Which part is racy? You don't need to stop the world because if there is a
deadlock the threads are aleady stopped.

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

> I suspect this fix is also racy but can't see how to fix the
> inconsistent wait-for graph bug without extreme overhead, for example,
> stopping the world, which suggests doing it during GC.
>
> Gábor
>
> PS: If a timeout is in effect around the acquisition of a lock,
> CHECK-DEADLOCK cuts the dependency chain, which is reasonable [1].
> However, only SBCL's own timeouts are recognized; async unwinding for
> another reason is not. This creates the possibility for false
> positives if the code employs such a mechanism as par for the course
> (arguably quite ugly).
>
> [1]: Another, weird option is to signal the inevitable timeout ahead
>      of time.
>
> On Tue, 12 Mar 2024 at 21:55, Stas Boukarev <[email protected]> wrote:
> >
> > I pushed a fix. But, as always with multithreaded code, it's hard to be
> certain. So, please, test.
> > On Mon, Feb 26, 2024 at 6:58 PM Michał Herda | Keepit via Sbcl-help <
> [email protected]> wrote:
> >>
> >> Hello,
> >>
> >> we at Keepit might have run into a situation where the
> deadlock-checking in SBCL seems overzealous in some situations because of a
> race condition in target-thread.lisp.
> >>
> >> Here's the hypothetical scenario for threads T1 T2 and mutexes M1 M2:
> >>
> >> 1. T2 grabs M2.
> >> 2. T1 grabs M1.
> >> 3. T1 starts waiting for M2 (which is locked by T2)
> >> 4. T1 starts checking for deadlocks.
> >> 5. T1 sees that M2 belongs to T2.
> >> 6. T2 releases M2.
> >> 7. T2 starts waiting for M1 (which is locked by T1).
> >> 8. T1 continues to check deadlocks and sees that T2 is waiting for M1.
> >> 9. T1 sees that M1 belongs to itself.
> >> 10. T1 signals a deadlock, even though M2 is now free and the code can
> proceed.
> >>
> >> Our idea of patching this behavior is to add a handler around the call
> to DETECT-DEADLOCK that, in case of signaling, reattempts to verify the
> deadlock. This resolves this particular situation in the following way:
> >>
> >> 11. The deadlock is handled, T1 attempts to check for deadlocks again.
> >> 12. T1 sees no deadlock, because M2 is now free.
> >> 13. T1 grabs M2.
> >> 14. T1 has both mutexes, does work, releases mutexes.
> >>
> >> The below patch seems to have resolved the deadlocks we've been seeing
> in our deployed application on 2.3.7. Is the above solution valid? Can we
> come up with anything better? Is it possible to avoid the situation where a
> thread T3 can grab M2 in meantime, which would lead to another false
> positive?
> >>
> >> BR,
> >> Michał "phoe" Herda
> >>
> >> --------------
> >>
> >> diff --git a/src/code/target-thread.lisp b/src/code/target-thread.lisp
> >> index
> 795802c769f6169b664bbedc118994e81d8ef919..d25a3c6ede5ab5ba7ad26b54fce901b5a3badc55
> 100644
> >> --- a/src/code/target-thread.lisp
> >> +++ b/src/code/target-thread.lisp
> >> @@ -578,7 +578,13 @@ See also: RETURN-FROM-THREAD and SB-EXT:EXIT."
> >>                              (return-from check-deadlock nil)))))))
> >>        ;; Timeout means there is no deadlock
> >>        (when (mutex-p origin)
> >> -        (detect-deadlock origin)
> >> +        (handler-case (detect-deadlock origin)
> >> +          (thread-deadlock ()
> >> +            ;; Double-check.  If it's a true deadlock, it should stay
> >> +            (detect-deadlock origin)
> >> +            ;; Restore the waiting-for mark now that we know it was
> >> +            ;; a false positive
> >> +            (setf (thread-waiting-for self) origin)))
> >>          t))))
> >>
> >> ;;;; WAIT-FOR -- waiting on arbitrary conditions
> >>
> >>
> >>
> >> This e-mail is sent to you from Keepit A/S. Dedicated SaaS Data
> Protection.
> >> VAT: DK30806883, Per Henrik Lings Allé 4, 7., DK-2100 Copenhagen Ø,
> Denmark.
> >>
> >> This e-mail is sent to you directly and is meant for nobody else. If
> the e-mail contains personal data that Keepit is responsible for and the
> e-mail was not meant for you, please do not forward, distribute, or copy,
> i.e. but return the e-mail to sender. Also, do not send the e-mail to a
> third party without making sure that you have our prior consent.
> Distribution of this e-mail to unauthorized receivers may have legal
> consequences.
> >> If you have received an e-mail from us and you don’t know why, then
> please refer to our Privacy Policy.
> >> If you do not want to receive more e-mails from us, please contact
> [email protected].
> >> _______________________________________________
> >> Sbcl-help mailing list
> >> [email protected]
> >> https://lists.sourceforge.net/lists/listinfo/sbcl-help
> >
> > _______________________________________________
> > Sbcl-help mailing list
> > [email protected]
> > https://lists.sourceforge.net/lists/listinfo/sbcl-help
>

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