linux/drivers/md/bcache/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.
 */

#define pr_fmt(fmt) …

#include "util.h"
#include "bset.h"

#include <linux/console.h>
#include <linux/sched/clock.h>
#include <linux/random.h>
#include <linux/prefetch.h>

#ifdef CONFIG_BCACHE_DEBUG

void bch_dump_bset(struct btree_keys *b, struct bset *i, unsigned int set)
{ … }

void bch_dump_bucket(struct btree_keys *b)
{ … }

int __bch_count_data(struct btree_keys *b)
{ … }

void __bch_check_keys(struct btree_keys *b, const char *fmt, ...)
{ … }

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

#else

static inline void bch_btree_iter_next_check(struct btree_iter *iter) {}

#endif

/* Keylists */

int __bch_keylist_realloc(struct keylist *l, unsigned int u64s)
{ … }

/* Pop the top key of keylist by pointing l->top to its previous key */
struct bkey *bch_keylist_pop(struct keylist *l)
{ … }

/* Pop the bottom key of keylist and update l->top_p */
void bch_keylist_pop_front(struct keylist *l)
{ … }

/* Key/pointer manipulation */

void bch_bkey_copy_single_ptr(struct bkey *dest, const struct bkey *src,
			      unsigned int i)
{ … }

bool __bch_cut_front(const struct bkey *where, struct bkey *k)
{ … }

bool __bch_cut_back(const struct bkey *where, struct bkey *k)
{ … }

/* Auxiliary search trees */

/* 32 bits total: */
#define BKEY_MID_BITS …
#define BKEY_EXPONENT_BITS …
#define BKEY_MANTISSA_BITS …
#define BKEY_MANTISSA_MASK …

struct bkey_float { … } __packed;

/*
 * BSET_CACHELINE was originally intended to match the hardware cacheline size -
 * it used to be 64, but I realized the lookup code would touch slightly less
 * memory if it was 128.
 *
 * It definites the number of bytes (in struct bset) per struct bkey_float in
 * the auxiliar search tree - when we're done searching the bset_float tree we
 * have this many bytes left that we do a linear search over.
 *
 * Since (after level 5) every level of the bset_tree is on a new cacheline,
 * we're touching one fewer cacheline in the bset tree in exchange for one more
 * cacheline in the linear search - but the linear search might stop before it
 * gets to the second cacheline.
 */

#define BSET_CACHELINE …

/* Space required for the btree node keys */
static inline size_t btree_keys_bytes(struct btree_keys *b)
{ … }

static inline size_t btree_keys_cachelines(struct btree_keys *b)
{ … }

/* Space required for the auxiliary search trees */
static inline size_t bset_tree_bytes(struct btree_keys *b)
{ … }

/* Space required for the prev pointers */
static inline size_t bset_prev_bytes(struct btree_keys *b)
{ … }

/* Memory allocation */

void bch_btree_keys_free(struct btree_keys *b)
{ … }

int bch_btree_keys_alloc(struct btree_keys *b,
			 unsigned int page_order,
			 gfp_t gfp)
{ … }

void bch_btree_keys_init(struct btree_keys *b, const struct btree_keys_ops *ops,
			 bool *expensive_debug_checks)
{ … }

/* Binary tree stuff for auxiliary search trees */

/*
 * return array index next to j when does in-order traverse
 * of a binary tree which is stored in a linear array
 */
static unsigned int inorder_next(unsigned int j, unsigned int size)
{ … }

/*
 * return array index previous to j when does in-order traverse
 * of a binary tree which is stored in a linear array
 */
static unsigned int inorder_prev(unsigned int j, unsigned int size)
{ … }

/*
 * I have no idea why this code works... and I'm the one who wrote it
 *
 * However, I do know what it does:
 * Given a binary tree constructed in an array (i.e. how you normally implement
 * a heap), it converts a node in the tree - referenced by array index - to the
 * index it would have if you did an inorder traversal.
 *
 * Also tested for every j, size up to size somewhere around 6 million.
 *
 * The binary tree starts at array index 1, not 0
 * extra is a function of size:
 *   extra = (size - rounddown_pow_of_two(size - 1)) << 1;
 */
