Prev: [PATCH 5/8] PM: suspend_block: Add suspend_blocker stats
Next: [PATCH/RFC] mutex: Fix optimistic spinning vs. BKL
From: Linus Torvalds on 11 May 2010 14:10


On Mon, 10 May 2010, Peter Zijlstra wrote:
>
> As to the 2 jiffy spin timeout, I guess we should add a lockdep warning
> for that, because anybody holding a mutex for longer than 2 jiffies and
> not sleeping does need fixing anyway.

I really hate the jiffies thing, but looking at the optimistic spinning, I
do wonder about two things..

First - we check "need_resched()" only if owner is NULL. That sounds
wrong. If we need to reschedule, we need to stop spinning _regardless_ of
whether the owner may have been preempted before setting the owner field.

Second: we allow "owner" to change, and we'll continue spinning. This is
how you can end up spinning for a long time - not because anybody holds
the mutex for longer than 2 jiffies, but because a lot of other threads
_together_ hold the mutex for longer than 2 jiffies.

Now, I think we do want some limited "continue spinning even if somebody
else ended up getting it instead", but I think we should at least limit
it. Otherwise we end up being potentially rather unfair, since we don't
have any fair queueing logic for the optimistic spinning phase.

Now, we could just count the number of times "owner" has changed, and I
suspect that would be sufficient. Now, that trivial counting sceme would
fail if "owner" stays the same (ie the same process re-takes the lock over
and over again, possibly due to hot cacheline things being very unfair
to the person who already owns it), but quite frankly, I don't think we
can get into that kind of situation.

Why? Mutexes may end up being very heavily contended, but they can't be
contended by just _one_ thread. So if we're really in a starvation issue,
the thread that is waiting _will_ see multiple different owners.

So once you have seen X number of other owners, you just say "screw it,
this spinning thing isn't working for me, I'll go to the sleeping case".

Of course, that is _really_ unfair. It will make it all that easier for
the other spinners to just get the lock by spinning. We used to have some
logic to say "we won't spin if there are proper waiters", but that was
horrible for performance. See commit ac6e60ee405.

Of course, it's quite possible that as long as "need_resched()" isn't set,
spinning really _is_ the right thing to do. Maybe it causes horrible CPU
load on some odd "everybody synchronize" loads, but maybe that really is
the best we can do.

Linus
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo(a)vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
From: Peter Zijlstra on 11 May 2010 14:30
On Tue, 2010-05-11 at 11:06 -0700, Linus Torvalds wrote:
>
> On Mon, 10 May 2010, Peter Zijlstra wrote:
> >
> > As to the 2 jiffy spin timeout, I guess we should add a lockdep warning
> > for that, because anybody holding a mutex for longer than 2 jiffies and
> > not sleeping does need fixing anyway.
>
> I really hate the jiffies thing, but looking at the optimistic spinning, I
> do wonder about two things..
>
> First - we check "need_resched()" only if owner is NULL. That sounds
> wrong. If we need to reschedule, we need to stop spinning _regardless_ of
> whether the owner may have been preempted before setting the owner field.

There is a second need_resched() in the inner spin loop in
kernel/sched.c:mutex_spin_on_owner().

> Second: we allow "owner" to change, and we'll continue spinning. This is
> how you can end up spinning for a long time - not because anybody holds
> the mutex for longer than 2 jiffies, but because a lot of other threads
> _together_ hold the mutex for longer than 2 jiffies.

Granted.

> Now, I think we do want some limited "continue spinning even if somebody
> else ended up getting it instead", but I think we should at least limit
> it. Otherwise we end up being potentially rather unfair, since we don't
> have any fair queueing logic for the optimistic spinning phase.
>
> Now, we could just count the number of times "owner" has changed, and I
> suspect that would be sufficient. Now, that trivial counting sceme would
> fail if "owner" stays the same (ie the same process re-takes the lock over
> and over again, possibly due to hot cacheline things being very unfair
> to the person who already owns it), but quite frankly, I don't think we
> can get into that kind of situation.
>
> Why? Mutexes may end up being very heavily contended, but they can't be
> contended by just _one_ thread. So if we're really in a starvation issue,
> the thread that is waiting _will_ see multiple different owners.
>
> So once you have seen X number of other owners, you just say "screw it,
> this spinning thing isn't working for me, I'll go to the sleeping case".

Right, so basically count the number of mutex_spin_on_owner() calls and
bail when >N.

