1#include <log.h>
2#include <math/clamp.h>
3#include <math/min_max.h>
4#include <sch/climb.h>
5#include <sch/periodic_work.h>
6#include <sch/sched.h>
7#include <test/export.h>
8#include <thread/thread.h>
9
10#include "internal.h"
11
12void climb_per_period_hook();
13SCHEDULER_PERIODIC_WORK_REGISTER_PER_PERIOD(climb_per_period_hook,
14 PERIODIC_WORK_MID);
15
16#ifdef DEBUG_CLIMB
17#define CLIMB_FLAGS LOG_SITE_ALL
18#else
19#define CLIMB_FLAGS LOG_SITE_LEVEL(LOG_ERROR)
20#endif
21
22LOG_SITE_DECLARE(climb, .flags = LOG_SITE_PRINT | LOG_SITE_DEFAULT,
23 .capacity = LOG_SITE_CAPACITY_DEFAULT,
24 .enabled_mask = CLIMB_FLAGS,
25 .dump_opts = ((struct log_dump_options){.show_tid = true}));
26
27LOG_HANDLE_DECLARE_PRINT(climb);
28#define climb_log(lvl, fmt, ...) \
29 log(LOG_SITE(climb), LOG_HANDLE(climb), lvl, fmt, ##__VA_ARGS__)
30
31#define climb_err(fmt, ...) climb_log(LOG_ERROR, fmt, ##__VA_ARGS__)
32#define climb_warn(fmt, ...) climb_log(LOG_WARN, fmt, ##__VA_ARGS__)
33#define climb_info(fmt, ...) climb_log(LOG_INFO, fmt, ##__VA_ARGS__)
34#define climb_debug(fmt, ...) climb_log(LOG_DEBUG, fmt, ##__VA_ARGS__)
35#define climb_trace(fmt, ...) climb_log(LOG_TRACE, fmt, ##__VA_ARGS__)
36
37struct climb_summary {
38 climb_pressure_t total_pressure_ewma;
39 size_t total_periods_spent;
40 size_t nthreads;
41};
42
43struct climb_budget {
44 int32_t max_boost_levels;
45 int32_t remaining;
46};
47
48#define CLIMB_EWMA(val, target) \
49 (fx_mul(CLIMB_BOOST_EWMA_ALPHA, val) + \
50 fx_mul(FX_ONE - CLIMB_BOOST_EWMA_ALPHA, fx_from_int(target)))
51
52static inline struct rbt *climb_tree_local() {
53 return &smp_core_scheduler()->climb_threads;
54}
55
56/*
57 * shaped = p ^ CLIMB_PRESSURE_EXPONENT
58 * level = floor(shaped * CLIMB_BOOST_LEVEL_MAX)
59 *
60 *
61 * 2000 +-------------------------------------------------------------------+
62 * |* + + + *|
63 * |** floor((p ** CLIMB_PRESSURE_EXPONENT) * CLIMB_BOOST_LEVEL_MAX) * |
64 * | * ** |
65 * | * * |
66 * 1500 |-+ ** ** +-|
67 * | * * |
68 * | ** ** |
69 * | * * |
70 * | ** ** |
71 * 1000 |-+ * * +-|
72 * | ** ** |
73 * | ** ** |
74 * | * * |
75 * | ** ** |
76 * 500 |-+ *** *** +-|
77 * | * * |
78 * | ** ** |
79 * | *** *** |
80 * | + **** + **** + |
81 * 0 +-------------------------------------------------------------------+
82 * -10 -5 0 5 10
83 *
84 * boost_clamp(level)
85 */
86static int32_t climb_pressure_to_boost_target(climb_pressure_t p) {
87 /* The pressure is between 0..1, so this doesn't do much
88 * with minor boosts. We have the BOOST_SCALE for config. purposes */
89
90 p = fx_mul(a: p, CLIMB_PRESSURE_TO_BOOST_SCALE);
91 climb_pressure_t shaped = fx_pow_i32(base: p, CLIMB_PRESSURE_EXPONENT);
92
93 int32_t level = fx_to_int(x: fx_mul(a: shaped, FX(CLIMB_BOOST_LEVEL_MAX)));
94
95 CLAMP(level, 0, CLIMB_BOOST_LEVEL_MAX);
96 return level;
97}
98TEST_EXPORT(climb_pressure_to_boost_target);
99
100/*
101 * total_pressure =
102 * pressure_clamp(direct_pressure + indirect_pressure * indirect_weight)
103 */
104static inline climb_pressure_t
105climb_thread_total_pressure(struct climb_thread_state *cts) {
106 return fx_clamp(x: cts->direct_pressure +
107 fx_mul(a: cts->indirect_pressure, CLIMB_INDIRECT_WEIGHT),
108 lo: 0, CLIMB_PRESSURE_MAX);
109}
110
111/*
112 * boost_ewma = alpha * old + (1 − alpha) * target
113 */
114static void update_fields(struct climb_thread_state *cts) {
115 climb_info("Update fields on %p", cts);
116 climb_pressure_t p = climb_thread_total_pressure(cts);
117 int32_t target = climb_pressure_to_boost_target(p);
118
119 /* EWMA */
120 cts->boost_ewma = CLIMB_EWMA(cts->boost_ewma, target);
121 cts->wanted_boost = fx_to_int(x: cts->boost_ewma);
122 cts->pressure_ewma = CLIMB_EWMA(cts->pressure_ewma, p);
123}
124
125climb_pressure_t climb_thread_applied_pressure(struct thread *t) {
126 return climb_thread_total_pressure(cts: &t->climb_state);
127}
128
129climb_pressure_t climb_thread_compute_pressure_to_apply(struct thread *t) {
130 return CLIMB_PRESSURE_THREAD_BASE + climb_thread_applied_pressure(t);
131 ;
132}
133
134/*
135 * new_pressure = p + delta * (max - p)
136 */
137static inline climb_pressure_t climb_accumulate(climb_pressure_t p,
138 climb_pressure_t delta,
139 climb_pressure_t max) {
140 return p + fx_mul(a: delta, b: (max - p));
141}
142
143/*
144 * scale = max(1 - direct, min_scale)
145 */
146static inline climb_pressure_t
147climb_pressure_scale_indirect(climb_pressure_t direct) {
148 climb_pressure_t scale = FX_ONE - direct;
149 return fx_max(a: scale, CLIMB_INDIRECT_MIN_SCALE);
150}
151
152static size_t climb_count_handles(struct climb_thread_state *cts) {
153 size_t agg = 0;
154 struct list_head *iter;
155 list_for_each(iter, &cts->handles) agg++;
156 return agg;
157}
158
159/*
160 *
161 * if direct pressure:
162 * new_direct_pressure = direct_pressure + delta *
163 * (direct_max − direct_pressure)
164 * if indirect pressure:
165 * scale = max(1 - direct_pressure, indirect_min_scale)
166 * scaled_delta = delta * scale
167 * new_indirect_pressure = indirect_pressure +
168 * scaled_delta *
169 * (indirect_max - indirect_pressure)
170 */
171static void apply_handle_pressures(struct thread *t, struct climb_handle *ch) {
172 struct climb_thread_state *cts = &t->climb_state;
173
174 climb_pressure_t delta = ch->pressure;
175
176 if (t == thread_get_current()) {
177 kassert(ch->kind == CLIMB_PRESSURE_DIRECT);
178 climb_pressure_t old = cts->direct_pressure;
179
180 climb_pressure_t newp =
181 climb_accumulate(p: old, delta, CLIMB_DIRECT_PRESSURE_MAX);
182
183 ch->applied_pressure_internal = newp - old;
184 kassert(newp - old);
185 climb_info("Applying pressure %u to %p", newp - old, cts);
186 cts->direct_pressure = newp;
187 return;
188 }
189
190 kassert(ch->kind == CLIMB_PRESSURE_INDIRECT);
191
192 /* indirect pressure */
193 climb_pressure_t scale =
194 climb_pressure_scale_indirect(direct: cts->direct_pressure);
195
196 climb_pressure_t scaled_delta = fx_mul(a: delta, b: scale);
197
198 climb_pressure_t old = cts->indirect_pressure;
199 climb_pressure_t newp =
200 climb_accumulate(p: old, delta: scaled_delta, CLIMB_INDIRECT_PRESSURE_MAX);
201
202 ch->applied_pressure_internal = newp - old;
203 kassert(newp - old);
204 climb_info("Applying pressure %u to %p", newp - old, cts);
205 cts->indirect_pressure = newp;
206}
207
208/* This assumes that the thread is already properly locked/protected */
209static void apply_handle(struct thread *t, struct climb_handle *ch) {
210 kassert(list_empty(&ch->list));
211
212 list_add_tail(new: &ch->list, head: &t->climb_state.handles);
213 apply_handle_pressures(t, ch);
214 struct climb_thread_state *cts = &t->climb_state;
215
216 climb_info("Apply handle on %p, %u", cts, climb_count_handles(cts));
217
218 /* If there was already a giver, like with indirect boosts, we don't
219 * change it. Otherwise, we do, and say we are the giver */
220 ch->given_by = ch->given_by ? ch->given_by : thread_get_current();
221
222 /* Was previously not on tree */
223 if (cts->pressure_periods == 0) {
224 cts->pressure_periods = 1;
225 kassert(!cts->on_climb_tree);
226 struct scheduler *sched = thread_get_scheduler_unsafe(t);
227 struct rbt *tree = &sched->climb_threads;
228
229 /* Get a reference for the tree */
230 kassert(thread_get(t));
231 climb_info("Insert %p to tree", cts);
232 rbt_insert(tree, new_node: &cts->climb_node);
233 cts->on_climb_tree = true;
234 } else if (cts->pressure_periods < 0) {
235 /* It was previously on decay... all we need to do
236 * is tell the thread to start pressure again,
237 * and set pressure_periods to 1 */
238 cts->pressure_periods = 1;
239 }
240}
241
242static void remove_handle(struct thread *t, struct climb_handle *ch) {
243 struct climb_thread_state *cts = &t->climb_state;
244 kassert(ch->given_by == thread_get_current());
245
246 if (ch->applied_pressure_internal == 0) {
247 climb_warn("No-op handle removed from %p", cts);
248 return;
249 }
250
251 if (ch->kind == CLIMB_PRESSURE_DIRECT) {
252 cts->direct_pressure -= ch->applied_pressure_internal;
253 } else {
254 kassert(ch->kind == CLIMB_PRESSURE_INDIRECT);
255 cts->indirect_pressure -= ch->applied_pressure_internal;
256 }
257
258 ch->applied_pressure_internal = 0;
259 list_del_init(entry: &ch->list);
260
261 climb_info("Remove handle on %p (thread %p), %u left", cts, t,
262 climb_count_handles(cts));
263
264 if (list_empty(head: &cts->handles)) {
265 /* This thread is done. Let it decay now */
266 cts->pressure_periods = -1;
267 climb_info("Begin decay on %p", cts);
268 }
269}
270
271static void climb_handle_act_self(struct thread *t, struct climb_handle *h,
272 void (*act)(struct thread *,
273 struct climb_handle *h)) {
274 enum irql irql = IRQL_PASSIVE_LEVEL;
275 bool irql_change = false;
276 if (irql_get() < IRQL_DISPATCH_LEVEL) {
277 irql = irql_raise(new_level: IRQL_DISPATCH_LEVEL);
278 irql_change = true;
279 }
280
281 kassert(t == thread_get_current());
282 act(t, h);
283
284 if (irql_change)
285 irql_lower(old_level: irql);
286}
287
288static void climb_handle_act_other(struct thread *t, struct climb_handle *ch,
289 void (*act)(struct thread *,
290 struct climb_handle *),
291 bool lock) {
292
293 /* thread cannot disappear under us */
294 enum irql irql = IRQL_PASSIVE_LEVEL;
295
296 struct scheduler *sch = NULL;
297
298 if (!lock)
299 sch = thread_get_scheduler(t, sirql_out: &irql);
300
301 act(t, ch);
302
303 if (!lock)
304 spin_unlock(&sch->lock, irql);
305}
306
307static bool climb_get_ref_not_curr(struct thread *t) {
308 if (t != thread_get_current())
309 return thread_get(obj: t);
310
311 return true;
312}
313
314/* Fine to thread_put here since we don't hold the scheduler lock */
315static void climb_drop_ref_not_curr(struct thread *t) {
316 if (t != thread_get_current())
317 thread_put(t);
318}
319
320static void climb_handle_act(struct thread *t, struct climb_handle *h,
321 void (*act)(struct thread *,
322 struct climb_handle *),
323 bool lock) {
324 if (t == thread_get_current()) {
325 climb_handle_act_self(t, h, act);
326 } else {
327 climb_handle_act_other(t, ch: h, act, lock);
328 }
329}
330
331static void climb_handle_remove_internal(struct climb_handle *h, bool lock) {
332 /* We might not always have a ref to the thread here.
333 * If the handle we are given is completely unused, this is because
334 * the thread we are removing from is NOT a timesharing thread.
335 *
336 * This means we can safely leave and no-op */
337 if (h->applied_pressure_internal == 0) {
338 kassert(list_empty(&h->list));
339 return;
340 }
341
342 struct thread *t = h->given_to;
343 climb_handle_act(t, h, act: remove_handle, lock);
344 h->given_to = NULL;
345 climb_drop_ref_not_curr(t);
346}
347
348static void climb_handle_apply_internal(struct thread *t,
349 struct climb_handle *h, bool lock) {
350 if (!climb_get_ref_not_curr(t))
351 return;
352
353 climb_handle_act(t, h, act: apply_handle, lock);
354 h->given_to = t;
355}
356
357void climb_handle_apply(struct thread *t, struct climb_handle *h) {
358 climb_handle_apply_internal(t, h, false);
359}
360
361void climb_handle_apply_locked(struct thread *t, struct climb_handle *h) {
362 climb_handle_apply_internal(t, h, true);
363}
364
365void climb_handle_remove(struct climb_handle *h) {
366 climb_handle_remove_internal(h, false);
367}
368
369void climb_handle_remove_locked(struct climb_handle *h) {
370 climb_handle_remove_internal(h, true);
371}
372
373void climb_thread_remove(struct thread *t) {
374
375 enum irql irql_out;
376 struct scheduler *sched = thread_get_scheduler(t, sirql_out: &irql_out);
377
378 struct climb_thread_state *cts = &t->climb_state;
379 struct rbt *tree = &sched->climb_threads;
380 struct rbt_node *node = &cts->climb_node;
381
382 bool put = false;
383 if (rbt_has_node(tree, node)) {
384 climb_info("Removing from tree %p", cts);
385 rbt_delete(tree, z: node);
386 cts->pressure_periods = 0;
387 cts->on_climb_tree = false;
388 put = true;
389 }
390
391 spin_unlock(&sched->lock, irql_out);
392
393 /* OK outside of the scheduler lock */
394 if (put)
395 thread_put(t);
396}
397
398static struct climb_budget climb_budget_from_summary(struct climb_summary *s) {
399 struct climb_budget b;
400
401 kassert(s->nthreads);
402 size_t boost_scale = CLIMB_GLOBAL_BOOST_SCALE(s->nthreads);
403 b.max_boost_levels =
404 fx_to_int(x: fx_mul(a: s->total_pressure_ewma, b: fx_from_int(x: boost_scale)));
405
406 int32_t max = s->nthreads * CLIMB_BOOST_LEVELS;
407 CLAMP(b.max_boost_levels, CLIMB_MIN_GLOBAL_BOOST, max);
408
409 b.remaining = b.max_boost_levels;
410 return b;
411}
412
413static void climb_apply_budget(struct scheduler *sched,
414 struct climb_budget *b) {
415 struct rbt_node *node;
416
417 rbt_for_each_reverse(node, &sched->climb_threads) {
418 if (b->remaining <= 0)
419 break;
420
421 struct climb_thread_state *cts =
422 climb_thread_state_from_tree_node(node);
423
424 /* NOTE: threads can get boosted around but we keep them in CLIMB.
425 * This is to allow them to still maintain their boosts after they
426 * return to TS, however, we still boost any threads within CLIMB,
427 * and treat them as if they are all TS threads to allow for a smooth
428 * return once a boosted thread comes back to being TS */
429
430 int32_t desired = cts->wanted_boost;
431 int32_t granted = MIN(desired, b->remaining);
432
433 cts->effective_boost = granted;
434 b->remaining -= granted;
435 }
436}
437
438/* This is our decay policy after a thread is removed from CLIMB.
439 *
440 * Because the boost is represented in part by an EWMA, it doesn't
441 * sharply drop when all pressure is released, but rather, gradually
442 * decays. This allows us to have smoother boost periods of threads,
443 * to prevent threads from switching between priority zones and
444 * inflicting costs on latency and consistency.
445 *
446 * Our policy for boost decay is as follows:
447 * When a thread has all of its pressure sources removed,
448 * it sets `pressure_periods` to -1.
449 *
450 * Upon subsequent passes within CLIMB's per-period work,
451 * this number decays by one. For example, if a thread has
452 * spent two periods in decay, it would be -2.
453 *
454 * Eventually, a thread will lose all of its boost, and
455 * when this happens (i.e. when `wanted_boost` drops to 0),
456 * the thread is removed from CLIMB accounting.
457 *
458 * However, there will come a time where too many periods have
459 * elapsed under decay. When this happens, the thread is forcibly
460 * removed. (CLIMB_MAX_DECAY_PERIODS)
461 *
462 */
463static void maybe_remove_node(struct rbt *tree, struct climb_thread_state *cts,
464 struct list_head *tlh) {
465 struct rbt_node *node = &cts->climb_node;
466 bool remove = false;
467
468 if (cts->pressure_periods < -CLIMB_MAX_DECAY_PERIODS)
469 remove = true;
470
471 if (cts->wanted_boost == 0)
472 remove = true;
473
474 if (remove) {
475 climb_info("Removing from tree %p", cts);
476 rbt_delete(tree, z: node);
477 cts->pressure_periods = 0;
478 cts->on_climb_tree = false;
479 cts->was_pinned =
480 thread_pin(container_of(cts, struct thread, climb_state));
481 list_add_tail(new: &cts->tmp_list_node, head: tlh);
482 } else {
483 cts->pressure_periods--;
484 }
485}
486
487static struct climb_summary summarize_and_advance(struct rbt *tree,
488 struct list_head *tlh) {
489 struct climb_summary ret = {0};
490 struct climb_thread_state *iter;
491 struct rbt_node *node, *tmp;
492
493 /* Sum it all up */
494 rbt_for_each_safe(node, tmp, tree) {
495 iter = climb_thread_state_from_tree_node(node);
496 update_fields(cts: iter);
497 ret.nthreads++;
498
499 ret.total_pressure_ewma += iter->pressure_ewma;
500
501 if (iter->pressure_periods > 0) {
502 ret.total_periods_spent += iter->pressure_periods;
503 iter->pressure_periods++;
504 } else {
505 maybe_remove_node(tree, cts: iter, tlh);
506 }
507 }
508
509 return ret;
510}
511
512void climb_per_period_hook() {
513 struct scheduler *sched = smp_core_scheduler();
514 enum irql irql = spin_lock_irq_disable(&sched->lock);
515
516 if (rbt_empty(tree: climb_tree_local())) {
517 spin_unlock(&sched->lock, irql);
518 return;
519 }
520
521 LIST_HEAD(threads_to_drop);
522
523 struct climb_summary summary =
524 summarize_and_advance(tree: climb_tree_local(), tlh: &threads_to_drop);
525 struct climb_budget budget = climb_budget_from_summary(s: &summary);
526 climb_apply_budget(sched: smp_core_scheduler(), b: &budget);
527
528 spin_unlock(&sched->lock, irql);
529
530 struct thread *tmp, *iter;
531 list_for_each_entry_safe(iter, tmp, &threads_to_drop,
532 climb_state.tmp_list_node) {
533 list_del_init(entry: &iter->climb_state.tmp_list_node);
534 if (!iter->climb_state.was_pinned)
535 thread_unpin(t: iter);
536
537 thread_put(t: iter);
538 }
539}
540
541void climb_thread_init(struct thread *t) {
542 struct climb_thread_state *cts = &t->climb_state;
543 cts->on_climb_tree = false;
544 cts->boost_ewma = FX(0);
545 cts->wanted_boost = 0;
546 cts->pressure_periods = 0;
547 INIT_LIST_HEAD(list: &cts->handles);
548 cts->direct_pressure = 0;
549 cts->indirect_pressure = 0;
550 rbt_init_node(n: &cts->climb_node);
551 struct climb_handle *ch = &cts->handle;
552 ch->name = t->name;
553 ch->applied_pressure_internal = 0;
554 ch->kind = CLIMB_PRESSURE_INDIRECT;
555 ch->given_by = t;
556 ch->given_to = NULL;
557 ch->pressure_source = NULL;
558 INIT_LIST_HEAD(list: &ch->list);
559}
560
561void climb_post_migrate_hook(struct thread *t, size_t old_cpu, size_t new_cpu) {
562 /* Locks are already held */
563 struct scheduler *old = global.schedulers[old_cpu];
564 struct scheduler *new = global.schedulers[new_cpu];
565
566 if (!rbt_has_node(tree: &old->climb_threads, node: &t->climb_state.climb_node)) {
567 kassert(t->climb_state.on_climb_tree == false);
568 kassert(t->climb_state.pressure_periods == 0);
569 return;
570 }
571
572 climb_warn("Migrating %p", &t->climb_state);
573
574 /* Migrate and recompute */
575 rbt_delete(tree: &old->climb_threads, z: &t->climb_state.climb_node);
576 rbt_insert(tree: &new->climb_threads, new_node: &t->climb_state.climb_node);
577}
578
579/* This is how we key our red black tree.
580 *
581 * 31.. .... .... .... .... .... .... ...0
582 *
583 *
584 * Our 32 bit fixed point representation uses the upper word as the "integer"
585 * part and the lower word as the "decimal" part. This is how climb_pressure_t
586 * is represented. However, we want to sort our threads in this tree as not
587 * just a climb_pressure_t, but also with their amount of elapsed periods.
588 *
589 * This is because sorting based on just climb_pressure_t will favor high
590 * pressure threads, which can potentially starve lower pressure threads
591 * that have been waiting for longer periods of time from a boost.
592 *
593 * climb_pressure_t is only ever a value between 0 and 1 in fixed point,
594 * thus we take the approach of shifting in the pressure_periods by
595 * a certain shift so that it contributes to the ordering of the tree.
596 *
597 * 31.. .... .... .... .... .... .... ...0
598 * S
599 *
600 * The "S" represents where the lowest bit of the pressure periods would be
601 * placed. This effectively means that every period of elapsed pressure
602 * is equal to 0.5 climb_pressure_t points, and means that two periods
603 * would result in a single maximum climb_pressure_t of pressure.
604 */
605size_t climb_get_thread_data(struct rbt_node *n) {
606 struct climb_thread_state *cts = climb_thread_state_from_tree_node(n);
607 return cts->pressure_periods * (1 << CLIMB_PRESSURE_KEY_SHIFT) +
608 climb_thread_total_pressure(cts);
609}
610
611int32_t climb_cmp_threads(const struct rbt_node *a, const struct rbt_node *b) {
612 int32_t ca = climb_get_thread_data(n: (struct rbt_node *) a);
613 int32_t cb = climb_get_thread_data(n: (struct rbt_node *) b);
614 return ca - cb;
615}
616