turnstile

include/sync/turnstile.h View source View on GitHub

Structs

turnstile

struct turnstile (11 fields) source

§ struct thread_wait_header wait

§ struct thread *owner

§ struct thread_class_donation pi

§ struct list_node hash_list

§ union

§ struct list_head freelist

§ struct list_node freelist_node

§ size_t waiters

how many goobers are blocking on me?

§ void *lock_obj

lock we are for

§ struct rbt queues[TURNSTILE_NUM_QUEUES]

§ enum turnstile_state state

§ uint64_t next_wait_seq

§ uint32_t handoffs

since the last fairness turn

turnstile_hash_chain

struct turnstile_hash_chain (2 fields) source

chains in hashtable

§ struct list_head list

§ struct spinlock lock

turnstile_hash_table

struct turnstile_hash_table (1 field) source

§ struct turnstile_hash_chain heads[TURNSTILE_HASH_SIZE]

Enums

turnstile_state

enum turnstile_state (3 variants) source

§ TURNSTILE_STATE_UNUSED

we are unused by anything…

§ TURNSTILE_STATE_IN_HASH_TABLE

we are the turnstile responsible for some lock and we are in the hash table

§ TURNSTILE_STATE_IN_FREE_LIST

we are sitting on the freelist of a turnstile sitting around in the hash table of turnstiles

Functions

turnstiles_init

void turnstiles_init(void)

source

turnstile_create

struct turnstile * turnstile_create(void)

source

turnstile_destroy

void turnstile_destroy(struct turnstile *ts)

source

turnstile_init

struct turnstile * turnstile_init(struct turnstile *ts)

source

turnstile_block

struct turnstile * turnstile_block(
    struct turnstile *ts,
    size_t queue_num,
    void *lock_obj,
    enum irql lock_irql,
    struct thread *owner
)

source

turnstile_lookup

enum irql turnstile_lookup(void *obj, struct turnstile **out_ts)

source

turnstile_unlock

void turnstile_unlock(void *obj, enum irql irql)

source

turnstile_wake

void turnstile_wake(
    struct turnstile *ts,
    size_t queue,
    size_t num_threads,
    enum irql lock_irql
)

source

turnstile_propagate_wroost

bool turnstile_propagate_wroost(
    struct wroost_percpu_data *pcd,
    struct thread *t
)

source

Returns whether the caller pcd needs to re-check threads because somewhere down the PI chain, someone wanted to bother the caller pcd (also merges kicks into pcd)

turnstile_wake_handoff

void turnstile_wake_handoff(
    struct turnstile *ts,
    size_t queue,
    struct thread *target,
    enum irql lock_irql
)

source

Hand off to queue head if target is NULL

turnstile_fair_pick

struct thread * turnstile_fair_pick(
    struct turnstile *ts,
    size_t *queue_out
)

source

Called once per handoff with chain locked. NULL means we should use the priority ordering of wq_prio

turnstile_get_waiter_count

size_t turnstile_get_waiter_count(void *lock_obj)

source

turnstile_thread_priority

int32_t turnstile_thread_priority(struct thread *t)

source

Macros

TURNSTILE_WRITER_QUEUE

#define TURNSTILE_WRITER_QUEUE 0

source

TURNSTILE_READER_QUEUE

#define TURNSTILE_READER_QUEUE 1

source

TURNSTILE_NUM_QUEUES

#define TURNSTILE_NUM_QUEUES 2

source

TURNSTILE_BYPASS_LIMIT

#define TURNSTILE_BYPASS_LIMIT 4

source

Every TURNSTILE_BYPASS_LIMIT-th handoff wakes the longest waiting waiter instead of the highest wq_prio

turnstile_from_freelist

#define turnstile_from_freelist(fl)

source

Expansion

#define turnstile_from_freelist(fl) \
    (container_of(fl, struct turnstile, freelist_node))

turnstile_from_hash_list_node

#define turnstile_from_hash_list_node(hln)

source

Expansion

#define turnstile_from_hash_list_node(hln) \
    (container_of(hln, struct turnstile, hash_list))

TURNSTILE_HASH_SIZE

#define TURNSTILE_HASH_SIZE 128

source

TURNSTILE_HASH_MASK

#define TURNSTILE_HASH_MASK (TURNSTILE_HASH_SIZE - 1)

source

TURNSTILE_OBJECT_HASH

#define TURNSTILE_OBJECT_HASH(obj)

source

Expansion

#define TURNSTILE_OBJECT_HASH(obj) \
    ((((uintptr_t) (obj) >> 3) * 2654435761u) & TURNSTILE_HASH_MASK)

TURNSTILE_CHAIN

#define TURNSTILE_CHAIN(sobj)

source

Expansion

#define TURNSTILE_CHAIN(sobj) global.turnstiles[TURNSTILE_OBJECT_HASH(sobj)]