[mirror_ubuntu-kernels.git] / drivers / md / bcache / extents.c

// SPDX-License-Identifier: GPL-2.0
/*
 * Copyright (C) 2010 Kent Overstreet <kent.overstreet@gmail.com>
 *
 * Uses a block device as cache for other block devices; optimized for SSDs.
 * All allocation is done in buckets, which should match the erase block size
 * of the device.
 *
 * Buckets containing cached data are kept on a heap sorted by priority;
 * bucket priority is increased on cache hit, and periodically all the buckets
 * on the heap have their priority scaled down. This currently is just used as
 * an LRU but in the future should allow for more intelligent heuristics.
 *
 * Buckets have an 8 bit counter; freeing is accomplished by incrementing the
 * counter. Garbage collection is used to remove stale pointers.
 *
 * Indexing is done via a btree; nodes are not necessarily fully sorted, rather
 * as keys are inserted we only sort the pages that have not yet been written.
 * When garbage collection is run, we resort the entire node.
 *
 * All configuration is done via sysfs; see Documentation/admin-guide/bcache.rst.
 */

#include "bcache.h"
#include "btree.h"
#include "debug.h"
#include "extents.h"
#include "writeback.h"

static void sort_key_next(struct btree_iter *iter,
			  struct btree_iter_set *i)
{
	i->k = bkey_next(i->k);

	if (i->k == i->end)
		*i = iter->data[--iter->used];
}

static bool bch_key_sort_cmp(struct btree_iter_set l,
			     struct btree_iter_set r)
{
	int64_t c = bkey_cmp(l.k, r.k);

	return c ? c > 0 : l.k < r.k;
}

static bool __ptr_invalid(struct cache_set *c, const struct bkey *k)
{
	unsigned int i;

	for (i = 0; i < KEY_PTRS(k); i++)
		if (ptr_available(c, k, i)) {
			struct cache *ca = PTR_CACHE(c, k, i);
			size_t bucket = PTR_BUCKET_NR(c, k, i);
			size_t r = bucket_remainder(c, PTR_OFFSET(k, i));

			if (KEY_SIZE(k) + r > c->sb.bucket_size ||
			    bucket <  ca->sb.first_bucket ||
			    bucket >= ca->sb.nbuckets)
				return true;
		}

	return false;
}

/* Common among btree and extent ptrs */

static const char *bch_ptr_status(struct cache_set *c, const struct bkey *k)
{
	unsigned int i;

	for (i = 0; i < KEY_PTRS(k); i++)
		if (ptr_available(c, k, i)) {
			struct cache *ca = PTR_CACHE(c, k, i);
			size_t bucket = PTR_BUCKET_NR(c, k, i);
			size_t r = bucket_remainder(c, PTR_OFFSET(k, i));

			if (KEY_SIZE(k) + r > c->sb.bucket_size)
				return "bad, length too big";
			if (bucket <  ca->sb.first_bucket)
				return "bad, short offset";
			if (bucket >= ca->sb.nbuckets)
				return "bad, offset past end of device";
			if (ptr_stale(c, k, i))
				return "stale";
		}

	if (!bkey_cmp(k, &ZERO_KEY))
		return "bad, null key";
	if (!KEY_PTRS(k))
		return "bad, no pointers";
	if (!KEY_SIZE(k))
		return "zeroed key";
	return "";
}

void bch_extent_to_text(char *buf, size_t size, const struct bkey *k)
{
	unsigned int i = 0;
	char *out = buf, *end = buf + size;

#define p(...)	(out += scnprintf(out, end - out, __VA_ARGS__))

	p("%llu:%llu len %llu -> [", KEY_INODE(k), KEY_START(k), KEY_SIZE(k));

	for (i = 0; i < KEY_PTRS(k); i++) {
		if (i)
			p(", ");

		if (PTR_DEV(k, i) == PTR_CHECK_DEV)
			p("check dev");
		else
			p("%llu:%llu gen %llu", PTR_DEV(k, i),
			  PTR_OFFSET(k, i), PTR_GEN(k, i));
	}

	p("]");

	if (KEY_DIRTY(k))
		p(" dirty");
	if (KEY_CSUM(k))
		p(" cs%llu %llx", KEY_CSUM(k), k->ptr[1]);
#undef p
}

static void bch_bkey_dump(struct btree_keys *keys, const struct bkey *k)
{
	struct btree *b = container_of(keys, struct btree, keys);
	unsigned int j;
	char buf[80];

	bch_extent_to_text(buf, sizeof(buf), k);
	pr_err(" %s", buf);

	for (j = 0; j < KEY_PTRS(k); j++) {
		size_t n = PTR_BUCKET_NR(b->c, k, j);

		pr_err(" bucket %zu", n);
		if (n >= b->c->sb.first_bucket && n < b->c->sb.nbuckets)
			pr_err(" prio %i",
			       PTR_BUCKET(b->c, k, j)->prio);
	}

	pr_err(" %s\n", bch_ptr_status(b->c, k));
}

/* Btree ptrs */

bool __bch_btree_ptr_invalid(struct cache_set *c, const struct bkey *k)
{
	char buf[80];

	if (!KEY_PTRS(k) || !KEY_SIZE(k) || KEY_DIRTY(k))
		goto bad;

	if (__ptr_invalid(c, k))
		goto bad;

	return false;
bad:
	bch_extent_to_text(buf, sizeof(buf), k);
	cache_bug(c, "spotted btree ptr %s: %s", buf, bch_ptr_status(c, k));
	return true;
}

static bool bch_btree_ptr_invalid(struct btree_keys *bk, const struct bkey *k)
{
	struct btree *b = container_of(bk, struct btree, keys);

	return __bch_btree_ptr_invalid(b->c, k);
}

