CFS Hard limits - v5

sched: Rename struct rt_bandwidth to sched_bandwidth

From: Dhaval Giani <[email protected]>

Rename struct rt_bandwidth to sched_bandwidth and rename some of the routines to generic names (s/rt_/sched_) so that they can be used by CFS hard limits code in the subsequent patches.

No functionality change by this patch.

Signed-off-by Dhaval Giani <[email protected]>

Signed-off-by Bharata B Rao <[email protected]>

---
 kernel/sched.c    |  127 ++++++++++++++++++++++++++---------------------------
 kernel/sched_rt.c |   46 ++++++++++---------
 2 files changed, 86 insertions(+), 87 deletions(-)

kernel/sched.c +14 -15

index c535cc4..21cf0d5 100644
@@ -139,50 +139,50 @@ struct rt_prio_array {
 	struct list_head queue[MAX_RT_PRIO];
 };
 
-struct rt_bandwidth {
+struct sched_bandwidth {
 	/* nests inside the rq lock: */
-	raw_spinlock_t		rt_runtime_lock;
-	ktime_t			rt_period;
-	u64			rt_runtime;
-	struct hrtimer		rt_period_timer;
+	raw_spinlock_t		runtime_lock;
+	ktime_t			period;
+	u64			runtime;
+	struct hrtimer		period_timer;
 };
 
-static struct rt_bandwidth def_rt_bandwidth;
+static struct sched_bandwidth def_rt_bandwidth;
 
-static int do_sched_rt_period_timer(struct rt_bandwidth *rt_b, int overrun);
+static int do_sched_rt_period_timer(struct sched_bandwidth *sched_b, int overrun);
 
 static enum hrtimer_restart sched_rt_period_timer(struct hrtimer *timer)
 {
-	struct rt_bandwidth *rt_b =
-		container_of(timer, struct rt_bandwidth, rt_period_timer);
+	struct sched_bandwidth *sched_b =
+		container_of(timer, struct sched_bandwidth, period_timer);
 	ktime_t now;
 	int overrun;
 	int idle = 0;
 
 	for (;;) {
 		now = hrtimer_cb_get_time(timer);
-		overrun = hrtimer_forward(timer, now, rt_b->rt_period);
+		overrun = hrtimer_forward(timer, now, sched_b->period);
 
 		if (!overrun)
 			break;
 
-		idle = do_sched_rt_period_timer(rt_b, overrun);
+		idle = do_sched_rt_period_timer(sched_b, overrun);
 	}
 
 	return idle ? HRTIMER_NORESTART : HRTIMER_RESTART;
 }
 
-static
-void init_rt_bandwidth(struct rt_bandwidth *rt_b, u64 period, u64 runtime)
+static void init_sched_bandwidth(struct sched_bandwidth *sched_b, u64 period,
+	u64 runtime, enum hrtimer_restart (*period_timer)(struct hrtimer *))
 {
-	rt_b->rt_period = ns_to_ktime(period);
-	rt_b->rt_runtime = runtime;
+	sched_b->period = ns_to_ktime(period);

kernel/sched.c +1 -1

 }
 
 static inline int rt_bandwidth_enabled(void)

@@ -190,42 +190,40 @@ static inline int rt_bandwidth_enabled(void)
 	return sysctl_sched_rt_runtime >= 0;
 }
 