static unsigned int __to_inorder(unsigned int j,
				  unsigned int size,
				  unsigned int extra)
{ … }

/*
 * Return the cacheline index in bset_tree->data, where j is index
 * from a linear array which stores the auxiliar binary tree
 */
static unsigned int to_inorder(unsigned int j, struct bset_tree *t)
{ … }

static unsigned int __inorder_to_tree(unsigned int j,
				      unsigned int size,
				      unsigned int extra)
{ … }

/*
 * Return an index from a linear array which stores the auxiliar binary
 * tree, j is the cacheline index of t->data.
 */
static unsigned int inorder_to_tree(unsigned int j, struct bset_tree *t)
{ … }

#if 0
void inorder_test(void)
{
	unsigned long done = 0;
	ktime_t start = ktime_get();

	for (unsigned int size = 2;
	     size < 65536000;
	     size++) {
		unsigned int extra =
			(size - rounddown_pow_of_two(size - 1)) << 1;
		unsigned int i = 1, j = rounddown_pow_of_two(size - 1);

		if (!(size % 4096))
			pr_notice("loop %u, %llu per us\n", size,
			       done / ktime_us_delta(ktime_get(), start));

		while (1) {
			if (__inorder_to_tree(i, size, extra) != j)
				panic("size %10u j %10u i %10u", size, j, i);

			if (__to_inorder(j, size, extra) != i)
				panic("size %10u j %10u i %10u", size, j, i);

			if (j == rounddown_pow_of_two(size) - 1)
				break;

			BUG_ON(inorder_prev(inorder_next(j, size), size) != j);

			j = inorder_next(j, size);
			i++;
		}

		done += size - 1;
	}
}
#endif

/*
 * 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; 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 struct bkey *cacheline_to_bkey(struct bset_tree *t,
				      unsigned int cacheline,
				      unsigned int offset)
{ … }

static unsigned int bkey_to_cacheline(struct bset_tree *t, struct bkey *k)
{ … }

static unsigned int bkey_to_cacheline_offset(struct bset_tree *t,
					 unsigned int cacheline,
					 struct bkey *k)
{ … }

static struct bkey *tree_to_bkey(struct bset_tree *t, unsigned int j)
{ … }

static struct bkey *tree_to_prev_bkey(struct bset_tree *t, unsigned int j)
{ … }

/*
 * 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 *table_to_bkey(struct bset_tree *t, unsigned int cacheline)
{ … }

static inline uint64_t shrd128(uint64_t high, uint64_t low, uint8_t shift)
{ … }

/*
 * Calculate mantissa value for struct bkey_float.
 * If most significant bit of f->exponent is not set, then
 *  - f->exponent >> 6 is 0
 *  - p[0] points to bkey->low
 *  - p[-1] borrows bits from KEY_INODE() of bkey->high
 * if most isgnificant bits of f->exponent is set, then
 *  - f->exponent >> 6 is 1
 *  - p[0] points to bits from KEY_INODE() of bkey->high
 *  - p[-1] points to other bits from KEY_INODE() of
 *    bkey->high too.
 * See make_bfloat() to check when most significant bit of f->exponent
 * is set or not.
 */
static inline unsigned int bfloat_mantissa(const struct bkey *k,
				       struct bkey_float *f)
{ … }

static void make_bfloat(struct bset_tree *t, unsigned int j)
{ … }

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

static void bch_bset_build_unwritten_tree(struct btree_keys *b)
{ … }

void bch_bset_init_next(struct btree_keys *b, struct bset *i, uint64_t magic)
{ … }

