path: root/fs/bcachefs/btree_iter.h

/* SPDX-License-Identifier: GPL-2.0 */
#ifndef _BCACHEFS_BTREE_ITER_H
#define _BCACHEFS_BTREE_ITER_H

#include "bset.h"
#include "btree_types.h"
#include "trace.h"

void bch2_trans_updates_to_text(struct printbuf *, struct btree_trans *);
void bch2_btree_path_to_text(struct printbuf *, struct btree_trans *, btree_path_idx_t);
void bch2_trans_paths_to_text(struct printbuf *, struct btree_trans *);
void bch2_dump_trans_updates(struct btree_trans *);
void bch2_dump_trans_paths_updates(struct btree_trans *);

static inline int __bkey_err(const struct bkey *k)
{
	return PTR_ERR_OR_ZERO(k);
}

#define bkey_err(_k)	__bkey_err((_k).k)

static inline void __btree_path_get(struct btree_trans *trans, struct btree_path *path, bool intent)
{
	unsigned idx = path - trans->paths;

	EBUG_ON(!test_bit(idx, trans->paths_allocated));
	if (unlikely(path->ref == U8_MAX)) {
		bch2_dump_trans_paths_updates(trans);
		panic("path %u refcount overflow\n", idx);
	}

	path->ref++;
	path->intent_ref += intent;
	trace_btree_path_get_ll(trans, path);
}

static inline bool __btree_path_put(struct btree_trans *trans, struct btree_path *path, bool intent)
{
	EBUG_ON(!test_bit(path - trans->paths, trans->paths_allocated));
	EBUG_ON(!path->ref);
	EBUG_ON(!path->intent_ref && intent);

	trace_btree_path_put_ll(trans, path);
	path->intent_ref -= intent;
	return --path->ref == 0;
}

static inline void btree_path_set_dirty(struct btree_path *path,
					enum btree_path_uptodate u)
{
	path->uptodate = max_t(unsigned, path->uptodate, u);
}

static inline struct btree *btree_path_node(struct btree_path *path,
					    unsigned level)
{
	return level < BTREE_MAX_DEPTH ? path->l[level].b : NULL;
}

static inline bool btree_node_lock_seq_matches(const struct btree_path *path,
					const struct btree *b, unsigned level)
{
	return path->l[level].lock_seq == six_lock_seq(&b->c.lock);
}

static inline struct btree *btree_node_parent(struct btree_path *path,
					      struct btree *b)
{
	return btree_path_node(path, b->c.level + 1);
}

/* Iterate over paths within a transaction: */

void __bch2_btree_trans_sort_paths(struct btree_trans *);

static inline void btree_trans_sort_paths(struct btree_trans *trans)
{
	if (!IS_ENABLED(CONFIG_BCACHEFS_DEBUG) &&
	    trans->paths_sorted)
		return;
	__bch2_btree_trans_sort_paths(trans);
}

static inline unsigned long *trans_paths_nr(struct btree_path *paths)
{
	return &container_of(paths, struct btree_trans_paths, paths[0])->nr_paths;
}

static inline unsigned long *trans_paths_allocated(struct btree_path *paths)
{
	unsigned long *v = trans_paths_nr(paths);
	return v - BITS_TO_LONGS(*v);
}

#define trans_for_each_path_idx_from(_paths_allocated, _nr, _idx, _start)\
	for (_idx = _start;						\
	     (_idx = find_next_bit(_paths_allocated, _nr, _idx)) < _nr;	\
	     _idx++)

static inline struct btree_path *
__trans_next_path(struct btree_trans *trans, unsigned *idx)
{
	unsigned long *w = trans->paths_allocated + *idx / BITS_PER_LONG;
	/*
	 * Open coded find_next_bit(), because
	 *  - this is fast path, we can't afford the function call
	 *  - and we know that nr_paths is a multiple of BITS_PER_LONG,
	 */
	while (*idx < trans->nr_paths) {
		unsigned long v = *w >> (*idx & (BITS_PER_LONG - 1));
		if (v) {
			*idx += __ffs(v);
			return trans->paths + *idx;
		}

		*idx += BITS_PER_LONG;
		*idx &= ~(BITS_PER_LONG - 1);
		w++;
	}

	return NULL;
}

/*
 * This version is intended to be safe for use on a btree_trans that is owned by
 * another thread, for bch2_btree_trans_to_text();
 */
#define trans_for_each_path_from(_trans, _path, _idx, _start)		\
	for (_idx = _start;						\
	     (_path = __trans_next_path((_trans), &_idx));		\
	     _idx++)

#define trans_for_each_path(_trans, _path, _idx)			\
	trans_for_each_path_from(_trans, _path, _idx, 1)

static inline struct btree_path *next_btree_path(struct btree_trans *trans, struct btree_path *path)
{
	unsigned idx = path ? path->sorted_idx +