1/* @title: Scheduler */
2#pragma once
3#include <acpi/lapic.h>
4#include <global.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
14#define WORK_STEAL_THRESHOLD \
15 75ULL /* How little work the core needs to be \
16 * doing to try to steal work from another \
17 * core. This means "% of the average" \
18 */
19
20#define SCHEDULER_DEFAULT_WORK_STEAL_MIN_DIFF 130
21
22struct idle_thread_data {
23 _Atomic uint64_t last_entry_ms;
24 uint64_t last_exit_ms;
25};
26
27struct scheduler {
28 /* Current tick data */
29 atomic_bool tick_enabled;
30 time_t tick_duration_ms;
31
32 /* Structures */
33 struct list_head urgent_threads;
34
35 struct rbt thread_rbt;
36 struct rbt completed_rbt;
37
38 struct list_head rt_threads;
39 struct list_head bg_threads;
40
41 struct rbt climb_threads; /* threads on this CPU participating in CLIMB */
42
43 _Atomic uint8_t queue_bitmap;
44
45 struct thread *current;
46 struct thread *drop_last_ref;
47
48 /* Thread count at each prio */
49 size_t thread_count[THREAD_PRIO_CLASS_COUNT];
50 size_t total_thread_count;
51 size_t total_weight;
52
53 /* Period information */
54 bool period_enabled;
55 uint64_t current_period;
56
57 time_t period_ms;
58 time_t period_start_ms; /* Timestamp */
59
60#ifdef PROFILING_SCHED
61 size_t periods_started; /* How many have we started?
62 * (Each one must complete) */
63
64 size_t idle_thread_loads;
65#endif
66
67 uint64_t core_id;
68
69 /* TODO: Rework time load balancing away from this foolery */
70
71 /* Work steal/migration */
72 atomic_bool being_robbed;
73 atomic_bool stealing_work;
74
75 struct spinlock lock;
76
77 /* Idle thread data */
78 struct thread *idle_thread;
79 struct idle_thread_data idle_thread_data;
80
81 struct scheduler *other_locked; /* If we acquired the lock of another
82 * scheduler in scheduler_yield(),
83 * we store a pointer to it here.
84 *
85 * If this is NULL, we didn't do that,
86 * but in the case that it isn't, we must
87 * drop the raw lock for this in addition
88 * to the lock for our scheduler */
89
90 struct rt_scheduler_percpu *rt;
91};
92
93void scheduler_init();
94
95struct scheduler *scheduler_select_best_for_thread(struct thread *t);
96void scheduler_add_thread(struct scheduler *sched, struct thread *thread,
97 bool lock_held);
98void scheduler_remove_thread(struct scheduler *sched, struct thread *t,
99 bool lock_held);
100void schedule(void);
101void k_sch_main(void *);
102void scheduler_idle_main(void *);
103void scheduler_yield();
104
105void scheduler_period_start(struct scheduler *s, uint64_t now_ms);
106
107void switch_context(struct cpu_context *old, struct cpu_context *new);
108void load_context(struct cpu_context *new);
109void save_context(struct cpu_context *new);
110
111bool scheduler_can_steal_work(struct scheduler *sched);
112bool scheduler_can_take_thread(size_t core, struct thread *target);
113uint64_t scheduler_compute_steal_threshold();
114struct thread *scheduler_try_do_steal(struct scheduler *sched);
115
116struct scheduler *scheduler_pick_victim(struct scheduler *self);
117struct thread *scheduler_steal_work(struct scheduler *new,
118 struct scheduler *victim);
119
120size_t scheduler_try_push_to_idle_core(struct scheduler *sched);
121
122void scheduler_tick_enable();
123void scheduler_tick_disable();
124enum irq_result scheduler_timer_isr(void *ctx, uint8_t vector,
125 struct irq_context *rsp);
126
127/* For a global structure containing central scheduler data */
128struct scheduler_data {
129 uint32_t max_concurrent_stealers;
130 _Atomic uint32_t active_stealers;
131 _Atomic uint32_t total_threads;
132 _Atomic int64_t steal_min_diff;
133};
134
135extern struct scheduler_data scheduler_data;
136
137static inline bool scheduler_self_in_resched() {
138 return atomic_load(&smp_core()->in_resched);
139}
140
141static inline bool scheduler_mark_self_in_resched(bool new) {
142 return atomic_exchange(&smp_core()->in_resched, new);
143}
144
145#define TICKS_FOR_PRIO(level) (level == THREAD_PRIO_LOW ? 64 : 1ULL << level)
146
147static inline bool scheduler_mark_core_needs_resched(struct core *c, bool new) {
148 return atomic_exchange(&c->needs_resched, new);
149}
150
151static inline bool scheduler_mark_self_needs_resched(bool new) {
152 return scheduler_mark_core_needs_resched(c: smp_core(), new);
153}
154
155static inline bool scheduler_self_needs_resched(void) {
156 return atomic_load(&smp_core()->needs_resched);
157}
158
159/* this is only ever called when a thread is loaded */
160static inline void scheduler_mark_self_idle(bool new) {
161 /* the old value is different from the new one */
162 struct core *c = smp_core();
163
164 if (c->idle != new) {
165 c->idle = new;
166 topology_mark_core_idle(cpu_id: c->id, idle: new);
167 scheduler_domain_mark_self_idle(idle: new);
168 if (new) {
169 atomic_fetch_add_explicit(&global.idle_core_count, 1,
170 memory_order_acq_rel);
171 } else {
172 atomic_fetch_sub_explicit(&global.idle_core_count, 1,
173 memory_order_acq_rel);
174 }
175
176 /* set the DPC event. once we exit the yield(),
177 * we will run DPCs that correspond to the status of
178 * IDLE/WOKE, and then unset the status */
179 c->dpc_event = new ? DPC_CPU_IDLE : DPC_CPU_WOKE;
180 }
181}
182
183static inline void scheduler_resched_if_needed(void) {
184 if (scheduler_self_in_resched())
185 return;
186
187 if (scheduler_mark_self_needs_resched(false)) {
188 scheduler_yield();
189 }
190}
191
192static inline bool scheduler_core_idle(struct core *c) {
193 return atomic_load(&c->idle);
194}
195
196static inline void scheduler_force_resched(struct scheduler *sched) {
197 if (sched->core_id == smp_core_id()) {
198 scheduler_mark_self_needs_resched(true);
199 } else {
200 struct core *other = global.cores[sched->core_id];
201 if (!other) {
202 ipi_send(apic_id: sched->core_id, IRQ_SCHEDULER);
203 return;
204 }
205
206 scheduler_mark_core_needs_resched(c: other, true);
207 ipi_send(apic_id: sched->core_id, IRQ_SCHEDULER);
208 }
209}
210
211static inline bool scheduler_preemption_disabled(void) {
212 return smp_core()->preempt_disable_depth > 0;
213}
214