path: root/fs/bcachefs/extents.c

// SPDX-License-Identifier: GPL-2.0
/*
 * Copyright (C) 2010 Kent Overstreet <kent.overstreet@gmail.com>
 *
 * Code for managing the extent btree and dynamically updating the writeback
 * dirty sector count.
 */

#include "bcachefs.h"
#include "bkey_methods.h"
#include "btree_gc.h"
#include "btree_io.h"
#include "btree_iter.h"
#include "buckets.h"
#include "checksum.h"
#include "compress.h"
#include "debug.h"
#include "disk_groups.h"
#include "error.h"
#include "extents.h"
#include "inode.h"
#include "journal.h"
#include "replicas.h"
#include "super.h"
#include "super-io.h"
#include "trace.h"
#include "util.h"

static unsigned bch2_crc_field_size_max[] = {
	[BCH_EXTENT_ENTRY_crc32] = CRC32_SIZE_MAX,
	[BCH_EXTENT_ENTRY_crc64] = CRC64_SIZE_MAX,
	[BCH_EXTENT_ENTRY_crc128] = CRC128_SIZE_MAX,
};

static void bch2_extent_crc_pack(union bch_extent_crc *,
				 struct bch_extent_crc_unpacked,
				 enum bch_extent_entry_type);

static struct bch_dev_io_failures *dev_io_failures(struct bch_io_failures *f,
						   unsigned dev)
{
	struct bch_dev_io_failures *i;

	for (i = f->devs; i < f->devs + f->nr; i++)
		if (i->dev == dev)
			return i;

	return NULL;
}

void bch2_mark_io_failure(struct bch_io_failures *failed,
			  struct extent_ptr_decoded *p)
{
	struct bch_dev_io_failures *f = dev_io_failures(failed, p->ptr.dev);

	if (!f) {
		BUG_ON(failed->nr >= ARRAY_SIZE(failed->devs));

		f = &failed->devs[failed->nr++];
		f->dev		= p->ptr.dev;
		f->idx		= p->idx;
		f->nr_failed	= 1;
		f->nr_retries	= 0;
	} else if (p->idx != f->idx) {
		f->idx		= p->idx;
		f->nr_failed	= 1;
		f->nr_retries	= 0;
	} else {
		f->nr_failed++;
	}
}

/*
 * returns true if p1 is better than p2:
 */
static inline bool ptr_better(struct bch_fs *c,
			      const struct extent_ptr_decoded p1,
			      const struct extent_ptr_decoded p2)
{
	if (likely(!p1.idx && !p2.idx)) {
		struct bch_dev *dev1 = bch_dev_bkey_exists(c, p1.ptr.dev);
		struct bch_dev *dev2 = bch_dev_bkey_exists(c, p2.ptr.dev);

		u64 l1 = atomic64_read(&dev1->cur_latency[READ]);
		u64 l2 = atomic64_read(&dev2->cur_latency[READ]);

		/* Pick at random, biased in favor of the faster device: */

		return bch2_rand_range(l1 + l2) > l1;
	}

	if (bch2_force_reconstruct_read)
		return p1.idx > p2.idx;

	return p1.idx < p2.idx;
}

/*
 * This picks a non-stale pointer, preferably from a device other than @avoid.
 * Avoid can be NULL, meaning pick any. If there are no non-stale pointers to
 * other devices, it will still pick a pointer from avoid.
 */
int bch2_bkey_pick_read_device(struct bch_fs *c, struct bkey_s_c k,
			       struct bch_io_failures *failed,
			       struct extent_ptr_decoded *pick)
{
	struct bkey_ptrs_c ptrs = bch2_bkey_ptrs_c(k);
	const union bch_extent_entry *entry;
	struct extent_ptr_decoded p;
	struct bch_dev_io_failures *f;
	struct bch_dev *ca;
	int ret = 0;

	if (k.k->type == KEY_TYPE_error)
		return -EIO;

	bkey_for_each_ptr_decode(k.k, ptrs, p, entry) {
		/*
		 * Unwritten extent: no need to actually read, treat it as a
		 * hole and return 0s:
		 */
		if (p.ptr.unwritten)
			return 0;

		ca = bch_dev_bkey_exists(c, p.ptr.dev);

		/*
		 * If there are any dirty pointers it's an error if we can't
		 * read:
		 */
		if (!ret && !p.ptr.cached)
			ret = -EIO;

		if (p.ptr.cached && ptr_stale(ca, &p.ptr))
			continue;

		f = failed ? dev_io_failures(failed, p.ptr.dev) : NULL;
		if (f)
			p.idx = f->nr_failed < f->nr_retries
				? f->idx
				: f->idx + 1;

		if (!p.idx &&
		    !bch2_dev_is_readable(ca))
			p.idx++;

		if (bch2_force_reconstruct_read &&
		    !p.idx && p.has_ec)
			p.idx++;

		if (p.idx >= (unsigned) p.has_ec + 1)
			continue;

		if (ret > 0 && !ptr_better(c, p, *pick))
			continue;

		*pick = p;
		ret = 1;
	}

	return ret;
}

/* KEY_TYPE_btree_ptr: */

int bch2_btree_ptr_invalid(struct bch_fs *c, struct bkey_s_c k,
			   enum bkey_invalid_flags flags,
			   struct printbuf *err)
{
	int ret = 0;

	bkey_fsck_err_on(bkey_val_u64s(k.k) > BCH_REPLICAS_MAX, c, err,
			 btree_ptr_val_too_big,
			 "value too big (%zu > %u)", bkey_val_u64s(k.k), BCH_REPLICAS_MAX);

