Skip to contentSkip to conversation

smt-aware rt load balancer

RFC In review Roman Gushchin 3 participants 24 messages Sep 4, 2014 – Sep 21, 2014

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

Hello!

We had an earlier discussion about using real-time policies on modern CPUs
for cpu-bound tasks with "near real-time" execution time expectations (like front-end servers):
https://lkml.org/lkml/2014/4/24/602 .

I sad, that I had a prototype of real-time load balancer (called smart), that performs well in this case.

Now it's ready to be published.

The patch set on top of the 3.10.x branch can be found here:
https://github.com/yandex/smart .

It's stable.
We use them in production for a couple of months on more than thousand machines. We get noticeable performance increase for many projects with different load patterns (up to 10-15% in both RPS and latency).

Any feedback, comments, questions are welcome!

Regards,
Roman

maintainer
#1 lore raw
Quoted 13 lines · Roman Gushchin

Hello!

We had an earlier discussion about using real-time policies on modern CPUs
for cpu-bound tasks with "near real-time" execution time expectations (like front-end servers):
https://lkml.org/lkml/2014/4/24/602 .

I sad, that I had a prototype of real-time load balancer (called smart), that performs well in this case.

Now it's ready to be published.

The patch set on top of the 3.10.x branch can be found here:
https://github.com/yandex/smart .

Quoted 6 lines

It's stable.
We use them in production for a couple of months on more than thousand machines. We get noticeable performance increase for many projects with different load patterns (up to 10-15% in both RPS and latency).

Any feedback, comments, questions are welcome!

-ENOPATCH

#2 lore raw

PATCH 1/19 smart: define and build per-core data structures

In reply to Roman Gushchin

From: Roman Gushchin <[email protected]>

First, this patch introduces the smart_core_data structure. This structure contains following fields:
cpu_core_id - per-cpu core id (first SMT thread on this core) core_next - id of next core on local node core_node_sibling - id of corresponding core on next node core_locked - per-core lock used for synchronizing core selection

The following macros/functions are introduced to access smart data:
cpu_core_id(cpu) - returns core id of CPU smart_data(cpu) - returns per-core smart_data (macro) core_next(cpu) - returns next core id of CPU core_node_sibling(cpu) - returns id of sibling core on next node

Also, this patch introduces build_smart_topology() function, which fills smart_core_data for each cpu.
Below is the illustration of how it's should look on 2-nodes CPU with 8 physical cores and 16 SMT threads.

cpu cpu_core_id

0,8              0
1,9              1
2,10             2
3,11             3
4,12             4
5,13             5
6,14             6
7,15             7

node 0 node 1

------------------------------      ------------------------------
core         0  core         1      core         4  core         5
core_next    1  core_next    2      core_next    5  core_next    6
node_sibling 4  node_sibling 5      node_sibling 0  node_sibling 1
core         2  core         3      core         6  core         7
core_next    3  core_next    0      core_next    7  core_next    4
node_sibling 6  node_sibling 7      node_sibling 2  node_sibling 3
------------------------------      ------------------------------

build_smart_topology() uses sched_domains data and is called each time sched domains are rebuilt. If smart topology is built successfully (checked by check_smart_data()), __smart_initialized static key is set to true.

---
 kernel/sched/core.c  |   3 +
 kernel/sched/rt.c    | 169 +++++++++++++++++++++++++++++++++++++++++++++++++++
 kernel/sched/sched.h |  40 ++++++++++++
 3 files changed, 212 insertions(+)
kernel/sched/core.c +3 -0
index c771f25..14bcdd6 100644
@@ -6671,6 +6671,7 @@ static int init_sched_domains(const struct cpumask *cpu_map)
 		doms_cur = &fallback_doms;
 	cpumask_andnot(doms_cur[0], cpu_map, cpu_isolated_map);
 	err = build_sched_domains(doms_cur[0], NULL);
+	build_smart_topology();
 	register_sched_domain_sysctl();
 
 	return err;
@@ -6791,6 +6792,8 @@ match2:
 
 	register_sched_domain_sysctl();
 
+	build_smart_topology();
+
 	mutex_unlock(&sched_domains_mutex);
 }
 
kernel/sched/rt.c +169 -0

178 lines not on this page · raw message

kernel/sched/sched.h +40 -0
index dfa31d5..357736b 100644
@@ -1378,3 +1378,43 @@ static inline u64 irq_time_read(int cpu)
 }
 #endif /* CONFIG_64BIT */
 #endif /* CONFIG_IRQ_TIME_ACCOUNTING */
+
+#ifdef CONFIG_SMART
+struct smart_core_data {
+	int cpu_core_id;
+
+	/* Per core data, use smart_data macro for access */
+	int core_next;
+	int core_node_sibling;
+	atomic_t core_locked;
+} ____cacheline_aligned_in_smp;
+
+extern struct static_key __smart_initialized;
+
+DECLARE_PER_CPU_SHARED_ALIGNED(struct smart_core_data, smart_core_data);
+
+static inline int cpu_core_id(int cpu)
+{
+	return per_cpu(smart_core_data, cpu).cpu_core_id;
+}
+
+#define smart_data(cpu) per_cpu(smart_core_data, cpu_core_id(cpu))
+
+static inline int core_node_sibling(int cpu)
+{
+	return smart_data(cpu).core_node_sibling;
+}
+
+static inline int next_core(int cpu)
+{
+	return smart_data(cpu).core_next;
+}
+
+void build_smart_topology(void);
+
+#else /* CONFIG_SMART */
+static inline void build_smart_topology(void)
+{
+}
+
+#endif /* CONFIG_SMART */
Signature · 1 line
1.9.3
#3 lore raw

PATCH 2/19 smart: add config option for SMART-related code

From: Roman Gushchin <[email protected]>

All the SMART-related code will use CONFIG_SMART config option.

---
 init/Kconfig | 11 +++++++++++
 1 file changed, 11 insertions(+)
init/Kconfig +11 -0
index 5d6feba..98dd173 100644
@@ -802,6 +802,17 @@ config NUMA_BALANCING
 
 	  This system will be inactive on UMA systems.
 
+config SMART
+	bool "Enable SMART rt scheduler extension"
+	default y
+	depends on SMP
+	help
+	  This option enables SMART (Simultaneous Multithreading-Aware Real-Time)
+	  scheduler exitension. SMART allows efficiently use of real-time
+	  scheduler for runtime tasks on modern multi-cores CPUs with
+	  enabled hyper-threading.
+	  Do not use for hard real-time purposes.
+
 menuconfig CGROUPS
 	boolean "Control Group support"
 	depends on EVENTFD
Signature · 1 line
1.9.3
#4 lore raw

PATCH 3/19 smart: introduce smart_enabled()

In reply to [email protected]

From: Roman Gushchin <[email protected]>

This patch introduces __smart_enabled static key and smart_enabled() function, which will be used to check if smart functionality is enabled.
An ability to turn it on/off will be added later.
By default, __smart_enabled is set to true.

---
 kernel/sched/rt.c    |  4 ++++
 kernel/sched/sched.h | 13 +++++++++++++
 2 files changed, 17 insertions(+)
kernel/sched/rt.c +4 -0
index fed3992..c71b9a3 100644
@@ -11,6 +11,7 @@
 #include <linux/jump_label.h>
 
 struct static_key __smart_initialized = STATIC_KEY_INIT_FALSE;
+struct static_key __smart_enabled = STATIC_KEY_INIT_TRUE;
 DEFINE_MUTEX(smart_mutex);
 
 DEFINE_PER_CPU_SHARED_ALIGNED(struct smart_core_data, smart_core_data);
@@ -2202,6 +2203,9 @@ void build_smart_topology(void)
 	int cpu;
 	int was_initialized;
 
+	if (!static_key_enabled(&__smart_enabled))
+		return;
+
 	mutex_lock(&smart_mutex);
 
 	was_initialized = static_key_enabled(&__smart_initialized);
kernel/sched/sched.h +13 -0
index 357736b..7e26454 100644
@@ -6,6 +6,7 @@
 #include <linux/spinlock.h>
 #include <linux/stop_machine.h>
 #include <linux/tick.h>
+#include <linux/jump_label.h>
 
 #include "cpupri.h"
 #include "cpuacct.h"
@@ -1390,6 +1391,7 @@ struct smart_core_data {
 } ____cacheline_aligned_in_smp;
 
 extern struct static_key __smart_initialized;
+extern struct static_key __smart_enabled;
 
 DECLARE_PER_CPU_SHARED_ALIGNED(struct smart_core_data, smart_core_data);
 
@@ -1400,6 +1402,12 @@ static inline int cpu_core_id(int cpu)
 
 #define smart_data(cpu) per_cpu(smart_core_data, cpu_core_id(cpu))
 
