Writer to Reader Boosting

include/sch/wroost.h View source View on GitHub

wroost “writer reader boost” portmanteau

Implementing writer to reader boosting for rwlocks is quite tricky, especially for turnstile-backed ones where you don’t get extra data to store lists of threads.

Lock side stuff:

Thus, this is a sort of lazy priority ceiling. The idea is this: we store a hash table where each bucket has no hlist, but rather, keeps a set of 4 16-bit counters and a CPU mask.

We hash every lock to store a small ‘counting bloom filter’ within each thread. We also keep a max_boost which is the maximum of all rwlock’s maximum priorities to mitigate excess boosting that could be pathological.

Then, writers hash into the table and bump the counter that corresponds to their perceived priority.

Scheduler side stuff:

Every CPU stores 256 x 16 bit counters that indicate the number of threads with a given ID (coarse entries are fanned across their respective sub-buckets) read-locked.

When one of these counters passes the 0 <-> 1 transition boundary, it sets/clears a CPU mask in the corresponding global hash table bucket.

Migrations also alter the CPU masks if they cross a transition boundary, and do so by first setting the new bit and then clearing the old one.

Structs

wroost_kicks

struct wroost_kicks (3 fields)

§ bool need_kicks

§ struct cpu_mask cpus

§ wroost_id_t lock_id

wroost_process_result

struct wroost_process_result (2 fields)

§ bool restart

§ bitmap_word_t *seen_data

seen_data marks the lock IDs that the code has already processed, at the bitmap word granularity. This is so that if the pending process needs to restart, it remains aware of what had already been processed, so it can merge it with potentially new bits and re-check and boost (since restart happens due to a writer boosting a reader on calling CPU)

Protected by scheduler->lock

wroost_percpu_data

struct wroost_percpu_data (14 fields)

§ atomic(enum wroost_state) state

§ cpu_id_t id

§ uint8_t *rq_bucket_counts

This keeps track of the number of READY threads on this CPU’s runqueues of every given lock ID. Notably, it does NOT keep track of RUNNING threads OR threads that were going to block.

Upon switch in, if a thread has any rwlocks held as a reader, it “contributes”, and when leaving, it “withdraws” its counts added.

However, the threads only contribute 1 per lock maximum, even if its 2-bit counter is more than 1. The intent here is to simply track “any thread”, not “exact counter”, so we only need every thread to contribute 1 for the count if it has that lock ID held as a reader.

We need this because this is what allows us to make the 0 <-> 1 switch for the bitmap per-lock-ID

§ struct hlist_head thread_map[WROOST_THREAD_COUNTERS]

Not actually a hashmap, it’s just the number of counters, where precise entries get their coarse entry counter

§ struct hlist_head multi_lock_readers

Since thread_map is guaranteed to only have single lock readers

§ struct hlist_head blocked_ts_readers

Readers that happen to be blocked on a turnstile go here. This is because such readers need to propagate their priorities, which cannot happen under sched->lock, but can under wroost_lock (and that is the sole purpose that lock actually exists).

Readers enter blocked_ts_readers on switch-out, and exit it on switch-in, both of which cannot happen during the DPC that iterates through this.

Migrations are not a concern here because these threads do not exist in the runqueues, and there is thus no way to have obtained them for a migration. These threads must also be woken on the CPU that they went to sleep on for this reason.

§ bool ts_requeue_pending

Set on switch-out when blocked_ts_reader gets boosted

§ atomic(bitmap_word_t) * pending_bitmap

§ struct wroost_process_result process_result

§ bitmap_word_t *in_dpc_deferred_ids

These primarily serve the purpose of implementing multi-hop.

In the DPC, some readers are also writers, and upon a priority change, they will also need to go bother relevant readers. However, this all happens deep down in the scheduler lock, so DPCs can’t be arbitrarily sent (deadlock). Thus, we merge all the CPU masks into a single one, and set bits in in_dpc_deferred_ids. The idea is that merging all of this together means that we may unnecessarily IPI some CPUs, but we will never have a false negative, and in the common case, this won’t be that bad since only a lock or two of this kind will be held

