Skip to content

Threads

include/thread/thread.h View source View on GitHub
TODO

This header has little business being in here, we should consider moving it out of this

struct cpu_context (8 fields) source

pluh

§ uint64_t rbx
§ uint64_t rbp
§ uint64_t r12
§ uint64_t r13
§ uint64_t r14
§ uint64_t r15
§ uint64_t rsp
§ uint64_t rip
struct thread_event_reason (3 fields) source
§ uint16_t duration_ms

wait duration (clamped to UINT16_MAX ms)

§ thread_act_reason_t wait_reason
§ thread_act_reason_t wake_reason

WAKE_IO, WAKE_MANUAL, WAKE_TIMEOUT…

struct thread_activity_bucket (5 fields) source

We’re using 1024 for power of 2 division strength reduction optimizations

§ uint32_t epoch

time_ms >> THREAD_ACTIVITY_BUCKET_SHIFT

§ uint16_t run_ms

run duration in window (0..1024)

§ uint16_t block_ms

blocked duration in window (0..1024)

§ uint16_t sleep_ms

sleeping duration in window (0..1024)

§ uint16_t wake_count

saturating wake count in window

struct thread_activity_stats (1 field) source
struct thread_activity_data (4 fields) source
§ uint32_t wait_start_ms

low 32 bits of wait start time

§ uint8_t head

next slot index

§ thread_act_reason_t active_wait_reason

NONE if not waiting

struct thread_create_params (10 fields) source
§ enum thread_prio_class base_prio_class
§ enum thread_flags flags
§ size_t stack_pages
§ void *arg
§ void *stack_internal
§ struct cpu_mask allowed_cpus

Default: All CPUs (functionally identical, so technically a mask)

§ cpu_id_t on_cpu

Default: CPU_ID_MAX

§ bool pinned
§ bool joinable
§ void *private
struct thread_activity_metrics (4 fields) source
§ uint8_t run_ratio
§ uint8_t block_ratio
§ uint8_t sleep_ratio
§ uint8_t wake_freq
struct thread (83 fields) source

Unique ID allocated from global thread ID tree

§ char *name

Stack

§ void *stack cc_sized_by(stack_size)
§ size_t stack_size
§ uint32_t yield_nesting
TODO

we should isolate this into the debug nesting mode, as this helps us identify scheduler_yield() nesting

§ uint32_t yield_nesting_max

Preserves the highest point yield_nesting ever reached

§ struct cpu_context regs

Registers

§ union
TODO

Use unions and combine these. Do make sure to keep in mind that all nodes get need to get reset if unions are to be used

§ struct list_node reaper_list

reaper list

§ struct list_node thread_list

global list of threads

§ union
§ struct rbt_node rq_tree_node

runqueue tree node

§ struct rbt_node rt_tree_node

alias for rt scheduling

§ union
§ struct list_node rq_list_node

runqueue list node

§ struct list_node rt_list_node

alias for rt scheduling

§ struct rbt_node wq_tree_node

Waitqueue nodes. TODO: union

waitqueue tree node

§ int32_t wq_prio

turnstile sort key TODO: there is probably a smarter way

§ uint64_t wq_seq

Turnstile arrival order sequence count

§ struct list_node wq_list_node

waitqueue list node

§ struct list_node rcu_list_node

blocked reader node on RCU leaf

§ atomic(enum thread_state) state

State

§ cpu_id_t curr_core

Who is running us?

-1 if not being ran

§ atomic(struct scheduler *) scheduler
TODO

implement a core_to_wake_on

§ time_ms_t run_start_time

When did we start running

§ atomic_uint32_t pinned_depth

Who is allowed to run us?

§ struct cpu_mask allowed_cpus
§ atomic_int64_t migrate_to

-1 if no migration target

Flags

§ enum rt_scheduler_capability accepted_rt_caps
§ atomic(enum thread_flags) flags
§ atomic_size_t migration_generation
§ thread_prio_t activity_score

Priorities

§ int32_t dynamic_delta

Signed delta applied to base

§ size_t weight
§ nice_t niceness

-20 .. + 19

§ cpu_perf_t wanted_perf

This is the cpu_perf_t the thread’s current CPU should try to match or do better than.

If the current CPU’s current wanted_perf does not satisfy the thread, we will try to either increase it for this CPU, or migrate the thread to another CPU.

§ time_ms_t last_class_change_ms