-static void start_rt_bandwidth(struct rt_bandwidth *rt_b)
+static void start_sched_bandwidth(struct sched_bandwidth *sched_b)
 {
 	ktime_t now;
 

Quoted 8 lines · Bharata B Rao

sched: Rename struct rt_bandwidth to sched_bandwidth

From: Dhaval Giani <[email protected]>

Rename struct rt_bandwidth to sched_bandwidth and rename some of the routines to generic names (s/rt_/sched_) so that they can be used by CFS hard limits code in the subsequent patches.

Quoted 4 lines

No functionality change by this patch.

Signed-off-by Dhaval Giani <[email protected]>

Signed-off-by Bharata B Rao <[email protected]>

Looks good, some nit picks below

Acked-by Balbir Singh <[email protected]>

Quoted 72 lines

---
 kernel/sched.c    |  127 ++++++++++++++++++++++++++---------------------------
 kernel/sched_rt.c |   46 ++++++++++---------
 2 files changed, 86 insertions(+), 87 deletions(-)

kernel/sched.c +16 -16

index c535cc4..21cf0d5 100644
@@ -139,50 +139,50 @@ struct rt_prio_array {
 	struct list_head queue[MAX_RT_PRIO];
 };
 
-struct rt_bandwidth {
+struct sched_bandwidth {
 	/* nests inside the rq lock: */
-	raw_spinlock_t		rt_runtime_lock;
-	ktime_t			rt_period;
-	u64			rt_runtime;
-	struct hrtimer		rt_period_timer;
+	raw_spinlock_t		runtime_lock;
+	ktime_t			period;
+	u64			runtime;
+	struct hrtimer		period_timer;
 };
 
-static struct rt_bandwidth def_rt_bandwidth;
+static struct sched_bandwidth def_rt_bandwidth;
 
-static int do_sched_rt_period_timer(struct rt_bandwidth *rt_b, int overrun);
+static int do_sched_rt_period_timer(struct sched_bandwidth *sched_b, int overrun);
 
 static enum hrtimer_restart sched_rt_period_timer(struct hrtimer *timer)
 {
-	struct rt_bandwidth *rt_b =
-		container_of(timer, struct rt_bandwidth, rt_period_timer);
+	struct sched_bandwidth *sched_b =
+		container_of(timer, struct sched_bandwidth, period_timer);
 	ktime_t now;
 	int overrun;
 	int idle = 0;
 
 	for (;;) {
 		now = hrtimer_cb_get_time(timer);
-		overrun = hrtimer_forward(timer, now, rt_b->rt_period);
+		overrun = hrtimer_forward(timer, now, sched_b->period);
 
 		if (!overrun)
 			break;
 
-		idle = do_sched_rt_period_timer(rt_b, overrun);
+		idle = do_sched_rt_period_timer(sched_b, overrun);
 	}
 
 	return idle ? HRTIMER_NORESTART : HRTIMER_RESTART;
 }
 
-static
-void init_rt_bandwidth(struct rt_bandwidth *rt_b, u64 period, u64 runtime)
+static void init_sched_bandwidth(struct sched_bandwidth *sched_b, u64 period,
+	u64 runtime, enum hrtimer_restart (*period_timer)(struct hrtimer *))
 {
-	rt_b->rt_period = ns_to_ktime(period);
-	rt_b->rt_runtime = runtime;
+	sched_b->period = ns_to_ktime(period);
+	sched_b->runtime = runtime;
 
-	raw_spin_lock_init(&rt_b->rt_runtime_lock);
+	raw_spin_lock_init(&sched_b->runtime_lock);
 

kernel/sched.c struct rt_prio_array { · line 185

Quoted 5 lines

kernel/sched.c +2 -2

-	hrtimer_init(&rt_b->rt_period_timer,
+	hrtimer_init(&sched_b->period_timer,
 			CLOCK_MONOTONIC, HRTIMER_MODE_REL);
-	rt_b->rt_period_timer.function = sched_rt_period_timer;
+	sched_b->period_timer.function = *period_timer;

Hmm.. may be I forgetting the "C" language, but why do you dereference the pointer before assignment? You should be able to directly assign a function address to the function pointer. Did you see a warning?

Quoted 17 lines

kernel/sched.c +2 -2

 }
 
 static inline int rt_bandwidth_enabled(void)

@@ -190,42 +190,40 @@ static inline int rt_bandwidth_enabled(void)
 	return sysctl_sched_rt_runtime >= 0;
 }
 
-static void start_rt_bandwidth(struct rt_bandwidth *rt_b)
+static void start_sched_bandwidth(struct sched_bandwidth *sched_b)
 {
 	ktime_t now;
 
-	if (!rt_bandwidth_enabled() || rt_b->rt_runtime == RUNTIME_INF)
+	if (!rt_bandwidth_enabled() || sched_b->runtime == RUNTIME_INF)
 		return;
 

kernel/sched.c static inline int rt_bandwidth_enabled(void) · line 203

Quoted 6 lines

kernel/sched.c +2 -2

-	if (hrtimer_active(&rt_b->rt_period_timer))
+	if (hrtimer_active(&sched_b->period_timer))
 		return;
 
-	raw_spin_lock(&rt_b->rt_runtime_lock);
+	raw_spin_lock(&sched_b->runtime_lock);

I don't quite understand why this is a raw_spin_lock

Hi,

This is the v5 post of CFS hard limits. In this patchset, I have pulled out bandwidth and runtime handling code from RT into sched.c so that the same code can be used by CFS hard limits.

Also I have addressed the review comments given by Peter Zijlstra for v4.

Hi Bharata,

Thanks for the updated patchset.  As discussed the other day briefly I have some concerns with the usage of the current RT bandwidth rate-limiting code as there are some assumptions made that I feel don't fit the general case well.

The reason for this is that the borrowing logic in bandwidth rebalance appears to make the assumption that we wil will be able to converge rapidly to the period.  Indeed, in each iteration of redistribution we take only 1/weight(nrcpus) [assuming no cpuset partitions] of the time remaining.  This is a decreasing series, and if we can't exceed the period our convergence looks pretty slow [geometric series].

In general it appears the following relation be satisfied for efficient
execution:  (weight(nr_cpus) * runtime) >> period

This assumption is well satisfied in the RT case since the available bandwidth is very high.  However I fear for the general case of user limits on tg usage lie at the other end of the spectrum.  Especially for those trying to partition large machines into many smaller well provisioned fractions, e.g. 0-2 cores out of a total 64.  The lock and re-distribution cost for each iteration is also going to be quite high in this case which will potentially compound on the number of iterations required above.

What are your thoughts on using a separate mechanism for the general case.  A draft proposal follows:

- Maintain a global run-time pool for each tg.  The runtime specified by the user represents the value that this pool will be refilled to each period.
- We continue to maintain the local notion of runtime/period in each cfs_rq, continue to accumulate locally here.

Upon locally exceeding the period acquire new credit from the global pool (either under lock or more likely using atomic ops).  This can either be in fixed steppings (e.g. 10ms, could be tunable) or following some quasi-curve variant with historical demand.

One caveat here is that there is some over-commit in the system, the local differences of runtime vs period represent additional over the global pool. However it should not be possible to consistently exceed limits since the rate of refill is gated by the runtime being input into the system via the per-tg pool.

This would also naturally associate with an interface change that would mean the runtime limit for a group would be the effective cpurate within the period.

e.g. by setting a runtime of 200000us on a 100000us period it would effectively allow you to use 2 cpus worth of wall-time on a multicore system.

I feel this is slightly more natural than the current definition which due to being local means that values set will not result in consistent behavior across machines of different core counts.  It also has the benefit of being consistent with observed exports of time consumed, e.g. rusage, (indirectly) time, etc.

For future scalability as machine size grows this could potentially be partitioned below the tg level along the boundaries of sched_domains (or something similar).  However for an initial draft given current machine sizes the contention on the global pool should hopefully be fairly low.

Quoted 2 lines · Paul Turner

Hi Bharata,

Hi Paul,

Sorry for the late reply. Since you removed the CC-list, I didn't get this mail in my inbox and hence didn't notice this at all until this time!

[Putting back the original CC list in this mail]

Quoted 16 lines

Thanks for the updated patchset.  As discussed the other day briefly I have some concerns with the usage of the current RT bandwidth rate-limiting code as there are some assumptions made that I feel don't fit the general case well.

The reason for this is that the borrowing logic in bandwidth rebalance appears to make the assumption that we wil will be able to converge rapidly to the period.  Indeed, in each iteration of redistribution we take only 1/weight(nrcpus) [assuming no cpuset partitions] of the time remaining.  This is a decreasing series, and if we can't exceed the period our convergence looks pretty slow [geometric series].

In general it appears the following relation be satisfied for efficient
execution:  (weight(nr_cpus) * runtime) >> period

Quoted 7 lines

This assumption is well satisfied in the RT case since the available bandwidth is very high.  However I fear for the general case of user limits on tg usage lie at the other end of the spectrum.  Especially for those trying to partition large machines into many smaller well provisioned fractions, e.g. 0-2 cores out of a total 64.  The lock and re-distribution cost for each iteration is also going to be quite high in this case which will potentially compound on the number of iterations required above.

I see your point. Having a runtime which is much lesser than the period will result in a lot of iterations of borrowing from every CPU before the source CPU accumulates the maximum possible runtime.

Apart from this, I also see that after accumulating the maximum possible runtime from all CPUs, the task sometimes moves to another CPU due to load balancing. When this happens, the new CPU starts the borrowing iterations all over again!

As you observe, borrowing just 1/n th (n = number of CPUs) of the spare runtime from each CPU is not ideal for CFS if runtimes are going to be much lesser than period unlike RT. This would involve iterating through all the CPUs and acquiring/releasing a spinlock in each iteration.

Quoted 14 lines

What are your thoughts on using a separate mechanism for the general case.  A draft proposal follows:

- Maintain a global run-time pool for each tg.  The runtime specified by the user represents the value that this pool will be refilled to each period.
- We continue to maintain the local notion of runtime/period in each cfs_rq, continue to accumulate locally here.

Upon locally exceeding the period acquire new credit from the global pool (either under lock or more likely using atomic ops).  This can either be in fixed steppings (e.g. 10ms, could be tunable) or following some quasi-curve variant with historical demand.

Quoted 6 lines

One caveat here is that there is some over-commit in the system, the local differences of runtime vs period represent additional over the global pool. However it should not be possible to consistently exceed limits since the rate of refill is gated by the runtime being input into the system via the per-tg pool.

We borrow from what is actually available as spare (spare = unused or remaining). With global pool, I see that would be difficult. Inability/difficulty in keeping the global pool in sync with the actual available spare time is the reason for over-commit ?

Quoted 10 lines

This would also naturally associate with an interface change that would mean the runtime limit for a group would be the effective cpurate within the period.

e.g. by setting a runtime of 200000us on a 100000us period it would effectively allow you to use 2 cpus worth of wall-time on a multicore system.

I feel this is slightly more natural than the current definition which due to being local means that values set will not result in consistent behavior across machines of different core counts.  It also has the benefit of being consistent with observed exports of time consumed, e.g. rusage, (indirectly) time, etc.

Though runtimes are enforced locally per-cpu, that's only the implementation. The definition of runtime and period is still system-wide/global. A runtime/period=0.25/0.5 will mean 0.25s of system wide runtime within a period of 0.5s. Talking about consistent definition, I would say this consistently defines half of system wide wall-time on all configurations :)

If it means 2 CPUs worth wall-time
in 4 core machine, it would mean 4 CPUs on a 8 CPU machine.  At this point, I am inclined to go with this and let the admins/tools work out the actual CPUs part of it. However I would like to hear what others think about this interface.

Quoted 5 lines

For future scalability as machine size grows this could potentially be partitioned below the tg level along the boundaries of sched_domains (or something similar).  However for an initial draft given current machine sizes the contention on the global pool should hopefully be fairly low.

One of the alternatives I have in mind is to be more aggressive while borrowing. While keeping the current algorithm (of iterating thro' all CPUs when borrowing) intact, we could potentially borrow more from those CPUs which don't have any running task from the given group. I just experimented with borrowing half of the available runtime from such CPUs and found that number of iterations are greatly reduced and the source runtime quickly converges to its max possible value. Do you see any issues with this ?

Thanks for your note.

Regards,
Bharata.
--
http://bharata.sulekha.com/blog/posts.htm, http://raobharata.wordpress.com/

Quoted 22 lines · Bharata B Rao

Quoted 14 lines · Paul Turner

What are your thoughts on using a separate mechanism for the general case.  A draft proposal follows:

- Maintain a global run-time pool for each tg.  The runtime specified by the user represents the value that this pool will be refilled to each period.
- We continue to maintain the local notion of runtime/period in each cfs_rq, continue to accumulate locally here.

Upon locally exceeding the period acquire new credit from the global pool (either under lock or more likely using atomic ops).  This can either be in fixed steppings (e.g. 10ms, could be tunable) or following some quasi-curve variant with historical demand.

Quoted 6 lines

One caveat here is that there is some over-commit in the system, the local differences of runtime vs period represent additional over the global pool. However it should not be possible to consistently exceed limits since the rate of refill is gated by the runtime being input into the system via the per-tg pool.

Quoted 5 lines

We borrow from what is actually available as spare (spare = unused or remaining). With global pool, I see that would be difficult. Inability/difficulty in keeping the global pool in sync with the actual available spare time is the reason for over-commit ?

We maintain two pools, a global pool (new) and a per-cfs_rq pool (similar to existing rt_bw).

When consuming time you charge vs your local bandwidth until it is expired, at this point you must either refill from the global pool, or throttle.

The "slack" in the system is the sum of unconsumed time in local pools from the *previous* global pool refill. This is bounded above by the size of time you refill a local pool at each expiry. We call the size of refill a 'slice'.

e.g.

Task limit of 50ms, slice=10ms, 4cpus, period of 500ms

Task A runs on cpus 0 and 1 for 5ms each, then blocks.

When A first executes on each cpu we take slice=10ms from the global pool of 50ms and apply it to the local rq. Execution then proceeds vs local pool.

Current state is: 5 ms in local pools on {0,1}, 30ms remaining in global pool

Upon period expiration we issue a global pool refill. At this point we have:
5 ms in local pools on {0,1}, 50ms remaining in global pool.

That 10ms of slack time is over-commit in the system. However it should be clear that this can only be a local effect since over any period of time the rate of input into the system is limited by global pool refill rate.

There are also some strategies that we are exploring to improve behavior further here. One idea is that if we maintain a generation counter then on voluntary dequeue (e.g. tasks block) we can return local time to the global period pool or expire it (if generations don't match), this greatly reduces the noise (via slack vs ideal limit) that a busty application can induce.

Quoted 12 lines

Quoted 11 lines

This would also naturally associate with an interface change that would mean the runtime limit for a group would be the effective cpurate within the period.

e.g. by setting a runtime of 200000us on a 100000us period it would effectively allow you to use 2 cpus worth of wall-time on a multicore system.

I feel this is slightly more natural than the current definition which due to being local means that values set will not result in consistent behavior across machines of different core counts.  It also has the benefit of being consistent with observed exports of time consumed, e.g. rusage, (indirectly) time, etc.

Quoted 6 lines

Though runtimes are enforced locally per-cpu, that's only the implementation. The definition of runtime and period is still system-wide/global. A runtime/period=0.25/0.5 will mean 0.25s of system wide runtime within a period of 0.5s. Talking about consistent definition, I would say this consistently defines half of system wide wall-time on all configurations :)

This feels non-intuitive suppose you have a non-homogeneous fleet of systems. It is also difficult to express limits in terms of cores, suppose I'm an admin trying to jail my users (maybe I rent out virtual time ala EC2 for example). The fractions I have to use to represent integer core amounts are going to become quite small on large systems.
For example, 1 core on a 64 core system would mean 3.905ms/250ms
period. What's the dependency here between your time and the current cpuset topology also, if I'm only allowed on half the system does this fraction then refer to global resources or what I'm constrained to? This seems a difficult data dependency to manage.

My (personal) ideology is that we are metering at the cpu level as opposed to the system level -- which means N seconds of cpu-time makes more sense to me. I feel it has advantages in that it can be specified more directly relative to the period and is independent of system partitioning.

I'd be interested to hear other opinions on this.

Quoted 13 lines

If it means 2 CPUs worth wall-time
in 4 core machine, it would mean 4 CPUs on a 8 CPU machine.  At this point, I am inclined to go with this and let the admins/tools work out the actual CPUs part of it. However I would like to hear what others think about this interface.

Quoted 5 lines

For future scalability as machine size grows this could potentially be partitioned below the tg level along the boundaries of sched_domains (or something similar).  However for an initial draft given current machine sizes the contention on the global pool should hopefully be fairly low.

Quoted 9 lines

One of the alternatives I have in mind is to be more aggressive while borrowing. While keeping the current algorithm (of iterating thro' all CPUs when borrowing) intact, we could potentially borrow more from those CPUs which don't have any running task from the given group. I just experimented with borrowing half of the available runtime from such CPUs and found that number of iterations are greatly reduced and the source runtime quickly converges to its max possible value. Do you see any issues with this ?

I strongly believe that this is going to induce significant lock contention and is not a scalable solution over time. While using a faster converging series for time may help I think there are confounding factors that limit effect here. Consider the 1 core on a 64 core system example above. With only 3.905ms per pool we are going to quickly hit the case where we are borrowing not-useful periods of time while thrashing locks.

We are in the midst of an implementation for proposal above which we'll have ready post to here for consideration next week. We have maintained your existing approach with respect to handling throttled entities and layered on top of that the proposed alternate local/global bandwidth scheme. Initial tests show very promising results!

Quoted 53 lines · Paul Turner

Quoted 22 lines · Bharata B Rao

Quoted 14 lines · Paul Turner

What are your thoughts on using a separate mechanism for the general case.  A draft proposal follows:

- Maintain a global run-time pool for each tg.  The runtime specified by the user represents the value that this pool will be refilled to each period.
- We continue to maintain the local notion of runtime/period in each cfs_rq, continue to accumulate locally here.

Upon locally exceeding the period acquire new credit from the global pool (either under lock or more likely using atomic ops).  This can either be in fixed steppings (e.g. 10ms, could be tunable) or following some quasi-curve variant with historical demand.

Quoted 6 lines

One caveat here is that there is some over-commit in the system, the local differences of runtime vs period represent additional over the global pool. However it should not be possible to consistently exceed limits since the rate of refill is gated by the runtime being input into the system via the per-tg pool.

Quoted 5 lines

We borrow from what is actually available as spare (spare = unused or remaining). With global pool, I see that would be difficult. Inability/difficulty in keeping the global pool in sync with the actual available spare time is the reason for over-commit ?

We maintain two pools, a global pool (new) and a per-cfs_rq pool (similar to existing rt_bw).

When consuming time you charge vs your local bandwidth until it is expired, at this point you must either refill from the global pool, or throttle.

The "slack" in the system is the sum of unconsumed time in local pools from the *previous* global pool refill.  This is bounded above by the size of time you refill a local pool at each expiry.  We call the size of refill a 'slice'.

e.g.

Task limit of 50ms, slice=10ms, 4cpus, period of 500ms

Task A runs on cpus 0 and 1 for 5ms each, then blocks.

When A first executes on each cpu we take slice=10ms from the global pool of 50ms and apply it to the local rq.  Execution then proceeds vs local pool.

Current state is: 5 ms in local pools on {0,1}, 30ms remaining in global pool

Quoted 7 lines

Upon period expiration we issue a global pool refill.  At this point we have:
5 ms in local pools on {0,1}, 50ms remaining in global pool.

That 10ms of slack time is over-commit in the system.  However it should be clear that this can only be a local effect since over any period of time the rate of input into the system is limited by global pool refill rate.

With the same setup as above consider 5 such tasks which block after consuming 5ms each. So now we have 25ms slack time. In the next bandwidth period if 5 cpu hogs start running and they would consume this 25ms and the 50ms from this period. So we gave 50% extra to a group in a bandwidth period. Just wondering how common such scenarious could be.

Quoted 7 lines

There are also some strategies that we are exploring to improve behavior further here.  One idea is that if we maintain a generation counter then on voluntary dequeue (e.g. tasks block) we can return local time to the global period pool or expire it (if generations don't match), this greatly reduces the noise (via slack vs ideal limit) that a busty application can induce.

Why not clear the remaining runtime during bandwidth refresh ?

Quoted 30 lines

Quoted 12 lines

Quoted 11 lines

This would also naturally associate with an interface change that would mean the runtime limit for a group would be the effective cpurate within the period.

e.g. by setting a runtime of 200000us on a 100000us period it would effectively allow you to use 2 cpus worth of wall-time on a multicore system.

I feel this is slightly more natural than the current definition which due to being local means that values set will not result in consistent behavior across machines of different core counts.  It also has the benefit of being consistent with observed exports of time consumed, e.g. rusage, (indirectly) time, etc.

Quoted 6 lines

Though runtimes are enforced locally per-cpu, that's only the implementation. The definition of runtime and period is still system-wide/global. A runtime/period=0.25/0.5 will mean 0.25s of system wide runtime within a period of 0.5s. Talking about consistent definition, I would say this consistently defines half of system wide wall-time on all configurations :)

This feels non-intuitive suppose you have a non-homogeneous fleet of systems.  It is also difficult to express limits in terms of cores, suppose I'm an admin trying to jail my users (maybe I rent out virtual time ala EC2 for example).  The fractions I have to use to represent integer core amounts are going to become quite small on large systems. For example, 1 core on a 64 core system would mean 3.905ms/250ms period.  What's the dependency here between your time and the current cpuset topology also, if I'm only allowed on half the system does this fraction then refer to global resources or what I'm constrained to? This seems a difficult data dependency to manage.

Quoted 7 lines

My (personal) ideology is that we are metering at the cpu level as opposed to the system level -- which means N seconds of cpu-time makes more sense to me.  I feel it has advantages in that it can be specified more directly relative to the period and is independent of system partitioning.

I'd be interested to hear other opinions on this.

We need a consensus here, will wait to see what others think about this.

Quoted 31 lines

Quoted 13 lines

If it means 2 CPUs worth wall-time
in 4 core machine, it would mean 4 CPUs on a 8 CPU machine.  At this point, I am inclined to go with this and let the admins/tools work out the actual CPUs part of it. However I would like to hear what others think about this interface.

Quoted 5 lines

For future scalability as machine size grows this could potentially be partitioned below the tg level along the boundaries of sched_domains (or something similar).  However for an initial draft given current machine sizes the contention on the global pool should hopefully be fairly low.

Quoted 9 lines

One of the alternatives I have in mind is to be more aggressive while borrowing. While keeping the current algorithm (of iterating thro' all CPUs when borrowing) intact, we could potentially borrow more from those CPUs which don't have any running task from the given group. I just experimented with borrowing half of the available runtime from such CPUs and found that number of iterations are greatly reduced and the source runtime quickly converges to its max possible value. Do you see any issues with this ?

I strongly believe that this is going to induce significant lock contention and is not a scalable solution over time.  While using a faster converging series for time may help I think there are confounding factors that limit effect here.  Consider the 1 core on a 64 core system example above.  With only 3.905ms per pool we are going to quickly hit the case where we are borrowing not-useful periods of time while thrashing locks.

Quoted 6 lines

We are in the midst of an implementation for proposal above which we'll have ready post to here for consideration next week.  We have maintained your existing approach with respect to handling throttled entities and layered on top of that the proposed alternate local/global bandwidth scheme.  Initial tests show very promising results!

Nice. Look forward to your patches.

Regards,
Bharata.

Quoted 62 lines · Bharata B Rao

Quoted 53 lines · Paul Turner

Quoted 22 lines · Bharata B Rao

Quoted 14 lines · Paul Turner

What are your thoughts on using a separate mechanism for the general case.  A draft proposal follows:

- Maintain a global run-time pool for each tg.  The runtime specified by the user represents the value that this pool will be refilled to each period.
- We continue to maintain the local notion of runtime/period in each cfs_rq, continue to accumulate locally here.

Upon locally exceeding the period acquire new credit from the global pool (either under lock or more likely using atomic ops).  This can either be in fixed steppings (e.g. 10ms, could be tunable) or following some quasi-curve variant with historical demand.

Quoted 6 lines

One caveat here is that there is some over-commit in the system, the local differences of runtime vs period represent additional over the global pool. However it should not be possible to consistently exceed limits since the rate of refill is gated by the runtime being input into the system via the per-tg pool.

Quoted 5 lines

We borrow from what is actually available as spare (spare = unused or remaining). With global pool, I see that would be difficult. Inability/difficulty in keeping the global pool in sync with the actual available spare time is the reason for over-commit ?

We maintain two pools, a global pool (new) and a per-cfs_rq pool (similar to existing rt_bw).

When consuming time you charge vs your local bandwidth until it is expired, at this point you must either refill from the global pool, or throttle.

The "slack" in the system is the sum of unconsumed time in local pools from the *previous* global pool refill.  This is bounded above by the size of time you refill a local pool at each expiry.  We call the size of refill a 'slice'.

e.g.

Task limit of 50ms, slice=10ms, 4cpus, period of 500ms

Task A runs on cpus 0 and 1 for 5ms each, then blocks.

When A first executes on each cpu we take slice=10ms from the global pool of 50ms and apply it to the local rq.  Execution then proceeds vs local pool.

Current state is: 5 ms in local pools on {0,1}, 30ms remaining in global pool

Quoted 7 lines

Upon period expiration we issue a global pool refill.  At this point we have:
5 ms in local pools on {0,1}, 50ms remaining in global pool.

That 10ms of slack time is over-commit in the system.  However it should be clear that this can only be a local effect since over any period of time the rate of input into the system is limited by global pool refill rate.

Quoted 6 lines

With the same setup as above consider 5 such tasks which block after consuming 5ms each. So now we have 25ms slack time. In the next bandwidth period if 5 cpu hogs start running and they would consume this 25ms and the 50ms from this period. So we gave 50% extra to a group in a bandwidth period. Just wondering how common such scenarious could be.

Yes within a single given period you may exceed your reservation due to slack.  However, of note is that across any 2 successive periods you are guaranteed to be within your reservation, i.e. 2*usage <= 2*period, as slack available means that you under-consumed your previous period.

For those needing a hard guarantee (independent of amelioration strategies) halving the period provided would then provide this across their target period with the basic v1 implementation.

Quoted 10 lines

Quoted 7 lines

There are also some strategies that we are exploring to improve behavior further here.  One idea is that if we maintain a generation counter then on voluntary dequeue (e.g. tasks block) we can return local time to the global period pool or expire it (if generations don't match), this greatly reduces the noise (via slack vs ideal limit) that a busty application can induce.

Why not clear the remaining runtime during bandwidth refresh ?

This doesn't scale with (many cpus) * (many bandwidth limits).

It is still my intuition that introducing a generation counter for quota would allow us to handle this gracefully as that would allow both invalidation of expired slack time and for the (potentially fractional) returning of local quota to the global pool within a period (upon block/voluntary yield).

Such tactics would probably seem better suited for a v2 as there are both other possible approaches and the matter of added complexity to the basic design.  However, if it works well it might sneak into v1 ;)

Quoted 83 lines

Quoted 30 lines

Quoted 12 lines

Quoted 11 lines

This would also naturally associate with an interface change that would mean the runtime limit for a group would be the effective cpurate within the period.

e.g. by setting a runtime of 200000us on a 100000us period it would effectively allow you to use 2 cpus worth of wall-time on a multicore system.

I feel this is slightly more natural than the current definition which due to being local means that values set will not result in consistent behavior across machines of different core counts.  It also has the benefit of being consistent with observed exports of time consumed, e.g. rusage, (indirectly) time, etc.

Quoted 6 lines

Though runtimes are enforced locally per-cpu, that's only the implementation. The definition of runtime and period is still system-wide/global. A runtime/period=0.25/0.5 will mean 0.25s of system wide runtime within a period of 0.5s. Talking about consistent definition, I would say this consistently defines half of system wide wall-time on all configurations :)

This feels non-intuitive suppose you have a non-homogeneous fleet of systems.  It is also difficult to express limits in terms of cores, suppose I'm an admin trying to jail my users (maybe I rent out virtual time ala EC2 for example).  The fractions I have to use to represent integer core amounts are going to become quite small on large systems. For example, 1 core on a 64 core system would mean 3.905ms/250ms period.  What's the dependency here between your time and the current cpuset topology also, if I'm only allowed on half the system does this fraction then refer to global resources or what I'm constrained to? This seems a difficult data dependency to manage.

Quoted 7 lines

My (personal) ideology is that we are metering at the cpu level as opposed to the system level -- which means N seconds of cpu-time makes more sense to me.  I feel it has advantages in that it can be specified more directly relative to the period and is independent of system partitioning.

I'd be interested to hear other opinions on this.

We need a consensus here, will wait to see what others think about this.

Quoted 31 lines

Quoted 13 lines

If it means 2 CPUs worth wall-time
in 4 core machine, it would mean 4 CPUs on a 8 CPU machine.  At this point, I am inclined to go with this and let the admins/tools work out the actual CPUs part of it. However I would like to hear what others think about this interface.

Quoted 5 lines

For future scalability as machine size grows this could potentially be partitioned below the tg level along the boundaries of sched_domains (or something similar).  However for an initial draft given current machine sizes the contention on the global pool should hopefully be fairly low.

Quoted 9 lines

One of the alternatives I have in mind is to be more aggressive while borrowing. While keeping the current algorithm (of iterating thro' all CPUs when borrowing) intact, we could potentially borrow more from those CPUs which don't have any running task from the given group. I just experimented with borrowing half of the available runtime from such CPUs and found that number of iterations are greatly reduced and the source runtime quickly converges to its max possible value. Do you see any issues with this ?

I strongly believe that this is going to induce significant lock contention and is not a scalable solution over time.  While using a faster converging series for time may help I think there are confounding factors that limit effect here.  Consider the 1 core on a 64 core system example above.  With only 3.905ms per pool we are going to quickly hit the case where we are borrowing not-useful periods of time while thrashing locks.

Quoted 6 lines

We are in the midst of an implementation for proposal above which we'll have ready post to here for consideration next week.  We have maintained your existing approach with respect to handling throttled entities and layered on top of that the proposed alternate local/global bandwidth scheme.  Initial tests show very promising results!

Nice. Look forward to your patches.

Regards,
Bharata.

Quoted 77 lines · Paul Turner

Quoted 62 lines · Bharata B Rao

Quoted 53 lines · Paul Turner

Quoted 22 lines · Bharata B Rao

Quoted 14 lines · Paul Turner

What are your thoughts on using a separate mechanism for the general case.  A draft proposal follows:

- Maintain a global run-time pool for each tg.  The runtime specified by the user represents the value that this pool will be refilled to each period.
- We continue to maintain the local notion of runtime/period in each cfs_rq, continue to accumulate locally here.

Upon locally exceeding the period acquire new credit from the global pool (either under lock or more likely using atomic ops).  This can either be in fixed steppings (e.g. 10ms, could be tunable) or following some quasi-curve variant with historical demand.

Quoted 6 lines

One caveat here is that there is some over-commit in the system, the local differences of runtime vs period represent additional over the global pool. However it should not be possible to consistently exceed limits since the rate of refill is gated by the runtime being input into the system via the per-tg pool.

Quoted 5 lines

We borrow from what is actually available as spare (spare = unused or remaining). With global pool, I see that would be difficult. Inability/difficulty in keeping the global pool in sync with the actual available spare time is the reason for over-commit ?

We maintain two pools, a global pool (new) and a per-cfs_rq pool (similar to existing rt_bw).

When consuming time you charge vs your local bandwidth until it is expired, at this point you must either refill from the global pool, or throttle.

The "slack" in the system is the sum of unconsumed time in local pools from the *previous* global pool refill.  This is bounded above by the size of time you refill a local pool at each expiry.  We call the size of refill a 'slice'.

e.g.

Task limit of 50ms, slice=10ms, 4cpus, period of 500ms

Task A runs on cpus 0 and 1 for 5ms each, then blocks.

When A first executes on each cpu we take slice=10ms from the global pool of 50ms and apply it to the local rq.  Execution then proceeds vs local pool.

Current state is: 5 ms in local pools on {0,1}, 30ms remaining in global pool

Quoted 7 lines

Upon period expiration we issue a global pool refill.  At this point we have:
5 ms in local pools on {0,1}, 50ms remaining in global pool.

That 10ms of slack time is over-commit in the system.  However it should be clear that this can only be a local effect since over any period of time the rate of input into the system is limited by global pool refill rate.

Quoted 6 lines

With the same setup as above consider 5 such tasks which block after consuming 5ms each. So now we have 25ms slack time. In the next bandwidth period if 5 cpu hogs start running and they would consume this 25ms and the 50ms from this period. So we gave 50% extra to a group in a bandwidth period. Just wondering how common such scenarious could be.

Yes within a single given period you may exceed your reservation due to slack.  However, of note is that across any 2 successive periods you are guaranteed to be within your reservation, i.e. 2*usage <= 2*period, as slack available means that you under-consumed your previous period.

Quoted 4 lines

For those needing a hard guarantee (independent of amelioration strategies) halving the period provided would then provide this across their target period with the basic v1 implementation.

Actually now that I think about it, this observation only holds when the slack is consumed within the second of the two periods. It should be restated something like:

for any n contiguous periods your maximum usage is n*runtime + nr_cpus*slice, note the slack term is constant and is dominated for any observation window involving several periods

Quoted 87 lines · Paul Turner

Quoted 77 lines · Paul Turner

Quoted 62 lines · Bharata B Rao

Quoted 53 lines · Paul Turner

Quoted 22 lines · Bharata B Rao

Quoted 14 lines · Paul Turner

What are your thoughts on using a separate mechanism for the general case.  A draft proposal follows:

- Maintain a global run-time pool for each tg.  The runtime specified by the user represents the value that this pool will be refilled to each period.
- We continue to maintain the local notion of runtime/period in each cfs_rq, continue to accumulate locally here.

Upon locally exceeding the period acquire new credit from the global pool (either under lock or more likely using atomic ops).  This can either be in fixed steppings (e.g. 10ms, could be tunable) or following some quasi-curve variant with historical demand.

Quoted 6 lines

One caveat here is that there is some over-commit in the system, the local differences of runtime vs period represent additional over the global pool. However it should not be possible to consistently exceed limits since the rate of refill is gated by the runtime being input into the system via the per-tg pool.

Quoted 5 lines

We borrow from what is actually available as spare (spare = unused or remaining). With global pool, I see that would be difficult. Inability/difficulty in keeping the global pool in sync with the actual available spare time is the reason for over-commit ?

We maintain two pools, a global pool (new) and a per-cfs_rq pool (similar to existing rt_bw).

When consuming time you charge vs your local bandwidth until it is expired, at this point you must either refill from the global pool, or throttle.

The "slack" in the system is the sum of unconsumed time in local pools from the *previous* global pool refill.  This is bounded above by the size of time you refill a local pool at each expiry.  We call the size of refill a 'slice'.

e.g.

Task limit of 50ms, slice=10ms, 4cpus, period of 500ms

Task A runs on cpus 0 and 1 for 5ms each, then blocks.

When A first executes on each cpu we take slice=10ms from the global pool of 50ms and apply it to the local rq.  Execution then proceeds vs local pool.

Current state is: 5 ms in local pools on {0,1}, 30ms remaining in global pool

Quoted 7 lines

Upon period expiration we issue a global pool refill.  At this point we have:
5 ms in local pools on {0,1}, 50ms remaining in global pool.

That 10ms of slack time is over-commit in the system.  However it should be clear that this can only be a local effect since over any period of time the rate of input into the system is limited by global pool refill rate.

Quoted 6 lines

With the same setup as above consider 5 such tasks which block after consuming 5ms each. So now we have 25ms slack time. In the next bandwidth period if 5 cpu hogs start running and they would consume this 25ms and the 50ms from this period. So we gave 50% extra to a group in a bandwidth period. Just wondering how common such scenarious could be.

Yes within a single given period you may exceed your reservation due to slack.  However, of note is that across any 2 successive periods you are guaranteed to be within your reservation, i.e. 2*usage <= 2*period, as slack available means that you under-consumed your previous period.

Quoted 4 lines

For those needing a hard guarantee (independent of amelioration strategies) halving the period provided would then provide this across their target period with the basic v1 implementation.

Actually now that I think about it, this observation only holds when the slack is consumed within the second of the two periods.  It should be restated something like:

Quoted 3 lines

for any n contiguous periods your maximum usage is n*runtime + nr_cpus*slice, note the slack term is constant and is dominated for any observation window involving several periods

Ok. We are talking about 'hard limits' here and looks like there is a theoritical possibility of exceeding the limit often. Need to understand how good/bad this is in real life.

Regards,
Bharata.

I'm really glad that we're having this discussion however it feels like we are rat-holing a little on the handling of slack? As an issue

it seems a non-starter since if necessary it can be scrubbed with the same overhead as the original proposal for period refresh (i.e. remove slack from each cpu). There are also trivial faster ways to zero it without this O(n) overhead.

I feel it would be more productive to focus discussion on other areas of design such as load balancer interaction, distribution from global to local pools, entity placement and fairness on wakeup, etc.

Quoted 4 lines

Regards,
Bharata.