[PATCH] sched: Force the address order of each sched class descriptor

[PATCH] sched: Force the address order of each sched class descriptor

[Steven Rostedt]

From: "Steven Rostedt (VMware)" <rostedt@goodmis.org>

[ Kirill, feel free to include this patch with yours ]

In order to make a micro optimization in pick_next_task(), the order of the
sched class descriptor address must be in the same order as their priority
to each other. That is:

 &idle_sched_class < &fair_sched_class < &rt_sched_class <
 &dl_sched_class < &stop_sched_class

In order to guarantee this order of the sched class descriptors, add each
one into their own data section and force the order in the linker script.

Link: https://lore.kernel.org/r/157675913272.349305.8936736338884044103.stgit@localhost.localdomain
Signed-off-by: Steven Rostedt (VMware) <rostedt@goodmis.org>
---
 include/asm-generic/vmlinux.lds.h | 13 +++++++++++++
 kernel/sched/deadline.c           |  3 ++-
 kernel/sched/fair.c               |  3 ++-
 kernel/sched/idle.c               |  3 ++-
 kernel/sched/rt.c                 |  3 ++-
 kernel/sched/stop_task.c          |  3 ++-
 6 files changed, 23 insertions(+), 5 deletions(-)

diff --git a/include/asm-generic/vmlinux.lds.h b/include/asm-generic/vmlinux.lds.h
index e00f41aa8ec4..7e8b02fdcf3f 100644
--- a/include/asm-generic/vmlinux.lds.h
+++ b/include/asm-generic/vmlinux.lds.h
@@ -108,6 +108,18 @@
 #define SBSS_MAIN .sbss
 #endif
 
+/*
+ * The order of the sched class addresses are important, as they are
+ * used to determine the order of the priority of each sched class in
+ * relation to each other.
+ */
+#define SCHED_DATA				\
+	*(__idle_sched_class)			\
+	*(__fair_sched_class)			\
+	*(__rt_sched_class)			\
+	*(__dl_sched_class)			\
+	*(__stop_sched_class)
+
 /*
  * Align to a 32 byte boundary equal to the
  * alignment gcc 4.5 uses for a struct
@@ -308,6 +320,7 @@
 #define DATA_DATA							\
 	*(.xiptext)							\
 	*(DATA_MAIN)							\
+	SCHED_DATA							\
 	*(.ref.data)							\
 	*(.data..shared_aligned) /* percpu related */			\
 	MEM_KEEP(init.data*)						\
diff --git a/kernel/sched/deadline.c b/kernel/sched/deadline.c
index 43323f875cb9..5abdbe569f93 100644
--- a/kernel/sched/deadline.c
+++ b/kernel/sched/deadline.c
@@ -2428,7 +2428,8 @@ static void prio_changed_dl(struct rq *rq, struct task_struct *p,
 	}
 }
 
