1/* @title: Writer to Reader Boosting */
2#pragma once
3#include <math/hash.h>
4#include <structures/hlist.h>
5#include <sync/rwlock_types.h>
6#include <thread/thread_types.h>
7
8/*
9 * wroost "writer reader boost" portmanteau
10 *
11 * Implementing writer to reader boosting for rwlocks is quite tricky,
12 * especially for turnstile-backed ones where you don't get extra data
13 * to store lists of threads.
14 *
15 * Lock side stuff:
16 *
17 * Thus, this is a sort of lazy priority ceiling. The idea is this:
18 * we store a hash table where each bucket has no hlist, but rather,
19 * keeps a set of 4 16-bit counters and a CPU mask.
20 *
21 * We hash every lock to store a small 'counting bloom filter'
22 * within each thread. We also keep a max_boost which is the
23 * maximum of all rwlock's maximum priorities to mitigate excess
24 * boosting that could be pathological.
25 *
26 * Then, writers hash into the table and bump the counter that
27 * corresponds to their perceived priority.
28 *
29 * Scheduler side stuff:
30 *
31 * Every CPU stores 256 x 16 bit counters that indicate the number of threads
32 * with a given ID (coarse entries are fanned across their respective
33 * sub-buckets) read-locked.
34 *
35 * When one of these counters passes the 0 <-> 1 transition boundary, it
36 * sets/clears a CPU mask in the corresponding global hash table bucket.
37 *
38 * Migrations also alter the CPU masks if they cross a transition boundary,
39 * and do so by first setting the new bit and then clearing the old one.
40 *
41 *
42 *
43 *
44 *
45 */
46
47/* Thread data */
48#define WROOST_BITS_PER_COUNTER 2
49#define WROOST_THREAD_MAP_DEPTH 32
50#define WROOST_COUNTER_MAX 0x3
51#define WROOST_COUNTER_MASK 0x3
52
53#define WROOST_MIN_BUCKET_COUNT 256U
54#define WROOST_MAX_BUCKET_COUNT 32768U
55#define WROOST_BUCKETS_PER_CPU_MULT 16U
56#define WROOST_THREAD_COUNTERS 32
57#define WROOST_FINE_ENTRY_COUNT 4
58#define WROOST_FINE_VALID_MASK ((1U << WROOST_FINE_ENTRY_COUNT) - 1U)
59#define WROOST_THREAD_COUNTER_BITS (WROOST_THREAD_COUNTERS * 2)
60#define WROOST_THREAD_COUNTER_BYTES (WROOST_THREAD_COUNTER_BITS / BITS_PER_BYTE)
61
62/* Percpu data */
63#define WROOST_THREAD_MAP_OVERFLOW ((struct thread *) (UINTPTR_MAX))
64
65typedef uint16_t wroost_id_t;
66typedef uint8_t wroost_counter_t;
67
68static_assert(BITS_NEEDED(WROOST_THREAD_COUNTERS - 1) == 5);
69
70static_assert(BIT_SIZEOF(wroost_id_t) >= BITS_NEEDED(WROOST_THREAD_COUNTERS),
71 "wroost_id_t needs to be wider");
72
73/* Writers are a simple state machine.
74 *
75 * NONE = nothing happening
76 * WANT = "I want a lock"
77 * WAIT = "I am waiting for a lock"
78 * BUMP = "I have yielded and bumped counters"
79 *
80 * WANT and WAIT are set in the thread's context, and BUMP is set immediately
81 * after the WAIT reaches the switch out function.
82 *
83 * We leave it at BUMP throughout a critical section,*/
84enum wroost_writer_state : uint8_t {
85 WROOST_WRITER_NONE,
86 WROOST_WRITER_WANT,
87 WROOST_WRITER_WAIT,
88 WROOST_WRITER_BUMP,
89};
90
91enum wroost_state {
92 WROOST_DPC_IDLE = 0,
93 WROOST_DPC_PENDING = 1,
94 WROOST_DPC_ACTIVE = 1 << 1,
95};
96
97struct wroost_kicks {
98 bool need_kicks;
99 struct cpu_mask cpus;
100 wroost_id_t lock_id;
101};
102
103struct wroost_process_result {
104 bool restart;
105
106 /* seen_data marks the lock IDs that the code has already
107 * processed, at the bitmap word granularity. This is so
108 * that if the pending process needs to restart, it
109 * remains aware of what had already been processed, so
110 * it can merge it with potentially new bits
111 * and re-check and boost (since restart happens
112 * due to a writer boosting a reader on calling CPU) */
113 bitmap_word_t *seen_data;
114};
115
116/* Protected by scheduler->lock */
117struct wroost_percpu_data {
118 atomic(enum wroost_state) state;
119 cpu_id_t id;
120
121 /* This keeps track of the number of READY threads on this CPU's
122 * runqueues of every given lock ID. Notably, it does NOT
123 * keep track of RUNNING threads OR threads that were going to block.
124 *
125 * Upon switch in, if a thread has any rwlocks held as a reader,
126 * it "contributes", and when leaving, it "withdraws" its counts
127 * added.
128 *
129 * However, the threads only contribute 1 per lock maximum,
130 * even if its 2-bit counter is more than 1. The intent here is to
131 * simply track "any thread", not "exact counter", so we only
132 * need every thread to contribute 1 for the count if it has
133 * that lock ID held as a reader.
134 *
135 * We need this because this is what allows us to make the
136 * 0 <-> 1 switch for the bitmap per-lock-ID
137 */
138 uint8_t *rq_bucket_counts;
139
140 /* Not actually a hashmap, it's just the number of counters,
141 * where precise entries get their coarse entry counter */
142 struct hlist_head thread_map[WROOST_THREAD_COUNTERS];
143
144 /* Since thread_map is guaranteed to only have single lock readers */
145 struct hlist_head multi_lock_readers;
146
147 /* Readers that happen to be blocked on a turnstile go here. This is
148 * because such readers need to propagate their priorities, which
149 * cannot happen under sched->lock, but can under wroost_lock (and
150 * that is the sole purpose that lock actually exists).
151 *
152 * Readers enter blocked_ts_readers on switch-out,
153 * and exit it on switch-in, both of which cannot happen during
154 * the DPC that iterates through this.
155 *
156 * Migrations are not a concern here because these threads do not
157 * exist in the runqueues, and there is thus no way to have
158 * obtained them for a migration. These threads must also
159 * be woken on the CPU that they went to sleep on for this reason. */
160 struct hlist_head blocked_ts_readers;
161
162 /* Set on switch-out when blocked_ts_reader gets boosted */
163 bool ts_requeue_pending;
164 atomic(bitmap_word_t) * pending_bitmap;
165
166 struct wroost_process_result process_result;
167
168 /* These primarily serve the purpose of implementing multi-hop.
169 *
170 * In the DPC, some readers are also writers, and upon a priority change,
171 * they will also need to go bother relevant readers. However, this all
172 * happens deep down in the scheduler lock, so DPCs can't be
173 * arbitrarily sent (deadlock). Thus, we merge all the CPU masks into
174 * a single one, and set bits in in_dpc_deferred_ids. The idea
175 * is that merging all of this together means that we may
176 * unnecessarily IPI some CPUs, but we will never have a false negative,
177 * and in the common case, this won't be that bad since only a lock
178 * or two of this kind will be held */
179 bitmap_word_t *in_dpc_deferred_ids; /* Bits represent lock IDs */
180 struct cpu_mask in_dpc_deferred_cpus;
181
182 struct dpc boost_dpc;
183 struct cpu_mask dpc_enqueue_deferred;
184 wroost_id_t writer_lock_id; /* So we know what to set for deferred DPCS */
185};
186
187struct wroost_fine_entry {
188 wroost_id_t lock_id; /* Shift this right by WROOST_FINE_INDEX_SHIFT
189 * to get the coarse index of the fine entry */
190};
191
192/*
193 * There's a key invariant with fine_entries:
194 *
195 * ====================================================================
196 * A counter is either FULLY represented in fine_entries, or completely
197 * unrepresented within fine_entries.
198 * ====================================================================
199 *
200 * The reason why:
201 *
202 * If 3/4 fine_entries are taken up, and a counter wants to allocate
203 * two more, then it ends up with a split: one of its contributing
204 * numbers in the counter is in the fine_entries, and one isn't.
205 *
206 * This means that the boost HAS to use the coarse entry, since
207 * otherwise, we risk a false negative, which would be completely
208 * against the premise of wroost.
209 *
210 * Thus, that extra fine_entry is wasted on a lock ID that doesn't
211 * use it. So, this invariant keeps all fine entries useful.
212 */
213struct wroost_thread_data {
214 struct hlist_node map_node;
215
216 /* Reader */
217 wroost_counter_t counters[WROOST_THREAD_COUNTER_BYTES];
218 struct wroost_fine_entry fine_entries[WROOST_FINE_ENTRY_COUNT];
219 uint8_t read_nesting_depth;
220
221 /* Writer */
222 wroost_id_t want_lock_id;
223
224 enum wroost_writer_state writer_state;
225
226 /* Boosts: applies to the readers */
227
228 /* boost_class_ceil is the ceil that the writer->reader boosts contribute.
229 * There is only one, and it is the maximum of any of the lock IDs it holds.
230 *
231 * max_boost serves a completely different role. Every rwlock is
232 * instantiated with a fixed maximum on the highest thread priority class
233 * that can enter the lock. max_boost is the maximum of all of these.
234 * The idea is that if an URGENT thread blocks on a rwlock with a maximum
235 * of RT, that code will panic.
236 *
237 * Thus, if we encounter a thread that seems
238 * to hold an ID where the urgent counter is >= 1, if this max_boost
239 * is at RT, we actually *don't* boost to urgent, and boost to what's
240 * further down (not necessarily RT either). It's essentially a way
241 * to cheaply verify that a big boost does NOT belong to us,
242 * because if it did, the kernel would've crashed long before.
243 */
244 enum thread_prio_class max_boost : THREAD_PRIO_CLASS_BIT_COUNT;
245
246 /* Whether this wroost_thread_data has
247 * contributed to the thread's class_floors */
248 bool contributed_floor : 1; /* Set by scheduler */
249 bool in_blocked_ts_list : 1;
250
251 /* TODO: use this to implement the optimization of knowing
252 * the readers cannot be of lower priority */
253 bool need_bump : 1;
254
255 /* Tracks which of the 4 fine_entries are active so index == 0
256 * does not get interpreted being a free slot */
257 uint8_t fine_valid : WROOST_FINE_ENTRY_COUNT;
258
259 enum thread_prio_class floor : THREAD_PRIO_CLASS_BIT_COUNT;
260};
261ct_assert_struct_size_eq(wroost_thread_data, 40);
262
263struct wroost_bucket {
264 /* "tally", so as to not conflict with "counter":
265 *
266 * 16-bit 2 * prio_class offset counters of owner prios */
267 atomic_uint64_t raw_tally;
268
269 /* 2 bits per CPU for 2 bits per prio class */
270
271 /* clang-format is very eager to format this as a pointer (??)
272 * TODO: Maybe this is a bug upstream */
273
274 /* clang-format off */
275 BITMAP_DECLARE_ATOMIC(rq_min_prio, THREAD_PRIO_CLASS_BIT_COUNT * CPU_MASK_BITS);
276 /* clang-format on */
277};
278
279struct wroost_hash_table {
280 struct wroost_bucket *buckets cc_counted_by(bucket_count);
281 size_t bucket_count;
282};
283
284enum thread_prio_class wroost_compute_ceil(struct wroost_thread_data *wtd,
285 enum thread_prio_class min);
286void wroost_pre_acquire(struct rwlock *lock, enum rwlock_acquire_type type);
287void wroost_post_acquire(struct rwlock *lock, enum rwlock_acquire_type type);
288void wroost_post_release(struct rwlock *lock, enum rwlock_acquire_type type);
289/* Separate from switch_in. this runs deferred DPC
290 * notifications/IPIs onto the other CPUs */
291void wroost_scheduler_switch_in_hook(void);
292void wroost_switch_in(struct thread *t);
293
294void wroost_switch_out(struct thread *t);
295void wroost_pre_wait(struct thread *curr);
296void wroost_post_wait(struct thread *curr);
297void wroost_post_migrate_hook(struct thread *t, cpu_id_t from, cpu_id_t to);
298
299size_t wroost_kick(struct wroost_kicks *kicks);
300bool wroost_merge_kicks(struct wroost_percpu_data *pcd,
301 struct wroost_kicks *kicks);
302
303struct wroost_kicks cc_warn_unused_result
304wroost_post_prio_change_locked(struct thread *t, enum thread_prio_class old,
305 enum thread_prio_class new);
306
307void wroost_init(void);
308void wroost_scheduler_init(struct scheduler *sched);
309