1#include <atomic.h>
2#include <structures/pairing_heap.h>
3#include <structures/rbt.h>
4#include <thread/queue.h>
5#include <thread/thread_types.h>
6#include <thread/wait.h>
7
8#define TURNSTILE_WRITER_QUEUE 0
9#define TURNSTILE_READER_QUEUE 1
10#define TURNSTILE_NUM_QUEUES 2
11
12struct wroost_percpu_data;
13enum turnstile_state {
14 TURNSTILE_STATE_UNUSED, /* we are unused by anything... */
15
16 TURNSTILE_STATE_IN_HASH_TABLE, /* we are the turnstile
17 * responsible for some lock
18 * and we are in the hash table */
19
20 TURNSTILE_STATE_IN_FREE_LIST, /* we are sitting on the freelist of
21 * a turnstile sitting around in the
22 * hash table of turnstiles */
23};
24
25struct turnstile {
26 struct thread_wait_header wait;
27 struct thread *owner;
28
29 struct thread_class_donation pi;
30 struct list_node hash_list;
31
32 union {
33 struct list_head freelist;
34 struct list_node freelist_node;
35 };
36 size_t waiters; /* how many goobers are blocking on me? */
37 void *lock_obj; /* lock we are for */
38 struct rbt queues[TURNSTILE_NUM_QUEUES];
39 enum turnstile_state state;
40
41 uint64_t next_wait_seq;
42 uint32_t handoffs; /* since the last fairness turn */
43};
44
45/* Every TURNSTILE_BYPASS_LIMIT-th handoff wakes the longest waiting
46 * waiter instead of the highest wq_prio */
47#define TURNSTILE_BYPASS_LIMIT 4
48
49#define turnstile_from_freelist(fl) \
50 (container_of(fl, struct turnstile, freelist_node))
51#define turnstile_from_hash_list_node(hln) \
52 (container_of(hln, struct turnstile, hash_list))
53
54/* chains in hashtable */
55struct turnstile_hash_chain {
56 struct list_head list;
57 struct spinlock lock;
58};
59
60#define TURNSTILE_HASH_SIZE 128
61#define TURNSTILE_HASH_MASK (TURNSTILE_HASH_SIZE - 1)
62
63#define TURNSTILE_OBJECT_HASH(obj) \
64 ((((uintptr_t) (obj) >> 3) * 2654435761u) & TURNSTILE_HASH_MASK)
65
66#define TURNSTILE_CHAIN(sobj) global.turnstiles[TURNSTILE_OBJECT_HASH(sobj)]
67
68struct turnstile_hash_table {
69 struct turnstile_hash_chain heads[TURNSTILE_HASH_SIZE];
70};
71
72void turnstiles_init(void);
73struct turnstile *turnstile_create(void);
74void turnstile_destroy(struct turnstile *ts);
75struct turnstile *turnstile_init(struct turnstile *ts);
76struct turnstile *turnstile_block(struct turnstile *ts, size_t queue_num,
77 void *lock_obj, enum irql lock_irql,
78 struct thread *owner);
79enum irql turnstile_lookup(void *obj, struct turnstile **out_ts);
80void turnstile_unlock(void *obj, enum irql irql);
81void turnstile_wake(struct turnstile *ts, size_t queue, size_t num_threads,
82 enum irql lock_irql);
83
84/* Returns whether the caller pcd needs to re-check threads
85 * because somewhere down the PI chain, someone wanted to
86 * bother the caller pcd (also merges kicks into pcd) */
87bool turnstile_propagate_wroost(struct wroost_percpu_data *pcd,
88 struct thread *t);
89/* Hand off to queue head if `target` is NULL */
90void turnstile_wake_handoff(struct turnstile *ts, size_t queue,
91 struct thread *target, enum irql lock_irql);
92
93/* Called once per handoff with chain locked. NULL means we should
94 * use the priority ordering of wq_prio */
95struct thread *turnstile_fair_pick(struct turnstile *ts, size_t *queue_out);
96size_t turnstile_get_waiter_count(void *lock_obj);
97int32_t turnstile_thread_priority(struct thread *t);
98