Skip to contentSkip to conversation

Use EDF to throttle RT task groups

RFC PATCH In review Fabio Checconi 2 participants 17 messages Jun 15, 2009 – Jul 15, 2009

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

cover Use EDF to throttle RT task groups

This patchset introduces a group level EDF scheduler to extend the current throttling mechanism, in order to make it support generic period assignments. With this patch, the rt_runtime and rt_period parameters can be used to specify arbitrary CPU reservations for RT tasks.

The first two patches fix two problems of the current implementation.

This is an early RFC, I'm interested in having an idea of what people think about this feature, if it's worth working on it, what can be improved in the design, etc.

The main design issues involved:

- It is no more possible to specify RUNTIME_INF for a task group when throttling is enabled. Rationale: supporting both throttled and unthrottled groups would have required too much extra complexity (I didn't find anything simpler than two parallel runqueues, one for throttled and one for unthrottled groups).

- Since it is not easy to mix tasks and groups on the same scheduler queue (tasks have no deadlines), the bandwidth reserved to the tasks in a group is controlled with two additional cgroup attributes:
rt_task_runtime_us and rt_task_period_us. These attrinutes control, within a cgroup, how much bandwidth is reserved to the tasks it contains.

- Shared resources are still handled using boosting. When a group contains a task inside a critical section it is scheduled according the highest priority among the ones of the tasks it contains. In this way, the same group has two modes: when it is not boosted it is scheduled according to its deadline; when it is boosted, it is scheduled according its priority. Boosted groups are always favored over non-boosted ones.

- The old priority array is now gone. To use only a single data structure for entities using both priorities and deadlines (due to boosting), the only possible choice was to use an rb-tree; the function used to order the keys takes into account the prioritization described above (boosted tasks, ordered by priority are favored to non-boosted tasks, ordered by increasing deadline).

- Given that the various rt_rq's belonging to the same task group are activated independently, there is the need of a timer per each rt_rq.

The patchset is against sched-devel, and (temporarily) depends on CONFIG_RT_GROUP_SCHED.

Any kind of feedback is welcome.

Fabio Checconi (8):
Fix rt_rq->pushable_tasks initialization in init_rt_rq() Fix hrtick handling
Replace struct prio_array with an RB tree Remove the balancing logic
Use EDF to throttle RT tasks hierarchically Modify the curr/next priority tracking Reprogram timers only when necessary
Use hrtick when available

 include/linux/init_task.h |    1 -
 include/linux/sched.h     |    2 +-
 kernel/sched.c            |  553 +++++++++++++++++++++++++------------
 kernel/sched_debug.c      |    4 +-
 kernel/sched_rt.c         |  672 +++++++++++++++++++++++++++------------------
 5 files changed, 781 insertions(+), 451 deletions(-)
#1 lore raw

PATCH 1/8 Fix rt_rq->pushable_tasks initialization in init_rt_rq()

init_rt_rq() initializes only rq->rt.pushable_tasks, and not the pushable_tasks field of the passed rt_rq. The plist is not used uninitialized since the only pushable_tasks plists used are the ones of root rt_rqs; anyway reinitializing the list on every group creation corrupts the root plist, losing its previous contents.

---
 kernel/sched.c |    2 +-
 1 files changed, 1 insertions(+), 1 deletions(-)
kernel/sched.c +1 -1
index 6032f51..873b252 100644
@@ -9075,7 +9075,7 @@ static void init_rt_rq(struct rt_rq *rt_rq, struct rq *rq)
 #ifdef CONFIG_SMP
 	rt_rq->rt_nr_migratory = 0;
 	rt_rq->overloaded = 0;
-	plist_head_init(&rq->rt.pushable_tasks, &rq->lock);
+	plist_head_init(&rt_rq->pushable_tasks, &rq->lock);
 #endif
 
 	rt_rq->rt_time = 0;
Signature · 1 line
1.6.2.2
#2 lore raw

Re: [PATCH 1/8] Fix rt_rq->pushable_tasks initialization in init_rt_rq()

Quoted 7 lines · Fabio Checconi

init_rt_rq() initializes only rq->rt.pushable_tasks, and not the pushable_tasks field of the passed rt_rq. The plist is not used uninitialized since the only pushable_tasks plists used are the ones of root rt_rqs; anyway reinitializing the list on every group creation corrupts the root plist, losing its previous contents.

Good catch, I'll queue this up.

Quoted 17 lines
---
 kernel/sched.c |    2 +-
 1 files changed, 1 insertions(+), 1 deletions(-)
kernel/sched.c +1 -1
index 6032f51..873b252 100644
@@ -9075,7 +9075,7 @@ static void init_rt_rq(struct rt_rq *rt_rq, struct rq *rq)
 #ifdef CONFIG_SMP
 	rt_rq->rt_nr_migratory = 0;
 	rt_rq->overloaded = 0;
-	plist_head_init(&rq->rt.pushable_tasks, &rq->lock);
+	plist_head_init(&rt_rq->pushable_tasks, &rq->lock);
 #endif
 
 	rt_rq->rt_time = 0;
#3 lore raw

[tip:sched/urgent] sched: Fix rt_rq->pushable_tasks initialization in init_rt_rq()

In reply to Fabio Checconi
Commit-ID:  c20b08e3986c2dbfa6df1e880bf4f7159994d199
Gitweb:     http://git.kernel.org/tip/c20b08e3986c2dbfa6df1e880bf4f7159994d199
Author:     Fabio Checconi <[email protected]>
AuthorDate: Mon, 15 Jun 2009 20:56:38 +0200
Committer:  Ingo Molnar <[email protected]>
CommitDate: Fri, 10 Jul 2009 10:43:30 +0200

sched: Fix rt_rq->pushable_tasks initialization in init_rt_rq()

init_rt_rq() initializes only rq->rt.pushable_tasks, and not the pushable_tasks field of the passed rt_rq. The plist is not used uninitialized since the only pushable_tasks plists used are the ones of root rt_rqs; anyway reinitializing the list on every group creation corrupts the root plist, losing its previous contents.

LKML-Reference: <[email protected]>

CC Gregory Haskins <[email protected]>
---
 kernel/sched.c |    2 +-
 1 files changed, 1 insertions(+), 1 deletions(-)
kernel/sched.c +1 -1
index c4549bd..efecfda 100644
@@ -9093,7 +9093,7 @@ static void init_rt_rq(struct rt_rq *rt_rq, struct rq *rq)
 #ifdef CONFIG_SMP
 	rt_rq->rt_nr_migratory = 0;
 	rt_rq->overloaded = 0;
-	plist_head_init(&rq->rt.pushable_tasks, &rq->lock);
+	plist_head_init(&rt_rq->pushable_tasks, &rq->lock);
 #endif
 
 	rt_rq->rt_time = 0;
#4 lore raw

PATCH 2/8 Fix hrtick handling

In reply to Fabio Checconi

The current hrtick implementation can end up asking to the hrtimer code to wake up ksoftirqd while holding rq->lock, causing a spinlock recursion. This patch uses __hrtimer_start_range_ns() to disable the wakeup in the reprogramming path.

---
 kernel/sched.c |   20 +++++++++++++++++---
 1 files changed, 17 insertions(+), 3 deletions(-)
kernel/sched.c +17 -3
index 873b252..b8d432b 100644
@@ -1090,6 +1090,19 @@ static enum hrtimer_restart hrtick(struct hrtimer *timer)
 }
 
 #ifdef CONFIG_SMP
+static void hrtick_restart(struct hrtimer *timer)
+{
+	ktime_t hard, soft;
+	unsigned long delta;
+
+	soft = hrtimer_get_softexpires(timer);
+	hard = hrtimer_get_expires(timer);
+	delta = ktime_to_ns(ktime_sub(hard, soft));
+
+	__hrtimer_start_range_ns(timer, soft, delta,
+				 HRTIMER_MODE_ABS_PINNED, 0);
+}
+
 /*
  * called from hardirq (IPI) context
  */
@@ -1098,7 +1111,7 @@ static void __hrtick_start(void *arg)
 	struct rq *rq = arg;
 
 	spin_lock(&rq->lock);
-	hrtimer_restart(&rq->hrtick_timer);
+	hrtick_restart(&rq->hrtick_timer);
 	rq->hrtick_csd_pending = 0;
 	spin_unlock(&rq->lock);
 }
@@ -1116,7 +1129,7 @@ static void hrtick_start(struct rq *rq, u64 delay)
 	hrtimer_set_expires(timer, time);
 
 	if (rq == this_rq()) {
-		hrtimer_restart(timer);
+		hrtick_restart(timer);
 	} else if (!rq->hrtick_csd_pending) {
 		__smp_call_function_single(cpu_of(rq), &rq->hrtick_csd, 0);
 		rq->hrtick_csd_pending = 1;
@@ -1173,7 +1186,8 @@ static void init_rq_hrtick(struct rq *rq)
 	rq->hrtick_csd.info = rq;
 #endif
 
-	hrtimer_init(&rq->hrtick_timer, CLOCK_MONOTONIC, HRTIMER_MODE_REL);
+	hrtimer_init(&rq->hrtick_timer, CLOCK_MONOTONIC,
+				HRTIMER_MODE_REL_PINNED);
 	rq->hrtick_timer.function = hrtick;
 }
 #else	/* CONFIG_SCHED_HRTICK */
Signature · 1 line
1.6.2.2
#5 lore raw

Re: [PATCH 2/8] Fix hrtick handling

Quoted 4 lines · Fabio Checconi

The current hrtick implementation can end up asking to the hrtimer code to wake up ksoftirqd while holding rq->lock, causing a spinlock recursion. This patch uses __hrtimer_start_range_ns() to disable the wakeup in the reprogramming path.

Right, A while back I did the following patch and handed that to someone on IRC to continue with, but I guess that never happened.

The thing that currently gets us into trouble is that when we hrtimer_start() an already expired timer we try to run it in place. However we cannot do that in context because we might start the timer under locks that the timer callback also wants, leading to a deadlock.

The current solution is to queue it in a softirq and kick the softirq. This however has the problem that we cannot do a wakeup when holding the rq->lock, which is where __hrtimer_start*() enters.

We can avoid all of this mess by simply failing the hrtimer_start*() with -ETIME when we pass it an already expired timer, which is what the below patch does.

All that needs doing is (testing and possibly fwd porting this patch, its a few weeks old now) auditing all hrtimer usage sites to make sure the new behaviour does as expected etc..

---
 include/linux/hrtimer.h   |    5 ---
 include/linux/interrupt.h |    1 -
 kernel/hrtimer.c          |   75 ++++++++++++++++++---------------------------
 kernel/perf_counter.c     |   27 ++++++++++++----
 kernel/sched.c            |   15 +++------
 5 files changed, 55 insertions(+), 68 deletions(-)
include/linux/hrtimer.h +0 -5
index dd44de5..46a9951 100644
@@ -339,11 +339,6 @@ extern int hrtimer_start(struct hrtimer *timer, ktime_t tim,
 			 const enum hrtimer_mode mode);
 extern int hrtimer_start_range_ns(struct hrtimer *timer, ktime_t tim,
 			unsigned long range_ns, const enum hrtimer_mode mode);
