Incorrect comparison of ticks in deadlkres

[Attilio Rao]

On Sat, May 25, 2013 at 11:55 PM, Ryan Stone <rysto32 at gmail.com> wrote:
> Currently deadlkres performs the following comparison when trying to check
> for threads that have been blocked on a mutex or sleeping on an sx lock:
>
> if (TD_ON_LOCK(td) && ticks < td->td_blktick) {
>     /* check for deadlock...*/

Yes the check looks indeed inverted.

>
>
> The test against ticks is incorrect.  It results in deadlkres only
> signaling a deadlock after ticks has rolled over; at 1000 hz this will take
> up to 49 days.  From looking at the history of the code this test appears
> to be a attempt to deal with ticks rollover.  However this is necessary;
> later on the code calculates the amount of time that has passed with:
> tticks = ticks - td->td_blktick;
>
> ticks was designed to exploit integer underflow in the case of rollover to
> guarantee that subtraction produces correct results in all cases (other
> than a double rollover, of course).  I am going to remove the two incorrect
> tests unless somebody can point out a overflow/underflow case that I
> haven't considered.

I'm not sure I follow what are you saying.
Assume that when thread td goes to sleep, ticks is very close to the
32 bits limit. Then thread td goes to sleep and td->td_blktick is set
to a value very close to 32 bits limits.
After a while deadlkres thread kicks in and in the while "ticks"
counter overflowed, rolling back to a very low value. How are you
supposed to compute a valid value from this situation?
I think that you need to still guard about overflow of ticks for such cases.

Additively, if you really want to improve deadlkres, you should bring
into the logic a fix for the adaptive spinning. Think about the
schematic LOR case. Because of the adaptive spinning what will happen
is that 2 threads getting a deadlock on 2 different locks will just
end up spinning. I think you should import some sort of checks just
like spinmutexes do, but with much higher time threshhold.

Attilio


--
Peace can only be achieved by understanding - A. Einstein