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

Groups > linux.kernel > #1680812 > unrolled thread

Re: [RFC][PATCH] sched: attach extra runtime to the right avg

Back to article view | Back to linux.kernel

This discussion starts older than the indexed window; earlier articles aren't shown. The article labeled Started by below is the oldest one visible, not the original post.

Contents

  Re: [RFC][PATCH] sched: attach extra runtime to the right avg Peter Zijlstra <peterz@infradead.org> - 2017-07-04 11:50 +0200
    Re: [RFC][PATCH] sched: attach extra runtime to the right avg Ingo Molnar <mingo@kernel.org> - 2017-07-04 12:20 +0200
      Re: [RFC][PATCH] sched: attach extra runtime to the right avg Peter Zijlstra <peterz@infradead.org> - 2017-07-04 14:30 +0200
        Re: [RFC][PATCH] sched: attach extra runtime to the right avg Josef Bacik <josef@toxicpanda.com> - 2017-07-04 14:50 +0200
        Re: [RFC][PATCH] sched: attach extra runtime to the right avg Peter Zijlstra <peterz@infradead.org> - 2017-07-04 14:50 +0200
          Re: [RFC][PATCH] sched: attach extra runtime to the right avg Josef Bacik <josef@toxicpanda.com> - 2017-07-04 16:00 +0200
            Re: [RFC][PATCH] sched: attach extra runtime to the right avg Peter Zijlstra <peterz@infradead.org> - 2017-07-04 16:30 +0200

#1680812 — Re: [RFC][PATCH] sched: attach extra runtime to the right avg

