path: root/fs/bcachefs/btree_locking.c

// SPDX-License-Identifier: GPL-2.0

#include "bcachefs.h"
#include "btree_cache.h"
#include "btree_locking.h"
#include "btree_types.h"

static struct lock_class_key bch2_btree_node_lock_key;

void bch2_btree_lock_init(struct btree_bkey_cached_common *b,
			  enum six_lock_init_flags flags,
			  gfp_t gfp)
{
	__six_lock_init(&b->lock, "b->c.lock", &bch2_btree_node_lock_key, flags, gfp);
	lockdep_set_notrack_class(&b->lock);
}

/* Btree node locking: */

struct six_lock_count bch2_btree_node_lock_counts(struct btree_trans *trans,
						  struct btree_path *skip,
						  struct btree_bkey_cached_common *b,
						  unsigned level)
{
	struct btree_path *path;
	struct six_lock_count ret;
	unsigned i;

	memset(&ret, 0, sizeof(ret));

	if (IS_ERR_OR_NULL(b))
		return ret;

	trans_for_each_path(trans, path, i)
		if (path != skip && &path->l[level].b->c == b) {
			int t = btree_node_locked_type(path, level);

			if (t != BTREE_NODE_UNLOCKED)
				ret.n[t]++;
		}

	return ret;
}

/* unlock */

void bch2_btree_node_unlock_write(struct btree_trans *trans,
			struct btree_path *path, struct btree *b)
{
	bch2_btree_node_unlock_write_inlined(trans, path, b);
}

/* lock */

/*
 * @trans wants to lock @b with type @type
 */
struct trans_waiting_for_lock {
	struct btree_trans		*trans;
	struct btree_bkey_cached_common	*node_want;
	enum six_lock_type		lock_want;

	/* for iterating over held locks :*/
	u8				path_idx;
	u8				level;
	u64				lock_start_time;
};

struct lock_graph {
	struct trans_waiting_for_lock	g[8];
	unsigned			nr;
};

static noinline void print_cycle(struct printbuf *out, struct lock_graph *g)
{
	struct trans_waiting_for_lock *i;

	prt_printf(out, "Found lock cycle (%u entries):\n", g->nr);

	for (i = g->g; i < g->g + g->nr; i++) {
		struct task_struct *task = READ_ONCE(i->trans->locking_wait.task);
		if (!task)
			continue;

		bch2_btree_trans_to_text(out, i->trans);
		bch2_prt_task_backtrace(out, task, i == g->g ? 5 : 1, GFP_NOWAIT);
	}
}

static noinline void print_chain(struct printbuf *out, struct lock_graph *g)
{
	struct trans_waiting_for_lock *i;

	for (i = g->g; i != g->g + g->nr; i++) {
		struct task_struct *task = READ_ONCE(i->trans->locking_wait.task);
		if (i != g->g)
			prt_str(out, "<- ");
		prt_printf(out, "%u ", task ? task->pid : 0);
	}
	prt_newline(out);
}

static void lock_graph_up(struct lock_graph *g)
{
	closure_put(&g->g[--g->nr].trans->ref);
}

static noinline void lock_graph_pop_all(struct lock_graph *g)
{
	while (g->nr)
		lock_graph_up(g);
}

static noinline void lock_graph_pop_from(struct lock_graph *g, struct trans_waiting_for_lock *i)
{
	while (g->g + g->nr > i)
		lock_graph_up(g);
}

static void __lock_graph_down(struct lock_graph *g, struct btree_trans *trans)
{
	g->g[g->nr++] = (struct trans_waiting_for_lock) {
		.trans		= trans,
		.node_want	= trans->locking,
		.lock_want	= trans->locking_wait.lock_want,
	};
}

static void lock_graph_down(struct lock_graph *g, struct btree_trans *trans)
{
	closure_get(&trans->ref);
	__lock_graph_down(g, trans);
}

static bool lock_graph_remove_non_waiters(struct lock_graph *g,
					  struct trans_waiting_for_lock *from)
{
	struct trans_waiting_for_lock *i;

	if (from->trans->locking != from->node_want) {
		lock_graph_pop_from(g, from);
		return true;
	}

	for (i = from + 1; i < g->g + g->nr; i++)
		if (i->trans->locking != i->node_want ||
		    i->trans->locking_wait.start_time != i[-1].lock_start_time) {
			lock_graph_pop_from(g, i);
			return true;
		}

	return false;
}

static void trace_would_deadlock(struct lock_graph *g, struct btree_trans *trans)
{
	struct bch_fs *c = trans->c;

	count_event(c, trans_restart_would_deadlock);

	if (trace_trans_restart_would_deadlock_enabled()) {
		struct printbuf buf = PRINTBUF;

		buf.atomic++;
		print_cycle(&buf, g);

		trace_trans_restart_would_deadlock(trans, buf.buf);
		printbuf_exit(&buf);
	}
}

static int abort_lock(struct lock_graph *g, struct trans_waiting_for_lock *i)
{
	if (i == g->g) {
		trace_would_deadlock(g, i->trans);
		return btree_trans_restart_foreign_task(i->trans,
					BCH_ERR_transaction_restart_would_deadlock,
					_THIS_IP_);
	} else {
		i->trans->lock_must_abort = true;
		wake_up_process(i->trans->locking_wait.task);
		return 0;
	}
}

static int btree_trans_abort_preference(struct btree_trans *trans)
{
	if (trans->lock_may_not_fail)
		return 0;
	if (trans->locking_wait.lock_want == SIX_LOCK_write)
		return 1;
	if (!trans->in_traverse_all)
		retu