[patch 0/2] Fix interactivity buglet with autogroup and shares distribution re-write

[patch 0/2] Fix interactivity buglet with autogroup and shares distribution re-write

[Paul Turner]

This should address the interactivity issues reported by Mike Galbraith:
https://lkml.org/lkml/2010/11/28/47

The root cause turns out to be a mis-ordering of weight updates and accounting
outstanding execution time.

This is fixed by making update_curr() 'atomic' once more with respect to
accounting, this allows us to then make sure any outstanding time is charged in
the re-weight path (prior to the actual update).

Thank-you to everyone for their patience while we tracked this down,

- Paul

[patch 1/2] sched: move periodic share updates to entity_tick()

[Paul Turner]

[-- Attachment #1: shares_on_tick.patch --]
[-- Type: text/plain, Size: 2230 bytes --]

Long running entities that do not block (dequeue) require periodic updates to
maintain accurate share values.  (Note: group entities with several threads are
quite likely to be non-blocking in many circumstances).

By virtue of being long-running however, we will see entity ticks (otherwise 
the required update occurs in dequeue/put and we are done).  Thus we can move 
the detection (and associated work) for these updates into the periodic path.

This restores the 'atomicity' of update_curr() with respect to accounting.

Signed-off-by: Paul Turner <pjt@google.com>

---
 kernel/sched_fair.c |   29 ++++++++++++++++++++++++-----
 1 file changed, 24 insertions(+), 5 deletions(-)

Index: tip3/kernel/sched_fair.c
===================================================================
--- tip3.orig/kernel/sched_fair.c
+++ tip3/kernel/sched_fair.c
@@ -563,12 +563,10 @@ __update_curr(struct cfs_rq *cfs_rq, str
 	update_min_vruntime(cfs_rq);
 
 #if defined CONFIG_SMP && defined CONFIG_FAIR_GROUP_SCHED
-	cfs_rq->load_unacc_exec_time += delta_exec;
-	if (cfs_rq->load_unacc_exec_time > sysctl_sched_shares_window) {
-		update_cfs_load(cfs_rq, 0);
-		update_cfs_shares(cfs_rq, 0);
-	}
+	if (!entity_is_task(curr))
+		group_cfs_rq(curr)->load_unacc_exec_time += delta_exec;
 #endif
+
 }
 
 static void update_curr(struct cfs_rq *cfs_rq)
@@ -809,6 +807,20 @@ static void update_cfs_shares(struct cfs
 
 	reweight_entity(cfs_rq_of(se), se, shares);
 }
+
+static void update_entity_shares_tick(struct sched_entity *se)
+{
+	struct cfs_rq *cfs_rq;
+
+	if (entity_is_task(se))
+		return;
+
+	cfs_rq = group_cfs_rq(se);
+	if (cfs_rq->load_unacc_exec_time > sysctl_sched_shares_window) {
+		update_cfs_load(cfs_rq, 0);
+		update_cfs_shares(cfs_rq, 0);
+	}
+}
 #else /* CONFIG_FAIR_GROUP_SCHED */
 static void update_cfs_load(struct cfs_rq *cfs_rq, int global_update)
 {
@@ -1133,6 +1145,13 @@ entity_tick(struct cfs_rq *cfs_rq, struc
 	 */
 	update_curr(cfs_rq);
 
+#if defined CONFIG_SMP && defined CONFIG_FAIR_GROUP_SCHED
+	/*
+	 * Update share accounting for long-running entities.
+	 */
+	update_entity_shares_tick(curr);
+#endif
+
 #ifdef CONFIG_SCHED_HRTICK
 	/*
 	 * queued ticks are scheduled to match the slice, so don't bother

Re: [patch 1/2] sched: move periodic share updates to entity_tick()

[Peter Zijlstra]

I made that:

---
Subject: sched: Move periodic share updates to entity_tick()
From: Paul Turner <pjt@google.com>
Date: Wed, 15 Dec 2010 19:10:17 -0800

Long running entities that do not block (dequeue) require periodic updates to
maintain accurate share values.  (Note: group entities with several threads are
quite likely to be non-blocking in many circumstances).

By virtue of being long-running however, we will see entity ticks (otherwise
the required update occurs in dequeue/put and we are done).  Thus we can move
the detection (and associated work) for these updates into the periodic path.

This restores the 'atomicity' of update_curr() with respect to accounting.

Signed-off-by: Paul Turner <pjt@google.com>
Signed-off-by: Peter Zijlstra <a.p.zijlstra@chello.nl>
LKML-Reference: <20101216031038.067028969@google.com>
---
 kernel/sched_fair.c |   21 +++++++++++++++++----
 1 file changed, 17 insertions(+), 4 deletions(-)

Index: linux-2.6/kernel/sched_fair.c
===================================================================
--- linux-2.6.orig/kernel/sched_fair.c
+++ linux-2.6/kernel/sched_fair.c
@@ -564,10 +564,6 @@ __update_curr(struct cfs_rq *cfs_rq, str
 
 #if defined CONFIG_SMP && defined CONFIG_FAIR_GROUP_SCHED
 	cfs_rq->load_unacc_exec_time += delta_exec;
-	if (cfs_rq->load_unacc_exec_time > sysctl_sched_shares_window) {
-		update_cfs_load(cfs_rq, 0);
-		update_cfs_shares(cfs_rq, 0);
-	}
 #endif
 }
 
@@ -809,6 +805,14 @@ static void update_cfs_shares(struct cfs
 
 	reweight_entity(cfs_rq_of(se), se, shares);
 }
+
+static void update_entity_shares_tick(struct cfs_rq *cfs_rq)
+{
+	if (cfs_rq->load_unacc_exec_time > sysctl_sched_shares_window) {
+		update_cfs_load(cfs_rq, 0);
+		update_cfs_shares(cfs_rq, 0);
+	}
+}
 #else /* CONFIG_FAIR_GROUP_SCHED */
 static void update_cfs_load(struct cfs_rq *cfs_rq, int global_update)
 {
@@ -817,6 +821,10 @@ static void update_cfs_load(struct cfs_r
 static inline void update_cfs_shares(struct cfs_rq *cfs_rq, long weight_delta)
 {
 }
+
+static inline void update_entity_shares_tick(struct cfs_rq *cfs_rq)
+{
+}
 #endif /* CONFIG_FAIR_GROUP_SCHED */
 
 static void enqueue_sleeper(struct cfs_rq *cfs_rq, struct sched_entity *se)
@@ -1133,6 +1141,11 @@ entity_tick(struct cfs_rq *cfs_rq, struc
 	 */
 	update_curr(cfs_rq);
 
+	/*
+	 * Update share accounting for long-running entities.
+	 */
+	update_entity_shares_tick(cfs_rq);
+
 #ifdef CONFIG_SCHED_HRTICK
 	/*
 	 * queued ticks are scheduled to match the slice, so don't bother

Re: [patch 1/2] sched: move periodic share updates to entity_tick()

[Mike Galbraith]

On Thu, 2010-12-16 at 12:03 +0100, Peter Zijlstra wrote:
> I made that:

Box is ill, I'll test these as soon as it's all better.

> ---
> Subject: sched: Move periodic share updates to entity_tick()
> From: Paul Turner <pjt@google.com>
> Date: Wed, 15 Dec 2010 19:10:17 -0800
> 
> Long running entities that do not block (dequeue) require periodic updates to
> maintain accurate share values.  (Note: group entities with several threads are
> quite likely to be non-blocking in many circumstances).
> 
> By virtue of being long-running however, we will see entity ticks (otherwise
> the required update occurs in dequeue/put and we are done).  Thus we can move
> the detection (and associated work) for these updates into the periodic path.
> 
> This restores the 'atomicity' of update_curr() with respect to accounting.
> 
> Signed-off-by: Paul Turner <pjt@google.com>
> Signed-off-by: Peter Zijlstra <a.p.zijlstra@chello.nl>
> LKML-Reference: <20101216031038.067028969@google.com>
> ---
>  kernel/sched_fair.c |   21 +++++++++++++++++----
>  1 file changed, 17 insertions(+), 4 deletions(-)
> 
> Index: linux-2.6/kernel/sched_fair.c
> ===================================================================
> --- linux-2.6.orig/kernel/sched_fair.c
> +++ linux-2.6/kernel/sched_fair.c
> @@ -564,10 +564,6 @@ __update_curr(struct cfs_rq *cfs_rq, str
>  
>  #if defined CONFIG_SMP && defined CONFIG_FAIR_GROUP_SCHED
>  	cfs_rq->load_unacc_exec_time += delta_exec;
> -	if (cfs_rq->load_unacc_exec_time > sysctl_sched_shares_window) {
> -		update_cfs_load(cfs_rq, 0);
> -		update_cfs_shares(cfs_rq, 0);
> -	}
>  #endif
>  }
>  
> @@ -809,6 +805,14 @@ static void update_cfs_shares(struct cfs
>  
>  	reweight_entity(cfs_rq_of(se), se, shares);
>  }
> +
> +static void update_entity_shares_tick(struct cfs_rq *cfs_rq)
> +{
> +	if (cfs_rq->load_unacc_exec_time > sysctl_sched_shares_window) {
> +		update_cfs_load(cfs_rq, 0);
> +		update_cfs_shares(cfs_rq, 0);
> +	}
> +}
>  #else /* CONFIG_FAIR_GROUP_SCHED */
>  static void update_cfs_load(struct cfs_rq *cfs_rq, int global_update)
>  {
> @@ -817,6 +821,10 @@ static void update_cfs_load(struct cfs_r
>  static inline void update_cfs_shares(struct cfs_rq *cfs_rq, long weight_delta)
>  {
>  }
> +
> +static inline void update_entity_shares_tick(struct cfs_rq *cfs_rq)
> +{
> +}
>  #endif /* CONFIG_FAIR_GROUP_SCHED */
>  
>  static void enqueue_sleeper(struct cfs_rq *cfs_rq, struct sched_entity *se)
> @@ -1133,6 +1141,11 @@ entity_tick(struct cfs_rq *cfs_rq, struc
>  	 */
>  	update_curr(cfs_rq);
>  
> +	/*
> +	 * Update share accounting for long-running entities.
> +	 */
> +	update_entity_shares_tick(cfs_rq);
> +
>  #ifdef CONFIG_SCHED_HRTICK
>  	/*
>  	 * queued ticks are scheduled to match the slice, so don't bother
> 

Re: [patch 1/2] sched: move periodic share updates to entity_tick()

[Paul Turner]

Back from the Holidays and catching up on email -- Peter, looks like
this fix still needs merging?

On Thu, Dec 16, 2010 at 6:26 AM, Mike Galbraith <efault@gmx.de> wrote:
> On Thu, 2010-12-16 at 12:03 +0100, Peter Zijlstra wrote:
>> I made that:
>
> Box is ill, I'll test these as soon as it's all better.
>
>> ---
>> Subject: sched: Move periodic share updates to entity_tick()
>> From: Paul Turner <pjt@google.com>
>> Date: Wed, 15 Dec 2010 19:10:17 -0800
>>
>> Long running entities that do not block (dequeue) require periodic updates to
>> maintain accurate share values.  (Note: group entities with several threads are
>> quite likely to be non-blocking in many circumstances).
>>
>> By virtue of being long-running however, we will see entity ticks (otherwise
>> the required update occurs in dequeue/put and we are done).  Thus we can move
>> the detection (and associated work) for these updates into the periodic path.
>>
>> This restores the 'atomicity' of update_curr() with respect to accounting.
>>
>> Signed-off-by: Paul Turner <pjt@google.com>
>> Signed-off-by: Peter Zijlstra <a.p.zijlstra@chello.nl>
>> LKML-Reference: <20101216031038.067028969@google.com>
>> ---
>>  kernel/sched_fair.c |   21 +++++++++++++++++----
>>  1 file changed, 17 insertions(+), 4 deletions(-)
>>
>> Index: linux-2.6/kernel/sched_fair.c
>> ===================================================================
>> --- linux-2.6.orig/kernel/sched_fair.c
>> +++ linux-2.6/kernel/sched_fair.c
>> @@ -564,10 +564,6 @@ __update_curr(struct cfs_rq *cfs_rq, str
>>
>>  #if defined CONFIG_SMP && defined CONFIG_FAIR_GROUP_SCHED
>>       cfs_rq->load_unacc_exec_time += delta_exec;
>> -     if (cfs_rq->load_unacc_exec_time > sysctl_sched_shares_window) {
>> -             update_cfs_load(cfs_rq, 0);
>> -             update_cfs_shares(cfs_rq, 0);
>> -     }
>>  #endif
>>  }
>>
>> @@ -809,6 +805,14 @@ static void update_cfs_shares(struct cfs
>>
>>       reweight_entity(cfs_rq_of(se), se, shares);
>>  }
>> +
>> +static void update_entity_shares_tick(struct cfs_rq *cfs_rq)
>> +{
>> +     if (cfs_rq->load_unacc_exec_time > sysctl_sched_shares_window) {
>> +             update_cfs_load(cfs_rq, 0);
>> +             update_cfs_shares(cfs_rq, 0);
>> +     }
>> +}
>>  #else /* CONFIG_FAIR_GROUP_SCHED */
>>  static void update_cfs_load(struct cfs_rq *cfs_rq, int global_update)
>>  {
>> @@ -817,6 +821,10 @@ static void update_cfs_load(struct cfs_r
>>  static inline void update_cfs_shares(struct cfs_rq *cfs_rq, long weight_delta)
>>  {
>>  }
>> +
>> +static inline void update_entity_shares_tick(struct cfs_rq *cfs_rq)
>> +{
>> +}
>>  #endif /* CONFIG_FAIR_GROUP_SCHED */
>>
>>  static void enqueue_sleeper(struct cfs_rq *cfs_rq, struct sched_entity *se)
>> @@ -1133,6 +1141,11 @@ entity_tick(struct cfs_rq *cfs_rq, struc
>>        */
>>       update_curr(cfs_rq);
>>
>> +     /*
>> +      * Update share accounting for long-running entities.
>> +      */
>> +     update_entity_shares_tick(cfs_rq);
>> +
>>  #ifdef CONFIG_SCHED_HRTICK
>>       /*
>>        * queued ticks are scheduled to match the slice, so don't bother
>>
>
>
>

Re: [patch 1/2] sched: move periodic share updates to entity_tick()

[Paul Turner]

Never mind, my git state was wonky -- I see these now, Thanks!

On Mon, Jan 10, 2011 at 3:49 PM, Paul Turner <pjt@google.com> wrote:
> Back from the Holidays and catching up on email -- Peter, looks like
> this fix still needs merging?
>
> On Thu, Dec 16, 2010 at 6:26 AM, Mike Galbraith <efault@gmx.de> wrote:
>> On Thu, 2010-12-16 at 12:03 +0100, Peter Zijlstra wrote:
>>> I made that:
>>
>> Box is ill, I'll test these as soon as it's all better.
>>
>>> ---
>>> Subject: sched: Move periodic share updates to entity_tick()
>>> From: Paul Turner <pjt@google.com>
>>> Date: Wed, 15 Dec 2010 19:10:17 -0800
>>>
>>> Long running entities that do not block (dequeue) require periodic updates to
>>> maintain accurate share values.  (Note: group entities with several threads are
>>> quite likely to be non-blocking in many circumstances).
>>>
>>> By virtue of being long-running however, we will see entity ticks (otherwise
>>> the required update occurs in dequeue/put and we are done).  Thus we can move
>>> the detection (and associated work) for these updates into the periodic path.
>>>
>>> This restores the 'atomicity' of update_curr() with respect to accounting.
>>>
>>> Signed-off-by: Paul Turner <pjt@google.com>
>>> Signed-off-by: Peter Zijlstra <a.p.zijlstra@chello.nl>
>>> LKML-Reference: <20101216031038.067028969@google.com>
>>> ---
>>>  kernel/sched_fair.c |   21 +++++++++++++++++----
>>>  1 file changed, 17 insertions(+), 4 deletions(-)
>>>
>>> Index: linux-2.6/kernel/sched_fair.c
>>> ===================================================================
>>> --- linux-2.6.orig/kernel/sched_fair.c
>>> +++ linux-2.6/kernel/sched_fair.c
>>> @@ -564,10 +564,6 @@ __update_curr(struct cfs_rq *cfs_rq, str
>>>
>>>  #if defined CONFIG_SMP && defined CONFIG_FAIR_GROUP_SCHED
>>>       cfs_rq->load_unacc_exec_time += delta_exec;
>>> -     if (cfs_rq->load_unacc_exec_time > sysctl_sched_shares_window) {
>>> -             update_cfs_load(cfs_rq, 0);
>>> -             update_cfs_shares(cfs_rq, 0);
>>> -     }
>>>  #endif
>>>  }
>>>
>>> @@ -809,6 +805,14 @@ static void update_cfs_shares(struct cfs
>>>
>>>       reweight_entity(cfs_rq_of(se), se, shares);
>>>  }
>>> +
>>> +static void update_entity_shares_tick(struct cfs_rq *cfs_rq)
>>> +{
>>> +     if (cfs_rq->load_unacc_exec_time > sysctl_sched_shares_window) {
>>> +             update_cfs_load(cfs_rq, 0);
>>> +             update_cfs_shares(cfs_rq, 0);
>>> +     }
>>> +}
>>>  #else /* CONFIG_FAIR_GROUP_SCHED */
>>>  static void update_cfs_load(struct cfs_rq *cfs_rq, int global_update)
>>>  {
>>> @@ -817,6 +821,10 @@ static void update_cfs_load(struct cfs_r
>>>  static inline void update_cfs_shares(struct cfs_rq *cfs_rq, long weight_delta)
>>>  {
>>>  }
>>> +
>>> +static inline void update_entity_shares_tick(struct cfs_rq *cfs_rq)
>>> +{
>>> +}
>>>  #endif /* CONFIG_FAIR_GROUP_SCHED */
>>>
>>>  static void enqueue_sleeper(struct cfs_rq *cfs_rq, struct sched_entity *se)
>>> @@ -1133,6 +1141,11 @@ entity_tick(struct cfs_rq *cfs_rq, struc
>>>        */
>>>       update_curr(cfs_rq);
>>>
>>> +     /*
>>> +      * Update share accounting for long-running entities.
>>> +      */
>>> +     update_entity_shares_tick(cfs_rq);
>>> +
>>>  #ifdef CONFIG_SCHED_HRTICK
>>>       /*
>>>        * queued ticks are scheduled to match the slice, so don't bother
>>>
>>
>>
>>
>

[tip:sched/core] sched: Move periodic share updates to entity_tick()

[tip-bot for Paul Turner]

Commit-ID:  43365bd7ff37979d2afdccbe953299ed64a4649b
Gitweb:     http://git.kernel.org/tip/43365bd7ff37979d2afdccbe953299ed64a4649b
Author:     Paul Turner <pjt@google.com>
AuthorDate: Wed, 15 Dec 2010 19:10:17 -0800
Committer:  Ingo Molnar <mingo@elte.hu>
CommitDate: Sun, 19 Dec 2010 16:36:22 +0100

sched: Move periodic share updates to entity_tick()

Long running entities that do not block (dequeue) require periodic updates to
maintain accurate share values.  (Note: group entities with several threads are
quite likely to be non-blocking in many circumstances).

By virtue of being long-running however, we will see entity ticks (otherwise
the required update occurs in dequeue/put and we are done).  Thus we can move
the detection (and associated work) for these updates into the periodic path.

This restores the 'atomicity' of update_curr() with respect to accounting.

Signed-off-by: Paul Turner <pjt@google.com>
Signed-off-by: Peter Zijlstra <a.p.zijlstra@chello.nl>
LKML-Reference: <20101216031038.067028969@google.com>
Signed-off-by: Ingo Molnar <mingo@elte.hu>
---
 kernel/sched_fair.c |   21 +++++++++++++++++----
 1 files changed, 17 insertions(+), 4 deletions(-)

diff --git a/kernel/sched_fair.c b/kernel/sched_fair.c
index c886717..16ee398 100644
--- a/kernel/sched_fair.c
+++ b/kernel/sched_fair.c
@@ -564,10 +564,6 @@ __update_curr(struct cfs_rq *cfs_rq, struct sched_entity *curr,
 
 #if defined CONFIG_SMP && defined CONFIG_FAIR_GROUP_SCHED
 	cfs_rq->load_unacc_exec_time += delta_exec;
-	if (cfs_rq->load_unacc_exec_time > sysctl_sched_shares_window) {
-		update_cfs_load(cfs_rq, 0);
-		update_cfs_shares(cfs_rq, 0);
-	}
 #endif
 }
 
@@ -809,6 +805,14 @@ static void update_cfs_shares(struct cfs_rq *cfs_rq, long weight_delta)
 
 	reweight_entity(cfs_rq_of(se), se, shares);
 }
+
+static void update_entity_shares_tick(struct cfs_rq *cfs_rq)
+{
+	if (cfs_rq->load_unacc_exec_time > sysctl_sched_shares_window) {
+		update_cfs_load(cfs_rq, 0);
+		update_cfs_shares(cfs_rq, 0);
+	}
+}
 #else /* CONFIG_FAIR_GROUP_SCHED */
 static void update_cfs_load(struct cfs_rq *cfs_rq, int global_update)
 {
@@ -817,6 +821,10 @@ static void update_cfs_load(struct cfs_rq *cfs_rq, int global_update)
 static inline void update_cfs_shares(struct cfs_rq *cfs_rq, long weight_delta)
 {
 }
+
+static inline void update_entity_shares_tick(struct cfs_rq *cfs_rq)
+{
+}
 #endif /* CONFIG_FAIR_GROUP_SCHED */
 
 static void enqueue_sleeper(struct cfs_rq *cfs_rq, struct sched_entity *se)
@@ -1133,6 +1141,11 @@ entity_tick(struct cfs_rq *cfs_rq, struct sched_entity *curr, int queued)
 	 */
 	update_curr(cfs_rq);
 
+	/*
+	 * Update share accounting for long-running entities.
+	 */
+	update_entity_shares_tick(cfs_rq);
+
 #ifdef CONFIG_SCHED_HRTICK
 	/*
 	 * queued ticks are scheduled to match the slice, so don't bother

[patch 2/2] sched: charge unaccounted run-time on entity re-weight

[Paul Turner]

[-- Attachment #1: update_on_reweight.patch --]
[-- Type: text/plain, Size: 1730 bytes --]

Mike Galbraith reported poor interactivity[*] when the new shares distribution 
code was combined with autogroups.

The root cause turns out to be a mis-ordering of accounting accrued execution
time and shares updates.  Since update_curr() is issued hierarchically,
updating the parent entity weights to reflect child enqueue/dequeue results in
the parent's unaccounted execution time then being accrued (vs vruntime) at the
new weight as opposed to the weight present at accumulation.

While this doesn't have much effect on processes with timeslices that cross a
tick, it is particularly problematic for an interactive process (e.g. Xorg)
which incurs many (tiny) timeslices.  In this scenario almost all updates are
at dequeue which can result in significant fairness perturbation (especially if
it is the only thread, resulting in potential {tg->shares, MIN_SHARES}
transitions).

Correct this by ensuring unaccounted time is accumulated prior to manipulating
an entity's weight.

[*] http://xkcd.com/619/ is perversely Nostradamian here.

Signed-off-by: Paul Turner <pjt@google.com>

---
 kernel/sched_fair.c |    6 +++++-
 1 file changed, 5 insertions(+), 1 deletion(-)

Index: tip3/kernel/sched_fair.c
===================================================================
--- tip3.orig/kernel/sched_fair.c
+++ tip3/kernel/sched_fair.c
@@ -767,8 +767,12 @@ static void update_cfs_load(struct cfs_r
 static void reweight_entity(struct cfs_rq *cfs_rq, struct sched_entity *se,
 			    unsigned long weight)
 {
-	if (se->on_rq)
+	if (se->on_rq) {
+		/* commit outstanding execution time */
+		if (cfs_rq->curr == se)
+			update_curr(cfs_rq);
 		account_entity_dequeue(cfs_rq, se);
+	}
 
 	update_load_set(&se->load, weight);
 

Re: [patch 2/2] sched: charge unaccounted run-time on entity re-weight

[Paul Turner]

Hum -- forgot to refresh mbx file, slightly cleaner version (we can 
still charge unaccounted time against our queuing cfs_rq).

- Paul

-----

sched: move periodic share updates to entity_tick()

Long running entities that do not block (dequeue) require periodic 
updates to
maintain accurate share values.  (Note: group entities with several 
threads are
quite likely to be non-blocking in many circumstances).

By virtue of being long-running however, we will see entity ticks 
(otherwise
the required update occurs in dequeue/put and we are done).  Thus we can 
move
the detection (and associated work) for these updates into the periodic 
path.

This restores the 'atomicity' of update_curr() with respect to accounting.

Signed-off-by: Paul Turner <pjt@google.com>

---
  kernel/sched_fair.c |   21 +++++++++++++++++----
  1 file changed, 17 insertions(+), 4 deletions(-)

Index: tip3/kernel/sched_fair.c
===================================================================
--- tip3.orig/kernel/sched_fair.c
+++ tip3/kernel/sched_fair.c
@@ -564,11 +564,8 @@ __update_curr(struct cfs_rq *cfs_rq, str

  #if defined CONFIG_SMP && defined CONFIG_FAIR_GROUP_SCHED
  	cfs_rq->load_unacc_exec_time += delta_exec;
-	if (cfs_rq->load_unacc_exec_time > sysctl_sched_shares_window) {
-		update_cfs_load(cfs_rq, 0);
-		update_cfs_shares(cfs_rq, 0);
-	}
  #endif
  }

  static void update_curr(struct cfs_rq *cfs_rq)
@@ -809,6 +806,15 @@ static void update_cfs_shares(struct cfs

  	reweight_entity(cfs_rq_of(se), se, shares);
  }
+
+static void update_cfs_rq_shares_tick(struct cfs_rq *cfs_rq)
+{
+	/* rate limit updates by the averaging window */
+	if (cfs_rq->load_unacc_exec_time > sysctl_sched_shares_window) {
+		update_cfs_load(cfs_rq, 0);
+		update_cfs_shares(cfs_rq, 0);
+	}
+}
  #else /* CONFIG_FAIR_GROUP_SCHED */
  static void update_cfs_load(struct cfs_rq *cfs_rq, int global_update)
  {
@@ -1133,6 +1139,13 @@ entity_tick(struct cfs_rq *cfs_rq, struc
  	 */
  	update_curr(cfs_rq);

+#if defined CONFIG_SMP && defined CONFIG_FAIR_GROUP_SCHED
+	/*
+	 * Update share accounting for long-running entities.
+	 */
+	update_cfs_rq_shares_tick(cfs_rq);
+#endif
+
  #ifdef CONFIG_SCHED_HRTICK
  	/*
  	 * queued ticks are scheduled to match the slice, so don't bother

Re: [patch 2/2] sched: charge unaccounted run-time on entity re-weight

[Paul Turner]

On 12/15/10 19:35, Paul Turner wrote:
> Hum -- forgot to refresh mbx file, slightly cleaner version (we can
> still charge unaccounted time against our queuing cfs_rq).
>
> - Paul
>

.... Obviously this is in lieu of the first patch and not this one.

I'm tired :(

> -----
>
> sched: move periodic share updates to entity_tick()
>
> Long running entities that do not block (dequeue) require periodic
> updates to
> maintain accurate share values. (Note: group entities with several
> threads are
> quite likely to be non-blocking in many circumstances).
>
> By virtue of being long-running however, we will see entity ticks
> (otherwise
> the required update occurs in dequeue/put and we are done). Thus we can
> move
> the detection (and associated work) for these updates into the periodic
> path.
>
> This restores the 'atomicity' of update_curr() with respect to accounting.
>
> Signed-off-by: Paul Turner <pjt@google.com>
>
> ---
> kernel/sched_fair.c | 21 +++++++++++++++++----
> 1 file changed, 17 insertions(+), 4 deletions(-)
>
> Index: tip3/kernel/sched_fair.c
> ===================================================================
> --- tip3.orig/kernel/sched_fair.c
> +++ tip3/kernel/sched_fair.c
> @@ -564,11 +564,8 @@ __update_curr(struct cfs_rq *cfs_rq, str
>
> #if defined CONFIG_SMP && defined CONFIG_FAIR_GROUP_SCHED
> cfs_rq->load_unacc_exec_time += delta_exec;
> - if (cfs_rq->load_unacc_exec_time > sysctl_sched_shares_window) {
> - update_cfs_load(cfs_rq, 0);
> - update_cfs_shares(cfs_rq, 0);
> - }
> #endif
> }
>
> static void update_curr(struct cfs_rq *cfs_rq)
> @@ -809,6 +806,15 @@ static void update_cfs_shares(struct cfs
>
> reweight_entity(cfs_rq_of(se), se, shares);
> }
> +
> +static void update_cfs_rq_shares_tick(struct cfs_rq *cfs_rq)
> +{
> + /* rate limit updates by the averaging window */
> + if (cfs_rq->load_unacc_exec_time > sysctl_sched_shares_window) {
> + update_cfs_load(cfs_rq, 0);
> + update_cfs_shares(cfs_rq, 0);
> + }
> +}
> #else /* CONFIG_FAIR_GROUP_SCHED */
> static void update_cfs_load(struct cfs_rq *cfs_rq, int global_update)
> {
> @@ -1133,6 +1139,13 @@ entity_tick(struct cfs_rq *cfs_rq, struc
> */
> update_curr(cfs_rq);
>
> +#if defined CONFIG_SMP && defined CONFIG_FAIR_GROUP_SCHED
> + /*
> + * Update share accounting for long-running entities.
> + */
> + update_cfs_rq_shares_tick(cfs_rq);
> +#endif
> +
> #ifdef CONFIG_SCHED_HRTICK
> /*
> * queued ticks are scheduled to match the slice, so don't bother

Re: [patch 2/2] sched: charge unaccounted run-time on entity re-weight

[Paul Turner]

On 12/15/10 19:35, Paul Turner wrote:
> Hum -- forgot to refresh mbx file, slightly cleaner version (we can
> still charge unaccounted time against our queuing cfs_rq).
>

... Obviously this is supposed to be in lieu of the first patch.

I'm tired  :(

> - Paul
>
> -----
>
> sched: move periodic share updates to entity_tick()
>
> Long running entities that do not block (dequeue) require periodic
> updates to
> maintain accurate share values. (Note: group entities with several
> threads are
> quite likely to be non-blocking in many circumstances).
>
> By virtue of being long-running however, we will see entity ticks
> (otherwise
> the required update occurs in dequeue/put and we are done). Thus we can
> move
> the detection (and associated work) for these updates into the periodic
> path.
>
> This restores the 'atomicity' of update_curr() with respect to accounting.
>
> Signed-off-by: Paul Turner <pjt@google.com>
>
> ---
> kernel/sched_fair.c | 21 +++++++++++++++++----
> 1 file changed, 17 insertions(+), 4 deletions(-)
>
> Index: tip3/kernel/sched_fair.c
> ===================================================================
> --- tip3.orig/kernel/sched_fair.c
> +++ tip3/kernel/sched_fair.c
> @@ -564,11 +564,8 @@ __update_curr(struct cfs_rq *cfs_rq, str
>
> #if defined CONFIG_SMP && defined CONFIG_FAIR_GROUP_SCHED
> cfs_rq->load_unacc_exec_time += delta_exec;
> - if (cfs_rq->load_unacc_exec_time > sysctl_sched_shares_window) {
> - update_cfs_load(cfs_rq, 0);
> - update_cfs_shares(cfs_rq, 0);
> - }
> #endif
> }
>
> static void update_curr(struct cfs_rq *cfs_rq)
> @@ -809,6 +806,15 @@ static void update_cfs_shares(struct cfs
>
> reweight_entity(cfs_rq_of(se), se, shares);
> }
> +
> +static void update_cfs_rq_shares_tick(struct cfs_rq *cfs_rq)
> +{
> + /* rate limit updates by the averaging window */
> + if (cfs_rq->load_unacc_exec_time > sysctl_sched_shares_window) {
> + update_cfs_load(cfs_rq, 0);
> + update_cfs_shares(cfs_rq, 0);
> + }
> +}
> #else /* CONFIG_FAIR_GROUP_SCHED */
> static void update_cfs_load(struct cfs_rq *cfs_rq, int global_update)
> {
> @@ -1133,6 +1139,13 @@ entity_tick(struct cfs_rq *cfs_rq, struc
> */
> update_curr(cfs_rq);
>
> +#if defined CONFIG_SMP && defined CONFIG_FAIR_GROUP_SCHED
> + /*
> + * Update share accounting for long-running entities.
> + */
> + update_cfs_rq_shares_tick(cfs_rq);
> +#endif
> +
> #ifdef CONFIG_SCHED_HRTICK
> /*
> * queued ticks are scheduled to match the slice, so don't bother

Re: [patch 2/2] sched: charge unaccounted run-time on entity re-weight

[Peter Zijlstra]

On Wed, 2010-12-15 at 19:10 -0800, Paul Turner wrote:
> plain text document attachment (update_on_reweight.patch)
> Mike Galbraith reported poor interactivity[*] when the new shares distribution 
> code was combined with autogroups.
> 
> The root cause turns out to be a mis-ordering of accounting accrued execution
> time and shares updates.  Since update_curr() is issued hierarchically,
> updating the parent entity weights to reflect child enqueue/dequeue results in
> the parent's unaccounted execution time then being accrued (vs vruntime) at the
> new weight as opposed to the weight present at accumulation.
> 
> While this doesn't have much effect on processes with timeslices that cross a
> tick, it is particularly problematic for an interactive process (e.g. Xorg)
> which incurs many (tiny) timeslices.  In this scenario almost all updates are
> at dequeue which can result in significant fairness perturbation (especially if
> it is the only thread, resulting in potential {tg->shares, MIN_SHARES}
> transitions).
> 
> Correct this by ensuring unaccounted time is accumulated prior to manipulating
> an entity's weight.
> 
> [*] http://xkcd.com/619/ is perversely Nostradamian here.
> 
> Signed-off-by: Paul Turner <pjt@google.com>
> 
> ---
>  kernel/sched_fair.c |    6 +++++-
>  1 file changed, 5 insertions(+), 1 deletion(-)
> 
> Index: tip3/kernel/sched_fair.c
> ===================================================================
> --- tip3.orig/kernel/sched_fair.c
> +++ tip3/kernel/sched_fair.c
> @@ -767,8 +767,12 @@ static void update_cfs_load(struct cfs_r
>  static void reweight_entity(struct cfs_rq *cfs_rq, struct sched_entity *se,
>  			    unsigned long weight)
>  {
> -	if (se->on_rq)
> +	if (se->on_rq) {
> +		/* commit outstanding execution time */
> +		if (cfs_rq->curr == se)
> +			update_curr(cfs_rq);
>  		account_entity_dequeue(cfs_rq, se);
> +	}
>  
>  	update_load_set(&se->load, weight);
>  

Hrmm,. so we have:

entity_tick()
  update_curr()
  update_entity_shares_tick()
    update_cfs_shares()
      reweight_entity()


{en,de}queue_entity()
  update_curr()
  update_cfs_shares()
    reweight_entity()

{en,de}queue_task_fair()
  update_cfs_shares() (the other branch)

update_shares_cpu()
  update_cfs_shares()

So wouldn't something like the below be nicer?

---

Index: linux-2.6/kernel/sched_fair.c
===================================================================
--- linux-2.6.orig/kernel/sched_fair.c
+++ linux-2.6/kernel/sched_fair.c
@@ -1249,6 +1249,7 @@ enqueue_task_fair(struct rq *rq, struct
 	for_each_sched_entity(se) {
 		struct cfs_rq *cfs_rq = cfs_rq_of(se);
 
+		update_curr(cfs_rq);
 		update_cfs_load(cfs_rq, 0);
 		update_cfs_shares(cfs_rq, 0);
 	}
@@ -1279,6 +1280,7 @@ static void dequeue_task_fair(struct rq
 	for_each_sched_entity(se) {
 		struct cfs_rq *cfs_rq = cfs_rq_of(se);
 
+		update_curr(cfs_rq);
 		update_cfs_load(cfs_rq, 0);
 		update_cfs_shares(cfs_rq, 0);
 	}
@@ -2085,6 +2087,7 @@ static int update_shares_cpu(struct task
 	raw_spin_lock_irqsave(&rq->lock, flags);
 
 	update_rq_clock(rq);
+	update_curr(cfs_rq);
 	update_cfs_load(cfs_rq, 1);
 
 	/*

Re: [patch 2/2] sched: charge unaccounted run-time on entity re-weight

[Paul Turner]

On Thu, Dec 16, 2010 at 3:03 AM, Peter Zijlstra <a.p.zijlstra@chello.nl> wrote:
> On Wed, 2010-12-15 at 19:10 -0800, Paul Turner wrote:
>> plain text document attachment (update_on_reweight.patch)
>> Mike Galbraith reported poor interactivity[*] when the new shares distribution
>> code was combined with autogroups.
>>
>> The root cause turns out to be a mis-ordering of accounting accrued execution
>> time and shares updates.  Since update_curr() is issued hierarchically,
>> updating the parent entity weights to reflect child enqueue/dequeue results in
>> the parent's unaccounted execution time then being accrued (vs vruntime) at the
>> new weight as opposed to the weight present at accumulation.
>>
>> While this doesn't have much effect on processes with timeslices that cross a
>> tick, it is particularly problematic for an interactive process (e.g. Xorg)
>> which incurs many (tiny) timeslices.  In this scenario almost all updates are
>> at dequeue which can result in significant fairness perturbation (especially if
>> it is the only thread, resulting in potential {tg->shares, MIN_SHARES}
>> transitions).
>>
>> Correct this by ensuring unaccounted time is accumulated prior to manipulating
>> an entity's weight.
>>
>> [*] http://xkcd.com/619/ is perversely Nostradamian here.
>>
>> Signed-off-by: Paul Turner <pjt@google.com>
>>
>> ---
>>  kernel/sched_fair.c |    6 +++++-
>>  1 file changed, 5 insertions(+), 1 deletion(-)
>>
>> Index: tip3/kernel/sched_fair.c
>> ===================================================================
>> --- tip3.orig/kernel/sched_fair.c
>> +++ tip3/kernel/sched_fair.c
>> @@ -767,8 +767,12 @@ static void update_cfs_load(struct cfs_r
>>  static void reweight_entity(struct cfs_rq *cfs_rq, struct sched_entity *se,
>>                           unsigned long weight)
>>  {
>> -     if (se->on_rq)
>> +     if (se->on_rq) {
>> +             /* commit outstanding execution time */
>> +             if (cfs_rq->curr == se)
>> +                     update_curr(cfs_rq);
>>               account_entity_dequeue(cfs_rq, se);
>> +     }
>>
>>       update_load_set(&se->load, weight);
>>
>
> Hrmm,. so we have:
>
> entity_tick()
>  update_curr()
>  update_entity_shares_tick()
>    update_cfs_shares()
>      reweight_entity()
>
>
> {en,de}queue_entity()
>  update_curr()
>  update_cfs_shares()
>    reweight_entity()
>
> {en,de}queue_task_fair()
>  update_cfs_shares() (the other branch)
>
> update_shares_cpu()
>  update_cfs_shares()
>
> So wouldn't something like the below be nicer?
>

That doesn't quite work.

The problem stems from:

- update_curr() accues time against current cfs_rq's timeline
  - We always need to do this for entity placement
  - Manipulation of the current cfs_rq's load affects its weights

However the current cfs_rq in the problem case is a group entity which
happens to be the current entity on the parenting se's group_cfs_rq
(say that 10 times fast).

When we update that entity's (call it X) weight to reflect the
interactions on its owned cfs_rq, the update isout of order with the
subsequent update_curr() on the parent which is what actually accounts
the accrued vruntime versus X (which was accumulated at old weight)

We need to either:

A) Get all of the update_currs() done up front, e.g. at the start of
enqueue_task_fair add another for_each
- I don't like this approach because it it becomes a concern that has
to be implemented by all callers
- There's also no point in issuing these if the entity in question
isnt cfs_rq->curr since there's no time to account in that case

B) Change the reweights in enqueue/dequeue/etc to occur against the
owned cfs_rq as opposed to the queueing cfs_rq.
- This is not really clean in my mind since it steps outside of the
semantic of we are "enqueuing E to T".  Instead of only really
manipulating T we're adding "oh and we'll finish manipulations
resulting from prior enqeues against E if it was a tree".

C) Charge unaccounted time versus an entity before re-weighting it
- I think this ends up being the nicest, we only end up issuing the
extra update_currs when we need them, and the second becomes a nop
since rq->clock doesn't move.  Not to mention it also blocks up this
hole completely since it becomes always safe to reweight_entity().



> ---
>
> Index: linux-2.6/kernel/sched_fair.c
> ===================================================================
> --- linux-2.6.orig/kernel/sched_fair.c
> +++ linux-2.6/kernel/sched_fair.c
> @@ -1249,6 +1249,7 @@ enqueue_task_fair(struct rq *rq, struct
>        for_each_sched_entity(se) {
>                struct cfs_rq *cfs_rq = cfs_rq_of(se);
>
> +               update_curr(cfs_rq);
>                update_cfs_load(cfs_rq, 0);
>                update_cfs_shares(cfs_rq, 0);
>        }
> @@ -1279,6 +1280,7 @@ static void dequeue_task_fair(struct rq
>        for_each_sched_entity(se) {
>                struct cfs_rq *cfs_rq = cfs_rq_of(se);
>
> +               update_curr(cfs_rq);

This would be out of order with the updated weights below

>                update_cfs_load(cfs_rq, 0);
>                update_cfs_shares(cfs_rq, 0);
>        }
> @@ -2085,6 +2087,7 @@ static int update_shares_cpu(struct task
>        raw_spin_lock_irqsave(&rq->lock, flags);
>
>        update_rq_clock(rq);
> +       update_curr(cfs_rq);

Likewise

>        update_cfs_load(cfs_rq, 1);
>
>        /*
>
>
>

Re: [patch 2/2] sched: charge unaccounted run-time on entity re-weight

[Peter Zijlstra]

On Thu, 2010-12-16 at 14:31 -0800, Paul Turner wrote:

> That doesn't quite work.
> 
> The problem stems from:
> 
> - update_curr() accues time against current cfs_rq's timeline
>   - We always need to do this for entity placement
>   - Manipulation of the current cfs_rq's load affects its weights

> However the current cfs_rq in the problem case is a group entity which
> happens to be the current entity on the parenting se's group_cfs_rq
> (say that 10 times fast).
> 
> When we update that entity's (call it X) weight to reflect the
> interactions on its owned cfs_rq, the update isout of order with the
> subsequent update_curr() on the parent which is what actually accounts
> the accrued vruntime versus X (which was accumulated at old weight)
> 
> We need to either:
> 
> A) Get all of the update_currs() done up front, e.g. at the start of
> enqueue_task_fair add another for_each
> - I don't like this approach because it it becomes a concern that has
> to be implemented by all callers
> - There's also no point in issuing these if the entity in question
> isnt cfs_rq->curr since there's no time to account in that case
> 
> B) Change the reweights in enqueue/dequeue/etc to occur against the
> owned cfs_rq as opposed to the queueing cfs_rq.
> - This is not really clean in my mind since it steps outside of the
> semantic of we are "enqueuing E to T".  Instead of only really
> manipulating T we're adding "oh and we'll finish manipulations
> resulting from prior enqeues against E if it was a tree".

I knew there was a reason I did it like that early on ;-)

> C) Charge unaccounted time versus an entity before re-weighting it
> - I think this ends up being the nicest, we only end up issuing the
> extra update_currs when we need them, and the second becomes a nop
> since rq->clock doesn't move.  Not to mention it also blocks up this
> hole completely since it becomes always safe to reweight_entity().

Hrmm, I see what you mean, its not exactly pretty either, but I must
admit to not seeing a better solution at the moment.

OK, so your patch it is ;-)

[tip:sched/core] sched: Fix interactivity bug by charging unaccounted run-time on entity re-weight

[tip-bot for Paul Turner]

Commit-ID:  19e5eebb8eaa5ca3ff8aa18cb57ccb7a9f67277d
Gitweb:     http://git.kernel.org/tip/19e5eebb8eaa5ca3ff8aa18cb57ccb7a9f67277d
Author:     Paul Turner <pjt@google.com>
AuthorDate: Wed, 15 Dec 2010 19:10:18 -0800
Committer:  Ingo Molnar <mingo@elte.hu>
CommitDate: Sun, 19 Dec 2010 16:36:30 +0100

sched: Fix interactivity bug by charging unaccounted run-time on entity re-weight

Mike Galbraith reported poor interactivity[*] when the new shares distribution
code was combined with autogroups.

The root cause turns out to be a mis-ordering of accounting accrued execution
time and shares updates.  Since update_curr() is issued hierarchically,
updating the parent entity weights to reflect child enqueue/dequeue results in
the parent's unaccounted execution time then being accrued (vs vruntime) at the
new weight as opposed to the weight present at accumulation.

While this doesn't have much effect on processes with timeslices that cross a
tick, it is particularly problematic for an interactive process (e.g. Xorg)
which incurs many (tiny) timeslices.  In this scenario almost all updates are
at dequeue which can result in significant fairness perturbation (especially if
it is the only thread, resulting in potential {tg->shares, MIN_SHARES}
transitions).

Correct this by ensuring unaccounted time is accumulated prior to manipulating
an entity's weight.

[*] http://xkcd.com/619/ is perversely Nostradamian here.

Signed-off-by: Paul Turner <pjt@google.com>
Signed-off-by: Peter Zijlstra <a.p.zijlstra@chello.nl>
Cc: Mike Galbraith <efault@gmx.de>
Cc: Linus Torvalds <torvalds@linux-foundation.org>
LKML-Reference: <20101216031038.159704378@google.com>
Signed-off-by: Ingo Molnar <mingo@elte.hu>
---
 kernel/sched_fair.c |    6 +++++-
 1 files changed, 5 insertions(+), 1 deletions(-)

diff --git a/kernel/sched_fair.c b/kernel/sched_fair.c
index 16ee398..c62ebae 100644
--- a/kernel/sched_fair.c
+++ b/kernel/sched_fair.c
@@ -765,8 +765,12 @@ static void update_cfs_load(struct cfs_rq *cfs_rq, int global_update)
 static void reweight_entity(struct cfs_rq *cfs_rq, struct sched_entity *se,
 			    unsigned long weight)
 {
-	if (se->on_rq)
+	if (se->on_rq) {
+		/* commit outstanding execution time */
+		if (cfs_rq->curr == se)
+			update_curr(cfs_rq);
 		account_entity_dequeue(cfs_rq, se);
+	}
 
 	update_load_set(&se->load, weight);