On Sun, Jul 02, 2017 at 11:37:18AM +0200, Ingo Molnar wrote:
> * josef@toxicpanda.com <josef@toxicpanda.com> wrote:
> 
> > From: Josef Bacik <jbacik@fb.com>
> > 
> > We only track the load avg of a se in 1024 ns chunks, so in order to
> > make up for the loss of the < 1024 ns part of a run/sleep delta we only
> > add the time we processed to the se->avg.last_update_time.  The problem
> > is there is no way to know if this extra time was while we were asleep
> > or while we were running.  Instead keep track of the remainder and apply
> > it in the appropriate place.  If the remainder was while we were
> > running, add it to the delta the next time we update the load avg while
> > running, and the same for sleeping.  This (coupled with other fixes)
> > mostly fixes the regression to my workload introduced by Peter's
> > experimental runnable load propagation patches.
> > 
> > Signed-off-by: Josef Bacik <jbacik@fb.com>
> 
> > @@ -2897,12 +2904,16 @@ ___update_load_avg(u64 now, int cpu, struct sched_avg *sa,
> >  	 * Use 1024ns as the unit of measurement since it's a reasonable
> >  	 * approximation of 1us and fast to compute.
> >  	 */
> > +	remainder = delta & (1023UL);
> > +	sa->last_update_time = now;
> > +	if (running)
> > +		sa->run_remainder = remainder;
> > +	else
> > +		sa->sleep_remainder = remainder;
> >  	delta >>= 10;
> >  	if (!delta)
> >  		return 0;
> >  
> > -	sa->last_update_time += delta << 10;
> > -
> 
> So I'm wondering, this chunk changes how sa->last_update_time is maintained in 
> ___update_load_avg(): the new code takes a precise timestamp, but the old code was 
> not taking an imprecise timestamp, but was updating it via deltas - where each 
> delta was rounded down to the nearest 1024 nsecs boundary.

Right..

> That, if this is the main code path that updates ->last_update_time, creates a 
> constant drift of rounding error that skews ->last_update_time into larger and 
> larger distances from the real 'now' - ever increasing the value of 'delta'.

Well, its a 0-sum. It doesn't drift unbounded. The difference will grow
up to 1023, at which point we'll account for it whole and we're back to
0.

The problem is that there's two states: running, blocked. And the
current scheme does not differentiate. We'll accrue the sub-block and
spill it into whatever state gets lucky.

Now, on average you'd hope that that works out and both running and
blocked get an equal number of spills pro-rata.

But apparently this isn't quite working out for Josef.

> An intermediate approach to improve that skew would be something like below. It 
> doesn't track the remainder like your patch does, but doesn't lose precision 
> either, just rounds down 'now' to the nearest 1024 boundary.


> diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
> index 008c514dc241..b03703cd7989 100644
> --- a/kernel/sched/fair.c
> +++ b/kernel/sched/fair.c
> @@ -2965,7 +2965,7 @@ ___update_load_avg(u64 now, int cpu, struct sched_avg *sa,
>  	if (!delta)
>  		return 0;
>  
> -	sa->last_update_time += delta << 10;
> +	sa->last_update_time = now & ~1023ULL;
>  

So if we have a task that always runs <1024ns it should still get blocks
of runtime because the difference between now and now&~1023 can be !0
and spill.

I'm just not immediately seeing how its different from the 0-sum we had.
It should be identical since delta*1024 would equally land us on those
same edges (there's an offset in the differential form between the two,
but since we start with last_update_time=0, the resulting edges are the
same afaict).


*confused*

[toc] | [next] | [standalone]

#1680840

* Peter Zijlstra <peterz@infradead.org> wrote:

> > An intermediate approach to improve that skew would be something like below. 
> > It doesn't track the remainder like your patch does, but doesn't lose 
> > precision either, just rounds down 'now' to the nearest 1024 boundary.
> 
> > diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
> > index 008c514dc241..b03703cd7989 100644
> > --- a/kernel/sched/fair.c
> > +++ b/kernel/sched/fair.c
> > @@ -2965,7 +2965,7 @@ ___update_load_avg(u64 now, int cpu, struct sched_avg *sa,
> >  	if (!delta)
> >  		return 0;
> >  
> > -	sa->last_update_time += delta << 10;
> > +	sa->last_update_time = now & ~1023ULL;
> >  
> 
> So if we have a task that always runs <1024ns it should still get blocks
> of runtime because the difference between now and now&~1023 can be !0
> and spill.

Agreed - in the first approximation I was trying to figure out why Josef was 
seeing an effect from the patch.

> I'm just not immediately seeing how its different from the 0-sum we had.
> It should be identical since delta*1024 would equally land us on those
> same edges (there's an offset in the differential form between the two,
> but since we start with last_update_time=0, the resulting edges are the
> same afaict).

So I think the difference is that this:

	sa->last_update_time = now & ~1023ULL;

is tracking the absolute value of 'now' (i.e. rq->clock in most cases) by and 
large, with a 1024 ns imprecision.

This code on the other hand:

	sa->last_update_time += delta << 10;

... in essence creates a whole new absolute clock value that slowly but surely is 
drifting away from the real rq->clock, because 'delta' is always rounded down to 
the nearest 1024 ns boundary, so we accumulate the 'remainder' losses.

That is because:

        delta >>= 10;
	...
        sa->last_update_time += delta << 10;

Given enough time, ->last_update_time can drift a long way, and this delta:

	delta = now - sa->last_update_time;

... becomes meaningless AFAICS, because it's essentially two different clocks that 
get compared.

But I might be super confused about this myself ...

Thanks,

	Ingo

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

#1680914

On Tue, Jul 04, 2017 at 12:13:09PM +0200, Ingo Molnar wrote:
> 
> This code on the other hand:
> 
> 	sa->last_update_time += delta << 10;
> 
> ... in essence creates a whole new absolute clock value that slowly but surely is 
> drifting away from the real rq->clock, because 'delta' is always rounded down to 
> the nearest 1024 ns boundary, so we accumulate the 'remainder' losses.
> 
> That is because:
> 
>         delta >>= 10;
> 	...
>         sa->last_update_time += delta << 10;
> 
> Given enough time, ->last_update_time can drift a long way, and this delta:
> 
> 	delta = now - sa->last_update_time;
> 
> ... becomes meaningless AFAICS, because it's essentially two different clocks that 
> get compared.

Thing is, once you drift over 1023 (ns) your delta increases and you
catch up again.



 A  B     C       D          E  F
 |  |     |       |          |  |
 +----+----+----+----+----+----+----+----+----+----+----+


A: now = 0
   sa->last_update_time = 0
   delta := (now - sa->last_update_time) >> 10 = 0

B: now = 614				(+614)
   delta = (614 - 0) >> 10 = 0
   sa->last_update_time += 0		(0)
   sa->last_update_time = now & ~1023	(0)

C: now = 1843				(+1229)
   delta = (1843 - 0) >> 10 = 1
   sa->last_update_time += 1024		(1024)
   sa->last_update_time = now & ~1023	(1024)


D: now = 3481				(+1638)
   delta = (3481 - 1024) >> 10 = 2
   sa->last_update_time += 2048		(3072)
   sa->last_update_time = now & ~1023	(3072)

E: now = 5734				(+2253)
   delta = (5734 - 3072) = 2
   sa->last_update_time += 2048		(5120)
   sa->last_update_time = now & ~1023	(5120)

F: now = 6348				(+614)
   delta = (6348 - 5120) >> 10 = 1
   sa->last_update_time += 1024		(6144)
   sa->last_update_time = now & ~1023	(6144)



And you'll see that both are identical, and that both D and F have
gotten a spill from sub-chunk accounting.

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

#1680923

On Tue, Jul 04, 2017 at 02:40:03PM +0200, Peter Zijlstra wrote:
> On Tue, Jul 04, 2017 at 02:21:50PM +0200, Peter Zijlstra wrote:
> > On Tue, Jul 04, 2017 at 12:13:09PM +0200, Ingo Molnar wrote:
> > > 
> > > This code on the other hand:
> > > 
> > > 	sa->last_update_time += delta << 10;
> > > 
> > > ... in essence creates a whole new absolute clock value that slowly but surely is 
> > > drifting away from the real rq->clock, because 'delta' is always rounded down to 
> > > the nearest 1024 ns boundary, so we accumulate the 'remainder' losses.
> > > 
> > > That is because:
> > > 
> > >         delta >>= 10;
> > > 	...
> > >         sa->last_update_time += delta << 10;
> > > 
> > > Given enough time, ->last_update_time can drift a long way, and this delta:
> > > 
> > > 	delta = now - sa->last_update_time;
> > > 
> > > ... becomes meaningless AFAICS, because it's essentially two different clocks that 
> > > get compared.
> > 
> > Thing is, once you drift over 1023 (ns) your delta increases and you
> > catch up again.
> > 
> > 
> > 
> >  A  B     C       D          E  F
> >  |  |     |       |          |  |
> >  +----+----+----+----+----+----+----+----+----+----+----+
> > 
> > 
> > A: now = 0
> >    sa->last_update_time = 0
> >    delta := (now - sa->last_update_time) >> 10 = 0
> > 
> > B: now = 614				(+614)
> >    delta = (614 - 0) >> 10 = 0
> >    sa->last_update_time += 0		(0)
> >    sa->last_update_time = now & ~1023	(0)
> > 
> > C: now = 1843				(+1229)
> >    delta = (1843 - 0) >> 10 = 1
> >    sa->last_update_time += 1024		(1024)
> >    sa->last_update_time = now & ~1023	(1024)
> > 
> > 
> > D: now = 3481				(+1638)
> >    delta = (3481 - 1024) >> 10 = 2
> >    sa->last_update_time += 2048		(3072)
> >    sa->last_update_time = now & ~1023	(3072)
> > 
> > E: now = 5734				(+2253)
> >    delta = (5734 - 3072) = 2
> >    sa->last_update_time += 2048		(5120)
> >    sa->last_update_time = now & ~1023	(5120)
> > 
> > F: now = 6348				(+614)
> >    delta = (6348 - 5120) >> 10 = 1
> >    sa->last_update_time += 1024		(6144)
> >    sa->last_update_time = now & ~1023	(6144)
> > 
> > 
> > 
> > And you'll see that both are identical, and that both D and F have
> > gotten a spill from sub-chunk accounting.
> 
> 
> Where the two approaches differ is when we have different modifications
> to sa->last_update_time (and we do).
> 
> The differential (+=) one does not mandate initial value of
> ->last_update_time has the bottom 9 bits cleared. It will simply
> continue from wherever.
> 
> The absolute (&) one however mandates that ->last_update_time always has
> the bottom few bits 0, otherwise we can 'gain' time. The first iteration
> will clear those bits and we'll then double account them.
> 
> It so happens that we have an explicit assign in migrate
> (attach_entity_load_avg / set_task_rq_fair). And on negative delta. In
> all those cases we use the immediate 'now' value, no clearing of bottom
> bits.
> 
> The differential should work fine with that, the absolute one has double
> accounting issues in that case.
> 
> So it would be very good to find what exactly causes Josef's workload to
> get 'fixed'.

Sorry let me experiment some more, like I said this is one of 4 patches I need
to actually fix my workload, and I've tested so many iterations of this problem
that I may be _thinking_ it affects things but it really doesn't.  I'll re-test
with the normal code and the other 3 patches in place and see if things are ok.
Thanks,

Josef

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

#1680926

On Tue, Jul 04, 2017 at 02:21:50PM +0200, Peter Zijlstra wrote:
> On Tue, Jul 04, 2017 at 12:13:09PM +0200, Ingo Molnar wrote:
> > 
> > This code on the other hand:
> > 
> > 	sa->last_update_time += delta << 10;
> > 
> > ... in essence creates a whole new absolute clock value that slowly but surely is 
> > drifting away from the real rq->clock, because 'delta' is always rounded down to 
> > the nearest 1024 ns boundary, so we accumulate the 'remainder' losses.
> > 
> > That is because:
> > 
> >         delta >>= 10;
> > 	...
> >         sa->last_update_time += delta << 10;
> > 
> > Given enough time, ->last_update_time can drift a long way, and this delta:
> > 
> > 	delta = now - sa->last_update_time;
> > 
> > ... becomes meaningless AFAICS, because it's essentially two different clocks that 
> > get compared.
> 
> Thing is, once you drift over 1023 (ns) your delta increases and you
> catch up again.
> 
> 
> 
>  A  B     C       D          E  F
>  |  |     |       |          |  |
>  +----+----+----+----+----+----+----+----+----+----+----+
> 
> 
> A: now = 0
>    sa->last_update_time = 0
>    delta := (now - sa->last_update_time) >> 10 = 0
> 
> B: now = 614				(+614)
>    delta = (614 - 0) >> 10 = 0
>    sa->last_update_time += 0		(0)
>    sa->last_update_time = now & ~1023	(0)
> 
> C: now = 1843				(+1229)
>    delta = (1843 - 0) >> 10 = 1
>    sa->last_update_time += 1024		(1024)
>    sa->last_update_time = now & ~1023	(1024)
> 
> 
> D: now = 3481				(+1638)
>    delta = (3481 - 1024) >> 10 = 2
>    sa->last_update_time += 2048		(3072)
>    sa->last_update_time = now & ~1023	(3072)
> 
> E: now = 5734				(+2253)
>    delta = (5734 - 3072) = 2
>    sa->last_update_time += 2048		(5120)
>    sa->last_update_time = now & ~1023	(5120)
> 
> F: now = 6348				(+614)
>    delta = (6348 - 5120) >> 10 = 1
>    sa->last_update_time += 1024		(6144)
>    sa->last_update_time = now & ~1023	(6144)
> 
> 
> 
> And you'll see that both are identical, and that both D and F have
> gotten a spill from sub-chunk accounting.


Where the two approaches differ is when we have different modifications
to sa->last_update_time (and we do).

The differential (+=) one does not mandate initial value of
->last_update_time has the bottom 9 bits cleared. It will simply
continue from wherever.

The absolute (&) one however mandates that ->last_update_time always has
the bottom few bits 0, otherwise we can 'gain' time. The first iteration
will clear those bits and we'll then double account them.

It so happens that we have an explicit assign in migrate
(attach_entity_load_avg / set_task_rq_fair). And on negative delta. In
all those cases we use the immediate 'now' value, no clearing of bottom
bits.

The differential should work fine with that, the absolute one has double
accounting issues in that case.

So it would be very good to find what exactly causes Josef's workload to
get 'fixed'.

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

#1680989

On Tue, Jul 04, 2017 at 02:40:03PM +0200, Peter Zijlstra wrote:
> On Tue, Jul 04, 2017 at 02:21:50PM +0200, Peter Zijlstra wrote:
> > On Tue, Jul 04, 2017 at 12:13:09PM +0200, Ingo Molnar wrote:
> > > 
> > > This code on the other hand:
> > > 
> > > 	sa->last_update_time += delta << 10;
> > > 
> > > ... in essence creates a whole new absolute clock value that slowly but surely is 
> > > drifting away from the real rq->clock, because 'delta' is always rounded down to 
> > > the nearest 1024 ns boundary, so we accumulate the 'remainder' losses.
> > > 
> > > That is because:
> > > 
> > >         delta >>= 10;
> > > 	...
> > >         sa->last_update_time += delta << 10;
> > > 
> > > Given enough time, ->last_update_time can drift a long way, and this delta:
> > > 
> > > 	delta = now - sa->last_update_time;
> > > 
> > > ... becomes meaningless AFAICS, because it's essentially two different clocks that 
> > > get compared.
> > 
> > Thing is, once you drift over 1023 (ns) your delta increases and you
> > catch up again.
> > 
> > 
> > 
> >  A  B     C       D          E  F
> >  |  |     |       |          |  |
> >  +----+----+----+----+----+----+----+----+----+----+----+
> > 
> > 
> > A: now = 0
> >    sa->last_update_time = 0
> >    delta := (now - sa->last_update_time) >> 10 = 0
> > 
> > B: now = 614				(+614)
> >    delta = (614 - 0) >> 10 = 0
> >    sa->last_update_time += 0		(0)
> >    sa->last_update_time = now & ~1023	(0)
> > 
> > C: now = 1843				(+1229)
> >    delta = (1843 - 0) >> 10 = 1
> >    sa->last_update_time += 1024		(1024)
> >    sa->last_update_time = now & ~1023	(1024)
> > 
> > 
> > D: now = 3481				(+1638)
> >    delta = (3481 - 1024) >> 10 = 2
> >    sa->last_update_time += 2048		(3072)
> >    sa->last_update_time = now & ~1023	(3072)
> > 
> > E: now = 5734				(+2253)
> >    delta = (5734 - 3072) = 2
> >    sa->last_update_time += 2048		(5120)
> >    sa->last_update_time = now & ~1023	(5120)
> > 
> > F: now = 6348				(+614)
> >    delta = (6348 - 5120) >> 10 = 1
> >    sa->last_update_time += 1024		(6144)
> >    sa->last_update_time = now & ~1023	(6144)
> > 
> > 
> > 
> > And you'll see that both are identical, and that both D and F have
> > gotten a spill from sub-chunk accounting.
> 
> 
> Where the two approaches differ is when we have different modifications
> to sa->last_update_time (and we do).
> 
> The differential (+=) one does not mandate initial value of
> ->last_update_time has the bottom 9 bits cleared. It will simply
> continue from wherever.
> 
> The absolute (&) one however mandates that ->last_update_time always has
> the bottom few bits 0, otherwise we can 'gain' time. The first iteration
> will clear those bits and we'll then double account them.
> 
> It so happens that we have an explicit assign in migrate
> (attach_entity_load_avg / set_task_rq_fair). And on negative delta. In
> all those cases we use the immediate 'now' value, no clearing of bottom
> bits.
> 
> The differential should work fine with that, the absolute one has double
> accounting issues in that case.
> 
> So it would be very good to find what exactly causes Josef's workload to
> get 'fixed'.

Sorry everybody, I thought I had tested all of the patches minus this one, but
apparently I did not.  Re-testing with the original code and my other patches
verified that the problem is still fixed, so this isn't needed.  Sorry for the
noise,

Josef

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

#1681019

On Tue, Jul 04, 2017 at 09:51:25AM -0400, Josef Bacik wrote:
> Sorry everybody, I thought I had tested all of the patches minus this one, but
> apparently I did not.  Re-testing with the original code and my other patches
> verified that the problem is still fixed, so this isn't needed.  Sorry for the
> noise,

N/P, thanks for testing!

[toc] | [prev] | [standalone]

Back to top | Article view | linux.kernel

csiph-web