linux/fs/bcachefs/btree_iter.c

// SPDX-License-Identifier: GPL-2.0

#include "bcachefs.h"
#include "bkey_methods.h"
#include "bkey_buf.h"
#include "btree_cache.h"
#include "btree_iter.h"
#include "btree_journal_iter.h"
#include "btree_key_cache.h"
#include "btree_locking.h"
#include "btree_update.h"
#include "debug.h"
#include "error.h"
#include "extents.h"
#include "journal.h"
#include "journal_io.h"
#include "replicas.h"
#include "snapshot.h"
#include "trace.h"

#include <linux/random.h>
#include <linux/prefetch.h>

static inline void btree_path_list_remove(struct btree_trans *, struct btree_path *);
static inline void btree_path_list_add(struct btree_trans *,
			btree_path_idx_t, btree_path_idx_t);

static inline unsigned long btree_iter_ip_allocated(struct btree_iter *iter)
{ … }

static btree_path_idx_t btree_path_alloc(struct btree_trans *, btree_path_idx_t);
static void bch2_trans_srcu_lock(struct btree_trans *);

static inline int __btree_path_cmp(const struct btree_path *l,
				   enum btree_id	r_btree_id,
				   bool			r_cached,
				   struct bpos		r_pos,
				   unsigned		r_level)
{ … }

static inline int btree_path_cmp(const struct btree_path *l,
				 const struct btree_path *r)
{ … }

static inline struct bpos bkey_successor(struct btree_iter *iter, struct bpos p)
{ … }

static inline struct bpos bkey_predecessor(struct btree_iter *iter, struct bpos p)
{ … }

static inline struct bpos btree_iter_search_key(struct btree_iter *iter)
{ … }

static inline bool btree_path_pos_before_node(struct btree_path *path,
					      struct btree *b)
{ … }

static inline bool btree_path_pos_after_node(struct btree_path *path,
					     struct btree *b)
{ … }

static inline bool btree_path_pos_in_node(struct btree_path *path,
					  struct btree *b)
{ … }

/* Btree iterator: */

#ifdef CONFIG_BCACHEFS_DEBUG

static void bch2_btree_path_verify_cached(struct btree_trans *trans,
					  struct btree_path *path)
{ … }

static void bch2_btree_path_verify_level(struct btree_trans *trans,
				struct btree_path *path, unsigned level)
{ … }

static void bch2_btree_path_verify(struct btree_trans *trans,
				   struct btree_path *path)
{ … }

void bch2_trans_verify_paths(struct btree_trans *trans)
{ … }

static void bch2_btree_iter_verify(struct btree_iter *iter)
{ … }

static void bch2_btree_iter_verify_entry_exit(struct btree_iter *iter)
{ … }

static int bch2_btree_iter_verify_ret(struct btree_iter *iter, struct bkey_s_c k)
{ … }

void bch2_assert_pos_locked(struct btree_trans *trans, enum btree_id id,
			    struct bpos pos)
{ … }

#else

static inline void bch2_btree_path_verify_level(struct btree_trans *trans,
						struct btree_path *path, unsigned l) {}
static inline void bch2_btree_path_verify(struct btree_trans *trans,
					  struct btree_path *path) {}
static inline void bch2_btree_iter_verify(struct btree_iter *iter) {}
static inline void bch2_btree_iter_verify_entry_exit(struct btree_iter *iter) {}
static inline int bch2_btree_iter_verify_ret(struct btree_iter *iter, struct bkey_s_c k) { return 0; }

#endif

/* Btree path: fixups after btree updates */

static void btree_node_iter_set_set_pos(struct btree_node_iter *iter,
					struct btree *b,
					struct bset_tree *t,
					struct bkey_packed *k)
{ … }

static void __bch2_btree_path_fix_key_modified(struct btree_path *path,
					       struct btree *b,
					       struct bkey_packed *where)
{ … }

void bch2_btree_path_fix_key_modified(struct btree_trans *trans,
				      struct btree *b,
				      struct bkey_packed *where)
{ … }

