sched: bandwidth-control tweaks for v3.2

PATCH In review Paul Turner 5 participants 15 messages Nov 8, 2011 – Nov 18, 2011

lore

Share & tools

lore

Paul Turner

author

2011-11-08 04:29 UTC #0 lore raw

cover sched: bandwidth-control tweaks for v3.2

Hi,

Please find attached a few minor tweaks for bandwidth control that are worth considering for 3.2

The first two are a performance improvement for the !enabled case and a buglet fix. While the last makes idle_balance() work with throttling.

Thanks,

- Paul

Paul Turner

author

2011-11-08 04:30 UTC #1 lore raw

PATCH 1/3 sched: use jump labels to reduce overhead when bandwidth control is inactive

Now that the linkage of jump-labels has been fixed they show a measurable improvement in overhead for the enabled-but-unused case.

Workload is:
'taskset -c 0 perf stat --repeat 50 -e instructions,cycles,branches bash -c "for ((i=0;i<5;i++)); do $(dirname $0)/pipe-test 20000; done"'

instructions cycles branches
-------------------------------------------------------------------------
Intel Westmere

base            806611770               745895590               146765378
+jumplabel      803090165 (-0.44)       713381840 (-4.36)       144561130

AMD Barcelona

base            824657415               740055589               148855354
+jumplabel      821056910 (-0.44)       737558389 (-0.34)       146635229

Signed-off-by Paul Turner <[email protected]>

---
 kernel/sched.c      |   33 +++++++++++++++++++++++++++++++--
 kernel/sched_fair.c |   17 +++++++++++++----
 2 files changed, 44 insertions(+), 6 deletions(-)

kernel/sched.c +31 -2

Index: tip/kernel/sched.c
===================================================================
@@ -71,6 +71,7 @@
 #include <linux/ctype.h>
 #include <linux/ftrace.h>
 #include <linux/slab.h>
+#include <linux/jump_label.h>
 
 #include <asm/tlb.h>
 #include <asm/irq_regs.h>

@@ -502,7 +503,32 @@ static void destroy_cfs_bandwidth(struct
 	hrtimer_cancel(&cfs_b->period_timer);
 	hrtimer_cancel(&cfs_b->slack_timer);
 }
-#else
+
+#ifdef HAVE_JUMP_LABEL
+static struct jump_label_key __cfs_bandwidth_used;
+
+static inline bool cfs_bandwidth_used(void)
+{
+	return static_branch(&__cfs_bandwidth_used);
+}
+
+static void account_cfs_bandwidth_used(int enabled, int was_enabled)
+{
+	/* only need to count groups transitioning between enabled/!enabled */
+	if (enabled && !was_enabled)
+		jump_label_inc(&__cfs_bandwidth_used);
+	else if (!enabled && was_enabled)
+		jump_label_dec(&__cfs_bandwidth_used);
+}
+#else /* !HAVE_JUMP_LABEL */
+/* static_branch doesn't help unless supported */
+static int cfs_bandwidth_used(void)
+{
+	return 1;
+}
+static void account_cfs_bandwidth_used(int enabled, int was_enabled) {}
+#endif /* HAVE_JUMP_LABEL */
+#else /* !CONFIG_CFS_BANDWIDTH */
 static void init_cfs_rq_runtime(struct cfs_rq *cfs_rq) {}
 static void init_cfs_bandwidth(struct cfs_bandwidth *cfs_b) {}
 static void destroy_cfs_bandwidth(struct cfs_bandwidth *cfs_b) {}