Class changes

§ uint64_t completed_period

Timeslice info and periods

§ time_ms_t period_runtime_raw_ms

Raw MS time of runtime this period

§ time_ms_t budget_time_raw_ms

Raw MS time of budget

§ time_ms_t timeslice_length_raw_ms
§ uint32_t virtual_period_runtime
§ uint32_t virtual_budget
§ uint32_t virtual_runtime_left
§ enum thread_activity_class activity_class : 4
§ enum thread_prio_class perceived_prio_class : THREAD_PRIO_CLASS_BIT_COUNT
§ enum thread_prio_class base_prio_class

for class boosts

§ struct spinlock pi_lock

Rules with this lock:

This lock is meant to synchronize updates to perceived_prio_class and base_prio_class. It is only meant to be used when

(1) you are updating a thread on another CPU OR a non-running thread on THIS CPU and ALSO have the runqueue lock held prior to taking this, and will update the thread positions after doing this, OR

(2) you are updating the currently running thread on the calling CPU, it is OK to NOT have the runqueue lock held.

In any case, the scheduler will not see an invalid perceived_prio_class, and should be able to make decisions based on it, as it would be properly locked.

§ uint8_t class_floors[THREAD_PRIO_CLASS_COUNT]

Also protected by pi_lock, perceived_prio_class = max(base_prio_class, highest class with a boost). remember to thread_recompute_prio_class_locked after changing things

Activity data

§ struct thread_activity_data activity_data
§ struct thread_activity_stats activity_stats
§ struct thread_activity_metrics activity_metrics

“Overview” derived from data and stats

Lock + rc

§ struct spinlock lock
§ refcount_t refcount
§ struct spinlock join_lock

Join

guards exit_status + the ZOMBIE publish

§ struct condvar join_cv

joiners wait here

§ int exit_status
§ uint32_t rcu_nesting

RCU stuff:

rcu_nesting and rcu_read_seq are written ONLY by this thread

rcu_leaf, rcu_blocked_seq, and rcu_list_node are how readers that get preempted mid-section get registered in RCU,

those are written under the leaf’s lock, either by us or the CPU switching us out

read section depth

§ uint64_t rcu_read_seq

GP sequence at the outermost lock

§ struct rcu_node *rcu_leaf

leaf we are registered on or NULL

§ uint64_t rcu_blocked_seq

GP we are counted against or 0

§ struct rcu_cb free_rcu
§ enum thread_state wait_state
§ enum thread_resume_reason wait_completion_reason

Storage

§ struct spinlock wait_lock
§ struct thread_wait_block *active_wait_blocks
§ size_t wait_block_count
§ atomic_uint64_t wait_epoch

Every new wait bumps this, and it gets updated under wait_lock.

While any block of the wait remains linked, the wait header’s lock prevents this from changing, since waits can’t end, and new ones can’t start, without unlinking the respective block.

§ uint16_t wait_key
§ enum thread_wait_status wait_status
§ bool wait_done : 1
§ bool alert_pending : 1
§ bool object_wait : 1
§ atomic(enum thread_wait_type) wait_type
§ struct timer wait_timer

for thread_wait_complete_timeout

§ uint64_t wait_timer_epoch

epoch the armed timer could end

§ struct list_head io_wait_tokens

list of tokens. NOTE: deprecated

§ struct turnstile *turnstile

my turnstile

§ atomic(struct turnstile *) blocked_ts

what am I blocked on

§ struct climb_thread_data climb_data
§ struct wroost_thread_data wroost_data
§ tlb_stamp_t lazy_tlb_gen
§ struct apc_queue apc_head[APC_TYPE_COUNT]

Standard APC queues

§ atomic_uint8_t apc_pending_mask

Any APC pending

bitmask of APC_TYPE_* pending

APC disable counts

§ uint32_t special_apc_disable
§ uint32_t kernel_apc_disable
§ void *private

Misc. private field for whatever needs it

Activity aggregations

