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() {
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() {
64 tick_enable();
65}
66
67void scheduler_tick_disable() {
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 || !self->tick_enabled) {
78 self->tick_duration_ms = new_duration;
79 timer_modify(timer: &self->tick, new: timer_delta_us(MS_TO_US(new_duration)));
80 scheduler_set_tick_enabled(sched: self, true);
81 }
82}
83
84void scheduler_change_tick_duration(uint64_t new_duration) {
85 change_tick_duration(new_duration);
86}
87
88static inline void update_thread_before_save(struct thread *thread,
89 time_ms_t time) {
90 thread_set_state(t: thread, state: THREAD_STATE_READY);
91 thread_scale_back_delta(thread);
92 thread->curr_core = -1;
93 thread_update_runtime_buckets(thread, time);
94 thread->virtual_runtime_left = thread_virtual_runtime_left(t: thread);
95}
96
97static inline bool thread_done_for_period(struct thread *thread) {
98 return THREAD_PRIO_IS_TIMESHARING(thread->perceived_prio_class) &&
99 thread->virtual_budget > 0 &&
100 thread->virtual_period_runtime >= thread->virtual_budget;
101}
102
103static inline void re_enqueue_thread(struct scheduler *sched,
104 struct thread *thread) {
105 /* Scheduler is locked - called from `schedule()` */
106 if (thread_done_for_period(thread)) {
107 thread->virtual_runtime_left = thread->virtual_budget;
108 thread->completed_period = sched->current_period;
109 retire_thread(sched, thread);
110 scheduler_increment_thread_count(sched, t: thread);
111 } else {
112 bool locked = true;
113 scheduler_add_thread(sched, thread, lock_held: locked);
114 }
115}
116
117static inline void update_idle_thread(time_ms_t time) {
118 struct idle_thread_data *data = smp_core_idle_thread();
119 data->last_exit_ms = time;
120}
121
122static inline void update_min_steal_diff(void) {
123 atomic_store(&scheduler_data.steal_min_diff,
124 scheduler_compute_steal_threshold());
125}
126
127static inline void save_thread(struct scheduler *sched, struct thread *curr,
128 time_ms_t time) {
129 update_min_steal_diff();
130
131 /* Only save a running thread that exists */
132 if (curr && thread_get_state(t: curr) == THREAD_STATE_RUNNING) {
133 update_thread_before_save(thread: curr, time);
134 re_enqueue_thread(sched, thread: curr);
135 } else if (curr && thread_get_state(t: curr) == THREAD_STATE_IDLE_THREAD) {
136 update_idle_thread(time);
137 }
138}
139
140/* returns `true` if the current scheduler lock gets acquired
141 * so the caller knows if it needs to acquire it */
142static inline bool migrate_to_destination(struct thread *t, time_ms_t time) {
143 int64_t dst;
144 if (!t || (dst = thread_set_migration_target(t, new: -1)) == -1)
145 return false;
146
147 if (dst == (int64_t) smp_id(cond: TOPC_IRQL))
148 return false;
149
150 enum irql irql_us, irql_other;
151 struct scheduler *us = smp_core_scheduler();
152 struct scheduler *other = global.schedulers[dst];
153
154 /* They're both DISPATCH */
155 scheduler_acquire_two_locks(a: us, b: other, a_irql_out: &irql_us, b_irql_out: &irql_other);
156
157 /* mark our own other_locked as `other` so that
158 * upon the switch-in, the lock is dropped */
159 us->other_locked = other;
160
161 /* save ourselves to the other scheduler */
162 save_thread(sched: other, curr: t, time);
163 thread_set_runqueue(t, s: other);
164
165 thread_post_migrate(t, old_cpu: us->core_id, new_cpu: dst);
166 return true;
167}
168
169static struct thread *pick_from_special_queues(struct scheduler *sched,
170 enum thread_prio_class prio) {
171 struct list_head *q = scheduler_get_this_thread_queue(sched, prio);
172 struct list_head *node = list_pop_front_init(head: q);
173 kassert(node);
174
175 return thread_from_rq_list_node(node);
176}
177
178static struct thread *pick_from_regular_queues(struct scheduler *sched,
179 time_ms_t now_ms) {
180 struct thread *next = find_highest_prio(sched);
181 if (next)
182 return next;
183
184 /* Here, we have been unable to find
185 * a thread in the ready queues,
186 * so we shall start a new period and swap
187 * the pointers and find the thread again */
188 swap_queues(sched);
189 scheduler_period_start(s: sched, now_ms);
190 return find_highest_prio(sched);
191}
192
193static struct thread *pick_thread(struct scheduler *sched, time_ms_t now_ms) {
194 uint8_t bitmap = scheduler_get_bitmap(sched);
195 /* Nothing in queues */
196 if (!bitmap)
197 return NULL;
198
199 struct thread *next = NULL;
200
201 enum thread_prio_class prio = available_prio_level_from_bitmap(bitmap);
202
203 if (prio != THREAD_PRIO_CLASS_TIMESHARE) {
204 next = pick_from_special_queues(sched, prio);
205 } else {
206 next = pick_from_regular_queues(sched, now_ms);
207 }
208
209 kassert(next); /* cannot be NULL - if it is the bitmap is lying */
210 scheduler_decrement_thread_count(sched, t: next);
211
212 /* make sure we are not idle */
213 scheduler_mark_self_idle(false);
214
215 return next;
216}
217
218static void load_thread(struct scheduler *sched, struct thread *next,
219 time_ms_t time) {
220 sched->current = next;
221 smp_core(cond: TOPC_IRQL)->current_thread = next;
222
223 kassert(next);
224
225 /* Do not mark the idle thread as RUNNING because this causes
226 * it to enter the runqueues, which is Very Bad™ (it gets enqueued,
227 * and becomes treated like a regular thread)! */
228 if (next->state != THREAD_STATE_IDLE_THREAD)
229 thread_set_state(t: next, state: THREAD_STATE_RUNNING);
230
231 thread_set_runqueue(t: next, s: sched);
232 next->curr_core = smp_id(cond: TOPC_IRQL);
233 next->run_start_time = time;
234
235 thread_calculate_activity_data(t: next);
236 thread_classify_activity(t: next, now_ms: time);
237}
238
239static inline struct thread *load_idle_thread(struct scheduler *sched) {
240
241 /* Idle thread has no need to have a tick
242 * No preemption will be occurring since nothing else runs */
243 tick_disable();
244 disable_period(sched);
245
246 struct idle_thread_data *idle = smp_core_idle_thread();
247
248 atomic_store(&idle->last_entry_ms, time_get_ms());
249
250 scheduler_mark_self_idle(true);
251
252 return sched->idle_thread;
253}
254
255static void change_tick(struct scheduler *sched, struct thread *next) {
256 /* Only one thread is running - no timeslice needed */
257 if (sched->total_thread_count == 0 && sched->completed_rbt.root == NULL) {
258 /* Disable the scheduling period because
259 * there is no need for period
260 * tracking when we have
261 * one thread running */
262 disable_period(sched);
263 tick_disable();
264 return;
265 }
266
267 if (THREAD_PRIO_HAS_TIMESLICE(next->perceived_prio_class) &&
268 thread_get_state(t: next) != THREAD_STATE_IDLE_THREAD) {
269 /* Timesharing threads need timeslices */
270 change_tick_duration(new_duration: next->timeslice_length_raw_ms);
271 } else if (next->perceived_prio_class == THREAD_PRIO_CLASS_RT) {
272 /* Realtime threads get the tick disabled. Only RT though.
273 * URGENT still needs it so that it can switch out and
274 * run another thread when the boost leaves */
275 tick_disable();
276 }
277}
278
279/* Below DISPATCH the IRQL is effectively thread state, and the level
280 * a thread was at uses the kernel stack (irql local variable) across
281 * the switch boundary, being restored on whatever CPU it resumes on */
282static inline void assert_switch_ctx(const char *where) {
283 BOOTSTAGE_IF_LT(BOOTSTAGE_LATE) {
284 return;
285 }
286
287 kassert(irql_get() >= IRQL_DISPATCH_LEVEL, "%s at %s, want >= %s", where,
288 irql_to_str(irql_get()), irql_to_str(IRQL_DISPATCH_LEVEL));
289 kassert(scheduler_preemption_disabled(TOPC_NONE),
290 "%s with preemption enabled", where);
291 kassert(!are_interrupts_enabled(), "%s with interrupts enabled", where);
292}
293
294static inline void context_switch(struct thread *curr, struct thread *next) {
295 assert_switch_ctx(where: "switching out");
296
297 if (curr)
298 thread_or_flags(t: curr, flags: THREAD_FLAG_YIELDED);
299
300 if (curr != next)
301 next->context_switches++;
302
303 /* We are responsible for dropping references
304 * on threads entering their last yield */
305 bool just_load = false;
306
307 if (!curr)
308 just_load = true;
309
310 if (curr && curr->state == THREAD_STATE_IDLE_THREAD)
311 just_load = true;
312
313 if (unlikely(curr && curr->state == THREAD_STATE_ZOMBIE)) {
314 just_load = true;
315 kassert(!smp_core_scheduler()->drop_last_ref);
316 smp_core_scheduler()->drop_last_ref = curr;
317 }
318
319 if (just_load) {
320 load_context(new: &next->regs);
321 } else {
322 switch_context(old: &curr->regs, new: &next->regs);
323
324 assert_switch_ctx(where: "resuming");
325 }
326}
327
328void schedule(void) {
329 time_ms_t time = time_get_ms();
330
331 struct scheduler *sched = smp_core_scheduler();
332
333 struct thread *curr = sched->current;
334 struct thread *next = NULL;
335
336 /* if this returns false, the thread was not migrated
337 * anywhere and we're responsible for acquiring our lock
338 * and also saving it to our runqueues. if it returns true,
339 * both our lock and the other CPU's locks for schedulers
340 * are acquired (ordered by memory address) and we don't
341 * have to acquire it or save the thread to our CPU since
342 * that happened in migrate_to_destination */
343 if (!migrate_to_destination(t: curr, time)) {
344
345 /* We have to disable interrupts here: why? well,
346 * because if we don't, we can get an IRQ right now,
347 * and in that ISR we can attempt to acquire this lock,
348 * and then we are in a big pickle since we deadlock */
349 enum irql irql = spin_lock_irq_disable(&sched->lock);
350 (void) irql;
351
352 save_thread(sched, curr, time);
353 }
354
355 /* Checks if we can steal, finds a victim, and tries to steal.
356 * NULL is returned if any step was unsuccessful */
357 struct thread *stolen = scheduler_try_do_steal(sched);
358
359 next = stolen ? stolen : pick_thread(sched, now_ms: time);
360
361 if (!next) {
362 /* Nothing available via steal or in our queues? */
363 next = load_idle_thread(sched);
364 } else {
365 /* Depending on what was loaded, we may or may not
366 * need to adjust the timeslice. RT threads do not
367 * have timeslices, so the timeslice needs to be
368 * disabled if an RT thread is chosen to run */
369 change_tick(sched, next);
370 }
371
372 /* The last known good point before next becomes current
373 *
374 * Threads still in a read-side critical section
375 * are registered here */
376 rcu_note_context_switch(outgoing: curr, /* next_is_idle = */ next->state ==
377 THREAD_STATE_IDLE_THREAD);
378
379 load_thread(sched, next, time);
380
381 context_switch(curr, next);
382}
383
384void scheduler_switch_in() {
385 struct scheduler *us = smp_core_scheduler();
386 struct scheduler *other = us->other_locked;
387 us->other_locked = NULL;
388
389 kassert(us != other);
390
391 if (!other) {
392 /* guaranteed to be the last IRQL, we always
393 * raise there, so it can't be any other */
394 spin_unlock(&us->lock, IRQL_DISPATCH_LEVEL);
395 } else {
396 scheduler_release_two_locks(a: us, b: other, a_irql: IRQL_DISPATCH_LEVEL,
397 b_irql: IRQL_DISPATCH_LEVEL);
398 }
399
400 struct thread *drop = us->drop_last_ref;
401 us->drop_last_ref = NULL;
402 if (drop)
403 thread_put(t: drop);
404
405 scheduler_periodic_work_execute(type: PERIODIC_WORK_PERIOD_BASED);
406 vmm_reclaim_page_tables();
407 atomic_store(&smp_core(TOPC_IRQL)->pt_seen_epoch,
408 atomic_load(&global.pt_epoch));
409 watchdog_pet();
410}
411
412/* Looping here to prevent unbounded recursion, keeping the max nesting == 1
413 * invariant upheld. Interrupt state stays uniform across
414 * iterations, and in_resched is cleared before the lower so DPCs
415 * have a chance to run */
416static void scheduler_yield_loop(void) {
417 do {
418 enum irql irql = irql_raise(new_level: IRQL_DISPATCH_LEVEL);
419 scheduler_mark_self_in_resched(true);
420
421 schedule();
422
423 scheduler_switch_in();
424
425 kassert(irql == IRQL_NONE || irql_get() == IRQL_DISPATCH_LEVEL,
426 "resumed at %s, want %s", irql_to_str(irql_get()),
427 irql_to_str(IRQL_DISPATCH_LEVEL));
428
429 scheduler_mark_self_in_resched(false);
430
431 irql_lower_no_resched(old_level: irql);
432
433 /* we store irql on the stack here, i.e. T1 entering the routine
434 * will "pop out" on the switch_in path on T2, and irql will
435 * be T2's entry value, which should match the current state */
436 kassert(irql == IRQL_NONE || irql_get() == irql,
437 "resumed at %s, entered at %s", irql_to_str(irql_get()),
438 irql_to_str(irql));
439 } while (scheduler_mark_self_needs_resched(false));
440}
441
442void scheduler_yield(void) {
443 struct core *c = smp_core(cond: TOPC_NONE);
444 bool entry_in_resched = atomic_load(&c->in_resched);
445 uint32_t entry_depth = smp_ctx_preempt_count(smp_ctx: c->ctx);
446 cpu_id_t entry_cpu = c->id;
447 kassert(!entry_in_resched, "yielding while already in resched on cpu %zu",
448 (size_t) entry_cpu);
449 kassert(entry_depth == 0, "yielding on cpu %zu with preempt depth %u",
450 (size_t) entry_cpu, entry_depth);
451
452 struct thread *self = thread_get_current();
453
454 /* Kernel APCs get deferred, since apc_check_and_deliver() raises
455 * to APC and lowers to PASSIVE, it can cause a reschedule over and over,
456 * but we leave the other APCs alone */
457 if (self)
458 apc_disable_kernel();
459
460 scheduler_yield_nesting_enter(t: self);
461
462 scheduler_lock_chk_assert();
463 scheduler_yield_loop();
464
465 /* It did the matching enter already, so we exit here */
466 scheduler_yield_nesting_exit(t: self);
467
468 if (self)
469 apc_enable_kernel();
470}
471