[PATCH 1/3] sched/fair: Introduce a new debugfs directory for EEVDF tests

[PATCH 1/3] sched/fair: Introduce a new debugfs directory for EEVDF tests

[Dhaval Giani (AMD)]

Signed-off-by: Dhaval Giani (AMD) <dhaval@gianis.ca>
---
 kernel/Kconfig.preempt     |  9 +++++++++
 kernel/sched/Makefile      |  1 +
 kernel/sched/debug.c       |  2 ++
 kernel/sched/eevdf-tests.c | 27 +++++++++++++++++++++++++++
 kernel/sched/sched.h       |  7 +++++++
 5 files changed, 46 insertions(+)

diff --git a/kernel/Kconfig.preempt b/kernel/Kconfig.preempt
index 54ea59ff8fbeb653b7084a78bd0d933076deaad5..96f47cf498aa10d7cbb375093e5533753ed7a414 100644
--- a/kernel/Kconfig.preempt
+++ b/kernel/Kconfig.preempt
@@ -176,3 +176,12 @@ config SCHED_CLASS_EXT
 	  For more information:
 	    Documentation/scheduler/sched-ext.rst
 	    https://github.com/sched-ext/scx
+
+config SCHED_EEVDF_TESTING
+	bool "EEVDF testing"
+	help
+	  This option is a debug option to test that your changes to the
+	  fair scheduling code do not break EEVDF invariants. There are
+	  controls exposted in debugfs to allow tests to be run. This has a
+	  performance impact, so do not enable unless you are a scheduler
+	  developer and know what you are doing.
diff --git a/kernel/sched/Makefile b/kernel/sched/Makefile
index 8ae86371ddcddf836172ee93ca34f2e91b4057a7..1a8416b8009ebf7cf38ac7b326f4b6472e62909a 100644
--- a/kernel/sched/Makefile
+++ b/kernel/sched/Makefile
@@ -37,3 +37,4 @@ obj-y += core.o
 obj-y += fair.o
 obj-y += build_policy.o
 obj-y += build_utility.o
+obj-y += eevdf-tests.o
diff --git a/kernel/sched/debug.c b/kernel/sched/debug.c
index 557246880a7e0839277df662703b7bfabeb3a497..e61acd5463145e4a54dcc816c1da774922ed0127 100644
--- a/kernel/sched/debug.c
+++ b/kernel/sched/debug.c
@@ -536,6 +536,8 @@ static __init int sched_init_debug(void)
 
 	debugfs_fair_server_init();
 
+	debugfs_eevdf_testing_init(debugfs_sched);
+
 	return 0;
 }
 late_initcall(sched_init_debug);
diff --git a/kernel/sched/eevdf-tests.c b/kernel/sched/eevdf-tests.c
new file mode 100644
index 0000000000000000000000000000000000000000..3bc016d3025733e53f586e30fcd31f650156d47e
--- /dev/null
+++ b/kernel/sched/eevdf-tests.c
@@ -0,0 +1,27 @@
+// SPDX-License-Identifier: GPL-2.0
+
+/*
+ * Copyright (C) 2025 Advanced Micro Devices, Inc
+ *
+ * Author: Dhaval Giani (AMD) <dhaval@gianis.ca>
+ *
+ * Basic functional tests for EEVDF - Invariants
+ *
+ * Use the debugfs triggers to run them
+ *
+ */
+
+#include <linux/debugfs.h>
+#include <linux/sched.h>
+
+#include "sched.h"
+
+#ifdef CONFIG_SCHED_EEVDF_TESTING
+
+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);
+
+}
+#endif /* CONFIG_SCHED_EEVDF_TESTING */
diff --git a/kernel/sched/sched.h b/kernel/sched/sched.h
index c5a6a503eb6de3867ea25f13dca3660da2805ff8..09cefe2aa871bbd533a413c76026895e969a58e7 100644
--- a/kernel/sched/sched.h
+++ b/kernel/sched/sched.h
@@ -44,6 +44,7 @@
 #include <linux/lockdep.h>
 #include <linux/minmax.h>
 #include <linux/mm.h>
