From nobody Mon Feb 9 01:01:56 2026 Received: from mail-4323.protonmail.ch (mail-4323.protonmail.ch [185.70.43.23]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 6BC411EFFBE for ; Wed, 23 Apr 2025 00:20:20 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=185.70.43.23 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1745367622; cv=none; b=f4ZwEB6qmpemtDZJ7q2ia1Qp2jLk9NWJVySRWlGBNGGEox1zlxCXt9COQDI1l9Qujm+5wyZqB51cIyqqvvqOznCO6hIXRsvsGoyr7vHpQ+hbfYn7gLsDSdqDd0aMJHZE+oLJwpfUt6EcYVgNBsUIPebF06+UyRJnjttXFfF3s9k= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1745367622; c=relaxed/simple; bh=+r3R+rr2bW0jfdEyFH6BjapHu/ndfnpWM2yE25YJd2c=; h=Date:To:From:Cc:Subject:Message-ID:In-Reply-To:References: MIME-Version:Content-Type; b=flRIyaeaXkeMattNCsXjixp/HweD/oUpMOQM/a6N5EvAuZd8ACAsW1moFDcwlFZwQiCd5BvyeDFvouZpfzuLDN0T1/+H0OjazLd2Wl+4buvjLv4K1QWyybA16rIJscffZH+Eig3hu6DY+WxLLLas0pgoJaqCKay6dpgmMeQbvTI= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gianis.ca; spf=pass smtp.mailfrom=gianis.ca; dkim=pass (2048-bit key) header.d=gianis.ca header.i=@gianis.ca header.b=gsF/xgNZ; arc=none smtp.client-ip=185.70.43.23 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gianis.ca Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=gianis.ca Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=gianis.ca header.i=@gianis.ca header.b="gsF/xgNZ" DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gianis.ca; s=protonmail; t=1745367618; x=1745626818; bh=dk+pasafF4bM7w+MFfwsEvyKgaRymc8SSrDzFjrIskQ=; h=Date:To:From:Cc:Subject:Message-ID:In-Reply-To:References: Feedback-ID:From:To:Cc:Date:Subject:Reply-To:Feedback-ID: Message-ID:BIMI-Selector:List-Unsubscribe:List-Unsubscribe-Post; b=gsF/xgNZz9F+qYh3bwgztJo+49+eal2kVBMuTXUnF7qNnYDW561DF61Q0FBB9weYs 4cw/dYk0VGK7VGQcyQGUCMY39bGCX3EaA1dfTRepHgqbvq6AeUtnnuUVLfE1XR3Mzc Ge+CCJpJos+Nk+ye8xhrefcFkL6iXqSqPG38DxzEuMQhm6es+x7cPdRZbzcseBQb3Z Tr/EPloIHhsg9Y69eXXxcxlXpEAN/U1uCk6LmPOLlMh3vAZvSgz4A3pJy+jW3XlQOq N9DX0H1fCCqIwgDiqdvmCZO79Xya9k6PbOScC5uL8DgiZiankBQjL+aMgK10VwU410 8KgCueI2GeYQg== Date: Wed, 23 Apr 2025 00:20:14 +0000 To: Ingo Molnar , Peter Zijlstra , Juri Lelli , Vincent Guittot , Dietmar Eggemann , Steven Rostedt , Ben Segall , Mel Gorman , Valentin Schneider From: "Dhaval Giani (AMD)" Cc: linux-kernel@vger.kernel.org, Dhaval Giani , Gautham Shenoy , K Prateek Nayak , "Dhaval Giani (AMD)" Subject: [PATCH 1/3] sched/fair: Introduce a new debugfs directory for EEVDF tests Message-ID: <20250422-b4-eevdf-tests-v1-post-v1-1-35d158254c72@gianis.ca> In-Reply-To: <20250422-b4-eevdf-tests-v1-post-v1-0-35d158254c72@gianis.ca> References: <20250422-b4-eevdf-tests-v1-post-v1-0-35d158254c72@gianis.ca> Feedback-ID: 128275035:user:proton X-Pm-Message-ID: d7f28bbef72c90bc7d8a399e3a768f4d2324476b Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset="utf-8" To: Ingo Molnar To: Peter Zijlstra To: Juri Lelli To: Vincent Guittot To: Dietmar Eggemann To: Steven Rostedt To: Ben Segall To: Mel Gorman To: Valentin Schneider Cc: linux-kernel@vger.kernel.org Cc: Dhaval Giani Cc: Gautham Shenoy Cc: K Prateek Nayak Signed-off-by: Dhaval Giani (AMD) --- 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..96f47cf498aa10d7cbb375093e5= 533753ed7a414 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..1a8416b8009ebf7cf38ac7b326f= 4b6472e62909a 100644 --- a/kernel/sched/Makefile +++ b/kernel/sched/Makefile @@ -37,3 +37,4 @@ obj-y +=3D core.o obj-y +=3D fair.o obj-y +=3D build_policy.o obj-y +=3D build_utility.o +obj-y +=3D eevdf-tests.o diff --git a/kernel/sched/debug.c b/kernel/sched/debug.c index 557246880a7e0839277df662703b7bfabeb3a497..e61acd5463145e4a54dcc816c1d= a774922ed0127 100644 --- a/kernel/sched/debug.c +++ b/kernel/sched/debug.c @@ -536,6 +536,8 @@ static __init int sched_init_debug(void) =20 debugfs_fair_server_init(); =20 + 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..3bc016d3025733e53f586e30fcd= 31f650156d47e --- /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) + * + * Basic functional tests for EEVDF - Invariants + * + * Use the debugfs triggers to run them + * + */ + +#include +#include + +#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 =3D debugfs_create_dir("eevdf-testing", debugfs_sch= ed); + +} +#endif /* CONFIG_SCHED_EEVDF_TESTING */ diff --git a/kernel/sched/sched.h b/kernel/sched/sched.h index c5a6a503eb6de3867ea25f13dca3660da2805ff8..09cefe2aa871bbd533a413c7602= 6895e969a58e7 100644 --- a/kernel/sched/sched.h +++ b/kernel/sched/sched.h @@ -44,6 +44,7 @@ #include #include #include +#include #include #include #include @@ -3987,4 +3988,10 @@ void sched_enq_and_set_task(struct sched_enq_and_set= _ctx *ctx); =20 #include "ext.h" =20 +#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 */ --=20 2.49.0 From nobody Mon Feb 9 01:01:56 2026 Received: from mail-10627.protonmail.ch (mail-10627.protonmail.ch [79.135.106.27]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id A862F1EEA4A for ; Wed, 23 Apr 2025 00:20:31 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=79.135.106.27 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1745367633; cv=none; b=r6ak/ZM8u43Sdqr/nzHT+jbfOhOLmsjQq1BlEZsBXr8wdWLyRG6USjqtCwkU6gA8X1tR4B7osVD+JfxvJeWln535c7ddkTL+Q1vxH6EmTayls9pslHQFDjrGyxpQ+p4ocP6BrhmLQkiFE3KXhf7dygjDI4zE2kiQDHMtYfl3hiE= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1745367633; c=relaxed/simple; bh=Rj+1L7wiGc50aCgbicmrIfLIlsPYyFqQnB3WkNjAi7w=; h=Date:To:From:Cc:Subject:Message-ID:In-Reply-To:References: MIME-Version:Content-Type; b=rLFaSEFjrVgBXzmlPB3w9ECYiRxOvlER3fdxRCLfvtH7OZqAduGEmwhUisROeENyHH9YDZ/Bstjd30iBYb79qsH29JaKg6TAiCyntKoESVS8wuxfXnv9u3roNiZrlx2SP6lUg+DuPsvzo+XL2uHNAJFAGN9wo5YA9IlUyK3jLfI= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gianis.ca; spf=pass smtp.mailfrom=gianis.ca; dkim=pass (2048-bit key) header.d=gianis.ca header.i=@gianis.ca header.b=hFgYO+g1; arc=none smtp.client-ip=79.135.106.27 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gianis.ca Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=gianis.ca Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=gianis.ca header.i=@gianis.ca header.b="hFgYO+g1" DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gianis.ca; s=protonmail; t=1745367629; x=1745626829; bh=qWMVyorMyU7WrTA+bky3Xgb1ylZ1FY0Pzqsqe9JTPKI=; h=Date:To:From:Cc:Subject:Message-ID:In-Reply-To:References: Feedback-ID:From:To:Cc:Date:Subject:Reply-To:Feedback-ID: Message-ID:BIMI-Selector:List-Unsubscribe:List-Unsubscribe-Post; b=hFgYO+g17Z7f0z7U1SH712Qf0n/1MSMi9uNpqT1n0hSAFpeyxvN+c9R1CVG5WSvHG QzuhCt9hAdkw6g7HB5o1eEIHuKmYX6MTY+i8UfgJU7QL4vIvMHnz2vaVPOvwAKWVVq ZXsX8kXSLjNLevDd4YHuDABEgOorG4NdfreLWCGL9G8rhsqAV6mhrlBW14spEcI3fY vTz/qQ+J8HBCPII1Qk9zGTZW/MDlIEt60nOhX5LHg7yY6B+09AisDu5IOkPZqd1RX9 FvHN1fQavk4CU8gFsl8lOxlgGB8pd57JzDEQlDwUEiTZUPUnz38+RC52Y0fV8if8u7 hoC+2jJlbN8EA== Date: Wed, 23 Apr 2025 00:20:22 +0000 To: Ingo Molnar , Peter Zijlstra , Juri Lelli , Vincent Guittot , Dietmar Eggemann , Steven Rostedt , Ben Segall , Mel Gorman , Valentin Schneider From: "Dhaval Giani (AMD)" Cc: linux-kernel@vger.kernel.org, Dhaval Giani , Gautham Shenoy , K Prateek Nayak , "Dhaval Giani (AMD)" Subject: [PATCH 2/3] sched/fair: Add a test to test that a task selected to run has positive lag Message-ID: <20250422-b4-eevdf-tests-v1-post-v1-2-35d158254c72@gianis.ca> In-Reply-To: <20250422-b4-eevdf-tests-v1-post-v1-0-35d158254c72@gianis.ca> References: <20250422-b4-eevdf-tests-v1-post-v1-0-35d158254c72@gianis.ca> Feedback-ID: 128275035:user:proton X-Pm-Message-ID: a9caaeb7b2dd126acf537f9ed036f7b74efe0297 Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset="utf-8" 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. To: Ingo Molnar To: Peter Zijlstra To: Juri Lelli To: Vincent Guittot To: Dietmar Eggemann To: Steven Rostedt To: Ben Segall To: Mel Gorman To: Valentin Schneider Cc: linux-kernel@vger.kernel.org Cc: Dhaval Giani Cc: Gautham Shenoy Cc: K Prateek Nayak Signed-off-by: Dhaval Giani (AMD) --- 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..8532330769bcc93dbf9cd98ebba= 75c838f62c045 100644 --- a/kernel/sched/eevdf-tests.c +++ b/kernel/sched/eevdf-tests.c @@ -18,10 +18,51 @@ =20 #ifdef CONFIG_SCHED_EEVDF_TESTING =20 +/* + * Test parameters + */ +bool eevdf_positive_lag_test; +u8 eevdf_positive_lag_count =3D 10; + static struct dentry *debugfs_eevdf_testing; void debugfs_eevdf_testing_init(struct dentry *debugfs_sched) { debugfs_eevdf_testing =3D debugfs_create_dir("eevdf-testing", debugfs_sch= ed); =20 + 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 =3D 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 =3D 0; + eevdf_positive_lag_test_counter =3D 0; + return; + } + + if (eevdf_positive_lag_test_counter > eevdf_positive_lag_count) { + eevdf_positive_lag_test =3D 0; + eevdf_positive_lag_test_counter =3D 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..924d9d35c2aa937bc0f4ca9565b= a774397b90f77 100644 --- a/kernel/sched/fair.c +++ b/kernel/sched/fair.c @@ -980,6 +980,8 @@ static struct sched_entity *pick_eevdf(struct cfs_rq *c= fs_rq) if (!best || (curr && entity_before(curr, best))) best =3D curr; =20 + test_eevdf_positive_lag(cfs_rq, best); + return best; } =20 diff --git a/kernel/sched/sched.h b/kernel/sched/sched.h index 09cefe2aa871bbd533a413c76026895e969a58e7..5ad5e033e1c81167b712ab176d4= d55e6b5d82d06 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); =20 #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 sche= d_entity *se) {} #endif /* CONFIG_SCHED_EEVDF_TESTING */ =20 #endif /* _KERNEL_SCHED_SCHED_H */ --=20 2.49.0 From nobody Mon Feb 9 01:01:56 2026 Received: from mail-24422.protonmail.ch (mail-24422.protonmail.ch [109.224.244.22]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 553B01F152E for ; Wed, 23 Apr 2025 00:20:43 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=109.224.244.22 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1745367645; cv=none; b=ZRxBquCDV+yIiuodsoKI+g87Teo51sXc2fRrJpv3Kb5ZhJR/qE9pR24Qp9EQIhBOElgmENzwuHtjmgujUAoQRZZ4KPd4Ve1qOf/TK9iSbYu69ihfqbJz6rjt9xfA1yK8IWR2YPseOMXlNL4Bcju1izTtfEsiWYQwLEYh7ZzBmjA= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1745367645; c=relaxed/simple; bh=yKWL4jY2BDIdsh1Ps7x8Yc3DgzHrdvlNGJSABfpgIts=; h=Date:To:From:Cc:Subject:Message-ID:In-Reply-To:References: MIME-Version:Content-Type; b=GSiHlRxqNd5lzFuCObofMk9HIoKhqxY50lPPrX9kNK8dloI42uaP341TZUNHBMbVjf4dNOkmbeGNWZL4GmIVo11r0OvAK+/iCedC5Ftu/L+I8BOrOzlSQFQhkXCn3qanVj9qXrOftd/+B5vMxCKcK2CI/3u0cbg3FzVfynSJwkg= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gianis.ca; spf=pass smtp.mailfrom=gianis.ca; dkim=pass (2048-bit key) header.d=gianis.ca header.i=@gianis.ca header.b=nMkvV+tF; arc=none smtp.client-ip=109.224.244.22 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gianis.ca Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=gianis.ca Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=gianis.ca header.i=@gianis.ca header.b="nMkvV+tF" DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gianis.ca; s=protonmail; t=1745367635; x=1745626835; bh=TQv8xWy2SuXNR3w9HMn48sP4mhxMyjWREB0DUyFohuQ=; h=Date:To:From:Cc:Subject:Message-ID:In-Reply-To:References: Feedback-ID:From:To:Cc:Date:Subject:Reply-To:Feedback-ID: Message-ID:BIMI-Selector:List-Unsubscribe:List-Unsubscribe-Post; b=nMkvV+tF3YMF+8a37K8aUOvXMLd32B5LlkYEt33lyjPMbvwcKo4fEDeZcUZuIF21U Y/HCE28UD+cXdQPm/n7cN6MiqJF9+BOWjWTVkmQGbn34DNd3+2z0faoXDjgNHhU15p bl5VPr9Du7zOgd2XH9NZcrMkHJIxAbUzr30ud4ezd/IBfX0cfV6G8XuPRl2sUkIeYt ciCDe0ep2cVVEIlSen/dQz118m7I+HPZ2o+cu9eZTp2O2YNxWmy8Lz6TKU0dL/yyLB +ZejqyT+ITuyW737ZjxtWPoaZX3otpAWN2P+A35wCcRwW65dn9wwrDtlTcozYbnCGW 8bpDyPRz/jAnw== Date: Wed, 23 Apr 2025 00:20:31 +0000 To: Ingo Molnar , Peter Zijlstra , Juri Lelli , Vincent Guittot , Dietmar Eggemann , Steven Rostedt , Ben Segall , Mel Gorman , Valentin Schneider From: "Dhaval Giani (AMD)" Cc: linux-kernel@vger.kernel.org, Dhaval Giani , Gautham Shenoy , K Prateek Nayak , "Dhaval Giani (AMD)" Subject: [PATCH 3/3] sched/fair: Test that the average lag across the system is zero Message-ID: <20250422-b4-eevdf-tests-v1-post-v1-3-35d158254c72@gianis.ca> In-Reply-To: <20250422-b4-eevdf-tests-v1-post-v1-0-35d158254c72@gianis.ca> References: <20250422-b4-eevdf-tests-v1-post-v1-0-35d158254c72@gianis.ca> Feedback-ID: 128275035:user:proton X-Pm-Message-ID: ee092e29a38b4d4c7f6ab4f77a354ae860b6914c Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset="utf-8" Lemma 2 of the EEVDF paper says that the sum of lags of all the tasks in the system is zero. The test is slightly different - the sum of lag across a runqueue is zero. The linux EEVDF implementation doesn't track a global vruntime. Instead it tracks the "zero-lag" vruntime. This can be obtained by calling avg_vruntime(cfs_rq). Walk through every single CFS runqueue (per CPU as well as per-cgroup), and add up the vruntimes. The average should be the same as avg_vruntime. To: Ingo Molnar To: Peter Zijlstra To: Juri Lelli To: Vincent Guittot To: Dietmar Eggemann To: Steven Rostedt To: Ben Segall To: Mel Gorman To: Valentin Schneider Cc: linux-kernel@vger.kernel.org Cc: Dhaval Giani Cc: Gautham Shenoy Cc: K Prateek Nayak Signed-off-by: Dhaval Giani (AMD) --- include/linux/sched.h | 7 ++ kernel/sched/eevdf-tests.c | 174 +++++++++++++++++++++++++++++++++++++++++= ++++ kernel/sched/fair.c | 3 + 3 files changed, 184 insertions(+) diff --git a/include/linux/sched.h b/include/linux/sched.h index f96ac198289349199b9c671240a20fc7826228ad..72788d51912657919adfad7f451= 983e80be4fa39 100644 --- a/include/linux/sched.h +++ b/include/linux/sched.h @@ -610,6 +610,13 @@ struct sched_entity { */ struct sched_avg avg; #endif +#ifdef CONFIG_SCHED_EEVDF_TESTING + /* + * Add a list element so that we don't recurse + * in the EEVDF unit test + */ + struct list_head tg_entry; +#endif }; =20 struct sched_rt_entity { diff --git a/kernel/sched/eevdf-tests.c b/kernel/sched/eevdf-tests.c index 8532330769bcc93dbf9cd98ebba75c838f62c045..c343e94b9a44ad32d01a0eedcb6= 1c1bbf5fdbaf6 100644 --- a/kernel/sched/eevdf-tests.c +++ b/kernel/sched/eevdf-tests.c @@ -24,6 +24,35 @@ bool eevdf_positive_lag_test; u8 eevdf_positive_lag_count =3D 10; =20 +static int test_total_zero_lag(void *); +static void launch_test_zero_lag(void); + +static int eevdf_zero_lag_show(struct seq_file *m, void *v) +{ + return 0; +} + +static int eevdf_zero_lag_open(struct inode *inode, struct file *filp) +{ + return single_open(filp, eevdf_zero_lag_show, NULL); +} + +static ssize_t eevdf_zero_lag_write(struct file *filp, const char __user *= ubuf, + size_t cnt, loff_t *ppos) +{ + launch_test_zero_lag(); + return 1; + +} + +static const struct file_operations eevdf_zero_lag_fops =3D { + .open =3D eevdf_zero_lag_open, + .write =3D eevdf_zero_lag_write, + .read =3D seq_read, + .llseek =3D seq_lseek, + .release =3D single_release, +}; + static struct dentry *debugfs_eevdf_testing; void debugfs_eevdf_testing_init(struct dentry *debugfs_sched) { @@ -33,6 +62,8 @@ void debugfs_eevdf_testing_init(struct dentry *debugfs_sc= hed) debugfs_eevdf_testing, &eevdf_positive_lag_test); debugfs_create_u8("eevdf_positive_lag_test_count", 0600, debugfs_eevdf_testing, &eevdf_positive_lag_count); + debugfs_create_file("eevdf_zero_lag_test", 0700, debugfs_eevdf_testing, + NULL, &eevdf_zero_lag_fops); =20 } =20 @@ -65,4 +96,147 @@ void test_eevdf_positive_lag(struct cfs_rq *cfs, struct= sched_entity *se) } } =20 +/* + * we do, what we need to do + */ +#define __node_2_se(node) \ + rb_entry((node), struct sched_entity, run_node) + +static bool test_eevdf_cfs_rq_zero_lag(struct cfs_rq *cfs, struct list_hea= d *tg_se) +{ + u64 cfs_avg_vruntime; + u64 calculated_avg_vruntime; + + u64 total_vruntime =3D 0; + u64 nr_tasks =3D 0; + + struct sched_entity *se; + struct rb_node *node; + struct rb_root *root; + + cfs_avg_vruntime =3D avg_vruntime(cfs); + + /* + * Walk through the rb tree -> look at the se->vruntime value and add it + */ + + total_vruntime =3D 0; + nr_tasks =3D 0; + + root =3D &cfs->tasks_timeline.rb_root; + + for (node =3D rb_first(root); node; node =3D rb_next(node)) { + se =3D __node_2_se(node); + WARN_ON_ONCE(__builtin_add_overflow(total_vruntime, + se->vruntime, &total_vruntime)); + /* + * if it is a task group, add to a list to look at later + */ + if (!entity_is_task(se)) + list_add_tail(&se->tg_entry, tg_se); + nr_tasks++; + } + + if (cfs->curr) { + WARN_ON_ONCE(__builtin_add_overflow(total_vruntime, + cfs->curr->vruntime, &total_vruntime)); + nr_tasks++; + } + + /* If there are no tasks, there is no lag :-) */ + if (!nr_tasks) + return true; + + calculated_avg_vruntime =3D total_vruntime / nr_tasks; + + return (calculated_avg_vruntime =3D=3D cfs_avg_vruntime); + +} + +/* + * Call with rq lock held + * + * return false on failure + */ +static bool test_eevdf_zero_lag(struct cfs_rq *cfs) +{ + struct list_head tg_se =3D LIST_HEAD_INIT(tg_se); + struct list_head *se_entry; + + /* + * The base CFS runqueue will always have sched entities queued. + * Test it, and start populating the tg_se list. + * + * If it fails, short circuit and return fail. + */ + + if (!test_eevdf_cfs_rq_zero_lag(cfs, &tg_se)) + return false; + + /* + * We made it here, let's walk through the list. Since it is + * setup as a queue, as we continue calling the rq test, it + * will add new task_groups to the list. Once drained, if we + * haven't failed, we will return true. + */ + + list_for_each(se_entry, &tg_se) { + struct sched_entity *se =3D list_entry(se_entry, struct sched_entity, tg= _entry); + + if (!test_eevdf_cfs_rq_zero_lag(group_cfs_rq(se), &tg_se)) + return false; + } + + /* + * WOOT! We succeeded! + */ + return true; + +} + +/* + * The average vruntime of the entire cfs_rq should be equal + * to the avg_vruntime(cfs_rq) + */ +static int test_total_zero_lag(void *data) +{ + int cpu; + struct rq *rq; + struct cfs_rq *cfs; + bool success =3D false; + + for_each_online_cpu(cpu) { + + rq =3D cpu_rq(cpu); + guard(rq_lock_irq)(rq); + + cfs =3D &rq->cfs; + + success =3D test_eevdf_zero_lag(cfs); + + if (!success) + break; + } + if (!success) { + trace_printk("FAILED: tracked average vruntime doesn't match calculated = average vruntime\n"); + return -1; + } + trace_printk("PASS: Tracked average runtime matches calculated average vr= untime\n"); + return 0; +} + +static void launch_test_zero_lag(void) +{ + struct task_struct *kt; + + kt =3D kthread_create(&test_total_zero_lag, NULL, "eevdf-tester-%d", + smp_processor_id()); + if (!kt) { + trace_printk("Failed to launch kthread\n"); + return; + } + + wake_up_process(kt); +} + #endif /* CONFIG_SCHED_EEVDF_TESTING */ diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c index 924d9d35c2aa937bc0f4ca9565ba774397b90f77..858c4e1b8fac661996d879a8dca= b2776db09d1c8 100644 --- a/kernel/sched/fair.c +++ b/kernel/sched/fair.c @@ -13473,6 +13473,9 @@ void init_tg_cfs_entry(struct task_group *tg, struc= t cfs_rq *cfs_rq, /* guarantee group entities always have weight */ update_load_set(&se->load, NICE_0_LOAD); se->parent =3D parent; +#ifdef CONFIG_SCHED_EEVDF_TESTING + INIT_LIST_HEAD(&(se->group_node)); +#endif } =20 static DEFINE_MUTEX(shares_mutex); --=20 2.49.0