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_REINSERT_THRESHOLD 2
17#define CLIMB_GLOBAL_BOOST_SCALE(nt) (CLIMB_BOOST_LEVELS / nt)
18#define CLIMB_PRESSURE_KEY_SHIFT 15
19#define CLIMB_MAX_DECAY_PERIODS 20
20
21enum climb_pressure_kind {
22 CLIMB_PRESSURE_DIRECT,
23 CLIMB_PRESSURE_INDIRECT,
24};
25
26struct climb_handle {
27 char *name;
28 struct list_head list;
29 climb_pressure_t pressure;
30 climb_pressure_t applied_pressure_internal; /* If 0, this has not
31 * applied presssure */
32
33 enum climb_pressure_kind kind;
34
35 struct climb_source *pressure_source;
36 struct thread *given_by; /* Debugging */
37 struct thread *given_to;
38};
39
40struct climb_thread_state {
41 /* pressure */
42 climb_pressure_t direct_pressure; /* Contributed direct pressure */
43 climb_pressure_t indirect_pressure; /* Indirect pressure from others */
44 climb_pressure_t pressure_ewma; /* EWMA of pressure over time */
45
46 /* boost */
47 int32_t wanted_boost; /* 0..20, how much this thread "wants" */
48 fx32_32_t boost_ewma; /* EWMA of the wanted_boost_raw */
49 int32_t effective_boost; /* How much boosted (derived from wanted_boost_raw)
50 * this thread "gets". This exists because CLIMB
51 * will take into account the existence of other
52 * threads and their boosts and periods spent
53 * to compute the boost of one thread */
54
55 /* time */
56 int32_t pressure_periods; /* >=1 active, < 0 decaying, 0 inactive */
57
58 /* accounting */
59 struct list_head handles; /* active pressure handles */
60
61 /* scheduler integration */
62 bool on_climb_tree : 1; /* Used to logically verify things */
63 bool was_pinned : 1;
64
65 struct rbt_node climb_node;
66 struct list_head tmp_list_node; /* Bit of a funny field: This node exists
67 * because we need to call thread_put() when
68 * removing a thread from the tree, however,
69 * this cannot happen under the scheduler
70 * lock because it wakes the reaper thread
71 * which has the chance to acquire an
72 * arbitrary scheduler lock */
73
74 /* if this thread becomes a CLIMB source,
75 * what would it "apply"? */
76 struct climb_handle handle;
77};
78#define climb_thread_state_from_tree_node(tn) \
79 (container_of(tn, struct climb_thread_state, climb_node))
80
81struct climb_source {
82 char *name;
83 climb_pressure_t base;
84};
85
86/* Pressures */
87#define CLIMB_PRESSURE_THREAD_BASE FX(0.05)
88#define CLIMB_PRESSURE_IO_BASE FX(0.20)
89#define CLIMB_PRESSURE_LOCK_BASE FX(0.10)
90#define CLIMB_PRESSURE_MAX FX(1.0)
91#define CLIMB_PRESSURE(x) FX(x)
92
93/* Pressure space */
94#define CLIMB_PRESSURE_MAX FX(1.0)
95#define CLIMB_DIRECT_PRESSURE_MAX FX(1.0)
96#define CLIMB_INDIRECT_PRESSURE_MAX FX(1.0)
97
98/* Indirect pressure scaling */
99#define CLIMB_INDIRECT_MIN_SCALE FX(0.10)
100#define CLIMB_INDIRECT_WEIGHT FX(0.85)
101
102/* Boost space */
103#define CLIMB_BOOST_LEVEL_MAX 20
104
105/* EWMA smoothing */
106#define CLIMB_BOOST_EWMA_ALPHA FX(0.75)
107
108/* Pressure to boost shaping */
109#define CLIMB_PRESSURE_EXPONENT 3 /* cubic */
110#define CLIMB_PRESSURE_TO_BOOST_SCALE FX(8.0)
111
112#define CLIMB_SOURCE_EXTERN(name) extern struct climb_source __climb_src_##name
113#define CLIMB_SOURCE_CREATE(n, strname, b) \
114 struct climb_source __climb_src_##n = {.name = strname, .base = b}
115#define CLIMB_SOURCE(name) &(__climb_src_##name)
116
117climb_pressure_t climb_thread_applied_pressure(struct thread *t);
118climb_pressure_t climb_thread_compute_pressure_to_apply(struct thread *t);
119
120void climb_handle_apply(struct thread *t, struct climb_handle *h);
121void climb_handle_update(struct thread *t, struct climb_handle *h,
122 climb_pressure_t new_pressure);
123void climb_handle_remove(struct climb_handle *h);
124
125void climb_handle_apply_locked(struct thread *t, struct climb_handle *h);
126void climb_handle_remove_locked(struct climb_handle *h);
127
128void climb_recompute_pressure(struct thread *t);
129void climb_thread_remove(struct thread *t);
130void climb_thread_init(struct thread *t);
131void climb_post_migrate_hook(struct thread *t, size_t old_cpu, size_t new_cpu);
132size_t climb_get_thread_data(struct rbt_node *n);
133
134static inline struct climb_handle *
135climb_handle_init(struct climb_handle *ch, struct climb_source *cs,
136 enum climb_pressure_kind k) {
137 INIT_LIST_HEAD(list: &ch->list);
138 if (cs) {
139 ch->pressure = cs->base;
140 ch->name = cs->name;
141 ch->pressure_source = cs;
142 }
143
144 ch->kind = k;
145 ch->applied_pressure_internal = 0;
146 return ch;
147}
148