+#include <linux/mmu_context.h>
 #include <linux/module.h>
 #include <linux/mutex_api.h>
 #include <linux/plist.h>
@@ -3987,4 +3988,10 @@ void sched_enq_and_set_task(struct sched_enq_and_set_ctx *ctx);
 
 #include "ext.h"
 
+#ifdef CONFIG_SCHED_EEVDF_TESTING
+void debugfs_eevdf_testing_init(struct dentry *debugfs_sched);
+#else /* CONFIG_SCHED_EEVDF_TESTING */
+static inline void init_eevdf_testing_debugfs(struct dentry *debugfs_sched) {}
+#endif /* CONFIG_SCHED_EEVDF_TESTING */
+
 #endif /* _KERNEL_SCHED_SCHED_H */

-- 
2.49.0

Re: [PATCH 1/3] sched/fair: Introduce a new debugfs directory for EEVDF tests

[kernel test robot]

Hi Dhaval,

kernel test robot noticed the following build errors:

[auto build test ERROR on tip/sched/core]
[also build test ERROR on linus/master v6.15-rc5 next-20250506]
[If your patch is applied to the wrong git tree, kindly drop us a note.
And when submitting patch, we suggest to use '--base' as documented in
https://git-scm.com/docs/git-format-patch#_base_tree_information]

url:    https://github.com/intel-lab-lkp/linux/commits/Dhaval-Giani-AMD/sched-fair-Add-a-test-to-test-that-a-task-selected-to-run-has-positive-lag/20250423-081648
base:   tip/sched/core
patch link:    https://lore.kernel.org/r/20250422-b4-eevdf-tests-v1-post-v1-1-5b174f040f55%40gianis.ca
patch subject: [PATCH 1/3] sched/fair: Introduce a new debugfs directory for EEVDF tests
config: arc-allnoconfig (https://download.01.org/0day-ci/archive/20250507/202505071441.9cwPFBsc-lkp@intel.com/config)
compiler: arc-linux-gcc (GCC) 14.2.0
reproduce (this is a W=1 build): (https://download.01.org/0day-ci/archive/20250507/202505071441.9cwPFBsc-lkp@intel.com/reproduce)

If you fix the issue in a separate patch/commit (i.e. not just a new version of
the same patch/commit), kindly add following tags
| Reported-by: kernel test robot <lkp@intel.com>
| Closes: https://lore.kernel.org/oe-kbuild-all/202505071441.9cwPFBsc-lkp@intel.com/

All errors (new ones prefixed by >>):

   In file included from kernel/sched/build_utility.c:71:
   kernel/sched/debug.c: In function 'sched_init_debug':
>> kernel/sched/debug.c:539:9: error: implicit declaration of function 'debugfs_eevdf_testing_init' [-Wimplicit-function-declaration]
     539 |         debugfs_eevdf_testing_init(debugfs_sched);
         |         ^~~~~~~~~~~~~~~~~~~~~~~~~~


vim +/debugfs_eevdf_testing_init +539 kernel/sched/debug.c

   534	
   535		debugfs_create_file("debug", 0444, debugfs_sched, NULL, &sched_debug_fops);
   536	
   537		debugfs_fair_server_init();
   538	
 > 539		debugfs_eevdf_testing_init(debugfs_sched);
   540	
   541		return 0;
   542	}
   543	late_initcall(sched_init_debug);
   544	

-- 
0-DAY CI Kernel Test Service
https://github.com/intel/lkp-tests/wiki

[PATCH 0/3] sched/eevdf: Introduce functional invariants for EEVDF

[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>

[PATCH 1/3] sched/fair: Introduce a new debugfs directory for EEVDF tests

[Dhaval Giani (AMD)]

To: Ingo Molnar <mingo@redhat.com>
To: Peter Zijlstra <peterz@infradead.org>
To: Juri Lelli <juri.lelli@redhat.com>
To: Vincent Guittot <vincent.guittot@linaro.org>
To: Dietmar Eggemann <dietmar.eggemann@arm.com>
To: Steven Rostedt <rostedt@goodmis.org>
To: Ben Segall <bsegall@google.com>
To: Mel Gorman <mgorman@suse.de>
To: Valentin Schneider <vschneid@redhat.com>
Cc: linux-kernel@vger.kernel.org
Cc: Dhaval Giani <dhaval.giani@amd.com>
Cc: Gautham Shenoy <gautham.shenoy@amd.com>
Cc: K Prateek Nayak <kprateek.nayak@amd.com>
Signed-off-by: Dhaval Giani (AMD) <dhaval@gianis.ca>
---
 kernel/Kconfig.preempt     |  9 +++++++++
 kernel/sched/Makefile      |  1 +
 kernel/sched/debug.c       |  2 ++
 kernel/sched/eevdf-tests.c | 27 +++++++++++++++++++++++++++
 kernel/sched/sched.h       |  7 +++++++
 5 files changed, 46 insertions(+)

diff --git a/kernel/Kconfig.preempt b/kernel/Kconfig.preempt
index 54ea59ff8fbeb653b7084a78bd0d933076deaad5..96f47cf498aa10d7cbb375093e5533753ed7a414 100644
--- a/kernel/Kconfig.preempt
+++ b/kernel/Kconfig.preempt
@@ -176,3 +176,12 @@ config SCHED_CLASS_EXT
 	  For more information:
 	    Documentation/scheduler/sched-ext.rst
 	    https://github.com/sched-ext/scx
+
+config SCHED_EEVDF_TESTING
+	bool "EEVDF testing"
+	help
+	  This option is a debug option to test that your changes to the
+	  fair scheduling code do not break EEVDF invariants. There are
+	  controls exposted in debugfs to allow tests to be run. This has a
+	  performance impact, so do not enable unless you are a scheduler
+	  developer and know what you are doing.
diff --git a/kernel/sched/Makefile b/kernel/sched/Makefile
index 8ae86371ddcddf836172ee93ca34f2e91b4057a7..1a8416b8009ebf7cf38ac7b326f4b6472e62909a 100644
--- a/kernel/sched/Makefile
+++ b/kernel/sched/Makefile
@@ -37,3 +37,4 @@ obj-y += core.o
 obj-y += fair.o
 obj-y += build_policy.o
 obj-y += build_utility.o
+obj-y += eevdf-tests.o
diff --git a/kernel/sched/debug.c b/kernel/sched/debug.c
index 557246880a7e0839277df662703b7bfabeb3a497..e61acd5463145e4a54dcc816c1da774922ed0127 100644
--- a/kernel/sched/debug.c
+++ b/kernel/sched/debug.c
@@ -536,6 +536,8 @@ static __init int sched_init_debug(void)
 
 	debugfs_fair_server_init();
 
+	debugfs_eevdf_testing_init(debugfs_sched);
+
 	return 0;
 }
 late_initcall(sched_init_debug);
diff --git a/kernel/sched/eevdf-tests.c b/kernel/sched/eevdf-tests.c
new file mode 100644
index 0000000000000000000000000000000000000000..3bc016d3025733e53f586e30fcd31f650156d47e
--- /dev/null
+++ b/kernel/sched/eevdf-tests.c
@@ -0,0 +1,27 @@
+// SPDX-License-Identifier: GPL-2.0
+
+/*
+ * Copyright (C) 2025 Advanced Micro Devices, Inc
+ *
+ * Author: Dhaval Giani (AMD) <dhaval@gianis.ca>
+ *
+ * Basic functional tests for EEVDF - Invariants
+ *
+ * Use the debugfs triggers to run them
+ *
+ */
+
+#include <linux/debugfs.h>
+#include <linux/sched.h>
+
+#include "sched.h"
+
+#ifdef CONFIG_SCHED_EEVDF_TESTING
+
+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);
+
+}
+#endif /* CONFIG_SCHED_EEVDF_TESTING */
diff --git a/kernel/sched/sched.h b/kernel/sched/sched.h
index c5a6a503eb6de3867ea25f13dca3660da2805ff8..09cefe2aa871bbd533a413c76026895e969a58e7 100644
--- a/kernel/sched/sched.h
+++ b/kernel/sched/sched.h
@@ -44,6 +44,7 @@
 #include <linux/lockdep.h>
 #include <linux/minmax.h>
 #include <linux/mm.h>
