1#include <bootstage_condition.h>
2#include <mem/vmm.h>
3#include <sch/periodic_work.h>
4#include <sch/sched.h>
5#include <smp/smp.h>
6#include <sync/rcu.h>
7#include <thread/apc.h>
8#include <thread/reaper.h>
9#include <watchdog.h>
10
11#include "internal.h"
12
13#ifdef DEBUG_LOCK_CHK
14
15#include "sync/lock_chk/internal.h"
16
17static void scheduler_lock_chk_assert(void) {
18 lock_chk_assert_schedulable(LOCK_CHK_SITE_HERE());
19}
20
21#else
22
23static void scheduler_lock_chk_assert(void) {}
24
25#endif
26
27/* We will perform scheduler period operations on thread load */
28
29struct scheduler_data scheduler_data = {
30 /* This is how many cores can be stealing work at once */
31 .max_concurrent_stealers = 0,
32
33 /* This is how many cores are attempting a work steal right now.
34 * If this is above the maximum concurrent stealers, we will not
35 * attempt any work steals. */
36 .active_stealers = 0,
37
38 /* total threads in runqueues of all cores */
39 .total_threads = 0,
40
41 /* How much more work the victim must be doing than the stealer
42 * for the stealer to go through with the steal. */
43 .steal_min_diff = SCHEDULER_DEFAULT_WORK_STEAL_MIN_DIFF,
44};
45
46static inline void tick_disable(void) {
47 struct scheduler *self = smp_core_scheduler();
48 if (scheduler_tick_enabled(sched: self)) {
49 timer_delete(timer: &self->tick);
50 scheduler_set_tick_enabled(sched: self, false);
51 }
52}
53
54static inline void tick_enable(void) {
55 struct scheduler *self = smp_core_scheduler();
56 if (!scheduler_tick_enabled(sched: self)) {
57 timer_modify(timer: &self->tick,
58 new: timer_delta_us(MS_TO_US(self->tick_duration_ms)));
59 scheduler_set_tick_enabled(sched: self, true);
60 }
61}
62
63void scheduler_tick_enable(void) {
64 tick_enable();
65}
66
67void scheduler_tick_disable(void) {
68 tick_disable();
69}
70
71static inline void change_tick_duration(time_ms_t new_duration) {
72 struct scheduler *self = smp_core_scheduler();
73
74 if (new_duration < 1)
75 new_duration = 3;
76
77 if (self->tick_duration_ms != new_duration ||
78 !atomic_load_rlx(&self->tick_enabled)) {
79 self->tick_duration_ms = new_duration;
80 timer_modify(timer: &self->tick, new: timer_delta_us(MS_TO_US(new_duration)));
81 scheduler_set_tick_enabled(sched: self, true);
82 }
83}
84
85void scheduler_change_tick_duration(uint64_t new_duration) {
86 change_tick_duration(new_duration);
87}
88
89static inline void update_thread_before_save(struct thread *thread,
90 time_ms_t time) {
91 thread_set_state(t: thread, state: THREAD_STATE_READY);
92 thread_scale_back_delta(thread);
93 thread->curr_core = -1;
94 thread_update_runtime_buckets(thread, time);
95 thread->virtual_runtime_left = thread_virtual_runtime_left(t: thread);
96}
97
98static inline bool thread_done_for_period(struct thread *thread) {
99 return thread->perceived_prio_class == THREAD_PRIO_CLASS_TIMESHARE &&
100 thread->virtual_budget > 0 &&
101 thread->virtual_period_runtime >= thread->virtual_budget;
102}
103
104static inline void re_enqueue_thread(struct scheduler *sched,
105 struct thread *thread) TSA_NO_ANALYSIS {
106 /* Scheduler is locked - called from `schedule()` */
107 if (thread_done_for_period(thread)) {
108 thread->virtual_runtime_left = thread->virtual_budget;
109 thread->completed_period = sched->current_period;
110 /* thread_done_for_period() already established it as timesharing */
111 thread->perceived_prio_class = THREAD_PRIO_CLASS_TIMESHARE;
112 retire_thread(sched, thread);
113 scheduler_increment_thread_count(sched, t: thread);
114 scheduler_debug_validate(sched);
115 } else {
116 scheduler_add_thread_locked(sched, thread);
117 }
118}
119
120static inline void update_idle_thread(time_ms_t time) {
121 struct idle_thread_data *data = smp_core_idle_thread();
122 data->last_exit_ms = time;
123}
124
125static inline void update_min_steal_diff(void) {
126 atomic_store(&scheduler_data.steal_min_diff,
127 scheduler_compute_steal_threshold());
128}
129
130static inline void save_thread(struct scheduler *sched, struct thread *curr,
131 time_ms_t time) TSA_NO_ANALYSIS {
132 update_min_steal_diff();
133
134 /* Only save a running thread that exists */
135 if (curr && thread_get_state(t: curr) == THREAD_STATE_RUNNING) {
136 update_thread_before_save(thread: curr, time);
137 re_enqueue_thread(sched, thread: curr);
138 } else if (curr && thread_get_state(t: curr) == THREAD_STATE_IDLE_THREAD) {
139 update_idle_thread(time);
140 }
141}
142
143/* returns `true` if the current scheduler lock gets acquired
144 * so the caller knows if it needs to acquire it */
145static inline bool migrate_to_destination(struct thread *t, time_ms_t time) {
146 int64_t dst;
147 if (!t || (dst = thread_set_migration_target(t, new: -1)) == -1)
148 return false;
149
150 if (dst == (int64_t) smp_id(cond: TOPC_IRQL))
151 return false;
152
153 enum irql irql_us, irql_other;
154 struct scheduler *us = smp_core_scheduler();
155 struct scheduler *other = global.schedulers[dst];
156
157 scheduler_acquire_two_locks(a: us, b: other, a_irql_out: &irql_us, b_irql_out: &irql_other);
158
159 /* mark our own other_locked as `other` so that
160 * upon the switch-in, the lock is dropped */
161 us->other_locked = other;
162 us->locked_irql = irql_us;
163 us->other_locked_irql = irql_other;
164
165 /* save ourselves to the other scheduler */
166 save_thread(sched: other, curr: t, time);
167 thread_set_runqueue(t, s: other);
168
169 /* An idle destination sits in a tickless hlt and won't look at its
170 * runqueue until its next interrupt, gotta go bother it */
171 scheduler_defer_resched(target: other);
172
173 thread_post_migrate(t, old_cpu: us->core_id, new_cpu: dst);
174 return true;
175}
176
177static struct thread *pick_from_special_queues(struct scheduler *sched,
178 enum thread_prio_class prio) {
179 struct list_head *q = scheduler_get_this_thread_queue(sched, prio);
180 struct list_node *node = list_head_pop_front_init(h: q);
181 enforce(node);
182
183 return thread_from_rq_list_node(node);
184}
185
186static struct thread *pick_from_regular_queues(struct scheduler *sched,
187 time_ms_t now_ms) {
188 struct thread *next = find_highest_prio(sched);
189 if (next)
190 return next;
191
192 /* Here, we have been unable to find
193 * a thread in the ready queues,
194 * so we shall start a new period and swap
195 * the pointers and find the thread again */
196 swap_queues(sched);
197 scheduler_period_start(s: sched, now_ms);
198 return find_highest_prio(sched);
199}
200
201static struct thread *pick_thread(struct scheduler *sched, time_ms_t now_ms) {
202 uint8_t bitmap = scheduler_get_bitmap(sched);
203 /* Nothing in queues */
204 if (!bitmap)
205 return NULL;
206
207 struct thread *next = NULL;
208
209 enum thread_prio_class prio = available_prio_level_from_bitmap(bitmap);
210
211 if (prio != THREAD_PRIO_CLASS_TIMESHARE) {
212 next = pick_from_special_queues(sched, prio);
213 } else {
214 next = pick_from_regular_queues(sched, now_ms);
215 }
216
217 enforce(next); /* cannot be NULL - if it is the bitmap is lying */
218 enforce(next->perceived_prio_class == prio,
219 "picked a %d thread off the %d queue",
220 (int) next->perceived_prio_class, (int) prio);
221 scheduler_decrement_thread_count(sched, t: next);
222 scheduler_debug_note_progress(sched);
223 scheduler_debug_validate(sched);
224
225 /* make sure we are not idle */
226 scheduler_mark_self_idle(false);
227
228 return next;
229}
230
231static void load_thread(struct scheduler *sched, struct thread *next,
232 time_ms_t time) {
233 sched->current = next;
234 smp_core(cond: TOPC_IRQL)->current_thread = next;
235
236 enforce(next);
237
238 /* Do not mark the idle thread as RUNNING because this causes
239 * it to enter the runqueues, which is Very Bad™ (it gets enqueued,
240 * and becomes treated like a regular thread)! */
241 if (atomic_load_rlx(&next->state) != THREAD_STATE_IDLE_THREAD)
242 thread_set_state(t: next, state: THREAD_STATE_RUNNING);
243
244 thread_set_runqueue(t: next, s: sched);
245 next->curr_core = smp_id(cond: TOPC_IRQL);
246 next->run_start_time = time;
247
248 thread_calculate_activity_data(t: next);
249 thread_classify_activity(t: next, now_ms: time);
250}
251
252static inline struct thread *load_idle_thread(struct scheduler *sched) {
253
254 /* Idle thread has no need to have a tick
255 * No preemption will be occurring since nothing else runs */
256 tick_disable();
257 disable_period(sched);
258
259 struct idle_thread_data *idle = smp_core_idle_thread();
260
261 atomic_store_rlx(&idle->last_entry_ms, time_get_ms());
262
263 scheduler_mark_self_idle(true);
264
265 return sched->idle_thread;
266}
267
268static void change_tick(struct scheduler *sched, struct thread *next) {
269 /* Only one thread is running - no timeslice needed */
270 if (sched->total_thread_count == 0 && sched->completed_rbt.root == NULL) {
271 /* Disable the scheduling period because
272 * there is no need for period
273 * tracking when we have
274 * one thread running */
275 disable_period(sched);
276 tick_disable();
277 return;
278 }
279
280 if (THREAD_PRIO_HAS_TIMESLICE(next->perceived_prio_class) &&
281 thread_get_state(t: next) != THREAD_STATE_IDLE_THREAD) {
282 /* Timesharing threads need timeslices */
283 change_tick_duration(new_duration: next->timeslice_length_raw_ms);
284 } else if (next->perceived_prio_class == THREAD_PRIO_CLASS_REALTIME) {
285 /* Realtime threads get the tick disabled. Only RT though.
286 * URGENT still needs it so that it can switch out and
287 * run another thread when the boost leaves */
288 tick_disable();
289 }
290}
291
292/* Below DISPATCH the IRQL is effectively thread state, and the level
293 * a thread was at uses the kernel stack (irql local variable) across
294 * the switch boundary, being restored on whatever CPU it resumes on */
295static inline void assert_switch_ctx(const char *where) {
296 BOOTSTAGE_IF_LT(BOOTSTAGE_LATE) {
297 return;
298 }
299
300 enforce(irql_get() >= IRQL_DISPATCH_LEVEL, INVALID_CONTEXT,
301 "%s at %s, want >= %s", where, irql_to_str(irql_get()),
302 irql_to_str(IRQL_DISPATCH_LEVEL));
303 enforce(scheduler_preemption_disabled(TOPC_NONE), INVALID_CONTEXT,
304 "%s with preemption enabled", where);
305 enforce(!irqs_enabled(), INVALID_CONTEXT, "%s with interrupts enabled",
306 where);
307}
308
309static inline void context_switch(struct thread *curr, struct thread *next) {
310 assert_switch_ctx(where: "switching out");
311
312 if (curr)
313 thread_or_flags(t: curr, flags: THREAD_FLAG_YIELDED);
314
315#ifdef DEBUG_THREAD
316 if (curr != next)
317 next->context_switches++;
318#endif
319
320 /* We are responsible for dropping references
321 * on threads entering their last yield */
322 bool just_load = false;
323
324 if (!curr)
325 just_load = true;
326
327 if (curr && atomic_load_rlx(&curr->state) == THREAD_STATE_IDLE_THREAD)
328 just_load = true;
329
330 if (cc_unlikely(curr &&
331 atomic_load_rlx(&curr->state) == THREAD_STATE_ZOMBIE)) {
332 just_load = true;
333 enforce(!smp_core_scheduler()->drop_last_ref);
334 smp_core_scheduler()->drop_last_ref = curr;
335 }
336
337 if (just_load) {
338 load_context(new: &next->regs);
339 } else {
340 switch_context(old: &curr->regs, new: &next->regs);
341
342 assert_switch_ctx(where: "resuming");
343 }
344}
345
346void schedule(void) TSA_NO_ANALYSIS {
347 time_ms_t time = time_get_ms();
348
349 struct scheduler *sched = smp_core_scheduler();
350
351 struct thread *curr = sched->current;
352 struct thread *next = NULL;
353
354 enum irql wirql = spin_lock_high(&sched->wroost_lock);
355 enum irql sirql = spin_lock_high(&sched->lock);
356
357 wroost_switch_out(t: curr);
358
359 spin_unlock(&sched->lock, sirql);
360 spin_unlock(&sched->wroost_lock, wirql);
361
362 /* if this returns false, the thread was not migrated
363 * anywhere and we're responsible for acquiring our lock
364 * and also saving it to our runqueues. if it returns true,
365 * both our lock and the other CPU's locks for schedulers
366 * are acquired (ordered by memory address) and we don't
367 * have to acquire it or save the thread to our CPU since
368 * that happened in migrate_to_destination */
369 if (!migrate_to_destination(t: curr, time)) {
370
371 /* We have to disable interrupts here: why? well,
372 * because if we don't, we can get an IRQ right now,
373 * and in that ISR we can attempt to acquire this lock,
374 * and then we are in a big pickle since we deadlock */
375 enum irql irql = spin_lock_high(&sched->lock);
376 cc_ignore(irql);
377
378 save_thread(sched, curr, time);
379 }
380
381 /* Checks if we can steal, finds a victim, and tries to steal.
382 * NULL is returned if any step was unsuccessful */
383 struct thread *stolen = scheduler_try_do_steal(sched);
384
385 next = stolen ? stolen : pick_thread(sched, now_ms: time);
386
387 if (!next) {
388 /* Nothing available via steal or in our queues? */
389 next = load_idle_thread(sched);
390 } else {
391 /* Depending on what was loaded, we may or may not
392 * need to adjust the timeslice. RT threads do not
393 * have timeslices, so the timeslice needs to be
394 * disabled if an RT thread is chosen to run */
395 change_tick(sched, next);
396 }
397
398 /* The last known good point before next becomes current
399 *
400 * Threads still in a read-side critical section
401 * are registered here */
402 rcu_note_context_switch(outgoing: curr);
403
404 load_thread(sched, next, time);
405
406 context_switch(curr, next);
407}
408
409void scheduler_switch_in(void) TSA_NO_ANALYSIS {
410 struct scheduler *us = smp_core_scheduler();
411 struct scheduler *other = us->other_locked;
412 struct thread *curr = thread_get_current();
413 us->other_locked = NULL;
414
415 enforce(us != other);
416
417 if (!other) {
418 /* guaranteed to be the last IRQL, we always
419 * raise there, so it can't be any other */
420 spin_unlock(&us->lock, IRQL_DISPATCH_LEVEL);
421 } else {
422 scheduler_release_two_locks(a: us, b: other, a_irql: us->locked_irql,
423 b_irql: us->other_locked_irql);
424 }
425
426 /* Once the locks are dropped, we need to go bother
427 * all deferred reschedule requests since it's
428 * safe to do so (preemption would be disabled still)
429 *
430 * We actually can't enforce(irql_get() == IRQL_DISPATCH_LEVEL) because
431 * early reschedules before IRQL availability would report NONE, but it's
432 * pretty easy to see that any code calling this would be at DISPATCH */
433 cpu_id_t i;
434 cpu_mask_for_each(i, us->deferred_resched_mask)
435 scheduler_force_resched(sched: global.schedulers[i]);
436
437 enum irql wirql = spin_lock_high(&us->wroost_lock);
438 enum irql sirql = spin_lock_high(&us->lock);
439
440 /* PERF: If this reader was stolen, that's fine, since the post migration
441 * hook would run and add it to our CPU, but it's rather redundant
442 * to add a thread and immediately remove it from wroost_percpu_data */
443 wroost_switch_in(t: curr);
444
445 spin_unlock(&us->lock, sirql);
446 spin_unlock(&us->wroost_lock, wirql);
447
448 wroost_scheduler_switch_in_hook();
449
450 cpu_mask_clear_all(m: &us->deferred_resched_mask);
451
452 struct thread *drop = us->drop_last_ref;
453 us->drop_last_ref = NULL;
454 if (drop)
455 thread_putref(t: drop);
456
457 scheduler_periodic_work_execute(type: PERIODIC_WORK_PERIOD_BASED);
458 vmm_reclaim_page_tables();
459 atomic_store(&smp_core(TOPC_IRQL)->pt_seen_epoch,
460 atomic_load(&global.pt_epoch));
461 watchdog_pet();
462}
463
464/* Looping here to prevent unbounded recursion, keeping the max nesting == 1
465 * invariant upheld. Interrupt state stays uniform across
466 * iterations, and in_resched is cleared before the lower so DPCs
467 * have a chance to run */
468static void scheduler_yield_loop(void) {
469 do {
470 enum irql irql = irql_raise(new_level: IRQL_DISPATCH_LEVEL);
471 scheduler_mark_self_in_resched(true);
472
473 schedule();
474
475 scheduler_switch_in();
476
477 enforce(irql == IRQL_NONE || irql_get() == IRQL_DISPATCH_LEVEL,
478 INVALID_CONTEXT, "resumed at %s, want %s",
479 irql_to_str(irql_get()), irql_to_str(IRQL_DISPATCH_LEVEL));
480
481 scheduler_mark_self_in_resched(false);
482
483 irql_lower_no_resched(old_level: irql);
484
485 /* we store irql on the stack here, i.e. T1 entering the routine
486 * will "pop out" on the switch_in path on T2, and irql will
487 * be T2's entry value, which should match the current state */
488 enforce(irql == IRQL_NONE || irql_get() == irql, INVALID_CONTEXT,
489 "resumed at %s, entered at %s", irql_to_str(irql_get()),
490 irql_to_str(irql));
491 } while (scheduler_mark_self_needs_resched(false));
492}
493
494void scheduler_yield(void) {
495 struct core *c = smp_core(cond: TOPC_NONE);
496 bool entry_in_resched = atomic_load(&c->in_resched);
497 uint32_t entry_depth = smp_ctx_preempt_count(smp_ctx: c->ctx);
498 cpu_id_t entry_cpu = c->id;
499
500 if (cc_likely(entry_cpu == smp_core(TOPC_NONE)->id)) {
501 enforce(!entry_in_resched, INVALID_CONTEXT,
502 "yielding while already in resched on cpu %zu",
503 (size_t) entry_cpu);
504 enforce(entry_depth == 0, INVALID_CONTEXT,
505 "yielding on cpu %zu with preempt depth %u", (size_t) entry_cpu,
506 entry_depth);
507 }
508
509 struct thread *self = thread_get_current();
510
511 /* Kernel APCs get deferred, since apc_check_and_deliver() raises
512 * to APC and lowers to PASSIVE, it can cause a reschedule over and over,
513 * but we leave the other APCs alone */
514 if (self)
515 apc_disable_kernel();
516
517 scheduler_yield_nesting_enter(t: self);
518
519 scheduler_lock_chk_assert();
520 scheduler_yield_loop();
521
522 /* It did the matching enter already, so we exit here */
523 scheduler_yield_nesting_exit(t: self);
524
525 if (self)
526 apc_enable_kernel();
527}
528