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