linux/fs/bcachefs/bset.c

// SPDX-License-Identifier: GPL-2.0
/*
 * Code for working with individual keys, and sorted sets of keys with in a
 * btree node
 *
 * Copyright 2012 Google, Inc.
 */

#include "bcachefs.h"
#include "btree_cache.h"
#include "bset.h"
#include "eytzinger.h"
#include "trace.h"
#include "util.h"

#include <asm/unaligned.h>
#include <linux/console.h>
#include <linux/random.h>
#include <linux/prefetch.h>

static inline void __bch2_btree_node_iter_advance(struct btree_node_iter *,
						  struct btree *);

static inline unsigned __btree_node_iter_used(struct btree_node_iter *iter)
{}

struct bset_tree *bch2_bkey_to_bset(struct btree *b, struct bkey_packed *k)
{}

/*
 * There are never duplicate live keys in the btree - but including keys that
 * have been flagged as deleted (and will be cleaned up later) we _will_ see
 * duplicates.
 *
 * Thus the sort order is: usual key comparison first, but for keys that compare
 * equal the deleted key(s) come first, and the (at most one) live version comes
 * last.
 *
 * The main reason for this is insertion: to handle overwrites, we first iterate
 * over keys that compare equal to our insert key, and then insert immediately
 * prior to the first key greater than the key we're inserting - our insert
 * position will be after all keys that compare equal to our insert key, which
 * by the time we actually do the insert will all be deleted.
 */

void bch2_dump_bset(struct bch_fs *c, struct btree *b,
		    struct bset *i, unsigned set)
{}

void bch2_dump_btree_node(struct bch_fs *c, struct btree *b)
{}

void bch2_dump_btree_node_iter(struct btree *b,
			      struct btree_node_iter *iter)
{}

struct btree_nr_keys bch2_btree_node_count_keys(struct btree *b)
{}

#ifdef CONFIG_BCACHEFS_DEBUG

void __bch2_verify_btree_nr_keys(struct btree *b)
{}

static void bch2_btree_node_iter_next_check(struct btree_node_iter *_iter,
					    struct btree *b)
{}

void bch2_btree_node_iter_verify(struct btree_node_iter *iter,
				 struct btree *b)
{}

void bch2_verify_insert_pos(struct btree *b, struct bkey_packed *where,
			    struct bkey_packed *insert, unsigned clobber_u64s)
{}

#else

static inline void bch2_btree_node_iter_next_check(struct btree_node_iter *iter,
						   struct btree *b) {}

#endif

/* Auxiliary search trees */

#define BFLOAT_FAILED_UNPACKED
#define BFLOAT_FAILED

struct bkey_float {};
#define BKEY_MANTISSA_BITS

static unsigned bkey_float_byte_offset(unsigned idx)
{}

struct ro_aux_tree {};

struct rw_aux_tree {};

static unsigned bset_aux_tree_buf_end(const struct bset_tree *t)
{}

static unsigned bset_aux_tree_buf_start(const struct btree *b,
					const struct bset_tree *t)
{}

static void *__aux_tree_base(const struct btree *b,
			     const struct bset_tree *t)
{}

static struct ro_aux_tree *ro_aux_tree_base(const struct btree *b,
					    const struct bset_tree *t)
{}

static u8 *ro_aux_tree_prev(const struct btree *b,
			    const struct bset_tree *t)
{}

static struct bkey_float *bkey_float(const struct btree *b,
				     const struct bset_tree *t,
				     unsigned idx)
{}

static void bset_aux_tree_verify(struct btree *b)
{}

void bch2_btree_keys_init(struct btree *b)
{}

/* Binary tree stuff for auxiliary search trees */

/*
 * Cacheline/offset <-> bkey pointer arithmetic:
 *
 * t->tree is a binary search tree in an array; each node corresponds to a key
 * in one cacheline in t->set (BSET_CACHELINE bytes).
 *
 * This means we don't have to store the full index of the key that a node in
 * the binary tree points to; eytzinger1_to_inorder() gives us the cacheline, and
 * then bkey_float->m gives us the offset within that cacheline, in units of 8
 * bytes.
 *
 * cacheline_to_bkey() and friends abstract out all the pointer arithmetic to
 * make this work.
 *
 * To construct the bfloat for an arbitrary key we need to know what the key
 * immediately preceding it is: we have to check if the two keys differ in the
 * bits we're going to store in bkey_float->mantissa. t->prev[j] stores the size
 * of the previous key so we can walk backwards to it from t->tree[j]'s key.
 */

static inline void *bset_cacheline(const struct btree *b,
				   const struct bset_tree *t,
				   unsigned cacheline)
{}

