Skip to contentSkip to conversation

CFS Bandwidth Control

PATCH In review Bharata B Rao 8 participants 51 messages Oct 12, 2010 – Dec 7, 2010

Subsystems (2)
lore
Share & tools
lore
#0 lore raw

v3 cover CFS Bandwidth Control

Hi,

Its been a while since we posted CPS hard limits (aka CFS bandwidth control now) patches, hence a quick recap first:

- I have been working on CFS hard limits since last year and have posted a few versions of the same (last post: http://lkml.org/lkml/2010/1/5/44)
- Paul Turner and Nikhil Rao meanwhile started working on CFS bandwidth control and have posted a couple of versions.
(last post v2: http://lwn.net/Articles/385055/)

Paul's approach mainly changed the way the CPU hard limit was represented. After his post, I decided to work with them and discontinue my patch series since their global bandwidth specification for group appears more flexible than the RT-type per-cpu bandwidth specification I had in my series.

Since Paul seems to be busy, I am taking the freedom of posting the next version of his patches with a few enhancements to the slack time handling. (more on this later)

Main changes in this post:

- Return the unused and remaining local quota at each CPU to the global runtime pool.
- A few fixes:
- Explicitly wake up the idle cpu during unthrottle.
- Optimally handle throttling of current task within enqueue_task.
- Fix compilation break with CONFIG_PREEMPT on.
- Fix a compilation break at intermediate patch level.
- Applies on 2.6.36-rc7.

More about slack time issue
---------------------------
Bandwidth available to a group is specified by two parameters: cpu.cfs_quota_us and cpu.cfs_period_us. cpu.cfs_quota_us is the max CPU time a group can consume within the time period of cpu.cfs_period_us. The quota available to a group within a period is maintained in a per-group global pool. In each CPU, the consumption happens by obtaining a slice of this global pool.

If the local quota (obtained as slices of global pool) isn't fully consumed within a given period, a group can potentially get more CPU time than its allowed for in the next interval. This is due to the slack time that may be left over from the previous interval. More details about how this is fixed is present in the description part of patch 7/7. Here I will only show the benefit of handling the slack time correctly through this experiment:

On a 16 CPU system, two different kinds of tasks were run as part of a group which had quota/bandwidth as 500000/500000 [=> 500ms/500ms], which means that the group was capped at 1CPU worth of time every period.

Type A task: Complete CPU hog.
Type B task: Sleeps for 500ms and runs as CPU hog for next 500ms. And this cycle
repeats.

1 task of type A and 15 tasks of type B were run for 20s, each bound to a different CPU. At the end of 20s, the CPU time obtained by each of them looked like this:

-----------------------------------------------------------------------
Without returning Returning slack time
slack time to global to global pool
pool (with patch 7/7)
-----------------------------------------------------------------------
1 type A task 7.96s 10.71s
15 type B tasks 12.36s 9.79s
-----------------------------------------------------------------------

This shows the effects of slack time and the benefit of handling it correctly.

I request the scheduler maintainers and others for comments on these patches.

Regards,
Bharata.

#1 lore raw

PATCH v3 1/7 sched: introduce primitives to account for CFS bandwidth tracking

sched: introduce primitives to account for CFS bandwidth tracking

From: Paul Turner <[email protected]>

In this patch we introduce the notion of CFS bandwidth, to account for the realities of SMP this is partitioned into globally unassigned bandwidth, and locally claimed bandwidth:
- The global bandwidth is per task_group, it represents a pool of unclaimed bandwidth that cfs_rq's can allocate from. It uses the new cfs_bandwidth structure.
- The local bandwidth is tracked per-cfs_rq, this represents allotments from the global pool
bandwidth assigned to a task_group, this is tracked using the new cfs_bandwidth structure.

Bandwidth is managed via cgroupfs via two new files in the cpu subsystem:
- cpu.cfs_period_us : the bandwidth period in usecs
- cpu.cfs_quota_us : the cpu bandwidth (in usecs) that this tg will be allowed to consume over period above.

A per-cfs_bandwidth timer is also introduced to handle future refresh at period expiration. There's some minor refactoring here so that start_bandwidth_timer() functionality can be shared

---
 init/Kconfig        |    9 +
 kernel/sched.c      |  271 +++++++++++++++++++++++++++++++++++++++++++++++-----
 kernel/sched_fair.c |   10 +
 3 files changed, 268 insertions(+), 22 deletions(-)
init/Kconfig +9 -0
@@ -609,6 +609,15 @@ config FAIR_GROUP_SCHED
 	depends on CGROUP_SCHED
 	default CGROUP_SCHED
 
+config CFS_BANDWIDTH
+	bool "CPU bandwidth provisioning for FAIR_GROUP_SCHED"
+	depends on EXPERIMENTAL
+	depends on FAIR_GROUP_SCHED
+	default n
+	help
+	  This option allows users to define quota and period for cpu
+	  bandwidth provisioning on a per-cgroup basis.
+
 config RT_GROUP_SCHED
 	bool "Group scheduling for SCHED_RR/FIFO"
 	depends on EXPERIMENTAL
kernel/sched.c +249 -22

366 lines not on this page · raw message

kernel/sched_fair.c +10 -0
@@ -360,6 +360,9 @@ static void __enqueue_entity(struct cfs_
 
 	rb_link_node(&se->run_node, parent, link);
 	rb_insert_color(&se->run_node, &cfs_rq->tasks_timeline);
+#ifdef CONFIG_CFS_BANDWIDTH
+	start_cfs_bandwidth(&cfs_rq->tg->cfs_bandwidth);
+#endif
 }
 
 static void __dequeue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se)
@@ -1126,6 +1129,13 @@ static void yield_task_fair(struct rq *r
 	se->vruntime = rightmost->vruntime + 1;
 }
 
+#ifdef CONFIG_CFS_BANDWIDTH
+static int do_sched_cfs_period_timer(struct cfs_bandwidth *cfs_b, int overrun)
+{
+	return 1;
+}
+#endif
+
 #ifdef CONFIG_SMP
 
 static void task_waking_fair(struct rq *rq, struct task_struct *p)
#8 lore raw

PATCH v3 2/7 sched: accumulate per-cfs_rq cpu usage

In reply to Bharata B Rao

sched: accumulate per-cfs_rq cpu usage

From: Paul Turner <[email protected]>

Introduce account_cfs_rq_quota() to account bandwidth usage on the cfs_rq level versus task_groups for which bandwidth has been assigned. This is tracked by whether the local cfs_rq->quota_assigned is finite or infinite (RUNTIME_INF).

For cfs_rq's that belong to a bandwidth constrained task_group we introduce tg_request_cfs_quota() which attempts to allocate quota from the global pool for use locally. Updates involving the global pool are currently protected under cfs_bandwidth->lock, local pools are protected by rq->lock.

This patch only attempts to assign and track quota, no action is taken in the case that cfs_rq->quota_used exceeds cfs_rq->quota_assigned.

---
 include/linux/sched.h |    4 ++++
 kernel/sched.c        |   13 +++++++++++++
 kernel/sched_fair.c   |   50 ++++++++++++++++++++++++++++++++++++++++++++++++++
 kernel/sysctl.c       |   10 ++++++++++
 4 files changed, 77 insertions(+)
include/linux/sched.h +4 -0
@@ -1898,6 +1898,10 @@ int sched_rt_handler(struct ctl_table *t
 		void __user *buffer, size_t *lenp,
 		loff_t *ppos);
 
+#ifdef CONFIG_CFS_BANDWIDTH
+extern unsigned int sysctl_sched_cfs_bandwidth_slice;
+#endif
+
 extern unsigned int sysctl_sched_compat_yield;
 
 #ifdef CONFIG_RT_MUTEXES
kernel/sched.c +13 -0
@@ -1929,6 +1929,19 @@ static const struct sched_class rt_sched
  * default: 0.5s
  */
 static u64 sched_cfs_bandwidth_period = 500000000ULL;
+
+/*
+ * default slice of quota to allocate from global tg to local cfs_rq pool on
+ * each refresh
+ * default: 10ms
+ */
+unsigned int sysctl_sched_cfs_bandwidth_slice = 10000UL;
+
+static inline u64 sched_cfs_bandwidth_slice(void)
+{
+	return (u64)sysctl_sched_cfs_bandwidth_slice * NSEC_PER_USEC;
+}
+
 #endif
 
 #define sched_class_highest (&rt_sched_class)
kernel/sched_fair.c +50 -0

68 lines not on this page · raw message

kernel/sysctl.c +10 -0
@@ -384,6 +384,16 @@ static struct ctl_table kern_table[] = {
 		.mode		= 0644,
 		.proc_handler	= proc_dointvec,
 	},
+#ifdef CONFIG_CFS_BANDWIDTH
+	{
+		.procname	= "sched_cfs_bandwidth_slice_us",
+		.data		= &sysctl_sched_cfs_bandwidth_slice,
+		.maxlen		= sizeof(unsigned int),
+		.mode		= 0644,
+		.proc_handler	= proc_dointvec_minmax,
+		.extra1		= &one,
+	},
+#endif
 #ifdef CONFIG_PROVE_LOCKING
 	{
 		.procname	= "prove_locking",
#24 lore raw

PATCH v3 3/7 sched: throttle cfs_rq entities which exceed their local quota

In reply to Bharata B Rao

sched: throttle cfs_rq entities which exceed their local quota

From: Paul Turner <[email protected]>

In account_cfs_rq_quota() (via update_curr()) we track consumption versus a cfs_rq's local quota and whether there is global quota available to continue enabling it in the event we run out.

This patch adds the required support for the latter case, throttling entities until quota is available to run. Throttling dequeues the entity in question and sends a reschedule to the owning cpu so that it can be evicted.

The following restrictions apply to a throttled cfs_rq:
- It is dequeued from sched_entity hierarchy and restricted from being re-enqueued. This means that new/waking children of this entity will be queued up to it, but not past it.
- It does not contribute to weight calculations in tg_shares_up
- In the case that the cfs_rq of the cpu we are trying to pull from is throttled it is is ignored by the loadbalancer in __load_balance_fair() and move_one_task_fair().

---
 kernel/sched.c      |   12 ++++++++
 kernel/sched_fair.c |   70 ++++++++++++++++++++++++++++++++++++++++++++++++----
 2 files changed, 76 insertions(+), 6 deletions(-)
kernel/sched.c +11 -1
@@ -387,6 +387,7 @@ struct cfs_rq {
 #endif
 #ifdef CONFIG_CFS_BANDWIDTH
 	u64 quota_assigned, quota_used;
+	int throttled;
 #endif
 #endif
 };
@@ -1668,6 +1669,8 @@ static void update_group_shares_cpu(stru
 	}
 }
 
+static inline int cfs_rq_throttled(struct cfs_rq *cfs_rq);
+
 /*
  * Re-compute the task group their per cpu shares over the given domain.
  * This needs to be done in a bottom-up fashion because the rq weight of a
@@ -1688,7 +1691,14 @@ static int tg_shares_up(struct task_grou
 	usd_rq_weight = per_cpu_ptr(update_shares_data, smp_processor_id());
 
 	for_each_cpu(i, sched_domain_span(sd)) {
-		weight = tg->cfs_rq[i]->load.weight;
+		/*
+		 * bandwidth throttled entities cannot contribute to load
+		 * balance
+		 */
+		if (!cfs_rq_throttled(tg->cfs_rq[i]))
+			weight = tg->cfs_rq[i]->load.weight;
+		else
+			weight = 0;
 		usd_rq_weight[i] = weight;
 
 		rq_weight += weight;
kernel/sched_fair.c +65 -5

124 lines not on this page · raw message

#40 lore raw

PATCH v3 4/7 sched: unthrottle cfs_rq(s) who ran out of quota at period refresh

In reply to Bharata B Rao

sched: unthrottle cfs_rq(s) who ran out of quota at period refresh

From: Paul Turner <[email protected]>

At the start of a new period there are several actions we must take:
- Refresh global bandwidth pool
- Unthrottle entities who ran out of quota as refreshed bandwidth permits

Unthrottled entities have the cfs_rq->throttled flag set and are re-enqueued into the cfs entity hierarchy.

sched_rt_period_mask() is refactored slightly into sched_bw_period_mask() since it is now shared by both cfs and rt bandwidth period timers.

The !CONFIG_RT_GROUP_SCHED && CONFIG_SMP case has been collapsed to use rd->span instead of cpu_online_mask since I think that was incorrect before (don't want to hit cpu's outside of your root_domain for RT bandwidth).

---
 kernel/sched.c      |   16 ++++++++++++
 kernel/sched_fair.c |   68 +++++++++++++++++++++++++++++++++++++++++++++++++++-
 kernel/sched_rt.c   |   19 --------------
 3 files changed, 84 insertions(+), 19 deletions(-)
kernel/sched.c +16 -0
@@ -1565,6 +1565,8 @@ static int tg_nop(struct task_group *tg,
 }
 #endif
 
+static inline const struct cpumask *sched_bw_period_mask(void);
+
 #ifdef CONFIG_SMP
 /* Used instead of source_load when we know the type == 0 */
 static unsigned long weighted_cpuload(const int cpu)
@@ -1933,6 +1935,18 @@ static inline void __set_task_cpu(struct
 
 static const struct sched_class rt_sched_class;
 
+#ifdef CONFIG_SMP
+static inline const struct cpumask *sched_bw_period_mask(void)
+{
+	return cpu_rq(smp_processor_id())->rd->span;
+}
+#else
+static inline const struct cpumask *sched_bw_period_mask(void)
+{
+	return cpu_online_mask;
+}
+#endif
+
 #ifdef CONFIG_CFS_BANDWIDTH
 /*
  * default period for cfs group bandwidth.
@@ -8937,6 +8951,8 @@ static int tg_set_cfs_bandwidth(struct t
 
 		raw_spin_lock_irq(&rq->lock);
 		init_cfs_rq_quota(cfs_rq);
+		if (cfs_rq_throttled(cfs_rq))
+			unthrottle_cfs_rq(cfs_rq);
 		raw_spin_unlock_irq(&rq->lock);
 	}
 	mutex_unlock(&mutex);
kernel/sched_fair.c +67 -1

87 lines not on this page · raw message

kernel/sched_rt.c +1 -18
@@ -241,18 +241,6 @@ static int rt_se_boosted(struct sched_rt
 	return p->prio != p->normal_prio;
 }
 
-#ifdef CONFIG_SMP
-static inline const struct cpumask *sched_rt_period_mask(void)
-{
-	return cpu_rq(smp_processor_id())->rd->span;
-}
-#else
-static inline const struct cpumask *sched_rt_period_mask(void)
-{
-	return cpu_online_mask;
-}
-#endif
-
 static inline
 struct rt_rq *sched_rt_period_rt_rq(struct rt_bandwidth *rt_b, int cpu)
 {
@@ -302,11 +290,6 @@ static inline int rt_rq_throttled(struct
 	return rt_rq->rt_throttled;
 }
 
-static inline const struct cpumask *sched_rt_period_mask(void)
-{
-	return cpu_online_mask;
-}
-
 static inline
 struct rt_rq *sched_rt_period_rt_rq(struct rt_bandwidth *rt_b, int cpu)
 {
@@ -524,7 +507,7 @@ static int do_sched_rt_period_timer(stru
 	if (!rt_bandwidth_enabled() || rt_b->rt_runtime == RUNTIME_INF)
 		return 1;
 
-	span = sched_rt_period_mask();
+	span = sched_bw_period_mask();
 	for_each_cpu(i, span) {
 		int enqueue = 0;
 		struct rt_rq *rt_rq = sched_rt_period_rt_rq(rt_b, i);
#43 lore raw

PATCH v3 5/7 sched: add exports tracking cfs bandwidth control statistics

In reply to Bharata B Rao

sched: add exports tracking cfs bandwidth control statistics

From: Nikhil Rao <[email protected]>

This change introduces statistics exports for the cpu sub-system, these are added through the use of a stat file similar to that exported by other subsystems.

The following exports are included:

nr_periods: number of periods in which execution occurred
nr_throttled: the number of periods above in which execution was throttle
throttled_time: cumulative wall-time that any cpus have been throttled for
this group

---
 kernel/sched.c      |   26 ++++++++++++++++++++++++++
 kernel/sched_fair.c |   18 +++++++++++++++++-
 2 files changed, 43 insertions(+), 1 deletion(-)
kernel/sched.c +26 -0
@@ -252,6 +252,11 @@ struct cfs_bandwidth {
 	ktime_t			period;
 	u64			runtime, quota;
 	struct hrtimer		period_timer;
+
+	/* throttle statistics */
+	u64			nr_periods;
+	u64			nr_throttled;
+	u64			throttled_time;
 };
 #endif
 
@@ -388,6 +393,7 @@ struct cfs_rq {
 #ifdef CONFIG_CFS_BANDWIDTH
 	u64 quota_assigned, quota_used;
 	int throttled;
+	u64 throttled_timestamp;
 #endif
 #endif
 };
@@ -425,6 +431,10 @@ void init_cfs_bandwidth(struct cfs_bandw
 
 	hrtimer_init(&cfs_b->period_timer, CLOCK_MONOTONIC, HRTIMER_MODE_REL);
 	cfs_b->period_timer.function = sched_cfs_period_timer;
+
+	cfs_b->nr_periods = 0;
+	cfs_b->nr_throttled = 0;
+	cfs_b->throttled_time = 0;
 }
 
 static
@@ -9029,6 +9039,18 @@ static int cpu_cfs_period_write_u64(stru
 	return tg_set_cfs_period(cgroup_tg(cgrp), cfs_period_us);
 }
 
+static int cpu_stats_show(struct cgroup *cgrp, struct cftype *cft,
+		struct cgroup_map_cb *cb)
+{
+	struct task_group *tg = cgroup_tg(cgrp);
+	struct cfs_bandwidth *cfs_b = tg_cfs_bandwidth(tg);
+
+	cb->fill(cb, "nr_periods", cfs_b->nr_periods);
+	cb->fill(cb, "nr_throttled", cfs_b->nr_throttled);
+	cb->fill(cb, "throttled_time", cfs_b->throttled_time);
+
+	return 0;
+}
 #endif /* CONFIG_CFS_BANDWIDTH */
 #endif /* CONFIG_FAIR_GROUP_SCHED */
 
@@ -9075,6 +9097,10 @@ static struct cftype cpu_files[] = {
 		.read_u64 = cpu_cfs_period_read_u64,
 		.write_u64 = cpu_cfs_period_write_u64,
 	},
+	{
+		.name = "stat",
+		.read_map = cpu_stats_show,
+	},
 #endif
 #ifdef CONFIG_RT_GROUP_SCHED
 	{
kernel/sched_fair.c +17 -1
@@ -1224,16 +1224,26 @@ static void throttle_cfs_rq(struct cfs_r
 
 out_throttled:
 	cfs_rq->throttled = 1;
+	cfs_rq->throttled_timestamp = rq_of(cfs_rq)->clock;
 }
 
 static void unthrottle_cfs_rq(struct cfs_rq *cfs_rq)
 {
 	struct sched_entity *se;
 	struct rq *rq = rq_of(cfs_rq);
+	struct cfs_bandwidth *cfs_b = tg_cfs_bandwidth(cfs_rq->tg);
 
 	se = cfs_rq->tg->se[cpu_of(rq_of(cfs_rq))];
 
+	/* update stats */
+	update_rq_clock(rq);
+	raw_spin_lock(&cfs_b->lock);
+	cfs_b->throttled_time += (rq->clock - cfs_rq->throttled_timestamp);
+	raw_spin_unlock(&cfs_b->lock);
+
 	cfs_rq->throttled = 0;
+	cfs_rq->throttled_timestamp = 0;
+
 	for_each_sched_entity(se) {
 		if (se->on_rq)
 			break;
@@ -1271,7 +1281,7 @@ static void account_cfs_rq_quota(struct 
 
 static int do_sched_cfs_period_timer(struct cfs_bandwidth *cfs_b, int overrun)
 {
-	int i, idle = 1;
+	int i, idle = 1, num_throttled = 0;
 	u64 delta;
 	const struct cpumask *span;
 
@@ -1293,6 +1303,7 @@ static int do_sched_cfs_period_timer(str
 
 		if (!cfs_rq_throttled(cfs_rq))
 			continue;
+		num_throttled++;
 
 		delta = tg_request_cfs_quota(cfs_rq->tg);
 
@@ -1306,6 +1317,11 @@ static int do_sched_cfs_period_timer(str
 		}
 	}
 
+	/* update throttled stats */
+	cfs_b->nr_periods++;
+	if (num_throttled)
+		cfs_b->nr_throttled++;
+
 	return idle;
 }
 
#44 lore raw

PATCH v3 6/7 sched: hierarchical task accounting for FAIR_GROUP_SCHED

In reply to Bharata B Rao

sched: hierarchical task accounting for FAIR_GROUP_SCHED

From: Paul Turner <[email protected]>

With task entities participating in throttled sub-trees it is possible for task activation/de-activation to not lead to root visible changes to rq->nr_running. This in turn leads to incorrect idle and weight-per-task load balance decisions.

To allow correct accounting we move responsibility for updating rq->nr_running to the respective sched::classes. In the fair-group case this update is hierarchical, tracking the number of active tasks rooted at each group entity.

Note: technically this issue also exists with the existing sched_rt throttling; however due to the nearly complete provisioning of system resources for rt scheduling this is much less common by default.

---
 kernel/sched.c      |    9 ++++++---
 kernel/sched_fair.c |   42 ++++++++++++++++++++++++++++++++++++++++++
 kernel/sched_rt.c   |    5 ++++-
 3 files changed, 52 insertions(+), 4 deletions(-)
kernel/sched.c +6 -3
@@ -333,7 +333,7 @@ struct task_group init_task_group;
 /* CFS-related fields in a runqueue */
 struct cfs_rq {
 	struct load_weight load;
-	unsigned long nr_running;
+	unsigned long nr_running, h_nr_tasks;
 
 	u64 exec_clock;
 	u64 min_vruntime;
@@ -1984,6 +1984,11 @@ static inline u64 sched_cfs_bandwidth_sl
 
 #include "sched_stats.h"
 
+static void mod_nr_running(struct rq *rq, long delta)
+{
+	rq->nr_running += delta;
+}
+
 static void inc_nr_running(struct rq *rq)
 {
 	rq->nr_running++;
@@ -2040,7 +2045,6 @@ static void activate_task(struct rq *rq,
 		rq->nr_uninterruptible--;
 
 	enqueue_task(rq, p, flags);
-	inc_nr_running(rq);
 }
 
 /*
@@ -2052,7 +2056,6 @@ static void deactivate_task(struct rq *r
 		rq->nr_uninterruptible++;
 
 	dequeue_task(rq, p, flags);
-	dec_nr_running(rq);
 }
 
 #include "sched_idletask.c"
kernel/sched_fair.c +42 -0

84 lines not on this page · raw message

kernel/sched_rt.c +4 -1
@@ -882,6 +882,8 @@ enqueue_task_rt(struct rq *rq, struct ta
 
 	if (!task_current(rq, p) && p->rt.nr_cpus_allowed > 1)
 		enqueue_pushable_task(rq, p);
+
+	inc_nr_running(rq);
 }
 
 static void dequeue_task_rt(struct rq *rq, struct task_struct *p, int flags)
@@ -892,6 +894,8 @@ static void dequeue_task_rt(struct rq *r
 	dequeue_rt_entity(rt_se);
 
 	dequeue_pushable_task(rq, p);
+
+	dec_nr_running(rq);
 }
 
 /*
@@ -1754,4 +1758,3 @@ static void print_rt_stats(struct seq_fi
 	rcu_read_unlock();
 }
 #endif /* CONFIG_SCHED_DEBUG */
-
#45 lore raw

PATCH v3 7/7 sched: Return/expire slack quota using generation counters

In reply to Bharata B Rao
Quoted 1 line

From Paul Turner <[email protected]>

sched: Return/expire slack quota using generation counters

This patch adds generation counters to track and expire quotas.

This allows for two useful semantics:

1) On voluntary dequeue quota can be returned to the global pool provided it is still "current". In this patch we return all but one tick's worth of quota so that workloads with high rates of turn-over do not incur significant contention.

When returning quota to the global pool, if there are throttled runqueues and we have more than a slice of quota available, attempt to unthrottle them (again this is to prevent contention in the high turn over case).

2) On period expiration the generation counter is incremented, naturally expiring outstanding slack quota in the system.

A separate hrtimer is used to drive the slack quota redistribution and subsequent unthrottling of throttled entities.

---
 kernel/sched.c      |   54 +++++++++++++++++++++++--
 kernel/sched_fair.c |  111 ++++++++++++++++++++++++++++++++++++++++++++--------
 2 files changed, 146 insertions(+), 19 deletions(-)
kernel/sched.c +51 -3
@@ -250,8 +250,10 @@ static LIST_HEAD(task_groups);
 struct cfs_bandwidth {
 	raw_spinlock_t		lock;
 	ktime_t			period;
-	u64			runtime, quota;
+	u64			runtime, quota, generation;
+	int 			throttled_rqs;
 	struct hrtimer		period_timer;
+	struct hrtimer		slack_timer;
 
 	/* throttle statistics */
 	u64			nr_periods;
@@ -391,7 +393,7 @@ struct cfs_rq {
 	unsigned long rq_weight;
 #endif
 #ifdef CONFIG_CFS_BANDWIDTH
-	u64 quota_assigned, quota_used;
+	u64 quota_assigned, quota_used, quota_generation;
 	int throttled;
 	u64 throttled_timestamp;
 #endif
@@ -399,6 +401,17 @@ struct cfs_rq {
 };
 
 #ifdef CONFIG_CFS_BANDWIDTH
+
+static int do_sched_cfs_slack_timer(struct cfs_bandwidth *cfs_b);
+
+static enum hrtimer_restart sched_cfs_slack_timer(struct hrtimer *timer)
+{
+	struct cfs_bandwidth *cfs_b =
+		container_of(timer, struct cfs_bandwidth, slack_timer);
+	do_sched_cfs_slack_timer(cfs_b);
+	return HRTIMER_NORESTART;
+}
+
 static int do_sched_cfs_period_timer(struct cfs_bandwidth *cfs_b, int overrun);
 
 static enum hrtimer_restart sched_cfs_period_timer(struct hrtimer *timer)
@@ -428,9 +441,11 @@ void init_cfs_bandwidth(struct cfs_bandw
 	raw_spin_lock_init(&cfs_b->lock);
 	cfs_b->quota = cfs_b->runtime = quota;
 	cfs_b->period = ns_to_ktime(period);
-
+	cfs_b->generation = 0;
 	hrtimer_init(&cfs_b->period_timer, CLOCK_MONOTONIC, HRTIMER_MODE_REL);
 	cfs_b->period_timer.function = sched_cfs_period_timer;
+	hrtimer_init(&cfs_b->slack_timer, CLOCK_MONOTONIC, HRTIMER_MODE_REL);
+	cfs_b->slack_timer.function = sched_cfs_slack_timer;
 
 	cfs_b->nr_periods = 0;
 	cfs_b->nr_throttled = 0;
@@ -464,6 +479,35 @@ static void destroy_cfs_bandwidth(struct
 {
 	hrtimer_cancel(&cfs_b->period_timer);
 }
+
+
+/* Should this be a tunable ? */
+#define CFS_SLACK_PERIOD	2000000	/* 2ms */
+
+static void destroy_cfs_slack_bandwidth(struct cfs_bandwidth *cfs_b)
+{
+	hrtimer_cancel(&cfs_b->slack_timer);
+}
+
+static void start_cfs_slack_bandwidth(struct cfs_bandwidth *cfs_b)
+{
+	if (cfs_b->quota == RUNTIME_INF)
+		return;
+
+	if (hrtimer_active(&cfs_b->slack_timer))
+		return;
+
+	raw_spin_lock(&cfs_b->lock);
+
+	/*
+	 * TODO: Don't start the slack timer if the
+	 * period timer is about to fire.
+	 */
+	start_bandwidth_timer(&cfs_b->slack_timer,
+		ns_to_ktime(CFS_SLACK_PERIOD));
+	raw_spin_unlock(&cfs_b->lock);
+}
+
 #endif
 
 /* Real-Time classes' related field in a runqueue: */
@@ -8182,6 +8226,7 @@ static void free_fair_sched_group(struct
 
 #ifdef CONFIG_CFS_BANDWIDTH
 	destroy_cfs_bandwidth(&tg->cfs_bandwidth);
+	destroy_cfs_slack_bandwidth(&tg->cfs_bandwidth);
 #endif
 
 	for_each_possible_cpu(i) {
@@ -8936,6 +8981,7 @@ static u64 cpu_shares_read_u64(struct cg
 static int tg_set_cfs_bandwidth(struct task_group *tg, u64 period, u64 quota)
 {
 	int i;
+	u64 next_generation;
 	static DEFINE_MUTEX(mutex);
 
 	if (tg == &init_task_group)
@@ -8956,6 +9002,7 @@ static int tg_set_cfs_bandwidth(struct t
 	raw_spin_lock_irq(&tg->cfs_bandwidth.lock);
 	tg->cfs_bandwidth.period = ns_to_ktime(period);
 	tg->cfs_bandwidth.runtime = tg->cfs_bandwidth.quota = quota;
+	next_generation = ++tg->cfs_bandwidth.generation;
 	raw_spin_unlock_irq(&tg->cfs_bandwidth.lock);
 
 	for_each_possible_cpu(i) {
@@ -8964,6 +9011,7 @@ static int tg_set_cfs_bandwidth(struct t
 
 		raw_spin_lock_irq(&rq->lock);
 		init_cfs_rq_quota(cfs_rq);
+		cfs_rq->quota_generation = next_generation;
 		if (cfs_rq_throttled(cfs_rq))
 			unthrottle_cfs_rq(cfs_rq);
 		raw_spin_unlock_irq(&rq->lock);
kernel/sched_fair.c +95 -16

175 lines not on this page · raw message

#46 lore raw
In reply to Bharata B Rao
Quoted 11 lines · On Tue, 12 Oct 2010 13:19:10 +0530 Bharata B Rao <[email protected]>…

Hi,

Its been a while since we posted CPS hard limits (aka CFS bandwidth control now) patches, hence a quick recap first:

- I have been working on CFS hard limits since last year and have posted a few versions of the same (last post: http://lkml.org/lkml/2010/1/5/44)
- Paul Turner and Nikhil Rao meanwhile started working on CFS bandwidth control and have posted a couple of versions.
(last post v2: http://lwn.net/Articles/385055/)

Quoted 9 lines

Paul's approach mainly changed the way the CPU hard limit was represented. After his post, I decided to work with them and discontinue my patch series since their global bandwidth specification for group appears more flexible than the RT-type per-cpu bandwidth specification I had in my series.

Since Paul seems to be busy, I am taking the freedom of posting the next version of his patches with a few enhancements to the slack time handling. (more on this later)

Wow, thank you. I've been looking forward to see updates. I'll try this set.

Regards,
-Kame

#47 lore raw
In reply to Bharata B Rao
Quoted 3 lines · Bharata B Rao

Hi,

Its been a while since we posted CPS hard limits (aka CFS bandwidth

Indeed, will see that I can incorporate those in the next experimental Linux-VServer patch for testing ...

btw, is it planned to allow for hard limits which are temporarily disabled when the machine/cpu would be otherwise idle (i.e. running the idle thread) or as we solved it, can we artificially advance the time (for the hard limits) when idle so that contexts which have work to do can work without sacrificing the priorization or the actual limits?

best,
Herbert

PS: from a quick glance I take it that using large values for period and quota, while keeping the ratio the same allows for 'burst loads'?

Quoted 70 lines

control now) patches, hence a quick recap first:

- I have been working on CFS hard limits since last year and have posted a few versions of the same (last post: http://lkml.org/lkml/2010/1/5/44)
- Paul Turner and Nikhil Rao meanwhile started working on CFS bandwidth control and have posted a couple of versions.
(last post v2: http://lwn.net/Articles/385055/)

Paul's approach mainly changed the way the CPU hard limit was represented. After his post, I decided to work with them and discontinue my patch series since their global bandwidth specification for group appears more flexible than the RT-type per-cpu bandwidth specification I had in my series.

Since Paul seems to be busy, I am taking the freedom of posting the next version of his patches with a few enhancements to the slack time handling. (more on this later)

Main changes in this post:

- Return the unused and remaining local quota at each CPU to the global runtime pool.
- A few fixes:
- Explicitly wake up the idle cpu during unthrottle.
- Optimally handle throttling of current task within enqueue_task.
- Fix compilation break with CONFIG_PREEMPT on.
- Fix a compilation break at intermediate patch level.
- Applies on 2.6.36-rc7.

More about slack time issue
---------------------------
Bandwidth available to a group is specified by two parameters: cpu.cfs_quota_us and cpu.cfs_period_us. cpu.cfs_quota_us is the max CPU time a group can consume within the time period of cpu.cfs_period_us. The quota available to a group within a period is maintained in a per-group global pool. In each CPU, the consumption happens by obtaining a slice of this global pool.

If the local quota (obtained as slices of global pool) isn't fully consumed within a given period, a group can potentially get more CPU time than its allowed for in the next interval. This is due to the slack time that may be left over from the previous interval. More details about how this is fixed is present in the description part of patch 7/7. Here I will only show the benefit of handling the slack time correctly through this experiment:

On a 16 CPU system, two different kinds of tasks were run as part of a group which had quota/bandwidth as 500000/500000 [=> 500ms/500ms], which means that the group was capped at 1CPU worth of time every period.

Type A task: Complete CPU hog.
Type B task: Sleeps for 500ms and runs as CPU hog for next 500ms. And this cycle
repeats.

1 task of type A and 15 tasks of type B were run for 20s, each bound to a different CPU. At the end of 20s, the CPU time obtained by each of them looked like this:

-----------------------------------------------------------------------
Without returning Returning slack time
slack time to global to global pool
pool (with patch 7/7)
-----------------------------------------------------------------------
1 type A task 7.96s 10.71s
15 type B tasks 12.36s 9.79s
-----------------------------------------------------------------------

This shows the effects of slack time and the benefit of handling it correctly.

I request the scheduler maintainers and others for comments on these patches.

Regards,
Bharata.

#48 lore raw
Quoted 8 lines · Herbert Poetzl
Quoted 3 lines · Bharata B Rao

Hi,

Its been a while since we posted CPS hard limits (aka CFS bandwidth

Indeed, will see that I can incorporate those in the next experimental Linux-VServer patch for testing ...

Quoted 7 lines

btw, is it planned to allow for hard limits which are temporarily disabled when the machine/cpu would be otherwise idle (i.e. running the idle thread) or as we solved it, can we artificially advance the time (for the hard limits) when idle so that contexts which have work to do can work without sacrificing the priorization or the actual limits?

This is a fairly useful idea, I hadn't planned on it but I can see the applications for it.

It's somewhat complicated by the fact that throttled entities are not in-tree, making correct selection in the case where the machine is otherwise idle difficult. One method of supporting this could be to maintain a separate entity for throttled entities (the same mechanism could be extended to include SCHED_IDLE entities, as well as extending SCHED_IDLE to group scheduling).

I think it best to first iterate on the fundamentals since this has been baking for a long time, before we try to add extensions.

Quoted 8 lines

best,
Herbert

PS: from a quick glance I take it that using large values for period and quota, while keeping the ratio the same allows for 'burst loads'?

Exactly!

Another approach we've used is to use small value for period and quota (with fixed ratio) for latency sensitive applications. This allows you to not blow out the tail of your latency distribution (since each individual throttle is for a short period of time, tail latencies are capped in exchange for a median latency increase).

Quoted 71 lines
Quoted 70 lines

control now) patches, hence a quick recap first:

- I have been working on CFS hard limits since last year and have posted a few versions of the same (last post: http://lkml.org/lkml/2010/1/5/44)
- Paul Turner and Nikhil Rao meanwhile started working on CFS bandwidth control and have posted a couple of versions.
  (last post v2: http://lwn.net/Articles/385055/)

Paul's approach mainly changed the way the CPU hard limit was represented. After his post, I decided to work with them and discontinue my patch series since their global bandwidth specification for group appears more flexible than the RT-type per-cpu bandwidth specification I had in my series.

Since Paul seems to be busy, I am taking the freedom of posting the next version of his patches with a few enhancements to the slack time handling. (more on this later)

Main changes in this post:

- Return the unused and remaining local quota at each CPU to the global runtime pool.
- A few fixes:
      - Explicitly wake up the idle cpu during unthrottle.
      - Optimally handle throttling of current task within enqueue_task.
      - Fix compilation break with CONFIG_PREEMPT on.
      - Fix a compilation break at intermediate patch level.
- Applies on 2.6.36-rc7.

More about slack time issue
---------------------------
Bandwidth available to a group is specified by two parameters: cpu.cfs_quota_us and cpu.cfs_period_us. cpu.cfs_quota_us is the max CPU time a group can consume within the time period of cpu.cfs_period_us. The quota available to a group within a period is maintained in a per-group global pool. In each CPU, the consumption happens by obtaining a slice of this global pool.

If the local quota (obtained as slices of global pool) isn't fully consumed within a given period, a group can potentially get more CPU time than its allowed for in the next interval. This is due to the slack time that may be left over from the previous interval. More details about how this is fixed is present in the description part of patch 7/7. Here I will only show the benefit of handling the slack time correctly through this experiment:

On a 16 CPU system, two different kinds of tasks were run as part of a group which had quota/bandwidth as 500000/500000 [=> 500ms/500ms], which means that the group was capped at 1CPU worth of time every period.

Type A task: Complete CPU hog.
Type B task: Sleeps for 500ms and runs as CPU hog for next 500ms. And this cycle repeats.

1 task of type A and 15 tasks of type B were run for 20s, each bound to a different CPU. At the end of 20s, the CPU time obtained by each of them looked like this:

-----------------------------------------------------------------------
                      Without returning       Returning slack time slack time to global    to global pool pool                    (with patch 7/7)
-----------------------------------------------------------------------
1 type A task         7.96s                   10.71s
15 type B tasks               12.36s                  9.79s
-----------------------------------------------------------------------

This shows the effects of slack time and the benefit of handling it correctly.

I request the scheduler maintainers and others for comments on these patches.

Regards,
Bharata.

#25 lore raw

Re: [PATCH v3 3/7] sched: throttle cfs_rq entities which exceed their local quota

In reply to Bharata B Rao
Quoted 40 lines · On Tue, 12 Oct 2010 13:22:02 +0530 Bharata B Rao <[email protected]>…

sched: throttle cfs_rq entities which exceed their local quota

From: Paul Turner <[email protected]>

In account_cfs_rq_quota() (via update_curr()) we track consumption versus a cfs_rq's local quota and whether there is global quota available to continue enabling it in the event we run out.

This patch adds the required support for the latter case, throttling entities until quota is available to run. Throttling dequeues the entity in question and sends a reschedule to the owning cpu so that it can be evicted.

The following restrictions apply to a throttled cfs_rq:
- It is dequeued from sched_entity hierarchy and restricted from being re-enqueued. This means that new/waking children of this entity will be queued up to it, but not past it.
- It does not contribute to weight calculations in tg_shares_up
- In the case that the cfs_rq of the cpu we are trying to pull from is throttled it is is ignored by the loadbalancer in __load_balance_fair() and move_one_task_fair().

---
 kernel/sched.c      |   12 ++++++++
 kernel/sched_fair.c |   70 ++++++++++++++++++++++++++++++++++++++++++++++++----
 2 files changed, 76 insertions(+), 6 deletions(-)
kernel/sched.c +1 -0
@@ -387,6 +387,7 @@ struct cfs_rq {
 #endif
 #ifdef CONFIG_CFS_BANDWIDTH
 	u64 quota_assigned, quota_used;
+	int throttled;
 #endif
 #endif
 };

kernel/sched.c static void update_group_shares_cpu(stru · line 1673

Quoted 5 lines
kernel/sched.c +2 -0
@@ -1668,6 +1669,8 @@ static void update_group_shares_cpu(stru
 	}
 }
 
+static inline int cfs_rq_throttled(struct cfs_rq *cfs_rq);
+

I just curious that static-inline forward declaration is inlined ?

Quoted 6 lines
kernel/sched.c +0 -0
 /*
  * Re-compute the task group their per cpu shares over the given domain.
  * This needs to be done in a bottom-up fashion because the rq weight of a
@@ -1688,7 +1691,14 @@ static int tg_shares_up(struct task_grou
 	usd_rq_weight = per_cpu_ptr(update_shares_data, smp_processor_id());
 

kernel/sched.c static int tg_shares_up(struct task_grou · line 1701

Quoted 10 lines
kernel/sched.c +8 -1
 	for_each_cpu(i, sched_domain_span(sd)) {
-		weight = tg->cfs_rq[i]->load.weight;
+		/*
+		 * bandwidth throttled entities cannot contribute to load
+		 * balance
+		 */
+		if (!cfs_rq_throttled(tg->cfs_rq[i]))
+			weight = tg->cfs_rq[i]->load.weight;
+		else
+			weight = 0;

cpu.share and bandwidth control can't be used simultaneously or... is this fair ? I'm not familiar with scheduler but this allows boost this tg. Could you add a brief documentaion of a spec/feature. in the next post ?

Thanks,
-Kame

#26 lore raw

Re: [PATCH v3 3/7] sched: throttle cfs_rq entities which exceed their local quota

Quoted 46 lines · KAMEZAWA Hiroyuki
Quoted 43 lines · On Tue, 12 Oct 2010 13:22:02 +0530 Bharata B Rao <[email protected]>…

sched: throttle cfs_rq entities which exceed their local quota

From: Paul Turner <[email protected]>

In account_cfs_rq_quota() (via update_curr()) we track consumption versus a cfs_rq's local quota and whether there is global quota available to continue enabling it in the event we run out.

This patch adds the required support for the latter case, throttling entities until quota is available to run.  Throttling dequeues the entity in question and sends a reschedule to the owning cpu so that it can be evicted.

The following restrictions apply to a throttled cfs_rq:
- It is dequeued from sched_entity hierarchy and restricted from being re-enqueued.  This means that new/waking children of this entity will be queued up to it, but not past it.
- It does not contribute to weight calculations in tg_shares_up
- In the case that the cfs_rq of the cpu we are trying to pull from is throttled it is  is ignored by the loadbalancer in __load_balance_fair() and move_one_task_fair().

---
 kernel/sched.c      |   12 ++++++++
 kernel/sched_fair.c |   70 ++++++++++++++++++++++++++++++++++++++++++++++++----

 2 files changed, 76 insertions(+), 6 deletions(-)
kernel/sched.c +1 -0
@@ -387,6 +387,7 @@ struct cfs_rq {
  #endif
  #ifdef CONFIG_CFS_BANDWIDTH
       u64 quota_assigned, quota_used;
+     int throttled;
  #endif
  #endif
  };
@@ -1668,6 +1669,8 @@ static void update_group_shares_cpu(stru
       }
  }
 
Quoted 5 lines

kernel/sched.c static void update_group_shares_cpu(stru · line 1673

Quoted 2 lines
kernel/sched.c +2 -0
+static inline int cfs_rq_throttled(struct cfs_rq *cfs_rq);
+

I just curious that static-inline forward declaration is inlined ?

Hm. This function is tiny, I should just move it up, thanks.

Quoted 6 lines
Quoted 6 lines
kernel/sched.c +0 -0
  /*
   * Re-compute the task group their per cpu shares over the given domain.
   * This needs to be done in a bottom-up fashion because the rq weight of a
@@ -1688,7 +1691,14 @@ static int tg_shares_up(struct task_grou
       usd_rq_weight = per_cpu_ptr(update_shares_data, smp_processor_id());
 
Quoted 15 lines

kernel/sched.c static int tg_shares_up(struct task_grou · line 1701

Quoted 10 lines
kernel/sched.c +8 -1
       for_each_cpu(i, sched_domain_span(sd)) {
-             weight = tg->cfs_rq[i]->load.weight;
+             /*
+              * bandwidth throttled entities cannot contribute to load
+              * balance
+              */
+             if (!cfs_rq_throttled(tg->cfs_rq[i]))
+                     weight = tg->cfs_rq[i]->load.weight;
+             else
+                     weight = 0;

cpu.share and bandwidth control can't be used simultaneously or... is this fair ? I'm not familiar with scheduler but this allows boost this tg. Could you add a brief documentaion of a spec/feature. in the next post ?

Bandwidth control is orthogonal to shares, shares continue controls distribution of bandwidth when within quota. Bandwidth control only has 'perceivable' effect when you exceed your reservation within a quota period.

What the above is doing is removing any throttled entities from the load-balancer's weight calculations (based on contribution from throttled entities) since these entities are already dequeued and cannot be balanced.

Or have I misunderstood your question?

Quoted 4 lines

Thanks,
-Kame

#27 lore raw

Re: [PATCH v3 3/7] sched: throttle cfs_rq entities which exceed their local quota

Quoted 78 lines · Paul Turner
Quoted 46 lines · KAMEZAWA Hiroyuki
Quoted 43 lines · On Tue, 12 Oct 2010 13:22:02 +0530 Bharata B Rao <[email protected]>…

sched: throttle cfs_rq entities which exceed their local quota

From: Paul Turner <[email protected]>

In account_cfs_rq_quota() (via update_curr()) we track consumption versus a cfs_rq's local quota and whether there is global quota available to continue enabling it in the event we run out.

This patch adds the required support for the latter case, throttling entities until quota is available to run.  Throttling dequeues the entity in question and sends a reschedule to the owning cpu so that it can be evicted.

The following restrictions apply to a throttled cfs_rq:
- It is dequeued from sched_entity hierarchy and restricted from being re-enqueued.  This means that new/waking children of this entity will be queued up to it, but not past it.
- It does not contribute to weight calculations in tg_shares_up
- In the case that the cfs_rq of the cpu we are trying to pull from is throttled it is  is ignored by the loadbalancer in __load_balance_fair() and move_one_task_fair().

---
 kernel/sched.c      |   12 ++++++++
 kernel/sched_fair.c |   70 ++++++++++++++++++++++++++++++++++++++++++++++++----

 2 files changed, 76 insertions(+), 6 deletions(-)
kernel/sched.c +1 -0
@@ -387,6 +387,7 @@ struct cfs_rq {
  #endif
  #ifdef CONFIG_CFS_BANDWIDTH
       u64 quota_assigned, quota_used;
+     int throttled;
  #endif
  #endif
  };
@@ -1668,6 +1669,8 @@ static void update_group_shares_cpu(stru
       }
  }
 
Quoted 5 lines

kernel/sched.c static void update_group_shares_cpu(stru · line 1673

Quoted 2 lines
kernel/sched.c +2 -0
+static inline int cfs_rq_throttled(struct cfs_rq *cfs_rq);
+

I just curious that static-inline forward declaration is inlined ?

Hm. This function is tiny, I should just move it up, thanks.

Quoted 6 lines
Quoted 6 lines
kernel/sched.c +0 -0
  /*
   * Re-compute the task group their per cpu shares over the given domain.
   * This needs to be done in a bottom-up fashion because the rq weight of a
@@ -1688,7 +1691,14 @@ static int tg_shares_up(struct task_grou
       usd_rq_weight = per_cpu_ptr(update_shares_data, smp_processor_id());
 
Quoted 15 lines

kernel/sched.c static int tg_shares_up(struct task_grou · line 1701

Quoted 10 lines
kernel/sched.c +8 -1
       for_each_cpu(i, sched_domain_span(sd)) {
-             weight = tg->cfs_rq[i]->load.weight;
+             /*
+              * bandwidth throttled entities cannot contribute to load
+              * balance
+              */
+             if (!cfs_rq_throttled(tg->cfs_rq[i]))
+                     weight = tg->cfs_rq[i]->load.weight;
+             else
+                     weight = 0;

cpu.share and bandwidth control can't be used simultaneously or... is this fair ? I'm not familiar with scheduler but this allows boost this tg. Could you add a brief documentaion of a spec/feature. in the next post ?

Quoted 4 lines

Bandwidth control is orthogonal to shares, shares continue controls distribution of bandwidth when within quota. Bandwidth control only has 'perceivable' effect when you exceed your reservation within a quota period.

So if a group gets throttled since its approaching its limit, it might not be possible to see perfect fairness b/n groups since bandwidth control kind of takes priority.

Regards,
Bharata.

#28 lore raw

Re: [PATCH v3 3/7] sched: throttle cfs_rq entities which exceed their local quota

Quoted 79 lines · Bharata B Rao
Quoted 78 lines · Paul Turner
Quoted 46 lines · KAMEZAWA Hiroyuki
Quoted 43 lines · On Tue, 12 Oct 2010 13:22:02 +0530 Bharata B Rao <[email protected]>…

sched: throttle cfs_rq entities which exceed their local quota

From: Paul Turner <[email protected]>

In account_cfs_rq_quota() (via update_curr()) we track consumption versus a cfs_rq's local quota and whether there is global quota available to continue enabling it in the event we run out.

This patch adds the required support for the latter case, throttling entities until quota is available to run.  Throttling dequeues the entity in question and sends a reschedule to the owning cpu so that it can be evicted.

The following restrictions apply to a throttled cfs_rq:
- It is dequeued from sched_entity hierarchy and restricted from being re-enqueued.  This means that new/waking children of this entity will be queued up to it, but not past it.
- It does not contribute to weight calculations in tg_shares_up
- In the case that the cfs_rq of the cpu we are trying to pull from is throttled it is  is ignored by the loadbalancer in __load_balance_fair() and move_one_task_fair().

---
 kernel/sched.c      |   12 ++++++++
 kernel/sched_fair.c |   70 ++++++++++++++++++++++++++++++++++++++++++++++++----

 2 files changed, 76 insertions(+), 6 deletions(-)
kernel/sched.c +1 -0
@@ -387,6 +387,7 @@ struct cfs_rq {
  #endif
  #ifdef CONFIG_CFS_BANDWIDTH
       u64 quota_assigned, quota_used;
+     int throttled;
  #endif
  #endif
  };
@@ -1668,6 +1669,8 @@ static void update_group_shares_cpu(stru
       }
  }
 
Quoted 5 lines

kernel/sched.c static void update_group_shares_cpu(stru · line 1673

Quoted 2 lines
kernel/sched.c +2 -0
+static inline int cfs_rq_throttled(struct cfs_rq *cfs_rq);
+

I just curious that static-inline forward declaration is inlined ?

Hm.   This function is tiny, I should just move it up, thanks.

Quoted 21 lines
Quoted 6 lines
kernel/sched.c +0 -0
  /*
   * Re-compute the task group their per cpu shares over the given domain.
   * This needs to be done in a bottom-up fashion because the rq weight of a
@@ -1688,7 +1691,14 @@ static int tg_shares_up(struct task_grou
       usd_rq_weight = per_cpu_ptr(update_shares_data, smp_processor_id());
 

kernel/sched.c static int tg_shares_up(struct task_grou · line 1701

Quoted 10 lines
kernel/sched.c +8 -1
       for_each_cpu(i, sched_domain_span(sd)) {
-             weight = tg->cfs_rq[i]->load.weight;
+             /*
+              * bandwidth throttled entities cannot contribute to load
+              * balance
+              */
+             if (!cfs_rq_throttled(tg->cfs_rq[i]))
+                     weight = tg->cfs_rq[i]->load.weight;
+             else
+                     weight = 0;

cpu.share and bandwidth control can't be used simultaneously or... is this fair ? I'm not familiar with scheduler but this allows boost this tg. Could you add a brief documentaion of a spec/feature. in the next post ?

Quoted 8 lines
Quoted 4 lines

Bandwidth control is orthogonal to shares, shares continue controls distribution of bandwidth when within quota.  Bandwidth control only has 'perceivable' effect when you exceed your reservation within a quota period.

So if a group gets throttled since its approaching its limit, it might not be possible to see perfect fairness b/n groups since bandwidth control kind of takes priority.

It's two-fold:

A) The shares will be released so that they can be distributed to other cpus within the group (where there may be quota remaining)
B) The weight will be hierarchically removed to *improve* fairness since those entities are not actually running (this is fixing the accounting, since these calculations are lazy we don't do it at time of throttle).

It shouldn't have negative implications for group:group fairness.

Quoted 4 lines

Regards,
Bharata.

#29 lore raw

Re: [PATCH v3 3/7] sched: throttle cfs_rq entities which exceed their local quota

In reply to Paul Turner
Quoted 32 lines · On Tue, 12 Oct 2010 23:44:29 -0700 Paul Turner <[email protected]> wrote:
Quoted 9 lines · KAMEZAWA Hiroyuki
Quoted 6 lines · On Tue, 12 Oct 2010 13:22:02 +0530 Bharata B Rao <[email protected]>…

 /*
  * Re-compute the task group their per cpu shares over the given domain.
  * This needs to be done in a bottom-up fashion because the rq weight of a

kernel/sched.c +0 -0
@@ -1688,7 +1691,14 @@ static int tg_shares_up(struct task_grou
       usd_rq_weight = per_cpu_ptr(update_shares_data, smp_processor_id());
 
Quoted 15 lines

kernel/sched.c static int tg_shares_up(struct task_grou · line 1701

Quoted 10 lines
kernel/sched.c +8 -1
       for_each_cpu(i, sched_domain_span(sd)) {
-             weight = tg->cfs_rq[i]->load.weight;
+             /*
+              * bandwidth throttled entities cannot contribute to load
+              * balance
+              */
+             if (!cfs_rq_throttled(tg->cfs_rq[i]))
+                     weight = tg->cfs_rq[i]->load.weight;
+             else
+                     weight = 0;

cpu.share and bandwidth control can't be used simultaneously or... is this fair ? I'm not familiar with scheduler but this allows boost this tg. Could you add a brief documentaion of a spec/feature. in the next post ?

Bandwidth control is orthogonal to shares, shares continue controls distribution of bandwidth when within quota. Bandwidth control only has 'perceivable' effect when you exceed your reservation within a quota period.

Quoted 7 lines

What the above is doing is removing any throttled entities from the load-balancer's weight calculations (based on contribution from throttled entities) since these entities are already dequeued and cannot be balanced.

Or have I misunderstood your question?

Thank you for quick reply.
It seems I don't undestand what "cfs_rq_throttled()==1" means.

Thanks,
-Kame

#30 lore raw

Re: [PATCH v3 3/7] sched: throttle cfs_rq entities which exceed their local quota

Quoted 40 lines · KAMEZAWA Hiroyuki
Quoted 37 lines · On Tue, 12 Oct 2010 23:44:29 -0700 Paul Turner <[email protected]> wrote:
Quoted 9 lines · KAMEZAWA Hiroyuki
Quoted 6 lines · On Tue, 12 Oct 2010 13:22:02 +0530 Bharata B Rao <[email protected]>…

 /*
  * Re-compute the task group their per cpu shares over the given domain.
  * This needs to be done in a bottom-up fashion because the rq weight of a

kernel/sched.c +0 -0
@@ -1688,7 +1691,14 @@ static int tg_shares_up(struct task_grou
       usd_rq_weight = per_cpu_ptr(update_shares_data, smp_processor_id());
 
Quoted 15 lines

kernel/sched.c static int tg_shares_up(struct task_grou · line 1701

Quoted 10 lines
kernel/sched.c +8 -1
       for_each_cpu(i, sched_domain_span(sd)) {
-             weight = tg->cfs_rq[i]->load.weight;
+             /*
+              * bandwidth throttled entities cannot contribute to load
+              * balance
+              */
+             if (!cfs_rq_throttled(tg->cfs_rq[i]))
+                     weight = tg->cfs_rq[i]->load.weight;
+             else
+                     weight = 0;

cpu.share and bandwidth control can't be used simultaneously or... is this fair ? I'm not familiar with scheduler but this allows boost this tg. Could you add a brief documentaion of a spec/feature. in the next post ?

Bandwidth control is orthogonal to shares, shares continue controls distribution of bandwidth when within quota.  Bandwidth control only has 'perceivable' effect when you exceed your reservation within a quota period.

What the above is doing is removing any throttled entities from the load-balancer's weight calculations (based on contribution from throttled entities) since these entities are already dequeued and cannot be balanced.

Quoted 5 lines
Quoted 2 lines

Or have I misunderstood your question?

Thank you for quick reply.
It seems I don't undestand what "cfs_rq_throttled()==1" means.

cfs_rq_throttled() == 1 correlates to cfs_rq->throttled == 1.

This is set when a cfs_rq exceeds it's local bandwidth quota and there is no quota available in the global pool to refresh it.

At that point the cfs_rq is forcibly throttled, we accomplish this by

a) Ending its execution
b) Removing it from the entity tree (se->on_rq == 0)
c) Setting the throttled flag

The cfs_rq->throttled flag is required to track this state so that we do not re-enqueue a throttled entity on child wake-up.

It also tells us here that we should update the accounting since these se's, while containing runnable entities, are not actually on_rq.

Quoted 5 lines

Thanks,
-Kame

#2 lore raw

Re: [PATCH v3 1/7] sched: introduce primitives to account for CFS bandwidth tracking

In reply to Bharata B Rao
Quoted 66 lines · Bharata B Rao

sched: introduce primitives to account for CFS bandwidth tracking

From: Paul Turner <[email protected]>

In this patch we introduce the notion of CFS bandwidth, to account for the realities of SMP this is partitioned into globally unassigned bandwidth, and locally claimed bandwidth:
- The global bandwidth is per task_group, it represents a pool of unclaimed bandwidth that cfs_rq's can allocate from. It uses the new cfs_bandwidth structure.
- The local bandwidth is tracked per-cfs_rq, this represents allotments from the global pool
bandwidth assigned to a task_group, this is tracked using the new cfs_bandwidth structure.

Bandwidth is managed via cgroupfs via two new files in the cpu subsystem:
- cpu.cfs_period_us : the bandwidth period in usecs
- cpu.cfs_quota_us : the cpu bandwidth (in usecs) that this tg will be allowed to consume over period above.

A per-cfs_bandwidth timer is also introduced to handle future refresh at period expiration. There's some minor refactoring here so that start_bandwidth_timer() functionality can be shared

---
 init/Kconfig        |    9 +
 kernel/sched.c      |  271 +++++++++++++++++++++++++++++++++++++++++++++++-----
 kernel/sched_fair.c |   10 +
 3 files changed, 268 insertions(+), 22 deletions(-)
init/Kconfig +9 -0
@@ -609,6 +609,15 @@ config FAIR_GROUP_SCHED
 	depends on CGROUP_SCHED
 	default CGROUP_SCHED
 
+config CFS_BANDWIDTH
+	bool "CPU bandwidth provisioning for FAIR_GROUP_SCHED"
+	depends on EXPERIMENTAL
+	depends on FAIR_GROUP_SCHED
+	default n
+	help
+	  This option allows users to define quota and period for cpu
+	  bandwidth provisioning on a per-cgroup basis.
+
 config RT_GROUP_SCHED
 	bool "Group scheduling for SCHED_RR/FIFO"
 	depends on EXPERIMENTAL
kernel/sched.c +6 -2
@@ -192,10 +192,28 @@ static inline int rt_bandwidth_enabled(v
 	return sysctl_sched_rt_runtime >= 0;
 }
 
-static void start_rt_bandwidth(struct rt_bandwidth *rt_b)
+static void start_bandwidth_timer(struct hrtimer *period_timer, ktime_t period)
 {
-	ktime_t now;
+	unsigned long delta;
+	ktime_t soft, hard, now;
+
+	for (;;) {
+		if (hrtimer_active(period_timer))

kernel/sched.c static inline int rt_bandwidth_enabled(v · line 211

Quoted 10 lines
kernel/sched.c +9 -0
+			break;
 
+		now = hrtimer_cb_get_time(period_timer);
+		hrtimer_forward(period_timer, now, period);
+
+		soft = hrtimer_get_softexpires(period_timer);
+		hard = hrtimer_get_expires(period_timer);
+		delta = ktime_to_ns(ktime_sub(hard, soft));
+		__hrtimer_start_range_ns(period_timer, soft, delta,
+					 HRTIMER_MODE_ABS_PINNED, 0);

This code can be replaced with

hrtimer_start_expires(period_timer, HRTIMER_MODE_ABS_PINNED) if we don't care about wakeup_softirq, is there a reason we prefer to keep wakeup as 0?

Quoted 76 lines
kernel/sched.c +29 -16
+	}
+}
+
+static void start_rt_bandwidth(struct rt_bandwidth *rt_b)
+{
 	if (!rt_bandwidth_enabled() || rt_b->rt_runtime == RUNTIME_INF)
 		return;
 
@@ -203,22 +221,7 @@ static void start_rt_bandwidth(struct rt
 		return;
 
 	raw_spin_lock(&rt_b->rt_runtime_lock);
-	for (;;) {
-		unsigned long delta;
-		ktime_t soft, hard;
-
-		if (hrtimer_active(&rt_b->rt_period_timer))
-			break;
-
-		now = hrtimer_cb_get_time(&rt_b->rt_period_timer);
-		hrtimer_forward(&rt_b->rt_period_timer, now, rt_b->rt_period);
-
-		soft = hrtimer_get_softexpires(&rt_b->rt_period_timer);
-		hard = hrtimer_get_expires(&rt_b->rt_period_timer);
-		delta = ktime_to_ns(ktime_sub(hard, soft));
-		__hrtimer_start_range_ns(&rt_b->rt_period_timer, soft, delta,
-				HRTIMER_MODE_ABS_PINNED, 0);
-	}
+	start_bandwidth_timer(&rt_b->rt_period_timer, rt_b->rt_period);
 	raw_spin_unlock(&rt_b->rt_runtime_lock);
 }
 
@@ -243,6 +246,15 @@ struct cfs_rq;
 
 static LIST_HEAD(task_groups);
 
+#ifdef CONFIG_CFS_BANDWIDTH
+struct cfs_bandwidth {
+	raw_spinlock_t		lock;
+	ktime_t			period;
+	u64			runtime, quota;
+	struct hrtimer		period_timer;
+};
+#endif
+
 /* task group related information */
 struct task_group {
 	struct cgroup_subsys_state css;
@@ -268,6 +280,10 @@ struct task_group {
 	struct task_group *parent;
 	struct list_head siblings;
 	struct list_head children;
+
+#ifdef CONFIG_CFS_BANDWIDTH
+	struct cfs_bandwidth cfs_bandwidth;
+#endif
 };
 
 #define root_task_group init_task_group
@@ -369,9 +385,76 @@ struct cfs_rq {
 	 */
 	unsigned long rq_weight;
 #endif
+#ifdef CONFIG_CFS_BANDWIDTH
+	u64 quota_assigned, quota_used;
+#endif
 #endif
 };
 
+#ifdef CONFIG_CFS_BANDWIDTH
+static int do_sched_cfs_period_timer(struct cfs_bandwidth *cfs_b, int overrun);
+
+static enum hrtimer_restart sched_cfs_period_timer(struct hrtimer *timer)
+{
+	struct cfs_bandwidth *cfs_b =
+		container_of(timer, struct cfs_bandwidth, period_timer);

kernel/sched.c struct cfs_rq { · line 410

Quoted 10 lines
kernel/sched.c +10 -0
+	ktime_t now;
+	int overrun;
+	int idle = 0;
+
+	for (;;) {
+		now = hrtimer_cb_get_time(timer);
+		overrun = hrtimer_forward(timer, now, cfs_b->period);
+
+		if (!overrun)
+			break;

What is the significance of overrun? overrun is set when delta > interval. The logic seems to be that hrtimer is forwarded in steps of cfs_b->period till we reach the desired time.

Quoted 25 lines
kernel/sched.c +25 -0
+
+		idle = do_sched_cfs_period_timer(cfs_b, overrun);
+	}
+
+	return idle ? HRTIMER_NORESTART : HRTIMER_RESTART;
+}
+
+static
+void init_cfs_bandwidth(struct cfs_bandwidth *cfs_b, u64 quota, u64 period)
+{
+	raw_spin_lock_init(&cfs_b->lock);
+	cfs_b->quota = cfs_b->runtime = quota;
+	cfs_b->period = ns_to_ktime(period);
+
+	hrtimer_init(&cfs_b->period_timer, CLOCK_MONOTONIC, HRTIMER_MODE_REL);
+	cfs_b->period_timer.function = sched_cfs_period_timer;
+}
+
+static
+void init_cfs_rq_quota(struct cfs_rq *cfs_rq)
+{
+	cfs_rq->quota_used = 0;
+	if (cfs_rq->tg->cfs_bandwidth.quota == RUNTIME_INF)
+		cfs_rq->quota_assigned = RUNTIME_INF;
+	else

kernel/sched.c struct cfs_rq { · line 445

Quoted 10 lines
kernel/sched.c +10 -0
+		cfs_rq->quota_assigned = 0;
+}
+
+static void start_cfs_bandwidth(struct cfs_bandwidth *cfs_b)
+{
+	if (cfs_b->quota == RUNTIME_INF)
+		return;
+
+	if (hrtimer_active(&cfs_b->period_timer))
+		return;

Why the double check, start_bandwidth_timer also checks this. Is it to avoid doing the check under cfs_b->lock?

Quoted 115 lines
kernel/sched.c +48 -4
+
+	raw_spin_lock(&cfs_b->lock);
+	start_bandwidth_timer(&cfs_b->period_timer, cfs_b->period);
+	raw_spin_unlock(&cfs_b->lock);
+}
+
+static void destroy_cfs_bandwidth(struct cfs_bandwidth *cfs_b)
+{
+	hrtimer_cancel(&cfs_b->period_timer);
+}
+#endif
+
 /* Real-Time classes' related field in a runqueue: */
 struct rt_rq {
 	struct rt_prio_array active;
@@ -1840,6 +1923,14 @@ static inline void __set_task_cpu(struct
 
 static const struct sched_class rt_sched_class;
 
+#ifdef CONFIG_CFS_BANDWIDTH
+/*
+ * default period for cfs group bandwidth.
+ * default: 0.5s
+ */
+static u64 sched_cfs_bandwidth_period = 500000000ULL;
+#endif
+
 #define sched_class_highest (&rt_sched_class)
 #define for_each_class(class) \
    for (class = sched_class_highest; class; class = class->next)
@@ -7644,6 +7735,9 @@ static void init_tg_cfs_entry(struct tas
 	tg->cfs_rq[cpu] = cfs_rq;
 	init_cfs_rq(cfs_rq, rq);
 	cfs_rq->tg = tg;
+#ifdef CONFIG_CFS_BANDWIDTH
+	init_cfs_rq_quota(cfs_rq);
+#endif
 	if (add)
 		list_add(&cfs_rq->leaf_cfs_rq_list, &rq->leaf_cfs_rq_list);
 
@@ -7789,6 +7883,10 @@ void __init sched_init(void)
 		 * We achieve this by letting init_task_group's tasks sit
 		 * directly in rq->cfs (i.e init_task_group->se[] = NULL).
 		 */
+#ifdef CONFIG_CFS_BANDWIDTH
+		init_cfs_bandwidth(&init_task_group.cfs_bandwidth,
+				RUNTIME_INF, sched_cfs_bandwidth_period);
+#endif
 		init_tg_cfs_entry(&init_task_group, &rq->cfs, NULL, i, 1, NULL);
 #endif
 #endif /* CONFIG_FAIR_GROUP_SCHED */
@@ -8032,6 +8130,10 @@ static void free_fair_sched_group(struct
 {
 	int i;
 
+#ifdef CONFIG_CFS_BANDWIDTH
+	destroy_cfs_bandwidth(&tg->cfs_bandwidth);
+#endif
+
 	for_each_possible_cpu(i) {
 		if (tg->cfs_rq)
 			kfree(tg->cfs_rq[i]);
@@ -8059,7 +8161,10 @@ int alloc_fair_sched_group(struct task_g
 		goto err;
 
 	tg->shares = NICE_0_LOAD;
-
+#ifdef CONFIG_CFS_BANDWIDTH
+	init_cfs_bandwidth(&tg->cfs_bandwidth, RUNTIME_INF,
+			sched_cfs_bandwidth_period);
+#endif
 	for_each_possible_cpu(i) {
 		rq = cpu_rq(i);
 
@@ -8505,7 +8610,7 @@ static int __rt_schedulable(struct task_
 	return walk_tg_tree(tg_schedulable, tg_nop, &data);
 }
 
-static int tg_set_bandwidth(struct task_group *tg,
+static int tg_set_rt_bandwidth(struct task_group *tg,
 		u64 rt_period, u64 rt_runtime)
 {
 	int i, err = 0;
@@ -8544,7 +8649,7 @@ int sched_group_set_rt_runtime(struct ta
 	if (rt_runtime_us < 0)
 		rt_runtime = RUNTIME_INF;
 
-	return tg_set_bandwidth(tg, rt_period, rt_runtime);
+	return tg_set_rt_bandwidth(tg, rt_period, rt_runtime);
 }
 
 long sched_group_rt_runtime(struct task_group *tg)
@@ -8569,7 +8674,7 @@ int sched_group_set_rt_period(struct tas
 	if (rt_period == 0)
 		return -EINVAL;
 
-	return tg_set_bandwidth(tg, rt_period, rt_runtime);
+	return tg_set_rt_bandwidth(tg, rt_period, rt_runtime);
 }
 
 long sched_group_rt_period(struct task_group *tg)
@@ -8776,6 +8881,116 @@ static u64 cpu_shares_read_u64(struct cg
 
 	return (u64) tg->shares;
 }
+
+#ifdef CONFIG_CFS_BANDWIDTH
+static int tg_set_cfs_bandwidth(struct task_group *tg, u64 period, u64 quota)
+{
+	int i;
+	static DEFINE_MUTEX(mutex);
+
+	if (tg == &init_task_group)
+		return -EINVAL;
+

kernel/sched.c static u64 cpu_shares_read_u64(struct cg · line 8903

Quoted 10 lines
kernel/sched.c +10 -0
+	if (!period)
+		return -EINVAL;
+
+	/*
+	 * Ensure we have at least one tick of bandwidth every period.  This is
+	 * to prevent reaching a state of large arrears when throttled via
+	 * entity_tick() resulting in prolonged exit starvation.
+	 */
+	if (NS_TO_JIFFIES(quota) < 1)
+		return -EINVAL;

I hope we document this in the Documentation :)

kernel/sched.c static u64 cpu_shares_read_u64(struct cg · line 8911

Quoted 8 lines
kernel/sched.c +8 -0
+
+	mutex_lock(&mutex);
+	raw_spin_lock_irq(&tg->cfs_bandwidth.lock);
+	tg->cfs_bandwidth.period = ns_to_ktime(period);
+	tg->cfs_bandwidth.runtime = tg->cfs_bandwidth.quota = quota;
+	raw_spin_unlock_irq(&tg->cfs_bandwidth.lock);
+
+	for_each_possible_cpu(i) {

Why not for_each_online_cpu()?

Quoted 9 lines
kernel/sched.c +9 -0
+		struct cfs_rq *cfs_rq = tg->cfs_rq[i];
+		struct rq *rq = rq_of(cfs_rq);
+
+		raw_spin_lock_irq(&rq->lock);
+		init_cfs_rq_quota(cfs_rq);
+		raw_spin_unlock_irq(&rq->lock);
+	}
+	mutex_unlock(&mutex);
+

kernel/sched.c static u64 cpu_shares_read_u64(struct cg · line 8930

Quoted 10 lines
kernel/sched.c +10 -0
+	return 0;
+}
+
+int tg_set_cfs_quota(struct task_group *tg, long cfs_runtime_us)
+{
+	u64 quota, period;
+
+	period = ktime_to_ns(tg->cfs_bandwidth.period);
+	if (cfs_runtime_us < 0)
+		quota = RUNTIME_INF;

So -1 or -x results in infinite quota?

kernel/sched.c static u64 cpu_shares_read_u64(struct cg · line 8942

Quoted 12 lines
kernel/sched.c +12 -0
+	else
+		quota = (u64)cfs_runtime_us * NSEC_PER_USEC;
+
+	return tg_set_cfs_bandwidth(tg, period, quota);
+}
+
+long tg_get_cfs_quota(struct task_group *tg)
+{
+	u64 quota_us;
+
+	if (tg->cfs_bandwidth.quota == RUNTIME_INF)
+		return -1;

This is a little inconsistent, I can set -5, but I see -1 when I do a get?

Quoted 86 lines
kernel/sched.c +63 -0
+
+	quota_us = tg->cfs_bandwidth.quota;
+	do_div(quota_us, NSEC_PER_USEC);
+	return quota_us;
+}
+
+int tg_set_cfs_period(struct task_group *tg, long cfs_period_us)
+{
+	u64 quota, period;
+
+	period = (u64)cfs_period_us * NSEC_PER_USEC;
+	quota = tg->cfs_bandwidth.quota;
+
+	if (period <= 0)
+		return -EINVAL;
+
+	return tg_set_cfs_bandwidth(tg, period, quota);
+}
+
+long tg_get_cfs_period(struct task_group *tg)
+{
+	u64 cfs_period_us;
+
+	cfs_period_us = ktime_to_ns(tg->cfs_bandwidth.period);
+	do_div(cfs_period_us, NSEC_PER_USEC);
+	return cfs_period_us;
+}
+
+static s64 cpu_cfs_quota_read_s64(struct cgroup *cgrp, struct cftype *cft)
+{
+	return tg_get_cfs_quota(cgroup_tg(cgrp));
+}
+
+static int cpu_cfs_quota_write_s64(struct cgroup *cgrp, struct cftype *cftype,
+				s64 cfs_quota_us)
+{
+	return tg_set_cfs_quota(cgroup_tg(cgrp), cfs_quota_us);
+}
+
+static u64 cpu_cfs_period_read_u64(struct cgroup *cgrp, struct cftype *cft)
+{
+	return tg_get_cfs_period(cgroup_tg(cgrp));
+}
+
+static int cpu_cfs_period_write_u64(struct cgroup *cgrp, struct cftype *cftype,
+				u64 cfs_period_us)
+{
+	return tg_set_cfs_period(cgroup_tg(cgrp), cfs_period_us);
+}
+
+#endif /* CONFIG_CFS_BANDWIDTH */
 #endif /* CONFIG_FAIR_GROUP_SCHED */
 
 #ifdef CONFIG_RT_GROUP_SCHED
@@ -8810,6 +9025,18 @@ static struct cftype cpu_files[] = {
 		.write_u64 = cpu_shares_write_u64,
 	},
 #endif
+#ifdef CONFIG_CFS_BANDWIDTH
+	{
+		.name = "cfs_quota_us",
+		.read_s64 = cpu_cfs_quota_read_s64,
+		.write_s64 = cpu_cfs_quota_write_s64,
+	},
+	{
+		.name = "cfs_period_us",
+		.read_u64 = cpu_cfs_period_read_u64,
+		.write_u64 = cpu_cfs_period_write_u64,
+	},
+#endif
 #ifdef CONFIG_RT_GROUP_SCHED
 	{
 		.name = "rt_runtime_us",
kernel/sched_fair.c +3 -0
@@ -360,6 +360,9 @@ static void __enqueue_entity(struct cfs_
 
 	rb_link_node(&se->run_node, parent, link);
 	rb_insert_color(&se->run_node, &cfs_rq->tasks_timeline);
+#ifdef CONFIG_CFS_BANDWIDTH
+	start_cfs_bandwidth(&cfs_rq->tg->cfs_bandwidth);
+#endif
 }
 
 static void __dequeue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se)

kernel/sched_fair.c static void yield_task_fair(struct rq *r · line 1135

Quoted 7 lines
kernel/sched_fair.c +4 -0
@@ -1126,6 +1129,13 @@ static void yield_task_fair(struct rq *r
 	se->vruntime = rightmost->vruntime + 1;
 }
 
+#ifdef CONFIG_CFS_BANDWIDTH
+static int do_sched_cfs_period_timer(struct cfs_bandwidth *cfs_b, int overrun)
+{
+	return 1;

Hmmm.. what is 1? true?

Quoted 6 lines
kernel/sched_fair.c +3 -0
+}
+#endif
+
 #ifdef CONFIG_SMP
 
 static void task_waking_fair(struct rq *rq, struct task_struct *p)
Signature · 2 lines
	Three Cheers,
	Balbir
#9 lore raw

Re: [PATCH v3 2/7] sched: accumulate per-cfs_rq cpu usage

In reply to Bharata B Rao
Quoted 92 lines · Bharata B Rao

sched: accumulate per-cfs_rq cpu usage

From: Paul Turner <[email protected]>

Introduce account_cfs_rq_quota() to account bandwidth usage on the cfs_rq level versus task_groups for which bandwidth has been assigned. This is tracked by whether the local cfs_rq->quota_assigned is finite or infinite (RUNTIME_INF).

For cfs_rq's that belong to a bandwidth constrained task_group we introduce tg_request_cfs_quota() which attempts to allocate quota from the global pool for use locally. Updates involving the global pool are currently protected under cfs_bandwidth->lock, local pools are protected by rq->lock.

This patch only attempts to assign and track quota, no action is taken in the case that cfs_rq->quota_used exceeds cfs_rq->quota_assigned.

---
 include/linux/sched.h |    4 ++++
 kernel/sched.c        |   13 +++++++++++++
 kernel/sched_fair.c   |   50 ++++++++++++++++++++++++++++++++++++++++++++++++++
 kernel/sysctl.c       |   10 ++++++++++
 4 files changed, 77 insertions(+)
include/linux/sched.h +4 -0
@@ -1898,6 +1898,10 @@ int sched_rt_handler(struct ctl_table *t
 		void __user *buffer, size_t *lenp,
 		loff_t *ppos);
 
+#ifdef CONFIG_CFS_BANDWIDTH
+extern unsigned int sysctl_sched_cfs_bandwidth_slice;
+#endif
+
 extern unsigned int sysctl_sched_compat_yield;
 
 #ifdef CONFIG_RT_MUTEXES
kernel/sched.c +13 -0
@@ -1929,6 +1929,19 @@ static const struct sched_class rt_sched
  * default: 0.5s
  */
 static u64 sched_cfs_bandwidth_period = 500000000ULL;
+
+/*
+ * default slice of quota to allocate from global tg to local cfs_rq pool on
+ * each refresh
+ * default: 10ms
+ */
+unsigned int sysctl_sched_cfs_bandwidth_slice = 10000UL;
+
+static inline u64 sched_cfs_bandwidth_slice(void)
+{
+	return (u64)sysctl_sched_cfs_bandwidth_slice * NSEC_PER_USEC;
+}
+
 #endif
 
 #define sched_class_highest (&rt_sched_class)
kernel/sched_fair.c +13 -0
@@ -267,6 +267,16 @@ find_matching_se(struct sched_entity **s
 
 #endif	/* CONFIG_FAIR_GROUP_SCHED */
 
+#ifdef CONFIG_CFS_BANDWIDTH
+static inline struct cfs_bandwidth *tg_cfs_bandwidth(struct task_group *tg)
+{
+	return &tg->cfs_bandwidth;
+}
+
+static void account_cfs_rq_quota(struct cfs_rq *cfs_rq,
+		unsigned long delta_exec);
+#endif
+
 
 /**************************************************************
  * Scheduling class tree data structure manipulation methods:
@@ -547,6 +557,9 @@ static void update_curr(struct cfs_rq *c
 		cpuacct_charge(curtask, delta_exec);
 		account_group_exec_runtime(curtask, delta_exec);
 	}
+#ifdef CONFIG_CFS_BANDWIDTH
+	account_cfs_rq_quota(cfs_rq, delta_exec);
+#endif
 }
 
 static inline void

kernel/sched_fair.c static void yield_task_fair(struct rq *r · line 1151

Quoted 9 lines
kernel/sched_fair.c +6 -0
@@ -1130,6 +1143,43 @@ static void yield_task_fair(struct rq *r
 }
 
 #ifdef CONFIG_CFS_BANDWIDTH
+static u64 tg_request_cfs_quota(struct task_group *tg)
+{
+	struct cfs_bandwidth *cfs_b = tg_cfs_bandwidth(tg);
+	u64 delta = 0;
+
+	if (cfs_b->runtime > 0 || cfs_b->quota == RUNTIME_INF) {

Quick question for cfs_b->quota == RUNTIME_INF, won't cfs_b->runtime be always > 0?

Quoted 53 lines
kernel/sched_fair.c +31 -0
+		raw_spin_lock(&cfs_b->lock);
+		/*
+		 * it's possible a bandwidth update has changed the global
+		 * pool.
+		 */
+		if (cfs_b->quota == RUNTIME_INF)
+			delta = sched_cfs_bandwidth_slice();
+		else {
+			delta = min(cfs_b->runtime,
+					sched_cfs_bandwidth_slice());
+			cfs_b->runtime -= delta;
+		}
+		raw_spin_unlock(&cfs_b->lock);
+	}
+	return delta;
+}
+
+static void account_cfs_rq_quota(struct cfs_rq *cfs_rq,
+		unsigned long delta_exec)
+{
+	if (cfs_rq->quota_assigned == RUNTIME_INF)
+		return;
+
+	cfs_rq->quota_used += delta_exec;
+
+	if (cfs_rq->quota_used < cfs_rq->quota_assigned)
+		return;
+
+	cfs_rq->quota_assigned += tg_request_cfs_quota(cfs_rq->tg);
+}
+
 static int do_sched_cfs_period_timer(struct cfs_bandwidth *cfs_b, int overrun)
 {
 	return 1;
kernel/sysctl.c +10 -0
@@ -384,6 +384,16 @@ static struct ctl_table kern_table[] = {
 		.mode		= 0644,
 		.proc_handler	= proc_dointvec,
 	},
+#ifdef CONFIG_CFS_BANDWIDTH
+	{
+		.procname	= "sched_cfs_bandwidth_slice_us",
+		.data		= &sysctl_sched_cfs_bandwidth_slice,
+		.maxlen		= sizeof(unsigned int),
+		.mode		= 0644,
+		.proc_handler	= proc_dointvec_minmax,
+		.extra1		= &one,
+	},
+#endif
 #ifdef CONFIG_PROVE_LOCKING
 	{
 		.procname	= "prove_locking",
Signature · 2 lines
	Three Cheers,
	Balbir
#10 lore raw

Re: [PATCH v3 2/7] sched: accumulate per-cfs_rq cpu usage

Quoted 96 lines · Balbir Singh
Quoted 94 lines · Bharata B Rao

sched: accumulate per-cfs_rq cpu usage

From: Paul Turner <[email protected]>

Introduce account_cfs_rq_quota() to account bandwidth usage on the cfs_rq level versus task_groups for which bandwidth has been assigned.  This is tracked by whether the local cfs_rq->quota_assigned is finite or infinite (RUNTIME_INF).

For cfs_rq's that belong to a bandwidth constrained task_group we introduce tg_request_cfs_quota() which attempts to allocate quota from the global pool for use locally.  Updates involving the global pool are currently protected under cfs_bandwidth->lock, local pools are protected by rq->lock.

This patch only attempts to assign and track quota, no action is taken in the case that cfs_rq->quota_used exceeds cfs_rq->quota_assigned.

---
 include/linux/sched.h |    4 ++++
 kernel/sched.c        |   13 +++++++++++++
 kernel/sched_fair.c   |   50 ++++++++++++++++++++++++++++++++++++++++++++++++++ kernel/sysctl.c       |   10 ++++++++++

 4 files changed, 77 insertions(+)
include/linux/sched.h +4 -0
@@ -1898,6 +1898,10 @@ int sched_rt_handler(struct ctl_table *t
               void __user *buffer, size_t *lenp,
               loff_t *ppos);
 
+#ifdef CONFIG_CFS_BANDWIDTH
+extern unsigned int sysctl_sched_cfs_bandwidth_slice;
+#endif
+
  extern unsigned int sysctl_sched_compat_yield;
 
  #ifdef CONFIG_RT_MUTEXES
kernel/sched.c +13 -0
@@ -1929,6 +1929,19 @@ static const struct sched_class rt_sched
   * default: 0.5s
   */
  static u64 sched_cfs_bandwidth_period = 500000000ULL;
+
+/*
+ * default slice of quota to allocate from global tg to local cfs_rq pool on
+ * each refresh
+ * default: 10ms
+ */
+unsigned int sysctl_sched_cfs_bandwidth_slice = 10000UL;
+
+static inline u64 sched_cfs_bandwidth_slice(void)
+{
+     return (u64)sysctl_sched_cfs_bandwidth_slice * NSEC_PER_USEC;
+}
+
  #endif
 
  #define sched_class_highest (&rt_sched_class)
kernel/sched_fair.c +13 -0
@@ -267,6 +267,16 @@ find_matching_se(struct sched_entity **s
 
  #endif       /* CONFIG_FAIR_GROUP_SCHED */
 
+#ifdef CONFIG_CFS_BANDWIDTH
+static inline struct cfs_bandwidth *tg_cfs_bandwidth(struct task_group *tg)
+{
+     return &tg->cfs_bandwidth;
+}
+
+static void account_cfs_rq_quota(struct cfs_rq *cfs_rq,
+             unsigned long delta_exec);
+#endif
+
 
  /**************************************************************
   * Scheduling class tree data structure manipulation methods:
@@ -547,6 +557,9 @@ static void update_curr(struct cfs_rq *c
               cpuacct_charge(curtask, delta_exec);
               account_group_exec_runtime(curtask, delta_exec);
       }
+#ifdef CONFIG_CFS_BANDWIDTH
+     account_cfs_rq_quota(cfs_rq, delta_exec);
+#endif
  }
 

 static inline void

kernel/sched_fair.c +0 -0
@@ -1130,6 +1143,43 @@ static void yield_task_fair(struct rq *r
  }
 
Quoted 10 lines

kernel/sched_fair.c static void yield_task_fair(struct rq *r · line 1151

Quoted 7 lines
kernel/sched_fair.c +6 -0
  #ifdef CONFIG_CFS_BANDWIDTH
+static u64 tg_request_cfs_quota(struct task_group *tg)
+{
+     struct cfs_bandwidth *cfs_b = tg_cfs_bandwidth(tg);
+     u64 delta = 0;
+
+     if (cfs_b->runtime > 0 || cfs_b->quota == RUNTIME_INF) {

Quick question for cfs_b->quota == RUNTIME_INF, won't cfs_b->runtime be always > 0?

Hi Balbir,

cfs_b->runtime can be 0 if the task group exhausts its quota. cfs_b->runtime is a counter that is periodically refreshed to cfs_b->quota, and is decremented every time a cfs_rq requests a slice.

-Thanks,
Nikhil

Quoted 59 lines
Quoted 44 lines
kernel/sched_fair.c +31 -0
+             raw_spin_lock(&cfs_b->lock);
+             /*
+              * it's possible a bandwidth update has changed the global
+              * pool.
+              */
+             if (cfs_b->quota == RUNTIME_INF)
+                     delta = sched_cfs_bandwidth_slice();
+             else {
+                     delta = min(cfs_b->runtime,
+                                     sched_cfs_bandwidth_slice());
+                     cfs_b->runtime -= delta;
+             }
+             raw_spin_unlock(&cfs_b->lock);
+     }
+     return delta;
+}
+
+static void account_cfs_rq_quota(struct cfs_rq *cfs_rq,
+             unsigned long delta_exec)
+{
+     if (cfs_rq->quota_assigned == RUNTIME_INF)
+             return;
+
+     cfs_rq->quota_used += delta_exec;
+
+     if (cfs_rq->quota_used < cfs_rq->quota_assigned)
+             return;
+
+     cfs_rq->quota_assigned += tg_request_cfs_quota(cfs_rq->tg);
+}
+
  static int do_sched_cfs_period_timer(struct cfs_bandwidth *cfs_b, int overrun)
  {
       return 1;
kernel/sysctl.c +3 -0
@@ -384,6 +384,16 @@ static struct ctl_table kern_table[] = {
               .mode           = 0644,
               .proc_handler   = proc_dointvec,
       },
+#ifdef CONFIG_CFS_BANDWIDTH
+     {
+             .procname       = "sched_cfs_bandwidth_slice_us",

kernel/sysctl.c static struct ctl_table kern_table[] = { · line 399

Quoted 10 lines
kernel/sysctl.c +7 -0
+             .data           = &sysctl_sched_cfs_bandwidth_slice,
+             .maxlen         = sizeof(unsigned int),
+             .mode           = 0644,
+             .proc_handler   = proc_dointvec_minmax,
+             .extra1         = &one,
+     },
+#endif
  #ifdef CONFIG_PROVE_LOCKING
       {
               .procname       = "prove_locking",

--
       Three Cheers,
       Balbir

#11 lore raw

Re: [PATCH v3 2/7] sched: accumulate per-cfs_rq cpu usage

Quoted 9 lines · Nikhil Rao
Quoted 2 lines

Quick question for cfs_b->quota == RUNTIME_INF, won't cfs_b->runtime be always > 0?

Hi Balbir,

cfs_b->runtime can be 0 if the task group exhausts its quota. cfs_b->runtime is a counter that is periodically refreshed to cfs_b->quota, and is decremented every time a cfs_rq requests a slice.

Thanks, Nikhil

I saw several checks for quota == RUNTIME_INF and saw updates not happening. Do we track usage for cgroups with infinite quota? IOW, is runtime updated? If so, why?

Signature · 2 lines
	Three Cheers,
	Balbir
#12 lore raw

Re: [PATCH v3 2/7] sched: accumulate per-cfs_rq cpu usage

Quoted 12 lines · Balbir Singh
Quoted 9 lines · Nikhil Rao
Quoted 2 lines

Quick question for cfs_b->quota == RUNTIME_INF, won't cfs_b->runtime be always > 0?

Hi Balbir,

cfs_b->runtime can be 0 if the task group exhausts its quota. cfs_b->runtime is a counter that is periodically refreshed to cfs_b->quota, and is decremented every time a cfs_rq requests a slice.

Quoted 6 lines

Thanks, Nikhil

I saw several checks for quota == RUNTIME_INF and saw updates not happening. Do we track usage for cgroups with infinite quota? IOW, is runtime updated? If so, why?

We don't track usage or update runtime for cgroups with infinite quota. Most of these RUNTIME_INF checks are usually at the top of the functions and return immediately. The checks in the middle of functions are mostly to prevent races when cfs_b->quota is updated.

And ... I think I might have misunderstood your original question. Let me try answering that again. We check for quota == RUNTIME_INF (in addition to cfs_b->runtime > 0) because it is possible that the global pool is updated to RUNTIME_INF between the quota check in account_cfs_rq_quota() and when the actual quota is distributed in tg_request_cfs_quota(). I hope that answers your original question.

-Thanks,
Nikhil

Quoted 4 lines

--
       Three Cheers,
       Balbir

#3 lore raw

Re: [PATCH v3 1/7] sched: introduce primitives to account for CFS bandwidth tracking

In reply to Balbir Singh
Quoted 81 lines · Balbir Singh
Quoted 66 lines · Bharata B Rao

sched: introduce primitives to account for CFS bandwidth tracking

From: Paul Turner <[email protected]>

In this patch we introduce the notion of CFS bandwidth, to account for the realities of SMP this is partitioned into globally unassigned bandwidth, and locally claimed bandwidth:
- The global bandwidth is per task_group, it represents a pool of unclaimed bandwidth that cfs_rq's can allocate from. It uses the new cfs_bandwidth structure.
- The local bandwidth is tracked per-cfs_rq, this represents allotments from the global pool
bandwidth assigned to a task_group, this is tracked using the new cfs_bandwidth structure.

Bandwidth is managed via cgroupfs via two new files in the cpu subsystem:
- cpu.cfs_period_us : the bandwidth period in usecs
- cpu.cfs_quota_us : the cpu bandwidth (in usecs) that this tg will be allowed to consume over period above.

A per-cfs_bandwidth timer is also introduced to handle future refresh at period expiration. There's some minor refactoring here so that start_bandwidth_timer() functionality can be shared

---
 init/Kconfig        |    9 +
 kernel/sched.c      |  271 +++++++++++++++++++++++++++++++++++++++++++++++-----
 kernel/sched_fair.c |   10 +
 3 files changed, 268 insertions(+), 22 deletions(-)
init/Kconfig +9 -0
@@ -609,6 +609,15 @@ config FAIR_GROUP_SCHED
 	depends on CGROUP_SCHED
 	default CGROUP_SCHED
 
+config CFS_BANDWIDTH
+	bool "CPU bandwidth provisioning for FAIR_GROUP_SCHED"
+	depends on EXPERIMENTAL
+	depends on FAIR_GROUP_SCHED
+	default n
+	help
+	  This option allows users to define quota and period for cpu
+	  bandwidth provisioning on a per-cgroup basis.
+
 config RT_GROUP_SCHED
 	bool "Group scheduling for SCHED_RR/FIFO"
 	depends on EXPERIMENTAL
kernel/sched.c +6 -2
@@ -192,10 +192,28 @@ static inline int rt_bandwidth_enabled(v
 	return sysctl_sched_rt_runtime >= 0;
 }
 
-static void start_rt_bandwidth(struct rt_bandwidth *rt_b)
+static void start_bandwidth_timer(struct hrtimer *period_timer, ktime_t period)
 {
-	ktime_t now;
+	unsigned long delta;
+	ktime_t soft, hard, now;
+
+	for (;;) {
+		if (hrtimer_active(period_timer))

kernel/sched.c static inline int rt_bandwidth_enabled(v · line 211

Quoted 10 lines
kernel/sched.c +9 -0
+			break;
 
+		now = hrtimer_cb_get_time(period_timer);
+		hrtimer_forward(period_timer, now, period);
+
+		soft = hrtimer_get_softexpires(period_timer);
+		hard = hrtimer_get_expires(period_timer);
+		delta = ktime_to_ns(ktime_sub(hard, soft));
+		__hrtimer_start_range_ns(period_timer, soft, delta,
+					 HRTIMER_MODE_ABS_PINNED, 0);

This code can be replaced with

Quoted 3 lines

hrtimer_start_expires(period_timer, HRTIMER_MODE_ABS_PINNED) if we don't care about wakeup_softirq, is there a reason we prefer to keep wakeup as 0?

We have carried this from RT code. ATM I am not exactly sure if wakeup parameter makes any difference to us. Need to check.

Quoted 83 lines
Quoted 83 lines
kernel/sched.c +35 -16
+	}
+}
+
+static void start_rt_bandwidth(struct rt_bandwidth *rt_b)
+{
 	if (!rt_bandwidth_enabled() || rt_b->rt_runtime == RUNTIME_INF)
 		return;
 
@@ -203,22 +221,7 @@ static void start_rt_bandwidth(struct rt
 		return;
 
 	raw_spin_lock(&rt_b->rt_runtime_lock);
-	for (;;) {
-		unsigned long delta;
-		ktime_t soft, hard;
-
-		if (hrtimer_active(&rt_b->rt_period_timer))
-			break;
-
-		now = hrtimer_cb_get_time(&rt_b->rt_period_timer);
-		hrtimer_forward(&rt_b->rt_period_timer, now, rt_b->rt_period);
-
-		soft = hrtimer_get_softexpires(&rt_b->rt_period_timer);
-		hard = hrtimer_get_expires(&rt_b->rt_period_timer);
-		delta = ktime_to_ns(ktime_sub(hard, soft));
-		__hrtimer_start_range_ns(&rt_b->rt_period_timer, soft, delta,
-				HRTIMER_MODE_ABS_PINNED, 0);
-	}
+	start_bandwidth_timer(&rt_b->rt_period_timer, rt_b->rt_period);
 	raw_spin_unlock(&rt_b->rt_runtime_lock);
 }
 
@@ -243,6 +246,15 @@ struct cfs_rq;
 
 static LIST_HEAD(task_groups);
 
+#ifdef CONFIG_CFS_BANDWIDTH
+struct cfs_bandwidth {
+	raw_spinlock_t		lock;
+	ktime_t			period;
+	u64			runtime, quota;
+	struct hrtimer		period_timer;
+};
+#endif
+
 /* task group related information */
 struct task_group {
 	struct cgroup_subsys_state css;
@@ -268,6 +280,10 @@ struct task_group {
 	struct task_group *parent;
 	struct list_head siblings;
 	struct list_head children;
+
+#ifdef CONFIG_CFS_BANDWIDTH
+	struct cfs_bandwidth cfs_bandwidth;
+#endif
 };
 
 #define root_task_group init_task_group
@@ -369,9 +385,76 @@ struct cfs_rq {
 	 */
 	unsigned long rq_weight;
 #endif
+#ifdef CONFIG_CFS_BANDWIDTH
+	u64 quota_assigned, quota_used;
+#endif
 #endif
 };
 
+#ifdef CONFIG_CFS_BANDWIDTH
+static int do_sched_cfs_period_timer(struct cfs_bandwidth *cfs_b, int overrun);
+
+static enum hrtimer_restart sched_cfs_period_timer(struct hrtimer *timer)
+{
+	struct cfs_bandwidth *cfs_b =
+		container_of(timer, struct cfs_bandwidth, period_timer);
+	ktime_t now;
+	int overrun;
+	int idle = 0;
+
+	for (;;) {
+		now = hrtimer_cb_get_time(timer);
Quoted 8 lines

kernel/sched.c struct cfs_rq { · line 410

Quoted 4 lines
kernel/sched.c +4 -0
+		overrun = hrtimer_forward(timer, now, cfs_b->period);
+
+		if (!overrun)
+			break;

What is the significance of overrun? overrun is set when delta > interval. The logic seems to be that hrtimer is forwarded in steps of cfs_b->period till we reach the desired time.

This is again carried from RT code where RT accounts for timer overruns by appropriately adjusting the runtime. We aren't currently doing anything with it in our timer handler, but we do need to check if and how we need to handle timer overruns.

Quoted 31 lines
Quoted 31 lines
kernel/sched.c +30 -0
+
+		idle = do_sched_cfs_period_timer(cfs_b, overrun);
+	}
+
+	return idle ? HRTIMER_NORESTART : HRTIMER_RESTART;
+}
+
+static
+void init_cfs_bandwidth(struct cfs_bandwidth *cfs_b, u64 quota, u64 period)
+{
+	raw_spin_lock_init(&cfs_b->lock);
+	cfs_b->quota = cfs_b->runtime = quota;
+	cfs_b->period = ns_to_ktime(period);
+
+	hrtimer_init(&cfs_b->period_timer, CLOCK_MONOTONIC, HRTIMER_MODE_REL);
+	cfs_b->period_timer.function = sched_cfs_period_timer;
+}
+
+static
+void init_cfs_rq_quota(struct cfs_rq *cfs_rq)
+{
+	cfs_rq->quota_used = 0;
+	if (cfs_rq->tg->cfs_bandwidth.quota == RUNTIME_INF)
+		cfs_rq->quota_assigned = RUNTIME_INF;
+	else
+		cfs_rq->quota_assigned = 0;
+}
+
+static void start_cfs_bandwidth(struct cfs_bandwidth *cfs_b)
+{
Quoted 8 lines

kernel/sched.c struct cfs_rq { · line 445

Quoted 5 lines
kernel/sched.c +5 -0
+	if (cfs_b->quota == RUNTIME_INF)
+		return;
+
+	if (hrtimer_active(&cfs_b->period_timer))
+		return;

Why the double check, start_bandwidth_timer also checks this. Is it to avoid doing the check under cfs_b->lock?

Again this is carried from RT code. I think the first one is quick check to back out w/o having to take the cfs_b->lock.

Quoted 120 lines
Quoted 120 lines
kernel/sched.c +52 -4
+
+	raw_spin_lock(&cfs_b->lock);
+	start_bandwidth_timer(&cfs_b->period_timer, cfs_b->period);
+	raw_spin_unlock(&cfs_b->lock);
+}
+
+static void destroy_cfs_bandwidth(struct cfs_bandwidth *cfs_b)
+{
+	hrtimer_cancel(&cfs_b->period_timer);
+}
+#endif
+
 /* Real-Time classes' related field in a runqueue: */
 struct rt_rq {
 	struct rt_prio_array active;
@@ -1840,6 +1923,14 @@ static inline void __set_task_cpu(struct
 
 static const struct sched_class rt_sched_class;
 
+#ifdef CONFIG_CFS_BANDWIDTH
+/*
+ * default period for cfs group bandwidth.
+ * default: 0.5s
+ */
+static u64 sched_cfs_bandwidth_period = 500000000ULL;
+#endif
+
 #define sched_class_highest (&rt_sched_class)
 #define for_each_class(class) \
    for (class = sched_class_highest; class; class = class->next)
@@ -7644,6 +7735,9 @@ static void init_tg_cfs_entry(struct tas
 	tg->cfs_rq[cpu] = cfs_rq;
 	init_cfs_rq(cfs_rq, rq);
 	cfs_rq->tg = tg;
+#ifdef CONFIG_CFS_BANDWIDTH
+	init_cfs_rq_quota(cfs_rq);
+#endif
 	if (add)
 		list_add(&cfs_rq->leaf_cfs_rq_list, &rq->leaf_cfs_rq_list);
 
@@ -7789,6 +7883,10 @@ void __init sched_init(void)
 		 * We achieve this by letting init_task_group's tasks sit
 		 * directly in rq->cfs (i.e init_task_group->se[] = NULL).
 		 */
+#ifdef CONFIG_CFS_BANDWIDTH
+		init_cfs_bandwidth(&init_task_group.cfs_bandwidth,
+				RUNTIME_INF, sched_cfs_bandwidth_period);
+#endif
 		init_tg_cfs_entry(&init_task_group, &rq->cfs, NULL, i, 1, NULL);
 #endif
 #endif /* CONFIG_FAIR_GROUP_SCHED */
@@ -8032,6 +8130,10 @@ static void free_fair_sched_group(struct
 {
 	int i;
 
+#ifdef CONFIG_CFS_BANDWIDTH
+	destroy_cfs_bandwidth(&tg->cfs_bandwidth);
+#endif
+
 	for_each_possible_cpu(i) {
 		if (tg->cfs_rq)
 			kfree(tg->cfs_rq[i]);
@@ -8059,7 +8161,10 @@ int alloc_fair_sched_group(struct task_g
 		goto err;
 
 	tg->shares = NICE_0_LOAD;
-
+#ifdef CONFIG_CFS_BANDWIDTH
+	init_cfs_bandwidth(&tg->cfs_bandwidth, RUNTIME_INF,
+			sched_cfs_bandwidth_period);
+#endif
 	for_each_possible_cpu(i) {
 		rq = cpu_rq(i);
 
@@ -8505,7 +8610,7 @@ static int __rt_schedulable(struct task_
 	return walk_tg_tree(tg_schedulable, tg_nop, &data);
 }
 
-static int tg_set_bandwidth(struct task_group *tg,
+static int tg_set_rt_bandwidth(struct task_group *tg,
 		u64 rt_period, u64 rt_runtime)
 {
 	int i, err = 0;
@@ -8544,7 +8649,7 @@ int sched_group_set_rt_runtime(struct ta
 	if (rt_runtime_us < 0)
 		rt_runtime = RUNTIME_INF;
 
-	return tg_set_bandwidth(tg, rt_period, rt_runtime);
+	return tg_set_rt_bandwidth(tg, rt_period, rt_runtime);
 }
 
 long sched_group_rt_runtime(struct task_group *tg)
@@ -8569,7 +8674,7 @@ int sched_group_set_rt_period(struct tas
 	if (rt_period == 0)
 		return -EINVAL;
 
-	return tg_set_bandwidth(tg, rt_period, rt_runtime);
+	return tg_set_rt_bandwidth(tg, rt_period, rt_runtime);
 }
 
 long sched_group_rt_period(struct task_group *tg)
@@ -8776,6 +8881,116 @@ static u64 cpu_shares_read_u64(struct cg
 
 	return (u64) tg->shares;
 }
+
+#ifdef CONFIG_CFS_BANDWIDTH
+static int tg_set_cfs_bandwidth(struct task_group *tg, u64 period, u64 quota)
+{
+	int i;
+	static DEFINE_MUTEX(mutex);
+
+	if (tg == &init_task_group)
+		return -EINVAL;
+
+	if (!period)
+		return -EINVAL;
+
+	/*
Quoted 8 lines

kernel/sched.c static u64 cpu_shares_read_u64(struct cg · line 8903

Quoted 6 lines
kernel/sched.c +6 -0
+	 * Ensure we have at least one tick of bandwidth every period.  This is
+	 * to prevent reaching a state of large arrears when throttled via
+	 * entity_tick() resulting in prolonged exit starvation.
+	 */
+	if (NS_TO_JIFFIES(quota) < 1)
+		return -EINVAL;

I hope we document this in the Documentation :)

Sure. This and also some documentation about the cgroup files we introduce will be added in our next post.

Quoted 11 lines

kernel/sched.c static u64 cpu_shares_read_u64(struct cg · line 8911

Quoted 9 lines
kernel/sched.c +8 -0
+
+	mutex_lock(&mutex);
+	raw_spin_lock_irq(&tg->cfs_bandwidth.lock);
+	tg->cfs_bandwidth.period = ns_to_ktime(period);
+	tg->cfs_bandwidth.runtime = tg->cfs_bandwidth.quota = quota;
+	raw_spin_unlock_irq(&tg->cfs_bandwidth.lock);
+
+	for_each_possible_cpu(i) {

Why not for_each_online_cpu()?

Again this is similar to what is done in RT. We however need to re-check if we want to take any special actions on CPU hot(un)plug.

Quoted 14 lines
Quoted 14 lines
kernel/sched.c +13 -0
+		struct cfs_rq *cfs_rq = tg->cfs_rq[i];
+		struct rq *rq = rq_of(cfs_rq);
+
+		raw_spin_lock_irq(&rq->lock);
+		init_cfs_rq_quota(cfs_rq);
+		raw_spin_unlock_irq(&rq->lock);
+	}
+	mutex_unlock(&mutex);
+
+	return 0;
+}
+
+int tg_set_cfs_quota(struct task_group *tg, long cfs_runtime_us)
Quoted 8 lines

kernel/sched.c static u64 cpu_shares_read_u64(struct cg · line 8930

Quoted 6 lines
kernel/sched.c +6 -0
+{
+	u64 quota, period;
+
+	period = ktime_to_ns(tg->cfs_bandwidth.period);
+	if (cfs_runtime_us < 0)
+		quota = RUNTIME_INF;

So -1 or -x results in infinite quota?

Yes.

Quoted 16 lines

kernel/sched.c static u64 cpu_shares_read_u64(struct cg · line 8942

Quoted 13 lines
kernel/sched.c +12 -0
+	else
+		quota = (u64)cfs_runtime_us * NSEC_PER_USEC;
+
+	return tg_set_cfs_bandwidth(tg, period, quota);
+}
+
+long tg_get_cfs_quota(struct task_group *tg)
+{
+	u64 quota_us;
+
+	if (tg->cfs_bandwidth.quota == RUNTIME_INF)
+		return -1;

This is a little inconsistent, I can set -5, but I see -1 when I do a get?

I see your point. May be we should just allow only -1 and positive values for quota.

Quoted 90 lines
Quoted 90 lines
kernel/sched.c +63 -0
+
+	quota_us = tg->cfs_bandwidth.quota;
+	do_div(quota_us, NSEC_PER_USEC);
+	return quota_us;
+}
+
+int tg_set_cfs_period(struct task_group *tg, long cfs_period_us)
+{
+	u64 quota, period;
+
+	period = (u64)cfs_period_us * NSEC_PER_USEC;
+	quota = tg->cfs_bandwidth.quota;
+
+	if (period <= 0)
+		return -EINVAL;
+
+	return tg_set_cfs_bandwidth(tg, period, quota);
+}
+
+long tg_get_cfs_period(struct task_group *tg)
+{
+	u64 cfs_period_us;
+
+	cfs_period_us = ktime_to_ns(tg->cfs_bandwidth.period);
+	do_div(cfs_period_us, NSEC_PER_USEC);
+	return cfs_period_us;
+}
+
+static s64 cpu_cfs_quota_read_s64(struct cgroup *cgrp, struct cftype *cft)
+{
+	return tg_get_cfs_quota(cgroup_tg(cgrp));
+}
+
+static int cpu_cfs_quota_write_s64(struct cgroup *cgrp, struct cftype *cftype,
+				s64 cfs_quota_us)
+{
+	return tg_set_cfs_quota(cgroup_tg(cgrp), cfs_quota_us);
+}
+
+static u64 cpu_cfs_period_read_u64(struct cgroup *cgrp, struct cftype *cft)
+{
+	return tg_get_cfs_period(cgroup_tg(cgrp));
+}
+
+static int cpu_cfs_period_write_u64(struct cgroup *cgrp, struct cftype *cftype,
+				u64 cfs_period_us)
+{
+	return tg_set_cfs_period(cgroup_tg(cgrp), cfs_period_us);
+}
+
+#endif /* CONFIG_CFS_BANDWIDTH */
 #endif /* CONFIG_FAIR_GROUP_SCHED */
 
 #ifdef CONFIG_RT_GROUP_SCHED
@@ -8810,6 +9025,18 @@ static struct cftype cpu_files[] = {
 		.write_u64 = cpu_shares_write_u64,
 	},
 #endif
+#ifdef CONFIG_CFS_BANDWIDTH
+	{
+		.name = "cfs_quota_us",
+		.read_s64 = cpu_cfs_quota_read_s64,
+		.write_s64 = cpu_cfs_quota_write_s64,
+	},
+	{
+		.name = "cfs_period_us",
+		.read_u64 = cpu_cfs_period_read_u64,
+		.write_u64 = cpu_cfs_period_write_u64,
+	},
+#endif
 #ifdef CONFIG_RT_GROUP_SCHED
 	{
 		.name = "rt_runtime_us",
kernel/sched_fair.c +3 -0
@@ -360,6 +360,9 @@ static void __enqueue_entity(struct cfs_
 
 	rb_link_node(&se->run_node, parent, link);
 	rb_insert_color(&se->run_node, &cfs_rq->tasks_timeline);
+#ifdef CONFIG_CFS_BANDWIDTH
+	start_cfs_bandwidth(&cfs_rq->tg->cfs_bandwidth);
+#endif
 }
 
 static void __dequeue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se)
@@ -1126,6 +1129,13 @@ static void yield_task_fair(struct rq *r
 	se->vruntime = rightmost->vruntime + 1;
 }
 
Quoted 6 lines

kernel/sched_fair.c static void yield_task_fair(struct rq *r · line 1135

Quoted 4 lines
kernel/sched_fair.c +4 -0
+#ifdef CONFIG_CFS_BANDWIDTH
+static int do_sched_cfs_period_timer(struct cfs_bandwidth *cfs_b, int overrun)
+{
+	return 1;

Hmmm.. what is 1? true?

That was just a place holder. This function gets full functionality in a later patch.

Thanks for your review.

Regards,
Bharata.

#13 lore raw

Re: [PATCH v3 2/7] sched: accumulate per-cfs_rq cpu usage

In reply to Nikhil Rao
Quoted 25 lines · Nikhil Rao
Quoted 12 lines · Balbir Singh
Quoted 9 lines · Nikhil Rao
Quoted 2 lines

Quick question for cfs_b->quota == RUNTIME_INF, won't cfs_b->runtime be always > 0?

Hi Balbir,

cfs_b->runtime can be 0 if the task group exhausts its quota. cfs_b->runtime is a counter that is periodically refreshed to cfs_b->quota, and is decremented every time a cfs_rq requests a slice.

Quoted 6 lines

Thanks, Nikhil

I saw several checks for quota == RUNTIME_INF and saw updates not happening. Do we track usage for cgroups with infinite quota? IOW, is runtime updated? If so, why?

We don't track usage or update runtime for cgroups with infinite quota. Most of these RUNTIME_INF checks are usually at the top of the functions and return immediately. The checks in the middle of functions are mostly to prevent races when cfs_b->quota is updated.

Quoted 7 lines

And ... I think I might have misunderstood your original question. Let me try answering that again. We check for quota == RUNTIME_INF (in addition to cfs_b->runtime > 0) because it is possible that the global pool is updated to RUNTIME_INF between the quota check in account_cfs_rq_quota() and when the actual quota is distributed in tg_request_cfs_quota(). I hope that answers your original question.

Yes, it does, thanks!

Signature · 2 lines
	Three Cheers,
	Balbir
maintainer
#4 lore raw

Re: [PATCH v3 1/7] sched: introduce primitives to account for CFS bandwidth tracking

In reply to Balbir Singh
Quoted 22 lines · Balbir Singh
Quoted 9 lines
kernel/sched.c +6 -2
-static void start_rt_bandwidth(struct rt_bandwidth *rt_b)
+static void start_bandwidth_timer(struct hrtimer *period_timer, ktime_t period)
 {
-	ktime_t now;
+	unsigned long delta;
+	ktime_t soft, hard, now;
+
+	for (;;) {
+		if (hrtimer_active(period_timer))

kernel/sched.c static inline int rt_bandwidth_enabled(v · line 211

Quoted 10 lines
kernel/sched.c +9 -0
+			break;
 
+		now = hrtimer_cb_get_time(period_timer);
+		hrtimer_forward(period_timer, now, period);
+
+		soft = hrtimer_get_softexpires(period_timer);
+		hard = hrtimer_get_expires(period_timer);
+		delta = ktime_to_ns(ktime_sub(hard, soft));
+		__hrtimer_start_range_ns(period_timer, soft, delta,
+					 HRTIMER_MODE_ABS_PINNED, 0);

This code can be replaced with

Quoted 3 lines

hrtimer_start_expires(period_timer, HRTIMER_MODE_ABS_PINNED) if we don't care about wakeup_softirq, is there a reason we prefer to keep wakeup as 0?

You cannot do wakeups while holding the rq->lock, can you? :-)

Quoted 14 lines
Quoted 14 lines
kernel/sched.c +12 -0
+	}
+}
 
 
+static enum hrtimer_restart sched_cfs_period_timer(struct hrtimer *timer)
+{
+	struct cfs_bandwidth *cfs_b =
+		container_of(timer, struct cfs_bandwidth, period_timer);
+	ktime_t now;
+	int overrun;
+	int idle = 0;
+
+	for (;;) {
+		now = hrtimer_cb_get_time(timer);
Quoted 9 lines

kernel/sched.c struct cfs_rq { · line 410

Quoted 4 lines
kernel/sched.c +4 -0
+		overrun = hrtimer_forward(timer, now, cfs_b->period);
+
+		if (!overrun)
+			break;

What is the significance of overrun? overrun is set when delta > interval. The logic seems to be that hrtimer is forwarded in steps of cfs_b->period till we reach the desired time.

Overrun is the number of periods missed. The goal is to increment the quota for each period, if the timer is late 3 periods, we still need to increment it 3 times, that's what overrun does.

Quoted 7 lines
Quoted 6 lines
kernel/sched.c +6 -0
+
+		idle = do_sched_cfs_period_timer(cfs_b, overrun);
+	}
+
+	return idle ? HRTIMER_NORESTART : HRTIMER_RESTART;
+}
Quoted 10 lines

kernel/sched.c struct cfs_rq { · line 445

Quoted 7 lines
kernel/sched.c +7 -0
+static void start_cfs_bandwidth(struct cfs_bandwidth *cfs_b)
+{
+	if (cfs_b->quota == RUNTIME_INF)
+		return;
+
+	if (hrtimer_active(&cfs_b->period_timer))
+		return;

Why the double check, start_bandwidth_timer also checks this. Is it to avoid doing the check under cfs_b->lock?

Basically..

Quoted 20 lines
Quoted 20 lines
kernel/sched.c +19 -0
+
+	raw_spin_lock(&cfs_b->lock);
+	start_bandwidth_timer(&cfs_b->period_timer, cfs_b->period);
+	raw_spin_unlock(&cfs_b->lock);
+}
+
 
+#ifdef CONFIG_CFS_BANDWIDTH
+static int tg_set_cfs_bandwidth(struct task_group *tg, u64 period, u64 quota)
+{
+	int i;
+	static DEFINE_MUTEX(mutex);
+
+	if (tg == &init_task_group)
+		return -EINVAL;
+
+	if (!period)
+		return -EINVAL;
+
+	/*
Quoted 8 lines

kernel/sched.c static u64 cpu_shares_read_u64(struct cg · line 8903

Quoted 6 lines
kernel/sched.c +6 -0
+	 * Ensure we have at least one tick of bandwidth every period.  This is
+	 * to prevent reaching a state of large arrears when throttled via
+	 * entity_tick() resulting in prolonged exit starvation.
+	 */
+	if (NS_TO_JIFFIES(quota) < 1)
+		return -EINVAL;

I hope we document this in the Documentation :)

/me went and looked up arrears in a dictionary and wonders why 'debt' wasn't good enough.

Quoted 10 lines

kernel/sched.c static u64 cpu_shares_read_u64(struct cg · line 8911

Quoted 8 lines
kernel/sched.c +8 -0
+
+	mutex_lock(&mutex);
+	raw_spin_lock_irq(&tg->cfs_bandwidth.lock);
+	tg->cfs_bandwidth.period = ns_to_ktime(period);
+	tg->cfs_bandwidth.runtime = tg->cfs_bandwidth.quota = quota;
+	raw_spin_unlock_irq(&tg->cfs_bandwidth.lock);
+
+	for_each_possible_cpu(i) {

Why not for_each_online_cpu()?

Probably could be cured with a hotplug handler, but then you need to track more state iirc.

Quoted 11 lines
Quoted 11 lines
kernel/sched.c +11 -0
+		struct cfs_rq *cfs_rq = tg->cfs_rq[i];
+		struct rq *rq = rq_of(cfs_rq);
+
+		raw_spin_lock_irq(&rq->lock);
+		init_cfs_rq_quota(cfs_rq);
+		raw_spin_unlock_irq(&rq->lock);
+	}
+	mutex_unlock(&mutex);
+
+	return 0;
+}
maintainer
#14 lore raw

Re: [PATCH v3 2/7] sched: accumulate per-cfs_rq cpu usage

In reply to Bharata B Rao
Quoted 12 lines · Bharata B Rao
kernel/sched_fair.c +12 -0
+static u64 tg_request_cfs_quota(struct task_group *tg)
+{
+       struct cfs_bandwidth *cfs_b = tg_cfs_bandwidth(tg);
+       u64 delta = 0;
+
+       if (cfs_b->runtime > 0 || cfs_b->quota == RUNTIME_INF) {
+               raw_spin_lock(&cfs_b->lock);
+               /*
+                * it's possible a bandwidth update has changed the global
+                * pool.
+                */
+               if (cfs_b->quota == RUNTIME_INF)

kernel/sched_fair.c static void yield_task_fair(struct rq *r · line 1167

Quoted 10 lines
kernel/sched_fair.c +10 -0
+                       delta = sched_cfs_bandwidth_slice();
+               else {
+                       delta = min(cfs_b->runtime,
+                                       sched_cfs_bandwidth_slice());
+                       cfs_b->runtime -= delta;
+               }
+               raw_spin_unlock(&cfs_b->lock);
+       }
+       return delta;
+} 

Since you check cfs_b->quote outside of cfs_b->lock anyway, you might as well avoid taking the lock in that case and directly return slice.

Also, you possibly evaluate sched_cfs_bandwidth_slice() twice.

maintainer
#17 lore raw

Re: [PATCH v3 2/7] sched: accumulate per-cfs_rq cpu usage

In reply to Bharata B Rao

kernel/sched_fair.c static void yield_task_fair(struct rq *r · line 1181

Quoted 13 lines · Bharata B Rao
kernel/sched_fair.c +13 -0
+static void account_cfs_rq_quota(struct cfs_rq *cfs_rq,
+               unsigned long delta_exec)
+{
+       if (cfs_rq->quota_assigned == RUNTIME_INF)
+               return;
+
+       cfs_rq->quota_used += delta_exec;
+
+       if (cfs_rq->quota_used < cfs_rq->quota_assigned)
+               return;
+
+       cfs_rq->quota_assigned += tg_request_cfs_quota(cfs_rq->tg);
+}

That looks iffy, quota_assigned is only ever incremented and can wrap. Why not subtract delta_exec and replenish when <0? That keeps the numbers small.

#15 lore raw

Re: [PATCH v3 2/7] sched: accumulate per-cfs_rq cpu usage

In reply to Peter Zijlstra
Quoted 18 lines · Peter Zijlstra
Quoted 17 lines · Bharata B Rao
kernel/sched_fair.c +17 -0
+static u64 tg_request_cfs_quota(struct task_group *tg)
+{
+       struct cfs_bandwidth *cfs_b = tg_cfs_bandwidth(tg);
+       u64 delta = 0;
+
+       if (cfs_b->runtime > 0 || cfs_b->quota == RUNTIME_INF) {
+               raw_spin_lock(&cfs_b->lock);
+               /*
+                * it's possible a bandwidth update has changed the global
+                * pool.
+                */
+               if (cfs_b->quota == RUNTIME_INF)
+                       delta = sched_cfs_bandwidth_slice();
+               else {
+                       delta = min(cfs_b->runtime,
+                                       sched_cfs_bandwidth_slice());
+                       cfs_b->runtime -= delta;
Quoted 9 lines
Quoted 5 lines

+               }
+               raw_spin_unlock(&cfs_b->lock);
+       }
+       return delta;
+}

Since you check cfs_b->quote outside of cfs_b->lock anyway, you might as well avoid taking the lock in that case and directly return slice.

Do you mean in the RUNTIME_INF case?

I suppose we could just avoid taking the lock there (theoretically it would be possible to slightly over-commit on a RUNTIME_INF => constrained transition, but this should be the supremely uncommon case and hey, it's transitioning from unlimited bandwidth anyway).

Quoted 2 lines

Also, you possibly evaluate sched_cfs_bandwidth_slice() twice.

Separate branch no? Should only be one evaluation. (fwiw the min macro looks to cache the evaluation)

maintainer
#31 lore raw

Re: [PATCH v3 3/7] sched: throttle cfs_rq entities which exceed their local quota

In reply to KAMEZAWA Hiroyuki
Quoted 3 lines · KAMEZAWA Hiroyuki

cpu.share and bandwidth control can't be used simultaneously or... is this fair ? I'm not familiar with scheduler but this allows boost this tg. Could you add a brief documentaion of a spec/feature. in the next post ?

Like explained, shares control the proportional distribution of time between groups, bandwidth puts a limit on how much time a group can take. It can cause a group to receive less than its fair share, but never more.

There is, however, a problem with all this, and that is that all this explicit idling of tasks can lead to a form of priority inversion. Regular preemptive scheduling already suffers from this, but explicitly idling tasks exacerbates the situation.

You basically get to add the longest induced idle time to all your lock hold times.

#18 lore raw

Re: [PATCH v3 2/7] sched: accumulate per-cfs_rq cpu usage

In reply to Peter Zijlstra
Quoted 16 lines · Peter Zijlstra

kernel/sched_fair.c static void yield_task_fair(struct rq *r · line 1181

Quoted 13 lines · Bharata B Rao
kernel/sched_fair.c +13 -0
+static void account_cfs_rq_quota(struct cfs_rq *cfs_rq,
+               unsigned long delta_exec)
+{
+       if (cfs_rq->quota_assigned == RUNTIME_INF)
+               return;
+
+       cfs_rq->quota_used += delta_exec;
+
+       if (cfs_rq->quota_used < cfs_rq->quota_assigned)
+               return;
+
+       cfs_rq->quota_assigned += tg_request_cfs_quota(cfs_rq->tg);
+}

That looks iffy, quota_assigned is only ever incremented and can wrap.

This can't advance at a rate faster than ~vruntime and we can't handle wrapping there anyway (fortunately it would take something like 35k years?)

Quoted 3 lines

Why not subtract delta_exec and replenish when <0? That keeps the numbers small.

Accounting in the opposite direction allows us to catch-up in subsequent periods when a task exceeds its bandwidth across an interval where we are not able to immediately throttle it (e.g. costly syscall without config_prempt). Since we'll continue to accrue the execution time in this case it will be effectively pre-charged against the next slice received.

maintainer
#21 lore raw

Re: [PATCH v3 2/7] sched: accumulate per-cfs_rq cpu usage

In reply to Bharata B Rao

kernel/sysctl.c static struct ctl_table kern_table[] = { · line 396

Quoted 10 lines · Bharata B Rao
kernel/sysctl.c +10 -0
+#ifdef CONFIG_CFS_BANDWIDTH
+       {
+               .procname       = "sched_cfs_bandwidth_slice_us",
+               .data           = &sysctl_sched_cfs_bandwidth_slice,
+               .maxlen         = sizeof(unsigned int),
+               .mode           = 0644,
+               .proc_handler   = proc_dointvec_minmax,
+               .extra1         = &one,
+       },
+#endif 

So this is basically your scalability knob.. the larger this value less less frequent we have to access global state, but the less parallelism is possible due to fewer CPUs depleting the total quota, leaving nothing for the others.

I guess one could go try and play load-balancer games to try and mitigate this by pulling this group's tasks to the CPU(s) that have move bandwidth for that group, but balancing that against the regular load-balancer goal of well balancing load, will undoubtedly be 'interesting'...

#22 lore raw

Re: [PATCH v3 2/7] sched: accumulate per-cfs_rq cpu usage

Quoted 17 lines · Peter Zijlstra

kernel/sysctl.c static struct ctl_table kern_table[] = { · line 396

Quoted 10 lines · Bharata B Rao
kernel/sysctl.c +10 -0
+#ifdef CONFIG_CFS_BANDWIDTH
+       {
+               .procname       = "sched_cfs_bandwidth_slice_us",
+               .data           = &sysctl_sched_cfs_bandwidth_slice,
+               .maxlen         = sizeof(unsigned int),
+               .mode           = 0644,
+               .proc_handler   = proc_dointvec_minmax,
+               .extra1         = &one,
+       },
+#endif

So this is basically your scalability knob.. the larger this value less less frequent we have to access global state, but the less parallelism is possible due to fewer CPUs depleting the total quota, leaving nothing for the others.

Exactly

Quoted 6 lines

I guess one could go try and play load-balancer games to try and mitigate this by pulling this group's tasks to the CPU(s) that have move bandwidth for that group, but balancing that against the regular load-balancer goal of well balancing load, will undoubtedly be 'interesting'...

I considered this approach as an alternative previously, but I don't think it can be enacted effectively:

Since quota will likely expire in a staggered fashion you're going to get a funnel-herd effect as everything is crowded onto the cpus with remaining quota.

It's much more easily avoided by keeping the slice small enough (relative to the bandwidth period) that we're not potentially stranding a significant percentage of our quota. The potential for abuse could be eliminated/reduced here by making the slice size a constant ratio relative to the period length. This would also make possible parallelism more deterministic.

I also think versioning the quota so that it can be potentially returned and redistributed on sleep is more effective/efficient in avoiding stranded quota.

Quoted 2 lines
maintainer
#19 lore raw

Re: [PATCH v3 2/7] sched: accumulate per-cfs_rq cpu usage

In reply to Paul Turner
Quoted 18 lines · Paul Turner
Quoted 16 lines · Peter Zijlstra

kernel/sched_fair.c static void yield_task_fair(struct rq *r · line 1181

Quoted 13 lines · Bharata B Rao
kernel/sched_fair.c +13 -0
+static void account_cfs_rq_quota(struct cfs_rq *cfs_rq,
+               unsigned long delta_exec)
+{
+       if (cfs_rq->quota_assigned == RUNTIME_INF)
+               return;
+
+       cfs_rq->quota_used += delta_exec;
+
+       if (cfs_rq->quota_used < cfs_rq->quota_assigned)
+               return;
+
+       cfs_rq->quota_assigned += tg_request_cfs_quota(cfs_rq->tg);
+}

That looks iffy, quota_assigned is only ever incremented and can wrap.

Quoted 3 lines

This can't advance at a rate faster than ~vruntime and we can't handle wrapping there anyway (fortunately it would take something like 35k years?)

You can't go faster than wall-time, vruntime can actually go a lot faster and can deal with wrapping.

Quoted 10 lines
Quoted 3 lines

Why not subtract delta_exec and replenish when <0? That keeps the numbers small.

Accounting in the opposite direction allows us to catch-up in subsequent periods when a task exceeds its bandwidth across an interval where we are not able to immediately throttle it (e.g. costly syscall without config_prempt). Since we'll continue to accrue the execution time in this case it will be effectively pre-charged against the next slice received.

Humm, how so, that's a simply matter of the quota going negative, right?

#23 lore raw

Re: [PATCH v3 2/7] sched: accumulate per-cfs_rq cpu usage

In reply to Paul Turner
Quoted 35 lines · Paul Turner
Quoted 17 lines · Peter Zijlstra

kernel/sysctl.c static struct ctl_table kern_table[] = { · line 396

Quoted 10 lines · Bharata B Rao
kernel/sysctl.c +10 -0
+#ifdef CONFIG_CFS_BANDWIDTH
+       {
+               .procname       = "sched_cfs_bandwidth_slice_us",
+               .data           = &sysctl_sched_cfs_bandwidth_slice,
+               .maxlen         = sizeof(unsigned int),
+               .mode           = 0644,
+               .proc_handler   = proc_dointvec_minmax,
+               .extra1         = &one,
+       },
+#endif

So this is basically your scalability knob.. the larger this value less less frequent we have to access global state, but the less parallelism is possible due to fewer CPUs depleting the total quota, leaving nothing for the others.

Exactly

Quoted 6 lines

I guess one could go try and play load-balancer games to try and mitigate this by pulling this group's tasks to the CPU(s) that have move bandwidth for that group, but balancing that against the regular load-balancer goal of well balancing load, will undoubtedly be 'interesting'...

I considered this approach as an alternative previously, but I don't think it can be enacted effectively:

Since quota will likely expire in a staggered fashion you're going to get a funnel-herd effect as everything is crowded onto the cpus with remaining quota.

Quoted 6 lines

It's much more easily avoided by keeping the slice small enough (relative to the bandwidth period) that we're not potentially stranding a significant percentage of our quota. The potential for abuse could be eliminated/reduced here by making the slice size a constant ratio relative to the period length. This would also make possible parallelism more deterministic.

You can see from the numbers I posted in 0/7, how current default of 10ms slice can lead to a large amount of stranted quota and how that can affect the runtime obtained by the tasks. So reducing the slice size should help, but it will still be a problem in a large system with huge number of CPUs where each CPU claims a slice and does not use it fully.

Regards,
Bharata.

#20 lore raw

Re: [PATCH v3 2/7] sched: accumulate per-cfs_rq cpu usage

In reply to Peter Zijlstra
Quoted 19 lines · Peter Zijlstra
Quoted 18 lines · Paul Turner
Quoted 16 lines · Peter Zijlstra

kernel/sched_fair.c static void yield_task_fair(struct rq *r · line 1181

Quoted 13 lines · Bharata B Rao
kernel/sched_fair.c +13 -0
+static void account_cfs_rq_quota(struct cfs_rq *cfs_rq,
+               unsigned long delta_exec)
+{
+       if (cfs_rq->quota_assigned == RUNTIME_INF)
+               return;
+
+       cfs_rq->quota_used += delta_exec;
+
+       if (cfs_rq->quota_used < cfs_rq->quota_assigned)
+               return;
+
+       cfs_rq->quota_assigned += tg_request_cfs_quota(cfs_rq->tg);
+}

That looks iffy, quota_assigned is only ever incremented and can wrap.

Quoted 6 lines
Quoted 3 lines

This can't advance at a rate faster than ~vruntime and we can't handle wrapping there anyway (fortunately it would take something like 35k years?)

You can't go faster than wall-time, vruntime can actually go a lot faster and can deal with wrapping.

Right -- I hadn't previously noticed the normalization w/ min_vruntime in min_vruntime()

Fortunately the wall_time constraint still holds :)

Quoted 5 lines
Quoted 5 lines
Quoted 4 lines

Why not subtract delta_exec and replenish when <0? That keeps the numbers small.

Quoted 9 lines
Quoted 6 lines

Accounting in the opposite direction allows us to catch-up in subsequent periods when a task exceeds its bandwidth across an interval where we are not able to immediately throttle it (e.g. costly syscall without config_prempt).  Since we'll continue to accrue the execution time in this case it will be effectively pre-charged against the next slice received.

Humm, how so, that's a simply matter of the quota going negative, right?

Then quota is signed and representation of infinite quota is more ambiguous.

#32 lore raw

Re: [PATCH v3 3/7] sched: throttle cfs_rq entities which exceed their local quota

In reply to Peter Zijlstra
Quoted 10 lines · On Thu, 14 Oct 2010 11:12:22 +0200 Peter Zijlstra <[email protected]> wrote:
Quoted 3 lines · KAMEZAWA Hiroyuki

cpu.share and bandwidth control can't be used simultaneously or... is this fair ? I'm not familiar with scheduler but this allows boost this tg. Could you add a brief documentaion of a spec/feature. in the next post ?

Like explained, shares control the proportional distribution of time between groups, bandwidth puts a limit on how much time a group can take. It can cause a group to receive less than its fair share, but never more.

Quoted 8 lines

There is, however, a problem with all this, and that is that all this explicit idling of tasks can lead to a form of priority inversion. Regular preemptive scheduling already suffers from this, but explicitly idling tasks exacerbates the situation.

You basically get to add the longest induced idle time to all your lock hold times.

What is the user-visible difference of the problem between
1) limit share to be very small.
2) use throttole.

If share is used, lock-hodler's priority is boosted ?

Thanks,
-Kame

#39 lore raw

Re: [PATCH v3 3/7] sched: throttle cfs_rq entities which exceed their local quota

In reply to Peter Zijlstra
Quoted 10 lines · Peter Zijlstra
Quoted 3 lines · KAMEZAWA Hiroyuki

cpu.share and bandwidth control can't be used simultaneously or... is this fair ? I'm not familiar with scheduler but this allows boost this tg. Could you add a brief documentaion of a spec/feature. in the next post ?

Like explained, shares control the proportional distribution of time between groups, bandwidth puts a limit on how much time a group can take. It can cause a group to receive less than its fair share, but never more.

Quoted 8 lines

There is, however, a problem with all this, and that is that all this explicit idling of tasks can lead to a form of priority inversion. Regular preemptive scheduling already suffers from this, but explicitly idling tasks exacerbates the situation.

You basically get to add the longest induced idle time to all your lock hold times.

This is a concern (especially for exit starvation, since the task needs to be scheduled for reaping); the way throttling is enacted should help to mitigate the risk / starvation here. When a group exceeds its bandwidth we don't actively force it off the cpu, we only set TIF_RESCHED; this the "enforcement" of throttling until we drop back down through put_prev_task().

This should mean we won't extend a semaphore wait time unless someone explicitly issues something a cond_resched() within it [at which point they are choosing a potentially arbitrary latency delay anyway, although this does expand it relative to the target sched_latency_period].

Quoted 2 lines
maintainer
#33 lore raw

Re: [PATCH v3 3/7] sched: throttle cfs_rq entities which exceed their local quota

In reply to KAMEZAWA Hiroyuki
Quoted 22 lines · KAMEZAWA Hiroyuki
Quoted 10 lines · On Thu, 14 Oct 2010 11:12:22 +0200 Peter Zijlstra <[email protected]> wrote:
Quoted 3 lines · KAMEZAWA Hiroyuki

cpu.share and bandwidth control can't be used simultaneously or... is this fair ? I'm not familiar with scheduler but this allows boost this tg. Could you add a brief documentaion of a spec/feature. in the next post ?

Like explained, shares control the proportional distribution of time between groups, bandwidth puts a limit on how much time a group can take. It can cause a group to receive less than its fair share, but never more.

Quoted 8 lines

There is, however, a problem with all this, and that is that all this explicit idling of tasks can lead to a form of priority inversion. Regular preemptive scheduling already suffers from this, but explicitly idling tasks exacerbates the situation.

You basically get to add the longest induced idle time to all your lock hold times.

Quoted 5 lines

What is the user-visible difference of the problem between
1) limit share to be very small.
2) use throttole.

If share is used, lock-hodler's priority is boosted ?

No, both lead to the same problem, its just that this adds another dimension to it.. and I'm fairly sure people won't realise this until it bites them in the ass.

#34 lore raw

Re: [PATCH v3 3/7] sched: throttle cfs_rq entities which exceed their local quota

Quoted 27 lines · On Thu, 14 Oct 2010 11:59:55 +0200 Peter Zijlstra <[email protected]> wrote:
Quoted 26 lines · KAMEZAWA Hiroyuki
Quoted 10 lines · On Thu, 14 Oct 2010 11:12:22 +0200 Peter Zijlstra <[email protected]> wrote:
Quoted 3 lines · KAMEZAWA Hiroyuki

cpu.share and bandwidth control can't be used simultaneously or... is this fair ? I'm not familiar with scheduler but this allows boost this tg. Could you add a brief documentaion of a spec/feature. in the next post ?

Like explained, shares control the proportional distribution of time between groups, bandwidth puts a limit on how much time a group can take. It can cause a group to receive less than its fair share, but never more.

Quoted 8 lines

There is, however, a problem with all this, and that is that all this explicit idling of tasks can lead to a form of priority inversion. Regular preemptive scheduling already suffers from this, but explicitly idling tasks exacerbates the situation.

You basically get to add the longest induced idle time to all your lock hold times.

What is the user-visible difference of the problem between
1) limit share to be very small.
2) use throttole.

Quoted 6 lines
Quoted 1 line

If share is used, lock-hodler's priority is boosted ?

No, both lead to the same problem, its just that this adds another dimension to it.. and I'm fairly sure people won't realise this until it bites them in the ass.

Hmm, them, existing problem but this add a new pitfall.

What's your recomendation to make progess on this work ?

I think 1st step will be..
- explain the problem of priority inversion in cgroup+cfs documenation with !!CAUTION!!

I'm sorry I'm not sure there have been trials for fixing priority inversion in the linux scheduler development.

Explaining my motivation, a user of this feature on my customer is virtual machine rental service. So, some fuctionality as
"When vcpu holds spinlock in kernel, please don't sleep.." will be nice. Is there patch already ?

Thanks,
-Kame

#35 lore raw

Re: [PATCH v3 3/7] sched: throttle cfs_rq entities which exceed their local quota

Quoted 44 lines · KAMEZAWA Hiroyuki
Quoted 27 lines · On Thu, 14 Oct 2010 11:59:55 +0200 Peter Zijlstra <[email protected]> wrote:
Quoted 26 lines · KAMEZAWA Hiroyuki
Quoted 10 lines · On Thu, 14 Oct 2010 11:12:22 +0200 Peter Zijlstra <[email protected]> wrote:
Quoted 3 lines · KAMEZAWA Hiroyuki

cpu.share and bandwidth control can't be used simultaneously or... is this fair ? I'm not familiar with scheduler but this allows boost this tg. Could you add a brief documentaion of a spec/feature. in the next post ?

Like explained, shares control the proportional distribution of time between groups, bandwidth puts a limit on how much time a group can take. It can cause a group to receive less than its fair share, but never more.

Quoted 8 lines

There is, however, a problem with all this, and that is that all this explicit idling of tasks can lead to a form of priority inversion. Regular preemptive scheduling already suffers from this, but explicitly idling tasks exacerbates the situation.

You basically get to add the longest induced idle time to all your lock hold times.

What is the user-visible difference of the problem between
  1) limit share to be very small.
  2) use throttole.

Quoted 6 lines
Quoted 1 line

If share is used, lock-hodler's priority is boosted ?

No, both lead to the same problem, its just that this adds another dimension to it.. and I'm fairly sure people won't realise this until it bites them in the ass.

Hmm, them, existing problem but this add a new pitfall.

What's your recomendation to make progess on this work ?

I think 1st step will be..
- explain the problem of priority inversion in cgroup+cfs documenation with !!CAUTION!!

Quoted 8 lines

I'm sorry I'm not sure there have been trials for fixing priority inversion in the linux scheduler development.

Explaining my motivation, a user of this feature on my customer is virtual machine rental service. So, some fuctionality as
"When vcpu holds spinlock in kernel, please don't sleep.." will be nice. Is there patch already ?

Per above:

When a group exceeds its bandwidth we don't actively force it off the cpu, we only set TIF_RESCHED; we won't process the throttling until we drop back down to userspace and handle the flag.

This means: we'll never throttle a spinlock

We'll also only throttle a sleepable lock (that doesn't disable preemption) when they voluntarily reschedule without releasing the lock, at which point they've chosen to open themselves to an arbitrary latency period anyway.

**

The case of a guest cpu holding spinlocks is part of a much larger rabbit hole that is spinlock enlightenment which should occur via pvops/etc interaction. The sane thing for this to do would be to (at least) preempt_disable() at which point the vcpu will be protected from throttling.

This seems somewhat orthogonal to this patchset however.

**

Agreed that PI inversion across threads and across vcpus are rather sickly beasts; especially given how bare the curtains are on the first case (which the second can only really build upon).

Quoted 16 lines

Thanks,
-Kame

maintainer
#38 lore raw

Re: [PATCH v3 3/7] sched: throttle cfs_rq entities which exceed their local quota

In reply to KAMEZAWA Hiroyuki
Quoted 6 lines · KAMEZAWA Hiroyuki
Quoted 4 lines

No, both lead to the same problem, its just that this adds another dimension to it.. and I'm fairly sure people won't realise this until it bites them in the ass.

Hmm, them, existing problem but this add a new pitfall.

Quoted 8 lines

What's your recomendation to make progess on this work ?

I think 1st step will be..
- explain the problem of priority inversion in cgroup+cfs documenation with !!CAUTION!!

I'm sorry I'm not sure there have been trials for fixing priority inversion in the linux scheduler development.

There's kernel/rtmutex.c which is a mutex implementation with classic PI that works for SCHED_FIFO/RR.

Thomas and I have been planning of completely rewriting PI support in the kernel for some time but haven't gotten around to actually doing it.

The goal is to implement a variant of the Proxy Execution Protocol (close to what gets described here in:
http://www.artist-embedded.org/docs/Events/2010/OSPERT/OSPERT2010-Proceedings.pdf
page 16, Timeslice donation in component based systems).

One of the advantages of PEP is that it works across all scheduling policies, including proportional fair share schedulers.

It also deals correctly with all PI issues for deadline based schedulers (correctly handles deadline as well as bandwidth inheritance).

Quoted 4 lines

Explaining my motivation, a user of this feature on my customer is virtual machine rental service. So, some fuctionality as
"When vcpu holds spinlock in kernel, please don't sleep.." will be nice. Is there patch already ?

Well, clearly you cannot sleep while holding a spinlock.. sleeping while holding a mutex/semaphore is allowed however, but even when you'd have full PI over all kernel lock (as -rt has), that's not enough, you have exactly the same problem with all userspace locks.

maintainer
#36 lore raw

Re: [PATCH v3 3/7] sched: throttle cfs_rq entities which exceed their local quota

In reply to Paul Turner
Quoted 2 lines · Paul Turner
Quoted 2 lines

"When vcpu holds spinlock in kernel, please don't sleep.." will be nice. Is there patch already ?

Oh you're talking about the guest spinlock crap? I don't particularly care about that.. that's a virt problem you see ;-)

#5 lore raw

Re: [PATCH v3 1/7] sched: introduce primitives to account for CFS bandwidth tracking

In reply to Peter Zijlstra
Quoted 24 lines · Peter Zijlstra
Quoted 22 lines · Balbir Singh
Quoted 9 lines
kernel/sched.c +6 -2
-static void start_rt_bandwidth(struct rt_bandwidth *rt_b)
+static void start_bandwidth_timer(struct hrtimer *period_timer, ktime_t period)
 {
-	ktime_t now;
+	unsigned long delta;
+	ktime_t soft, hard, now;
+
+	for (;;) {
+		if (hrtimer_active(period_timer))

kernel/sched.c static inline int rt_bandwidth_enabled(v · line 211

Quoted 10 lines
kernel/sched.c +9 -0
+			break;
 
+		now = hrtimer_cb_get_time(period_timer);
+		hrtimer_forward(period_timer, now, period);
+
+		soft = hrtimer_get_softexpires(period_timer);
+		hard = hrtimer_get_expires(period_timer);
+		delta = ktime_to_ns(ktime_sub(hard, soft));
+		__hrtimer_start_range_ns(period_timer, soft, delta,
+					 HRTIMER_MODE_ABS_PINNED, 0);

This code can be replaced with

Quoted 6 lines
Quoted 3 lines

hrtimer_start_expires(period_timer, HRTIMER_MODE_ABS_PINNED) if we don't care about wakeup_softirq, is there a reason we prefer to keep wakeup as 0?

You cannot do wakeups while holding the rq->lock, can you? :-)

:-) Yes, given that we wakeup softirq only for the current CPU. There is scope for some code reuse anyway, I'll see if I can send a patch.

Quoted 91 lines
Quoted 14 lines
Quoted 14 lines
kernel/sched.c +12 -0
+	}
+}
 
 
+static enum hrtimer_restart sched_cfs_period_timer(struct hrtimer *timer)
+{
+	struct cfs_bandwidth *cfs_b =
+		container_of(timer, struct cfs_bandwidth, period_timer);
+	ktime_t now;
+	int overrun;
+	int idle = 0;
+
+	for (;;) {
+		now = hrtimer_cb_get_time(timer);
Quoted 9 lines

kernel/sched.c struct cfs_rq { · line 410

Quoted 4 lines
kernel/sched.c +4 -0
+		overrun = hrtimer_forward(timer, now, cfs_b->period);
+
+		if (!overrun)
+			break;

What is the significance of overrun? overrun is set when delta > interval. The logic seems to be that hrtimer is forwarded in steps of cfs_b->period till we reach the desired time.

Overrun is the number of periods missed. The goal is to increment the quota for each period, if the timer is late 3 periods, we still need to increment it 3 times, that's what overrun does.

Quoted 7 lines
Quoted 6 lines
kernel/sched.c +6 -0
+
+		idle = do_sched_cfs_period_timer(cfs_b, overrun);
+	}
+
+	return idle ? HRTIMER_NORESTART : HRTIMER_RESTART;
+}
Quoted 10 lines

kernel/sched.c struct cfs_rq { · line 445

Quoted 7 lines
kernel/sched.c +7 -0
+static void start_cfs_bandwidth(struct cfs_bandwidth *cfs_b)
+{
+	if (cfs_b->quota == RUNTIME_INF)
+		return;
+
+	if (hrtimer_active(&cfs_b->period_timer))
+		return;

Why the double check, start_bandwidth_timer also checks this. Is it to avoid doing the check under cfs_b->lock?

Basically..

Quoted 20 lines
Quoted 20 lines
kernel/sched.c +19 -0
+
+	raw_spin_lock(&cfs_b->lock);
+	start_bandwidth_timer(&cfs_b->period_timer, cfs_b->period);
+	raw_spin_unlock(&cfs_b->lock);
+}
+
 
+#ifdef CONFIG_CFS_BANDWIDTH
+static int tg_set_cfs_bandwidth(struct task_group *tg, u64 period, u64 quota)
+{
+	int i;
+	static DEFINE_MUTEX(mutex);
+
+	if (tg == &init_task_group)
+		return -EINVAL;
+
+	if (!period)
+		return -EINVAL;
+
+	/*
Quoted 8 lines

kernel/sched.c static u64 cpu_shares_read_u64(struct cg · line 8903

Quoted 6 lines
kernel/sched.c +6 -0
+	 * Ensure we have at least one tick of bandwidth every period.  This is
+	 * to prevent reaching a state of large arrears when throttled via
+	 * entity_tick() resulting in prolonged exit starvation.
+	 */
+	if (NS_TO_JIFFIES(quota) < 1)
+		return -EINVAL;

I hope we document this in the Documentation :)

/me went and looked up arrears in a dictionary and wonders why 'debt' wasn't good enough.

Quoted 10 lines

kernel/sched.c static u64 cpu_shares_read_u64(struct cg · line 8911

Quoted 8 lines
kernel/sched.c +8 -0
+
+	mutex_lock(&mutex);
+	raw_spin_lock_irq(&tg->cfs_bandwidth.lock);
+	tg->cfs_bandwidth.period = ns_to_ktime(period);
+	tg->cfs_bandwidth.runtime = tg->cfs_bandwidth.quota = quota;
+	raw_spin_unlock_irq(&tg->cfs_bandwidth.lock);
+
+	for_each_possible_cpu(i) {

Why not for_each_online_cpu()?

Quoted 3 lines

Probably could be cured with a hotplug handler, but then you need to track more state iirc.

What more state? If a CPU is offline, we never get to it, do we? I think we need to do just an init and destroy - no?

Quoted 12 lines
Quoted 11 lines
Quoted 11 lines
kernel/sched.c +11 -0
+		struct cfs_rq *cfs_rq = tg->cfs_rq[i];
+		struct rq *rq = rq_of(cfs_rq);
+
+		raw_spin_lock_irq(&rq->lock);
+		init_cfs_rq_quota(cfs_rq);
+		raw_spin_unlock_irq(&rq->lock);
+	}
+	mutex_unlock(&mutex);
+
+	return 0;
+}
Signature · 2 lines
	Three Cheers,
	Balbir
maintainer
#6 lore raw

Re: [PATCH v3 1/7] sched: introduce primitives to account for CFS bandwidth tracking

Quoted 10 lines · Balbir Singh
Quoted 7 lines
Quoted 4 lines

hrtimer_start_expires(period_timer, HRTIMER_MODE_ABS_PINNED) if we don't care about wakeup_softirq, is there a reason we prefer to keep wakeup as 0?

You cannot do wakeups while holding the rq->lock, can you? :-)

:-) Yes, given that we wakeup softirq only for the current CPU. There is scope for some code reuse anyway, I'll see if I can send a patch.

Well, both Thomas and I would like hrtimer_start() and friends to return -ETIME in this case. But that means changing all callers to cope with that, and sweeping the tree to make that happen is like lots of work.

#37 lore raw

Re: [PATCH v3 3/7] sched: throttle cfs_rq entities which exceed their local quota

In reply to Peter Zijlstra
Quoted 5 lines · On Thu, 14 Oct 2010 12:41:44 +0200 Peter Zijlstra <[email protected]> wrote:
Quoted 2 lines · Paul Turner
Quoted 2 lines

"When vcpu holds spinlock in kernel, please don't sleep.." will be nice. Is there patch already ?

Oh you're talking about the guest spinlock crap?

yes ;)

Quoted 1 line

I don't particularly care about that.. that's a virt problem you see ;-)

Hmm. AFAIK, all qemu's thread will be under a cgroup. So, I'll be happy if a vcpu is on a loop to wait for spinlock yields immediately...But I'm not famliar with this area, either. Thanks.

-Kame

#41 lore raw

Re: [PATCH v3 4/7] sched: unthrottle cfs_rq(s) who ran out of quota at period refresh

In reply to Bharata B Rao
Quoted 11 lines · Bharata B Rao

sched: unthrottle cfs_rq(s) who ran out of quota at period refresh

From: Paul Turner <[email protected]>

At the start of a new period there are several actions we must take:
- Refresh global bandwidth pool
- Unthrottle entities who ran out of quota as refreshed bandwidth permits

Unthrottled entities have the cfs_rq->throttled flag set and are re-enqueued into the cfs entity hierarchy.

Am I reading this right?

Quoted 58 lines

sched_rt_period_mask() is refactored slightly into sched_bw_period_mask() since it is now shared by both cfs and rt bandwidth period timers.

The !CONFIG_RT_GROUP_SCHED && CONFIG_SMP case has been collapsed to use rd->span instead of cpu_online_mask since I think that was incorrect before (don't want to hit cpu's outside of your root_domain for RT bandwidth).

---
 kernel/sched.c      |   16 ++++++++++++
 kernel/sched_fair.c |   68 +++++++++++++++++++++++++++++++++++++++++++++++++++-
 kernel/sched_rt.c   |   19 --------------
 3 files changed, 84 insertions(+), 19 deletions(-)
kernel/sched.c +16 -0
@@ -1565,6 +1565,8 @@ static int tg_nop(struct task_group *tg,
 }
 #endif
 
+static inline const struct cpumask *sched_bw_period_mask(void);
+
 #ifdef CONFIG_SMP
 /* Used instead of source_load when we know the type == 0 */
 static unsigned long weighted_cpuload(const int cpu)
@@ -1933,6 +1935,18 @@ static inline void __set_task_cpu(struct
 
 static const struct sched_class rt_sched_class;
 
+#ifdef CONFIG_SMP
+static inline const struct cpumask *sched_bw_period_mask(void)
+{
+	return cpu_rq(smp_processor_id())->rd->span;
+}
+#else
+static inline const struct cpumask *sched_bw_period_mask(void)
+{
+	return cpu_online_mask;
+}
+#endif
+
 #ifdef CONFIG_CFS_BANDWIDTH
 /*
  * default period for cfs group bandwidth.
@@ -8937,6 +8951,8 @@ static int tg_set_cfs_bandwidth(struct t
 
 		raw_spin_lock_irq(&rq->lock);
 		init_cfs_rq_quota(cfs_rq);
+		if (cfs_rq_throttled(cfs_rq))
+			unthrottle_cfs_rq(cfs_rq);
 		raw_spin_unlock_irq(&rq->lock);
 	}
 	mutex_unlock(&mutex);

kernel/sched_fair.c find_matching_se(struct sched_entity **s · line 273

Quoted 6 lines
kernel/sched_fair.c +3 -0
@@ -268,6 +268,13 @@ find_matching_se(struct sched_entity **s
 #endif	/* CONFIG_FAIR_GROUP_SCHED */
 
 #ifdef CONFIG_CFS_BANDWIDTH
+static inline
+struct cfs_rq *cfs_bandwidth_cfs_rq(struct cfs_bandwidth *cfs_b, int cpu)
+{

Nit pick, but I'd call this function cfs_bandwidth_cfs_cpu_rq

Quoted 15 lines
kernel/sched_fair.c +8 -0
+	return container_of(cfs_b, struct task_group,
+			cfs_bandwidth)->cfs_rq[cpu];
+}
+
 static inline struct cfs_bandwidth *tg_cfs_bandwidth(struct task_group *tg)
 {
 	return &tg->cfs_bandwidth;
@@ -1219,6 +1226,29 @@ out_throttled:
 	cfs_rq->throttled = 1;
 }
 
+static void unthrottle_cfs_rq(struct cfs_rq *cfs_rq)
+{
+	struct sched_entity *se;
+	struct rq *rq = rq_of(cfs_rq);

kernel/sched_fair.c out_throttled: · line 1242

Quoted 10 lines
kernel/sched_fair.c +10 -0
+
+	se = cfs_rq->tg->se[cpu_of(rq_of(cfs_rq))];
+
+	cfs_rq->throttled = 0;
+	for_each_sched_entity(se) {
+		if (se->on_rq)
+			break;
+
+		cfs_rq = cfs_rq_of(se);
+		enqueue_entity(cfs_rq, se, ENQUEUE_WAKEUP);

Should we really enqueue with ENQUEUE_WAKEUP - the task throttled, not slept.

Quoted 13 lines
kernel/sched_fair.c +9 -0
+		if (cfs_rq_throttled(cfs_rq))
+			break;
+	}
+
+	/* determine whether we need to wake up potentally idle cpu */
+	if (rq->curr == rq->idle && rq->cfs.nr_running)
+		resched_task(rq->curr);
+}
+
 static void account_cfs_rq_quota(struct cfs_rq *cfs_rq,
 		unsigned long delta_exec)
 {

kernel/sched_fair.c static void account_cfs_rq_quota(struct · line 1279

Quoted 10 lines
kernel/sched_fair.c +6 -1
@@ -1241,8 +1271,44 @@ static void account_cfs_rq_quota(struct 
 
 static int do_sched_cfs_period_timer(struct cfs_bandwidth *cfs_b, int overrun)
 {
-	return 1;
+	int i, idle = 1;
+	u64 delta;
+	const struct cpumask *span;
+
+	if (cfs_b->quota == RUNTIME_INF)
+		return 1;

I am afraid I don't understand how return codes are being used here. idle is set to 1 if there are no running tasks across all CPUs. Why do we return a 1 from here?

Quoted 77 lines
kernel/sched_fair.c +31 -0
+
+	/* reset group quota */
+	raw_spin_lock(&cfs_b->lock);
+	cfs_b->runtime = cfs_b->quota;
+	raw_spin_unlock(&cfs_b->lock);
+
+	span = sched_bw_period_mask();
+	for_each_cpu(i, span) {
+		struct rq *rq = cpu_rq(i);
+		struct cfs_rq *cfs_rq = cfs_bandwidth_cfs_rq(cfs_b, i);
+
+		if (cfs_rq->nr_running)
+			idle = 0;
+
+		if (!cfs_rq_throttled(cfs_rq))
+			continue;
+
+		delta = tg_request_cfs_quota(cfs_rq->tg);
+
+		if (delta) {
+			raw_spin_lock(&rq->lock);
+			cfs_rq->quota_assigned += delta;
+
+			if (cfs_rq->quota_used < cfs_rq->quota_assigned)
+				unthrottle_cfs_rq(cfs_rq);
+			raw_spin_unlock(&rq->lock);
+		}
+	}
+
+	return idle;
 }
+
 #endif
 
 #ifdef CONFIG_SMP
kernel/sched_rt.c +1 -18
@@ -241,18 +241,6 @@ static int rt_se_boosted(struct sched_rt
 	return p->prio != p->normal_prio;
 }
 
-#ifdef CONFIG_SMP
-static inline const struct cpumask *sched_rt_period_mask(void)
-{
-	return cpu_rq(smp_processor_id())->rd->span;
-}
-#else
-static inline const struct cpumask *sched_rt_period_mask(void)
-{
-	return cpu_online_mask;
-}
-#endif
-
 static inline
 struct rt_rq *sched_rt_period_rt_rq(struct rt_bandwidth *rt_b, int cpu)
 {
@@ -302,11 +290,6 @@ static inline int rt_rq_throttled(struct
 	return rt_rq->rt_throttled;
 }
 
-static inline const struct cpumask *sched_rt_period_mask(void)
-{
-	return cpu_online_mask;
-}
-
 static inline
 struct rt_rq *sched_rt_period_rt_rq(struct rt_bandwidth *rt_b, int cpu)
 {
@@ -524,7 +507,7 @@ static int do_sched_rt_period_timer(stru
 	if (!rt_bandwidth_enabled() || rt_b->rt_runtime == RUNTIME_INF)
 		return 1;
 
-	span = sched_rt_period_mask();
+	span = sched_bw_period_mask();
 	for_each_cpu(i, span) {
 		int enqueue = 0;
 		struct rt_rq *rt_rq = sched_rt_period_rt_rq(rt_b, i);
Signature · 2 lines
	Three Cheers,
	Balbir
#49 lore raw
In reply to Bharata B Rao
Quoted 11 lines · Bharata B Rao

Hi,

Its been a while since we posted CPS hard limits (aka CFS bandwidth control now) patches, hence a quick recap first:

- I have been working on CFS hard limits since last year and have posted a few versions of the same (last post: http://lkml.org/lkml/2010/1/5/44)
- Paul Turner and Nikhil Rao meanwhile started working on CFS bandwidth control and have posted a couple of versions.
(last post v2: http://lwn.net/Articles/385055/)

Hi, All

I tried it, it works very good! It adds a very useful feature.
It is very helpful for virtualization or cloud-computing I think. I hope the next version patchset of it will be sent and get merged soon.

When I tested it, my box became dead several times, infrequently, and I don't know how to reproduce it, but next steps may help to reproduce it:

# mount -t cgroup -o cpu xxx /mnt
# cd /mnt
# mkdir test
# cd test
# echo 5000000 > cpu.cfs_period_us
# echo 1000000 > cpu.cfs_quota_us
# cat /dev/zero > /dev/null &
# echo $! > tasks
# #make the system busy, browse websites and open many tabs in your browser etc
# #but do NOT do things important.
# #after some time, the system may dead. (can not respond even you type AltSysrqC)

Thank you all
Lai

#50 lore raw
Quoted 22 lines · Lai Jiangshan
Quoted 11 lines · Bharata B Rao

Hi,

Its been a while since we posted CPS hard limits (aka CFS bandwidth control now) patches, hence a quick recap first:

- I have been working on CFS hard limits since last year and have posted a few versions of the same (last post: http://lkml.org/lkml/2010/1/5/44)
- Paul Turner and Nikhil Rao meanwhile started working on CFS bandwidth control and have posted a couple of versions.
(last post v2: http://lwn.net/Articles/385055/)

Hi, All

I tried it, it works very good! It adds a very useful feature.
It is very helpful for virtualization or cloud-computing I think. I hope the next version patchset of it will be sent and get merged soon.

When I tested it, my box became dead several times, infrequently, and I don't know how to reproduce it, but next steps may help to reproduce it:

Quoted 12 lines
# mount -t cgroup -o cpu xxx /mnt
# cd /mnt
# mkdir test
# cd test
# echo 5000000 > cpu.cfs_period_us
# echo 1000000 > cpu.cfs_quota_us
# cat /dev/zero > /dev/null &
# echo $! > tasks
# #make the system busy, browse websites and open many tabs in your browser etc
# #but do NOT do things important.
# #after some time, the system may dead. (can not respond even you type AltSysrqC)

Hi Lai, Thanks for testing the patches. I haven't seen this behaviour still. But will try out the steps you mention and see if I can reproduce it here. Meanwhile if you find more information about the problem, do let us know.

Regards,
Bharata.

#7 lore raw

Re: [PATCH v3 1/7] sched: introduce primitives to account for CFS bandwidth tracking

In reply to Balbir Singh
Quoted 37 lines · Balbir Singh
Quoted 35 lines · Peter Zijlstra
Quoted 12 lines · Balbir Singh
Quoted 12 lines
kernel/sched.c +12 -0
+static int tg_set_cfs_bandwidth(struct task_group *tg, u64 period, u64 quota)
+{
+	int i;
+	static DEFINE_MUTEX(mutex);
+
+	if (tg == &init_task_group)
+		return -EINVAL;
+
+	if (!period)
+		return -EINVAL;
+
+	/*
Quoted 8 lines

kernel/sched.c static u64 cpu_shares_read_u64(struct cg · line 8903

Quoted 6 lines
kernel/sched.c +6 -0
+	 * Ensure we have at least one tick of bandwidth every period.  This is
+	 * to prevent reaching a state of large arrears when throttled via
+	 * entity_tick() resulting in prolonged exit starvation.
+	 */
+	if (NS_TO_JIFFIES(quota) < 1)
+		return -EINVAL;

I hope we document this in the Documentation :)

/me went and looked up arrears in a dictionary and wonders why 'debt' wasn't good enough.

Quoted 10 lines

kernel/sched.c static u64 cpu_shares_read_u64(struct cg · line 8911

Quoted 8 lines
kernel/sched.c +8 -0
+
+	mutex_lock(&mutex);
+	raw_spin_lock_irq(&tg->cfs_bandwidth.lock);
+	tg->cfs_bandwidth.period = ns_to_ktime(period);
+	tg->cfs_bandwidth.runtime = tg->cfs_bandwidth.quota = quota;
+	raw_spin_unlock_irq(&tg->cfs_bandwidth.lock);
+
+	for_each_possible_cpu(i) {

Why not for_each_online_cpu()?

Quoted 6 lines
Quoted 3 lines

Probably could be cured with a hotplug handler, but then you need to track more state iirc.

What more state? If a CPU is offline, we never get to it, do we? I think we need to do just an init and destroy - no?

Here we essentially initialize tg->cfs_rq[cpu]->quota_used{assigned} for all CPUs. Given that we don't destroy tg->cfs_rq[cpu] and tg->se->[cpu] when a CPU goes offline, is it really worth to have a notifier to just initialize quota_used and quota_assigned when a CPU comes online ?

Regards,
Bharata.

Quoted 17 lines
Quoted 13 lines
Quoted 12 lines
Quoted 12 lines
kernel/sched.c +11 -0
+		struct cfs_rq *cfs_rq = tg->cfs_rq[i];
+		struct rq *rq = rq_of(cfs_rq);
+
+		raw_spin_lock_irq(&rq->lock);
+		init_cfs_rq_quota(cfs_rq);
+		raw_spin_unlock_irq(&rq->lock);
+	}
+	mutex_unlock(&mutex);
+
+	return 0;
+}
Signature · 2 lines
	Three Cheers,
	Balbir
#42 lore raw

Re: [PATCH v3 4/7] sched: unthrottle cfs_rq(s) who ran out of quota at period refresh

In reply to Balbir Singh

Sorry Balbir, didn't realize that we haven't replied to these comments from you.

Quoted 10 lines · Balbir Singh
Quoted 8 lines · Bharata B Rao

sched: unthrottle cfs_rq(s) who ran out of quota at period refresh

From: Paul Turner <[email protected]>

At the start of a new period there are several actions we must take:
- Refresh global bandwidth pool
- Unthrottle entities who ran out of quota as refreshed bandwidth permits

Quoted 5 lines
Quoted 3 lines

Unthrottled entities have the cfs_rq->throttled flag set and are re-enqueued into the cfs entity hierarchy.

Am I reading this right?

Yes, Needs to be corrected. Thanks.

Quoted 88 lines
Quoted 59 lines

sched_rt_period_mask() is refactored slightly into sched_bw_period_mask() since it is now shared by both cfs and rt bandwidth period timers.

The !CONFIG_RT_GROUP_SCHED && CONFIG_SMP case has been collapsed to use rd->span instead of cpu_online_mask since I think that was incorrect before (don't want to hit cpu's outside of your root_domain for RT bandwidth).

---
 kernel/sched.c      |   16 ++++++++++++
 kernel/sched_fair.c |   68 +++++++++++++++++++++++++++++++++++++++++++++++++++-
 kernel/sched_rt.c   |   19 --------------
 3 files changed, 84 insertions(+), 19 deletions(-)
kernel/sched.c +16 -0
@@ -1565,6 +1565,8 @@ static int tg_nop(struct task_group *tg,
 }
 #endif
 
+static inline const struct cpumask *sched_bw_period_mask(void);
+
 #ifdef CONFIG_SMP
 /* Used instead of source_load when we know the type == 0 */
 static unsigned long weighted_cpuload(const int cpu)
@@ -1933,6 +1935,18 @@ static inline void __set_task_cpu(struct
 
 static const struct sched_class rt_sched_class;
 
+#ifdef CONFIG_SMP
+static inline const struct cpumask *sched_bw_period_mask(void)
+{
+	return cpu_rq(smp_processor_id())->rd->span;
+}
+#else
+static inline const struct cpumask *sched_bw_period_mask(void)
+{
+	return cpu_online_mask;
+}
+#endif
+
 #ifdef CONFIG_CFS_BANDWIDTH
 /*
  * default period for cfs group bandwidth.
@@ -8937,6 +8951,8 @@ static int tg_set_cfs_bandwidth(struct t
 
 		raw_spin_lock_irq(&rq->lock);
 		init_cfs_rq_quota(cfs_rq);
+		if (cfs_rq_throttled(cfs_rq))
+			unthrottle_cfs_rq(cfs_rq);
 		raw_spin_unlock_irq(&rq->lock);
 	}
 	mutex_unlock(&mutex);

kernel/sched_fair.c find_matching_se(struct sched_entity **s · line 273

Quoted 6 lines
kernel/sched_fair.c +3 -0
@@ -268,6 +268,13 @@ find_matching_se(struct sched_entity **s
 #endif	/* CONFIG_FAIR_GROUP_SCHED */
 
 #ifdef CONFIG_CFS_BANDWIDTH
+static inline
+struct cfs_rq *cfs_bandwidth_cfs_rq(struct cfs_bandwidth *cfs_b, int cpu)
+{

Nit pick, but I'd call this function cfs_bandwidth_cfs_cpu_rq

Quoted 20 lines
kernel/sched_fair.c +13 -0
+	return container_of(cfs_b, struct task_group,
+			cfs_bandwidth)->cfs_rq[cpu];
+}
+
 static inline struct cfs_bandwidth *tg_cfs_bandwidth(struct task_group *tg)
 {
 	return &tg->cfs_bandwidth;
@@ -1219,6 +1226,29 @@ out_throttled:
 	cfs_rq->throttled = 1;
 }
 
+static void unthrottle_cfs_rq(struct cfs_rq *cfs_rq)
+{
+	struct sched_entity *se;
+	struct rq *rq = rq_of(cfs_rq);
+
+	se = cfs_rq->tg->se[cpu_of(rq_of(cfs_rq))];
+
+	cfs_rq->throttled = 0;
+	for_each_sched_entity(se) {
Quoted 8 lines

kernel/sched_fair.c out_throttled: · line 1242

Quoted 5 lines
kernel/sched_fair.c +5 -0
+		if (se->on_rq)
+			break;
+
+		cfs_rq = cfs_rq_of(se);
+		enqueue_entity(cfs_rq, se, ENQUEUE_WAKEUP);

Should we really enqueue with ENQUEUE_WAKEUP - the task throttled, not slept.

Yes, but the actions are quite similar. In both the cases, they go off the runqueque and get enqueued back. I see two (side)effects of using DEQUEUE_SLEEP during dequeue and ENQUEUE_WAKEUP during enqueue:

- vruntime normalization isn't done for throttled entities. This should be fine since they don't get pulled around when throttled.
- vruntime of throttled entities are re-calculated during unthrottling(enqueue). This will ensure that throttled entities don't get undue vruntime-advantage when they are enqueued back.

This is my understanding. I would request Paul to comment here.

Quoted 15 lines
Quoted 15 lines
kernel/sched_fair.c +9 -0
+		if (cfs_rq_throttled(cfs_rq))
+			break;
+	}
+
+	/* determine whether we need to wake up potentally idle cpu */
+	if (rq->curr == rq->idle && rq->cfs.nr_running)
+		resched_task(rq->curr);
+}
+
 static void account_cfs_rq_quota(struct cfs_rq *cfs_rq,
 		unsigned long delta_exec)
 {
@@ -1241,8 +1271,44 @@ static void account_cfs_rq_quota(struct 
 
Quoted 13 lines

kernel/sched_fair.c static void account_cfs_rq_quota(struct · line 1279

Quoted 9 lines
kernel/sched_fair.c +6 -1
 static int do_sched_cfs_period_timer(struct cfs_bandwidth *cfs_b, int overrun)
 {
-	return 1;
+	int i, idle = 1;
+	u64 delta;
+	const struct cpumask *span;
+
+	if (cfs_b->quota == RUNTIME_INF)
+		return 1;

I am afraid I don't understand how return codes are being used here. idle is set to 1 if there are no running tasks across all CPUs. Why do we return a 1 from here?

Remember we are in hrtimer handler here, returning 1 will ensure that hrtimer isn't restarted. So we don't restart the timer for a group that isn't bandwidth constrained.

Regards,
Bharata.