path: root/fs/bcachefs/btree_types.h

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

#include <linux/list.h>
#include <linux/rhashtable.h>

#include "bbpos_types.h"
#include "btree_key_cache_types.h"
#include "buckets_types.h"
#include "darray.h"
#include "errcode.h"
#include "journal_types.h"
#include "replicas_types.h"
#include "six.h"

struct open_bucket;
struct btree_update;
struct btree_trans;

#define MAX_BSETS		3U

struct btree_nr_keys {

	/*
	 * Amount of live metadata (i.e. size of node after a compaction) in
	 * units of u64s
	 */
	u16			live_u64s;
	u16			bset_u64s[MAX_BSETS];

	/* live keys only: */
	u16			packed_keys;
	u16			unpacked_keys;
};

struct bset_tree {
	/*
	 * We construct a binary tree in an array as if the array
	 * started at 1, so that things line up on the same cachelines
	 * better: see comments in bset.c at cacheline_to_bkey() for
	 * details
	 */

	/* size of the binary tree and prev array */
	u16			size;

	/* function of size - precalculated for to_inorder() */
	u16			extra;

	u16			data_offset;
	u16			aux_data_offset;
	u16			end_offset;
};

struct btree_write {
	struct journal_entry_pin	journal;
};

struct btree_alloc {
	struct open_buckets	ob;
	__BKEY_PADDED(k, BKEY_BTREE_PTR_VAL_U64s_MAX);
};

struct btree_bkey_cached_common {
	struct six_lock		lock;
	u8			level;
	u8			btree_id;
	bool			cached;
};

struct btree {
	struct btree_bkey_cached_common c;

	struct rhash_head	hash;
	u64			hash_val;

	unsigned long		flags;
	u16			written;
	u8			nsets;
	u8			nr_key_bits;
	u16			version_ondisk;

	struct bkey_format	format;

	struct btree_node	*data;
	void			*aux_data;

	/*
	 * Sets of sorted keys - the real btree node - plus a binary search tree
	 *
	 * set[0] is special; set[0]->tree, set[0]->prev and set[0]->data point
	 * to the memory we have allocated for this btree node. Additionally,
	 * set[0]->data points to the entire btree node as it exists on disk.
	 */
	struct bset_tree	set[MAX_BSETS];

	struct btree_nr_keys	nr;
	u16			sib_u64s[2];
	u16			whiteout_u64s;
	u8			byte_order;
	u8			unpack_fn_len;

	struct btree_write	writes[2];

	/* Key/pointer for this btree node */
	__BKEY_PADDED(key, BKEY_BTREE_PTR_VAL_U64s_MAX);

	/*
	 * XXX: add a delete sequence number, so when bch2_btree_node_relock()
	 * fails because the lock sequence number has changed - i.e. the
	 * contents were modified - we can still relock the node if it's still
	 * the one we want, without redoing the traversal
	 */

	/*
	 * For asynchronous splits/interior node updates:
	 * When we do a split, we allocate new child nodes and update the parent
	 * node to point to them: we update the parent in memory immediately,
	 * but then we must wait until the children have been written out before
	 * the update to the parent can be written - this is a list of the
	 * btree_updates that are blocking this node from being
	 * written:
	 */
	struct list_head	write_blocked;

	/*
	 * Also for asynchronous splits/interior node updates:
	 * If a btree node isn't reachable yet, we don't want to kick off
	 * another write - because that write also won't yet be reachable and
	 * marking it as completed before it's reachable would be incorrect:
	 */
	unsigned long		will_make_reachable;

	struct open_buckets	ob;

	/* lru list */
	struct list_head	list;
};

#define BCH_BTREE_CACHE_NOT_FREED_REASONS()	\
	x(lock_intent)				\
	x(lock_write)				\
	x(dirty)				\
	x(read_in_flight)			\
	x(write_in_flight)			\
	x(noevict)				\
	x(write_blocked)			\
	x(will_make_reachable)			\
	x(access_bit)

enum bch_btree_cache_not_freed_reasons {
#define x(n) BCH_BTREE_CACHE_NOT_FREED_##n,
	BCH_BTREE_CACHE_NOT_FREED_REASONS()
#undef x
	BCH_BTREE_CACHE_NOT_FREED_REASONS_NR,
};