Bits represent lock IDs

§ struct cpu_mask in_dpc_deferred_cpus

§ struct dpc boost_dpc

§ struct cpu_mask dpc_enqueue_deferred

§ wroost_id_t writer_lock_id

So we know what to set for deferred DPCS

wroost_fine_entry

struct wroost_fine_entry (1 field)

§ wroost_id_t lock_id

Shift this right by WROOST_FINE_INDEX_SHIFT to get the coarse index of the fine entry

wroost_thread_data

struct wroost_thread_data (12 fields)

There’s a key invariant with fine_entries:

==================================================================== A counter is either FULLY represented in fine_entries, or completely unrepresented within fine_entries. ====================================================================

The reason why:

If 3/4 fine_entries are taken up, and a counter wants to allocate two more, then it ends up with a split: one of its contributing numbers in the counter is in the fine_entries, and one isn’t.

This means that the boost HAS to use the coarse entry, since otherwise, we risk a false negative, which would be completely against the premise of wroost.

Thus, that extra fine_entry is wasted on a lock ID that doesn’t use it. So, this invariant keeps all fine entries useful.

§ struct hlist_node map_node

Reader

§ wroost_counter_t counters[WROOST_THREAD_COUNTER_BYTES]

§ struct wroost_fine_entry fine_entries[WROOST_FINE_ENTRY_COUNT]

§ uint8_t read_nesting_depth

Writer

§ wroost_id_t want_lock_id

§ enum wroost_writer_state writer_state

§ enum thread_prio_class max_boost : THREAD_PRIO_CLASS_BIT_COUNT

boost_class_ceil is the ceil that the writer->reader boosts contribute. There is only one, and it is the maximum of any of the lock IDs it holds.

max_boost serves a completely different role. Every rwlock is instantiated with a fixed maximum on the highest thread priority class that can enter the lock. max_boost is the maximum of all of these. The idea is that if an URGENT thread blocks on a rwlock with a maximum of RT, that code will panic.

Thus, if we encounter a thread that seems to hold an ID where the urgent counter is >= 1, if this max_boost is at RT, we actually don’t boost to urgent, and boost to what’s further down (not necessarily RT either). It’s essentially a way to cheaply verify that a big boost does NOT belong to us, because if it did, the kernel would’ve crashed long before.

§ bool contributed_floor : 1

Whether this wroost_thread_data has contributed to the thread’s class_floors

Set by scheduler

§ bool in_blocked_ts_list : 1

§ bool need_bump : 1

TODO

use this to implement the optimization of knowing the readers cannot be of lower priority

§ uint8_t fine_valid : WROOST_FINE_ENTRY_COUNT

Tracks which of the 4 fine_entries are active so index == 0 does not get interpreted being a free slot

§ enum thread_prio_class floor : THREAD_PRIO_CLASS_BIT_COUNT

wroost_bucket

struct wroost_bucket (1 field)

§ atomic_uint64_t raw_tally

“tally”, so as to not conflict with “counter”:

16-bit 2 * prio_class offset counters of owner prios

wroost_hash_table

struct wroost_hash_table (2 fields)

§ struct wroost_bucket *buckets cc_counted_by(bucket_count)

§ size_t bucket_count

Enums

wroost_writer_state

enum wroost_writer_state : uint8_t (4 variants)

Writers are a simple state machine.

NONE = nothing happening WANT = “I want a lock” WAIT = “I am waiting for a lock” BUMP = “I have yielded and bumped counters”

WANT and WAIT are set in the thread’s context, and BUMP is set immediately after the WAIT reaches the switch out function.

We leave it at BUMP throughout a critical section,

§ WROOST_WRITER_NONE