static struct bkey_packed *cacheline_to_bkey(const struct btree *b,
					     const struct bset_tree *t,
					     unsigned cacheline,
					     unsigned offset)
{}

static unsigned bkey_to_cacheline(const struct btree *b,
				  const struct bset_tree *t,
				  const struct bkey_packed *k)
{}

static ssize_t __bkey_to_cacheline_offset(const struct btree *b,
					  const struct bset_tree *t,
					  unsigned cacheline,
					  const struct bkey_packed *k)
{}

static unsigned bkey_to_cacheline_offset(const struct btree *b,
					 const struct bset_tree *t,
					 unsigned cacheline,
					 const struct bkey_packed *k)
{}

static inline struct bkey_packed *tree_to_bkey(const struct btree *b,
					       const struct bset_tree *t,
					       unsigned j)
{}

static struct bkey_packed *tree_to_prev_bkey(const struct btree *b,
					     const struct bset_tree *t,
					     unsigned j)
{}

static struct rw_aux_tree *rw_aux_tree(const struct btree *b,
				       const struct bset_tree *t)
{}

/*
 * For the write set - the one we're currently inserting keys into - we don't
 * maintain a full search tree, we just keep a simple lookup table in t->prev.
 */
static struct bkey_packed *rw_aux_to_bkey(const struct btree *b,
					  struct bset_tree *t,
					  unsigned j)
{}

static void rw_aux_tree_set(const struct btree *b, struct bset_tree *t,
			    unsigned j, struct bkey_packed *k)
{}

static void bch2_bset_verify_rw_aux_tree(struct btree *b,
					struct bset_tree *t)
{}

/* returns idx of first entry >= offset: */
static unsigned rw_aux_tree_bsearch(struct btree *b,
				    struct bset_tree *t,
				    unsigned offset)
{}

static inline unsigned bkey_mantissa(const struct bkey_packed *k,
				     const struct bkey_float *f,
				     unsigned idx)
{}

static __always_inline void make_bfloat(struct btree *b, struct bset_tree *t,
					unsigned j,
					struct bkey_packed *min_key,
					struct bkey_packed *max_key)
{}

/* bytes remaining - only valid for last bset: */
static unsigned __bset_tree_capacity(struct btree *b, const struct bset_tree *t)
{}

static unsigned bset_ro_tree_capacity(struct btree *b, const struct bset_tree *t)
{}

static unsigned bset_rw_tree_capacity(struct btree *b, const struct bset_tree *t)
{}

static noinline void __build_rw_aux_tree(struct btree *b, struct bset_tree *t)
{}

static noinline void __build_ro_aux_tree(struct btree *b, struct bset_tree *t)
{}

static void bset_alloc_tree(struct btree *b, struct bset_tree *t)
{}

void bch2_bset_build_aux_tree(struct btree *b, struct bset_tree *t,
			     bool writeable)
{}

void bch2_bset_init_first(struct btree *b, struct bset *i)
{}

void bch2_bset_init_next(struct btree *b, struct btree_node_entry *bne)
{}

/*
 * find _some_ key in the same bset as @k that precedes @k - not necessarily the
 * immediate predecessor:
 */
static struct bkey_packed *__bkey_prev(struct btree *b, struct bset_tree *t,
				       struct bkey_packed *k)
{}

struct bkey_packed *bch2_bkey_prev_filter(struct btree *b,
					  struct bset_tree *t,
					  struct bkey_packed *k,
					  unsigned min_key_type)
{}

/* Insert */

static void bch2_bset_fix_lookup_table(struct btree *b,
				       struct bset_tree *t,
				       struct bkey_packed *_where,
				       unsigned clobber_u64s,
				       unsigned new_u64s)
{}

void bch2_bset_insert(struct btree *b,
		      struct btree_node_iter *iter,
		      struct bkey_packed *where,
		      struct bkey_i *insert,
		      unsigned clobber_u64s)
{}

void bch2_bset_delete(struct btree *b,
		      struct bkey_packed *where,
		      unsigned clobber_u64s)
{}

/* Lookup */

__flatten
static struct bkey_packed *bset_search_write_set(const struct btree *b,
				struct bset_tree *t,
				struct bpos *search)
{}

static inline void prefetch_four_cachelines(void *p)
{}

static inline bool bkey_mantissa_bits_dropped(const struct btree *b,
					      const struct bkey_float *f,
					      unsigned idx)
{}

__flatten
static struct bkey_packed *bset_search_tree(const struct btree *b,
				const struct bset_tree *t,
				const struct bpos *search,
				const struct bkey_packed *packed_search)
{}