static void __bch2_btree_node_iter_fix(struct btree_path *path,
				       struct btree *b,
				       struct btree_node_iter *node_iter,
				       struct bset_tree *t,
				       struct bkey_packed *where,
				       unsigned clobber_u64s,
				       unsigned new_u64s)
{ … }

void bch2_btree_node_iter_fix(struct btree_trans *trans,
			      struct btree_path *path,
			      struct btree *b,
			      struct btree_node_iter *node_iter,
			      struct bkey_packed *where,
			      unsigned clobber_u64s,
			      unsigned new_u64s)
{ … }

/* Btree path level: pointer to a particular btree node and node iter */

static inline struct bkey_s_c __btree_iter_unpack(struct bch_fs *c,
						  struct btree_path_level *l,
						  struct bkey *u,
						  struct bkey_packed *k)
{ … }

static inline struct bkey_s_c btree_path_level_peek_all(struct bch_fs *c,
							struct btree_path_level *l,
							struct bkey *u)
{ … }

static inline struct bkey_s_c btree_path_level_peek(struct btree_trans *trans,
						    struct btree_path *path,
						    struct btree_path_level *l,
						    struct bkey *u)
{ … }

static inline struct bkey_s_c btree_path_level_prev(struct btree_trans *trans,
						    struct btree_path *path,
						    struct btree_path_level *l,
						    struct bkey *u)
{ … }

static inline bool btree_path_advance_to_pos(struct btree_path *path,
					     struct btree_path_level *l,
					     int max_advance)
{ … }

static inline void __btree_path_level_init(struct btree_path *path,
					   unsigned level)
{ … }

void bch2_btree_path_level_init(struct btree_trans *trans,
				struct btree_path *path,
				struct btree *b)
{ … }

/* Btree path: fixups after btree node updates: */

static void bch2_trans_revalidate_updates_in_node(struct btree_trans *trans, struct btree *b)
{ … }

/*
 * A btree node is being replaced - update the iterator to point to the new
 * node:
 */
void bch2_trans_node_add(struct btree_trans *trans,
			 struct btree_path *path,
			 struct btree *b)
{ … }

/*
 * A btree node has been modified in such a way as to invalidate iterators - fix
 * them:
 */
void bch2_trans_node_reinit_iter(struct btree_trans *trans, struct btree *b)
{ … }

/* Btree path: traverse, set_pos: */

static inline int btree_path_lock_root(struct btree_trans *trans,
				       struct btree_path *path,
				       unsigned depth_want,
				       unsigned long trace_ip)
{ … }

noinline
static int btree_path_prefetch(struct btree_trans *trans, struct btree_path *path)
{ … }

static int btree_path_prefetch_j(struct btree_trans *trans, struct btree_path *path,
				 struct btree_and_journal_iter *jiter)
{ … }

static noinline void btree_node_mem_ptr_set(struct btree_trans *trans,
					    struct btree_path *path,
					    unsigned plevel, struct btree *b)
{ … }

static noinline int btree_node_iter_and_journal_peek(struct btree_trans *trans,
						     struct btree_path *path,
						     unsigned flags,
						     struct bkey_buf *out)
{ … }

static __always_inline int btree_path_down(struct btree_trans *trans,
					   struct btree_path *path,
					   unsigned flags,
					   unsigned long trace_ip)
{ … }

static int bch2_btree_path_traverse_all(struct btree_trans *trans)
{ … }

static inline bool btree_path_check_pos_in_node(struct btree_path *path,
						unsigned l, int check_pos)
{ … }

static inline bool btree_path_good_node(struct btree_trans *trans,
					struct btree_path *path,
					unsigned l, int check_pos)
{ … }

static void btree_path_set_level_down(struct btree_trans *trans,
				      struct btree_path *path,
				      unsigned new_level)
{ … }

static noinline unsigned __btree_path_up_until_good_node(struct btree_trans *trans,
							 struct btree_path *path,
							 int check_pos)
{ … }

