1#include <asm.h>
2#include <bootstage.h>
3#include <crypto/prng.h>
4#include <irq/idt.h>
5#include <math/clamp.h>
6#include <math/fixed.h>
7#include <math/min_max.h>
8#include <registry.h>
9#include <sch/sched.h>
10#include <smp/smp.h>
11#include <stdatomic.h>
12#include <stdint.h>
13
14#include "internal.h"
15
16/* TODO: #define things <--- do this */
17
18static void derive_timeshare_prio_range(enum thread_activity_class cls,
19 uint32_t *min, uint32_t *max);
20
21#define THREAD_DELTA_UNIT (1ULL << 3)
22
23#define THREAD_BOOST_WAKE_SMALL \
24 (4ULL * THREAD_DELTA_UNIT) /* provisional boost for wake */
25
26#define THREAD_BOOST_WAKE_LARGE \
27 (12ULL * THREAD_DELTA_UNIT) /* stronger boost if very interactive */
28
29#define THREAD_PENALTY_CPU_RUN \
30 (3ULL * THREAD_DELTA_UNIT) /* penalize heavy CPU usage per run period */
31
32#define THREAD_DELTA_MAX (1 << 9)
33
34#define THREAD_REINSERT_THRESHOLD \
35 (8ULL * THREAD_DELTA_UNIT) /* only reinsert if effective priority changes \
36 >= this */
37
38#define THREAD_HYSTERESIS_MS 250ULL
39#define THREAD_PROV_BOOST_MS 50ULL /* provisional boost expiration */
40
41#define THREAD_MUL_INTERACTIVE 3ULL /* Big boost */
42#define THREAD_MUL_IO_BOUND 2ULL /* Small boost */
43#define THREAD_MUL_CPU_BOUND 1ULL /* No boost */
44#define THREAD_MUL_SLEEPY 1ULL /* No boost */
45
46/* Scheduling periods */
47#define MIN_PERIOD_MS 20ULL /* don’t go too short */
48#define MAX_PERIOD_MS 300ULL /* don’t go too long */
49#define BASE_PERIOD_MS 50ULL /* baseline for small loads */
50
51/* Timeslices */
52#define MIN_SLICE_MS 2 /* smallest slice granularity */
53#define MAX_SLICE_MS 20 /* cap slice length to avoid hogs */
54
55#define WAKE_FREQ_MAX 20
56#define WAKE_FREQ_SCALE 5
57
58#define THREAD_SLICE_MIN 1
59#define THREAD_SLICE_MAX 16
60
61#define THREAD_BASE_WEIGHT 1024
62#define THREAD_WEIGHT_SCALING 100
63
64#define NICE_BASE_FP FX(1.022)
65
66#define SET_MUL(__multiplier) \
67 class_mul = __multiplier; \
68 break;
69
70static enum thread_activity_class
71classify_activity(struct thread_activity_metrics m) {
72 if (m.run_ratio > 80 && m.block_ratio < 10)
73 return THREAD_ACTIVITY_CLASS_CPU_BOUND;
74
75 if (m.block_ratio > 40 && m.wake_freq > 2)
76 return THREAD_ACTIVITY_CLASS_IO_BOUND;
77
78 if (m.wake_freq > 5)
79 return THREAD_ACTIVITY_CLASS_INTERACTIVE;
80
81 if (m.sleep_ratio > 50)
82 return THREAD_ACTIVITY_CLASS_SLEEPY;
83
84 /* Let's not confuse the rest of the scheduler
85 * with an unknown classification */
86 return THREAD_ACTIVITY_CLASS_CPU_BOUND;
87}
88
89void thread_classify_activity(struct thread *t, uint64_t now_ms) {
90 /* Rate limit to prevent rapid bouncing */
91 if (now_ms - t->last_class_change_ms < THREAD_HYSTERESIS_MS)
92 return;
93
94 t->activity_class = classify_activity(m: t->activity_metrics);
95 t->last_class_change_ms = now_ms;
96}
97
98static struct thread_activity_metrics calc_activity_metrics(struct thread *t) {
99 struct thread_activity_metrics m = {0};
100 uint64_t total_duration = 0;
101 uint64_t total_block = 0;
102 uint64_t total_sleep = 0;
103 uint64_t total_run = 0;
104 uint64_t total_wake_count = 0;
105
106 for (size_t i = 0; i < THREAD_ACTIVITY_BUCKET_COUNT; i++) {
107 struct thread_activity_bucket *b = &t->activity_stats->buckets[i];
108 struct thread_runtime_bucket *rtb = &t->activity_stats->rt_buckets[i];
109
110 uint64_t run_time = rtb->run_time_ms;
111 uint64_t block_time = b->block_duration;
112 uint64_t sleep_time = b->sleep_duration;
113
114 total_run += run_time;
115 total_block += block_time;
116 total_sleep += sleep_time;
117 total_wake_count += b->wake_count;
118 }
119
120 total_duration = total_run + total_block + total_sleep;
121 if (total_duration == 0)
122 total_duration = 1;
123
124 m.run_ratio = (total_run * 100) / total_duration;
125 m.block_ratio = (total_block * 100) / total_duration;
126 m.sleep_ratio = (total_sleep * 100) / total_duration;
127
128 m.wake_freq = total_wake_count / THREAD_ACTIVITY_BUCKET_COUNT;
129
130 return m;
131}
132
133void thread_calculate_activity_data(struct thread *t) {
134 if (thread_get_state(t) == THREAD_STATE_IDLE_THREAD)
135 return;
136
137 struct thread_activity_metrics mtcs = calc_activity_metrics(t);
138 t->activity_metrics = mtcs;
139}
140
141static void derive_timeshare_prio_range(enum thread_activity_class cls,
142 uint32_t *min, uint32_t *max) {
143 switch (cls) {
144 case THREAD_ACTIVITY_CLASS_INTERACTIVE:
145 *min = THREAD_ACT_INTERACTIVE_MIN;
146 *max = THREAD_ACT_INTERACTIVE_MAX;
147 break;
148
149 case THREAD_ACTIVITY_CLASS_IO_BOUND:
150 *min = THREAD_ACT_IO_BOUND_MIN;
151 *max = THREAD_ACT_IO_BOUND_MAX;
152 break;
153
154 case THREAD_ACTIVITY_CLASS_CPU_BOUND:
155 *min = THREAD_ACT_CPU_BOUND_MIN;
156 *max = THREAD_ACT_CPU_BOUND_MAX;
157 break;
158
159 case THREAD_ACTIVITY_CLASS_SLEEPY:
160 default:
161 *min = THREAD_ACT_SLEEPY_MIN;
162 *max = THREAD_ACT_SLEEPY_MAX;
163 break;
164 }
165}
166
167static uint32_t compute_activity_score_pct(struct thread_activity_metrics *m) {
168 uint32_t wake_norm = m->wake_freq > WAKE_FREQ_MAX ? 100 : m->wake_freq * 5;
169
170 uint32_t interactive_pct = (wake_norm * (100u - m->block_ratio)) / 100u;
171
172 uint32_t cpu_factor = 100u - m->run_ratio;
173
174 uint32_t score_pct = (interactive_pct * cpu_factor) / 100u;
175
176 uint32_t bias = score_pct / 8;
177
178 uint32_t final_pct = score_pct + bias;
179
180 if (final_pct > 100)
181 final_pct = 100;
182
183 return final_pct;
184}
185
186static inline int32_t jitter_for_thread(void) {
187 uint32_t v = prng_next();
188 uint32_t jit = THREAD_REINSERT_THRESHOLD >> 2;
189 int32_t j = (int32_t) (v % (2 * jit + 1)) - (int32_t) jit;
190 return j;
191}
192
193static int get_class_multiplier(enum thread_activity_class class) {
194 int class_mul;
195 switch (class) {
196 case THREAD_ACTIVITY_CLASS_INTERACTIVE: SET_MUL(THREAD_MUL_INTERACTIVE);
197 case THREAD_ACTIVITY_CLASS_IO_BOUND: SET_MUL(THREAD_MUL_IO_BOUND);
198 case THREAD_ACTIVITY_CLASS_CPU_BOUND: SET_MUL(THREAD_MUL_CPU_BOUND);
199 case THREAD_ACTIVITY_CLASS_SLEEPY:
200 default: SET_MUL(0); /* Unclassified thread or sleepy thread */
201 }
202 return class_mul;
203}
204
205void thread_apply_wake_boost(struct thread *t) {
206 if (thread_is_rt(t))
207 return;
208
209 uint32_t score_pct = compute_activity_score_pct(m: &t->activity_metrics);
210 int32_t mul = get_class_multiplier(class: t->activity_class);
211
212 int64_t delta_change64 = score_pct * THREAD_DELTA_UNIT * mul / 100;
213
214 delta_change64 += jitter_for_thread();
215
216 int64_t new_delta = (int64_t) t->dynamic_delta + delta_change64;
217 CLAMP(new_delta, -THREAD_DELTA_MAX, THREAD_DELTA_MAX);
218
219 t->dynamic_delta = (int32_t) new_delta;
220
221 thread_update_effective_priority(t);
222}
223
224static int32_t compute_cpu_penalty(struct thread *t, int32_t base_penalty) {
225 struct thread_activity_metrics *m = &t->activity_metrics;
226 uint32_t run_scale = m->run_ratio;
227 uint32_t wake_scale = m->wake_freq * 2;
228 if (wake_scale > 100)
229 wake_scale = 100;
230
231 int32_t penalty = base_penalty * run_scale / 100;
232 penalty -= base_penalty * wake_scale / 200;
233 if (penalty < 1)
234 penalty = 1;
235
236 return penalty;
237}
238
239void thread_apply_cpu_penalty(struct thread *t) {
240 thread_calculate_activity_data(t); /* Give it another update */
241
242 /* Apply the penalty */
243 if (t->activity_class == THREAD_ACTIVITY_CLASS_CPU_BOUND) {
244 /* Small penalty */
245 int32_t penalty = compute_cpu_penalty(t, THREAD_PENALTY_CPU_RUN);
246 int64_t scaled_delta = penalty * t->weight / MAX(t->weight, 1ULL);
247
248 CLAMP(scaled_delta, -THREAD_DELTA_MAX, THREAD_DELTA_MAX);
249 t->dynamic_delta -= scaled_delta;
250 }
251
252 thread_update_effective_priority(t);
253}
254
255static int64_t base_weight_of(struct thread *t) {
256 struct thread_activity_metrics *m = &t->activity_metrics;
257
258 int64_t w = THREAD_BASE_WEIGHT;
259
260 w += m->wake_freq * THREAD_WEIGHT_SCALING;
261 w += (THREAD_WEIGHT_SCALING - m->run_ratio) * (THREAD_WEIGHT_SCALING / 2);
262 w += t->dynamic_delta / THREAD_WEIGHT_SCALING;
263
264 int32_t effective_boost = t->niceness + t->climb_state.effective_boost;
265
266 if (effective_boost) {
267 int32_t nf = fx_pow_i32(NICE_BASE_FP, exp: effective_boost);
268 w = (w * nf) >> 16;
269 }
270
271 if (w < 1)
272 w = 1;
273
274 return w;
275}
276
277void thread_update_effective_priority(struct thread *t) {
278 uint32_t min, max;
279 derive_timeshare_prio_range(cls: t->activity_class, min: &min, max: &max);
280
281 int64_t avg = ((int64_t) min + (int64_t) max) / 2;
282 int64_t eff = avg + t->dynamic_delta;
283 CLAMP(eff, min, max);
284
285 t->activity_score = (thread_prio_t) eff;
286 t->virtual_runtime_left = thread_virtual_runtime_left(t);
287 t->weight = base_weight_of(t);
288}
289
290static uint64_t compute_period(struct scheduler *s) {
291 uint64_t load = s->total_thread_count;
292 uint64_t period = BASE_PERIOD_MS + (load * 2); /* Linear growth */
293 CLAMP(period, MIN_PERIOD_MS, MAX_PERIOD_MS);
294 return period;
295}
296
297static uint64_t map_activity_score(uint64_t score) {
298 const uint64_t min_score = THREAD_ACT_SLEEPY_MIN;
299 const uint64_t max_score = THREAD_ACT_INTERACTIVE_MAX;
300 const uint64_t slice_delta = THREAD_SLICE_MAX - THREAD_SLICE_MIN;
301 const uint64_t score_range = max_score - min_score;
302
303 CLAMP(score, min_score, max_score);
304
305 uint64_t score_delta = score - min_score;
306
307 return 1 + (score_delta * slice_delta) / score_range;
308}
309
310static uint64_t thread_derive_slice_count(struct thread *t) {
311 uint64_t base = map_activity_score(score: t->activity_score);
312 int64_t adjust = 1;
313
314 if (t->activity_metrics.block_ratio > t->activity_metrics.run_ratio)
315 adjust += 1;
316
317 if (t->activity_metrics.run_ratio > 70)
318 adjust -= 1;
319
320 if (t->activity_metrics.sleep_ratio > 70)
321 adjust -= 1;
322
323 int64_t result = (int64_t) base + adjust;
324
325 CLAMP(result, THREAD_SLICE_MIN, THREAD_SLICE_MAX);
326
327 return (uint64_t) result;
328}
329
330static void allocate_slices(struct scheduler *s, uint64_t now_ms) {
331 s->period_ms = compute_period(s);
332 s->period_start_ms = now_ms;
333
334 uint64_t total_weight = 0;
335 struct rbt_node *node;
336 rbt_for_each(node, &s->thread_rbt) {
337 struct thread *t = thread_from_rq_rbt_node(node);
338 total_weight += t->weight;
339 }
340
341 if (total_weight == 0)
342 total_weight = 1;
343
344 rbt_for_each(node, &s->thread_rbt) {
345 struct thread *t = thread_from_rq_rbt_node(node);
346
347 uint64_t budget_ms = (s->period_ms * t->weight) / total_weight;
348 if (budget_ms < MIN_SLICE_MS)
349 budget_ms = MIN_SLICE_MS;
350
351 t->period_runtime_raw_ms = 0;
352 t->budget_time_raw_ms = budget_ms;
353
354 uint64_t slices = thread_derive_slice_count(t);
355 t->timeslice_length_raw_ms = budget_ms / slices;
356
357 uint64_t mult = t->activity_score == 0 ? 1 : t->activity_score;
358
359 t->virtual_period_runtime = 0;
360 t->virtual_budget = budget_ms * mult;
361 t->completed_period = s->current_period - 1;
362 }
363}
364
365static void scheduler_update_thread_weights(struct scheduler *s) {
366 struct rbt_node *node;
367 rbt_for_each(node, &s->thread_rbt) {
368 struct thread *t = rbt_entry(node, struct thread, rq_tree_node);
369
370 /* This will recalculate activity data
371 * and update the effective priority */
372 thread_apply_cpu_penalty(t);
373 }
374}
375
376void scheduler_period_start(struct scheduler *s, uint64_t now_ms) {
377 s->current_period++;
378
379 scheduler_update_thread_weights(s);
380
381 allocate_slices(s, now_ms);
382
383 s->period_enabled = true;
384}
385