mirror of https://lore.kernel.org/lkml/
 help / color / mirror / Atom feed
* [PATCH 0/3] sched/eevdf: Introduce functional invariants for EEVDF
@ 2025-04-23  0:20 Dhaval Giani (AMD)
  2025-04-23  0:20 ` [PATCH 1/3] sched/fair: Introduce a new debugfs directory for EEVDF tests Dhaval Giani (AMD)
                   ` (2 more replies)
  0 siblings, 3 replies; 8+ messages in thread
From: Dhaval Giani (AMD) @ 2025-04-23  0:20 UTC (permalink / raw)
  To: Ingo Molnar, Peter Zijlstra, Juri Lelli, Vincent Guittot,
	Dietmar Eggemann, Steven Rostedt, Ben Segall, Mel Gorman,
	Valentin Schneider
  Cc: linux-kernel, Dhaval Giani, Gautham Shenoy, K Prateek Nayak,
	Dhaval Giani (AMD)

Introducing test cases for testing invariants for EEVDF. These are based
of the original tech report available at
https://citeseerx.ist.psu.edu/document?repid=rep1&type=pdf&doi=805acf7726282721504c8f00575d91ebfd750564

There are two invariants being tested here

1. This is based of Lemma 1 in the paper, which states that if a task
has positive lag, it is eligible. We do not test exactly this. Instead
we test if a task is eligible (which it is, if it is being to run), that
it has a positive lag.

2. This test is based of Lemma 2, which states that the sum of the lags
of all the tasks in the system is zero.

The patch series introduce a debugfs directory with triggers to run
each test.

This is not meant to enabled in production. This is a development tool
for scheduler developers

Changes since v1
- Add a tunable to change number of tasks to check for Lemma 1
- Remove the recursion in Lemma 2
- Use functions to detect overflows in Lemma 2

Signed-off-by: Dhaval Giani (AMD) <dhaval@gianis.ca>
---
Dhaval Giani (AMD) (3):
      sched/fair: Introduce a new debugfs directory for EEVDF tests
      sched/fair: Add a test to test that a task selected to run has positive lag
      sched/fair: Test that the average lag across the system is zero

 include/linux/sched.h      |   7 ++
 kernel/Kconfig.preempt     |   9 ++
 kernel/sched/Makefile      |   1 +
 kernel/sched/debug.c       |   2 +
 kernel/sched/eevdf-tests.c | 242 +++++++++++++++++++++++++++++++++++++++++++++
 kernel/sched/fair.c        |   5 +
 kernel/sched/sched.h       |   9 ++
 7 files changed, 275 insertions(+)
---
base-commit: c70fc32f44431bb30f9025ce753ba8be25acbba3
change-id: 20250402-b4-eevdf-tests-v1-post-a7550c4a94cf

Best regards,
-- 
Dhaval Giani (AMD) <dhaval@gianis.ca>



^ permalink raw reply	[flat|nested] 8+ messages in thread
* [PATCH 2/3] sched/fair: Add a test to test that a task selected to run has positive lag
@ 2025-04-23  0:15 Dhaval Giani (AMD)
  0 siblings, 0 replies; 8+ messages in thread
From: Dhaval Giani (AMD) @ 2025-04-23  0:15 UTC (permalink / raw)
  Cc: linux-kernel, Dhaval Giani, Gautham Shenoy, K Prateek Nayak,
	Dhaval Giani (AMD)

Lemma 1 from the original EEVDF paper says that any task that
has a positive lag is eligible to run.

This test tests the opposite - any task that is picked to run must
have a positive lag for it to be eligible to run.

Signed-off-by: Dhaval Giani (AMD) <dhaval@gianis.ca>
---
 kernel/sched/eevdf-tests.c | 41 +++++++++++++++++++++++++++++++++++++++++
 kernel/sched/fair.c        |  2 ++
 kernel/sched/sched.h       |  2 ++
 3 files changed, 45 insertions(+)