@@ -9188,7 +9214,7 @@ static int __cfs_schedulable(struct task
 
 static int tg_set_cfs_bandwidth(struct task_group *tg, u64 period, u64 quota)
 {
-	int i, ret = 0, runtime_enabled;
+	int i, ret = 0, runtime_enabled, runtime_was_enabled;
 	struct cfs_bandwidth *cfs_b = tg_cfs_bandwidth(tg);
 
 	if (tg == &root_task_group)

@@ -9216,6 +9242,9 @@ static int tg_set_cfs_bandwidth(struct t
 		goto out_unlock;
 
 	runtime_enabled = quota != RUNTIME_INF;
+	runtime_was_enabled = cfs_b->quota != RUNTIME_INF;
+	account_cfs_bandwidth_used(runtime_enabled, runtime_was_enabled);
+
 	raw_spin_lock_irq(&cfs_b->lock);
 	cfs_b->period = ns_to_ktime(period);
 	cfs_b->quota = quota;

kernel/sched_fair.c +12 -3

Index: tip/kernel/sched_fair.c
===================================================================
@@ -1408,7 +1408,7 @@ static void __account_cfs_rq_runtime(str
 static __always_inline void account_cfs_rq_runtime(struct cfs_rq *cfs_rq,
 						   unsigned long delta_exec)
 {
-	if (!cfs_rq->runtime_enabled)
+	if (!cfs_bandwidth_used() || !cfs_rq->runtime_enabled)
 		return;
 
 	__account_cfs_rq_runtime(cfs_rq, delta_exec);

@@ -1416,13 +1416,13 @@ static __always_inline void account_cfs_
 
 static inline int cfs_rq_throttled(struct cfs_rq *cfs_rq)
 {
-	return cfs_rq->throttled;
+	return cfs_bandwidth_used() && cfs_rq->throttled;
 }
 
 /* check whether cfs_rq, or any parent, is throttled */
 static inline int throttled_hierarchy(struct cfs_rq *cfs_rq)
 {
-	return cfs_rq->throttle_count;
+	return cfs_bandwidth_used() && cfs_rq->throttle_count;
 }
 
 /*

@@ -1743,6 +1743,9 @@ static void __return_cfs_rq_runtime(stru
 
 static __always_inline void return_cfs_rq_runtime(struct cfs_rq *cfs_rq)
 {
+	if (!cfs_bandwidth_used())
+		return;
+
 	if (!cfs_rq->runtime_enabled || !cfs_rq->nr_running)
 		return;

@@ -1788,6 +1791,9 @@ static void do_sched_cfs_slack_timer(str
  */
 static void check_enqueue_throttle(struct cfs_rq *cfs_rq)
 {
+	if (!cfs_bandwidth_used())
+		return;
+
 	/* an active group must be handled by the update_curr()->put() path */
 	if (!cfs_rq->runtime_enabled || cfs_rq->curr)
 		return;

@@ -1805,6 +1811,9 @@ static void check_enqueue_throttle(struc
 /* conditionally throttle active cfs_rq's from put_prev_entity() */
 static void check_cfs_rq_runtime(struct cfs_rq *cfs_rq)
 {
+	if (!cfs_bandwidth_used())
+		return;
+
 	if (likely(!cfs_rq->runtime_enabled || cfs_rq->runtime_remaining > 0))
 		return;

Peter Zijlstra

2011-11-08 09:26 UTC #2 lore raw

Re: [patch 1/3] sched: use jump labels to reduce overhead when bandwidth control is inactive

kernel/sched.c static void destroy_cfs_bandwidth(struct · line 522

Quoted 8 lines · Paul Turner

kernel/sched.c +8 -0

+static void account_cfs_bandwidth_used(int enabled, int was_enabled)
+{
+       /* only need to count groups transitioning between enabled/!enabled */
+       if (enabled && !was_enabled)
+               jump_label_inc(&__cfs_bandwidth_used);
+       else if (!enabled && was_enabled)
+               jump_label_dec(&__cfs_bandwidth_used);
+}

Can't you use jump_label_enabled(&__cfs_bandwidth_used) to was_enabled ?

Peter Zijlstra

2011-11-08 09:28 UTC #3 lore raw

Re: [patch 1/3] sched: use jump labels to reduce overhead when bandwidth control is inactive

In reply to Paul Turner

Quoted 11 lines · Peter Zijlstra

kernel/sched.c static void destroy_cfs_bandwidth(struct · line 522

Quoted 8 lines · Paul Turner

kernel/sched.c +8 -0

+static void account_cfs_bandwidth_used(int enabled, int was_enabled)
+{
+       /* only need to count groups transitioning between enabled/!enabled */
+       if (enabled && !was_enabled)
+               jump_label_inc(&__cfs_bandwidth_used);
+       else if (!enabled && was_enabled)
+               jump_label_dec(&__cfs_bandwidth_used);
+}

Can't you use jump_label_enabled(&__cfs_bandwidth_used) to was_enabled ?

n/m I'm not awake yet..

Peter Zijlstra

2011-11-08 09:29 UTC #4 lore raw

Re: [patch 1/3] sched: use jump labels to reduce overhead when bandwidth control is inactive

In reply to Paul Turner

Quoted 11 lines · Paul Turner

kernel/sched_fair.c +3 -0

@@ -1788,6 +1791,9 @@ static void do_sched_cfs_slack_timer(str
  */
 static void check_enqueue_throttle(struct cfs_rq *cfs_rq)
 {
+       if (!cfs_bandwidth_used())
+               return;
+
        /* an active group must be handled by the update_curr()->put() path */
        if (!cfs_rq->runtime_enabled || cfs_rq->curr)
                return;

kernel/sched_fair.c static void check_enqueue_throttle(struc · line 1819

Quoted 9 lines

kernel/sched_fair.c +3 -0

@@ -1805,6 +1811,9 @@ static void check_enqueue_throttle(struc
 /* conditionally throttle active cfs_rq's from put_prev_entity() */
 static void check_cfs_rq_runtime(struct cfs_rq *cfs_rq)
 {
+       if (!cfs_bandwidth_used())
+               return;
+
        if (likely(!cfs_rq->runtime_enabled || cfs_rq->runtime_remaining > 0))
                return;

does it matter if you pull this out into an inline function like:

static __always_inline void check_enqueue_throttle(struct cfs_rq *cfs_rq)

{
	if (cfs_bandwidth_used())
		__check_enqueue_throttle(cfs_rq);
}

That would avoid the superfluous function call as well.

Paul Turner

author

2011-11-11 04:23 UTC #5 lore raw

Re: [patch 1/3] sched: use jump labels to reduce overhead when bandwidth control is inactive

Quoted 24 lines · Peter Zijlstra

Quoted 11 lines · Paul Turner

kernel/sched_fair.c +3 -0

@@ -1788,6 +1791,9 @@ static void do_sched_cfs_slack_timer(str
   */
  static void check_enqueue_throttle(struct cfs_rq *cfs_rq)
  {
+       if (!cfs_bandwidth_used())
+               return;
+
         /* an active group must be handled by the update_curr()->put() path */
         if (!cfs_rq->runtime_enabled || cfs_rq->curr)
                 return;

kernel/sched_fair.c static void check_enqueue_throttle(struc · line 1819

Quoted 9 lines

kernel/sched_fair.c +3 -0

@@ -1805,6 +1811,9 @@ static void check_enqueue_throttle(struc
  /* conditionally throttle active cfs_rq's from put_prev_entity() */
  static void check_cfs_rq_runtime(struct cfs_rq *cfs_rq)
  {
+       if (!cfs_bandwidth_used())
+               return;
+
         if (likely(!cfs_rq->runtime_enabled || cfs_rq->runtime_remaining>  0))
                 return;

does it matter if you pull this out into an inline function like:

Quoted 7 lines

static __always_inline void check_enqueue_throttle(struct cfs_rq *cfs_rq)
{
	if (cfs_bandwidth_used())
		__check_enqueue_throttle(cfs_rq);
}
That would avoid the superfluous function call as well.

This this is the only call-site it's being inlined already so there's no difference atm. That said, check_enqueue_throttle is sufficiently small we could just add __always_inline to force this to be the default behavior and avoid any surprises from this in the future.

Let me know if you'd like me to re-post with this added.

- Paul

tip-bot for Paul Turner

author

2011-11-18 23:42 UTC #6 lore raw

[tip:sched/core] sched: Use jump labels to reduce overhead when bandwidth control is inactive

In reply to Paul Turner

Commit-ID:  56f570e512eeb5b412cb3a62234adc446a8eb32b
Gitweb:     http://git.kernel.org/tip/56f570e512eeb5b412cb3a62234adc446a8eb32b
Author:     Paul Turner <[email protected]>
AuthorDate: Mon, 7 Nov 2011 20:26:33 -0800
Committer:  Ingo Molnar <[email protected]>
CommitDate: Wed, 16 Nov 2011 08:48:18 +0100

sched: Use jump labels to reduce overhead when bandwidth control is inactive

Now that the linkage of jump-labels has been fixed they show a measurable improvement in overhead for the enabled-but-unused case.

Workload is:

'taskset -c 0 perf stat --repeat 50 -e instructions,cycles,branches
bash -c "for ((i=0;i<5;i++)); do $(dirname $0)/pipe-test 20000; done"'

There's a speedup for all situations:

instructions cycles branches
-------------------------------------------------------------------------
Intel Westmere

 base            806611770               745895590               146765378
 +jumplabel      803090165 (-0.44%)      713381840 (-4.36%)      144561130

AMD Barcelona

 base            824657415               740055589               148855354
 +jumplabel      821056910 (-0.44%)      737558389 (-0.34%)      146635229

Signed-off-by Paul Turner <[email protected]>

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

Link http://lkml.kernel.org/r/[email protected] open here

Signed-off-by Ingo Molnar <[email protected]>

---
 kernel/sched.c      |   33 +++++++++++++++++++++++++++++++--
 kernel/sched_fair.c |   15 ++++++++++++---
 2 files changed, 43 insertions(+), 5 deletions(-)

kernel/sched.c +31 -2

index d6b149c..d9d79a4 100644
@@ -72,6 +72,7 @@
 #include <linux/ftrace.h>
 #include <linux/slab.h>
 #include <linux/init_task.h>
+#include <linux/jump_label.h>
 
 #include <asm/tlb.h>
 #include <asm/irq_regs.h>

@@ -503,7 +504,32 @@ static void destroy_cfs_bandwidth(struct cfs_bandwidth *cfs_b)
 	hrtimer_cancel(&cfs_b->period_timer);
 	hrtimer_cancel(&cfs_b->slack_timer);
 }
-#else
+
+#ifdef HAVE_JUMP_LABEL
+static struct jump_label_key __cfs_bandwidth_used;
+
+static inline bool cfs_bandwidth_used(void)
+{
+	return static_branch(&__cfs_bandwidth_used);
+}
+
+static void account_cfs_bandwidth_used(int enabled, int was_enabled)
+{
+	/* only need to count groups transitioning between enabled/!enabled */
+	if (enabled && !was_enabled)
+		jump_label_inc(&__cfs_bandwidth_used);
+	else if (!enabled && was_enabled)
+		jump_label_dec(&__cfs_bandwidth_used);
+}
+#else /* !HAVE_JUMP_LABEL */
+/* static_branch doesn't help unless supported */
+static int cfs_bandwidth_used(void)
+{
+	return 1;
+}
+static void account_cfs_bandwidth_used(int enabled, int was_enabled) {}
+#endif /* HAVE_JUMP_LABEL */
+#else /* !CONFIG_CFS_BANDWIDTH */
 static void init_cfs_rq_runtime(struct cfs_rq *cfs_rq) {}
 static void init_cfs_bandwidth(struct cfs_bandwidth *cfs_b) {}
 static void destroy_cfs_bandwidth(struct cfs_bandwidth *cfs_b) {}

@@ -9203,7 +9229,7 @@ static int __cfs_schedulable(struct task_group *tg, u64 period, u64 runtime);
 
 static int tg_set_cfs_bandwidth(struct task_group *tg, u64 period, u64 quota)
 {
-	int i, ret = 0, runtime_enabled;
+	int i, ret = 0, runtime_enabled, runtime_was_enabled;
 	struct cfs_bandwidth *cfs_b = tg_cfs_bandwidth(tg);
 
 	if (tg == &root_task_group)

@@ -9231,6 +9257,9 @@ static int tg_set_cfs_bandwidth(struct task_group *tg, u64 period, u64 quota)
 		goto out_unlock;
 
 	runtime_enabled = quota != RUNTIME_INF;
+	runtime_was_enabled = cfs_b->quota != RUNTIME_INF;
+	account_cfs_bandwidth_used(runtime_enabled, runtime_was_enabled);
+
 	raw_spin_lock_irq(&cfs_b->lock);
 	cfs_b->period = ns_to_ktime(period);
 	cfs_b->quota = quota;

kernel/sched_fair.c +12 -3

index a78ed27..a608593 100644
@@ -1421,7 +1421,7 @@ static void __account_cfs_rq_runtime(struct cfs_rq *cfs_rq,
 static __always_inline void account_cfs_rq_runtime(struct cfs_rq *cfs_rq,
 						   unsigned long delta_exec)
 {
-	if (!cfs_rq->runtime_enabled)
+	if (!cfs_bandwidth_used() || !cfs_rq->runtime_enabled)
 		return;
 
 	__account_cfs_rq_runtime(cfs_rq, delta_exec);

@@ -1429,13 +1429,13 @@ static __always_inline void account_cfs_rq_runtime(struct cfs_rq *cfs_rq,
 
 static inline int cfs_rq_throttled(struct cfs_rq *cfs_rq)
 {
-	return cfs_rq->throttled;
+	return cfs_bandwidth_used() && cfs_rq->throttled;
 }
 
 /* check whether cfs_rq, or any parent, is throttled */
 static inline int throttled_hierarchy(struct cfs_rq *cfs_rq)
 {
-	return cfs_rq->throttle_count;
+	return cfs_bandwidth_used() && cfs_rq->throttle_count;
 }
 
 /*

@@ -1756,6 +1756,9 @@ static void __return_cfs_rq_runtime(struct cfs_rq *cfs_rq)
 
 static __always_inline void return_cfs_rq_runtime(struct cfs_rq *cfs_rq)
 {
+	if (!cfs_bandwidth_used())
+		return;
+
 	if (!cfs_rq->runtime_enabled || cfs_rq->nr_running)
 		return;

@@ -1801,6 +1804,9 @@ static void do_sched_cfs_slack_timer(struct cfs_bandwidth *cfs_b)
  */
 static void check_enqueue_throttle(struct cfs_rq *cfs_rq)
 {
+	if (!cfs_bandwidth_used())
+		return;
+
 	/* an active group must be handled by the update_curr()->put() path */
 	if (!cfs_rq->runtime_enabled || cfs_rq->curr)
 		return;

@@ -1818,6 +1824,9 @@ static void check_enqueue_throttle(struct cfs_rq *cfs_rq)
 /* conditionally throttle active cfs_rq's from put_prev_entity() */
 static void check_cfs_rq_runtime(struct cfs_rq *cfs_rq)
 {
+	if (!cfs_bandwidth_used())
+		return;
+
 	if (likely(!cfs_rq->runtime_enabled || cfs_rq->runtime_remaining > 0))
 		return;

Paul Turner

author

2011-11-08 04:29 UTC #7 lore raw

PATCH 2/3 sched: fix buglet in return_cfs_rq_runtime()

In reply to Paul Turner

In return_cfs_rq_runtime() we want to return bandwidth when there are no remaining tasks, not "return" when this is the case.

Signed-off-by Paul Turner <[email protected]>

---
 kernel/sched_fair.c |    2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

kernel/sched_fair.c +1 -1

Index: tip/kernel/sched_fair.c
===================================================================
@@ -1746,7 +1746,7 @@ static __always_inline void return_cfs_r
 	if (!cfs_bandwidth_used())
 		return;
 
-	if (!cfs_rq->runtime_enabled || !cfs_rq->nr_running)
+	if (!cfs_rq->runtime_enabled || cfs_rq->nr_running)
 		return;
 
 	__return_cfs_rq_runtime(cfs_rq);

tip-bot for Paul Turner

author

2011-11-18 23:41 UTC #8 lore raw

[tip:sched/core] sched: Fix buglet in return_cfs_rq_runtime()

Commit-ID:  fccfdc6f0d8c83c854eeb6d93aa158f0e551bd49
Gitweb:     http://git.kernel.org/tip/fccfdc6f0d8c83c854eeb6d93aa158f0e551bd49
Author:     Paul Turner <[email protected]>
AuthorDate: Mon, 7 Nov 2011 20:26:34 -0800
Committer:  Ingo Molnar <[email protected]>
CommitDate: Wed, 16 Nov 2011 08:43:45 +0100

sched: Fix buglet in return_cfs_rq_runtime()

In return_cfs_rq_runtime() we want to return bandwidth when there are no remaining tasks, not "return" when this is the case.

Signed-off-by Paul Turner <[email protected]>

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

Link http://lkml.kernel.org/r/[email protected] open here

Signed-off-by Ingo Molnar <[email protected]>

---
 kernel/sched_fair.c |    2 +-
 1 files changed, 1 insertions(+), 1 deletions(-)

kernel/sched_fair.c +1 -1

index ba0e1f4..a78ed27 100644
@@ -1756,7 +1756,7 @@ static void __return_cfs_rq_runtime(struct cfs_rq *cfs_rq)
 
 static __always_inline void return_cfs_rq_runtime(struct cfs_rq *cfs_rq)
 {
-	if (!cfs_rq->runtime_enabled || !cfs_rq->nr_running)
+	if (!cfs_rq->runtime_enabled || cfs_rq->nr_running)
 		return;
 
 	__return_cfs_rq_runtime(cfs_rq);

Paul Turner

author

2011-11-08 04:29 UTC #9 lore raw

PATCH 3/3 From: Ben Segall <[email protected]>

In reply to Paul Turner

sched: update task accounting on throttle so that idle_balance() will trigger

Since throttling occurs in the put_prev_task() path we do not get to observe this delta against nr_running when making the decision to idle_balance().

Fix this by first enumerating cfs_rq throttle states so that we can distinguish throttling cfs_rqs. Then remove tasks that will be throttled in put_prev_task from rq->nr_running/cfs_rq->h_nr_running when in account_cfs_rq_runtime, rather than delaying until put_prev_task.

This allows schedule() to call idle_balance when we go idle due to throttling.

Using Kamalesh's nested-cgroup test case[1] we see the following improvement on a 16 core system:
baseline: Average CPU Idle percentage 13.9667%
+patch: Average CPU Idle percentage 3.53333%
[1]: https://lkml.org/lkml/2011/9/15/261

Signed-off-by Ben Segall <[email protected]>

Signed-off-by Paul Turner <[email protected]>

---
 kernel/sched.c      |   24 ++++++++----
 kernel/sched_fair.c |  101 ++++++++++++++++++++++++++++++++++++----------------
 2 files changed, 87 insertions(+), 38 deletions(-)

kernel/sched.c +17 -7

Index: tip/kernel/sched.c
===================================================================
@@ -269,6 +269,13 @@ struct cfs_bandwidth {
 #endif
 };
 
+enum runtime_state {
+	RUNTIME_UNLIMITED,
+	RUNTIME_AVAILABLE,
+	RUNTIME_THROTTLING,
+	RUNTIME_THROTTLED
+};
+
 /* task group related information */
 struct task_group {
 	struct cgroup_subsys_state css;

@@ -402,12 +409,12 @@ struct cfs_rq {
 	unsigned long load_contribution;
 #endif
 #ifdef CONFIG_CFS_BANDWIDTH
-	int runtime_enabled;
+	enum runtime_state runtime_state;
 	u64 runtime_expires;
 	s64 runtime_remaining;
 
 	u64 throttled_timestamp;
-	int throttled, throttle_count;
+	int throttle_count;
 	struct list_head throttled_list;
 #endif
 #endif

@@ -470,7 +477,7 @@ static void init_cfs_bandwidth(struct cf
 
 static void init_cfs_rq_runtime(struct cfs_rq *cfs_rq)
 {
-	cfs_rq->runtime_enabled = 0;
+	cfs_rq->runtime_state = RUNTIME_UNLIMITED;
 	INIT_LIST_HEAD(&cfs_rq->throttled_list);
 }

@@ -6368,7 +6375,7 @@ static void unthrottle_offline_cfs_rqs(s
 	for_each_leaf_cfs_rq(rq, cfs_rq) {
 		struct cfs_bandwidth *cfs_b = tg_cfs_bandwidth(cfs_rq->tg);
 
-		if (!cfs_rq->runtime_enabled)
+		if (!cfs_rq_runtime_enabled(cfs_rq))
 			continue;
 
 		/*

@@ -9263,11 +9270,14 @@ static int tg_set_cfs_bandwidth(struct t
 		struct rq *rq = rq_of(cfs_rq);
 
 		raw_spin_lock_irq(&rq->lock);
-		cfs_rq->runtime_enabled = runtime_enabled;
-		cfs_rq->runtime_remaining = 0;
-
 		if (cfs_rq_throttled(cfs_rq))
 			unthrottle_cfs_rq(cfs_rq);
+
+		if (runtime_enabled)
+			cfs_rq->runtime_state = RUNTIME_AVAILABLE;
+		else
+			cfs_rq->runtime_state = RUNTIME_UNLIMITED;
+		cfs_rq->runtime_remaining = 0;
 		raw_spin_unlock_irq(&rq->lock);
 	}
 out_unlock:

kernel/sched_fair.c +70 ~~-31~~

180 lines not on this page · raw message

Paul Turner

author

2011-11-10 02:29 UTC #10 lore raw

Re: [patch 3/3] From: Ben Segall <[email protected]>

I mangled the subject/from headers on this one, fixed should be below.

Thanks,

- Paul
---

sched: update task accounting on throttle so that idle_balance() will trigger
From: Ben Segall <[email protected]>

Since throttling occurs in the put_prev_task() path we do not get to observe this delta against nr_running when making the decision to idle_balance().

This allows schedule() to call idle_balance when we go idle due to throttling.

Signed-off-by Ben Segall <[email protected]>

Signed-off-by Paul Turner <[email protected]>

---
 kernel/sched.c      |   24 ++++++++----
 kernel/sched_fair.c |  101 ++++++++++++++++++++++++++++++++++++----------------
 2 files changed, 87 insertions(+), 38 deletions(-)

kernel/sched.c +17 -7

Index: tip/kernel/sched.c
===================================================================
@@ -269,6 +269,13 @@ struct cfs_bandwidth {
 #endif
 };
 
+enum runtime_state {
+	RUNTIME_UNLIMITED,
+	RUNTIME_AVAILABLE,
+	RUNTIME_THROTTLING,
+	RUNTIME_THROTTLED
+};
+
 /* task group related information */
 struct task_group {
 	struct cgroup_subsys_state css;

@@ -402,12 +409,12 @@ struct cfs_rq {
 	unsigned long load_contribution;
 #endif
 #ifdef CONFIG_CFS_BANDWIDTH
-	int runtime_enabled;
+	enum runtime_state runtime_state;
 	u64 runtime_expires;
 	s64 runtime_remaining;
 
 	u64 throttled_timestamp;
-	int throttled, throttle_count;
+	int throttle_count;
 	struct list_head throttled_list;
 #endif
 #endif

@@ -470,7 +477,7 @@ static void init_cfs_bandwidth(struct cf
 
 static void init_cfs_rq_runtime(struct cfs_rq *cfs_rq)
 {
-	cfs_rq->runtime_enabled = 0;
+	cfs_rq->runtime_state = RUNTIME_UNLIMITED;
 	INIT_LIST_HEAD(&cfs_rq->throttled_list);
 }

@@ -6368,7 +6375,7 @@ static void unthrottle_offline_cfs_rqs(s
 	for_each_leaf_cfs_rq(rq, cfs_rq) {
 		struct cfs_bandwidth *cfs_b = tg_cfs_bandwidth(cfs_rq->tg);
 
-		if (!cfs_rq->runtime_enabled)
+		if (!cfs_rq_runtime_enabled(cfs_rq))
 			continue;
 
 		/*

@@ -9263,11 +9270,14 @@ static int tg_set_cfs_bandwidth(struct t
 		struct rq *rq = rq_of(cfs_rq);
 
 		raw_spin_lock_irq(&rq->lock);
-		cfs_rq->runtime_enabled = runtime_enabled;
-		cfs_rq->runtime_remaining = 0;
-
 		if (cfs_rq_throttled(cfs_rq))
 			unthrottle_cfs_rq(cfs_rq);
+
+		if (runtime_enabled)
+			cfs_rq->runtime_state = RUNTIME_AVAILABLE;
+		else
+			cfs_rq->runtime_state = RUNTIME_UNLIMITED;
+		cfs_rq->runtime_remaining = 0;
 		raw_spin_unlock_irq(&rq->lock);
 	}
 out_unlock:

kernel/sched_fair.c +70 ~~-31~~

180 lines not on this page · raw message

Paul Turner

author

2011-11-10 02:30 UTC #11 lore raw

Re: [patch 3/3] From: Ben Segall <[email protected]>

In reply to Paul Turner

I mangled the subject/from headers on this one, fixed should be below.

Thanks,

- Paul
---
sched: update task accounting on throttle so that idle_balance() will trigger
From: Ben Segall <[email protected]>

Since throttling occurs in the put_prev_task() path we do not get to observe this delta against nr_running when making the decision to idle_balance().

This allows schedule() to call idle_balance when we go idle due to throttling.

Signed-off-by Ben Segall <[email protected]>

Signed-off-by Paul Turner <[email protected]>

---
 kernel/sched.c      |   24 ++++++++----
 kernel/sched_fair.c |  101 ++++++++++++++++++++++++++++++++++++----------------
 2 files changed, 87 insertions(+), 38 deletions(-)

kernel/sched.c +17 -7

Index: tip/kernel/sched.c
===================================================================
@@ -269,6 +269,13 @@ struct cfs_bandwidth {
 #endif
 };
 
+enum runtime_state {
+	RUNTIME_UNLIMITED,
+	RUNTIME_AVAILABLE,
+	RUNTIME_THROTTLING,
+	RUNTIME_THROTTLED
+};
+
 /* task group related information */
 struct task_group {
 	struct cgroup_subsys_state css;

@@ -402,12 +409,12 @@ struct cfs_rq {
 	unsigned long load_contribution;
 #endif
 #ifdef CONFIG_CFS_BANDWIDTH
-	int runtime_enabled;
+	enum runtime_state runtime_state;
 	u64 runtime_expires;
 	s64 runtime_remaining;
 
 	u64 throttled_timestamp;
-	int throttled, throttle_count;
+	int throttle_count;
 	struct list_head throttled_list;
 #endif
 #endif

@@ -470,7 +477,7 @@ static void init_cfs_bandwidth(struct cf
 
 static void init_cfs_rq_runtime(struct cfs_rq *cfs_rq)
 {
-	cfs_rq->runtime_enabled = 0;
+	cfs_rq->runtime_state = RUNTIME_UNLIMITED;
 	INIT_LIST_HEAD(&cfs_rq->throttled_list);
 }

@@ -6368,7 +6375,7 @@ static void unthrottle_offline_cfs_rqs(s
 	for_each_leaf_cfs_rq(rq, cfs_rq) {
 		struct cfs_bandwidth *cfs_b = tg_cfs_bandwidth(cfs_rq->tg);
 
-		if (!cfs_rq->runtime_enabled)
+		if (!cfs_rq_runtime_enabled(cfs_rq))
 			continue;
 
 		/*

@@ -9263,11 +9270,14 @@ static int tg_set_cfs_bandwidth(struct t
 		struct rq *rq = rq_of(cfs_rq);
 
 		raw_spin_lock_irq(&rq->lock);
-		cfs_rq->runtime_enabled = runtime_enabled;
-		cfs_rq->runtime_remaining = 0;
-
 		if (cfs_rq_throttled(cfs_rq))
 			unthrottle_cfs_rq(cfs_rq);
+
+		if (runtime_enabled)
+			cfs_rq->runtime_state = RUNTIME_AVAILABLE;
+		else
+			cfs_rq->runtime_state = RUNTIME_UNLIMITED;
+		cfs_rq->runtime_remaining = 0;
 		raw_spin_unlock_irq(&rq->lock);
 	}
 out_unlock:

kernel/sched_fair.c +70 ~~-31~~

180 lines not on this page · raw message

Kamalesh Babulal

Tested-by

2011-11-14 10:25 UTC #12 lore raw

Re: [patch 3/3] From: Ben Segall <[email protected]>

[snip]

Quoted 10 lines

Since throttling occurs in the put_prev_task() path we do not get to observe this delta against nr_running when making the decision to idle_balance().
Fix this by first enumerating cfs_rq throttle states so that we can distinguish throttling cfs_rqs. Then remove tasks that will be throttled in put_prev_task from rq->nr_running/cfs_rq->h_nr_running when in account_cfs_rq_runtime, rather than delaying until put_prev_task.
This allows schedule() to call idle_balance when we go idle due to throttling.

Quoted 8 lines

Using Kamalesh's nested-cgroup test case[1] we see the following improvement on a 16 core system:
baseline: Average CPU Idle percentage 13.9667%
+patch: Average CPU Idle percentage 3.53333%
[1]: https://lkml.org/lkml/2011/9/15/261
Signed-off-by Ben Segall <[email protected]>
Signed-off-by Paul Turner <[email protected]>

Tested-by Kamalesh Babulal <[email protected]>

Thanks for the patch. I tested patches on the same test environment, over which the cpu idle time was reported first at https://lkml.org/lkml/2011/6/7/352. In brief, tests were run on 2 socket quad core machine with three level of nested cgroups hierarchy and five cgroups created below the third level. Each of the five cgroups, having 2,2,4,8,16 while1 or cpu-matrix (https://lkml.org/lkml/2011/11/4/107)
tasks attached to them respectively.

[1] CFS Bandwith tweaks, were the patches posted by Paul Turner (https://lkml.org/lkml/2011/11/7/603)
[2] nohz idle balance RFC patch by Srivatsa Vaddagiri (https://lkml.org/lkml/2011/11/2/117)

While running the cpu-matrix benchmark with the patches, there was an improvement around ~50 to 55% and additional ~3% benefit in idle time with nohz idle balance patch. With while1 loop the improvment was around ~36 to 40% over tip and an additional benefit of ~4 to 5% was seen with nohz idle balance patch.

(1) cpu-matrix benchmark with nohz=on

    ----------------------------------

Run Base (tip) tip + CFS Bandwith tweaks tip + CFS Bandwith tweaks + nohz idle patch
--------------------------------------------------------------------------------------------------------------------------------------------------------------------------
1 Average CPU Idle percentage 4.1% Average CPU Idle percentage 2.36667% Average CPU Idle percentage 2.23333%
Bandwidth shared with remaining non-Idle 95.9% Bandwidth shared with remaining non-Idle 97.63333% Bandwidth shared with remaining non-Idle 97.76667%

2 Average CPU Idle percentage 4.23% Average CPU Idle percentage 2.3% Average CPU Idle percentage 2.16667%
Bandwidth shared with remaining non-Idle 95.77% Bandwidth shared with remaining non-Idle 97.7% Bandwidth shared with remaining non-Idle 97.83333%

(2) cpu-matrix benchmark with nohz=off

    -----------------------------------

Run Base (tip) tip + CFS Bandwith tweaks tip + CFS Bandwith tweaks + nohz idle patch
--------------------------------------------------------------------------------------------------------------------------------------------------------------------------
1 Average CPU Idle percentage 4.53333% Average CPU Idle percentage 2.43333% Average CPU Idle percentage 2.36667%
Bandwidth shared with remaining non-Idle 95.46667% Bandwidth shared with remaining non-Idle 97.56667% Bandwidth shared with remaining non-Idle 97.63333%

2 Average CPU Idle percentage 4.4% Average CPU Idle percentage 2.36667% Average CPU Idle percentage 2.4%
Bandwidth shared with remaining non-Idle 95.6% Bandwidth shared with remaining non-Idle 97.63333% Bandwidth shared with remaining non-Idle 97.6%

(3) while1 loop with nohz=on

    -------------------------

Run Base (tip) tip + CFS Bandwith tweaks tip + CFS Bandwith tweaks + nohz idle patch
--------------------------------------------------------------------------------------------------------------------------------------------------------------------------
1 Average CPU Idle percentage 6.26667% Average CPU Idle percentage 2.5% Average CPU Idle percentage 2.23333%
Bandwidth shared with remaining non-Idle 93.73333% Bandwidth shared with remaining non-Idle 97.5% Bandwidth shared with remaining non-Idle 97.76667%

2 Average CPU Idle percentage 6.73333% Average CPU Idle percentage 2.46667% Average CPU Idle percentage 2.13333%
Bandwidth shared with remaining non-Idle 93.26667% Bandwidth shared with remaining non-Idle 97.53333% Bandwidth shared with remaining non-Idle 97.86667%

(4) while1 loop with nohz=off

    --------------------------

Run Base (tip) tip + CFS Bandwith tweaks tip + CFS Bandwith tweaks + nohz idle patch
--------------------------------------------------------------------------------------------------------------------------------------------------------------------------
1 Average CPU Idle percentage 3.6% Average CPU Idle percentage 2.4% Average CPU Idle percentage 2.43333%
Bandwidth shared with remaining non-Idle 96.4% Bandwidth shared with remaining non-Idle 97.6% Bandwidth shared with remaining non-Idle 97.56667%

2 Average CPU Idle percentage 3.46667% Average CPU Idle percentage 2.33333% Average CPU Idle percentage 2.4%
Bandwidth shared with remaining non-Idle 96.53333% Bandwidth shared with remaining non-Idle 97.66667% Bandwidth shared with remaining non-Idle 97.6%

each cpu-matrix benchmark task was run as # perf sched cpu-matrix -s1k -i 1000 -p100

Kamalesh.

Peter Zijlstra

2011-11-14 12:02 UTC #13 lore raw

Re: [patch 3/3] From: Ben Segall <[email protected]>

In reply to Paul Turner

Quoted 14 lines · Paul Turner

sched: update task accounting on throttle so that idle_balance() will trigger
From: Ben Segall <[email protected]>
Since throttling occurs in the put_prev_task() path we do not get to observe this delta against nr_running when making the decision to idle_balance().
Fix this by first enumerating cfs_rq throttle states so that we can distinguish throttling cfs_rqs. Then remove tasks that will be throttled in put_prev_task from rq->nr_running/cfs_rq->h_nr_running when in account_cfs_rq_runtime, rather than delaying until put_prev_task.
This allows schedule() to call idle_balance when we go idle due to throttling.

Quoted 8 lines

Using Kamalesh's nested-cgroup test case[1] we see the following improvement on a 16 core system:
baseline: Average CPU Idle percentage 13.9667%
+patch: Average CPU Idle percentage 3.53333%
[1]: https://lkml.org/lkml/2011/9/15/261
Signed-off-by Ben Segall <[email protected]>
Signed-off-by Paul Turner <[email protected]>

I really don't like this patch... There's something wrong about decoupling the dequeue from nr_running accounting.

That said, I haven't got a bright idea either.. anyway, I think the patch is somewhat too big for 3.2 at this point.

Quoted 10 lines

---
  kernel/sched.c      |   24 ++++++++----
  kernel/sched_fair.c |  101 ++++++++++++++++++++++++++++++++++++----------------
  2 files changed, 87 insertions(+), 38 deletions(-)
Index: tip/kernel/sched.c
===================================================================

kernel/sched.c struct cfs_bandwidth { · line 277

Quoted 9 lines

kernel/sched.c +6 -0

@@ -269,6 +269,13 @@ struct cfs_bandwidth {
  #endif
  };
 
+enum runtime_state {
+       RUNTIME_UNLIMITED,
+       RUNTIME_AVAILABLE,
+       RUNTIME_THROTTLING,
+       RUNTIME_THROTTLED
+};

What's the difference between throttling and throttled? Throttling is between actually getting throttled and put_prev_task() getting called? This all wants a comment.

Quoted 10 lines

kernel/sched.c +10 -0

+static void account_nr_throttling(struct cfs_rq *cfs_rq, long nr_throttling)
+{
+       struct sched_entity *se;
+
+       se = cfs_rq->tg->se[cpu_of(rq_of(cfs_rq))];
+
+       for_each_sched_entity(se) {
+               struct cfs_rq *qcfs_rq = cfs_rq_of(se);
+               if (!se->on_rq)
+                       break;

kernel/sched.c struct cfs_bandwidth {

Quoted 10 lines

kernel/sched.c +10 -0

+
+               qcfs_rq->h_nr_running -= nr_throttling;
+
+               if (qcfs_rq->runtime_state == RUNTIME_THROTTLING)
+                       break;
+       }
+
+       if (!se)
+               rq_of(cfs_rq)->nr_running -= nr_throttling;
+}

Since you'll end up calling this stuff with a negative nr_throttling, please use += to avoid the double negative brain twist.

Quoted 5 lines

static void __account_cfs_rq_runtime(struct cfs_rq *cfs_rq,
unsigned long delta_exec)
{
kernel/sched.c +0 -0
@@ -1401,14 +1422,33 @@ static void __account_cfs_rq_runtime(str
         * if we're unable to extend our runtime we resched so that the active

kernel/sched.c static void __account_cfs_rq_runtime(str · line 1430

Quoted 10 lines

kernel/sched.c +6 -2

         * hierarchy can be throttled
         */
-       if (!assign_cfs_rq_runtime(cfs_rq) && likely(cfs_rq->curr))
-               resched_task(rq_of(cfs_rq)->curr);
+       if (assign_cfs_rq_runtime(cfs_rq))
+               return;
+
+       if (unlikely(!cfs_rq->curr) || throttled_hierarchy(cfs_rq) ||
+          cfs_rq->runtime_state == RUNTIME_THROTTLING)
+               return;

How exactly can we get here if we're throttling already?

Quoted 21 lines

kernel/sched.c +12 -1

+       resched_task(rq_of(cfs_rq)->curr);
+
+       /*
+       * Remove us from nr_running/h_nr_running so
+       * that idle_balance gets called if necessary
+       */
+       account_nr_throttling(cfs_rq, cfs_rq->h_nr_running);
+       cfs_rq->runtime_state = RUNTIME_THROTTLING;
+}

@@ -1416,7 +1456,9 @@ static __always_inline void account_cfs_
 
  static inline int cfs_rq_throttled(struct cfs_rq *cfs_rq)
  {
-       return cfs_bandwidth_used() && cfs_rq->throttled;
+       return cfs_bandwidth_used() &&
+               (cfs_rq->runtime_state == RUNTIME_THROTTLED ||
+                cfs_rq->runtime_state == RUNTIME_THROTTLING);
  }

= THROTTLING saves a test.

Benjamin Segall

2011-11-15 21:14 UTC #14 lore raw

Re: [patch 3/3] From: Ben Segall <[email protected]>

Quoted 21 lines · Peter Zijlstra

Quoted 20 lines · Paul Turner
sched: update task accounting on throttle so that idle_balance() will trigger
From: Ben Segall <[email protected]>
Since throttling occurs in the put_prev_task() path we do not get to observe this delta against nr_running when making the decision to idle_balance().
Fix this by first enumerating cfs_rq throttle states so that we can distinguish throttling cfs_rqs. Then remove tasks that will be throttled in put_prev_task from rq->nr_running/cfs_rq->h_nr_running when in account_cfs_rq_runtime, rather than delaying until put_prev_task.
This allows schedule() to call idle_balance when we go idle due to throttling.
Using Kamalesh's nested-cgroup test case[1] we see the following improvement on a 16 core system:
baseline: Average CPU Idle percentage 13.9667%
+patch: Average CPU Idle percentage 3.53333%
[1]: https://lkml.org/lkml/2011/9/15/261

Quoted 8 lines

Quoted 2 lines
Signed-off-by Ben Segall <[email protected]>
Signed-off-by Paul Turner <[email protected]>
I really don't like this patch... There's something wrong about decoupling the dequeue from nr_running accounting.
That said, I haven't got a bright idea either.. anyway, I think the patch is somewhat too big for 3.2 at this point.

Since we can't really throttle until schedule or so, the simplest solution would be to move it from put_prev_task to a prev_schedule hook so that it could be before idle_balance, but that seems a bit heavy just for cfs bandwidth.

Quoted 14 lines

Quoted 14 lines
---
  kernel/sched.c      |   24 ++++++++----
  kernel/sched_fair.c |  101 ++++++++++++++++++++++++++++++++++++----------------
  2 files changed, 87 insertions(+), 38 deletions(-)
Index: tip/kernel/sched.c
===================================================================
kernel/sched.c +0 -0
@@ -269,6 +269,13 @@ struct cfs_bandwidth {
  #endif
  };
 

Quoted 10 lines

kernel/sched.c struct cfs_bandwidth { · line 277
Quoted 6 lines
kernel/sched.c +6 -0
+enum runtime_state {
+       RUNTIME_UNLIMITED,
+       RUNTIME_AVAILABLE,
+       RUNTIME_THROTTLING,
+       RUNTIME_THROTTLED
+};
What's the difference between throttling and throttled? Throttling is between actually getting throttled and put_prev_task() getting called? This all wants a comment.

Yes, although THROTTLING->AVAILABLE (or even ->UNLIMITED) is also possible.

Quoted 6 lines

kernel/sched.c +0 -2

@@ -1401,14 +1422,33 @@ static void __account_cfs_rq_runtime(str
         * if we're unable to extend our runtime we resched so that the active
         * hierarchy can be throttled
         */
-       if (!assign_cfs_rq_runtime(cfs_rq) && likely(cfs_rq->curr))
-               resched_task(rq_of(cfs_rq)->curr);

Quoted 8 lines

kernel/sched.c static void __account_cfs_rq_runtime(str · line 1430
Quoted 6 lines
kernel/sched.c +6 -0
+       if (assign_cfs_rq_runtime(cfs_rq))
+               return;
+
+       if (unlikely(!cfs_rq->curr) || throttled_hierarchy(cfs_rq) ||
+          cfs_rq->runtime_state == RUNTIME_THROTTLING)
+               return;
How exactly can we get here if we're throttling already?

A wakeup in the same to-be-throttled cfs_rq before need_resched is handled. The simplest trigger would be three tasks on the same cfs_rq, only one of which is running. If it tries to wake both of the other tasks just as it runs out of runtime, we would hit this.

And the patch updated for these and your other comments:

-- 8< --
From: Benjamin Segall <[email protected]>
Subject: sched: update task accounting on throttle so that idle_balance() will trigger

Since throttling occurs in the put_prev_task() path we do not get to observe this delta against nr_running when making the decision to idle_balance().

This allows schedule() to call idle_balance when we go idle due to throttling.

Signed-off-by Ben Segall <[email protected]>

Signed-off-by Paul Turner <[email protected]>

---
 kernel/sched.c      |   28 +++++++++++---
 kernel/sched_fair.c |  100 +++++++++++++++++++++++++++++++++++----------------
 2 files changed, 90 insertions(+), 38 deletions(-)

kernel/sched.c +21 -7

index 7c1b2f5..0af1680 100644
@@ -269,6 +269,17 @@ struct cfs_bandwidth {
 #endif
 };
 
+/*
+ * THROTTLING tasks have been removed from nr_running, but have not
+ * yet been dequeued. THROTTLED tasks have been entirely dequeued.
+ */
+enum runtime_state {
+	RUNTIME_UNLIMITED,
+	RUNTIME_AVAILABLE,
+	RUNTIME_THROTTLING,
+	RUNTIME_THROTTLED
+};
+
 /* task group related information */
 struct task_group {
 	struct cgroup_subsys_state css;

@@ -402,12 +413,12 @@ struct cfs_rq {
 	unsigned long load_contribution;
 #endif
 #ifdef CONFIG_CFS_BANDWIDTH
-	int runtime_enabled;
+	enum runtime_state runtime_state;
 	u64 runtime_expires;
 	s64 runtime_remaining;
 
 	u64 throttled_timestamp;
-	int throttled, throttle_count;
+	int throttle_count;
 	struct list_head throttled_list;
 #endif
 #endif

@@ -470,7 +481,7 @@ static void init_cfs_bandwidth(struct cfs_bandwidth *cfs_b)
 
 static void init_cfs_rq_runtime(struct cfs_rq *cfs_rq)
 {
-	cfs_rq->runtime_enabled = 0;
+	cfs_rq->runtime_state = RUNTIME_UNLIMITED;
 	INIT_LIST_HEAD(&cfs_rq->throttled_list);
 }

@@ -6368,7 +6379,7 @@ static void unthrottle_offline_cfs_rqs(struct rq *rq)
 	for_each_leaf_cfs_rq(rq, cfs_rq) {
 		struct cfs_bandwidth *cfs_b = tg_cfs_bandwidth(cfs_rq->tg);
 
-		if (!cfs_rq->runtime_enabled)
+		if (!cfs_rq_runtime_enabled(cfs_rq))
 			continue;
 
 		/*

@@ -9263,11 +9274,14 @@ static int tg_set_cfs_bandwidth(struct task_group *tg, u64 period, u64 quota)
 		struct rq *rq = rq_of(cfs_rq);
 
 		raw_spin_lock_irq(&rq->lock);
-		cfs_rq->runtime_enabled = runtime_enabled;
-		cfs_rq->runtime_remaining = 0;
-
 		if (cfs_rq_throttled(cfs_rq))
 			unthrottle_cfs_rq(cfs_rq);
+
+		if (runtime_enabled)
+			cfs_rq->runtime_state = RUNTIME_AVAILABLE;
+		else
+			cfs_rq->runtime_state = RUNTIME_UNLIMITED;
+		cfs_rq->runtime_remaining = 0;
 		raw_spin_unlock_irq(&rq->lock);
 	}
 out_unlock:

kernel/sched_fair.c +69 ~~-31~~

179 lines not on this page · raw message