Skip to contentSkip to conversation

sched/core: fix pick_next_task 'max' tracking

PATCH In review Josh Don 5 participants 17 messages Aug 18, 2021 – Oct 5, 2021 Scheduler

lore
Share & tools
lore

Josh Don

author
#0 lore raw

PATCH 1/1 sched/core: fix pick_next_task 'max' tracking

For core-sched, pick_next_task will update the 'max' task if there is a cookie mismatch (since in this case the new task must be of higher priority than the current max). However, we fail to update 'max' if we've found a task with a matching cookie and higher priority than 'max'.

This can result in extra iterations on SMT-X machines, where X > 2.

As an example, on a machine with SMT=3, on core 0, SMT-0 might pick the following, in order:

- SMT-0: p1, with cookie A, and priority 10 (max = p1)
- SMT-1: p2, with cookie A, and priority 30 (max not updated here)
- SMT-2: p3, with cookie B, and priority 20 (max = p2) > invalidate the other picks and retry

Here, we should have instead updated 'max' when picking for SMT-1. Note that this code would eventually have righted itself, since the retry loop would re-pick p2, and update 'max' accordingly. However, this patch avoids the extra round-trip.

---
 kernel/sched/core.c | 2 ++
 1 file changed, 2 insertions(+)
kernel/sched/core.c +2 -0
index 3431939699dc..110ea7582a33 100644
@@ -5623,6 +5623,8 @@ pick_next_task(struct rq *rq, struct task_struct *prev, struct rq_flags *rf)
 					occ = 1;
 					goto again;
 				}
+			} else if (prio_less(max, p, fi_before)) {
+				max = p;
 			}
 		}
 	}
Signature · 1 line
2.33.0.rc1.237.g0d66db33f3-goog
#1 lore raw

Hi Josh,

Quoted 6 lines · Josh Don

For core-sched, pick_next_task will update the 'max' task if there is a cookie mismatch (since in this case the new task must be of higher priority than the current max). However, we fail to update 'max' if we've found a task with a matching cookie and higher priority than 'max'.

Quoted 7 lines

This can result in extra iterations on SMT-X machines, where X > 2.

As an example, on a machine with SMT=3, on core 0, SMT-0 might pick the following, in order:

- SMT-0: p1, with cookie A, and priority 10 (max = p1)
- SMT-1: p2, with cookie A, and priority 30 (max not updated here)

Thanks for your illustration. Good catch.
The guilty is 'cookie_equals(class_pick, cookie))' condition in pick_task()

Quoted 7 lines

- SMT-2: p3, with cookie B, and priority 20 (max = p2) > invalidate the other picks and retry

Here, we should have instead updated 'max' when picking for SMT-1. Note that this code would eventually have righted itself, since the retry loop would re-pick p2, and update 'max' accordingly. However, this patch avoids the extra round-trip.

This is correct then may increase the chance to retry. That means it is more possible to filter the max first(not sure).

Quoted 21 lines
---
 kernel/sched/core.c | 2 ++
 1 file changed, 2 insertions(+)
kernel/sched/core.c +2 -0
index 3431939699dc..110ea7582a33 100644
@@ -5623,6 +5623,8 @@ pick_next_task(struct rq *rq, struct task_struct *prev, struct rq_flags *rf)
 					occ = 1;
 					goto again;
 				}
+			} else if (prio_less(max, p, fi_before)) {
+				max = p;
 			}
 		}
 	}
Signature · 1 line
2.33.0.rc1.237.g0d66db33f3-goog

Thanks,
Tao

#2 lore raw

Hi,

Quoted 36 lines · Tao Zhou

Hi Josh,

Quoted 6 lines · Josh Don

For core-sched, pick_next_task will update the 'max' task if there is a cookie mismatch (since in this case the new task must be of higher priority than the current max). However, we fail to update 'max' if we've found a task with a matching cookie and higher priority than 'max'.

Quoted 7 lines

This can result in extra iterations on SMT-X machines, where X > 2.

As an example, on a machine with SMT=3, on core 0, SMT-0 might pick the following, in order:

- SMT-0: p1, with cookie A, and priority 10 (max = p1)
- SMT-1: p2, with cookie A, and priority 30 (max not updated here)

Thanks for your illustration. Good catch.
The guilty is 'cookie_equals(class_pick, cookie))' condition in pick_task()

Quoted 7 lines

- SMT-2: p3, with cookie B, and priority 20 (max = p2) > invalidate the other picks and retry

Here, we should have instead updated 'max' when picking for SMT-1. Note that this code would eventually have righted itself, since the retry loop would re-pick p2, and update 'max' accordingly. However, this patch avoids the extra round-trip.

This is correct then may increase the chance to retry. That means it is more possible to filter the max first(not sure).

Quoted 5 lines
---
 kernel/sched/core.c | 2 ++
 1 file changed, 2 insertions(+)
Quoted 16 lines
Quoted 16 lines
kernel/sched/core.c +2 -0
index 3431939699dc..110ea7582a33 100644
@@ -5623,6 +5623,8 @@ pick_next_task(struct rq *rq, struct task_struct *prev, struct rq_flags *rf)
 					occ = 1;
 					goto again;
 				}
+			} else if (prio_less(max, p, fi_before)) {
+				max = p;
 			}
 		}
 	}
Signature · 1 line
2.33.0.rc1.237.g0d66db33f3-goog

My ugly patch need to continue, not compiled.
Rebase on the previous patch.

From 79f25599486c79ecb2e78875498b24f1320060b8 Mon Sep 17 00:00:00 2001
From: Tao Zhou <[email protected]>
Date: Wed, 18 Aug 2021 00:07:38 +0800
Subject: [PATCH] optimize pick_next_task()

sched/core: Optimize pick_next_task() not sure

---
 kernel/sched/core.c  | 78 ++++++++++++++++++++++++++++++--------------
 kernel/sched/sched.h |  1 +
 2 files changed, 54 insertions(+), 25 deletions(-)
kernel/sched/core.c +53 -25
index 20ffcc044134..18f236f75170 100644
@@ -5370,28 +5370,42 @@ pick_task(struct rq *rq, const struct sched_class *class, struct task_struct *ma
 		if (max && class_pick->core_cookie &&
 		    prio_less(class_pick, max, in_fi))
 			return idle_sched_class.pick_task(rq);
-
-		return class_pick;
 	}
 
-	/*
-	 * If class_pick is idle or matches cookie, return early.
-	 */
-	if (cookie_equals(class_pick, cookie))
-		return class_pick;
+	return class_pick;
+}
+
+static task_struct *
+filter_max_prio(struct rq *rq, struct task_struct *class_pick, struct task_struct *max, bool in_fi)
+{
+	unsigned long cookie = rq->core->core_cookie;
+	struct task_struct *cookie_pick = NULL;
+	bool cookie_core_temp = false;
 
-	cookie_pick = sched_core_find(rq, cookie);
+	rq->core_temp = class_pick;
 
-	/*
-	 * If class > max && class > cookie, it is the highest priority task on
-	 * the core (so far) and it must be selected, otherwise we must go with
-	 * the cookie pick in order to satisfy the constraint.
-	 */
-	if (prio_less(cookie_pick, class_pick, in_fi) &&
-	    (!max || prio_less(max, class_pick, in_fi)))
-		return class_pick;
+	if (cookie) {
+		if (!cookie_equals(class_pick, cookie)) {
+			cookie_pick = sched_core_find(rq, cookie);
+			/*
+			 * If class > max && class > cookie, it is the
+			 * highest priority task on the core (so far)
+			 * and it must be selected, otherwise we must
+			 * go with the cookie pick in order to satisfy
+			 * the constraint.
+			 */
+			if (prio_less(cookie_pick, class_pick, in_fi) &&
+			    (!max || prio_less(max, class_pick, in_fi)))
+				return class_pick;
+			cookie_core_temp = true;
+		} else if (prio_less(max, class_pick, fi_before))
+				return class_pick;
+	}
 
-	return cookie_pick;
+	if (cookie_core_temp)
+		rq->core_temp = cookie_pick;
+
+	return NULL;
 }
 
 extern void task_vruntime_update(struct rq *rq, struct task_struct *p, bool in_fi);
