Skip to contentSkip to conversation

SCHED_DEADLINE (new version of SCHED_EDF)

RFC PATCH In review Raistlin 5 participants 45 messages Oct 16, 2009 – Jan 13, 2010

Subsystems (8)
lore
Share & tools
lore

Raistlin

author
#0 lore raw

cover SCHED_DEADLINE (new version of SCHED_EDF)

Hi Peter, Hi all,

Given all the comments and feedback we got, here it is the new version of our EDF patch, this time in a split series. :-)

Special thanks to all the one that gave us any kind of suggestion, especially during last RTLWS in Dresden.

The rationale/motivation for the new scheduler is the same of the first e-mail (http://lwn.net/Articles/353797/), thus I only add some new and (I think) interesting links:
- Ericsson posting about SCHED_EDF/DEADLINE
https://labs.ericsson.com/blog/making-linux-more-real-time

- The slides we presented at RTLWS in Dresden:
http://retis.sssup.it/people/faggioli/sched_deadline/rtlw_EDF.pdf

- Luca Abeni's presentation about using deadline based reservation schedulers for IRQ-Threads:
http://www.disi.unitn.it/~abeni/rtlws-slides.pdf

Moreover, we moved the project on gitorious.org, therefore:
http://gitorious.org/sched_deadline

I am also setting up right now the Wiki section, where you can find some more detailed usage instructions, examples and overhead estimation:
http://gitorious.org/sched_deadline/pages/Home

Git repositories are up and running, and ready at:
(mainline)
git://gitorious.org/sched_deadline/linux-deadline.git sched-deadline

(sched-devel)
git://gitorious.org/sched_deadline/linux-deadline.git sched-devel-deadline

(preempt-rt [*])
git://gitorious.org/sched_deadline/linux-deadline.git rt-deadline

The new project homepage is
http://www.evidence.eu.com/sched_deadline.html

Here the main changes we did, following what many of you --and mainly Peter-- suggested:
- name changed from SCHED_EDF to SCHED_DEADLINE

- SCHED_DEADLINE has higher priority than SCHED_FIFO/SCHED_RR

- flags added in sched_param_ex to signal deadline misses (in case of utilization > 100%) and/or budget overruns

- new sched_*_ex prototypes, with a len field to accomodate the size of sched_param_ex, trying to avoid further ABI issues if it changes

- new syscall sched_wait_interval added. It behaves like clock_nanosleep but, for a SCHED_DEADLINE task, it also represent the end of the current instance (sched_yield no longer needed)

- on fork, child starts but with 0 bandwidth (i.e., it does not start! :-D)

- bug fixing :)

Any feedback and contribution is welcome.

Many thanks,

Dario Faggioli
Claudio Scordino
Michael Trimarchi

[*] porting toward preempt-rt is work in progress. Code is there, but we are testing and fixing it, with the help of Luca and Nicola from Trento... So don't consider it as the final version!

author
#1 lore raw

RFC PATCH 1/12 Extended scheduling parameters structure added.

An extended scheduling parameter structure, sched_param_ex, is defined in this commit, as the starting point for supporting task models more sophisticated than fixed-priority.

One that is both popular and (hopefully!) general enough is the so-called sporadic task model, in which tasks' computation is divided into instances, each one with:
* a (maximum/typical) execution time,
* a minimum interval between the activation of two consecutive instances,
* a time instant by which the computation of the instance must be completed.

The new sched_param_ex reflects this model, and thus allows for better specification of time sensitive workloads typical, for example, in real-time, control and/or continuous media applications.

---
 include/linux/sched.h |    8 ++++++++
 1 files changed, 8 insertions(+), 0 deletions(-)
