1 // SPDX-License-Identifier: GPL-2.0
13 	__six_lock_init(&b->lock, "b->c.lock", &bch2_btree_node_lock_key, flags, gfp);  in bch2_btree_lock_init()
14 	lockdep_set_notrack_class(&b->lock);  in bch2_btree_lock_init()
22 						  unsigned level)  in bch2_btree_node_lock_counts()  argument
34 		if (path != skip && &path->l[level].b->c == b) {  in bch2_btree_node_lock_counts()
35 			int t = btree_node_locked_type(path, level);  in bch2_btree_node_lock_counts()
64 	u8				level;  member
77 	prt_printf(out, "Found lock cycle (%u entries):\n", g->nr);  in print_cycle()
79 	for (i = g->g; i < g->g + g->nr; i++) {  in print_cycle()
80 		struct task_struct *task = READ_ONCE(i->trans->locking_wait.task);  in print_cycle()
84 		bch2_btree_trans_to_text(out, i->trans);  in print_cycle()
85 		bch2_prt_task_backtrace(out, task, i == g->g ? 5 : 1, GFP_NOWAIT);  in print_cycle()
93 	for (i = g->g; i != g->g + g->nr; i++) {  in print_chain()
94 		struct task_struct *task = i->trans->locking_wait.task;  in print_chain()
95 		if (i != g->g)  in print_chain()
96 			prt_str(out, "<- ");  in print_chain()
97 		prt_printf(out, "%u ", task ?task->pid : 0);  in print_chain()
104 	closure_put(&g->g[--g->nr].trans->ref);  in lock_graph_up()
109 	while (g->nr)  in lock_graph_pop_all()
115 	while (g->g + g->nr > i)  in lock_graph_pop_from()
121 	g->g[g->nr++] = (struct trans_waiting_for_lock) {  in __lock_graph_down()
123 		.node_want	= trans->locking,  in __lock_graph_down()
124 		.lock_want	= trans->locking_wait.lock_want,  in __lock_graph_down()
130 	closure_get(&trans->ref);  in lock_graph_down()
139 	if (from->trans->locking != from->node_want) {  in lock_graph_remove_non_waiters()
144 	for (i = from + 1; i < g->g + g->nr; i++)  in lock_graph_remove_non_waiters()
145 		if (i->trans->locking != i->node_want ||  in lock_graph_remove_non_waiters()
146 		    i->trans->locking_wait.start_time != i[-1].lock_start_time) {  in lock_graph_remove_non_waiters()
156 	struct bch_fs *c = trans->c;  in trace_would_deadlock()
173 	if (i == g->g) {  in abort_lock()
174 		trace_would_deadlock(g, i->trans);  in abort_lock()
175 		return btree_trans_restart(i->trans, BCH_ERR_transaction_restart_would_deadlock);  in abort_lock()
177 		i->trans->lock_must_abort = true;  in abort_lock()
178 		wake_up_process(i->trans->locking_wait.task);  in abort_lock()
185 	if (trans->lock_may_not_fail)  in btree_trans_abort_preference()
187 	if (trans->locking_wait.lock_want == SIX_LOCK_write)  in btree_trans_abort_preference()
189 	if (!trans->in_traverse_all)  in btree_trans_abort_preference()
207 		ret = -1;  in break_cycle()
211 	for (i = from; i < g->g + g->nr; i++) {  in break_cycle()
212 		pref = btree_trans_abort_preference(i->trans);  in break_cycle()
223 		prt_printf(&buf, bch2_fmt(g->g->trans->c, "cycle of nofail locks"));  in break_cycle()
225 		for (i = g->g; i < g->g + g->nr; i++) {  in break_cycle()
226 			struct btree_trans *trans = i->trans;  in break_cycle()
232 			bch2_prt_task_backtrace(&buf, trans->locking_wait.task, 2, GFP_NOWAIT);  in break_cycle()
254 	struct btree_trans *orig_trans = g->g->trans;  in lock_graph_descend()
257 	for (i = g->g; i < g->g + g->nr; i++)  in lock_graph_descend()
258 		if (i->trans == trans) {  in lock_graph_descend()
259 			closure_put(&trans->ref);  in lock_graph_descend()
263 	if (g->nr == ARRAY_SIZE(g->g)) {  in lock_graph_descend()
264 		closure_put(&trans->ref);  in lock_graph_descend()
266 		if (orig_trans->lock_may_not_fail)  in lock_graph_descend()
274 		trace_and_count(trans->c, trans_restart_would_deadlock_recursion_limit, trans, _RET_IP_);  in lock_graph_descend()
290 	struct trans_waiting_for_lock *top;  in bch2_check_for_deadlock()  local
297 	if (trans->lock_must_abort && !trans->lock_may_not_fail) {  in bch2_check_for_deadlock()
299 			return -1;  in bch2_check_for_deadlock()
307 	/* trans->paths is rcu protected vs. freeing */  in bch2_check_for_deadlock()
310 		cycle->atomic++;  in bch2_check_for_deadlock()
315 	top = &g.g[g.nr - 1];  in bch2_check_for_deadlock()
317 	struct btree_path *paths = rcu_dereference(top->trans->paths);  in bch2_check_for_deadlock()
324 				     path_idx, top->path_idx) {  in bch2_check_for_deadlock()
326 		if (!path->nodes_locked)  in bch2_check_for_deadlock()
329 		if (path_idx != top->path_idx) {  in bch2_check_for_deadlock()
330 			top->path_idx		= path_idx;  in bch2_check_for_deadlock()
331 			top->level		= 0;  in bch2_check_for_deadlock()
332 			top->lock_start_time	= 0;  in bch2_check_for_deadlock()
336 		     top->level < BTREE_MAX_DEPTH;  in bch2_check_for_deadlock()
337 		     top->level++, top->lock_start_time = 0) {  in bch2_check_for_deadlock()
338 			int lock_held = btree_node_locked_type(path, top->level);  in bch2_check_for_deadlock()
343 			b = &READ_ONCE(path->l[top->level].b)->c;  in bch2_check_for_deadlock()
349 				 * structures - which means it can't be blocked  in bch2_check_for_deadlock()
368 			if (list_empty_careful(&b->lock.wait_list))  in bch2_check_for_deadlock()
371 			raw_spin_lock(&b->lock.wait_lock);  in bch2_check_for_deadlock()
372 			list_for_each_entry(trans, &b->lock.wait_list, locking_wait.list) {  in bch2_check_for_deadlock()
373 				BUG_ON(b != trans->locking);  in bch2_check_for_deadlock()
375 				if (top->lock_start_time &&  in bch2_check_for_deadlock()
376 				    time_after_eq64(top->lock_start_time, trans->locking_wait.start_time))  in bch2_check_for_deadlock()
379 				top->lock_start_time = trans->locking_wait.start_time;  in bch2_check_for_deadlock()
382 				if (trans == top->trans ||  in bch2_check_for_deadlock()
383 				    !lock_type_conflicts(lock_held, trans->locking_wait.lock_want))  in bch2_check_for_deadlock()
386 				closure_get(&trans->ref);  in bch2_check_for_deadlock()
387 				raw_spin_unlock(&b->lock.wait_lock);  in bch2_check_for_deadlock()
395 			raw_spin_unlock(&b->lock.wait_lock);  in bch2_check_for_deadlock()
405 		--cycle->atomic;  in bch2_check_for_deadlock()
421 	int readers = bch2_btree_node_lock_counts(trans, NULL, b, b->level).n[SIX_LOCK_read];  in __bch2_btree_node_lock_write()
425 	 * Must drop our read locks before calling six_lock_write() -  in __bch2_btree_node_lock_write()
430 	six_lock_readers_add(&b->lock, -readers);  in __bch2_btree_node_lock_write()
433 	six_lock_readers_add(&b->lock, readers);  in __bch2_btree_node_lock_write()
436 		mark_btree_node_locked_noreset(path, b->level, BTREE_NODE_INTENT_LOCKED);  in __bch2_btree_node_lock_write()
456 	unsigned l = path->level;  in btree_path_get_locks()
457 	int fail_idx = -1;  in btree_path_get_locks()
469 				f->l	= l;  in btree_path_get_locks()
470 				f->b	= path->l[l].b;  in btree_path_get_locks()
475 	} while (l < path->locks_want);  in btree_path_get_locks()
487 			path->l[fail_idx].b = upgrade  in btree_path_get_locks()
488 				? ERR_PTR(-BCH_ERR_no_btree_node_upgrade)  in btree_path_get_locks()
489 				: ERR_PTR(-BCH_ERR_no_btree_node_relock);  in btree_path_get_locks()
490 			--fail_idx;  in btree_path_get_locks()
494 	if (path->uptodate == BTREE_ITER_NEED_RELOCK)  in btree_path_get_locks()
495 		path->uptodate = BTREE_ITER_UPTODATE;  in btree_path_get_locks()
497 	return path->uptodate < BTREE_ITER_NEED_RELOCK;  in btree_path_get_locks()
501 			      struct btree_path *path, unsigned level,  in __bch2_btree_node_relock()  argument
504 	struct btree *b = btree_path_node(path, level);  in __bch2_btree_node_relock()
505 	int want = __btree_lock_want(path, level);  in __bch2_btree_node_relock()
510 	if (six_relock_type(&b->c.lock, want, path->l[level].lock_seq) ||  in __bch2_btree_node_relock()
511 	    (btree_node_lock_seq_matches(path, b, level) &&  in __bch2_btree_node_relock()
512 	     btree_node_lock_increment(trans, &b->c, level, want))) {  in __bch2_btree_node_relock()
513 		mark_btree_node_locked(trans, path, level, want);  in __bch2_btree_node_relock()
517 	if (trace && !trans->notrace_relock_fail)  in __bch2_btree_node_relock()
518 		trace_and_count(trans->c, btree_path_relock_fail, trans, _RET_IP_, path, level);  in __bch2_btree_node_relock()
525 			     struct btree_path *path, unsigned level)  in bch2_btree_node_upgrade()  argument
527 	struct btree *b = path->l[level].b;  in bch2_btree_node_upgrade()
529 	if (!is_btree_node(path, level))  in bch2_btree_node_upgrade()
532 	switch (btree_lock_want(path, level)) {  in bch2_btree_node_upgrade()
534 		BUG_ON(btree_node_locked(path, level));  in bch2_btree_node_upgrade()
537 		BUG_ON(btree_node_intent_locked(path, level));  in bch2_btree_node_upgrade()
538 		return bch2_btree_node_relock(trans, path, level);  in bch2_btree_node_upgrade()
545 	if (btree_node_intent_locked(path, level))  in bch2_btree_node_upgrade()
551 	if (btree_node_locked(path, level)  in bch2_btree_node_upgrade()
552 	    ? six_lock_tryupgrade(&b->c.lock)  in bch2_btree_node_upgrade()
553 	    : six_relock_type(&b->c.lock, SIX_LOCK_intent, path->l[level].lock_seq))  in bch2_btree_node_upgrade()
556 	if (btree_node_lock_seq_matches(path, b, level) &&  in bch2_btree_node_upgrade()
557 	    btree_node_lock_increment(trans, &b->c, level, BTREE_NODE_INTENT_LOCKED)) {  in bch2_btree_node_upgrade()
558 		btree_node_unlock(trans, path, level);  in bch2_btree_node_upgrade()
562 	trace_and_count(trans->c, btree_path_upgrade_fail, trans, _RET_IP_, path, level);  in bch2_btree_node_upgrade()
565 	mark_btree_node_locked_noreset(path, level, BTREE_NODE_INTENT_LOCKED);  in bch2_btree_node_upgrade()
572  * Only for btree_cache.c - only relocks intent locks
579 	for (l = path->level;  in bch2_btree_path_relock_intent()
580 	     l < path->locks_want && btree_path_node(path, l);  in bch2_btree_path_relock_intent()
585 			trace_and_count(trans->c, trans_restart_relock_path_intent, trans, _RET_IP_, path);  in bch2_btree_path_relock_intent()
607 		trace_and_count(trans->c, trans_restart_relock_path, trans, trace_ip, path);  in __bch2_btree_path_relock()
619 	EBUG_ON(path->locks_want >= new_locks_want);  in bch2_btree_path_upgrade_noupgrade_sibs()
621 	path->locks_want = new_locks_want;  in bch2_btree_path_upgrade_noupgrade_sibs()
638 	 * XXX: this is ugly - we'd prefer to not be mucking with other  in __bch2_btree_path_upgrade()
641 	 * On failure to upgrade the iterator, setting iter->locks_want and  in __bch2_btree_path_upgrade()
649 	 * an iterator is a copy - for now, we'll just upgrade any other  in __bch2_btree_path_upgrade()
653 	 * before interior nodes - now that's handled by  in __bch2_btree_path_upgrade()
656 	if (!path->cached && !trans->in_traverse_all) {  in __bch2_btree_path_upgrade()
662 			    linked->cached == path->cached &&  in __bch2_btree_path_upgrade()
663 			    linked->btree_id == path->btree_id &&  in __bch2_btree_path_upgrade()
664 			    linked->locks_want < new_locks_want) {  in __bch2_btree_path_upgrade()
665 				linked->locks_want = new_locks_want;  in __bch2_btree_path_upgrade()
678 	unsigned l, old_locks_want = path->locks_want;  in __bch2_btree_path_downgrade()
680 	if (trans->restarted)  in __bch2_btree_path_downgrade()
683 	EBUG_ON(path->locks_want < new_locks_want);  in __bch2_btree_path_downgrade()
685 	path->locks_want = new_locks_want;  in __bch2_btree_path_downgrade()
687 	while (path->nodes_locked &&  in __bch2_btree_path_downgrade()
688 	       (l = btree_path_highest_level_locked(path)) >= path->locks_want) {  in __bch2_btree_path_downgrade()
689 		if (l > path->level) {  in __bch2_btree_path_downgrade()
693 				six_lock_downgrade(&path->l[l].b->c.lock);  in __bch2_btree_path_downgrade()
712 	if (trans->restarted)  in bch2_trans_downgrade()
716 		if (path->ref)  in bch2_trans_downgrade()
738 		bch2_bpos_to_text(&buf, path->pos);  in bch2_trans_relock_fail()
739 		prt_printf(&buf, " l=%u seq=%u node seq=", f->l, path->l[f->l].lock_seq);  in bch2_trans_relock_fail()
740 		if (IS_ERR_OR_NULL(f->b)) {  in bch2_trans_relock_fail()
741 			prt_str(&buf, bch2_err_str(PTR_ERR(f->b)));  in bch2_trans_relock_fail()
743 			prt_printf(&buf, "%u", f->b->c.lock.seq);  in bch2_trans_relock_fail()
746 				bch2_btree_node_lock_counts(trans, NULL, &f->b->c, f->l);  in bch2_trans_relock_fail()
749 			c = six_lock_counts(&f->b->c.lock);  in bch2_trans_relock_fail()
757 	count_event(trans->c, trans_restart_relock);  in bch2_trans_relock_fail()
768 	if (unlikely(trans->restarted))  in __bch2_trans_relock()
769 		return -((int) trans->restarted);  in __bch2_trans_relock()
770 	if (unlikely(trans->locked))  in __bch2_trans_relock()
779 		if (path->should_be_locked &&  in __bch2_trans_relock()
828 				bch2_btree_node_unlock_write(trans, path, path->l[l].b);  in bch2_trans_unlock_write()
849 	 * there is no node at path->level, which generally means we were  in bch2_btree_path_verify_locks()
852 	BUG_ON(path->uptodate == BTREE_ITER_UPTODATE &&  in bch2_btree_path_verify_locks()
853 	       btree_path_node(path, path->level) &&  in bch2_btree_path_verify_locks()
854 	       !path->nodes_locked);  in bch2_btree_path_verify_locks()
856 	if (!path->nodes_locked)  in bch2_btree_path_verify_locks()
871 		       path->l[l].lock_seq != six_lock_seq(&path->l[l].b->c.lock));  in bch2_btree_path_verify_locks()
881 		if (path->nodes_locked)  in bch2_trans_locked()
888 	if (!trans->locked) {  in bch2_trans_verify_locks()