Skip to contentSkip to conversation

sched: SCHED_DEADLINE v8

PATCH In review Juri Lelli 4 participants 57 messages Oct 14, 2013 – Oct 17, 2013

Subsystems (10)
lore
Share & tools
lore

Juri Lelli

author
#0 lore raw

cover sched: SCHED_DEADLINE v8

Hello everyone,

here we go with a new version of the SCHED_DEADLINE patchset (v8). I know that it has been a while since I released last version [1], but I thought not to spam the mailing list with simple updates. Well... this IS basically an update to 3.12-rc5, but it comes right before the next Kernel Summit and Real Time Linux Workshop and, since I'll be present at both events, it is probably time to fire-up the discussion again.

Moreover, interesting news:

- a better mechanism for coordinating mutually exclusive access to critical sections is coming soon (we wrote a paper about it for RTLWS15 [2]);
- the patchset is now available in the 3.4 and 3.10 Yocto kernels [3] (thanks a lot for this to Bruce Ashfield and Insop Song); even though it is hard to say how many new users we got with this, we can say that having SCHED_DEADLINE in Yocto provides availabily to OSVs like Wind River and others;
- a european project has started (JUNIPER [4]) for which we will provide kernel level support based on this patchset (and we will soon have a real use case for it! yayyy! :)).

The development is taking place at:
https://github.com/jlelli/sched-deadline

branch: sched-dl-V8 (this patchset on top of tip/master).

Check the repositories frequently if you're interested, and feel free to e-mail me for any issue you run into.

Test applications:
https://github.com/gbagnoli/rt-app
https://github.com/jlelli/schedtool-dl