+static inline bool smart_enabled(void)
+{
+	return static_key_false(&__smart_initialized) &&
+		static_key_true(&__smart_enabled);
+}
+
 static inline int core_node_sibling(int cpu)
 {
 	return smart_data(cpu).core_node_sibling;
@@ -1417,4 +1425,9 @@ static inline void build_smart_topology(void)
 {
 }
 
+static inline bool smart_enabled(void)
+{
+	return false;
+}
+
 #endif /* CONFIG_SMART */
Signature · 1 line
1.9.3
#5 lore raw

PATCH 4/19 smart: helper functions for smart_data manipulations

In reply to [email protected]

From: Roman Gushchin <[email protected]>

This commit adds the following helper functions:
acquire_core() - acquires per-core lock
release_core() - releases per-core lock
core_acquired() - checks if per-core lock is acquired core_is_rt_free() - checks if there are no rt tasks on specified core core_rt_free_thread() - finds free SMT thread on specified core find_rt_free_core() - finds free core starting with specified core

---
 kernel/sched/sched.h | 87 ++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 87 insertions(+)
kernel/sched/sched.h +87 -0
index 7e26454..4603096 100644
@@ -1418,6 +1418,89 @@ static inline int next_core(int cpu)
 	return smart_data(cpu).core_next;
 }
 
+static inline int acquire_core(int cpu)
+{
+	return (0 == atomic_cmpxchg(&smart_data(cpu).core_locked, 0, 1));
+}
+
+static inline void release_core(int cpu)
+{
+	atomic_set(&smart_data(cpu).core_locked, 0);
+}
+
+static inline int core_acquired(int cpu)
+{
+	return atomic_read(&smart_data(cpu).core_locked);
+}
+
+static inline int core_is_rt_free(int core)
+{
+	struct rq *rq;
+	int cpu;
+	unsigned int nr_rt;
+	struct task_struct *task;
+
+	for_each_cpu(cpu, topology_thread_cpumask(core)) {
+		rq = cpu_rq(cpu);
+
+		if (rq->rt.rt_throttled)
+			return 0;
+
+		nr_rt = rq->rt.rt_nr_running;
+		if (nr_rt) {
+			if (nr_rt > 1)
+				return 0;
+
+			task = ACCESS_ONCE(rq->curr);
+			if (task->mm)
+				return 0;
+		}
+	}
+
+	return 1;
+}
+
+static inline int core_rt_free_thread(int core)
+{
+	struct rq *rq;
+	int cpu;
+
+	for_each_cpu(cpu, topology_thread_cpumask(core)) {
+		rq = cpu_rq(cpu);
+
+		if (rq->rt.rt_throttled)
+			continue;
+
+		if (!rq->rt.rt_nr_running)
+			return cpu;
+	}
+
+	return -1;
+}
+
+static inline int find_rt_free_core(int start_cpu, struct task_struct *task)
+{
+	int core;
+
+	/* Local cores */
+	core = cpu_core_id(start_cpu);
+	do {
+		if (!core_acquired(core) && core_is_rt_free(core) &&
+		    cpumask_test_cpu(core, tsk_cpus_allowed(task)))
+			return core;
+	} while (core = next_core(core), core != cpu_core_id(start_cpu));
+
+	/* Remote cores */
+	core = core_node_sibling(start_cpu);
+	do {
+		if (!core_acquired(core) && core_is_rt_free(core) &&
+		    cpumask_test_cpu(core, tsk_cpus_allowed(task)))
+			return core;
+	} while (core = next_core(core), core != core_node_sibling(start_cpu));
+
+	return -1;
+}
+
 void build_smart_topology(void);
 
 #else /* CONFIG_SMART */
@@ -1430,4 +1513,8 @@ static inline bool smart_enabled(void)
 	return false;
 }
 
+static inline void release_core(int cpu)
+{
+}
+
 #endif /* CONFIG_SMART */
Signature · 1 line
1.9.3
#6 lore raw

PATCH 5/19 smart: CPU selection logic

In reply to [email protected]

From: Roman Gushchin <[email protected]>

This commit contains the most important code: CPU selection logic. It's implemented by smart_find_lowest_rq() function and some helper functions.

The logic is relatively simple:
1) try to find free core on local node (starting with previous task's CPU)
2) try to find free core on next remote node
3) try to find free SMT thread on local node
4) try to find free SMT thread on remote node
5) try to find SMT thread with minimum rt tasks

If we find free CPU on any step we try to acquire it and if it's successful we stop further processing and quit; otherwise, if CPU is locked, we restart the search.

---
 kernel/sched/rt.c    | 32 ++++++++++++++++++++++++++++++++
 kernel/sched/sched.h | 43 +++++++++++++++++++++++++++++++++++++++++++
 2 files changed, 75 insertions(+)
kernel/sched/rt.c +32 -0
index c71b9a3..805951b 100644
@@ -2286,4 +2286,36 @@ void build_smart_topology(void)
 	mutex_unlock(&smart_mutex);
 }
 
+static int smart_find_lowest_rq(struct task_struct *task, bool wakeup)
+{
+	int prev_cpu = task_cpu(task);
+	int best_cpu;
+	int attempts;
+
+	if (task->nr_cpus_allowed == 1)
+		return -1; /* No other targets possible */
+
+	rcu_read_lock();
+
+
+	for (attempts = 3; attempts; attempts--) {
+		best_cpu = find_rt_free_core(prev_cpu, task);
+		if (best_cpu == -1) {
+			best_cpu = find_rt_best_thread(prev_cpu, task);
+
+			break;
+		}
+
+		if (!acquire_core(best_cpu))
+			continue;
+
+		if (likely(core_is_rt_free(best_cpu)))
+			break;
+
+		release_core(best_cpu);
+	}
+
+	rcu_read_unlock();
+	return best_cpu;
+}
 #endif /* CONFIG_SMART */
kernel/sched/sched.h +43 -0

49 lines not on this page · raw message

Signature · 1 line
1.9.3
#7 lore raw

PATCH 6/19 smart: use CPU selection logic if smart is enabled

In reply to [email protected]

From: Roman Gushchin <[email protected]>

This patch causes rt scheduler to use smart CPU selection logic, if smart_enabled() returns true.

Also, release_core() should be called every time rt-task is actually enqueued on the runqueue or it's clear, that it will never be enqueued on selected CPU.

---
 kernel/sched/core.c |  6 +++++-
 kernel/sched/rt.c   | 29 +++++++++++++++++++++++++++--
 2 files changed, 32 insertions(+), 3 deletions(-)
kernel/sched/core.c +5 -1
index 14bcdd6..832b3d0 100644
@@ -1262,8 +1262,12 @@ int select_task_rq(struct task_struct *p, int sd_flags, int wake_flags)
 	 *   not worry about this generic constraint ]
 	 */
 	if (unlikely(!cpumask_test_cpu(cpu, tsk_cpus_allowed(p)) ||
-		     !cpu_online(cpu)))
+		     !cpu_online(cpu))) {
+		if (smart_enabled() && task_has_rt_policy(p) && cpu >= 0)
+			release_core(cpu);
+
 		cpu = select_fallback_rq(task_cpu(p), p);
+	}
 
 	return cpu;
 }
kernel/sched/rt.c +27 -2
index 805951b..1993c47 100644
@@ -15,6 +15,14 @@ struct static_key __smart_enabled = STATIC_KEY_INIT_TRUE;
 DEFINE_MUTEX(smart_mutex);
 
 DEFINE_PER_CPU_SHARED_ALIGNED(struct smart_core_data, smart_core_data);
+
+static int smart_find_lowest_rq(struct task_struct *task, bool wakeup);
+
+#else /* CONFIG_SMART */
+static inline int smart_find_lowest_rq(struct task_struct *task, bool wakeup)
+{
+	return -1;
+}
 #endif /* CONFIG_SMART */
 
 int sched_rr_timeslice = RR_TIMESLICE;
@@ -1211,6 +1219,7 @@ enqueue_task_rt(struct rq *rq, struct task_struct *p, int flags)
 		enqueue_pushable_task(rq, p);
 
 	inc_nr_running(rq);
+	release_core(cpu_of(rq));
 }
 
 static void dequeue_task_rt(struct rq *rq, struct task_struct *p, int flags)
@@ -1278,6 +1287,13 @@ select_task_rq_rt(struct task_struct *p, int sd_flag, int flags)
 	if (sd_flag != SD_BALANCE_WAKE && sd_flag != SD_BALANCE_FORK)
 		goto out;
 
+	if (smart_enabled()) {
+		int target = smart_find_lowest_rq(p, true);
+		if (likely(target != -1))
+			cpu = target;
+		goto out;
+	}
+
 	rq = cpu_rq(cpu);
 
 	rcu_read_lock();
@@ -1580,10 +1596,17 @@ static struct rq *find_lock_lowest_rq(struct task_struct *task, struct rq *rq)
 	int cpu;
 
 	for (tries = 0; tries < RT_MAX_TRIES; tries++) {
-		cpu = find_lowest_rq(task);
+		if (smart_enabled())
+			cpu = smart_find_lowest_rq(task, false);
+		else
+			cpu = find_lowest_rq(task);
+
+		if ((cpu == -1) || (cpu == rq->cpu)) {
+			if (cpu == rq->cpu)
+				release_core(cpu);
 
-		if ((cpu == -1) || (cpu == rq->cpu))
 			break;
+		}
 
 		lowest_rq = cpu_rq(cpu);
 
@@ -1602,6 +1625,7 @@ static struct rq *find_lock_lowest_rq(struct task_struct *task, struct rq *rq)
 				     !task->on_rq)) {
 
 				double_unlock_balance(rq, lowest_rq);
+				release_core(cpu);
 				lowest_rq = NULL;
 				break;
 			}
