Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > linux.kernel > #1659298 > unrolled thread

[PATCH v2 0/8] scheduler tinification

Back to article view | Back to linux.kernel

Contents

  [PATCH v2 0/8] scheduler tinification Nicolas Pitre <nicolas.pitre@linaro.org> - 2017-06-07 01:30 +0200
    [PATCH v2 8/8] sched/rt: make it configurable Nicolas Pitre <nicolas.pitre@linaro.org> - 2017-06-07 01:30 +0200
    [PATCH v2 1/8] cpuset/sched: cpuset makes sense for SMP only Nicolas Pitre <nicolas.pitre@linaro.org> - 2017-06-07 01:50 +0200
    Re: [PATCH v2 0/8] scheduler tinification Ingo Molnar <mingo@kernel.org> - 2017-06-07 18:10 +0200
      Re: [PATCH v2 0/8] scheduler tinification Nicolas Pitre <nicolas.pitre@linaro.org> - 2017-06-07 19:10 +0200
        Re: [PATCH v2 0/8] scheduler tinification Alan Cox <gnomes@lxorguk.ukuu.org.uk> - 2017-06-07 21:00 +0200
          Re: [PATCH v2 0/8] scheduler tinification Nicolas Pitre <nicolas.pitre@linaro.org> - 2017-06-07 23:20 +0200
            Re: [PATCH v2 0/8] scheduler tinification Alan Cox <gnomes@lxorguk.ukuu.org.uk> - 2017-06-08 00:00 +0200
        Re: [PATCH v2 0/8] scheduler tinification Ingo Molnar <mingo@kernel.org> - 2017-06-08 10:00 +0200
          Re: [PATCH v2 0/8] scheduler tinification Alan Cox <gnomes@lxorguk.ukuu.org.uk> - 2017-06-08 20:20 +0200
          Re: [PATCH v2 0/8] scheduler tinification Nicolas Pitre <nicolas.pitre@linaro.org> - 2017-06-08 22:20 +0200
            Re: [PATCH v2 0/8] scheduler tinification Ingo Molnar <mingo@kernel.org> - 2017-06-11 11:30 +0200
              Re: [PATCH v2 0/8] scheduler tinification Nicolas Pitre <nicolas.pitre@linaro.org> - 2017-06-11 17:30 +0200
            Re: [PATCH v2 0/8] scheduler tinification Ingo Molnar <mingo@kernel.org> - 2017-06-11 11:50 +0200
              Re: [PATCH v2 0/8] scheduler tinification Nicolas Pitre <nicolas.pitre@linaro.org> - 2017-06-11 18:50 +0200
                Re: [PATCH v2 0/8] scheduler tinification Ingo Molnar <mingo@kernel.org> - 2017-06-13 09:20 +0200
                  Re: [PATCH v2 0/8] scheduler tinification Nicolas Pitre <nicolas.pitre@linaro.org> - 2017-06-13 14:30 +0200

#1659298 — [PATCH v2 0/8] scheduler tinification

Many embedded systems don't need the full scheduler support. Most of the
time, user space is tightly controlled and many of the scheduler facilities
are simply unused.

This patch series makes it possible to configure out some parts of the
scheduler such as the deadline and realtime scheduler classes. The saving
in kernel footprint is non negligible.

Small ARM kernel config before this series:

   text    data     bss     dec     hex filename
  28623    3404     128   32155    7d9b kernel/sched/built-in.o

With this series and dl and rt classes disabled:

   text    data     bss     dec     hex filename
  20734    3334      40   24108    5e2c kernel/sched/built-in.o

A significant part of the remaining code is support for various system calls
that could be automatically removed when user space doesn't use it but that
is a topic for another day.

Changes from v1:

- the deadline class is configurable independently from the realtime class
- split of the PI futex code to make non-PI futexes available when RT
  is configured out
- removal of many #ifdefs to keep the code more readable

diffstat for this series:

 include/linux/futex.h          |    7 +-
 include/linux/init_task.h      |   15 +-
 include/linux/rtmutex.h        |   69 +
 include/linux/sched.h          |    4 +
 include/linux/sched/deadline.h |    8 +-
 include/linux/sched/rt.h       |   10 +-
 init/Kconfig                   |   28 +-
 kernel/futex.c                 | 2829 ++++++++--------------------------
 kernel/futex_pi.c              | 1563 +++++++++++++++++++
 kernel/locking/Makefile        |    3 +
 kernel/locking/locktorture.c   |    4 +-
 kernel/locking/rtmutex.c       |    6 +-
 kernel/sched/Makefile          |    7 +-
 kernel/sched/core.c            |  759 +--------
 kernel/sched/cpudeadline.h     |    7 +-
 kernel/sched/deadline.c        |  340 ++++
 kernel/sched/debug.c           |    6 +
 kernel/sched/rt.c              |  315 +++-
 kernel/sched/sched.h           |   88 +-
 kernel/sched/stop_task.c       |    6 +
 kernel/sysctl.c                |    4 +-
 kernel/time/posix-cpu-timers.c |    7 +-
 lib/Kconfig.debug              |    2 +-
 23 files changed, 3190 insertions(+), 2897 deletions(-)

[toc] | [next] | [standalone]

#1659299 — [PATCH v2 8/8] sched/rt: make it configurable

On most small systems where user space is tightly controlled, the realtime
scheduling class can often be dispensed with to reduce the kernel footprint.
Let's make it configurable.

