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

Groups > linux.kernel > #1238015 > unrolled thread

[PATCH v3 0/2] sched: consider missed ticks when updating cpu load

Back to article view | Back to linux.kernel

Contents

  [PATCH v3 0/2] sched: consider missed ticks when updating cpu load <byungchul.park@lge.com> - 2015-10-02 09:50 +0200
    [PATCH v3 2/2] sched: consider missed ticks when updating global cpu load <byungchul.park@lge.com> - 2015-10-02 09:50 +0200
      Re: [PATCH v3 2/2] sched: consider missed ticks when updating global  cpu load Peter Zijlstra <peterz@infradead.org> - 2015-10-02 18:10 +0200
        Re: [PATCH v3 2/2] sched: consider missed ticks when updating global  cpu load Byungchul Park <byungchul.park@lge.com> - 2015-10-04 09:00 +0200
          Re: [PATCH v3 2/2] sched: consider missed ticks when updating global  cpu load Peter Zijlstra <peterz@infradead.org> - 2015-10-05 10:20 +0200
    [PATCH v3 1/2] sched: make __update_cpu_load() handle active tickless case <byungchul.park@lge.com> - 2015-10-02 09:50 +0200

#1238015 — [PATCH v3 0/2] sched: consider missed ticks when updating cpu load

From: Byungchul Park <byungchul.park@lge.com>

change from v3 to v2
- add a patch which make __update_cpu_load() handle active tickless

change from v1 to v2
- add some additional commit message (logic is same exactly)

Byungchul Park (2):
  sched: make __update_cpu_load() handle active tickless case
  sched: consider missed ticks when updating global cpu load

 kernel/sched/fair.c |   51 +++++++++++++++++++++++++++++++++++++++++++--------
 1 file changed, 43 insertions(+), 8 deletions(-)

-- 
1.7.9.5

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

[toc] | [next] | [standalone]

#1238019 — [PATCH v3 2/2] sched: consider missed ticks when updating global cpu load

From: Byungchul Park <byungchul.park@lge.com>

in hrtimer_interrupt(), the first tick_program_event() can be failed
because the next timer could be already expired due to,
(see the comment in hrtimer_interrupt())

- tracing
- long lasting callbacks
- being scheduled away when running in a VM

in the case that the first tick_program_event() is failed, the second
tick_program_event() set the expired time to more than one tick later.
then next tick can happen after more than one tick, even though tick is
not stopped by e.g. NOHZ.

when the next tick occurs, update_process_times() -> scheduler_tick()
-> update_cpu_load_active() is performed, assuming the distance between
last tick and current tick is 1 tick! it's wrong in this case. thus,
this abnormal case should be considered in update_cpu_load_active().

Signed-off-by: Byungchul Park <byungchul.park@lge.com>
---
 kernel/sched/fair.c |    7 +++++--
 1 file changed, 5 insertions(+), 2 deletions(-)

diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
index 9e76871..14b9757 100644
--- a/kernel/sched/fair.c
+++ b/kernel/sched/fair.c
@@ -4388,12 +4388,15 @@ void update_cpu_load_nohz(void)
  */
 void update_cpu_load_active(struct rq *this_rq)
 {
+	unsigned long curr_jiffies = READ_ONCE(jiffies);
+	unsigned long pending_updates;
 	unsigned long load = weighted_cpuload(cpu_of(this_rq));
 	/*
 	 * See the mess around update_idle_cpu_load() / update_cpu_load_nohz().
 	 */
-	this_rq->last_load_update_tick = jiffies;
-	__update_cpu_load(this_rq, load, 1, 1);
+	pending_updates = curr_jiffies - this_rq->last_load_update_tick;
+	this_rq->last_load_update_tick = curr_jiffies;
+	__update_cpu_load(this_rq, load, pending_updates, 1);
 }
 
 /*
-- 
1.7.9.5

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

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

#1238380 — Re: [PATCH v3 2/2] sched: consider missed ticks when updating global cpu load

On Fri, Oct 02, 2015 at 04:46:14PM +0900, byungchul.park@lge.com wrote:
> From: Byungchul Park <byungchul.park@lge.com>
> 
> in hrtimer_interrupt(), the first tick_program_event() can be failed
> because the next timer could be already expired due to,
> (see the comment in hrtimer_interrupt())
> 
> - tracing
> - long lasting callbacks

If anything keeps interrupts disabled for longer than 1 tick, you'd
better go fix that.

> - being scheduled away when running in a VM

Not sure how much I should care about that, and this patch is completely
wrong for that anyhow.

And this case in hrtimer_interrupt() is basically a fail case, if you
hit that, you've got bigger problems. The solution is to rework things
so you don't get there.


> in the case that the first tick_program_event() is failed, the second
> tick_program_event() set the expired time to more than one tick later.
> then next tick can happen after more than one tick, even though tick is
> not stopped by e.g. NOHZ.
> 
> when the next tick occurs, update_process_times() -> scheduler_tick()
> -> update_cpu_load_active() is performed, assuming the distance between
> last tick and current tick is 1 tick! it's wrong in this case. thus,
> this abnormal case should be considered in update_cpu_load_active().

Everything in update_process_times() assumes 1 tick, just fixing up 
one function inside that callchain is wrong -- I've already told you
that.


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

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

#1239049 — Re: [PATCH v3 2/2] sched: consider missed ticks when updating global cpu load

On Fri, Oct 02, 2015 at 05:59:06PM +0200, Peter Zijlstra wrote:
> On Fri, Oct 02, 2015 at 04:46:14PM +0900, byungchul.park@lge.com wrote:
> > From: Byungchul Park <byungchul.park@lge.com>
> > 
> > in hrtimer_interrupt(), the first tick_program_event() can be failed
> > because the next timer could be already expired due to,
> > (see the comment in hrtimer_interrupt())
> > 
> > - tracing
> > - long lasting callbacks
> 
> If anything keeps interrupts disabled for longer than 1 tick, you'd
> better go fix that.

tracing and long lasting callbacks are not my case.

> 
> > - being scheduled away when running in a VM

this is my case.

> 
> Not sure how much I should care about that, and this patch is completely
> wrong for that anyhow.

do you mean, in upper case, we must assume ticks occur with 1 tick interval
when update_process_times() is called even though more than 1 tick is
actually passed in host? right? i am really wondering it. i would admit i
was wrong if what you mean is same as what i understand.

> 
> And this case in hrtimer_interrupt() is basically a fail case, if you
> hit that, you've got bigger problems. The solution is to rework things
> so you don't get there.
> 
> 
> > in the case that the first tick_program_event() is failed, the second
> > tick_program_event() set the expired time to more than one tick later.
> > then next tick can happen after more than one tick, even though tick is
> > not stopped by e.g. NOHZ.
> > 
> > when the next tick occurs, update_process_times() -> scheduler_tick()
> > -> update_cpu_load_active() is performed, assuming the distance between
> > last tick and current tick is 1 tick! it's wrong in this case. thus,
> > this abnormal case should be considered in update_cpu_load_active().
> 
> Everything in update_process_times() assumes 1 tick, just fixing up 
> one function inside that callchain is wrong -- I've already told you
> that.

anyway, it's wrong for update_process_times() to assume 1 tick because
tick_irq_exit() -> tick_nohz_irq_exit() -> tick_nohz_full_update_tick()
-> tick_nohz_restart_sched_tick() can happen at full NOHZ as i already
said. in this full NOHZ case for tick to restart from non-idle,

1. update_process_times() -> account_process_tick() must be able to handle
more than one tick, or tick_nohz_restart_sched_tick() should handle the
case additionally. (i think the latter is better.) i will try to modify
the code to handle it if you agree with me.

2. to handle full NOHZ, tick_nohz_restart_sched_tick() should call
update_cpu_load_active() instead of update_cpu_load_nohz() with my 1/2
patch and 2/2 patch, or we should modify update_cpu_load_nohz() to know
full NOHZ, which currently don't know full NOHZ. (you may agree with the
latter.) in any case, 1/2 patch is necessary which current code is
absolutely missing.

peter, what do you think about my opinion? and about my 1/2 patch?
i will modify 2/2 patch depending on your feedback.

> 
> 
> --
> To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
> the body of a message to majordomo@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@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

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

#1239338 — Re: [PATCH v3 2/2] sched: consider missed ticks when updating global cpu load

On Sun, Oct 04, 2015 at 03:58:19PM +0900, Byungchul Park wrote:
> On Fri, Oct 02, 2015 at 05:59:06PM +0200, Peter Zijlstra wrote:
> > On Fri, Oct 02, 2015 at 04:46:14PM +0900, byungchul.park@lge.com wrote:
> > > From: Byungchul Park <byungchul.park@lge.com>
> > > 
> > > in hrtimer_interrupt(), the first tick_program_event() can be failed
> > > because the next timer could be already expired due to,
> > > (see the comment in hrtimer_interrupt())
> > > 
> > > - tracing
> > > - long lasting callbacks
> > 
> > If anything keeps interrupts disabled for longer than 1 tick, you'd
> > better go fix that.
> 
> tracing and long lasting callbacks are not my case.
> 
> > 
> > > - being scheduled away when running in a VM
> 
> this is my case.

I was afraid of that :/

> > 
> > Not sure how much I should care about that, and this patch is completely
> > wrong for that anyhow.
> 
> do you mean, in upper case, we must assume ticks occur with 1 tick interval
> when update_process_times() is called even though more than 1 tick is
> actually passed in host? right? i am really wondering it. i would admit i
> was wrong if what you mean is same as what i understand.

The first part is that I despise virt ;-), the second part is the
below argument that just fixing up some leaf function is wrong.

This check in the timer interrupt handler is purely a fail safe against
horrid behaviour and if you hit this you've lost.

> > And this case in hrtimer_interrupt() is basically a fail case, if you
> > hit that, you've got bigger problems. The solution is to rework things
> > so you don't get there.
> > 
> > 
> > > in the case that the first tick_program_event() is failed, the second
> > > tick_program_event() set the expired time to more than one tick later.
> > > then next tick can happen after more than one tick, even though tick is
> > > not stopped by e.g. NOHZ.
> > > 
> > > when the next tick occurs, update_process_times() -> scheduler_tick()
> > > -> update_cpu_load_active() is performed, assuming the distance between
> > > last tick and current tick is 1 tick! it's wrong in this case. thus,
> > > this abnormal case should be considered in update_cpu_load_active().
> > 
> > Everything in update_process_times() assumes 1 tick, just fixing up 
> > one function inside that callchain is wrong -- I've already told you
> > that.
> 
> anyway, it's wrong for update_process_times() to assume 1 tick because
> tick_irq_exit() -> tick_nohz_irq_exit() -> tick_nohz_full_update_tick()
> -> tick_nohz_restart_sched_tick() can happen at full NOHZ as i already
> said. in this full NOHZ case for tick to restart from non-idle,

NO_HZ_FULL is very much a work in progress, there's plenty wrong with
it. But yes, if it does this then its broken here too, I'm not sure if
Frederic is aware of this or not (I'm sure he's got a fairly big list of
broken for NO_HZ_FULL).

> 1. update_process_times() -> account_process_tick() must be able to handle
> more than one tick, or tick_nohz_restart_sched_tick() should handle the
> case additionally. (i think the latter is better.) i will try to modify
> the code to handle it if you agree with me.

Yes, and we need to audit all the other stuff called from
update_process_times().

run_local_timers() seems be ok.
rcu_check_clalbacks() also doesn't seem to care about ticks.

I _think_ we fixed most of the scheduler_tick()
stuff (under the assumption that TSC is stable), but I'm not sure.

and run_posix_cpu_timers() might also be ok.

> 2. to handle full NOHZ, tick_nohz_restart_sched_tick() should call
> update_cpu_load_active() instead of update_cpu_load_nohz() with my 1/2
> patch and 2/2 patch, or we should modify update_cpu_load_nohz() to know
> full NOHZ, which currently don't know full NOHZ. (you may agree with the
> latter.) in any case, 1/2 patch is necessary which current code is
> absolutely missing.
> 
> peter, what do you think about my opinion? and about my 1/2 patch?

I did not look too closely, but it might have the right shape for
dealing with !idle ticks. I'd have to look more closely at it.

> i will modify 2/2 patch depending on your feedback.

I think it will take more than a single patch to rework all of
update_process_times(). And we should also ask Thomas for his opinion,
but I think we want:

	- make update_process_times() take a nr_ticks argument
	  - fixup everything below it

	- fix tick_nohz_handler to not ignore the hrtimer_forward()
	  return value and pass it into
	  tick_sched_handle()/update_process_times().

	  (assuming this is the right oneshot tick part, tick-common
	  seems to be about periodic timers which aren't used much ?!)


Also, there is of course the question of what time means in virt, is
there time when you're not running etc.. But I'll leave that to people
who care about such things.
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

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

#1238026 — [PATCH v3 1/2] sched: make __update_cpu_load() handle active tickless case

From: Byungchul Park <byungchul.park@lge.com>

There are some cases where distance between ticks is more then one tick,
while the cpu is not idle, e.g.

 - full NOHZ
 - tracing
 - long lasting callbacks
 - being scheduled away when running in a VM

However __update_cpu_load() assumes it is the idle tickless case if the
distance between ticks is more than 1, even though it can be the active
tickless case. Thus in the active tickless case, updating cpu load
cannot be performed correctly. To update cpu load properly, this patch
changes __update_cpu_load() so that it can handle active tickless case.

We can consider the new_load for each omitted tick during tickless though
the each new_load would be zero in idle tickless case, while it's not
true in non-idle tickless case e.g. full NOHZ. We can approximately
consider the new_load ~= the last this_rq->cpu_load[0] during tickless
in non-idle tickless case e.g. full NOHZ. Now, let's define a symbol L
which is representing the each new_load during tickless so that L = 0 in
idle tickless case, L = this_rq->cpu_load[0] in non-idle tickless case.
Then, we can get the cpu_load(n) during tickless since last update, by

cpu_load(n) = (1 - 1/s) * cpu_load(n-1) + (1/s) * L
              where n = the current tick - 1, s = scale
            = A * cpu_load(n-1) + B
              where A = 1 - 1/s, B = (1/s) * L
            = A * (A * cpu_load(n-2) + B) + B
            = A * (A * (A * cpu_load(n-3) + B) + B) + B
            = A^3 * cpu_load(n-3) + A^2 * B + A * B + B
            = A^i * cpu_load(n-i) + (A^(i-1) + A^(i-2) + ... + 1) * B
              where i = pending_updates - 1
            = A^i * cpu_load(n-i) + B * (A^i - 1) / (A - 1)
              by geometric series formula for sum
            = (1 - 1/s)^i * (cpu_load(n-i) - L) + L
              by extending A and B

Calculation is over!

1. (1 - 1/s)^i can be handled by decay_load_missed().
2. cpu_load(n-i) is the "old_load".
3. L is the this_rq->cpu_load[0], updated at the last time.
4. cpu_load(n) for current tick will be handled at this time.

Signed-off-by: Byungchul Park <byungchul.park@lge.com>
---
 kernel/sched/fair.c |   46 +++++++++++++++++++++++++++++++++++++++-------
 1 file changed, 39 insertions(+), 7 deletions(-)

diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
index 4d5f97b..9e76871 100644
--- a/kernel/sched/fair.c
+++ b/kernel/sched/fair.c
@@ -4249,13 +4249,44 @@ decay_load_missed(unsigned long load, unsigned long missed_updates, int idx)
 
 /*
  * Update rq->cpu_load[] statistics. This function is usually called every
- * scheduler tick (TICK_NSEC). With tickless idle this will not be called
- * every tick. We fix it up based on jiffies.
+ * scheduler tick (TICK_NSEC). With tickless this will not be called every
+ * tick. We fix it up based on jiffies.
+ *
+ * We can consider the new_load for each omitted tick during tickless though
+ * the each new_load would be zero in idle tickless case, while it's not
+ * true in non-idle tickless case e.g. full NOHZ. We can approximately
+ * consider the new_load ~= the last this_rq->cpu_load[0] during tickless
+ * in non-idle tickless case e.g. full NOHZ. Now, let's define a symbol L
+ * which is representing the each new_load during tickless so that L = 0 in
+ * idle tickless case, L = this_rq->cpu_load[0] in non-idle tickless case.
+ * Then, we can get the cpu_load(n) during tickless since last update, by
+ *
+ * cpu_load(n) = (1 - 1/s) * cpu_load(n-1) + (1/s) * L
+ *               where n = the current tick - 1, s = scale
+ *             = A * cpu_load(n-1) + B
+ *               where A = 1 - 1/s, B = (1/s) * L
+ *             = A * (A * cpu_load(n-2) + B) + B
+ *             = A * (A * (A * cpu_load(n-3) + B) + B) + B
+ *             = A^3 * cpu_load(n-3) + A^2 * B + A * B + B
+ *             = A^i * cpu_load(n-i) + (A^(i-1) + A^(i-2) + ... + 1) * B
+ *               where i = pending_updates - 1
+ *             = A^i * cpu_load(n-i) + B * (A^i - 1) / (A - 1)
+ *               by geometric series formula for sum
+ *             = (1 - 1/s)^i * (cpu_load(n-i) - L) + L
+ *               by extending A and B
+ *
+ * Calculation is over!
+ *
+ * 1. (1 - 1/s)^i can be handled by decay_load_missed().
+ * 2. cpu_load(n-i) is the "old_load".
+ * 3. L is the this_rq->cpu_load[0], updated at the last time.
+ * 4. cpu_load(n) for current tick will be handled at this time.
  */
 static void __update_cpu_load(struct rq *this_rq, unsigned long this_load,
-			      unsigned long pending_updates)
+			      unsigned long pending_updates, int active)
 {
 	int i, scale;
+	unsigned long tickless_load = active ? this_rq->cpu_load[0] : 0;
 
 	this_rq->nr_load_updates++;
 
@@ -4266,8 +4297,9 @@ static void __update_cpu_load(struct rq *this_rq, unsigned long this_load,
 
 		/* scale is effectively 1 << i now, and >> i divides by scale */
 
-		old_load = this_rq->cpu_load[i];
+		old_load = this_rq->cpu_load[i] - tickless_load;
 		old_load = decay_load_missed(old_load, pending_updates - 1, i);
+		old_load += tickless_load;
 		new_load = this_load;
 		/*
 		 * Round up the averaging division if load is increasing. This
@@ -4322,7 +4354,7 @@ static void update_idle_cpu_load(struct rq *this_rq)
 	pending_updates = curr_jiffies - this_rq->last_load_update_tick;
 	this_rq->last_load_update_tick = curr_jiffies;
 
-	__update_cpu_load(this_rq, load, pending_updates);
+	__update_cpu_load(this_rq, load, pending_updates, 0);
 }
 
 /*
@@ -4345,7 +4377,7 @@ void update_cpu_load_nohz(void)
 		 * We were idle, this means load 0, the current load might be
 		 * !0 due to remote wakeups and the sort.
 		 */
-		__update_cpu_load(this_rq, 0, pending_updates);
+		__update_cpu_load(this_rq, 0, pending_updates, 0);
 	}
 	raw_spin_unlock(&this_rq->lock);
 }
@@ -4361,7 +4393,7 @@ void update_cpu_load_active(struct rq *this_rq)
 	 * See the mess around update_idle_cpu_load() / update_cpu_load_nohz().
 	 */
 	this_rq->last_load_update_tick = jiffies;
-	__update_cpu_load(this_rq, load, 1);
+	__update_cpu_load(this_rq, load, 1, 1);
 }
 
 /*
-- 
1.7.9.5

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

[toc] | [prev] | [standalone]

Back to top | Article view | linux.kernel

csiph-web