§ WROOST_WRITER_WANT

§ WROOST_WRITER_WAIT

§ WROOST_WRITER_BUMP

wroost_state

enum wroost_state (3 variants)

§ WROOST_DPC_IDLE = 0

§ WROOST_DPC_PENDING = 1

§ WROOST_DPC_ACTIVE = 1 << 1

Type Aliases

wroost_id_t

typedef uint16_t wroost_id_t

wroost_counter_t

typedef uint8_t wroost_counter_t

Functions

wroost_compute_ceil

enum thread_prio_class wroost_compute_ceil(
    struct wroost_thread_data *wtd,
    enum thread_prio_class min
)

wroost_pre_acquire

void wroost_pre_acquire(
    struct rwlock *lock,
    enum rwlock_acquire_type type
)

wroost_post_acquire

void wroost_post_acquire(
    struct rwlock *lock,
    enum rwlock_acquire_type type
)

wroost_post_release

void wroost_post_release(
    struct rwlock *lock,
    enum rwlock_acquire_type type
)

wroost_scheduler_switch_in_hook

void wroost_scheduler_switch_in_hook(void)

Separate from switch_in. this runs deferred DPC notifications/IPIs onto the other CPUs

wroost_switch_in

void wroost_switch_in(struct thread *t)

wroost_switch_out

void wroost_switch_out(struct thread *t)

wroost_pre_wait

void wroost_pre_wait(struct thread *curr)

wroost_post_wait

void wroost_post_wait(struct thread *curr)

wroost_post_migrate_hook

void wroost_post_migrate_hook(
    struct thread *t,
    cpu_id_t from,
    cpu_id_t to
)

wroost_kick

size_t wroost_kick(struct wroost_kicks *kicks)

wroost_merge_kicks

bool wroost_merge_kicks(
    struct wroost_percpu_data *pcd,
    struct wroost_kicks *kicks
)

wroost_post_prio_change_locked

struct wroost_kicks cc_warn_unused_result wroost_post_prio_change_locked(
    struct thread *t,
    enum thread_prio_class old,
    enum thread_prio_class new
)

wroost_init

void wroost_init(void)

wroost_scheduler_init

void wroost_scheduler_init(struct scheduler *sched)

Macros

Thread data

WROOST_BITS_PER_COUNTER

#define WROOST_BITS_PER_COUNTER 2

WROOST_THREAD_MAP_DEPTH

#define WROOST_THREAD_MAP_DEPTH 32

WROOST_COUNTER_MAX

#define WROOST_COUNTER_MAX 0x3

WROOST_COUNTER_MASK

#define WROOST_COUNTER_MASK 0x3

WROOST_MIN_BUCKET_COUNT

#define WROOST_MIN_BUCKET_COUNT 256U

WROOST_MAX_BUCKET_COUNT

#define WROOST_MAX_BUCKET_COUNT 32768U

WROOST_BUCKETS_PER_CPU_MULT

#define WROOST_BUCKETS_PER_CPU_MULT 16U

WROOST_THREAD_COUNTERS

#define WROOST_THREAD_COUNTERS 32

WROOST_FINE_ENTRY_COUNT

#define WROOST_FINE_ENTRY_COUNT 4

WROOST_FINE_VALID_MASK

#define WROOST_FINE_VALID_MASK ((1U << WROOST_FINE_ENTRY_COUNT) - 1U)

WROOST_THREAD_COUNTER_BITS

#define WROOST_THREAD_COUNTER_BITS (WROOST_THREAD_COUNTERS * 2)

WROOST_THREAD_COUNTER_BYTES

#define WROOST_THREAD_COUNTER_BYTES (WROOST_THREAD_COUNTER_BITS / BITS_PER_BYTE)

Percpu data

WROOST_THREAD_MAP_OVERFLOW

#define WROOST_THREAD_MAP_OVERFLOW ((struct thread *) (UINTPTR_MAX))