1/* @title: CLIMB framework */
2#pragma once
3#include <math/fixed.h>
4#include <stdbool.h>
5#include <stddef.h>
6#include <stdint.h>
7#include <structures/list.h>
8#include <structures/rbt.h>
9#include <thread/thread_types.h>
10
11typedef fx32_32_t climb_pressure_t;
12struct climb_handle;
13
14#define CLIMB_BOOST_LEVELS 20
15#define CLIMB_MIN_GLOBAL_BOOST 1
16#define CLIMB_GLOBAL_BOOST_SCALE(nt) (CLIMB_BOOST_LEVELS / nt)
17#define CLIMB_PRESSURE_KEY_SHIFT 31 /* one period == 0.5 pressure points */
18#define CLIMB_MAX_DECAY_PERIODS 20
19
20/* Pressures */
21#define CLIMB_PRESSURE_THREAD_BASE FX(0.05)
22#define CLIMB_PRESSURE_IO_BASE FX(0.20)
23#define CLIMB_PRESSURE_LOCK_BASE FX(0.10)
24#define CLIMB_PRESSURE(x) FX(x)
25
26/* Pressure space */
27#define CLIMB_PRESSURE_MAX FX(1.0)
28#define CLIMB_DIRECT_PRESSURE_MAX FX(1.0)
29#define CLIMB_INDIRECT_PRESSURE_MAX FX(1.0)
30
31/* Indirect pressure scaling */
32#define CLIMB_INDIRECT_MIN_SCALE FX(0.10)
33#define CLIMB_INDIRECT_WEIGHT FX(0.85)
34
35/* Boost space */
36#define CLIMB_BOOST_LEVEL_MAX 20
37
38/* EWMA smoothing */
39#define CLIMB_BOOST_EWMA_ALPHA FX(0.75)
40
41/* Pressure to boost shaping */
42#define CLIMB_PRESSURE_EXPONENT 3 /* cubic */
43#define CLIMB_PRESSURE_TO_BOOST_SCALE FX(8.0)
44enum climb_pressure_kind {
45 CLIMB_PRESSURE_DIRECT,
46 CLIMB_PRESSURE_INDIRECT,
47};
48
49struct climb_handle {
50 struct list_node list;
51 climb_pressure_t pressure;
52 climb_pressure_t applied_pressure_internal; /* If 0, this has not
53 * applied presssure */
54
55 enum climb_pressure_kind kind;
56
57#ifdef DEBUG_CLIMB
58 struct thread *given_by; /* Debugging */
59#endif
60
61 struct thread *given_to;
62};
63
64struct climb_thread_data {
65 /* pressure */
66 climb_pressure_t direct_pressure; /* Contributed direct pressure */
67 climb_pressure_t indirect_pressure; /* Indirect pressure from others */
68 climb_pressure_t pressure_ewma; /* EWMA of pressure over time */
69
70 /* boost */
71 int32_t wanted_boost; /* 0..20, how much this thread "wants" */
72 fx32_32_t boost_ewma; /* EWMA of the wanted_boost_raw */
73 int32_t effective_boost; /* How much boosted (derived from wanted_boost_raw)
74 * this thread "gets". This exists because CLIMB
75 * will take into account the existence of other
76 * threads and their boosts and periods spent
77 * to compute the boost of one thread */
78
79 /* time */
80 int32_t pressure_periods; /* >=1 active, < 0 decaying, 0 inactive */
81
82 /* accounting */
83 struct list_head handles; /* active pressure handles */
84
85 /* scheduler integration */
86 bool on_climb_tree : 1; /* Used to logically verify things */
87
88 struct rbt_node climb_node;
89
90 /* if this thread becomes a CLIMB source,
91 * what would it "apply"? */
92 struct climb_handle handle;
93};
94#define climb_thread_data_from_tree_node(tn) \
95 (container_of(tn, struct climb_thread_data, climb_node))
96
97struct climb_source {
98 char *name;
99 climb_pressure_t base;
100};
101
102#define CLIMB_SOURCE_EXTERN(name) extern struct climb_source __climb_src_##name
103#define CLIMB_SOURCE_CREATE(n, strname, b) \
104 struct climb_source __climb_src_##n = {.name = strname, .base = b}
105#define CLIMB_SOURCE(name) &(__climb_src_##name)
106
107climb_pressure_t climb_thread_applied_pressure(struct thread *t);
108climb_pressure_t climb_thread_compute_pressure_to_apply(struct thread *t);
109
110void climb_handle_apply(struct thread *t, struct climb_handle *h);
111void climb_handle_update(struct thread *t, struct climb_handle *h,
112 climb_pressure_t new_pressure);
113void climb_handle_remove(struct climb_handle *h);
114
115void climb_handle_apply_locked(struct thread *t, struct climb_handle *h);
116void climb_handle_remove_locked(struct climb_handle *h);
117
118void climb_recompute_pressure(struct thread *t);
119void climb_thread_remove(struct thread *t);
120void climb_thread_init(struct thread *t);
121void climb_post_migrate_hook(struct thread *t, size_t old_cpu, size_t new_cpu);
122size_t climb_get_thread_data(struct rbt_node *n);
123int32_t climb_cmp_threads(const struct rbt_node *a, const struct rbt_node *b);
124
125static inline struct climb_handle *
126climb_handle_init(struct climb_handle *ch, struct climb_source *cs,
127 enum climb_pressure_kind k) {
128 list_node_init(n: &ch->list);
129 if (cs)
130 ch->pressure = cs->base;
131
132 ch->kind = k;
133 ch->applied_pressure_internal = 0;
134 return ch;
135}
136