+#include <linux/mmu_context.h>
 #include <linux/module.h>
 #include <linux/mutex_api.h>
 #include <linux/plist.h>
@@ -3987,4 +3988,10 @@ void sched_enq_and_set_task(struct sched_enq_and_set_ctx *ctx);
 
 #include "ext.h"
 
+#ifdef CONFIG_SCHED_EEVDF_TESTING
+void debugfs_eevdf_testing_init(struct dentry *debugfs_sched);
+#else /* CONFIG_SCHED_EEVDF_TESTING */
+static inline void init_eevdf_testing_debugfs(struct dentry *debugfs_sched) {}
+#endif /* CONFIG_SCHED_EEVDF_TESTING */
+
 #endif /* _KERNEL_SCHED_SCHED_H */

-- 
2.49.0

Re: [PATCH 1/3] sched/fair: Introduce a new debugfs directory for EEVDF tests

[kernel test robot]

Hi Dhaval,

kernel test robot noticed the following build errors:

[auto build test ERROR on c70fc32f44431bb30f9025ce753ba8be25acbba3]

url:    https://github.com/intel-lab-lkp/linux/commits/Dhaval-Giani-AMD/sched-fair-Introduce-a-new-debugfs-directory-for-EEVDF-tests/20250423-082221
base:   c70fc32f44431bb30f9025ce753ba8be25acbba3
patch link:    https://lore.kernel.org/r/20250422-b4-eevdf-tests-v1-post-v1-1-35d158254c72%40gianis.ca
patch subject: [PATCH 1/3] sched/fair: Introduce a new debugfs directory for EEVDF tests
config: x86_64-kexec (https://download.01.org/0day-ci/archive/20250507/202505071739.GJbmEQJp-lkp@intel.com/config)
compiler: clang version 20.1.2 (https://github.com/llvm/llvm-project 58df0ef89dd64126512e4ee27b4ac3fd8ddf6247)
reproduce (this is a W=1 build): (https://download.01.org/0day-ci/archive/20250507/202505071739.GJbmEQJp-lkp@intel.com/reproduce)

If you fix the issue in a separate patch/commit (i.e. not just a new version of
the same patch/commit), kindly add following tags
| Reported-by: kernel test robot <lkp@intel.com>
| Closes: https://lore.kernel.org/oe-kbuild-all/202505071739.GJbmEQJp-lkp@intel.com/

All errors (new ones prefixed by >>):

   In file included from kernel/sched/build_utility.c:71:
>> kernel/sched/debug.c:539:2: error: call to undeclared function 'debugfs_eevdf_testing_init'; ISO C99 and later do not support implicit function declarations [-Wimplicit-function-declaration]
     539 |         debugfs_eevdf_testing_init(debugfs_sched);
         |         ^
   1 error generated.


vim +/debugfs_eevdf_testing_init +539 kernel/sched/debug.c

   534	
   535		debugfs_create_file("debug", 0444, debugfs_sched, NULL, &sched_debug_fops);
   536	
   537		debugfs_fair_server_init();
   538	
 > 539		debugfs_eevdf_testing_init(debugfs_sched);
   540	
   541		return 0;
   542	}
   543	late_initcall(sched_init_debug);
   544	

-- 
0-DAY CI Kernel Test Service
https://github.com/intel/lkp-tests/wiki

[PATCH 0/3] sched/eevdf: Introduce functional invariants for EEVDF

[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>

[PATCH 1/3] sched/fair: Introduce a new debugfs directory for EEVDF tests

[Dhaval Giani (AMD)]

Signed-off-by: Dhaval Giani (AMD) <dhaval@gianis.ca>
---
 kernel/Kconfig.preempt     |  9 +++++++++
 kernel/sched/Makefile      |  1 +
 kernel/sched/debug.c       |  2 ++
 kernel/sched/eevdf-tests.c | 27 +++++++++++++++++++++++++++
 kernel/sched/sched.h       |  7 +++++++
 5 files changed, 46 insertions(+)

diff --git a/kernel/Kconfig.preempt b/kernel/Kconfig.preempt
index 54ea59ff8fbeb653b7084a78bd0d933076deaad5..96f47cf498aa10d7cbb375093e5533753ed7a414 100644
--- a/kernel/Kconfig.preempt
+++ b/kernel/Kconfig.preempt
@@ -176,3 +176,12 @@ config SCHED_CLASS_EXT
 	  For more information:
 	    Documentation/scheduler/sched-ext.rst
 	    https://github.com/sched-ext/scx
+
+config SCHED_EEVDF_TESTING
+	bool "EEVDF testing"
+	help
+	  This option is a debug option to test that your changes to the
+	  fair scheduling code do not break EEVDF invariants. There are
+	  controls exposted in debugfs to allow tests to be run. This has a
+	  performance impact, so do not enable unless you are a scheduler
+	  developer and know what you are doing.
diff --git a/kernel/sched/Makefile b/kernel/sched/Makefile
index 8ae86371ddcddf836172ee93ca34f2e91b4057a7..1a8416b8009ebf7cf38ac7b326f4b6472e62909a 100644
--- a/kernel/sched/Makefile
+++ b/kernel/sched/Makefile
@@ -37,3 +37,4 @@ obj-y += core.o
 obj-y += fair.o
 obj-y += build_policy.o
 obj-y += build_utility.o
+obj-y += eevdf-tests.o
diff --git a/kernel/sched/debug.c b/kernel/sched/debug.c
index 557246880a7e0839277df662703b7bfabeb3a497..e61acd5463145e4a54dcc816c1da774922ed0127 100644
--- a/kernel/sched/debug.c
+++ b/kernel/sched/debug.c
@@ -536,6 +536,8 @@ static __init int sched_init_debug(void)
 
 	debugfs_fair_server_init();
 
+	debugfs_eevdf_testing_init(debugfs_sched);
+
 	return 0;
 }
 late_initcall(sched_init_debug);
diff --git a/kernel/sched/eevdf-tests.c b/kernel/sched/eevdf-tests.c
new file mode 100644
index 0000000000000000000000000000000000000000..3bc016d3025733e53f586e30fcd31f650156d47e
--- /dev/null
+++ b/kernel/sched/eevdf-tests.c
@@ -0,0 +1,27 @@
+// SPDX-License-Identifier: GPL-2.0
+
+/*
+ * Copyright (C) 2025 Advanced Micro Devices, Inc
+ *
+ * Author: Dhaval Giani (AMD) <dhaval@gianis.ca>
+ *
+ * Basic functional tests for EEVDF - Invariants
+ *
+ * Use the debugfs triggers to run them
+ *
+ */
+
+#include <linux/debugfs.h>
+#include <linux/sched.h>
+
+#include "sched.h"
+
+#ifdef CONFIG_SCHED_EEVDF_TESTING
+
+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);
+
+}
+#endif /* CONFIG_SCHED_EEVDF_TESTING */
diff --git a/kernel/sched/sched.h b/kernel/sched/sched.h
index c5a6a503eb6de3867ea25f13dca3660da2805ff8..09cefe2aa871bbd533a413c76026895e969a58e7 100644
--- a/kernel/sched/sched.h
+++ b/kernel/sched/sched.h
@@ -44,6 +44,7 @@
 #include <linux/lockdep.h>
 #include <linux/minmax.h>
 #include <linux/mm.h>
+#include <linux/mmu_context.h>
 #include <linux/module.h>
 #include <linux/mutex_api.h>
 #include <linux/plist.h>
@@ -3987,4 +3988,10 @@ void sched_enq_and_set_task(struct sched_enq_and_set_ctx *ctx);
 
 #include "ext.h"
 
+#ifdef CONFIG_SCHED_EEVDF_TESTING
+void debugfs_eevdf_testing_init(struct dentry *debugfs_sched);
+#else /* CONFIG_SCHED_EEVDF_TESTING */
+static inline void init_eevdf_testing_debugfs(struct dentry *debugfs_sched) {}
+#endif /* CONFIG_SCHED_EEVDF_TESTING */
+
 #endif /* _KERNEL_SCHED_SCHED_H */

-- 
2.49.0