Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > linux.kernel > #1720724 > unrolled thread

[PATCH RFC/RFT] sched/fair: Improve the behavior of sync flag

Back to article view | Back to linux.kernel

Contents

  [PATCH RFC/RFT] sched/fair: Improve the behavior of sync flag Joel Fernandes <joelaf@google.com> - 2017-08-27 03:10 +0200
    Re: [PATCH RFC/RFT] sched/fair: Improve the behavior of sync flag Mike Galbraith <efault@gmx.de> - 2017-08-27 07:50 +0200
      Re: [PATCH RFC/RFT] sched/fair: Improve the behavior of sync flag Mike Galbraith <efault@gmx.de> - 2017-08-27 08:10 +0200
        Re: [PATCH RFC/RFT] sched/fair: Improve the behavior of sync flag Joel Fernandes <joelaf@google.com> - 2017-08-27 08:40 +0200
          Re: [PATCH RFC/RFT] sched/fair: Improve the behavior of sync flag Mike Galbraith <efault@gmx.de> - 2017-08-27 09:20 +0200
          Re: [PATCH RFC/RFT] sched/fair: Improve the behavior of sync flag Mike Galbraith <efault@gmx.de> - 2017-08-27 20:10 +0200
            Re: [PATCH RFC/RFT] sched/fair: Improve the behavior of sync flag Joel Fernandes <joelaf@google.com> - 2017-08-28 07:30 +0200
              Re: [PATCH RFC/RFT] sched/fair: Improve the behavior of sync flag Mike Galbraith <efault@gmx.de> - 2017-08-28 08:20 +0200
                Re: [PATCH RFC/RFT] sched/fair: Improve the behavior of sync flag Mike Galbraith <efault@gmx.de> - 2017-08-28 08:50 +0200
                Re: [PATCH RFC/RFT] sched/fair: Improve the behavior of sync flag Joel Fernandes <joelaf@google.com> - 2017-08-28 18:30 +0200
                  Re: [PATCH RFC/RFT] sched/fair: Improve the behavior of sync flag Mike Galbraith <efault@gmx.de> - 2017-08-28 19:20 +0200
      Re: [PATCH RFC/RFT] sched/fair: Improve the behavior of sync flag Joel Fernandes <joelaf@google.com> - 2017-08-27 08:30 +0200
      Re: [PATCH RFC/RFT] sched/fair: Improve the behavior of sync flag Mike Galbraith <efault@gmx.de> - 2017-08-27 09:00 +0200

#1720724 — [PATCH RFC/RFT] sched/fair: Improve the behavior of sync flag

