linux-kernel.vger.kernel.org archive mirror
 help / color / mirror / Atom feed
* [PATCH v3] sched/fair: sanitize vruntime of entity being placed
@ 2023-02-09 19:31 Roman Kagan
  2023-02-21  9:38 ` Vincent Guittot
  0 siblings, 1 reply; 14+ messages in thread
From: Roman Kagan @ 2023-02-09 19:31 UTC (permalink / raw)
  To: linux-kernel
  Cc: Valentin Schneider, Zhang Qiao, Ben Segall, Vincent Guittot,
	Waiman Long, Peter Zijlstra, Steven Rostedt, Mel Gorman,
	Dietmar Eggemann, Daniel Bristot de Oliveira, Ingo Molnar,
	Juri Lelli

From: Zhang Qiao <zhangqiao22@huawei.com>

When a scheduling entity is placed onto cfs_rq, its vruntime is pulled
to the base level (around cfs_rq->min_vruntime), so that the entity
doesn't gain extra boost when placed backwards.

However, if the entity being placed wasn't executed for a long time, its
vruntime may get too far behind (e.g. while cfs_rq was executing a
low-weight hog), which can inverse the vruntime comparison due to s64
overflow.  This results in the entity being placed with its original
vruntime way forwards, so that it will effectively never get to the cpu.

To prevent that, ignore the vruntime of the entity being placed if it
didn't execute for longer than the time that can lead to an overflow.

Signed-off-by: Zhang Qiao <zhangqiao22@huawei.com>
[rkagan: formatted, adjusted commit log, comments, cutoff value]
Co-developed-by: Roman Kagan <rkagan@amazon.de>
Signed-off-by: Roman Kagan <rkagan@amazon.de>
---
v2 -> v3:
- make cutoff less arbitrary and update comments [Vincent]

v1 -> v2:
- add Zhang Qiao's s-o-b
- fix constant promotion on 32bit

 kernel/sched/fair.c | 21 +++++++++++++++++++--
 1 file changed, 19 insertions(+), 2 deletions(-)

diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
index 0f8736991427..3baa6b7ea860 100644
--- a/kernel/sched/fair.c
+++ b/kernel/sched/fair.c
@@ -4656,6 +4656,7 @@ static void
 place_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int initial)
 {
 	u64 vruntime = cfs_rq->min_vruntime;
+	u64 sleep_time;
 
 	/*
 	 * The 'current' period is already promised to the current tasks,
@@ -4685,8 +4686,24 @@ place_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int initial)
 		vruntime -= thresh;
 	}
 
-	/* ensure we never gain time by being placed backwards. */
-	se->vruntime = max_vruntime(se->vruntime, vruntime);
+	/*
+	 * Pull vruntime of the entity being placed to the base level of
+	 * cfs_rq, to prevent boosting it if placed backwards.
+	 * However, min_vruntime can advance much faster than real time, with
+	 * the exterme being when an entity with the minimal weight always runs
+	 * on the cfs_rq.  If the new entity slept for long, its vruntime
+	 * difference from min_vruntime may overflow s64 and their comparison
+	 * may get inversed, so ignore the entity's original vruntime in that
+	 * case.
+	 * The maximal vruntime speedup is given by the ratio of normal to
+	 * minimal weight: NICE_0_LOAD / MIN_SHARES, so cutting off on the
+	 * sleep time of 2^63 / NICE_0_LOAD should be safe.
+	 */
+	sleep_time = rq_clock_task(rq_of(cfs_rq)) - se->exec_start;
+	if ((s64)sleep_time > (1ULL << 63) / NICE_0_LOAD)
+		se->vruntime = vruntime;
+	else
+		se->vruntime = max_vruntime(se->vruntime, vruntime);
 }
 
 static void check_enqueue_throttle(struct cfs_rq *cfs_rq);
-- 
2.34.1




Amazon Development Center Germany GmbH
Krausenstr. 38
10117 Berlin
Geschaeftsfuehrung: Christian Schlaeger, Jonathan Weiss
Eingetragen am Amtsgericht Charlottenburg unter HRB 149173 B
Sitz: Berlin
Ust-ID: DE 289 237 879




^ permalink raw reply related	[flat|nested] 14+ messages in thread

end of thread, other threads:[~2023-03-03  8:33 UTC | newest]

Thread overview: 14+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2023-02-09 19:31 [PATCH v3] sched/fair: sanitize vruntime of entity being placed Roman Kagan
2023-02-21  9:38 ` Vincent Guittot
2023-02-21 16:57   ` Roman Kagan
2023-02-21 17:26     ` Vincent Guittot
2023-02-27  8:42       ` Roman Kagan
2023-02-27 14:37         ` Vincent Guittot
2023-02-27 17:00           ` Dietmar Eggemann
2023-02-27 17:15             ` Vincent Guittot
2023-03-02  9:36           ` Zhang Qiao
2023-03-02 13:34             ` Vincent Guittot
2023-03-02 14:29               ` Zhang Qiao
2023-03-02 14:55                 ` Vincent Guittot
2023-03-03  6:51                   ` Zhang Qiao
2023-03-03  8:32                     ` Vincent Guittot

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).