xfs: teach xfs_btree_has_record to return false if there are gaps

The current implementation of xfs_btree_has_record returns true if it
finds /any/ record within the given range.  Unfortunately, that's not
what the predicate is supposed to do -- it's supposed to test if the
/entire/ range is covered by records.

Therefore, enhance the routine to check that the first record it
encounters starts earlier or at the same point as the low key, the last
record ends at or after the same point as the high key, and that there
aren't any gaps in the records.

Signed-off-by: Darrick J. Wong <djwong@kernel.org>

5 files changed, 124 insertions, 9 deletions

diff --git a/fs/xfs/libxfs/xfs_alloc.c b/fs/xfs/libxfs/xfs_alloc.c
index 95157f5a5a6c..4a17a5a167eb 100644
--- a/fs/xfs/libxfs/xfs_alloc.c
+++ b/fs/xfs/libxfs/xfs_alloc.c
@@ -3440,6 +3440,18 @@ xfs_alloc_query_all(
 	return xfs_btree_query_all(cur, xfs_alloc_query_range_helper, &query);
 }
 
+static bool
+xfs_alloc_has_key_gap(
+	struct xfs_btree_cur		*cur,
+	const union xfs_btree_key	*key1,
+	const union xfs_btree_key	*key2)
+{
+	xfs_agblock_t			next;
+
+	next = be32_to_cpu(key1->alloc.ar_startblock) + 1;
+	return next != be32_to_cpu(key2->alloc.ar_startblock);
+}
+
 /* Is there a record covering a given extent? */
 int
 xfs_alloc_has_record(
@@ -3456,7 +3468,8 @@ xfs_alloc_has_record(
 	memset(&high, 0xFF, sizeof(high));
 	high.a.ar_startblock = bno + len - 1;
 
-	return xfs_btree_has_record(cur, &low, &high, exists);
+	return xfs_btree_has_record(cur, &low, &high, xfs_alloc_has_key_gap,
+			exists);
 }
 
 /*
diff --git a/fs/xfs/libxfs/xfs_btree.c b/fs/xfs/libxfs/xfs_btree.c
index 298395481713..c8c9b07e75bc 100644
--- a/fs/xfs/libxfs/xfs_btree.c
+++ b/fs/xfs/libxfs/xfs_btree.c
@@ -4874,6 +4874,23 @@ xfs_btree_diff_two_ptrs(
 	return (int64_t)be32_to_cpu(a->s) - be32_to_cpu(b->s);
 }
 
+struct xbtree_hasrec {
+	xfs_btree_key_gap_fn	has_gap;
+
+	/* Keys for the start and end of the range we want to know about. */
+	union xfs_btree_key	start_key;
+	union xfs_btree_key	end_key;
+
+	/* Highest record key we've seen so far. */
+	union xfs_btree_key	high_key;
+
+	/* Are we processing the first record? */
+	bool			first_rec;
+
+	/* Did we see any records at all? */
+	bool			saw_anything;
+};
+
 /* If there's an extent, we're done. */
 STATIC int
 xfs_btree_has_record_helper(
@@ -4881,7 +4898,35 @@ xfs_btree_has_record_helper(
 	const union xfs_btree_rec	*rec,
 	void				*priv)
 {
-	return -ECANCELED;
+	union xfs_btree_key		rec_low_key;
+	union xfs_btree_key		rec_high_key;
+	struct xbtree_hasrec		*info = priv;
+	int64_t				res;
+
+	cur->bc_ops->init_key_from_rec(&rec_low_key, rec);
+	if (info->first_rec) {
+		/* Bail if the first record starts after the start key. */
+		res = cur->bc_ops->diff_two_keys(cur, &info->start_key,
+				&rec_low_key);
+		if (res < 0)
+			return -ECANCELED;
+
+		info->first_rec = false;
+	} else {
+		/* Bail if there's a gap with the previous record. */
+		if (info->has_gap(cur, &info->high_key, &rec_low_key))
+			return -ECANCELED;
+	}
+
+	info->saw_anything = true;
+
+	/* If the current record is higher than what we've seen, remember it. */
+	cur->bc_ops->init_high_key_from_rec(&rec_high_key, rec);
+	res = cur->bc_ops->diff_two_keys(cur, &rec_high_key, &info->high_key);
+	if (res > 0)
+		info->high_key = rec_high_key; /* struct copy */
+
+	return 0;
 }
 
 /* Is there a record covering a given range of keys? */
@@ -4890,18 +4935,45 @@ xfs_btree_has_record(
 	struct xfs_btree_cur		*cur,
 	const union xfs_btree_irec	*low,
 	const union xfs_btree_irec	*high,
+	xfs_btree_key_gap_fn		has_gap,
 	bool				*exists)
 {
+	struct xbtree_hasrec		info = {
+		.first_rec		= true,
+		.has_gap		= has_gap,
+	};
+	union xfs_btree_rec		rec;
+	int64_t				res;
 	int				error;
 
+	cur->bc_rec = *low;
+	cur->bc_ops->init_rec_from_cur(cur, &rec);
+	cur->bc_ops->init_key_from_rec(&info.start_key, &rec);
+
+	cur->bc_rec = *high;
+	cur->bc_ops->init_rec_from_cur(cur, &rec);
+	cur->bc_ops->init_key_from_rec(&info.end_key, &rec);
+
 	error = xfs_btree_query_range(cur, low, high,
-			&xfs_btree_has_record_helper, NULL);
+			&xfs_btree_has_record_helper, &info);
 	if (error == -ECANCELED) {
-		*exists = true;
+		/* Bailing out early means we found an uncovered area. */
+		*exists = false;
 		return 0;
 	}
-	*exists = false;
-	return error;
+	if (error)
+		return error;
+
+	if (!info.saw_anything) {
+		*exists = false;
+	} else {
+		/* Did the record set go at least as far as the end? */
+		res = cur->bc_ops->diff_two_keys(cur, &info.high_key,
+				&info.end_key);
+		*exists = (res >= 0);
+	}
+
+	return 0;
 }
 
 /* Are there more records in this btree? */
