Re: False positives in deadlock detection

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