@@ -5508,24 +5522,37 @@ pick_next_task(struct rq *rq, struct task_struct *prev, struct rq_flags *rf)
 	 * order.
 	 */
 	for_each_class(class) {
-again:
+		struct task_struct *class_pick, *cookie_pick;
+		struct rq *rq_i;
+
+		for_each_cpu_wrap(i, smt_mask, cpu) {
+			rq_i = cpu_rq(i);
+			class_pick = pick_task(rq_i, class, max, fi_before);
+			/*
+			 * This sibling doesn't yet have a suitable task to run.
+			 */
+			if (!class_pick)
+				continue;
+
+			if (filter_max_prio(rq_i, class_pick, max, fi_before))
+				max = class_pick;
+		}
+
 		for_each_cpu_wrap(i, smt_mask, cpu) {
-			struct rq *rq_i = cpu_rq(i);
 			struct task_struct *p;
+			rq_i = cpu_rq(i);
 
 			if (rq_i->core_pick)
 				continue;
 
 			/*
-			 * If this sibling doesn't yet have a suitable task to
-			 * run; ask for the most eligible task, given the
-			 * highest priority task already selected for this
-			 * core.
+			 * This sibling doesn't yet have a suitable task to run.
 			 */
-			p = pick_task(rq_i, class, max, fi_before);
-			if (!p)
+			if (!rq_i->core_temp)
 				continue;
 
+			p = rq_i->core_temp;
+
 			if (!is_task_rq_idle(p))
 				occ++;
 
@@ -9024,6 +9051,7 @@ void __init sched_init(void)
 #ifdef CONFIG_SCHED_CORE
 		rq->core = NULL;
 		rq->core_pick = NULL;
+		rq->core_temp = NULL;
 		rq->core_enabled = 0;
 		rq->core_tree = RB_ROOT;
 		rq->core_forceidle = false;
kernel/sched/sched.h +1 -0
index 14a41a243f7b..2b21a3846b8e 100644
@@ -1089,6 +1089,7 @@ struct rq {
 	/* per rq */
 	struct rq		*core;
 	struct task_struct	*core_pick;
+	struct task_struct	*core_temp;
 	unsigned int		core_enabled;
 	unsigned int		core_sched_seq;
 	struct rb_root		core_tree;
Signature · 6 lines
2.31.1



Thanks,
Tao
maintainer
#3 lore raw
In reply to Josh Don
Quoted 16 lines · Josh Don

For core-sched, pick_next_task will update the 'max' task if there is a cookie mismatch (since in this case the new task must be of higher priority than the current max). However, we fail to update 'max' if we've found a task with a matching cookie and higher priority than 'max'.

This can result in extra iterations on SMT-X machines, where X > 2.

As an example, on a machine with SMT=3, on core 0, SMT-0 might pick the following, in order:

- SMT-0: p1, with cookie A, and priority 10 (max = p1)
- SMT-1: p2, with cookie A, and priority 30 (max not updated here)
- SMT-2: p3, with cookie B, and priority 20 (max = p2) > invalidate the other picks and retry

Quoted 4 lines

Here, we should have instead updated 'max' when picking for SMT-1. Note that this code would eventually have righted itself, since the retry loop would re-pick p2, and update 'max' accordingly. However, this patch avoids the extra round-trip.

Going with the observation Tao made; how about we rewrite the whole lot to not be mind-bending complicated :-)

How's this? It seems to build and pass the core-sched selftest thingy (so it must be perfect, right? :-)

---
 kernel/sched/core.c  | 147 ++++++++++++++-------------------------------------
 kernel/sched/sched.h |   1 +
 2 files changed, 41 insertions(+), 107 deletions(-)
kernel/sched/core.c +40 -107
index ceae25ea8a0e..e896250c2fb8 100644
@@ -5404,66 +5404,18 @@ static inline bool cookie_match(struct task_struct *a, struct task_struct *b)
 	return a->core_cookie == b->core_cookie;
 }
 
-// XXX fairness/fwd progress conditions
-/*
- * Returns
- * - NULL if there is no runnable task for this class.
- * - the highest priority task for this runqueue if it matches
- *   rq->core->core_cookie or its priority is greater than max.
- * - Else returns idle_task.
- */
-static struct task_struct *
-pick_task(struct rq *rq, const struct sched_class *class, struct task_struct *max, bool in_fi)
-{
-	struct task_struct *class_pick, *cookie_pick;
-	unsigned long cookie = rq->core->core_cookie;
-
-	class_pick = class->pick_task(rq);
-	if (!class_pick)
-		return NULL;
-
-	if (!cookie) {
-		/*
-		 * If class_pick is tagged, return it only if it has
-		 * higher priority than max.
-		 */
-		if (max && class_pick->core_cookie &&
-		    prio_less(class_pick, max, in_fi))
-			return idle_sched_class.pick_task(rq);
-
-		return class_pick;
-	}
-
-	/*
-	 * If class_pick is idle or matches cookie, return early.
-	 */
-	if (cookie_equals(class_pick, cookie))
-		return class_pick;
-
-	cookie_pick = sched_core_find(rq, cookie);
-
-	/*
-	 * If class > max && class > cookie, it is the highest priority task on
-	 * the core (so far) and it must be selected, otherwise we must go with
-	 * the cookie pick in order to satisfy the constraint.
-	 */
-	if (prio_less(cookie_pick, class_pick, in_fi) &&
-	    (!max || prio_less(max, class_pick, in_fi)))
-		return class_pick;
-
-	return cookie_pick;
-}
-
 extern void task_vruntime_update(struct rq *rq, struct task_struct *p, bool in_fi);
 
 static struct task_struct *
 pick_next_task(struct rq *rq, struct task_struct *prev, struct rq_flags *rf)
 {
-	struct task_struct *next, *max = NULL;
+	struct task_struct *next, *p, *max = NULL;
 	const struct sched_class *class;
 	const struct cpumask *smt_mask;
 	bool fi_before = false;
-	int i, j, cpu, occ = 0;
+	unsigned long cookie;
+	int i, cpu, occ = 0;
+	struct rq *rq_i;
 	bool need_sync;
 
 	if (!sched_core_enabled(rq))
@@ -5554,76 +5506,57 @@ pick_next_task(struct rq *rq, struct task_struct *prev, struct rq_flags *rf)
 		}
 	}
 
