1#include <asm.h>
2#include <atomic.h>
3#include <bootstage.h>
4#include <crypto/prng.h>
5#include <irq/idt.h>
6#include <math/bit.h>
7#include <math/fixed.h>
8#include <math/min_max.h>
9#include <registry.h>
10#include <sch/sched.h>
11#include <smp/smp.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 BIT(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 ((int64_t) BIT(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 UINT64_C(20) /* don’t go too short */
48#define MAX_PERIOD_MS UINT64_C(300) /* 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 INT64_C(1)
59#define THREAD_SLICE_MAX INT64_C(16)
60#define THREAD_WEIGHT_MIN UINT64_C(1)
61
62#define THREAD_BASE_WEIGHT 1024
63#define THREAD_WEIGHT_SCALING 100
64
65#define NICE_BASE_FP FX(1.022)
66
67static enum thread_activity_class
68classify_activity(struct thread_activity_metrics m) {
69 if (m.run_ratio > 80 && m.block_ratio < 10)
70 return THREAD_ACTIVITY_CLASS_CPU_BOUND;
71
72 if (m.block_ratio > 40 && m.wake_freq > 2)
73 return THREAD_ACTIVITY_CLASS_IO_BOUND;
74
75 if (m.wake_freq > 5)
76 return THREAD_ACTIVITY_CLASS_INTERACTIVE;
77
78 if (m.sleep_ratio > 50)
79 return THREAD_ACTIVITY_CLASS_SLEEPY;
80
81 /* Let's not confuse the rest of the scheduler
82 * with an unknown classification */
83 return THREAD_ACTIVITY_CLASS_CPU_BOUND;
84}
85
86void thread_classify_activity(struct thread *t, uint64_t now_ms) {
87 /* Rate limit to prevent rapid bouncing */
88 if (now_ms - t->last_class_change_ms < THREAD_HYSTERESIS_MS)
89 return;
90
91 t->activity_class = classify_activity(m: t->activity_metrics);
92 t->last_class_change_ms = now_ms;
93}
94
95static struct thread_activity_metrics calc_activity_metrics(struct thread *t) {
96 struct thread_activity_metrics m = {0};
97 uint64_t total_duration = 0;
98 uint64_t total_block = 0;
99 uint64_t total_sleep = 0;
100 uint64_t total_run = 0;
101 uint64_t total_wake_count = 0;
102 uint32_t current_epoch =
103 (uint32_t) ((uint64_t) time_get_ms() >> THREAD_ACTIVITY_BUCKET_SHIFT);
104
105 for (size_t i = 0; i < THREAD_ACTIVITY_BUCKET_COUNT; i++) {
106 struct thread_activity_bucket *b = &t->activity_stats.buckets[i];
107
108 if ((uint32_t) (current_epoch - b->epoch) >=
109 THREAD_ACTIVITY_BUCKET_COUNT)
110 continue;
111
112 total_run += b->run_ms;
113 total_block += b->block_ms;
114 total_sleep += b->sleep_ms;
115 total_wake_count += b->wake_count;
116 }
117
118 total_duration = total_run + total_block + total_sleep;
119 if (total_duration == 0)
120 total_duration = 1;
121
122 m.run_ratio = (total_run * 100) / total_duration;
123 m.block_ratio = (total_block * 100) / total_duration;
124 m.sleep_ratio = (total_sleep * 100) / total_duration;
125
126 uint64_t avg_wake = total_wake_count / THREAD_ACTIVITY_BUCKET_COUNT;
127 m.wake_freq = (avg_wake > UINT8_MAX) ? UINT8_MAX : (uint8_t) avg_wake;
128
129 return m;
130}
131
132void thread_calculate_activity_data(struct thread *t) {
133 if (thread_get_state(t) == THREAD_STATE_IDLE_THREAD)
134 return;
135
136 struct thread_activity_metrics mtcs = calc_activity_metrics(t);
137 t->activity_metrics = mtcs;
138}
139
140static void derive_timeshare_prio_range(enum thread_activity_class cls,
141 uint32_t *min, uint32_t *max) {
142 switch (cls) {
143 case THREAD_ACTIVITY_CLASS_INTERACTIVE:
144 *min = THREAD_ACT_INTERACTIVE_MIN;
145 *max = THREAD_ACT_INTERACTIVE_MAX;
146 break;
147
148 case THREAD_ACTIVITY_CLASS_IO_BOUND:
149 *min = THREAD_ACT_IO_BOUND_MIN;
150 *max = THREAD_ACT_IO_BOUND_MAX;
151 break;
152
153 case THREAD_ACTIVITY_CLASS_CPU_BOUND:
154 *min = THREAD_ACT_CPU_BOUND_MIN;
155 *max = THREAD_ACT_CPU_BOUND_MAX;
156 break;
157
158 case THREAD_ACTIVITY_CLASS_SLEEPY:
159 default:
160 *min = THREAD_ACT_SLEEPY_MIN;
161 *max = THREAD_ACT_SLEEPY_MAX;
162 break;
163 }
164}
165
166static uint32_t compute_activity_score_pct(struct thread_activity_metrics *m) {
167 uint32_t wake_norm = m->wake_freq > WAKE_FREQ_MAX ? 100 : m->wake_freq * 5;
168
169 uint32_t interactive_pct = (wake_norm * (100u - m->block_ratio)) / 100u;
170
171 uint32_t cpu_factor = 100u - m->run_ratio;
172
173 uint32_t score_pct = (interactive_pct * cpu_factor) / 100u;
174
175 uint32_t bias = score_pct / 8;
176
177 uint32_t final_pct = score_pct + bias;
178
179 if (final_pct > 100)
180 final_pct = 100;
181
182 return final_pct;
183}
184
185static inline int32_t jitter_for_thread(void) {
186 uint32_t v = prng_next();
187 uint32_t jit = THREAD_REINSERT_THRESHOLD >> 2;
188 int32_t j = (int32_t) (v % (2 * jit + 1)) - (int32_t) jit;
189 return j;
190}
191
192static int get_class_multiplier(enum thread_activity_class class) {
193 switch (class) {
194 case THREAD_ACTIVITY_CLASS_INTERACTIVE: return THREAD_MUL_INTERACTIVE;
195 case THREAD_ACTIVITY_CLASS_IO_BOUND: return THREAD_MUL_IO_BOUND;
196 case THREAD_ACTIVITY_CLASS_CPU_BOUND: return THREAD_MUL_CPU_BOUND;
197 case THREAD_ACTIVITY_CLASS_SLEEPY:
198 default: return 0; /* Unclassified thread or sleepy thread */
199 }
200}
201
202void thread_apply_wake_boost(struct thread *t) {
203 if (thread_is_rt(t))
204 return;
205
206 uint32_t score_pct = compute_activity_score_pct(m: &t->activity_metrics);
207 int32_t mul = get_class_multiplier(class: t->activity_class);
208
209 int64_t delta_change64 = score_pct * THREAD_DELTA_UNIT * mul / 100;
210
211 delta_change64 += jitter_for_thread();
212
213 int64_t new_delta = (int64_t) t->dynamic_delta + delta_change64;
214 new_delta = CLAMP(new_delta, -THREAD_DELTA_MAX, THREAD_DELTA_MAX);
215
216 t->dynamic_delta = (int32_t) new_delta;
217
218 thread_update_effective_priority(t);
219}
220
221static int32_t compute_cpu_penalty(struct thread *t, int32_t base_penalty) {
222 struct thread_activity_metrics *m = &t->activity_metrics;
223 uint32_t run_scale = m->run_ratio;
224 uint32_t wake_scale = m->wake_freq * 2;
225 if (wake_scale > 100)
226 wake_scale = 100;
227
228 int32_t penalty = base_penalty * run_scale / 100;
229 penalty -= base_penalty * wake_scale / 200;
230 if (penalty < 1)
231 penalty = 1;
232
233 return penalty;
234}
235
236void thread_apply_cpu_penalty(struct thread *t) {
237 thread_calculate_activity_data(t); /* Give it another update */
238
239 /* Apply the penalty */
240 if (t->activity_class == THREAD_ACTIVITY_CLASS_CPU_BOUND) {
241 /* Small penalty */
242 int32_t penalty = compute_cpu_penalty(t, THREAD_PENALTY_CPU_RUN);
243 int64_t scaled_delta =
244 penalty * t->weight / MAX(t->weight, THREAD_WEIGHT_MIN);
245
246 scaled_delta = CLAMP(scaled_delta, -THREAD_DELTA_MAX, THREAD_DELTA_MAX);
247 t->dynamic_delta -= scaled_delta;
248 }
249
250 thread_update_effective_priority(t);
251}
252
253static int64_t base_weight_of(struct thread *t) {
254 struct thread_activity_metrics *m = &t->activity_metrics;
255
256 int64_t w = THREAD_BASE_WEIGHT;
257
258 w += m->wake_freq * THREAD_WEIGHT_SCALING;
259 w += (THREAD_WEIGHT_SCALING - m->run_ratio) * (THREAD_WEIGHT_SCALING / 2);
260 w += t->dynamic_delta / THREAD_WEIGHT_SCALING;
261
262 int32_t effective_boost = t->niceness + t->climb_data.effective_boost;
263
264 if (effective_boost) {
265 fx32_32_t nf = fx_pow_i32(NICE_BASE_FP, exp: effective_boost);
266 w = fx_to_int(x: fx_mul(a: fx_from_int(x: w), b: nf));
267 }
268
269 if (w < 1)
270 w = 1;
271
272 return w;
273}
274
275void thread_update_effective_priority(struct thread *t) {
276 uint32_t min, max;
277 derive_timeshare_prio_range(cls: t->activity_class, min: &min, max: &max);
278
279 int64_t avg = ((int64_t) min + (int64_t) max) / 2;
280 int64_t eff = avg + t->dynamic_delta;
281 int64_t eff_min = min;
282 int64_t eff_max = max;
283 eff = CLAMP(eff, eff_min, eff_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 period = 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 score = 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 result = 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, *tmp;
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_safe(node, tmp, &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->virtual_runtime_left = thread_virtual_runtime_left(t);
362 t->completed_period = s->current_period - 1;
363
364 rbt_reinsert(tree: &s->thread_rbt, node);
365 }
366}
367
368static void scheduler_update_thread_weights(struct scheduler *s) {
369 struct rbt_node *node;
370 rbt_for_each(node, &s->thread_rbt) {
371 struct thread *t = rbt_entry(node, struct thread, rq_tree_node);
372
373 /* The penalty refreshes virtual_runtime_left, the tree's key, but
374 * allocate_slices() sets the real one right after. Keep the key
375 * where it is so the tree stays ordered, since a node moved here
376 * could be visited and penalized twice */
377 uint32_t key = t->virtual_runtime_left;
378
379 /* This will recalculate activity data
380 * and update the effective priority */
381 thread_apply_cpu_penalty(t);
382
383 t->virtual_runtime_left = key;
384 }
385}
386
387void scheduler_period_start(struct scheduler *s, uint64_t now_ms) {
388 s->current_period++;
389
390 scheduler_update_thread_weights(s);
391
392 allocate_slices(s, now_ms);
393
394 s->period_enabled = true;
395 scheduler_debug_validate(sched: s);
396}
397