1#include <compiler/core.h>
2#include <compiler/intrinsic.h>
3#include <enforce.h>
4#include <math/bit.h>
5#include <math/min_max.h>
6#include <sch/sched.h>
7#include <thread/apc.h>
8#include <thread/thread.h>
9#include <time/time.h>
10
11static inline void scheduler_set_queue_bitmap(struct scheduler *sched,
12 uint8_t prio) {
13 uint8_t mask = 0;
14 mask = BIT_SET(mask, prio);
15 atomic_fetch_or(&sched->queue_bitmap, mask);
16}
17
18static inline void scheduler_clear_queue_bitmap(struct scheduler *sched,
19 uint8_t prio) {
20 uint8_t mask = UINT8_MAX;
21 mask = BIT_CLEAR(mask, prio);
22 atomic_fetch_and(&sched->queue_bitmap, mask);
23}
24
25static inline uint8_t scheduler_get_bitmap(struct scheduler *sched) {
26 return atomic_load(&sched->queue_bitmap);
27}
28
29static inline struct scheduler *smp_core_scheduler(void) {
30 return global.schedulers[smp_id(cond: TOPC_IRQL)];
31}
32
33static inline struct idle_thread_data *smp_core_idle_thread(void) {
34 return &smp_core_scheduler()->idle_thread_data;
35}
36
37static inline bool thread_exhausted_period(struct scheduler *sched,
38 struct thread *thread) {
39 return thread->completed_period == sched->current_period;
40}
41
42#ifdef DEBUG_SCHED
43void scheduler_debug_validate(struct scheduler *sched);
44
45static inline void scheduler_debug_note_progress(struct scheduler *sched) {
46 atomic_store_rlx(&sched->debug_progress_ms, (uint64_t) time_get_ms());
47}
48#else
49static inline void scheduler_debug_validate(struct scheduler *sched) {
50 cc_ignore(sched);
51}
52
53static inline void scheduler_debug_note_progress(struct scheduler *sched) {
54 cc_ignore(sched);
55}
56#endif
57
58static inline void scheduler_decrement_thread_count(struct scheduler *sched,
59 struct thread *t) {
60 sched->total_thread_count--;
61 sched->thread_count[t->perceived_prio_class]--;
62
63 if (sched->thread_count[t->perceived_prio_class] == 0)
64 scheduler_clear_queue_bitmap(sched, prio: t->perceived_prio_class);
65
66 if (t->perceived_prio_class == THREAD_PRIO_CLASS_TIMESHARE)
67 sched->total_weight -= t->weight;
68
69 atomic_dec(&scheduler_data.total_threads);
70}
71
72static inline void scheduler_increment_thread_count(struct scheduler *sched,
73 struct thread *t) {
74 if (sched->total_thread_count++ == 0)
75 scheduler_debug_note_progress(sched);
76
77 sched->thread_count[t->perceived_prio_class]++;
78 scheduler_set_queue_bitmap(sched, prio: t->perceived_prio_class);
79
80 if (t->perceived_prio_class == THREAD_PRIO_CLASS_TIMESHARE)
81 sched->total_weight += t->weight;
82
83 atomic_inc(&scheduler_data.total_threads);
84}
85
86static inline size_t scheduler_get_thread_count(struct scheduler *sched,
87 enum thread_prio_class prio) {
88 return sched->thread_count[prio];
89}
90
91static inline struct list_head *
92scheduler_get_this_thread_queue(struct scheduler *sched,
93 enum thread_prio_class prio) {
94 switch (prio) {
95 case THREAD_PRIO_CLASS_URGENT: return &sched->urgent_threads;
96 case THREAD_PRIO_CLASS_REALTIME: return &sched->rt_threads;
97 case THREAD_PRIO_CLASS_TIMESHARE: return NULL; /* Use the tree */
98 case THREAD_PRIO_CLASS_BACKGROUND: return &sched->bg_threads;
99 }
100 unreachable("invalid thread_prio_class");
101}
102
103static inline void enqueue_to_tree(struct scheduler *sched,
104 struct thread *thread) {
105 rbt_insert(tree: &sched->thread_rbt, new_node: &thread->rq_tree_node);
106}
107
108static inline void retire_thread(struct scheduler *sched,
109 struct thread *thread) {
110 rbt_insert(tree: &sched->completed_rbt, new_node: &thread->rq_tree_node);
111}
112
113static inline void dequeue_from_tree(struct scheduler *sched,
114 struct thread *thread) {
115 if (rbt_has_node(tree: &sched->completed_rbt, node: &thread->rq_tree_node))
116 return rbt_delete(tree: &sched->completed_rbt, z: &thread->rq_tree_node);
117
118 rbt_delete(tree: &sched->thread_rbt, z: &thread->rq_tree_node);
119}
120
121/* The `thread_rbt` should be NULL here */
122static inline void swap_queues(struct scheduler *sched) {
123 enforce(sched->thread_rbt.root == NULL);
124 sched->thread_rbt.root = sched->completed_rbt.root;
125 sched->completed_rbt.root = NULL;
126}
127
128static inline bool scheduler_ts_empty(struct scheduler *sched) {
129 return sched->thread_rbt.root == NULL && sched->completed_rbt.root == NULL;
130}
131
132static inline enum thread_prio_class
133available_prio_level_from_bitmap(uint8_t bitmap) {
134 return 31 - ci_clz((uint32_t) bitmap);
135}
136
137static inline struct thread *find_highest_prio(struct scheduler *sched) {
138 struct rbt_node *node = rbt_max(tree: &sched->thread_rbt);
139 if (!node)
140 return NULL;
141
142 rbt_delete(tree: &sched->thread_rbt, z: node);
143
144 return thread_from_rq_rbt_node(node);
145}
146
147/* Don't touch `current_period` here */
148static inline void disable_period(struct scheduler *sched) {
149 sched->period_enabled = false;
150 sched->period_ms = 0;
151 sched->period_start_ms = 0;
152}
153
154static inline bool scheduler_tick_enabled(struct scheduler *sched) {
155 return atomic_load(&sched->tick_enabled);
156}
157
158static inline bool scheduler_set_tick_enabled(struct scheduler *sched,
159 bool new) {
160 return atomic_exchange(&sched->tick_enabled, new);
161}
162
163static inline const char *thread_state_str(const enum thread_state state) {
164 switch (state) {
165 case THREAD_STATE_IDLE_THREAD: return "IDLE THREAD";
166 case THREAD_STATE_READY: return "READY";
167 case THREAD_STATE_RUNNING: return "RUNNING";
168 case THREAD_STATE_BLOCKED: return "BLOCKED";
169 case THREAD_STATE_SLEEPING: return "SLEEPING";
170 case THREAD_STATE_ZOMBIE: return "ZOMBIE";
171 case THREAD_STATE_TERMINATED: return "TERMINATED";
172 case THREAD_STATE_HALTED: return "HALTED";
173 }
174 unreachable("invalid thread state");
175}
176
177static inline const char *
178thread_activity_class_str(enum thread_activity_class c) {
179 switch (c) {
180 case THREAD_ACTIVITY_CLASS_CPU_BOUND: return "CPU BOUND";
181 case THREAD_ACTIVITY_CLASS_IO_BOUND: return "IO BOUND";
182 case THREAD_ACTIVITY_CLASS_INTERACTIVE: return "INTERACTIVE";
183 case THREAD_ACTIVITY_CLASS_SLEEPY: return "SLEEPY";
184 case THREAD_ACTIVITY_CLASS_UNKNOWN: return "UNKNOWN";
185 }
186 unreachable("invalid thread activity class");
187}
188
189static inline int64_t thread_virtual_runtime_left(struct thread *t) {
190 int64_t ret = t->virtual_budget - t->virtual_period_runtime;
191 return MAX(ret, INT64_C(0));
192}
193
194static inline void thread_scale_back_delta(struct thread *thread) {
195 thread->dynamic_delta = (thread->dynamic_delta * 1000) / 1100;
196}
197
198static inline void
199scheduler_acquire_two_locks(struct scheduler *a, struct scheduler *b,
200 enum irql *a_irql_out,
201 enum irql *b_irql_out) TSA_NO_ANALYSIS {
202 enforce(a != b);
203 if (a < b) {
204 *a_irql_out = spin_lock_high(&a->lock);
205 *b_irql_out = spin_lock_high(&b->lock);
206 } else {
207 *b_irql_out = spin_lock_high(&b->lock);
208 *a_irql_out = spin_lock_high(&a->lock);
209 }
210}
211
212static inline void
213scheduler_release_two_locks(struct scheduler *a, struct scheduler *b,
214 enum irql a_irql,
215 enum irql b_irql) TSA_NO_ANALYSIS {
216 if (a == b)
217 return spin_unlock(&a->lock, a_irql);
218
219 if (a > b) {
220 spin_unlock(&a->lock, a_irql);
221 spin_unlock(&b->lock, b_irql);
222 } else {
223 spin_unlock(&b->lock, b_irql);
224 spin_unlock(&a->lock, a_irql);
225 }
226}
227
228/* this function and the other release_two_raw_locks is only to be used
229 * from inside of scheduler_yield() and friends. nowhere else! */
230static inline void
231scheduler_acquire_two_raw_locks(struct scheduler *a,
232 struct scheduler *b) TSA_NO_ANALYSIS {
233 enforce(a != b);
234 if (a < b) {
235 spin_lock_raw(&a->lock);
236 spin_lock_raw(&b->lock);
237 } else {
238 spin_lock_raw(&b->lock);
239 spin_lock_raw(&a->lock);
240 }
241}
242
243static inline void
244scheduler_release_two_raw_locks(struct scheduler *a,
245 struct scheduler *b) TSA_NO_ANALYSIS {
246 enforce(a != b);
247 if (a > b) {
248 spin_unlock_raw(&a->lock);
249 spin_unlock_raw(&b->lock);
250 } else {
251 spin_unlock_raw(&b->lock);
252 spin_unlock_raw(&a->lock);
253 }
254}
255
256static inline void scheduler_defer_resched(struct scheduler *target) {
257 cpu_mask_set(m: &smp_core_scheduler()->deferred_resched_mask, cpu: target->core_id);
258}
259
260/* Internal use only */
261void scheduler_switch_in(void);
262
263/* NOTE: This is merely a place to hook things into.
264 * The actual CPU that calls this is undefined */
265void thread_post_migrate(struct thread *t, cpu_id_t old_cpu, cpu_id_t new_cpu);
266
267/* Called with wait_lock held after every object link is removed */
268void scheduler_complete_object_wait(struct thread *t,
269 enum thread_resume_reason reason);
270
271void scheduler_resume_for_apc(struct thread *t);
272void thread_class_floor_inc_locked(struct thread *t,
273 enum thread_prio_class class);
274void thread_class_floor_dec_locked(struct thread *t,
275 enum thread_prio_class class);
276