static bool btree_ptr_bad_expensive(struct btree *b, const struct bkey *k)
{
	unsigned int i;
	char buf[80];
	struct bucket *g;

	if (mutex_trylock(&b->c->bucket_lock)) {
		for (i = 0; i < KEY_PTRS(k); i++)
			if (ptr_available(b->c, k, i)) {
				g = PTR_BUCKET(b->c, k, i);

				if (KEY_DIRTY(k) ||
				    g->prio != BTREE_PRIO ||
				    (b->c->gc_mark_valid &&
				     GC_MARK(g) != GC_MARK_METADATA))
					goto err;
			}

		mutex_unlock(&b->c->bucket_lock);
	}

	return false;
err:
	mutex_unlock(&b->c->bucket_lock);
	bch_extent_to_text(buf, sizeof(buf), k);
	btree_bug(b,
"inconsistent btree pointer %s: bucket %zi pin %i prio %i gen %i last_gc %i mark %llu",
		  buf, PTR_BUCKET_NR(b->c, k, i), atomic_read(&g->pin),
		  g->prio, g->gen, g->last_gc, GC_MARK(g));
	return true;
}

static bool bch_btree_ptr_bad(struct btree_keys *bk, const struct bkey *k)
{
	struct btree *b = container_of(bk, struct btree, keys);
	unsigned int i;

	if (!bkey_cmp(k, &ZERO_KEY) ||
	    !KEY_PTRS(k) ||
	    bch_ptr_invalid(bk, k))
		return true;

	for (i = 0; i < KEY_PTRS(k); i++)
		if (!ptr_available(b->c, k, i) ||
		    ptr_stale(b->c, k, i))
			return true;

	if (expensive_debug_checks(b->c) &&
	    btree_ptr_bad_expensive(b, k))
		return true;

	return false;
}

static bool bch_btree_ptr_insert_fixup(struct btree_keys *bk,
				       struct bkey *insert,
				       struct btree_iter *iter,
				       struct bkey *replace_key)
{
	struct btree *b = container_of(bk, struct btree, keys);

	if (!KEY_OFFSET(insert))
		btree_current_write(b)->prio_blocked++;

	return false;
}

const struct btree_keys_ops bch_btree_keys_ops = {
	.sort_cmp	= bch_key_sort_cmp,
	.insert_fixup	= bch_btree_ptr_insert_fixup,
	.key_invalid	= bch_btree_ptr_invalid,
	.key_bad	= bch_btree_ptr_bad,
	.key_to_text	= bch_extent_to_text,
	.key_dump	= bch_bkey_dump,
};

/* Extents */

/*
 * Returns true if l > r - unless l == r, in which case returns true if l is
 * older than r.
 *
 * Necessary for btree_sort_fixup() - if there are multiple keys that compare
 * equal in different sets, we have to process them newest to oldest.
 */
static bool bch_extent_sort_cmp(struct btree_iter_set l,
				struct btree_iter_set r)
{
	int64_t c = bkey_cmp(&START_KEY(l.k), &START_KEY(r.k));

	return c ? c > 0 : l.k < r.k;
}

static struct bkey *bch_extent_sort_fixup(struct btree_iter *iter,
					  struct bkey *tmp)
{
	while (iter->used > 1) {
		struct btree_iter_set *top = iter->data, *i = top + 1;

		if (iter->used > 2 &&
		    bch_extent_sort_cmp(i[0], i[1]))
			i++;

		if (bkey_cmp(top->k, &START_KEY(i->k)) <= 0)
			break;

		if (!KEY_SIZE(i->k)) {
			sort_key_next(iter, i);
			heap_sift(iter, i - top, bch_extent_sort_cmp);
			continue;
		}

		if (top->k > i->k) {
			if (bkey_cmp(top->k, i->k) >= 0)
				sort_key_next(iter, i);
			else
				bch_cut_front(top->k, i->k);

			heap_sift(iter, i - top, bch_extent_sort_cmp);
		} else {
			/* can't happen because of comparison func */
			BUG_ON(!bkey_cmp(&START_KEY(top->k), &START_KEY(i->k)));

			if (bkey_cmp(i->k, top->k) < 0) {
				bkey_copy(tmp, top->k);

				bch_cut_back(&START_KEY(i->k), tmp);
				bch_cut_front(i->k, top->k);
				heap_sift(iter, 0, bch_extent_sort_cmp);

				return tmp;
			} else {
				bch_cut_back(&START_KEY(i->k), top->k);
			}
		}
	}

	return NULL;
}

static void bch_subtract_dirty(struct bkey *k,
			   struct cache_set *c,
			   uint64_t offset,
			   int sectors)
{
	if (KEY_DIRTY(k))
		bcache_dev_sectors_dirty_add(c, KEY_INODE(k),
					     offset, -sectors);
}

static bool bch_extent_insert_fixup(struct btree_keys *b,
				    struct bkey *insert,
				    struct btree_iter *iter,
				    struct bkey *replace_key)
{
	struct cache_set *c = container_of(b, struct btree, keys)->c;

	uint64_t old_offset;
	unsigned int old_size, sectors_found = 0;

	BUG_ON(!KEY_OFFSET(insert));
	BUG_ON(!KEY_SIZE(insert));