Development mailing list: linux-dl; you can subscribe from here:
http://feanor.sssup.it/mailman/listinfo/linux-dl
or via e-mail (send a message to [email protected] with just the word `help' as subject or in the body to receive info).

The code was being jointly developed by ReTiS Lab (http://retis.sssup.it)
and Evidence S.r.l (http://www.evidence.eu.com) in the context of the ACTORS EU-funded project (http://www.actors-project.eu) and the S(o)OS EU-funded project (http://www.soos-project.eu/). Development is now supported by the JUNIPER EU-funded project [4].

As usual, any kind of feedback is welcome and appreciated.

Thanks in advice and regards,

- Juri

[1] http://lwn.net/Articles/376502, http://lwn.net/Articles/353797,

    http://lwn.net/Articles/412410, http://lwn.net/Articles/490944,
    http://lwn.net/Articles/498472, http://lwn.net/Articles/521091,
    http://lwn.net/Articles/537388

[2] https://www.osadl.org/?id=1743

[3] https://www.yoctoproject.org/

[4] http://www.juniper-project.org/page/overview

Dario Faggioli (9):
sched: add sched_class->task_dead.
sched: add extended scheduling interface.
sched: SCHED_DEADLINE structures & implementation.
sched: SCHED_DEADLINE avg_update accounting.
sched: add schedstats for -deadline tasks.
sched: add latency tracing for -deadline tasks.
sched: drafted deadline inheritance logic.
sched: add bandwidth management for sched_dl.
sched: add sched_dl documentation.

Harald Gustafsson (1):
sched: add period support for -deadline tasks.

Juri Lelli (3):
sched: SCHED_DEADLINE SMP-related data structures & logic.
sched: make dl_bw a sub-quota of rt_bw
sched: speed up -dl pushes with a push-heap.

Peter Zijlstra (1):
rtmutex: turn the plist into an rb-tree.

 Documentation/scheduler/sched-deadline.txt |  196 ++++
 arch/arm/include/asm/unistd.h              |    2 +-
 arch/arm/include/uapi/asm/unistd.h         |    3 +
 arch/arm/kernel/calls.S                    |    3 +
 arch/x86/syscalls/syscall_32.tbl           |    3 +
 arch/x86/syscalls/syscall_64.tbl           |    3 +
 include/linux/init_task.h                  |   10 +
 include/linux/rtmutex.h                    |   18 +-
 include/linux/sched.h                      |  122 +-
 include/linux/sched/deadline.h             |   24 +
 include/linux/sched/rt.h                   |    3 +-
 include/linux/sched/sysctl.h               |   11 +
 include/linux/syscalls.h                   |    7 +
 include/uapi/linux/sched.h                 |    1 +
 kernel/fork.c                              |    8 +-
 kernel/futex.c                             |    2 +
 kernel/hrtimer.c                           |    3 +-
 kernel/rtmutex-debug.c                     |    8 +-
 kernel/rtmutex.c                           |  164 ++-
 kernel/rtmutex_common.h                    |   22 +-
 kernel/sched/Makefile                      |    4 +-
 kernel/sched/core.c                        |  660 ++++++++++-
 kernel/sched/cpudeadline.c                 |  216 ++++
 kernel/sched/cpudeadline.h                 |   33 +
 kernel/sched/deadline.c                    | 1658 ++++++++++++++++++++++++++++
 kernel/sched/debug.c                       |   46 +
 kernel/sched/rt.c                          |    2 +-
 kernel/sched/sched.h                       |  150 +++
 kernel/sched/stop_task.c                   |    2 +-
 kernel/sysctl.c                            |    7 +
 kernel/trace/trace_sched_wakeup.c          |   45 +-
 kernel/trace/trace_selftest.c              |   28 +-
 32 files changed, 3343 insertions(+), 121 deletions(-)
 create mode 100644 Documentation/scheduler/sched-deadline.txt
 create mode 100644 include/linux/sched/deadline.h
 create mode 100644 kernel/sched/cpudeadline.c
 create mode 100644 kernel/sched/cpudeadline.h
 create mode 100644 kernel/sched/deadline.c
Signature · 1 line
1.7.9.5
author
#1 lore raw

PATCH 1/14 sched: add sched_class->task_dead.

From: Dario Faggioli <[email protected]>

Add a new function to the scheduling class interface. It is called at the end of a context switch, if the prev task is in TASK_DEAD state.

It might be useful for the scheduling classes that want to be notified when one of their task dies, e.g. to perform some cleanup actions.

---
 kernel/sched/core.c  |    3 +++
 kernel/sched/sched.h |    1 +
 2 files changed, 4 insertions(+)
kernel/sched/core.c +3 -0
index 5ac63c9..850a02c 100644
@@ -1890,6 +1890,9 @@ static void finish_task_switch(struct rq *rq, struct task_struct *prev)
 	if (mm)
 		mmdrop(mm);
 	if (unlikely(prev_state == TASK_DEAD)) {
+		if (prev->sched_class->task_dead)
+			prev->sched_class->task_dead(prev);
+
 		/*
 		 * Remove function-return probe instances associated with this
 		 * task and put them back on the free list.
kernel/sched/sched.h +1 -0
index b3c5653..64eda5c 100644
@@ -992,6 +992,7 @@ struct sched_class {
 	void (*set_curr_task) (struct rq *rq);
 	void (*task_tick) (struct rq *rq, struct task_struct *p, int queued);
 	void (*task_fork) (struct task_struct *p);
+	void (*task_dead) (struct task_struct *p);
 
 	void (*switched_from) (struct rq *this_rq, struct task_struct *task);
 	void (*switched_to) (struct rq *this_rq, struct task_struct *task);
Signature · 1 line
1.7.9.5
author
#2 lore raw

PATCH 2/14 sched: add extended scheduling interface.

In reply to Juri Lelli

From: Dario Faggioli <[email protected]>

Add the interface bits needed for supporting scheduling algorithms with extended parameters (e.g., SCHED_DEADLINE).

In general, it makes possible to specify a periodic/sporadic task, that executes for a given amount of runtime at each instance, and is scheduled according to the urgency of their own timing constraints, i.e.:
- a (maximum/typical) instance execution time,
- a minimum interval between consecutive instances,
- a time constraint by which each instance must be completed.

Thus, both the data structure that holds the scheduling parameters of the tasks and the system calls dealing with it must be extended. Unfortunately, modifying the existing struct sched_param would break the ABI and result in potentially serious compatibility issues with legacy binaries.

For these reasons, this patch:
- defines the new struct sched_param2, containing all the fields that are necessary for specifying a task in the computational model described above;
- defines and implements the new scheduling related syscalls that manipulate it, i.e., sched_setscheduler2(), sched_setparam2() and sched_getparam2().

Syscalls are introduced for x86 (32 and 64 bits) and ARM only, as a proof of concept and for developing and testing purposes. Making them available on other architectures is straightforward.

Since no "user" for these new parameters is introduced in this patch, the implementation of the new system calls is just identical to their already existing counterpart. Future patches that implement scheduling policies able to exploit the new data structure must also take care of modifying the *2() calls accordingly with their own purposes.

---
 arch/arm/include/asm/unistd.h      |    2 +-
 arch/arm/include/uapi/asm/unistd.h |    3 +
 arch/arm/kernel/calls.S            |    3 +
 arch/x86/syscalls/syscall_32.tbl   |    3 +
 arch/x86/syscalls/syscall_64.tbl   |    3 +
 include/linux/sched.h              |   50 ++++++++++++++++
 include/linux/syscalls.h           |    7 +++
 kernel/sched/core.c                |  110 +++++++++++++++++++++++++++++++++++-
 8 files changed, 177 insertions(+), 4 deletions(-)
arch/arm/include/asm/unistd.h +1 -1
index 141baa3..5f260fd 100644
@@ -15,7 +15,7 @@
 
 #include <uapi/asm/unistd.h>
 
-#define __NR_syscalls  (380)
+#define __NR_syscalls  (383)
 #define __ARM_NR_cmpxchg		(__ARM_NR_BASE+0x00fff0)
 
 #define __ARCH_WANT_STAT64
arch/arm/include/uapi/asm/unistd.h +3 -0
index af33b44..6a4985e 100644
@@ -406,6 +406,9 @@
 #define __NR_process_vm_writev		(__NR_SYSCALL_BASE+377)
 #define __NR_kcmp			(__NR_SYSCALL_BASE+378)
 #define __NR_finit_module		(__NR_SYSCALL_BASE+379)
+#define __NR_sched_setscheduler2	(__NR_SYSCALL_BASE+380)
+#define __NR_sched_setparam2		(__NR_SYSCALL_BASE+381)
+#define __NR_sched_getparam2		(__NR_SYSCALL_BASE+382)
 
 /*
  * This may need to be greater than __NR_last_syscall+1 in order to
arch/arm/kernel/calls.S +3 -0
index c6ca7e3..0fb1ef7 100644
@@ -389,6 +389,9 @@
 		CALL(sys_process_vm_writev)
 		CALL(sys_kcmp)
 		CALL(sys_finit_module)
+/* 380 */	CALL(sys_sched_setscheduler2)
+		CALL(sys_sched_setparam2)
+		CALL(sys_sched_getparam2)
 #ifndef syscalls_counted
 .equ syscalls_padding, ((NR_syscalls + 3) & ~3) - NR_syscalls
 #define syscalls_counted
arch/x86/syscalls/syscall_32.tbl +3 -0
index aabfb83..dfce815 100644
@@ -357,3 +357,6 @@
 348	i386	process_vm_writev	sys_process_vm_writev		compat_sys_process_vm_writev
 349	i386	kcmp			sys_kcmp
 350	i386	finit_module		sys_finit_module
+351	i386	sched_setparam2		sys_sched_setparam2
+352	i386	sched_getparam2		sys_sched_getparam2
+353	i386	sched_setscheduler2	sys_sched_setscheduler2
arch/x86/syscalls/syscall_64.tbl +3 -0
index 38ae65d..1849a70 100644
@@ -320,6 +320,9 @@
 311	64	process_vm_writev	sys_process_vm_writev
 312	common	kcmp			sys_kcmp
 313	common	finit_module		sys_finit_module
+314	common	sched_setparam2		sys_sched_setparam2
+315	common	sched_getparam2		sys_sched_getparam2
+316	common	sched_setscheduler2	sys_sched_setscheduler2
 
 #
 # x32-specific system call numbers start at 512 to avoid cache impact
include/linux/sched.h +50 -0

62 lines not on this page · raw message

include/linux/syscalls.h +7 -0
index 7fac04e..170ac59 100644
@@ -38,6 +38,7 @@ struct rlimit;
 struct rlimit64;
 struct rusage;
 struct sched_param;
+struct sched_param2;
 struct sel_arg_struct;
 struct semaphore;
 struct sembuf;
@@ -277,11 +278,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_setscheduler2(pid_t pid, int policy,
+					struct sched_param2 __user *param);
 asmlinkage long sys_sched_setparam(pid_t pid,
 					struct sched_param __user *param);
+asmlinkage long sys_sched_setparam2(pid_t pid,
+					struct sched_param2 __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_getparam2(pid_t pid,
+					struct sched_param2 __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/core.c +107 -3

155 lines not on this page · raw message

Signature · 1 line
1.7.9.5
author
#3 lore raw

PATCH 3/14 sched: SCHED_DEADLINE structures & implementation.

In reply to Juri Lelli

From: Dario Faggioli <[email protected]>

Introduces the data structures, constants and symbols needed for SCHED_DEADLINE implementation.

Core data structure of SCHED_DEADLINE are defined, along with their initializers. Hooks for checking if a task belong to the new policy are also added where they are needed.

Adds a scheduling class, in sched/dl.c and a new policy called SCHED_DEADLINE. It is an implementation of the Earliest Deadline First (EDF) scheduling algorithm, augmented with a mechanism (called Constant Bandwidth Server, CBS) that makes it possible to isolate the behaviour of tasks between each other.

The typical -deadline task will be made up of a computation phase (instance) which is activated on a periodic or sporadic fashion. The expected (maximum) duration of such computation is called the task's runtime; the time interval by which each instance need to be completed is called the task's relative deadline. The task's absolute deadline is dynamically calculated as the time instant a task (better, an instance) activates plus the relative deadline.

The EDF algorithms selects the task with the smallest absolute deadline as the one to be executed first, while the CBS ensures each task to run for at most its runtime every (relative) deadline length time interval, avoiding any interference between different tasks (bandwidth isolation).
Thanks to this feature, also tasks that do not strictly comply with the computational model sketched above can effectively use the new policy.

To summarize, this patch:
- introduces the data structures, constants and symbols needed;
- implements the core logic of the scheduling algorithm in the new scheduling class file;
- provides all the glue code between the new scheduling class and the core scheduler and refines the interactions between sched/dl and the other existing scheduling classes.

---
 arch/arm/include/asm/unistd.h  |    2 +-
 include/linux/sched.h          |   47 ++-
 include/linux/sched/deadline.h |   24 ++
 include/linux/sched/rt.h       |    2 +-
 include/uapi/linux/sched.h     |    1 +
 kernel/fork.c                  |    4 +-
 kernel/hrtimer.c               |    3 +-
 kernel/sched/Makefile          |    2 +-
 kernel/sched/core.c            |  111 ++++++-
 kernel/sched/deadline.c        |  692 ++++++++++++++++++++++++++++++++++++++++
 kernel/sched/sched.h           |   28 ++
 kernel/sched/stop_task.c       |    2 +-
 12 files changed, 895 insertions(+), 23 deletions(-)
 create mode 100644 include/linux/sched/deadline.h
 create mode 100644 kernel/sched/deadline.c
arch/arm/include/asm/unistd.h +1 -1
index 5f260fd..acabef1 100644
@@ -15,7 +15,7 @@
 
 #include <uapi/asm/unistd.h>
 
-#define __NR_syscalls  (383)
+#define __NR_syscalls  (384)
 #define __ARM_NR_cmpxchg		(__ARM_NR_BASE+0x00fff0)
 
 #define __ARCH_WANT_STAT64
include/linux/sched.h +46 -1

71 lines not on this page · raw message

include/linux/sched/deadline.h new file +24 -0
new file mode 100644
index 0000000..9d303b8
@@ -0,0 +1,24 @@
+#ifndef _SCHED_DEADLINE_H
+#define _SCHED_DEADLINE_H
+
+/*
+ * SCHED_DEADLINE tasks has negative priorities, reflecting
+ * the fact that any of them has higher prio than RT and
+ * NORMAL/BATCH tasks.
+ */
+
+#define MAX_DL_PRIO		0
+
+static inline int dl_prio(int prio)
+{
+	if (unlikely(prio < MAX_DL_PRIO))
+		return 1;
+	return 0;
+}
+
+static inline int dl_task(struct task_struct *p)
+{
+	return dl_prio(p->prio);
+}
+
+#endif /* _SCHED_DEADLINE_H */
include/linux/sched/rt.h +1 -1
index 440434d..a157797 100644
@@ -22,7 +22,7 @@
 
 static inline int rt_prio(int prio)
 {
-	if (unlikely(prio < MAX_RT_PRIO))
+	if ((unsigned)prio < MAX_RT_PRIO)
 		return 1;
 	return 0;
 }
include/uapi/linux/sched.h +1 -0
index 5a0f945..2d5e49a 100644
@@ -39,6 +39,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
 
kernel/fork.c +3 -1
index 086fe73..55fc95f 100644
@@ -1313,7 +1313,9 @@ static struct task_struct *copy_process(unsigned long clone_flags,
 #endif
 
 	/* Perform scheduler related setup. Assign this task to a CPU. */
-	sched_fork(p);
+	retval = sched_fork(p);
+	if (retval)
+		goto bad_fork_cleanup_policy;
 
 	retval = perf_event_init_task(p);
 	if (retval)
kernel/hrtimer.c +2 -1
index 383319b..0909436 100644
@@ -46,6 +46,7 @@
 #include <linux/sched.h>
 #include <linux/sched/sysctl.h>
 #include <linux/sched/rt.h>
+#include <linux/sched/deadline.h>
 #include <linux/timer.h>
 #include <linux/freezer.h>
 
@@ -1610,7 +1611,7 @@ long hrtimer_nanosleep(struct timespec *rqtp, struct timespec __user *rmtp,
 	unsigned long slack;
 
 	slack = current->timer_slack_ns;
-	if (rt_task(current))
+	if (dl_task(current) || rt_task(current))
 		slack = 0;
 
 	hrtimer_init_on_stack(&t.timer, clockid, mode);
kernel/sched/Makefile +1 -1
index 54adcf3..d77282f 100644
@@ -11,7 +11,7 @@ ifneq ($(CONFIG_SCHED_OMIT_FRAME_POINTER),y)
 CFLAGS_core.o := $(PROFILING) -fno-omit-frame-pointer
 endif
 
-obj-y += core.o proc.o clock.o cputime.o idle_task.o fair.o rt.o stop_task.o
+obj-y += core.o proc.o clock.o cputime.o idle_task.o fair.o rt.o deadline.o stop_task.o
 obj-$(CONFIG_SMP) += cpupri.o
 obj-$(CONFIG_SCHED_AUTOGROUP) += auto_group.o
 obj-$(CONFIG_SCHEDSTATS) += stats.o
kernel/sched/core.c +95 -16

240 lines not on this page · raw message

kernel/sched/deadline.c new file +692 -0

692 lines not on this page · raw message

kernel/sched/sched.h +28 -0
index 64eda5c..ba97476 100644
@@ -2,6 +2,7 @@
 #include <linux/sched.h>
 #include <linux/sched/sysctl.h>
 #include <linux/sched/rt.h>
+#include <linux/sched/deadline.h>
 #include <linux/mutex.h>
 #include <linux/spinlock.h>
 #include <linux/stop_machine.h>
@@ -87,11 +88,23 @@ static inline int rt_policy(int policy)
 	return 0;
 }
 
+static inline int dl_policy(int policy)
+{
+	if (unlikely(policy == SCHED_DEADLINE))
+		return 1;
+	return 0;
+}
+
 static inline int task_has_rt_policy(struct task_struct *p)
 {
 	return rt_policy(p->policy);
 }
 
+static inline int task_has_dl_policy(struct task_struct *p)
+{
+	return dl_policy(p->policy);
+}
+
 /*
  * This is the priority-queue data structure of the RT scheduling class:
  */
@@ -363,6 +376,15 @@ struct rt_rq {
 #endif
 };
 
+/* Deadline class' related fields in a runqueue */
+struct dl_rq {
+	/* runqueue is an rbtree, ordered by deadline */
+	struct rb_root rb_root;
+	struct rb_node *rb_leftmost;
+
+	unsigned long dl_nr_running;
+};
+
 #ifdef CONFIG_SMP
 
 /*
@@ -427,6 +449,7 @@ struct rq {
 
 	struct cfs_rq cfs;
 	struct rt_rq rt;
+	struct dl_rq dl;
 
 #ifdef CONFIG_FAIR_GROUP_SCHED
 	/* list of leaf cfs_rq on this cpu: */
@@ -957,6 +980,7 @@ static const u32 prio_to_wmult[40] = {
 #else
 #define ENQUEUE_WAKING		0
 #endif
+#define ENQUEUE_REPLENISH	8
 
 #define DEQUEUE_SLEEP		1
 
@@ -1012,6 +1036,7 @@ struct sched_class {
    for (class = sched_class_highest; class; class = class->next)
 
 extern const struct sched_class stop_sched_class;
+extern const struct sched_class dl_sched_class;
 extern const struct sched_class rt_sched_class;
 extern const struct sched_class fair_sched_class;
 extern const struct sched_class idle_sched_class;
@@ -1047,6 +1072,8 @@ extern void resched_cpu(int cpu);
 extern struct rt_bandwidth def_rt_bandwidth;
 extern void init_rt_bandwidth(struct rt_bandwidth *rt_b, u64 period, u64 runtime);
 
+extern void init_dl_task_timer(struct sched_dl_entity *dl_se);
+
 extern void update_idle_cpu_load(struct rq *this_rq);
 
 extern void init_task_runnable_average(struct task_struct *p);
@@ -1305,6 +1332,7 @@ extern void print_rt_stats(struct seq_file *m, int cpu);
 
 extern void init_cfs_rq(struct cfs_rq *cfs_rq);
 extern void init_rt_rq(struct rt_rq *rt_rq, struct rq *rq);
+extern void init_dl_rq(struct dl_rq *rt_rq, struct rq *rq);
 
 extern void account_cfs_bandwidth_used(int enabled, int was_enabled);
 
kernel/sched/stop_task.c +1 -1
index e08fbee..a5cef17 100644
@@ -103,7 +103,7 @@ get_rr_interval_stop(struct rq *rq, struct task_struct *task)
  * Simple, special scheduling class for the per-CPU stop tasks:
  */
 const struct sched_class stop_sched_class = {
-	.next			= &rt_sched_class,
+	.next			= &dl_sched_class,
 
 	.enqueue_task		= enqueue_task_stop,
 	.dequeue_task		= dequeue_task_stop,
Signature · 1 line
1.7.9.5
maintainer
#4 lore raw

Re: [PATCH 03/14] sched: SCHED_DEADLINE structures & implementation.

include/linux/sched.h struct sched_rt_entity { · line 1064

Quoted 4 lines · Juri Lelli
include/linux/sched.h +4 -0
+struct sched_dl_entity {
+	struct rb_node	rb_node;
+	int nr_cpus_allowed;
+

Please see:

29baa7478ba4 sched: Move nr_cpus_allowed out of 'struct sched_rt_entity'

author
#5 lore raw

Re: [PATCH 03/14] sched: SCHED_DEADLINE structures & implementation.

Quoted 11 lines · Peter Zijlstra

include/linux/sched.h struct sched_rt_entity { · line 1064

Quoted 4 lines · Juri Lelli
include/linux/sched.h +4 -0
+struct sched_dl_entity {
+	struct rb_node	rb_node;
+	int nr_cpus_allowed;
+

Please see:

29baa7478ba4 sched: Move nr_cpus_allowed out of 'struct sched_rt_entity'

Yes, I already considered and used that. But, it is slipped into next patch :\. I'll bring the change to this patch.

Thanks,

- Juri

maintainer
#6 lore raw

Re: [PATCH 03/14] sched: SCHED_DEADLINE structures & implementation.

Quoted 2 lines · Juri Lelli

Yes, I already considered and used that. But, it is slipped into next patch :\. I'll bring the change to this patch.

Ah yes, the wandering hunks problem. I'm only too familiar with it :-(

maintainer
#7 lore raw

Re: [PATCH 03/14] sched: SCHED_DEADLINE structures & implementation.

In reply to Juri Lelli

kernel/sched/core.c void sched_fork(struct task_struct *p) · line 1706

Quoted 8 lines · Juri Lelli
kernel/sched/core.c +3 -1
@@ -1693,8 +1701,14 @@ void sched_fork(struct task_struct *p)
 		p->sched_reset_on_fork = 0;
 	}
 
-	if (!rt_prio(p->prio))
+	if (dl_prio(p->prio)) {
+		put_cpu();
+		return -EAGAIN;

Is this really the error we want to return on fork()?

EAGAIN to me indicates a spurious error and we should try again later; however as it obvious from the code above; we'll always fail, there's no point in trying again later.

I would think something like EINVAL; even though there are no arguments to fork(); would me a better option.

Then again; I really don't care too much; anybody any preferences?

maintainer
#8 lore raw

Re: [PATCH 03/14] sched: SCHED_DEADLINE structures & implementation.

In reply to Juri Lelli
Quoted 18 lines · Juri Lelli
kernel/sched/deadline.c new file +18 -0
+/*
+ * We are being explicitly informed that a new instance is starting,
+ * and this means that:
+ *  - the absolute deadline of the entity has to be placed at
+ *    current time + relative deadline;
+ *  - the runtime of the entity has to be set to the maximum value.
+ *
+ * The capability of specifying such event is useful whenever a -deadline
+ * entity wants to (try to!) synchronize its behaviour with the scheduler's
+ * one, and to (try to!) reconcile itself with its own scheduling
+ * parameters.
+ */
+static inline void setup_new_dl_entity(struct sched_dl_entity *dl_se)
+{
+	struct dl_rq *dl_rq = dl_rq_of_se(dl_se);
+	struct rq *rq = rq_of_dl_rq(dl_rq);
+
+	WARN_ON(!dl_se->dl_new || dl_se->dl_throttled);

kernel/sched/deadline.c line 90

Quoted 10 lines
kernel/sched/deadline.c new file +10 -0
+
+	/*
+	 * We use the regular wall clock time to set deadlines in the
+	 * future; in fact, we must consider execution overheads (time
+	 * spent on hardirq context, etc.).
+	 */
+	dl_se->deadline = rq->clock + dl_se->dl_deadline;
+	dl_se->runtime = dl_se->dl_runtime;
+	dl_se->dl_new = 0;
+}

78becc270975 sched: Use an accessor to read the rq clock

wants you to use rq_clock(rq) there I think.

author
#9 lore raw

Re: [PATCH 03/14] sched: SCHED_DEADLINE structures & implementation.

Quoted 32 lines · Peter Zijlstra
Quoted 18 lines · Juri Lelli
kernel/sched/deadline.c new file +18 -0
+/*
+ * We are being explicitly informed that a new instance is starting,
+ * and this means that:
+ *  - the absolute deadline of the entity has to be placed at
+ *    current time + relative deadline;
+ *  - the runtime of the entity has to be set to the maximum value.
+ *
+ * The capability of specifying such event is useful whenever a -deadline
+ * entity wants to (try to!) synchronize its behaviour with the scheduler's
+ * one, and to (try to!) reconcile itself with its own scheduling
+ * parameters.
+ */
+static inline void setup_new_dl_entity(struct sched_dl_entity *dl_se)
+{
+	struct dl_rq *dl_rq = dl_rq_of_se(dl_se);
+	struct rq *rq = rq_of_dl_rq(dl_rq);
+
+	WARN_ON(!dl_se->dl_new || dl_se->dl_throttled);

kernel/sched/deadline.c line 90

Quoted 10 lines
kernel/sched/deadline.c new file +10 -0
+
+	/*
+	 * We use the regular wall clock time to set deadlines in the
+	 * future; in fact, we must consider execution overheads (time
+	 * spent on hardirq context, etc.).
+	 */
+	dl_se->deadline = rq->clock + dl_se->dl_deadline;
+	dl_se->runtime = dl_se->dl_runtime;
+	dl_se->dl_new = 0;
+}

78becc270975 sched: Use an accessor to read the rq clock

Quoted 3 lines

wants you to use rq_clock(rq) there I think.

Modified here and below.

Thanks,

- Juri

maintainer
#10 lore raw

Re: [PATCH 03/14] sched: SCHED_DEADLINE structures & implementation.

In reply to Juri Lelli
Quoted 5 lines · Juri Lelli
kernel/sched/deadline.c new file +5 -0
+static void replenish_dl_entity(struct sched_dl_entity *dl_se)
+{
+	struct dl_rq *dl_rq = dl_rq_of_se(dl_se);
+	struct rq *rq = rq_of_dl_rq(dl_rq);
+

kernel/sched/deadline.c line 124

Quoted 10 lines
kernel/sched/deadline.c new file +10 -0
+	/*
+	 * We keep moving the deadline away until we get some
+	 * available runtime for the entity. This ensures correct
+	 * handling of situations where the runtime overrun is
+	 * arbitrary large.
+	 */
+	while (dl_se->runtime <= 0) {
+		dl_se->deadline += dl_se->dl_deadline;
+		dl_se->runtime += dl_se->dl_runtime;
+	}

Are we sure GCC won't be 'smart' and bite us; that is do we need something like:

  asm("" : "+rm" (dl_se->runtime));

in there? See:

0d98bb2656e9 sched: Prevent compiler from optimising the sched_avg_update() loop

author
#11 lore raw

Re: [PATCH 03/14] sched: SCHED_DEADLINE structures & implementation.

Quoted 20 lines · Peter Zijlstra
Quoted 5 lines · Juri Lelli
kernel/sched/deadline.c new file +5 -0
+static void replenish_dl_entity(struct sched_dl_entity *dl_se)
+{
+	struct dl_rq *dl_rq = dl_rq_of_se(dl_se);
+	struct rq *rq = rq_of_dl_rq(dl_rq);
+

kernel/sched/deadline.c line 124

Quoted 10 lines
kernel/sched/deadline.c new file +10 -0
+	/*
+	 * We keep moving the deadline away until we get some
+	 * available runtime for the entity. This ensures correct
+	 * handling of situations where the runtime overrun is
+	 * arbitrary large.
+	 */
+	while (dl_se->runtime <= 0) {
+		dl_se->deadline += dl_se->dl_deadline;
+		dl_se->runtime += dl_se->dl_runtime;
+	}

Are we sure GCC won't be 'smart' and bite us; that is do we need something like:

Quoted 6 lines
  asm("" : "+rm" (dl_se->runtime));

in there? See:

0d98bb2656e9 sched: Prevent compiler from optimising the sched_avg_update() loop

When disassembled everything seems fine, at least for x86 and ARM. Do I add the fake data hazard anyway?

Thanks,

- Juri

maintainer
#12 lore raw

Re: [PATCH 03/14] sched: SCHED_DEADLINE structures & implementation.

Quoted 3 lines · Juri Lelli

When disassembled everything seems fine, at least for x86 and ARM. Do I add the fake data hazard anyway?

nah, lets add it when we find it's needed.

maintainer
#13 lore raw

Re: [PATCH 03/14] sched: SCHED_DEADLINE structures & implementation.

In reply to Juri Lelli
Quoted 5 lines · Juri Lelli
kernel/sched/deadline.c new file +5 -0
+static void update_curr_dl(struct rq *rq)
+{
+	struct task_struct *curr = rq->curr;
+	struct sched_dl_entity *dl_se = &curr->dl;
+	u64 delta_exec;

kernel/sched/deadline.c line 371

Quoted 10 lines
kernel/sched/deadline.c new file +10 -0
+
+	if (!dl_task(curr) || !on_dl_rq(dl_se))
+		return;
+
+	/*
+	 * Consumed budget is computed considering the time as
+	 * observed by schedulable tasks (excluding time spent
+	 * in hardirq context, etc.)
+	 */
+	delta_exec = rq->clock_task - curr->se.exec_start;

Oh, cute.. So we compute deadlines from rq->clock but compute runtime from rq->clock_task.

So won't that give funny results in that clock_task is generally slower than clock; so people get more 'time'.

Maybe there's some illumination on this point further on; I'll continue reading.

author
#14 lore raw

Re: [PATCH 03/14] sched: SCHED_DEADLINE structures & implementation.

Quoted 20 lines · Peter Zijlstra
Quoted 5 lines · Juri Lelli
kernel/sched/deadline.c new file +5 -0
+static void update_curr_dl(struct rq *rq)
+{
+	struct task_struct *curr = rq->curr;
+	struct sched_dl_entity *dl_se = &curr->dl;
+	u64 delta_exec;

kernel/sched/deadline.c line 371

Quoted 10 lines
kernel/sched/deadline.c new file +10 -0
+
+	if (!dl_task(curr) || !on_dl_rq(dl_se))
+		return;
+
+	/*
+	 * Consumed budget is computed considering the time as
+	 * observed by schedulable tasks (excluding time spent
+	 * in hardirq context, etc.)
+	 */
+	delta_exec = rq->clock_task - curr->se.exec_start;

Oh, cute.. So we compute deadlines from rq->clock but compute runtime from rq->clock_task.

Quoted 6 lines

So won't that give funny results in that clock_task is generally slower than clock; so people get more 'time'.

Maybe there's some illumination on this point further on; I'll continue reading.

We discussed on this point in the past...

Quoted 8 lines · Juri Lelli
Quoted 1 line

+ dl_se->deadline = rq->clock + dl_se->dl_deadline;

You might want to use rq->clock_task, this clock excludes times spend in hardirq context and steal-time (when paravirt).

Then again, it might not want to use that.. but its something you might want to consider and make explicit by means of a comment.

Quoted 7 lines · Tommaso Cucinotta
Quoted 7 lines
Quoted 2 lines

The idea is that ->clock_task gives the time as observed by schedulable tasks and excludes other muck.

so clock_task might be better to compute the consumed budget at task deschedule, but for setting deadlines one period ahead in the future guess the regular wall-time rq->clock is the one to be used?

Quoted 5 lines

Yep, that was the idea, unless my recollection has completely gone flaky! :-P

Perhaps adding a comment saying right this thing above, as Peter suggested?

And we kind of agreed on the current use of the different clocks. Do you think we have to reason (test) more about this? Or do we live with that and see if something strange happens? (I actually didn't see anything suspiciuos in my use of the patchset).

Thanks,

- Juri

maintainer
#15 lore raw

Re: [PATCH 03/14] sched: SCHED_DEADLINE structures & implementation.

Quoted 3 lines · Juri Lelli
Quoted 1 line · Peter Zijlstra

On Mon, Oct 14, 2013 at 12:43:35PM +0200, Juri Lelli wrote:

We discussed on this point in the past...

Ah, completely forgot about that; please update the comment that we indeed use different clocks for deadline and runtime and that the full ramifications need further study; but that deadline needs hard walltime and clock_task is more natural for runtime.

author
#16 lore raw

Re: [PATCH 03/14] sched: SCHED_DEADLINE structures & implementation.

Quoted 10 lines · Peter Zijlstra
Quoted 3 lines · Juri Lelli
Quoted 1 line · Peter Zijlstra

On Mon, Oct 14, 2013 at 12:43:35PM +0200, Juri Lelli wrote:

We discussed on this point in the past...

Ah, completely forgot about that; please update the comment that we indeed use different clocks for deadline and runtime and that the full ramifications need further study; but that deadline needs hard walltime and clock_task is more natural for runtime.

Ok, done.

Thanks,

- Juri

maintainer
#17 lore raw

Re: [PATCH 03/14] sched: SCHED_DEADLINE structures & implementation.

In reply to Juri Lelli
Quoted 6 lines · Juri Lelli

+/*
+ * Yield task semantic for -deadline tasks is:
+ *
+ * get off from the CPU until our next instance, with
+ * a new runtime.
+ */

Could you amend that comment with a reason for why this is so? I have vague recollections of a discussion on this subject but can't recall. It seems like a useful thing to have.

author
#18 lore raw

Re: [PATCH 03/14] sched: SCHED_DEADLINE structures & implementation.

Quoted 8 lines · Peter Zijlstra
Quoted 6 lines · Juri Lelli

+/*
+ * Yield task semantic for -deadline tasks is:
+ *
+ * get off from the CPU until our next instance, with
+ * a new runtime.
+ */

Quoted 4 lines

Could you amend that comment with a reason for why this is so? I have vague recollections of a discussion on this subject but can't recall. It seems like a useful thing to have.

I think discussion happened before I started maintaining the patchset, but I'm quite sure this would be helpful for bandwidth reclaiming mechanisms. Basically, if I'm able to report that I didn't use all the budget of my current instance, I could donate that remaining budget to other task instances. Bandwidth reclaiming is another nice thing to have, and we actually have some ideas on how to implement it (TODO list always grows :)).

I'll amend the comment saying that this function is of little use now, but will be helpful in the future.

Thanks,

- Juri

maintainer
#19 lore raw

Re: [PATCH 03/14] sched: SCHED_DEADLINE structures & implementation.

In reply to Juri Lelli

kernel/sched/deadline.c line 664

Quoted 10 lines · Juri Lelli
kernel/sched/deadline.c new file +10 -0
+static void set_cpus_allowed_dl(struct task_struct *p,
+				const struct cpumask *new_mask)
+{
+	int weight = cpumask_weight(new_mask);
+
+	BUG_ON(!dl_task(p));
+
+	cpumask_copy(&p->cpus_allowed, new_mask);
+	p->dl.nr_cpus_allowed = weight;
+}

This seems identical so the default in do_set_cpus_allowed(); can we leave this function out and use the default?

author
#20 lore raw

Re: [PATCH 03/14] sched: SCHED_DEADLINE structures & implementation.

Quoted 15 lines · Peter Zijlstra

kernel/sched/deadline.c line 664

Quoted 10 lines · Juri Lelli
kernel/sched/deadline.c new file +10 -0
+static void set_cpus_allowed_dl(struct task_struct *p,
+				const struct cpumask *new_mask)
+{
+	int weight = cpumask_weight(new_mask);
+
+	BUG_ON(!dl_task(p));
+
+	cpumask_copy(&p->cpus_allowed, new_mask);
+	p->dl.nr_cpus_allowed = weight;
+}

This seems identical so the default in do_set_cpus_allowed(); can we leave this function out and use the default?

Another thing that is changed completely in next patch. Anyway, I removed it from here too.

Thanks,

- Juri

author
#21 lore raw

PATCH 4/14 sched: SCHED_DEADLINE SMP-related data structures & logic.

In reply to Juri Lelli

Introduces data structures relevant for implementing dynamic migration of -deadline tasks and the logic for checking if runqueues are overloaded with -deadline tasks and for choosing where a task should migrate, when it is the case.

Adds also dynamic migrations to SCHED_DEADLINE, so that tasks can be moved among CPUs when necessary. It is also possible to bind a task to a (set of) CPU(s), thus restricting its capability of migrating, or forbidding migrations at all.

The very same approach used in sched_rt is utilised:
- -deadline tasks are kept into CPU-specific runqueues,
- -deadline tasks are migrated among runqueues to achieve the following:
* on an M-CPU system the M earliest deadline ready tasks are always running;
* affinity/cpusets settings of all the -deadline tasks is always respected.

Therefore, this very special form of "load balancing" is done with an active method, i.e., the scheduler pushes or pulls tasks between runqueues when they are woken up and/or (de)scheduled.
IOW, every time a preemption occurs, the descheduled task might be sent to some other CPU (depending on its deadline) to continue executing (push). On the other hand, every time a CPU becomes idle, it might pull the second earliest deadline ready task from some other CPU.

To enforce this, a pull operation is always attempted before taking any scheduling decision (pre_schedule()), as well as a push one after each scheduling decision (post_schedule()). In addition, when a task arrives or wakes up, the best CPU where to resume it is selected taking into account its affinity mask, the system topology, but also its deadline. E.g., from the scheduling point of view, the best CPU where to wake up (and also where to push) a task is the one which is running the task with the latest deadline among the M executing ones.

In order to facilitate these decisions, per-runqueue "caching" of the deadlines of the currently running and of the first ready task is used. Queued but not running tasks are also parked in another rb-tree to speed-up pushes.

---
 include/linux/sched.h   |    2 +-
 kernel/sched/core.c     |   10 +-
 kernel/sched/deadline.c |  943 +++++++++++++++++++++++++++++++++++++++++++++--
 kernel/sched/rt.c       |    2 +-
 kernel/sched/sched.h    |   34 ++
 5 files changed, 960 insertions(+), 31 deletions(-)
include/linux/sched.h +1 -1
index 7370f3e..b071ca2 100644
@@ -1060,7 +1060,6 @@ struct sched_rt_entity {
 
 struct sched_dl_entity {
 	struct rb_node	rb_node;
-	int nr_cpus_allowed;
 
 	/*
 	 * Original scheduling parameters. Copied here from sched_param2
@@ -1175,6 +1174,7 @@ struct task_struct {
 	struct list_head tasks;
 #ifdef CONFIG_SMP
 	struct plist_node pushable_tasks;
+	struct rb_node pushable_dl_tasks;
 #endif
 
 	struct mm_struct *mm, *active_mm;
kernel/sched/core.c +9 -1
index cfe15bfc..aa02240 100644
@@ -1737,6 +1737,7 @@ int sched_fork(struct task_struct *p)
 #endif
 #ifdef CONFIG_SMP
 	plist_node_init(&p->pushable_tasks, MAX_PRIO);
+	RB_CLEAR_NODE(&p->pushable_dl_tasks);
 #endif
 
 	put_cpu();
@@ -4418,6 +4419,7 @@ void do_set_cpus_allowed(struct task_struct *p, const struct cpumask *new_mask)
 
 	cpumask_copy(&p->cpus_allowed, new_mask);
 	p->nr_cpus_allowed = cpumask_weight(new_mask);
+	p->nr_cpus_allowed = cpumask_weight(new_mask);
 }
 
 /*
@@ -5148,6 +5150,7 @@ static void free_rootdomain(struct rcu_head *rcu)
 	struct root_domain *rd = container_of(rcu, struct root_domain, rcu);
 
 	cpupri_cleanup(&rd->cpupri);
+	free_cpumask_var(rd->dlo_mask);
 	free_cpumask_var(rd->rto_mask);
 	free_cpumask_var(rd->online);
 	free_cpumask_var(rd->span);
@@ -5199,8 +5202,10 @@ static int init_rootdomain(struct root_domain *rd)
 		goto out;
 	if (!alloc_cpumask_var(&rd->online, GFP_KERNEL))
 		goto free_span;
-	if (!alloc_cpumask_var(&rd->rto_mask, GFP_KERNEL))
+	if (!alloc_cpumask_var(&rd->dlo_mask, GFP_KERNEL))
 		goto free_online;
+	if (!alloc_cpumask_var(&rd->rto_mask, GFP_KERNEL))
+		goto free_dlo_mask;
 
 	if (cpupri_init(&rd->cpupri) != 0)
 		goto free_rto_mask;
@@ -5208,6 +5213,8 @@ static int init_rootdomain(struct root_domain *rd)
 
 free_rto_mask:
 	free_cpumask_var(rd->rto_mask);
+free_dlo_mask:
+	free_cpumask_var(rd->dlo_mask);
 free_online:
 	free_cpumask_var(rd->online);
 free_span:
@@ -6542,6 +6549,7 @@ void __init sched_init_smp(void)
 	free_cpumask_var(non_isolated_cpus);
 
 	init_sched_rt_class();
+	init_sched_dl_class();
 }
 #else
 void __init sched_init_smp(void)
kernel/sched/deadline.c +915 -28

1,064 lines not on this page · raw message

kernel/sched/rt.c +1 -1
index 01970c8..f7c4881 100644
@@ -1720,7 +1720,7 @@ static void task_woken_rt(struct rq *rq, struct task_struct *p)
 	    !test_tsk_need_resched(rq->curr) &&
 	    has_pushable_tasks(rq) &&
 	    p->nr_cpus_allowed > 1 &&
-	    rt_task(rq->curr) &&
+	    (dl_task(rq->curr) || rt_task(rq->curr)) &&
 	    (rq->curr->nr_cpus_allowed < 2 ||
 	     rq->curr->prio <= p->prio))
 		push_rt_tasks(rq);
kernel/sched/sched.h +34 -0
index ba97476..70d0030 100644
@@ -383,6 +383,31 @@ struct dl_rq {
 	struct rb_node *rb_leftmost;
 
 	unsigned long dl_nr_running;
+
+#ifdef CONFIG_SMP
+	/*
+	 * Deadline values of the currently executing and the
+	 * earliest ready task on this rq. Caching these facilitates
+	 * the decision wether or not a ready but not running task
+	 * should migrate somewhere else.
+	 */
+	struct {
+		u64 curr;
+		u64 next;
+	} earliest_dl;
+
+	unsigned long dl_nr_migratory;
+	unsigned long dl_nr_total;
+	int overloaded;
+
+	/*
+	 * Tasks on this rq that can be pushed away. They are kept in
+	 * an rb-tree, ordered by tasks' deadlines, with caching
+	 * of the leftmost (earliest deadline) element.
+	 */
+	struct rb_root pushable_dl_tasks_root;
+	struct rb_node *pushable_dl_tasks_leftmost;
+#endif
 };
 
 #ifdef CONFIG_SMP
@@ -403,6 +428,13 @@ struct root_domain {
 	cpumask_var_t online;
 
 	/*
+	 * The bit corresponding to a CPU gets set here if such CPU has more
+	 * than one runnable -deadline task (as it is below for RT tasks).
+	 */
+	cpumask_var_t dlo_mask;
+	atomic_t dlo_count;
+
+	/*
 	 * The "RT overload" flag: it gets set if a CPU has more than
 	 * one runnable RT task.
 	 */
@@ -1063,6 +1095,8 @@ static inline void idle_balance(int cpu, struct rq *rq)
 extern void sysrq_sched_debug_show(void);
 extern void sched_init_granularity(void);
 extern void update_max_interval(void);
+
+extern void init_sched_dl_class(void);
 extern void init_sched_rt_class(void);
 extern void init_sched_fair_class(void);
 
Signature · 1 line
1.7.9.5
maintainer
#22 lore raw

Re: [PATCH 04/14] sched: SCHED_DEADLINE SMP-related data structures & logic.

kernel/sched/deadline.c static inline int is_leftmost(struct task_struct *p, struct dl_rq *dl_rq) · line 96

Quoted 13 lines · Juri Lelli
kernel/sched/deadline.c +13 -0
+static inline void dl_set_overload(struct rq *rq)
+{
+	if (!rq->online)
+		return;
+
+	cpumask_set_cpu(rq->cpu, rq->rd->dlo_mask);
+	/*
+	 * Must be visible before the overload count is
+	 * set (as in sched_rt.c).
+	 */
+	wmb();
+	atomic_inc(&rq->rd->dlo_count);
+}

Please, make that smp_wmb() and modify the comment to point to the matching barrier ; I couldn't find one! Which suggests something is amiss.

Ideally we'd have something like smp_wmb__after_set_bit() but alas.

author
#23 lore raw

Re: [PATCH 04/14] sched: SCHED_DEADLINE SMP-related data structures & logic.

Quoted 19 lines · Peter Zijlstra

kernel/sched/deadline.c static inline int is_leftmost(struct task_struct *p, struct dl_rq *dl_rq) · line 96

Quoted 13 lines · Juri Lelli
kernel/sched/deadline.c +13 -0
+static inline void dl_set_overload(struct rq *rq)
+{
+	if (!rq->online)
+		return;
+
+	cpumask_set_cpu(rq->cpu, rq->rd->dlo_mask);
+	/*
+	 * Must be visible before the overload count is
+	 * set (as in sched_rt.c).
+	 */
+	wmb();
+	atomic_inc(&rq->rd->dlo_count);
+}

Please, make that smp_wmb() and modify the comment to point to the matching barrier ; I couldn't find one! Which suggests something is amiss.

Quoted 2 lines

Ideally we'd have something like smp_wmb__after_set_bit() but alas.

The only user of this function is pull_dl_task (that tries to pull only if at least one runqueue of the root_domain is overloaded). Surely makes sense to ensure that changes in the dlo_mask have to be visible before we check if we should look at that mask. Am I right if I say that the matching barrier is constituted by the spin_lock on this_rq acquired by schedule() before calling pre_schedule()?

Same thing in rt_set_overload(), do we need to modify the comment also there?

Thanks,

- Juri

maintainer
#24 lore raw

Re: [PATCH 04/14] sched: SCHED_DEADLINE SMP-related data structures & logic.

Quoted 23 lines · Juri Lelli
Quoted 19 lines · Peter Zijlstra

Review

Quoted 13 lines · Juri Lelli
(quoted diff) +13 -0
+static inline void dl_set_overload(struct rq *rq)
+{
+	if (!rq->online)
+		return;
+
+	cpumask_set_cpu(rq->cpu, rq->rd->dlo_mask);
+	/*
+	 * Must be visible before the overload count is
+	 * set (as in sched_rt.c).
+	 */
+	wmb();
+	atomic_inc(&rq->rd->dlo_count);
+}

Please, make that smp_wmb() and modify the comment to point to the matching barrier ; I couldn't find one! Which suggests something is amiss.

Quoted 2 lines

Ideally we'd have something like smp_wmb__after_set_bit() but alas.

Quoted 8 lines

The only user of this function is pull_dl_task (that tries to pull only if at least one runqueue of the root_domain is overloaded). Surely makes sense to ensure that changes in the dlo_mask have to be visible before we check if we should look at that mask. Am I right if I say that the matching barrier is constituted by the spin_lock on this_rq acquired by schedule() before calling pre_schedule()?

Same thing in rt_set_overload(), do we need to modify the comment also there?

So I haven't looked at the dl code, but for the RT code the below is required.

Without that smp_rmb() in there we could actually miss seeing the rto_mask bit.

---
 kernel/sched/rt.c | 10 +++++++++-
 1 file changed, 9 insertions(+), 1 deletion(-)
kernel/sched/rt.c +9 -1
index e9304cdc26fe..a848f526b941 100644
@@ -246,8 +246,10 @@ static inline void rt_set_overload(struct rq *rq)
 	 * if we should look at the mask. It would be a shame
 	 * if we looked at the mask, but the mask was not
 	 * updated yet.
+	 *
+	 * Matched by the barrier in pull_rt_task().
 	 */
-	wmb();
+	smp_wmb();
 	atomic_inc(&rq->rd->rto_count);
 }
 
@@ -1626,6 +1628,12 @@ static int pull_rt_task(struct rq *this_rq)
 	if (likely(!rt_overloaded(this_rq)))
 		return 0;
 
+	/*
+	 * Match the barrier from rt_set_overloaded; this guarantees that if we
+	 * see overloaded we must also see the rto_mask bit.
+	 */
+	smp_rmb();
+
 	for_each_cpu(cpu, this_rq->rd->rto_mask) {
 		if (this_cpu == cpu)
 			continue;
author
#25 lore raw

Re: [PATCH 04/14] sched: SCHED_DEADLINE SMP-related data structures & logic.

Quoted 31 lines · Peter Zijlstra
Quoted 30 lines · Juri Lelli
Quoted 19 lines · Peter Zijlstra

Review

Quoted 13 lines · Juri Lelli
(quoted diff) +13 -0
+static inline void dl_set_overload(struct rq *rq)
+{
+	if (!rq->online)
+		return;
+
+	cpumask_set_cpu(rq->cpu, rq->rd->dlo_mask);
+	/*
+	 * Must be visible before the overload count is
+	 * set (as in sched_rt.c).
+	 */
+	wmb();
+	atomic_inc(&rq->rd->dlo_count);
+}

Please, make that smp_wmb() and modify the comment to point to the matching barrier ; I couldn't find one! Which suggests something is amiss.

Quoted 2 lines

Ideally we'd have something like smp_wmb__after_set_bit() but alas.

The only user of this function is pull_dl_task (that tries to pull only if at least one runqueue of the root_domain is overloaded). Surely makes sense to ensure that changes in the dlo_mask have to be visible before we check if we should look at that mask. Am I right if I say that the matching barrier is constituted by the spin_lock on this_rq acquired by schedule() before calling pre_schedule()?

Quoted 5 lines
Quoted 1 line

Same thing in rt_set_overload(), do we need to modify the comment also there?

So I haven't looked at the dl code, but for the RT code the below is required.

Same thing for dl code.

Thanks,

- Juri

Quoted 37 lines

Without that smp_rmb() in there we could actually miss seeing the rto_mask bit.

---
 kernel/sched/rt.c | 10 +++++++++-
 1 file changed, 9 insertions(+), 1 deletion(-)
kernel/sched/rt.c +9 -1
index e9304cdc26fe..a848f526b941 100644
@@ -246,8 +246,10 @@ static inline void rt_set_overload(struct rq *rq)
 	 * if we should look at the mask. It would be a shame
 	 * if we looked at the mask, but the mask was not
 	 * updated yet.
+	 *
+	 * Matched by the barrier in pull_rt_task().
 	 */
-	wmb();
+	smp_wmb();
 	atomic_inc(&rq->rd->rto_count);
 }
 
@@ -1626,6 +1628,12 @@ static int pull_rt_task(struct rq *this_rq)
 	if (likely(!rt_overloaded(this_rq)))
 		return 0;
 
+	/*
+	 * Match the barrier from rt_set_overloaded; this guarantees that if we
+	 * see overloaded we must also see the rto_mask bit.
+	 */
+	smp_rmb();
+
 	for_each_cpu(cpu, this_rq->rd->rto_mask) {
 		if (this_cpu == cpu)
 			continue;
#26 lore raw

[tip:sched/core] sched/rt: Add missing rmb()

In reply to Peter Zijlstra
sched/rt: Add missing rmb()
Commit-ID:  7c3f2ab7b844f1a859afbc3d41925e8a0faba5fa
Gitweb:     http://git.kernel.org/tip/7c3f2ab7b844f1a859afbc3d41925e8a0faba5fa
Author:     Peter Zijlstra <[email protected]>
AuthorDate: Tue, 15 Oct 2013 12:35:07 +0200
Committer:  Ingo Molnar <[email protected]>
CommitDate: Wed, 16 Oct 2013 14:22:13 +0200

sched/rt: Add missing rmb()

While discussing the proposed SCHED_DEADLINE patches which in parts mimic the existing FIFO code it was noticed that the wmb in rt_set_overloaded() didn't have a matching barrier.

The only site using rt_overloaded() to test the rto_count is pull_rt_task() and we should issue a matching rmb before then assuming there's an rto_mask bit set.

Without that smp_rmb() in there we could actually miss seeing the rto_mask bit.

Also, change to using smp_[wr]mb(), even though this is SMP only code; memory barriers without smp_ always make me think they're against hardware of some sort.

---
 kernel/sched/rt.c | 10 +++++++++-
 1 file changed, 9 insertions(+), 1 deletion(-)
kernel/sched/rt.c +9 -1
index e9304cd..a848f52 100644
@@ -246,8 +246,10 @@ static inline void rt_set_overload(struct rq *rq)
 	 * if we should look at the mask. It would be a shame
 	 * if we looked at the mask, but the mask was not
 	 * updated yet.
+	 *
+	 * Matched by the barrier in pull_rt_task().
 	 */
-	wmb();
+	smp_wmb();
 	atomic_inc(&rq->rd->rto_count);
 }
 
@@ -1626,6 +1628,12 @@ static int pull_rt_task(struct rq *this_rq)
 	if (likely(!rt_overloaded(this_rq)))
 		return 0;
 
+	/*
+	 * Match the barrier from rt_set_overloaded; this guarantees that if we
+	 * see overloaded we must also see the rto_mask bit.
+	 */
+	smp_rmb();
+
 	for_each_cpu(cpu, this_rq->rd->rto_mask) {
 		if (this_cpu == cpu)
 			continue;
author
#27 lore raw

PATCH 5/14 sched: SCHED_DEADLINE avg_update accounting.

In reply to Juri Lelli

From: Dario Faggioli <[email protected]>

Make the core scheduler and load balancer aware of the load produced by -deadline tasks, by updating the moving average like for sched_rt.

---
 kernel/sched/deadline.c |    2 ++
 1 file changed, 2 insertions(+)
kernel/sched/deadline.c +2 -0
index 223cc3e..d3334fc 100644
@@ -557,6 +557,8 @@ static void update_curr_dl(struct rq *rq)
 	curr->se.exec_start = rq->clock_task;
 	cpuacct_charge(curr, delta_exec);
 
+	sched_rt_avg_update(rq, delta_exec);
+
 	dl_se->runtime -= delta_exec;
 	if (dl_runtime_exceeded(rq, dl_se)) {
 		__dequeue_task_dl(rq, curr, 0);
Signature · 1 line
1.7.9.5
author
#28 lore raw

PATCH 6/14 sched: add period support for -deadline tasks.

In reply to Juri Lelli

From: Harald Gustafsson <[email protected]>

Make it possible to specify a period (different or equal than deadline) for -deadline tasks.

---
 include/linux/sched.h   |    1 +
 kernel/sched/core.c     |   15 ++++++++++++---
 kernel/sched/deadline.c |   10 +++++++---
 3 files changed, 20 insertions(+), 6 deletions(-)
include/linux/sched.h +1 -0
index b071ca2..424f64a 100644
@@ -1068,6 +1068,7 @@ struct sched_dl_entity {
 	 */
 	u64 dl_runtime;		/* maximum runtime for each instance	*/
 	u64 dl_deadline;	/* relative deadline of each instance	*/
+	u64 dl_period;		/* separation of two instances (period) */
 
 	/*
 	 * Actual scheduling parameters. Initialized with the values above,
kernel/sched/core.c +12 -3
index aa02240..2ec8a93 100644
@@ -1617,6 +1617,7 @@ static void __sched_fork(struct task_struct *p)
 	hrtimer_init(&p->dl.dl_timer, CLOCK_MONOTONIC, HRTIMER_MODE_REL);
 	p->dl.dl_runtime = p->dl.runtime = 0;
 	p->dl.dl_deadline = p->dl.deadline = 0;
+	p->dl.dl_period = 0;
 	p->dl.flags = 0;
 
 	INIT_LIST_HEAD(&p->rt.run_list);
@@ -3304,6 +3305,10 @@ __setparam_dl(struct task_struct *p, const struct sched_param2 *param2)
 	init_dl_task_timer(dl_se);
 	dl_se->dl_runtime = param2->sched_runtime;
 	dl_se->dl_deadline = param2->sched_deadline;
+	if (param2->sched_period != 0)
+		dl_se->dl_period = param2->sched_period;
+	else
+		dl_se->dl_period = dl_se->dl_deadline;
 	dl_se->flags = param2->sched_flags;
 	dl_se->dl_throttled = 0;
 	dl_se->dl_new = 1;
@@ -3317,19 +3322,23 @@ __getparam_dl(struct task_struct *p, struct sched_param2 *param2)
 	param2->sched_priority = p->rt_priority;
 	param2->sched_runtime = dl_se->dl_runtime;
 	param2->sched_deadline = dl_se->dl_deadline;
+	param2->sched_period = dl_se->dl_period;
 	param2->sched_flags = dl_se->flags;
 }
 
 /*
  * This function validates the new parameters of a -deadline task.
  * We ask for the deadline not being zero, and greater or equal
- * than the runtime.
+ * than the runtime, as well as the period of being zero or
+ * greater than deadline.
  */
 static bool
 __checkparam_dl(const struct sched_param2 *prm)
 {
-	return prm && (&prm->sched_deadline) != 0 &&
-	       (s64)(&prm->sched_deadline - &prm->sched_runtime) >= 0;
+	return prm && prm->sched_deadline != 0 &&
+	       (prm->sched_period == 0 ||
+		(s64)(prm->sched_period - prm->sched_deadline) >= 0) &&
+	       (s64)(prm->sched_deadline - prm->sched_runtime) >= 0;
 }
 
 /*
kernel/sched/deadline.c +7 -3
index d3334fc..92546f3 100644
@@ -287,7 +287,7 @@ static void replenish_dl_entity(struct sched_dl_entity *dl_se)
 	 * arbitrary large.
 	 */
 	while (dl_se->runtime <= 0) {
-		dl_se->deadline += dl_se->dl_deadline;
+		dl_se->deadline += dl_se->dl_period;
 		dl_se->runtime += dl_se->dl_runtime;
 	}
 
@@ -327,9 +327,13 @@ static void replenish_dl_entity(struct sched_dl_entity *dl_se)
  *
  * This function returns true if:
  *
- *   runtime / (deadline - t) > dl_runtime / dl_deadline ,
+ *   runtime / (deadline - t) > dl_runtime / dl_period ,
  *
  * IOW we can't recycle current parameters.
+ *
+ * Notice that the bandwidth check is done against the period. For
+ * task with deadline equal to period this is the same of using
+ * dl_deadline instead of dl_period in the equation above.
  */
 static bool dl_entity_overflow(struct sched_dl_entity *dl_se, u64 t)
 {
@@ -353,7 +357,7 @@ static bool dl_entity_overflow(struct sched_dl_entity *dl_se, u64 t)
 	 * of anything below microseconds resolution is actually fiction
 	 * (but still we want to give the user that illusion >;).
 	 */
-	left = (dl_se->dl_deadline >> 10) * (dl_se->runtime >> 10);
+	left = (dl_se->dl_period >> 10) * (dl_se->runtime >> 10);
 	right = ((dl_se->deadline - t) >> 10) * (dl_se->dl_runtime >> 10);
 
 	return dl_time_before(right, left);
Signature · 1 line
1.7.9.5
maintainer
#29 lore raw

Re: [PATCH 06/14] sched: add period support for -deadline tasks.

Quoted 4 lines · Juri Lelli

From: Harald Gustafsson <[email protected]>

Make it possible to specify a period (different or equal than deadline) for -deadline tasks.

Could we add a little blurb here as to why we'd want this?

(I think I do, and I certainly know where to find the answer, but its better to have a more complete changelog).

author
#30 lore raw

Re: [PATCH 06/14] sched: add period support for -deadline tasks.

Quoted 11 lines · Peter Zijlstra
Quoted 4 lines · Juri Lelli

From: Harald Gustafsson <[email protected]>

Make it possible to specify a period (different or equal than deadline) for -deadline tasks.

Could we add a little blurb here as to why we'd want this?

(I think I do, and I certainly know where to find the answer, but its better to have a more complete changelog).

Yes, I could amend the commit message in something like this:

Make it possible to specify a period (different or equal than deadline) for -deadline tasks. Relative deadlines (D_i) are used on task arrivals to generate new scheduling (absolute) deadlines as "d = t + D_i", and periods (P_i) to postpone the scheduling deadlines as "d = d + P_i" when the budget is zero. This is in general useful to model (and schedule) tasks that have slow activation rates (long periods), but have to be scheduled soon once activated (short deadlines).

What do you think?

Thanks,

- Juri

maintainer
#31 lore raw

Re: [PATCH 06/14] sched: add period support for -deadline tasks.

Quoted 23 lines · Juri Lelli
Quoted 11 lines · Peter Zijlstra
Quoted 4 lines · Juri Lelli

From: Harald Gustafsson <[email protected]>

Make it possible to specify a period (different or equal than deadline) for -deadline tasks.

Could we add a little blurb here as to why we'd want this?

(I think I do, and I certainly know where to find the answer, but its better to have a more complete changelog).

Yes, I could amend the commit message in something like this:

Make it possible to specify a period (different or equal than deadline) for -deadline tasks. Relative deadlines (D_i) are used on task arrivals to generate new scheduling (absolute) deadlines as "d = t + D_i", and periods (P_i) to postpone the scheduling deadlines as "d = d + P_i" when the budget is zero. This is in general useful to model (and schedule) tasks that have slow activation rates (long periods), but have to be scheduled soon once activated (short deadlines).

Quoted 1 line

What do you think?

Yes that's much better. Thanks!

author
#32 lore raw

PATCH 7/14 sched: add schedstats for -deadline tasks.

In reply to Juri Lelli

From: Dario Faggioli <[email protected]>

Add some typical sched-debug output to dl_rq(s) and some schedstats to -deadline tasks.

---
 include/linux/sched.h   |   13 +++++++++++++
 kernel/sched/deadline.c |   45 +++++++++++++++++++++++++++++++++++++++++++++
 kernel/sched/debug.c    |   46 ++++++++++++++++++++++++++++++++++++++++++++++
 kernel/sched/sched.h    |    9 ++++++++-
 4 files changed, 112 insertions(+), 1 deletion(-)
include/linux/sched.h +13 -0
index 424f64a..c8bfabc 100644
@@ -1058,6 +1058,15 @@ struct sched_rt_entity {
 #endif
 };
 
+#ifdef CONFIG_SCHEDSTATS
+struct sched_stats_dl {
+	u64			last_dmiss;
+	u64			last_rorun;
+	u64			dmiss_max;
+	u64			rorun_max;
+};
+#endif
+
 struct sched_dl_entity {
 	struct rb_node	rb_node;
 
@@ -1097,6 +1106,10 @@ struct sched_dl_entity {
 	 * own bandwidth to be enforced, thus we need one timer per task.
 	 */
 	struct hrtimer dl_timer;
+
+#ifdef CONFIG_SCHEDSTATS
+	struct sched_stats_dl stats;
+#endif
 };
 
 struct rcu_node;
kernel/sched/deadline.c +45 -0

66 lines not on this page · raw message

kernel/sched/debug.c +46 -0

64 lines not on this page · raw message

kernel/sched/sched.h +8 -1
index 70d0030..b04aeed 100644
@@ -384,6 +384,8 @@ struct dl_rq {
 
 	unsigned long dl_nr_running;
 
+	u64 exec_clock;
+
 #ifdef CONFIG_SMP
 	/*
 	 * Deadline values of the currently executing and the
@@ -410,6 +412,11 @@ struct dl_rq {
 #endif
 };
 
+#ifdef CONFIG_SCHED_DEBUG
+struct sched_dl_entity *__pick_dl_last_entity(struct dl_rq *dl_rq);
+void print_dl_stats(struct seq_file *m, int cpu);
+#endif
+
 #ifdef CONFIG_SMP
 
 /*
@@ -1366,7 +1373,7 @@ extern void print_rt_stats(struct seq_file *m, int cpu);
 
 extern void init_cfs_rq(struct cfs_rq *cfs_rq);
 extern void init_rt_rq(struct rt_rq *rt_rq, struct rq *rq);
-extern void init_dl_rq(struct dl_rq *rt_rq, struct rq *rq);
+extern void init_dl_rq(struct dl_rq *dl_rq, struct rq *rq);
 
 extern void account_cfs_bandwidth_used(int enabled, int was_enabled);
 
Signature · 1 line
1.7.9.5
maintainer
#33 lore raw

Re: [PATCH 07/14] sched: add schedstats for -deadline tasks.

Quoted 4 lines · Juri Lelli

From: Dario Faggioli <[email protected]>

Add some typical sched-debug output to dl_rq(s) and some schedstats to -deadline tasks.

Could you perhaps add a bit to the changelog explaining what kind of problems this patch helped (or could help) to find?

author
#34 lore raw

Re: [PATCH 07/14] sched: add schedstats for -deadline tasks.

Quoted 9 lines · Peter Zijlstra
Quoted 4 lines · Juri Lelli

From: Dario Faggioli <[email protected]>

Add some typical sched-debug output to dl_rq(s) and some schedstats to -deadline tasks.

Could you perhaps add a bit to the changelog explaining what kind of problems this patch helped (or could help) to find?

Expanded in this:

Add some typical sched-debug output to dl_rq(s) and some schedstats to -deadline tasks. This helps spotting problems with queue and dequeue operations (incorrect ordering) and gives hints about system status (one can have an idea if the system is overloaded, if tasks are missing their deadlines and the entity of such anomalies).

Thanks,

- Juri

author
#35 lore raw

PATCH 8/14 sched: add latency tracing for -deadline tasks.

In reply to Juri Lelli

From: Dario Faggioli <[email protected]>

It is very likely that systems that wants/needs to use the new SCHED_DEADLINE policy also want to have the scheduling latency of the -deadline tasks under control.

For this reason a new version of the scheduling wakeup latency, called "wakeup_dl", is introduced.

As a consequence of applying this patch there will be three wakeup latency tracer:
* "wakeup", that deals with all tasks in the system;
* "wakeup_rt", that deals with -rt and -deadline tasks only;
* "wakeup_dl", that deals with -deadline tasks only.

---
 kernel/trace/trace_sched_wakeup.c |   44 +++++++++++++++++++++++++++++++++----
 kernel/trace/trace_selftest.c     |   28 +++++++++++++----------
 2 files changed, 57 insertions(+), 15 deletions(-)
kernel/trace/trace_sched_wakeup.c +40 -4
index fee77e1..1457fb1 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_dl;
 
 static arch_spinlock_t wakeup_lock =
 	(arch_spinlock_t)__ARCH_SPIN_LOCK_UNLOCKED;
@@ -472,9 +473,17 @@ probe_wakeup(void *ignore, struct task_struct *p, int success)
 	tracing_record_cmdline(p);
 	tracing_record_cmdline(current);
 
-	if ((wakeup_rt && !rt_task(p)) ||
-			p->prio >= wakeup_prio ||
-			p->prio >= current->prio)
+	/*
+	 * Semantic is like this:
+	 *  - wakeup tracer handles all tasks in the system, independently
+	 *    from their scheduling class;
+	 *  - wakeup_rt tracer handles tasks belonging to sched_dl and
+	 *    sched_rt class;
+	 *  - wakeup_dl handles tasks belonging to sched_dl class only.
+	 */
+	if ((wakeup_dl && !dl_task(p)) ||
+	    (wakeup_rt && !dl_task(p) && !rt_task(p)) ||
+	    (p->prio >= wakeup_prio || p->prio >= current->prio))
 		return;
 
 	pc = preempt_count();
@@ -486,7 +495,7 @@ probe_wakeup(void *ignore, struct task_struct *p, int success)
 	arch_spin_lock(&wakeup_lock);
 
 	/* check for races. */
-	if (!tracer_enabled || p->prio >= wakeup_prio)
+	if (!tracer_enabled || (!dl_task(p) && p->prio >= wakeup_prio))
 		goto out_locked;
 
 	/* reset the trace */
@@ -597,16 +606,25 @@ static int __wakeup_tracer_init(struct trace_array *tr)
 
 static int wakeup_tracer_init(struct trace_array *tr)
 {
+	wakeup_dl = 0;
 	wakeup_rt = 0;
 	return __wakeup_tracer_init(tr);
 }
 
 static int wakeup_rt_tracer_init(struct trace_array *tr)
 {
+	wakeup_dl = 0;
 	wakeup_rt = 1;
 	return __wakeup_tracer_init(tr);
 }
 
+static int wakeup_dl_tracer_init(struct trace_array *tr)
+{
+	wakeup_dl = 1;
+	wakeup_rt = 0;
+	return __wakeup_tracer_init(tr);
+}
+
 static void wakeup_tracer_reset(struct trace_array *tr)
 {
 	int lat_flag = save_flags & TRACE_ITER_LATENCY_FMT;
@@ -674,6 +692,20 @@ static struct tracer wakeup_rt_tracer __read_mostly =
 	.use_max_tr	= true,
 };
 
+static struct tracer wakeup_dl_tracer __read_mostly =
+{
+	.name		= "wakeup_dl",
+	.init		= wakeup_dl_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;
@@ -686,6 +718,10 @@ __init static int init_wakeup_tracer(void)
 	if (ret)
 		return ret;
 
+	ret = register_tracer(&wakeup_dl_tracer);
+	if (ret)
+		return ret;
+
 	return 0;
 }
 core_initcall(init_wakeup_tracer);
kernel/trace/trace_selftest.c +17 -11
index a7329b7..f76f8d6 100644
@@ -1022,11 +1022,17 @@ trace_selftest_startup_nop(struct tracer *trace, struct trace_array *tr)
 #ifdef CONFIG_SCHED_TRACER
 static int trace_wakeup_test_thread(void *data)
 {
-	/* Make this a RT thread, doesn't need to be too high */
-	static const struct sched_param param = { .sched_priority = 5 };
+	/* Make this a -deadline thread */
+	struct sched_param2 paramx = {
+		.sched_priority = 0,
+		.sched_runtime = 100000ULL,
+		.sched_deadline = 10000000ULL,
+		.sched_period = 10000000ULL
+		.sched_flags = 0
+	};
 	struct completion *x = data;
 
-	sched_setscheduler(current, SCHED_FIFO, &param);
+	sched_setscheduler2(current, SCHED_DEADLINE, &paramx);
 
 	/* Make it know we have a new prio */
 	complete(x);
@@ -1040,8 +1046,8 @@ static int trace_wakeup_test_thread(void *data)
 	/* we are awake, now wait to disappear */
 	while (!kthread_should_stop()) {
 		/*
-		 * This is an RT task, do short sleeps to let
-		 * others run.
+		 * This will likely be the system top priority
+		 * task, do short sleeps to let others run.
 		 */
 		msleep(100);
 	}
@@ -1054,21 +1060,21 @@ trace_selftest_startup_wakeup(struct tracer *trace, struct trace_array *tr)
 {
 	unsigned long save_max = tracing_max_latency;
 	struct task_struct *p;
-	struct completion isrt;
+	struct completion is_ready;
 	unsigned long count;
 	int ret;
 
-	init_completion(&isrt);
+	init_completion(&is_ready);
 
-	/* create a high prio thread */
-	p = kthread_run(trace_wakeup_test_thread, &isrt, "ftrace-test");
+	/* create a -deadline thread */
+	p = kthread_run(trace_wakeup_test_thread, &is_ready, "ftrace-test");
 	if (IS_ERR(p)) {
 		printk(KERN_CONT "Failed to create ftrace wakeup test thread ");
 		return -1;
 	}
 
-	/* make sure the thread is running at an RT prio */
-	wait_for_completion(&isrt);
+	/* make sure the thread is running at -deadline policy */
+	wait_for_completion(&is_ready);
 
 	/* start the tracing */
 	ret = tracer_init(trace, tr);
Signature · 1 line
1.7.9.5
author
#36 lore raw

PATCH 9/14 rtmutex: turn the plist into an rb-tree.

In reply to Juri Lelli

From: Peter Zijlstra <[email protected]>

Turn the pi-chains from plist to rb-tree, in the rt_mutex code, and provide a proper comparison function for -deadline and -priority tasks.

This is done mainly because:
- classical prio field of the plist is just an int, which might not be enough for representing a deadline;
- manipulating such a list would become O(nr_deadline_tasks), which might be to much, as the number of -deadline task increases.

Therefore, an rb-tree is used, and tasks are queued in it according to the following logic:
- among two -priority (i.e., SCHED_BATCH/OTHER/RR/FIFO) tasks, the one with the higher (lower, actually!) prio wins;
- among a -priority and a -deadline task, the latter always wins;
- among two -deadline tasks, the one with the earliest deadline wins.

Queueing and dequeueing functions are changed accordingly, for both the list of a task's pi-waiters and the list of tasks blocked on a pi-lock.

---
 include/linux/init_task.h |   10 +++
 include/linux/rtmutex.h   |   18 ++----
 include/linux/sched.h     |    4 +-
 kernel/fork.c             |    3 +-
 kernel/futex.c            |    2 +
 kernel/rtmutex-debug.c    |    8 +--
 kernel/rtmutex.c          |  152 ++++++++++++++++++++++++++++++++++++---------
 kernel/rtmutex_common.h   |   22 +++----
 kernel/sched/core.c       |    4 --
 9 files changed, 157 insertions(+), 66 deletions(-)
include/linux/init_task.h +10 -0
index 5cd0f09..69b97ea 100644
@@ -11,6 +11,7 @@
 #include <linux/user_namespace.h>
 #include <linux/securebits.h>
 #include <linux/seqlock.h>
+#include <linux/rbtree.h>
 #include <net/net_namespace.h>
 #include <linux/sched/rt.h>
 
@@ -154,6 +155,14 @@ extern struct task_group root_task_group;
 
 #define INIT_TASK_COMM "swapper"
 
+#ifdef CONFIG_RT_MUTEXES
+# define INIT_RT_MUTEXES(tsk)						\
+	.pi_waiters = RB_ROOT,						\
+	.pi_waiters_leftmost = NULL,
+#else
+# define INIT_RT_MUTEXES(tsk)
+#endif
+
 /*
  *  INIT_TASK is used to set up the first task table, touch at
  * your own risk!. Base=0, limit=0x1fffff (=2MB)
@@ -221,6 +230,7 @@ extern struct task_group root_task_group;
 	INIT_TRACE_RECURSION						\
 	INIT_TASK_RCU_PREEMPT(tsk)					\
 	INIT_CPUSET_SEQ							\
+	INIT_RT_MUTEXES(tsk)						\
 	INIT_VTIME(tsk)							\
 }
 
include/linux/rtmutex.h +6 -12
index de17134..3aed8d7 100644
@@ -13,7 +13,7 @@
 #define __LINUX_RT_MUTEX_H
 
 #include <linux/linkage.h>
-#include <linux/plist.h>
+#include <linux/rbtree.h>
 #include <linux/spinlock_types.h>
 
 extern int max_lock_depth; /* for sysctl */
@@ -22,12 +22,14 @@ extern int max_lock_depth; /* for sysctl */
  * The rt_mutex structure
  *
  * @wait_lock:	spinlock to protect the structure
- * @wait_list:	pilist head to enqueue waiters in priority order
+ * @waiters:	rbtree root to enqueue waiters in priority order
+ * @waiters_leftmost: top waiter
  * @owner:	the mutex owner
  */
 struct rt_mutex {
 	raw_spinlock_t		wait_lock;
-	struct plist_head	wait_list;
+	struct rb_root          waiters;
+	struct rb_node          *waiters_leftmost;
 	struct task_struct	*owner;
 #ifdef CONFIG_DEBUG_RT_MUTEXES
 	int			save_state;
@@ -66,7 +68,7 @@ struct hrtimer_sleeper;
 
 #define __RT_MUTEX_INITIALIZER(mutexname) \
 	{ .wait_lock = __RAW_SPIN_LOCK_UNLOCKED(mutexname.wait_lock) \
-	, .wait_list = PLIST_HEAD_INIT(mutexname.wait_list) \
+	, .waiters = RB_ROOT \
 	, .owner = NULL \
 	__DEBUG_RT_MUTEX_INITIALIZER(mutexname)}
 
@@ -98,12 +100,4 @@ extern int rt_mutex_trylock(struct rt_mutex *lock);
 
 extern void rt_mutex_unlock(struct rt_mutex *lock);
 
-#ifdef CONFIG_RT_MUTEXES
-# define INIT_RT_MUTEXES(tsk)						\
-	.pi_waiters	= PLIST_HEAD_INIT(tsk.pi_waiters),	\
-	INIT_RT_MUTEX_DEBUG(tsk)
-#else
-# define INIT_RT_MUTEXES(tsk)
-#endif
-
 #endif
include/linux/sched.h +3 -1
index c8bfabc..2fbb50a 100644
@@ -16,6 +16,7 @@ struct sched_param {
 #include <linux/types.h>
 #include <linux/timex.h>
 #include <linux/jiffies.h>
+#include <linux/plist.h>
 #include <linux/rbtree.h>
 #include <linux/thread_info.h>
 #include <linux/cpumask.h>
@@ -1340,7 +1341,8 @@ struct task_struct {
 
 #ifdef CONFIG_RT_MUTEXES
 	/* PI waiters blocked on a rt_mutex held by this task */
-	struct plist_head pi_waiters;
+	struct rb_root pi_waiters;
+	struct rb_node *pi_waiters_leftmost;
 	/* Deadlock detection and priority inheritance handling */
 	struct rt_mutex_waiter *pi_blocked_on;
 #endif
kernel/fork.c +2 -1
index 55fc95f..aa6e18d 100644
@@ -1089,7 +1089,8 @@ static void rt_mutex_init_task(struct task_struct *p)
 {
 	raw_spin_lock_init(&p->pi_lock);
 #ifdef CONFIG_RT_MUTEXES
-	plist_head_init(&p->pi_waiters);
+	p->pi_waiters = RB_ROOT;
+	p->pi_waiters_leftmost = NULL;
 	p->pi_blocked_on = NULL;
 #endif
 }
kernel/futex.c +2 -0
index c3a1a55..ff7141e 100644
@@ -2315,6 +2315,8 @@ static int futex_wait_requeue_pi(u32 __user *uaddr, unsigned int flags,
 	 * code while we sleep on uaddr.
 	 */
 	debug_rt_mutex_init_waiter(&rt_waiter);
+	RB_CLEAR_NODE(&rt_waiter.pi_tree_entry);
+	RB_CLEAR_NODE(&rt_waiter.tree_entry);
 	rt_waiter.task = NULL;
 
 	ret = get_futex_key(uaddr2, flags & FLAGS_SHARED, &key2, VERIFY_WRITE);
kernel/rtmutex-debug.c +2 -6
index 13b243a..49b2ed3 100644
@@ -24,7 +24,7 @@
 #include <linux/kallsyms.h>
 #include <linux/syscalls.h>
 #include <linux/interrupt.h>
-#include <linux/plist.h>
+#include <linux/rbtree.h>
 #include <linux/fs.h>
 #include <linux/debug_locks.h>
 
@@ -57,7 +57,7 @@ static void printk_lock(struct rt_mutex *lock, int print_owner)
 
 void rt_mutex_debug_task_free(struct task_struct *task)
 {
-	DEBUG_LOCKS_WARN_ON(!plist_head_empty(&task->pi_waiters));
+	DEBUG_LOCKS_WARN_ON(!RB_EMPTY_ROOT(&task->pi_waiters));
 	DEBUG_LOCKS_WARN_ON(task->pi_blocked_on);
 }
 
@@ -154,16 +154,12 @@ void debug_rt_mutex_proxy_unlock(struct rt_mutex *lock)
 void debug_rt_mutex_init_waiter(struct rt_mutex_waiter *waiter)
 {
 	memset(waiter, 0x11, sizeof(*waiter));
-	plist_node_init(&waiter->list_entry, MAX_PRIO);
-	plist_node_init(&waiter->pi_list_entry, MAX_PRIO);
 	waiter->deadlock_task_pid = NULL;
 }
 
 void debug_rt_mutex_free_waiter(struct rt_mutex_waiter *waiter)
 {
 	put_pid(waiter->deadlock_task_pid);
-	DEBUG_LOCKS_WARN_ON(!plist_node_empty(&waiter->list_entry));
-	DEBUG_LOCKS_WARN_ON(!plist_node_empty(&waiter->pi_list_entry));
 	memset(waiter, 0x22, sizeof(*waiter));
 }
 
kernel/rtmutex.c +121 -31

269 lines not on this page · raw message

kernel/rtmutex_common.h +11 -11
index 53a66c8..b65442f 100644
@@ -40,13 +40,13 @@ extern void schedule_rt_mutex_test(struct rt_mutex *lock);
  * This is the control structure for tasks blocked on a rt_mutex,
  * which is allocated on the kernel stack on of the blocked task.
  *
- * @list_entry:		pi node to enqueue into the mutex waiters list
- * @pi_list_entry:	pi node to enqueue into the mutex owner waiters list
+ * @tree_entry:		pi node to enqueue into the mutex waiters tree
+ * @pi_tree_entry:	pi node to enqueue into the mutex owner waiters tree
  * @task:		task reference to the blocked task
  */
 struct rt_mutex_waiter {
-	struct plist_node	list_entry;
-	struct plist_node	pi_list_entry;
+	struct rb_node          tree_entry;
+	struct rb_node          pi_tree_entry;
 	struct task_struct	*task;
 	struct rt_mutex		*lock;
 #ifdef CONFIG_DEBUG_RT_MUTEXES
@@ -57,11 +57,11 @@ struct rt_mutex_waiter {
 };
 
 /*
- * Various helpers to access the waiters-plist:
+ * Various helpers to access the waiters-tree:
  */
 static inline int rt_mutex_has_waiters(struct rt_mutex *lock)
 {
-	return !plist_head_empty(&lock->wait_list);
+	return !RB_EMPTY_ROOT(&lock->waiters);
 }
 
 static inline struct rt_mutex_waiter *
@@ -69,8 +69,8 @@ rt_mutex_top_waiter(struct rt_mutex *lock)
 {
 	struct rt_mutex_waiter *w;
 
-	w = plist_first_entry(&lock->wait_list, struct rt_mutex_waiter,
-			       list_entry);
+	w = rb_entry(lock->waiters_leftmost, struct rt_mutex_waiter,
+		     tree_entry);
 	BUG_ON(w->lock != lock);
 
 	return w;
@@ -78,14 +78,14 @@ rt_mutex_top_waiter(struct rt_mutex *lock)
 
 static inline int task_has_pi_waiters(struct task_struct *p)
 {
-	return !plist_head_empty(&p->pi_waiters);
+	return !RB_EMPTY_ROOT(&p->pi_waiters);
 }
 
 static inline struct rt_mutex_waiter *
 task_top_pi_waiter(struct task_struct *p)
 {
-	return plist_first_entry(&p->pi_waiters, struct rt_mutex_waiter,
-				  pi_list_entry);
+	return rb_entry(p->pi_waiters_leftmost, struct rt_mutex_waiter,
+			pi_tree_entry);
 }
 
 /*
kernel/sched/core.c +0 -4
index 2ec8a93..3925282 100644
@@ -6729,10 +6729,6 @@ void __init sched_init(void)
 	INIT_HLIST_HEAD(&init_task.preempt_notifiers);
 #endif
 
-#ifdef CONFIG_RT_MUTEXES
-	plist_head_init(&init_task.pi_waiters);
-#endif
-
 	/*
 	 * The boot idle thread does lazy MMU switching as well:
 	 */
Signature · 1 line
1.7.9.5
author
#37 lore raw

PATCH 10/14 sched: drafted deadline inheritance logic.

In reply to Juri Lelli

From: Dario Faggioli <[email protected]>

Some method to deal with rt-mutexes and make sched_dl interact with the current PI-coded is needed, raising all but trivial issues, that needs (according to us) to be solved with some restructuring of the pi-code (i.e., going toward a proxy execution-ish implementation).

This is under development, in the meanwhile, as a temporary solution, what this commits does is:
- ensure a pi-lock owner with waiters is never throttled down. Instead, when it runs out of runtime, it immediately gets replenished and it's deadline is postponed;
- the scheduling parameters (relative deadline and default runtime) used for that replenishments --during the whole period it holds the pi-lock-- are the ones of the waiting task with earliest deadline.

Acting this way, we provide some kind of boosting to the lock-owner, still by using the existing (actually, slightly modified by the previous commit) pi-architecture.

We would stress the fact that this is only a surely needed, all but clean solution to the problem. In the end it's only a way to re-start discussion within the community. So, as always, comments, ideas, rants, etc.. are welcome! :-)

---
 include/linux/sched.h    |    8 +++-
 include/linux/sched/rt.h |    1 +
 kernel/fork.c            |    1 +
 kernel/rtmutex.c         |   13 ++++++-
 kernel/sched/core.c      |   36 +++++++++++++++---
 kernel/sched/deadline.c  |   91 +++++++++++++++++++++++++++-------------------
 kernel/sched/sched.h     |   14 +++++++
 7 files changed, 117 insertions(+), 47 deletions(-)
include/linux/sched.h +7 -1
index 2fbb50a..17da410 100644
@@ -1099,8 +1099,12 @@ struct sched_dl_entity {
 	 * @dl_new tells if a new instance arrived. If so we must
 	 * start executing it with full runtime and reset its absolute
 	 * deadline;
+	 *
+	 * @dl_boosted tells if we are boosted due to DI. If so we are
+	 * outside bandwidth enforcement mechanism (but only until we
+	 * exit the critical section).
 	 */
-	int dl_throttled, dl_new;
+	int dl_throttled, dl_new, dl_boosted;
 
 	/*
 	 * Bandwidth enforcement timer. Each -deadline task has its
@@ -1345,6 +1349,8 @@ struct task_struct {
 	struct rb_node *pi_waiters_leftmost;
 	/* Deadlock detection and priority inheritance handling */
 	struct rt_mutex_waiter *pi_blocked_on;
+	/* Top pi_waiters task */
+	struct task_struct *pi_top_task;
 #endif
 
 #ifdef CONFIG_DEBUG_MUTEXES
include/linux/sched/rt.h +1 -0
index a157797..1fa88a2c 100644
@@ -35,6 +35,7 @@ static inline int rt_task(struct task_struct *p)
 #ifdef CONFIG_RT_MUTEXES
 extern int rt_mutex_getprio(struct task_struct *p);
 extern void rt_mutex_setprio(struct task_struct *p, int prio);
+extern struct task_struct *rt_mutex_get_top_task(struct task_struct *task);
 extern void rt_mutex_adjust_pi(struct task_struct *p);
 static inline bool tsk_is_pi_blocked(struct task_struct *tsk)
 {
kernel/fork.c +1 -0
index aa6e18d..7247105 100644
@@ -1092,6 +1092,7 @@ static void rt_mutex_init_task(struct task_struct *p)
 	p->pi_waiters = RB_ROOT;
 	p->pi_waiters_leftmost = NULL;
 	p->pi_blocked_on = NULL;
+	p->pi_top_task = NULL;
 #endif
 }
 
kernel/rtmutex.c +11 -2
index 4ea7eaa..cb5f950 100644
@@ -200,6 +200,14 @@ int rt_mutex_getprio(struct task_struct *task)
 		   task->normal_prio);
 }
 
+struct task_struct *rt_mutex_get_top_task(struct task_struct *task)
+{
+	if (likely(!task_has_pi_waiters(task)))
+		return NULL;
+
+	return task_top_pi_waiter(task)->task;
+}
+
 /*
  * Adjust the priority of a task, after its pi_waiters got modified.
  *
@@ -209,7 +217,7 @@ static void __rt_mutex_adjust_prio(struct task_struct *task)
 {
 	int prio = rt_mutex_getprio(task);
 
-	if (task->prio != prio)
+	if (task->prio != prio || dl_prio(prio))
 		rt_mutex_setprio(task, prio);
 }
 
@@ -652,7 +660,8 @@ void rt_mutex_adjust_pi(struct task_struct *task)
 	raw_spin_lock_irqsave(&task->pi_lock, flags);
 
 	waiter = task->pi_blocked_on;
-	if (!waiter || waiter->task->prio == task->prio) {
+	if (!waiter || (waiter->task->prio == task->prio &&
+			!dl_prio(task->prio))) {
 		raw_spin_unlock_irqrestore(&task->pi_lock, flags);
 		return;
 	}
kernel/sched/core.c +30 -6
index 3925282..f9e7906 100644
@@ -951,7 +951,7 @@ static inline void check_class_changed(struct rq *rq, struct task_struct *p,
 		if (prev_class->switched_from)
 			prev_class->switched_from(rq, p);
 		p->sched_class->switched_to(rq, p);
-	} else if (oldprio != p->prio)
+	} else if (oldprio != p->prio || dl_task(p))
 		p->sched_class->prio_changed(rq, p, oldprio);
 }
 
@@ -3042,7 +3042,7 @@ EXPORT_SYMBOL(sleep_on_timeout);
  */
 void rt_mutex_setprio(struct task_struct *p, int prio)
 {
-	int oldprio, on_rq, running;
+	int oldprio, on_rq, running, enqueue_flag = 0;
 	struct rq *rq;
 	const struct sched_class *prev_class;
 
@@ -3069,6 +3069,7 @@ void rt_mutex_setprio(struct task_struct *p, int prio)
 	}
 
 	trace_sched_pi_setprio(p, prio);
+	p->pi_top_task = rt_mutex_get_top_task(p);
 	oldprio = p->prio;
 	prev_class = p->sched_class;
 	on_rq = p->on_rq;
@@ -3078,19 +3079,42 @@ void rt_mutex_setprio(struct task_struct *p, int prio)
 	if (running)
 		p->sched_class->put_prev_task(rq, p);
 
-	if (dl_prio(prio))
+	/*
+	 * Boosting condition are:
+	 * 1. -rt task is running and holds mutex A
+	 *      --> -dl task blocks on mutex A
+	 *
+	 * 2. -dl task is running and holds mutex A
+	 *      --> -dl task blocks on mutex A and could preempt the
+	 *          running task
+	 */
+	if (dl_prio(prio)) {
+		if (!dl_prio(p->normal_prio) || (p->pi_top_task &&
+			dl_entity_preempt(&p->pi_top_task->dl, &p->dl))) {
+			p->dl.dl_boosted = 1;
+			p->dl.dl_throttled = 0;
+			enqueue_flag = ENQUEUE_REPLENISH;
+		} else
+			p->dl.dl_boosted = 0;
 		p->sched_class = &dl_sched_class;
-	else if (rt_prio(prio))
+	} else if (rt_prio(prio)) {
+		if (dl_prio(oldprio))
+			p->dl.dl_boosted = 0;
+		if (oldprio < prio)
+			enqueue_flag = ENQUEUE_HEAD;
 		p->sched_class = &rt_sched_class;
-	else
+	} else {
+		if (dl_prio(oldprio))
+			p->dl.dl_boosted = 0;
 		p->sched_class = &fair_sched_class;
+	}
 
 	p->prio = prio;
 
 	if (running)
 		p->sched_class->set_curr_task(rq);
 	if (on_rq)
-		enqueue_task(rq, p, oldprio < prio ? ENQUEUE_HEAD : 0);
+		enqueue_task(rq, p, enqueue_flag);
 
 	check_class_changed(rq, p, prev_class, oldprio);
 out_unlock:
kernel/sched/deadline.c +53 -38

208 lines not on this page · raw message

kernel/sched/sched.h +14 -0
index b04aeed..4da50db 100644
@@ -105,6 +105,20 @@ static inline int task_has_dl_policy(struct task_struct *p)
 	return dl_policy(p->policy);
 }
 
+static inline int dl_time_before(u64 a, u64 b)
+{
+	return (s64)(a - b) < 0;
+}
+
+/*
+ * Tells if entity @a should preempt entity @b.
+ */
+static inline
+int dl_entity_preempt(struct sched_dl_entity *a, struct sched_dl_entity *b)
+{
+	return dl_time_before(a->deadline, b->deadline);
+}
+
 /*
  * This is the priority-queue data structure of the RT scheduling class:
  */
Signature · 1 line
1.7.9.5
author
#38 lore raw

PATCH 11/14 sched: add bandwidth management for sched_dl.

In reply to Juri Lelli

From: Dario Faggioli <[email protected]>

In order of -deadline scheduling to be effective and useful, it is important that some method of having the allocation of the available CPU bandwidth to tasks and task groups under control.
This is usually called "admission control" and if it is not performed at all, no guarantee can be given on the actual scheduling of the -deadline tasks.

Since when RT-throttling has been introduced each task group have a bandwidth associated to itself, calculated as a certain amount of runtime over a period. Moreover, to make it possible to manipulate such bandwidth, readable/writable controls have been added to both procfs (for system wide settings) and cgroupfs (for per-group settings).
Therefore, the same interface is being used for controlling the bandwidth distrubution to -deadline tasks and task groups, i.e., new controls but with similar names, equivalent meaning and with the same usage paradigm are added.

However, more discussion is needed in order to figure out how we want to manage SCHED_DEADLINE bandwidth at the task group level. Therefore, this patch adds a less sophisticated, but actually very sensible, mechanism to ensure that a certain utilization cap is not overcome per each root_domain (the single rq for !SMP configurations).

Another main difference between deadline bandwidth management and RT-throttling is that -deadline tasks have bandwidth on their own (while -rt ones doesn't!), and thus we don't need an higher level throttling mechanism to enforce the desired bandwidth.

This patch, therefore:
- adds system wide deadline bandwidth management by means of:
* /proc/sys/kernel/sched_dl_runtime_us,
* /proc/sys/kernel/sched_dl_period_us,
that determine (i.e., runtime / period) the total bandwidth available on each CPU of each root_domain for -deadline tasks;
- couples the RT and deadline bandwidth management, i.e., enforces that the sum of how much bandwidth is being devoted to -rt -deadline tasks to stay below 100%.

This means that, for a root_domain comprising M CPUs, -deadline tasks can be created until the sum of their bandwidths stay below:

M * (sched_dl_runtime_us / sched_dl_period_us)

It is also possible to disable this bandwidth management logic, and be thus free of oversubscribing the system up to any arbitrary level.

---
 include/linux/sched.h             |    1 +
 include/linux/sched/sysctl.h      |   13 ++
 kernel/rtmutex.c                  |    1 +
 kernel/sched/core.c               |  431 ++++++++++++++++++++++++++++++++++---
 kernel/sched/deadline.c           |   50 ++++-
 kernel/sched/sched.h              |   74 ++++++-
 kernel/sysctl.c                   |   14 ++
 kernel/trace/trace_sched_wakeup.c |    1 +
 8 files changed, 551 insertions(+), 34 deletions(-)
include/linux/sched.h +1 -0
index 17da410..de29080 100644
@@ -1079,6 +1079,7 @@ struct sched_dl_entity {
 	u64 dl_runtime;		/* maximum runtime for each instance	*/
 	u64 dl_deadline;	/* relative deadline of each instance	*/
 	u64 dl_period;		/* separation of two instances (period) */
+	u64 dl_bw;		/* dl_runtime / dl_deadline		*/
 
 	/*
 	 * Actual scheduling parameters. Initialized with the values above,
include/linux/sched/sysctl.h +13 -0
index bf8086b..33fbf32 100644
@@ -83,6 +83,15 @@ static inline unsigned int get_sysctl_timer_migration(void)
 extern unsigned int sysctl_sched_rt_period;
 extern int sysctl_sched_rt_runtime;
 
+/*
+ *  control SCHED_DEADLINE reservations:
+ *
+ *  /proc/sys/kernel/sched_dl_period_us
+ *  /proc/sys/kernel/sched_dl_runtime_us
+ */
+extern unsigned int sysctl_sched_dl_period;
+extern int sysctl_sched_dl_runtime;
+
 #ifdef CONFIG_CFS_BANDWIDTH
 extern unsigned int sysctl_sched_cfs_bandwidth_slice;
 #endif
@@ -101,4 +110,8 @@ extern int sched_rt_handler(struct ctl_table *table, int write,
 		void __user *buffer, size_t *lenp,
 		loff_t *ppos);
 
+int sched_dl_handler(struct ctl_table *table, int write,
+		void __user *buffer, size_t *lenp,
+		loff_t *ppos);
+
 #endif /* _SCHED_SYSCTL_H */
kernel/rtmutex.c +1 -0
index cb5f950..f7f667e 100644
@@ -14,6 +14,7 @@
 #include <linux/export.h>
 #include <linux/sched.h>
 #include <linux/sched/rt.h>
+#include <linux/sched/deadline.h>
 #include <linux/timer.h>
 
 #include "rtmutex_common.h"
kernel/sched/core.c +406 -25

560 lines not on this page · raw message

kernel/sched/deadline.c +44 -6

98 lines not on this page · raw message

kernel/sched/sched.h +71 -3

131 lines not on this page · raw message

kernel/sysctl.c +14 -0
index b2f06f3..f0cf6d6 100644
@@ -414,6 +414,20 @@ static struct ctl_table kern_table[] = {
 		.mode		= 0644,
 		.proc_handler	= sched_rr_handler,
 	},
+	{
+		.procname	= "sched_dl_period_us",
+		.data		= &sysctl_sched_dl_period,
+		.maxlen		= sizeof(unsigned int),
+		.mode		= 0644,
+		.proc_handler	= sched_dl_handler,
+	},
+	{
+		.procname	= "sched_dl_runtime_us",
+		.data		= &sysctl_sched_dl_runtime,
+		.maxlen		= sizeof(int),
+		.mode		= 0644,
+		.proc_handler	= sched_dl_handler,
+	},
 #ifdef CONFIG_SCHED_AUTOGROUP
 	{
 		.procname	= "sched_autogroup_enabled",
kernel/trace/trace_sched_wakeup.c +1 -0
index 1457fb1..b5a9f02 100644
@@ -16,6 +16,7 @@
 #include <linux/uaccess.h>
 #include <linux/ftrace.h>
 #include <linux/sched/rt.h>
+#include <linux/sched/deadline.h>
 #include <trace/events/sched.h>
 #include "trace.h"
 
Signature · 1 line
1.7.9.5
author
#39 lore raw

PATCH 12/14 sched: make dl_bw a sub-quota of rt_bw

In reply to Juri Lelli

Change real-time bandwidth management as to make dl_bw a sub-quota of rt_bw. This patch leaves rt_bw at its default value and sets dl_bw at 40% of rt_bw. It also remove sched_dl_period_us control knob using sched_rt_period_us as common period for both rt_bw and dl_bw.

Checks are made when the user tries to change dl_bw sub-quota as to not fall below what currently used. Since dl_bw now depends upon rt_bw, similar checks are performed when the users modifies rt_bw and dl_bw is changed accordingly. Setting rt_bw sysctl variable to -1 (actually disabling rt throttling) disables dl_bw checks as well.

---
 include/linux/sched/sysctl.h |    2 -
 kernel/sched/core.c          |  285 ++++++++++++++++++++----------------------
 kernel/sched/deadline.c      |    5 +-
 kernel/sched/sched.h         |   24 ++--
 kernel/sysctl.c              |    7 --
 5 files changed, 147 insertions(+), 176 deletions(-)
include/linux/sched/sysctl.h +0 -2
index 33fbf32..444a257 100644
@@ -86,10 +86,8 @@ extern int sysctl_sched_rt_runtime;
 /*
  *  control SCHED_DEADLINE reservations:
  *
- *  /proc/sys/kernel/sched_dl_period_us
  *  /proc/sys/kernel/sched_dl_runtime_us
  */
-extern unsigned int sysctl_sched_dl_period;
 extern int sysctl_sched_dl_runtime;
 
 #ifdef CONFIG_CFS_BANDWIDTH
kernel/sched/core.c +135 -150

395 lines not on this page · raw message

kernel/sched/deadline.c +2 -3
index 35d7c2d..ca20110 100644
@@ -48,10 +48,9 @@ static inline int is_leftmost(struct task_struct *p, struct dl_rq *dl_rq)
 	return dl_rq->rb_leftmost == &dl_se->rb_node;
 }
 
-void init_dl_bandwidth(struct dl_bandwidth *dl_b, u64 period, u64 runtime)
+void init_dl_bandwidth(struct dl_bandwidth *dl_b, u64 runtime)
 {
 	raw_spin_lock_init(&dl_b->dl_runtime_lock);
-	dl_b->dl_period = period;
 	dl_b->dl_runtime = runtime;
 }
 
@@ -64,7 +63,7 @@ void init_dl_bw(struct dl_bw *dl_b)
 	if (global_dl_runtime() == RUNTIME_INF)
 		dl_b->bw = -1;
 	else
-		dl_b->bw = to_ratio(global_dl_period(), global_dl_runtime());
+		dl_b->bw = to_ratio(global_rt_period(), global_dl_runtime());
 	raw_spin_unlock(&def_dl_bandwidth.dl_runtime_lock);
 	dl_b->total_bw = 0;
 }
kernel/sched/sched.h +10 -14
index 08931a6..bf4acf8 100644
@@ -142,20 +142,20 @@ struct rt_bandwidth {
 	struct hrtimer		rt_period_timer;
 };
 /*
- * To keep the bandwidth of -deadline tasks and groups under control
- * we need some place where:
- *  - store the maximum -deadline bandwidth of the system (the group);
+ * To keep the bandwidth of -deadline tasks under control we need some
+ * place where:
+ *  - store the maximum -deadline bandwidth of the system;
  *  - cache the fraction of that bandwidth that is currently allocated.
  *
  * This is all done in the data structure below. It is similar to the
  * one used for RT-throttling (rt_bandwidth), with the main difference
  * that, since here we are only interested in admission control, we
- * do not decrease any runtime while the group "executes", neither we
+ * do not decrease any runtime while the task "executes", neither we
  * need a timer to replenish it.
  *
  * With respect to SMP, the bandwidth is given on a per-CPU basis,
  * meaning that:
- *  - dl_bw (< 100%) is the bandwidth of the system (group) on each CPU;
+ *  - dl_bw (< 100%) is the bandwidth of the system on each CPU;
  *  - dl_total_bw array contains, in the i-eth element, the currently
  *    allocated bandwidth on the i-eth CPU.
  * Moreover, groups consume bandwidth on each CPU, while tasks only
@@ -168,7 +168,6 @@ struct rt_bandwidth {
 struct dl_bandwidth {
 	raw_spinlock_t dl_runtime_lock;
 	u64 dl_runtime;
-	u64 dl_period;
 };
 
 static inline int dl_bandwidth_enabled(void)
@@ -178,10 +177,12 @@ static inline int dl_bandwidth_enabled(void)
 
 struct dl_bw {
 	raw_spinlock_t lock;
-	u64 bw, total_bw;
+	/* default value */
+	u64 bw;
+	/* allocated */
+	u64 total_bw;
 };
 
-static inline u64 global_dl_period(void);
 static inline u64 global_dl_runtime(void);
 
 extern struct mutex sched_domains_mutex;
@@ -924,11 +925,6 @@ static inline u64 global_rt_runtime(void)
 	return (u64)sysctl_sched_rt_runtime * NSEC_PER_USEC;
 }
 
-static inline u64 global_dl_period(void)
-{
-	return (u64)sysctl_sched_dl_period * NSEC_PER_USEC;
-}
-
 static inline u64 global_dl_runtime(void)
 {
 	if (sysctl_sched_dl_runtime < 0)
@@ -1192,7 +1188,7 @@ extern struct rt_bandwidth def_rt_bandwidth;
 extern void init_rt_bandwidth(struct rt_bandwidth *rt_b, u64 period, u64 runtime);
 
 extern struct dl_bandwidth def_dl_bandwidth;
-extern void init_dl_bandwidth(struct dl_bandwidth *dl_b, u64 period, u64 runtime);
+extern void init_dl_bandwidth(struct dl_bandwidth *dl_b, u64 runtime);
 extern void init_dl_task_timer(struct sched_dl_entity *dl_se);
 
 unsigned long to_ratio(u64 period, u64 runtime);
kernel/sysctl.c +0 -7
index f0cf6d6..8159e7e 100644
@@ -415,13 +415,6 @@ static struct ctl_table kern_table[] = {
 		.proc_handler	= sched_rr_handler,
 	},
 	{
-		.procname	= "sched_dl_period_us",
-		.data		= &sysctl_sched_dl_period,
-		.maxlen		= sizeof(unsigned int),
-		.mode		= 0644,
-		.proc_handler	= sched_dl_handler,
-	},
-	{
 		.procname	= "sched_dl_runtime_us",
 		.data		= &sysctl_sched_dl_runtime,
 		.maxlen		= sizeof(int),
Signature · 1 line
1.7.9.5
#40 lore raw

Re: [PATCH 12/14] sched: make dl_bw a sub-quota of rt_bw

kernel/sched/core.c void sched_move_task(struct task_struct *tsk) · line 7346

Quoted 11 lines · Juri Lelli
kernel/sched/core.c +10 -0
+#ifdef CONFIG_SMP
+		struct dl_bw *dl_b = &cpu_rq(i)->rd->dl_bw;
+#else
+		struct dl_bw *dl_b = &cpu_rq(i)->dl.dl_bw;
+#endif
 
+#ifdef CONFIG_SMP
+		struct dl_bw *dl_b = &cpu_rq(i)->rd->dl_bw;
+#else
+		struct dl_bw *dl_b = &cpu_rq(i)->dl.dl_bw;
+#endif

Btw., this kind of SMP/UP assymetry pattern really sucks. Why not make UP use the SMP data structure, even if it's degenerate?

Thanks,

Ingo

author
#41 lore raw

Re: [PATCH 12/14] sched: make dl_bw a sub-quota of rt_bw

Quoted 9 lines · Ingo Molnar
Quoted 5 lines · Juri Lelli
kernel/sched/core.c +5 -0
+#ifdef CONFIG_SMP
+		struct dl_bw *dl_b = &cpu_rq(i)->rd->dl_bw;
+#else
+		struct dl_bw *dl_b = &cpu_rq(i)->dl.dl_bw;
+#endif
Quoted 9 lines

kernel/sched/core.c void sched_move_task(struct task_struct *tsk) · line 7313

Quoted 5 lines
kernel/sched/core.c +5 -0
+#ifdef CONFIG_SMP
+		struct dl_bw *dl_b = &cpu_rq(i)->rd->dl_bw;
+#else
+		struct dl_bw *dl_b = &cpu_rq(i)->dl.dl_bw;
+#endif

Btw., this kind of SMP/UP assymetry pattern really sucks. Why not make UP use the SMP data structure, even if it's degenerate?

Yes, I don't like it either, but that comes from the fact that it seemed to me that, semantically, bandwidth for -deadline tasks has to be associated to the single runqueue in UP and to the root_domain for SMP. In UP root_domain is compiled out, so I'm not sure to understand what you suggest. I could probably let dl_bw live on runqueues with the assumption that all the runqueues from the same root_domain have the same dl_bw, that represents the dl_bw of the root_domain. But I don't like this replication either :(.

Thanks,

- Juri

maintainer
#42 lore raw

Re: [PATCH 12/14] sched: make dl_bw a sub-quota of rt_bw

Quoted 20 lines · Juri Lelli
Quoted 9 lines · Ingo Molnar
Quoted 5 lines · Juri Lelli
kernel/sched/core.c +5 -0
+#ifdef CONFIG_SMP
+		struct dl_bw *dl_b = &cpu_rq(i)->rd->dl_bw;
+#else
+		struct dl_bw *dl_b = &cpu_rq(i)->dl.dl_bw;
+#endif
Quoted 9 lines

kernel/sched/core.c void sched_move_task(struct task_struct *tsk) · line 7313

Quoted 5 lines
kernel/sched/core.c +5 -0
+#ifdef CONFIG_SMP
+		struct dl_bw *dl_b = &cpu_rq(i)->rd->dl_bw;
+#else
+		struct dl_bw *dl_b = &cpu_rq(i)->dl.dl_bw;
+#endif

Btw., this kind of SMP/UP assymetry pattern really sucks. Why not make UP use the SMP data structure, even if it's degenerate?

Quoted 7 lines

Yes, I don't like it either, but that comes from the fact that it seemed to me that, semantically, bandwidth for -deadline tasks has to be associated to the single runqueue in UP and to the root_domain for SMP. In UP root_domain is compiled out, so I'm not sure to understand what you suggest. I could probably let dl_bw live on runqueues with the assumption that all the runqueues from the same root_domain have the same dl_bw, that represents the dl_bw of the root_domain. But I don't like this replication either :(.

#ifdef CONFIG_SMP

static inline struct dl_bw *dl_bw_of(int i)

{
	return &cpu_rq(i)->rd->dl_bw;
}

#else

static inline struct dl_bw *dl_bw_of(int i)

{
	return &cpu_rq(i)->dl.dl_bw;
}

#endif

?

author
#43 lore raw

Re: [PATCH 12/14] sched: make dl_bw a sub-quota of rt_bw

Quoted 38 lines · Peter Zijlstra
Quoted 20 lines · Juri Lelli
Quoted 9 lines · Ingo Molnar
Quoted 5 lines · Juri Lelli
kernel/sched/core.c +5 -0
+#ifdef CONFIG_SMP
+		struct dl_bw *dl_b = &cpu_rq(i)->rd->dl_bw;
+#else
+		struct dl_bw *dl_b = &cpu_rq(i)->dl.dl_bw;
+#endif
Quoted 9 lines

kernel/sched/core.c void sched_move_task(struct task_struct *tsk) · line 7313

Quoted 5 lines
kernel/sched/core.c +5 -0
+#ifdef CONFIG_SMP
+		struct dl_bw *dl_b = &cpu_rq(i)->rd->dl_bw;
+#else
+		struct dl_bw *dl_b = &cpu_rq(i)->dl.dl_bw;
+#endif

Btw., this kind of SMP/UP assymetry pattern really sucks. Why not make UP use the SMP data structure, even if it's degenerate?

Quoted 7 lines

Yes, I don't like it either, but that comes from the fact that it seemed to me that, semantically, bandwidth for -deadline tasks has to be associated to the single runqueue in UP and to the root_domain for SMP. In UP root_domain is compiled out, so I'm not sure to understand what you suggest. I could probably let dl_bw live on runqueues with the assumption that all the runqueues from the same root_domain have the same dl_bw, that represents the dl_bw of the root_domain. But I don't like this replication either :(.

#ifdef CONFIG_SMP

static inline struct dl_bw *dl_bw_of(int i)

{
	return &cpu_rq(i)->rd->dl_bw;
}

#else

Quoted 9 lines

static inline struct dl_bw *dl_bw_of(int i)

{
	return &cpu_rq(i)->dl.dl_bw;
}

#endif

?

Yes, way better.

Thanks,

- Juri

#44 lore raw

Re: [PATCH 12/14] sched: make dl_bw a sub-quota of rt_bw

In reply to Peter Zijlstra
Quoted 38 lines · Peter Zijlstra
Quoted 20 lines · Juri Lelli
Quoted 9 lines · Ingo Molnar
Quoted 5 lines · Juri Lelli
kernel/sched/core.c +5 -0
+#ifdef CONFIG_SMP
+		struct dl_bw *dl_b = &cpu_rq(i)->rd->dl_bw;
+#else
+		struct dl_bw *dl_b = &cpu_rq(i)->dl.dl_bw;
+#endif
Quoted 9 lines

kernel/sched/core.c void sched_move_task(struct task_struct *tsk) · line 7313

Quoted 5 lines
kernel/sched/core.c +5 -0
+#ifdef CONFIG_SMP
+		struct dl_bw *dl_b = &cpu_rq(i)->rd->dl_bw;
+#else
+		struct dl_bw *dl_b = &cpu_rq(i)->dl.dl_bw;
+#endif

Btw., this kind of SMP/UP assymetry pattern really sucks. Why not make UP use the SMP data structure, even if it's degenerate?

Quoted 7 lines

Yes, I don't like it either, but that comes from the fact that it seemed to me that, semantically, bandwidth for -deadline tasks has to be associated to the single runqueue in UP and to the root_domain for SMP. In UP root_domain is compiled out, so I'm not sure to understand what you suggest. I could probably let dl_bw live on runqueues with the assumption that all the runqueues from the same root_domain have the same dl_bw, that represents the dl_bw of the root_domain. But I don't like this replication either :(.

#ifdef CONFIG_SMP

static inline struct dl_bw *dl_bw_of(int i)

{
	return &cpu_rq(i)->rd->dl_bw;
}

#else

Quoted 8 lines

static inline struct dl_bw *dl_bw_of(int i)

{
	return &cpu_rq(i)->dl.dl_bw;
}

#endif

?

Really, please make it _symmetric_ ...

Single core systems are becoming a historic curiosity, should we should justify every piece of extra complexity we add for them.

So I'd rather see obvious SMP code where the UP case works fine too, and _then_ maybe check a separate patch that adds the UP optimization, with (object size) numbers proving that it's worth it, etc.

Thanks,

Ingo

maintainer
#45 lore raw

Re: [PATCH 12/14] sched: make dl_bw a sub-quota of rt_bw

Quoted 8 lines · Ingo Molnar

Really, please make it _symmetric_ ...

Single core systems are becoming a historic curiosity, should we should justify every piece of extra complexity we add for them.

So I'd rather see obvious SMP code where the UP case works fine too, and _then_ maybe check a separate patch that adds the UP optimization, with (object size) numbers proving that it's worth it, etc.

That's a slightly larger task than it appears; the core scheduler code they rely on with smp doesn't exist on up.

We can do this but we need to do it scheduler wide.

#46 lore raw

Re: [PATCH 12/14] sched: make dl_bw a sub-quota of rt_bw

Quoted 7 lines · Peter Zijlstra
Quoted 6 lines · Ingo Molnar

Really, please make it _symmetric_ ...

Single core systems are becoming a historic curiosity, should we should justify every piece of extra complexity we add for them.

Quoted 8 lines
Quoted 3 lines

So I'd rather see obvious SMP code where the UP case works fine too, and _then_ maybe check a separate patch that adds the UP optimization, with (object size) numbers proving that it's worth it, etc.

That's a slightly larger task than it appears; the core scheduler code they rely on with smp doesn't exist on up.

We can do this but we need to do it scheduler wide.

The scheduler has over 800 #ifdefs or similar preprocessor directives:

comet:~/tip> git grep '^#' kernel/sched/ | grep -v include | wc -l 855

I'd like to see this simplified a bit, _especially_ before we add new complexity ...

Thanks,

Ingo

maintainer
#47 lore raw

Re: [PATCH 12/14] sched: make dl_bw a sub-quota of rt_bw

Quoted 7 lines · Ingo Molnar

The scheduler has over 800 #ifdefs or similar preprocessor directives:

comet:~/tip> git grep '^#' kernel/sched/ | grep -v include | wc -l 855

I'd like to see this simplified a bit, _especially_ before we add new complexity ...

I agree; however I also think its unfair to pile this on Juri. Esp the avenue pushed here, which will increase UP text and (runtime) data sizes, to which I think some people will still object.

There's this entire 'maker' community (aka. internet of things) now using very small Linux devices. Think Raspberry-Pi, Intel Quark (however much I hate Intel for shipping a new 32bit device) etc.

These people are wanting to run Linux on these tiny devices, with tiny memories etc; we shouldn't make their life harder than it already is.

Also; you didn't object about the 29 new #ifdefs currently in tip.

How about we use some of the 'quality' conference time in EDI to do some big code shuffles to get rid of some of them. I'm sure we can reduce the number of ifdeffery by simply merging various similar blocks and maybe write a few extra helper functions.

This is how kernel/sched/ got created in the first place; as a means to keep the fingers busy at a conference ;-)

#48 lore raw

Re: [PATCH 12/14] sched: make dl_bw a sub-quota of rt_bw

Quoted 10 lines · Peter Zijlstra
Quoted 7 lines · Ingo Molnar

The scheduler has over 800 #ifdefs or similar preprocessor directives:

comet:~/tip> git grep '^#' kernel/sched/ | grep -v include | wc -l 855

I'd like to see this simplified a bit, _especially_ before we add new complexity ...

I agree; however I also think its unfair to pile this on Juri.

Well, it's that particular ugly #ifdef that caught my eye.

Quoted 11 lines

[...] Esp the avenue pushed here, which will increase UP text and (runtime) data sizes, to which I think some people will still object.

There's this entire 'maker' community (aka. internet of things) now using very small Linux devices. Think Raspberry-Pi, Intel Quark (however much I hate Intel for shipping a new 32bit device) etc.

These people are wanting to run Linux on these tiny devices, with tiny memories etc; we shouldn't make their life harder than it already is.

Also; you didn't object about the 29 new #ifdefs currently in tip.

It was the straw that broke the camel's back.

Quoted 7 lines

How about we use some of the 'quality' conference time in EDI to do some big code shuffles to get rid of some of them. I'm sure we can reduce the number of ifdeffery by simply merging various similar blocks and maybe write a few extra helper functions.

This is how kernel/sched/ got created in the first place; as a means to keep the fingers busy at a conference ;-)

LOL, agreed, we can try that ;-)

Also, we can certainly merge SCHED_DEADLINE first, as long as there's a hard feature stop afterwards and as long as cleanups will eventually arrive.

Thanks,

Ingo

author
#49 lore raw

PATCH 13/14 sched: speed up -dl pushes with a push-heap.

In reply to Juri Lelli

Data from tests confirmed that the original active load balancing logic didn't scale neither in the number of CPU nor in the number of tasks (as sched_rt does).

Here we provide a global data structure to keep track of deadlines of the running tasks in the system. The structure is composed by a bitmask showing the free CPUs and a max-heap, needed when the system is heavily loaded.

The implementation and concurrent access scheme are kept simple by design. However, our measurements show that we can compete with sched_rt on large multi-CPUs machines [1].

Only the push path is addressed, the extension to use this structure also for pull decisions is straightforward. However, we are currently evaluating different (in order to decrease/avoid contention) data structures to solve possibly both problems. We are also going to re-run tests considering recent changes inside cpupri [2].

[1] http://retis.sssup.it/~jlelli/papers/Ospert11Lelli.pdf
[2] http://www.spinics.net/lists/linux-rt-users/msg06778.html

---
 kernel/sched/Makefile      |    2 +-
 kernel/sched/core.c        |    3 +
 kernel/sched/cpudeadline.c |  216 ++++++++++++++++++++++++++++++++++++++++++++
 kernel/sched/cpudeadline.h |   33 +++++++
 kernel/sched/deadline.c    |   53 +++--------
 kernel/sched/sched.h       |    2 +
 6 files changed, 269 insertions(+), 40 deletions(-)
 create mode 100644 kernel/sched/cpudeadline.c
 create mode 100644 kernel/sched/cpudeadline.h
kernel/sched/Makefile +1 -1
index d77282f..ba43447 100644
@@ -12,7 +12,7 @@ CFLAGS_core.o := $(PROFILING) -fno-omit-frame-pointer
 endif
 
 obj-y += core.o proc.o clock.o cputime.o idle_task.o fair.o rt.o deadline.o stop_task.o
-obj-$(CONFIG_SMP) += cpupri.o
+obj-$(CONFIG_SMP) += cpupri.o cpudeadline.o
 obj-$(CONFIG_SCHED_AUTOGROUP) += auto_group.o
 obj-$(CONFIG_SCHEDSTATS) += stats.o
 obj-$(CONFIG_SCHED_DEBUG) += debug.o
kernel/sched/core.c +3 -0
index ddc1f49..49aa0ff 100644
@@ -5385,6 +5385,7 @@ static void free_rootdomain(struct rcu_head *rcu)
 	struct root_domain *rd = container_of(rcu, struct root_domain, rcu);
 
 	cpupri_cleanup(&rd->cpupri);
+	cpudl_cleanup(&rd->cpudl);
 	free_cpumask_var(rd->dlo_mask);
 	free_cpumask_var(rd->rto_mask);
 	free_cpumask_var(rd->online);
@@ -5443,6 +5444,8 @@ static int init_rootdomain(struct root_domain *rd)
 		goto free_dlo_mask;
 
 	init_dl_bw(&rd->dl_bw);
+	if (cpudl_init(&rd->cpudl) != 0)
+		goto free_dlo_mask;
 
 	if (cpupri_init(&rd->cpupri) != 0)
 		goto free_rto_mask;
kernel/sched/cpudeadline.c new file +216 -0

216 lines not on this page · raw message

kernel/sched/cpudeadline.h new file +33 -0
new file mode 100644
index 0000000..a202789
@@ -0,0 +1,33 @@
+#ifndef _LINUX_CPUDL_H
+#define _LINUX_CPUDL_H
+
+#include <linux/sched.h>
+
+#define IDX_INVALID     -1
+
+struct array_item {
+	u64 dl;
+	int cpu;
+};
+
+struct cpudl {
+	raw_spinlock_t lock;
+	int size;
+	int cpu_to_idx[NR_CPUS];
+	struct array_item elements[NR_CPUS];
+	cpumask_var_t free_cpus;
+};
+
+
+#ifdef CONFIG_SMP
+int cpudl_find(struct cpudl *cp, struct task_struct *p,
+	       struct cpumask *later_mask);
+void cpudl_set(struct cpudl *cp, int cpu, u64 dl, int is_valid);
+int cpudl_init(struct cpudl *cp);
+void cpudl_cleanup(struct cpudl *cp);
+#else
+#define cpudl_set(cp, cpu, dl) do { } while (0)
+#define cpudl_init() do { } while (0)
+#endif /* CONFIG_SMP */
+
+#endif /* _LINUX_CPUDL_H */
kernel/sched/deadline.c +14 -39

119 lines not on this page · raw message

kernel/sched/sched.h +2 -0
index bf4acf8..596e290 100644
@@ -9,6 +9,7 @@
 #include <linux/tick.h>
 
 #include "cpupri.h"
+#include "cpudeadline.h"
 #include "cpuacct.h"
 
 struct rq;
@@ -507,6 +508,7 @@ struct root_domain {
 	cpumask_var_t dlo_mask;
 	atomic_t dlo_count;
 	struct dl_bw dl_bw;
+	struct cpudl cpudl;
 
 	/*
 	 * The "RT overload" flag: it gets set if a CPU has more than
Signature · 1 line
1.7.9.5
author
#50 lore raw

PATCH 14/14 sched: add sched_dl documentation.

In reply to Juri Lelli

From: Dario Faggioli <[email protected]>

Add in Documentation/scheduler/ some hints about the design choices, the usage and the future possible developments of the sched_dl scheduling class and of the SCHED_DEADLINE policy.

---
 Documentation/scheduler/sched-deadline.txt |  196 ++++++++++++++++++++++++++++
 kernel/sched/deadline.c                    |    3 +-
 2 files changed, 198 insertions(+), 1 deletion(-)
 create mode 100644 Documentation/scheduler/sched-deadline.txt
Documentation/scheduler/sched-deadline.txt new file +196 -0
new file mode 100644
index 0000000..4d1ed52
@@ -0,0 +1,196 @@
+			  Deadline Task Scheduling
+			  ------------------------
+
+CONTENTS
+========
+
+0. WARNING
+1. Overview
+2. Task scheduling
+2. The Interface
+3. Bandwidth management
+  3.1 System-wide settings
+  3.2 Task interface
+  3.4 Default behavior
+4. Tasks CPU affinity
+  4.1 SCHED_DEADLINE and cpusets HOWTO
+5. 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 users
+ know what they're doing.
+
+
+1. Overview
+===========
+
+ The SCHED_DEADLINE policy contained inside the sched_dl scheduling class is
+ basically an implementation of the Earliest Deadline First (EDF) scheduling
+ algorithm, augmented with a mechanism (called Constant Bandwidth Server, CBS)
+ that makes it possible to isolate the behavior of tasks between each other.
+
+
+2. Task scheduling
+==================
+
+ The typical -deadline task is composed of a computation phase (instance)
+ which is activated on a periodic or sporadic fashion. The expected (maximum)
+ duration of such computation is called the task's runtime; the time interval
+ by which each instance needs to be completed is called the task's relative
+ deadline. The task's absolute deadline is dynamically calculated as the
+ time instant a task (or, more properly) activates plus the relative
+ deadline.
+
+ The EDF[1] algorithm selects the task with the smallest absolute deadline as
+ the one to be executed first, while the CBS[2,3] ensures that each task runs
+ for at most its runtime every period, avoiding any interference between
+ different tasks (bandwidth isolation).
+ Thanks to this feature, also tasks that do not strictly comply with the
+ computational model described above can effectively use the new policy.
+ IOW, there are no limitations on what kind of task can exploit this new
+ scheduling discipline, even if it must be said that it is particularly
+ suited for periodic or sporadic tasks that need guarantees on their
+ timing behavior, e.g., multimedia, streaming, control applications, etc.
+
+ References:
+  1 - C. L. Liu and J. W. Layland. Scheduling algorithms for multiprogram-
+      ming in a hard-real-time environment. Journal of the Association for
+      Computing Machinery, 20(1), 1973.
+  2 - L. Abeni , G. Buttazzo. Integrating Multimedia Applications in Hard
+      Real-Time Systems. Proceedings of the 19th IEEE Real-time Systems
+      Symposium, 1998. http://retis.sssup.it/~giorgio/paps/1998/rtss98-cbs.pdf
+  3 - L. Abeni. Server Mechanisms for Multimedia Applications. ReTiS Lab
+      Technical Report. http://xoomer.virgilio.it/lucabe72/pubs/tr-98-01.ps
+
+3. Bandwidth management
+=======================
+
+ In order for the -deadline scheduling to be effective and useful, it is
+ important to have some method to keep the allocation of the available CPU
+ bandwidth to the tasks under control.
+ This is usually called "admission control" and if it is not performed at all,
+ no guarantee can be given on the actual scheduling of the -deadline tasks.
+
+ Since when RT-throttling has been introduced each task group has a bandwidth
+ associated, calculated as a certain amount of runtime over a period.
+ Moreover, to make it possible to manipulate such bandwidth, readable/writable
+ controls have been added to both procfs (for system wide settings) and cgroupfs
+ (for per-group settings).
+ Therefore, the same interface is being used for controlling the bandwidth
+ distrubution to -deadline tasks and task groups, i.e., new controls but with
+ similar names, equivalent meaning and with the same usage paradigm are added.
+
+ However, more discussion is needed in order to figure out how we want to manage
+ SCHED_DEADLINE bandwidth at the task group level. Therefore, SCHED_DEADLINE
+ uses (for now) a less sophisticated, but actually very sensible, mechanism to
+ ensure that a certain utilization cap is not overcome per each root_domain.
+
+ Another main difference between deadline bandwidth management and RT-throttling
+ is that -deadline tasks have bandwidth on their own (while -rt ones don't!),
+ and thus we don't need an higher level throttling mechanism to enforce the
+ desired bandwidth.
+
+3.1 System wide settings
+------------------------
+
+ The system wide settings are configured under the /proc virtual file system.
+
+ The control knob that is added to the /proc virtual file system is
+ /proc/sys/kernel/sched_dl_runtime_us. It accepts (if written) and provides (if
+ read) the new runtime for each CPU in each root_domain. The period control knob
+ is instead shared with -rt settings (/proc/sys/kernel/sched_rt_period_us). 
+
+ The CPU bandwidth available to -deadline tasks is actually a sub-quota of
+ the -rt bandwidth. By default 95% of system bandwidth is allocate to -rt tasks;
+ among this, a 40% quota is reserved for -dl tasks. To have the actual quota a
+ simple multiplication is needed: .95 * .40 = .38 (38% of system bandwidth for
+ deadline tasks).
+
+ This means that, for a root_domain comprising M CPUs, -deadline tasks
+ can be created until the sum of their bandwidths stay below:
+
+   M * (sched_dl_runtime_us * rt_bw)
+
+ It is also possible to disable this bandwidth management logic, and
+ be thus free of oversubscribing the system up to any arbitrary level.
+ This is done by writing -1 in /proc/sys/kernel/sched_dl_runtime_us or
+ in /proc/sys/kernel/sched_rt_runtime_us.
+
+
+3.2 Task interface
+------------------
+
+ Specifying a periodic/sporadic task that executes for a given amount of
+ runtime at each instance, and that is scheduled according to the urgency of
+ its own timing constraints needs, in general, a way of declaring:
+  - a (maximum/typical) instance execution time,
+  - a minimum interval between consecutive instances,
+  - a time constraint by which each instance must be completed.
+
+ Therefore:
+  * a new struct sched_param2, containing all the necessary fields is
+    provided;
+  * the new scheduling related syscalls that manipulate it, i.e.,
+    sched_setscheduler2(), sched_setparam2() and sched_getparam2()
+    are implemented.
+
+
+3.3 Default behavior
+---------------------
+
+The default value for SCHED_DEADLINE bandwidth is to have dl_runtime equal to
+40000. Being rt_period equal to 1000000, by default, it means that -deadline
+tasks can use at most 40%, multiplied by the number of CPUs that compose the
+root_domain, for each root_domain.
+
+A -deadline task cannot fork.
+
+4. Tasks CPU affinity
+=====================
+
+-deadline tasks cannot have an affinity mask smaller that the entire
+root_domain they are created on. However, affinities can be specified
+through the cpuset facility (Documentation/cgroups/cpusets.txt).
+
+4.1 SCHED_DEADLINE and cpusets HOWTO
+------------------------------------
+
+An example of a simple configuration (pin a -deadline task to CPU0)
+follows (rt-app is used to create a -deadline task).
+
+mkdir /dev/cpuset
+mount -t cgroup -o cpuset cpuset /dev/cpuset
+cd /dev/cpuset
+mkdir cpu0
+echo 0 > cpu0/cpuset.cpus
+echo 0 > cpu0/cpuset.mems
+echo 1 > cpuset.cpu_exclusive
+echo 0 > cpuset.sched_load_balance
+echo 1 > cpu0/cpuset.cpu_exclusive
+echo 1 > cpu0/cpuset.mem_exclusive
+echo $$ > cpu0/tasks
+rt-app -t 100000:10000:d:0 -D5 (it is now actually superfluous to specify
+task affinity)
+
+5. Future plans
+===============
+
+Still missing:
+
+ - refinements to deadline inheritance, especially regarding the possibility
+   of retaining bandwidth isolation among non-interacting tasks. This is
+   being studied from both theoretical and practical point of views, and
+   hopefully we should be able to produce some demonstrative code soon;
+ - (c)group based bandwidth management, and maybe scheduling;
+ - access control for non-root users (and related security concerns to
+   address), which is the best way to allow unprivileged use of the mechanisms
+   and how to prevent non-root users "cheat" the system?
+
+As already discussed, we are planning also to merge this work with the EDF
+throttling patches [https://lkml.org/lkml/2010/2/23/239] but we still are in
+the preliminary phases of the merge and we really seek feedback that would
+help us decide on the direction it should take.
kernel/sched/deadline.c +2 -1
index 1499381..00b550b 100644
@@ -348,7 +348,8 @@ static void replenish_dl_entity(struct sched_dl_entity *dl_se,
  * disrupting the schedulability of the system. Otherwise, we should
  * refill the runtime and set the deadline a period in the future,
  * because keeping the current (absolute) deadline of the task would
- * result in breaking guarantees promised to other tasks.
+ * result in breaking guarantees promised to other tasks (refer to
+ * Documentation/scheduler/sched-deadline.txt for more informations).
  *
  * This function returns true if:
  *
Signature · 1 line
1.7.9.5
author
#51 lore raw
In reply to Juri Lelli

Ok,

I forgot a space after the last Cc with git send-mail, sorry about that. Here the Cc list is right.

Thanks,

- Juri

Quoted 123 lines · Juri Lelli

Hello everyone,

here we go with a new version of the SCHED_DEADLINE patchset (v8). I know that it has been a while since I released last version [1], but I thought not to spam the mailing list with simple updates. Well... this IS basically an update to 3.12-rc5, but it comes right before the next Kernel Summit and Real Time Linux Workshop and, since I'll be present at both events, it is probably time to fire-up the discussion again.

Moreover, interesting news:

- a better mechanism for coordinating mutually exclusive access to critical sections is coming soon (we wrote a paper about it for RTLWS15 [2]);
- the patchset is now available in the 3.4 and 3.10 Yocto kernels [3] (thanks a lot for this to Bruce Ashfield and Insop Song); even though it is hard to say how many new users we got with this, we can say that having SCHED_DEADLINE in Yocto provides availabily to OSVs like Wind River and others;
- a european project has started (JUNIPER [4]) for which we will provide kernel level support based on this patchset (and we will soon have a real use case for it! yayyy! :)).

The development is taking place at:
https://github.com/jlelli/sched-deadline

branch: sched-dl-V8 (this patchset on top of tip/master).

Check the repositories frequently if you're interested, and feel free to e-mail me for any issue you run into.

Test applications:
https://github.com/gbagnoli/rt-app
https://github.com/jlelli/schedtool-dl

Development mailing list: linux-dl; you can subscribe from here:
http://feanor.sssup.it/mailman/listinfo/linux-dl
or via e-mail (send a message to [email protected] with just the word `help' as subject or in the body to receive info).

The code was being jointly developed by ReTiS Lab (http://retis.sssup.it)
and Evidence S.r.l (http://www.evidence.eu.com) in the context of the ACTORS EU-funded project (http://www.actors-project.eu) and the S(o)OS EU-funded project (http://www.soos-project.eu/). Development is now supported by the JUNIPER EU-funded project [4].

As usual, any kind of feedback is welcome and appreciated.

Thanks in advice and regards,

- Juri

[1] http://lwn.net/Articles/376502, http://lwn.net/Articles/353797,

    http://lwn.net/Articles/412410, http://lwn.net/Articles/490944,
    http://lwn.net/Articles/498472, http://lwn.net/Articles/521091,
    http://lwn.net/Articles/537388

[2] https://www.osadl.org/?id=1743

[3] https://www.yoctoproject.org/

[4] http://www.juniper-project.org/page/overview

Dario Faggioli (9):
sched: add sched_class->task_dead.
sched: add extended scheduling interface.
sched: SCHED_DEADLINE structures & implementation.
sched: SCHED_DEADLINE avg_update accounting.
sched: add schedstats for -deadline tasks.
sched: add latency tracing for -deadline tasks.
sched: drafted deadline inheritance logic.
sched: add bandwidth management for sched_dl.
sched: add sched_dl documentation.

Harald Gustafsson (1):
sched: add period support for -deadline tasks.

Juri Lelli (3):
sched: SCHED_DEADLINE SMP-related data structures & logic.
sched: make dl_bw a sub-quota of rt_bw
sched: speed up -dl pushes with a push-heap.

Peter Zijlstra (1):
rtmutex: turn the plist into an rb-tree.

 Documentation/scheduler/sched-deadline.txt |  196 ++++
 arch/arm/include/asm/unistd.h              |    2 +-
 arch/arm/include/uapi/asm/unistd.h         |    3 +
 arch/arm/kernel/calls.S                    |    3 +
 arch/x86/syscalls/syscall_32.tbl           |    3 +
 arch/x86/syscalls/syscall_64.tbl           |    3 +
 include/linux/init_task.h                  |   10 +
 include/linux/rtmutex.h                    |   18 +-
 include/linux/sched.h                      |  122 +-
 include/linux/sched/deadline.h             |   24 +
 include/linux/sched/rt.h                   |    3 +-
 include/linux/sched/sysctl.h               |   11 +
 include/linux/syscalls.h                   |    7 +
 include/uapi/linux/sched.h                 |    1 +
 kernel/fork.c                              |    8 +-
 kernel/futex.c                             |    2 +
 kernel/hrtimer.c                           |    3 +-
 kernel/rtmutex-debug.c                     |    8 +-
 kernel/rtmutex.c                           |  164 ++-
 kernel/rtmutex_common.h                    |   22 +-
 kernel/sched/Makefile                      |    4 +-
 kernel/sched/core.c                        |  660 ++++++++++-
 kernel/sched/cpudeadline.c                 |  216 ++++
 kernel/sched/cpudeadline.h                 |   33 +
 kernel/sched/deadline.c                    | 1658 ++++++++++++++++++++++++++++
 kernel/sched/debug.c                       |   46 +
 kernel/sched/rt.c                          |    2 +-
 kernel/sched/sched.h                       |  150 +++
 kernel/sched/stop_task.c                   |    2 +-
 kernel/sysctl.c                            |    7 +
 kernel/trace/trace_sched_wakeup.c          |   45 +-
 kernel/trace/trace_selftest.c              |   28 +-
 32 files changed, 3343 insertions(+), 121 deletions(-)
 create mode 100644 Documentation/scheduler/sched-deadline.txt
 create mode 100644 include/linux/sched/deadline.h
 create mode 100644 kernel/sched/cpudeadline.c
 create mode 100644 kernel/sched/cpudeadline.h
 create mode 100644 kernel/sched/deadline.c
maintainer
#52 lore raw
In reply to Juri Lelli
Quoted 8 lines · Juri Lelli

Hello everyone,

here we go with a new version of the SCHED_DEADLINE patchset (v8). I know that it has been a while since I released last version [1], but I thought not to spam the mailing list with simple updates. Well... this IS basically an update to 3.12-rc5, but it comes right before the next Kernel Summit and Real Time Linux Workshop and, since I'll be present at both events, it is probably time to fire-up the discussion again.

So I feel we should just merge this stuff already; the only 'issue' I have is the cgroup abi muck. We clearly need a bit more discussion on what/how we want things there but there are no easy answers :/ So I'd say lets try this and see where we'll find ourselves.

Steve; could you go over the SMP push/pull bits as they're modeled after the stuff you did for FIFO.

#53 lore raw
Quoted 11 lines · Peter Zijlstra
Quoted 8 lines · Juri Lelli

Hello everyone,

here we go with a new version of the SCHED_DEADLINE patchset (v8). I know that it has been a while since I released last version [1], but I thought not to spam the mailing list with simple updates. Well... this IS basically an update to 3.12-rc5, but it comes right before the next Kernel Summit and Real Time Linux Workshop and, since I'll be present at both events, it is probably time to fire-up the discussion again.

So I feel we should just merge this stuff already; [...]

Fully agreed - this has been going on for a long time and the patch-set has settled down nicely.

Quoted 4 lines

[...] the only 'issue' I have is the cgroup abi muck. We clearly need a bit more discussion on what/how we want things there but there are no easy answers :/ So I'd say lets try this and see where we'll find ourselves.

I'd suggest we leave out the cgroup ABI muck from the first round of upstream merge - do it in a second round, that will give it more attention.

Thanks,

Ingo

maintainer
#54 lore raw
Quoted 8 lines · Ingo Molnar
Quoted 4 lines

[...] the only 'issue' I have is the cgroup abi muck. We clearly need a bit more discussion on what/how we want things there but there are no easy answers :/ So I'd say lets try this and see where we'll find ourselves.

I'd suggest we leave out the cgroup ABI muck from the first round of upstream merge - do it in a second round, that will give it more attention.

I'm afraid that'd give rise to some very weird situations for people using cgroups :/

#55 lore raw
Quoted 7 lines · Peter Zijlstra
Quoted 5 lines · Ingo Molnar
Quoted 4 lines

[...] the only 'issue' I have is the cgroup abi muck. We clearly need a bit more discussion on what/how we want things there but there are no easy answers :/ So I'd say lets try this and see where we'll find ourselves.

Quoted 6 lines
Quoted 3 lines

I'd suggest we leave out the cgroup ABI muck from the first round of upstream merge - do it in a second round, that will give it more attention.

I'm afraid that'd give rise to some very weird situations for people using cgroups :/

Why? One solution would be to just not offer bandwidth management initially - but use some sane default.

Yes, this doesn't offer "true" deadline scheduling yet, but would allow us to move most of the code upstream, without any ABI changes initially (other than adding the SCHED_DEADLINE policy and such).

Thanks,

Ingo

maintainer
#56 lore raw
Quoted 17 lines · Ingo Molnar
Quoted 7 lines · Peter Zijlstra
Quoted 5 lines · Ingo Molnar
Quoted 4 lines

[...] the only 'issue' I have is the cgroup abi muck. We clearly need a bit more discussion on what/how we want things there but there are no easy answers :/ So I'd say lets try this and see where we'll find ourselves.

Quoted 6 lines
Quoted 3 lines

I'd suggest we leave out the cgroup ABI muck from the first round of upstream merge - do it in a second round, that will give it more attention.

I'm afraid that'd give rise to some very weird situations for people using cgroups :/

Quoted 6 lines

Why? One solution would be to just not offer bandwidth management initially - but use some sane default.

Yes, this doesn't offer "true" deadline scheduling yet, but would allow us to move most of the code upstream, without any ABI changes initially (other than adding the SCHED_DEADLINE policy and such).

I suppose we could keep the global sysctl thingies but indeed ignore all the cgroup limits for now. That would allow some admission control but leaves out the hairiest part.