1/* @title: Real-time scheduling */
2#pragma once
3#include <log.h>
4#include <sch/rt_sched_types.h>
5#include <smp/topology.h>
6#include <stdatomic.h>
7#include <stdbool.h>
8#include <stddef.h>
9#include <stdint.h>
10#include <structures/list.h>
11#include <structures/locked_list.h>
12#include <structures/rbt.h>
13#include <sync/semaphore.h>
14#include <thread/thread_types.h>
15#include <thread/workqueue.h>
16#include <types/refcount.h>
17
18/* @idea:big Real-time scheduler load balancing */
19/*
20 * # Big Idea: Realtime scheduler load balancing (EXPERIMENTAL)
21 *
22 * ## Credits: axvon
23 *
24 * ## Audience: Realtime program writers and scheduler interested people
25 *
26 * ## Overview:
27 *
28 * Our realtime thread scheduling load balancing philosophy is based around
29 * this following "overarching theory statement":
30 *
31 *
32 * "Always pull, never push."
33 *
34 *
35 * Whenever load balancing occurs, there is always a "positive" party,
36 * and a "negative" party.
37 *
38 * The positive party is the one which gets load removed, and the negative
39 * party is the one that gets load added.
40 *
41 * Within realtime scheduling, some amount of non-determinism will always be
42 * present (e.g. the branch predictor decides to evict entries from its BTB,
43 * the cache misses a few times here and there, a spinlock is spun on
44 * for a few extra cycles).
45 *
46 * Thus, our goal becomes NOT to completely remove non-determinism, as that
47 * becomes somewhat of an infeasible plumbing job, but rather, it is to
48 * minimize non-determinism and its harm.
49 *
50 * ## Background:
51 *
52 * Realtime scheduler load balancing has long been a topic of great contention
53 * in realtime scheduling. Although EDF is a provably optimal algorithm on
54 * uniprocessor systems, its performance and optimality is varied on
55 * multiprocessor machines.
56 *
57 * ## Summary:
58 *
59 * Load balancing in a realtime operating system that supports timesharing
60 * scheduling is inherently non-deterministic. The outcome of a load
61 * balance is almost entirely dependent on the various loads
62 * present on the different nodes and logical processors.
63 *
64 * However, we can reduce this non-determinism by making the load balancing
65 * unidirectional, or in other words, only allowing one kind of migration.
66 *
67 * There are two main kinds of load migration:
68 *
69 * Pushing is when the positive party actively offloads its work
70 * onto the negative party, with the negative party not having
71 * any say in this matter.
72 *
73 * Pulling is when the negative party actively takes work from
74 * the positive party, with the positive party not being
75 * able to do much regarding this action.
76 *
77 * Within realtime scheduling, the impact of the non-determinism from
78 * pushing is clearly much more significant and harmful than pulling.
79 *
80 * Imagine this:
81 * CPU0 is happily running its 3 realtime tasks
82 *
83 * CPU1 is unhappily running its 9 realtime tasks
84 *
85 * CPU0 is making its way through a long-running compute task,
86 * with 2 more interactive tasks in the queue
87 *
88 * CPU1 is switching more rapidly between its 8 tasks
89 *
90 * Then, all of a sudden, CPU1 context switches, and
91 * exclaims "I can't take this anymore!",
92 * and it pushes 3 of its tasks onto CPU0.
93 *
94 * Now, CPU0 has had an influx of work, but it is still running
95 * its compute task. This brings a major problem:
96 *
97 * "The work we just moved will have no guarantee that it is run"
98 *
99 * And we can end up in this scenario:
100 *
101 * CPU0 is happily running one of its 6 realtime tasks, but
102 * some new tasks are sitting in the queue expecting to
103 * be switched to, but that never happens.
104 *
105 * CPU1 is now a bit less frustrated about its load, but now
106 * 3 tasks that were originally assigned to it are waiting
107 * in a runqueue, and it no longer is able to choose when
108 * those 3 tasks will get to run again, unless it tracks the
109 * affinity of each of the tasks that it was running and moves them back.
110 *
111 * Now, compare this to pull-only policies:
112 * CPU0 is happily running its 3 realtime tasks
113 *
114 * CPU1 is unhappily running its 9 realtime tasks
115 *
116 * CPU0 context switches, and *notices* that CPU1 has
117 * some extra work it can take. It decides to pull it over,
118 * and then immediately run it.
119 *
120 * Now, although CPU0 has had work added, this work
121 * is guaranteed runtime after the migration, potentially
122 * allowing it to complete early/giving it more CPU time.
123 *
124 * From this example, we can see how using pull-only migration provides
125 * stricter, deterministic guarantees about whether or not a task will
126 * run after being migrated. This is the primary reason why we are
127 * choosing this paradigm, in addition to a slight improvement in
128 * *when* tasks get migrated (i.e. on the negative party's side, an explicit
129 * call to yield the processor must be made for work to be added, as opposed
130 * to work pushing where the negative party can randomly get work added.
131 *
132 * ## API:
133 * TODO
134 *
135 * ## Errors:
136 *
137 * The modular realtime scheduler system of this kernel *allows realtime
138 * schedulers to fail*, and *fails upwards*. TODO
139 *
140 * ## Context:
141 *
142 * The realtime scheduler exists under the broader scheduling and multitasking
143 * capabilities of this kernel, and exists in contrast to the primary
144 * timesharing scheduler which is detailed to a greater extent elsewhere.
145 *
146 * ## Constraints:
147 * TODO
148 *
149 * ## Internals:
150 * TODO
151 *
152 * ## Strategy:
153 * TODO
154 *
155 * ## Rationale:
156 * TODO
157 *
158 */
159
160LOG_SITE_EXTERN(rt_sched); /* For generic logging */
161LOG_HANDLE_EXTERN(rt_sched); /* For generic logging */
162
163#define rt_sched_log(lvl, fmt, ...) \
164 log(LOG_SITE(rt_sched), LOG_HANDLE(rt_sched), lvl, fmt, ##__VA_ARGS__)
165
166#define rt_sched_err(fmt, ...) rt_sched_log(LOG_ERROR, fmt, ##__VA_ARGS__)
167#define rt_sched_warn(fmt, ...) rt_sched_log(LOG_WARN, fmt, ##__VA_ARGS__)
168#define rt_sched_info(fmt, ...) rt_sched_log(LOG_INFO, fmt, ##__VA_ARGS__)
169#define rt_sched_debug(fmt, ...) rt_sched_log(LOG_DEBUG, fmt, ##__VA_ARGS__)
170#define rt_sched_trace(fmt, ...) rt_sched_log(LOG_TRACE, fmt, ##__VA_ARGS__)
171
172/* Realtime schedulers are allowed to reserve a certain amount of pointer-sized
173 * fields in each thread to use for whatever they would like. This is ideally
174 * not meant to point to dynamically allocated memory, and should be used
175 * to embed additional data per thread. */
176
177/* We refer to these as "slots". I could call them "reservations", but much
178 * RT scheduling related work uses "reservation" to refer to time "slices"
179 * in static scheduling of tasks, and I don't want to deal with odd name
180 * conflicts */
181#define RT_SCHEDULER_SLOTS_PER_THREAD 8
182
183typedef size_t rt_domain_id_t;
184typedef int32_t rt_weight_t;
185
186/* This is a range from [-1, 1], where
187 * -1 means "Not urgent at all", and
188 * 1 means "absolutely urgent, things
189 * keep missing, problems keep
190 * happening"... */
191typedef fx32_32_t rt_urgency_t;
192
193struct rt_scheduler;
194
195/* This enum exists for debug/info reasons. No actual operations are
196 * performed based on the topology level */
197enum rt_scheduler_topo_level {
198 RT_SCHEDULER_TOPO_SMT, /* Symmetric multiprocessing threads */
199 RT_SCHEDULER_TOPO_CORE, /* SMTs under a core */
200 RT_SCHEDULER_TOPO_NUMA, /* NUMA node */
201 RT_SCHEDULER_TOPO_LLC, /* Last level cache (some processors
202 * have multiple L3 caches for a given
203 * physical processor) */
204 RT_SCHEDULER_TOPO_PACKAGE, /* Physical processor in a socket */
205 RT_SCHEDULER_TOPO_MACHINE, /* Whole machine */
206 RT_SCHEDULER_TOPO_CUSTOM, /* Custom topology */
207};
208
209/* rt_scheduler_status: 16 bit "bitflags":
210 *
211 * ┌───────────────────────────┐
212 * Bits │ 15..12 11..8 7..4 3..0 │
213 * Use │ AAAA **** **IT D%%% │
214 * └───────────────────────────┘
215 *
216 *
217 * D - Degraded performance observed
218 * T - Throttled
219 * I - CPU isolation
220 * A - Unused (Available)
221 * * - Unused (Unavailable)
222 * %%% - Overloaded amount bits
223 *
224 */
225enum rt_scheduler_status : uint16_t {
226 RT_SCHEDULER_STATUS_OK = 0,
227 RT_SCHEDULER_STATUS_DEGRADED = 1 << 3,
228 RT_SCHEDULER_STATUS_THROTTLED = 1 << 4,
229 RT_SCHEDULER_STATUS_ISOLATED = 1 << 5,
230};
231
232/* These are the primary instances of an RT scheduler module...
233 *
234 * It can either be unloaded (inactive, default), or loaded
235 * (_static data structures allocated), or active (there exists
236 * an active instance of this rt_scheduler_static on some CPU */
237enum rt_scheduler_static_state {
238 RT_SCHEDULER_STATIC_UNLOADED, /* No structures allocated */
239 RT_SCHEDULER_STATIC_LOADED, /* Structures allocated, unused (this state
240 * doesn't strictly need to exist for
241 * correctness purposes, but is very helpful
242 * in debugging and to allow one to unload
243 * unused rt_scheduler_statics */
244 RT_SCHEDULER_STATIC_DESTROYING, /* Taking down. No one can "Grab a ref" */
245};
246
247enum rt_slot_priority {
248 RT_SLOT_REQUIRED, /* Scheduler load will fail if this fails */
249 RT_SLOT_OPTIONAL, /* Scheduler load will continue if this fails */
250};
251
252struct rt_slot_request {
253 char *name; /* Debug */
254 enum rt_slot_priority prio;
255 int32_t mapped_to; /* -1 = none */
256};
257
258struct rt_scheduler_blocklist_node {
259 struct list_head list;
260 char *blocked_scheduler_name;
261};
262
263struct rt_scheduler_percpu_permitted {
264 enum rt_scheduler_capability allowed_capabilities;
265 struct list_head blocklist;
266 struct spinlock lock;
267};
268
269struct rt_thread_summary {
270 /* This field exists as a "Summary of the summary". It gives us a
271 * high level, obvious and simple (but somewhat inaccurate) indicator
272 * to motivate the core scheduler to read the other fields inside
273 * this structure. Its main role is for performance/quick summaries */
274
275 enum rt_scheduler_status status;
276
277 rt_weight_t weight; /* A "weight" of the load on the scheduler. A thread
278 * provides a base weight, and then this can be added
279 * or removed depending on properties of the thread */
280 rt_weight_t weight_ewma;
281
282 /* Urgency is separate from the weight of a thread. There can be
283 * a lot of threads on an RT scheduler, but they could all just be
284 * hitting their deadlines fine and doing a-OK, indicating that
285 * there is less of a need for migrations to happen away */
286 rt_urgency_t urgency;
287 rt_urgency_t urgency_ewma;
288
289 /* Each rt_scheduler contains one of these */
290};
291
292struct rt_thread_summary_ext {
293 struct rt_scheduler_static *source; /* The statically allocated
294 * variable, used to compare if
295 * two exts are from
296 * the same scheduler for
297 * decisionmaking bias */
298
299 void *private; /* We DO NOT hardcode _ext fields into
300 * the main structure. All we can do is check if
301 * two rt_schedulers are using the same policy,
302 * and then allow them to coordinate internally
303 * IF AND ONLY IF that is the case. */
304
305 /* Each rt_scheduler can be polled for this */
306};
307
308/* Because we adopt a "Pull only" philosophy within load balancing, we
309 * use "shed requests" to allow RT schedulers to say "I have work, take it away
310 * from me". These exist separate from summaries, as these will set a bit
311 * in a per-domain bitmap regarding the RT scheduler request statuses */
312struct rt_thread_shed_request {
313 bool on; /* Not always on */
314 rt_urgency_t urgency; /* How much do we need to have things moved? */
315
316 size_t threads_available; /* How many can we take away? */
317
318 /* This is a "suggestion" list of threads to take.
319 * Notably, the amount of threads on this list does NOT
320 * HAVE TO match the `threads_available`. This gives
321 * us the ability to potentially say "Hey, we have X
322 * threads available, however, we do not know
323 * specifically which of these you might want to take.
324 *
325 * (e.g. RR might just see that there are too many
326 * threads, and simply say "we have N too many")
327 * Rule behind this: before anything is ever taken
328 * from `threads`, it MUST be verified that it *can* be taken.
329 *
330 * Ideally, no pinned threads should end up here, however, if
331 * any do, (or if any incompatible cpu masks are here), they
332 * should absolutely not get pulled onto another domain */
333 struct list_head threads;
334};
335
336typedef enum rt_scheduler_error (*rt_scheduler_fn)(struct rt_scheduler *);
337typedef enum rt_scheduler_error (*rt_scheduler_static_fn)(
338 struct rt_scheduler_static *);
339typedef void (*rt_scheduler_thread_fn)(struct rt_scheduler *, struct thread *);
340
341/* The rt_scheduler lock is held prior to calling these
342 * functions unless explicitly stated otherwise */
343struct rt_scheduler_ops {
344 /* RT scheduler initialization happens once at load/boot */
345 rt_scheduler_static_fn on_load;
346 rt_scheduler_static_fn on_unload;
347
348 rt_scheduler_fn init; /* RT scheduler lock not held */
349
350 rt_scheduler_fn destroy; /* Must be called AFTER the
351 * RT scheduler is not used */
352
353 rt_scheduler_fn switch_in; /* scheduler switched in */
354 rt_scheduler_fn switch_out; /* scheduler switched out */
355
356 rt_scheduler_fn on_failure; /* Called when the RT scheduler fails. This
357 * is not intended to do much heavy
358 * lifting, and is meant to instead
359 * recover what can be recovered/log data */
360
361 /* Two RT schedulers are deemed "twins" if they belong to the same
362 * rt_scheduler_static. This allows rt schedulers of the same
363 * type to make migration decisions, and make them better
364 * than what the core scheduler might be able to "guess/estimate"
365 *
366 * Both locks are acquired */
367 enum rt_scheduler_error (*migrate_twin)(struct rt_scheduler *self,
368 struct rt_scheduler *other);
369
370 struct thread *(*pick_thread)(
371 struct rt_scheduler *); /* select next RT thread, if any */
372
373 rt_scheduler_thread_fn add_thread;
374 rt_scheduler_thread_fn remove_thread;
375 struct rt_thread_summary_ext (*get_summary_ext)(struct rt_scheduler *);
376
377 rt_scheduler_fn on_tick;
378
379 /* This is called to tell the RT scheduler "Give me all your threads back,
380 * and put them onto this list". The reason we have this is because at
381 * failure points/swap out points, we need to get all our threads back,
382 * so that we can hold them for a bit before letting another scheduler
383 * get back at it and schedule them */
384
385 /* Use t->rt_list_node for this */
386 void (*return_all_threads)(struct rt_scheduler *, struct list_head *);
387
388 rt_domain_id_t (*domain_id_for_cpu)(struct core *);
389};
390
391struct rt_ext_fn {
392 const char *name;
393 uint32_t id;
394 uintptr_t (*fn)(uintptr_t, uintptr_t);
395};
396
397/* Here is how we bind CPUs together within the realtime scheduler:
398 *
399 * Basically, every realtime scheduler is expected to return
400 * a rt_domain_id_t for each struct core. Each rt_domain_id_t has
401 * exactly ONE mapping for which rt_scheduler it is bound to.
402 *
403 * Whenever a thread wants to migrate to a given CPU, it doesn't
404 * JUST check if the cpu mask is compatible with that CPU, but rather,
405 * with the mask of the rt_scheduler_mapping that that CPU is using
406 * for its rt_scheduler structure.
407 *
408 * This gives us the ability to choose the granularity which we have
409 * our rt_schedulers operate at. We can make them global, we can make
410 * them per-node, per-socket, per-cpu, etc...
411 */
412struct rt_scheduler_mapping {
413 struct rbt_node tree_node;
414 struct rt_scheduler_static *static_bptr;
415 rt_domain_id_t id;
416 struct cpu_mask members;
417 struct cpu_mask active; /* Subset of `members` */
418 struct rt_scheduler *rts;
419 struct spinlock lock;
420 void *data;
421};
422
423/* This is statically allocated (in a linker section if it's a part
424 * of the main kernel), and meant to represent "What can this scheduler
425 * do" instead of a running state of a scheduler */
426
427struct rt_scheduler_static {
428
429 /* ---------- INTERNAL ---------- */
430 struct list_head list_internal;
431 struct rbt mappings_internal; /* "dynamic" object.
432 * nodes are dynamic, this is static */
433 struct cpu_mask *active_mask_internal; /* Who is using us? */
434 refcount_t refcount;
435 struct work teardown_work;
436 _Atomic enum rt_scheduler_static_state state;
437 struct spinlock state_change_lock;
438
439 /* ---------- EXTERNAL ---------- */
440 const char *name;
441 struct rt_scheduler_ops ops;
442 enum rt_scheduler_topo_level topo_level;
443 enum rt_scheduler_capability capabilities;
444 size_t num_slot_requests; /* We use this to determine how many slot requests
445 * we should *actually* go through and fill */
446 struct rt_slot_request slot_requests[RT_SCHEDULER_SLOTS_PER_THREAD];
447 size_t num_ext_fns;
448 struct rt_ext_fn ext_fns[];
449};
450
451/* This is a structure that is allocated per-CPU at boot time.
452 *
453 * Whenever a scheduler is swapped out, this entire thing is cleared/reset,
454 * and then another scheduler comes and populates it. This population is
455 * allowed to perform allocations and such, so it must take place inside of a
456 * DPC. Similarly, destruction happens in a DPC */
457struct rt_scheduler {
458 struct list_head list; /* This is used to keep a global pool of
459 * rt_schedulers. We split this per-domain,
460 * and whenever a CPU switches into an
461 * rt_scheduler, it takes one out of
462 * the pool, and whenever a CPU no longer
463 * is using its own rt_scheduler, it
464 * puts it back into the pool */
465
466 struct core *owner; /* We make one per-CPU. Who owns this one? */
467
468 struct rt_scheduler_mapping *mapping_source; /* Used to look at what other
469 * CPUs can access this one */
470
471 bool failed_internal; /* Used to temporarily indicate that the scheduler has
472 * FAIL_ASAP'd a function, but it just isn't safe to
473 * fail the scheduler at the current moment
474 * (checked later) */
475
476 struct rt_thread_summary summary; /* Summary of "What's goin on?" */
477 struct rt_thread_shed_request shed_request;
478
479 struct log_site *log_site; /* This is used for the core scheduler to log
480 * general RT scheduler events to, like state
481 * transitions and such. The RT scheduler
482 * itself is also allowed to modify this,
483 * but it can also keep its own log_site */
484
485 struct log_handle log_handle; /* Similarly, a structure that the core
486 * scheduler uses to log rt_scheduler changes
487 * and whatnot. Usable by the rt_scheduler
488 * itself, but the rt_scheduler can go
489 * and do what it likes */
490
491 size_t thread_count;
492
493 /* LOCK ORDERING: lower address first */
494
495 struct spinlock lock; /* This lock protects the rt_scheduler too, however
496 * RT schedulers themselves are free to do whatever
497 * internal locking they'd like (if that somehow
498 * becomes a thing they want to do?) */
499};
500
501struct rt_scheduler_percpu {
502 struct scheduler *scheduler; /* Backpointer for this CPU */
503 struct rt_scheduler *born_with;
504 struct rt_scheduler_mapping *active_mapping;
505 struct rt_scheduler_percpu_permitted perms;
506
507 /* This is how we synchronize switching the rt scheduler.
508 *
509 * The technique is as follows: We initialize the switch_semaphore to 1.
510 *
511 * When entering the switch routine, we first invoke semaphore_wait
512 *
513 * Then, inside of the switch, we semaphore_wake */
514 struct semaphore switch_semaphore;
515 struct log_site *log_site;
516 struct log_handle log_handle;
517 _Atomic enum rt_scheduler_error switch_code;
518 _Atomic(struct rt_scheduler_static *) switch_into;
519};
520
521struct rt_global {
522 struct locked_list static_list;
523 struct locked_list *sch_pool; /* one per domain */
524
525 /* TODO: If someone can come up with a better solution, tell me */
526 struct spinlock switch_lock;
527};
528
529extern struct workqueue *rt_wq;
530extern struct rt_global rt_global;
531
532void rt_scheduler_boot_init();
533