	while (1) {
		struct bkey *k = bch_btree_iter_next(iter);

		if (!k)
			break;

		if (bkey_cmp(&START_KEY(k), insert) >= 0) {
			if (KEY_SIZE(k))
				break;
			else
				continue;
		}

		if (bkey_cmp(k, &START_KEY(insert)) <= 0)
			continue;

		old_offset = KEY_START(k);
		old_size = KEY_SIZE(k);

		/*
		 * We might overlap with 0 size extents; we can't skip these
		 * because if they're in the set we're inserting to we have to
		 * adjust them so they don't overlap with the key we're
		 * inserting. But we don't want to check them for replace
		 * operations.
		 */

		if (replace_key && KEY_SIZE(k)) {
			/*
			 * k might have been split since we inserted/found the
			 * key we're replacing
			 */
			unsigned int i;
			uint64_t offset = KEY_START(k) -
				KEY_START(replace_key);

			/* But it must be a subset of the replace key */
			if (KEY_START(k) < KEY_START(replace_key) ||
			    KEY_OFFSET(k) > KEY_OFFSET(replace_key))
				goto check_failed;

			/* We didn't find a key that we were supposed to */
			if (KEY_START(k) > KEY_START(insert) + sectors_found)
				goto check_failed;

			if (!bch_bkey_equal_header(k, replace_key))
				goto check_failed;

			/* skip past gen */
			offset <<= 8;

			BUG_ON(!KEY_PTRS(replace_key));

			for (i = 0; i < KEY_PTRS(replace_key); i++)
				if (k->ptr[i] != replace_key->ptr[i] + offset)
					goto check_failed;

			sectors_found = KEY_OFFSET(k) - KEY_START(insert);
		}

		if (bkey_cmp(insert, k) < 0 &&
		    bkey_cmp(&START_KEY(insert), &START_KEY(k)) > 0) {
			/*
			 * We overlapped in the middle of an existing key: that
			 * means we have to split the old key. But we have to do
			 * slightly different things depending on whether the
			 * old key has been written out yet.
			 */

			struct bkey *top;

			bch_subtract_dirty(k, c, KEY_START(insert),
				       KEY_SIZE(insert));

			if (bkey_written(b, k)) {
				/*
				 * We insert a new key to cover the top of the
				 * old key, and the old key is modified in place
				 * to represent the bottom split.
				 *
				 * It's completely arbitrary whether the new key
				 * is the top or the bottom, but it has to match
				 * up with what btree_sort_fixup() does - it
				 * doesn't check for this kind of overlap, it
				 * depends on us inserting a new key for the top
				 * here.
				 */
				top = bch_bset_search(b, bset_tree_last(b),
						      insert);
				bch_bset_insert(b, top, k);
			} else {
				BKEY_PADDED(key) temp;
				bkey_copy(&temp.key, k);
				bch_bset_insert(b, k, &temp.key);
				top = bkey_next(k);
			}

			bch_cut_front(insert, top);
			bch_cut_back(&START_KEY(insert), k);
			bch_bset_fix_invalidated_key(b, k);
			goto out;
		}

		if (bkey_cmp(insert, k) < 0) {
			bch_cut_front(insert, k);
		} else {
			if (bkey_cmp(&START_KEY(insert), &START_KEY(k)) > 0)
				old_offset = KEY_START(insert);

			if (bkey_written(b, k) &&
			    bkey_cmp(&START_KEY(insert), &START_KEY(k)) <= 0) {
				/*
				 * Completely overwrote, so we don't have to
				 * invalidate the binary search tree
				 */
				bch_cut_front(k, k);
			} else {
				__bch_cut_back(&START_KEY(insert), k);
				bch_bset_fix_invalidated_key(b, k);
			}
		}

		bch_subtract_dirty(k, c, old_offset, old_size - KEY_SIZE(k));
	}

check_failed:
	if (replace_key) {
		if (!sectors_found) {
			return true;
		} else if (sectors_found < KEY_SIZE(insert)) {
			SET_KEY_OFFSET(insert, KEY_OFFSET(insert) -
				       (KEY_SIZE(insert) - sectors_found));
			SET_KEY_SIZE(insert, sectors_found);
		}
	}
out:
	if (KEY_DIRTY(insert))
		bcache_dev_sectors_dirty_add(c, KEY_INODE(insert),
					     KEY_START(insert),
					     KEY_SIZE(insert));

	return false;
}

bool __bch_extent_invalid(struct cache_set *c, const struct bkey *k)
{
	char buf[80];

	if (!KEY_SIZE(k))
		return true;

	if (KEY_SIZE(k) > KEY_OFFSET(k))
		goto bad;

	if (__ptr_invalid(c, k))
		goto bad;

	return false;
bad:
	bch_extent_to_text(buf, sizeof(buf), k);
	cache_bug(c, "spotted extent %s: %s", buf, bch_ptr_status(c, k));
	return true;
}

static bool bch_extent_invalid(struct btree_keys *bk, const struct bkey *k)
{
	struct btree *b = container_of(bk, struct btree, keys);

	return __bch_extent_invalid(b->c, k);
}

static bool bch_extent_bad_expensive(struct btree *b, const struct bkey *k,
				     unsigned int ptr)
{
	struct bucket *g = PTR_BUCKET(b->c, k, ptr);
	char buf[80];

	if (mutex_trylock(&b->c->bucket_lock)) {
		if (b->c->gc_mark_valid &&
		    (!GC_MARK(g) ||
		     GC_MARK(g) == GC_MARK_METADATA ||
		     (GC_MARK(g) != GC_MARK_DIRTY && KEY_DIRTY(k))))
			goto err;

		if (g->prio == BTREE_PRIO)
			goto err;

		mutex_unlock(&b->c->bucket_lock);
	}

	return false;
err:
	mutex_unlock(&b->c->bucket_lock);
	bch_extent_to_text(buf, sizeof(buf), k);
	btree_bug(b,
"inconsistent extent pointer %s:\nbucket %zu pin %i prio %i gen %i last_gc %i mark %llu",
		  buf, PTR_BUCKET_NR(b->c, k, ptr), atomic_read(&g->pin),
		  g->prio, g->gen, g->last_gc, GC_MARK(g));
	return true;
}