enum thread_activity_class (5 variants) source
§ THREAD_ACTIVITY_CLASS_CPU_BOUND
§ THREAD_ACTIVITY_CLASS_IO_BOUND
§ THREAD_ACTIVITY_CLASS_INTERACTIVE
§ THREAD_ACTIVITY_CLASS_SLEEPY
§ THREAD_ACTIVITY_CLASS_UNKNOWN
struct thread * thread_create_internal(
    thread_entry_fn_t entry,
    struct thread_create_params params,
    char *fmt
)
source
struct thread * thread_spawn_internal(
    thread_entry_fn_t entry,
    struct thread_create_params params,
    char *fmt
)
source
void thread_set_joinable(struct thread *t)
source
void thread_free(struct thread *t)
source
void thread_init_thread_ids(void)
source
cc_noreturn void thread_exit(void)
source
void thread_print(const struct thread *t)
source
void thread_classify_activity(struct thread *t, uint64_t now_ms)
source
void thread_update_runtime_buckets(
    struct thread *thread,
    time_ms_t time
)
source
void thread_apply_wake_boost(struct thread *t)
source
void thread_update_effective_priority(struct thread *t)
source
void thread_apply_cpu_penalty(struct thread *t)
source
void thread_add_wake_reason(
    struct thread *t,
    thread_act_reason_t reason
)
source
void thread_calculate_activity_data(struct thread *t)
source
void thread_add_block_reason(
    struct thread *t,
    thread_act_reason_t reason
)
source
void thread_add_sleep_reason(
    struct thread *t,
    thread_act_reason_t reason
)
source
void thread_set_timesharing(struct thread *t)
source
void thread_set_background(struct thread *t)
source
void thread_migrate(struct thread *t, size_t dest_core)
source
void thread_boost_self(enum thread_prio_class class)
source
void thread_unboost_self(enum thread_prio_class class)
source
void thread_enqueue(struct thread *t)
source
void thread_enqueue_on_core(struct thread *t, uint64_t core_id)
source
struct wroost_kicks cc_warn_unused_result thread_recompute_prio_class_locked(struct thread *t)
source
enum thread_prio_class thread_recompute_prio_class_dry_locked(
    struct thread *t,
    enum thread_prio_class *old_out,
    enum thread_prio_class *new_out
)
source

Dry run: see what the new prio would be, don’t set anything

void thread_recompute_prio_class_raw_locked(
    struct thread *t,
    enum thread_prio_class *old_out,
    enum thread_prio_class *new_out
)
source
bool thread_inherit_priority(
    struct thread *boosted,
    struct thread *from,
    struct thread_class_donation *d,
    struct wroost_kicks *kicks_out
)
source
void thread_donate_class(
    struct thread *boosted,
    enum thread_prio_class class,
    struct thread_class_donation *d
)
source
void thread_uninherit_priority(struct thread_class_donation *d)
source
void thread_remove_boost(void)
source
cc_noreturn void thread_exit_with_status(int status)
source
int thread_join(struct thread *t)
source
bool thread_join_timeout(
    struct thread *t,
    time_ms_t timeout_ms,
    int *status_out
)
source
void thread_detach(struct thread *t)
source
void thread_lock_two_runqueues(
    struct thread *a,
    struct thread *b,
    struct scheduler **out_rq_a,
    struct scheduler **out_rq_b,
    enum irql *irq_a,
    enum irql *irq_b
)
source
void thread_lock_thread_and_rq(
    struct thread *t,
    struct scheduler *other_rq,
    struct scheduler **out_thread_rq,
    enum irql *irq_first,
    enum irql *irq_second
)
source
void thread_unlock_thread_and_rq(
    struct scheduler *thread_rq,
    struct scheduler *other_rq,
    enum irql irq_first,
    enum irql irq_second
)
source
bool thread_in_context(void)
source
REFCOUNT_GENERATE_GETREF_FOR_STRUCT_WITH_FAILURE_COND(thread, refcount, flags, &THREAD_FLAG_DYING) (1 declaration) source
§ bool thread_getref(struct thread *obj)
void reaper_enqueue(struct thread *t)
source
void thread_putref(struct thread *t)
source
uint32_t scheduler_yield_nesting(struct thread *t)
source
void scheduler_yield_nesting_enter(struct thread *t)
source
uint32_t scheduler_yield_nesting_max(struct thread *t)
source
void scheduler_yield_nesting_exit(struct thread *t)
source
void scheduler_yield_nesting_reset(struct thread *t)
source
struct thread * thread_get_current(void)
source
int64_t thread_set_migration_target(struct thread *t, int64_t new)
source
enum thread_state thread_get_state(struct thread *t)
source
void thread_set_state(struct thread *t, enum thread_state state)
source
enum thread_flags thread_get_flags(struct thread *t)
source
void thread_set_flags(struct thread *t, enum thread_flags new)
source
uint32_t thread_pin(struct thread *t)
source
uint32_t thread_unpin(struct thread *t)
source
bool thread_is_pinned(struct thread *t)
source
enum thread_flags thread_or_flags(
    struct thread *t,
    enum thread_flags flags
)
source
enum thread_flags thread_and_flags(
    struct thread *t,
    enum thread_flags flags
)
source
enum thread_flags thread_set_flag(
    struct thread *t,
    enum thread_flags flag
)
source
enum thread_flags thread_clear_flag(
    struct thread *t,
    enum thread_flags flag
)
source
bool thread_test_flag(struct thread *t, enum thread_flags flag)
source
size_t thread_get_migration_generation(struct thread *t)
source
struct scheduler * thread_get_scheduler_unsafe(struct thread *t)
source
void thread_set_runqueue(struct thread *t, struct scheduler *s)
source
bool thread_getref_rcu(struct thread *t)
source