@@ -1614,6 +1638,7 @@ static struct rq *find_lock_lowest_rq(struct task_struct *task, struct rq *rq)
 		/* try again */
 		double_unlock_balance(rq, lowest_rq);
 		lowest_rq = NULL;
+		release_core(cpu);
 	}
 
 	return lowest_rq;
Signature · 1 line
1.9.3
#8 lore raw

Re: [PATCH 06/19] smart: use CPU selection logic if smart is enabled

Quoted 4 lines · On Thu 2014-09-04 20:30:52, [email protected] wrote:

From: Roman Gushchin <[email protected]>

This patch causes rt scheduler to use smart CPU selection logic, if smart_enabled() returns true.

SMART is a technology to report HDD health, so while it is cool name, it might be better to use different name to avoid confusion.

Pavel

Quoted 99 lines
kernel/sched/core.c +5 -1
@@ -1262,8 +1262,12 @@ int select_task_rq(struct task_struct *p, int sd_flags, int wake_flags)
 	 *   not worry about this generic constraint ]
 	 */
 	if (unlikely(!cpumask_test_cpu(cpu, tsk_cpus_allowed(p)) ||
-		     !cpu_online(cpu)))
+		     !cpu_online(cpu))) {
+		if (smart_enabled() && task_has_rt_policy(p) && cpu >= 0)
+			release_core(cpu);
+
 		cpu = select_fallback_rq(task_cpu(p), p);
+	}
 
 	return cpu;
 }
kernel/sched/rt.c +27 -2
index 805951b..1993c47 100644
@@ -15,6 +15,14 @@ struct static_key __smart_enabled = STATIC_KEY_INIT_TRUE;
 DEFINE_MUTEX(smart_mutex);
 
 DEFINE_PER_CPU_SHARED_ALIGNED(struct smart_core_data, smart_core_data);
+
+static int smart_find_lowest_rq(struct task_struct *task, bool wakeup);
+
+#else /* CONFIG_SMART */
+static inline int smart_find_lowest_rq(struct task_struct *task, bool wakeup)
+{
+	return -1;
+}
 #endif /* CONFIG_SMART */
 
 int sched_rr_timeslice = RR_TIMESLICE;
@@ -1211,6 +1219,7 @@ enqueue_task_rt(struct rq *rq, struct task_struct *p, int flags)
 		enqueue_pushable_task(rq, p);
 
 	inc_nr_running(rq);
+	release_core(cpu_of(rq));
 }
 
 static void dequeue_task_rt(struct rq *rq, struct task_struct *p, int flags)
@@ -1278,6 +1287,13 @@ select_task_rq_rt(struct task_struct *p, int sd_flag, int flags)
 	if (sd_flag != SD_BALANCE_WAKE && sd_flag != SD_BALANCE_FORK)
 		goto out;
 
+	if (smart_enabled()) {
+		int target = smart_find_lowest_rq(p, true);
+		if (likely(target != -1))
+			cpu = target;
+		goto out;
+	}
+
 	rq = cpu_rq(cpu);
 
 	rcu_read_lock();
@@ -1580,10 +1596,17 @@ static struct rq *find_lock_lowest_rq(struct task_struct *task, struct rq *rq)
 	int cpu;
 
 	for (tries = 0; tries < RT_MAX_TRIES; tries++) {
-		cpu = find_lowest_rq(task);
+		if (smart_enabled())
+			cpu = smart_find_lowest_rq(task, false);
+		else
+			cpu = find_lowest_rq(task);
+
+		if ((cpu == -1) || (cpu == rq->cpu)) {
+			if (cpu == rq->cpu)
+				release_core(cpu);
 
-		if ((cpu == -1) || (cpu == rq->cpu))
 			break;
+		}
 
 		lowest_rq = cpu_rq(cpu);
 
@@ -1602,6 +1625,7 @@ static struct rq *find_lock_lowest_rq(struct task_struct *task, struct rq *rq)
 				     !task->on_rq)) {
 
 				double_unlock_balance(rq, lowest_rq);
+				release_core(cpu);
 				lowest_rq = NULL;
 				break;
 			}
@@ -1614,6 +1638,7 @@ static struct rq *find_lock_lowest_rq(struct task_struct *task, struct rq *rq)
 		/* try again */
 		double_unlock_balance(rq, lowest_rq);
 		lowest_rq = NULL;
+		release_core(cpu);
 	}
 
 	return lowest_rq;
Signature · 7 lines
1.9.3

--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to [email protected]
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/
Signature · 2 lines
(english) http://www.livejournal.com/~pavelmachek
(cesky, pictures) http://atrey.karlin.mff.cuni.cz/~pavel/picture/horses/blog.html
#9 lore raw

PATCH 7/19 smart: balance load between nodes

In reply to [email protected]

From: Roman Gushchin <[email protected]>

Although previously introduced CPU selection logic isn't limited by local node, if the number of rt tasks is smaller than the number of physical cores per node, significant load imbalance can occur.

Modern CPUs tends to scale their's frequency depending on the number of loaded CPUs, so such imbalance can lead to decreased per-CPU performance on the more loaded node.

To solve this problem, this commit adds the following logic to CPU selection logic: if the number of running rt processes on current node is greater than on a remote node and the difference is more than 1/4 of the number of rt tasks on local node, start search with corresponding core on the remote node.

The number of rt tasks on each node is tracked with per-node atomic count.

---
 kernel/sched/rt.c    | 22 ++++++++++++++++++++++
 kernel/sched/sched.h | 29 +++++++++++++++++++++++++++++
 2 files changed, 51 insertions(+)
kernel/sched/rt.c +22 -0
index 1993c47..3202ab4 100644
@@ -15,6 +15,7 @@ struct static_key __smart_enabled = STATIC_KEY_INIT_TRUE;
 DEFINE_MUTEX(smart_mutex);
 
 DEFINE_PER_CPU_SHARED_ALIGNED(struct smart_core_data, smart_core_data);
+struct smart_node_data smart_node_data[MAX_NUMNODES] ____cacheline_aligned_in_smp;
 
 static int smart_find_lowest_rq(struct task_struct *task, bool wakeup);
 
@@ -1218,6 +1219,7 @@ enqueue_task_rt(struct rq *rq, struct task_struct *p, int flags)
 	if (!task_current(rq, p) && p->nr_cpus_allowed > 1)
 		enqueue_pushable_task(rq, p);
 
+	inc_node_running(cpu_of(rq));
 	inc_nr_running(rq);
 	release_core(cpu_of(rq));
 }
@@ -1231,6 +1233,7 @@ static void dequeue_task_rt(struct rq *rq, struct task_struct *p, int flags)
 
 	dequeue_pushable_task(rq, p);
 
+	dec_node_running(cpu_of(rq));
 	dec_nr_running(rq);
 }
 
@@ -2316,12 +2319,31 @@ static int smart_find_lowest_rq(struct task_struct *task, bool wakeup)
 	int prev_cpu = task_cpu(task);
 	int best_cpu;
 	int attempts;
+	int this_node_rt, other_node_rt;
+	int node, this_node;
 
 	if (task->nr_cpus_allowed == 1)
 		return -1; /* No other targets possible */
 
 	rcu_read_lock();
 
