linux-kernel.vger.kernel.org archive mirror
 help / color / mirror / Atom feed
From: Peter Zijlstra <peterz@infradead.org>
To: Steven Rostedt <rostedt@goodmis.org>
Cc: LKML <linux-kernel@vger.kernel.org>,
	Ingo Molnar <mingo@kernel.org>,
	Thomas Gleixner <tglx@linutronix.de>,
	Clark Williams <williams@redhat.com>,
	Andrew Morton <akpm@linux-foundation.org>,
	Nick Piggin <nickpiggin@yahoo.com.au>
Subject: Re: [PATCH] sched: Do not release current rq lock on non contended double_lock_balance()
Date: Tue, 14 Jun 2016 13:58:20 +0200	[thread overview]
Message-ID: <20160614115820.GD30921@twins.programming.kicks-ass.net> (raw)
In-Reply-To: <20160613123732.3a8ccc57@gandalf.local.home>

On Mon, Jun 13, 2016 at 12:37:32PM -0400, Steven Rostedt wrote:
> The solution was to simply release the current (this_rq) lock and then
> take both locks.
> 
> 	spin_unlock(&this_rq->lock);
> 	double_rq_lock(this_rq, busiest);

> What I could not understand about Gregory's patch is that regardless of
> contention, the currently held lock is always released, opening up a
> window for this ping ponging to occur. When I changed the code to only
> release on contention of the second lock, things improved tremendously.

Its simpler to reason about and there wasn't a problem with at the time.

The above puts a strict limit on hold time and is fair because of the
queueing.

> +++ b/kernel/sched/sched.h
> @@ -1548,10 +1548,15 @@ static inline int _double_lock_balance(struct rq *this_rq, struct rq *busiest)
>  	__acquires(busiest->lock)
>  	__acquires(this_rq->lock)
>  {
> +	int ret = 0;
> +
> +	if (unlikely(!raw_spin_trylock(&busiest->lock))) {
> +		raw_spin_unlock(&this_rq->lock);
> +		double_rq_lock(this_rq, busiest);
> +		ret = 1;
> +	}
>  
> +	return ret;
>  }

This relies on trylock no being allowed to steal the lock, which I think
is true for all fair spinlocks (for ticket this must be true, but it is
possible with qspinlock for example).

And it does indeed make the hold time harder to analyze.

For instance; pull_rt_task() does:

	for_each_cpu() {
		double_lock_balance(this, that);
		...
		double_unlock_balance(this, that);
	}

Which, with the trylock, ends up with a max possible hold time of
O(nr_cpus).

Unlikely, sure, but RT is a game of upper bounds etc.

So should we maybe do something like:

	if (unlikely(raw_spin_is_contended(&this_rq->lock) ||
	             !raw_spin_trylock(&busiest->lock))) {
		raw_spin_unlock(&this_rq->lock);
		double_rq_lock(this_rq, busiest);
		ret = 1;
	}

?

> 	CPU 0				CPU 1
> 	-----				-----
>     [ wake up ]
> 				     spin_lock(cpu1_rq->lock);
>     spin_lock(cpu1_rq->lock)
> 				    double_lock_balance()
> 				    [ release cpu1_rq->lock ]
> 				    spin_lock(cpu1_rq->lock)
>     [due to ticket, now acquires
>      cpu1_rq->lock ]
> 
>     [goes to push task]
>     double_lock_balance()
>     [ release cpu1_rq->lock ]
>                                    [ acquires lock ]
> 				   spin_lock(cpu2_rq->lock)
> 				   [ blocks as cpu2 is using it ]
> 

Also, its not entirely clear this scenario helps illustrate how your
change is better; because here the lock _is_ contended, so we'll fail
the trylock, no?

  reply	other threads:[~2016-06-14 11:58 UTC|newest]

Thread overview: 7+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2016-06-13 16:37 Steven Rostedt
2016-06-14 11:58 ` Peter Zijlstra [this message]
2016-06-14 17:52   ` Steven Rostedt
2016-06-14 18:02   ` Steven Rostedt
2016-06-14 19:42     ` Peter Zijlstra
2016-06-15 11:14     ` Peter Zijlstra
2016-06-15 16:13       ` Steven Rostedt

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=20160614115820.GD30921@twins.programming.kicks-ass.net \
    --to=peterz@infradead.org \
    --cc=akpm@linux-foundation.org \
    --cc=linux-kernel@vger.kernel.org \
    --cc=mingo@kernel.org \
    --cc=nickpiggin@yahoo.com.au \
    --cc=rostedt@goodmis.org \
    --cc=tglx@linutronix.de \
    --cc=williams@redhat.com \
    --subject='Re: [PATCH] sched: Do not release current rq lock on non contended double_lock_balance()' \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).