1#include <kassert.h>
2#include <sch/sched.h>
3#include <thread/apc.h>
4#include <thread/thread.h>
5
6static inline void scheduler_set_queue_bitmap(struct scheduler *sched,
7 uint8_t prio) {
8 atomic_fetch_or(&sched->queue_bitmap, 1 << prio);
9}
10
11static inline void scheduler_clear_queue_bitmap(struct scheduler *sched,
12 uint8_t prio) {
13 atomic_fetch_and(&sched->queue_bitmap, ~(1 << prio));
14}
15
16static inline uint8_t scheduler_get_bitmap(struct scheduler *sched) {
17 return atomic_load(&sched->queue_bitmap);
18}
19
20static inline struct scheduler *smp_core_scheduler(void) {
21 return global.schedulers[smp_core_id()];
22}
23
24static inline struct idle_thread_data *smp_core_idle_thread(void) {
25 return &smp_core_scheduler()->idle_thread_data;
26}
27
28static inline bool thread_exhausted_period(struct scheduler *sched,
29 struct thread *thread) {
30 return thread->completed_period == sched->current_period;
31}
32
33static inline void scheduler_decrement_thread_count(struct scheduler *sched,
34 struct thread *t) {
35 sched->total_thread_count--;
36 sched->thread_count[t->perceived_prio_class]--;
37
38 if (sched->thread_count[t->perceived_prio_class] == 0)
39 scheduler_clear_queue_bitmap(sched, prio: t->perceived_prio_class);
40
41 if (t->effective_priority == THREAD_PRIO_CLASS_TIMESHARE)
42 sched->total_weight -= t->weight;
43
44 atomic_fetch_sub(&scheduler_data.total_threads, 1);
45}
46
47static inline void scheduler_increment_thread_count(struct scheduler *sched,
48 struct thread *t) {
49 sched->total_thread_count++;
50 sched->thread_count[t->perceived_prio_class]++;
51 scheduler_set_queue_bitmap(sched, prio: t->perceived_prio_class);
52
53 if (t->effective_priority == THREAD_PRIO_CLASS_TIMESHARE)
54 sched->total_weight += t->weight;
55
56 atomic_fetch_add(&scheduler_data.total_threads, 1);
57}
58
59static inline size_t scheduler_get_thread_count(struct scheduler *sched,
60 enum thread_prio_class prio) {
61 return sched->thread_count[prio];
62}
63
64static inline struct list_head *
65scheduler_get_this_thread_queue(struct scheduler *sched,
66 enum thread_prio_class prio) {
67 switch (prio) {
68 case THREAD_PRIO_CLASS_URGENT: return &sched->urgent_threads;
69 case THREAD_PRIO_CLASS_RT: return &sched->rt_threads;
70 case THREAD_PRIO_CLASS_TIMESHARE: return NULL; /* Use the tree */
71 case THREAD_PRIO_CLASS_BACKGROUND: return &sched->bg_threads;
72 }
73 kassert_unreachable("invalid thread_prio_class");
74}
75
76static inline void enqueue_to_tree(struct scheduler *sched,
77 struct thread *thread) {
78 rbt_insert(tree: &sched->thread_rbt, new_node: &thread->rq_tree_node);
79}
80
81static inline void retire_thread(struct scheduler *sched,
82 struct thread *thread) {
83 rbt_insert(tree: &sched->completed_rbt, new_node: &thread->rq_tree_node);
84}
85
86static inline void dequeue_from_tree(struct scheduler *sched,
87 struct thread *thread) {
88 if (rbt_has_node(tree: &sched->completed_rbt, node: &thread->rq_tree_node))
89 return rbt_delete(tree: &sched->completed_rbt, z: &thread->rq_tree_node);
90
91 rbt_delete(tree: &sched->thread_rbt, z: &thread->rq_tree_node);
92}
93
94/* The `thread_rbt` should be NULL here */
95static inline void swap_queues(struct scheduler *sched) {
96 kassert(sched->thread_rbt.root == NULL);
97 sched->thread_rbt.root = sched->completed_rbt.root;
98 sched->completed_rbt.root = NULL;
99}
100
101static inline bool scheduler_ts_empty(struct scheduler *sched) {
102 return sched->thread_rbt.root == NULL && sched->completed_rbt.root == NULL;
103}
104
105static inline enum thread_prio_class
106available_prio_level_from_bitmap(uint8_t bitmap) {
107 return 31 - __builtin_clz((uint32_t) bitmap);
108}
109
110static inline struct thread *find_highest_prio(struct scheduler *sched) {
111 struct rbt_node *node = rbt_max(tree: &sched->thread_rbt);
112 if (!node)
113 return NULL;
114
115 rbt_delete(tree: &sched->thread_rbt, z: node);
116
117 return thread_from_rq_rbt_node(node);
118}
119
120/* Don't touch `current_period` here */
121static inline void disable_period(struct scheduler *sched) {
122 sched->period_enabled = false;
123 sched->period_ms = 0;
124 sched->period_start_ms = 0;
125}
126
127static inline bool scheduler_tick_enabled(struct scheduler *sched) {
128 return atomic_load(&sched->tick_enabled);
129}
130
131static inline bool scheduler_set_tick_enabled(struct scheduler *sched,
132 bool new) {
133 return atomic_exchange(&sched->tick_enabled, new);
134}
135
136static inline const char *thread_state_str(const enum thread_state state) {
137 switch (state) {
138 case THREAD_STATE_IDLE_THREAD: return "IDLE THREAD";
139 case THREAD_STATE_READY: return "READY";
140 case THREAD_STATE_RUNNING: return "RUNNING";
141 case THREAD_STATE_BLOCKED: return "BLOCKED";
142 case THREAD_STATE_SLEEPING: return "SLEEPING";
143 case THREAD_STATE_ZOMBIE: return "ZOMBIE";
144 case THREAD_STATE_TERMINATED: return "TERMINATED";
145 case THREAD_STATE_HALTED: return "HALTED";
146 }
147 kassert_unreachable("invalid thread state");
148}
149
150static inline const char *
151thread_activity_class_str(enum thread_activity_class c) {
152 switch (c) {
153 case THREAD_ACTIVITY_CLASS_CPU_BOUND: return "CPU BOUND";
154 case THREAD_ACTIVITY_CLASS_IO_BOUND: return "IO BOUND";
155 case THREAD_ACTIVITY_CLASS_INTERACTIVE: return "INTERACTIVE";
156 case THREAD_ACTIVITY_CLASS_SLEEPY: return "SLEEPY";
157 case THREAD_ACTIVITY_CLASS_UNKNOWN: return "UNKNOWN";
158 }
159 kassert_unreachable("invalid thread activity class");
160}
161
162static inline int64_t thread_virtual_runtime_left(struct thread *t) {
163 int64_t ret = t->virtual_budget - t->virtual_period_runtime;
164 return ret < 0 ? 0 : ret;
165}
166
167static inline void thread_scale_back_delta(struct thread *thread) {
168 thread->dynamic_delta = (thread->dynamic_delta * 1000) / 1100;
169}
170
171static inline void scheduler_acquire_two_locks(struct scheduler *a,
172 struct scheduler *b,
173 enum irql *a_irql_out,
174 enum irql *b_irql_out) {
175 kassert(a != b);
176 if (a < b) {
177 *a_irql_out = spin_lock_irq_disable(lock: &a->lock);
178 *b_irql_out = spin_lock_irq_disable(lock: &b->lock);
179 } else {
180 *b_irql_out = spin_lock_irq_disable(lock: &b->lock);
181 *a_irql_out = spin_lock_irq_disable(lock: &a->lock);
182 }
183}
184
185static inline void scheduler_release_two_locks(struct scheduler *a,
186 struct scheduler *b,
187 enum irql a_irql,
188 enum irql b_irql) {
189 if (a == b)
190 return spin_unlock(lock: &a->lock, old: a_irql);
191
192 if (a > b) {
193 spin_unlock(lock: &a->lock, old: a_irql);
194 spin_unlock(lock: &b->lock, old: b_irql);
195 } else {
196 spin_unlock(lock: &b->lock, old: b_irql);
197 spin_unlock(lock: &a->lock, old: a_irql);
198 }
199}
200
201/* this function and the other release_two_raw_locks is only to be used
202 * from inside of scheduler_yield() and friends. nowhere else! */
203static inline void scheduler_acquire_two_raw_locks(struct scheduler *a,
204 struct scheduler *b) {
205 kassert(a != b);
206 if (a < b) {
207 spin_lock_raw(lock: &a->lock);
208 spin_lock_raw(lock: &b->lock);
209 } else {
210 spin_lock_raw(lock: &b->lock);
211 spin_lock_raw(lock: &a->lock);
212 }
213}
214
215static inline void scheduler_release_two_raw_locks(struct scheduler *a,
216 struct scheduler *b) {
217 kassert(a != b);
218 if (a > b) {
219 spin_unlock_raw(lock: &a->lock);
220 spin_unlock_raw(lock: &b->lock);
221 } else {
222 spin_unlock_raw(lock: &b->lock);
223 spin_unlock_raw(lock: &a->lock);
224 }
225}
226
227/* Internal use only */
228void thread_prepare_to_wake_locked(struct thread *t, enum thread_wake_reason r,
229 void *wake_src);
230void scheduler_switch_in();
231void thread_post_migrate(struct thread *t, size_t old_cpu, size_t new_cpu);
232