> Of course, it's quite possible that as long as "need_resched()" isn't set,
> spinning really _is_ the right thing to do. Maybe it causes horrible CPU
> load on some odd "everybody synchronize" loads, but maybe that really is
> the best we can do.

Ben's argument was that spinning for a long time wrecks power usage.

That said, I'd still like a counter/event/warning to see if someone
actually manages to hold onto a mutex for long (2 jiffies) without
scheduling at all. If we ever run into something like that, that needs
to get fixed regardless.



--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo(a)vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
From: Benjamin Herrenschmidt on 11 May 2010 17:20
On Tue, 2010-05-11 at 11:06 -0700, Linus Torvalds wrote:
>
> On Mon, 10 May 2010, Peter Zijlstra wrote:
> >
> > As to the 2 jiffy spin timeout, I guess we should add a lockdep warning
> > for that, because anybody holding a mutex for longer than 2 jiffies and
> > not sleeping does need fixing anyway.
>
> I really hate the jiffies thing, but looking at the optimistic spinning, I
> do wonder about two things..
>
> First - we check "need_resched()" only if owner is NULL. That sounds
> wrong. If we need to reschedule, we need to stop spinning _regardless_ of
> whether the owner may have been preempted before setting the owner field.

The inner call mutex_spin_on_owner() checks it regardless (yeah, I
tripped on that too initially).

.../...

> Now, we could just count the number of times "owner" has changed, and I
> suspect that would be sufficient. Now, that trivial counting sceme would
> fail if "owner" stays the same (ie the same process re-takes the lock over
> and over again, possibly due to hot cacheline things being very unfair
> to the person who already owns it), but quite frankly, I don't think we
> can get into that kind of situation.

I've observed cases where owner didn't appear to change but we also
didn't trip on need_resched(), which leads me to wonder, if nobody is
contending to run on that processor, we may never set need_resched() and
end up spinning as long as the target is running.

This cause the deadlock with the BKL (which I fixed) but it also means
we may spend a long time without going to sleep, which means CPU not
dozed or returned to the hypervisor etc... for longer than needed.

That's the reasoning behind the jiffy timeout. It's not great but it
will get us out in some amount of time, which I wanted to guarantee.

.../...

> Of course, it's quite possible that as long as "need_resched()" isn't set,
> spinning really _is_ the right thing to do. Maybe it causes horrible CPU
> load on some odd "everybody synchronize" loads, but maybe that really is
> the best we can do.

Well, that happens at least occasionally but if you think that can be
safely ignored, then drop the jiffy timeout.

Cheers,
Ben.

> Linus
> --
> To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
> the body of a message to majordomo(a)vger.kernel.org
> More majordomo info at http://vger.kernel.org/majordomo-info.html
> Please read the FAQ at http://www.tux.org/lkml/


--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo(a)vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
From: Tony Breeds on 11 May 2010 19:10
On Tue, May 11, 2010 at 03:43:01PM +0000, tip-bot for Tony Breeds wrote:
> Commit-ID: 227945799cc10d77c6ef812f3eb8a61a78689454
> Gitweb: http://git.kernel.org/tip/227945799cc10d77c6ef812f3eb8a61a78689454
> Author: Tony Breeds <tony(a)bakeyournoodle.com>

For the record this is Ben's patch not mine, I just used time_before() to
address feedback.

Thanks for taking it though.

Yours Tony
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo(a)vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
From: Ingo Molnar on 18 May 2010 12:20

* tip-bot for Tony Breeds <tony(a)bakeyournoodle.com> wrote:

> Commit-ID: 227945799cc10d77c6ef812f3eb8a61a78689454
> Gitweb: http://git.kernel.org/tip/227945799cc10d77c6ef812f3eb8a61a78689454
> Author: Tony Breeds <tony(a)bakeyournoodle.com>
> AuthorDate: Fri, 7 May 2010 14:20:10 +1000
> Committer: Ingo Molnar <mingo(a)elte.hu>
> CommitDate: Tue, 11 May 2010 17:07:24 +0200
>
> mutex: Fix optimistic spinning vs. BKL

Tony, mind sending a version of this patch that does not
include a jiffies based spinning loop?

Thanks,

Ingo
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo(a)vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
First  |  Prev  |  Next  |  Last
Pages: 1 2 3 4
Prev: [PATCH 5/8] PM: suspend_block: Add suspend_blocker stats
Next: [PATCH/RFC] mutex: Fix optimistic spinning vs. BKL