/*
 * Build auxiliary binary tree 'struct bset_tree *t', this tree is used to
 * accelerate bkey search in a btree node (pointed by bset_tree->data in
 * memory). After search in the auxiliar tree by calling bset_search_tree(),
 * a struct bset_search_iter is returned which indicates range [l, r] from
 * bset_tree->data where the searching bkey might be inside. Then a followed
 * linear comparison does the exact search, see __bch_bset_search() for how
 * the auxiliary tree is used.
 */
void bch_bset_build_written_tree(struct btree_keys *b)
{ … }

/* Insert */

void bch_bset_fix_invalidated_key(struct btree_keys *b, struct bkey *k)
{ … }

static void bch_bset_fix_lookup_table(struct btree_keys *b,
				      struct bset_tree *t,
				      struct bkey *k)
{ … }

/*
 * Tries to merge l and r: l should be lower than r
 * Returns true if we were able to merge. If we did merge, l will be the merged
 * key, r will be untouched.
 */
bool bch_bkey_try_merge(struct btree_keys *b, struct bkey *l, struct bkey *r)
{ … }

void bch_bset_insert(struct btree_keys *b, struct bkey *where,
		     struct bkey *insert)
{ … }

unsigned int bch_btree_insert_key(struct btree_keys *b, struct bkey *k,
			      struct bkey *replace_key)
{ … }

/* Lookup */

struct bset_search_iter { … };

static struct bset_search_iter bset_search_write_set(struct bset_tree *t,
						     const struct bkey *search)
{ … }

static struct bset_search_iter bset_search_tree(struct bset_tree *t,
						const struct bkey *search)
{ … }

struct bkey *__bch_bset_search(struct btree_keys *b, struct bset_tree *t,
			       const struct bkey *search)
{ … }

/* Btree iterator */

new_btree_iter_cmp_fn;

static inline bool new_btree_iter_cmp(const void *l, const void *r, void __always_unused *args)
{ … }

static inline void new_btree_iter_swap(void *iter1, void *iter2, void __always_unused *args)
{ … }

static inline bool btree_iter_end(struct btree_iter *iter)
{ … }

void bch_btree_iter_push(struct btree_iter *iter, struct bkey *k,
			 struct bkey *end)
{ … }

static struct bkey *__bch_btree_iter_init(struct btree_keys *b,
					  struct btree_iter *iter,
					  struct bkey *search,
					  struct bset_tree *start)
{ … }

struct bkey *bch_btree_iter_init(struct btree_keys *b,
				 struct btree_iter *iter,
				 struct bkey *search)
{ … }

static inline struct bkey *__bch_btree_iter_next(struct btree_iter *iter,
						 new_btree_iter_cmp_fn *cmp)
{ … }

struct bkey *bch_btree_iter_next(struct btree_iter *iter)
{ … }

struct bkey *bch_btree_iter_next_filter(struct btree_iter *iter,
					struct btree_keys *b, ptr_filter_fn fn)
{ … }

/* Mergesort */

void bch_bset_sort_state_free(struct bset_sort_state *state)
{ … }

int bch_bset_sort_state_init(struct bset_sort_state *state,
			     unsigned int page_order)
{ … }

static void btree_mergesort(struct btree_keys *b, struct bset *out,
			    struct btree_iter *iter,
			    bool fixup, bool remove_stale)
{ … }

static void __btree_sort(struct btree_keys *b, struct btree_iter *iter,
			 unsigned int start, unsigned int order, bool fixup,
			 struct bset_sort_state *state)
{ … }

void bch_btree_sort_partial(struct btree_keys *b, unsigned int start,
			    struct bset_sort_state *state)
{ … }

void bch_btree_sort_and_fix_extents(struct btree_keys *b,
				    struct btree_iter *iter,
				    struct bset_sort_state *state)
{ … }

void bch_btree_sort_into(struct btree_keys *b, struct btree_keys *new,
			 struct bset_sort_state *state)
{ … }

#define SORT_CRIT …

void bch_btree_sort_lazy(struct btree_keys *b, struct bset_sort_state *state)
{ … }

void bch_btree_keys_stats(struct btree_keys *b, struct bset_stats *stats)
{ … }