用 BFS 找出循环锁依赖的短路径

2180check_noncircular(struct held_lock *src, struct held_lock *target,2181		  struct lock_trace **const trace)2182{2183	enum bfs_result ret;2184	struct lock_list *target_entry;2185	struct lock_list src_entry;21862187	bfs_init_root(&src_entry, src);21882189	debug_atomic_inc(nr_cyclic_checks);21902191	ret = check_path(target, &src_entry, hlock_conflict, NULL, &target_entry);21922193	if (unlikely(ret == BFS_RMATCH)) {

2154static noinline enum bfs_result2155check_path(struct held_lock *target, struct lock_list *src_entry,2156	   bool (*match)(struct lock_list *entry, void *data),2157	   bool (*skip)(struct lock_list *entry, void *data),2158	   struct lock_list **target_entry)2159{2160	enum bfs_result ret;21612162	ret = __bfs_forwards(src_entry, target, match, skip, target_entry);21632164	if (unlikely(bfs_error(ret)))2165		print_bfs_bug(ret);21662167	return ret;2168}

1743	lockdep_assert_locked();17441745	__cq_init(cq);1746	__cq_enqueue(cq, source_entry);17471748	while ((lock = __bfs_next(lock, offset)) || (lock = __cq_dequeue(cq))) {1749		if (!lock->class)1750			return BFS_EINVALIDNODE;17511752		/*1753		 * Step 1: check whether we already finish on this one.1754		 *1755		 * If we have visited all the dependencies from this @lock to1756		 * others (iow, if we have visited all lock_list entries in1757		 * @lock->class->locks_{after,before}) we skip, otherwise go1758		 * and visit all the dependencies in the list and mark this1759		 * list accessed.1760		 */1761		if (lock_accessed(lock))1762			continue;1763		else1764			mark_lock_accessed(lock);

1809		first = true;1810		head = get_dep_list(lock, offset);1811		list_for_each_entry_rcu(entry, head, entry) {1812			visit_lock_entry(entry, lock);18131814			/*1815			 * Note we only enqueue the first of the list into the1816			 * queue, because we can always find a sibling1817			 * dependency from one (see __bfs_next()), as a result1818			 * the space of queue is saved.1819			 */1820			if (!first)1821				continue;18221823			first = false;18241825			if (__cq_enqueue(cq, entry))1826				return BFS_EQUEUEFULL;18271828			cq_depth = __cq_get_elem_count(cq);1829			if (max_bfs_queue_depth < cq_depth)1830				max_bfs_queue_depth = cq_depth;