1 /* SPDX-License-Identifier: GPL-2.0 */
2 /*
3 * A central FIFO sched_ext scheduler which demonstrates the following:
4 *
5 * a. Making all scheduling decisions from one CPU:
6 *
7 * The central CPU is the only one making scheduling decisions. All other
8 * CPUs kick the central CPU when they run out of tasks to run.
9 *
10 * There is one global BPF queue and the central CPU schedules all CPUs by
11 * dispatching from the global queue to each CPU's local dsq from dispatch().
12 * This isn't the most straightforward. e.g. It'd be easier to bounce
13 * through per-CPU BPF queues. The current design is chosen to maximally
14 * utilize and verify various SCX mechanisms such as LOCAL_ON dispatching.
15 *
16 * b. Tickless operation
17 *
18 * All tasks are dispatched with the infinite slice which allows stopping the
19 * ticks on CONFIG_NO_HZ_FULL kernels running with the proper nohz_full
20 * parameter. The tickless operation can be observed through
21 * /proc/interrupts.
22 *
23 * Periodic switching is enforced by a periodic timer checking all CPUs and
24 * preempting them as necessary. Unfortunately, BPF timer currently doesn't
25 * have a way to pin to a specific CPU, so the periodic timer isn't pinned to
26 * the central CPU.
27 *
28 * c. Preemption
29 *
30 * Kthreads are unconditionally queued to the head of a matching local dsq
31 * and dispatched with SCX_DSQ_PREEMPT. This ensures that a kthread is always
32 * prioritized over user threads, which is required for ensuring forward
33 * progress as e.g. the periodic timer may run on a ksoftirqd and if the
34 * ksoftirqd gets starved by a user thread, there may not be anything else to
35 * vacate that user thread.
36 *
37 * SCX_KICK_PREEMPT is used to trigger scheduling and CPUs to move to the
38 * next tasks.
39 *
40 * This scheduler is designed to maximize usage of various SCX mechanisms. A
41 * more practical implementation would likely put the scheduling loop outside
42 * the central CPU's dispatch() path and add some form of priority mechanism.
43 *
44 * Copyright (c) 2022 Meta Platforms, Inc. and affiliates.
45 * Copyright (c) 2022 Tejun Heo <tj@kernel.org>
46 * Copyright (c) 2022 David Vernet <dvernet@meta.com>
47 */
48 #include <scx/common.bpf.h>
49
50 char _license[] SEC("license") = "GPL";
51
52 enum {
53 FALLBACK_DSQ_ID = 0,
54 MS_TO_NS = 1000LLU * 1000,
55 TIMER_INTERVAL_NS = 1 * MS_TO_NS,
56 };
57
58 const volatile s32 central_cpu;
59 const volatile u32 nr_cpu_ids = 1; /* !0 for veristat, set during init */
60 const volatile u64 slice_ns;
61
62 bool timer_pinned = true;
63 bool timer_started;
64 u64 nr_total, nr_locals, nr_queued, nr_lost_pids;
65 u64 nr_timers, nr_dispatches, nr_mismatches, nr_retries;
66 u64 nr_overflows;
67
68 UEI_DEFINE(uei);
69
70 struct {
71 __uint(type, BPF_MAP_TYPE_QUEUE);
72 __uint(max_entries, 4096);
73 __type(value, s32);
74 } central_q SEC(".maps");
75
76 /* can't use percpu map due to bad lookups */
77 bool RESIZABLE_ARRAY(data, cpu_gimme_task);
78 u64 RESIZABLE_ARRAY(data, cpu_started_at);
79
80 struct central_timer {
81 struct bpf_timer timer;
82 };
83
84 struct {
85 __uint(type, BPF_MAP_TYPE_ARRAY);
86 __uint(max_entries, 1);
87 __type(key, u32);
88 __type(value, struct central_timer);
89 } central_timer SEC(".maps");
90
BPF_STRUCT_OPS(central_select_cpu,struct task_struct * p,s32 prev_cpu,u64 wake_flags)91 s32 BPF_STRUCT_OPS(central_select_cpu, struct task_struct *p,
92 s32 prev_cpu, u64 wake_flags)
93 {
94 /*
95 * Steer wakeups to the central CPU as much as possible to avoid
96 * disturbing other CPUs. It's safe to blindly return the central cpu as
97 * select_cpu() is a hint and if @p can't be on it, the kernel will
98 * automatically pick a fallback CPU.
99 */
100 return central_cpu;
101 }
102
BPF_STRUCT_OPS(central_enqueue,struct task_struct * p,u64 enq_flags)103 void BPF_STRUCT_OPS(central_enqueue, struct task_struct *p, u64 enq_flags)
104 {
105 s32 pid = p->pid;
106
107 __sync_fetch_and_add(&nr_total, 1);
108
109 /*
110 * Push per-cpu kthreads at the head of local dsq's and preempt the
111 * corresponding CPU. This ensures that e.g. ksoftirqd isn't blocked
112 * behind other threads which is necessary for forward progress
113 * guarantee as we depend on the BPF timer which may run from ksoftirqd.
114 */
115 if ((p->flags & PF_KTHREAD) && p->nr_cpus_allowed == 1) {
116 __sync_fetch_and_add(&nr_locals, 1);
117 scx_bpf_dsq_insert(p, SCX_DSQ_LOCAL, SCX_SLICE_INF,
118 enq_flags | SCX_ENQ_PREEMPT);
119 return;
120 }
121
122 if (bpf_map_push_elem(¢ral_q, &pid, 0)) {
123 __sync_fetch_and_add(&nr_overflows, 1);
124 scx_bpf_dsq_insert(p, FALLBACK_DSQ_ID, SCX_SLICE_INF, enq_flags);
125 return;
126 }
127
128 __sync_fetch_and_add(&nr_queued, 1);
129
130 if (!scx_bpf_task_running(p))
131 scx_bpf_kick_cpu(central_cpu, SCX_KICK_PREEMPT);
132 }
133
dispatch_to_cpu(s32 cpu)134 static bool dispatch_to_cpu(s32 cpu)
135 {
136 struct task_struct *p;
137 s32 pid;
138
139 bpf_repeat(BPF_MAX_LOOPS) {
140 if (bpf_map_pop_elem(¢ral_q, &pid))
141 break;
142
143 __sync_fetch_and_sub(&nr_queued, 1);
144
145 p = bpf_task_from_pid(pid);
146 if (!p) {
147 __sync_fetch_and_add(&nr_lost_pids, 1);
148 continue;
149 }
150
151 /*
152 * If we can't run the task at the top for whatever reason,
153 * bounce it to the fallback dsq. Also check
154 * is_migration_disabled() explicitly as p->cpus_ptr may not
155 * reflect the migration-disabled state yet if
156 * migrate_disable_switch() hasn't run.
157 */
158 if (!bpf_cpumask_test_cpu(cpu, p->cpus_ptr) ||
159 (is_migration_disabled(p) && scx_bpf_task_cpu(p) != cpu)) {
160 __sync_fetch_and_add(&nr_mismatches, 1);
161 scx_bpf_dsq_insert(p, FALLBACK_DSQ_ID, SCX_SLICE_INF, 0);
162 bpf_task_release(p);
163 /*
164 * We might run out of dispatch buffer slots if we continue dispatching
165 * to the fallback DSQ, without dispatching to the local DSQ of the
166 * target CPU. In such a case, break the loop now as will fail the
167 * next dispatch operation.
168 */
169 if (!scx_bpf_dispatch_nr_slots())
170 break;
171 continue;
172 }
173
174 /* dispatch to local and mark that @cpu doesn't need more */
175 scx_bpf_dsq_insert(p, SCX_DSQ_LOCAL_ON | cpu, SCX_SLICE_INF, 0);
176
177 if (cpu != central_cpu)
178 scx_bpf_kick_cpu(cpu, SCX_KICK_IDLE);
179
180 bpf_task_release(p);
181 return true;
182 }
183
184 return false;
185 }
186
start_central_timer(void)187 static void start_central_timer(void)
188 {
189 struct bpf_timer *timer;
190 u32 key = 0;
191 int ret;
192
193 if (likely(timer_started))
194 return;
195
196 timer = bpf_map_lookup_elem(¢ral_timer, &key);
197 if (!timer) {
198 scx_bpf_error("failed to lookup central timer");
199 return;
200 }
201
202 ret = bpf_timer_start(timer, TIMER_INTERVAL_NS, BPF_F_TIMER_CPU_PIN);
203 /*
204 * BPF_F_TIMER_CPU_PIN is pretty new (>=6.7). If we're running in a
205 * kernel which doesn't have it, bpf_timer_start() will return -EINVAL.
206 * Retry without the PIN. This would be the perfect use case for
207 * bpf_core_enum_value_exists() but the enum type doesn't have a name
208 * and can't be used with bpf_core_enum_value_exists(). Oh well...
209 */
210 if (ret == -EINVAL) {
211 timer_pinned = false;
212 ret = bpf_timer_start(timer, TIMER_INTERVAL_NS, 0);
213 }
214
215 if (ret) {
216 scx_bpf_error("bpf_timer_start failed (%d)", ret);
217 return;
218 }
219
220 timer_started = true;
221 }
222
BPF_STRUCT_OPS(central_dispatch,s32 cpu,struct task_struct * prev)223 void BPF_STRUCT_OPS(central_dispatch, s32 cpu, struct task_struct *prev)
224 {
225 if (cpu == central_cpu) {
226 start_central_timer();
227
228 /* dispatch for all other CPUs first */
229 __sync_fetch_and_add(&nr_dispatches, 1);
230
231 bpf_for(cpu, 0, nr_cpu_ids) {
232 bool *gimme;
233
234 if (!scx_bpf_dispatch_nr_slots())
235 break;
236
237 /* central's gimme is never set */
238 gimme = ARRAY_ELEM_PTR(cpu_gimme_task, cpu, nr_cpu_ids);
239 if (!gimme || !*gimme)
240 continue;
241
242 if (dispatch_to_cpu(cpu))
243 *gimme = false;
244 }
245
246 /*
247 * Retry if we ran out of dispatch buffer slots as we might have
248 * skipped some CPUs and also need to dispatch for self. The ext
249 * core automatically retries if the local dsq is empty but we
250 * can't rely on that as we're dispatching for other CPUs too.
251 * Kick self explicitly to retry.
252 */
253 if (!scx_bpf_dispatch_nr_slots()) {
254 __sync_fetch_and_add(&nr_retries, 1);
255 scx_bpf_kick_cpu(central_cpu, SCX_KICK_PREEMPT);
256 return;
257 }
258
259 /* look for a task to run on the central CPU */
260 if (scx_bpf_dsq_move_to_local(FALLBACK_DSQ_ID, 0))
261 return;
262 dispatch_to_cpu(central_cpu);
263 } else {
264 bool *gimme;
265
266 if (scx_bpf_dsq_move_to_local(FALLBACK_DSQ_ID, 0))
267 return;
268
269 gimme = ARRAY_ELEM_PTR(cpu_gimme_task, cpu, nr_cpu_ids);
270 if (gimme)
271 *gimme = true;
272
273 /*
274 * Force dispatch on the scheduling CPU so that it finds a task
275 * to run for us.
276 */
277 scx_bpf_kick_cpu(central_cpu, SCX_KICK_PREEMPT);
278 }
279 }
280
BPF_STRUCT_OPS(central_running,struct task_struct * p)281 void BPF_STRUCT_OPS(central_running, struct task_struct *p)
282 {
283 s32 cpu = scx_bpf_task_cpu(p);
284 u64 *started_at = ARRAY_ELEM_PTR(cpu_started_at, cpu, nr_cpu_ids);
285 if (started_at)
286 *started_at = scx_bpf_now() ?: 1; /* 0 indicates idle */
287 }
288
BPF_STRUCT_OPS(central_stopping,struct task_struct * p,bool runnable)289 void BPF_STRUCT_OPS(central_stopping, struct task_struct *p, bool runnable)
290 {
291 s32 cpu = scx_bpf_task_cpu(p);
292 u64 *started_at = ARRAY_ELEM_PTR(cpu_started_at, cpu, nr_cpu_ids);
293 if (started_at)
294 *started_at = 0;
295 }
296
central_timerfn(void * map,int * key,struct bpf_timer * timer)297 static int central_timerfn(void *map, int *key, struct bpf_timer *timer)
298 {
299 u64 now = scx_bpf_now();
300 u64 nr_to_kick = nr_queued;
301 s32 i, curr_cpu;
302 int ret;
303
304 curr_cpu = bpf_get_smp_processor_id();
305 if (timer_pinned && (curr_cpu != central_cpu)) {
306 scx_bpf_error("Central timer ran on CPU %d, not central CPU %d",
307 curr_cpu, central_cpu);
308 return 0;
309 }
310
311 bpf_for(i, 0, nr_cpu_ids) {
312 s32 cpu = (nr_timers + i) % nr_cpu_ids;
313 u64 *started_at;
314
315 if (cpu == central_cpu)
316 continue;
317
318 /* kick iff the current one exhausted its slice */
319 started_at = ARRAY_ELEM_PTR(cpu_started_at, cpu, nr_cpu_ids);
320 if (started_at && *started_at &&
321 time_before(now, *started_at + slice_ns))
322 continue;
323
324 /* and there's something pending */
325 if (scx_bpf_dsq_nr_queued(FALLBACK_DSQ_ID) ||
326 scx_bpf_dsq_nr_queued(SCX_DSQ_LOCAL_ON | cpu))
327 ;
328 else if (nr_to_kick)
329 nr_to_kick--;
330 else
331 continue;
332
333 scx_bpf_kick_cpu(cpu, SCX_KICK_PREEMPT);
334 }
335
336 ret = bpf_timer_start(timer, TIMER_INTERVAL_NS,
337 timer_pinned ? BPF_F_TIMER_CPU_PIN : 0);
338 if (ret)
339 scx_bpf_error("bpf_timer_start failed (%d)", ret);
340 __sync_fetch_and_add(&nr_timers, 1);
341 return 0;
342 }
343
BPF_STRUCT_OPS_SLEEPABLE(central_init)344 int BPF_STRUCT_OPS_SLEEPABLE(central_init)
345 {
346 u32 key = 0;
347 struct bpf_timer *timer;
348 int ret;
349
350 ret = scx_bpf_create_dsq(FALLBACK_DSQ_ID, -1);
351 if (ret) {
352 scx_bpf_error("scx_bpf_create_dsq failed (%d)", ret);
353 return ret;
354 }
355
356 timer = bpf_map_lookup_elem(¢ral_timer, &key);
357 if (!timer)
358 return -ESRCH;
359
360 bpf_timer_init(timer, ¢ral_timer, CLOCK_MONOTONIC);
361 bpf_timer_set_callback(timer, central_timerfn);
362
363 scx_bpf_kick_cpu(central_cpu, 0);
364
365 return 0;
366 }
367
BPF_STRUCT_OPS(central_exit,struct scx_exit_info * ei)368 void BPF_STRUCT_OPS(central_exit, struct scx_exit_info *ei)
369 {
370 UEI_RECORD(uei, ei);
371 }
372
373 SCX_OPS_DEFINE(central_ops,
374 /*
375 * We are offloading all scheduling decisions to the central CPU
376 * and thus being the last task on a given CPU doesn't mean
377 * anything special. Enqueue the last tasks like any other tasks.
378 */
379 .flags = SCX_OPS_ENQ_LAST,
380
381 .select_cpu = (void *)central_select_cpu,
382 .enqueue = (void *)central_enqueue,
383 .dispatch = (void *)central_dispatch,
384 .running = (void *)central_running,
385 .stopping = (void *)central_stopping,
386 .init = (void *)central_init,
387 .exit = (void *)central_exit,
388 .name = "central");
389