Received: by 2002:a05:7412:d008:b0:f9:6acb:47ec with SMTP id bd8csp261862rdb; Tue, 19 Dec 2023 16:24:40 -0800 (PST) X-Google-Smtp-Source: AGHT+IGLhy6OZLsdE2oAQV3sMeEOWymTTTiojxsKza3o2kpgBZlf9AMVOZ2Z0J5TTX3+/O5ozjfm X-Received: by 2002:a05:6830:917:b0:6da:32cd:893d with SMTP id v23-20020a056830091700b006da32cd893dmr16592076ott.50.1703031879908; Tue, 19 Dec 2023 16:24:39 -0800 (PST) ARC-Seal: i=1; a=rsa-sha256; t=1703031879; cv=none; d=google.com; s=arc-20160816; b=TPJvuI2NjYy+bpSMWmEgT0uDcY1kqf0kuCuGmx2pI7JUK3h8APE1gpDLkuIdC/L/Ab LLrt2Lclf3ArqFn22/s8aHi7Ewyhjpkj20zsSXynMGBuQghldde+Wduh+7a3RAXHGLJr UTHRhXAqzi02lp5JmK1fIlA1F+ZjYqSyRf8TN5qS2IopVKspcviIk6Em7b32ktHA1d4K K8NqO1Tsi1WrI7mxVHT4LV5yawxfa/RcZhHwCUTDD6GpbI8d/6pTZ2nKAalmG5kXdwUE abcegRzMCtCCJDVdrcPiFlJYSKT7CUGoD6fETj+d7970dCyvjViK0J1umZPWux27qEqC fJ0w== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=content-transfer-encoding:cc:to:from:subject:message-id:references :mime-version:list-unsubscribe:list-subscribe:list-id:precedence :in-reply-to:date:dkim-signature; bh=AIfyyqU8vvkBxzT4xph+dm2KvcH+GhhY/2ZmCVqXntI=; fh=lq1k4m46TqOToIb7rHC/F2KmHTJTjmaV9sS3Am9W7nA=; b=0eGig8GVr2RhdHF67bwiQiOS+ZLYT1ug6Iz1x9Ebgi9BpoA+AqRbbB3S2Bmqkymt/F X7jvuPEutzZfOisCYYBfLxh4xPXm+RgC+X2rTPQ19VnxIgJCCUQENIgxhQC/U6CNZ6Jk dLC9iVtGRW5rZx9tPNRskGDv+4NG94BTTi/YRjDhWiGy25Xp6Xt7eC4aigACocOCvLrd fCR6hwVJnEPNSoIX4/ADnORxxINKlI1C9kK6rODlwcaob2TeFeK7uDXBLcZMd+pip+2h NtJZahY5A0G/1BBHsFNy0lg1YruXZbhz3Ao6ncoMsD7Ga1gZu17bz9EW5PZ4N+0ty8ir UZ9w== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@google.com header.s=20230601 header.b=umVrC99g; spf=pass (google.com: domain of linux-kernel+bounces-6153-linux.lists.archive=gmail.com@vger.kernel.org designates 2604:1380:40f1:3f00::1 as permitted sender) smtp.mailfrom="linux-kernel+bounces-6153-linux.lists.archive=gmail.com@vger.kernel.org"; dmarc=pass (p=REJECT sp=REJECT dis=NONE) header.from=google.com Return-Path: Received: from sy.mirrors.kernel.org (sy.mirrors.kernel.org. [2604:1380:40f1:3f00::1]) by mx.google.com with ESMTPS id n31-20020a056a000d5f00b006ce010d03d3si2914245pfv.303.2023.12.19.16.24.39 for (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 19 Dec 2023 16:24:39 -0800 (PST) Received-SPF: pass (google.com: domain of linux-kernel+bounces-6153-linux.lists.archive=gmail.com@vger.kernel.org designates 2604:1380:40f1:3f00::1 as permitted sender) client-ip=2604:1380:40f1:3f00::1; Authentication-Results: mx.google.com; dkim=pass header.i=@google.com header.s=20230601 header.b=umVrC99g; spf=pass (google.com: domain of linux-kernel+bounces-6153-linux.lists.archive=gmail.com@vger.kernel.org designates 2604:1380:40f1:3f00::1 as permitted sender) smtp.mailfrom="linux-kernel+bounces-6153-linux.lists.archive=gmail.com@vger.kernel.org"; dmarc=pass (p=REJECT sp=REJECT dis=NONE) header.from=google.com Received: from smtp.subspace.kernel.org (wormhole.subspace.kernel.org [52.25.139.140]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by sy.mirrors.kernel.org (Postfix) with ESMTPS id 4C3C2B24AD3 for ; Wed, 20 Dec 2023 00:23:52 +0000 (UTC) Received: from localhost.localdomain (localhost.localdomain [127.0.0.1]) by smtp.subspace.kernel.org (Postfix) with ESMTP id 54F8D20B29; Wed, 20 Dec 2023 00:19:37 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=google.com header.i=@google.com header.b="umVrC99g" X-Original-To: linux-kernel@vger.kernel.org Received: from mail-yw1-f201.google.com (mail-yw1-f201.google.com [209.85.128.201]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 95372200D5 for ; Wed, 20 Dec 2023 00:19:33 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=reject dis=none) header.from=google.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=flex--jstultz.bounces.google.com Received: by mail-yw1-f201.google.com with SMTP id 00721157ae682-5e73bd9079eso32578577b3.2 for ; Tue, 19 Dec 2023 16:19:33 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20230601; t=1703031572; x=1703636372; darn=vger.kernel.org; h=content-transfer-encoding:cc:to:from:subject:message-id:references :mime-version:in-reply-to:date:from:to:cc:subject:date:message-id :reply-to; bh=AIfyyqU8vvkBxzT4xph+dm2KvcH+GhhY/2ZmCVqXntI=; b=umVrC99gRoJhtjuT9Sr4qw/c6e1DLGzxutQKK5qOnxrXllsSXpXpOoA2UTVmAlqguj gyaNfHIrmyHWLONVtHRsNQKDJXulTbLVt7RHDCv3YSY+OgPu+4UeGXXM5alTZtsYp5xC WkuxSh6Vl6D+IkGLzG1m1yTHKs0AoEyQR94zrvJFIShEXdQ08bWpQg/wMQP87Ngru5vt QPJ/dGfucl8QV+1ThB4XHceWwhAUZ+CSHtQpJ7mbGCaw939xvSQ4/n2lWSxxNKzfXKgI ZL6HxUnRDsLOK2H4ur0IuUwjR2YVtL5UXCyOz7k+Vry/ZUzmF0DtZMp+oCtBV2DhMIEx DBDQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1703031572; x=1703636372; h=content-transfer-encoding:cc:to:from:subject:message-id:references :mime-version:in-reply-to:date:x-gm-message-state:from:to:cc:subject :date:message-id:reply-to; bh=AIfyyqU8vvkBxzT4xph+dm2KvcH+GhhY/2ZmCVqXntI=; b=plgU+p4OW9YSJtcZDuFFQzuZJbU/we6lJwaiB9vwQiRoHWlreqsCmAEi/Aa4B57ROC ZNqcBH00rKaPVXKT6BYDjcx5a/yZPe8LoB4Se4gTmm0ns6y19YwKVhFhWlbnLBInGAJq 9MWmStOpAN5oKF67vTmR5hMS7ot0k+ydOw2oGmjqVOFm2onbMonvR2QYlpEW6dHNrW0c hP5UCYhARmKoyQVeodP1CuwGWTchfHx9pffYpwNoBC1aRYJG35tb05sDphUBnqqZSxBu YO/acuXD5ojz9w8XOwcssFzbi7RM8D9INRpY5CDqK4hejCOUVJ+PAEWnIrObzR85P+58 4Fyg== X-Gm-Message-State: AOJu0Yyuw/YWSTKLd9rrxQJUH5+jQdpAVHuVnjaTcLeDpJWDgg1x5nWa uX8aFRF2uPXnF7IGb2nfXrtGV12we56sG/ejQGmFlmcFnhn48/vpcmMAV07ddvSCH5hbAILh95x egTCs1EyzIj7AvNUe0mZog7TrKvsTw/GnDy+SlATtL2RhCRlSaDX/NvsBr0j6mHZ9ptrG9O4= X-Received: from jstultz-noogler2.c.googlers.com ([fda3:e722:ac3:cc00:24:72f4:c0a8:600]) (user=jstultz job=sendgmr) by 2002:a05:690c:4491:b0:5e8:3e57:6900 with SMTP id gr17-20020a05690c449100b005e83e576900mr423186ywb.1.1703031572518; Tue, 19 Dec 2023 16:19:32 -0800 (PST) Date: Tue, 19 Dec 2023 16:18:28 -0800 In-Reply-To: <20231220001856.3710363-1-jstultz@google.com> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: Mime-Version: 1.0 References: <20231220001856.3710363-1-jstultz@google.com> X-Mailer: git-send-email 2.43.0.472.g3155946c3a-goog Message-ID: <20231220001856.3710363-18-jstultz@google.com> Subject: [PATCH v7 17/23] sched: Initial sched_football test implementation From: John Stultz To: LKML Cc: John Stultz , Joel Fernandes , Qais Yousef , Ingo Molnar , Peter Zijlstra , Juri Lelli , Vincent Guittot , Dietmar Eggemann , Valentin Schneider , Steven Rostedt , Ben Segall , Zimuzo Ezeozue , Youssef Esmat , Mel Gorman , Daniel Bristot de Oliveira , Will Deacon , Waiman Long , Boqun Feng , "Paul E. McKenney" , Metin Kaya , Xuewen Yan , K Prateek Nayak , Thomas Gleixner , kernel-team@android.com Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable Reimplementation of the sched_football test from LTP: https://github.com/linux-test-project/ltp/blob/master/testcases/realtime/fu= nc/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 Cc: Qais Yousef Cc: Ingo Molnar Cc: Peter Zijlstra Cc: Juri Lelli Cc: Vincent Guittot Cc: Dietmar Eggemann Cc: Valentin Schneider Cc: Steven Rostedt Cc: Ben Segall Cc: Zimuzo Ezeozue Cc: Youssef Esmat Cc: Mel Gorman Cc: Daniel Bristot de Oliveira Cc: Will Deacon Cc: Waiman Long Cc: Boqun Feng Cc: "Paul E. McKenney" Cc: Metin Kaya Cc: Xuewen Yan Cc: K Prateek Nayak Cc: Thomas Gleixner Cc: kernel-team@android.com Signed-off-by: John Stultz --- 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 +=3D core.o obj-y +=3D fair.o obj-y +=3D build_policy.o obj-y +=3D build_utility.o +obj-$(CONFIG_SCHED_RT_INVARIENT_TEST) +=3D test_sched_football.o diff --git a/kernel/sched/test_sched_football.c b/kernel/sched/test_sched_f= ootball.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/realt= ime/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 =C2=A9 International Business Machines Corp., 2007, 2008 + * Copyright (C) Google, 2023 + * + * Authors: John Stultz + */ + +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include + +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 =3D { + .size =3D sizeof(struct sched_attr), + .sched_policy =3D SCHED_FIFO, + .sched_nice =3D 0, + .sched_priority =3D prio, + }; + int ret; + + kth =3D kthread_create(threadfn, data, name); + if (IS_ERR(kth)) { + pr_warn("%s eerr, kthread_create failed\n", __func__); + return kth; + } + ret =3D 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 =3D (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 =3D (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 =3D (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 =3D 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 =3D (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 =3D 0; i < players_per_team; i++) + kth =3D 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 =3D 0; i < players_per_team; i++) + kth =3D 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 =3D 0; i < players_per_team; i++) + kth =3D 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 =3D 0; i < players_per_team; i++) + kth =3D 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 =3D 0; i < players_per_team; i++) + kth =3D 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 =3D atomic_read(&ball_pos); + pr_info("%s: final ball_pos: %ld\n", __func__, final_pos); + WARN_ON(final_pos !=3D 0); + game_over =3D true; + return 0; +} + +static int __init test_sched_football_init(void) +{ + struct task_struct *kth; + int i; + + players_per_team =3D num_online_cpus(); + + mutex_low_list =3D kmalloc_array(players_per_team, sizeof(struct mutex),= GFP_ATOMIC); + mutex_mid_list =3D kmalloc_array(players_per_team, sizeof(struct mutex),= GFP_ATOMIC); + + for (i =3D 0; i < players_per_team; i++) { + mutex_init(&mutex_low_list[i]); + mutex_init(&mutex_mid_list[i]); + } + + kth =3D 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. =20 +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 --=20 2.43.0.472.g3155946c3a-goog