[PATCH] sched: prevent getting too much vruntime

[PATCH] sched: prevent getting too much vruntime

[byungchul.park]

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

Especially in the case below, se->vruntime can be too large and
scheduling cannot work properly.

1. set se->vruntime to "cfs_rq->min_vruntime - sysctl_sched_latency" in
   place_entity() when detaching the se from cfs_rq.
2. do a normalization by "se->vruntime -= cfs_rq->min_vruntime".
   (see detach_task_cfs_rq().)
3. do "se->vruntime += cfs_rq->min_vruntime", when attaching the se to
   a cfs_rq where cfs_rq->min_vruntime < sysctl_sched_latency.

In this case, se->vruntime is suppose to be a negative value, but
actually it is a too large value because vruntime is a unsigned type.
It's wrong. To avoid this situation, this patch takes the case into
account.

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

diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
index 077076f..a7cc8e8 100644
--- a/kernel/sched/fair.c
+++ b/kernel/sched/fair.c
@@ -480,6 +480,13 @@ static void update_min_vruntime(struct cfs_rq *cfs_rq)
 #endif
 }
 
+static inline void vruntime_unnormalize(struct cfs_rq *cfs_rq, struct sched_entity *se)
+{
+	se->vruntime += cfs_rq->min_vruntime;
+	if (unlikely((s64)se->vruntime < 0))
+		se->vruntime = 0;
+}
+
 /*
  * Enqueue an entity into the rb-tree:
  */
@@ -3002,7 +3009,7 @@ enqueue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags)
 	 * through calling update_curr().
 	 */
 	if (!(flags & ENQUEUE_WAKEUP) || (flags & ENQUEUE_WAKING))
-		se->vruntime += cfs_rq->min_vruntime;
+		vruntime_unnormalize(cfs_rq, se);
 
 	/*
 	 * Update run-time statistics of the 'current'.
@@ -8019,7 +8026,7 @@ static void attach_task_cfs_rq(struct task_struct *p)
 	attach_entity_load_avg(cfs_rq, se);
 
 	if (!vruntime_normalized(p))
-		se->vruntime += cfs_rq->min_vruntime;
+		vruntime_unnormalize(cfs_rq, se);
 }
 
 static void switched_from_fair(struct rq *rq, struct task_struct *p)
-- 
1.7.9.5

Re: [PATCH] sched: prevent getting too much vruntime

[Peter Zijlstra]

On Wed, Nov 11, 2015 at 05:50:27PM +0900, byungchul.park@lge.com wrote:

I've not actually read anything; my brain isn't working right today.

> +static inline void vruntime_unnormalize(struct cfs_rq *cfs_rq, struct sched_entity *se)
> +{
> +	se->vruntime += cfs_rq->min_vruntime;
> +	if (unlikely((s64)se->vruntime < 0))
> +		se->vruntime = 0;
> +}

But this is broken. This simply _cannot_ be right.

vruntime very much needs to wrap in u64 space. While regular time in ns
takes some 584 year to wrap, vruntime is scaled. The fastest vruntime is
2/1024 or 512 times faster than normal time. Making it take just over a
year to wrap around. This will happen.

Re: [PATCH] sched: prevent getting too much vruntime

[Byungchul Park]

On Wed, Nov 11, 2015 at 10:26:32AM +0100, Peter Zijlstra wrote:
> On Wed, Nov 11, 2015 at 05:50:27PM +0900, byungchul.park@lge.com wrote:
> 
> I've not actually read anything; my brain isn't working right today.
> 
> > +static inline void vruntime_unnormalize(struct cfs_rq *cfs_rq, struct sched_entity *se)
> > +{
> > +	se->vruntime += cfs_rq->min_vruntime;
> > +	if (unlikely((s64)se->vruntime < 0))
> > +		se->vruntime = 0;
> > +}
> 
> But this is broken. This simply _cannot_ be right.
> 
> vruntime very much needs to wrap in u64 space. While regular time in ns
> takes some 584 year to wrap, vruntime is scaled. The fastest vruntime is
> 2/1024 or 512 times faster than normal time. Making it take just over a
> year to wrap around. This will happen.

Then, do you mean it's no problem even if we compare between a vruntime
not wrapped yet and another vruntime already wrapped? I really wonder it.

> 
> 
> --
> 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/

Re: [PATCH] sched: prevent getting too much vruntime

[Peter Zijlstra]

On Wed, Nov 11, 2015 at 06:48:49PM +0900, Byungchul Park wrote:
> On Wed, Nov 11, 2015 at 10:26:32AM +0100, Peter Zijlstra wrote:
> > On Wed, Nov 11, 2015 at 05:50:27PM +0900, byungchul.park@lge.com wrote:
> > 
> > I've not actually read anything; my brain isn't working right today.
> > 
> > > +static inline void vruntime_unnormalize(struct cfs_rq *cfs_rq, struct sched_entity *se)
> > > +{
> > > +	se->vruntime += cfs_rq->min_vruntime;
> > > +	if (unlikely((s64)se->vruntime < 0))
> > > +		se->vruntime = 0;
> > > +}
> > 
> > But this is broken. This simply _cannot_ be right.
> > 
> > vruntime very much needs to wrap in u64 space. While regular time in ns
> > takes some 584 year to wrap, vruntime is scaled. The fastest vruntime is
> > 2/1024 or 512 times faster than normal time. Making it take just over a
> > year to wrap around. This will happen.
> 
> Then, do you mean it's no problem even if we compare between a vruntime
> not wrapped yet and another vruntime already wrapped? I really wonder it.

It should be; we were really careful with this back when we wrote all
that. All vruntime comparisons should be of the form (s64)(a-b). Which
gets you the correct order assuming things haven't drifted more than
2^63 apart.

Re: [PATCH] sched: prevent getting too much vruntime

[Byungchul Park]

On Wed, Nov 11, 2015 at 12:50:43PM +0100, Peter Zijlstra wrote:
> On Wed, Nov 11, 2015 at 06:48:49PM +0900, Byungchul Park wrote:
> > On Wed, Nov 11, 2015 at 10:26:32AM +0100, Peter Zijlstra wrote:
> > > On Wed, Nov 11, 2015 at 05:50:27PM +0900, byungchul.park@lge.com wrote:
> > > 
> > > I've not actually read anything; my brain isn't working right today.
> > > 
> > > > +static inline void vruntime_unnormalize(struct cfs_rq *cfs_rq, struct sched_entity *se)
> > > > +{
> > > > +	se->vruntime += cfs_rq->min_vruntime;
> > > > +	if (unlikely((s64)se->vruntime < 0))
> > > > +		se->vruntime = 0;
> > > > +}
> > > 
> > > But this is broken. This simply _cannot_ be right.
> > > 
> > > vruntime very much needs to wrap in u64 space. While regular time in ns
> > > takes some 584 year to wrap, vruntime is scaled. The fastest vruntime is
> > > 2/1024 or 512 times faster than normal time. Making it take just over a
> > > year to wrap around. This will happen.
> > 
> > Then, do you mean it's no problem even if we compare between a vruntime
> > not wrapped yet and another vruntime already wrapped? I really wonder it.
> 
> It should be; we were really careful with this back when we wrote all
> that. All vruntime comparisons should be of the form (s64)(a-b). Which
> gets you the correct order assuming things haven't drifted more than
> 2^63 apart.

I checked it. It looks no problem as you said.

Thank you very much.

> --
> 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/