1/* @title: Scheduler */
2#pragma once
3#include <global.h>
4#include <irq/ipi.h>
5#include <sch/domain.h>
6#include <smp/core.h>
7#include <smp/topology.h>
8#include <stdarg.h>
9#include <stdbool.h>
10#include <structures/rbt.h>
11#include <sync/spinlock.h>
12#include <thread/thread_types.h>
13#include <time/timer.h>
14#include <tsa.h>
15
16#define WORK_STEAL_THRESHOLD \
17 75ULL /* How little work the core needs to be \
18 * doing to try to steal work from another \
19 * core. This means "% of the average" \
20 */
21
22#define SCHEDULER_DEFAULT_WORK_STEAL_MIN_DIFF 130
23
24struct idle_thread_data {
25 atomic_uint64_t last_entry_ms;
26 uint64_t last_exit_ms;
27};
28
29struct scheduler {
30 /* Current tick data */
31 atomic_bool tick_enabled;
32 time_ms_t tick_duration_ms;
33
34 /* Structures */
35 struct list_head urgent_threads;
36
37 struct rbt thread_rbt;
38 struct rbt completed_rbt;
39
40 struct list_head rt_threads;
41 struct list_head bg_threads;
42
43 struct rbt climb_threads; /* threads on this CPU participating in CLIMB */
44
45 atomic_uint8_t queue_bitmap;
46
47 struct thread *current;
48 struct thread *drop_last_ref;
49 struct timer tick;
50
51 struct spinlock wroost_lock;
52 struct wroost_percpu_data *wroost_data;
53
54 /* Thread count at each prio */
55 size_t thread_count[THREAD_PRIO_CLASS_COUNT];
56 size_t total_thread_count;
57 size_t total_weight;
58
59 /* Period information */
60 bool period_enabled;
61 uint64_t current_period;
62
63 time_ms_t period_ms;
64 time_ms_t period_start_ms; /* Timestamp */
65
66#ifdef PROFILING_SCHED
67 size_t periods_started; /* How many have we started?
68 * (Each one must complete) */
69
70 size_t idle_thread_loads;
71#endif
72
73 cpu_id_t core_id;
74
75 /* TODO: Rework time load balancing away from this foolery */
76
77 /* Work steal/migration */
78 atomic_bool being_robbed;
79 atomic_bool stealing_work;
80
81 struct spinlock lock;
82
83 /* Idle thread data */
84 struct thread *idle_thread;
85 struct idle_thread_data idle_thread_data;
86
87 struct scheduler *other_locked; /* If we acquired the lock of another
88 * scheduler in scheduler_yield(),
89 * we store a pointer to it here.
90 *
91 * If this is NULL, we didn't do that,
92 * but in the case that it isn't, we must
93 * drop the raw lock for this in addition
94 * to the lock for our scheduler */
95
96 enum irql locked_irql;
97 enum irql other_locked_irql;
98
99 struct cpu_mask deferred_resched_mask;
100 struct rt_scheduler_percpu *rt;
101
102#ifdef DEBUG_SCHED
103 /* Runqueue progress, racily read by detector */
104 atomic_uint64_t debug_progress_ms;
105#endif
106};
107
108void scheduler_init(void);
109
110#ifdef DEBUG_SCHED
111void scheduler_debug_start(void);
112#else
113static inline void scheduler_debug_start(void) {}
114#endif
115
116struct scheduler *scheduler_select_best_for_thread(struct thread *t);
117void scheduler_add_thread_locked(struct scheduler *sched, struct thread *thread)
118 TSA_CALLER_HOLDS(&sched->lock);
119
120void scheduler_add_thread(struct scheduler *sched, struct thread *thread);
121
122void scheduler_remove_thread_locked(struct scheduler *sched, struct thread *t)
123 TSA_CALLER_HOLDS(&sched->lock);
124
125void scheduler_remove_thread(struct scheduler *sched, struct thread *t);
126void schedule(void);
127void k_sch_main(void *);
128void scheduler_idle_main(void *);
129void scheduler_yield(void);
130
131void scheduler_period_start(struct scheduler *s, uint64_t now_ms);
132
133void switch_context(struct cpu_context *old, struct cpu_context *new);
134void load_context(struct cpu_context *new);
135void save_context(struct cpu_context *new);
136
137bool scheduler_can_steal_work(struct scheduler *sched);
138bool scheduler_can_take_thread(size_t core, struct thread *target);
139uint64_t scheduler_compute_steal_threshold(void);
140struct thread *scheduler_try_do_steal(struct scheduler *sched);
141
142struct scheduler *scheduler_pick_victim(struct scheduler *self);
143struct thread *scheduler_steal_work(struct scheduler *new,
144 struct scheduler *victim);
145
146size_t scheduler_try_push_to_idle_core(struct scheduler *sched);
147
148void scheduler_tick_enable(void);
149void scheduler_tick_disable(void);
150enum irq_result scheduler_reschedule_isr(struct irq_context *rsp, void *ctx);
151
152/* For a global structure containing central scheduler data */
153struct scheduler_data {
154 uint32_t max_concurrent_stealers;
155 atomic_uint32_t active_stealers;
156 atomic_uint32_t total_threads;
157 atomic_int64_t steal_min_diff;
158};
159
160extern struct scheduler_data scheduler_data;
161
162static inline bool scheduler_self_in_resched(void) {
163 return smp_read(TOPC_NONE, in_resched);
164}
165
166/* Because this is always executed at or above DISPATCH it is fine */
167static inline bool scheduler_mark_self_in_resched(bool new) {
168 return atomic_exchange(&smp_core(TOPC_IRQL)->in_resched, new);
169}
170
171static inline bool scheduler_mark_core_needs_resched(struct core *c, bool new) {
172 return atomic_exchange(&c->needs_resched, new);
173}
174
175static inline bool scheduler_mark_self_needs_resched(bool new) {
176 return scheduler_mark_core_needs_resched(c: smp_core(cond: TOPC_NONE), new);
177}
178
179static inline bool scheduler_mark_core_needs_run_dpcs(struct core *c,
180 bool new) {
181 return atomic_exchange(&c->needs_run_dpcs, new);
182}
183
184static inline bool scheduler_mark_self_needs_run_dpcs(bool new) {
185 return scheduler_mark_core_needs_run_dpcs(c: smp_core(cond: TOPC_NONE), new);
186}
187
188/* this is only ever called when a thread is loaded */
189static inline void scheduler_mark_self_idle(bool new) {
190 /* the old value is different from the new one */
191 struct core *c = smp_core(cond: TOPC_IRQL); /* Only ever called from
192 * the reschedule routine */
193
194 if (atomic_load_rlx(&c->idle) != new) {
195 atomic_store_rlx(&c->idle, new);
196 topology_mark_core_idle(cpu_id: c->id, idle: new);
197 scheduler_domain_mark_self_idle(idle: new);
198 if (new) {
199 atomic_inc_acq_rel(&global.idle_core_count);
200 } else {
201 atomic_dec_acq_rel(&global.idle_core_count);
202 }
203 }
204}
205
206static inline void scheduler_resched_if_needed(void) {
207 if (scheduler_self_in_resched())
208 return;
209
210 if (scheduler_mark_self_needs_resched(false))
211 scheduler_yield();
212}
213
214static inline bool scheduler_core_idle(struct core *c) {
215 return atomic_load(&c->idle);
216}
217
218/* NOTE: this function is unsafe to call from context that holds a runqueue
219 * lock. The reason:
220 *
221 * Imagine the following:
222 * CPU 0 is holding RQ 0's lock
223 * CPU 0 IPI's CPU 1
224 * CPU 1, before that IPI arrives, was spinning on
225 * RQ 0's lock, since it was migrating a thread.
226 *
227 * Thus, CPU 1 cannot respond to the IPI
228 * because it has interrupts disabled,
229 * and will never enter the ISR to ack.
230 *
231 * CPU 0 spins on waiting for this (uncompletable) IPI to complete
232 * CPU 1 is also stuck waiting for RQ 0's lock to be relinquished,
233 * which is something that won't happen because of this
234 * dependency
235 *
236 * *boom* deadlock.
237 *
238 * scheduler core code is supposed to call scheduler_defer_resched()
239 * defined in the internal header there.
240 */
241static inline void scheduler_force_resched(struct scheduler *sched) {
242 scheduler_mark_core_needs_resched(c: global.cores[sched->core_id], true);
243 ipi_send(cpu: sched->core_id, IRQ_SCHEDULER);
244}
245
246static inline bool cc_warn_unused_result
247scheduler_try_force_resched(struct scheduler *sched) {
248 scheduler_mark_core_needs_resched(c: global.cores[sched->core_id], true);
249 return ipi_send_try(cpu: sched->core_id, IRQ_SCHEDULER);
250}
251
252enum irql thread_lock_scheduler(struct thread *t, struct scheduler **out_sched)
253 TSA_ACQUIRES_SPIN(&(*out_sched)->lock);
254
255/* Uses the blocking ipi_send(), so no spinlock may be held. */
256static inline void scheduler_force_run_dpcs(cpu_id_t cpu) {
257 ipi_send(cpu, IRQ_DPC);
258}
259
260static inline bool scheduler_preemption_disabled(enum topology_caller c) {
261 return (smp_ctx(c) & SMP_CTX_PREEMPT_MASK) != 0;
262}
263
264void scheduler_change_tick_duration(uint64_t new_duration);
265