	ret = bch2_bkey_ptrs_invalid(c, k, flags, err);
fsck_err:
	return ret;
}

void bch2_btree_ptr_to_text(struct printbuf *out, struct bch_fs *c,
			    struct bkey_s_c k)
{
	bch2_bkey_ptrs_to_text(out, c, k);
}

int bch2_btree_ptr_v2_invalid(struct bch_fs *c, struct bkey_s_c k,
			      enum bkey_invalid_flags flags,
			      struct printbuf *err)
{
	int ret = 0;

	bkey_fsck_err_on(bkey_val_u64s(k.k) > BKEY_BTREE_PTR_VAL_U64s_MAX, c, err,
			 btree_ptr_v2_val_too_big,
			 "value too big (%zu > %zu)",
			 bkey_val_u64s(k.k), BKEY_BTREE_PTR_VAL_U64s_MAX);

	ret = bch2_bkey_ptrs_invalid(c, k, flags, err);
fsck_err:
	return ret;
}

void bch2_btree_ptr_v2_to_text(struct printbuf *out, struct bch_fs *c,
			       struct bkey_s_c k)
{
	struct bkey_s_c_btree_ptr_v2 bp = bkey_s_c_to_btree_ptr_v2(k);

	prt_printf(out, "seq %llx written %u min_key %s",
	       le64_to_cpu(bp.v->seq),
	       le16_to_cpu(bp.v->sectors_written),
	       BTREE_PTR_RANGE_UPDATED(bp.v) ? "R " : "");

	bch2_bpos_to_text(out, bp.v->min_key);
	prt_printf(out, " ");
	bch2_bkey_ptrs_to_text(out, c, k);
}

void bch2_btree_ptr_v2_compat(enum btree_id btree_id, unsigned version,
			      unsigned big_endian, int write,
			      struct bkey_s k)
{
	struct bkey_s_btree_ptr_v2 bp = bkey_s_to_btree_ptr_v2(k);

	compat_bpos(0, btree_id, version, big_endian, write, &bp.v->min_key);

	if (version < bcachefs_metadata_version_inode_btree_change &&
	    btree_id_is_extents(btree_id) &&
	    !bkey_eq(bp.v->min_key, POS_MIN))
		bp.v->min_key = write
			? bpos_nosnap_predecessor(bp.v->min_key)
			: bpos_nosnap_successor(bp.v->min_key);
}

/* KEY_TYPE_extent: */

bool bch2_extent_merge(struct bch_fs *c, struct bkey_s l, struct bkey_s_c r)
{
	struct bkey_ptrs   l_ptrs = bch2_bkey_ptrs(l);
	struct bkey_ptrs_c r_ptrs = bch2_bkey_ptrs_c(r);
	union bch_extent_entry *en_l;
	const union bch_extent_entry *en_r;
	struct extent_ptr_decoded lp, rp;
	bool use_right_ptr;
	struct bch_dev *ca;

	en_l = l_ptrs.start;
	en_r = r_ptrs.start;
	while (en_l < l_ptrs.end && en_r < r_ptrs.end) {
		if (extent_entry_type(en_l) != extent_entry_type(en_r))
			return false;

		en_l = extent_entry_next(en_l);
		en_r = extent_entry_next(en_r);
	}

	if (en_l < l_ptrs.end || en_r < r_ptrs.end)
		return false;

	en_l = l_ptrs.start;
	en_r = r_ptrs.start;
	lp.crc = bch2_extent_crc_unpack(l.k, NULL);
	rp.crc = bch2_extent_crc_unpack(r.k, NULL);

	while (__bkey_ptr_next_decode(l.k, l_ptrs.end, lp, en_l) &&
	       __bkey_ptr_next_decode(r.k, r_ptrs.end, rp, en_r)) {
		if (lp.ptr.offset + lp.crc.offset + lp.crc.live_size !=
		    rp.ptr.offset + rp.crc.offset ||
		    lp.ptr.dev			!= rp.ptr.dev ||
		    lp.ptr.gen			!= rp.ptr.gen ||
		    lp.ptr.unwritten		!= rp.ptr.unwritten ||
		    lp.has_ec			!= rp.has_ec)
			return false;

		/* Extents may not straddle buckets: */
		ca = bch_dev_bkey_exists(c, lp.ptr.dev);
		if (PTR_BUCKET_NR(ca, &lp.ptr) != PTR_BUCKET_NR(ca, &rp.ptr))
			return false;

		if (lp.has_ec			!= rp.has_ec ||
		    (lp.has_ec &&
		     (lp.ec.block		!= rp.ec.block ||
		      lp.ec.redundancy		!= rp.ec.redundancy ||
		      lp.ec.idx			!= rp.ec.idx)))
			return false;

		if (lp.crc.compression_type	!= rp.crc.compression_type ||
		    lp.crc.nonce		!= rp.crc.nonce)
			return false;

		if (lp.crc.offset + lp.crc.live_size + rp.crc.live_size <=
		    lp.crc.uncompressed_size) {
			/* can use left extent's crc entry */
		} else if (lp.crc.live_size <= rp.crc.offset) {
			/* can use right extent's crc entry */
		} else {
			/* check if checksums can be merged: */
			if (lp.crc.csum_type		!= rp.crc.csum_type ||
			    lp.crc.nonce		!= rp.crc.nonce ||
			    crc_is_compressed(lp.crc) ||
			    !bch2_checksum_mergeable(lp.crc.csum_type))
				return false;

			if (lp.crc.offset + lp.crc.live_size != lp.crc.compressed_size ||
			    rp.crc.offset)
				return false;

			if (lp.crc.csum_type &&
			    lp.crc.uncompressed