static __always_inline __flatten
struct bkey_packed *__bch2_bset_search(struct btree *b,
				struct bset_tree *t,
				struct bpos *search,
				const struct bkey_packed *lossy_packed_search)
{}

static __always_inline __flatten
struct bkey_packed *bch2_bset_search_linear(struct btree *b,
				struct bset_tree *t,
				struct bpos *search,
				struct bkey_packed *packed_search,
				const struct bkey_packed *lossy_packed_search,
				struct bkey_packed *m)
{}

/* Btree node iterator */

static inline void __bch2_btree_node_iter_push(struct btree_node_iter *iter,
			      struct btree *b,
			      const struct bkey_packed *k,
			      const struct bkey_packed *end)
{}

void bch2_btree_node_iter_push(struct btree_node_iter *iter,
			       struct btree *b,
			       const struct bkey_packed *k,
			       const struct bkey_packed *end)
{}

noinline __flatten __cold
static void btree_node_iter_init_pack_failed(struct btree_node_iter *iter,
			      struct btree *b, struct bpos *search)
{}

/**
 * bch2_btree_node_iter_init - initialize a btree node iterator, starting from a
 * given position
 *
 * @iter:	iterator to initialize
 * @b:		btree node to search
 * @search:	search key
 *
 * Main entry point to the lookup code for individual btree nodes:
 *
 * NOTE:
 *
 * When you don't filter out deleted keys, btree nodes _do_ contain duplicate
 * keys. This doesn't matter for most code, but it does matter for lookups.
 *
 * Some adjacent keys with a string of equal keys:
 *	i j k k k k l m
 *
 * If you search for k, the lookup code isn't guaranteed to return you any
 * specific k. The lookup code is conceptually doing a binary search and
 * iterating backwards is very expensive so if the pivot happens to land at the
 * last k that's what you'll get.
 *
 * This works out ok, but it's something to be aware of:
 *
 *  - For non extents, we guarantee that the live key comes last - see
 *    btree_node_iter_cmp(), keys_out_of_order(). So the duplicates you don't
 *    see will only be deleted keys you don't care about.
 *
 *  - For extents, deleted keys sort last (see the comment at the top of this
 *    file). But when you're searching for extents, you actually want the first
 *    key strictly greater than your search key - an extent that compares equal
 *    to the search key is going to have 0 sectors after the search key.
 *
 *    But this does mean that we can't just search for
 *    bpos_successor(start_of_range) to get the first extent that overlaps with
 *    the range we want - if we're unlucky and there's an extent that ends
 *    exactly where we searched, then there could be a deleted key at the same
 *    position and we'd get that when we search instead of the preceding extent
 *    we needed.
 *
 *    So we've got to search for start_of_range, then after the lookup iterate
 *    past any extents that compare equal to the position we searched for.
 */
__flatten
void bch2_btree_node_iter_init(struct btree_node_iter *iter,
			       struct btree *b, struct bpos *search)
{}

void bch2_btree_node_iter_init_from_start(struct btree_node_iter *iter,
					  struct btree *b)
{}

struct bkey_packed *bch2_btree_node_iter_bset_pos(struct btree_node_iter *iter,
						  struct btree *b,
						  struct bset_tree *t)
{}

static inline bool btree_node_iter_sort_two(struct btree_node_iter *iter,
					    struct btree *b,
					    unsigned first)
{}

void bch2_btree_node_iter_sort(struct btree_node_iter *iter,
			       struct btree *b)
{}

void bch2_btree_node_iter_set_drop(struct btree_node_iter *iter,
				   struct btree_node_iter_set *set)
{}

static inline void __bch2_btree_node_iter_advance(struct btree_node_iter *iter,
						  struct btree *b)
{}

void bch2_btree_node_iter_advance(struct btree_node_iter *iter,
				  struct btree *b)
{}

/*
 * Expensive:
 */
struct bkey_packed *bch2_btree_node_iter_prev_all(struct btree_node_iter *iter,
						  struct btree *b)
{}

struct bkey_packed *bch2_btree_node_iter_prev(struct btree_node_iter *iter,
					      struct btree *b)
{}

struct bkey_s_c bch2_btree_node_iter_peek_unpack(struct btree_node_iter *iter,
						 struct btree *b,
						 struct bkey *u)
{}

/* Mergesort */

void bch2_btree_keys_stats(const struct btree *b, struct bset_stats *stats)
{}

void bch2_bfloat_to_text(struct printbuf *out, struct btree *b,
			 struct bkey_packed *k)
{}