-extern int
-__hrtimer_start_range_ns(struct hrtimer *timer, ktime_t tim,
-			 unsigned long delta_ns,
-			 const enum hrtimer_mode mode, int wakeup);
-
 extern int hrtimer_cancel(struct hrtimer *timer);
 extern int hrtimer_try_to_cancel(struct hrtimer *timer);
 
include/linux/interrupt.h +0 -1
index dd574d5..62d3073 100644
@@ -337,7 +337,6 @@ enum
 	BLOCK_SOFTIRQ,
 	TASKLET_SOFTIRQ,
 	SCHED_SOFTIRQ,
-	HRTIMER_SOFTIRQ,
 	RCU_SOFTIRQ,	/* Preferable RCU should always be the last softirq */
 
 	NR_SOFTIRQS
kernel/hrtimer.c +30 -45

124 lines not on this page · raw message

kernel/perf_counter.c +20 -7
index ef5d8a5..a5c0ac3 100644
@@ -3308,15 +3308,22 @@ static int cpu_clock_perf_counter_enable(struct perf_counter *counter)
 {
 	struct hw_perf_counter *hwc = &counter->hw;
 	int cpu = raw_smp_processor_id();
+	u64 period;
+	int ret;
 
 	atomic64_set(&hwc->prev_count, cpu_clock(cpu));
 	hrtimer_init(&hwc->hrtimer, CLOCK_MONOTONIC, HRTIMER_MODE_REL);
 	hwc->hrtimer.function = perf_swcounter_hrtimer;
 	if (hwc->sample_period) {
-		u64 period = max_t(u64, 10000, hwc->sample_period);
-		__hrtimer_start_range_ns(&hwc->hrtimer,
+again:
+		period = max_t(u64, 10000, hwc->sample_period);
+		ret = hrtimer_start_range_ns(&hwc->hrtimer,
 				ns_to_ktime(period), 0,
-				HRTIMER_MODE_REL, 0);
+				HRTIMER_MODE_REL);
+		if (ret == -ETIME) {
+			hwc->sample_period += period;
+			goto again;
+		}
 	}
 
 	return 0;
@@ -3357,7 +3364,8 @@ static void task_clock_perf_counter_update(struct perf_counter *counter, u64 now
 static int task_clock_perf_counter_enable(struct perf_counter *counter)
 {
 	struct hw_perf_counter *hwc = &counter->hw;
-	u64 now;
+	u64 period, now;
+	int ret;
 
 	now = counter->ctx->time;
 
@@ -3365,10 +3373,15 @@ static int task_clock_perf_counter_enable(struct perf_counter *counter)
 	hrtimer_init(&hwc->hrtimer, CLOCK_MONOTONIC, HRTIMER_MODE_REL);
 	hwc->hrtimer.function = perf_swcounter_hrtimer;
 	if (hwc->sample_period) {
-		u64 period = max_t(u64, 10000, hwc->sample_period);
-		__hrtimer_start_range_ns(&hwc->hrtimer,
+again:
+		period = max_t(u64, 10000, hwc->sample_period);
+		ret = hrtimer_start_range_ns(&hwc->hrtimer,
 				ns_to_ktime(period), 0,
-				HRTIMER_MODE_REL, 0);
+				HRTIMER_MODE_REL);
+		if (ret == -ETIME) {
+			hwc->sample_period += period;
+			goto again:
+		}
 	}
 
 	return 0;
kernel/sched.c +5 -10
index 92dbda2..4157b1c 100644
@@ -228,20 +228,15 @@ static void start_rt_bandwidth(struct rt_bandwidth *rt_b)
 
 	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);
+		hrtimer_forward(&rt_b->rt_period_timer, now, rt_b->rt_period);
+		hrtimer_start_expires(&rt_b->rt_period_timer,
+				HRTIMER_MODE_ABS_PINNED);
 	}
 	spin_unlock(&rt_b->rt_runtime_lock);
 }
@@ -1155,8 +1150,8 @@ static __init void init_hrtick(void)
  */
 static void hrtick_start(struct rq *rq, u64 delay)
 {
-	__hrtimer_start_range_ns(&rq->hrtick_timer, ns_to_ktime(delay), 0,
-			HRTIMER_MODE_REL_PINNED, 0);
+	hrtimer_start_range_ns(&rq->hrtick_timer, ns_to_ktime(delay), 0,
+			HRTIMER_MODE_REL_PINNED);
 }
 
 static inline void init_hrtick(void)
#6 lore raw

PATCH 3/8 Replace struct prio_array with an RB tree

In reply to Fabio Checconi

To store groups in deadline order the old prio_array is not enough. To keep things simple, use the same data structure to store tasks in priority order.

---
 include/linux/init_task.h |    1 -
 include/linux/sched.h     |    2 +-
 kernel/sched.c            |   25 ++-----
 kernel/sched_rt.c         |  157 +++++++++++++++++++++++++++++++--------------
 4 files changed, 117 insertions(+), 68 deletions(-)
include/linux/init_task.h +0 -1
index 28b1f30..5c698b4 100644
@@ -139,7 +139,6 @@ extern struct cred init_cred;
 		.group_node 	= LIST_HEAD_INIT(tsk.se.group_node),	\
 	},								\
 	.rt		= {						\
-		.run_list	= LIST_HEAD_INIT(tsk.rt.run_list),	\
 		.time_slice	= HZ, 					\
 		.nr_cpus_allowed = NR_CPUS,				\
 	},								\
include/linux/sched.h +1 -1
index d08b3f7..a115067 100644
@@ -1128,7 +1128,7 @@ struct sched_entity {
 };
 
 struct sched_rt_entity {
-	struct list_head run_list;
+	struct rb_node rb_node;
 	unsigned long timeout;
 	unsigned int time_slice;
 	int nr_cpus_allowed;
kernel/sched.c +8 -17
index b8d432b..675ea96 100644
@@ -157,11 +157,11 @@ static inline int task_has_rt_policy(struct task_struct *p)
 }
 
 /*
- * This is the priority-queue data structure of the RT scheduling class:
+ * This is the EDF queue data structure of the RT scheduling class:
  */