RCU keeps the thread memory allocated so we inc_not_zero here and everything is fine and dandy, everything must be in a read side critical section, though

enum irql thread_acquire_internal(
    struct thread *t,
    bool (*fn)(struct thread *),
    bool *success
)
source
enum irql thread_acquire(struct thread *t, bool *success)
source
enum irql thread_acquire_rcu(struct thread *t, bool *success)
source
void thread_release(struct thread *t, enum irql irql)
source
bool thread_is_rt(struct thread *t)
source
enum thread_wait_type thread_get_wait_type(struct thread *t)
source
#define THREAD_DEFAULT_TIMESLICE 15
source

15 ms

#define THREAD_CLASS_WIDTH 1024
source
#define THREAD_CLASS_HALF (THREAD_CLASS_WIDTH / 2)
source
#define THREAD_BAND_MIN(avg)
source
Expansion
#define THREAD_BAND_MIN(avg) ((avg) - THREAD_CLASS_HALF)
#define THREAD_BAND_MAX(avg)
source
Expansion
#define THREAD_BAND_MAX(avg) ((avg) + THREAD_CLASS_HALF)
#define THREAD_ACT_INTERACTIVE_AVG 4000u
source
#define THREAD_ACT_IO_BOUND_AVG 2500u
source
#define THREAD_ACT_CPU_BOUND_AVG 1200u
source
#define THREAD_ACT_SLEEPY_AVG 4500u
source
#define THREAD_ACT_INTERACTIVE_MIN THREAD_BAND_MIN(THREAD_ACT_INTERACTIVE_AVG)
source
#define THREAD_ACT_INTERACTIVE_MAX THREAD_BAND_MAX(THREAD_ACT_INTERACTIVE_AVG)
source
#define THREAD_ACT_IO_BOUND_MIN THREAD_BAND_MIN(THREAD_ACT_IO_BOUND_AVG)
source
#define THREAD_ACT_IO_BOUND_MAX THREAD_BAND_MAX(THREAD_ACT_IO_BOUND_AVG)
source
#define THREAD_ACT_CPU_BOUND_MIN THREAD_BAND_MIN(THREAD_ACT_CPU_BOUND_AVG)
source
#define THREAD_ACT_CPU_BOUND_MAX THREAD_BAND_MAX(THREAD_ACT_CPU_BOUND_AVG)
source
#define THREAD_ACT_SLEEPY_MIN THREAD_BAND_MIN(THREAD_ACT_SLEEPY_AVG)
source
#define THREAD_ACT_SLEEPY_MAX THREAD_BAND_MAX(THREAD_ACT_SLEEPY_AVG)
source
#define THREAD_NICENESS_VALID(n)
source
Expansion
#define THREAD_NICENESS_VALID(n) IN_RANGE((nice_t) (n), NICE_MIN, NICE_MAX)
#define THREAD_EVENT_REASON_NONE 0xFF
source
#define THREAD_PRIO_HAS_TIMESLICE(prio)
source

Background threads share timeslices

Expansion
#define THREAD_PRIO_HAS_TIMESLICE(prio) \
    (prio == THREAD_PRIO_CLASS_TIMESHARE || \
     prio == THREAD_PRIO_CLASS_BACKGROUND)