static bool bch_extent_bad(struct btree_keys *bk, const struct bkey *k)
{
	struct btree *b = container_of(bk, struct btree, keys);
	unsigned int i, stale;
	char buf[80];

	if (!KEY_PTRS(k) ||
	    bch_extent_invalid(bk, k))
		return true;

	for (i = 0; i < KEY_PTRS(k); i++)
		if (!ptr_available(b->c, k, i))
			return true;

	for (i = 0; i < KEY_PTRS(k); i++) {
		stale = ptr_stale(b->c, k, i);

		if (stale && KEY_DIRTY(k)) {
			bch_extent_to_text(buf, sizeof(buf), k);
			pr_info("stale dirty pointer, stale %u, key: %s",
				stale, buf);
		}

		btree_bug_on(stale > BUCKET_GC_GEN_MAX, b,
			     "key too stale: %i, need_gc %u",
			     stale, b->c->need_gc);

		if (stale)
			return true;

		if (expensive_debug_checks(b->c) &&
		    bch_extent_bad_expensive(b, k, i))
			return true;
	}

	return false;
}

static uint64_t merge_chksums(struct bkey *l, struct bkey *r)
{
	return (l->ptr[KEY_PTRS(l)] + r->ptr[KEY_PTRS(r)]) &
		~((uint64_t)1 << 63);
}

static bool bch_extent_merge(struct btree_keys *bk,
			     struct bkey *l,
			     struct bkey *r)
{
	struct btree *b = container_of(bk, struct btree, keys);
	unsigned int i;

	if (key_merging_disabled(b->c))
		return false;

	for (i = 0; i < KEY_PTRS(l); i++)
		if (l->ptr[i] + MAKE_PTR(0, KEY_SIZE(l), 0) != r->ptr[i] ||
		    PTR_BUCKET_NR(b->c, l, i) != PTR_BUCKET_NR(b->c, r, i))
			return false;

	/* Keys with no pointers aren't restricted to one bucket and could
	 * overflow KEY_SIZE
	 */
	if (KEY_SIZE(l) + KEY_SIZE(r) > USHRT_MAX) {
		SET_KEY_OFFSET(l, KEY_OFFSET(l) + USHRT_MAX - KEY_SIZE(l));
		SET_KEY_SIZE(l, USHRT_MAX);

		bch_cut_front(l, r);
		return false;
	}

	if (KEY_CSUM(l)) {
		if (KEY_CSUM(r))
			l->ptr[KEY_PTRS(l)] = merge_chksums(l, r);
		else
			SET_KEY_CSUM(l, 0);
	}

	SET_KEY_OFFSET(l, KEY_OFFSET(l) + KEY_SIZE(r));
	SET_KEY_SIZE(l, KEY_SIZE(l) + KEY_SIZE(r));

	return true;
}

const struct btree_keys_ops bch_extent_keys_ops = {
	.sort_cmp	= bch_extent_sort_cmp,
	.sort_fixup	= bch_extent_sort_fixup,
	.insert_fixup	= bch_extent_insert_fixup,
	.key_invalid	= bch_extent_invalid,
	.key_bad	= bch_extent_bad,
	.key_merge	= bch_extent_merge,
	.key_to_text	= bch_extent_to_text,
	.key_dump	= bch_bkey_dump,
	.is_extents	= true,
};
Commit	Line	Data
b2441318	1	// SPDX-License-Identifier: GPL-2.0
65d45231 KO	2	/*
	3	* Copyright (C) 2010 Kent Overstreet <kent.overstreet@gmail.com>
	4	*
	5	* Uses a block device as cache for other block devices; optimized for SSDs.
	6	* All allocation is done in buckets, which should match the erase block size
	7	* of the device.
	8	*
	9	* Buckets containing cached data are kept on a heap sorted by priority;
	10	* bucket priority is increased on cache hit, and periodically all the buckets
	11	* on the heap have their priority scaled down. This currently is just used as
	12	* an LRU but in the future should allow for more intelligent heuristics.
	13	*
	14	* Buckets have an 8 bit counter; freeing is accomplished by incrementing the
	15	* counter. Garbage collection is used to remove stale pointers.
	16	*
	17	* Indexing is done via a btree; nodes are not necessarily fully sorted, rather
	18	* as keys are inserted we only sort the pages that have not yet been written.
	19	* When garbage collection is run, we resort the entire node.
	20	*
5fb94e9c	21	* All configuration is done via sysfs; see Documentation/admin-guide/bcache.rst.
65d45231 KO	22	*/
	23
	24	#include "bcache.h"
	25	#include "btree.h"
	26	#include "debug.h"
	27	#include "extents.h"
	28	#include "writeback.h"
	29
	30	static void sort_key_next(struct btree_iter *iter,
	31	struct btree_iter_set *i)
	32	{
	33	i->k = bkey_next(i->k);
	34
	35	if (i->k == i->end)
	36	*i = iter->data[--iter->used];
	37	}
	38
	39	static bool bch_key_sort_cmp(struct btree_iter_set l,
	40	struct btree_iter_set r)
	41	{
	42	int64_t c = bkey_cmp(l.k, r.k);
	43
	44	return c ? c > 0 : l.k < r.k;
	45	}
	46
	47	static bool __ptr_invalid(struct cache_set c, const struct bkey k)
	48	{
6f10f7d1	49	unsigned int i;
65d45231 KO	50
	51	for (i = 0; i < KEY_PTRS(k); i++)
	52	if (ptr_available(c, k, i)) {
	53	struct cache *ca = PTR_CACHE(c, k, i);
	54	size_t bucket = PTR_BUCKET_NR(c, k, i);
	55	size_t r = bucket_remainder(c, PTR_OFFSET(k, i));
	56
	57	if (KEY_SIZE(k) + r > c->sb.bucket_size \|\|
	58	bucket < ca->sb.first_bucket \|\|
	59	bucket >= ca->sb.nbuckets)
	60	return true;
	61	}
	62
	63	return false;
	64	}
	65
