Fix interactivity buglet with autogroup and shares distribution re-write

I made that:

---
Subject: sched: Move periodic share updates to entity_tick()
From: Paul Turner <[email protected]>
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 <[email protected]>

Signed-off-by Peter Zijlstra <[email protected]>

LKML-Reference: <[email protected]>

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

Index: linux-2.6/kernel/sched_fair.c
===================================================================

kernel/sched_fair.c +17 -4

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

Quoted 1 line · Peter Zijlstra

I made that:

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

Quoted 76 lines

---
Subject: sched: Move periodic share updates to entity_tick()
From: Paul Turner <[email protected]>
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 <[email protected]>

Signed-off-by Peter Zijlstra <[email protected]>

LKML-Reference: <[email protected]>
---
 kernel/sched_fair.c |   21 +++++++++++++++++----

 1 file changed, 17 insertions(+), 4 deletions(-)

Index: linux-2.6/kernel/sched_fair.c
===================================================================

kernel/sched_fair.c +17 -4

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

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

Quoted 84 lines · Mike Galbraith

Quoted 1 line · Peter Zijlstra

I made that:

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

Quoted 76 lines

---
Subject: sched: Move periodic share updates to entity_tick()
From: Paul Turner <[email protected]>
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 <[email protected]>

Signed-off-by Peter Zijlstra <[email protected]>

LKML-Reference: <[email protected]>
---
 kernel/sched_fair.c |   21 +++++++++++++++++----

 1 file changed, 17 insertions(+), 4 deletions(-)

Index: linux-2.6/kernel/sched_fair.c
===================================================================

kernel/sched_fair.c +17 -4

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

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 <[email protected]>

---
kernel/sched_fair.c | 21 +++++++++++++++++----

1 file changed, 17 insertions(+), 4 deletions(-)

Index: tip3/kernel/sched_fair.c
===================================================================

kernel/sched_fair.c +16 -4

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

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 <[email protected]>

---
kernel/sched_fair.c | 21 +++++++++++++++++----

1 file changed, 17 insertions(+), 4 deletions(-)

Index: tip3/kernel/sched_fair.c
===================================================================

kernel/sched_fair.c +16 -4

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

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 <[email protected]>

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

Index: tip3/kernel/sched_fair.c
===================================================================

kernel/sched_fair.c +0 -0

@@ -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)
 {

Quoted 36 lines · Paul Turner

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 <[email protected]>

---
 kernel/sched_fair.c |    6 +++++-

 1 file changed, 5 insertions(+), 1 deletion(-)

Index: tip3/kernel/sched_fair.c
===================================================================

kernel/sched_fair.c +0 -0

@@ -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)
  {

kernel/sched_fair.c static void update_cfs_load(struct cfs_r · line 778

Quoted 10 lines

kernel/sched_fair.c +5 -1

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

kernel/sched_fair.c +1 -0

@@ -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);
        }

kernel/sched_fair.c +0 -0

        update_cfs_load(cfs_rq, 1);
 
        /*

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().