#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)
{ … }
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
#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)
{ … }
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)
{ … }
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)
{ … }
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)
{ … }
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)
{ … }
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)
{ … }
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)
{ … }
__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)
{ … }
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)
{ … }
__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)
{ … }
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)
{ … }
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)
{ … }