1#pragma once
2
3#ifdef DEBUG_LOCK_CHK
4
5#include <atomic.h>
6#include <console/crash.h>
7#include <math/hash.h>
8#include <stdarg.h>
9#include <stdbool.h>
10#include <stdint.h>
11#include <string.h>
12#include <stringify.h>
13#include <structures/hlist.h>
14#include <structures/list.h>
15#include <sync/lock_chk_types.h>
16#include <sync/raw_spinlock.h>
17
18struct thread;
19
20enum lock_chk_result : uint8_t {
21 LOCK_CHK_RESULT_OK,
22 LOCK_CHK_RESULT_INACTIVE,
23 LOCK_CHK_RESULT_RECURSION,
24 LOCK_CHK_RESULT_CYCLE,
25 LOCK_CHK_RESULT_NOT_HELD,
26 LOCK_CHK_RESULT_WRONG_THREAD,
27 LOCK_CHK_RESULT_NODE_CAPACITY,
28 LOCK_CHK_RESULT_EDGE_CAPACITY,
29 LOCK_CHK_RESULT_HELD_CAPACITY,
30 LOCK_CHK_RESULT_BAD_CONTEXT,
31 LOCK_CHK_RESULT_INTERNAL,
32};
33
34struct lock_chk_node {
35 struct hlist_node hash_entry;
36 struct list_head out_edges;
37 struct list_head in_edges;
38 const struct lock_chk_class *class;
39 uint16_t id;
40 enum lock_subclass subclass;
41 uint8_t context_bits;
42};
43
44struct lock_chk_edge {
45 struct list_node from_entry;
46 struct list_node to_entry;
47 struct lock_chk_node *from;
48 struct lock_chk_node *to;
49 const struct lock_chk_site *first_site;
50 enum lock_chk_mode from_mode;
51 enum lock_chk_mode to_mode;
52};
53
54struct lock_chk_graph {
55 struct raw_spinlock lock;
56 struct hlist_head class_hash[LOCK_CHK_HASH_BUCKETS];
57 struct lock_chk_node nodes[LOCK_CHK_MAX_NODES];
58 struct lock_chk_edge edges[LOCK_CHK_MAX_EDGES];
59 uint16_t node_count;
60 uint16_t edge_count;
61 uint32_t visit_generation[LOCK_CHK_MODE_STATE_COUNT];
62 int32_t parent_state[LOCK_CHK_MODE_STATE_COUNT];
63 int32_t parent_edge[LOCK_CHK_MODE_STATE_COUNT];
64 uint16_t dfs_stack[LOCK_CHK_MODE_STATE_COUNT];
65 int32_t last_cycle_end_state;
66 uint32_t generation;
67};
68
69#define CRASH_CODES_lock_chk \
70 (CYCLE, "Lock cycle detected"), (RECURSION, "Recursive lock acquisition"), \
71 (RELEASE, "Bad lock release"), \
72 (CONTEXT, "Lock used in an invalid context"), \
73 (THREAD_EXIT, "Thread exited holding locks"), \
74 (SPIN_ORDER, "Spinlock release order violated"), \
75 (CAPACITY, "Validator capacity exhausted"), \
76 (UNINITIALIZED, "Uninitialized lock used"), \
77 (NOT_HELD, "Lock expected held, but is not"), \
78 (UNEXPECTED_HELD, "Lock held when it must not be")
79
80enum lock_chk_failure_kind : uint8_t {
81 CRASH_CODES_ENUM(lock_chk, LOCK_CHK_FAIL_)
82};
83CRASH_CODES_DECLARE(lock_chk);
84
85#define LOCK_CHK_MAX_CYCLE_HOPS 16
86
87struct lock_chk_cycle_hop {
88 const struct lock_chk_class *from_class;
89 const struct lock_chk_class *to_class;
90 const struct lock_chk_site *site;
91 uint8_t from_subclass;
92 uint8_t to_subclass;
93 enum lock_chk_mode from_mode;
94 enum lock_chk_mode to_mode;
95};
96
97#define LOCK_CHK_MSG_MAX 128
98
99/* This is the actual contents of the message of an error,
100 * and we only keep one in lock_chk_global */
101struct lock_chk_report {
102 uint64_t signature;
103 uint16_t cycle_len;
104 bool cycle_truncated;
105 struct lock_chk_cycle_hop cycle_hops[LOCK_CHK_MAX_CYCLE_HOPS];
106 char msg[LOCK_CHK_MSG_MAX];
107};
108
109/* *what* the failure actually is, which gets
110 * passed by pointer and just on the stack */
111struct lock_chk_fault {
112 enum lock_chk_failure_kind kind;
113 const struct lock_chk_class *class;
114 const struct lock_chk_site *site;
115 void *instance;
116 struct lock_chk_report *report;
117 const char *capacity_pool;
118 uint32_t capacity_used;
119 uint32_t capacity_limit;
120 enum lock_chk_type type;
121 enum lock_chk_mode mode;
122 enum lock_subclass subclass;
123};
124
125struct lock_chk_globals {
126 struct lock_chk_graph graph;
127
128 atomic(enum lock_chk_engine_state) state;
129 atomic(enum lock_chk_engine_state) deep;
130 atomic(enum lock_chk_engine_state) debug;
131
132 bool panic_on_exhaustion;
133
134 /* for claiming the report */
135 atomic_bool report_busy;
136 struct lock_chk_report report;
137};
138
139extern struct lock_chk_globals lock_chk_global;
140
141struct lock_chk_dep {
142 struct lock_chk_node *node;
143 enum lock_chk_mode mode;
144};
145
146/* Things graph operations often need, bundled together. We keep
147 * *graph in here so in the future we could potentially scale,
148 * and right now, unit tests can test their own graphs */
149struct lock_chk_ctx {
150 struct lock_chk_graph *graph;
151 const struct lock_chk_acq_req *req;
152 const struct lock_chk_thread_data *thread_data;
153 const struct lock_chk_site *site;
154 struct lock_chk_fault *fault;
155};
156
157struct lock_debug_spin_entry {
158 void *instance;
159 const struct lock_chk_site *acquire_site;
160 enum irql prev_irql;
161 enum lock_chk_type type;
162};
163
164struct lock_debug_cpu {
165 struct lock_debug_spin_entry stack[LOCK_CHK_MAX_SPIN_DEPTH];
166 uint8_t depth;
167};
168
169struct lock_chk_guard {
170 uint8_t *depth;
171 bool irqs_enabled;
172};
173
174static inline struct lock_chk_dep lock_chk_dep_make(struct lock_chk_node *node,
175 enum lock_chk_mode mode) {
176 return (struct lock_chk_dep) {.node = node, .mode = mode};
177}
178
179void lock_chk_graph_init(struct lock_chk_graph *graph);
180uint64_t lock_chk_calc_sig(const struct lock_chk_cycle_hop *hops,
181 uint16_t cycle_len);
182void lock_chk_report_fail(const struct lock_chk_fault *fault);
183enum lock_chk_result lock_chk_graph_resolve_node(const struct lock_chk_ctx *ctx,
184 struct lock_chk_map *map,
185 enum lock_subclass subclass,
186 struct lock_chk_node **out);
187enum lock_chk_result lock_chk_graph_add_dep(const struct lock_chk_ctx *ctx,
188 struct lock_chk_dep from,
189 struct lock_chk_dep to);
190enum lock_chk_result lock_chk_graph_prepare_acq(const struct lock_chk_ctx *ctx,
191 struct lock_chk_map *map,
192 enum lock_subclass subclass,
193 struct lock_chk_node **out);
194
195void lock_chk_deep_activate(void);
196void lock_debug_activate(void);
197
198void lock_chk_before_acq(struct lock_chk_acq_token *token,
199 const struct lock_chk_acq_req *request);
200void lock_chk_acqd(struct lock_chk_acq_token *token);
201void lock_chk_cancel(struct lock_chk_acq_token *token);
202void lock_chk_before_rel(struct lock_chk_rel_token *token,
203 const struct lock_chk_rel_req *request);
204void lock_chk_reld(struct lock_chk_rel_token *token);
205
206struct lock_chk_guard lock_chk_enter(void) TSA_ACQUIRES_IRQS;
207void lock_chk_leave(const struct lock_chk_guard *guard) TSA_RELEASES_IRQS;
208
209void lock_chk_thread_init(struct thread *thread);
210void lock_chk_thread_exit(struct thread *thread);
211
212static inline bool lock_chk_modes_conflict(enum lock_chk_mode a,
213 enum lock_chk_mode b) {
214 return a == LOCK_CHK_MODE_EXCLUSIVE || b == LOCK_CHK_MODE_EXCLUSIVE;
215}
216
217static inline struct lock_chk_report *lock_chk_report_claim(void) {
218 if (atomic_xchg_acq_rel(&lock_chk_global.report_busy, true))
219 return NULL;
220
221 struct lock_chk_report *report = &lock_chk_global.report;
222 report->signature = 0;
223 report->cycle_len = 0;
224 report->cycle_truncated = false;
225 report->msg[0] = '\0';
226 return report;
227}
228
229static inline void lock_chk_report_release(void) {
230 atomic_store_release(&lock_chk_global.report_busy, false);
231}
232
233cc_printf_like(2, 3) static inline void
234lock_chk_fail(struct lock_chk_fault *fault, const char *fmt, ...) {
235 fault->report = lock_chk_report_claim();
236 if (fault->report != NULL) {
237 va_list args;
238 va_start(args, fmt);
239 vsnprintf(fault->report->msg, sizeof(fault->report->msg), fmt, args);
240 va_end(args);
241 }
242
243 lock_chk_report_fail(fault);
244}
245
246static inline struct lock_chk_fault
247lock_chk_fault_from_id(enum lock_chk_failure_kind kind, struct lock_chk_id lock,
248 const struct lock_chk_map *map,
249 const struct lock_chk_site *site,
250 enum lock_chk_mode mode, enum lock_subclass subclass) {
251 return (struct lock_chk_fault) {
252 .kind = kind,
253 .class = map != NULL ? map->class : NULL,
254 .site = site,
255 .instance = lock.instance,
256 .type = lock.type,
257 .mode = mode,
258 .subclass = subclass,
259 };
260}
261
262static inline struct lock_chk_fault
263lock_chk_fault_from_req(enum lock_chk_failure_kind kind,
264 const struct lock_chk_acq_req *request) {
265 return lock_chk_fault_from_id(kind, request->lock, request->map,
266 request->site, request->mode,
267 request->subclass);
268}
269
270static inline struct lock_chk_fault
271lock_chk_fault_from_rel(enum lock_chk_failure_kind kind,
272 const struct lock_chk_rel_req *request) {
273 return lock_chk_fault_from_id(kind, request->lock, request->map,
274 request->site, request->mode, 0);
275}
276
277/* For paths holding the live lock itself */
278static inline struct lock_chk_fault lock_chk_fault_from_lock(
279 enum lock_chk_failure_kind kind, const struct lock_chk_lock *lock,
280 const struct lock_chk_site *site, enum lock_chk_mode mode) {
281 return lock_chk_fault_from_id(kind, lock_chk_id_of(lock), &lock->map, site,
282 mode, 0);
283}
284
285static inline uint64_t lock_chk_hash_bytes(uint64_t hash, const void *data,
286 size_t len) {
287 return hash_fnv1a_64_update(hash, data, len);
288}
289
290static inline uint64_t lock_chk_hash_str(uint64_t hash, const char *str) {
291 const char *value = str != NULL ? str : "";
292 return lock_chk_hash_bytes(hash, value, strlen(value));
293}
294
295static inline bool
296lock_chk_state_active(const atomic(enum lock_chk_engine_state) * state) {
297 return atomic_load_acq(state) == LOCK_CHK_ACTIVE;
298}
299
300static inline const struct lock_chk_class *
301lock_chk_map_class(const struct lock_chk_map *map) {
302 return map->class != NULL ? map->class : &map->instance_class;
303}
304
305static inline bool lock_chk_type_is_spin(enum lock_chk_type type) {
306 return type == LOCK_CHK_TYPE_SPIN || type == LOCK_CHK_TYPE_QSPIN;
307}
308
309static inline bool lock_chk_type_is_blocking(enum lock_chk_type type) {
310 return type == LOCK_CHK_TYPE_MUTEX || type == LOCK_CHK_TYPE_MUTEX_SIMPLE ||
311 type == LOCK_CHK_TYPE_RWLOCK;
312}
313
314static inline struct lock_chk_held *
315lock_chk_find_held(struct lock_chk_thread_data *thread_data,
316 const void *instance, enum lock_chk_type type,
317 bool match_type, enum lock_chk_mode mode, bool match_mode) {
318 for (uint8_t i = 0; i < thread_data->depth; i++) {
319 struct lock_chk_held *held = &thread_data->held[i];
320 if (held->lock.instance != instance)
321 continue;
322
323 if (match_type && held->lock.type != type)
324 continue;
325
326 if (match_mode && held->mode != mode)
327 continue;
328
329 return held;
330 }
331
332 return NULL;
333}
334
335static inline bool lock_op_irq_safe(enum lock_op_flags flags) {
336 return (flags & LOCK_OP_IRQ_MASK) == LOCK_OP_IRQ_HIGH;
337}
338
339static inline size_t lock_chk_class_hash(const struct lock_chk_class *class,
340 enum lock_subclass subclass) {
341 uintptr_t key = (uintptr_t) class;
342 return ((key >> 4) ^ (key >> 13) ^ subclass) % LOCK_CHK_HASH_BUCKETS;
343}
344
345static inline uint16_t lock_chk_mode_bit(enum lock_chk_mode mode) {
346 enforce(mode == LOCK_CHK_MODE_SHARED || mode == LOCK_CHK_MODE_EXCLUSIVE);
347 return mode == LOCK_CHK_MODE_EXCLUSIVE ? 1 : 0;
348}
349
350static inline uint16_t lock_chk_mode_state(const struct lock_chk_node *node,
351 enum lock_chk_mode mode) {
352 return (uint16_t) (node->id * 2 + lock_chk_mode_bit(mode));
353}
354
355static inline struct lock_chk_node *
356lock_chk_state_node(struct lock_chk_graph *graph, uint16_t state) {
357 return &graph->nodes[state / 2];
358}
359
360static inline enum lock_chk_mode lock_chk_state_mode(uint16_t state) {
361 return (state % 2) != 0 ? LOCK_CHK_MODE_EXCLUSIVE : LOCK_CHK_MODE_SHARED;
362}
363
364STRINGIFY_DECLARE_ENUM(lock_chk_type) {
365 switch (stringify_in) {
366 case LOCK_CHK_TYPE_SPIN: return "spinlock";
367 case LOCK_CHK_TYPE_QSPIN: return "qspinlock";
368 case LOCK_CHK_TYPE_MUTEX: return "mutex";
369 case LOCK_CHK_TYPE_MUTEX_SIMPLE: return "simple mutex";
370 case LOCK_CHK_TYPE_RWLOCK: return "rwlock";
371 default: cc_unreachable();
372 }
373}
374
375#endif /* DEBUG_LOCK_CHK */
376