diff --git a/fs/xfs/libxfs/xfs_btree.h b/fs/xfs/libxfs/xfs_btree.h
index 4eaf8517f850..7aa3eb174edd 100644
--- a/fs/xfs/libxfs/xfs_btree.h
+++ b/fs/xfs/libxfs/xfs_btree.h
@@ -518,9 +518,13 @@ void xfs_btree_get_keys(struct xfs_btree_cur *cur,
 		struct xfs_btree_block *block, union xfs_btree_key *key);
 union xfs_btree_key *xfs_btree_high_key_from_key(struct xfs_btree_cur *cur,
 		union xfs_btree_key *key);
+typedef bool (*xfs_btree_key_gap_fn)(struct xfs_btree_cur *cur,
+		const union xfs_btree_key *key1,
+		const union xfs_btree_key *key2);
 int xfs_btree_has_record(struct xfs_btree_cur *cur,
 		const union xfs_btree_irec *low,
-		const union xfs_btree_irec *high, bool *exists);
+		const union xfs_btree_irec *high, xfs_btree_key_gap_fn has_gap,
+		bool *exists);
 bool xfs_btree_has_more_records(struct xfs_btree_cur *cur);
 struct xfs_ifork *xfs_btree_ifork_ptr(struct xfs_btree_cur *cur);
 
diff --git a/fs/xfs/libxfs/xfs_refcount.c b/fs/xfs/libxfs/xfs_refcount.c
index e5d767a7fc5d..64aec6279ad8 100644
--- a/fs/xfs/libxfs/xfs_refcount.c
+++ b/fs/xfs/libxfs/xfs_refcount.c
@@ -1764,6 +1764,18 @@ out_free:
 	return error;
 }
 
+static bool
+xfs_refcount_has_key_gap(
+	struct xfs_btree_cur		*cur,
+	const union xfs_btree_key	*key1,
+	const union xfs_btree_key	*key2)
+{
+	xfs_agblock_t			next;
+
+	next = be32_to_cpu(key1->refc.rc_startblock) + 1;
+	return next != be32_to_cpu(key2->refc.rc_startblock);
+}
+
 /* Is there a record covering a given extent? */
 int
 xfs_refcount_has_record(
@@ -1780,5 +1792,6 @@ xfs_refcount_has_record(
 	memset(&high, 0xFF, sizeof(high));
 	high.rc.rc_startblock = bno + len - 1;
 
-	return xfs_btree_has_record(cur, &low, &high, exists);
+	return xfs_btree_has_record(cur, &low, &high, xfs_refcount_has_key_gap,
+			exists);
 }
diff --git a/fs/xfs/libxfs/xfs_rmap.c b/fs/xfs/libxfs/xfs_rmap.c
index f45929b1b94a..b0eb45132682 100644
--- a/fs/xfs/libxfs/xfs_rmap.c
+++ b/fs/xfs/libxfs/xfs_rmap.c
@@ -2630,6 +2630,18 @@ xfs_rmap_compare(
 		return 0;
 }
 
+static bool
+xfs_rmap_has_key_gap(
+	struct xfs_btree_cur		*cur,
+	const union xfs_btree_key	*key1,
+	const union xfs_btree_key	*key2)
+{
+	xfs_agblock_t			next;
+
+	next = be32_to_cpu(key1->rmap.rm_startblock) + 1;
+	return next != be32_to_cpu(key2->rmap.rm_startblock);
+}
+
 /* Is there a record covering a given extent? */
 int
 xfs_rmap_has_record(
@@ -2646,7 +2658,8 @@ xfs_rmap_has_record(
 	memset(&high, 0xFF, sizeof(high));
 	high.r.rm_startblock = bno + len - 1;
 
-	return xfs_btree_has_record(cur, &low, &high, exists);
+	return xfs_btree_has_record(cur, &low, &high, xfs_rmap_has_key_gap,
+			exists);
 }
 
 /*