1#include <acpi/lapic.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
10#include "internal.h"
11
12/* We will perform scheduler period operations on thread load */
13
14struct scheduler_data scheduler_data = {
15 /* This is how many cores can be stealing work at once */
16 .max_concurrent_stealers = 0,
17
18 /* This is how many cores are attempting a work steal right now.
19 * If this is above the maximum concurrent stealers, we will not
20 * attempt any work steals. */
21 .active_stealers = 0,
22
23 /* total threads in runqueues of all cores */
24 .total_threads = 0,
25
26 /* How much more work the victim must be doing than the stealer
27 * for the stealer to go through with the steal. */
28 .steal_min_diff = SCHEDULER_DEFAULT_WORK_STEAL_MIN_DIFF,
29};
30
31static inline void tick_disable() {
32 struct scheduler *self = smp_core_scheduler();
33 if (scheduler_tick_enabled(sched: self)) {
34 lapic_timer_disable();
35 scheduler_set_tick_enabled(sched: self, false);
36 }
37}
38
39static inline void tick_enable() {
40 struct scheduler *self = smp_core_scheduler();
41 if (!scheduler_tick_enabled(sched: self)) {
42 lapic_timer_enable();
43 scheduler_set_tick_enabled(sched: self, true);
44 }
45}
46
47void scheduler_tick_enable() {
48 tick_enable();
49}
50
51void scheduler_tick_disable() {
52 tick_disable();
53}
54
55static inline void change_tick_duration(uint64_t new_duration) {
56 struct scheduler *self = smp_core_scheduler();
57
58 /* Tick duration is the same */
59 if (self->tick_duration_ms == new_duration && scheduler_tick_enabled(sched: self))
60 return;
61
62 self->tick_duration_ms = new_duration;
63 lapic_timer_set_ms(ms: new_duration);
64 tick_enable();
65}
66
67void scheduler_change_tick_duration(uint64_t new_duration) {
68 change_tick_duration(new_duration);
69}
70
71static inline void update_thread_before_save(struct thread *thread,
72 time_t time) {
73 thread_set_state(t: thread, state: THREAD_STATE_READY);
74 thread_scale_back_delta(thread);
75 thread->curr_core = -1;
76 thread_update_runtime_buckets(thread, time);
77 thread->virtual_runtime_left = thread_virtual_runtime_left(t: thread);
78}
79
80static inline bool thread_done_for_period(struct thread *thread) {
81 return THREAD_PRIO_IS_TIMESHARING(thread->perceived_prio_class) &&
82 thread->virtual_period_runtime >= thread->virtual_budget;
83}
84
85static inline void re_enqueue_thread(struct scheduler *sched,
86 struct thread *thread) {
87 /* Scheduler is locked - called from `schedule()` */
88 if (thread_done_for_period(thread)) {
89 thread->virtual_runtime_left = thread->virtual_budget;
90 thread->completed_period = sched->current_period;
91 retire_thread(sched, thread);
92 scheduler_increment_thread_count(sched, t: thread);
93 } else {
94 bool locked = true;
95 scheduler_add_thread(sched, thread, lock_held: locked);
96 }
97}
98
99static inline void update_idle_thread(time_t time) {
100 struct idle_thread_data *data = smp_core_idle_thread();
101 data->last_exit_ms = time;
102}
103
104static inline void update_min_steal_diff(void) {
105 atomic_store(&scheduler_data.steal_min_diff,
106 scheduler_compute_steal_threshold());
107}
108
109static inline void save_thread(struct scheduler *sched, struct thread *curr,
110 time_t time) {
111 update_min_steal_diff();
112
113 /* Only save a running thread that exists */
114 if (curr && thread_get_state(t: curr) == THREAD_STATE_RUNNING) {
115 update_thread_before_save(thread: curr, time);
116 re_enqueue_thread(sched, thread: curr);
117 } else if (curr && thread_get_state(t: curr) == THREAD_STATE_IDLE_THREAD) {
118 update_idle_thread(time);
119 }
120}
121
122/* returns `true` if the current scheduler lock gets acquired
123 * so the caller knows if it needs to acquire it */
124static inline bool migrate_to_destination(struct thread *t, time_t time) {
125 int64_t dst;
126 if (!t || (dst = thread_set_migration_target(t, new: -1)) == -1)
127 return false;
128
129 if (dst == (int64_t) smp_core_id())
130 return false;
131
132 enum irql irql_us, irql_other;
133 struct scheduler *us = smp_core_scheduler();
134 struct scheduler *other = global.schedulers[dst];
135
136 /* They're both DISPATCH */
137 scheduler_acquire_two_locks(a: us, b: other, a_irql_out: &irql_us, b_irql_out: &irql_other);
138
139 /* mark our own other_locked as `other` so that
140 * upon the switch-in, the lock is dropped */
141 us->other_locked = other;
142
143 /* save ourselves to the other scheduler */
144 save_thread(sched: other, curr: t, time);
145 thread_set_runqueue(t, s: other);
146
147 thread_post_migrate(t, old_cpu: us->core_id, new_cpu: dst);
148 return true;
149}
150
151static struct thread *pick_from_special_queues(struct scheduler *sched,
152 enum thread_prio_class prio) {
153 struct list_head *q = scheduler_get_this_thread_queue(sched, prio);
154 struct list_head *node = list_pop_front_init(head: q);
155 kassert(node);
156
157 return thread_from_rq_list_node(node);
158}
159
160static struct thread *pick_from_regular_queues(struct scheduler *sched,
161 time_t now_ms) {
162 struct thread *next = find_highest_prio(sched);
163 if (next)
164 return next;
165
166 /* Here, we have been unable to find
167 * a thread in the ready queues,
168 * so we shall start a new period and swap
169 * the pointers and find the thread again */
170 swap_queues(sched);
171 scheduler_period_start(s: sched, now_ms);
172 return find_highest_prio(sched);
173}
174
175static struct thread *pick_thread(struct scheduler *sched, time_t now_ms) {
176 uint8_t bitmap = scheduler_get_bitmap(sched);
177 /* Nothing in queues */
178 if (!bitmap)
179 return NULL;
180
181 struct thread *next = NULL;
182
183 enum thread_prio_class prio = available_prio_level_from_bitmap(bitmap);
184
185 if (prio != THREAD_PRIO_CLASS_TIMESHARE) {
186 next = pick_from_special_queues(sched, prio);
187 } else {
188 next = pick_from_regular_queues(sched, now_ms);
189 }
190
191 kassert(next); /* cannot be NULL - if it is the bitmap is lying */
192 scheduler_decrement_thread_count(sched, t: next);
193
194 /* make sure we are not idle */
195 scheduler_mark_self_idle(false);
196
197 return next;
198}
199
200static void load_thread(struct scheduler *sched, struct thread *next,
201 time_t time) {
202 sched->current = next;
203 smp_core()->current_thread = next;
204
205 kassert(next);
206
207 /* Do not mark the idle thread as RUNNING because this causes
208 * it to enter the runqueues, which is Very Bad™ (it gets enqueued,
209 * and becomes treated like a regular thread)! */
210 if (next->state != THREAD_STATE_IDLE_THREAD)
211 thread_set_state(t: next, state: THREAD_STATE_RUNNING);
212
213 thread_set_runqueue(t: next, s: sched);
214 next->curr_core = smp_core_id();
215 next->run_start_time = time;
216
217 thread_calculate_activity_data(t: next);
218 thread_classify_activity(t: next, now_ms: time);
219}
220
221static inline struct thread *load_idle_thread(struct scheduler *sched) {
222
223 /* Idle thread has no need to have a tick
224 * No preemption will be occurring since nothing else runs */
225 tick_disable();
226 disable_period(sched);
227
228 struct idle_thread_data *idle = smp_core_idle_thread();
229
230 atomic_store(&idle->last_entry_ms, time_get_ms());
231
232 scheduler_mark_self_idle(true);
233
234 return sched->idle_thread;
235}
236
237static void change_tick(struct scheduler *sched, struct thread *next) {
238 /* Only one thread is running - no timeslice needed */
239 if (sched->total_thread_count == 0) {
240 /* Disable the scheduling period because
241 * there is no need for period
242 * tracking when we have
243 * one thread running */
244 disable_period(sched);
245 tick_disable();
246 return;
247 }
248
249 if (THREAD_PRIO_HAS_TIMESLICE(next->perceived_prio_class) &&
250 thread_get_state(t: next) != THREAD_STATE_IDLE_THREAD) {
251 /* Timesharing threads need timeslices */
252 change_tick_duration(new_duration: next->timeslice_length_raw_ms);
253 } else if (next->perceived_prio_class == THREAD_PRIO_CLASS_RT) {
254 /* Realtime threads get the tick disabled. Only RT though.
255 * URGENT still needs it so that it can switch out and
256 * run another thread when the boost leaves */
257 tick_disable();
258 }
259}
260
261static inline void context_switch(struct thread *curr, struct thread *next) {
262 if (curr)
263 thread_or_flags(t: curr, flags: THREAD_FLAG_YIELDED);
264
265 if (curr != next)
266 next->context_switches++;
267
268 /* We are responsible for dropping references
269 * on threads entering their last yield */
270 bool just_load = false;
271
272 if (!curr)
273 just_load = true;
274
275 if (curr && curr->state == THREAD_STATE_IDLE_THREAD)
276 just_load = true;
277
278 if (unlikely(curr && curr->state == THREAD_STATE_ZOMBIE)) {
279 just_load = true;
280 kassert(!smp_core_scheduler()->drop_last_ref);
281 smp_core_scheduler()->drop_last_ref = curr;
282 }
283
284 if (just_load) {
285 load_context(new: &next->regs);
286 } else {
287 switch_context(old: &curr->regs, new: &next->regs);
288 }
289}
290
291void schedule(void) {
292 time_t time = time_get_ms();
293
294 struct scheduler *sched = smp_core_scheduler();
295
296 struct thread *curr = sched->current;
297 struct thread *next = NULL;
298
299 /* if this returns false, the thread was not migrated
300 * anywhere and we're responsible for acquiring our lock
301 * and also saving it to our runqueues. if it returns true,
302 * both our lock and the other CPU's locks for schedulers
303 * are acquired (ordered by memory address) and we don't
304 * have to acquire it or save the thread to our CPU since
305 * that happened in migrate_to_destination */
306 if (!migrate_to_destination(t: curr, time)) {
307
308 /* We have to disable interrupts here: why? well,
309 * because if we don't, we can get an IRQ right now,
310 * and in that ISR we can attempt to acquire this lock,
311 * and then we are in a big pickle since we deadlock */
312 enum irql irql = spin_lock_irq_disable(lock: &sched->lock);
313 (void) irql;
314
315 save_thread(sched, curr, time);
316 }
317
318 /* Checks if we can steal, finds a victim, and tries to steal.
319 * NULL is returned if any step was unsuccessful */
320 struct thread *stolen = scheduler_try_do_steal(sched);
321
322 next = stolen ? stolen : pick_thread(sched, now_ms: time);
323
324 if (!next) {
325 /* Nothing available via steal or in our queues? */
326 next = load_idle_thread(sched);
327 } else {
328 /* Depending on what was loaded, we may or may not
329 * need to adjust the timeslice. RT threads do not
330 * have timeslices, so the timeslice needs to be
331 * disabled if an RT thread is chosen to run */
332 change_tick(sched, next);
333 }
334
335 load_thread(sched, next, time);
336
337 context_switch(curr, next);
338}
339
340void scheduler_switch_in() {
341 struct scheduler *us = smp_core_scheduler();
342 struct scheduler *other = us->other_locked;
343 us->other_locked = NULL;
344
345 kassert(us != other);
346
347 if (!other) {
348 /* guaranteed to be the last IRQL, we always
349 * raise there, so it can't be any other */
350 spin_unlock(lock: &us->lock, old: IRQL_DISPATCH_LEVEL);
351 } else {
352 scheduler_release_two_locks(a: us, b: other, a_irql: IRQL_DISPATCH_LEVEL,
353 b_irql: IRQL_DISPATCH_LEVEL);
354 }
355
356 struct thread *drop = us->drop_last_ref;
357 us->drop_last_ref = NULL;
358 if (drop)
359 thread_put(t: drop);
360
361 scheduler_periodic_work_execute(type: PERIODIC_WORK_PERIOD_BASED);
362 vmm_reclaim_page_tables();
363 atomic_store(&smp_core()->pt_seen_epoch, atomic_load(&global.pt_epoch));
364}
365
366void scheduler_yield() {
367 kassert(!scheduler_self_in_resched());
368 kassert(!scheduler_preemption_disabled());
369
370 enum irql irql = irql_raise(new_level: IRQL_DISPATCH_LEVEL);
371 scheduler_mark_self_in_resched(true);
372
373 schedule();
374
375 scheduler_switch_in();
376
377 scheduler_mark_self_in_resched(false);
378
379 irql_lower(old_level: irql);
380}
381