The code that makes explicit assumptions about actual RT mutexes (i.e
where the compatibility wrappers don't make sense) has to be made conditional on CONFIG_SCHED_RT. This is
also done here.

Signed-off-by: Nicolas Pitre <nico@linaro.org>
---
 include/linux/init_task.h      | 15 +++++++++++----
 include/linux/rtmutex.h        |  2 +-
 include/linux/sched.h          |  2 ++
 include/linux/sched/rt.h       | 10 ++++++++--
 init/Kconfig                   | 14 +++++++++++---
 kernel/locking/Makefile        |  3 +++
 kernel/locking/locktorture.c   |  4 ++--
 kernel/sched/Makefile          |  4 ++--
 kernel/sched/core.c            | 33 +++++++++++++++++++++++++++------
 kernel/sched/deadline.c        |  4 ++++
 kernel/sched/debug.c           |  2 ++
 kernel/sched/sched.h           | 33 ++++++++++++++++++++++++---------
 kernel/sched/stop_task.c       |  4 +++-
 kernel/sysctl.c                |  4 +++-
 kernel/time/posix-cpu-timers.c |  8 +++++---
 lib/Kconfig.debug              |  2 +-
 16 files changed, 109 insertions(+), 35 deletions(-)

diff --git a/include/linux/init_task.h b/include/linux/init_task.h
index e049526bc1..6befc0aa61 100644
--- a/include/linux/init_task.h
+++ b/include/linux/init_task.h
@@ -225,6 +225,16 @@ extern struct cred init_cred;
 #define INIT_TASK_SECURITY
 #endif
 
+#ifdef CONFIG_SCHED_RT
+#define INIT_TASK_RT(tsk)						\
+	.rt		= {						\
+		.run_list	= LIST_HEAD_INIT(tsk.rt.run_list),	\
+		.time_slice	= RR_TIMESLICE,				\
+	},
+#else
+#define INIT_TASK_RT(tsk)
+#endif
+
 /*
  *  INIT_TASK is used to set up the first task table, touch at
  * your own risk!. Base=0, limit=0x1fffff (=2MB)
@@ -250,10 +260,7 @@ extern struct cred init_cred;
 	.se		= {						\
 		.group_node 	= LIST_HEAD_INIT(tsk.se.group_node),	\
 	},								\
-	.rt		= {						\
-		.run_list	= LIST_HEAD_INIT(tsk.rt.run_list),	\
-		.time_slice	= RR_TIMESLICE,				\
-	},								\
+	INIT_TASK_RT(tsk)						\
 	.tasks		= LIST_HEAD_INIT(tsk.tasks),			\
 	INIT_PUSHABLE_TASKS(tsk)					\
 	INIT_CGROUP_SCHED(tsk)						\
diff --git a/include/linux/rtmutex.h b/include/linux/rtmutex.h
index 01db77a41b..05c444f930 100644
--- a/include/linux/rtmutex.h
+++ b/include/linux/rtmutex.h
@@ -12,7 +12,7 @@
 #ifndef __LINUX_RT_MUTEX_H
 #define __LINUX_RT_MUTEX_H
 
-#if 1 /* will become def CONFIG_SCHED_RT later */
+#ifdef CONFIG_SCHED_RT
 
 #include <linux/linkage.h>
 #include <linux/rbtree.h>
diff --git a/include/linux/sched.h b/include/linux/sched.h
index ba0c203669..71a43480ed 100644
--- a/include/linux/sched.h
+++ b/include/linux/sched.h
@@ -518,7 +518,9 @@ struct task_struct {
 
 	const struct sched_class	*sched_class;
 	struct sched_entity		se;
+#ifdef CONFIG_SCHED_RT
 	struct sched_rt_entity		rt;
+#endif
 #ifdef CONFIG_CGROUP_SCHED
 	struct task_group		*sched_task_group;
 #endif
diff --git a/include/linux/sched/rt.h b/include/linux/sched/rt.h
index f93329aba3..681c48361f 100644
--- a/include/linux/sched/rt.h
+++ b/include/linux/sched/rt.h
@@ -7,7 +7,7 @@ struct task_struct;
 
 static inline int rt_prio(int prio)
 {
-	if (unlikely(prio < MAX_RT_PRIO))
+	if (IS_ENABLED(CONFIG_SCHED_RT) && unlikely(prio < MAX_RT_PRIO))
 		return 1;
 	return 0;
 }
@@ -17,7 +17,7 @@ static inline int rt_task(struct task_struct *p)
 	return rt_prio(p->prio);
 }
 
-#ifdef CONFIG_RT_MUTEXES
+#if defined(CONFIG_RT_MUTEXES) && defined(CONFIG_SCHED_RT)
 /*
  * Must hold either p->pi_lock or task_rq(p)->lock.
  */
@@ -52,4 +52,10 @@ extern void normalize_rt_tasks(void);
  */
 #define RR_TIMESLICE		(100 * HZ / 1000)
 
+#ifdef CONFIG_SCHED_RT
+#define rt_timeout(tsk)		(tsk)->rt.timeout
+#else
+#define rt_timeout(tsk)		0
+#endif
+
 #endif /* _LINUX_SCHED_RT_H */
diff --git a/init/Kconfig b/init/Kconfig
index 43e6ae3414..723ec1cb5c 100644
--- a/init/Kconfig
+++ b/init/Kconfig
@@ -687,7 +687,7 @@ config TREE_RCU_TRACE
 
 config RCU_BOOST
 	bool "Enable RCU priority boosting"
-	depends on RT_MUTEXES && PREEMPT_RCU && RCU_EXPERT
+	depends on SCHED_RT && RT_MUTEXES && PREEMPT_RCU && RCU_EXPERT
 	default n
 	help
 	  This option boosts the priority of preempted RCU readers that
@@ -1090,7 +1090,7 @@ config CFS_BANDWIDTH
 
 config RT_GROUP_SCHED
 	bool "Group scheduling for SCHED_RR/FIFO"
-	depends on CGROUP_SCHED
+	depends on CGROUP_SCHED && SCHED_RT
 	default n
 	help
 	  This feature lets you explicitly allocate real CPU bandwidth
@@ -1303,6 +1303,14 @@ config SCHED_AUTOGROUP
 	  desktop applications.  Task group autogeneration is currently based
 	  upon task session.
 
+config SCHED_RT
+	bool "Real Time Task Scheduling" if EXPERT
+	default y
+	help
+	  This adds the sched_rt scheduling class to the kernel providing
+ 	  support for the SCHED_FIFO and SCHED_RR policies. You might want
+	  to disable this to reduce the kernel size. If unsure say y.
+
 config SCHED_DL
 	bool "Deadline Task Scheduling" if EXPERT
 	default y
@@ -1640,7 +1648,7 @@ config FUTEX
 
 config FUTEX_PI
 	bool
-	depends on FUTEX && RT_MUTEXES
+	depends on FUTEX && RT_MUTEXES && SCHED_RT
 	default y
 
 config HAVE_FUTEX_CMPXCHG
diff --git a/kernel/locking/Makefile b/kernel/locking/Makefile
index 760158d9d9..52892cf26c 100644
--- a/kernel/locking/Makefile
+++ b/kernel/locking/Makefile
@@ -20,8 +20,11 @@ obj-$(CONFIG_SMP) += spinlock.o
 obj-$(CONFIG_LOCK_SPIN_ON_OWNER) += osq_lock.o
 obj-$(CONFIG_PROVE_LOCKING) += spinlock.o
 obj-$(CONFIG_QUEUED_SPINLOCKS) += qspinlock.o
+# Compatibility wrappers in rtmutex.h are used when CONFIG_SCHED_Rt=n
+ifeq ($(CONFIG_SCHED_RT),y)
 obj-$(CONFIG_RT_MUTEXES) += rtmutex.o
 obj-$(CONFIG_DEBUG_RT_MUTEXES) += rtmutex-debug.o
+endif
 obj-$(CONFIG_DEBUG_SPINLOCK) += spinlock.o
 obj-$(CONFIG_DEBUG_SPINLOCK) += spinlock_debug.o
 obj-$(CONFIG_RWSEM_GENERIC_SPINLOCK) += rwsem-spinlock.o
diff --git a/kernel/locking/locktorture.c b/kernel/locking/locktorture.c
index f24582d4da..53d6753d50 100644
--- a/kernel/locking/locktorture.c
+++ b/kernel/locking/locktorture.c
@@ -446,7 +446,7 @@ static struct lock_torture_ops ww_mutex_lock_ops = {
 	.name		= "ww_mutex_lock"
 };
 
-#ifdef CONFIG_RT_MUTEXES
+#if defined(CONFIG_RT_MUTEXES) && defined(CONFIG_SCHED_RT)
 static DEFINE_RT_MUTEX(torture_rtmutex);
 
 static int torture_rtmutex_lock(void) __acquires(torture_rtmutex)
@@ -872,7 +872,7 @@ static int __init lock_torture_init(void)
 		&rw_lock_ops, &rw_lock_irq_ops,
 		&mutex_lock_ops,
 		&ww_mutex_lock_ops,
-#ifdef CONFIG_RT_MUTEXES
+#if defined(CONFIG_RT_MUTEXES) && defined(CONFIG_SCHED_RT)
 		&rtmutex_lock_ops,
 #endif
 		&rwsem_lock_ops,
diff --git a/kernel/sched/Makefile b/kernel/sched/Makefile
index 3bd6a7c1cc..bccbef85e5 100644
--- a/kernel/sched/Makefile
+++ b/kernel/sched/Makefile
@@ -16,8 +16,8 @@ CFLAGS_core.o := $(PROFILING) -fno-omit-frame-pointer
 endif
 
 obj-y += core.o loadavg.o clock.o cputime.o
-obj-y += wait.o swait.o completion.o idle.o
-obj-y += idle_task.o fair.o rt.o
+obj-y += wait.o swait.o completion.o idle.o idle_task.o fair.o
+obj-$(CONFIG_SCHED_RT) += rt.o
 obj-$(CONFIG_SCHED_DL) += deadline.o $(if $(CONFIG_SMP),cpudeadline.o)
 obj-$(CONFIG_SMP) += cpupri.o topology.o stop_task.o
 obj-$(CONFIG_SCHED_AUTOGROUP) += autogroup.o
diff --git a/kernel/sched/core.c b/kernel/sched/core.c
index 30138033b7..0d718b68df 100644
--- a/kernel/sched/core.c
+++ b/kernel/sched/core.c
@@ -642,8 +642,8 @@ bool sched_can_stop_tick(struct rq *rq)
 	 * If there are more than one RR tasks, we need the tick to effect the
 	 * actual RR behaviour.
 	 */
-	if (rq->rt.rr_nr_running) {
-		if (rq->rt.rr_nr_running == 1)
+	if (rt_rr_nr_running(rq)) {
+		if (rt_rr_nr_running(rq) == 1)
 			return true;
 		else
 			return false;
@@ -653,7 +653,7 @@ bool sched_can_stop_tick(struct rq *rq)
 	 * If there's no RR tasks, but FIFO tasks, we can skip the tick, no
 	 * forced preemption between FIFO tasks.
 	 */
-	fifo_nr_running = rq->rt.rt_nr_running - rq->rt.rr_nr_running;
+	fifo_nr_running = rt_rt_nr_running(rq) - rt_rr_nr_running(rq);
 	if (fifo_nr_running)
 		return true;
 
@@ -1584,7 +1584,7 @@ void sched_set_stop_task(int cpu, struct task_struct *stop)
 		 * Reset it back to a normal scheduling class so that
 		 * it can die in pieces.
 		 */
-		old_stop->sched_class = &rt_sched_class;
+		old_stop->sched_class = stop_sched_class.next;
 	}
 }
 
@@ -2180,11 +2180,13 @@ static void __sched_fork(unsigned long clone_flags, struct task_struct *p)
 	__dl_clear_params(p);
 #endif
 
+#ifdef CONFIG_SCHED_RT
 	INIT_LIST_HEAD(&p->rt.run_list);
 	p->rt.timeout		= 0;
 	p->rt.time_slice	= sched_rr_timeslice;
 	p->rt.on_rq		= 0;
 	p->rt.on_list		= 0;
+#endif
 
 #ifdef CONFIG_PREEMPT_NOTIFIERS
 	INIT_HLIST_HEAD(&p->preempt_notifiers);
@@ -3595,7 +3597,7 @@ int default_wake_function(wait_queue_t *curr, unsigned mode, int wake_flags,
 }
 EXPORT_SYMBOL(default_wake_function);
 
-#ifdef CONFIG_RT_MUTEXES
+#if defined(CONFIG_RT_MUTEXES) && defined(CONFIG_SCHED_RT)
 
 static inline int __rt_effective_prio(struct task_struct *pi_task, int prio)
 {
@@ -3994,6 +3996,23 @@ static int __sched_setscheduler(struct task_struct *p,
 
 	/* May grab non-irq protected spin_locks: */
 	BUG_ON(in_interrupt());
+
+	/*
+	 * When the RT scheduling class is disabled, let's make sure kernel threads
+	 * wanting RT still get lowest nice value to give them highest available
+	 * priority rather than simply returning an error. Obviously we can't test
+	 * rt_policy() here as it is always false in that case.
+	 */
+	if (!IS_ENABLED(CONFIG_SCHED_RT) && !user &&
+	    (policy == SCHED_FIFO || policy == SCHED_RR)) {
+		static const struct sched_attr k_attr = {
+			.sched_policy = SCHED_NORMAL,
+			.sched_nice = MIN_NICE,
+		};
+		attr = &k_attr;
+		policy = SCHED_NORMAL;
+	}
+
 recheck:
 	/* Double check policy once rq lock held: */
 	if (policy < 0) {
@@ -5857,7 +5876,10 @@ void __init sched_init(void)
 		rq->calc_load_active = 0;
 		rq->calc_load_update = jiffies + LOAD_FREQ;
 		init_cfs_rq(&rq->cfs);
+#ifdef CONFIG_SCHED_RT
 		init_rt_rq(&rq->rt);
+		rq->rt.rt_runtime = def_rt_bandwidth.rt_runtime;
+#endif
 		init_dl_rq(&rq->dl);
 #ifdef CONFIG_FAIR_GROUP_SCHED
 		root_task_group.shares = ROOT_TASK_GROUP_LOAD;
@@ -5886,7 +5908,6 @@ void __init sched_init(void)
 		init_tg_cfs_entry(&root_task_group, &rq->cfs, NULL, i, NULL);
 #endif /* CONFIG_FAIR_GROUP_SCHED */
 
-		rq->rt.rt_runtime = def_rt_bandwidth.rt_runtime;
 #ifdef CONFIG_RT_GROUP_SCHED
 		init_tg_rt_entry(&root_task_group, &rq->rt, NULL, i, NULL);
 #endif
diff --git a/kernel/sched/deadline.c b/kernel/sched/deadline.c
index e879feae5f..08d7193ba5 100644
--- a/kernel/sched/deadline.c
+++ b/kernel/sched/deadline.c
@@ -1825,7 +1825,11 @@ static void prio_changed_dl(struct rq *rq, struct task_struct *p,
 }
 
 const struct sched_class dl_sched_class = {
+#ifdef CONFIG_SCHED_RT
 	.next			= &rt_sched_class,
+#else
+	.next			= &fair_sched_class,
+#endif
 	.enqueue_task		= enqueue_task_dl,
 	.dequeue_task		= dequeue_task_dl,
 	.yield_task		= yield_task_dl,
diff --git a/kernel/sched/debug.c b/kernel/sched/debug.c
index 84f80a81ab..c550723ce9 100644
--- a/kernel/sched/debug.c
+++ b/kernel/sched/debug.c
@@ -645,7 +645,9 @@ do {									\
 
 	spin_lock_irqsave(&sched_debug_lock, flags);
 	print_cfs_stats(m, cpu);
+#ifdef CONFIG_SCHED_RT
 	print_rt_stats(m, cpu);
+#endif
 #ifdef CONFIG_SCHED_DL
 	print_dl_stats(m, cpu);
 #endif
diff --git a/kernel/sched/sched.h b/kernel/sched/sched.h
index c05cc33848..07366c1d04 100644
--- a/kernel/sched/sched.h
+++ b/kernel/sched/sched.h
@@ -132,7 +132,8 @@ static inline int fair_policy(int policy)
 
 static inline int rt_policy(int policy)
 {
-	return policy == SCHED_FIFO || policy == SCHED_RR;
+	return IS_ENABLED(CONFIG_SCHED_RT) &&
+	       (policy == SCHED_FIFO || policy == SCHED_RR);
 }
 
 static inline int dl_policy(int policy)
@@ -398,8 +399,6 @@ extern void __refill_cfs_bandwidth_runtime(struct cfs_bandwidth *cfs_b);
 extern void start_cfs_bandwidth(struct cfs_bandwidth *cfs_b);
 extern void unthrottle_cfs_rq(struct cfs_rq *cfs_rq);
 
-extern void free_rt_sched_group(struct task_group *tg);
-extern int alloc_rt_sched_group(struct task_group *tg, struct task_group *parent);
 extern void init_tg_rt_entry(struct task_group *tg, struct rt_rq *rt_rq,
 		struct sched_rt_entity *rt_se, int cpu,
 		struct sched_rt_entity *parent);
@@ -518,7 +517,7 @@ struct cfs_rq {
 
 static inline int rt_bandwidth_enabled(void)
 {
-	return sysctl_sched_rt_runtime >= 0;
+	return IS_ENABLED(CONFIG_SCHED_RT) && sysctl_sched_rt_runtime >= 0;
 }
 
 /* RT IPI pull logic requires IRQ_WORK */
@@ -567,6 +566,24 @@ struct rt_rq {
 #endif
 };
 
+extern struct rt_bandwidth def_rt_bandwidth;
+
+#ifdef CONFIG_SCHED_RT
+#define rt_rr_nr_running(rq)		(rq)->rt.rr_nr_running
+#define rt_rt_nr_running(rq)		(rq)->rt.rt_nr_running
+extern int alloc_rt_sched_group(struct task_group *tg, struct task_group *parent);
+extern void free_rt_sched_group(struct task_group *tg);
+extern void init_sched_rt_class(void);
+extern void init_rt_bandwidth(struct rt_bandwidth *rt_b, u64 period, u64 runtime);
+#else
+#define rt_rr_nr_running(rq)		0
+#define rt_rt_nr_running(rq)		0
+#define alloc_rt_sched_group(...)	1
+#define free_rt_sched_group(tg)		do { } while (0)
+#define init_sched_rt_class()		do {  } while (0)
+#define init_rt_bandwidth(...)		do { } while (0)
+#endif
+
 /* Deadline class' related fields in a runqueue */
 struct dl_rq {
 	/* runqueue is an rbtree, ordered by deadline */
@@ -1470,8 +1487,10 @@ static inline void set_curr_task(struct rq *rq, struct task_struct *curr)
 #define sched_class_highest (&stop_sched_class)
 #elif defined(CONFIG_SCHED_DL)
 #define sched_class_highest (&dl_sched_class)
-#else
+#elif defined(CONFIG_SCHED_RT)
 #define sched_class_highest (&rt_sched_class)
+#else
+#define sched_class_highest (&fair_sched_class)
 #endif
 
 #define for_each_class(class) \
@@ -1524,15 +1543,11 @@ extern void sysrq_sched_debug_show(void);
 extern void sched_init_granularity(void);
 extern void update_max_interval(void);
 
-extern void init_sched_rt_class(void);
 extern void init_sched_fair_class(void);
 
 extern void resched_curr(struct rq *rq);
 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);
 
 unsigned long to_ratio(u64 period, u64 runtime);
diff --git a/kernel/sched/stop_task.c b/kernel/sched/stop_task.c
index 5632dc3e63..7cad8c1540 100644
--- a/kernel/sched/stop_task.c
+++ b/kernel/sched/stop_task.c
@@ -112,8 +112,10 @@ static void update_curr_stop(struct rq *rq)
 const struct sched_class stop_sched_class = {
 #ifdef CONFIG_SCHED_DL
 	.next			= &dl_sched_class,
-#else
+#elif defined(CONFIG_SCHED_RT)
 	.next			= &rt_sched_class,
+#else
+	.next			= &fair_sched_class,
 #endif
 
 	.enqueue_task		= enqueue_task_stop,
diff --git a/kernel/sysctl.c b/kernel/sysctl.c
index 4dfba1a76c..1c670f4053 100644
--- a/kernel/sysctl.c
+++ b/kernel/sysctl.c
@@ -401,6 +401,7 @@ static struct ctl_table kern_table[] = {
 	},
 #endif /* CONFIG_NUMA_BALANCING */
 #endif /* CONFIG_SCHED_DEBUG */
+#ifdef CONFIG_SCHED_RT
 	{
 		.procname	= "sched_rt_period_us",
 		.data		= &sysctl_sched_rt_period,
@@ -422,6 +423,7 @@ static struct ctl_table kern_table[] = {
 		.mode		= 0644,
 		.proc_handler	= sched_rr_handler,
 	},
+#endif
 #ifdef CONFIG_SCHED_AUTOGROUP
 	{
 		.procname	= "sched_autogroup_enabled",
@@ -1071,7 +1073,7 @@ static struct ctl_table kern_table[] = {
 		.extra1		= &neg_one,
 	},
 #endif
-#ifdef CONFIG_RT_MUTEXES
+#if defined(CONFIG_RT_MUTEXES) && defined(CONFIG_SCHED_RT)
 	{
 		.procname	= "max_lock_depth",
 		.data		= &max_lock_depth,
diff --git a/kernel/time/posix-cpu-timers.c b/kernel/time/posix-cpu-timers.c
index d2a1e6dd02..32b2ea6212 100644
--- a/kernel/time/posix-cpu-timers.c
+++ b/kernel/time/posix-cpu-timers.c
@@ -4,6 +4,7 @@
 
 #include <linux/sched/signal.h>
 #include <linux/sched/cputime.h>
+#include <linux/sched/rt.h>
 #include <linux/posix-timers.h>
 #include <linux/errno.h>
 #include <linux/math64.h>
@@ -814,13 +815,14 @@ static void check_thread_timers(struct task_struct *tsk,
 	/*
 	 * Check for the special case thread timers.
 	 */
-	soft = READ_ONCE(sig->rlim[RLIMIT_RTTIME].rlim_cur);
+	soft = IS_ENABLED(CONFIG_SCHED_RT) ?
+		READ_ONCE(sig->rlim[RLIMIT_RTTIME].rlim_cur) : RLIM_INFINITY;
 	if (soft != RLIM_INFINITY) {
 		unsigned long hard =
 			READ_ONCE(sig->rlim[RLIMIT_RTTIME].rlim_max);
 
 		if (hard != RLIM_INFINITY &&
-		    tsk->rt.timeout > DIV_ROUND_UP(hard, USEC_PER_SEC/HZ)) {
+		    rt_timeout(tsk) > DIV_ROUND_UP(hard, USEC_PER_SEC/HZ)) {
 			/*
 			 * At the hard limit, we just die.
 			 * No need to calculate anything else now.
@@ -832,7 +834,7 @@ static void check_thread_timers(struct task_struct *tsk,
 			__group_send_sig_info(SIGKILL, SEND_SIG_PRIV, tsk);
 			return;
 		}
-		if (tsk->rt.timeout > DIV_ROUND_UP(soft, USEC_PER_SEC/HZ)) {
+		if (rt_timeout(tsk) > DIV_ROUND_UP(soft, USEC_PER_SEC/HZ)) {
 			/*
 			 * At the soft limit, send a SIGXCPU every second.
 			 */
diff --git a/lib/Kconfig.debug b/lib/Kconfig.debug
index e4587ebe52..0ecc7eb9dc 100644
--- a/lib/Kconfig.debug
+++ b/lib/Kconfig.debug
@@ -1008,7 +1008,7 @@ menu "Lock Debugging (spinlocks, mutexes, etc...)"
 
 config DEBUG_RT_MUTEXES
 	bool "RT Mutex debugging, deadlock detection"
-	depends on DEBUG_KERNEL && RT_MUTEXES
+	depends on DEBUG_KERNEL && RT_MUTEXES && SCHED_RT
 	help
 	 This allows rt mutex semantics violations and rt mutex related
 	 deadlocks (lockups) to be detected and reported automatically.
-- 
2.9.4

[toc] | [prev] | [next] | [standalone]

#1659303 — [PATCH v2 1/8] cpuset/sched: cpuset makes sense for SMP only

Make CONFIG_CPUSETS depend on SMP as this feature makes no sense
on UP. This allows for configuring out cpuset_cpumask_can_shrink()
and task_can_attach() entirely.

Signed-off-by: Nicolas Pitre <nico@linaro.org>
---
 init/Kconfig        | 1 +
 kernel/sched/core.c | 7 +++----
 2 files changed, 4 insertions(+), 4 deletions(-)

diff --git a/init/Kconfig b/init/Kconfig
index 4ef946b466..b9aed60cac 100644
--- a/init/Kconfig
+++ b/init/Kconfig
@@ -1156,6 +1156,7 @@ config CGROUP_HUGETLB
 
 config CPUSETS
 	bool "Cpuset controller"
+	depends on SMP
 	help
 	  This option will let you create and manage CPUSETs which
 	  allow dynamically partitioning a system into sets of CPUs and
diff --git a/kernel/sched/core.c b/kernel/sched/core.c
index 803c3bc274..de274b1bd2 100644
--- a/kernel/sched/core.c
+++ b/kernel/sched/core.c
@@ -5463,6 +5463,8 @@ void init_idle(struct task_struct *idle, int cpu)
 #endif
 }
 
+#ifdef CONFIG_SMP
+
 int cpuset_cpumask_can_shrink(const struct cpumask *cur,
 			      const struct cpumask *trial)
 {
@@ -5506,7 +5508,6 @@ int task_can_attach(struct task_struct *p,
 		goto out;
 	}
 
-#ifdef CONFIG_SMP
 	if (dl_task(p) && !cpumask_intersects(task_rq(p)->rd->span,
 					      cs_cpus_allowed)) {
 		unsigned int dest_cpu = cpumask_any_and(cpu_active_mask,
@@ -5536,13 +5537,11 @@ int task_can_attach(struct task_struct *p,
 		rcu_read_unlock_sched();
 
 	}
-#endif
+
 out:
 	return ret;
 }
 
-#ifdef CONFIG_SMP
-
 bool sched_smp_initialized __read_mostly;
 
 #ifdef CONFIG_NUMA_BALANCING
-- 
2.9.4

[toc] | [prev] | [next] | [standalone]

#1659955

* Nicolas Pitre <nicolas.pitre@linaro.org> wrote:

> Many embedded systems don't need the full scheduler support. Most of the
> time, user space is tightly controlled and many of the scheduler facilities
> are simply unused.

Sorry, NAK:

>  23 files changed, 3190 insertions(+), 2897 deletions(-)

That's a lot of extra code plus churn for a code base that is already pretty
#ifdef heavy.

Also, the savings are marginal, even with significant functionality disabled:

>   text    data     bss     dec     hex filename
>  28623    3404     128   32155    7d9b kernel/sched/built-in.o
>
> With this series and dl and rt classes disabled:
>
>   text    data     bss     dec     hex filename
>  20734    3334      40   24108    5e2c kernel/sched/built-in.o

With 1GHz + 1GB RAM SoCs being well below $10 in bulk we worry about code 
complexity, predictability, testability, behavioral and ABI uniformity a lot more 
than about the last 10-20k of kernel text footprint...

So I think the 'tiny' efforts are fundamentally misguided and are shooting for an 
ever shrinking market of RAM/ROM starved products whose share is shrinking every 
month.

We want to _remove_ kernel options and reduce complexity, not increase it.

So unless there's convincing counter arguments, or Linus overrules me, this NAK is 
pretty firm.

I'd love to see scheduler complexity reduction patches though, the "CPP count" of 
the scheduler code base is pretty damn high:

  triton:~/tip> git grep -h '^#[^ ]' kernel/sched/  | cut -d' ' -f1 | sort | uniq -c | sort -n | tail -10
      2 #ifdef  CONFIG_SCHED_DEBUG
      4 #endif  /*
     19 #if
     26 #ifndef
     27 #undef
     97 #else
    161 #define
    199 #include
    317 #ifdef
    361 #endif

Thanks,

	Ingo

[toc] | [prev] | [next] | [standalone]

#1660020

On Wed, 7 Jun 2017, Ingo Molnar wrote:

> 
> * Nicolas Pitre <nicolas.pitre@linaro.org> wrote:
> 
> > Many embedded systems don't need the full scheduler support. Most of the
> > time, user space is tightly controlled and many of the scheduler facilities
> > are simply unused.
> 
> Sorry, NAK:
> 
> >  23 files changed, 3190 insertions(+), 2897 deletions(-)
> 
> That's a lot of extra code plus churn for a code base that is already pretty
> #ifdef heavy.
> 
> Also, the savings are marginal, even with significant functionality disabled:
> 
> >   text    data     bss     dec     hex filename
> >  28623    3404     128   32155    7d9b kernel/sched/built-in.o
> >
> > With this series and dl and rt classes disabled:
> >
> >   text    data     bss     dec     hex filename
> >  20734    3334      40   24108    5e2c kernel/sched/built-in.o
> 
> With 1GHz + 1GB RAM SoCs being well below $10 in bulk we worry about code 
> complexity, predictability, testability, behavioral and ABI uniformity a lot more 
> than about the last 10-20k of kernel text footprint...
> 
> So I think the 'tiny' efforts are fundamentally misguided and are shooting for an 
> ever shrinking market of RAM/ROM starved products whose share is shrinking every 
> month.

I'm rather seeing the opposite: an ever growing market of 
internet-connected coin-cell-battery-powered tiny devices where the 
amount of RAM is counted in kilobytes rather than megabytes.

Let me repeat some background as to what my fundamental motivation is, 
and then maybe you'll understand why I'm doing this.

What is the biggest buzzword in the IT industry besides AI right now?
It is IOT.

Most IOT targets are so small that people are rewriting new operating 
systems from scratch for them. Lots of fragmentation already exists. 
We're talking about systems with less than one megabyte of RAM, 
sometimes much less.  Still, those things are being connected to the 
internet. And this is going to be a total security nightmare.

I wish to be able to leverage the Linux ecosystem for as much of the IOT 
space as possible to avoid the worst of those nightmares.  The Linux 
ecosystem has a *lot* of knowledgeable people around it, a lot of 
testing infrastructure and tooling available already, etc.  If a 
security issue turns up on Linux, it has a greater chance of being 
caught early, or fixed quickly otherwise, and finding people with the 
right knowledge is easier on Linux than it could be on any RTOS out 
there. Still with me so far?

Yes we have tools that can automatically reduce the kernel size. We can 
use LTO with the compiler, etc.  LTO is pretty good already. It can 
typically reduce the kernel size by 20%.  If all system calls are 
disabled except for a few ones, then LTO can get rid of another 20%. The 
minimal kernel I get is still 400-500 KB in size.  That's still too big.

There is this 120 KB of VFS code that is always there even though there 
is no real filesystem at all configured in the kernel. There is that 
other 100 KB of core driver support code despite the fact that the set 
of drivers I'm using are very simple and make no use of most of that 
core driver code. Etc.

There comes a point where there is no option but to explicitly trim out 
parts of the kernel as such decisions cannot be automated, hence this 
patch series. Bringing the scheduler under 20KB in size is therefore 
very useful in that context. Alternatively I could push for a parallel 
implementation as I did with the TTY layer where I obtained a 6x size 
reduction. But in the scheduler case I obtained only a 2x size reduction 
so I thought it could be more profitable to get about the same saving by 
reworking the existing code instead., and eventually contributing a very 
bare scheduler class that would be a smaller alternative to the fair 
scheduler for deployments where that makes sense. Unless you actually 
changed your mind about alternative whole scheduler implementations that 
is...

For Linux to be suitable for small IoT, it has to be small, damn small. 
My target is 256 KB of RAM.  And if you look at the kind of application 
those 256-KB systems are doing, it's basically one main task typically 
acquiring sensor data and sending it in some crypted protocol over a 
wireless network on the internet, and possibly accepting commands back.  
So what do you need from the OS to achieve that?  A few system calls, a 
minimal scheduler, minimal memory management, minimal filesystem 
structure and minimal network stack. And your user app.

So, why not having each of those blocks be created using the existing 
Linux syscall interface and internal API?  At that point, it should be 
possible to take your standard full-featured Linux workstation and 
develop your user app on it, run it there using all the existing native 
debugging tools, etc. In the end you just pick the mini version of 
everything for the final target and you're done.  And you don't have to 
learn a whole new OS, development environment and program model, etc.

Next on my list would be a cache-less, completely serialized VFS bypass 
that has only what's needed to make the link between the read/write 
syscalls, a filesystem driver and a block driver while preserving the 
existing kernel APIs. And by being really small, the maintenance cost of 
a "parallel" implementation isn't very high, certainly much less than 
trying to maintain a single code path that can scale to both extremes 
in that case.

PS: As far as I remember, Linus didn't condemn the idea last time I 
    brought up this topic in his presence. I therefore hope we could 
    find ways for allowing Linux usage into the largest computing device 
    deployment to come.


Nicolas

[toc] | [prev] | [next] | [standalone]

#1660109

> Next on my list would be a cache-less, completely serialized VFS bypass 
> that has only what's needed to make the link between the read/write 
> syscalls, a filesystem driver and a block driver while preserving the 
> existing kernel APIs. And by being really small, the maintenance cost of 
> a "parallel" implementation isn't very high, certainly much less than 
> trying to maintain a single code path that can scale to both extremes 
> in that case.

So once you've rewritten the tty layer, the device drivers, the VFS and
removed most of the syscalls why even pretend it's Linux any more. It's
something else, and that something else is totally architecturally
incompatible with Linux. That's btw a good thing - trying to fit Linux
directly into such a tiny device isn't sensible because the core
assumptions you make about scalability are just totally different.

IMHO it would be far far better to just borrow the bits that look handy,
and the bits of the ABI you need and put them together as a new OS
kernel. When you look at tiny hardware even core bits of the Linux
architecture like the wait queues are just not sensible uses of memory
and cause fragmentation. The dcache is completely insane in that
environment, the scheduler is total overkill and the networking is easy
to DoS in a tiny memory. The device layer assumes dynamic hot pluggable
device architecture - and that's extremely expensive but nonsensical for
most µcontrollers.

It's easy to put a Unixlike OS in 256K of RAM and a pile of flash. It's
going to be pretty easy to put all the major bits of the Linux API into
it. You can run 2.11BSD with only 256K of writable memory (you need more
in your PDP-11 to run it but if you look all of that in a µcontroller
would live in flash).


Alan

[toc] | [prev] | [next] | [standalone]

#1660236

[Multipart message — attachments visible in raw view] — view raw

On Wed, 7 Jun 2017, Alan Cox wrote:

> > Next on my list would be a cache-less, completely serialized VFS bypass 
> > that has only what's needed to make the link between the read/write 
> > syscalls, a filesystem driver and a block driver while preserving the 
> > existing kernel APIs. And by being really small, the maintenance cost of 
> > a "parallel" implementation isn't very high, certainly much less than 
> > trying to maintain a single code path that can scale to both extremes 
> > in that case.
> 
> So once you've rewritten the tty layer, the device drivers, the VFS and
> removed most of the syscalls why even pretend it's Linux any more. It's
> something else, and that something else is totally architecturally
> incompatible with Linux.

You got at least one thing wrong. One huge benefit is to leverage 
existing device drivers of which Linux is plentiful. So there is no 
point rewriting device drivers.

Then if most syscalls are removed then *of course* you won't be able to 
boot a standard "Linux" distro on it. But that's not the point either. 
However the compatibility is preserved the other way around i.e. user 
space from this Linux subset should just work as is on a full Linux 
kernel. And it would still be a Linux code base i.e. architecturally 
compatible with Linux at the source level.

> That's btw a good thing - trying to fit Linux
> directly into such a tiny device isn't sensible because the core
> assumptions you make about scalability are just totally different.

For a couple core components that's true, hence my approach with the TTY 
layer. But many other parts aren't that bad. And given that a small 
system can't afford that many whistles and bells then it is not like if 
the whole of Linux would be rewritten anyway.

> IMHO it would be far far better to just borrow the bits that look 
> handy, and the bits of the ABI you need and put them together as a new 
> OS kernel.

Hasn't that been attempted and failed already? One nasty effect of such 
an approach is effectively the creation of a fork, then you completely 
lose the community leverage and gravitational effect, create 
fragmentation, fixes are not propagated across, etc.

> When you look at tiny hardware even core bits of the Linux
> architecture like the wait queues are just not sensible uses of memory
> and cause fragmentation. The dcache is completely insane in that
> environment, the scheduler is total overkill and the networking is easy
> to DoS in a tiny memory. The device layer assumes dynamic hot pluggable
> device architecture - and that's extremely expensive but nonsensical for
> most µcontrollers.

Why do you think I'm proposing scheduler patches? And TTY patches before 
that, and having plans for the VFS? Obviously, all those things coule be 
reimplemented for small scale in a new and separate tiny OS. But what if 
those things could just live in the Linux source tree alongside their 
big cousins and be swapped according to your needs? Why couldn't those 
arguments served to the embedded people for years about joining the 
mainline effort be extended to this use case as well?

> It's easy to put a Unixlike OS in 256K of RAM and a pile of flash. It's
> going to be pretty easy to put all the major bits of the Linux API into
> it. You can run 2.11BSD with only 256K of writable memory (you need more
> in your PDP-11 to run it but if you look all of that in a µcontroller
> would live in flash).

Would be nice if that could share the same source code whenever 
possible, and also the same source tree, no?


Nicolas

[toc] | [prev] | [next] | [standalone]

#1660274

> You got at least one thing wrong. One huge benefit is to leverage 
> existing device drivers of which Linux is plentiful. So there is no 
> point rewriting device drivers.

So you want to keep a common interface for some of the common driver
APIs. Several people have managed that.

> > IMHO it would be far far better to just borrow the bits that look 
> > handy, and the bits of the ABI you need and put them together as a new 
> > OS kernel.  
> 
> Hasn't that been attempted and failed already? One nasty effect of such 
> an approach is effectively the creation of a fork, then you completely 
> lose the community leverage and gravitational effect, create 
> fragmentation, fixes are not propagated across, etc.

Almost nothing can be shared though, and for drivers you want to re-use
then if you can re-use them you can share the code for that.

> Why do you think I'm proposing scheduler patches? And TTY patches before 
> that, and having plans for the VFS? Obviously, all those things coule be 
> reimplemented for small scale in a new and separate tiny OS. But what if 
> those things could just live in the Linux source tree alongside their 
> big cousins and be swapped according to your needs? Why couldn't those 
> arguments served to the embedded people for years about joining the 
> mainline effort be extended to this use case as well?

I don't think it works like that. The overhead of the duplication
and trying to keep them aligned rapidly exceeds the value they give. The
moment you try and do the job well you also 
> 
> > It's easy to put a Unixlike OS in 256K of RAM and a pile of flash. It's
> > going to be pretty easy to put all the major bits of the Linux API into
> > it. You can run 2.11BSD with only 256K of writable memory (you need more
> > in your PDP-11 to run it but if you look all of that in a µcontroller
> > would live in flash).  
> 
> Would be nice if that could share the same source code whenever 
> possible, and also the same source tree, no?

But that will never work. The fundamental architecture of a tiny system
is different because the scaling rules and underlying algorithms are
different. wait queues don't work sanely on tiny devices, TCP queues need
a totally different architecture, scheduling is quite different, memory
mangement is totally different, things like the dcache which is fairly
fundamental to the VFS internals make no sense, the locking model for
file systems makes no sense because you can't use all that expensive
scaling. Even the device core which is designed for dynamically managed
trees of devices with hotplug, discovery and power management heirarchies
is basically a large resource expensive paper weight.

It goes on and on. Add any desire to do hard real time or meet things
like ASIL-B to that and you hit a brick wall pretty damned quick.

When you proposed the tty changes I was dubious, now you are talking
about basically writing a new OS kernel in the same git tree that shares
the drivers it looks even less sensible from a Linux perspective.

Alan

[toc] | [prev] | [next] | [standalone]

#1660884

Also, let me make it clear at the outset that we do care about RAM footprint all 
the time, and I've applied countless data structure and .text reducing patches to 
the kernel. But there's a cost/benefit analysis to be made, and this series fails 
that test in my view, because it increases the complexity of an already complex 
code base:

* Nicolas Pitre <nicolas.pitre@linaro.org> wrote:

> Most IOT targets are so small that people are rewriting new operating systems 
> from scratch for them. Lots of fragmentation already exists.

Let me offer a speculative if somewhat cynical prediction: 90% of those ghastly 
IOT hardware hacks won't survive the market. The remaining 10% will be successful 
financially, despite being ghastly hardware hacks and will eventually, in the next 
iteration or so, get a proper OS.

As users ask for more features the the hardware capabilities will increase 
dramatically and home-grown microcontroller derived code plus minimal OSes will be 
replaced by a 'real' OS. Because both developers and users will demand IPv6 
compatibility, or Bluetooth connectivity, or storage support, or any random range 
of features we have in the Linux kernel.

With the stroke of a pen from the CFO: "yes, we can spend more on our next 
hardware design!" the problem goes away, overnight, and nobody will look back at 
the hardware hack that had only 1MB of RAM.

> [...] We're talking about systems with less than one megabyte of RAM, sometimes 
> much less.

Two data points:

Firstly, by the time any Linux kernel change I commit today gets to a typical 
distro it's at least 0.5-1 years, 2 years for it to get widely used by hardware 
shops - 5 years to get used by enterprises. More latency in more conservative 
places.

Secondly, I don't see Moore's Law reversing:

   http://nerdfever.com/wp-content/uploads/2015/06/2015-06_Moravec_MIPS.png

If you combine those two time frames, the consequence of this:

Even taking the 1MB size at face value (which I don't: a networking enabled system 
can probably not function very well with just 1MB of RAM) - the RAM-starved 1 MB 
system today will effectively be a 2 MB system in 2 years.

And yes, I don't claim Moore's law will go on forever and I'm oversimplifying - 
maybe things are slowing down and it will only be 1.5 MB, but the point remains: 
the importance of your 20kb .text savings will become a 10-15k .text savings in 
just 2 years. In 8 years today's 1 MB system will be a 32 MB system if that trend 
holds up.

You can already fit a mostly full Linux system into 32 MB just fine, i.e. the 
problem has solved itself just by waiting a bit or by increasing the hardware 
capabilities a bit.

But the kernel complexity you introduce with this series stays with us! It will be 
an additional cost added to many scheduler commits going forward. It's an added 
cost for all the other usecases.

Also, it's not like 20k .text savings will magically enable Linux to fit into 1MB 
of RAM - it won't. The smallest still practical more or less generic Linux system 
in existence today is around 16 MB. You can shrink it more, but the effort 
increases exponentially once you go below a natural minimum size.

> [...]  Still, those things are being connected to the internet. [...]

So while I believe small size has its value, I think it's far more important to be 
able to _trust_ those devices than to squeeze the last kilobyte out of the kernel.

In that sense these qualities:

 - reducing complexity,
 - reducing actual line count,
 - increasing testability,
 - increasing reviewability,
 - offering behavioral and ABI uniformity

are more important than 1% of RAM of very, very RAM starved system which likely 
won't use Linux to begin with...

So while it obviously the "complexity vs. kernel size" trade-off will always be a 
judgement call, for the scheduler it's not really an open question what we need to 
do at this stage: we need to reduce complexity and #ifdef variants, not increase 
it.

Thanks,

	Ingo

[toc] | [prev] | [next] | [standalone]

#1661558

> As users ask for more features the the hardware capabilities will increase 
> dramatically and home-grown microcontroller derived code plus minimal OSes will be 
> replaced by a 'real' OS. Because both developers and users will demand IPv6 
> compatibility, or Bluetooth connectivity, or storage support, or any random range 
> of features we have in the Linux kernel.

There are already tiny OS's with that feature set but they don't feel
Unixish and aren't quite so fun to program.

> Even taking the 1MB size at face value (which I don't: a networking enabled system 
> can probably not function very well with just 1MB of RAM) - the RAM-starved 1 MB 
> system today will effectively be a 2 MB system in 2 years.

Probably not - I may be wrong but power and what you can and can't put on
the same die are likely to mean that small RAM devices are here for a
while and in fact the CFO will be ordering the engineers to get it in
less RAM to save 20 cents a unit.

> And yes, I don't claim Moore's law will go on forever and I'm oversimplifying - 
> maybe things are slowing down and it will only be 1.5 MB, but the point remains: 
> the importance of your 20kb .text savings will become a 10-15k .text savings in 
> just 2 years. In 8 years today's 1 MB system will be a 32 MB system if that trend 
> holds up.

Power means it's more likely IMHO that todays 256K RAM system will in a
few years be either a 64K RAM system or have tons of persistent memory.

Alan

[toc] | [prev] | [next] | [standalone]

#1661645

On Thu, 8 Jun 2017, Ingo Molnar wrote:

> 
> Also, let me make it clear at the outset that we do care about RAM footprint all 
> the time, and I've applied countless data structure and .text reducing patches to 
> the kernel. But there's a cost/benefit analysis to be made, and this series fails 
> that test in my view, because it increases the complexity of an already complex 
> code base:
> 
> * Nicolas Pitre <nicolas.pitre@linaro.org> wrote:
> 
> > Most IOT targets are so small that people are rewriting new operating systems 
> > from scratch for them. Lots of fragmentation already exists.
> 
> Let me offer a speculative if somewhat cynical prediction: 90% of those ghastly 
> IOT hardware hacks won't survive the market. The remaining 10% will be successful 
> financially, despite being ghastly hardware hacks and will eventually, in the next 
> iteration or so, get a proper OS.

Your prediction is based on a false premise. There is simply no money to 
be made with IoT hardware, especially in the low end.  Those little 
devices will be given away for free because it is in the service 
subscription that the money is. So the hardware has to, and will be, 
extremely cheap to produce. If a serious bug turns up in one of those 
device, my own cynical prediction is that no one will bother with field 
upgradability and they will ask you to throw the device away instead 
while they ship you a replacement (field upgradability implies at least 
twice the flash memory size and that comes with a cost so some will 
gamble that obsolescence will happen before a serious bug turns up).

> As users ask for more features the the hardware capabilities will increase 
> dramatically and home-grown microcontroller derived code plus minimal OSes will be 
> replaced by a 'real' OS. Because both developers and users will demand IPv6 
> compatibility, or Bluetooth connectivity, or storage support, or any random range 
> of features we have in the Linux kernel.

The "Cloud" is taking care of most of that. For the rest, your cellphone 
or IoT gateway will take over. IPv6 stacks are already used in tiny 
microcontrollers with as low as 32KB of RAM.

> With the stroke of a pen from the CFO: "yes, we can spend more on our next 
> hardware design!" the problem goes away, overnight, and nobody will look back at 
> the hardware hack that had only 1MB of RAM.

Of course hobbyists can already get a Raspberry Pi Zero and run a full 
featured Linux distro on it... for a mere 5 bucks. That comes with 512MB 
of RAM so my patches certainly don't make a difference there.

But that's not that simple.  First there is a fundamental constraint 
which is power consumption. If you want your device to run for months 
(some will hope years) from the same tiny battery then you just cannot 
afford SDRAM. So we're talking static RAM here. And to keep costs down 
because you want to give away your thingies by the millions for free it 
usually means single-chip designs with on-chip sub-megabyte static RAM.  
And in that field the 256KB mark is located towards the high end of the 
spectrum.  Many IPv6-capable chips available today have less than that.

And the thing is: people already manage to do a awful lot of stuff in 
such a constrained device. Some probably did a good job of it, but most 
of them likely suck and we don't know about their bugs because we have 
no idea what's running inside.

And because it is rather easy to write a new OS from scratch for such a 
small environment (and who didn't dream of writing his own OS, right?) 
then about every company in that field did so. That's not counting most 
Open Source ones which usually are close to single-person projects. So 
you get a lot of fragmentation, very very little peer review, and no 
incentive for proper maintenance because the cost saving simply isn't 
significant enough.

It is just like asteroids. Some of them collapse to form bigger objects 
like planets, while others have too weak a gravitational field to gather 
more matter. My vision is about leveraging the Linux gravitational power 
to bring the tiny embedded space together because, on its own, the tiny 
embedded space simply has not enough community power to actually 
organize itself.

Of course there are important parts of Linux that couldn't be reused as 
is in such a setup, but yet many other things still can be reused with 
either some modifications or a tiny parallel subsystem substitution. 
Technically, it is always possible to find ways to make it low on 
maintenance and beneficial to the wider community. But first and 
foremost you have to agree with the fundamental principle of gathering 
more people around a common codebase to make it better for everyone and 
not suggest that they stick to themselves. If you agree to that then we 
can move back to a technical discussion.

> > [...] We're talking about systems with less than one megabyte of RAM, sometimes 
> > much less.
> 
> Two data points:
> 
> Firstly, by the time any Linux kernel change I commit today gets to a typical 
> distro it's at least 0.5-1 years, 2 years for it to get widely used by hardware 
> shops - 5 years to get used by enterprises. More latency in more conservative 
> places.

Don't forget that you are also merging patches today from the Android 
folks that have been deployed into actual products years ago. So the 
enterprise distro comparison simply has no commonalities here.

> Secondly, I don't see Moore's Law reversing:
> 
>    http://nerdfever.com/wp-content/uploads/2015/06/2015-06_Moravec_MIPS.png
> 
> If you combine those two time frames, the consequence of this:
> 
> Even taking the 1MB size at face value (which I don't: a networking enabled system 
> can probably not function very well with just 1MB of RAM) - the RAM-starved 1 MB 
> system today will effectively be a 2 MB system in 2 years.

As surprising as it might be, IPv6 stacks requiring only a few dozens of 
kilobytes of memory do exist. Not so surprisingly though, some people 
think that the existing stacks simply suck and they are rewriting yet 
another one ... because they think their own will be better of course.

So there *is* still a huge market for sub-megabyte systems. I was also 
counting on Moore's law so that by the time Linux actually has the 
ability to be tailored for such systems then typical SRAM in those 
10-cents microcontrollers will be 512KB instead of 128 or 32.

> You can already fit a mostly full Linux system into 32 MB just fine, i.e. the 
> problem has solved itself just by waiting a bit or by increasing the hardware 
> capabilities a bit.

You just can't procure SDRAM chips smaller than 32MB on the market 
anymore. That's why Linux didn't get any pressure to fit in smaller than 
that for quite a while. But I've heard of some people having use cases 
for thousands if not millions of Linux VMs on a single server and 
they're looking at 10MB VMs or smaller for their application.

> But the kernel complexity you introduce with this series stays with us! It will be 
> an additional cost added to many scheduler commits going forward. It's an added 
> cost for all the other usecases.

OK, let's talk about that a bit. How isn't sched/core.c with its 7387 
lines not overly complex already? How is my moving of rt related code to 
rt.c and dl related code to dl.c not helping things? Isn't it easier to 
understand the 3500 lines of code in futex.c when half of it i.e. the PI 
specific code is split into a separate file? I ask you.

If you want to pick only those patches for now then please be my guest. 
At lease the first two patches of the series should be mergeable without 
even a doubt.

As to the actual complexity I'm introducing... this is just about not 
compiling some files in and stubbing calls to them out. Isn't that a 
sign of good isolation when you can stub the dl class out with only 9 
insertions and 6 deletions to sched/core.c? I'm not saying the 
complexity is nonexistent here, but just the _ability_ to remove a 
scheduler class enforces code abstractions which should be a good thing 
maintenance wise, no?

> Also, it's not like 20k .text savings will magically enable Linux to fit into 1MB 
> of RAM - it won't. The smallest still practical more or less generic Linux system 
> in existence today is around 16 MB. You can shrink it more, but the effort 
> increases exponentially once you go below a natural minimum size.

Again, I'm not after a tiny-and-generic Linux target. I'm after a 
tiny-and-heavily-tailored Linux subset that shares the same ABI and API 
as the generic Linux. Once you start compiling out pieces of the core 
kernel, it obviously isn't generic anymore, but the potential for size 
reduction becomes much bigger.

Anyway... as I said, you have to agree with the high level goal and 
principle of leveraging the Linux codebase to gather the tiny embedded 
people around it. The tiny embedded community simply will never take 
hold otherwise. . If we cannot agree on that then any other point of 
discussion is moot. In which case I'll simply drop this project entirely 
and move on.


Nicolas

[toc] | [prev] | [next] | [standalone]

#1663083

* Nicolas Pitre <nicolas.pitre@linaro.org> wrote:

> > But the kernel complexity you introduce with this series stays with us! It 
> > will be an additional cost added to many scheduler commits going forward. It's 
> > an added cost for all the other usecases.
> 
> OK, let's talk about that a bit. How isn't sched/core.c with its 7387 
> lines not overly complex already? How is my moving of rt related code to 
> rt.c and dl related code to dl.c not helping things? Isn't it easier to 
> understand the 3500 lines of code in futex.c when half of it i.e. the PI 
> specific code is split into a separate file? I ask you.
> 
> If you want to pick only those patches for now then please be my guest. 
> At lease the first two patches of the series should be mergeable without 
> even a doubt.

That's a strawman argument - I was reacting to the combined effect of your series:

 > > >  23 files changed, 3190 insertions(+), 2897 deletions(-)

A subset of the patches might be fine and note that in fact I already picked a 
patch from your series that made sense, I committed this patch of yours three days 
ago:

  f5832c1998af: sched/core: Omit building stop_sched_class when !SMP

I'll pick others as well as long as they don't complicate the code. Please send a 
revised series that only does unambiguous complexity reduction/cleanups.

Thanks,

	Ingo

[toc] | [prev] | [next] | [standalone]

#1663119

On Sun, 11 Jun 2017, Ingo Molnar wrote:

> 
> * Nicolas Pitre <nicolas.pitre@linaro.org> wrote:
> 
> > If you want to pick only those patches for now then please be my guest. 
> > At least the first two patches of the series should be mergeable without 
> > even a doubt.
> 
> That's a strawman argument - I was reacting to the combined effect of your series:
> 
>  > > >  23 files changed, 3190 insertions(+), 2897 deletions(-)

As I mentioned, the bulk of that count comes from moving rt and dl code 
out of sched/core.c into their respective .c files:


    sched/deadline: move dl related code out of sched/core.c
    
    ... to sched/deadline.c. This helps making sched/core.c smaller and
    hopefully easier to understand and maintain. This also will help
    configuring the deadline scheduling class out of the kernel build.
    
    Signed-off-by: Nicolas Pitre <nico@linaro.org>

 kernel/sched/core.c     | 335 +----------------------------------------
 kernel/sched/deadline.c | 336 ++++++++++++++++++++++++++++++++++++++++++
 kernel/sched/sched.h    |  14 ++
 3 files changed, 356 insertions(+), 329 deletions(-)


    sched/rt: move rt related code out of sched/core.c
    
    ... to sched/rt.c. This helps making sched/core.c smaller and hopefully
    easier to understand and maintain. This also will make it easier to
    configure the realtime scheduling class out of the kernel build.
    
    Signed-off-by: Nicolas Pitre <nico@linaro.org>

 kernel/sched/core.c  | 315 ---------------------------------------------
 kernel/sched/rt.c    | 310 ++++++++++++++++++++++++++++++++++++++++++++
 kernel/sched/sched.h |   5 +
 3 files changed, 315 insertions(+), 315 deletions(-)

I also untangled the futex code so the PI support is gathered in a file 
of its own:


    futex: make PI support optional
    
    Split out the priority inheritance support to a file of its own
    to make futex.c easier to understand and, hopefully, to maintain.
    This also makes it possible to compile out the PI support when RT
    task support is not available.
    
    Signed-off-by: Nicolas Pitre <nico@linaro.org>

 include/linux/futex.h |    7 +-
 init/Kconfig          |    7 +-
 kernel/futex.c        | 2829 ++++++++++---------------------------------
 kernel/futex_pi.c     | 1563 ++++++++++++++++++++++++
 4 files changed, 2233 insertions(+), 2173 deletions(-)

Granted I made a mistake in this last description above. It should have 
said "RT mutex support" instead of "RT task support". But those 3 
patches are making the code easier to understand I'd say.

> A subset of the patches might be fine and note that in fact I already picked a 
> patch from your series that made sense, I committed this patch of yours three days 
> ago:
> 
>   f5832c1998af: sched/core: Omit building stop_sched_class when !SMP

Good. That was patch #2/8.  Why did you skip over #1/8 "cpuset/sched: 
cpuset makes sense for SMP only"? It is the same kind of simple cleanup 
as the one you did apply.

> I'll pick others as well as long as they don't complicate the code. Please send a 
> revised series that only does unambiguous complexity reduction/cleanups.

Tell me from the above which patches would qualify and I'll repost them.


Nicolas

[toc] | [prev] | [next] | [standalone]

#1663084

* Nicolas Pitre <nicolas.pitre@linaro.org> wrote:

> > With the stroke of a pen from the CFO: "yes, we can spend more on our next 
> > hardware design!" the problem goes away, overnight, and nobody will look back at 
> > the hardware hack that had only 1MB of RAM.
> 
> Of course hobbyists can already get a Raspberry Pi Zero and run a full 
> featured Linux distro on it... for a mere 5 bucks. That comes with 512MB 
> of RAM so my patches certainly don't make a difference there.

Note that those mere 5 bucks are probably 50 cents or less in bulk. Perfectly fine 
economics for many types of 'throw away IoT hardware' products.

> But that's not that simple.  First there is a fundamental constraint 
> which is power consumption. If you want your device to run for months 
> (some will hope years) from the same tiny battery then you just cannot 
> afford SDRAM. So we're talking static RAM here. And to keep costs down 
> because you want to give away your thingies by the millions for free it 
> usually means single-chip designs with on-chip sub-megabyte static RAM.  
> And in that field the 256KB mark is located towards the high end of the 
> spectrum.  Many IPv6-capable chips available today have less than that.
> 
> And the thing is: people already manage to do a awful lot of stuff in 
> such a constrained device. Some probably did a good job of it, but most 
> of them likely suck and we don't know about their bugs because we have 
> no idea what's running inside.

Ok, let me put it this way: there's no way in hell I see a viable Linux kernel 
running (no matter how stripped down) in 32K or even 64K of RAM. 256K is a stretch 
as well - but that RAM size you claim to be already 'high end', so it probably 
wouldn't be used as a standardized solution anyway...

Today a Linux 'allnoconfig' kernel, i.e. a kernel with no device drivers and no 
filesystems whatsoever and with everything optional turned off (including all 
networking!), is over 2MB large text+data (on x86, which has a compressed 
instruction set - it would possibly be larger on simpler CPUs):

 triton:~/tip> size vmlinux
    text    data     bss     dec  filename
  926056  208624 1215904 2350584  vmlinux

A series that shrinks the .text size of the allnoconfig core Linux kernel from 1MB 
to 9.9MB in isolation is not proof.

There will literally have to be two orders of magnitude more patches than that to 
reach the 32K size envelope, if I (very) optimistically assume that the difficulty 
to shrink code is constant (which it most certainly is not).

I.e. the whole stated premise of the series is wildly not realistic AFAICS, the 
series does not make Linux more usable at all on that category of devices (Linux 
is totally inadequate because it's way too large), it only increases its 
complexity.

But you can prove me wrong: show me a Linux kernel for a real device that fits 
into 32KB of RAM (or even 256 KB) and _then_ I'll consider the cost/benefit 
equation.

Until that happens I consider most forms of additional complexity on the 
non-hardware dependent side of the kernel a net negative.

Thanks,

	Ingo

[toc] | [prev] | [next] | [standalone]

#1663122

On Sun, 11 Jun 2017, Ingo Molnar wrote:

> * Nicolas Pitre <nicolas.pitre@linaro.org> wrote:
> 
> > But that's not that simple.  First there is a fundamental constraint 
> > which is power consumption. If you want your device to run for months 
> > (some will hope years) from the same tiny battery then you just cannot 
> > afford SDRAM. So we're talking static RAM here. And to keep costs down 
> > because you want to give away your thingies by the millions for free it 
> > usually means single-chip designs with on-chip sub-megabyte static RAM.  
> > And in that field the 256KB mark is located towards the high end of the 
> > spectrum.  Many IPv6-capable chips available today have less than that.
> > 
> > And the thing is: people already manage to do a awful lot of stuff in 
> > such a constrained device. Some probably did a good job of it, but most 
> > of them likely suck and we don't know about their bugs because we have 
> > no idea what's running inside.
> 
> Ok, let me put it this way: there's no way in hell I see a viable Linux kernel 
> running (no matter how stripped down) in 32K or even 64K of RAM. 256K is a stretch 
> as well - but that RAM size you claim to be already 'high end', so it probably 
> wouldn't be used as a standardized solution anyway...

I never pretended to make Linux runable in 32KB of RAM. Therefore we 
strongly agree here. I however mentioned that some 32KB chips are IPv6 
capable, just to give you a different perspective given that you're more 
acquainted with multi-gigabyte systems.

And as you did mention Moore's law previously, the fact that 256KB of 
RAM might be somewhat high-end today in that space, that should become 
pretty common in the near future. The test board in front of me has 
384KB of SRAM and bigger ones exist.

> Today a Linux 'allnoconfig' kernel, i.e. a kernel with no device drivers and no 
> filesystems whatsoever and with everything optional turned off (including all 
> networking!), is over 2MB large text+data (on x86, which has a compressed 
> instruction set - it would possibly be larger on simpler CPUs):
> 
>  triton:~/tip> size vmlinux
>     text    data     bss     dec  filename
>   926056  208624 1215904 2350584  vmlinux

On ARM, allnoconfig produces:

   text    data     bss     dec     hex filename
 548144   95480   24252  667876   a30e4 vmlinux

But more realistically, the test system I'm using currently runs the 
kernel XIP from flash, so the text size is an indirect metric. It uses 
external RAM as the 384KB of SRAM still doesn't allow for a successful 
boot. But here's what I get once booted:

/ # free
             total       used       free     shared    buffers     cached
Mem:          7936       1624       6312          0          0        492
-/+ buffers/cache:       1132       6804
/ # uname -a
Linux (none) 4.12.0-rc4-00013-g32352a9367 #35 PREEMPT Sun Jun 11 10:45:02 EDT 2017 armv7ml GNU/Linux

I could make user space XIP from flash as well, but right now it is just 
some initramfs living in RAM.

Obviously you can't use the native Linux networking stack in such small 
systems. But a few IPv6 stacks have been made to work in a few kilobytes 
already.

> A series that shrinks the .text size of the allnoconfig core Linux kernel from 1MB 
> to 9.9MB in isolation is not proof.

I assume you meant 0.9MB.

It is no proof of course. But I'm following the well known and proven 
"release early, release often" mantra here... unless this is no longer 
promoted?

> There will literally have to be two orders of magnitude more patches than that to 
> reach the 32K size envelope, if I (very) optimistically assume that the difficulty 
> to shrink code is constant (which it most certainly is not).

Once again, my goal is _not_ 32KB.

And I don't intend to shrink code. Most of the time I just want to 
_remove_ code. Compiling it out to be precise. The goal of this series 
is all about compiling out code. And to achieve that with the scheduler, 
I simply moved some code to different source files and not including 
those source files in the final build. That keeps the number of #ifdef's 
to a minimum but it makes a big diffstat due to the code movement.

In the TTY layer case, I found out that writing a simplistic parallel 
equivalent that doesn't have to scale to server class systems and 
remains compatible with existing drivers allowed a 6x factor in size 
reduction. The same strategy could be employed with the VFS where any 
kind of file caching doesn't make sense in a tiny system. Don't worry, 
I'm lot looking forward to using BTRFS in 256KB of RAM either.

To give you an idea, here's the size repartition from that booting 
kernel above:

$ size */built-in.o
   text    data     bss     dec     hex filename
 290669   41864    3616  336149   52115 drivers/built-in.o
 173275    1189    5472  179936   2bee0 fs/built-in.o
  10135   14084      84   24303    5eef init/built-in.o
 198624   22000   25160  245784   3c018 kernel/built-in.o
  79064     133      53   79250   13592 lib/built-in.o
  97034    6328    3532  106894   1a18e mm/built-in.o
   2135       0       0    2135     857 security/built-in.o
 146046       0       0  146046   23a7e usr/built-in.o
      0       0       0       0       0 virt/built-in.o

That's without LTO (because with LTO there's no way to size individual 
parts) and without syscall trimming. From previous experiments, LTO 
brings a 20% reduction on the final build size, and LTO with syscall 
trimming together provide about 40% reduction. One nice thing about LTO 
is that part of the 75KB of lib code automatically gets discarded when 
not referenced, etc.  This is not always the case for most of the core 
driver infrastructure despite most of it not being used in my case.

But there are pieces of the kernel that can't automatically be 
eliminated, such as scheduler classes, because the compiler just can't 
tell if they'll be used at run time.

Some "memory hogs" (relatively speaking) might need a tiny version to 
cope with a handful of processes max and a few static drivers. As Alan 
said, wait queues as they are right now consume a lot of memory. But 
since they're well defined and encapsulated already, it is possible to 
provide a light alternative implemented in a way that uses much less 
memory with the side effect of being much less scalable. But scalability 
is not a huge concern when you have only 256KB of RAM.

So it is a combination of strategies that will make the 256KB goal 
possible. And as you can see from the free output above, this is not 
_that_ far off already.

> But you can prove me wrong: show me a Linux kernel for a real device that fits 
> into 32KB of RAM (or even 256 KB) and _then_ I'll consider the cost/benefit 
> equation.

Your insisting on 32KB in this discussion is simply disingenuous.

So you are basically saying that you want me to work another year on 
this project "behind closed doors" and come out with "a final solution" 
before you tell me if my approach is worthy of your consideration? 
Thanks but no thanks. As I said elsewhere, the value in this proposal is 
mainline inclusion in an ongoing process otherwise there is no gain over 
those small OSes out there, and my time is more valuable than that.


Nicolas

[toc] | [prev] | [next] | [standalone]

#1664535

* Nicolas Pitre <nicolas.pitre@linaro.org> wrote:

> > A series that shrinks the .text size of the allnoconfig core Linux kernel from 1MB 
> > to 9.9MB in isolation is not proof.
> 
> I assume you meant 0.9MB.

0.992 MB actually if we apply the ~8k .text savings. 0.9MB would imply 100k of 
savings on an allnoconfig kernel.

> It is no proof of course. But I'm following the well known and proven 
> "release early, release often" mantra here... unless this is no longer 
> promoted?

I'm following that same pattern: I gave you negative review feedback as early as 
possible. Fragmention of the scheduler ABI increases complexity and has knock-on 
costs - and the kernel size reduction for the usecase you cited are still 1-2 
orders of magnitude away from making a practical difference.

> > There will literally have to be two orders of magnitude more patches than that 
> > to reach the 32K size envelope, if I (very) optimistically assume that the 
> > difficulty to shrink code is constant (which it most certainly is not).
> 
> Once again, my goal is _not_ 32KB.
> 
> And I don't intend to shrink code. Most of the time I just want to 
> _remove_ code. Compiling it out to be precise. The goal of this series 
> is all about compiling out code. And to achieve that with the scheduler, 
> I simply moved some code to different source files and not including 
> those source files in the final build. That keeps the number of #ifdef's 
> to a minimum but it makes a big diffstat due to the code movement.

So I'm fine with most of the code movement - let's try this series without any of 
the more controversial bits which should make future arguments easier.

Thanks,

	Ingo

[toc] | [prev] | [next] | [standalone]

#1664790

On Tue, 13 Jun 2017, Ingo Molnar wrote:

> > I simply moved some code to different source files and not including 
> > those source files in the final build. That keeps the number of #ifdef's 
> > to a minimum but it makes a big diffstat due to the code movement.
> 
> So I'm fine with most of the code movement - let's try this series without any of 
> the more controversial bits which should make future arguments easier.

You should then be able to merge patches #1 to #5 already (you already 
have #2) as the more controversial ones are at the end.


Nicolas

[toc] | [prev] | [standalone]

Back to top | Article view | linux.kernel

csiph-web