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