1 // SPDX-License-Identifier: GPL-2.0+
2 /*
3 * Module-based test case for RT scheduling invariant
4 *
5 * A reimplementation of my old sched_football test
6 * found in LTP:
7 * https://github.com/linux-test-project/ltp/blob/master/testcases/realtime/func/sched_football/sched_football.c
8 *
9 * Similar to that test, this tries to validate the RT
10 * scheduling invariant, that the across N available cpus, the
11 * top N priority tasks always running.
12 *
13 * This is done via having N offensive players that are
14 * medium priority, which constantly are trying to increment the
15 * ball_pos counter.
16 *
17 * Blocking this are N defensive players that are higher
18 * priority which just spin on the cpu, preventing the medium
19 * priority tasks from running.
20 *
21 * To complicate this, there are also N defensive low priority
22 * tasks. These start first and each acquire one of N mutexes.
23 * The high priority defense tasks will later try to grab the
24 * mutexes and block, opening a window for the offensive tasks
25 * to run and increment the ball. If priority inheritance or
26 * proxy execution is used, the low priority defense players
27 * should be boosted to the high priority levels, and will
28 * prevent the mid priority offensive tasks from running.
29 *
30 * Copyright © International Business Machines Corp., 2007, 2008
31 * Copyright (C) Google, 2023, 2024
32 *
33 * Authors: John Stultz <jstultz@google.com>
34 */
35
36 #define MODULE_NAME "ksched_football"
37 #define pr_fmt(fmt) MODULE_NAME ": " fmt
38
39 #include <linux/kernel.h>
40 #include <linux/module.h>
41 #include <linux/kthread.h>
42 #include <linux/delay.h>
43 #include <linux/sched/rt.h>
44 #include <linux/mutex.h>
45 #include <linux/rwsem.h>
46 #include <linux/smp.h>
47 #include <linux/slab.h>
48 #include <uapi/linux/sched/types.h>
49 #include <linux/rtmutex.h>
50
51 MODULE_AUTHOR("John Stultz <jstultz@google.com>");
52 MODULE_DESCRIPTION("Test case for RT scheduling invariant");
53 MODULE_LICENSE("GPL");
54
55 atomic_t players_ready;
56 atomic_t ball_pos;
57 unsigned long players_per_team;
58 bool game_over;
59
60 #define DEF_GAME_TIME 10
61 #define CHECKIN_TIMEOUT 30
62
63 #define REF_PRIO 20
64 #define FAN_PRIO 15
65 #define DEF_HI_PRIO 10
66 #define OFF_PRIO 5
67 #define DEF_MID_PRIO 3
68 #define DEF_LOW_PRIO 2
69
70 #ifdef CONFIG_SCHED_PROXY_EXEC
71 struct mutex *mutex_low_list;
72 struct mutex *mutex_mid_list;
73 #define test_lock_init(x) mutex_init(x)
74 #define TEST_LOCK_SIZE sizeof(struct mutex)
75 #define test_lock(x) mutex_lock(x)
76 #define test_unlock(x) mutex_unlock(x)
77 #else
78 struct rt_mutex *mutex_low_list;
79 struct rt_mutex *mutex_mid_list;
80 #define test_lock_init(x) rt_mutex_init(x)
81 #define TEST_LOCK_SIZE sizeof(struct rt_mutex)
82 #define test_lock(x) rt_mutex_lock(x)
83 #define test_unlock(x) rt_mutex_unlock(x)
84 #endif
85
create_fifo_thread(int (* threadfn)(void * data),void * data,char * name,int prio)86 static struct task_struct *create_fifo_thread(int (*threadfn)(void *data),
87 void *data, char *name, int prio)
88 {
89 struct task_struct *kth;
90 struct sched_attr attr = {
91 .size = sizeof(struct sched_attr),
92 .sched_policy = SCHED_FIFO,
93 .sched_nice = 0,
94 .sched_priority = prio,
95 };
96 int ret;
97
98 kth = kthread_create(threadfn, data, name);
99 if (IS_ERR(kth)) {
100 pr_warn("%s: Error, kthread_create %s failed\n", __func__,
101 name);
102 return kth;
103 }
104 ret = sched_setattr_nocheck(kth, &attr);
105 if (ret) {
106 kthread_stop(kth);
107 pr_warn("%s: Error, failed to set SCHED_FIFO for %s\n",
108 __func__, name);
109 return ERR_PTR(ret);
110 }
111
112 wake_up_process(kth);
113 return kth;
114 }
115
spawn_players(int (* threadfn)(void * data),char * name,int prio)116 static int spawn_players(int (*threadfn)(void *data), char *name, int prio)
117 {
118 unsigned long current_players, start, i;
119 struct task_struct *kth;
120
121 current_players = atomic_read(&players_ready);
122 /* Create players_per_team threads */
123 for (i = 0; i < players_per_team; i++) {
124 kth = create_fifo_thread(threadfn, (void *)i, name, prio);
125 if (IS_ERR(kth))
126 return -1;
127 }
128
129 start = jiffies;
130 /* Wait for players_per_team threads to check in */
131 while (atomic_read(&players_ready) < current_players + players_per_team) {
132 msleep(1);
133 if (jiffies - start > CHECKIN_TIMEOUT * HZ) {
134 pr_err("%s: Error, %s players took too long to checkin "
135 "(only %ld of %ld checked in)\n", __func__, name,
136 (long)atomic_read(&players_ready),
137 current_players + players_per_team);
138 return -1;
139 }
140 }
141 return 0;
142 }
143
defense_low_thread(void * arg)144 static int defense_low_thread(void *arg)
145 {
146 long tnum = (long)arg;
147
148 atomic_inc(&players_ready);
149 test_lock(&mutex_low_list[tnum]);
150 while (!READ_ONCE(game_over)) {
151 if (kthread_should_stop())
152 break;
153 schedule();
154 }
155 test_unlock(&mutex_low_list[tnum]);
156 return 0;
157 }
158
defense_mid_thread(void * arg)159 static int defense_mid_thread(void *arg)
160 {
161 long tnum = (long)arg;
162
163 atomic_inc(&players_ready);
164 test_lock(&mutex_mid_list[tnum]);
165 test_lock(&mutex_low_list[tnum]);
166 while (!READ_ONCE(game_over)) {
167 if (kthread_should_stop())
168 break;
169 schedule();
170 }
171 test_unlock(&mutex_low_list[tnum]);
172 test_unlock(&mutex_mid_list[tnum]);
173 return 0;
174 }
175
offense_thread(void * arg)176 static int offense_thread(void *arg)
177 {
178 atomic_inc(&players_ready);
179 while (!READ_ONCE(game_over)) {
180 if (kthread_should_stop())
181 break;
182 schedule();
183 atomic_inc(&ball_pos);
184 }
185 return 0;
186 }
187
defense_hi_thread(void * arg)188 static int defense_hi_thread(void *arg)
189 {
190 long tnum = (long)arg;
191
192 atomic_inc(&players_ready);
193 test_lock(&mutex_mid_list[tnum]);
194 while (!READ_ONCE(game_over)) {
195 if (kthread_should_stop())
196 break;
197 schedule();
198 }
199 test_unlock(&mutex_mid_list[tnum]);
200 return 0;
201 }
202
crazy_fan_thread(void * arg)203 static int crazy_fan_thread(void *arg)
204 {
205 atomic_inc(&players_ready);
206 while (!READ_ONCE(game_over)) {
207 if (kthread_should_stop())
208 break;
209 schedule();
210 udelay(1000);
211 msleep(2);
212 }
213 return 0;
214 }
215
216 struct completion referee_done;
217
referee_thread(void * arg)218 static int referee_thread(void *arg)
219 {
220 unsigned long game_time = (long)arg;
221 unsigned long final_pos;
222
223 WRITE_ONCE(game_over, false);
224 pr_info("Started referee, game_time: %ld secs !\n", game_time);
225 /* Create low priority defensive team */
226 if (spawn_players(defense_low_thread, "defense-low-thread", DEF_LOW_PRIO))
227 goto out;
228
229 if (spawn_players(defense_mid_thread, "defense-mid-thread", DEF_MID_PRIO))
230 goto out;
231
232 /* Create mid priority offensive team */
233 if (spawn_players(offense_thread, "offense-thread", OFF_PRIO))
234 goto out;
235
236 /* Create high priority defensive team */
237 if (spawn_players(defense_hi_thread, "defense-hi-thread", DEF_HI_PRIO))
238 goto out;
239
240 /* Create high priority crazy fan threads */
241 if (spawn_players(crazy_fan_thread, "crazy-fan-thread", FAN_PRIO))
242 goto out;
243 pr_info("All players checked in! Starting game.\n");
244 atomic_set(&ball_pos, 0);
245 msleep(game_time * 1000);
246 final_pos = atomic_read(&ball_pos);
247 WRITE_ONCE(game_over, true);
248 pr_info("Final ball_pos: %ld\n", final_pos);
249 WARN_ON(final_pos != 0);
250 out:
251 pr_info("Game Over!\n");
252 WRITE_ONCE(game_over, true);
253 complete(&referee_done);
254 return 0;
255 }
256
257 DEFINE_MUTEX(run_lock);
258
play_game(unsigned long game_time)259 static int play_game(unsigned long game_time)
260 {
261 struct task_struct *kth;
262 int i, ret = -1;
263
264 #ifdef CONFIG_SCHED_PROXY_EXEC
265 /* Avoid running test if PROXY_EXEC is built in, but off via cmdline */
266 if (!sched_proxy_exec()) {
267 pr_warn("CONFIG_SCHED_PROXY_EXEC=y but disabled via boot arg, skipping ksched_football tests, as they can hang");
268 return -1;
269 }
270 #endif
271
272 if (!mutex_trylock(&run_lock)) {
273 pr_err("Game already running\n");
274 return -1;
275 }
276
277 players_per_team = num_online_cpus();
278
279 mutex_low_list = kmalloc_array(players_per_team, TEST_LOCK_SIZE, GFP_ATOMIC);
280 if (!mutex_low_list)
281 goto out;
282
283 mutex_mid_list = kmalloc_array(players_per_team, TEST_LOCK_SIZE, GFP_ATOMIC);
284 if (!mutex_mid_list)
285 goto out_mid_list;
286
287 for (i = 0; i < players_per_team; i++) {
288 test_lock_init(&mutex_low_list[i]);
289 test_lock_init(&mutex_mid_list[i]);
290 }
291
292 atomic_set(&players_ready, 0);
293 init_completion(&referee_done);
294 kth = create_fifo_thread(referee_thread, (void *)game_time, "referee-thread", REF_PRIO);
295 if (IS_ERR(kth))
296 goto out_create_fifo;
297 wait_for_completion(&referee_done);
298 msleep(2000);
299 ret = 0;
300
301 out_create_fifo:
302 kfree(mutex_mid_list);
303 out_mid_list:
304 kfree(mutex_low_list);
305 out:
306 mutex_unlock(&run_lock);
307 return ret;
308 }
309
310 static int game_length = DEF_GAME_TIME;
311
start_game_show(struct kobject * kobj,struct kobj_attribute * attr,char * buf)312 static ssize_t start_game_show(struct kobject *kobj, struct kobj_attribute *attr,
313 char *buf)
314 {
315 return sysfs_emit(buf, "%d\n", game_length);
316 }
317
start_game_store(struct kobject * kobj,struct kobj_attribute * attr,const char * buf,size_t count)318 static ssize_t start_game_store(struct kobject *kobj, struct kobj_attribute *attr,
319 const char *buf, size_t count)
320 {
321 unsigned long len;
322 int ret;
323
324 ret = kstrtol(buf, 10, &len);
325 if (ret < 0)
326 return ret;
327
328 if (len < DEF_GAME_TIME) {
329 pr_warn("Game length can't be less then %i\n", DEF_GAME_TIME);
330 len = DEF_GAME_TIME;
331 }
332 play_game(len);
333 game_length = len;
334
335 return count;
336 }
337
338 static struct kobj_attribute start_game_attribute =
339 __ATTR(start_game, 0664, start_game_show, start_game_store);
340
341 static struct attribute *attrs[] = {
342 &start_game_attribute.attr,
343 NULL, /* need to NULL terminate the list of attributes */
344 };
345
346 static struct attribute_group attr_group = {
347 .attrs = attrs,
348 };
349
350 static struct kobject *ksched_football_kobj;
351
test_ksched_football_init(void)352 static int __init test_ksched_football_init(void)
353 {
354 int retval;
355
356 #ifdef CONFIG_SCHED_PROXY_EXEC
357 /* Avoid running test if PROXY_EXEC is built in, but off via cmdline */
358 if (!sched_proxy_exec()) {
359 pr_warn("CONFIG_SCHED_PROXY_EXEC=y but disabled via boot arg, skipping ksched_football tests, as they can hang");
360 return -1;
361 }
362 #endif
363
364 ksched_football_kobj = kobject_create_and_add("ksched_football", kernel_kobj);
365 if (!ksched_football_kobj)
366 return -ENOMEM;
367
368 /* Create the files associated with this kobject */
369 retval = sysfs_create_group(ksched_football_kobj, &attr_group);
370 if (retval)
371 kobject_put(ksched_football_kobj);
372
373 return play_game(DEF_GAME_TIME);
374 }
375 module_init(test_ksched_football_init);
376