CFS Bandwidth Control
Subsystems (2)
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.
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)
PATCH v3 2/7 sched: accumulate per-cfs_rq cpu usage
In reply to Bharata B Raosched: 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",
PATCH v3 3/7 sched: throttle cfs_rq entities which exceed their local quota
In reply to Bharata B Raosched: 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
PATCH v3 4/7 sched: unthrottle cfs_rq(s) who ran out of quota at period refresh
In reply to Bharata B Raosched: 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(structstatic 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 traw_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_rtreturn 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(structreturn 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(struif (!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 v3 5/7 sched: add exports tracking cfs bandwidth control statistics
In reply to Bharata B Raosched: 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 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 | 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_bandwhrtimer_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(strureturn 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(structstatic 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(strif (!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; }
PATCH v3 6/7 sched: hierarchical task accounting for FAIR_GROUP_SCHED
In reply to Bharata B Raosched: 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 taif (!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 *rdequeue_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 */ -
PATCH v3 7/7 sched: Return/expire slack quota using generation counters
In reply to Bharata B RaoQuoted 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_bandwraw_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 cgstatic 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 traw_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 traw_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
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
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 withinenqueue_task.
- Fix compilation break withCONFIG_PREEMPTon.
- 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.
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,
HerbertPS: 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 withinenqueue_task.
- Fix compilation break withCONFIG_PREEMPTon.
- 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.
Re: [PATCH v3 3/7] sched: throttle cfs_rq entities which exceed their local quota
In reply to Bharata B RaoQuoted 40 lines · On Tue, 12 Oct 2010 13:22:02 +0530 Bharata B Rao <[email protected]>…
sched: throttle
cfs_rqentities which exceed their local quotaFrom: Paul Turner <[email protected]>
In
account_cfs_rq_quota()(viaupdate_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 fromsched_entityhierarchy 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 intg_shares_up
- In the case that thecfs_rqof the cpu we are trying to pull from is throttled it is is ignored by the loadbalancer in__load_balance_fair()andmove_one_task_fair().Signed-off-by Paul Turner <[email protected]>Signed-off-by Nikhil Rao <[email protected]>Signed-off-by Bharata B Rao <[email protected]>--- 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
-1for_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
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_rqentities which exceed their local quotaFrom: Paul Turner <[email protected]>
In
account_cfs_rq_quota()(viaupdate_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 fromsched_entityhierarchy 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 intg_shares_up
- In the case that thecfs_rqof the cpu we are trying to pull from is throttled it is is ignored by the loadbalancer in__load_balance_fair()andmove_one_task_fair().Signed-off-by Paul Turner <[email protected]>Signed-off-by Nikhil Rao <[email protected]>Signed-off-by Bharata B Rao <[email protected]>---
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
-1for_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
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_rqentities which exceed their local quotaFrom: Paul Turner <[email protected]>
In
account_cfs_rq_quota()(viaupdate_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 fromsched_entityhierarchy 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 intg_shares_up
- In the case that thecfs_rqof the cpu we are trying to pull from is throttled it is is ignored by the loadbalancer in__load_balance_fair()andmove_one_task_fair().Signed-off-by Paul Turner <[email protected]>Signed-off-by Nikhil Rao <[email protected]>Signed-off-by Bharata B Rao <[email protected]>---
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
-1for_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.
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_rqentities which exceed their local quotaFrom: Paul Turner <[email protected]>
In
account_cfs_rq_quota()(viaupdate_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 fromsched_entityhierarchy 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 intg_shares_up
- In the case that thecfs_rqof the cpu we are trying to pull from is throttled it is is ignored by the loadbalancer in__load_balance_fair()andmove_one_task_fair().Signed-off-by Paul Turner <[email protected]>Signed-off-by Nikhil Rao <[email protected]>Signed-off-by Bharata B Rao <[email protected]>---
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
-1for_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.
Re: [PATCH v3 3/7] sched: throttle cfs_rq entities which exceed their local quota
In reply to Paul TurnerQuoted 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 akernel/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
-1for_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
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 akernel/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
-1for_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
Re: [PATCH v3 1/7] sched: introduce primitives to account for CFS bandwidth tracking
In reply to Bharata B RaoQuoted 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 pertask_group, it represents a pool of unclaimed bandwidth that cfs_rq's can allocate from. It uses the newcfs_bandwidthstructure.
- The local bandwidth is tracked per-cfs_rq, this represents allotments from the global pool
bandwidth assigned to atask_group, this is tracked using the newcfs_bandwidthstructure.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 sharedSigned-off-by Paul Turner <[email protected]>Signed-off-by Nikhil Rao <[email protected]>Signed-off-by Bharata B Rao <[email protected]>--- 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 EXPERIMENTALkernel/sched.c +6
-2@@ -192,10 +192,28 @@ static inline int rt_bandwidth_enabled(vreturn 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 rtreturn ;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(structstatic 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 taif (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 tasif (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 cgreturn (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
Re: [PATCH v3 2/7] sched: accumulate per-cfs_rq cpu usage
In reply to Bharata B RaoQuoted 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 thecfs_rqlevel versustask_groupsfor which bandwidth has been assigned. This is tracked by whether the localcfs_rq->quota_assignedis finite or infinite (RUNTIME_INF).For cfs_rq's that belong to a bandwidth constrained
task_groupwe introducetg_request_cfs_quota()which attempts to allocate quota from the global pool for use locally. Updates involving the global pool are currently protected undercfs_bandwidth->lock, local pools are protected byrq->lock.This patch only attempts to assign and track quota, no action is taken in the case that
cfs_rq->quota_usedexceedscfs_rq->quota_assigned.Signed-off-by Paul Turner <[email protected]>Signed-off-by Nikhil Rao <[email protected]>Signed-off-by Bharata B Rao <[email protected]>--- 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 *ccpuacct_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
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 thecfs_rqlevel versustask_groupsfor which bandwidth has been assigned. This is tracked by whether the localcfs_rq->quota_assignedis finite or infinite (RUNTIME_INF).For cfs_rq's that belong to a bandwidth constrained
task_groupwe introducetg_request_cfs_quota()which attempts to allocate quota from the global pool for use locally. Updates involving the global pool are currently protected undercfs_bandwidth->lock, local pools are protected byrq->lock.This patch only attempts to assign and track quota, no action is taken in the case that
cfs_rq->quota_usedexceedscfs_rq->quota_assigned.Signed-off-by Paul Turner <[email protected]>Signed-off-by Nikhil Rao <[email protected]>Signed-off-by Bharata B Rao <[email protected]>---
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_MUTEXESkernel/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'tcfs_b->runtimebe 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
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'tcfs_b->runtimebe always > 0?Hi Balbir,
cfs_b->runtimecan be 0 if the task group exhausts its quota.cfs_b->runtimeis a counter that is periodically refreshed tocfs_b->quota, and is decremented every time acfs_rqrequests 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
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'tcfs_b->runtimebe always > 0?Hi Balbir,
cfs_b->runtimecan be 0 if the task group exhausts its quota.cfs_b->runtimeis a counter that is periodically refreshed tocfs_b->quota, and is decremented every time acfs_rqrequests a slice.
Quoted 6 lines
Thanks, Nikhil
I saw several checks for quota ==
RUNTIME_INFand 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
Re: [PATCH v3 1/7] sched: introduce primitives to account for CFS bandwidth tracking
In reply to Balbir SinghQuoted 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 pertask_group, it represents a pool of unclaimed bandwidth that cfs_rq's can allocate from. It uses the newcfs_bandwidthstructure.
- The local bandwidth is tracked per-cfs_rq, this represents allotments from the global pool
bandwidth assigned to atask_group, this is tracked using the newcfs_bandwidthstructure.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 sharedSigned-off-by Paul Turner <[email protected]>Signed-off-by Nikhil Rao <[email protected]>Signed-off-by Bharata B Rao <[email protected]>--- 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 EXPERIMENTALkernel/sched.c +6
-2@@ -192,10 +192,28 @@ static inline int rt_bandwidth_enabled(vreturn 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 aboutwakeup_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 rtreturn ;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->periodtill 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_timeralso checks this. Is it to avoid doing the check undercfs_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(structstatic 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 taif (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 tasif (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 cgreturn (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.
Re: [PATCH v3 2/7] sched: accumulate per-cfs_rq cpu usage
In reply to Nikhil RaoQuoted 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'tcfs_b->runtimebe always > 0?Hi Balbir,
cfs_b->runtimecan be 0 if the task group exhausts its quota.cfs_b->runtimeis a counter that is periodically refreshed tocfs_b->quota, and is decremented every time acfs_rqrequests a slice.Quoted 6 lines
Thanks, Nikhil
I saw several checks for quota ==
RUNTIME_INFand 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_INFchecks are usually at the top of the functions and return immediately. The checks in the middle of functions are mostly to prevent races whencfs_b->quotais 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 tocfs_b->runtime> 0) because it is possible that the global pool is updated toRUNTIME_INFbetween the quota check inaccount_cfs_rq_quota()and when the actual quota is distributed intg_request_cfs_quota(). I hope that answers your original question.
Yes, it does, thanks!
Signature · 2 lines
Three Cheers, Balbir
Peter Zijlstra
maintainerRe: [PATCH v3 1/7] sched: introduce primitives to account for CFS bandwidth tracking
In reply to Balbir SinghQuoted 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 aboutwakeup_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->periodtill 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_timeralso checks this. Is it to avoid doing the check undercfs_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 ; +}
Peter Zijlstra
maintainerRe: [PATCH v3 2/7] sched: accumulate per-cfs_rq cpu usage
In reply to Bharata B RaoQuoted 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.
Peter Zijlstra
maintainerRe: [PATCH v3 2/7] sched: accumulate per-cfs_rq cpu usage
In reply to Bharata B Raokernel/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.
Re: [PATCH v3 2/7] sched: accumulate per-cfs_rq cpu usage
In reply to Peter ZijlstraQuoted 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->quoteoutside ofcfs_b->lockanyway, 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)
Peter Zijlstra
maintainerRe: [PATCH v3 3/7] sched: throttle cfs_rq entities which exceed their local quota
In reply to KAMEZAWA HiroyukiQuoted 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.
Peter Zijlstra
maintainerRe: [PATCH v3 2/7] sched: accumulate per-cfs_rq cpu usage
In reply to Paul TurnerQuoted 1 line · Paul Turner
Separate branch no?
Right, /me goes get more morning juice..
Re: [PATCH v3 2/7] sched: accumulate per-cfs_rq cpu usage
In reply to Peter ZijlstraQuoted 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_assignedis 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_execand 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.
Peter Zijlstra
maintainerRe: [PATCH v3 2/7] sched: accumulate per-cfs_rq cpu usage
In reply to Bharata B Raokernel/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'...
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, + }, +#endifSo 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
Peter Zijlstra
maintainerRe: [PATCH v3 2/7] sched: accumulate per-cfs_rq cpu usage
In reply to Paul TurnerQuoted 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_assignedis 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_execand 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?
Re: [PATCH v3 2/7] sched: accumulate per-cfs_rq cpu usage
In reply to Paul TurnerQuoted 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, + }, +#endifSo 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.
Re: [PATCH v3 2/7] sched: accumulate per-cfs_rq cpu usage
In reply to Peter ZijlstraQuoted 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_assignedis 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_execand 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.
Re: [PATCH v3 3/7] sched: throttle cfs_rq entities which exceed their local quota
In reply to Peter ZijlstraQuoted 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
Re: [PATCH v3 3/7] sched: throttle cfs_rq entities which exceed their local quota
In reply to Peter ZijlstraQuoted 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
Peter Zijlstra
maintainerRe: [PATCH v3 3/7] sched: throttle cfs_rq entities which exceed their local quota
In reply to KAMEZAWA HiroyukiQuoted 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.
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
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
Peter Zijlstra
maintainerRe: [PATCH v3 3/7] sched: throttle cfs_rq entities which exceed their local quota
In reply to KAMEZAWA HiroyukiQuoted 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.
Peter Zijlstra
maintainerRe: [PATCH v3 3/7] sched: throttle cfs_rq entities which exceed their local quota
In reply to Paul TurnerQuoted 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 ;-)
Re: [PATCH v3 1/7] sched: introduce primitives to account for CFS bandwidth tracking
In reply to Peter ZijlstraQuoted 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 aboutwakeup_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->periodtill 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_timeralso checks this. Is it to avoid doing the check undercfs_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
Peter Zijlstra
maintainerRe: [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 aboutwakeup_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.
Re: [PATCH v3 3/7] sched: throttle cfs_rq entities which exceed their local quota
In reply to Peter ZijlstraQuoted 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
Re: [PATCH v3 4/7] sched: unthrottle cfs_rq(s) who ran out of quota at period refresh
In reply to Bharata B RaoQuoted 11 lines · Bharata B Rao
sched: unthrottle
cfs_rq(s)who ran out of quota at period refreshFrom: 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 permitsUnthrottled entities have the
cfs_rq->throttledflag 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 intosched_bw_period_mask()since it is now shared by both cfs and rt bandwidth period timers.The !CONFIG_RT_GROUP_SCHED &&
CONFIG_SMPcase has been collapsed to userd->spaninstead ofcpu_online_masksince I think that was incorrect before (don't want to hit cpu's outside of yourroot_domainfor RT bandwidth).Signed-off-by Paul Turner <[email protected]>Signed-off-by Nikhil Rao <[email protected]>Signed-off-by Bharata B Rao <[email protected]>--- 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(structstatic 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 traw_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(structstatic 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_rtreturn 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(structreturn 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(struif (!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
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
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.
Re: [PATCH v3 1/7] sched: introduce primitives to account for CFS bandwidth tracking
In reply to Balbir SinghQuoted 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
Re: [PATCH v3 4/7] sched: unthrottle cfs_rq(s) who ran out of quota at period refresh
In reply to Balbir SinghSorry 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 refreshFrom: 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->throttledflag 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 intosched_bw_period_mask()since it is now shared by both cfs and rt bandwidth period timers.The !CONFIG_RT_GROUP_SCHED &&
CONFIG_SMPcase has been collapsed to userd->spaninstead ofcpu_online_masksince I think that was incorrect before (don't want to hit cpu's outside of yourroot_domainfor RT bandwidth).Signed-off-by Paul Turner <[email protected]>Signed-off-by Nikhil Rao <[email protected]>Signed-off-by Bharata B Rao <[email protected]>--- 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(structstatic 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 traw_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_rqQuoted 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
-1static 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.