dc9d98d6 KO	66	/* Common among btree and extent ptrs */
	67
	68	static const char bch_ptr_status(struct cache_set c, const struct bkey *k)
	69	{
6f10f7d1	70	unsigned int i;
dc9d98d6 KO	71
	72	for (i = 0; i < KEY_PTRS(k); i++)
	73	if (ptr_available(c, k, i)) {
	74	struct cache *ca = PTR_CACHE(c, k, i);
	75	size_t bucket = PTR_BUCKET_NR(c, k, i);
	76	size_t r = bucket_remainder(c, PTR_OFFSET(k, i));
	77
	78	if (KEY_SIZE(k) + r > c->sb.bucket_size)
	79	return "bad, length too big";
	80	if (bucket < ca->sb.first_bucket)
	81	return "bad, short offset";
	82	if (bucket >= ca->sb.nbuckets)
	83	return "bad, offset past end of device";
	84	if (ptr_stale(c, k, i))
	85	return "stale";
	86	}
	87
	88	if (!bkey_cmp(k, &ZERO_KEY))
	89	return "bad, null key";
	90	if (!KEY_PTRS(k))
	91	return "bad, no pointers";
	92	if (!KEY_SIZE(k))
	93	return "zeroed key";
	94	return "";
	95	}
	96
	97	void bch_extent_to_text(char buf, size_t size, const struct bkey k)
	98	{
6f10f7d1	99	unsigned int i = 0;
dc9d98d6 KO	100	char out = buf, end = buf + size;
	101
	102	#define p(...) (out += scnprintf(out, end - out, __VA_ARGS__))
	103
	104	p("%llu:%llu len %llu -> [", KEY_INODE(k), KEY_START(k), KEY_SIZE(k));
	105
	106	for (i = 0; i < KEY_PTRS(k); i++) {
	107	if (i)
	108	p(", ");
	109
	110	if (PTR_DEV(k, i) == PTR_CHECK_DEV)
	111	p("check dev");
	112	else
	113	p("%llu:%llu gen %llu", PTR_DEV(k, i),
	114	PTR_OFFSET(k, i), PTR_GEN(k, i));
	115	}
	116
	117	p("]");
	118
	119	if (KEY_DIRTY(k))
	120	p(" dirty");
	121	if (KEY_CSUM(k))
	122	p(" cs%llu %llx", KEY_CSUM(k), k->ptr[1]);
	123	#undef p
	124	}
	125
	126	static void bch_bkey_dump(struct btree_keys keys, const struct bkey k)
	127	{
	128	struct btree *b = container_of(keys, struct btree, keys);
6f10f7d1	129	unsigned int j;
dc9d98d6 KO	130	char buf[80];
	131
	132	bch_extent_to_text(buf, sizeof(buf), k);
6ae63e35	133	pr_err(" %s", buf);
dc9d98d6 KO	134
	135	for (j = 0; j < KEY_PTRS(k); j++) {
	136	size_t n = PTR_BUCKET_NR(b->c, k, j);
dc9d98d6	137
6ae63e35	138	pr_err(" bucket %zu", n);
dc9d98d6	139	if (n >= b->c->sb.first_bucket && n < b->c->sb.nbuckets)
6ae63e35	140	pr_err(" prio %i",
dc9d98d6 KO	141	PTR_BUCKET(b->c, k, j)->prio);
	142	}
	143
6ae63e35	144	pr_err(" %s\n", bch_ptr_status(b->c, k));
dc9d98d6 KO	145	}
dc9d98d6 KO	146
65d45231 KO	147	/* Btree ptrs */
	148
	149	bool __bch_btree_ptr_invalid(struct cache_set c, const struct bkey k)
	150	{
	151	char buf[80];
	152
	153	if (!KEY_PTRS(k) \|\| !KEY_SIZE(k) \|\| KEY_DIRTY(k))
	154	goto bad;
	155
	156	if (__ptr_invalid(c, k))
	157	goto bad;
	158
	159	return false;
	160	bad:
dc9d98d6	161	bch_extent_to_text(buf, sizeof(buf), k);
65d45231 KO	162	cache_bug(c, "spotted btree ptr %s: %s", buf, bch_ptr_status(c, k));
	163	return true;
	164	}
	165
a85e968e	166	static bool bch_btree_ptr_invalid(struct btree_keys bk, const struct bkey k)
65d45231	167	{
a85e968e	168	struct btree *b = container_of(bk, struct btree, keys);
1fae7cf0	169
65d45231 KO	170	return __bch_btree_ptr_invalid(b->c, k);
	171	}
	172
	173	static bool btree_ptr_bad_expensive(struct btree b, const struct bkey k)
	174	{
6f10f7d1	175	unsigned int i;
65d45231 KO	176	char buf[80];
	177	struct bucket *g;
	178
	179	if (mutex_trylock(&b->c->bucket_lock)) {
	180	for (i = 0; i < KEY_PTRS(k); i++)
	181	if (ptr_available(b->c, k, i)) {
	182	g = PTR_BUCKET(b->c, k, i);
	183
	184	if (KEY_DIRTY(k) \|\|
	185	g->prio != BTREE_PRIO \|\|
	186	(b->c->gc_mark_valid &&
	187	GC_MARK(g) != GC_MARK_METADATA))
	188	goto err;
	189	}
	190
	191	mutex_unlock(&b->c->bucket_lock);
	192	}
	193
	194	return false;
	195	err:
	196	mutex_unlock(&b->c->bucket_lock);
dc9d98d6	197	bch_extent_to_text(buf, sizeof(buf), k);
65d45231	198	btree_bug(b,
3a2fd9d5	199	"inconsistent btree pointer %s: bucket %zi pin %i prio %i gen %i last_gc %i mark %llu",
65d45231	200	buf, PTR_BUCKET_NR(b->c, k, i), atomic_read(&g->pin),
3a2fd9d5	201	g->prio, g->gen, g->last_gc, GC_MARK(g));
65d45231 KO	202	return true;
	203	}
	204
