Reimplementation of the sched_football test from LTP:
https://github.com/linux-test-project/ltp/blob/master/testcases/realtime/func/sched_football/sched_football.c
But reworked to run in the kernel and utilize mutexes
to illustrate proper boosting of low priority mutex
holders.
TODO:
* Need a rt_mutex version so it can work w/o proxy-execution
* Need a better place to put it
Cc: Joel Fernandes <joelaf@google.com>
Cc: Qais Yousef <qyousef@google.com>
Cc: Ingo Molnar <mingo@redhat.com>
Cc: Peter Zijlstra <peterz@infradead.org>
Cc: Juri Lelli <juri.lelli@redhat.com>
Cc: Vincent Guittot <vincent.guittot@linaro.org>
Cc: Dietmar Eggemann <dietmar.eggemann@arm.com>
Cc: Valentin Schneider <vschneid@redhat.com>
Cc: Steven Rostedt <rostedt@goodmis.org>
Cc: Ben Segall <bsegall@google.com>
Cc: Zimuzo Ezeozue <zezeozue@google.com>
Cc: Youssef Esmat <youssefesmat@google.com>
Cc: Mel Gorman <mgorman@suse.de>
Cc: Daniel Bristot de Oliveira <bristot@redhat.com>
Cc: Will Deacon <will@kernel.org>
Cc: Waiman Long <longman@redhat.com>
Cc: Boqun Feng <boqun.feng@gmail.com>
Cc: "Paul E. McKenney" <paulmck@kernel.org>
Cc: Metin Kaya <Metin.Kaya@arm.com>
Cc: Xuewen Yan <xuewen.yan94@gmail.com>
Cc: K Prateek Nayak <kprateek.nayak@amd.com>
Cc: Thomas Gleixner <tglx@linutronix.de>
Cc: kernel-team@android.com
Signed-off-by: John Stultz <jstultz@google.com>
---
kernel/sched/Makefile | 1 +
kernel/sched/test_sched_football.c | 242 +++++++++++++++++++++++++++++
lib/Kconfig.debug | 14 ++
3 files changed, 257 insertions(+)
create mode 100644 kernel/sched/test_sched_football.c
diff --git a/kernel/sched/Makefile b/kernel/sched/Makefile
index 976092b7bd45..2729d565dfd7 100644
--- a/kernel/sched/Makefile
+++ b/kernel/sched/Makefile
@@ -32,3 +32,4 @@ obj-y += core.o
obj-y += fair.o
obj-y += build_policy.o
obj-y += build_utility.o
+obj-$(CONFIG_SCHED_RT_INVARIENT_TEST) += test_sched_football.o
diff --git a/kernel/sched/test_sched_football.c b/kernel/sched/test_sched_football.c
new file mode 100644
index 000000000000..9742c45c0fe0
--- /dev/null
+++ b/kernel/sched/test_sched_football.c
@@ -0,0 +1,242 @@
+// SPDX-License-Identifier: GPL-2.0+
+/*
+ * Module-based test case for RT scheduling invariant
+ *
+ * A reimplementation of my old sched_football test
+ * found in LTP:
+ * https://github.com/linux-test-project/ltp/blob/master/testcases/realtime/func/sched_football/sched_football.c
+ *
+ * Similar to that test, this tries to validate the RT
+ * scheduling invariant, that the across N available cpus, the
+ * top N priority tasks always running.
+ *
+ * This is done via having N offsensive players that are
+ * medium priority, which constantly are trying to increment the
+ * ball_pos counter.
+ *
+ * Blocking this, are N defensive players that are higher
+ * priority which just spin on the cpu, preventing the medium
+ * priroity tasks from running.
+ *
+ * To complicate this, there are also N defensive low priority
+ * tasks. These start first and each aquire one of N mutexes.
+ * The high priority defense tasks will later try to grab the
+ * mutexes and block, opening a window for the offsensive tasks
+ * to run and increment the ball. If priority inheritance or
+ * proxy execution is used, the low priority defense players
+ * should be boosted to the high priority levels, and will
+ * prevent the mid priority offensive tasks from running.
+ *
+ * Copyright © International Business Machines Corp., 2007, 2008
+ * Copyright (C) Google, 2023
+ *
+ * Authors: John Stultz <jstultz@google.com>
+ */
+
+#include <linux/kernel.h>
+#include <linux/module.h>
+#include <linux/kthread.h>
+#include <linux/delay.h>
+#include <linux/sched/rt.h>
+#include <linux/spinlock.h>
+#include <linux/mutex.h>
+#include <linux/rwsem.h>
+#include <linux/smp.h>
+#include <linux/slab.h>
+#include <linux/interrupt.h>
+#include <linux/sched.h>
+#include <uapi/linux/sched/types.h>
+#include <linux/rtmutex.h>
+
+atomic_t players_ready;
+atomic_t ball_pos;
+int players_per_team;
+bool game_over;
+
+struct mutex *mutex_low_list;
+struct mutex *mutex_mid_list;
+
+static inline
+struct task_struct *create_fifo_thread(int (*threadfn)(void *data), void *data,
+ char *name, int prio)
+{
+ struct task_struct *kth;
+ struct sched_attr attr = {
+ .size = sizeof(struct sched_attr),
+ .sched_policy = SCHED_FIFO,
+ .sched_nice = 0,
+ .sched_priority = prio,
+ };
+ int ret;
+
+ kth = kthread_create(threadfn, data, name);
+ if (IS_ERR(kth)) {
+ pr_warn("%s eerr, kthread_create failed\n", __func__);
+ return kth;
+ }
+ ret = sched_setattr_nocheck(kth, &attr);
+ if (ret) {
+ kthread_stop(kth);
+ pr_warn("%s: failed to set SCHED_FIFO\n", __func__);
+ return ERR_PTR(ret);
+ }
+
+ wake_up_process(kth);
+ return kth;
+}
+
+int defense_low_thread(void *arg)
+{
+ long tnum = (long)arg;
+
+ atomic_inc(&players_ready);
+ mutex_lock(&mutex_low_list[tnum]);
+ while (!READ_ONCE(game_over)) {
+ if (kthread_should_stop())
+ break;
+ schedule();
+ }
+ mutex_unlock(&mutex_low_list[tnum]);
+ return 0;
+}
+
+int defense_mid_thread(void *arg)
+{
+ long tnum = (long)arg;
+
+ atomic_inc(&players_ready);
+ mutex_lock(&mutex_mid_list[tnum]);
+ mutex_lock(&mutex_low_list[tnum]);
+ while (!READ_ONCE(game_over)) {
+ if (kthread_should_stop())
+ break;
+ schedule();
+ }
+ mutex_unlock(&mutex_low_list[tnum]);
+ mutex_unlock(&mutex_mid_list[tnum]);
+ return 0;
+}
+
+int offense_thread(void *)
+{
+ atomic_inc(&players_ready);
+ while (!READ_ONCE(game_over)) {
+ if (kthread_should_stop())
+ break;
+ schedule();
+ atomic_inc(&ball_pos);
+ }
+ return 0;
+}
+
+int defense_hi_thread(void *arg)
+{
+ long tnum = (long)arg;
+
+ atomic_inc(&players_ready);
+ mutex_lock(&mutex_mid_list[tnum]);
+ while (!READ_ONCE(game_over)) {
+ if (kthread_should_stop())
+ break;
+ schedule();
+ }
+ mutex_unlock(&mutex_mid_list[tnum]);
+ return 0;
+}
+
+int crazy_fan_thread(void *)
+{
+ int count = 0;
+
+ atomic_inc(&players_ready);
+ while (!READ_ONCE(game_over)) {
+ if (kthread_should_stop())
+ break;
+ schedule();
+ udelay(1000);
+ msleep(2);
+ count++;
+ }
+ return 0;
+}
+
+int ref_thread(void *arg)
+{
+ struct task_struct *kth;
+ long game_time = (long)arg;
+ unsigned long final_pos;
+ long i;
+
+ pr_info("%s: started ref, game_time: %ld secs !\n", __func__,
+ game_time);
+
+ /* Create low priority defensive team */
+ for (i = 0; i < players_per_team; i++)
+ kth = create_fifo_thread(defense_low_thread, (void *)i,
+ "defese-low-thread", 2);
+ /* Wait for the defense threads to start */
+ while (atomic_read(&players_ready) < players_per_team)
+ msleep(1);
+
+ for (i = 0; i < players_per_team; i++)
+ kth = create_fifo_thread(defense_mid_thread,
+ (void *)(players_per_team - i - 1),
+ "defese-mid-thread", 3);
+ /* Wait for the defense threads to start */
+ while (atomic_read(&players_ready) < players_per_team * 2)
+ msleep(1);
+
+ /* Create mid priority offensive team */
+ for (i = 0; i < players_per_team; i++)
+ kth = create_fifo_thread(offense_thread, NULL,
+ "offense-thread", 5);
+ /* Wait for the offense threads to start */
+ while (atomic_read(&players_ready) < players_per_team * 3)
+ msleep(1);
+
+ /* Create high priority defensive team */
+ for (i = 0; i < players_per_team; i++)
+ kth = create_fifo_thread(defense_hi_thread, (void *)i,
+ "defese-hi-thread", 10);
+ /* Wait for the defense threads to start */
+ while (atomic_read(&players_ready) < players_per_team * 4)
+ msleep(1);
+
+ /* Create high priority defensive team */
+ for (i = 0; i < players_per_team; i++)
+ kth = create_fifo_thread(crazy_fan_thread, NULL,
+ "crazy-fan-thread", 15);
+ /* Wait for the defense threads to start */
+ while (atomic_read(&players_ready) < players_per_team * 5)
+ msleep(1);
+
+ pr_info("%s: all players checked in! Starting game.\n", __func__);
+ atomic_set(&ball_pos, 0);
+ msleep(game_time * 1000);
+ final_pos = atomic_read(&ball_pos);
+ pr_info("%s: final ball_pos: %ld\n", __func__, final_pos);
+ WARN_ON(final_pos != 0);
+ game_over = true;
+ return 0;
+}
+
+static int __init test_sched_football_init(void)
+{
+ struct task_struct *kth;
+ int i;
+
+ players_per_team = num_online_cpus();
+
+ mutex_low_list = kmalloc_array(players_per_team, sizeof(struct mutex), GFP_ATOMIC);
+ mutex_mid_list = kmalloc_array(players_per_team, sizeof(struct mutex), GFP_ATOMIC);
+
+ for (i = 0; i < players_per_team; i++) {
+ mutex_init(&mutex_low_list[i]);
+ mutex_init(&mutex_mid_list[i]);
+ }
+
+ kth = create_fifo_thread(ref_thread, (void *)10, "ref-thread", 20);
+
+ return 0;
+}
+module_init(test_sched_football_init);
diff --git a/lib/Kconfig.debug b/lib/Kconfig.debug
index 4405f81248fb..1d90059d190f 100644
--- a/lib/Kconfig.debug
+++ b/lib/Kconfig.debug
@@ -1238,6 +1238,20 @@ config SCHED_DEBUG
that can help debug the scheduler. The runtime overhead of this
option is minimal.
+config SCHED_RT_INVARIENT_TEST
+ tristate "RT invarient scheduling tester"
+ depends on DEBUG_KERNEL
+ help
+ This option provides a kernel module that runs tests to make
+ sure the RT invarient holds (top N priority tasks run on N
+ available cpus).
+
+ Say Y here if you want kernel rt scheduling tests
+ to be built into the kernel.
+ Say M if you want this test to build as a module.
+ Say N if you are unsure.
+
+
config SCHED_INFO
bool
default n
--
2.43.0.472.g3155946c3a-googOn 20/12/2023 12:18 am, John Stultz wrote:
> Reimplementation of the sched_football test from LTP:
> https://github.com/linux-test-project/ltp/blob/master/testcases/realtime/func/sched_football/sched_football.c
>
> But reworked to run in the kernel and utilize mutexes
> to illustrate proper boosting of low priority mutex
> holders.
>
> TODO:
> * Need a rt_mutex version so it can work w/o proxy-execution
> * Need a better place to put it
>
> Cc: Joel Fernandes <joelaf@google.com>
> Cc: Qais Yousef <qyousef@google.com>
> Cc: Ingo Molnar <mingo@redhat.com>
> Cc: Peter Zijlstra <peterz@infradead.org>
> Cc: Juri Lelli <juri.lelli@redhat.com>
> Cc: Vincent Guittot <vincent.guittot@linaro.org>
> Cc: Dietmar Eggemann <dietmar.eggemann@arm.com>
> Cc: Valentin Schneider <vschneid@redhat.com>
> Cc: Steven Rostedt <rostedt@goodmis.org>
> Cc: Ben Segall <bsegall@google.com>
> Cc: Zimuzo Ezeozue <zezeozue@google.com>
> Cc: Youssef Esmat <youssefesmat@google.com>
> Cc: Mel Gorman <mgorman@suse.de>
> Cc: Daniel Bristot de Oliveira <bristot@redhat.com>
> Cc: Will Deacon <will@kernel.org>
> Cc: Waiman Long <longman@redhat.com>
> Cc: Boqun Feng <boqun.feng@gmail.com>
> Cc: "Paul E. McKenney" <paulmck@kernel.org>
> Cc: Metin Kaya <Metin.Kaya@arm.com>
> Cc: Xuewen Yan <xuewen.yan94@gmail.com>
> Cc: K Prateek Nayak <kprateek.nayak@amd.com>
> Cc: Thomas Gleixner <tglx@linutronix.de>
> Cc: kernel-team@android.com
> Signed-off-by: John Stultz <jstultz@google.com>
> ---
> kernel/sched/Makefile | 1 +
> kernel/sched/test_sched_football.c | 242 +++++++++++++++++++++++++++++
> lib/Kconfig.debug | 14 ++
> 3 files changed, 257 insertions(+)
> create mode 100644 kernel/sched/test_sched_football.c
>
> diff --git a/kernel/sched/Makefile b/kernel/sched/Makefile
> index 976092b7bd45..2729d565dfd7 100644
> --- a/kernel/sched/Makefile
> +++ b/kernel/sched/Makefile
> @@ -32,3 +32,4 @@ obj-y += core.o
> obj-y += fair.o
> obj-y += build_policy.o
> obj-y += build_utility.o
> +obj-$(CONFIG_SCHED_RT_INVARIENT_TEST) += test_sched_football.o
> diff --git a/kernel/sched/test_sched_football.c b/kernel/sched/test_sched_football.c
> new file mode 100644
> index 000000000000..9742c45c0fe0
> --- /dev/null
> +++ b/kernel/sched/test_sched_football.c
> @@ -0,0 +1,242 @@
> +// SPDX-License-Identifier: GPL-2.0+
> +/*
> + * Module-based test case for RT scheduling invariant
> + *
> + * A reimplementation of my old sched_football test
> + * found in LTP:
> + * https://github.com/linux-test-project/ltp/blob/master/testcases/realtime/func/sched_football/sched_football.c
> + *
> + * Similar to that test, this tries to validate the RT
> + * scheduling invariant, that the across N available cpus, the
> + * top N priority tasks always running.
> + *
> + * This is done via having N offsensive players that are
> + * medium priority, which constantly are trying to increment the
> + * ball_pos counter.
> + *
> + * Blocking this, are N defensive players that are higher
> + * priority which just spin on the cpu, preventing the medium
> + * priroity tasks from running.
> + *
> + * To complicate this, there are also N defensive low priority
> + * tasks. These start first and each aquire one of N mutexes.
> + * The high priority defense tasks will later try to grab the
> + * mutexes and block, opening a window for the offsensive tasks
> + * to run and increment the ball. If priority inheritance or
> + * proxy execution is used, the low priority defense players
> + * should be boosted to the high priority levels, and will
> + * prevent the mid priority offensive tasks from running.
> + *
> + * Copyright © International Business Machines Corp., 2007, 2008
> + * Copyright (C) Google, 2023
> + *
> + * Authors: John Stultz <jstultz@google.com>
> + */
> +
> +#include <linux/kernel.h>
> +#include <linux/module.h>
> +#include <linux/kthread.h>
> +#include <linux/delay.h>
> +#include <linux/sched/rt.h>
> +#include <linux/spinlock.h>
> +#include <linux/mutex.h>
> +#include <linux/rwsem.h>
> +#include <linux/smp.h>
> +#include <linux/slab.h>
> +#include <linux/interrupt.h>
> +#include <linux/sched.h>
> +#include <uapi/linux/sched/types.h>
> +#include <linux/rtmutex.h>
> +
> +atomic_t players_ready;
> +atomic_t ball_pos;
> +int players_per_team;
> +bool game_over;
> +
> +struct mutex *mutex_low_list;
> +struct mutex *mutex_mid_list;
> +
> +static inline
> +struct task_struct *create_fifo_thread(int (*threadfn)(void *data), void *data,
> + char *name, int prio)
> +{
> + struct task_struct *kth;
> + struct sched_attr attr = {
> + .size = sizeof(struct sched_attr),
> + .sched_policy = SCHED_FIFO,
> + .sched_nice = 0,
> + .sched_priority = prio,
> + };
> + int ret;
> +
> + kth = kthread_create(threadfn, data, name);
> + if (IS_ERR(kth)) {
> + pr_warn("%s eerr, kthread_create failed\n", __func__);
> + return kth;
> + }
> + ret = sched_setattr_nocheck(kth, &attr);
> + if (ret) {
> + kthread_stop(kth);
> + pr_warn("%s: failed to set SCHED_FIFO\n", __func__);
> + return ERR_PTR(ret);
> + }
> +
> + wake_up_process(kth);
> + return kth;
> +}
> +
> +int defense_low_thread(void *arg)
> +{
> + long tnum = (long)arg;
> +
> + atomic_inc(&players_ready);
> + mutex_lock(&mutex_low_list[tnum]);
> + while (!READ_ONCE(game_over)) {
> + if (kthread_should_stop())
> + break;
> + schedule();
> + }
> + mutex_unlock(&mutex_low_list[tnum]);
> + return 0;
> +}
> +
> +int defense_mid_thread(void *arg)
> +{
> + long tnum = (long)arg;
> +
> + atomic_inc(&players_ready);
> + mutex_lock(&mutex_mid_list[tnum]);
> + mutex_lock(&mutex_low_list[tnum]);
> + while (!READ_ONCE(game_over)) {
> + if (kthread_should_stop())
> + break;
> + schedule();
> + }
> + mutex_unlock(&mutex_low_list[tnum]);
> + mutex_unlock(&mutex_mid_list[tnum]);
> + return 0;
> +}
> +
> +int offense_thread(void *)
> +{
> + atomic_inc(&players_ready);
> + while (!READ_ONCE(game_over)) {
> + if (kthread_should_stop())
> + break;
> + schedule();
> + atomic_inc(&ball_pos);
> + }
> + return 0;
> +}
> +
> +int defense_hi_thread(void *arg)
> +{
> + long tnum = (long)arg;
> +
> + atomic_inc(&players_ready);
> + mutex_lock(&mutex_mid_list[tnum]);
> + while (!READ_ONCE(game_over)) {
> + if (kthread_should_stop())
> + break;
> + schedule();
> + }
> + mutex_unlock(&mutex_mid_list[tnum]);
> + return 0;
> +}
> +
> +int crazy_fan_thread(void *)
> +{
> + int count = 0;
> +
> + atomic_inc(&players_ready);
> + while (!READ_ONCE(game_over)) {
> + if (kthread_should_stop())
> + break;
> + schedule();
> + udelay(1000);
> + msleep(2);
> + count++;
@count is only increased. Is it really necessary?
> + }
> + return 0;
> +}
> +
> +int ref_thread(void *arg)
> +{
> + struct task_struct *kth;
> + long game_time = (long)arg;
> + unsigned long final_pos;
> + long i;
> +
> + pr_info("%s: started ref, game_time: %ld secs !\n", __func__,
> + game_time);
> +
> + /* Create low priority defensive team */
> + for (i = 0; i < players_per_team; i++)
> + kth = create_fifo_thread(defense_low_thread, (void *)i,
> + "defese-low-thread", 2);
> + /* Wait for the defense threads to start */
> + while (atomic_read(&players_ready) < players_per_team)
> + msleep(1);
> +
> + for (i = 0; i < players_per_team; i++)
> + kth = create_fifo_thread(defense_mid_thread,
> + (void *)(players_per_team - i - 1),
> + "defese-mid-thread", 3);
> + /* Wait for the defense threads to start */
> + while (atomic_read(&players_ready) < players_per_team * 2)
> + msleep(1);
> +
> + /* Create mid priority offensive team */
> + for (i = 0; i < players_per_team; i++)
> + kth = create_fifo_thread(offense_thread, NULL,
> + "offense-thread", 5);
> + /* Wait for the offense threads to start */
> + while (atomic_read(&players_ready) < players_per_team * 3)
> + msleep(1);
> +
> + /* Create high priority defensive team */
> + for (i = 0; i < players_per_team; i++)
> + kth = create_fifo_thread(defense_hi_thread, (void *)i,
> + "defese-hi-thread", 10);
> + /* Wait for the defense threads to start */
> + while (atomic_read(&players_ready) < players_per_team * 4)
> + msleep(1);
> +
> + /* Create high priority defensive team */
> + for (i = 0; i < players_per_team; i++)
> + kth = create_fifo_thread(crazy_fan_thread, NULL,
> + "crazy-fan-thread", 15);
> + /* Wait for the defense threads to start */
> + while (atomic_read(&players_ready) < players_per_team * 5)
> + msleep(1);
> +
> + pr_info("%s: all players checked in! Starting game.\n", __func__);
> + atomic_set(&ball_pos, 0);
> + msleep(game_time * 1000);
> + final_pos = atomic_read(&ball_pos);
> + pr_info("%s: final ball_pos: %ld\n", __func__, final_pos);
> + WARN_ON(final_pos != 0);
> + game_over = true;
> + return 0;
> +}
> +
> +static int __init test_sched_football_init(void)
> +{
> + struct task_struct *kth;
> + int i;
> +
> + players_per_team = num_online_cpus();
> +
> + mutex_low_list = kmalloc_array(players_per_team, sizeof(struct mutex), GFP_ATOMIC);
> + mutex_mid_list = kmalloc_array(players_per_team, sizeof(struct mutex), GFP_ATOMIC);
> +
> + for (i = 0; i < players_per_team; i++) {
> + mutex_init(&mutex_low_list[i]);
> + mutex_init(&mutex_mid_list[i]);
> + }
> +
> + kth = create_fifo_thread(ref_thread, (void *)10, "ref-thread", 20);
> +
> + return 0;
> +}
* Please prepend a prefix to prints to ease capturing the module logs.
* I think `rmmod test_sched_football` throws `Device or resource busy`
error and fails to remove the module because of missing module_exit().
> +module_init(test_sched_football_init);
> diff --git a/lib/Kconfig.debug b/lib/Kconfig.debug
> index 4405f81248fb..1d90059d190f 100644
> --- a/lib/Kconfig.debug
> +++ b/lib/Kconfig.debug
> @@ -1238,6 +1238,20 @@ config SCHED_DEBUG
> that can help debug the scheduler. The runtime overhead of this
> option is minimal.
>
> +config SCHED_RT_INVARIENT_TEST
> + tristate "RT invarient scheduling tester"
> + depends on DEBUG_KERNEL
> + help
> + This option provides a kernel module that runs tests to make
> + sure the RT invarient holds (top N priority tasks run on N
> + available cpus).
> +
> + Say Y here if you want kernel rt scheduling tests
> + to be built into the kernel.
> + Say M if you want this test to build as a module.
> + Say N if you are unsure.
> +
> +
> config SCHED_INFO
> bool
> default n
On Thu, Dec 28, 2023 at 8:36 AM Metin Kaya <metin.kaya@arm.com> wrote:
> On 20/12/2023 12:18 am, John Stultz wrote:
> > +int crazy_fan_thread(void *)
> > +{
> > + int count = 0;
> > +
> > + atomic_inc(&players_ready);
> > + while (!READ_ONCE(game_over)) {
> > + if (kthread_should_stop())
> > + break;
> > + schedule();
> > + udelay(1000);
> > + msleep(2);
> > + count++;
>
> @count is only increased. Is it really necessary?
Nope. Just remnants of earlier debug code.
>
> * Please prepend a prefix to prints to ease capturing the module logs.
Done.
> * I think `rmmod test_sched_football` throws `Device or resource busy`
> error and fails to remove the module because of missing module_exit().
Yep. I'm skipping this for now, but I'll see about adding it later
after I figure out the changes I need to manufacture the problematic
load-balancing condition I'm worried about, as it doesn't seem to
appear on its own so far.
thanks
-john
On 20/12/2023 12:18 am, John Stultz wrote:
> Reimplementation of the sched_football test from LTP:
> https://github.com/linux-test-project/ltp/blob/master/testcases/realtime/func/sched_football/sched_football.c
>
> But reworked to run in the kernel and utilize mutexes
> to illustrate proper boosting of low priority mutex
> holders.
>
> TODO:
> * Need a rt_mutex version so it can work w/o proxy-execution
> * Need a better place to put it
>
> Cc: Joel Fernandes <joelaf@google.com>
> Cc: Qais Yousef <qyousef@google.com>
> Cc: Ingo Molnar <mingo@redhat.com>
> Cc: Peter Zijlstra <peterz@infradead.org>
> Cc: Juri Lelli <juri.lelli@redhat.com>
> Cc: Vincent Guittot <vincent.guittot@linaro.org>
> Cc: Dietmar Eggemann <dietmar.eggemann@arm.com>
> Cc: Valentin Schneider <vschneid@redhat.com>
> Cc: Steven Rostedt <rostedt@goodmis.org>
> Cc: Ben Segall <bsegall@google.com>
> Cc: Zimuzo Ezeozue <zezeozue@google.com>
> Cc: Youssef Esmat <youssefesmat@google.com>
> Cc: Mel Gorman <mgorman@suse.de>
> Cc: Daniel Bristot de Oliveira <bristot@redhat.com>
> Cc: Will Deacon <will@kernel.org>
> Cc: Waiman Long <longman@redhat.com>
> Cc: Boqun Feng <boqun.feng@gmail.com>
> Cc: "Paul E. McKenney" <paulmck@kernel.org>
> Cc: Metin Kaya <Metin.Kaya@arm.com>
> Cc: Xuewen Yan <xuewen.yan94@gmail.com>
> Cc: K Prateek Nayak <kprateek.nayak@amd.com>
> Cc: Thomas Gleixner <tglx@linutronix.de>
> Cc: kernel-team@android.com
> Signed-off-by: John Stultz <jstultz@google.com>
> ---
> kernel/sched/Makefile | 1 +
> kernel/sched/test_sched_football.c | 242 +++++++++++++++++++++++++++++
> lib/Kconfig.debug | 14 ++
> 3 files changed, 257 insertions(+)
> create mode 100644 kernel/sched/test_sched_football.c
>
> diff --git a/kernel/sched/Makefile b/kernel/sched/Makefile
> index 976092b7bd45..2729d565dfd7 100644
> --- a/kernel/sched/Makefile
> +++ b/kernel/sched/Makefile
> @@ -32,3 +32,4 @@ obj-y += core.o
> obj-y += fair.o
> obj-y += build_policy.o
> obj-y += build_utility.o
> +obj-$(CONFIG_SCHED_RT_INVARIENT_TEST) += test_sched_football.o
> diff --git a/kernel/sched/test_sched_football.c b/kernel/sched/test_sched_football.c
> new file mode 100644
> index 000000000000..9742c45c0fe0
> --- /dev/null
> +++ b/kernel/sched/test_sched_football.c
> @@ -0,0 +1,242 @@
> +// SPDX-License-Identifier: GPL-2.0+
> +/*
> + * Module-based test case for RT scheduling invariant
> + *
> + * A reimplementation of my old sched_football test
> + * found in LTP:
> + * https://github.com/linux-test-project/ltp/blob/master/testcases/realtime/func/sched_football/sched_football.c
> + *
> + * Similar to that test, this tries to validate the RT
> + * scheduling invariant, that the across N available cpus, the
> + * top N priority tasks always running.
> + *
> + * This is done via having N offsensive players that are
> + * medium priority, which constantly are trying to increment the
> + * ball_pos counter.
> + *
> + * Blocking this, are N defensive players that are higher
> + * priority which just spin on the cpu, preventing the medium
> + * priroity tasks from running.
> + *
> + * To complicate this, there are also N defensive low priority
> + * tasks. These start first and each aquire one of N mutexes.
> + * The high priority defense tasks will later try to grab the
> + * mutexes and block, opening a window for the offsensive tasks
> + * to run and increment the ball. If priority inheritance or
> + * proxy execution is used, the low priority defense players
> + * should be boosted to the high priority levels, and will
> + * prevent the mid priority offensive tasks from running.
> + *
> + * Copyright © International Business Machines Corp., 2007, 2008
> + * Copyright (C) Google, 2023
> + *
> + * Authors: John Stultz <jstultz@google.com>
> + */
> +
> +#include <linux/kernel.h>
> +#include <linux/module.h>
> +#include <linux/kthread.h>
> +#include <linux/delay.h>
> +#include <linux/sched/rt.h>
> +#include <linux/spinlock.h>
> +#include <linux/mutex.h>
> +#include <linux/rwsem.h>
> +#include <linux/smp.h>
> +#include <linux/slab.h>
> +#include <linux/interrupt.h>
> +#include <linux/sched.h>
> +#include <uapi/linux/sched/types.h>
> +#include <linux/rtmutex.h>
> +
> +atomic_t players_ready;
> +atomic_t ball_pos;
> +int players_per_team;
> +bool game_over;
> +
> +struct mutex *mutex_low_list;
> +struct mutex *mutex_mid_list;
> +
> +static inline
> +struct task_struct *create_fifo_thread(int (*threadfn)(void *data), void *data,
> + char *name, int prio)
> +{
> + struct task_struct *kth;
> + struct sched_attr attr = {
> + .size = sizeof(struct sched_attr),
> + .sched_policy = SCHED_FIFO,
> + .sched_nice = 0,
> + .sched_priority = prio,
> + };
> + int ret;
> +
> + kth = kthread_create(threadfn, data, name);
> + if (IS_ERR(kth)) {
> + pr_warn("%s eerr, kthread_create failed\n", __func__);
> + return kth;
> + }
> + ret = sched_setattr_nocheck(kth, &attr);
> + if (ret) {
> + kthread_stop(kth);
> + pr_warn("%s: failed to set SCHED_FIFO\n", __func__);
> + return ERR_PTR(ret);
> + }
> +
> + wake_up_process(kth);
> + return kth;
> +}
> +
> +int defense_low_thread(void *arg)
> +{
> + long tnum = (long)arg;
> +
> + atomic_inc(&players_ready);
> + mutex_lock(&mutex_low_list[tnum]);
> + while (!READ_ONCE(game_over)) {
> + if (kthread_should_stop())
> + break;
> + schedule();
> + }
> + mutex_unlock(&mutex_low_list[tnum]);
> + return 0;
> +}
> +
> +int defense_mid_thread(void *arg)
> +{
> + long tnum = (long)arg;
> +
> + atomic_inc(&players_ready);
> + mutex_lock(&mutex_mid_list[tnum]);
> + mutex_lock(&mutex_low_list[tnum]);
> + while (!READ_ONCE(game_over)) {
> + if (kthread_should_stop())
> + break;
> + schedule();
> + }
> + mutex_unlock(&mutex_low_list[tnum]);
> + mutex_unlock(&mutex_mid_list[tnum]);
> + return 0;
> +}
> +
> +int offense_thread(void *)
> +{
> + atomic_inc(&players_ready);
> + while (!READ_ONCE(game_over)) {
> + if (kthread_should_stop())
> + break;
> + schedule();
> + atomic_inc(&ball_pos);
> + }
> + return 0;
> +}
> +
> +int defense_hi_thread(void *arg)
> +{
> + long tnum = (long)arg;
> +
> + atomic_inc(&players_ready);
> + mutex_lock(&mutex_mid_list[tnum]);
> + while (!READ_ONCE(game_over)) {
> + if (kthread_should_stop())
> + break;
> + schedule();
> + }
> + mutex_unlock(&mutex_mid_list[tnum]);
> + return 0;
> +}
> +
> +int crazy_fan_thread(void *)
> +{
> + int count = 0;
> +
> + atomic_inc(&players_ready);
> + while (!READ_ONCE(game_over)) {
> + if (kthread_should_stop())
> + break;
> + schedule();
> + udelay(1000);
> + msleep(2);
> + count++;
> + }
> + return 0;
> +}
> +
> +int ref_thread(void *arg)
> +{
> + struct task_struct *kth;
> + long game_time = (long)arg;
> + unsigned long final_pos;
> + long i;
> +
> + pr_info("%s: started ref, game_time: %ld secs !\n", __func__,
> + game_time);
> +
> + /* Create low priority defensive team */
> + for (i = 0; i < players_per_team; i++)
> + kth = create_fifo_thread(defense_low_thread, (void *)i,
> + "defese-low-thread", 2);
> + /* Wait for the defense threads to start */
> + while (atomic_read(&players_ready) < players_per_team)
> + msleep(1);
> +
> + for (i = 0; i < players_per_team; i++)
> + kth = create_fifo_thread(defense_mid_thread,
> + (void *)(players_per_team - i - 1),
> + "defese-mid-thread", 3);
> + /* Wait for the defense threads to start */
> + while (atomic_read(&players_ready) < players_per_team * 2)
> + msleep(1);
> +
> + /* Create mid priority offensive team */
> + for (i = 0; i < players_per_team; i++)
> + kth = create_fifo_thread(offense_thread, NULL,
> + "offense-thread", 5);
> + /* Wait for the offense threads to start */
> + while (atomic_read(&players_ready) < players_per_team * 3)
> + msleep(1);
> +
> + /* Create high priority defensive team */
> + for (i = 0; i < players_per_team; i++)
> + kth = create_fifo_thread(defense_hi_thread, (void *)i,
> + "defese-hi-thread", 10);
> + /* Wait for the defense threads to start */
> + while (atomic_read(&players_ready) < players_per_team * 4)
> + msleep(1);
> +
> + /* Create high priority defensive team */
> + for (i = 0; i < players_per_team; i++)
> + kth = create_fifo_thread(crazy_fan_thread, NULL,
> + "crazy-fan-thread", 15);
> + /* Wait for the defense threads to start */
> + while (atomic_read(&players_ready) < players_per_team * 5)
> + msleep(1);
> +
> + pr_info("%s: all players checked in! Starting game.\n", __func__);
> + atomic_set(&ball_pos, 0);
> + msleep(game_time * 1000);
> + final_pos = atomic_read(&ball_pos);
> + pr_info("%s: final ball_pos: %ld\n", __func__, final_pos);
> + WARN_ON(final_pos != 0);
> + game_over = true;
> + return 0;
> +}
> +
> +static int __init test_sched_football_init(void)
> +{
> + struct task_struct *kth;
> + int i;
> +
> + players_per_team = num_online_cpus();
> +
> + mutex_low_list = kmalloc_array(players_per_team, sizeof(struct mutex), GFP_ATOMIC);
> + mutex_mid_list = kmalloc_array(players_per_team, sizeof(struct mutex), GFP_ATOMIC);
> +
> + for (i = 0; i < players_per_team; i++) {
> + mutex_init(&mutex_low_list[i]);
> + mutex_init(&mutex_mid_list[i]);
> + }
> +
> + kth = create_fifo_thread(ref_thread, (void *)10, "ref-thread", 20);
> +
> + return 0;
> +}
> +module_init(test_sched_football_init);
Hit `modpost: missing MODULE_LICENSE() in
kernel/sched/test_sched_football.o` error when I build this module.
JFYI: the module does not have MODULE_NAME(), MODULE_DESCRIPTION(),
MODULE_AUTHOR(), module_exit(), ... as well.
> diff --git a/lib/Kconfig.debug b/lib/Kconfig.debug
> index 4405f81248fb..1d90059d190f 100644
> --- a/lib/Kconfig.debug
> +++ b/lib/Kconfig.debug
> @@ -1238,6 +1238,20 @@ config SCHED_DEBUG
> that can help debug the scheduler. The runtime overhead of this
> option is minimal.
>
> +config SCHED_RT_INVARIENT_TEST
> + tristate "RT invarient scheduling tester"
> + depends on DEBUG_KERNEL
> + help
> + This option provides a kernel module that runs tests to make
> + sure the RT invarient holds (top N priority tasks run on N
> + available cpus).
> +
> + Say Y here if you want kernel rt scheduling tests
> + to be built into the kernel.
> + Say M if you want this test to build as a module.
> + Say N if you are unsure.
> +
> +
> config SCHED_INFO
> bool
> default n
On Thu, Dec 28, 2023 at 7:19 AM Metin Kaya <metin.kaya@arm.com> wrote:
> On 20/12/2023 12:18 am, John Stultz wrote:
> > +static int __init test_sched_football_init(void)
> > +{
> > + struct task_struct *kth;
> > + int i;
> > +
> > + players_per_team = num_online_cpus();
> > +
> > + mutex_low_list = kmalloc_array(players_per_team, sizeof(struct mutex), GFP_ATOMIC);
> > + mutex_mid_list = kmalloc_array(players_per_team, sizeof(struct mutex), GFP_ATOMIC);
> > +
> > + for (i = 0; i < players_per_team; i++) {
> > + mutex_init(&mutex_low_list[i]);
> > + mutex_init(&mutex_mid_list[i]);
> > + }
> > +
> > + kth = create_fifo_thread(ref_thread, (void *)10, "ref-thread", 20);
> > +
> > + return 0;
> > +}
> > +module_init(test_sched_football_init);
>
> Hit `modpost: missing MODULE_LICENSE() in
> kernel/sched/test_sched_football.o` error when I build this module.
>
> JFYI: the module does not have MODULE_NAME(), MODULE_DESCRIPTION(),
> MODULE_AUTHOR(), module_exit(), ... as well.
Good point. I've only been using it as a built-in.
Added all of those except for module_exit() for now, as I don't want
it to be unloaded while the kthreads are running.
thanks
-john
On 20/12/2023 12:18 am, John Stultz wrote:
> Reimplementation of the sched_football test from LTP:
> https://github.com/linux-test-project/ltp/blob/master/testcases/realtime/func/sched_football/sched_football.c
>
> But reworked to run in the kernel and utilize mutexes
> to illustrate proper boosting of low priority mutex
> holders.
>
> TODO:
> * Need a rt_mutex version so it can work w/o proxy-execution
> * Need a better place to put it
I think also this patch can be upstreamed regardless of other Proxy
Execution patches, right?
>
> Cc: Joel Fernandes <joelaf@google.com>
> Cc: Qais Yousef <qyousef@google.com>
> Cc: Ingo Molnar <mingo@redhat.com>
> Cc: Peter Zijlstra <peterz@infradead.org>
> Cc: Juri Lelli <juri.lelli@redhat.com>
> Cc: Vincent Guittot <vincent.guittot@linaro.org>
> Cc: Dietmar Eggemann <dietmar.eggemann@arm.com>
> Cc: Valentin Schneider <vschneid@redhat.com>
> Cc: Steven Rostedt <rostedt@goodmis.org>
> Cc: Ben Segall <bsegall@google.com>
> Cc: Zimuzo Ezeozue <zezeozue@google.com>
> Cc: Youssef Esmat <youssefesmat@google.com>
> Cc: Mel Gorman <mgorman@suse.de>
> Cc: Daniel Bristot de Oliveira <bristot@redhat.com>
> Cc: Will Deacon <will@kernel.org>
> Cc: Waiman Long <longman@redhat.com>
> Cc: Boqun Feng <boqun.feng@gmail.com>
> Cc: "Paul E. McKenney" <paulmck@kernel.org>
> Cc: Metin Kaya <Metin.Kaya@arm.com>
> Cc: Xuewen Yan <xuewen.yan94@gmail.com>
> Cc: K Prateek Nayak <kprateek.nayak@amd.com>
> Cc: Thomas Gleixner <tglx@linutronix.de>
> Cc: kernel-team@android.com
> Signed-off-by: John Stultz <jstultz@google.com>
> ---
> kernel/sched/Makefile | 1 +
> kernel/sched/test_sched_football.c | 242 +++++++++++++++++++++++++++++
> lib/Kconfig.debug | 14 ++
> 3 files changed, 257 insertions(+)
> create mode 100644 kernel/sched/test_sched_football.c
>
> diff --git a/kernel/sched/Makefile b/kernel/sched/Makefile
> index 976092b7bd45..2729d565dfd7 100644
> --- a/kernel/sched/Makefile
> +++ b/kernel/sched/Makefile
> @@ -32,3 +32,4 @@ obj-y += core.o
> obj-y += fair.o
> obj-y += build_policy.o
> obj-y += build_utility.o
> +obj-$(CONFIG_SCHED_RT_INVARIENT_TEST) += test_sched_football.o
> diff --git a/kernel/sched/test_sched_football.c b/kernel/sched/test_sched_football.c
> new file mode 100644
> index 000000000000..9742c45c0fe0
> --- /dev/null
> +++ b/kernel/sched/test_sched_football.c
> @@ -0,0 +1,242 @@
> +// SPDX-License-Identifier: GPL-2.0+
> +/*
> + * Module-based test case for RT scheduling invariant
> + *
> + * A reimplementation of my old sched_football test
> + * found in LTP:
> + * https://github.com/linux-test-project/ltp/blob/master/testcases/realtime/func/sched_football/sched_football.c
> + *
> + * Similar to that test, this tries to validate the RT
> + * scheduling invariant, that the across N available cpus, the
> + * top N priority tasks always running.
> + *
> + * This is done via having N offsensive players that are
offensive
> + * medium priority, which constantly are trying to increment the
> + * ball_pos counter.
> + *
> + * Blocking this, are N defensive players that are higher
> + * priority which just spin on the cpu, preventing the medium
> + * priroity tasks from running.
priority
> + *
> + * To complicate this, there are also N defensive low priority
> + * tasks. These start first and each aquire one of N mutexes.
> + * The high priority defense tasks will later try to grab the
> + * mutexes and block, opening a window for the offsensive tasks
> + * to run and increment the ball. If priority inheritance or
> + * proxy execution is used, the low priority defense players
> + * should be boosted to the high priority levels, and will
> + * prevent the mid priority offensive tasks from running.
> + *
> + * Copyright © International Business Machines Corp., 2007, 2008
> + * Copyright (C) Google, 2023
> + *
> + * Authors: John Stultz <jstultz@google.com>
> + */
> +
> +#include <linux/kernel.h>
> +#include <linux/module.h>
> +#include <linux/kthread.h>
> +#include <linux/delay.h>
> +#include <linux/sched/rt.h>
> +#include <linux/spinlock.h>
> +#include <linux/mutex.h>
> +#include <linux/rwsem.h>
> +#include <linux/smp.h>
> +#include <linux/slab.h>
> +#include <linux/interrupt.h>
> +#include <linux/sched.h>
> +#include <uapi/linux/sched/types.h>
> +#include <linux/rtmutex.h>
> +
> +atomic_t players_ready;
> +atomic_t ball_pos;
> +int players_per_team;
Nit: Number of players cannot be lower than 0. Should it be unsigned then?
> +bool game_over;
> +
> +struct mutex *mutex_low_list;
> +struct mutex *mutex_mid_list;
> +
> +static inline
> +struct task_struct *create_fifo_thread(int (*threadfn)(void *data), void *data,
> + char *name, int prio)
> +{
> + struct task_struct *kth;
> + struct sched_attr attr = {
> + .size = sizeof(struct sched_attr),
> + .sched_policy = SCHED_FIFO,
> + .sched_nice = 0,
> + .sched_priority = prio,
> + };
> + int ret;
> +
> + kth = kthread_create(threadfn, data, name);
> + if (IS_ERR(kth)) {
> + pr_warn("%s eerr, kthread_create failed\n", __func__);
Extra e at eerr?
> + return kth;
> + }
> + ret = sched_setattr_nocheck(kth, &attr);
> + if (ret) {
> + kthread_stop(kth);
> + pr_warn("%s: failed to set SCHED_FIFO\n", __func__);
> + return ERR_PTR(ret);
> + }
> +
> + wake_up_process(kth);
> + return kth;
I think the result of this function is actually unused. So,
create_fifo_thread()'s return type can be void?
> +}
> +
> +int defense_low_thread(void *arg)
> +{
> + long tnum = (long)arg;
> +
> + atomic_inc(&players_ready);
> + mutex_lock(&mutex_low_list[tnum]);
> + while (!READ_ONCE(game_over)) {
> + if (kthread_should_stop())
> + break;
> + schedule();
> + }
> + mutex_unlock(&mutex_low_list[tnum]);
> + return 0;
> +}
> +
> +int defense_mid_thread(void *arg)
> +{
> + long tnum = (long)arg;
> +
> + atomic_inc(&players_ready);
> + mutex_lock(&mutex_mid_list[tnum]);
> + mutex_lock(&mutex_low_list[tnum]);
> + while (!READ_ONCE(game_over)) {
> + if (kthread_should_stop())
> + break;
> + schedule();
> + }
> + mutex_unlock(&mutex_low_list[tnum]);
> + mutex_unlock(&mutex_mid_list[tnum]);
> + return 0;
> +}
> +
> +int offense_thread(void *)
Does this (no param name) build fine on Android env?
> +{
> + atomic_inc(&players_ready);
> + while (!READ_ONCE(game_over)) {
> + if (kthread_should_stop())
> + break;
> + schedule();
> + atomic_inc(&ball_pos);
> + }
> + return 0;
> +}
> +
> +int defense_hi_thread(void *arg)
> +{
> + long tnum = (long)arg;
> +
> + atomic_inc(&players_ready);
> + mutex_lock(&mutex_mid_list[tnum]);
> + while (!READ_ONCE(game_over)) {
> + if (kthread_should_stop())
> + break;
> + schedule();
> + }
> + mutex_unlock(&mutex_mid_list[tnum]);
> + return 0;
> +}
> +
> +int crazy_fan_thread(void *)
Same (no param name) question here.
> +{
> + int count = 0;
> +
> + atomic_inc(&players_ready);
> + while (!READ_ONCE(game_over)) {
> + if (kthread_should_stop())
> + break;
> + schedule();
> + udelay(1000);
> + msleep(2);
> + count++;
> + }
> + return 0;
> +}
> +
> +int ref_thread(void *arg)
> +{
> + struct task_struct *kth;
> + long game_time = (long)arg;
> + unsigned long final_pos;
> + long i;
> +
> + pr_info("%s: started ref, game_time: %ld secs !\n", __func__,
> + game_time);
> +
> + /* Create low priority defensive team */
Sorry: extra space after `low`.
> + for (i = 0; i < players_per_team; i++)
> + kth = create_fifo_thread(defense_low_thread, (void *)i,
> + "defese-low-thread", 2);
> + /* Wait for the defense threads to start */
> + while (atomic_read(&players_ready) < players_per_team)
> + msleep(1);
> +
> + for (i = 0; i < players_per_team; i++)
> + kth = create_fifo_thread(defense_mid_thread,
> + (void *)(players_per_team - i - 1),
> + "defese-mid-thread", 3);
> + /* Wait for the defense threads to start */
> + while (atomic_read(&players_ready) < players_per_team * 2)
> + msleep(1);
> +
> + /* Create mid priority offensive team */
> + for (i = 0; i < players_per_team; i++)
> + kth = create_fifo_thread(offense_thread, NULL,
> + "offense-thread", 5);
> + /* Wait for the offense threads to start */
> + while (atomic_read(&players_ready) < players_per_team * 3)
> + msleep(1);
> +
> + /* Create high priority defensive team */
> + for (i = 0; i < players_per_team; i++)
> + kth = create_fifo_thread(defense_hi_thread, (void *)i,
> + "defese-hi-thread", 10);
> + /* Wait for the defense threads to start */
> + while (atomic_read(&players_ready) < players_per_team * 4)
> + msleep(1);
> +
> + /* Create high priority defensive team */
> + for (i = 0; i < players_per_team; i++)
> + kth = create_fifo_thread(crazy_fan_thread, NULL,
> + "crazy-fan-thread", 15);
> + /* Wait for the defense threads to start */
> + while (atomic_read(&players_ready) < players_per_team * 5)
> + msleep(1);
> +
> + pr_info("%s: all players checked in! Starting game.\n", __func__);
> + atomic_set(&ball_pos, 0);
> + msleep(game_time * 1000);
> + final_pos = atomic_read(&ball_pos);
> + pr_info("%s: final ball_pos: %ld\n", __func__, final_pos);
> + WARN_ON(final_pos != 0);
> + game_over = true;
> + return 0;
> +}
> +
> +static int __init test_sched_football_init(void)
> +{
> + struct task_struct *kth;
> + int i;
> +
> + players_per_team = num_online_cpus();
> +
> + mutex_low_list = kmalloc_array(players_per_team, sizeof(struct mutex), GFP_ATOMIC);
> + mutex_mid_list = kmalloc_array(players_per_team, sizeof(struct mutex), GFP_ATOMIC);
* Extra space after `players_per_team,`.
* Shouldn't we check result of `kmalloc_array()`?
Same comments for `mutex_low_list` (previous) line.
> +
> + for (i = 0; i < players_per_team; i++) {
> + mutex_init(&mutex_low_list[i]);
> + mutex_init(&mutex_mid_list[i]);
> + }
> +
> + kth = create_fifo_thread(ref_thread, (void *)10, "ref-thread", 20);
> +
> + return 0;
> +}
> +module_init(test_sched_football_init);
> diff --git a/lib/Kconfig.debug b/lib/Kconfig.debug
> index 4405f81248fb..1d90059d190f 100644
> --- a/lib/Kconfig.debug
> +++ b/lib/Kconfig.debug
> @@ -1238,6 +1238,20 @@ config SCHED_DEBUG
> that can help debug the scheduler. The runtime overhead of this
> option is minimal.
>
> +config SCHED_RT_INVARIENT_TEST
> + tristate "RT invarient scheduling tester"
> + depends on DEBUG_KERNEL
> + help
> + This option provides a kernel module that runs tests to make
> + sure the RT invarient holds (top N priority tasks run on N
> + available cpus).
> +
> + Say Y here if you want kernel rt scheduling tests
> + to be built into the kernel.
> + Say M if you want this test to build as a module.
> + Say N if you are unsure.
> +
> +
> config SCHED_INFO
> bool
> default n
On Fri, Dec 22, 2023 at 1:32 AM Metin Kaya <metin.kaya@arm.com> wrote:
>
> On 20/12/2023 12:18 am, John Stultz wrote:
> > Reimplementation of the sched_football test from LTP:
> > https://github.com/linux-test-project/ltp/blob/master/testcases/realtime/func/sched_football/sched_football.c
> >
> > But reworked to run in the kernel and utilize mutexes
> > to illustrate proper boosting of low priority mutex
> > holders.
> >
> > TODO:
> > * Need a rt_mutex version so it can work w/o proxy-execution
> > * Need a better place to put it
>
> I think also this patch can be upstreamed regardless of other Proxy
> Execution patches, right?
Well, we would need to use rt_mutexes for the !PROXY case to validate
inheritance.
But something like it could be included before PROXY lands.
> > + *
> > + * This is done via having N offsensive players that are
>
> offensive
Fixed.
> > + * medium priority, which constantly are trying to increment the
> > + * ball_pos counter.
> > + *
> > + * Blocking this, are N defensive players that are higher
> > + * priority which just spin on the cpu, preventing the medium
> > + * priroity tasks from running.
>
> priority
Fixed.
> > +atomic_t players_ready;
> > +atomic_t ball_pos;
> > +int players_per_team;
>
> Nit: Number of players cannot be lower than 0. Should it be unsigned then?
Fixed.
> > +bool game_over;
> > +
> > +struct mutex *mutex_low_list;
> > +struct mutex *mutex_mid_list;
> > +
> > +static inline
> > +struct task_struct *create_fifo_thread(int (*threadfn)(void *data), void *data,
> > + char *name, int prio)
> > +{
> > + struct task_struct *kth;
> > + struct sched_attr attr = {
> > + .size = sizeof(struct sched_attr),
> > + .sched_policy = SCHED_FIFO,
> > + .sched_nice = 0,
> > + .sched_priority = prio,
> > + };
> > + int ret;
> > +
> > + kth = kthread_create(threadfn, data, name);
> > + if (IS_ERR(kth)) {
> > + pr_warn("%s eerr, kthread_create failed\n", __func__);
>
> Extra e at eerr?
Fixed.
> > + return kth;
> > + }
> > + ret = sched_setattr_nocheck(kth, &attr);
> > + if (ret) {
> > + kthread_stop(kth);
> > + pr_warn("%s: failed to set SCHED_FIFO\n", __func__);
> > + return ERR_PTR(ret);
> > + }
> > +
> > + wake_up_process(kth);
> > + return kth;
>
> I think the result of this function is actually unused. So,
> create_fifo_thread()'s return type can be void?
It's not used, but it probably should be. At least I should be
checking for the failure cases. I'll rework to fix this.
> > +
> > +int offense_thread(void *)
>
> Does this (no param name) build fine on Android env?
Good point, I've only been testing this bit with qemu. I'll fix it up.
> > +int ref_thread(void *arg)
> > +{
> > + struct task_struct *kth;
> > + long game_time = (long)arg;
> > + unsigned long final_pos;
> > + long i;
> > +
> > + pr_info("%s: started ref, game_time: %ld secs !\n", __func__,
> > + game_time);
> > +
> > + /* Create low priority defensive team */
>
> Sorry: extra space after `low`.
Fixed.
> > + mutex_low_list = kmalloc_array(players_per_team, sizeof(struct mutex), GFP_ATOMIC);
> > + mutex_mid_list = kmalloc_array(players_per_team, sizeof(struct mutex), GFP_ATOMIC);
>
> * Extra space after `players_per_team,`.
> * Shouldn't we check result of `kmalloc_array()`?
>
> Same comments for `mutex_low_list` (previous) line.
Yep.
Thanks for all the suggestions!
-john
Hi John,
On 12/19/23 16:18, John Stultz wrote:
> Reimplementation of the sched_football test from LTP:
> https://github.com/linux-test-project/ltp/blob/master/testcases/realtime/func/sched_football/sched_football.c
>
> But reworked to run in the kernel and utilize mutexes
> to illustrate proper boosting of low priority mutex
> holders.
>
> TODO:
> * Need a rt_mutex version so it can work w/o proxy-execution
> * Need a better place to put it
>
> Cc: kernel-team@android.com
> Signed-off-by: John Stultz <jstultz@google.com>
> ---
> kernel/sched/Makefile | 1 +
> kernel/sched/test_sched_football.c | 242 +++++++++++++++++++++++++++++
> lib/Kconfig.debug | 14 ++
> 3 files changed, 257 insertions(+)
> create mode 100644 kernel/sched/test_sched_football.c
>
> diff --git a/kernel/sched/test_sched_football.c b/kernel/sched/test_sched_football.c
> new file mode 100644
> index 000000000000..9742c45c0fe0
> --- /dev/null
> +++ b/kernel/sched/test_sched_football.c
> @@ -0,0 +1,242 @@
> +// SPDX-License-Identifier: GPL-2.0+
> +/*
> + * Module-based test case for RT scheduling invariant
> + *
> + * A reimplementation of my old sched_football test
> + * found in LTP:
> + * https://github.com/linux-test-project/ltp/blob/master/testcases/realtime/func/sched_football/sched_football.c
> + *
> + * Similar to that test, this tries to validate the RT
> + * scheduling invariant, that the across N available cpus, the
> + * top N priority tasks always running.
> + *
> + * This is done via having N offsensive players that are
> + * medium priority, which constantly are trying to increment the
> + * ball_pos counter.
> + *
> + * Blocking this, are N defensive players that are higher
no comma ^
> + * priority which just spin on the cpu, preventing the medium
> + * priroity tasks from running.
> + *
> + * To complicate this, there are also N defensive low priority
> + * tasks. These start first and each aquire one of N mutexes.
acquire
> + * The high priority defense tasks will later try to grab the
> + * mutexes and block, opening a window for the offsensive tasks
offensive
> + * to run and increment the ball. If priority inheritance or
> + * proxy execution is used, the low priority defense players
> + * should be boosted to the high priority levels, and will
> + * prevent the mid priority offensive tasks from running.
> + *
> + * Copyright © International Business Machines Corp., 2007, 2008
> + * Copyright (C) Google, 2023
> + *
> + * Authors: John Stultz <jstultz@google.com>
> + */
> +
> +#include <linux/kernel.h>
> +#include <linux/module.h>
> +#include <linux/kthread.h>
> +#include <linux/delay.h>
> +#include <linux/sched/rt.h>
> +#include <linux/spinlock.h>
> +#include <linux/mutex.h>
> +#include <linux/rwsem.h>
> +#include <linux/smp.h>
> +#include <linux/slab.h>
> +#include <linux/interrupt.h>
> +#include <linux/sched.h>
> +#include <uapi/linux/sched/types.h>
> +#include <linux/rtmutex.h>
> +
> +atomic_t players_ready;
> +atomic_t ball_pos;
> +int players_per_team;
> +bool game_over;
> +
> +struct mutex *mutex_low_list;
> +struct mutex *mutex_mid_list;
> +
[]
Is this the referee?
> +int ref_thread(void *arg)
> +{
> + struct task_struct *kth;
> + long game_time = (long)arg;
> + unsigned long final_pos;
> + long i;
> +
> + pr_info("%s: started ref, game_time: %ld secs !\n", __func__,
> + game_time);
> +
> + /* Create low priority defensive team */
> + for (i = 0; i < players_per_team; i++)
> + kth = create_fifo_thread(defense_low_thread, (void *)i,
> + "defese-low-thread", 2);
defense
> + /* Wait for the defense threads to start */
> + while (atomic_read(&players_ready) < players_per_team)
> + msleep(1);
> +
> + for (i = 0; i < players_per_team; i++)
> + kth = create_fifo_thread(defense_mid_thread,
> + (void *)(players_per_team - i - 1),
> + "defese-mid-thread", 3);
ditto
> + /* Wait for the defense threads to start */
> + while (atomic_read(&players_ready) < players_per_team * 2)
> + msleep(1);
> +
> + /* Create mid priority offensive team */
> + for (i = 0; i < players_per_team; i++)
> + kth = create_fifo_thread(offense_thread, NULL,
> + "offense-thread", 5);
> + /* Wait for the offense threads to start */
> + while (atomic_read(&players_ready) < players_per_team * 3)
> + msleep(1);
> +
> + /* Create high priority defensive team */
> + for (i = 0; i < players_per_team; i++)
> + kth = create_fifo_thread(defense_hi_thread, (void *)i,
> + "defese-hi-thread", 10);
ditto
> + /* Wait for the defense threads to start */
> + while (atomic_read(&players_ready) < players_per_team * 4)
> + msleep(1);
> +
> + /* Create high priority defensive team */
> + for (i = 0; i < players_per_team; i++)
> + kth = create_fifo_thread(crazy_fan_thread, NULL,
> + "crazy-fan-thread", 15);
> + /* Wait for the defense threads to start */
> + while (atomic_read(&players_ready) < players_per_team * 5)
> + msleep(1);
> +
> + pr_info("%s: all players checked in! Starting game.\n", __func__);
> + atomic_set(&ball_pos, 0);
> + msleep(game_time * 1000);
> + final_pos = atomic_read(&ball_pos);
> + pr_info("%s: final ball_pos: %ld\n", __func__, final_pos);
> + WARN_ON(final_pos != 0);
> + game_over = true;
> + return 0;
> +}
> +
> diff --git a/lib/Kconfig.debug b/lib/Kconfig.debug
> index 4405f81248fb..1d90059d190f 100644
> --- a/lib/Kconfig.debug
> +++ b/lib/Kconfig.debug
> @@ -1238,6 +1238,20 @@ config SCHED_DEBUG
> that can help debug the scheduler. The runtime overhead of this
> option is minimal.
>
> +config SCHED_RT_INVARIENT_TEST
INVARIANT
> + tristate "RT invarient scheduling tester"
invariant
> + depends on DEBUG_KERNEL
> + help
> + This option provides a kernel module that runs tests to make
> + sure the RT invarient holds (top N priority tasks run on N
invariant
> + available cpus).
> +
> + Say Y here if you want kernel rt scheduling tests
RT
> + to be built into the kernel.
> + Say M if you want this test to build as a module.
> + Say N if you are unsure.
> +
> +
> config SCHED_INFO
> bool
> default n
--
#Randy
https://people.kernel.org/tglx/notes-about-netiquette
https://subspace.kernel.org/etiquette.html
On Tue, Dec 19, 2023 at 4:59 PM Randy Dunlap <rdunlap@infradead.org> wrote: > On 12/19/23 16:18, John Stultz wrote: > [] > > Is this the referee? Yea, good point. "ref" is an overloaded shorthand. Will fix. Thanks also for all the spelling corrections! Much appreciated. -john
© 2016 - 2025 Red Hat, Inc.