1#ifdef DEBUG_LOCK_CHK
2
3#include <enforce.h>
4#include <irq/irq.h>
5#include <stddef.h>
6#include <stdint.h>
7#include <string.h>
8
9#include "internal.h"
10
11static_assert((LOCK_CHK_HASH_BUCKETS & (LOCK_CHK_HASH_BUCKETS - 1)) == 0,
12 "LOCK_CHK_HASH_BUCKETS must be a power of two");
13
14static struct lock_chk_node *node_hash_next(struct lock_chk_node *node) {
15 if (node->hash_entry.next == NULL)
16 return NULL;
17
18 return hlist_entry(node->hash_entry.next, struct lock_chk_node, hash_entry);
19}
20
21static struct lock_chk_node *find_node(struct lock_chk_graph *graph,
22 const struct lock_chk_class *class,
23 enum lock_subclass subclass) {
24 size_t bucket = lock_chk_class_hash(class, subclass);
25 struct hlist_node *first = graph->class_hash[bucket].first;
26 struct lock_chk_node *node =
27 first != NULL ? hlist_entry(first, struct lock_chk_node, hash_entry)
28 : NULL;
29
30 for (; node != NULL; node = node_hash_next(node))
31 if (node->class == class && node->subclass == subclass)
32 return node;
33
34 return NULL;
35}
36
37static enum lock_chk_result record_ctx(struct lock_chk_node *base_node,
38 const struct lock_chk_acq_req *request) {
39 if (!lock_chk_type_is_spin(request->lock.type))
40 return LOCK_CHK_RESULT_OK;
41
42 uint8_t ctx = 0;
43 if (request->in_irq || irq_in_interrupt()) {
44 ctx = LOCK_CHK_CTX_IRQ;
45 } else if (request->op_flags & LOCK_OP_RAW) {
46 if (request->prev_irql >= IRQL_HIGH_LEVEL || !request->irqs_enabled) {
47 ctx = LOCK_CHK_CTX_SPIN_HIGH;
48 } else {
49 ctx = LOCK_CHK_CTX_SPIN_DISPATCH;
50 }
51 } else if ((request->op_flags & LOCK_OP_IRQ_MASK) == LOCK_OP_IRQ_HIGH) {
52 ctx = LOCK_CHK_CTX_SPIN_HIGH;
53 } else {
54 enforce(request->op_flags & LOCK_OP_IRQ_MASK);
55 ctx = LOCK_CHK_CTX_SPIN_DISPATCH;
56 }
57
58 /* IRQ safety mismatch check */
59 if ((ctx == LOCK_CHK_CTX_SPIN_DISPATCH &&
60 (base_node->context_bits &
61 (LOCK_CHK_CTX_SPIN_HIGH | LOCK_CHK_CTX_IRQ)) != 0) ||
62 ((ctx == LOCK_CHK_CTX_SPIN_HIGH || ctx == LOCK_CHK_CTX_IRQ) &&
63 (base_node->context_bits & LOCK_CHK_CTX_SPIN_DISPATCH) != 0)) {
64 return LOCK_CHK_RESULT_BAD_CONTEXT;
65 }
66
67 base_node->context_bits |= ctx;
68 return LOCK_CHK_RESULT_OK;
69}
70
71static enum lock_chk_result resolve_node(struct lock_chk_graph *graph,
72 struct lock_chk_map *map,
73 enum lock_subclass subclass,
74 const struct lock_chk_acq_req *request,
75 struct lock_chk_node **out) {
76 if (subclass >= LOCK_CHK_MAX_SUBCLASSES)
77 return LOCK_CHK_RESULT_INTERNAL;
78
79 const struct lock_chk_class *class = lock_chk_map_class(map);
80
81 struct lock_chk_node *base_node = find_node(graph, class, 0);
82 if (base_node == NULL) {
83 if (graph->node_count == LOCK_CHK_MAX_NODES)
84 return LOCK_CHK_RESULT_NODE_CAPACITY;
85
86 base_node = &graph->nodes[graph->node_count];
87 base_node->id = graph->node_count++;
88 base_node->class = class;
89 base_node->subclass = 0;
90 base_node->context_bits = 0;
91 INIT_HLIST_NODE(&base_node->hash_entry);
92 list_head_init(&base_node->out_edges);
93 list_head_init(&base_node->in_edges);
94 hlist_add_head(&base_node->hash_entry,
95 &graph->class_hash[lock_chk_class_hash(class, 0)]);
96 }
97
98 atomic_store_release(&map->base_node, base_node);
99
100 if (request != NULL) {
101 enum lock_chk_result ctx_res = record_ctx(base_node, request);
102 if (ctx_res != LOCK_CHK_RESULT_OK)
103 return ctx_res;
104 }
105
106 if (subclass == 0) {
107 *out = base_node;
108 return LOCK_CHK_RESULT_OK;
109 }
110
111 struct lock_chk_node *node = find_node(graph, class, subclass);
112 if (node == NULL) {
113 if (graph->node_count == LOCK_CHK_MAX_NODES)
114 return LOCK_CHK_RESULT_NODE_CAPACITY;
115
116 node = &graph->nodes[graph->node_count];
117 node->id = graph->node_count++;
118 node->class = class;
119 node->subclass = subclass;
120 node->context_bits = 0;
121 INIT_HLIST_NODE(&node->hash_entry);
122 list_head_init(&node->out_edges);
123 list_head_init(&node->in_edges);
124 hlist_add_head(
125 &node->hash_entry,
126 &graph->class_hash[lock_chk_class_hash(class, subclass)]);
127 }
128
129 *out = node;
130 return LOCK_CHK_RESULT_OK;
131}
132
133static struct lock_chk_edge *find_edge(struct lock_chk_dep from,
134 struct lock_chk_dep to) {
135 struct list_node *entry;
136 list_for_each(entry, &from.node->out_edges) {
137 struct lock_chk_edge *edge =
138 list_entry(entry, struct lock_chk_edge, from_entry);
139 if (edge->to == to.node && edge->from_mode == from.mode &&
140 edge->to_mode == to.mode)
141 return edge;
142 }
143
144 return NULL;
145}
146
147static bool graph_path(struct lock_chk_graph *graph, struct lock_chk_dep start,
148 struct lock_chk_dep target) {
149 graph->generation++;
150 if (graph->generation == 0) {
151 memset(graph->visit_generation, 0, sizeof(graph->visit_generation));
152 graph->generation = 1;
153 }
154
155 uint16_t stack_depth = 0;
156 uint16_t start_state = lock_chk_mode_state(start.node, start.mode);
157 graph->dfs_stack[stack_depth++] = start_state;
158 graph->visit_generation[start_state] = graph->generation;
159 graph->parent_state[start_state] = -1;
160 graph->parent_edge[start_state] = -1;
161
162 while (stack_depth != 0) {
163 uint16_t state = graph->dfs_stack[--stack_depth];
164 struct lock_chk_node *node = lock_chk_state_node(graph, state);
165 enum lock_chk_mode mode = lock_chk_state_mode(state);
166
167 if (node == target.node && lock_chk_modes_conflict(mode, target.mode)) {
168 graph->last_cycle_end_state = (int32_t) state;
169 return true;
170 }
171
172 struct list_node *entry;
173 list_for_each(entry, &node->out_edges) {
174 struct lock_chk_edge *edge =
175 list_entry(entry, struct lock_chk_edge, from_entry);
176 if (!lock_chk_modes_conflict(mode, edge->from_mode))
177 continue;
178
179 uint16_t next = lock_chk_mode_state(edge->to, edge->to_mode);
180 if (graph->visit_generation[next] == graph->generation)
181 continue;
182
183 graph->visit_generation[next] = graph->generation;
184 graph->parent_state[next] = state;
185 graph->parent_edge[next] = (int32_t) (edge - &graph->edges[0]);
186 graph->dfs_stack[stack_depth++] = next;
187 }
188 }
189
190 return false;
191}
192
193static void publish_edge(struct lock_chk_graph *graph, struct lock_chk_dep from,
194 struct lock_chk_dep to,
195 const struct lock_chk_site *site) {
196 struct lock_chk_edge *edge = &graph->edges[graph->edge_count++];
197 edge->from = from.node;
198 edge->to = to.node;
199 edge->from_mode = from.mode;
200 edge->to_mode = to.mode;
201 edge->first_site = site;
202 list_node_init(&edge->from_entry);
203 list_node_init(&edge->to_entry);
204 list_head_push_back(&from.node->out_edges, &edge->from_entry);
205 list_head_push_back(&to.node->in_edges, &edge->to_entry);
206}
207
208static uint16_t extract_cycle(struct lock_chk_graph *graph,
209 struct lock_chk_dep from, struct lock_chk_dep to,
210 const struct lock_chk_site *site,
211 struct lock_chk_cycle_hop *hops,
212 uint16_t max_hops, bool *truncated) {
213 if (max_hops == 0)
214 return 0;
215
216 uint16_t edge_indices[LOCK_CHK_MAX_CYCLE_HOPS];
217 uint16_t num_existing_edges = 0;
218 int32_t curr = graph->last_cycle_end_state;
219
220 while (curr >= 0 && graph->parent_state[curr] != -1) {
221 int32_t e_idx = graph->parent_edge[curr];
222 if (e_idx >= 0 && num_existing_edges < LOCK_CHK_MAX_CYCLE_HOPS) {
223 edge_indices[num_existing_edges++] = (uint16_t) e_idx;
224 }
225 curr = graph->parent_state[curr];
226 }
227
228 hops[0] = (struct lock_chk_cycle_hop){
229 .from_class = from.node->class,
230 .from_subclass = from.node->subclass,
231 .from_mode = from.mode,
232 .to_class = to.node->class,
233 .to_subclass = to.node->subclass,
234 .to_mode = to.mode,
235 .site = site,
236 };
237 uint16_t count = 1;
238
239 for (int i = (int) num_existing_edges - 1; i >= 0 && count < max_hops;
240 i--) {
241 struct lock_chk_edge *e = &graph->edges[edge_indices[i]];
242 hops[count++] = (struct lock_chk_cycle_hop){
243 .from_class = e->from->class,
244 .from_subclass = e->from->subclass,
245 .from_mode = e->from_mode,
246 .to_class = e->to->class,
247 .to_subclass = e->to->subclass,
248 .to_mode = e->to_mode,
249 .site = e->first_site,
250 };
251 }
252
253 if (truncated != NULL)
254 *truncated = (num_existing_edges + 1 > max_hops);
255
256 return count;
257}
258
259static int hops_cmp(const struct lock_chk_cycle_hop *a,
260 const struct lock_chk_cycle_hop *b) {
261 const char *from_a_name = a->from_class ? a->from_class->name : "";
262 const char *from_b_name = b->from_class ? b->from_class->name : "";
263 int c = strcmp(from_a_name, from_b_name);
264 if (c != 0)
265 return c;
266
267 const char *from_a_file = a->from_class ? a->from_class->file : "";
268 const char *from_b_file = b->from_class ? b->from_class->file : "";
269 c = strcmp(from_a_file, from_b_file);
270 if (c != 0)
271 return c;
272
273 uint32_t from_a_line = a->from_class ? a->from_class->line : 0;
274 uint32_t from_b_line = b->from_class ? b->from_class->line : 0;
275 if (from_a_line != from_b_line)
276 return from_a_line < from_b_line ? -1 : 1;
277
278 if (a->from_subclass != b->from_subclass)
279 return a->from_subclass < b->from_subclass ? -1 : 1;
280
281 if (a->from_mode != b->from_mode)
282 return a->from_mode < b->from_mode ? -1 : 1;
283
284 const char *to_a_name = a->to_class ? a->to_class->name : "";
285 const char *to_b_name = b->to_class ? b->to_class->name : "";
286 c = strcmp(to_a_name, to_b_name);
287 if (c != 0)
288 return c;
289
290 const char *to_a_file = a->to_class ? a->to_class->file : "";
291 const char *to_b_file = b->to_class ? b->to_class->file : "";
292 c = strcmp(to_a_file, to_b_file);
293 if (c != 0)
294 return c;
295
296 uint32_t to_a_line = a->to_class ? a->to_class->line : 0;
297 uint32_t to_b_line = b->to_class ? b->to_class->line : 0;
298 if (to_a_line != to_b_line)
299 return to_a_line < to_b_line ? -1 : 1;
300
301 if (a->to_subclass != b->to_subclass)
302 return a->to_subclass < b->to_subclass ? -1 : 1;
303
304 if (a->to_mode != b->to_mode)
305 return a->to_mode < b->to_mode ? -1 : 1;
306
307 return 0;
308}
309
310static int compare_rotations(const struct lock_chk_cycle_hop *hops,
311 uint16_t len, uint16_t rot_a, uint16_t rot_b) {
312 for (uint16_t offset = 0; offset < len; offset++) {
313 const struct lock_chk_cycle_hop *hop_a = &hops[(rot_a + offset) % len];
314 const struct lock_chk_cycle_hop *hop_b = &hops[(rot_b + offset) % len];
315 int c = hops_cmp(hop_a, hop_b);
316 if (c != 0)
317 return c;
318 }
319 return 0;
320}
321
322uint64_t lock_chk_calc_sig(const struct lock_chk_cycle_hop *hops,
323 uint16_t cycle_len) {
324 if (cycle_len == 0)
325 return 0;
326
327 uint16_t best_rot = 0;
328 for (uint16_t i = 1; i < cycle_len; i++) {
329 if (compare_rotations(hops, cycle_len, i, best_rot) < 0)
330 best_rot = i;
331 }
332
333 uint64_t signature = HASH_FNV1A_64_OFFSET_BASIS;
334 for (uint16_t step = 0; step < cycle_len; step++) {
335 const struct lock_chk_cycle_hop *hop =
336 &hops[(best_rot + step) % cycle_len];
337 const char *from_name = hop->from_class ? hop->from_class->name : "";
338 const char *from_file = hop->from_class ? hop->from_class->file : "";
339 uint32_t from_line = hop->from_class ? hop->from_class->line : 0;
340 const char *to_name = hop->to_class ? hop->to_class->name : "";
341 const char *to_file = hop->to_class ? hop->to_class->file : "";
342 uint32_t to_line = hop->to_class ? hop->to_class->line : 0;
343
344 signature = lock_chk_hash_str(signature, from_name);
345 signature = lock_chk_hash_str(signature, from_file);
346 signature =
347 lock_chk_hash_bytes(signature, &from_line, sizeof(from_line));
348 signature = lock_chk_hash_bytes(signature, &hop->from_subclass,
349 sizeof(hop->from_subclass));
350 signature = lock_chk_hash_bytes(signature, &hop->from_mode,
351 sizeof(hop->from_mode));
352 signature = lock_chk_hash_str(signature, to_name);
353 signature = lock_chk_hash_str(signature, to_file);
354 signature = lock_chk_hash_bytes(signature, &to_line, sizeof(to_line));
355 signature = lock_chk_hash_bytes(signature, &hop->to_subclass,
356 sizeof(hop->to_subclass));
357 signature =
358 lock_chk_hash_bytes(signature, &hop->to_mode, sizeof(hop->to_mode));
359 }
360
361 return signature;
362}
363
364void lock_chk_graph_init(struct lock_chk_graph *graph) {
365 raw_spinlock_init(&graph->lock);
366 graph->node_count = 0;
367 graph->edge_count = 0;
368 graph->generation = 0;
369 graph->last_cycle_end_state = -1;
370 memset(graph->class_hash, 0, sizeof(graph->class_hash));
371 memset(graph->visit_generation, 0, sizeof(graph->visit_generation));
372}
373
374enum lock_chk_result lock_chk_graph_resolve_node(const struct lock_chk_ctx *ctx,
375 struct lock_chk_map *map,
376 enum lock_subclass subclass,
377 struct lock_chk_node **out) {
378 bool irqs_enabled = raw_spin_lock_high(&ctx->graph->lock);
379 enum lock_chk_result result =
380 resolve_node(ctx->graph, map, subclass, ctx->req, out);
381 raw_spin_unlock_irq_restore(&ctx->graph->lock, irqs_enabled);
382 return result;
383}
384
385static void make_cycle_fail(const struct lock_chk_ctx *ctx,
386 struct lock_chk_dep from, struct lock_chk_dep to) {
387 *ctx->fault = (struct lock_chk_fault){
388 .kind = LOCK_CHK_FAIL_CYCLE,
389 .site = ctx->site,
390 .class = to.node->class,
391 .subclass = to.node->subclass,
392 .mode = to.mode,
393 .report = lock_chk_report_claim(),
394 };
395
396 struct lock_chk_report *report = ctx->fault->report;
397 if (report == NULL)
398 return;
399
400 snprintf(report->msg, sizeof(report->msg), "'%s' -> '%s'",
401 from.node->class ? from.node->class->name : "lock",
402 to.node->class ? to.node->class->name : "lock");
403 report->cycle_len =
404 extract_cycle(ctx->graph, from, to, ctx->site, report->cycle_hops,
405 LOCK_CHK_MAX_CYCLE_HOPS, &report->cycle_truncated);
406 report->signature =
407 lock_chk_calc_sig(report->cycle_hops, report->cycle_len);
408}
409
410static void make_cap_fail(const struct lock_chk_ctx *ctx,
411 struct lock_chk_node *to) {
412 *ctx->fault = (struct lock_chk_fault){
413 .kind = LOCK_CHK_FAIL_CAPACITY,
414 .site = ctx->site,
415 .class = to->class,
416 .subclass = to->subclass,
417 .capacity_pool = "edges",
418 .capacity_used = ctx->graph->edge_count,
419 .capacity_limit = LOCK_CHK_MAX_EDGES,
420 .report = lock_chk_report_claim(),
421 };
422
423 if (ctx->fault->report != NULL)
424 snprintf(ctx->fault->report->msg, sizeof(ctx->fault->report->msg),
425 "dependency edges %u/%u", ctx->graph->edge_count,
426 LOCK_CHK_MAX_EDGES);
427}
428
429enum lock_chk_result lock_chk_graph_add_dep(const struct lock_chk_ctx *ctx,
430 struct lock_chk_dep from,
431 struct lock_chk_dep to) {
432 bool irqs_enabled = raw_spin_lock_high(&ctx->graph->lock);
433 enum lock_chk_result result = LOCK_CHK_RESULT_OK;
434
435 if (find_edge(from, to) != NULL)
436 goto out;
437
438 if (graph_path(ctx->graph, to, from)) {
439 if (ctx->fault != NULL)
440 make_cycle_fail(ctx, from, to);
441 result = LOCK_CHK_RESULT_CYCLE;
442 goto out;
443 }
444
445 if (ctx->graph->edge_count == LOCK_CHK_MAX_EDGES) {
446 if (ctx->fault != NULL)
447 make_cap_fail(ctx, to.node);
448 result = LOCK_CHK_RESULT_EDGE_CAPACITY;
449 goto out;
450 }
451
452 publish_edge(ctx->graph, from, to, ctx->site);
453
454out:
455 raw_spin_unlock_irq_restore(&ctx->graph->lock, irqs_enabled);
456 return result;
457}
458
459static bool dep_repeated(const struct lock_chk_thread_data *thread_data,
460 uint8_t index) {
461 const struct lock_chk_held *candidate = &thread_data->held[index];
462
463 for (uint8_t i = 0; i < index; i++) {
464 const struct lock_chk_held *prior = &thread_data->held[i];
465 if ((prior->lock.flags & LOCK_CHKD_ORDER) != 0 &&
466 prior->node == candidate->node && prior->mode == candidate->mode)
467 return true;
468 }
469
470 return false;
471}
472
473static struct lock_chk_dep held_dep(const struct lock_chk_held *held) {
474 return (struct lock_chk_dep){.node = held->node, .mode = held->mode};
475}
476
477static bool held_contribs(const struct lock_chk_thread_data *td,
478 uint8_t index) {
479 return (td->held[index].lock.flags & LOCK_CHKD_ORDER) != 0 &&
480 !dep_repeated(td, index);
481}
482
483static enum lock_chk_result add_held_deps(const struct lock_chk_ctx *ctx,
484 struct lock_chk_dep to) {
485 const struct lock_chk_thread_data *thread_data = ctx->thread_data;
486 size_t missing = 0;
487
488 for (uint8_t i = 0; i < thread_data->depth; i++) {
489 if (!held_contribs(thread_data, i))
490 continue;
491
492 struct lock_chk_dep from = held_dep(&thread_data->held[i]);
493 if (find_edge(from, to) != NULL)
494 continue;
495
496 if (graph_path(ctx->graph, to, from)) {
497 if (ctx->fault != NULL)
498 make_cycle_fail(ctx, from, to);
499 return LOCK_CHK_RESULT_CYCLE;
500 }
501 missing++;
502 }
503
504 if (missing > (size_t) (LOCK_CHK_MAX_EDGES - ctx->graph->edge_count)) {
505 if (ctx->fault != NULL)
506 make_cap_fail(ctx, to.node);
507 return LOCK_CHK_RESULT_EDGE_CAPACITY;
508 }
509
510 for (uint8_t i = 0; i < thread_data->depth; i++) {
511 if (!held_contribs(thread_data, i))
512 continue;
513
514 struct lock_chk_dep from = held_dep(&thread_data->held[i]);
515 if (find_edge(from, to) != NULL)
516 continue;
517
518 publish_edge(ctx->graph, from, to, ctx->site);
519 }
520
521 return LOCK_CHK_RESULT_OK;
522}
523
524static void rollback_nodes(struct lock_chk_graph *graph,
525 uint16_t old_node_count) {
526 while (graph->node_count > old_node_count) {
527 struct lock_chk_node *node = &graph->nodes[--graph->node_count];
528 hlist_del(&node->hash_entry);
529 }
530}
531
532enum lock_chk_result lock_chk_graph_prepare_acq(const struct lock_chk_ctx *ctx,
533 struct lock_chk_map *map,
534 enum lock_subclass subclass,
535 struct lock_chk_node **out) {
536 struct lock_chk_graph *graph = ctx->graph;
537 const struct lock_chk_acq_req *request = ctx->req;
538 bool irqs_enabled = raw_spin_lock_high(&graph->lock);
539 uint16_t old_node_count = graph->node_count;
540 struct lock_chk_node *old_base = atomic_load_rlx(&map->base_node);
541 const struct lock_chk_class *class = lock_chk_map_class(map);
542 struct lock_chk_node *existing_base = find_node(graph, class, 0);
543 uint8_t old_context_bits =
544 existing_base != NULL ? existing_base->context_bits : 0;
545
546 enum lock_chk_result result =
547 resolve_node(graph, map, subclass, request, out);
548 if (result != LOCK_CHK_RESULT_OK)
549 goto rollback;
550
551 if ((request->op_flags & LOCK_OP_KIND_MASK) == LOCK_OP_KIND_BLOCKING) {
552 result = add_held_deps(
553 ctx, (struct lock_chk_dep){.node = *out, .mode = request->mode});
554 if (result != LOCK_CHK_RESULT_OK)
555 goto rollback;
556 }
557
558 raw_spin_unlock_irq_restore(&graph->lock, irqs_enabled);
559 return LOCK_CHK_RESULT_OK;
560
561rollback:
562 rollback_nodes(graph, old_node_count);
563 if (existing_base != NULL)
564 existing_base->context_bits = old_context_bits;
565 atomic_store_rlx(&map->base_node, old_base);
566 *out = NULL;
567 raw_spin_unlock_irq_restore(&graph->lock, irqs_enabled);
568 return result;
569}
570
571#endif /* DEBUG_LOCK_CHK */
572