[PATCH 0/5] BT scheduling class

[PATCH 0/5] BT scheduling class

[xiaoggchen]

From: chen xiaoguang <xiaoggchen@tencent.com>

This patch set introduces a new scheduler, we name it BT scheduler
for the moment.

First let me introduce the background why we add a new scheduler.

We have two scenarios in our business:

Scenario 1:
Server application need to response to 10 million requests in one minute
and we must achieve to at least 99.99% successful response to the requests
to keep user experience.

First only server application exists in the system and the success
rate is 99.998% and the average cpu use is only 25%.
To improve the cpu use we run some other applications which are not time
critical tasks in the system. Cgroup's share mechanism is used to restrict
the cpu usage for these kinds of tasks. But there are nearly 5000 requests
in one minute that cannot be handled in time by the server and the success
rate is only 99.94%. Then the BT scheduler is used for the other
applications. After test we found that at most 400 requests failed in one
minute and the success rate are 99.996%. The cpu use increased to 70%.

Test results:
------------------------------------------------------------------------
                     | failure counts/m |success rate  |cpu utilization|
------------------------------------------------------------------------
server load(CFS)     | 200              | 99.998%      | 25%           |
------------------------------------------------------------------------
server load(CFS +    | 5000             | 99.95%       | 55%           |
cgroup.shares=65536) |                  |              |               |
other load(CFS +     |                  |              |               |
cgroup.shares=2)     |                  |              |               |
------------------------------------------------------------------------
server load(CFS)     | 200-400          | 99.996%      | 70%           |
other load(BT)       |                  |              |               |
------------------------------------------------------------------------

Scenario 2:
A service program receives 2000 requests per minute and the average latency
per request is 115 milliseconds. Then we add some other tasks into the
system to share the cpu with the service program. While the other tasks use
the CFS scheduler the average latency increased to 138 milliseconds.
Also dozens of failures increased at the same time.
A server program usually depends on several modules which depend on
additional other modules and so on. So if the latency increased several
milliseconds for one module then the whole latency for the service program
will be amplified times.

Then we use the BT scheduler for the other tasks the average latency
is 122 milliseconds but the failures keep the same. 

Test results:
-----------------------------------------------------------------------
                    | failure counts/m | AVG latency(milliseconds)    |
-----------------------------------------------------------------------
server load(CFS)    |                  | 115                          |
-----------------------------------------------------------------------
server load(CFS)+   | increase 30-50   | 138                          |
other load(CFS)     |                  |                              |
-----------------------------------------------------------------------
server load(CFS)+   | no change        | 122                          |
other load(BT)      |                  |                              |
-----------------------------------------------------------------------

From the above two cases we know that tasks with BT scheduler will not
interfere the normal tasks and will run in cpu spare time. It can be
preempted by normal tasks on demand.

We have millions of servers in our company, so it is very important for
us to improve the cpu use to reduce the costs.

The goal of BT scheduler is to improve the cpu use while do not interfere
the normal tasks.

BT is the abbreviation of batch and we will change the name when we find
a more suitable word.

Tasks with BT schedule class are usually cpu-bound and run in background
and will be preempted by normal tasks such as tasks with CFS schedule class
at any time.

This patch set is just the basic schedule class of BT scheduler.
We will send the complete patches after we finish the full test.

The BT scheduler is similar with the CFS scheduler. We also use the
rb-tree as the run queue to save the runnable tasks. And the vruntime 
concept is also used in the BT scheduler. And the priority of BT scheduler
is from 140 to 179. So now the schedulers in the kernel are as follows:
deadline, RT, CFS, BT and idle.

We can restrict the usage percent of tasks with BT scheduler in per cpu
granularity. We also optimized the load balance algorithm by taking 
cpu's ability of running BT tasks and the waiting times in the run
queue of BT tasks into account. We also add cgroup support for BT
scheduling class.

chen xiaoguang (5):
  sched/BT: add BT scheduling entity
  sched/BT: implement the BT scheduling class
  sched/BT: extend the priority for BT scheduling class
  sched/BT: account the cpu time for BT scheduling class
  sched/BT: add debug information for BT scheduling class

 fs/proc/base.c                 |    3 +-
 include/linux/ioprio.h         |    2 +-
 include/linux/sched.h          |   18 +
 include/linux/sched/bt.h       |   30 ++
 include/linux/sched/prio.h     |    5 +-
 include/uapi/linux/sched.h     |    1 +
 init/init_task.c               |    6 +-
 kernel/delayacct.c             |    2 +-
 kernel/exit.c                  |    3 +-
 kernel/sched/Makefile          |    2 +-
 kernel/sched/bt.c              | 1040 ++++++++++++++++++++++++++++++++++++++++
 kernel/sched/core.c            |   55 ++-
 kernel/sched/cputime.c         |   33 +-
 kernel/sched/debug.c           |   37 ++
 kernel/sched/fair.c            |   31 +-
 kernel/sched/loadavg.c         |    5 +-
 kernel/sched/sched.h           |   40 ++
 kernel/time/posix-cpu-timers.c |    2 +-
 18 files changed, 1272 insertions(+), 43 deletions(-)
 create mode 100644 include/linux/sched/bt.h
 create mode 100644 kernel/sched/bt.c

-- 
1.8.3.1

[PATCH 1/5] sched/BT: add BT scheduling entity

[xiaoggchen]

From: chen xiaoguang <xiaoggchen@tencent.com>

Signed-off-by: Newton Gao <newtongao@tencent.com>
Signed-off-by: Shook Liu <shookliu@tencent.com>
Signed-off-by: Zhiguang Peng <zgpeng@tencent.com>
Signed-off-by: Xiaoguang Chen <xiaoggchen@tencent.com>
---
 include/linux/sched.h      | 18 ++++++++++++++++++
 include/uapi/linux/sched.h |  1 +
 kernel/sched/Makefile      |  2 +-
 kernel/sched/bt.c          | 17 +++++++++++++++++
 kernel/sched/core.c        | 10 ++++++++++
 kernel/sched/sched.h       | 22 ++++++++++++++++++++++
 6 files changed, 69 insertions(+), 1 deletion(-)
 create mode 100644 kernel/sched/bt.c

diff --git a/include/linux/sched.h b/include/linux/sched.h
index 1183741..c0dfbb2 100644
--- a/include/linux/sched.h
+++ b/include/linux/sched.h
@@ -560,6 +560,23 @@ struct sched_dl_entity {
 	struct hrtimer inactive_timer;
 };
 