struct btree_cache_list {
	unsigned		idx;
	struct shrinker		*shrink;
	struct list_head	list;
	size_t			nr;
};

struct btree_cache {
	struct rhashtable	table;
	bool			table_init_done;
	/*
	 * We never free a struct btree, except on shutdown - we just put it on
	 * the btree_cache_freed list and reuse it later. This simplifies the
	 * code, and it doesn't cost us much memory as the memory usage is
	 * dominated by buffers that hold the actual btree node data and those
	 * can be freed - and the number of struct btrees allocated is
	 * effectively bounded.
	 *
	 * btree_cache_freeable effectively is a small cache - we use it because
	 * high order page allocations can be rather expensive, and it's quite
	 * common to delete and allocate btree nodes in quick succession. It
	 * should never grow past ~2-3 nodes in practice.
	 */
	struct mutex		lock;
	struct list_head	freeable;
	struct list_head	freed_pcpu;
	struct list_head	freed_nonpcpu;
	struct btree_cache_list	live[2];

	size_t			nr_freeable;
	size_t			nr_reserve;
	size_t			nr_by_btree[BTREE_ID_NR];
	atomic_long_t		nr_dirty;

	/* shrinker stats */
	size_t			nr_freed;
	u64			not_freed[BCH_BTREE_CACHE_NOT_FREED_REASONS_NR];

	/*
	 * If we need to allocate memory for a new btree node and that
	 * allocation fails, we can cannibalize another node in the btree cache
	 * to satisfy the allocation - lock to guarantee only one thread does
	 * this at a time:
	 */
	struct task_struct	*alloc_lock;
	struct closure_waitlist	alloc_wait;

	struct bbpos		pinned_nodes_start;
	struct bbpos		pinned_nodes_end;
	/* btree id mask: 0 for leaves, 1 for interior */
	u64			pinned_nodes_mask[2];
};

struct btree_node_iter {
	struct btree_node_iter_set {
		u16	k, end;
	} data[MAX_BSETS];
};

#define BTREE_ITER_FLAGS()			\
	x(slots)				\
	x(intent)				\
	x(prefetch)				\
	x(is_extents)				\
	x(not_extents)				\
	x(cached)				\
	x(with_key_cache)			\
	x(with_updates)				\
	x(with_journal)				\
	x(snapshot_field)			\
	x(all_snapshots)			\
	x(filter_snapshots)			\
	x(nopreserve)				\
	x(cached_nofill)			\
	x(key_cache_fill)			\

#define STR_HASH_FLAGS()			\
	x(must_create)				\
	x(must_replace)

#define BTREE_UPDATE_FLAGS()			\
	x(internal_snapshot_node)		\
	x(nojournal)				\
	x(key_cache_reclaim)


/*
 * BTREE_TRIGGER_norun - don't run triggers at all
 *
 * BTREE_TRIGGER_transactional - we're running transactional triggers as part of
 * a transaction commit: triggers may generate new updates
 *
 * BTREE_TRIGGER_atomic - we're running atomic triggers during a transaction
 * commit: we have our journal reservation, we're holding btree node write
 * locks, and we know the transaction is going to commit (returning an error
 * here is a fatal error, causing us to go emergency read-only)
 *
 * BTREE_TRIGGER_gc - we're in gc/fsck: running triggers to recalculate e.g. disk usage
 *
 * BTREE_TRIGGER_insert - @new is entering the btree
 * BTREE_TRIGGER_overwrite - @old is leaving the btree
 *
 * BTREE_TRIGGER_bucket_invalidate - signal from bucket invalidate path to alloc
 * trigger
 */
#define BTREE_TRIGGER_FLAGS()			\
	x(norun)				\
	x(transactional)			\
	x(atomic)				\
	x(check_repair)				\
	x(gc)					\
	x(insert)				\
	x(overwrite)				\
	x(is_root)				\
	x(bucket_invalidate)

enum {
#define x(n) BTREE_ITER_FLAG_BIT_##n,
	BTREE_ITER_FLAGS()
	STR_HASH_FLAGS()
	BTREE_UPDATE_FLAGS()
	BTREE_TRIGGER_FLAGS()
#undef x
};