static inline unsigned btree_path_up_until_good_node(struct btree_trans *trans,
						     struct btree_path *path,
						     int check_pos)
{ … }

/*
 * This is the main state machine for walking down the btree - walks down to a
 * specified depth
 *
 * Returns 0 on success, -EIO on error (error reading in a btree node).
 *
 * On error, caller (peek_node()/peek_key()) must return NULL; the error is
 * stashed in the iterator and returned from bch2_trans_exit().
 */
int bch2_btree_path_traverse_one(struct btree_trans *trans,
				 btree_path_idx_t path_idx,
				 unsigned flags,
				 unsigned long trace_ip)
{ … }

static inline void btree_path_copy(struct btree_trans *trans, struct btree_path *dst,
			    struct btree_path *src)
{ … }

static btree_path_idx_t btree_path_clone(struct btree_trans *trans, btree_path_idx_t src,
					 bool intent, unsigned long ip)
{ … }

__flatten
btree_path_idx_t __bch2_btree_path_make_mut(struct btree_trans *trans,
			btree_path_idx_t path, bool intent, unsigned long ip)
{ … }

btree_path_idx_t __must_check
__bch2_btree_path_set_pos(struct btree_trans *trans,
			  btree_path_idx_t path_idx, struct bpos new_pos,
			  bool intent, unsigned long ip)
{ … }

/* Btree path: main interface: */

static struct btree_path *have_path_at_pos(struct btree_trans *trans, struct btree_path *path)
{ … }

static struct btree_path *have_node_at_pos(struct btree_trans *trans, struct btree_path *path)
{ … }

static inline void __bch2_path_free(struct btree_trans *trans, btree_path_idx_t path)
{ … }

static bool bch2_btree_path_can_relock(struct btree_trans *trans, struct btree_path *path)
{ … }

void bch2_path_put(struct btree_trans *trans, btree_path_idx_t path_idx, bool intent)
{ … }

static void bch2_path_put_nokeep(struct btree_trans *trans, btree_path_idx_t path,
				 bool intent)
{ … }

void __noreturn bch2_trans_restart_error(struct btree_trans *trans, u32 restart_count)
{ … }

void __noreturn bch2_trans_in_restart_error(struct btree_trans *trans)
{ … }

void __noreturn bch2_trans_unlocked_error(struct btree_trans *trans)
{ … }

noinline __cold
void bch2_trans_updates_to_text(struct printbuf *buf, struct btree_trans *trans)
{ … }

noinline __cold
void bch2_dump_trans_updates(struct btree_trans *trans)
{ … }

static void bch2_btree_path_to_text_short(struct printbuf *out, struct btree_trans *trans, btree_path_idx_t path_idx)
{ … }

static const char *btree_node_locked_str(enum btree_node_locked_type t)
{ … }

void bch2_btree_path_to_text(struct printbuf *out, struct btree_trans *trans, btree_path_idx_t path_idx)
{ … }

static noinline __cold
void __bch2_trans_paths_to_text(struct printbuf *out, struct btree_trans *trans,
				bool nosort)
{ … }

noinline __cold
void bch2_trans_paths_to_text(struct printbuf *out, struct btree_trans *trans)
{ … }

static noinline __cold
void __bch2_dump_trans_paths_updates(struct btree_trans *trans, bool nosort)
{ … }

noinline __cold
void bch2_dump_trans_paths_updates(struct btree_trans *trans)
{ … }

noinline __cold
static void bch2_trans_update_max_paths(struct btree_trans *trans)
{ … }

noinline __cold
int __bch2_btree_trans_too_many_iters(struct btree_trans *trans)
{ … }

static noinline void btree_path_overflow(struct btree_trans *trans)
{ … }

static noinline void btree_paths_realloc(struct btree_trans *trans)
{ … }

static inline btree_path_idx_t btree_path_alloc(struct btree_trans *trans,
						btree_path_idx_t pos)
{ … }