+struct sched_bt_entity {
+	struct load_weight load;
+	struct rb_node          run_node;
+	unsigned int            on_rq;
+
+	u64                     exec_start;
+	u64                     sum_exec_runtime;
+	u64                     vruntime;
+	u64                     prev_sum_exec_runtime;
+
+	u64                     nr_migrations;
+
+#if defined(CONFIG_SCHEDSTATS) || defined(CONFIG_LATENCYTOP)
+	struct sched_statistics *statistics;
+#endif
+};
+
 union rcu_special {
 	struct {
 		u8			blocked;
@@ -639,6 +656,7 @@ struct task_struct {
 	struct task_group		*sched_task_group;
 #endif
 	struct sched_dl_entity		dl;
+	struct sched_bt_entity		bt;
 
 #ifdef CONFIG_PREEMPT_NOTIFIERS
 	/* List of struct preempt_notifier: */
diff --git a/include/uapi/linux/sched.h b/include/uapi/linux/sched.h
index ed4ee17..410042a 100644
--- a/include/uapi/linux/sched.h
+++ b/include/uapi/linux/sched.h
@@ -41,6 +41,7 @@
 /* SCHED_ISO: reserved but not implemented yet */
 #define SCHED_IDLE		5
 #define SCHED_DEADLINE		6
+#define SCHED_BT		7
 
 /* Can be ORed in to make sure the process is reverted back to SCHED_NORMAL on fork */
 #define SCHED_RESET_ON_FORK     0x40000000
diff --git a/kernel/sched/Makefile b/kernel/sched/Makefile
index 21fb5a5..938e539 100644
--- a/kernel/sched/Makefile
+++ b/kernel/sched/Makefile
@@ -17,7 +17,7 @@ CFLAGS_core.o := $(PROFILING) -fno-omit-frame-pointer
 endif
 
 obj-y += core.o loadavg.o clock.o cputime.o
-obj-y += idle.o fair.o rt.o deadline.o
+obj-y += idle.o fair.o rt.o deadline.o bt.o
 obj-y += wait.o wait_bit.o swait.o completion.o
 
 obj-$(CONFIG_SMP) += cpupri.o cpudeadline.o topology.o stop_task.o pelt.o
diff --git a/kernel/sched/bt.c b/kernel/sched/bt.c
new file mode 100644
index 0000000..56566e6
--- /dev/null
+++ b/kernel/sched/bt.c
@@ -0,0 +1,17 @@
+// SPDX-License-Identifier: GPL-2.0
+/*
+ * Background Scheduling Class
+ */
+
+#include "sched.h"
+
+void init_bt_rq(struct bt_rq *bt_rq)
+{
+	bt_rq->tasks_timeline = RB_ROOT;
+	bt_rq->min_vruntime = (u64)(-(1LL << 20));
+#ifndef CONFIG_64BIT
+	bt_rq->min_vruntime_copy = bt_rq->min_vruntime;
+#endif
+}
+
+
diff --git a/kernel/sched/core.c b/kernel/sched/core.c
index 874c427..3eb4723 100644
--- a/kernel/sched/core.c
+++ b/kernel/sched/core.c
@@ -2138,6 +2138,13 @@ static void __sched_fork(unsigned long clone_flags, struct task_struct *p)
 	p->se.vruntime			= 0;
 	INIT_LIST_HEAD(&p->se.group_node);
 
+	p->bt.on_rq			= 0;
+	p->bt.exec_start		= 0;
+	p->bt.sum_exec_runtime		= 0;
+	p->bt.prev_sum_exec_runtime	= 0;
+	p->bt.nr_migrations		= 0;
+	p->bt.vruntime			= 0;
+
 #ifdef CONFIG_FAIR_GROUP_SCHED
 	p->se.cfs_rq			= NULL;
 #endif
@@ -2145,6 +2152,7 @@ static void __sched_fork(unsigned long clone_flags, struct task_struct *p)
 #ifdef CONFIG_SCHEDSTATS
 	/* Even if schedstat is disabled, there should not be garbage */
 	memset(&p->se.statistics, 0, sizeof(p->se.statistics));
+	p->bt.statistics = &p->se.statistics;
 #endif
 
 	RB_CLEAR_NODE(&p->dl.rb_node);
@@ -5974,6 +5982,7 @@ void __init sched_init(void)
 		init_cfs_rq(&rq->cfs);
 		init_rt_rq(&rq->rt);
 		init_dl_rq(&rq->dl);
+		init_bt_rq(&rq->bt);
 #ifdef CONFIG_FAIR_GROUP_SCHED
 		root_task_group.shares = ROOT_TASK_GROUP_LOAD;
 		INIT_LIST_HEAD(&rq->leaf_cfs_rq_list);
@@ -6186,6 +6195,7 @@ void normalize_rt_tasks(void)
 			continue;
 
 		p->se.exec_start = 0;
+		p->bt.exec_start = 0;
 		schedstat_set(p->se.statistics.wait_start,  0);
 		schedstat_set(p->se.statistics.sleep_start, 0);
 		schedstat_set(p->se.statistics.block_start, 0);
diff --git a/kernel/sched/sched.h b/kernel/sched/sched.h
index b52ed1a..320c80d 100644
--- a/kernel/sched/sched.h
+++ b/kernel/sched/sched.h
@@ -331,6 +331,7 @@ bool __dl_overflow(struct dl_bw *dl_b, int cpus, u64 old_bw, u64 new_bw)
 
 struct cfs_rq;
 struct rt_rq;
+struct bt_rq;
 
 extern struct list_head task_groups;
 
@@ -576,6 +577,25 @@ struct cfs_rq {
 #endif /* CONFIG_FAIR_GROUP_SCHED */
 };
 
+struct bt_rq {
+	struct load_weight load;
+	unsigned int bt_nr_running;
+	unsigned long nr_uninterruptible;
+
+	u64 exec_clock;
+	u64 min_vruntime;
+#ifndef CONFIG_64BIT
+	u64 min_vruntime_copy;
+#endif
+#ifdef CONFIG_SCHED_DEBUG
+	unsigned int            nr_spread_over;
+#endif
+	struct rb_root tasks_timeline;
+	struct rb_node *rb_leftmost;
+
+	struct sched_bt_entity *curr, *next;
+};
+
 static inline int rt_bandwidth_enabled(void)
 {
 	return sysctl_sched_rt_runtime >= 0;
@@ -838,6 +858,7 @@ struct rq {
 	struct cfs_rq		cfs;
 	struct rt_rq		rt;
 	struct dl_rq		dl;
+	struct bt_rq		bt;
 
 #ifdef CONFIG_FAIR_GROUP_SCHED
 	/* list of leaf cfs_rq on this CPU: */
@@ -2107,6 +2128,7 @@ static inline void double_rq_unlock(struct rq *rq1, struct rq *rq2)
 extern void init_cfs_rq(struct cfs_rq *cfs_rq);
 extern void init_rt_rq(struct rt_rq *rt_rq);
 extern void init_dl_rq(struct dl_rq *dl_rq);
+extern void init_bt_rq(struct bt_rq *bt_rq);
 
 extern void cfs_bandwidth_usage_inc(void);
 extern void cfs_bandwidth_usage_dec(void);
-- 
1.8.3.1

[PATCH 2/5] sched/BT: implement the BT scheduling class

[xiaoggchen]

From: chen xiaoguang <xiaoggchen@tencent.com>

Signed-off-by: Newton Gao <newtongao@tencent.com>
Signed-off-by: Shook Liu <shookliu@tencent.com>
Signed-off-by: Zhiguang Peng <zgpeng@tencent.com>
Signed-off-by: Xiaoguang Chen <xiaoggchen@tencent.com>
---
 kernel/sched/bt.c    | 1012 ++++++++++++++++++++++++++++++++++++++++++++++++++
 kernel/sched/fair.c  |    4 +-
 kernel/sched/sched.h |    5 +-
 3 files changed, 1018 insertions(+), 3 deletions(-)

diff --git a/kernel/sched/bt.c b/kernel/sched/bt.c
index 56566e6..87eb04f 100644
--- a/kernel/sched/bt.c
+++ b/kernel/sched/bt.c
@@ -5,6 +5,8 @@
 
 #include "sched.h"
 
+#include <trace/events/sched.h>
+
 void init_bt_rq(struct bt_rq *bt_rq)
 {
 	bt_rq->tasks_timeline = RB_ROOT;
@@ -14,4 +16,1014 @@ void init_bt_rq(struct bt_rq *bt_rq)
 #endif
 }
 
+static inline struct bt_rq *task_bt_rq(struct task_struct *p)
+{
+	return &task_rq(p)->bt;
+}
+
+static inline struct task_struct *bt_task_of(struct sched_bt_entity *bt_se)
+{
+	return container_of(bt_se, struct task_struct, bt);
+}
+
+static inline struct bt_rq *bt_rq_of(struct sched_bt_entity *bt_se)
+{
+	struct task_struct *p = bt_task_of(bt_se);
+	struct rq *rq = task_rq(p);
+
+	return &rq->bt;
+}
+
+static inline struct rq *rq_of_bt_rq(struct bt_rq *bt_rq)
+{
+	return container_of(bt_rq, struct rq, bt);
+}
+
+static u64 __calc_delta(u64 delta_exec, unsigned long weight,
+		struct load_weight *lw);
+
+/*
+ * delta /= w
+ */
+static inline unsigned long
+calc_delta_bt(unsigned long delta, struct sched_bt_entity *bt_se)
+{
+	if (unlikely(bt_se->load.weight != NICE_0_LOAD))
+		delta = __calc_delta(delta, NICE_0_LOAD, &bt_se->load);
+
+	return delta;
+}
+
+static inline void update_load_add(struct load_weight *lw, unsigned long inc)
+{
+	lw->weight += inc;
+	lw->inv_weight = 0;
+}
+
+/*
+ * The idea is to set a period in which each task runs once.
+ *
+ * When there are too many tasks (sched_nr_latency) we have to stretch
+ * this period because otherwise the slices get too small.
+ *
+ * p = (nr <= nl) ? l : l*nr/nl
+ */
+static u64 __sched_period(unsigned long nr_running)
+{
+if (unlikely(nr_running > sched_nr_latency))
+	return nr_running * sysctl_sched_min_granularity;
+else
+	return sysctl_sched_latency;
+}
+
+/*
+ * We calculate the wall-time slice from the period by taking a part
+ * proportional to the weight.
+ *
+ * s = p*P[w/rw]
+ */
+static u64 sched_bt_slice(struct bt_rq *bt_rq, struct sched_bt_entity *se)
+{
+	u64 slice = __sched_period(bt_rq->bt_nr_running + !se->on_rq);
+	struct load_weight *load;
+	struct load_weight lw;
+
+	bt_rq = bt_rq_of(se);
+	load = &bt_rq->load;
+
+	if (unlikely(!se->on_rq)) {
+		lw = bt_rq->load;
+		update_load_add(&lw, se->load.weight);
+		load = &lw;
+	}
+	slice = __calc_delta(slice, se->load.weight, load);
+	return slice;
+}
+
+/*
+ * We calculate the vruntime slice of a to-be-inserted task.
+ *
+ * vs = s/w
+ */
+static u64 sched_bt_vslice(struct bt_rq *bt_rq, struct sched_bt_entity *se)
+{
+	return calc_delta_bt(sched_bt_slice(bt_rq, se), se);
+}
+
+static inline u64 max_vruntime(u64 max_vruntime, u64 vruntime)
+{
+	s64 delta = (s64)(vruntime - max_vruntime);
+
+	if (delta > 0)
+		max_vruntime = vruntime;
+
+	return max_vruntime;
+}
+
+static inline u64 min_vruntime(u64 min_vruntime, u64 vruntime)
+{
+	s64 delta = (s64)(vruntime - min_vruntime);
+
+	if (delta < 0)
+		min_vruntime = vruntime;
+
+	return min_vruntime;
+}
+
+static inline int bt_entity_before(struct sched_bt_entity *a,
+				struct sched_bt_entity *b)
+{
+	return (s64)(a->vruntime - b->vruntime) < 0;
+}
+
+static void
+place_bt_entity(struct bt_rq *bt_rq, struct sched_bt_entity *se, int initial)
+{
+	u64 vruntime = bt_rq->min_vruntime;
+
+	/*
+	 * The 'current' period is already promised to the current tasks,
+	 * however the extra weight of the new task will slow them down a
+	 * little, place the new task so that it fits in the slot that
+	 * stays open at the end.
+	 */
+	if (initial && sched_feat(START_DEBIT))
+		vruntime += sched_bt_vslice(bt_rq, se);
+
+	/* sleeps up to a single latency don't count. */
+	if (!initial) {
+		unsigned long thresh = sysctl_sched_latency;
+
+		/*
+		 * Halve their sleep time's effect, to allow
+		 * for a gentler effect of sleepers:
+		 */
+		if (sched_feat(GENTLE_FAIR_SLEEPERS))
+			thresh >>= 1;
+
+		vruntime -= thresh;
+	}
+
+	/* ensure we never gain time by being placed backwards. */
+	se->vruntime = max_vruntime(se->vruntime, vruntime);
+}
+
+static void update_bt_min_vruntime(struct bt_rq *bt_rq)
+{
+	u64 vruntime = bt_rq->min_vruntime;
+
+	if (bt_rq->curr)
+		vruntime = bt_rq->curr->vruntime;
+
+	if (bt_rq->rb_leftmost) {
+		struct sched_bt_entity *bt_se = rb_entry(bt_rq->rb_leftmost,
+				struct sched_bt_entity,
+				run_node);
+
+		if (!bt_rq->curr)
+			vruntime = bt_se->vruntime;
+		else
+			vruntime = min_vruntime(vruntime, bt_se->vruntime);
+	}
+
+	/* ensure we never gain time by being placed backwards. */
+	bt_rq->min_vruntime = max_vruntime(bt_rq->min_vruntime, vruntime);
+#ifndef CONFIG_64BIT
+	smp_wmb();
+	bt_rq->min_vruntime_copy = bt_rq->min_vruntime;
+#endif
+}
+
+/*
+ * Update the current task's runtime statistics. Skip current tasks that
+ * are not in our scheduling class.
+ */
+static inline void
+__update_curr_bt(struct bt_rq *bt_rq, struct sched_bt_entity *curr,
+		unsigned long delta_exec)
+{
+	unsigned long delta_exec_weighted;
+
+	schedstat_set(curr->statistics->exec_max,
+		max((u64)delta_exec, curr->statistics->exec_max));
+
+	curr->sum_exec_runtime += delta_exec;
+	schedstat_add(bt_rq->exec_clock, delta_exec);
+	delta_exec_weighted = calc_delta_bt(delta_exec, curr);
+
+	curr->vruntime += delta_exec_weighted;
+	update_bt_min_vruntime(bt_rq);
+}
+
+static void
+account_bt_entity_enqueue(struct bt_rq *bt_rq, struct sched_bt_entity *se)
+{
+	update_load_add(&bt_rq->load, se->load.weight);
+	bt_rq->bt_nr_running++;
+}
+
+static inline void
+update_stats_wait_start_bt(struct bt_rq *bt_rq, struct sched_bt_entity *bt_se)
+{
+	schedstat_set(bt_se->statistics->wait_start, rq_of_bt_rq(bt_rq)->clock);
+}
+
+static void update_stats_enqueue_bt(struct bt_rq *bt_rq,
+				struct sched_bt_entity *se)
+{
+	/*
+	 * Are we enqueueing a waiting task? (for current tasks
+	 * a dequeue/enqueue event is a NOP)
+	 */
+	if (se != bt_rq->curr)
+		update_stats_wait_start_bt(bt_rq, se);
+}
+
+static void update_curr(struct bt_rq *bt_rq)
+{
+	struct sched_bt_entity *curr = bt_rq->curr;
+	u64 now = rq_of_bt_rq(bt_rq)->clock_task;
+	unsigned long delta_exec;
+	struct task_struct *tsk;
+
+	if (unlikely(!curr))
+		return;
+
+	/*
+	 * Get the amount of time the current task was running
+	 * since the last time we changed load (this cannot
+	 * overflow on 32 bits):
+	 */
+	delta_exec = (unsigned long)(now - curr->exec_start);
+	if (!delta_exec)
+		return;
+
+	__update_curr_bt(bt_rq, curr, delta_exec);
+	curr->exec_start = now;
+
+	tsk = bt_task_of(curr);
+	trace_sched_stat_runtime(tsk, delta_exec, curr->vruntime);
+	cpuacct_charge(tsk, delta_exec);
+}
+
+static void __enqueue_bt_entity(struct bt_rq *bt_rq,
+				struct sched_bt_entity *bt_se)
+{
+	struct rb_node **link = &bt_rq->tasks_timeline.rb_node;
+	struct rb_node *parent = NULL;
+	struct sched_bt_entity *entry;
+	int leftmost = 1;
+
+	/*
+	 * Find the right place in the rbtree:
+	 */
+	while (*link) {
+		parent = *link;
+		entry = rb_entry(parent, struct sched_bt_entity, run_node);
+		/*
+		 * We dont care about collisions. Nodes with
+		 * the same key stay together.
+		 */
+		if (bt_entity_before(bt_se, entry)) {
+			link = &parent->rb_left;
+		} else {
+			link = &parent->rb_right;
+			leftmost = 0;
+		}
+	}
+
+	/*
+	 * Maintain a cache of leftmost tree entries (it is frequently
+	 * used):
+	 */
+	if (leftmost)
+		bt_rq->rb_leftmost = &bt_se->run_node;
+
+	rb_link_node(&bt_se->run_node, parent, link);
+	rb_insert_color(&bt_se->run_node, &bt_rq->tasks_timeline);
+}
+
+
+static void
+enqueue_bt_entity(struct bt_rq *bt_rq, struct sched_bt_entity *bt_se, int flags)
+{
+	bool renorm = !(flags && ENQUEUE_WAKEUP) || (flags & ENQUEUE_MIGRATED);
+
+	/*
+	 * Update the normalized vruntime before updating min_vruntime
+	 * through callig update_curr().
+	 */
+	if (renorm && (bt_rq->curr == bt_se))
+		bt_se->vruntime += bt_rq->min_vruntime;
+
+	/*
+	 * Update run-time statistics of the 'current'.
+	 */
+	update_curr(bt_rq);
+	account_bt_entity_enqueue(bt_rq, bt_se);
+
+	if (flags & ENQUEUE_WAKEUP)
+		place_bt_entity(bt_rq, bt_se, 0);
+
+	update_stats_enqueue_bt(bt_rq, bt_se);
+	if (bt_se != bt_rq->curr)
+		__enqueue_bt_entity(bt_rq, bt_se);
+	bt_se->on_rq = 1;
+}
+
+/*
+ * The enqueue_task method is called before nr_running is
+ * increased. Here we update the fair scheduling stats and
+ * then put the task into the rbtree:
+ */
+static void
+enqueue_task_bt(struct rq *rq, struct task_struct *p, int flags)
+{
+	struct bt_rq *bt_rq;
+	struct sched_bt_entity *se = &p->bt;
+
+	if (se->on_rq)
+		return;
+
+	bt_rq = bt_rq_of(se);
+	flags = ENQUEUE_WAKEUP;
+	enqueue_bt_entity(bt_rq, se, flags);
+
+	add_nr_running(rq, 1);
+}
+
+static void
+update_stats_wait_end_bt(struct bt_rq *bt_rq, struct sched_bt_entity *se)
+{
+	schedstat_set(se->statistics->wait_max, max(se->statistics->wait_max,
+		rq_of_bt_rq(bt_rq)->clock - se->statistics->wait_start));
+	schedstat_set(se->statistics->wait_count, se->statistics->wait_count
+			+ 1);
+	schedstat_set(se->statistics->wait_sum, se->statistics->wait_sum +
+		rq_of_bt_rq(bt_rq)->clock - se->statistics->wait_start);
+#ifdef CONFIG_SCHEDSTATS
+	trace_sched_stat_wait(bt_task_of(se),
+	rq_of_bt_rq(bt_rq)->clock - se->statistics->wait_start);
+#endif
+	schedstat_set(se->statistics->wait_start, 0);
+}
+
+static inline void
+update_stats_dequeue_bt(struct bt_rq *bt_rq, struct sched_bt_entity *se)
+{
+	/*
+	 * Mark the end of the wait period if dequeueing a
+	 * waiting task:
+	 */
+	if (se != bt_rq->curr)
+		update_stats_wait_end_bt(bt_rq, se);
+}
+
+static void __clear_buddies_next_bt(struct sched_bt_entity *se)
+{
+	struct bt_rq *bt_rq = bt_rq_of(se);
+
+	bt_rq->next = NULL;
+}
+
+static void __clear_buddies_skip_bt(struct sched_bt_entity *se)
+{
+	struct bt_rq *bt_rq = bt_rq_of(se);
+
+	bt_rq->skip = NULL;
+}
+
+static void set_skip_buddy_bt(struct sched_bt_entity *se)
+{
+	bt_rq_of(se)->skip = se;
+}
+
+static void clear_buddies_bt(struct bt_rq *bt_rq, struct sched_bt_entity *se)
+{
+	if (bt_rq->next == se)
+		__clear_buddies_next_bt(se);
+	if (bt_rq->skip == se)
+		__clear_buddies_skip_bt(se);
+}
+
+static void __dequeue_bt_entity(struct bt_rq *bt_rq,
+				struct sched_bt_entity *bt_se)
+{
+	if (bt_rq->rb_leftmost == &bt_se->run_node) {
+		struct rb_node *next_node;
+
+		next_node = rb_next(&bt_se->run_node);
+		bt_rq->rb_leftmost = next_node;
+	}
+	rb_erase(&bt_se->run_node, &bt_rq->tasks_timeline);
+}
+
+static inline void update_load_sub(struct load_weight *lw, unsigned long dec)
+{
+	lw->weight -= dec;
+	lw->inv_weight = 0;
+}
+
+static void
+account_bt_entity_dequeue(struct bt_rq *bt_rq, struct sched_bt_entity *se)
+{
+	update_load_sub(&bt_rq->load, se->load.weight);
+	bt_rq->bt_nr_running--;
+}
+
+static void
+dequeue_bt_entity(struct bt_rq *bt_rq, struct sched_bt_entity *se, int flags)
+{
+	struct task_struct *tsk = bt_task_of(se);
+	/*
+	 * Update run-time statistics of the 'current'.
+	 */
+	update_curr(bt_rq);
+
+	update_stats_dequeue_bt(bt_rq, se);
+	if (flags & DEQUEUE_SLEEP) {
+#if defined(CONFIG_SCHEDSTATS) || defined(CONFIG_LATENCYTOP)
+		if (tsk->state & TASK_INTERRUPTIBLE)
+			se->statistics->sleep_start = rq_of_bt_rq(bt_rq)->clock;
+		if (tsk->state & TASK_UNINTERRUPTIBLE)
+			se->statistics->block_start = rq_of_bt_rq(bt_rq)->clock;
+	}
+#endif
+	clear_buddies_bt(bt_rq, se);
+
+	if (se != bt_rq->curr)
+		__dequeue_bt_entity(bt_rq, se);
+	se->on_rq = 0;
+	account_bt_entity_dequeue(bt_rq, se);
+
+	/*
+	 * Normalize the entity after updating the min_vruntime because the
+	 * update can refer to the ->curr item and we need to reflect this
+	 * movement in our normalized position.
+	 */
+	if (!(flags & DEQUEUE_SLEEP))
+		se->vruntime -= bt_rq->min_vruntime;
+
+	update_bt_min_vruntime(bt_rq);
+}
+
+/*
+ * The dequeue_task method is called before nr_running is
+ * decreased. We remove the task from the rbtree and
+ * update the fair scheduling stats:
+ */
+static void dequeue_task_bt(struct rq *rq, struct task_struct *p, int flags)
+{
+	struct bt_rq *bt_rq;
+	struct sched_bt_entity *se = &p->bt;
+
+	bt_rq = bt_rq_of(se);
+	flags = DEQUEUE_SLEEP;
+	dequeue_bt_entity(bt_rq, se, flags);
+
+	bt_rq->bt_nr_running--;
+
+	sub_nr_running(rq, 1);
+}
+
+static void update_curr_bt(struct rq *rq)
+{
+	update_curr(&rq->bt);
+}
+
+/*
+ * sched_yield() is very simple
+ *
+ * The magic of dealing with the ->skip buddy is in pick_next_entity.
+ */
+static void yield_task_bt(struct rq *rq)
+{
+	struct task_struct *curr = rq->curr;
+	struct bt_rq *bt_rq = task_bt_rq(curr);
+	struct sched_bt_entity *se = &curr->bt;
+
+	/*
+	 * Are we the only task in the tree?
+	 */
+	if (unlikely(rq->nr_running == 1))
+		return;
+
+	clear_buddies_bt(bt_rq, se);
+	update_rq_clock(rq);
+	/*
+	 * Update run-time statistics of the 'current'.
+	 */
+	update_curr(bt_rq);
+	rq_clock_skip_update(rq);
+	set_skip_buddy_bt(se);
+}
+
+struct sched_bt_entity *__pick_first_bt_entity(struct bt_rq *bt_rq)
+{
+	struct rb_node *left = bt_rq->rb_leftmost;
+
+	if (!left)
+		return NULL;
+
+	return rb_entry(left, struct sched_bt_entity, run_node);
+}
+
+
+#define WMULT_CONST    (~0U)
+#define WMULT_SHIFT    32
+
+static void __update_inv_weight(struct load_weight *lw)
+{
+	unsigned long w;
+
+	if (likely(lw->inv_weight))
+		return;
+
+	w = scale_load_down(lw->weight);
+
+	if (BITS_PER_LONG > 32 && unlikely(w >= WMULT_CONST))
+		lw->inv_weight = 1;
+	else if (unlikely(!w))
+		lw->inv_weight = WMULT_CONST;
+	else
+		lw->inv_weight = WMULT_CONST / w;
+}
+
+/*
+ * delta_exec * weight / lw.weight
+ *   OR
+ * (delta_exec * (weight * lw->inv_weight)) >> WMULT_SHIFT
+ *
+ * Either weight := NICE_0_LOAD and lw \e sched_prio_to_wmult[], in which case
+ * we're guaranteed shift stays positive because inv_weight is guaranteed to
+ * fit 32 bits, and NICE_0_LOAD gives another 10 bits; therefore shift >= 22.
+ *
+ * Or, weight =< lw.weight (because lw.weight is the runqueue weight), thus
+ * weight/lw.weight <= 1, and therefore our shift will also be positive.
+ */
+static u64 __calc_delta(u64 delta_exec, unsigned long weight,
+			struct load_weight *lw)
+{
+	u64 fact = scale_load_down(weight);
+	int shift = WMULT_SHIFT;
+
+	__update_inv_weight(lw);
+
+	if (unlikely(fact >> 32)) {
+		while (fact >> 32) {
+			fact >>= 1;
+			shift--;
+		}
+	}
+
+	/* hint to use a 32x32->64 mul */
+	fact = (u64)(u32)fact * lw->inv_weight;
+
+	while (fact >> 32) {
+		fact >>= 1;
+		shift--;
+	}
+
+	return mul_u64_u32_shr(delta_exec, fact, shift);
+}
+
+static unsigned long
+wakeup_gran_bt(struct sched_bt_entity *curr, struct sched_bt_entity *se)
+{
+	unsigned long gran = sysctl_sched_wakeup_granularity;
+
+	/*
+	 * Since its curr running now, convert the gran from real-time
+	 * to virtual-time in his units.
+	 *
+	 * By using 'se' instead of 'curr' we penalize light tasks, so
+	 * they get preempted easier. That is, if 'se' < 'curr' then
+	 * the resulting gran will be larger, therefore penalizing the
+	 * lighter, if otoh 'se' > 'curr' then the resulting gran will
+	 * be smaller, again penalizing the lighter task.
+	 *
+	 * This is especially important for buddies when the leftmost
+	 * task is higher priority than the buddy.
+	 */
+	return calc_delta_bt(gran, se);
+}
+
+
+static int
+wakeup_preempt_bt_entity(struct sched_bt_entity *curr,
+			struct sched_bt_entity *se)
+{
+	s64 gran, vdiff = curr->vruntime - se->vruntime;
+
+	if (vdiff <= 0)
+		return -1;
+
+	gran = wakeup_gran_bt(curr, se);
+	if (vdiff > gran)
+		return 1;
+
+	return 0;
+}
+
+/*
+ * Preempt the current task with a newly woken task if needed:
+ */
+static void
+check_preempt_tick_bt(struct bt_rq *bt_rq, struct sched_bt_entity *curr)
+{
+	unsigned long ideal_runtime, delta_exec;
+	struct sched_bt_entity *se;
+	s64 delta;
+
+	ideal_runtime = sched_bt_slice(bt_rq, curr);
+	delta_exec = curr->sum_exec_runtime - curr->prev_sum_exec_runtime;
+	if (delta_exec > ideal_runtime) {
+		resched_curr(rq_of_bt_rq(bt_rq));
+		/*
+		 * The current task ran long enough, ensure it doesn't get
+		 * re-elected due to buddy favours.
+		 */
+		clear_buddies_bt(bt_rq, curr);
+		return;
+	}
+
+	/*
+	 * Ensure that a task that missed wakeup preemption by a
+	 * narrow margin doesn't have to wait for a full slice.
+	 * This also mitigates buddy induced latencies under load.
+	 */
+	if (delta_exec < sysctl_sched_min_granularity)
+		return;
+
+	se = __pick_first_bt_entity(bt_rq);
+	delta = curr->vruntime - se->vruntime;
+
+	if (delta < 0)
+		return;
+
+	if (delta > ideal_runtime)
+		resched_curr(rq_of_bt_rq(bt_rq));
+}
+
+static void set_next_buddy_bt(struct sched_bt_entity *se)
+{
+	if (unlikely(task_has_idle_policy(bt_task_of(se))))
+		return;
+
+	bt_rq_of(se)->next = se;
+}
+
+/*
+ * Preempt the current task with a newly woken task if needed:
+ */
+static void check_preempt_wakeup_bt(struct rq *rq, struct task_struct *p,
+				int wake_flags)
+{
+	struct task_struct *curr = rq->curr;
+	struct sched_bt_entity *se = &curr->bt, *pse = &p->bt;
+	struct bt_rq *bt_rq = task_bt_rq(curr);
+	int scale = bt_rq->bt_nr_running >= sched_nr_latency;
+	int next_buddy_marked = 0;
+
+	if (unlikely(se == pse))
+		return;
+
+	if (sched_feat(NEXT_BUDDY) && scale && !(wake_flags & WF_FORK)) {
+		set_next_buddy_bt(pse);
+		next_buddy_marked = 1;
+	}
+
+	/*
+	 * We can come here with TIF_NEED_RESCHED already set from new task
+	 * wake up path.
+	 *
+	 * Note: this also catches the edge-case of curr being in a throttled
+	 * group (e.g. via set_curr_task), since update_curr() (in the
+	 * enqueue of curr) will have resulted in resched being set.  This
+	 * prevents us from potentially nominating it as a false LAST_BUDDY
+	 * below.
+	 */
+	if (test_tsk_need_resched(curr))
+		return;
+
+	/* BT tasks are by definition preempted by non-bt tasks. */
+	if (likely(p->policy < SCHED_BT))
+		goto preempt;
+
+	if (!sched_feat(WAKEUP_PREEMPTION))
+		return;
+
+	update_curr(bt_rq_of(se));
+	BUG_ON(!pse);
+	if (wakeup_preempt_bt_entity(se, pse) == 1) {
+		/*
+		 * Bias pick_next to pick the sched entity that is
+		 * triggering this preemption.
+		 */
+		if (!next_buddy_marked)
+			set_next_buddy_bt(pse);
+		goto preempt;
+	}
+
+	return;
+
+preempt:
+	resched_curr(rq);
+	/*
+	 * Only set the backward buddy when the current task is still
+	 * on the rq. This can happen when a wakeup gets interleaved
+	 * with schedule on the ->pre_schedule() or idle_balance()
+	 * point, either of which can * drop the rq lock.
+	 *
+	 * Also, during early boot the idle thread is in the fair class,
+	 * for obvious reasons its a bad idea to schedule back to it.
+	 */
+	if (unlikely(!se->on_rq || curr == rq->idle))
+		return;
+}
+
+static struct sched_bt_entity *__pick_next_bt_entity(
+					struct sched_bt_entity *bt_se)
+{
+	struct rb_node *next = rb_next(&bt_se->run_node);
+
+	if (!next)
+		return NULL;
+
+	return rb_entry(next, struct sched_bt_entity, run_node);
+}
+
+/*
+ * We are picking a new current task - update its stats:
+ */
+static inline void
+update_stats_curr_start_bt(struct bt_rq *bt_rq, struct sched_bt_entity *se)
+{
+	/*
+	 * We are starting a new run period:
+	 */
+	se->exec_start = rq_of_bt_rq(bt_rq)->clock_task;
+}
+
+static void
+set_next_bt_entity(struct bt_rq *bt_rq, struct sched_bt_entity *se)
+{
+	/* 'current' is not kept within the tree. */
+	if (se->on_rq) {
+		/*
+		 * Any task has to be enqueued before it get to execute on
+		 * a CPU. So account for the time it spent waiting on the
+		 * runqueue.
+		 */
+		update_stats_wait_end_bt(bt_rq, se);
+		__dequeue_bt_entity(bt_rq, se);
+	}
+
+	update_stats_curr_start_bt(bt_rq, se);
+	bt_rq->curr = se;
+#ifdef CONFIG_SCHEDSTATS
+	/*
+	 * Track our maximum slice length, if the CPU's load is at
+	 * least twice that of our own weight (i.e. dont track it
+	 * when there are only lesser-weight tasks around):
+	 */
+	if (bt_rq->load.weight >= 2*se->load.weight) {
+		se->statistics->slice_max = max(se->statistics->slice_max,
+			se->sum_exec_runtime - se->prev_sum_exec_runtime);
+	}
+#endif
+	se->prev_sum_exec_runtime = se->sum_exec_runtime;
+}
+
+/*
+ * Pick the next process, keeping these things in mind, in this order:
+ * 1) keep things fair between processes/task groups
+ * 2) pick the "next" process, since someone really wants that to run
+ * 3) do not run the "skip" process, if something else is available
+ */
+static struct sched_bt_entity *pick_next_bt_entity(struct bt_rq *bt_rq)
+{
+	struct sched_bt_entity *se = __pick_first_bt_entity(bt_rq);
+	struct sched_bt_entity *left = se;
+
+	/*
+	 * Avoid running the skip buddy, if running something else can
+	 * be done without getting too unfair.
+	 */
+	if (bt_rq->skip == se) {
+		struct sched_bt_entity *second = __pick_next_bt_entity(se);
+
+		if (second && wakeup_preempt_bt_entity(second, left) < 1)
+			se = second;
+	}
+
+	/*
+	 * Someone really wants this to run. If it's not unfair, run it.
+	 */
+	if (bt_rq->next && wakeup_preempt_bt_entity(bt_rq->next, left) < 1)
+		se = bt_rq->next;
+
+	clear_buddies_bt(bt_rq, se);
+
+	return se;
+}
+
+
+static struct task_struct *
+pick_next_task_bt(struct rq *rq, struct task_struct *prev, struct rq_flags *rf)
+{
+	struct task_struct *p;
+	struct bt_rq *bt_rq;
+	struct sched_bt_entity *se;
+
+	bt_rq = &rq->bt;
+
+	if (!bt_rq->bt_nr_running)
+		return NULL;
+
+	put_prev_task(rq, prev);
+
+	se = pick_next_bt_entity(bt_rq);
+	set_next_bt_entity(bt_rq, se);
+
+	p = bt_task_of(se);
+
+	return p;
+}
+
+static void put_prev_bt_entity(struct bt_rq *bt_rq,
+				struct sched_bt_entity *prev)
+{
+	/*
+	 * If still on the runqueue then deactivate_task()
+	 * was not called and update_curr() has to be done:
+	 */
+	if (prev->on_rq)
+		update_curr(bt_rq);
+
+	if (prev->on_rq) {
+		update_stats_wait_start_bt(bt_rq, prev);
+		/* Put 'current' back into the tree. */
+		__enqueue_bt_entity(bt_rq, prev);
+	}
+	bt_rq->curr = NULL;
+}
+
+/*
+ * Account for a descheduled task:
+ */
+static void put_prev_task_bt(struct rq *rq, struct task_struct *prev)
+{
+	struct sched_bt_entity *se = &prev->bt;
+	struct bt_rq *bt_rq;
+
+	bt_rq = bt_rq_of(se);
+	put_prev_bt_entity(bt_rq, se);
+}
+
+#ifdef CONFIG_SMP
+static int
+select_task_rq_bt(struct task_struct *p, int prev_cpu, int sd_flag,
+		int wake_flags)
+{
+	struct sched_domain *tmp;
+	int cpu = smp_processor_id();
+	int new_cpu = cpu;
+
+	if (p->nr_cpus_allowed == 1)
+		return prev_cpu;
+
+	rcu_read_lock();
+	for_each_domain(cpu, tmp) {
+		if (cpumask_test_cpu(cpu, &p->cpus_allowed)) {
+			new_cpu = cpu;
+			break;
+		}
+	}
+	rcu_read_unlock();
+
+	return new_cpu;
+}
+#endif
+/* Account for a task changing its policy or group.
+ *
+ * This routine is mostly called to set bt_rq->curr field when a task
+ * migrates between groups/classes.
+ */
+static void set_curr_task_bt(struct rq *rq)
+{
+	struct sched_bt_entity *se = &rq->curr->bt;
+	struct bt_rq *bt_rq = bt_rq_of(se);
+
+	set_next_bt_entity(bt_rq, se);
+}
+
+static void
+bt_entity_tick(struct bt_rq *bt_rq, struct sched_bt_entity *curr, int queued)
+{
+	/*
+	 * Update run-time statistics of the 'current'.
+	 */
+	update_curr(bt_rq);
+
+#ifdef CONFIG_SCHED_HRTICK
+	/*
+	 * queued ticks are scheduled to match the slice, so don't bother
+	 * validating it and just reschedule.
+	 */
+	if (queued) {
+		resched_curr(rq_of_bt_rq(bt_rq));
+		return;
+	}
+#endif
+
+	if (bt_rq->bt_nr_running > 1)
+		check_preempt_tick_bt(bt_rq, curr);
+}
+
+/*
+ * scheduler tick hitting a task of our scheduling class:
+ */
+static void task_tick_bt(struct rq *rq, struct task_struct *curr, int queued)
+{
+	struct bt_rq *bt_rq;
+	struct sched_bt_entity *se = &curr->bt;
+
+	bt_rq = bt_rq_of(se);
+	bt_entity_tick(bt_rq, se, queued);
+}
+/*
+ * Priority of the task has changed. Check to see if we preempt
+ * the current task.
+ */
+static void
+prio_changed_bt(struct rq *rq, struct task_struct *p, int oldprio)
+{
+	if (!p->bt.on_rq)
+		return;
+
+	/*
+	 * Reschedule if we are currently running on this runqueue and
+	 * our priority decreased, or if we are not currently running on
+	 * this runqueue and our priority is higher than the current's
+	 */
+	if (rq->curr == p) {
+		if (p->prio > oldprio)
+			resched_curr(rq);
+	} else
+		check_preempt_curr(rq, p, 0);
+}
+
+/*
+ * We switched to the sched_fair class.
+ */
+static void switched_to_bt(struct rq *rq, struct task_struct *p)
+{
+	if (!p->bt.on_rq)
+		return;
+	/*
+	 * We were most likely switched from sched_rt, so
+	 * kick off the schedule if running, otherwise just see
+	 * if we can still preempt the current task.
+	 */
+	if (rq->curr == p)
+		resched_curr(rq);
+	else
+		check_preempt_curr(rq, p, 0);
+}
+
+static unsigned int get_rr_interval_bt(struct rq *rq, struct task_struct *task)
+{
+	struct sched_bt_entity *se = &task->bt;
+	unsigned int rr_interval = 0;
+
+	/*
+	 * Time slice is 0 for SCHED_OTHER tasks that are on an otherwise
+	 * idle runqueue:
+	 */
+	if (rq->bt.load.weight)
+		rr_interval = NS_TO_JIFFIES(sched_bt_slice(bt_rq_of(se), se));
+
+	return rr_interval;
+}
+
+const struct sched_class bt_sched_class = {
+	.next                   = &idle_sched_class,
+	.enqueue_task           = enqueue_task_bt,
+	.dequeue_task           = dequeue_task_bt,
+	.yield_task             = yield_task_bt,
+	.check_preempt_curr     = check_preempt_wakeup_bt,
+	.pick_next_task         = pick_next_task_bt,
+	.put_prev_task          = put_prev_task_bt,
+#ifdef CONFIG_SMP
+	.select_task_rq         = select_task_rq_bt,
+	.set_cpus_allowed       = set_cpus_allowed_common,
+#endif
+	.set_curr_task          = set_curr_task_bt,
+	.task_tick              = task_tick_bt,
+	.prio_changed           = prio_changed_bt,
+	.switched_to            = switched_to_bt,
+	.get_rr_interval        = get_rr_interval_bt,
+	.update_curr            = update_curr_bt,
+};
 
diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
index f35930f..5299ce8 100644
--- a/kernel/sched/fair.c
+++ b/kernel/sched/fair.c
@@ -64,7 +64,7 @@
 /*
  * This value is kept at sysctl_sched_latency/sysctl_sched_min_granularity
  */
-static unsigned int sched_nr_latency = 8;
+unsigned int sched_nr_latency = 8;
 
 /*
  * After fork, child runs first. If set to 0 (default) then
@@ -10653,7 +10653,7 @@ static unsigned int get_rr_interval_fair(struct rq *rq, struct task_struct *task
  * All the scheduling class methods:
  */
 const struct sched_class fair_sched_class = {
-	.next			= &idle_sched_class,
+	.next			= &bt_sched_class,
 	.enqueue_task		= enqueue_task_fair,
 	.dequeue_task		= dequeue_task_fair,
 	.yield_task		= yield_task_fair,
diff --git a/kernel/sched/sched.h b/kernel/sched/sched.h
index 320c80d..68007be 100644
--- a/kernel/sched/sched.h
+++ b/kernel/sched/sched.h
@@ -593,7 +593,7 @@ struct bt_rq {
 	struct rb_root tasks_timeline;
 	struct rb_node *rb_leftmost;
 
-	struct sched_bt_entity *curr, *next;
+	struct sched_bt_entity *curr, *next, *skip;
 };
 
 static inline int rt_bandwidth_enabled(void)
@@ -1754,6 +1754,7 @@ static inline void set_curr_task(struct rq *rq, struct task_struct *curr)
 extern const struct sched_class rt_sched_class;
 extern const struct sched_class fair_sched_class;
 extern const struct sched_class idle_sched_class;
+extern const struct sched_class bt_sched_class;
 
 
 #ifdef CONFIG_SMP
@@ -2362,4 +2363,6 @@ static inline bool sched_energy_enabled(void)
 #define perf_domain_span(pd) NULL
 static inline bool sched_energy_enabled(void) { return false; }
 
+extern unsigned int sched_nr_latency;
+
 #endif /* CONFIG_ENERGY_MODEL && CONFIG_CPU_FREQ_GOV_SCHEDUTIL */
-- 
1.8.3.1

[PATCH 3/5] sched/BT: extend the priority for BT scheduling class

[xiaoggchen]

From: chen xiaoguang <xiaoggchen@tencent.com>

The priority of BT scheduler is from 140 to 179.

Signed-off-by: Newton Gao <newtongao@tencent.com>
Signed-off-by: Shook Liu <shookliu@tencent.com>
Signed-off-by: Zhiguang Peng <zgpeng@tencent.com>
Signed-off-by: Xiaoguang Chen <xiaoggchen@tencent.com>
---
 include/linux/ioprio.h     |  2 +-
 include/linux/sched/bt.h   | 30 ++++++++++++++++++++++++++++++
 include/linux/sched/prio.h |  5 ++++-
 init/init_task.c           |  6 +++---
 kernel/sched/core.c        | 15 ++++++++++++---
 kernel/sched/cputime.c     | 26 ++++++++++++++++++++------
 kernel/sched/sched.h       | 12 ++++++++++++
 7 files changed, 82 insertions(+), 14 deletions(-)
 create mode 100644 include/linux/sched/bt.h

diff --git a/include/linux/ioprio.h b/include/linux/ioprio.h
index e9bfe69..3adb9ad 100644
--- a/include/linux/ioprio.h
+++ b/include/linux/ioprio.h
@@ -62,7 +62,7 @@ static inline int task_nice_ioprio(struct task_struct *task)
  */
 static inline int task_nice_ioclass(struct task_struct *task)
 {
-	if (task->policy == SCHED_IDLE)
+	if (task->policy == SCHED_IDLE || task->policy == SCHED_BT)
 		return IOPRIO_CLASS_IDLE;
 	else if (task_is_realtime(task))
 		return IOPRIO_CLASS_RT;
diff --git a/include/linux/sched/bt.h b/include/linux/sched/bt.h
new file mode 100644
index 0000000..5f40600
--- /dev/null
+++ b/include/linux/sched/bt.h
@@ -0,0 +1,30 @@
+/* SPDX-License-Identifier: GPL-2.0 */
+#ifndef _SCHED_BT_H
+#define _SCHED_BT_H
+
+/*
+ * SCHED_BT tasks has 140~179 priorities, reflecting
+ * the fact that any of them has slower prio than RT and
+ * NORMAL/BATCH tasks.
+ */
+#define NICE_TO_BT_PRIO(nice)  (MAX_RT_PRIO + (nice) + 20 + 40)
+#define PRIO_TO_BT_NICE(prio)  ((prio) - MAX_RT_PRIO - 20 - 40)
+static inline int task_bt_nice(const struct task_struct *p)
+{
+	return PRIO_TO_BT_NICE((p)->static_prio);
+}
+
+static inline int bt_prio(int prio)
+{
+	if (unlikely(prio < MAX_PRIO && prio >= MIN_BT_PRIO))
+		return 1;
+	return 0;
+}
+
+static inline int bt_task(struct task_struct *p)
+{
+	return bt_prio(p->prio);
+}
+#endif /* _SCHED_BT_H */
+
+
diff --git a/include/linux/sched/prio.h b/include/linux/sched/prio.h
index 7d64fea..5c36ed2 100644
--- a/include/linux/sched/prio.h
+++ b/include/linux/sched/prio.h
@@ -22,9 +22,12 @@
 #define MAX_USER_RT_PRIO	100
 #define MAX_RT_PRIO		MAX_USER_RT_PRIO
 
-#define MAX_PRIO		(MAX_RT_PRIO + NICE_WIDTH)
+#define MAX_PRIO		(MAX_RT_PRIO + NICE_WIDTH + 40)
 #define DEFAULT_PRIO		(MAX_RT_PRIO + NICE_WIDTH / 2)
 
+#define MIN_BT_PRIO		(MAX_RT_PRIO + 40)
+#define MAX_BT_PRIO		(MAX_PRIO - 1)
+
 /*
  * Convert user-nice values [ -20 ... 0 ... 19 ]
  * to static priority [ MAX_RT_PRIO..MAX_PRIO-1 ],
diff --git a/init/init_task.c b/init/init_task.c
index c70ef65..603ec4f 100644
--- a/init/init_task.c
+++ b/init/init_task.c
@@ -68,9 +68,9 @@ struct task_struct init_task
 	.stack		= init_stack,
 	.usage		= REFCOUNT_INIT(2),
 	.flags		= PF_KTHREAD,
-	.prio		= MAX_PRIO - 20,
-	.static_prio	= MAX_PRIO - 20,
-	.normal_prio	= MAX_PRIO - 20,
+	.prio		= MAX_PRIO - 20 - 40,
+	.static_prio	= MAX_PRIO - 20 - 40,
+	.normal_prio	= MAX_PRIO - 20 - 40,
 	.policy		= SCHED_NORMAL,
 	.cpus_allowed	= CPU_MASK_ALL,
 	.nr_cpus_allowed= NR_CPUS,
diff --git a/kernel/sched/core.c b/kernel/sched/core.c
index 3eb4723..b542c17 100644
--- a/kernel/sched/core.c
+++ b/kernel/sched/core.c
@@ -2312,7 +2312,8 @@ int sched_fork(unsigned long clone_flags, struct task_struct *p)
 	 * Revert to default priority/policy on fork if requested.
 	 */
 	if (unlikely(p->sched_reset_on_fork)) {
-		if (task_has_dl_policy(p) || task_has_rt_policy(p)) {
+		if (task_has_dl_policy(p) || task_has_rt_policy(p) ||
+		    task_has_bt_policy(p)) {
 			p->policy = SCHED_NORMAL;
 			p->static_prio = NICE_TO_PRIO(0);
 			p->rt_priority = 0;
@@ -2333,6 +2334,8 @@ int sched_fork(unsigned long clone_flags, struct task_struct *p)
 		return -EAGAIN;
 	else if (rt_prio(p->prio))
 		p->sched_class = &rt_sched_class;
+	else if (bt_prio(p->prio))
+		p->sched_class = &bt_sched_class;
 	else
 		p->sched_class = &fair_sched_class;
 
@@ -3833,6 +3836,12 @@ void rt_mutex_setprio(struct task_struct *p, struct task_struct *pi_task)
 		if (oldprio < prio)
 			queue_flag |= ENQUEUE_HEAD;
 		p->sched_class = &rt_sched_class;
+	} else if (bt_prio(prio)) {
+		if (dl_prio(oldprio))
+			p->dl.dl_boosted = 0;
+		if (rt_prio(oldprio))
+			p->rt.timeout = 0;
+		p->sched_class = &bt_sched_class;
 	} else {
 		if (dl_prio(oldprio))
 			p->dl.dl_boosted = 0;
@@ -3991,7 +4000,7 @@ int idle_cpu(int cpu)
 {
 	struct rq *rq = cpu_rq(cpu);
 
-	if (rq->curr != rq->idle)
+	if (rq->curr != rq->idle && !bt_prio(rq->curr->prio))
 		return 0;
 
 	if (rq->nr_running)
@@ -6200,7 +6209,7 @@ void normalize_rt_tasks(void)
 		schedstat_set(p->se.statistics.sleep_start, 0);
 		schedstat_set(p->se.statistics.block_start, 0);
 
-		if (!dl_task(p) && !rt_task(p)) {
+		if (!dl_task(p) && !rt_task(p) && !bt_task(p)) {
 			/*
 			 * Renice negative nice level userspace
 			 * tasks back to 0:
diff --git a/kernel/sched/cputime.c b/kernel/sched/cputime.c
index 2305ce8..ca26a04 100644
--- a/kernel/sched/cputime.c
+++ b/kernel/sched/cputime.c
@@ -122,7 +122,10 @@ void account_user_time(struct task_struct *p, u64 cputime)
 	p->utime += cputime;
 	account_group_user_time(p, cputime);
 
-	index = (task_nice(p) > 0) ? CPUTIME_NICE : CPUTIME_USER;
+	if (bt_prio(p->static_prio))
+		index = (task_bt_nice(p) > 0) ? CPUTIME_NICE : CPUTIME_USER;
+	else
+		index = (task_nice(p) > 0) ? CPUTIME_NICE : CPUTIME_USER;
 
 	/* Add user time to cpustat. */
 	task_group_account_field(p, index, cputime);
@@ -146,13 +149,24 @@ void account_guest_time(struct task_struct *p, u64 cputime)
 	p->gtime += cputime;
 
 	/* Add guest time to cpustat. */
-	if (task_nice(p) > 0) {
-		cpustat[CPUTIME_NICE] += cputime;
-		cpustat[CPUTIME_GUEST_NICE] += cputime;
+	if (bt_prio(p->static_prio)) {
+		if (task_bt_nice(p) > 0) {
+			cpustat[CPUTIME_NICE] += cputime;
+			cpustat[CPUTIME_GUEST_NICE] += cputime;
+		} else {
+			cpustat[CPUTIME_USER] += cputime;
+			cpustat[CPUTIME_GUEST] += cputime;
+		}
 	} else {
-		cpustat[CPUTIME_USER] += cputime;
-		cpustat[CPUTIME_GUEST] += cputime;
+		if (task_nice(p) > 0) {
+			cpustat[CPUTIME_NICE] += cputime;
+			cpustat[CPUTIME_GUEST_NICE] += cputime;
+		} else {
+			cpustat[CPUTIME_USER] += cputime;
+			cpustat[CPUTIME_GUEST] += cputime;
+		}
 	}
+
 }
 
 /*
diff --git a/kernel/sched/sched.h b/kernel/sched/sched.h
index 68007be..403eec6 100644
--- a/kernel/sched/sched.h
+++ b/kernel/sched/sched.h
@@ -32,6 +32,7 @@
 #include <linux/sched/user.h>
 #include <linux/sched/wake_q.h>
 #include <linux/sched/xacct.h>
+#include <linux/sched/bt.h>
 
 #include <uapi/linux/sched/types.h>
 
@@ -172,6 +173,12 @@ static inline int dl_policy(int policy)
 {
 	return policy == SCHED_DEADLINE;
 }
+
+static inline int bt_policy(int policy)
+{
+	return policy == SCHED_BT;
+}
+
 static inline bool valid_policy(int policy)
 {
 	return idle_policy(policy) || fair_policy(policy) ||
@@ -193,6 +200,11 @@ static inline int task_has_dl_policy(struct task_struct *p)
 	return dl_policy(p->policy);
 }
 
+static inline int task_has_bt_policy(struct task_struct *p)
+{
+	return bt_policy(p->policy);
+}
+
 #define cap_scale(v, s) ((v)*(s) >> SCHED_CAPACITY_SHIFT)
 
 /*
-- 
1.8.3.1

[PATCH 4/5] sched/BT: account the cpu time for BT scheduling class

[xiaoggchen]

From: chen xiaoguang <xiaoggchen@tencent.com>

Signed-off-by: Newton Gao <newtongao@tencent.com>
Signed-off-by: Shook Liu <shookliu@tencent.com>
Signed-off-by: Zhiguang Peng <zgpeng@tencent.com>
Signed-off-by: Xiaoguang Chen <xiaoggchen@tencent.com>
---
 fs/proc/base.c                 |  3 ++-
 kernel/delayacct.c             |  2 +-
 kernel/exit.c                  |  3 ++-
 kernel/sched/core.c            | 30 +++++++++++++++++++++++-------
 kernel/sched/cputime.c         |  7 ++++---
 kernel/sched/fair.c            | 27 +++++++++++++++++----------
 kernel/sched/loadavg.c         |  5 +++--
 kernel/time/posix-cpu-timers.c |  2 +-
 8 files changed, 53 insertions(+), 26 deletions(-)

diff --git a/fs/proc/base.c b/fs/proc/base.c
index 9c8ca6c..356f2e8 100644
--- a/fs/proc/base.c
+++ b/fs/proc/base.c
@@ -459,7 +459,8 @@ static int proc_pid_schedstat(struct seq_file *m, struct pid_namespace *ns,
 		seq_puts(m, "0 0 0\n");
 	else
 		seq_printf(m, "%llu %llu %lu\n",
-		   (unsigned long long)task->se.sum_exec_runtime,
+		   (unsigned long long)task->se.sum_exec_runtime +
+		   (unsigned long long)task->bt.sum_exec_runtime,
 		   (unsigned long long)task->sched_info.run_delay,
 		   task->sched_info.pcount);
 
diff --git a/kernel/delayacct.c b/kernel/delayacct.c
index 27725754..c8bb8f6 100644
--- a/kernel/delayacct.c
+++ b/kernel/delayacct.c
@@ -106,7 +106,7 @@ int __delayacct_add_tsk(struct taskstats *d, struct task_struct *tsk)
 	 */
 	t1 = tsk->sched_info.pcount;
 	t2 = tsk->sched_info.run_delay;
-	t3 = tsk->se.sum_exec_runtime;
+	t3 = tsk->se.sum_exec_runtime + tsk->bt.sum_exec_runtime;
 
 	d->cpu_count += t1;
 
diff --git a/kernel/exit.c b/kernel/exit.c
index 1803efb..ee5ef46 100644
--- a/kernel/exit.c
+++ b/kernel/exit.c
@@ -152,7 +152,8 @@ static void __exit_signal(struct task_struct *tsk)
 	sig->inblock += task_io_get_inblock(tsk);
 	sig->oublock += task_io_get_oublock(tsk);
 	task_io_accounting_add(&sig->ioac, &tsk->ioac);
-	sig->sum_sched_runtime += tsk->se.sum_exec_runtime;
+	sig->sum_sched_runtime += (tsk->se.sum_exec_runtime +
+				   tsk->bt.sum_exec_runtime);
 	sig->nr_threads--;
 	__unhash_process(tsk, group_dead);
 	write_sequnlock(&sig->stats_lock);
diff --git a/kernel/sched/core.c b/kernel/sched/core.c
index b542c17..e8fbd9e 100644
--- a/kernel/sched/core.c
+++ b/kernel/sched/core.c
@@ -789,9 +789,13 @@ static inline void dequeue_task(struct rq *rq, struct task_struct *p, int flags)
 
 void activate_task(struct rq *rq, struct task_struct *p, int flags)
 {
-	if (task_contributes_to_load(p))
+	if (task_contributes_to_load(p)) {
 		rq->nr_uninterruptible--;
 
+		if (unlikely(p->sched_class == &bt_sched_class))
+			rq->bt.nr_uninterruptible--;
+	}
+
 	enqueue_task(rq, p, flags);
 
 	p->on_rq = TASK_ON_RQ_QUEUED;
@@ -801,9 +805,13 @@ void deactivate_task(struct rq *rq, struct task_struct *p, int flags)
 {
 	p->on_rq = (flags & DEQUEUE_SLEEP) ? 0 : TASK_ON_RQ_MIGRATING;
 
-	if (task_contributes_to_load(p))
+	if (task_contributes_to_load(p)) {
 		rq->nr_uninterruptible++;
 
+		if (unlikely(p->sched_class == &bt_sched_class))
+			rq->bt.nr_uninterruptible++;
+	}
+
 	dequeue_task(rq, p, flags);
 }
 
@@ -1727,9 +1735,13 @@ static void ttwu_do_wakeup(struct rq *rq, struct task_struct *p, int wake_flags,
 	lockdep_assert_held(&rq->lock);
 
 #ifdef CONFIG_SMP
-	if (p->sched_contributes_to_load)
+	if (p->sched_contributes_to_load) {
 		rq->nr_uninterruptible--;
 
+		if (unlikely(p->sched_class == &bt_sched_class))
+			rq->bt.nr_uninterruptible--;
+	}
+
 	if (wake_flags & WF_MIGRATED)
 		en_flags |= ENQUEUE_MIGRATED;
 #endif
@@ -3007,7 +3019,7 @@ unsigned long long task_sched_runtime(struct task_struct *p)
 	 * been accounted, so we're correct here as well.
 	 */
 	if (!p->on_cpu || !task_on_rq_queued(p))
-		return p->se.sum_exec_runtime;
+		return p->se.sum_exec_runtime + p->bt.sum_exec_runtime;
 #endif
 
 	rq = task_rq_lock(p, &rf);
@@ -3021,7 +3033,7 @@ unsigned long long task_sched_runtime(struct task_struct *p)
 		update_rq_clock(rq);
 		p->sched_class->update_curr(rq);
 	}
-	ns = p->se.sum_exec_runtime;
+	ns = p->se.sum_exec_runtime + p->bt.sum_exec_runtime;
 	task_rq_unlock(rq, p, &rf);
 
 	return ns;
@@ -4003,7 +4015,7 @@ int idle_cpu(int cpu)
 	if (rq->curr != rq->idle && !bt_prio(rq->curr->prio))
 		return 0;
 
-	if (rq->nr_running)
+	if (rq->nr_running - rq->bt.bt_nr_running)
 		return 0;
 
 #ifdef CONFIG_SMP
@@ -5383,9 +5395,13 @@ void init_idle(struct task_struct *idle, int cpu)
 
 	__sched_fork(0, idle);
 	idle->state = TASK_RUNNING;
-	idle->se.exec_start = sched_clock();
+	idle->se.exec_start = idle->bt.exec_start = sched_clock();
 	idle->flags |= PF_IDLE;
 
+#if defined(CONFIG_SCHEDSTATS) || defined(CONFIG_LATENCYTOP)
+	idle->bt.statistics = &idle->se.statistics;
+#endif
+
 	kasan_unpoison_task_stack(idle);
 
 #ifdef CONFIG_SMP
diff --git a/kernel/sched/cputime.c b/kernel/sched/cputime.c
index ca26a04..4cba3f2 100644
--- a/kernel/sched/cputime.c
+++ b/kernel/sched/cputime.c
@@ -283,7 +283,7 @@ static inline u64 account_other_time(u64 max)
 #ifdef CONFIG_64BIT
 static inline u64 read_sum_exec_runtime(struct task_struct *t)
 {
-	return t->se.sum_exec_runtime;
+	return t->se.sum_exec_runtime + t->bt.sum_exec_runtime;
 }
 #else
 static u64 read_sum_exec_runtime(struct task_struct *t)
@@ -293,7 +293,7 @@ static u64 read_sum_exec_runtime(struct task_struct *t)
 	struct rq *rq;
 
 	rq = task_rq_lock(t, &rf);
-	ns = t->se.sum_exec_runtime;
+	ns = t->se.sum_exec_runtime + t->bt.sum_exec_runtime;
 	task_rq_unlock(rq, t, &rf);
 
 	return ns;
@@ -677,7 +677,8 @@ void cputime_adjust(struct task_cputime *curr, struct prev_cputime *prev,
 void task_cputime_adjusted(struct task_struct *p, u64 *ut, u64 *st)
 {
 	struct task_cputime cputime = {
-		.sum_exec_runtime = p->se.sum_exec_runtime,
+		.sum_exec_runtime = p->se.sum_exec_runtime +
+				p->bt.sum_exec_runtime,
 	};
 
 	task_cputime(p, &cputime.utime, &cputime.stime);
diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
index 5299ce8..ca08107 100644
--- a/kernel/sched/fair.c
+++ b/kernel/sched/fair.c
@@ -7137,7 +7137,7 @@ static void yield_task_fair(struct rq *rq)
 	/*
 	 * Are we the only task in the tree?
 	 */
-	if (unlikely(rq->nr_running == 1))
+	if (unlikely((rq->nr_running - rq->bt.bt_nr_running) == 1))
 		return;
 
 	clear_buddies(cfs_rq, se);
@@ -7357,7 +7357,9 @@ static int task_hot(struct task_struct *p, struct lb_env *env)
 	/*
 	 * Buddy candidates are cache hot:
 	 */
-	if (sched_feat(CACHE_HOT_BUDDY) && env->dst_rq->nr_running &&
+	if (sched_feat(CACHE_HOT_BUDDY) &&
+		(env->dst_rq->nr_running -
+			env->dst_rq->bt.bt_nr_running) &&
 			(&p->se == cfs_rq_of(&p->se)->next ||
 			 &p->se == cfs_rq_of(&p->se)->last))
 		return 1;
@@ -7398,7 +7400,8 @@ static int migrate_degrades_locality(struct task_struct *p, struct lb_env *env)
 
 	/* Migrating away from the preferred node is always bad. */
 	if (src_nid == p->numa_preferred_nid) {
-		if (env->src_rq->nr_running > env->src_rq->nr_preferred_running)
+		if ((env->src_rq->nr_running - env->src_rq->bt.bt_nr_running) >
+		     env->src_rq->nr_preferred_running)
 			return 1;
 		else
 			return -1;
@@ -7580,7 +7583,9 @@ static int detach_tasks(struct lb_env *env)
 		 * We don't want to steal all, otherwise we may be treated likewise,
 		 * which could at worst lead to a livelock crash.
 		 */
-		if (env->idle != CPU_NOT_IDLE && env->src_rq->nr_running <= 1)
+		if (env->idle != CPU_NOT_IDLE &&
+		   (env->src_rq->nr_running -
+			env->src_rq->bt.bt_nr_running) <= 1)
 			break;
 
 		p = list_last_entry(tasks, struct task_struct, se.group_node);
@@ -8272,7 +8277,7 @@ static inline void update_sg_lb_stats(struct lb_env *env,
 		sgs->group_util += cpu_util(i);
 		sgs->sum_nr_running += rq->cfs.h_nr_running;
 
-		nr_running = rq->nr_running;
+		nr_running = rq->nr_running - rq->bt.bt_nr_running;
 		if (nr_running > 1)
 			*sg_status |= SG_OVERLOAD;
 
@@ -9080,7 +9085,7 @@ static int load_balance(int this_cpu, struct rq *this_rq,
 	env.src_rq = busiest;
 
 	ld_moved = 0;
-	if (busiest->nr_running > 1) {
+	if (busiest->nr_running - busiest->bt.bt_nr_running > 1) {
 		/*
 		 * Attempt to move tasks. If find_busiest_group has found
 		 * an imbalance but busiest->nr_running <= 1, the group is
@@ -9088,7 +9093,8 @@ static int load_balance(int this_cpu, struct rq *this_rq,
 		 * correctly treated as an imbalance.
 		 */
 		env.flags |= LBF_ALL_PINNED;
-		env.loop_max  = min(sysctl_sched_nr_migrate, busiest->nr_running);
+		env.loop_max  = min(sysctl_sched_nr_migrate,
+			busiest->nr_running - busiest->bt.bt_nr_running);
 
 more_balance:
 		rq_lock_irqsave(busiest, &rf);
@@ -9359,7 +9365,7 @@ static int active_load_balance_cpu_stop(void *data)
 		goto out_unlock;
 
 	/* Is there any task to move? */
-	if (busiest_rq->nr_running <= 1)
+	if (busiest_rq->nr_running - busiest_rq->bt.bt_nr_running <= 1)
 		goto out_unlock;
 
 	/*
@@ -9628,7 +9634,7 @@ static void nohz_balancer_kick(struct rq *rq)
 	if (time_before(now, nohz.next_balance))
 		goto out;
 
-	if (rq->nr_running >= 2) {
+	if (rq->nr_running - rq->bt.bt_nr_running >= 2) {
 		flags = NOHZ_KICK_MASK;
 		goto out;
 	}
@@ -10075,7 +10081,8 @@ static int idle_balance(struct rq *this_rq, struct rq_flags *rf)
 		 * Stop searching for tasks to pull if there are
 		 * now runnable tasks on this rq.
 		 */
-		if (pulled_task || this_rq->nr_running > 0)
+		if (pulled_task || this_rq->nr_running -
+			this_rq->bt.bt_nr_running > 0)
 			break;
 	}
 	rcu_read_unlock();
diff --git a/kernel/sched/loadavg.c b/kernel/sched/loadavg.c
index 28a5165..6810e59 100644
--- a/kernel/sched/loadavg.c
+++ b/kernel/sched/loadavg.c
@@ -80,8 +80,9 @@ long calc_load_fold_active(struct rq *this_rq, long adjust)
 {
 	long nr_active, delta = 0;
 
-	nr_active = this_rq->nr_running - adjust;
-	nr_active += (long)this_rq->nr_uninterruptible;
+	nr_active = this_rq->nr_running - this_rq->bt.bt_nr_running - adjust;
+	nr_active += (long)this_rq->nr_uninterruptible -
+		     (long)this_rq->bt.nr_uninterruptible;
 
 	if (nr_active != this_rq->calc_load_active) {
 		delta = nr_active - this_rq->calc_load_active;
diff --git a/kernel/time/posix-cpu-timers.c b/kernel/time/posix-cpu-timers.c
index 0a426f4..db54c82 100644
--- a/kernel/time/posix-cpu-timers.c
+++ b/kernel/time/posix-cpu-timers.c
@@ -829,7 +829,7 @@ static void check_thread_timers(struct task_struct *tsk,
 	tsk_expires->virt_exp = expires;
 
 	tsk_expires->sched_exp = check_timers_list(++timers, firing,
-						   tsk->se.sum_exec_runtime);
+			   tsk->se.sum_exec_runtime + tsk->bt.sum_exec_runtime);
 
 	/*
 	 * Check for the special case thread timers.
-- 
1.8.3.1

[PATCH 5/5] sched/BT: add debug information for BT scheduling class

[xiaoggchen]

From: chen xiaoguang <xiaoggchen@tencent.com>

Signed-off-by: Newton Gao <newtongao@tencent.com>
Signed-off-by: Shook Liu <shookliu@tencent.com>
Signed-off-by: Zhiguang Peng <zgpeng@tencent.com>
Signed-off-by: Xiaoguang Chen <xiaoggchen@tencent.com>
---
 kernel/sched/bt.c    | 11 +++++++++++
 kernel/sched/debug.c | 37 +++++++++++++++++++++++++++++++++++++
 kernel/sched/sched.h |  3 +++
 3 files changed, 51 insertions(+)

diff --git a/kernel/sched/bt.c b/kernel/sched/bt.c
index 87eb04f..11b4abd 100644
--- a/kernel/sched/bt.c
+++ b/kernel/sched/bt.c
@@ -1027,3 +1027,14 @@ static unsigned int get_rr_interval_bt(struct rq *rq, struct task_struct *task)
 	.update_curr            = update_curr_bt,
 };
 
+#ifdef CONFIG_SCHED_DEBUG
+void print_bt_stats(struct seq_file *m, int cpu)
+{
+	struct bt_rq *bt_rq;
+
+	rcu_read_lock();
+	bt_rq = &cpu_rq(cpu)->bt;
+	print_bt_rq(m, cpu, bt_rq);
+	rcu_read_unlock();
+}
+#endif
diff --git a/kernel/sched/debug.c b/kernel/sched/debug.c
index 678bfb9..44d0859 100644
--- a/kernel/sched/debug.c
+++ b/kernel/sched/debug.c
@@ -497,6 +497,43 @@ static void print_rq(struct seq_file *m, struct rq *rq, int rq_cpu)
 	rcu_read_unlock();
 }
 
+void print_bt_rq(struct seq_file *m, int cpu, struct bt_rq *bt_rq)
+{
+	s64 MIN_vruntime = -1, min_vruntime, max_vruntime = -1,
+		spread, rq0_min_vruntime, spread0;
+	struct rq *rq = cpu_rq(cpu);
+	unsigned long flags;
+
+	SEQ_printf(m, "\nbt_rq[%d]:\n", cpu);
+
+	SEQ_printf(m, "  .%-30s: %lld.%06ld\n", "exec_clock",
+			SPLIT_NS(bt_rq->exec_clock));
+
+	raw_spin_lock_irqsave(&rq->lock, flags);
+	if (bt_rq->rb_leftmost)
+		MIN_vruntime = (__pick_first_bt_entity(bt_rq))->vruntime;
+	min_vruntime = bt_rq->min_vruntime;
+	rq0_min_vruntime = cpu_rq(0)->bt.min_vruntime;
+	raw_spin_unlock_irqrestore(&rq->lock, flags);
+	SEQ_printf(m, "  .%-30s: %lld.%06ld\n", "MIN_vruntime",
+		SPLIT_NS(MIN_vruntime));
+	SEQ_printf(m, "  .%-30s: %lld.%06ld\n", "min_vruntime",
+		SPLIT_NS(min_vruntime));
+	SEQ_printf(m, "  .%-30s: %lld.%06ld\n", "max_vruntime",
+		SPLIT_NS(max_vruntime));
+	spread = max_vruntime - MIN_vruntime;
+	SEQ_printf(m, "  .%-30s: %lld.%06ld\n", "spread",
+		SPLIT_NS(spread));
+	spread0 = min_vruntime - rq0_min_vruntime;
+	SEQ_printf(m, "  .%-30s: %lld.%06ld\n", "spread0",
+		SPLIT_NS(spread0));
+	SEQ_printf(m, "  .%-30s: %d\n", "nr_spread_over",
+		bt_rq->nr_spread_over);
+	SEQ_printf(m, "  .%-30s: %d\n", "nr_running", bt_rq->bt_nr_running);
+	SEQ_printf(m, "  .%-30s: %ld\n", "load", bt_rq->load.weight);
+}
+
+
 void print_cfs_rq(struct seq_file *m, int cpu, struct cfs_rq *cfs_rq)
 {
 	s64 MIN_vruntime = -1, min_vruntime, max_vruntime = -1,
diff --git a/kernel/sched/sched.h b/kernel/sched/sched.h
index 403eec6..749f580 100644
--- a/kernel/sched/sched.h
+++ b/kernel/sched/sched.h
@@ -2120,6 +2120,8 @@ static inline void double_rq_unlock(struct rq *rq1, struct rq *rq2)
 extern struct sched_entity *__pick_first_entity(struct cfs_rq *cfs_rq);
 extern struct sched_entity *__pick_last_entity(struct cfs_rq *cfs_rq);
 
+extern struct sched_bt_entity *__pick_first_bt_entity(struct bt_rq *bt_rq);
+
 #ifdef	CONFIG_SCHED_DEBUG
 extern bool sched_debug_enabled;
 
@@ -2129,6 +2131,7 @@ static inline void double_rq_unlock(struct rq *rq1, struct rq *rq2)
 extern void print_cfs_rq(struct seq_file *m, int cpu, struct cfs_rq *cfs_rq);
 extern void print_rt_rq(struct seq_file *m, int cpu, struct rt_rq *rt_rq);
 extern void print_dl_rq(struct seq_file *m, int cpu, struct dl_rq *dl_rq);
+extern void print_bt_rq(struct seq_file *m, int cpu, struct bt_rq *bt_rq);
 #ifdef CONFIG_NUMA_BALANCING
 extern void
 show_numa_stats(struct task_struct *p, struct seq_file *m);
-- 
1.8.3.1

Re: [PATCH 0/5] BT scheduling class

[Peter Zijlstra]

On Fri, Jun 21, 2019 at 03:45:52PM +0800, xiaoggchen@tencent.com wrote:
> From: chen xiaoguang <xiaoggchen@tencent.com>
> 
> This patch set introduces a new scheduler, we name it BT scheduler
> for the moment.

> The BT scheduler is similar with the CFS scheduler. We also use the
> rb-tree as the run queue to save the runnable tasks. And the vruntime 
> concept is also used in the BT scheduler. And the priority of BT scheduler
> is from 140 to 179. So now the schedulers in the kernel are as follows:
> deadline, RT, CFS, BT and idle.

NAK; it has no forward progress guarantees. This is also the reason why
SCHED_IDLE is not a true idle time scheduler but a very low weight CFS
tasks.

It also has some very 'interesting' starvation cases, consider one of
your BT tasks owns a mutex, but then there are there are runnable CFS
tasks. The BT task will never get runtime and release the mutex.

Also; NAK at all the duplication.

Re: [PATCH 0/5] BT scheduling class

[Peter Zijlstra]

On Fri, Jun 21, 2019 at 03:45:52PM +0800, xiaoggchen@tencent.com wrote:

> First only server application exists in the system and the success
> rate is 99.998% and the average cpu use is only 25%.

Have you guys looked at this series:

  https://lkml.kernel.org/r/cover.1556182964.git.viresh.kumar@linaro.org

Re: [PATCH 0/5] BT scheduling class

[Valentin Schneider]

On 21/06/2019 14:03, Peter Zijlstra wrote:
> On Fri, Jun 21, 2019 at 03:45:52PM +0800, xiaoggchen@tencent.com wrote:
> 
>> First only server application exists in the system and the success
>> rate is 99.998% and the average cpu use is only 25%.
> 
> Have you guys looked at this series:
> 
>   https://lkml.kernel.org/r/cover.1556182964.git.viresh.kumar@linaro.org
> 
> 

Sort of a shot in the dark here, but I wonder if task stealing [1] could
help as well? IIRC Steve had some pretty good CPU utilization improvements
with his series.

FWIW I have a somewhat recent rebase of CFS stealing laying around at [2].

[1]: https://lore.kernel.org/lkml/1544131696-2888-1-git-send-email-steven.sistare@oracle.com/
[2]: http://www.linux-arm.org/git?p=linux-vs.git;a=shortlog;h=refs/heads/mainline/cfs-stealing/v4-rebase