1#include <mem/alloc.h>
2#include <mem/nofail.h>
3#include <sch/sched.h>
4#include <sch/wroost.h>
5#include <sync/rwlock.h>
6#include <sync/turnstile.h>
7#include <thread/thread.h>
8
9#include "atomic.h"
10#include "internal.h"
11#include "sync/rwlock_internal.h"
12
13/* The way that fine entries work:
14 *
15 * Coarse entries are fixed, however, fine entries are dynamic based on
16 * hash_table.bucket_count. In order to derive a fine entry index shift,
17 * we figure out the number of bits that a coarse entry cannot cover.
18 *
19 * This is done through a
20 * BITS_NEEDED((bucket_count/WROOST_THREAD_COUNTERS)-1), as
21 * it represents the number of bits the thread counters miss.
22 */
23struct wroost_globals {
24 struct wroost_hash_table hash_table;
25 size_t fine_index_bits;
26 size_t fine_offset_mask;
27};
28
29struct wroost_globals wroost_global = {0};
30
31#define WROOST_KICK_UPDATE_PENDING (1)
32#define WROOST_KICK_SEND_DPCS (1 << 1)
33#define WROOST_COARSE_FACTOR \
34 (wroost_global.hash_table.bucket_count / WROOST_THREAD_COUNTERS)
35
36static size_t wroost_kick_cpus(struct cpu_mask *mask, wroost_id_t lock_id,
37 int options);
38static bool percpu_boost_kick(cpu_id_t target, wroost_id_t lock_id,
39 int options);
40
41static inline size_t bucket_count(void) {
42 return wroost_global.hash_table.bucket_count;
43}
44
45/* Counters are two bits. Index 0 is bit 0, index 1 is bit 2, index 2 is bit 4, etc. */
46static inline uint8_t wroost_get_counter(struct wroost_thread_data *wtd,
47 uint8_t index, uint8_t *byte_idx_out,
48 uint8_t *byte_offset_out) {
49 enforce_precond(index < WROOST_THREAD_COUNTERS);
50 uint8_t bits_per_ctr_word = BIT_SIZEOF(wroost_counter_t);
51 size_t bit_index = index * WROOST_BITS_PER_COUNTER;
52
53 if (byte_idx_out)
54 *byte_idx_out = bit_index / bits_per_ctr_word;
55
56 if (byte_offset_out)
57 *byte_offset_out = bit_index % bits_per_ctr_word;
58
59 return wtd->counters[bit_index / bits_per_ctr_word];
60}
61
62static inline wroost_counter_t
63wroost_read_counter(struct wroost_thread_data *wtd, uint8_t ctr_idx) {
64 uint8_t idx, offset;
65 wroost_counter_t ctr = wroost_get_counter(wtd, index: ctr_idx, byte_idx_out: &idx, byte_offset_out: &offset);
66 return (ctr >> offset) & WROOST_COUNTER_MASK;
67}
68
69static inline void wroost_write_counter(struct wroost_thread_data *wtd,
70 uint8_t ctr_idx, uint8_t new_ctr_val) {
71 enforce_precond((new_ctr_val & WROOST_COUNTER_MASK) == new_ctr_val);
72
73 uint8_t idx, offset;
74 wroost_counter_t ctr = wroost_get_counter(wtd, index: ctr_idx, byte_idx_out: &idx, byte_offset_out: &offset);
75 wroost_counter_t cleared = ctr & ~(WROOST_COUNTER_MASK << offset);
76 wroost_counter_t new = (new_ctr_val << offset) | cleared;
77 wtd->counters[idx] = new;
78}
79
80static inline uint8_t wroost_inc_counter(struct wroost_thread_data *wtd,
81 uint8_t ctr_idx,
82 wroost_counter_t *ctr_val) {
83 if ((*ctr_val = wroost_read_counter(wtd, ctr_idx)) == WROOST_COUNTER_MAX)
84 return WROOST_COUNTER_MAX;
85
86 wroost_write_counter(wtd, ctr_idx, new_ctr_val: *ctr_val + 1);
87 return *ctr_val + 1;
88}
89
90static inline uint8_t wroost_dec_counter(struct wroost_thread_data *wtd,
91 uint8_t ctr_idx) {
92 wroost_counter_t ctr_val;
93 if ((ctr_val = wroost_read_counter(wtd, ctr_idx)) == WROOST_COUNTER_MAX)
94 return WROOST_COUNTER_MAX;
95
96 enforce(ctr_val > 0, UNDERFLOW);
97 wroost_write_counter(wtd, ctr_idx, new_ctr_val: ctr_val - 1);
98 return ctr_val - 1;
99}
100
101static inline cc_maybe_unused uint16_t
102wroost_read_tally(struct wroost_bucket *bkt, enum thread_prio_class class) {
103 enforce(class < THREAD_PRIO_CLASS_COUNT);
104 uint64_t ret = atomic_load_acq(&bkt->raw_tally);
105 return (ret >> ((size_t) class * BIT_SIZEOF(uint16_t))) & UINT16_MAX;
106}
107
108static inline void wroost_move_tally(struct wroost_bucket *bkt,
109 enum thread_prio_class from,
110 enum thread_prio_class to) {
111#ifdef DEBUG_WROOST
112 for (int i = 0; i < THREAD_PRIO_CLASS_COUNT; i++)
113 enforce(wroost_read_tally(bkt, i) != UINT16_MAX, OVERFLOW);
114#endif
115
116 uint64_t inc_mask = BIT((size_t) to * BIT_SIZEOF(uint16_t));
117 uint64_t dec_mask = BIT((size_t) from * BIT_SIZEOF(uint16_t));
118 uint64_t delta = inc_mask - dec_mask;
119 atomic_fetch_add_release(&bkt->raw_tally, delta);
120}
121
122static inline wroost_id_t wroost_hash(struct rwlock *lock) {
123 return hash_pointer(ptr: lock) % wroost_global.hash_table.bucket_count;
124}
125
126static inline uint8_t wroost_fine_entry_index(struct wroost_fine_entry *ent) {
127 return ent->lock_id >> wroost_global.fine_index_bits;
128}
129
130static inline struct wroost_fine_entry *
131wroost_get_fine_entry(struct wroost_thread_data *wtd, uint8_t index) {
132 enforce(index < WROOST_THREAD_COUNTERS);
133 for (int i = 0; i < WROOST_FINE_ENTRY_COUNT; i++) {
134 if ((wtd->fine_valid & BIT(i)) &&
135 wroost_fine_entry_index(ent: &wtd->fine_entries[i]) == index)
136 return &wtd->fine_entries[i];
137 }
138
139 return NULL;
140}
141
142static inline void wroost_clear_fine_entry(struct wroost_thread_data *wtd,
143 int slot) {
144 enforce_precond(slot >= 0 && slot < WROOST_FINE_ENTRY_COUNT);
145 wtd->fine_entries[slot].lock_id = 0;
146 wtd->fine_valid &= ~BIT(slot);
147}
148
149static inline void wroost_evict_fine_entries(struct wroost_thread_data *wtd,
150 uint8_t index) {
151 for (int i = 0; i < WROOST_FINE_ENTRY_COUNT; i++) {
152 if ((wtd->fine_valid & BIT(i)) &&
153 wroost_fine_entry_index(ent: &wtd->fine_entries[i]) == index)
154 wroost_clear_fine_entry(wtd, slot: i);
155 }
156}
157
158static inline struct wroost_fine_entry *
159wroost_alloc_fine_entry(struct wroost_thread_data *wtd) {
160 /* Notable edge case here:
161 *
162 * the index can be 0, so we track slot liveness explicitly via fine_valid
163 * instead of relying on index == 0 meaning 'free'.
164 */
165 uint8_t free_mask = (~wtd->fine_valid) & WROOST_FINE_VALID_MASK;
166 if (free_mask == 0)
167 return NULL;
168
169 int i = ci_ctz(free_mask);
170 wtd->fine_valid |= BIT(i);
171 return &wtd->fine_entries[i];
172}
173
174static size_t next_ctr(const wroost_counter_t *ctrs, size_t total,
175 size_t start) {
176 if (start >= total)
177 return total;
178
179 size_t ctr_count = (total + WROOST_COUNTER_MAX) >> WROOST_BITS_PER_COUNTER;
180 size_t c = start >> WROOST_BITS_PER_COUNTER;
181 uint8_t mask = UINT8_MAX
182 << ((start & WROOST_COUNTER_MAX) * WROOST_BITS_PER_COUNTER);
183
184 do {
185 uint8_t ctr = ctrs[c] & mask;
186 if (ctr != 0) {
187 size_t idx = (c << WROOST_BITS_PER_COUNTER) | (ci_ctz(ctr) >> 1);
188 return MIN(idx, total);
189 }
190
191 mask = UINT8_MAX;
192 c++;
193 } while (c < ctr_count);
194
195 return total;
196}
197
198#define wroost_for_each_set_ctr(ctr_val, i, ctrs, n_bytes) \
199 for (size_t _tot_##i = \
200 (size_t) (n_bytes) * \
201 (BIT_SIZEOF(wroost_counter_t) / WROOST_BITS_PER_COUNTER), \
202 _active_##i = 1; \
203 _active_##i && _tot_##i > 0; _active_##i = 0) \
204 for ((i) = next_ctr((ctrs), _tot_##i, 0); \
205 (i) < _tot_##i && \
206 (((ctr_val) = \
207 (wroost_counter_t) (((ctrs)[(i) >> \
208 WROOST_BITS_PER_COUNTER] >> \
209 (((i) & WROOST_COUNTER_MASK) * \
210 WROOST_BITS_PER_COUNTER)) & \
211 WROOST_COUNTER_MASK)), \
212 1); \
213 (i) = next_ctr((ctrs), _tot_##i, (i) + 1))
214
215/*
216 * Invariants to check:
217 *
218 * (1) All counters are either all in the exact_entries or not
219 * (2) Saturated counters or zero counters have 0 fine_entries
220 * (3) There are no duplicate fine entries
221 */
222#define wroost_check_enforce(wtd) enforce(wroost_state_check(wtd))
223static bool wroost_state_check(struct wroost_thread_data *wtd) {
224 cc_ignore(wtd);
225
226#ifdef DEBUG_WROOST
227 for (int i = 0; i < WROOST_FINE_ENTRY_COUNT; i++) {
228 if (wtd->fine_valid & BIT(i)) {
229 struct wroost_fine_entry *ent = &wtd->fine_entries[i];
230 for (int j = 0; j < WROOST_FINE_ENTRY_COUNT; j++) {
231 if (i != j && (wtd->fine_valid & BIT(j))) {
232 if (ent->lock_id == wtd->fine_entries[j].lock_id)
233 return false;
234 }
235 }
236 }
237 }
238
239 for (int i = 0; i < WROOST_THREAD_COUNTERS; i++) {
240 wroost_counter_t ctr = wroost_read_counter(wtd, i);
241 int found = 0;
242 for (int j = 0; j < WROOST_FINE_ENTRY_COUNT; j++) {
243 if ((wtd->fine_valid & BIT(j)) &&
244 wroost_fine_entry_index(&wtd->fine_entries[j]) == i)
245 found++;
246 }
247
248 if (ctr == 0 || ctr == WROOST_COUNTER_MAX) {
249 if (found != 0)
250 return false;
251 } else {
252 if (found && found != ctr)
253 return false;
254 }
255 }
256
257#endif
258
259 return true;
260}
261
262static void bucket_idx_and_offset(cpu_id_t cpu, size_t *out_idx,
263 size_t *out_offset) {
264 size_t idx = cpu * THREAD_PRIO_CLASS_BIT_COUNT;
265 if (out_idx)
266 *out_idx = idx / BITMAP_BITS_PER_WORD;
267
268 if (out_offset)
269 *out_offset = idx % BITMAP_BITS_PER_WORD;
270}
271
272static enum thread_prio_class read_bucket_prio(struct wroost_bucket *bkt,
273 cpu_id_t cpu) {
274 size_t idx, offset;
275 bucket_idx_and_offset(cpu, out_idx: &idx, out_offset: &offset);
276 bitmap_word_t word = atomic_load(&bkt->rq_min_prio[idx]);
277 return (word >> offset) & THREAD_PRIO_CLASS_MASK;
278}
279
280static void percpu_inc_id(struct wroost_percpu_data *pcpu, wroost_id_t lock_id,
281 enum thread_prio_class prio) {
282 pcpu->rq_bucket_counts[lock_id]++;
283
284 struct wroost_bucket *bkt = &wroost_global.hash_table.buckets[lock_id];
285
286 enum thread_prio_class old = read_bucket_prio(bkt, cpu: pcpu->id);
287 if (old > prio) {
288 size_t idx, offset;
289 bucket_idx_and_offset(cpu: pcpu->id, out_idx: &idx, out_offset: &offset);
290 enum thread_prio_class new = (old ^ prio) << offset;
291 atomic_fetch_xor(&bkt->rq_min_prio[idx], new);
292 }
293}
294
295/*
296 * We do a trick here. If the 2-bit priority class counter in the bucket is
297 * 0b11, this semantically means "urgent is the minimum", but functionally
298 * means "no need to reschedule this CPU for a writer->reader boost".
299 *
300 * This functionality is identical to what we want when a CPU has no threads
301 * of a given lock ID, so we stash an URGENT when clearing.
302 */
303static void percpu_dec_id(struct wroost_percpu_data *pcpu,
304 wroost_id_t lock_id) {
305 enforce(pcpu->rq_bucket_counts[lock_id] > 0, UNDERFLOW);
306 if (--pcpu->rq_bucket_counts[lock_id] == 0) {
307 struct wroost_bucket *bkt = &wroost_global.hash_table.buckets[lock_id];
308 size_t idx, offset;
309 bucket_idx_and_offset(cpu: pcpu->id, out_idx: &idx, out_offset: &offset);
310
311 enum thread_prio_class new = THREAD_PRIO_CLASS_URGENT << offset;
312 atomic_fetch_or(&bkt->rq_min_prio[idx], new);
313 }
314}
315
316static enum thread_prio_class ceil_for(wroost_id_t lock_id,
317 enum thread_prio_class max_boost,
318 enum thread_prio_class min) {
319 enforce_precond(max_boost < THREAD_PRIO_CLASS_COUNT);
320
321 /* This is for readers. If the max boost is less than the minimum (base)
322 * thread priority, it should've panicked on lock entry. */
323 enforce_precond(min <= max_boost);
324
325 uint64_t bucket_word =
326 atomic_load(&wroost_global.hash_table.buckets[lock_id].raw_tally);
327
328 if (cc_likely(bucket_word == 0))
329 return min;
330
331 union {
332 uint16_t tallies[THREAD_PRIO_CLASS_COUNT];
333 uint64_t raw;
334 } exp = {.raw = bucket_word};
335
336 enum thread_prio_class ceil = min;
337 for (int p = max_boost; p > min; p--) {
338 if (exp.tallies[p] > 0) {
339 ceil = MAX((enum thread_prio_class) p, ceil);
340 break;
341 }
342 }
343
344 return ceil;
345}
346
347static struct wroost_kicks boost_thread_to(struct thread *t,
348 enum thread_prio_class prio) {
349 struct wroost_thread_data *wtd = &t->wroost_data;
350 enforce(prio <= wtd->max_boost);
351
352 spin_guard_high(&t->pi_lock);
353
354 if (!wtd->contributed_floor) {
355 wtd->floor = prio;
356 wtd->contributed_floor = true;
357 thread_class_floor_inc_locked(t, class: prio);
358 } else if (prio > wtd->floor) {
359 thread_class_floor_inc_locked(t, class: prio);
360 thread_class_floor_dec_locked(t, class: wtd->floor);
361 wtd->floor = prio;
362 }
363
364 return thread_recompute_prio_class_locked(t);
365}
366
367bool wroost_merge_kicks(struct wroost_percpu_data *pcd,
368 struct wroost_kicks *kicks) {
369 bool bother_self = false;
370 if (kicks->need_kicks) {
371 cpu_mask_or(dst: &pcd->in_dpc_deferred_cpus, b: &kicks->cpus);
372 bitmap_set(map: pcd->in_dpc_deferred_ids, bit: kicks->lock_id);
373
374 /* We don't re-enqueue the DPC on ourselves, that's unnecessary
375 * since the DPC itself can simply loop again */
376 cpu_mask_clear(m: &pcd->in_dpc_deferred_cpus, cpu: pcd->id);
377
378 if (cpu_mask_test(m: &kicks->cpus, cpu: pcd->id)) {
379 bother_self = true;
380
381 struct cpu_mask self_mask = CPU_MASK_INIT;
382
383 cpu_mask_set(m: &self_mask, cpu: pcd->id);
384
385 /* Just pend the update on the current CPU */
386 wroost_kick_cpus(mask: &self_mask, lock_id: kicks->lock_id,
387 WROOST_KICK_UPDATE_PENDING);
388 }
389 }
390
391 return bother_self;
392}
393
394static struct wroost_kicks boost_thread_in_dpc(struct scheduler *sched,
395 struct thread *t,
396 enum thread_prio_class prio) {
397 SPINLOCK_ASSERT_HELD(&sched->lock);
398 struct wroost_percpu_data *pcd = sched->wroost_data;
399
400 struct wroost_thread_data *wtd = &t->wroost_data;
401 enforce(prio <= wtd->max_boost);
402
403 struct wroost_kicks kicks = {0};
404
405 enum irql irql = spin_lock_high(&t->pi_lock);
406 enum thread_prio_class old, new;
407
408#ifdef DEBUG_WROOST
409 /* Should effectively be a no-op */
410 thread_recompute_prio_class_raw_locked(t, &old, &new);
411 enforce(old == new, "likely stale priority floor");
412#endif
413
414 if (!wtd->contributed_floor) {
415 wtd->floor = prio;
416 wtd->contributed_floor = true;
417 thread_class_floor_inc_locked(t, class: prio);
418 } else if (prio > wtd->floor) {
419 thread_class_floor_inc_locked(t, class: prio);
420 thread_class_floor_dec_locked(t, class: wtd->floor);
421 wtd->floor = prio;
422 }
423
424 thread_recompute_prio_class_dry_locked(t, old_out: &old, new_out: &new);
425
426 kicks = wroost_post_prio_change_locked(t, old, new);
427 wroost_merge_kicks(pcd, kicks: &kicks);
428
429 /* If this happens, this MUST be because of us.
430 *
431 * NOTE: scheduler_remove_thread_locked does not change the
432 * perceived_prio_class, so a removal and re-insertion is fine */
433 if (old != new) {
434 if (thread_get_state(t) == THREAD_STATE_READY)
435 scheduler_remove_thread_locked(sched, t);
436
437 t->perceived_prio_class = new;
438
439 if (thread_get_state(t) == THREAD_STATE_READY)
440 scheduler_add_thread_locked(sched, thread: t);
441 }
442
443 spin_unlock(&t->pi_lock, irql);
444
445 return kicks;
446}
447
448static void unboost_thread(struct thread *t) {
449 struct wroost_thread_data *wtd = &t->wroost_data;
450 spin_guard_high(&t->pi_lock);
451
452 if (wtd->contributed_floor)
453 thread_class_floor_dec_locked(t, class: wtd->floor);
454
455 wtd->floor = 0;
456 wtd->contributed_floor = false;
457
458 /* Unboost is fine to ignore the kicks from a boost */
459 cc_discard(thread_recompute_prio_class_locked(t));
460}
461
462static enum thread_prio_class ceil_for_thread(wroost_id_t id,
463 struct thread *t) {
464 return ceil_for(lock_id: id, max_boost: t->wroost_data.max_boost, min: t->base_prio_class);
465}
466
467/* There's a balance to strike with the scheduler runqueue lock granularity.
468 *
469 * If we lock around the WHOLE DPC, then writers can stall waiting
470 * for us to complete it if we are in the middle of it.
471 *
472 * This is because the IPI would wait for us to exit our IRQ disabled
473 * critical section, which would be bounded by the time we hold
474 * the lock for. In contrast, holding it for too little is also
475 * not great since the lock paths get noisy.
476 *
477 * We break it to the per-bitmap-pass granularity.
478 *
479 * Readers that are also writers on other locks are a special case.
480 *
481 * There need not be another list that checks them, but rather,
482 * they will simply end up on either thread_map or multi_lock_readers.
483 *
484 * For such threads, the DPC will need to use a CPU mask that
485 */
486static bool process_pending_word(struct scheduler *self, size_t w_idx,
487 bitmap_word_t pending,
488 struct wroost_process_result *result) {
489 struct thread *iter;
490 struct wroost_percpu_data *pcd = self->wroost_data;
491
492 while (pending) {
493 uint8_t bit = cw_ctz(pending);
494 pending &= pending - 1;
495
496 wroost_id_t id = (w_idx * BIT_SIZEOF(bitmap_word_t)) | bit;
497 wroost_id_t coarse = id / WROOST_COARSE_FACTOR;
498 struct wroost_kicks kicks = {0};
499
500 enforce(id < bucket_count());
501 enforce(coarse < WROOST_THREAD_COUNTERS);
502
503 hlist_for_each_entry(iter, &pcd->thread_map[coarse],
504 wroost_data.map_node) {
505#ifdef DEBUG_WROOST
506 enforce(!atomic_load_acq(&iter->blocked_ts));
507#endif
508 enum thread_prio_class new = ceil_for_thread(id, t: iter);
509 kicks = boost_thread_in_dpc(sched: self, t: iter, prio: new);
510 if (cpu_mask_test(m: &kicks.cpus, cpu: self->core_id))
511 return (result->restart = true);
512 }
513
514 hlist_for_each_entry(iter, &pcd->multi_lock_readers,
515 wroost_data.map_node) {
516#ifdef DEBUG_WROOST
517 enforce(!atomic_load_acq(&iter->blocked_ts));
518#endif
519 struct wroost_thread_data *wtd = &iter->wroost_data;
520
521 for (int i = 0; i < WROOST_FINE_ENTRY_COUNT; i++) {
522 struct wroost_fine_entry *ent = &wtd->fine_entries[i];
523
524 /* If we find it in a fine entry, we know this is the only
525 * occurrence because the fine entries
526 * cannot contain duplicates */
527 if ((wtd->fine_valid & BIT(i)) && ent->lock_id == id) {
528 enum thread_prio_class new = ceil_for_thread(id, t: iter);
529 kicks = boost_thread_in_dpc(sched: self, t: iter, prio: new);
530 if (cpu_mask_test(m: &kicks.cpus, cpu: self->core_id))
531 return (result->restart = true);
532
533 goto next;
534 }
535 }
536
537 wroost_counter_t cc_unused val;
538 wroost_id_t i;
539 wroost_for_each_set_ctr(val, i, wtd->counters,
540 WROOST_THREAD_COUNTER_BYTES) {
541 if (i != coarse)
542 continue;
543
544 wroost_id_t base = i * WROOST_COARSE_FACTOR;
545 enum thread_prio_class to = ceil_for_thread(id: base, t: iter);
546
547 /* We start at one because boost_to already checked 0 */
548 for (wroost_id_t j = 1; j < WROOST_COARSE_FACTOR; j++) {
549 wroost_id_t lock_id = base + j;
550 to = MAX(to, ceil_for_thread(lock_id, iter));
551 }
552
553 kicks = boost_thread_in_dpc(sched: self, t: iter, prio: to);
554 if (cpu_mask_test(m: &kicks.cpus, cpu: self->core_id))
555 return (result->restart = true);
556 }
557
558 next:
559 continue;
560 }
561 }
562
563 return false;
564}
565
566static bool process_pending_word_ts(struct scheduler *self, size_t w_idx,
567 bitmap_word_t pending,
568 struct wroost_process_result *result) {
569 struct thread *iter;
570 struct wroost_percpu_data *pcd = self->wroost_data;
571
572 while (pending) {
573 uint8_t bit = cw_ctz(pending);
574 pending &= pending - 1;
575
576 wroost_id_t id = (w_idx * BIT_SIZEOF(bitmap_word_t)) | bit;
577 wroost_id_t coarse = id / WROOST_COARSE_FACTOR;
578
579 struct wroost_kicks kicks = {0};
580
581 hlist_for_each_entry(iter, &pcd->blocked_ts_readers,
582 wroost_data.map_node) {
583 struct wroost_thread_data *wtd = &iter->wroost_data;
584
585 for (int i = 0; i < WROOST_FINE_ENTRY_COUNT; i++) {
586 struct wroost_fine_entry *ent = &wtd->fine_entries[i];
587
588 if ((wtd->fine_valid & BIT(i)) && ent->lock_id == id) {
589 enum thread_prio_class new = ceil_for_thread(id, t: iter);
590 kicks = boost_thread_in_dpc(sched: self, t: iter, prio: new);
591 if (cpu_mask_test(m: &kicks.cpus, cpu: self->core_id))
592 return (result->restart = true);
593
594 if (turnstile_propagate_wroost(pcd, t: iter))
595 return (result->restart = true);
596
597 goto next;
598 }
599 }
600
601 wroost_counter_t cc_unused val;
602 wroost_id_t i;
603 wroost_for_each_set_ctr(val, i, wtd->counters,
604 WROOST_THREAD_COUNTER_BYTES) {
605 if (i != coarse)
606 continue;
607
608 wroost_id_t base = i * WROOST_COARSE_FACTOR;
609 enum thread_prio_class to = ceil_for_thread(id: base, t: iter);
610
611 for (wroost_id_t j = 1; j < WROOST_COARSE_FACTOR; j++) {
612 wroost_id_t lock_id = base + j;
613 to = MAX(to, ceil_for_thread(lock_id, iter));
614 }
615
616 kicks = boost_thread_in_dpc(sched: self, t: iter, prio: to);
617 if (cpu_mask_test(m: &kicks.cpus, cpu: self->core_id))
618 return (result->restart = true);
619
620 if (turnstile_propagate_wroost(pcd, t: iter))
621 return (result->restart = true);
622 }
623
624 next:
625 continue;
626 }
627 }
628
629 return false;
630}
631
632static void process_pending_bitmap(struct scheduler *self,
633 struct wroost_process_result *result) {
634 enforce(irql_get() == IRQL_DISPATCH_LEVEL, INVALID_CONTEXT);
635 enforce(!result->restart);
636
637 struct wroost_percpu_data *pcd = self->wroost_data;
638 bitmap_zero(map: pcd->in_dpc_deferred_ids, nbits: bucket_count());
639 cpu_mask_clear_all(m: &pcd->in_dpc_deferred_cpus);
640
641 enum irql wirql = spin_lock_high(&self->wroost_lock);
642 enum irql sirql = spin_lock_high(&self->lock);
643
644 for (size_t w = 0; w < BITMAP_WORDS(bucket_count()); w++) {
645 bitmap_word_t pending = atomic_xchg_acq_rel(&pcd->pending_bitmap[w], 0);
646
647 pending |= result->seen_data[w];
648 result->seen_data[w] = pending;
649
650 if (process_pending_word(self, w_idx: w, pending, result))
651 goto out_inner;
652 }
653
654 spin_unlock(&self->lock, sirql);
655
656 /* We have to re-check and iterate again under ONLY the wroost_lock.
657 *
658 * This part is for boosting blocked_ts_readers, which needs to
659 * propagate the inheritance up the chain, and thus, requires that
660 * no sched->lock be held (only wroost_lock to protect this state) */
661 for (size_t w = 0; w < BITMAP_WORDS(bucket_count()); w++) {
662 bitmap_word_t new_word =
663 atomic_xchg_acq_rel(&pcd->pending_bitmap[w], 0);
664 bitmap_word_t pending = new_word | result->seen_data[w];
665
666 /* Add the new words to the set here. This is because on
667 * a retry, we start from the beginning again, iterating
668 * over non-blocked threads, so we need to preserve those */
669 result->seen_data[w] |= new_word;
670
671 if (process_pending_word_ts(self, w_idx: w, pending, result))
672 goto out_outer;
673 }
674
675 if (pcd->ts_requeue_pending) {
676 pcd->ts_requeue_pending = false;
677
678 struct thread *iter;
679 hlist_for_each_entry(iter, &pcd->blocked_ts_readers,
680 wroost_data.map_node) {
681 if (turnstile_propagate_wroost(pcd, t: iter)) {
682 pcd->ts_requeue_pending = true;
683 result->restart = true;
684 goto out_outer;
685 }
686 }
687 }
688
689 spin_unlock(&self->wroost_lock, wirql);
690 return;
691
692out_inner:
693 spin_unlock(&self->lock, sirql);
694
695out_outer:
696 spin_unlock(&self->wroost_lock, wirql);
697}
698
699static void kick_from_dpc(struct wroost_percpu_data *pcd) {
700 /* boost_thread_in_dpc enforces that this doesn't happen. We don't
701 * send the DPC on ourselves since we goto restart */
702 enforce(!cpu_mask_test(&pcd->in_dpc_deferred_cpus, pcd->id));
703
704 size_t bit;
705 bitmap_for_each_bit_set(bit, pcd->in_dpc_deferred_ids,
706 wroost_global.hash_table.bucket_count)
707 wroost_kick_cpus(mask: &pcd->in_dpc_deferred_cpus, lock_id: bit,
708 WROOST_KICK_UPDATE_PENDING | WROOST_KICK_SEND_DPCS);
709}
710
711/* This DPC runs on the reader-side CPU and is
712 * responsible for doing all of the boosting of READY threads.
713 *
714 * We don't boost a RUNNING thread here though,
715 * that happens on switch out */
716static void wroost_dpc(struct dpc_context *dc, void *a, void *b) {
717 cc_ignore(dc, a, b);
718 struct scheduler *self = smp_core_scheduler();
719 struct wroost_percpu_data *pcd = self->wroost_data;
720
721 while (true) {
722 atomic_fetch_and(&pcd->state, ~WROOST_DPC_PENDING);
723
724 struct wroost_process_result *result = &pcd->process_result;
725 bitmap_zero(map: result->seen_data, nbits: bucket_count());
726
727 /* Every time `kicks` happens to have THIS CPU in its mask,
728 * we have to re-scan. This won't infinitely loop (hopefully) because
729 * the mask only becomes set upon a priority change,
730 * and eventually all priority changes will have completed.
731 */
732 do {
733 result->restart = false;
734 process_pending_bitmap(self, result);
735 kick_from_dpc(pcd);
736 } while (result->restart);
737
738 /* If a writer came about, this CAS fails and we go again */
739 enum wroost_state want = WROOST_DPC_ACTIVE;
740
741 if (cc_likely(atomic_cas_strong(&self->wroost_data->state, &want,
742 WROOST_DPC_IDLE)))
743 break;
744 }
745}
746
747void wroost_pre_acquire(struct rwlock *lock, enum rwlock_acquire_type type) {
748 wroost_id_t hash = wroost_hash(lock);
749 struct thread *curr = thread_get_current();
750 struct wroost_thread_data *wtd = &curr->wroost_data;
751
752 enforce(wtd->writer_state == WROOST_WRITER_NONE);
753
754 /* Nothing for readers to do at the moment */
755 if (type == RWLOCK_WRITE) {
756 wtd->want_lock_id = hash;
757 wtd->writer_state = WROOST_WRITER_WANT;
758 }
759}
760
761static void post_read_acquire(struct rwlock *lock,
762 enum thread_prio_class lock_max_ceil) {
763 struct thread *curr = thread_get_current();
764 wroost_id_t id = wroost_hash(lock);
765 uint16_t c_idx = id / WROOST_COARSE_FACTOR;
766 uint16_t offset = id % WROOST_COARSE_FACTOR;
767 enforce((offset & wroost_global.fine_offset_mask) == offset);
768 struct wroost_thread_data *wtd = &curr->wroost_data;
769
770 /* We're touching per-thread that the scheduler cares about,
771 * so let's prevent preemption so it always sees a valid state */
772 enum irql irql = irql_raise(new_level: IRQL_DISPATCH_LEVEL);
773 wroost_check_enforce(wtd);
774
775 if (wtd->read_nesting_depth == 0 || lock_max_ceil > wtd->max_boost)
776 wtd->max_boost = lock_max_ceil;
777
778 wtd->read_nesting_depth++;
779
780 wroost_counter_t prev_val;
781 wroost_counter_t new_val = wroost_inc_counter(wtd, ctr_idx: c_idx, ctr_val: &prev_val);
782 enforce(((c_idx << wroost_global.fine_index_bits) | offset) == id);
783
784 if (prev_val == 0) {
785 /* First lock in this index, try to get an entry */
786 struct wroost_fine_entry *fe = wroost_alloc_fine_entry(wtd);
787 if (fe)
788 fe->lock_id = id;
789
790 } else if (new_val == WROOST_COUNTER_MAX) {
791 /* Evict entries */
792 wroost_evict_fine_entries(wtd, index: c_idx);
793 } else {
794 /* second lock, allocate a fine entry only if the first one exists,
795 * evicting on allocation failure */
796 struct wroost_fine_entry *old;
797 if ((old = wroost_get_fine_entry(wtd, index: c_idx)) != NULL) {
798 /* We cannot end up with a duplicate ID in the fine
799 * entries, this would break the unlock path */
800 if (old->lock_id == id) {
801 wroost_evict_fine_entries(wtd, index: c_idx);
802 } else {
803 struct wroost_fine_entry *fe = wroost_alloc_fine_entry(wtd);
804 if (fe) {
805 fe->lock_id = id;
806 } else {
807 wroost_evict_fine_entries(wtd, index: c_idx);
808 }
809 }
810 }
811 }
812
813 wroost_check_enforce(wtd);
814 irql_lower(old_level: irql);
815}
816
817void wroost_post_acquire(struct rwlock *lock, enum rwlock_acquire_type type) {
818 struct thread *curr = thread_get_current();
819 struct wroost_thread_data *wtd = &curr->wroost_data;
820
821 if (type == RWLOCK_READ) {
822 enum thread_prio_class ceil =
823 RWLOCK_GET_MAX_PRIO(RWLOCK_READ_LOCK_WORD(lock));
824 post_read_acquire(lock, lock_max_ceil: ceil);
825 } else {
826 /* We cannot have been mid-wait and somehow got the lock.
827 * We either wanted the lock, didn't block, or blocked,
828 * in which case it would transition to BUMP */
829 enforce(wtd->writer_state != WROOST_WRITER_WAIT);
830 enforce(wtd->writer_state != WROOST_WRITER_NONE);
831
832 /* We incremented boost counters. Acquire the pi_lock so that
833 * updates to our perceived priority synchronize and we decrement
834 * properly and update the state */
835 if (wtd->writer_state == WROOST_WRITER_BUMP) {
836 enum irql irql = spin_lock_high(&curr->pi_lock);
837
838 enum thread_prio_class bumped = curr->perceived_prio_class;
839
840 wroost_id_t lock_id = wtd->want_lock_id;
841 struct wroost_bucket *bkt =
842 &wroost_global.hash_table.buckets[lock_id];
843 size_t offset = bumped * BIT_SIZEOF(uint16_t);
844 uint64_t dec = BIT(offset);
845
846 atomic_fetch_sub(&bkt->raw_tally, dec);
847
848 /* Set it to NONE here, inside the pi_lock, because
849 * doing it outside would cause other threads to
850 * acquire pi_lock and see BUMP, causing underflow */
851 wtd->writer_state = WROOST_WRITER_NONE;
852 wtd->want_lock_id = 0;
853
854 spin_unlock(&curr->pi_lock, irql);
855 } else {
856 /* Does not need pi_lock because it was never BUMP to begin
857 * with, because we never entered WAIT state, and never will
858 * at this point, so no one acquiring our
859 * lock will see stale state */
860 wtd->writer_state = WROOST_WRITER_NONE;
861 wtd->want_lock_id = 0;
862 }
863 }
864}
865
866static void post_read_release(struct rwlock *lock) {
867 struct thread *curr = thread_get_current();
868 struct wroost_thread_data *wtd = &curr->wroost_data;
869
870 enum irql irql = irql_raise(new_level: IRQL_DISPATCH_LEVEL);
871 wroost_check_enforce(wtd);
872 enforce(wtd->read_nesting_depth > 0, UNDERFLOW);
873
874 wroost_id_t id = wroost_hash(lock);
875 if (cc_likely(--wtd->read_nesting_depth == 0)) {
876 for (int i = 0; i < WROOST_THREAD_COUNTER_BYTES; i++)
877 wtd->counters[i] = 0;
878
879#ifdef DEBUG_WROOST
880 /* fine_valid = 0 automatically permits allocations, we do not need
881 * to clear lock_id */
882 for (int i = 0; i < WROOST_FINE_ENTRY_COUNT; i++) {
883 if (wtd->fine_valid & BIT(i))
884 enforce(wtd->fine_entries[i].lock_id == id);
885 }
886#endif
887
888 wtd->fine_valid = 0;
889 wtd->max_boost = 0;
890 unboost_thread(t: curr);
891 } else {
892 uint16_t c_idx = id / WROOST_COARSE_FACTOR;
893
894 wroost_counter_t prev_val = wroost_read_counter(wtd, ctr_idx: c_idx);
895 wroost_dec_counter(wtd, ctr_idx: c_idx);
896
897 if (prev_val < WROOST_COUNTER_MAX) {
898 /* We are guaranteed to have no duplicates */
899 for (int i = 0; i < WROOST_FINE_ENTRY_COUNT; i++) {
900 struct wroost_fine_entry *wfe = &wtd->fine_entries[i];
901 if ((wtd->fine_valid & BIT(i)) && wfe->lock_id == id) {
902 wroost_clear_fine_entry(wtd, slot: i);
903 break;
904 }
905 }
906 }
907 }
908
909 wroost_check_enforce(wtd);
910 irql_lower(old_level: irql);
911}
912
913void wroost_post_release(struct rwlock *lock, enum rwlock_acquire_type type) {
914 if (type == RWLOCK_READ)
915 post_read_release(lock);
916
917 /* Writers have nothing to do. They only use wroost to send
918 * boosts to readers while they wait for readers, and once
919 * the post_acquire happens, they are all done */
920}
921
922static bool percpu_boost_kick(cpu_id_t target, wroost_id_t lock_id,
923 int options) {
924 struct wroost_percpu_data *pcd = global.schedulers[target]->wroost_data;
925
926 size_t word = lock_id / BIT_SIZEOF(bitmap_word_t);
927 size_t idx = lock_id % BIT_SIZEOF(bitmap_word_t);
928
929 uint64_t prev_bits = 0;
930
931 if (options & WROOST_KICK_UPDATE_PENDING)
932 prev_bits = atomic_fetch_or(&pcd->pending_bitmap[word], BIT(idx));
933
934 /* Early returning here is OK. We won't have a missed bit set, because
935 * if this bit is already set, someone else has sent out the DPC and
936 * it is waiting to get to this point */
937 if (prev_bits & BIT(idx))
938 return true;
939
940 if (options & WROOST_KICK_SEND_DPCS) {
941 enum wroost_state prev_state = atomic_fetch_or(
942 &pcd->state, WROOST_DPC_PENDING | WROOST_DPC_ACTIVE);
943
944 if (!(prev_state & WROOST_DPC_ACTIVE))
945 return true;
946
947 return dpc_enqueue_on_cpu(
948 cpu: target, d: &global.schedulers[target]->wroost_data->boost_dpc);
949 } else {
950 return true;
951 }
952}
953
954static size_t wroost_kick_cpus(struct cpu_mask *mask, wroost_id_t lock_id,
955 int options) {
956 cpu_id_t i;
957#ifdef DEBUG_WROOST
958 cpu_mask_for_each(i, *mask)
959 enforce(i < global.core_count);
960#endif
961
962 size_t kicked = 0;
963 cpu_mask_for_each(i, *mask) {
964 percpu_boost_kick(target: i, lock_id, options);
965 kicked++;
966 }
967
968 return kicked;
969}
970
971size_t wroost_kick(struct wroost_kicks *kicks) {
972 return wroost_kick_cpus(mask: &kicks->cpus, lock_id: kicks->lock_id,
973 WROOST_KICK_UPDATE_PENDING | WROOST_KICK_SEND_DPCS);
974}
975
976static void set_target_cpus(struct wroost_bucket *bkt, struct cpu_mask *on_mask,
977 enum thread_prio_class writer_prio) {
978 cpu_id_t checked = 0;
979 for (size_t bm_word_idx = 0; checked < global.core_count; bm_word_idx++) {
980 bitmap_word_t word = atomic_load(&bkt->rq_min_prio[bm_word_idx]);
981
982 for (int shift = 0;
983 shift < BITMAP_BITS_PER_WORD && checked < global.core_count;
984 shift += THREAD_PRIO_CLASS_BIT_COUNT) {
985 enum thread_prio_class prio =
986 (word >> shift) & THREAD_PRIO_CLASS_MASK;
987
988 if (prio < writer_prio)
989 cpu_mask_set(m: on_mask, cpu: checked);
990
991 checked++;
992 }
993 }
994}
995
996/* Register/unregister a reader with a given CPU. Returns an actual
997 * priority to boost to when add == true, base_prio_class otherwise */
998static enum thread_prio_class update_reader(struct wroost_percpu_data *pcd,
999 struct thread *t, bool add) {
1000 struct wroost_thread_data *wtd = &t->wroost_data;
1001 enum thread_prio_class boost_to = t->base_prio_class;
1002 enum thread_prio_class p;
1003 /* wtd->read_nesting_depth <= 4 not necessarily mean that all locks
1004 * held reside in the fine entries, such as when
1005 * a counter overflows at read_nesting_depth == 3 */
1006 size_t found_fine_count = 0;
1007 wroost_id_t found_coarse = 0;
1008 bool blocked_on_ts = atomic_load_acq(&t->blocked_ts);
1009
1010 if (blocked_on_ts && add)
1011 thread_pin(t);
1012
1013 /* Because coarse entries are either fully inside the fine entries or not,
1014 * we can use this without needing to check the actual coarse entries */
1015 BITMAP_DECLARE(skip_map, WROOST_THREAD_COUNTERS) = {0};
1016
1017 for (int i = 0; i < WROOST_FINE_ENTRY_COUNT; i++) {
1018 if (wtd->fine_valid & BIT(i)) {
1019 wroost_id_t id = wtd->fine_entries[i].lock_id;
1020 if (add && (p = ceil_for(lock_id: id, max_boost: wtd->max_boost, min: boost_to)) > boost_to)
1021 boost_to = p;
1022
1023 if (add) {
1024 percpu_inc_id(pcpu: pcd, lock_id: id, prio: t->base_prio_class);
1025 } else {
1026 percpu_dec_id(pcpu: pcd, lock_id: id);
1027 }
1028
1029 found_coarse = id / WROOST_COARSE_FACTOR;
1030
1031 bitmap_set(map: skip_map, bit: found_coarse);
1032 if (++found_fine_count == wtd->read_nesting_depth)
1033 break;
1034 }
1035 }
1036
1037 enforce(found_fine_count <= wtd->read_nesting_depth, CORRUPTION);
1038 if (add) {
1039 if (blocked_on_ts) {
1040 hlist_add_head(n: &wtd->map_node, h: &pcd->blocked_ts_readers);
1041 wtd->in_blocked_ts_list = true;
1042 } else {
1043 if (wtd->read_nesting_depth == 1) {
1044 hlist_add_head(n: &wtd->map_node, h: &pcd->thread_map[found_coarse]);
1045 } else {
1046 hlist_add_head(n: &wtd->map_node, h: &pcd->multi_lock_readers);
1047 }
1048 }
1049 } else {
1050 hlist_del(n: &wtd->map_node);
1051 }
1052
1053 /* No need to check coarse entries */
1054 if (found_fine_count == wtd->read_nesting_depth)
1055 goto out;
1056
1057 cc_maybe_unused wroost_counter_t val;
1058 wroost_id_t i;
1059 wroost_for_each_set_ctr(val, i, wtd->counters,
1060 WROOST_THREAD_COUNTER_BYTES) {
1061 if (bitmap_test(map: skip_map, bit: i))
1062 continue;
1063
1064 for (size_t j = 0; j < WROOST_COARSE_FACTOR; j++) {
1065 wroost_id_t k = (wroost_id_t) (i * WROOST_COARSE_FACTOR + j);
1066
1067 if (add) {
1068 percpu_inc_id(pcpu: pcd, lock_id: k, prio: t->base_prio_class);
1069 } else {
1070 percpu_dec_id(pcpu: pcd, lock_id: k);
1071 }
1072
1073 if (add && (p = ceil_for(lock_id: k, max_boost: wtd->max_boost, min: boost_to)) > boost_to)
1074 boost_to = p;
1075 }
1076 }
1077
1078out:
1079 if (!add && wtd->in_blocked_ts_list) {
1080 thread_unpin(t);
1081 wtd->in_blocked_ts_list = false;
1082 }
1083
1084 return boost_to;
1085}
1086
1087static void switch_out_writer(struct thread *t) {
1088 struct wroost_percpu_data *pcd = smp_core_scheduler()->wroost_data;
1089
1090 spin_guard_high(&t->pi_lock);
1091
1092 enum thread_prio_class writer_class = t->perceived_prio_class;
1093 wroost_id_t lock_id = t->wroost_data.want_lock_id;
1094 struct wroost_bucket *bkt = &wroost_global.hash_table.buckets[lock_id];
1095 size_t offset = writer_class * BIT_SIZEOF(uint16_t);
1096 uint64_t inc = BIT(offset);
1097 uint64_t prev_raw = atomic_fetch_add(&bkt->raw_tally, inc);
1098
1099 t->wroost_data.writer_state = WROOST_WRITER_BUMP;
1100
1101 /* 0 -> 1 transition, we handle IPI'ing and whatnot */
1102 uint16_t prev_class_cnt = (prev_raw >> offset) & UINT16_MAX;
1103
1104 if (prev_class_cnt == 0) {
1105 set_target_cpus(bkt, on_mask: &pcd->dpc_enqueue_deferred, writer_prio: writer_class);
1106 pcd->writer_lock_id = lock_id;
1107 }
1108}
1109
1110static void switch_out_reader(struct thread *t) {
1111 struct wroost_thread_data *wtd = &t->wroost_data;
1112
1113 if (wtd->read_nesting_depth == 0)
1114 return;
1115
1116 wroost_check_enforce(wtd);
1117 struct wroost_percpu_data *pcd = smp_core_scheduler()->wroost_data;
1118
1119 enum thread_prio_class boost_to = update_reader(pcd, t, /* add = */ true);
1120
1121 struct wroost_kicks kicks = boost_thread_to(t, prio: boost_to);
1122 if (kicks.need_kicks) {
1123#ifdef DEBUG_WROOST
1124 enforce(cpu_mask_first_set(&pcd->dpc_enqueue_deferred) ==
1125 CPU_MASK_BITS ||
1126 pcd->writer_lock_id == kicks.lock_id);
1127#endif
1128 cpu_mask_or(dst: &pcd->dpc_enqueue_deferred, b: &kicks.cpus);
1129 pcd->writer_lock_id = kicks.lock_id;
1130 }
1131
1132 if (wtd->in_blocked_ts_list && t->wq_prio != turnstile_thread_priority(t))
1133 pcd->ts_requeue_pending = true;
1134}
1135
1136/* Runs in scheduler with runqueue lock held */
1137void wroost_switch_out(struct thread *t) {
1138 if (!t)
1139 return;
1140
1141 /* We only switch out the writer on WRITER_WAIT,
1142 * because it could've just been preempted. We do want
1143 * to check the reader data before the writer, since
1144 * writers go off of perceived priority, which reading influences */
1145 switch_out_reader(t);
1146 if (t->wroost_data.writer_state == WROOST_WRITER_WAIT)
1147 switch_out_writer(t);
1148}
1149
1150/* Runs in scheduler with runqueue lock held, not necessarily on `t` */
1151void wroost_switch_in(struct thread *t) {
1152 if (t && t->wroost_data.read_nesting_depth > 0) {
1153 struct wroost_percpu_data *pcd = smp_core_scheduler()->wroost_data;
1154 update_reader(pcd, t, /* add = */ false);
1155 }
1156}
1157
1158/* Separate from switch_in. this runs deferred DPC
1159 * notifications/IPIs onto the other CPUs */
1160void wroost_scheduler_switch_in_hook(void) {
1161 struct wroost_percpu_data *pcd = smp_core_scheduler()->wroost_data;
1162 if (wroost_kick_cpus(mask: &pcd->dpc_enqueue_deferred, lock_id: pcd->writer_lock_id,
1163 WROOST_KICK_UPDATE_PENDING | WROOST_KICK_SEND_DPCS)) {
1164 cpu_mask_clear_all(m: &pcd->dpc_enqueue_deferred);
1165 } else {
1166#ifdef DEBUG_WROOST
1167 /* No bits can be set. writer_lock_id can be any value though, since
1168 * it just means that we didn't happen to
1169 * encounter any CPUs that need a kick */
1170 enforce(cpu_mask_first_set(&pcd->dpc_enqueue_deferred) ==
1171 CPU_MASK_BITS);
1172#endif
1173 }
1174
1175 pcd->writer_lock_id = 0;
1176
1177 if (pcd->ts_requeue_pending)
1178 percpu_boost_kick(target: pcd->id, lock_id: 0, WROOST_KICK_SEND_DPCS);
1179}
1180
1181void wroost_pre_wait(struct thread *curr) {
1182#ifdef DEBUG_WROOST
1183 enforce(curr == thread_get_current());
1184#endif
1185
1186 enforce(curr->wroost_data.writer_state == WROOST_WRITER_NONE ||
1187 curr->wroost_data.writer_state == WROOST_WRITER_WANT);
1188 if (curr->wroost_data.writer_state == WROOST_WRITER_WANT)
1189 curr->wroost_data.writer_state = WROOST_WRITER_WAIT;
1190}
1191
1192/* This exists for the specific purpose of updating the wait
1193 * state for threads that began a wait but never actually got
1194 * switched out. We go back to wanting a lock if that happened */
1195void wroost_post_wait(struct thread *curr) {
1196#ifdef DEBUG_WROOST
1197 enforce(curr == thread_get_current());
1198#endif
1199
1200 /* We either have to have (1) bumped the tallies, due to switch-out,
1201 * (2) begun a wait, but get bothered before the tally bump, or (3)
1202 * never been a writer at all. There is no case where this code
1203 * would be reached in the middle of trying to get the lock though. */
1204 enforce(curr->wroost_data.writer_state != WROOST_WRITER_WANT);
1205 if (curr->wroost_data.writer_state == WROOST_WRITER_WAIT)
1206 curr->wroost_data.writer_state = WROOST_WRITER_WANT;
1207}
1208
1209void wroost_post_migrate_hook(struct thread *t, cpu_id_t from, cpu_id_t to) {
1210 /* The migration hook is only relevant for readers.
1211 * Writers keep no per-CPU state */
1212 if (t->wroost_data.read_nesting_depth == 0)
1213 return;
1214
1215 if (atomic_load(&t->blocked_ts))
1216 panic("reader with blocked_ts cannot migrate");
1217
1218 update_reader(pcd: global.schedulers[from]->wroost_data, t,
1219 /* add = */ false);
1220 update_reader(pcd: global.schedulers[to]->wroost_data, t, /* add = */ true);
1221}
1222
1223struct wroost_kicks wroost_post_prio_change_locked(struct thread *t,
1224 enum thread_prio_class old,
1225 enum thread_prio_class new) {
1226 struct wroost_kicks kicks = {0};
1227 SPINLOCK_ASSERT_HELD(&t->pi_lock);
1228 wroost_id_t lock_id = 0;
1229 if (t->wroost_data.writer_state == WROOST_WRITER_BUMP && old != new) {
1230 lock_id = t->wroost_data.want_lock_id;
1231 struct wroost_bucket *bkt = &wroost_global.hash_table.buckets[lock_id];
1232 wroost_move_tally(bkt, from: old, to: new);
1233
1234 /* We need to go bother other CPUs. The problem is that the caller
1235 * can hold any lock (including the runqueue lock), which can
1236 * deadlock the target CPUs if they're trying to get the locks
1237 * the caller happens to be holding */
1238 if (old < new) {
1239 kicks.need_kicks = true;
1240 kicks.lock_id = lock_id;
1241 set_target_cpus(bkt, on_mask: &kicks.cpus, writer_prio: new);
1242 }
1243 }
1244
1245 return kicks;
1246}
1247
1248static size_t wroost_calc_default_buckets(size_t cpu_count) {
1249 size_t target = cpu_count * WROOST_BUCKETS_PER_CPU_MULT;
1250
1251 if (target <= WROOST_MIN_BUCKET_COUNT)
1252 return WROOST_MIN_BUCKET_COUNT;
1253
1254 if (target >= WROOST_MAX_BUCKET_COUNT)
1255 return WROOST_MAX_BUCKET_COUNT;
1256
1257 return CLAMP(next_pow2(target), WROOST_MIN_BUCKET_COUNT,
1258 WROOST_MAX_BUCKET_COUNT);
1259}
1260
1261void wroost_init(void) {
1262 size_t bucket_count = wroost_calc_default_buckets(cpu_count: global.core_count);
1263 enforce(IS_POW2(bucket_count));
1264 enforce(bucket_count <= UINT16_MAX - 1, CAPACITY_EXCEEDED);
1265
1266 wroost_global.hash_table.bucket_count = bucket_count;
1267
1268 enforce(IS_POW2(wroost_global.hash_table.bucket_count));
1269
1270 wroost_global.hash_table.buckets = nofail_vnews(
1271 wroost_global.hash_table.buckets, bucket_count, ALLOC_ZERO);
1272
1273 for (size_t i = 0; i < bucket_count; i++) {
1274 struct wroost_bucket *bkt = &wroost_global.hash_table.buckets[i];
1275
1276 /* Fill it with ones 'URGENT' */
1277 bitmap_fill(map: (bitmap_word_t *) bkt->rq_min_prio,
1278 THREAD_PRIO_CLASS_BIT_COUNT * CPU_MASK_BITS);
1279 }
1280
1281 wroost_global.fine_index_bits = BITS_NEEDED(
1282 (wroost_global.hash_table.bucket_count / WROOST_THREAD_COUNTERS) - 1);
1283
1284 wroost_global.fine_offset_mask =
1285 (1ULL << wroost_global.fine_index_bits) - 1;
1286}
1287
1288void wroost_scheduler_init(struct scheduler *sched) {
1289 sched->wroost_data = nofail_vnew(sched->wroost_data, ALLOC_ZERO);
1290
1291 struct wroost_percpu_data *pcd = sched->wroost_data;
1292 dpc_init(d: &pcd->boost_dpc, fn: wroost_dpc, NULL, NULL);
1293 pcd->id = sched->core_id;
1294
1295 pcd->pending_bitmap = nofail_vnews(
1296 pcd->pending_bitmap, BITMAP_WORDS(bucket_count()), ALLOC_ZERO);
1297
1298 pcd->process_result.seen_data =
1299 nofail_vnews(pcd->process_result.seen_data,
1300 BITMAP_WORDS(bucket_count()), ALLOC_ZERO);
1301
1302 pcd->in_dpc_deferred_ids = nofail_vnews(
1303 pcd->in_dpc_deferred_ids, BITMAP_WORDS(bucket_count()), ALLOC_ZERO);
1304
1305 pcd->rq_bucket_counts =
1306 nofail_vnews(pcd->rq_bucket_counts, bucket_count(), ALLOC_ZERO);
1307
1308 cpu_mask_clear_all(m: &pcd->dpc_enqueue_deferred);
1309}
1310