a85e968e	205	static bool bch_btree_ptr_bad(struct btree_keys bk, const struct bkey k)
65d45231	206	{
a85e968e	207	struct btree *b = container_of(bk, struct btree, keys);
6f10f7d1	208	unsigned int i;
65d45231 KO	209
	210	if (!bkey_cmp(k, &ZERO_KEY) \|\|
	211	!KEY_PTRS(k) \|\|
a85e968e	212	bch_ptr_invalid(bk, k))
65d45231 KO	213	return true;
	214
	215	for (i = 0; i < KEY_PTRS(k); i++)
	216	if (!ptr_available(b->c, k, i) \|\|
	217	ptr_stale(b->c, k, i))
	218	return true;
	219
	220	if (expensive_debug_checks(b->c) &&
	221	btree_ptr_bad_expensive(b, k))
	222	return true;
	223
	224	return false;
	225	}
	226
829a60b9 KO	227	static bool bch_btree_ptr_insert_fixup(struct btree_keys *bk,
	228	struct bkey *insert,
	229	struct btree_iter *iter,
	230	struct bkey *replace_key)
	231	{
	232	struct btree *b = container_of(bk, struct btree, keys);
	233
	234	if (!KEY_OFFSET(insert))
	235	btree_current_write(b)->prio_blocked++;
	236
	237	return false;
	238	}
	239
65d45231 KO	240	const struct btree_keys_ops bch_btree_keys_ops = {
65d45231 KO	241	.sort_cmp = bch_key_sort_cmp,
829a60b9	242	.insert_fixup = bch_btree_ptr_insert_fixup,
65d45231 KO	243	.key_invalid = bch_btree_ptr_invalid,
65d45231 KO	244	.key_bad = bch_btree_ptr_bad,
dc9d98d6 KO	245	.key_to_text = bch_extent_to_text,
dc9d98d6 KO	246	.key_dump = bch_bkey_dump,
65d45231 KO	247	};
	248
	249	/* Extents */
	250
	251	/*
	252	* Returns true if l > r - unless l == r, in which case returns true if l is
	253	* older than r.
	254	*
	255	* Necessary for btree_sort_fixup() - if there are multiple keys that compare
	256	* equal in different sets, we have to process them newest to oldest.
	257	*/
	258	static bool bch_extent_sort_cmp(struct btree_iter_set l,
	259	struct btree_iter_set r)
	260	{
	261	int64_t c = bkey_cmp(&START_KEY(l.k), &START_KEY(r.k));
	262
	263	return c ? c > 0 : l.k < r.k;
	264	}
	265
	266	static struct bkey bch_extent_sort_fixup(struct btree_iter iter,
	267	struct bkey *tmp)
	268	{
	269	while (iter->used > 1) {
	270	struct btree_iter_set top = iter->data, i = top + 1;
	271
	272	if (iter->used > 2 &&
	273	bch_extent_sort_cmp(i[0], i[1]))
	274	i++;
	275
	276	if (bkey_cmp(top->k, &START_KEY(i->k)) <= 0)
	277	break;
	278
	279	if (!KEY_SIZE(i->k)) {
	280	sort_key_next(iter, i);
	281	heap_sift(iter, i - top, bch_extent_sort_cmp);
	282	continue;
	283	}
	284
	285	if (top->k > i->k) {
	286	if (bkey_cmp(top->k, i->k) >= 0)
	287	sort_key_next(iter, i);
	288	else
	289	bch_cut_front(top->k, i->k);
	290
	291	heap_sift(iter, i - top, bch_extent_sort_cmp);
	292	} else {
	293	/* can't happen because of comparison func */
	294	BUG_ON(!bkey_cmp(&START_KEY(top->k), &START_KEY(i->k)));
	295
	296	if (bkey_cmp(i->k, top->k) < 0) {
	297	bkey_copy(tmp, top->k);
	298
	299	bch_cut_back(&START_KEY(i->k), tmp);
	300	bch_cut_front(i->k, top->k);
	301	heap_sift(iter, 0, bch_extent_sort_cmp);
	302
	303	return tmp;
	304	} else {
	305	bch_cut_back(&START_KEY(i->k), top->k);
	306	}
	307	}
	308	}
	309
	310	return NULL;
311	}
312
cb851149 JS	313	static void bch_subtract_dirty(struct bkey *k,
	314	struct cache_set *c,
	315	uint64_t offset,
	316	int sectors)
	317	{
	318	if (KEY_DIRTY(k))
	319	bcache_dev_sectors_dirty_add(c, KEY_INODE(k),
	320	offset, -sectors);
	321	}
	322