-struct rt_prio_array {
-	DECLARE_BITMAP(bitmap, MAX_RT_PRIO+1); /* include 1 bit for delimiter */
-	struct list_head queue[MAX_RT_PRIO];
+struct rt_edf_tree {
+	struct rb_root rb_root;
+	struct rb_node *rb_leftmost;
 };
 
 struct rt_bandwidth {
@@ -481,7 +481,7 @@ struct cfs_rq {
 
 /* Real-Time classes' related field in a runqueue: */
 struct rt_rq {
-	struct rt_prio_array active;
+	struct rt_edf_tree active;
 	unsigned long rt_nr_running;
 #if defined CONFIG_SMP || defined CONFIG_RT_GROUP_SCHED
 	struct {
@@ -2595,7 +2595,7 @@ static void __sched_fork(struct task_struct *p)
 	p->se.wait_max			= 0;
 #endif
 
-	INIT_LIST_HEAD(&p->rt.run_list);
+	RB_CLEAR_NODE(&p->rt.rb_node);
 	p->se.on_rq = 0;
 	INIT_LIST_HEAD(&p->se.group_node);
 
@@ -9069,16 +9069,7 @@ static void init_cfs_rq(struct cfs_rq *cfs_rq, struct rq *rq)
 
 static void init_rt_rq(struct rt_rq *rt_rq, struct rq *rq)
 {
-	struct rt_prio_array *array;
-	int i;
-
-	array = &rt_rq->active;
-	for (i = 0; i < MAX_RT_PRIO; i++) {
-		INIT_LIST_HEAD(array->queue + i);
-		__clear_bit(i, array->bitmap);
-	}
-	/* delimiter for bitsearch: */
-	__set_bit(MAX_RT_PRIO, array->bitmap);
+	rt_rq->active.rb_root = RB_ROOT;
 
 #if defined CONFIG_SMP || defined CONFIG_RT_GROUP_SCHED
 	rt_rq->highest_prio.curr = MAX_RT_PRIO;
@@ -9158,7 +9149,7 @@ static void init_tg_rt_entry(struct task_group *tg, struct rt_rq *rt_rq,
 
 	rt_se->my_q = rt_rq;
 	rt_se->parent = parent;
-	INIT_LIST_HEAD(&rt_se->run_list);
+	RB_CLEAR_NODE(&rt_se->rb_node);
 }
 #endif
 
kernel/sched_rt.c +108 -49

240 lines not on this page · raw message

Signature · 1 line
1.6.2.2
#7 lore raw

PATCH 4/8 Remove the balancing logic

In reply to Fabio Checconi

The balancing logic would require to run an admission test on each step it takes trying to balance the bandwidths assigned to each group. Now it is not doing so, and it can produce unschedulable assignments, which in turn would make EDF scheduling on each single cpu pointless. Temporarily remove it; we can add it back later, once the system proves to be stable enough.

---
 kernel/sched_rt.c |  142 -----------------------------------------------------
 1 files changed, 0 insertions(+), 142 deletions(-)
kernel/sched_rt.c +0 -142
index 7ae1212..c23f3ad 100644
@@ -287,137 +287,16 @@ static inline struct rt_bandwidth *sched_rt_bandwidth(struct rt_rq *rt_rq)
 
 #ifdef CONFIG_SMP
 /*
- * We ran out of runtime, see if we can borrow some from our neighbours.
- */
-static int do_balance_runtime(struct rt_rq *rt_rq)
-{
-	struct rt_bandwidth *rt_b = sched_rt_bandwidth(rt_rq);
-	struct root_domain *rd = cpu_rq(smp_processor_id())->rd;
-	int i, weight, more = 0;
-	u64 rt_period;
-
-	weight = cpumask_weight(rd->span);
-
-	spin_lock(&rt_b->rt_runtime_lock);
-	rt_period = ktime_to_ns(rt_b->rt_period);
-	for_each_cpu(i, rd->span) {
-		struct rt_rq *iter = sched_rt_period_rt_rq(rt_b, i);
-		s64 diff;
-
-		if (iter == rt_rq)
-			continue;
-
-		spin_lock(&iter->rt_runtime_lock);
-		/*
-		 * Either all rqs have inf runtime and there's nothing to steal
-		 * or __disable_runtime() below sets a specific rq to inf to
-		 * indicate its been disabled and disalow stealing.
-		 */
-		if (iter->rt_runtime == RUNTIME_INF)
-			goto next;
-
-		/*
-		 * From runqueues with spare time, take 1/n part of their
-		 * spare time, but no more than our period.
-		 */
-		diff = iter->rt_runtime - iter->rt_time;
-		if (diff > 0) {
-			diff = div_u64((u64)diff, weight);
-			if (rt_rq->rt_runtime + diff > rt_period)
-				diff = rt_period - rt_rq->rt_runtime;
-			iter->rt_runtime -= diff;
-			rt_rq->rt_runtime += diff;
-			more = 1;
-			if (rt_rq->rt_runtime == rt_period) {
-				spin_unlock(&iter->rt_runtime_lock);
-				break;
-			}
-		}
-next:
-		spin_unlock(&iter->rt_runtime_lock);
-	}
-	spin_unlock(&rt_b->rt_runtime_lock);
-
-	return more;
-}
-
-/*
  * Ensure this RQ takes back all the runtime it lend to its neighbours.
  */
 static void __disable_runtime(struct rq *rq)
 {
-	struct root_domain *rd = rq->rd;
 	struct rt_rq *rt_rq;
 
-	if (unlikely(!scheduler_running))
-		return;
-
 	for_each_leaf_rt_rq(rt_rq, rq) {
-		struct rt_bandwidth *rt_b = sched_rt_bandwidth(rt_rq);
-		s64 want;
-		int i;
-
-		spin_lock(&rt_b->rt_runtime_lock);
-		spin_lock(&rt_rq->rt_runtime_lock);
-		/*
-		 * Either we're all inf and nobody needs to borrow, or we're
-		 * already disabled and thus have nothing to do, or we have
-		 * exactly the right amount of runtime to take out.
-		 */
-		if (rt_rq->rt_runtime == RUNTIME_INF ||
-				rt_rq->rt_runtime == rt_b->rt_runtime)
-			goto balanced;
-		spin_unlock(&rt_rq->rt_runtime_lock);
-
-		/*
-		 * Calculate the difference between what we started out with
-		 * and what we current have, that's the amount of runtime
-		 * we lend and now have to reclaim.
-		 */
-		want = rt_b->rt_runtime - rt_rq->rt_runtime;
-
-		/*
-		 * Greedy reclaim, take back as much as we can.
-		 */
-		for_each_cpu(i, rd->span) {
-			struct rt_rq *iter = sched_rt_period_rt_rq(rt_b, i);
-			s64 diff;
-
-			/*
-			 * Can't reclaim from ourselves or disabled runqueues.
-			 */
-			if (iter == rt_rq || iter->rt_runtime == RUNTIME_INF)
-				continue;
-
-			spin_lock(&iter->rt_runtime_lock);
-			if (want > 0) {
-				diff = min_t(s64, iter->rt_runtime, want);
-				iter->rt_runtime -= diff;
-				want -= diff;
-			} else {
-				iter->rt_runtime -= want;
-				want -= want;
-			}
-			spin_unlock(&iter->rt_runtime_lock);
-
-			if (!want)
-				break;
-		}
-
 		spin_lock(&rt_rq->rt_runtime_lock);
-		/*
-		 * We cannot be left wanting - that would mean some runtime
-		 * leaked out of the system.
-		 */
-		BUG_ON(want);
-balanced:
-		/*
-		 * Disable all the borrow logic by pretending we have inf
-		 * runtime - in which case borrowing doesn't make sense.
-		 */
 		rt_rq->rt_runtime = RUNTIME_INF;
 		spin_unlock(&rt_rq->rt_runtime_lock);
-		spin_unlock(&rt_b->rt_runtime_lock);
 	}
 }
 
@@ -461,24 +340,6 @@ static void enable_runtime(struct rq *rq)
 	__enable_runtime(rq);
 	spin_unlock_irqrestore(&rq->lock, flags);
 }
-
-static int balance_runtime(struct rt_rq *rt_rq)
-{
-	int more = 0;
-
-	if (rt_rq->rt_time > rt_rq->rt_runtime) {
-		spin_unlock(&rt_rq->rt_runtime_lock);
-		more = do_balance_runtime(rt_rq);
-		spin_lock(&rt_rq->rt_runtime_lock);
-	}
-
-	return more;
-}
-#else /* !CONFIG_SMP */
-static inline int balance_runtime(struct rt_rq *rt_rq)
-{
-	return 0;
-}
 #endif /* CONFIG_SMP */
 
 static int do_sched_rt_period_timer(struct rt_bandwidth *rt_b, int overrun)
@@ -500,8 +361,6 @@ static int do_sched_rt_period_timer(struct rt_bandwidth *rt_b, int overrun)
 			u64 runtime;
 
 			spin_lock(&rt_rq->rt_runtime_lock);
-			if (rt_rq->rt_throttled)
-				balance_runtime(rt_rq);
 			runtime = rt_rq->rt_runtime;
 			rt_rq->rt_time -= min(rt_rq->rt_time, overrun*runtime);
 			if (rt_rq->rt_throttled && rt_rq->rt_time < runtime) {
@@ -544,7 +403,6 @@ static int sched_rt_runtime_exceeded(struct rt_rq *rt_rq)
 	if (sched_rt_runtime(rt_rq) >= sched_rt_period(rt_rq))
 		return 0;
 
-	balance_runtime(rt_rq);
 	runtime = sched_rt_runtime(rt_rq);
 	if (runtime == RUNTIME_INF)
 		return 0;
Signature · 1 line
1.6.2.2
#8 lore raw

PATCH 5/8 Use EDF to throttle RT tasks hierarchically

In reply to Fabio Checconi

Switch to EDF to implement throttling in sched_rt. This patch:

- introduces a struct task_rt_group to abstract an EDF runqueue,

    capable to hold both tasks and groups;
  - adds two task_rt_groups to each task_group, one to store tasks,
    and another to store subgroups;
  - modifies the sched_rt class hooks in order to use the two
    task_rt_groups;

- modifies the admission control code, in order to take into account of the new task-only subgroup.

Using two different runqueues is necessary because tasks have no deadlines and cannot be mixed with groups, that now are scheduled by deadline (assigned implicitly by the throttling algorithm).

---
 kernel/sched.c       |  508 ++++++++++++++++++++++++++++++++++----------------
 kernel/sched_debug.c |    4 +-
 kernel/sched_rt.c    |  288 +++++++++++++++++++++--------
 3 files changed, 559 insertions(+), 241 deletions(-)
kernel/sched.c +349 -159
index 675ea96..bdae263 100644
@@ -169,34 +169,10 @@ struct rt_bandwidth {
 	spinlock_t		rt_runtime_lock;
 	ktime_t			rt_period;
 	u64			rt_runtime;
-	struct hrtimer		rt_period_timer;
 };
 
 static struct rt_bandwidth def_rt_bandwidth;
 
-static int do_sched_rt_period_timer(struct rt_bandwidth *rt_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);
-	ktime_t now;
-	int overrun;
-	int idle = 0;
-
-	for (;;) {
-		now = hrtimer_cb_get_time(timer);
-		overrun = hrtimer_forward(timer, now, rt_b->rt_period);
-
-		if (!overrun)
-			break;
-
-		idle = do_sched_rt_period_timer(rt_b, overrun);
-	}
-
-	return idle ? HRTIMER_NORESTART : HRTIMER_RESTART;
-}
-
 static
 void init_rt_bandwidth(struct rt_bandwidth *rt_b, u64 period, u64 runtime)
 {
@@ -204,10 +180,6 @@ void init_rt_bandwidth(struct rt_bandwidth *rt_b, u64 period, u64 runtime)
 	rt_b->rt_runtime = runtime;
 
 	spin_lock_init(&rt_b->rt_runtime_lock);
-
-	hrtimer_init(&rt_b->rt_period_timer,
-			CLOCK_MONOTONIC, HRTIMER_MODE_REL);
-	rt_b->rt_period_timer.function = sched_rt_period_timer;
 }
 
 static inline int rt_bandwidth_enabled(void)
@@ -215,43 +187,6 @@ static inline int rt_bandwidth_enabled(void)
 	return sysctl_sched_rt_runtime >= 0;
 }
 
-static void start_rt_bandwidth(struct rt_bandwidth *rt_b)
-{
-	ktime_t now;
-
-	if (!rt_bandwidth_enabled() || rt_b->rt_runtime == RUNTIME_INF)
-		return;
-
-	if (hrtimer_active(&rt_b->rt_period_timer))
-		return;
-
-	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);
-	}
-	spin_unlock(&rt_b->rt_runtime_lock);
-}
-
-#ifdef CONFIG_RT_GROUP_SCHED
-static void destroy_rt_bandwidth(struct rt_bandwidth *rt_b)
-{
-	hrtimer_cancel(&rt_b->rt_period_timer);
-}
-#endif
-
 /*
  * sched_domains_mutex serializes calls to arch_init_sched_domains,
  * detach_destroy_domains and partition_sched_domains.
@@ -266,6 +201,18 @@ struct cfs_rq;
 
 static LIST_HEAD(task_groups);
 
+#ifdef CONFIG_RT_GROUP_SCHED
+struct task_group;
+
+struct task_rt_group {
+	struct sched_rt_entity **rt_se;
+	struct rt_rq **rt_rq;
+
+	struct rt_bandwidth rt_bandwidth;
+	struct task_group *tg;
+};
+#endif
+
 /* task group related information */
 struct task_group {
 #ifdef CONFIG_CGROUP_SCHED
@@ -285,10 +232,8 @@ struct task_group {
 #endif
 
 #ifdef CONFIG_RT_GROUP_SCHED
-	struct sched_rt_entity **rt_se;
-	struct rt_rq **rt_rq;
-
-	struct rt_bandwidth rt_bandwidth;
+	struct task_rt_group rt_rq_group;
+	struct task_rt_group rt_task_group;
 #endif
 
 	struct rcu_head rcu;
@@ -324,9 +269,17 @@ static DEFINE_PER_CPU(struct cfs_rq, init_cfs_rq) ____cacheline_aligned_in_smp;
 #ifdef CONFIG_RT_GROUP_SCHED
 static DEFINE_PER_CPU(struct sched_rt_entity, init_sched_rt_entity);
 static DEFINE_PER_CPU(struct rt_rq, init_rt_rq) ____cacheline_aligned_in_smp;
+static DEFINE_PER_CPU(struct sched_rt_entity, init_sched_rt_task_entity);
+static DEFINE_PER_CPU(struct rt_rq, init_rt_task_rq) \
+			____cacheline_aligned_in_smp;
 #endif /* CONFIG_RT_GROUP_SCHED */
 #else /* !CONFIG_USER_SCHED */
 #define root_task_group init_task_group
+#ifdef CONFIG_RT_GROUP_SCHED
+static DEFINE_PER_CPU(struct sched_rt_entity, init_sched_rt_task_entity);
+static DEFINE_PER_CPU(struct rt_rq, init_rt_task_rq) \
+			____cacheline_aligned_in_smp;
+#endif
 #endif /* CONFIG_USER_SCHED */
 
 /* task_group_lock serializes add/remove of task groups and also changes to
@@ -394,8 +347,8 @@ static inline void set_task_rq(struct task_struct *p, unsigned int cpu)
 #endif
 
 #ifdef CONFIG_RT_GROUP_SCHED
-	p->rt.rt_rq  = task_group(p)->rt_rq[cpu];
-	p->rt.parent = task_group(p)->rt_se[cpu];
+	p->rt.rt_rq  = task_group(p)->rt_task_group.rt_rq[cpu];
+	p->rt.parent = task_group(p)->rt_task_group.rt_se[cpu];
 #endif
 }
 
@@ -496,22 +449,31 @@ struct rt_rq {
 	int overloaded;
 	struct plist_head pushable_tasks;
 #endif
-	int rt_throttled;
+	int rt_flags;
+
+	u64 rt_deadline;
 	u64 rt_time;
 	u64 rt_runtime;
+	ktime_t rt_period;
+
+	struct hrtimer rt_period_timer;
+
 	/* Nests inside the rq lock: */
 	spinlock_t rt_runtime_lock;
 
-#ifdef CONFIG_RT_GROUP_SCHED
 	unsigned long rt_nr_boosted;
 
+#ifdef CONFIG_RT_GROUP_SCHED
 	struct rq *rq;
 	struct list_head leaf_rt_rq_list;
-	struct task_group *tg;
+	struct task_rt_group *rt_tg;
 	struct sched_rt_entity *rt_se;
 #endif
 };
 
+#define RT_RQ_THROTTLED		1
+#define RT_RQ_NEEDS_UPDATE	2
+
 #ifdef CONFIG_SMP
 
 /*
@@ -6176,7 +6138,7 @@ recheck:
 		 * assigned.
 		 */
 		if (rt_bandwidth_enabled() && rt_policy(policy) &&
-				task_group(p)->rt_bandwidth.rt_runtime == 0)
+		    task_group(p)->rt_task_group.rt_bandwidth.rt_runtime == 0)
 			return -EPERM;
 #endif
 
@@ -9084,7 +9046,7 @@ static void init_rt_rq(struct rt_rq *rt_rq, struct rq *rq)
 #endif
 
 	rt_rq->rt_time = 0;
-	rt_rq->rt_throttled = 0;
+	rt_rq->rt_flags = 0;
 	rt_rq->rt_runtime = 0;
 	spin_lock_init(&rt_rq->rt_runtime_lock);
 
@@ -9124,21 +9086,57 @@ static void init_tg_cfs_entry(struct task_group *tg, struct cfs_rq *cfs_rq,
 #endif
 
 #ifdef CONFIG_RT_GROUP_SCHED
-static void init_tg_rt_entry(struct task_group *tg, struct rt_rq *rt_rq,
-		struct sched_rt_entity *rt_se, int cpu, int add,
-		struct sched_rt_entity *parent)
+static void init_tg_rt_rq(struct rt_rq *rt_rq, struct task_rt_group *rt_tg,
+			  int cpu, struct sched_rt_entity *rt_se,
+			  struct sched_rt_entity *parent)
 {
 	struct rq *rq = cpu_rq(cpu);
 
-	tg->rt_rq[cpu] = rt_rq;
+	rt_tg->rt_rq[cpu] = rt_rq;
 	init_rt_rq(rt_rq, rq);
-	rt_rq->tg = tg;
+	rt_rq->rt_tg = rt_tg;
 	rt_rq->rt_se = rt_se;
-	rt_rq->rt_runtime = tg->rt_bandwidth.rt_runtime;
+
+	rt_rq->rt_runtime = rt_tg->rt_bandwidth.rt_runtime;
+	rt_rq->rt_period = rt_tg->rt_bandwidth.rt_period;
+
+	hrtimer_init(&rt_rq->rt_period_timer,
+		     CLOCK_MONOTONIC, HRTIMER_MODE_REL);
+	rt_rq->rt_period_timer.function = sched_rt_period_timer;
+
+	if (!rt_se)
+		return;
+
+	rt_tg->rt_se[cpu] = rt_se;
+	rt_se->parent = parent;
+	rt_se->my_q = rt_rq;
+	RB_CLEAR_NODE(&rt_se->rb_node);
+}
+
+static void init_tg_rt_entry(struct task_group *tg, struct rt_rq *rt_rq,
+		struct sched_rt_entity *rt_se, struct rt_rq *rt_task_rq,
+		struct sched_rt_entity *rt_task_se, int cpu, int add,
+		struct sched_rt_entity *parent)
+{
+	struct rq *rq = cpu_rq(cpu);
+
+	init_tg_rt_rq(rt_rq, &tg->rt_rq_group, cpu, rt_se, parent);
+
 	if (add)
 		list_add(&rt_rq->leaf_rt_rq_list, &rq->leaf_rt_rq_list);
 
-	tg->rt_se[cpu] = rt_se;
+	if (rt_task_rq) {
+		init_tg_rt_rq(rt_task_rq, &tg->rt_task_group,
+			      cpu, rt_task_se, rt_se);
+
+		if (add) {
+			list_add(&rt_task_rq->leaf_rt_rq_list,
+				 &rq->leaf_rt_rq_list);
+		}
+
+		rt_task_se->rt_rq = rt_rq;
+	}
+
 	if (!rt_se)
 		return;
 
@@ -9147,9 +9145,6 @@ static void init_tg_rt_entry(struct task_group *tg, struct rt_rq *rt_rq,
 	else
 		rt_se->rt_rq = parent->my_q;
 
-	rt_se->my_q = rt_rq;
-	rt_se->parent = parent;
-	RB_CLEAR_NODE(&rt_se->rb_node);
 }
 #endif
 
@@ -9162,7 +9157,7 @@ void __init sched_init(void)
 	alloc_size += 2 * nr_cpu_ids * sizeof(void **);
 #endif
 #ifdef CONFIG_RT_GROUP_SCHED
-	alloc_size += 2 * nr_cpu_ids * sizeof(void **);
+	alloc_size += 4 * nr_cpu_ids * sizeof(void **);
 #endif
 #ifdef CONFIG_USER_SCHED
 	alloc_size *= 2;
@@ -9193,17 +9188,32 @@ void __init sched_init(void)
 #endif /* CONFIG_USER_SCHED */
 #endif /* CONFIG_FAIR_GROUP_SCHED */
 #ifdef CONFIG_RT_GROUP_SCHED
-		init_task_group.rt_se = (struct sched_rt_entity **)ptr;
+		init_task_group.rt_rq_group.rt_se =
+					(struct sched_rt_entity **)ptr;
 		ptr += nr_cpu_ids * sizeof(void **);
 
-		init_task_group.rt_rq = (struct rt_rq **)ptr;
+		init_task_group.rt_rq_group.rt_rq = (struct rt_rq **)ptr;
 		ptr += nr_cpu_ids * sizeof(void **);
 
+		init_task_group.rt_task_group.rt_se =
+					(struct sched_rt_entity **)ptr;
+		ptr += nr_cpu_ids * sizeof(void **);
+
+		init_task_group.rt_task_group.rt_rq = (struct rt_rq **)ptr;
+		ptr += nr_cpu_ids * sizeof(void **);
 #ifdef CONFIG_USER_SCHED
-		root_task_group.rt_se = (struct sched_rt_entity **)ptr;
+		root_task_group.rt_rq_group.rt_se =
+					(struct sched_rt_entity **)ptr;
 		ptr += nr_cpu_ids * sizeof(void **);
 
-		root_task_group.rt_rq = (struct rt_rq **)ptr;
+		root_task_group.rt_rq_group.rt_rq = (struct rt_rq **)ptr;
+		ptr += nr_cpu_ids * sizeof(void **);
+
+		root_task_group.rt_task_group.rt_se =
+					(struct sched_rt_entity **)ptr;
+		ptr += nr_cpu_ids * sizeof(void **);
+
+		root_task_group.rt_task_group.rt_rq = (struct rt_rq **)ptr;
 		ptr += nr_cpu_ids * sizeof(void **);
 #endif /* CONFIG_USER_SCHED */
 #endif /* CONFIG_RT_GROUP_SCHED */
@@ -9223,11 +9233,19 @@ void __init sched_init(void)
 			global_rt_period(), global_rt_runtime());
 
 #ifdef CONFIG_RT_GROUP_SCHED
-	init_rt_bandwidth(&init_task_group.rt_bandwidth,
+	init_rt_bandwidth(&init_task_group.rt_rq_group.rt_bandwidth,
+			global_rt_period(), global_rt_runtime());
+	init_rt_bandwidth(&init_task_group.rt_task_group.rt_bandwidth,
 			global_rt_period(), global_rt_runtime());
+	init_task_group.rt_rq_group.tg = &init_task_group;
+	init_task_group.rt_task_group.tg = &init_task_group;
 #ifdef CONFIG_USER_SCHED
-	init_rt_bandwidth(&root_task_group.rt_bandwidth,
+	init_rt_bandwidth(&root_task_group.rt_rq_group.rt_bandwidth,
+			global_rt_period(), RUNTIME_INF);
+	init_rt_bandwidth(&root_task_group.rt_task_group.rt_bandwidth,
 			global_rt_period(), RUNTIME_INF);
+	root_task_group.rt_rq_group.tg = &root_task_group;
+	root_task_group.rt_task_group.tg = &root_task_group;
 #endif /* CONFIG_USER_SCHED */
 #endif /* CONFIG_RT_GROUP_SCHED */
 
@@ -9302,13 +9320,19 @@ void __init sched_init(void)
 #ifdef CONFIG_RT_GROUP_SCHED
 		INIT_LIST_HEAD(&rq->leaf_rt_rq_list);
 #ifdef CONFIG_CGROUP_SCHED
-		init_tg_rt_entry(&init_task_group, &rq->rt, NULL, i, 1, NULL);
+		init_tg_rt_entry(&init_task_group, &rq->rt, NULL,
+				 &per_cpu(init_rt_task_rq, i),
+				 &per_cpu(init_sched_rt_task_entity, i),
+				 i, 1, NULL);
 #elif defined CONFIG_USER_SCHED
-		init_tg_rt_entry(&root_task_group, &rq->rt, NULL, i, 0, NULL);
+		init_tg_rt_entry(&root_task_group, &rq->rt, NULL,
+				 NULL, NULL, i, 0, NULL);
 		init_tg_rt_entry(&init_task_group,
-				&per_cpu(init_rt_rq, i),
-				&per_cpu(init_sched_rt_entity, i), i, 1,
-				root_task_group.rt_se[i]);
+				 &per_cpu(init_rt_rq, i),
+				 &per_cpu(init_sched_rt_entity, i),
+				 &per_cpu(init_rt_task_rq, i),
+				 &per_cpu(init_sched_rt_task_entity, i),
+				 i, 1, root_task_group.rt_rq_group.rt_se[i]);
 #endif
 #endif
 
@@ -9601,40 +9625,61 @@ static inline void unregister_fair_sched_group(struct task_group *tg, int cpu)
 #endif /* CONFIG_FAIR_GROUP_SCHED */
 
 #ifdef CONFIG_RT_GROUP_SCHED
-static void free_rt_sched_group(struct task_group *tg)
+
+static void free_rt_task_group(struct task_rt_group *rt_tg)
 {
 	int i;
 
-	destroy_rt_bandwidth(&tg->rt_bandwidth);
-
 	for_each_possible_cpu(i) {
-		if (tg->rt_rq)
-			kfree(tg->rt_rq[i]);
-		if (tg->rt_se)
-			kfree(tg->rt_se[i]);
+		if (rt_tg->rt_rq[i]) {
+			hrtimer_cancel(&rt_tg->rt_rq[i]->rt_period_timer);
+			kfree(rt_tg->rt_rq[i]);
+		}
+		if (rt_tg->rt_se[i])
+			kfree(rt_tg->rt_se[i]);
 	}
 
-	kfree(tg->rt_rq);
-	kfree(tg->rt_se);
+	kfree(rt_tg->rt_rq);
+	kfree(rt_tg->rt_se);
+}
+
+static void free_rt_sched_group(struct task_group *tg)
+{
+	free_rt_task_group(&tg->rt_rq_group);
+	free_rt_task_group(&tg->rt_task_group);
 }
 
 static
 int alloc_rt_sched_group(struct task_group *tg, struct task_group *parent)
 {
-	struct rt_rq *rt_rq;
-	struct sched_rt_entity *rt_se;
+	struct rt_rq *rt_rq, *rt_task_rq;
+	struct sched_rt_entity *rt_se, *rt_task_se;
 	struct rq *rq;
 	int i;
 
-	tg->rt_rq = kzalloc(sizeof(rt_rq) * nr_cpu_ids, GFP_KERNEL);
-	if (!tg->rt_rq)
+	tg->rt_rq_group.rt_rq = kzalloc(sizeof(rt_rq) * nr_cpu_ids, GFP_KERNEL);
+	if (!tg->rt_rq_group.rt_rq)
+		goto err;
+	tg->rt_rq_group.rt_se = kzalloc(sizeof(rt_se) * nr_cpu_ids, GFP_KERNEL);
+	if (!tg->rt_rq_group.rt_se)
+		goto err;
+
+	tg->rt_task_group.rt_rq = kzalloc(sizeof(rt_rq) * nr_cpu_ids,
+					  GFP_KERNEL);
+	if (!tg->rt_task_group.rt_rq)
 		goto err;
-	tg->rt_se = kzalloc(sizeof(rt_se) * nr_cpu_ids, GFP_KERNEL);
-	if (!tg->rt_se)
+	tg->rt_task_group.rt_se = kzalloc(sizeof(rt_se) * nr_cpu_ids,
+					  GFP_KERNEL);
+	if (!tg->rt_task_group.rt_se)
 		goto err;
 
-	init_rt_bandwidth(&tg->rt_bandwidth,
+	init_rt_bandwidth(&tg->rt_rq_group.rt_bandwidth,
+			ktime_to_ns(def_rt_bandwidth.rt_period), 0);
+	tg->rt_rq_group.tg = tg;
+
+	init_rt_bandwidth(&tg->rt_task_group.rt_bandwidth,
 			ktime_to_ns(def_rt_bandwidth.rt_period), 0);
+	tg->rt_task_group.tg = tg;
 
 	for_each_possible_cpu(i) {
 		rq = cpu_rq(i);
@@ -9647,26 +9692,49 @@ int alloc_rt_sched_group(struct task_group *tg, struct task_group *parent)
 		rt_se = kzalloc_node(sizeof(struct sched_rt_entity),
 				     GFP_KERNEL, cpu_to_node(i));
 		if (!rt_se)
-			goto err;
+			goto free_rt_rq;
+
+		rt_task_rq = kzalloc_node(sizeof(struct rt_rq),
+					  GFP_KERNEL, cpu_to_node(i));
+		if (!rt_task_rq)
+			goto free_rt_se;
+
+		rt_task_se = kzalloc_node(sizeof(struct sched_rt_entity),
+					  GFP_KERNEL, cpu_to_node(i));
+		if (!rt_task_se)
+			goto free_rt_task_rq;
 
-		init_tg_rt_entry(tg, rt_rq, rt_se, i, 0, parent->rt_se[i]);
+		init_tg_rt_entry(tg, rt_rq, rt_se, rt_task_rq, rt_task_se,
+				 i, 0, parent->rt_rq_group.rt_se[i]);
 	}
 
 	return 1;
 
+ free_rt_task_rq:
+	kfree(rt_task_rq);
+
+ free_rt_se:
+	kfree(rt_se);
+
+ free_rt_rq:
+	kfree(rt_rq);
+
  err:
 	return 0;
 }
 
 static inline void register_rt_sched_group(struct task_group *tg, int cpu)
 {
-	list_add_rcu(&tg->rt_rq[cpu]->leaf_rt_rq_list,
+	list_add_rcu(&tg->rt_rq_group.rt_rq[cpu]->leaf_rt_rq_list,
+			&cpu_rq(cpu)->leaf_rt_rq_list);
+	list_add_rcu(&tg->rt_task_group.rt_rq[cpu]->leaf_rt_rq_list,
 			&cpu_rq(cpu)->leaf_rt_rq_list);
 }
 
 static inline void unregister_rt_sched_group(struct task_group *tg, int cpu)
 {
-	list_del_rcu(&tg->rt_rq[cpu]->leaf_rt_rq_list);
+	list_del_rcu(&tg->rt_rq_group.rt_rq[cpu]->leaf_rt_rq_list);
+	list_del_rcu(&tg->rt_task_group.rt_rq[cpu]->leaf_rt_rq_list);
 }
 #else /* !CONFIG_RT_GROUP_SCHED */
 static inline void free_rt_sched_group(struct task_group *tg)
@@ -9911,7 +9979,7 @@ static inline int tg_has_rt_tasks(struct task_group *tg)
 	struct task_struct *g, *p;
 
 	do_each_thread(g, p) {
-		if (rt_task(p) && rt_rq_of_se(&p->rt)->tg == tg)
+		if (rt_task(p) && rt_rq_of_se(&p->rt)->rt_tg->tg == tg)
 			return 1;
 	} while_each_thread(g, p);
 
@@ -9922,19 +9990,58 @@ struct rt_schedulable_data {
 	struct task_group *tg;
 	u64 rt_period;
 	u64 rt_runtime;
+	int rt_task_group;
 };
 
+static inline void rt_tg_parameters(struct task_rt_group *rt_tg,
+				    u64 *period, u64 *runtime)
+{
+	struct rt_bandwidth *rt_b = &rt_tg->rt_bandwidth;
+
+	*period = ktime_to_ns(rt_b->rt_period);
+	*runtime = rt_b->rt_runtime;
+
+}
+
+static unsigned long tg_utilization(struct task_group *tg,
+				    struct rt_schedulable_data *d)
+{
+	struct task_group *child;
+	unsigned long sum;
+	u64 period, runtime;
+
+	if (d && tg == d->tg && d->rt_task_group) {
+		period = d->rt_period;
+		runtime = d->rt_runtime;
+	} else
+		rt_tg_parameters(&tg->rt_task_group, &period, &runtime);
+
+	sum = to_ratio(period, runtime);
+
+	list_for_each_entry_rcu(child, &tg->children, siblings) {
+		if (d && child == d->tg && !d->rt_task_group) {
+			period = d->rt_period;
+			runtime = d->rt_runtime;
+		} else
+			rt_tg_parameters(&child->rt_rq_group,
+					 &period, &runtime);
+
+		sum += to_ratio(period, runtime);
+	}
+
+	return sum;
+}
+
 static int tg_schedulable(struct task_group *tg, void *data)
 {
 	struct rt_schedulable_data *d = data;
-	struct task_group *child;
-	unsigned long total, sum = 0;
+	unsigned long total, sum;
 	u64 period, runtime;
 
-	period = ktime_to_ns(tg->rt_bandwidth.rt_period);
-	runtime = tg->rt_bandwidth.rt_runtime;
+	period = ktime_to_ns(tg->rt_rq_group.rt_bandwidth.rt_period);
+	runtime = tg->rt_rq_group.rt_bandwidth.rt_runtime;
 
-	if (tg == d->tg) {
+	if (tg == d->tg && !d->rt_task_group) {
 		period = d->rt_period;
 		runtime = d->rt_runtime;
 	}
@@ -9949,7 +10056,7 @@ static int tg_schedulable(struct task_group *tg, void *data)
 	/*
 	 * Cannot have more runtime than the period.
 	 */
-	if (runtime > period && runtime != RUNTIME_INF)
+	if (runtime > period)
 		return -EINVAL;
 
 	/*
@@ -9969,17 +10076,7 @@ static int tg_schedulable(struct task_group *tg, void *data)
 	/*
 	 * The sum of our children's runtime should not exceed our own.
 	 */
-	list_for_each_entry_rcu(child, &tg->children, siblings) {
-		period = ktime_to_ns(child->rt_bandwidth.rt_period);
-		runtime = child->rt_bandwidth.rt_runtime;
-
-		if (child == d->tg) {
-			period = d->rt_period;
-			runtime = d->rt_runtime;
-		}
-
-		sum += to_ratio(period, runtime);
-	}
+	sum = tg_utilization(tg, d);
 
 	if (sum > total)
 		return -EINVAL;
@@ -9987,40 +10084,54 @@ static int tg_schedulable(struct task_group *tg, void *data)
 	return 0;
 }
 
-static int __rt_schedulable(struct task_group *tg, u64 period, u64 runtime)
+static int __rt_schedulable(struct task_group *tg, u64 period,
+			    u64 runtime, int rt_task_group)
 {
 	struct rt_schedulable_data data = {
 		.tg = tg,
 		.rt_period = period,
 		.rt_runtime = runtime,
+		.rt_task_group = rt_task_group,
 	};
 
 	return walk_tg_tree(tg_schedulable, tg_nop, &data);
 }
 
-static int tg_set_bandwidth(struct task_group *tg,
-		u64 rt_period, u64 rt_runtime)
+static void rt_rq_set_bandwidth(struct task_rt_group *rt_tg, int cpu,
+				u64 rt_period, u64 rt_runtime)
 {
+	struct rt_rq *rt_rq = rt_tg->rt_rq[cpu];
+
+	spin_lock(&rt_rq->rt_runtime_lock);
+	rt_rq->rt_runtime = rt_runtime;
+	rt_rq->rt_period = ns_to_ktime(rt_period);
+	spin_unlock(&rt_rq->rt_runtime_lock);
+}
+
+static int tg_set_bandwidth(struct task_group *tg, u64 rt_period,
+			    u64 rt_runtime, int rt_task_group)
+{
+	struct task_rt_group *rt_tg;
 	int i, err = 0;
 
 	mutex_lock(&rt_constraints_mutex);
 	read_lock(&tasklist_lock);
-	err = __rt_schedulable(tg, rt_period, rt_runtime);
+	err = __rt_schedulable(tg, rt_period, rt_runtime, rt_task_group);
 	if (err)
 		goto unlock;
 
-	spin_lock_irq(&tg->rt_bandwidth.rt_runtime_lock);
-	tg->rt_bandwidth.rt_period = ns_to_ktime(rt_period);
-	tg->rt_bandwidth.rt_runtime = rt_runtime;
+	if (rt_task_group)
+		rt_tg = &tg->rt_task_group;
+	else
+		rt_tg = &tg->rt_rq_group;
 
-	for_each_possible_cpu(i) {
-		struct rt_rq *rt_rq = tg->rt_rq[i];
+	spin_lock_irq(&rt_tg->rt_bandwidth.rt_runtime_lock);
+	rt_tg->rt_bandwidth.rt_period = ns_to_ktime(rt_period);
+	rt_tg->rt_bandwidth.rt_runtime = rt_runtime;
 
-		spin_lock(&rt_rq->rt_runtime_lock);
-		rt_rq->rt_runtime = rt_runtime;
-		spin_unlock(&rt_rq->rt_runtime_lock);
-	}
-	spin_unlock_irq(&tg->rt_bandwidth.rt_runtime_lock);
+	for_each_possible_cpu(i)
+		rt_rq_set_bandwidth(rt_tg, i, rt_period, rt_runtime);
+	spin_unlock_irq(&rt_tg->rt_bandwidth.rt_runtime_lock);
  unlock:
 	read_unlock(&tasklist_lock);
 	mutex_unlock(&rt_constraints_mutex);
@@ -10032,22 +10143,22 @@ int sched_group_set_rt_runtime(struct task_group *tg, long rt_runtime_us)
 {
 	u64 rt_runtime, rt_period;
 
-	rt_period = ktime_to_ns(tg->rt_bandwidth.rt_period);
+	rt_period = ktime_to_ns(tg->rt_rq_group.rt_bandwidth.rt_period);
 	rt_runtime = (u64)rt_runtime_us * NSEC_PER_USEC;
 	if (rt_runtime_us < 0)
 		rt_runtime = RUNTIME_INF;
 
-	return tg_set_bandwidth(tg, rt_period, rt_runtime);
+	return tg_set_bandwidth(tg, rt_period, rt_runtime, 0);
 }
 
 long sched_group_rt_runtime(struct task_group *tg)
 {
 	u64 rt_runtime_us;
 
-	if (tg->rt_bandwidth.rt_runtime == RUNTIME_INF)
+	if (tg->rt_rq_group.rt_bandwidth.rt_runtime == RUNTIME_INF)
 		return -1;
 
-	rt_runtime_us = tg->rt_bandwidth.rt_runtime;
+	rt_runtime_us = tg->rt_rq_group.rt_bandwidth.rt_runtime;
 	do_div(rt_runtime_us, NSEC_PER_USEC);
 	return rt_runtime_us;
 }
@@ -10057,19 +10168,65 @@ int sched_group_set_rt_period(struct task_group *tg, long rt_period_us)
 	u64 rt_runtime, rt_period;
 
 	rt_period = (u64)rt_period_us * NSEC_PER_USEC;
-	rt_runtime = tg->rt_bandwidth.rt_runtime;
+	rt_runtime = tg->rt_rq_group.rt_bandwidth.rt_runtime;
 
 	if (rt_period == 0)
 		return -EINVAL;
 
-	return tg_set_bandwidth(tg, rt_period, rt_runtime);
+	return tg_set_bandwidth(tg, rt_period, rt_runtime, 0);
 }
 
 long sched_group_rt_period(struct task_group *tg)
 {
 	u64 rt_period_us;
 
-	rt_period_us = ktime_to_ns(tg->rt_bandwidth.rt_period);
+	rt_period_us = ktime_to_ns(tg->rt_rq_group.rt_bandwidth.rt_period);
+	do_div(rt_period_us, NSEC_PER_USEC);
+	return rt_period_us;
+}
+
+int sched_group_set_task_rt_runtime(struct task_group *tg, long rt_runtime_us)
+{
+	u64 rt_runtime, rt_period;
+
+	rt_period = ktime_to_ns(tg->rt_task_group.rt_bandwidth.rt_period);
+	rt_runtime = (u64)rt_runtime_us * NSEC_PER_USEC;
+	if (rt_runtime_us < 0)
+		rt_runtime = RUNTIME_INF;
+
+	return tg_set_bandwidth(tg, rt_period, rt_runtime, 1);
+}
+
+long sched_group_task_rt_runtime(struct task_group *tg)
+{
+	u64 rt_runtime_us;
+
+	if (tg->rt_task_group.rt_bandwidth.rt_runtime == RUNTIME_INF)
+		return -1;
+
+	rt_runtime_us = tg->rt_task_group.rt_bandwidth.rt_runtime;
+	do_div(rt_runtime_us, NSEC_PER_USEC);
+	return rt_runtime_us;
+}
+
+int sched_group_set_task_rt_period(struct task_group *tg, long rt_period_us)
+{
+	u64 rt_runtime, rt_period;
+
+	rt_period = (u64)rt_period_us * NSEC_PER_USEC;
+	rt_runtime = tg->rt_task_group.rt_bandwidth.rt_runtime;
+
+	if (rt_period == 0)
+		return -EINVAL;
+
+	return tg_set_bandwidth(tg, rt_period, rt_runtime, 1);
+}
+
+long sched_group_task_rt_period(struct task_group *tg)
+{
+	u64 rt_period_us;
+
+	rt_period_us = ktime_to_ns(tg->rt_task_group.rt_bandwidth.rt_period);
 	do_div(rt_period_us, NSEC_PER_USEC);
 	return rt_period_us;
 }
@@ -10093,7 +10250,7 @@ static int sched_rt_global_constraints(void)
 
 	mutex_lock(&rt_constraints_mutex);
 	read_lock(&tasklist_lock);
-	ret = __rt_schedulable(NULL, 0, 0);
+	ret = __rt_schedulable(NULL, 0, 0, 0);
 	read_unlock(&tasklist_lock);
 	mutex_unlock(&rt_constraints_mutex);
 
@@ -10103,7 +10260,7 @@ static int sched_rt_global_constraints(void)
 int sched_rt_can_attach(struct task_group *tg, struct task_struct *tsk)
 {
 	/* Don't accept realtime tasks when there is no way for them to run */
-	if (rt_task(tsk) && tg->rt_bandwidth.rt_runtime == 0)
+	if (rt_task(tsk) && tg->rt_task_group.rt_bandwidth.rt_runtime == 0)
 		return 0;
 
 	return 1;
@@ -10131,6 +10288,7 @@ static int sched_rt_global_constraints(void)
 
 		spin_lock(&rt_rq->rt_runtime_lock);
 		rt_rq->rt_runtime = global_rt_runtime();
+		rt_rq->rt_period = ns_to_ktime(global_rt_period());
 		spin_unlock(&rt_rq->rt_runtime_lock);
 	}
 	spin_unlock_irqrestore(&def_rt_bandwidth.rt_runtime_lock, flags);
@@ -10254,6 +10412,17 @@ static s64 cpu_rt_runtime_read(struct cgroup *cgrp, struct cftype *cft)
 	return sched_group_rt_runtime(cgroup_tg(cgrp));
 }
 
+static int cpu_rt_task_runtime_write(struct cgroup *cgrp, struct cftype *cft,
+				     s64 val)
+{
+	return sched_group_set_task_rt_runtime(cgroup_tg(cgrp), val);
+}
+
+static s64 cpu_rt_task_runtime_read(struct cgroup *cgrp, struct cftype *cft)
+{
+	return sched_group_task_rt_runtime(cgroup_tg(cgrp));
+}
+
 static int cpu_rt_period_write_uint(struct cgroup *cgrp, struct cftype *cftype,
 		u64 rt_period_us)
 {
@@ -10264,6 +10433,17 @@ static u64 cpu_rt_period_read_uint(struct cgroup *cgrp, struct cftype *cft)
 {
 	return sched_group_rt_period(cgroup_tg(cgrp));
 }
+
+static int cpu_rt_task_period_write_uint(struct cgroup *cgrp,
+			struct cftype *cftype, u64 rt_period_us)
+{
+	return sched_group_set_task_rt_period(cgroup_tg(cgrp), rt_period_us);
+}
+
+static u64 cpu_rt_task_period_read_uint(struct cgroup *cgrp, struct cftype *cft)
+{
+	return sched_group_task_rt_period(cgroup_tg(cgrp));
+}
 #endif /* CONFIG_RT_GROUP_SCHED */
 
 static struct cftype cpu_files[] = {
@@ -10285,6 +10465,16 @@ static struct cftype cpu_files[] = {
 		.read_u64 = cpu_rt_period_read_uint,
 		.write_u64 = cpu_rt_period_write_uint,
 	},
+	{
+		.name = "rt_task_runtime_us",
+		.read_s64 = cpu_rt_task_runtime_read,
+		.write_s64 = cpu_rt_task_runtime_write,
+	},
+	{
+		.name = "rt_task_period_us",
+		.read_u64 = cpu_rt_task_period_read_uint,
+		.write_u64 = cpu_rt_task_period_write_uint,
+	},
 #endif
 };
 
kernel/sched_debug.c +2 -2
index 467ca72..895b2c7 100644
@@ -222,7 +222,7 @@ void print_rt_rq(struct seq_file *m, int cpu, struct rt_rq *rt_rq)
 {
 #if defined(CONFIG_CGROUP_SCHED) && defined(CONFIG_RT_GROUP_SCHED)
 	char path[128];
-	struct task_group *tg = rt_rq->tg;
+	struct task_group *tg = rt_rq->rt_tg->tg;
 
 	task_group_path(tg, path, sizeof(path));
 
@@ -238,7 +238,7 @@ void print_rt_rq(struct seq_file *m, int cpu, struct rt_rq *rt_rq)
 	SEQ_printf(m, "  .%-30s: %Ld.%06ld\n", #x, SPLIT_NS(rt_rq->x))
 
 	P(rt_nr_running);
-	P(rt_throttled);
+	P(rt_flags);
 	PN(rt_time);
 	PN(rt_runtime);
 
kernel/sched_rt.c +208 -80

430 lines not on this page · raw message

Signature · 1 line
1.6.2.2
#9 lore raw

PATCH 6/8 Modify the curr/next priority tracking

In reply to Fabio Checconi

Synchronize with the data structures used for EDF throttling the code which tracks the highest and the second-highest priority in each group.

---
 kernel/sched_rt.c |   82 ++++++++++++++++++++++++++++++++++++++++------------
 1 files changed, 63 insertions(+), 19 deletions(-)
kernel/sched_rt.c +63 -19
index 5d2353f..f43ce7b 100644
@@ -536,16 +536,57 @@ static inline struct sched_rt_entity *__rt_edf_next(struct sched_rt_entity *se)
 
 #if defined CONFIG_SMP
 
-static struct task_struct *pick_next_highest_task_rt(struct rq *rq, int cpu);
+static int is_task_rq(struct rt_rq *rt_rq)
+{
+	struct task_rt_group *rt_tg = rt_rq->rt_tg;
+	return rt_tg->tg == container_of(rt_tg, struct task_group,
+					 rt_task_group);
+}
 
-static inline int next_prio(struct rq *rq)
+static void find_highest_prios(struct rt_rq *rt_rq, int *curr, int *next)
 {
-	struct task_struct *next = pick_next_highest_task_rt(rq, rq->cpu);
+	struct sched_rt_entity *se, *next_se;
+	struct rt_rq *child;
+	struct rb_node *node;
+	int curp = MAX_RT_PRIO, nextp = MAX_RT_PRIO;
+
+	if (is_task_rq(rt_rq)) {
+		se = __rt_edf_first(&rt_rq->active);
+		if (se) {
+			curp = rt_task_of(se)->prio;
+			next_se = __rt_edf_next(se);
+			if (next_se)
+				nextp = rt_task_of(next_se)->prio;
+		}
+	} else {
+		for (node = rb_first(&rt_rq->active.rb_root);
+		     node; node = rb_next(node)) {
+			se = rb_entry(node, struct sched_rt_entity, rb_node);
+			child = group_rt_rq(se);
+
+			if (child->highest_prio.next < curp) {
+				curp = child->highest_prio.curr;
+				nextp = child->highest_prio.next;
+			} else if (child->highest_prio.curr < curp) {
+				nextp = curp;
+				curp = child->highest_prio.curr;
+				if (child->highest_prio.next < nextp)
+					nextp = child->highest_prio.next;
+			} else if (child->highest_prio.curr < nextp)
+				nextp = child->highest_prio.curr;
+		}
+	}
 
-	if (next && rt_prio(next->prio))
-		return next->prio;
-	else
-		return MAX_RT_PRIO;
+	*curr = curp;
+	*next = nextp;
+}
+
+static inline int next_prio(struct rt_rq *rt_rq)
+{
+	int curp, nextp;
+
+	find_highest_prios(rt_rq, &curp, &nextp);
+	return nextp;
 }
 
 static void
@@ -554,7 +595,6 @@ inc_rt_prio_smp(struct rt_rq *rt_rq, int prio, int prev_prio)
 	struct rq *rq = rq_of_rt_rq(rt_rq);
 
 	if (prio < prev_prio) {
-
 		/*
 		 * If the new task is higher in priority than anything on the
 		 * run-queue, we know that the previous high becomes our
@@ -576,18 +616,22 @@ inc_rt_prio_smp(struct rt_rq *rt_rq, int prio, int prev_prio)
 		/*
 		 * Otherwise, we need to recompute next-highest
 		 */
-		rt_rq->highest_prio.next = next_prio(rq);
+		rt_rq->highest_prio.next = next_prio(rt_rq);
 }
 
 static void
-dec_rt_prio_smp(struct rt_rq *rt_rq, int prio, int prev_prio)
+dec_rt_prio_smp(struct rt_rq *rt_rq, int prio, int prevp, int nextp)
 {
 	struct rq *rq = rq_of_rt_rq(rt_rq);
 
-	if (rt_rq->rt_nr_running && (prio <= rt_rq->highest_prio.next))
-		rt_rq->highest_prio.next = next_prio(rq);
+	if (rt_rq->rt_nr_running && (prio <= rt_rq->highest_prio.next)) {
+		if (nextp == -1)
+			rt_rq->highest_prio.next = next_prio(rt_rq);
+		else
+			rt_rq->highest_prio.next = nextp;
+	}
 
-	if (rq->online && rt_rq->highest_prio.curr != prev_prio)
+	if (rq->online && rt_rq->highest_prio.curr != prevp)
 		cpupri_set(&rq->rd->cpupri, rq->cpu, rt_rq->highest_prio.curr);
 }
 
@@ -596,7 +640,8 @@ dec_rt_prio_smp(struct rt_rq *rt_rq, int prio, int prev_prio)
 static inline
 void inc_rt_prio_smp(struct rt_rq *rt_rq, int prio, int prev_prio) {}
 static inline
-void dec_rt_prio_smp(struct rt_rq *rt_rq, int prio, int prev_prio) {}
+void dec_rt_prio_smp(struct rt_rq *rt_rq, int prio, int prev_prio,
+		     int next_prio) {}
 
 #endif /* CONFIG_SMP */
 
@@ -615,8 +660,7 @@ inc_rt_prio(struct rt_rq *rt_rq, int prio)
 static void
 dec_rt_prio(struct rt_rq *rt_rq, int prio)
 {
-	struct sched_rt_entity *rt_se;
-	int prev_prio = rt_rq->highest_prio.curr;
+	int prev_prio = rt_rq->highest_prio.curr, curr_prio, next_prio = -1;
 
 	if (rt_rq->rt_nr_running) {
 
@@ -627,14 +671,14 @@ dec_rt_prio(struct rt_rq *rt_rq, int prio)
 		 * we may have some recomputation to do
 		 */
 		if (prio == prev_prio) {
-			rt_se = __rt_edf_first(&rt_rq->active);
-			rt_rq->highest_prio.curr = rt_se_prio(rt_se);
+			find_highest_prios(rt_rq, &curr_prio, &next_prio);
+			rt_rq->highest_prio.curr = curr_prio;
 		}
 
 	} else
 		rt_rq->highest_prio.curr = MAX_RT_PRIO;
 
-	dec_rt_prio_smp(rt_rq, prio, prev_prio);
+	dec_rt_prio_smp(rt_rq, prio, prev_prio, next_prio);
 }
 
 #else
Signature · 1 line
1.6.2.2
#10 lore raw

PATCH 7/8 Reprogram timers only when necessary

In reply to Fabio Checconi

Avoid unnecessary timer reprogramming when a group is at its full capacity and it is already enqueued. Such a group will not need further budget recharges until it astually consumes its budget, so do not rearm its timer immediately.

---
 kernel/sched_rt.c |   19 ++++++++++++++++++-
 1 files changed, 18 insertions(+), 1 deletions(-)
kernel/sched_rt.c +18 -1
index f43ce7b..a9db16b 100644
@@ -386,6 +386,19 @@ static int do_sched_rt_period_timer(struct rt_rq *rt_rq, int overrun)
 	return idle;
 }
 
+static inline int rt_rq_needs_recharge(struct rt_rq *rt_rq)
+{
+	struct sched_rt_entity *rt_se = rt_rq->rt_se;
+
+	if (rt_rq->rt_time)
+		return 1;
+
+	if (!rt_se)
+		return 0;
+
+	return !on_rt_rq(rt_rq->rt_se);
+}
+
 static enum hrtimer_restart sched_rt_period_timer(struct hrtimer *timer)
 {
 	struct rt_rq *rt_rq = container_of(timer, struct rt_rq,
@@ -402,7 +415,8 @@ static enum hrtimer_restart sched_rt_period_timer(struct hrtimer *timer)
 		idle = do_sched_rt_period_timer(rt_rq, overrun);
 	}
 
-	return idle ? HRTIMER_NORESTART : HRTIMER_RESTART;
+	return idle || !rt_rq_needs_recharge(rt_rq) ?
+		HRTIMER_NORESTART : HRTIMER_RESTART;
 }
 
 static void start_rt_period_timer(struct rt_rq *rt_rq)
@@ -428,6 +442,9 @@ static void start_rt_period_timer(struct rt_rq *rt_rq)
 		if (overrun)
 			__do_sched_rt_period_timer(rt_rq, overrun);
 
+		if (!rt_rq_needs_recharge(rt_rq))
+			return;
+
 		soft = hrtimer_get_softexpires(&rt_rq->rt_period_timer);
 		hard = hrtimer_get_expires(&rt_rq->rt_period_timer);
 		range = ktime_to_ns(ktime_sub(hard, soft));
Signature · 1 line
1.6.2.2
#11 lore raw

PATCH 8/8 Use hrtick when available

In reply to Fabio Checconi

To have a more precise budget enforcement, use the hrtick when available. This comes at the cost of additional overhead; anyway it is disabled by default.

---
 kernel/sched_rt.c |   32 +++++++++++++++++++++++++++++++-
 1 files changed, 31 insertions(+), 1 deletions(-)
kernel/sched_rt.c +31 -1
index a9db16b..38a7be0 100644
@@ -1150,14 +1150,41 @@ static struct task_struct *_pick_next_task_rt(struct rq *rq)
 	return p;
 }
 
+static void rt_start_hrtick(struct rq *rq, struct task_struct *p)
+{
+	struct sched_rt_entity *rt_se = &p->rt;
+	struct rt_rq *rt_rq;
+	s64 delta, expires = global_rt_period();
+
+	for_each_sched_rt_entity(rt_se) {
+		rt_rq = rt_rq_of_se(rt_se);
+		delta = rt_rq->rt_runtime - rt_rq->rt_time;
+		expires = min(expires, delta);
+	}
+
+	/*
+	 * Given the current handling of hrtick in sched_fair, this
+	 * may interfere with sched_fair tasks, generating a spurious
+	 * tick when switching from an RT to a SCHED_OTHER task.
+	 * This is due to the fact that sched_fair reprograms the
+	 * hrtick only in its enqueue/dequeue codepaths.
+	 */
+	if (expires > 10000)
+		hrtick_start(rq, expires);
+}
+
 static struct task_struct *pick_next_task_rt(struct rq *rq)
 {
 	struct task_struct *p = _pick_next_task_rt(rq);
 
 	/* The running task is never eligible for pushing */
-	if (p)
+	if (p) {
 		dequeue_pushable_task(rq, p);
 
+		if (hrtick_enabled(rq))
+			rt_start_hrtick(rq, p);
+	}
+
 	return p;
 }
 
@@ -1794,6 +1821,9 @@ static void task_tick_rt(struct rq *rq, struct task_struct *p, int queued)
 {
 	update_curr_rt(rq);
 
+	if (queued)
+		return;
+
 	watchdog(rq, p);
 
 	/*
Signature · 1 line
1.6.2.2
#12 lore raw
In reply to Fabio Checconi

Hi Fabio,

Sorry for the delay, but we already spoke in person about this last week, a bit more detail here.

Quoted 10 lines · Fabio Checconi

This patchset introduces a group level EDF scheduler to extend the current throttling mechanism, in order to make it support generic period assignments. With this patch, the rt_runtime and rt_period parameters can be used to specify arbitrary CPU reservations for RT tasks.

This is an early RFC, I'm interested in having an idea of what people think about this feature, if it's worth working on it, what can be improved in the design, etc.

Quoted 7 lines

The main design issues involved:

- It is no more possible to specify RUNTIME_INF for a task group when throttling is enabled. Rationale: supporting both throttled and unthrottled groups would have required too much extra complexity (I didn't find anything simpler than two parallel runqueues, one for throttled and one for unthrottled groups).

I would think this is more than reasonable to the point that I wonder if it was possible to begin with. I was assuming the current bandwidth validation stuff would already exclude this possibility.

Quoted 6 lines

- Since it is not easy to mix tasks and groups on the same scheduler queue (tasks have no deadlines), the bandwidth reserved to the tasks in a group is controlled with two additional cgroup attributes:
rt_task_runtime_us and rt_task_period_us. These attrinutes control, within a cgroup, how much bandwidth is reserved to the tasks it contains.

Agreed.

Quoted 7 lines

- Shared resources are still handled using boosting. When a group contains a task inside a critical section it is scheduled according the highest priority among the ones of the tasks it contains. In this way, the same group has two modes: when it is not boosted it is scheduled according to its deadline; when it is boosted, it is scheduled according its priority. Boosted groups are always favored over non-boosted ones.

Yeah, for now this PCP like solution is the best we have. Preferably we'll come up with something really smart soon :-)

Quoted 11 lines

- The old priority array is now gone. To use only a single data structure for entities using both priorities and deadlines (due to boosting), the only possible choice was to use an rb-tree; the function used to order the keys takes into account the prioritization described above (boosted tasks, ordered by priority are favored to non-boosted tasks, ordered by increasing deadline).

- Given that the various rt_rq's belonging to the same task group are activated independently, there is the need of a timer per each rt_rq.

Like I suggested last week, we could flatten the full hierarchy to a 2 level one, the top level being a EDF like scheduler which purely schedules the 'phantom' task groups as created by the new rt_task_*_us parameters.

Once such a task group is selected we use the regular FIFO rules to pick a task.

Further, like mentioned, you remove the bandwidth distribution between cpus in patch 4. You do this because you schedule the groups using PEDF, however I was thinking that when we use GEDF to schedule the groups we can use the theory from:

H. Leontyev and J. Anderson, " A Hierarchical Multiprocessor Bandwidth Reservation Scheme with Timing Guarantees ", Proceedings of the 20th Euromicro Conference on Real-Time Systems, pp. 191-200, July 200

    http://www.cs.unc.edu/~anderson/papers/ecrts08c.pdf

This would allow us to lift this constraint.

As to load-balancing. The current scheme of load-balancing the tasks utterly ignores the deadline settings and would also need some suitable changes. I fear this part will be a little more challenging.

I would think that by using the GEDF and minimal concurrency group scheduling we'd get the desired deadline behaviour. After that we'd get the task of selecting the FIFO tasks within the dynamic vcpu range resulting from the deadline server.

We could simply implement global-fifo to make it work, and then move towards adapting the current (!group) load-balancer to work within these more dynamic constraints.

Thoughts?

#13 lore raw
Quoted 8 lines

From: Peter Zijlstra <[email protected]>
Date: Thu, Jul 09, 2009 12:36:13PM +0200

Hi Fabio,

Sorry for the delay, but we already spoke in person about this last week, a bit more detail here.

No problem, thank you for looking at this.

Quoted 19 lines · Fabio Checconi
Quoted 10 lines

This patchset introduces a group level EDF scheduler to extend the current throttling mechanism, in order to make it support generic period assignments. With this patch, the rt_runtime and rt_period parameters can be used to specify arbitrary CPU reservations for RT tasks.

This is an early RFC, I'm interested in having an idea of what people think about this feature, if it's worth working on it, what can be improved in the design, etc.

Quoted 7 lines

The main design issues involved:

- It is no more possible to specify RUNTIME_INF for a task group when throttling is enabled. Rationale: supporting both throttled and unthrottled groups would have required too much extra complexity (I didn't find anything simpler than two parallel runqueues, one for throttled and one for unthrottled groups).

Quoted 6 lines

I would think this is more than reasonable to the point that I wonder if it was possible to begin with. I was assuming the current bandwidth validation stuff would already exclude this possibility.

From the scheduling code it seemed possible, but I think I overlooked

the admission control part, sorry about that.

Quoted 28 lines
Quoted 6 lines

- Since it is not easy to mix tasks and groups on the same scheduler queue (tasks have no deadlines), the bandwidth reserved to the tasks in a group is controlled with two additional cgroup attributes:
rt_task_runtime_us and rt_task_period_us. These attrinutes control, within a cgroup, how much bandwidth is reserved to the tasks it contains.

Agreed.

Quoted 7 lines

- Shared resources are still handled using boosting. When a group contains a task inside a critical section it is scheduled according the highest priority among the ones of the tasks it contains. In this way, the same group has two modes: when it is not boosted it is scheduled according to its deadline; when it is boosted, it is scheduled according its priority. Boosted groups are always favored over non-boosted ones.

Yeah, for now this PCP like solution is the best we have. Preferably we'll come up with something really smart soon :-)

Quoted 8 lines

- The old priority array is now gone. To use only a single data structure for entities using both priorities and deadlines (due to boosting), the only possible choice was to use an rb-tree; the function used to order the keys takes into account the prioritization described above (boosted tasks, ordered by priority are favored to non-boosted tasks, ordered by increasing deadline).

Quoted 9 lines
Quoted 3 lines

- Given that the various rt_rq's belonging to the same task group are activated independently, there is the need of a timer per each rt_rq.

Like I suggested last week, we could flatten the full hierarchy to a 2 level one, the top level being a EDF like scheduler which purely schedules the 'phantom' task groups as created by the new rt_task_*_us parameters.

I really like this idea, it would simplify things a lot, with almost no changes from the scheduling theory POV. I'll give it a try as soon as possible.

Quoted 12 lines

Once such a task group is selected we use the regular FIFO rules to pick a task.

Further, like mentioned, you remove the bandwidth distribution between cpus in patch 4. You do this because you schedule the groups using PEDF, however I was thinking that when we use GEDF to schedule the groups we can use the theory from:

H. Leontyev and J. Anderson, " A Hierarchical Multiprocessor Bandwidth Reservation Scheme with Timing Guarantees ", Proceedings of the 20th Euromicro Conference on Real-Time Systems, pp. 191-200, July 200

Quoted 8 lines
    http://www.cs.unc.edu/~anderson/papers/ecrts08c.pdf

This would allow us to lift this constraint.

As to load-balancing. The current scheme of load-balancing the tasks utterly ignores the deadline settings and would also need some suitable changes. I fear this part will be a little more challenging.

I was thinking about doing things gradually: first extend throttling to handle generic periods, then extend the push-pull logic (I think you are referring to it with load-balancing) to fully support it, and then think about global EDF. I think it would be difficult to do all the things at one time.

I'm not sure that a pure GEDF approach would scale well given the number of CPUs Linux can support in extreme configurations, maybe a clustered approach would be more suitable (Anderson's group has published interesting results both about GEDF scalability and C-EDF). The focus on bounded tardiness for soft real time tasks in GEDF would also give a slightly different meaning to the runtime/period assignments done at the interface level.

So my proposal was in the direction of introducing group EDF scheduling consistently with the current throttling implementation, to obtain a more flexible form of assigning CPU reservations. GEDF can be implemented on top of it, adding a push-pull logic to the PEDF queues; anyway I would not do this without extended benchmarking in various hw configurations.

(Other schemes to implement GEDF would require major surgery to the
scheduler code, a thing that I wanted to avoid.)

I understand your concern with the removal of the bandwidth distribution logic, I'll try to reintroduce it in my next post, taking into account the PEDF schedulability constraints.

Quoted 10 lines

I would think that by using the GEDF and minimal concurrency group scheduling we'd get the desired deadline behaviour. After that we'd get the task of selecting the FIFO tasks within the dynamic vcpu range resulting from the deadline server.

We could simply implement global-fifo to make it work, and then move towards adapting the current (!group) load-balancer to work within these more dynamic constraints.

Thoughts?

About minimal concurrency group scheduling, I am not sure of how we would handle CPUs hot insertion/extraction, or how the allocation would be done efficiently (avoiding bin-packing issues) online inside the kernel.

To adapt the current load-balancer to the choices of the deadline-based scheduler I was thinking about using a cpupri-like structure per task_group, but now I'm not able to estimate the resulting overhead...

Do you think that this gradual approach makes sense?

#14 lore raw
Quoted 5 lines · Fabio Checconi

I was thinking about doing things gradually: first extend throttling to handle generic periods, then extend the push-pull logic (I think you are referring to it with load-balancing) to fully support it, and then think about global EDF. I think it would be difficult to do all the things at one time.

Agreed.

Quoted 3 lines

About minimal concurrency group scheduling, I am not sure of how we would handle CPUs hot insertion/extraction, or how the allocation would be done efficiently (avoiding bin-packing issues) online inside the kernel.

Right, since the current interface specifies bandwidth in a single-cpu normalized fashion, adding/removing cpus will only affect the total bandwidth available, but should not affect the bandwidth calculations.

So it should not break anything, but it sure might surprise, then again, hotplug is an explicit action on behalf of the admin, so he pretty much gets what he asked for :-)

I might have to re-read that mim-concurrency G-EDF paper again, but I failed to spot the bin-packing issue.

Quoted 3 lines

To adapt the current load-balancer to the choices of the deadline-based scheduler I was thinking about using a cpupri-like structure per task_group, but now I'm not able to estimate the resulting overhead...

Right, per task_group sounds about the right level for the FIFO balancer. It gets a little more complicated due to having a dynamic number of vcpus being served at any one time though.

This will also lead to extra task migrations, but sure, whatever works first, then make it better.

Quoted 1 line

Do you think that this gradual approach makes sense?

Yeah it does ;-)

#15 lore raw
Quoted 17 lines

From: Peter Zijlstra <[email protected]>
Date: Wed, Jul 15, 2009 09:50:12AM +0200

Quoted 5 lines · Fabio Checconi

I was thinking about doing things gradually: first extend throttling to handle generic periods, then extend the push-pull logic (I think you are referring to it with load-balancing) to fully support it, and then think about global EDF. I think it would be difficult to do all the things at one time.

Agreed.

Quoted 3 lines

About minimal concurrency group scheduling, I am not sure of how we would handle CPUs hot insertion/extraction, or how the allocation would be done efficiently (avoiding bin-packing issues) online inside the kernel.

Quoted 8 lines

Right, since the current interface specifies bandwidth in a single-cpu normalized fashion, adding/removing cpus will only affect the total bandwidth available, but should not affect the bandwidth calculations.

So it should not break anything, but it sure might surprise, then again, hotplug is an explicit action on behalf of the admin, so he pretty much gets what he asked for :-)

Even the proper assignment of runtimes and periods is in the hands of who runs the system, so the effectiveness of admission control already depends on the userspace.

Quoted 3 lines

I might have to re-read that mim-concurrency G-EDF paper again, but I failed to spot the bin-packing issue.

In the paper you cited, the Conclusion section lists the support for dynamic systems and for joining/leaving of tasks as a future work; I think that handling (de-)fragmentation and allocation of cpu bandwidth when tasks and groups are created/destroyed might be quite complex from within the kernel.

I'd prefer to have the mechanims enforcing the bandwidth allocation inside the kernel, and, eventually, an interface allowing the userspace to specify nontrivial allocation schemes, like the one in the paper.

Quoted 11 lines
Quoted 3 lines

To adapt the current load-balancer to the choices of the deadline-based scheduler I was thinking about using a cpupri-like structure per task_group, but now I'm not able to estimate the resulting overhead...

Right, per task_group sounds about the right level for the FIFO balancer. It gets a little more complicated due to having a dynamic number of vcpus being served at any one time though.

This will also lead to extra task migrations, but sure, whatever works first, then make it better.

This will also be interesting to evaluate the cost of other hierarchical global schedulers, since implementing them with partitioned queues will require similar techniques to migrate tasks...

Quoted 3 lines
Quoted 1 line

Do you think that this gradual approach makes sense?

Yeah it does ;-)

#16 lore raw
Quoted 10 lines · Fabio Checconi
Quoted 4 lines

I might have to re-read that mim-concurrency G-EDF paper again, but I failed to spot the bin-packing issue.

In the paper you cited, the Conclusion section lists the support for dynamic systems and for joining/leaving of tasks as a future work; I think that handling (de-)fragmentation and allocation of cpu bandwidth when tasks and groups are created/destroyed might be quite complex from within the kernel.

Hmm, right, so I was thinking that we could simply create int(w_i) full cpu and 1 frac(w_i) server tasks and let the single level G-EDF sort it out.

It looks to me that by only scheduling the leafs of the hierarchy you side-step a lot of issues, but then maybe it generates other issues :-)

Quoted 3 lines

I'd prefer to have the mechanims enforcing the bandwidth allocation inside the kernel, and, eventually, an interface allowing the userspace to specify nontrivial allocation schemes, like the one in the paper.

Right.