-const struct sched_class dl_sched_class = {
+const struct sched_class dl_sched_class
+	__attribute__((section("__dl_sched_class"))) = {
 	.next			= &rt_sched_class,
 	.enqueue_task		= enqueue_task_dl,
 	.dequeue_task		= dequeue_task_dl,
diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
index 08a233e97a01..e745fe0e0cd3 100644
--- a/kernel/sched/fair.c
+++ b/kernel/sched/fair.c
@@ -10745,7 +10745,8 @@ 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 = {
+const struct sched_class fair_sched_class
+	__attribute__((section("__fair_sched_class"))) = {
 	.next			= &idle_sched_class,
 	.enqueue_task		= enqueue_task_fair,
 	.dequeue_task		= dequeue_task_fair,
diff --git a/kernel/sched/idle.c b/kernel/sched/idle.c
index ffa959e91227..700a9c826f0e 100644
--- a/kernel/sched/idle.c
+++ b/kernel/sched/idle.c
@@ -454,7 +454,8 @@ static void update_curr_idle(struct rq *rq)
 /*
  * Simple, special scheduling class for the per-CPU idle tasks:
  */
-const struct sched_class idle_sched_class = {
+const struct sched_class idle_sched_class
+	__attribute__((section("__idle_sched_class"))) = {
 	/* .next is NULL */
 	/* no enqueue/yield_task for idle tasks */
 
diff --git a/kernel/sched/rt.c b/kernel/sched/rt.c
index e591d40fd645..5d3f9bcddaeb 100644
--- a/kernel/sched/rt.c
+++ b/kernel/sched/rt.c
@@ -2354,7 +2354,8 @@ static unsigned int get_rr_interval_rt(struct rq *rq, struct task_struct *task)
 		return 0;
 }
 
-const struct sched_class rt_sched_class = {
+const struct sched_class rt_sched_class
+	__attribute__((section("__rt_sched_class"))) = {
 	.next			= &fair_sched_class,
 	.enqueue_task		= enqueue_task_rt,
 	.dequeue_task		= dequeue_task_rt,
diff --git a/kernel/sched/stop_task.c b/kernel/sched/stop_task.c
index 4c9e9975684f..03bc7530ff75 100644
--- a/kernel/sched/stop_task.c
+++ b/kernel/sched/stop_task.c
@@ -115,7 +115,8 @@ static void update_curr_stop(struct rq *rq)
 /*
  * Simple, special scheduling class for the per-CPU stop tasks:
  */
-const struct sched_class stop_sched_class = {
+const struct sched_class stop_sched_class
+	__attribute__((section("__stop_sched_class"))) = {
 	.next			= &dl_sched_class,
 
 	.enqueue_task		= enqueue_task_stop,
-- 
2.20.1

[PATCH v3] sched: Micro optimization in pick_next_task() and in check_preempt_curr()

[Kirill Tkhai]

This introduces an optimization based on xxx_sched_class addresses
in two hot scheduler functions: pick_next_task() and check_preempt_curr().

It is possible to compare pointers to sched classes to check, which
of them has a higher priority, instead of current iterations using
for_each_class().

One more result of the patch is that size of object file becomes a little
less (excluding added BUG_ON(), which goes in __init section):

$size kernel/sched/core.o
         text     data      bss	    dec	    hex	filename
before:  66446    18957	    676	  86079	  1503f	kernel/sched/core.o
after:   66398    18957	    676	  86031	  1500f	kernel/sched/core.o

Signed-off-by: Kirill Tkhai <ktkhai@virtuozzo.com>
---
 kernel/sched/core.c |   24 +++++++++---------------
 1 file changed, 9 insertions(+), 15 deletions(-)

diff --git a/kernel/sched/core.c b/kernel/sched/core.c
index 15508c202bf5..befdd7158b27 100644
--- a/kernel/sched/core.c
+++ b/kernel/sched/core.c
@@ -1416,20 +1416,10 @@ static inline void check_class_changed(struct rq *rq, struct task_struct *p,
 
 void check_preempt_curr(struct rq *rq, struct task_struct *p, int flags)
 {
-	const struct sched_class *class;
-
-	if (p->sched_class == rq->curr->sched_class) {
+	if (p->sched_class == rq->curr->sched_class)
 		rq->curr->sched_class->check_preempt_curr(rq, p, flags);
-	} else {
-		for_each_class(class) {
-			if (class == rq->curr->sched_class)
-				break;
-			if (class == p->sched_class) {
-				resched_curr(rq);
-				break;
-			}
-		}
-	}
+	else if (p->sched_class > rq->curr->sched_class)
+		resched_curr(rq);
 
 	/*
 	 * A queue event has occurred, and we're going to schedule.  In
@@ -3914,8 +3904,7 @@ pick_next_task(struct rq *rq, struct task_struct *prev, struct rq_flags *rf)
 	 * higher scheduling class, because otherwise those loose the
 	 * opportunity to pull in more work from other CPUs.
 	 */
-	if (likely((prev->sched_class == &idle_sched_class ||
-		    prev->sched_class == &fair_sched_class) &&
+	if (likely(prev->sched_class <= &fair_sched_class &&
 		   rq->nr_running == rq->cfs.h_nr_running)) {
 
 		p = pick_next_task_fair(rq, prev, rf);
@@ -6569,6 +6558,11 @@ void __init sched_init(void)
 	unsigned long ptr = 0;
 	int i;
 
+	BUG_ON(&idle_sched_class > &fair_sched_class ||
+		&fair_sched_class > &rt_sched_class ||
+		&rt_sched_class > &dl_sched_class ||
+		&dl_sched_class > &stop_sched_class);
+
 	wait_bit_init();
 
 #ifdef CONFIG_FAIR_GROUP_SCHED

Re: [PATCH v3] sched: Micro optimization in pick_next_task() and in check_preempt_curr()

[Steven Rostedt]

On Thu, 19 Dec 2019 20:12:15 +0000
Kirill Tkhai <ktkhai@virtuozzo.com> wrote:

> This introduces an optimization based on xxx_sched_class addresses
> in two hot scheduler functions: pick_next_task() and check_preempt_curr().
> 
> It is possible to compare pointers to sched classes to check, which
> of them has a higher priority, instead of current iterations using
> for_each_class().
> 
> One more result of the patch is that size of object file becomes a little
> less (excluding added BUG_ON(), which goes in __init section):
> 
> $size kernel/sched/core.o
>          text     data      bss	    dec	    hex	filename
> before:  66446    18957	    676	  86079	  1503f	kernel/sched/core.o
> after:   66398    18957	    676	  86031	  1500f	kernel/sched/core.o
> 
> Signed-off-by: Kirill Tkhai <ktkhai@virtuozzo.com>

Care to resend, not as a mime image?

-- Steve


> Content-Type: text/plain; charset="utf-8"
> Content-ID: <C1D028DDF0B4064595B78514E3E235C5@eurprd08.prod.outlook.com>
> Content-Transfer-Encoding: base64
> MIME-Version: 1.0
> X-OriginatorOrg: virtuozzo.com
> X-MS-Exchange-CrossTenant-Network-Message-Id: 63724e70-f5a2-4d04-bbaa-08d784bfbdf9
> X-MS-Exchange-CrossTenant-originalarrivaltime: 19 Dec 2019 20:12:16.0672
>  (UTC)
> X-MS-Exchange-CrossTenant-fromentityheader: Hosted
> X-MS-Exchange-CrossTenant-id: 0bc7f26d-0264-416e-a6fc-8352af79c58f
> X-MS-Exchange-CrossTenant-mailboxtype: HOSTED
> X-MS-Exchange-CrossTenant-userprincipalname: wYML0eHmbgTBU2jD+X1IMNyAYqtN3rJ3EgoGfPJQcQ2Wqq2KJfyClc/7Q5BfozgXMC5ZM7OdiAJShPtJE7UvuA==
> X-MS-Exchange-Transport-CrossTenantHeadersStamped: VI1PR08MB3343
> 
> VGhpcyBpbnRyb2R1Y2VzIGFuIG9wdGltaXphdGlvbiBiYXNlZCBvbiB4eHhfc2NoZWRfY2xhc3Mg
> YWRkcmVzc2VzDQppbiB0d28gaG90IHNjaGVkdWxlciBmdW5jdGlvbnM6IHBpY2tfbmV4dF90YXNr
> KCkgYW5kIGNoZWNrX3ByZWVtcHRfY3VycigpLg0KDQpJdCBpcyBwb3NzaWJsZSB0byBjb21wYXJl
> IHBvaW50ZXJzIHRvIHNjaGVkIGNsYXNzZXMgdG8gY2hlY2ssIHdoaWNoDQpvZiB0aGVtIGhhcyBh
> IGhpZ2hlciBwcmlvcml0eSwgaW5zdGVhZCBvZiBjdXJyZW50IGl0ZXJhdGlvbnMgdXNpbmcNCmZv
> cl9lYWNoX2NsYXNzKCkuDQoNCk9uZSBtb3JlIHJlc3VsdCBvZiB0aGUgcGF0Y2ggaXMgdGhhdCBz
> aXplIG9mIG9iamVjdCBmaWxlIGJlY29tZXMgYSBsaXR0bGUNCmxlc3MgKGV4Y2x1ZGluZyBhZGRl
> ZCBCVUdfT04oKSwgd2hpY2ggZ29lcyBpbiBfX2luaXQgc2VjdGlvbik6DQoNCiRzaXplIGtlcm5l
> bC9zY2hlZC9jb3JlLm8NCiAgICAgICAgIHRleHQgICAgIGRhdGEgICAgICBic3MJICAgIGRlYwkg
> ICAgaGV4CWZpbGVuYW1lDQpiZWZvcmU6ICA2NjQ0NiAgICAxODk1NwkgICAgNjc2CSAgODYwNzkJ
> ICAxNTAzZglrZXJuZWwvc2NoZWQvY29yZS5vDQphZnRlcjogICA2NjM5OCAgICAxODk1NwkgICAg
> Njc2CSAgODYwMzEJICAxNTAwZglrZXJuZWwvc2NoZWQvY29yZS5vDQoNClNpZ25lZC1vZmYtYnk6
> IEtpcmlsbCBUa2hhaSA8a3RraGFpQHZpcnR1b3p6by5jb20+DQotLS0NCiBrZXJuZWwvc2NoZWQv
> Y29yZS5jIHwgICAyNCArKysrKysrKystLS0tLS0tLS0tLS0tLS0NCiAxIGZpbGUgY2hhbmdlZCwg
> OSBpbnNlcnRpb25zKCspLCAxNSBkZWxldGlvbnMoLSkNCg0KZGlmZiAtLWdpdCBhL2tlcm5lbC9z
> Y2hlZC9jb3JlLmMgYi9rZXJuZWwvc2NoZWQvY29yZS5jDQppbmRleCAxNTUwOGMyMDJiZjUuLmJl
> ZmRkNzE1OGIyNyAxMDA2NDQNCi0tLSBhL2tlcm5lbC9zY2hlZC9jb3JlLmMNCisrKyBiL2tlcm5l
> bC9zY2hlZC9jb3JlLmMNCkBAIC0xNDE2LDIwICsxNDE2LDEwIEBAIHN0YXRpYyBpbmxpbmUgdm9p
> ZCBjaGVja19jbGFzc19jaGFuZ2VkKHN0cnVjdCBycSAqcnEsIHN0cnVjdCB0YXNrX3N0cnVjdCAq
> cCwNCiANCiB2b2lkIGNoZWNrX3ByZWVtcHRfY3VycihzdHJ1Y3QgcnEgKnJxLCBzdHJ1Y3QgdGFz
> a19zdHJ1Y3QgKnAsIGludCBmbGFncykNCiB7DQotCWNvbnN0IHN0cnVjdCBzY2hlZF9jbGFzcyAq
> Y2xhc3M7DQotDQotCWlmIChwLT5zY2hlZF9jbGFzcyA9PSBycS0+Y3Vyci0+c2NoZWRfY2xhc3Mp
> IHsNCisJaWYgKHAtPnNjaGVkX2NsYXNzID09IHJxLT5jdXJyLT5zY2hlZF9jbGFzcykNCiAJCXJx
> LT5jdXJyLT5zY2hlZF9jbGFzcy0+Y2hlY2tfcHJlZW1wdF9jdXJyKHJxLCBwLCBmbGFncyk7DQot
> CX0gZWxzZSB7DQotCQlmb3JfZWFjaF9jbGFzcyhjbGFzcykgew0KLQkJCWlmIChjbGFzcyA9PSBy
> cS0+Y3Vyci0+c2NoZWRfY2xhc3MpDQotCQkJCWJyZWFrOw0KLQkJCWlmIChjbGFzcyA9PSBwLT5z
> Y2hlZF9jbGFzcykgew0KLQkJCQlyZXNjaGVkX2N1cnIocnEpOw0KLQkJCQlicmVhazsNCi0JCQl9
> DQotCQl9DQotCX0NCisJZWxzZSBpZiAocC0+c2NoZWRfY2xhc3MgPiBycS0+Y3Vyci0+c2NoZWRf
> Y2xhc3MpDQorCQlyZXNjaGVkX2N1cnIocnEpOw0KIA0KIAkvKg0KIAkgKiBBIHF1ZXVlIGV2ZW50
> IGhhcyBvY2N1cnJlZCwgYW5kIHdlJ3JlIGdvaW5nIHRvIHNjaGVkdWxlLiAgSW4NCkBAIC0zOTE0
> LDggKzM5MDQsNyBAQCBwaWNrX25leHRfdGFzayhzdHJ1Y3QgcnEgKnJxLCBzdHJ1Y3QgdGFza19z
> dHJ1Y3QgKnByZXYsIHN0cnVjdCBycV9mbGFncyAqcmYpDQogCSAqIGhpZ2hlciBzY2hlZHVsaW5n
> IGNsYXNzLCBiZWNhdXNlIG90aGVyd2lzZSB0aG9zZSBsb29zZSB0aGUNCiAJICogb3Bwb3J0dW5p
> dHkgdG8gcHVsbCBpbiBtb3JlIHdvcmsgZnJvbSBvdGhlciBDUFVzLg0KIAkgKi8NCi0JaWYgKGxp
> a2VseSgocHJldi0+c2NoZWRfY2xhc3MgPT0gJmlkbGVfc2NoZWRfY2xhc3MgfHwNCi0JCSAgICBw
> cmV2LT5zY2hlZF9jbGFzcyA9PSAmZmFpcl9zY2hlZF9jbGFzcykgJiYNCisJaWYgKGxpa2VseShw
> cmV2LT5zY2hlZF9jbGFzcyA8PSAmZmFpcl9zY2hlZF9jbGFzcyAmJg0KIAkJICAgcnEtPm5yX3J1
> bm5pbmcgPT0gcnEtPmNmcy5oX25yX3J1bm5pbmcpKSB7DQogDQogCQlwID0gcGlja19uZXh0X3Rh
> c2tfZmFpcihycSwgcHJldiwgcmYpOw0KQEAgLTY1NjksNiArNjU1OCwxMSBAQCB2b2lkIF9faW5p
> dCBzY2hlZF9pbml0KHZvaWQpDQogCXVuc2lnbmVkIGxvbmcgcHRyID0gMDsNCiAJaW50IGk7DQog
> DQorCUJVR19PTigmaWRsZV9zY2hlZF9jbGFzcyA+ICZmYWlyX3NjaGVkX2NsYXNzIHx8DQorCQkm
> ZmFpcl9zY2hlZF9jbGFzcyA+ICZydF9zY2hlZF9jbGFzcyB8fA0KKwkJJnJ0X3NjaGVkX2NsYXNz
> ID4gJmRsX3NjaGVkX2NsYXNzIHx8DQorCQkmZGxfc2NoZWRfY2xhc3MgPiAmc3RvcF9zY2hlZF9j
> bGFzcyk7DQorDQogCXdhaXRfYml0X2luaXQoKTsNCiANCiAjaWZkZWYgQ09ORklHX0ZBSVJfR1JP
> VVBfU0NIRUQNCg0K

Re: [PATCH RESEND v3] sched: Micro optimization in pick_next_task() and in check_preempt_curr()

[Peter Zijlstra]

On Fri, Dec 20, 2019 at 12:27:05AM +0300, Kirill Tkhai wrote:
> This introduces an optimization based on xxx_sched_class addresses
> in two hot scheduler functions: pick_next_task() and check_preempt_curr().
> 
> It is possible to compare pointers to sched classes to check, which
> of them has a higher priority, instead of current iterations using
> for_each_class().
> 
> One more result of the patch is that size of object file becomes a little
> less (excluding added BUG_ON(), which goes in __init section):
> 
> $size kernel/sched/core.o
>          text     data      bss	    dec	    hex	filename
> before:  66446    18957	    676	  86079	  1503f	kernel/sched/core.o
> after:   66398    18957	    676	  86031	  1500f	kernel/sched/core.o
> 
> Signed-off-by: Kirill Tkhai <ktkhai@virtuozzo.com>

Thanks guys!

[tip: sched/core] sched: Micro optimization in pick_next_task() and in check_preempt_curr()

[tip-bot2 for Kirill Tkhai]

The following commit has been merged into the sched/core branch of tip:

Commit-ID:     aa93cd53bc1b91b5f99c7b55e3dcc1ac98e99558
Gitweb:        https://git.kernel.org/tip/aa93cd53bc1b91b5f99c7b55e3dcc1ac98e99558
Author:        Kirill Tkhai <tkhai@yandex.ru>
AuthorDate:    Thu, 19 Dec 2019 16:44:55 -05:00
Committer:     Peter Zijlstra <peterz@infradead.org>
CommitterDate: Thu, 25 Jun 2020 13:45:44 +02:00

sched: Micro optimization in pick_next_task() and in check_preempt_curr()

This introduces an optimization based on xxx_sched_class addresses
in two hot scheduler functions: pick_next_task() and check_preempt_curr().

It is possible to compare pointers to sched classes to check, which
of them has a higher priority, instead of current iterations using
for_each_class().

One more result of the patch is that size of object file becomes a little
less (excluding added BUG_ON(), which goes in __init section):

$size kernel/sched/core.o
         text     data      bss	    dec	    hex	filename
before:  66446    18957	    676	  86079	  1503f	kernel/sched/core.o
after:   66398    18957	    676	  86031	  1500f	kernel/sched/core.o

Signed-off-by: Kirill Tkhai <ktkhai@virtuozzo.com>
Signed-off-by: Steven Rostedt (VMware) <rostedt@goodmis.org>
Signed-off-by: Peter Zijlstra (Intel) <peterz@infradead.org>
Link: http://lkml.kernel.org/r/711a9c4b-ff32-1136-b848-17c622d548f3@yandex.ru
---
 kernel/sched/core.c | 19 ++++---------------
 1 file changed, 4 insertions(+), 15 deletions(-)

diff --git a/kernel/sched/core.c b/kernel/sched/core.c
index 81640fe..0a08d0c 100644
--- a/kernel/sched/core.c
+++ b/kernel/sched/core.c
@@ -1412,20 +1412,10 @@ static inline void check_class_changed(struct rq *rq, struct task_struct *p,
 
 void check_preempt_curr(struct rq *rq, struct task_struct *p, int flags)
 {
-	const struct sched_class *class;
-
-	if (p->sched_class == rq->curr->sched_class) {
+	if (p->sched_class == rq->curr->sched_class)
 		rq->curr->sched_class->check_preempt_curr(rq, p, flags);
-	} else {
-		for_each_class(class) {
-			if (class == rq->curr->sched_class)
-				break;
-			if (class == p->sched_class) {
-				resched_curr(rq);
-				break;
-			}
-		}
-	}
+	else if (p->sched_class > rq->curr->sched_class)
+		resched_curr(rq);
 
 	/*
 	 * A queue event has occurred, and we're going to schedule.  In
@@ -4003,8 +3993,7 @@ pick_next_task(struct rq *rq, struct task_struct *prev, struct rq_flags *rf)
 	 * higher scheduling class, because otherwise those loose the
 	 * opportunity to pull in more work from other CPUs.
 	 */
-	if (likely((prev->sched_class == &idle_sched_class ||
-		    prev->sched_class == &fair_sched_class) &&
+	if (likely(prev->sched_class <= &fair_sched_class &&
 		   rq->nr_running == rq->cfs.h_nr_running)) {
 
 		p = pick_next_task_fair(rq, prev, rf);