include/linux/sched.h +8 -0
index 75e6e60..ac9837c 100644
@@ -94,6 +94,14 @@ struct sched_param {
 
 #include <asm/processor.h>
 
+struct sched_param_ex {
+	int sched_priority;
+	struct timespec sched_runtime;
+	struct timespec sched_deadline;
+	struct timespec sched_period;
+	int sched_flags;
+};
+
 struct exec_domain;
 struct futex_pi_state;
 struct robust_list_head;
Signature · 9 lines
1.6.0.4

-- 
<<This happens because I choose it to happen!>> (Raistlin Majere)
----------------------------------------------------------------------
Dario Faggioli, ReTiS Lab, Scuola Superiore Sant'Anna, Pisa  (Italy)

http://blog.linux.it/raistlin / [email protected] /
[email protected]
maintainer
#2 lore raw

Re: [RFC 1/12][PATCH] Extended scheduling parameters structure added.

Quoted 12 lines · Raistlin
 include/linux/sched.h |    8 ++++++++
 1 files changed, 8 insertions(+), 0 deletions(-)
include/linux/sched.h +1 -0
index 75e6e60..ac9837c 100644
@@ -94,6 +94,14 @@ struct sched_param {
 
 #include <asm/processor.h>
 
+struct sched_param_ex {

include/linux/sched.h struct sched_param { · line 107

Quoted 10 lines
include/linux/sched.h +7 -0
+	int sched_priority;
+	struct timespec sched_runtime;
+	struct timespec sched_deadline;
+	struct timespec sched_period;
+	int sched_flags;
+};
+
 struct exec_domain;
 struct futex_pi_state;
 struct robust_list_head;

Why separate this change from the introduction of the new system calls?

author
#3 lore raw

Re: [RFC 1/12][PATCH] Extended scheduling parameters structure added.

Quoted 13 lines · Peter Zijlstra
Quoted 11 lines · Raistlin
 include/linux/sched.h |    8 ++++++++
 1 files changed, 8 insertions(+), 0 deletions(-)
include/linux/sched.h +0 -0
index 75e6e60..ac9837c 100644
@@ -94,6 +94,14 @@ struct sched_param {
 
 #include <asm/processor.h>
 
Quoted 14 lines

include/linux/sched.h struct sched_param { · line 107

Quoted 11 lines
include/linux/sched.h +8 -0
+struct sched_param_ex {
+	int sched_priority;
+	struct timespec sched_runtime;
+	struct timespec sched_deadline;
+	struct timespec sched_period;
+	int sched_flags;
+};
+
 struct exec_domain;
 struct futex_pi_state;
 struct robust_list_head;

Why separate this change from the introduction of the new system calls?

Nothing particular... I was just thinking that the extended data structure might have sense even for other --more general-- purposes. But I can merge the two if it sounds better.

Thanks and regards,
Dario

Signature · 6 lines
<<This happens because I choose it to happen!>> (Raistlin Majere)
----------------------------------------------------------------------
Dario Faggioli, ReTiS Lab, Scuola Superiore Sant'Anna, Pisa  (Italy)

http://blog.linux.it/raistlin / [email protected] /
[email protected]
author
#4 lore raw

Re: [RFC 0/12][PATCH] SCHED_DEADLINE: core of the scheduling class

In reply to Raistlin

This commit introduces a new scheduling policy (SCHED_DEADLINE), implemented in a new scheduling class (sched_deadline.c).

As of now, it implements the popular Earliest Deadline First (EDF) real-time scheduling algorithm.
It basically means each (instance of each) task has a deadline, indicating the time instant by which its computation has to be completed. The scheduler always picks the task with the earliest deadline as the next to be executed.

Some more logic is added in order to avoid tasks interfering between each others, i.e., a deadline miss of task A should not affect the capability of task B to meet its own deadline.

Open issues:
- this implementation is ``fully partitioned'', which means each task has to be bound to one processor at any given time. Turning it into ``global scheduling'' (i.e., migrations are allowed) is work in progress;
- proper dealing with critical sections/rt-mutexes is also missing, and is also work in progress.

---
 include/linux/sched.h   |   36 ++++
 kernel/hrtimer.c        |    2 +-
 kernel/sched.c          |   44 ++++-
 kernel/sched_deadline.c |  513 +++++++++++++++++++++++++++++++++++++++++++++++
 kernel/sched_fair.c     |    2 +-
 kernel/sched_rt.c       |    2 +-
 6 files changed, 587 insertions(+), 12 deletions(-)
 create mode 100644 kernel/sched_deadline.c
include/linux/sched.h +36 -0
index ac9837c..20e1a6a 100644
@@ -38,6 +38,7 @@
 #define SCHED_BATCH		3
 /* SCHED_ISO: reserved but not implemented yet */
 #define SCHED_IDLE		5
+#define SCHED_DEADLINE		6
 /* Can be ORed in to make sure the process is reverted back to SCHED_NORMAL on fork */
 #define SCHED_RESET_ON_FORK     0x40000000
 
@@ -159,6 +160,7 @@ extern unsigned long get_parent_ip(unsigned long addr);
 
 struct seq_file;
 struct cfs_rq;
+struct dl_rq;
 struct task_group;
 #ifdef CONFIG_SCHED_DEBUG
 extern void proc_sched_show_task(struct task_struct *p, struct seq_file *m);
@@ -1218,6 +1220,27 @@ struct sched_rt_entity {
 #endif
 };
 
+#define DL_NEW			0x00000001
+#define DL_THROTTLED		0x00000002
+#define DL_BOOSTED		0x00000004
+
+struct sched_dl_entity {
+	struct rb_node	rb_node;
+	/* actual scheduling parameters */
+	s64		runtime;
+	u64		deadline;
+	unsigned int	flags;
+
+	/* original parameters taken from sched_param_ex */
+	u64		sched_runtime;
+	u64		sched_deadline;
+	u64		sched_period;
+	u64		bw;
+
+	int		nr_cpus_allowed;
+	struct hrtimer	dl_timer;
+};
+
 struct rcu_node;
 
 struct task_struct {
@@ -1240,6 +1263,7 @@ struct task_struct {
 	const struct sched_class *sched_class;
 	struct sched_entity se;
 	struct sched_rt_entity rt;
+	struct sched_dl_entity dl;
 
 #ifdef CONFIG_PREEMPT_NOTIFIERS
 	/* list of struct preempt_notifier: */
@@ -1583,6 +1607,18 @@ static inline int rt_task(struct task_struct *p)
 	return rt_prio(p->prio);
 }
 
+static inline int deadline_policy(int policy)
+{
+	if (unlikely(policy == SCHED_DEADLINE))
+		return 1;
+	return 0;
+}
+
+static inline int deadline_task(struct task_struct *p)
+{
+	return deadline_policy(p->policy);
+}
+
 static inline struct pid *task_pid(struct task_struct *task)
 {
 	return task->pids[PIDTYPE_PID].pid;
kernel/hrtimer.c +1 -1
index 3e1c36e..bf6a3b1 100644
@@ -1537,7 +1537,7 @@ long hrtimer_nanosleep(struct timespec *rqtp, struct timespec __user *rmtp,
 	unsigned long slack;
 
 	slack = current->timer_slack_ns;
-	if (rt_task(current))
+	if (deadline_task(current) || rt_task(current))
 		slack = 0;
 
 	hrtimer_init_on_stack(&t.timer, clockid, mode);
kernel/sched.c +35 -9

109 lines not on this page · raw message

kernel/sched_deadline.c new file +513 -0

513 lines not on this page · raw message

kernel/sched_fair.c +1 -1
index 4e777b4..8144cb4 100644
@@ -1571,7 +1571,7 @@ static void check_preempt_wakeup(struct rq *rq, struct task_struct *p, int wake_
 
 	update_curr(cfs_rq);
 
-	if (unlikely(rt_prio(p->prio))) {
+	if (unlikely(deadline_task(p) || rt_prio(p->prio))) {
 		resched_task(curr);
 		return;
 	}
kernel/sched_rt.c +1 -1
index a4d790c..65cef57 100644
@@ -1004,7 +1004,7 @@ static void check_preempt_equal_prio(struct rq *rq, struct task_struct *p)
  */
 static void check_preempt_curr_rt(struct rq *rq, struct task_struct *p, int flags)
 {
-	if (p->prio < rq->curr->prio) {
+	if (deadline_task(p) || p->prio < rq->curr->prio) {
 		resched_task(rq->curr);
 		return;
 	}
Signature · 9 lines
1.6.0.4

-- 
<<This happens because I choose it to happen!>> (Raistlin Majere)
----------------------------------------------------------------------
Dario Faggioli, ReTiS Lab, Scuola Superiore Sant'Anna, Pisa  (Italy)

http://blog.linux.it/raistlin / [email protected] /
[email protected]
maintainer
#5 lore raw

Re: [RFC 0/12][PATCH] SCHED_DEADLINE: core of the scheduling class

Quoted 6 lines · Raistlin
kernel/sched.c +0 -2
@@ -5966,10 +5982,14 @@ void rt_mutex_setprio(struct task_struct *p, int prio)
        if (running)
                p->sched_class->put_prev_task(rq, p);
 
-       if (rt_prio(prio))
-               p->sched_class = &rt_sched_class;

kernel/sched.c void rt_mutex_setprio(struct task_struct *p, int prio) · line 5992

Quoted 10 lines
kernel/sched.c +8 -2
-       else
-               p->sched_class = &fair_sched_class;
+       if (deadline_task(p))
+               p->sched_class = &deadline_sched_class;
+       else {
+               if (rt_prio(prio))
+                       p->sched_class = &rt_sched_class;
+               else
+                       p->sched_class = &fair_sched_class;
+       } 

This looks wrong.

This is PI code, so the effective class should be determined based on the 'priority' not on the 'policy'.

I understand we don't yet have deadline inheritance like things in place, but this would be where we should make use of the simple ceiling protocol to boost things for now.

#6 lore raw

Re: [RFC 0/12][PATCH] SCHED_DEADLINE: core of the scheduling class

Quoted 5 lines · Peter Zijlstra
Quoted 4 lines · Raistlin
kernel/sched.c +0 -0
@@ -5966,10 +5982,14 @@ void rt_mutex_setprio(struct task_struct *p, int prio)
        if (running)
                p->sched_class->put_prev_task(rq, p);
 
Quoted 15 lines

kernel/sched.c void rt_mutex_setprio(struct task_struct *p, int prio) · line 5992

Quoted 12 lines
kernel/sched.c +8 -4
-       if (rt_prio(prio))
-               p->sched_class = &rt_sched_class;
-       else
-               p->sched_class = &fair_sched_class;
+       if (deadline_task(p))
+               p->sched_class = &deadline_sched_class;
+       else {
+               if (rt_prio(prio))
+                       p->sched_class = &rt_sched_class;
+               else
+                       p->sched_class = &fair_sched_class;
+       } 

This looks wrong.

Completely agree! :-P

Quoted 3 lines

This is PI code, so the effective class should be determined based on the 'priority' not on the 'policy'.

Agree, but...

Quoted 4 lines

I understand we don't yet have deadline inheritance like things in place, but this would be where we should make use of the simple ceiling protocol to boost things for now.

... You got it! This is me having no idea of what solution would be better since no deadline/bandwidth/whatever inheritance is in place right now.

Now that you gave a direction, I'll follow right that path! :-)

Thanks and regards,
Dario

Signature · 6 lines
<<This happens because I choose it to happen!>> (Raistlin Majere)
----------------------------------------------------------------------
Dario Faggioli, ReTiS Lab, Scuola Superiore Sant'Anna, Pisa  (Italy)

http://blog.linux.it/raistlin / [email protected] /
[email protected]
maintainer
#7 lore raw

Re: [RFC 0/12][PATCH] SCHED_DEADLINE: core of the scheduling class

In reply to Raistlin
Quoted 1 line · Raistlin

+ if (unlikely(task_has_deadline_policy(p) || task_has_rt_policy(p))) {

small nit, since both task_has_{deadline,rt}_policy() already have unlikely()s in, this extra unlikely is not needed.

author
#8 lore raw

Re: [RFC 0/12][PATCH] SCHED_DEADLINE: core of the scheduling class

Quoted 6 lines · Peter Zijlstra
Quoted 1 line · Raistlin

+ if (unlikely(task_has_deadline_policy(p) || task_has_rt_policy(p))) {

small nit, since both task_has_{deadline,rt}_policy() already have unlikely()s in, this extra unlikely is not needed.

Coping. :-)

Thanks and regards,
Dario

Signature · 6 lines
<<This happens because I choose it to happen!>> (Raistlin Majere)
----------------------------------------------------------------------
Dario Faggioli, ReTiS Lab, Scuola Superiore Sant'Anna, Pisa  (Italy)

http://blog.linux.it/raistlin / [email protected] /
[email protected]
maintainer
#9 lore raw

Re: [RFC 0/12][PATCH] SCHED_DEADLINE: core of the scheduling class

In reply to Raistlin
Quoted 12 lines · Raistlin
kernel/sched_deadline.c new file +12 -0
+struct task_struct *pick_next_task_deadline(struct rq *rq)
+{
+       struct sched_dl_entity *dl_se;
+       struct task_struct *p;
+       struct dl_rq *dl_rq;
+
+       dl_rq = &rq->dl;
+
+       if (likely(!dl_rq->dl_nr_running))
+               return NULL;
+
+       dl_se = pick_next_deadline_entity(rq, dl_rq);

kernel/sched_deadline.c line 415

Quoted 10 lines
kernel/sched_deadline.c new file +10 -0
+       BUG_ON(!dl_se);
+
+       p = deadline_task_of(dl_se);
+       p->se.exec_start = rq->clock;
+#ifdef CONFIG_SCHED_HRTICK
+       if (hrtick_enabled(rq))
+               start_hrtick_deadline(rq, p);
+#endif
+       return p;
+} 

I'm not sure about actually using hrtick like this, I'd expect SCHED_DEADLINE to always use hrtimers when available. The only reason to use some of the hrtick infrastructure is to re-use the hrtick_start() logic which uses IPIs to ensure we program the timer on the right cpu (so we can schedule from it).

The whole IPI mess requires USE_GENERIC_SMP_HELPERS, which makes CONFIG_HRTICK useful (ensures we have hrtimers enabled and have generic IPI bits)

The problem is that things like hrtick_enabled() also check sched_feat(HRTICK) which is disabled by default (because programming the clock hw on each schedule was found too expensive) but that should not stop SCHED_DEADLINE from using it.

maintainer
#10 lore raw

Re: [RFC 0/12][PATCH] SCHED_DEADLINE: core of the scheduling class

Quoted 21 lines · Peter Zijlstra
Quoted 20 lines · Raistlin
kernel/sched_deadline.c new file +20 -0
+struct task_struct *pick_next_task_deadline(struct rq *rq)
+{
+       struct sched_dl_entity *dl_se;
+       struct task_struct *p;
+       struct dl_rq *dl_rq;
+
+       dl_rq = &rq->dl;
+
+       if (likely(!dl_rq->dl_nr_running))
+               return NULL;
+
+       dl_se = pick_next_deadline_entity(rq, dl_rq);
+       BUG_ON(!dl_se);
+
+       p = deadline_task_of(dl_se);
+       p->se.exec_start = rq->clock;
+#ifdef CONFIG_SCHED_HRTICK
+       if (hrtick_enabled(rq))
+               start_hrtick_deadline(rq, p);
+#endif
Quoted 8 lines

kernel/sched_deadline.c line 415

Quoted 2 lines
kernel/sched_deadline.c new file +2 -0
+       return p;
+} 

I'm not sure about actually using hrtick like this, I'd expect SCHED_DEADLINE to always use hrtimers when available. The only reason to use some of the hrtick infrastructure is to re-use the hrtick_start() logic which uses IPIs to ensure we program the timer on the right cpu (so we can schedule from it).

Hmm I suppose we could ignore all that CONFIG_SCHED_HRTICK stuff and simply bounce the schedule event using the resched ipi when we find we're on the wrong cpu. Not ideal though.. frigging mess all this :-)

maintainer
#11 lore raw

Re: [RFC 0/12][PATCH] SCHED_DEADLINE: core of the scheduling class

Quoted 31 lines · Peter Zijlstra
Quoted 21 lines · Peter Zijlstra
Quoted 20 lines · Raistlin
kernel/sched_deadline.c new file +20 -0
+struct task_struct *pick_next_task_deadline(struct rq *rq)
+{
+       struct sched_dl_entity *dl_se;
+       struct task_struct *p;
+       struct dl_rq *dl_rq;
+
+       dl_rq = &rq->dl;
+
+       if (likely(!dl_rq->dl_nr_running))
+               return NULL;
+
+       dl_se = pick_next_deadline_entity(rq, dl_rq);
+       BUG_ON(!dl_se);
+
+       p = deadline_task_of(dl_se);
+       p->se.exec_start = rq->clock;
+#ifdef CONFIG_SCHED_HRTICK
+       if (hrtick_enabled(rq))
+               start_hrtick_deadline(rq, p);
+#endif
Quoted 8 lines

kernel/sched_deadline.c line 415

Quoted 2 lines
kernel/sched_deadline.c new file +2 -0
+       return p;
+} 

I'm not sure about actually using hrtick like this, I'd expect SCHED_DEADLINE to always use hrtimers when available. The only reason to use some of the hrtick infrastructure is to re-use the hrtick_start() logic which uses IPIs to ensure we program the timer on the right cpu (so we can schedule from it).

Quoted 3 lines

Hmm I suppose we could ignore all that CONFIG_SCHED_HRTICK stuff and simply bounce the schedule event using the resched ipi when we find we're on the wrong cpu. Not ideal though.. frigging mess all this :-)

Hmm bugger that, that's not going to work since the fallback timer stuff doesn't run from hardirq context and is generally useless anyway :-)

#12 lore raw

Re: [RFC 0/12][PATCH] SCHED_DEADLINE: core of the scheduling class

In reply to Peter Zijlstra
Quoted 21 lines · Peter Zijlstra
Quoted 20 lines · Raistlin
kernel/sched_deadline.c new file +20 -0
+struct task_struct *pick_next_task_deadline(struct rq *rq)
+{
+       struct sched_dl_entity *dl_se;
+       struct task_struct *p;
+       struct dl_rq *dl_rq;
+
+       dl_rq = &rq->dl;
+
+       if (likely(!dl_rq->dl_nr_running))
+               return NULL;
+
+       dl_se = pick_next_deadline_entity(rq, dl_rq);
+       BUG_ON(!dl_se);
+
+       p = deadline_task_of(dl_se);
+       p->se.exec_start = rq->clock;
+#ifdef CONFIG_SCHED_HRTICK
+       if (hrtick_enabled(rq))
+               start_hrtick_deadline(rq, p);
+#endif
Quoted 9 lines

kernel/sched_deadline.c line 415

Quoted 2 lines
kernel/sched_deadline.c new file +2 -0
+       return p;
+} 

I'm not sure about actually using hrtick like this, I'd expect SCHED_DEADLINE to always use hrtimers when available. The only reason to use some of the hrtick infrastructure is to re-use the hrtick_start() logic which uses IPIs to ensure we program the timer on the right cpu (so we can schedule from it).

Yeah, that and the fact that it seemed to me very easy and clean to:
- check for runtime enforcement inside the task_tick_deadline function, as other scheduling classes do, and then
- if possible, ask that task_tick_deadline function to be called right at the time instant I expect my runtime to be depleted. If that won't happen --because of no-hrtick or no-hires-hrtimers-- the check will still be performed during the next tick.

Quoted 9 lines

The whole IPI mess requires USE_GENERIC_SMP_HELPERS, which makes CONFIG_HRTICK useful (ensures we have hrtimers enabled and have generic IPI bits)

The problem is that things like hrtick_enabled() also check sched_feat(HRTICK) which is disabled by default (because programming the clock hw on each schedule was found too expensive) but that should not stop SCHED_DEADLINE from using it.

Mmm... I might have lost you here... :-(

Do you think that keep using hrtick_start and alike, even if sched_feat(HRTICK) is disabled, could be good enough? Or are you suggesting something different?
IOTH, should I simply bypass the sched_feat()/hrtick_enabled() check or you think I need something more?

Thanks and regards,
Dario

Signature · 6 lines
<<This happens because I choose it to happen!>> (Raistlin Majere)
----------------------------------------------------------------------
Dario Faggioli, ReTiS Lab, Scuola Superiore Sant'Anna, Pisa  (Italy)

http://blog.linux.it/raistlin / [email protected] /
[email protected]
maintainer
#13 lore raw

Re: [RFC 0/12][PATCH] SCHED_DEADLINE: core of the scheduling class

Quoted 43 lines · Dario Faggioli
Quoted 21 lines · Peter Zijlstra
Quoted 20 lines · Raistlin
kernel/sched_deadline.c new file +20 -0
+struct task_struct *pick_next_task_deadline(struct rq *rq)
+{
+       struct sched_dl_entity *dl_se;
+       struct task_struct *p;
+       struct dl_rq *dl_rq;
+
+       dl_rq = &rq->dl;
+
+       if (likely(!dl_rq->dl_nr_running))
+               return NULL;
+
+       dl_se = pick_next_deadline_entity(rq, dl_rq);
+       BUG_ON(!dl_se);
+
+       p = deadline_task_of(dl_se);
+       p->se.exec_start = rq->clock;
+#ifdef CONFIG_SCHED_HRTICK
+       if (hrtick_enabled(rq))
+               start_hrtick_deadline(rq, p);
+#endif
Quoted 9 lines

kernel/sched_deadline.c line 415

Quoted 2 lines
kernel/sched_deadline.c new file +2 -0
+       return p;
+} 

I'm not sure about actually using hrtick like this, I'd expect SCHED_DEADLINE to always use hrtimers when available. The only reason to use some of the hrtick infrastructure is to re-use the hrtick_start() logic which uses IPIs to ensure we program the timer on the right cpu (so we can schedule from it).

Yeah, that and the fact that it seemed to me very easy and clean to:
- check for runtime enforcement inside the task_tick_deadline function, as other scheduling classes do, and then
- if possible, ask that task_tick_deadline function to be called right at the time instant I expect my runtime to be depleted. If that won't happen --because of no-hrtick or no-hires-hrtimers-- the check will still be performed during the next tick.

Quoted 4 lines

The whole IPI mess requires USE_GENERIC_SMP_HELPERS, which makes CONFIG_HRTICK useful (ensures we have hrtimers enabled and have generic IPI bits)

Quoted 6 lines
Quoted 5 lines

The problem is that things like hrtick_enabled() also check sched_feat(HRTICK) which is disabled by default (because programming the clock hw on each schedule was found too expensive) but that should not stop SCHED_DEADLINE from using it.

Mmm... I might have lost you here... :-(

I had a little chat with fabio around new-years and I think we ended up agreeing that your current usage is ok, we can always fix it up later.

Its an unfortunate complicated dance of hrtimer being configured in, having capable hardware and dealing with all the fallout cases.

The only thing which is unfortunate for your current usage is the sched_feat(HRTICK) thing, we generally do not want HRTICK for SCHED_OTHER, whereas we'd always (when configured and having capable hardware) want if for SCHED_DEADLINE..

maintainer
#14 lore raw

Re: [RFC 0/12][PATCH] SCHED_DEADLINE: core of the scheduling class

In reply to Raistlin
Quoted 6 lines · Raistlin
kernel/sched_deadline.c new file +6 -0
+static unsigned long
+load_balance_deadline(struct rq *this_rq, int this_cpu, struct rq *busiest,
+                unsigned long max_load_move,
+                struct sched_domain *sd, enum cpu_idle_type idle,
+                int *all_pinned, int *this_best_prio)
+{

kernel/sched_deadline.c line 474

Quoted 10 lines
kernel/sched_deadline.c new file +10 -0
+       /* for now, don't touch SCHED_DEADLINE tasks */
+       return 0;
+}
+
+static int
+move_one_task_deadline(struct rq *this_rq, int this_cpu, struct rq *busiest,
+                 struct sched_domain *sd, enum cpu_idle_type idle)
+{
+       return 0;
+} 

The good news is that I've killed all that :-)

author
#15 lore raw

Re: [RFC 0/12][PATCH] SCHED_DEADLINE: core of the scheduling class

Quoted 11 lines · Peter Zijlstra
Quoted 10 lines · Raistlin
kernel/sched_deadline.c new file +10 -0
+static unsigned long
+load_balance_deadline(struct rq *this_rq, int this_cpu, struct rq *busiest,
+                unsigned long max_load_move,
+                struct sched_domain *sd, enum cpu_idle_type idle,
+                int *all_pinned, int *this_best_prio)
+{
+       /* for now, don't touch SCHED_DEADLINE tasks */
+       return 0;
+}
+
Quoted 9 lines

kernel/sched_deadline.c line 474

Quoted 6 lines
kernel/sched_deadline.c new file +6 -0
+static int
+move_one_task_deadline(struct rq *this_rq, int this_cpu, struct rq *busiest,
+                 struct sched_domain *sd, enum cpu_idle_type idle)
+{
+       return 0;
+} 

The good news is that I've killed all that :-)

Yeah, good news then! :-D

By the way... I hope you all will soon hear from us something regarding global-SMP and migrations with respect to this scheduler.

Thanks and regards,
Dario

Signature · 6 lines
<<This happens because I choose it to happen!>> (Raistlin Majere)
----------------------------------------------------------------------
Dario Faggioli, ReTiS Lab, Scuola Superiore Sant'Anna, Pisa  (Italy)

http://blog.linux.it/raistlin / [email protected] /
[email protected]
author
#16 lore raw

Re: [RFC 0/12][PATCH] SCHED_DEADLINE: fork and terminate task logic

In reply to Raistlin

This commits adds the code that make it possible for a SCHED_DEADLINE task to fork a child and to correctly terminate.

The child of a SCHED_DEADLINE task is (if !reset_on_fork) SCHED_DEADLINE as well, but it has no bandwidth and it thus can't even start running. To make it run, some other task (e.g., the parent) should provide it with valid SCHED_DEADLINE parameters.

Actually, this is one of the simplest alternatives we have here, but it might not be the best one. Therefore, discussion on what the ``most natural'' behaviour is is still open and comments are welcome.

---
 kernel/sched.c          |   18 +++++++++++++++++-
 kernel/sched_deadline.c |   20 ++++++++++++++++++++
 2 files changed, 37 insertions(+), 1 deletions(-)
kernel/sched.c +17 -1
index adf1414..243066e 100644
@@ -2561,8 +2561,20 @@ void sched_fork(struct task_struct *p, int clone_flags)
 	 * Make sure we do not leak PI boosting priority to the child.
 	 */
 	p->prio = current->normal_prio;
+	if (deadline_task(p)) {
+		p->sched_class = &deadline_sched_class;
 
-	if (!rt_prio(p->prio))
+		/*
+		 * the child will be SCHED_DEADLINE, but with zero bandwidth.
+		 * The parent (or some other task) must call setscheduler_ex
+		 * on it, or it won't ever start.
+		 */
+		init_deadline_task(p);
+		p->dl.flags &= ~DL_NEW;
+		p->dl.flags |= DL_THROTTLED;
+	} else if (rt_prio(p->prio))
+		p->sched_class = &rt_sched_class;
+	else
 		p->sched_class = &fair_sched_class;
 
 #ifdef CONFIG_SMP
@@ -2744,6 +2756,10 @@ static void finish_task_switch(struct rq *rq, struct task_struct *prev)
 	if (mm)
 		mmdrop(mm);
 	if (unlikely(prev_state == TASK_DEAD)) {
+		/* a deadline task is dying: stop the bandwidth timer */
+		if (deadline_task(prev))
+			hrtimer_cancel(&prev->dl.dl_timer);
+
 		/*
 		 * Remove function-return probe instances associated with this
 		 * task and put them back on the free list.
kernel/sched_deadline.c +20 -0
index 5430c48..b4be178 100644
@@ -213,6 +213,26 @@ unlock:
 	return HRTIMER_NORESTART;
 }
 
+static void init_deadline_timer(struct hrtimer *timer)
+{
+	if (hrtimer_active(timer)) {
+		hrtimer_try_to_cancel(timer);
+		return;
+	}
+
+	hrtimer_init(timer, CLOCK_MONOTONIC, HRTIMER_MODE_REL);
+	timer->function = deadline_timer;
+}
+
+static void init_deadline_task(struct task_struct *p)
+{
+	RB_CLEAR_NODE(&p->dl.rb_node);
+	init_deadline_timer(&p->dl.dl_timer);
+	p->dl.sched_runtime = p->dl.runtime = 0;
+	p->dl.sched_deadline = p->dl.deadline = 0;
+	p->dl.flags = p->dl.bw = 0;
+}
+
 static
 int deadline_runtime_exceeded(struct rq *rq, struct sched_dl_entity *dl_se)
 {
Signature · 9 lines
1.6.0.4

-- 
<<This happens because I choose it to happen!>> (Raistlin Majere)
----------------------------------------------------------------------
Dario Faggioli, ReTiS Lab, Scuola Superiore Sant'Anna, Pisa  (Italy)

http://blog.linux.it/raistlin / [email protected] /
[email protected]
maintainer
#17 lore raw

Re: [RFC 0/12][PATCH] SCHED_DEADLINE: fork and terminate task logic

Quoted 7 lines · Raistlin

+++ b/kernel/sched.c

kernel/sched.c +2 -0
@@ -2561,8 +2561,20 @@ void sched_fork(struct task_struct *p, int clone_flags)
         * Make sure we do not leak PI boosting priority to the child.
         */
        p->prio = current->normal_prio;
+       if (deadline_task(p)) {
+               p->sched_class = &deadline_sched_class;

kernel/sched.c void sched_fork(struct task_struct *p, int clone_flags) · line 2574

Quoted 10 lines
kernel/sched.c +8 -1
 
-       if (!rt_prio(p->prio))
+               /*
+                * the child will be SCHED_DEADLINE, but with zero bandwidth.
+                * The parent (or some other task) must call setscheduler_ex
+                * on it, or it won't ever start.
+                */
+               init_deadline_task(p);
+               p->dl.flags &= ~DL_NEW;
+               p->dl.flags |= DL_THROTTLED;

I recently added ->task_fork(), which is called after the class assignment.

Quoted 7 lines
kernel/sched.c +3 -0
+       } else if (rt_prio(p->prio))
+               p->sched_class = &rt_sched_class;
+       else
                p->sched_class = &fair_sched_class;
 
 #ifdef CONFIG_SMP

kernel/sched.c static void finish_task_switch(struct rq *rq, struct task_struct *prev) · line 2765

Quoted 10 lines
kernel/sched.c +4 -0
@@ -2744,6 +2756,10 @@ static void finish_task_switch(struct rq *rq, struct task_struct *prev)
        if (mm)
                mmdrop(mm);
        if (unlikely(prev_state == TASK_DEAD)) {
+               /* a deadline task is dying: stop the bandwidth timer */
+               if (deadline_task(prev))
+                       hrtimer_cancel(&prev->dl.dl_timer);
+
                /*
                 * Remove function-return probe instances associated with this
                 * task and put them back on the free list. 

Shouldn't this be done in the ->dequeue_task() callback?

author
#18 lore raw

Re: [RFC 0/12][PATCH] SCHED_DEADLINE: fork and terminate task logic

Quoted 10 lines · Peter Zijlstra

kernel/sched.c void sched_fork(struct task_struct *p, int clone_flags) · line 2574

Quoted 9 lines
kernel/sched.c +8 -1
-       if (!rt_prio(p->prio))
+               /*
+                * the child will be SCHED_DEADLINE, but with zero bandwidth.
+                * The parent (or some other task) must call setscheduler_ex
+                * on it, or it won't ever start.
+                */
+               init_deadline_task(p);
+               p->dl.flags &= ~DL_NEW;
+               p->dl.flags |= DL_THROTTLED;
Quoted 3 lines

I recently added ->task_fork(), which is called after the class assignment.

Saw that, and it is being of great help! :-P

Quoted 5 lines
Quoted 5 lines
kernel/sched.c +3 -0
+       } else if (rt_prio(p->prio))
+               p->sched_class = &rt_sched_class;
+       else
                p->sched_class = &fair_sched_class;
Quoted 15 lines

kernel/sched.c static void finish_task_switch(struct rq *rq, struct task_struct *prev) · line 2765

Quoted 12 lines

#ifdef CONFIG_SMP

kernel/sched.c +4 -0
@@ -2744,6 +2756,10 @@ static void finish_task_switch(struct rq *rq, struct task_struct *prev)
        if (mm)
                mmdrop(mm);
        if (unlikely(prev_state == TASK_DEAD)) {
+               /* a deadline task is dying: stop the bandwidth timer */
+               if (deadline_task(prev))
+                       hrtimer_cancel(&prev->dl.dl_timer);
+
                /*
                 * Remove function-return probe instances associated with this
                 * task and put them back on the free list. 

Shouldn't this be done in the ->dequeue_task() callback?

Not sure of this snippet... Actually, it is one of the most disturbing piece of code of this whole scheduler. :-(

The reason why it is here is that I think it is needed to call hrtimer_cancel() _without_ holding the rq->lock, is that correct?

It is

Thanks and regards,
Dario

Signature · 6 lines
<<This happens because I choose it to happen!>> (Raistlin Majere)
----------------------------------------------------------------------
Dario Faggioli, ReTiS Lab, Scuola Superiore Sant'Anna, Pisa  (Italy)

http://blog.linux.it/raistlin / [email protected] /
[email protected]
maintainer
#19 lore raw

Re: [RFC 0/12][PATCH] SCHED_DEADLINE: fork and terminate task logic

Quoted 20 lines · Raistlin
Quoted 5 lines
Quoted 5 lines
kernel/sched.c +3 -0
+       } else if (rt_prio(p->prio))
+               p->sched_class = &rt_sched_class;
+       else
                p->sched_class = &fair_sched_class;
Quoted 15 lines

kernel/sched.c static void finish_task_switch(struct rq *rq, struct task_struct *prev) · line 2765

Quoted 12 lines

#ifdef CONFIG_SMP

kernel/sched.c +4 -0
@@ -2744,6 +2756,10 @@ static void finish_task_switch(struct rq *rq, struct task_struct *prev)
        if (mm)
                mmdrop(mm);
        if (unlikely(prev_state == TASK_DEAD)) {
+               /* a deadline task is dying: stop the bandwidth timer */
+               if (deadline_task(prev))
+                       hrtimer_cancel(&prev->dl.dl_timer);
+
                /*
                 * Remove function-return probe instances associated with this
                 * task and put them back on the free list. 

Shouldn't this be done in the ->dequeue_task() callback?

Quoted 5 lines

Not sure of this snippet... Actually, it is one of the most disturbing piece of code of this whole scheduler. :-(

The reason why it is here is that I think it is needed to call hrtimer_cancel() _without_ holding the rq->lock, is that correct?

I think we can nest the hrtimer base lock inside the rq->lock these days, so it should be safe to call while holding it, anyway, lockdep will quickly tell you if you try ;-)

Quoted 1 line

It is

Is that a stmt or an unfinished sentence?

#20 lore raw

Re: [RFC 0/12][PATCH] SCHED_DEADLINE: fork and terminate task logic

Quoted 25 lines · Peter Zijlstra
Quoted 23 lines · Raistlin
Quoted 5 lines
Quoted 5 lines
kernel/sched.c +3 -0
+       } else if (rt_prio(p->prio))
+               p->sched_class = &rt_sched_class;
+       else
                p->sched_class = &fair_sched_class;
Quoted 15 lines

kernel/sched.c static void finish_task_switch(struct rq *rq, struct task_struct *prev) · line 2765

Quoted 12 lines

#ifdef CONFIG_SMP

kernel/sched.c +4 -0
@@ -2744,6 +2756,10 @@ static void finish_task_switch(struct rq *rq, struct task_struct *prev)
        if (mm)
                mmdrop(mm);
        if (unlikely(prev_state == TASK_DEAD)) {
+               /* a deadline task is dying: stop the bandwidth timer */
+               if (deadline_task(prev))
+                       hrtimer_cancel(&prev->dl.dl_timer);
+
                /*
                 * Remove function-return probe instances associated with this
                 * task and put them back on the free list. 

Shouldn't this be done in the ->dequeue_task() callback?

Not sure of this snippet... Actually, it is one of the most disturbing piece of code of this whole scheduler. :-(

Quoted 7 lines
Quoted 2 lines

The reason why it is here is that I think it is needed to call hrtimer_cancel() _without_ holding the rq->lock, is that correct?

I think we can nest the hrtimer base lock inside the rq->lock these days, so it should be safe to call while holding it, anyway, lockdep will quickly tell you if you try ;-)

Nice, I'll try this soon, thanks.

Quoted 4 lines
Quoted 1 line

It is

Is that a stmt or an unfinished sentence?

No, this is nothing, sorry! :-P

Regards,
Dario

Signature · 6 lines
<<This happens because I choose it to happen!>> (Raistlin Majere)
----------------------------------------------------------------------
Dario Faggioli, ReTiS Lab, Scuola Superiore Sant'Anna, Pisa  (Italy)

http://blog.linux.it/raistlin / [email protected] /
[email protected]
#21 lore raw

Re: [RFC 0/12][PATCH] SCHED_DEADLINE: fork and terminate task logic

In reply to Peter Zijlstra
Quoted 28 lines

From: Peter Zijlstra <[email protected]>
Date: Wed, Jan 13, 2010 05:15:11PM +0100

Quoted 23 lines · Raistlin
Quoted 5 lines
Quoted 5 lines
kernel/sched.c +3 -0
+       } else if (rt_prio(p->prio))
+               p->sched_class = &rt_sched_class;
+       else
                p->sched_class = &fair_sched_class;
Quoted 15 lines

kernel/sched.c static void finish_task_switch(struct rq *rq, struct task_struct *prev) · line 2765

Quoted 12 lines

#ifdef CONFIG_SMP

kernel/sched.c +4 -0
@@ -2744,6 +2756,10 @@ static void finish_task_switch(struct rq *rq, struct task_struct *prev)
        if (mm)
                mmdrop(mm);
        if (unlikely(prev_state == TASK_DEAD)) {
+               /* a deadline task is dying: stop the bandwidth timer */
+               if (deadline_task(prev))
+                       hrtimer_cancel(&prev->dl.dl_timer);
+
                /*
                 * Remove function-return probe instances associated with this
                 * task and put them back on the free list. 

Shouldn't this be done in the ->dequeue_task() callback?

Not sure of this snippet... Actually, it is one of the most disturbing piece of code of this whole scheduler. :-(

Quoted 7 lines
Quoted 2 lines

The reason why it is here is that I think it is needed to call hrtimer_cancel() _without_ holding the rq->lock, is that correct?

I think we can nest the hrtimer base lock inside the rq->lock these days, so it should be safe to call while holding it, anyway, lockdep will quickly tell you if you try ;-)

I may be wrong, but the race here should be between the hrtimer_cancel() and the handler itself (which takes rq->lock): if the timer handler is running on a different cpu and still it has not entered its critical section we may end up here waiting for it to terminate, but that will never happen.

If we are able to enforce that both hrtimer_cancel() and the timer handler are always executed on the same cpu then we should be safe, because this code would never be executed with a running handler.

author
#22 lore raw

Re: [RFC 0/12][PATCH] SCHED_DEADLINE: added sched_*_ex syscalls

In reply to Raistlin

This commits adds the new syscalls needed to set/get the parameters for SCHED_DEADLINE scheduling policy. As it can be expected, they all deal with sched_param_ex.

The new syscalls are:
* sched_setscheduler_ex,
* sched_setparam_ex,
* sched_getparam_ex.

They have been added to x86, x86-64 and ARM only for now, since these are the only architectures we are able to test... But adding the bits needed for supporting other archs is more than straightforward...

---
 arch/arm/include/asm/unistd.h      |    3 +
 arch/arm/kernel/calls.S            |    3 +
 arch/x86/ia32/ia32entry.S          |    3 +
 arch/x86/include/asm/unistd_32.h   |    5 +-
 arch/x86/include/asm/unistd_64.h   |    6 ++
 arch/x86/kernel/syscall_table_32.S |    3 +
 include/linux/syscalls.h           |    7 ++
 kernel/sched.c                     |  168 +++++++++++++++++++++++++++++++++---
 8 files changed, 185 insertions(+), 13 deletions(-)
arch/arm/include/asm/unistd.h +3 -0
index 7020217..09b927e 100644
@@ -391,6 +391,9 @@
 #define __NR_pwritev			(__NR_SYSCALL_BASE+362)
 #define __NR_rt_tgsigqueueinfo		(__NR_SYSCALL_BASE+363)
 #define __NR_perf_event_open		(__NR_SYSCALL_BASE+364)
+#define __NR_sched_setscheduler_ex	(__NR_SYSCALL_BASE+365)
+#define __NR_sched_setparam_ex		(__NR_SYSCALL_BASE+366)
+#define __NR_sched_getparam_ex		(__NR_SYSCALL_BASE+367)
 
 /*
  * The following SWIs are ARM private.
arch/arm/kernel/calls.S +3 -0
index fafce1b..42ad362 100644
@@ -374,6 +374,9 @@
 		CALL(sys_pwritev)
 		CALL(sys_rt_tgsigqueueinfo)
 		CALL(sys_perf_event_open)
+/* 365 */	CALL(sys_sched_setscheduler_ex)
+		CALL(sys_sched_setparam_ex)
+		CALL(sys_sched_getparam_ex)
 #ifndef syscalls_counted
 .equ syscalls_padding, ((NR_syscalls + 3) & ~3) - NR_syscalls
 #define syscalls_counted
arch/x86/ia32/ia32entry.S +3 -0
index 1733f9f..3d04691 100644
@@ -842,4 +842,7 @@ ia32_sys_call_table:
 	.quad compat_sys_pwritev
 	.quad compat_sys_rt_tgsigqueueinfo	/* 335 */
 	.quad sys_perf_event_open
+	.quad sys_sched_setscheduler_ex
+	.quad sys_sched_setparam_ex
+	.quad sys_sched_getparam_ex
 ia32_syscall_end:
arch/x86/include/asm/unistd_32.h +4 -1
index 6fb3c20..3928c04 100644
@@ -342,10 +342,13 @@
 #define __NR_pwritev		334
 #define __NR_rt_tgsigqueueinfo	335
 #define __NR_perf_event_open	336
+#define __NR_sched_setscheduler_ex	337
+#define __NR_sched_setparam_ex		338
+#define __NR_sched_getparam_ex		339
 
 #ifdef __KERNEL__
 
-#define NR_syscalls 337
+#define NR_syscalls 340
 
 #define __ARCH_WANT_IPC_PARSE_VERSION
 #define __ARCH_WANT_OLD_READDIR
arch/x86/include/asm/unistd_64.h +6 -0
index 8d3ad0a..84b0743 100644
@@ -661,6 +661,12 @@ __SYSCALL(__NR_pwritev, sys_pwritev)
 __SYSCALL(__NR_rt_tgsigqueueinfo, sys_rt_tgsigqueueinfo)
 #define __NR_perf_event_open			298
 __SYSCALL(__NR_perf_event_open, sys_perf_event_open)
+#define __NR_sched_setscheduler_ex		299
+__SYSCALL(__NR_sched_setscheduler_ex, sys_sched_setscheduler_ex)
+#define __NR_sched_setparam_ex			300
+__SYSCALL(__NR_sched_setparam_ex, sys_sched_setparam_ex)
+#define __NR_sched_getparam_ex			301
+__SYSCALL(__NR_sched_getparam_ex, sys_sched_getparam_ex)
 
 #ifndef __NO_STUBS
 #define __ARCH_WANT_OLD_READDIR
arch/x86/kernel/syscall_table_32.S +3 -0
index 0157cd2..38f056c 100644
@@ -336,3 +336,6 @@ ENTRY(sys_call_table)
 	.long sys_pwritev
 	.long sys_rt_tgsigqueueinfo	/* 335 */
 	.long sys_perf_event_open
+	.long sys_sched_setscheduler_ex
+	.long sys_sched_setparam_ex
+	.long sys_sched_getparam_ex
include/linux/syscalls.h +7 -0
index a990ace..dad0b33 100644
@@ -33,6 +33,7 @@ struct pollfd;
 struct rlimit;
 struct rusage;
 struct sched_param;
+struct sched_param_ex;
 struct semaphore;
 struct sembuf;
 struct shmid_ds;
@@ -390,11 +391,17 @@ asmlinkage long sys_clock_nanosleep(clockid_t which_clock, int flags,
 asmlinkage long sys_nice(int increment);
 asmlinkage long sys_sched_setscheduler(pid_t pid, int policy,
 					struct sched_param __user *param);
+asmlinkage long sys_sched_setscheduler_ex(pid_t pid, int policy,
+					struct sched_param_ex __user *param);
 asmlinkage long sys_sched_setparam(pid_t pid,
 					struct sched_param __user *param);
+asmlinkage long sys_sched_setparam_ex(pid_t pid,
+					struct sched_param_ex __user *param);
 asmlinkage long sys_sched_getscheduler(pid_t pid);
 asmlinkage long sys_sched_getparam(pid_t pid,
 					struct sched_param __user *param);
+asmlinkage long sys_sched_getparam_ex(pid_t pid,
+					struct sched_param_ex __user *param);
 asmlinkage long sys_sched_setaffinity(pid_t pid, unsigned int len,
 					unsigned long __user *user_mask_ptr);
 asmlinkage long sys_sched_getaffinity(pid_t pid, unsigned int len,
kernel/sched.c +156 -12

255 lines not on this page · raw message

Signature · 9 lines
1.6.0.4

-- 
<<This happens because I choose it to happen!>> (Raistlin Majere)
----------------------------------------------------------------------
Dario Faggioli, ReTiS Lab, Scuola Superiore Sant'Anna, Pisa  (Italy)

http://blog.linux.it/raistlin / [email protected] /
[email protected]
author
#23 lore raw

Re: [RFC 0/12][PATCH] SCHED_DEADLINE: added sched-debug support.

In reply to Raistlin

This commit adds the debugging output support for the SCHED_DEADLINE runqueue.

---
 include/linux/sched.h   |    6 ++++++
 kernel/sched_deadline.c |   21 +++++++++++++++++++++
 kernel/sched_debug.c    |   33 +++++++++++++++++++++++++++++++++
 3 files changed, 60 insertions(+), 0 deletions(-)
include/linux/sched.h +6 -0
index 20e1a6a..fac928a 100644
@@ -167,6 +167,8 @@ extern void proc_sched_show_task(struct task_struct *p, struct seq_file *m);
 extern void proc_sched_set_task(struct task_struct *p);
 extern void
 print_cfs_rq(struct seq_file *m, int cpu, struct cfs_rq *cfs_rq);
+extern void
+print_deadline_rq(struct seq_file *m, int cpu, struct dl_rq *dl_rq);
 #else
 static inline void
 proc_sched_show_task(struct task_struct *p, struct seq_file *m)
@@ -179,6 +181,10 @@ static inline void
 print_cfs_rq(struct seq_file *m, int cpu, struct cfs_rq *cfs_rq)
 {
 }
+static inline void
+print_deadline_rq(struct seq_file *m, int cpu, struct dl_rq *dl_rq)
+{
+}
 #endif
 
 extern unsigned long long time_sync_thresh;
kernel/sched_deadline.c +21 -0
index b4be178..f2c1b6e 100644
@@ -400,6 +400,16 @@ static void start_hrtick_deadline(struct rq *rq, struct task_struct *p)
 }
 #endif
 
+static struct sched_dl_entity *__pick_deadline_last_entity(struct dl_rq *dl_rq)
+{
+	struct rb_node *last = rb_last(&dl_rq->rb_root);
+
+	if (!last)
+		return NULL;
+
+	return rb_entry(last, struct sched_dl_entity, rb_node);
+}
+
 static struct sched_dl_entity *pick_next_deadline_entity(struct rq *rq,
 							 struct dl_rq *dl_rq)
 {
@@ -531,3 +541,14 @@ static const struct sched_class deadline_sched_class = {
 	.switched_to		= switched_to_deadline,
 };
 
+#ifdef CONFIG_SCHED_DEBUG
+static void print_deadline_stats(struct seq_file *m, int cpu)
+{
+	struct dl_rq *dl_rq = &cpu_rq(cpu)->dl;
+
+	rcu_read_lock();
+	for_each_leaf_deadline_rq(dl_rq, cpu_rq(cpu))
+		print_deadline_rq(m, cpu, dl_rq);
+	rcu_read_unlock();
+}
+#endif /* CONFIG_SCHED_DEBUG */
kernel/sched_debug.c +33 -0
index efb8440..809ba55 100644
@@ -246,6 +246,38 @@ void print_rt_rq(struct seq_file *m, int cpu, struct rt_rq *rt_rq)
 #undef P
 }
 
+void print_deadline_rq(struct seq_file *m, int cpu, struct dl_rq *dl_rq)
+{
+	s64 min_deadline = -1, max_deadline = -1;
+	struct rq *rq = &per_cpu(runqueues, cpu);
+	struct sched_dl_entity *last;
+	unsigned long flags;
+
+	SEQ_printf(m, "\ndl_rq[%d]:\n", cpu);
+
+	spin_lock_irqsave(&rq->lock, flags);
+	if (dl_rq->rb_leftmost)
+		min_deadline = (rb_entry(dl_rq->rb_leftmost,
+					 struct sched_dl_entity,
+					 rb_node))->deadline;
+	last = __pick_deadline_last_entity(dl_rq);
+	if (last)
+		max_deadline = last->deadline;
+	spin_unlock_irqrestore(&rq->lock, flags);
+
+#define P(x) \
+	SEQ_printf(m, "  .%-30s: %Ld\n", #x, (long long)(x))
+#define PN(x) \
+	SEQ_printf(m, "  .%-30s: %Ld.%06ld\n", #x, SPLIT_NS(x))
+
+	P(dl_rq->dl_nr_running);
+	PN(min_deadline);
+	PN(max_deadline);
+
+#undef PN
+#undef P
+}
+
 static void print_cpu(struct seq_file *m, int cpu)
 {
 	struct rq *rq = cpu_rq(cpu);
@@ -301,6 +333,7 @@ static void print_cpu(struct seq_file *m, int cpu)
 #endif
 	print_cfs_stats(m, cpu);
 	print_rt_stats(m, cpu);
+	print_deadline_stats(m, cpu);
 
 	print_rq(m, rq, cpu);
 }
Signature · 9 lines
1.6.0.4

-- 
<<This happens because I choose it to happen!>> (Raistlin Majere)
----------------------------------------------------------------------
Dario Faggioli, ReTiS Lab, Scuola Superiore Sant'Anna, Pisa  (Italy)

http://blog.linux.it/raistlin / [email protected] /
[email protected]
author
#24 lore raw

RFC PATCH 6/12 SCHED_DEADLINE: added scheduling latency tracer

In reply to Raistlin

This commit adds a new ftrace tracer 'wakeup_deadline', to trace the maximum wakeup latency of SCHED_DEADLINE tasks.

---
 kernel/trace/trace_sched_wakeup.c |   31 +++++++++++++++++++++++++++++++
 1 files changed, 31 insertions(+), 0 deletions(-)
kernel/trace/trace_sched_wakeup.c +31 -0
index 26185d7..180948c 100644
@@ -27,6 +27,7 @@ static int			wakeup_cpu;
 static int			wakeup_current_cpu;
 static unsigned			wakeup_prio = -1;
 static int			wakeup_rt;
+static int			wakeup_deadline;
 
 static raw_spinlock_t wakeup_lock =
 	(raw_spinlock_t)__RAW_SPIN_LOCK_UNLOCKED;
@@ -214,6 +215,9 @@ probe_wakeup(struct rq *rq, struct task_struct *p, int success)
 	tracing_record_cmdline(p);
 	tracing_record_cmdline(current);
 
+	if (wakeup_deadline && !deadline_task(p))
+		return;
+
 	if ((wakeup_rt && !rt_task(p)) ||
 			p->prio >= wakeup_prio ||
 			p->prio >= current->prio)
@@ -340,16 +344,25 @@ static int __wakeup_tracer_init(struct trace_array *tr)
 
 static int wakeup_tracer_init(struct trace_array *tr)
 {
+	wakeup_deadline = 0;
 	wakeup_rt = 0;
 	return __wakeup_tracer_init(tr);
 }
 
 static int wakeup_rt_tracer_init(struct trace_array *tr)
 {
+	wakeup_deadline = 0;
 	wakeup_rt = 1;
 	return __wakeup_tracer_init(tr);
 }
 
+static int wakeup_deadline_tracer_init(struct trace_array *tr)
+{
+	wakeup_deadline = 1;
+	wakeup_rt = 0;
+	return __wakeup_tracer_init(tr);
+}
+
 static void wakeup_tracer_reset(struct trace_array *tr)
 {
 	stop_wakeup_tracer(tr);
@@ -398,6 +411,20 @@ static struct tracer wakeup_rt_tracer __read_mostly =
 #endif
 };
 
+static struct tracer wakeup_deadline_tracer __read_mostly =
+{
+	.name		= "wakeup_deadline",
+	.init		= wakeup_deadline_tracer_init,
+	.reset		= wakeup_tracer_reset,
+	.start		= wakeup_tracer_start,
+	.stop		= wakeup_tracer_stop,
+	.wait_pipe	= poll_wait_pipe,
+	.print_max	= 1,
+#ifdef CONFIG_FTRACE_SELFTEST
+	.selftest    = trace_selftest_startup_wakeup,
+#endif
+};
+
 __init static int init_wakeup_tracer(void)
 {
 	int ret;
@@ -410,6 +437,10 @@ __init static int init_wakeup_tracer(void)
 	if (ret)
 		return ret;
 
+	ret = register_tracer(&wakeup_deadline_tracer);
+	if (ret)
+		return ret;
+
 	return 0;
 }
 device_initcall(init_wakeup_tracer);
Signature · 10 lines
1.6.0.4


-- 
<<This happens because I choose it to happen!>> (Raistlin Majere)
----------------------------------------------------------------------
Dario Faggioli, ReTiS Lab, Scuola Superiore Sant'Anna, Pisa  (Italy)

http://blog.linux.it/raistlin / [email protected] /
[email protected]
author
#25 lore raw

RFC PATCH 7/12 SCHED_DEADLINE: signal delivery when overrunning

In reply to Raistlin

Starting from this commit, the user can ask to receive a SIGXCPU signal every time the task runtime is overrun or a scheduling deadline is missed. This is done by means of the sched_flags field already present in sched_param_ex.

A runtime overrun will be quite common, e.g. due to coarse execution time accounting, wrong parameter assignement, etc.
A deadline miss --since the deadlines the scheduler sees are ``scheduling deadlines'' which have not necessarily to be equal to task's deadlines-- is much more unlikely, and should only happen in an overloaded system.

---
 include/linux/sched.h     |    5 ++++
 kernel/posix-cpu-timers.c |   52 +++++++++++++++++++++++++++++++++++++++++++-
 kernel/sched_deadline.c   |   18 +++++++++++++++
 3 files changed, 73 insertions(+), 2 deletions(-)
include/linux/sched.h +5 -0
index fac928a..16668f9 100644
@@ -95,6 +95,9 @@ struct sched_param {
 
 #include <asm/processor.h>
 
+#define SCHED_SIG_RORUN		0x80000000
+#define SCHED_SIG_DMISS		0x40000000
+
 struct sched_param_ex {
 	int sched_priority;
 	struct timespec sched_runtime;
@@ -1229,6 +1232,8 @@ struct sched_rt_entity {
 #define DL_NEW			0x00000001
 #define DL_THROTTLED		0x00000002
 #define DL_BOOSTED		0x00000004
+#define DL_RORUN		0x00000008
+#define DL_DMISS		0x00000010
 
 struct sched_dl_entity {
 	struct rb_node	rb_node;
kernel/posix-cpu-timers.c +50 -2

78 lines not on this page · raw message

kernel/sched_deadline.c +18 -0
index f2c1b6e..7b57bb0 100644
@@ -236,9 +236,27 @@ static void init_deadline_task(struct task_struct *p)
 static
 int deadline_runtime_exceeded(struct rq *rq, struct sched_dl_entity *dl_se)
 {
+	/*
+	 * if the user asked for that, we have to inform him about
+	 * a (scheduling) deadline miss ...
+	 */
+	if (unlikely(dl_se->flags & SCHED_SIG_DMISS &&
+	    deadline_time_before(dl_se->deadline, rq->clock)))
+		dl_se->flags |= DL_DMISS;
+
 	if (dl_se->runtime >= 0 || deadline_se_boosted(dl_se))
 		return 0;
 
+	/*
+	 * ... and the same appies to runtime overruns.
+	 *
+	 * Note that (hopefully small) runtime overruns are very likely
+	 * to occur, mainly due to accounting resolution, while missing a
+	 * scheduling deadline should happen only on oversubscribed systems.
+	 */
+	if (dl_se->flags & SCHED_SIG_RORUN)
+		dl_se->flags |= DL_RORUN;
+
 	dequeue_deadline_entity(dl_se);
 	if (!start_deadline_timer(dl_se, dl_se->deadline)) {
 		replenish_deadline_entity(dl_se);
Signature · 10 lines
1.6.0.4


-- 
<<This happens because I choose it to happen!>> (Raistlin Majere)
----------------------------------------------------------------------
Dario Faggioli, ReTiS Lab, Scuola Superiore Sant'Anna, Pisa  (Italy)

http://blog.linux.it/raistlin / [email protected] /
[email protected]
maintainer
#26 lore raw

Re: [RFC 7/12][PATCH] SCHED_DEADLINE: signal delivery when overrunning

Quoted 10 lines · Raistlin

Starting from this commit, the user can ask to receive a SIGXCPU signal every time the task runtime is overrun or a scheduling deadline is missed. This is done by means of the sched_flags field already present in sched_param_ex.

A runtime overrun will be quite common, e.g. due to coarse execution time accounting, wrong parameter assignement, etc.
A deadline miss --since the deadlines the scheduler sees are ``scheduling deadlines'' which have not necessarily to be equal to task's deadlines-- is much more unlikely, and should only happen in an overloaded system.

Right, I think its much better to not do this in posix-cpu-timers.c, that code is shite.

Its probably possible to set SIGXCPU pending and raise TIF_SIGPENDING from within the scheduler code, and that will be triggered when we return to userspace.

That also gets rid of that coarse execution time accounting muck, since the scheduler has ns accurate accounting.

author
#27 lore raw

Re: [RFC 7/12][PATCH] SCHED_DEADLINE: signal delivery when overrunning

Quoted 6 lines · Peter Zijlstra
Quoted 5 lines

A runtime overrun will be quite common, e.g. due to coarse execution time accounting, wrong parameter assignement, etc.
A deadline miss --since the deadlines the scheduler sees are ``scheduling deadlines'' which have not necessarily to be equal to task's deadlines-- is much more unlikely, and should only happen in an overloaded system.

Quoted 7 lines

Right, I think its much better to not do this in posix-cpu-timers.c, that code is shite.

Its probably possible to set SIGXCPU pending and raise TIF_SIGPENDING from within the scheduler code, and that will be triggered when we return to userspace.

Ok, this sounds a lot better to me too... I'll go for this!

Quoted 3 lines

That also gets rid of that coarse execution time accounting muck, since the scheduler has ns accurate accounting.

Yes --at least when the hrtick is enabled-- I agree that this is another very interesting benefit of this approach.

It'll be done like this in the next version of the patchset I'm preparing.

Thanks for the answer and regards,
Dario

Signature · 6 lines
<<This happens because I choose it to happen!>> (Raistlin Majere)
----------------------------------------------------------------------
Dario Faggioli, ReTiS Lab, Scuola Superiore Sant'Anna, Pisa  (Italy)

http://blog.linux.it/raistlin / [email protected] /
[email protected]
author
#28 lore raw

RFC PATCH 8/12 SCHED_DEADLINE: wait next instance syscall added.

In reply to Raistlin

This commit introduces another new SCHED_DEADLINE related syscall. It is called sched_wait_interval() and it has close-to-clock_nanosleep semantic.

However, for SCHED_DEADLINE tasks, it should be the call with which each job closes its current instance. In fact, in this case, the task is put to sleep and, when it wakes up, the scheduler is informed that a new job arrived, saving the overhead that usually comes with a task activation to enforce maximum task bandwidth.

---
 arch/arm/include/asm/unistd.h      |    1 +
 arch/arm/kernel/calls.S            |    1 +
 arch/x86/ia32/ia32entry.S          |    1 +
 arch/x86/include/asm/unistd_32.h   |    3 +-
 arch/x86/include/asm/unistd_64.h   |    2 +
 arch/x86/kernel/syscall_table_32.S |    1 +
 include/linux/sched.h              |    1 +
 include/linux/syscalls.h           |    3 ++
 kernel/sched.c                     |   71 ++++++++++++++++++++++++++++++++++++
 kernel/sched_deadline.c            |    9 +++++
 10 files changed, 92 insertions(+), 1 deletions(-)
arch/arm/include/asm/unistd.h +1 -0
index 09b927e..769ced1 100644
@@ -394,6 +394,7 @@
 #define __NR_sched_setscheduler_ex	(__NR_SYSCALL_BASE+365)
 #define __NR_sched_setparam_ex		(__NR_SYSCALL_BASE+366)
 #define __NR_sched_getparam_ex		(__NR_SYSCALL_BASE+367)
+#define __NR_sched_wait_interval	(__NR_SYSCALL_BASE+368)
 
 /*
  * The following SWIs are ARM private.
arch/arm/kernel/calls.S +1 -0
index 42ad362..8292271 100644
@@ -377,6 +377,7 @@
 /* 365 */	CALL(sys_sched_setscheduler_ex)
 		CALL(sys_sched_setparam_ex)
 		CALL(sys_sched_getparam_ex)
+		CALL(sys_sched_wait_interval)
 #ifndef syscalls_counted
 .equ syscalls_padding, ((NR_syscalls + 3) & ~3) - NR_syscalls
 #define syscalls_counted
arch/x86/ia32/ia32entry.S +1 -0
index 3d04691..9306b80 100644
@@ -845,4 +845,5 @@ ia32_sys_call_table:
 	.quad sys_sched_setscheduler_ex
 	.quad sys_sched_setparam_ex
 	.quad sys_sched_getparam_ex
+	.quad sys_sched_wait_interval		/* 340 */
 ia32_syscall_end:
arch/x86/include/asm/unistd_32.h +2 -1
index 3928c04..63954cb 100644
@@ -345,10 +345,11 @@
 #define __NR_sched_setscheduler_ex	337
 #define __NR_sched_setparam_ex		338
 #define __NR_sched_getparam_ex		339
+#define __NR_sched_wait_interval	340
 
 #ifdef __KERNEL__
 
-#define NR_syscalls 340
+#define NR_syscalls 341
 
 #define __ARCH_WANT_IPC_PARSE_VERSION
 #define __ARCH_WANT_OLD_READDIR
arch/x86/include/asm/unistd_64.h +2 -0
index 84b0743..63cccc7 100644
@@ -667,6 +667,8 @@ __SYSCALL(__NR_sched_setscheduler_ex, sys_sched_setscheduler_ex)
 __SYSCALL(__NR_sched_setparam_ex, sys_sched_setparam_ex)
 #define __NR_sched_getparam_ex			301
 __SYSCALL(__NR_sched_getparam_ex, sys_sched_getparam_ex)
+#define __NR_sched_wait_interval		302
+__SYSCALL(__NR_sched_wait_interval, sys_sched_wait_interval)
 
 #ifndef __NO_STUBS
 #define __ARCH_WANT_OLD_READDIR
arch/x86/kernel/syscall_table_32.S +1 -0
index 38f056c..bd2cc8e 100644
@@ -339,3 +339,4 @@ ENTRY(sys_call_table)
 	.long sys_sched_setscheduler_ex
 	.long sys_sched_setparam_ex
 	.long sys_sched_getparam_ex
+	.long sys_sched_wait_interval	/* 340 */
include/linux/sched.h +1 -0
index 16668f9..478e07c 100644
@@ -1088,6 +1088,7 @@ struct sched_class {
 	void (*enqueue_task) (struct rq *rq, struct task_struct *p, int wakeup);
 	void (*dequeue_task) (struct rq *rq, struct task_struct *p, int sleep);
 	void (*yield_task) (struct rq *rq);
+	void (*wait_interval) (struct task_struct *p);
 
 	void (*check_preempt_curr) (struct rq *rq, struct task_struct *p, int flags);
 
include/linux/syscalls.h +3 -0
index dad0b33..e01f59c 100644
@@ -407,6 +407,9 @@ asmlinkage long sys_sched_setaffinity(pid_t pid, unsigned int len,
 asmlinkage long sys_sched_getaffinity(pid_t pid, unsigned int len,
 					unsigned long __user *user_mask_ptr);
 asmlinkage long sys_sched_yield(void);
+asmlinkage long sys_sched_wait_interval(int flags,
+					const struct timespec __user *rqtp,
+					struct timespec __user *rmtp);
 asmlinkage long sys_sched_get_priority_max(int policy);
 asmlinkage long sys_sched_get_priority_min(int policy);
 asmlinkage long sys_sched_rr_get_interval(pid_t pid,
kernel/sched.c +71 -0

77 lines not on this page · raw message

kernel/sched_deadline.c +9 -0
index 7b57bb0..82c0192 100644
@@ -401,6 +401,14 @@ static void yield_task_deadline(struct rq *rq)
 {
 }
 
+/*
+ * Informs the scheduler that an instance ended.
+ */
+static void wait_interval_deadline(struct task_struct *p)
+{
+	p->dl.flags |= DL_NEW;
+}
+
 #ifdef CONFIG_SCHED_HRTICK
 static void start_hrtick_deadline(struct rq *rq, struct task_struct *p)
 {
@@ -538,6 +546,7 @@ static const struct sched_class deadline_sched_class = {
 	.enqueue_task		= enqueue_task_deadline,
 	.dequeue_task		= dequeue_task_deadline,
 	.yield_task		= yield_task_deadline,
+	.wait_interval		= wait_interval_deadline,
 
 	.check_preempt_curr	= check_preempt_curr_deadline,
 
Signature · 10 lines
1.6.0.4


-- 
<<This happens because I choose it to happen!>> (Raistlin Majere)
----------------------------------------------------------------------
Dario Faggioli, ReTiS Lab, Scuola Superiore Sant'Anna, Pisa  (Italy)

http://blog.linux.it/raistlin / [email protected] /
[email protected]
maintainer
#29 lore raw

Re: [RFC 8/12][PATCH] SCHED_DEADLINE: wait next instance syscall added.

Quoted 8 lines · Raistlin

This commit introduces another new SCHED_DEADLINE related syscall. It is called sched_wait_interval() and it has close-to-clock_nanosleep semantic.

However, for SCHED_DEADLINE tasks, it should be the call with which each job closes its current instance. In fact, in this case, the task is put to sleep and, when it wakes up, the scheduler is informed that a new job arrived, saving the overhead that usually comes with a task activation to enforce maximum task bandwidth.

The changelog suggests (and a very brief looks seems to confirm) that this code could be much smaller by using hrtimer_nanosleep().

The implementation as presented seems to only call ->wait_interval() when the timer arms, which seems like a bug, we should always call it, regardless of whether we're on a period boundary.

author
#30 lore raw

Re: [RFC 8/12][PATCH] SCHED_DEADLINE: wait next instance syscall added.

Quoted 6 lines · Peter Zijlstra
Quoted 5 lines

However, for SCHED_DEADLINE tasks, it should be the call with which each job closes its current instance. In fact, in this case, the task is put to sleep and, when it wakes up, the scheduler is informed that a new job arrived, saving the overhead that usually comes with a task activation to enforce maximum task bandwidth.

Quoted 7 lines

The changelog suggests (and a very brief looks seems to confirm) that this code could be much smaller by using hrtimer_nanosleep().

The implementation as presented seems to only call ->wait_interval() when the timer arms, which seems like a bug, we should always call it, regardless of whether we're on a period boundary.

Ok, thanks, I'll look carefully at that! The current code is an attempt of mine to replicate the behaviour of clock_nanosleep, but you're definitely right here, it can be done much better.

Thanks and regards,
Dario

Signature · 6 lines
<<This happens because I choose it to happen!>> (Raistlin Majere)
----------------------------------------------------------------------
Dario Faggioli, ReTiS Lab, Scuola Superiore Sant'Anna, Pisa  (Italy)

http://blog.linux.it/raistlin / [email protected] /
[email protected]
author
#31 lore raw

RFC PATCH 9/12 SCHED_DEADLINE: system wide bandwidth management

In reply to Raistlin

This commit adds the capability of controlling the maximum, system wide, CPU bandwidth that is devoted to SCHED_DEADLINE tasks.

This is done by means of two files:
- /proc/sys/kernel/sched_deadline_runtime_us,
- /proc/sys/kernel/sched_deadline_period_us.
The ratio runtime/period is the total bandwidth all the SCHED_DEADLINE tasks can use in the system as a whole.
Trying to create tasks in such a way that they exceed this limitation will fail, as soon as the bandwidth cap would be overcome.

Default value is _zero_ bandwidth available, thus write some numbers in those files before trying to start some SCHED_DEADLINE task. Setting runtime > period is allowed (i.e., more than 100% bandwidth available for -deadline tasks), since it makes more than sense in SMP systems.

---
 include/linux/sched.h |    7 ++
 kernel/sched.c        |  149 ++++++++++++++++++++++++++++++++++++++++++++++++-
 kernel/sysctl.c       |   16 +++++
 3 files changed, 171 insertions(+), 1 deletions(-)
include/linux/sched.h +7 -0
index 478e07c..4de72eb 100644
@@ -1984,6 +1984,13 @@ int sched_rt_handler(struct ctl_table *table, int write,
 		void __user *buffer, size_t *lenp,
 		loff_t *ppos);
 
+extern unsigned int sysctl_sched_deadline_period;
+extern int sysctl_sched_deadline_runtime;
+
+int sched_deadline_handler(struct ctl_table *table, int write,
+		void __user *buffer, size_t *lenp,
+		loff_t *ppos);
+
 extern unsigned int sysctl_sched_compat_yield;
 
 #ifdef CONFIG_RT_MUTEXES
kernel/sched.c +148 -1

186 lines not on this page · raw message

kernel/sysctl.c +16 -0
index 0d949c5..34117f9 100644
@@ -373,6 +373,22 @@ static struct ctl_table kern_table[] = {
 	},
 	{
 		.ctl_name	= CTL_UNNUMBERED,
+		.procname	= "sched_deadline_period_us",
+		.data		= &sysctl_sched_deadline_period,
+		.maxlen		= sizeof(unsigned int),
+		.mode		= 0644,
+		.proc_handler	= &sched_deadline_handler,
+	},
+	{
+		.ctl_name	= CTL_UNNUMBERED,
+		.procname	= "sched_deadline_runtime_us",
+		.data		= &sysctl_sched_deadline_runtime,
+		.maxlen		= sizeof(int),
+		.mode		= 0644,
+		.proc_handler	= &sched_deadline_handler,
+	},
+	{
+		.ctl_name	= CTL_UNNUMBERED,
 		.procname	= "sched_compat_yield",
 		.data		= &sysctl_sched_compat_yield,
 		.maxlen		= sizeof(unsigned int),
Signature · 10 lines
1.6.0.4


-- 
<<This happens because I choose it to happen!>> (Raistlin Majere)
----------------------------------------------------------------------
Dario Faggioli, ReTiS Lab, Scuola Superiore Sant'Anna, Pisa  (Italy)

http://blog.linux.it/raistlin / [email protected] /
[email protected]
#32 lore raw

Re: [RFC 9/12][PATCH] SCHED_DEADLINE: system wide bandwidth management

Quoted 11 lines · Raistlin

This commit adds the capability of controlling the maximum, system wide, CPU bandwidth that is devoted to SCHED_DEADLINE tasks.

This is done by means of two files:
 - /proc/sys/kernel/sched_deadline_runtime_us,
 - /proc/sys/kernel/sched_deadline_period_us.
The ratio runtime/period is the total bandwidth all the SCHED_DEADLINE tasks can use in the system as a whole.
Trying to create tasks in such a way that they exceed this limitation will fail, as soon as the bandwidth cap would be overcome.

Quoted 5 lines

Default value is _zero_ bandwidth available, thus write some numbers in those files before trying to start some SCHED_DEADLINE task. Setting runtime > period is allowed (i.e., more than 100% bandwidth available for -deadline tasks), since it makes more than sense in SMP systems.

I don't like this interface. A couple of issues that come to mind are
1. There is no check to prevent over provisioning of the system (if I have missed the check, please correct me)
2. It is not CPU hotplug safe (I can understand that it is not that important an issue now, but we should keep in mind that linux is hotplug capable, so we would need to hook into the hotplug mechanism)

I would very much prefer the current interface where the runtime <= period is always enforced. For SMP then across the system we would allow a runtime equivalent to runtime * NR_CPU. I think it would make more sense to push it as a percentage system wide. (I don't think it should be an issue for processes since a process can only run one CPU so its runtime and period will mean just that and not percentage). comments?

thanks,
Dhaval

Signature · 3 lines
Ogden Nash  - "The trouble with a kitten is that when it grows up,
it's always a cat." -
http://www.brainyquote.com/quotes/authors/o/ogden_nash.html
maintainer
#33 lore raw

Re: [RFC 9/12][PATCH] SCHED_DEADLINE: system wide bandwidth management

In reply to Raistlin
Quoted 11 lines · Raistlin

This commit adds the capability of controlling the maximum, system wide, CPU bandwidth that is devoted to SCHED_DEADLINE tasks.

This is done by means of two files:
- /proc/sys/kernel/sched_deadline_runtime_us,
- /proc/sys/kernel/sched_deadline_period_us.
The ratio runtime/period is the total bandwidth all the SCHED_DEADLINE tasks can use in the system as a whole.
Trying to create tasks in such a way that they exceed this limitation will fail, as soon as the bandwidth cap would be overcome.

Quoted 4 lines

Default value is _zero_ bandwidth available, thus write some numbers in those files before trying to start some SCHED_DEADLINE task. Setting runtime > period is allowed (i.e., more than 100% bandwidth available for -deadline tasks), since it makes more than sense in SMP systems.

Right, so the current rt bandwidth controls go up to 100%, where 100% is root_domain wide. That is, the bandwidth usage scale is irrespective of the number of cpus.

If that was the best choice could of course be argued, but since we have that, it would be strange to add another set of controls which do not conform.

author
#34 lore raw

Re: [RFC 9/12][PATCH] SCHED_DEADLINE: system wide bandwidth management

Quoted 9 lines · Peter Zijlstra
Quoted 4 lines

Default value is _zero_ bandwidth available, thus write some numbers in those files before trying to start some SCHED_DEADLINE task. Setting runtime > period is allowed (i.e., more than 100% bandwidth available for -deadline tasks), since it makes more than sense in SMP systems.

Right, so the current rt bandwidth controls go up to 100%, where 100% is root_domain wide. That is, the bandwidth usage scale is irrespective of the number of cpus.

Yep, I know. Mine controls were working a little bit different because of the fact I have bandwidth control at the task group --not rq-- level. Anyway...

Quoted 4 lines

If that was the best choice could of course be argued, but since we have that, it would be strange to add another set of controls which do not conform.

... I again agree that consistency come first, and I'll move the controls in the right place, and convert them to the conforming behavior.

Thanks and regards,
Dario

Signature · 6 lines
<<This happens because I choose it to happen!>> (Raistlin Majere)
----------------------------------------------------------------------
Dario Faggioli, ReTiS Lab, Scuola Superiore Sant'Anna, Pisa  (Italy)

http://blog.linux.it/raistlin / [email protected] /
[email protected]
author
#35 lore raw

RFC PATCH 10/12 SCHED_DEADLINE: group bandwidth management code

In reply to Raistlin

CPU Container Groups support for SCHED_DEADLINE is introduced by this commit.

CGroups, if configured, have a SCHED_DEADLINE bandwidth, and it is enforced that the sum of the bandwidths of entities (tasks and groups) belonging to a group stays below its own bandwidth.

---
 init/Kconfig            |   14 ++
 kernel/sched.c          |  419 +++++++++++++++++++++++++++++++++++++++++++++++
 kernel/sched_deadline.c |    4 +
 kernel/sched_debug.c    |    3 +-
 4 files changed, 439 insertions(+), 1 deletions(-)
init/Kconfig +14 -0
index 09c5c64..17318ca 100644
@@ -454,6 +454,20 @@ config RT_GROUP_SCHED
 	  realtime bandwidth for them.
 	  See Documentation/scheduler/sched-rt-group.txt for more information.
 
+config DEADLINE_GROUP_SCHED
+	bool "Group scheduling for SCHED_DEADLINE"
+	depends on EXPERIMENTAL
+	depends on GROUP_SCHED
+	depends on CGROUPS
+	depends on !USER_SCHED
+	default n
+	help
+	  This feature lets you explicitly specify, in terms of runtime
+	  and period, the bandwidth of a task control group. This means
+	  tasks (and other groups) can be added to it only up to such
+	  ``bandwidth cap'', which might be useful for avoiding or
+	  controlling oversubscription.
+
 choice
 	depends on GROUP_SCHED
 	prompt "Basis for grouping tasks"
kernel/sched.c +419 -0

564 lines not on this page · raw message

kernel/sched_deadline.c +4 -0
index 82c0192..a14b928 100644
@@ -15,6 +15,10 @@
  * However, thanks to bandwidth isolation, overruns and deadline misses
  * remains local, and does not affect any other task in the system.
  *
+ * Groups, if configured, have bandwidth as well, and it is enforced that
+ * the sum of the bandwidths of entities (tasks and groups) belonging to
+ * a group stays below its own bandwidth.
+ *
  * Copyright (C) 2009 Dario Faggioli, Michael Trimarchi
  */
 
kernel/sched_debug.c +2 -1
index 809ba55..27ab926 100644
@@ -146,7 +146,8 @@ static void print_rq(struct seq_file *m, struct rq *rq, int rq_cpu)
 }
 
 #if defined(CONFIG_CGROUP_SCHED) && \
-	(defined(CONFIG_FAIR_GROUP_SCHED) || defined(CONFIG_RT_GROUP_SCHED))
+	(defined(CONFIG_FAIR_GROUP_SCHED) || defined(CONFIG_RT_GROUP_SCHED) || \
+	 defined(CONFIG_DEADLINE_GROUP_SCHED))
 static void task_group_path(struct task_group *tg, char *buf, int buflen)
 {
 	/* may be NULL if the underlying cgroup isn't fully-created yet */
Signature · 10 lines
1.6.0.4


-- 
<<This happens because I choose it to happen!>> (Raistlin Majere)
----------------------------------------------------------------------
Dario Faggioli, ReTiS Lab, Scuola Superiore Sant'Anna, Pisa  (Italy)

http://blog.linux.it/raistlin / [email protected] /
[email protected]
maintainer
#36 lore raw

Re: [RFC 10/12][PATCH] SCHED_DEADLINE: group bandwidth management code

Quoted 5 lines · Raistlin

CPU Container Groups support for SCHED_DEADLINE is introduced by this commit.

CGroups, if configured, have a SCHED_DEADLINE bandwidth, and it is enforced that the sum of the bandwidths of entities (tasks and groups) belonging to a group stays below its own bandwidth.

No real comment on the code here, but since we have a deadline bandwidth reservation, should we not also couple to the existing rt (fifo) bandwidth reservation?

We can't after all guarantee the FIFO time if there's deadline reservations around for more.

author
#37 lore raw

Re: [RFC 10/12][PATCH] SCHED_DEADLINE: group bandwidth management code

Quoted 7 lines · Peter Zijlstra
Quoted 5 lines · Raistlin

CPU Container Groups support for SCHED_DEADLINE is introduced by this commit.

CGroups, if configured, have a SCHED_DEADLINE bandwidth, and it is enforced that the sum of the bandwidths of entities (tasks and groups) belonging to a group stays below its own bandwidth.

Quoted 7 lines

No real comment on the code here, but since we have a deadline bandwidth reservation, should we not also couple to the existing rt (fifo) bandwidth reservation?

We can't after all guarantee the FIFO time if there's deadline reservations around for more.

Mmm... If I'm getting this right, you're suggesting to decrease from the available system rt-bandwidth the bandwidth devoted to deadline scheduling.

This make more than sense to me... I'll think about how to make the code reflect that.

Thanks and regards,
Dario

Signature · 6 lines
<<This happens because I choose it to happen!>> (Raistlin Majere)
----------------------------------------------------------------------
Dario Faggioli, ReTiS Lab, Scuola Superiore Sant'Anna, Pisa  (Italy)

http://blog.linux.it/raistlin / [email protected] /
[email protected]
author
#38 lore raw

RFC PATCH 11/12 SCHED_DEADLINE: documentation

In reply to Raistlin

This commit adds some more documentation and comments on how the new scheduling policy works.

---
 Documentation/scheduler/sched-deadline.txt |  174 ++++++++++++++++++++++++++++
 include/linux/sched.h                      |   45 +++++++
 init/Kconfig                               |    1 +
 3 files changed, 220 insertions(+), 0 deletions(-)
 create mode 100644 Documentation/scheduler/sched-deadline.txt
Documentation/scheduler/sched-deadline.txt new file +174 -0
new file mode 100644
index 0000000..cadfa9f
@@ -0,0 +1,174 @@
+			Deadline Task and Group Scheduling
+			----------------------------------
+
+CONTENTS
+========
+
+0. WARNING
+1. Overview
+  1.1 Task scheduling
+  1.2 Group scheduling
+2. The interface
+  2.1 System-wide settings
+  2.2 Default behavior
+  2.3 Basis for grouping tasks
+3. Future plans
+
+
+0. WARNING
+==========
+
+ Fiddling with these settings can result in an unpredictable or even unstable
+ system behavior. As for -rt (group) scheduling, it is assumed that root
+ knows what he is doing.
+
+
+1. Overview
+===========
+
+The SCHED_DEADLINE scheduling class implements the Earliest Deadline First
+(EDF) algorithm and uses the Constant Bandwidth Server (CBS) to provide
+bandwidth isolation among tasks.
+The implementation is aligned with the current mainstream kernel, and it
+relies on standard Linux mechanisms (e.g., control groups) to natively support
+multicore platforms and to provide hierarchical scheduling through a standard
+API.
+
+
+1.1 Task scheduling
+-------------------
+
+The SCHED_DEADLINE scheduling class does not make any restrictive assumption
+on the characteristics of the tasks, thus it can handle:
+ * periodic tasks, typical in real-time and control applications;
+ * sporadic tasks, typical in soft real-time and multimedia applications;
+ * aperiodic tasks.
+
+This is mainly because temporal isolation is ensured: the temporal behavior
+of each task (i.e., its ability to meet deadlines) is not affected by what
+happens in any other task in the system.
+In other words, even if a task misbehaves, it is not able to exploit larger
+execution time than the amount that has been devoted to it.
+
+In fact, each task is assigned a ``scheduling budget'' (sched_runtime) and a
+``scheduling deadline'' (sched_deadline, also called period in this branch
+of the real-time literature).
+This means the task is guaranteed to execute for an amount of time equal to
+sched_runtime every sched_deadline, i.e., to utilize at most a CPU bandwidth
+equal to sched_runtime/sched_deadline.
+If it tries to execute more than its sched_runtime it is slowed down, by
+stopping it until the time instant of its next deadline.
+
+However, although this algorithm (i.e., the CBS) is effective for encapsulating
+aperiodic or sporadic --real-time or non real-time-- tasks in a real-time
+EDF scheduled system, it imposes some overhead to ``standard'' periodic tasks.
+Therefore, we make it possible for periodic task to specify that they are going
+to sleep, waiting for the next activation, because a periodic instance just
+ended. This avoid them (provided they behave well!) being disturbed by
+the CBS bandwidth management logic.
+
+
+Group scheduling
+----------------
+
+The scheduling class is integrated with the control groups mechanism in order
+to allow the creation of groups of tasks with a cap on their total utilization.
+
+However, groups plays no role in the on-line scheduling decisions. This is
+different on how group scheduling works for the -rt scheduling class, and
+the difference comes from the fact that -deadline tasks _already_ have their
+own bandwidth, which is not true for standard POSIX SCHED_FIFO or SCHED_RR
+processes and threads.
+
+Therefore, there is no need for fully hierarchical runqueue implementation,
+hierarchical runtime accounting, etc., which result in simpler code and
+smaller overhead.
+All we do are bandwidth ``consistency checks'', which are performed at the
+occurrence of the following events:
+ * a -deadline task is created or moved inside a group,
+ * the parameters of a -deadline task (if inside a group) are modified,
+ * the -deadline related parameters of a group are modified.
+
+The purpose of this is ensuring the cumulative utilization of tasks and
+groups is below the one of the group containing them (see below).
+
+
+2. The Interface
+================
+
+
+2.1 System wide settings
+------------------------
+
+The system wide settings are configured under the /proc virtual file system:
+
+/proc/sys/kernel/sched_deadline_period_us:
+  The scheduling period that is equivalent to 100% CPU bandwidth
+
+/proc/sys/kernel/sched_deadline_runtime_us:
+  A global limit on how much time real-time scheduling may use. Even without
+  CONFIG_DEADLINE_GROUP_SCHED enabled, this will limit time reserved to
+  -deadline processes. With CONFIG_DEADLINE_GROUP_SCHED it signifies the
+  total bandwidth available to all real-time groups.
+
+  * Time is specified in us because the interface is s32. This gives an
+    operating range from 1us to about 35 minutes;
+  * sched_deadline_period_us takes values from 1 to INT_MAX;
+  * sched_deadline_runtime_us takes values from 1 to INT_MAX;
+  * setting runtime = period specifies 100% bandwidth exploitable by
+    -deadline tasks;
+  * setting runtime > period allows for more than 100% bandwidth
+    exploitable by -deadline tasks, which still might make sense,
+    especially in SMP systems.
+
+
+2.2 Default behavior
+---------------------
+
+The default values for sched_deadline_period_us and
+sched_deadline_runtime_us are 0.  This means no -deadline tasks or
+groups can be created!
+
+Consistently, bandwidth assigned to the root group, and to each newly created
+group, is 0 as well.
+
+
+2.3 Basis for grouping tasks
+----------------------------
+
+There are two compile-time settings for allocating CPU bandwidth. These are
+configured using the "Basis for grouping tasks" multiple choice menu under
+General setup > Group CPU Scheduler:
+
+CONFIG_USER_SCHED (aka "Basis for grouping tasks" =  "user id")
+
+This, for now, is not supported for deadline group scheduling.
+
+CONFIG_CGROUP_SCHED (aka "Basis for grouping tasks" = "Control groups")
+
+This uses the /cgroup virtual file system, i.e.:
+ * /cgroup/<cgroup>/cpu.deadline_runtime_us and
+ * /cgroup/<cgroup>/cpu.deadline_period_us,
+to control the CPU time reserved or each control group.
+
+For more information on working with control groups, you should read
+Documentation/cgroups/cgroups.txt as well.
+
+Group settings are checked against the following limits:
+
+ * for the root group {r}
+     runtime_{r} / period_{r} <= global_runtime / global_period
+ * for each group {i}, subgroup of group {j}
+     \Sum_{i} runtime_{i} / period_{i} <= runtime_{j} / period_{j}
+
+
+3. Future plans
+===============
+
+Only two, but very important pieces are missing:
+
+ * SMP/multicore global scheduling throughout push and pull logic (as in
+   -rt). This is not finished, but is on it's way, and will come very soon!
+ * Deadline/BandWidth Inheritance and/or Proxy Execution mechanisms for the
+  rt_mutexes. This probably need some more discussion, and also some more time
+  to have it implemented!
include/linux/sched.h +45 -0

51 lines not on this page · raw message

init/Kconfig +1 -0
index 17318ca..d4a52b7 100644
@@ -467,6 +467,7 @@ config DEADLINE_GROUP_SCHED
 	  tasks (and other groups) can be added to it only up to such
 	  ``bandwidth cap'', which might be useful for avoiding or
 	  controlling oversubscription.
+	  See Documentation/scheduler/sched-deadline.txt for more.
 
 choice
 	depends on GROUP_SCHED
Signature · 10 lines
1.6.0.4


-- 
<<This happens because I choose it to happen!>> (Raistlin Majere)
----------------------------------------------------------------------
Dario Faggioli, ReTiS Lab, Scuola Superiore Sant'Anna, Pisa  (Italy)

http://blog.linux.it/raistlin / [email protected] /
[email protected]
author
#39 lore raw

RFC PATCH 12/12 SCHED_DEADLINE: modified sched_*_ex API

In reply to Raistlin

This commit amends the new API introduced to deal with the new sched_param_ex scheduling parameter data structure.

What we add is one more parameter to all the functions, containing the size of sched_param_ex. It might turn out useful in possible future extensions of sched_param_ex itself, to avoid issue with ABI of legacy applications.

---
 include/linux/syscalls.h |    6 +++---
 kernel/sched.c           |   25 ++++++++++++++++---------
 2 files changed, 19 insertions(+), 12 deletions(-)
include/linux/syscalls.h +3 -3
index e01f59c..60a99a7 100644
@@ -391,16 +391,16 @@ asmlinkage long sys_clock_nanosleep(clockid_t which_clock, int flags,
 asmlinkage long sys_nice(int increment);
 asmlinkage long sys_sched_setscheduler(pid_t pid, int policy,
 					struct sched_param __user *param);
-asmlinkage long sys_sched_setscheduler_ex(pid_t pid, int policy,
+asmlinkage long sys_sched_setscheduler_ex(pid_t pid, int policy, unsigned len,
 					struct sched_param_ex __user *param);
 asmlinkage long sys_sched_setparam(pid_t pid,
 					struct sched_param __user *param);
-asmlinkage long sys_sched_setparam_ex(pid_t pid,
+asmlinkage long sys_sched_setparam_ex(pid_t pid, unsigned len,
 					struct sched_param_ex __user *param);
 asmlinkage long sys_sched_getscheduler(pid_t pid);
 asmlinkage long sys_sched_getparam(pid_t pid,
 					struct sched_param __user *param);
-asmlinkage long sys_sched_getparam_ex(pid_t pid,
+asmlinkage long sys_sched_getparam_ex(pid_t pid, unsigned len,
 					struct sched_param_ex __user *param);
 asmlinkage long sys_sched_setaffinity(pid_t pid, unsigned int len,
 					unsigned long __user *user_mask_ptr);
kernel/sched.c +16 -9
index a8ebfa2..d3a61f5 100644
@@ -6662,7 +6662,7 @@ do_sched_setscheduler(pid_t pid, int policy, struct sched_param __user *param)
 }
 
 static int
-do_sched_setscheduler_ex(pid_t pid, int policy,
+do_sched_setscheduler_ex(pid_t pid, int policy, unsigned int len,
 			 struct sched_param_ex __user *param_ex)
 {
 	struct sched_param lparam;
@@ -6672,8 +6672,9 @@ do_sched_setscheduler_ex(pid_t pid, int policy,
 
 	if (!param_ex || pid < 0)
 		return -EINVAL;
-	if (copy_from_user(&lparam_ex, param_ex,
-	    sizeof(struct sched_param_ex)))
+	if (len > sizeof(struct sched_param_ex))
+		return -EINVAL;
+	if (copy_from_user(&lparam_ex, param_ex,len))
 		return -EFAULT;
 
 	rcu_read_lock();
@@ -6708,15 +6709,17 @@ SYSCALL_DEFINE3(sched_setscheduler, pid_t, pid, int, policy,
  * sys_sched_setscheduler_ex - set/change the scheduler policy to SCHED_DEADLINE
  * @pid: the pid in question.
  * @policy: new policy (should be SCHED_DEADLINE).
+ * @len: size of data pointed by param_ex.
  * @param: structure containg the extended deadline parameters.
  */
-SYSCALL_DEFINE3(sched_setscheduler_ex, pid_t, pid, int, policy,
+SYSCALL_DEFINE4(sched_setscheduler_ex, pid_t, pid,
+		int, policy, unsigned, len,
 		struct sched_param_ex __user *, param_ex)
 {
 	if (policy < 0)
 		return -EINVAL;
 
-	return do_sched_setscheduler_ex(pid, policy, param_ex);
+	return do_sched_setscheduler_ex(pid, policy, len, param_ex);
 }
 
 /**
@@ -6732,12 +6735,13 @@ SYSCALL_DEFINE2(sched_setparam, pid_t, pid, struct sched_param __user *, param)
 /**
  * sys_sched_setparam - set/change the DEADLINE parameters of a thread
  * @pid: the pid in question.
+ * @len: size of data pointed by param_ex.
  * @param_ex: structure containing the new parameters (deadline, runtime, etc.).
  */
-SYSCALL_DEFINE2(sched_setparam_ex, pid_t, pid,
+SYSCALL_DEFINE3(sched_setparam_ex, pid_t, pid, unsigned, len,
 		struct sched_param_ex __user *, param_ex)
 {
-	return do_sched_setscheduler_ex(pid, -1, param_ex);
+	return do_sched_setscheduler_ex(pid, -1, len, param_ex);
 }
 
 /**
@@ -6807,9 +6811,10 @@ out_unlock:
 /**
  * sys_sched_getparam - get the DEADLINE task parameters of a thread
  * @pid: the pid in question.
+ * @len: size of data pointed by param_ex.
  * @param_ex: structure containing the new parameters (deadline, runtime, etc.).
  */
-SYSCALL_DEFINE2(sched_getparam_ex, pid_t, pid,
+SYSCALL_DEFINE3(sched_getparam_ex, pid_t, pid, unsigned, len,
 		struct sched_param_ex __user *, param_ex)
 {
 	struct sched_param_ex lp;
@@ -6818,6 +6823,8 @@ SYSCALL_DEFINE2(sched_getparam_ex, pid_t, pid,
 
 	if (!param_ex || pid < 0)
 		return -EINVAL;
+	if (len < sizeof(struct sched_param_ex))
+		return -EINVAL;
 
 	read_lock(&tasklist_lock);
 	p = find_process_by_pid(pid);
@@ -6837,7 +6844,7 @@ SYSCALL_DEFINE2(sched_getparam_ex, pid_t, pid,
 	/*
 	 * This one might sleep, we cannot do it with a spinlock held ...
 	 */
-	retval = copy_to_user(param_ex, &lp, sizeof(*param_ex)) ? -EFAULT : 0;
+	retval = copy_to_user(param_ex, &lp, len) ? -EFAULT : 0;
 
 	return retval;
 
Signature · 9 lines
1.6.0.4

-- 
<<This happens because I choose it to happen!>> (Raistlin Majere)
----------------------------------------------------------------------
Dario Faggioli, ReTiS Lab, Scuola Superiore Sant'Anna, Pisa  (Italy)

http://blog.linux.it/raistlin / [email protected] /
[email protected]
maintainer
#40 lore raw

Re: [RFC 12/12][PATCH] SCHED_DEADLINE: modified sched_*_ex API

Quoted 13 lines · Raistlin
kernel/sched.c +2 -1
@@ -6807,9 +6811,10 @@ out_unlock:
 /**
  * sys_sched_getparam - get the DEADLINE task parameters of a thread
  * @pid: the pid in question.
+ * @len: size of data pointed by param_ex.
  * @param_ex: structure containing the new parameters (deadline, runtime, etc.).
  */
-SYSCALL_DEFINE2(sched_getparam_ex, pid_t, pid,
+SYSCALL_DEFINE3(sched_getparam_ex, pid_t, pid, unsigned, len,
                struct sched_param_ex __user *, param_ex)
 {
        struct sched_param_ex lp;

kernel/sched.c SYSCALL_DEFINE2(sched_getparam_ex, pid_t, pid, · line 6830

Quoted 8 lines
kernel/sched.c +2 -0
@@ -6818,6 +6823,8 @@ SYSCALL_DEFINE2(sched_getparam_ex, pid_t, pid,
 
        if (!param_ex || pid < 0)
                return -EINVAL;
+       if (len < sizeof(struct sched_param_ex))
+               return -EINVAL;
 
        read_lock(&tasklist_lock);
        p = find_process_by_pid(pid);

This allows len > sizeof().

kernel/sched.c SYSCALL_DEFINE2(sched_getparam_ex, pid_t, pid, · line 6849

Quoted 8 lines
kernel/sched.c +1 -1
@@ -6837,7 +6844,7 @@ SYSCALL_DEFINE2(sched_getparam_ex, pid_t, pid,
        /*
         * This one might sleep, we cannot do it with a spinlock held ...
         */
-       retval = copy_to_user(param_ex, &lp, sizeof(*param_ex)) ? -EFAULT : 0;
+       retval = copy_to_user(param_ex, &lp, len) ? -EFAULT : 0;
 
        return retval; 

Which would copy more than lp, resulting in a stack leak, right?

author
#41 lore raw

Re: [RFC 12/12][PATCH] SCHED_DEADLINE: modified sched_*_ex API

Quoted 20 lines · Peter Zijlstra
Quoted 19 lines · Raistlin
kernel/sched.c +4 -1
@@ -6807,9 +6811,10 @@ out_unlock:
 /**
  * sys_sched_getparam - get the DEADLINE task parameters of a thread
  * @pid: the pid in question.
+ * @len: size of data pointed by param_ex.
  * @param_ex: structure containing the new parameters (deadline, runtime, etc.).
  */
-SYSCALL_DEFINE2(sched_getparam_ex, pid_t, pid,
+SYSCALL_DEFINE3(sched_getparam_ex, pid_t, pid, unsigned, len,
                struct sched_param_ex __user *, param_ex)
 {
        struct sched_param_ex lp;
@@ -6818,6 +6823,8 @@ SYSCALL_DEFINE2(sched_getparam_ex, pid_t, pid,
 
        if (!param_ex || pid < 0)
                return -EINVAL;
+       if (len < sizeof(struct sched_param_ex))
+               return -EINVAL;
 
Quoted 5 lines

kernel/sched.c SYSCALL_DEFINE2(sched_getparam_ex, pid_t, pid, · line 6830

Quoted 2 lines
kernel/sched.c +0 -0
        read_lock(&tasklist_lock);
        p = find_process_by_pid(pid);

This allows len > sizeof().

Yes...

Quoted 11 lines

kernel/sched.c SYSCALL_DEFINE2(sched_getparam_ex, pid_t, pid, · line 6849

Quoted 8 lines
kernel/sched.c +1 -1
@@ -6837,7 +6844,7 @@ SYSCALL_DEFINE2(sched_getparam_ex, pid_t, pid,
        /*
         * This one might sleep, we cannot do it with a spinlock held ...
         */
-       retval = copy_to_user(param_ex, &lp, sizeof(*param_ex)) ? -EFAULT : 0;
+       retval = copy_to_user(param_ex, &lp, len) ? -EFAULT : 0;
 
        return retval; 

Which would copy more than lp, resulting in a stack leak, right?

... And yes again! :-)

This has been done bearing in mind that the _kernel_side_ sched_param_ex --once stabilized-- will never lower its size. I.e., it should always grow and, if/when it does, it should retain the position of existing fields, for the sake of backward compatibility.

In that case, I think, the only possible case we have to face is the one where the "old" userspace program/library uses a version of sched_param_ex which is smaller than the one in the kernel, and what we want is the kernel to fill only the fields existing in the userspace code.

Does all this make sense?

If yes, I guess I just have to flip the inequality in the if() turning it into "if (len > sizeof())" (, then apologize for the glaring bug! :-P) and then I'm done, am I?

Thanks and regards,
Dario

Signature · 6 lines
<<This happens because I choose it to happen!>> (Raistlin Majere)
----------------------------------------------------------------------
Dario Faggioli, ReTiS Lab, Scuola Superiore Sant'Anna, Pisa  (Italy)

http://blog.linux.it/raistlin / [email protected] /
[email protected]
maintainer
#42 lore raw

Re: [RFC 12/12][PATCH] SCHED_DEADLINE: modified sched_*_ex API

Quoted 52 lines · Raistlin
Quoted 20 lines · Peter Zijlstra
Quoted 19 lines · Raistlin
kernel/sched.c +4 -1
@@ -6807,9 +6811,10 @@ out_unlock:
 /**
  * sys_sched_getparam - get the DEADLINE task parameters of a thread
  * @pid: the pid in question.
+ * @len: size of data pointed by param_ex.
  * @param_ex: structure containing the new parameters (deadline, runtime, etc.).
  */
-SYSCALL_DEFINE2(sched_getparam_ex, pid_t, pid,
+SYSCALL_DEFINE3(sched_getparam_ex, pid_t, pid, unsigned, len,
                struct sched_param_ex __user *, param_ex)
 {
        struct sched_param_ex lp;
@@ -6818,6 +6823,8 @@ SYSCALL_DEFINE2(sched_getparam_ex, pid_t, pid,
 
        if (!param_ex || pid < 0)
                return -EINVAL;
+       if (len < sizeof(struct sched_param_ex))
+               return -EINVAL;
 
Quoted 5 lines

kernel/sched.c SYSCALL_DEFINE2(sched_getparam_ex, pid_t, pid, · line 6830

Quoted 2 lines
kernel/sched.c +0 -0
        read_lock(&tasklist_lock);
        p = find_process_by_pid(pid);

This allows len > sizeof().

Yes...

Quoted 11 lines

kernel/sched.c SYSCALL_DEFINE2(sched_getparam_ex, pid_t, pid, · line 6849

Quoted 8 lines
kernel/sched.c +1 -1
@@ -6837,7 +6844,7 @@ SYSCALL_DEFINE2(sched_getparam_ex, pid_t, pid,
        /*
         * This one might sleep, we cannot do it with a spinlock held ....
         */
-       retval = copy_to_user(param_ex, &lp, sizeof(*param_ex)) ? -EFAULT : 0;
+       retval = copy_to_user(param_ex, &lp, len) ? -EFAULT : 0;
 
        return retval; 

Which would copy more than lp, resulting in a stack leak, right?

.... And yes again! :-)

This has been done bearing in mind that the _kernel_side_ sched_param_ex --once stabilized-- will never lower its size. I.e., it should always grow and, if/when it does, it should retain the position of existing fields, for the sake of backward compatibility.

In that case, I think, the only possible case we have to face is the one where the "old" userspace program/library uses a version of sched_param_ex which is smaller than the one in the kernel, and what we want is the kernel to fill only the fields existing in the userspace code.

Quoted 5 lines

Does all this make sense?

If yes, I guess I just have to flip the inequality in the if() turning it into "if (len > sizeof())" (, then apologize for the glaring bug! :-P) and then I'm done, am I?

Right, I think so..

maintainer
#43 lore raw

Re: [RFC 12/12][PATCH] SCHED_DEADLINE: modified sched_*_ex API

In reply to Raistlin
Quoted 31 lines · Raistlin

This commit amends the new API introduced to deal with the new sched_param_ex scheduling parameter data structure.

What we add is one more parameter to all the functions, containing the size of sched_param_ex. It might turn out useful in possible future extensions of sched_param_ex itself, to avoid issue with ABI of legacy applications.

kernel/sched.c +4 -1
@@ -6807,9 +6811,10 @@ out_unlock:
 /**
  * sys_sched_getparam - get the DEADLINE task parameters of a thread
  * @pid: the pid in question.
+ * @len: size of data pointed by param_ex.
  * @param_ex: structure containing the new parameters (deadline, runtime, etc.).
  */
-SYSCALL_DEFINE2(sched_getparam_ex, pid_t, pid,
+SYSCALL_DEFINE3(sched_getparam_ex, pid_t, pid, unsigned, len,
 		struct sched_param_ex __user *, param_ex)
 {
 	struct sched_param_ex lp;
@@ -6818,6 +6823,8 @@ SYSCALL_DEFINE2(sched_getparam_ex, pid_t, pid,
 
 	if (!param_ex || pid < 0)
 		return -EINVAL;
+	if (len < sizeof(struct sched_param_ex))
+		return -EINVAL;
 
 	read_lock(&tasklist_lock);
 	p = find_process_by_pid(pid);

kernel/sched.c SYSCALL_DEFINE2(sched_getparam_ex, pid_t, pid, · line 6850

Quoted 8 lines
kernel/sched.c +1 -1
@@ -6837,7 +6844,7 @@ SYSCALL_DEFINE2(sched_getparam_ex, pid_t, pid,
 	/*
 	 * This one might sleep, we cannot do it with a spinlock held ...
 	 */
-	retval = copy_to_user(param_ex, &lp, sizeof(*param_ex)) ? -EFAULT : 0;
+	retval = copy_to_user(param_ex, &lp, len) ? -EFAULT : 0;
 
 	return retval;
 

I think this doesn't even do what it claims to do, namely provide a flexible ABI, since you fail the operation when there is not enough room provided. Hence, when we grow the struct an older program that was compiled against the smaller one will become an insta-fail.

What this should do is deal with smaller structs by ensuring the tail is 0 and simply copying out the head.

New bits in the flags field are also an interesting challenge.

author
#44 lore raw

Re: [RFC 12/12][PATCH] SCHED_DEADLINE: modified sched_*_ex API

Quoted 22 lines · Peter Zijlstra
Quoted 8 lines
kernel/sched.c +2 -0
 	if (!param_ex || pid < 0)
 		return -EINVAL;
+	if (len < sizeof(struct sched_param_ex))
+		return -EINVAL;
 
 	read_lock(&tasklist_lock);
 	p = find_process_by_pid(pid);

kernel/sched.c SYSCALL_DEFINE2(sched_getparam_ex, pid_t, pid, · line 6850

Quoted 8 lines
kernel/sched.c +1 -1
@@ -6837,7 +6844,7 @@ SYSCALL_DEFINE2(sched_getparam_ex, pid_t, pid,
 	/*
 	 * This one might sleep, we cannot do it with a spinlock held ...
 	 */
-	retval = copy_to_user(param_ex, &lp, sizeof(*param_ex)) ? -EFAULT : 0;
+	retval = copy_to_user(param_ex, &lp, len) ? -EFAULT : 0;
 
 	return retval;
 

I think this doesn't even do what it claims to do, namely provide a flexible ABI, since you fail the operation when there is not enough room provided. Hence, when we grow the struct an older program that was compiled against the smaller one will become an insta-fail.

Quoted 3 lines

What this should do is deal with smaller structs by ensuring the tail is 0 and simply copying out the head.

Yep... As said in the previous mail I wanted to do so, and I'll do it now that I see how odd was what I wrote! :-P

Quoted 2 lines

New bits in the flags field are also an interesting challenge.

Right... I think that a (partial?) solution could be to properly choose default values for newcomer flags, could that be right?

Thanks and regards,
Dario

Signature · 6 lines
<<This happens because I choose it to happen!>> (Raistlin Majere)
----------------------------------------------------------------------
Dario Faggioli, ReTiS Lab, Scuola Superiore Sant'Anna, Pisa  (Italy)

http://blog.linux.it/raistlin / [email protected] /
[email protected]