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