Binder (Android's IPC mechanism) which uses sync wake ups during synchronous
transactions to the scheduler to indicate that the waker is about to sleep
soon. The current wake up path can improved when the sync flag is passed
resulting in higher binder performance. In this patch we more strongly wake up
the wakee on the waker's CPU if sync is passed based on a few other conditions
such as wake_cap, cpus allowed.  wake_wide is checked only after the sync flag
check so that it doesn't mess up sync.  Binder throughput tests see good
improvement improvement when waking up wakee (calling thread) on the waker's
CPU (called thread) with this flag. Some tests results are below:

On an 8-core ARM64 system, following is data from running
hwbinderThroughputTest with variable number of workers and services (the
workers are clients calling into the service threads and sleeps till the
service replies to them).

2 workers calling into 4 services:
Without patch: iterations per sec: 62757
With patch:    iterations per sec: 75236 (+19.88%)

4 workers calling into 2 services:
Without patch: iterations per sec: 82379
With patch:    iterations per sec: 85829 (+4.18%)

Cc: Peter Zijlstra <peterz@infradead.org>
Cc: Josef Bacik <jbacik@fb.com>
Cc: Juri Lelli <Juri.Lelli@arm.com>
Cc: Brendan Jackman <brendan.jackman@arm.com>
Cc: Dietmar Eggemann <dietmar.eggemann@arm.com>
Cc: Matt Fleming <matt@codeblueprint.co.uk>
Cc: Rik van Riel <riel@redhat.com>
Signed-off-by: Joel Fernandes <joelaf@google.com>
---
Rik, as we discussed on IRC I am hoping that the lkp bot will also do its own
tests with this patch. I'm not sure if anything special needs to be in the
subject line to trigger the tests, if that's the case let me know and thanks!

 kernel/sched/fair.c | 15 ++++++++++++---
 1 file changed, 12 insertions(+), 3 deletions(-)

diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
index eca6a57527f9..808571bc8ebe 100644
--- a/kernel/sched/fair.c
+++ b/kernel/sched/fair.c
@@ -6276,10 +6276,19 @@ select_task_rq_fair(struct task_struct *p, int prev_cpu, int sd_flag, int wake_f
 	int want_affine = 0;
 	int sync = wake_flags & WF_SYNC;
 
-	if (sd_flag & SD_BALANCE_WAKE) {
+	if (sd_flag & SD_BALANCE_WAKE)
 		record_wakee(p);
-		want_affine = !wake_wide(p) && !wake_cap(p, cpu, prev_cpu)
-			      && cpumask_test_cpu(cpu, &p->cpus_allowed);
+
+	if ((sd_flag & SD_BALANCE_WAKE) && !wake_cap(p, cpu, prev_cpu)
+	    && cpumask_test_cpu(cpu, &p->cpus_allowed)) {
+		/*
+		 * WF_SYNC indicates waker will goto sleep, incase waker is
+		 * the only one running, select the waker's CPU to run wakee
+		 */
+		if (sync && cpu_rq(cpu)->nr_running < 2)
+			return cpu;
+
+		want_affine = !wake_wide(p);
 	}
 
 	rcu_read_lock();
-- 
2.14.1.342.g6490525c54-goog

[toc] | [next] | [standalone]

#1720742

On Sat, 2017-08-26 at 18:02 -0700, Joel Fernandes wrote:
> Binder (Android's IPC mechanism) which uses sync wake ups during synchronous
> transactions to the scheduler to indicate that the waker is about to sleep
> soon. The current wake up path can improved when the sync flag is passed
> resulting in higher binder performance. In this patch we more strongly wake up
> the wakee on the waker's CPU if sync is passed based on a few other conditions
> such as wake_cap, cpus allowed.  wake_wide is checked only after the sync flag
> check so that it doesn't mess up sync.  Binder throughput tests see good
> improvement improvement when waking up wakee (calling thread) on the waker's
> CPU (called thread) with this flag. Some tests results are below:

Sync is not a contract, it's a hint.  If you really want sync behavior,
you need to create a contract signed in blood to signal that you really
really are passing the baton.

Sync wakeups make tons of sense when the waker really really has one
and only one wakee, AND really really is going to sleep immediately,
with zero overlap that can be converted to throughput by waking to an
idle core.  With no L2 misses to slow them down, pass the baton
microbenchmarks that do no real work can generate impressive ping-pong
numbers... but the real world tends to do more than just bat a byte
around endlessly.  The existing hint is not strong enough for your
needs, it's current users may overlap with their wakee(s), change their
minds about sleeping (be handed more work to do) etc etc.

	-Mike

[toc] | [prev] | [next] | [standalone]

#1720747

On Sun, 2017-08-27 at 07:44 +0200, Mike Galbraith wrote:
> On Sat, 2017-08-26 at 18:02 -0700, Joel Fernandes wrote:
> > Binder (Android's IPC mechanism) which uses sync wake ups during synchronous
> > transactions to the scheduler to indicate that the waker is about to sleep
> > soon. The current wake up path can improved when the sync flag is passed
> > resulting in higher binder performance. In this patch we more strongly wake up
> > the wakee on the waker's CPU if sync is passed based on a few other conditions
> > such as wake_cap, cpus allowed.  wake_wide is checked only after the sync flag
> > check so that it doesn't mess up sync.  Binder throughput tests see good
> > improvement improvement when waking up wakee (calling thread) on the waker's
> > CPU (called thread) with this flag. Some tests results are below:
> 
> Sync is not a contract, it's a hint.  If you really want sync behavior,
> you need to create a contract signed in blood to signal that you really
> really are passing the baton.

P.S. to get the most bang for your synchronous buck, you want a
preemptive wakeup.. but that butts heads with the fair engine.

	-Mike

[toc] | [prev] | [next] | [standalone]

#1720753

Hi Mike,

On Sat, Aug 26, 2017 at 11:08 PM, Mike Galbraith <efault@gmx.de> wrote:
> On Sun, 2017-08-27 at 07:44 +0200, Mike Galbraith wrote:
>> On Sat, 2017-08-26 at 18:02 -0700, Joel Fernandes wrote:
>> > Binder (Android's IPC mechanism) which uses sync wake ups during synchronous
>> > transactions to the scheduler to indicate that the waker is about to sleep
>> > soon. The current wake up path can improved when the sync flag is passed
>> > resulting in higher binder performance. In this patch we more strongly wake up
>> > the wakee on the waker's CPU if sync is passed based on a few other conditions
>> > such as wake_cap, cpus allowed.  wake_wide is checked only after the sync flag
>> > check so that it doesn't mess up sync.  Binder throughput tests see good
>> > improvement improvement when waking up wakee (calling thread) on the waker's
>> > CPU (called thread) with this flag. Some tests results are below:
>>
>> Sync is not a contract, it's a hint.  If you really want sync behavior,
>> you need to create a contract signed in blood to signal that you really
>> really are passing the baton.
>
> P.S. to get the most bang for your synchronous buck, you want a
> preemptive wakeup.. but that butts heads with the fair engine.
>

By preemptive wake up I guess you mean the waker would give up its
time slice and let the wakee use it? That's a cool idea but I agree it
would be against the fair task behavior.

Also about real world benchmarks, in Android we have usecases that
show that the graphics performance and we have risk of frame drops if
we don't use the sync flag so this is a real world need. Binder is the
backbone of Android and for the benefit of these usecases, Android
kernels make sync a contract (written in blood as you put it).

thanks,

-Joel


>         -Mike

[toc] | [prev] | [next] | [standalone]

#1720770

On Sat, 2017-08-26 at 23:39 -0700, Joel Fernandes wrote:
> 
> > P.S. to get the most bang for your synchronous buck, you want a
> > preemptive wakeup.. but that butts heads with the fair engine.
> >
> 
> By preemptive wake up I guess you mean the waker would give up its
> time slice and let the wakee use it? That's a cool idea but I agree it
> would be against the fair task behavior.

No, I meant a preemption, that being the cheapest switch.  Any mucking
about with vruntime is a non-starter (NAK bait), making guaranteed
preemption a non-starter.

	-Mike 

[toc] | [prev] | [next] | [standalone]

#1720900

On Sat, 2017-08-26 at 23:39 -0700, Joel Fernandes wrote:
> 
> Also about real world benchmarks, in Android we have usecases that
> show that the graphics performance and we have risk of frame drops if
> we don't use the sync flag so this is a real world need.

That likely has everything to do with cpufreq not realizing that your
CPUs really are quite busy when scheduling cross core at fairly high
frequency, and not clocking up properly.

	-Mike

[toc] | [prev] | [next] | [standalone]

#1721030

Hi Mike,

On Sun, Aug 27, 2017 at 11:07 AM, Mike Galbraith <efault@gmx.de> wrote:
> On Sat, 2017-08-26 at 23:39 -0700, Joel Fernandes wrote:
>>
>> Also about real world benchmarks, in Android we have usecases that
>> show that the graphics performance and we have risk of frame drops if
>> we don't use the sync flag so this is a real world need.
>
> That likely has everything to do with cpufreq not realizing that your
> CPUs really are quite busy when scheduling cross core at fairly high
> frequency, and not clocking up properly.
>

I'm glad you brought this point up. Since Android O, the userspace
processes are much more split across procedure calls due to a feature
called treble (which does this for security, modularity etc). Due to
this, a lot of things that were happening within a process boundary
happen now across process boundaries over the binder bus. Early on
folks noticed that this caused performance issues without sync flag
being used as a more strong hint. This can happen when there are 2
threads are in different frequency domains on different CPUs and are
communicating over binder, due to this the combined load of both
threads is divided between the individual CPUs and causes them to run
at lower frequency. Where as if they are running together on the same
CPUs, then they would run at a higher frequency and perform better as
their combined load would run at a higher frequency. So a stronger
sync actually helps this case if we're careful about using it when
possible.

thanks,

-Joel



>         -Mike

[toc] | [prev] | [next] | [standalone]

#1721046

On Sun, 2017-08-27 at 22:27 -0700, Joel Fernandes wrote:
> Hi Mike,
> 
> On Sun, Aug 27, 2017 at 11:07 AM, Mike Galbraith <efault@gmx.de> wrote:
> > On Sat, 2017-08-26 at 23:39 -0700, Joel Fernandes wrote:
> >>
> >> Also about real world benchmarks, in Android we have usecases that
> >> show that the graphics performance and we have risk of frame drops if
> >> we don't use the sync flag so this is a real world need.
> >
> > That likely has everything to do with cpufreq not realizing that your
> > CPUs really are quite busy when scheduling cross core at fairly high
> > frequency, and not clocking up properly.
> >
> 
> I'm glad you brought this point up. Since Android O, the userspace
> processes are much more split across procedure calls due to a feature
> called treble (which does this for security, modularity etc). Due to
> this, a lot of things that were happening within a process boundary
> happen now across process boundaries over the binder bus. Early on
> folks noticed that this caused performance issues without sync flag
> being used as a more strong hint. This can happen when there are 2
> threads are in different frequency domains on different CPUs and are
> communicating over binder, due to this the combined load of both
> threads is divided between the individual CPUs and causes them to run
> at lower frequency. Where as if they are running together on the same
> CPUs, then they would run at a higher frequency and perform better as
> their combined load would run at a higher frequency. So a stronger
> sync actually helps this case if we're careful about using it when
> possible.

Sure, but isn't that really a cpufreq issue?  We schedule cross core
quite aggressively for obvious reasons.  Now on mostly idle handheld
devices, you may get better battery life by stacking tasks a bit more,
in which case a sync-me-harder flag may be what you really want/need,
but with modern CPUs, I'm kinda skeptical of that, would have to see
cold hard numbers to become a believer.  Iff deeper cstate etc for
longer does make a big difference, I can imagine wakeup time migrate
leftward if capacity exists as an "on battery" tactic. (though that
thought also invokes some unpleasant bounce fest images)

	-Mike

[toc] | [prev] | [next] | [standalone]

#1721056

On Mon, 2017-08-28 at 08:10 +0200, Mike Galbraith wrote:
> Iff deeper cstate etc for
> longer does make a big difference, I can imagine wakeup time migrate
> leftward if capacity exists as an "on battery" tactic. (though that
> thought also invokes some unpleasant bounce fest images)

(consolidate left would have to be LB global to avoid fight with self)

[toc] | [prev] | [next] | [standalone]

#1721790

Hi Mike,

On Sun, Aug 27, 2017 at 11:10 PM, Mike Galbraith <efault@gmx.de> wrote:
> On Sun, 2017-08-27 at 22:27 -0700, Joel Fernandes wrote:
>> Hi Mike,
>>
>> On Sun, Aug 27, 2017 at 11:07 AM, Mike Galbraith <efault@gmx.de> wrote:
>> > On Sat, 2017-08-26 at 23:39 -0700, Joel Fernandes wrote:
>> >>
>> >> Also about real world benchmarks, in Android we have usecases that
>> >> show that the graphics performance and we have risk of frame drops if
>> >> we don't use the sync flag so this is a real world need.
>> >
>> > That likely has everything to do with cpufreq not realizing that your
>> > CPUs really are quite busy when scheduling cross core at fairly high
>> > frequency, and not clocking up properly.
>> >
>>
>> I'm glad you brought this point up. Since Android O, the userspace
>> processes are much more split across procedure calls due to a feature
>> called treble (which does this for security, modularity etc). Due to
>> this, a lot of things that were happening within a process boundary
>> happen now across process boundaries over the binder bus. Early on
>> folks noticed that this caused performance issues without sync flag
>> being used as a more strong hint. This can happen when there are 2
>> threads are in different frequency domains on different CPUs and are
>> communicating over binder, due to this the combined load of both
>> threads is divided between the individual CPUs and causes them to run
>> at lower frequency. Where as if they are running together on the same
>> CPUs, then they would run at a higher frequency and perform better as
>> their combined load would run at a higher frequency. So a stronger
>> sync actually helps this case if we're careful about using it when
>> possible.
>
> Sure, but isn't that really a cpufreq issue?  We schedule cross core

IMO its an issue with the scheduler not being aware of the
relationship between groups of tasks doing work as a pipeline. Sync
seems to me one way to communicate that.

> quite aggressively for obvious reasons.  Now on mostly idle handheld
> devices, you may get better battery life by stacking tasks a bit more,
> in which case a sync-me-harder flag may be what you really want/need,
> but with modern CPUs, I'm kinda skeptical of that, would have to see
> cold hard numbers to become a believer.  Iff deeper cstate etc for

If you can suggest any tests, I could run them on my Intel machine? By
the way CPUs on handhelds are pretty modern these days ;-)

> longer does make a big difference, I can imagine wakeup time migrate
> leftward if capacity exists as an "on battery" tactic. (though that
> thought also invokes some unpleasant bounce fest images)

I'm assuming you mean that tasks are packed together more closely and
scheduled on energy aware CPUs at wake up time. This is exactly what
we do in the Energy aware scheduling (EAS) that ARM has been working
on and is integrated into the Android kernels but its being done
whether on battery or plugged in. Also instead of migrating leftward
or a fixed diretion, it checks for what would the changes in energy be
based on an "energy model" and the current utilization before deciding
on whether to wake up on a different CPU. Its also not perfect and is
an approximation but overall seems to provide good energy savings.

thanks,

-Joel


>
>         -Mike

[toc] | [prev] | [next] | [standalone]

#1721826

On Mon, 2017-08-28 at 09:20 -0700, Joel Fernandes wrote:
> Hi Mike,
> 
> On Sun, Aug 27, 2017 at 11:10 PM, Mike Galbraith <efault@gmx.de> wrote:
> > On Sun, 2017-08-27 at 22:27 -0700, Joel Fernandes wrote:
> >> Hi Mike,
> >>
> >> On Sun, Aug 27, 2017 at 11:07 AM, Mike Galbraith <efault@gmx.de> wrote:
> >> > On Sat, 2017-08-26 at 23:39 -0700, Joel Fernandes wrote:
> >> >>
> >> >> Also about real world benchmarks, in Android we have usecases that
> >> >> show that the graphics performance and we have risk of frame drops if
> >> >> we don't use the sync flag so this is a real world need.
> >> >
> >> > That likely has everything to do with cpufreq not realizing that your
> >> > CPUs really are quite busy when scheduling cross core at fairly high
> >> > frequency, and not clocking up properly.
> >> >
> >>
> >> I'm glad you brought this point up. Since Android O, the userspace
> >> processes are much more split across procedure calls due to a feature
> >> called treble (which does this for security, modularity etc). Due to
> >> this, a lot of things that were happening within a process boundary
> >> happen now across process boundaries over the binder bus. Early on
> >> folks noticed that this caused performance issues without sync flag
> >> being used as a more strong hint. This can happen when there are 2
> >> threads are in different frequency domains on different CPUs and are
> >> communicating over binder, due to this the combined load of both
> >> threads is divided between the individual CPUs and causes them to run
> >> at lower frequency. Where as if they are running together on the same
> >> CPUs, then they would run at a higher frequency and perform better as
> >> their combined load would run at a higher frequency. So a stronger
> >> sync actually helps this case if we're careful about using it when
> >> possible.
> >
> > Sure, but isn't that really a cpufreq issue?  We schedule cross core
> 
> IMO its an issue with the scheduler not being aware of the
> relationship between groups of tasks doing work as a pipeline. Sync
> seems to me one way to communicate that.

It's certainly simple, which is requirement #1.

> > quite aggressively for obvious reasons.  Now on mostly idle handheld
> > devices, you may get better battery life by stacking tasks a bit more,
> > in which case a sync-me-harder flag may be what you really want/need,
> > but with modern CPUs, I'm kinda skeptical of that, would have to see
> > cold hard numbers to become a believer.  Iff deeper cstate etc for
> 
> If you can suggest any tests, I could run them on my Intel machine? By
> the way CPUs on handhelds are pretty modern these days ;-)

Nah, that would be wasting your time doing what I could do myself.

> > longer does make a big difference, I can imagine wakeup time migrate
> > leftward if capacity exists as an "on battery" tactic. (though that
> > thought also invokes some unpleasant bounce fest images)
> 
> I'm assuming you mean that tasks are packed together more closely and
> scheduled on energy aware CPUs at wake up time. This is exactly what
> we do in the Energy aware scheduling (EAS) that ARM has been working
> on and is integrated into the Android kernels but its being done
> whether on battery or plugged in. Also instead of migrating leftward
> or a fixed diretion, it checks for what would the changes in energy be
> based on an "energy model" and the current utilization before deciding
> on whether to wake up on a different CPU. Its also not perfect and is
> an approximation but overall seems to provide good energy savings.

OK, so you're already doing some packing.

Personally, I still think that there's a bit of a disconnect between
cpufreq and scheduler, but that aside, sync was invented for what
you're trying to do.  If you can improve it without wreckage, cool,
generic improvement rocks, so good luck.

	-Mike

[toc] | [prev] | [next] | [standalone]

#1720751

(Sorry my last reply was incorrectly formatted, resending..)

Hi Mike,

On Sat, Aug 26, 2017 at 10:44 PM, Mike Galbraith <efault@gmx.de> wrote:
> On Sat, 2017-08-26 at 18:02 -0700, Joel Fernandes wrote:
>> Binder (Android's IPC mechanism) which uses sync wake ups during
synchronous
>> transactions to the scheduler to indicate that the waker is about to
sleep
>> soon. The current wake up path can improved when the sync flag is passed
>> resulting in higher binder performance. In this patch we more strongly
wake up
>> the wakee on the waker's CPU if sync is passed based on a few other
conditions
>> such as wake_cap, cpus allowed.  wake_wide is checked only after the
sync flag
>> check so that it doesn't mess up sync.  Binder throughput tests see good
>> improvement improvement when waking up wakee (calling thread) on the
waker's
>> CPU (called thread) with this flag. Some tests results are below:
>
> Sync is not a contract, it's a hint.  If you really want sync behavior,
> you need to create a contract signed in blood to signal that you really
> really are passing the baton.

Yes that is the usecase of binder, we are really passing the baton when we
pass sync. We also make binder to not pass sync if there's more work todo
and more tasks to wake up. In all current and past products, we have been
using sync has a hard contract as you said. Are you proposing addition of
another flag to differentiate between the existing hint and the contract?

I tried making sync be ignored if wake_wide = 1 as well but its not working
well for our use cases and hurts performance.

> Sync wakeups make tons of sense when the waker really really has one
> and only one wakee, AND really really is going to sleep immediately,

Yes that is the case of binder. If we're going to be doing more work and
waking up others before going to sleep, we wouldn't pass sync.

Binder is actually an RPC mechanism, where the calling thread and called
thread are essentially a single entity but are split across process
boundaries. By using thread pools, we increase the likelihood that there's
a single thread available for each caller which will go back to sleep after
replying.

> with zero overlap that can be converted to throughput by waking to an
> idle core.

That's exactly why the micro benchmark too speeds up, from our observation
the wake up of an idle core increases the latency (it probably also wastes
power).

thanks,

-Joel

[toc] | [prev] | [next] | [standalone]

#1720765

On Sat, 2017-08-26 at 23:18 -0700, Joel Fernandes wrote:
> 
> > Sync is not a contract, it's a hint.  If you really want sync behavior,
> > you need to create a contract signed in blood to signal that you really
> > really are passing the baton.
> 
> Yes that is the usecase of binder, we are really passing the baton
> when we pass sync. We also make binder to not pass sync if there's
> more work todo and more tasks to wake up. In all current and past
> products, we have been using sync has a hard contract as you said.
> Are you proposing addition of another flag to differentiate between
> the existing hint and the contract?

Yes, the alternative being to unilaterally (as you did) make the
existing hint a contract, in which case you would get to deal with any
fallout.  You'd certainly get some "yay, you rock" mail, but you'd also
get some "boo, you suck rocks" to go with it :)

	-Mike

[toc] | [prev] | [standalone]

Back to top | Article view | linux.kernel

csiph-web