-	for_each_cpu(i, smt_mask) {
-		struct rq *rq_i = cpu_rq(i);
-
+	/*
+	 * For each thread: do the regular task pick and find the max prio task
+	 * amongst them.
+	 *
+	 * Tie-break prio towards the current CPU
+	 */
+	for_each_cpu_wrap(i, smt_mask, cpu) {
+		rq_i = cpu_rq(i);
 		rq_i->core_pick = NULL;
 
 		if (i != cpu)
 			update_rq_clock(rq_i);
+
+		for_each_class(class) {
+			p = rq_i->core_temp = class->pick_task(rq_i);
+			if (p)
+				break;
+		}
+
+		if (!max || prio_less(max, p, fi_before))
+			max = p;
 	}
 
+	cookie = rq->core->core_cookie = max->core_cookie;
+
 	/*
-	 * Try and select tasks for each sibling in descending sched_class
-	 * order.
+	 * For each thread: try and find a runnable task that matches @max or
+	 * force idle.
 	 */
-	for_each_class(class) {
-again:
-		for_each_cpu_wrap(i, smt_mask, cpu) {
-			struct rq *rq_i = cpu_rq(i);
-			struct task_struct *p;
-
-			if (rq_i->core_pick)
-				continue;
+	for_each_cpu(i, smt_mask) {
+		rq_i = cpu_rq(i);
+		p = rq_i->core_temp;
 
-			/*
-			 * If this sibling doesn't yet have a suitable task to
-			 * run; ask for the most eligible task, given the
-			 * highest priority task already selected for this
-			 * core.
-			 */
-			p = pick_task(rq_i, class, max, fi_before);
+		if (!cookie_equals(p, cookie)) {
+			p = NULL;
+			if (cookie)
+				p = sched_core_find(rq_i, cookie);
 			if (!p)
-				continue;
+				p = idle_sched_class.pick_task(rq_i);
+		}
 
-			if (!is_task_rq_idle(p))
-				occ++;
+		rq_i->core_pick = p;
 
-			rq_i->core_pick = p;
-			if (rq_i->idle == p && rq_i->nr_running) {
+		if (p == rq_i->idle) {
+			if (rq_i->nr_running) {
 				rq->core->core_forceidle = true;
 				if (!fi_before)
 					rq->core->core_forceidle_seq++;
 			}
-
-			/*
-			 * If this new candidate is of higher priority than the
-			 * previous; and they're incompatible; we need to wipe
-			 * the slate and start over. pick_task makes sure that
-			 * p's priority is more than max if it doesn't match
-			 * max's cookie.
-			 *
-			 * NOTE: this is a linear max-filter and is thus bounded
-			 * in execution time.
-			 */
-			if (!max || !cookie_match(max, p)) {
-				struct task_struct *old_max = max;
-
-				rq->core->core_cookie = p->core_cookie;
-				max = p;
-
-				if (old_max) {
-					rq->core->core_forceidle = false;
-					for_each_cpu(j, smt_mask) {
-						if (j == i)
-							continue;
-
-						cpu_rq(j)->core_pick = NULL;
-					}
-					occ = 1;
-					goto again;
-				}
-			}
+		} else {
+			occ++;
 		}
 	}
 
@@ -5643,7 +5576,7 @@ pick_next_task(struct rq *rq, struct task_struct *prev, struct rq_flags *rf)
 	 * non-matching user state.
 	 */
 	for_each_cpu(i, smt_mask) {
-		struct rq *rq_i = cpu_rq(i);
+		rq_i = cpu_rq(i);
 
 		/*
 		 * An online sibling might have gone offline before a task
kernel/sched/sched.h +1 -0
index d9f8d73a1d84..0760b460903a 100644
@@ -1091,6 +1091,7 @@ struct rq {
 	/* per rq */
 	struct rq		*core;
 	struct task_struct	*core_pick;
+	struct task_struct	*core_temp;
 	unsigned int		core_enabled;
 	unsigned int		core_sched_seq;
 	struct rb_root		core_tree;
#4 lore raw

Hi Peter,

Quoted 125 lines · Peter Zijlstra
Quoted 16 lines · Josh Don

For core-sched, pick_next_task will update the 'max' task if there is a cookie mismatch (since in this case the new task must be of higher priority than the current max). However, we fail to update 'max' if we've found a task with a matching cookie and higher priority than 'max'.

This can result in extra iterations on SMT-X machines, where X > 2.

As an example, on a machine with SMT=3, on core 0, SMT-0 might pick the following, in order:

- SMT-0: p1, with cookie A, and priority 10 (max = p1)
- SMT-1: p2, with cookie A, and priority 30 (max not updated here)
- SMT-2: p3, with cookie B, and priority 20 (max = p2) > invalidate the other picks and retry

Quoted 4 lines

Here, we should have instead updated 'max' when picking for SMT-1. Note that this code would eventually have righted itself, since the retry loop would re-pick p2, and update 'max' accordingly. However, this patch avoids the extra round-trip.

Going with the observation Tao made; how about we rewrite the whole lot to not be mind-bending complicated :-)

How's this? It seems to build and pass the core-sched selftest thingy (so it must be perfect, right? :-)

---
 kernel/sched/core.c  | 147 ++++++++++++++-------------------------------------
 kernel/sched/sched.h |   1 +
 2 files changed, 41 insertions(+), 107 deletions(-)
kernel/sched/core.c +12 -55
index ceae25ea8a0e..e896250c2fb8 100644
@@ -5404,66 +5404,18 @@ static inline bool cookie_match(struct task_struct *a, struct task_struct *b)
 	return a->core_cookie == b->core_cookie;
 }
 
-// XXX fairness/fwd progress conditions
-/*
- * Returns
- * - NULL if there is no runnable task for this class.
- * - the highest priority task for this runqueue if it matches
- *   rq->core->core_cookie or its priority is greater than max.
- * - Else returns idle_task.
- */
-static struct task_struct *
-pick_task(struct rq *rq, const struct sched_class *class, struct task_struct *max, bool in_fi)
-{
-	struct task_struct *class_pick, *cookie_pick;
-	unsigned long cookie = rq->core->core_cookie;
-
-	class_pick = class->pick_task(rq);
-	if (!class_pick)
-		return NULL;
-
-	if (!cookie) {
-		/*
-		 * If class_pick is tagged, return it only if it has
-		 * higher priority than max.
-		 */
-		if (max && class_pick->core_cookie &&
-		    prio_less(class_pick, max, in_fi))
-			return idle_sched_class.pick_task(rq);
-
-		return class_pick;
-	}
-
-	/*
-	 * If class_pick is idle or matches cookie, return early.
-	 */
-	if (cookie_equals(class_pick, cookie))
-		return class_pick;
-
-	cookie_pick = sched_core_find(rq, cookie);
-
-	/*
-	 * If class > max && class > cookie, it is the highest priority task on
-	 * the core (so far) and it must be selected, otherwise we must go with
-	 * the cookie pick in order to satisfy the constraint.
-	 */
-	if (prio_less(cookie_pick, class_pick, in_fi) &&
-	    (!max || prio_less(max, class_pick, in_fi)))
-		return class_pick;
-
-	return cookie_pick;
-}
-
 extern void task_vruntime_update(struct rq *rq, struct task_struct *p, bool in_fi);
 
 static struct task_struct *
 pick_next_task(struct rq *rq, struct task_struct *prev, struct rq_flags *rf)
 {
-	struct task_struct *next, *max = NULL;
+	struct task_struct *next, *p, *max = NULL;
 	const struct sched_class *class;
 	const struct cpumask *smt_mask;
 	bool fi_before = false;
-	int i, j, cpu, occ = 0;
+	unsigned long cookie;
+	int i, cpu, occ = 0;
+	struct rq *rq_i;
 	bool need_sync;
 
 	if (!sched_core_enabled(rq))
@@ -5554,76 +5506,57 @@ pick_next_task(struct rq *rq, struct task_struct *prev, struct rq_flags *rf)
 		}
 	}
 
-	for_each_cpu(i, smt_mask) {
-		struct rq *rq_i = cpu_rq(i);
-
+	/*
+	 * For each thread: do the regular task pick and find the max prio task
+	 * amongst them.
+	 *
+	 * Tie-break prio towards the current CPU
+	 */
+	for_each_cpu_wrap(i, smt_mask, cpu) {
+		rq_i = cpu_rq(i);
 		rq_i->core_pick = NULL;
 

kernel/sched/core.c pick_next_task(struct rq *rq, struct task_struct *prev, struct rq_flags *rf) · line 5528

Quoted 10 lines
kernel/sched/core.c +8 -0
 		if (i != cpu)
 			update_rq_clock(rq_i);
+
+		for_each_class(class) {
+			p = rq_i->core_temp = class->pick_task(rq_i);
+			if (p)
+				break;
+		}
+
+		if (!max || prio_less(max, p, fi_before))

The above 'prio_less(max, p, fi_before)' condition covers the case of Josh's fix if I'm not wrong.

The rewriting code looks clarity and simpler..

Quoted 99 lines
kernel/sched/core.c +20 -52
+			max = p;
 	}
 
+	cookie = rq->core->core_cookie = max->core_cookie;
+
 	/*
-	 * Try and select tasks for each sibling in descending sched_class
-	 * order.
+	 * For each thread: try and find a runnable task that matches @max or
+	 * force idle.
 	 */
-	for_each_class(class) {
-again:
-		for_each_cpu_wrap(i, smt_mask, cpu) {
-			struct rq *rq_i = cpu_rq(i);
-			struct task_struct *p;
-
-			if (rq_i->core_pick)
-				continue;
+	for_each_cpu(i, smt_mask) {
+		rq_i = cpu_rq(i);
+		p = rq_i->core_temp;
 
-			/*
-			 * If this sibling doesn't yet have a suitable task to
-			 * run; ask for the most eligible task, given the
-			 * highest priority task already selected for this
-			 * core.
-			 */
-			p = pick_task(rq_i, class, max, fi_before);
+		if (!cookie_equals(p, cookie)) {
+			p = NULL;
+			if (cookie)
+				p = sched_core_find(rq_i, cookie);
 			if (!p)
-				continue;
+				p = idle_sched_class.pick_task(rq_i);
+		}
 
-			if (!is_task_rq_idle(p))
-				occ++;
+		rq_i->core_pick = p;
 
-			rq_i->core_pick = p;
-			if (rq_i->idle == p && rq_i->nr_running) {
+		if (p == rq_i->idle) {
+			if (rq_i->nr_running) {
 				rq->core->core_forceidle = true;
 				if (!fi_before)
 					rq->core->core_forceidle_seq++;
 			}
-
-			/*
-			 * If this new candidate is of higher priority than the
-			 * previous; and they're incompatible; we need to wipe
-			 * the slate and start over. pick_task makes sure that
-			 * p's priority is more than max if it doesn't match
-			 * max's cookie.
-			 *
-			 * NOTE: this is a linear max-filter and is thus bounded
-			 * in execution time.
-			 */
-			if (!max || !cookie_match(max, p)) {
-				struct task_struct *old_max = max;
-
-				rq->core->core_cookie = p->core_cookie;
-				max = p;
-
-				if (old_max) {
-					rq->core->core_forceidle = false;
-					for_each_cpu(j, smt_mask) {
-						if (j == i)
-							continue;
-
-						cpu_rq(j)->core_pick = NULL;
-					}
-					occ = 1;
-					goto again;
-				}
-			}
+		} else {
+			occ++;
 		}
 	}
 
@@ -5643,7 +5576,7 @@ pick_next_task(struct rq *rq, struct task_struct *prev, struct rq_flags *rf)
 	 * non-matching user state.
 	 */
 	for_each_cpu(i, smt_mask) {
-		struct rq *rq_i = cpu_rq(i);
+		rq_i = cpu_rq(i);
 
 		/*
 		 * An online sibling might have gone offline before a task
kernel/sched/sched.h +0 -0
index d9f8d73a1d84..0760b460903a 100644

kernel/sched/sched.h struct rq { · line 1097

Quoted 7 lines
kernel/sched/sched.h +1 -0
@@ -1091,6 +1091,7 @@ struct rq {
 	/* per rq */
 	struct rq		*core;
 	struct task_struct	*core_pick;
+	struct task_struct	*core_temp;
 	unsigned int		core_enabled;
 	unsigned int		core_sched_seq;
 	struct rb_root		core_tree;

Thanks,
Tao

#5 lore raw
In reply to Peter Zijlstra

Hi Peter,

Quoted 11 lines
Quoted 4 lines

Here, we should have instead updated 'max' when picking for SMT-1. Note that this code would eventually have righted itself, since the retry loop would re-pick p2, and update 'max' accordingly. However, this patch avoids the extra round-trip.

Going with the observation Tao made; how about we rewrite the whole lot to not be mind-bending complicated :-)

How's this? It seems to build and pass the core-sched selftest thingy (so it must be perfect, right? :-)

Nice, the code is much simpler now :-). A minor suggestion down..

Quoted 8 lines
kernel/sched/core.c +5 -3
-       for_each_cpu(i, smt_mask) {
-               struct rq *rq_i = cpu_rq(i);
-
+       /*
+        * For each thread: do the regular task pick and find the max prio task
+        * amongst them.
+        *
+        * Tie-break prio towards the current CPU

kernel/sched/core.c pick_next_task(struct rq *rq, struct task_struct *prev, struct rq_flags *rf) · line 5523

Quoted 10 lines
kernel/sched/core.c +6 -0
+        */
+       for_each_cpu_wrap(i, smt_mask, cpu) {
+               rq_i = cpu_rq(i);
                rq_i->core_pick = NULL;
 
                if (i != cpu)
                        update_rq_clock(rq_i);
+
+               for_each_class(class) {
+                       p = rq_i->core_temp = class->pick_task(rq_i);

I think we can use core_pick to store the pick here and core_temp might not be required. What do you feel?

kernel/sched/core.c pick_next_task(struct rq *rq, struct task_struct *prev, struct rq_flags *rf) · line 5529

Quoted 6 lines
kernel/sched/core.c +6 -0
+                       if (p)
+                               break;
+               }
+
+               if (!max || prio_less(max, p, fi_before))
+                       max = p;

Thanks,
Vineeth

#6 lore raw

Hi Vineeth,

Quoted 29 lines · Vineeth Pillai

Hi Peter,

Quoted 11 lines
Quoted 4 lines

Here, we should have instead updated 'max' when picking for SMT-1. Note that this code would eventually have righted itself, since the retry loop would re-pick p2, and update 'max' accordingly. However, this patch avoids the extra round-trip.

Going with the observation Tao made; how about we rewrite the whole lot to not be mind-bending complicated :-)

How's this? It seems to build and pass the core-sched selftest thingy (so it must be perfect, right? :-)

Nice, the code is much simpler now :-). A minor suggestion down..

Quoted 13 lines
kernel/sched/core.c +8 -3
-       for_each_cpu(i, smt_mask) {
-               struct rq *rq_i = cpu_rq(i);
-
+       /*
+        * For each thread: do the regular task pick and find the max prio task
+        * amongst them.
+        *
+        * Tie-break prio towards the current CPU
+        */
+       for_each_cpu_wrap(i, smt_mask, cpu) {
+               rq_i = cpu_rq(i);
                rq_i->core_pick = NULL;
Quoted 7 lines

kernel/sched/core.c pick_next_task(struct rq *rq, struct task_struct *prev, struct rq_flags *rf) · line 5523

Quoted 5 lines
                if (i != cpu)
                        update_rq_clock(rq_i);
kernel/sched/core.c +3 -0
+
+               for_each_class(class) {
+                       p = rq_i->core_temp = class->pick_task(rq_i);

I think we can use core_pick to store the pick here and core_temp might not be required. What do you feel?

You're right.

The @core_temp load the class pick, the @core_pick is the final pick(class or cookie). Using @core_pick to store class pick first and then the final pick is right and save the bytes) but just a little not clarity from my end :-)

Quoted 10 lines

kernel/sched/core.c pick_next_task(struct rq *rq, struct task_struct *prev, struct rq_flags *rf) · line 5529

Quoted 6 lines
kernel/sched/core.c +6 -0
+                       if (p)
+                               break;
+               }
+
+               if (!max || prio_less(max, p, fi_before))
+                       max = p;

Thanks,
Vineeth

Thanks,
Tao

maintainer
#7 lore raw
In reply to Vineeth Pillai
Quoted 29 lines · Vineeth Pillai

Hi Peter,

Quoted 11 lines
Quoted 4 lines

Here, we should have instead updated 'max' when picking for SMT-1. Note that this code would eventually have righted itself, since the retry loop would re-pick p2, and update 'max' accordingly. However, this patch avoids the extra round-trip.

Going with the observation Tao made; how about we rewrite the whole lot to not be mind-bending complicated :-)

How's this? It seems to build and pass the core-sched selftest thingy (so it must be perfect, right? :-)

Nice, the code is much simpler now :-). A minor suggestion down..

Quoted 13 lines
kernel/sched/core.c +8 -3
-       for_each_cpu(i, smt_mask) {
-               struct rq *rq_i = cpu_rq(i);
-
+       /*
+        * For each thread: do the regular task pick and find the max prio task
+        * amongst them.
+        *
+        * Tie-break prio towards the current CPU
+        */
+       for_each_cpu_wrap(i, smt_mask, cpu) {
+               rq_i = cpu_rq(i);
                rq_i->core_pick = NULL;
Quoted 7 lines

kernel/sched/core.c pick_next_task(struct rq *rq, struct task_struct *prev, struct rq_flags *rf) · line 5523

Quoted 5 lines
                if (i != cpu)
                        update_rq_clock(rq_i);
kernel/sched/core.c +3 -0
+
+               for_each_class(class) {
+                       p = rq_i->core_temp = class->pick_task(rq_i);

I think we can use core_pick to store the pick here and core_temp might not be required. What do you feel?

Indeed we can; makes the code a little less obvious but saves a few bytes.

Let me go do that and also attempt a Changelog to go with it ;-)

maintainer
#8 lore raw

PATCH 1/1 sched/core: Simplify core-wide task selection

Quoted 1 line · Peter Zijlstra

Let me go do that and also attempt a Changelog to go with it ;-)

How's this then?

---
Subject: sched/core: Simplify core-wide task selection
From: Peter Zijlstra <[email protected]>
Date: Tue Aug 24 11:05:47 CEST 2021

Tao suggested a two-pass task selection to avoid the retry loop.

Not only does it avoid the retry loop, it results in *much* simpler code.

This also fixes an issue spotted by Josh Don where, for SMT3+, we can forget to update max on the first pass and get to do an extra round.

---
 kernel/sched/core.c | 156 +++++++++++++++-------------------------------------
 1 file changed, 45 insertions(+), 111 deletions(-)
kernel/sched/core.c +45 -111
index ceae25ea8a0e..8a9a32df5f38 100644
@@ -5381,8 +5381,7 @@ __pick_next_task(struct rq *rq, struct task_struct *prev, struct rq_flags *rf)
 			return p;
 	}
 
-	/* The idle class should always have a runnable task: */
-	BUG();
+	BUG(); /* The idle class should always have a runnable task. */
 }
 
 #ifdef CONFIG_SCHED_CORE
@@ -5404,54 +5403,18 @@ static inline bool cookie_match(struct task_struct *a, struct task_struct *b)
 	return a->core_cookie == b->core_cookie;
 }
 
-// XXX fairness/fwd progress conditions
-/*
- * Returns
- * - NULL if there is no runnable task for this class.
- * - the highest priority task for this runqueue if it matches
- *   rq->core->core_cookie or its priority is greater than max.
- * - Else returns idle_task.
- */
-static struct task_struct *
-pick_task(struct rq *rq, const struct sched_class *class, struct task_struct *max, bool in_fi)
+static inline struct task_struct *pick_task(struct rq *rq)
 {
-	struct task_struct *class_pick, *cookie_pick;
-	unsigned long cookie = rq->core->core_cookie;
-
-	class_pick = class->pick_task(rq);
-	if (!class_pick)
-		return NULL;
-
-	if (!cookie) {
-		/*
-		 * If class_pick is tagged, return it only if it has
-		 * higher priority than max.
-		 */
-		if (max && class_pick->core_cookie &&
-		    prio_less(class_pick, max, in_fi))
-			return idle_sched_class.pick_task(rq);
+	const struct sched_class *class;
+	struct task_struct *p;
 
-		return class_pick;
+	for_each_class(class) {
+		p = class->pick_task(rq);
+		if (p)
+			return p;
 	}
 
-	/*
-	 * If class_pick is idle or matches cookie, return early.
-	 */
-	if (cookie_equals(class_pick, cookie))
-		return class_pick;
-
-	cookie_pick = sched_core_find(rq, cookie);
-
-	/*
-	 * If class > max && class > cookie, it is the highest priority task on
-	 * the core (so far) and it must be selected, otherwise we must go with
-	 * the cookie pick in order to satisfy the constraint.
-	 */
-	if (prio_less(cookie_pick, class_pick, in_fi) &&
-	    (!max || prio_less(max, class_pick, in_fi)))
-		return class_pick;
-
-	return cookie_pick;
+	BUG(); /* The idle class should always have a runnable task. */
 }
 
 extern void task_vruntime_update(struct rq *rq, struct task_struct *p, bool in_fi);
@@ -5459,11 +5422,12 @@ extern void task_vruntime_update(struct rq *rq, struct task_struct *p, bool in_f
 static struct task_struct *
 pick_next_task(struct rq *rq, struct task_struct *prev, struct rq_flags *rf)
 {
-	struct task_struct *next, *max = NULL;
-	const struct sched_class *class;
+	struct task_struct *next, *p, *max = NULL;
 	const struct cpumask *smt_mask;
 	bool fi_before = false;
-	int i, j, cpu, occ = 0;
+	unsigned long cookie;
+	int i, cpu, occ = 0;
+	struct rq *rq_i;
 	bool need_sync;
 
 	if (!sched_core_enabled(rq))
@@ -5536,12 +5500,7 @@ pick_next_task(struct rq *rq, struct task_struct *prev, struct rq_flags *rf)
 	 * and there are no cookied tasks running on siblings.
 	 */
 	if (!need_sync) {
-		for_each_class(class) {
-			next = class->pick_task(rq);
-			if (next)
-				break;
-		}
-
+		next = pick_task(rq);
 		if (!next->core_cookie) {
 			rq->core_pick = NULL;
 			/*
@@ -5554,76 +5513,51 @@ pick_next_task(struct rq *rq, struct task_struct *prev, struct rq_flags *rf)
 		}
 	}
 
-	for_each_cpu(i, smt_mask) {
-		struct rq *rq_i = cpu_rq(i);
-
-		rq_i->core_pick = NULL;
+	/*
+	 * For each thread: do the regular task pick and find the max prio task
+	 * amongst them.
+	 *
+	 * Tie-break prio towards the current CPU
+	 */
+	for_each_cpu_wrap(i, smt_mask, cpu) {
+		rq_i = cpu_rq(i);
 
 		if (i != cpu)
 			update_rq_clock(rq_i);
+
+		p = rq_i->core_pick = pick_task(rq_i);
+		if (!max || prio_less(max, p, fi_before))
+			max = p;
 	}
 
+	cookie = rq->core->core_cookie = max->core_cookie;
+
 	/*
-	 * Try and select tasks for each sibling in descending sched_class
-	 * order.
+	 * For each thread: try and find a runnable task that matches @max or
+	 * force idle.
 	 */
-	for_each_class(class) {
-again:
-		for_each_cpu_wrap(i, smt_mask, cpu) {
-			struct rq *rq_i = cpu_rq(i);
-			struct task_struct *p;
-
-			if (rq_i->core_pick)
-				continue;
+	for_each_cpu(i, smt_mask) {
+		rq_i = cpu_rq(i);
+		p = rq_i->core_pick;
 
-			/*
-			 * If this sibling doesn't yet have a suitable task to
-			 * run; ask for the most eligible task, given the
-			 * highest priority task already selected for this
-			 * core.
-			 */
-			p = pick_task(rq_i, class, max, fi_before);
+		if (!cookie_equals(p, cookie)) {
+			p = NULL;
+			if (cookie)
+				p = sched_core_find(rq_i, cookie);
 			if (!p)
-				continue;
+				p = idle_sched_class.pick_task(rq_i);
+		}
 
-			if (!is_task_rq_idle(p))
-				occ++;
+		rq_i->core_pick = p;
 
-			rq_i->core_pick = p;
-			if (rq_i->idle == p && rq_i->nr_running) {
+		if (p == rq_i->idle) {
+			if (rq_i->nr_running) {
 				rq->core->core_forceidle = true;
 				if (!fi_before)
 					rq->core->core_forceidle_seq++;
 			}
-
-			/*
-			 * If this new candidate is of higher priority than the
-			 * previous; and they're incompatible; we need to wipe
-			 * the slate and start over. pick_task makes sure that
-			 * p's priority is more than max if it doesn't match
-			 * max's cookie.
-			 *
-			 * NOTE: this is a linear max-filter and is thus bounded
-			 * in execution time.
-			 */
-			if (!max || !cookie_match(max, p)) {
-				struct task_struct *old_max = max;
-
-				rq->core->core_cookie = p->core_cookie;
-				max = p;
-
-				if (old_max) {
-					rq->core->core_forceidle = false;
-					for_each_cpu(j, smt_mask) {
-						if (j == i)
-							continue;
-
-						cpu_rq(j)->core_pick = NULL;
-					}
-					occ = 1;
-					goto again;
-				}
-			}
+		} else {
+			occ++;
 		}
 	}
 
@@ -5643,7 +5577,7 @@ pick_next_task(struct rq *rq, struct task_struct *prev, struct rq_flags *rf)
 	 * non-matching user state.
 	 */
 	for_each_cpu(i, smt_mask) {
-		struct rq *rq_i = cpu_rq(i);
+		rq_i = cpu_rq(i);
 
 		/*
 		 * An online sibling might have gone offline before a task
#9 lore raw

Re: [PATCH] sched/core: Simplify core-wide task selection

Hi Peter,

Quoted 29 lines · Peter Zijlstra
Quoted 1 line · Peter Zijlstra

Let me go do that and also attempt a Changelog to go with it ;-)

How's this then?

---
Subject: sched/core: Simplify core-wide task selection
From: Peter Zijlstra <[email protected]>
Date: Tue Aug 24 11:05:47 CEST 2021

Tao suggested a two-pass task selection to avoid the retry loop.

Not only does it avoid the retry loop, it results in *much* simpler code.

This also fixes an issue spotted by Josh Don where, for SMT3+, we can forget to update max on the first pass and get to do an extra round.

---
 kernel/sched/core.c | 156 +++++++++++++++-------------------------------------
 1 file changed, 45 insertions(+), 111 deletions(-)
kernel/sched/core.c +0 -0
index ceae25ea8a0e..8a9a32df5f38 100644

kernel/sched/core.c __pick_next_task(struct rq *rq, struct task_struct *prev, struct rq_flags *rf) · line 5384

Quoted 6 lines
kernel/sched/core.c +1 -2
@@ -5381,8 +5381,7 @@ __pick_next_task(struct rq *rq, struct task_struct *prev, struct rq_flags *rf)
 			return p;
 	}
 
-	/* The idle class should always have a runnable task: */
-	BUG();
+	BUG(); /* The idle class should always have a runnable task. */

How can use pick_task() here instead.

The Reported-by is comfortable and enough for me.

Otherwise, Look good to me.

Quoted 204 lines
kernel/sched/core.c +43 -108
 }
 
 #ifdef CONFIG_SCHED_CORE
@@ -5404,54 +5403,18 @@ static inline bool cookie_match(struct task_struct *a, struct task_struct *b)
 	return a->core_cookie == b->core_cookie;
 }
 
-// XXX fairness/fwd progress conditions
-/*
- * Returns
- * - NULL if there is no runnable task for this class.
- * - the highest priority task for this runqueue if it matches
- *   rq->core->core_cookie or its priority is greater than max.
- * - Else returns idle_task.
- */
-static struct task_struct *
-pick_task(struct rq *rq, const struct sched_class *class, struct task_struct *max, bool in_fi)
+static inline struct task_struct *pick_task(struct rq *rq)
 {
-	struct task_struct *class_pick, *cookie_pick;
-	unsigned long cookie = rq->core->core_cookie;
-
-	class_pick = class->pick_task(rq);
-	if (!class_pick)
-		return NULL;
-
-	if (!cookie) {
-		/*
-		 * If class_pick is tagged, return it only if it has
-		 * higher priority than max.
-		 */
-		if (max && class_pick->core_cookie &&
-		    prio_less(class_pick, max, in_fi))
-			return idle_sched_class.pick_task(rq);
+	const struct sched_class *class;
+	struct task_struct *p;
 
-		return class_pick;
+	for_each_class(class) {
+		p = class->pick_task(rq);
+		if (p)
+			return p;
 	}
 
-	/*
-	 * If class_pick is idle or matches cookie, return early.
-	 */
-	if (cookie_equals(class_pick, cookie))
-		return class_pick;
-
-	cookie_pick = sched_core_find(rq, cookie);
-
-	/*
-	 * If class > max && class > cookie, it is the highest priority task on
-	 * the core (so far) and it must be selected, otherwise we must go with
-	 * the cookie pick in order to satisfy the constraint.
-	 */
-	if (prio_less(cookie_pick, class_pick, in_fi) &&
-	    (!max || prio_less(max, class_pick, in_fi)))
-		return class_pick;
-
-	return cookie_pick;
+	BUG(); /* The idle class should always have a runnable task. */
 }
 
 extern void task_vruntime_update(struct rq *rq, struct task_struct *p, bool in_fi);
@@ -5459,11 +5422,12 @@ extern void task_vruntime_update(struct rq *rq, struct task_struct *p, bool in_f
 static struct task_struct *
 pick_next_task(struct rq *rq, struct task_struct *prev, struct rq_flags *rf)
 {
-	struct task_struct *next, *max = NULL;
-	const struct sched_class *class;
+	struct task_struct *next, *p, *max = NULL;
 	const struct cpumask *smt_mask;
 	bool fi_before = false;
-	int i, j, cpu, occ = 0;
+	unsigned long cookie;
+	int i, cpu, occ = 0;
+	struct rq *rq_i;
 	bool need_sync;
 
 	if (!sched_core_enabled(rq))
@@ -5536,12 +5500,7 @@ pick_next_task(struct rq *rq, struct task_struct *prev, struct rq_flags *rf)
 	 * and there are no cookied tasks running on siblings.
 	 */
 	if (!need_sync) {
-		for_each_class(class) {
-			next = class->pick_task(rq);
-			if (next)
-				break;
-		}
-
+		next = pick_task(rq);
 		if (!next->core_cookie) {
 			rq->core_pick = NULL;
 			/*
@@ -5554,76 +5513,51 @@ pick_next_task(struct rq *rq, struct task_struct *prev, struct rq_flags *rf)
 		}
 	}
 
-	for_each_cpu(i, smt_mask) {
-		struct rq *rq_i = cpu_rq(i);
-
-		rq_i->core_pick = NULL;
+	/*
+	 * For each thread: do the regular task pick and find the max prio task
+	 * amongst them.
+	 *
+	 * Tie-break prio towards the current CPU
+	 */
+	for_each_cpu_wrap(i, smt_mask, cpu) {
+		rq_i = cpu_rq(i);
 
 		if (i != cpu)
 			update_rq_clock(rq_i);
+
+		p = rq_i->core_pick = pick_task(rq_i);
+		if (!max || prio_less(max, p, fi_before))
+			max = p;
 	}
 
+	cookie = rq->core->core_cookie = max->core_cookie;
+
 	/*
-	 * Try and select tasks for each sibling in descending sched_class
-	 * order.
+	 * For each thread: try and find a runnable task that matches @max or
+	 * force idle.
 	 */
-	for_each_class(class) {
-again:
-		for_each_cpu_wrap(i, smt_mask, cpu) {
-			struct rq *rq_i = cpu_rq(i);
-			struct task_struct *p;
-
-			if (rq_i->core_pick)
-				continue;
+	for_each_cpu(i, smt_mask) {
+		rq_i = cpu_rq(i);
+		p = rq_i->core_pick;
 
-			/*
-			 * If this sibling doesn't yet have a suitable task to
-			 * run; ask for the most eligible task, given the
-			 * highest priority task already selected for this
-			 * core.
-			 */
-			p = pick_task(rq_i, class, max, fi_before);
+		if (!cookie_equals(p, cookie)) {
+			p = NULL;
+			if (cookie)
+				p = sched_core_find(rq_i, cookie);
 			if (!p)
-				continue;
+				p = idle_sched_class.pick_task(rq_i);
+		}
 
-			if (!is_task_rq_idle(p))
-				occ++;
+		rq_i->core_pick = p;
 
-			rq_i->core_pick = p;
-			if (rq_i->idle == p && rq_i->nr_running) {
+		if (p == rq_i->idle) {
+			if (rq_i->nr_running) {
 				rq->core->core_forceidle = true;
 				if (!fi_before)
 					rq->core->core_forceidle_seq++;
 			}
-
-			/*
-			 * If this new candidate is of higher priority than the
-			 * previous; and they're incompatible; we need to wipe
-			 * the slate and start over. pick_task makes sure that
-			 * p's priority is more than max if it doesn't match
-			 * max's cookie.
-			 *
-			 * NOTE: this is a linear max-filter and is thus bounded
-			 * in execution time.
-			 */
-			if (!max || !cookie_match(max, p)) {
-				struct task_struct *old_max = max;
-
-				rq->core->core_cookie = p->core_cookie;
-				max = p;
-
-				if (old_max) {
-					rq->core->core_forceidle = false;
-					for_each_cpu(j, smt_mask) {
-						if (j == i)
-							continue;
-
-						cpu_rq(j)->core_pick = NULL;
-					}
-					occ = 1;
-					goto again;
-				}
-			}
+		} else {
+			occ++;
 		}
 	}
 

kernel/sched/core.c pick_next_task(struct rq *rq, struct task_struct *prev, struct rq_flags *rf) · line 5583

Quoted 8 lines
kernel/sched/core.c +1 -1
@@ -5643,7 +5577,7 @@ pick_next_task(struct rq *rq, struct task_struct *prev, struct rq_flags *rf)
 	 * non-matching user state.
 	 */
 	for_each_cpu(i, smt_mask) {
-		struct rq *rq_i = cpu_rq(i);
+		rq_i = cpu_rq(i);
 
 		/*
 		 * An online sibling might have gone offline before a task

Thanks,
Tao

author Reviewed-by on v1 1/1
#10 lore raw

Re: [PATCH] sched/core: Simplify core-wide task selection

In reply to Peter Zijlstra
Quoted 13 lines · Peter Zijlstra
Quoted 1 line · Peter Zijlstra

Let me go do that and also attempt a Changelog to go with it ;-)

How's this then?

---
Subject: sched/core: Simplify core-wide task selection
From: Peter Zijlstra <[email protected]>
Date: Tue Aug 24 11:05:47 CEST 2021

Tao suggested a two-pass task selection to avoid the retry loop.

Quoted 8 lines

Not only does it avoid the retry loop, it results in *much* simpler code.

This also fixes an issue spotted by Josh Don where, for SMT3+, we can forget to update max on the first pass and get to do an extra round.

Quoted 227 lines
---
 kernel/sched/core.c | 156 +++++++++++++++-------------------------------------
 1 file changed, 45 insertions(+), 111 deletions(-)
kernel/sched/core.c +45 -111
index ceae25ea8a0e..8a9a32df5f38 100644
@@ -5381,8 +5381,7 @@ __pick_next_task(struct rq *rq, struct task_struct *prev, struct rq_flags *rf)
                        return p;
        }
 
-       /* The idle class should always have a runnable task: */
-       BUG();
+       BUG(); /* The idle class should always have a runnable task. */
 }
 
 #ifdef CONFIG_SCHED_CORE
@@ -5404,54 +5403,18 @@ static inline bool cookie_match(struct task_struct *a, struct task_struct *b)
        return a->core_cookie == b->core_cookie;
 }
 
-// XXX fairness/fwd progress conditions
-/*
- * Returns
- * - NULL if there is no runnable task for this class.
- * - the highest priority task for this runqueue if it matches
- *   rq->core->core_cookie or its priority is greater than max.
- * - Else returns idle_task.
- */
-static struct task_struct *
-pick_task(struct rq *rq, const struct sched_class *class, struct task_struct *max, bool in_fi)
+static inline struct task_struct *pick_task(struct rq *rq)
 {
-       struct task_struct *class_pick, *cookie_pick;
-       unsigned long cookie = rq->core->core_cookie;
-
-       class_pick = class->pick_task(rq);
-       if (!class_pick)
-               return NULL;
-
-       if (!cookie) {
-               /*
-                * If class_pick is tagged, return it only if it has
-                * higher priority than max.
-                */
-               if (max && class_pick->core_cookie &&
-                   prio_less(class_pick, max, in_fi))
-                       return idle_sched_class.pick_task(rq);
+       const struct sched_class *class;
+       struct task_struct *p;
 
-               return class_pick;
+       for_each_class(class) {
+               p = class->pick_task(rq);
+               if (p)
+                       return p;
        }
 
-       /*
-        * If class_pick is idle or matches cookie, return early.
-        */
-       if (cookie_equals(class_pick, cookie))
-               return class_pick;
-
-       cookie_pick = sched_core_find(rq, cookie);
-
-       /*
-        * If class > max && class > cookie, it is the highest priority task on
-        * the core (so far) and it must be selected, otherwise we must go with
-        * the cookie pick in order to satisfy the constraint.
-        */
-       if (prio_less(cookie_pick, class_pick, in_fi) &&
-           (!max || prio_less(max, class_pick, in_fi)))
-               return class_pick;
-
-       return cookie_pick;
+       BUG(); /* The idle class should always have a runnable task. */
 }
 
 extern void task_vruntime_update(struct rq *rq, struct task_struct *p, bool in_fi);
@@ -5459,11 +5422,12 @@ extern void task_vruntime_update(struct rq *rq, struct task_struct *p, bool in_f
 static struct task_struct *
 pick_next_task(struct rq *rq, struct task_struct *prev, struct rq_flags *rf)
 {
-       struct task_struct *next, *max = NULL;
-       const struct sched_class *class;
+       struct task_struct *next, *p, *max = NULL;
        const struct cpumask *smt_mask;
        bool fi_before = false;
-       int i, j, cpu, occ = 0;
+       unsigned long cookie;
+       int i, cpu, occ = 0;
+       struct rq *rq_i;
        bool need_sync;
 
        if (!sched_core_enabled(rq))
@@ -5536,12 +5500,7 @@ pick_next_task(struct rq *rq, struct task_struct *prev, struct rq_flags *rf)
         * and there are no cookied tasks running on siblings.
         */
        if (!need_sync) {
-               for_each_class(class) {
-                       next = class->pick_task(rq);
-                       if (next)
-                               break;
-               }
-
+               next = pick_task(rq);
                if (!next->core_cookie) {
                        rq->core_pick = NULL;
                        /*
@@ -5554,76 +5513,51 @@ pick_next_task(struct rq *rq, struct task_struct *prev, struct rq_flags *rf)
                }
        }
 
-       for_each_cpu(i, smt_mask) {
-               struct rq *rq_i = cpu_rq(i);
-
-               rq_i->core_pick = NULL;
+       /*
+        * For each thread: do the regular task pick and find the max prio task
+        * amongst them.
+        *
+        * Tie-break prio towards the current CPU
+        */
+       for_each_cpu_wrap(i, smt_mask, cpu) {
+               rq_i = cpu_rq(i);
 
                if (i != cpu)
                        update_rq_clock(rq_i);
+
+               p = rq_i->core_pick = pick_task(rq_i);
+               if (!max || prio_less(max, p, fi_before))
+                       max = p;
        }
 
+       cookie = rq->core->core_cookie = max->core_cookie;
+
        /*
-        * Try and select tasks for each sibling in descending sched_class
-        * order.
+        * For each thread: try and find a runnable task that matches @max or
+        * force idle.
         */
-       for_each_class(class) {
-again:
-               for_each_cpu_wrap(i, smt_mask, cpu) {
-                       struct rq *rq_i = cpu_rq(i);
-                       struct task_struct *p;
-
-                       if (rq_i->core_pick)
-                               continue;
+       for_each_cpu(i, smt_mask) {
+               rq_i = cpu_rq(i);
+               p = rq_i->core_pick;
 
-                       /*
-                        * If this sibling doesn't yet have a suitable task to
-                        * run; ask for the most eligible task, given the
-                        * highest priority task already selected for this
-                        * core.
-                        */
-                       p = pick_task(rq_i, class, max, fi_before);
+               if (!cookie_equals(p, cookie)) {
+                       p = NULL;
+                       if (cookie)
+                               p = sched_core_find(rq_i, cookie);
                        if (!p)
-                               continue;
+                               p = idle_sched_class.pick_task(rq_i);
+               }
 
-                       if (!is_task_rq_idle(p))
-                               occ++;
+               rq_i->core_pick = p;
 
-                       rq_i->core_pick = p;
-                       if (rq_i->idle == p && rq_i->nr_running) {
+               if (p == rq_i->idle) {
+                       if (rq_i->nr_running) {
                                rq->core->core_forceidle = true;
                                if (!fi_before)
                                        rq->core->core_forceidle_seq++;
                        }
-
-                       /*
-                        * If this new candidate is of higher priority than the
-                        * previous; and they're incompatible; we need to wipe
-                        * the slate and start over. pick_task makes sure that
-                        * p's priority is more than max if it doesn't match
-                        * max's cookie.
-                        *
-                        * NOTE: this is a linear max-filter and is thus bounded
-                        * in execution time.
-                        */
-                       if (!max || !cookie_match(max, p)) {
-                               struct task_struct *old_max = max;
-
-                               rq->core->core_cookie = p->core_cookie;
-                               max = p;
-
-                               if (old_max) {
-                                       rq->core->core_forceidle = false;
-                                       for_each_cpu(j, smt_mask) {
-                                               if (j == i)
-                                                       continue;
-
-                                               cpu_rq(j)->core_pick = NULL;
-                                       }
-                                       occ = 1;
-                                       goto again;
-                               }
-                       }
+               } else {
+                       occ++;
                }
        }
 
@@ -5643,7 +5577,7 @@ pick_next_task(struct rq *rq, struct task_struct *prev, struct rq_flags *rf)
         * non-matching user state.
         */
        for_each_cpu(i, smt_mask) {
-               struct rq *rq_i = cpu_rq(i);
+               rq_i = cpu_rq(i);
 
                /*
                 * An online sibling might have gone offline before a task
Reviewed-by on v1 1/1
#11 lore raw

Re: [PATCH] sched/core: Simplify core-wide task selection

In reply to Peter Zijlstra
Quoted 240 lines · Peter Zijlstra
Quoted 1 line · Peter Zijlstra

Let me go do that and also attempt a Changelog to go with it ;-)

How's this then?

---
Subject: sched/core: Simplify core-wide task selection
From: Peter Zijlstra <[email protected]>
Date: Tue Aug 24 11:05:47 CEST 2021

Tao suggested a two-pass task selection to avoid the retry loop.

Not only does it avoid the retry loop, it results in *much* simpler code.

This also fixes an issue spotted by Josh Don where, for SMT3+, we can forget to update max on the first pass and get to do an extra round.

---
 kernel/sched/core.c | 156 +++++++++++++++-------------------------------------
 1 file changed, 45 insertions(+), 111 deletions(-)
kernel/sched/core.c +44 -110
index ceae25ea8a0e..8a9a32df5f38 100644
@@ -5381,8 +5381,7 @@ __pick_next_task(struct rq *rq, struct task_struct *prev, struct rq_flags *rf)
                        return p;
        }
 
-       /* The idle class should always have a runnable task: */
-       BUG();
+       BUG(); /* The idle class should always have a runnable task. */
 }
 
 #ifdef CONFIG_SCHED_CORE
@@ -5404,54 +5403,18 @@ static inline bool cookie_match(struct task_struct *a, struct task_struct *b)
        return a->core_cookie == b->core_cookie;
 }
 
-// XXX fairness/fwd progress conditions
-/*
- * Returns
- * - NULL if there is no runnable task for this class.
- * - the highest priority task for this runqueue if it matches
- *   rq->core->core_cookie or its priority is greater than max.
- * - Else returns idle_task.
- */
-static struct task_struct *
-pick_task(struct rq *rq, const struct sched_class *class, struct task_struct *max, bool in_fi)
+static inline struct task_struct *pick_task(struct rq *rq)
 {
-       struct task_struct *class_pick, *cookie_pick;
-       unsigned long cookie = rq->core->core_cookie;
-
-       class_pick = class->pick_task(rq);
-       if (!class_pick)
-               return NULL;
-
-       if (!cookie) {
-               /*
-                * If class_pick is tagged, return it only if it has
-                * higher priority than max.
-                */
-               if (max && class_pick->core_cookie &&
-                   prio_less(class_pick, max, in_fi))
-                       return idle_sched_class.pick_task(rq);
+       const struct sched_class *class;
+       struct task_struct *p;
 
-               return class_pick;
+       for_each_class(class) {
+               p = class->pick_task(rq);
+               if (p)
+                       return p;
        }
 
-       /*
-        * If class_pick is idle or matches cookie, return early.
-        */
-       if (cookie_equals(class_pick, cookie))
-               return class_pick;
-
-       cookie_pick = sched_core_find(rq, cookie);
-
-       /*
-        * If class > max && class > cookie, it is the highest priority task on
-        * the core (so far) and it must be selected, otherwise we must go with
-        * the cookie pick in order to satisfy the constraint.
-        */
-       if (prio_less(cookie_pick, class_pick, in_fi) &&
-           (!max || prio_less(max, class_pick, in_fi)))
-               return class_pick;
-
-       return cookie_pick;
+       BUG(); /* The idle class should always have a runnable task. */
 }
 
 extern void task_vruntime_update(struct rq *rq, struct task_struct *p, bool in_fi);
@@ -5459,11 +5422,12 @@ extern void task_vruntime_update(struct rq *rq, struct task_struct *p, bool in_f
 static struct task_struct *
 pick_next_task(struct rq *rq, struct task_struct *prev, struct rq_flags *rf)
 {
-       struct task_struct *next, *max = NULL;
-       const struct sched_class *class;
+       struct task_struct *next, *p, *max = NULL;
        const struct cpumask *smt_mask;
        bool fi_before = false;
-       int i, j, cpu, occ = 0;
+       unsigned long cookie;
+       int i, cpu, occ = 0;
+       struct rq *rq_i;
        bool need_sync;
 
        if (!sched_core_enabled(rq))
@@ -5536,12 +5500,7 @@ pick_next_task(struct rq *rq, struct task_struct *prev, struct rq_flags *rf)
         * and there are no cookied tasks running on siblings.
         */
        if (!need_sync) {
-               for_each_class(class) {
-                       next = class->pick_task(rq);
-                       if (next)
-                               break;
-               }
-
+               next = pick_task(rq);
                if (!next->core_cookie) {
                        rq->core_pick = NULL;
                        /*
@@ -5554,76 +5513,51 @@ pick_next_task(struct rq *rq, struct task_struct *prev, struct rq_flags *rf)
                }
        }
 
-       for_each_cpu(i, smt_mask) {
-               struct rq *rq_i = cpu_rq(i);
-
-               rq_i->core_pick = NULL;
+       /*
+        * For each thread: do the regular task pick and find the max prio task
+        * amongst them.
+        *
+        * Tie-break prio towards the current CPU
+        */
+       for_each_cpu_wrap(i, smt_mask, cpu) {
+               rq_i = cpu_rq(i);
 
                if (i != cpu)
                        update_rq_clock(rq_i);
+
+               p = rq_i->core_pick = pick_task(rq_i);
+               if (!max || prio_less(max, p, fi_before))
+                       max = p;
        }
 
+       cookie = rq->core->core_cookie = max->core_cookie;
+
        /*
-        * Try and select tasks for each sibling in descending sched_class
-        * order.
+        * For each thread: try and find a runnable task that matches @max or
+        * force idle.
         */
-       for_each_class(class) {
-again:
-               for_each_cpu_wrap(i, smt_mask, cpu) {
-                       struct rq *rq_i = cpu_rq(i);
-                       struct task_struct *p;
-
-                       if (rq_i->core_pick)
-                               continue;
+       for_each_cpu(i, smt_mask) {
+               rq_i = cpu_rq(i);
+               p = rq_i->core_pick;
 
-                       /*
-                        * If this sibling doesn't yet have a suitable task to
-                        * run; ask for the most eligible task, given the
-                        * highest priority task already selected for this
-                        * core.
-                        */
-                       p = pick_task(rq_i, class, max, fi_before);
+               if (!cookie_equals(p, cookie)) {
+                       p = NULL;
+                       if (cookie)
+                               p = sched_core_find(rq_i, cookie);
                        if (!p)
-                               continue;
+                               p = idle_sched_class.pick_task(rq_i);
+               }
 
-                       if (!is_task_rq_idle(p))
-                               occ++;
+               rq_i->core_pick = p;
 
-                       rq_i->core_pick = p;
-                       if (rq_i->idle == p && rq_i->nr_running) {
+               if (p == rq_i->idle) {
+                       if (rq_i->nr_running) {
                                rq->core->core_forceidle = true;
                                if (!fi_before)
                                        rq->core->core_forceidle_seq++;
                        }
-
-                       /*
-                        * If this new candidate is of higher priority than the
-                        * previous; and they're incompatible; we need to wipe
-                        * the slate and start over. pick_task makes sure that
-                        * p's priority is more than max if it doesn't match
-                        * max's cookie.
-                        *
-                        * NOTE: this is a linear max-filter and is thus bounded
-                        * in execution time.
-                        */
-                       if (!max || !cookie_match(max, p)) {
-                               struct task_struct *old_max = max;
-
-                               rq->core->core_cookie = p->core_cookie;
-                               max = p;
-
-                               if (old_max) {
-                                       rq->core->core_forceidle = false;
-                                       for_each_cpu(j, smt_mask) {
-                                               if (j == i)
-                                                       continue;
-
-                                               cpu_rq(j)->core_pick = NULL;
-                                       }
-                                       occ = 1;
-                                       goto again;
-                               }
-                       }
+               } else {
+                       occ++;
                }
        }
 

kernel/sched/core.c pick_next_task(struct rq *rq, struct task_struct *prev, struct rq_flags *rf) · line 5583

Quoted 8 lines
kernel/sched/core.c +1 -1
@@ -5643,7 +5577,7 @@ pick_next_task(struct rq *rq, struct task_struct *prev, struct rq_flags *rf)
         * non-matching user state.
         */
        for_each_cpu(i, smt_mask) {
-               struct rq *rq_i = cpu_rq(i);
+               rq_i = cpu_rq(i);
 
                /*
                 * An online sibling might have gone offline before a task

--
Cheers,
~Vineeth

## "Its not the load that breaks you, but the way u carry it!" ##

merge bot Applied
#12 lore raw

[tip: sched/core] sched/core: Simplify core-wide task selection

In reply to Peter Zijlstra
The following commit has been merged into the sched/core branch of tip:

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

Commit-ID:     4b2b9ed7b987eb6243b609095fe5c8c65340e5ee
Gitweb:        https://git.kernel.org/tip/4b2b9ed7b987eb6243b609095fe5c8c65340e5ee
Author:        Peter Zijlstra <[email protected]>
AuthorDate:    Tue, 24 Aug 2021 11:05:47 +02:00
Committer:     Peter Zijlstra <[email protected]>
CommitterDate: Thu, 09 Sep 2021 11:27:30 +02:00

sched/core: Simplify core-wide task selection

Tao suggested a two-pass task selection to avoid the retry loop.

Not only does it avoid the retry loop, it results in *much* simpler code.

This also fixes an issue spotted by Josh Don where, for SMT3+, we can forget to update max on the first pass and get to do an extra round.

---
 kernel/sched/core.c | 156 ++++++++++++-------------------------------
 1 file changed, 45 insertions(+), 111 deletions(-)
kernel/sched/core.c +45 -111
index d19d1ba..953ff36 100644
@@ -5518,8 +5518,7 @@ restart:
 			return p;
 	}
 
-	/* The idle class should always have a runnable task: */
-	BUG();
+	BUG(); /* The idle class should always have a runnable task. */
 }
 
 #ifdef CONFIG_SCHED_CORE
@@ -5541,54 +5540,18 @@ static inline bool cookie_match(struct task_struct *a, struct task_struct *b)
 	return a->core_cookie == b->core_cookie;
 }
 
-// XXX fairness/fwd progress conditions
-/*
- * Returns
- * - NULL if there is no runnable task for this class.
- * - the highest priority task for this runqueue if it matches
- *   rq->core->core_cookie or its priority is greater than max.
- * - Else returns idle_task.
- */
-static struct task_struct *
-pick_task(struct rq *rq, const struct sched_class *class, struct task_struct *max, bool in_fi)
+static inline struct task_struct *pick_task(struct rq *rq)
 {
-	struct task_struct *class_pick, *cookie_pick;
-	unsigned long cookie = rq->core->core_cookie;
-
-	class_pick = class->pick_task(rq);
-	if (!class_pick)
-		return NULL;
-
-	if (!cookie) {
-		/*
-		 * If class_pick is tagged, return it only if it has
-		 * higher priority than max.
-		 */
-		if (max && class_pick->core_cookie &&
-		    prio_less(class_pick, max, in_fi))
-			return idle_sched_class.pick_task(rq);
+	const struct sched_class *class;
+	struct task_struct *p;
 
-		return class_pick;
+	for_each_class(class) {
+		p = class->pick_task(rq);
+		if (p)
+			return p;
 	}
 
-	/*
-	 * If class_pick is idle or matches cookie, return early.
-	 */
-	if (cookie_equals(class_pick, cookie))
-		return class_pick;
-
-	cookie_pick = sched_core_find(rq, cookie);
-
-	/*
-	 * If class > max && class > cookie, it is the highest priority task on
-	 * the core (so far) and it must be selected, otherwise we must go with
-	 * the cookie pick in order to satisfy the constraint.
-	 */
-	if (prio_less(cookie_pick, class_pick, in_fi) &&
-	    (!max || prio_less(max, class_pick, in_fi)))
-		return class_pick;
-
-	return cookie_pick;
+	BUG(); /* The idle class should always have a runnable task. */
 }
 
 extern void task_vruntime_update(struct rq *rq, struct task_struct *p, bool in_fi);
@@ -5596,11 +5559,12 @@ extern void task_vruntime_update(struct rq *rq, struct task_struct *p, bool in_f
 static struct task_struct *
 pick_next_task(struct rq *rq, struct task_struct *prev, struct rq_flags *rf)
 {
-	struct task_struct *next, *max = NULL;
-	const struct sched_class *class;
+	struct task_struct *next, *p, *max = NULL;
 	const struct cpumask *smt_mask;
 	bool fi_before = false;
-	int i, j, cpu, occ = 0;
+	unsigned long cookie;
+	int i, cpu, occ = 0;
+	struct rq *rq_i;
 	bool need_sync;
 
 	if (!sched_core_enabled(rq))
@@ -5673,12 +5637,7 @@ pick_next_task(struct rq *rq, struct task_struct *prev, struct rq_flags *rf)
 	 * and there are no cookied tasks running on siblings.
 	 */
 	if (!need_sync) {
-		for_each_class(class) {
-			next = class->pick_task(rq);
-			if (next)
-				break;
-		}
-
+		next = pick_task(rq);
 		if (!next->core_cookie) {
 			rq->core_pick = NULL;
 			/*
@@ -5691,76 +5650,51 @@ pick_next_task(struct rq *rq, struct task_struct *prev, struct rq_flags *rf)
 		}
 	}
 
-	for_each_cpu(i, smt_mask) {
-		struct rq *rq_i = cpu_rq(i);
-
-		rq_i->core_pick = NULL;
+	/*
+	 * For each thread: do the regular task pick and find the max prio task
+	 * amongst them.
+	 *
+	 * Tie-break prio towards the current CPU
+	 */
+	for_each_cpu_wrap(i, smt_mask, cpu) {
+		rq_i = cpu_rq(i);
 
 		if (i != cpu)
 			update_rq_clock(rq_i);
+
+		p = rq_i->core_pick = pick_task(rq_i);
+		if (!max || prio_less(max, p, fi_before))
+			max = p;
 	}
 
+	cookie = rq->core->core_cookie = max->core_cookie;
+
 	/*
-	 * Try and select tasks for each sibling in descending sched_class
-	 * order.
+	 * For each thread: try and find a runnable task that matches @max or
+	 * force idle.
 	 */
-	for_each_class(class) {
-again:
-		for_each_cpu_wrap(i, smt_mask, cpu) {
-			struct rq *rq_i = cpu_rq(i);
-			struct task_struct *p;
-
-			if (rq_i->core_pick)
-				continue;
+	for_each_cpu(i, smt_mask) {
+		rq_i = cpu_rq(i);
+		p = rq_i->core_pick;
 
-			/*
-			 * If this sibling doesn't yet have a suitable task to
-			 * run; ask for the most eligible task, given the
-			 * highest priority task already selected for this
-			 * core.
-			 */
-			p = pick_task(rq_i, class, max, fi_before);
+		if (!cookie_equals(p, cookie)) {
+			p = NULL;
+			if (cookie)
+				p = sched_core_find(rq_i, cookie);
 			if (!p)
-				continue;
+				p = idle_sched_class.pick_task(rq_i);
+		}
 
-			if (!is_task_rq_idle(p))
-				occ++;
+		rq_i->core_pick = p;
 
-			rq_i->core_pick = p;
-			if (rq_i->idle == p && rq_i->nr_running) {
+		if (p == rq_i->idle) {
+			if (rq_i->nr_running) {
 				rq->core->core_forceidle = true;
 				if (!fi_before)
 					rq->core->core_forceidle_seq++;
 			}
-
-			/*
-			 * If this new candidate is of higher priority than the
-			 * previous; and they're incompatible; we need to wipe
-			 * the slate and start over. pick_task makes sure that
-			 * p's priority is more than max if it doesn't match
-			 * max's cookie.
-			 *
-			 * NOTE: this is a linear max-filter and is thus bounded
-			 * in execution time.
-			 */
-			if (!max || !cookie_match(max, p)) {
-				struct task_struct *old_max = max;
-
-				rq->core->core_cookie = p->core_cookie;
-				max = p;
-
-				if (old_max) {
-					rq->core->core_forceidle = false;
-					for_each_cpu(j, smt_mask) {
-						if (j == i)
-							continue;
-
-						cpu_rq(j)->core_pick = NULL;
-					}
-					occ = 1;
-					goto again;
-				}
-			}
+		} else {
+			occ++;
 		}
 	}
 
@@ -5780,7 +5714,7 @@ again:
 	 * non-matching user state.
 	 */
 	for_each_cpu(i, smt_mask) {
-		struct rq *rq_i = cpu_rq(i);
+		rq_i = cpu_rq(i);
 
 		/*
 		 * An online sibling might have gone offline before a task
merge bot Applied
#13 lore raw

[tip: sched/core] sched/core: Simplify core-wide task selection

In reply to Peter Zijlstra
The following commit has been merged into the sched/core branch of tip:

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

Commit-ID:     bc9ffef31bf59819c9fc032178534ff9ed7c4981
Gitweb:        https://git.kernel.org/tip/bc9ffef31bf59819c9fc032178534ff9ed7c4981
Author:        Peter Zijlstra <[email protected]>
AuthorDate:    Tue, 24 Aug 2021 11:05:47 +02:00
Committer:     Peter Zijlstra <[email protected]>
CommitterDate: Tue, 05 Oct 2021 15:51:33 +02:00

sched/core: Simplify core-wide task selection

Tao suggested a two-pass task selection to avoid the retry loop.

Not only does it avoid the retry loop, it results in *much* simpler code.

This also fixes an issue spotted by Josh Don where, for SMT3+, we can forget to update max on the first pass and get to do an extra round.

---
 kernel/sched/core.c | 156 ++++++++++++-------------------------------
 1 file changed, 45 insertions(+), 111 deletions(-)
kernel/sched/core.c +45 -111
index 2672694..f963c81 100644
@@ -5580,8 +5580,7 @@ restart:
 			return p;
 	}
 
-	/* The idle class should always have a runnable task: */
-	BUG();
+	BUG(); /* The idle class should always have a runnable task. */
 }
 
 #ifdef CONFIG_SCHED_CORE
@@ -5603,54 +5602,18 @@ static inline bool cookie_match(struct task_struct *a, struct task_struct *b)
 	return a->core_cookie == b->core_cookie;
 }
 
-// XXX fairness/fwd progress conditions
-/*
- * Returns
- * - NULL if there is no runnable task for this class.
- * - the highest priority task for this runqueue if it matches
- *   rq->core->core_cookie or its priority is greater than max.
- * - Else returns idle_task.
- */
-static struct task_struct *
-pick_task(struct rq *rq, const struct sched_class *class, struct task_struct *max, bool in_fi)
+static inline struct task_struct *pick_task(struct rq *rq)
 {
-	struct task_struct *class_pick, *cookie_pick;
-	unsigned long cookie = rq->core->core_cookie;
-
-	class_pick = class->pick_task(rq);
-	if (!class_pick)
-		return NULL;
-
-	if (!cookie) {
-		/*
-		 * If class_pick is tagged, return it only if it has
-		 * higher priority than max.
-		 */
-		if (max && class_pick->core_cookie &&
-		    prio_less(class_pick, max, in_fi))
-			return idle_sched_class.pick_task(rq);
+	const struct sched_class *class;
+	struct task_struct *p;
 
-		return class_pick;
+	for_each_class(class) {
+		p = class->pick_task(rq);
+		if (p)
+			return p;
 	}
 
-	/*
-	 * If class_pick is idle or matches cookie, return early.
-	 */
-	if (cookie_equals(class_pick, cookie))
-		return class_pick;
-
-	cookie_pick = sched_core_find(rq, cookie);
-
-	/*
-	 * If class > max && class > cookie, it is the highest priority task on
-	 * the core (so far) and it must be selected, otherwise we must go with
-	 * the cookie pick in order to satisfy the constraint.
-	 */
-	if (prio_less(cookie_pick, class_pick, in_fi) &&
-	    (!max || prio_less(max, class_pick, in_fi)))
-		return class_pick;
-
-	return cookie_pick;
+	BUG(); /* The idle class should always have a runnable task. */
 }
 
 extern void task_vruntime_update(struct rq *rq, struct task_struct *p, bool in_fi);
@@ -5658,11 +5621,12 @@ extern void task_vruntime_update(struct rq *rq, struct task_struct *p, bool in_f
 static struct task_struct *
 pick_next_task(struct rq *rq, struct task_struct *prev, struct rq_flags *rf)
 {
-	struct task_struct *next, *max = NULL;
-	const struct sched_class *class;
+	struct task_struct *next, *p, *max = NULL;
 	const struct cpumask *smt_mask;
 	bool fi_before = false;
-	int i, j, cpu, occ = 0;
+	unsigned long cookie;
+	int i, cpu, occ = 0;
+	struct rq *rq_i;
 	bool need_sync;
 
 	if (!sched_core_enabled(rq))
@@ -5735,12 +5699,7 @@ pick_next_task(struct rq *rq, struct task_struct *prev, struct rq_flags *rf)
 	 * and there are no cookied tasks running on siblings.
 	 */
 	if (!need_sync) {
-		for_each_class(class) {
-			next = class->pick_task(rq);
-			if (next)
-				break;
-		}
-
+		next = pick_task(rq);
 		if (!next->core_cookie) {
 			rq->core_pick = NULL;
 			/*
@@ -5753,76 +5712,51 @@ pick_next_task(struct rq *rq, struct task_struct *prev, struct rq_flags *rf)
 		}
 	}
 
-	for_each_cpu(i, smt_mask) {
-		struct rq *rq_i = cpu_rq(i);
-
-		rq_i->core_pick = NULL;
+	/*
+	 * For each thread: do the regular task pick and find the max prio task
+	 * amongst them.
+	 *
+	 * Tie-break prio towards the current CPU
+	 */
+	for_each_cpu_wrap(i, smt_mask, cpu) {
+		rq_i = cpu_rq(i);
 
 		if (i != cpu)
 			update_rq_clock(rq_i);
+
+		p = rq_i->core_pick = pick_task(rq_i);
+		if (!max || prio_less(max, p, fi_before))
+			max = p;
 	}
 
+	cookie = rq->core->core_cookie = max->core_cookie;
+
 	/*
-	 * Try and select tasks for each sibling in descending sched_class
-	 * order.
+	 * For each thread: try and find a runnable task that matches @max or
+	 * force idle.
 	 */
-	for_each_class(class) {
-again:
-		for_each_cpu_wrap(i, smt_mask, cpu) {
-			struct rq *rq_i = cpu_rq(i);
-			struct task_struct *p;
-
-			if (rq_i->core_pick)
-				continue;
+	for_each_cpu(i, smt_mask) {
+		rq_i = cpu_rq(i);
+		p = rq_i->core_pick;
 
-			/*
-			 * If this sibling doesn't yet have a suitable task to
-			 * run; ask for the most eligible task, given the
-			 * highest priority task already selected for this
-			 * core.
-			 */
-			p = pick_task(rq_i, class, max, fi_before);
+		if (!cookie_equals(p, cookie)) {
+			p = NULL;
+			if (cookie)
+				p = sched_core_find(rq_i, cookie);
 			if (!p)
-				continue;
+				p = idle_sched_class.pick_task(rq_i);
+		}
 
-			if (!is_task_rq_idle(p))
-				occ++;
+		rq_i->core_pick = p;
 
-			rq_i->core_pick = p;
-			if (rq_i->idle == p && rq_i->nr_running) {
+		if (p == rq_i->idle) {
+			if (rq_i->nr_running) {
 				rq->core->core_forceidle = true;
 				if (!fi_before)
 					rq->core->core_forceidle_seq++;
 			}
-
-			/*
-			 * If this new candidate is of higher priority than the
-			 * previous; and they're incompatible; we need to wipe
-			 * the slate and start over. pick_task makes sure that
-			 * p's priority is more than max if it doesn't match
-			 * max's cookie.
-			 *
-			 * NOTE: this is a linear max-filter and is thus bounded
-			 * in execution time.
-			 */
-			if (!max || !cookie_match(max, p)) {
-				struct task_struct *old_max = max;
-
-				rq->core->core_cookie = p->core_cookie;
-				max = p;
-
-				if (old_max) {
-					rq->core->core_forceidle = false;
-					for_each_cpu(j, smt_mask) {
-						if (j == i)
-							continue;
-
-						cpu_rq(j)->core_pick = NULL;
-					}
-					occ = 1;
-					goto again;
-				}
-			}
+		} else {
+			occ++;
 		}
 	}
 
@@ -5842,7 +5776,7 @@ again:
 	 * non-matching user state.
 	 */
 	for_each_cpu(i, smt_mask) {
-		struct rq *rq_i = cpu_rq(i);
+		rq_i = cpu_rq(i);
 
 		/*
 		 * An online sibling might have gone offline before a task
author
#14 lore raw
In reply to Peter Zijlstra

Hi Peter,

On Mon, Aug 23, 2021 at 4:17 AM Peter Zijlstra <[email protected]> wrote:
[snip]

Quoted 5 lines
kernel/sched/core.c +3 -1
+       for_each_cpu(i, smt_mask) {
+               rq_i = cpu_rq(i);
+               p = rq_i->core_temp;
 
-                       /*

kernel/sched/core.c pick_next_task(struct rq *rq, struct task_struct *prev, struct rq_flags *rf) · line 5545

Quoted 10 lines
kernel/sched/core.c +4 -6
-                        * If this sibling doesn't yet have a suitable task to
-                        * run; ask for the most eligible task, given the
-                        * highest priority task already selected for this
-                        * core.
-                        */
-                       p = pick_task(rq_i, class, max, fi_before);
+               if (!cookie_equals(p, cookie)) {
+                       p = NULL;
+                       if (cookie)
+                               p = sched_core_find(rq_i, cookie);

In the case that 'max' has a zero cookie, shouldn't we search for a match on this cpu if the original class pick ('p') had a non-zero cookie? We don't enqueue tasks with zero cookie in the core_tree, so I forget if there was some other reasoning here.

Quoted 4 lines
                        if (!p)
kernel/sched/core.c +2 -1
-                               continue;
+                               p = idle_sched_class.pick_task(rq_i);
+               }
#15 lore raw

Hi Josh,

Quoted 20 lines · Josh Don

Hi Peter,

On Mon, Aug 23, 2021 at 4:17 AM Peter Zijlstra <[email protected]> wrote:
[snip]

Quoted 5 lines
kernel/sched/core.c +3 -1
+       for_each_cpu(i, smt_mask) {
+               rq_i = cpu_rq(i);
+               p = rq_i->core_temp;
 
-                       /*

kernel/sched/core.c pick_next_task(struct rq *rq, struct task_struct *prev, struct rq_flags *rf) · line 5545

Quoted 10 lines
kernel/sched/core.c +4 -6
-                        * If this sibling doesn't yet have a suitable task to
-                        * run; ask for the most eligible task, given the
-                        * highest priority task already selected for this
-                        * core.
-                        */
-                       p = pick_task(rq_i, class, max, fi_before);
+               if (!cookie_equals(p, cookie)) {
+                       p = NULL;
+                       if (cookie)
+                               p = sched_core_find(rq_i, cookie);
Quoted 1 line

In the case that 'max' has a zero cookie, shouldn't we search for a

In the original pick_task(), when cookie is zero, we choose class pick task or force idle task.

Quoted 3 lines

match on this cpu if the original class pick ('p') had a non-zero cookie? We don't enqueue tasks with zero cookie in the core_tree, so I forget if there was some other reasoning here.

So, no need to search the core_tree when cookie is zero.

But I'm not sure that force idle pick condition(in pick_task()) is also covered by this clause in the first filter max loop in the rewrite..

'
if (!max || prio_less(max, p, fi_before))

		max = p;

'

I just thought there are three(one add by Josh) places that can return max;

1, !cookie condition and class_pick > max
2, cookie equal condition and class_pick > max(add by Josh) 3, cookie not equal condition and class_pick > max.

The rewrite change a little with the class pick, it loops all class to find the max first(finally will get one task and not be possible return NULL). This is not the same with the original.

It is very possible that I'm getting wrong, then please shout to me.

Quoted 4 lines

kernel/sched/core.c pick_next_task(struct rq *rq, struct task_struct *prev, struct rq_flags *rf) · line 5548

Quoted 4 lines
                        if (!p)
kernel/sched/core.c +2 -1
-                               continue;
+                               p = idle_sched_class.pick_task(rq_i);
+               }

Thanks,
Tao

maintainer
#16 lore raw
In reply to Josh Don
Quoted 20 lines · Josh Don

Hi Peter,

On Mon, Aug 23, 2021 at 4:17 AM Peter Zijlstra <[email protected]> wrote:
[snip]

Quoted 5 lines
kernel/sched/core.c +3 -1
+       for_each_cpu(i, smt_mask) {
+               rq_i = cpu_rq(i);
+               p = rq_i->core_temp;
 
-                       /*

kernel/sched/core.c pick_next_task(struct rq *rq, struct task_struct *prev, struct rq_flags *rf) · line 5545

Quoted 10 lines
kernel/sched/core.c +4 -6
-                        * If this sibling doesn't yet have a suitable task to
-                        * run; ask for the most eligible task, given the
-                        * highest priority task already selected for this
-                        * core.
-                        */
-                       p = pick_task(rq_i, class, max, fi_before);
+               if (!cookie_equals(p, cookie)) {
+                       p = NULL;
+                       if (cookie)
+                               p = sched_core_find(rq_i, cookie);
Quoted 4 lines

In the case that 'max' has a zero cookie, shouldn't we search for a match on this cpu if the original class pick ('p') had a non-zero cookie? We don't enqueue tasks with zero cookie in the core_tree, so I forget if there was some other reasoning here.

IIRC we don't keep 0-cookies in the tree. Lemme check.

Yeah, see sched_core_enqueue(), they bail for 0-cookie.

This is indeed sub-optimal, but also having the 0-cookie tasks in the tree has other issues IIRC.