btree_path_idx_t bch2_path_get(struct btree_trans *trans,
			     enum btree_id btree_id, struct bpos pos,
			     unsigned locks_want, unsigned level,
			     unsigned flags, unsigned long ip)
{ … }

btree_path_idx_t bch2_path_get_unlocked_mut(struct btree_trans *trans,
					    enum btree_id btree_id,
					    unsigned level,
					    struct bpos pos)
{ … }

struct bkey_s_c bch2_btree_path_peek_slot(struct btree_path *path, struct bkey *u)
{ … }


void bch2_set_btree_iter_dontneed(struct btree_iter *iter)
{ … }
/* Btree iterators: */

int __must_check
__bch2_btree_iter_traverse(struct btree_iter *iter)
{ … }

int __must_check
bch2_btree_iter_traverse(struct btree_iter *iter)
{ … }

/* Iterate across nodes (leaf and interior nodes) */

struct btree *bch2_btree_iter_peek_node(struct btree_iter *iter)
{ … }

struct btree *bch2_btree_iter_peek_node_and_restart(struct btree_iter *iter)
{ … }

struct btree *bch2_btree_iter_next_node(struct btree_iter *iter)
{ … }

/* Iterate across keys (in leaf nodes only) */

inline bool bch2_btree_iter_advance(struct btree_iter *iter)
{ … }

inline bool bch2_btree_iter_rewind(struct btree_iter *iter)
{ … }

static noinline
void bch2_btree_trans_peek_prev_updates(struct btree_trans *trans, struct btree_iter *iter,
					struct bkey_s_c *k)
{ … }

static noinline
void bch2_btree_trans_peek_updates(struct btree_trans *trans, struct btree_iter *iter,
				   struct bkey_s_c *k)
{ … }

static noinline
void bch2_btree_trans_peek_slot_updates(struct btree_trans *trans, struct btree_iter *iter,
					struct bkey_s_c *k)
{ … }

static struct bkey_i *bch2_btree_journal_peek(struct btree_trans *trans,
					      struct btree_iter *iter,
					      struct bpos end_pos)
{ … }

static noinline
struct bkey_s_c btree_trans_peek_slot_journal(struct btree_trans *trans,
					      struct btree_iter *iter)
{ … }

static noinline
struct bkey_s_c btree_trans_peek_journal(struct btree_trans *trans,
					 struct btree_iter *iter,
					 struct bkey_s_c k)
{ … }

/*
 * Checks btree key cache for key at iter->pos and returns it if present, or
 * bkey_s_c_null:
 */
static noinline
struct bkey_s_c btree_trans_peek_key_cache(struct btree_iter *iter, struct bpos pos)
{ … }

static struct bkey_s_c __bch2_btree_iter_peek(struct btree_iter *iter, struct bpos search_key)
{ … }

/**
 * bch2_btree_iter_peek_upto() - returns first key greater than or equal to
 * iterator's current position
 * @iter:	iterator to peek from
 * @end:	search limit: returns keys less than or equal to @end
 *
 * Returns:	key if found, or an error extractable with bkey_err().
 */
struct bkey_s_c bch2_btree_iter_peek_upto(struct btree_iter *iter, struct bpos end)
{ … }

/**
 * bch2_btree_iter_next() - returns first key greater than iterator's current
 * position
 * @iter:	iterator to peek from
 *
 * Returns:	key if found, or an error extractable with bkey_err().
 */
struct bkey_s_c bch2_btree_iter_next(struct btree_iter *iter)
{ … }

/**
 * bch2_btree_iter_peek_prev() - returns first key less than or equal to
 * iterator's current position
 * @iter:	iterator to peek from
 *
 * Returns:	key if found, or an error extractable with bkey_err().
 */
struct bkey_s_c bch2_btree_iter_peek_prev(struct btree_iter *iter)
{ … }

/**
 * bch2_btree_iter_prev() - returns first key less than iterator's current
 * position
 * @iter:	iterator to peek from
 *
 * Returns:	key if found, or an error extractable with bkey_err().
 */