829a60b9 KO	323	static bool bch_extent_insert_fixup(struct btree_keys *b,
	324	struct bkey *insert,
	325	struct btree_iter *iter,
	326	struct bkey *replace_key)
	327	{
	328	struct cache_set *c = container_of(b, struct btree, keys)->c;
	329
829a60b9	330	uint64_t old_offset;
6f10f7d1	331	unsigned int old_size, sectors_found = 0;
829a60b9 KO	332
	333	BUG_ON(!KEY_OFFSET(insert));
	334	BUG_ON(!KEY_SIZE(insert));
	335
	336	while (1) {
	337	struct bkey *k = bch_btree_iter_next(iter);
1fae7cf0	338
829a60b9 KO	339	if (!k)
	340	break;
	341
	342	if (bkey_cmp(&START_KEY(k), insert) >= 0) {
	343	if (KEY_SIZE(k))
	344	break;
	345	else
	346	continue;
	347	}
	348
	349	if (bkey_cmp(k, &START_KEY(insert)) <= 0)
	350	continue;
	351
	352	old_offset = KEY_START(k);
	353	old_size = KEY_SIZE(k);
	354
	355	/*
	356	* We might overlap with 0 size extents; we can't skip these
	357	* because if they're in the set we're inserting to we have to
	358	* adjust them so they don't overlap with the key we're
	359	* inserting. But we don't want to check them for replace
	360	* operations.
	361	*/
	362
	363	if (replace_key && KEY_SIZE(k)) {
	364	/*
	365	* k might have been split since we inserted/found the
	366	* key we're replacing
	367	*/
6f10f7d1	368	unsigned int i;
829a60b9 KO	369	uint64_t offset = KEY_START(k) -
	370	KEY_START(replace_key);
	371
	372	/* But it must be a subset of the replace key */
	373	if (KEY_START(k) < KEY_START(replace_key) \|\|
	374	KEY_OFFSET(k) > KEY_OFFSET(replace_key))
	375	goto check_failed;
	376
	377	/* We didn't find a key that we were supposed to */
	378	if (KEY_START(k) > KEY_START(insert) + sectors_found)
	379	goto check_failed;
	380
3bdad1e4	381	if (!bch_bkey_equal_header(k, replace_key))
829a60b9 KO	382	goto check_failed;
	383
	384	/* skip past gen */
	385	offset <<= 8;
	386
	387	BUG_ON(!KEY_PTRS(replace_key));
	388
	389	for (i = 0; i < KEY_PTRS(replace_key); i++)
	390	if (k->ptr[i] != replace_key->ptr[i] + offset)
	391	goto check_failed;
	392
	393	sectors_found = KEY_OFFSET(k) - KEY_START(insert);
	394	}
	395
	396	if (bkey_cmp(insert, k) < 0 &&
	397	bkey_cmp(&START_KEY(insert), &START_KEY(k)) > 0) {
	398	/*
	399	* We overlapped in the middle of an existing key: that
	400	* means we have to split the old key. But we have to do
	401	* slightly different things depending on whether the
	402	* old key has been written out yet.
	403	*/
	404
	405	struct bkey *top;
	406
cb851149 JS	407	bch_subtract_dirty(k, c, KEY_START(insert),
cb851149 JS	408	KEY_SIZE(insert));
829a60b9 KO	409
	410	if (bkey_written(b, k)) {
	411	/*
	412	* We insert a new key to cover the top of the
	413	* old key, and the old key is modified in place
	414	* to represent the bottom split.
	415	*
	416	* It's completely arbitrary whether the new key
	417	* is the top or the bottom, but it has to match
	418	* up with what btree_sort_fixup() does - it
	419	* doesn't check for this kind of overlap, it
	420	* depends on us inserting a new key for the top
	421	* here.
	422	*/
	423	top = bch_bset_search(b, bset_tree_last(b),
	424	insert);
	425	bch_bset_insert(b, top, k);
	426	} else {
	427	BKEY_PADDED(key) temp;
	428	bkey_copy(&temp.key, k);
	429	bch_bset_insert(b, k, &temp.key);
	430	top = bkey_next(k);
	431	}
	432
	433	bch_cut_front(insert, top);
	434	bch_cut_back(&START_KEY(insert), k);
	435	bch_bset_fix_invalidated_key(b, k);
	436	goto out;
	437	}
	438
	439	if (bkey_cmp(insert, k) < 0) {
	440	bch_cut_front(insert, k);
	441	} else {
	442	if (bkey_cmp(&START_KEY(insert), &START_KEY(k)) > 0)
	443	old_offset = KEY_START(insert);
	444
	445	if (bkey_written(b, k) &&
	446	bkey_cmp(&START_KEY(insert), &START_KEY(k)) <= 0) {
	447	/*
	448	* Completely overwrote, so we don't have to
	449	* invalidate the binary search tree
	450	*/
	451	bch_cut_front(k, k);
	452	} else {
	453	__bch_cut_back(&START_KEY(insert), k);
	454	bch_bset_fix_invalidated_key(b, k);
	455	}
	456	}
	457
cb851149	458	bch_subtract_dirty(k, c, old_offset, old_size - KEY_SIZE(k));
829a60b9 KO	459	}
	460
	461	check_failed:
	462	if (replace_key) {
	463	if (!sectors_found) {
	464	return true;
	465	} else if (sectors_found < KEY_SIZE(insert)) {
	466	SET_KEY_OFFSET(insert, KEY_OFFSET(insert) -
	467	(KEY_SIZE(insert) - sectors_found));
	468	SET_KEY_SIZE(insert, sectors_found);
	469	}
	470	}
	471	out:
	472	if (KEY_DIRTY(insert))
	473	bcache_dev_sectors_dirty_add(c, KEY_INODE(insert),
	474	KEY_START(insert),
	475	KEY_SIZE(insert));
	476
	477	return false;
	478	}
	479
9aa61a99	480	bool __bch_extent_invalid(struct cache_set c, const struct bkey k)
65d45231 KO	481	{
	482	char buf[80];
	483
	484	if (!KEY_SIZE(k))
	485	return true;
	486
	487	if (KEY_SIZE(k) > KEY_OFFSET(k))
	488	goto bad;
	489
9aa61a99	490	if (__ptr_invalid(c, k))
65d45231 KO	491	goto bad;
	492
	493	return false;
	494	bad:
dc9d98d6	495	bch_extent_to_text(buf, sizeof(buf), k);
9aa61a99	496	cache_bug(c, "spotted extent %s: %s", buf, bch_ptr_status(c, k));
65d45231 KO	497	return true;
	498	}
	499
9aa61a99 KO	500	static bool bch_extent_invalid(struct btree_keys bk, const struct bkey k)
	501	{
	502	struct btree *b = container_of(bk, struct btree, keys);
1fae7cf0	503
9aa61a99 KO	504	return __bch_extent_invalid(b->c, k);
	505	}
	506