diff --git a/kernel/sched/eevdf-tests.c b/kernel/sched/eevdf-tests.c
index 3bc016d3025733e53f586e30fcd31f650156d47e..8532330769bcc93dbf9cd98ebba75c838f62c045 100644
--- a/kernel/sched/eevdf-tests.c
+++ b/kernel/sched/eevdf-tests.c
@@ -18,10 +18,51 @@
 
 #ifdef CONFIG_SCHED_EEVDF_TESTING
 
+/*
+ * Test parameters
+ */
+bool eevdf_positive_lag_test;
+u8 eevdf_positive_lag_count = 10;
+
 static struct dentry *debugfs_eevdf_testing;
 void debugfs_eevdf_testing_init(struct dentry *debugfs_sched)
 {
 	debugfs_eevdf_testing = debugfs_create_dir("eevdf-testing", debugfs_sched);
 
+	debugfs_create_bool("eevdf_positive_lag_test", 0700,
+				debugfs_eevdf_testing, &eevdf_positive_lag_test);
+	debugfs_create_u8("eevdf_positive_lag_test_count", 0600,
+				debugfs_eevdf_testing, &eevdf_positive_lag_count);
+
 }
+
+void test_eevdf_positive_lag(struct cfs_rq *cfs, struct sched_entity *se)
+{
+	static int eevdf_positive_lag_test_counter;
+	u64 eevdf_average_vruntime;
+
+	if (!eevdf_positive_lag_test)
+		return;
+
+	if (!se || !cfs)
+		return;
+
+	eevdf_average_vruntime = avg_vruntime(cfs);
+	eevdf_positive_lag_test_counter++;
+
+	if (se->vruntime > eevdf_average_vruntime) {
+		trace_printk("FAIL: Lemma 1 failed - selected task has negative lag\n");
+		eevdf_positive_lag_test = 0;
+		eevdf_positive_lag_test_counter = 0;
+		return;
+	}
+
+	if (eevdf_positive_lag_test_counter > eevdf_positive_lag_count) {
+		eevdf_positive_lag_test = 0;
+		eevdf_positive_lag_test_counter = 0;
+		trace_printk("PASS: At least %u selected tasks had positive lag\n",
+							eevdf_positive_lag_count);
+	}
+}
+
 #endif /* CONFIG_SCHED_EEVDF_TESTING */
diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
index eb5a2572b4f8b6b5517befc299312b6ae7476e88..924d9d35c2aa937bc0f4ca9565ba774397b90f77 100644
--- a/kernel/sched/fair.c
+++ b/kernel/sched/fair.c
@@ -980,6 +980,8 @@ static struct sched_entity *pick_eevdf(struct cfs_rq *cfs_rq)
 	if (!best || (curr && entity_before(curr, best)))
 		best = curr;
 
+	test_eevdf_positive_lag(cfs_rq, best);
+
 	return best;
 }
 
diff --git a/kernel/sched/sched.h b/kernel/sched/sched.h
index 09cefe2aa871bbd533a413c76026895e969a58e7..5ad5e033e1c81167b712ab176d4d55e6b5d82d06 100644
--- a/kernel/sched/sched.h
+++ b/kernel/sched/sched.h
@@ -3990,8 +3990,10 @@ void sched_enq_and_set_task(struct sched_enq_and_set_ctx *ctx);
 
 #ifdef CONFIG_SCHED_EEVDF_TESTING
 void debugfs_eevdf_testing_init(struct dentry *debugfs_sched);
+void test_eevdf_positive_lag(struct cfs_rq *cfs, struct sched_entity *se);
 #else /* CONFIG_SCHED_EEVDF_TESTING */
 static inline void init_eevdf_testing_debugfs(struct dentry *debugfs_sched) {}
+static inline void test_eevdf_positive_lag(struct cfs_rq *cfs, struct sched_entity *se) {}
 #endif /* CONFIG_SCHED_EEVDF_TESTING */
 
 #endif /* _KERNEL_SCHED_SCHED_H */