/* iter flags must fit in a u16: */
//BUILD_BUG_ON(BTREE_ITER_FLAG_BIT_key_cache_fill > 15);

enum btree_iter_update_trigger_flags {
#define x(n) BTREE_ITER_##n	= 1U << BTREE_ITER_FLAG_BIT_##n,
	BTREE_ITER_FLAGS()
#undef x
#define x(n) STR_HASH_##n	= 1U << BTREE_ITER_FLAG_BIT_##n,
	STR_HASH_FLAGS()
#undef x
#define x(n) BTREE_UPDATE_##n	= 1U << BTREE_ITER_FLAG_BIT_##n,
	BTREE_UPDATE_FLAGS()
#undef x
#define x(n) BTREE_TRIGGER_##n	= 1U << BTREE_ITER_FLAG_BIT_##n,
	BTREE_TRIGGER_FLAGS()
#undef x
};

enum btree_path_uptodate {
	BTREE_ITER_UPTODATE		= 0,
	BTREE_ITER_NEED_RELOCK		= 1,
	BTREE_ITER_NEED_TRAVERSE	= 2,
};

#if defined(CONFIG_BCACHEFS_LOCK_TIME_STATS) || defined(CONFIG_BCACHEFS_DEBUG)
#define TRACK_PATH_ALLOCATED
#endif

typedef u16 btree_path_idx_t;

struct btree_path {
	btree_path_idx_t	sorted_idx;
	u8			ref;
	u8			intent_ref;

	/* btree_iter_copy starts here: */
	struct bpos		pos;

	enum btree_id		btree_id:5;
	bool			cached:1;
	bool			preserve:1;
	enum btree_path_uptodate uptodate:2;
	/*
	 * When true, failing to relock this path will cause the transaction to
	 * restart:
	 */
	bool			should_be_locked:1;
	unsigned		level:3,
				locks_want:3;
	u8			nodes_locked;

	struct btree_path_level {
		struct btree	*b;
		struct btree_node_iter iter;
		u32		lock_seq;
#ifdef CONFIG_BCACHEFS_LOCK_TIME_STATS
		u64             lock_taken_time;
#endif
	}			l[BTREE_MAX_DEPTH];
#ifdef TRACK_PATH_ALLOCATED
	unsigned long		ip_allocated;
#endif
};

static inline struct btree_path_level *path_l(struct btree_path *path)
{
	return path->l + path->level;
}

static inline unsigned long btree_path_ip_allocated(struct btree_path *path)
{
#ifdef TRACK_PATH_ALLOCATED
	return path->ip_allocated;
#else
	return _THIS_IP_;
#endif
}

/*
 * @pos			- iterator's current position
 * @level		- current btree depth
 * @locks_want		- btree level below which we start taking intent locks
 * @nodes_locked	- bitmask indicating which nodes in @nodes are locked
 * @nodes_intent_locked	- bitmask indicating which locks are intent locks
 */
struct btree_iter {
	struct btree_trans	*trans;
	btree_path_idx_t	path;
	btree_path_idx_t	update_path;
	btree_path_idx_t	key_cache_path;

	enum btree_id		btree_id:8;
	u8			min_depth;

	/* btree_iter_copy starts here: */
	u16			flags;

	/* When we're filtering by snapshot, the snapshot ID we're looking for: */
	unsigned		snapshot;

	struct bpos		pos;
	/*
	 * Current unpacked key - so that bch2_btree_iter_next()/
	 * bch2_btree_iter_next_slot() can correctly advance pos.
	 */
	struct bkey		k;

	/* BTREE_ITER_with_journal: */
	size_t			journal_idx;
#ifdef TRACK_PATH_ALLOCATED
	unsigned long		ip_allocated;
#endif
};

#define BKEY_CACHED_ACCESSED		0
#define BKEY_CACHED_DIRTY		1

struct bkey_cached {
	struct btree_bkey_cached_common c;

	unsigned long		flags;
	u16			u64s;
	struct bkey_cached_key	key;

	struct rhash_head	hash;

	struct journal_entry_pin journal