65d45231	507	static bool bch_extent_bad_expensive(struct btree b, const struct bkey k,
6f10f7d1	508	unsigned int ptr)
65d45231 KO	509	{
	510	struct bucket *g = PTR_BUCKET(b->c, k, ptr);
	511	char buf[80];
	512
	513	if (mutex_trylock(&b->c->bucket_lock)) {
	514	if (b->c->gc_mark_valid &&
4fe6a816 KO	515	(!GC_MARK(g) \|\|
	516	GC_MARK(g) == GC_MARK_METADATA \|\|
	517	(GC_MARK(g) != GC_MARK_DIRTY && KEY_DIRTY(k))))
65d45231 KO	518	goto err;
	519
	520	if (g->prio == BTREE_PRIO)
	521	goto err;
	522
	523	mutex_unlock(&b->c->bucket_lock);
	524	}
	525
	526	return false;
	527	err:
	528	mutex_unlock(&b->c->bucket_lock);
dc9d98d6	529	bch_extent_to_text(buf, sizeof(buf), k);
65d45231	530	btree_bug(b,
3a2fd9d5	531	"inconsistent extent pointer %s:\nbucket %zu pin %i prio %i gen %i last_gc %i mark %llu",
65d45231	532	buf, PTR_BUCKET_NR(b->c, k, ptr), atomic_read(&g->pin),
3a2fd9d5	533	g->prio, g->gen, g->last_gc, GC_MARK(g));
65d45231 KO	534	return true;
	535	}
	536
a85e968e	537	static bool bch_extent_bad(struct btree_keys bk, const struct bkey k)
65d45231	538	{
a85e968e	539	struct btree *b = container_of(bk, struct btree, keys);
6f10f7d1	540	unsigned int i, stale;
58ac3230	541	char buf[80];
65d45231 KO	542
65d45231 KO	543	if (!KEY_PTRS(k) \|\|
a85e968e	544	bch_extent_invalid(bk, k))
65d45231 KO	545	return true;
	546
	547	for (i = 0; i < KEY_PTRS(k); i++)
	548	if (!ptr_available(b->c, k, i))
	549	return true;
	550
65d45231	551	for (i = 0; i < KEY_PTRS(k); i++) {
65d45231 KO	552	stale = ptr_stale(b->c, k, i);
65d45231 KO	553
58ac3230 TJ	554	if (stale && KEY_DIRTY(k)) {
	555	bch_extent_to_text(buf, sizeof(buf), k);
	556	pr_info("stale dirty pointer, stale %u, key: %s",
	557	stale, buf);
	558	}
	559
149d0efa	560	btree_bug_on(stale > BUCKET_GC_GEN_MAX, b,
65d45231 KO	561	"key too stale: %i, need_gc %u",
	562	stale, b->c->need_gc);
	563
65d45231 KO	564	if (stale)
	565	return true;
	566
	567	if (expensive_debug_checks(b->c) &&
	568	bch_extent_bad_expensive(b, k, i))
	569	return true;
	570	}
	571
	572	return false;
	573	}
	574
	575	static uint64_t merge_chksums(struct bkey l, struct bkey r)
	576	{
	577	return (l->ptr[KEY_PTRS(l)] + r->ptr[KEY_PTRS(r)]) &
	578	~((uint64_t)1 << 63);
	579	}
	580
b0d30981 CL	581	static bool bch_extent_merge(struct btree_keys *bk,
	582	struct bkey *l,
	583	struct bkey *r)
65d45231	584	{
a85e968e	585	struct btree *b = container_of(bk, struct btree, keys);
6f10f7d1	586	unsigned int i;
65d45231 KO	587
	588	if (key_merging_disabled(b->c))
	589	return false;
	590
65d45231	591	for (i = 0; i < KEY_PTRS(l); i++)
cf33c1ee	592	if (l->ptr[i] + MAKE_PTR(0, KEY_SIZE(l), 0) != r->ptr[i] \|\|
65d45231 KO	593	PTR_BUCKET_NR(b->c, l, i) != PTR_BUCKET_NR(b->c, r, i))
	594	return false;
	595
	596	/* Keys with no pointers aren't restricted to one bucket and could
	597	* overflow KEY_SIZE
	598	*/
	599	if (KEY_SIZE(l) + KEY_SIZE(r) > USHRT_MAX) {
	600	SET_KEY_OFFSET(l, KEY_OFFSET(l) + USHRT_MAX - KEY_SIZE(l));
	601	SET_KEY_SIZE(l, USHRT_MAX);
	602
	603	bch_cut_front(l, r);
	604	return false;
	605	}
	606
	607	if (KEY_CSUM(l)) {
	608	if (KEY_CSUM(r))
	609	l->ptr[KEY_PTRS(l)] = merge_chksums(l, r);
	610	else
	611	SET_KEY_CSUM(l, 0);
	612	}
	613
	614	SET_KEY_OFFSET(l, KEY_OFFSET(l) + KEY_SIZE(r));
	615	SET_KEY_SIZE(l, KEY_SIZE(l) + KEY_SIZE(r));
	616
	617	return true;
	618	}
	619
	620	const struct btree_keys_ops bch_extent_keys_ops = {
	621	.sort_cmp = bch_extent_sort_cmp,
	622	.sort_fixup = bch_extent_sort_fixup,
829a60b9	623	.insert_fixup = bch_extent_insert_fixup,
65d45231 KO	624	.key_invalid = bch_extent_invalid,
	625	.key_bad = bch_extent_bad,
	626	.key_merge = bch_extent_merge,
dc9d98d6 KO	627	.key_to_text = bch_extent_to_text,
dc9d98d6 KO	628	.key_dump = bch_bkey_dump,
65d45231 KO	629	.is_extents = true,
65d45231 KO	630	};