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 <thread/thread.h>
8
9#include "internal.h"
10
11void climb_per_period_hook();
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_DECLARE(climb, .flags = LOG_SITE_PRINT | 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 .show_args = true}));
26
27LOG_HANDLE_DECLARE_DEFAULT(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 inline 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}
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_state *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_state *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_state);
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_state *cts) {
152 size_t agg = 0;
153 struct list_head *iter;
154 list_for_each(iter, &cts->handles) agg++;
155 return agg;
156}
157
158/*
159 *
160 * if direct pressure:
161 * new_direct_pressure = direct_pressure + delta *
162 * (direct_max − direct_pressure)
163 * if indirect pressure:
164 * scale = max(1 - direct_pressure, indirect_min_scale)
165 * scaled_delta = delta * scale
166 * new_indirect_pressure = indirect_pressure +
167 * scaled_delta *
168 * (indirect_max - indirect_pressure)
169 */
170static void apply_handle_pressures(struct thread *t, struct climb_handle *ch) {
171 struct climb_thread_state *cts = &t->climb_state;
172
173 climb_pressure_t delta = ch->pressure;
174
175 if (t == thread_get_current()) {
176 kassert(ch->kind == CLIMB_PRESSURE_DIRECT);
177 climb_pressure_t old = cts->direct_pressure;
178
179 climb_pressure_t newp =
180 climb_accumulate(p: old, delta, CLIMB_DIRECT_PRESSURE_MAX);
181
182 ch->applied_pressure_internal = newp - old;
183 kassert(newp - old);
184 climb_info("Applying pressure %u to %p", newp - old, cts);
185 cts->direct_pressure = newp;
186 return;
187 }
188
189 kassert(ch->kind == CLIMB_PRESSURE_INDIRECT);
190
191 /* indirect pressure */
192 climb_pressure_t scale =
193 climb_pressure_scale_indirect(direct: cts->direct_pressure);
194
195 climb_pressure_t scaled_delta = fx_mul(a: delta, b: scale);
196
197 climb_pressure_t old = cts->indirect_pressure;
198 climb_pressure_t newp =
199 climb_accumulate(p: old, delta: scaled_delta, CLIMB_INDIRECT_PRESSURE_MAX);
200
201 ch->applied_pressure_internal = newp - old;
202 kassert(newp - old);
203 climb_info("Applying pressure %u to %p", newp - old, cts);
204 cts->indirect_pressure = newp;
205}
206
207/* This assumes that the thread is already properly locked/protected */
208static void apply_handle(struct thread *t, struct climb_handle *ch) {
209 kassert(list_empty(&ch->list));
210
211 list_add_tail(new: &ch->list, head: &t->climb_state.handles);
212 apply_handle_pressures(t, ch);
213 struct climb_thread_state *cts = &t->climb_state;
214
215 climb_info("Apply handle on %p, %u", cts, climb_count_handles(cts));
216
217 /* If there was already a giver, like with indirect boosts, we don't
218 * change it. Otherwise, we do, and say we are the giver */
219 ch->given_by = ch->given_by ? ch->given_by : thread_get_current();
220
221 /* Was previously not on tree */
222 if (cts->pressure_periods == 0) {
223 cts->pressure_periods = 1;
224 kassert(!cts->on_climb_tree);
225 struct scheduler *sched = thread_get_scheduler_unsafe(t);
226 struct rbt *tree = &sched->climb_threads;
227
228 /* Get a reference for the tree */
229 kassert(thread_get(t));
230 climb_info("Insert %p to tree", cts);
231 rbt_insert(tree, new_node: &cts->climb_node);
232 cts->on_climb_tree = true;
233 } else if (cts->pressure_periods < 0) {
234 /* It was previously on decay... all we need to do
235 * is tell the thread to start pressure again,
236 * and set pressure_periods to 1 */
237 cts->pressure_periods = 1;
238 }
239}
240
241static void remove_handle(struct thread *t, struct climb_handle *ch) {
242 struct climb_thread_state *cts = &t->climb_state;
243 kassert(ch->given_by == thread_get_current());
244
245 if (ch->applied_pressure_internal == 0) {
246 climb_warn("No-op handle removed from %p", cts);
247 return;
248 }
249
250 if (ch->kind == CLIMB_PRESSURE_DIRECT) {
251 cts->direct_pressure -= ch->applied_pressure_internal;
252 } else {
253 kassert(ch->kind == CLIMB_PRESSURE_INDIRECT);
254 cts->indirect_pressure -= ch->applied_pressure_internal;
255 }
256
257 ch->applied_pressure_internal = 0;
258 list_del_init(entry: &ch->list);
259
260 climb_info("Remove handle on %p (thread %p), %u left", cts, t,
261 climb_count_handles(cts));
262
263 if (list_empty(head: &cts->handles)) {
264 /* This thread is done. Let it decay now */
265 cts->pressure_periods = -1;
266 climb_info("Begin decay on %p", cts);
267 }
268}
269
270static void climb_handle_act_self(struct thread *t, struct climb_handle *h,
271 void (*act)(struct thread *,
272 struct climb_handle *h)) {
273 enum irql irql = IRQL_PASSIVE_LEVEL;
274 bool irql_change = false;
275 if (irql_get() < IRQL_DISPATCH_LEVEL) {
276 irql = irql_raise(new_level: IRQL_DISPATCH_LEVEL);
277 irql_change = true;
278 }
279
280 kassert(t == thread_get_current());
281 act(t, h);
282
283 if (irql_change)
284 irql_lower(old_level: irql);
285}
286
287static void climb_handle_act_other(struct thread *t, struct climb_handle *ch,
288 void (*act)(struct thread *,
289 struct climb_handle *),
290 bool lock) {
291
292 /* thread cannot disappear under us */
293 enum irql irql = IRQL_PASSIVE_LEVEL;
294
295 struct scheduler *sch = NULL;
296
297 if (!lock)
298 sch = thread_get_scheduler(t, sirql_out: &irql);
299
300 act(t, ch);
301
302 if (!lock)
303 spin_unlock(lock: &sch->lock, old: irql);
304}
305
306static bool climb_get_ref_not_curr(struct thread *t) {
307 if (t != thread_get_current())
308 return thread_get(obj: t);
309
310 return true;
311}
312
313/* Fine to thread_put here since we don't hold the scheduler lock */
314static void climb_drop_ref_not_curr(struct thread *t) {
315 if (t != thread_get_current())
316 thread_put(t);
317}
318
319static void climb_handle_act(struct thread *t, struct climb_handle *h,
320 void (*act)(struct thread *,
321 struct climb_handle *),
322 bool lock) {
323 if (t == thread_get_current()) {
324 climb_handle_act_self(t, h, act);
325 } else {
326 climb_handle_act_other(t, ch: h, act, lock);
327 }
328}
329
330static void climb_handle_remove_internal(struct climb_handle *h, bool lock) {
331 /* We might not always have a ref to the thread here.
332 * If the handle we are given is completely unused, this is because
333 * the thread we are removing from is NOT a timesharing thread.
334 *
335 * This means we can safely leave and no-op */
336 if (h->applied_pressure_internal == 0) {
337 kassert(list_empty(&h->list));
338 return;
339 }
340
341 struct thread *t = h->given_to;
342 climb_handle_act(t, h, act: remove_handle, lock);
343 h->given_to = NULL;
344 climb_drop_ref_not_curr(t);
345}
346
347static void climb_handle_apply_internal(struct thread *t,
348 struct climb_handle *h, bool lock) {
349 if (!climb_get_ref_not_curr(t))
350 return;
351
352 climb_handle_act(t, h, act: apply_handle, lock);
353 h->given_to = t;
354}
355
356void climb_handle_apply(struct thread *t, struct climb_handle *h) {
357 climb_handle_apply_internal(t, h, false);
358}
359
360void climb_handle_apply_locked(struct thread *t, struct climb_handle *h) {
361 climb_handle_apply_internal(t, h, true);
362}
363
364void climb_handle_remove(struct climb_handle *h) {
365 climb_handle_remove_internal(h, false);
366}
367
368void climb_handle_remove_locked(struct climb_handle *h) {
369 climb_handle_remove_internal(h, true);
370}
371
372void climb_thread_remove(struct thread *t) {
373
374 enum irql irql_out;
375 struct scheduler *sched = thread_get_scheduler(t, sirql_out: &irql_out);
376
377 struct climb_thread_state *cts = &t->climb_state;
378 struct rbt *tree = &sched->climb_threads;
379 struct rbt_node *node = &cts->climb_node;
380
381 bool put = false;
382 if (rbt_has_node(tree, node)) {
383 climb_info("Removing from tree %p", cts);
384 rbt_delete(tree, z: node);
385 cts->pressure_periods = 0;
386 cts->on_climb_tree = false;
387 put = true;
388 }
389
390 spin_unlock(lock: &sched->lock, old: irql_out);
391
392 /* OK outside of the scheduler lock */
393 if (put)
394 thread_put(t);
395}
396
397static struct climb_budget climb_budget_from_summary(struct climb_summary *s) {
398 struct climb_budget b;
399
400 kassert(s->nthreads);
401 size_t boost_scale = CLIMB_GLOBAL_BOOST_SCALE(s->nthreads);
402 b.max_boost_levels =
403 fx_to_int(x: fx_mul(a: s->total_pressure_ewma, b: fx_from_int(x: boost_scale)));
404
405 int32_t max = s->nthreads * CLIMB_BOOST_LEVELS;
406 CLAMP(b.max_boost_levels, CLIMB_MIN_GLOBAL_BOOST, max);
407
408 b.remaining = b.max_boost_levels;
409 return b;
410}
411
412static void climb_apply_budget(struct scheduler *sched,
413 struct climb_budget *b) {
414 struct rbt_node *node;
415
416 rbt_for_each_reverse(node, &sched->climb_threads) {
417 if (b->remaining <= 0)
418 break;
419
420 struct climb_thread_state *cts =
421 climb_thread_state_from_tree_node(node);
422
423 /* NOTE: threads can get boosted around but we keep them in CLIMB.
424 * This is to allow them to still maintain their boosts after they
425 * return to TS, however, we still boost any threads within CLIMB,
426 * and treat them as if they are all TS threads to allow for a smooth
427 * return once a boosted thread comes back to being TS */
428
429 int32_t desired = cts->wanted_boost;
430 int32_t granted = MIN(desired, b->remaining);
431
432 cts->effective_boost = granted;
433 b->remaining -= granted;
434 }
435}
436
437/* This is our decay policy after a thread is removed from CLIMB.
438 *
439 * Because the boost is represented in part by an EWMA, it doesn't
440 * sharply drop when all pressure is released, but rather, gradually
441 * decays. This allows us to have smoother boost periods of threads,
442 * to prevent threads from switching between priority zones and
443 * inflicting costs on latency and consistency.
444 *
445 * Our policy for boost decay is as follows:
446 * When a thread has all of its pressure sources removed,
447 * it sets `pressure_periods` to -1.
448 *
449 * Upon subsequent passes within CLIMB's per-period work,
450 * this number decays by one. For example, if a thread has
451 * spent two periods in decay, it would be -2.
452 *
453 * Eventually, a thread will lose all of its boost, and
454 * when this happens (i.e. when `wanted_boost` drops to 0),
455 * the thread is removed from CLIMB accounting.
456 *
457 * However, there will come a time where too many periods have
458 * elapsed under decay. When this happens, the thread is forcibly
459 * removed. (CLIMB_MAX_DECAY_PERIODS)
460 *
461 */
462static void maybe_remove_node(struct rbt *tree, struct climb_thread_state *cts,
463 struct list_head *tlh) {
464 struct rbt_node *node = &cts->climb_node;
465 bool remove = false;
466
467 if (cts->pressure_periods < -CLIMB_MAX_DECAY_PERIODS)
468 remove = true;
469
470 if (cts->wanted_boost == 0)
471 remove = true;
472
473 if (remove) {
474 climb_info("Removing from tree %p", cts);
475 rbt_delete(tree, z: node);
476 cts->pressure_periods = 0;
477 cts->on_climb_tree = false;
478 cts->was_pinned =
479 thread_pin(container_of(cts, struct thread, climb_state));
480 list_add_tail(new: &cts->tmp_list_node, head: tlh);
481 } else {
482 cts->pressure_periods--;
483 }
484}
485
486static struct climb_summary summarize_and_advance(struct rbt *tree,
487 struct list_head *tlh) {
488 struct climb_summary ret = {0};
489 struct climb_thread_state *iter;
490 struct rbt_node *node, *tmp;
491
492 /* Sum it all up */
493 rbt_for_each_safe(node, tmp, tree) {
494 iter = climb_thread_state_from_tree_node(node);
495 update_fields(cts: iter);
496 ret.nthreads++;
497
498 ret.total_pressure_ewma += iter->pressure_ewma;
499
500 if (iter->pressure_periods > 0) {
501 ret.total_periods_spent += iter->pressure_periods;
502 iter->pressure_periods++;
503 } else {
504 maybe_remove_node(tree, cts: iter, tlh);
505 }
506 }
507
508 return ret;
509}
510
511void climb_per_period_hook() {
512 struct scheduler *sched = smp_core_scheduler();
513 enum irql irql = spin_lock_irq_disable(lock: &sched->lock);
514
515 if (rbt_empty(tree: climb_tree_local())) {
516 spin_unlock(lock: &sched->lock, old: irql);
517 return;
518 }
519
520 LIST_HEAD(threads_to_drop);
521
522 struct climb_summary summary =
523 summarize_and_advance(tree: climb_tree_local(), tlh: &threads_to_drop);
524 struct climb_budget budget = climb_budget_from_summary(s: &summary);
525 climb_apply_budget(sched: smp_core_scheduler(), b: &budget);
526
527 spin_unlock(lock: &sched->lock, old: irql);
528
529 struct thread *tmp, *iter;
530 list_for_each_entry_safe(iter, tmp, &threads_to_drop,
531 climb_state.tmp_list_node) {
532 list_del_init(entry: &iter->climb_state.tmp_list_node);
533 if (!iter->climb_state.was_pinned)
534 thread_unpin(t: iter);
535
536 thread_put(t: iter);
537 }
538}
539
540void climb_thread_init(struct thread *t) {
541 struct climb_thread_state *cts = &t->climb_state;
542 cts->on_climb_tree = false;
543 cts->boost_ewma = FX(0);
544 cts->wanted_boost = 0;
545 cts->pressure_periods = 0;
546 INIT_LIST_HEAD(list: &cts->handles);
547 cts->direct_pressure = 0;
548 cts->indirect_pressure = 0;
549 rbt_init_node(n: &cts->climb_node);
550 struct climb_handle *ch = &cts->handle;
551 ch->name = t->name;
552 ch->applied_pressure_internal = 0;
553 ch->kind = CLIMB_PRESSURE_INDIRECT;
554 ch->given_by = t;
555 ch->given_to = NULL;
556 ch->pressure_source = NULL;
557 INIT_LIST_HEAD(list: &ch->list);
558}
559
560void climb_post_migrate_hook(struct thread *t, size_t old_cpu, size_t new_cpu) {
561 /* Locks are already held */
562 struct scheduler *old = global.schedulers[old_cpu];
563 struct scheduler *new = global.schedulers[new_cpu];
564
565 if (!rbt_has_node(tree: &old->climb_threads, node: &t->climb_state.climb_node)) {
566 kassert(t->climb_state.on_climb_tree == false);
567 kassert(t->climb_state.pressure_periods == 0);
568 return;
569 }
570
571 climb_warn("Migrating %p", &t->climb_state);
572
573 /* Migrate and recompute */
574 rbt_delete(tree: &old->climb_threads, z: &t->climb_state.climb_node);
575 rbt_insert(tree: &new->climb_threads, new_node: &t->climb_state.climb_node);
576}
577
578/* This is how we key our red black tree.
579 *
580 * 31.. .... .... .... .... .... .... ...0
581 *
582 *
583 * Our 32 bit fixed point representation uses the upper word as the "integer"
584 * part and the lower word as the "decimal" part. This is how climb_pressure_t
585 * is represented. However, we want to sort our threads in this tree as not
586 * just a climb_pressure_t, but also with their amount of elapsed periods.
587 *
588 * This is because sorting based on just climb_pressure_t will favor high
589 * pressure threads, which can potentially starve lower pressure threads
590 * that have been waiting for longer periods of time from a boost.
591 *
592 * climb_pressure_t is only ever a value between 0 and 1 in fixed point,
593 * thus we take the approach of shifting in the pressure_periods by
594 * a certain shift so that it contributes to the ordering of the tree.
595 *
596 * 31.. .... .... .... .... .... .... ...0
597 * S
598 *
599 * The "S" represents where the lowest bit of the pressure periods would be
600 * placed. This effectively means that every period of elapsed pressure
601 * is equal to 0.5 climb_pressure_t points, and means that two periods
602 * would result in a single maximum climb_pressure_t of pressure.
603 */
604size_t climb_get_thread_data(struct rbt_node *n) {
605 struct climb_thread_state *cts = climb_thread_state_from_tree_node(n);
606 return cts->pressure_periods * (1 << CLIMB_PRESSURE_KEY_SHIFT) +
607 climb_thread_total_pressure(cts);
608}
609