struct bkey_s_c bch2_btree_iter_prev(struct btree_iter *iter)
{ … }

struct bkey_s_c bch2_btree_iter_peek_slot(struct btree_iter *iter)
{ … }

struct bkey_s_c bch2_btree_iter_next_slot(struct btree_iter *iter)
{ … }

struct bkey_s_c bch2_btree_iter_prev_slot(struct btree_iter *iter)
{ … }

struct bkey_s_c bch2_btree_iter_peek_and_restart_outlined(struct btree_iter *iter)
{ … }

/* new transactional stuff: */

#ifdef CONFIG_BCACHEFS_DEBUG
static void btree_trans_verify_sorted_refs(struct btree_trans *trans)
{ … }

static void btree_trans_verify_sorted(struct btree_trans *trans)
{ … }
#else
static inline void btree_trans_verify_sorted_refs(struct btree_trans *trans) {}
static inline void btree_trans_verify_sorted(struct btree_trans *trans) {}
#endif

void __bch2_btree_trans_sort_paths(struct btree_trans *trans)
{ … }

static inline void btree_path_list_remove(struct btree_trans *trans,
					  struct btree_path *path)
{ … }

static inline void btree_path_list_add(struct btree_trans *trans,
				       btree_path_idx_t pos,
				       btree_path_idx_t path_idx)
{ … }

void bch2_trans_iter_exit(struct btree_trans *trans, struct btree_iter *iter)
{ … }

void bch2_trans_iter_init_outlined(struct btree_trans *trans,
			  struct btree_iter *iter,
			  enum btree_id btree_id, struct bpos pos,
			  unsigned flags)
{ … }

void bch2_trans_node_iter_init(struct btree_trans *trans,
			       struct btree_iter *iter,
			       enum btree_id btree_id,
			       struct bpos pos,
			       unsigned locks_want,
			       unsigned depth,
			       unsigned flags)
{ … }

void bch2_trans_copy_iter(struct btree_iter *dst, struct btree_iter *src)
{ … }

void *__bch2_trans_kmalloc(struct btree_trans *trans, size_t size)
{ … }

static inline void check_srcu_held_too_long(struct btree_trans *trans)
{ … }

void bch2_trans_srcu_unlock(struct btree_trans *trans)
{ … }

static void bch2_trans_srcu_lock(struct btree_trans *trans)
{ … }

/**
 * bch2_trans_begin() - reset a transaction after a interrupted attempt
 * @trans: transaction to reset
 *
 * Returns:	current restart counter, to be used with trans_was_restarted()
 *
 * While iterating over nodes or updating nodes a attempt to lock a btree node
 * may return BCH_ERR_transaction_restart when the trylock fails. When this
 * occurs bch2_trans_begin() should be called and the transaction retried.
 */
u32 bch2_trans_begin(struct btree_trans *trans)
{ … }

const char *bch2_btree_transaction_fns[BCH_TRANSACTIONS_NR] = …;

unsigned bch2_trans_get_fn_idx(const char *fn)
{ … }

struct btree_trans *__bch2_trans_get(struct bch_fs *c, unsigned fn_idx)
	__acquires(&c->btree_trans_barrier)
{ … }

static void check_btree_paths_leaked(struct btree_trans *trans)
{ … }

void bch2_trans_put(struct btree_trans *trans)
	__releases(&c->btree_trans_barrier)
{ … }

bool bch2_current_has_btree_trans(struct bch_fs *c)
{ … }

static void __maybe_unused
bch2_btree_bkey_cached_common_to_text(struct printbuf *out,
				      struct btree_bkey_cached_common *b)
{ … }

void bch2_btree_trans_to_text(struct printbuf *out, struct btree_trans *trans)
{ … }

void bch2_fs_btree_iter_exit(struct bch_fs *c)
{ … }

void bch2_fs_btree_iter_init_early(struct bch_fs *c)
{ … }

int bch2_fs_btree_iter_init(struct bch_fs *c)
{ … }