CFS Bandwidth Control
Subsystems (2)
v2 cover CFS Bandwidth Control
Hi all,
Please find attached v2 of our proposed approach for bandwidth provisioning under CFS. Bharata's original RFC motivating discussion on this topic can be found at: http://lkml.org/lkml/2009/6/4/24
This is an evolution of our previous posting: http://lkml.org/lkml/2010/2/12/393
The improvements herein are incremental: hierarchal task tracking for better load-balance under throttle conditions, statistics export for decision guidance in user-space control systems, minor bugs fixed, and some code clean-up.
The skeleton of our approach is as follows:
- As above we maintain a global pool, per-tg, pool of unassigned quota. On it we track the bandwidth period, quota per period, and runtime remaining in the current period. As bandwidth is used within a period it is decremented from runtime. Runtime is currently synchronized using a spinlock, in the current implementation there's no reason this couldn't be done using atomic ops instead however the spinlock allows for a little more flexibility in experimentation with other schemes.
- When a cfs_rq participating in a bandwidth constrained task_group executes it acquires time in sysctl_sched_cfs_bandwidth_slice (default currently 10ms) size chunks from the global pool, this synchronizes under rq->lock and is part of the update_curr path.
- Throttled entities are dequeued immediately. Throttled entities are gated from participating in the tree at the {enqueue, dequeue}_entity level.
More details on the motivation and approach, as well as performance benchmark results can be found in the original posting.
One caveat that bears discussion is that this leads to an alternate specification of bandwidth versus the sched_rt case. The defined bandwidth becomes an absolute quantifier relative to the period and is agnostic of allowed cpus.
Open-questions:
- Is there any value in having the slice be tunable at the task-group level?
- I suspect 5ms may be a better default slice value, however I have not had the opportunity to verify this yet. There's also room for some dynamic range here.
Acknowledgements:
We would like to thank Bharata B Rao and Dhaval Giani for discussion and their original proposal, many elements in this patchset are directly inspired by their original posting. Bharata has also been integral in the preparation of this second version, providing valuable feedback and review.
Ken Chen also provided early review and comments.
Thanks,
- Paul and Nikhil
---
Nikhil Rao (1):
sched: add exports tracking cfs bandwidth control statistics
Paul Turner (5):
sched: introduce primitives to account for CFS bandwidth tracking
sched: accumulate per-cfs_rq cpu usage
sched: throttle cfs_rq entities which exceed their local quota
sched: unthrottle cfs_rq(s) who ran out of quota at period refresh
sched: hierarchical task accounting for FAIR_GROUP_SCHED
include/linux/sched.h | 4 + init/Kconfig | 9 + kernel/sched.c | 347 +++++++++++++++++++++++++++++++++++++++++++++---- kernel/sched_fair.c | 240 +++++++++++++++++++++++++++++++++- kernel/sched_rt.c | 24 +-- kernel/sysctl.c | 10 + 6 files changed, 585 insertions(+), 49 deletions(-)
PATCH v2 1/6 sched: introduce primitives to account for CFS bandwidth tracking
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
@@ -597,6 +597,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_rq *cfs_rq, struct sched_entity *se)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)
@@ -1144,6 +1147,13 @@ static void yield_task_fair(struct rq *rq) 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)
PATCH v2 2/6 sched: accumulate per-cfs_rq cpu usage
In reply to Paul TurnerIntroduce 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(+), 0 deletions(-)
include/linux/sched.h +4 -0
@@ -1903,6 +1903,10 @@ int sched_rt_handler(struct ctl_table *table, int write, 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
@@ -1912,6 +1912,19 @@ static const struct sched_class rt_sched_class;* 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
@@ -354,6 +354,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",
PATCH v2 3/6 sched: throttle cfs_rq entities which exceed their local quota
In reply to Paul TurnerIn 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 | 62 +++++++++++++++++++++++++++++++++++++++++++++++---- 2 files changed, 68 insertions(+), 6 deletions(-)
kernel/sched.c +11 -1
@@ -422,6 +422,7 @@ struct cfs_rq {#endif #ifdef CONFIG_CFS_BANDWIDTH u64 quota_assigned, quota_used; +int throttled;#endif #endif };
@@ -1647,6 +1648,8 @@ static void update_group_shares_cpu(struct task_group *tg, int cpu, } } +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
@@ -1667,7 +1670,14 @@ static int tg_shares_up(struct task_group *tg, void *data) 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 +57 -5
122 lines not on this page · raw message
PATCH v2 4/6 sched: unthrottle cfs_rq(s) who ran out of quota at period refresh
In reply to Paul TurnerAt 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 | 63 ++++++++++++++++++++++++++++++++++++++++++++++++++- kernel/sched_rt.c | 19 +-------------- 3 files changed, 79 insertions(+), 19 deletions(-)
kernel/sched.c +16 -0
@@ -1529,6 +1529,8 @@ static int tg_nop(struct task_group *tg, void *data) }#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)
@@ -1916,6 +1918,18 @@ static inline void __set_task_cpu(struct task_struct *p, unsigned int cpu)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.
@@ -8904,6 +8918,8 @@ static int tg_set_cfs_bandwidth(struct task_group *tg, u64 period, u64 quota)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 +62 -1
82 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_entity *rt_se)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 rt_rq *rt_rq)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(struct rt_bandwidth *rt_b, int overrun)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);
PATCH v2 5/6 sched: add exports tracking cfs bandwidth control statistics
In reply to Paul TurnerFrom: 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 occurrednr_throttled: the number of periods above in which execution was throttlethrottled_time: cumulative wall-time that any cpus have been throttled for
this group
--- kernel/sched.c | 26 ++++++++++++++++++++++++++ kernel/sched_fair.c | 19 ++++++++++++++++++- 2 files changed, 44 insertions(+), 1 deletions(-)
kernel/sched.c +26 -0
@@ -251,6 +251,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
@@ -423,6 +428,7 @@ struct cfs_rq {#ifdef CONFIG_CFS_BANDWIDTH u64 quota_assigned, quota_used;int throttled; +u64 throttled_timestamp;#endif #endif };
@@ -460,6 +466,10 @@ void init_cfs_bandwidth(struct cfs_bandwidth *cfs_b, u64 quota, u64 period)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
@@ -8996,6 +9006,18 @@ static int cpu_cfs_period_write_u64(struct cgroup *cgrp, struct cftype *cftype,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 */
@@ -9042,6 +9064,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 +18 -1
@@ -1229,15 +1229,26 @@ static void throttle_cfs_rq(struct cfs_rq *cfs_rq)break ; } 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 cfs_bandwidth *cfs_b =tg_cfs_bandwidth (cfs_rq->tg); +struct rq *rq =rq_of (cfs_rq); 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 +1282,7 @@ static void account_cfs_rq_quota(struct cfs_rq *cfs_rq,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 +1304,7 @@ static int do_sched_cfs_period_timer(struct cfs_bandwidth *cfs_b, int overrun)if (!cfs_rq_throttled (cfs_rq))continue ; + num_throttled++; delta =tg_request_cfs_quota (cfs_rq->tg);
@@ -1306,6 +1318,11 @@ static int do_sched_cfs_period_timer(struct cfs_bandwidth *cfs_b, int overrun) } } +/* update throttled stats */ + cfs_b->nr_periods++; +if (num_throttled) + cfs_b->nr_throttled++; +return idle; }
PATCH v2 6/6 sched: hierarchical task accounting for FAIR_GROUP_SCHED
In reply to Paul TurnerWith 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
@@ -368,7 +368,7 @@ static inline struct task_group *task_group(struct task_struct *p)/* 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;
@@ -1967,6 +1967,11 @@ static inline u64 sched_cfs_bandwidth_slice(void)#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++;
@@ -2042,7 +2047,6 @@ static void activate_task(struct rq *rq, struct task_struct *p, int wakeup) rq->nr_uninterruptible--;enqueue_task (rq, p, wakeup, false); -inc_nr_running (rq); }/*
@@ -2054,7 +2058,6 @@ static void deactivate_task(struct rq *rq, struct task_struct *p, int sleep) rq->nr_uninterruptible++;dequeue_task (rq, p, sleep); -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 task_struct *p, int wakeup, bool head)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 sleep)
@@ -892,6 +894,8 @@ static void dequeue_task_rt(struct rq *rq, struct task_struct *p, int sleep)dequeue_rt_entity (rt_se);dequeue_pushable_task (rq, p); + +dec_nr_running (rq); }/*
@@ -1758,4 +1762,3 @@ static void print_rt_stats(struct seq_file *m, int cpu) rcu_read_unlock(); }#endif /* CONFIG_SCHED_DEBUG */ -