#define THREAD_ACTIVITY_BUCKET_COUNT 4
source
#define THREAD_ACTIVITY_BUCKET_SHIFT 10
source
#define THREAD_ACTIVITY_BUCKET_DURATION
source
Expansion
#define THREAD_ACTIVITY_BUCKET_DURATION \
    (1U << THREAD_ACTIVITY_BUCKET_SHIFT) /* 1024 ms (~1s) */
#define THREAD_ACTIVITY_BUCKET_MASK (THREAD_ACTIVITY_BUCKET_DURATION - 1U)
source
#define THREAD_ACTIVITY_INDEX_MASK (THREAD_ACTIVITY_BUCKET_COUNT - 1U)
source
#define THREAD_EVENT_RINGBUFFER_CAPACITY THREAD_ACTIVITY_BUCKET_COUNT
source
#define THREAD_EVENT_RINGBUFFER_MASK (THREAD_EVENT_RINGBUFFER_CAPACITY - 1U)
source
#define TOTAL_BUCKET_DURATION
source
#define thread_from_rq_rbt_node(node)
source
Expansion
#define thread_from_rq_rbt_node(node) \
    rbt_entry(node, struct thread, rq_tree_node)
#define thread_from_rq_list_node(ln)
source
Expansion
#define thread_from_rq_list_node(ln) \
    (container_of(ln, struct thread, rq_list_node))
#define thread_from_rcu_list_node(ln)
source
Expansion
#define thread_from_rcu_list_node(ln) \
    (container_of(ln, struct thread, rcu_list_node))
#define thread_from_wq_pairing_node(pn)
source
Expansion
#define thread_from_wq_pairing_node(pn) \
    (container_of(pn, struct thread, wq_pairing_node))
#define thread_from_wq_list_node(ln)
source
Expansion
#define thread_from_wq_list_node(ln) \
    (container_of(ln, struct thread, wq_list_node))
#define thread_from_wq_rbt_node(ln)
source
Expansion
#define thread_from_wq_rbt_node(ln) \
    (container_of(ln, struct thread, wq_tree_node))
#define thread_log(lvl, fmt, ...)
source
Expansion
#define thread_log(lvl, fmt, ...) \
    ({ \
        if (global.current_bootstage >= BOOTSTAGE_LATE) \
            log(thread_get_current()->log_site, \
                &thread_get_current()->log_handle, lvl, fmt, ##__VA_ARGS__); \
    })
#define thread_err(fmt, ...)
source
Expansion
#define thread_err(fmt, ...) thread_log(LOG_ERROR, fmt, ##__VA_ARGS__)
#define thread_warn(fmt, ...)
source
Expansion
#define thread_warn(fmt, ...) thread_log(LOG_WARN, fmt, ##__VA_ARGS__)
#define thread_info(fmt, ...)
source
Expansion
#define thread_info(fmt, ...) thread_log(LOG_INFO, fmt, ##__VA_ARGS__)
#define thread_debug(fmt, ...)
source
Expansion
#define thread_debug(fmt, ...) thread_log(LOG_DEBUG, fmt, ##__VA_ARGS__)
#define thread_trace(fmt, ...)
source
Expansion
#define thread_trace(fmt, ...) thread_log(LOG_TRACE, fmt, ##__VA_ARGS__)
#define SCHED_MAX_YIELD_NESTING 1
source
#define THREAD_CREATE_PARAMS_DEFAULTS
source
Expansion
#define THREAD_CREATE_PARAMS_DEFAULTS \
    .stack_pages = (THREAD_STACK_SIZE / PAGE_SIZE), .on_cpu = CPU_ID_MAX, \
    .joinable = false, .pinned = false, .allowed_cpus = CPU_MASK_INIT_ALL, \
    .arg = NULL, .private = NULL, .stack_internal = NULL, .flags = 0, \
    .base_prio_class = THREAD_PRIO_CLASS_TIMESHARE
#define thread_params_with_defaults(...)
source
#define thread_create(name, entry, ...)
source
Expansion
#define thread_create(name, entry, ...) \
    thread_create_internal((entry), \
                           (struct thread_create_params) \
                               thread_params_with_defaults(__VA_ARGS__), \
                           PP_UNPAREN(name))
#define thread_spawn(name, entry, ...)
source
Expansion
#define thread_spawn(name, entry, ...) \
    thread_spawn_internal((entry), \
                          (struct thread_create_params) \
                              thread_params_with_defaults(__VA_ARGS__), \
                          PP_UNPAREN(name))