1#include <stdatomic.h>
2#include <structures/pairing_heap.h>
3#include <structures/rbt.h>
4#include <thread/queue.h>
5#include <thread/thread_types.h>
6
7#define TURNSTILE_WRITER_QUEUE 0
8#define TURNSTILE_READER_QUEUE 1
9#define TURNSTILE_NUM_QUEUES 2
10
11enum turnstile_state {
12 TURNSTILE_STATE_UNUSED, /* we are unused by anything... */
13
14 TURNSTILE_STATE_IN_HASH_TABLE, /* we are the turnstile
15 * responsible for some lock
16 * and we are in the hash table */
17
18 TURNSTILE_STATE_IN_FREE_LIST, /* we are sitting on the freelist of
19 * a turnstile sitting around in the
20 * hash table of turnstiles */
21};
22
23struct turnstile {
24 struct thread *owner;
25
26 /* If a boost occurs, what did we give it? */
27 bool applied_pi_boost;
28 enum thread_prio_class prio_class;
29 struct list_head hash_list;
30 struct list_head freelist;
31 size_t waiters; /* how many goobers are blocking on me? */
32 void *lock_obj; /* lock we are for */
33 struct rbt queues[TURNSTILE_NUM_QUEUES];
34 enum turnstile_state state;
35};
36
37#define turnstile_from_freelist(fl) \
38 (container_of(fl, struct turnstile, freelist))
39#define turnstile_from_hash_list_node(hln) \
40 (container_of(hln, struct turnstile, hash_list))
41
42/* chains in hashtable */
43struct turnstile_hash_chain {
44 struct list_head list;
45 struct spinlock lock;
46};
47
48#define TURNSTILE_HASH_SIZE 128
49#define TURNSTILE_HASH_MASK (TURNSTILE_HASH_SIZE - 1)
50
51#define TURNSTILE_OBJECT_HASH(obj) \
52 ((((uintptr_t) (obj) >> 3) * 2654435761u) & TURNSTILE_HASH_MASK)
53
54#define TURNSTILE_CHAIN(sobj) global.turnstiles[TURNSTILE_OBJECT_HASH(sobj)]
55
56struct turnstile_hash_table {
57 struct turnstile_hash_chain heads[TURNSTILE_HASH_SIZE];
58};
59
60void turnstiles_init();
61struct turnstile *turnstile_create(void);
62void turnstile_destroy(struct turnstile *ts);
63struct turnstile *turnstile_init(struct turnstile *ts);
64struct turnstile *turnstile_block(struct turnstile *ts, size_t queue_num,
65 void *lock_obj, enum irql lock_irql,
66 struct thread *owner);
67struct turnstile *turnstile_lookup(void *obj, enum irql *irql_out);
68void turnstile_unlock(void *obj, enum irql irql);
69void turnstile_wake(struct turnstile *ts, size_t queue, size_t num_threads,
70 enum irql lock_irql);
71size_t turnstile_get_waiter_count(void *lock_obj);
72int32_t turnstile_thread_priority(struct thread *t);
73