+	if (wakeup) {
+		this_node = cpu_to_node(prev_cpu);
+		this_node_rt = node_running(this_node);
+
+		for_each_online_node(node) {
+			if (node == this_node)
+				continue;
+
+			other_node_rt = node_running(node);
+
+			if (this_node_rt > other_node_rt &&
+			    ((this_node_rt - other_node_rt) * 4 > this_node_rt)) {
+				this_node_rt = other_node_rt;
+				prev_cpu = core_node_sibling(prev_cpu);
+			}
+		}
+	}
 
 	for (attempts = 3; attempts; attempts--) {
 		best_cpu = find_rt_free_core(prev_cpu, task);
kernel/sched/sched.h +29 -0
index b662a89..dd539ca 100644
@@ -1390,10 +1390,15 @@ struct smart_core_data {
 	atomic_t core_locked;
 } ____cacheline_aligned_in_smp;
 
+struct smart_node_data {
+	atomic_t nr_rt_running;
+} ____cacheline_aligned_in_smp;
+
 extern struct static_key __smart_initialized;
 extern struct static_key __smart_enabled;
 
 DECLARE_PER_CPU_SHARED_ALIGNED(struct smart_core_data, smart_core_data);
+extern struct smart_node_data smart_node_data[MAX_NUMNODES];
 
 static inline int cpu_core_id(int cpu)
 {
@@ -1401,6 +1406,7 @@ static inline int cpu_core_id(int cpu)
 }
 
 #define smart_data(cpu) per_cpu(smart_core_data, cpu_core_id(cpu))
+#define smart_node_ptr(cpu) smart_node_data[cpu_to_node(cpu)]
 
 static inline bool smart_enabled(void)
 {
@@ -1433,6 +1439,21 @@ static inline int core_acquired(int cpu)
 	return atomic_read(&smart_data(cpu).core_locked);
 }
 
+static inline void inc_node_running(int cpu)
+{
+	atomic_inc(&smart_node_ptr(cpu).nr_rt_running);
+}
+
+static inline void dec_node_running(int cpu)
+{
+	atomic_dec(&smart_node_ptr(cpu).nr_rt_running);
+}
+
+static inline int node_running(int node)
+{
+	return atomic_read(&smart_node_data[node].nr_rt_running);
+}
+
 static inline int core_is_rt_free(int core)
 {
 	struct rq *rq;
@@ -1560,4 +1581,12 @@ static inline void release_core(int cpu)
 {
 }
 
+static inline void inc_node_running(int cpu)
+{
+}
+
+static inline void dec_node_running(int cpu)
+{
+}
+
 #endif /* CONFIG_SMART */
Signature · 1 line
1.9.3
#10 lore raw

PATCH 8/19 smart: smart pull

In reply to [email protected]

From: Roman Gushchin <[email protected]>

This patch implements migration of running rt tasks (aka "smart pull"). The idea is quite simple: if there are free cores, there is no reason to suffer from hyper-threading.

The implementation is a bit trickier:
in pre_schedule() we check, if we are switching from rt task to non-rt (CFS or idle), and if so, we schedule a delayed work. This work searches for a rt tasks, which is the best candidate for migrating (has maximal smart_score). If there is a such candidate, migration occurs. Such migration always occurs from non-first SMT thread on source core to first SMT thread on destination core.

Smart score are counting in the following way: for each running rt task on each scheduler tick we check if there are tasks concurrently running on the same core. If so, we add this number to smart score.

---
 include/linux/sched.h |   3 ++
 kernel/sched/core.c   |  35 +++++++++++++++++
 kernel/sched/rt.c     | 107 +++++++++++++++++++++++++++++++++++++++++++++++++-
 kernel/sched/sched.h  |  10 +++++
 4 files changed, 154 insertions(+), 1 deletion(-)
include/linux/sched.h +3 -0
index 597c8ab..49b7361 100644
@@ -1023,6 +1023,9 @@ struct sched_rt_entity {
 	/* rq "owned" by this entity/group: */
 	struct rt_rq		*my_q;
 #endif
+#ifdef CONFIG_SMART
+	atomic_t smart_score;
+#endif
 };
 
 
kernel/sched/core.c +35 -0
index 832b3d0..9d888610c 100644
@@ -4920,6 +4920,41 @@ static int migration_cpu_stop(void *data)
 	return 0;
 }
 
+#ifdef CONFIG_SMART
+int smart_migrate_task(struct task_struct *p, int prev_cpu,
+		       int dest_cpu)
+{
+	unsigned long flags;
+	struct rq *rq;
+
+	rq = task_rq_lock(p, &flags);
+
+	/* Something has changed? Do nothing. */
+	if (unlikely(prev_cpu != cpu_of(rq)))
+		goto out;
+
+	if (unlikely(!rt_task(p)))
+		goto out;
+
+	if (p->nr_cpus_allowed == 1 ||
+	    !cpumask_test_cpu(dest_cpu, &p->cpus_allowed))
+		goto out;
+
+	if (p->on_rq) {
+		struct migration_arg arg = { p, dest_cpu };
+		/* Need help from migration thread: drop lock and wait. */
+		task_rq_unlock(rq, p, &flags);
+		stop_one_cpu(cpu_of(rq), migration_cpu_stop, &arg);
+		tlb_migrate_finish(p->mm);
+		return 0;
+	}
+out:
+	task_rq_unlock(rq, p, &flags);
+
+	return -1;
+}
+#endif
+
 #ifdef CONFIG_HOTPLUG_CPU
 
 /*
kernel/sched/rt.c +106 -1

149 lines not on this page · raw message

kernel/sched/sched.h +10 -0
index dd539ca..463fdbe 100644
@@ -1565,6 +1565,12 @@ static inline int find_rt_best_thread(int start_cpu, struct task_struct *task)
 	return best_cpu;
 }
 
+static inline void reset_smart_score(struct sched_rt_entity *rt_se)
+{
+	atomic_set(&rt_se->smart_score, 0);
+}
+
+int smart_migrate_task(struct task_struct *p, int prev_cpu, int dest_cpu);
 void build_smart_topology(void);
 
 #else /* CONFIG_SMART */
@@ -1589,4 +1595,8 @@ static inline void dec_node_running(int cpu)
 {
 }
 
+static inline void reset_smart_score(struct sched_rt_entity *rt_se)
+{
+}
+
 #endif /* CONFIG_SMART */
Signature · 1 line
1.9.3
#11 lore raw

PATCH 9/19 smart: throttle CFS tasks by affinning to first SMT thread

In reply to [email protected]

From: Roman Gushchin <[email protected]>

Normal ("CFS") tasks can affect the performance of rt tasks by loading other SMT threads on the same core. If we want to have a guaranteed performance for rt tasks, it's unacceptable.
So, this patch denies enqueuing of CFS tasks if there are running rt tasks on the same core.

---
 kernel/sched/fair.c  | 25 ++++++++++++++++++++-----
 kernel/sched/rt.c    |  4 ++++
 kernel/sched/sched.h | 21 +++++++++++++++++++++
 kernel/sysctl.c      |  4 ++++
 4 files changed, 49 insertions(+), 5 deletions(-)
kernel/sched/fair.c +20 -5
index c7ab8ea..629aa0d 100644
@@ -3285,6 +3285,9 @@ find_idlest_cpu(struct sched_group *group, struct task_struct *p, int this_cpu)
 
 	/* Traverse only the allowed CPUs */
 	for_each_cpu_and(i, sched_group_cpus(group), tsk_cpus_allowed(p)) {
+		if (!cpu_allowed_for_cfs(i))
+			continue;
+
 		load = weighted_cpuload(i);
 
 		if (load < min_load || (load == min_load && i == this_cpu)) {
@@ -3305,13 +3308,14 @@ static int select_idle_sibling(struct task_struct *p, int target)
 	struct sched_group *sg;
 	int i = task_cpu(p);
 
-	if (idle_cpu(target))
+	if (idle_cpu(target) && cpu_allowed_for_cfs(target))
 		return target;
 
 	/*
 	 * If the prevous cpu is cache affine and idle, don't be stupid.
 	 */
-	if (i != target && cpus_share_cache(i, target) && idle_cpu(i))
+	if (i != target && cpus_share_cache(i, target) && idle_cpu(i) &&
+	    cpu_allowed_for_cfs(i))
 		return i;
 
 	/*
@@ -3326,12 +3330,15 @@ static int select_idle_sibling(struct task_struct *p, int target)
 				goto next;
 
 			for_each_cpu(i, sched_group_cpus(sg)) {
-				if (i == target || !idle_cpu(i))
+				if (i == target || !idle_cpu(i) ||
+				    !cpu_allowed_for_cfs(i))
 					goto next;
 			}
 
 			target = cpumask_first_and(sched_group_cpus(sg),
 					tsk_cpus_allowed(p));
+			if (!cpu_allowed_for_cfs(target))
+				goto next;
 			goto done;
 next:
 			sg = sg->next;
@@ -3366,7 +3373,8 @@ select_task_rq_fair(struct task_struct *p, int sd_flag, int wake_flags)
 		return prev_cpu;
 
 	if (sd_flag & SD_BALANCE_WAKE) {
-		if (cpumask_test_cpu(cpu, tsk_cpus_allowed(p)))
+		if (cpumask_test_cpu(cpu, tsk_cpus_allowed(p)) &&
+		    cpu_allowed_for_cfs(cpu))
 			want_affine = 1;
 		new_cpu = prev_cpu;
 	}
@@ -3931,6 +3939,9 @@ int can_migrate_task(struct task_struct *p, struct lb_env *env)
 	if (throttled_lb_pair(task_group(p), env->src_cpu, env->dst_cpu))
 		return 0;
 
+	if (!cpu_allowed_for_cfs(env->dst_cpu))
+		return 0;
+
 	if (!cpumask_test_cpu(env->dst_cpu, tsk_cpus_allowed(p))) {
 		int cpu;
 
@@ -5191,7 +5202,8 @@ more_balance:
 			 * moved to this_cpu
 			 */
 			if (!cpumask_test_cpu(this_cpu,
-					tsk_cpus_allowed(busiest->curr))) {
+					tsk_cpus_allowed(busiest->curr)) ||
+			    !cpu_allowed_for_cfs(this_cpu)) {
 				raw_spin_unlock_irqrestore(&busiest->lock,
 							    flags);
 				env.flags |= LBF_ALL_PINNED;
@@ -5270,6 +5282,9 @@ void idle_balance(int this_cpu, struct rq *this_rq)
 
 	this_rq->idle_stamp = this_rq->clock;
 
+	if (!cpu_allowed_for_cfs(this_cpu))
+		return;
+
 	if (this_rq->avg_idle < sysctl_sched_migration_cost)
 		return;
 
kernel/sched/rt.c +4 -0
index 7ef0fd0..8621443 100644
@@ -1436,7 +1436,11 @@ static struct task_struct *_pick_next_task_rt(struct rq *rq)
 	if (!rt_rq->rt_nr_running)
 		return NULL;
 
+#ifdef CONFIG_SMART
+	if (rt_rq_throttled(rt_rq) && rq->cfs.h_nr_running)
+#else
 	if (rt_rq_throttled(rt_rq))
+#endif
 		return NULL;
 
 	do {
kernel/sched/sched.h +21 -0
index 463fdbe..c7c1cdc 100644
@@ -1396,6 +1396,7 @@ struct smart_node_data {
 
 extern struct static_key __smart_initialized;
 extern struct static_key __smart_enabled;
+extern struct static_key smart_cfs_throttle;
 
 DECLARE_PER_CPU_SHARED_ALIGNED(struct smart_core_data, smart_core_data);
 extern struct smart_node_data smart_node_data[MAX_NUMNODES];
@@ -1454,6 +1455,21 @@ static inline int node_running(int node)
 	return atomic_read(&smart_node_data[node].nr_rt_running);
 }
 
+static inline bool cpu_allowed_for_cfs(int cpu)
+{
+	struct rq *rq;
+	int core = cpu_core_id(cpu);
+
+	if (!smart_enabled() || !static_key_true(&smart_cfs_throttle))
+		return true;
+
+	if (cpu == core)
+		return true;
+
+	rq = cpu_rq(core);
+	return (!rq->rt.rt_nr_running || rq->rt.rt_throttled);
+}
+
 static inline int core_is_rt_free(int core)
 {
 	struct rq *rq;
@@ -1599,4 +1615,9 @@ static inline void reset_smart_score(struct sched_rt_entity *rt_se)
 {
 }
 
+static inline bool cpu_allowed_for_cfs(int cpu)
+{
+	return true;
+}
+
 #endif /* CONFIG_SMART */
kernel/sysctl.c +4 -0
index 9469f4c..7ee22ef 100644
@@ -175,6 +175,10 @@ extern int unaligned_dump_stack;
 extern int no_unaligned_warning;
 #endif
 
+#ifdef CONFIG_SMART
+struct static_key smart_cfs_throttle = STATIC_KEY_INIT_TRUE;
+#endif
+
 #ifdef CONFIG_PROC_SYSCTL
 static int proc_do_cad_pid(struct ctl_table *table, int write,
 		  void __user *buffer, size_t *lenp, loff_t *ppos);
Signature · 1 line
1.9.3
#12 lore raw

PATCH 10/19 smart: smart gathering

In reply to [email protected]

From: Roman Gushchin <[email protected]>

Previous patch denies starting new CFS tasks on a core with running rt tasks. The problem still exists if there are already running CFS tasks at the moment rt task starts.
This patch introduces smart gathering - migration of running CFS tasks from all other CPUs to the CPU with rt task.

---
 kernel/sched/core.c  | 98 ++++++++++++++++++++++++++++++++++++++++++++++++++++
 kernel/sched/sched.h | 14 ++++++++
 kernel/sysctl.c      |  1 +
 3 files changed, 113 insertions(+)
kernel/sched/core.c +98 -0
index 9d888610c..5954f48 100644
@@ -2753,6 +2753,8 @@ void scheduler_tick(void)
 	curr->sched_class->task_tick(rq, curr, 0);
 	raw_spin_unlock(&rq->lock);
 
+	smart_tick(cpu);
+
 	perf_event_task_tick();
 
 #ifdef CONFIG_SMP
@@ -4921,6 +4923,97 @@ static int migration_cpu_stop(void *data)
 }
 
 #ifdef CONFIG_SMART
+
+DEFINE_PER_CPU_SHARED_ALIGNED(struct smart_gathering, smart_gathering_data);
+
+static int smart_gathering_cpu_stop(void *data)
+{
+	int this_cpu = smp_processor_id();
+	int dest_cpu = cpu_core_id(this_cpu);
+	struct rq *rq = cpu_rq(this_cpu);
+	struct task_struct *next;
+	struct smart_gathering *sg;
+	unsigned long flags;
+	int ret;
+	int iter;
+
+	WARN_ON(this_cpu == dest_cpu);
+
+	raw_spin_lock_irqsave(&rq->lock, flags);
+	for (iter = 0; iter < rq->cfs.h_nr_running; iter++) {
+		next = fair_sched_class.pick_next_task(rq);
+		if (!next)
+			break;
+		next->sched_class->put_prev_task(rq, next);
+
+		if (!cpumask_test_cpu(dest_cpu, tsk_cpus_allowed(next)) ||
+		    !cpu_online(dest_cpu))
+			break;
+
+		raw_spin_unlock(&rq->lock);
+		ret = __migrate_task(next, this_cpu, dest_cpu);
+		raw_spin_lock(&rq->lock);
+
+		if (!ret)
+			break;
+	}
+	raw_spin_unlock_irqrestore(&rq->lock, flags);
+
+	sg = &smart_gathering_data(this_cpu);
+	spin_lock_irqsave(&sg->lock, flags);
+	WARN_ON(!sg->gather);
+	sg->gather = 0;
+	spin_unlock_irqrestore(&sg->lock, flags);
+
+	return 0;
+}
+
+void smart_tick(int cpu)
+{
+	unsigned long flags;
+	struct smart_gathering *sg;
+	int gather = 0;
+	struct rq *rq;
+	int core;
+	struct task_struct *curr;
+
+	if (idle_cpu(cpu) || !smart_enabled() ||
+	    !static_key_true(&smart_cfs_gather))
+		return;
+
+	rcu_read_lock();
+
+	core = cpu_core_id(cpu);
+	if (cpu != core) {
+		rq = cpu_rq(core);
+		curr = rq->curr;
+		if (rt_task(curr) && curr->mm)
+			gather = 1;
+
+		rq = cpu_rq(cpu);
+		curr = rq->curr;
+		if (rt_task(curr))
+			gather = 0;
+	}
+
+	if (gather) {
+		sg = &smart_gathering_data(cpu);
+
+		spin_lock_irqsave(&sg->lock, flags);
+		if (sg->gather)
+			gather = 0;
+		else
+			sg->gather = 1;
+		spin_unlock_irqrestore(&sg->lock, flags);
+	}
+
+	rcu_read_unlock();
+
+	if (gather)
+		stop_one_cpu_nowait(cpu, smart_gathering_cpu_stop, NULL,
+				    &sg->work);
+}
+
 int smart_migrate_task(struct task_struct *p, int prev_cpu,
 		       int dest_cpu)
 {
@@ -7093,6 +7186,11 @@ void __init sched_init(void)
 #endif
 		init_rq_hrtick(rq);
 		atomic_set(&rq->nr_iowait, 0);
+
+#ifdef CONFIG_SMART
+		spin_lock_init(&smart_gathering_data(i).lock);
+		smart_gathering_data(i).gather = 0;
+#endif
 	}
 
 	set_load_weight(&init_task);
kernel/sched/sched.h +14 -0
index c7c1cdc..80d202e 100644
@@ -1394,11 +1394,19 @@ struct smart_node_data {
 	atomic_t nr_rt_running;
 } ____cacheline_aligned_in_smp;
 
+struct smart_gathering {
+	spinlock_t lock;
+	int gather;
+	struct cpu_stop_work work;
+};
+
 extern struct static_key __smart_initialized;
 extern struct static_key __smart_enabled;
+extern struct static_key smart_cfs_gather;
 extern struct static_key smart_cfs_throttle;
 
 DECLARE_PER_CPU_SHARED_ALIGNED(struct smart_core_data, smart_core_data);
+DECLARE_PER_CPU_SHARED_ALIGNED(struct smart_gathering, smart_gathering_data);
 extern struct smart_node_data smart_node_data[MAX_NUMNODES];
 
 static inline int cpu_core_id(int cpu)
@@ -1408,6 +1416,7 @@ static inline int cpu_core_id(int cpu)
 
 #define smart_data(cpu) per_cpu(smart_core_data, cpu_core_id(cpu))
 #define smart_node_ptr(cpu) smart_node_data[cpu_to_node(cpu)]
+#define smart_gathering_data(cpu) per_cpu(smart_gathering_data, cpu)
 
 static inline bool smart_enabled(void)
 {
@@ -1586,6 +1595,7 @@ static inline void reset_smart_score(struct sched_rt_entity *rt_se)
 	atomic_set(&rt_se->smart_score, 0);
 }
 
+void smart_tick(int cpu);
 int smart_migrate_task(struct task_struct *p, int prev_cpu, int dest_cpu);
 void build_smart_topology(void);
 
@@ -1620,4 +1630,8 @@ static inline bool cpu_allowed_for_cfs(int cpu)
 	return true;
 }
 
+static inline void smart_tick(int cpu)
+{
+}
+
 #endif /* CONFIG_SMART */
kernel/sysctl.c +1 -0
index 7ee22ef..a1e71e9 100644
@@ -176,6 +176,7 @@ extern int no_unaligned_warning;
 #endif
 
 #ifdef CONFIG_SMART
+struct static_key smart_cfs_gather = STATIC_KEY_INIT_TRUE;
 struct static_key smart_cfs_throttle = STATIC_KEY_INIT_TRUE;
 #endif
 
Signature · 1 line
1.9.3
#13 lore raw

PATCH 11/19 smart: smart debug

In reply to [email protected]

From: Roman Gushchin <[email protected]>

This patch introduces debug infrastructure for smart. The infrastructure contains a number of per-cpu counters, smart_event() function to register smart-related events and procfs interface to read and reset these counters.

The following events are counting:
pull - smart pull
balance_local - local cpu selection
balance_remote - remote cpu selection
select_core - free local core selected
select_rcore - free remote core selected
select_thread - free local cpu selected
select_rthread - free remote cpu selected
select_busy - busy cpu selected
select_busy_curr - current busy cpu selected
select_fallback - select_fallback_rq() called
rt_pull - rt push
rt_push - rt pull

---
 init/Kconfig         |  8 +++++
 kernel/sched/core.c  |  3 ++
 kernel/sched/rt.c    | 85 +++++++++++++++++++++++++++++++++++++++++++++++++++-
 kernel/sched/sched.h | 38 +++++++++++++++++++++++
 4 files changed, 133 insertions(+), 1 deletion(-)
init/Kconfig +8 -0
index 98dd173..d936b49 100644
@@ -813,6 +813,14 @@ config SMART
 	  enabled hyper-threading.
 	  Do not use for hard real-time purposes.
 
+config SMART_DEBUG
+	bool "Enable SMART debug features"
+	default y
+	depends on SMART
+	help
+	  This option adds gathering of SMART statistics. It's
+	  available via /proc/smart_stat interface.
+
 menuconfig CGROUPS
 	boolean "Control Group support"
 	depends on EVENTFD
kernel/sched/core.c +3 -0
index 5954f48..c2b988c 100644
@@ -1180,6 +1180,9 @@ static int select_fallback_rq(int cpu, struct task_struct *p)
 	enum { cpuset, possible, fail } state = cpuset;
 	int dest_cpu;
 
+	if (smart_enabled() && task_has_rt_policy(p))
+		smart_event(select_fallback);
+
 	/*
 	 * If the node that the cpu is on has been offlined, cpu_to_node()
 	 * will return -1. There is no cpu on the node, and we should
kernel/sched/rt.c +84 -1

130 lines not on this page · raw message

kernel/sched/sched.h +38 -0
index 80d202e..d450b8f 100644
@@ -1380,6 +1380,38 @@ static inline u64 irq_time_read(int cpu)
 #endif /* CONFIG_64BIT */
 #endif /* CONFIG_IRQ_TIME_ACCOUNTING */
 
+#ifdef CONFIG_SMART_DEBUG
+struct smart_stat {
+	u64 pull;
+	u64 balance_local;
+	u64 balance_remote;
+	u64 select_core;
+	u64 select_rcore;
+	u64 select_thread;
+	u64 select_rthread;
+	u64 select_busy;
+	u64 select_busy_curr;
+	u64 select_fallback;
+	u64 rt_pull;
+	u64 rt_push;
+};
+
+DECLARE_PER_CPU(struct smart_stat, smart_stat);
+#define smart_event(e) do { __get_cpu_var(smart_stat).e++; } while (0)
+#define smart_event_node(prev_cpu, next_cpu, local_event, remote_event) \
+	do {								\
+		if (prev_cpu >= 0 && next_cpu >= 0 &&			\
+		    cpu_to_node(prev_cpu) == cpu_to_node(next_cpu))	\
+			smart_event(local_event);			\
+		else							\
+			smart_event(remote_event);			\
+	} while (0)
+#else
+#define smart_event(e) do { } while (0)
+#define smart_event_node(prev_cpu, next_cpu, local_event, remote_event) \
+	do { } while (0)
+#endif /* CONFIG_SMART_DEBUG */
+
 #ifdef CONFIG_SMART
 struct smart_core_data {
 	int cpu_core_id;
@@ -1417,6 +1449,7 @@ static inline int cpu_core_id(int cpu)
 #define smart_data(cpu) per_cpu(smart_core_data, cpu_core_id(cpu))
 #define smart_node_ptr(cpu) smart_node_data[cpu_to_node(cpu)]
 #define smart_gathering_data(cpu) per_cpu(smart_gathering_data, cpu)
+#define smart_stats(cpu) per_cpu(smart_core_data, cpu_core_id(cpu)).stats
 
 static inline bool smart_enabled(void)
 {
@@ -1587,6 +1620,11 @@ static inline int find_rt_best_thread(int start_cpu, struct task_struct *task)
 	    min_running == cpu_rq(start_cpu)->rt.rt_nr_running)
 		best_cpu = -1;
 
+	if (best_cpu == -1 || best_cpu == start_cpu)
+		smart_event(select_busy_curr);
+	else
+		smart_event(select_busy);
+
 	return best_cpu;
 }
 
Signature · 1 line
1.9.3
#14 lore raw

PATCH 12/19 smart: cgroup interface for smart

In reply to [email protected]

From: Roman Gushchin <[email protected]>

This patch extends cpu cgroup controller to provide convenient interface for using smart.
The interface contains one simple knob: smart. If it's set to 1, SCHED_RR scheduling policy (with priority 10) is assigned to all non-rt tasks in the group. If it's set to 0, scheduling policy of all rt tasks is reset to SCHED_NORMAL.
Global enabling/disabling smart doesn't affect per-cgroup smart knob state, but tasks in the smart cgroup will actually scheduled by CFS if smart is disabled globally. In other words, tasks in a cgroup with smart knob set are scheduled by real-time scheduler only if smart is enabled. If smart is temporarily disabled globally (due to cpu hotplug, for instance), all tasks in smart cgroups will be temporarily scheduled by CFS and than rt scheduling policy will be restored. Such behavior guarantees graceful degradation if something is wrong with smart.

---
 kernel/sched/core.c  | 126 ++++++++++++++++++++++++++++++++++++++++++++++++++-
 kernel/sched/rt.c    |   8 ++++
 kernel/sched/sched.h |   6 +++
 3 files changed, 139 insertions(+), 1 deletion(-)
kernel/sched/core.c +125 -1
index c2b988c..0f25fe0 100644
@@ -7413,6 +7413,10 @@ struct task_group *sched_create_group(struct task_group *parent)
 	if (!alloc_rt_sched_group(tg, parent))
 		goto err;
 
+#ifdef CONFIG_SMART
+	tg->smart = parent->smart;
+#endif
+
 	return tg;
 
 err:
@@ -7877,13 +7881,119 @@ static int cpu_cgroup_can_attach(struct cgroup *cgrp,
 	return 0;
 }
 
+#ifdef CONFIG_SMART
+
+int sched_smart_prio = 10;
+
+static void __update_task_smart(struct task_struct *task,
+				struct cgroup *cgrp)
+{
+	struct task_group *tg;
+	int policy;
+	struct sched_param param;
+
+	if (!task->mm)
+		return;
+
+	tg = cgroup_tg(cgrp);
+
+	if (!rt_task(task) && tg->smart > 0) {
+		policy = SCHED_RR;
+		param.sched_priority = sched_smart_prio;
+	} else if (rt_task(task) && tg->smart <= 0) {
+		policy = SCHED_NORMAL;
+		param.sched_priority = 0;
+	} else
+		return;
+
+	WARN_ON(sched_setscheduler_nocheck(task, policy, &param));
+}
+
+static void update_task_smart(struct task_struct *task,
+			      struct cgroup_scanner *scan)
+{
+	__update_task_smart(task, scan->cg);
+}
+
+static int update_cgrp_smart(struct cgroup *cgrp)
+{
+	struct cgroup_scanner scan;
+
+	scan.cg = cgrp;
+	scan.test_task = NULL;
+	scan.process_task = update_task_smart;
+	scan.heap = NULL;
+
+	return cgroup_scan_tasks(&scan);
+}
+
+static u64 cpu_smart_read(struct cgroup *cgrp, struct cftype *cft)
+{
+	return cgroup_tg(cgrp)->smart == 1 ? 1 : 0;
+}
+
+static int cpu_smart_write(struct cgroup *cgrp, struct cftype *cftype,
+			   u64 enable)
+{
+	struct task_group *tg = cgroup_tg(cgrp);
+
+	if (enable != 0 && enable != 1)
+		return -EINVAL;
+
+	/* Don't allow to enable smart for root cgroup */
+	if (!tg->se[0])
+		return -EINVAL;
+
+	mutex_lock(&smart_mutex);
+	tg->smart = (smart_enabled() ? 1 : -1) * enable;
+	update_cgrp_smart(cgrp);
+	mutex_unlock(&smart_mutex);
+
+	return 0;
+}
+
+static int update_smart_tg(struct task_group *tg, void *data)
+{
+	int ret = 0;
+	int enabled = smart_enabled();
+
+	if (enabled && tg->smart < 0) {
+		tg->smart = 1;
+		ret = update_cgrp_smart(tg->css.cgroup);
+	} else if (!enabled && tg->smart > 0) {
+		tg->smart = -1;
+		ret = update_cgrp_smart(tg->css.cgroup);
+	}
+
+	return ret;
+}
+
+int smart_update_globally(void)
+{
+	int ret;
+
+	rcu_read_lock();
+	ret = walk_tg_tree(update_smart_tg, tg_nop, NULL);
+	rcu_read_unlock();
+
+	return ret;
+}
+#else /* CONFIG_SMART */
+static void __update_task_smart(struct task_struct *task,
+				struct cgroup *cgrp)
+{
+}
+#endif  /* CONFIG_SMART */
+
 static void cpu_cgroup_attach(struct cgroup *cgrp,
 			      struct cgroup_taskset *tset)
 {
 	struct task_struct *task;
 
-	cgroup_taskset_for_each(task, cgrp, tset)
+	cgroup_taskset_for_each(task, cgrp, tset) {
 		sched_move_task(task);
+		__update_task_smart(task, cgrp);
+	}
 }
 
 static void
@@ -8214,6 +8324,13 @@ static struct cftype cpu_files[] = {
 		.write_u64 = cpu_rt_period_write_uint,
 	},
 #endif
+#ifdef CONFIG_SMART
+	{
+		.name = "smart",
+		.read_u64 = cpu_smart_read,
+		.write_u64 = cpu_smart_write,
+	},
+#endif
 	{ }	/* terminate */
 };
 
@@ -8231,6 +8348,13 @@ struct cgroup_subsys cpu_cgroup_subsys = {
 	.early_init	= 1,
 };
 
+#else /* CONFIG_CGROUP_SCHED */
+#ifdef CONFIG_SMART
+int smart_update_globally(void)
+{
+	return 0;
+}
+#endif
 #endif	/* CONFIG_CGROUP_SCHED */
 
 void dump_cpu_task(int cpu)
kernel/sched/rt.c +8 -0
index 14acd51..a3fd83c 100644
@@ -2405,6 +2405,14 @@ void build_smart_topology(void)
 	if (!check_smart_data()) {
 		printk(KERN_INFO "smart: enabled\n");
 		static_key_slow_inc(&__smart_initialized);
+		if (!was_initialized) {
+			smart_update_globally();
+			printk(KERN_INFO "smart: enabled globally\n");
+		}
+	} else if (was_initialized) {
+		printk(KERN_ALERT "smart: can't build smart topology\n");
+		smart_update_globally();
+		printk(KERN_ALERT "smart: disabled globally\n");
 	}
 
 	rcu_read_unlock();
kernel/sched/sched.h +6 -0
index d450b8f..6ab02dd 100644
@@ -165,6 +165,10 @@ struct task_group {
 #endif
 
 	struct cfs_bandwidth cfs_bandwidth;
+
+#ifdef CONFIG_SMART
+	int smart;
+#endif
 };
 
 #ifdef CONFIG_FAIR_GROUP_SCHED
@@ -1434,6 +1438,7 @@ struct smart_gathering {
 
 extern struct static_key __smart_initialized;
 extern struct static_key __smart_enabled;
+extern struct mutex smart_mutex;
 extern struct static_key smart_cfs_gather;
 extern struct static_key smart_cfs_throttle;
 
@@ -1636,6 +1641,7 @@ static inline void reset_smart_score(struct sched_rt_entity *rt_se)
 void smart_tick(int cpu);
 int smart_migrate_task(struct task_struct *p, int prev_cpu, int dest_cpu);
 void build_smart_topology(void);
+int smart_update_globally(void);
 
 #else /* CONFIG_SMART */
 static inline void build_smart_topology(void)
Signature · 1 line
1.9.3
#15 lore raw

PATCH 13/19 smart: nosmart boot option

In reply to [email protected]

From: Roman Gushchin <[email protected]>

This patch introduces nosmart boot option, that is intended to disable smart globally at boot time.

---
 kernel/sched/rt.c | 7 +++++++
 1 file changed, 7 insertions(+)
kernel/sched/rt.c +7 -0
index a3fd83c..ff7751a 100644
@@ -2319,6 +2319,13 @@ static int cpu_with_number(int number, cpumask_t *mask)
 	return -1;
 }
 
+static int __init nosmart_setup(char *str)
+{
+	static_key_slow_dec(&__smart_enabled);
+	return 0;
+}
+early_param("nosmart", nosmart_setup);
+
 void build_smart_topology(void)
 {
 	int cpu;
Signature · 1 line
1.9.3
#16 lore raw

PATCH 14/19 smart: smart-related sysctl's

In reply to [email protected]

From: Roman Gushchin <[email protected]>

This patch introduces sysctl interface for smart configuration (default values are given in brackets):
sched_smart_enable (1) - enable/disable smart globally sched_smart_prio (10) - rt priority of tasks in a cgroup with smart set sched_smart_gathering (1) - enable/disable smart gathering sched_smart_throttle (1) - enable/disable throttling of CFS tasks

---
 kernel/sched/rt.c | 76 +++++++++++++++++++++++++++++++++++++++++++++++++++++++
 kernel/sysctl.c   | 39 ++++++++++++++++++++++++++++
 2 files changed, 115 insertions(+)
kernel/sched/rt.c +76 -0
index ff7751a..21ffe09 100644
@@ -2247,6 +2247,82 @@ void print_rt_stats(struct seq_file *m, int cpu)
 #endif /* CONFIG_SCHED_DEBUG */
 
 #ifdef CONFIG_SMART
+int proc_smart_enable(struct ctl_table *table, int write,
+		      void __user *buffer, size_t *lenp, loff_t *ppos)
+{
+	int enable = static_key_enabled(&__smart_enabled);
+	int ret;
+
+	build_smart_topology();
+
+	mutex_lock(&smart_mutex);
+
+	if (write && !static_key_false(&__smart_initialized)) {
+		ret = -EBUSY;
+		goto exit;
+	}
+
+	table->data = &enable;
+	ret = proc_dointvec(table, write, buffer, lenp, ppos);
+	if (ret)
+		goto exit;
+
+	if (write) {
+		if (enable && !static_key_enabled(&__smart_enabled)) {
+			static_key_slow_inc(&__smart_enabled);
+			smart_update_globally();
+		}
+
+		if (!enable && static_key_enabled(&__smart_enabled)) {
+			static_key_slow_dec(&__smart_enabled);
+			smart_update_globally();
+		}
+	}
+
+exit:
+	mutex_unlock(&smart_mutex);
+
+	return ret;
+}
+
+int proc_smart_static_key(struct ctl_table *table, int write,
+			  void __user *buffer, size_t *lenp, loff_t *ppos)
+{
+	struct static_key *key;
+	int enable;
+	int ret;
+	static DEFINE_MUTEX(mutex);
+
+	mutex_lock(&mutex);
+
+	key = table->data;
+	enable = static_key_enabled(key);
+
+	if (write && !static_key_false(&__smart_initialized)) {
+		ret = -EBUSY;
+		goto exit;
+	}
+
+	table->data = &enable;
+	ret = proc_dointvec(table, write, buffer, lenp, ppos);
+	if (ret)
+		goto exit;
+
+	if (write) {
+		if (enable && !static_key_enabled(key))
+			static_key_slow_inc(key);
+
+		if (!enable && static_key_enabled(key))
+			static_key_slow_dec(key);
+	}
+
+exit:
+	table->data = key;
+	mutex_unlock(&mutex);
+
+	return ret;
+}
+
 int check_smart_data(void)
 {
 	int cpu, core;
kernel/sysctl.c +39 -0
index a1e71e9..27eb548 100644
@@ -128,6 +128,7 @@ static int __maybe_unused one = 1;
 static int __maybe_unused two = 2;
 static int __maybe_unused three = 3;
 static unsigned long one_ul = 1;
+static int ninety_eight = 98;
 static int one_hundred = 100;
 #ifdef CONFIG_PRINTK
 static int ten_thousand = 10000;
@@ -178,6 +179,13 @@ extern int no_unaligned_warning;
 #ifdef CONFIG_SMART
 struct static_key smart_cfs_gather = STATIC_KEY_INIT_TRUE;
 struct static_key smart_cfs_throttle = STATIC_KEY_INIT_TRUE;
+
+extern int sched_smart_prio;
+
+int proc_smart_static_key(struct ctl_table *table, int write,
+			  void __user *buffer, size_t *lenp, loff_t *ppos);
+int proc_smart_enable(struct ctl_table *table, int write,
+		      void __user *buffer, size_t *lenp, loff_t *ppos);
 #endif
 
 #ifdef CONFIG_PROC_SYSCTL
@@ -446,6 +454,37 @@ static struct ctl_table kern_table[] = {
 		.extra1		= &one,
 	},
 #endif
+#ifdef CONFIG_SMART
+	{
+		.procname	= "sched_smart_enable",
+		.maxlen		= sizeof(int),
+		.mode		= 0644,
+		.proc_handler	= proc_smart_enable,
+	},
+	{
+		.procname	= "sched_smart_prio",
+		.data		= &sched_smart_prio,
+		.maxlen		= sizeof(int),
+		.mode		= 0644,
+		.proc_handler	= proc_dointvec_minmax,
+		.extra1		= &one,
+		.extra2		= &ninety_eight,
+	},
+	{
+		.procname	= "sched_smart_gathering",
+		.data		= &smart_cfs_gather,
+		.maxlen		= sizeof(int),
+		.mode		= 0644,
+		.proc_handler	= proc_smart_static_key,
+	},
+	{
+		.procname	= "sched_smart_throttle",
+		.data		= &smart_cfs_throttle,
+		.maxlen		= sizeof(int),
+		.mode		= 0644,
+		.proc_handler	= proc_smart_static_key,
+	},
+#endif
 #ifdef CONFIG_PROVE_LOCKING
 	{
 		.procname	= "prove_locking",
Signature · 1 line
1.9.3
#17 lore raw

PATCH 15/19 smart: decrease default rt_period/rt_runtime values

In reply to [email protected]

From: Roman Gushchin <[email protected]>

By default, rt_period is 1s and rt_runtime is 0.95s. These values are to high to achieve acceptable system responsibility under high rt load. Decrease it to 100ms and 99ms respectively.

---
 kernel/sched/core.c | 15 +++++++++++----
 1 file changed, 11 insertions(+), 4 deletions(-)
kernel/sched/core.c +11 -4
index 0f25fe0..a1b116e 100644
@@ -282,19 +282,26 @@ const_debug unsigned int sysctl_sched_nr_migrate = 32;
  */
 const_debug unsigned int sysctl_sched_time_avg = MSEC_PER_SEC;
 
+#ifdef CONFIG_SMART
+#define DEFAULT_SCHED_RT_PERIOD 100000
+#define DEFAULT_SCHED_RT_RUNTIME 99000
+
+#else
+#define DEFAULT_SCHED_RT_PERIOD 1000000
+#define DEFAULT_SCHED_RT_RUNTIME 950000
+#endif
+
 /*
  * period over which we measure -rt task cpu usage in us.
- * default: 1s
  */
-unsigned int sysctl_sched_rt_period = 1000000;
+unsigned int sysctl_sched_rt_period = DEFAULT_SCHED_RT_PERIOD;
 
 __read_mostly int scheduler_running;
 
 /*
  * part of the period that we allow rt tasks to run in us.
- * default: 0.95s
  */
-int sysctl_sched_rt_runtime = 950000;
+int sysctl_sched_rt_runtime = DEFAULT_SCHED_RT_RUNTIME;
 
 
 
Signature · 1 line
1.9.3
#18 lore raw

PATCH 16/19 smart: change default RR timeslice to 5ms

In reply to [email protected]

From: Roman Gushchin <[email protected]>

By default, SCHED_RR timeslice is 100ms. Change it to 5ms to achieve better responsibility.

---
 include/linux/sched/rt.h | 4 ++++
 1 file changed, 4 insertions(+)
include/linux/sched/rt.h +4 -0
index 440434d..988eae8 100644
@@ -59,6 +59,10 @@ extern void normalize_rt_tasks(void);
  * default timeslice is 100 msecs (used only for SCHED_RR tasks).
  * Timeslices get refilled after they expire.
  */
+#ifdef CONFIG_SMART
+#define RR_TIMESLICE		(5 * HZ / 1000)
+#else
 #define RR_TIMESLICE		(100 * HZ / 1000)
+#endif
 
 #endif /* _SCHED_RT_H */
Signature · 1 line
1.9.3
#19 lore raw

PATCH 17/19 smart: disable RT runtime sharing

In reply to [email protected]

From: Roman Gushchin <[email protected]>

This patch disables runtime sharing for rt tasks (RT_RUNTIME_SHARE). It's necessary to guarantee that CFS tasks (including system threads like rcu workers) will get time slice regularly on each cpu even when system is heavily loaded with rt tasks.

---
 kernel/sched/features.h | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)
kernel/sched/features.h +1 -1
index 99399f8..0945d38 100644
@@ -57,7 +57,7 @@ SCHED_FEAT(NONTASK_POWER, true)
 SCHED_FEAT(TTWU_QUEUE, true)
 
 SCHED_FEAT(FORCE_SD_OVERLAP, false)
-SCHED_FEAT(RT_RUNTIME_SHARE, true)
+SCHED_FEAT(RT_RUNTIME_SHARE, false)
 SCHED_FEAT(LB_MIN, false)
 
 /*
Signature · 1 line
1.9.3
#20 lore raw

PATCH 18/19 hrtimers: calculate expires_next after all timers are executed

In reply to [email protected]

From: Stanislav Fomichev <[email protected]>

I think I'm hitting particularly subtle issue with NOHZ_IDLE kernel.

The sequence is as follows:
- CPU enters idle, we disable tick
- hrtimer interrupt fires (for hrtimer_wakeup)
- for clock base #1 (REALTIME) we wake up SCHED_RT thread and start RT period timer (from start_rt_bandwidth) for clock base #0 (MONOTONIC)
- because we already checked expiry time for clock base #0
we end up programming wrong wake up time (minutes, from tick_sched_timer)
- then, we exit idle loop and restart tick;
but because tick_sched_timer is not leftmost (the leftmost one is RT period timer) we don't program it

So in the end, I see working CPU without tick interrupt. This eventually leads to RCU stall on that CPU: rcu_gp_kthread is not woken up because there is no tick (this is the reason I started digging this up).

The proposed fix runs expired timers first and only then tries to find next expiry time for all clocks.

---
 include/linux/hrtimer.h |  2 ++
 kernel/hrtimer.c        | 41 +++++++++++++++++++++++++++++++----------
 2 files changed, 33 insertions(+), 10 deletions(-)
include/linux/hrtimer.h +2 -0
index d19a5c2..520a671 100644
@@ -141,6 +141,7 @@ struct hrtimer_sleeper {
  * @get_time:		function to retrieve the current time of the clock
  * @softirq_time:	the time when running the hrtimer queue in the softirq
  * @offset:		offset of this clock to the monotonic base
+ * @next:		time of the next event on this clock base
  */
 struct hrtimer_clock_base {
 	struct hrtimer_cpu_base	*cpu_base;
@@ -151,6 +152,7 @@ struct hrtimer_clock_base {
 	ktime_t			(*get_time)(void);
 	ktime_t			softirq_time;
 	ktime_t			offset;
+	ktime_t			next;
 };
 
 enum  hrtimer_base_type {
kernel/hrtimer.c +31 -10

84 lines not on this page · raw message

Signature · 1 line
1.9.3
#21 lore raw

PATCH 19/19 smart: add description to the README file

In reply to [email protected]

From: Roman Gushchin <[email protected]>

---
 README | 56 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 56 insertions(+)
README +56 -0
index a24ec89..c8af02d 100644
@@ -1,3 +1,59 @@
+        SMART (Simultaneous Multithreading-Aware Real-Time)
+
+This commit series adds SMT awareness to Linux RT scheduler.
+
+SMART is aimed at realtime CPU-bound applications which run for a
+short period of time (tens of milliseconds) and expect no interruption
+(basically anything that is facing user and should finish execution as
+quickly as possible).
+
+On our memory-hot search clusters with thousands of machines we see
+10-15% more RPS compared to CFS. Most profit is gained when machine
+load is around 50%.
+
+While we aim for full CPU utilization with SMART, some care is still
+taken about CFS tasks, because it's crucial to be able to ssh on a fully
+loaded machine.
+
+Linux realtime scheduler uses cpupri structure to distribute tasks
+among CPU cores which doesn't take topology into account and thus can
+make very poor scheduling decisions. SMART scheduler completely abandons
+cpupri mechanism and tries to balance RT load between NUMA nodes and
+doesn't place (if possible) tasks on adjacent SMT threads of a single core.
+
+Among other features are:
+- SMART pull: if all SMT threads of a single core execute RT tasks we
+  migrate them whenever free core becomes available
+- CFS throttling: if some core has RT tasks running, we don't enqueue
+  CFS tasks on the other SMT threads of this core
+- SMART gathering: we migrate running CFS tasks from all SMT threads
+  of a core that don't have RT tasks, to the thread that has
+
+Usage:
+
+SMART is just an improvement on classic Linux realtime scheduler, thus
+all tasks that have SCHED_FIFO or SCHED_RR policy use SMART. From the
+command line it's possible to manipulate scheduler's policy using chrt
+command.
+
+Also, we provide cpu.smart knob to the cpu cgroup which sets scheduler
+policy of all tasks in the cgroup to SCHED_RR.
+
+
+When not to use SMART (you still can use it, but don't expect any profit):
+- target application is not bursty and its execution takes second(s)
+- CPU utilization of target machine approaches 100%
+- target application is true real-time application and you do care
+  about latency measured in microseconds
+
+
+Copyright (c) 2013-2014, Yandex LLC
+
+Authors: Roman Gushchin ([email protected]),
+	 Stanislav Fomichev ([email protected])
+
+--------------------------------------------------------------------------------
+
         Linux kernel release 3.x <http://kernel.org/>
 
 These are the release notes for Linux version 3.  Read them carefully,
Signature · 1 line
1.9.3
maintainer
#22 lore raw
In reply to Roman Gushchin

No, we're not going to merge a second rt balancer. If you want to change it change the one that is there. But it needs to remain a valid _Real_Time_ balancer at all times.

#23 lore raw

I'm not pretending to merge it now (and that why I sent a link to repository instead of patches), but, probably, there are guys here, who can try it and save a bit of hardware.

Regards,
Roman

04.09.2014, 20:49, "Peter Zijlstra" <[email protected]>:

Quoted 3 lines

No, we're not going to merge a second rt balancer. If you want to change it change the one that is there. But it needs to remain a valid _Real_Time_ balancer at all times.