-- 
2.49.0



^ permalink raw reply	[flat|nested] 8+ messages in thread
* [PATCH 0/3] sched/eevdf: Introduce functional invariants for EEVDF
@ 2025-04-23  0:10 Dhaval Giani (AMD)
  2025-04-23  0:11 ` [PATCH 2/3] sched/fair: Add a test to test that a task selected to run has positive lag Dhaval Giani (AMD)
  0 siblings, 1 reply; 8+ messages in thread
From: Dhaval Giani (AMD) @ 2025-04-23  0:10 UTC (permalink / raw)
  Cc: linux-kernel, Dhaval Giani, Gautham Shenoy, K Prateek Nayak,
	Dhaval Giani (AMD)

Introducing test cases for testing invariants for EEVDF. These are based
of the original tech report available at
https://citeseerx.ist.psu.edu/document?repid=rep1&type=pdf&doi=805acf7726282721504c8f00575d91ebfd750564

There are two invariants being tested here

1. This is based of Lemma 1 in the paper, which states that if a task
has positive lag, it is eligible. We do not test exactly this. Instead
we test if a task is eligible (which it is, if it is being to run), that
it has a positive lag.

2. This test is based of Lemma 2, which states that the sum of the lags
of all the tasks in the system is zero.

The patch series introduce a debugfs directory with triggers to run
each test.

This is not meant to enabled in production. This is a development tool
for scheduler developers

Changes since v1
- Add a tunable to change number of tasks to check for Lemma 1
- Remove the recursion in Lemma 2
- Use functions to detect overflows in Lemma 2

Signed-off-by: Dhaval Giani (AMD) <dhaval@gianis.ca>
---
Dhaval Giani (AMD) (3):
      sched/fair: Introduce a new debugfs directory for EEVDF tests
      sched/fair: Add a test to test that a task selected to run has positive lag
      sched/fair: Test that the average lag across the system is zero

 include/linux/sched.h      |   7 ++
 kernel/Kconfig.preempt     |   9 ++
 kernel/sched/Makefile      |   1 +
 kernel/sched/debug.c       |   2 +
 kernel/sched/eevdf-tests.c | 242 +++++++++++++++++++++++++++++++++++++++++++++
 kernel/sched/fair.c        |   5 +
 kernel/sched/sched.h       |   9 ++
 7 files changed, 275 insertions(+)
---
base-commit: c70fc32f44431bb30f9025ce753ba8be25acbba3
change-id: 20250402-b4-eevdf-tests-v1-post-a7550c4a94cf

Best regards,
-- 
Dhaval Giani (AMD) <dhaval@gianis.ca>



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

end of thread, other threads:[~2025-05-07 10:26 UTC | newest]

Thread overview: 8+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2025-04-23  0:20 [PATCH 0/3] sched/eevdf: Introduce functional invariants for EEVDF Dhaval Giani (AMD)
2025-04-23  0:20 ` [PATCH 1/3] sched/fair: Introduce a new debugfs directory for EEVDF tests Dhaval Giani (AMD)
2025-05-07 10:03   ` kernel test robot
2025-04-23  0:20 ` [PATCH 2/3] sched/fair: Add a test to test that a task selected to run has positive lag Dhaval Giani (AMD)
2025-05-07 10:25   ` kernel test robot
2025-04-23  0:20 ` [PATCH 3/3] sched/fair: Test that the average lag across the system is zero Dhaval Giani (AMD)
  -- strict thread matches above, loose matches on Subject: below --
2025-04-23  0:15 [PATCH 2/3] sched/fair: Add a test to test that a task selected to run has positive lag Dhaval Giani (AMD)
2025-04-23  0:10 [PATCH 0/3] sched/eevdf: Introduce functional invariants for EEVDF Dhaval Giani (AMD)
2025-04-23  0:11 ` [PATCH 2/3] sched/fair: Add a test to test that a task selected to run has positive lag Dhaval Giani (AMD)

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox

all inboxes | Powered by JetHome®